/* device name <-> number map system optimized for rapid, constant time lookup. * Copyright (C) 1996 Charles Blake, see ../COPYING.LIB for distribution * conditions. * Copyright (C) 1998 Michael K. Johnson */#include <errno.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <sys/types.h>#include <sys/stat.h>#include <sys/mman.h>#include <dirent.h>#include <unistd.h>#include <fcntl.h>#define __KERNEL__#include <linux/kdev_t.h>#undef __KERNEL__#define DEVDIR		"/dev"#define DEVTAB		"psdevtab"static char *devtab_paths[] = {    "/etc/" DEVTAB,    "%s/."  DEVTAB,    NULL};#define DEVINITIALMODE	0664#define DEV_MAX_PATH	(5+256)#define DEV_NAME_MAX	8static dev_t major[] = { 2, 3, 4, 5, 19, 20, 22, 23, 24, 25, 32, 33,			46, 47, 48, 49 };#define Nminor		256#define Nmajor		(sizeof(major)/sizeof(dev_t))#define Ndev		(Nmajor*Nminor)#define Ndevtab		(Ndev*DEV_NAME_MAX)static char* devtab;	/* the memory buffer holding all the name strings *//* This macro evaluates to the address into the table of the string of   DEV_NAME_MAX chars for the device with major m, minor n. */#define TAB(m,n) (devtab + (m)*(Nminor*DEV_NAME_MAX) + (n)*DEV_NAME_MAX)static int devtab_initialized = 0;static char* name_to_path(char* name);	/* forward declarations */static int   init_devtab (void);/* Device Name -> Number Map   many-to-one: -1 on failed match.*/dev_t name_to_dev(char* name) {    static struct stat sbuf;    return (stat(name_to_path(name), &sbuf) < 0) ? -1 : sbuf.st_rdev;}/* find m in a[] assuming a is sorted into ascending order *//* in-line linear search placeholder until more majors warrant binary search */static __inline__ int lookup(dev_t m, dev_t* a, int n) {    int k;    for(k=0; k < n && a[k] != m; k++)	;    return (k < n) ? k : -1;}/* Device Number -> Name Map   one-to-many: first directory order match in DEVDIR, "" on failed match.*/char* dev_to_name(dev_t num) {    static char	rval[DEV_NAME_MAX+1];    dev_t m = MAJOR(num), n = MINOR(num), tmp;    if (!devtab_initialized && !init_devtab())	return "";    if ((tmp = lookup(m, major, Nmajor)) == (dev_t)-1)	return "";    strncpy(rval, TAB(tmp,n), DEV_NAME_MAX);    rval[DEV_NAME_MAX] = '\0';    return rval;}static int dev_to_devtab(int);static int init_devtab(void) {    static struct stat sbuf, lbuf;    static int fd;    char **fmt, path[64], *HOME = getenv("HOME") ? getenv("HOME") : "";    for (fmt = devtab_paths; *fmt; fmt++) {	snprintf(path, sizeof path, *fmt, HOME);	lbuf.st_ino = 0; /* initialize for test later */	if (lstat(path, &lbuf) >= 0 && S_ISLNK(lbuf.st_mode))	    /* don't follow symlinks */	    continue;	if ( (fd = open(path, O_RDONLY)) < 0	/* open DEVTAB file */	     || fstat(fd, &sbuf) < 0		/* fstat it */	     || (lbuf.st_ino && (sbuf.st_ino != lbuf.st_ino)) /* race */	     || sbuf.st_nlink > 1		/* hardlink attack */	     || sbuf.st_size != Ndevtab		/* make sure it's the right size */	     || (devtab = mmap(0, Ndevtab, PROT_READ, MAP_SHARED, fd, 0)) == (caddr_t) -1	     || close(fd) == -1)	    {	/* could not open for read, attempt to fix/create */		int oumsk = umask(0);		if (devtab)		    munmap(devtab, Ndevtab);		if (((fd = open(path, O_RDWR|O_TRUNC|O_CREAT, DEVINITIALMODE)) == -1 &&		     (unlink(path), fd = open(path, O_RDWR|O_TRUNC|O_CREAT, DEVINITIALMODE)) == -1)		     || !dev_to_devtab(fd)) {		    close(fd);          /* either both opens failed or the constructor failed */		    unlink(path);	/* in case we created but could not fill a file */		    umask(oumsk);		    continue;		} else {		    devtab_initialized = 1;		    close(fd);		    umask(oumsk);		    return 1;		}	    }	else	    return devtab_initialized = 1;    }    return devtab_initialized;}/* stat every file in DEVDIR saving its basename in devtab[] if it has   a MAJOR(st_rdev) in our list of majors. return 0 on error otherwise 1. */static int dev_to_devtab(int fd) {    static struct stat sbuf;    int i;    dev_t m;    struct dirent* ent;    DIR* dev;        if (!(dev = opendir(DEVDIR))) {	fprintf(stderr, "%s: %s\nCannot generate device number -> name mapping.\n",		DEVDIR, strerror(errno));	return 0;    }    if (!(devtab = malloc(Ndevtab))) {	fprintf(stderr, "%s: could not allocate memory\n", strerror(errno));	return 0;    }    memset((void*)devtab, 0, Ndevtab);    while ((ent = readdir(dev))) {	/* loop over all dirents in DEVDIR */	if (lstat(name_to_path(ent->d_name), &sbuf) < 0	    || !S_ISCHR(sbuf.st_mode))	    /* only look for char special devs */	    continue;			    /* due to overloading of majors */	m = MAJOR(sbuf.st_rdev);	    /* copy name to appropriate spot */	if ((i = lookup(m, major, Nmajor)) != -1)	    strncpy(TAB(i,MINOR(sbuf.st_rdev)), ent->d_name, DEV_NAME_MAX);    }    closedir(dev);    if (write(fd, devtab, Ndevtab) != Ndevtab) /* probably no disk space */	return 0;    return 1;}static char path[DEV_MAX_PATH];static char* name_to_path(char* name) {    static char* Path;    if (!Path) {	strcpy(path, DEVDIR);		/* copy DEVDIR */	path[sizeof(DEVDIR) - 1] = '/';	/* change NUL to '/' */	Path = path + sizeof(DEVDIR);	/* put Path at start of basename */    }    strncpy(Path, name, DEV_MAX_PATH - sizeof(DEVDIR));    return path;}#ifdef TEST_DEVNAMEint main(int argc, char** argv) {	/* usage: cmd [<major> <minor>|<name>] */    dev_t tmp;    if (argc < 2) {	printf("%s: [ maj min... | name ... ]\n", argv[0]);	return 0;    }    if (argv[1][0] >= '0' && argv[1][0] <= '9')	for(argv++ ; argv[0] && argv[1] ; argv+=2)	    printf("%s\n", dev_to_name(MKDEV( atoi(argv[0]), atoi(argv[1]) )));    else	for(argv++ ; *argv ; argv++) {	    tmp = name_to_dev(*argv);	    printf("%d, %d\n", MAJOR(tmp), MINOR(tmp));	}    return 0;}#endif/*Using this program on over 700 files in /dev to perform number->name resolutiontook well under 300 microsecs per device number pair on a Pentium 90.  It issomewhat tough to time because once the 3 pages have been mapped in, the time isalmost zero.  For things like top, this method may even be faster in the longrun.  Those interested can gprof it for me.  This system has the virtue of beingnearly perfectly adaptable to individual systems, self updating when /devchanges and pretty darn fast when it hasn't.  It will be slow for users withoutperms to change the psdevtab file, though.  So this is what I decided wasreasonable.  If the process does not have perms to create or update/etc/psdevtab and it is out of date, we try /tmp/psdevtab.  If /tmp/psdevtab iseither out of date or unreadable (malicious user creates it and chmods it),$HOME/.psdevtab is used.  This secondarily allows for per-user naming of ttys,but is really so that at most one user sees only a single delay per /devmodification.To do the timings I did something like this with zsh:    a=(`ls -l *(%^@/) | awk '{print $5 $6}' | sed 's/,/ /'`);    time ./test $aFinally, for lack of a better file for these to be in, I have collected theold algorithmic device number <-> device name mappings.  Let m = major device number and n = minor device number satisfy:    devno = m<<8 + n , m = devno>>8 , n = devno && 0x00FF, and let    char L[32]="pqrstuvwxyzABCDEFGHIJKLMNOPQRSTU", H[16]="01234567890abcdef";	DEVICE NUMBERS		SPECIAL FILE NAMES  OLD SYSTEM (64 pseudoterminal devices):	m=4:	    n=0..63:	tty + itoa_dec(n+1)	    n=128..191:	pty + L[(n-128)/16] + H[(n-128)%16]	    n=192..255:	tty + L[(n-192)/16] + H[(n-192)%16]  NEW SYSTEM (256/512 pseudoterminal devices):	m=2, n:		pty + L[n/16] + H[n%16]	m=3, n:		tty + L[n/16] + H[n%16]	m=4, n:		tty + itoa_dec(n+1)	m=49, n:	pty + L[16+n/16] + H[n%16]	m=50, n:	tty + L[16+n/16] + H[n%16]  (THE SAME IN EITHER SYSTEM)  CALL-UNIX AND CONTROLLING TERMINAL DEVICES	m=5:	    n=0:	tty	    n=64..128:	cua  + {'0' + (n-64)}  CYCLADES MULTIPORT:	m=19, n:	ttyC + itoa_hex(n)	m=20, n: cub + itoa_hex(n) *//* Re-implementation of old interface with the new generic functions. *//* This does exactly the same thing as name_to_dev only now a full "ttyXX"   specification will work as well.*/int tty_to_dev(char *tty) {    static char pref_name_1[32] = "tty", *pnam1 = pref_name_1 + 3,	        pref_name_2[32] = "cu",  *pnam2 = pref_name_2 + 2;    dev_t num;    if ((num = name_to_dev(tty)) != (dev_t) -1)	/* try tty straight up */	return num;    strncpy(pnam1, tty, 32 - 3);	/* try with "tty" prepended */    if ((num = name_to_dev(pref_name_1)) != (dev_t) -1)	return num;    strncpy(pnam2, tty, 32 - 2);	/* try with "cu" prepended */    if ((num = name_to_dev(pref_name_2)) != (dev_t) -1)	return num;    return -1;		/* no match */}/* new abstraction that can maybe be generalized a little better. */char* abbrev_of_tty(char *tty) {    static char temp[32];		/* return buf: good only until next call */    char *pos = strpbrk(tty, "yu");	/* end of (presumed) prefices: tty*, cu* */    temp[0] = 0;    if (tty && tty[0] && pos && pos[0] && pos[1])	sprintf(temp, "%*.*s", 3, 3, pos + 1);    else	strncpy(temp, " ? ", 31);    return temp;}/* Do in-place modification of the 4-buffer `tty' based upon `dev' */void dev_to_tty(char *tty, int dev) {    char* new = abbrev_of_tty(dev_to_name(dev));    strncpy(tty, new, 4);}