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