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