Thank you for the analysis.
On Tue, Jan 29, 2019 at 05:24:52PM -0500, Mark Michelson wrote: > Hi Ben, > > I've taken a look at the code in skiplist.c and I think your concerns aren't > an issue. My search isn't exhaustive by any means, but I haven't seen any > way to make the implementation explode on itself. The implementation mirrors > the pseudocode used in the skiplist paper that is referenced at the top of > the file (including the naming of variables). The biggest difference I see > is that the sentinel "NIL" node at the end of the skiplist is not used. > Instead, there are checks for the nullity of x->forward[i] in a bunch of > places. > > As far as the "height" field is concerned, the skiplist paper doesn't ever > define exactly what fields are required for a skiplist node. However, you > can infer that the "forward" and "key" [1] fields are necessary. The author > of the file likely either thought they would need the height field and then > it turned out they didn't, or they put it in as a debugging aid. > > Mark Michelson > > [1] OVS code uses the term "data" instead of "key" even though most of the > other naming in the OVS code mirrors the skiplist paper. > > On 1/24/19 12:49 AM, Ben Pfaff wrote: > > 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 > > > _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
