Java > Open Source Codes > com > sleepycat > je > tree > BIN


1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 2002,2006 Oracle. All rights reserved.
5  *
6  * $Id: BIN.java,v 1.187 2006/11/03 03:07:55 mark Exp $
7  */
8
9 package com.sleepycat.je.tree;
10
11 import java.util.Comparator ;
12 import java.util.Iterator ;
13 import java.util.Set ;
14
15 import com.sleepycat.je.DatabaseException;
16 import com.sleepycat.je.cleaner.Cleaner;
17 import com.sleepycat.je.dbi.CursorImpl;
18 import com.sleepycat.je.dbi.DatabaseId;
19 import com.sleepycat.je.dbi.DatabaseImpl;
20 import com.sleepycat.je.dbi.DbConfigManager;
21 import com.sleepycat.je.dbi.EnvironmentImpl;
22 import com.sleepycat.je.dbi.MemoryBudget;
23 import com.sleepycat.je.log.LogEntryType;
24 import com.sleepycat.je.log.LogManager;
25 import com.sleepycat.je.log.LoggableObject;
26 import com.sleepycat.je.txn.BasicLocker;
27 import com.sleepycat.je.txn.LockGrantType;
28 import com.sleepycat.je.txn.LockResult;
29 import com.sleepycat.je.txn.LockType;
30 import com.sleepycat.je.utilint.DbLsn;
31 import com.sleepycat.je.utilint.TinyHashSet;
32
33 /**
34  * A BIN represents a Bottom Internal Node in the JE tree.
35  */
36 public class BIN extends IN implements LoggableObject {
37
38     private static final String BEGIN_TAG = "<bin>";
39     private static final String END_TAG = "</bin>";
40
41     /*
42      * The set of cursors that are currently referring to this BIN.
43      */
44     private TinyHashSet cursorSet;
45
46     /*
47      * Support for logging BIN deltas. (Partial BIN logging)
48      */
49
50     /* Location of last delta, for cleaning. */
51     private long lastDeltaVersion = DbLsn.NULL_LSN;
52     private int numDeltasSinceLastFull; // num deltas logged
53 private boolean prohibitNextDelta; // disallow delta on next log
54
55     public BIN() {
56         cursorSet = new TinyHashSet();
57         numDeltasSinceLastFull = 0;
58         prohibitNextDelta = false;
59     }
60
61     public BIN(DatabaseImpl db,
62            byte[] identifierKey,
63            int maxEntriesPerNode,
64            int level) {
65         super(db, identifierKey, maxEntriesPerNode, level);
66
67         cursorSet = new TinyHashSet();
68         numDeltasSinceLastFull = 0;
69         prohibitNextDelta = false;
70     }
71
72     /**
73      * Create a holder object that encapsulates information about this
74      * BIN for the INCompressor.
75      */
76     public BINReference createReference() {
77       return new BINReference(getNodeId(), getDatabase().getId(),
78                                 getIdentifierKey());
79     }
80
81     /**
82      * Create a new BIN. Need this because we can't call newInstance()
83      * without getting a 0 for nodeid.
84      */
85     protected IN createNewInstance(byte[] identifierKey,
86                    int maxEntries,
87                    int level) {
88         return new BIN(getDatabase(), identifierKey, maxEntries, level);
89     }
90
91     /*
92      * Return whether the shared latch for this kind of node should be of the
93      * "always exclusive" variety. Presently, only IN's are actually latched
94      * shared. BINs, DINs, and DBINs are all latched exclusive only.
95      */
96     boolean isAlwaysLatchedExclusively() {
97     return true;
98     }
99
100     /**
101      * Get the key (dupe or identifier) in child that is used to locate
102      * it in 'this' node. For BIN's, the child node has to be a DIN
103      * so we use the Dup Key to cross the main-tree/dupe-tree boundary.
104      */
105     public byte[] getChildKey(IN child)
106         throws DatabaseException {
107
108         return child.getDupKey();
109     }
110     
111     /**
112      * @return the log entry type to use for bin delta log entries.
113      */
114     LogEntryType getBINDeltaType() {
115         return LogEntryType.LOG_BIN_DELTA;
116     }
117
118     /**
119      * @return location of last logged delta version. If never set,
120      * return null.
121      */
122     public long getLastDeltaVersion() {
123         return lastDeltaVersion;
124     }
125
126     /**
127      * If cleaned or compressed, must log full version.
128      * @Override
129      */
130     public void setProhibitNextDelta() {
131         prohibitNextDelta = true;
132     }
133
134     /*
135      * If this search can go further, return the child. If it can't, and you
136      * are a possible new parent to this child, return this IN. If the
137      * search can't go further and this IN can't be a parent to this child,
138      * return null.
139      */
140     protected void descendOnParentSearch(SearchResult result,
141                                          boolean targetContainsDuplicates,
142                                          boolean targetIsRoot,
143                                          long targetNodeId,
144                                          Node child,
145                                          boolean requireExactMatch)
146         throws DatabaseException {
147
148         if (child.canBeAncestor(targetContainsDuplicates)) {
149             if (targetContainsDuplicates && targetIsRoot) {
150
151                 /*
152                  * Don't go further -- the target is a root of a dup tree, so
153                  * this BIN will have to be the parent.
154                  */
155                 long childNid = child.getNodeId();
156                 ((IN) child).releaseLatch();
157
158                 result.keepSearching = false; // stop searching
159
160                 if (childNid == targetNodeId) { // set if exact find
161 result.exactParentFound = true;
162                 } else {
163                     result.exactParentFound = false;
164                 }
165
166                 /*
167                  * Return a reference to this node unless we need an exact
168                  * match and this isn't exact.
169                  */
170                 if (requireExactMatch && ! result.exactParentFound) {
171                     result.parent = null;
172                     releaseLatch();
173                 } else {
174                     result.parent = this;
175                 }
176
177             } else {
178                 /*
179                  * Go further down into the dup tree.
180                  */
181                 releaseLatch();
182                 result.parent = (IN) child;
183             }
184         } else {
185             /*
186              * Our search ends, we didn't find it. If we need an exact match,
187              * give up, if we only need a potential match, keep this node
188              * latched and return it.
189              */
190             result.exactParentFound = false;
191             result.keepSearching = false;
192             if (!requireExactMatch && targetContainsDuplicates) {
193                 result.parent = this;
194             } else {
195                 releaseLatch();
196                 result.parent = null;
197             }
198         }
199     }
200
201     /*
202      * A BIN can be the ancestor of an internal node of the duplicate tree. It
203      * can't be the parent of an IN or another BIN.
204      */
205     protected boolean canBeAncestor(boolean targetContainsDuplicates) {
206         /* True if the target is a DIN or DBIN */
207         return targetContainsDuplicates;
208     }
209
210     /**
211      * @Override
212      */
213     boolean isEvictionProhibited() {
214         return (nCursors() > 0);
215     }
216
217     /**
218      * @Override
219      */
220     boolean hasNonLNChildren() {
221
222         for (int i = 0; i < getNEntries(); i++) {
223             Node node = getTarget(i);
224             if (node != null) {
225                 if (!(node instanceof LN)) {
226                     return true;
227                 }
228             }
229         }
230
231         return false;
232     }
233
234     /**
235      * @Override
236      */
237     int getChildEvictionType() {
238
239         Cleaner cleaner = getDatabase().getDbEnvironment().getCleaner();
240
241         for (int i = 0; i < getNEntries(); i++) {
242             Node node = getTarget(i);
243             if (node != null) {
244                 if (node instanceof LN) {
245                     if (cleaner.isEvictable(this, i)) {
246                         return MAY_EVICT_LNS;
247                     }
248                 } else {
249                     return MAY_NOT_EVICT;
250                 }
251             }
252         }
253         return MAY_EVICT_NODE;
254     }
255
256     /**
257      * Indicates whether entry 0's key is "special" in that it always
258      * compares less than any other key. BIN's don't have the special
259      * key, but IN's do.
260      */
261     boolean entryZeroKeyComparesLow() {
262         return false;
263     }
264
265     /**
266      * Mark this entry as deleted, using the delete flag. Only BINS
267      * may do this.
268      *
269      * @param index indicates target entry
270      */
271     public void setKnownDeleted(int index) {
272
273         /*
274          * The target is cleared to save memory, since a known deleted entry
275          * will never be fetched. The migrate flag is also cleared since
276          * migration is never needed for known deleted entries either.
277          */
278         super.setKnownDeleted(index);
279         updateMemorySize(getTarget(index), null);
280         setMigrate(index, false);
281         super.setTarget(index, null);
282         setDirty(true);
283     }
284
285     /**
286      * Mark this entry as deleted, using the delete flag. Only BINS
287      * may do this. Don't null the target field.
288      *
289      * This is used so that an LN can still be locked by the compressor
290      * even if the entry is knownDeleted.
291      * See BIN.compress.
292      *
293      * @param index indicates target entry
294      */
295     public void setKnownDeletedLeaveTarget(int index) {
296
297         /*
298          * The migrate flag is cleared since migration is never needed for
299          * known deleted entries.
300          */
301         setMigrate(index, false);
302         super.setKnownDeleted(index);
303         setDirty(true);
304     }
305
306     /**
307      * Clear the known deleted flag. Only BINS may do this.
308      * @param index indicates target entry
309      */
310     public void clearKnownDeleted(int index) {
311         super.clearKnownDeleted(index);
312         setDirty(true);
313     }
314
315     /* Called once at environment startup by MemoryBudget */
316     public static long computeOverhead(DbConfigManager configManager)
317         throws DatabaseException {
318
319         /*
320      * Overhead consists of all the fields in this class plus the
321      * entry arrays in the IN class.
322          */
323         return MemoryBudget.BIN_FIXED_OVERHEAD +
324         IN.computeArraysOverhead(configManager);
325     }
326
327     protected long getMemoryOverhead(MemoryBudget mb) {
328         return mb.getBINOverhead();
329     }
330
331     /*
332      * Cursors
333      */
334
335     /* public for the test suite. */
336     public Set getCursorSet() {
337         return cursorSet.copy();
338     }
339
340     /**
341      * Register a cursor with this bin. Caller has this bin already latched.
342      * @param cursor Cursor to register.
343      */
344     public void addCursor(CursorImpl cursor) {
345         assert isLatchOwnerForWrite();
346         cursorSet.add(cursor);
347     }
348
349     /**
350      * Unregister a cursor with this bin. Caller has this bin already
351      * latched.
352      *
353      * @param cursor Cursor to unregister.
354      */
355     public void removeCursor(CursorImpl cursor) {
356         assert isLatchOwnerForWrite();
357         cursorSet.remove(cursor);
358     }
359
360     /**
361      * @return the number of cursors currently referring to this BIN.
362      */
363     public int nCursors() {
364         return cursorSet.size();
365     }
366
367     /**
368      * The following four methods access the correct fields in a
369      * cursor depending on whether "this" is a BIN or DBIN. For
370      * BIN's, the CursorImpl.index and CursorImpl.bin fields should be
371      * used. For DBIN's, the CursorImpl.dupIndex and CursorImpl.dupBin
372      * fields should be used.
373      */
374     BIN getCursorBIN(CursorImpl cursor) {
375         return cursor.getBIN();
376     }
377
378     BIN getCursorBINToBeRemoved(CursorImpl cursor) {
379         return cursor.getBINToBeRemoved();
380     }
381
382     int getCursorIndex(CursorImpl cursor) {
383         return cursor.getIndex();
384     }
385
386     void setCursorBIN(CursorImpl cursor, BIN bin) {
387         cursor.setBIN(bin);
388     }
389
390     void setCursorIndex(CursorImpl cursor, int index) {
391         cursor.setIndex(index);
392     }
393
394     /**
395      * Called when we know we are about to split on behalf of a key
396      * that is the minimum (leftSide) or maximum (!leftSide) of this
397      * node. This is achieved by just forcing the split to occur
398      * either one element in from the left or the right
399      * (i.e. splitIndex is 1 or nEntries - 1).
400      */
401     void splitSpecial(IN parent, int parentIndex, int maxEntriesPerNode,
402               byte[] key, boolean leftSide)
403     throws DatabaseException {
404
405     int index = findEntry(key, true, false);
406     int nEntries = getNEntries();
407     boolean exact = (index & IN.EXACT_MATCH) != 0;
408     index &= ~IN.EXACT_MATCH;
409     if (leftSide &&
410         index < 0) {
411         splitInternal(parent, parentIndex, maxEntriesPerNode, 1);
412     } else if (!leftSide &&
413            !exact &&
414            index == (nEntries - 1)) {
415         splitInternal(parent, parentIndex, maxEntriesPerNode,
416               nEntries - 1);
417     } else {
418         split(parent, parentIndex, maxEntriesPerNode);
419     }
420     }
421
422     /**
423      * Adjust any cursors that are referring to this BIN. This method
424      * is called during a split operation. "this" is the BIN being split.
425      * newSibling is the new BIN into which the entries from "this"
426      * between newSiblingLow and newSiblingHigh have been copied.
427      *
428      * @param newSibling - the newSibling into which "this" has been split.
429      * @param newSiblingLow, newSiblingHigh - the low and high entry of
430      * "this" that were moved into newSibling.
431      */
432     void adjustCursors(IN newSibling,
433                        int newSiblingLow,
434                        int newSiblingHigh) {
435         assert newSibling.isLatchOwnerForWrite();
436         assert this.isLatchOwnerForWrite();
437         int adjustmentDelta = (newSiblingHigh - newSiblingLow);
438         Iterator iter = cursorSet.iterator();
439         while (iter.hasNext()) {
440             CursorImpl cursor = (CursorImpl) iter.next();
441             if (getCursorBINToBeRemoved(cursor) == this) {
442
443                 /*
444                  * This BIN will be removed from the cursor by CursorImpl
445                  * following advance to next BIN; ignore it.
446                  */
447                 continue;
448             }
449             int cIdx = getCursorIndex(cursor);
450             BIN cBin = getCursorBIN(cursor);
451             assert cBin == this :
452                 "nodeId=" + getNodeId() +
453                 " cursor=" + cursor.dumpToString(true);
454             assert newSibling instanceof BIN;
455
456             /*
457              * There are four cases to consider for cursor adjustments,
458              * depending on (1) how the existing node gets split, and
459              * (2) where the cursor points to currently.
460              * In cases 1 and 2, the id key of the node being split is
461              * to the right of the splitindex so the new sibling gets
462              * the node entries to the left of that index. This is
463              * indicated by "new sibling" to the left of the vertical
464              * split line below. The right side of the node contains
465              * entries that will remain in the existing node (although
466              * they've been shifted to the left). The vertical bar (^)
467              * indicates where the cursor currently points.
468              *
469              * case 1:
470              *
471              * We need to set the cursor's "bin" reference to point
472              * at the new sibling, but we don't need to adjust its
473              * index since that continues to be correct post-split.
474              *
475              * +=======================================+
476              * | new sibling | existing node |
477              * +=======================================+
478              * cursor ^
479              *
480              * case 2:
481              *
482              * We only need to adjust the cursor's index since it
483              * continues to point to the current BIN post-split.
484              *
485              * +=======================================+
486              * | new sibling | existing node |
487              * +=======================================+
488              * cursor ^
489              *
490              * case 3:
491              *
492              * Do nothing. The cursor continues to point at the
493              * correct BIN and index.
494              *
495              * +=======================================+
496              * | existing Node | new sibling |
497              * +=======================================+
498              * cursor ^
499              *
500              * case 4:
501              *
502              * Adjust the "bin" pointer to point at the new sibling BIN
503              * and also adjust the index.
504              *
505              * +=======================================+
506              * | existing Node | new sibling |
507              * +=======================================+
508              * cursor ^
509              */
510             BIN ns = (BIN) newSibling;
511             if (newSiblingLow == 0) {
512                 if (cIdx < newSiblingHigh) {
513                     /* case 1 */
514                     setCursorBIN(cursor, ns);
515                     iter.remove();
516                     ns.addCursor(cursor);
517                 } else {
518                     /* case 2 */
519                     setCursorIndex(cursor, cIdx - adjustmentDelta);
520                 }
521             } else {
522                 if (cIdx >= newSiblingLow) {
523                     /* case 4 */
524                     setCursorIndex(cursor, cIdx - newSiblingLow);
525                     setCursorBIN(cursor, ns);
526                     iter.remove();
527                     ns.addCursor(cursor);
528                 }
529             }
530         }
531     }
532
533     /**
534      * For each cursor in this BIN's cursor set, ensure that the
535      * cursor is actually referring to this BIN.
536      */
537     public void verifyCursors() {
538         if (cursorSet != null) {
539             Iterator iter = cursorSet.iterator();
540             while (iter.hasNext()) {
541                 CursorImpl cursor = (CursorImpl) iter.next();
542                 if (getCursorBINToBeRemoved(cursor) != this) {
543                     BIN cBin = getCursorBIN(cursor);
544                     assert cBin == this;
545                 }
546             }
547         }
548     }
549
550     /**
551      * Adjust cursors referring to this BIN following an insert.
552      *
553      * @param insertIndex - The index of the new entry.
554      */
555     void adjustCursorsForInsert(int insertIndex) {
556         assert this.isLatchOwnerForWrite();
557         /* cursorSet may be null if this is being created through
558            createFromLog() */
559         if (cursorSet != null) {
560             Iterator iter = cursorSet.iterator();
561             while (iter.hasNext()) {
562                 CursorImpl cursor = (CursorImpl) iter.next();
563                 if (getCursorBINToBeRemoved(cursor) != this) {
564                     int cIdx = getCursorIndex(cursor);
565                     if (insertIndex <= cIdx) {
566                         setCursorIndex(cursor, cIdx + 1);
567                     }
568                 }
569             }
570         }
571     }
572
573     /**
574      * Adjust cursors referring to the given binIndex in this BIN following a
575      * mutation of the entry from an LN to a DIN. The entry was moved from a
576      * BIN to a newly created DBIN so each cursor must be added to the new
577      * DBIN.
578      *
579      * @param binIndex - The index of the DIN (previously LN) entry in the BIN.
580      *
581      * @param dupBin - The DBIN into which the LN entry was moved.
582      *
583      * @param dupBinIndex - The index of the moved LN entry in the DBIN.
584      *
585      * @param excludeCursor - The cursor being used for insertion and that
586      * should not be updated.
587      */
588     void adjustCursorsForMutation(int binIndex,
589                   DBIN dupBin,
590                   int dupBinIndex,
591                                   CursorImpl excludeCursor) {
592         assert this.isLatchOwnerForWrite();
593         /* cursorSet may be null if this is being created through
594            createFromLog() */
595         if (cursorSet != null) {
596             Iterator iter = cursorSet.iterator();
597             while (iter.hasNext()) {
598                 CursorImpl cursor = (CursorImpl) iter.next();
599                 if (getCursorBINToBeRemoved(cursor) != this &&
600                     cursor != excludeCursor &&
601                     cursor.getIndex() == binIndex) {
602                     assert cursor.getDupBIN() == null;
603                     cursor.addCursor(dupBin);
604                     cursor.updateDBin(dupBin, dupBinIndex);
605                 }
606             }
607         }
608     }
609
610     /**
611      * Compress this BIN by removing any entries that are deleted. Deleted
612      * entries are those that have LN's marked deleted or if the knownDeleted
613      * flag is set. Caller is responsible for latching and unlatching
614      * this node.
615      *
616      * @param binRef is used to determine the set of keys to be checked for
617      * deletedness, or is null to check all keys.
618      * @param canFetch if false, don't fetch any non-resident children. We
619      * don't want some callers of compress, such as the evictor, to fault
620      * in other nodes.
621      *
622      * @return true if we had to requeue the entry because we were unable to
623      * get locks, false if all entries were processed and therefore any
624      * remaining deleted keys in the BINReference must now be in some other BIN
625      * because of a split.
626      */
627     public boolean compress(BINReference binRef, boolean canFetch)
628         throws DatabaseException {
629
630         boolean ret = false;
631         boolean setNewIdKey = false;
632         boolean anyLocksDenied = false;
633     DatabaseImpl db = getDatabase();
634         BasicLocker lockingTxn = new BasicLocker(db.getDbEnvironment());
635
636         try {
637             for (int i = 0; i < getNEntries(); i++) {
638
639         /*
640          * We have to be able to lock the LN before we can compress the
641          * entry. If we can't, then, skip over it.
642          *
643          * We must lock the LN even if isKnownDeleted is true, because
644          * locks protect the aborts. (Aborts may execute multiple
645          * operations, where each operation latches and unlatches. It's
646          * the LN lock that protects the integrity of the whole
647          * multi-step process.)
648                  *
649                  * For example, during abort, there may be cases where we have
650          * deleted and then added an LN during the same txn. This
651          * means that to undo/abort it, we first delete the LN (leaving
652          * knownDeleted set), and then add it back into the tree. We
653          * want to make sure the entry is in the BIN when we do the
654          * insert back in.
655          */
656                 boolean deleteEntry = false;
657
658                 if (binRef == null ||
659             isEntryPendingDeleted(i) ||
660                     isEntryKnownDeleted(i) ||
661                     binRef.hasDeletedKey(new Key(getKey(i)))) {
662
663                     Node n = null;
664                     if (canFetch) {
665                         n = fetchTarget(i);
666                     } else {
667                         n = getTarget(i);
668                         if (n == null) {
669                             /* Punt, we don't know the state of this child. */
670                             continue;
671                         }
672                     }
673
674                     if (n == null) {
675                         /* Cleaner deleted the log file. Compress this LN. */
676                         deleteEntry = true;
677                     } else if (isEntryKnownDeleted(i)) {
678                         LockResult lockRet = lockingTxn.nonBlockingLock
679                             (n.getNodeId(), LockType.READ, db);
680                         if (lockRet.getLockGrant() == LockGrantType.DENIED) {
681                             anyLocksDenied = true;
682                             continue;
683                         }
684
685                         deleteEntry = true;
686                     } else {
687                         if (!n.containsDuplicates()) {
688                             LN ln = (LN) n;
689                             LockResult lockRet = lockingTxn.nonBlockingLock
690                                 (ln.getNodeId(), LockType.READ, db);
691                             if (lockRet.getLockGrant() ==
692                                 LockGrantType.DENIED) {
693                                 anyLocksDenied = true;
694                                 continue;
695                             }
696
697                             if (ln.isDeleted()) {
698                                 deleteEntry = true;
699                             }
700                         }
701                     }
702
703                     /* Remove key from BINReference in case we requeue it. */
704                     if (binRef != null) {
705                         binRef.removeDeletedKey(new Key(getKey(i)));
706                     }
707                 }
708
709                 /* At this point, we know we can delete. */
710                 if (deleteEntry) {
711                     boolean entryIsIdentifierKey = Key.compareKeys
712                         (getKey(i), getIdentifierKey(),
713                          getKeyComparator()) == 0;
714                     if (entryIsIdentifierKey) {
715
716                         /*
717                          * We're about to remove the entry with the idKey so
718                          * the node will need a new idkey.
719                          */
720                         setNewIdKey = true;
721                     }
722
723                     boolean deleteSuccess = deleteEntry(i, true);
724                     assert deleteSuccess;
725
726                     /*
727                      * Since we're deleting the current entry, bump the current
728                      * index back down one.
729                      */
730                     i--;
731                 }
732             }
733         } finally {
734             if (lockingTxn != null) {
735                 lockingTxn.operationEnd();
736             }
737         }
738
739         if (anyLocksDenied && binRef != null) {
740             db.getDbEnvironment().addToCompressorQueue(binRef, false);
741             ret = true;
742         }
743
744         if (getNEntries() != 0 && setNewIdKey) {
745             setIdentifierKey(getKey(0));
746         }
747
748         /* This BIN is empty and expendable. */
749         if (getNEntries() == 0) {
750             setGeneration(0);
751         }
752
753         return ret;
754     }
755
756     public boolean isCompressible() {
757         return true;
758     }
759
760     /**
761      * Reduce memory consumption by evicting all LN targets. Note that
762      * this may cause LNs to be logged, which would require marking this
763      * BIN dirty.
764      *
765      * The BIN should be latched by the caller.
766      * @return number of evicted bytes. Note that a 0 return does not
767      * necessarily mean that the BIN had no evictable LNs. It's possible that
768      * resident, dirty LNs were not lockable.
769      */
770     public long evictLNs()
771         throws DatabaseException {
772
773         assert isLatchOwnerForWrite() :
774             "BIN must be latched before evicting LNs";
775
776         Cleaner cleaner = getDatabase().getDbEnvironment().getCleaner();
777
778         /*
779          * We can't evict an LN which is pointed to by a cursor, in case that
780          * cursor has a reference to the LN object. We'll take the cheap
781          * choice and avoid evicting any LNs if there are cursors on this
782          * BIN. We could do a more expensive, precise check to see entries
783          * have which cursors. (We'd have to be careful to use the right
784          * field, index vs dupIndex). This is something we might move to
785          * later.
786          */
787         long removed = 0;
788         if (nCursors() == 0) {
789             for (int i = 0; i < getNEntries(); i++) {
790                 removed += evictInternal(i, cleaner);
791             }
792             updateMemorySize(removed, 0);
793         }
794         return removed;
795     }
796
797     /**
798      * Evict a single LN if allowed and adjust the memory budget.
799      *
800      * @return number of evicted bytes. Note that a 0 return does not
801      * necessarily mean there was no eviction because the targetLN was not
802      * resident. It's possible that resident, dirty LNs were not lockable.
803      */
804     public void evictLN(int index)
805         throws DatabaseException {
806
807         Cleaner cleaner = getDatabase().getDbEnvironment().getCleaner();
808         long removed = evictInternal(index, cleaner);
809         updateMemorySize(removed, 0);
810     }
811
812     /**
813      * Evict a single LN if allowed. The amount of memory freed is returned
814      * and must be subtracted from the memory budget by the caller.
815      */
816     private long evictInternal(int index, Cleaner cleaner)
817         throws DatabaseException {
818
819         Node n = getTarget(index);
820
821         /* Don't strip LNs that the cleaner will be migrating. */
822         if (n instanceof LN &&
823         cleaner.isEvictable(this, index)) {
824
825             /* Log target if necessary. */
826             LN ln = (LN) n;
827             if (ln.isDirty()) {
828             DatabaseImpl dbImpl = getDatabase();
829
830                 /*
831                  * Only deferred write databases should have dirty LNs. This
832                  * is an overly stringent assertion, because a db can flop
833                  * between dw and durable mode, but is used currently for our
834                  * regression testing.
835                  */
836                 assert dbImpl.isDeferredWrite();
837
838                 /*
839                  * Note that old offset will not be marked obsolete. Ideally
840                  * we'd use getLsn(index). For DW we don't know the size of
841                  * the last logged LN, so we pass zero for the obsolete size.
842                  */
843                 EnvironmentImpl envImpl = dbImpl.getDbEnvironment();
844                 long oldOffset = envImpl.getDeferredWriteTemp() ?
845                     getLsn(index) : DbLsn.NULL_LSN;
846                 long lsn = ln.log(envImpl,
847                                   dbImpl.getId(),
848                                   getKey(index),
849                                   oldOffset, // offset tracking
850 0, // obsolete size
851 null, // locker
852 false); // Is provisional.
853 updateEntry(index, lsn);
854             }
855
856             /* Clear target. */
857             setTarget(index, null);
858
859             return n.getMemorySizeIncludedByParent();
860         } else {
861             return 0;
862         }
863     }
864
865     /* For debugging. Overrides method in IN. */
866     boolean validateSubtreeBeforeDelete(int index)
867         throws DatabaseException {
868
869         return true;
870     }
871
872     /**
873      * Check if this node fits the qualifications for being part of a deletable
874      * subtree. It can only have one IN child and no LN children.
875      *
876      * We assume that this is only called under an assert.
877      */
878     boolean isValidForDelete()
879         throws DatabaseException {
880
881         /*
882      * Can only have one valid child, and that child should be deletable.
883      */
884         int validIndex = 0;
885         int numValidEntries = 0;
886     boolean needToLatch = !isLatchOwnerForWrite();
887     try {
888         if (needToLatch) {
889         latch();
890         }
891         for (int i = 0; i < getNEntries(); i++) {
892         if (!isEntryKnownDeleted(i)) {
893             numValidEntries++;
894             validIndex = i;
895         }
896         }
897
898         if (numValidEntries > 1) { // more than 1 entry
899 return false;
900         } else {
901         if (nCursors() > 0) { // cursors on BIN, not eligable
902 return false;
903         }
904         if (numValidEntries == 1) { // need to check child (DIN or LN)
905 Node child = fetchTarget(validIndex);
906             if (child == null) {
907             return false;
908             }
909             child.latchShared();
910             boolean ret = child.isValidForDelete();
911             child.releaseLatch();
912             return ret;
913         } else {
914             return true; // 0 entries.
915 }
916         }
917     } finally {
918         if (needToLatch &&
919         isLatchOwnerForWrite()) {
920         releaseLatch();
921         }
922     }
923     }
924
925     /*
926      * DbStat support.
927      */
928     void accumulateStats(TreeWalkerStatsAccumulator acc) {
929     acc.processBIN(this, new Long (getNodeId()), getLevel());
930     }
931
932     /**
933      * Return the relevant user defined comparison function for this
934      * type of node. For IN's and BIN's, this is the BTree Comparison
935      * function. Overriden by DBIN.
936      */
937     public Comparator getKeyComparator() {
938         return getDatabase().getBtreeComparator();
939     }
940
941     public String beginTag() {
942         return BEGIN_TAG;
943     }
944
945     public String endTag() {
946         return END_TAG;
947     }
948
949     /*
950      * Logging support
951      */
952
953     /**
954      * @see IN.logDirtyChildren();
955      */
956     public void logDirtyChildren()
957         throws DatabaseException {
958
959         /* Look for targets that are dirty. */
960         EnvironmentImpl envImpl = getDatabase().getDbEnvironment();
961         for (int i = 0; i < getNEntries(); i++) {
962             Node node = getTarget(i);
963             if (node != null) {
964
965                 if (node instanceof LN) {
966                     LN ln = (LN) node;
967
968                     /* No need to lock, this is non-txnal. */
969                     if (ln.isDirty()) {
970
971                         /*
972                          * Note that old offset will not be marked obsolete.
973                          * Ideally we'd use getLsn(i). For DW we don't know
974                          * the size of the last logged LN, so we pass zero for
975                          * the obsolete size.
976                          */
977                         long oldOffset = envImpl.getDeferredWriteTemp() ?
978                             getLsn(i) : DbLsn.NULL_LSN;
979                         long childLsn = ln.log(envImpl,
980                                                getDatabase().getId(),
981                                                getKey(i),
982                                                oldOffset, // obsolete tracking
983 0, // obsolete size
984 null, // locker
985 true); // backgroundIO
986 updateEntry(i, childLsn);
987                     }
988
989                 } else {
990                     DIN din = (DIN) node;
991                     din.latch(false);
992                     try {
993                         if (din.getDirty()) {
994                             din.logDirtyChildren();
995                             long childLsn =
996                                 din.log(envImpl.getLogManager(),
997                                         false, // allow deltas
998 true, // is provisional
999 false, // proactive migration
1000 true, // backgroundIO
1001 this); // provisional parent
1002 updateEntry(i, childLsn);
1003                        }
1004                    } finally {
1005                        din.releaseLatch();
1006                    }
1007                }
1008            }
1009        }
1010    }
1011
1012    /**
1013     * @see LoggableObject#getLogType
1014     */
1015    public LogEntryType getLogType() {
1016        return LogEntryType.LOG_BIN;
1017    }
1018
1019    public String shortClassName() {
1020        return "BIN";
1021    }
1022
1023    /**
1024     * Decide how to log this node. BINs may be logged provisionally. If
1025     * logging a delta, return an null for the LSN.
1026     */
1027    protected long logInternal(LogManager logManager,
1028                   boolean allowDeltas,
1029                   boolean isProvisional,
1030                               boolean proactiveMigration,
1031                               boolean backgroundIO,
1032                               IN parent)
1033        throws DatabaseException {
1034
1035        boolean doDeltaLog = false;
1036        long lastFullVersion = getLastFullVersion();
1037
1038        /* Allow the cleaner to migrate LNs before logging. */
1039        Cleaner cleaner = getDatabase().getDbEnvironment().getCleaner();
1040        cleaner.lazyMigrateLNs(this, proactiveMigration, backgroundIO);
1041
1042        /* Check for dirty LNs in deferred-write databases. */
1043        if (getDatabase().isDeferredWrite()) {
1044            logDirtyLNs(logManager);
1045        }
1046
1047        /*
1048         * We can log a delta rather than full version of this BIN if
1049         * - this has been called from the checkpointer with allowDeltas=true
1050         * - there is a full version on disk
1051         * - we meet the percentage heuristics defined by environment params.
1052         * - this delta is not prohibited because of cleaning or compression
1053         * - this is not a deferred write db
1054         * All other logging should be of the full version.
1055         */
1056        BINDelta deltaInfo = null;
1057        if ((allowDeltas) &&
1058            (lastFullVersion != DbLsn.NULL_LSN) &&
1059            !prohibitNextDelta &&
1060            !getDatabase().isDeferredWrite()) {
1061            deltaInfo = new BINDelta(this);
1062            doDeltaLog = doDeltaLog(deltaInfo);
1063        }
1064
1065        long returnLsn = DbLsn.NULL_LSN;
1066        if (doDeltaLog) {
1067
1068            /*
1069             * Don't change the dirtiness of the node -- leave it dirty. Deltas
1070             * are never provisional, they must be processed at recovery time.
1071             */
1072            lastDeltaVersion = logManager.log
1073                (deltaInfo, false, // isProvisional
1074 backgroundIO, DbLsn.NULL_LSN, 0);
1075            returnLsn = DbLsn.NULL_LSN;
1076            numDeltasSinceLastFull++;
1077        } else {
1078            /* Log a full version of the IN. */
1079            returnLsn = super.logInternal
1080                (logManager, allowDeltas, isProvisional, proactiveMigration,
1081                 backgroundIO, parent);
1082            lastDeltaVersion = DbLsn.NULL_LSN;
1083            numDeltasSinceLastFull = 0;
1084        }
1085        prohibitNextDelta = false;
1086
1087        return returnLsn;
1088    }
1089
1090    private void logDirtyLNs(LogManager logManager)
1091        throws DatabaseException {
1092        
1093        DatabaseId dbId = getDatabase().getId();
1094        EnvironmentImpl envImpl = getDatabase().getDbEnvironment();
1095                
1096        for (int i = 0; i < getNEntries(); i++) {
1097            Node node = getTarget(i);
1098            if ((node != null) && (node instanceof LN)) {
1099
1100                LN ln = (LN) node;
1101                if (ln.isDirty()) {
1102
1103                    /*
1104                     * Only deferred write databases should have dirty
1105                     * LNs. This is an overly stringent assertion, because a
1106                     * db can flop between dw and durable mode, but is used
1107                     * currently for our regression testing.
1108                     */
1109                    assert getDatabase().isDeferredWrite();
1110
1111                    /*
1112                     * Note that old offset will not be marked obsolete.
1113                     * Ideally we'd use getLsn(i). For DW we don't know the
1114                     * size of the last logged LN, so we pass zero for the
1115                     * obsolete size.
1116                     */
1117                    long oldOffset = envImpl.getDeferredWriteTemp() ?
1118                        getLsn(i) : DbLsn.NULL_LSN;
1119                    long lsn = ln.log(envImpl,
1120                                      dbId,
1121                                      getKey(i),
1122                                      null, // delDupKey
1123 oldOffset, // obsolete tracking
1124 0, // obsolete size
1125 null, // locker
1126 true, // backgroundIO
1127 false); // Is provisional.
1128 updateEntry(i, lsn);
1129                }
1130            }
1131        }
1132    }
1133
1134    /**
1135     * Decide whether to log a full or partial BIN, depending on the ratio of
1136     * the delta size to full BIN size, and the number of deltas that
1137     * have been logged since the last full.
1138     *
1139     * @return true if we should log the deltas of this BIN
1140     */
1141    private boolean doDeltaLog(BINDelta deltaInfo)
1142        throws DatabaseException {
1143
1144        int maxDiffs = (getNEntries() *
1145                        getDatabase().getBinDeltaPercent())/100;
1146        if ((deltaInfo.getNumDeltas() <= maxDiffs) &&
1147            (numDeltasSinceLastFull < getDatabase().getBinMaxDeltas())) {
1148            return true;
1149        } else {
1150            return false;
1151        }
1152    }
1153}
1154

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags