Gordon Sim commented on PROTON-858:

Note that in example above, size is never greater than 8, so load is at most 
0.5 and expansion is never necessary. Note also that although the description 
says 'unbalanced', it doesn't require a huge imbalance for there to be 
problems, just an 'unlucky'  sequence.

> 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

Reply via email to