LCOV - code coverage report
Current view: top level - test/unittests/heap - slot-set-unittest.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 146 148 98.6 %
Date: 2019-01-20 Functions: 23 32 71.9 %

          Line data    Source code
       1             : // Copyright 2016 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 <limits>
       6             : #include <map>
       7             : 
       8             : #include "src/globals.h"
       9             : #include "src/heap/slot-set.h"
      10             : #include "src/heap/spaces.h"
      11             : #include "src/objects/slots.h"
      12             : #include "testing/gtest/include/gtest/gtest.h"
      13             : 
      14             : namespace v8 {
      15             : namespace internal {
      16             : 
      17       15128 : TEST(SlotSet, InsertAndLookup1) {
      18           1 :   SlotSet set;
      19             :   set.SetPageStart(0);
      20       65537 :   for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
      21      131072 :     EXPECT_FALSE(set.Lookup(i));
      22             :   }
      23       65536 :   for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
      24       65536 :     set.Insert(i);
      25             :   }
      26       65536 :   for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
      27      131072 :     EXPECT_TRUE(set.Lookup(i));
      28           1 :   }
      29           1 : }
      30             : 
      31       15128 : TEST(SlotSet, InsertAndLookup2) {
      32           1 :   SlotSet set;
      33             :   set.SetPageStart(0);
      34       65537 :   for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
      35       65536 :     if (i % 7 == 0) {
      36        9363 :       set.Insert(i);
      37             :     }
      38             :   }
      39       65536 :   for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
      40       65536 :     if (i % 7 == 0) {
      41       18726 :       EXPECT_TRUE(set.Lookup(i));
      42             :     } else {
      43      112346 :       EXPECT_FALSE(set.Lookup(i));
      44             :     }
      45           1 :   }
      46           1 : }
      47             : 
      48       15128 : TEST(SlotSet, Iterate) {
      49           1 :   SlotSet set;
      50             :   set.SetPageStart(0);
      51       65537 :   for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
      52       65536 :     if (i % 7 == 0) {
      53        9363 :       set.Insert(i);
      54             :     }
      55             :   }
      56             : 
      57             :   set.Iterate(
      58             :       [](MaybeObjectSlot slot) {
      59        9363 :         if (slot.address() % 3 == 0) {
      60             :           return KEEP_SLOT;
      61             :         } else {
      62             :           return REMOVE_SLOT;
      63             :         }
      64             :       },
      65           1 :       SlotSet::KEEP_EMPTY_BUCKETS);
      66             : 
      67       65537 :   for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
      68       65536 :     if (i % 21 == 0) {
      69        6242 :       EXPECT_TRUE(set.Lookup(i));
      70             :     } else {
      71      124830 :       EXPECT_FALSE(set.Lookup(i));
      72             :     }
      73           1 :   }
      74           1 : }
      75             : 
      76       15128 : TEST(SlotSet, Remove) {
      77           1 :   SlotSet set;
      78             :   set.SetPageStart(0);
      79       65537 :   for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
      80       65536 :     if (i % 7 == 0) {
      81        9363 :       set.Insert(i);
      82             :     }
      83             :   }
      84             : 
      85       65536 :   for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
      86       65536 :     if (i % 3 != 0) {
      87       43690 :       set.Remove(i);
      88             :     }
      89             :   }
      90             : 
      91       65536 :   for (int i = 0; i < Page::kPageSize; i += kTaggedSize) {
      92       65536 :     if (i % 21 == 0) {
      93        6242 :       EXPECT_TRUE(set.Lookup(i));
      94             :     } else {
      95      124830 :       EXPECT_FALSE(set.Lookup(i));
      96             :     }
      97           1 :   }
      98           1 : }
      99             : 
     100        1675 : void CheckRemoveRangeOn(uint32_t start, uint32_t end) {
     101        1675 :   SlotSet set;
     102             :   set.SetPageStart(0);
     103        1675 :   uint32_t first = start == 0 ? 0 : start - kTaggedSize;
     104        1675 :   uint32_t last = end == Page::kPageSize ? end - kTaggedSize : end;
     105        5025 :   for (const auto mode :
     106        3350 :        {SlotSet::FREE_EMPTY_BUCKETS, SlotSet::KEEP_EMPTY_BUCKETS}) {
     107     2353486 :     for (uint32_t i = first; i <= last; i += kTaggedSize) {
     108     2350136 :       set.Insert(i);
     109             :     }
     110        3350 :     set.RemoveRange(start, end, mode);
     111        3350 :     if (first != start) {
     112        6492 :       EXPECT_TRUE(set.Lookup(first));
     113             :     }
     114        3350 :     if (last == end) {
     115        6696 :       EXPECT_TRUE(set.Lookup(last));
     116             :     }
     117     2346892 :     for (uint32_t i = start; i < end; i += kTaggedSize) {
     118     4687084 :       EXPECT_FALSE(set.Lookup(i));
     119             :     }
     120        1675 :   }
     121        1675 : }
     122             : 
     123       15128 : TEST(SlotSet, RemoveRange) {
     124           1 :   CheckRemoveRangeOn(0, Page::kPageSize);
     125           1 :   CheckRemoveRangeOn(1 * kTaggedSize, 1023 * kTaggedSize);
     126          35 :   for (uint32_t start = 0; start <= 32; start++) {
     127          33 :     CheckRemoveRangeOn(start * kTaggedSize, (start + 1) * kTaggedSize);
     128          33 :     CheckRemoveRangeOn(start * kTaggedSize, (start + 2) * kTaggedSize);
     129          33 :     const uint32_t kEnds[] = {32, 64, 100, 128, 1024, 1500, 2048};
     130         264 :     for (size_t i = 0; i < sizeof(kEnds) / sizeof(uint32_t); i++) {
     131        1617 :       for (int k = -3; k <= 3; k++) {
     132        1617 :         uint32_t end = (kEnds[i] + k);
     133        1617 :         if (start < end) {
     134        1607 :           CheckRemoveRangeOn(start * kTaggedSize, end * kTaggedSize);
     135             :         }
     136             :       }
     137             :     }
     138             :   }
     139           1 :   SlotSet set;
     140             :   set.SetPageStart(0);
     141           3 :   for (const auto mode :
     142           2 :        {SlotSet::FREE_EMPTY_BUCKETS, SlotSet::KEEP_EMPTY_BUCKETS}) {
     143           2 :     set.Insert(Page::kPageSize / 2);
     144           2 :     set.RemoveRange(0, Page::kPageSize, mode);
     145      131074 :     for (uint32_t i = 0; i < Page::kPageSize; i += kTaggedSize) {
     146      262144 :       EXPECT_FALSE(set.Lookup(i));
     147             :     }
     148           1 :   }
     149           1 : }
     150             : 
     151       15128 : TEST(TypedSlotSet, Iterate) {
     152           1 :   TypedSlotSet set(0);
     153             :   // These two constants must be static as a workaround
     154             :   // for a MSVC++ bug about lambda captures, see the discussion at
     155             :   // https://social.msdn.microsoft.com/Forums/SqlServer/4abf18bd-4ae4-4c72-ba3e-3b13e7909d5f
     156             :   static const int kDelta = 10000001;
     157           1 :   int added = 0;
     158          55 :   for (uint32_t i = 0; i < TypedSlotSet::kMaxOffset; i += kDelta) {
     159          54 :     SlotType type = static_cast<SlotType>(i % CLEARED_SLOT);
     160          54 :     set.Insert(type, i);
     161          54 :     ++added;
     162             :   }
     163           1 :   int iterated = 0;
     164             :   set.Iterate(
     165          54 :       [&iterated](SlotType type, Address addr) {
     166          54 :         uint32_t i = static_cast<uint32_t>(addr);
     167         108 :         EXPECT_EQ(i % CLEARED_SLOT, static_cast<uint32_t>(type));
     168         108 :         EXPECT_EQ(0u, i % kDelta);
     169          54 :         ++iterated;
     170          54 :         return i % 2 == 0 ? KEEP_SLOT : REMOVE_SLOT;
     171             :       },
     172           1 :       TypedSlotSet::KEEP_EMPTY_CHUNKS);
     173           1 :   EXPECT_EQ(added, iterated);
     174           1 :   iterated = 0;
     175             :   set.Iterate(
     176          27 :       [&iterated](SlotType type, Address addr) {
     177          27 :         uint32_t i = static_cast<uint32_t>(addr);
     178          54 :         EXPECT_EQ(0u, i % 2);
     179          27 :         ++iterated;
     180          27 :         return KEEP_SLOT;
     181             :       },
     182           1 :       TypedSlotSet::KEEP_EMPTY_CHUNKS);
     183           3 :   EXPECT_EQ(added / 2, iterated);
     184           1 : }
     185             : 
     186       15128 : TEST(TypedSlotSet, ClearInvalidSlots) {
     187           1 :   TypedSlotSet set(0);
     188             :   const int kHostDelta = 100;
     189             :   uint32_t entries = 10;
     190          11 :   for (uint32_t i = 0; i < entries; i++) {
     191          10 :     SlotType type = static_cast<SlotType>(i % CLEARED_SLOT);
     192          10 :     set.Insert(type, i * kHostDelta);
     193             :   }
     194             : 
     195             :   std::map<uint32_t, uint32_t> invalid_ranges;
     196           6 :   for (uint32_t i = 1; i < entries; i += 2) {
     197             :     invalid_ranges.insert(
     198          10 :         std::pair<uint32_t, uint32_t>(i * kHostDelta, i * kHostDelta + 1));
     199             :   }
     200             : 
     201           1 :   set.ClearInvalidSlots(invalid_ranges);
     202           7 :   for (std::map<uint32_t, uint32_t>::iterator it = invalid_ranges.begin();
     203             :        it != invalid_ranges.end(); ++it) {
     204           5 :     uint32_t start = it->first;
     205           5 :     uint32_t end = it->second;
     206             :     set.Iterate(
     207          25 :         [=](SlotType slot_type, Address slot_addr) {
     208          25 :           CHECK(slot_addr < start || slot_addr >= end);
     209          25 :           return KEEP_SLOT;
     210             :         },
     211           5 :         TypedSlotSet::KEEP_EMPTY_CHUNKS);
     212           1 :   }
     213           1 : }
     214             : 
     215       15128 : TEST(TypedSlotSet, Merge) {
     216           2 :   TypedSlotSet set0(0), set1(0);
     217             :   static const uint32_t kEntries = 10000;
     218       10001 :   for (uint32_t i = 0; i < kEntries; i++) {
     219       10000 :     set0.Insert(EMBEDDED_OBJECT_SLOT, 2 * i);
     220       10000 :     set1.Insert(EMBEDDED_OBJECT_SLOT, 2 * i + 1);
     221             :   }
     222           1 :   uint32_t count = 0;
     223           1 :   set0.Merge(&set1);
     224             :   set0.Iterate(
     225       20000 :       [&count](SlotType slot_type, Address slot_addr) {
     226       20000 :         if (count < kEntries) {
     227       20000 :           CHECK_EQ(slot_addr % 2, 0);
     228             :         } else {
     229       20000 :           CHECK_EQ(slot_addr % 2, 1);
     230             :         }
     231       20000 :         ++count;
     232       20000 :         return KEEP_SLOT;
     233             :       },
     234           1 :       TypedSlotSet::KEEP_EMPTY_CHUNKS);
     235           1 :   CHECK_EQ(2 * kEntries, count);
     236             :   set1.Iterate(
     237           0 :       [](SlotType slot_type, Address slot_addr) {
     238           0 :         CHECK(false);  // Unreachable.
     239             :         return KEEP_SLOT;
     240             :       },
     241           2 :       TypedSlotSet::KEEP_EMPTY_CHUNKS);
     242           1 : }
     243             : 
     244             : }  // namespace internal
     245        9075 : }  // namespace v8

Generated by: LCOV version 1.10