test-descriptor-array.cc 14.6 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
// Copyright 2020 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/base/logging.h"
#include "src/codegen/code-stub-assembler.h"
#include "src/common/globals.h"
#include "src/objects/descriptor-array.h"
#include "src/objects/property-details.h"
#include "src/objects/string-inl.h"
#include "src/objects/transitions-inl.h"
#include "test/cctest/cctest.h"
#include "test/cctest/compiler/code-assembler-tester.h"
#include "test/cctest/compiler/function-tester.h"
#include "test/cctest/test-transitions.h"

namespace v8 {
namespace internal {

namespace {

using Label = compiler::CodeAssemblerLabel;
template <class T>
using TVariable = compiler::TypedCodeAssemblerVariable<T>;

Handle<Name> NewNameWithHash(Isolate* isolate, const char* str, uint32_t hash,
                             bool is_integer) {
Patrick Thier's avatar
Patrick Thier committed
28 29 30
  uint32_t hash_field = Name::CreateHashFieldValue(
      hash, is_integer ? Name::HashFieldType::kIntegerIndex
                       : Name::HashFieldType::kHash);
31 32

  Handle<Name> name = isolate->factory()->NewOneByteInternalizedString(
33
      base::OneByteVector(str), hash_field);
34
  name->set_raw_hash_field(hash_field);
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
  CHECK(name->IsUniqueName());
  return name;
}

template <typename... Args>
MaybeHandle<Object> Call(Isolate* isolate, Handle<JSFunction> function,
                         Args... args) {
  const int nof_args = sizeof...(Args);
  Handle<Object> call_args[] = {args...};
  Handle<Object> receiver = isolate->factory()->undefined_value();
  return Execution::Call(isolate, function, receiver, nof_args, call_args);
}

void CheckDescriptorArrayLookups(Isolate* isolate, Handle<Map> map,
                                 std::vector<Handle<Name>>& names,
                                 Handle<JSFunction> csa_lookup) {
  // Test C++ implementation.
  {
53
    DisallowGarbageCollection no_gc;
54
    DescriptorArray descriptors = map->instance_descriptors(isolate);
55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
    DCHECK(descriptors.IsSortedNoDuplicates());
    int nof_descriptors = descriptors.number_of_descriptors();

    for (size_t i = 0; i < names.size(); ++i) {
      Name name = *names[i];
      InternalIndex index = descriptors.Search(name, nof_descriptors, false);
      CHECK(index.is_found());
      CHECK_EQ(i, index.as_uint32());
    }
  }

  // Test CSA implementation.
  if (!FLAG_jitless) {
    for (size_t i = 0; i < names.size(); ++i) {
      Handle<Object> name_index =
          Call(isolate, csa_lookup, map, names[i]).ToHandleChecked();
      CHECK(name_index->IsSmi());
      CHECK_EQ(DescriptorArray::ToKeyIndex(static_cast<int>(i)),
               Smi::ToInt(*name_index));
    }
  }
}

void CheckTransitionArrayLookups(Isolate* isolate,
                                 Handle<TransitionArray> transitions,
                                 std::vector<Handle<Map>>& maps,
                                 Handle<JSFunction> csa_lookup) {
  // Test C++ implementation.
  {
84
    DisallowGarbageCollection no_gc;
85 86 87 88
    DCHECK(transitions->IsSortedNoDuplicates());

    for (size_t i = 0; i < maps.size(); ++i) {
      Map expected_map = *maps[i];
89 90
      Name name = expected_map.instance_descriptors(isolate).GetKey(
          expected_map.LastAdded());
91 92 93 94 95 96 97 98 99 100 101 102

      Map map = transitions->SearchAndGetTargetForTesting(PropertyKind::kData,
                                                          name, NONE);
      CHECK(!map.is_null());
      CHECK_EQ(expected_map, map);
    }
  }

  // Test CSA implementation.
  if (!FLAG_jitless) {
    for (size_t i = 0; i < maps.size(); ++i) {
      Handle<Map> expected_map = maps[i];
103 104
      Handle<Name> name(expected_map->instance_descriptors(isolate).GetKey(
                            expected_map->LastAdded()),
105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
                        isolate);

      Handle<Object> transition_map =
          Call(isolate, csa_lookup, transitions, name).ToHandleChecked();
      CHECK(transition_map->IsMap());
      CHECK_EQ(*expected_map, *transition_map);
    }
  }
}

// Creates function with (Map, Name) arguments. Returns Smi with the index of
// the name value of the found descriptor (DescriptorArray::ToKeyIndex())
// or null otherwise.
Handle<JSFunction> CreateCsaDescriptorArrayLookup(Isolate* isolate) {
  // We are not allowed to generate code in jitless mode.
  if (FLAG_jitless) return Handle<JSFunction>();

  // Preallocate handle for the result in the current handle scope.
  Handle<JSFunction> result_function(JSFunction{}, isolate);

  const int kNumParams = 2;

  compiler::CodeAssemblerTester asm_tester(
      isolate, kNumParams + 1,  // +1 to include receiver.
129
      CodeKind::FOR_TESTING);
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
  {
    CodeStubAssembler m(asm_tester.state());

    auto map = m.Parameter<Map>(1);
    auto unique_name = m.Parameter<Name>(2);

    Label passed(&m), failed(&m);
    Label if_found(&m), if_not_found(&m);
    TVariable<IntPtrT> var_name_index(&m);

    TNode<Uint32T> bit_field3 = m.LoadMapBitField3(map);
    TNode<DescriptorArray> descriptors = m.LoadMapDescriptors(map);

    m.DescriptorLookup(unique_name, descriptors, bit_field3, &if_found,
                       &var_name_index, &if_not_found);

    m.BIND(&if_found);
    m.Return(m.SmiTag(var_name_index.value()));

    m.BIND(&if_not_found);
    m.Return(m.NullConstant());
  }

  {
    compiler::FunctionTester ft(asm_tester.GenerateCode(), kNumParams);
    // Copy function value to a handle created in the outer handle scope.
    result_function.PatchValue(*ft.function);
  }

  return result_function;
}

// Creates function with (TransitionArray, Name) arguments. Returns transition
// map if transition is found or null otherwise.
Handle<JSFunction> CreateCsaTransitionArrayLookup(Isolate* isolate) {
  // We are not allowed to generate code in jitless mode.
  if (FLAG_jitless) return Handle<JSFunction>();

  // Preallocate handle for the result in the current handle scope.
  Handle<JSFunction> result_function(JSFunction{}, isolate);

  const int kNumParams = 2;
  compiler::CodeAssemblerTester asm_tester(
      isolate, kNumParams + 1,  // +1 to include receiver.
174
      CodeKind::FOR_TESTING);
175 176 177 178 179 180 181 182 183 184 185 186 187 188 189
  {
    CodeStubAssembler m(asm_tester.state());

    auto transitions = m.Parameter<TransitionArray>(1);
    auto unique_name = m.Parameter<Name>(2);

    Label passed(&m), failed(&m);
    Label if_found(&m), if_not_found(&m);
    TVariable<IntPtrT> var_name_index(&m);

    m.TransitionLookup(unique_name, transitions, &if_found, &var_name_index,
                       &if_not_found);

    m.BIND(&if_found);
    {
190 191
      static_assert(static_cast<int>(PropertyKind::kData) == 0);
      static_assert(NONE == 0);
192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220
      const int kKeyToTargetOffset = (TransitionArray::kEntryTargetIndex -
                                      TransitionArray::kEntryKeyIndex) *
                                     kTaggedSize;
      TNode<Map> transition_map = m.CAST(m.GetHeapObjectAssumeWeak(
          m.LoadArrayElement(transitions, WeakFixedArray::kHeaderSize,
                             var_name_index.value(), kKeyToTargetOffset)));
      m.Return(transition_map);
    }

    m.BIND(&if_not_found);
    m.Return(m.NullConstant());
  }

  {
    compiler::FunctionTester ft(asm_tester.GenerateCode(), kNumParams);
    // Copy function value to a handle created in the outer handle scope.
    result_function.PatchValue(*ft.function);
  }

  return result_function;
}

}  // namespace

TEST(DescriptorArrayHashCollisionMassive) {
  CcTest::InitializeVM();
  Isolate* isolate = CcTest::i_isolate();
  HandleScope handle_scope(isolate);

Patrick Thier's avatar
Patrick Thier committed
221 222 223
  static_assert(Name::HashFieldTypeBits::kSize == 2,
                "This test might require updating if more HashFieldType values "
                "are introduced");
224 225 226 227

  std::vector<Handle<Name>> names;

  // Use the same hash value for all names.
Patrick Thier's avatar
Patrick Thier committed
228 229
  uint32_t hash = static_cast<uint32_t>(
      isolate->GenerateIdentityHash(Name::HashBits::kMax));
230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259

  for (int i = 0; i < kMaxNumberOfDescriptors / 2; ++i) {
    // Add pairs of names having the same base hash value but having different
    // values of is_integer bit.
    bool first_is_integer = (i & 1) != 0;
    bool second_is_integer = (i & 2) != 0;

    names.push_back(NewNameWithHash(isolate, "a", hash, first_is_integer));
    names.push_back(NewNameWithHash(isolate, "b", hash, second_is_integer));
  }

  // Create descriptor array with the created names by appending fields to some
  // map. DescriptorArray marking relies on the fact that it's attached to an
  // owning map.
  Handle<Map> map = Map::Create(isolate, 0);

  Handle<FieldType> any_type = FieldType::Any(isolate);

  for (size_t i = 0; i < names.size(); ++i) {
    map = Map::CopyWithField(isolate, map, names[i], any_type, NONE,
                             PropertyConstness::kMutable,
                             Representation::Tagged(), OMIT_TRANSITION)
              .ToHandleChecked();
  }

  Handle<JSFunction> csa_lookup = CreateCsaDescriptorArrayLookup(isolate);

  CheckDescriptorArrayLookups(isolate, map, names, csa_lookup);

  // Sort descriptor array and check it again.
260
  map->instance_descriptors(isolate).Sort();
261 262 263 264 265 266 267 268
  CheckDescriptorArrayLookups(isolate, map, names, csa_lookup);
}

TEST(DescriptorArrayHashCollision) {
  CcTest::InitializeVM();
  Isolate* isolate = CcTest::i_isolate();
  HandleScope handle_scope(isolate);

Patrick Thier's avatar
Patrick Thier committed
269 270 271
  static_assert(Name::HashFieldTypeBits::kSize == 2,
                "This test might require updating if more HashFieldType values "
                "are introduced");
272 273 274 275 276 277 278 279

  std::vector<Handle<Name>> names;
  uint32_t hash = 0;

  for (int i = 0; i < kMaxNumberOfDescriptors / 2; ++i) {
    if (i % 2 == 0) {
      // Change hash value for every pair of names.
      hash = static_cast<uint32_t>(
Patrick Thier's avatar
Patrick Thier committed
280
          isolate->GenerateIdentityHash(Name::HashBits::kMax));
281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310
    }

    // Add pairs of names having the same base hash value but having different
    // values of is_integer bit.
    bool first_is_integer = (i & 1) != 0;
    bool second_is_integer = (i & 2) != 0;

    names.push_back(NewNameWithHash(isolate, "a", hash, first_is_integer));
    names.push_back(NewNameWithHash(isolate, "b", hash, second_is_integer));
  }

  // Create descriptor array with the created names by appending fields to some
  // map. DescriptorArray marking relies on the fact that it's attached to an
  // owning map.
  Handle<Map> map = Map::Create(isolate, 0);

  Handle<FieldType> any_type = FieldType::Any(isolate);

  for (size_t i = 0; i < names.size(); ++i) {
    map = Map::CopyWithField(isolate, map, names[i], any_type, NONE,
                             PropertyConstness::kMutable,
                             Representation::Tagged(), OMIT_TRANSITION)
              .ToHandleChecked();
  }

  Handle<JSFunction> csa_lookup = CreateCsaDescriptorArrayLookup(isolate);

  CheckDescriptorArrayLookups(isolate, map, names, csa_lookup);

  // Sort descriptor array and check it again.
311
  map->instance_descriptors(isolate).Sort();
312 313 314 315 316 317 318 319
  CheckDescriptorArrayLookups(isolate, map, names, csa_lookup);
}

TEST(TransitionArrayHashCollisionMassive) {
  CcTest::InitializeVM();
  Isolate* isolate = CcTest::i_isolate();
  HandleScope handle_scope(isolate);

Patrick Thier's avatar
Patrick Thier committed
320 321 322
  static_assert(Name::HashFieldTypeBits::kSize == 2,
                "This test might require updating if more HashFieldType values "
                "are introduced");
323 324 325 326

  std::vector<Handle<Name>> names;

  // Use the same hash value for all names.
Patrick Thier's avatar
Patrick Thier committed
327 328
  uint32_t hash = static_cast<uint32_t>(
      isolate->GenerateIdentityHash(Name::HashBits::kMax));
329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372

  for (int i = 0; i < TransitionsAccessor::kMaxNumberOfTransitions / 2; ++i) {
    // Add pairs of names having the same base hash value but having different
    // values of is_integer bit.
    bool first_is_integer = (i & 1) != 0;
    bool second_is_integer = (i & 2) != 0;

    names.push_back(NewNameWithHash(isolate, "a", hash, first_is_integer));
    names.push_back(NewNameWithHash(isolate, "b", hash, second_is_integer));
  }

  // Create transitions for each name.
  Handle<Map> root_map = Map::Create(isolate, 0);

  std::vector<Handle<Map>> maps;

  Handle<FieldType> any_type = FieldType::Any(isolate);

  for (size_t i = 0; i < names.size(); ++i) {
    Handle<Map> map =
        Map::CopyWithField(isolate, root_map, names[i], any_type, NONE,
                           PropertyConstness::kMutable,
                           Representation::Tagged(), INSERT_TRANSITION)
            .ToHandleChecked();
    maps.push_back(map);
  }

  Handle<JSFunction> csa_lookup = CreateCsaTransitionArrayLookup(isolate);

  Handle<TransitionArray> transition_array(
      TestTransitionsAccessor(isolate, root_map).transitions(), isolate);

  CheckTransitionArrayLookups(isolate, transition_array, maps, csa_lookup);

  // Sort transition array and check it again.
  transition_array->Sort();
  CheckTransitionArrayLookups(isolate, transition_array, maps, csa_lookup);
}

TEST(TransitionArrayHashCollision) {
  CcTest::InitializeVM();
  Isolate* isolate = CcTest::i_isolate();
  HandleScope handle_scope(isolate);

Patrick Thier's avatar
Patrick Thier committed
373 374 375
  static_assert(Name::HashFieldTypeBits::kSize == 2,
                "This test might require updating if more HashFieldType values "
                "are introduced");
376 377 378 379

  std::vector<Handle<Name>> names;

  // Use the same hash value for all names.
Patrick Thier's avatar
Patrick Thier committed
380 381
  uint32_t hash = static_cast<uint32_t>(
      isolate->GenerateIdentityHash(Name::HashBits::kMax));
382 383 384 385 386

  for (int i = 0; i < TransitionsAccessor::kMaxNumberOfTransitions / 2; ++i) {
    if (i % 2 == 0) {
      // Change hash value for every pair of names.
      hash = static_cast<uint32_t>(
Patrick Thier's avatar
Patrick Thier committed
387
          isolate->GenerateIdentityHash(Name::HashBits::kMax));
388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427
    }
    // Add pairs of names having the same base hash value but having different
    // values of is_integer bit.
    bool first_is_integer = (i & 1) != 0;
    bool second_is_integer = (i & 2) != 0;

    names.push_back(NewNameWithHash(isolate, "a", hash, first_is_integer));
    names.push_back(NewNameWithHash(isolate, "b", hash, second_is_integer));
  }

  // Create transitions for each name.
  Handle<Map> root_map = Map::Create(isolate, 0);

  std::vector<Handle<Map>> maps;

  Handle<FieldType> any_type = FieldType::Any(isolate);

  for (size_t i = 0; i < names.size(); ++i) {
    Handle<Map> map =
        Map::CopyWithField(isolate, root_map, names[i], any_type, NONE,
                           PropertyConstness::kMutable,
                           Representation::Tagged(), INSERT_TRANSITION)
            .ToHandleChecked();
    maps.push_back(map);
  }

  Handle<JSFunction> csa_lookup = CreateCsaTransitionArrayLookup(isolate);

  Handle<TransitionArray> transition_array(
      TestTransitionsAccessor(isolate, root_map).transitions(), isolate);

  CheckTransitionArrayLookups(isolate, transition_array, maps, csa_lookup);

  // Sort transition array and check it again.
  transition_array->Sort();
  CheckTransitionArrayLookups(isolate, transition_array, maps, csa_lookup);
}

}  // namespace internal
}  // namespace v8