Home | History | Annotate | Download | only in runtime
      1 /*
      2  * Copyright (C) 2014 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_MONITOR_POOL_H_
     18 #define ART_RUNTIME_MONITOR_POOL_H_
     19 
     20 #include "monitor.h"
     21 
     22 #include "base/allocator.h"
     23 #ifdef __LP64__
     24 #include <stdint.h>
     25 #include "atomic.h"
     26 #include "runtime.h"
     27 #else
     28 #include "base/stl_util.h"     // STLDeleteElements
     29 #endif
     30 
     31 namespace art {
     32 
     33 // Abstraction to keep monitors small enough to fit in a lock word (32bits). On 32bit systems the
     34 // monitor id loses the alignment bits of the Monitor*.
     35 class MonitorPool {
     36  public:
     37   static MonitorPool* Create() {
     38 #ifndef __LP64__
     39     return nullptr;
     40 #else
     41     return new MonitorPool();
     42 #endif
     43   }
     44 
     45   static Monitor* CreateMonitor(Thread* self, Thread* owner, mirror::Object* obj, int32_t hash_code)
     46       SHARED_REQUIRES(Locks::mutator_lock_) {
     47 #ifndef __LP64__
     48     Monitor* mon = new Monitor(self, owner, obj, hash_code);
     49     DCHECK_ALIGNED(mon, LockWord::kMonitorIdAlignment);
     50     return mon;
     51 #else
     52     return GetMonitorPool()->CreateMonitorInPool(self, owner, obj, hash_code);
     53 #endif
     54   }
     55 
     56   static void ReleaseMonitor(Thread* self, Monitor* monitor) {
     57 #ifndef __LP64__
     58     UNUSED(self);
     59     delete monitor;
     60 #else
     61     GetMonitorPool()->ReleaseMonitorToPool(self, monitor);
     62 #endif
     63   }
     64 
     65   static void ReleaseMonitors(Thread* self, MonitorList::Monitors* monitors) {
     66 #ifndef __LP64__
     67     UNUSED(self);
     68     STLDeleteElements(monitors);
     69 #else
     70     GetMonitorPool()->ReleaseMonitorsToPool(self, monitors);
     71 #endif
     72   }
     73 
     74   static Monitor* MonitorFromMonitorId(MonitorId mon_id) {
     75 #ifndef __LP64__
     76     return reinterpret_cast<Monitor*>(mon_id << LockWord::kMonitorIdAlignmentShift);
     77 #else
     78     return GetMonitorPool()->LookupMonitor(mon_id);
     79 #endif
     80   }
     81 
     82   static MonitorId MonitorIdFromMonitor(Monitor* mon) {
     83 #ifndef __LP64__
     84     return reinterpret_cast<MonitorId>(mon) >> LockWord::kMonitorIdAlignmentShift;
     85 #else
     86     return mon->GetMonitorId();
     87 #endif
     88   }
     89 
     90   static MonitorId ComputeMonitorId(Monitor* mon, Thread* self) {
     91 #ifndef __LP64__
     92     UNUSED(self);
     93     return MonitorIdFromMonitor(mon);
     94 #else
     95     return GetMonitorPool()->ComputeMonitorIdInPool(mon, self);
     96 #endif
     97   }
     98 
     99   static MonitorPool* GetMonitorPool() {
    100 #ifndef __LP64__
    101     return nullptr;
    102 #else
    103     return Runtime::Current()->GetMonitorPool();
    104 #endif
    105   }
    106 
    107   ~MonitorPool() {
    108 #ifdef __LP64__
    109     FreeInternal();
    110 #endif
    111   }
    112 
    113  private:
    114 #ifdef __LP64__
    115   // When we create a monitor pool, threads have not been initialized, yet, so ignore thread-safety
    116   // analysis.
    117   MonitorPool() NO_THREAD_SAFETY_ANALYSIS;
    118 
    119   void AllocateChunk() REQUIRES(Locks::allocated_monitor_ids_lock_);
    120 
    121   // Release all chunks and metadata. This is done on shutdown, where threads have been destroyed,
    122   // so ignore thead-safety analysis.
    123   void FreeInternal() NO_THREAD_SAFETY_ANALYSIS;
    124 
    125   Monitor* CreateMonitorInPool(Thread* self, Thread* owner, mirror::Object* obj, int32_t hash_code)
    126       SHARED_REQUIRES(Locks::mutator_lock_);
    127 
    128   void ReleaseMonitorToPool(Thread* self, Monitor* monitor);
    129   void ReleaseMonitorsToPool(Thread* self, MonitorList::Monitors* monitors);
    130 
    131   // Note: This is safe as we do not ever move chunks.  All needed entries in the monitor_chunks_
    132   // data structure are read-only once we get here.  Updates happen-before this call because
    133   // the lock word was stored with release semantics and we read it with acquire semantics to
    134   // retrieve the id.
    135   Monitor* LookupMonitor(MonitorId mon_id) {
    136     size_t offset = MonitorIdToOffset(mon_id);
    137     size_t index = offset / kChunkSize;
    138     size_t top_index = index / kMaxListSize;
    139     size_t list_index = index % kMaxListSize;
    140     size_t offset_in_chunk = offset % kChunkSize;
    141     uintptr_t base = monitor_chunks_[top_index][list_index];
    142     return reinterpret_cast<Monitor*>(base + offset_in_chunk);
    143   }
    144 
    145   static bool IsInChunk(uintptr_t base_addr, Monitor* mon) {
    146     uintptr_t mon_ptr = reinterpret_cast<uintptr_t>(mon);
    147     return base_addr <= mon_ptr && (mon_ptr - base_addr < kChunkSize);
    148   }
    149 
    150   MonitorId ComputeMonitorIdInPool(Monitor* mon, Thread* self) {
    151     MutexLock mu(self, *Locks::allocated_monitor_ids_lock_);
    152     for (size_t i = 0; i <= current_chunk_list_index_; ++i) {
    153       for (size_t j = 0; j < ChunkListCapacity(i); ++j) {
    154         if (j >= num_chunks_ && i == current_chunk_list_index_) {
    155           break;
    156         }
    157         uintptr_t chunk_addr = monitor_chunks_[i][j];
    158         if (IsInChunk(chunk_addr, mon)) {
    159           return OffsetToMonitorId(
    160               reinterpret_cast<uintptr_t>(mon) - chunk_addr
    161               + i * (kMaxListSize * kChunkSize) + j * kChunkSize);
    162         }
    163       }
    164     }
    165     LOG(FATAL) << "Did not find chunk that contains monitor.";
    166     return 0;
    167   }
    168 
    169   static constexpr size_t MonitorIdToOffset(MonitorId id) {
    170     return id << 3;
    171   }
    172 
    173   static constexpr MonitorId OffsetToMonitorId(size_t offset) {
    174     return static_cast<MonitorId>(offset >> 3);
    175   }
    176 
    177   static constexpr size_t ChunkListCapacity(size_t index) {
    178     return kInitialChunkStorage << index;
    179   }
    180 
    181   // TODO: There are assumptions in the code that monitor addresses are 8B aligned (>>3).
    182   static constexpr size_t kMonitorAlignment = 8;
    183   // Size of a monitor, rounded up to a multiple of alignment.
    184   static constexpr size_t kAlignedMonitorSize = (sizeof(Monitor) + kMonitorAlignment - 1) &
    185                                                 -kMonitorAlignment;
    186   // As close to a page as we can get seems a good start.
    187   static constexpr size_t kChunkCapacity = kPageSize / kAlignedMonitorSize;
    188   // Chunk size that is referenced in the id. We can collapse this to the actually used storage
    189   // in a chunk, i.e., kChunkCapacity * kAlignedMonitorSize, but this will mean proper divisions.
    190   static constexpr size_t kChunkSize = kPageSize;
    191   static_assert(IsPowerOfTwo(kChunkSize), "kChunkSize must be power of 2");
    192   // The number of chunks of storage that can be referenced by the initial chunk list.
    193   // The total number of usable monitor chunks is typically 255 times this number, so it
    194   // should be large enough that we don't run out. We run out of address bits if it's > 512.
    195   // Currently we set it a bit smaller, to save half a page per process.  We make it tiny in
    196   // debug builds to catch growth errors. The only value we really expect to tune.
    197   static constexpr size_t kInitialChunkStorage = kIsDebugBuild ? 1U : 256U;
    198   static_assert(IsPowerOfTwo(kInitialChunkStorage), "kInitialChunkStorage must be power of 2");
    199   // The number of lists, each containing pointers to storage chunks.
    200   static constexpr size_t kMaxChunkLists = 8;  //  Dictated by 3 bit index. Don't increase above 8.
    201   static_assert(IsPowerOfTwo(kMaxChunkLists), "kMaxChunkLists must be power of 2");
    202   static constexpr size_t kMaxListSize = kInitialChunkStorage << (kMaxChunkLists - 1);
    203   // We lose 3 bits in monitor id due to 3 bit monitor_chunks_ index, and gain it back from
    204   // the 3 bit alignment constraint on monitors:
    205   static_assert(kMaxListSize * kChunkSize < (1 << LockWord::kMonitorIdSize),
    206       "Monitor id bits don't fit");
    207   static_assert(IsPowerOfTwo(kMaxListSize), "kMaxListSize must be power of 2");
    208 
    209   // Array of pointers to lists (again arrays) of pointers to chunks containing monitors.
    210   // Zeroth entry points to a list (array) of kInitialChunkStorage pointers to chunks.
    211   // Each subsequent list as twice as large as the preceding one.
    212   // Monitor Ids are interpreted as follows:
    213   //     Top 3 bits (of 28): index into monitor_chunks_.
    214   //     Next 16 bits: index into the chunk list, i.e. monitor_chunks_[i].
    215   //     Last 9 bits: offset within chunk, expressed as multiple of kMonitorAlignment.
    216   // If we set kInitialChunkStorage to 512, this would allow us to use roughly 128K chunks of
    217   // monitors, which is 0.5GB of monitors.  With this maximum setting, the largest chunk list
    218   // contains 64K entries, and we make full use of the available index space. With a
    219   // kInitialChunkStorage value of 256, this is proportionately reduced to 0.25GB of monitors.
    220   // Updates to monitor_chunks_ are guarded by allocated_monitor_ids_lock_ .
    221   // No field in this entire data structure is ever updated once a monitor id whose lookup
    222   // requires it has been made visible to another thread.  Thus readers never race with
    223   // updates, in spite of the fact that they acquire no locks.
    224   uintptr_t* monitor_chunks_[kMaxChunkLists];  //  uintptr_t is really a Monitor* .
    225   // Highest currently used index in monitor_chunks_ . Used for newly allocated chunks.
    226   size_t current_chunk_list_index_ GUARDED_BY(Locks::allocated_monitor_ids_lock_);
    227   // Number of chunk pointers stored in monitor_chunks_[current_chunk_list_index_] so far.
    228   size_t num_chunks_ GUARDED_BY(Locks::allocated_monitor_ids_lock_);
    229   // After the initial allocation, this is always equal to
    230   // ChunkListCapacity(current_chunk_list_index_).
    231   size_t current_chunk_list_capacity_ GUARDED_BY(Locks::allocated_monitor_ids_lock_);
    232 
    233   typedef TrackingAllocator<uint8_t, kAllocatorTagMonitorPool> Allocator;
    234   Allocator allocator_;
    235 
    236   // Start of free list of monitors.
    237   // Note: these point to the right memory regions, but do *not* denote initialized objects.
    238   Monitor* first_free_ GUARDED_BY(Locks::allocated_monitor_ids_lock_);
    239 #endif
    240 };
    241 
    242 }  // namespace art
    243 
    244 #endif  // ART_RUNTIME_MONITOR_POOL_H_
    245