subr_hash.c revision 33109
1/* 2 * Copyright (c) 1982, 1986, 1991, 1993 3 * The Regents of the University of California. All rights reserved. 4 * (c) UNIX System Laboratories, Inc. 5 * All or some portions of this file are derived from material licensed 6 * to the University of California by American Telephone and Telegraph 7 * Co. or Unix System Laboratories, Inc. and are reproduced herein with 8 * the permission of UNIX System Laboratories, Inc. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the University of 21 * California, Berkeley and its contributors. 22 * 4. Neither the name of the University nor the names of its contributors 23 * may be used to endorse or promote products derived from this software 24 * without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36 * SUCH DAMAGE. 37 * 38 * @(#)kern_subr.c 8.3 (Berkeley) 1/21/94 39 * $Id: kern_subr.c,v 1.17 1998/02/04 22:32:34 eivind Exp $ 40 */ 41 42#include "opt_diagnostic.h" 43 44#include <sys/param.h> 45#include <sys/systm.h> 46#include <sys/proc.h> 47#include <sys/malloc.h> 48#include <sys/lock.h> 49#include <sys/vnode.h> 50 51#include <vm/vm.h> 52#include <vm/vm_prot.h> 53#include <vm/vm_page.h> 54#include <vm/vm_map.h> 55 56int 57uiomove(cp, n, uio) 58 register caddr_t cp; 59 register int n; 60 register struct uio *uio; 61{ 62 register struct iovec *iov; 63 u_int cnt; 64 int error; 65 66#ifdef DIAGNOSTIC 67 if (uio->uio_rw != UIO_READ && uio->uio_rw != UIO_WRITE) 68 panic("uiomove: mode"); 69 if (uio->uio_segflg == UIO_USERSPACE && uio->uio_procp != curproc) 70 panic("uiomove proc"); 71#endif 72 while (n > 0 && uio->uio_resid) { 73 iov = uio->uio_iov; 74 cnt = iov->iov_len; 75 if (cnt == 0) { 76 uio->uio_iov++; 77 uio->uio_iovcnt--; 78 continue; 79 } 80 if (cnt > n) 81 cnt = n; 82 83 switch (uio->uio_segflg) { 84 85 case UIO_USERSPACE: 86 case UIO_USERISPACE: 87 if (uio->uio_rw == UIO_READ) 88 error = copyout(cp, iov->iov_base, cnt); 89 else 90 error = copyin(iov->iov_base, cp, cnt); 91 if (error) 92 return (error); 93 break; 94 95 case UIO_SYSSPACE: 96 if (uio->uio_rw == UIO_READ) 97 bcopy((caddr_t)cp, iov->iov_base, cnt); 98 else 99 bcopy(iov->iov_base, (caddr_t)cp, cnt); 100 break; 101 case UIO_NOCOPY: 102 break; 103 } 104 iov->iov_base += cnt; 105 iov->iov_len -= cnt; 106 uio->uio_resid -= cnt; 107 uio->uio_offset += cnt; 108 cp += cnt; 109 n -= cnt; 110 } 111 return (0); 112} 113 114int 115uiomoveco(cp, n, uio, obj) 116 caddr_t cp; 117 int n; 118 struct uio *uio; 119 struct vm_object *obj; 120{ 121 struct iovec *iov; 122 u_int cnt; 123 int error; 124 125#ifdef DIAGNOSTIC 126 if (uio->uio_rw != UIO_READ && uio->uio_rw != UIO_WRITE) 127 panic("uiomove: mode"); 128 if (uio->uio_segflg == UIO_USERSPACE && uio->uio_procp != curproc) 129 panic("uiomove proc"); 130#endif 131 while (n > 0 && uio->uio_resid) { 132 iov = uio->uio_iov; 133 cnt = iov->iov_len; 134 if (cnt == 0) { 135 uio->uio_iov++; 136 uio->uio_iovcnt--; 137 continue; 138 } 139 if (cnt > n) 140 cnt = n; 141 142 switch (uio->uio_segflg) { 143 144 case UIO_USERSPACE: 145 case UIO_USERISPACE: 146 if (uio->uio_rw == UIO_READ) { 147 if (vfs_ioopt && ((cnt & PAGE_MASK) == 0) && 148 ((((int) iov->iov_base) & PAGE_MASK) == 0) && 149 ((uio->uio_offset & PAGE_MASK) == 0) && 150 ((((int) cp) & PAGE_MASK) == 0)) { 151 error = vm_uiomove(&curproc->p_vmspace->vm_map, obj, 152 uio->uio_offset, cnt, 153 (vm_offset_t) iov->iov_base, NULL); 154 } else { 155 error = copyout(cp, iov->iov_base, cnt); 156 } 157 } else { 158 error = copyin(iov->iov_base, cp, cnt); 159 } 160 if (error) 161 return (error); 162 break; 163 164 case UIO_SYSSPACE: 165 if (uio->uio_rw == UIO_READ) 166 bcopy((caddr_t)cp, iov->iov_base, cnt); 167 else 168 bcopy(iov->iov_base, (caddr_t)cp, cnt); 169 break; 170 case UIO_NOCOPY: 171 break; 172 } 173 iov->iov_base += cnt; 174 iov->iov_len -= cnt; 175 uio->uio_resid -= cnt; 176 uio->uio_offset += cnt; 177 cp += cnt; 178 n -= cnt; 179 } 180 return (0); 181} 182 183int 184uioread(n, uio, obj, nread) 185 int n; 186 struct uio *uio; 187 struct vm_object *obj; 188 int *nread; 189{ 190 int npagesmoved; 191 struct iovec *iov; 192 u_int cnt, tcnt; 193 int error; 194 195 *nread = 0; 196 if (vfs_ioopt < 2) 197 return 0; 198 199 error = 0; 200 201 while (n > 0 && uio->uio_resid) { 202 iov = uio->uio_iov; 203 cnt = iov->iov_len; 204 if (cnt == 0) { 205 uio->uio_iov++; 206 uio->uio_iovcnt--; 207 continue; 208 } 209 if (cnt > n) 210 cnt = n; 211 212 if ((uio->uio_segflg == UIO_USERSPACE) && 213 ((((int) iov->iov_base) & PAGE_MASK) == 0) && 214 ((uio->uio_offset & PAGE_MASK) == 0) ) { 215 216 if (cnt < PAGE_SIZE) 217 break; 218 219 cnt &= ~PAGE_MASK; 220 221 error = vm_uiomove(&curproc->p_vmspace->vm_map, obj, 222 uio->uio_offset, cnt, 223 (vm_offset_t) iov->iov_base, &npagesmoved); 224 225 if (npagesmoved == 0) 226 break; 227 228 tcnt = npagesmoved * PAGE_SIZE; 229 if (tcnt != cnt) { 230 cnt = tcnt; 231 } 232 233 if (error) 234 break; 235 236 iov->iov_base += cnt; 237 iov->iov_len -= cnt; 238 uio->uio_resid -= cnt; 239 uio->uio_offset += cnt; 240 *nread += cnt; 241 n -= cnt; 242 } else { 243 break; 244 } 245 } 246 return error; 247} 248 249/* 250 * Give next character to user as result of read. 251 */ 252int 253ureadc(c, uio) 254 register int c; 255 register struct uio *uio; 256{ 257 register struct iovec *iov; 258 259again: 260 if (uio->uio_iovcnt == 0 || uio->uio_resid == 0) 261 panic("ureadc"); 262 iov = uio->uio_iov; 263 if (iov->iov_len == 0) { 264 uio->uio_iovcnt--; 265 uio->uio_iov++; 266 goto again; 267 } 268 switch (uio->uio_segflg) { 269 270 case UIO_USERSPACE: 271 if (subyte(iov->iov_base, c) < 0) 272 return (EFAULT); 273 break; 274 275 case UIO_SYSSPACE: 276 *iov->iov_base = c; 277 break; 278 279 case UIO_USERISPACE: 280 if (suibyte(iov->iov_base, c) < 0) 281 return (EFAULT); 282 break; 283 case UIO_NOCOPY: 284 break; 285 } 286 iov->iov_base++; 287 iov->iov_len--; 288 uio->uio_resid--; 289 uio->uio_offset++; 290 return (0); 291} 292 293#ifdef vax /* unused except by ct.c, other oddities XXX */ 294/* 295 * Get next character written in by user from uio. 296 */ 297int 298uwritec(uio) 299 struct uio *uio; 300{ 301 register struct iovec *iov; 302 register int c; 303 304 if (uio->uio_resid <= 0) 305 return (-1); 306again: 307 if (uio->uio_iovcnt <= 0) 308 panic("uwritec"); 309 iov = uio->uio_iov; 310 if (iov->iov_len == 0) { 311 uio->uio_iov++; 312 if (--uio->uio_iovcnt == 0) 313 return (-1); 314 goto again; 315 } 316 switch (uio->uio_segflg) { 317 318 case UIO_USERSPACE: 319 c = fubyte(iov->iov_base); 320 break; 321 322 case UIO_SYSSPACE: 323 c = *(u_char *) iov->iov_base; 324 break; 325 326 case UIO_USERISPACE: 327 c = fuibyte(iov->iov_base); 328 break; 329 } 330 if (c < 0) 331 return (-1); 332 iov->iov_base++; 333 iov->iov_len--; 334 uio->uio_resid--; 335 uio->uio_offset++; 336 return (c); 337} 338#endif /* vax */ 339 340/* 341 * General routine to allocate a hash table. 342 */ 343void * 344hashinit(elements, type, hashmask) 345 int elements; 346 struct malloc_type *type; 347 u_long *hashmask; 348{ 349 long hashsize; 350 LIST_HEAD(generic, generic) *hashtbl; 351 int i; 352 353 if (elements <= 0) 354 panic("hashinit: bad elements"); 355 for (hashsize = 1; hashsize <= elements; hashsize <<= 1) 356 continue; 357 hashsize >>= 1; 358 hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK); 359 for (i = 0; i < hashsize; i++) 360 LIST_INIT(&hashtbl[i]); 361 *hashmask = hashsize - 1; 362 return (hashtbl); 363} 364 365static int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 1531, 2039, 366 2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143, 6653, 367 7159, 7673, 8191, 12281, 16381, 24571, 32749 }; 368#define NPRIMES (sizeof(primes) / sizeof(primes[0])) 369 370/* 371 * General routine to allocate a prime number sized hash table. 372 */ 373void * 374phashinit(elements, type, nentries) 375 int elements; 376 struct malloc_type *type; 377 u_long *nentries; 378{ 379 long hashsize; 380 LIST_HEAD(generic, generic) *hashtbl; 381 int i; 382 383 if (elements <= 0) 384 panic("phashinit: bad elements"); 385 for (i = 1, hashsize = primes[1]; hashsize <= elements;) { 386 i++; 387 if (i == NPRIMES) 388 break; 389 hashsize = primes[i]; 390 } 391 hashsize = primes[i - 1]; 392 hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK); 393 for (i = 0; i < hashsize; i++) 394 LIST_INIT(&hashtbl[i]); 395 *nentries = hashsize; 396 return (hashtbl); 397} 398