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