KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sleepycat > je > recovery > RecoveryManager


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 JavaDoc;
12 import java.util.ArrayList JavaDoc;
13 import java.util.HashMap JavaDoc;
14 import java.util.HashSet JavaDoc;
15 import java.util.Iterator JavaDoc;
16 import java.util.List JavaDoc;
17 import java.util.Map JavaDoc;
18 import java.util.Set JavaDoc;
19 import java.util.logging.Level JavaDoc;
20 import java.util.logging.Logger JavaDoc;
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 JavaDoc TRACE_DUP_ROOT_REPLACE =
60         "DupRootRecover:";
61     private static final String JavaDoc TRACE_LN_REDO = "LNRedo:";
62     private static final String JavaDoc TRACE_LN_UNDO = "LNUndo";
63     private static final String JavaDoc TRACE_IN_REPLACE = "INRecover:";
64     private static final String JavaDoc TRACE_ROOT_REPLACE = "RootRecover:";
65     private static final String JavaDoc TRACE_IN_DEL_REPLAY = "INDelReplay:";
66     private static final String JavaDoc TRACE_IN_DUPDEL_REPLAY = "INDupDelReplay:";
67     private static final String JavaDoc 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 JavaDoc committedTxnIds; // committed txns
75
private Set JavaDoc abortedTxnIds; // aborted txns
76
private Map JavaDoc preparedTxns; // txnid -> prepared Txn
77
private Set JavaDoc inListRebuildDbIds; // dbs for which we have to rebuild the
78
// in memory IN list.
79

80     private Level JavaDoc detailedTraceLevel; // level value for detailed trace msgs
81
private Map JavaDoc 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 JavaDoc();
95         abortedTxnIds = new HashSet JavaDoc();
96     preparedTxns = new HashMap JavaDoc();
97         inListRebuildDbIds = new HashSet JavaDoc();
98         fileSummaryLsns = new HashMap JavaDoc();
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 JavaDoc 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 JavaDoc, 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 JavaDoc, 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 JavaDoc, 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 JavaDoc mapLNSet = new HashSet JavaDoc();
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 JavaDoc lnSet = new HashSet JavaDoc();
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 JavaDoc, DatabaseException {
510
511         Set JavaDoc targetEntries = new HashSet JavaDoc();
512         Set JavaDoc deltaType = new HashSet JavaDoc();
513         String JavaDoc passADesc = null;
514         String JavaDoc passBDesc = null;
515         String JavaDoc 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 JavaDoc 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 JavaDoc, 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 JavaDoc 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 JavaDoc targetLogEntryTypes,
694                         boolean requireExactMatch,
695                         LevelRecorder recorder)
696         throws IOException JavaDoc, 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 JavaDoc 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 JavaDoc 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 JavaDoc targetLogEntryTypes,
763                                Set JavaDoc targetDbs)
764         throws IOException JavaDoc, 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 JavaDoc 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 JavaDoc 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 JavaDoc lnTypes)
885         throws IOException JavaDoc, 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 JavaDoc iter = lnTypes.iterator();
896         while (iter.hasNext()) {
897             LogEntryType lnType = (LogEntryType) iter.next();
898             reader.addTargetType(lnType);
899         }
900
901         Map JavaDoc countedFileSummaries = new HashMap JavaDoc(); // TxnNodeId -> file number
902
Set JavaDoc countedAbortLsnNodes = new HashSet JavaDoc(); // 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 JavaDoc 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 JavaDoc prepareIdL = new Long JavaDoc(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 JavaDoc(reader.getTxnAbortId()));
1003        } else {
1004                    /* The entry just read is a commit record. */
1005                    committedTxnIds.add(new Long JavaDoc(reader.getTxnCommitId()));
1006                }
1007            }
1008            info.nRepeatIteratorReads += reader.getNRepeatIteratorReads();
1009        } catch (RuntimeException JavaDoc 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 JavaDoc lnTypes)
1021        throws IOException JavaDoc, 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 JavaDoc iter = lnTypes.iterator();
1031        while (iter.hasNext()) {
1032            LogEntryType lnType = (LogEntryType) iter.next();
1033            reader.addTargetType(lnType);
1034        }
1035
1036        Set JavaDoc countedAbortLsnNodes = new HashSet JavaDoc(); // 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 JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc();
1253                replaceOrInsertChild(db, inFromLog, logLsn, inLsn,
1254                                     trackingList, requireExactMatch);
1255        inFromLogLatchReleased = true;
1256            }
1257        } catch (Exception JavaDoc e) {
1258            String JavaDoc 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 JavaDoc printTrackList(List JavaDoc trackingList) {
1282        if (trackingList != null) {
1283            StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
1284            Iterator JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc logFileNum = new Long JavaDoc(DbLsn.getFileNumber(logLsn));
2052            long fileSummaryLsn =
2053        DbLsn.longToLsn((Long JavaDoc) 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 JavaDoc oldLsnFile = new Long JavaDoc(DbLsn.getFileNumber(oldLsn));
2075        long oldFsLsn =
2076            DbLsn.longToLsn((Long JavaDoc) 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 JavaDoc abortFileNum = new Long JavaDoc(DbLsn.getFileNumber(abortLsn));
2110        long abortFsLsn =
2111            DbLsn.longToLsn((Long JavaDoc) 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 JavaDoc countedFileSummaries,
2142                                     Set JavaDoc countedAbortLsnNodes) {
2143
2144        UtilizationTracker tracker = env.getUtilizationTracker();
2145
2146        /* Compare the fileSummaryLsn to the logLsn. */
2147        Long JavaDoc logFileNum = new Long JavaDoc(DbLsn.getFileNumber(logLsn));
2148        long fileSummaryLsn =
2149            DbLsn.longToLsn((Long JavaDoc) 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 JavaDoc countedFile = (Long JavaDoc) 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 JavaDoc 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 JavaDoc 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 JavaDoc level,
2206                              DatabaseImpl database,
2207                              String JavaDoc 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 JavaDoc logger = database.getDbEnvironment().getLogger();
2219        Level JavaDoc useLevel= level;
2220        if (!success) {
2221            useLevel = Level.SEVERE;
2222        }
2223        if (logger.isLoggable(useLevel)) {
2224            StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
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 JavaDoc logger = env.getLogger();
2265        if (logger.isLoggable(detailedTraceLevel)) {
2266            StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
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 JavaDoc method,
2281                    Exception JavaDoc originalException)
2282        throws DatabaseException {
2283        String JavaDoc 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 JavaDoc level, DatabaseImpl database) {
2298        Logger JavaDoc logger = database.getDbEnvironment().getLogger();
2299        if (logger.isLoggable(level)) {
2300            StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
2301            sb.append(TRACE_ROOT_DELETE);
2302            sb.append(" Dbid=").append(database.getId());
2303            logger.log(level, sb.toString());
2304        }
2305    }
2306}
2307
Popular Tags