indirect_reference_table_test.cc revision 9d7ef62b854289632791a83223c1a5a5b3c8fc64 
1/*
2 * Copyright (C) 2009 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include "indirect_reference_table-inl.h"
18
19#include "class_linker-inl.h"
20#include "common_runtime_test.h"
21#include "mirror/object-inl.h"
22#include "scoped_thread_state_change-inl.h"
23
24namespace art {
25
26class IndirectReferenceTableTest : public CommonRuntimeTest {};
27
28static void CheckDump(IndirectReferenceTable* irt, size_t num_objects, size_t num_unique)
29    REQUIRES_SHARED(Locks::mutator_lock_) {
30  std::ostringstream oss;
31  irt->Dump(oss);
32  if (num_objects == 0) {
33    EXPECT_EQ(oss.str().find("java.lang.Object"), std::string::npos) << oss.str();
34  } else if (num_objects == 1) {
35    EXPECT_NE(oss.str().find("1 of java.lang.Object"), std::string::npos) << oss.str();
36  } else {
37    EXPECT_NE(oss.str().find(StringPrintf("%zd of java.lang.Object (%zd unique instances)",
38                                          num_objects, num_unique)),
39              std::string::npos)
40                  << "\n Expected number of objects: " << num_objects
41                  << "\n Expected unique objects: " << num_unique << "\n"
42                  << oss.str();
43  }
44}
45
46TEST_F(IndirectReferenceTableTest, BasicTest) {
47  // This will lead to error messages in the log.
48  ScopedLogSeverity sls(LogSeverity::FATAL);
49
50  ScopedObjectAccess soa(Thread::Current());
51  static const size_t kTableMax = 20;
52  std::string error_msg;
53  IndirectReferenceTable irt(kTableMax,
54                             kGlobal,
55                             IndirectReferenceTable::ResizableCapacity::kNo,
56                             &error_msg);
57  ASSERT_TRUE(irt.IsValid()) << error_msg;
58
59  mirror::Class* c = class_linker_->FindSystemClass(soa.Self(), "Ljava/lang/Object;");
60  StackHandleScope<4> hs(soa.Self());
61  ASSERT_TRUE(c != nullptr);
62  Handle<mirror::Object> obj0 = hs.NewHandle(c->AllocObject(soa.Self()));
63  ASSERT_TRUE(obj0.Get() != nullptr);
64  Handle<mirror::Object> obj1 = hs.NewHandle(c->AllocObject(soa.Self()));
65  ASSERT_TRUE(obj1.Get() != nullptr);
66  Handle<mirror::Object> obj2 = hs.NewHandle(c->AllocObject(soa.Self()));
67  ASSERT_TRUE(obj2.Get() != nullptr);
68  Handle<mirror::Object> obj3 = hs.NewHandle(c->AllocObject(soa.Self()));
69  ASSERT_TRUE(obj3.Get() != nullptr);
70
71  const IRTSegmentState cookie = kIRTFirstSegment;
72
73  CheckDump(&irt, 0, 0);
74
75  IndirectRef iref0 = (IndirectRef) 0x11110;
76  EXPECT_FALSE(irt.Remove(cookie, iref0)) << "unexpectedly successful removal";
77
78  // Add three, check, remove in the order in which they were added.
79  iref0 = irt.Add(cookie, obj0.Get());
80  EXPECT_TRUE(iref0 != nullptr);
81  CheckDump(&irt, 1, 1);
82  IndirectRef iref1 = irt.Add(cookie, obj1.Get());
83  EXPECT_TRUE(iref1 != nullptr);
84  CheckDump(&irt, 2, 2);
85  IndirectRef iref2 = irt.Add(cookie, obj2.Get());
86  EXPECT_TRUE(iref2 != nullptr);
87  CheckDump(&irt, 3, 3);
88
89  EXPECT_OBJ_PTR_EQ(obj0.Get(), irt.Get(iref0));
90  EXPECT_OBJ_PTR_EQ(obj1.Get(), irt.Get(iref1));
91  EXPECT_OBJ_PTR_EQ(obj2.Get(), irt.Get(iref2));
92
93  EXPECT_TRUE(irt.Remove(cookie, iref0));
94  CheckDump(&irt, 2, 2);
95  EXPECT_TRUE(irt.Remove(cookie, iref1));
96  CheckDump(&irt, 1, 1);
97  EXPECT_TRUE(irt.Remove(cookie, iref2));
98  CheckDump(&irt, 0, 0);
99
100  // Table should be empty now.
101  EXPECT_EQ(0U, irt.Capacity());
102
103  // Get invalid entry (off the end of the list).
104  EXPECT_TRUE(irt.Get(iref0) == nullptr);
105
106  // Add three, remove in the opposite order.
107  iref0 = irt.Add(cookie, obj0.Get());
108  EXPECT_TRUE(iref0 != nullptr);
109  iref1 = irt.Add(cookie, obj1.Get());
110  EXPECT_TRUE(iref1 != nullptr);
111  iref2 = irt.Add(cookie, obj2.Get());
112  EXPECT_TRUE(iref2 != nullptr);
113  CheckDump(&irt, 3, 3);
114
115  ASSERT_TRUE(irt.Remove(cookie, iref2));
116  CheckDump(&irt, 2, 2);
117  ASSERT_TRUE(irt.Remove(cookie, iref1));
118  CheckDump(&irt, 1, 1);
119  ASSERT_TRUE(irt.Remove(cookie, iref0));
120  CheckDump(&irt, 0, 0);
121
122  // Table should be empty now.
123  ASSERT_EQ(0U, irt.Capacity());
124
125  // Add three, remove middle / middle / bottom / top.  (Second attempt
126  // to remove middle should fail.)
127  iref0 = irt.Add(cookie, obj0.Get());
128  EXPECT_TRUE(iref0 != nullptr);
129  iref1 = irt.Add(cookie, obj1.Get());
130  EXPECT_TRUE(iref1 != nullptr);
131  iref2 = irt.Add(cookie, obj2.Get());
132  EXPECT_TRUE(iref2 != nullptr);
133  CheckDump(&irt, 3, 3);
134
135  ASSERT_EQ(3U, irt.Capacity());
136
137  ASSERT_TRUE(irt.Remove(cookie, iref1));
138  CheckDump(&irt, 2, 2);
139  ASSERT_FALSE(irt.Remove(cookie, iref1));
140  CheckDump(&irt, 2, 2);
141
142  // Get invalid entry (from hole).
143  EXPECT_TRUE(irt.Get(iref1) == nullptr);
144
145  ASSERT_TRUE(irt.Remove(cookie, iref2));
146  CheckDump(&irt, 1, 1);
147  ASSERT_TRUE(irt.Remove(cookie, iref0));
148  CheckDump(&irt, 0, 0);
149
150  // Table should be empty now.
151  ASSERT_EQ(0U, irt.Capacity());
152
153  // Add four entries.  Remove #1, add new entry, verify that table size
154  // is still 4 (i.e. holes are getting filled).  Remove #1 and #3, verify
155  // that we delete one and don't hole-compact the other.
156  iref0 = irt.Add(cookie, obj0.Get());
157  EXPECT_TRUE(iref0 != nullptr);
158  iref1 = irt.Add(cookie, obj1.Get());
159  EXPECT_TRUE(iref1 != nullptr);
160  iref2 = irt.Add(cookie, obj2.Get());
161  EXPECT_TRUE(iref2 != nullptr);
162  IndirectRef iref3 = irt.Add(cookie, obj3.Get());
163  EXPECT_TRUE(iref3 != nullptr);
164  CheckDump(&irt, 4, 4);
165
166  ASSERT_TRUE(irt.Remove(cookie, iref1));
167  CheckDump(&irt, 3, 3);
168
169  iref1 = irt.Add(cookie, obj1.Get());
170  EXPECT_TRUE(iref1 != nullptr);
171
172  ASSERT_EQ(4U, irt.Capacity()) << "hole not filled";
173  CheckDump(&irt, 4, 4);
174
175  ASSERT_TRUE(irt.Remove(cookie, iref1));
176  CheckDump(&irt, 3, 3);
177  ASSERT_TRUE(irt.Remove(cookie, iref3));
178  CheckDump(&irt, 2, 2);
179
180  ASSERT_EQ(3U, irt.Capacity()) << "should be 3 after two deletions";
181
182  ASSERT_TRUE(irt.Remove(cookie, iref2));
183  CheckDump(&irt, 1, 1);
184  ASSERT_TRUE(irt.Remove(cookie, iref0));
185  CheckDump(&irt, 0, 0);
186
187  ASSERT_EQ(0U, irt.Capacity()) << "not empty after split remove";
188
189  // Add an entry, remove it, add a new entry, and try to use the original
190  // iref.  They have the same slot number but are for different objects.
191  // With the extended checks in place, this should fail.
192  iref0 = irt.Add(cookie, obj0.Get());
193  EXPECT_TRUE(iref0 != nullptr);
194  CheckDump(&irt, 1, 1);
195  ASSERT_TRUE(irt.Remove(cookie, iref0));
196  CheckDump(&irt, 0, 0);
197  iref1 = irt.Add(cookie, obj1.Get());
198  EXPECT_TRUE(iref1 != nullptr);
199  CheckDump(&irt, 1, 1);
200  ASSERT_FALSE(irt.Remove(cookie, iref0)) << "mismatched del succeeded";
201  CheckDump(&irt, 1, 1);
202  ASSERT_TRUE(irt.Remove(cookie, iref1)) << "switched del failed";
203  ASSERT_EQ(0U, irt.Capacity()) << "switching del not empty";
204  CheckDump(&irt, 0, 0);
205
206  // Same as above, but with the same object.  A more rigorous checker
207  // (e.g. with slot serialization) will catch this.
208  iref0 = irt.Add(cookie, obj0.Get());
209  EXPECT_TRUE(iref0 != nullptr);
210  CheckDump(&irt, 1, 1);
211  ASSERT_TRUE(irt.Remove(cookie, iref0));
212  CheckDump(&irt, 0, 0);
213  iref1 = irt.Add(cookie, obj0.Get());
214  EXPECT_TRUE(iref1 != nullptr);
215  CheckDump(&irt, 1, 1);
216  if (iref0 != iref1) {
217    // Try 0, should not work.
218    ASSERT_FALSE(irt.Remove(cookie, iref0)) << "temporal del succeeded";
219  }
220  ASSERT_TRUE(irt.Remove(cookie, iref1)) << "temporal cleanup failed";
221  ASSERT_EQ(0U, irt.Capacity()) << "temporal del not empty";
222  CheckDump(&irt, 0, 0);
223
224  // null isn't a valid iref.
225  ASSERT_TRUE(irt.Get(nullptr) == nullptr);
226
227  // Stale lookup.
228  iref0 = irt.Add(cookie, obj0.Get());
229  EXPECT_TRUE(iref0 != nullptr);
230  CheckDump(&irt, 1, 1);
231  ASSERT_TRUE(irt.Remove(cookie, iref0));
232  EXPECT_TRUE(irt.Get(iref0) == nullptr) << "stale lookup succeeded";
233  CheckDump(&irt, 0, 0);
234
235  // Test table resizing.
236  // These ones fit...
237  static const size_t kTableInitial = kTableMax / 2;
238  IndirectRef manyRefs[kTableInitial];
239  for (size_t i = 0; i < kTableInitial; i++) {
240    manyRefs[i] = irt.Add(cookie, obj0.Get());
241    ASSERT_TRUE(manyRefs[i] != nullptr) << "Failed adding " << i;
242    CheckDump(&irt, i + 1, 1);
243  }
244  // ...this one causes overflow.
245  iref0 = irt.Add(cookie, obj0.Get());
246  ASSERT_TRUE(iref0 != nullptr);
247  ASSERT_EQ(kTableInitial + 1, irt.Capacity());
248  CheckDump(&irt, kTableInitial + 1, 1);
249
250  for (size_t i = 0; i < kTableInitial; i++) {
251    ASSERT_TRUE(irt.Remove(cookie, manyRefs[i])) << "failed removing " << i;
252    CheckDump(&irt, kTableInitial - i, 1);
253  }
254  // Because of removal order, should have 11 entries, 10 of them holes.
255  ASSERT_EQ(kTableInitial + 1, irt.Capacity());
256
257  ASSERT_TRUE(irt.Remove(cookie, iref0)) << "multi-remove final failed";
258
259  ASSERT_EQ(0U, irt.Capacity()) << "multi-del not empty";
260  CheckDump(&irt, 0, 0);
261}
262
263TEST_F(IndirectReferenceTableTest, Holes) {
264  // Test the explicitly named cases from the IRT implementation:
265  //
266  // 1) Segment with holes (current_num_holes_ > 0), push new segment, add/remove reference
267  // 2) Segment with holes (current_num_holes_ > 0), pop segment, add/remove reference
268  // 3) Segment with holes (current_num_holes_ > 0), push new segment, pop segment, add/remove
269  //    reference
270  // 4) Empty segment, push new segment, create a hole, pop a segment, add/remove a reference
271  // 5) Base segment, push new segment, create a hole, pop a segment, push new segment, add/remove
272  //    reference
273
274  ScopedObjectAccess soa(Thread::Current());
275  static const size_t kTableMax = 10;
276
277  mirror::Class* c = class_linker_->FindSystemClass(soa.Self(), "Ljava/lang/Object;");
278  StackHandleScope<5> hs(soa.Self());
279  ASSERT_TRUE(c != nullptr);
280  Handle<mirror::Object> obj0 = hs.NewHandle(c->AllocObject(soa.Self()));
281  ASSERT_TRUE(obj0.Get() != nullptr);
282  Handle<mirror::Object> obj1 = hs.NewHandle(c->AllocObject(soa.Self()));
283  ASSERT_TRUE(obj1.Get() != nullptr);
284  Handle<mirror::Object> obj2 = hs.NewHandle(c->AllocObject(soa.Self()));
285  ASSERT_TRUE(obj2.Get() != nullptr);
286  Handle<mirror::Object> obj3 = hs.NewHandle(c->AllocObject(soa.Self()));
287  ASSERT_TRUE(obj3.Get() != nullptr);
288  Handle<mirror::Object> obj4 = hs.NewHandle(c->AllocObject(soa.Self()));
289  ASSERT_TRUE(obj4.Get() != nullptr);
290
291  std::string error_msg;
292
293  // 1) Segment with holes (current_num_holes_ > 0), push new segment, add/remove reference.
294  {
295    IndirectReferenceTable irt(kTableMax,
296                               kGlobal,
297                               IndirectReferenceTable::ResizableCapacity::kNo,
298                               &error_msg);
299    ASSERT_TRUE(irt.IsValid()) << error_msg;
300
301    const IRTSegmentState cookie0 = kIRTFirstSegment;
302
303    CheckDump(&irt, 0, 0);
304
305    IndirectRef iref0 = irt.Add(cookie0, obj0.Get());
306    IndirectRef iref1 = irt.Add(cookie0, obj1.Get());
307    IndirectRef iref2 = irt.Add(cookie0, obj2.Get());
308
309    EXPECT_TRUE(irt.Remove(cookie0, iref1));
310
311    // New segment.
312    const IRTSegmentState cookie1 = irt.GetSegmentState();
313
314    IndirectRef iref3 = irt.Add(cookie1, obj3.Get());
315
316    // Must not have filled the previous hole.
317    EXPECT_EQ(irt.Capacity(), 4u);
318    EXPECT_TRUE(irt.Get(iref1) == nullptr);
319    CheckDump(&irt, 3, 3);
320
321    UNUSED(iref0, iref1, iref2, iref3);
322  }
323
324  // 2) Segment with holes (current_num_holes_ > 0), pop segment, add/remove reference
325  {
326    IndirectReferenceTable irt(kTableMax,
327                               kGlobal,
328                               IndirectReferenceTable::ResizableCapacity::kNo,
329                               &error_msg);
330    ASSERT_TRUE(irt.IsValid()) << error_msg;
331
332    const IRTSegmentState cookie0 = kIRTFirstSegment;
333
334    CheckDump(&irt, 0, 0);
335
336    IndirectRef iref0 = irt.Add(cookie0, obj0.Get());
337
338    // New segment.
339    const IRTSegmentState cookie1 = irt.GetSegmentState();
340
341    IndirectRef iref1 = irt.Add(cookie1, obj1.Get());
342    IndirectRef iref2 = irt.Add(cookie1, obj2.Get());
343    IndirectRef iref3 = irt.Add(cookie1, obj3.Get());
344
345    EXPECT_TRUE(irt.Remove(cookie1, iref2));
346
347    // Pop segment.
348    irt.SetSegmentState(cookie1);
349
350    IndirectRef iref4 = irt.Add(cookie1, obj4.Get());
351
352    EXPECT_EQ(irt.Capacity(), 2u);
353    EXPECT_TRUE(irt.Get(iref2) == nullptr);
354    CheckDump(&irt, 2, 2);
355
356    UNUSED(iref0, iref1, iref2, iref3, iref4);
357  }
358
359  // 3) Segment with holes (current_num_holes_ > 0), push new segment, pop segment, add/remove
360  //    reference.
361  {
362    IndirectReferenceTable irt(kTableMax,
363                               kGlobal,
364                               IndirectReferenceTable::ResizableCapacity::kNo,
365                               &error_msg);
366    ASSERT_TRUE(irt.IsValid()) << error_msg;
367
368    const IRTSegmentState cookie0 = kIRTFirstSegment;
369
370    CheckDump(&irt, 0, 0);
371
372    IndirectRef iref0 = irt.Add(cookie0, obj0.Get());
373
374    // New segment.
375    const IRTSegmentState cookie1 = irt.GetSegmentState();
376
377    IndirectRef iref1 = irt.Add(cookie1, obj1.Get());
378    IndirectRef iref2 = irt.Add(cookie1, obj2.Get());
379
380    EXPECT_TRUE(irt.Remove(cookie1, iref1));
381
382    // New segment.
383    const IRTSegmentState cookie2 = irt.GetSegmentState();
384
385    IndirectRef iref3 = irt.Add(cookie2, obj3.Get());
386
387    // Pop segment.
388    irt.SetSegmentState(cookie2);
389
390    IndirectRef iref4 = irt.Add(cookie1, obj4.Get());
391
392    EXPECT_EQ(irt.Capacity(), 3u);
393    EXPECT_TRUE(irt.Get(iref1) == nullptr);
394    CheckDump(&irt, 3, 3);
395
396    UNUSED(iref0, iref1, iref2, iref3, iref4);
397  }
398
399  // 4) Empty segment, push new segment, create a hole, pop a segment, add/remove a reference.
400  {
401    IndirectReferenceTable irt(kTableMax,
402                               kGlobal,
403                               IndirectReferenceTable::ResizableCapacity::kNo,
404                               &error_msg);
405    ASSERT_TRUE(irt.IsValid()) << error_msg;
406
407    const IRTSegmentState cookie0 = kIRTFirstSegment;
408
409    CheckDump(&irt, 0, 0);
410
411    IndirectRef iref0 = irt.Add(cookie0, obj0.Get());
412
413    // New segment.
414    const IRTSegmentState cookie1 = irt.GetSegmentState();
415
416    IndirectRef iref1 = irt.Add(cookie1, obj1.Get());
417    EXPECT_TRUE(irt.Remove(cookie1, iref1));
418
419    // Emptied segment, push new one.
420    const IRTSegmentState cookie2 = irt.GetSegmentState();
421
422    IndirectRef iref2 = irt.Add(cookie1, obj1.Get());
423    IndirectRef iref3 = irt.Add(cookie1, obj2.Get());
424    IndirectRef iref4 = irt.Add(cookie1, obj3.Get());
425
426    EXPECT_TRUE(irt.Remove(cookie1, iref3));
427
428    // Pop segment.
429    UNUSED(cookie2);
430    irt.SetSegmentState(cookie1);
431
432    IndirectRef iref5 = irt.Add(cookie1, obj4.Get());
433
434    EXPECT_EQ(irt.Capacity(), 2u);
435    EXPECT_TRUE(irt.Get(iref3) == nullptr);
436    CheckDump(&irt, 2, 2);
437
438    UNUSED(iref0, iref1, iref2, iref3, iref4, iref5);
439  }
440
441  // 5) Base segment, push new segment, create a hole, pop a segment, push new segment, add/remove
442  //    reference
443  {
444    IndirectReferenceTable irt(kTableMax,
445                               kGlobal,
446                               IndirectReferenceTable::ResizableCapacity::kNo,
447                               &error_msg);
448    ASSERT_TRUE(irt.IsValid()) << error_msg;
449
450    const IRTSegmentState cookie0 = kIRTFirstSegment;
451
452    CheckDump(&irt, 0, 0);
453
454    IndirectRef iref0 = irt.Add(cookie0, obj0.Get());
455
456    // New segment.
457    const IRTSegmentState cookie1 = irt.GetSegmentState();
458
459    IndirectRef iref1 = irt.Add(cookie1, obj1.Get());
460    IndirectRef iref2 = irt.Add(cookie1, obj1.Get());
461    IndirectRef iref3 = irt.Add(cookie1, obj2.Get());
462
463    EXPECT_TRUE(irt.Remove(cookie1, iref2));
464
465    // Pop segment.
466    irt.SetSegmentState(cookie1);
467
468    // Push segment.
469    const IRTSegmentState cookie1_second = irt.GetSegmentState();
470    UNUSED(cookie1_second);
471
472    IndirectRef iref4 = irt.Add(cookie1, obj3.Get());
473
474    EXPECT_EQ(irt.Capacity(), 2u);
475    EXPECT_TRUE(irt.Get(iref3) == nullptr);
476    CheckDump(&irt, 2, 2);
477
478    UNUSED(iref0, iref1, iref2, iref3, iref4);
479  }
480}
481
482TEST_F(IndirectReferenceTableTest, Resize) {
483  ScopedObjectAccess soa(Thread::Current());
484  static const size_t kTableMax = 512;
485
486  mirror::Class* c = class_linker_->FindSystemClass(soa.Self(), "Ljava/lang/Object;");
487  StackHandleScope<1> hs(soa.Self());
488  ASSERT_TRUE(c != nullptr);
489  Handle<mirror::Object> obj0 = hs.NewHandle(c->AllocObject(soa.Self()));
490  ASSERT_TRUE(obj0.Get() != nullptr);
491
492  std::string error_msg;
493  IndirectReferenceTable irt(kTableMax,
494                             kLocal,
495                             IndirectReferenceTable::ResizableCapacity::kYes,
496                             &error_msg);
497  ASSERT_TRUE(irt.IsValid()) << error_msg;
498
499  CheckDump(&irt, 0, 0);
500  const IRTSegmentState cookie = kIRTFirstSegment;
501
502  for (size_t i = 0; i != kTableMax + 1; ++i) {
503    irt.Add(cookie, obj0.Get());
504  }
505
506  EXPECT_EQ(irt.Capacity(), kTableMax + 1);
507}
508
509}  // namespace art
510