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