SortedLSNTreeWalker


1   /*-
2    * See the file LICENSE for redistribution information.
3    *
4    * Copyright (c) 2002,2006 Oracle.  All rights reserved.
5    *
6    * $Id: SortedLSNTreeWalker.java,v 1.16 2006/11/03 03:07:50 mark Exp $
7    */
8   
9   package com.sleepycat.je.dbi;
10  
11  import java.util.Arrays  ;
12  import java.util.HashSet  ;
13  import java.util.Iterator  ;
14  import java.util.List  ;
15  import java.util.Set  ;
16  
17  import com.sleepycat.je.DatabaseEntry;
18  import com.sleepycat.je.DatabaseException;
19  import com.sleepycat.je.cleaner.OffsetList;
20  import com.sleepycat.je.log.LogEntryType;
21  import com.sleepycat.je.log.entry.LNLogEntry;
22  import com.sleepycat.je.log.entry.LogEntry;
23  import com.sleepycat.je.tree.ChildReference;
24  import com.sleepycat.je.tree.BIN;
25  import com.sleepycat.je.tree.DBIN;
26  import com.sleepycat.je.tree.DIN;
27  import com.sleepycat.je.tree.DupCountLN;
28  import com.sleepycat.je.tree.IN;
29  import com.sleepycat.je.tree.LN;
30  import com.sleepycat.je.tree.Node;
31  import com.sleepycat.je.utilint.DbLsn;
32  
33  /**
34   * Class to walk over the tree using sorted LSN fetching for parts of the tree
35   * that are not in memory.  Returns LSNs for each node in the tree
36   * <b>except</b> the root IN, but in an arbitrary order (i.e. not key
37   * order). The caller is responsible for getting the root IN's LSN explicitly.
38   * <p>
39   * A calllback function specified in the constructor is executed for each LSN
40   * found.
41   * <p>
42   * The walker works in two phases.  The first phase is to gather and return all
43   * the INs from the INList that match the database being iterated over.  For
44   * each IN, all of the LSNs of the children are passed to the callback method
45   * (processLSN).  If the child was not in memory, it is added to a list of LSNs
46   * to read.  When all of the in-memory INs have been processed, the list of
47   * LSNs that were harvested are sorted.
48   * <p>
49   * Then for each of the sorted LSNs, the target is fetched, the type
50   * determined, and the LSN and type passed to the callback method for
51   * processing.  LSNs of the children of those nodes are retrieved and the
52   * process repeated until there are no more nodes to be fetched for this
53   * database's tree.
54   */
55  public class SortedLSNTreeWalker {
56  
57      /*
58       * The interface for calling back to the user with each LSN.
59       */
60      public interface TreeNodeProcessor {
61      void processLSN(long childLSN,
62                          LogEntryType childType,
63                          Node theNode,
64                          byte[] lnKey)
65          throws DatabaseException;
66  
67      /* Used when processing DW dbs where there are no LSNs. */
68      void processDupCount(long count);
69      }
70  
71      /*
72       * Optionally passed to the SortedLSNTreeWalker to be called when an
73       * exception occurs.
74       */
75      public interface ExceptionPredicate {
76      /* Return true if the exception can be ignored. */
77      boolean ignoreException(Exception   e);
78      }
79  
80      protected DatabaseImpl dbImpl;
81      private EnvironmentImpl envImpl;
82  
83      /* 
84       * Save the root LSN at construction time, because the root may be
85       * nulled out before walk() executes.
86       */
87      private long rootLsn; 
88  
89      /* Indicates whether db has allowDuplicates set. */
90      private boolean dups;
91  
92      /*
93       * Set removeINsFromINList to true if INs read from the INList should be
94       * removed.
95       */
96      private boolean removeINsFromINList;
97  
98      /*
99       * Whether to call DatabaseImpl.finishedINListHarvest().
100      */
101     private boolean setDbState;
102 
103     /*
104      * An array (and index) of LSNs that were accumulated in a previous pass
105      * over the tree.
106      */
107     private long[] currentLSNs;
108     private int currentLSNIdx = 0;
109 
110     /*
111      * A list of LSNs being accumulated.  Once they have been accumulated, they
112      * will be moved to currentLSNs, fetched, and returned to the user.
113      *
114      * Store this in two OffsetLists, one for the file number portion of the
115      * LSN and the other for the file offset portion since OffsetLists can only
116      * store ints, not longs.
117      */
118     private OffsetList accumulatedLSNFileNumbers;
119     private OffsetList accumulatedLSNFileOffsets;
120 
121     private TreeNodeProcessor callback;
122 
123     /*
124      * If true, then walker should also accumulate LNs and pass them in sorted
125      * order to the TreeNodeProcessor callback method.
126      */
127     protected boolean accumulateLNs = false;
128 
129     /*
130      * If true, then walker should process Dup Trees all the way to the bottom.
131      * If false, then walker only processes the root DIN and DupCountLN.
132      */
133     private boolean processDupTree = true;
134 
135     /*
136      * If true, then we still pass nodes that have null lsns (i.e. during
137      * DeferredWrite DB processing in Database.count().
138      */
139     private boolean passNullLSNNodes = false;
140 
141     /* 
142      * If non-null, save any exceptions encountered while traversing nodes into
143      * this savedException list, in order to walk as much of the tree as
144      * possible. The caller of the tree walker will handle the exceptions. 
145      */
146     private List   savedExceptions;
147     
148     private ExceptionPredicate excPredicate;
149 
150     /* Holder for returning LN key from fetchLSN. */
151     private DatabaseEntry lnKeyEntry = new DatabaseEntry();
152 
153     /*
154      * @param rootLsn is passed in addition to the dbImpl, because the
155      * root may be nulled out on the dbImpl before walk() is called.
156      */
157     public SortedLSNTreeWalker(DatabaseImpl dbImpl,
158                    boolean removeINsFromINList,
159                    boolean setDbState,
160                                long rootLsn,
161                    TreeNodeProcessor callback,
162                                List   savedExceptions,
163                    ExceptionPredicate excPredicate)
164     throws DatabaseException {
165 
166     /* This iterator is used on both deleted and undeleted databases. */
167     this.dbImpl = dbImpl;
168     this.envImpl = dbImpl.getDbEnvironment();
169     if (envImpl == null) {
170         throw new DatabaseException
171         ("environmentImpl is null for target db " +
172                  dbImpl.getDebugName());
173     }
174     this.dups = dbImpl.getSortedDuplicates();
175 
176     this.removeINsFromINList = removeINsFromINList;
177     this.setDbState = setDbState;
178         this.rootLsn = rootLsn;
179     this.callback = callback;
180         this.savedExceptions = savedExceptions;
181     this.excPredicate = excPredicate;
182     currentLSNs = new long[0];
183     currentLSNIdx = 0;
184     }
185 
186     void setProcessDupTree(boolean processDupTree) {
187     this.processDupTree = processDupTree;
188     }
189 
190     void setPassNullLSNNodes(boolean passNullLSNNodes) {
191     this.passNullLSNNodes = passNullLSNNodes;
192     }
193 
194     /*
195      * Return true if some INs were found on the INList for this db.
196      */
197     private boolean extractINsForDb(INList inList)
198     throws DatabaseException {
199 
200     boolean foundSome = false;
201 
202         /* Search the INList and put all qualifying INs into another list. */
203         Set   foundSet = new HashSet  ();
204         long memoryChange = 0;
205         MemoryBudget mb = envImpl.getMemoryBudget();
206     inList.latchMajor();
207     try {
208             /* consolidate the INList first. */
209             inList.latchMinorAndDumpAddedINs();
210 
211         Iterator   iter = inList.iterator();
212         while (iter.hasNext()) {
213         IN thisIN = (IN) iter.next();
214         if (thisIN.getDatabase() == dbImpl) {
215             foundSome = true;
216             if (removeINsFromINList) {
217             iter.remove();
218                         memoryChange += (thisIN.getAccumulatedDelta() -
219                                          thisIN.getInMemorySize());
220                         thisIN.setInListResident(false);
221             }
222                     foundSet.add(thisIN);
223         }
224         }
225         } catch (DatabaseException e) {
226             /* Update the memory budget with any changes. */
227             mb.updateTreeMemoryUsage(memoryChange);
228             throw e;
229     } finally {
230         inList.releaseMajorLatch();
231     }
232 
233         /* 
234          * Do processing outside of INList latch in order to reduce lockout
235          * of checkpointing and eviction. 
236          */
237         if (foundSome) {
238             Iterator   iter = foundSet.iterator();
239             while (iter.hasNext()) {
240                 IN thisIN = (IN) iter.next();
241                 accumulateLSNs(thisIN);
242             }
243         }
244 
245         /* 
246          * Update the memory in one fell swoop after releasing all references
247          * to INs in order to reduce contention on memory budget contention
248          * latch. Wait until all references to INs are released.
249          */
250         foundSet = null;
251         mb.updateTreeMemoryUsage(memoryChange);
252 
253     return foundSome;
254     }
255 
256     /**
257      * Find all non-resident nodes, and execute the callback.  The root IN's
258      * LSN is not returned to the callback.
259      */
260     public void walk()
261     throws DatabaseException {
262 
263     walkInternal();
264     }
265 
266     protected void walkInternal()
267     throws DatabaseException {
268 
269     INList inList = envImpl.getInMemoryINs();
270     IN root = null;
271     if (!extractINsForDb(inList)) {
272         if (rootLsn == DbLsn.NULL_LSN) {
273         return;
274         }
275 
276         root = getRootIN(rootLsn);
277         accumulateLSNs(root);
278         releaseRootIN(root);
279         }
280 
281         if (setDbState) {
282             dbImpl.finishedINListHarvest();
283         }
284 
285     while (true) {
286         maybeGetMoreINs();
287         if (currentLSNs != null &&
288         currentLSNIdx < currentLSNs.length) {
289                 fetchAndProcessLSN(currentLSNs[currentLSNIdx++]);
290         } else {
291         break;
292         }
293     }
294     }
295 
296     private void maybeGetMoreINs() {
297 
298     if ((currentLSNs != null &&
299          currentLSNIdx >= currentLSNs.length)) {
300 
301         if (accumulatedLSNFileNumbers == null ||
302         accumulatedLSNFileNumbers.size() == 0) {
303 
304         /* Nothing left to process. Mark completion of second phase. */
305         currentLSNs = null;
306         currentLSNIdx = Integer.MAX_VALUE;
307         return;
308         }
309 
310         long[] tempFileNumbers = accumulatedLSNFileNumbers.toArray();
311         long[] tempFileOffsets = accumulatedLSNFileOffsets.toArray();
312         int nLSNs = tempFileNumbers.length;
313         currentLSNIdx = 0;
314         currentLSNs = new long[nLSNs];
315         for (int i = 0; i < nLSNs; i++) {
316         currentLSNs[i] =
317             DbLsn.makeLsn(tempFileNumbers[i], tempFileOffsets[i]);
318         }
319 
320         Arrays.sort(currentLSNs);
321         accumulatedLSNFileNumbers = null;
322         accumulatedLSNFileOffsets = null;
323     }
324     }
325 
326     private void accumulateLSNs(IN in)
327     throws DatabaseException {
328 
329     boolean accumulate = true;
330 
331         /* 
332          * If this is the bottom of the tree and we're not accumulating LNs,
333          * then there's no need to accumulate any more LSNs, but we still need
334          * to callback with each of them.
335          */
336     boolean childIsLN = (!dups && (in instanceof BIN)) ||
337         (in instanceof DBIN);
338     if (childIsLN) {
339         if (!accumulateLNs) {
340 
341         /*
342          * No need to accumulate the LSNs of a non-dup BIN or a DBIN.
343          */
344         accumulate = false;
345         }
346     }
347 
348     boolean isDINRoot = (in instanceof DIN) && in.isRoot();
349 
350     /*
351      * Process all children, but only accumulate LSNs for children that are
352      * not in memory.
353      */
354     if (processDupTree || !in.containsDuplicates()) {
355         for (int i = 0; i < in.getNEntries(); i++) {
356 
357         if (in.isEntryPendingDeleted(i) ||
358             in.isEntryKnownDeleted(i)) {
359             continue;
360         }
361 
362         long lsn = in.getLsn(i);
363         Node node = in.getTarget(i);
364         if (accumulate && (node == null)) {
365             if (accumulatedLSNFileNumbers == null) {
366             accumulatedLSNFileNumbers = new OffsetList();
367             accumulatedLSNFileOffsets = new OffsetList();
368             }
369 
370             accumulatedLSNFileNumbers.add(DbLsn.getFileNumber(lsn),
371                           false);
372             accumulatedLSNFileOffsets.add(DbLsn.getFileOffset(lsn),
373                           false);
374 
375             /*
376              * If we're maintaining a map from LSN to owning IN/index,
377              * then update the map here.
378              */
379             addToLsnINMap(new Long  (lsn), in, i);
380             /* callback.processLSN is called when we fetch this LSN. */
381         } else if (lsn != DbLsn.NULL_LSN ||
382                passNullLSNNodes){
383 
384             /* 
385              * If the child is resident, use that log type, else we can
386              * assume it's a LN.
387              */
388                     byte[] lnKey = (node == null || node instanceof LN) ?
389                         in.getKey(i) : null;
390             callback.processLSN(lsn,
391                     (node == null) ? LogEntryType.LOG_LN :
392                     node.getLogType(),
393                     node,
394                                         lnKey);
395         }
396         }
397     }
398 
399         /* Handle the DupCountLN for a DIN root. */
400         if (isDINRoot) {
401         DIN din = (DIN) in;
402         ChildReference dupCountLNRef = din.getDupCountLNRef();
403         long lsn = dupCountLNRef.getLsn();
404         if (lsn == DbLsn.NULL_LSN) {
405         DupCountLN dcl = (DupCountLN) din.getDupCountLN();
406         callback.processDupCount(dcl.getDupCount());
407         } else {
408         Node node = fetchLSN(lsn, lnKeyEntry);
409         callback.processLSN
410                     (lsn, LogEntryType.LOG_DUPCOUNTLN, node,
411                      dupCountLNRef.getKey());
412         }
413         }
414     }
415 
416     /*
417      * Fetch the node at 'lsn' and callback to let the invoker process it.  If
418      * it is an IN, accumulate LSNs for it.
419      */
420     private void fetchAndProcessLSN(long lsn)
421     throws DatabaseException {
422 
423         try {
424             lnKeyEntry.setData(null);
425             Node node = fetchLSN(lsn, lnKeyEntry);
426             if (node != null) {
427                 callback.processLSN
428                     (lsn, node.getLogType(), node, lnKeyEntry.getData());
429                 
430                 if (node instanceof IN) {
431                     accumulateLSNs((IN) node);
432                 }
433             }
434         } catch (DatabaseException e) {
435         if (excPredicate == null ||
436         !excPredicate.ignoreException(e)) {
437         if (savedExceptions != null) {
438 
439             /* 
440              * This LSN fetch hit a failure. Do as much of the rest of
441              * the tree as possible.
442              */
443             savedExceptions.add(e);
444         } else {
445             throw e;
446         }
447         }
448     }
449     }
450 
451     /**
452      * The default behavior fetches the rootIN from the log, but classes
453      * extending this may fetch the root from the tree.
454      */
455     protected IN getRootIN(long rootLsn)
456     throws DatabaseException {
457 
458     return (IN) envImpl.getLogManager().get(rootLsn);
459     }
460 
461     protected void releaseRootIN(IN ignore)
462     throws DatabaseException {
463 
464     /* 
465      * There's no root IN latch in a vanilla Sorted LSN Tree Walk because
466      * we just fetched the root from the log.
467      */
468     }
469 
470     protected void addToLsnINMap(Long   lsn, IN in, int index) {
471     }
472 
473     protected Node fetchLSN(long lsn, DatabaseEntry lnKeyEntry)
474     throws DatabaseException {
475 
476         LogEntry entry = envImpl.getLogManager().getLogEntry(lsn);
477         if (entry instanceof LNLogEntry) {
478             lnKeyEntry.setData(((LNLogEntry) entry).getKey());
479         }
480         return (Node) entry.getMainItem();
481     }
482 
483     public List   getSavedExceptions() {
484         return savedExceptions;
485     }
486 }
487
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags