Java API By Example, From Geeks To Geeks.

1 /*- 2  * See the file LICENSE for redistribution information. 3  * 4  * Copyright (c) 2002,2006 Oracle. All rights reserved. 5  * 6  * $Id: RecoveryManager.java,v 1.211 2006/12/04 18:47:41 cwl Exp $ 7  */ 8 9 package com.sleepycat.je.recovery; 10 11 import java.io.IOException ; 12 import java.util.ArrayList ; 13 import java.util.HashMap ; 14 import java.util.HashSet ; 15 import java.util.Iterator ; 16 import java.util.List ; 17 import java.util.Map ; 18 import java.util.Set ; 19 import java.util.logging.Level ; 20 import java.util.logging.Logger ; 21 22 import com.sleepycat.je.CheckpointConfig; 23 import com.sleepycat.je.DatabaseException; 24 import com.sleepycat.je.DbInternal; 25 import com.sleepycat.je.TransactionConfig; 26 import com.sleepycat.je.cleaner.UtilizationTracker; 27 import com.sleepycat.je.config.EnvironmentParams; 28 import com.sleepycat.je.dbi.DatabaseId; 29 import com.sleepycat.je.dbi.DatabaseImpl; 30 import com.sleepycat.je.dbi.DbConfigManager; 31 import com.sleepycat.je.dbi.DbTree; 32 import com.sleepycat.je.dbi.EnvironmentImpl; 33 import com.sleepycat.je.latch.LatchSupport; 34 import com.sleepycat.je.log.CheckpointFileReader; 35 import com.sleepycat.je.log.FileManager; 36 import com.sleepycat.je.log.INFileReader; 37 import com.sleepycat.je.log.LNFileReader; 38 import com.sleepycat.je.log.LastFileReader; 39 import com.sleepycat.je.log.LogEntryType; 40 import com.sleepycat.je.log.LogFileNotFoundException; 41 import com.sleepycat.je.tree.BIN; 42 import com.sleepycat.je.tree.ChildReference; 43 import com.sleepycat.je.tree.DIN; 44 import com.sleepycat.je.tree.IN; 45 import com.sleepycat.je.tree.Key; 46 import com.sleepycat.je.tree.LN; 47 import com.sleepycat.je.tree.Node; 48 import com.sleepycat.je.tree.SearchResult; 49 import com.sleepycat.je.tree.TrackingInfo; 50 import com.sleepycat.je.tree.Tree; 51 import com.sleepycat.je.tree.TreeLocation; 52 import com.sleepycat.je.tree.WithRootLatched; 53 import com.sleepycat.je.txn.LockType; 54 import com.sleepycat.je.txn.Txn; 55 import com.sleepycat.je.utilint.DbLsn; 56 import com.sleepycat.je.utilint.Tracer; 57 58 public class RecoveryManager { 59     private static final String TRACE_DUP_ROOT_REPLACE = 60         "DupRootRecover:"; 61     private static final String TRACE_LN_REDO = "LNRedo:"; 62     private static final String TRACE_LN_UNDO = "LNUndo"; 63     private static final String TRACE_IN_REPLACE = "INRecover:"; 64     private static final String TRACE_ROOT_REPLACE = "RootRecover:"; 65     private static final String TRACE_IN_DEL_REPLAY = "INDelReplay:"; 66     private static final String TRACE_IN_DUPDEL_REPLAY = "INDupDelReplay:"; 67     private static final String TRACE_ROOT_DELETE = "RootDelete:"; 68 69     private static final int CLEAR_INCREMENT = 50; 70 71     private EnvironmentImpl env; 72     private int readBufferSize; 73     private RecoveryInfo info; // stat info 74 private Set committedTxnIds; // committed txns 75 private Set abortedTxnIds; // aborted txns 76 private Map preparedTxns; // txnid -> prepared Txn 77 private Set inListRebuildDbIds; // dbs for which we have to rebuild the 78 // in memory IN list. 79 80     private Level detailedTraceLevel; // level value for detailed trace msgs 81 private Map fileSummaryLsns; // file number -> LSN of FileSummaryLN 82 private int inListClearCounter; // governs intermediate IN list clearing 83 84     /** 85      * Make a recovery manager 86      */ 87     public RecoveryManager(EnvironmentImpl env) 88         throws DatabaseException { 89 90         this.env = env; 91         DbConfigManager cm = env.getConfigManager(); 92         readBufferSize = 93             cm.getInt(EnvironmentParams.LOG_ITERATOR_READ_SIZE); 94         committedTxnIds = new HashSet (); 95         abortedTxnIds = new HashSet (); 96     preparedTxns = new HashMap (); 97         inListRebuildDbIds = new HashSet (); 98         fileSummaryLsns = new HashMap (); 99 100         /* 101          * Figure out the level to use for detailed trace messages, by choosing 102          * the more verbose of the recovery manager's trace setting vs the 103          * general trace setting. 104          */ 105         detailedTraceLevel = 106             Tracer.parseLevel(env, 107                               EnvironmentParams.JE_LOGGING_LEVEL_RECOVERY); 108     } 109      110     /** 111      * Look for an existing log and use it to create an in memory structure for 112      * accessing existing databases. The file manager and logging system are 113      * only available after recovery. 114      * @return RecoveryInfo statistics about the recovery process. 115      */ 116     public RecoveryInfo recover(boolean readOnly) 117         throws DatabaseException { 118 119         info = new RecoveryInfo(); 120 121         try { 122             FileManager fileManager = env.getFileManager(); 123         DbConfigManager configManager = env.getConfigManager(); 124         boolean forceCheckpoint = 125         configManager.getBoolean 126         (EnvironmentParams.ENV_RECOVERY_FORCE_CHECKPOINT); 127             if (fileManager.filesExist()) { 128 129                 /* 130                  * Establish the location of the end of the log. After this, we 131                  * can write to the log. No Tracer calls are allowed until 132                  * after this point is established in the log. 133                  */ 134                 findEndOfLog(readOnly); 135                 Tracer.trace(Level.CONFIG, env, 136                              "Recovery underway, found end of log"); 137          138                 /* 139                  * Establish the location of the root, the last checkpoint, and 140                  * the first active LSN by finding the last checkpoint. 141                  */ 142                 findLastCheckpoint(); 143         env.getLogManager().setLastLsnAtRecovery 144             (fileManager.getLastUsedLsn()); 145                 Tracer.trace(Level.CONFIG, env, 146                              "Recovery checkpoint search, " + 147                              info); 148 149                 /* Read in the root. */ 150                 env.readMapTreeFromLog(info.useRootLsn); 151 152                 /* Rebuild the in memory tree from the log. */ 153                 buildTree(); 154             } else { 155 156                 /* 157                  * Nothing more to be done. Enable publishing of debug log 158                  * messages to the database log. 159                  */ 160                 env.enableDebugLoggingToDbLog(); 161                 Tracer.trace(Level.CONFIG, env, "Recovery w/no files."); 162                 env.logMapTreeRoot(); 163 164         /* 165          * Always force a checkpoint during creation. 166          */ 167         forceCheckpoint = true; 168             } 169 170         if (preparedTxns.size() > 0) { 171         Tracer.trace(Level.INFO, env, 172                  "There are " + preparedTxns.size() + 173                  " prepared but unfinished txns."); 174 175         /* 176          * We don't need this set any more since these are all 177          * registered with the TxnManager now. 178          */ 179         preparedTxns = null; 180         } 181 182             /* 183              * Open the UP database and populate the cache before the first 184              * checkpoint so that the checkpoint may flush file summary 185              * information. May be disabled for unittests. 186              */ 187             if (DbInternal.getCreateUP 188                 (env.getConfigManager().getEnvironmentConfig())) { 189                 env.getUtilizationProfile().populateCache(); 190             } 191 192             /* 193              * At this point, we've recovered (or there were no log files at 194              * all. Write a checkpoint into the log. 195              * 196              * NOTE: The discussion of deltas below may be obsolete now that 197              * we use dirty bits to determine what to include in a delta. 198              * However, we still want to disallow deltas to flush full versions 199              * after a crash. 200              * 201              * Don't allow deltas, because the delta-determining scheme that 202              * compares child entries to the last full LSN doesn't work in 203              * recovery land. New child entries may have an earlier LSN than 204              * the owning BIN's last full, because of the act of splicing in 205              * LNs during recovery. 206              * 207              * For example, suppose that during LN redo, bin 10 was split into 208              * bin 10 and bin 12. That splitting causes a full log. Then later 209              * on, the redo splices LN x, which is from before the last full of 210              * bin 10, into bin 10. If we checkpoint allowing deltas after 211              * recovery finishes, we won't pick up the LNx diff, because that 212              * LN is an earlier LSN than the split-induced full log entry of 213              * bin 10. 214              */ 215             if (!readOnly && 216         (env.getLogManager().getLastLsnAtRecovery() != 217          info.checkpointEndLsn || 218          forceCheckpoint)) { 219                 CheckpointConfig config = new CheckpointConfig(); 220                 config.setForce(true); 221                 config.setMinimizeRecoveryTime(true); 222                 env.invokeCheckpoint 223                     (config, 224                      false, // flushAll 225 "recovery"); 226             } else { 227                 /* Initialze intervals when there is no initial checkpoint. */ 228                 env.getCheckpointer().initIntervals 229                     (info.checkpointEndLsn, System.currentTimeMillis()); 230             } 231 232         } catch (IOException e) { 233             Tracer.trace(env, "RecoveryManager", "recover", 234                          "Couldn't recover", e); 235             throw new RecoveryException(env, "Couldn't recover: " + 236                                         e.getMessage(), e); 237         } finally { 238         Tracer.trace(Level.CONFIG, env, "Recovery finished: " + info); 239         } 240 241         return info; 242     } 243 244     /** 245      * Find the end of the log, initialize the FileManager. While we're 246      * perusing the log, return the last checkpoint LSN if we happen to see it. 247      */ 248     private void findEndOfLog(boolean readOnly) 249         throws IOException , DatabaseException { 250 251         LastFileReader reader = new LastFileReader(env, readBufferSize); 252 253         /* 254          * Tell the reader to iterate through the log file until we hit the end 255          * of the log or an invalid entry. 256          * Remember the last seen CkptEnd, and the first CkptStart with no 257          * following CkptEnd. 258          */ 259         while (reader.readNextEntry()) { 260             LogEntryType type = reader.getEntryType(); 261             if (LogEntryType.LOG_CKPT_END.equals(type)) { 262                 info.checkpointEndLsn = reader.getLastLsn(); 263                 info.partialCheckpointStartLsn = DbLsn.NULL_LSN; 264             } else if (LogEntryType.LOG_CKPT_START.equals(type)) { 265                 if (info.partialCheckpointStartLsn == DbLsn.NULL_LSN) { 266                     info.partialCheckpointStartLsn = reader.getLastLsn(); 267                 } 268             } 269         } 270 271         /* 272          * The last valid lsn should point to the start of the last valid log entry, 273          * while the end of the log should point to the first byte of blank space, 274          * so these two should not be the same. 275          */ 276         assert (reader.getLastValidLsn() != reader.getEndOfLog()): 277             "lastUsed=" + DbLsn.getNoFormatString(reader.getLastValidLsn()) + 278             " end=" + DbLsn.getNoFormatString(reader.getEndOfLog()); 279 280 281         /* Now truncate if necessary. */ 282         if (!readOnly) { 283             reader.setEndOfFile(); 284         } 285 286         /* Tell the fileManager where the end of the log is. */ 287         info.lastUsedLsn = reader.getLastValidLsn(); 288         info.nextAvailableLsn = reader.getEndOfLog(); 289         info.nRepeatIteratorReads += reader.getNRepeatIteratorReads(); 290         env.getFileManager().setLastPosition(info.nextAvailableLsn, 291                                              info.lastUsedLsn, 292                                              reader.getPrevOffset()); 293 294         /* 295          * Now the logging system is initialized and can do more 296          * logging. Enable publishing of debug log messages to the database 297          * log. 298          */ 299         env.enableDebugLoggingToDbLog(); 300     } 301 302     /** 303      * Find the last checkpoint and establish the firstActiveLsn point, 304      * checkpoint start, and checkpoint end. 305      */ 306     private void findLastCheckpoint() 307         throws IOException , DatabaseException { 308 309         /* 310          * The checkpointLsn might have been already found when establishing 311          * the end of the log. If it was found, then partialCheckpointStartLsn 312          * was also found. If it was not found, search backwards for it now 313          * and also set partialCheckpointStartLsn. 314          */ 315         if (info.checkpointEndLsn == DbLsn.NULL_LSN) { 316              317             /* 318              * Search backwards though the log for a checkpoint end entry and a 319              * root entry. 320              */ 321             CheckpointFileReader searcher = 322                 new CheckpointFileReader(env, readBufferSize, false, 323                                          info.lastUsedLsn, DbLsn.NULL_LSN, 324                                          info.nextAvailableLsn); 325 326             while (searcher.readNextEntry()) { 327 328                 /* 329                  * Continue iterating until we find a checkpoint end entry. 330                  * While we're at it, remember the last root seen in case we 331                  * don't find a checkpoint end entry. 332                  */ 333                 if (searcher.isCheckpointEnd()) { 334 335                     /* 336                      * We're done, the checkpoint end will tell us where the 337                      * root is. 338                      */ 339                     info.checkpointEndLsn = searcher.getLastLsn(); 340                     break; 341                 } else if (searcher.isCheckpointStart()) { 342 343                     /* 344                      * Remember the first CkptStart following the CkptEnd. 345                      */ 346                     info.partialCheckpointStartLsn = searcher.getLastLsn(); 347 348                 } else if (searcher.isRoot()) { 349 350                     /* 351                      * Save the last root that was found in the log in case we 352                      * don't see a checkpoint. 353                      */ 354                     if (info.useRootLsn == DbLsn.NULL_LSN) { 355                         info.useRootLsn = searcher.getLastLsn(); 356                     } 357                 } 358             } 359             info.nRepeatIteratorReads += searcher.getNRepeatIteratorReads(); 360         } 361 362         /* 363          * If we haven't found a checkpoint, we'll have to recover without 364          * one. At a minimium, we must have found a root. 365          */ 366         if (info.checkpointEndLsn == DbLsn.NULL_LSN) { 367             info.checkpointStartLsn = DbLsn.NULL_LSN; 368             info.firstActiveLsn = DbLsn.NULL_LSN; 369         } else { 370             /* Read in the checkpoint entry. */ 371             CheckpointEnd checkpointEnd = 372                 (CheckpointEnd) (env.getLogManager().get 373                  (info.checkpointEndLsn)); 374             info.checkpointEnd = checkpointEnd; 375             info.checkpointStartLsn = checkpointEnd.getCheckpointStartLsn(); 376             info.firstActiveLsn = checkpointEnd.getFirstActiveLsn(); 377             if (checkpointEnd.getRootLsn() != DbLsn.NULL_LSN) { 378                 info.useRootLsn = checkpointEnd.getRootLsn(); 379             } 380 381             /* Init the checkpointer's id sequence and FirstActiveLsn.*/ 382             env.getCheckpointer().setCheckpointId(checkpointEnd.getId()); 383             env.getCheckpointer().setFirstActiveLsn 384                 (checkpointEnd.getFirstActiveLsn()); 385         } 386         if (info.useRootLsn == DbLsn.NULL_LSN) { 387             throw new NoRootException 388         (env, 389          "This environment's log file has no root. Since the root " + 390          "is the first entry written into a log at environment " + 391          "creation, this should only happen if the initial creation " + 392          "of the environment was never checkpointed or synced. " + 393          "Please move aside the existing log files to allow the " + 394          "creation of a new environment"); 395         } 396     } 397 398     /** 399      * Use the log to recreate an in memory tree. 400      */ 401     private void buildTree() 402         throws IOException , DatabaseException { 403 404         inListClearCounter = 0; 405 406         /* 407          * Read all map database INs, find largest node id before any 408          * possiblity of splits, find largest txn Id before any need for a root 409          * update (which would use an AutoTxn) 410          */ 411         int passNum = buildINs(1, 412                                true, /* mapping tree */ 413                                false); /* dup tree */ 414 415 416         /* 417          * Undo all aborted map LNs. Read and remember all committed 418          * transaction ids. 419          */ 420         Tracer.trace(Level.CONFIG, env, passStartHeader(passNum) + 421                      "undo map LNs"); 422     long start = System.currentTimeMillis(); 423         Set mapLNSet = new HashSet (); 424         mapLNSet.add(LogEntryType.LOG_MAPLN_TRANSACTIONAL); 425         mapLNSet.add(LogEntryType.LOG_TXN_COMMIT); 426         mapLNSet.add(LogEntryType.LOG_TXN_ABORT); 427         mapLNSet.add(LogEntryType.LOG_TXN_PREPARE); 428         undoLNs(info, mapLNSet); 429     long end = System.currentTimeMillis(); 430         Tracer.trace(Level.CONFIG, env, passEndHeader(passNum, start, end) + 431              info.toString()); 432         passNum++; 433 434         /* 435          * Replay all mapLNs, mapping tree in place now. Use the set of 436          * committed txns found from the undo pass. 437          */ 438         Tracer.trace(Level.CONFIG, env, passStartHeader(passNum) + 439                      "redo map LNs"); 440     start = System.currentTimeMillis(); 441         mapLNSet.add(LogEntryType.LOG_MAPLN); 442         redoLNs(info, mapLNSet); 443     end = System.currentTimeMillis(); 444         Tracer.trace(Level.CONFIG, env, passEndHeader(passNum, start, end) + 445              info.toString()); 446         passNum++; 447 448         /* 449          * Reconstruct the internal nodes for the main level trees. 450          */ 451         passNum = buildINs(passNum, 452                            false, /* mapping tree*/ 453                            false); /* dup tree */ 454 455         /* 456          * Reconstruct the internal nodes for the duplicate level trees. 457          */ 458         passNum = buildINs(passNum, 459                            false, /* mapping tree*/ 460                            true); /* dup tree */ 461 462         /* 463          * Rebuild the in memory IN list. Once the tree is complete we can 464          * invoke the evictor. The evictor will also be invoked during the 465          * undo and redo passes. 466          */ 467         rebuildINList(); 468         env.invokeEvictor(); 469 470         /* 471          * Undo aborted LNs. No need to collect committed txn ids again, was 472          * done in the undo of all aborted MapLNs. 473          */ 474         Tracer.trace(Level.CONFIG, env, passStartHeader(9) + "undo LNs"); 475     start = System.currentTimeMillis(); 476         Set lnSet = new HashSet (); 477         lnSet.add(LogEntryType.LOG_LN_TRANSACTIONAL); 478         lnSet.add(LogEntryType.LOG_NAMELN_TRANSACTIONAL); 479         lnSet.add(LogEntryType.LOG_DEL_DUPLN_TRANSACTIONAL); 480         lnSet.add(LogEntryType.LOG_DUPCOUNTLN_TRANSACTIONAL); 481 482         undoLNs(info, lnSet); 483     end = System.currentTimeMillis(); 484         Tracer.trace(Level.CONFIG, env, passEndHeader(9, start, end) + 485              info.toString()); 486 487         /* Replay LNs. Also read non-transactional LNs. */ 488         Tracer.trace(Level.CONFIG, env, passStartHeader(10) + "redo LNs"); 489     start = System.currentTimeMillis(); 490         lnSet.add(LogEntryType.LOG_LN); 491         lnSet.add(LogEntryType.LOG_NAMELN); 492         lnSet.add(LogEntryType.LOG_DEL_DUPLN); 493         lnSet.add(LogEntryType.LOG_DUPCOUNTLN); 494         lnSet.add(LogEntryType.LOG_FILESUMMARYLN); 495         redoLNs(info, lnSet); 496     end = System.currentTimeMillis(); 497         Tracer.trace(Level.CONFIG, env, passEndHeader(10, start, end) + 498              info.toString()); 499     } 500 501     /* 502      * Up to three passes for the INs of a given level 503      * @param mappingTree if true, we're rebuilding the mapping tree 504      * @param dupTree if true, we're rebuilding the dup tree. 505      */ 506     private int buildINs(int passNum, 507                          boolean mappingTree, 508                          boolean dupTree) 509         throws IOException , DatabaseException { 510 511         Set targetEntries = new HashSet (); 512         Set deltaType = new HashSet (); 513         String passADesc = null; 514         String passBDesc = null; 515         String passCDesc = null; 516 517         if (mappingTree) { 518             passADesc = "read mapping INs"; 519             passBDesc = "redo mapping INs"; 520             passCDesc = "read mapping BINDeltas"; 521         } else if (dupTree) { 522             passADesc = "read dup INs"; 523             passBDesc = "redo dup INs"; 524             passCDesc = "read dup BINDeltas"; 525         } else { 526             passADesc = "read main INs"; 527             passBDesc = "redo main INs"; 528             passCDesc = "read main BINDeltas"; 529         } 530 531         if (dupTree) { 532             /* Duplicate trees read these entries. */ 533             targetEntries.add(LogEntryType.LOG_DIN); 534             targetEntries.add(LogEntryType.LOG_DBIN); 535             targetEntries.add(LogEntryType.LOG_IN_DUPDELETE_INFO); 536             deltaType.add(LogEntryType.LOG_DUP_BIN_DELTA); 537         } else { 538             /* Main tree and mapping tree read these types of entries. */ 539             targetEntries.add(LogEntryType.LOG_IN); 540             targetEntries.add(LogEntryType.LOG_BIN); 541             targetEntries.add(LogEntryType.LOG_IN_DELETE_INFO); 542             deltaType.add(LogEntryType.LOG_BIN_DELTA); 543         } 544 545         /* 546          * Pass a: Read all INs and place into the proper location. 547          */ 548         Tracer.trace(Level.CONFIG, env, passStartHeader(passNum) + passADesc); 549         LevelRecorder recorder = new LevelRecorder(); 550     long start = System.currentTimeMillis(); 551         if (mappingTree) { 552             readINsAndTrackIds(info.checkpointStartLsn, recorder); 553         } else { 554             int numINsSeen = readINs(info.checkpointStartLsn, 555                                      false, // mapping tree only 556 targetEntries, 557                                      /* 558                                       * requireExactMatch -- why is it true 559                                       * for dups, false for main tree? 560                                       * Keeping logic the same for now. 561                                       */ 562                                      (dupTree? true: false), 563                                      recorder); 564             if (dupTree) { 565                 info.numDuplicateINs += numINsSeen; 566             } else { 567                 info.numOtherINs += numINsSeen; 568             } 569         } 570     long end = System.currentTimeMillis(); 571         Tracer.trace(Level.CONFIG, env, passEndHeader(passNum, start, end) + 572              info.toString()); 573         passNum++; 574 575         /* 576          * Pass b: Redo INs if the LevelRecorder detects a split/compression 577          * was done after ckpt [#14424] 578          */ 579         Set redoSet = recorder.getDbsWithDifferentLevels(); 580         if (redoSet.size() > 0) { 581             Tracer.trace(Level.CONFIG, env, 582                          passStartHeader(passNum) + passBDesc); 583             start = System.currentTimeMillis(); 584             repeatReadINs(info.checkpointStartLsn, 585                           targetEntries, 586                           redoSet); 587             end = System.currentTimeMillis(); 588             Tracer.trace(Level.CONFIG, env, 589                          passEndHeader(passNum, start, end) + info.toString()); 590             passNum++; 591         } 592 593         /* 594          * Pass c: Read BIN Deltas. 595          * BINDeltas must be processed after all INs so the delta is properly 596          * applied to the last version. For example, suppose BINDeltas were not 597          * done in a later pass, the tree is INa->BINb, and the log has 598          * INa 599          * BINDelta for BINb 600          * INa 601          * the splicing in of the second INa would override the BINDelta. 602          */ 603         Tracer.trace(Level.CONFIG, env, passStartHeader(passNum) + passCDesc); 604     start = System.currentTimeMillis(); 605         info.numBinDeltas += readINs(info.checkpointStartLsn, 606                                      mappingTree, 607                                      deltaType, 608                                      true, // requireExactMatch 609 null); // LevelRecorder 610 end = System.currentTimeMillis(); 611         Tracer.trace(Level.CONFIG, env, 612                      passEndHeader(passNum, start, end) + info.toString()); 613         passNum++; 614 615         return passNum; 616     } 617 618     /* 619      * Read every internal node and IN DeleteInfo in the mapping tree and place 620      * in the in-memory tree. 621      */ 622     private void readINsAndTrackIds(long rollForwardLsn, 623                                     LevelRecorder recorder) 624         throws IOException , DatabaseException { 625 626         INFileReader reader = 627             new INFileReader(env, 628                              readBufferSize, 629                              rollForwardLsn, // start lsn 630 info.nextAvailableLsn, // end lsn 631 true, // track node and db ids 632 false, // map db only 633 info.partialCheckpointStartLsn, 634                              fileSummaryLsns); 635         reader.addTargetType(LogEntryType.LOG_IN); 636         reader.addTargetType(LogEntryType.LOG_BIN); 637         reader.addTargetType(LogEntryType.LOG_IN_DELETE_INFO); 638 639         /* Validate all entries in at least one full recovery pass. */ 640         reader.setAlwaysValidateChecksum(true); 641 642         try { 643             info.numMapINs = 0; 644             DbTree dbMapTree = env.getDbMapTree(); 645 646             /* 647          * Process every IN, INDeleteInfo, and INDupDeleteInfo in the 648          * mapping tree. 649          */ 650             while (reader.readNextEntry()) { 651                 DatabaseId dbId = reader.getDatabaseId(); 652                 if (dbId.equals(DbTree.ID_DB_ID)) { 653                     DatabaseImpl db = dbMapTree.getDb(dbId); 654                     replayOneIN(reader, db, false, recorder); 655                     info.numMapINs++; 656                 } 657             } 658 659             /* 660              * Update node id and database sequences. Use either the maximum of 661              * the ids seen by the reader vs the ids stored in the checkpoint. 662              */ 663             info.useMaxNodeId = reader.getMaxNodeId(); 664             info.useMaxDbId = reader.getMaxDbId(); 665             info.useMaxTxnId = reader.getMaxTxnId(); 666             if (info.checkpointEnd != null) { 667                 if (info.useMaxNodeId < info.checkpointEnd.getLastNodeId()) { 668                     info.useMaxNodeId = info.checkpointEnd.getLastNodeId(); 669                 } 670                 if (info.useMaxDbId < info.checkpointEnd.getLastDbId()) { 671                     info.useMaxDbId = info.checkpointEnd.getLastDbId(); 672                 } 673                 if (info.useMaxTxnId < info.checkpointEnd.getLastTxnId()) { 674                     info.useMaxTxnId = info.checkpointEnd.getLastTxnId(); 675                 } 676             } 677 678             Node.setLastNodeId(info.useMaxNodeId); 679             env.getDbMapTree().setLastDbId(info.useMaxDbId); 680             env.getTxnManager().setLastTxnId(info.useMaxTxnId); 681 682             info.nRepeatIteratorReads += reader.getNRepeatIteratorReads(); 683         } catch (Exception e) { 684             traceAndThrowException(reader.getLastLsn(), "readMapIns", e); 685         } 686     } 687 688     /** 689      * Read INs and process. 690      */ 691     private int readINs(long rollForwardLsn, 692                         boolean mapDbOnly, 693                         Set targetLogEntryTypes, 694                         boolean requireExactMatch, 695                         LevelRecorder recorder) 696         throws IOException , DatabaseException { 697 698         // don't need to track NodeIds 699 INFileReader reader = 700         new INFileReader(env, 701                              readBufferSize, 702                              rollForwardLsn, // startlsn 703 info.nextAvailableLsn, // finish 704 false, 705                  mapDbOnly, 706                              info.partialCheckpointStartLsn, 707                              fileSummaryLsns); 708 709         Iterator iter = targetLogEntryTypes.iterator(); 710         while (iter.hasNext()) { 711             reader.addTargetType((LogEntryType) iter.next()); 712         } 713 714         int numINsSeen = 0; 715         try { 716 717             /* 718              * Read all non-provisional INs, and process if they don't belong 719              * to the mapping tree. 720              */ 721             DbTree dbMapTree = env.getDbMapTree(); 722             while (reader.readNextEntry()) { 723                 DatabaseId dbId = reader.getDatabaseId(); 724                 boolean isMapDb = dbId.equals(DbTree.ID_DB_ID); 725                 boolean isTarget = false; 726 727                 if (mapDbOnly && isMapDb) { 728                     isTarget = true; 729                 } else if (!mapDbOnly && !isMapDb) { 730                     isTarget = true; 731                 } 732                 if (isTarget) { 733                     DatabaseImpl db = dbMapTree.getDb(dbId); 734                     if (db == null) { 735                         // This db has been deleted, ignore the entry. 736 } else { 737                         replayOneIN(reader, db, requireExactMatch, recorder); 738                         numINsSeen++; 739 740                         /* 741                          * Add any db that we encounter IN's for because 742                          * they'll be part of the in-memory tree and therefore 743                          * should be included in the INList rebuild. 744                          */ 745                         inListRebuildDbIds.add(dbId); 746                     } 747                 } 748             } 749 750             info.nRepeatIteratorReads += reader.getNRepeatIteratorReads(); 751             return numINsSeen; 752         } catch (Exception e) { 753             traceAndThrowException(reader.getLastLsn(), "readNonMapIns", e); 754             return 0; 755         } 756     } 757 758     /** 759      * Read INs and process. 760      */ 761     private void repeatReadINs(long rollForwardLsn, 762                                Set targetLogEntryTypes, 763                                Set targetDbs) 764         throws IOException , DatabaseException { 765 766         // don't need to track NodeIds 767 INFileReader reader = 768         new INFileReader(env, 769                              readBufferSize, 770                              rollForwardLsn, // startlsn 771 info.nextAvailableLsn, // finish 772 false, 773                              false, // mapDbOnly 774 info.partialCheckpointStartLsn, 775                              fileSummaryLsns); 776 777         Iterator iter = targetLogEntryTypes.iterator(); 778         while (iter.hasNext()) { 779             reader.addTargetType((LogEntryType) iter.next()); 780         } 781 782         try { 783 784             /* Read all non-provisional INs that are in the repeat set. */ 785             DbTree dbMapTree = env.getDbMapTree(); 786             while (reader.readNextEntry()) { 787                 DatabaseId dbId = reader.getDatabaseId(); 788                 if (targetDbs.contains(dbId)) { 789                     DatabaseImpl db = dbMapTree.getDb(dbId); 790                     if (db == null) { 791                         // This db has been deleted, ignore the entry. 792 } else { 793                         replayOneIN(reader, 794                                     db, 795                                     true, // requireExactMatch, 796 null); // level recorder 797 } 798                 } 799             } 800 801             info.nRepeatIteratorReads += reader.getNRepeatIteratorReads(); 802         } catch (Exception e) { 803             traceAndThrowException(reader.getLastLsn(), "readNonMapIns", e); 804         } 805     } 806 807     /** 808      * Get an IN from the reader, set its database, and fit into tree. 809      */ 810     private void replayOneIN(INFileReader reader, 811                              DatabaseImpl db, 812                              boolean requireExactMatch, 813                              LevelRecorder recorder) 814         throws DatabaseException { 815          816         if (reader.isDeleteInfo()) { 817             /* Last entry is a delete, replay it. */ 818             replayINDelete(db, 819                            reader.getDeletedNodeId(), 820                            false, 821                            reader.getDeletedIdKey(), 822                            null, 823                            reader.getLastLsn()); 824         } else if (reader.isDupDeleteInfo()) { 825             /* Last entry is a dup delete, replay it. */ 826             replayINDelete(db, 827                            reader.getDupDeletedNodeId(), 828                            true, 829                            reader.getDupDeletedMainKey(), 830                            reader.getDupDeletedDupKey(), 831                            reader.getLastLsn()); 832         } else { 833 834             /* 835          * Last entry is a node, replay it. Now, we should really call 836          * IN.postFetchInit, but we want to do something different from the 837          * faulting-in-a-node path, because we don't want to put the IN on 838          * the in memory list, and we don't want to search the db map tree, 839          * so we have a IN.postRecoveryInit. Note also that we have to 840          * pass the LSN of the current log entry and also the LSN of the IN 841          * in question. The only time these differ is when the log entry is 842          * a BINDelta -- then the IN's LSN is the last full version LSN, 843          * and the log LSN is the current log entry. 844              */ 845             IN in = reader.getIN(); 846             long inLsn = reader.getLsnOfIN(); 847             in.postRecoveryInit(db, inLsn); 848             in.latch(); 849 850             /* 851              * track the levels, in case we need an extra splits vs ckpt 852              * reconcilliation. 853              */ 854             if (recorder != null) { 855                 recorder.record(db.getId(), in.getLevel()); 856             } 857             replaceOrInsert(db, in, reader.getLastLsn(), inLsn, 858                             requireExactMatch); 859         } 860 861         /* 862      * Although we're careful to not place INs instantiated from the log on 863      * the IN list, we do call normal tree search methods when checking 864      * agains the active tree. The INList builds up from the faulting in of 865      * nodes this way. However, some of those nodes become obsolete as we 866      * splice in newer versions, so the INList becomes too large and can 867      * pose a problem by causing us to overflow memory bounds. Some 868      * possible solutions are to create an environment wide recovery mode, 869      * or to put special logic into the normal faulting-in path to know 870      * that we're in recovery. Because we don't want to impact normal code 871      * paths, we're going to just periodically clear the INList here. The 872      * INList will be regenerated at the end of recovery. 873          */ 874         if ((++inListClearCounter % CLEAR_INCREMENT) == 0) { 875             env.getInMemoryINs().clear(); 876         } 877     } 878 879     /** 880      * Undo all aborted LNs. To do so, walk the log backwards, keeping a 881      * collection of committed txns. If we see a log entry that doesn't have a 882      * committed txn, undo it. 883      */ 884     private void undoLNs(RecoveryInfo info, Set lnTypes) 885         throws IOException , DatabaseException { 886 887     long firstActiveLsn = info.firstActiveLsn; 888     long lastUsedLsn = info.lastUsedLsn; 889     long endOfFileLsn = info.nextAvailableLsn; 890         /* Set up a reader to pick up target log entries from the log. */ 891         LNFileReader reader = 892             new LNFileReader(env, readBufferSize, lastUsedLsn, 893                              false, endOfFileLsn, firstActiveLsn, null); 894 895         Iterator iter = lnTypes.iterator(); 896         while (iter.hasNext()) { 897             LogEntryType lnType = (LogEntryType) iter.next(); 898             reader.addTargetType(lnType); 899         } 900 901         Map countedFileSummaries = new HashMap (); // TxnNodeId -> file number 902 Set countedAbortLsnNodes = new HashSet (); // set of TxnNodeId 903 904         DbTree dbMapTree = env.getDbMapTree(); 905         TreeLocation location = new TreeLocation(); 906         try { 907 908             /* 909              * Iterate over the target LNs and commit records, constructing 910              * tree. 911              */ 912             while (reader.readNextEntry()) { 913                 if (reader.isLN()) { 914 915                     /* Get the txnId from the log entry. */ 916                     Long txnId = reader.getTxnId(); 917 918                     /* 919                      * If this node is not in a committed txn, examine it to 920                      * see if it should be undone. 921                      */ 922                     if (txnId != null && 923             !committedTxnIds.contains(txnId)) { 924 925             /* 926              * Invoke the evictor to reduce memory consumption. 927              */ 928             env.invokeEvictor(); 929 930             LN ln = reader.getLN(); 931             long logLsn = reader.getLastLsn(); 932             long abortLsn = reader.getAbortLsn(); 933             boolean abortKnownDeleted = 934                 reader.getAbortKnownDeleted(); 935             DatabaseId dbId = reader.getDatabaseId(); 936             DatabaseImpl db = dbMapTree.getDb(dbId); 937                          938             /* Database may be null if it's been deleted. */ 939             if (db != null) { 940                 ln.postFetchInit(db, logLsn); 941                 try { 942                                 undo(detailedTraceLevel, 943                                      db, 944                                      location, 945                                      ln, 946                                      reader.getKey(), 947                                      reader.getDupTreeKey(), 948                                      logLsn, 949                                      abortLsn, 950                                      abortKnownDeleted, 951                                      info, 952                                      true); 953                 } finally { 954                 if (location.bin != null) { 955                     location.bin.releaseLatchIfOwner(); 956                 } 957                 } 958                 /* Undo utilization info. */ 959                 TxnNodeId txnNodeId = 960                 new TxnNodeId(reader.getNodeId(), 961                           txnId.longValue()); 962                 undoUtilizationInfo(ln, logLsn, abortLsn, 963                         abortKnownDeleted, 964                                                 reader.getLastEntrySize(), 965                         txnNodeId, 966                         countedFileSummaries, 967                         countedAbortLsnNodes); 968 969                 /* 970                  * Add any db that we encounter LN's for because 971                  * they'll be part of the in-memory tree and 972                  * therefore should be included in the INList 973                  * rebuild. 974                  */ 975                 inListRebuildDbIds.add(dbId); 976             } 977             } 978                 } else if (reader.isPrepare()) { 979 980             /* 981              * The entry just read is a prepare record. There should 982              * be no lock conflicts during recovery, but just in case 983              * there are, we set the locktimeout to 0. 984              */ 985             long prepareId = reader.getTxnPrepareId(); 986             Long prepareIdL = new Long (prepareId); 987             if (!committedTxnIds.contains(prepareIdL) && 988             !abortedTxnIds.contains(prepareIdL)) { 989             TransactionConfig txnConf = new TransactionConfig(); 990             Txn preparedTxn = new Txn(env, txnConf, prepareId); 991             preparedTxn.setLockTimeout(0); 992             preparedTxns.put(prepareIdL, preparedTxn); 993             env.getTxnManager().registerXATxn 994                 (reader.getTxnPrepareXid(), preparedTxn, true); 995             Tracer.trace(Level.INFO, env, 996                      "Found unfinished prepare record: id: " + 997                      reader.getTxnPrepareId() + 998                      " Xid: " + reader.getTxnPrepareXid()); 999             } 1000                } else if (reader.isAbort()) { 1001            /* The entry just read is an abort record. */ 1002            abortedTxnIds.add(new Long (reader.getTxnAbortId())); 1003        } else { 1004                    /* The entry just read is a commit record. */ 1005                    committedTxnIds.add(new Long (reader.getTxnCommitId())); 1006                } 1007            } 1008            info.nRepeatIteratorReads += reader.getNRepeatIteratorReads(); 1009        } catch (RuntimeException e) { 1010            traceAndThrowException(reader.getLastLsn(), "undoLNs", e); 1011        } 1012    } 1013 1014    /** 1015     * Apply all committed LNs. 1016     * @param rollForwardLsn start redoing from this point 1017     * @param lnType1 targetted LN 1018     * @param lnType2 targetted LN 1019     */ 1020    private void redoLNs(RecoveryInfo info, Set lnTypes) 1021        throws IOException , DatabaseException { 1022 1023    long endOfFileLsn = info.nextAvailableLsn; 1024    long rollForwardLsn = info.checkpointStartLsn; 1025        /* Set up a reader to pick up target log entries from the log */ 1026        LNFileReader reader = 1027            new LNFileReader(env, readBufferSize, rollForwardLsn, 1028                             true, DbLsn.NULL_LSN, endOfFileLsn, null); 1029 1030        Iterator iter = lnTypes.iterator(); 1031        while (iter.hasNext()) { 1032            LogEntryType lnType = (LogEntryType) iter.next(); 1033            reader.addTargetType(lnType); 1034        } 1035 1036        Set countedAbortLsnNodes = new HashSet (); // set of TxnNodeId 1037 1038        DbTree dbMapTree = env.getDbMapTree(); 1039        TreeLocation location = new TreeLocation(); 1040        try { 1041 1042            /* Iterate over the target LNs and construct in- memory tree. */ 1043            while (reader.readNextEntry()) { 1044                if (reader.isLN()) { 1045 1046                    /* Get the txnId from the log entry. */ 1047                    Long txnId = reader.getTxnId(); 1048                 1049                    /* 1050                     * If this LN is in a committed txn, or if it's a 1051                     * non-transactional LN, redo it. 1052                     */ 1053            boolean processThisLN = false; 1054            boolean lnIsCommitted = false; 1055            boolean lnIsPrepared = false; 1056            Txn preparedTxn = null; 1057            if (txnId == null) { 1058            processThisLN = true; 1059            } else { 1060            lnIsCommitted = committedTxnIds.contains(txnId); 1061            if (!lnIsCommitted) { 1062                preparedTxn = (Txn) preparedTxns.get(txnId); 1063                lnIsPrepared = preparedTxn != null; 1064            } 1065            if (lnIsCommitted || lnIsPrepared) { 1066                processThisLN = true; 1067            } 1068            } 1069            if (processThisLN) { 1070 1071                        /* Invoke the evictor to reduce memory consumption. */ 1072                        env.invokeEvictor(); 1073 1074                        LN ln = reader.getLN(); 1075                        DatabaseId dbId = reader.getDatabaseId(); 1076                        DatabaseImpl db = dbMapTree.getDb(dbId); 1077                        long logLsn = reader.getLastLsn(); 1078                        long treeLsn = DbLsn.NULL_LSN; 1079 1080                        /* Database may be null if it's been deleted. */ 1081                        if (db != null) { 1082                            ln.postFetchInit(db, logLsn); 1083 1084                if (preparedTxn != null) { 1085                preparedTxn.addLogInfo(logLsn); 1086 1087                /* 1088                 * We're reconstructing a prepared, but not 1089                 * finished, transaction. We know that there 1090                 * was a write lock on this LN since it exists 1091                 * in the log under this txnId. 1092                 */ 1093                preparedTxn.lock 1094                                    (ln.getNodeId(), LockType.WRITE, 1095                                     false /*noWait*/, db); 1096                preparedTxn.setPrepared(true); 1097                } 1098 1099                            treeLsn = redo(db, 1100                                           location, 1101                                           ln, 1102                                           reader.getKey(), 1103                                           reader.getDupTreeKey(), 1104                                           logLsn, 1105                                           info); 1106 1107                            /* 1108                             * Add any db that we encounter LN's for because 1109                             * they'll be part of the in-memory tree and 1110                             * therefore should be included in the INList 1111                             * rebuild. 1112                             */ 1113                            inListRebuildDbIds.add(dbId); 1114                        } 1115 1116                        /* Redo utilization info. */ 1117                        TxnNodeId txnNodeId = null; 1118                        if (txnId != null) { 1119                            txnNodeId = new TxnNodeId(reader.getNodeId(), 1120                                                      txnId.longValue()); 1121                        } 1122                        redoUtilizationInfo(logLsn, treeLsn, 1123                                            reader.getAbortLsn(), 1124                                            reader.getAbortKnownDeleted(), 1125                                            reader.getLastEntrySize(), 1126                                            reader.getKey(), 1127                                            ln, txnNodeId, 1128                                            countedAbortLsnNodes); 1129                    } 1130                } 1131            } 1132            info.nRepeatIteratorReads += reader.getNRepeatIteratorReads(); 1133        } catch (Exception e) { 1134            traceAndThrowException(reader.getLastLsn(), "redoLns", e); 1135        } 1136    } 1137 1138    /** 1139     * Rebuild the in memory inList with INs that have been made resident by 1140     * the recovery process. 1141     */ 1142    private void rebuildINList() 1143        throws DatabaseException { 1144 1145        env.getInMemoryINs().clear(); // empty out 1146 env.getDbMapTree().rebuildINListMapDb(); // scan map db 1147 1148        /* For all the dbs that we read in recovery, scan for resident INs. */ 1149        Iterator iter = inListRebuildDbIds.iterator(); 1150        while (iter.hasNext()) { 1151            DatabaseId dbId = (DatabaseId) iter.next(); 1152            /* We already did the map tree, don't do it again. */ 1153            if (!dbId.equals(DbTree.ID_DB_ID)) { 1154                DatabaseImpl db = env.getDbMapTree().getDb(dbId); 1155        if (db != null) { 1156            db.getTree().rebuildINList(); 1157        } 1158            } 1159        } 1160    } 1161 1162    /* Struct to hold a nodeId/txnId tuple */ 1163    private static class TxnNodeId { 1164        long nodeId; 1165        long txnId; 1166         1167        TxnNodeId(long nodeId, long txnId) { 1168            this.nodeId = nodeId; 1169            this.txnId = txnId; 1170        } 1171 1172        /** 1173         * Compare two TxnNodeId objects 1174         */ 1175        public boolean equals(Object obj) { 1176            if (this == obj) { 1177                return true; 1178            } 1179 1180            if (!(obj instanceof TxnNodeId)) { 1181                return false; 1182            } 1183 1184            return ((((TxnNodeId) obj).txnId == txnId) && 1185                    (((TxnNodeId) obj).nodeId == nodeId)); 1186        } 1187 1188        public int hashCode() { 1189            return (int) (txnId + nodeId); 1190        } 1191 1192        public String toString() { 1193            return "txnId=" + txnId + "/nodeId=" + nodeId; 1194        } 1195    } 1196 1197    /* 1198     * Tree manipulation methods. 1199     */ 1200 1201    /** 1202     * Recover an internal node. If inFromLog is: 1203     * - not found, insert it in the appropriate location. 1204     * - if found and there is a physical match (LSNs are the same) 1205     * do nothing. 1206     * - if found and there is a logical match (LSNs are different, 1207     * another version of this IN is in place, replace the found node 1208     * with the node read from the log only if the log version's 1209     * LSN is greater. 1210     * InFromLog should be latched upon entering this method and it will 1211     * not be latched upon exiting. 1212     * 1213     * @param inFromLog - the new node to put in the tree. The identifier key 1214     * and node id are used to find the existing version of the node. 1215     * @param logLsn - the location of log entry in in the log. 1216     * @param inLsn LSN of this in -- may not be the same as the log LSN if 1217     * the current entry is a BINDelta 1218     * @param requireExactMatch - true if we won't place this node in the tree 1219     * unless we find exactly that parent. Used for BINDeltas, where we want 1220     * to only apply the BINDelta to that exact node. 1221     */ 1222    private void replaceOrInsert(DatabaseImpl db, 1223                                 IN inFromLog, 1224                                 long logLsn, 1225                                 long inLsn, 1226                                 boolean requireExactMatch) 1227        throws DatabaseException { 1228 1229        List trackingList = null; 1230    boolean inFromLogLatchReleased = false; 1231        try { 1232 1233            /* 1234             * We must know a priori if this node is the root. We can't infer 1235             * that status from a search of the existing tree, because 1236             * splitting the root is done by putting a node above the old root. 1237             * A search downward would incorrectly place the new root below the 1238             * existing tree. 1239             */ 1240            if (inFromLog.isRoot()) { 1241                if (inFromLog.containsDuplicates()) { 1242                    replaceOrInsertDuplicateRoot(db, (DIN) inFromLog, logLsn); 1243                } else { 1244                    replaceOrInsertRoot(db, inFromLog, logLsn); 1245            inFromLogLatchReleased = true; 1246                } 1247            } else { 1248                /* 1249                 * Look for a parent. The call to getParentNode unlatches node. 1250                 * Then place inFromLog in the tree if appropriate. 1251                 */ 1252                trackingList = new ArrayList (); 1253                replaceOrInsertChild(db, inFromLog, logLsn, inLsn, 1254                                     trackingList, requireExactMatch); 1255        inFromLogLatchReleased = true; 1256            } 1257        } catch (Exception e) { 1258            String trace = printTrackList(trackingList); 1259            Tracer.trace(db.getDbEnvironment(), "RecoveryManager", 1260                         "replaceOrInsert", " lsnFromLog:" + 1261                         DbLsn.getNoFormatString(logLsn) + " " + trace, 1262                         e); 1263            throw new DatabaseException("lsnFromLog=" + 1264                                        DbLsn.getNoFormatString(logLsn), e); 1265        } finally { 1266        if (!inFromLogLatchReleased) { 1267        inFromLog.releaseLatchIfOwner(); 1268        } 1269         1270            assert (LatchSupport.countLatchesHeld() == 0): 1271                LatchSupport.latchesHeldToString() + 1272                "LSN = " + DbLsn.toString(logLsn) + 1273                " inFromLog = " + inFromLog.getNodeId(); 1274 1275        } 1276    } 1277 1278    /** 1279     * Dump a tracking list into a string. 1280     */ 1281    private String printTrackList(List trackingList) { 1282        if (trackingList != null) { 1283            StringBuffer sb = new StringBuffer (); 1284            Iterator iter = trackingList.iterator(); 1285            sb.append("Trace list:"); 1286            sb.append('\n'); 1287            while (iter.hasNext()) { 1288                sb.append((TrackingInfo) iter.next()); 1289                sb.append('\n'); 1290            } 1291            return sb.toString(); 1292        } else { 1293            return null; 1294        } 1295    } 1296 1297    /** 1298     * Replay an IN delete. Remove an entry from an IN to reflect a reverse 1299     * split. 1300     */ 1301    private void replayINDelete(DatabaseImpl db, 1302                long nodeId, 1303                                boolean containsDuplicates, 1304                byte[] mainKey, 1305                byte[] dupKey, 1306                                long logLsn) 1307        throws DatabaseException { 1308 1309        boolean found = false; 1310        boolean deleted = false; 1311        Tree tree = db.getTree(); 1312        SearchResult result = new SearchResult(); 1313 1314        try { 1315            /* Search for the parent of this target node. */ 1316            result = db.getTree().getParentINForChildIN 1317                (nodeId, 1318                 containsDuplicates, 1319                 false, // do not stop at dup tree root 1320 mainKey, 1321                 dupKey, 1322                 false, // requireExactMatch 1323 false, // updateGeneration 1324 -1, // targetLevel 1325 null, // trackingList 1326 true); // doFetch 1327 1328            if (result.parent == null) { 1329                /* It's null -- we actually deleted the root. */ 1330                tree.withRootLatchedExclusive(new RootDeleter(tree)); 1331                DbTree dbTree = db.getDbEnvironment().getDbMapTree(); 1332                dbTree.modifyDbRoot(db); 1333                traceRootDeletion(Level.FINE, db); 1334                deleted = true; 1335            } else if (result.exactParentFound) { 1336                /* Exact match was found -- delete the parent entry. */ 1337                found = true; 1338                deleted = result.parent.deleteEntry(result.index, false); 1339            } 1340        } finally { 1341            if (result.parent != null) { 1342                result.parent.releaseLatch(); 1343            } 1344 1345            traceINDeleteReplay 1346                (nodeId, logLsn, found, deleted, result.index, 1347                 containsDuplicates); 1348        } 1349    } 1350 1351    /* 1352     * RootDeleter lets us clear the rootIN within the root latch. 1353     */ 1354    private static class RootDeleter implements WithRootLatched { 1355        Tree tree; 1356        RootDeleter(Tree tree) { 1357            this.tree = tree; 1358        } 1359 1360        /** 1361         * @return true if the in-memory root was replaced. 1362         */ 1363        public IN doWork(ChildReference root) 1364            throws DatabaseException { 1365 1366            tree.setRoot(null, false); 1367            return null; 1368        } 1369    } 1370 1371    /** 1372     * If the root of this tree is null, use this IN from the log as a root. 1373     * Note that we should really also check the LSN of the mapLN, because 1374     * perhaps the root is null because it's been deleted. However, the replay 1375     * of all the LNs will end up adjusting the tree correctly. 1376     * 1377     * If there is a root, check if this IN is a different LSN and if so, 1378     * replace it. 1379     */ 1380    private void replaceOrInsertRoot(DatabaseImpl db, IN inFromLog, long lsn) 1381        throws DatabaseException { 1382 1383        boolean success = true; 1384        Tree tree = db.getTree(); 1385        RootUpdater rootUpdater = new RootUpdater(tree, inFromLog, lsn); 1386        try { 1387            /* Run the root updater while the root latch is held. */ 1388            tree.withRootLatchedExclusive(rootUpdater); 1389 1390            /* Update the mapLN if necessary */ 1391            if (rootUpdater.updateDone()) { 1392                EnvironmentImpl env = db.getDbEnvironment(); 1393                env.getDbMapTree().modifyDbRoot(db); 1394            } 1395        } catch (Exception e) { 1396            success = false; 1397            throw new DatabaseException("lsnFromLog=" + 1398                                        DbLsn.getNoFormatString(lsn), 1399                                        e); 1400        } finally { 1401            trace(detailedTraceLevel, 1402                  db, TRACE_ROOT_REPLACE, success, inFromLog, 1403                  lsn, 1404                  null, 1405                  true, 1406                  rootUpdater.getReplaced(), 1407                  rootUpdater.getInserted(), 1408                  rootUpdater.getOriginalLsn(), 1409          DbLsn.NULL_LSN, 1410          -1); 1411        } 1412    } 1413 1414    /* 1415     * RootUpdater lets us replace the tree root within the tree root latch. 1416     */ 1417    private static class RootUpdater implements WithRootLatched { 1418        private Tree tree; 1419        private IN inFromLog; 1420        private long lsn = DbLsn.NULL_LSN; 1421        private boolean inserted = false; 1422        private boolean replaced = false; 1423        private long originalLsn = DbLsn.NULL_LSN; 1424 1425        RootUpdater(Tree tree, IN inFromLog, long lsn) { 1426            this.tree = tree; 1427            this.inFromLog = inFromLog; 1428            this.lsn = lsn; 1429        } 1430 1431        public IN doWork(ChildReference root) 1432            throws DatabaseException { 1433 1434            ChildReference newRoot = 1435        tree.makeRootChildReference(inFromLog, new byte[0], lsn); 1436            inFromLog.releaseLatch(); 1437 1438            if (root == null) { 1439                tree.setRoot(newRoot, false); 1440                inserted = true; 1441            } else { 1442                originalLsn = root.getLsn(); // for debugLog 1443 1444                /* 1445                 * The current in-memory root IN is older than the root IN from 1446                 * the log. 1447                 */ 1448                if (DbLsn.compareTo(originalLsn, lsn) < 0) { 1449                    tree.setRoot(newRoot, false); 1450                    replaced = true; 1451                } 1452            } 1453            return null; 1454        } 1455 1456        boolean updateDone() { 1457            return inserted || replaced; 1458        } 1459 1460        boolean getInserted() { 1461            return inserted; 1462        } 1463 1464        boolean getReplaced() { 1465            return replaced; 1466        } 1467 1468        long getOriginalLsn() { 1469            return originalLsn; 1470        } 1471    } 1472 1473    /** 1474     * Recover this root of a duplicate tree. 1475     */ 1476    private void replaceOrInsertDuplicateRoot(DatabaseImpl db, 1477                                              DIN inFromLog, 1478                                              long lsn) 1479        throws DatabaseException { 1480 1481        boolean found = true; 1482        boolean inserted = false; 1483        boolean replaced = false; 1484        long originalLsn = DbLsn.NULL_LSN; 1485 1486        byte[] mainTreeKey = inFromLog.getMainTreeKey(); 1487        IN parent = null; 1488        int index = -1; 1489        boolean success = false; 1490        try { 1491 1492            /* 1493             * Allow splits since the parent BIN of this DIN may be full. 1494             * [#13435] 1495             */ 1496            parent = db.getTree().searchSplitsAllowed 1497                (mainTreeKey, -1, true /*updateGeneration*/); 1498            assert parent instanceof BIN; 1499 1500        ChildReference newRef = 1501        new ChildReference(inFromLog, mainTreeKey, lsn); 1502        index = parent.insertEntry1(newRef); 1503        if ((index >= 0 && 1504         (index & IN.EXACT_MATCH) != 0)) { 1505 1506        index &= ~IN.EXACT_MATCH; 1507 1508        /* 1509         * Replace whatever's at this entry, whether it's an LN or an 1510         * earlier root DIN as long as one of the following is true: 1511         * 1512         * - the entry is known deleted 1513         * - or the LSN is earlier than the one we've just read from 1514         * the log. 1515         */ 1516        if (parent.isEntryKnownDeleted(index)) { 1517            /* Be sure to clear the known deleted bit. */ 1518            parent.setEntry(index, inFromLog, mainTreeKey, 1519                    lsn, (byte) 0); 1520            replaced = true; 1521        } else { 1522            originalLsn = parent.getLsn(index); 1523            if (DbLsn.compareTo(originalLsn, lsn) < 0) { 1524            parent.setEntry(index, inFromLog, mainTreeKey, lsn, 1525                    parent.getState(index)); 1526            replaced = true; 1527            } 1528        } 1529        } else { 1530        found = false; 1531        } 1532        success = true; 1533        } finally { 1534            if (parent != null) { 1535                parent.releaseLatch(); 1536            } 1537            trace(detailedTraceLevel, 1538                  db, 1539                  TRACE_DUP_ROOT_REPLACE, success, inFromLog, 1540                  lsn, parent, found, 1541                  replaced, inserted, originalLsn, DbLsn.NULL_LSN, index); 1542        } 1543    } 1544 1545    private void replaceOrInsertChild(DatabaseImpl db, 1546                                      IN inFromLog, 1547                                      long logLsn, 1548                                      long inLsn, 1549                                      List trackingList, 1550                                      boolean requireExactMatch) 1551        throws DatabaseException { 1552 1553        boolean inserted = false; 1554        boolean replaced = false; 1555        long originalLsn = DbLsn.NULL_LSN; 1556        boolean success = false; 1557        SearchResult result = new SearchResult(); 1558        try { 1559            result = db.getTree().getParentINForChildIN 1560                (inFromLog, 1561                 requireExactMatch, 1562                 false, // updateGeneration 1563 -1, // targetLevel 1564 trackingList); 1565 1566            /* 1567             * Does inFromLog exist in this parent? 1568             * 1569             * 1. No possible parent -- skip this child. It's represented 1570             * by a parent that's later in the log. 1571             * 2. No match, but a possible parent: don't insert, all nodes 1572             * are logged in such a way that they must have a possible 1573             * parent (#13501) 1574             * 3. physical match: (LSNs same) this LSN is already in place, 1575             * do nothing. 1576             * 4. logical match: another version of this IN is in place. 1577             * Replace child with inFromLog if inFromLog's 1578             * LSN is greater. 1579             */ 1580            if (result.parent == null) { 1581                return; // case 1, no possible parent. 1582 } 1583 1584            /* Get the key that will locate inFromLog in this parent. */ 1585            if (result.index >= 0) { 1586                if (result.parent.getLsn(result.index) == logLsn) { 1587                    /* case 3: do nothing */ 1588 1589                } else { 1590 1591                    /* 1592                     * Not an exact physical match, now need to look at child. 1593                     */ 1594                    if (result.exactParentFound) { 1595                        originalLsn = result.parent.getLsn(result.index); 1596                         1597                        /* case 4: It's a logical match, replace */ 1598                        if (DbLsn.compareTo(originalLsn, logLsn) < 0) { 1599 1600                            /* 1601                 * It's a logical match, replace. Put the child 1602                 * node reference into the parent, as well as the 1603                 * true LSN of the IN. (If this entry is a 1604                 * BINDelta, the node has been updated with all the 1605                 * deltas, but the LSN we want to put in should be 1606                 * the last full LSN, not the LSN of the BINDelta) 1607                             */ 1608                            result.parent.updateEntry(result.index, 1609                                                      inFromLog, 1610                                                      inLsn); 1611                            replaced = true; 1612                        } 1613                    } 1614                    /* else case 2 */ 1615                } 1616            } 1617            /* else case 2 */ 1618 1619            success = true; 1620        } finally { 1621            if (result.parent != null) { 1622                result.parent.releaseLatch(); 1623            } 1624 1625            trace(detailedTraceLevel, db, 1626                  TRACE_IN_REPLACE, success, inFromLog, 1627                  logLsn, result.parent, 1628                  result.exactParentFound, replaced, inserted, 1629                  originalLsn, DbLsn.NULL_LSN, result.index); 1630        } 1631    } 1632 1633    /** 1634     * Redo a committed LN for recovery. 1635     * 1636     * <pre> 1637     * log LN found | logLSN > LSN | LN is deleted | action 1638     * in tree | in tree | | 1639     * --------------+--------------+---------------+------------------------ 1640     * Y | N | n/a | no action 1641     * --------------+--------------+---------------+------------------------ 1642     * Y | Y | N | replace w/log LSN 1643     * --------------+--------------+---------------+------------------------ 1644     * Y | Y | Y | replace w/log LSN, put 1645     * | | | on compressor queue 1646     * --------------+--------------+---------------+------------------------ 1647     * N | n/a | N | insert into tree 1648     * --------------+--------------+---------------+------------------------ 1649     * N | n/a | Y | no action 1650     * --------------+--------------+---------------+------------------------ 1651     * 1652     * </pre> 1653     * 1654     * @param location holds state about the search in the tree. Passed 1655     * in from the recovery manager to reduce objection creation overhead. 1656     * @param lnFromLog - the new node to put in the tree. 1657     * @param mainKey is the key that navigates us through the main tree 1658     * @param dupTreeKey is the key that navigates us through the duplicate 1659     * tree 1660     * @param logLsn is the LSN from the just-read log entry 1661     * @param info is a recovery stats object. 1662     * @return the LSN found in the tree, or NULL_LSN if not found. 1663     */ 1664    private long redo(DatabaseImpl db, 1665              TreeLocation location, 1666              LN lnFromLog, 1667              byte[] mainKey, 1668              byte[] dupKey, 1669              long logLsn, 1670              RecoveryInfo info) 1671        throws DatabaseException { 1672 1673        boolean found = false; 1674        boolean replaced = false; 1675        boolean inserted = false; 1676        boolean success = false; 1677        try { 1678 1679            /* 1680             * Find the BIN which is the parent of this LN. 1681             */ 1682            location.reset(); 1683            found = db.getTree().getParentBINForChildLN 1684                (location, mainKey, dupKey, lnFromLog, 1685                 true, // splitsAllowed 1686 false, // findDeletedEntries 1687 true, // searchDupTree 1688 true); // updateGeneration 1689 1690            if (!found && (location.bin == null)) { 1691 1692                /* 1693                 * There is no possible parent for this LN. This tree was 1694                 * probably compressed away. 1695                 */ 1696                success = true; 1697                return DbLsn.NULL_LSN; 1698            } 1699 1700            /* 1701             * Now we're at the parent for this LN, whether BIN, DBIN or DIN 1702             */ 1703            if (lnFromLog.containsDuplicates()) { 1704                if (found) { 1705 1706            /* 1707             * This is a dupCountLN. It's ok if there's no DIN parent 1708             * for it. [#11307]. 1709             */ 1710            DIN duplicateRoot = (DIN) 1711            location.bin.fetchTarget(location.index); 1712            if (DbLsn.compareTo(logLsn, location.childLsn) >= 0) { 1713            /* DupCountLN needs replacing. */ 1714            duplicateRoot.latch(); 1715            duplicateRoot.updateDupCountLNRefAndNullTarget(logLsn); 1716            duplicateRoot.releaseLatch(); 1717            } 1718                } 1719            } else { 1720                if (found) { 1721 1722                    /* 1723                     * This LN is in the tree. See if it needs replacing. 1724                     */ 1725                    info.lnFound++; 1726 1727                    if (DbLsn.compareTo(logLsn, location.childLsn) > 0) { 1728                        info.lnReplaced++; 1729                        replaced = true; 1730 1731                        /* 1732             * Be sure to make the target null. We don't want this 1733             * new LN resident, it will make recovery start 1734             * dragging in the whole tree and will consume too much 1735             * memory. 1736                         */ 1737                        location.bin.updateEntry(location.index, 1738                                                 null, 1739                                                 logLsn); 1740                    } 1741 1742                    /* 1743                     * If the entry in the tree is deleted, put it on the 1744                     * compressor queue. Set KnownDeleted to prevent fetching 1745                     * a cleaned LN. 1746                     */ 1747                    if (DbLsn.compareTo(logLsn, location.childLsn) >= 0 && 1748                        lnFromLog.isDeleted()) { 1749                        location.bin.setKnownDeletedLeaveTarget 1750                            (location.index); 1751                        byte[] deletedKey = location.bin.containsDuplicates() ? 1752                            dupKey : mainKey; 1753 1754                        /* 1755                         * In the case of SR 8984, the LN has no data and 1756                         * therefore no valid delete key. Don't compress. 1757                         */ 1758                        if (deletedKey != null) { 1759                            db.getDbEnvironment().addToCompressorQueue 1760                                (location.bin, 1761                                 new Key(deletedKey), 1762                                 false); // don't wakeup compressor 1763 } 1764                    } 1765 1766                } else { 1767                    /* 1768                     * This LN is not in the tree. If it's not deleted, insert 1769                     * it. 1770                     */ 1771                    info.lnNotFound++; 1772                    if (!lnFromLog.isDeleted()) { 1773                        info.lnInserted++; 1774                        inserted = true; 1775                        boolean insertOk = 1776                insertRecovery(db, location, logLsn); 1777                        assert insertOk; 1778                    } 1779                } 1780            } 1781            success = true; 1782            return found ? location.childLsn : DbLsn.NULL_LSN; 1783        } finally { 1784            if (location.bin != null) { 1785                location.bin.releaseLatchIfOwner(); 1786            } 1787            trace(detailedTraceLevel, db, 1788                  TRACE_LN_REDO, success, lnFromLog, 1789                  logLsn, location.bin, found, 1790                  replaced, inserted, 1791                  location.childLsn, DbLsn.NULL_LSN, location.index); 1792        } 1793    } 1794 1795    /** 1796     * Undo the changes to this node. Here are the rules that govern the action 1797     * taken. 1798     * 1799     * <pre> 1800     * 1801     * found LN in | abortLsn is | logLsn == | action taken 1802     * tree | null | LSN in tree | by undo 1803     * -------------+-------------+---------------------------------------- 1804     * Y | N | Y | replace w/abort LSN 1805     * ------------ +-------------+-----------------+----------------------- 1806     * Y | Y | Y | remove from tree 1807     * ------------ +-------------+-----------------+----------------------- 1808     * Y | N/A | N | no action 1809     * ------------ +-------------+-----------------+----------------------- 1810     * N | N/A | N/A | no action (*) 1811     * (*) If this key is not present in the tree, this record doesn't 1812     * reflect the IN state of the tree and this log entry is not applicable. 1813     * 1814     * </pre> 1815     * @param location holds state about the search in the tree. Passed 1816     * in from the recovery manager to reduce objection creation overhead. 1817     * @param lnFromLog - the new node to put in the tree. 1818     * @param mainKey is the key that navigates us through the main tree 1819     * @param dupTreeKey is the key that navigates us through the duplicate 1820     * tree 1821     * @param logLsn is the LSN from the just-read log entry 1822     * @param abortLsn gives us the location of the original version of the 1823     * node 1824     * @param info is a recovery stats object. 1825     */ 1826    public static void undo(Level traceLevel, 1827                            DatabaseImpl db, 1828                            TreeLocation location, 1829                            LN lnFromLog, 1830                            byte[] mainKey, 1831                            byte[] dupKey, 1832                            long logLsn, 1833                            long abortLsn, 1834                            boolean abortKnownDeleted, 1835                            RecoveryInfo info, 1836                            boolean splitsAllowed) 1837        throws DatabaseException { 1838 1839        boolean found = false; 1840        boolean replaced = false; 1841        boolean success = false; 1842 1843        try { 1844 1845            /* 1846             * Find the BIN which is the parent of this LN. 1847             */ 1848            location.reset(); 1849            found = db.getTree().getParentBINForChildLN 1850                (location, mainKey, dupKey, lnFromLog, splitsAllowed, 1851                 true, // findDeletedEntries 1852 false, // searchDupTree 1853 true); // updateGeneration 1854 1855            /* 1856             * Now we're at the rightful parent, whether BIN or DBIN. 1857             */ 1858            if (lnFromLog.containsDuplicates()) { 1859 1860                /* 1861         * This is a dupCountLN. It's ok if there's no DIN parent 1862         * for it. [#11307]. 1863         */ 1864                if (found) { 1865            DIN duplicateRoot = (DIN) 1866            location.bin.fetchTarget(location.index); 1867                    duplicateRoot.latch(); 1868                    try { 1869                        if (DbLsn.compareTo(logLsn, location.childLsn) == 0) { 1870                            /* DupCountLN needs replacing. */ 1871                            duplicateRoot. 1872                                updateDupCountLNRefAndNullTarget(abortLsn); 1873                            replaced = true; 1874                        } 1875                    } finally { 1876                        duplicateRoot.releaseLatch(); 1877                    } 1878        } 1879            } else { 1880                if (found) { 1881                    /* This LN is in the tree. See if it needs replacing. */ 1882                    if (info != null) { 1883                        info.lnFound++; 1884                    } 1885            boolean updateEntry = 1886            DbLsn.compareTo(logLsn, location.childLsn) == 0; 1887            if (updateEntry) { 1888            if (abortLsn == DbLsn.NULL_LSN) { 1889 1890                /* 1891                 * To undo a node that was created by this txn, 1892                 * remove it. If this entry is deleted, put it on 1893                             * the compressor queue. Set KnownDeleted to 1894                             * prevent fetching a cleaned LN. 1895                 */ 1896                location.bin. 1897                setKnownDeletedLeaveTarget(location.index); 1898                            byte[] deletedKey = 1899                                location.bin.containsDuplicates() ? 1900                                dupKey : mainKey; 1901                db.getDbEnvironment().addToCompressorQueue 1902                (location.bin, 1903                                 new Key(deletedKey), 1904                                 false); // don't wakeup compressor 1905 1906            } else { 1907 1908                /* 1909                 * Apply the log record by updating the in memory 1910                 * tree slot to contain the abort LSN and abort 1911                 * Known Deleted flag. 1912                 */ 1913                if (info != null) { 1914                info.lnReplaced++; 1915                } 1916                replaced = true; 1917                location.bin.updateEntry(location.index, 1918                             null, 1919                             abortLsn); 1920                if (abortKnownDeleted) { 1921                location.bin.setKnownDeleted(location.index); 1922                } else { 1923                location.bin.clearKnownDeleted(location.index); 1924                } 1925            } 1926 1927                        /* 1928                         * We must clear the PendingDeleted flag for 1929                         * non-deleted entries. Clear it unconditionally, 1930                         * since KnownDeleted will be set above for a deleted 1931                         * entry. [#12885] 1932                         */ 1933                        location.bin.clearPendingDeleted(location.index); 1934            } 1935 1936                } else { 1937 1938                    /* 1939                     * This LN is not in the tree. Just make a note of it. 1940                     */ 1941                    if (info != null) { 1942                        info.lnNotFound++; 1943                    } 1944                } 1945            } 1946 1947            success = true; 1948        } finally { 1949            /* 1950             * Note that undo relies on the caller to unlatch the bin. Not 1951             * ideal, done in order to support abort processing. 1952             */ 1953            trace(traceLevel, db, TRACE_LN_UNDO, success, lnFromLog, 1954          logLsn, location.bin, found, replaced, false, 1955          location.childLsn, abortLsn, location.index); 1956        } 1957    } 1958 1959    /** 1960     * Inserts a LN into the tree for recovery redo processing. In this 1961     * case, we know we don't have to lock when checking child LNs for deleted 1962     * status (there can be no other thread running on this tree) and we don't 1963     * have to log the new entry. (it's in the log already) 1964     * 1965     * @param db 1966     * @param location this embodies the parent bin, the index, the key that 1967     * represents this entry in the bin. 1968     * @param logLsn LSN of this current ln 1969     * @param key to use when creating a new ChildReference object. 1970     * @return true if LN was inserted, false if it was a duplicate 1971     * duplicate or if an attempt was made to insert a duplicate when 1972     * allowDuplicates was false. 1973     */ 1974    private static boolean insertRecovery(DatabaseImpl db, 1975                                          TreeLocation location, 1976                                          long logLsn) 1977        throws DatabaseException { 1978         1979        /* Make a child reference as a candidate for insertion. */ 1980        ChildReference newLNRef = 1981        new ChildReference(null, location.lnKey, logLsn); 1982 1983        BIN parentBIN = location.bin; 1984        int entryIndex = parentBIN.insertEntry1(newLNRef); 1985 1986        if ((entryIndex & IN.INSERT_SUCCESS) == 0) { 1987 1988            /* 1989         * Entry may have been a duplicate. Insertion was not successful. 1990         */ 1991            entryIndex &= ~IN.EXACT_MATCH; 1992 1993            boolean canOverwrite = false; 1994            if (parentBIN.isEntryKnownDeleted(entryIndex)) { 1995                canOverwrite = true; 1996            } else { 1997 1998                /* 1999                 * Read the LN that's in this slot to check for deleted 2000                 * status. No need to lock, since this is recovery. If 2001                 * fetchTarget returns null, a deleted LN was cleaned. 2002                 */ 2003                LN currentLN = (LN) parentBIN.fetchTarget(entryIndex); 2004 2005                if (currentLN == null || currentLN.isDeleted()) { 2006                    canOverwrite = true; 2007                } 2008 2009                /* 2010         * Evict the target again manually, to reduce memory 2011         * consumption while the evictor is not running. 2012                 */ 2013        parentBIN.updateEntry(entryIndex, null); 2014            } 2015 2016            if (canOverwrite) { 2017                parentBIN.updateEntry(entryIndex, null, logLsn, 2018                                      location.lnKey); 2019                parentBIN.clearKnownDeleted(entryIndex); 2020                location.index = entryIndex; 2021                return true; 2022            } else { 2023                return false; 2024            } 2025        } 2026        location.index = entryIndex & ~IN.INSERT_SUCCESS; 2027        return true; 2028    } 2029 2030    /** 2031     * Update file utilization info during redo. 2032     */ 2033    private void redoUtilizationInfo(long logLsn, 2034                     long treeLsn, 2035                                     long abortLsn, 2036                     boolean abortKnownDeleted, 2037                                     int logEntrySize, 2038                                     byte[] key, 2039                                     LN ln, 2040                     TxnNodeId txnNodeId, 2041                                     Set countedAbortLsnNodes) 2042        throws DatabaseException { 2043 2044        UtilizationTracker tracker = env.getUtilizationTracker(); 2045 2046        /* 2047         * If the LN is marked deleted and its LSN follows the FileSummaryLN 2048         * for its file, count it as obsolete. 2049         */ 2050        if (ln.isDeleted()) { 2051            Long logFileNum = new Long (DbLsn.getFileNumber(logLsn)); 2052            long fileSummaryLsn = 2053        DbLsn.longToLsn((Long ) fileSummaryLsns.get(logFileNum)); 2054            int cmpFsLsnToLogLsn = 2055        (fileSummaryLsn != DbLsn.NULL_LSN) ? 2056        DbLsn.compareTo(fileSummaryLsn, logLsn) : -1; 2057            if (cmpFsLsnToLogLsn < 0) { 2058                tracker.countObsoleteNode(logLsn, null, logEntrySize); 2059            } 2060        } 2061 2062        /* Was the LN found in the tree? */ 2063        if (treeLsn != DbLsn.NULL_LSN) { 2064            int cmpLogLsnToTreeLsn = DbLsn.compareTo(logLsn, treeLsn); 2065 2066            /* 2067             * If the oldLsn and newLsn differ and the newLsn follows the 2068             * FileSummaryLN for the file of the oldLsn, count the oldLsn as 2069             * obsolete. 2070             */ 2071            if (cmpLogLsnToTreeLsn != 0) { 2072                long newLsn = (cmpLogLsnToTreeLsn < 0) ? treeLsn : logLsn; 2073                long oldLsn = (cmpLogLsnToTreeLsn > 0) ? treeLsn : logLsn; 2074                Long oldLsnFile = new Long (DbLsn.getFileNumber(oldLsn)); 2075        long oldFsLsn = 2076            DbLsn.longToLsn((Long ) fileSummaryLsns.get(oldLsnFile)); 2077                int cmpOldFsLsnToNewLsn = 2078            (oldFsLsn != DbLsn.NULL_LSN) ? 2079            DbLsn.compareTo(oldFsLsn, newLsn) : -1; 2080                if (cmpOldFsLsnToNewLsn < 0) { 2081                    /* Fetch the LN only if necessary and so configured. */ 2082                    int oldSize = 0; 2083                    if (oldLsn == logLsn) { 2084                        oldSize = logEntrySize; 2085                    } else if (env.getCleaner().getFetchObsoleteSize()) { 2086                        try { 2087                            LN oldLn = (LN) env.getLogManager().get(oldLsn); 2088                            oldSize = oldLn.getTotalLastLoggedSize(key); 2089                        } catch (LogFileNotFoundException e) { 2090                            /* Ignore errors if the file was cleaned. */ 2091                        } 2092                    } 2093                    tracker.countObsoleteNode(oldLsn, null, oldSize); 2094                } 2095            } 2096 2097            /* 2098             * If the logLsn is equal to or precedes the treeLsn and the entry 2099             * has an abortLsn that was not previously deleted, consider the 2100             * set of entries for the given node. If the logLsn is the first 2101             * in the set that follows the FileSummaryLN of the abortLsn, count 2102             * the abortLsn as obsolete. 2103             */ 2104            if (cmpLogLsnToTreeLsn <= 0 && 2105                abortLsn != DbLsn.NULL_LSN && 2106                !abortKnownDeleted && 2107                !countedAbortLsnNodes.contains(txnNodeId)) { 2108                /* We have not counted this abortLsn yet. */ 2109                Long abortFileNum = new Long (DbLsn.getFileNumber(abortLsn)); 2110        long abortFsLsn = 2111            DbLsn.longToLsn((Long ) fileSummaryLsns.get(abortFileNum)); 2112                int cmpAbortFsLsnToLogLsn = 2113            (abortFsLsn != DbLsn.NULL_LSN) ? 2114            DbLsn.compareTo(abortFsLsn, logLsn) : -1; 2115                if (cmpAbortFsLsnToLogLsn < 0) { 2116 2117                    /* 2118                     * logLsn follows the FileSummaryLN of the abortLsn. The 2119                     * abortLsn is only an approximation of the prior LSN, so 2120                     * use inexact counting. Since this is relatively rare, 2121                     * a zero entry size (use average size) is acceptable. 2122                     */ 2123                    tracker.countObsoleteNodeInexact(abortLsn, null, 0); 2124 2125                    /* Don't count this abortLsn (this node) again. */ 2126                    countedAbortLsnNodes.add(txnNodeId); 2127                } 2128            } 2129        } 2130    } 2131 2132    /** 2133     * Update file utilization info during recovery undo (not abort undo). 2134     */ 2135    private void undoUtilizationInfo(LN ln, 2136                     long logLsn, 2137                     long abortLsn, 2138                                     boolean abortKnownDeleted, 2139                                     int logEntrySize, 2140                                     TxnNodeId txnNodeId, 2141                                     Map countedFileSummaries, 2142                                     Set countedAbortLsnNodes) { 2143 2144        UtilizationTracker tracker = env.getUtilizationTracker(); 2145 2146        /* Compare the fileSummaryLsn to the logLsn. */ 2147        Long logFileNum = new Long (DbLsn.getFileNumber(logLsn)); 2148        long fileSummaryLsn = 2149            DbLsn.longToLsn((Long ) fileSummaryLsns.get(logFileNum)); 2150        int cmpFsLsnToLogLsn = (fileSummaryLsn != DbLsn.NULL_LSN) ? 2151            DbLsn.compareTo(fileSummaryLsn, logLsn) : -1; 2152 2153        /* 2154         * Count the logLsn as obsolete if it follows the FileSummaryLN for the 2155         * file of its Lsn. 2156         */ 2157        if (cmpFsLsnToLogLsn < 0) { 2158            tracker.countObsoleteNode(logLsn, null, logEntrySize); 2159        } 2160 2161        /* 2162         * Consider the latest LSN for the given node that precedes the 2163         * FileSummaryLN for the file of its LSN. Count this LSN as obsolete 2164         * if it is not a deleted LN. 2165         */ 2166        if (cmpFsLsnToLogLsn > 0) { 2167            Long countedFile = (Long ) countedFileSummaries.get(txnNodeId); 2168            if (countedFile == null || 2169                countedFile.longValue() > logFileNum.longValue()) { 2170 2171                /* 2172                 * We encountered a new file number and the FsLsn follows the 2173                 * logLsn. 2174                 */ 2175                if (!ln.isDeleted()) { 2176                    tracker.countObsoleteNode(logLsn, null, logEntrySize); 2177                } 2178                /* Don't count this file again. */ 2179                countedFileSummaries.put(txnNodeId, logFileNum); 2180            } 2181        } 2182    } 2183 2184    /** 2185     * Concoct a header for the recovery pass trace info. 2186     */ 2187    private String passStartHeader(int passNum) { 2188        return "Recovery Pass " + passNum + " start: "; 2189    } 2190 2191    /** 2192     * Concoct a header for the recovery pass trace info. 2193     */ 2194    private String passEndHeader(int passNum, long start, long end) { 2195        return "Recovery Pass " + passNum + " end (" + 2196            (end-start) + "): "; 2197    } 2198 2199    /** 2200     * Send trace messages to the java.util.logger. Don't rely on the logger 2201     * alone to conditionalize whether we send this message, we don't even want 2202     * to construct the message if the level is not enabled. This is used to 2203     * construct verbose trace messages for individual log entry processing. 2204     */ 2205    private static void trace(Level level, 2206                              DatabaseImpl database, 2207                              String debugType, 2208                              boolean success, 2209                              Node node, 2210                              long logLsn, 2211                              IN parent, 2212                              boolean found, 2213                              boolean replaced, 2214                              boolean inserted, 2215                              long replacedLsn, 2216                  long abortLsn, 2217                  int index) { 2218        Logger logger = database.getDbEnvironment().getLogger(); 2219        Level useLevel= level; 2220        if (!success) { 2221            useLevel = Level.SEVERE; 2222        } 2223        if (logger.isLoggable(useLevel)) { 2224            StringBuffer sb = new StringBuffer (); 2225            sb.append(debugType); 2226            sb.append(" success=").append(success); 2227            sb.append(" node="); 2228            sb.append(node.getNodeId()); 2229            sb.append(" lsn="); 2230            sb.append(DbLsn.getNoFormatString(logLsn)); 2231            if (parent != null) { 2232                sb.append(" parent=").append(parent.getNodeId()); 2233            } 2234            sb.append(" found="); 2235            sb.append(found); 2236            sb.append(" replaced="); 2237            sb.append(replaced); 2238            sb.append(" inserted="); 2239            sb.append(inserted); 2240            if (replacedLsn != DbLsn.NULL_LSN) { 2241                sb.append(" replacedLsn="); 2242                sb.append(DbLsn.getNoFormatString(replacedLsn)); 2243            } 2244            if (abortLsn != DbLsn.NULL_LSN) { 2245                sb.append(" abortLsn="); 2246                sb.append(DbLsn.getNoFormatString(abortLsn)); 2247            } 2248            sb.append(" index=").append(index); 2249            logger.log(useLevel, sb.toString()); 2250        } 2251    } 2252 2253    /** 2254     * Send trace messages to the java.util.logger. Don't rely on the logger 2255     * alone to conditionalize whether we send this message, we don't even want 2256     * to construct the message if the level is not enabled. 2257     */ 2258    private void traceINDeleteReplay(long nodeId, 2259                                     long logLsn, 2260                                     boolean found, 2261                                     boolean deleted, 2262                                     int index, 2263                     boolean isDuplicate) { 2264        Logger logger = env.getLogger(); 2265        if (logger.isLoggable(detailedTraceLevel)) { 2266            StringBuffer sb = new StringBuffer (); 2267            sb.append((isDuplicate) ? 2268              TRACE_IN_DUPDEL_REPLAY : 2269              TRACE_IN_DEL_REPLAY); 2270            sb.append(" node=").append(nodeId); 2271            sb.append(" lsn=").append(DbLsn.getNoFormatString(logLsn)); 2272            sb.append(" found=").append(found); 2273            sb.append(" deleted=").append(deleted); 2274            sb.append(" index=").append(index); 2275            logger.log(detailedTraceLevel, sb.toString()); 2276        } 2277    } 2278 2279    private void traceAndThrowException(long badLsn, 2280                    String method, 2281                    Exception originalException) 2282        throws DatabaseException { 2283        String badLsnString = DbLsn.getNoFormatString(badLsn); 2284        Tracer.trace(env, 2285                     "RecoveryManager", 2286                     method, 2287                     "last LSN = " + badLsnString, 2288                     originalException); 2289        throw new DatabaseException("last LSN=" + badLsnString, 2290                                    originalException); 2291    } 2292 2293    /** 2294     * Log trace information about root deletions, called by INCompressor and 2295     * recovery. 2296     */ 2297    public static void traceRootDeletion(Level level, DatabaseImpl database) { 2298        Logger logger = database.getDbEnvironment().getLogger(); 2299        if (logger.isLoggable(level)) { 2300            StringBuffer sb = new StringBuffer (); 2301            sb.append(TRACE_ROOT_DELETE); 2302            sb.append(" Dbid=").append(database.getId()); 2303            logger.log(level, sb.toString()); 2304        } 2305    } 2306} 2307

A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame Popular Tags