Added mark bit cell iterator.

src/mark-compact.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1921 matching lines @@
 
 
 static void DiscoverGreyObjectsOnPage(MarkingDeque* marking_deque,
                                       MemoryChunk* p) {
   ASSERT(!marking_deque->IsFull());
   ASSERT(strcmp(Marking::kWhiteBitPattern, "00") == 0);
   ASSERT(strcmp(Marking::kBlackBitPattern, "10") == 0);
   ASSERT(strcmp(Marking::kGreyBitPattern, "11") == 0);
   ASSERT(strcmp(Marking::kImpossibleBitPattern, "01") == 0);
 
-  MarkBit::CellType* cells = p->markbits()->cells();
+  Address cell_base;

[titzer, 2013/07/15 13:42:06]

Can be in the loop, no? And also below.

[Hannes Payer (out of office), 2013/07/16 12:13:00]

Done.

+  MarkBit::CellType* cell;

[Michael Starzinger, 2013/07/15 14:01:46]

nit: Lets move the declaration of the variables into the loop where they are
actually defined. More local, easier to read.

[Hannes Payer (out of office), 2013/07/16 12:13:00]

Done.

+  for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
+    cell_base = it.CurrentCellBase();
+    cell = it.CurrentCell();
 
-  int last_cell_index =
-      Bitmap::IndexToCell(
-          Bitmap::CellAlignIndex(
-              p->AddressToMarkbitIndex(p->area_end())));
-
-  Address cell_base = p->area_start();
-  int cell_index = Bitmap::IndexToCell(
-          Bitmap::CellAlignIndex(
-              p->AddressToMarkbitIndex(cell_base)));
-
-
-  for (;
-       cell_index < last_cell_index;
-       cell_index++, cell_base += 32 * kPointerSize) {
-    ASSERT(static_cast<unsigned>(cell_index) ==
-           Bitmap::IndexToCell(
-               Bitmap::CellAlignIndex(
-                   p->AddressToMarkbitIndex(cell_base))));
-
-    const MarkBit::CellType current_cell = cells[cell_index];
+    const MarkBit::CellType current_cell = *cell;
     if (current_cell == 0) continue;
 
-    const MarkBit::CellType next_cell = cells[cell_index + 1];
-    MarkBit::CellType grey_objects = current_cell &
-        ((current_cell >> 1) | (next_cell << (Bitmap::kBitsPerCell - 1)));
+    MarkBit::CellType grey_objects;
+    if (it.HasNext()) {
+      const MarkBit::CellType next_cell = *(cell+1);
+      grey_objects = current_cell &
+          ((current_cell >> 1) | (next_cell << (Bitmap::kBitsPerCell - 1)));
+    } else {
+      grey_objects = current_cell & (current_cell >> 1);
+    }
 
     int offset = 0;
     while (grey_objects != 0) {
       int trailing_zeros = CompilerIntrinsics::CountTrailingZeros(grey_objects);
       grey_objects >>= trailing_zeros;
       offset += trailing_zeros;
-      MarkBit markbit(&cells[cell_index], 1 << offset, false);
+      MarkBit markbit(cell, 1 << offset, false);
       ASSERT(Marking::IsGrey(markbit));
       Marking::GreyToBlack(markbit);
       Address addr = cell_base + offset * kPointerSize;
       HeapObject* object = HeapObject::FromAddress(addr);
       MemoryChunk::IncrementLiveBytesFromGC(object->address(), object->Size());
       marking_deque->PushBlack(object);
       if (marking_deque->IsFull()) return;
       offset += 2;
       grey_objects >>= 2;
     }
 
     grey_objects >>= (Bitmap::kBitsPerCell - 1);
   }
 }
 
 
 int MarkCompactCollector::DiscoverAndPromoteBlackObjectsOnPage(
     NewSpace* new_space,
     NewSpacePage* p) {
   ASSERT(strcmp(Marking::kWhiteBitPattern, "00") == 0);
   ASSERT(strcmp(Marking::kBlackBitPattern, "10") == 0);
   ASSERT(strcmp(Marking::kGreyBitPattern, "11") == 0);
   ASSERT(strcmp(Marking::kImpossibleBitPattern, "01") == 0);
 
   MarkBit::CellType* cells = p->markbits()->cells();
   int survivors_size = 0;
 
-  int last_cell_index =
-      Bitmap::IndexToCell(
-          Bitmap::CellAlignIndex(
-              p->AddressToMarkbitIndex(p->area_end())));
+  Address cell_base;
+  MarkBit::CellType* cell;

[Michael Starzinger, 2013/07/15 14:01:46]

nit: Likewise.

[Hannes Payer (out of office), 2013/07/16 12:13:00]

Done.

+  for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
+    cell_base = it.CurrentCellBase();
+    cell = it.CurrentCell();
 
-  Address cell_base = p->area_start();
-  int cell_index = Bitmap::IndexToCell(
-          Bitmap::CellAlignIndex(
-              p->AddressToMarkbitIndex(cell_base)));
-
-  for (;
-       cell_index < last_cell_index;
-       cell_index++, cell_base += 32 * kPointerSize) {
-    ASSERT(static_cast<unsigned>(cell_index) ==
-           Bitmap::IndexToCell(
-               Bitmap::CellAlignIndex(
-                   p->AddressToMarkbitIndex(cell_base))));
-
-    MarkBit::CellType current_cell = cells[cell_index];
+    MarkBit::CellType current_cell = *cell;
     if (current_cell == 0) continue;
 
     int offset = 0;
     while (current_cell != 0) {
       int trailing_zeros = CompilerIntrinsics::CountTrailingZeros(current_cell);
       current_cell >>= trailing_zeros;
       offset += trailing_zeros;
       Address address = cell_base + offset * kPointerSize;
       HeapObject* object = HeapObject::FromAddress(address);
 
@@ skipping 19 matching lines @@
         allocation = new_space->AllocateRaw(size);
         ASSERT(!allocation->IsFailure());
       }
       Object* target = allocation->ToObjectUnchecked();
 
       MigrateObject(HeapObject::cast(target)->address(),
                     object->address(),
                     size,
                     NEW_SPACE);
     }
-    cells[cell_index] = 0;
+    *cells = 0;
   }
   return survivors_size;
 }
 
 
 static void DiscoverGreyObjectsInSpace(Heap* heap,
                                        MarkingDeque* marking_deque,
                                        PagedSpace* space) {
   if (!space->was_swept_conservatively()) {
     HeapObjectIterator it(space);
@@ skipping 906 matching lines @@
 
   heap_->IncrementYoungSurvivorsCounter(survivors_size);
   new_space->set_age_mark(new_space->top());
 }
 
 
 void MarkCompactCollector::EvacuateLiveObjectsFromPage(Page* p) {
   AlwaysAllocateScope always_allocate;
   PagedSpace* space = static_cast<PagedSpace*>(p->owner());
   ASSERT(p->IsEvacuationCandidate() && !p->WasSwept());
-  MarkBit::CellType* cells = p->markbits()->cells();
   p->MarkSweptPrecisely();
 
-  int last_cell_index =
-      Bitmap::IndexToCell(
-          Bitmap::CellAlignIndex(
-              p->AddressToMarkbitIndex(p->area_end())));
-
-  Address cell_base = p->area_start();
-  int cell_index = Bitmap::IndexToCell(
-          Bitmap::CellAlignIndex(
-              p->AddressToMarkbitIndex(cell_base)));
-
   int offsets[16];
 
-  for (;
-       cell_index < last_cell_index;
-       cell_index++, cell_base += 32 * kPointerSize) {
-    ASSERT(static_cast<unsigned>(cell_index) ==
-           Bitmap::IndexToCell(
-               Bitmap::CellAlignIndex(
-                   p->AddressToMarkbitIndex(cell_base))));
-    if (cells[cell_index] == 0) continue;
+  Address cell_base;
+  MarkBit::CellType* cell;

[Michael Starzinger, 2013/07/15 14:01:46]

nit: Likewise.

[Hannes Payer (out of office), 2013/07/16 12:13:00]

Done.

+  for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
+    cell_base = it.CurrentCellBase();
+    cell = it.CurrentCell();
 
-    int live_objects = MarkWordToObjectStarts(cells[cell_index], offsets);
+    if (*cell == 0) continue;
+
+    int live_objects = MarkWordToObjectStarts(*cell, offsets);
     for (int i = 0; i < live_objects; i++) {
       Address object_addr = cell_base + offsets[i] * kPointerSize;
       HeapObject* object = HeapObject::FromAddress(object_addr);
       ASSERT(Marking::IsBlack(Marking::MarkBitFrom(object)));
 
       int size = object->Size();
 
       MaybeObject* target = space->AllocateRaw(size);
       if (target->IsFailure()) {
         // OS refused to give us memory.
         V8::FatalProcessOutOfMemory("Evacuation");
         return;
       }
 
       Object* target_object = target->ToObjectUnchecked();
 
       MigrateObject(HeapObject::cast(target_object)->address(),
                     object_addr,
                     size,
                     space->identity());
       ASSERT(object->map_word().IsForwardingAddress());
     }
 
     // Clear marking bits for current cell.
-    cells[cell_index] = 0;
+    *cell = 0;
   }
   p->ResetLiveBytes();
 }
 
 
 void MarkCompactCollector::EvacuatePages() {
   int npages = evacuation_candidates_.length();
   for (int i = 0; i < npages; i++) {
     Page* p = evacuation_candidates_[i];
     ASSERT(p->IsEvacuationCandidate() ||
@@ skipping 100 matching lines @@
   ASSERT(!p->IsEvacuationCandidate() && !p->WasSwept());
   ASSERT_EQ(skip_list_mode == REBUILD_SKIP_LIST,
             space->identity() == CODE_SPACE);
   ASSERT((p->skip_list() == NULL) || (skip_list_mode == REBUILD_SKIP_LIST));
 
   double start_time = 0.0;
   if (FLAG_print_cumulative_gc_stat) {
     start_time = OS::TimeCurrentMillis();
   }
 
-  MarkBit::CellType* cells = p->markbits()->cells();
   p->MarkSweptPrecisely();
 
-  int last_cell_index =
-      Bitmap::IndexToCell(
-          Bitmap::CellAlignIndex(
-              p->AddressToMarkbitIndex(p->area_end())));
-
   Address free_start = p->area_start();
-  int cell_index =
-      Bitmap::IndexToCell(
-          Bitmap::CellAlignIndex(
-              p->AddressToMarkbitIndex(free_start)));
-
   ASSERT(reinterpret_cast<intptr_t>(free_start) % (32 * kPointerSize) == 0);
-  Address object_address = free_start;
   int offsets[16];
 
   SkipList* skip_list = p->skip_list();
   int curr_region = -1;
   if ((skip_list_mode == REBUILD_SKIP_LIST) && skip_list) {
     skip_list->Clear();
   }
 
-  for (;
-       cell_index < last_cell_index;
-       cell_index++, object_address += 32 * kPointerSize) {
-    ASSERT(static_cast<unsigned>(cell_index) ==
-           Bitmap::IndexToCell(
-               Bitmap::CellAlignIndex(
-                   p->AddressToMarkbitIndex(object_address))));
-    int live_objects = MarkWordToObjectStarts(cells[cell_index], offsets);
+  MarkBit::CellType* cell;
+  Address cell_base;
+  for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
+    cell = it.CurrentCell();
+    cell_base = it.CurrentCellBase();
+    int live_objects = MarkWordToObjectStarts(*cell, offsets);
     int live_index = 0;
     for ( ; live_objects != 0; live_objects--) {
-      Address free_end = object_address + offsets[live_index++] * kPointerSize;
+      Address free_end = cell_base + offsets[live_index++] * kPointerSize;
       if (free_end != free_start) {
         space->Free(free_start, static_cast<int>(free_end - free_start));
 #ifdef ENABLE_GDB_JIT_INTERFACE
         if (FLAG_gdbjit && space->identity() == CODE_SPACE) {
           GDBJITInterface::RemoveCodeRange(free_start, free_end);
         }
 #endif
       }
       HeapObject* live_object = HeapObject::FromAddress(free_end);
       ASSERT(Marking::IsBlack(Marking::MarkBitFrom(live_object)));
       Map* map = live_object->map();
       int size = live_object->SizeFromMap(map);
       if (sweeping_mode == SWEEP_AND_VISIT_LIVE_OBJECTS) {
         live_object->IterateBody(map->instance_type(), size, v);
       }
       if ((skip_list_mode == REBUILD_SKIP_LIST) && skip_list != NULL) {
         int new_region_start =
             SkipList::RegionNumber(free_end);
         int new_region_end =
             SkipList::RegionNumber(free_end + size - kPointerSize);
         if (new_region_start != curr_region ||
             new_region_end != curr_region) {
           skip_list->AddObject(free_end, size);
           curr_region = new_region_end;
         }
       }
       free_start = free_end + size;
     }
     // Clear marking bits for current cell.
-    cells[cell_index] = 0;
+    *cell = 0;
   }
   if (free_start != p->area_end()) {
     space->Free(free_start, static_cast<int>(p->area_end() - free_start));
 #ifdef ENABLE_GDB_JIT_INTERFACE
     if (FLAG_gdbjit && space->identity() == CODE_SPACE) {
       GDBJITInterface::RemoveCodeRange(free_start, p->area_end());
     }
 #endif
   }
   p->ResetLiveBytes();
@@ skipping 646 matching lines @@
 template<MarkCompactCollector::SweepingParallelism mode>
 intptr_t MarkCompactCollector::SweepConservatively(PagedSpace* space,
                                                    FreeList* free_list,
                                                    Page* p) {
   ASSERT(!p->IsEvacuationCandidate() && !p->WasSwept());
   ASSERT((mode == MarkCompactCollector::SWEEP_IN_PARALLEL &&
          free_list != NULL) ||
          (mode == MarkCompactCollector::SWEEP_SEQUENTIALLY &&
          free_list == NULL));
 
-  MarkBit::CellType* cells = p->markbits()->cells();
   p->MarkSweptConservatively();
 
-  int last_cell_index =
-      Bitmap::IndexToCell(
-          Bitmap::CellAlignIndex(
-              p->AddressToMarkbitIndex(p->area_end())));
-
-  int cell_index =
-      Bitmap::IndexToCell(
-          Bitmap::CellAlignIndex(
-              p->AddressToMarkbitIndex(p->area_start())));
-
   intptr_t freed_bytes = 0;
-
-  // This is the start of the 32 word block that we are currently looking at.
-  Address block_address = p->area_start();
+  size_t size = 0;
 
   // Skip over all the dead objects at the start of the page and mark them free.
-  for (;
-       cell_index < last_cell_index;
-       cell_index++, block_address += 32 * kPointerSize) {
-    if (cells[cell_index] != 0) break;
+  Address cell_base = 0;
+  MarkBit::CellType* cell = NULL;
+  MarkBitCellIterator it(p);
+  for (; !it.Done(); it.Advance()) {
+    cell_base = it.CurrentCellBase();
+    cell = it.CurrentCell();
+    if (*cell != 0) break;
   }
-  size_t size = block_address - p->area_start();
-  if (cell_index == last_cell_index) {
+
+  if (it.Done()) {
+    size = p->area_end() - p->area_start();
     freed_bytes += Free<mode>(space, free_list, p->area_start(),
                               static_cast<int>(size));
     ASSERT_EQ(0, p->LiveBytes());
     return freed_bytes;
   }
+
   // Grow the size of the start-of-page free space a little to get up to the
   // first live object.
-  Address free_end = StartOfLiveObject(block_address, cells[cell_index]);
+  Address free_end = StartOfLiveObject(cell_base, *cell);
   // Free the first free space.
   size = free_end - p->area_start();
   freed_bytes += Free<mode>(space, free_list, p->area_start(),
                             static_cast<int>(size));
 
   // The start of the current free area is represented in undigested form by
   // the address of the last 32-word section that contained a live object and
   // the marking bitmap for that cell, which describes where the live object
   // started.  Unless we find a large free space in the bitmap we will not
   // digest this pair into a real address.  We start the iteration here at the
   // first word in the marking bit map that indicates a live object.
-  Address free_start = block_address;
-  uint32_t free_start_cell = cells[cell_index];
+  Address free_start = cell_base;
+  MarkBit::CellType free_start_cell = *cell;
 
-  for ( ;
-       cell_index < last_cell_index;
-       cell_index++, block_address += 32 * kPointerSize) {
-    ASSERT((unsigned)cell_index ==
-        Bitmap::IndexToCell(
-            Bitmap::CellAlignIndex(
-                p->AddressToMarkbitIndex(block_address))));
-    uint32_t cell = cells[cell_index];
-    if (cell != 0) {
+  for (; !it.Done(); it.Advance()) {
+    cell_base = it.CurrentCellBase();
+    cell = it.CurrentCell();
+    if (*cell != 0) {
       // We have a live object.  Check approximately whether it is more than 32
       // words since the last live object.
-      if (block_address - free_start > 32 * kPointerSize) {
+      if (cell_base - free_start > 32 * kPointerSize) {
         free_start = DigestFreeStart(free_start, free_start_cell);
-        if (block_address - free_start > 32 * kPointerSize) {
+        if (cell_base - free_start > 32 * kPointerSize) {
           // Now that we know the exact start of the free space it still looks
           // like we have a large enough free space to be worth bothering with.
           // so now we need to find the start of the first live object at the
           // end of the free space.
-          free_end = StartOfLiveObject(block_address, cell);
+          free_end = StartOfLiveObject(cell_base, *cell);
           freed_bytes += Free<mode>(space, free_list, free_start,
                                     static_cast<int>(free_end - free_start));
         }
       }
       // Update our undigested record of where the current free area started.
-      free_start = block_address;
-      free_start_cell = cell;
+      free_start = cell_base;
+      free_start_cell = *cell;
       // Clear marking bits for current cell.
-      cells[cell_index] = 0;
+      *cell = 0;
     }
   }
 
   // Handle the free space at the end of the page.
-  if (block_address - free_start > 32 * kPointerSize) {
+  if (cell_base - free_start > 32 * kPointerSize) {
     free_start = DigestFreeStart(free_start, free_start_cell);
     freed_bytes += Free<mode>(space, free_list, free_start,
-                              static_cast<int>(block_address - free_start));
+                              static_cast<int>(p->area_end() - free_start));
   }
 
   p->ResetLiveBytes();
   return freed_bytes;
 }
 
 
 void MarkCompactCollector::SweepInParallel(PagedSpace* space,
                                            FreeList* private_free_list,
                                            FreeList* free_list) {
@@ skipping 389 matching lines @@
   while (buffer != NULL) {
     SlotsBuffer* next_buffer = buffer->next();
     DeallocateBuffer(buffer);
     buffer = next_buffer;
   }
   *buffer_address = NULL;
 }
 
 
 } }  // namespace v8::internal