TestIndirectRefTable.cpp revision c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2ef 
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#include <sys/time.h>
24
25#ifndef NDEBUG
26
27#define DBUG_MSG    ALOGI
28
29class Stopwatch {
30public:
31    Stopwatch() {
32        reset();
33    }
34
35    void reset() {
36        start_ = now();
37    }
38
39    float elapsedSeconds() {
40        return (now() - start_) * 0.000001f;
41    }
42
43private:
44    u8 start_;
45
46    static u8 now() {
47#ifdef HAVE_POSIX_CLOCKS
48        struct timespec tm;
49        clock_gettime(CLOCK_THREAD_CPUTIME_ID, &tm);
50        return tm.tv_sec * 1000000LL + tm.tv_nsec / 1000;
51#else
52        struct timeval tv;
53        gettimeofday(&tv, NULL);
54        return tv.tv_sec * 1000000LL + tv.tv_usec;
55#endif
56    }
57};
58
59/*
60 * Basic add/get/delete tests in an unsegmented table.
61 */
62static bool basicTest()
63{
64    static const int kTableMax = 20;
65    IndirectRefTable irt;
66    IndirectRef iref0, iref1, iref2, iref3;
67    IndirectRef manyRefs[kTableMax];
68    ClassObject* clazz = dvmFindClass("Ljava/lang/Object;", NULL);
69    Object* obj0 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
70    Object* obj1 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
71    Object* obj2 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
72    Object* obj3 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
73    const u4 cookie = IRT_FIRST_SEGMENT;
74    bool result = false;
75
76    if (!irt.init(kTableMax/2, kTableMax, kIndirectKindGlobal)) {
77        return false;
78    }
79
80    iref0 = (IndirectRef) 0x11110;
81    if (irt.remove(cookie, iref0)) {
82        ALOGE("unexpectedly successful removal");
83        goto bail;
84    }
85
86    /*
87     * Add three, check, remove in the order in which they were added.
88     */
89    DBUG_MSG("+++ START fifo\n");
90    iref0 = irt.add(cookie, obj0);
91    iref1 = irt.add(cookie, obj1);
92    iref2 = irt.add(cookie, obj2);
93    if (iref0 == NULL || iref1 == NULL || iref2 == NULL) {
94        ALOGE("trivial add1 failed");
95        goto bail;
96    }
97
98    if (irt.get(iref0) != obj0 ||
99            irt.get(iref1) != obj1 ||
100            irt.get(iref2) != obj2) {
101        ALOGE("objects don't match expected values %p %p %p vs. %p %p %p",
102                irt.get(iref0), irt.get(iref1), irt.get(iref2),
103                obj0, obj1, obj2);
104        goto bail;
105    } else {
106        DBUG_MSG("+++ obj1=%p --> iref1=%p\n", obj1, iref1);
107    }
108
109    if (!irt.remove(cookie, iref0) ||
110            !irt.remove(cookie, iref1) ||
111            !irt.remove(cookie, iref2))
112    {
113        ALOGE("fifo deletion failed");
114        goto bail;
115    }
116
117    /* table should be empty now */
118    if (irt.capacity() != 0) {
119        ALOGE("fifo del not empty");
120        goto bail;
121    }
122
123    /* get invalid entry (off the end of the list) */
124    if (irt.get(iref0) != kInvalidIndirectRefObject) {
125        ALOGE("stale entry get succeeded unexpectedly");
126        goto bail;
127    }
128
129    /*
130     * Add three, remove in the opposite order.
131     */
132    DBUG_MSG("+++ START lifo\n");
133    iref0 = irt.add(cookie, obj0);
134    iref1 = irt.add(cookie, obj1);
135    iref2 = irt.add(cookie, obj2);
136    if (iref0 == NULL || iref1 == NULL || iref2 == NULL) {
137        ALOGE("trivial add2 failed");
138        goto bail;
139    }
140
141    if (!irt.remove(cookie, iref2) ||
142            !irt.remove(cookie, iref1) ||
143            !irt.remove(cookie, iref0))
144    {
145        ALOGE("lifo deletion failed");
146        goto bail;
147    }
148
149    /* table should be empty now */
150    if (irt.capacity() != 0) {
151        ALOGE("lifo del not empty");
152        goto bail;
153    }
154
155    /*
156     * Add three, remove middle / middle / bottom / top.  (Second attempt
157     * to remove middle should fail.)
158     */
159    DBUG_MSG("+++ START unorder\n");
160    iref0 = irt.add(cookie, obj0);
161    iref1 = irt.add(cookie, obj1);
162    iref2 = irt.add(cookie, obj2);
163    if (iref0 == NULL || iref1 == NULL || iref2 == NULL) {
164        ALOGE("trivial add3 failed");
165        goto bail;
166    }
167
168    if (irt.capacity() != 3) {
169        ALOGE("expected 3 entries, found %d", irt.capacity());
170        goto bail;
171    }
172
173    if (!irt.remove(cookie, iref1) || irt.remove(cookie, iref1)) {
174        ALOGE("unorder deletion1 failed");
175        goto bail;
176    }
177
178    /* get invalid entry (from hole) */
179    if (irt.get(iref1) != kInvalidIndirectRefObject) {
180        ALOGE("hole get succeeded unexpectedly");
181        goto bail;
182    }
183
184    if (!irt.remove(cookie, iref2) || !irt.remove(cookie, iref0)) {
185        ALOGE("unorder deletion2 failed");
186        goto bail;
187    }
188
189    /* table should be empty now */
190    if (irt.capacity() != 0) {
191        ALOGE("unorder del not empty");
192        goto bail;
193    }
194
195    /*
196     * Add four entries.  Remove #1, add new entry, verify that table size
197     * is still 4 (i.e. holes are getting filled).  Remove #1 and #3, verify
198     * that we delete one and don't hole-compact the other.
199     */
200    DBUG_MSG("+++ START hole fill\n");
201    iref0 = irt.add(cookie, obj0);
202    iref1 = irt.add(cookie, obj1);
203    iref2 = irt.add(cookie, obj2);
204    iref3 = irt.add(cookie, obj3);
205    if (iref0 == NULL || iref1 == NULL || iref2 == NULL || iref3 == NULL) {
206        ALOGE("trivial add4 failed");
207        goto bail;
208    }
209    if (!irt.remove(cookie, iref1)) {
210        ALOGE("remove 1 of 4 failed");
211        goto bail;
212    }
213    iref1 = irt.add(cookie, obj1);
214    if (irt.capacity() != 4) {
215        ALOGE("hole not filled");
216        goto bail;
217    }
218    if (!irt.remove(cookie, iref1) || !irt.remove(cookie, iref3)) {
219        ALOGE("remove 1/3 failed");
220        goto bail;
221    }
222    if (irt.capacity() != 3) {
223        ALOGE("should be 3 after two deletions");
224        goto bail;
225    }
226    if (!irt.remove(cookie, iref2) || !irt.remove(cookie, iref0)) {
227        ALOGE("remove 2/0 failed");
228        goto bail;
229    }
230    if (irt.capacity() != 0) {
231        ALOGE("not empty after split remove");
232        goto bail;
233    }
234
235    /*
236     * Add an entry, remove it, add a new entry, and try to use the original
237     * iref.  They have the same slot number but are for different objects.
238     * With the extended checks in place, this should fail.
239     */
240    DBUG_MSG("+++ START switched\n");
241    iref0 = irt.add(cookie, obj0);
242    irt.remove(cookie, iref0);
243    iref1 = irt.add(cookie, obj1);
244    if (irt.remove(cookie, iref0)) {
245        ALOGE("mismatched del succeeded (%p vs %p)", iref0, iref1);
246        goto bail;
247    }
248    if (!irt.remove(cookie, iref1)) {
249        ALOGE("switched del failed");
250        goto bail;
251    }
252    if (irt.capacity() != 0) {
253        ALOGE("switching del not empty");
254        goto bail;
255    }
256
257    /*
258     * Same as above, but with the same object.  A more rigorous checker
259     * (e.g. with slot serialization) will catch this.
260     */
261    DBUG_MSG("+++ START switched same object\n");
262    iref0 = irt.add(cookie, obj0);
263    irt.remove(cookie, iref0);
264    iref1 = irt.add(cookie, obj0);
265    if (iref0 != iref1) {
266        /* try 0, should not work */
267        if (irt.remove(cookie, iref0)) {
268            ALOGE("temporal del succeeded (%p vs %p)", iref0, iref1);
269            goto bail;
270        }
271    }
272    if (!irt.remove(cookie, iref1)) {
273        ALOGE("temporal cleanup failed");
274        goto bail;
275    }
276    if (irt.capacity() != 0) {
277        ALOGE("temporal del not empty");
278        goto bail;
279    }
280
281    DBUG_MSG("+++ START null lookup\n");
282    if (irt.get(NULL) != kInvalidIndirectRefObject) {
283        ALOGE("null lookup succeeded");
284        goto bail;
285    }
286
287    DBUG_MSG("+++ START stale lookup\n");
288    iref0 = irt.add(cookie, obj0);
289    irt.remove(cookie, iref0);
290    if (irt.get(iref0) != kInvalidIndirectRefObject) {
291        ALOGE("stale lookup succeeded");
292        goto bail;
293    }
294
295    /*
296     * Test table overflow.
297     */
298    DBUG_MSG("+++ START overflow\n");
299    int i;
300    for (i = 0; i < kTableMax; i++) {
301        manyRefs[i] = irt.add(cookie, obj0);
302        if (manyRefs[i] == NULL) {
303            ALOGE("Failed adding %d of %d", i, kTableMax);
304            goto bail;
305        }
306    }
307    if (irt.add(cookie, obj0) != NULL) {
308        ALOGE("Table overflow succeeded");
309        goto bail;
310    }
311    if (irt.capacity() != (size_t)kTableMax) {
312        ALOGE("Expected %d entries, found %d", kTableMax, irt.capacity());
313        goto bail;
314    }
315    irt.dump("table with 20 entries, all filled");
316    for (i = 0; i < kTableMax-1; i++) {
317        if (!irt.remove(cookie, manyRefs[i])) {
318            ALOGE("multi-remove failed at %d", i);
319            goto bail;
320        }
321    }
322    irt.dump("table with 20 entries, 19 of them holes");
323    /* because of removal order, should have 20 entries, 19 of them holes */
324    if (irt.capacity() != (size_t)kTableMax) {
325        ALOGE("Expected %d entries (with holes), found %d",
326                kTableMax, irt.capacity());
327        goto bail;
328    }
329    if (!irt.remove(cookie, manyRefs[kTableMax-1])) {
330        ALOGE("multi-remove final failed");
331        goto bail;
332    }
333    if (irt.capacity() != 0) {
334        ALOGE("multi-del not empty");
335        goto bail;
336    }
337
338    /* Done */
339    DBUG_MSG("+++ basic test complete\n");
340    result = true;
341
342bail:
343    irt.destroy();
344    return result;
345}
346
347static bool performanceTest()
348{
349    static const int kTableMax = 100;
350    IndirectRefTable irt;
351    IndirectRef manyRefs[kTableMax];
352    ClassObject* clazz = dvmFindClass("Ljava/lang/Object;", NULL);
353    Object* obj0 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
354    const u4 cookie = IRT_FIRST_SEGMENT;
355    const int kLoops = 100000;
356    Stopwatch stopwatch;
357
358    DBUG_MSG("+++ START performance\n");
359
360    if (!irt.init(kTableMax, kTableMax, kIndirectKindGlobal)) {
361        return false;
362    }
363
364    stopwatch.reset();
365    for (int loop = 0; loop < kLoops; loop++) {
366        for (int i = 0; i < kTableMax; i++) {
367            manyRefs[i] = irt.add(cookie, obj0);
368        }
369        for (int i = 0; i < kTableMax; i++) {
370            irt.remove(cookie, manyRefs[i]);
371        }
372    }
373    DBUG_MSG("Add/remove %d objects FIFO order, %d iterations, %0.3fms / iteration",
374            kTableMax, kLoops, stopwatch.elapsedSeconds() * 1000 / kLoops);
375
376    stopwatch.reset();
377    for (int loop = 0; loop < kLoops; loop++) {
378        for (int i = 0; i < kTableMax; i++) {
379            manyRefs[i] = irt.add(cookie, obj0);
380        }
381        for (int i = kTableMax; i-- > 0; ) {
382            irt.remove(cookie, manyRefs[i]);
383        }
384    }
385    DBUG_MSG("Add/remove %d objects LIFO order, %d iterations, %0.3fms / iteration",
386            kTableMax, kLoops, stopwatch.elapsedSeconds() * 1000  / kLoops);
387
388    for (int i = 0; i < kTableMax; i++) {
389        manyRefs[i] = irt.add(cookie, obj0);
390    }
391    stopwatch.reset();
392    for (int loop = 0; loop < kLoops; loop++) {
393        for (int i = 0; i < kTableMax; i++) {
394            irt.get(manyRefs[i]);
395        }
396    }
397    DBUG_MSG("Get %d objects, %d iterations, %0.3fms / iteration",
398            kTableMax, kLoops, stopwatch.elapsedSeconds() * 1000  / kLoops);
399    for (int i = kTableMax; i-- > 0; ) {
400        irt.remove(cookie, manyRefs[i]);
401    }
402
403    irt.destroy();
404    return true;
405}
406
407/*
408 * Some quick tests.
409 */
410bool dvmTestIndirectRefTable()
411{
412    if (!basicTest()) {
413        ALOGE("IRT basic test failed");
414        return false;
415    }
416
417    if (!performanceTest()) {
418        ALOGE("IRT performance test failed");
419        return false;
420    }
421
422    return true;
423}
424
425#endif /*NDEBUG*/
426