[ https://issues.apache.org/jira/browse/PROTON-858?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14522926#comment-14522926 ]
ASF subversion and git services commented on PROTON-858: -------------------------------------------------------- Commit 7d1007b479e42b635d9cda530197936a205e4c8e in qpid-proton's branch refs/heads/master from [~gsim] [ https://git-wip-us.apache.org/repos/asf?p=qpid-proton.git;h=7d1007b ] PROTON-858: fix deletion of entries from map to preserve consistency in coalesced hashing > 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 > Fix For: 0.9.1 > > > 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)