Home | History | Annotate | Download | only in accounting 
      1 /*
      2  * Copyright (C) 2012 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #ifndef ART_RUNTIME_GC_ACCOUNTING_MOD_UNION_TABLE_H_
     18 #define ART_RUNTIME_GC_ACCOUNTING_MOD_UNION_TABLE_H_
     19 
     20 #include "gc_allocator.h"
     21 #include "globals.h"
     22 #include "safe_map.h"
     23 
     24 #include <set>
     25 #include <vector>
     26 
     27 namespace art {
     28 namespace mirror {
     29   class Object;
     30 }  // namespace mirror
     31 
     32 namespace gc {
     33 
     34 namespace collector {
     35   class MarkSweep;
     36 }  // namespace collector
     37 namespace space {
     38   class ContinuousSpace;
     39   class Space;
     40 }  // namespace space
     41 
     42 class Heap;
     43 
     44 namespace accounting {
     45 
     46 class SpaceBitmap;
     47 class HeapBitmap;
     48 
     49 // The mod-union table is the union of modified cards. It is used to allow the card table to be
     50 // cleared between GC phases, reducing the number of dirty cards that need to be scanned.
     51 class ModUnionTable {
     52  public:
     53   typedef std::set<byte*, std::less<byte*>, GCAllocator<byte*> > CardSet;
     54 
     55   explicit ModUnionTable(Heap* heap) : heap_(heap) {}
     56 
     57   virtual ~ModUnionTable() {}
     58 
     59   // Clear cards which map to a memory range of a space. This doesn't immediately update the
     60   // mod-union table, as updating the mod-union table may have an associated cost, such as
     61   // determining references to track.
     62   virtual void ClearCards(space::ContinuousSpace* space) = 0;
     63 
     64   // Update the mod-union table using data stored by ClearCards. There may be multiple ClearCards
     65   // before a call to update, for example, back-to-back sticky GCs.
     66   virtual void Update() = 0;
     67 
     68   // Mark the bitmaps for all references which are stored in the mod-union table.
     69   virtual void MarkReferences(collector::MarkSweep* mark_sweep) = 0;
     70 
     71   // Verification, sanity checks that we don't have clean cards which conflict with out cached data
     72   // for said cards. Exclusive lock is required since verify sometimes uses
     73   // SpaceBitmap::VisitMarkedRange and VisitMarkedRange can't know if the callback will modify the
     74   // bitmap or not.
     75   virtual void Verify() EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) = 0;
     76 
     77   virtual void Dump(std::ostream& os) = 0;
     78 
     79   Heap* GetHeap() const {
     80     return heap_;
     81   }
     82 
     83  protected:
     84   Heap* const heap_;
     85 };
     86 
     87 // Reference caching implementation. Caches references pointing to alloc space(s) for each card.
     88 class ModUnionTableReferenceCache : public ModUnionTable {
     89  public:
     90   explicit ModUnionTableReferenceCache(Heap* heap) : ModUnionTable(heap) {}
     91   virtual ~ModUnionTableReferenceCache() {}
     92 
     93   // Clear and store cards for a space.
     94   void ClearCards(space::ContinuousSpace* space);
     95 
     96   // Update table based on cleared cards.
     97   void Update()
     98       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
     99       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    100 
    101   // Mark all references to the alloc space(s).
    102   void MarkReferences(collector::MarkSweep* mark_sweep)
    103       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
    104       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
    105 
    106   // Exclusive lock is required since verify uses SpaceBitmap::VisitMarkedRange and
    107   // VisitMarkedRange can't know if the callback will modify the bitmap or not.
    108   void Verify() EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_);
    109 
    110   // Function that tells whether or not to add a reference to the table.
    111   virtual bool AddReference(const mirror::Object* obj, const mirror::Object* ref) = 0;
    112 
    113   void Dump(std::ostream& os);
    114 
    115  protected:
    116   // Cleared card array, used to update the mod-union table.
    117   ModUnionTable::CardSet cleared_cards_;
    118 
    119   // Maps from dirty cards to their corresponding alloc space references.
    120   SafeMap<const byte*, std::vector<const mirror::Object*>, std::less<const byte*>,
    121     GCAllocator<std::pair<const byte*, std::vector<const mirror::Object*> > > > references_;
    122 };
    123 
    124 // Card caching implementation. Keeps track of which cards we cleared and only this information.
    125 class ModUnionTableCardCache : public ModUnionTable {
    126  public:
    127   explicit ModUnionTableCardCache(Heap* heap) : ModUnionTable(heap) {}
    128   virtual ~ModUnionTableCardCache() {}
    129 
    130   // Clear and store cards for a space.
    131   void ClearCards(space::ContinuousSpace* space);
    132 
    133   // Nothing to update as all dirty cards were placed into cleared cards during clearing.
    134   void Update() {}
    135 
    136   // Mark all references to the alloc space(s).
    137   void MarkReferences(collector::MarkSweep* mark_sweep)
    138       EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_)
    139       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
    140 
    141   // Nothing to verify.
    142   void Verify() {}
    143 
    144   void Dump(std::ostream& os);
    145 
    146  protected:
    147   // Cleared card array, used to update the mod-union table.
    148   CardSet cleared_cards_;
    149 };
    150 
    151 }  // namespace accounting
    152 }  // namespace gc
    153 }  // namespace art
    154 
    155 #endif  // ART_RUNTIME_GC_ACCOUNTING_MOD_UNION_TABLE_H_
    156