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