X-Git-Url: https://pd.if.org/git/?p=btree;a=blobdiff_plain;f=threads2h.c;h=500e8b3d470af09006dcd851e1aaeab26941a09d;hp=46742c487497d05185dd795028a54aadb46ff4db;hb=HEAD;hpb=471ecef14bab98d48dad385a2d9c3d4f361aa6c6 diff --git a/threads2h.c b/threads2h.c index 46742c4..500e8b3 100644 --- a/threads2h.c +++ b/threads2h.c @@ -93,11 +93,11 @@ typedef enum{ // share is count of read accessors // grant write lock when share == 0 -typedef struct { - volatile unsigned char mutex; - volatile unsigned char exclusive:1; - volatile unsigned char pending:1; - volatile ushort share; +volatile typedef struct { + unsigned char mutex[1]; + unsigned char exclusive:1; + unsigned char pending:1; + ushort share; } BtSpinLatch; // hash table entries @@ -170,17 +170,15 @@ 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; // The memory mapping pool table buffer manager entry typedef struct { - unsigned long long int lru; // number of times accessed uid basepage; // mapped base page number char *map; // mapped memory pointer ushort slot; // slot index in this array @@ -192,6 +190,8 @@ typedef struct { #endif } BtPool; +#define CLOCK_bit 0x8000 // bit in pool->pin + // The loadpage interface object typedef struct { @@ -230,7 +230,7 @@ typedef struct { ushort poolmax; // highest page pool node allocated ushort poolmask; // total number of pages in mmap segment - 1 ushort hashsize; // size of Hash Table for pool entries - volatile uint evicted; // last evicted hash table slot + volatile uint evicted; // last evicted pool table slot ushort *hash; // pool index for hash entries BtSpinLatch *latch; // latches for hash table slots BtLatchMgr *latchmgr; // mapped latch page from allocation page @@ -373,10 +373,10 @@ ushort prev; do { // obtain latch mutex #ifdef unix - if( __sync_lock_test_and_set(&latch->mutex, 1) ) + if( __sync_lock_test_and_set(latch->mutex, 1) ) continue; #else - if( _InterlockedExchange8(&latch->mutex, 1) ) + if( _InterlockedExchange8(latch->mutex, 1) ) continue; #endif // see if exclusive request is granted or pending @@ -385,9 +385,9 @@ ushort prev; latch->share++; #ifdef unix - __sync_lock_release (&latch->mutex); + __sync_lock_release (latch->mutex); #else - _InterlockedExchange8(&latch->mutex, 0); + _InterlockedExchange8(latch->mutex, 0); #endif if( prev ) @@ -408,10 +408,10 @@ uint prev; do { #ifdef unix - if( __sync_lock_test_and_set(&latch->mutex, 1) ) + if( __sync_lock_test_and_set(latch->mutex, 1) ) continue; #else - if( _InterlockedExchange8(&latch->mutex, 1) ) + if( _InterlockedExchange8(latch->mutex, 1) ) continue; #endif if( prev = !(latch->share | latch->exclusive) ) @@ -419,9 +419,9 @@ uint prev; else latch->pending = 1; #ifdef unix - __sync_lock_release (&latch->mutex); + __sync_lock_release (latch->mutex); #else - _InterlockedExchange8(&latch->mutex, 0); + _InterlockedExchange8(latch->mutex, 0); #endif if( prev ) return; @@ -442,10 +442,10 @@ int bt_spinwritetry(BtSpinLatch *latch) uint prev; #ifdef unix - if( __sync_lock_test_and_set(&latch->mutex, 1) ) + if( __sync_lock_test_and_set(latch->mutex, 1) ) return 0; #else - if( _InterlockedExchange8(&latch->mutex, 1) ) + if( _InterlockedExchange8(latch->mutex, 1) ) return 0; #endif // take write access if all bits are clear @@ -454,9 +454,9 @@ uint prev; latch->exclusive = 1; #ifdef unix - __sync_lock_release (&latch->mutex); + __sync_lock_release (latch->mutex); #else - _InterlockedExchange8(&latch->mutex, 0); + _InterlockedExchange8(latch->mutex, 0); #endif return prev; } @@ -467,17 +467,17 @@ void bt_spinreleasewrite(BtSpinLatch *latch) { // obtain latch mutex #ifdef unix - while( __sync_lock_test_and_set(&latch->mutex, 1) ) + while( __sync_lock_test_and_set(latch->mutex, 1) ) sched_yield(); #else - while( _InterlockedExchange8(&latch->mutex, 1) ) + while( _InterlockedExchange8(latch->mutex, 1) ) SwitchToThread(); #endif latch->exclusive = 0; #ifdef unix - __sync_lock_release (&latch->mutex); + __sync_lock_release (latch->mutex); #else - _InterlockedExchange8(&latch->mutex, 0); + _InterlockedExchange8(latch->mutex, 0); #endif } @@ -486,17 +486,17 @@ void bt_spinreleasewrite(BtSpinLatch *latch) void bt_spinreleaseread(BtSpinLatch *latch) { #ifdef unix - while( __sync_lock_test_and_set(&latch->mutex, 1) ) + while( __sync_lock_test_and_set(latch->mutex, 1) ) sched_yield(); #else - while( _InterlockedExchange8(&latch->mutex, 1) ) + while( _InterlockedExchange8(latch->mutex, 1) ) SwitchToThread(); #endif latch->share--; #ifdef unix - __sync_lock_release (&latch->mutex); + __sync_lock_release (latch->mutex); #else - _InterlockedExchange8(&latch->mutex, 0); + _InterlockedExchange8(latch->mutex, 0); #endif } @@ -613,6 +613,8 @@ ushort hashidx = page_no % bt->mgr->latchmgr->latchhash; ushort slot, avail = 0, victim, idx; BtLatchSet *set; + // try to find existing latch table entry for this page + // obtain read lock on hash table entry bt_spinreadlock(bt->mgr->latchmgr->table[hashidx].latch); @@ -784,14 +786,14 @@ uint slot; close (mgr->idx); free (mgr->pool); free (mgr->hash); - free (mgr->latch); + free ((void *)mgr->latch); free (mgr); #else FlushFileBuffers(mgr->idx); CloseHandle(mgr->idx); GlobalFree (mgr->pool); GlobalFree (mgr->hash); - GlobalFree (mgr->latch); + GlobalFree ((void *)mgr->latch); GlobalFree (mgr); #endif } @@ -801,10 +803,10 @@ uint slot; void bt_close (BtDb *bt) { #ifdef unix - if ( bt->mem ) + if( bt->mem ) free (bt->mem); #else - if ( bt->mem) + if( bt->mem) VirtualFree (bt->mem, 0, MEM_RELEASE); #endif free (bt); @@ -1115,7 +1117,7 @@ uint slot; pool->hashprev = pool->hashnext = NULL; pool->basepage = page_no & ~bt->mgr->poolmask; - pool->lru = 1; + pool->pin = CLOCK_bit + 1; if( slot = bt->mgr->hash[idx] ) { node = bt->mgr->pool + slot; @@ -1126,32 +1128,6 @@ uint slot; bt->mgr->hash[idx] = pool->slot; } -// find best segment to evict from buffer pool - -BtPool *bt_findlru (BtDb *bt, uint hashslot) -{ -unsigned long long int target = ~0LL; -BtPool *pool = NULL, *node; - - if( !hashslot ) - return NULL; - - node = bt->mgr->pool + hashslot; - - // scan pool entries under hash table slot - - do { - if( node->pin ) - continue; - if( node->lru > target ) - continue; - target = node->lru; - pool = node; - } while( node = node->hashnext ); - - return pool; -} - // map new buffer pool segment to virtual memory BTERR bt_mapsegment(BtDb *bt, BtPool *pool, uid page_no) @@ -1206,42 +1182,25 @@ void bt_unpinpool (BtPool *pool) BtPool *bt_pinpool(BtDb *bt, uid page_no) { +uint slot, hashidx, idx, victim; BtPool *pool, *node, *next; -uint slot, idx, victim; // lock hash table chain - idx = (uint)(page_no >> bt->mgr->seg_bits) % bt->mgr->hashsize; - bt_spinreadlock (&bt->mgr->latch[idx]); + hashidx = (uint)(page_no >> bt->mgr->seg_bits) % bt->mgr->hashsize; + bt_spinwritelock (&bt->mgr->latch[hashidx]); // look up in hash table - if( pool = bt_findpool(bt, page_no, idx) ) { -#ifdef unix - __sync_fetch_and_add(&pool->pin, 1); -#else - _InterlockedIncrement16 (&pool->pin); -#endif - bt_spinreleaseread (&bt->mgr->latch[idx]); - pool->lru++; - return pool; - } - - // upgrade to write lock - - bt_spinreleaseread (&bt->mgr->latch[idx]); - bt_spinwritelock (&bt->mgr->latch[idx]); - - // try to find page in pool with write lock - - if( pool = bt_findpool(bt, page_no, idx) ) { + if( pool = bt_findpool(bt, page_no, hashidx) ) { #ifdef unix + __sync_fetch_and_or(&pool->pin, CLOCK_bit); __sync_fetch_and_add(&pool->pin, 1); #else + _InterlockedOr16 (&pool->pin, CLOCK_bit); _InterlockedIncrement16 (&pool->pin); #endif - bt_spinreleasewrite (&bt->mgr->latch[idx]); - pool->lru++; + bt_spinreleasewrite (&bt->mgr->latch[hashidx]); return pool; } @@ -1261,13 +1220,8 @@ uint slot, idx, victim; if( bt_mapsegment(bt, pool, page_no) ) return NULL; - bt_linkhash(bt, pool, page_no, idx); -#ifdef unix - __sync_fetch_and_add(&pool->pin, 1); -#else - _InterlockedIncrement16 (&pool->pin); -#endif - bt_spinreleasewrite (&bt->mgr->latch[idx]); + bt_linkhash(bt, pool, page_no, hashidx); + bt_spinreleasewrite (&bt->mgr->latch[hashidx]); return pool; } @@ -1286,20 +1240,30 @@ uint slot, idx, victim; #else victim = _InterlockedIncrement (&bt->mgr->evicted) - 1; #endif - victim %= bt->mgr->hashsize; + victim %= bt->mgr->poolmax; + pool = bt->mgr->pool + victim; + idx = (uint)(pool->basepage >> bt->mgr->seg_bits) % bt->mgr->hashsize; + + if( !victim ) + continue; // try to get write lock // skip entry if not obtained - if( !bt_spinwritetry (&bt->mgr->latch[victim]) ) + if( !bt_spinwritetry (&bt->mgr->latch[idx]) ) continue; - // if pool entry is empty - // or any pages are pinned - // skip this entry + // skip this entry if + // page is pinned + // or clock bit is set - if( !(pool = bt_findlru(bt, bt->mgr->hash[victim])) ) { - bt_spinreleasewrite (&bt->mgr->latch[victim]); + if( pool->pin ) { +#ifdef unix + __sync_fetch_and_and(&pool->pin, ~CLOCK_bit); +#else + _InterlockedAnd16 (&pool->pin, ~CLOCK_bit); +#endif + bt_spinreleasewrite (&bt->mgr->latch[idx]); continue; } @@ -1308,14 +1272,14 @@ uint slot, idx, victim; if( node = pool->hashprev ) node->hashnext = pool->hashnext; else if( node = pool->hashnext ) - bt->mgr->hash[victim] = node->slot; + bt->mgr->hash[idx] = node->slot; else - bt->mgr->hash[victim] = 0; + bt->mgr->hash[idx] = 0; if( node = pool->hashnext ) node->hashprev = pool->hashprev; - bt_spinreleasewrite (&bt->mgr->latch[victim]); + bt_spinreleasewrite (&bt->mgr->latch[idx]); // remove old file mapping #ifdef unix @@ -1333,13 +1297,8 @@ uint slot, idx, victim; if( bt_mapsegment(bt, pool, page_no) ) return NULL; - bt_linkhash(bt, pool, page_no, idx); -#ifdef unix - __sync_fetch_and_add(&pool->pin, 1); -#else - _InterlockedIncrement16 (&pool->pin); -#endif - bt_spinreleasewrite (&bt->mgr->latch[idx]); + bt_linkhash(bt, pool, page_no, hashidx); + bt_spinreleasewrite (&bt->mgr->latch[hashidx]); return pool; } } @@ -1420,15 +1379,15 @@ int reuse; reuse = 0; } #ifdef unix - if ( pwrite(bt->mgr->idx, page, bt->mgr->page_size, new_page << bt->mgr->page_bits) < bt->mgr->page_size ) + if( pwrite(bt->mgr->idx, page, bt->mgr->page_size, new_page << bt->mgr->page_bits) < bt->mgr->page_size ) return bt->err = BTERR_wrt, 0; // if writing first page of pool block, zero last page in the block - if ( !reuse && bt->mgr->poolmask > 0 && (new_page & bt->mgr->poolmask) == 0 ) + if( !reuse && bt->mgr->poolmask > 0 && (new_page & bt->mgr->poolmask) == 0 ) { // use zero buffer to write zeros - if ( pwrite(bt->mgr->idx,bt->zero, bt->mgr->page_size, (new_page | bt->mgr->poolmask) << bt->mgr->page_bits) < bt->mgr->page_size ) + if( pwrite(bt->mgr->idx,bt->zero, bt->mgr->page_size, (new_page | bt->mgr->poolmask) << bt->mgr->page_bits) < bt->mgr->page_size ) return bt->err = BTERR_wrt, 0; } #else @@ -1536,7 +1495,7 @@ BtPool *prevpool; // re-read and re-lock root after determining actual level of root if( set->page->lvl != drill) { - if ( set->page_no != ROOT_page ) + if( set->page_no != ROOT_page ) return bt->err = BTERR_struct, 0; drill = set->page->lvl; @@ -1964,10 +1923,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 +1948,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 +1964,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 +1972,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 +1992,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; } @@ -2102,7 +2042,7 @@ BtKey ptr; ptr = keyptr(set->page, slot); else { - if ( !bt->err ) + if( !bt->err ) bt->err = BTERR_ovflw; return bt->err; } @@ -2245,6 +2185,67 @@ uint bt_tod(BtDb *bt, uint slot) #ifdef STANDALONE +#ifndef unix +double getCpuTime(int type) +{ +FILETIME crtime[1]; +FILETIME xittime[1]; +FILETIME systime[1]; +FILETIME usrtime[1]; +SYSTEMTIME timeconv[1]; +double ans = 0; + + memset (timeconv, 0, sizeof(SYSTEMTIME)); + + switch( type ) { + case 0: + GetSystemTimeAsFileTime (xittime); + FileTimeToSystemTime (xittime, timeconv); + ans = (double)timeconv->wDayOfWeek * 3600 * 24; + break; + case 1: + GetProcessTimes (GetCurrentProcess(), crtime, xittime, systime, usrtime); + FileTimeToSystemTime (usrtime, timeconv); + break; + case 2: + GetProcessTimes (GetCurrentProcess(), crtime, xittime, systime, usrtime); + FileTimeToSystemTime (systime, timeconv); + break; + } + + ans += (double)timeconv->wHour * 3600; + ans += (double)timeconv->wMinute * 60; + ans += (double)timeconv->wSecond; + ans += (double)timeconv->wMilliseconds / 1000; + return ans; +} +#else +#include +#include + +double getCpuTime(int type) +{ +struct rusage used[1]; +struct timeval tv[1]; + + switch( type ) { + case 0: + gettimeofday(tv, NULL); + return (double)tv->tv_sec + (double)tv->tv_usec / 1000000; + + case 1: + getrusage(RUSAGE_SELF, used); + return (double)used->ru_utime.tv_sec + (double)used->ru_utime.tv_usec / 1000000; + + case 2: + getrusage(RUSAGE_SELF, used); + return (double)used->ru_stime.tv_sec + (double)used->ru_stime.tv_usec / 1000000; + } + + return 0; +} +#endif + void bt_latchaudit (BtDb *bt) { ushort idx, hashidx; @@ -2253,7 +2254,7 @@ BtPageSet set[1]; BtKey ptr; #ifdef unix - for( idx = 1; idx < bt->mgr->latchmgr->latchdeployed; idx++ ) { + for( idx = 1; idx <= bt->mgr->latchmgr->latchdeployed; idx++ ) { set->latch = bt->mgr->latchsets + idx; if( set->latch->pin ) { fprintf(stderr, "latchset %d pinned for page %.6x\n", idx, set->latch->page_no); @@ -2390,8 +2391,6 @@ FILE *in; found++; else if( bt->err ) fprintf(stderr, "Error %d Syserr %d Line: %d\n", bt->err, errno, line), exit(0); - else - fprintf(stderr, "Unable to find key %.*s line %d\n", len, key, line); len = 0; } else if( len < 255 ) @@ -2474,16 +2473,15 @@ int main (int argc, char **argv) { int idx, cnt, len, slot, err; int segsize, bits = 16; +double start, stop; #ifdef unix pthread_t *threads; -timer start, stop; #else -time_t start[1], stop[1]; HANDLE *threads; #endif -double real_time; ThreadArg *args; uint poolsize = 0; +float elapsed; int num = 0; char key[1]; BtMgr *mgr; @@ -2500,11 +2498,7 @@ BtDb *bt; exit(0); } -#ifdef unix - gettimeofday(&start, NULL); -#else - time(start); -#endif + start = getCpuTime(0); if( argc > 3 ) bits = atoi(argv[3]); @@ -2562,18 +2556,20 @@ BtDb *bt; #ifdef unix for( idx = 0; idx < cnt; idx++ ) pthread_join (threads[idx], NULL); - gettimeofday(&stop, NULL); - real_time = 1000.0 * ( stop.tv_sec - start.tv_sec ) + 0.001 * (stop.tv_usec - start.tv_usec ); #else WaitForMultipleObjects (cnt, threads, TRUE, INFINITE); for( idx = 0; idx < cnt; idx++ ) CloseHandle(threads[idx]); - time (stop); - real_time = 1000 * (*stop - *start); #endif - fprintf(stderr, " Time to complete: %.2f seconds\n", real_time/1000); + elapsed = getCpuTime(0) - start; + fprintf(stderr, " real %dm%.3fs\n", (int)(elapsed/60), elapsed - (int)(elapsed/60)*60); + elapsed = getCpuTime(1); + fprintf(stderr, " user %dm%.3fs\n", (int)(elapsed/60), elapsed - (int)(elapsed/60)*60); + elapsed = getCpuTime(2); + fprintf(stderr, " sys %dm%.3fs\n", (int)(elapsed/60), elapsed - (int)(elapsed/60)*60); + bt_mgrclose (mgr); }