nfshash.c

vxworks源码源码解读是学习vxworks的最佳途径

/* nfshash.c - file based hash table for file handle to file name and reverse */

/* copyright - Wind River Systems */

/*
modification history
--------------------
01a,15nov98,rjc written
i*/

/*
 * INTERNAL
 *
 * The nfs server is required to maintain a mapping of file names to file
 * handles since the file handle is of limited size but nfs  requests
 * use 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 corresponding
 * file handle and correspondingly get the file name given the file handle.
 *
 * The name to handle operation would typically be done infrequently
 * compared 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 towards
 * keeping the latter operation more efficient.
 *
 * Conceptually the hash table is simple. Given a hash table entry we
 * compute the hash value for each of the 2 hashing functions and then 
 * plece the entry into two lists. While deleting we remove it from both
 * lists. However since we must keep this data structure on disk we
 * must 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 the
 * standard malloc/free based implementation.
 *
 * Our design allocates the disk space in larger chunks (than may be needed
 * to 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 as
 * a pointer.
 *
 * Data structures
 *
 * File block bit map table
 *
 * This structure which is maintained in memory contains a bit per block
 * of 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 would
 * expand 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 file
 * as it would be extremely inefficient in general (in case free block is not
 * at 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 entries
 * in 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 the
 * entries in a block and traversing the linked list of blocks
 *
 * Contents of an entry -
 *
 * Each entry consists of a triple comprising a next entry pointer, the
 * file handle , and the file name. The next entry pointer points to the next
 * entry 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 into
 * a block when keyed by file handle will not hash into the same block when
 * keyed by file name. While maintaining duplicates will work around this
 * problem we would end up doubling the storage requirements and increasing
 * the size of this file would increase search times anyway and most likely
 * negate most of the benefits of this organization.
 *
 */


/* 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>

/* 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);
/*
     sprintf  (pTbl->nmBuf, "%s/leofs.%x", dirName, (unsigned)pTbl);
*/

     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 = malloc (sizeof (TBL_DESC));
		if (nfsHashTblInit (pDev->pTbl, pDir) == ERROR)
		    {
		    printf ("cannot initialize nfs hash file\n");
		    free (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; mntTbl < 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)
		    {
		    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 */

	if (lseek (pTbl->fd, (pTbl->numBlocks + 1) *  HASH_BKT_SZ - 1, 
	    SEEK_SET) == ERROR)
	    {
	    return (BAD_OFFSET);
	    }
        pTbl->numBlocks ++;

	return ((pTbl->numBlocks - 1) * HASH_BKT_SZ);
	}
    else
        {
	/* existing free block available */
	/* scan byte wise then bit wise */
	pIx = (char *) pBits;
	for (; *pIx == 0; ++pIx)
	    {};
        for (ix = 0; ix < CHAR_BIT_LEN; ++ix)