{"action":"created","issue":{"url":"https://api.github.com/repos/gnustep/libobjc2/issues/53","repository_url":"https://api.github.com/repos/gnustep/libobjc2","labels_url":"https://api.github.com/repos/gnustep/libobjc2/issues/53/labels{/name}","comments_url":"https://api.github.com/repos/gnustep/libobjc2/issues/53/comments","events_url":"https://api.github.com/repos/gnustep/libobjc2/issues/53/events","html_url":"https://github.com/gnustep/libobjc2/pull/53","id":299185420,"number":53,"title":"fix a mismanagement of the hash table that could lead to data loss","user":{"login":"DHowett-MSFT","id":14316954,"avatar_url":"https://avatars2.githubusercontent.com/u/14316954?v=4","gravatar_id":"","url":"https://api.github.com/users/DHowett-MSFT","html_url":"https://github.com/DHowett-MSFT","followers_url":"https://api.github.com/users/DHowett-MSFT/followers","following_url":"https://api.github.com/users/DHowett-MSFT/following{/other_user}","gists_url":"https://api.github.com/users/DHowett-MSFT/gists{/gist_id}","starred_url":"https://api.github.com/users/DHowett-MSFT/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/DHowett-MSFT/subscriptions","organizations_url":"https://api.github.com/users/DHowett-MSFT/orgs","repos_url":"https://api.github.com/users/DHowett-MSFT/repos","events_url":"https://api.github.com/users/DHowett-MSFT/events{/privacy}","received_events_url":"https://api.github.com/users/DHowett-MSFT/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2018-02-22T00:57:51Z","updated_at":"2018-02-22T09:47:10Z","closed_at":null,"author_association":"CONTRIBUTOR","pull_request":{"url":"https://api.github.com/repos/gnustep/libobjc2/pulls/53","html_url":"https://github.com/gnustep/libobjc2/pull/53","diff_url":"https://github.com/gnustep/libobjc2/pull/53.diff","patch_url":"https://github.com/gnustep/libobjc2/pull/53.patch"},"body":"This commit fixes a data loss bug in our hopscotch table implementation.\r\nRemoving values from the table can result in other values becoming\r\ndisconnected and lost.\r\n\r\nLet A, B, and C be values that all hash to cell 0.\r\nAssume the hopscotch distance factor H = 2.\r\n\r\n```\r\n   0     1     2\r\n+-----+-----+-----+\r\n|     |     |     |\r\n+-----+-----+-----+\r\n```\r\n\r\nAfter adding A\r\n```\r\n   0     1     2\r\n+-----+-----+-----+\r\n|  A  |     |     |\r\n+-----+-----+-----+\r\n   |\r\n   +-Neighbors =\r\n```\r\n\r\nAfter adding B\r\n\r\n```\r\n   0     1     2\r\n+-----+-----+-----+\r\n|  A  |  B  |     |\r\n+-----+-----+-----+\r\n   |\r\n   +-Neighbors = 1\r\n```\r\n\r\nAfter adding C\r\n\r\n```\r\n   0     1     2\r\n+-----+-----+-----+\r\n|  A  |  B  |  C  |\r\n+-----+-----+-----+\r\n   |\r\n   +-Neighbors = 1, 2\r\n```\r\n\r\nIf we then remove B,\r\n\r\n```\r\n   0     1     2\r\n+-----+-----+-----+\r\n|  A  | [X] |  C  |\r\n+-----+-----+-----+\r\n   |\r\n   +-Neighbors = 1, 2\r\n```\r\n\r\n* It is replaced with a placeholder [X].\r\n* A's neighbor table is not updated to reflect the loss.\r\n\r\nIf we then remove A,\r\n\r\n```\r\n   0     1     2\r\n+-----+-----+-----+\r\n| [X] | [X] | [C] |\r\n+-----+-----+-----+\r\n   |\r\n   +-Neighbors = 2\r\n```\r\n\r\n* The table is rebalanced to promote A's lowest neighbor to the primary\r\n  cell position.\r\n* C from cell 2 remains cell 0's neighbor.\r\n\r\nThe bug manifests if [X] the placeholder value passes the null check set\r\nout in MAP_TABLE_VALUE_NULL; that is, the placeholder is \"effectively\r\nnull\".\r\n\r\nLooking up the key that matches C will first evaluate its base cell, the\r\none that collided with the key in the first place. Since that is\r\nplaceholder [X], and [X] is \"effectively null\", the lookup stops.\r\n\r\nC is never retrieved from the hash table.\r\n\r\n---\r\nThe expedient solution to this bug is to update cell 0's neighbors when\r\nB is first removed, effectively skipping the hole:\r\n\r\nIf we remove B as above,\r\n\r\n```\r\n   0     1     2\r\n+-----+-----+-----+\r\n|  A  | [X] |  C  |\r\n+-----+-----+-----+\r\n   |\r\n   +-Neighbors = 2 <<< HERE\r\n```\r\n\r\nbut clear the neighbor bit for cell 1, the promotion that happens when A\r\nis later removed places C in cell 0.\r\n\r\n```\r\n   0     1     2\r\n+-----+-----+-----+\r\n|  C  | [X] | [X] |\r\n+-----+-----+-----+\r\n   |\r\n   +-Neighbors =\r\n```"},"comment":{"url":"https://api.github.com/repos/gnustep/libobjc2/issues/comments/367625098","html_url":"https://github.com/gnustep/libobjc2/pull/53#issuecomment-367625098","issue_url":"https://api.github.com/repos/gnustep/libobjc2/issues/53","id":367625098,"user":{"login":"davidchisnall","id":404454,"avatar_url":"https://avatars3.githubusercontent.com/u/404454?v=4","gravatar_id":"","url":"https://api.github.com/users/davidchisnall","html_url":"https://github.com/davidchisnall","followers_url":"https://api.github.com/users/davidchisnall/followers","following_url":"https://api.github.com/users/davidchisnall/following{/other_user}","gists_url":"https://api.github.com/users/davidchisnall/gists{/gist_id}","starred_url":"https://api.github.com/users/davidchisnall/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/davidchisnall/subscriptions","organizations_url":"https://api.github.com/users/davidchisnall/orgs","repos_url":"https://api.github.com/users/davidchisnall/repos","events_url":"https://api.github.com/users/davidchisnall/events{/privacy}","received_events_url":"https://api.github.com/users/davidchisnall/received_events","type":"User","site_admin":false},"created_at":"2018-02-22T09:47:10Z","updated_at":"2018-02-22T09:47:10Z","author_association":"COLLABORATOR","body":"Ouch.  I thought I'd fixed that about 7 years ago.\r\n\r\nAt some point, I plan on migrating a load of the code to C++ and using a better off-the-shelf hashtable implementation.  I've been investigating the Tessil ones for this purpose.  I want to get the new ABI stuff finished first though, because attempting to merge that and a bunch of file renames is going to be painful."}}
{"actor":{"display_login":"davidchisnall"}}