[jira] [Commented] (PROTON-858) unbalanced maps can get corrupted
[ https://issues.apache.org/jira/browse/PROTON-858?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14528447#comment-14528447 ] ASF subversion and git services commented on PROTON-858: Commit f82f96ab65dbcc61230b39151deb4e5b07b4407f in qpid-proton's branch refs/heads/kgiusti-python3 from [~gsim] [ https://git-wip-us.apache.org/repos/asf?p=qpid-proton.git;h=f82f96a ] PROTON-858: add test case for deletion of entry in a coalesced chain 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)
[jira] [Commented] (PROTON-858) unbalanced maps can get corrupted
[ https://issues.apache.org/jira/browse/PROTON-858?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14522927#comment-14522927 ] ASF subversion and git services commented on PROTON-858: Commit f82f96ab65dbcc61230b39151deb4e5b07b4407f in qpid-proton's branch refs/heads/master from [~gsim] [ https://git-wip-us.apache.org/repos/asf?p=qpid-proton.git;h=f82f96a ] PROTON-858: add test case for deletion of entry in a coalesced chain 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)
[jira] [Commented] (PROTON-858) unbalanced maps can get corrupted
[ https://issues.apache.org/jira/browse/PROTON-858?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=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)
[jira] [Commented] (PROTON-858) unbalanced maps can get corrupted
[ https://issues.apache.org/jira/browse/PROTON-858?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=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)
[jira] [Commented] (PROTON-858) unbalanced maps can get corrupted
[ https://issues.apache.org/jira/browse/PROTON-858?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=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)
[jira] [Commented] (PROTON-858) unbalanced maps can get corrupted
[ https://issues.apache.org/jira/browse/PROTON-858?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14506923#comment-14506923 ] 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 (v6.3.4#6332)
