1 2 /*- 3 * See the file LICENSE for redistribution information. 4 * 5 * Copyright (c) 2002, 2014 Oracle and/or its affiliates. All rights reserved. 6 * 7 */ 8 9 package com.sleepycat.je.tree; 10 11 import static org.junit.Assert.assertEquals; 12 import static org.junit.Assert.assertFalse; 13 import static org.junit.Assert.assertTrue; 14 15 import java.io.File; 16 17 import org.junit.After; 18 import org.junit.Before; 19 import org.junit.Test; 20 21 import com.sleepycat.je.CacheMode; 22 import com.sleepycat.je.Cursor; 23 import com.sleepycat.je.CursorConfig; 24 import com.sleepycat.je.Database; 25 import com.sleepycat.je.DatabaseConfig; 26 import com.sleepycat.je.DatabaseEntry; 27 import com.sleepycat.je.DatabaseException; 28 import com.sleepycat.je.DbInternal; 29 import com.sleepycat.je.Environment; 30 import com.sleepycat.je.EnvironmentConfig; 31 import com.sleepycat.je.LockMode; 32 import com.sleepycat.je.OperationStatus; 33 import com.sleepycat.je.Transaction; 34 import com.sleepycat.je.config.EnvironmentParams; 35 import com.sleepycat.je.dbi.CursorImpl; 36 import com.sleepycat.je.tree.Key.DumpType; 37 import com.sleepycat.je.util.TestUtils; 38 import com.sleepycat.util.test.SharedTestUtils; 39 import com.sleepycat.util.test.TestBase; 40 import com.sleepycat.je.utilint.Pair; 41 import com.sleepycat.je.utilint.TestHook; 42 43 public class FetchWithNoLatchTest extends TestBase { 44 static private final boolean DEBUG = false; 45 46 private final File envHome; 47 private Environment env; 48 private Database db1; 49 private Database db2; 50 private Database db3; 51 FetchWithNoLatchTest()52 public FetchWithNoLatchTest() { 53 envHome = SharedTestUtils.getTestDir(); 54 55 Key.DUMP_TYPE = DumpType.BINARY; 56 } 57 58 @Before setUp()59 public void setUp() 60 throws Exception { 61 62 super.setUp(); 63 initEnv(); 64 } 65 66 @After tearDown()67 public void tearDown() { 68 69 try { 70 db1.close(); 71 db2.close(); 72 db3.close(); 73 env.close(); 74 } catch (DatabaseException E) { 75 } 76 } 77 initEnv()78 private void initEnv() 79 throws DatabaseException { 80 81 EnvironmentConfig envConfig = TestUtils.initEnvConfig(); 82 envConfig.setConfigParam(EnvironmentParams.NODE_MAX.getName(), "4"); 83 envConfig.setTransactional(true); 84 envConfig.setAllowCreate(true); 85 env = new Environment(envHome, envConfig); 86 87 String databaseName = "testDb1"; 88 Transaction txn = env.beginTransaction(null, null); 89 DatabaseConfig dbConfig = new DatabaseConfig(); 90 dbConfig.setTransactional(true); 91 dbConfig.setAllowCreate(true); 92 db1 = env.openDatabase(txn, databaseName, dbConfig); 93 txn.commit(); 94 95 databaseName = "testDb2"; 96 txn = env.beginTransaction(null, null); 97 dbConfig = new DatabaseConfig(); 98 dbConfig.setTransactional(true); 99 dbConfig.setAllowCreate(true); 100 db2 = env.openDatabase(txn, databaseName, dbConfig); 101 txn.commit(); 102 103 databaseName = "testDb3"; 104 dbConfig = new DatabaseConfig(); 105 dbConfig.setTransactional(true); 106 dbConfig.setAllowCreate(true); 107 db3 = env.openDatabase(null, databaseName, dbConfig); 108 } 109 110 @Test testSplit1()111 public void testSplit1() 112 throws Exception { 113 114 Key.DUMP_TYPE = DumpType.BINARY; 115 final Database db = db1; 116 117 try { 118 /* Create the initial tree */ 119 Tree tree = createTree(db); 120 121 /* Evict the BIN B containing the key 20 (BIN 14) */ 122 final Pair<IN, IN> pair = evictBIN(db, 20); 123 final IN parent = pair.first(); 124 final IN bin = pair.second(); 125 126 /* 127 * Refetch B (via getParentINForChildIN() below) while splitting 128 * its sibling and parent (BINs 11 and 13) at the "same" time. The 129 * split is done via the test hook below, which is executed right 130 * after IN.fetchIN() releases the latch on B's parent in order to 131 * fetch B. The split causes B's parent to change. 132 */ 133 FetchINTestHook fetchINHook = new FetchINTestHook( 134 db, parent, 66, true, false); 135 136 parent.setFetchINHook(fetchINHook); 137 tree.setFetchINHook(fetchINHook); 138 139 bin.latch(); 140 SearchResult result = tree.getParentINForChildIN( 141 bin, false, /*useTargetLevel*/ true, /*doFetch*/ 142 CacheMode.UNCHANGED); 143 144 result.parent.releaseLatch(); 145 146 /* Make sure everything went fine. */ 147 assertTrue(fetchINHook.foundNullChild); 148 assertTrue(result.exactParentFound); 149 assertTrue(parent != result.parent); 150 assertTrue(result.parent.getNodeId() > parent.getNodeId()); 151 152 } catch (Throwable t) { 153 t.printStackTrace(); 154 throw new Exception(t); 155 } 156 } 157 158 159 @Test testSplit2()160 public void testSplit2() 161 throws Exception { 162 163 Key.DUMP_TYPE = DumpType.BINARY; 164 final Database db = db2; 165 166 try { 167 /* Create the initial tree */ 168 Tree tree = createTree(db); 169 170 /* Evict the BIN B containing the key 20 (BIN 14) */ 171 final Pair<IN, IN> pair = evictBIN(db, 30); 172 final IN parent = pair.first(); 173 final IN bin = pair.second(); 174 175 /* 176 * Refetch B (via getParentINForChildIN() below) while splitting B 177 * itself and its parent (BIN 13) at the "same" time. The split is 178 * done via the FetchINTestHook, which is executed right after 179 * IN.fetchIN() releases the latch on B's parent in order to fetch 180 * B. The split does not change B's parent. However, the version 181 * B that fetchIN() is fetching becomes obsolete as a result of 182 * the split, and should not be attached to the tree. This is 183 * indeed avaoided because fetchIN() will find B's new version 184 * in the tree, and will return that one instead of the one just 185 * fetched from disk. 186 */ 187 FetchINTestHook fetchINHook = new FetchINTestHook( 188 db, parent, 33, true, false); 189 190 parent.setFetchINHook(fetchINHook); 191 tree.setFetchINHook(fetchINHook); 192 193 bin.latch(); 194 SearchResult result = tree.getParentINForChildIN( 195 bin, false, /*useTargetLevel*/ true, /*doFetch*/ 196 CacheMode.UNCHANGED); 197 198 /* Make sure everything went fine. */ 199 assertTrue(fetchINHook.foundNullChild); 200 assertTrue(result.exactParentFound); 201 assertTrue(parent != result.parent); 202 203 result.parent.releaseLatch(); 204 205 rangeSearch(db); 206 207 } catch (Throwable t) { 208 t.printStackTrace(); 209 throw new Exception(t); 210 } 211 } 212 213 214 @Test testSplit3()215 public void testSplit3() 216 throws Exception { 217 218 Key.DUMP_TYPE = DumpType.BINARY; 219 final Database db = db3; 220 221 try { 222 /* Create the initial tree */ 223 Tree tree = createTree(db); 224 225 /* Evict the BIN B containing the key 50 (BIN 11) */ 226 final Pair<IN, IN> pair = evictBIN(db, 50); 227 final IN parent = pair.first(); 228 final IN bin = pair.second(); 229 230 /* 231 * Refetch B (via getParentINForChildIN() below) while splitting B 232 * itself and its parent (BIN 13) at the "same" time. The split is 233 * done via the FetchINTestHook, which is executed right after 234 * IN.fetchIN() releases the latch on B's parent in order to fetch 235 * B. The split does not change B's parent. However, the version 236 * B that fetchIN() is fetching becomes obsolete as a result of 237 * the split, and should not be attached to the tree. In this test, 238 * after B is split, we evict B before resuming with fetchIN(). 239 * fetchIN() will not attach the fetched (obsolete) version in the 240 * tree because the parent slot has an LSN that is different than 241 * the fetched LSN. 242 */ 243 FetchINTestHook fetchINHook = new FetchINTestHook( 244 db, parent, 66, true, true); 245 246 parent.setFetchINHook(fetchINHook); 247 tree.setFetchINHook(fetchINHook); 248 249 bin.latch(); 250 SearchResult result = tree.getParentINForChildIN( 251 bin, false, /*useTargetLevel*/ true, /*doFetch*/ 252 CacheMode.UNCHANGED); 253 254 result.parent.releaseLatch(); 255 256 /* Make sure everything went fine. */ 257 assertTrue(fetchINHook.foundNullChild); 258 assertTrue(result.exactParentFound); 259 assertTrue(parent == result.parent); 260 261 rangeSearch(db); 262 263 } catch (Throwable t) { 264 t.printStackTrace(); 265 throw new Exception(t); 266 } 267 } 268 269 @Test testSplit4()270 public void testSplit4() 271 throws Exception { 272 273 Key.DUMP_TYPE = DumpType.BINARY; 274 final Database db = db2; 275 276 try { 277 /* Create the initial tree */ 278 Tree tree = createTree(db); 279 280 /* Evict the BIN B containing the key 120 (BIN 9) */ 281 final Pair<IN, IN> pair = evictBIN(db, 120); 282 final IN parent = pair.first(); 283 284 /* 285 * Execute search(110) while splitting B (but not its parent) at 286 * the "same" time. The split is done via the FetchINTestHook, 287 * which is executed right after IN.fetchIN() (called from 288 * search(110)) releases the latch on B's parent in order to 289 * fetch B. The split does not change B's parent. However, 290 * the key we are looking for is now in B's new sibling and 291 * fetchIN() should return that sibling without causing a 292 * restart of the search. 293 */ 294 FetchINTestHook fetchINHook = new FetchINTestHook( 295 db, parent, 126, false, false); 296 297 parent.setFetchINHook(fetchINHook); 298 //parent.setIdentifierKey(new byte[]{(byte)40}); 299 300 Cursor cursor = db.openCursor(null, CursorConfig.DEFAULT); 301 302 assertEquals( 303 OperationStatus.SUCCESS, 304 cursor.getSearchKey( 305 new DatabaseEntry(new byte[]{(byte)110}), 306 new DatabaseEntry(), 307 LockMode.DEFAULT)); 308 309 cursor.close(); 310 311 } catch (Throwable t) { 312 t.printStackTrace(); 313 throw new Exception(t); 314 } 315 } 316 317 /* 318 * A test hook assigned to a givan IN P and triggerred when P.fetchIN() 319 * is called to fetch a missing child of P, after P is unlatched. The 320 * doHook() method causes P to split by inserting a given key in one of 321 * P's children. 322 */ 323 class FetchINTestHook implements TestHook { 324 325 Database db; 326 IN parent; 327 int newKey; 328 boolean parentSplits; 329 boolean evict; 330 boolean foundNullChild = false; 331 FetchINTestHook( Database db, IN parent, int newKey, boolean parentSplits, boolean evict)332 FetchINTestHook( 333 Database db, 334 IN parent, 335 int newKey, 336 boolean parentSplits, 337 boolean evict) { 338 339 this.db = db; 340 this.parent = parent; 341 this.newKey = newKey; 342 this.parentSplits = parentSplits; 343 this.evict = evict; 344 } 345 346 @Override doHook()347 public void doHook() { 348 /* Only process the first call to the hook. */ 349 parent.setFetchINHook(null); 350 351 int numEntries = parent.getNEntries(); 352 353 /* split the parent of the missing bin. */ 354 assertEquals( 355 OperationStatus.SUCCESS, 356 db.put(null, 357 new DatabaseEntry(new byte[]{(byte)newKey}), 358 new DatabaseEntry(new byte[] {1}))); 359 360 if (parentSplits) { 361 assert(numEntries > parent.getNEntries()); 362 } 363 364 if (evict) { 365 evictBIN(db, newKey); 366 } 367 } 368 doHook(Object obj)369 @Override public void doHook(Object obj) { 370 assertFalse(foundNullChild); 371 foundNullChild = true; 372 } 373 hookSetup()374 @Override public void hookSetup() { } doIOHook()375 @Override public void doIOHook() { } 376 getHookValue()377 @Override public Object getHookValue() { return foundNullChild; } 378 }; 379 380 /* 381 * Create a tree that looks like this: 382 * 383 * --------------------- 384 * | nid: 12 - key: 70 | 385 * |...................| 386 * | 70 | 110 | 387 * --------------------- 388 * / \ 389 * / \ 390 * ---------------------- .. Subtree shown 391 * | nid: 13 - key: 70 | below. 392 * |....................| 393 * | 40 | 50 | 80 | 394 * ---------------------- 395 * / | \ 80 <= k < 110 396 * ------------------ | ----------------- 397 * | | | 398 * --------------------- --------------------- ---------------------- 399 * | nid: 14 - key: 40 | | nid: 11 - key: 70 | | nid: 10 - key: 100 | 400 * |...................| |...................| |....................| 401 * | 10 | 20 | 30 | 40 | | 50 | 60 | 65 | 70 | | 80 | 90 | 95 | 100 | 402 * --------------------- --------------------- ---------------------- 403 * 404 * 405 * ---------------------- 406 * | nid: 8 - key: 160 | 407 * |....................| 408 * | 110 | 140 | 409 * ---------------------- 410 * / \ 411 * / \ 412 * / \ 413 * ------------------------- ------------------------ 414 * | nid: 9 - key: 130 | | nid: 7 - key: 160 | 415 * |.......................| |......................| 416 * | 110 | 120 | 125 | 130 | | 140 | 150 | 160 | 417 * ------------------------- ------------------------ 418 */ createTree(Database db)419 Tree createTree(Database db) { 420 421 for (int i = 160; i > 0; i-= 10) { 422 assertEquals( 423 OperationStatus.SUCCESS, 424 db.put(null, 425 new DatabaseEntry(new byte[] { (byte) i }), 426 new DatabaseEntry(new byte[] {1}))); 427 } 428 429 assertEquals( 430 OperationStatus.SUCCESS, 431 db.put(null, 432 new DatabaseEntry(new byte[]{(byte)65}), 433 new DatabaseEntry(new byte[] {1}))); 434 435 assertEquals( 436 OperationStatus.SUCCESS, 437 db.put(null, 438 new DatabaseEntry(new byte[]{(byte)95}), 439 new DatabaseEntry(new byte[] {1}))); 440 441 assertEquals( 442 OperationStatus.SUCCESS, 443 db.put(null, 444 new DatabaseEntry(new byte[]{(byte)125}), 445 new DatabaseEntry(new byte[] {1}))); 446 447 Tree tree = DbInternal.getDatabaseImpl(db).getTree(); 448 449 if (DEBUG) { 450 System.out.println("<dump>"); 451 tree.dump(); 452 } 453 454 return tree; 455 } 456 457 /* 458 * Evict the BIN containing the given key and return the BIN and its parent. 459 */ evictBIN(Database db, int keyVal)460 Pair<IN, IN> evictBIN(Database db, int keyVal) { 461 462 Tree tree = DbInternal.getDatabaseImpl(db).getTree(); 463 464 Cursor cursor = db.openCursor(null, CursorConfig.DEFAULT); 465 cursor.setCacheMode(CacheMode.EVICT_BIN); 466 467 CursorImpl cursorImpl = DbInternal.getCursorImpl(cursor); 468 469 DatabaseEntry key = new DatabaseEntry(new byte[] { (byte) keyVal }); 470 DatabaseEntry data = new DatabaseEntry(); 471 assertEquals( 472 OperationStatus.SUCCESS, 473 cursor.getSearchKey(key, data, LockMode.DEFAULT)); 474 475 IN bin = cursorImpl.getBIN(); 476 bin.latch(); 477 478 SearchResult result = tree.getParentINForChildIN( 479 bin, false, /*useTargetLevel*/ true, /*doFetch*/ 480 CacheMode.UNCHANGED); 481 482 assertTrue(result.exactParentFound); 483 484 final IN parent = result.parent; 485 parent.releaseLatch(); 486 487 /* evict the BIN */ 488 cursor.close(); 489 490 return new Pair<>(parent, bin); 491 } 492 493 /* 494 * Do a range search for keys in [10, 100] 495 */ rangeSearch(Database db)496 void rangeSearch(Database db) { 497 498 Cursor cursor = db.openCursor(null, CursorConfig.DEFAULT); 499 DatabaseEntry key = new DatabaseEntry(new byte[] { (byte) 10 }); 500 DatabaseEntry data = new DatabaseEntry(); 501 assertEquals( 502 OperationStatus.SUCCESS, 503 cursor.getSearchKeyRange(key, data, LockMode.DEFAULT)); 504 505 OperationStatus status = OperationStatus.SUCCESS; 506 int keyVal = 0; 507 int numKeys = 0; 508 do { 509 status = cursor.getNext(key, data, LockMode.DEFAULT); 510 511 keyVal = (int)(key.getData()[0]); 512 if (keyVal > 100) { 513 break; 514 } 515 516 ++numKeys; 517 System.out.println(keyVal); 518 } while (status == OperationStatus.SUCCESS); 519 520 cursor.close(); 521 522 assertEquals(numKeys, 12); 523 } 524 } 525