1 /* 2 * Copyright (c) 2014, 2017, 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, mtNMT); 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, MEMFLAGS flags) { 138 assert(flags != mtNone, "Should have a real memory type"); 139 unsigned int index = hash_to_index(key.hash()); 140 *bucket_idx = (size_t)index; 141 *pos_idx = 0; 142 143 // First entry for this hash bucket 144 if (_table[index] == NULL) { 145 MallocSiteHashtableEntry* entry = new_entry(key, flags); 146 // OOM check 147 if (entry == NULL) return NULL; 148 149 // swap in the head 150 if (Atomic::cmpxchg(entry, &_table[index], (MallocSiteHashtableEntry*)NULL) == NULL) { 151 return entry->data(); 152 } 153 154 delete entry; 155 } 156 157 MallocSiteHashtableEntry* head = _table[index]; 158 while (head != NULL && (*pos_idx) <= MAX_BUCKET_LENGTH) { 159 MallocSite* site = head->data(); 160 if (site->flags() == flags && site->equals(key)) { 161 return head->data(); 162 } 163 164 if (head->next() == NULL && (*pos_idx) < MAX_BUCKET_LENGTH) { 165 MallocSiteHashtableEntry* entry = new_entry(key, flags); 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; 186 index < pos_idx && head != NULL; 187 index++, head = (MallocSiteHashtableEntry*)head->next()) {} 188 assert(head != NULL, "Invalid position index"); 189 return head->data(); 190 } 191 192 // Allocates MallocSiteHashtableEntry object. Special call stack 193 // (pre-installed allocation site) has to be used to avoid infinite 194 // recursion. 195 MallocSiteHashtableEntry* MallocSiteTable::new_entry(const NativeCallStack& key, MEMFLAGS flags) { 196 void* p = AllocateHeap(sizeof(MallocSiteHashtableEntry), mtNMT, 197 *hash_entry_allocation_stack(), AllocFailStrategy::RETURN_NULL); 198 return ::new (p) MallocSiteHashtableEntry(key, flags); 199 } 200 201 void MallocSiteTable::reset() { 202 for (int index = 0; index < table_size; index ++) { 203 MallocSiteHashtableEntry* head = _table[index]; 204 _table[index] = NULL; 205 delete_linked_list(head); 206 } 207 } 208 209 void MallocSiteTable::delete_linked_list(MallocSiteHashtableEntry* head) { 210 MallocSiteHashtableEntry* p; 211 while (head != NULL) { 212 p = head; 213 head = (MallocSiteHashtableEntry*)head->next(); 214 if (p != (MallocSiteHashtableEntry*)_hash_entry_allocation_site) { 215 delete p; 216 } 217 } 218 } 219 220 void MallocSiteTable::shutdown() { 221 AccessLock locker(&_access_count); 222 locker.exclusiveLock(); 223 reset(); 224 } 225 226 bool MallocSiteTable::walk_malloc_site(MallocSiteWalker* walker) { 227 assert(walker != NULL, "NuLL walker"); 228 AccessLock locker(&_access_count); 229 if (locker.sharedLock()) { 230 NOT_PRODUCT(_peak_count = MAX2(_peak_count, _access_count);) 231 return walk(walker); 232 } 233 return false; 234 } 235 236 237 void MallocSiteTable::AccessLock::exclusiveLock() { 238 jint target; 239 jint val; 240 241 assert(_lock_state != ExclusiveLock, "Can only call once"); 242 assert(*_lock >= 0, "Can not content exclusive lock"); 243 244 // make counter negative to block out shared locks 245 do { 246 val = *_lock; 247 target = _MAGIC_ + *_lock; 248 } while (Atomic::cmpxchg(target, _lock, val) != val); 249 250 // wait for all readers to exit 251 while (*_lock != _MAGIC_) { 252 #ifdef _WINDOWS 253 os::naked_short_sleep(1); 254 #else 255 os::naked_yield(); 256 #endif 257 } 258 _lock_state = ExclusiveLock; 259 } 260 261 bool MallocSiteHashtableEntry::atomic_insert(MallocSiteHashtableEntry* entry) { 262 return Atomic::cmpxchg(entry, &_next, (MallocSiteHashtableEntry*)NULL) == NULL; 263 }