From 55149d5e2b69cd6dfa7f6fd3d02e0d488b3fd69d Mon Sep 17 00:00:00 2001 From: Jeffrey Altman Date: Mon, 5 Nov 2007 18:25:33 +0000 Subject: [PATCH] windows-bplus-tree-20071105 Migrate search key into thread local storage --- src/WINNT/afsd/afsd_init.c | 16 ++++++- src/WINNT/afsd/cm_btree.c | 94 +++++++++++++++++++++++++++++++++++++- src/WINNT/afsd/cm_btree.h | 17 +++---- 3 files changed, 113 insertions(+), 14 deletions(-) diff --git a/src/WINNT/afsd/afsd_init.c b/src/WINNT/afsd/afsd_init.c index f75679fab..64364ca5e 100644 --- a/src/WINNT/afsd/afsd_init.c +++ b/src/WINNT/afsd/afsd_init.c @@ -23,6 +23,9 @@ #include #include "afsd.h" +#ifdef USE_BPLUS +#include "cm_btree.h" +#endif #include #include #include @@ -40,7 +43,9 @@ extern int RXSTATS_ExecuteRequest(struct rx_call *z_call); extern afs_int32 cryptall; extern int cm_enableServerLocks; extern int cm_deleteReadOnly; +#ifdef USE_BPLUS extern afs_int32 cm_BPlusTrees; +#endif extern afs_int32 cm_OfflineROIsValid; extern const char **smb_ExecutableExtensions; @@ -1067,6 +1072,7 @@ int afsd_InitCM(char **reasonP) } afsi_log("CM DeleteReadOnly is %u", cm_deleteReadOnly); +#ifdef USE_BPLUS dummyLen = sizeof(DWORD); code = RegQueryValueEx(parmKey, "BPlusTrees", NULL, NULL, (BYTE *) &dwValue, &dummyLen); @@ -1075,6 +1081,14 @@ int afsd_InitCM(char **reasonP) } afsi_log("CM BPlusTrees is %u", cm_BPlusTrees); + if (cm_BPlusTrees && !cm_InitBPlusDir()) { + cm_BPlusTrees = 0; + afsi_log("CM BPlusTree initialization failure; disabled for this session"); + } +#else + afsi_log("CM BPlusTrees is not supported"); +#endif + if ((RegQueryValueEx( parmKey, "PrefetchExecutableExtensions", 0, ®Type, NULL, &dummyLen) == ERROR_SUCCESS) && (regType == REG_MULTI_SZ)) @@ -1159,7 +1173,7 @@ int afsd_InitCM(char **reasonP) smb_InitIoctl(); cm_InitCallback(); - + code = cm_InitMappedMemory(virtualCache, cm_CachePath, stats, cm_chunkSize, cacheBlocks, blockSize); afsi_log("cm_InitMappedMemory code %x", code); if (code != 0) { diff --git a/src/WINNT/afsd/cm_btree.c b/src/WINNT/afsd/cm_btree.c index 80b1b7b45..ac2a57271 100644 --- a/src/WINNT/afsd/cm_btree.c +++ b/src/WINNT/afsd/cm_btree.c @@ -66,6 +66,14 @@ static void _pullentry(Nptr node, int entry, int offset); static void _xferentry(Nptr srcNode, int srcEntry, Nptr destNode, int destEntry); static void _setentry(Nptr node, int entry, keyT key, Nptr downNode); +/* access key and data values for B+tree methods */ +/* pass values to getSlot(), descend...() */ +static keyT getfunkey(Tree *B); +static dataT getfundata(Tree *B); +static void setfunkey(Tree *B, keyT v); +static void setfundata(Tree *B, dataT v); + + #ifdef DEBUG_BTREE static int _isRoot(Tree *B, Nptr n) { @@ -114,6 +122,19 @@ static int _isFull(Tree *B, Nptr n) /***********************************************************************\ | B+tree Initialization and Cleanup Routines | \***********************************************************************/ +static DWORD TlsKeyIndex; +static DWORD TlsDataIndex; + +long cm_InitBPlusDir(void) +{ + if ((TlsKeyIndex = TlsAlloc()) == TLS_OUT_OF_INDEXES) + return 0; + + if ((TlsDataIndex = TlsAlloc()) == TLS_OUT_OF_INDEXES) + return 0; + + return 1; +} /******************** Set up B+tree structure **********************/ Tree *initBtree(unsigned int poolsz, unsigned int fanout, KeyCmp keyCmp) @@ -168,6 +189,73 @@ void freeBtree(Tree *B) } +/* access key and data values for B+tree methods */ +/* pass values to getSlot(), descend...() */ +static keyT getfunkey(Tree *B) { + keyT *tlsKey; + + // Retrieve a data pointer for the current thread. + tlsKey = (keyT *) TlsGetValue(TlsKeyIndex); + if (tlsKey == NULL) { + if (GetLastError() != ERROR_SUCCESS) + osi_panic("TlsGetValue failed", __FILE__, __LINE__); + else + osi_panic("get before set", __FILE__, __LINE__); + } + + return *tlsKey; +} + +static dataT getfundata(Tree *B) { + dataT *tlsData; + + // Retrieve a data pointer for the current thread. + tlsData = (dataT *) TlsGetValue(TlsDataIndex); + if (tlsData == NULL) { + if (GetLastError() != ERROR_SUCCESS) + osi_panic("TlsGetValue failed", __FILE__, __LINE__); + else + osi_panic("get before set", __FILE__, __LINE__); + } + + return *tlsData; +} + +static void setfunkey(Tree *B, keyT theKey) { + keyT *tlsKey; + + tlsKey = (keyT *) TlsGetValue(TlsKeyIndex); + if (tlsKey == NULL) { + if (GetLastError() != ERROR_SUCCESS) + osi_panic("TlsGetValue failed", __FILE__, __LINE__); + + tlsKey = malloc(sizeof(keyT)); + + if (!TlsSetValue(TlsKeyIndex, tlsKey)) + osi_panic("TlsSetValue failed", __FILE__, __LINE__); + } + + *tlsKey = theKey; +} + +static void setfundata(Tree *B, dataT theData) { + dataT *tlsData; + + tlsData = (dataT *) TlsGetValue(TlsDataIndex); + if (tlsData == NULL) { + if (GetLastError() != ERROR_SUCCESS) + osi_panic("TlsGetValue failed", __FILE__, __LINE__); + + tlsData = malloc(sizeof(dataT)); + + if (!TlsSetValue(TlsDataIndex, tlsData)) + osi_panic("TlsSetValue failed", __FILE__, __LINE__); + } + + *tlsData = theData; +} + + /***********************************************************************\ | Find leaf node in which data nodes can be found | \***********************************************************************/ @@ -276,10 +364,12 @@ static int findKey(Tree *B, Nptr curr, int lo, int hi) mid = (lo + hi) >> 1; switch (findslot = bestMatch(B, curr, mid)) { case BTLOWER: /* check lower half of range */ - findslot = findKey(B, curr, lo, mid - 1); /* never in 2-3+trees */ + if (mid > 1) + findslot = findKey(B, curr, lo, mid - 1); /* never in 2-3+trees */ break; case BTUPPER: /* check upper half of range */ - findslot = findKey(B, curr, mid + 1, hi); + if (mid < getfanout(B)) + findslot = findKey(B, curr, mid + 1, hi); break; case BTERROR: sprintf(B->message, "FINDKEY: (lo %d hi %d) Bad key ordering on node %d (0x%p)\n", diff --git a/src/WINNT/afsd/cm_btree.h b/src/WINNT/afsd/cm_btree.h index 61ad7852c..695ee3339 100644 --- a/src/WINNT/afsd/cm_btree.h +++ b/src/WINNT/afsd/cm_btree.h @@ -107,10 +107,8 @@ typedef struct tree { unsigned int height; /* nodes traversed from root to leaves */ Nptr pool; /* list of all nodes */ Nptr empty; /* list of empty nodes */ - keyT theKey; /* the key value used in tree operations */ - dataT theData; /* data used for insertions/deletions */ union { /* nodes to change in insert and delete */ - Nptr split; + Nptr split; /* protected by scp->dirlock write-lock */ Nptr merge; } branch; KeyCmp keycmp; /* pointer to function comparing two keys */ @@ -164,10 +162,15 @@ long cm_BPlusDirNextEnumEntry(cm_direnum_t *enump, cm_direnum_entry_t **entrypp) long cm_BPlusDirFreeEnumeration(cm_direnum_t *enump); long cm_BPlusDirEnumTest(cm_scache_t * dscp, afs_uint32 locked); +long cm_InitBPlusDir(void); + +/************ Statistic Counter ***************************************/ + extern afs_uint32 bplus_free_tree; extern afs_uint32 bplus_dv_error; extern afs_uint64 bplus_free_time; + /************ Accessor Macros *****************************************/ /* low level definition of Nptr value usage */ @@ -246,14 +249,6 @@ extern afs_uint64 bplus_free_time; #define xferentry(j, q, v, z) _xferentry(j, q, v, z) #define setentry(j, q, v, z) _setentry(j, q, v, z) - -/* access key and data values for B+tree methods */ -/* pass values to getSlot(), descend...() */ -#define getfunkey(B) ((B)->theKey) -#define getfundata(B) ((B)->theData) -#define setfunkey(B,v) ((B)->theKey = (v)) -#define setfundata(B,v) ((B)->theData = (v)) - /* define number of B+tree nodes for free node pool */ #define getpoolsize(B) ((B)->poolsize) #define setpoolsize(B,v) ((B)->poolsize = (v)) -- 2.39.5