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 /*
18 * Test the indirect reference table implementation.
19 */
20 #include "Dalvik.h"
21
22 #include <stdlib.h>
23
24 #ifndef NDEBUG
25
26 #define DBUG_MSG LOGV
27
28 /*
29 * Basic add/get/delete tests in an unsegmented table.
30 */
basicTest(void)31 static bool basicTest(void)
32 {
33 static const int kTableMax = 20;
34 IndirectRefTable irt;
35 IndirectRef iref0, iref1, iref2, iref3;
36 IndirectRef manyRefs[kTableMax];
37 ClassObject* clazz = dvmFindClass("Ljava/lang/Object;", NULL);
38 Object* obj0 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
39 Object* obj1 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
40 Object* obj2 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
41 Object* obj3 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
42 const u4 cookie = IRT_FIRST_SEGMENT;
43 bool result = false;
44
45 if (!dvmInitIndirectRefTable(&irt, kTableMax/2, kTableMax,
46 kIndirectKindGlobal))
47 {
48 return false;
49 }
50
51 iref0 = (IndirectRef) 0x11110;
52 if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref0)) {
53 LOGE("unexpectedly successful removal\n");
54 goto bail;
55 }
56
57 /*
58 * Add three, check, remove in the order in which they were added.
59 */
60 DBUG_MSG("+++ START fifo\n");
61 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
62 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
63 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
64 if (iref0 == NULL || iref1 == NULL || iref2 == NULL) {
65 LOGE("trivial add1 failed\n");
66 goto bail;
67 }
68
69 if (dvmGetFromIndirectRefTable(&irt, iref0) != obj0 ||
70 dvmGetFromIndirectRefTable(&irt, iref1) != obj1 ||
71 dvmGetFromIndirectRefTable(&irt, iref2) != obj2)
72 {
73 LOGE("objects don't match expected values %p %p %p vs. %p %p %p\n",
74 dvmGetFromIndirectRefTable(&irt, iref0),
75 dvmGetFromIndirectRefTable(&irt, iref1),
76 dvmGetFromIndirectRefTable(&irt, iref2),
77 obj0, obj1, obj2);
78 goto bail;
79 } else {
80 DBUG_MSG("+++ obj1=%p --> iref1=%p\n", obj1, iref1);
81 }
82
83 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref0) ||
84 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref1) ||
85 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref2))
86 {
87 LOGE("fifo deletion failed\n");
88 goto bail;
89 }
90
91 /* table should be empty now */
92 if (dvmIndirectRefTableEntries(&irt) != 0) {
93 LOGE("fifo del not empty\n");
94 goto bail;
95 }
96
97 /* get invalid entry (off the end of the list) */
98 if (dvmGetFromIndirectRefTable(&irt, iref0) != NULL) {
99 LOGE("stale entry get succeeded unexpectedly\n");
100 goto bail;
101 }
102
103 /*
104 * Add three, remove in the opposite order.
105 */
106 DBUG_MSG("+++ START lifo\n");
107 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
108 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
109 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
110 if (iref0 == NULL || iref1 == NULL || iref2 == NULL) {
111 LOGE("trivial add2 failed\n");
112 goto bail;
113 }
114
115 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2) ||
116 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref1) ||
117 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref0))
118 {
119 LOGE("lifo deletion failed\n");
120 goto bail;
121 }
122
123 /* table should be empty now */
124 if (dvmIndirectRefTableEntries(&irt) != 0) {
125 LOGE("lifo del not empty\n");
126 goto bail;
127 }
128
129 /*
130 * Add three, remove middle / middle / bottom / top. (Second attempt
131 * to remove middle should fail.)
132 */
133 DBUG_MSG("+++ START unorder\n");
134 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
135 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
136 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
137 if (iref0 == NULL || iref1 == NULL || iref2 == NULL) {
138 LOGE("trivial add3 failed\n");
139 goto bail;
140 }
141
142 if (dvmIndirectRefTableEntries(&irt) != 3) {
143 LOGE("expected 3 entries, found %d\n",
144 dvmIndirectRefTableEntries(&irt));
145 goto bail;
146 }
147
148 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref1) ||
149 dvmRemoveFromIndirectRefTable(&irt, cookie, iref1))
150 {
151 LOGE("unorder deletion1 failed\n");
152 goto bail;
153 }
154
155 /* get invalid entry (from hole) */
156 if (dvmGetFromIndirectRefTable(&irt, iref1) != NULL) {
157 LOGE("hole get succeeded unexpectedly\n");
158 goto bail;
159 }
160
161 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2) ||
162 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref0))
163 {
164 LOGE("unorder deletion2 failed\n");
165 goto bail;
166 }
167
168 /* table should be empty now */
169 if (dvmIndirectRefTableEntries(&irt) != 0) {
170 LOGE("unorder del not empty\n");
171 goto bail;
172 }
173
174 /*
175 * Add four entries. Remove #1, add new entry, verify that table size
176 * is still 4 (i.e. holes are getting filled). Remove #1 and #3, verify
177 * that we delete one and don't hole-compact the other.
178 */
179 DBUG_MSG("+++ START hole fill\n");
180 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
181 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
182 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
183 iref3 = dvmAddToIndirectRefTable(&irt, cookie, obj3);
184 if (iref0 == NULL || iref1 == NULL || iref2 == NULL || iref3 == NULL) {
185 LOGE("trivial add4 failed\n");
186 goto bail;
187 }
188 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref1)) {
189 LOGE("remove 1 of 4 failed\n");
190 goto bail;
191 }
192 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
193 if (dvmIndirectRefTableEntries(&irt) != 4) {
194 LOGE("hole not filled\n");
195 goto bail;
196 }
197 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref1) ||
198 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref3))
199 {
200 LOGE("remove 1/3 failed\n");
201 goto bail;
202 }
203 if (dvmIndirectRefTableEntries(&irt) != 3) {
204 LOGE("should be 3 after two deletions\n");
205 goto bail;
206 }
207 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2) ||
208 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref0))
209 {
210 LOGE("remove 2/0 failed\n");
211 goto bail;
212 }
213 if (dvmIndirectRefTableEntries(&irt) != 0) {
214 LOGE("not empty after split remove\n");
215 goto bail;
216 }
217
218 /*
219 * Add an entry, remove it, add a new entry, and try to use the original
220 * iref. They have the same slot number but are for different objects.
221 * With the extended checks in place, this should fail.
222 */
223 DBUG_MSG("+++ START switched\n");
224 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
225 dvmRemoveFromIndirectRefTable(&irt, cookie, iref0);
226 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
227 if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref0)) {
228 LOGE("mismatched del succeeded (%p vs %p)\n", iref0, iref1);
229 goto bail;
230 }
231 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref1)) {
232 LOGE("switched del failed\n");
233 goto bail;
234 }
235 if (dvmIndirectRefTableEntries(&irt) != 0) {
236 LOGE("switching del not empty\n");
237 goto bail;
238 }
239
240 /*
241 * Same as above, but with the same object. A more rigorous checker
242 * (e.g. with slot serialization) will catch this.
243 */
244 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
245 dvmRemoveFromIndirectRefTable(&irt, cookie, iref0);
246 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
247 if (iref0 != iref1) {
248 if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref0)) {
249 LOGE("temporal del succeeded (%p vs %p)\n", iref0, iref1);
250 goto bail;
251 }
252 } else {
253 dvmRemoveFromIndirectRefTable(&irt, cookie, iref1);
254 }
255 if (dvmIndirectRefTableEntries(&irt) != 0) {
256 LOGE("temporal del not empty\n");
257 goto bail;
258 }
259
260 /*
261 * Test table overflow.
262 */
263 DBUG_MSG("+++ START overflow\n");
264 int i;
265 for (i = 0; i < kTableMax; i++) {
266 manyRefs[i] = dvmAddToIndirectRefTable(&irt, cookie, obj0);
267 if (manyRefs[i] == NULL) {
268 LOGE("Failed adding %d of %d\n", i, kTableMax);
269 goto bail;
270 }
271 }
272 if (dvmAddToIndirectRefTable(&irt, cookie, obj0) != NULL) {
273 LOGE("Table overflow succeeded\n");
274 goto bail;
275 }
276 if (dvmIndirectRefTableEntries(&irt) != (size_t)kTableMax) {
277 LOGE("Expected %d entries, found %d\n",
278 kTableMax, dvmIndirectRefTableEntries(&irt));
279 goto bail;
280 }
281 for (i = 0; i < kTableMax-1; i++) {
282 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, manyRefs[i])) {
283 LOGE("multi-remove failed at %d\n", i);
284 goto bail;
285 }
286 }
287 /* because of removal order, should have 20 entries, 19 of them holes */
288 if (dvmIndirectRefTableEntries(&irt) != (size_t)kTableMax) {
289 LOGE("Expected %d entries (with holes), found %d\n",
290 kTableMax, dvmIndirectRefTableEntries(&irt));
291 goto bail;
292 }
293 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, manyRefs[kTableMax-1])) {
294 LOGE("multi-remove final failed\n");
295 goto bail;
296 }
297 if (dvmIndirectRefTableEntries(&irt) != 0) {
298 LOGE("multi-del not empty\n");
299 goto bail;
300 }
301
302 DBUG_MSG("+++ basic test complete\n");
303 result = true;
304
305 bail:
306 dvmClearIndirectRefTable(&irt);
307 return result;
308 }
309
310 /*
311 * Test operations on a segmented table.
312 */
segmentTest(void)313 static bool segmentTest(void)
314 {
315 static const int kTableMax = 20;
316 IndirectRefTable irt;
317 IndirectRef iref0, iref1, iref2, iref3;
318 ClassObject* clazz = dvmFindClass("Ljava/lang/Object;", NULL);
319 Object* obj0 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
320 Object* obj1 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
321 Object* obj2 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
322 Object* obj3 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
323 u4 cookie;
324 u4 segmentState[4];
325 bool result = false;
326
327 if (!dvmInitIndirectRefTable(&irt, kTableMax, kTableMax,
328 kIndirectKindLocal))
329 {
330 return false;
331 }
332 cookie = segmentState[0] = IRT_FIRST_SEGMENT;
333 DBUG_MSG("+++ objs %p %p %p %p\n", obj0, obj1, obj2, obj3);
334
335 /*
336 * Push two, create new segment, push two more, try to get all four,
337 * try to delete all 4. All four should be accessible, but only the
338 * last two should be deletable.
339 */
340 DBUG_MSG("+++ START basic segment\n");
341 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
342 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
343 cookie = segmentState[1] = dvmPushIndirectRefTableSegment(&irt);
344 DBUG_MSG("+++ pushed, cookie is 0x%08x\n", cookie);
345 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
346 iref3 = dvmAddToIndirectRefTable(&irt, cookie, obj3);
347
348 if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref0) ||
349 dvmRemoveFromIndirectRefTable(&irt, cookie, iref1))
350 {
351 LOGE("removed values from earlier segment\n");
352 goto bail;
353 }
354 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2) ||
355 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref3))
356 {
357 LOGE("unable to remove values from current segment\n");
358 goto bail;
359 }
360 if (dvmIndirectRefTableEntries(&irt) != 2) {
361 LOGE("wrong total entries\n");
362 goto bail;
363 }
364 dvmPopIndirectRefTableSegment(&irt, segmentState[1]);
365 cookie = segmentState[0];
366 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref0) ||
367 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref1))
368 {
369 LOGE("unable to remove values from first segment\n");
370 goto bail;
371 }
372 if (dvmIndirectRefTableEntries(&irt) != 0) {
373 LOGE("basic push/pop not empty\n");
374 goto bail;
375 }
376
377 /*
378 * Push two, delete first, segment, push two more, pop segment, verify
379 * the last two are no longer present and hole count is right. The
380 * adds after the segment pop should not be filling in the hole.
381 */
382 DBUG_MSG("+++ START segment pop\n");
383 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
384 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
385 dvmRemoveFromIndirectRefTable(&irt, cookie, iref0);
386 cookie = segmentState[1] = dvmPushIndirectRefTableSegment(&irt);
387 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
388 iref3 = dvmAddToIndirectRefTable(&irt, cookie, obj3);
389 dvmPopIndirectRefTableSegment(&irt, segmentState[1]);
390 cookie = segmentState[0];
391 if (dvmIndirectRefTableEntries(&irt) != 2) {
392 LOGE("wrong total entries after pop\n");
393 goto bail;
394 }
395 dvmRemoveFromIndirectRefTable(&irt, cookie, iref1);
396 if (dvmIndirectRefTableEntries(&irt) != 0) {
397 LOGE("not back to zero after pop + del\n");
398 goto bail;
399 }
400
401 /*
402 * Multiple segments, some empty.
403 */
404 DBUG_MSG("+++ START multiseg\n");
405 iref0 = dvmAppendToIndirectRefTable(&irt, cookie, obj0);
406 iref1 = dvmAppendToIndirectRefTable(&irt, cookie, obj1);
407 cookie = segmentState[1] = dvmPushIndirectRefTableSegment(&irt);
408 cookie = segmentState[2] = dvmPushIndirectRefTableSegment(&irt);
409 iref3 = dvmAppendToIndirectRefTable(&irt, cookie, obj3);
410 iref2 = dvmAppendToIndirectRefTable(&irt, cookie, obj2);
411 dvmRemoveFromIndirectRefTable(&irt, cookie, iref3);
412 cookie = segmentState[3] = dvmPushIndirectRefTableSegment(&irt);
413 iref3 = dvmAppendToIndirectRefTable(&irt, cookie, obj3);
414
415 if (dvmGetFromIndirectRefTable(&irt, iref0) != obj0 ||
416 dvmGetFromIndirectRefTable(&irt, iref1) != obj1 ||
417 dvmGetFromIndirectRefTable(&irt, iref2) != obj2 ||
418 dvmGetFromIndirectRefTable(&irt, iref3) != obj3)
419 {
420 LOGE("Unable to retrieve all multiseg objects\n");
421 goto bail;
422 }
423
424 dvmDumpIndirectRefTable(&irt, "test");
425
426 //int i;
427 //for (i = 0; i < sizeof(segmentState) / sizeof(segmentState[0]); i++) {
428 // DBUG_MSG("+++ segment %d = 0x%08x\n", i, segmentState[i]);
429 //}
430
431 dvmRemoveFromIndirectRefTable(&irt, cookie, iref3);
432 if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref2)) {
433 LOGE("multiseg del2 worked\n");
434 goto bail;
435 }
436 dvmPopIndirectRefTableSegment(&irt, segmentState[3]);
437 cookie = segmentState[2];
438 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2)) {
439 LOGE("multiseg del2b failed (cookie=0x%08x ref=%p)\n", cookie, iref2);
440 goto bail;
441 }
442 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
443
444 /* pop two off at once */
445 dvmPopIndirectRefTableSegment(&irt, segmentState[1]);
446 cookie = segmentState[0];
447
448 if (dvmIndirectRefTableEntries(&irt) != 2) {
449 LOGE("Unexpected entry count in multiseg\n");
450 goto bail;
451 }
452 dvmRemoveFromIndirectRefTable(&irt, cookie, iref0);
453 dvmRemoveFromIndirectRefTable(&irt, cookie, iref1);
454 if (dvmIndirectRefTableEntries(&irt) != 0) {
455 LOGE("Unexpected entry count at multiseg end\n");
456 goto bail;
457 }
458
459 DBUG_MSG("+++ segment test complete\n");
460 result = true;
461
462 bail:
463 dvmClearIndirectRefTable(&irt);
464 return result;
465 }
466
467
468 /*
469 * Some quick tests.
470 */
dvmTestIndirectRefTable(void)471 bool dvmTestIndirectRefTable(void)
472 {
473 if (!basicTest()) {
474 LOGE("IRT basic test failed\n");
475 return false;
476 }
477 if (!segmentTest()) {
478 LOGE("IRT segment test failed\n");
479 return false;
480 }
481
482 return true;
483 }
484
485 #endif /*NDEBUG*/
486