From: Rudy_Nedved@RUDY.FAC.CS.CMU.EDU
Newsgroups: comp.protocols.appletalk
Subject: Re: recent CAP STAT_CACHE patches
Date: 5 Jan 93 18:58:46 GMT
Distribution: world
Organization: The Internet


I have submitted the patches to the cap@mun... folks. No response from them.

So what the heck...here they are:

Patch #:	rudy2
Type:		performance improvement
Priority:	none
Modification:	expand a cache and reduce byte compares
Submitted:	Rudy Nedved (ern) <ern+@h.gp.cs.cmu.edu>
Summary:	ENUM cache has been expanded from 30 to 100.
Summary:	a hash value added to IDirP to speed up child lookup
Summary:	ipathstr re-done to minimize strlen byte operations
File:		cap60/applications/aufs/afps.h
File:		cap60/applications/aufs/afpdid.c

*** applications/aufs/afps.h.orig	Fri Dec  4 11:42:57 1992
--- applications/aufs/afps.h		Fri Dec  4 12:01:06 1992
***************
*** 1,7 ****
  /*
!  * $Author: djh $ $Date: 1992/06/23 23:28:08 $
!  * $Header: /mac/src/cap60/applications/aufs/RCS/afps.h,v 2.3 1992/06/23 23:28:08 djh Rel djh $
!  * $Revision: 2.3 $
  */
  
  /*
--- 1,7 ----
  /*
!  * $oAuthor: djh $ $oDate: 1992/06/23 23:28:08 $
!  * $oHeader: /mac/src/cap60/applications/aufs/RCS/afps.h,v 2.3 1992/06/23 23:28:08 djh Rel djh $
!  * $oRevision: 2.3 $
  */
  
  /*
***************
*** 85,90 ****
--- 85,91 ----
  
  typedef struct idir {		/* local directory info (internal) */
    char *name;			/* the directory name */
+   long hash;			/* hash of the directory name */
    struct idir *next;		/* ptr to next at same level */
    struct idir *subs;		/* ptr to children */
    struct idir *pdir;		/* ptr to parent */
***************
*** 178,184 ****
  
  #define NOECIDX (-1)
  
! #define NECSIZE 30		/* size of the enum cache */
  
  void ECacheInit();
  char *OSEnumGet();
--- 179,185 ----
  
  #define NOECIDX (-1)
  
! #define NECSIZE 100		/* size of the enum cache */
  
  void ECacheInit();
  char *OSEnumGet();

*** applications/aufs/afpdid.c.orig	Fri Dec  4 11:43:29 1992
--- applications/aufs/afpdid.c		Fri Dec  4 12:03:23 1992
***************
*** 1,7 ****
  /*
!  * $Author: djh $ $Date: 1992/07/27 15:29:09 $
!  * $Header: /mac/src/cap60/applications/aufs/RCS/afpdid.c,v 2.3 1992/07/27 15:29:09 djh Rel djh $
!  * $Revision: 2.3 $
  */
  
  /*
--- 1,7 ----
  /*
!  * $oAuthor: djh $ $oDate: 1992/07/27 15:29:09 $
!  * $oHeader: /mac/src/cap60/applications/aufs/RCS/afpdid.c,v 2.3 1992/07/27 15:29:09 djh Rel djh $
!  * $oRevision: 2.3 $
  */
  
  /*
***************
*** 107,114 ****
  IDirP dir;
  char *nam;
  {
!   for (; dir != (IDirP) 0 && strcmp(dir->name,nam) != 0; dir = dir->next)
!     /* NULL */;
    return(dir);
  }
   
--- 107,127 ----
  IDirP dir;
  char *nam;
  {
!   register long hash;
!   register char *p;
! 
!   p = nam;
!   hash = 0;
!   while (*p) {
!     hash <<= 2;
!     hash += *p++;
!   }
!   for(;dir != (IDirP) 0; dir = dir->next) {
!     if (dir->hash != hash)
! 	continue;
!     if (strcmp(dir->name,nam) == 0)
! 	break;
!   }
    return(dir);
  }
   
