From c38559a3725bc74cd7d1fe09aad3554fb2eea3a7 Mon Sep 17 00:00:00 2001 From: Robert Haas Date: Fri, 28 Feb 2014 13:27:09 -0500 Subject: [PATCH] Fix bugs. --- src/backend/utils/mmgr/freepage.c | 257 ++++++++++++++++++------------ 1 file changed, 156 insertions(+), 101 deletions(-) diff --git a/src/backend/utils/mmgr/freepage.c b/src/backend/utils/mmgr/freepage.c index cdcea73c36..2c1845a79b 100644 --- a/src/backend/utils/mmgr/freepage.c +++ b/src/backend/utils/mmgr/freepage.c @@ -105,18 +105,19 @@ static Size FreePageBtreeSearchInternal(FreePageBtree *btp, Size first_page); static Size FreePageBtreeSearchLeaf(FreePageBtree *btp, Size first_page); static FreePageBtree *FreePageBtreeSplitPage(FreePageManager *fpm, FreePageBtree *btp); +static void FreePageBtreeUpdateParentPointers(char *base, FreePageBtree *btp); static void FreePageManagerDumpBtree(FreePageManager *fpm, FreePageBtree *btp, - int level, StringInfo buf); + FreePageBtree *parent, int level, StringInfo buf); static void FreePageManagerDumpSpans(FreePageManager *fpm, FreePageSpanLeader *span, Size expected_pages, StringInfo buf); static bool FreePageManagerGetInternal(FreePageManager *fpm, Size npages, Size *first_page); +static bool FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, + Size npages, bool soft); static void FreePagePopSpanLeader(FreePageManager *fpm, Size pageno); static void FreePagePushSpanLeader(FreePageManager *fpm, Size first_page, Size npages); -static bool FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, - Size npages, bool soft); /* * Initialize a new, empty free page manager. @@ -235,7 +236,7 @@ FreePageManagerDump(FreePageManager *fpm) appendStringInfo(&buf, "btree depth %u:\n", fpm->btree_depth); root = relptr_access(base, fpm->btree_root); - FreePageManagerDumpBtree(fpm, root, 0, &buf); + FreePageManagerDumpBtree(fpm, root, NULL, 0, &buf); } else if (fpm->singleton_npages > 0) { @@ -474,12 +475,18 @@ FreePageBtreeConsolidate(FreePageManager *fpm, FreePageBtree *btp) if (np != NULL && btp->hdr.nused + np->hdr.nused <= max) { if (btp->hdr.magic == FREE_PAGE_LEAF_MAGIC) + { memcpy(&btp->u.leaf_key[btp->hdr.nused], &np->u.leaf_key[0], sizeof(FreePageBtreeLeafKey) * np->hdr.nused); + btp->hdr.nused += np->hdr.nused; + } else + { memcpy(&btp->u.internal_key[btp->hdr.nused], &np->u.internal_key[0], sizeof(FreePageBtreeInternalKey) * np->hdr.nused); - btp->hdr.nused += np->hdr.nused; + btp->hdr.nused += np->hdr.nused; + FreePageBtreeUpdateParentPointers(base, btp); + } FreePageBtreeRemovePage(fpm, np); return; } @@ -493,11 +500,18 @@ FreePageBtreeConsolidate(FreePageManager *fpm, FreePageBtree *btp) if (np != NULL && btp->hdr.nused + np->hdr.nused <= max) { if (btp->hdr.magic == FREE_PAGE_LEAF_MAGIC) + { memcpy(&np->u.leaf_key[np->hdr.nused], &btp->u.leaf_key[0], sizeof(FreePageBtreeLeafKey) * btp->hdr.nused); + np->hdr.nused += btp->hdr.nused; + } else + { memcpy(&np->u.internal_key[np->hdr.nused], &btp->u.internal_key[0], sizeof(FreePageBtreeInternalKey) * btp->hdr.nused); + np->hdr.nused += btp->hdr.nused; + FreePageBtreeUpdateParentPointers(base, np); + } np->hdr.nused += btp->hdr.nused; FreePageBtreeRemovePage(fpm, btp); return; @@ -520,15 +534,16 @@ FreePageBtreeFindLeftSibling(char *base, FreePageBtree *btp) Size first_page; Size index; + first_page = FreePageBtreeFirstKey(p); p = relptr_access(base, p->hdr.parent); if (p == NULL) return NULL; /* we were passed the rightmost page */ - first_page = FreePageBtreeFirstKey(p); index = FreePageBtreeSearchInternal(p, first_page); if (index > 0) { + Assert(p->u.internal_key[index].first_page == first_page); p = relptr_access(base, p->u.internal_key[index - 1].child); break; } @@ -564,15 +579,16 @@ FreePageBtreeFindRightSibling(char *base, FreePageBtree *btp) Size first_page; Size index; + first_page = FreePageBtreeFirstKey(p); p = relptr_access(base, p->hdr.parent); if (p == NULL) return NULL; /* we were passed the rightmost page */ - first_page = FreePageBtreeFirstKey(p); index = FreePageBtreeSearchInternal(p, first_page); if (index < p->hdr.nused - 1) { + Assert(p->u.internal_key[index].first_page == first_page); p = relptr_access(base, p->u.internal_key[index + 1].child); break; } @@ -724,12 +740,11 @@ FreePageBtreeRemovePage(FreePageManager *fpm, FreePageBtree *btp) { char *base = fpm_segment_base(fpm); FreePageBtree *parent; + Size index; + Size first_page; for (;;) { - Size index; - Size first_page; - /* Find parent page. */ parent = relptr_access(base, btp->hdr.parent); if (parent == NULL) @@ -742,48 +757,49 @@ FreePageBtreeRemovePage(FreePageManager *fpm, FreePageBtree *btp) return; } - /* Find and remove the downlink. */ - first_page = FreePageBtreeFirstKey(btp); - if (parent->hdr.magic == FREE_PAGE_LEAF_MAGIC) - { - index = FreePageBtreeSearchLeaf(parent, first_page); - Assert(index < parent->hdr.nused); - if (index < parent->hdr.nused - 1) - memmove(&parent->u.leaf_key[index], - &parent->u.leaf_key[index + 1], - sizeof(FreePageBtreeLeafKey) - * (parent->hdr.nused - index - 1)); - } - else - { - index = FreePageBtreeSearchInternal(parent, first_page); - Assert(index < parent->hdr.nused); - if (index < parent->hdr.nused - 1) - memmove(&parent->u.internal_key[index], - &parent->u.internal_key[index + 1], - sizeof(FreePageBtreeInternalKey) - * (btp->hdr.nused - index - 1)); - } - parent->hdr.nused--; - - /* Recycle target page. */ - FreePageBtreeRecycle(fpm, fpm_pointer_to_page(base, btp)); - /* - * If the parent has become empty in turn, we must loop around and - * remove it in turn. If not, we can break out of the loop, but must - * adjust ancestor keys if we updated the first key on the page. + * If the parent contains only one item, we need to remove it as + * well. */ - if (parent->hdr.nused > 0) - { - if (index == 0) - FreePageBtreeAdjustAncestorKeys(fpm, parent); + if (parent->hdr.nused > 1) break; - } + FreePageBtreeRecycle(fpm, fpm_pointer_to_page(base, btp)); btp = parent; } - /* Consider whether to consolidate the parent with a sibings. */ + /* Find and remove the downlink. */ + first_page = FreePageBtreeFirstKey(btp); + if (parent->hdr.magic == FREE_PAGE_LEAF_MAGIC) + { + index = FreePageBtreeSearchLeaf(parent, first_page); + Assert(index < parent->hdr.nused); + if (index < parent->hdr.nused - 1) + memmove(&parent->u.leaf_key[index], + &parent->u.leaf_key[index + 1], + sizeof(FreePageBtreeLeafKey) + * (parent->hdr.nused - index - 1)); + } + else + { + index = FreePageBtreeSearchInternal(parent, first_page); + Assert(index < parent->hdr.nused); + if (index < parent->hdr.nused - 1) + memmove(&parent->u.internal_key[index], + &parent->u.internal_key[index + 1], + sizeof(FreePageBtreeInternalKey) + * (parent->hdr.nused - index - 1)); + } + parent->hdr.nused--; + Assert(parent->hdr.nused > 0); + + /* Recycle the page. */ + FreePageBtreeRecycle(fpm, fpm_pointer_to_page(base, btp)); + + /* Adjust ancestor keys if needed. */ + if (index == 0) + FreePageBtreeAdjustAncestorKeys(fpm, parent); + + /* Consider whether to consolidate the parent with a sibling. */ FreePageBtreeConsolidate(fpm, parent); } @@ -838,8 +854,17 @@ FreePageBtreeSearch(FreePageManager *fpm, Size first_page, else result->split_pages = 0; + /* Descend to appropriate child page. */ + Assert(index < btp->hdr.nused); child = relptr_access(base, btp->u.internal_key[index].child); - Assert(relptr_access(base, child->hdr.parent) == btp); + if (relptr_access(base, child->hdr.parent) != btp) + { + elog(LOG, "btp = %zu, child = %zu, child parent = %zu", + fpm_pointer_to_page(base, btp), + fpm_pointer_to_page(base, child), + fpm_pointer_to_page(base, relptr_access(base, child->hdr.parent))); + elog(FATAL, "%s", FreePageManagerDump(fpm)); + } btp = child; } @@ -949,25 +974,52 @@ FreePageBtreeSplitPage(FreePageManager *fpm, FreePageBtree *btp) memcpy(&newsibling->u.internal_key, &btp->u.internal_key[btp->hdr.nused], sizeof(FreePageBtreeInternalKey) * newsibling->hdr.nused); + FreePageBtreeUpdateParentPointers(fpm_segment_base(fpm), newsibling); } return newsibling; } +/* + * When internal pages are split or merged, the parent pointers of their + * children must be updated. + */ +static void +FreePageBtreeUpdateParentPointers(char *base, FreePageBtree *btp) +{ + Size i; + + Assert(btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC); + for (i = 0; i < btp->hdr.nused; ++i) + { + FreePageBtree *child; + + child = relptr_access(base, btp->u.internal_key[i].child); + relptr_store(base, child->hdr.parent, btp); + } +} + /* * Debugging dump of btree data. */ static void -FreePageManagerDumpBtree(FreePageManager *fpm, FreePageBtree *btp, int level, - StringInfo buf) +FreePageManagerDumpBtree(FreePageManager *fpm, FreePageBtree *btp, + FreePageBtree *parent, int level, StringInfo buf) { char *base = fpm_segment_base(fpm); Size pageno = fpm_pointer_to_page(base, btp); Size index; + FreePageBtree *check_parent; check_stack_depth(); - appendStringInfo(buf, " %zu@%d %c:", pageno, level, + check_parent = relptr_access(base, btp->hdr.parent); + appendStringInfo(buf, " %zu@%d %c", pageno, level, btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC ? 'i' : 'l'); + if (parent != check_parent) + appendStringInfo(buf, " [actual parent %zu, expected %zu]", + fpm_pointer_to_page(base, check_parent), + fpm_pointer_to_page(base, parent)); + appendStringInfoChar(buf, ':'); for (index = 0; index < btp->hdr.nused; ++index) { if (btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC) @@ -988,7 +1040,7 @@ FreePageManagerDumpBtree(FreePageManager *fpm, FreePageBtree *btp, int level, FreePageBtree *child; child = relptr_access(base, btp->u.internal_key[index].child); - FreePageManagerDumpBtree(fpm, child, level + 1, buf); + FreePageManagerDumpBtree(fpm, child, btp, level + 1, buf); } } } @@ -1145,56 +1197,6 @@ FreePageManagerGetInternal(FreePageManager *fpm, Size npages, Size *first_page) return true; } -/* - * Remove a FreePageSpanLeader from the linked-list that contains it, either - * because we're changing the size of the span, or because we're allocating it. - */ -static void -FreePagePopSpanLeader(FreePageManager *fpm, Size pageno) -{ - char *base = fpm_segment_base(fpm); - FreePageSpanLeader *span; - FreePageSpanLeader *next; - FreePageSpanLeader *prev; - - span = (FreePageSpanLeader *) fpm_page_to_pointer(base, pageno); - - next = relptr_access(base, span->next); - prev = relptr_access(base, span->prev); - if (next != NULL) - relptr_copy(next->prev, span->prev); - if (prev != NULL) - relptr_copy(prev->next, span->next); - else - { - Size f = Min(span->npages, FPM_NUM_FREELISTS) - 1; - - Assert(fpm->freelist[f].relptr_off == pageno * FPM_PAGE_SIZE); - relptr_copy(fpm->freelist[f], span->next); - } -} - -/* - * Initialize a new FreePageSpanLeader and put it on the appropriate free list. - */ -static void -FreePagePushSpanLeader(FreePageManager *fpm, Size first_page, Size npages) -{ - char *base = fpm_segment_base(fpm); - Size f = Min(npages, FPM_NUM_FREELISTS) - 1; - FreePageSpanLeader *head = relptr_access(base, fpm->freelist[f]); - FreePageSpanLeader *span; - - span = (FreePageSpanLeader *) fpm_page_to_pointer(base, first_page); - span->magic = FREE_PAGE_SPAN_LEADER_MAGIC; - span->npages = npages; - relptr_store(base, span->next, head); - relptr_store(base, span->prev, (FreePageSpanLeader *) NULL); - if (head != NULL) - relptr_store(base, head->prev, span); - relptr_store(base, fpm->freelist[f], span); -} - /* * Put a range of pages into the btree and freelists, consolidating it with * existing free spans just before and/or after it. If 'soft' is true, @@ -1470,6 +1472,7 @@ FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, index = FreePageBtreeSearchInternal(insert_into, key); FreePageBtreeInsertInternal(base, insert_into, index, key, child); + relptr_store(base, child->hdr.parent, insert_into); if (index == 0 && insert_into == split_target) FreePageBtreeAdjustAncestorKeys(fpm, split_target); } @@ -1509,6 +1512,7 @@ FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, index = FreePageBtreeSearchInternal(parent, key); FreePageBtreeInsertInternal(base, parent, index, key, newsibling); + relptr_store(base, newsibling->hdr.parent, parent); if (index == 0) FreePageBtreeAdjustAncestorKeys(fpm, parent); break; @@ -1524,6 +1528,7 @@ FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, * free list, and we're done. */ FreePagePushSpanLeader(fpm, first_page, npages); + return true; } } @@ -1541,3 +1546,53 @@ FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, return true; } + +/* + * Remove a FreePageSpanLeader from the linked-list that contains it, either + * because we're changing the size of the span, or because we're allocating it. + */ +static void +FreePagePopSpanLeader(FreePageManager *fpm, Size pageno) +{ + char *base = fpm_segment_base(fpm); + FreePageSpanLeader *span; + FreePageSpanLeader *next; + FreePageSpanLeader *prev; + + span = (FreePageSpanLeader *) fpm_page_to_pointer(base, pageno); + + next = relptr_access(base, span->next); + prev = relptr_access(base, span->prev); + if (next != NULL) + relptr_copy(next->prev, span->prev); + if (prev != NULL) + relptr_copy(prev->next, span->next); + else + { + Size f = Min(span->npages, FPM_NUM_FREELISTS) - 1; + + Assert(fpm->freelist[f].relptr_off == pageno * FPM_PAGE_SIZE); + relptr_copy(fpm->freelist[f], span->next); + } +} + +/* + * Initialize a new FreePageSpanLeader and put it on the appropriate free list. + */ +static void +FreePagePushSpanLeader(FreePageManager *fpm, Size first_page, Size npages) +{ + char *base = fpm_segment_base(fpm); + Size f = Min(npages, FPM_NUM_FREELISTS) - 1; + FreePageSpanLeader *head = relptr_access(base, fpm->freelist[f]); + FreePageSpanLeader *span; + + span = (FreePageSpanLeader *) fpm_page_to_pointer(base, first_page); + span->magic = FREE_PAGE_SPAN_LEADER_MAGIC; + span->npages = npages; + relptr_store(base, span->next, head); + relptr_store(base, span->prev, (FreePageSpanLeader *) NULL); + if (head != NULL) + relptr_store(base, head->prev, span); + relptr_store(base, fpm->freelist[f], span); +} -- 2.39.5