1 /* $NetBSD: subr_hash.c,v 1.12 2021/06/13 14:58:49 simonb Exp $ */
2
3 /*
4 * Copyright (c) 1982, 1986, 1991, 1993
5 * The Regents of the University of California. All rights reserved.
6 * (c) UNIX System Laboratories, Inc.
7 * All or some portions of this file are derived from material licensed
8 * to the University of California by American Telephone and Telegraph
9 * Co. or Unix System Laboratories, Inc. and are reproduced herein with
10 * the permission of UNIX System Laboratories, Inc.
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
14 * are met:
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 * 3. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 *
36 * @(#)kern_subr.c 8.4 (Berkeley) 2/14/95
37 */
38
39 #include <sys/cdefs.h>
40 __KERNEL_RCSID(0, "$NetBSD: subr_hash.c,v 1.12 2021/06/13 14:58:49 simonb Exp $");
41
42 #include <sys/param.h>
43 #include <sys/bitops.h>
44 #include <sys/kmem.h>
45 #include <sys/systm.h>
46 #include <sys/pslist.h>
47 #include <sys/rwlock.h>
48 #include <sys/sysctl.h>
49
50 static int hashstat_sysctl(SYSCTLFN_PROTO);
51
52 static size_t
hash_list_size(enum hashtype htype)53 hash_list_size(enum hashtype htype)
54 {
55 LIST_HEAD(, generic) *hashtbl_list;
56 SLIST_HEAD(, generic) *hashtbl_slist;
57 TAILQ_HEAD(, generic) *hashtbl_tailq;
58 struct pslist_head *hashtbl_pslist;
59 size_t esize;
60
61 switch (htype) {
62 case HASH_LIST:
63 esize = sizeof(*hashtbl_list);
64 break;
65 case HASH_PSLIST:
66 esize = sizeof(*hashtbl_pslist);
67 break;
68 case HASH_SLIST:
69 esize = sizeof(*hashtbl_slist);
70 break;
71 case HASH_TAILQ:
72 esize = sizeof(*hashtbl_tailq);
73 break;
74 default:
75 panic("hashdone: invalid table type");
76 }
77 return esize;
78 }
79
80 /*
81 * General routine to allocate a hash table.
82 * Allocate enough memory to hold at least `elements' list-head pointers.
83 * Return a pointer to the allocated space and set *hashmask to a pattern
84 * suitable for masking a value to use as an index into the returned array.
85 */
86 void *
hashinit(u_int elements,enum hashtype htype,bool waitok,u_long * hashmask)87 hashinit(u_int elements, enum hashtype htype, bool waitok, u_long *hashmask)
88 {
89 LIST_HEAD(, generic) *hashtbl_list;
90 SLIST_HEAD(, generic) *hashtbl_slist;
91 TAILQ_HEAD(, generic) *hashtbl_tailq;
92 struct pslist_head *hashtbl_pslist;
93 u_long hashsize, i;
94 size_t esize;
95 void *p;
96
97 KASSERT(elements > 0);
98
99 #define MAXELEMENTS (1U << ((sizeof(elements) * NBBY) - 1))
100 if (elements > MAXELEMENTS)
101 elements = MAXELEMENTS;
102
103 hashsize = 1UL << (ilog2(elements - 1) + 1);
104 esize = hash_list_size(htype);
105
106 p = kmem_alloc(hashsize * esize, waitok ? KM_SLEEP : KM_NOSLEEP);
107 if (p == NULL)
108 return NULL;
109
110 switch (htype) {
111 case HASH_LIST:
112 hashtbl_list = p;
113 for (i = 0; i < hashsize; i++)
114 LIST_INIT(&hashtbl_list[i]);
115 break;
116 case HASH_PSLIST:
117 hashtbl_pslist = p;
118 for (i = 0; i < hashsize; i++)
119 PSLIST_INIT(&hashtbl_pslist[i]);
120 break;
121 case HASH_SLIST:
122 hashtbl_slist = p;
123 for (i = 0; i < hashsize; i++)
124 SLIST_INIT(&hashtbl_slist[i]);
125 break;
126 case HASH_TAILQ:
127 hashtbl_tailq = p;
128 for (i = 0; i < hashsize; i++)
129 TAILQ_INIT(&hashtbl_tailq[i]);
130 break;
131 }
132 *hashmask = hashsize - 1;
133 return p;
134 }
135
136 /*
137 * Free memory from hash table previosly allocated via hashinit().
138 */
139 void
hashdone(void * hashtbl,enum hashtype htype,u_long hashmask)140 hashdone(void *hashtbl, enum hashtype htype, u_long hashmask)
141 {
142 const size_t esize = hash_list_size(htype);
143 kmem_free(hashtbl, esize * (hashmask + 1));
144 }
145
146 /*
147 * Support for hash statistics (vmstat -H / vmstat -h hashname).
148 */
149
150 struct hashstat {
151 const char *hs_name;
152 hashstat_func_t hs_func;
153 TAILQ_ENTRY(hashstat) hs_next;
154 };
155 TAILQ_HEAD(, hashstat) hashstat_list =
156 TAILQ_HEAD_INITIALIZER(hashstat_list);
157 static krwlock_t hashstat_lock;
158
159 void
hashstat_register(const char * name,hashstat_func_t func)160 hashstat_register(const char *name, hashstat_func_t func)
161 {
162 struct hashstat *hs;
163
164 hs = kmem_alloc(sizeof(*hs), KM_SLEEP);
165
166 hs->hs_name = name;
167 hs->hs_func = func;
168
169 rw_enter(&hashstat_lock, RW_WRITER);
170 TAILQ_INSERT_TAIL(&hashstat_list, hs, hs_next);
171 rw_exit(&hashstat_lock);
172 }
173
174 /*
175 * sysctl support for returning kernel hash statistics.
176 *
177 * We (ab)use CTL_DESCRIBE and CTL_QUERY:
178 * When passed an OID of CTL_DESCRIBE, return a list and description
179 * of the available hashes.
180 * When passed an OID of CTL_QUERY, use the hash name passed in the
181 * "new" hash input as the name of a single hash to return stats on.
182 */
183 static int
hashstat_sysctl(SYSCTLFN_ARGS)184 hashstat_sysctl(SYSCTLFN_ARGS)
185 {
186 struct hashstat_sysctl hs;
187 struct hashstat *hash;
188 char queryname[SYSCTL_NAMELEN];
189 size_t written;
190 bool fill, query;
191 int error;
192
193 if (oldp == NULL) {
194 *oldlenp = 0;
195 TAILQ_FOREACH(hash, &hashstat_list, hs_next)
196 *oldlenp += sizeof(hs);
197 return 0;
198 }
199
200 error = 0;
201 written = 0;
202
203 if (namelen > 0 && name[0] == CTL_DESCRIBE)
204 fill = false;
205 else
206 fill = true;
207
208 if (namelen > 0 && name[0] == CTL_QUERY) {
209 const struct hashstat_sysctl *h = newp;
210 size_t s;
211
212 if (h == NULL) {
213 /* Can't QUERY one hash without supplying the hash name. */
214 return EINVAL;
215 }
216 query = true;
217 error = sysctl_copyinstr(l, h->hash_name, queryname,
218 sizeof(queryname), &s);
219 if (error)
220 return error;
221 } else {
222 query = false;
223 }
224
225 sysctl_unlock();
226 rw_enter(&hashstat_lock, RW_READER);
227 TAILQ_FOREACH(hash, &hashstat_list, hs_next) {
228 if (query && (strcmp(hash->hs_name, queryname) != 0)) {
229 continue;
230 }
231
232 memset(&hs, 0, sizeof(hs));
233 error = hash->hs_func(&hs, fill);
234 if (error)
235 break;
236
237 error = sysctl_copyout(l, &hs, oldp, sizeof(hs));
238 if (error)
239 break;
240 written += sizeof(hs);
241 oldp = (char *)oldp + sizeof(hs);
242 }
243 rw_exit(&hashstat_lock);
244 sysctl_relock();
245
246 if (query && written == 0) /* query not found? */
247 error = ENOENT;
248
249 *oldlenp = written;
250 return error;
251 }
252
253
254 SYSCTL_SETUP(sysctl_hash_setup, "sysctl hash stats setup")
255 {
256
257 rw_init(&hashstat_lock); /* as good a place as any for this */
258
259 sysctl_createv(NULL, 0, NULL, NULL,
260 CTLFLAG_PERMANENT|CTLFLAG_READWRITE,
261 CTLTYPE_STRUCT,
262 "hashstat", SYSCTL_DESCR("kernel hash statistics"),
263 hashstat_sysctl, 0, NULL, 0,
264 CTL_KERN, CTL_CREATE, CTL_EOL);
265 }
266