***************
*** 124,132 ****
--- 137,154 ----
  char *name;
  {
    IDirP dir;
+   register long hash;
+   register char *p;
  
    dir = (IDirP) malloc(sizeof(IDir));
    dir->name = (char *) malloc((unsigned) strlen(name)+1);
+   hash = 0;
+   p = name;
+   while (*p) {
+     hash <<= 2;
+     hash += *p++;
+   }
+   dir->hash = hash;
    strcpy(dir->name,name);
    dir->pdir = parent;			/* set pointer to parent in node */
    dir->subs = NILDIR;			/* no children */
***************
*** 145,150 ****
--- 167,173 ----
    OSValidateDIDDirInfo(dir);		/* validate directory info */
    if (parent && (dir->flags & DID_DATA) == 0) {
      parent->subs = dir->next;	/* unlink it */
+     dir->hash = 0;
      free(dir->name);		/* nada */
      free(dir);			/* nada */
      return(NILDIR);
***************
*** 177,203 ****
    if (lastcd == cd)			/* same as last request? */
      return(paths);			/* yes.. just return old paths */
    lastcd = cd;				/* else set new dir */
!   return(ipathstr(cd,paths));		/* and do the work... */
  }
  
  private char *
  ipathstr(cd,p)
  IDirP cd;
! char *p;
  {
!   int len;
  
!   if (cd == rootd) 			/* check for root directory  */
!     strcpy(p,"/");			/* at top of tree, init path */
!   else {
!     (void)ipathstr(cd->pdir,p);		/* recurse on parent until root */
!     len = strlen(p);
      if (cd->pdir != rootd) 
!       p[len++] = '/';			/* add path component */
!     strcpy(p+len, cd->name);		/* concatenate current dir to path */
    }
-   return(p);				/* and return a pointer... */
- }
  
  /*
   * return a path relative to vroot
--- 200,238 ----
    if (lastcd == cd)			/* same as last request? */
      return(paths);			/* yes.. just return old paths */
    lastcd = cd;				/* else set new dir */
!   ipathstr(cd,paths);			/* and do the work... */
!   return(paths);			/* return new path */
  }
  
  private char *
  ipathstr(cd,p)
  IDirP cd;
! register char *p;
  {
!   register char *t;
  
!   /* check for root directory  */
!   if (cd == rootd) {
!     /* at top of tree, init path */
!     *p++ = '/';
!     *p = '\0';
!     return (p);
!   }
! 
!   /* recurse on parent until root, get new insertion pointer */
!   p = ipathstr(cd->pdir,p);
! 
!   /* insert new path component */
    if (cd->pdir != rootd)
!     *p++ = '/';
!   t = cd->name;
!   while (*t)
!     *p++ = *t++;
!   *p = '\0';
! 
!   /* return new insertion pointer */
!   return(p);
  }
  
  /*
   * return a path relative to vroot
***************
*** 529,535 ****
  }
  
  /*
!  * OSErr EtoIFile(char *file, IDirP *idir, IDirP *ipdir, int *ivol
   *		  sdword edir, word evol, byte eptype, byte *epath);
   *
   * Convert external arguments which specify a file/dir into internal
--- 564,570 ----
  }
  
  /*
!  * OSErr EtoIfile(char *file, IDirP *idir, IDirP *ipdir, int *ivol
   *		  sdword edir, word evol, byte eptype, byte *epath);
   *
   * Convert external arguments which specify a file/dir into internal
***************
*** 816,821 ****
--- 851,865 ----
    }
  
    if (strcmp(from,to) != 0) {		/* if different names then... */
+     register long hash;
+     register char *p;
+     hash = 0;
+     p = to;
+     while (*p) {
+       hash <<= 2;
+       hash += *p++;
+     }
+     fdir->hash = hash;
      free(fdir->name);			/* release the old name */
      fdir->name = (char *) malloc((unsigned) strlen(to)+1);
      strcpy(fdir->name,to);		/* copy new name */

Patch #:	rudy3
Type:		performance improvement to STAT_CACHE code
Priority:	none
Modification:	add module init call, use internal buffer
Submitted:	Rudy Nedved (ern) <ern+@h.gp.cs.cmu.edu>
Summary:	initialize things by adding an init call
Summary:	eliminate malloc/free calls
Summary:	allow stat of parent and root without loss of info
File:		cap60/applications/aufs/afpserver.c
File:		cap60/applications/aufs/afpspd.c

