Thanks a lot for the detailed explanation! I borrowed it and sent a
patch that removes the member:
https://patchwork.ozlabs.org/patch/1031285/
On Fri, Jan 25, 2019 at 07:00:02PM +0000, Rodriguez Betancourt, Esteban wrote:
> 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
