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 /* try 0, should not work */
249 if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref0)) {
250 LOGE("temporal del succeeded (%p vs %p)\n", iref0, iref1);
251 goto bail;
252 }
253 }
254 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref1)) {
255 LOGE("temporal cleanup failed\n");
256 goto bail;
257 }
258 if (dvmIndirectRefTableEntries(&irt) != 0) {
259 LOGE("temporal del not empty\n");
260 goto bail;
261 }
262
263 /*
264 * Test table overflow.
265 */
266 DBUG_MSG("+++ START overflow\n");
267 int i;
268 for (i = 0; i < kTableMax; i++) {
269 manyRefs[i] = dvmAddToIndirectRefTable(&irt, cookie, obj0);
270 if (manyRefs[i] == NULL) {
271 LOGE("Failed adding %d of %d\n", i, kTableMax);
272 goto bail;
273 }
274 }
275 if (dvmAddToIndirectRefTable(&irt, cookie, obj0) != NULL) {
276 LOGE("Table overflow succeeded\n");
277 goto bail;
278 }
279 if (dvmIndirectRefTableEntries(&irt) != (size_t)kTableMax) {
280 LOGE("Expected %d entries, found %d\n",
281 kTableMax, dvmIndirectRefTableEntries(&irt));
282 goto bail;
283 }
284 for (i = 0; i < kTableMax-1; i++) {
285 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, manyRefs[i])) {
286 LOGE("multi-remove failed at %d\n", i);
287 goto bail;
288 }
289 }
290 /* because of removal order, should have 20 entries, 19 of them holes */
291 if (dvmIndirectRefTableEntries(&irt) != (size_t)kTableMax) {
292 LOGE("Expected %d entries (with holes), found %d\n",
293 kTableMax, dvmIndirectRefTableEntries(&irt));
294 goto bail;
295 }
296 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, manyRefs[kTableMax-1])) {
297 LOGE("multi-remove final failed\n");
298 goto bail;
299 }
300 if (dvmIndirectRefTableEntries(&irt) != 0) {
301 LOGE("multi-del not empty\n");
302 goto bail;
303 }
304
305 DBUG_MSG("+++ basic test complete\n");
306 result = true;
307
308 bail:
309 dvmClearIndirectRefTable(&irt);
310 return result;
311 }
312
313 /*
314 * Test operations on a segmented table.
315 */
segmentTest(void)316 static bool segmentTest(void)
317 {
318 static const int kTableMax = 20;
319 IndirectRefTable irt;
320 IndirectRef iref0, iref1, iref2, iref3;
321 ClassObject* clazz = dvmFindClass("Ljava/lang/Object;", NULL);
322 Object* obj0 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
323 Object* obj1 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
324 Object* obj2 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
325 Object* obj3 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
326 u4 cookie;
327 u4 segmentState[4];
328 bool result = false;
329
330 if (!dvmInitIndirectRefTable(&irt, kTableMax, kTableMax,
331 kIndirectKindLocal))
332 {
333 return false;
334 }
335 cookie = segmentState[0] = IRT_FIRST_SEGMENT;
336 DBUG_MSG("+++ objs %p %p %p %p\n", obj0, obj1, obj2, obj3);
337
338 /*
339 * Push two, create new segment, push two more, try to get all four,
340 * try to delete all 4. All four should be accessible, but only the
341 * last two should be deletable.
342 */
343 DBUG_MSG("+++ START basic segment\n");
344 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
345 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
346 cookie = segmentState[1] = dvmPushIndirectRefTableSegment(&irt);
347 DBUG_MSG("+++ pushed, cookie is 0x%08x\n", cookie);
348 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
349 iref3 = dvmAddToIndirectRefTable(&irt, cookie, obj3);
350
351 if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref0) ||
352 dvmRemoveFromIndirectRefTable(&irt, cookie, iref1))
353 {
354 LOGE("removed values from earlier segment\n");
355 goto bail;
356 }
357 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2) ||
358 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref3))
359 {
360 LOGE("unable to remove values from current segment\n");
361 goto bail;
362 }
363 if (dvmIndirectRefTableEntries(&irt) != 2) {
364 LOGE("wrong total entries\n");
365 goto bail;
366 }
367 dvmPopIndirectRefTableSegment(&irt, segmentState[1]);
368 cookie = segmentState[0];
369 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref0) ||
370 !dvmRemoveFromIndirectRefTable(&irt, cookie, iref1))
371 {
372 LOGE("unable to remove values from first segment\n");
373 goto bail;
374 }
375 if (dvmIndirectRefTableEntries(&irt) != 0) {
376 LOGE("basic push/pop not empty\n");
377 goto bail;
378 }
379
380 /*
381 * Push two, delete first, segment, push two more, pop segment, verify
382 * the last two are no longer present and hole count is right. The
383 * adds after the segment pop should not be filling in the hole.
384 */
385 DBUG_MSG("+++ START segment pop\n");
386 iref0 = dvmAddToIndirectRefTable(&irt, cookie, obj0);
387 iref1 = dvmAddToIndirectRefTable(&irt, cookie, obj1);
388 dvmRemoveFromIndirectRefTable(&irt, cookie, iref0);
389 cookie = segmentState[1] = dvmPushIndirectRefTableSegment(&irt);
390 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
391 iref3 = dvmAddToIndirectRefTable(&irt, cookie, obj3);
392 dvmPopIndirectRefTableSegment(&irt, segmentState[1]);
393 cookie = segmentState[0];
394 if (dvmIndirectRefTableEntries(&irt) != 2) {
395 LOGE("wrong total entries after pop\n");
396 goto bail;
397 }
398 dvmRemoveFromIndirectRefTable(&irt, cookie, iref1);
399 if (dvmIndirectRefTableEntries(&irt) != 0) {
400 LOGE("not back to zero after pop + del\n");
401 goto bail;
402 }
403
404 /*
405 * Multiple segments, some empty.
406 */
407 DBUG_MSG("+++ START multiseg\n");
408 iref0 = dvmAppendToIndirectRefTable(&irt, cookie, obj0);
409 iref1 = dvmAppendToIndirectRefTable(&irt, cookie, obj1);
410 cookie = segmentState[1] = dvmPushIndirectRefTableSegment(&irt);
411 cookie = segmentState[2] = dvmPushIndirectRefTableSegment(&irt);
412 iref3 = dvmAppendToIndirectRefTable(&irt, cookie, obj3);
413 iref2 = dvmAppendToIndirectRefTable(&irt, cookie, obj2);
414 dvmRemoveFromIndirectRefTable(&irt, cookie, iref3);
415 cookie = segmentState[3] = dvmPushIndirectRefTableSegment(&irt);
416 iref3 = dvmAppendToIndirectRefTable(&irt, cookie, obj3);
417
418 if (dvmGetFromIndirectRefTable(&irt, iref0) != obj0 ||
419 dvmGetFromIndirectRefTable(&irt, iref1) != obj1 ||
420 dvmGetFromIndirectRefTable(&irt, iref2) != obj2 ||
421 dvmGetFromIndirectRefTable(&irt, iref3) != obj3)
422 {
423 LOGE("Unable to retrieve all multiseg objects\n");
424 goto bail;
425 }
426
427 dvmDumpIndirectRefTable(&irt, "test");
428
429 //int i;
430 //for (i = 0; i < sizeof(segmentState) / sizeof(segmentState[0]); i++) {
431 // DBUG_MSG("+++ segment %d = 0x%08x\n", i, segmentState[i]);
432 //}
433
434 dvmRemoveFromIndirectRefTable(&irt, cookie, iref3);
435 if (dvmRemoveFromIndirectRefTable(&irt, cookie, iref2)) {
436 LOGE("multiseg del2 worked\n");
437 goto bail;
438 }
439 dvmPopIndirectRefTableSegment(&irt, segmentState[3]);
440 cookie = segmentState[2];
441 if (!dvmRemoveFromIndirectRefTable(&irt, cookie, iref2)) {
442 LOGE("multiseg del2b failed (cookie=0x%08x ref=%p)\n", cookie, iref2);
443 goto bail;
444 }
445 iref2 = dvmAddToIndirectRefTable(&irt, cookie, obj2);
446
447 /* pop two off at once */
448 dvmPopIndirectRefTableSegment(&irt, segmentState[1]);
449 cookie = segmentState[0];
450
451 if (dvmIndirectRefTableEntries(&irt) != 2) {
452 LOGE("Unexpected entry count in multiseg\n");
453 goto bail;
454 }
455 dvmRemoveFromIndirectRefTable(&irt, cookie, iref0);
456 dvmRemoveFromIndirectRefTable(&irt, cookie, iref1);
457 if (dvmIndirectRefTableEntries(&irt) != 0) {
458 LOGE("Unexpected entry count at multiseg end\n");
459 goto bail;
460 }
461
462 DBUG_MSG("+++ segment test complete\n");
463 result = true;
464
465 bail:
466 dvmClearIndirectRefTable(&irt);
467 return result;
468 }
469
470
471 /*
472 * Some quick tests.
473 */
dvmTestIndirectRefTable(void)474 bool dvmTestIndirectRefTable(void)
475 {
476 if (!basicTest()) {
477 LOGE("IRT basic test failed\n");
478 return false;
479 }
480 if (!segmentTest()) {
481 LOGE("IRT segment test failed\n");
482 return false;
483 }
484
485 return true;
486 }
487
488 #endif /*NDEBUG*/
489