From 0756819e460acb958eeb073f4d5ca9ddf66ec6c7 Mon Sep 17 00:00:00 2001 From: unknown Date: Wed, 19 Feb 2014 08:48:28 -0800 Subject: [PATCH] Make bt_splitpage more conservative wrt posting fence keys --- btree2s.c | 60 ++++++++++++++------------------------------ threads2h.c | 72 +++++++++++++++++++---------------------------------- threads2i.c | 70 +++++++++++++++++++-------------------------------- threads2j.c | 72 +++++++++++++++++++---------------------------------- 4 files changed, 95 insertions(+), 179 deletions(-) diff --git a/btree2s.c b/btree2s.c index 586dea7..49b9109 100644 --- a/btree2s.c +++ b/btree2s.c @@ -121,10 +121,9 @@ typedef struct { uint min; // next key offset unsigned char bits:7; // page size in bits unsigned char free:1; // page is on free list - unsigned char lvl:5; // level of page + unsigned char lvl:6; // level of page unsigned char kill:1; // page is being deleted unsigned char dirty:1; // page is dirty - unsigned char posted:1; // page is posted in parent unsigned char right[BtId]; // page number to right } *BtPage; @@ -1500,11 +1499,10 @@ uid right; BTERR bt_splitpage (BtDb *bt) { uint cnt = 0, idx = 0, max, nxt = bt->page_size; +unsigned char fencekey[256], rightkey[256]; uid page_no = bt->page_no, right; -unsigned char fencekey[256]; BtPage page = bt->page; uint lvl = page->lvl; -uint prev; BtKey key; // split higher half of keys to bt->frame @@ -1526,6 +1524,10 @@ BtKey key; slotptr(bt->frame, idx)->off = nxt; } + // remember fence key for new right page + + memcpy (rightkey, key, key->len + 1); + bt->frame->bits = bt->page_bits; bt->frame->min = nxt; bt->frame->cnt = idx; @@ -1546,7 +1548,6 @@ BtKey key; memcpy (bt->frame, page, bt->page_size); memset (page+1, 0, bt->page_size - sizeof(*page)); nxt = bt->page_size; - page->posted = 0; page->dirty = 0; page->act = 0; cnt = 0; @@ -1568,6 +1569,7 @@ BtKey key; // remember fence key for smaller page memcpy (fencekey, key, key->len + 1); + bt_putid(page->right, right); page->min = nxt; page->cnt = idx; @@ -1577,59 +1579,33 @@ BtKey key; if( page_no == ROOT_page ) return bt_splitroot (bt, fencekey, right); - // update left (containing) node + // lock right page - if( bt_update(bt, page, page_no) ) + if( bt_lockpage (bt, right, BtLockParent) ) return bt->err; - right = 0; - - // insert new fences in parent pages + // update left (containing) node - while( 1 ) { - if( bt_lockpage (bt, page_no, BtLockParent) ) + if( bt_update(bt, page, page_no) ) return bt->err; - if( right ) - if( bt_mappage (bt, &bt->page, page_no) ) + if( bt_lockpage (bt, page_no, BtLockParent) ) return bt->err; - key = keyptr(bt->page, bt->page->cnt); - memcpy (fencekey, key, key->len + 1); - prev = bt->page->posted; - - if( right && prev ) { - if( bt_unlockpage (bt, page_no, BtLockParent) ) - return bt->err; - return bt_unlockpage (bt, page_no, BtLockWrite); - } - - right = bt_getid (bt->page->right); - bt->page->posted = 1; + // insert new fence for reformulated left block - if( bt_update (bt, bt->page, page_no) ) + if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, page_no, time(NULL)) ) return bt->err; - if( bt_unlockpage (bt, page_no, BtLockWrite) ) - return bt->err; - - // insert new fence for reformulated left block - - if( !prev ) - if( bt_insertkey (bt, fencekey+1, *fencekey, lvl + 1, page_no, time(NULL)) ) - return bt->err; + // switch fence for right block of larger keys to new right page - if( bt_unlockpage (bt, page_no, BtLockParent) ) + if( bt_insertkey (bt, rightkey+1, *rightkey, lvl+1, right, time(NULL)) ) return bt->err; - if( !(page_no = right) ) - break; - - if( bt_lockpage (bt, page_no, BtLockWrite) ) + if( bt_unlockpage (bt, page_no, BtLockParent) ) return bt->err; - } - return 0; + return bt_unlockpage (bt, right, BtLockParent); } // Insert new key into the btree at requested level. diff --git a/threads2h.c b/threads2h.c index 46742c4..4a28044 100644 --- a/threads2h.c +++ b/threads2h.c @@ -170,10 +170,9 @@ typedef struct BtPage_ { uint min; // next key offset unsigned char bits:7; // page size in bits unsigned char free:1; // page is on free list - unsigned char lvl:5; // level of page + unsigned char lvl:6; // level of page unsigned char kill:1; // page is being killed unsigned char dirty:1; // page has deleted keys - unsigned char posted:1; // page fence is posted unsigned char right[BtId]; // page number to right } *BtPage; @@ -1964,10 +1963,10 @@ uid left; BTERR bt_splitpage (BtDb *bt, BtPageSet *set) { uint cnt = 0, idx = 0, max, nxt = bt->mgr->page_size; -unsigned char fencekey[256]; +unsigned char fencekey[256], rightkey[256]; uint lvl = set->page->lvl; +BtPageSet right[1]; uint prev; -uid right; BtKey key; // split higher half of keys to bt->frame @@ -1989,6 +1988,10 @@ BtKey key; slotptr(bt->frame, idx)->off = nxt; } + // remember existing fence key for new page to the right + + memcpy (rightkey, key, key->len + 1); + bt->frame->bits = bt->mgr->page_bits; bt->frame->min = nxt; bt->frame->cnt = idx; @@ -2001,7 +2004,7 @@ BtKey key; // get new free page and write higher keys to it. - if( !(right = bt_newpage(bt, bt->frame)) ) + if( !(right->page_no = bt_newpage(bt, bt->frame)) ) return bt->err; // update lower keys to continue in old page @@ -2009,7 +2012,6 @@ BtKey key; memcpy (bt->frame, set->page, bt->mgr->page_size); memset (set->page+1, 0, bt->mgr->page_size - sizeof(*set->page)); nxt = bt->mgr->page_size; - set->page->posted = 0; set->page->dirty = 0; set->page->act = 0; cnt = 0; @@ -2030,62 +2032,40 @@ BtKey key; // remember fence key for smaller page memcpy(fencekey, key, key->len + 1); - bt_putid(set->page->right, right); + + bt_putid(set->page->right, right->page_no); set->page->min = nxt; set->page->cnt = idx; // if current page is the root page, split it if( set->page_no == ROOT_page ) - return bt_splitroot (bt, set, fencekey, right); - - right = 0; + return bt_splitroot (bt, set, fencekey, right->page_no); // insert new fences in their parent pages - while( 1 ) { - bt_lockpage (BtLockParent, set->latch); - - key = keyptr (set->page, set->page->cnt); - memcpy (fencekey, key, key->len + 1); - prev = set->page->posted; - - if( right && prev ) { - bt_unlockpage (BtLockParent, set->latch); - bt_unlockpage (BtLockWrite, set->latch); - bt_unpinlatch (set->latch); - bt_unpinpool (set->pool); - return 0; - } - - right = bt_getid (set->page->right); - set->page->posted = 1; - - bt_unlockpage (BtLockWrite, set->latch); - - // insert new fence for reformulated left block of smaller keys + right->latch = bt_pinlatch (bt, right->page_no); + bt_lockpage (BtLockParent, right->latch); - if( !prev ) - if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) ) - return bt->err; + bt_lockpage (BtLockParent, set->latch); + bt_unlockpage (BtLockWrite, set->latch); - bt_unlockpage (BtLockParent, set->latch); - bt_unpinlatch (set->latch); - bt_unpinpool (set->pool); + // insert new fence for reformulated left block of smaller keys - if( !(set->page_no = right) ) - break; + if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) ) + return bt->err; - set->latch = bt_pinlatch (bt, right); + // switch fence for right block of larger keys to new right page - if( set->pool = bt_pinpool (bt, right) ) - set->page = bt_page (bt, set->pool, right); - else - return bt->err; + if( bt_insertkey (bt, rightkey+1, *rightkey, lvl+1, right->page_no, time(NULL)) ) + return bt->err; - bt_lockpage (BtLockWrite, set->latch); - } + bt_unlockpage (BtLockParent, set->latch); + bt_unpinlatch (set->latch); + bt_unpinpool (set->pool); + bt_unlockpage (BtLockParent, right->latch); + bt_unpinlatch (right->latch); return 0; } diff --git a/threads2i.c b/threads2i.c index 0c7c41d..c425d18 100644 --- a/threads2i.c +++ b/threads2i.c @@ -1878,10 +1878,10 @@ uid left; BTERR bt_splitpage (BtDb *bt, BtPageSet *set) { uint cnt = 0, idx = 0, max, nxt = bt->mgr->page_size; -unsigned char fencekey[256]; +unsigned char fencekey[256], rightkey[256]; uint lvl = set->page->lvl; +BtPageSet right[1]; uint prev; -uid right; BtKey key; // split higher half of keys to bt->frame @@ -1903,6 +1903,10 @@ BtKey key; slotptr(bt->frame, idx)->off = nxt; } + // remember existing fence key for new page to the right + + memcpy (rightkey, key, key->len + 1); + bt->frame->bits = bt->mgr->page_bits; bt->frame->min = nxt; bt->frame->cnt = idx; @@ -1915,7 +1919,7 @@ BtKey key; // get new free page and write higher keys to it. - if( !(right = bt_newpage(bt, bt->frame)) ) + if( !(right->page_no = bt_newpage(bt, bt->frame)) ) return bt->err; // update lower keys to continue in old page @@ -1923,7 +1927,6 @@ BtKey key; memcpy (bt->frame, set->page, bt->mgr->page_size); memset (set->page+1, 0, bt->mgr->page_size - sizeof(*set->page)); nxt = bt->mgr->page_size; - set->page->posted = 0; set->page->dirty = 0; set->page->act = 0; cnt = 0; @@ -1944,65 +1947,42 @@ BtKey key; // remember fence key for smaller page memcpy(fencekey, key, key->len + 1); - bt_putid(set->page->right, right); + + bt_putid(set->page->right, right->page_no); set->page->min = nxt; set->page->cnt = idx; // if current page is the root page, split it if( set->page_no == ROOT_page ) - return bt_splitroot (bt, set, fencekey, right); - - right = 0; + return bt_splitroot (bt, set, fencekey, right->page_no); // insert new fences in their parent pages - while( 1 ) { - bt_lockpage (BtLockParent, set->latch); - - key = keyptr (set->page, set->page->cnt); - memcpy (fencekey, key, key->len + 1); - prev = set->page->posted; - - if( right && prev ) { - bt_unlockpage (BtLockParent, set->latch); - bt_unlockpage (BtLockWrite, set->latch); - bt_unpinlatch (set->latch); - bt_unpinpool (set->pool); - return 0; - } - - right = bt_getid (set->page->right); - set->page->posted = 1; - - bt_unlockpage (BtLockWrite, set->latch); - - // insert new fence for reformulated left block of smaller keys + right->latch = bt_pinlatch (bt, right->page_no); + bt_lockpage (BtLockParent, right->latch); - if( !prev ) - if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) ) - return bt->err; + bt_lockpage (BtLockParent, set->latch); + bt_unlockpage (BtLockWrite, set->latch); - bt_unlockpage (BtLockParent, set->latch); - bt_unpinlatch (set->latch); - bt_unpinpool (set->pool); + // insert new fence for reformulated left block of smaller keys - if( !(set->page_no = right) ) - break; + if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) ) + return bt->err; - set->latch = bt_pinlatch (bt, right); + // switch fence for right block of larger keys to new right page - if( set->pool = bt_pinpool (bt, right) ) - set->page = bt_page (bt, set->pool, right); - else - return bt->err; + if( bt_insertkey (bt, rightkey+1, *rightkey, lvl+1, right->page_no, time(NULL)) ) + return bt->err; - bt_lockpage (BtLockWrite, set->latch); - } + bt_unlockpage (BtLockParent, set->latch); + bt_unpinlatch (set->latch); + bt_unpinpool (set->pool); + bt_unlockpage (BtLockParent, right->latch); + bt_unpinlatch (right->latch); return 0; } - // Insert new key into the btree at given level. BTERR bt_insertkey (BtDb *bt, unsigned char *key, uint len, uint lvl, uid id, uint tod) diff --git a/threads2j.c b/threads2j.c index ce186a6..a1081b3 100644 --- a/threads2j.c +++ b/threads2j.c @@ -1926,11 +1926,11 @@ uid left; BTERR bt_splitpage (BtDb *bt, BtPageSet *set) { uint cnt = 0, idx = 0, max, nxt = bt->mgr->page_size; -unsigned char fencekey[256]; +unsigned char fencekey[256], rightkey[256]; uint lvl = set->page->lvl; -uid right; -BtKey key; +BtPageSet right[1]; uint prev; +BtKey key; // split higher half of keys to bt->frame @@ -1951,6 +1951,10 @@ uint prev; slotptr(bt->frame, idx)->off = nxt; } + // remember existing fence key for new page to the right + + memcpy (rightkey, key, key->len + 1); + bt->frame->bits = bt->mgr->page_bits; bt->frame->min = nxt; bt->frame->cnt = idx; @@ -1963,7 +1967,7 @@ uint prev; // get new free page and write higher keys to it. - if( !(right = bt_newpage(bt, bt->frame)) ) + if( !(right->page_no = bt_newpage(bt, bt->frame)) ) return bt->err; // update lower keys to continue in old page @@ -1971,7 +1975,6 @@ uint prev; memcpy (bt->frame, set->page, bt->mgr->page_size); memset (set->page+1, 0, bt->mgr->page_size - sizeof(*set->page)); nxt = bt->mgr->page_size; - set->page->posted = 0; set->page->dirty = 0; set->page->act = 0; cnt = 0; @@ -1992,65 +1995,42 @@ uint prev; // remember fence key for smaller page memcpy(fencekey, key, key->len + 1); - bt_putid(set->page->right, right); + + bt_putid(set->page->right, right->page_no); set->page->min = nxt; set->page->cnt = idx; // if current page is the root page, split it if( set->page_no == ROOT_page ) - return bt_splitroot (bt, set, fencekey, right); - - bt_unlockpage (BtLockWrite, set->latch); - right = 0; + return bt_splitroot (bt, set, fencekey, right->page_no); // insert new fences in their parent pages - while( 1 ) { - bt_lockpage (BtLockParent, set->latch); - bt_lockpage (BtLockWrite, set->latch); - - key = keyptr (set->page, set->page->cnt); - memcpy (fencekey, key, key->len + 1); - prev = set->page->posted; - - if( right && prev ) { - bt_unlockpage (BtLockParent, set->latch); - bt_unlockpage (BtLockWrite, set->latch); - bt_unpinlatch (set->latch); - bt_unpinpool (set->pool); - return 0; - } - - right = bt_getid (set->page->right); - set->page->posted = 1; - - bt_unlockpage (BtLockWrite, set->latch); + right->latch = bt_pinlatch (bt, right->page_no); + bt_lockpage (BtLockParent, right->latch); - // insert new fence for reformulated left block of smaller keys + bt_lockpage (BtLockParent, set->latch); + bt_unlockpage (BtLockWrite, set->latch); - if( !prev ) - if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) ) - return bt->err; + // insert new fence for reformulated left block of smaller keys - bt_unlockpage (BtLockParent, set->latch); - bt_unpinlatch (set->latch); - bt_unpinpool (set->pool); + if( bt_insertkey (bt, fencekey+1, *fencekey, lvl+1, set->page_no, time(NULL)) ) + return bt->err; - if( !(set->page_no = right) ) - break; + // switch fence for right block of larger keys to new right page - set->latch = bt_pinlatch (bt, right); + if( bt_insertkey (bt, rightkey+1, *rightkey, lvl+1, right->page_no, time(NULL)) ) + return bt->err; - if( set->pool = bt_pinpool (bt, right) ) - set->page = bt_page (bt, set->pool, right); - else - return bt->err; - } + bt_unlockpage (BtLockParent, set->latch); + bt_unpinlatch (set->latch); + bt_unpinpool (set->pool); + bt_unlockpage (BtLockParent, right->latch); + bt_unpinlatch (right->latch); return 0; } - // Insert new key into the btree at given level. BTERR bt_insertkey (BtDb *bt, unsigned char *key, uint len, uint lvl, uid id, uint tod) -- 2.40.0