*** applications/aufs/afpserver.c.orig	Wed Mar 13 05:29:40 1991
--- applications/aufs/afpserver.c	Fri Dec  4 12:36:30 1992
***************
*** 1,7 ****
  /*
!  * $Author: djh $ $Date: 91/03/13 20:29:21 $
!  * $Header: afpserver.c,v 2.2 91/03/13 20:29:21 djh Exp $
!  * $Revision: 2.2 $
  */
  
  /*
--- 1,7 ----
  /*
!  * $oAuthor: djh $ $oDate: 91/03/13 20:29:21 $
!  * $oHeader: afpserver.c,v 2.2 91/03/13 20:29:21 djh Exp $
!  * $oRevision: 2.2 $
  */
  
  /*
***************
*** 222,227 ****
--- 222,230 ----
    ECacheInit();			/* init afposenum cache */
    InitIconCache();		/* init afpdt cache */
    InitDID();			/* init directory stuff  */
+ #ifdef STAT_CACHE
+   OSstat_Init();		/* init stat cache */
+ #endif STAT_CACHE
  }
  
  private int loggedin = FALSE;

*** applications/aufs/afpspd.c.orig	Fri Dec  4 11:43:29 1992
--- applications/aufs/afpspd.c		Fri Dec  4 12:34:50 1992
***************
*** 18,24 ****
  
  #ifdef STAT_CACHE
  
