[ 
https://issues.apache.org/jira/browse/PROTON-858?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14514059#comment-14514059
 ] 

Gordon Sim commented on PROTON-858:
-----------------------------------

As it turns out the use of the addressable region for entries that don't 
actually map there is *intended* and is a technique known as coalesced hashing. 
The error then is on the delete algorithm.

> 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)

Reply via email to