169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// Copyright 2011 the V8 project authors. All rights reserved. 269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// Redistribution and use in source and binary forms, with or without 369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// modification, are permitted provided that the following conditions are 469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// met: 569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// 669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// * Redistributions of source code must retain the above copyright 769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// notice, this list of conditions and the following disclaimer. 869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// * Redistributions in binary form must reproduce the above 969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// copyright notice, this list of conditions and the following 1069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// disclaimer in the documentation and/or other materials provided 1169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// with the distribution. 1269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// * Neither the name of Google Inc. nor the names of its 1369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// contributors may be used to endorse or promote products derived 1469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// from this software without specific prior written permission. 1569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// 1669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 2869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch#include "v8.h" 2969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 3069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch#include "api.h" 3169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch#include "debug.h" 3269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch#include "execution.h" 3369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch#include "factory.h" 3469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch#include "macro-assembler.h" 3569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch#include "objects.h" 3669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch#include "global-handles.h" 3769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch#include "cctest.h" 3869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 3969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdochusing namespace v8::internal; 4069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 413ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 4269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen MurdochTEST(ObjectHashTable) { 4369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch v8::HandleScope scope; 4469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch LocalContext context; 4569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch Handle<ObjectHashTable> table = FACTORY->NewObjectHashTable(23); 4669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch Handle<JSObject> a = FACTORY->NewJSArray(7); 4769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch Handle<JSObject> b = FACTORY->NewJSArray(11); 4869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch table = PutIntoObjectHashTable(table, a, b); 4969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch CHECK_EQ(table->NumberOfElements(), 1); 5069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch CHECK_EQ(table->Lookup(*a), *b); 5169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch CHECK_EQ(table->Lookup(*b), HEAP->undefined_value()); 5269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 5369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch // Keys still have to be valid after objects were moved. 5469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch HEAP->CollectGarbage(NEW_SPACE); 5569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch CHECK_EQ(table->NumberOfElements(), 1); 5669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch CHECK_EQ(table->Lookup(*a), *b); 5769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch CHECK_EQ(table->Lookup(*b), HEAP->undefined_value()); 5869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 5969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch // Keys that are overwritten should not change number of elements. 6069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch table = PutIntoObjectHashTable(table, a, FACTORY->NewJSArray(13)); 6169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch CHECK_EQ(table->NumberOfElements(), 1); 6269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch CHECK_NE(table->Lookup(*a), *b); 6369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 6469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch // Keys mapped to undefined should be removed permanently. 6569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch table = PutIntoObjectHashTable(table, a, FACTORY->undefined_value()); 6669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch CHECK_EQ(table->NumberOfElements(), 0); 6769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch CHECK_EQ(table->NumberOfDeletedElements(), 1); 6869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch CHECK_EQ(table->Lookup(*a), HEAP->undefined_value()); 6969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 703ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Keys should map back to their respective values and also should get 713ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // an identity hash code generated. 7269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch for (int i = 0; i < 100; i++) { 7369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch Handle<JSObject> key = FACTORY->NewJSArray(7); 7469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch Handle<JSObject> value = FACTORY->NewJSArray(11); 7569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch table = PutIntoObjectHashTable(table, key, value); 7669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch CHECK_EQ(table->NumberOfElements(), i + 1); 7769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch CHECK_NE(table->FindEntry(*key), ObjectHashTable::kNotFound); 7869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch CHECK_EQ(table->Lookup(*key), *value); 793ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch CHECK(key->GetIdentityHash(OMIT_CREATION)->ToObjectChecked()->IsSmi()); 803ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch } 813ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 823ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Keys never added to the map which already have an identity hash 833ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // code should not be found. 843ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (int i = 0; i < 100; i++) { 853ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Handle<JSObject> key = FACTORY->NewJSArray(7); 863ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch CHECK(key->GetIdentityHash(ALLOW_CREATION)->ToObjectChecked()->IsSmi()); 873ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch CHECK_EQ(table->FindEntry(*key), ObjectHashTable::kNotFound); 883ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch CHECK_EQ(table->Lookup(*key), HEAP->undefined_value()); 893ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch CHECK(key->GetIdentityHash(OMIT_CREATION)->ToObjectChecked()->IsSmi()); 9069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } 9169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 923ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Keys that don't have an identity hash should not be found and also 933ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // should not get an identity hash code generated. 943ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch for (int i = 0; i < 100; i++) { 953ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Handle<JSObject> key = FACTORY->NewJSArray(7); 963ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch CHECK_EQ(table->Lookup(*key), HEAP->undefined_value()); 973ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch CHECK_EQ(key->GetIdentityHash(OMIT_CREATION), HEAP->undefined_value()); 9869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } 9969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch} 1003ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1013ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1023ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#ifdef DEBUG 1033ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochTEST(ObjectHashSetCausesGC) { 1043ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch v8::HandleScope scope; 1053ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LocalContext context; 1063ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Handle<ObjectHashSet> table = FACTORY->NewObjectHashSet(1); 1073ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Handle<JSObject> key = FACTORY->NewJSArray(0); 1083ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1093ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Simulate a full heap so that generating an identity hash code 1103ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // in subsequent calls will request GC. 1113ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch FLAG_gc_interval = 0; 1123ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1133ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Calling Contains() should not cause GC ever. 1143ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch CHECK(!table->Contains(*key)); 1153ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1163ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Calling Remove() should not cause GC ever. 1173ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch CHECK(!table->Remove(*key)->IsFailure()); 1183ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1193ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Calling Add() should request GC by returning a failure. 1203ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch CHECK(table->Add(*key)->IsRetryAfterGC()); 1213ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 1223ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#endif 1233ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1243ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1253ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#ifdef DEBUG 1263ef787dbeca8a5fb1086949cda830dccee07bfbdBen MurdochTEST(ObjectHashTableCausesGC) { 1273ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch v8::HandleScope scope; 1283ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch LocalContext context; 1293ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Handle<ObjectHashTable> table = FACTORY->NewObjectHashTable(1); 1303ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch Handle<JSObject> key = FACTORY->NewJSArray(0); 1313ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1323ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Simulate a full heap so that generating an identity hash code 1333ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // in subsequent calls will request GC. 1343ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch FLAG_gc_interval = 0; 1353ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1363ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Calling Lookup() should not cause GC ever. 1373ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch CHECK(table->Lookup(*key)->IsUndefined()); 1383ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch 1393ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch // Calling Put() should request GC by returning a failure. 1403ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch CHECK(table->Put(*key, *key)->IsRetryAfterGC()); 1413ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch} 1423ef787dbeca8a5fb1086949cda830dccee07bfbdBen Murdoch#endif 143