2 * rnam.c -- BSD format name cache functions for lsof library
7 * Copyright 1997 Purdue Research Foundation, West Lafayette, Indiana
8 * 47907. All rights reserved.
10 * Written by Victor A. Abell
12 * This software is not subject to any license of the American Telephone
13 * and Telegraph Company or the Regents of the University of California.
15 * Permission is granted to anyone to use this software for any purpose on
16 * any computer system, and to alter it and redistribute it freely, subject
17 * to the following restrictions:
19 * 1. Neither the authors nor Purdue University are responsible for any
20 * consequences of the use of this software.
22 * 2. The origin of this software must not be misrepresented, either by
23 * explicit claim or by omission. Credit to the authors and Purdue
24 * University must appear in documentation and sources.
26 * 3. Altered versions must be plainly marked as such, and must not be
27 * misrepresented as being the original software.
29 * 4. This notice may not be removed or altered.
33 #include "../machine.h"
35 #if defined(HASNCACHE) && defined(USE_LIB_RNAM)
38 static char copyright[] =
39 "@(#) Copyright 1997 Purdue Research Foundation.\nAll rights reserved.\n";
40 static char *rcsid = "$Id: rnam.c,v 1.11 2008/10/21 16:13:23 abe Exp $";
41 # endif /* !defined(lint) */
47 * rnam.c - read BSD format (struct namecache or nch) name cache
49 * This code is effective only when HASNCACHE is defined.
55 * #include the relevant header file -- e.g., <sys/namei.h>.
57 * Define X_NCACHE as the nickname for the kernel cache address.
59 * Define X_NCSIZE as the nickname for the size of the kernel cache.
61 * Define NCACHE_NXT if the kernel's name cache is a linked list, starting
62 * at the X_NCACHE address, rather than a table, starting at that address.
64 * Define NCACHE_NO_ROOT if the calling dialect doesn't support
65 * the locating of the root node of a file system.
67 * Define the name of the name cache structure -- e.g.,
69 * #define NCACHE <structure name>
71 * Define the following casts, if they differ from the defaults:
73 * NCACHE_SZ_CAST cast for X_NCSIZE (default int)
76 * #define NCACHE_SZ_CAST unsigned long
78 * Define the names of these elements of struct NCACHE:
80 * must #define NCACHE_NM <name>
81 * must #define NCACHE_NMLEN <name length
82 * optional #define NCACHE_NXT <link to next entry>
83 * must #define NCACHE_NODEADDR <node address>
84 * must #define NCACHE_NODEID <node capability ID)
85 * optional #define NCACHE_PARADDR <parent node address>
86 * optional #define NCACHE_PARID <parent node capability ID)
88 * The caller may need to:
90 * Define NCHNAMLEN as the length of the name element of NCACHE, if it's
91 * not defined in the header file that defines the NCACHE structure.
93 * Define this prototype for ncache_load():
95 * _PROTOTYPE(static void ncache_load,(void));
100 * Local static values
103 static int Mch; /* name cache hash mask */
105 # if !defined(NCACHE_NC_CAST)
106 #define NCACHE_SZ_CAST int
107 # endif /* !defined(NCACHE_NC_CAST) */
109 static NCACHE_SZ_CAST Nc = 0; /* size of name cache */
110 static int Nch = 0; /* size of name cache hash pointer
113 KA_T na; /* node address */
115 # if defined(NCACHE_NODEID)
116 unsigned long id; /* capability ID */
117 # endif /* defined(NCACHE_NODEID) */
119 # if defined(NCACHE_PARADDR) && defined(NCACHE_PARID)
120 KA_T pa; /* parent node address */
121 struct l_nch *pla; /* parent local node address */
122 unsigned long did; /* parent capability ID */
123 # endif /* defined(NCACHE_PARADDR) && defined(NCACHE_PARID) */
125 char nm[NCHNAMLEN+1]; /* name */
126 int nl; /* name length */
129 static struct l_nch *Ncache = (struct l_nch*)NULL;
130 /* the local name cache */
131 static struct l_nch **Nchash = (struct l_nch **)NULL;
132 /* Ncache hash pointers */
133 static int Ncfirst = 1; /* first-call status */
135 # if defined(NCACHE_NODEID)
136 #define ncachehash(i,n) Nchash+(((((int)(n)>>2)+((int)(i)))*31415)&Mch)
137 _PROTOTYPE(static struct l_nch *ncache_addr,(unsigned long i, KA_T na));
138 # else /* !defined(NCACHE_NODEID) */
139 #define ncachehash(n) Nchash+((((int)(n)>>2)*31415)&Mch)
140 _PROTOTYPE(static struct l_nch *ncache_addr,(KA_T na));
141 # endif /* defined(NCACHE_NODEID) */
143 #define DEFNCACHESZ 1024 /* local size if X_NCSIZE kernel value < 1 */
144 #define LNCHINCRSZ 64 /* local size increment */
146 # if !defined(NCACHE_NO_ROOT)
147 _PROTOTYPE(static int ncache_isroot,(KA_T na, char *cp));
148 # endif /* !defined(NCACHE_NO_ROOT) */
152 * ncache_addr() - look up a node's local ncache address
155 static struct l_nch *
157 # if defined(NCACHE_NODEID)
159 unsigned long i; /* node's capability ID */
160 # else /* !defined(NCACHE_NODEID) */
162 # endif /* defined(NCACHE_NODEID) */
164 KA_T na; /* node's address */
168 # if defined(NCACHE_NODEID)
169 for (hp = ncachehash(i, na); *hp; hp++)
170 # else /* !defined(NCACHE_NODEID) */
171 for (hp = ncachehash(na); *hp; hp++)
172 # endif /* defined(NCACHE_NODEID) */
176 # if defined(NCACHE_NODEID)
177 if ((*hp)->id == i && (*hp)->na == na)
178 # else /* !defined(NCACHE_NODEID) */
180 # endif /* defined(NCACHE_NODEID) */
184 return((struct l_nch *)NULL);
188 # if !defined(NCACHE_NO_ROOT)
190 * ncache_isroot() - is head of name cache path a file system root?
194 ncache_isroot(na, cp)
195 KA_T na; /* kernel node address */
196 char *cp; /* partial path */
198 char buf[MAXPATHLEN];
204 static KA_T *nc = (KA_T *)NULL;
211 * Search the root vnode cache.
213 for (i = 0; i < ncn; i++) {
218 * Read the vnode and see if it's a VDIR node with the VROOT flag set. If
219 * it is, then the path is complete.
221 * If it isn't, and if the file has an inode number, search the mount table
222 * and see if the file system's inode number is known. If it is, form the
223 * possible full path, safely stat() it, and see if it's inode number matches
224 * the one we have for this file. If it does, then the path is complete.
226 if (kread((KA_T)na, (char *)&v, sizeof(v))
227 || v.v_type != VDIR || !(v.v_flag & VROOT)) {
230 * The vnode tests failed. Try the inode tests.
232 if (Lf->inp_ty != 1 || !Lf->inode
233 || !Lf->fsdir || (len = strlen(Lf->fsdir)) < 1)
235 if ((len + 1 + strlen(cp) + 1) > sizeof(buf))
237 for (mtp = readmnt(); mtp; mtp = mtp->next) {
238 if (!mtp->dir || !mtp->inode)
240 if (strcmp(Lf->fsdir, mtp->dir) == 0)
245 (void) strcpy(buf, Lf->fsdir);
246 if (buf[len - 1] != '/')
248 (void) strcpy(&buf[len], cp);
249 if (statsafely(buf, &sb) != 0
250 || (unsigned long)sb.st_ino != Lf->inode)
254 * Add the node address to the root node cache.
258 len = (MALLOC_S)(10 * sizeof(KA_T));
259 nc = (KA_T *)malloc(len);
261 len = (MALLOC_S)((nca + 10) * sizeof(KA_T));
262 nc = (KA_T *)realloc(nc, len);
265 (void) fprintf(stderr, "%s: no space for root node table\n",
274 # endif /* !defined(NCACHE_NO_ROOT) */
278 * ncache_load() - load the kernel's name cache
284 struct l_nch **hp, *lc;
288 static KA_T kp = (KA_T)NULL;
291 # if defined(NCACHE_NXT)
294 # else /* !defined NCACHE_NXT) */
295 static struct NCACHE *kca = (struct NCACHE *)NULL;
296 # endif /* defined(NCACHE_NXT) */
303 * Do startup (first-time) functions.
307 * Establish kernel cache size.
310 if (get_Nl_value(X_NCSIZE, (struct drive_Nl *)NULL, &v) < 0
312 || kread((KA_T)v, (char *)&Nc, sizeof(Nc)))
315 (void) fprintf(stderr,
316 "%s: WARNING: can't read name cache size: %s\n",
317 Pn, print_kptr(v, (char *)NULL, 0));
324 (void) fprintf(stderr,
325 "%s: WARNING: kernel name cache size: %d\n", Pn, Nc);
326 (void) fprintf(stderr,
327 " Cache size assumed to be: %d\n", DEFNCACHESZ);
329 iNc = Nc = DEFNCACHESZ;
332 * Establish kernel cache address.
335 if (get_Nl_value(X_NCACHE, (struct drive_Nl *)NULL, &v) < 0
337 || kread((KA_T)v, (char *)&kp, sizeof(kp))) {
339 (void) fprintf(stderr,
340 "%s: WARNING: can't read name cache address: %s\n",
341 Pn, print_kptr(v, (char *)NULL, 0));
346 # if defined(NCACHE_NXT)
349 # else /* !defined(NCACHE_NXT) */
351 * Allocate space for a local copy of the kernel's cache.
353 len = Nc * sizeof(struct NCACHE);
354 if (!(kca = (struct NCACHE *)malloc((MALLOC_S)len))) {
356 (void) fprintf(stderr,
357 "%s: can't allocate name cache space: %d\n", Pn, len);
360 # endif /* defined(NCACHE_NXT) */
363 * Allocate space for the local cache.
365 len = Nc * sizeof(struct l_nch);
366 if (!(Ncache = (struct l_nch *)malloc((MALLOC_S)len))) {
371 (void) fprintf(stderr,
372 "%s: no space for %d byte local name cache\n", Pn, len);
378 * Do setup for repeat calls.
383 (void) free((FREE_P *)Nchash);
384 Nchash = (struct l_nch **)NULL;
387 # if defined(NCACHE_NXT)
389 # endif /* defined(NCACHE_NXT) */
393 # if !defined(NCACHE_NXT)
396 * Read the kernel's name cache.
398 if (kread(kp, (char *)kca, (Nc * sizeof(struct NCACHE)))) {
400 (void) fprintf(stderr,
401 "%s: WARNING: can't read kernel's name cache: %s\n",
402 Pn, print_kptr(kp, (char *)NULL, 0));
406 # endif /* !defined(NCACHE_NXT) */
409 * Build a local copy of the kernel name cache.
412 # if defined(NCACHE_NXT)
413 for (i = iNc * 16, kc = &nc, lc = Ncache, n = 0; kp; )
414 # else /* !defined(NCACHE_NXT) */
415 for (i = n = 0, kc = kca, lc = Ncache; i < Nc; i++, kc++)
416 # endif /* defined(NCACHE_NXT) */
420 # if defined(NCACHE_NXT)
421 if (kread(kp, (char *)kc, sizeof(nc)))
423 if ((kp = (KA_T)kc->NCACHE_NXT) == kf)
425 # endif /* defined(NCACHE_NXT) */
427 if (!kc->NCACHE_NODEADDR)
429 if ((len = kc->NCACHE_NMLEN) < 1 || len > NCHNAMLEN)
431 if (len < 3 && kc->NCACHE_NM[0] == '.') {
432 if (len == 1 || (len == 2 && kc->NCACHE_NM[1] == '.'))
436 # if defined(NCACHE_NXT)
439 if (!(Ncache = (struct l_nch *)realloc(Ncache,
440 (MALLOC_S)(Nc * sizeof(struct l_nch)))))
442 (void) fprintf(stderr,
443 "%s: no more space for %d entry local name cache\n",
449 # endif /* defined(NCACHE_NXT) */
451 # if defined(NCACHE_NODEID)
452 lc->na = (KA_T)kc->NCACHE_NODEADDR;
453 lc->id = kc->NCACHE_NODEID;
454 # endif /* defined(NCACHE_NODEID) */
456 # if defined(NCACHE_PARADDR)
457 lc->pa = (KA_T)kc->NCACHE_PARADDR;
458 lc->pla = (struct l_nch *)NULL;
459 # endif /* defined(NCACHE_PARADDR) */
461 # if defined(NCACHE_PARID)
462 lc->did = kc->NCACHE_PARID;
463 # endif /* defined(NCACHE_PARID) */
465 (void) strncpy(lc->nm, kc->NCACHE_NM, len);
467 lc->nl = strlen(lc->nm);
471 # if defined(NCACHE_NXT)
474 (void) fprintf(stderr,
475 "%s: WARNING: name cache truncated at %d entries\n",
479 # endif /* defined(NCACHE_NXT) */
483 * Reduce memory usage, as required.
486 # if !defined(NCACHE_NXT)
488 (void) free((FREE_P *)kca);
489 # endif /* !defined(NCACHE_NXT) */
494 (void) free((FREE_P *)Ncache);
495 Ncache = (struct l_nch *)NULL;
498 (void) fprintf(stderr,
499 "%s: WARNING: unusable name cache size: %d\n", Pn, n);
505 len = Nc * sizeof(struct l_nch);
506 if (!(Ncache = (struct l_nch *)realloc(Ncache, len)))
511 * Build a hash table to locate Ncache entries.
513 for (Nch = 1; Nch < Nc; Nch <<= 1)
517 if (!(Nchash = (struct l_nch **)calloc(Nch+Nc, sizeof(struct l_nch *))))
520 (void) fprintf(stderr,
521 "%s: no space for %d name cache hash pointers\n",
525 for (i = 0, lc = Ncache; i < Nc; i++, lc++) {
527 # if defined(NCACHE_NODEID)
528 for (hp = ncachehash(lc->id, lc->na), n = 1; *hp; hp++)
529 # else /* defined(NCACHE_NODEID) */
530 for (hp = ncachehash(lc->na), n = 1; *hp; hp++)
531 # endif /* defined(NCACHE_NODEID) */
535 # if defined(NCACHE_NODEID)
536 if ((*hp)->na == lc->na && (*hp)->id == lc->id
537 # else /* defined(NCACHE_NODEID) */
538 if ((*hp)->na == lc->na
539 # endif /* defined(NCACHE_NODEID) */
541 && strcmp((*hp)->nm, lc->nm) == 0
543 # if defined(NCACHE_PARADDR) && defined(NCACHE_PARID)
544 && (*hp)->pa == lc->pa && (*hp)->did == lc->did
545 # endif /* defined(NCACHE_PARADDR) && defined(NCACHE_PARID) */
556 # if defined(NCACHE_PARADDR) && defined(NCACHE_PARID)
558 * Make a final pass through the local cache and convert parent node
559 * addresses to local name cache pointers.
561 for (i = 0, lc = Ncache; i < Nc; i++, lc++) {
564 lc->pla = ncache_addr(lc->did, lc->pa);
566 # endif /* defined(NCACHE_PARADDR) && defined(NCACHE_PARID) */
571 * ncache_lookup() - look up a node's name in the kernel's name cache
575 ncache_lookup(buf, blen, fp)
576 char *buf; /* receiving name buffer */
577 int blen; /* receiving buffer length */
578 int *fp; /* full path reply */
588 # if defined(HASFSINO)
590 * If the entry has an inode number that matches the inode number of the
591 * file system mount point, return an empty path reply. That tells the
592 * caller to print the file system mount point name only.
594 if ((Lf->inp_ty == 1) && Lf->fs_ino && (Lf->inode == Lf->fs_ino))
596 # endif /* defined(HASFSINO) */
599 * Look up the name cache entry for the node address.
602 # if defined(NCACHE_NODEID)
603 if (Nc == 0 || !(lc = ncache_addr(Lf->id, Lf->na)))
604 # else /* defined(NCACHE_NODEID) */
605 if (Nc == 0 || !(lc = ncache_addr(Lf->na)))
606 # endif /* defined(NCACHE_NODEID) */
612 * If the node has no cache entry, see if it's the mount
613 * point of a known file system.
615 if (!Lf->fsdir || !Lf->dev_def || Lf->inp_ty != 1)
616 return((char *)NULL);
617 for (mtp = readmnt(); mtp; mtp = mtp->next) {
618 if (!mtp->dir || !mtp->inode)
620 if (Lf->dev == mtp->dev
621 && mtp->inode == Lf->inode
622 && strcmp(mtp->dir, Lf->fsdir) == 0)
625 return((char *)NULL);
628 * Start the path assembly.
630 if ((nl = lc->nl) > (blen - 1))
631 return((char *)NULL);
632 cp = buf + blen - nl - 1;
633 rlen = blen - nl - 1;
634 (void) strcpy(cp, lc->nm);
636 # if defined(NCACHE_PARADDR) && defined(NCACHE_PARID)
638 * Look up the name cache entries that are parents of the node address.
642 * the name length is too large to fit in the receiving buffer.
647 # if !defined(NCACHE_NO_ROOT)
648 if (ncache_isroot(lc->pa, cp))
650 # endif /* !defined(NCACHE_NO_ROOT) */
655 if (((nl = lc->nl) + 1) > rlen)
660 (void) strncpy((cp - nl), lc->nm, nl);
664 # endif /* defined(NCACHE_PARADDR) && defined(NCACHE_PARID) */
667 #else /* !defined(HASNCACHE) || !defined(USE_LIB_RNAM) */
668 char rnam_d1[] = "d"; char *rnam_d2 = rnam_d1;
669 #endif /* defined(HASNCACHE) && defined(USE_LIB_RNAM) */