1 // Copyright 2017 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include <stdlib.h>
6 #include <sstream>
7 #include <utility>
8
9 #include "src/init/v8.h"
10 #include "src/objects/objects-inl.h"
11 #include "src/objects/objects.h"
12 #include "src/objects/ordered-hash-table.h"
13 #include "src/third_party/siphash/halfsiphash.h"
14 #include "src/utils/utils.h"
15
16 #include "test/cctest/cctest.h"
17
18 namespace v8 {
19 namespace internal {
20
AddToSetAndGetHash(Isolate * isolate,Handle<JSObject> obj,bool has_fast_properties)21 int AddToSetAndGetHash(Isolate* isolate, Handle<JSObject> obj,
22 bool has_fast_properties) {
23 CHECK_EQ(has_fast_properties, obj->HasFastProperties());
24 CHECK_EQ(ReadOnlyRoots(isolate).undefined_value(), obj->GetHash());
25 Handle<OrderedHashSet> set = isolate->factory()->NewOrderedHashSet();
26 OrderedHashSet::Add(isolate, set, obj);
27 CHECK_EQ(has_fast_properties, obj->HasFastProperties());
28 return Smi::ToInt(obj->GetHash());
29 }
30
GetPropertyDictionaryHash(Handle<JSObject> obj)31 int GetPropertyDictionaryHash(Handle<JSObject> obj) {
32 if (V8_ENABLE_SWISS_NAME_DICTIONARY_BOOL) {
33 return obj->property_dictionary_swiss().Hash();
34 } else {
35 return obj->property_dictionary().Hash();
36 }
37 }
38
GetPropertyDictionaryLength(Handle<JSObject> obj)39 int GetPropertyDictionaryLength(Handle<JSObject> obj) {
40 if (V8_ENABLE_SWISS_NAME_DICTIONARY_BOOL) {
41 return obj->property_dictionary_swiss().Capacity();
42 } else {
43 return obj->property_dictionary().length();
44 }
45 }
46
CheckIsDictionaryModeObject(Handle<JSObject> obj)47 void CheckIsDictionaryModeObject(Handle<JSObject> obj) {
48 if (V8_ENABLE_SWISS_NAME_DICTIONARY_BOOL) {
49 CHECK(obj->raw_properties_or_hash().IsSwissNameDictionary());
50 } else {
51 CHECK(obj->raw_properties_or_hash().IsNameDictionary());
52 }
53 }
54
CheckFastObject(Handle<JSObject> obj,int hash)55 void CheckFastObject(Handle<JSObject> obj, int hash) {
56 CHECK(obj->HasFastProperties());
57 CHECK(obj->raw_properties_or_hash().IsPropertyArray());
58 CHECK_EQ(Smi::FromInt(hash), obj->GetHash());
59 CHECK_EQ(hash, obj->property_array().Hash());
60 }
61
CheckDictionaryObject(Handle<JSObject> obj,int hash)62 void CheckDictionaryObject(Handle<JSObject> obj, int hash) {
63 CHECK(!obj->HasFastProperties());
64 CheckIsDictionaryModeObject(obj);
65 CHECK_EQ(Smi::FromInt(hash), obj->GetHash());
66 CHECK_EQ(hash, GetPropertyDictionaryHash(obj));
67 }
68
TEST(AddHashCodeToFastObjectWithoutProperties)69 TEST(AddHashCodeToFastObjectWithoutProperties) {
70 CcTest::InitializeVM();
71 v8::HandleScope scope(CcTest::isolate());
72 Isolate* isolate = CcTest::i_isolate();
73
74 Handle<JSObject> obj =
75 isolate->factory()->NewJSObject(isolate->object_function());
76 CHECK(obj->HasFastProperties());
77
78 int hash = AddToSetAndGetHash(isolate, obj, true);
79 CHECK_EQ(Smi::FromInt(hash), obj->raw_properties_or_hash());
80 }
81
TEST(AddHashCodeToFastObjectWithInObjectProperties)82 TEST(AddHashCodeToFastObjectWithInObjectProperties) {
83 CcTest::InitializeVM();
84 v8::HandleScope scope(CcTest::isolate());
85 Isolate* isolate = CcTest::i_isolate();
86
87 const char* source = " var x = { a: 1};";
88 CompileRun(source);
89
90 Handle<JSObject> obj = GetGlobal<JSObject>("x");
91 CHECK_EQ(ReadOnlyRoots(isolate).empty_fixed_array(),
92 obj->raw_properties_or_hash());
93
94 int hash = AddToSetAndGetHash(isolate, obj, true);
95 CHECK_EQ(Smi::FromInt(hash), obj->raw_properties_or_hash());
96 }
97
TEST(AddHashCodeToFastObjectWithPropertiesArray)98 TEST(AddHashCodeToFastObjectWithPropertiesArray) {
99 CcTest::InitializeVM();
100 v8::HandleScope scope(CcTest::isolate());
101 Isolate* isolate = CcTest::i_isolate();
102
103 const char* source =
104 " var x = {}; "
105 " x.a = 1; x.b = 2; x.c = 3; x.d = 4; x.e = 5; ";
106 CompileRun(source);
107
108 Handle<JSObject> obj = GetGlobal<JSObject>("x");
109 CHECK(obj->HasFastProperties());
110
111 int hash = AddToSetAndGetHash(isolate, obj, true);
112 CheckFastObject(obj, hash);
113 }
114
TEST(AddHashCodeToSlowObject)115 TEST(AddHashCodeToSlowObject) {
116 CcTest::InitializeVM();
117 v8::HandleScope scope(CcTest::isolate());
118 Isolate* isolate = CcTest::i_isolate();
119
120 Handle<JSObject> obj =
121 isolate->factory()->NewJSObject(isolate->object_function());
122 CHECK(obj->HasFastProperties());
123 JSObject::NormalizeProperties(isolate, obj, CLEAR_INOBJECT_PROPERTIES, 0,
124 "cctest/test-hashcode");
125
126 CheckIsDictionaryModeObject(obj);
127
128 int hash = AddToSetAndGetHash(isolate, obj, false);
129 CheckDictionaryObject(obj, hash);
130 }
131
TEST(TransitionFastWithInObjectToFastWithPropertyArray)132 TEST(TransitionFastWithInObjectToFastWithPropertyArray) {
133 CcTest::InitializeVM();
134 v8::HandleScope scope(CcTest::isolate());
135 Isolate* isolate = CcTest::i_isolate();
136
137 const char* source =
138 " var x = { };"
139 " x.a = 1; x.b = 2; x.c = 3; x.d = 4;";
140 CompileRun(source);
141
142 Handle<JSObject> obj = GetGlobal<JSObject>("x");
143 CHECK(obj->HasFastProperties());
144
145 int hash = AddToSetAndGetHash(isolate, obj, true);
146 CHECK_EQ(Smi::FromInt(hash), obj->raw_properties_or_hash());
147
148 int length = obj->property_array().length();
149 CompileRun("x.e = 5;");
150 CHECK(obj->property_array().length() > length);
151 CheckFastObject(obj, hash);
152 }
153
TEST(TransitionFastWithPropertyArray)154 TEST(TransitionFastWithPropertyArray) {
155 CcTest::InitializeVM();
156 v8::HandleScope scope(CcTest::isolate());
157 Isolate* isolate = CcTest::i_isolate();
158
159 const char* source =
160 " var x = { };"
161 " x.a = 1; x.b = 2; x.c = 3; x.d = 4; x.e = 5; ";
162 CompileRun(source);
163
164 Handle<JSObject> obj = GetGlobal<JSObject>("x");
165 CHECK(obj->raw_properties_or_hash().IsPropertyArray());
166
167 int hash = AddToSetAndGetHash(isolate, obj, true);
168 CHECK_EQ(hash, obj->property_array().Hash());
169
170 int length = obj->property_array().length();
171 CompileRun("x.f = 2; x.g = 5; x.h = 2");
172 CHECK(obj->property_array().length() > length);
173 CheckFastObject(obj, hash);
174 }
175
TEST(TransitionFastWithPropertyArrayToSlow)176 TEST(TransitionFastWithPropertyArrayToSlow) {
177 CcTest::InitializeVM();
178 v8::HandleScope scope(CcTest::isolate());
179 Isolate* isolate = CcTest::i_isolate();
180
181 const char* source =
182 " var x = { };"
183 " x.a = 1; x.b = 2; x.c = 3; x.d = 4; x.e = 5; ";
184 CompileRun(source);
185
186 Handle<JSObject> obj = GetGlobal<JSObject>("x");
187 CHECK(obj->raw_properties_or_hash().IsPropertyArray());
188
189 int hash = AddToSetAndGetHash(isolate, obj, true);
190 CHECK(obj->raw_properties_or_hash().IsPropertyArray());
191 CHECK_EQ(hash, obj->property_array().Hash());
192
193 JSObject::NormalizeProperties(isolate, obj, KEEP_INOBJECT_PROPERTIES, 0,
194 "cctest/test-hashcode");
195 CheckDictionaryObject(obj, hash);
196 }
197
TEST(TransitionSlowToSlow)198 TEST(TransitionSlowToSlow) {
199 CcTest::InitializeVM();
200 v8::HandleScope scope(CcTest::isolate());
201 Isolate* isolate = CcTest::i_isolate();
202
203 const char* source = " var x = {}; ";
204 CompileRun(source);
205
206 Handle<JSObject> obj = GetGlobal<JSObject>("x");
207 JSObject::NormalizeProperties(isolate, obj, CLEAR_INOBJECT_PROPERTIES, 0,
208 "cctest/test-hashcode");
209 CheckIsDictionaryModeObject(obj);
210
211 int hash = AddToSetAndGetHash(isolate, obj, false);
212 CHECK_EQ(hash, GetPropertyDictionaryHash(obj));
213
214 int length = GetPropertyDictionaryLength(obj);
215 CompileRun("for(var i = 0; i < 10; i++) { x['f'+i] = i };");
216 CHECK(GetPropertyDictionaryLength(obj) > length);
217 CheckDictionaryObject(obj, hash);
218 }
219
TEST(TransitionSlowToFastWithoutProperties)220 TEST(TransitionSlowToFastWithoutProperties) {
221 CcTest::InitializeVM();
222 v8::HandleScope scope(CcTest::isolate());
223 Isolate* isolate = CcTest::i_isolate();
224
225 Handle<JSObject> obj =
226 isolate->factory()->NewJSObject(isolate->object_function());
227 JSObject::NormalizeProperties(isolate, obj, CLEAR_INOBJECT_PROPERTIES, 0,
228 "cctest/test-hashcode");
229 CheckIsDictionaryModeObject(obj);
230
231 int hash = AddToSetAndGetHash(isolate, obj, false);
232 CHECK_EQ(hash, GetPropertyDictionaryHash(obj));
233
234 JSObject::MigrateSlowToFast(obj, 0, "cctest/test-hashcode");
235 CHECK_EQ(Smi::FromInt(hash), obj->GetHash());
236 }
237
TEST(TransitionSlowToFastWithPropertyArray)238 TEST(TransitionSlowToFastWithPropertyArray) {
239 CcTest::InitializeVM();
240 v8::HandleScope scope(CcTest::isolate());
241 Isolate* isolate = CcTest::i_isolate();
242
243 const char* source =
244 " var x = Object.create(null); "
245 " for(var i = 0; i < 10; i++) { x['f'+i] = i }; ";
246 CompileRun(source);
247
248 Handle<JSObject> obj = GetGlobal<JSObject>("x");
249 CheckIsDictionaryModeObject(obj);
250
251 int hash = AddToSetAndGetHash(isolate, obj, false);
252 CHECK_EQ(hash, GetPropertyDictionaryHash(obj));
253
254 JSObject::MigrateSlowToFast(obj, 0, "cctest/test-hashcode");
255 CheckFastObject(obj, hash);
256 }
257
258 namespace {
259
260 using HashFunction = uint32_t (*)(uint32_t key, uint64_t seed);
261
TestIntegerHashQuality(const int samples_log2,int num_buckets_log2,uint64_t seed,double max_var,HashFunction hash_function)262 void TestIntegerHashQuality(const int samples_log2, int num_buckets_log2,
263 uint64_t seed, double max_var,
264 HashFunction hash_function) {
265 int samples = 1 << samples_log2;
266 int num_buckets = 1 << num_buckets_log2;
267 int mean = samples / num_buckets;
268 int* buckets = new int[num_buckets];
269
270 for (int i = 0; i < num_buckets; i++) buckets[i] = 0;
271
272 for (int i = 0; i < samples; i++) {
273 uint32_t hash = hash_function(i, seed);
274 buckets[hash % num_buckets]++;
275 }
276
277 int sum_deviation = 0;
278 for (int i = 0; i < num_buckets; i++) {
279 int deviation = abs(buckets[i] - mean);
280 sum_deviation += deviation * deviation;
281 }
282 delete[] buckets;
283
284 double variation_coefficient = sqrt(sum_deviation * 1.0 / num_buckets) / mean;
285
286 printf("samples: 1 << %2d, buckets: 1 << %2d, var_coeff: %0.3f\n",
287 samples_log2, num_buckets_log2, variation_coefficient);
288 CHECK_LT(variation_coefficient, max_var);
289 }
HalfSipHash(uint32_t key,uint64_t seed)290 uint32_t HalfSipHash(uint32_t key, uint64_t seed) {
291 return halfsiphash(key, seed);
292 }
293
JenkinsHash(uint32_t key,uint64_t seed)294 uint32_t JenkinsHash(uint32_t key, uint64_t seed) {
295 return ComputeLongHash(static_cast<uint64_t>(key) ^ seed);
296 }
297
DefaultHash(uint32_t key,uint64_t seed)298 uint32_t DefaultHash(uint32_t key, uint64_t seed) {
299 return ComputeSeededHash(key, seed);
300 }
301 } // anonymous namespace
302
TestIntegerHashQuality(HashFunction hash_function)303 void TestIntegerHashQuality(HashFunction hash_function) {
304 TestIntegerHashQuality(17, 13, 0x123456789ABCDEFU, 0.4, hash_function);
305 TestIntegerHashQuality(16, 12, 0x123456789ABCDEFU, 0.4, hash_function);
306 TestIntegerHashQuality(15, 11, 0xFEDCBA987654321U, 0.4, hash_function);
307 TestIntegerHashQuality(14, 10, 0xFEDCBA987654321U, 0.4, hash_function);
308 TestIntegerHashQuality(13, 9, 1, 0.4, hash_function);
309 TestIntegerHashQuality(12, 8, 1, 0.4, hash_function);
310
311 TestIntegerHashQuality(17, 10, 0x123456789ABCDEFU, 0.2, hash_function);
312 TestIntegerHashQuality(16, 9, 0x123456789ABCDEFU, 0.2, hash_function);
313 TestIntegerHashQuality(15, 8, 0xFEDCBA987654321U, 0.2, hash_function);
314 TestIntegerHashQuality(14, 7, 0xFEDCBA987654321U, 0.2, hash_function);
315 TestIntegerHashQuality(13, 6, 1, 0.2, hash_function);
316 TestIntegerHashQuality(12, 5, 1, 0.2, hash_function);
317 }
318
TEST(HalfSipHashQuality)319 TEST(HalfSipHashQuality) { TestIntegerHashQuality(HalfSipHash); }
320
TEST(JenkinsHashQuality)321 TEST(JenkinsHashQuality) { TestIntegerHashQuality(JenkinsHash); }
322
TEST(DefaultHashQuality)323 TEST(DefaultHashQuality) { TestIntegerHashQuality(DefaultHash); }
324
325 } // namespace internal
326 } // namespace v8
327