TestIndirectRefTable.cpp revision d5c36b9040bd26a81219a7f399513526f9b46324 
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 */
31static 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) != kInvalidIndirectRefObject) {
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) != kInvalidIndirectRefObject) {
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
308bail:
309    dvmClearIndirectRefTable(&irt);
310    return result;
311}
312
313/*
314 * Test operations on a segmented table.
315 */
316static 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
465bail:
466    dvmClearIndirectRefTable(&irt);
467    return result;
468}
469
470
471/*
472 * Some quick tests.
473 */
474bool 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