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