[
https://issues.apache.org/jira/browse/PROTON-858?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Gordon Sim resolved PROTON-858.
-------------------------------
Resolution: Fixed
Fix Version/s: (was: 0.9.1)
0.10
Assignee: Gordon Sim
> 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
> Assignee: Gordon Sim
> Priority: Critical
> Fix For: 0.10
>
>
> 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)
