[ https://issues.apache.org/jira/browse/PROTON-858?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14516805#comment-14516805 ]
Gordon Sim commented on PROTON-858: ----------------------------------- I've posted a fix here: https://reviews.apache.org/r/33623/. This is I think the simplest possible, though it can be optimised further. > 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)