From: Date: June 7 2007 4:25am Subject: bk commit into 6.0-falcon tree (chris:1.2553) BUG#26930 List-Archive: http://lists.mysql.com/commits/28250 X-Bug: 26930 Message-Id: <20070607022558.658A21D89B@terrazzo.site> Below is the list of changes that have just been committed into a local 6.0-falcon repository of root. When root does a push these changes will be propagated to the main repository and, within 24 hours after the push, to the public repository. For information on how to access the public repository see http://dev.mysql.com/doc/mysql/en/installing-source-tree.html ChangeSet@stripped, 2007-06-06 21:25:50-05:00, chris@stripped +6 -0 Bug#26930 "Falcon: Replaying a big mysql dump file crashes mysqld" Fixed three unrelated indexing issues that prevented a SAP R3 database dump file from loading: 1. Modified IndexRootPage::splitIndexPage() such that the parent page references the "left" page with node having a null key and appended record number of 0. 2. Modified IndexPage::findInsertionPoint() to correctly order duplicate null keys by using a record number comparison. 3. Adjusted an assert in IndexRootPage::findInsertionLeaf() to allow for searches across pages of the same non-zero level. Also enhanced printPage() for detailed debugging of index pages. storage/falcon/Dbb.h@stripped, 2007-06-06 21:17:04-05:00, chris@stripped +1 -0 Added DEBUG_PAGE_LEVEL for detailed debugging of index pages. storage/falcon/IndexPage.cpp@stripped, 2007-06-06 21:17:04-05:00, chris@stripped +130 -14 IndexPage::findInsertionPoint() exits the node search if node.length == 0, preventing a record number comparison for duplicate null keys and causing nodes to be inserted out of order. Modified findInsertionPoint() to only exit the node search if node.length == 0 for level 1 pages and above. Also added an enhanced version of printPage(). storage/falcon/IndexPage.h@stripped, 2007-06-06 21:17:04-05:00, chris@stripped +4 -0 Enhanced printPage(). storage/falcon/IndexRootPage.cpp@stripped, 2007-06-06 21:17:04-05:00, chris@stripped +40 -20 Fix 1: splitIndexPage() creates a parent page that references two new child pages. The node referencing the "left" page was created with a null key and 0 record number. The record number was not appended to the new node if it referenced a level 0 page, producing a node that did not sort correctly and effectively corrupting the parent page. Modified splitIndexPage() to so that the new parent page references the leftmost level 0 page with a null key *and* an appended record number of 0. Fix 2: Nodes having only null keys were sorted in descending order. Modified indInsertionPoint() so that duplicate null keys are compared using the record number. storage/falcon/Page.h@stripped, 2007-06-06 21:17:04-05:00, chris@stripped +4 -0 Added page number field for debug-only builds. storage/falcon/PageInventoryPage.cpp@stripped, 2007-06-06 21:17:04-05:00, chris@stripped +3 -0 Added a page number field for debugging. # This is a BitKeeper patch. What follows are the unified diffs for the # set of deltas contained in the patch. The rest of the patch, the part # that BitKeeper cares about, is below these diffs. # User: chris # Host: terrazzo.site # Root: /home/chris/work/dev/dev-8/mysql-5.1-falcon --- 1.41/storage/falcon/Dbb.h 2007-06-04 17:08:16 -05:00 +++ 1.42/storage/falcon/Dbb.h 2007-06-06 21:17:04 -05:00 @@ -50,6 +50,7 @@ #define DEBUG_INVERSION 1 << 10 #define DEBUG_DEFERRED_INDEX 1 << 11 #define DEBUG_RECORD_SCAVENGE 1 << 12 +#define DEBUG_PAGE_LEVEL 1 << 13 #define DEBUG_ALL -1 static const int FillLevels = 5; --- 1.51/storage/falcon/IndexPage.cpp 2007-06-01 16:02:33 -05:00 +++ 1.52/storage/falcon/IndexPage.cpp 2007-06-06 21:17:04 -05:00 @@ -42,8 +42,11 @@ AddNodeResult IndexPage::addNode(Dbb *dbb, IndexKey *indexKey, int32 recordNumber) { - if (dbb->debug & (DEBUG_KEYS | DEBUG_NODES_ADDED)) - Btn::printKey ("new key: ", indexKey, 0, false); + if (dbb->debug & (DEBUG_KEYS | DEBUG_NODES_ADDED | DEBUG_PAGE_LEVEL)) + { + Log::debug("\n***** addNode(%d) - ", recordNumber); + Btn::printKey ("New key", indexKey, 0, false); + } if (dbb->debug & (DEBUG_PAGES | DEBUG_NODES_ADDED)) printPage (this, 0, false); @@ -433,10 +436,13 @@ if (recordNumber == END_BUCKET) ASSERT(nextPage != 0); - for (UCHAR *p = node.key, *q = key + node.offset, *end = key + l; q < end;) - if (*p++ > *q++) - break; - else if (*p++ < *q++) + for (UCHAR *p = node.key, *q = key + node.offset, *end = key + l; q < end; p++, q++) + { + if (*p > *q) // current > previous, good + break; + else if (*p == *q) // current == previous, good so far + continue; + else if (*p < *q) // current < previous, bad { if (before) printPage ((IndexPage*) before, 0, false); @@ -444,6 +450,7 @@ printPage(this, 0, false); FATAL("Mal-formed index page"); } + } keyLength = node.expandKey(key); } @@ -597,12 +604,122 @@ node.printKey ("", key, inversion); } - length = (int) ((UCHAR*) node.node - (UCHAR*) page); + length = (UCHAR*) node.node - (UCHAR*) page; if (length != page->length) Log::debug ("**** bad bucket length -- should be %d ***\n", length); } +void IndexPage::printPage(IndexPage *page, int32 pageNum, bool printDetail, bool inversion) +{ + LogLock logLock; +#ifdef DEBUG_INDEX_PAGE + int32 pageNumber = page->pageNumber; +#else + int32 pageNumber = pageNum; +#endif + + Log::debug ("Page: %d level: %d length: %d prior: %d next: %d parent: %d BEGIN\n", + pageNumber, + page->level, + page->length, + page->priorPage, + page->nextPage, + page->parentPage); + + Btn *end = (Btn*) ((UCHAR*) page + page->length); + IndexNode node (page); + IndexNode lastNode1; + IndexNode lastNode2; + + for (int i = 0; node.node < end; node.getNext(), i++) + { + if (i < 3 || printDetail) + printNode(i, page, pageNumber, node, inversion); + else if (node.getNumber() < 0) + { + if (i > 3) + Log::debug(" ...\n"); + if (i > 4) + printNode(i - 2, page, pageNumber, lastNode2, inversion); + if (i > 3) + printNode(i - 1, page, pageNumber, lastNode1, inversion); + printNode(i, page, pageNumber, node, inversion); + } + + lastNode2 = lastNode1; + lastNode1 = node; + } + +// if (printDetail) + Log::debug ("Page: %d level: %d length: %d prior: %d next: %d parent: %d END\n", + pageNumber, + page->level, + page->length, + page->priorPage, + page->nextPage, + page->parentPage); + + int length = (UCHAR*) node.node - (UCHAR*) page; + + if (length != page->length) + Log::debug ("**** bad bucket length -- should be %d ***\n", length); +} + +void IndexPage::printNode(int i, IndexPage * page, int32 pageNumber, IndexNode & node, bool inversion) +{ + UCHAR key[MAX_PHYSICAL_KEY_LENGTH]; + + //LogLock logLock; + node.expandKey(key); + + if (page->level == 0) + Log::debug("%4d: record: %6d, ofs: %4d, len: %4d, pgofs: %4d | %6d ", + i, // node count + node.getNumber(), // record number + node.offset, // key offset + node.length, // stored length of key + (char*) node.node - (char*) page, // physical offset into page + pageNumber); + else + Log::debug("%4d: page: %6d, ofs: %4d, len: %4d, pgofs: %4d, record: %6d | %6d ", + i, // node count + node.getNumber(), // page number + node.offset, // key offset + node.length, // stored length of key + (char*) node.node - (char*) page, // offset into page + node.getAppendedRecordNumber(), // appended record number + pageNumber); + + node.printKey("", key, inversion); +} + +void IndexPage::printNode(IndexPage *page, int32 pageNumber, Btn *node, bool inversion) +{ + Btn *end = (Btn*) ((UCHAR*) page + page->length); + IndexNode tmp(page); + int i; + + for (i = 0; tmp.node < end; tmp.getNext(), i++) + { + if (tmp.node == node) + break; + } + + { + //LogLock logLock; + Log::debug("Page: %d level: %d length: %d prior: %d next: %d parent: %d\n", + pageNumber, + page->level, + page->length, + page->priorPage, + page->nextPage, + page->parentPage); + + printNode(i, page, pageNumber, tmp, inversion); + } +} + void IndexPage::validate(Dbb *dbb, Validation *validation, Bitmap *pages, int32 parentPageNumber) { if (pageType == PAGE_inversion) @@ -985,16 +1102,15 @@ if (q < nodeEnd) goto exit; // key < node, use this node. - // key values are equal, test the record numbers, - // for level 0, they are embedded. Level > 0, they are appended - - if (node.length == 0) - goto exit; + // Key values are equal, so test the record numbers. + // Record numbers are embedded for level 0, appended for level > 0. if (level) { - if (indexKey->recordNumber > node.getAppendedRecordNumber()) - break; // keep looking. + if (node.length == 0) + goto exit; // node length of 0 is valid for null keys on level 0 + else if (indexKey->recordNumber > node.getAppendedRecordNumber()) + break; // keep looking } else { --- 1.22/storage/falcon/IndexPage.h 2007-04-23 08:50:35 -05:00 +++ 1.23/storage/falcon/IndexPage.h 2007-06-06 21:17:04 -05:00 @@ -27,6 +27,7 @@ #include "Page.h" #include "Btn.h" #include "RootPage.h" +#include "IndexNode.h" static const int SUPERNODES = 16; @@ -76,6 +77,9 @@ static Bdb* createNewLevel (Dbb *dbb, int level, int version, int32 page1, int32 page2, IndexKey *key2, TransId transId); static void printPage (Bdb *bdb, bool inversion); static void printPage (IndexPage *page, int32 pageNumber, bool inversion); + static void printPage (IndexPage *page, int32 pageNum, bool printDetail, bool inversion); + static void printNode(int i, IndexPage * page, int32 pageNumber, IndexNode & node, bool inversion = false); + static void printNode(IndexPage *page, int32 pageNumber, Btn *node, bool inversion = false); static int32 getRecordNumber(const UCHAR *ptr); static void logIndexPage (Bdb *bdb, TransId transId); static Btn* findInsertionPoint(int level, IndexKey* indexKey, int32 recordNumber, IndexKey* expandedKey, Btn* nodes, Btn* bucketEnd); --- 1.65/storage/falcon/IndexRootPage.cpp 2007-06-01 16:02:34 -05:00 +++ 1.66/storage/falcon/IndexRootPage.cpp 2007-06-06 21:17:04 -05:00 @@ -111,20 +111,16 @@ IndexKey searchKey(key); searchKey.appendRecordNumber(recordNumber); - if (dbb->debug & (DEBUG_KEYS | DEBUG_NODES_ADDED)) + if (dbb->debug & (DEBUG_KEYS | DEBUG_NODES_ADDED | DEBUG_PAGE_LEVEL)) { LogLock logLock; - Btn::printKey ("insertion key: ", key, 0, false); - Btn::printKey (" appended key: ", &searchKey, 0, false); + Log::debug("\n***** addIndexEntry(%d, %d)\n", recordNumber, indexId); + Btn::printKey ("insertion key", key, 0, false); + Btn::printKey (" appended key", &searchKey, 0, false); } for (int n = 0; n < 3; ++n) { - /*** - if (recordNumber == 172303) - Btn::printKey("page 172303", length, key, 0, false); - ***/ - /* Find insert page and position on page */ Bdb *bdb = findInsertionLeaf(dbb, indexId, &searchKey, recordNumber, transId); @@ -190,8 +186,8 @@ if (n) { ++dbb->debug; - Btn::printKey ("Key: ", key, 0, false); - Btn::printKey ("SearchKey: ", &searchKey, 0, false); + Btn::printKey ("Key", key, 0, false); + Btn::printKey ("SearchKey", &searchKey, 0, false); Bdb *bdb = findInsertionLeaf (dbb, indexId, &searchKey, recordNumber, transId); IndexPage *page = (IndexPage*) bdb->buffer; @@ -278,7 +274,6 @@ return bdb; } - while (page->level > 0) { IndexNode node (page->findNodeInBranch(indexKey, recordNumber)); @@ -296,12 +291,17 @@ } int level = page->level; + int32 nextPage = page->nextPage; int32 parentPage = bdb->pageNumber; bdb = dbb->handoffPage(bdb, pageNumber, PAGE_btree, (page->level > 1) ? Shared : Exclusive); page = (IndexPage*) bdb->buffer; - ASSERT(page->level == level - 1); + + // Verify that the new page is either a child page or the next page on + // the same level. + + ASSERT((page->level == level - 1) || (pageNumber == nextPage)); ASSERT(page->level > 0 || bdb->lockType == Exclusive); if (dbb->debug & (DEBUG_PAGES | DEBUG_FIND_LEAF)) @@ -507,8 +507,17 @@ Bdb *leftBdb = dbb->allocPage(PAGE_btree, transId); IndexPage *leftPage = (IndexPage*) leftBdb->buffer; memcpy(leftPage, page, page->length); +// leftPage->pageNumber = leftBdb->pageNumber; splitPage->priorPage = leftBdb->pageNumber; + // Create a node referencing the leftmost page. Assign to it a null key + // and record number 0 to ensure that all nodes are inserted after it. + + IndexKey leftKey(indexKey->index); + + if (leftPage->level == 0) + leftKey.appendRecordNumber(0); + // Reinitialize the parent page page->level = splitPage->level + 1; @@ -517,9 +526,9 @@ IndexKey dummy(indexKey->index); dummy.keyLength = 0; page->length = OFFSET (IndexPage*, nodes); - page->addNode (dbb, &dummy, END_LEVEL); - page->addNode (dbb, &dummy, leftBdb->pageNumber); - page->addNode (dbb, &splitKey, splitBdb->pageNumber); + page->addNode(dbb, &dummy, END_LEVEL); + page->addNode(dbb, &leftKey, leftBdb->pageNumber); + page->addNode(dbb, &splitKey, splitBdb->pageNumber); leftPage->parentPage = bdb->pageNumber; splitPage->parentPage = bdb->pageNumber; @@ -533,6 +542,16 @@ IndexPage::printPage(splitBdb, false); ***/ + if (dbb->debug & DEBUG_PAGE_LEVEL) + { + Log::debug("\n***** splitIndexPage(%d, %d) - NEW LEVEL: Parent page = %d\n", recordNumber, indexId, bdb->pageNumber); + page->printPage(page, 0, false, false); + Log::debug("\n***** splitIndexPage(%d, %d) - NEW LEVEL: Left page = %d \n" , recordNumber, indexId, leftBdb->pageNumber); + page->printPage(leftPage, 0, true, false); + Log::debug("\n***** splitIndexPage(%d, %d) - NEW LEVEL: Split page = %d \n", recordNumber, indexId, splitBdb->pageNumber); + page->printPage(splitPage, 0, false, false); + } + dbb->setPrecedence(leftBdb, splitBdb->pageNumber); dbb->setPrecedence(bdb, leftBdb->pageNumber); splitBdb->release(); @@ -592,8 +611,8 @@ if (dbb->debug & (DEBUG_KEYS | DEBUG_NODES_DELETED)) { - Btn::printKey ("deletion key: ", key, 0, false); - Btn::printKey (" search key: ", &searchKey, 0, false); + Btn::printKey ("deletion key", key, 0, false); + Btn::printKey (" search key", &searchKey, 0, false); } // Try to delete node. If necessary, chase to next page. @@ -866,11 +885,12 @@ IndexKey searchKey(key); searchKey.appendRecordNumber(recordNumber); - if (dbb->debug & (DEBUG_KEYS | DEBUG_NODES_DELETED)) + if (dbb->debug & (DEBUG_KEYS | DEBUG_NODES_DELETED | DEBUG_PAGE_LEVEL)) { LogLock logLock; - Btn::printKey ("insertion key: ", &key, 0, false); - Btn::printKey (" appended key: ", &searchKey, 0, false); + Log::debug("\n***** indexMerge(%d, %d) - Key\n", recordNumber, indexId); + Btn::printKey ("insertion key", &key, 0, false); + Btn::printKey (" appended key", &searchKey, 0, false); } Bdb *bdb = findInsertionLeaf(dbb, indexId, &searchKey, recordNumber, transId); --- 1.3/storage/falcon/Page.h 2007-04-23 08:50:36 -05:00 +++ 1.4/storage/falcon/Page.h 2007-06-06 21:17:04 -05:00 @@ -45,6 +45,10 @@ short pageType; short checksum; + +#ifdef DEBUG_INDEX_PAGE + int32 pageNumber; +#endif }; #endif // !defined(AFX_PAGE_H__6A019C1D_A340_11D2_AB5A_0000C01D2301__INCLUDED_) --- 1.13/storage/falcon/PageInventoryPage.cpp 2007-04-23 08:50:36 -05:00 +++ 1.14/storage/falcon/PageInventoryPage.cpp 2007-06-06 21:17:04 -05:00 @@ -103,6 +103,9 @@ Log::debug("page %d allocated\n", pageNumber); #endif +#ifdef DEBUG_INDEX_PAGE + newBdb->buffer->pageNumber = pageNumber; +#endif return newBdb; } }