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