From 36530bfd4b37d74464c11d16b4dd322e0b4e3870 Mon Sep 17 00:00:00 2001 From: Robert Haas Date: Fri, 21 Feb 2014 00:41:13 -0500 Subject: [PATCH] Fix bugs. --- src/backend/utils/mmgr/freepage.c | 174 ++++++++++++++---------------- 1 file changed, 80 insertions(+), 94 deletions(-) diff --git a/src/backend/utils/mmgr/freepage.c b/src/backend/utils/mmgr/freepage.c index 25fd13700e..45bfc4a80f 100644 --- a/src/backend/utils/mmgr/freepage.c +++ b/src/backend/utils/mmgr/freepage.c @@ -75,12 +75,9 @@ struct FreePageBtree /* Results of a btree search */ typedef struct FreePageBtreeSearchResult { - FreePageBtree *page_exact; - Size index_exact; - FreePageBtree *page_next; - Size index_next; - FreePageBtree *page_prev; - Size index_prev; + FreePageBtree *page; + Size index; + bool found; unsigned split_pages; } FreePageBtreeSearchResult; @@ -348,6 +345,7 @@ FreePageBtreeAdjustAncestorKeys(FreePageManager *fpm, FreePageBtree *btp) { FreePageBtree *check; + check = relptr_access(base, parent->u.internal_key[s].child); Assert(s < parent->hdr.nused); Assert(child == check); } @@ -547,17 +545,13 @@ FreePageBtreeRemove(FreePageManager *fpm, FreePageBtree *btp, Size index) /* * Search the btree for an entry for the given first page and initialize - * *result with the results of the search. If an exact match is found, - * result->page_exact and result->index_exact will be set to the page and - * slot where it is located. Otherwise, result->page_exact will be NULL; - * result->page_next and result->index_next will indicate the point at which - * the key could be inserted; and result->page_prev and result->index_prev - * will indicate the preceding key (unless the proposed first_page would - * precede everything currently in the tree, in which case result->page_prev - * will be NULL). result->split_pages will contain the number of additional - * btree pages that will be needed when performing a split to insert a key into - * result->page_exact or result->page_next. Except as described above, the - * contents of fields in the result object are undefined on return. + * *result with the results of the search. result->page and result->index + * indicate either the position of an exact match or the position at which + * the new key should be inserted. result->found is true for an exact match, + * otherwise false. result->split_pages will contain the number of additional + * btree pages that will be needed when performing a split to insert a key. + * Except as described above, the contents of fields in the result object are + * undefined on return. */ static void FreePageBtreeSearch(FreePageManager *fpm, Size first_page, @@ -572,20 +566,21 @@ FreePageBtreeSearch(FreePageManager *fpm, Size first_page, /* If the btree is empty, there's nothing to find. */ if (btp == NULL) { - result->page_exact = NULL; - result->page_next = NULL; - result->page_prev = NULL; + result->page = NULL; + result->found = false; return; } /* Descend until we hit a leaf. */ while (btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC) { + FreePageBtree *child; + index = FreePageBtreeSearchInternal(btp, first_page); /* * If the index is 0, we're not going to find it, but we keep - * descending anyway so that we can find the element that follows it. + * descending anyway so that we can find the insertion point. */ if (index > 0) --index; @@ -599,7 +594,9 @@ FreePageBtreeSearch(FreePageManager *fpm, Size first_page, else result->split_pages = 0; - btp = relptr_access(base, btp->u.internal_key[index].child); + child = relptr_access(base, btp->u.internal_key[index].child); + Assert(relptr_access(base, child->hdr.parent) == btp); + btp = child; } /* Track required split depth for leaf insert. */ @@ -613,57 +610,12 @@ FreePageBtreeSearch(FreePageManager *fpm, Size first_page, /* Search leaf page. */ index = FreePageBtreeSearchLeaf(btp, first_page); - if (index < btp->hdr.nused && - first_page == btp->u.leaf_key[index].first_page) - { - /* Exact match. */ - result->page_exact = btp; - result->index_exact = index; - return; /* No need to set previous key in this case. */ - } - - /* No exact match; indicate insertion position. */ - result->page_exact = NULL; - result->page_next = btp; - result->index_next = index; - - /* Find the previous key. */ - if (index > 0) - { - /* Previous key on same page. */ - result->page_prev = btp; - result->index_prev = index - 1; - } - else - { - /* Walk up tree until we can move left. */ - while (index == 0) - { - btp = relptr_access(base, btp->hdr.parent); - if (btp == NULL) - { - /* We're the first key in the btree. */ - result->page_prev = NULL; - return; - } - index = FreePageBtreeSearchInternal(btp, first_page); - } - - /* Move left. */ - btp = relptr_access(base, btp->u.internal_key[index - 1].child); - - /* Descend right. */ - while (btp->hdr.magic == FREE_PAGE_INTERNAL_MAGIC) - { - Size nused = btp->hdr.nused; - btp = relptr_access(base, btp->u.internal_key[nused - 1].child); - } - - /* Get rightmost key on page. */ - result->page_prev = btp; - result->index_prev = btp->hdr.nused - 1; - } + /* Assemble results. */ + result->page = btp; + result->index = index; + result->found = index < btp->hdr.nused && + first_page == btp->u.leaf_key[index].first_page; } /* @@ -922,21 +874,21 @@ FreePageManagerGetInternal(FreePageManager *fpm, Size npages, Size *first_page) * appropriate free list. */ FreePageBtreeSearch(fpm, victim_page, &result); - Assert(result.page_exact != NULL); + Assert(result.found); if (victim->npages == npages) - FreePageBtreeRemove(fpm, result.page_exact, result.index_exact); + FreePageBtreeRemove(fpm, result.page, result.index); else { FreePageBtreeLeafKey *key; /* Adjust btree to reflect remaining pages. */ Assert(victim->npages > npages); - key = &result.page_exact->u.leaf_key[result.index_exact]; + key = &result.page->u.leaf_key[result.index]; Assert(key->npages == victim->npages); key->first_page += npages; key->npages -= npages; - if (result.index_exact == 0) - FreePageBtreeAdjustAncestorKeys(fpm, result.page_exact); + if (result.index == 0) + FreePageBtreeAdjustAncestorKeys(fpm, result.page); /* Put the unallocated pages back on the appropriate free list. */ FreePagePushSpanLeader(fpm, victim_page + npages, @@ -1014,6 +966,8 @@ FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, FreePageBtreeSearchResult result; FreePageBtreeLeafKey *prevkey = NULL; FreePageBtreeLeafKey *nextkey = NULL; + FreePageBtree *np; + Size nindex; /* We can store a single free span without initializing the btree. */ if (fpm->btree_depth == 0) @@ -1079,11 +1033,43 @@ FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, /* Search the btree. */ FreePageBtreeSearch(fpm, first_page, &result); - Assert(result.page_exact == NULL); /* can't already be there */ - if (result.page_prev != NULL) - prevkey = &result.page_prev->u.leaf_key[result.index_prev]; - if (result.index_next < result.page_next->hdr.nused) - nextkey = &result.page_next->u.leaf_key[result.index_next]; + Assert(!result.found); + if (result.index > 0) + prevkey = &result.page->u.leaf_key[result.index - 1]; + if (result.index < result.page->hdr.nused) + { + np = result.page; + nindex = result.index; + nextkey = &result.page->u.leaf_key[result.index]; + } + else + { + /* + * We need to find the right sibling of the insertion point to + * determine whether we can consolidate with the following key. + * Move up until we can move right; then descend left. + */ + np = result.page; + for (;;) + { + np = relptr_access(base, np->hdr.parent); + if (np == NULL) + break; /* no next key exists */ + nindex = FreePageBtreeSearchInternal(np, first_page); + if (nindex < np->hdr.nused) + { + np = relptr_access(base, np->u.internal_key[nindex].child); + break; + } + } + if (np != NULL) + { + while (np->hdr.magic == FREE_PAGE_INTERNAL_MAGIC) + np = relptr_access(base, np->u.internal_key[0].child); + nextkey = &np->u.leaf_key[0]; + nindex = 0; + } + } /* Consolidate with the previous entry if possible. */ if (prevkey != NULL && prevkey->first_page + prevkey->npages >= first_page) @@ -1101,6 +1087,7 @@ FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, nextkey->first_page); prevkey->npages = (nextkey->first_page - prevkey->first_page) + nextkey->npages; + FreePagePopSpanLeader(fpm, nextkey->first_page); remove_next = true; } @@ -1119,7 +1106,7 @@ FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, * as nextkey. FreePageBtreeRemove() shouldn't notice that, though. */ if (remove_next) - FreePageBtreeRemove(fpm, result.page_next, result.index_next); + FreePageBtreeRemove(fpm, np, nindex); return true; } @@ -1142,8 +1129,8 @@ FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, nextkey->npages = newpages; /* If reducing first key on page, ancestors might need adjustment. */ - if (result.index_next == 0) - FreePageBtreeAdjustAncestorKeys(fpm, result.page_next); + if (nindex == 0) + FreePageBtreeAdjustAncestorKeys(fpm, np); return true; } @@ -1153,9 +1140,9 @@ FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, { /* * XXX. Try any coping strategies we want to use to avoid a split, - * such as inserting on page_prev instead of page_next, or shuffling + * such as inserting to np if np != result.page, or shuffling * keys between siblings. If any of those strategies work, make - * sure to update result.split_pages. + * sure to update result.split_pages, or just return. */ /* If this is a soft insert, it's time to give up. */ @@ -1209,7 +1196,7 @@ FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, /* If we still need to perform a split, do it. */ if (result.split_pages > 0) { - FreePageBtree *split_target = result.page_next; + FreePageBtree *split_target = result.page; FreePageBtree *child = NULL; Size key = first_page; @@ -1274,7 +1261,7 @@ FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, FreePageBtreeFirstKey(split_target); relptr_store(base, newroot->u.internal_key[0].child, split_target); - relptr_store(base, newroot->hdr.parent, newroot); + relptr_store(base, split_target->hdr.parent, newroot); newroot->u.internal_key[1].first_page = FreePageBtreeFirstKey(newsibling); relptr_store(base, newroot->u.internal_key[1].child, @@ -1315,13 +1302,12 @@ FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, } /* Physically add the key to the page. */ - Assert(result.page_next->hdr.nused < FPM_ITEMS_PER_LEAF_PAGE); - FreePageBtreeInsertLeaf(result.page_next, result.index_next, - first_page, npages); + Assert(result.page->hdr.nused < FPM_ITEMS_PER_LEAF_PAGE); + FreePageBtreeInsertLeaf(result.page, result.index, first_page, npages); /* If new first key on page, ancestors might need adjustment. */ - if (result.index_next == 0) - FreePageBtreeAdjustAncestorKeys(fpm, result.page_next); + if (result.index == 0) + FreePageBtreeAdjustAncestorKeys(fpm, result.page); /* Put it on the free list. */ FreePagePushSpanLeader(fpm, first_page, npages); -- 2.39.5