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
29 class Stopwatch {
30 public:
Stopwatch()31 Stopwatch() {
32 reset();
33 }
34
reset()35 void reset() {
36 start_ = now();
37 }
38
elapsedSeconds()39 float elapsedSeconds() {
40 return (now() - start_) * 0.000001f;
41 }
42
43 private:
44 u8 start_;
45
now()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 */
basicTest()62 static 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
342 bail:
343 irt.destroy();
344 return result;
345 }
346
performanceTest()347 static 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 */
dvmTestIndirectRefTable()410 bool 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