Fri, 10 Oct 2014 15:51:58 +0200
8059758: Footprint regressions with JDK-8038423
Summary: Changes in JDK-8038423 always initialize (zero out) virtual memory used for auxiliary data structures. This causes a footprint regression for G1 in startup benchmarks. This is because they do not touch that memory at all, so the operating system does not actually commit these pages. The fix is to, if the initialization value of the data structures matches the default value of just committed memory (=0), do not do anything.
Reviewed-by: jwilhelm, brutisso
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 */
25 #include "precompiled.hpp"
26 #include "classfile/altHashing.hpp"
27 #include "classfile/javaClasses.hpp"
28 #include "gc_implementation/g1/g1CollectedHeap.inline.hpp"
29 #include "gc_implementation/g1/g1SATBCardTableModRefBS.hpp"
30 #include "gc_implementation/g1/g1StringDedupTable.hpp"
31 #include "memory/gcLocker.hpp"
32 #include "memory/padded.inline.hpp"
33 #include "oops/typeArrayOop.hpp"
34 #include "runtime/mutexLocker.hpp"
36 //
37 // Freelist in the deduplication table entry cache. Links table
38 // entries together using their _next fields.
39 //
40 class G1StringDedupEntryFreeList : public CHeapObj<mtGC> {
41 private:
42 G1StringDedupEntry* _list;
43 size_t _length;
45 public:
46 G1StringDedupEntryFreeList() :
47 _list(NULL),
48 _length(0) {
49 }
51 void add(G1StringDedupEntry* entry) {
52 entry->set_next(_list);
53 _list = entry;
54 _length++;
55 }
57 G1StringDedupEntry* remove() {
58 G1StringDedupEntry* entry = _list;
59 if (entry != NULL) {
60 _list = entry->next();
61 _length--;
62 }
63 return entry;
64 }
66 size_t length() {
67 return _length;
68 }
69 };
71 //
72 // Cache of deduplication table entries. This cache provides fast allocation and
73 // reuse of table entries to lower the pressure on the underlying allocator.
74 // But more importantly, it provides fast/deferred freeing of table entries. This
75 // is important because freeing of table entries is done during stop-the-world
76 // phases and it is not uncommon for large number of entries to be freed at once.
77 // Tables entries that are freed during these phases are placed onto a freelist in
78 // the cache. The deduplication thread, which executes in a concurrent phase, will
79 // later reuse or free the underlying memory for these entries.
80 //
81 // The cache allows for single-threaded allocations and multi-threaded frees.
82 // Allocations are synchronized by StringDedupTable_lock as part of a table
83 // modification.
84 //
85 class G1StringDedupEntryCache : public CHeapObj<mtGC> {
86 private:
87 // One freelist per GC worker to allow lock less freeing of
88 // entries while doing a parallel scan of the table. Using
89 // PaddedEnd to avoid false sharing.
90 PaddedEnd<G1StringDedupEntryFreeList>* _lists;
91 size_t _nlists;
93 public:
94 G1StringDedupEntryCache();
95 ~G1StringDedupEntryCache();
97 // Get a table entry from the cache freelist, or allocate a new
98 // entry if the cache is empty.
99 G1StringDedupEntry* alloc();
101 // Insert a table entry into the cache freelist.
102 void free(G1StringDedupEntry* entry, uint worker_id);
104 // Returns current number of entries in the cache.
105 size_t size();
107 // If the cache has grown above the given max size, trim it down
108 // and deallocate the memory occupied by trimmed of entries.
109 void trim(size_t max_size);
110 };
112 G1StringDedupEntryCache::G1StringDedupEntryCache() {
113 _nlists = MAX2(ParallelGCThreads, (size_t)1);
114 _lists = PaddedArray<G1StringDedupEntryFreeList, mtGC>::create_unfreeable((uint)_nlists);
115 }
117 G1StringDedupEntryCache::~G1StringDedupEntryCache() {
118 ShouldNotReachHere();
119 }
121 G1StringDedupEntry* G1StringDedupEntryCache::alloc() {
122 for (size_t i = 0; i < _nlists; i++) {
123 G1StringDedupEntry* entry = _lists[i].remove();
124 if (entry != NULL) {
125 return entry;
126 }
127 }
128 return new G1StringDedupEntry();
129 }
131 void G1StringDedupEntryCache::free(G1StringDedupEntry* entry, uint worker_id) {
132 assert(entry->obj() != NULL, "Double free");
133 assert(worker_id < _nlists, "Invalid worker id");
134 entry->set_obj(NULL);
135 entry->set_hash(0);
136 _lists[worker_id].add(entry);
137 }
139 size_t G1StringDedupEntryCache::size() {
140 size_t size = 0;
141 for (size_t i = 0; i < _nlists; i++) {
142 size += _lists[i].length();
143 }
144 return size;
145 }
147 void G1StringDedupEntryCache::trim(size_t max_size) {
148 size_t cache_size = 0;
149 for (size_t i = 0; i < _nlists; i++) {
150 G1StringDedupEntryFreeList* list = &_lists[i];
151 cache_size += list->length();
152 while (cache_size > max_size) {
153 G1StringDedupEntry* entry = list->remove();
154 assert(entry != NULL, "Should not be null");
155 cache_size--;
156 delete entry;
157 }
158 }
159 }
161 G1StringDedupTable* G1StringDedupTable::_table = NULL;
162 G1StringDedupEntryCache* G1StringDedupTable::_entry_cache = NULL;
164 const size_t G1StringDedupTable::_min_size = (1 << 10); // 1024
165 const size_t G1StringDedupTable::_max_size = (1 << 24); // 16777216
166 const double G1StringDedupTable::_grow_load_factor = 2.0; // Grow table at 200% load
167 const double G1StringDedupTable::_shrink_load_factor = _grow_load_factor / 3.0; // Shrink table at 67% load
168 const double G1StringDedupTable::_max_cache_factor = 0.1; // Cache a maximum of 10% of the table size
169 const uintx G1StringDedupTable::_rehash_multiple = 60; // Hash bucket has 60 times more collisions than expected
170 const uintx G1StringDedupTable::_rehash_threshold = (uintx)(_rehash_multiple * _grow_load_factor);
172 uintx G1StringDedupTable::_entries_added = 0;
173 uintx G1StringDedupTable::_entries_removed = 0;
174 uintx G1StringDedupTable::_resize_count = 0;
175 uintx G1StringDedupTable::_rehash_count = 0;
177 G1StringDedupTable::G1StringDedupTable(size_t size, jint hash_seed) :
178 _size(size),
179 _entries(0),
180 _grow_threshold((uintx)(size * _grow_load_factor)),
181 _shrink_threshold((uintx)(size * _shrink_load_factor)),
182 _rehash_needed(false),
183 _hash_seed(hash_seed) {
184 assert(is_power_of_2(size), "Table size must be a power of 2");
185 _buckets = NEW_C_HEAP_ARRAY(G1StringDedupEntry*, _size, mtGC);
186 memset(_buckets, 0, _size * sizeof(G1StringDedupEntry*));
187 }
189 G1StringDedupTable::~G1StringDedupTable() {
190 FREE_C_HEAP_ARRAY(G1StringDedupEntry*, _buckets, mtGC);
191 }
193 void G1StringDedupTable::create() {
194 assert(_table == NULL, "One string deduplication table allowed");
195 _entry_cache = new G1StringDedupEntryCache();
196 _table = new G1StringDedupTable(_min_size);
197 }
199 void G1StringDedupTable::add(typeArrayOop value, unsigned int hash, G1StringDedupEntry** list) {
200 G1StringDedupEntry* entry = _entry_cache->alloc();
201 entry->set_obj(value);
202 entry->set_hash(hash);
203 entry->set_next(*list);
204 *list = entry;
205 _entries++;
206 }
208 void G1StringDedupTable::remove(G1StringDedupEntry** pentry, uint worker_id) {
209 G1StringDedupEntry* entry = *pentry;
210 *pentry = entry->next();
211 _entry_cache->free(entry, worker_id);
212 }
214 void G1StringDedupTable::transfer(G1StringDedupEntry** pentry, G1StringDedupTable* dest) {
215 G1StringDedupEntry* entry = *pentry;
216 *pentry = entry->next();
217 unsigned int hash = entry->hash();
218 size_t index = dest->hash_to_index(hash);
219 G1StringDedupEntry** list = dest->bucket(index);
220 entry->set_next(*list);
221 *list = entry;
222 }
224 bool G1StringDedupTable::equals(typeArrayOop value1, typeArrayOop value2) {
225 return (value1 == value2 ||
226 (value1->length() == value2->length() &&
227 (!memcmp(value1->base(T_CHAR),
228 value2->base(T_CHAR),
229 value1->length() * sizeof(jchar)))));
230 }
232 typeArrayOop G1StringDedupTable::lookup(typeArrayOop value, unsigned int hash,
233 G1StringDedupEntry** list, uintx &count) {
234 for (G1StringDedupEntry* entry = *list; entry != NULL; entry = entry->next()) {
235 if (entry->hash() == hash) {
236 typeArrayOop existing_value = entry->obj();
237 if (equals(value, existing_value)) {
238 // Match found
239 return existing_value;
240 }
241 }
242 count++;
243 }
245 // Not found
246 return NULL;
247 }
249 typeArrayOop G1StringDedupTable::lookup_or_add_inner(typeArrayOop value, unsigned int hash) {
250 size_t index = hash_to_index(hash);
251 G1StringDedupEntry** list = bucket(index);
252 uintx count = 0;
254 // Lookup in list
255 typeArrayOop existing_value = lookup(value, hash, list, count);
257 // Check if rehash is needed
258 if (count > _rehash_threshold) {
259 _rehash_needed = true;
260 }
262 if (existing_value == NULL) {
263 // Not found, add new entry
264 add(value, hash, list);
266 // Update statistics
267 _entries_added++;
268 }
270 return existing_value;
271 }
273 unsigned int G1StringDedupTable::hash_code(typeArrayOop value) {
274 unsigned int hash;
275 int length = value->length();
276 const jchar* data = (jchar*)value->base(T_CHAR);
278 if (use_java_hash()) {
279 hash = java_lang_String::hash_code(data, length);
280 } else {
281 hash = AltHashing::murmur3_32(_table->_hash_seed, data, length);
282 }
284 return hash;
285 }
287 void G1StringDedupTable::deduplicate(oop java_string, G1StringDedupStat& stat) {
288 assert(java_lang_String::is_instance(java_string), "Must be a string");
289 No_Safepoint_Verifier nsv;
291 stat.inc_inspected();
293 typeArrayOop value = java_lang_String::value(java_string);
294 if (value == NULL) {
295 // String has no value
296 stat.inc_skipped();
297 return;
298 }
300 unsigned int hash = 0;
302 if (use_java_hash()) {
303 // Get hash code from cache
304 hash = java_lang_String::hash(java_string);
305 }
307 if (hash == 0) {
308 // Compute hash
309 hash = hash_code(value);
310 stat.inc_hashed();
311 }
313 if (use_java_hash() && hash != 0) {
314 // Store hash code in cache
315 java_lang_String::set_hash(java_string, hash);
316 }
318 typeArrayOop existing_value = lookup_or_add(value, hash);
319 if (existing_value == value) {
320 // Same value, already known
321 stat.inc_known();
322 return;
323 }
325 // Get size of value array
326 uintx size_in_bytes = value->size() * HeapWordSize;
327 stat.inc_new(size_in_bytes);
329 if (existing_value != NULL) {
330 // Enqueue the reference to make sure it is kept alive. Concurrent mark might
331 // otherwise declare it dead if there are no other strong references to this object.
332 G1SATBCardTableModRefBS::enqueue(existing_value);
334 // Existing value found, deduplicate string
335 java_lang_String::set_value(java_string, existing_value);
337 if (G1CollectedHeap::heap()->is_in_young(value)) {
338 stat.inc_deduped_young(size_in_bytes);
339 } else {
340 stat.inc_deduped_old(size_in_bytes);
341 }
342 }
343 }
345 G1StringDedupTable* G1StringDedupTable::prepare_resize() {
346 size_t size = _table->_size;
348 // Check if the hashtable needs to be resized
349 if (_table->_entries > _table->_grow_threshold) {
350 // Grow table, double the size
351 size *= 2;
352 if (size > _max_size) {
353 // Too big, don't resize
354 return NULL;
355 }
356 } else if (_table->_entries < _table->_shrink_threshold) {
357 // Shrink table, half the size
358 size /= 2;
359 if (size < _min_size) {
360 // Too small, don't resize
361 return NULL;
362 }
363 } else if (StringDeduplicationResizeALot) {
364 // Force grow
365 size *= 2;
366 if (size > _max_size) {
367 // Too big, force shrink instead
368 size /= 4;
369 }
370 } else {
371 // Resize not needed
372 return NULL;
373 }
375 // Update statistics
376 _resize_count++;
378 // Allocate the new table. The new table will be populated by workers
379 // calling unlink_or_oops_do() and finally installed by finish_resize().
380 return new G1StringDedupTable(size, _table->_hash_seed);
381 }
383 void G1StringDedupTable::finish_resize(G1StringDedupTable* resized_table) {
384 assert(resized_table != NULL, "Invalid table");
386 resized_table->_entries = _table->_entries;
388 // Free old table
389 delete _table;
391 // Install new table
392 _table = resized_table;
393 }
395 void G1StringDedupTable::unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl, uint worker_id) {
396 // The table is divided into partitions to allow lock-less parallel processing by
397 // multiple worker threads. A worker thread first claims a partition, which ensures
398 // exclusive access to that part of the table, then continues to process it. To allow
399 // shrinking of the table in parallel we also need to make sure that the same worker
400 // thread processes all partitions where entries will hash to the same destination
401 // partition. Since the table size is always a power of two and we always shrink by
402 // dividing the table in half, we know that for a given partition there is only one
403 // other partition whoes entries will hash to the same destination partition. That
404 // other partition is always the sibling partition in the second half of the table.
405 // For example, if the table is divided into 8 partitions, the sibling of partition 0
406 // is partition 4, the sibling of partition 1 is partition 5, etc.
407 size_t table_half = _table->_size / 2;
409 // Let each partition be one page worth of buckets
410 size_t partition_size = MIN2(table_half, os::vm_page_size() / sizeof(G1StringDedupEntry*));
411 assert(table_half % partition_size == 0, "Invalid partition size");
413 // Number of entries removed during the scan
414 uintx removed = 0;
416 for (;;) {
417 // Grab next partition to scan
418 size_t partition_begin = cl->claim_table_partition(partition_size);
419 size_t partition_end = partition_begin + partition_size;
420 if (partition_begin >= table_half) {
421 // End of table
422 break;
423 }
425 // Scan the partition followed by the sibling partition in the second half of the table
426 removed += unlink_or_oops_do(cl, partition_begin, partition_end, worker_id);
427 removed += unlink_or_oops_do(cl, table_half + partition_begin, table_half + partition_end, worker_id);
428 }
430 // Delayed update avoid contention on the table lock
431 if (removed > 0) {
432 MutexLockerEx ml(StringDedupTable_lock, Mutex::_no_safepoint_check_flag);
433 _table->_entries -= removed;
434 _entries_removed += removed;
435 }
436 }
438 uintx G1StringDedupTable::unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl,
439 size_t partition_begin,
440 size_t partition_end,
441 uint worker_id) {
442 uintx removed = 0;
443 for (size_t bucket = partition_begin; bucket < partition_end; bucket++) {
444 G1StringDedupEntry** entry = _table->bucket(bucket);
445 while (*entry != NULL) {
446 oop* p = (oop*)(*entry)->obj_addr();
447 if (cl->is_alive(*p)) {
448 cl->keep_alive(p);
449 if (cl->is_resizing()) {
450 // We are resizing the table, transfer entry to the new table
451 _table->transfer(entry, cl->resized_table());
452 } else {
453 if (cl->is_rehashing()) {
454 // We are rehashing the table, rehash the entry but keep it
455 // in the table. We can't transfer entries into the new table
456 // at this point since we don't have exclusive access to all
457 // destination partitions. finish_rehash() will do a single
458 // threaded transfer of all entries.
459 typeArrayOop value = (typeArrayOop)*p;
460 unsigned int hash = hash_code(value);
461 (*entry)->set_hash(hash);
462 }
464 // Move to next entry
465 entry = (*entry)->next_addr();
466 }
467 } else {
468 // Not alive, remove entry from table
469 _table->remove(entry, worker_id);
470 removed++;
471 }
472 }
473 }
475 return removed;
476 }
478 G1StringDedupTable* G1StringDedupTable::prepare_rehash() {
479 if (!_table->_rehash_needed && !StringDeduplicationRehashALot) {
480 // Rehash not needed
481 return NULL;
482 }
484 // Update statistics
485 _rehash_count++;
487 // Compute new hash seed
488 _table->_hash_seed = AltHashing::compute_seed();
490 // Allocate the new table, same size and hash seed
491 return new G1StringDedupTable(_table->_size, _table->_hash_seed);
492 }
494 void G1StringDedupTable::finish_rehash(G1StringDedupTable* rehashed_table) {
495 assert(rehashed_table != NULL, "Invalid table");
497 // Move all newly rehashed entries into the correct buckets in the new table
498 for (size_t bucket = 0; bucket < _table->_size; bucket++) {
499 G1StringDedupEntry** entry = _table->bucket(bucket);
500 while (*entry != NULL) {
501 _table->transfer(entry, rehashed_table);
502 }
503 }
505 rehashed_table->_entries = _table->_entries;
507 // Free old table
508 delete _table;
510 // Install new table
511 _table = rehashed_table;
512 }
514 void G1StringDedupTable::verify() {
515 for (size_t bucket = 0; bucket < _table->_size; bucket++) {
516 // Verify entries
517 G1StringDedupEntry** entry = _table->bucket(bucket);
518 while (*entry != NULL) {
519 typeArrayOop value = (*entry)->obj();
520 guarantee(value != NULL, "Object must not be NULL");
521 guarantee(Universe::heap()->is_in_reserved(value), "Object must be on the heap");
522 guarantee(!value->is_forwarded(), "Object must not be forwarded");
523 guarantee(value->is_typeArray(), "Object must be a typeArrayOop");
524 unsigned int hash = hash_code(value);
525 guarantee((*entry)->hash() == hash, "Table entry has inorrect hash");
526 guarantee(_table->hash_to_index(hash) == bucket, "Table entry has incorrect index");
527 entry = (*entry)->next_addr();
528 }
530 // Verify that we do not have entries with identical oops or identical arrays.
531 // We only need to compare entries in the same bucket. If the same oop or an
532 // identical array has been inserted more than once into different/incorrect
533 // buckets the verification step above will catch that.
534 G1StringDedupEntry** entry1 = _table->bucket(bucket);
535 while (*entry1 != NULL) {
536 typeArrayOop value1 = (*entry1)->obj();
537 G1StringDedupEntry** entry2 = (*entry1)->next_addr();
538 while (*entry2 != NULL) {
539 typeArrayOop value2 = (*entry2)->obj();
540 guarantee(!equals(value1, value2), "Table entries must not have identical arrays");
541 entry2 = (*entry2)->next_addr();
542 }
543 entry1 = (*entry1)->next_addr();
544 }
545 }
546 }
548 void G1StringDedupTable::trim_entry_cache() {
549 MutexLockerEx ml(StringDedupTable_lock, Mutex::_no_safepoint_check_flag);
550 size_t max_cache_size = (size_t)(_table->_size * _max_cache_factor);
551 _entry_cache->trim(max_cache_size);
552 }
554 void G1StringDedupTable::print_statistics(outputStream* st) {
555 st->print_cr(
556 " [Table]\n"
557 " [Memory Usage: "G1_STRDEDUP_BYTES_FORMAT_NS"]\n"
558 " [Size: "SIZE_FORMAT", Min: "SIZE_FORMAT", Max: "SIZE_FORMAT"]\n"
559 " [Entries: "UINTX_FORMAT", Load: "G1_STRDEDUP_PERCENT_FORMAT_NS", Cached: " UINTX_FORMAT ", Added: "UINTX_FORMAT", Removed: "UINTX_FORMAT"]\n"
560 " [Resize Count: "UINTX_FORMAT", Shrink Threshold: "UINTX_FORMAT"("G1_STRDEDUP_PERCENT_FORMAT_NS"), Grow Threshold: "UINTX_FORMAT"("G1_STRDEDUP_PERCENT_FORMAT_NS")]\n"
561 " [Rehash Count: "UINTX_FORMAT", Rehash Threshold: "UINTX_FORMAT", Hash Seed: 0x%x]\n"
562 " [Age Threshold: "UINTX_FORMAT"]",
563 G1_STRDEDUP_BYTES_PARAM(_table->_size * sizeof(G1StringDedupEntry*) + (_table->_entries + _entry_cache->size()) * sizeof(G1StringDedupEntry)),
564 _table->_size, _min_size, _max_size,
565 _table->_entries, (double)_table->_entries / (double)_table->_size * 100.0, _entry_cache->size(), _entries_added, _entries_removed,
566 _resize_count, _table->_shrink_threshold, _shrink_load_factor * 100.0, _table->_grow_threshold, _grow_load_factor * 100.0,
567 _rehash_count, _rehash_threshold, _table->_hash_seed,
568 StringDeduplicationAgeThreshold);
569 }