1 // Copyright 2011 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28 #include "src/v8.h" 29 #include "test/cctest/cctest.h" 30 31 #include "src/api.h" 32 #include "src/debug/debug.h" 33 #include "src/execution.h" 34 #include "src/factory.h" 35 #include "src/global-handles.h" 36 #include "src/macro-assembler.h" 37 #include "src/objects.h" 38 #include "test/cctest/heap/utils-inl.h" 39 40 using namespace v8::internal; 41 42 namespace { 43 44 45 template<typename HashMap> 46 static void TestHashMap(Handle<HashMap> table) { 47 Isolate* isolate = CcTest::i_isolate(); 48 Factory* factory = isolate->factory(); 49 50 Handle<JSObject> a = factory->NewJSArray(7); 51 Handle<JSObject> b = factory->NewJSArray(11); 52 table = HashMap::Put(table, a, b); 53 CHECK_EQ(table->NumberOfElements(), 1); 54 CHECK_EQ(table->Lookup(a), *b); 55 // When the key does not exist in the map, Lookup returns the hole. 56 CHECK_EQ(table->Lookup(b), CcTest::heap()->the_hole_value()); 57 58 // Keys still have to be valid after objects were moved. 59 CcTest::heap()->CollectGarbage(NEW_SPACE); 60 CHECK_EQ(table->NumberOfElements(), 1); 61 CHECK_EQ(table->Lookup(a), *b); 62 CHECK_EQ(table->Lookup(b), CcTest::heap()->the_hole_value()); 63 64 // Keys that are overwritten should not change number of elements. 65 table = HashMap::Put(table, a, factory->NewJSArray(13)); 66 CHECK_EQ(table->NumberOfElements(), 1); 67 CHECK_NE(table->Lookup(a), *b); 68 69 // Keys that have been removed are mapped to the hole. 70 bool was_present = false; 71 table = HashMap::Remove(table, a, &was_present); 72 CHECK(was_present); 73 CHECK_EQ(table->NumberOfElements(), 0); 74 CHECK_EQ(table->Lookup(a), CcTest::heap()->the_hole_value()); 75 76 // Keys should map back to their respective values and also should get 77 // an identity hash code generated. 78 for (int i = 0; i < 100; i++) { 79 Handle<JSReceiver> key = factory->NewJSArray(7); 80 Handle<JSObject> value = factory->NewJSArray(11); 81 table = HashMap::Put(table, key, value); 82 CHECK_EQ(table->NumberOfElements(), i + 1); 83 CHECK_NE(table->FindEntry(key), HashMap::kNotFound); 84 CHECK_EQ(table->Lookup(key), *value); 85 CHECK(key->GetIdentityHash()->IsSmi()); 86 } 87 88 // Keys never added to the map which already have an identity hash 89 // code should not be found. 90 for (int i = 0; i < 100; i++) { 91 Handle<JSReceiver> key = factory->NewJSArray(7); 92 CHECK(JSReceiver::GetOrCreateIdentityHash(key)->IsSmi()); 93 CHECK_EQ(table->FindEntry(key), HashMap::kNotFound); 94 CHECK_EQ(table->Lookup(key), CcTest::heap()->the_hole_value()); 95 CHECK(key->GetIdentityHash()->IsSmi()); 96 } 97 98 // Keys that don't have an identity hash should not be found and also 99 // should not get an identity hash code generated. 100 for (int i = 0; i < 100; i++) { 101 Handle<JSReceiver> key = factory->NewJSArray(7); 102 CHECK_EQ(table->Lookup(key), CcTest::heap()->the_hole_value()); 103 Object* identity_hash = key->GetIdentityHash(); 104 CHECK_EQ(identity_hash, CcTest::heap()->undefined_value()); 105 } 106 } 107 108 109 TEST(HashMap) { 110 LocalContext context; 111 v8::HandleScope scope(context->GetIsolate()); 112 Isolate* isolate = CcTest::i_isolate(); 113 TestHashMap(ObjectHashTable::New(isolate, 23)); 114 } 115 116 117 class ObjectHashTableTest: public ObjectHashTable { 118 public: 119 void insert(int entry, int key, int value) { 120 set(EntryToIndex(entry), Smi::FromInt(key)); 121 set(EntryToIndex(entry) + 1, Smi::FromInt(value)); 122 } 123 124 int lookup(int key) { 125 Handle<Object> key_obj(Smi::FromInt(key), GetIsolate()); 126 return Smi::cast(Lookup(key_obj))->value(); 127 } 128 129 int capacity() { 130 return Capacity(); 131 } 132 }; 133 134 135 TEST(HashTableRehash) { 136 LocalContext context; 137 Isolate* isolate = CcTest::i_isolate(); 138 v8::HandleScope scope(context->GetIsolate()); 139 // Test almost filled table. 140 { 141 Handle<ObjectHashTable> table = ObjectHashTable::New(isolate, 100); 142 ObjectHashTableTest* t = reinterpret_cast<ObjectHashTableTest*>(*table); 143 int capacity = t->capacity(); 144 for (int i = 0; i < capacity - 1; i++) { 145 t->insert(i, i * i, i); 146 } 147 t->Rehash(handle(Smi::FromInt(0), isolate)); 148 for (int i = 0; i < capacity - 1; i++) { 149 CHECK_EQ(i, t->lookup(i * i)); 150 } 151 } 152 // Test half-filled table. 153 { 154 Handle<ObjectHashTable> table = ObjectHashTable::New(isolate, 100); 155 ObjectHashTableTest* t = reinterpret_cast<ObjectHashTableTest*>(*table); 156 int capacity = t->capacity(); 157 for (int i = 0; i < capacity / 2; i++) { 158 t->insert(i, i * i, i); 159 } 160 t->Rehash(handle(Smi::FromInt(0), isolate)); 161 for (int i = 0; i < capacity / 2; i++) { 162 CHECK_EQ(i, t->lookup(i * i)); 163 } 164 } 165 } 166 167 168 #ifdef DEBUG 169 template<class HashSet> 170 static void TestHashSetCausesGC(Handle<HashSet> table) { 171 Isolate* isolate = CcTest::i_isolate(); 172 Factory* factory = isolate->factory(); 173 174 Handle<JSObject> key = factory->NewJSArray(0); 175 176 // Simulate a full heap so that generating an identity hash code 177 // in subsequent calls will request GC. 178 SimulateFullSpace(CcTest::heap()->new_space()); 179 SimulateFullSpace(CcTest::heap()->old_space()); 180 181 // Calling Contains() should not cause GC ever. 182 int gc_count = isolate->heap()->gc_count(); 183 CHECK(!table->Contains(key)); 184 CHECK(gc_count == isolate->heap()->gc_count()); 185 186 // Calling Remove() will not cause GC in this case. 187 bool was_present = false; 188 table = HashSet::Remove(table, key, &was_present); 189 CHECK(!was_present); 190 CHECK(gc_count == isolate->heap()->gc_count()); 191 192 // Calling Add() should cause GC. 193 table = HashSet::Add(table, key); 194 CHECK(gc_count < isolate->heap()->gc_count()); 195 } 196 #endif 197 198 199 #ifdef DEBUG 200 template<class HashMap> 201 static void TestHashMapCausesGC(Handle<HashMap> table) { 202 Isolate* isolate = CcTest::i_isolate(); 203 Factory* factory = isolate->factory(); 204 205 Handle<JSObject> key = factory->NewJSArray(0); 206 207 // Simulate a full heap so that generating an identity hash code 208 // in subsequent calls will request GC. 209 SimulateFullSpace(CcTest::heap()->new_space()); 210 SimulateFullSpace(CcTest::heap()->old_space()); 211 212 // Calling Lookup() should not cause GC ever. 213 CHECK(table->Lookup(key)->IsTheHole()); 214 215 // Calling Put() should request GC by returning a failure. 216 int gc_count = isolate->heap()->gc_count(); 217 HashMap::Put(table, key, key); 218 CHECK(gc_count < isolate->heap()->gc_count()); 219 } 220 221 222 TEST(ObjectHashTableCausesGC) { 223 i::FLAG_stress_compaction = false; 224 LocalContext context; 225 v8::HandleScope scope(context->GetIsolate()); 226 Isolate* isolate = CcTest::i_isolate(); 227 TestHashMapCausesGC(ObjectHashTable::New(isolate, 1)); 228 } 229 #endif 230 231 TEST(SetRequiresCopyOnCapacityChange) { 232 LocalContext context; 233 v8::HandleScope scope(context->GetIsolate()); 234 Isolate* isolate = CcTest::i_isolate(); 235 Handle<NameDictionary> dict = NameDictionary::New(isolate, 0, TENURED); 236 dict->SetRequiresCopyOnCapacityChange(); 237 Handle<Name> key = isolate->factory()->InternalizeString( 238 v8::Utils::OpenHandle(*v8_str("key"))); 239 Handle<Object> value = handle(Smi::FromInt(0), isolate); 240 Handle<NameDictionary> new_dict = 241 NameDictionary::Add(dict, key, value, PropertyDetails::Empty()); 242 CHECK_NE(*dict, *new_dict); 243 } 244 245 } // namespace 246
