src/store-buffer.cc

// Copyright 2011 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
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "v8.h"

#include "store-buffer.h"
#include "store-buffer-inl.h"
#include "v8-counters.h"

namespace v8 {
namespace internal {

StoreBuffer::StoreBuffer(Heap* heap)
    : heap_(heap),
      start_(NULL),
      limit_(NULL),
      old_start_(NULL),
      old_limit_(NULL),
      old_top_(NULL),
      old_reserved_limit_(NULL),
      old_buffer_is_sorted_(false),
      old_buffer_is_filtered_(false),
      during_gc_(false),
      store_buffer_rebuilding_enabled_(false),
      callback_(NULL),
      may_move_store_buffer_entries_(true),
      virtual_memory_(NULL),
      hash_map_1_(NULL),
      hash_map_2_(NULL) {
}


void StoreBuffer::Setup() {
  virtual_memory_ = new VirtualMemory(kStoreBufferSize * 3);
  uintptr_t start_as_int =
      reinterpret_cast<uintptr_t>(virtual_memory_->address());
  start_ =
      reinterpret_cast<Address*>(RoundUp(start_as_int, kStoreBufferSize * 2));
  limit_ = start_ + (kStoreBufferSize / kPointerSize);

  old_virtual_memory_ =
      new VirtualMemory(kOldStoreBufferLength * kPointerSize);
  old_top_ = old_start_ =
      reinterpret_cast<Address*>(old_virtual_memory_->address());
  // Don't know the alignment requirements of the OS, but it is certainly not
  // less than 0xfff.
  ASSERT((reinterpret_cast<uintptr_t>(old_start_) & 0xfff) == 0);
  int initial_length = static_cast<int>(OS::CommitPageSize() / kPointerSize);
  ASSERT(initial_length > 0);
  ASSERT(initial_length <= kOldStoreBufferLength);
  old_limit_ = old_start_ + initial_length;
  old_reserved_limit_ = old_start_ + kOldStoreBufferLength;

  CHECK(old_virtual_memory_->Commit(
            reinterpret_cast<void*>(old_start_),
            (old_limit_ - old_start_) * kPointerSize,
            false));

  ASSERT(reinterpret_cast<Address>(start_) >= virtual_memory_->address());
  ASSERT(reinterpret_cast<Address>(limit_) >= virtual_memory_->address());
  Address* vm_limit = reinterpret_cast<Address*>(
      reinterpret_cast<char*>(virtual_memory_->address()) +
          virtual_memory_->size());
  ASSERT(start_ <= vm_limit);
  ASSERT(limit_ <= vm_limit);
  USE(vm_limit);
  ASSERT((reinterpret_cast<uintptr_t>(limit_) & kStoreBufferOverflowBit) != 0);
  ASSERT((reinterpret_cast<uintptr_t>(limit_ - 1) & kStoreBufferOverflowBit) ==
         0);

  CHECK(virtual_memory_->Commit(reinterpret_cast<Address>(start_),
                                kStoreBufferSize,
                                false));  // Not executable.
  heap_->public_set_store_buffer_top(start_);

  hash_map_1_ = new uintptr_t[kHashMapLength];
  hash_map_2_ = new uintptr_t[kHashMapLength];

  ZapHashTables();
}


void StoreBuffer::TearDown() {
  delete virtual_memory_;
  delete old_virtual_memory_;
  delete[] hash_map_1_;
  delete[] hash_map_2_;
  old_start_ = old_top_ = old_limit_ = old_reserved_limit_ = NULL;
  start_ = limit_ = NULL;
  heap_->public_set_store_buffer_top(start_);
}


void StoreBuffer::StoreBufferOverflow(Isolate* isolate) {
  isolate->heap()->store_buffer()->Compact();
}


#if V8_TARGET_ARCH_X64
static int CompareAddresses(const void* void_a, const void* void_b) {
  intptr_t a =
      reinterpret_cast<intptr_t>(*reinterpret_cast<const Address*>(void_a));
  intptr_t b =
      reinterpret_cast<intptr_t>(*reinterpret_cast<const Address*>(void_b));
  // Unfortunately if int is smaller than intptr_t there is no branch-free
  // way to return a number with the same sign as the difference between the
  // pointers.
  if (a == b) return 0;
  if (a < b) return -1;
  ASSERT(a > b);
  return 1;
}
#else
static int CompareAddresses(const void* void_a, const void* void_b) {
  intptr_t a =
      reinterpret_cast<intptr_t>(*reinterpret_cast<const Address*>(void_a));
  intptr_t b =
      reinterpret_cast<intptr_t>(*reinterpret_cast<const Address*>(void_b));
  ASSERT(sizeof(1) == sizeof(a));
  // Shift down to avoid wraparound.
  return (a >> kPointerSizeLog2) - (b >> kPointerSizeLog2);
}
#endif


void StoreBuffer::Uniq() {
  ASSERT(HashTablesAreZapped());
  // Remove adjacent duplicates and cells that do not point at new space.
  Address previous = NULL;
  Address* write = old_start_;
  ASSERT(may_move_store_buffer_entries_);
  for (Address* read = old_start_; read < old_top_; read++) {
    Address current = *read;
    if (current != previous) {
      if (heap_->InNewSpace(*reinterpret_cast<Object**>(current))) {
        *write++ = current;
      }
    }
    previous = current;
  }
  old_top_ = write;
}


void StoreBuffer::EnsureSpace(intptr_t space_needed) {
  while (old_limit_ - old_top_ < space_needed &&
         old_limit_ < old_reserved_limit_) {
    size_t grow = old_limit_ - old_start_;  // Double size.
    CHECK(old_virtual_memory_->Commit(reinterpret_cast<void*>(old_limit_),
                                      grow * kPointerSize,
                                      false));
    old_limit_ += grow;
  }

  if (old_limit_ - old_top_ >= space_needed) return;

  if (old_buffer_is_filtered_) return;
  ASSERT(may_move_store_buffer_entries_);
  Compact();

  old_buffer_is_filtered_ = true;
  bool page_has_scan_on_scavenge_flag = false;

  PointerChunkIterator it(heap_);
  MemoryChunk* chunk;
  while ((chunk = it.next()) != NULL) {
    if (chunk->scan_on_scavenge()) page_has_scan_on_scavenge_flag = true;
  }

  if (page_has_scan_on_scavenge_flag) {
    Filter(MemoryChunk::SCAN_ON_SCAVENGE);
  }

  // If filtering out the entries from scan_on_scavenge pages got us down to
  // less than half full, then we are satisfied with that.
  if (old_limit_ - old_top_ > old_top_ - old_start_) return;

  // Sample 1 entry in 97 and filter out the pages where we estimate that more
  // than 1 in 8 pointers are to new space.
  static const int kSampleFinenesses = 5;
  static const struct Samples {
    int prime_sample_step;
    int threshold;
  } samples[kSampleFinenesses] =  {
    { 97, ((Page::kPageSize / kPointerSize) / 97) / 8 },
    { 23, ((Page::kPageSize / kPointerSize) / 23) / 16 },
    { 7, ((Page::kPageSize / kPointerSize) / 7) / 32 },
    { 3, ((Page::kPageSize / kPointerSize) / 3) / 256 },
    { 1, 0}
  };
  for (int i = kSampleFinenesses - 1; i >= 0; i--) {
    ExemptPopularPages(samples[i].prime_sample_step, samples[i].threshold);
    // As a last resort we mark all pages as being exempt from the store buffer.
    ASSERT(i != 0 || old_top_ == old_start_);
    if (old_limit_ - old_top_ > old_top_ - old_start_) return;
  }
  UNREACHABLE();
}


// Sample the store buffer to see if some pages are taking up a lot of space
// in the store buffer.
void StoreBuffer::ExemptPopularPages(int prime_sample_step, int threshold) {
  PointerChunkIterator it(heap_);
  MemoryChunk* chunk;
  while ((chunk = it.next()) != NULL) {
    chunk->set_store_buffer_counter(0);
  }
  bool created_new_scan_on_scavenge_pages = false;
  MemoryChunk* previous_chunk = NULL;
  for (Address* p = old_start_; p < old_top_; p += prime_sample_step) {
    Address addr = *p;
    MemoryChunk* containing_chunk = NULL;
    if (previous_chunk != NULL && previous_chunk->Contains(addr)) {
      containing_chunk = previous_chunk;
    } else {
      containing_chunk = MemoryChunk::FromAnyPointerAddress(addr);
    }
    int old_counter = containing_chunk->store_buffer_counter();
    if (old_counter == threshold) {
      containing_chunk->set_scan_on_scavenge(true);
      created_new_scan_on_scavenge_pages = true;
    }
    containing_chunk->set_store_buffer_counter(old_counter + 1);
    previous_chunk = containing_chunk;
  }
  if (created_new_scan_on_scavenge_pages) {
    Filter(MemoryChunk::SCAN_ON_SCAVENGE);
  }
  old_buffer_is_filtered_ = true;
}


void StoreBuffer::Filter(int flag) {
  Address* new_top = old_start_;
  MemoryChunk* previous_chunk = NULL;
  for (Address* p = old_start_; p < old_top_; p++) {
    Address addr = *p;
    MemoryChunk* containing_chunk = NULL;
    if (previous_chunk != NULL && previous_chunk->Contains(addr)) {
      containing_chunk = previous_chunk;
    } else {
      containing_chunk = MemoryChunk::FromAnyPointerAddress(addr);
      previous_chunk = containing_chunk;
    }
    if (!containing_chunk->IsFlagSet(flag)) {
      *new_top++ = addr;
    }
  }
  old_top_ = new_top;
}


void StoreBuffer::SortUniq() {
  Compact();
  if (old_buffer_is_sorted_) return;
  ZapHashTables();
  qsort(reinterpret_cast<void*>(old_start_),
        old_top_ - old_start_,
        sizeof(*old_top_),
        &CompareAddresses);
  Uniq();

  old_buffer_is_sorted_ = true;
}


bool StoreBuffer::PrepareForIteration() {
  Compact();
  PointerChunkIterator it(heap_);
  MemoryChunk* chunk;
  bool page_has_scan_on_scavenge_flag = false;
  while ((chunk = it.next()) != NULL) {
    if (chunk->scan_on_scavenge()) page_has_scan_on_scavenge_flag = true;
  }

  if (page_has_scan_on_scavenge_flag) {
    Filter(MemoryChunk::SCAN_ON_SCAVENGE);
  }
  ZapHashTables();
  return page_has_scan_on_scavenge_flag;
}


#ifdef DEBUG
void StoreBuffer::Clean() {
  ZapHashTables();
  Uniq();  // Also removes things that no longer point to new space.
  CheckForFullBuffer();
}


static bool Zapped(char* start, int size) {
  for (int i = 0; i < size; i++) {
    if (start[i] != 0) return false;
  }
  return true;
}


bool StoreBuffer::HashTablesAreZapped() {
  return Zapped(reinterpret_cast<char*>(hash_map_1_),
                sizeof(uintptr_t) * kHashMapLength) &&
      Zapped(reinterpret_cast<char*>(hash_map_2_),
             sizeof(uintptr_t) * kHashMapLength);
}


static Address* in_store_buffer_1_element_cache = NULL;


bool StoreBuffer::CellIsInStoreBuffer(Address cell_address) {
  if (!FLAG_enable_slow_asserts) return true;
  if (in_store_buffer_1_element_cache != NULL &&
      *in_store_buffer_1_element_cache == cell_address) {
    return true;
  }
  Address* top = reinterpret_cast<Address*>(heap_->store_buffer_top());
  for (Address* current = top - 1; current >= start_; current--) {
    if (*current == cell_address) {
      in_store_buffer_1_element_cache = current;
      return true;
    }
  }
  for (Address* current = old_top_ - 1; current >= old_start_; current--) {
    if (*current == cell_address) {
      in_store_buffer_1_element_cache = current;
      return true;
    }
  }
  return false;
}
#endif


void StoreBuffer::ZapHashTables() {
  memset(reinterpret_cast<void*>(hash_map_1_),
         0,
         sizeof(uintptr_t) * kHashMapLength);
  memset(reinterpret_cast<void*>(hash_map_2_),
         0,
         sizeof(uintptr_t) * kHashMapLength);
}


void StoreBuffer::GCPrologue() {
  ZapHashTables();
  during_gc_ = true;
}


#ifdef DEBUG
static void DummyScavengePointer(HeapObject** p, HeapObject* o) {
  // Do nothing.
}


void StoreBuffer::VerifyPointers(PagedSpace* space,
                                 RegionCallback region_callback) {
  PageIterator it(space);

  while (it.has_next()) {
    Page* page = it.next();
    FindPointersToNewSpaceOnPage(
        reinterpret_cast<PagedSpace*>(page->owner()),
        page,
        region_callback,
        &DummyScavengePointer);
  }
}


void StoreBuffer::VerifyPointers(LargeObjectSpace* space) {
  LargeObjectIterator it(space);
  for (HeapObject* object = it.Next(); object != NULL; object = it.Next()) {
    if (object->IsFixedArray()) {
      Address slot_address = object->address();
      Address end = object->address() + object->Size();

      while (slot_address < end) {
        HeapObject** slot = reinterpret_cast<HeapObject**>(slot_address);
        // When we are not in GC the Heap::InNewSpace() predicate
        // checks that pointers which satisfy predicate point into
        // the active semispace.
        heap_->InNewSpace(*slot);
        slot_address += kPointerSize;
      }
    }
  }
}
#endif


void StoreBuffer::Verify() {
#ifdef DEBUG
  VerifyPointers(heap_->old_pointer_space(),
                 &StoreBuffer::FindPointersToNewSpaceInRegion);
  VerifyPointers(heap_->map_space(),
                 &StoreBuffer::FindPointersToNewSpaceInMapsRegion);
  VerifyPointers(heap_->lo_space());
#endif
}


void StoreBuffer::GCEpilogue() {
  during_gc_ = false;
  if (FLAG_verify_heap) {
    Verify();
  }
}


void StoreBuffer::FindPointersToNewSpaceInRegion(
    Address start, Address end, ObjectSlotCallback slot_callback) {
  for (Address slot_address = start;
       slot_address < end;
       slot_address += kPointerSize) {
    Object** slot = reinterpret_cast<Object**>(slot_address);
    if (heap_->InNewSpace(*slot)) {
      HeapObject* object = reinterpret_cast<HeapObject*>(*slot);
      ASSERT(object->IsHeapObject());
      slot_callback(reinterpret_cast<HeapObject**>(slot), object);
      if (heap_->InNewSpace(*slot)) {
        EnterDirectlyIntoStoreBuffer(slot_address);
      }
    }
  }
}


// Compute start address of the first map following given addr.
static inline Address MapStartAlign(Address addr) {
  Address page = Page::FromAddress(addr)->ObjectAreaStart();
  return page + (((addr - page) + (Map::kSize - 1)) / Map::kSize * Map::kSize);
}


// Compute end address of the first map preceding given addr.
static inline Address MapEndAlign(Address addr) {
  Address page = Page::FromAllocationTop(addr)->ObjectAreaStart();
  return page + ((addr - page) / Map::kSize * Map::kSize);
}


void StoreBuffer::FindPointersToNewSpaceInMaps(
    Address start,
    Address end,
    ObjectSlotCallback slot_callback) {
  ASSERT(MapStartAlign(start) == start);
  ASSERT(MapEndAlign(end) == end);

  Address map_address = start;
  while (map_address < end) {
    ASSERT(!heap_->InNewSpace(Memory::Object_at(map_address)));
    ASSERT(Memory::Object_at(map_address)->IsMap());

    Address pointer_fields_start = map_address + Map::kPointerFieldsBeginOffset;
    Address pointer_fields_end = map_address + Map::kPointerFieldsEndOffset;

    FindPointersToNewSpaceInRegion(pointer_fields_start,
                                   pointer_fields_end,
                                   slot_callback);
    map_address += Map::kSize;
  }
}


void StoreBuffer::FindPointersToNewSpaceInMapsRegion(
    Address start,
    Address end,
    ObjectSlotCallback slot_callback) {
  Address map_aligned_start = MapStartAlign(start);
  Address map_aligned_end   = MapEndAlign(end);

  ASSERT(map_aligned_start == start);
  ASSERT(map_aligned_end == end);

  FindPointersToNewSpaceInMaps(map_aligned_start,
                               map_aligned_end,
                               slot_callback);
}


// This function iterates over all the pointers in a paged space in the heap,
// looking for pointers into new space.  Within the pages there may be dead
// objects that have not been overwritten by free spaces or fillers because of
// lazy sweeping.  These dead objects may not contain pointers to new space.
// The garbage areas that have been swept properly (these will normally be the
// large ones) will be marked with free space and filler map words.  In
// addition any area that has never been used at all for object allocation must
// be marked with a free space or filler.  Because the free space and filler
// maps do not move we can always recognize these even after a compaction.
// Normal objects like FixedArrays and JSObjects should not contain references
// to these maps.  The special garbage section (see comment in spaces.h) is
// skipped since it can contain absolutely anything.  Any objects that are
// allocated during iteration may or may not be visited by the iteration, but
// they will not be partially visited.
void StoreBuffer::FindPointersToNewSpaceOnPage(
    PagedSpace* space,
    Page* page,
    RegionCallback region_callback,
    ObjectSlotCallback slot_callback) {
  Address visitable_start = page->ObjectAreaStart();
  Address end_of_page = page->ObjectAreaEnd();

  Address visitable_end = visitable_start;

  Object* free_space_map = heap_->free_space_map();
  Object* two_pointer_filler_map = heap_->two_pointer_filler_map();

  while (visitable_end < end_of_page) {
    Object* o = *reinterpret_cast<Object**>(visitable_end);
    // Skip fillers but not things that look like fillers in the special
    // garbage section which can contain anything.
    if (o == free_space_map ||
        o == two_pointer_filler_map ||
        (visitable_end == space->top() && visitable_end != space->limit())) {
      if (visitable_start != visitable_end) {
        // After calling this the special garbage section may have moved.
        (this->*region_callback)(visitable_start,
                                 visitable_end,
                                 slot_callback);
        if (visitable_end >= space->top() && visitable_end < space->limit()) {
          visitable_end = space->limit();
          visitable_start = visitable_end;
          continue;
        }
      }
      if (visitable_end == space->top() && visitable_end != space->limit()) {
        visitable_start = visitable_end = space->limit();
      } else {
        // At this point we are either at the start of a filler or we are at
        // the point where the space->top() used to be before the
        // visit_pointer_region call above.  Either way we can skip the
        // object at the current spot:  We don't promise to visit objects
        // allocated during heap traversal, and if space->top() moved then it
        // must be because an object was allocated at this point.
        visitable_start =
            visitable_end + HeapObject::FromAddress(visitable_end)->Size();
        visitable_end = visitable_start;
      }
    } else {
      ASSERT(o != free_space_map);
      ASSERT(o != two_pointer_filler_map);
      ASSERT(visitable_end < space->top() || visitable_end >= space->limit());
      visitable_end += kPointerSize;
    }
  }
  ASSERT(visitable_end == end_of_page);
  if (visitable_start != visitable_end) {
    (this->*region_callback)(visitable_start,
                             visitable_end,
                             slot_callback);
  }
}


void StoreBuffer::IteratePointersInStoreBuffer(
    ObjectSlotCallback slot_callback) {
  Address* limit = old_top_;
  old_top_ = old_start_;
  {
    DontMoveStoreBufferEntriesScope scope(this);
    for (Address* current = old_start_; current < limit; current++) {
#ifdef DEBUG
      Address* saved_top = old_top_;
#endif
      Object** slot = reinterpret_cast<Object**>(*current);
      Object* object = *slot;
      if (heap_->InFromSpace(object)) {
        HeapObject* heap_object = reinterpret_cast<HeapObject*>(object);
        slot_callback(reinterpret_cast<HeapObject**>(slot), heap_object);
        if (heap_->InNewSpace(*slot)) {
          EnterDirectlyIntoStoreBuffer(reinterpret_cast<Address>(slot));
        }
      }
      ASSERT(old_top_ == saved_top + 1 || old_top_ == saved_top);
    }
  }
}


void StoreBuffer::IteratePointersToNewSpace(ObjectSlotCallback slot_callback) {
  // We do not sort or remove duplicated entries from the store buffer because
  // we expect that callback will rebuild the store buffer thus removing
  // all duplicates and pointers to old space.
  bool some_pages_to_scan = PrepareForIteration();

  // TODO(gc): we want to skip slots on evacuation candidates
  // but we can't simply figure that out from slot address
  // because slot can belong to a large object.
  IteratePointersInStoreBuffer(slot_callback);

  // We are done scanning all the pointers that were in the store buffer, but
  // there may be some pages marked scan_on_scavenge that have pointers to new
  // space that are not in the store buffer.  We must scan them now.  As we
  // scan, the surviving pointers to new space will be added to the store
  // buffer.  If there are still a lot of pointers to new space then we will
  // keep the scan_on_scavenge flag on the page and discard the pointers that
  // were added to the store buffer.  If there are not many pointers to new
  // space left on the page we will keep the pointers in the store buffer and
  // remove the flag from the page.
  if (some_pages_to_scan) {
    if (callback_ != NULL) {
      (*callback_)(heap_, NULL, kStoreBufferStartScanningPagesEvent);
    }
    PointerChunkIterator it(heap_);
    MemoryChunk* chunk;
    while ((chunk = it.next()) != NULL) {
      if (chunk->scan_on_scavenge()) {
        chunk->set_scan_on_scavenge(false);
        if (callback_ != NULL) {
          (*callback_)(heap_, chunk, kStoreBufferScanningPageEvent);
        }
        if (chunk->owner() == heap_->lo_space()) {
          LargePage* large_page = reinterpret_cast<LargePage*>(chunk);
          HeapObject* array = large_page->GetObject();
          ASSERT(array->IsFixedArray());
          Address start = array->address();
          Address end = start + array->Size();
          FindPointersToNewSpaceInRegion(start, end, slot_callback);
        } else {
          Page* page = reinterpret_cast<Page*>(chunk);
          PagedSpace* owner = reinterpret_cast<PagedSpace*>(page->owner());
          FindPointersToNewSpaceOnPage(
              owner,
              page,
              (owner == heap_->map_space() ?
                 &StoreBuffer::FindPointersToNewSpaceInMapsRegion :
                 &StoreBuffer::FindPointersToNewSpaceInRegion),
              slot_callback);
        }
      }
    }
    if (callback_ != NULL) {
      (*callback_)(heap_, NULL, kStoreBufferScanningPageEvent);
    }
  }
}


void StoreBuffer::Compact() {
  Address* top = reinterpret_cast<Address*>(heap_->store_buffer_top());

  if (top == start_) return;

  // There's no check of the limit in the loop below so we check here for
  // the worst case (compaction doesn't eliminate any pointers).
  ASSERT(top <= limit_);
  heap_->public_set_store_buffer_top(start_);
  EnsureSpace(top - start_);
  ASSERT(may_move_store_buffer_entries_);
  // Goes through the addresses in the store buffer attempting to remove
  // duplicates.  In the interest of speed this is a lossy operation.  Some
  // duplicates will remain.  We have two hash tables with different hash
  // functions to reduce the number of unnecessary clashes.
  for (Address* current = start_; current < top; current++) {
    ASSERT(!heap_->cell_space()->Contains(*current));
    ASSERT(!heap_->code_space()->Contains(*current));
    ASSERT(!heap_->old_data_space()->Contains(*current));
    uintptr_t int_addr = reinterpret_cast<uintptr_t>(*current);
    // Shift out the last bits including any tags.
    int_addr >>= kPointerSizeLog2;
    int hash1 =
        ((int_addr ^ (int_addr >> kHashMapLengthLog2)) & (kHashMapLength - 1));
    if (hash_map_1_[hash1] == int_addr) continue;
    int hash2 =
        ((int_addr - (int_addr >> kHashMapLengthLog2)) & (kHashMapLength - 1));
    hash2 ^= hash2 >> (kHashMapLengthLog2 * 2);
    if (hash_map_2_[hash2] == int_addr) continue;
    if (hash_map_1_[hash1] == 0) {
      hash_map_1_[hash1] = int_addr;
    } else if (hash_map_2_[hash2] == 0) {
      hash_map_2_[hash2] = int_addr;
    } else {
      // Rather than slowing down we just throw away some entries.  This will
      // cause some duplicates to remain undetected.
      hash_map_1_[hash1] = int_addr;
      hash_map_2_[hash2] = 0;
    }
    old_buffer_is_sorted_ = false;
    old_buffer_is_filtered_ = false;
    *old_top_++ = reinterpret_cast<Address>(int_addr << kPointerSizeLog2);
    ASSERT(old_top_ <= old_limit_);
  }
  heap_->isolate()->counters()->store_buffer_compactions()->Increment();
  CheckForFullBuffer();
}


void StoreBuffer::CheckForFullBuffer() {
  EnsureSpace(kStoreBufferSize * 2);
}

} }  // namespace v8::internal