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