0001: /*-
0002: * See the file LICENSE for redistribution information.
0003: *
0004: * Copyright (c) 2002,2008 Oracle. All rights reserved.
0005: *
0006: * $Id: Tree.java,v 1.418.2.9 2008/01/07 15:14:16 cwl Exp $
0007: */
0008:
0009: package com.sleepycat.je.tree;
0010:
0011: import java.nio.ByteBuffer;
0012: import java.util.Arrays;
0013: import java.util.ArrayList;
0014: import java.util.List;
0015: import java.util.ListIterator;
0016: import java.util.logging.Level;
0017: import java.util.logging.Logger;
0018:
0019: import com.sleepycat.je.DatabaseException;
0020: import com.sleepycat.je.cleaner.UtilizationTracker;
0021: import com.sleepycat.je.config.EnvironmentParams;
0022: import com.sleepycat.je.dbi.CursorImpl;
0023: import com.sleepycat.je.dbi.DatabaseImpl;
0024: import com.sleepycat.je.dbi.DbConfigManager;
0025: import com.sleepycat.je.dbi.DbTree;
0026: import com.sleepycat.je.dbi.EnvironmentImpl;
0027: import com.sleepycat.je.dbi.INList;
0028: import com.sleepycat.je.latch.LatchSupport;
0029: import com.sleepycat.je.latch.SharedLatch;
0030: import com.sleepycat.je.log.LogManager;
0031: import com.sleepycat.je.log.LogUtils;
0032: import com.sleepycat.je.log.Loggable;
0033: import com.sleepycat.je.recovery.RecoveryManager;
0034: import com.sleepycat.je.txn.BasicLocker;
0035: import com.sleepycat.je.txn.LockGrantType;
0036: import com.sleepycat.je.txn.LockResult;
0037: import com.sleepycat.je.txn.LockType;
0038: import com.sleepycat.je.txn.Locker;
0039: import com.sleepycat.je.txn.WriteLockInfo;
0040: import com.sleepycat.je.utilint.DbLsn;
0041: import com.sleepycat.je.utilint.TestHook;
0042: import com.sleepycat.je.utilint.TestHookExecute;
0043: import com.sleepycat.je.utilint.Tracer;
0044:
0045: /**
0046: * Tree implements the JE B+Tree.
0047: *
0048: * A note on tree search patterns:
0049: * There's a set of Tree.search* methods. Some clients of the tree use
0050: * those search methods directly, whereas other clients of the tree
0051: * tend to use methods built on top of search.
0052: *
0053: * The semantics of search* are
0054: * they leave you pointing at a BIN or IN
0055: * they don't tell you where the reference of interest is.
0056: * they traverse a single tree, to jump into the duplicate tree, the
0057: * caller has to take explicit action.
0058: * The semantics of the get* methods are:
0059: * they leave you pointing at a BIN or IN
0060: * they return the index of the slot of interest
0061: * they traverse down to whatever level is needed -- they'll take care of
0062: * jumping into the duplicate tree.
0063: * they are built on top of search* methods.
0064: * For the future:
0065: * Over time, we need to clarify which methods are to be used by clients
0066: * of the tree. Preferably clients that call the tree use get*, although
0067: * their are cases where they need visibility into the tree structure. For
0068: * example, tee cursors use search* because they want to add themselves to
0069: * BIN before jumping into the duplicate tree.
0070: *
0071: * Also, search* should return the location of the slot to save us a
0072: * second binary search.
0073: */
0074: public final class Tree implements Loggable {
0075:
0076: /* For debug tracing */
0077: private static final String TRACE_ROOT_SPLIT = "RootSplit:";
0078: private static final String TRACE_DUP_ROOT_SPLIT = "DupRootSplit:";
0079: private static final String TRACE_MUTATE = "Mut:";
0080: private static final String TRACE_INSERT = "Ins:";
0081: private static final String TRACE_INSERT_DUPLICATE = "InsD:";
0082:
0083: private DatabaseImpl database;
0084: private ChildReference root;
0085: private int maxMainTreeEntriesPerNode;
0086: private int maxDupTreeEntriesPerNode;
0087: private boolean purgeRoot;
0088:
0089: /*
0090: * Latch that must be held when using/accessing the root node. Protects
0091: * against the root being changed out from underneath us by splitRoot.
0092: */
0093: private SharedLatch rootLatch;
0094:
0095: private TreeStats treeStats;
0096:
0097: private ThreadLocal treeStatsAccumulatorTL = new ThreadLocal();
0098:
0099: /*
0100: * We don't need the stack trace on this so always throw a static and
0101: * avoid the cost of Throwable.fillInStack() every time it's thrown.
0102: * [#13354].
0103: */
0104: private static SplitRequiredException splitRequiredException = new SplitRequiredException();
0105:
0106: /**
0107: * Embodies an enum for the type of search being performed. NORMAL means
0108: * do a regular search down the tree. LEFT/RIGHT means search down the
0109: * left/right side to find the first/last node in the tree.
0110: */
0111: public static class SearchType {
0112: /* Search types */
0113: public static final SearchType NORMAL = new SearchType();
0114: public static final SearchType LEFT = new SearchType();
0115: public static final SearchType RIGHT = new SearchType();
0116:
0117: /* No lock types can be defined outside this class. */
0118: private SearchType() {
0119: }
0120: }
0121:
0122: /* For unit tests */
0123: private TestHook waitHook; // used for generating race conditions
0124: private TestHook searchHook; // [#12736]
0125: private TestHook ckptHook; // [#13897]
0126:
0127: /**
0128: * Create a new tree.
0129: */
0130: public Tree(DatabaseImpl database) throws DatabaseException {
0131:
0132: init(database);
0133: setDatabase(database);
0134: }
0135:
0136: /**
0137: * Create a tree that's being read in from the log.
0138: */
0139: public Tree() throws DatabaseException {
0140:
0141: init(null);
0142: maxMainTreeEntriesPerNode = 0;
0143: maxDupTreeEntriesPerNode = 0;
0144: }
0145:
0146: /**
0147: * constructor helper
0148: */
0149: private void init(DatabaseImpl database) {
0150: rootLatch = LatchSupport
0151: .makeSharedLatch("RootLatch",
0152: (database != null) ? database
0153: .getDbEnvironment() : null);
0154: treeStats = new TreeStats();
0155: this .root = null;
0156: this .database = database;
0157: }
0158:
0159: /**
0160: * Set the database for this tree. Used by recovery when recreating an
0161: * existing tree.
0162: */
0163: public void setDatabase(DatabaseImpl database)
0164: throws DatabaseException {
0165:
0166: this .database = database;
0167: maxMainTreeEntriesPerNode = database.getNodeMaxEntries();
0168: maxDupTreeEntriesPerNode = database.getNodeMaxDupTreeEntries();
0169: DbConfigManager configManager = database.getDbEnvironment()
0170: .getConfigManager();
0171: purgeRoot = configManager
0172: .getBoolean(EnvironmentParams.COMPRESSOR_PURGE_ROOT);
0173: }
0174:
0175: /**
0176: * @return the database for this Tree.
0177: */
0178: public DatabaseImpl getDatabase() {
0179: return database;
0180: }
0181:
0182: /**
0183: * Set the root for the tree. Should only be called within the root latch.
0184: */
0185: public void setRoot(ChildReference newRoot, boolean notLatched) {
0186: assert (notLatched || rootLatch.isWriteLockedByCurrentThread());
0187: root = newRoot;
0188: }
0189:
0190: public ChildReference makeRootChildReference(Node target,
0191: byte[] key, long lsn) {
0192: return new RootChildReference(target, key, lsn);
0193: }
0194:
0195: private ChildReference makeRootChildReference() {
0196: return new RootChildReference();
0197: }
0198:
0199: /*
0200: * A tree doesn't have a root if (a) the root field is null, or (b)
0201: * the root is non-null, but has neither a valid target nor a valid
0202: * LSN. Case (b) can happen if the dataabase is or was previously opened in
0203: * deferred write mode.
0204: * @return false if there is no real root.
0205: */
0206: public boolean rootExists() {
0207: if (root == null) {
0208: return false;
0209: }
0210:
0211: if ((root.getTarget() == null)
0212: && (root.getLsn() == DbLsn.NULL_LSN)) {
0213: return false;
0214: }
0215:
0216: return true;
0217: }
0218:
0219: /**
0220: * Perform a fast check to see if the root IN is resident. No latching is
0221: * performed. To ensure that the root IN is not loaded by another thread,
0222: * this method should be called while holding a write lock on the MapLN.
0223: * That will prevent opening the DB in another thread, and potentially
0224: * loading the root IN. [#13415]
0225: */
0226: public boolean isRootResident() {
0227: return root != null && root.getTarget() != null;
0228: }
0229:
0230: /*
0231: * Class that overrides fetchTarget() so that if the rootLatch is not
0232: * held exclusively when the root is fetched, we upgrade it to exclusive.
0233: */
0234: private class RootChildReference extends ChildReference {
0235:
0236: private RootChildReference() {
0237: super ();
0238: }
0239:
0240: private RootChildReference(Node target, byte[] key, long lsn) {
0241: super (target, key, lsn);
0242: }
0243:
0244: /* Not used. */
0245: private RootChildReference(Node target, byte[] key, long lsn,
0246: byte existingState) {
0247: super (target, key, lsn, existingState);
0248: }
0249:
0250: /* Caller is responsible for releasing rootLatch. */
0251: public Node fetchTarget(DatabaseImpl database, IN in)
0252: throws DatabaseException {
0253:
0254: if (getTarget() == null
0255: && !rootLatch.isWriteLockedByCurrentThread()) {
0256: rootLatch.release();
0257: rootLatch.acquireExclusive();
0258: }
0259:
0260: return super .fetchTarget(database, in);
0261: }
0262:
0263: public void setTarget(Node target) {
0264: assert rootLatch.isWriteLockedByCurrentThread();
0265: super .setTarget(target);
0266: }
0267:
0268: public void clearTarget() {
0269: assert rootLatch.isWriteLockedByCurrentThread();
0270: super .clearTarget();
0271: }
0272:
0273: public void setLsn(long lsn) {
0274: assert rootLatch.isWriteLockedByCurrentThread();
0275: super .setLsn(lsn);
0276: }
0277:
0278: void updateLsnAfterOptionaLog(DatabaseImpl dbImpl, long lsn) {
0279: assert rootLatch.isWriteLockedByCurrentThread();
0280: super .updateLsnAfterOptionalLog(dbImpl, lsn);
0281: }
0282: }
0283:
0284: /**
0285: * Get LSN of the rootIN. Obtained without latching, should only be
0286: * accessed while quiescent.
0287: */
0288: public long getRootLsn() {
0289: if (root == null) {
0290: return DbLsn.NULL_LSN;
0291: } else {
0292: return root.getLsn();
0293: }
0294: }
0295:
0296: /**
0297: * @return the TreeStats for this tree.
0298: */
0299: TreeStats getTreeStats() {
0300: return treeStats;
0301: }
0302:
0303: private TreeWalkerStatsAccumulator getTreeStatsAccumulator() {
0304: if (EnvironmentImpl.getThreadLocalReferenceCount() > 0) {
0305: return (TreeWalkerStatsAccumulator) treeStatsAccumulatorTL
0306: .get();
0307: } else {
0308: return null;
0309: }
0310: }
0311:
0312: public void setTreeStatsAccumulator(TreeWalkerStatsAccumulator tSA) {
0313: treeStatsAccumulatorTL.set(tSA);
0314: }
0315:
0316: public IN withRootLatchedExclusive(WithRootLatched wrl)
0317: throws DatabaseException {
0318:
0319: try {
0320: rootLatch.acquireExclusive();
0321: return wrl.doWork(root);
0322: } finally {
0323: rootLatch.release();
0324: }
0325: }
0326:
0327: public IN withRootLatchedShared(WithRootLatched wrl)
0328: throws DatabaseException {
0329:
0330: try {
0331: rootLatch.acquireShared();
0332: return wrl.doWork(root);
0333: } finally {
0334: rootLatch.release();
0335: }
0336: }
0337:
0338: /**
0339: * Deletes a BIN specified by key from the tree. If the BIN resides in a
0340: * subtree that can be pruned away, prune as much as possible, so we
0341: * don't leave a branch that has no BINs.
0342: *
0343: * It's possible that the targeted BIN will now have entries, or will
0344: * have resident cursors. Either will prevent deletion.
0345: *
0346: * @param idKey - the identifier key of the node to delete.
0347: * @param tracker is used for tracking obsolete node info.
0348: */
0349: public void delete(byte[] idKey, UtilizationTracker tracker)
0350: throws DatabaseException, NodeNotEmptyException,
0351: CursorsExistException {
0352:
0353: IN subtreeRootIN = null;
0354:
0355: /*
0356: * A delete is a reverse split that must be propagated up to the root.
0357: * [#13501] Keep all nodes from the rootIN to the parent of the
0358: * deletable subtree latched as we descend so we can log the
0359: * IN deletion and cascade the logging up the tree. The latched
0360: * nodes are kept in order in the nodeLadder.
0361: */
0362: ArrayList nodeLadder = new ArrayList();
0363:
0364: IN rootIN = null;
0365: boolean rootNeedsUpdating = false;
0366: rootLatch.acquireExclusive();
0367: try {
0368: if (!rootExists()) {
0369: /* no action, tree is deleted or was never persisted. */
0370: return;
0371: }
0372:
0373: rootIN = (IN) root.fetchTarget(database, null);
0374: rootIN.latch(false);
0375:
0376: searchDeletableSubTree(rootIN, idKey, nodeLadder);
0377: if (nodeLadder.size() == 0) {
0378:
0379: /*
0380: * The root is the top of the deletable subtree. Delete the
0381: * whole tree if the purge root je property is set.
0382: * In general, there's no reason to delete this last
0383: * IN->...IN->BIN subtree since we're likely to to add more
0384: * nodes to this tree again. Deleting the subtree also
0385: * adds to the space used by the log since a MapLN needs to
0386: * be written when the root is nulled, and a MapLN, IN
0387: * (root), BIN needs to be written when the root is
0388: * recreated.
0389: *
0390: * Consider a queue application which frequently inserts
0391: * and deletes entries and often times leaves the tree
0392: * empty, but will insert new records again.
0393: *
0394: * An optimization might be to prune the multiple IN path
0395: * to the last BIN (if it even exists) to just a root IN
0396: * pointing to the single BIN, but this doesn't feel like
0397: * it's worth the trouble since the extra depth doesn't
0398: * matter all that much.
0399: */
0400:
0401: if (purgeRoot) {
0402: subtreeRootIN = logTreeRemoval(rootIN);
0403: if (subtreeRootIN != null) {
0404: rootNeedsUpdating = true;
0405: }
0406: }
0407: } else {
0408: /* Detach this subtree. */
0409: SplitInfo detachPoint = (SplitInfo) nodeLadder
0410: .get(nodeLadder.size() - 1);
0411: boolean deleteOk = detachPoint.parent.deleteEntry(
0412: detachPoint.index, true);
0413: assert deleteOk;
0414:
0415: /* Cascade updates upward, including writing the root IN. */
0416: rootNeedsUpdating = cascadeUpdates(nodeLadder, null, -1);
0417: subtreeRootIN = detachPoint.child;
0418: }
0419: } finally {
0420: releaseNodeLadderLatches(nodeLadder);
0421:
0422: if (rootIN != null) {
0423: rootIN.releaseLatch();
0424: }
0425:
0426: rootLatch.release();
0427: }
0428:
0429: if (subtreeRootIN != null) {
0430:
0431: EnvironmentImpl envImpl = database.getDbEnvironment();
0432: if (rootNeedsUpdating) {
0433: /*
0434: * modifyDbRoot will grab locks and we can't have the INList
0435: * latches or root latch held while it tries to acquire locks.
0436: */
0437: DbTree dbTree = envImpl.getDbMapTree();
0438: dbTree.optionalModifyDbRoot(database);
0439: RecoveryManager.traceRootDeletion(Level.FINE, database);
0440: }
0441:
0442: /*
0443: * Count obsolete nodes after logging the delete. We can do
0444: * this without having the nodes of the subtree latched because the
0445: * subtree has been detached from the tree.
0446: */
0447: INList inList = envImpl.getInMemoryINs();
0448: accountForSubtreeRemoval(inList, subtreeRootIN, tracker);
0449: }
0450: }
0451:
0452: private void releaseNodeLadderLatches(ArrayList nodeLadder)
0453: throws DatabaseException {
0454:
0455: /*
0456: * Clear any latches left in the node ladder. Release from the
0457: * bottom up.
0458: */
0459: ListIterator iter = nodeLadder.listIterator(nodeLadder.size());
0460: while (iter.hasPrevious()) {
0461: SplitInfo info = (SplitInfo) iter.previous();
0462: info.child.releaseLatch();
0463: }
0464: }
0465:
0466: /**
0467: * This entire tree is empty, clear the root and log a new MapLN
0468: * @return the rootIN that has been detached, or null if there
0469: * hasn't been any removal.
0470: */
0471: private IN logTreeRemoval(IN rootIN) throws DatabaseException {
0472:
0473: assert rootLatch.isWriteLockedByCurrentThread();
0474: IN detachedRootIN = null;
0475:
0476: /**
0477: * XXX: Suspect that validateSubtree is no longer needed, now that we
0478: * hold all latches.
0479: */
0480: if ((rootIN.getNEntries() <= 1)
0481: && (rootIN.validateSubtreeBeforeDelete(0))) {
0482:
0483: root = null;
0484:
0485: /*
0486: * Record the root deletion for recovery. Do this within
0487: * the root latch. We need to put this log entry into the
0488: * log before another thread comes in and creates a new
0489: * rootIN for this database.
0490: *
0491: * For example,
0492: * LSN 1000 IN delete info entry
0493: * LSN 1010 new IN, for next set of inserts
0494: * LSN 1020 new BIN, for next set of inserts.
0495: *
0496: * The entry at 1000 is needed so that LSN 1010 will
0497: * properly supercede all previous IN entries in the tree.
0498: * Without the INDelete, we may not use the new root, because
0499: * it has a different node id.
0500: */
0501: INDeleteInfo info = new INDeleteInfo(rootIN.getNodeId(),
0502: rootIN.getIdentifierKey(), database.getId());
0503: info.optionalLog(database.getDbEnvironment()
0504: .getLogManager(), database);
0505:
0506: detachedRootIN = rootIN;
0507: }
0508: return detachedRootIN;
0509: }
0510:
0511: /**
0512: * Update nodes for a delete, going upwards. For example, suppose a
0513: * node ladder holds:
0514: * INa, INb, index for INb in INa
0515: * INb, INc, index for INc in INb
0516: * INc, BINd, index for BINd in INc
0517: *
0518: * When we enter this method, BINd has already been removed from INc. We
0519: * need to
0520: * - log INc
0521: * - update INb, log INb
0522: * - update INa, log INa
0523: *
0524: * @param nodeLadder List of SplitInfos describing each node pair on the
0525: * downward path
0526: * @param binRoot parent of the dup tree, or null if this is not for
0527: * dups.
0528: * @param index slot occupied by this din tree.
0529: * @return whether the DB root needs updating.
0530: */
0531: private boolean cascadeUpdates(ArrayList nodeLadder, BIN binRoot,
0532: int index) throws DatabaseException {
0533:
0534: ListIterator iter = nodeLadder.listIterator(nodeLadder.size());
0535: EnvironmentImpl envImpl = database.getDbEnvironment();
0536: LogManager logManager = envImpl.getLogManager();
0537:
0538: long newLsn = DbLsn.NULL_LSN;
0539: SplitInfo info = null;
0540: while (iter.hasPrevious()) {
0541: info = (SplitInfo) iter.previous();
0542:
0543: if (newLsn != DbLsn.NULL_LSN) {
0544: info.parent.updateEntry(info.index, newLsn);
0545: }
0546: newLsn = info.parent.optionalLog(logManager);
0547: }
0548:
0549: boolean rootNeedsUpdating = false;
0550: if (info != null) {
0551: /* We've logged the top of this subtree, record it properly. */
0552: if (info.parent.isDbRoot()) {
0553: /* We updated the rootIN of the database. */
0554: assert rootLatch.isWriteLockedByCurrentThread();
0555: root.updateLsnAfterOptionalLog(database, newLsn);
0556: rootNeedsUpdating = true;
0557: } else if ((binRoot != null) && info.parent.isRoot()) {
0558: /* We updated the DIN root of the database. */
0559: binRoot.updateEntry(index, newLsn);
0560: } else {
0561: assert false;
0562: }
0563: }
0564: return rootNeedsUpdating;
0565: }
0566:
0567: /**
0568: * Delete a subtree of a duplicate tree. Find the duplicate tree using
0569: * mainKey in the top part of the tree and idKey in the duplicate tree.
0570: *
0571: * @param idKey the identifier key to be used in the duplicate subtree to
0572: * find the duplicate path.
0573: * @param mainKey the key to be used in the main tree to find the
0574: * duplicate subtree.
0575: * @param tracker is used for tracking obsolete node info.
0576: *
0577: * @return true if the delete succeeded, false if there were still cursors
0578: * present on the leaf DBIN of the subtree that was located.
0579: */
0580: public void deleteDup(byte[] idKey, byte[] mainKey,
0581: UtilizationTracker tracker) throws DatabaseException,
0582: NodeNotEmptyException, CursorsExistException {
0583:
0584: /* Find the BIN that is the parent of this duplicate tree. */
0585: IN in = search(mainKey, SearchType.NORMAL, -1, null, false /*updateGeneration*/);
0586:
0587: IN deletedSubtreeRoot = null;
0588: try {
0589: assert in.isLatchOwnerForWrite();
0590: assert in instanceof BIN;
0591: assert in.getNEntries() > 0;
0592:
0593: /* Find the appropriate entry in this BIN. */
0594: int index = in.findEntry(mainKey, false, true);
0595: if (index >= 0) {
0596: deletedSubtreeRoot = deleteDupSubtree(idKey, (BIN) in,
0597: index);
0598: }
0599: } finally {
0600: in.releaseLatch();
0601: }
0602:
0603: if (deletedSubtreeRoot != null) {
0604: EnvironmentImpl envImpl = database.getDbEnvironment();
0605: accountForSubtreeRemoval(envImpl.getInMemoryINs(),
0606: deletedSubtreeRoot, tracker);
0607: }
0608: }
0609:
0610: /**
0611: * We enter and leave this method with 'bin' latched.
0612: * @return the root of the subtree we have deleted, so it can be
0613: * properly accounted for. May be null if nothing was deleted.
0614: */
0615: private IN deleteDupSubtree(byte[] idKey, BIN bin, int index)
0616: throws DatabaseException, NodeNotEmptyException,
0617: CursorsExistException {
0618:
0619: EnvironmentImpl envImpl = database.getDbEnvironment();
0620: boolean dupCountLNLocked = false;
0621: DupCountLN dcl = null;
0622: BasicLocker locker = new BasicLocker(envImpl);
0623:
0624: /* Latch the DIN root. */
0625: DIN duplicateRoot = (DIN) bin.fetchTarget(index);
0626: duplicateRoot.latch(false);
0627:
0628: ArrayList nodeLadder = new ArrayList();
0629: IN subtreeRootIN = null;
0630:
0631: try {
0632:
0633: /*
0634: * Read lock the dup count LN to ascertain whether there are any
0635: * writers in the tree. XXX: This seems unnecessary now, revisit.
0636: */
0637: ChildReference dclRef = duplicateRoot.getDupCountLNRef();
0638: dcl = (DupCountLN) dclRef.fetchTarget(database,
0639: duplicateRoot);
0640:
0641: LockResult lockResult = locker.nonBlockingLock(dcl
0642: .getNodeId(), LockType.READ, database);
0643: if (lockResult.getLockGrant() == LockGrantType.DENIED) {
0644: throw CursorsExistException.CURSORS_EXIST;
0645: } else {
0646: dupCountLNLocked = true;
0647: }
0648:
0649: /*
0650: * We don't release the latch on bin before we search the
0651: * duplicate tree below because we might be deleting the whole
0652: * subtree from the IN and we want to keep it latched until we
0653: * know.
0654: */
0655: searchDeletableSubTree(duplicateRoot, idKey, nodeLadder);
0656:
0657: if (nodeLadder.size() == 0) {
0658: /* We're deleting the duplicate root. */
0659: if (bin.nCursors() == 0) {
0660: boolean deleteOk = bin.deleteEntry(index, true);
0661: assert deleteOk;
0662:
0663: /*
0664: * Use an INDupDeleteInfo to make it clear that
0665: * this duplicate tree has been eradicated. This
0666: * is analagous to deleting a root; we must be sure
0667: * that we can overlay another subtree onto this slot
0668: * at recovery redo.
0669: */
0670: INDupDeleteInfo info = new INDupDeleteInfo(
0671: duplicateRoot.getNodeId(), duplicateRoot
0672: .getMainTreeKey(), duplicateRoot
0673: .getDupTreeKey(), database.getId());
0674: info.optionalLog(envImpl.getLogManager(), database);
0675:
0676: subtreeRootIN = duplicateRoot;
0677:
0678: if (bin.getNEntries() == 0) {
0679: database.getDbEnvironment()
0680: .addToCompressorQueue(bin, null, false);
0681: }
0682: } else {
0683:
0684: /*
0685: * Cursors prevent us from deleting this dup tree, we'll
0686: * have to retry.
0687: */
0688: throw CursorsExistException.CURSORS_EXIST;
0689: }
0690: } else {
0691:
0692: /* We're deleting a portion of the duplicate tree. */
0693: SplitInfo detachPoint = (SplitInfo) nodeLadder
0694: .get(nodeLadder.size() - 1);
0695: boolean deleteOk = detachPoint.parent.deleteEntry(
0696: detachPoint.index, true);
0697: assert deleteOk;
0698:
0699: /*
0700: * Cascade updates upward, including writing the root
0701: * DIN and parent BIN.
0702: */
0703: cascadeUpdates(nodeLadder, bin, index);
0704: subtreeRootIN = detachPoint.child;
0705: }
0706: } finally {
0707: releaseNodeLadderLatches(nodeLadder);
0708:
0709: /* FindBugs -- ignore dcl possibly null warning. */
0710: if (dupCountLNLocked) {
0711: locker.releaseLock(dcl.getNodeId());
0712: }
0713:
0714: duplicateRoot.releaseLatch();
0715: }
0716:
0717: return subtreeRootIN;
0718: }
0719:
0720: /**
0721: * Find the leftmost node (IN or BIN) in the tree. Do not descend into a
0722: * duplicate tree if the leftmost entry of the first BIN refers to one.
0723: *
0724: * @return the leftmost node in the tree, null if the tree is empty. The
0725: * returned node is latched and the caller must release it.
0726: */
0727: public IN getFirstNode() throws DatabaseException {
0728:
0729: return search(null, SearchType.LEFT, -1, null, true /*updateGeneration*/);
0730: }
0731:
0732: /**
0733: * Find the rightmost node (IN or BIN) in the tree. Do not descend into a
0734: * duplicate tree if the rightmost entry of the last BIN refers to one.
0735: *
0736: * @return the rightmost node in the tree, null if the tree is empty. The
0737: * returned node is latched and the caller must release it.
0738: */
0739: public IN getLastNode() throws DatabaseException {
0740:
0741: return search(null, SearchType.RIGHT, -1, null, true /*updateGeneration*/);
0742: }
0743:
0744: /**
0745: * Find the leftmost node (DBIN) in a duplicate tree.
0746: *
0747: * @return the leftmost node in the tree, null if the tree is empty. The
0748: * returned node is latched and the caller must release it.
0749: */
0750: public DBIN getFirstNode(DIN dupRoot) throws DatabaseException {
0751:
0752: if (dupRoot == null) {
0753: throw new IllegalArgumentException(
0754: "getFirstNode passed null root");
0755: }
0756:
0757: assert dupRoot.isLatchOwnerForWrite();
0758:
0759: IN ret = searchSubTree(dupRoot, null, SearchType.LEFT, -1,
0760: null, true /*updateGeneration*/);
0761: return (DBIN) ret;
0762: }
0763:
0764: /**
0765: * Find the rightmost node (DBIN) in a duplicate tree.
0766: *
0767: * @return the rightmost node in the tree, null if the tree is empty. The
0768: * returned node is latched and the caller must release it.
0769: */
0770: public DBIN getLastNode(DIN dupRoot) throws DatabaseException {
0771:
0772: if (dupRoot == null) {
0773: throw new IllegalArgumentException(
0774: "getLastNode passed null root");
0775: }
0776:
0777: assert dupRoot.isLatchOwnerForWrite();
0778:
0779: IN ret = searchSubTree(dupRoot, null, SearchType.RIGHT, -1,
0780: null, true /*updateGeneration*/);
0781: return (DBIN) ret;
0782: }
0783:
0784: /**
0785: * GetParentNode without optional tracking.
0786: */
0787: public SearchResult getParentINForChildIN(IN child,
0788: boolean requireExactMatch, boolean updateGeneration)
0789: throws DatabaseException {
0790:
0791: return getParentINForChildIN(child, requireExactMatch,
0792: updateGeneration, -1, null);
0793: }
0794:
0795: /**
0796: * Return a reference to the parent or possible parent of the child. Used
0797: * by objects that need to take a standalone node and find it in the tree,
0798: * like the evictor, checkpointer, and recovery.
0799: *
0800: * @param child The child node for which to find the parent. This node is
0801: * latched by the caller and is released by this function before returning
0802: * to the caller.
0803: *
0804: * @param requireExactMatch if true, we must find the exact parent, not a
0805: * potential parent.
0806: *
0807: * @param updateGeneration if true, set the generation count during
0808: * latching. Pass false when the LRU should not be impacted, such as
0809: * during eviction and checkpointing.
0810: *
0811: * @param trackingList if not null, add the LSNs of the parents visited
0812: * along the way, as a debug tracing mechanism. This is meant to stay in
0813: * production, to add information to the log.
0814: *
0815: * @return a SearchResult object. If the parent has been found,
0816: * result.foundExactMatch is true. If any parent, exact or potential has
0817: * been found, result.parent refers to that node.
0818: */
0819: public SearchResult getParentINForChildIN(IN child,
0820: boolean requireExactMatch, boolean updateGeneration,
0821: int targetLevel, List trackingList)
0822: throws DatabaseException {
0823:
0824: /* Sanity checks */
0825: if (child == null) {
0826: throw new IllegalArgumentException(
0827: "getParentNode passed null");
0828: }
0829:
0830: assert child.isLatchOwnerForWrite();
0831:
0832: /*
0833: * Get information from child before releasing latch.
0834: */
0835: byte[] mainTreeKey = child.getMainTreeKey();
0836: byte[] dupTreeKey = child.getDupTreeKey();
0837: boolean isRoot = child.isRoot();
0838: child.releaseLatch();
0839:
0840: return getParentINForChildIN(child.getNodeId(), child
0841: .containsDuplicates(), isRoot, mainTreeKey, dupTreeKey,
0842: requireExactMatch, updateGeneration, targetLevel,
0843: trackingList, true);
0844: }
0845:
0846: /**
0847: * Return a reference to the parent or possible parent of the child. Used
0848: * by objects that need to take a node id and find it in the tree,
0849: * like the evictor, checkpointer, and recovery.
0850: *
0851: * @param requireExactMatch if true, we must find the exact parent, not a
0852: * potential parent.
0853: *
0854: * @param updateGeneration if true, set the generation count during
0855: * latching. Pass false when the LRU should not be impacted, such as
0856: * during eviction and checkpointing.
0857: *
0858: * @param trackingList if not null, add the LSNs of the parents visited
0859: * along the way, as a debug tracing mechanism. This is meant to stay in
0860: * production, to add information to the log.
0861: *
0862: * @param doFetch if false, stop the search if we run into a non-resident
0863: * child. Used by the checkpointer to avoid conflicting with work done
0864: * by the evictor.
0865: *
0866: * @param child The child node for which to find the parent. This node is
0867: * latched by the caller and is released by this function before returning
0868: * to the caller.
0869: *
0870: * @return a SearchResult object. If the parent has been found,
0871: * result.foundExactMatch is true. If any parent, exact or potential has
0872: * been found, result.parent refers to that node.
0873: */
0874: public SearchResult getParentINForChildIN(long targetNodeId,
0875: boolean targetContainsDuplicates, boolean targetIsRoot,
0876: byte[] targetMainTreeKey, byte[] targetDupTreeKey,
0877: boolean requireExactMatch, boolean updateGeneration,
0878: int targetLevel, List trackingList, boolean doFetch)
0879: throws DatabaseException {
0880:
0881: IN rootIN = getRootINLatchedExclusive(updateGeneration);
0882:
0883: SearchResult result = new SearchResult();
0884: if (rootIN != null) {
0885: /* The tracking list is a permanent tracing aid. */
0886: if (trackingList != null) {
0887: trackingList.add(new TrackingInfo(root.getLsn(), rootIN
0888: .getNodeId()));
0889: }
0890:
0891: IN potentialParent = rootIN;
0892:
0893: try {
0894: while (result.keepSearching) {
0895:
0896: /*
0897: * [12736] Prune away oldBin. Assert has intentional
0898: * side effect.
0899: */
0900: assert TestHookExecute.doHookIfSet(searchHook);
0901:
0902: potentialParent.findParent(SearchType.NORMAL,
0903: targetNodeId, targetContainsDuplicates,
0904: targetIsRoot, targetMainTreeKey,
0905: targetDupTreeKey, result,
0906: requireExactMatch, updateGeneration,
0907: targetLevel, trackingList, doFetch);
0908: potentialParent = result.parent;
0909: }
0910: } catch (Exception e) {
0911: potentialParent.releaseLatchIfOwner();
0912:
0913: throw new DatabaseException(e);
0914: }
0915: }
0916: return result;
0917: }
0918:
0919: /**
0920: * Return a reference to the parent of this LN. This searches through the
0921: * main and duplicate tree and allows splits. Set the tree location to the
0922: * proper BIN parent whether or not the LN child is found. That's because
0923: * if the LN is not found, recovery or abort will need to place it within
0924: * the tree, and so we must point at the appropriate position.
0925: *
0926: * <p>When this method returns with location.bin non-null, the BIN is
0927: * latched and must be unlatched by the caller. Note that location.bin may
0928: * be non-null even if this method returns false.</p>
0929: *
0930: * @param location a holder class to hold state about the location
0931: * of our search. Sort of an internal cursor.
0932: *
0933: * @param mainKey key to navigate through main key
0934: *
0935: * @param dupKey key to navigate through duplicate tree. May be null, since
0936: * deleted lns have no data.
0937: *
0938: * @param ln the node instantiated from the log
0939: *
0940: * @param splitsAllowed true if this method is allowed to cause tree splits
0941: * as a side effect. In practice, recovery can cause splits, but abort
0942: * can't.
0943: *
0944: * @param searchDupTree true if a search through the dup tree looking for
0945: * a match on the ln's node id should be made (only in the case where
0946: * dupKey == null). See SR 8984.
0947: *
0948: * @param updateGeneration if true, set the generation count during
0949: * latching. Pass false when the LRU should not be impacted, such as
0950: * during eviction and checkpointing.
0951: *
0952: * @return true if node found in tree.
0953: * If false is returned and there is the possibility that we can insert
0954: * the record into a plausible parent we must also set
0955: * - location.bin (may be null if no possible parent found)
0956: * - location.lnKey (don't need to set if no possible parent).
0957: */
0958: public boolean getParentBINForChildLN(TreeLocation location,
0959: byte[] mainKey, byte[] dupKey, LN ln,
0960: boolean splitsAllowed, boolean findDeletedEntries,
0961: boolean searchDupTree, boolean updateGeneration)
0962: throws DatabaseException {
0963:
0964: /*
0965: * Find the BIN that either points to this LN or could be its
0966: * ancestor.
0967: */
0968: IN searchResult = null;
0969: try {
0970: if (splitsAllowed) {
0971: searchResult = searchSplitsAllowed(mainKey, -1,
0972: updateGeneration);
0973: } else {
0974: searchResult = search(mainKey, SearchType.NORMAL, -1,
0975: null, updateGeneration);
0976: }
0977: location.bin = (BIN) searchResult;
0978: } catch (Exception e) {
0979: /* SR 11360 tracing. */
0980: StringBuffer msg = new StringBuffer();
0981: if (searchResult != null) {
0982: searchResult.releaseLatchIfOwner();
0983: msg.append("searchResult=" + searchResult.getClass()
0984: + " nodeId=" + searchResult.getNodeId()
0985: + " nEntries=" + searchResult.getNEntries());
0986: }
0987: throw new DatabaseException(msg.toString(), e);
0988: }
0989:
0990: if (location.bin == null) {
0991: return false;
0992: }
0993:
0994: /*
0995: * If caller wants us to consider knownDeleted entries then do an
0996: * inexact search in findEntry since that will find knownDeleted
0997: * entries. If caller doesn't want us to consider knownDeleted entries
0998: * then do an exact search in findEntry since that will not return
0999: * knownDeleted entries.
1000: */
1001: boolean exactSearch = false;
1002: boolean indicateIfExact = true;
1003: if (!findDeletedEntries) {
1004: exactSearch = true;
1005: indicateIfExact = false;
1006: }
1007: location.index = location.bin.findEntry(mainKey,
1008: indicateIfExact, exactSearch);
1009:
1010: boolean match = false;
1011: if (findDeletedEntries) {
1012: match = (location.index >= 0 && (location.index & IN.EXACT_MATCH) != 0);
1013: location.index &= ~IN.EXACT_MATCH;
1014: } else {
1015: match = (location.index >= 0);
1016: }
1017:
1018: if (match) {
1019:
1020: /*
1021: * A BIN parent was found and a slot matches the key. See if
1022: * we have to search further into what may be a dup tree.
1023: */
1024: if (!location.bin.isEntryKnownDeleted(location.index)) {
1025:
1026: /*
1027: * If this database doesn't support duplicates, no point in
1028: * incurring the potentially large cost of fetching in
1029: * the child to check for dup trees. In the future, we could
1030: * optimize further by storing state per slot as to whether
1031: * a dup tree hangs below.
1032: */
1033: if (database.getSortedDuplicates()) {
1034:
1035: Node childNode = location.bin
1036: .fetchTarget(location.index);
1037: try {
1038:
1039: /*
1040: * Is our target LN a regular record or a dup count?
1041: */
1042: if (childNode == null) {
1043: /* Child is a deleted cleaned LN. */
1044: } else if (ln.containsDuplicates()) {
1045: /* This is a duplicate count LN. */
1046: return searchDupTreeForDupCountLNParent(
1047: location, mainKey, childNode);
1048: } else {
1049:
1050: /*
1051: * This is a regular LN. If this is a dup tree,
1052: * descend and search. If not, we've found the
1053: * parent.
1054: */
1055: if (childNode.containsDuplicates()) {
1056: if (dupKey == null) {
1057:
1058: /*
1059: * We are at a dup tree but our target LN
1060: * has no dup key because it's a deleted
1061: * LN. We've encountered the case of SR
1062: * 8984 where we are searching for an LN
1063: * that was deleted before the conversion
1064: * to a duplicate tree.
1065: */
1066: return searchDupTreeByNodeId(
1067: location, childNode, ln,
1068: searchDupTree,
1069: updateGeneration);
1070: } else {
1071: return searchDupTreeForDBIN(
1072: location, dupKey,
1073: (DIN) childNode, ln,
1074: findDeletedEntries,
1075: indicateIfExact,
1076: exactSearch, splitsAllowed,
1077: updateGeneration);
1078: }
1079: }
1080: }
1081: } catch (DatabaseException e) {
1082: location.bin.releaseLatchIfOwner();
1083: throw e;
1084: }
1085: }
1086: }
1087:
1088: /* We had a match, we didn't need to search the duplicate tree. */
1089: location.childLsn = location.bin.getLsn(location.index);
1090: return true;
1091: } else {
1092: location.lnKey = mainKey;
1093: return false;
1094: }
1095: }
1096:
1097: /**
1098: * For SR [#8984]: our prospective child is a deleted LN, and
1099: * we're facing a dup tree. Alas, the deleted LN has no data, and
1100: * therefore nothing to guide the search in the dup tree. Instead,
1101: * we search by node id. This is very expensive, but this
1102: * situation is a very rare case.
1103: */
1104: private boolean searchDupTreeByNodeId(TreeLocation location,
1105: Node childNode, LN ln, boolean searchDupTree,
1106: boolean updateGeneration) throws DatabaseException {
1107:
1108: if (searchDupTree) {
1109: BIN oldBIN = location.bin;
1110: if (childNode.matchLNByNodeId(location, ln.getNodeId())) {
1111: location.index &= ~IN.EXACT_MATCH;
1112: if (oldBIN != null) {
1113: oldBIN.releaseLatch();
1114: }
1115: location.bin.latch(updateGeneration);
1116: return true;
1117: } else {
1118: return false;
1119: }
1120: } else {
1121:
1122: /*
1123: * This is called from undo() so this LN can
1124: * just be ignored.
1125: */
1126: return false;
1127: }
1128: }
1129:
1130: /**
1131: * @return true if childNode is the DIN parent of this DupCountLN
1132: */
1133: private boolean searchDupTreeForDupCountLNParent(
1134: TreeLocation location, byte[] mainKey, Node childNode)
1135: throws DatabaseException {
1136: location.lnKey = mainKey;
1137: if (childNode instanceof DIN) {
1138: DIN dupRoot = (DIN) childNode;
1139: location.childLsn = dupRoot.getDupCountLNRef().getLsn();
1140: return true;
1141: } else {
1142:
1143: /*
1144: * If we're looking for a DupCountLN but don't find a
1145: * duplicate tree, then the key now refers to a single
1146: * datum. This can happen when all dups for a key are
1147: * deleted, the compressor runs, and then a single
1148: * datum is inserted. [#10597]
1149: */
1150: return false;
1151: }
1152: }
1153:
1154: /**
1155: * Search the dup tree for the DBIN parent of this ln.
1156: */
1157: private boolean searchDupTreeForDBIN(TreeLocation location,
1158: byte[] dupKey, DIN dupRoot, LN ln,
1159: boolean findDeletedEntries, boolean indicateIfExact,
1160: boolean exactSearch, boolean splitsAllowed,
1161: boolean updateGeneration) throws DatabaseException {
1162:
1163: assert dupKey != null;
1164:
1165: dupRoot.latch();
1166:
1167: try {
1168: /* Make sure there's room for inserts. */
1169: if (maybeSplitDuplicateRoot(location.bin, location.index)) {
1170: dupRoot = (DIN) location.bin
1171: .fetchTarget(location.index);
1172: }
1173:
1174: /*
1175: * Wait until after any duplicate root splitting to unlatch the
1176: * bin.
1177: */
1178: location.bin.releaseLatch();
1179:
1180: /*
1181: * The dupKey is going to be the key that represents the LN in this
1182: * BIN parent.
1183: */
1184: location.lnKey = dupKey;
1185:
1186: /* Search the dup tree */
1187: if (splitsAllowed) {
1188: try {
1189: location.bin = (BIN) searchSubTreeSplitsAllowed(
1190: dupRoot, location.lnKey, ln.getNodeId(),
1191: updateGeneration);
1192: } catch (SplitRequiredException e) {
1193:
1194: /*
1195: * Shouldn't happen; the only caller of this method which
1196: * allows splits is from recovery, which is single
1197: * threaded.
1198: */
1199: throw new DatabaseException(e);
1200: }
1201: } else {
1202: location.bin = (BIN) searchSubTree(dupRoot,
1203: location.lnKey, SearchType.NORMAL, ln
1204: .getNodeId(), null, updateGeneration);
1205: }
1206:
1207: /* Search for LN w/exact key. */
1208: location.index = location.bin.findEntry(location.lnKey,
1209: indicateIfExact, exactSearch);
1210: boolean match;
1211: if (findDeletedEntries) {
1212: match = (location.index >= 0 && (location.index & IN.EXACT_MATCH) != 0);
1213: location.index &= ~IN.EXACT_MATCH;
1214: } else {
1215: match = (location.index >= 0);
1216: }
1217:
1218: if (match) {
1219: location.childLsn = location.bin.getLsn(location.index);
1220: return true;
1221: } else {
1222: return false;
1223: }
1224: } catch (DatabaseException e) {
1225: dupRoot.releaseLatchIfOwner();
1226: throw e;
1227: }
1228: }
1229:
1230: /**
1231: * Return a reference to the adjacent BIN.
1232: *
1233: * @param bin The BIN to find the next BIN for. This BIN is latched.
1234: * @param traverseWithinDupTree if true, only search within the dup tree
1235: * and return null when the traversal runs out of duplicates.
1236: *
1237: * @return The next BIN, or null if there are no more. The returned node
1238: * is latched and the caller must release it. If null is returned, the
1239: * argument BIN remains latched.
1240: */
1241: public BIN getNextBin(BIN bin, boolean traverseWithinDupTree)
1242: throws DatabaseException {
1243:
1244: return getNextBinInternal(traverseWithinDupTree, bin, true);
1245: }
1246:
1247: /**
1248: * Return a reference to the previous BIN.
1249: *
1250: * @param bin The BIN to find the next BIN for. This BIN is latched.
1251: * @param traverseWithinDupTree if true, only search within the dup tree
1252: * and return null when the traversal runs out of duplicates.
1253: *
1254: * @return The previous BIN, or null if there are no more. The returned
1255: * node is latched and the caller must release it. If null is returned,
1256: * the argument bin remains latched.
1257: */
1258: public BIN getPrevBin(BIN bin, boolean traverseWithinDupTree)
1259: throws DatabaseException {
1260:
1261: return getNextBinInternal(traverseWithinDupTree, bin, false);
1262: }
1263:
1264: /**
1265: * Helper routine for above two routines to iterate through BIN's.
1266: */
1267: private BIN getNextBinInternal(boolean traverseWithinDupTree,
1268: BIN bin, boolean forward) throws DatabaseException {
1269:
1270: /*
1271: * Use the right most key (for a forward progressing cursor) or the
1272: * left most key (for a backward progressing cursor) as the idkey. The
1273: * reason is that the BIN may get split while finding the next BIN so
1274: * it's not safe to take the BIN's identifierKey entry. If the BIN
1275: * gets splits, then the right (left) most key will still be on the
1276: * resultant node. The exception to this is that if there are no
1277: * entries, we just use the identifier key.
1278: */
1279: byte[] idKey = null;
1280:
1281: if (bin.getNEntries() == 0) {
1282: idKey = bin.getIdentifierKey();
1283: } else if (forward) {
1284: idKey = bin.getKey(bin.getNEntries() - 1);
1285: } else {
1286: idKey = bin.getKey(0);
1287: }
1288:
1289: IN next = bin;
1290: boolean nextIsLatched = false;
1291:
1292: assert LatchSupport.countLatchesHeld() == 1 : LatchSupport
1293: .latchesHeldToString();
1294:
1295: /*
1296: * Ascend the tree until we find a level that still has nodes to the
1297: * right (or left if !forward) of the path that we're on. If we reach
1298: * the root level, we're done. If we're searching within a duplicate
1299: * tree, stay within the tree.
1300: */
1301: IN parent = null;
1302: IN nextIN = null;
1303: boolean nextINIsLatched = false;
1304: try {
1305: while (true) {
1306:
1307: /*
1308: * Move up a level from where we are now and check to see if we
1309: * reached the top of the tree.
1310: */
1311: SearchResult result = null;
1312: if (!traverseWithinDupTree) {
1313: /* Operating on a regular tree -- get the parent. */
1314: nextIsLatched = false;
1315: result = getParentINForChildIN(next,
1316: true /* requireExactMatch */, true /* updateGeneration */);
1317: if (result.exactParentFound) {
1318: parent = result.parent;
1319: } else {
1320: /* We've reached the root of the tree. */
1321: assert (LatchSupport.countLatchesHeld() == 0) : LatchSupport
1322: .latchesHeldToString();
1323: return null;
1324: }
1325: } else {
1326: /* This is a duplicate tree, stay within the tree.*/
1327: if (next.isRoot()) {
1328: /* We've reached the top of the dup tree. */
1329: next.releaseLatch();
1330: nextIsLatched = false;
1331: return null;
1332: } else {
1333: result = getParentINForChildIN(next,
1334: true /* requireExactMatch */, true /* updateGeneration */);
1335: nextIsLatched = false;
1336: if (result.exactParentFound) {
1337: parent = result.parent;
1338: } else {
1339: return null;
1340: }
1341: }
1342: }
1343:
1344: assert (LatchSupport.countLatchesHeld() == 1) : LatchSupport
1345: .latchesHeldToString();
1346:
1347: /*
1348: * Figure out which entry we are in the parent. Add (subtract)
1349: * 1 to move to the next (previous) one and check that we're
1350: * still pointing to a valid child. Don't just use the result
1351: * of the parent.findEntry call in getParentNode, because we
1352: * want to use our explicitly chosen idKey.
1353: */
1354: int index = parent.findEntry(idKey, false, false);
1355: boolean moreEntriesThisBin = false;
1356: if (forward) {
1357: index++;
1358: if (index < parent.getNEntries()) {
1359: moreEntriesThisBin = true;
1360: }
1361: } else {
1362: if (index > 0) {
1363: moreEntriesThisBin = true;
1364: }
1365: index--;
1366: }
1367:
1368: if (moreEntriesThisBin) {
1369:
1370: /*
1371: * There are more entries to the right of the current path
1372: * in parent. Get the entry, and then descend down the
1373: * left most path to a BIN.
1374: */
1375: nextIN = (IN) parent.fetchTarget(index);
1376: nextIN.latch();
1377: nextINIsLatched = true;
1378:
1379: assert (LatchSupport.countLatchesHeld() == 2) : LatchSupport
1380: .latchesHeldToString();
1381:
1382: if (nextIN instanceof BIN) {
1383: /* We landed at a leaf (i.e. a BIN). */
1384: parent.releaseLatch();
1385: TreeWalkerStatsAccumulator treeStatsAccumulator = getTreeStatsAccumulator();
1386: if (treeStatsAccumulator != null) {
1387: nextIN
1388: .accumulateStats(treeStatsAccumulator);
1389: }
1390:
1391: return (BIN) nextIN;
1392: } else {
1393:
1394: /*
1395: * We landed at an IN. Descend down to the appropriate
1396: * leaf (i.e. BIN) node.
1397: */
1398: nextINIsLatched = false;
1399: IN ret = searchSubTree(nextIN, null,
1400: (forward ? SearchType.LEFT
1401: : SearchType.RIGHT), -1, null,
1402: true /*updateGeneration*/);
1403: parent.releaseLatch();
1404:
1405: assert LatchSupport.countLatchesHeld() == 1 : LatchSupport
1406: .latchesHeldToString();
1407:
1408: if (ret instanceof BIN) {
1409: return (BIN) ret;
1410: } else {
1411: throw new InconsistentNodeException(
1412: "subtree did not have a BIN for leaf");
1413: }
1414: }
1415: }
1416: next = parent;
1417: nextIsLatched = true;
1418: }
1419: } catch (DatabaseException e) {
1420: if (nextIsLatched) {
1421: next.releaseLatchIfOwner();
1422: nextIsLatched = false;
1423: }
1424: if (parent != null) {
1425: parent.releaseLatchIfOwner();
1426: }
1427: if (nextIN != null && nextINIsLatched) {
1428: nextIN.releaseLatchIfOwner();
1429: }
1430: throw e;
1431: }
1432: }
1433:
1434: /**
1435: * Split the root of the tree.
1436: */
1437: private void splitRoot() throws DatabaseException {
1438:
1439: /*
1440: * Create a new root IN, insert the current root IN into it, and then
1441: * call split.
1442: */
1443: EnvironmentImpl env = database.getDbEnvironment();
1444: LogManager logManager = env.getLogManager();
1445: INList inMemoryINs = env.getInMemoryINs();
1446:
1447: IN curRoot = null;
1448: curRoot = (IN) root.fetchTarget(database, null);
1449: curRoot.latch();
1450: long curRootLsn = 0;
1451: long logLsn = 0;
1452: IN newRoot = null;
1453: try {
1454:
1455: /*
1456: * Make a new root IN, giving it an id key from the previous root.
1457: */
1458: byte[] rootIdKey = curRoot.getKey(0);
1459: newRoot = new IN(database, rootIdKey,
1460: maxMainTreeEntriesPerNode, curRoot.getLevel() + 1);
1461: newRoot.latch();
1462: newRoot.setIsRoot(true);
1463: curRoot.setIsRoot(false);
1464:
1465: /*
1466: * Make the new root IN point to the old root IN. Log the old root
1467: * provisionally, because we modified it so it's not the root
1468: * anymore, then log the new root. We are guaranteed to be able to
1469: * insert entries, since we just made this root.
1470: */
1471: try {
1472: curRootLsn = curRoot.optionalLogProvisional(logManager,
1473: newRoot);
1474: boolean insertOk = newRoot
1475: .insertEntry(new ChildReference(curRoot,
1476: rootIdKey, curRootLsn));
1477: assert insertOk;
1478:
1479: logLsn = newRoot.optionalLog(logManager);
1480: } catch (DatabaseException e) {
1481: /* Something went wrong when we tried to log. */
1482: curRoot.setIsRoot(true);
1483: throw e;
1484: }
1485: inMemoryINs.add(newRoot);
1486:
1487: /*
1488: * Make the tree's root reference point to this new node. Now the
1489: * MapLN is logically dirty, but the change hasn't been logged. Be
1490: * sure to flush the MapLN if we ever evict the root.
1491: */
1492: root.setTarget(newRoot);
1493: root.updateLsnAfterOptionalLog(database, logLsn);
1494: curRoot.split(newRoot, 0, maxMainTreeEntriesPerNode);
1495: root.setLsn(newRoot.getLastFullVersion());
1496:
1497: } finally {
1498: /* FindBugs ignore possible null pointer dereference of newRoot. */
1499: newRoot.releaseLatch();
1500: curRoot.releaseLatch();
1501: }
1502: treeStats.nRootSplits++;
1503: traceSplitRoot(Level.FINE, TRACE_ROOT_SPLIT, newRoot, logLsn,
1504: curRoot, curRootLsn);
1505: }
1506:
1507: /**
1508: * Search the tree, starting at the root. Depending on search type either
1509: * search using key, or search all the way down the right or left sides.
1510: * Stop the search either when the bottom of the tree is reached, or a node
1511: * matching nid is found (see below) in which case that node's parent is
1512: * returned.
1513: *
1514: * Preemptive splitting is not done during the search.
1515: *
1516: * @param key - the key to search for, or null if searchType is LEFT or
1517: * RIGHT.
1518: *
1519: * @param searchType - The type of tree search to perform. NORMAL means
1520: * we're searching for key in the tree. LEFT/RIGHT means we're descending
1521: * down the left or right side, resp. DELETE means we're descending the
1522: * tree and will return the lowest node in the path that has > 1 entries.
1523: *
1524: * @param nid - The nodeid to search for in the tree. If found, returns
1525: * its parent. If the nodeid of the root is passed, null is returned.
1526: *
1527: * @param binBoundary - If non-null, information is returned about whether
1528: * the BIN found is the first or last BIN in the database.
1529: *
1530: * @return - the Node that matches the criteria, if any. This is the node
1531: * that is farthest down the tree with a match. Returns null if the root
1532: * is null. Node is latched (unless it's null) and must be unlatched by
1533: * the caller. Only IN's and BIN's are returned, not LN's. In a NORMAL
1534: * search, It is the caller's responsibility to do the findEntry() call on
1535: * the key and BIN to locate the entry that matches key. The return value
1536: * node is latched upon return and it is the caller's responsibility to
1537: * unlatch it.
1538: */
1539: public IN search(byte[] key, SearchType searchType, long nid,
1540: BINBoundary binBoundary, boolean updateGeneration)
1541: throws DatabaseException {
1542:
1543: IN rootIN = getRootIN(true /* updateGeneration */);
1544:
1545: if (rootIN != null) {
1546: return searchSubTree(rootIN, key, searchType, nid,
1547: binBoundary, updateGeneration);
1548: } else {
1549: return null;
1550: }
1551: }
1552:
1553: /**
1554: * Do a key based search, permitting pre-emptive splits. Returns the
1555: * target node's parent.
1556: */
1557: public IN searchSplitsAllowed(byte[] key, long nid,
1558: boolean updateGeneration) throws DatabaseException {
1559:
1560: IN insertTarget = null;
1561: while (insertTarget == null) {
1562: rootLatch.acquireShared();
1563: boolean rootLatched = true;
1564: boolean rootLatchedExclusive = false;
1565: boolean rootINLatched = false;
1566: boolean success = false;
1567: IN rootIN = null;
1568: try {
1569: while (true) {
1570: if (rootExists()) {
1571: rootIN = (IN) root.fetchTarget(database, null);
1572:
1573: /* Check if root needs splitting. */
1574: if (rootIN.needsSplitting()) {
1575: if (!rootLatchedExclusive) {
1576: rootIN = null;
1577: rootLatch.release();
1578: rootLatch.acquireExclusive();
1579: rootLatchedExclusive = true;
1580: continue;
1581: }
1582: splitRoot();
1583:
1584: /*
1585: * We can't hold any latches while we lock. If the
1586: * root splits again between latch release and
1587: * DbTree.db lock, no problem. The latest root
1588: * will still get written out.
1589: */
1590: rootLatch.release();
1591: rootLatched = false;
1592: EnvironmentImpl env = database
1593: .getDbEnvironment();
1594: env.getDbMapTree().optionalModifyDbRoot(
1595: database);
1596: rootLatched = true;
1597: rootLatch.acquireExclusive();
1598: rootIN = (IN) root.fetchTarget(database,
1599: null);
1600: }
1601: rootIN.latch();
1602: rootINLatched = true;
1603: }
1604: break;
1605: }
1606: success = true;
1607: } finally {
1608: if (!success && rootINLatched) {
1609: rootIN.releaseLatch();
1610: }
1611: if (rootLatched) {
1612: rootLatch.release();
1613: }
1614: }
1615:
1616: /* Don't loop forever if the root is null. [#13897] */
1617: if (rootIN == null) {
1618: break;
1619: }
1620:
1621: try {
1622: success = false;
1623: insertTarget = searchSubTreeSplitsAllowed(rootIN, key,
1624: nid, updateGeneration);
1625: success = true;
1626: } catch (SplitRequiredException e) {
1627:
1628: success = true;
1629:
1630: /*
1631: * The last slot in the root was used at the point when this
1632: * thread released the rootIN latch in order to force splits.
1633: * Retry. SR [#11147].
1634: */
1635: continue;
1636: } finally {
1637: if (!success) {
1638: rootIN.releaseLatchIfOwner();
1639: if (insertTarget != null) {
1640: insertTarget.releaseLatchIfOwner();
1641: }
1642: }
1643: }
1644: }
1645:
1646: return insertTarget;
1647: }
1648:
1649: /*
1650: * Singleton class to indicate that root IN needs to be relatched for
1651: * exclusive access due to a fetch occurring.
1652: */
1653: private static class RelatchRequiredException extends
1654: DatabaseException {
1655: public synchronized Throwable fillInStackTrace() {
1656: return this ;
1657: }
1658: }
1659:
1660: private static RelatchRequiredException relatchRequiredException = new RelatchRequiredException();
1661:
1662: /**
1663: * Wrapper for searchSubTreeInternal that does a restart if a
1664: * RelatchRequiredException is thrown (i.e. a relatch of the root is
1665: * needed.
1666: */
1667: public IN searchSubTree(IN parent, byte[] key,
1668: SearchType searchType, long nid, BINBoundary binBoundary,
1669: boolean updateGeneration) throws DatabaseException {
1670:
1671: /*
1672: * Max of two iterations required. First is root latched shared, and
1673: * second is root latched exclusive.
1674: */
1675: for (int i = 0; i < 2; i++) {
1676: try {
1677: return searchSubTreeInternal(parent, key, searchType,
1678: nid, binBoundary, updateGeneration);
1679: } catch (RelatchRequiredException RRE) {
1680: parent = getRootINLatchedExclusive(updateGeneration);
1681: }
1682: }
1683:
1684: throw new DatabaseException(
1685: "searchSubTreeInternal should have completed in two tries");
1686: }
1687:
1688: /**
1689: * Searches a portion of the tree starting at parent using key. If during
1690: * the search a node matching a non-null nid argument is found, its parent
1691: * is returned. If searchType is NORMAL, then key must be supplied to
1692: * guide the search. If searchType is LEFT (or RIGHT), then the tree is
1693: * searched down the left (or right) side to find the first (or last) leaf,
1694: * respectively.
1695: * <p>
1696: * Enters with parent latched, assuming it's not null. Exits with the
1697: * return value latched, assuming it's not null.
1698: * <p>
1699: * @param parent - the root of the subtree to start the search at. This
1700: * node should be latched by the caller and will be unlatched prior to
1701: * return.
1702: *
1703: * @param key - the key to search for, unless searchType is LEFT or RIGHT
1704: *
1705: * @param searchType - NORMAL means search using key and, optionally, nid.
1706: * LEFT means find the first (leftmost) leaf
1707: * RIGHT means find the last (rightmost) leaf
1708: *
1709: * @param nid - The nodeid to search for in the tree. If found, returns
1710: * its parent. If the nodeid of the root is passed, null is returned.
1711: * Pass -1 if no nodeid based search is desired.
1712: *
1713: * @return - the node matching the argument criteria, or null. The node is
1714: * latched and must be unlatched by the caller. The parent argument and
1715: * any other nodes that are latched during the search are unlatched prior
1716: * to return.
1717: *
1718: * @throws RelatchRequiredException if the root node (parent) must be
1719: * relatched exclusively because a null target was encountered (i.e. a
1720: * fetch must be performed on parent's child and the parent is latched
1721: * shared.
1722: */
1723: public IN searchSubTreeInternal(IN parent, byte[] key,
1724: SearchType searchType, long nid, BINBoundary binBoundary,
1725: boolean updateGeneration) throws DatabaseException {
1726:
1727: /* Return null if we're passed a null arg. */
1728: if (parent == null) {
1729: return null;
1730: }
1731:
1732: if ((searchType == SearchType.LEFT || searchType == SearchType.RIGHT)
1733: && key != null) {
1734:
1735: /*
1736: * If caller is asking for a right or left search, they shouldn't
1737: * be passing us a key.
1738: */
1739: throw new IllegalArgumentException(
1740: "searchSubTree passed key and left/right search");
1741: }
1742:
1743: assert parent.isLatchOwnerForRead();
1744:
1745: if (parent.getNodeId() == nid) {
1746: parent.releaseLatch();
1747: return null;
1748: }
1749:
1750: if (binBoundary != null) {
1751: binBoundary.isLastBin = true;
1752: binBoundary.isFirstBin = true;
1753: }
1754:
1755: int index;
1756: IN child = null;
1757: IN grandParent = null;
1758: boolean childIsLatched = false;
1759: boolean grandParentIsLatched = false;
1760: boolean maintainGrandParentLatches = !parent
1761: .isLatchOwnerForWrite();
1762:
1763: TreeWalkerStatsAccumulator treeStatsAccumulator = getTreeStatsAccumulator();
1764:
1765: try {
1766: do {
1767: if (treeStatsAccumulator != null) {
1768: parent.accumulateStats(treeStatsAccumulator);
1769: }
1770:
1771: if (parent.getNEntries() == 0) {
1772: /* No more children, can't descend anymore. */
1773: return parent;
1774: } else if (searchType == SearchType.NORMAL) {
1775: /* Look for the entry matching key in the current node. */
1776: index = parent.findEntry(key, false, false);
1777: } else if (searchType == SearchType.LEFT) {
1778: /* Left search, always take the 0th entry. */
1779: index = 0;
1780: } else if (searchType == SearchType.RIGHT) {
1781: /* Right search, always take the highest entry. */
1782: index = parent.getNEntries() - 1;
1783: } else {
1784: throw new IllegalArgumentException(
1785: "Invalid value of searchType: "
1786: + searchType);
1787: }
1788:
1789: assert index >= 0;
1790:
1791: if (binBoundary != null) {
1792: if (index != parent.getNEntries() - 1) {
1793: binBoundary.isLastBin = false;
1794: }
1795: if (index != 0) {
1796: binBoundary.isFirstBin = false;
1797: }
1798: }
1799:
1800: /*
1801: * Get the child node. If target is null, and we don't have
1802: * parent latched exclusively, then we need to relatch this
1803: * parent so that we can fill in the target. Fetching a target
1804: * is a write to a node so it must be exclusively latched.
1805: * Once we have the parent relatched exclusively, then we can
1806: * release the grand parent.
1807: */
1808: if (maintainGrandParentLatches
1809: && parent.getTarget(index) == null
1810: && !parent.isAlwaysLatchedExclusively()) {
1811:
1812: if (grandParent == null) {
1813:
1814: /*
1815: * grandParent is null which implies parent is the root
1816: * so throw RelatchRequiredException.
1817: */
1818: throw relatchRequiredException;
1819: } else {
1820: /* Release parent shared and relatch exclusive. */
1821: parent.releaseLatch();
1822: parent.latch();
1823: }
1824:
1825: /*
1826: * Once parent has been re-latched exclusive we can release
1827: * grandParent now (sooner), rather than after the
1828: * fetchTarget (later).
1829: */
1830: if (grandParent != null) {
1831: grandParent.releaseLatch();
1832: grandParentIsLatched = false;
1833: grandParent = null;
1834: }
1835: }
1836: child = (IN) parent.fetchTarget(index);
1837:
1838: /*
1839: * We know we're done with grandParent for sure, so release
1840: * now.
1841: */
1842: if (grandParent != null) {
1843: grandParent.releaseLatch();
1844: grandParentIsLatched = false;
1845: }
1846:
1847: /* See if we're even using shared latches. */
1848: if (maintainGrandParentLatches) {
1849: child.latchShared(updateGeneration);
1850: } else {
1851: child.latch(updateGeneration);
1852: }
1853: childIsLatched = true;
1854:
1855: if (treeStatsAccumulator != null) {
1856: child.accumulateStats(treeStatsAccumulator);
1857: }
1858:
1859: /*
1860: * If this child matches nid, then stop the search and return
1861: * the parent.
1862: */
1863: if (child.getNodeId() == nid) {
1864: child.releaseLatch();
1865: childIsLatched = false;
1866: return parent;
1867: }
1868:
1869: /* Continue down a level */
1870: if (maintainGrandParentLatches) {
1871: grandParent = parent;
1872: grandParentIsLatched = true;
1873: } else {
1874: parent.releaseLatch();
1875: }
1876: parent = child;
1877: } while (!(parent instanceof BIN));
1878:
1879: return child;
1880: } catch (Exception t) {
1881:
1882: /*
1883: * In [#14903] we encountered a latch exception below and the
1884: * original exception t was lost. Print the stack trace and
1885: * rethrow the original exception if this happens again, to get
1886: * more information about the problem.
1887: */
1888: try {
1889: if (child != null && childIsLatched) {
1890: child.releaseLatchIfOwner();
1891: }
1892:
1893: if (parent != child) {
1894: parent.releaseLatchIfOwner();
1895: }
1896: } catch (Exception t2) {
1897: t2.printStackTrace();
1898: }
1899:
1900: if (t instanceof DatabaseException) {
1901: /* don't re-wrap a DatabaseException; we may need its type. */
1902: throw (DatabaseException) t;
1903: } else {
1904: throw new DatabaseException(t);
1905: }
1906: } finally {
1907: if (grandParent != null && grandParentIsLatched) {
1908: grandParent.releaseLatch();
1909: grandParentIsLatched = false;
1910: }
1911: }
1912: }
1913:
1914: /**
1915: * Search down the tree using a key, but instead of returning the BIN that
1916: * houses that key, find the point where we can detach a deletable
1917: * subtree. A deletable subtree is a branch where each IN has one child,
1918: * and the bottom BIN has no entries and no resident cursors. That point
1919: * can be found by saving a pointer to the lowest node in the path with
1920: * more than one entry.
1921: *
1922: * INa
1923: * / \
1924: * INb INc
1925: * | |
1926: * INd ..
1927: * / \
1928: * INe ..
1929: * |
1930: * BINx (suspected of being empty)
1931: *
1932: * In this case, we'd like to prune off the subtree headed by INe. INd
1933: * is the parent of this deletable subtree. As we descend, we must keep
1934: * latches for all the nodes that will be logged. In this case, we
1935: * will need to keep INa, INb and INd latched when we return from this
1936: * method.
1937: *
1938: * The method returns a list of parent/child/index structures. In this
1939: * example, the list will hold:
1940: * INa/INb/index
1941: * INb/INd/index
1942: * INd/INe/index
1943: * Every node is latched, and every node except for the bottom most child
1944: * (INe) must be logged.
1945: */
1946: public void searchDeletableSubTree(IN parent, byte[] key,
1947: ArrayList nodeLadder) throws DatabaseException,
1948: NodeNotEmptyException, CursorsExistException {
1949:
1950: assert (parent != null);
1951: assert (key != null);
1952: assert parent.isLatchOwnerForWrite();
1953:
1954: int index;
1955: IN child = null;
1956:
1957: /* Save the lowest IN in the path that has multiple entries. */
1958: IN lowestMultipleEntryIN = null;
1959:
1960: do {
1961: if (parent.getNEntries() == 0) {
1962: break;
1963: }
1964:
1965: /* Remember if this is the lowest multiple point. */
1966: if (parent.getNEntries() > 1) {
1967: lowestMultipleEntryIN = parent;
1968: }
1969:
1970: index = parent.findEntry(key, false, false);
1971: assert index >= 0;
1972:
1973: /* Get the child node that matches. */
1974: child = (IN) parent.fetchTarget(index);
1975: child.latch(false);
1976: nodeLadder.add(new SplitInfo(parent, child, index));
1977:
1978: /* Continue down a level */
1979: parent = child;
1980: } while (!(parent instanceof BIN));
1981:
1982: /*
1983: * See if there is a reason we can't delete this BIN -- i.e.
1984: * new items have been inserted, or a cursor exists on it.
1985: */
1986: if ((child != null) && (child instanceof BIN)) {
1987: if (child.getNEntries() != 0) {
1988: throw NodeNotEmptyException.NODE_NOT_EMPTY;
1989: }
1990:
1991: /*
1992: * This case can happen if we are keeping a BIN on an empty
1993: * cursor as we traverse.
1994: */
1995: if (((BIN) child).nCursors() > 0) {
1996: throw CursorsExistException.CURSORS_EXIST;
1997: }
1998: }
1999:
2000: if (lowestMultipleEntryIN != null) {
2001:
2002: /*
2003: * Release all nodes up to the pair that holds the detach
2004: * point. We won't be needing those nodes, since they'll be
2005: * pruned and won't need to be updated.
2006: */
2007: ListIterator iter = nodeLadder.listIterator(nodeLadder
2008: .size());
2009: while (iter.hasPrevious()) {
2010: SplitInfo info = (SplitInfo) iter.previous();
2011: if (info.parent == lowestMultipleEntryIN) {
2012: break;
2013: } else {
2014: info.child.releaseLatch();
2015: iter.remove();
2016: }
2017: }
2018: } else {
2019:
2020: /*
2021: * We actually have to prune off the entire tree. Release
2022: * all latches, and clear the node ladder.
2023: */
2024: releaseNodeLadderLatches(nodeLadder);
2025: nodeLadder.clear();
2026: }
2027: }
2028:
2029: /**
2030: * Search the portion of the tree starting at the parent, permitting
2031: * preemptive splits.
2032: */
2033: private IN searchSubTreeSplitsAllowed(IN parent, byte[] key,
2034: long nid, boolean updateGeneration)
2035: throws DatabaseException, SplitRequiredException {
2036:
2037: if (parent != null) {
2038:
2039: /*
2040: * Search downward until we hit a node that needs a split. In
2041: * that case, retreat to the top of the tree and force splits
2042: * downward.
2043: */
2044: while (true) {
2045: try {
2046: return searchSubTreeUntilSplit(parent, key, nid,
2047: updateGeneration);
2048: } catch (SplitRequiredException e) {
2049: /* SR [#11144]*/
2050: if (waitHook != null) {
2051: waitHook.doHook();
2052: }
2053:
2054: /*
2055: * ForceSplit may itself throw SplitRequiredException if it
2056: * finds that the parent doesn't have room to hold an extra
2057: * entry. Allow the exception to propagate up to a place
2058: * where it's safe to split the parent. We do this rather
2059: * than
2060: */
2061: forceSplit(parent, key);
2062: }
2063: }
2064: } else {
2065: return null;
2066: }
2067: }
2068:
2069: /**
2070: * Search the subtree, but throw an exception when we see a node
2071: * that has to be split.
2072: */
2073: private IN searchSubTreeUntilSplit(IN parent, byte[] key, long nid,
2074: boolean updateGeneration) throws DatabaseException,
2075: SplitRequiredException {
2076:
2077: /* Return null if we're passed a null arg. */
2078: if (parent == null) {
2079: return null;
2080: }
2081:
2082: assert parent.isLatchOwnerForWrite();
2083:
2084: if (parent.getNodeId() == nid) {
2085: parent.releaseLatch();
2086: return null;
2087: }
2088:
2089: int index;
2090: IN child = null;
2091: boolean childIsLatched = false;
2092: boolean success = false;
2093:
2094: try {
2095: do {
2096: if (parent.getNEntries() == 0) {
2097: /* No more children, can't descend anymore. */
2098: success = true;
2099: return parent;
2100: } else {
2101: /* Look for the entry matching key in the current node. */
2102: index = parent.findEntry(key, false, false);
2103: }
2104:
2105: assert index >= 0;
2106:
2107: /* Get the child node that matches. */
2108: child = (IN) parent.fetchTarget(index);
2109: child.latch(updateGeneration);
2110: childIsLatched = true;
2111:
2112: /* Throw if we need to split. */
2113: if (child.needsSplitting()) {
2114: child.releaseLatch();
2115: childIsLatched = false;
2116: parent.releaseLatch();
2117: success = true;
2118: throw splitRequiredException;
2119: }
2120:
2121: /*
2122: * If this child matches nid, then stop the search and return
2123: * the parent.
2124: */
2125: if (child.getNodeId() == nid) {
2126: child.releaseLatch();
2127: childIsLatched = false;
2128: success = true;
2129: return parent;
2130: }
2131:
2132: /* Continue down a level */
2133: parent.releaseLatch();
2134: parent = child;
2135: } while (!(parent instanceof BIN));
2136:
2137: success = true;
2138: return parent;
2139: } finally {
2140: if (!success) {
2141: if (child != null && childIsLatched) {
2142: child.releaseLatchIfOwner();
2143: }
2144: if (parent != child) {
2145: parent.releaseLatchIfOwner();
2146: }
2147: }
2148: }
2149: }
2150:
2151: /**
2152: * Do pre-emptive splitting in the subtree topped by the "parent" node.
2153: * Search down the tree until we get to the BIN level, and split any nodes
2154: * that fit the splittable requirement.
2155: *
2156: * Note that more than one node in the path may be splittable. For example,
2157: * a tree might have a level2 IN and a BIN that are both splittable, and
2158: * would be encountered by the same insert operation.
2159: */
2160: private void forceSplit(IN parent, byte[] key)
2161: throws DatabaseException, SplitRequiredException {
2162:
2163: ArrayList nodeLadder = new ArrayList();
2164:
2165: boolean allLeftSideDescent = true;
2166: boolean allRightSideDescent = true;
2167: int index;
2168: IN child = null;
2169: IN originalParent = parent;
2170: ListIterator iter = null;
2171:
2172: boolean isRootLatched = false;
2173: boolean success = false;
2174: try {
2175:
2176: /*
2177: * Latch the root in order to update the root LSN when we're done.
2178: * Latch order must be: root, root IN. We'll leave this method
2179: * with the original parent latched.
2180: */
2181: if (originalParent.isDbRoot()) {
2182: rootLatch.acquireExclusive();
2183: isRootLatched = true;
2184: }
2185: originalParent.latch();
2186:
2187: /*
2188: * Another thread may have crept in and
2189: * - used the last free slot in the parent, making it impossible
2190: * to correctly progagate the split.
2191: * - actually split the root, in which case we may be looking at
2192: * the wrong subtree for this search.
2193: * If so, throw and retry from above. SR [#11144]
2194: */
2195: if (originalParent.needsSplitting()
2196: || !originalParent.isRoot()) {
2197: throw splitRequiredException;
2198: }
2199:
2200: /*
2201: * Search downward to the BIN level, saving the information
2202: * needed to do a split if necessary.
2203: */
2204: do {
2205: if (parent.getNEntries() == 0) {
2206: /* No more children, can't descend anymore. */
2207: break;
2208: } else {
2209: /* Look for the entry matching key in the current node. */
2210: index = parent.findEntry(key, false, false);
2211: if (index != 0) {
2212: allLeftSideDescent = false;
2213: }
2214: if (index != (parent.getNEntries() - 1)) {
2215: allRightSideDescent = false;
2216: }
2217: }
2218:
2219: assert index >= 0;
2220:
2221: /*
2222: * Get the child node that matches. We only need to work on
2223: * nodes in residence.
2224: */
2225: child = (IN) parent.getTarget(index);
2226: if (child == null) {
2227: break;
2228: } else {
2229: child.latch();
2230: nodeLadder.add(new SplitInfo(parent, child, index));
2231: }
2232:
2233: /* Continue down a level */
2234: parent = child;
2235: } while (!(parent instanceof BIN));
2236:
2237: boolean startedSplits = false;
2238: LogManager logManager = database.getDbEnvironment()
2239: .getLogManager();
2240:
2241: /*
2242: * Process the accumulated nodes from the bottom up. Split each
2243: * node if required. If the node should not split, we check if
2244: * there have been any splits on the ladder yet. If there are none,
2245: * we merely release the node, since there is no update. If splits
2246: * have started, we need to propagate new LSNs upward, so we log
2247: * the node and update its parent.
2248: *
2249: * Start this iterator at the end of the list.
2250: */
2251: iter = nodeLadder.listIterator(nodeLadder.size());
2252: long lastParentForSplit = -1;
2253: while (iter.hasPrevious()) {
2254: SplitInfo info = (SplitInfo) iter.previous();
2255: child = info.child;
2256: parent = info.parent;
2257: index = info.index;
2258:
2259: /* Opportunistically split the node if it is full. */
2260: if (child.needsSplitting()) {
2261: int maxEntriesPerNode = (child.containsDuplicates() ? maxDupTreeEntriesPerNode
2262: : maxMainTreeEntriesPerNode);
2263: if (allLeftSideDescent || allRightSideDescent) {
2264: child.splitSpecial(parent, index,
2265: maxEntriesPerNode, key,
2266: allLeftSideDescent);
2267: } else {
2268: child.split(parent, index, maxEntriesPerNode);
2269: }
2270: lastParentForSplit = parent.getNodeId();
2271: startedSplits = true;
2272:
2273: /*
2274: * If the DB root IN was logged, update the DB tree's child
2275: * reference. Now the MapLN is logically dirty, but the
2276: * change hasn't been logged. Set the rootIN to be dirty
2277: * again, to force flushing the rootIN and mapLN in the
2278: * next checkpoint. Be sure to flush the MapLN
2279: * if we ever evict the root.
2280: */
2281: if (parent.isDbRoot()) {
2282: assert isRootLatched;
2283: root.setLsn(parent.getLastFullVersion());
2284: parent.setDirty(true);
2285: }
2286: } else {
2287: if (startedSplits) {
2288: long newLsn = 0;
2289:
2290: /*
2291: * If this child was the parent of a split, it's
2292: * already logged by the split call. We just need to
2293: * propagate the logging upwards. If this child is just
2294: * a link in the chain upwards, log it.
2295: */
2296: if (lastParentForSplit == child.getNodeId()) {
2297: newLsn = child.getLastFullVersion();
2298: } else {
2299: newLsn = child.optionalLog(logManager);
2300: }
2301: parent.updateEntry(index, newLsn);
2302: }
2303: }
2304: child.releaseLatch();
2305: child = null;
2306: iter.remove();
2307: }
2308:
2309: success = true;
2310: } finally {
2311:
2312: if (!success) {
2313: if (child != null) {
2314: child.releaseLatchIfOwner();
2315: }
2316: originalParent.releaseLatchIfOwner();
2317: }
2318:
2319: /*
2320: * Unlatch any remaining children. There should only be remainders
2321: * in the event of an exception.
2322: */
2323: if (nodeLadder.size() > 0) {
2324: iter = nodeLadder.listIterator(nodeLadder.size());
2325: while (iter.hasPrevious()) {
2326: SplitInfo info = (SplitInfo) iter.previous();
2327: info.child.releaseLatchIfOwner();
2328: }
2329: }
2330:
2331: if (isRootLatched) {
2332: rootLatch.release();
2333: }
2334: }
2335: }
2336:
2337: /**
2338: * Helper to obtain the root IN with shared root latching. Optionally
2339: * updates the generation of the root when latching it.
2340: */
2341: public IN getRootIN(boolean updateGeneration)
2342: throws DatabaseException {
2343:
2344: return getRootINInternal(updateGeneration, false);
2345: }
2346:
2347: /**
2348: * Helper to obtain the root IN with exclusive root latching. Optionally
2349: * updates the generation of the root when latching it.
2350: */
2351: public IN getRootINLatchedExclusive(boolean updateGeneration)
2352: throws DatabaseException {
2353:
2354: return getRootINInternal(updateGeneration, true);
2355: }
2356:
2357: private IN getRootINInternal(boolean updateGeneration,
2358: boolean exclusive) throws DatabaseException {
2359:
2360: rootLatch.acquireShared();
2361: IN rootIN = null;
2362: try {
2363: if (rootExists()) {
2364: rootIN = (IN) root.fetchTarget(database, null);
2365: if (exclusive) {
2366: rootIN.latch(updateGeneration);
2367: } else {
2368: rootIN.latchShared(updateGeneration);
2369: }
2370: }
2371: return rootIN;
2372: } finally {
2373: rootLatch.release();
2374: }
2375: }
2376:
2377: /**
2378: * Inserts a new LN into the tree.
2379: * @param ln The LN to insert into the tree.
2380: * @param key Key value for the node
2381: * @param allowDuplicates whether to allow duplicates to be inserted
2382: * @param cursor the cursor to update to point to the newly inserted
2383: * key/data pair, or null if no cursor should be updated.
2384: * @return true if LN was inserted, false if it was a duplicate
2385: * duplicate or if an attempt was made to insert a duplicate when
2386: * allowDuplicates was false.
2387: */
2388: public boolean insert(LN ln, byte[] key, boolean allowDuplicates,
2389: CursorImpl cursor, LockResult lnLock)
2390: throws DatabaseException {
2391:
2392: validateInsertArgs(allowDuplicates);
2393:
2394: EnvironmentImpl env = database.getDbEnvironment();
2395: LogManager logManager = env.getLogManager();
2396: INList inMemoryINs = env.getInMemoryINs();
2397:
2398: /* Find and latch the relevant BIN. */
2399: BIN bin = null;
2400: try {
2401: bin = findBinForInsert(key, logManager, inMemoryINs, cursor);
2402: assert bin.isLatchOwnerForWrite();
2403:
2404: /* Make a child reference as a candidate for insertion. */
2405: ChildReference newLNRef = new ChildReference(ln, key,
2406: DbLsn.NULL_LSN);
2407:
2408: /*
2409: * If we're doing a put that is not a putCurrent, then the cursor
2410: * passed in may not be pointing to BIN (it was set to the BIN that
2411: * the search landed on which may be different than BIN). Set the
2412: * BIN correctly here so that adjustCursorsForInsert doesn't blow
2413: * an assertion. We'll finish the job by setting the index below.
2414: */
2415: cursor.setBIN(bin);
2416:
2417: int index = bin.insertEntry1(newLNRef);
2418: if ((index & IN.INSERT_SUCCESS) != 0) {
2419:
2420: /*
2421: * Update the cursor to point to the entry that has been
2422: * successfully inserted.
2423: */
2424: index &= ~IN.INSERT_SUCCESS;
2425: cursor.updateBin(bin, index);
2426:
2427: /* Log the new LN. */
2428: long newLsn = DbLsn.NULL_LSN;
2429:
2430: try {
2431: newLsn = ln.optionalLogUpdateMemUsage(database,
2432: key, DbLsn.NULL_LSN, cursor.getLocker(),
2433: bin);
2434: } finally {
2435: if ((newLsn == DbLsn.NULL_LSN)
2436: && !database.isDeferredWrite()) {
2437:
2438: /*
2439: * Possible buffer overflow, out-of-memory, or I/O
2440: * exception during logging. The BIN entry will
2441: * contain a NULL_LSN. To prevent an exception during
2442: * a fetch, we set the KnownDeleted flag. We do not
2443: * call BIN.deleteEntry because cursors will not be
2444: * adjusted. We do not add this entry to the
2445: * compressor queue to avoid complexity (this is rare).
2446: * [13126, 12605, 11271]
2447: */
2448: bin.setKnownDeleted(index);
2449: }
2450: }
2451: lnLock.setAbortLsn(DbLsn.NULL_LSN, true, true);
2452: bin.updateEntry(index, newLsn);
2453:
2454: traceInsert(Level.FINER, env, bin, ln, newLsn, index);
2455: return true;
2456: } else {
2457:
2458: /*
2459: * Entry may have been a duplicate. Insertion was not
2460: * successful.
2461: */
2462: index &= ~IN.EXACT_MATCH;
2463: cursor.updateBin(bin, index);
2464:
2465: /*
2466: * The key in the BIN slot and the key of the new LN may be
2467: * non-identical but compare as equal by the btree comparator.
2468: * This is disallowed for databases with duplicates configured.
2469: * [#15704]
2470: */
2471: if (database.getSortedDuplicates()
2472: && database.getBtreeComparator() != null
2473: && !Arrays.equals(key, bin.getKey(index))) {
2474: throw new IllegalArgumentException(
2475: "Custom Btree comparator matches two non-identical "
2476: + "keys in a Database with duplicates configured");
2477: }
2478:
2479: LN currentLN = null;
2480: boolean isDup = false;
2481: Node n = bin.fetchTarget(index);
2482: if (n == null || n instanceof LN) {
2483: currentLN = (LN) n;
2484: } else {
2485: isDup = true;
2486: }
2487:
2488: /* If an LN is present, lock it and check deleted-ness. */
2489: boolean isDeleted = false;
2490: LockResult currentLock = null;
2491:
2492: if (!isDup) {
2493: if (currentLN == null) {
2494: /* The LN was cleaned. */
2495: isDeleted = true;
2496: } else {
2497: currentLock = cursor.lockLNDeletedAllowed(
2498: currentLN, LockType.WRITE);
2499: currentLN = currentLock.getLN();
2500: /* The BIN/index may have changed while locking. */
2501: bin = cursor.getBIN();
2502: index = cursor.getIndex();
2503: if (cursor.getDupBIN() != null) {
2504:
2505: /*
2506: * A dup tree appeared during locking. We will
2507: * position to a different dup tree entry later in
2508: * insertDuplicate, so we must remove the cursor
2509: * from this dup tree entry. This is a rare case
2510: * so performance is not an issue.
2511: */
2512: cursor
2513: .clearDupBIN(true /*alreadyLatched*/);
2514: isDup = true;
2515: } else if (bin.isEntryKnownDeleted(index)
2516: || currentLN == null
2517: || currentLN.isDeleted()) {
2518: /* The current LN is deleted/cleaned. */
2519: isDeleted = true;
2520: }
2521: }
2522: }
2523:
2524: if (isDeleted) {
2525:
2526: /*
2527: * Set the abort LSN to that of the lock held on the
2528: * current LN, if the current LN was previously locked by
2529: * this txn. This is needed when we change the node ID of
2530: * this slot.
2531: *
2532: * If reusing a slot with a deleted LN deleted in a prior
2533: * transaction (the LockGrantType is NEW or UPGRADE),
2534: * always set abortKnownDeleted=true. It may be that the
2535: * existing slot is PENDING_DELETED, but we restore to
2536: * KNOWN_DELETED in the event of an abort.
2537: */
2538: long abortLsn = bin.getLsn(index);
2539: boolean abortKnownDeleted = true;
2540: if (currentLN != null
2541: && currentLock.getLockGrant() == LockGrantType.EXISTING) {
2542: long nodeId = currentLN.getNodeId();
2543: Locker locker = cursor.getLocker();
2544: WriteLockInfo info = locker
2545: .getWriteLockInfo(nodeId);
2546: abortLsn = info.getAbortLsn();
2547: abortKnownDeleted = info.getAbortKnownDeleted();
2548: }
2549: lnLock.setAbortLsn(abortLsn, abortKnownDeleted);
2550:
2551: /*
2552: * Current entry is a deleted entry. Replace it with LN.
2553: * Pass NULL_LSN for the oldLsn parameter of the log()
2554: * method because the old LN was counted obsolete when it
2555: * was deleted.
2556: */
2557: long newLsn = ln.optionalLog(env, database, key,
2558: DbLsn.NULL_LSN, 0, cursor.getLocker());
2559:
2560: /*
2561: * When reusing a slot, the key is replaced in the BIN
2562: * slot. This ensures that the correct key value is used
2563: * when the new key is non-identical to the key in the slot
2564: * but is considered equal by the btree comparator.
2565: * [#15704]
2566: */
2567: bin.updateEntry(index, ln, newLsn, key);
2568: bin.clearKnownDeleted(index);
2569: bin.clearPendingDeleted(index);
2570:
2571: traceInsert(Level.FINER, env, bin, ln, newLsn,
2572: index);
2573: return true;
2574: } else {
2575:
2576: /*
2577: * Attempt to insert a duplicate in an exception dup tree
2578: * or create a dup tree if none exists.
2579: */
2580: return insertDuplicate(key, bin, ln, logManager,
2581: inMemoryINs, cursor, lnLock,
2582: allowDuplicates);
2583: }
2584: }
2585: } finally {
2586: cursor.releaseBIN();
2587: }
2588: }
2589:
2590: /**
2591: * Attempts to insert a duplicate at the current cursor BIN position. If
2592: * an existing dup tree exists, insert into it; otherwise, create a new
2593: * dup tree and place the new LN and the existing LN into it. If the
2594: * current BIN entry contains an LN, the caller guarantees that it is not
2595: * deleted.
2596: *
2597: * @return true if duplicate inserted successfully, false if it was a
2598: * duplicate duplicate, false if a there is an existing LN and
2599: * allowDuplicates is false.
2600: */
2601: private boolean insertDuplicate(byte[] key, BIN bin, LN newLN,
2602: LogManager logManager, INList inMemoryINs,
2603: CursorImpl cursor, LockResult lnLock,
2604: boolean allowDuplicates) throws DatabaseException {
2605:
2606: EnvironmentImpl env = database.getDbEnvironment();
2607: int index = cursor.getIndex();
2608: boolean successfulInsert = false;
2609:
2610: DIN dupRoot = null;
2611: Node n = bin.fetchTarget(index);
2612: long binNid = bin.getNodeId();
2613:
2614: if (n instanceof DIN) {
2615: DBIN dupBin = null;
2616:
2617: /*
2618: * A duplicate tree exists. Find the relevant DBIN and insert the
2619: * new entry into it.
2620: */
2621: try {
2622: dupRoot = (DIN) n;
2623: dupRoot.latch();
2624:
2625: /* Lock the DupCountLN before logging any LNs. */
2626: LockResult dclLockResult = cursor.lockDupCountLN(
2627: dupRoot, LockType.WRITE);
2628: /* The BIN/index may have changed during locking. */
2629: bin = cursor.getBIN();
2630: index = cursor.getIndex();
2631:
2632: /*
2633: * Do not proceed if duplicates are not allowed and there are
2634: * one or more duplicates already present. Note that if the
2635: * dup count is zero, we allow the insert.
2636: */
2637: if (!allowDuplicates) {
2638: DupCountLN dcl = (DupCountLN) dclLockResult.getLN();
2639: if (dcl.getDupCount() > 0) {
2640: return false;
2641: }
2642: }
2643:
2644: /*
2645: * Split the dup root if necessary. The dup root may have
2646: * changed during locking above or by the split, so refetch it.
2647: * In either case it will be latched.
2648: */
2649: maybeSplitDuplicateRoot(bin, index);
2650: dupRoot = (DIN) bin.fetchTarget(index);
2651:
2652: /*
2653: * Search the duplicate tree for the right place to insert this
2654: * new record. Releases the latch on duplicateRoot. If the
2655: * duplicateRoot got logged as a result of some splitting,
2656: * update the BIN's LSN information. The SortedLSNTreeWalker
2657: * relies on accurate LSNs in the in-memory tree.
2658: */
2659: byte[] newLNKey = newLN.getData();
2660: long previousLsn = dupRoot.getLastFullVersion();
2661: try {
2662: dupBin = (DBIN) searchSubTreeSplitsAllowed(dupRoot,
2663: newLNKey, -1, true /*updateGeneration*/);
2664: } catch (SplitRequiredException e) {
2665:
2666: /*
2667: * Shouldn't happen -- we have the DIN in the root of the
2668: * dup tree latched during this insert, so there should be
2669: * no possibility of being unable to insert a new entry
2670: * into the DIN root of the dup tree.
2671: */
2672: throw new DatabaseException(e);
2673: }
2674:
2675: long currentLsn = dupRoot.getLastFullVersion();
2676: if (currentLsn != previousLsn) {
2677: bin.updateEntry(index, currentLsn);
2678: }
2679:
2680: /* Release the BIN latch to increase concurrency. */
2681: cursor.releaseBIN();
2682: bin = null;
2683:
2684: /* The search above released the dup root latch. */
2685: dupRoot = null;
2686:
2687: /*
2688: * Try to insert a new reference object. If successful, we'll
2689: * log the LN and update the LSN in the reference.
2690: */
2691: ChildReference newLNRef = new ChildReference(newLN,
2692: newLNKey, DbLsn.NULL_LSN);
2693:
2694: int dupIndex = dupBin.insertEntry1(newLNRef);
2695: if ((dupIndex & IN.INSERT_SUCCESS) != 0) {
2696:
2697: /*
2698: * Update the cursor to point to the entry that has been
2699: * successfully inserted.
2700: */
2701: dupIndex &= ~IN.INSERT_SUCCESS;
2702: cursor.updateDBin(dupBin, dupIndex);
2703:
2704: /* Log the new LN. */
2705: long newLsn = DbLsn.NULL_LSN;
2706: try {
2707: newLsn = newLN.optionalLogUpdateMemUsage(
2708: database, key, DbLsn.NULL_LSN, cursor
2709: .getLocker(), dupBin);
2710: } finally {
2711: if ((newLsn == DbLsn.NULL_LSN)
2712: && (!database.isDeferredWrite())) {
2713:
2714: /*
2715: * See Tree.insert for an explanation of handling
2716: * of IOException and OOME.
2717: */
2718: dupBin.setKnownDeleted(dupIndex);
2719: }
2720: }
2721:
2722: lnLock.setAbortLsn(DbLsn.NULL_LSN, true, true);
2723:
2724: /*
2725: * Use updateEntry to be sure to mark the dupBin as dirty.
2726: */
2727: dupBin.updateEntry(dupIndex, newLsn);
2728:
2729: traceInsertDuplicate(Level.FINER, database
2730: .getDbEnvironment(), dupBin, newLN, newLsn,
2731: binNid);
2732: successfulInsert = true;
2733: } else {
2734:
2735: /*
2736: * The insert was not successful. Either this is a
2737: * duplicate duplicate or there is an existing entry but
2738: * that entry is deleted.
2739: */
2740: dupIndex &= ~IN.EXACT_MATCH;
2741: cursor.updateDBin(dupBin, dupIndex);
2742: LN currentLN = (LN) dupBin.fetchTarget(dupIndex);
2743:
2744: /* If an LN is present, lock it and check deleted-ness. */
2745: boolean isDeleted = false;
2746: LockResult currentLock = null;
2747: if (currentLN == null) {
2748: /* The LN was cleaned. */
2749: isDeleted = true;
2750: } else {
2751: currentLock = cursor.lockLNDeletedAllowed(
2752: currentLN, LockType.WRITE);
2753: currentLN = currentLock.getLN();
2754:
2755: /*
2756: * The BIN may have been latched while locking above.
2757: * Release the latch here because we released it above
2758: * to improve concurrency, and we will latch it again
2759: * below to increment the duplicate count. [#15574]
2760: */
2761: cursor.releaseBIN();
2762:
2763: /* The DBIN/index may have changed while locking. */
2764: dupBin = cursor.getDupBIN();
2765: dupIndex = cursor.getDupIndex();
2766: if (dupBin.isEntryKnownDeleted(dupIndex)
2767: || currentLN == null
2768: || currentLN.isDeleted()) {
2769: /* The current LN is deleted/cleaned. */
2770: isDeleted = true;
2771: }
2772: }
2773:
2774: if (isDeleted) {
2775: /* See Tree.insert for an explanation. */
2776: long abortLsn = dupBin.getLsn(dupIndex);
2777: boolean abortKnownDeleted = true;
2778: if (currentLN != null
2779: && currentLock.getLockGrant() == LockGrantType.EXISTING) {
2780: long nodeId = currentLN.getNodeId();
2781: Locker locker = cursor.getLocker();
2782: WriteLockInfo info = locker
2783: .getWriteLockInfo(nodeId);
2784: abortLsn = info.getAbortLsn();
2785: abortKnownDeleted = info
2786: .getAbortKnownDeleted();
2787: }
2788: lnLock.setAbortLsn(abortLsn, abortKnownDeleted);
2789:
2790: /*
2791: * Current entry is a deleted entry. Replace it with
2792: * LN. Pass NULL_LSN for the oldLsn parameter of the
2793: * log() method because the old LN was counted obsolete
2794: * when it was deleted.
2795: */
2796: long newLsn = newLN.optionalLog(env, database,
2797: key, DbLsn.NULL_LSN, 0, cursor
2798: .getLocker());
2799:
2800: /*
2801: * When reusing a slot, the key is replaced in the DBIN
2802: * slot. This ensures that the correct key value is
2803: * used when the new key is non-identical to the key in
2804: * the slot but is considered equal by the duplicate
2805: * comparator. [#15704]
2806: */
2807: dupBin.updateEntry(dupIndex, newLN, newLsn,
2808: newLNKey);
2809: dupBin.clearKnownDeleted(dupIndex);
2810: dupBin.clearPendingDeleted(dupIndex);
2811:
2812: traceInsertDuplicate(Level.FINER, database
2813: .getDbEnvironment(), dupBin, newLN,
2814: newLsn, binNid);
2815: successfulInsert = true;
2816: } else {
2817: /* Duplicate duplicate. */
2818: successfulInsert = false;
2819: }
2820: }
2821:
2822: /*
2823: * To avoid latching out of order (up the tree), release the
2824: * DBIN latch before latching the BIN and dup root.
2825: */
2826: dupBin.releaseLatch();
2827: dupBin = null;
2828:
2829: if (successfulInsert) {
2830: cursor.latchBIN();
2831: dupRoot = cursor
2832: .getLatchedDupRoot(false /*isDBINLatched*/);
2833: cursor.releaseBIN();
2834: dupRoot.incrementDuplicateCount(dclLockResult, key,
2835: cursor.getLocker(), true /*increment*/);
2836: }
2837: } finally {
2838: if (dupBin != null) {
2839: dupBin.releaseLatchIfOwner();
2840: }
2841:
2842: if (dupRoot != null) {
2843: dupRoot.releaseLatchIfOwner();
2844: }
2845: }
2846: } else if (n instanceof LN) {
2847:
2848: /*
2849: * There is no duplicate tree yet. The existing LN is guaranteed
2850: * to be non-deleted, so to insert we must create a dup tree.
2851: */
2852: if (!allowDuplicates) {
2853: return false;
2854: }
2855:
2856: /*
2857: * Mutate the current BIN/LN pair into a BIN/DupCountLN/DIN/DBIN/LN
2858: * duplicate tree. Log the new entries.
2859: */
2860: try {
2861: lnLock.setAbortLsn(DbLsn.NULL_LSN, true, true);
2862: dupRoot = createDuplicateTree(key, logManager,
2863: inMemoryINs, newLN, cursor);
2864: } finally {
2865: if (dupRoot != null) {
2866: dupRoot.releaseLatch();
2867: successfulInsert = true;
2868: } else {
2869: successfulInsert = false;
2870: }
2871: }
2872: } else {
2873: throw new InconsistentNodeException(
2874: "neither LN or DIN found in BIN");
2875: }
2876:
2877: return successfulInsert;
2878: }
2879:
2880: /**
2881: * Check if the duplicate root needs to be split. The current duplicate
2882: * root is latched. Exit with the new root (even if it's unchanged)
2883: * latched and the old root (unless the root is unchanged) unlatched.
2884: *
2885: * @param bin the BIN containing the duplicate root.
2886: * @param index the index of the duplicate root in bin.
2887: * @return true if the duplicate root was split.
2888: */
2889: private boolean maybeSplitDuplicateRoot(BIN bin, int index)
2890: throws DatabaseException {
2891:
2892: DIN curRoot = (DIN) bin.fetchTarget(index);
2893:
2894: if (curRoot.needsSplitting()) {
2895:
2896: EnvironmentImpl env = database.getDbEnvironment();
2897: LogManager logManager = env.getLogManager();
2898: INList inMemoryINs = env.getInMemoryINs();
2899:
2900: /*
2901: * Make a new root DIN, giving it an id key from the previous root.
2902: */
2903: byte[] rootIdKey = curRoot.getKey(0);
2904: DIN newRoot = new DIN(database, rootIdKey,
2905: maxDupTreeEntriesPerNode, curRoot.getDupKey(),
2906: curRoot.getDupCountLNRef(), curRoot.getLevel() + 1);
2907:
2908: newRoot.latch();
2909: long curRootLsn = 0;
2910: long logLsn = 0;
2911: try {
2912: newRoot.setIsRoot(true);
2913: curRoot.setDupCountLN(null);
2914: curRoot.setIsRoot(false);
2915:
2916: /*
2917: * Make the new root DIN point to the old root DIN, and then
2918: * log. We should be able to insert into the root because the
2919: * root is newly created.
2920: */
2921: try {
2922: curRootLsn = curRoot.optionalLogProvisional(
2923: logManager, newRoot);
2924: boolean insertOk = newRoot
2925: .insertEntry(new ChildReference(curRoot,
2926: rootIdKey, bin.getLsn(index)));
2927: assert insertOk;
2928:
2929: logLsn = newRoot.optionalLog(logManager);
2930: } catch (DatabaseException e) {
2931:
2932: /* Something went wrong when we tried to log. */
2933: curRoot.setIsRoot(true);
2934: throw e;
2935: }
2936:
2937: inMemoryINs.add(newRoot);
2938: bin.updateEntry(index, newRoot, logLsn);
2939: curRoot.split(newRoot, 0, maxDupTreeEntriesPerNode);
2940: } finally {
2941: curRoot.releaseLatch();
2942: }
2943: traceSplitRoot(Level.FINE, TRACE_DUP_ROOT_SPLIT, newRoot,
2944: logLsn, curRoot, curRootLsn);
2945: return true;
2946: } else {
2947: return false;
2948: }
2949: }
2950:
2951: /**
2952: * Convert an existing BIN entry from a single (non-duplicate) LN to a new
2953: * DIN/DupCountLN->DBIN->LN subtree.
2954: *
2955: * @param key the key of the entry which will become the duplicate key
2956: * for the duplicate subtree.
2957: * @param logManager the logManager
2958: * @param inMemoryINs the in memory IN list
2959: * @param newLN the new record to be inserted
2960: * @param cursor points to the target position for this new dup tree.
2961: * @return the new duplicate subtree root (a DIN). It is latched
2962: * when it is returned and the caller should unlatch it. If new entry
2963: * to be inserted is a duplicate of the existing LN, null is returned.
2964: */
2965: private DIN createDuplicateTree(byte[] key, LogManager logManager,
2966: INList inMemoryINs, LN newLN, CursorImpl cursor)
2967: throws DatabaseException {
2968:
2969: EnvironmentImpl env = database.getDbEnvironment();
2970: DIN dupRoot = null;
2971: DBIN dupBin = null;
2972: BIN bin = cursor.getBIN();
2973: int index = cursor.getIndex();
2974:
2975: /*
2976: * fetchTarget returned an LN before this method was called, and we're
2977: * still latched, so the target should never be null here.
2978: */
2979: LN existingLN = (LN) bin.fetchTarget(index);
2980: boolean existingLNIsDeleted = bin.isEntryKnownDeleted(index)
2981: || existingLN.isDeleted();
2982: assert existingLN != null;
2983:
2984: byte[] existingKey = existingLN.getData();
2985: byte[] newLNKey = newLN.getData();
2986:
2987: /* Check for duplicate duplicates. */
2988: boolean keysEqual = Key.compareKeys(newLNKey, existingKey,
2989: database.getDuplicateComparator()) == 0;
2990: if (keysEqual) {
2991: return null;
2992: }
2993:
2994: /*
2995: * Replace the existing LN with a duplicate tree.
2996: *
2997: * Once we create a dup tree, we don't revert back to the LN. Create
2998: * a DupCountLN to hold the count for this dup tree. Since we don't
2999: * roll back the internal nodes of a duplicate tree, we need to create
3000: * a pre-transaction version of the DupCountLN. This version must hold
3001: * a count of either 0 or 1, depending on whether the current
3002: * transaction created the exising lN or not. If the former, the count
3003: * must roll back to 0, if the latter, the count must roll back to 1.
3004: *
3005: * Note that we are logging a sequence of nodes and must make sure the
3006: * log can be correctly recovered even if the entire sequence doesn't
3007: * make it to the log. We need to make all children provisional to the
3008: * DIN. This works:
3009: *
3010: * Entry 1: (provisional) DupCountLN (first version)
3011: * Entry 2: (provisional) DupBIN
3012: * Entry 3: DIN
3013: * Entry 4: DupCountLN (second version, incorporating the new count.
3014: * This can't be provisional because we need to possibly
3015: * roll it back.)
3016: * Entry 5: new LN.
3017: * See [SR #10203] for a description of the bug that existed before
3018: * this change.
3019: */
3020:
3021: /* Create the first version of DupCountLN and log it. (Entry 1). */
3022: Locker locker = cursor.getLocker();
3023: long nodeId = existingLN.getNodeId();
3024:
3025: /*
3026: * If the existing entry is known to be deleted or was created by this
3027: * transaction, then the DCL should get rolled back to 0, not 1.
3028: * [13726].
3029: */
3030: int startingCount = (locker.createdNode(nodeId)
3031: || existingLNIsDeleted || locker.getWriteLockInfo(
3032: nodeId).getAbortKnownDeleted()) ? 0 : 1;
3033:
3034: DupCountLN dupCountLN = new DupCountLN(startingCount);
3035: long firstDupCountLNLsn = dupCountLN.optionalLogProvisional(
3036: env, database, key, DbLsn.NULL_LSN, 0);
3037:
3038: /* Make the duplicate root and DBIN. */
3039: dupRoot = new DIN(
3040: database,
3041: existingKey, // idkey
3042: maxDupTreeEntriesPerNode,
3043: key, // dup key
3044: new ChildReference(dupCountLN, key, firstDupCountLNLsn),
3045: 2); // level
3046: dupRoot.latch();
3047: dupRoot.setIsRoot(true);
3048:
3049: dupBin = new DBIN(database, existingKey, // idkey
3050: maxDupTreeEntriesPerNode, key, // dup key
3051: 1); // level
3052: dupBin.latch();
3053:
3054: /*
3055: * Attach the existing LN child to the duplicate BIN. Since this is a
3056: * newly created BIN, insertEntry will be successful.
3057: */
3058: ChildReference newExistingLNRef = new ChildReference(
3059: existingLN, existingKey, bin.getLsn(index), bin
3060: .getState(index));
3061:
3062: boolean insertOk = dupBin.insertEntry(newExistingLNRef);
3063: assert insertOk;
3064:
3065: try {
3066:
3067: /* Entry 2: DBIN. */
3068: long dbinLsn = dupBin.optionalLogProvisional(logManager,
3069: dupRoot);
3070: inMemoryINs.add(dupBin);
3071:
3072: /* Attach the duplicate BIN to the duplicate IN root. */
3073: dupRoot.setEntry(0, dupBin, dupBin.getKey(0), dbinLsn,
3074: dupBin.getState(0));
3075:
3076: /* Entry 3: DIN */
3077: long dinLsn = dupRoot.optionalLog(logManager);
3078: inMemoryINs.add(dupRoot);
3079:
3080: /*
3081: * Now that the DIN is logged, we've created a duplicate tree that
3082: * holds the single, preexisting LN. We can safely create the non
3083: * provisional LNs that pertain to this insert -- the new LN and
3084: * the new DupCountLN.
3085: *
3086: * We request a lock while holding latches which is usually
3087: * forbidden, but safe in this case since we know it will be
3088: * immediately granted (we just created dupCountLN above).
3089: */
3090: LockResult lockResult = locker.lock(dupCountLN.getNodeId(),
3091: LockType.WRITE, false /*noWait*/, database);
3092: lockResult.setAbortLsn(firstDupCountLNLsn, false);
3093:
3094: dupCountLN.setDupCount(2);
3095: long dupCountLsn = dupCountLN.optionalLogUpdateMemUsage(
3096: database, key, firstDupCountLNLsn, locker, dupRoot);
3097: dupRoot.updateDupCountLNRef(dupCountLsn);
3098:
3099: /* Add the newly created LN. */
3100: long newLsn = newLN.optionalLog(env, database, key,
3101: DbLsn.NULL_LSN, 0, locker);
3102: int dupIndex = dupBin.insertEntry1(new ChildReference(
3103: newLN, newLNKey, newLsn));
3104: dupIndex &= ~IN.INSERT_SUCCESS;
3105: cursor.updateDBin(dupBin, dupIndex);
3106:
3107: /*
3108: * Adjust any cursors positioned on the mutated BIN entry to point
3109: * to the DBIN at the location of the entry we moved there. The
3110: * index of the moved entry is 1 or 0, the XOR of the index of the
3111: * new entry.
3112: */
3113: bin.adjustCursorsForMutation(index, dupBin, dupIndex ^ 1,
3114: cursor);
3115: dupBin.releaseLatch();
3116:
3117: /*
3118: * Update the "regular" BIN to point to the new duplicate tree
3119: * instead of the existing LN. Clear the MIGRATE flag since it
3120: * applies only to the original LN.
3121: */
3122: bin.updateEntry(index, dupRoot, dinLsn);
3123: bin.setMigrate(index, false);
3124:
3125: traceMutate(Level.FINE, bin, existingLN, newLN, newLsn,
3126: dupCountLN, dupCountLsn, dupRoot, dinLsn, dupBin,
3127: dbinLsn);
3128: } catch (DatabaseException e) {
3129:
3130: /*
3131: * Strictly speaking, not necessary to release latches, because if
3132: * we fail to log the entries, we just throw them away, but our
3133: * unit tests check for 0 latches held in the event of a logging
3134: * error.
3135: */
3136: dupBin.releaseLatchIfOwner();
3137: dupRoot.releaseLatchIfOwner();
3138: throw e;
3139: }
3140: return dupRoot;
3141: }
3142:
3143: /**
3144: * Validate args passed to insert. Presently this just means making sure
3145: * that if they say duplicates are allowed that the database supports
3146: * duplicates.
3147: */
3148: private void validateInsertArgs(boolean allowDuplicates)
3149: throws DatabaseException {
3150: if (allowDuplicates && !database.getSortedDuplicates()) {
3151: throw new DatabaseException(
3152: "allowDuplicates passed to insert but database doesn't "
3153: + "have allow duplicates set.");
3154: }
3155: }
3156:
3157: /**
3158: * Find the BIN that is relevant to the insert. If the tree doesn't exist
3159: * yet, then create the first IN and BIN.
3160: * @return the BIN that was found or created and return it latched.
3161: */
3162: private BIN findBinForInsert(byte[] key, LogManager logManager,
3163: INList inMemoryINs, CursorImpl cursor)
3164: throws DatabaseException {
3165:
3166: BIN bin;
3167:
3168: /* First try using the BIN at the cursor position to avoid a search. */
3169: bin = cursor.latchBIN();
3170: if (bin != null) {
3171: if (!bin.needsSplitting() && bin.isKeyInBounds(key)) {
3172: return bin;
3173: } else {
3174: bin.releaseLatch();
3175: }
3176: }
3177:
3178: boolean rootLatchIsHeld = false;
3179: try {
3180: long logLsn;
3181:
3182: /*
3183: * We may have to try several times because of a small
3184: * timing window, explained below.
3185: */
3186: while (true) {
3187: rootLatchIsHeld = true;
3188: rootLatch.acquireShared();
3189: if (!rootExists()) {
3190: rootLatch.release();
3191: rootLatch.acquireExclusive();
3192: if (rootExists()) {
3193: rootLatch.release();
3194: rootLatchIsHeld = false;
3195: continue;
3196: }
3197:
3198: /*
3199: * This is an empty tree, either because it's brand new
3200: * tree or because everything in it was deleted. Create an
3201: * IN and a BIN. We could latch the rootIN here, but
3202: * there's no reason to since we're just creating the
3203: * initial tree and we have the rootLatch held. Log the
3204: * nodes as soon as they're created, but remember that
3205: * referred-to children must come before any references to
3206: * their LSNs.
3207: */
3208: /* First BIN in the tree, log provisionally right away. */
3209: bin = new BIN(database, key,
3210: maxMainTreeEntriesPerNode, 1);
3211: bin.latch();
3212: logLsn = bin.optionalLogProvisional(logManager,
3213: null);
3214:
3215: /*
3216: * Log the root right away. Leave the root dirty, because
3217: * the MapLN is not being updated, and we want to avoid
3218: * this scenario from [#13897], where the LN has no
3219: * possible parent.
3220: * provisional BIN
3221: * root IN
3222: * checkpoint start
3223: * LN is logged
3224: * checkpoint end
3225: * BIN is dirtied, but is not part of checkpoint
3226: */
3227:
3228: IN rootIN = new IN(database, key,
3229: maxMainTreeEntriesPerNode, 2);
3230:
3231: /*
3232: * OK to latch the root after a child BIN because it's
3233: * during creation.
3234: */
3235: rootIN.latch();
3236: rootIN.setIsRoot(true);
3237:
3238: boolean insertOk = rootIN
3239: .insertEntry(new ChildReference(bin, key,
3240: logLsn));
3241: assert insertOk;
3242:
3243: logLsn = rootIN.optionalLog(logManager);
3244: rootIN.setDirty(true); /*force re-logging, see [#13897]*/
3245:
3246: root = makeRootChildReference(rootIN, new byte[0],
3247: logLsn);
3248:
3249: rootIN.releaseLatch();
3250:
3251: /* Add the new nodes to the in memory list. */
3252: inMemoryINs.add(bin);
3253: inMemoryINs.add(rootIN);
3254: rootLatch.release();
3255: rootLatchIsHeld = false;
3256:
3257: break;
3258: } else {
3259: rootLatch.release();
3260: rootLatchIsHeld = false;
3261:
3262: /*
3263: * There's a tree here, so search for where we should
3264: * insert. However, note that a window exists after we
3265: * release the root latch. We release the latch because the
3266: * search method expects to take the latch. After the
3267: * release and before search, the INCompressor may come in
3268: * and delete the entire tree, so search may return with a
3269: * null.
3270: */
3271: IN in = searchSplitsAllowed(key, -1, true /*updateGeneration*/);
3272: if (in == null) {
3273: /* The tree was deleted by the INCompressor. */
3274: continue;
3275: } else {
3276: /* search() found a BIN where this key belongs. */
3277: bin = (BIN) in;
3278: break;
3279: }
3280: }
3281: }
3282: } finally {
3283: if (rootLatchIsHeld) {
3284: rootLatch.release();
3285: }
3286: }
3287:
3288: /* testing hook to insert item into log. */
3289: if (ckptHook != null) {
3290: ckptHook.doHook();
3291: }
3292:
3293: return bin;
3294: }
3295:
3296: /*
3297: * Given a subtree root (an IN), remove it and all of its children from the
3298: * in memory IN list. Also count removed nodes as obsolete and gather the
3299: * set of file summaries that should be logged. The tracker will be flushed
3300: * to the log later.
3301: */
3302: private void accountForSubtreeRemoval(INList inList,
3303: IN subtreeRoot, UtilizationTracker tracker)
3304: throws DatabaseException {
3305:
3306: inList.latchMajor();
3307: try {
3308: subtreeRoot.accountForSubtreeRemoval(inList, tracker);
3309: } finally {
3310: inList.releaseMajorLatch();
3311: }
3312:
3313: Tracer.trace(Level.FINE, database.getDbEnvironment(),
3314: "SubtreeRemoval: subtreeRoot = "
3315: + subtreeRoot.getNodeId());
3316: }
3317:
3318: /*
3319: * Logging support
3320: */
3321:
3322: /**
3323: * @see Loggable#getLogSize
3324: */
3325: public int getLogSize() {
3326: int size = LogUtils.getBooleanLogSize(); // root exists?
3327: if (root != null) {
3328: size += root.getLogSize();
3329: }
3330: return size;
3331: }
3332:
3333: /**
3334: * @see Loggable#writeToLog
3335: */
3336: public void writeToLog(ByteBuffer logBuffer) {
3337: LogUtils.writeBoolean(logBuffer, (root != null));
3338: if (root != null) {
3339: root.writeToLog(logBuffer);
3340: }
3341: }
3342:
3343: /**
3344: * @see Loggable#readFromLog
3345: */
3346: public void readFromLog(ByteBuffer itemBuffer, byte entryTypeVersion) {
3347: boolean rootExists = LogUtils.readBoolean(itemBuffer);
3348: if (rootExists) {
3349: root = makeRootChildReference();
3350: root.readFromLog(itemBuffer, entryTypeVersion);
3351: }
3352: }
3353:
3354: /**
3355: * @see Loggable#dumpLog
3356: */
3357: public void dumpLog(StringBuffer sb, boolean verbose) {
3358: sb.append("<root>");
3359: if (root != null) {
3360: root.dumpLog(sb, verbose);
3361: }
3362: sb.append("</root>");
3363: }
3364:
3365: /**
3366: * @see Loggable#getTransactionId
3367: */
3368: public long getTransactionId() {
3369: return 0;
3370: }
3371:
3372: /**
3373: * rebuildINList is used by recovery to add all the resident nodes to the
3374: * IN list.
3375: */
3376: public void rebuildINList() throws DatabaseException {
3377:
3378: INList inMemoryList = database.getDbEnvironment()
3379: .getInMemoryINs();
3380:
3381: if (root != null) {
3382: rootLatch.acquireShared();
3383: try {
3384: Node rootIN = root.getTarget();
3385: if (rootIN != null) {
3386: rootIN.rebuildINList(inMemoryList);
3387: }
3388: } finally {
3389: rootLatch.release();
3390: }
3391: }
3392: }
3393:
3394: /*
3395: * Debugging stuff.
3396: */
3397: public void dump() throws DatabaseException {
3398:
3399: System.out.println(dumpString(0));
3400: }
3401:
3402: public String dumpString(int nSpaces) throws DatabaseException {
3403:
3404: StringBuffer sb = new StringBuffer();
3405: sb.append(TreeUtils.indent(nSpaces));
3406: sb.append("<tree>");
3407: sb.append('\n');
3408: if (root != null) {
3409: sb.append(DbLsn.dumpString(root.getLsn(), nSpaces));
3410: sb.append('\n');
3411: IN rootIN = (IN) root.getTarget();
3412: if (rootIN == null) {
3413: sb.append("<in/>");
3414: } else {
3415: sb.append(rootIN.toString());
3416: }
3417: sb.append('\n');
3418: }
3419: sb.append(TreeUtils.indent(nSpaces));
3420: sb.append("</tree>");
3421: return sb.toString();
3422: }
3423:
3424: /**
3425: * Unit test support to validate subtree pruning. Didn't want to make root
3426: * access public.
3427: */
3428: boolean validateDelete(int index) throws DatabaseException {
3429:
3430: rootLatch.acquireShared();
3431: try {
3432: IN rootIN = (IN) root.fetchTarget(database, null);
3433: return rootIN.validateSubtreeBeforeDelete(index);
3434: } finally {
3435: rootLatch.release();
3436: }
3437: }
3438:
3439: /**
3440: * Debugging check that all resident nodes are on the INList and no stray
3441: * nodes are present in the unused portion of the IN arrays.
3442: */
3443: public void validateINList(IN parent) throws DatabaseException {
3444:
3445: if (parent == null) {
3446: parent = (IN) root.getTarget();
3447: }
3448: if (parent != null) {
3449: INList inList = database.getDbEnvironment()
3450: .getInMemoryINs();
3451: if (!inList.getINs().contains(parent)) {
3452: throw new DatabaseException("IN " + parent.getNodeId()
3453: + " missing from INList");
3454: }
3455: for (int i = 0;; i += 1) {
3456: try {
3457: Node node = parent.getTarget(i);
3458: if (i >= parent.getNEntries()) {
3459: if (node != null) {
3460: throw new DatabaseException("IN "
3461: + parent.getNodeId()
3462: + " has stray node "
3463: + node.getNodeId() + " at index "
3464: + i);
3465: }
3466: byte[] key = parent.getKey(i);
3467: if (key != null) {
3468: throw new DatabaseException("IN "
3469: + parent.getNodeId()
3470: + " has stray key " + key
3471: + " at index " + i);
3472: }
3473: }
3474: if (node instanceof IN) {
3475: validateINList((IN) node);
3476: }
3477: } catch (ArrayIndexOutOfBoundsException e) {
3478: break;
3479: }
3480: }
3481: }
3482: }
3483:
3484: /* For unit testing only. */
3485: public void setWaitHook(TestHook hook) {
3486: waitHook = hook;
3487: }
3488:
3489: /* For unit testing only. */
3490: public void setSearchHook(TestHook hook) {
3491: searchHook = hook;
3492: }
3493:
3494: /* For unit testing only. */
3495: public void setCkptHook(TestHook hook) {
3496: ckptHook = hook;
3497: }
3498:
3499: /**
3500: * Send trace messages to the java.util.logger. Don't rely on the logger
3501: * alone to conditionalize whether we send this message, we don't even want
3502: * to construct the message if the level is not enabled.
3503: */
3504: private void traceSplitRoot(Level level, String splitType,
3505: IN newRoot, long newRootLsn, IN oldRoot, long oldRootLsn) {
3506: Logger logger = database.getDbEnvironment().getLogger();
3507: if (logger.isLoggable(level)) {
3508: StringBuffer sb = new StringBuffer();
3509: sb.append(splitType);
3510: sb.append(" newRoot=").append(newRoot.getNodeId());
3511: sb.append(" newRootLsn=").append(
3512: DbLsn.getNoFormatString(newRootLsn));
3513: sb.append(" oldRoot=").append(oldRoot.getNodeId());
3514: sb.append(" oldRootLsn=").append(
3515: DbLsn.getNoFormatString(oldRootLsn));
3516: logger.log(level, sb.toString());
3517: }
3518: }
3519:
3520: /**
3521: * Send trace messages to the java.util.logger. Don't rely on the logger
3522: * alone to conditionalize whether we send this message, we don't even want
3523: * to construct the message if the level is not enabled.
3524: */
3525: private void traceMutate(Level level, BIN theBin, LN existingLn,
3526: LN newLn, long newLsn, DupCountLN dupCountLN,
3527: long dupRootLsn, DIN dupRoot, long ddinLsn, DBIN dupBin,
3528: long dbinLsn) {
3529: Logger logger = database.getDbEnvironment().getLogger();
3530: if (logger.isLoggable(level)) {
3531: StringBuffer sb = new StringBuffer();
3532: sb.append(TRACE_MUTATE);
3533: sb.append(" existingLn=");
3534: sb.append(existingLn.getNodeId());
3535: sb.append(" newLn=");
3536: sb.append(newLn.getNodeId());
3537: sb.append(" newLnLsn=");
3538: sb.append(DbLsn.getNoFormatString(newLsn));
3539: sb.append(" dupCountLN=");
3540: sb.append(dupCountLN.getNodeId());
3541: sb.append(" dupRootLsn=");
3542: sb.append(DbLsn.getNoFormatString(dupRootLsn));
3543: sb.append(" rootdin=");
3544: sb.append(dupRoot.getNodeId());
3545: sb.append(" ddinLsn=");
3546: sb.append(DbLsn.getNoFormatString(ddinLsn));
3547: sb.append(" dbin=");
3548: sb.append(dupBin.getNodeId());
3549: sb.append(" dbinLsn=");
3550: sb.append(DbLsn.getNoFormatString(dbinLsn));
3551: sb.append(" bin=");
3552: sb.append(theBin.getNodeId());
3553:
3554: logger.log(level, sb.toString());
3555: }
3556: }
3557:
3558: /**
3559: * Send trace messages to the java.util.logger. Don't rely on the logger
3560: * alone to conditionalize whether we send this message, we don't even want
3561: * to construct the message if the level is not enabled.
3562: */
3563: private void traceInsert(Level level, EnvironmentImpl env,
3564: BIN insertingBin, LN ln, long lnLsn, int index) {
3565: Logger logger = env.getLogger();
3566: if (logger.isLoggable(level)) {
3567: StringBuffer sb = new StringBuffer();
3568: sb.append(TRACE_INSERT);
3569: sb.append(" bin=");
3570: sb.append(insertingBin.getNodeId());
3571: sb.append(" ln=");
3572: sb.append(ln.getNodeId());
3573: sb.append(" lnLsn=");
3574: sb.append(DbLsn.getNoFormatString(lnLsn));
3575: sb.append(" index=");
3576: sb.append(index);
3577:
3578: logger.log(level, sb.toString());
3579: }
3580: }
3581:
3582: /**
3583: * Send trace messages to the java.util.logger. Don't rely on the logger
3584: * alone to conditionalize whether we send this message, we don't even want
3585: * to construct the message if the level is not enabled.
3586: */
3587: private void traceInsertDuplicate(Level level, EnvironmentImpl env,
3588: BIN insertingDBin, LN ln, long lnLsn, long binNid) {
3589: Logger logger = env.getLogger();
3590: if (logger.isLoggable(level)) {
3591: StringBuffer sb = new StringBuffer();
3592: sb.append(TRACE_INSERT_DUPLICATE);
3593: sb.append(" dbin=");
3594: sb.append(insertingDBin.getNodeId());
3595: sb.append(" bin=");
3596: sb.append(binNid);
3597: sb.append(" ln=");
3598: sb.append(ln.getNodeId());
3599: sb.append(" lnLsn=");
3600: sb.append(DbLsn.getNoFormatString(lnLsn));
3601:
3602: logger.log(level, sb.toString());
3603: }
3604: }
3605:
3606: private static class SplitInfo {
3607: IN parent;
3608: IN child;
3609: int index;
3610:
3611: SplitInfo(IN parent, IN child, int index) {
3612: this.parent = parent;
3613: this.child = child;
3614: this.index = index;
3615: }
3616: }
3617: }
|