/* nfsHash.c - file based hash table for file handle to file name and reverse *//* Copyright 1998 - 2001 Wind River Systems, Inc. */#include "copyright_wrs.h" /*modification history--------------------01b,19oct01,rae  merge from truestack ver 01g, base o1a (SPRs 62705, 35767)01a,15nov98,rjc  written*//*INTERNALDESCRIPTIONThe nfs server is required to maintain a mapping of file names to filehandles since the file handle is of limited size but nfs  requestsuse a file handle to id the file. This map is being implemented as a 2 way hash table so given a file name we can find out the correspondingfile handle and correspondingly get the file name given the file handle.The name to handle operation would typically be done infrequentlycompared to the handle to name op since the former corresponds to opening the file while the latter is needed for every nfs request. Therefore the hash table has been implememnted with a bias towardskeeping the latter operation more efficient.Conceptually the hash table is simple. Given a hash table entry wecompute the hash value for each of the 2 hashing functions and then plece the entry into two lists. While deleting we remove it from bothlists. However since we must keep this data structure on disk wemust avoid the typical in memory implementation as a linked list of entries. That's because it is inefficient to implement a fragmentation/compaction memory management system as is done in the case of thestandard malloc/free based implementation.Our design allocates the disk space in larger chunks (than may be neededto store a single entry) and uses a bit map to keep track of free blocks.The hash table is maintained in a dos file. The file offset is used asa pointer.Data structuresFile block bit map tableThis structure which is maintained in memory contains a bit per blockof the dos file. In order to locate a free block we simply scan this bit from the start until a free block is found. If none are found we wouldexpand the hash file by seeking beyond the existing end of the file and update the bit map block correspondingly. Freeing a block is done by turning off the bit. Currently we do not reduce the size of the fileas it would be extremely inefficient in general (in case free block is notat the end of the file. Free blocks at the end of the list could be returned to the file system by truncating the file.Contents of a hash table block. Each block contains a sequence of entries followed by a pointer to the next block in the list keyed by file handle. In other words all entriesin a block and the blocks after it, would have hashed to the same value,and we can locate a required entry given the file handle by examining theentries in a block and traversing the linked list of blocksContents of an entry -Each entry consists of a triple comprising a next entry pointer, thefile handle , and the file name. The next entry pointer points to the nextentry in the hash chain, keyed by file name. Unlike the file handle based chain these entries are not organized into blocks as doing so would require that we maintain a duplicate entry since in general entries which hash intoa block when keyed by file handle will not hash into the same block whenkeyed by file name. While maintaining duplicates will work around thisproblem we would end up doubling the storage requirements and increasingthe size of this file would increase search times anyway and most likelynegate most of the benefits of this organization.To use this feature, include the following component:INCLUDE_NETWRS_NFSHASHNOMANUAL*//* includes */#include "vxWorks.h"#include "unistd.h"#include "xdr_nfs.h"#include "string.h"#include "fcntl.h"#include "stdio.h"#include "stdlib.h"#include "memLib.h"#include "nfsdLib.h"#include "ctype.h"#include "sys/stat.h"#include "semLib.h"#include "memPartLib.h"/* defines */#define MAX_DEVS 10#define MAX_MNTS 20#define MAX_HASH_BLKS  10000#define HASH_BKT_SZ   (1 * 1024)#define CHAR_BIT_LEN    8#define INT_BIT_LEN     (sizeof (int) * CHAR_BIT_LEN)#define BAD_OFFSET      ((off_t)(~0x0))#define FH_HASH_TBL_LEN      512#define NAME_HASH_TBL_LEN    512#define MIN_ENTRY_SZ    (sizeof (HNDL_NAME))#define STR_INT_LEN(s)  ((strlen (s) + 1 + sizeof (int) - 1) / sizeof (int))#define STR_ALIGN_LEN(s) (((strlen (s) + 1 + sizeof (int) - 1) / sizeof (int)) \			   *  sizeof (int))#define HASH_BKT_HDR_SZ    (sizeof (off_t) + sizeof (int))#define ENTRY_HDR_SZ    (sizeof (HNDL_NAME) - sizeof(int))/* forward declaration */LOCAL int blkRead (int, off_t, char *, int);LOCAL int blkWrite (int, off_t, char *, int );/* typedefs *//* descriptor for a nfs hashtable */typedef struct tblDesc      {    int     allocBits [MAX_HASH_BLKS/INT_BIT_LEN + 1];  /* bits allocated */    int     numBlocks;                          /* number of blocks allocated */    int     fd;              /* file descriptor of file containing hash table*/    off_t   nameHash [NAME_HASH_TBL_LEN - 1];  /* hash by name table */    int     nextInode;        /* next inode number to allocate */    int     refCnt;           /* reference count */    SEM_ID  sem;              /* protection lock */    char    nmBuf [NFS_MAXPATHLEN];  /* file name for hash table */    }  TBL_DESC;/*  * nfs handle and name pairs are stored in this structure. This structure  * is contained within the hash buckets which are written to disk. These * structures will have overall length a multple of sizeof (int) so * that  the next field stays aligned on a word boundary when in * memory  */typedef struct hndlName    {    off_t        next;         /* next entry ptr */    off_t        prev;         /* prev entry ptr */    short        totalLen;     /* total length of entry */    short        nameLen;      /* length of name string, 0 for free netry */    int          fh;     /* file handlei/inode  */    char         name [sizeof (int)]; /* actual str length is upto max 					 pathname lwngth, this is just for 					 a minimum string. Entry length must 					 be a multiple of sizeof (int) for					 alignment */    }   HNDL_NAME;/*  * hash bucket contains a number of HNDL_NAME pairs along with free space */typedef struct hashBkt      {    off_t        next;       /* next bkt ptr */    int          freeSpace;  /* free space remaining in bucket */    char         entries [HASH_BKT_SZ - sizeof (off_t) - sizeof (int)];			  /* buffer for entries of type HNDL_NAME */    }  HASH_BKT;/*  * Mapping from a file system device id to corresponding hash table descriptor. * There is one hash table per file system device if there are nfs exported *  directories in that file system */typedef struct devIdPair    {    int         dev;    TBL_DESC *  pTbl;    } DEV_ID_PAIR  ;/*  * Mapping from the nfs volume mount id to the hash table descriptor. * The nfs volume id is generated in the nfsExport () routine and is * maintained within the nfs file handle. */typedef struct mntIdPair    {    int         mntId;    TBL_DESC *  pTbl;    } MNT_ID_PAIR;/* locals *//* device to hash table descriptor table */LOCAL DEV_ID_PAIR   devTbl[MAX_DEVS];/* mount volume  to hash table descriptor table */LOCAL MNT_ID_PAIR   mntTbl[MAX_MNTS];/******************************************************************************* * insertMntId - insert entry into mount id based table ** Inserts pointer <pTbl> to a hash file table descriptor in the mount id* based table for nfs mount point <mntId>** NOMANUAL** RETURNS: N/A.*/LOCAL void insertMntId     (    TBL_DESC *    pTbl,    int           mntId    )    {    MNT_ID_PAIR *   pMnt;    for (pMnt = mntTbl; pMnt < mntTbl + MAX_MNTS; ++pMnt)	{	if (pMnt->mntId == 0)	    {	    pMnt->mntId = mntId;	    pMnt->pTbl = pTbl;	    return ;	    }        }    }/******************************************************************************* * getTblEnt - get entry from mnt table ** Returns ptr to table descriptor for give mount id <id>.** RETURNS: ptr to entry or NULL*/LOCAL TBL_DESC *  tblDescGet     (    int   id   /* mount id */    )    {    int ix;    for (ix = 0; ix < MAX_MNTS; ++ix)	{	if (mntTbl[ix].mntId ==  id)	    return (mntTbl[ix].pTbl);        }    return (NULL);    }/******************************************************************************* * nfsHashTblInit - initialize a hash table ** Initialize a hash table given the corresponding descriptor <pTbl>* creating the hash file in dir <dirName>.** RETURNS: OK or ERROR*/LOCAL STATUS nfsHashTblInit    (    TBL_DESC *   pTbl,    char *       dirName    )    {    off_t *      pOff;    HASH_BKT     initBuf;    HNDL_NAME *  pEnt;    int          ix;    memset ((char*) pTbl->allocBits, 0, sizeof (pTbl->allocBits));    for (pOff = pTbl->nameHash; pOff < (pTbl->nameHash + NAME_HASH_TBL_LEN); 	 ++pOff)	{	*pOff = BAD_OFFSET;	}     sprintf  (pTbl->nmBuf, "%s/leofs", dirName);     if ((pTbl->fd = open (pTbl->nmBuf, O_CREAT | O_RDWR | O_TRUNC, 0777)) 	 == ERROR)	 {	 printf ("cannot create file %s\n", pTbl->nmBuf);	 return (ERROR);	 }     /* create the fh hash blocks in the file */     pTbl->numBlocks = FH_HASH_TBL_LEN;     initBuf.next = BAD_OFFSET;     initBuf.freeSpace = sizeof (initBuf) - sizeof (initBuf.next) - 			 sizeof (initBuf.freeSpace);     pEnt = (HNDL_NAME*)initBuf.entries;     pEnt->totalLen = initBuf.freeSpace;     pEnt->nameLen = 0;     for (ix = 0; ix < FH_HASH_TBL_LEN ; ++ix)	 {	 if (write (pTbl->fd, (char *)&initBuf, sizeof (initBuf)) 	     != sizeof (initBuf))	     {	     return (ERROR);	     }	 }     pTbl->refCnt = 0;     pTbl->nextInode = 0;     pTbl->sem = semBCreate (SEM_Q_PRIORITY, SEM_FULL);     if (pTbl->sem == NULL)	return (ERROR);     return (OK);     }/*******************************************************************************  * nfsHashTblSet - set up nfs hash table** Set up an nfs hash table for exported directory <pDir> with mount voleume id* <mntId> and file system device id <devId>. If a hash fiel already exists* for <devId> then we simply need to setup a ptr to the existing hash table* descriptor alse a new hash file must be allocated adn initialized.** RETURNS: N/A*/void nfsHashTblSet    (    char *   pDir,     /* directory name */    int      mntId,    /*mount id */    u_long   devId     /* device Id */    )    {    DEV_ID_PAIR *   pDev;    for (pDev = devTbl; pDev < devTbl + MAX_DEVS; ++pDev)	{	if (pDev->dev != 0 && pDev->dev == devId)	    break;	}    if (pDev >= devTbl + MAX_DEVS)	{        for (pDev = devTbl; pDev < devTbl + MAX_DEVS; ++pDev)	    {	    if (pDev->dev == 0)		{		pDev->dev = devId;		pDev->pTbl = KHEAP_ALLOC (sizeof (TBL_DESC));		if (nfsHashTblInit (pDev->pTbl, pDir) == ERROR)		    {		    printf ("cannot initialize nfs hash file\n");		    KHEAP_FREE((char *)pDev->pTbl);		    return;		    }		break;                }            }        }    pDev->pTbl->refCnt++;    insertMntId (pDev->pTbl, mntId);    }/*******************************************************************************  * nfsHashTblUnset - clean up  nfs hash table** Clean up an nfs hash table for exported directory <pDir> with mount volume id* <mntId> and file system device id <devId>. Delete the allocated table * descriptor if there are no other references to it. ** RETURNS: N/A*/void nfsHashTblUnset    (    char *   pDir,     /* directory name */    int      mntId    /*mount id */    )    {    DEV_ID_PAIR *   pDev;    MNT_ID_PAIR *   pMnt;    TBL_DESC *      pTbl;    for (pMnt = mntTbl; pMnt < mntTbl + MAX_MNTS; ++pMnt)	{	if (pMnt->mntId  == mntId)	    break;	}    if (pMnt >= mntTbl + MAX_MNTS)	{	return;	}    else	{	pTbl = pMnt->pTbl;	pMnt->mntId = 0;	pMnt->pTbl -= 0;	pTbl->refCnt--;	if (pTbl->refCnt == 0)	    {	    close (pTbl->fd);	    unlink (pTbl->nmBuf);	    semDelete (pTbl->sem);	    for (pDev = devTbl; pDev < devTbl + MAX_DEVS; ++pDev)		{		if (pDev->pTbl == pTbl)		    {		    KHEAP_FREE (pTbl);		    pDev->pTbl = 0;		    pDev->dev = 0;		    }	         }             }         }    }/*******************************************************************************  * blockAlloc - allocates block from the file to be used as a hash bucket ** The length of the file being used is incremented by HASH_BKT_SZ* and the bit map updated to reflect that. The bit corresponding to* the allocated block is turned off marking the block as being in use,* so in case caller does not actually use the block he shuld free the block* with blockFree below** RETURNS: file offset of allocated block else BAD_OFFSET* NOMANUAL*/LOCAL off_t blockAlloc    (    TBL_DESC *     pTbl    )    {    int *  pBits = pTbl->allocBits;    int *  pMax = pTbl->allocBits + 		  ((pTbl->numBlocks + INT_BIT_LEN -1) / sizeof (int));  		  /* 1 beyond last word */    char *  pIx;    int     bitPos; /* bit position of allocated block */    int     ix;    if (pTbl->numBlocks >= MAX_HASH_BLKS)	{	return (BAD_OFFSET);	}    for ( ; *pBits == 0 && pBits < pMax ; ++pBits)	{}    if (pBits == pMax)	{        /* allocate a new block in the file at the end */