From ccfba9c7b806bdbd60f31010618e99eb48d2ddb6 Mon Sep 17 00:00:00 2001 From: Jeffrey Altman Date: Fri, 22 Jun 2007 23:15:38 +0000 Subject: [PATCH] windows-cell-hashtables-20070622 Add name and ID hash tables for cell lookups. cell lookups occur on every request. sometimes multiple times. removing the walking of the cell list when there are dozens of cells decreases cpu utilization and increases throughput. --- src/WINNT/afsd/cm_cell.c | 121 ++++++++++++++++++++++++++++++++----- src/WINNT/afsd/cm_cell.h | 22 +++++-- src/WINNT/afsd/cm_ioctl.c | 4 +- src/WINNT/afsd/cm_memmap.c | 17 ++++++ src/WINNT/afsd/cm_memmap.h | 4 ++ 5 files changed, 145 insertions(+), 23 deletions(-) diff --git a/src/WINNT/afsd/cm_cell.c b/src/WINNT/afsd/cm_cell.c index 85d6dfb20..22a1bd613 100644 --- a/src/WINNT/afsd/cm_cell.c +++ b/src/WINNT/afsd/cm_cell.c @@ -124,12 +124,15 @@ cm_cell_t *cm_GetCell_Gen(char *namep, char *newnamep, afs_uint32 flags) long code; char fullname[200]=""; int hasWriteLock = 0; + afs_uint32 hash; if (!strcmp(namep,SMB_IOCTL_FILENAME_NOSLASH)) return NULL; + hash = CM_CELL_NAME_HASH(namep); + lock_ObtainRead(&cm_cellLock); - for (cp = cm_data.allCellsp; cp; cp=cp->nextp) { + for (cp = cm_data.cellNameHashTablep[hash]; cp; cp=cp->nameNextp) { if (stricmp(namep, cp->name) == 0) { strcpy(fullname, cp->name); break; @@ -146,7 +149,7 @@ cm_cell_t *cm_GetCell_Gen(char *namep, char *newnamep, afs_uint32 flags) /* when we dropped the lock the cell could have been added * to the list so check again while holding the write lock */ - for (cp = cm_data.allCellsp; cp; cp=cp->nextp) { + for (cp = cm_data.cellNameHashTablep[hash]; cp; cp=cp->nameNextp) { if (stricmp(namep, cp->name) == 0) { strcpy(fullname, cp->name); break; @@ -202,7 +205,8 @@ cm_cell_t *cm_GetCell_Gen(char *namep, char *newnamep, afs_uint32 flags) * we should use it instead of completing the allocation * of a new cm_cell_t */ - for (cp2 = cm_data.allCellsp; cp2; cp2=cp2->nextp) { + hash = CM_CELL_NAME_HASH(fullname); + for (cp2 = cm_data.cellNameHashTablep[hash]; cp2; cp2=cp2->nameNextp) { if (stricmp(fullname, cp2->name) == 0) { break; } @@ -225,18 +229,21 @@ cm_cell_t *cm_GetCell_Gen(char *namep, char *newnamep, afs_uint32 flags) strncpy(cp->name, fullname, CELL_MAXNAMELEN); cp->name[CELL_MAXNAMELEN-1] = '\0'; - /* append cell to global list */ + /* the cellID cannot be 0 */ + cp->cellID = ++cm_data.currentCells; + + /* append cell to global list */ if (cm_data.allCellsp == NULL) { cm_data.allCellsp = cp; } else { - for (cp2 = cm_data.allCellsp; cp2->nextp; cp2=cp2->nextp) + for (cp2 = cm_data.allCellsp; cp2->allNextp; cp2=cp2->allNextp) ; - cp2->nextp = cp; + cp2->allNextp = cp; } - cp->nextp = NULL; - - /* the cellID cannot be 0 */ - cp->cellID = ++cm_data.currentCells; + cp->allNextp = NULL; + + cm_AddCellToNameHashTable(cp); + cm_AddCellToIDHashTable(cp); } done: @@ -253,9 +260,13 @@ cm_cell_t *cm_GetCell_Gen(char *namep, char *newnamep, afs_uint32 flags) cm_cell_t *cm_FindCellByID(afs_int32 cellID) { cm_cell_t *cp; + afs_uint32 hash; lock_ObtainRead(&cm_cellLock); - for (cp = cm_data.allCellsp; cp; cp=cp->nextp) { + + hash = CM_CELL_ID_HASH(cellID); + + for (cp = cm_data.cellIDHashTablep[hash]; cp; cp=cp->idNextp) { if (cellID == cp->cellID) break; } @@ -273,7 +284,7 @@ cm_ValidateCell(void) cm_cell_t * cellp; afs_uint32 count; - for (cellp = cm_data.allCellsp, count = 0; cellp; cellp=cellp->nextp, count++) { + for (cellp = cm_data.allCellsp, count = 0; cellp; cellp=cellp->allNextp, count++) { if ( cellp->magic != CM_CELL_MAGIC ) { afsi_log("cm_ValidateCell failure: cellp->magic != CM_CELL_MAGIC"); fprintf(stderr, "cm_ValidateCell failure: cellp->magic != CM_CELL_MAGIC\n"); @@ -302,7 +313,7 @@ cm_ShutdownCell(void) { cm_cell_t * cellp; - for (cellp = cm_data.allCellsp; cellp; cellp=cellp->nextp) + for (cellp = cm_data.allCellsp; cellp; cellp=cellp->allNextp) lock_FinalizeMutex(&cellp->mx); return 0; @@ -322,6 +333,8 @@ void cm_InitCell(int newFile, long maxCells) cm_data.allCellsp = NULL; cm_data.currentCells = 0; cm_data.maxCells = maxCells; + memset(cm_data.cellNameHashTablep, 0, sizeof(cm_cell_t *) * cm_data.cellHashTableSize); + memset(cm_data.cellIDHashTablep, 0, sizeof(cm_cell_t *) * cm_data.cellHashTableSize); #ifdef AFS_FREELANCE_CLIENT /* Generate a dummy entry for the Freelance cell whether or not @@ -338,7 +351,7 @@ void cm_InitCell(int newFile, long maxCells) strncpy(cellp->name, "Freelance.Local.Cell", CELL_MAXNAMELEN); /*safe*/ /* thread on global list */ - cellp->nextp = cm_data.allCellsp; + cellp->allNextp = cm_data.allCellsp; cm_data.allCellsp = cellp; cellp->cellID = AFS_FAKE_ROOT_CELL_ID; @@ -346,7 +359,7 @@ void cm_InitCell(int newFile, long maxCells) cellp->flags = CM_CELLFLAG_FREELANCE; #endif } else { - for (cellp = cm_data.allCellsp; cellp; cellp=cellp->nextp) { + for (cellp = cm_data.allCellsp; cellp; cellp=cellp->allNextp) { lock_InitializeMutex(&cellp->mx, "cm_cell_t mutex"); cellp->vlServersp = NULL; } @@ -386,7 +399,7 @@ int cm_DumpCells(FILE *outputFile, char *cookie, int lock) cookie, cm_data.currentCells, cm_data.maxCells); WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL); - for (cellp = cm_data.allCellsp; cellp; cellp=cellp->nextp) { + for (cellp = cm_data.allCellsp; cellp; cellp=cellp->allNextp) { sprintf(output, "%s cellp=0x%p,name=%s ID=%d flags=0x%x\r\n", cookie, cellp, cellp->name, cellp->cellID, cellp->flags); WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL); @@ -401,3 +414,79 @@ int cm_DumpCells(FILE *outputFile, char *cookie, int lock) return(0); } +/* call with volume write-locked and mutex held */ +void cm_AddCellToNameHashTable(cm_cell_t *cellp) +{ + int i; + + if (cellp->flags & CM_CELLFLAG_IN_NAMEHASH) + return; + + i = CM_CELL_NAME_HASH(cellp->name); + + cellp->nameNextp = cm_data.cellNameHashTablep[i]; + cm_data.cellNameHashTablep[i] = cellp; + cellp->flags |= CM_CELLFLAG_IN_NAMEHASH; +} + +/* call with cell write-locked and mutex held */ +void cm_RemoveCellFromNameHashTable(cm_cell_t *cellp) +{ + cm_cell_t **lcellpp; + cm_cell_t *tcellp; + int i; + + if (cellp->flags & CM_CELLFLAG_IN_NAMEHASH) { + /* hash it out first */ + i = CM_CELL_NAME_HASH(cellp->name); + for (lcellpp = &cm_data.cellNameHashTablep[i], tcellp = cm_data.cellNameHashTablep[i]; + tcellp; + lcellpp = &tcellp->nameNextp, tcellp = tcellp->nameNextp) { + if (tcellp == cellp) { + *lcellpp = cellp->nameNextp; + cellp->flags &= ~CM_CELLFLAG_IN_NAMEHASH; + cellp->nameNextp = NULL; + break; + } + } + } +} + +/* call with cell write-locked and mutex held */ +void cm_AddCellToIDHashTable(cm_cell_t *cellp) +{ + int i; + + if (cellp->flags & CM_CELLFLAG_IN_IDHASH) + return; + + i = CM_CELL_ID_HASH(cellp->cellID); + + cellp->idNextp = cm_data.cellIDHashTablep[i]; + cm_data.cellIDHashTablep[i] = cellp; + cellp->flags |= CM_CELLFLAG_IN_IDHASH; +} + +/* call with cell write-locked and mutex held */ +void cm_RemoveCellFromIDHashTable(cm_cell_t *cellp) +{ + cm_cell_t **lcellpp; + cm_cell_t *tcellp; + int i; + + if (cellp->flags & CM_CELLFLAG_IN_IDHASH) { + /* hash it out first */ + i = CM_CELL_ID_HASH(cellp->cellID); + for (lcellpp = &cm_data.cellIDHashTablep[i], tcellp = cm_data.cellIDHashTablep[i]; + tcellp; + lcellpp = &tcellp->idNextp, tcellp = tcellp->idNextp) { + if (tcellp == cellp) { + *lcellpp = cellp->idNextp; + cellp->flags &= ~CM_CELLFLAG_IN_IDHASH; + cellp->idNextp = NULL; + break; + } + } + } +} + diff --git a/src/WINNT/afsd/cm_cell.h b/src/WINNT/afsd/cm_cell.h index 0652e2ac3..02a9caee2 100644 --- a/src/WINNT/afsd/cm_cell.h +++ b/src/WINNT/afsd/cm_cell.h @@ -20,7 +20,9 @@ typedef struct cm_cell { afs_uint32 magic; afs_int32 cellID; /* cell ID */ - struct cm_cell *nextp; /* locked by cm_cellLock */ + struct cm_cell *allNextp; /* locked by cm_cellLock */ + struct cm_cell *nameNextp; /* locked by cm_cellLock */ + struct cm_cell *idNextp; /* locked by cm_cellLock */ char name[CELL_MAXNAMELEN]; /* cell name; never changes */ cm_serverRef_t *vlServersp; /* locked by cm_serverLock */ osi_mutex_t mx; /* mutex locking fields (flags) */ @@ -29,10 +31,16 @@ typedef struct cm_cell { } cm_cell_t; /* These are bit flag values */ -#define CM_CELLFLAG_SUID 1 /* setuid flag; not yet used */ -#define CM_CELLFLAG_DNS 2 /* cell servers are from DNS */ -#define CM_CELLFLAG_VLSERVER_INVALID 4 /* cell servers are invalid */ -#define CM_CELLFLAG_FREELANCE 8 /* local freelance fake cell */ +#define CM_CELLFLAG_SUID 1 /* setuid flag; not yet used */ +#define CM_CELLFLAG_DNS 2 /* cell servers are from DNS */ +#define CM_CELLFLAG_VLSERVER_INVALID 4 /* cell servers are invalid */ +#define CM_CELLFLAG_FREELANCE 8 /* local freelance fake cell */ +#define CM_CELLFLAG_IN_NAMEHASH 0x10 +#define CM_CELLFLAG_IN_IDHASH 0x20 + +#define CM_CELL_NAME_HASH(name) (SDBMHash(name) % cm_data.cellHashTableSize) + +#define CM_CELL_ID_HASH(id) ((unsigned long) id % cm_data.cellHashTableSize) extern void cm_InitCell(int newFile, long maxCells); @@ -54,4 +62,8 @@ extern cm_cell_t *cm_allCellsp; extern int cm_DumpCells(FILE *, char *, int); +extern void cm_AddCellToNameHashTable(cm_cell_t * cellp); + +extern void cm_AddCellToIDHashTable(cm_cell_t * cellp); + #endif /* __CELL_H_ENV_ */ diff --git a/src/WINNT/afsd/cm_ioctl.c b/src/WINNT/afsd/cm_ioctl.c index 318360ad3..caaae5882 100644 --- a/src/WINNT/afsd/cm_ioctl.c +++ b/src/WINNT/afsd/cm_ioctl.c @@ -1250,7 +1250,7 @@ long cm_IoctlGetCell(struct smb_ioctl *ioctlp, struct cm_user *userp) } lock_ObtainRead(&cm_cellLock); - for (tcellp = cm_data.allCellsp; tcellp; tcellp = tcellp->nextp) { + for (tcellp = cm_data.allCellsp; tcellp; tcellp = tcellp->allNextp) { if (whichCell == 0) break; whichCell--; } @@ -1307,7 +1307,7 @@ long cm_IoctlNewCell(struct smb_ioctl *ioctlp, struct cm_user *userp) cm_SkipIoctlPath(ioctlp); lock_ObtainWrite(&cm_cellLock); - for (cp = cm_data.allCellsp; cp; cp=cp->nextp) + for (cp = cm_data.allCellsp; cp; cp=cp->allNextp) { long code; lock_ObtainMutex(&cp->mx); diff --git a/src/WINNT/afsd/cm_memmap.c b/src/WINNT/afsd/cm_memmap.c index 5a83ee21d..45479e9d3 100644 --- a/src/WINNT/afsd/cm_memmap.c +++ b/src/WINNT/afsd/cm_memmap.c @@ -38,6 +38,14 @@ ComputeSizeOfVolumes(DWORD maxvols) return size; } +afs_uint64 +ComputeSizeOfCellHT(DWORD maxcells) +{ + afs_uint64 size; + size = osi_PrimeLessThan((afs_uint32)(maxcells/7 + 1)) * sizeof(cm_cell_t *); + return size; +} + afs_uint64 ComputeSizeOfVolumeHT(DWORD maxvols) { @@ -119,6 +127,7 @@ ComputeSizeOfMappingFile(DWORD stats, DWORD maxVols, DWORD maxCells, DWORD chunk + ComputeSizeOfVolumes(maxVols) + 4 * ComputeSizeOfVolumeHT(maxVols) + ComputeSizeOfCells(maxCells) + + 2 * ComputeSizeOfCellHT(maxCells) + ComputeSizeOfACLCache(stats) + ComputeSizeOfSCache(stats) + ComputeSizeOfSCacheHT(stats) @@ -233,6 +242,7 @@ cm_ShutdownMappedMemory(void) afsi_log(" volumeHashTableSize = %d", cm_data.volumeHashTableSize); afsi_log(" currentVolumes = %d", cm_data.currentVolumes); afsi_log(" maxVolumes = %d", cm_data.maxVolumes); + afsi_log(" cellHashTableSize = %d", cm_data.cellHashTableSize); afsi_log(" currentCells = %d", cm_data.currentCells); afsi_log(" maxCells = %d", cm_data.maxCells); afsi_log(" scacheHashTableSize = %d", cm_data.scacheHashTableSize); @@ -417,6 +427,7 @@ cm_ValidateMappedMemory(char * cachePath) fprintf(stderr," volumeHashTableSize = %d", config_data_p->volumeHashTableSize); fprintf(stderr," currentVolumes = %d\n", config_data_p->currentVolumes); fprintf(stderr," maxVolumes = %d\n", config_data_p->maxVolumes); + fprintf(stderr," cellHashTableSize = %d", config_data_p->cellHashTableSize); fprintf(stderr," currentCells = %d\n", config_data_p->currentCells); fprintf(stderr," maxCells = %d\n", config_data_p->maxCells); fprintf(stderr," scacheHashTableSize = %d\n", config_data_p->scacheHashTableSize); @@ -816,6 +827,7 @@ cm_InitMappedMemory(DWORD virtualCache, char * cachePath, DWORD stats, DWORD chu afsi_log(" volumeHashTableSize = %d", config_data_p->volumeHashTableSize); afsi_log(" currentVolumes = %d", config_data_p->currentVolumes); afsi_log(" maxVolumes = %d", config_data_p->maxVolumes); + afsi_log(" cellHashTableSize = %d", config_data_p->cellHashTableSize); afsi_log(" currentCells = %d", config_data_p->currentCells); afsi_log(" maxCells = %d", config_data_p->maxCells); afsi_log(" scacheHashTableSize = %d", config_data_p->scacheHashTableSize); @@ -841,6 +853,7 @@ cm_InitMappedMemory(DWORD virtualCache, char * cachePath, DWORD stats, DWORD chu cm_data.bufferSize = mappingSize; cm_data.scacheHashTableSize = osi_PrimeLessThan(stats / 2 + 1); cm_data.volumeHashTableSize = osi_PrimeLessThan((afs_uint32)(maxVols/7 + 1)); + cm_data.cellHashTableSize = osi_PrimeLessThan((afs_uint32)(maxCells/7 + 1)); if (virtualCache) { cm_data.cacheType = CM_BUF_CACHETYPE_VIRTUAL; } else { @@ -865,6 +878,10 @@ cm_InitMappedMemory(DWORD virtualCache, char * cachePath, DWORD stats, DWORD chu baseAddress += ComputeSizeOfVolumeHT(maxVols); cm_data.volumeBKIDHashTablep = (cm_volume_t **)baseAddress; baseAddress += ComputeSizeOfVolumeHT(maxVols); + cm_data.cellNameHashTablep = (cm_cell_t **)baseAddress; + baseAddress += ComputeSizeOfCellHT(maxCells); + cm_data.cellIDHashTablep = (cm_cell_t **)baseAddress; + baseAddress += ComputeSizeOfCellHT(maxCells); cm_data.cellBaseAddress = (cm_cell_t *) baseAddress; baseAddress += ComputeSizeOfCells(maxCells); cm_data.aclBaseAddress = (cm_aclent_t *) baseAddress; diff --git a/src/WINNT/afsd/cm_memmap.h b/src/WINNT/afsd/cm_memmap.h index 5a6775a5a..1233f87ad 100644 --- a/src/WINNT/afsd/cm_memmap.h +++ b/src/WINNT/afsd/cm_memmap.h @@ -60,6 +60,10 @@ typedef struct cm_config_data { cm_scache_t * scacheLRUFirstp; cm_scache_t * scacheLRULastp; + cm_cell_t ** cellNameHashTablep; + cm_cell_t ** cellIDHashTablep; + afs_uint32 cellHashTableSize; + cm_volume_t ** volumeNameHashTablep; cm_volume_t ** volumeRWIDHashTablep; cm_volume_t ** volumeROIDHashTablep; -- 2.39.5