Gordon Sim created PROTON-858:
---------------------------------
Summary: unbalanced maps can get corrupted
Key: PROTON-858
URL: https://issues.apache.org/jira/browse/PROTON-858
Project: Qpid Proton
Issue Type: Bug
Components: proton-c
Affects Versions: 0.9
Reporter: Gordon Sim
Priority: Critical
I came across an issue caused by proton's inability to find a delivery for the
id specified in a disposition it received, although the delivery with that id
did indeed exist.
On further analysis, it appears that maps that are not well balanced can get
corrupted, such that the lookup function fails, even when the map 'contains' an
entry with the required key.
When adding an entry whose key maps to the same addressable index in the map as
an existing entry, a free entry is taken from the end of the list and linked to
that existing entry. However if all the entries outside the addressable range
are used - and since addressable = 0.86*capacity, there are actually not that
many of those - then a free entry from the addressable range is used for a key
that does not map to that index. This can then lead to a situation where the
deletion of an entry causes another to become unfindable.
(Detailed example: assume capacity is 16, i.e. first 13 entries (indices 0 to
12) are addressable, last three (indices 13, 14 and 15) are not.
Add value a with key 1, value b with key 2, value c with key 3. These take the
first three addressable entries respectively. Now add items that map to those
same addressable indexes, e.g. a2 with key 14, b2 with key 15, c2 with key 16.
The three free non-addressable entries at the end are used for these i.e.
indices 15, 14 and 13 respectively, and they are linked to the first three
entries (at indices 1, 2 and 3 respectively).
Now add d with key 4, which takes the 4th addressable index, then add d2 with
key 17, which maps to the same addressable index. We take the next free entry
which is at index 12 - *inside* the addressable range - set the key to 10,
value to d2 and link it to the entry at index 4.
Now delete key 17, which is at index 15. Then add value n with key 12. Index 12
is already taken by d2, so we use the newly vacated entry at index15 and link
that to the end of d2 at index 12.
Now we delete key 20 at index 12. Its the middle link in a chain of three so we
join the previous entry - d at index 4 to the next entry n at index 15.
Now you can't find n by its key 12).
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
