From 7c8ac5a01b4ba5d4c7060875ea024e6efbc12893 Mon Sep 17 00:00:00 2001 From: Yang Guo Date: Thu, 10 Jan 2019 12:39:59 +0100 Subject: deps: cherry-pick c736883 from upstream V8 Original commit message: Optionally use halfsiphash for integer hashing. Change-Id: Ibd14f7b3fe78635675c76ae864112e3a3a7bc701 Reviewed-on: https://chromium-review.googlesource.com/c/1382463 Commit-Queue: Yang Guo Reviewed-by: Benedikt Meurer Cr-Commit-Position: refs/heads/master@{#58674} Refs: https://github.com/v8/v8/commit/c736883ed4e3ff92d1fd5a60497cec5311df9a25 --- deps/v8/BUILD.gn | 8 ++ deps/v8/PRESUBMIT.py | 10 +- deps/v8/src/third_party/siphash/LICENSE | 116 ++++++++++++++++++++++++ deps/v8/src/third_party/siphash/halfsiphash.cc | 83 +++++++++++++++++ deps/v8/src/third_party/siphash/halfsiphash.h | 17 ++++ deps/v8/src/utils.h | 5 + deps/v8/test/cctest/test-code-stub-assembler.cc | 2 +- deps/v8/test/cctest/test-hashcode.cc | 69 ++++++++++++++ 8 files changed, 308 insertions(+), 2 deletions(-) create mode 100644 deps/v8/src/third_party/siphash/LICENSE create mode 100644 deps/v8/src/third_party/siphash/halfsiphash.cc create mode 100644 deps/v8/src/third_party/siphash/halfsiphash.h (limited to 'deps') diff --git a/deps/v8/BUILD.gn b/deps/v8/BUILD.gn index 6bb77db7ea..10e1a28b0a 100644 --- a/deps/v8/BUILD.gn +++ b/deps/v8/BUILD.gn @@ -116,6 +116,9 @@ declare_args() { # tools/gen-postmortem-metadata.py for details. v8_postmortem_support = false + # Use Siphash as added protection against hash flooding attacks. + v8_use_siphash = false + # Switches off inlining in V8. v8_no_inline = false @@ -390,6 +393,9 @@ config("features") { if (v8_use_multi_snapshots) { defines += [ "V8_MULTI_SNAPSHOTS" ] } + if (v8_use_siphash) { + defines += [ "V8_USE_SIPHASH" ] + } } config("toolchain") { @@ -2502,6 +2508,8 @@ v8_source_set("v8_base") { "src/string-stream.h", "src/strtod.cc", "src/strtod.h", + "src/third_party/siphash/halfsiphash.cc", + "src/third_party/siphash/halfsiphash.h", "src/third_party/utf8-decoder/utf8-decoder.h", "src/torque-assembler.h", "src/tracing/trace-event.cc", diff --git a/deps/v8/PRESUBMIT.py b/deps/v8/PRESUBMIT.py index 88a64e727b..e48d51d8e5 100644 --- a/deps/v8/PRESUBMIT.py +++ b/deps/v8/PRESUBMIT.py @@ -43,6 +43,9 @@ _EXCLUDED_PATHS = ( r"^tools[\\\/].*", ) +_LICENSE_FILE = ( + r"LICENSE" +) # Regular expression that matches code which should not be run through cpplint. _NO_LINT_PATHS = ( @@ -311,8 +314,13 @@ def _CommonChecks(input_api, output_api): results.extend(_CheckCommitMessageBugEntry(input_api, output_api)) results.extend(input_api.canned_checks.CheckPatchFormatted( input_api, output_api)) + + # License files are taken as is, even if they include gendered pronouns. + license_filter = lambda path: input_api.FilterSourceFile( + path, black_list=_LICENSE_FILE) results.extend(input_api.canned_checks.CheckGenderNeutral( - input_api, output_api)) + input_api, output_api, source_file_filter=license_filter)) + results.extend(_V8PresubmitChecks(input_api, output_api)) results.extend(_CheckUnwantedDependencies(input_api, output_api)) results.extend( diff --git a/deps/v8/src/third_party/siphash/LICENSE b/deps/v8/src/third_party/siphash/LICENSE new file mode 100644 index 0000000000..670154e353 --- /dev/null +++ b/deps/v8/src/third_party/siphash/LICENSE @@ -0,0 +1,116 @@ +CC0 1.0 Universal + +Statement of Purpose + +The laws of most jurisdictions throughout the world automatically confer +exclusive Copyright and Related Rights (defined below) upon the creator and +subsequent owner(s) (each and all, an "owner") of an original work of +authorship and/or a database (each, a "Work"). + +Certain owners wish to permanently relinquish those rights to a Work for the +purpose of contributing to a commons of creative, cultural and scientific +works ("Commons") that the public can reliably and without fear of later +claims of infringement build upon, modify, incorporate in other works, reuse +and redistribute as freely as possible in any form whatsoever and for any +purposes, including without limitation commercial purposes. These owners may +contribute to the Commons to promote the ideal of a free culture and the +further production of creative, cultural and scientific works, or to gain +reputation or greater distribution for their Work in part through the use and +efforts of others. + +For these and/or other purposes and motivations, and without any expectation +of additional consideration or compensation, the person associating CC0 with a +Work (the "Affirmer"), to the extent that he or she is an owner of Copyright +and Related Rights in the Work, voluntarily elects to apply CC0 to the Work +and publicly distribute the Work under its terms, with knowledge of his or her +Copyright and Related Rights in the Work and the meaning and intended legal +effect of CC0 on those rights. + +1. Copyright and Related Rights. A Work made available under CC0 may be +protected by copyright and related or neighboring rights ("Copyright and +Related Rights"). Copyright and Related Rights include, but are not limited +to, the following: + + i. the right to reproduce, adapt, distribute, perform, display, communicate, + and translate a Work; + + ii. moral rights retained by the original author(s) and/or performer(s); + + iii. publicity and privacy rights pertaining to a person's image or likeness + depicted in a Work; + + iv. rights protecting against unfair competition in regards to a Work, + subject to the limitations in paragraph 4(a), below; + + v. rights protecting the extraction, dissemination, use and reuse of data in + a Work; + + vi. database rights (such as those arising under Directive 96/9/EC of the + European Parliament and of the Council of 11 March 1996 on the legal + protection of databases, and under any national implementation thereof, + including any amended or successor version of such directive); and + + vii. other similar, equivalent or corresponding rights throughout the world + based on applicable law or treaty, and any national implementations thereof. + +2. Waiver. To the greatest extent permitted by, but not in contravention of, +applicable law, Affirmer hereby overtly, fully, permanently, irrevocably and +unconditionally waives, abandons, and surrenders all of Affirmer's Copyright +and Related Rights and associated claims and causes of action, whether now +known or unknown (including existing as well as future claims and causes of +action), in the Work (i) in all territories worldwide, (ii) for the maximum +duration provided by applicable law or treaty (including future time +extensions), (iii) in any current or future medium and for any number of +copies, and (iv) for any purpose whatsoever, including without limitation +commercial, advertising or promotional purposes (the "Waiver"). Affirmer makes +the Waiver for the benefit of each member of the public at large and to the +detriment of Affirmer's heirs and successors, fully intending that such Waiver +shall not be subject to revocation, rescission, cancellation, termination, or +any other legal or equitable action to disrupt the quiet enjoyment of the Work +by the public as contemplated by Affirmer's express Statement of Purpose. + +3. Public License Fallback. Should any part of the Waiver for any reason be +judged legally invalid or ineffective under applicable law, then the Waiver +shall be preserved to the maximum extent permitted taking into account +Affirmer's express Statement of Purpose. In addition, to the extent the Waiver +is so judged Affirmer hereby grants to each affected person a royalty-free, +non transferable, non sublicensable, non exclusive, irrevocable and +unconditional license to exercise Affirmer's Copyright and Related Rights in +the Work (i) in all territories worldwide, (ii) for the maximum duration +provided by applicable law or treaty (including future time extensions), (iii) +in any current or future medium and for any number of copies, and (iv) for any +purpose whatsoever, including without limitation commercial, advertising or +promotional purposes (the "License"). The License shall be deemed effective as +of the date CC0 was applied by Affirmer to the Work. Should any part of the +License for any reason be judged legally invalid or ineffective under +applicable law, such partial invalidity or ineffectiveness shall not +invalidate the remainder of the License, and in such case Affirmer hereby +affirms that he or she will not (i) exercise any of his or her remaining +Copyright and Related Rights in the Work or (ii) assert any associated claims +and causes of action with respect to the Work, in either case contrary to +Affirmer's express Statement of Purpose. + +4. Limitations and Disclaimers. + + a. No trademark or patent rights held by Affirmer are waived, abandoned, + surrendered, licensed or otherwise affected by this document. + + b. Affirmer offers the Work as-is and makes no representations or warranties + of any kind concerning the Work, express, implied, statutory or otherwise, + including without limitation warranties of title, merchantability, fitness + for a particular purpose, non infringement, or the absence of latent or + other defects, accuracy, or the present or absence of errors, whether or not + discoverable, all to the greatest extent permissible under applicable law. + + c. Affirmer disclaims responsibility for clearing rights of other persons + that may apply to the Work or any use thereof, including without limitation + any person's Copyright and Related Rights in the Work. Further, Affirmer + disclaims responsibility for obtaining any necessary consents, permissions + or other rights required for any use of the Work. + + d. Affirmer understands and acknowledges that Creative Commons is not a + party to this document and has no duty or obligation with respect to this + CC0 or use of the Work. + +For more information, please see + diff --git a/deps/v8/src/third_party/siphash/halfsiphash.cc b/deps/v8/src/third_party/siphash/halfsiphash.cc new file mode 100644 index 0000000000..d3730c4819 --- /dev/null +++ b/deps/v8/src/third_party/siphash/halfsiphash.cc @@ -0,0 +1,83 @@ +/* + * SipHash reference C implementation + * + * Copyright (c) 2016 Jean-Philippe Aumasson + * + * To the extent possible under law, the author(s) have dedicated all + * copyright and related and neighboring rights to this software to the public + * domain worldwide. This software is distributed without any warranty. + * + * You should have received a copy of the CC0 Public Domain Dedication along + * with this software. If not, see + * . + */ + +/* + * Originally taken from https://github.com/veorq/SipHash/ + * Altered to match V8's use case. + */ + +#include + +#include "src/base/logging.h" +#include "src/base/v8-fallthrough.h" + +#define ROTL(x, b) (uint32_t)(((x) << (b)) | ((x) >> (32 - (b)))) + +#define SIPROUND \ + do { \ + v0 += v1; \ + v1 = ROTL(v1, 5); \ + v1 ^= v0; \ + v0 = ROTL(v0, 16); \ + v2 += v3; \ + v3 = ROTL(v3, 8); \ + v3 ^= v2; \ + v0 += v3; \ + v3 = ROTL(v3, 7); \ + v3 ^= v0; \ + v2 += v1; \ + v1 = ROTL(v1, 13); \ + v1 ^= v2; \ + v2 = ROTL(v2, 16); \ + } while (0) + +// Simplified half-siphash-2-4 implementation for 4 byte input. +uint32_t halfsiphash(const uint32_t value, const uint64_t seed) { + uint32_t v0 = 0; + uint32_t v1 = 0; + uint32_t v2 = 0x6c796765; + uint32_t v3 = 0x74656462; + uint32_t k[2]; + memcpy(k, &seed, sizeof(seed)); + uint32_t b = 4 << 24; + v3 ^= k[1]; + v2 ^= k[0]; + v1 ^= k[1]; + v0 ^= k[0]; + + v3 ^= value; + + // 2 c-rounds + SIPROUND; + SIPROUND; + + v0 ^= value; + v3 ^= b; + + // 2 c-rounds + SIPROUND; + SIPROUND; + + v0 ^= b; + v2 ^= 0xff; + + // 4 d-rounds + SIPROUND; + SIPROUND; + SIPROUND; + SIPROUND; + + b = v1 ^ v3; + return b; +} diff --git a/deps/v8/src/third_party/siphash/halfsiphash.h b/deps/v8/src/third_party/siphash/halfsiphash.h new file mode 100644 index 0000000000..7b55115774 --- /dev/null +++ b/deps/v8/src/third_party/siphash/halfsiphash.h @@ -0,0 +1,17 @@ +/* + * SipHash reference C implementation + * + * Copyright (c) 2016 Jean-Philippe Aumasson + * + * To the extent possible under law, the author(s) have dedicated all + * copyright and related and neighboring rights to this software to the public + * domain worldwide. This software is distributed without any warranty. + * + * You should have received a copy of the CC0 Public Domain Dedication along + * with this software. If not, see + * . + */ + +#include + +uint32_t halfsiphash(const uint32_t value, const uint64_t seed); diff --git a/deps/v8/src/utils.h b/deps/v8/src/utils.h index 90a1227a2b..51c22ffd70 100644 --- a/deps/v8/src/utils.h +++ b/deps/v8/src/utils.h @@ -22,6 +22,7 @@ #include "src/base/platform/platform.h" #include "src/base/v8-fallthrough.h" #include "src/globals.h" +#include "src/third_party/siphash/halfsiphash.h" #include "src/vector.h" #if defined(V8_OS_AIX) @@ -513,7 +514,11 @@ inline uint32_t ComputeLongHash(uint64_t key) { } inline uint32_t ComputeSeededHash(uint32_t key, uint64_t seed) { +#ifdef V8_USE_SIPHASH + return halfsiphash(key, seed); +#else return ComputeLongHash(static_cast(key) ^ seed); +#endif // V8_USE_SIPHASH } inline uint32_t ComputePointerHash(void* ptr) { diff --git a/deps/v8/test/cctest/test-code-stub-assembler.cc b/deps/v8/test/cctest/test-code-stub-assembler.cc index ffe9200eee..4289efa1d0 100644 --- a/deps/v8/test/cctest/test-code-stub-assembler.cc +++ b/deps/v8/test/cctest/test-code-stub-assembler.cc @@ -345,7 +345,7 @@ TEST(ComputeIntegerHash) { Handle result = ft.Call(key).ToHandleChecked(); uint32_t hash = ComputeSeededHash(k, isolate->heap()->HashSeed()); - Smi* expected = Smi::FromInt(hash & Smi::kMaxValue); + Smi* expected = Smi::FromInt(hash); CHECK_EQ(expected, Smi::cast(*result)); } } diff --git a/deps/v8/test/cctest/test-hashcode.cc b/deps/v8/test/cctest/test-hashcode.cc index 2059d53885..7c07ff6fdc 100644 --- a/deps/v8/test/cctest/test-hashcode.cc +++ b/deps/v8/test/cctest/test-hashcode.cc @@ -8,6 +8,8 @@ #include "src/objects-inl.h" #include "src/objects.h" +#include "src/third_party/siphash/halfsiphash.h" +#include "src/utils.h" #include "src/v8.h" #include "test/cctest/cctest.h" @@ -227,5 +229,72 @@ TEST(TransitionSlowToFastWithPropertyArray) { CheckFastObject(obj, hash); } +namespace { + +typedef uint32_t (*HashFunction)(uint32_t key, uint64_t seed); + +void TestIntegerHashQuality(const int samples_log2, int num_buckets_log2, + uint64_t seed, double max_var, + HashFunction hash_function) { + int samples = 1 << samples_log2; + int num_buckets = 1 << num_buckets_log2; + int mean = samples / num_buckets; + int* buckets = new int[num_buckets]; + + for (int i = 0; i < num_buckets; i++) buckets[i] = 0; + + for (int i = 0; i < samples; i++) { + uint32_t hash = hash_function(i, seed); + buckets[hash % num_buckets]++; + } + + int sum_deviation = 0; + for (int i = 0; i < num_buckets; i++) { + int deviation = abs(buckets[i] - mean); + sum_deviation += deviation * deviation; + } + delete[] buckets; + + double variation_coefficient = sqrt(sum_deviation * 1.0 / num_buckets) / mean; + + printf("samples: 1 << %2d, buckets: 1 << %2d, var_coeff: %0.3f\n", + samples_log2, num_buckets_log2, variation_coefficient); + CHECK_LT(variation_coefficient, max_var); +} +uint32_t HalfSipHash(uint32_t key, uint64_t seed) { + return halfsiphash(key, seed); +} + +uint32_t JenkinsHash(uint32_t key, uint64_t seed) { + return ComputeLongHash(static_cast(key) ^ seed); +} + +uint32_t DefaultHash(uint32_t key, uint64_t seed) { + return ComputeSeededHash(key, seed); +} +} // anonymous namespace + +void TestIntegerHashQuality(HashFunction hash_function) { + TestIntegerHashQuality(17, 13, 0x123456789ABCDEFU, 0.4, hash_function); + TestIntegerHashQuality(16, 12, 0x123456789ABCDEFU, 0.4, hash_function); + TestIntegerHashQuality(15, 11, 0xFEDCBA987654321U, 0.4, hash_function); + TestIntegerHashQuality(14, 10, 0xFEDCBA987654321U, 0.4, hash_function); + TestIntegerHashQuality(13, 9, 1, 0.4, hash_function); + TestIntegerHashQuality(12, 8, 1, 0.4, hash_function); + + TestIntegerHashQuality(17, 10, 0x123456789ABCDEFU, 0.2, hash_function); + TestIntegerHashQuality(16, 9, 0x123456789ABCDEFU, 0.2, hash_function); + TestIntegerHashQuality(15, 8, 0xFEDCBA987654321U, 0.2, hash_function); + TestIntegerHashQuality(14, 7, 0xFEDCBA987654321U, 0.2, hash_function); + TestIntegerHashQuality(13, 6, 1, 0.2, hash_function); + TestIntegerHashQuality(12, 5, 1, 0.2, hash_function); +} + +TEST(HalfSipHashQuality) { TestIntegerHashQuality(HalfSipHash); } + +TEST(JenkinsHashQuality) { TestIntegerHashQuality(JenkinsHash); } + +TEST(DefaultHashQuality) { TestIntegerHashQuality(DefaultHash); } + } // namespace internal } // namespace v8 -- cgit v1.2.3