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