subr_hash.c revision 72200
1191783Srmacklem/* 2191783Srmacklem * Copyright (c) 1982, 1986, 1991, 1993 3191783Srmacklem * The Regents of the University of California. All rights reserved. 4191783Srmacklem * (c) UNIX System Laboratories, Inc. 5191783Srmacklem * All or some portions of this file are derived from material licensed 6191783Srmacklem * to the University of California by American Telephone and Telegraph 7191783Srmacklem * Co. or Unix System Laboratories, Inc. and are reproduced herein with 8191783Srmacklem * the permission of UNIX System Laboratories, Inc. 9191783Srmacklem * 10191783Srmacklem * Redistribution and use in source and binary forms, with or without 11191783Srmacklem * modification, are permitted provided that the following conditions 12191783Srmacklem * are met: 13191783Srmacklem * 1. Redistributions of source code must retain the above copyright 14191783Srmacklem * notice, this list of conditions and the following disclaimer. 15191783Srmacklem * 2. Redistributions in binary form must reproduce the above copyright 16191783Srmacklem * notice, this list of conditions and the following disclaimer in the 17191783Srmacklem * documentation and/or other materials provided with the distribution. 18191783Srmacklem * 3. All advertising materials mentioning features or use of this software 19191783Srmacklem * must display the following acknowledgement: 20191783Srmacklem * This product includes software developed by the University of 21191783Srmacklem * California, Berkeley and its contributors. 22191783Srmacklem * 4. Neither the name of the University nor the names of its contributors 23191783Srmacklem * may be used to endorse or promote products derived from this software 24191783Srmacklem * without specific prior written permission. 25191783Srmacklem * 26191783Srmacklem * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 27191783Srmacklem * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28191783Srmacklem * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29191783Srmacklem * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 30191783Srmacklem * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31191783Srmacklem * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32191783Srmacklem * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33191783Srmacklem * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34191783Srmacklem * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35191783Srmacklem * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36191783Srmacklem * SUCH DAMAGE. 37191783Srmacklem * 38191783Srmacklem * @(#)kern_subr.c 8.3 (Berkeley) 1/21/94 39191783Srmacklem * $FreeBSD: head/sys/kern/kern_subr.c 72200 2001-02-09 06:11:45Z bmilekic $ 40191783Srmacklem */ 41191783Srmacklem 42191783Srmacklem#include <sys/param.h> 43191783Srmacklem#include <sys/systm.h> 44191783Srmacklem#include <sys/kernel.h> 45191783Srmacklem#include <sys/ktr.h> 46191783Srmacklem#include <sys/proc.h> 47191783Srmacklem#include <sys/malloc.h> 48191783Srmacklem#include <sys/mutex.h> 49191783Srmacklem#include <sys/lock.h> 50191783Srmacklem#include <sys/resourcevar.h> 51191783Srmacklem#include <sys/vnode.h> 52191783Srmacklem 53191783Srmacklem#include <vm/vm.h> 54191783Srmacklem#include <vm/vm_page.h> 55191783Srmacklem#include <vm/vm_map.h> 56191783Srmacklem 57191783Srmacklemstatic void uio_yield __P((void)); 58191783Srmacklem 59191783Srmacklemint 60191783Srmacklemuiomove(cp, n, uio) 61191783Srmacklem register caddr_t cp; 62191783Srmacklem register int n; 63191783Srmacklem register struct uio *uio; 64191783Srmacklem{ 65191783Srmacklem register struct iovec *iov; 66191783Srmacklem u_int cnt; 67191783Srmacklem int error = 0; 68191783Srmacklem int save = 0; 69191783Srmacklem 70191783Srmacklem KASSERT(uio->uio_rw == UIO_READ || uio->uio_rw == UIO_WRITE, 71191783Srmacklem ("uiomove: mode")); 72191783Srmacklem KASSERT(uio->uio_segflg != UIO_USERSPACE || uio->uio_procp == curproc, 73191783Srmacklem ("uiomove proc")); 74191783Srmacklem 75191783Srmacklem if (curproc) { 76191783Srmacklem save = curproc->p_flag & P_DEADLKTREAT; 77191783Srmacklem curproc->p_flag |= P_DEADLKTREAT; 78191783Srmacklem } 79191783Srmacklem 80191783Srmacklem while (n > 0 && uio->uio_resid) { 81191783Srmacklem iov = uio->uio_iov; 82191783Srmacklem cnt = iov->iov_len; 83191783Srmacklem if (cnt == 0) { 84191783Srmacklem uio->uio_iov++; 85191783Srmacklem uio->uio_iovcnt--; 86191783Srmacklem continue; 87192115Srmacklem } 88191783Srmacklem if (cnt > n) 89191783Srmacklem cnt = n; 90191783Srmacklem 91191783Srmacklem switch (uio->uio_segflg) { 92191783Srmacklem 93191783Srmacklem case UIO_USERSPACE: 94191783Srmacklem case UIO_USERISPACE: 95191783Srmacklem if (ticks - PCPU_GET(switchticks) >= hogticks) 96191783Srmacklem uio_yield(); 97191783Srmacklem if (uio->uio_rw == UIO_READ) 98191783Srmacklem error = copyout(cp, iov->iov_base, cnt); 99191783Srmacklem else 100191783Srmacklem error = copyin(iov->iov_base, cp, cnt); 101191783Srmacklem if (error) 102191783Srmacklem break; 103191783Srmacklem break; 104191783Srmacklem 105191783Srmacklem case UIO_SYSSPACE: 106191783Srmacklem if (uio->uio_rw == UIO_READ) 107191783Srmacklem bcopy((caddr_t)cp, iov->iov_base, cnt); 108191783Srmacklem else 109191783Srmacklem bcopy(iov->iov_base, (caddr_t)cp, cnt); 110191783Srmacklem break; 111191783Srmacklem case UIO_NOCOPY: 112191783Srmacklem break; 113191783Srmacklem } 114191783Srmacklem iov->iov_base += cnt; 115191783Srmacklem iov->iov_len -= cnt; 116191783Srmacklem uio->uio_resid -= cnt; 117191783Srmacklem uio->uio_offset += cnt; 118191783Srmacklem cp += cnt; 119191783Srmacklem n -= cnt; 120191783Srmacklem } 121191783Srmacklem if (curproc) 122191783Srmacklem curproc->p_flag = (curproc->p_flag & ~P_DEADLKTREAT) | save; 123191783Srmacklem return (error); 124191783Srmacklem} 125191783Srmacklem 126220530Srmacklemint 127191783Srmacklemuiomoveco(cp, n, uio, obj) 128192115Srmacklem caddr_t cp; 129191783Srmacklem int n; 130191783Srmacklem struct uio *uio; 131191783Srmacklem struct vm_object *obj; 132191783Srmacklem{ 133191783Srmacklem struct iovec *iov; 134191783Srmacklem u_int cnt; 135191783Srmacklem int error; 136191783Srmacklem 137191783Srmacklem KASSERT(uio->uio_rw == UIO_READ || uio->uio_rw == UIO_WRITE, 138191783Srmacklem ("uiomoveco: mode")); 139191783Srmacklem KASSERT(uio->uio_segflg != UIO_USERSPACE || uio->uio_procp == curproc, 140191783Srmacklem ("uiomoveco proc")); 141191783Srmacklem 142191783Srmacklem while (n > 0 && uio->uio_resid) { 143191783Srmacklem iov = uio->uio_iov; 144191783Srmacklem cnt = iov->iov_len; 145191783Srmacklem if (cnt == 0) { 146191783Srmacklem uio->uio_iov++; 147191783Srmacklem uio->uio_iovcnt--; 148191783Srmacklem continue; 149191783Srmacklem } 150191783Srmacklem if (cnt > n) 151191783Srmacklem cnt = n; 152191783Srmacklem 153191783Srmacklem switch (uio->uio_segflg) { 154191783Srmacklem 155191783Srmacklem case UIO_USERSPACE: 156191783Srmacklem case UIO_USERISPACE: 157191783Srmacklem if (ticks - PCPU_GET(switchticks) >= hogticks) 158191783Srmacklem uio_yield(); 159191783Srmacklem if (uio->uio_rw == UIO_READ) { 160191783Srmacklem#ifdef ENABLE_VFS_IOOPT 161191783Srmacklem if (vfs_ioopt && ((cnt & PAGE_MASK) == 0) && 162191783Srmacklem ((((intptr_t) iov->iov_base) & PAGE_MASK) == 0) && 163191783Srmacklem ((uio->uio_offset & PAGE_MASK) == 0) && 164191783Srmacklem ((((intptr_t) cp) & PAGE_MASK) == 0)) { 165191783Srmacklem error = vm_uiomove(&curproc->p_vmspace->vm_map, obj, 166191783Srmacklem uio->uio_offset, cnt, 167191783Srmacklem (vm_offset_t) iov->iov_base, NULL); 168191783Srmacklem } else 169191783Srmacklem#endif 170191783Srmacklem { 171191783Srmacklem error = copyout(cp, iov->iov_base, cnt); 172191783Srmacklem } 173191783Srmacklem } else { 174191783Srmacklem error = copyin(iov->iov_base, cp, cnt); 175191783Srmacklem } 176191783Srmacklem if (error) 177191783Srmacklem return (error); 178191783Srmacklem break; 179191783Srmacklem 180191783Srmacklem case UIO_SYSSPACE: 181191783Srmacklem if (uio->uio_rw == UIO_READ) 182191783Srmacklem bcopy((caddr_t)cp, iov->iov_base, cnt); 183191783Srmacklem else 184191783Srmacklem bcopy(iov->iov_base, (caddr_t)cp, cnt); 185191783Srmacklem break; 186191783Srmacklem case UIO_NOCOPY: 187191783Srmacklem break; 188191783Srmacklem } 189191783Srmacklem iov->iov_base += cnt; 190191783Srmacklem iov->iov_len -= cnt; 191191783Srmacklem uio->uio_resid -= cnt; 192191783Srmacklem uio->uio_offset += cnt; 193191783Srmacklem cp += cnt; 194191783Srmacklem n -= cnt; 195191783Srmacklem } 196191783Srmacklem return (0); 197191783Srmacklem} 198191783Srmacklem 199191783Srmacklem#ifdef ENABLE_VFS_IOOPT 200191783Srmacklem 201191783Srmacklemint 202191783Srmacklemuioread(n, uio, obj, nread) 203191783Srmacklem int n; 204191783Srmacklem struct uio *uio; 205191783Srmacklem struct vm_object *obj; 206191783Srmacklem int *nread; 207191783Srmacklem{ 208191783Srmacklem int npagesmoved; 209191783Srmacklem struct iovec *iov; 210191783Srmacklem u_int cnt, tcnt; 211191783Srmacklem int error; 212192115Srmacklem 213191783Srmacklem *nread = 0; 214191783Srmacklem if (vfs_ioopt < 2) 215191783Srmacklem return 0; 216192115Srmacklem 217191783Srmacklem error = 0; 218191783Srmacklem 219191783Srmacklem while (n > 0 && uio->uio_resid) { 220191783Srmacklem iov = uio->uio_iov; 221191783Srmacklem cnt = iov->iov_len; 222191783Srmacklem if (cnt == 0) { 223191783Srmacklem uio->uio_iov++; 224191783Srmacklem uio->uio_iovcnt--; 225191783Srmacklem continue; 226191783Srmacklem } 227192115Srmacklem if (cnt > n) 228191783Srmacklem cnt = n; 229191783Srmacklem 230191783Srmacklem if ((uio->uio_segflg == UIO_USERSPACE) && 231191783Srmacklem ((((intptr_t) iov->iov_base) & PAGE_MASK) == 0) && 232191783Srmacklem ((uio->uio_offset & PAGE_MASK) == 0) ) { 233191783Srmacklem 234191783Srmacklem if (cnt < PAGE_SIZE) 235191783Srmacklem break; 236191783Srmacklem 237191783Srmacklem cnt &= ~PAGE_MASK; 238191783Srmacklem 239191783Srmacklem if (ticks - PCPU_GET(switchticks) >= hogticks) 240191783Srmacklem uio_yield(); 241191783Srmacklem error = vm_uiomove(&curproc->p_vmspace->vm_map, obj, 242191783Srmacklem uio->uio_offset, cnt, 243191783Srmacklem (vm_offset_t) iov->iov_base, &npagesmoved); 244191783Srmacklem 245191783Srmacklem if (npagesmoved == 0) 246191783Srmacklem break; 247191783Srmacklem 248191783Srmacklem tcnt = npagesmoved * PAGE_SIZE; 249191783Srmacklem cnt = tcnt; 250191783Srmacklem 251191783Srmacklem if (error) 252191783Srmacklem break; 253191783Srmacklem 254211951Srmacklem iov->iov_base += cnt; 255205941Srmacklem iov->iov_len -= cnt; 256191783Srmacklem uio->uio_resid -= cnt; 257191783Srmacklem uio->uio_offset += cnt; 258192115Srmacklem *nread += cnt; 259192115Srmacklem n -= cnt; 260191783Srmacklem } else { 261192115Srmacklem break; 262191783Srmacklem } 263191783Srmacklem } 264191783Srmacklem return error; 265191783Srmacklem} 266191783Srmacklem 267191783Srmacklem#endif 268191783Srmacklem 269191783Srmacklem/* 270191783Srmacklem * Give next character to user as result of read. 271191783Srmacklem */ 272191783Srmacklemint 273191783Srmacklemureadc(c, uio) 274191783Srmacklem register int c; 275191783Srmacklem register struct uio *uio; 276191783Srmacklem{ 277191783Srmacklem register struct iovec *iov; 278191783Srmacklem 279191783Srmacklemagain: 280191783Srmacklem if (uio->uio_iovcnt == 0 || uio->uio_resid == 0) 281192115Srmacklem panic("ureadc"); 282216700Srmacklem iov = uio->uio_iov; 283191783Srmacklem if (iov->iov_len == 0) { 284191783Srmacklem uio->uio_iovcnt--; 285191783Srmacklem uio->uio_iov++; 286191783Srmacklem goto again; 287191783Srmacklem } 288191783Srmacklem switch (uio->uio_segflg) { 289191783Srmacklem 290220645Srmacklem case UIO_USERSPACE: 291191783Srmacklem if (subyte(iov->iov_base, c) < 0) 292220648Srmacklem return (EFAULT); 293191783Srmacklem break; 294191783Srmacklem 295191783Srmacklem case UIO_SYSSPACE: 296191783Srmacklem *iov->iov_base = c; 297191783Srmacklem break; 298191783Srmacklem 299191783Srmacklem case UIO_USERISPACE: 300191783Srmacklem if (suibyte(iov->iov_base, c) < 0) 301191783Srmacklem return (EFAULT); 302191783Srmacklem break; 303191783Srmacklem case UIO_NOCOPY: 304191783Srmacklem break; 305191783Srmacklem } 306191783Srmacklem iov->iov_base++; 307191783Srmacklem iov->iov_len--; 308191783Srmacklem uio->uio_resid--; 309191783Srmacklem uio->uio_offset++; 310191783Srmacklem return (0); 311192121Srmacklem} 312191783Srmacklem 313192115Srmacklem/* 314191783Srmacklem * General routine to allocate a hash table. 315192115Srmacklem */ 316191783Srmacklemvoid * 317191783Srmacklemhashinit(elements, type, hashmask) 318191783Srmacklem int elements; 319191783Srmacklem struct malloc_type *type; 320191783Srmacklem u_long *hashmask; 321191783Srmacklem{ 322191783Srmacklem long hashsize; 323191783Srmacklem LIST_HEAD(generic, generic) *hashtbl; 324191783Srmacklem int i; 325191783Srmacklem 326207170Srmacklem if (elements <= 0) 327191783Srmacklem panic("hashinit: bad elements"); 328191783Srmacklem for (hashsize = 1; hashsize <= elements; hashsize <<= 1) 329192115Srmacklem continue; 330220648Srmacklem hashsize >>= 1; 331191783Srmacklem hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK); 332192115Srmacklem for (i = 0; i < hashsize; i++) 333191783Srmacklem LIST_INIT(&hashtbl[i]); 334191783Srmacklem *hashmask = hashsize - 1; 335191783Srmacklem return (hashtbl); 336191783Srmacklem} 337191783Srmacklem 338191783Srmacklemstatic int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 1531, 2039, 339191783Srmacklem 2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143, 6653, 340191783Srmacklem 7159, 7673, 8191, 12281, 16381, 24571, 32749 }; 341192115Srmacklem#define NPRIMES (sizeof(primes) / sizeof(primes[0])) 342191783Srmacklem 343191783Srmacklem/* 344191783Srmacklem * General routine to allocate a prime number sized hash table. 345191783Srmacklem */ 346191783Srmacklemvoid * 347191783Srmacklemphashinit(elements, type, nentries) 348191783Srmacklem int elements; 349191783Srmacklem struct malloc_type *type; 350191783Srmacklem u_long *nentries; 351191783Srmacklem{ 352191783Srmacklem long hashsize; 353192337Srmacklem LIST_HEAD(generic, generic) *hashtbl; 354191783Srmacklem int i; 355191783Srmacklem 356191783Srmacklem if (elements <= 0) 357191783Srmacklem panic("phashinit: bad elements"); 358191783Srmacklem for (i = 1, hashsize = primes[1]; hashsize <= elements;) { 359191783Srmacklem i++; 360191783Srmacklem if (i == NPRIMES) 361191783Srmacklem break; 362191783Srmacklem hashsize = primes[i]; 363191783Srmacklem } 364191783Srmacklem hashsize = primes[i - 1]; 365191783Srmacklem hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK); 366191783Srmacklem for (i = 0; i < hashsize; i++) 367191783Srmacklem LIST_INIT(&hashtbl[i]); 368191783Srmacklem *nentries = hashsize; 369191783Srmacklem return (hashtbl); 370191783Srmacklem} 371191783Srmacklem 372191783Srmacklemstatic void 373222289Srmacklemuio_yield() 374207082Srmacklem{ 375191783Srmacklem struct proc *p; 376191783Srmacklem int s; 377191783Srmacklem 378191783Srmacklem p = curproc; 379191783Srmacklem s = splhigh(); 380191783Srmacklem mtx_lock_spin(&sched_lock); 381191783Srmacklem DROP_GIANT_NOSWITCH(); 382191783Srmacklem p->p_priority = p->p_usrpri; 383191783Srmacklem setrunqueue(p); 384191783Srmacklem p->p_stats->p_ru.ru_nivcsw++; 385191783Srmacklem mi_switch(); 386191783Srmacklem mtx_unlock_spin(&sched_lock); 387191783Srmacklem PICKUP_GIANT(); 388191783Srmacklem splx(s); 389191783Srmacklem} 390191783Srmacklem