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
25 #include "logging/log.hpp"
26 #include "runtime/interfaceSupport.inline.hpp"
27 #include "runtime/javaThread.hpp"
28 #include "runtime/mutexLocker.hpp"
29 #include "runtime/objectMonitorTable.hpp"
30 #include "runtime/safepoint.hpp"
31 #include "runtime/thread.hpp"
32 #include "runtime/timerTrace.hpp"
33 #include "runtime/trimNativeHeap.hpp"
34 #include "utilities/debug.hpp"
35 #include "utilities/globalDefinitions.hpp"
36
37 // -----------------------------------------------------------------------------
38 // Theory of operations -- Object Monitor Table:
39 //
40 // The OMT (Object Monitor Table) is a concurrent hash table specifically
41 // designed so that it (in the normal case) can be searched from C2 generated
42 // code.
43 //
44 // In its simplest form it consists of:
45 // 1. An array of pointers.
46 // 2. The size (capacity) of the array, which is always a power of two.
47 //
48 // When you want to find a monitor associated with an object, you extract the
49 // hash value of the object. Then calculate an index by taking the hash value
50 // and bit-wise AND it with the capacity mask (i.e., size-1) of the OMT. Now
101 // until all the monitor pointers from old OMTs have been transferred to the
102 // newest "current" OMT.
103 //
104 // The memory for old, unlinked OMTs will be freed after a thread-local
105 // handshake with all Java threads.
106 //
107 // Searching the OMT for a monitor pointer while there are several generations
108 // of the OMT, will start from the oldest OMT.
109 //
110 // A note about the GROW_LOAD_FACTOR: In order to guarantee that the add and
111 // search algorithms can't loop forever, we must make sure that there is at
112 // least one null pointer in the array to stop them from dead looping.
113 // Furthermore, when we grow the OMT, we must make sure that the new "current"
114 // can accommodate all the monitors from all older OMTs, while still being so
115 // sparsely populated that the C2 generated code will likely find what it's
116 // searching for at the hash index, without needing further linear searching.
117 // The grow load factor is set to 12.5%, which satisfies the above
118 // requirements. Don't change it for fun, it might backfire.
119 // -----------------------------------------------------------------------------
120
121 Atomic<ObjectMonitorTable::Table*> ObjectMonitorTable::_curr;
122
123 class ObjectMonitorTable::Table : public CHeapObj<mtObjectMonitor> {
124 friend class ObjectMonitorTable;
125
126 DEFINE_PAD_MINUS_SIZE(0, DEFAULT_CACHE_LINE_SIZE, 0);
127 const size_t _capacity_mask; // One less than its power-of-two capacity
128 Atomic<Table*> _prev; // Set while growing/rebuilding
129 Atomic<Entry>* _buckets; // The payload
130 DEFINE_PAD_MINUS_SIZE(1, DEFAULT_CACHE_LINE_SIZE, sizeof(_capacity_mask) + sizeof(_prev) + sizeof(_buckets));
131 Atomic<size_t> _items_count;
132 DEFINE_PAD_MINUS_SIZE(2, DEFAULT_CACHE_LINE_SIZE, sizeof(_items_count));
133
134 static Entry as_entry(ObjectMonitor* monitor) {
135 Entry entry = static_cast<Entry>((uintptr_t)monitor);
136 assert(entry >= Entry::below_is_special, "Must be! (entry: " PTR_FORMAT ")", intptr_t(entry));
137 return entry;
138 }
139
140 static ObjectMonitor* as_monitor(Entry entry) {
385 bool result = bucket.compare_set(entry, removed(), memory_order_relaxed);
386 assert(result, "should not fail");
387 break;
388 }
389
390 index = (index + 1) & _capacity_mask;
391 assert(index != start_index, "invariant");
392 }
393
394 // Old versions are removed after newer versions to ensure that observing
395 // the monitor removed and then doing a subsequent lookup results in there
396 // still not being a monitor, instead of flickering back to being there.
397 // Only the deflation thread rebuilds and unlinks tables, so we do not need
398 // any concurrency safe prev read below.
399 if (_prev.load_relaxed() != nullptr) {
400 _prev.load_relaxed()->remove(obj, old_monitor, hash);
401 }
402 }
403
404 void reinsert(oop obj, Entry new_monitor) {
405 intptr_t hash = obj->mark().hash();
406
407 const size_t start_index = size_t(hash) & _capacity_mask;
408 size_t index = start_index;
409
410 for (;;) {
411 Atomic<Entry>& bucket = _buckets[index];
412 Entry entry = bucket.load_acquire();
413
414 if (entry == empty()) {
415 // Empty slot to install the new monitor.
416 Entry result = bucket.compare_exchange(entry, new_monitor, memory_order_acq_rel);
417 if (result == entry) {
418 // Success - unconditionally increment.
419 inc_items_count();
420 return;
421 }
422
423 // Another monitor was installed.
424 entry = result;
425 }
501 // In the current implementation the deflation thread drives
502 // the rebuilding, and it will already have removed any entry
503 // it has deflated. The assert is only here to make sure.
504 assert(!monitor->is_being_async_deflated(), "Should be");
505 // Re-insert still live monitor.
506 reinsert(obj, entry);
507 }
508 }
509 }
510
511 // Unlink this table, releasing the tombstones and relocations.
512 _prev.release_store(nullptr);
513 }
514 };
515
516 void ObjectMonitorTable::create() {
517 _curr.store_relaxed(new Table(128, nullptr));
518 }
519
520 ObjectMonitor* ObjectMonitorTable::monitor_get(oop obj) {
521 const intptr_t hash = obj->mark().hash();
522 Table* curr = _curr.load_acquire();
523 ObjectMonitor* monitor = curr->get(obj, hash);
524 return monitor;
525 }
526
527 // Returns a new table to try inserting into.
528 ObjectMonitorTable::Table* ObjectMonitorTable::grow_table(Table* curr) {
529 Table* result;
530 Table* new_table = _curr.load_acquire();
531 if (new_table != curr) {
532 // Table changed; no need to try further
533 return new_table;
534 }
535
536 {
537 // Use MonitorDeflation_lock to only allow one inflating thread to
538 // attempt to allocate the new table.
539 MonitorLocker ml(MonitorDeflation_lock, Mutex::_no_safepoint_check_flag);
540
541 new_table = _curr.load_acquire();
548 result = _curr.compare_exchange(curr, new_table, memory_order_acq_rel);
549 if (result == curr) {
550 log_info(monitorinflation)("Growing object monitor table (capacity: %zu)",
551 new_table->capacity());
552 // Since we grew the table (we have a new current) we need to
553 // notify the deflation thread to rebuild the table (to get rid of
554 // old currents).
555 ObjectSynchronizer::set_is_async_deflation_requested(true);
556 ml.notify_all();
557 return new_table;
558 }
559 }
560
561 // Somebody else started rebuilding; restart in their new table.
562 delete new_table;
563
564 return result;
565 }
566
567 ObjectMonitor* ObjectMonitorTable::monitor_put_get(ObjectMonitor* monitor, oop obj) {
568 const intptr_t hash = obj->mark().hash();
569 Table* curr = _curr.load_acquire();
570
571 for (;;) {
572 // Curr is the latest table and is reasonably loaded.
573 ObjectMonitor* result = curr->get_set(obj, curr->as_entry(monitor), hash);
574 if (result != nullptr) {
575 return result;
576 }
577 // The table's limit was reached, we need to grow it.
578 curr = grow_table(curr);
579 }
580 }
581
582 void ObjectMonitorTable::remove_monitor_entry(ObjectMonitor* monitor) {
583 oop obj = monitor->object_peek();
584 if (obj == nullptr) {
585 // Defer removal until subsequent rebuilding.
586 return;
587 }
588 const intptr_t hash = obj->mark().hash();
589 Table* curr = _curr.load_acquire();
590 curr->remove(obj, curr->as_entry(monitor), hash);
591 assert(monitor_get(obj) != monitor, "should have been removed");
592 }
593
594 // Before handshake; rebuild and unlink tables.
595 void ObjectMonitorTable::rebuild(GrowableArray<Table*>* delete_list) {
596 Table* new_table;
597 {
598 // Concurrent inserts while in the middle of rebuilding can result
599 // in the population count increasing past the load factor limit.
600 // For this to be okay we need to bound how much it may exceed the
601 // limit. A sequence of tables with doubling capacity may
602 // eventually, after rebuilding, reach the maximum population of
603 // max_population(table_1) + max_population(table_1*2) + ... +
604 // max_population(table_1*2^n).
605 // I.e. max_population(2*table_1 *2^n) - max_population(table_1).
606 // With a 12.5% load factor, the implication is that as long as
607 // rebuilding a table will double its capacity, the maximum load
608 // after rebuilding is less than 25%. However, we can't always
|
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
25 #include "logging/log.hpp"
26 #include "runtime/interfaceSupport.inline.hpp"
27 #include "runtime/javaThread.hpp"
28 #include "runtime/mutexLocker.hpp"
29 #include "runtime/objectMonitor.inline.hpp"
30 #include "runtime/objectMonitorTable.hpp"
31 #include "runtime/safepoint.hpp"
32 #include "runtime/synchronizer.hpp"
33 #include "runtime/thread.hpp"
34 #include "runtime/timerTrace.hpp"
35 #include "runtime/trimNativeHeap.hpp"
36 #include "utilities/debug.hpp"
37 #include "utilities/globalDefinitions.hpp"
38
39 // -----------------------------------------------------------------------------
40 // Theory of operations -- Object Monitor Table:
41 //
42 // The OMT (Object Monitor Table) is a concurrent hash table specifically
43 // designed so that it (in the normal case) can be searched from C2 generated
44 // code.
45 //
46 // In its simplest form it consists of:
47 // 1. An array of pointers.
48 // 2. The size (capacity) of the array, which is always a power of two.
49 //
50 // When you want to find a monitor associated with an object, you extract the
51 // hash value of the object. Then calculate an index by taking the hash value
52 // and bit-wise AND it with the capacity mask (i.e., size-1) of the OMT. Now
103 // until all the monitor pointers from old OMTs have been transferred to the
104 // newest "current" OMT.
105 //
106 // The memory for old, unlinked OMTs will be freed after a thread-local
107 // handshake with all Java threads.
108 //
109 // Searching the OMT for a monitor pointer while there are several generations
110 // of the OMT, will start from the oldest OMT.
111 //
112 // A note about the GROW_LOAD_FACTOR: In order to guarantee that the add and
113 // search algorithms can't loop forever, we must make sure that there is at
114 // least one null pointer in the array to stop them from dead looping.
115 // Furthermore, when we grow the OMT, we must make sure that the new "current"
116 // can accommodate all the monitors from all older OMTs, while still being so
117 // sparsely populated that the C2 generated code will likely find what it's
118 // searching for at the hash index, without needing further linear searching.
119 // The grow load factor is set to 12.5%, which satisfies the above
120 // requirements. Don't change it for fun, it might backfire.
121 // -----------------------------------------------------------------------------
122
123 // Get the identity hash from an oop, handling both compact and legacy headers.
124 // Returns 0 if the object has not been hashed yet (meaning no monitor exists
125 // for it in the table).
126 static intptr_t object_hash(oop obj) {
127 markWord mark = obj->mark();
128 if (UseCompactObjectHeaders) {
129 if (!mark.is_hashed()) {
130 return 0;
131 }
132 return static_cast<intptr_t>(ObjectSynchronizer::get_hash(mark, obj));
133 } else {
134 return mark.hash();
135 }
136 }
137
138 Atomic<ObjectMonitorTable::Table*> ObjectMonitorTable::_curr;
139
140 class ObjectMonitorTable::Table : public CHeapObj<mtObjectMonitor> {
141 friend class ObjectMonitorTable;
142
143 DEFINE_PAD_MINUS_SIZE(0, DEFAULT_CACHE_LINE_SIZE, 0);
144 const size_t _capacity_mask; // One less than its power-of-two capacity
145 Atomic<Table*> _prev; // Set while growing/rebuilding
146 Atomic<Entry>* _buckets; // The payload
147 DEFINE_PAD_MINUS_SIZE(1, DEFAULT_CACHE_LINE_SIZE, sizeof(_capacity_mask) + sizeof(_prev) + sizeof(_buckets));
148 Atomic<size_t> _items_count;
149 DEFINE_PAD_MINUS_SIZE(2, DEFAULT_CACHE_LINE_SIZE, sizeof(_items_count));
150
151 static Entry as_entry(ObjectMonitor* monitor) {
152 Entry entry = static_cast<Entry>((uintptr_t)monitor);
153 assert(entry >= Entry::below_is_special, "Must be! (entry: " PTR_FORMAT ")", intptr_t(entry));
154 return entry;
155 }
156
157 static ObjectMonitor* as_monitor(Entry entry) {
402 bool result = bucket.compare_set(entry, removed(), memory_order_relaxed);
403 assert(result, "should not fail");
404 break;
405 }
406
407 index = (index + 1) & _capacity_mask;
408 assert(index != start_index, "invariant");
409 }
410
411 // Old versions are removed after newer versions to ensure that observing
412 // the monitor removed and then doing a subsequent lookup results in there
413 // still not being a monitor, instead of flickering back to being there.
414 // Only the deflation thread rebuilds and unlinks tables, so we do not need
415 // any concurrency safe prev read below.
416 if (_prev.load_relaxed() != nullptr) {
417 _prev.load_relaxed()->remove(obj, old_monitor, hash);
418 }
419 }
420
421 void reinsert(oop obj, Entry new_monitor) {
422 intptr_t hash = as_monitor(new_monitor)->hash();
423
424 const size_t start_index = size_t(hash) & _capacity_mask;
425 size_t index = start_index;
426
427 for (;;) {
428 Atomic<Entry>& bucket = _buckets[index];
429 Entry entry = bucket.load_acquire();
430
431 if (entry == empty()) {
432 // Empty slot to install the new monitor.
433 Entry result = bucket.compare_exchange(entry, new_monitor, memory_order_acq_rel);
434 if (result == entry) {
435 // Success - unconditionally increment.
436 inc_items_count();
437 return;
438 }
439
440 // Another monitor was installed.
441 entry = result;
442 }
518 // In the current implementation the deflation thread drives
519 // the rebuilding, and it will already have removed any entry
520 // it has deflated. The assert is only here to make sure.
521 assert(!monitor->is_being_async_deflated(), "Should be");
522 // Re-insert still live monitor.
523 reinsert(obj, entry);
524 }
525 }
526 }
527
528 // Unlink this table, releasing the tombstones and relocations.
529 _prev.release_store(nullptr);
530 }
531 };
532
533 void ObjectMonitorTable::create() {
534 _curr.store_relaxed(new Table(128, nullptr));
535 }
536
537 ObjectMonitor* ObjectMonitorTable::monitor_get(oop obj) {
538 const intptr_t hash = object_hash(obj);
539 if (hash == 0) return nullptr;
540 Table* curr = _curr.load_acquire();
541 ObjectMonitor* monitor = curr->get(obj, hash);
542 return monitor;
543 }
544
545 // Returns a new table to try inserting into.
546 ObjectMonitorTable::Table* ObjectMonitorTable::grow_table(Table* curr) {
547 Table* result;
548 Table* new_table = _curr.load_acquire();
549 if (new_table != curr) {
550 // Table changed; no need to try further
551 return new_table;
552 }
553
554 {
555 // Use MonitorDeflation_lock to only allow one inflating thread to
556 // attempt to allocate the new table.
557 MonitorLocker ml(MonitorDeflation_lock, Mutex::_no_safepoint_check_flag);
558
559 new_table = _curr.load_acquire();
566 result = _curr.compare_exchange(curr, new_table, memory_order_acq_rel);
567 if (result == curr) {
568 log_info(monitorinflation)("Growing object monitor table (capacity: %zu)",
569 new_table->capacity());
570 // Since we grew the table (we have a new current) we need to
571 // notify the deflation thread to rebuild the table (to get rid of
572 // old currents).
573 ObjectSynchronizer::set_is_async_deflation_requested(true);
574 ml.notify_all();
575 return new_table;
576 }
577 }
578
579 // Somebody else started rebuilding; restart in their new table.
580 delete new_table;
581
582 return result;
583 }
584
585 ObjectMonitor* ObjectMonitorTable::monitor_put_get(ObjectMonitor* monitor, oop obj) {
586 const intptr_t hash = monitor->hash();
587 Table* curr = _curr.load_acquire();
588
589 for (;;) {
590 // Curr is the latest table and is reasonably loaded.
591 ObjectMonitor* result = curr->get_set(obj, curr->as_entry(monitor), hash);
592 if (result != nullptr) {
593 return result;
594 }
595 // The table's limit was reached, we need to grow it.
596 curr = grow_table(curr);
597 }
598 }
599
600 void ObjectMonitorTable::remove_monitor_entry(ObjectMonitor* monitor) {
601 oop obj = monitor->object_peek();
602 if (obj == nullptr) {
603 // Defer removal until subsequent rebuilding.
604 return;
605 }
606 const intptr_t hash = monitor->hash();
607 Table* curr = _curr.load_acquire();
608 curr->remove(obj, curr->as_entry(monitor), hash);
609 assert(monitor_get(obj) != monitor, "should have been removed");
610 }
611
612 // Before handshake; rebuild and unlink tables.
613 void ObjectMonitorTable::rebuild(GrowableArray<Table*>* delete_list) {
614 Table* new_table;
615 {
616 // Concurrent inserts while in the middle of rebuilding can result
617 // in the population count increasing past the load factor limit.
618 // For this to be okay we need to bound how much it may exceed the
619 // limit. A sequence of tables with doubling capacity may
620 // eventually, after rebuilding, reach the maximum population of
621 // max_population(table_1) + max_population(table_1*2) + ... +
622 // max_population(table_1*2^n).
623 // I.e. max_population(2*table_1 *2^n) - max_population(table_1).
624 // With a 12.5% load factor, the implication is that as long as
625 // rebuilding a table will double its capacity, the maximum load
626 // after rebuilding is less than 25%. However, we can't always
|