search

m4nh / skimap_ros

Ros implementation of Skimap
GNU General Public License v3.0
267 stars 101 forks source link

Stack corruption on insert (when compiled under Windows/VS2017) #26

Closed asbe closed 5 years ago

asbe commented 5 years ago

Hi, it seems that there is a slight issue in SkipList.hpp in the call NodeType *insert(K search_key, V new_value).

When search_key does not match curr_node->key a random level is selected, but the call randomlevel can return up to MAXLEVEL. When the code is compiled on Windows (with VS2017) it this behavior results in stack corruption by writing outside the range of update. Decrementing max return from randomlevel removes this issue.

Is this a bug that actually occurs on linux as well - but stays hidden because of more robust handling of stack corruptions? Or is it some portability issue. I have to admit that I'm a bit dense re the algorithm, so it is not entirely clear to me why the random level is chosen.

m4nh commented 5 years ago

Hi @asbe ! Thanks for the tips! Actually we never tried it on WINDOWS due to the ROS package wrapper, but it is very strange behavior.. the array is create with "MAXLEVEL + 1" size so also an index of MAXLEVEL is admissible.. when you debug it what is the actual "RandomLevel" value compared with the "udpate" size? ..

However the randomness here is added to choose different depths, for the current new node, in the hidden SkipList superstructure. This randomness is the way to let the SkipList looks like similar to a B-Tree without the drawbacks of the rebalancing.

asbe commented 5 years ago

Hi again. Thanks for the quick response. I've been looking at the code again. When debugging update is of size MAXLEVEL, and so is all of the forwards, so the corruption occurs in writing update[level] = header_node_; when new_level is randomly chosen to be MAXLEVEL. I have no clue why this occurs, however in many cases it seems that zero-index of the nodes are never used?!

m4nh commented 5 years ago

No ok! it's a bug.. because the update is created with

SkipListNode<K, V, MAXLEVEL> *update[MAXLEVEL];

Try to modify it with

SkipListNode<K, V, MAXLEVEL> *update[MAXLEVEL+1];

in such a way as to be consistent with forwards. Level 0 is never used because at level 0 is present the Full Linked List represented by the SkipList.. the higher is level, instead, the shorter is the representation of the list (i.e. random elements are conceptually removed)

asbe commented 5 years ago

Yes! Seems to fix it. I'll close the issue, but will not submit a PR for 2 characters edit.. :-)