On Tue, Jan 29, 2019 at 02:18:24PM +0300, Ilya Maximets wrote: > On 28.01.2019 20:48, Ilya Maximets wrote: > > 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 ? > > There is another possibility to simplify above loop. > I read the article that mentioned at the file header. It clearly states that > implementation does not require to store height for each node. But the > deletion loop looks more sane there. We do not need to check the data using > the comparator, we just need to check that we still have 'x' on this level, > i.e. that 'update[i]->forward[i] == x' because that is the node that we're > removing and we do not need to update links on levels where we have no 'x'. > The loop will look like in the article: > > for (i = 0; i <= list->level; i++) { > if (update[i]->forward[i] != x) { > break; > } > update[i]->forward[i] = x->forward[i]; > } > > > So, there are 2 ways here: > 1. Keep the 'height' and use it inside 'skiplist_delete'. > > 2. Remove the 'height' and later simplify the loop inside > 'skiplist_delete' by checking only 'update[i]->forward[i] != x'. > > IMHO, we could go with the second approach. Apply this patch as is and > prepare another one for 'skiplist_delete' improvement. > > If so, > Acked-by: Ilya Maximets <[email protected]>
Thanks. I applied this patch and yours to master. _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
