0001: /*-
0002: * See the file LICENSE for redistribution information.
0003: *
0004: * Copyright (c) 2002,2008 Oracle. All rights reserved.
0005: *
0006: * $Id: FileProcessor.java,v 1.17.2.10 2008/01/07 15:14:08 cwl Exp $
0007: */
0008:
0009: package com.sleepycat.je.cleaner;
0010:
0011: import java.io.IOException;
0012: import java.util.HashMap;
0013: import java.util.HashSet;
0014: import java.util.Iterator;
0015: import java.util.Map;
0016: import java.util.Set;
0017: import java.util.SortedMap;
0018: import java.util.TreeMap;
0019: import java.util.logging.Level;
0020:
0021: import com.sleepycat.je.DatabaseException;
0022: import com.sleepycat.je.dbi.DatabaseId;
0023: import com.sleepycat.je.dbi.DatabaseImpl;
0024: import com.sleepycat.je.dbi.DbTree;
0025: import com.sleepycat.je.dbi.EnvironmentImpl;
0026: import com.sleepycat.je.dbi.MemoryBudget;
0027: import com.sleepycat.je.log.CleanerFileReader;
0028: import com.sleepycat.je.log.LogFileNotFoundException;
0029: import com.sleepycat.je.tree.BIN;
0030: import com.sleepycat.je.tree.ChildReference;
0031: import com.sleepycat.je.tree.DIN;
0032: import com.sleepycat.je.tree.IN;
0033: import com.sleepycat.je.tree.LN;
0034: import com.sleepycat.je.tree.SearchResult;
0035: import com.sleepycat.je.tree.Tree;
0036: import com.sleepycat.je.tree.TreeLocation;
0037: import com.sleepycat.je.tree.WithRootLatched;
0038: import com.sleepycat.je.txn.BasicLocker;
0039: import com.sleepycat.je.txn.LockGrantType;
0040: import com.sleepycat.je.txn.LockResult;
0041: import com.sleepycat.je.txn.LockType;
0042: import com.sleepycat.je.utilint.DaemonThread;
0043: import com.sleepycat.je.utilint.DbLsn;
0044: import com.sleepycat.je.utilint.Tracer;
0045:
0046: /**
0047: * Reads all entries in a log file and either determines them to be obsolete or
0048: * marks them for migration. LNs are marked for migration by setting the BIN
0049: * entry MIGRATE flag. INs are marked for migration by setting the dirty flag.
0050: *
0051: * May be invoked explicitly by calling doClean, or woken up if used as a
0052: * daemon thread.
0053: */
0054: class FileProcessor extends DaemonThread {
0055:
0056: /**
0057: * The number of LN log entries after we process pending LNs. If we do
0058: * this too seldom, the pending LN queue may grow large, and it isn't
0059: * budgeted memory. If we process it too often, we will repeatedly request
0060: * a non-blocking lock for the same locked node.
0061: */
0062: private static final int PROCESS_PENDING_EVERY_N_LNS = 100;
0063:
0064: /**
0065: * Whether to prohibit BINDeltas for a BIN that is fetched by the cleaner.
0066: * The theory is that when fetching a BIN during cleaning we normally
0067: * expect that the BIN will be evicted soon, and a delta during checkpoint
0068: * would be wasted. However, this does not take into account use of the
0069: * BIN by the application after fetching; the BIN could become hot and then
0070: * deltas may be profitable. To be safe we currently allow deltas when
0071: * fetching.
0072: */
0073: private static final boolean PROHIBIT_DELTAS_WHEN_FETCHING = false;
0074:
0075: private static final boolean DEBUG_TRACING = false;
0076:
0077: private EnvironmentImpl env;
0078: private Cleaner cleaner;
0079: private FileSelector fileSelector;
0080: private UtilizationProfile profile;
0081:
0082: /* Log version for the target file. */
0083: private int fileLogVersion;
0084:
0085: /* Per Run counters. Reset before each file is processed. */
0086: private int nINsObsoleteThisRun = 0;
0087: private int nINsCleanedThisRun = 0;
0088: private int nINsDeadThisRun = 0;
0089: private int nINsMigratedThisRun = 0;
0090: private int nLNsObsoleteThisRun = 0;
0091: private int nLNsCleanedThisRun = 0;
0092: private int nLNsDeadThisRun = 0;
0093: private int nLNsLockedThisRun = 0;
0094: private int nLNsMigratedThisRun = 0;
0095: private int nLNsMarkedThisRun = 0;
0096: private int nLNQueueHitsThisRun = 0;
0097: private int nEntriesReadThisRun;
0098: private long nRepeatIteratorReadsThisRun;
0099:
0100: FileProcessor(String name, EnvironmentImpl env, Cleaner cleaner,
0101: UtilizationProfile profile, FileSelector fileSelector) {
0102: super (0, name, env);
0103: this .env = env;
0104: this .cleaner = cleaner;
0105: this .fileSelector = fileSelector;
0106: this .profile = profile;
0107: }
0108:
0109: public void clearEnv() {
0110: env = null;
0111: cleaner = null;
0112: fileSelector = null;
0113: profile = null;
0114: }
0115:
0116: /**
0117: * Adds a sentinal object to the work queue to force onWakeup to be
0118: * called immediately after setting je.env.runCleaner=true. We want to
0119: * process any backlog immediately.
0120: */
0121: void addSentinalWorkObject() {
0122: try {
0123: workQueueLatch.acquire();
0124: workQueue.add(new Object());
0125: workQueueLatch.release();
0126: } catch (DatabaseException e) {
0127: throw new IllegalStateException(e);
0128: }
0129: }
0130:
0131: /**
0132: * Return the number of retries when a deadlock exception occurs.
0133: */
0134: protected int nDeadlockRetries() throws DatabaseException {
0135:
0136: return cleaner.nDeadlockRetries;
0137: }
0138:
0139: /**
0140: * Cleaner doesn't have a work queue so just throw an exception if it's
0141: * ever called.
0142: */
0143: public void addToQueue(Object o) throws DatabaseException {
0144:
0145: throw new DatabaseException(
0146: "Cleaner.addToQueue should never be called.");
0147: }
0148:
0149: /**
0150: * Activates the cleaner. Is normally called when je.cleaner.byteInterval
0151: * bytes are written to the log.
0152: */
0153: public void onWakeup() throws DatabaseException {
0154:
0155: doClean(true, // invokedFromDaemon
0156: true, // cleanMultipleFiles
0157: false); // forceCleaning
0158:
0159: /* Remove the sentinal -- see addSentinalWorkObject. */
0160: workQueueLatch.acquire();
0161: workQueue.clear();
0162: workQueueLatch.release();
0163: }
0164:
0165: /**
0166: * Cleans selected files and returns the number of files cleaned. May be
0167: * called by the daemon thread or programatically.
0168: *
0169: * @param invokedFromDaemon currently has no effect.
0170: *
0171: * @param cleanMultipleFiles is true to clean until we're under budget,
0172: * or false to clean at most one file.
0173: *
0174: * @param forceCleaning is true to clean even if we're not under the
0175: * utilization threshold.
0176: *
0177: * @return the number of files cleaned, not including files cleaned
0178: * unsuccessfully.
0179: */
0180: public synchronized int doClean(boolean invokedFromDaemon,
0181: boolean cleanMultipleFiles, boolean forceCleaning)
0182: throws DatabaseException {
0183:
0184: if (env.isClosed()) {
0185: return 0;
0186: }
0187:
0188: /* Clean until no more files are selected. */
0189: int nOriginalLogFiles = profile.getNumberOfFiles();
0190: int nFilesCleaned = 0;
0191: while (true) {
0192:
0193: /* Don't clean forever. */
0194: if (nFilesCleaned >= nOriginalLogFiles) {
0195: break;
0196: }
0197:
0198: /* Stop if the daemon is paused or the environment is closing. */
0199: if ((invokedFromDaemon && isPaused()) || env.isClosing()) {
0200: break;
0201: }
0202:
0203: /*
0204: * Process pending LNs and then attempt to delete all cleaned files
0205: * that are safe to delete. Pending LNs can prevent file deletion.
0206: */
0207: cleaner.processPending();
0208: cleaner.deleteSafeToDeleteFiles();
0209:
0210: /*
0211: * Select the next file for cleaning and update the Cleaner's
0212: * read-only file collections.
0213: */
0214: boolean needLowUtilizationSet = cleaner.clusterResident
0215: || cleaner.clusterAll;
0216:
0217: Long fileNum = fileSelector.selectFileForCleaning(profile,
0218: forceCleaning, needLowUtilizationSet,
0219: cleaner.maxBatchFiles);
0220:
0221: cleaner.updateReadOnlyFileCollections();
0222:
0223: /*
0224: * If no file was selected, the total utilization is under the
0225: * threshold and we can stop cleaning.
0226: */
0227: if (fileNum == null) {
0228: break;
0229: }
0230:
0231: /*
0232: * Clean the selected file.
0233: */
0234: resetPerRunCounters();
0235: boolean finished = false;
0236: boolean fileDeleted = false;
0237: long fileNumValue = fileNum.longValue();
0238: int runId = ++cleaner.nCleanerRuns;
0239: try {
0240:
0241: String traceMsg = "CleanerRun " + runId + " on file 0x"
0242: + Long.toHexString(fileNumValue)
0243: + " begins backlog=" + cleaner.nBacklogFiles;
0244: Tracer.trace(Level.INFO, env, traceMsg);
0245: if (DEBUG_TRACING) {
0246: System.out.println("\n" + traceMsg);
0247: }
0248:
0249: /* Clean all log entries in the file. */
0250: Set deferredWriteDbs = new HashSet();
0251: if (processFile(fileNum, deferredWriteDbs)) {
0252: /* File is fully processed, update status information. */
0253: fileSelector.addCleanedFile(fileNum,
0254: deferredWriteDbs);
0255: nFilesCleaned += 1;
0256: accumulatePerRunCounters();
0257: finished = true;
0258: }
0259: } catch (LogFileNotFoundException e) {
0260:
0261: /*
0262: * File was deleted. Although it is possible that the file was
0263: * deleted externally it is much more likely that the file was
0264: * deleted normally after being cleaned earlier (this was
0265: * observed prior to JE 3.2.29), and that we are mistakedly
0266: * processing the file repeatedly. Since the file does not
0267: * exist, ignore the error so that the cleaner will continue.
0268: * The tracing below will indicate that the file was deleted.
0269: * Remove the file completely from the FileSelector and
0270: * UtilizationProfile so that we don't repeatedly attempt to
0271: * process it. [#15528]
0272: */
0273: fileDeleted = true;
0274: profile.removeFile(fileNum);
0275: fileSelector.removeAllFileReferences(fileNum);
0276: } catch (IOException e) {
0277: Tracer.trace(env, "Cleaner", "doClean", "", e);
0278: throw new DatabaseException(e);
0279: } finally {
0280: if (!finished && !fileDeleted) {
0281: fileSelector.putBackFileForCleaning(fileNum);
0282: }
0283: String traceMsg = "CleanerRun " + runId + " on file 0x"
0284: + Long.toHexString(fileNumValue)
0285: + " invokedFromDaemon=" + invokedFromDaemon
0286: + " finished=" + finished + " fileDeleted="
0287: + fileDeleted + " nEntriesRead="
0288: + nEntriesReadThisRun + " nINsObsolete="
0289: + nINsObsoleteThisRun + " nINsCleaned="
0290: + nINsCleanedThisRun + " nINsDead="
0291: + nINsDeadThisRun + " nINsMigrated="
0292: + nINsMigratedThisRun + " nLNsObsolete="
0293: + nLNsObsoleteThisRun + " nLNsCleaned="
0294: + nLNsCleanedThisRun + " nLNsDead="
0295: + nLNsDeadThisRun + " nLNsMigrated="
0296: + nLNsMigratedThisRun + " nLNsMarked="
0297: + nLNsMarkedThisRun + " nLNQueueHits="
0298: + nLNQueueHitsThisRun + " nLNsLocked="
0299: + nLNsLockedThisRun;
0300: Tracer.trace(Level.SEVERE, env, traceMsg);
0301: if (DEBUG_TRACING) {
0302: System.out.println("\n" + traceMsg);
0303: }
0304: }
0305:
0306: /* If we should only clean one file, stop now. */
0307: if (!cleanMultipleFiles) {
0308: break;
0309: }
0310: }
0311:
0312: return nFilesCleaned;
0313: }
0314:
0315: /**
0316: * Process all log entries in the given file.
0317: *
0318: * Note that we check for obsolete entries using the active TFS
0319: * (TrackedFileSummary) for a file while it is being processed, and we
0320: * prohibit flushing (eviction) of that offset information until file
0321: * processing is complete. An entry could become obsolete because: 1-
0322: * normal application activity deletes or updates the entry, 2- proactive
0323: * migration migrates the entry before we process it, or 3- if trackDetail
0324: * is false. However, checking the TFS is expensive if it has many
0325: * entries, because we perform a linear search. There is a tradeoff
0326: * between the cost of the TFS lookup and its benefit, which is to avoid a
0327: * tree search if the entry is obsolete. Note that many more lookups for
0328: * non-obsolete entries than obsolete entries will typically be done. In
0329: * spite of that we check the tracked summary to avoid the situation where
0330: * eviction does proactive migration, and evicts a BIN that is very soon
0331: * afterward fetched during cleaning.
0332: *
0333: * @param fileNum the file being cleaned.
0334: * @param deferredWriteDbs the set of databaseIds for deferredWrite
0335: * databases which need a sync before a cleaned file can be safely deleted.
0336: * @return false if we aborted file processing because the environment is
0337: * being closed.
0338: */
0339: private boolean processFile(Long fileNum, Set deferredWriteDbs)
0340: throws DatabaseException, IOException {
0341:
0342: /* Get the current obsolete offsets for this file. */
0343: PackedOffsets obsoleteOffsets = new PackedOffsets();
0344: TrackedFileSummary tfs = profile.getObsoleteDetail(fileNum,
0345: obsoleteOffsets, true /* logUpdate */);
0346: PackedOffsets.Iterator obsoleteIter = obsoleteOffsets
0347: .iterator();
0348: long nextObsolete = -1;
0349:
0350: /* Keep in local variables because they are mutable properties. */
0351: final int readBufferSize = cleaner.readBufferSize;
0352: int lookAheadCacheSize = cleaner.lookAheadCacheSize;
0353:
0354: /*
0355: * Add the overhead of this method to the budget. Two read buffers are
0356: * allocated by the file reader. The log size of the offsets happens to
0357: * be the same as the memory overhead.
0358: */
0359: int adjustMem = (2 * readBufferSize)
0360: + obsoleteOffsets.getLogSize() + lookAheadCacheSize;
0361: MemoryBudget budget = env.getMemoryBudget();
0362: budget.updateMiscMemoryUsage(adjustMem);
0363:
0364: /* Evict after updating the budget. */
0365: if (Cleaner.DO_CRITICAL_EVICTION) {
0366: env.getEvictor().doCriticalEviction(true); // backgroundIO
0367: }
0368:
0369: /*
0370: * We keep a look ahead cache of non-obsolete LNs. When we lookup a
0371: * BIN in processLN, we also process any other LNs in that BIN that are
0372: * in the cache. This can reduce the number of tree lookups.
0373: */
0374: LookAheadCache lookAheadCache = new LookAheadCache(
0375: lookAheadCacheSize);
0376:
0377: /*
0378: * For obsolete entries we must check for pending deleted DBs. To
0379: * avoid the overhead of DbTree.getDb on every entry we keep a set of
0380: * all DB IDs encountered and do the check once per DB at the end.
0381: */
0382: Set checkPendingDbSet = new HashSet();
0383:
0384: /*
0385: * Use local caching to reduce DbTree.getDb overhead. Do not call
0386: * releaseDb after getDb with the dbCache, since the entire dbCache
0387: * will be released at the end of thie method.
0388: */
0389: Map dbCache = new HashMap();
0390: DbTree dbMapTree = env.getDbMapTree();
0391:
0392: try {
0393: /* Create the file reader. */
0394: CleanerFileReader reader = new CleanerFileReader(env,
0395: readBufferSize, DbLsn.NULL_LSN, fileNum);
0396: /* Validate all entries before ever deleting a file. */
0397: reader.setAlwaysValidateChecksum(true);
0398:
0399: TreeLocation location = new TreeLocation();
0400:
0401: int nProcessedLNs = 0;
0402: while (reader.readNextEntry()) {
0403: cleaner.nEntriesRead += 1;
0404: long logLsn = reader.getLastLsn();
0405: long fileOffset = DbLsn.getFileOffset(logLsn);
0406: boolean isLN = reader.isLN();
0407: boolean isIN = reader.isIN();
0408: boolean isRoot = reader.isRoot();
0409: boolean isFileHeader = reader.isFileHeader();
0410: boolean isObsolete = false;
0411:
0412: if (reader.isFileHeader()) {
0413: fileLogVersion = reader.getFileHeader()
0414: .getLogVersion();
0415: }
0416:
0417: /* Stop if the daemon is shut down. */
0418: if (env.isClosing()) {
0419: return false;
0420: }
0421:
0422: /* Update background reads. */
0423: int nReads = reader.getAndResetNReads();
0424: if (nReads > 0) {
0425: env.updateBackgroundReads(nReads);
0426: }
0427:
0428: /* Sleep if background read/write limit was exceeded. */
0429: env.sleepAfterBackgroundIO();
0430:
0431: /* Check for a known obsolete node. */
0432: while (nextObsolete < fileOffset
0433: && obsoleteIter.hasNext()) {
0434: nextObsolete = obsoleteIter.next();
0435: }
0436: if (nextObsolete == fileOffset) {
0437: isObsolete = true;
0438: }
0439:
0440: /* Check for the entry type next because it is very cheap. */
0441: if (!isObsolete && !isLN && !isIN && !isRoot) {
0442: /* Consider all entries we do not process as obsolete. */
0443: isObsolete = true;
0444: }
0445:
0446: /*
0447: * SR 14583: In JE 2.0 and later we can assume that all
0448: * deleted LNs are obsolete. Either the delete committed and
0449: * the BIN parent is marked with a pending deleted bit, or the
0450: * delete rolled back, in which case there is no reference
0451: * to this entry. JE 1.7.1 and earlier require a tree lookup
0452: * because deleted LNs may still be reachable through their BIN
0453: * parents.
0454: */
0455: if (!isObsolete && isLN && reader.getLN().isDeleted()
0456: && fileLogVersion > 2) {
0457: /* Deleted LNs are always obsolete. */
0458: isObsolete = true;
0459: }
0460:
0461: /* Check the current tracker last, as it is more expensive. */
0462: if (!isObsolete && tfs != null
0463: && tfs.containsObsoleteOffset(fileOffset)) {
0464: isObsolete = true;
0465: }
0466:
0467: /* Skip known obsolete nodes. */
0468: if (isObsolete) {
0469: /* Count obsolete stats. */
0470: if (isLN) {
0471: nLNsObsoleteThisRun++;
0472: } else if (isIN) {
0473: nINsObsoleteThisRun++;
0474: }
0475: /* Must update the pending DB set for obsolete entries. */
0476: DatabaseId dbId = reader.getDatabaseId();
0477: if (dbId != null) {
0478: checkPendingDbSet.add(dbId);
0479: }
0480: continue;
0481: }
0482:
0483: /* Evict before processing each entry. */
0484: if (Cleaner.DO_CRITICAL_EVICTION) {
0485: env.getEvictor().doCriticalEviction(true); // backgroundIO
0486: }
0487:
0488: /* The entry is not known to be obsolete -- process it now. */
0489: if (isLN) {
0490:
0491: LN targetLN = reader.getLN();
0492: DatabaseId dbId = reader.getDatabaseId();
0493: byte[] key = reader.getKey();
0494: byte[] dupKey = reader.getDupTreeKey();
0495:
0496: lookAheadCache.add(new Long(DbLsn
0497: .getFileOffset(logLsn)), new LNInfo(
0498: targetLN, dbId, key, dupKey));
0499:
0500: if (lookAheadCache.isFull()) {
0501: processLN(fileNum, location, lookAheadCache,
0502: dbCache, deferredWriteDbs);
0503: }
0504:
0505: /*
0506: * Process pending LNs before proceeding in order to
0507: * prevent the pending list from growing too large.
0508: */
0509: nProcessedLNs += 1;
0510: if (nProcessedLNs % PROCESS_PENDING_EVERY_N_LNS == 0) {
0511: cleaner.processPending();
0512: }
0513:
0514: } else if (isIN) {
0515:
0516: IN targetIN = reader.getIN();
0517: DatabaseId dbId = reader.getDatabaseId();
0518: DatabaseImpl db = dbMapTree.getDb(dbId,
0519: cleaner.lockTimeout, dbCache);
0520: targetIN.setDatabase(db);
0521: processIN(targetIN, db, logLsn, deferredWriteDbs);
0522:
0523: } else if (isRoot) {
0524:
0525: env.rewriteMapTreeRoot(logLsn);
0526: } else {
0527: assert false;
0528: }
0529: }
0530:
0531: /* Process remaining queued LNs. */
0532: while (!lookAheadCache.isEmpty()) {
0533: if (Cleaner.DO_CRITICAL_EVICTION) {
0534: env.getEvictor().doCriticalEviction(true); // backgroundIO
0535: }
0536: processLN(fileNum, location, lookAheadCache, dbCache,
0537: deferredWriteDbs);
0538: /* Sleep if background read/write limit was exceeded. */
0539: env.sleepAfterBackgroundIO();
0540: }
0541:
0542: /* Update the pending DB set. */
0543: for (Iterator i = checkPendingDbSet.iterator(); i.hasNext();) {
0544: DatabaseId dbId = (DatabaseId) i.next();
0545: DatabaseImpl db = dbMapTree.getDb(dbId,
0546: cleaner.lockTimeout, dbCache);
0547: cleaner.addPendingDB(db);
0548: }
0549:
0550: /* Update reader stats. */
0551: nEntriesReadThisRun = reader.getNumRead();
0552: nRepeatIteratorReadsThisRun = reader
0553: .getNRepeatIteratorReads();
0554:
0555: } finally {
0556: /* Subtract the overhead of this method from the budget. */
0557: budget.updateMiscMemoryUsage(0 - adjustMem);
0558:
0559: /* Release all cached DBs. */
0560: dbMapTree.releaseDbs(dbCache);
0561:
0562: /* Allow flushing of TFS when cleaning is complete. */
0563: if (tfs != null) {
0564: tfs.setAllowFlush(true);
0565: }
0566: }
0567:
0568: return true;
0569: }
0570:
0571: /**
0572: * Processes the first LN in the look ahead cache and removes it from the
0573: * cache. While the BIN is latched, look through the BIN for other LNs in
0574: * the cache; if any match, process them to avoid a tree search later.
0575: */
0576: private void processLN(Long fileNum, TreeLocation location,
0577: LookAheadCache lookAheadCache, Map dbCache,
0578: Set deferredWriteDbs) throws DatabaseException {
0579:
0580: nLNsCleanedThisRun++;
0581:
0582: /* Get the first LN from the queue. */
0583: Long offset = lookAheadCache.nextOffset();
0584: LNInfo info = lookAheadCache.remove(offset);
0585:
0586: LN ln = info.getLN();
0587: byte[] key = info.getKey();
0588: byte[] dupKey = info.getDupKey();
0589:
0590: long logLsn = DbLsn.makeLsn(fileNum.longValue(), offset
0591: .longValue());
0592:
0593: /*
0594: * Do not call releaseDb after this getDb, since the entire dbCache
0595: * will be released later.
0596: */
0597: DatabaseImpl db = env.getDbMapTree().getDb(info.getDbId(),
0598: cleaner.lockTimeout, dbCache);
0599:
0600: /* Status variables are used to generate debug tracing info. */
0601: boolean processedHere = true; // The LN was cleaned here.
0602: boolean obsolete = false; // The LN is no longer in use.
0603: boolean completed = false; // This method completed.
0604:
0605: BIN bin = null;
0606: DIN parentDIN = null; // for DupCountLNs
0607: try {
0608:
0609: /*
0610: * If the DB is gone, this LN is obsolete. If delete cleanup is in
0611: * progress, put the DB into the DB pending set; this LN will be
0612: * declared deleted after the delete cleanup is finished.
0613: */
0614: if (db == null || db.isDeleted()) {
0615: cleaner.addPendingDB(db);
0616: nLNsDeadThisRun++;
0617: obsolete = true;
0618: completed = true;
0619: return;
0620: }
0621:
0622: Tree tree = db.getTree();
0623: assert tree != null;
0624:
0625: /*
0626: * Search down to the bottom most level for the parent of this LN.
0627: */
0628: boolean parentFound = tree.getParentBINForChildLN(location,
0629: key, dupKey, ln, false, // splitsAllowed
0630: true, // findDeletedEntries
0631: false, // searchDupTree
0632: Cleaner.UPDATE_GENERATION);
0633: bin = location.bin;
0634: int index = location.index;
0635:
0636: if (!parentFound) {
0637: nLNsDeadThisRun++;
0638: obsolete = true;
0639: completed = true;
0640: return;
0641: }
0642:
0643: /*
0644: * Now we're at the parent for this LN, whether BIN, DBIN or DIN.
0645: * If knownDeleted, LN is deleted and can be purged.
0646: */
0647: if (bin.isEntryKnownDeleted(index)) {
0648: nLNsDeadThisRun++;
0649: obsolete = true;
0650: completed = true;
0651: return;
0652: }
0653:
0654: /*
0655: * Determine whether the parent is the current BIN, or in the case
0656: * of a DupCountLN, a DIN. Get the tree LSN in either case.
0657: */
0658: boolean isDupCountLN = ln.containsDuplicates();
0659: long treeLsn;
0660: if (isDupCountLN) {
0661: parentDIN = (DIN) bin.fetchTarget(index);
0662: parentDIN.latch(Cleaner.UPDATE_GENERATION);
0663: ChildReference dclRef = parentDIN.getDupCountLNRef();
0664: treeLsn = dclRef.getLsn();
0665: } else {
0666: treeLsn = bin.getLsn(index);
0667: }
0668:
0669: /* Process this LN that was found in the tree. */
0670: processedHere = false;
0671: processFoundLN(info, logLsn, treeLsn, bin, index, parentDIN);
0672: completed = true;
0673:
0674: /*
0675: * For all other non-deleted LNs in this BIN, lookup their LSN
0676: * in the LN queue and process any matches.
0677: */
0678: if (!isDupCountLN) {
0679: for (int i = 0; i < bin.getNEntries(); i += 1) {
0680: long binLsn = bin.getLsn(i);
0681: if (i != index
0682: && !bin.isEntryKnownDeleted(i)
0683: && !bin.isEntryPendingDeleted(i)
0684: && DbLsn.getFileNumber(binLsn) == fileNum
0685: .longValue()) {
0686:
0687: Long myOffset = new Long(DbLsn
0688: .getFileOffset(binLsn));
0689: LNInfo myInfo = lookAheadCache.remove(myOffset);
0690:
0691: if (myInfo != null) {
0692: nLNQueueHitsThisRun++;
0693: nLNsCleanedThisRun++;
0694: processFoundLN(myInfo, binLsn, binLsn, bin,
0695: i, null);
0696: }
0697: }
0698: }
0699: }
0700: return;
0701:
0702: } finally {
0703: noteDbsRequiringSync(db, deferredWriteDbs);
0704:
0705: if (parentDIN != null) {
0706: parentDIN.releaseLatchIfOwner();
0707: }
0708:
0709: if (bin != null) {
0710: bin.releaseLatchIfOwner();
0711: }
0712:
0713: if (processedHere) {
0714: cleaner.trace(cleaner.detailedTraceLevel,
0715: Cleaner.CLEAN_LN, ln, logLsn, completed,
0716: obsolete, false /*migrated*/);
0717: }
0718: }
0719: }
0720:
0721: /**
0722: * Processes an LN that was found in the tree. Lock the LN's node ID and
0723: * then set the entry's MIGRATE flag if the LSN of the LN log entry is the
0724: * active LSN in the tree.
0725: *
0726: * @param info identifies the LN log entry.
0727: *
0728: * @param logLsn is the LSN of the log entry.
0729: *
0730: * @param treeLsn is the LSN found in the tree.
0731: *
0732: * @param bin is the BIN found in the tree; is latched on method entry and
0733: * exit.
0734: *
0735: * @param index is the BIN index found in the tree.
0736: *
0737: * @param parentDIN is non-null for a DupCountLN only; if non-null, is
0738: * latched on method entry and exit.
0739: */
0740: private void processFoundLN(LNInfo info, long logLsn, long treeLsn,
0741: BIN bin, int index, DIN parentDIN) throws DatabaseException {
0742:
0743: LN ln = info.getLN();
0744: byte[] key = info.getKey();
0745: byte[] dupKey = info.getDupKey();
0746:
0747: DatabaseImpl db = bin.getDatabase();
0748: boolean isDupCountLN = parentDIN != null;
0749:
0750: /* Status variables are used to generate debug tracing info. */
0751: boolean obsolete = false; // The LN is no longer in use.
0752: boolean migrated = false; // The LN was in use and is migrated.
0753: boolean lockDenied = false;// The LN lock was denied.
0754: boolean completed = false; // This method completed.
0755:
0756: long nodeId = ln.getNodeId();
0757: BasicLocker locker = null;
0758: try {
0759: Tree tree = db.getTree();
0760: assert tree != null;
0761:
0762: /*
0763: * If the tree and log LSNs are equal, then we can be fairly
0764: * certain that the log entry is current; in that case, it is
0765: * wasteful to lock the LN here -- it is better to lock only once
0766: * during lazy migration. But if the tree and log LSNs differ, it
0767: * is likely that another thread has updated or deleted the LN and
0768: * the log LSN is now obsolete; in this case we can avoid dirtying
0769: * the BIN by checking for obsoleteness here, which requires
0770: * locking. The latter case can occur frequently if trackDetail is
0771: * false.
0772: *
0773: * 1. If the LSN in the tree and in the log are the same, we will
0774: * attempt to migrate it.
0775: *
0776: * 2. If the LSN in the tree is < the LSN in the log, the log entry
0777: * is obsolete, because this LN has been rolled back to a previous
0778: * version by a txn that aborted.
0779: *
0780: * 3. If the LSN in the tree is > the LSN in the log, the log entry
0781: * is obsolete, because the LN was advanced forward by some
0782: * now-committed txn.
0783: *
0784: * 4. If the LSN in the tree is a null LSN, the log entry is
0785: * obsolete. A slot can only have a null LSN if the record has
0786: * never been written to disk in a deferred write database, and
0787: * in that case the log entry must be for a past, deleted version
0788: * of that record.
0789: */
0790: if (ln.isDeleted() && (treeLsn == logLsn)
0791: && fileLogVersion <= 2) {
0792:
0793: /*
0794: * SR 14583: After JE 2.0, deleted LNs are never found in the
0795: * tree, since we can assume they're obsolete and correctly
0796: * marked as such in the obsolete offset tracking. JE 1.7.1 and
0797: * earlier did not use the pending deleted bit, so deleted LNs
0798: * may still be reachable through their BIN parents.
0799: */
0800: obsolete = true;
0801: nLNsDeadThisRun++;
0802: bin.setPendingDeleted(index);
0803: } else if (treeLsn == DbLsn.NULL_LSN) {
0804:
0805: /*
0806: * Case 4: The LN in the tree is a never-written LN for a
0807: * deferred-write db, so the LN in the file is obsolete.
0808: */
0809: obsolete = true;
0810: } else if (treeLsn != logLsn) {
0811:
0812: /*
0813: * Check to see whether the LN being migrated is locked
0814: * elsewhere. Do that by attempting to lock it. We can hold
0815: * the latch on the BIN (and DIN) since we always attempt to
0816: * acquire a non-blocking read lock. Holding the latch ensures
0817: * that the INs won't change underneath us because of splits or
0818: * eviction.
0819: */
0820: locker = new BasicLocker(env);
0821: LockResult lockRet = locker.nonBlockingLock(nodeId,
0822: LockType.READ, db);
0823: if (lockRet.getLockGrant() == LockGrantType.DENIED) {
0824:
0825: /*
0826: * LN is currently locked by another Locker, so we can't
0827: * assume anything about the value of the LSN in the bin.
0828: */
0829: nLNsLockedThisRun++;
0830: lockDenied = true;
0831: } else {
0832: /* The LN is obsolete and can be purged. */
0833: nLNsDeadThisRun++;
0834: obsolete = true;
0835: }
0836: }
0837:
0838: if (!obsolete && !lockDenied) {
0839:
0840: /*
0841: * Set the migrate flag and dirty the parent IN. The evictor
0842: * or checkpointer will migrate the LN later.
0843: *
0844: * Then set the target node so it does not have to be fetched
0845: * when it is migrated, if the tree and log LSNs are equal and
0846: * the target is not resident. We must call postFetchInit to
0847: * initialize MapLNs that have not been fully initialized yet
0848: * [#13191].
0849: */
0850: if (isDupCountLN) {
0851: ChildReference dclRef = parentDIN
0852: .getDupCountLNRef();
0853: dclRef.setMigrate(true);
0854: parentDIN.setDirty(true);
0855:
0856: if (treeLsn == logLsn && dclRef.getTarget() == null) {
0857: ln.postFetchInit(db, logLsn);
0858: parentDIN.updateDupCountLN(ln);
0859: }
0860: } else {
0861: bin.setMigrate(index, true);
0862: bin.setDirty(true);
0863:
0864: if (treeLsn == logLsn
0865: && bin.getTarget(index) == null) {
0866: ln.postFetchInit(db, logLsn);
0867: bin.updateEntry(index, ln);
0868: /* Ensure keys are transactionally correct. [#15704] */
0869: bin.updateKeyIfChanged(index, bin
0870: .containsDuplicates() ? dupKey : key);
0871: }
0872:
0873: /*
0874: * If the generation is zero, we fetched this BIN just for
0875: * cleaning.
0876: */
0877: if (PROHIBIT_DELTAS_WHEN_FETCHING
0878: && bin.getGeneration() == 0) {
0879: bin.setProhibitNextDelta();
0880: }
0881:
0882: /*
0883: * Update the generation so that the BIN is not evicted
0884: * immediately. This allows the cleaner to fill in as many
0885: * entries as possible before eviction, as to-be-cleaned
0886: * files are processed.
0887: */
0888: bin.setGeneration();
0889: }
0890:
0891: nLNsMarkedThisRun++;
0892: migrated = true;
0893: }
0894: completed = true;
0895: } finally {
0896: if (locker != null) {
0897: locker.operationEnd();
0898: }
0899:
0900: /*
0901: * If a write lock is held, it is likely that the log LSN will
0902: * become obsolete. It is more efficient to process this via the
0903: * pending list than to set the MIGRATE flag, dirty the BIN, and
0904: * cause the BIN to be logged unnecessarily.
0905: */
0906: if (completed && lockDenied) {
0907: fileSelector.addPendingLN(ln, db.getId(), key, dupKey);
0908: }
0909:
0910: cleaner.trace(cleaner.detailedTraceLevel, Cleaner.CLEAN_LN,
0911: ln, logLsn, completed, obsolete, migrated);
0912: }
0913: }
0914:
0915: /**
0916: * If an IN is still in use in the in-memory tree, dirty it. The checkpoint
0917: * invoked at the end of the cleaning run will end up rewriting it.
0918: */
0919: private void processIN(IN inClone, DatabaseImpl db, long logLsn,
0920: Set deferredWriteDbs) throws DatabaseException {
0921:
0922: boolean obsolete = false;
0923: boolean dirtied = false;
0924: boolean completed = false;
0925:
0926: try {
0927: nINsCleanedThisRun++;
0928:
0929: /*
0930: * If the DB is gone, this LN is obsolete. If delete cleanup is in
0931: * progress, put the DB into the DB pending set; this LN will be
0932: * declared deleted after the delete cleanup is finished.
0933: */
0934: if (db == null || db.isDeleted()) {
0935: cleaner.addPendingDB(db);
0936: nINsDeadThisRun++;
0937: obsolete = true;
0938: completed = true;
0939: return;
0940: }
0941:
0942: Tree tree = db.getTree();
0943: assert tree != null;
0944:
0945: IN inInTree = findINInTree(tree, db, inClone, logLsn);
0946:
0947: if (inInTree == null) {
0948: /* IN is no longer in the tree. Do nothing. */
0949: nINsDeadThisRun++;
0950: obsolete = true;
0951: } else {
0952:
0953: /*
0954: * IN is still in the tree. Dirty it. Checkpoint or eviction
0955: * will write it out. Prohibit the next delta, since the
0956: * original version must be made obsolete.
0957: */
0958: nINsMigratedThisRun++;
0959: inInTree.setDirty(true);
0960: inInTree.setProhibitNextDelta();
0961: inInTree.releaseLatch();
0962: dirtied = true;
0963: }
0964:
0965: completed = true;
0966: } finally {
0967: noteDbsRequiringSync(db, deferredWriteDbs);
0968:
0969: cleaner.trace(cleaner.detailedTraceLevel, Cleaner.CLEAN_IN,
0970: inClone, logLsn, completed, obsolete, dirtied);
0971: }
0972: }
0973:
0974: /**
0975: * Given a clone of an IN that has been taken out of the log, try to find
0976: * it in the tree and verify that it is the current one in the log.
0977: * Returns the node in the tree if it is found and it is current re: LSN's.
0978: * Otherwise returns null if the clone is not found in the tree or it's not
0979: * the latest version. Caller is responsible for unlatching the returned
0980: * IN.
0981: */
0982: private IN findINInTree(Tree tree, DatabaseImpl db, IN inClone,
0983: long logLsn) throws DatabaseException {
0984:
0985: /* Check if inClone is the root. */
0986: if (inClone.isDbRoot()) {
0987: IN rootIN = isRoot(tree, db, inClone, logLsn);
0988: if (rootIN == null) {
0989:
0990: /*
0991: * inClone is a root, but no longer in use. Return now, because
0992: * a call to tree.getParentNode will return something
0993: * unexpected since it will try to find a parent.
0994: */
0995: return null;
0996: } else {
0997: return rootIN;
0998: }
0999: }
1000:
1001: /* It's not the root. Can we find it, and if so, is it current? */
1002: inClone.latch(Cleaner.UPDATE_GENERATION);
1003: SearchResult result = null;
1004: try {
1005:
1006: result = tree
1007: .getParentINForChildIN(inClone, true, // requireExactMatch
1008: Cleaner.UPDATE_GENERATION, inClone
1009: .getLevel(), null); // trackingList
1010:
1011: if (!result.exactParentFound) {
1012: return null;
1013: }
1014:
1015: long treeLsn = result.parent.getLsn(result.index);
1016:
1017: /*
1018: * The IN in the tree is a never-written IN for a DW db so the IN
1019: * in the file is obsolete. [#15588]
1020: */
1021: if (treeLsn == DbLsn.NULL_LSN) {
1022: return null;
1023: }
1024:
1025: int compareVal = DbLsn.compareTo(treeLsn, logLsn);
1026:
1027: if (compareVal > 0) {
1028: /* Log entry is obsolete. */
1029: return null;
1030: } else {
1031:
1032: /*
1033: * Log entry is same or newer than what's in the tree. Dirty
1034: * the IN and let checkpoint write it out.
1035: */
1036: IN in;
1037: if (compareVal == 0) {
1038: /* We can reuse the log entry if the LSNs are equal. */
1039: in = (IN) result.parent.getTarget(result.index);
1040: if (in == null) {
1041: in = inClone;
1042: in.postFetchInit(db, logLsn);
1043: result.parent.updateEntry(result.index, in);
1044: }
1045: } else {
1046: in = (IN) result.parent.fetchTarget(result.index);
1047: }
1048: in.latch(Cleaner.UPDATE_GENERATION);
1049: return in;
1050: }
1051: } finally {
1052: if ((result != null) && (result.exactParentFound)) {
1053: result.parent.releaseLatch();
1054: }
1055: }
1056: }
1057:
1058: /*
1059: * When we process a target log entry for a deferred write db, we may
1060: * need to sync the db at the next checkpoint.
1061: * Cases are:
1062: * IN found in the tree:
1063: * The IN is dirtied and must be written out at the next ckpt.
1064: * IN not found in the tree:
1065: * This log entry is not in use by the in-memory tree, but a later
1066: * recovery has the possibility of reverting to the last synced
1067: * version. To prevent that, we have to sync the database before
1068: * deleting the file.
1069: * LN found in tree:
1070: * It will be migrated, need to be synced.
1071: * LN not found in tree:
1072: * Like not-found IN, need to be sure that the database is
1073: * sufficiently synced.
1074: * Note that if nothing in the db is actually dirty (LN and IN are not
1075: * found) there's no harm done, there will be no sync and no extra
1076: * processing.
1077: */
1078: private void noteDbsRequiringSync(DatabaseImpl db,
1079: Set deferredWriteDbs) {
1080:
1081: /*
1082: * We add all non-deleted DBs to the set, not just DeferredWrite DBs,
1083: * because any DB may be opened as DeferredWrite at a future time. If
1084: * is it opened as DeferredWrite between now and the time the
1085: * checkpointer runs, we must be sure to flush it during the
1086: * checkpoint. For example, if the DB is not currently open by a user
1087: * but is being cleaned, it will not be in DeferredWrite mode. But a
1088: * user may open it as DeferredWrite at any time, and its mode will
1089: * change to DeferredWrite. [#15913]
1090: */
1091: if (db != null && !db.isDeleted()) {
1092: deferredWriteDbs.add(db.getId());
1093: }
1094: }
1095:
1096: /**
1097: * Get the current root in the tree, or null if the inClone
1098: * is the current root.
1099: */
1100: private static class RootDoWork implements WithRootLatched {
1101: private DatabaseImpl db;
1102: private IN inClone;
1103: private long logLsn;
1104:
1105: RootDoWork(DatabaseImpl db, IN inClone, long logLsn) {
1106: this .db = db;
1107: this .inClone = inClone;
1108: this .logLsn = logLsn;
1109: }
1110:
1111: public IN doWork(ChildReference root) throws DatabaseException {
1112:
1113: if (root == null
1114: || (root.getLsn() == DbLsn.NULL_LSN)
1115: || // deferred write root
1116: (root.fetchTarget(db, null).getNodeId() != inClone
1117: .getNodeId())) {
1118: return null;
1119: }
1120:
1121: /*
1122: * A root LSN less than the log LSN must be an artifact of when we
1123: * didn't properly propagate the logging of the rootIN up to the
1124: * root ChildReference. We still do this for compatibility with
1125: * old log versions but may be able to remove it in the future.
1126: */
1127: if (DbLsn.compareTo(root.getLsn(), logLsn) <= 0) {
1128: IN rootIN = (IN) root.fetchTarget(db, null);
1129: rootIN.latch(Cleaner.UPDATE_GENERATION);
1130: return rootIN;
1131: } else {
1132: return null;
1133: }
1134: }
1135: }
1136:
1137: /**
1138: * Check if the cloned IN is the same node as the root in tree. Return the
1139: * real root if it is, null otherwise. If non-null is returned, the
1140: * returned IN (the root) is latched -- caller is responsible for
1141: * unlatching it.
1142: */
1143: private IN isRoot(Tree tree, DatabaseImpl db, IN inClone, long lsn)
1144: throws DatabaseException {
1145:
1146: RootDoWork rdw = new RootDoWork(db, inClone, lsn);
1147: return tree.withRootLatchedShared(rdw);
1148: }
1149:
1150: /**
1151: * Reset per-run counters.
1152: */
1153: private void resetPerRunCounters() {
1154: nINsObsoleteThisRun = 0;
1155: nINsCleanedThisRun = 0;
1156: nINsDeadThisRun = 0;
1157: nINsMigratedThisRun = 0;
1158: nLNsObsoleteThisRun = 0;
1159: nLNsCleanedThisRun = 0;
1160: nLNsDeadThisRun = 0;
1161: nLNsMigratedThisRun = 0;
1162: nLNsMarkedThisRun = 0;
1163: nLNQueueHitsThisRun = 0;
1164: nLNsLockedThisRun = 0;
1165: nEntriesReadThisRun = 0;
1166: nRepeatIteratorReadsThisRun = 0;
1167: }
1168:
1169: /**
1170: * Add per-run counters to total counters.
1171: */
1172: private void accumulatePerRunCounters() {
1173: cleaner.nINsObsolete += nINsObsoleteThisRun;
1174: cleaner.nINsCleaned += nINsCleanedThisRun;
1175: cleaner.nINsDead += nINsDeadThisRun;
1176: cleaner.nINsMigrated += nINsMigratedThisRun;
1177: cleaner.nLNsObsolete += nLNsObsoleteThisRun;
1178: cleaner.nLNsCleaned += nLNsCleanedThisRun;
1179: cleaner.nLNsDead += nLNsDeadThisRun;
1180: cleaner.nLNsMigrated += nLNsMigratedThisRun;
1181: cleaner.nLNsMarked += nLNsMarkedThisRun;
1182: cleaner.nLNQueueHits += nLNQueueHitsThisRun;
1183: cleaner.nLNsLocked += nLNsLockedThisRun;
1184: cleaner.nRepeatIteratorReads += nRepeatIteratorReadsThisRun;
1185: }
1186:
1187: /**
1188: * A cache of LNInfo by LSN offset. Used to hold a set of LNs that are
1189: * to be processed. Keeps track of memory used, and when full (over
1190: * budget) the next offset should be queried and removed.
1191: */
1192: private static class LookAheadCache {
1193:
1194: private SortedMap map;
1195: private int maxMem;
1196: private int usedMem;
1197:
1198: LookAheadCache(int lookAheadCacheSize) {
1199: map = new TreeMap();
1200: maxMem = lookAheadCacheSize;
1201: usedMem = MemoryBudget.TREEMAP_OVERHEAD;
1202: }
1203:
1204: boolean isEmpty() {
1205: return map.isEmpty();
1206: }
1207:
1208: boolean isFull() {
1209: return usedMem >= maxMem;
1210: }
1211:
1212: Long nextOffset() {
1213: return (Long) map.firstKey();
1214: }
1215:
1216: void add(Long lsnOffset, LNInfo info) {
1217: map.put(lsnOffset, info);
1218: usedMem += info.getMemorySize();
1219: usedMem += MemoryBudget.TREEMAP_ENTRY_OVERHEAD;
1220: }
1221:
1222: LNInfo remove(Long offset) {
1223: LNInfo info = (LNInfo) map.remove(offset);
1224: if (info != null) {
1225: usedMem -= info.getMemorySize();
1226: usedMem -= MemoryBudget.TREEMAP_ENTRY_OVERHEAD;
1227: }
1228: return info;
1229: }
1230: }
1231: }
|