1 /*
2 * Copyright (c) 2014, 2019, 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 *
198 }
199 }
200
201 double end = os::elapsedTime();
202 log_trace(gc, stringdedup)("Deleted " UINTX_FORMAT " entries, " STRDEDUP_TIME_FORMAT_MS,
203 count, STRDEDUP_TIME_PARAM_MS(end - start));
204 }
205
206 StringDedupTable* StringDedupTable::_table = NULL;
207 StringDedupEntryCache* StringDedupTable::_entry_cache = NULL;
208
209 const size_t StringDedupTable::_min_size = (1 << 10); // 1024
210 const size_t StringDedupTable::_max_size = (1 << 24); // 16777216
211 const double StringDedupTable::_grow_load_factor = 2.0; // Grow table at 200% load
212 const double StringDedupTable::_shrink_load_factor = _grow_load_factor / 3.0; // Shrink table at 67% load
213 const double StringDedupTable::_max_cache_factor = 0.1; // Cache a maximum of 10% of the table size
214 const uintx StringDedupTable::_rehash_multiple = 60; // Hash bucket has 60 times more collisions than expected
215 const uintx StringDedupTable::_rehash_threshold = (uintx)(_rehash_multiple * _grow_load_factor);
216
217 uintx StringDedupTable::_entries_added = 0;
218 uintx StringDedupTable::_entries_removed = 0;
219 uintx StringDedupTable::_resize_count = 0;
220 uintx StringDedupTable::_rehash_count = 0;
221
222 StringDedupTable* StringDedupTable::_resized_table = NULL;
223 StringDedupTable* StringDedupTable::_rehashed_table = NULL;
224 volatile size_t StringDedupTable::_claimed_index = 0;
225
226 StringDedupTable::StringDedupTable(size_t size, jint hash_seed) :
227 _size(size),
228 _entries(0),
229 _shrink_threshold((uintx)(size * _shrink_load_factor)),
230 _grow_threshold((uintx)(size * _grow_load_factor)),
231 _rehash_needed(false),
232 _hash_seed(hash_seed) {
233 assert(is_power_of_2(size), "Table size must be a power of 2");
234 _buckets = NEW_C_HEAP_ARRAY(StringDedupEntry*, _size, mtGC);
235 memset(_buckets, 0, _size * sizeof(StringDedupEntry*));
236 }
237
238 StringDedupTable::~StringDedupTable() {
462
463 // Number of entries removed during the scan
464 uintx removed = 0;
465
466 for (;;) {
467 // Grab next partition to scan
468 size_t partition_begin = claim_table_partition(partition_size);
469 size_t partition_end = partition_begin + partition_size;
470 if (partition_begin >= table_half) {
471 // End of table
472 break;
473 }
474
475 // Scan the partition followed by the sibling partition in the second half of the table
476 removed += unlink_or_oops_do(cl, partition_begin, partition_end, worker_id);
477 removed += unlink_or_oops_do(cl, table_half + partition_begin, table_half + partition_end, worker_id);
478 }
479
480 // Delayed update to avoid contention on the table lock
481 if (removed > 0) {
482 MutexLocker ml(StringDedupTable_lock, Mutex::_no_safepoint_check_flag);
483 _table->_entries -= removed;
484 _entries_removed += removed;
485 }
486 }
487
488 uintx StringDedupTable::unlink_or_oops_do(StringDedupUnlinkOrOopsDoClosure* cl,
489 size_t partition_begin,
490 size_t partition_end,
491 uint worker_id) {
492 uintx removed = 0;
493 for (size_t bucket = partition_begin; bucket < partition_end; bucket++) {
494 StringDedupEntry** entry = _table->bucket(bucket);
495 while (*entry != NULL) {
496 oop* p = (oop*)(*entry)->obj_addr();
497 if (cl->is_alive(*p)) {
498 cl->keep_alive(p);
499 if (is_resizing()) {
500 // We are resizing the table, transfer entry to the new table
501 _table->transfer(entry, _resized_table);
502 } else {
503 if (is_rehashing()) {
504 // We are rehashing the table, rehash the entry but keep it
|
1 /*
2 * Copyright (c) 2014, 2020, 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 *
198 }
199 }
200
201 double end = os::elapsedTime();
202 log_trace(gc, stringdedup)("Deleted " UINTX_FORMAT " entries, " STRDEDUP_TIME_FORMAT_MS,
203 count, STRDEDUP_TIME_PARAM_MS(end - start));
204 }
205
206 StringDedupTable* StringDedupTable::_table = NULL;
207 StringDedupEntryCache* StringDedupTable::_entry_cache = NULL;
208
209 const size_t StringDedupTable::_min_size = (1 << 10); // 1024
210 const size_t StringDedupTable::_max_size = (1 << 24); // 16777216
211 const double StringDedupTable::_grow_load_factor = 2.0; // Grow table at 200% load
212 const double StringDedupTable::_shrink_load_factor = _grow_load_factor / 3.0; // Shrink table at 67% load
213 const double StringDedupTable::_max_cache_factor = 0.1; // Cache a maximum of 10% of the table size
214 const uintx StringDedupTable::_rehash_multiple = 60; // Hash bucket has 60 times more collisions than expected
215 const uintx StringDedupTable::_rehash_threshold = (uintx)(_rehash_multiple * _grow_load_factor);
216
217 uintx StringDedupTable::_entries_added = 0;
218 volatile uintx StringDedupTable::_entries_removed = 0;
219 uintx StringDedupTable::_resize_count = 0;
220 uintx StringDedupTable::_rehash_count = 0;
221
222 StringDedupTable* StringDedupTable::_resized_table = NULL;
223 StringDedupTable* StringDedupTable::_rehashed_table = NULL;
224 volatile size_t StringDedupTable::_claimed_index = 0;
225
226 StringDedupTable::StringDedupTable(size_t size, jint hash_seed) :
227 _size(size),
228 _entries(0),
229 _shrink_threshold((uintx)(size * _shrink_load_factor)),
230 _grow_threshold((uintx)(size * _grow_load_factor)),
231 _rehash_needed(false),
232 _hash_seed(hash_seed) {
233 assert(is_power_of_2(size), "Table size must be a power of 2");
234 _buckets = NEW_C_HEAP_ARRAY(StringDedupEntry*, _size, mtGC);
235 memset(_buckets, 0, _size * sizeof(StringDedupEntry*));
236 }
237
238 StringDedupTable::~StringDedupTable() {
462
463 // Number of entries removed during the scan
464 uintx removed = 0;
465
466 for (;;) {
467 // Grab next partition to scan
468 size_t partition_begin = claim_table_partition(partition_size);
469 size_t partition_end = partition_begin + partition_size;
470 if (partition_begin >= table_half) {
471 // End of table
472 break;
473 }
474
475 // Scan the partition followed by the sibling partition in the second half of the table
476 removed += unlink_or_oops_do(cl, partition_begin, partition_end, worker_id);
477 removed += unlink_or_oops_do(cl, table_half + partition_begin, table_half + partition_end, worker_id);
478 }
479
480 // Delayed update to avoid contention on the table lock
481 if (removed > 0) {
482 assert_locked_or_safepoint_weak(StringDedupTable_lock);
483 Atomic::sub(&_table->_entries, removed);
484 Atomic::add(&_entries_removed, removed);
485 }
486 }
487
488 uintx StringDedupTable::unlink_or_oops_do(StringDedupUnlinkOrOopsDoClosure* cl,
489 size_t partition_begin,
490 size_t partition_end,
491 uint worker_id) {
492 uintx removed = 0;
493 for (size_t bucket = partition_begin; bucket < partition_end; bucket++) {
494 StringDedupEntry** entry = _table->bucket(bucket);
495 while (*entry != NULL) {
496 oop* p = (oop*)(*entry)->obj_addr();
497 if (cl->is_alive(*p)) {
498 cl->keep_alive(p);
499 if (is_resizing()) {
500 // We are resizing the table, transfer entry to the new table
501 _table->transfer(entry, _resized_table);
502 } else {
503 if (is_rehashing()) {
504 // We are rehashing the table, rehash the entry but keep it
|