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 */ 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 irt.dump("table with 20 entries, all filled"); 285 for (i = 0; i < kTableMax-1; i++) { 286 if (!irt.remove(cookie, manyRefs[i])) { 287 LOGE("multi-remove failed at %d", i); 288 goto bail; 289 } 290 } 291 irt.dump("table with 20 entries, 19 of them holes"); 292 /* because of removal order, should have 20 entries, 19 of them holes */ 293 if (irt.capacity() != (size_t)kTableMax) { 294 LOGE("Expected %d entries (with holes), found %d", 295 kTableMax, irt.capacity()); 296 goto bail; 297 } 298 if (!irt.remove(cookie, manyRefs[kTableMax-1])) { 299 LOGE("multi-remove final failed"); 300 goto bail; 301 } 302 if (irt.capacity() != 0) { 303 LOGE("multi-del not empty"); 304 goto bail; 305 } 306 307 /* Done */ 308 DBUG_MSG("+++ basic test complete\n"); 309 result = true; 310 311 bail: 312 irt.destroy(); 313 return result; 314 } 315 316 /* 317 * Some quick tests. 318 */ 319 bool dvmTestIndirectRefTable() 320 { 321 if (!basicTest()) { 322 LOGE("IRT basic test failed"); 323 return false; 324 } 325 326 return true; 327 } 328 329 #endif /*NDEBUG*/ 330
