TestIndirectRefTable.cpp revision 476157d87784f48935cb86f01c079db1f9338e36 
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    LOGI
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        LOGE("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        LOGE("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        LOGE("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        LOGE("fifo deletion failed");
114        goto bail;
115    }
116
117    /* table should be empty now */
118    if (irt.capacity() != 0) {
119        LOGE("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        LOGE("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        LOGE("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        LOGE("lifo deletion failed");
146        goto bail;
147    }
148
149    /* table should be empty now */
150    if (irt.capacity() != 0) {
151        LOGE("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        LOGE("trivial add3 failed");
165        goto bail;
166    }
167
168    if (irt.capacity() != 3) {
169        LOGE("expected 3 entries, found %d", irt.capacity());
170        goto bail;
171    }
172
173    if (!irt.remove(cookie, iref1) || irt.remove(cookie, iref1)) {
174        LOGE("unorder deletion1 failed");
175        goto bail;
176    }
177
178    /* get invalid entry (from hole) */
179    if (irt.get(iref1) != kInvalidIndirectRefObject) {
180        LOGE("hole get succeeded unexpectedly");
181        goto bail;
182    }
183
184    if (!irt.remove(cookie, iref2) || !irt.remove(cookie, iref0)) {
185        LOGE("unorder deletion2 failed");
186        goto bail;
187    }
188
189    /* table should be empty now */
190    if (irt.capacity() != 0) {
191        LOGE("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        LOGE("trivial add4 failed");
207        goto bail;
208    }
209    if (!irt.remove(cookie, iref1)) {
210        LOGE("remove 1 of 4 failed");
211        goto bail;
212    }
213    iref1 = irt.add(cookie, obj1);
214    if (irt.capacity() != 4) {
215        LOGE("hole not filled");
216        goto bail;
217    }
218    if (!irt.remove(cookie, iref1) || !irt.remove(cookie, iref3)) {
219        LOGE("remove 1/3 failed");
220        goto bail;
221    }
222    if (irt.capacity() != 3) {
223        LOGE("should be 3 after two deletions");
224        goto bail;
225    }
226    if (!irt.remove(cookie, iref2) || !irt.remove(cookie, iref0)) {
227        LOGE("remove 2/0 failed");
228        goto bail;
229    }
230    if (irt.capacity() != 0) {
231        LOGE("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        LOGE("mismatched del succeeded (%p vs %p)", iref0, iref1);
246        goto bail;
247    }
248    if (!irt.remove(cookie, iref1)) {
249        LOGE("switched del failed");
250        goto bail;
251    }
252    if (irt.capacity() != 0) {
253        LOGE("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            LOGE("temporal del succeeded (%p vs %p)", iref0, iref1);
269            goto bail;
270        }
271    }
272    if (!irt.remove(cookie, iref1)) {
273        LOGE("temporal cleanup failed");
274        goto bail;
275    }
276    if (irt.capacity() != 0) {
277        LOGE("temporal del not empty");
278        goto bail;
279    }
280
281    DBUG_MSG("+++ START null lookup\n");
282    if (irt.get(NULL) != kInvalidIndirectRefObject) {
283        LOGE("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        LOGE("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            LOGE("Failed adding %d of %d", i, kTableMax);
304            goto bail;
305        }
306    }
307    if (irt.add(cookie, obj0) != NULL) {
308        LOGE("Table overflow succeeded");
309        goto bail;
310    }
311    if (irt.capacity() != (size_t)kTableMax) {
312        LOGE("Expected %d entries, found %d", kTableMax, irt.capacity());
313        goto bail;
314    }
315    for (i = 0; i < kTableMax-1; i++) {
316        if (!irt.remove(cookie, manyRefs[i])) {
317            LOGE("multi-remove failed at %d", i);
318            goto bail;
319        }
320    }
321    /* because of removal order, should have 20 entries, 19 of them holes */
322    if (irt.capacity() != (size_t)kTableMax) {
323        LOGE("Expected %d entries (with holes), found %d",
324                kTableMax, irt.capacity());
325        goto bail;
326    }
327    if (!irt.remove(cookie, manyRefs[kTableMax-1])) {
328        LOGE("multi-remove final failed");
329        goto bail;
330    }
331    if (irt.capacity() != 0) {
332        LOGE("multi-del not empty");
333        goto bail;
334    }
335
336    DBUG_MSG("+++ basic test complete\n");
337    result = true;
338
339bail:
340    irt.destroy();
341    return result;
342}
343
344static bool performanceTest()
345{
346    static const int kTableMax = 100;
347    IndirectRefTable irt;
348    IndirectRef manyRefs[kTableMax];
349    ClassObject* clazz = dvmFindClass("Ljava/lang/Object;", NULL);
350    Object* obj0 = dvmAllocObject(clazz, ALLOC_DONT_TRACK);
351    const u4 cookie = IRT_FIRST_SEGMENT;
352    const int kLoops = 100000;
353    Stopwatch stopwatch;
354
355    DBUG_MSG("+++ START performance\n");
356
357    if (!irt.init(kTableMax, kTableMax, kIndirectKindGlobal)) {
358        return false;
359    }
360
361    stopwatch.reset();
362    for (int loop = 0; loop < kLoops; loop++) {
363        for (int i = 0; i < kTableMax; i++) {
364            manyRefs[i] = irt.add(cookie, obj0);
365        }
366        for (int i = 0; i < kTableMax; i++) {
367            irt.remove(cookie, manyRefs[i]);
368        }
369    }
370    DBUG_MSG("Add/remove %d objects FIFO order, %d iterations, %0.3fms / iteration",
371            kTableMax, kLoops, stopwatch.elapsedSeconds() * 1000 / kLoops);
372
373    stopwatch.reset();
374    for (int loop = 0; loop < kLoops; loop++) {
375        for (int i = 0; i < kTableMax; i++) {
376            manyRefs[i] = irt.add(cookie, obj0);
377        }
378        for (int i = kTableMax; i-- > 0; ) {
379            irt.remove(cookie, manyRefs[i]);
380        }
381    }
382    DBUG_MSG("Add/remove %d objects LIFO order, %d iterations, %0.3fms / iteration",
383            kTableMax, kLoops, stopwatch.elapsedSeconds() * 1000  / kLoops);
384
385    for (int i = 0; i < kTableMax; i++) {
386        manyRefs[i] = irt.add(cookie, obj0);
387    }
388    stopwatch.reset();
389    for (int loop = 0; loop < kLoops; loop++) {
390        for (int i = 0; i < kTableMax; i++) {
391            irt.get(manyRefs[i]);
392        }
393    }
394    DBUG_MSG("Get %d objects, %d iterations, %0.3fms / iteration",
395            kTableMax, kLoops, stopwatch.elapsedSeconds() * 1000  / kLoops);
396    for (int i = kTableMax; i-- > 0; ) {
397        irt.remove(cookie, manyRefs[i]);
398    }
399
400    irt.destroy();
401    return true;
402}
403
404/*
405 * Some quick tests.
406 */
407bool dvmTestIndirectRefTable()
408{
409    if (!basicTest()) {
410        LOGE("IRT basic test failed");
411        return false;
412    }
413
414    if (!performanceTest()) {
415        LOGE("IRT performance test failed");
416        return false;
417    }
418
419    return true;
420}
421
422#endif /*NDEBUG*/
423