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