Memory safety bug in hashtable replace about libucl HOT 7 OPEN

Addendum: It looks as if the replacement simply does not take place in some cases. I tried to add a work around where I just leaked a reference to the old value. When I do this, the later emit alternates between showing the old and new values, depending on the value of the random seed.

from libucl.

It looks as if this is somewhat more complicated. The sequence is:

1. Three properties in kh_ucl_hash_node_t values fields 0, 1, and 2.
2. ucl_object_delete_key deletes the one in field 0
3. ucl_object_replace_key replaces the one in field 2.

At the end of this, iterating over the fields shows the old and new versions of property 3.

This appears to happen only if the deleted property is the first one and another is renamed (removed / inserted at a fixed location). My guess is that the hash table is preserving insertion order by keeping an array of elements and having a hash map that points to them, but it isn't correctly updated in some corner cases.

Unfortunately, I have reached the limit of my ability to debug this code.

from libucl.

Yes, there is a hash + array to preserve order which makes things complicated. I will take a look shortly, thank you for your investigations!

from libucl.

Well, the whole deletion code is wrong in fact... I don't have a clear opinion about how to fix it. Khash pointers are not stable, so we cannot store them in an array. We also cannot store array index in ucl_object_t. The only alternative is to rewrite this data structure to probably an intrusive double-linked list.

from libucl.

This line is totally wrong: https://github.com/vstakhov/libucl/blob/master/src/ucl_hash.c#L515
It address hash table via kh_value using array indicies, which is just not correct. However, there is no way to do this procedure using kv_A function, as array stores ucl_object_t that has no array index stored nor access to the underlying hash element structure. Also, O(N) deletion is not something one would expect from a hash table...

from libucl.

O(n) deletion isn't ideal, but deleting keys in a config file is a fairly unusual case, so I'd much rather see O(n) deletion than deletion causing memory corruption.

from libucl.

Ok, I have updated the structure but hash table would now store pointers to entries not entries + each hash insertion would imply an additional malloc call :( It is very suboptimal so it might be revised at some point. However, I have not found any other way to keep order counting that khash uses open addressing so pointers safety is not an option, so I just cannot use pointers returned from khash in linked lists as they are invalidated on each hash resize.

from libucl.