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 */
basicTest()31 static 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
308 bail:
309 irt.destroy();
310 return result;
311 }
312
313 /*
314 * Some quick tests.
315 */
dvmTestIndirectRefTable()316 bool 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