subr_hash.c revision 31853
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.13 1997/10/10 18:14:23 phk Exp $ 40 */ 41 42#include <sys/param.h> 43#include <sys/systm.h> 44#include <sys/proc.h> 45#include <sys/malloc.h> 46#include <sys/lock.h> 47 48#include <vm/vm.h> 49#include <vm/vm_prot.h> 50#include <vm/vm_page.h> 51#include <vm/vm_map.h> 52 53int 54uiomove(cp, n, uio) 55 register caddr_t cp; 56 register int n; 57 register struct uio *uio; 58{ 59 register struct iovec *iov; 60 u_int cnt; 61 int error; 62 63#ifdef DIAGNOSTIC 64 if (uio->uio_rw != UIO_READ && uio->uio_rw != UIO_WRITE) 65 panic("uiomove: mode"); 66 if (uio->uio_segflg == UIO_USERSPACE && uio->uio_procp != curproc) 67 panic("uiomove proc"); 68#endif 69 while (n > 0 && uio->uio_resid) { 70 iov = uio->uio_iov; 71 cnt = iov->iov_len; 72 if (cnt == 0) { 73 uio->uio_iov++; 74 uio->uio_iovcnt--; 75 continue; 76 } 77 if (cnt > n) 78 cnt = n; 79 80 switch (uio->uio_segflg) { 81 82 case UIO_USERSPACE: 83 case UIO_USERISPACE: 84 if (uio->uio_rw == UIO_READ) 85 error = copyout(cp, iov->iov_base, cnt); 86 else 87 error = copyin(iov->iov_base, cp, cnt); 88 if (error) 89 return (error); 90 break; 91 92 case UIO_SYSSPACE: 93 if (uio->uio_rw == UIO_READ) 94 bcopy((caddr_t)cp, iov->iov_base, cnt); 95 else 96 bcopy(iov->iov_base, (caddr_t)cp, cnt); 97 break; 98 case UIO_NOCOPY: 99 break; 100 } 101 iov->iov_base += cnt; 102 iov->iov_len -= cnt; 103 uio->uio_resid -= cnt; 104 uio->uio_offset += cnt; 105 cp += cnt; 106 n -= cnt; 107 } 108 return (0); 109} 110 111int 112uiomoveco(cp, n, uio, obj) 113 caddr_t cp; 114 int n; 115 struct uio *uio; 116 struct vm_object *obj; 117{ 118 struct iovec *iov; 119 u_int cnt; 120 int error; 121 122#ifdef DIAGNOSTIC 123 if (uio->uio_rw != UIO_READ && uio->uio_rw != UIO_WRITE) 124 panic("uiomove: mode"); 125 if (uio->uio_segflg == UIO_USERSPACE && uio->uio_procp != curproc) 126 panic("uiomove proc"); 127#endif 128 while (n > 0 && uio->uio_resid) { 129 iov = uio->uio_iov; 130 cnt = iov->iov_len; 131 if (cnt == 0) { 132 uio->uio_iov++; 133 uio->uio_iovcnt--; 134 continue; 135 } 136 if (cnt > n) 137 cnt = n; 138 139 switch (uio->uio_segflg) { 140 141 case UIO_USERSPACE: 142 case UIO_USERISPACE: 143 if (uio->uio_rw == UIO_READ) { 144 if (((cnt & PAGE_MASK) == 0) && 145 ((((int) iov->iov_base) & PAGE_MASK) == 0) && 146 ((uio->uio_offset & PAGE_MASK) == 0) && 147 ((((int) cp) & PAGE_MASK) == 0)) { 148 error = vm_uiomove(&curproc->p_vmspace->vm_map, obj, 149 uio->uio_offset, cnt, 150 (vm_offset_t) iov->iov_base); 151 } else { 152 error = copyout(cp, iov->iov_base, cnt); 153 } 154 } else { 155 error = copyin(iov->iov_base, cp, cnt); 156 } 157 if (error) 158 return (error); 159 break; 160 161 case UIO_SYSSPACE: 162 if (uio->uio_rw == UIO_READ) 163 bcopy((caddr_t)cp, iov->iov_base, cnt); 164 else 165 bcopy(iov->iov_base, (caddr_t)cp, cnt); 166 break; 167 case UIO_NOCOPY: 168 break; 169 } 170 iov->iov_base += cnt; 171 iov->iov_len -= cnt; 172 uio->uio_resid -= cnt; 173 uio->uio_offset += cnt; 174 cp += cnt; 175 n -= cnt; 176 } 177 return (0); 178} 179 180/* 181 * Give next character to user as result of read. 182 */ 183int 184ureadc(c, uio) 185 register int c; 186 register struct uio *uio; 187{ 188 register struct iovec *iov; 189 190again: 191 if (uio->uio_iovcnt == 0 || uio->uio_resid == 0) 192 panic("ureadc"); 193 iov = uio->uio_iov; 194 if (iov->iov_len == 0) { 195 uio->uio_iovcnt--; 196 uio->uio_iov++; 197 goto again; 198 } 199 switch (uio->uio_segflg) { 200 201 case UIO_USERSPACE: 202 if (subyte(iov->iov_base, c) < 0) 203 return (EFAULT); 204 break; 205 206 case UIO_SYSSPACE: 207 *iov->iov_base = c; 208 break; 209 210 case UIO_USERISPACE: 211 if (suibyte(iov->iov_base, c) < 0) 212 return (EFAULT); 213 break; 214 case UIO_NOCOPY: 215 break; 216 } 217 iov->iov_base++; 218 iov->iov_len--; 219 uio->uio_resid--; 220 uio->uio_offset++; 221 return (0); 222} 223 224#ifdef vax /* unused except by ct.c, other oddities XXX */ 225/* 226 * Get next character written in by user from uio. 227 */ 228int 229uwritec(uio) 230 struct uio *uio; 231{ 232 register struct iovec *iov; 233 register int c; 234 235 if (uio->uio_resid <= 0) 236 return (-1); 237again: 238 if (uio->uio_iovcnt <= 0) 239 panic("uwritec"); 240 iov = uio->uio_iov; 241 if (iov->iov_len == 0) { 242 uio->uio_iov++; 243 if (--uio->uio_iovcnt == 0) 244 return (-1); 245 goto again; 246 } 247 switch (uio->uio_segflg) { 248 249 case UIO_USERSPACE: 250 c = fubyte(iov->iov_base); 251 break; 252 253 case UIO_SYSSPACE: 254 c = *(u_char *) iov->iov_base; 255 break; 256 257 case UIO_USERISPACE: 258 c = fuibyte(iov->iov_base); 259 break; 260 } 261 if (c < 0) 262 return (-1); 263 iov->iov_base++; 264 iov->iov_len--; 265 uio->uio_resid--; 266 uio->uio_offset++; 267 return (c); 268} 269#endif /* vax */ 270 271/* 272 * General routine to allocate a hash table. 273 */ 274void * 275hashinit(elements, type, hashmask) 276 int elements; 277 struct malloc_type *type; 278 u_long *hashmask; 279{ 280 long hashsize; 281 LIST_HEAD(generic, generic) *hashtbl; 282 int i; 283 284 if (elements <= 0) 285 panic("hashinit: bad elements"); 286 for (hashsize = 1; hashsize <= elements; hashsize <<= 1) 287 continue; 288 hashsize >>= 1; 289 hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK); 290 for (i = 0; i < hashsize; i++) 291 LIST_INIT(&hashtbl[i]); 292 *hashmask = hashsize - 1; 293 return (hashtbl); 294} 295 296static int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 1531, 2039, 297 2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143, 6653, 298 7159, 7673, 8191, 12281, 16381, 24571, 32749 }; 299#define NPRIMES (sizeof(primes) / sizeof(primes[0])) 300 301/* 302 * General routine to allocate a prime number sized hash table. 303 */ 304void * 305phashinit(elements, type, nentries) 306 int elements; 307 struct malloc_type *type; 308 u_long *nentries; 309{ 310 long hashsize; 311 LIST_HEAD(generic, generic) *hashtbl; 312 int i; 313 314 if (elements <= 0) 315 panic("phashinit: bad elements"); 316 for (i = 1, hashsize = primes[1]; hashsize <= elements;) { 317 i++; 318 if (i == NPRIMES) 319 break; 320 hashsize = primes[i]; 321 } 322 hashsize = primes[i - 1]; 323 hashtbl = malloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK); 324 for (i = 0; i < hashsize; i++) 325 LIST_INIT(&hashtbl[i]); 326 *nentries = hashsize; 327 return (hashtbl); 328} 329