160833Sjake/* $FreeBSD$ */
229095Sphk#include <stdio.h>
329095Sphk#include <stdlib.h>
429095Sphk#include <unistd.h>
529095Sphk#include <fcntl.h>
629095Sphk#include <kvm.h>
729095Sphk#include <nlist.h>
888799Skbyanc#include <sysexits.h>
929095Sphk#include <sys/uio.h>
1029095Sphk#include <sys/namei.h>
1129095Sphk#include <sys/param.h>
1288799Skbyanc#include <sys/queue.h>
1329095Sphk#include <sys/time.h>
1429095Sphk#include <sys/vnode.h>
1529095Sphk/*----------------------------------*/
1629095Sphkstatic u_int crc16_table[16] = {
1729095Sphk    0x0000, 0xCC01, 0xD801, 0x1400,
1829095Sphk    0xF001, 0x3C00, 0x2800, 0xE401,
1929095Sphk    0xA001, 0x6C00, 0x7800, 0xB401,
2029095Sphk    0x5000, 0x9C01, 0x8801, 0x4400
2129095Sphk};
2229095Sphk
2388799Skbyanc/* XXX Taken from sys/kern/vfs_cache.c */
2488799Skbyancstruct	namecache {
2588799Skbyanc	LIST_ENTRY(namecache) nc_hash;
2688799Skbyanc	LIST_ENTRY(namecache) nc_src;
2788799Skbyanc	TAILQ_ENTRY(namecache) nc_dst;
2888799Skbyanc	struct	vnode *nc_dvp;
2988799Skbyanc	struct	vnode *nc_vp;
3088799Skbyanc	u_char	nc_flag;
3188799Skbyanc	u_char	nc_nlen;
3288799Skbyanc	char	nc_name[0];
3388799Skbyanc};
3488799Skbyanc
3529095Sphkstatic u_short
3629095Sphkwlpsacrc(u_char *buf, u_int len)
3729095Sphk{
3829095Sphk    u_short     crc = 0;
3929095Sphk    int         i, r1;
4029095Sphk
4129095Sphk    for (i = 0; i < len; i++, buf++) {
4229095Sphk        /* lower 4 bits */
4329095Sphk        r1 = crc16_table[crc & 0xF];
4429095Sphk        crc = (crc >> 4) & 0x0FFF;
4529095Sphk        crc = crc ^ r1 ^ crc16_table[*buf & 0xF];
4629095Sphk
4729095Sphk        /* upper 4 bits */
4829095Sphk        r1 = crc16_table[crc & 0xF];
4929095Sphk        crc = (crc >> 4) & 0x0FFF;
5029095Sphk        crc = crc ^ r1 ^ crc16_table[(*buf >> 4) & 0xF];
5129095Sphk    }
5229095Sphk    return(crc);
5329095Sphk}
5429095Sphk
5529095Sphk/*----------------------------------*/
5629095Sphkstruct nlist nl[] = {
5729095Sphk	{ "_nchash", 0},
5829095Sphk	{ "_nchashtbl", 0},
5929095Sphk	{ 0, 0 },
6029095Sphk};
6129095Sphk
6229095Sphkint histo[2047];
6329095Sphkint histn[2047];
6429095Sphkint *newbucket;
6529095Sphk
6629095Sphkint
6729095Sphkmain(int argc, char **argv)
6829095Sphk{
6929095Sphk	int nchash, i, j, k, kn;
7029095Sphk	int nb, p1, p2;
7129095Sphk	u_long p;
7260938Sjake	LIST_HEAD(nchashhead, namecache) *nchashtbl;
7329095Sphk	struct namecache *nc;
7429095Sphk	struct vnode vn;
7529095Sphk
7688799Skbyanc	kvm_t *kvm = kvm_open(NULL, NULL, NULL, O_RDONLY, argv[0]);
7788799Skbyanc	if (kvm == NULL)
7888799Skbyanc		return(EX_OSERR);
7929095Sphk
8029095Sphk	printf("kvm: %p\n", kvm);
8129095Sphk	printf("kvm_nlist: %d\n", kvm_nlist(kvm, nl));
8229095Sphk	kvm_read(kvm, nl[0].n_value, &nchash, sizeof nchash);
8329095Sphk	nchash++;
8429095Sphk	nchashtbl = malloc(nchash * sizeof *nchashtbl);
8588799Skbyanc	nc = malloc(sizeof *nc + NAME_MAX);
8629095Sphk	newbucket = malloc(nchash * sizeof (int));
8729095Sphk	memset(newbucket, 0, nchash * sizeof (int));
8829095Sphk	kvm_read(kvm, nl[1].n_value, &p, sizeof p);
8929095Sphk	kvm_read(kvm, p, nchashtbl, nchash * sizeof *nchashtbl);
9029095Sphk	for (i=0; i < nchash; i++) {
9129095Sphk#if 0
9229095Sphk		printf("%d\n", i);
9329095Sphk#endif
9429095Sphk		nb=0;
9529095Sphk		p = (u_long)LIST_FIRST(nchashtbl+i);
9629095Sphk		while (p) {
9729095Sphk			nb++;
9888799Skbyanc			kvm_read(kvm, p, nc, sizeof *nc + NAME_MAX);
9929095Sphk			kvm_read(kvm, (u_long)nc->nc_dvp, &vn, sizeof vn);
10029095Sphk			nc->nc_name[nc->nc_nlen] = '\0';
10129095Sphk			for (j=k=kn=0;nc->nc_name[j];j++) {
10229095Sphk				k+= nc->nc_name[j];
10329095Sphk				kn <<= 1;
10429095Sphk				kn+= nc->nc_name[j];
10529095Sphk			}
10629095Sphk			/*
10729095Sphk			kn = k;
10829095Sphk			*/
10929095Sphk			kn = wlpsacrc(nc->nc_name,nc->nc_nlen);
11029095Sphk
11129095Sphk			/* kn += (u_long)vn.v_data >> 8;  */
11229095Sphk			/* kn += (u_long)nc->nc_dvp >> 7;    */
11329095Sphk			kn += vn.v_id;
11429095Sphk			kn &= (nchash - 1);
11529095Sphk			newbucket[kn]++;
11629095Sphk#if 1
11729095Sphk			printf("%4d  dvp %08x  hash %08x  vp %08x  id %08x  name <%s>\n",
11829095Sphk				i,nc->nc_dvp, k, nc->nc_vp, vn.v_id, nc->nc_name);
11929095Sphk#endif
12029095Sphk			p = (u_long)LIST_NEXT(nc, nc_hash);
12129095Sphk		}
12229095Sphk		histo[nb]++;
12329095Sphk	}
12429095Sphk	for (i=0; i < nchash; i++) {
12529095Sphk		histn[newbucket[i]]++;
12629095Sphk	}
12729095Sphk	p1=p2 = 0;
12829095Sphk	for (i=0;i<30;i++) {
12929095Sphk		p1 += histo[i] * i;
13029095Sphk		p2 += histn[i] * i;
13129095Sphk		if (histo[i] || histn[i])
13229095Sphk			printf("H%02d %4d %4d / %4d %4d\n",i,histo[i], p1 , histn[i], p2);
13329095Sphk	}
13429095Sphk
13529095Sphk	return (0);
13629095Sphk}
13729095Sphk
138