001: /*-
002: * See the file LICENSE for redistribution information.
003: *
004: * Copyright (c) 2002,2008 Oracle. All rights reserved.
005: *
006: * $Id: SortedLSNTreeWalker.java,v 1.17.2.5 2008/01/07 15:14:09 cwl Exp $
007: */
008:
009: package com.sleepycat.je.dbi;
010:
011: import java.util.Arrays;
012: import java.util.HashSet;
013: import java.util.Iterator;
014: import java.util.List;
015: import java.util.Set;
016:
017: import com.sleepycat.je.DatabaseEntry;
018: import com.sleepycat.je.DatabaseException;
019: import com.sleepycat.je.cleaner.OffsetList;
020: import com.sleepycat.je.log.LogEntryType;
021: import com.sleepycat.je.log.entry.LNLogEntry;
022: import com.sleepycat.je.log.entry.LogEntry;
023: import com.sleepycat.je.tree.BIN;
024: import com.sleepycat.je.tree.ChildReference;
025: import com.sleepycat.je.tree.DBIN;
026: import com.sleepycat.je.tree.DIN;
027: import com.sleepycat.je.tree.DupCountLN;
028: import com.sleepycat.je.tree.IN;
029: import com.sleepycat.je.tree.LN;
030: import com.sleepycat.je.tree.Node;
031: import com.sleepycat.je.utilint.DbLsn;
032:
033: /**
034: * Class to walk over the tree using sorted LSN fetching for parts of the tree
035: * that are not in memory. Returns LSNs for each node in the tree
036: * <b>except</b> the root IN, but in an arbitrary order (i.e. not key
037: * order). The caller is responsible for getting the root IN's LSN explicitly.
038: * <p>
039: * A calllback function specified in the constructor is executed for each LSN
040: * found.
041: * <p>
042: * The walker works in two phases. The first phase is to gather and return all
043: * the INs from the INList that match the database being iterated over. For
044: * each IN, all of the LSNs of the children are passed to the callback method
045: * (processLSN). If the child was not in memory, it is added to a list of LSNs
046: * to read. When all of the in-memory INs have been processed, the list of
047: * LSNs that were harvested are sorted.
048: * <p>
049: * Then for each of the sorted LSNs, the target is fetched, the type
050: * determined, and the LSN and type passed to the callback method for
051: * processing. LSNs of the children of those nodes are retrieved and the
052: * process repeated until there are no more nodes to be fetched for this
053: * database's tree.
054: */
055: public class SortedLSNTreeWalker {
056:
057: /*
058: * The interface for calling back to the user with each LSN.
059: */
060: public interface TreeNodeProcessor {
061: void processLSN(long childLSN, LogEntryType childType,
062: Node theNode, byte[] lnKey) throws DatabaseException;
063:
064: /* Used for processing dirty (unlogged) deferred write LNs. [#15365] */
065: void processDirtyDeletedLN(long childLSN, LN ln, byte[] lnKey)
066: throws DatabaseException;
067:
068: /* Used when processing DW dbs where there are no LSNs. */
069: void processDupCount(long count);
070: }
071:
072: /*
073: * Optionally passed to the SortedLSNTreeWalker to be called when an
074: * exception occurs.
075: */
076: public interface ExceptionPredicate {
077: /* Return true if the exception can be ignored. */
078: boolean ignoreException(Exception e);
079: }
080:
081: protected DatabaseImpl dbImpl;
082: private EnvironmentImpl envImpl;
083:
084: /*
085: * Save the root LSN at construction time, because the root may be
086: * nulled out before walk() executes.
087: */
088: private long rootLsn;
089:
090: /* Indicates whether db has allowDuplicates set. */
091: private boolean dups;
092:
093: /*
094: * Set removeINsFromINList to true if INs read from the INList should be
095: * removed.
096: */
097: private boolean removeINsFromINList;
098:
099: /*
100: * Whether to call DatabaseImpl.finishedINListHarvest().
101: */
102: private boolean setDbState;
103:
104: /*
105: * An array (and index) of LSNs that were accumulated in a previous pass
106: * over the tree.
107: */
108: private long[] currentLSNs;
109: private int currentLSNIdx = 0;
110:
111: /*
112: * A list of LSNs being accumulated. Once they have been accumulated, they
113: * will be moved to currentLSNs, fetched, and returned to the user.
114: *
115: * Store this in two OffsetLists, one for the file number portion of the
116: * LSN and the other for the file offset portion since OffsetLists can only
117: * store ints, not longs.
118: */
119: private OffsetList accumulatedLSNFileNumbers;
120: private OffsetList accumulatedLSNFileOffsets;
121:
122: private TreeNodeProcessor callback;
123:
124: /*
125: * If true, then walker should also accumulate LNs and pass them in sorted
126: * order to the TreeNodeProcessor callback method.
127: */
128: protected boolean accumulateLNs = false;
129:
130: /*
131: * If true, then walker should process Dup Trees all the way to the bottom.
132: * If false, then walker only processes the root DIN and DupCountLN.
133: */
134: private boolean processDupTree = true;
135:
136: /*
137: * If true, then we still pass nodes that have null lsns (i.e. during
138: * DeferredWrite DB processing in Database.count().
139: */
140: private boolean passNullLSNNodes = false;
141:
142: /*
143: * If non-null, save any exceptions encountered while traversing nodes into
144: * this savedException list, in order to walk as much of the tree as
145: * possible. The caller of the tree walker will handle the exceptions.
146: */
147: private List savedExceptions;
148:
149: private ExceptionPredicate excPredicate;
150:
151: /* Holder for returning LN key from fetchLSN. */
152: private DatabaseEntry lnKeyEntry = new DatabaseEntry();
153:
154: /*
155: * @param rootLsn is passed in addition to the dbImpl, because the
156: * root may be nulled out on the dbImpl before walk() is called.
157: */
158: public SortedLSNTreeWalker(DatabaseImpl dbImpl,
159: boolean removeINsFromINList, boolean setDbState,
160: long rootLsn, TreeNodeProcessor callback,
161: List savedExceptions, ExceptionPredicate excPredicate)
162: throws DatabaseException {
163:
164: /* This iterator is used on both deleted and undeleted databases. */
165: this .dbImpl = dbImpl;
166: this .envImpl = dbImpl.getDbEnvironment();
167: if (envImpl == null) {
168: throw new DatabaseException(
169: "environmentImpl is null for target db "
170: + dbImpl.getDebugName());
171: }
172: this .dups = dbImpl.getSortedDuplicates();
173:
174: this .removeINsFromINList = removeINsFromINList;
175: this .setDbState = setDbState;
176: this .rootLsn = rootLsn;
177: this .callback = callback;
178: this .savedExceptions = savedExceptions;
179: this .excPredicate = excPredicate;
180: currentLSNs = new long[0];
181: currentLSNIdx = 0;
182: }
183:
184: void setProcessDupTree(boolean processDupTree) {
185: this .processDupTree = processDupTree;
186: }
187:
188: void setPassNullLSNNodes(boolean passNullLSNNodes) {
189: this .passNullLSNNodes = passNullLSNNodes;
190: }
191:
192: /*
193: * Return true if some INs were found on the INList for this db.
194: */
195: private boolean extractINsForDb(INList inList)
196: throws DatabaseException {
197:
198: boolean foundSome = false;
199:
200: /* Search the INList and put all qualifying INs into another list. */
201: Set foundSet = new HashSet();
202: long memoryChange = 0;
203: MemoryBudget mb = envImpl.getMemoryBudget();
204: inList.latchMajor();
205: try {
206: /* Consolidate the INList first. */
207: inList.latchMinorAndDumpAddedINs();
208:
209: Iterator iter = inList.iterator();
210: while (iter.hasNext()) {
211: IN this IN = (IN) iter.next();
212: if (this IN.getDatabase() == dbImpl) {
213: foundSome = true;
214: if (removeINsFromINList) {
215: iter.remove();
216: memoryChange += (this IN.getAccumulatedDelta() - this IN
217: .getInMemorySize());
218: this IN.setInListResident(false);
219: }
220: foundSet.add(this IN);
221: }
222: }
223: } catch (DatabaseException e) {
224: /* Update the memory budget with any changes. */
225: mb.updateTreeMemoryUsage(memoryChange);
226: throw e;
227: } finally {
228: inList.releaseMajorLatch();
229: }
230:
231: /*
232: * Do processing outside of INList latch in order to reduce lockout
233: * of checkpointing and eviction.
234: */
235: if (foundSome) {
236: Iterator iter = foundSet.iterator();
237: while (iter.hasNext()) {
238: IN this IN = (IN) iter.next();
239: accumulateLSNs(this IN);
240: }
241: }
242:
243: /*
244: * Update the memory in one fell swoop after releasing all references
245: * to INs in order to reduce contention on memory budget contention
246: * latch. Wait until all references to INs are released.
247: */
248: foundSet = null;
249: mb.updateTreeMemoryUsage(memoryChange);
250:
251: return foundSome;
252: }
253:
254: /**
255: * Find all non-resident nodes, and execute the callback. The root IN's
256: * LSN is not returned to the callback.
257: */
258: public void walk() throws DatabaseException {
259:
260: walkInternal();
261: }
262:
263: protected void walkInternal() throws DatabaseException {
264:
265: INList inList = envImpl.getInMemoryINs();
266: IN root = null;
267: if (!extractINsForDb(inList)) {
268: if (rootLsn == DbLsn.NULL_LSN) {
269: return;
270: }
271:
272: root = getRootIN(rootLsn);
273: accumulateLSNs(root);
274: releaseRootIN(root);
275: }
276:
277: if (setDbState) {
278: dbImpl.finishedINListHarvest();
279: }
280:
281: while (true) {
282: maybeGetMoreINs();
283: if (currentLSNs != null
284: && currentLSNIdx < currentLSNs.length) {
285: fetchAndProcessLSN(currentLSNs[currentLSNIdx++]);
286: } else {
287: break;
288: }
289: }
290: }
291:
292: private void maybeGetMoreINs() {
293:
294: if ((currentLSNs != null && currentLSNIdx >= currentLSNs.length)) {
295:
296: if (accumulatedLSNFileNumbers == null
297: || accumulatedLSNFileNumbers.size() == 0) {
298:
299: /* Nothing left to process. Mark completion of second phase. */
300: currentLSNs = null;
301: currentLSNIdx = Integer.MAX_VALUE;
302: return;
303: }
304:
305: long[] tempFileNumbers = accumulatedLSNFileNumbers
306: .toArray();
307: long[] tempFileOffsets = accumulatedLSNFileOffsets
308: .toArray();
309: int nLSNs = tempFileNumbers.length;
310: currentLSNIdx = 0;
311: currentLSNs = new long[nLSNs];
312: for (int i = 0; i < nLSNs; i++) {
313: currentLSNs[i] = DbLsn.makeLsn(tempFileNumbers[i],
314: tempFileOffsets[i]);
315: }
316:
317: Arrays.sort(currentLSNs);
318: accumulatedLSNFileNumbers = null;
319: accumulatedLSNFileOffsets = null;
320: }
321: }
322:
323: private void accumulateLSNs(IN in) throws DatabaseException {
324:
325: boolean accumulate = true;
326:
327: /*
328: * If this is the bottom of the tree and we're not accumulating LNs,
329: * then there's no need to accumulate any more LSNs, but we still need
330: * to callback with each of them.
331: */
332: boolean childIsLN = (!dups && (in instanceof BIN))
333: || (in instanceof DBIN);
334: if (childIsLN) {
335: if (!accumulateLNs) {
336:
337: /*
338: * No need to accumulate the LSNs of a non-dup BIN or a DBIN.
339: */
340: accumulate = false;
341: }
342: }
343:
344: boolean isDINRoot = (in instanceof DIN) && in.isRoot();
345:
346: /*
347: * Process all children, but only accumulate LSNs for children that are
348: * not in memory.
349: */
350: if (processDupTree || !in.containsDuplicates()) {
351: for (int i = 0; i < in.getNEntries(); i++) {
352:
353: long lsn = in.getLsn(i);
354: Node node = in.getTarget(i);
355:
356: if (in.isEntryPendingDeleted(i)
357: || in.isEntryKnownDeleted(i)) {
358:
359: /* Dirty LNs (deferred write) get special treatment. */
360: if (node instanceof LN) {
361: LN ln = (LN) node;
362: if (ln.isDirty()) {
363: callback.processDirtyDeletedLN(lsn, ln, in
364: .getKey(i));
365: }
366: }
367: continue;
368: }
369:
370: if (accumulate && (node == null)) {
371: if (accumulatedLSNFileNumbers == null) {
372: accumulatedLSNFileNumbers = new OffsetList();
373: accumulatedLSNFileOffsets = new OffsetList();
374: }
375:
376: accumulatedLSNFileNumbers.add(DbLsn
377: .getFileNumber(lsn), false);
378: accumulatedLSNFileOffsets.add(DbLsn
379: .getFileOffset(lsn), false);
380:
381: /*
382: * If we're maintaining a map from LSN to owning IN/index,
383: * then update the map here.
384: */
385: addToLsnINMap(new Long(lsn), in, i);
386: /* callback.processLSN is called when we fetch this LSN. */
387: } else if (lsn != DbLsn.NULL_LSN || passNullLSNNodes) {
388:
389: /*
390: * If the child is resident, use that log type, else we can
391: * assume it's a LN.
392: */
393: byte[] lnKey = (node == null || node instanceof LN) ? in
394: .getKey(i)
395: : null;
396: callback.processLSN(lsn,
397: (node == null) ? LogEntryType.LOG_LN : node
398: .getLogType(), node, lnKey);
399: }
400: }
401: }
402:
403: /* Handle the DupCountLN for a DIN root. */
404: if (isDINRoot) {
405: DIN din = (DIN) in;
406: ChildReference dupCountLNRef = din.getDupCountLNRef();
407: long lsn = dupCountLNRef.getLsn();
408: if (lsn == DbLsn.NULL_LSN) {
409: DupCountLN dcl = (DupCountLN) din.getDupCountLN();
410: callback.processDupCount(dcl.getDupCount());
411: } else {
412: /* Negative index signifies a DupCountLN. */
413: addToLsnINMap(new Long(lsn), in, -1);
414: Node node = fetchLSN(lsn, lnKeyEntry);
415: callback.processLSN(lsn, LogEntryType.LOG_DUPCOUNTLN,
416: node, dupCountLNRef.getKey());
417: }
418: }
419: }
420:
421: /*
422: * Fetch the node at 'lsn' and callback to let the invoker process it. If
423: * it is an IN, accumulate LSNs for it.
424: */
425: private void fetchAndProcessLSN(long lsn) throws DatabaseException {
426:
427: try {
428: lnKeyEntry.setData(null);
429: Node node = fetchLSN(lsn, lnKeyEntry);
430: if (node != null) {
431: callback.processLSN(lsn, node.getLogType(), node,
432: lnKeyEntry.getData());
433:
434: if (node instanceof IN) {
435: accumulateLSNs((IN) node);
436: }
437: }
438: } catch (DatabaseException e) {
439: if (excPredicate == null
440: || !excPredicate.ignoreException(e)) {
441: if (savedExceptions != null) {
442:
443: /*
444: * This LSN fetch hit a failure. Do as much of the rest of
445: * the tree as possible.
446: */
447: savedExceptions.add(e);
448: } else {
449: throw e;
450: }
451: }
452: }
453: }
454:
455: /**
456: * The default behavior fetches the rootIN from the log, but classes
457: * extending this may fetch the root from the tree.
458: */
459: protected IN getRootIN(long rootLsn) throws DatabaseException {
460:
461: return (IN) envImpl.getLogManager().get(rootLsn);
462: }
463:
464: protected void releaseRootIN(IN ignore) throws DatabaseException {
465:
466: /*
467: * There's no root IN latch in a vanilla Sorted LSN Tree Walk because
468: * we just fetched the root from the log.
469: */
470: }
471:
472: /**
473: * @param index a negative index signifies a DupCountLN.
474: */
475: protected void addToLsnINMap(Long lsn, IN in, int index) {
476: }
477:
478: protected Node fetchLSN(long lsn, DatabaseEntry lnKeyEntry)
479: throws DatabaseException {
480:
481: LogEntry entry = envImpl.getLogManager().getLogEntry(lsn);
482: if (entry instanceof LNLogEntry) {
483: lnKeyEntry.setData(((LNLogEntry) entry).getKey());
484: }
485: return (Node) entry.getMainItem();
486: }
487:
488: public List getSavedExceptions() {
489: return savedExceptions;
490: }
491: }
|