in hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/BTree.java [591:781]
private void performOp(int pageId, ICachedPage parent, boolean parentIsReadLatched, BTreeOpContext ctx)
throws HyracksDataException, TreeIndexException {
ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
ctx.interiorFrame.setPage(node);
// this check performs an unprotected read in the page
// the following could happen: TODO fill out
boolean unsafeIsLeaf = ctx.interiorFrame.isLeaf();
boolean isReadLatched = acquireLatch(node, ctx, unsafeIsLeaf);
boolean smFlag = ctx.interiorFrame.getSmFlag();
// re-check leafness after latching
boolean isLeaf = ctx.interiorFrame.isLeaf();
// remember trail of pageLsns, to unwind recursion in case of an ongoing
// structure modification
ctx.pageLsns.add(ctx.interiorFrame.getPageLsn());
try {
// Latch coupling: unlatch parent.
if (parent != null) {
if (parentIsReadLatched) {
parent.releaseReadLatch();
} else {
parent.releaseWriteLatch(true);
}
bufferCache.unpin(parent);
}
if (!isLeaf || smFlag) {
if (!smFlag) {
// We use this loop to deal with possibly multiple operation
// restarts due to ongoing structure modifications during
// the descent.
boolean repeatOp = true;
while (repeatOp && ctx.opRestarts < MAX_RESTARTS) {
int childPageId = ctx.interiorFrame.getChildPageId(ctx.pred);
performOp(childPageId, node, isReadLatched, ctx);
if (!ctx.pageLsns.isEmpty()) {
if (ctx.pageLsns.getLast() == FULL_RESTART_OP) {
break;
} else if (ctx.pageLsns.getLast() == RESTART_OP) {
// Pop the restart op indicator.
ctx.pageLsns.removeLast();
node = isConsistent(pageId, ctx);
if (node != null) {
isReadLatched = true;
// Descend the tree again.
continue;
} else {
// Pop pageLsn of this page (version seen by this op during descent).
ctx.pageLsns.removeLast();
// This node is not consistent set the restart indicator for upper level.
ctx.pageLsns.add(RESTART_OP);
break;
}
}
}
switch (ctx.op) {
case INSERT:
case UPSERT:
case UPDATE: {
// Is there a propagated split key?
if (ctx.splitKey.getBuffer() != null) {
ICachedPage interiorNode = bufferCache.pin(
BufferedFileHandle.getDiskPageId(fileId, pageId), false);
interiorNode.acquireWriteLatch();
try {
// Insert or update op. Both can cause split keys to propagate upwards.
insertInterior(interiorNode, pageId, ctx.splitKey.getTuple(), ctx);
} finally {
interiorNode.releaseWriteLatch(true);
bufferCache.unpin(interiorNode);
}
} else {
unsetSmPages(ctx);
}
break;
}
case DELETE: {
if (ctx.splitKey.getBuffer() != null) {
throw new BTreeException(
"Split key was propagated during delete. Delete allows empty leaf pages.");
}
break;
}
default: {
// Do nothing for Search and DiskOrderScan.
break;
}
}
// Operation completed.
repeatOp = false;
} // end while
} else { // smFlag
ctx.opRestarts++;
if (isReadLatched) {
node.releaseReadLatch();
} else {
node.releaseWriteLatch(true);
}
bufferCache.unpin(node);
// TODO: this should be an instant duration lock, how to do
// this in java?
// instead we just immediately release the lock. this is
// inefficient but still correct and will not cause
// latch-deadlock
treeLatch.readLock().lock();
treeLatch.readLock().unlock();
// unwind recursion and restart operation, find lowest page
// with a pageLsn as seen by this operation during descent
ctx.pageLsns.removeLast(); // pop current page lsn
// put special value on the stack to inform caller of
// restart
ctx.pageLsns.add(RESTART_OP);
}
} else { // isLeaf and !smFlag
// We may have to restart an op to avoid latch deadlock.
boolean restartOp = false;
ctx.leafFrame.setPage(node);
switch (ctx.op) {
case INSERT: {
int targetTupleIndex = ctx.leafFrame.findInsertTupleIndex(ctx.pred.getLowKey());
restartOp = insertLeaf(ctx.pred.getLowKey(), targetTupleIndex, pageId, ctx);
break;
}
case UPSERT: {
int targetTupleIndex = ctx.leafFrame.findUpsertTupleIndex(ctx.pred.getLowKey());
restartOp = upsertLeaf(ctx.pred.getLowKey(), targetTupleIndex, pageId, ctx);
break;
}
case UPDATE: {
int oldTupleIndex = ctx.leafFrame.findUpdateTupleIndex(ctx.pred.getLowKey());
restartOp = updateLeaf(ctx.pred.getLowKey(), oldTupleIndex, pageId, ctx);
break;
}
case DELETE: {
restartOp = deleteLeaf(node, pageId, ctx.pred.getLowKey(), ctx);
break;
}
case SEARCH: {
ctx.cursorInitialState.setSearchOperationCallback(ctx.searchCallback);
ctx.cursorInitialState.setOriginialKeyComparator(ctx.cmp);
ctx.cursorInitialState.setPage(node);
ctx.cursorInitialState.setPageId(pageId);
ctx.cursor.open(ctx.cursorInitialState, ctx.pred);
break;
}
}
if (ctx.op != IndexOperation.SEARCH) {
node.releaseWriteLatch(true);
bufferCache.unpin(node);
}
if (restartOp) {
// Wait for the SMO to persistFrontiers before restarting.
treeLatch.readLock().lock();
treeLatch.readLock().unlock();
ctx.pageLsns.removeLast();
ctx.pageLsns.add(FULL_RESTART_OP);
}
}
} catch (TreeIndexException e) {
if (!ctx.exceptionHandled) {
if (node != null) {
if (isReadLatched) {
node.releaseReadLatch();
} else {
node.releaseWriteLatch(true);
}
bufferCache.unpin(node);
ctx.exceptionHandled = true;
}
}
throw e;
} catch (Exception e) {
e.printStackTrace();
if (node != null) {
if (isReadLatched) {
node.releaseReadLatch();
} else {
node.releaseWriteLatch(true);
}
bufferCache.unpin(node);
}
BTreeException wrappedException = new BTreeException(e);
ctx.exceptionHandled = true;
throw wrappedException;
}
}