1 /*
   2  * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 #include "precompiled.hpp"
  25 
  26 
  27 #include "memory/allocation.inline.hpp"
  28 #include "runtime/atomic.hpp"
  29 #include "services/mallocSiteTable.hpp"
  30 
  31 /*
  32  * Early os::malloc() calls come from initializations of static variables, long before entering any
  33  * VM code. Upon the arrival of the first os::malloc() call, malloc site hashtable has to be
  34  * initialized, along with the allocation site for the hashtable entries.
  35  * To ensure that malloc site hashtable can be initialized without triggering any additional os::malloc()
  36  * call, the hashtable bucket array and hashtable entry allocation site have to be static.
  37  * It is not a problem for hashtable bucket, since it is an array of pointer type, C runtime just
  38  * allocates a block memory and zero the memory for it.
  39  * But for hashtable entry allocation site object, things get tricky. C runtime not only allocates
  40  * memory for it, but also calls its constructor at some later time. If we initialize the allocation site
  41  * at the first os::malloc() call, the object will be reinitialized when its constructor is called
  42  * by C runtime.
  43  * To workaround above issue, we declare a static size_t array with the size of the CallsiteHashtableEntry,
  44  * the memory is used to instantiate CallsiteHashtableEntry for the hashtable entry allocation site.
  45  * Given it is a primitive type array, C runtime will do nothing other than assign the memory block for the variable,
  46  * which is exactly what we want.
  47  * The same trick is also applied to create NativeCallStack object for CallsiteHashtableEntry memory allocation.
  48  *
  49  * Note: C++ object usually aligns to particular alignment, depends on compiler implementation, we declare
  50  * the memory as size_t arrays, to ensure the memory is aligned to native machine word alignment.
  51  */
  52 
  53 // Reserve enough memory for NativeCallStack and MallocSiteHashtableEntry objects
  54 size_t MallocSiteTable::_hash_entry_allocation_stack[CALC_OBJ_SIZE_IN_TYPE(NativeCallStack, size_t)];
  55 size_t MallocSiteTable::_hash_entry_allocation_site[CALC_OBJ_SIZE_IN_TYPE(MallocSiteHashtableEntry, size_t)];
  56 
  57 // Malloc site hashtable buckets
  58 MallocSiteHashtableEntry*  MallocSiteTable::_table[MallocSiteTable::table_size];
  59 
  60 // concurrent access counter
  61 volatile int MallocSiteTable::_access_count = 0;
  62 
  63 // Tracking hashtable contention
  64 NOT_PRODUCT(int MallocSiteTable::_peak_count = 0;)
  65 
  66 
  67 /*
  68  * Initialize malloc site table.
  69  * Hashtable entry is malloc'd, so it can cause infinite recursion.
  70  * To avoid above problem, we pre-initialize a hash entry for
  71  * this allocation site.
  72  * The method is called during C runtime static variable initialization
  73  * time, it is in single-threaded mode from JVM perspective.
  74  */
  75 bool MallocSiteTable::initialize() {
  76   assert(sizeof(_hash_entry_allocation_stack) >= sizeof(NativeCallStack), "Sanity Check");
  77   assert(sizeof(_hash_entry_allocation_site) >= sizeof(MallocSiteHashtableEntry),
  78     "Sanity Check");
  79   assert((size_t)table_size <= MAX_MALLOCSITE_TABLE_SIZE, "Hashtable overflow");
  80 
  81   // Fake the call stack for hashtable entry allocation
  82   assert(NMT_TrackingStackDepth > 1, "At least one tracking stack");
  83 
  84   // Create pseudo call stack for hashtable entry allocation
  85   address pc[3];
  86   if (NMT_TrackingStackDepth >= 3) {
  87     pc[2] = (address)MallocSiteTable::allocation_at;
  88   }
  89   if (NMT_TrackingStackDepth >= 2) {
  90     pc[1] = (address)MallocSiteTable::lookup_or_add;
  91   }
  92   pc[0] = (address)MallocSiteTable::new_entry;
  93 
  94   // Instantiate NativeCallStack object, have to use placement new operator. (see comments above)
  95   NativeCallStack* stack = ::new ((void*)_hash_entry_allocation_stack)
  96     NativeCallStack(pc, MIN2(((int)(sizeof(pc) / sizeof(address))), ((int)NMT_TrackingStackDepth)));
  97 
  98   // Instantiate hash entry for hashtable entry allocation callsite
  99   MallocSiteHashtableEntry* entry = ::new ((void*)_hash_entry_allocation_site)
 100     MallocSiteHashtableEntry(*stack);
 101 
 102   // Add the allocation site to hashtable.
 103   int index = hash_to_index(stack->hash());
 104   _table[index] = entry;
 105 
 106   return true;
 107 }
 108 
 109 // Walks entries in the hashtable.
 110 // It stops walk if the walker returns false.
 111 bool MallocSiteTable::walk(MallocSiteWalker* walker) {
 112   MallocSiteHashtableEntry* head;
 113   for (int index = 0; index < table_size; index ++) {
 114     head = _table[index];
 115     while (head != NULL) {
 116       if (!walker->do_malloc_site(head->peek())) {
 117         return false;
 118       }
 119       head = (MallocSiteHashtableEntry*)head->next();
 120     }
 121   }
 122   return true;
 123 }
 124 
 125 /*
 126  *  The hashtable does not have deletion policy on individual entry,
 127  *  and each linked list node is inserted via compare-and-swap,
 128  *  so each linked list is stable, the contention only happens
 129  *  at the end of linked list.
 130  *  This method should not return NULL under normal circumstance.
 131  *  If NULL is returned, it indicates:
 132  *    1. Out of memory, it cannot allocate new hash entry.
 133  *    2. Overflow hash bucket.
 134  *  Under any of above circumstances, caller should handle the situation.
 135  */
 136 MallocSite* MallocSiteTable::lookup_or_add(const NativeCallStack& key, size_t* bucket_idx,
 137   size_t* pos_idx) {
 138   unsigned int index = hash_to_index(key.hash());
 139   *bucket_idx = (size_t)index;
 140   *pos_idx = 0;
 141 
 142   // First entry for this hash bucket
 143   if (_table[index] == NULL) {
 144     MallocSiteHashtableEntry* entry = new_entry(key);
 145     // OOM check
 146     if (entry == NULL) return NULL;
 147 
 148     // swap in the head
 149     if (Atomic::cmpxchg_ptr((void*)entry, (volatile void *)&_table[index], NULL) == NULL) {
 150       return entry->data();
 151     }
 152 
 153     delete entry;
 154   }
 155 
 156   MallocSiteHashtableEntry* head = _table[index];
 157   while (head != NULL && (*pos_idx) <= MAX_BUCKET_LENGTH) {
 158     MallocSite* site = head->data();
 159     if (site->equals(key)) {
 160       // found matched entry
 161       return head->data();
 162     }
 163 
 164     if (head->next() == NULL && (*pos_idx) < MAX_BUCKET_LENGTH) {
 165       MallocSiteHashtableEntry* entry = new_entry(key);
 166       // OOM check
 167       if (entry == NULL) return NULL;
 168       if (head->atomic_insert(entry)) {
 169         (*pos_idx) ++;
 170         return entry->data();
 171       }
 172       // contended, other thread won
 173       delete entry;
 174     }
 175     head = (MallocSiteHashtableEntry*)head->next();
 176     (*pos_idx) ++;
 177   }
 178   return NULL;
 179 }
 180 
 181 // Access malloc site
 182 MallocSite* MallocSiteTable::malloc_site(size_t bucket_idx, size_t pos_idx) {
 183   assert(bucket_idx < table_size, "Invalid bucket index");
 184   MallocSiteHashtableEntry* head = _table[bucket_idx];
 185   for (size_t index = 0; index < pos_idx && head != NULL;
 186     index ++, head = (MallocSiteHashtableEntry*)head->next());
 187   assert(head != NULL, "Invalid position index");
 188   return head->data();
 189 }
 190 
 191 // Allocates MallocSiteHashtableEntry object. Special call stack
 192 // (pre-installed allocation site) has to be used to avoid infinite
 193 // recursion.
 194 MallocSiteHashtableEntry* MallocSiteTable::new_entry(const NativeCallStack& key) {
 195   void* p = AllocateHeap(sizeof(MallocSiteHashtableEntry), mtNMT,
 196     *hash_entry_allocation_stack(), AllocFailStrategy::RETURN_NULL);
 197   return ::new (p) MallocSiteHashtableEntry(key);
 198 }
 199 
 200 void MallocSiteTable::reset() {
 201   for (int index = 0; index < table_size; index ++) {
 202     MallocSiteHashtableEntry* head = _table[index];
 203     _table[index] = NULL;
 204     delete_linked_list(head);
 205   }
 206 }
 207 
 208 void MallocSiteTable::delete_linked_list(MallocSiteHashtableEntry* head) {
 209   MallocSiteHashtableEntry* p;
 210   while (head != NULL) {
 211     p = head;
 212     head = (MallocSiteHashtableEntry*)head->next();
 213     if (p != (MallocSiteHashtableEntry*)_hash_entry_allocation_site) {
 214       delete p;
 215     }
 216   }
 217 }
 218 
 219 void MallocSiteTable::shutdown() {
 220   AccessLock locker(&_access_count);
 221   locker.exclusiveLock();
 222   reset();
 223 }
 224 
 225 bool MallocSiteTable::walk_malloc_site(MallocSiteWalker* walker) {
 226   assert(walker != NULL, "NuLL walker");
 227   AccessLock locker(&_access_count);
 228   if (locker.sharedLock()) {
 229     NOT_PRODUCT(_peak_count = MAX2(_peak_count, _access_count);)
 230     return walk(walker);
 231   }
 232   return false;
 233 }
 234 
 235 
 236 void MallocSiteTable::AccessLock::exclusiveLock() {
 237   jint target;
 238   jint val;
 239 
 240   assert(_lock_state != ExclusiveLock, "Can only call once");
 241   assert(*_lock >= 0, "Can not content exclusive lock");
 242 
 243   // make counter negative to block out shared locks
 244   do {
 245     val = *_lock;
 246     target = _MAGIC_ + *_lock;
 247   } while (Atomic::cmpxchg(target, _lock, val) != val);
 248 
 249   // wait for all readers to exit
 250   while (*_lock != _MAGIC_) {
 251 #ifdef _WINDOWS
 252     os::naked_short_sleep(1);
 253 #else
 254     os::naked_yield();
 255 #endif
 256   }
 257   _lock_state = ExclusiveLock;
 258 }
 259 
 260