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