| Message ID | 20190125202206.18297-1-blp@ovn.org |
|---|---|
| State | Accepted |
| Headers | show |
| Series | [ovs-dev] skiplist: Remove 'height' from skiplist_node. | expand |
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 <estebarb@hpe.com> 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 <estebarb@hpe.com> > Signed-off-by: Ben Pfaff <blp@ovn.org> > --- 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 ? > 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]); > >
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 <estebarb@hpe.com> 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 <estebarb@hpe.com> >> Signed-off-by: Ben Pfaff <blp@ovn.org> >> --- > > 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 <i.maximets@samsung.com> > > >> 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]); >> >>
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 <estebarb@hpe.com> 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 <estebarb@hpe.com> > >> Signed-off-by: Ben Pfaff <blp@ovn.org> > >> --- > > > > 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 <i.maximets@samsung.com> Thanks. I applied this patch and yours to master.
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]);
This member was write-only: it was initialized and never used later on. Thanks to Esteban Rodriguez Betancourt <estebarb@hpe.com> 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 <estebarb@hpe.com> Signed-off-by: Ben Pfaff <blp@ovn.org> --- lib/skiplist.c | 2 -- 1 file changed, 2 deletions(-)