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]>
---
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]);
--
2.20.1
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
