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: src/sys/kern/kern_subr.c,v 1.31.2.2 2002/04/21 08:09:37 bde Exp $ 40 * $DragonFly: src/sys/kern/kern_subr.c,v 1.25 2006/12/23 23:47:54 swildner Exp $ 41 */ 42 43 #include "opt_ddb.h" 44 45 #include <sys/param.h> 46 #include <sys/systm.h> 47 #include <sys/kernel.h> 48 #include <sys/proc.h> 49 #include <sys/malloc.h> 50 #include <sys/lock.h> 51 #include <sys/resourcevar.h> 52 #include <sys/sysctl.h> 53 #include <sys/uio.h> 54 #include <sys/vnode.h> 55 #include <machine/limits.h> 56 57 #include <vm/vm.h> 58 #include <vm/vm_page.h> 59 #include <vm/vm_map.h> 60 61 SYSCTL_INT(_kern, KERN_IOV_MAX, iov_max, CTLFLAG_RD, NULL, UIO_MAXIOV, 62 "Maximum number of elements in an I/O vector; sysconf(_SC_IOV_MAX)"); 63 64 /* 65 * UIO_READ: copy the kernelspace cp to the user or kernelspace UIO 66 * UIO_WRITE: copy the user or kernelspace UIO to the kernelspace cp 67 * 68 * For userspace UIO's, uio_td must be the current thread. 69 */ 70 int 71 uiomove(caddr_t cp, int n, struct uio *uio) 72 { 73 struct iovec *iov; 74 u_int cnt; 75 int error = 0; 76 int save = 0; 77 int baseticks = ticks; 78 79 KASSERT(uio->uio_rw == UIO_READ || uio->uio_rw == UIO_WRITE, 80 ("uiomove: mode")); 81 KASSERT(uio->uio_segflg != UIO_USERSPACE || uio->uio_td == curthread, 82 ("uiomove proc")); 83 84 if (curproc) { 85 save = curproc->p_flag & P_DEADLKTREAT; 86 curproc->p_flag |= P_DEADLKTREAT; 87 } 88 89 while (n > 0 && uio->uio_resid) { 90 iov = uio->uio_iov; 91 cnt = iov->iov_len; 92 if (cnt == 0) { 93 uio->uio_iov++; 94 uio->uio_iovcnt--; 95 continue; 96 } 97 if (cnt > n) 98 cnt = n; 99 100 switch (uio->uio_segflg) { 101 102 case UIO_USERSPACE: 103 if (ticks - baseticks >= hogticks) { 104 uio_yield(); 105 baseticks = ticks; 106 } 107 if (uio->uio_rw == UIO_READ) 108 error = copyout(cp, iov->iov_base, cnt); 109 else 110 error = copyin(iov->iov_base, cp, cnt); 111 if (error) 112 break; 113 break; 114 115 case UIO_SYSSPACE: 116 if (uio->uio_rw == UIO_READ) 117 bcopy((caddr_t)cp, iov->iov_base, cnt); 118 else 119 bcopy(iov->iov_base, (caddr_t)cp, cnt); 120 break; 121 case UIO_NOCOPY: 122 break; 123 } 124 iov->iov_base += cnt; 125 iov->iov_len -= cnt; 126 uio->uio_resid -= cnt; 127 uio->uio_offset += cnt; 128 cp += cnt; 129 n -= cnt; 130 } 131 if (curproc) 132 curproc->p_flag = (curproc->p_flag & ~P_DEADLKTREAT) | save; 133 return (error); 134 } 135 /* 136 * Wrapper for uiomove() that validates the arguments against a known-good 137 * kernel buffer. Currently, uiomove accepts a signed (n) argument, which 138 * is almost definitely a bad thing, so we catch that here as well. We 139 * return a runtime failure, but it might be desirable to generate a runtime 140 * assertion failure instead. 141 */ 142 int 143 uiomove_frombuf(void *buf, int buflen, struct uio *uio) 144 { 145 unsigned int offset, n; 146 147 if (uio->uio_offset < 0 || uio->uio_resid < 0 || 148 (offset = uio->uio_offset) != uio->uio_offset) 149 return (EINVAL); 150 if (buflen <= 0 || offset >= buflen) 151 return (0); 152 if ((n = buflen - offset) > INT_MAX) 153 return (EINVAL); 154 return (uiomove((char *)buf + offset, n, uio)); 155 } 156 157 158 int 159 uiomoveco(caddr_t cp, int n, struct uio *uio, struct vm_object *obj) 160 { 161 struct iovec *iov; 162 u_int cnt; 163 int error; 164 int baseticks = ticks; 165 166 KASSERT(uio->uio_rw == UIO_READ || uio->uio_rw == UIO_WRITE, 167 ("uiomoveco: mode")); 168 KASSERT(uio->uio_segflg != UIO_USERSPACE || uio->uio_td == curthread, 169 ("uiomoveco proc")); 170 171 while (n > 0 && uio->uio_resid) { 172 iov = uio->uio_iov; 173 cnt = iov->iov_len; 174 if (cnt == 0) { 175 uio->uio_iov++; 176 uio->uio_iovcnt--; 177 continue; 178 } 179 if (cnt > n) 180 cnt = n; 181 182 switch (uio->uio_segflg) { 183 184 case UIO_USERSPACE: 185 if (ticks - baseticks >= hogticks) { 186 uio_yield(); 187 baseticks = ticks; 188 } 189 if (uio->uio_rw == UIO_READ) { 190 error = copyout(cp, iov->iov_base, cnt); 191 } else { 192 error = copyin(iov->iov_base, cp, cnt); 193 } 194 if (error) 195 return (error); 196 break; 197 198 case UIO_SYSSPACE: 199 if (uio->uio_rw == UIO_READ) 200 bcopy((caddr_t)cp, iov->iov_base, cnt); 201 else 202 bcopy(iov->iov_base, (caddr_t)cp, cnt); 203 break; 204 case UIO_NOCOPY: 205 break; 206 } 207 iov->iov_base += cnt; 208 iov->iov_len -= cnt; 209 uio->uio_resid -= cnt; 210 uio->uio_offset += cnt; 211 cp += cnt; 212 n -= cnt; 213 } 214 return (0); 215 } 216 217 /* 218 * Give next character to user as result of read. 219 */ 220 int 221 ureadc(int c, struct uio *uio) 222 { 223 struct iovec *iov; 224 225 again: 226 if (uio->uio_iovcnt == 0 || uio->uio_resid == 0) 227 panic("ureadc"); 228 iov = uio->uio_iov; 229 if (iov->iov_len == 0) { 230 uio->uio_iovcnt--; 231 uio->uio_iov++; 232 goto again; 233 } 234 switch (uio->uio_segflg) { 235 236 case UIO_USERSPACE: 237 if (subyte(iov->iov_base, c) < 0) 238 return (EFAULT); 239 break; 240 241 case UIO_SYSSPACE: 242 *iov->iov_base = c; 243 break; 244 245 case UIO_NOCOPY: 246 break; 247 } 248 iov->iov_base++; 249 iov->iov_len--; 250 uio->uio_resid--; 251 uio->uio_offset++; 252 return (0); 253 } 254 255 /* 256 * General routine to allocate a hash table. Make the hash table size a 257 * power of 2 greater or equal to the number of elements requested, and 258 * store the masking value in *hashmask. 259 */ 260 void * 261 hashinit(int elements, struct malloc_type *type, u_long *hashmask) 262 { 263 long hashsize; 264 LIST_HEAD(generic, generic) *hashtbl; 265 int i; 266 267 if (elements <= 0) 268 panic("hashinit: bad elements"); 269 for (hashsize = 2; hashsize < elements; hashsize <<= 1) 270 continue; 271 hashtbl = kmalloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK); 272 for (i = 0; i < hashsize; i++) 273 LIST_INIT(&hashtbl[i]); 274 *hashmask = hashsize - 1; 275 return (hashtbl); 276 } 277 278 static int primes[] = { 1, 13, 31, 61, 127, 251, 509, 761, 1021, 1531, 2039, 279 2557, 3067, 3583, 4093, 4603, 5119, 5623, 6143, 6653, 280 7159, 7673, 8191, 12281, 16381, 24571, 32749 }; 281 #define NPRIMES (sizeof(primes) / sizeof(primes[0])) 282 283 /* 284 * General routine to allocate a prime number sized hash table. 285 */ 286 void * 287 phashinit(int elements, struct malloc_type *type, u_long *nentries) 288 { 289 long hashsize; 290 LIST_HEAD(generic, generic) *hashtbl; 291 int i; 292 293 if (elements <= 0) 294 panic("phashinit: bad elements"); 295 for (i = 1, hashsize = primes[1]; hashsize <= elements;) { 296 i++; 297 if (i == NPRIMES) 298 break; 299 hashsize = primes[i]; 300 } 301 hashsize = primes[i - 1]; 302 hashtbl = kmalloc((u_long)hashsize * sizeof(*hashtbl), type, M_WAITOK); 303 for (i = 0; i < hashsize; i++) 304 LIST_INIT(&hashtbl[i]); 305 *nentries = hashsize; 306 return (hashtbl); 307 } 308 309 /* 310 * Copyin an iovec. If the iovec array fits, use the preallocated small 311 * iovec structure. If it is too big, dynamically allocate an iovec array 312 * of sufficient size. 313 * 314 * MPSAFE 315 */ 316 int 317 iovec_copyin(struct iovec *uiov, struct iovec **kiov, struct iovec *siov, 318 size_t iov_cnt, int *iov_len) 319 { 320 struct iovec *iovp; 321 int error, i; 322 323 if (iov_cnt >= UIO_MAXIOV) 324 return EMSGSIZE; 325 if (iov_cnt >= UIO_SMALLIOV) { 326 MALLOC(*kiov, struct iovec *, sizeof(struct iovec) * iov_cnt, 327 M_IOV, M_WAITOK); 328 } else { 329 *kiov = siov; 330 } 331 error = copyin(uiov, *kiov, iov_cnt * sizeof(struct iovec)); 332 if (error == 0) { 333 *iov_len = 0; 334 for (i = 0, iovp = *kiov; i < iov_cnt; i++, iovp++) { 335 /* 336 * Check for both *iov_len overflows and out of 337 * range iovp->iov_len's. We limit to the 338 * capabilities of signed integers. 339 */ 340 if (*iov_len + (int)iovp->iov_len < *iov_len) 341 error = EINVAL; 342 *iov_len += (int)iovp->iov_len; 343 } 344 } 345 if (error) 346 iovec_free(kiov, siov); 347 return (error); 348 } 349