subr_hash.c revision 52635
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 * $FreeBSD: head/sys/kern/kern_subr.c 52635 1999-10-29 18:09:36Z phk $ 40 */ 41 42#include <sys/param.h> 43#include <sys/systm.h> 44#include <sys/kernel.h> 45#include <sys/proc.h> 46#include <sys/malloc.h> 47#include <sys/lock.h> 48#include <sys/resourcevar.h> 49#include <sys/vnode.h> 50 51#include <vm/vm.h> 52#include <vm/vm_page.h> 53#include <vm/vm_map.h> 54 55static void uio_yield __P((void)); 56 57int 58uiomove(cp, n, uio) 59 register caddr_t cp; 60 register int n; 61 register struct uio *uio; 62{ 63 register struct iovec *iov; 64 u_int cnt; 65 int error = 0; 66 int save = 0; 67 68 KASSERT(uio->uio_rw == UIO_READ || uio->uio_rw == UIO_WRITE, 69 ("uiomove: mode")); 70 KASSERT(uio->uio_segflg != UIO_USERSPACE || uio->uio_procp == curproc, 71 ("uiomove proc")); 72 73 if (curproc) { 74 save = curproc->p_flag & P_DEADLKTREAT; 75 curproc->p_flag |= P_DEADLKTREAT; 76 } 77 78 while (n > 0 && uio->uio_resid) { 79 iov = uio->uio_iov; 80 cnt = iov->iov_len; 81 if (cnt == 0) { 82 uio->uio_iov++; 83 uio->uio_iovcnt--; 84 continue; 85 } 86 if (cnt > n) 87 cnt = n; 88 89 switch (uio->uio_segflg) { 90 91 case UIO_USERSPACE: 92 case UIO_USERISPACE: 93 if (ticks - switchticks >= hogticks) 94 uio_yield(); 95 if (uio->uio_rw == UIO_READ) 96 error = copyout(cp, iov->iov_base, cnt); 97 else 98 error = copyin(iov->iov_base, cp, cnt); 99 if (error) 100 break; 101 break; 102 103 case UIO_SYSSPACE: 104 if (uio->uio_rw == UIO_READ) 105 bcopy((caddr_t)cp, iov->iov_base, cnt); 106 else 107 bcopy(iov->iov_base, (caddr_t)cp, cnt); 108 break; 109 case UIO_NOCOPY: 110 break; 111 } 112 iov->iov_base += cnt; 113 iov->iov_len -= cnt; 114 uio->uio_resid -= cnt; 115 uio->uio_offset += cnt; 116 cp += cnt; 117 n -= cnt; 118 } 119 if (curproc) 120 curproc->p_flag = (curproc->p_flag & ~P_DEADLKTREAT) | save; 121 return (error); 122} 123 124int 125uiomoveco(cp, n, uio, obj) 126 caddr_t cp; 127 int n; 128 struct uio *uio; 129 struct vm_object *obj; 130{ 131 struct iovec *iov; 132 u_int cnt; 133 int error; 134 135 KASSERT(uio->uio_rw == UIO_READ || uio->uio_rw == UIO_WRITE, 136 ("uiomoveco: mode")); 137 KASSERT(uio->uio_segflg != UIO_USERSPACE || uio->uio_procp == curproc, 138 ("uiomoveco proc")); 139 140 while (n > 0 && uio->uio_resid) { 141 iov = uio->uio_iov; 142 cnt = iov->iov_len; 143 if (cnt == 0) { 144 uio->uio_iov++; 145 uio->uio_iovcnt--; 146 continue; 147 } 148 if (cnt > n) 149 cnt = n; 150 151 switch (uio->uio_segflg) { 152 153 case UIO_USERSPACE: 154 case UIO_USERISPACE: 155 if (ticks - switchticks >= hogticks) 156 uio_yield(); 157 if (uio->uio_rw == UIO_READ) { 158#ifdef ENABLE_VFS_IOOPT 159 if (vfs_ioopt && ((cnt & PAGE_MASK) == 0) && 160 ((((intptr_t) iov->iov_base) & PAGE_MASK) == 0) && 161 ((uio->uio_offset & PAGE_MASK) == 0) && 162 ((((intptr_t) cp) & PAGE_MASK) == 0)) { 163 error = vm_uiomove(&curproc->p_vmspace->vm_map, obj, 164 uio->uio_offset, cnt, 165 (vm_offset_t) iov->iov_base, NULL); 166 } else 167#endif 168 { 169 error = copyout(cp, iov->iov_base, cnt); 170 } 171 } else { 172 error = copyin(iov->iov_base, cp, cnt); 173 } 174 if (error) 175 return (error); 176 break; 177 178 case UIO_SYSSPACE: 179 if (uio->uio_rw == UIO_READ) 180 bcopy((caddr_t)cp, iov->iov_base, cnt); 181 else 182 bcopy(iov->iov_base, (caddr_t)cp, cnt); 183 break; 184 case UIO_NOCOPY: 185 break; 186 } 187 iov->iov_base += cnt; 188 iov->iov_len -= cnt; 189 uio->uio_resid -= cnt; 190 uio->uio_offset += cnt; 191 cp += cnt; 192 n -= cnt; 193 } 194 return (0); 195} 196 197#ifdef ENABLE_VFS_IOOPT 198 199int 200uioread(n, uio, obj, nread) 201 int n; 202 struct uio *uio; 203 struct vm_object *obj; 204 int *nread; 205{ 206 int npagesmoved; 207 struct iovec *iov; 208 u_int cnt, tcnt; 209 int error; 210 211 *nread = 0; 212 if (vfs_ioopt < 2) 213 return 0; 214 215 error = 0; 216 217 while (n > 0 && uio->uio_resid) { 218 iov = uio->uio_iov; 219 cnt = iov->iov_len; 220 if (cnt == 0) { 221 uio->uio_iov++; 222 uio->uio_iovcnt--; 223 continue; 224 } 225 if (cnt > n) 226 cnt = n; 227 228 if ((uio->uio_segflg == UIO_USERSPACE) && 229 ((((intptr_t) iov->iov_base) & PAGE_MASK) == 0) && 230 ((uio->uio_offset & PAGE_MASK) == 0) ) { 231 232 if (cnt < PAGE_SIZE) 233 break; 234 235 cnt &= ~PAGE_MASK; 236 237 if (ticks - switchticks >= hogticks) 238 uio_yield(); 239 error = vm_uiomove(&curproc->p_vmspace->vm_map, obj, 240 uio->uio_offset, cnt, 241 (vm_offset_t) iov->iov_base, &npagesmoved); 242 243 if (npagesmoved == 0) 244 break; 245 246 tcnt = npagesmoved * PAGE_SIZE; 247 cnt = tcnt; 248 249 if (error) 250 break; 251 252 iov->iov_base += cnt; 253 iov->iov_len -= cnt; 254 uio->uio_resid -= cnt; 255 uio->uio_offset += cnt; 256 *nread += cnt; 257 n -= cnt; 258 } else { 259 break; 260 } 261 } 262 return error; 263} 264 265#endif 266 267/* 268 * Give next character to user as result of read. 269 */ 270int 271ureadc(c, uio) 272 register int c; 273 register struct uio *uio; 274{ 275 register struct iovec *iov; 276 277again: 278 if (uio->uio_iovcnt == 0 || uio->uio_resid == 0) 279 panic("ureadc"); 280 iov = uio->uio_iov; 281 if (iov->iov_len == 0) { 282 uio->uio_iovcnt--; 283 uio->uio_iov++; 284 goto again; 285 } 286 switch (uio->uio_segflg) { 287 288 case UIO_USERSPACE: 289 if (subyte(iov->iov_base, c) < 0) 290 return (EFAULT); 291 break; 292 293 case UIO_SYSSPACE: 294 *iov->iov_base = c; 295 break; 296 297 case UIO_USERISPACE: 298 if (suibyte(iov->iov_base, c) < 0) 299 return (EFAULT); 300 break; 301 case UIO_NOCOPY: 302 break; 303 } 304 iov->iov_base++; 305 iov->iov_len--; 306 uio->uio_resid--; 307 uio->uio_offset++; 308 return (0); 309} 310 311#ifdef vax /* unused except by ct.c, other oddities XXX */ 312/* 313 * Get next character written in by user from uio. 314 */ 315int 316uwritec(uio) 317 struct uio *uio; 318{ 319 register struct iovec *iov; 320 register int c; 321 322 if (uio->uio_resid <= 0) 323 return (-1); 324again: 325 if (uio->uio_iovcnt <= 0) 326 panic("uwritec"); 327 iov = uio->uio_iov; 328 if (iov->iov_len == 0) { 329 uio->uio_iov++; 330 if (--uio->uio_iovcnt == 0) 331 return (-1); 332 goto again; 333 } 334 switch (uio->uio_segflg) { 335 336 case UIO_USERSPACE: 337 c = fubyte(iov->iov_base); 338 break; 339 340 case UIO_SYSSPACE: 341 c = *(u_char *) iov->iov_base; 342 break; 343 344 case UIO_USERISPACE: 345 c = fuibyte(iov->iov_base); 346 break; 347 } 348 if (c < 0) 349 return (-1); 350 iov->iov_base++; 351 iov->iov_len--; 352 uio->uio_resid--; 353 uio->uio_offset++; 354 return (c); 355} 356#endif /* vax */ 357 358/* 359 * General routine to allocate a hash table. 360 */ 361void * 362hashinit(elements, type, hashmask) 363 int elements; 364 struct malloc_type *type; 365 u_long *hashmask; 366{ 367 long hashsize; 368 LIST_HEAD(generic, generic) *hashtbl; 369 int i; 370 371 if (elements <= 0) 372 panic("hashinit: bad elements"); 373 for (hashsize = 1; hashsize <= elements; hashsize <<= 1) 374 continue; 375 hashsize >>= 1; 376 hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK); 377 for (i = 0; i < hashsize; i++) 378 LIST_INIT(&hashtbl[i]); 379 *hashmask = hashsize - 1; 380 return (hashtbl); 381} 382 383static int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 1531, 2039, 384 2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143, 6653, 385 7159, 7673, 8191, 12281, 16381, 24571, 32749 }; 386#define NPRIMES (sizeof(primes) / sizeof(primes[0])) 387 388/* 389 * General routine to allocate a prime number sized hash table. 390 */ 391void * 392phashinit(elements, type, nentries) 393 int elements; 394 struct malloc_type *type; 395 u_long *nentries; 396{ 397 long hashsize; 398 LIST_HEAD(generic, generic) *hashtbl; 399 int i; 400 401 if (elements <= 0) 402 panic("phashinit: bad elements"); 403 for (i = 1, hashsize = primes[1]; hashsize <= elements;) { 404 i++; 405 if (i == NPRIMES) 406 break; 407 hashsize = primes[i]; 408 } 409 hashsize = primes[i - 1]; 410 hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK); 411 for (i = 0; i < hashsize; i++) 412 LIST_INIT(&hashtbl[i]); 413 *nentries = hashsize; 414 return (hashtbl); 415} 416 417static void 418uio_yield() 419{ 420 struct proc *p; 421 int s; 422 423 p = curproc; 424 p->p_priority = p->p_usrpri; 425 s = splhigh(); 426 setrunqueue(p); 427 p->p_stats->p_ru.ru_nivcsw++; 428 mi_switch(); 429 splx(s); 430} 431