1/*
2 * rnam.c -- BSD format name cache functions for lsof library
3 */
4
5
6/*
7 * Copyright 1997 Purdue Research Foundation, West Lafayette, Indiana
8 * 47907.  All rights reserved.
9 *
10 * Written by Victor A. Abell
11 *
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.
14 *
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:
18 *
19 * 1. Neither the authors nor Purdue University are responsible for any
20 *    consequences of the use of this software.
21 *
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.
25 *
26 * 3. Altered versions must be plainly marked as such, and must not be
27 *    misrepresented as being the original software.
28 *
29 * 4. This notice may not be removed or altered.
30 */
31
32
33#include "../machine.h"
34
35#if	defined(HASNCACHE) && defined(USE_LIB_RNAM)
36
37# if	!defined(lint)
38static char copyright[] =
39"@(#) Copyright 1997 Purdue Research Foundation.\nAll rights reserved.\n";
40static char *rcsid = "$Id: rnam.c,v 1.11 2008/10/21 16:13:23 abe Exp $";
41# endif	/* !defined(lint) */
42
43#include "../lsof.h"
44
45
46/*
47 * rnam.c - read BSD format (struct namecache or nch) name cache
48 *
49 * This code is effective only when HASNCACHE is defined.
50 */
51
52/*
53 * The caller must:
54 *
55 *	#include the relevant header file -- e.g., <sys/namei.h>.
56 *
57 *	Define X_NCACHE as the nickname for the kernel cache address.
58 *
59 *	Define X_NCSIZE as the nickname for the size of the kernel cache.
60 *
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.
63 *
64 *	Define NCACHE_NO_ROOT if the calling dialect doesn't support
65 *	the locating of the root node of a file system.
66 *
67 *	Define the name of the name cache structure -- e.g.,
68 *
69 *		#define NCACHE	<structure name>
70 *
71 *	Define the following casts, if they differ from the defaults:
72 *
73 *		NCACHE_SZ_CAST	cast for X_NCSIZE (default int)
74 *
75 *	e.g.,
76 *		#define NCACHE_SZ_CAST unsigned long
77 *
78 *	Define the names of these elements of struct NCACHE:
79 *
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)
87 *
88 * The caller may need to:
89 *
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.
92 *
93 *	Define this prototype for ncache_load():
94 *
95 *		_PROTOTYPE(static void ncache_load,(void));
96 */
97
98
99/*
100 * Local static values
101 */
102
103static int Mch;				/* name cache hash mask */
104
105# if	!defined(NCACHE_NC_CAST)
106#define	NCACHE_SZ_CAST	int
107# endif	/* !defined(NCACHE_NC_CAST) */
108
109static NCACHE_SZ_CAST Nc = 0;		/* size of name cache */
110static int Nch = 0;			/* size of name cache hash pointer
111					 * table */
112struct l_nch {
113	KA_T na;			/* node address */
114
115# if	defined(NCACHE_NODEID)
116	unsigned long id;		/* capability ID */
117# endif	/* defined(NCACHE_NODEID) */
118
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) */
124
125	char nm[NCHNAMLEN+1];		/* name */
126	int nl;				/* name length */
127};
128
129static struct l_nch *Ncache = (struct l_nch*)NULL;
130					/* the local name cache */
131static struct l_nch **Nchash = (struct l_nch **)NULL;
132					/* Ncache hash pointers */
133static int Ncfirst = 1;			/* first-call status */
134
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) */
142
143#define DEFNCACHESZ	1024	/* local size if X_NCSIZE kernel value < 1 */
144#define	LNCHINCRSZ	64	/* local size increment */
145
146# if	!defined(NCACHE_NO_ROOT)
147_PROTOTYPE(static int ncache_isroot,(KA_T na, char *cp));
148# endif	/* !defined(NCACHE_NO_ROOT) */
149
150
151/*
152 * ncache_addr() - look up a node's local ncache address
153 */
154
155static struct l_nch *
156
157# if	defined(NCACHE_NODEID)
158ncache_addr(i, na)
159	unsigned long i;		/* node's capability ID */
160# else	/* !defined(NCACHE_NODEID) */
161ncache_addr(na)
162# endif	/* defined(NCACHE_NODEID) */
163
164	KA_T na;			/* node's address */
165{
166	struct l_nch **hp;
167
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) */
173
174	{
175
176# if	defined(NCACHE_NODEID)
177	    if ((*hp)->id == i && (*hp)->na == na)
178# else	/* !defined(NCACHE_NODEID) */
179	    if ((*hp)->na == na)
180# endif	/* defined(NCACHE_NODEID) */
181
182		return(*hp);
183	}
184	return((struct l_nch *)NULL);
185}
186
187
188# if	!defined(NCACHE_NO_ROOT)
189/*
190 * ncache_isroot() - is head of name cache path a file system root?
191 */
192
193static int
194ncache_isroot(na, cp)
195	KA_T na;				/* kernel node address */
196	char *cp;				/* partial path */
197{
198	char buf[MAXPATHLEN];
199	int i;
200	MALLOC_S len;
201	struct mounts *mtp;
202	static int nca = 0;
203	static int ncn = 0;
204	static KA_T *nc = (KA_T *)NULL;
205	struct stat sb;
206	struct vnode v;
207
208	if (!na)
209	    return(0);
210/*
211 * Search the root vnode cache.
212 */
213	for (i = 0; i < ncn; i++) {
214	    if (na == nc[i])
215		return(1);
216	}
217/*
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.
220 *
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.
225 */
226	if (kread((KA_T)na, (char *)&v, sizeof(v))
227	||  v.v_type != VDIR || !(v.v_flag & VROOT)) {
228
229	/*
230	 * The vnode tests failed.  Try the inode tests.
231	 */
232	    if (Lf->inp_ty != 1 || !Lf->inode
233	    ||  !Lf->fsdir || (len = strlen(Lf->fsdir)) < 1)
234		return(0);
235	    if ((len + 1 + strlen(cp) + 1) > sizeof(buf))
236		return(0);
237	    for (mtp = readmnt(); mtp; mtp = mtp->next) {
238		if (!mtp->dir || !mtp->inode)
239		    continue;
240		if (strcmp(Lf->fsdir, mtp->dir) == 0)
241		    break;
242	    }
243	    if (!mtp)
244		return(0);
245	    (void) strcpy(buf, Lf->fsdir);
246	    if (buf[len - 1] != '/')
247		buf[len++] = '/';
248	    (void) strcpy(&buf[len], cp);
249	    if (statsafely(buf, &sb) != 0
250	    ||  (unsigned long)sb.st_ino != Lf->inode)
251		return(0);
252	}
253/*
254 * Add the node address to the root node cache.
255 */
256	if (ncn >= nca) {
257	    if (!nca) {
258		len = (MALLOC_S)(10 * sizeof(KA_T));
259		nc = (KA_T *)malloc(len);
260	    } else {
261		len = (MALLOC_S)((nca + 10) * sizeof(KA_T));
262		nc = (KA_T *)realloc(nc, len);
263	    }
264	    if (!nc) {
265		(void) fprintf(stderr, "%s: no space for root node table\n",
266		    Pn);
267		Exit(1);
268	    }
269	    nca += 10;
270	}
271	nc[ncn++] = na;
272	return(1);
273}
274# endif	/* !defined(NCACHE_NO_ROOT) */
275
276
277/*
278 * ncache_load() - load the kernel's name cache
279 */
280
281void
282ncache_load()
283{
284	struct l_nch **hp, *lc;
285	int i, len, n;
286	static int iNc = 0;
287	struct NCACHE *kc;
288	static KA_T kp = (KA_T)NULL;
289	KA_T v;
290
291# if	defined(NCACHE_NXT)
292	static KA_T kf;
293	struct NCACHE nc;
294# else	/* !defined NCACHE_NXT) */
295	static struct NCACHE *kca = (struct NCACHE *)NULL;
296# endif	/* defined(NCACHE_NXT) */
297
298	if (!Fncache)
299	    return;
300	if (Ncfirst) {
301
302	/*
303	 * Do startup (first-time) functions.
304	 */
305	    Ncfirst = 0;
306	/*
307	 * Establish kernel cache size.
308	 */
309	    v = (KA_T)0;
310	    if (get_Nl_value(X_NCSIZE, (struct drive_Nl *)NULL, &v) < 0
311	    ||  !v
312	    ||  kread((KA_T)v, (char *)&Nc, sizeof(Nc)))
313	    {
314		if (!Fwarn)
315		    (void) fprintf(stderr,
316			"%s: WARNING: can't read name cache size: %s\n",
317			Pn, print_kptr(v, (char *)NULL, 0));
318		iNc = Nc = 0;
319		return;
320	    }
321	    iNc = Nc;
322	    if (Nc < 1) {
323		if (!Fwarn) {
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);
328		}
329		iNc = Nc = DEFNCACHESZ;
330	    }
331	/*
332	 * Establish kernel cache address.
333	 */
334	    v = (KA_T)0;
335	    if (get_Nl_value(X_NCACHE, (struct drive_Nl *)NULL, &v) < 0
336	    ||  !v
337	    ||  kread((KA_T)v, (char *)&kp, sizeof(kp))) {
338		if (!Fwarn)
339		    (void) fprintf(stderr,
340			"%s: WARNING: can't read name cache address: %s\n",
341			Pn, print_kptr(v, (char *)NULL, 0));
342		iNc = Nc = 0;
343		return;
344	    }
345
346# if	defined(NCACHE_NXT)
347	    kf = kp;
348
349# else	/* !defined(NCACHE_NXT) */
350	/*
351	 * Allocate space for a local copy of the kernel's cache.
352	 */
353	    len = Nc * sizeof(struct NCACHE);
354	    if (!(kca = (struct NCACHE *)malloc((MALLOC_S)len))) {
355		if (!Fwarn)
356		    (void) fprintf(stderr,
357			"%s: can't allocate name cache space: %d\n", Pn, len);
358		Exit(1);
359	    }
360# endif	/* defined(NCACHE_NXT) */
361
362	/*
363	 * Allocate space for the local cache.
364	 */
365	    len = Nc * sizeof(struct l_nch);
366	    if (!(Ncache = (struct l_nch *)malloc((MALLOC_S)len))) {
367
368no_local_space:
369
370		if (!Fwarn)
371		    (void) fprintf(stderr,
372			"%s: no space for %d byte local name cache\n", Pn, len);
373		Exit(1);
374	    }
375	} else {
376
377	/*
378	 * Do setup for repeat calls.
379	 */
380	    if ((Nc = iNc) == 0)
381		return;
382	    if (Nchash) {
383		(void) free((FREE_P *)Nchash);
384		Nchash = (struct l_nch **)NULL;
385	    }
386
387# if    defined(NCACHE_NXT)
388	    kp = kf;
389# endif /* defined(NCACHE_NXT) */
390
391	}
392
393# if    !defined(NCACHE_NXT)
394
395/*
396 * Read the kernel's name cache.
397 */
398	if (kread(kp, (char *)kca, (Nc * sizeof(struct NCACHE)))) {
399	    if (!Fwarn)
400		(void) fprintf(stderr,
401		    "%s: WARNING: can't read kernel's name cache: %s\n",
402		    Pn, print_kptr(kp, (char *)NULL, 0));
403	    Nc = 0;
404	    return;
405        }
406# endif /* !defined(NCACHE_NXT) */
407
408/*
409 * Build a local copy of the kernel name cache.
410 */
411
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) */
417
418	{
419
420# if	defined(NCACHE_NXT)
421	    if (kread(kp, (char *)kc, sizeof(nc)))
422		break;
423	    if ((kp = (KA_T)kc->NCACHE_NXT) == kf)
424		kp = (KA_T)NULL;
425# endif	/* defined(NCACHE_NXT) */
426
427	    if (!kc->NCACHE_NODEADDR)
428		continue;
429	    if ((len = kc->NCACHE_NMLEN) < 1 || len > NCHNAMLEN)
430		continue;
431	    if (len < 3 && kc->NCACHE_NM[0] == '.') {
432		if (len == 1 || (len == 2 && kc->NCACHE_NM[1] == '.'))
433		    continue;
434	    }
435
436# if	defined(NCACHE_NXT)
437	    if (n >= Nc) {
438		Nc += LNCHINCRSZ;
439		if (!(Ncache = (struct l_nch *)realloc(Ncache,
440		     (MALLOC_S)(Nc * sizeof(struct l_nch)))))
441		{
442		    (void) fprintf(stderr,
443			"%s: no more space for %d entry local name cache\n",
444			Pn, Nc);
445		    Exit(1);
446		}
447		lc = &Ncache[n];
448	    }
449# endif	/* defined(NCACHE_NXT) */
450
451#  if	defined(NCACHE_NODEID)
452	    lc->na = (KA_T)kc->NCACHE_NODEADDR;
453	    lc->id = kc->NCACHE_NODEID;
454#  endif	/* defined(NCACHE_NODEID) */
455
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) */
460
461#  if	defined(NCACHE_PARID)
462	    lc->did = kc->NCACHE_PARID;
463#  endif	/* defined(NCACHE_PARID) */
464
465	    (void) strncpy(lc->nm, kc->NCACHE_NM, len);
466	    lc->nm[len] = '\0';
467	    lc->nl = strlen(lc->nm);
468	    n++;
469	    lc++;
470
471# if	defined(NCACHE_NXT)
472	    if (n >= i) {
473		if (!Fwarn)
474		    (void) fprintf(stderr,
475			"%s: WARNING: name cache truncated at %d entries\n",
476			Pn, n);
477		break;
478	    }
479# endif	/* defined(NCACHE_NXT) */
480
481	}
482/*
483 * Reduce memory usage, as required.
484 */
485
486# if	!defined(NCACHE_NXT)
487	if (!RptTm)
488	    (void) free((FREE_P *)kca);
489# endif	/* !defined(NCACHE_NXT) */
490
491	if (n < 1) {
492	    Nc = 0;
493	    if (!RptTm) {
494		(void) free((FREE_P *)Ncache);
495		Ncache = (struct l_nch *)NULL;
496	    }
497	    if (!Fwarn)
498		(void) fprintf(stderr,
499		    "%s: WARNING: unusable name cache size: %d\n", Pn, n);
500	    return;
501	}
502	if (n < Nc) {
503	    Nc = n;
504	    if (!RptTm) {
505		len = Nc * sizeof(struct l_nch);
506		if (!(Ncache = (struct l_nch *)realloc(Ncache, len)))
507		    goto no_local_space;
508	    }
509	}
510/*
511 * Build a hash table to locate Ncache entries.
512 */
513	for (Nch = 1; Nch < Nc; Nch <<= 1)
514	    ;
515	Nch <<= 1;
516	Mch = Nch - 1;
517	if (!(Nchash = (struct l_nch **)calloc(Nch+Nc, sizeof(struct l_nch *))))
518	{
519	    if (!Fwarn)
520		(void) fprintf(stderr,
521		    "%s: no space for %d name cache hash pointers\n",
522		    Pn, Nch + Nc);
523	    Exit(1);
524	}
525	for (i = 0, lc = Ncache; i < Nc; i++, lc++) {
526
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) */
532
533	    {
534
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) */
540
541		&&  strcmp((*hp)->nm, lc->nm) == 0
542
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) */
546
547		) {
548		    n = 0;
549		    break;
550		}
551	    }
552	    if (n)
553		*hp = lc;
554	}
555
556# if	defined(NCACHE_PARADDR) && defined(NCACHE_PARID)
557/*
558 * Make a final pass through the local cache and convert parent node
559 * addresses to local name cache pointers.
560 */
561	for (i = 0, lc = Ncache; i < Nc; i++, lc++) {
562	    if (!lc->pa)
563		continue;
564	    lc->pla = ncache_addr(lc->did, lc->pa);
565	}
566# endif	/* defined(NCACHE_PARADDR) && defined(NCACHE_PARID) */
567}
568
569
570/*
571 * ncache_lookup() - look up a node's name in the kernel's name cache
572 */
573
574char *
575ncache_lookup(buf, blen, fp)
576	char *buf;			/* receiving name buffer */
577	int blen;			/* receiving buffer length */
578	int *fp;			/* full path reply */
579{
580	char *cp = buf;
581	struct l_nch *lc;
582	struct mounts *mtp;
583	int nl, rlen;
584
585	*cp = '\0';
586	*fp = 0;
587
588# if	defined(HASFSINO)
589/*
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.
593 */
594	if ((Lf->inp_ty == 1) && Lf->fs_ino && (Lf->inode == Lf->fs_ino))
595	    return(cp);
596# endif	/* defined(HASFSINO) */
597
598/*
599 * Look up the name cache entry for the node address.
600 */
601
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) */
607
608
609	{
610
611	/*
612	 * If the node has no cache entry, see if it's the mount
613	 * point of a known file system.
614	 */
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)
619		    continue;
620		if (Lf->dev == mtp->dev
621		&&  mtp->inode == Lf->inode
622		&&  strcmp(mtp->dir, Lf->fsdir) == 0)
623		    return(cp);
624	    }
625	    return((char *)NULL);
626	}
627/*
628 * Start the path assembly.
629 */
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);
635
636# if	defined(NCACHE_PARADDR) && defined(NCACHE_PARID)
637/*
638 * Look up the name cache entries that are parents of the node address.
639 * Quit when:
640 *
641 *	there's no parent;
642 *	the name length is too large to fit in the receiving buffer.
643 */
644	for (;;) {
645	    if (!lc->pla) {
646
647#  if	!defined(NCACHE_NO_ROOT)
648		if (ncache_isroot(lc->pa, cp))
649		    *fp = 1;
650#  endif	/* !defined(NCACHE_NO_ROOT) */
651
652		break;
653	    }
654	    lc = lc->pla;
655	    if (((nl = lc->nl) + 1) > rlen)
656		break;
657	    *(cp - 1) = '/';
658	    cp--;
659	    rlen--;
660	    (void) strncpy((cp - nl), lc->nm, nl);
661	    cp -= nl;
662	    rlen -= nl;
663	}
664# endif	/* defined(NCACHE_PARADDR) && defined(NCACHE_PARID) */
665	return(cp);
666}
667#else	/* !defined(HASNCACHE) || !defined(USE_LIB_RNAM) */
668char rnam_d1[] = "d"; char *rnam_d2 = rnam_d1;
669#endif	/* defined(HASNCACHE) && defined(USE_LIB_RNAM) */
670