On 25.01.2019 23:22, Ben Pfaff wrote:
> This member was write-only: it was initialized and never used later on.
>
> Thanks to Esteban Rodriguez Betancourt <[email protected]> for the
> following additional rationale:
>
> In this case you are right, the "height" member is not only not
> used, it is in fact not required, and can be safely removed,
> without causing security issues.
>
> The code can't read past the end of the 'forward' array because
> the skiplist "level" member, that specifies the maximum height of
> the whole skiplist.
>
> The "level" field is updated in insertions and deletions, so that
> in insertion the root node will point to the newly created item
> (if there isn't a list there yet). At the deletions, if the
> deleted item is the last one at that height then the root is
> modified to point to NULL at that height, and the whole skiplist
> height is decremented.
>
> For the forward_to case:
>
> - If a node is found in a list of level/height N, then it has
> height N (that's why it was inserted in that list)
>
> - forward_to travels throught nodes in the same level, so it is
> safe, as it doesn't go up.
>
> - If a node has height N, then it belongs to all the lists
> initiated at root->forward[n, n-1 ,n-2, ..., 0]
>
> - forward_to may go to lower levels, but that is safe, because of
> previous point.
>
> So, the protection is given by the "level" field in skiplist root
> node, and it is enough to guarantee that the code won't go off
> limits at 'forward' array. But yes, the height field is unused,
> unneeded, and can be removed safely.
>
> CC: Esteban Rodriguez Betancourt <[email protected]>
> Signed-off-by: Ben Pfaff <[email protected]>
> ---
Patch looks correct.
However, maybe we could use this field inside skiplist_delete ?
Here is the part of skiplist_delete function:
191 if (x && list->cmp(x->data, value, list->cfg) == 0) {
192 for (i = 0; i <= list->level; i++) {
193 if (!update[i]->forward[i] ||
194 list->cmp(update[i]->forward[i]->data, value,
195 list->cfg) != 0) {
196 break;
197 }
198 update[i]->forward[i] = x->forward[i];
199 }
On above lines comparator (list->cmp) used to determine if our "x"
exists on current level (i). I think, that we can simply replace this
with checking: if (i > x->height || !update[i]->forward[i]).
We may probably skip the "update[i]->forward[i]" check because it
could not be NULL if we still have "x" on this level.
So, It looks like we could re-write above loop dropping all the checks:
for (i = 0; i <= x->height; i++) {
update[i]->forward[i] = x->forward[i];
}
Any thoughts ?
> lib/skiplist.c | 2 --
> 1 file changed, 2 deletions(-)
>
> diff --git a/lib/skiplist.c b/lib/skiplist.c
> index 2cea6d8dfbee..1ae592623099 100644
> --- a/lib/skiplist.c
> +++ b/lib/skiplist.c
> @@ -40,7 +40,6 @@
> /* Skiplist node container */
> struct skiplist_node {
> const void *data; /* Pointer to saved data. */
> - int height; /* Height of this node. */
> struct skiplist_node *forward[]; /* Links to the next nodes. */
> };
>
> @@ -66,7 +65,6 @@ skiplist_create_node(int level, const void *object)
>
> new_node = xmalloc(alloc_size);
> new_node->data = object;
> - new_node->height = level;
> memset(new_node->forward, 0,
> (level + 1) * sizeof new_node->forward[0]);
>
>
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
