TestIndirectRefTable.cpp revision ce0968340f9ddd54f20e38d4946bfd2ef8f1f343 
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    LOGI
27
28/*
29 * Basic add/get/delete tests in an unsegmented table.
30 */
31static bool basicTest()
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 (!irt.init(kTableMax/2, kTableMax, kIndirectKindGlobal)) {
46        return false;
47    }
48
49    iref0 = (IndirectRef) 0x11110;
50    if (irt.remove(cookie, iref0)) {
51        LOGE("unexpectedly successful removal");
52        goto bail;
53    }
54
55    /*
56     * Add three, check, remove in the order in which they were added.
57     */
58    DBUG_MSG("+++ START fifo\n");
59    iref0 = irt.add(cookie, obj0);
60    iref1 = irt.add(cookie, obj1);
61    iref2 = irt.add(cookie, obj2);
62    if (iref0 == NULL || iref1 == NULL || iref2 == NULL) {
63        LOGE("trivial add1 failed");
64        goto bail;
65    }
66
67    if (irt.get(iref0) != obj0 ||
68            irt.get(iref1) != obj1 ||
69            irt.get(iref2) != obj2) {
70        LOGE("objects don't match expected values %p %p %p vs. %p %p %p",
71                irt.get(iref0), irt.get(iref1), irt.get(iref2),
72                obj0, obj1, obj2);
73        goto bail;
74    } else {
75        DBUG_MSG("+++ obj1=%p --> iref1=%p\n", obj1, iref1);
76    }
77
78    if (!irt.remove(cookie, iref0) ||
79            !irt.remove(cookie, iref1) ||
80            !irt.remove(cookie, iref2))
81    {
82        LOGE("fifo deletion failed");
83        goto bail;
84    }
85
86    /* table should be empty now */
87    if (irt.capacity() != 0) {
88        LOGE("fifo del not empty");
89        goto bail;
90    }
91
92    /* get invalid entry (off the end of the list) */
93    if (irt.get(iref0) != kInvalidIndirectRefObject) {
94        LOGE("stale entry get succeeded unexpectedly");
95        goto bail;
96    }
97
98    /*
99     * Add three, remove in the opposite order.
100     */
101    DBUG_MSG("+++ START lifo\n");
102    iref0 = irt.add(cookie, obj0);
103    iref1 = irt.add(cookie, obj1);
104    iref2 = irt.add(cookie, obj2);
105    if (iref0 == NULL || iref1 == NULL || iref2 == NULL) {
106        LOGE("trivial add2 failed");
107        goto bail;
108    }
109
110    if (!irt.remove(cookie, iref2) ||
111            !irt.remove(cookie, iref1) ||
112            !irt.remove(cookie, iref0))
113    {
114        LOGE("lifo deletion failed");
115        goto bail;
116    }
117
118    /* table should be empty now */
119    if (irt.capacity() != 0) {
120        LOGE("lifo del not empty");
121        goto bail;
122    }
123
124    /*
125     * Add three, remove middle / middle / bottom / top.  (Second attempt
126     * to remove middle should fail.)
127     */
128    DBUG_MSG("+++ START unorder\n");
129    iref0 = irt.add(cookie, obj0);
130    iref1 = irt.add(cookie, obj1);
131    iref2 = irt.add(cookie, obj2);
132    if (iref0 == NULL || iref1 == NULL || iref2 == NULL) {
133        LOGE("trivial add3 failed");
134        goto bail;
135    }
136
137    if (irt.capacity() != 3) {
138        LOGE("expected 3 entries, found %d", irt.capacity());
139        goto bail;
140    }
141
142    if (!irt.remove(cookie, iref1) || irt.remove(cookie, iref1)) {
143        LOGE("unorder deletion1 failed");
144        goto bail;
145    }
146
147    /* get invalid entry (from hole) */
148    if (irt.get(iref1) != kInvalidIndirectRefObject) {
149        LOGE("hole get succeeded unexpectedly");
150        goto bail;
151    }
152
153    if (!irt.remove(cookie, iref2) || !irt.remove(cookie, iref0)) {
154        LOGE("unorder deletion2 failed");
155        goto bail;
156    }
157
158    /* table should be empty now */
159    if (irt.capacity() != 0) {
160        LOGE("unorder del not empty");
161        goto bail;
162    }
163
164    /*
165     * Add four entries.  Remove #1, add new entry, verify that table size
166     * is still 4 (i.e. holes are getting filled).  Remove #1 and #3, verify
167     * that we delete one and don't hole-compact the other.
168     */
169    DBUG_MSG("+++ START hole fill\n");
170    iref0 = irt.add(cookie, obj0);
171    iref1 = irt.add(cookie, obj1);
172    iref2 = irt.add(cookie, obj2);
173    iref3 = irt.add(cookie, obj3);
174    if (iref0 == NULL || iref1 == NULL || iref2 == NULL || iref3 == NULL) {
175        LOGE("trivial add4 failed");
176        goto bail;
177    }
178    if (!irt.remove(cookie, iref1)) {
179        LOGE("remove 1 of 4 failed");
180        goto bail;
181    }
182    iref1 = irt.add(cookie, obj1);
183    if (irt.capacity() != 4) {
184        LOGE("hole not filled");
185        goto bail;
186    }
187    if (!irt.remove(cookie, iref1) || !irt.remove(cookie, iref3)) {
188        LOGE("remove 1/3 failed");
189        goto bail;
190    }
191    if (irt.capacity() != 3) {
192        LOGE("should be 3 after two deletions");
193        goto bail;
194    }
195    if (!irt.remove(cookie, iref2) || !irt.remove(cookie, iref0)) {
196        LOGE("remove 2/0 failed");
197        goto bail;
198    }
199    if (irt.capacity() != 0) {
200        LOGE("not empty after split remove");
201        goto bail;
202    }
203
204    /*
205     * Add an entry, remove it, add a new entry, and try to use the original
206     * iref.  They have the same slot number but are for different objects.
207     * With the extended checks in place, this should fail.
208     */
209    DBUG_MSG("+++ START switched\n");
210    iref0 = irt.add(cookie, obj0);
211    irt.remove(cookie, iref0);
212    iref1 = irt.add(cookie, obj1);
213    if (irt.remove(cookie, iref0)) {
214        LOGE("mismatched del succeeded (%p vs %p)", iref0, iref1);
215        goto bail;
216    }
217    if (!irt.remove(cookie, iref1)) {
218        LOGE("switched del failed");
219        goto bail;
220    }
221    if (irt.capacity() != 0) {
222        LOGE("switching del not empty");
223        goto bail;
224    }
225
226    /*
227     * Same as above, but with the same object.  A more rigorous checker
228     * (e.g. with slot serialization) will catch this.
229     */
230    DBUG_MSG("+++ START switched same object\n");
231    iref0 = irt.add(cookie, obj0);
232    irt.remove(cookie, iref0);
233    iref1 = irt.add(cookie, obj0);
234    if (iref0 != iref1) {
235        /* try 0, should not work */
236        if (irt.remove(cookie, iref0)) {
237            LOGE("temporal del succeeded (%p vs %p)", iref0, iref1);
238            goto bail;
239        }
240    }
241    if (!irt.remove(cookie, iref1)) {
242        LOGE("temporal cleanup failed");
243        goto bail;
244    }
245    if (irt.capacity() != 0) {
246        LOGE("temporal del not empty");
247        goto bail;
248    }
249
250    DBUG_MSG("+++ START null lookup\n");
251    if (irt.get(NULL) != kInvalidIndirectRefObject) {
252        LOGE("null lookup succeeded");
253        goto bail;
254    }
255
256    DBUG_MSG("+++ START stale lookup\n");
257    iref0 = irt.add(cookie, obj0);
258    irt.remove(cookie, iref0);
259    if (irt.get(iref0) != kInvalidIndirectRefObject) {
260        LOGE("stale lookup succeeded");
261        goto bail;
262    }
263
264    /*
265     * Test table overflow.
266     */
267    DBUG_MSG("+++ START overflow\n");
268    int i;
269    for (i = 0; i < kTableMax; i++) {
270        manyRefs[i] = irt.add(cookie, obj0);
271        if (manyRefs[i] == NULL) {
272            LOGE("Failed adding %d of %d", i, kTableMax);
273            goto bail;
274        }
275    }
276    if (irt.add(cookie, obj0) != NULL) {
277        LOGE("Table overflow succeeded");
278        goto bail;
279    }
280    if (irt.capacity() != (size_t)kTableMax) {
281        LOGE("Expected %d entries, found %d", kTableMax, irt.capacity());
282        goto bail;
283    }
284    for (i = 0; i < kTableMax-1; i++) {
285        if (!irt.remove(cookie, manyRefs[i])) {
286            LOGE("multi-remove failed at %d", i);
287            goto bail;
288        }
289    }
290    /* because of removal order, should have 20 entries, 19 of them holes */
291    if (irt.capacity() != (size_t)kTableMax) {
292        LOGE("Expected %d entries (with holes), found %d",
293                kTableMax, irt.capacity());
294        goto bail;
295    }
296    if (!irt.remove(cookie, manyRefs[kTableMax-1])) {
297        LOGE("multi-remove final failed");
298        goto bail;
299    }
300    if (irt.capacity() != 0) {
301        LOGE("multi-del not empty");
302        goto bail;
303    }
304
305    DBUG_MSG("+++ basic test complete\n");
306    result = true;
307
308bail:
309    irt.destroy();
310    return result;
311}
312
313/*
314 * Some quick tests.
315 */
316bool dvmTestIndirectRefTable()
317{
318    if (!basicTest()) {
319        LOGE("IRT basic test failed");
320        return false;
321    }
322
323    return true;
324}
325
326#endif /*NDEBUG*/
327