Home | History | Annotate | Download | only in heap 
      1 // Copyright 2015 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 #ifndef V8_HEAP_SLOTS_BUFFER_H_
      6 #define V8_HEAP_SLOTS_BUFFER_H_
      7 
      8 #include "src/objects.h"
      9 
     10 namespace v8 {
     11 namespace internal {
     12 
     13 // Forward declarations.
     14 class SlotsBuffer;
     15 
     16 
     17 // SlotsBufferAllocator manages the allocation and deallocation of slots buffer
     18 // chunks and links them together. Slots buffer chunks are always created by the
     19 // SlotsBufferAllocator.
     20 class SlotsBufferAllocator {
     21  public:
     22   SlotsBuffer* AllocateBuffer(SlotsBuffer* next_buffer);
     23   void DeallocateBuffer(SlotsBuffer* buffer);
     24 
     25   void DeallocateChain(SlotsBuffer** buffer_address);
     26 };
     27 
     28 
     29 // SlotsBuffer records a sequence of slots that has to be updated
     30 // after live objects were relocated from evacuation candidates.
     31 // All slots are either untyped or typed:
     32 //    - Untyped slots are expected to contain a tagged object pointer.
     33 //      They are recorded by an address.
     34 //    - Typed slots are expected to contain an encoded pointer to a heap
     35 //      object where the way of encoding depends on the type of the slot.
     36 //      They are recorded as a pair (SlotType, slot address).
     37 // We assume that zero-page is never mapped this allows us to distinguish
     38 // untyped slots from typed slots during iteration by a simple comparison:
     39 // if element of slots buffer is less than NUMBER_OF_SLOT_TYPES then it
     40 // is the first element of typed slot's pair.
     41 class SlotsBuffer {
     42  public:
     43   typedef Object** ObjectSlot;
     44 
     45   explicit SlotsBuffer(SlotsBuffer* next_buffer)
     46       : idx_(0), chain_length_(1), next_(next_buffer) {
     47     if (next_ != NULL) {
     48       chain_length_ = next_->chain_length_ + 1;
     49     }
     50   }
     51 
     52   ~SlotsBuffer() {}
     53 
     54   void Add(ObjectSlot slot) {
     55     DCHECK(0 <= idx_ && idx_ < kNumberOfElements);
     56 #ifdef DEBUG
     57     if (slot >= reinterpret_cast<ObjectSlot>(NUMBER_OF_SLOT_TYPES)) {
     58       DCHECK_NOT_NULL(*slot);
     59     }
     60 #endif
     61     slots_[idx_++] = slot;
     62   }
     63 
     64   ObjectSlot Get(intptr_t i) {
     65     DCHECK(i >= 0 && i < kNumberOfElements);
     66     return slots_[i];
     67   }
     68 
     69   size_t Size() {
     70     DCHECK(idx_ <= kNumberOfElements);
     71     return idx_;
     72   }
     73 
     74   enum SlotType {
     75     EMBEDDED_OBJECT_SLOT,
     76     OBJECT_SLOT,
     77     RELOCATED_CODE_OBJECT,
     78     CELL_TARGET_SLOT,
     79     CODE_TARGET_SLOT,
     80     CODE_ENTRY_SLOT,
     81     DEBUG_TARGET_SLOT,
     82     NUMBER_OF_SLOT_TYPES
     83   };
     84 
     85   static const char* SlotTypeToString(SlotType type) {
     86     switch (type) {
     87       case EMBEDDED_OBJECT_SLOT:
     88         return "EMBEDDED_OBJECT_SLOT";
     89       case OBJECT_SLOT:
     90         return "OBJECT_SLOT";
     91       case RELOCATED_CODE_OBJECT:
     92         return "RELOCATED_CODE_OBJECT";
     93       case CELL_TARGET_SLOT:
     94         return "CELL_TARGET_SLOT";
     95       case CODE_TARGET_SLOT:
     96         return "CODE_TARGET_SLOT";
     97       case CODE_ENTRY_SLOT:
     98         return "CODE_ENTRY_SLOT";
     99       case DEBUG_TARGET_SLOT:
    100         return "DEBUG_TARGET_SLOT";
    101       case NUMBER_OF_SLOT_TYPES:
    102         return "NUMBER_OF_SLOT_TYPES";
    103     }
    104     return "UNKNOWN SlotType";
    105   }
    106 
    107   SlotsBuffer* next() { return next_; }
    108 
    109   static int SizeOfChain(SlotsBuffer* buffer) {
    110     if (buffer == NULL) return 0;
    111     return static_cast<int>(buffer->idx_ +
    112                             (buffer->chain_length_ - 1) * kNumberOfElements);
    113   }
    114 
    115   inline bool IsFull() { return idx_ == kNumberOfElements; }
    116 
    117   inline bool HasSpaceForTypedSlot() { return idx_ < kNumberOfElements - 1; }
    118 
    119   enum AdditionMode { FAIL_ON_OVERFLOW, IGNORE_OVERFLOW };
    120 
    121   static bool ChainLengthThresholdReached(SlotsBuffer* buffer) {
    122     return buffer != NULL && buffer->chain_length_ >= kChainLengthThreshold;
    123   }
    124 
    125   INLINE(static bool AddTo(SlotsBufferAllocator* allocator,
    126                            SlotsBuffer** buffer_address, ObjectSlot slot,
    127                            AdditionMode mode)) {
    128     SlotsBuffer* buffer = *buffer_address;
    129     if (buffer == NULL || buffer->IsFull()) {
    130       if (mode == FAIL_ON_OVERFLOW && ChainLengthThresholdReached(buffer)) {
    131         allocator->DeallocateChain(buffer_address);
    132         return false;
    133       }
    134       buffer = allocator->AllocateBuffer(buffer);
    135       *buffer_address = buffer;
    136     }
    137     buffer->Add(slot);
    138     return true;
    139   }
    140 
    141   static bool IsTypedSlot(ObjectSlot slot);
    142 
    143   static bool AddTo(SlotsBufferAllocator* allocator,
    144                     SlotsBuffer** buffer_address, SlotType type, Address addr,
    145                     AdditionMode mode);
    146 
    147   // Eliminates all stale entries from the slots buffer, i.e., slots that
    148   // are not part of live objects anymore. This method must be called after
    149   // marking, when the whole transitive closure is known and must be called
    150   // before sweeping when mark bits are still intact.
    151   static void RemoveInvalidSlots(Heap* heap, SlotsBuffer* buffer);
    152 
    153   // Eliminate all slots that are within the given address range.
    154   static void RemoveObjectSlots(Heap* heap, SlotsBuffer* buffer,
    155                                 Address start_slot, Address end_slot);
    156 
    157   // Ensures that there are no invalid slots in the chain of slots buffers.
    158   static void VerifySlots(Heap* heap, SlotsBuffer* buffer);
    159 
    160   static const int kNumberOfElements = 1021;
    161 
    162  private:
    163   static const int kChainLengthThreshold = 15;
    164 
    165   intptr_t idx_;
    166   intptr_t chain_length_;
    167   SlotsBuffer* next_;
    168   ObjectSlot slots_[kNumberOfElements];
    169 };
    170 
    171 
    172 }  // namespace internal
    173 }  // namespace v8
    174 
    175 #endif  // V8_HEAP_SLOTS_BUFFER_H_
    176