{"action":"created","issue":{"url":"https://api.github.com/repos/rust-lang/rust/issues/38368","repository_url":"https://api.github.com/repos/rust-lang/rust","labels_url":"https://api.github.com/repos/rust-lang/rust/issues/38368/labels{/name}","comments_url":"https://api.github.com/repos/rust-lang/rust/issues/38368/comments","events_url":"https://api.github.com/repos/rust-lang/rust/issues/38368/events","html_url":"https://github.com/rust-lang/rust/pull/38368","id":195616043,"number":38368,"title":"Adaptive hashmap implementation","user":{"login":"arthurprs","id":715958,"avatar_url":"https://avatars.githubusercontent.com/u/715958?v=3","gravatar_id":"","url":"https://api.github.com/users/arthurprs","html_url":"https://github.com/arthurprs","followers_url":"https://api.github.com/users/arthurprs/followers","following_url":"https://api.github.com/users/arthurprs/following{/other_user}","gists_url":"https://api.github.com/users/arthurprs/gists{/gist_id}","starred_url":"https://api.github.com/users/arthurprs/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/arthurprs/subscriptions","organizations_url":"https://api.github.com/users/arthurprs/orgs","repos_url":"https://api.github.com/users/arthurprs/repos","events_url":"https://api.github.com/users/arthurprs/events{/privacy}","received_events_url":"https://api.github.com/users/arthurprs/received_events","type":"User","site_admin":false},"labels":[{"id":223796632,"url":"https://api.github.com/repos/rust-lang/rust/labels/relnotes","name":"relnotes","color":"fad8c7","default":false},{"id":211668062,"url":"https://api.github.com/repos/rust-lang/rust/labels/T-libs","name":"T-libs","color":"bfd4f2","default":false}],"state":"closed","locked":false,"assignee":{"login":"bluss","id":3209739,"avatar_url":"https://avatars.githubusercontent.com/u/3209739?v=3","gravatar_id":"","url":"https://api.github.com/users/bluss","html_url":"https://github.com/bluss","followers_url":"https://api.github.com/users/bluss/followers","following_url":"https://api.github.com/users/bluss/following{/other_user}","gists_url":"https://api.github.com/users/bluss/gists{/gist_id}","starred_url":"https://api.github.com/users/bluss/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bluss/subscriptions","organizations_url":"https://api.github.com/users/bluss/orgs","repos_url":"https://api.github.com/users/bluss/repos","events_url":"https://api.github.com/users/bluss/events{/privacy}","received_events_url":"https://api.github.com/users/bluss/received_events","type":"User","site_admin":false},"assignees":[{"login":"bluss","id":3209739,"avatar_url":"https://avatars.githubusercontent.com/u/3209739?v=3","gravatar_id":"","url":"https://api.github.com/users/bluss","html_url":"https://github.com/bluss","followers_url":"https://api.github.com/users/bluss/followers","following_url":"https://api.github.com/users/bluss/following{/other_user}","gists_url":"https://api.github.com/users/bluss/gists{/gist_id}","starred_url":"https://api.github.com/users/bluss/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bluss/subscriptions","organizations_url":"https://api.github.com/users/bluss/orgs","repos_url":"https://api.github.com/users/bluss/repos","events_url":"https://api.github.com/users/bluss/events{/privacy}","received_events_url":"https://api.github.com/users/bluss/received_events","type":"User","site_admin":false}],"milestone":null,"comments":29,"created_at":"2016-12-14T19:00:33Z","updated_at":"2017-02-20T08:34:04Z","closed_at":"2017-02-16T23:22:12Z","pull_request":{"url":"https://api.github.com/repos/rust-lang/rust/pulls/38368","html_url":"https://github.com/rust-lang/rust/pull/38368","diff_url":"https://github.com/rust-lang/rust/pull/38368.diff","patch_url":"https://github.com/rust-lang/rust/pull/38368.patch"},"body":"All credits to @pczarn who wrote https://github.com/rust-lang/rfcs/pull/1796 and https://github.com/contain-rs/hashmap2/pull/5\r\n\r\n **Background**\r\n\r\nRust std lib hashmap puts a strong emphasis on security, we did some improvements in https://github.com/rust-lang/rust/pull/37470 but in some very specific cases and for non-default hashers it's still vulnerable (see #36481).\r\n\r\nThis is a simplified version of https://github.com/rust-lang/rfcs/pull/1796 proposal sans switching hashers on the fly and other things that require an RFC process and further decisions. I think this part has great potential by itself.\r\n\r\n**Proposal**\r\nThis PR adds code checking for extra long probe and shifts lengths (see code comments and https://github.com/rust-lang/rfcs/pull/1796 for details), when those are encountered the hashmap will grow (even if the capacity limit is not reached yet) _greatly_ attenuating the degenerate performance case.\r\n\r\nWe need a lower bound on the minimum occupancy that may trigger the early resize, otherwise in extreme cases it's possible to turn the CPU attack into a memory attack. The PR code puts that lower bound at half of the max occupancy (defined by ResizePolicy). This reduces the protection (it could potentially be exploited between 0-50% occupancy) but makes it completely safe.\r\n\r\n**Drawbacks**\r\n\r\n* May interact badly with poor hashers.  Maps using those may not use the desired capacity.\r\n* It adds 2-3 branches to the common insert path, luckily those are highly predictable and there's room to shave some in future patches.\r\n* May complicate exposure of ResizePolicy in the future as the constants are a function of the fill factor.\r\n\r\n**Example**\r\n\r\nExample code that exploit the exposure of iteration order and weak hasher.\r\n\r\n```\r\nconst MERGE: usize = 10_000usize;\r\n#[bench]\r\nfn merge_dos(b: &mut Bencher) {\r\n    let first_map: $hashmap<usize, usize, FnvBuilder> = (0..MERGE).map(|i| (i, i)).collect();\r\n    let second_map: $hashmap<usize, usize, FnvBuilder> = (MERGE..MERGE * 2).map(|i| (i, i)).collect();\r\n    b.iter(|| {\r\n        let mut merged = first_map.clone();\r\n        for (&k, &v) in &second_map {\r\n            merged.insert(k, v);\r\n        }\r\n        ::test::black_box(merged);\r\n    });\r\n}\r\n```\r\n\r\n_91 is stdlib and _ad is patched (the end capacity in both cases is the same)\r\n\r\n```\r\nrunning 2 tests\r\ntest _91::merge_dos              ... bench:  47,311,843 ns/iter (+/- 2,040,302)\r\ntest _ad::merge_dos              ... bench:     599,099 ns/iter (+/- 83,270)\r\n```\r\n"},"comment":{"url":"https://api.github.com/repos/rust-lang/rust/issues/comments/281017174","html_url":"https://github.com/rust-lang/rust/pull/38368#issuecomment-281017174","issue_url":"https://api.github.com/repos/rust-lang/rust/issues/38368","id":281017174,"user":{"login":"pczarn","id":3356767,"avatar_url":"https://avatars.githubusercontent.com/u/3356767?v=3","gravatar_id":"","url":"https://api.github.com/users/pczarn","html_url":"https://github.com/pczarn","followers_url":"https://api.github.com/users/pczarn/followers","following_url":"https://api.github.com/users/pczarn/following{/other_user}","gists_url":"https://api.github.com/users/pczarn/gists{/gist_id}","starred_url":"https://api.github.com/users/pczarn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pczarn/subscriptions","organizations_url":"https://api.github.com/users/pczarn/orgs","repos_url":"https://api.github.com/users/pczarn/repos","events_url":"https://api.github.com/users/pczarn/events{/privacy}","received_events_url":"https://api.github.com/users/pczarn/received_events","type":"User","site_admin":false},"created_at":"2017-02-20T08:34:04Z","updated_at":"2017-02-20T08:34:04Z","body":"I agree. This issue also indicates that the hashmap load factor may be too high.\r\n\r\nThanks for help running these simulations."}}
{"actor":{"display_login":"pczarn"}}