{"payload":{"feedbackUrl":"https://github.com/orgs/community/discussions/53140","repo":{"id":49165156,"defaultBranch":"master","name":"libobjc2","ownerLogin":"microsoft","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2016-01-06T22:17:23.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/6154722?v=4","public":true,"private":false,"isOrgOwned":true},"refInfo":{"name":"","listCacheKey":"v0:1685741013.448496","currentOid":""},"activityList":{"items":[{"before":"f2e4c5ac4b3ac17f413a38bbc7ee1242f9efd0f7","after":"ec2a4abdeb9b62b382c2e1e3f9787cc93da6346f","ref":"refs/heads/master","pushedAt":"2023-06-13T17:53:30.546Z","pushType":"pr_merge","commitsCount":2,"pusher":{"login":"microsoft-github-policy-service[bot]","name":null,"path":"/apps/microsoft-github-policy-service","primaryAvatarUrl":"https://avatars.githubusercontent.com/in/95686?s=80&v=4"},"commit":{"message":"Auto merge mandatory file pr\n\nThis pr is auto merged as it contains a mandatory file and is opened for more than 10 days.","shortMessageHtmlLink":"Auto merge mandatory file pr"}},{"before":"f2e4c5ac4b3ac17f413a38bbc7ee1242f9efd0f7","after":"c244201575f69a90041d83f69a90a09e4d7a837e","ref":"refs/heads/users/GitHubPolicyService/da00e394-33cc-4e7f-af42-457afe224f9e","pushedAt":"2023-06-02T21:23:33.904Z","pushType":"push","commitsCount":1,"pusher":{"login":"microsoft-github-policy-service[bot]","name":null,"path":"/apps/microsoft-github-policy-service","primaryAvatarUrl":"https://avatars.githubusercontent.com/in/95686?s=80&v=4"},"commit":{"message":"Microsoft mandatory file","shortMessageHtmlLink":"Microsoft mandatory file"}},{"before":null,"after":"f2e4c5ac4b3ac17f413a38bbc7ee1242f9efd0f7","ref":"refs/heads/users/GitHubPolicyService/da00e394-33cc-4e7f-af42-457afe224f9e","pushedAt":"2023-06-02T21:23:33.448Z","pushType":"branch_creation","commitsCount":0,"pusher":{"login":"microsoft-github-policy-service[bot]","name":null,"path":"/apps/microsoft-github-policy-service","primaryAvatarUrl":"https://avatars.githubusercontent.com/in/95686?s=80&v=4"},"commit":{"message":"Fix a mismanagement of the hash table that could lead to data loss.\n\nThis commit fixes a data loss bug in our hopscotch table implementation.\nRemoving values from the table can result in other values becoming\ndisconnected and lost.\n\nLet A, B, and C be values that all hash to cell 0.\nAssume the hopscotch distance factor H = 2.\n\n   0     1     2\n+-----+-----+-----+\n|     |     |     |\n+-----+-----+-----+\n\nAfter adding A\n   0     1     2\n+-----+-----+-----+\n|  A  |     |     |\n+-----+-----+-----+\n   |\n   +-Neighbors =\n\nAfter adding B\n   0     1     2\n+-----+-----+-----+\n|  A  |  B  |     |\n+-----+-----+-----+\n   |\n   +-Neighbors = 1\n\nAfter adding C\n   0     1     2\n+-----+-----+-----+\n|  A  |  B  |  C  |\n+-----+-----+-----+\n   |\n   +-Neighbors = 1, 2\n\nIf we then remove B,\n   0     1     2\n+-----+-----+-----+\n|  A  | [X] |  C  |\n+-----+-----+-----+\n   |\n   +-Neighbors = 1, 2\n\n* It is replaced with a placeholder [X].\n* A's neighbor table is not updated to reflect the loss.\n\nIf we then remove A,\n   0     1     2\n+-----+-----+-----+\n| [X] | [X] | [C] |\n+-----+-----+-----+\n   |\n   +-Neighbors = 2\n\n* The table is rebalanced to promote A's lowest neighbor to the primary\n  cell position.\n* C from cell 2 remains cell 0's neighbor.\n\nThe bug manifests if [X] the placeholder value passes the null check set\nout in MAP_TABLE_VALUE_NULL; that is, the placeholder is \"effectively\nnull\".\n\nLooking up the key that matches C will first evaluate its base cell, the\none that collided with the key in the first place. Since that is\nplaceholder [X], and [X] is \"effectively null\", the lookup stops.\n\nC is never retrieved from the hash table.\n\n---\nThe expedient solution to this bug is to update cell 0's neighbors when\nB is first removed, effectively skipping the hole:\n\nIf we remove B as above,\n   0     1     2\n+-----+-----+-----+\n|  A  | [X] |  C  |\n+-----+-----+-----+\n   |\n   +-Neighbors = 2 <<< HERE\n\nbut clear the neighbor bit for cell 1, the promotion that happens when A\nis later removed places C in cell 0.\n\n   0     1     2\n+-----+-----+-----+\n|  C  | [X] | [X] |\n+-----+-----+-----+\n   |\n   +-Neighbors =","shortMessageHtmlLink":"Fix a mismanagement of the hash table that could lead to data loss."}}],"hasNextPage":false,"hasPreviousPage":false,"activityType":"all","actor":null,"timePeriod":"all","sort":"DESC","perPage":30,"cursor":"Y3Vyc29yOnYyOpK7MjAyMy0wNi0xM1QxNzo1MzozMC41NDY0NjdazwAAAANAtu0e","startCursor":"Y3Vyc29yOnYyOpK7MjAyMy0wNi0xM1QxNzo1MzozMC41NDY0NjdazwAAAANAtu0e","endCursor":"Y3Vyc29yOnYyOpK7MjAyMy0wNi0wMlQyMToyMzozMy40NDg0OTZazwAAAAM5yao2"}},"title":"Activity · microsoft/libobjc2"}