Hello, 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. Sorry about the trouble it may have caused. Regards, Esteban > I'm really suspicious about the code in lib/skiplist.c, because I > noticed that it writes, but never reads, the 'height' member of struct > skiplist_node. I suspect that, therefore, in some circumstances the > code can read past the end of the 'forward' array in skiplist_node. > > I'd appreciate it if someone out there has time to verify that I'm right > or I'm wrong. > > Thanks, > > Ben. _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