! struct statobj {
  	char * NAME;
  	struct stat STAT;
  	int FN,RS;
--- 18,24 ----
  
  #ifdef STAT_CACHE
  
! private struct statobj {
  	char * NAME;
  	struct stat STAT;
  	int FN,RS;
***************
*** 41,47 ****
--- 41,65 ----
  private char CUR_DIR_STR[1024];
  private char * CUR_DIR = NULL;
  private int CUR_DIR_LEN;
+ private char CUR_STAT_STR[1024];
+ private int CUR_STAT_LEVEL=0;
  
+ OSstat_Init()
+ {
+ 	register int P;
+ 
+ 	for(P = 0;P <= MAX_LEVEL;P++) {
+ 		STATS[P].NAME = NULL;
+ 		STATS[P].STAT.st_nlink = -1;
+ 		STATS[P].FN = VAL_INVALID;
+ 		STATS[P].RS = VAL_INVALID;
+ 	}
+ 
+ 	STATS[0].NAME = "<root>";
+ 
+ 	time(&CUR_TIME);
+ }
+ 
  OScd(path)
  	char * path;
  {
***************
*** 96,108 ****
  private release_stats(K)
  	int K;
  {
! 	int P;
  
  	if (DBOSI)
  		printf("release_stats=%d\n",K);
  
! 	for (P = K; STATS[P].NAME != NULL; P++) {
! 		free(STATS[P].NAME);
  		STATS[P].STAT.st_nlink = -1;
  		STATS[P].FN = VAL_INVALID;
  		STATS[P].RS = VAL_INVALID;
--- 114,125 ----
  private release_stats(K)
  	int K;
  {
! 	register int P;
  
  	if (DBOSI)
  		printf("release_stats=%d\n",K);
  
! 	for (P = K; P <= CUR_STAT_LEVEL; P++) {
  		STATS[P].STAT.st_nlink = -1;
  		STATS[P].FN = VAL_INVALID;
  		STATS[P].RS = VAL_INVALID;
***************
*** 113,191 ****
  private int EXPIRE_REQ;
  
  private expire_stats(K)
! 	int K;
  {
  	if (!EXPIRE_REQ)
  		return;
  	EXPIRE_REQ = 0;
! 	for (K = 0; STATS[K].NAME != NULL; K++) {
! 		if (STATS[K].VAL_TIME > CUR_TIME) {
  			STATS[K].STAT.st_nlink = -1;
  			STATS[K].FN = VAL_INVALID;
  			STATS[K].RS = VAL_INVALID;
  			if (DBOSI)
! 				printf("expired=%d(%s)\n",K,STATS[K].NAME);
  		}
  	}
  }
  
! private char * newstr(STR)
! 	char * STR;
  {
! 	char * P;
  
! 	P = (char *) malloc(strlen(STR)+1);
! 	if (P != NULL) {
! 		strcpy(P,STR);
! 		return P;
  	}
  	return NULL;
  }
  
! private struct statobj * locate_statobj(path)
! 	char * path;
! {
! 	char STR[1024];
! 	char * PART[20];
! 	int K,P,LC;
! 	char * S;
  
! 	if (*path != '/' || strcmp(path,"/") == 0)
  		return NULL;
- 	strcpy(STR,path);
- 	S = STR+1;
- 	K = 0;
- 	PART[K] = S;
- 	while ((S = (char*)index(S,'/')) != NULL) {
- 		*S++ = 0;
- 		PART[++K] = S;
- 		if (K >= MAX_LEVEL)
- 			return NULL;
  	}
- 	LC = K+1;
- 	expire_stats();
  	
! 	for (K = 0; K < LC && STATS[K].NAME != NULL && strcmp(STATS[K].NAME,PART[K]) == 0; K++);
! 	if (K == LC) {
! 		K--;
  		return &STATS[K];
- 	} else {
- 		release_stats(K);
- 		for (P = K; P < LC; P++) {
- 			STATS[P].NAME = newstr(PART[P]);
- 			STATS[P].STAT.st_nlink = -1;
- 			STATS[P].FN = VAL_INVALID;
- 			STATS[P].RS = VAL_INVALID;
  		}
! 		return &STATS[LC-1];
  	}
  }
  	
  OSstat(path,buf)
  	char * path;
  	struct stat *buf;
  {
- 	struct stat B;
  	struct statobj * CE;
  
  	if (DBOSI)
--- 130,298 ----
  private int EXPIRE_REQ;
  
  private expire_stats(K)
! 	register int K;
  {
  	if (!EXPIRE_REQ)
  		return;
  	EXPIRE_REQ = 0;
! 	for (K = 0; K <= CUR_STAT_LEVEL; K++) {
! 		if (STATS[K].STAT.st_nlink < 0)
! 			continue;
! 		if (STATS[K].VAL_TIME <= CUR_TIME) {
! 			if (DBOSI)
! 				printf("time delta %d vs %d (%d)\n",
! 					CUR_TIME,STATS[K].VAL_TIME,
! 					CUR_TIME - STATS[K].VAL_TIME);
  			STATS[K].STAT.st_nlink = -1;
  			STATS[K].FN = VAL_INVALID;
  			STATS[K].RS = VAL_INVALID;
  			if (DBOSI)
! 				printf("expired=%d(%s) t=%d\n",K,STATS[K].NAME,
! 				       STATS[K].VAL_TIME - CUR_TIME);
  		}
  	}
  }
  
! private struct statobj * locate_statobj(path)
! 	char * path;
  {
! 	register char *NEW,*OLD;
! 	register char *TMP;
! 	char *REPLACE;
! 	register int K;
  
! 	if (DBOSI)
! 		printf("locate_statobj: path '%s'\n", path);
! 
! 	/* get the path and make sure it is an absolute one */
! 	NEW = path;
! 	if (*NEW++ != '/')
! 		return NULL;
! 
! 	/* get rid of old information */
! 	expire_stats();
! 
! 	/* record what we are replacing */
! 	REPLACE = CUR_STAT_STR;
! 
! 	/* loop thru each path component and check against current */
! 	for(K=0;;) {
! 		/* strip leading slashes */
! 		while (*NEW == '/') NEW++;
! 
! 		/* handle root */
! 		if (K == 0) {
! 			if (*NEW == '\0') {
! 				if (DBOSI)
! 					printf("locate_statobj: root\n");
! 				return &STATS[0];
  			}
+ 			/* something more */
+ 			K++;
+ 		}
+ 
+ 		/* do we have info for this level? */
+ 		if (K > CUR_STAT_LEVEL)
+ 			break;	/* nope */
+ 
+ 		/* do we have a name for this level */
+ 		if ((OLD = STATS[K].NAME) == NULL)
+ 			break;	/* nope */
+ 
+ 		/* record buffer name */
+ 		REPLACE = OLD;
+ 
+ 		/* compare name */
+ 		TMP = NEW;
+ 		while (*OLD && *OLD == *TMP) {
+ 			OLD++;
+ 			TMP++;
+ 		}
+ 
+ 		/* did we end cleanly? */
+ 		if (*OLD != '\0')
+ 			break;	/* nope */
+ 
+ 		/* did NEW path end? */
+ 		if (*TMP == '\0') {
+ 			/* yes */
+ 			if (DBOSI)
+ 				printf("locate_statobj: found %d: '%s'\n",
+ 				       K,STATS[K].NAME);
+ 			return &STATS[K];
+ 		}
+ 
+ 		/* did NEW path end on slash? */
+ 		if (*TMP != '/')
+ 			break;	/* nope */
+ 
+ 		/* about to loop, see if too many levels */
+ 		if (++K >= MAX_LEVEL) {
+ 			if (DBOSI)
+ 				printf("locate_statobj: too many '%s'\n",
+ 				       path);
  			return NULL;
  		}
  
! 		/* loop again */
! 		REPLACE = ++OLD;
! 		NEW = TMP;
! 	}
  
! 	/* add components */
! 	release_stats(K);
! 
! 	OLD = REPLACE;
! 	for(;;) {
! 		/* strip leading slashes */
! 		while (*NEW == '/') NEW++;
! 
! 		/* make sure we have something */
! 		if (*NEW == '\0') {
! 			/* must be trailing slash */
! 			if (DBOSI)
! 				printf("locate_statobj: trailing / in '%s'\n",
! 				       path);
  			return NULL;
  		}
  
! 		/* record and copy component */
! 		STATS[K].NAME = OLD;
! 
! 		while (*NEW && *NEW != '/')
! 			*OLD++ = *NEW++;
! 		*OLD++ = '\0';
! 
! 		/* record new stat level */
! 		CUR_STAT_LEVEL = K;
! 
! 		/* are we done? */
! 		if (*NEW == '\0') {
! 			/* yep */
! 			if (DBOSI)
! 				printf("locate_statobj: return %d: '%s'\n",
! 				       K,STATS[K].NAME);
  			return &STATS[K];
  		}
! 
! 		/* about to loop, see if too many levels */
! 		if (++K >= MAX_LEVEL) {
! 			if (DBOSI)
! 				printf("locate_statobj: too many (add) '%s'\n",
! 				       path);
! 			return NULL;
  		}
+ 
+ 		/* loop again */
  	}
  
+ 	/* NEVER REACHED */
+ }
+ 	
  OSstat(path,buf)
  	char * path;
  	struct stat *buf;
  {
  	struct statobj * CE;
  
  	if (DBOSI)
***************
*** 193,210 ****
  
  	CE = locate_statobj(path);
  	if (CE != NULL) {
! 		if (CE->STAT.st_nlink != -1) {
  			if (DBOSI)
  				printf("OSstat=cache path\n");
  			bcopy(&CE->STAT,buf,sizeof(struct stat));
  			return 0;
  		}
! 		if (cwd_stat(path,&B) == 0) {
  			if (DBOSI)
  				printf("OSstat=caching path\n");
! 			bcopy(&B,&CE->STAT,sizeof(struct stat));
  			CE->VAL_TIME = CUR_TIME+EXP_TIME;
- 			bcopy(&B,buf,sizeof(struct stat));
  			return 0;
  		}
  		return -1;
--- 300,316 ----
  
  	CE = locate_statobj(path);
  	if (CE != NULL) {
! 		if (CE->STAT.st_nlink >= 0) {
  			if (DBOSI)
  				printf("OSstat=cache path\n");
  			bcopy(&CE->STAT,buf,sizeof(struct stat));
  			return 0;
  		}
! 		if (cwd_stat(path,buf) == 0) {
  			if (DBOSI)
  				printf("OSstat=caching path\n");
! 			bcopy(buf,&CE->STAT,sizeof(struct stat));
  			CE->VAL_TIME = CUR_TIME+EXP_TIME;
  			return 0;
  		}
  		return -1;

Patch #:	rudy4
Type:		performance improvement to file cache
Priority:	none
Modification:	add hash value for lookups
Submitted:	Rudy Nedved (ern) <ern+@h.gp.cs.cmu.edu>
Summary:	minimize byte comparisons on frequent name lookups in cache
File:		cap60/applications/aufs/afpposfi.c

*** applications/aufs/afposfi.c.orig	Fri Dec  4 11:42:58 1992
--- applications/aufs/afposfi.c		Fri Dec  4 12:43:37 1992
***************
*** 1,7 ****
  /*
!  * $Author: djh $ $Date: 1992/06/23 23:29:41 $
!  * $Header: /mac/src/cap60/applications/aufs/RCS/afposfi.c,v 2.3 1992/06/23 23:29:41 djh Rel djh $
!  * $Revision: 2.3 $
  */
  
  /*
--- 1,7 ----
  /*
!  * $oAuthor: djh $ $oDate: 1992/06/23 23:29:41 $
!  * $oHeader: /mac/src/cap60/applications/aufs/RCS/afposfi.c,v 2.3 1992/06/23 23:29:41 djh Rel djh $
!  * $oRevision: 2.3 $
  */
  
  /*
***************
*** 50,55 ****
--- 50,56 ----
    IDirP fe_pdir;		/* directory */
    int fe_okay;			/* last internal modify count */
    char  *fe_fnam;		/* file */
+   long   fe_hash;		/* hash value of file name */
    /* should we use ctime instead perhaps? */
    time_t fe_mtime;		/* last modify time: file system */
    time_t fe_vtime;		/* last time validated */
***************
*** 219,224 ****
--- 220,226 ----
    
    free(fe->fe_fnam);			/* always free the name */
    fe->fe_fnam = (char *) 0;		/*  and zero... */
+   fe->fe_hash = 0;			/* (and clear the hash value)
    fe->next = NULL;			/* trash it here since want in both */
    if (fce == (FCacheEnt *) 0)		/* check for recycled entry */
      lfce = fce = fe;			/* if none then save */
***************
*** 235,240 ****
--- 237,244 ----
  fc_compare(fe,key)
  FCacheEnt *fe,*key;
  {
+   if (fe->fe_hash != key->fe_hash)
+     return(FALSE);
    if (fe->fe_pdir != key->fe_pdir)
      return(FALSE);
    return(strcmp(fe->fe_fnam,key->fe_fnam) == 0);
***************
*** 257,262 ****
--- 261,267 ----
  
    fe->fe_pdir = key->fe_pdir;
    fe->fe_fnam = (char *) malloc(strlen(key->fe_fnam)+1);
+   fe->fe_hash = key->fe_hash;
    fe->fe_okay = TRUE;
    fe->fe_mtime = 0;
    time(&fe->fe_vtime);			/* validate time stamp */
***************
*** 484,493 ****
--- 489,507 ----
  IDirP pdir;
  char *fn;
  {
+   register long hash;
+   register char *p;
    FCacheEnt key;
  
    key.fe_pdir = pdir;
    key.fe_fnam = fn;
+   p = fn;
+   hash = 0;
+   while (*p) {
+     hash <<= 2;
+     hash += *p++;
+   }
+   key.fe_hash = hash;
    
    /* do the "quick" check first */
    if (getfe == 0 || !fc_compare(getfe,&key)) {
***************
*** 501,511 ****
--- 515,534 ----
  IDirP pdir;     
  char *fn;
  {
+   register long hash;
+   register char *p;
    FCacheEnt key;
    int idx;
  
    key.fe_pdir = pdir;
    key.fe_fnam = fn;
+   p = fn;
+   hash = 0;
+   while (*p) {
+     hash <<= 2;
+     hash += *p++;
+   }
+   key.fe_hash = hash;
  
    EModified(pdir);		/* make parent directory as modified */
    if (getfe == 0 || !fc_compare(getfe,&key)) {
Patch #:	rudy5
Type:		documentation update
Priority:	none
Modification:	Add performance comment about -s switch to aufs
Submitted:	Rudy Nedved (ern) <ern+@h.gp.cs.cmu.edu>
File:		cap60/man/AUFS.8

*** man/AUFS.8.orig	Fri Dec  4 11:43:42 1992
--- man/AUFS.8		Fri Dec  4 13:04:33 1992
***************
*** 199,204 ****
--- 199,205 ----
  to report usage statistics such as system time use and
  number of times encountered for the various AFP commands.
  These statistics are recorded in the log file at the end of a run.
+ NOTE: Recording these statistics slows down the server operations.
  .TP 10
  .BI \-d " <flags>"
  specifies debugging flags for the cap libraries.  See cap(3) for a