1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <unistd.h>
4 #include <fcntl.h>
5 #include <kvm.h>
6 #include <nlist.h>
7 #include <sysexits.h>
8 #include <sys/uio.h>
9 #include <sys/namei.h>
10 #include <sys/param.h>
11 #include <sys/queue.h>
12 #include <sys/time.h>
13 #include <sys/vnode.h>
14 /*----------------------------------*/
15 static u_int crc16_table[16] = {
16 0x0000, 0xCC01, 0xD801, 0x1400,
17 0xF001, 0x3C00, 0x2800, 0xE401,
18 0xA001, 0x6C00, 0x7800, 0xB401,
19 0x5000, 0x9C01, 0x8801, 0x4400
20 };
21
22 /* XXX Taken from sys/kern/vfs_cache.c */
23 struct namecache {
24 LIST_ENTRY(namecache) nc_hash;
25 LIST_ENTRY(namecache) nc_src;
26 TAILQ_ENTRY(namecache) nc_dst;
27 struct vnode *nc_dvp;
28 struct vnode *nc_vp;
29 u_char nc_flag;
30 u_char nc_nlen;
31 char nc_name[0];
32 };
33
34 static u_short
wlpsacrc(u_char * buf,u_int len)35 wlpsacrc(u_char *buf, u_int len)
36 {
37 u_short crc = 0;
38 int i, r1;
39
40 for (i = 0; i < len; i++, buf++) {
41 /* lower 4 bits */
42 r1 = crc16_table[crc & 0xF];
43 crc = (crc >> 4) & 0x0FFF;
44 crc = crc ^ r1 ^ crc16_table[*buf & 0xF];
45
46 /* upper 4 bits */
47 r1 = crc16_table[crc & 0xF];
48 crc = (crc >> 4) & 0x0FFF;
49 crc = crc ^ r1 ^ crc16_table[(*buf >> 4) & 0xF];
50 }
51 return(crc);
52 }
53
54 /*----------------------------------*/
55 struct nlist nl[] = {
56 { "_nchash", 0},
57 { "_nchashtbl", 0},
58 { 0, 0 },
59 };
60
61 int histo[2047];
62 int histn[2047];
63 int *newbucket;
64
65 int
main(int argc,char ** argv)66 main(int argc, char **argv)
67 {
68 int nchash, i, j, k, kn;
69 int nb, p1, p2;
70 u_long p;
71 LIST_HEAD(nchashhead, namecache) *nchashtbl;
72 struct namecache *nc;
73 struct vnode vn;
74
75 kvm_t *kvm = kvm_open(NULL, NULL, NULL, O_RDONLY, argv[0]);
76 if (kvm == NULL)
77 return(EX_OSERR);
78
79 printf("kvm: %p\n", kvm);
80 printf("kvm_nlist: %d\n", kvm_nlist(kvm, nl));
81 kvm_read(kvm, nl[0].n_value, &nchash, sizeof nchash);
82 nchash++;
83 nchashtbl = malloc(nchash * sizeof *nchashtbl);
84 nc = malloc(sizeof *nc + NAME_MAX);
85 newbucket = malloc(nchash * sizeof (int));
86 memset(newbucket, 0, nchash * sizeof (int));
87 kvm_read(kvm, nl[1].n_value, &p, sizeof p);
88 kvm_read(kvm, p, nchashtbl, nchash * sizeof *nchashtbl);
89 for (i=0; i < nchash; i++) {
90 #if 0
91 printf("%d\n", i);
92 #endif
93 nb=0;
94 p = (u_long)LIST_FIRST(nchashtbl+i);
95 while (p) {
96 nb++;
97 kvm_read(kvm, p, nc, sizeof *nc + NAME_MAX);
98 kvm_read(kvm, (u_long)nc->nc_dvp, &vn, sizeof vn);
99 nc->nc_name[nc->nc_nlen] = '\0';
100 for (j=k=kn=0;nc->nc_name[j];j++) {
101 k+= nc->nc_name[j];
102 kn <<= 1;
103 kn+= nc->nc_name[j];
104 }
105 /*
106 kn = k;
107 */
108 kn = wlpsacrc(nc->nc_name,nc->nc_nlen);
109
110 /* kn += (u_long)vn.v_data >> 8; */
111 /* kn += (u_long)nc->nc_dvp >> 7; */
112 kn += vn.v_id;
113 kn &= (nchash - 1);
114 newbucket[kn]++;
115 #if 1
116 printf("%4d dvp %08x hash %08x vp %08x id %08x name <%s>\n",
117 i,nc->nc_dvp, k, nc->nc_vp, vn.v_id, nc->nc_name);
118 #endif
119 p = (u_long)LIST_NEXT(nc, nc_hash);
120 }
121 histo[nb]++;
122 }
123 for (i=0; i < nchash; i++) {
124 histn[newbucket[i]]++;
125 }
126 p1=p2 = 0;
127 for (i=0;i<30;i++) {
128 p1 += histo[i] * i;
129 p2 += histn[i] * i;
130 if (histo[i] || histn[i])
131 printf("H%02d %4d %4d / %4d %4d\n",i,histo[i], p1 , histn[i], p2);
132 }
133
134 return (0);
135 }
136
137