--- /dev/null
+/*\r
+\r
+ Derby - Class org.apache.derby.impl.store.access.btree.BTreePostCommit\r
+\r
+ Licensed to the Apache Software Foundation (ASF) under one or more\r
+ contributor license agreements. See the NOTICE file distributed with\r
+ this work for additional information regarding copyright ownership.\r
+ The ASF licenses this file to you under the Apache License, Version 2.0\r
+ (the "License"); you may not use this file except in compliance with\r
+ the License. You may obtain a copy of the License at\r
+\r
+ http://www.apache.org/licenses/LICENSE-2.0\r
+\r
+ Unless required by applicable law or agreed to in writing, software\r
+ distributed under the License is distributed on an "AS IS" BASIS,\r
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
+ See the License for the specific language governing permissions and\r
+ limitations under the License.\r
+\r
+ */\r
+\r
+package org.apache.derby.impl.store.access.btree;\r
+\r
+import org.apache.derby.iapi.services.context.ContextManager;\r
+import org.apache.derby.iapi.services.daemon.Serviceable;\r
+import org.apache.derby.iapi.services.sanity.SanityManager;\r
+import org.apache.derby.iapi.error.StandardException;\r
+\r
+import org.apache.derby.iapi.store.access.AccessFactory;\r
+import org.apache.derby.iapi.store.access.AccessFactoryGlobals;\r
+import org.apache.derby.iapi.store.access.ConglomerateController;\r
+import org.apache.derby.iapi.store.access.DynamicCompiledOpenConglomInfo;\r
+import org.apache.derby.iapi.store.access.RowUtil;\r
+import org.apache.derby.iapi.store.access.TransactionController;\r
+\r
+import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;\r
+import org.apache.derby.iapi.store.access.conglomerate.TransactionManager;\r
+\r
+import org.apache.derby.iapi.store.raw.ContainerHandle;\r
+import org.apache.derby.iapi.store.raw.FetchDescriptor;\r
+import org.apache.derby.iapi.store.raw.LockingPolicy;\r
+import org.apache.derby.iapi.store.raw.Page;\r
+import org.apache.derby.iapi.store.raw.RecordHandle;\r
+\r
+import org.apache.derby.iapi.types.DataValueDescriptor;\r
+\r
+import org.apache.derby.iapi.reference.SQLState;\r
+\r
+/**\r
+\r
+The BTreePostCommit class implements the Serviceable protocol. \r
+\r
+In it's role as a Serviceable object, it stores the state necessary to \r
+find a page in a btree that may have committed delete's to reclaim.\r
+\r
+In it's role as a PostCommitProcessor it looks up the page described, and\r
+reclaims space in the btree. It first trys to clean up any deleted commits\r
+on the page. It then will shrink the tree if it is going to delete all\r
+rows from the page (RESOLVE - not done yet).\r
+\r
+**/\r
+\r
+class BTreePostCommit implements Serviceable\r
+{\r
+ private AccessFactory access_factory = null;\r
+ private long page_number = ContainerHandle.INVALID_PAGE_NUMBER;\r
+\r
+ protected BTree btree = null;\r
+\r
+ /* Constructors for This class: */\r
+ BTreePostCommit(\r
+ AccessFactory access_factory,\r
+ BTree btree,\r
+ long input_page_number)\r
+ {\r
+ this.access_factory = access_factory; \r
+ this.btree = btree; \r
+ this.page_number = input_page_number; \r
+ }\r
+\r
+ /* Private/Protected methods of This class: */\r
+\r
+ /* Public Methods of This class: */\r
+\r
+ /* Public Methods of Serviceable class: */\r
+\r
+ /**\r
+ * The urgency of this post commit work.\r
+ * <p>\r
+ * This determines where this Serviceable is put in the post commit \r
+ * queue. Post commit work in the btree can be safely delayed until there\r
+ * is not user work to do.\r
+ *\r
+ * @return false, this work should not be serviced ASAP\r
+ **/\r
+ public boolean serviceASAP()\r
+ {\r
+ return(true);\r
+ }\r
+\r
+\r
+ // @return true, if this work needs to be done on a user thread immediately\r
+ public boolean serviceImmediately()\r
+ {\r
+ return false;\r
+ } \r
+\r
+ private final void doShrink(\r
+ OpenBTree open_btree, \r
+ DataValueDescriptor[] shrink_row)\r
+ throws StandardException\r
+ {\r
+ ControlRow root = null;\r
+\r
+ /*\r
+ System.out.println(\r
+ "Calling shrink on tree with levels = " + \r
+ open_btree.getHeight() + "\n");\r
+ */\r
+\r
+ // Get the root page back, and perform a split following the\r
+ // to-be-inserted key. The split releases the root page latch.\r
+ root = ControlRow.get(open_btree, BTree.ROOTPAGEID);\r
+\r
+ root.shrinkFor(open_btree, shrink_row);\r
+\r
+ root = null;\r
+\r
+ // on return from shrinkFor the root pointer is invalid. The\r
+ // latch has been released, the root page may have changed from\r
+ // a branch to a leaf.\r
+\r
+ return;\r
+ }\r
+\r
+ /**\r
+ * Open index for either table level or row level update.\r
+ * <p>\r
+ * @param lock_level For table level use TransactionManager.MODE_TABLE,\r
+ * for row level use TransactionManager.MODE_RECORD\r
+ * @param lock_mode For table level use LockingPolicy.MODE_CONTAINER,\r
+ * for row level use LockingPolicy.MODE_RECORD\r
+ *\r
+ * @exception StandardException Standard exception policy.\r
+ **/\r
+ private final OpenBTree openIndex(\r
+ TransactionManager internal_xact,\r
+ int lock_level,\r
+ int lock_mode)\r
+ throws StandardException\r
+ {\r
+ OpenBTree open_btree = new OpenBTree();\r
+\r
+ ConglomerateController base_cc = \r
+ btree.lockTable(\r
+ internal_xact, \r
+ (ContainerHandle.MODE_FORUPDATE |\r
+ ContainerHandle.MODE_LOCK_NOWAIT), \r
+ lock_level,\r
+ TransactionController.ISOLATION_REPEATABLE_READ);\r
+\r
+ open_btree.init(\r
+ (TransactionManager) null, \r
+ internal_xact, \r
+ (ContainerHandle) null, // open the container \r
+ internal_xact.getRawStoreXact(),\r
+ false,\r
+ (ContainerHandle.MODE_FORUPDATE | ContainerHandle.MODE_LOCK_NOWAIT),\r
+ lock_level,\r
+ btree.getBtreeLockingPolicy(\r
+ internal_xact.getRawStoreXact(),\r
+ lock_level,\r
+ lock_mode,\r
+ TransactionController.ISOLATION_REPEATABLE_READ, \r
+ base_cc,\r
+ open_btree),\r
+ btree, \r
+ (LogicalUndo) null, // No logical undo necessry.\r
+ (DynamicCompiledOpenConglomInfo) null);\r
+\r
+ return(open_btree);\r
+ }\r
+\r
+ /**\r
+ * perform the work described in the postcommit work.\r
+ * <p>\r
+ * In this implementation the only work that can be executed by this\r
+ * post commit processor is this class itself.\r
+ * <p>\r
+ *\r
+ * @return Returns Serviceable.DONE when work has completed, or\r
+ * returns Serviceable.REQUEUE if work needs to be requeued.\r
+ *\r
+ * @param contextMgr the context manager started by the\r
+ * post commit daemon\r
+ *\r
+ * @exception StandardException Standard exception policy.\r
+ **/\r
+ public int performWork(ContextManager contextMgr)\r
+ throws StandardException\r
+ {\r
+\r
+ // requeue if work was not completed in this try because of locks\r
+ boolean requeue_work = false;\r
+\r
+ TransactionManager tc = (TransactionManager)\r
+ this.access_factory.getAndNameTransaction(\r
+ contextMgr, AccessFactoryGlobals.SYS_TRANS_NAME);\r
+\r
+ TransactionManager internal_xact = tc.getInternalTransaction();\r
+\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ if (SanityManager.DEBUG_ON("verbose_btree_post_commit"))\r
+ System.out.println("starting internal xact\n");\r
+ }\r
+\r
+ OpenBTree open_btree = null;\r
+\r
+ try\r
+ {\r
+ // Get lock on base table.\r
+ \r
+ // First attempt to get a table lock on the btree. This lock is\r
+ // requested NOWAIT to not impede normal operation on the table.\r
+ // If the lock were to wait then the current lock manager livelock \r
+ // algorithm would block all subsequent lock requests on this \r
+ // btree even if they are compatible with the current holder of \r
+ // the lock.\r
+ //\r
+ // If this lock is granted then:\r
+ // 1) deleted rows on the page can automatically be purged as\r
+ // they must be committed, otherwise lock would not have been\r
+ // granted.\r
+ // 2) if all rows from page are reclaimed then a structure shrink\r
+ // which requires table level lock can be executed.\r
+ //\r
+ open_btree = \r
+ openIndex(\r
+ internal_xact, \r
+ TransactionController.MODE_TABLE, \r
+ LockingPolicy.MODE_CONTAINER);\r
+\r
+ DataValueDescriptor[] shrink_key = \r
+ purgeCommittedDeletes(open_btree, this.page_number);\r
+\r
+ // RESOLVE (mikem) - move this call when doing row level locking.\r
+ if (shrink_key != null)\r
+ doShrink(open_btree, shrink_key);\r
+\r
+ open_btree.close();\r
+ }\r
+ catch (StandardException se)\r
+ {\r
+ // 2 kinds of errors here expected here. Either container not \r
+ // found or could not obtain lock (LOCK_TIMEOUT or DEADLOCK).\r
+ //\r
+ // It is possible by the time this post commit work gets scheduled \r
+ // that the container has been dropped and that the open container \r
+ // call will return null - in this case just return assuming no \r
+ // work to be done.\r
+\r
+ if (se.getMessageId().equals(SQLState.LOCK_TIMEOUT) ||\r
+ se.getMessageId().equals(SQLState.DEADLOCK))\r
+ {\r
+ // Could not get exclusive table lock, so try row level\r
+ // reclaim of just the rows on this page. No merge is \r
+ // attempted.\r
+\r
+ try\r
+ {\r
+ open_btree = \r
+ openIndex(\r
+ internal_xact, \r
+ TransactionController.MODE_RECORD, \r
+ LockingPolicy.MODE_RECORD);\r
+\r
+ purgeRowLevelCommittedDeletes(open_btree);\r
+\r
+ open_btree.close();\r
+\r
+ }\r
+ catch (StandardException se2)\r
+ {\r
+ if (se2.getMessageId().equals(SQLState.LOCK_TIMEOUT) ||\r
+ se2.getMessageId().equals(SQLState.DEADLOCK))\r
+ {\r
+ // Could not get intended exclusive table lock, so \r
+ // requeue and hope other user gives up table level\r
+ // lock soon. This should not be normal case.\r
+ requeue_work = true;\r
+ }\r
+ }\r
+ }\r
+ }\r
+ finally\r
+ {\r
+ internal_xact.commit();\r
+ internal_xact.destroy();\r
+ }\r
+\r
+ return(requeue_work ? Serviceable.REQUEUE : Serviceable.DONE);\r
+ }\r
+\r
+ private final DataValueDescriptor[] getShrinkKey(\r
+ OpenBTree open_btree, \r
+ ControlRow control_row,\r
+ int slot_no)\r
+ throws StandardException\r
+ {\r
+ DataValueDescriptor[] shrink_key = \r
+ open_btree.getConglomerate().createTemplate(\r
+ open_btree.getRawTran());\r
+\r
+ control_row.page.fetchFromSlot(\r
+ (RecordHandle) null,\r
+ slot_no, shrink_key, \r
+ (FetchDescriptor) null,\r
+ true);\r
+\r
+ return(shrink_key);\r
+ }\r
+\r
+ /**\r
+ * Reclaim space taken up by committed deleted rows.\r
+ * <p>\r
+ * This routine assumes it has been called by an internal transaction which\r
+ * has performed no work so far, and that it has an exclusive table lock. \r
+ * These assumptions mean that any deleted rows encountered must be from\r
+ * committed transactions (otherwise we could not have gotten the exclusive\r
+ * table lock).\r
+ * <p>\r
+ * RESOLVE (mikem) - under row locking this routine must do more work to\r
+ * determine a deleted row is a committed deleted row.\r
+ *\r
+ * @param open_btree The btree already opened.\r
+ * @param pageno The page number of the page to look for committed deletes.\r
+ *\r
+ * @exception StandardException Standard exception policy.\r
+ **/\r
+ private final DataValueDescriptor[] purgeCommittedDeletes(\r
+ OpenBTree open_btree,\r
+ long pageno)\r
+ throws StandardException\r
+ {\r
+ ControlRow control_row = null;\r
+ DataValueDescriptor[] shrink_key = null; \r
+\r
+ try\r
+ {\r
+ // The following can fail either if it can't get the latch or\r
+ // somehow the page requested no longer exists. In either case\r
+ // the post commit work will just skip it.\r
+ control_row = ControlRow.getNoWait(open_btree, pageno);\r
+\r
+ if (control_row != null)\r
+ {\r
+ Page page = control_row.page;\r
+\r
+ // The number records that can be reclaimed is:\r
+ // total recs - control row - recs_not_deleted\r
+ int num_possible_commit_delete = \r
+ page.recordCount() - 1 - page.nonDeletedRecordCount();\r
+\r
+ if (num_possible_commit_delete > 0)\r
+ {\r
+ // loop backward so that purges which affect the slot table \r
+ // don't affect the loop (ie. they only move records we \r
+ // have already looked at).\r
+ for (int slot_no = page.recordCount() - 1; \r
+ slot_no > 0; \r
+ slot_no--) \r
+ {\r
+ if (page.isDeletedAtSlot(slot_no))\r
+ {\r
+\r
+ if (page.recordCount() == 2)\r
+ {\r
+ // About to purge last row from page so \r
+ // remember the key so we can shrink the \r
+ // tree.\r
+ shrink_key = this.getShrinkKey(\r
+ open_btree, control_row, slot_no);\r
+ }\r
+\r
+ page.purgeAtSlot(slot_no, 1, true);\r
+\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ if (SanityManager.DEBUG_ON(\r
+ "verbose_btree_post_commit"))\r
+ {\r
+ System.out.println(\r
+ "Purging row[" + slot_no + "]" + \r
+ "on page:" + pageno + ".\n");\r
+ }\r
+ }\r
+ }\r
+ }\r
+ }\r
+\r
+ if (page.recordCount() == 1)\r
+ {\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ if (SanityManager.DEBUG_ON("verbose_btree_post_commit"))\r
+ {\r
+ System.out.println("Chance to shrink.\n");\r
+ }\r
+ }\r
+ }\r
+ }\r
+ else\r
+ {\r
+ if (SanityManager.DEBUG)\r
+ {\r
+ if (SanityManager.DEBUG_ON("verbose_btree_post_commit"))\r
+ {\r
+ System.out.println(\r
+ "Get No Wait returned null. page num = " + pageno +\r
+ "\n");\r
+ }\r
+ }\r
+ }\r
+ }\r
+ finally\r
+ {\r
+ if (control_row != null)\r
+ control_row.release();\r
+ }\r
+\r
+ return(shrink_key);\r
+ }\r
+\r
+ /**\r
+ * Attempt to reclaim committed deleted rows from the page with row locking.\r
+ * <p>\r
+ * Get exclusive latch on page, and then loop backward through\r
+ * page searching for deleted rows which are committed. \r
+ * This routine is called only from post commit processing so it will never\r
+ * see rows deleted by the current transaction.\r
+ * For each deleted row on the page\r
+ * it attempts to get an exclusive lock on the deleted row, NOWAIT.\r
+ * If it succeeds, and since this transaction did not delete the row then \r
+ * the row must have been deleted by a transaction which has committed, so\r
+ * it is safe to purge the row. It then purges the row from the page.\r
+ *\r
+ * @param open_btree The already open btree, which has been locked with IX\r
+ * table lock, to use to get latch on page.\r
+ *\r
+ * @exception StandardException Standard exception policy.\r
+ **/\r
+ private final void purgeRowLevelCommittedDeletes(\r
+ OpenBTree open_btree)\r
+ throws StandardException\r
+ {\r
+ LeafControlRow leaf = null;\r
+\r
+ try\r
+ {\r
+ // The following can fail, returning null, either if it can't get\r
+ // the latch or somehow the page requested no longer exists. In \r
+ // either case the post commit work will just skip it.\r
+ leaf = (LeafControlRow) \r
+ ControlRow.getNoWait(open_btree, page_number);\r
+ if (leaf == null)\r
+ return;\r
+\r
+ BTreeLockingPolicy btree_locking_policy = \r
+ open_btree.getLockingPolicy();\r
+\r
+ // The number records that can be reclaimed is:\r
+ // total recs - control row - recs_not_deleted\r
+ int num_possible_commit_delete = \r
+ leaf.page.recordCount() - 1 - leaf.page.nonDeletedRecordCount();\r
+\r
+ if ((num_possible_commit_delete > 0) &&\r
+ (btree_locking_policy.lockScanForReclaimSpace(leaf)))\r
+ {\r
+ DataValueDescriptor[] scratch_template = \r
+ open_btree.getRuntimeMem().get_template(\r
+ open_btree.getRawTran());\r
+\r
+ // Need to get an exclusive scan lock on the page before we can\r
+ // do any sort of purges, otherwise other concurrent scans would\r
+ // not work. If we can't get the lock NOWAIT, just give up on\r
+ // purging rows. \r
+ Page page = leaf.page;\r
+\r
+\r
+ // RowLocation column is in last column of template.\r
+ FetchDescriptor lock_fetch_desc = \r
+ RowUtil.getFetchDescriptorConstant(\r
+ scratch_template.length - 1);\r
+\r
+ // loop backward so that purges which affect the slot table \r
+ // don't affect the loop (ie. they only move records we \r
+ // have already looked at).\r
+ for (int slot_no = page.recordCount() - 1; \r
+ slot_no > 0; \r
+ slot_no--) \r
+ {\r
+ if (page.isDeletedAtSlot(slot_no))\r
+ {\r
+ // try to get an exclusive lock on the row, if we can \r
+ // then the row is a committed deleted row and it is \r
+ // safe to purge it.\r
+ if (btree_locking_policy.lockScanCommittedDeletedRow(\r
+ open_btree, leaf, scratch_template, \r
+ lock_fetch_desc, slot_no))\r
+ {\r
+ // the row is a committed deleted row, purge it.\r
+ page.purgeAtSlot(slot_no, 1, true);\r
+ }\r
+ }\r
+ }\r
+\r
+ }\r
+ }\r
+ finally\r
+ {\r
+ if (leaf != null)\r
+ leaf.release();\r
+ }\r
+ }\r
+}\r