1 /*
2 * Copyright (c) 2018, 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 #include "gc/shared/oopStorage.inline.hpp"
26 #include "gc/shared/oopStorageParState.inline.hpp"
27 #include "gc/shared/workgroup.hpp"
28 #include "memory/allocation.inline.hpp"
29 #include "memory/resourceArea.hpp"
30 #include "metaprogramming/conditional.hpp"
31 #include "metaprogramming/enableIf.hpp"
32 #include "runtime/handles.inline.hpp"
33 #include "runtime/interfaceSupport.inline.hpp"
34 #include "runtime/mutex.hpp"
35 #include "runtime/mutexLocker.hpp"
36 #include "runtime/thread.hpp"
37 #include "runtime/vm_operations.hpp"
38 #include "runtime/vmThread.hpp"
39 #include "utilities/align.hpp"
40 #include "utilities/ostream.hpp"
41 #include "utilities/quickSort.hpp"
42 #include "unittest.hpp"
43
44 // --- FIXME: Disable some tests on 32bit Windows, because SafeFetch
45 // (which is used by allocation_status) doesn't currently provide
46 // protection in the context where gtests are run; see JDK-8185734.
47 #ifdef _WIN32
48 #define DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS
49 #endif
50
51 // Access storage internals.
52 class OopStorage::TestAccess : public AllStatic {
53 public:
54 typedef OopStorage::Block Block;
55 typedef OopStorage::AllocateList AllocateList;
56 typedef OopStorage::ActiveArray ActiveArray;
57
58 static ActiveArray& active_array(const OopStorage& storage) {
59 return *storage._active_array;
60 }
61
62 static AllocateList& allocate_list(OopStorage& storage) {
63 return storage._allocate_list;
64 }
65
66 static const AllocateList& allocate_list(const OopStorage& storage) {
67 return storage._allocate_list;
68 }
69
70 static Mutex* allocate_mutex(const OopStorage& storage) {
71 return storage._allocate_mutex;
72 }
73
74 static bool reduce_deferred_updates(OopStorage& storage) {
75 return storage.reduce_deferred_updates();
76 }
77
78 static bool block_is_empty(const Block& block) {
79 return block.is_empty();
80 }
81
82 static bool block_is_full(const Block& block) {
83 return block.is_full();
84 }
85
86 static unsigned block_allocation_count(const Block& block) {
87 uintx bitmask = block.allocated_bitmask();
88 unsigned count = 0;
89 for ( ; bitmask != 0; bitmask >>= 1) {
90 if ((bitmask & 1) != 0) {
91 ++count;
92 }
93 }
94 return count;
95 }
96
97 static size_t memory_per_block() {
98 return Block::allocation_size();
99 }
100
101 static void block_array_set_block_count(ActiveArray* blocks, size_t count) {
102 blocks->_block_count = count;
103 }
104 };
105
106 typedef OopStorage::TestAccess TestAccess;
107
108 // The "Oop" prefix is to avoid collision with similar opto names when
109 // building with precompiled headers, or for consistency with that
110 // workaround. There really should be an opto namespace.
111 typedef TestAccess::Block OopBlock;
112 typedef TestAccess::AllocateList AllocateList;
113 typedef TestAccess::ActiveArray ActiveArray;
114
115 // Using EXPECT_EQ can't use NULL directly. Otherwise AIX build breaks.
116 const OopBlock* const NULL_BLOCK = NULL;
117
118 static size_t list_length(const AllocateList& list) {
119 size_t result = 0;
120 for (const OopBlock* block = list.chead();
121 block != NULL;
122 block = list.next(*block)) {
123 ++result;
124 }
125 return result;
126 }
127
128 static void clear_list(AllocateList& list) {
129 OopBlock* next;
130 for (OopBlock* block = list.head(); block != NULL; block = next) {
131 next = list.next(*block);
132 list.unlink(*block);
133 }
134 }
135
136 static bool is_list_empty(const AllocateList& list) {
137 return list.chead() == NULL;
138 }
139
140 static bool process_deferred_updates(OopStorage& storage) {
141 MutexLockerEx ml(TestAccess::allocate_mutex(storage), Mutex::_no_safepoint_check_flag);
142 bool result = false;
143 while (TestAccess::reduce_deferred_updates(storage)) {
144 result = true;
145 }
146 return result;
147 }
148
149 static void release_entry(OopStorage& storage, oop* entry, bool process_deferred = true) {
150 *entry = NULL;
151 storage.release(entry);
152 if (process_deferred) {
153 process_deferred_updates(storage);
154 }
155 }
156
157 static size_t empty_block_count(const OopStorage& storage) {
158 const AllocateList& list = TestAccess::allocate_list(storage);
159 size_t count = 0;
160 for (const OopBlock* block = list.ctail();
161 (block != NULL) && block->is_empty();
162 ++count, block = list.prev(*block))
163 {}
164 return count;
165 }
166
167 static size_t active_count(const OopStorage& storage) {
168 return TestAccess::active_array(storage).block_count();
169 }
170
171 static OopBlock* active_head(const OopStorage& storage) {
172 ActiveArray& ba = TestAccess::active_array(storage);
173 size_t count = ba.block_count();
174 if (count == 0) {
175 return NULL;
176 } else {
177 return ba.at(count - 1);
178 }
179 }
180
181 class OopStorageTest : public ::testing::Test {
182 public:
183 OopStorageTest();
184 ~OopStorageTest();
185
186 Mutex _allocate_mutex;
187 Mutex _active_mutex;
188 OopStorage _storage;
189
190 static const int _active_rank = Mutex::leaf - 1;
191 static const int _allocate_rank = Mutex::leaf;
192
193 class CountingIterateClosure;
194 template<bool is_const> class VM_CountAtSafepoint;
195 };
196
197 OopStorageTest::OopStorageTest() :
198 _allocate_mutex(_allocate_rank,
199 "test_OopStorage_allocate",
200 false,
201 Mutex::_safepoint_check_never),
202 _active_mutex(_active_rank,
203 "test_OopStorage_active",
204 false,
205 Mutex::_safepoint_check_never),
206 _storage("Test Storage", &_allocate_mutex, &_active_mutex)
207 { }
208
209 OopStorageTest::~OopStorageTest() {
210 clear_list(TestAccess::allocate_list(_storage));
211 }
212
213 class OopStorageTestWithAllocation : public OopStorageTest {
214 public:
215 OopStorageTestWithAllocation();
216
217 static const size_t _max_entries = 1000;
218 oop* _entries[_max_entries];
219
220 class VM_DeleteBlocksAtSafepoint;
221 };
222
223 OopStorageTestWithAllocation::OopStorageTestWithAllocation() {
224 for (size_t i = 0; i < _max_entries; ++i) {
225 _entries[i] = _storage.allocate();
226 EXPECT_TRUE(_entries[i] != NULL);
227 EXPECT_EQ(i + 1, _storage.allocation_count());
228 }
229 };
230
231 const size_t OopStorageTestWithAllocation::_max_entries;
232
233 class OopStorageTestWithAllocation::VM_DeleteBlocksAtSafepoint
234 : public VM_GTestExecuteAtSafepoint {
235 public:
236 VM_DeleteBlocksAtSafepoint(OopStorage* storage) : _storage(storage) {}
237
238 void doit() {
239 _storage->delete_empty_blocks_safepoint();
240 }
241
242 private:
243 OopStorage* _storage;
244 };
245
246 static bool is_allocate_list_sorted(const OopStorage& storage) {
247 // The allocate_list isn't strictly sorted. Rather, all empty
248 // blocks are segregated to the end of the list.
249 const AllocateList& list = TestAccess::allocate_list(storage);
250 const OopBlock* block = list.ctail();
251 for ( ; (block != NULL) && block->is_empty(); block = list.prev(*block)) {}
252 for ( ; block != NULL; block = list.prev(*block)) {
253 if (block->is_empty()) {
254 return false;
255 }
256 }
257 return true;
258 }
259
260 static size_t total_allocation_count(const OopStorage& storage) {
261 size_t total_count = 0;
262 const ActiveArray& ba = TestAccess::active_array(storage);
263 size_t limit = active_count(storage);
264 for (size_t i = 0; i < limit; ++i) {
265 total_count += TestAccess::block_allocation_count(*ba.at(i));
266 }
267 return total_count;
268 }
269
270 TEST_VM_F(OopStorageTest, allocate_one) {
271 EXPECT_EQ(0u, active_count(_storage));
272 EXPECT_TRUE(is_list_empty(TestAccess::allocate_list(_storage)));
273
274 oop* ptr = _storage.allocate();
275 EXPECT_TRUE(ptr != NULL);
276 EXPECT_EQ(1u, _storage.allocation_count());
277
278 EXPECT_EQ(1u, active_count(_storage));
279 EXPECT_EQ(1u, _storage.block_count());
280 EXPECT_EQ(1u, list_length(TestAccess::allocate_list(_storage)));
281
282 EXPECT_EQ(0u, empty_block_count(_storage));
283
284 const OopBlock* block = TestAccess::allocate_list(_storage).chead();
285 EXPECT_NE(block, (OopBlock*)NULL);
286 EXPECT_EQ(block, active_head(_storage));
287 EXPECT_FALSE(TestAccess::block_is_empty(*block));
288 EXPECT_FALSE(TestAccess::block_is_full(*block));
289 EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));
290
291 release_entry(_storage, ptr);
292 EXPECT_EQ(0u, _storage.allocation_count());
293
294 EXPECT_EQ(1u, active_count(_storage));
295 EXPECT_EQ(1u, _storage.block_count());
296 EXPECT_EQ(1u, list_length(TestAccess::allocate_list(_storage)));
297
298 EXPECT_EQ(1u, empty_block_count(_storage));
299
300 const OopBlock* new_block = TestAccess::allocate_list(_storage).chead();
301 EXPECT_EQ(block, new_block);
302 EXPECT_EQ(block, active_head(_storage));
303 EXPECT_TRUE(TestAccess::block_is_empty(*block));
304 EXPECT_FALSE(TestAccess::block_is_full(*block));
305 EXPECT_EQ(0u, TestAccess::block_allocation_count(*block));
306 }
307
308 TEST_VM_F(OopStorageTest, allocation_count) {
309 static const size_t max_entries = 1000;
310 oop* entries[max_entries];
311
312 AllocateList& allocate_list = TestAccess::allocate_list(_storage);
313
314 EXPECT_EQ(0u, active_count(_storage));
315 EXPECT_EQ(0u, _storage.block_count());
316 EXPECT_TRUE(is_list_empty(allocate_list));
317
318 size_t allocated = 0;
319 for ( ; allocated < max_entries; ++allocated) {
320 EXPECT_EQ(allocated, _storage.allocation_count());
321 if (active_count(_storage) != 0) {
322 EXPECT_EQ(1u, active_count(_storage));
323 EXPECT_EQ(1u, _storage.block_count());
324 const OopBlock& block = *TestAccess::active_array(_storage).at(0);
325 EXPECT_EQ(allocated, TestAccess::block_allocation_count(block));
326 if (TestAccess::block_is_full(block)) {
327 break;
328 } else {
329 EXPECT_FALSE(is_list_empty(allocate_list));
330 EXPECT_EQ(&block, allocate_list.chead());
331 }
332 }
333 entries[allocated] = _storage.allocate();
334 }
335
336 EXPECT_EQ(allocated, _storage.allocation_count());
337 EXPECT_EQ(1u, active_count(_storage));
338 EXPECT_EQ(1u, _storage.block_count());
339 EXPECT_TRUE(is_list_empty(allocate_list));
340 const OopBlock& block = *TestAccess::active_array(_storage).at(0);
341 EXPECT_TRUE(TestAccess::block_is_full(block));
342 EXPECT_EQ(allocated, TestAccess::block_allocation_count(block));
343
344 for (size_t i = 0; i < allocated; ++i) {
345 release_entry(_storage, entries[i]);
346 size_t remaining = allocated - (i + 1);
347 EXPECT_EQ(remaining, TestAccess::block_allocation_count(block));
348 EXPECT_EQ(remaining, _storage.allocation_count());
349 EXPECT_FALSE(is_list_empty(allocate_list));
350 }
351 }
352
353 TEST_VM_F(OopStorageTest, allocate_many) {
354 static const size_t max_entries = 1000;
355 oop* entries[max_entries];
356
357 AllocateList& allocate_list = TestAccess::allocate_list(_storage);
358
359 EXPECT_EQ(0u, empty_block_count(_storage));
360
361 entries[0] = _storage.allocate();
362 ASSERT_TRUE(entries[0] != NULL);
363 EXPECT_EQ(1u, active_count(_storage));
364 EXPECT_EQ(1u, _storage.block_count());
365 EXPECT_EQ(1u, list_length(allocate_list));
366 EXPECT_EQ(0u, empty_block_count(_storage));
367
368 const OopBlock* block = TestAccess::active_array(_storage).at(0);
369 EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));
370 EXPECT_EQ(block, allocate_list.chead());
371
372 for (size_t i = 1; i < max_entries; ++i) {
373 entries[i] = _storage.allocate();
374 EXPECT_EQ(i + 1, _storage.allocation_count());
375 ASSERT_TRUE(entries[i] != NULL);
376 EXPECT_EQ(0u, empty_block_count(_storage));
377
378 if (block == NULL) {
379 ASSERT_FALSE(is_list_empty(allocate_list));
380 EXPECT_EQ(1u, list_length(allocate_list));
381 block = allocate_list.chead();
382 EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));
383 EXPECT_EQ(block, active_head(_storage));
384 } else if (TestAccess::block_is_full(*block)) {
385 EXPECT_TRUE(is_list_empty(allocate_list));
386 block = NULL;
387 } else {
388 EXPECT_FALSE(is_list_empty(allocate_list));
389 EXPECT_EQ(block, allocate_list.chead());
390 EXPECT_EQ(block, active_head(_storage));
391 }
392 }
393
394 if (block != NULL) {
395 EXPECT_NE(0u, TestAccess::block_allocation_count(*block));
396 EXPECT_FALSE(is_list_empty(allocate_list));
397 EXPECT_EQ(block, allocate_list.chead());
398 EXPECT_EQ(block, active_head(_storage));
399 }
400
401 for (size_t i = 0; i < max_entries; ++i) {
402 release_entry(_storage, entries[i]);
403 EXPECT_TRUE(is_allocate_list_sorted(_storage));
404 EXPECT_EQ(max_entries - (i + 1), total_allocation_count(_storage));
405 }
406
407 EXPECT_EQ(active_count(_storage), list_length(allocate_list));
408 EXPECT_EQ(active_count(_storage), _storage.block_count());
409 EXPECT_EQ(active_count(_storage), empty_block_count(_storage));
410 for (const OopBlock* block = allocate_list.chead();
411 block != NULL;
412 block = allocate_list.next(*block)) {
413 EXPECT_TRUE(TestAccess::block_is_empty(*block));
414 }
415 }
416
417 TEST_VM_F(OopStorageTestWithAllocation, random_release) {
418 static const size_t step = 11;
419 ASSERT_NE(0u, _max_entries % step); // max_entries and step are mutually prime
420
421 EXPECT_EQ(0u, empty_block_count(_storage));
422
423 AllocateList& allocate_list = TestAccess::allocate_list(_storage);
424
425 EXPECT_EQ(_max_entries, total_allocation_count(_storage));
426 EXPECT_GE(1u, list_length(allocate_list));
427
428 // Release all entries in "random" order.
429 size_t released = 0;
430 for (size_t i = 0; released < _max_entries; i = (i + step) % _max_entries) {
431 if (_entries[i] != NULL) {
432 release_entry(_storage, _entries[i]);
433 _entries[i] = NULL;
434 ++released;
435 EXPECT_EQ(_max_entries - released, total_allocation_count(_storage));
436 EXPECT_TRUE(is_allocate_list_sorted(_storage));
437 }
438 }
439
440 EXPECT_EQ(active_count(_storage), list_length(allocate_list));
441 EXPECT_EQ(active_count(_storage), _storage.block_count());
442 EXPECT_EQ(0u, total_allocation_count(_storage));
443 EXPECT_EQ(list_length(allocate_list), empty_block_count(_storage));
444 }
445
446 TEST_VM_F(OopStorageTestWithAllocation, random_allocate_release) {
447 static const size_t release_step = 11;
448 static const size_t allocate_step = 5;
449 ASSERT_NE(0u, _max_entries % release_step); // max_entries and step are mutually prime
450
451 EXPECT_EQ(0u, empty_block_count(_storage));
452
453 AllocateList& allocate_list = TestAccess::allocate_list(_storage);
454
455 EXPECT_EQ(_max_entries, total_allocation_count(_storage));
456 EXPECT_GE(1u, list_length(allocate_list));
457
458 // Release all entries in "random" order, "randomly" interspersed
459 // with additional allocations.
460 size_t released = 0;
461 size_t total_released = 0;
462 for (size_t i = 0; released < _max_entries; i = (i + release_step) % _max_entries) {
463 if (_entries[i] != NULL) {
464 release_entry(_storage, _entries[i]);
465 _entries[i] = NULL;
466 ++released;
467 ++total_released;
468 EXPECT_EQ(_max_entries - released, total_allocation_count(_storage));
469 EXPECT_TRUE(is_allocate_list_sorted(_storage));
470 if (total_released % allocate_step == 0) {
471 _entries[i] = _storage.allocate();
472 --released;
473 EXPECT_EQ(_max_entries - released, total_allocation_count(_storage));
474 EXPECT_TRUE(is_allocate_list_sorted(_storage));
475 }
476 }
477 }
478
479 EXPECT_EQ(active_count(_storage), list_length(allocate_list));
480 EXPECT_EQ(active_count(_storage), _storage.block_count());
481 EXPECT_EQ(0u, total_allocation_count(_storage));
482 EXPECT_EQ(list_length(allocate_list), empty_block_count(_storage));
483 }
484
485 template<bool sorted>
486 class OopStorageTestBlockRelease : public OopStorageTestWithAllocation {
487 public:
488 void SetUp() {
489 size_t nrelease = _max_entries / 2;
490 oop** to_release = NEW_C_HEAP_ARRAY(oop*, nrelease, mtInternal);
491
492 for (size_t i = 0; i < nrelease; ++i) {
493 to_release[i] = _entries[2 * i];
494 *to_release[i] = NULL;
495 }
496 if (sorted) {
497 QuickSort::sort(to_release, nrelease, PointerCompare(), false);
498 }
499
500 _storage.release(to_release, nrelease);
501 EXPECT_EQ(_max_entries - nrelease, _storage.allocation_count());
502
503 for (size_t i = 0; i < nrelease; ++i) {
504 release_entry(_storage, _entries[2 * i + 1], false);
505 EXPECT_EQ(_max_entries - nrelease - (i + 1), _storage.allocation_count());
506 }
507 EXPECT_TRUE(process_deferred_updates(_storage));
508
509 EXPECT_EQ(_storage.block_count(), empty_block_count(_storage));
510
511 FREE_C_HEAP_ARRAY(oop*, to_release);
512 }
513
514 struct PointerCompare {
515 int operator()(const void* p, const void* q) const {
516 return (p < q) ? -1 : int(p != q);
517 }
518 };
519 };
520
521 typedef OopStorageTestBlockRelease<true> OopStorageTestBlockReleaseSorted;
522 typedef OopStorageTestBlockRelease<false> OopStorageTestBlockReleaseUnsorted;
523
524 TEST_VM_F(OopStorageTestBlockReleaseSorted, block_release) {}
525 TEST_VM_F(OopStorageTestBlockReleaseUnsorted, block_release) {}
526
527 #ifndef DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS
528 TEST_VM_F(OopStorageTest, invalid_pointer) {
529 {
530 char* mem = NEW_C_HEAP_ARRAY(char, 1000, mtInternal);
531 oop* ptr = reinterpret_cast<oop*>(align_down(mem + 250, sizeof(oop)));
532 // Predicate returns false for some malloc'ed block.
533 EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(ptr));
534 FREE_C_HEAP_ARRAY(char, mem);
535 }
536
537 {
538 oop obj;
539 oop* ptr = &obj;
540 // Predicate returns false for some "random" location.
541 EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(ptr));
542 }
543 }
544 #endif // DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS
545
546 class OopStorageTest::CountingIterateClosure {
547 public:
548 size_t _const_count;
549 size_t _const_non_null;
550 size_t _non_const_count;
551 size_t _non_const_non_null;
552
553 void do_oop(const oop* ptr) {
554 ++_const_count;
555 if (*ptr != NULL) {
556 ++_const_non_null;
557 }
558 }
559
560 void do_oop(oop* ptr) {
561 ++_non_const_count;
562 if (*ptr != NULL) {
563 ++_non_const_non_null;
564 }
565 }
566
567 CountingIterateClosure() :
568 _const_count(0),
569 _const_non_null(0),
570 _non_const_count(0),
571 _non_const_non_null(0)
572 {}
573 };
574
575 template<bool is_const>
576 class OopStorageTest::VM_CountAtSafepoint : public VM_GTestExecuteAtSafepoint {
577 public:
578 typedef typename Conditional<is_const,
579 const OopStorage,
580 OopStorage>::type Storage;
581
582 VM_CountAtSafepoint(Storage* storage, CountingIterateClosure* cl) :
583 _storage(storage), _cl(cl)
584 {}
585
586 void doit() { _storage->oops_do(_cl); }
587
588 private:
589 Storage* _storage;
590 CountingIterateClosure* _cl;
591 };
592
593 TEST_VM_F(OopStorageTest, simple_iterate) {
594 // Dummy oop value.
595 intptr_t dummy_oop_value = 0xbadbeaf;
596 oop dummy_oop = reinterpret_cast<oopDesc*>(&dummy_oop_value);
597
598 const size_t max_entries = 1000;
599 oop* entries[max_entries];
600
601 size_t allocated = 0;
602 size_t entries_with_values = 0;
603 for (size_t i = 0; i < max_entries; i += 10) {
604 for ( ; allocated < i; ++allocated) {
605 entries[allocated] = _storage.allocate();
606 ASSERT_TRUE(entries[allocated] != NULL);
607 if ((allocated % 3) != 0) {
608 *entries[allocated] = dummy_oop;
609 ++entries_with_values;
610 }
611 }
612
613 {
614 CountingIterateClosure cl;
615 VM_CountAtSafepoint<false> op(&_storage, &cl);
616 {
617 ThreadInVMfromNative invm(JavaThread::current());
618 VMThread::execute(&op);
619 }
620 EXPECT_EQ(allocated, cl._non_const_count);
621 EXPECT_EQ(entries_with_values, cl._non_const_non_null);
622 EXPECT_EQ(0u, cl._const_count);
623 EXPECT_EQ(0u, cl._const_non_null);
624 }
625
626 {
627 CountingIterateClosure cl;
628 VM_CountAtSafepoint<true> op(&_storage, &cl);
629 {
630 ThreadInVMfromNative invm(JavaThread::current());
631 VMThread::execute(&op);
632 }
633 EXPECT_EQ(allocated, cl._const_count);
634 EXPECT_EQ(entries_with_values, cl._const_non_null);
635 EXPECT_EQ(0u, cl._non_const_count);
636 EXPECT_EQ(0u, cl._non_const_non_null);
637 }
638 }
639
640 while (allocated > 0) {
641 release_entry(_storage, entries[--allocated], false);
642 }
643 process_deferred_updates(_storage);
644 }
645
646 class OopStorageTestIteration : public OopStorageTestWithAllocation {
647 public:
648 static const size_t _max_workers = 2;
649 unsigned char _states[_max_workers][_max_entries];
650
651 static const unsigned char mark_released = 1u << 0;
652 static const unsigned char mark_invalid = 1u << 1;
653 static const unsigned char mark_const = 1u << 2;
654 static const unsigned char mark_non_const = 1u << 3;
655
656 virtual void SetUp() {
657 OopStorageTestWithAllocation::SetUp();
658
659 memset(_states, 0, sizeof(_states));
660
661 size_t initial_release = 0;
662 for ( ; empty_block_count(_storage) < 2; ++initial_release) {
663 ASSERT_GT(_max_entries, initial_release);
664 release_entry(_storage, _entries[initial_release]);
665 _states[0][initial_release] = mark_released;
666 }
667
668 for (size_t i = initial_release; i < _max_entries; i += 3) {
669 release_entry(_storage, _entries[i], false);
670 _states[0][i] = mark_released;
671 }
672 process_deferred_updates(_storage);
673 }
674
675 class VerifyState;
676 class VerifyFn;
677 template<bool is_const> class VM_Verify;
678
679 class VerifyClosure;
680 class VM_VerifyUsingOopsDo;
681 };
682
683 const unsigned char OopStorageTestIteration::mark_released;
684 const unsigned char OopStorageTestIteration::mark_invalid;
685 const unsigned char OopStorageTestIteration::mark_const;
686 const unsigned char OopStorageTestIteration::mark_non_const;
687
688 class OopStorageTestIteration::VerifyState {
689 public:
690 unsigned char _expected_mark;
691 const oop* const* _entries;
692 unsigned char (&_states)[_max_workers][_max_entries];
693
694 VerifyState(unsigned char expected_mark,
695 const oop* const* entries,
696 unsigned char (&states)[_max_workers][_max_entries]) :
697 _expected_mark(expected_mark),
698 _entries(entries),
699 _states(states)
700 { }
701
702 bool update(const oop* ptr, uint worker_id, unsigned char mark) const {
703 size_t index = 0;
704 bool found = find_entry(ptr, &index);
705 EXPECT_TRUE(found);
706 EXPECT_GT(_max_entries, index);
707 EXPECT_GT(_max_workers, worker_id);
708 if (!found) {
709 return false;
710 } else if (index >= _max_entries) {
711 return false;
712 } else if (worker_id >= _max_workers) {
713 return false;
714 } else {
715 EXPECT_EQ(0, _states[worker_id][index]);
716 if (_states[worker_id][index] != 0) {
717 _states[worker_id][index] |= mark_invalid;
718 return false;
719 } else {
720 _states[worker_id][index] |= mark;
721 return true;
722 }
723 }
724 }
725
726 void check() const {
727 for (size_t i = 0; i < _max_entries; ++i) {
728 unsigned char mark = 0;
729 for (size_t w = 0; w < _max_workers; ++w) {
730 if (mark == 0) {
731 mark = _states[w][i];
732 } else {
733 EXPECT_EQ(0u, _states[w][i]);
734 }
735 }
736 if (mark == 0) {
737 EXPECT_NE(0u, mark);
738 } else if ((mark & mark_released) != 0) {
739 EXPECT_EQ(mark_released, mark);
740 } else {
741 EXPECT_EQ(_expected_mark, mark);
742 }
743 }
744 }
745
746 private:
747 bool find_entry(const oop* ptr, size_t* index) const {
748 for (size_t i = 0; i < _max_entries; ++i) {
749 if (ptr == _entries[i]) {
750 *index = i;
751 return true;
752 }
753 }
754 return false;
755 }
756 };
757
758 class OopStorageTestIteration::VerifyFn {
759 public:
760 VerifyFn(VerifyState* state, uint worker_id = 0) :
761 _state(state),
762 _worker_id(worker_id)
763 {}
764
765 bool operator()( oop* ptr) const {
766 return _state->update(ptr, _worker_id, mark_non_const);
767 }
768
769 bool operator()(const oop* ptr) const {
770 return _state->update(ptr, _worker_id, mark_const);
771 }
772
773 private:
774 VerifyState* _state;
775 uint _worker_id;
776 };
777
778 class OopStorageTestIteration::VerifyClosure {
779 public:
780 VerifyClosure(VerifyState* state, uint worker_id = 0) :
781 _state(state),
782 _worker_id(worker_id)
783 {}
784
785 void do_oop(oop* ptr) {
786 _state->update(ptr, _worker_id, mark_non_const);
787 }
788
789 void do_oop(const oop* ptr) {
790 _state->update(ptr, _worker_id, mark_const);
791 }
792
793 private:
794 VerifyState* _state;
795 uint _worker_id;
796 };
797
798 const size_t OopStorageTestIteration::_max_workers;
799
800 template<bool is_const>
801 class OopStorageTestIteration::VM_Verify : public VM_GTestExecuteAtSafepoint {
802 public:
803 typedef typename Conditional<is_const,
804 const OopStorage,
805 OopStorage>::type Storage;
806
807 VM_Verify(Storage* storage, VerifyState* vstate) :
808 _storage(storage), _vstate(vstate), _result(false)
809 {}
810
811 void doit() {
812 VerifyFn verifier(_vstate);
813 _result = _storage->iterate_safepoint(verifier);
814 }
815
816 bool result() const { return _result; }
817
818 private:
819 Storage* _storage;
820 VerifyState* _vstate;
821 bool _result;
822 };
823
824 class OopStorageTestIteration::VM_VerifyUsingOopsDo : public VM_GTestExecuteAtSafepoint {
825 public:
826 VM_VerifyUsingOopsDo(OopStorage* storage, VerifyState* vstate) :
827 _storage(storage), _vstate(vstate)
828 {}
829
830 void doit() {
831 VerifyClosure verifier(_vstate);
832 _storage->oops_do(&verifier);
833 }
834
835 private:
836 OopStorage* _storage;
837 VerifyState* _vstate;
838 };
839
840 TEST_VM_F(OopStorageTestIteration, iterate_safepoint) {
841 VerifyState vstate(mark_non_const, _entries, _states);
842 VM_Verify<false> op(&_storage, &vstate);
843 {
844 ThreadInVMfromNative invm(JavaThread::current());
845 VMThread::execute(&op);
846 }
847 EXPECT_TRUE(op.result());
848 vstate.check();
849 }
850
851 TEST_VM_F(OopStorageTestIteration, const_iterate_safepoint) {
852 VerifyState vstate(mark_const, _entries, _states);
853 VM_Verify<true> op(&_storage, &vstate);
854 {
855 ThreadInVMfromNative invm(JavaThread::current());
856 VMThread::execute(&op);
857 }
858 EXPECT_TRUE(op.result());
859 vstate.check();
860 }
861
862 TEST_VM_F(OopStorageTestIteration, oops_do) {
863 VerifyState vstate(mark_non_const, _entries, _states);
864 VM_VerifyUsingOopsDo op(&_storage, &vstate);
865 {
866 ThreadInVMfromNative invm(JavaThread::current());
867 VMThread::execute(&op);
868 }
869 vstate.check();
870 }
871
872 class OopStorageTestParIteration : public OopStorageTestIteration {
873 public:
874 WorkGang* workers();
875
876 class VM_ParStateVerify;
877
878 template<bool concurrent, bool is_const> class Task;
879 template<bool concurrent, bool is_const> class TaskUsingOopsDo;
880
881 private:
882 static WorkGang* _workers;
883 };
884
885 WorkGang* OopStorageTestParIteration::_workers = NULL;
886
887 WorkGang* OopStorageTestParIteration::workers() {
888 if (_workers == NULL) {
889 _workers = new WorkGang("OopStorageTestParIteration workers",
890 _max_workers,
891 false,
892 false);
893 _workers->initialize_workers();
894 _workers->update_active_workers(_max_workers);
895 }
896 return _workers;
897 }
898
899 template<bool concurrent, bool is_const>
900 class OopStorageTestParIteration::Task : public AbstractGangTask {
901 typedef OopStorage::ParState<concurrent, is_const> StateType;
902
903 typedef typename Conditional<is_const,
904 const OopStorage,
905 OopStorage>::type Storage;
906
907 public:
908 Task(const char* name, Storage* storage, VerifyState* vstate) :
909 AbstractGangTask(name),
910 _state(storage),
911 _vstate(vstate)
912 {}
913
914 virtual void work(uint worker_id) {
915 VerifyFn verifier(_vstate, worker_id);
916 _state.iterate(verifier);
917 }
918
919 private:
920 StateType _state;
921 VerifyState* _vstate;
922 };
923
924 template<bool concurrent, bool is_const>
925 class OopStorageTestParIteration::TaskUsingOopsDo : public AbstractGangTask {
926 public:
927 TaskUsingOopsDo(const char* name, OopStorage* storage, VerifyState* vstate) :
928 AbstractGangTask(name),
929 _state(storage),
930 _vstate(vstate)
931 {}
932
933 virtual void work(uint worker_id) {
934 VerifyClosure verifier(_vstate, worker_id);
935 _state.oops_do(&verifier);
936 }
937
938 private:
939 OopStorage::ParState<concurrent, is_const> _state;
940 VerifyState* _vstate;
941 };
942
943 class OopStorageTestParIteration::VM_ParStateVerify : public VM_GTestExecuteAtSafepoint {
944 public:
945 VM_ParStateVerify(WorkGang* workers, AbstractGangTask* task) :
946 _workers(workers), _task(task)
947 {}
948
949 void doit() {
950 _workers->run_task(_task);
951 }
952
953 private:
954 WorkGang* _workers;
955 AbstractGangTask* _task;
956 };
957
958 TEST_VM_F(OopStorageTestParIteration, par_state_safepoint_iterate) {
959 VerifyState vstate(mark_non_const, _entries, _states);
960 Task<false, false> task("test", &_storage, &vstate);
961 VM_ParStateVerify op(workers(), &task);
962 {
963 ThreadInVMfromNative invm(JavaThread::current());
964 VMThread::execute(&op);
965 }
966 vstate.check();
967 }
968
969 TEST_VM_F(OopStorageTestParIteration, par_state_safepoint_const_iterate) {
970 VerifyState vstate(mark_const, _entries, _states);
971 Task<false, true> task("test", &_storage, &vstate);
972 VM_ParStateVerify op(workers(), &task);
973 {
974 ThreadInVMfromNative invm(JavaThread::current());
975 VMThread::execute(&op);
976 }
977 vstate.check();
978 }
979
980 TEST_VM_F(OopStorageTestParIteration, par_state_safepoint_oops_do) {
981 VerifyState vstate(mark_non_const, _entries, _states);
982 TaskUsingOopsDo<false, false> task("test", &_storage, &vstate);
983 VM_ParStateVerify op(workers(), &task);
984 {
985 ThreadInVMfromNative invm(JavaThread::current());
986 VMThread::execute(&op);
987 }
988 vstate.check();
989 }
990
991 TEST_VM_F(OopStorageTestParIteration, par_state_safepoint_const_oops_do) {
992 VerifyState vstate(mark_const, _entries, _states);
993 TaskUsingOopsDo<false, true> task("test", &_storage, &vstate);
994 VM_ParStateVerify op(workers(), &task);
995 {
996 ThreadInVMfromNative invm(JavaThread::current());
997 VMThread::execute(&op);
998 }
999 vstate.check();
1000 }
1001
1002 TEST_VM_F(OopStorageTestParIteration, par_state_concurrent_iterate) {
1003 VerifyState vstate(mark_non_const, _entries, _states);
1004 Task<true, false> task("test", &_storage, &vstate);
1005 workers()->run_task(&task);
1006 vstate.check();
1007 }
1008
1009 TEST_VM_F(OopStorageTestParIteration, par_state_concurrent_const_iterate) {
1010 VerifyState vstate(mark_const, _entries, _states);
1011 Task<true, true> task("test", &_storage, &vstate);
1012 workers()->run_task(&task);
1013 vstate.check();
1014 }
1015
1016 TEST_VM_F(OopStorageTestParIteration, par_state_concurrent_oops_do) {
1017 VerifyState vstate(mark_non_const, _entries, _states);
1018 TaskUsingOopsDo<true, false> task("test", &_storage, &vstate);
1019 workers()->run_task(&task);
1020 vstate.check();
1021 }
1022
1023 TEST_VM_F(OopStorageTestParIteration, par_state_concurrent_const_oops_do) {
1024 VerifyState vstate(mark_const, _entries, _states);
1025 TaskUsingOopsDo<true, true> task("test", &_storage, &vstate);
1026 workers()->run_task(&task);
1027 vstate.check();
1028 }
1029
1030 TEST_VM_F(OopStorageTestWithAllocation, delete_empty_blocks_safepoint) {
1031 size_t initial_active_size = active_count(_storage);
1032 EXPECT_EQ(initial_active_size, _storage.block_count());
1033 ASSERT_LE(3u, initial_active_size); // Need at least 3 blocks for test
1034
1035 for (size_t i = 0; empty_block_count(_storage) < 3; ++i) {
1036 ASSERT_GT(_max_entries, i);
1037 release_entry(_storage, _entries[i]);
1038 }
1039
1040 EXPECT_EQ(initial_active_size, active_count(_storage));
1041 EXPECT_EQ(initial_active_size, _storage.block_count());
1042 EXPECT_EQ(3u, empty_block_count(_storage));
1043
1044 {
1045 ThreadInVMfromNative invm(JavaThread::current());
1046 VM_DeleteBlocksAtSafepoint op(&_storage);
1047 VMThread::execute(&op);
1048 }
1049 EXPECT_EQ(0u, empty_block_count(_storage));
1050 EXPECT_EQ(initial_active_size - 3, active_count(_storage));
1051 EXPECT_EQ(initial_active_size - 3, _storage.block_count());
1052 }
1053
1054 TEST_VM_F(OopStorageTestWithAllocation, delete_empty_blocks_concurrent) {
1055 size_t initial_active_size = active_count(_storage);
1056 EXPECT_EQ(initial_active_size, _storage.block_count());
1057 ASSERT_LE(3u, initial_active_size); // Need at least 3 blocks for test
1058
1059 for (size_t i = 0; empty_block_count(_storage) < 3; ++i) {
1060 ASSERT_GT(_max_entries, i);
1061 release_entry(_storage, _entries[i]);
1062 }
1063
1064 EXPECT_EQ(initial_active_size, active_count(_storage));
1065 EXPECT_EQ(initial_active_size, _storage.block_count());
1066 EXPECT_EQ(3u, empty_block_count(_storage));
1067
1068 _storage.delete_empty_blocks_concurrent();
1069 EXPECT_EQ(0u, empty_block_count(_storage));
1070 EXPECT_EQ(initial_active_size - 3, active_count(_storage));
1071 EXPECT_EQ(initial_active_size - 3, _storage.block_count());
1072 }
1073
1074 TEST_VM_F(OopStorageTestWithAllocation, allocation_status) {
1075 oop* retained = _entries[200];
1076 oop* released = _entries[300];
1077 oop* garbage = reinterpret_cast<oop*>(1024 * 1024);
1078 release_entry(_storage, released);
1079
1080 EXPECT_EQ(OopStorage::ALLOCATED_ENTRY, _storage.allocation_status(retained));
1081 EXPECT_EQ(OopStorage::UNALLOCATED_ENTRY, _storage.allocation_status(released));
1082 #ifndef DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS
1083 EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(garbage));
1084 #endif
1085
1086 for (size_t i = 0; i < _max_entries; ++i) {
1087 if ((_entries[i] != retained) && (_entries[i] != released)) {
1088 // Leave deferred release updates to block deletion.
1089 release_entry(_storage, _entries[i], false);
1090 }
1091 }
1092
1093 {
1094 ThreadInVMfromNative invm(JavaThread::current());
1095 VM_DeleteBlocksAtSafepoint op(&_storage);
1096 VMThread::execute(&op);
1097 }
1098 EXPECT_EQ(OopStorage::ALLOCATED_ENTRY, _storage.allocation_status(retained));
1099 #ifndef DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS
1100 EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(released));
1101 EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(garbage));
1102 #endif // DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS
1103 }
1104
1105 TEST_VM_F(OopStorageTest, usage_info) {
1106 size_t goal_blocks = 5;
1107 oop* entries[1000];
1108 size_t allocated = 0;
1109
1110 EXPECT_EQ(0u, _storage.block_count());
1111 // There is non-block overhead, so always some usage.
1112 EXPECT_LT(0u, _storage.total_memory_usage());
1113
1114 while (_storage.block_count() < goal_blocks) {
1115 size_t this_count = _storage.block_count();
1116 while (_storage.block_count() == this_count) {
1117 ASSERT_GT(ARRAY_SIZE(entries), allocated);
1118 entries[allocated] = _storage.allocate();
1119 ASSERT_TRUE(entries[allocated] != NULL);
1120 ++allocated;
1121 }
1122 EXPECT_NE(0u, _storage.block_count());
1123 EXPECT_NE(0u, _storage.total_memory_usage());
1124 }
1125
1126 EXPECT_LT(TestAccess::memory_per_block() * _storage.block_count(),
1127 _storage.total_memory_usage());
1128 }
1129
1130 #ifndef PRODUCT
1131
1132 TEST_VM_F(OopStorageTestWithAllocation, print_storage) {
1133 // Release the first 1/2
1134 for (size_t i = 0; i < (_max_entries / 2); ++i) {
1135 // Deferred updates don't affect print output.
1136 release_entry(_storage, _entries[i], false);
1137 _entries[i] = NULL;
1138 }
1139 // Release every other remaining
1140 for (size_t i = _max_entries / 2; i < _max_entries; i += 2) {
1141 // Deferred updates don't affect print output.
1142 release_entry(_storage, _entries[i], false);
1143 _entries[i] = NULL;
1144 }
1145
1146 size_t expected_entries = _max_entries / 4;
1147 EXPECT_EQ(expected_entries, _storage.allocation_count());
1148
1149 size_t entries_per_block = BitsPerWord;
1150 size_t expected_blocks = (_max_entries + entries_per_block - 1) / entries_per_block;
1151 EXPECT_EQ(expected_blocks, _storage.block_count());
1152
1153 double expected_usage = (100.0 * expected_entries) / (expected_blocks * entries_per_block);
1154
1155 {
1156 ResourceMark rm;
1157 stringStream expected_st;
1158 expected_st.print("Test Storage: " SIZE_FORMAT
1159 " entries in " SIZE_FORMAT
1160 " blocks (%.F%%), " SIZE_FORMAT " bytes",
1161 expected_entries,
1162 expected_blocks,
1163 expected_usage,
1164 _storage.total_memory_usage());
1165 stringStream st;
1166 _storage.print_on(&st);
1167 EXPECT_STREQ(expected_st.as_string(), st.as_string());
1168 }
1169 }
1170
1171 #endif // !PRODUCT
1172
1173 class OopStorageBlockCollectionTest : public ::testing::Test {
1174 protected:
1175 OopStorageBlockCollectionTest() {
1176 for (size_t i = 0; i < nvalues; ++i) {
1177 values[i] = OopBlock::new_block(pseudo_owner());
1178 }
1179 }
1180
1181 ~OopStorageBlockCollectionTest() {
1182 for (size_t i = 0; i < nvalues; ++i) {
1183 OopBlock::delete_block(*values[i]);
1184 }
1185 }
1186
1187 public:
1188 static const size_t nvalues = 10;
1189 OopBlock* values[nvalues];
1190
1191 private:
1192 // The only thing we actually care about is the address of the owner.
1193 static const size_t pseudo_owner_size = sizeof(OopStorage) / sizeof(void*);
1194 static const void* const _pseudo_owner[pseudo_owner_size];
1195 static const OopStorage* pseudo_owner() {
1196 return reinterpret_cast<const OopStorage*>(&_pseudo_owner);
1197 }
1198 };
1199
1200 const size_t OopStorageBlockCollectionTest::nvalues;
1201 const void* const OopStorageBlockCollectionTest::_pseudo_owner[] = {};
1202
1203 class OopStorageAllocateListTest : public OopStorageBlockCollectionTest {};
1204
1205 TEST_F(OopStorageAllocateListTest, empty_list) {
1206 AllocateList list;
1207
1208 EXPECT_TRUE(is_list_empty(list));
1209 EXPECT_EQ(NULL_BLOCK, list.head());
1210 EXPECT_EQ(NULL_BLOCK, list.chead());
1211 EXPECT_EQ(NULL_BLOCK, list.ctail());
1212 }
1213
1214 TEST_F(OopStorageAllocateListTest, push_back) {
1215 AllocateList list;
1216
1217 for (size_t i = 0; i < nvalues; ++i) {
1218 list.push_back(*values[i]);
1219 EXPECT_FALSE(is_list_empty(list));
1220 EXPECT_EQ(list.ctail(), values[i]);
1221 }
1222
1223 EXPECT_EQ(list.chead(), list.head());
1224 EXPECT_EQ(list.chead(), values[0]);
1225 EXPECT_EQ(list.ctail(), values[nvalues - 1]);
1226
1227 const OopBlock* block = list.chead();
1228 for (size_t i = 0; i < nvalues; ++i) {
1229 EXPECT_EQ(block, values[i]);
1230 block = list.next(*block);
1231 }
1232 EXPECT_EQ(NULL_BLOCK, block);
1233
1234 block = list.ctail();
1235 for (size_t i = 0; i < nvalues; ++i) {
1236 EXPECT_EQ(block, values[nvalues - i - 1]);
1237 block = list.prev(*block);
1238 }
1239 EXPECT_EQ(NULL_BLOCK, block);
1240
1241 clear_list(list);
1242 }
1243
1244 TEST_F(OopStorageAllocateListTest, push_front) {
1245 AllocateList list;
1246
1247 for (size_t i = 0; i < nvalues; ++i) {
1248 list.push_front(*values[i]);
1249 EXPECT_FALSE(is_list_empty(list));
1250 EXPECT_EQ(list.head(), values[i]);
1251 }
1252
1253 EXPECT_EQ(list.chead(), list.head());
1254 EXPECT_EQ(list.chead(), values[nvalues - 1]);
1255 EXPECT_EQ(list.ctail(), values[0]);
1256
1257 const OopBlock* block = list.chead();
1258 for (size_t i = 0; i < nvalues; ++i) {
1259 EXPECT_EQ(block, values[nvalues - i - 1]);
1260 block = list.next(*block);
1261 }
1262 EXPECT_EQ(NULL_BLOCK, block);
1263
1264 block = list.ctail();
1265 for (size_t i = 0; i < nvalues; ++i) {
1266 EXPECT_EQ(block, values[i]);
1267 block = list.prev(*block);
1268 }
1269 EXPECT_EQ(NULL_BLOCK, block);
1270
1271 clear_list(list);
1272 }
1273
1274 class OopStorageAllocateListTestWithList : public OopStorageAllocateListTest {
1275 public:
1276 OopStorageAllocateListTestWithList() : list() {
1277 for (size_t i = 0; i < nvalues; ++i) {
1278 list.push_back(*values[i]);
1279 }
1280 }
1281
1282 ~OopStorageAllocateListTestWithList() {
1283 clear_list(list);
1284 }
1285
1286 AllocateList list;
1287 };
1288
1289 TEST_F(OopStorageAllocateListTestWithList, unlink_front) {
1290 EXPECT_EQ(list.chead(), values[0]);
1291 EXPECT_EQ(list.ctail(), values[nvalues - 1]);
1292
1293 list.unlink(*values[0]);
1294 EXPECT_EQ(NULL_BLOCK, list.next(*values[0]));
1295 EXPECT_EQ(NULL_BLOCK, list.prev(*values[0]));
1296 EXPECT_EQ(list.chead(), values[1]);
1297 EXPECT_EQ(list.ctail(), values[nvalues - 1]);
1298
1299 const OopBlock* block = list.chead();
1300 for (size_t i = 1; i < nvalues; ++i) {
1301 EXPECT_EQ(block, values[i]);
1302 block = list.next(*block);
1303 }
1304 EXPECT_EQ(NULL_BLOCK, block);
1305 }
1306
1307 TEST_F(OopStorageAllocateListTestWithList, unlink_back) {
1308 EXPECT_EQ(list.chead(), values[0]);
1309
1310 list.unlink(*values[nvalues - 1]);
1311 EXPECT_EQ(NULL_BLOCK, list.next(*values[nvalues - 1]));
1312 EXPECT_EQ(NULL_BLOCK, list.prev(*values[nvalues - 1]));
1313 EXPECT_EQ(list.chead(), values[0]);
1314 EXPECT_EQ(list.ctail(), values[nvalues - 2]);
1315
1316 const OopBlock* block = list.chead();
1317 for (size_t i = 0; i < nvalues - 1; ++i) {
1318 EXPECT_EQ(block, values[i]);
1319 block = list.next(*block);
1320 }
1321 EXPECT_EQ(NULL_BLOCK, block);
1322 }
1323
1324 TEST_F(OopStorageAllocateListTestWithList, unlink_middle) {
1325 EXPECT_EQ(list.chead(), values[0]);
1326
1327 size_t index = nvalues / 2;
1328
1329 list.unlink(*values[index]);
1330 EXPECT_EQ(NULL_BLOCK, list.next(*values[index]));
1331 EXPECT_EQ(NULL_BLOCK, list.prev(*values[index]));
1332 EXPECT_EQ(list.chead(), values[0]);
1333 EXPECT_EQ(list.ctail(), values[nvalues - 1]);
1334
1335 const OopBlock* block = list.chead();
1336 for (size_t i = 0; i < index; ++i) {
1337 EXPECT_EQ(block, values[i]);
1338 block = list.next(*block);
1339 }
1340 for (size_t i = index + 1; i < nvalues; ++i) {
1341 EXPECT_EQ(block, values[i]);
1342 block = list.next(*block);
1343 }
1344 EXPECT_EQ(NULL_BLOCK, block);
1345 }
1346
1347 TEST_F(OopStorageAllocateListTest, single) {
1348 AllocateList list;
1349
1350 list.push_back(*values[0]);
1351 EXPECT_EQ(NULL_BLOCK, list.next(*values[0]));
1352 EXPECT_EQ(NULL_BLOCK, list.prev(*values[0]));
1353 EXPECT_EQ(list.chead(), values[0]);
1354 EXPECT_EQ(list.ctail(), values[0]);
1355
1356 list.unlink(*values[0]);
1357 EXPECT_EQ(NULL_BLOCK, list.next(*values[0]));
1358 EXPECT_EQ(NULL_BLOCK, list.prev(*values[0]));
1359 EXPECT_EQ(NULL_BLOCK, list.chead());
1360 EXPECT_EQ(NULL_BLOCK, list.ctail());
1361 }
1362
1363 class OopStorageActiveArrayTest : public OopStorageBlockCollectionTest {};
1364
1365 TEST_F(OopStorageActiveArrayTest, empty_array) {
1366 ActiveArray* a = ActiveArray::create(nvalues);
1367
1368 EXPECT_EQ(nvalues, a->size());
1369 EXPECT_EQ(0u, a->block_count_acquire());
1370 TestAccess::block_array_set_block_count(a, 2);
1371 EXPECT_EQ(2u, a->block_count_acquire());
1372 TestAccess::block_array_set_block_count(a, 0);
1373 a->increment_refcount();
1374 a->increment_refcount();
1375 EXPECT_FALSE(a->decrement_refcount());
1376 EXPECT_TRUE(a->decrement_refcount());
1377
1378 ActiveArray::destroy(a);
1379 }
1380
1381 TEST_F(OopStorageActiveArrayTest, push) {
1382 ActiveArray* a = ActiveArray::create(nvalues - 1);
1383
1384 for (size_t i = 0; i < nvalues - 1; ++i) {
1385 EXPECT_TRUE(a->push(values[i]));
1386 EXPECT_EQ(i + 1, a->block_count_acquire());
1387 EXPECT_EQ(values[i], a->at(i));
1388 }
1389 EXPECT_FALSE(a->push(values[nvalues - 1]));
1390
1391 TestAccess::block_array_set_block_count(a, 0);
1392 ActiveArray::destroy(a);
1393 }
1394
1395 class OopStorageActiveArrayTestWithArray : public OopStorageActiveArrayTest {
1396 public:
1397 OopStorageActiveArrayTestWithArray() : a(ActiveArray::create(nvalues)) {
1398 for (size_t i = 0; i < nvalues; ++i) {
1399 a->push(values[i]);
1400 }
1401 }
1402
1403 ~OopStorageActiveArrayTestWithArray() {
1404 TestAccess::block_array_set_block_count(a, 0);
1405 ActiveArray::destroy(a);
1406 }
1407
1408 ActiveArray* a;
1409 };
1410
1411 TEST_F(OopStorageActiveArrayTestWithArray, remove0) {
1412 a->remove(values[0]);
1413 EXPECT_EQ(nvalues - 1, a->block_count_acquire());
1414 EXPECT_EQ(values[nvalues - 1], a->at(0));
1415 for (size_t i = 1; i < nvalues - 1; ++i) {
1416 EXPECT_EQ(values[i], a->at(i));
1417 }
1418 }
1419
1420 TEST_F(OopStorageActiveArrayTestWithArray, remove3) {
1421 a->remove(values[3]);
1422 EXPECT_EQ(nvalues - 1, a->block_count_acquire());
1423 for (size_t i = 0; i < 3; ++i) {
1424 EXPECT_EQ(values[i], a->at(i));
1425 }
1426 EXPECT_EQ(values[nvalues - 1], a->at(3));
1427 for (size_t i = 4; i < nvalues - 1; ++i) {
1428 EXPECT_EQ(values[i], a->at(i));
1429 }
1430 }
1431
1432 TEST_F(OopStorageActiveArrayTestWithArray, remove_last) {
1433 a->remove(values[nvalues - 1]);
1434 EXPECT_EQ(nvalues - 1, a->block_count_acquire());
1435 for (size_t i = 0; i < nvalues - 1; ++i) {
1436 EXPECT_EQ(values[i], a->at(i));
1437 }
1438 }