pseudofs_fileno.c revision 77998 
1/*-
2 * Copyright (c) 2001 Dag-Erling Co�dan Sm�rgrav
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer
10 *    in this position and unchanged.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in the
13 *    documentation and/or other materials provided with the distribution.
14 * 3. The name of the author may not be used to endorse or promote products
15 *    derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 *      $FreeBSD: head/sys/fs/pseudofs/pseudofs_fileno.c 77998 2001-06-10 18:39:21Z des $
29 */
30
31#include <sys/param.h>
32#include <sys/kernel.h>
33#include <sys/systm.h>
34#include <sys/malloc.h>
35#include <sys/mount.h>
36#include <sys/mutex.h>
37#include <sys/proc.h>
38#include <sys/sbuf.h>
39#include <sys/sysctl.h>
40
41#include <machine/limits.h>
42
43#include <fs/pseudofs/pseudofs.h>
44#include <fs/pseudofs/pseudofs_internal.h>
45
46static MALLOC_DEFINE(M_PFSFILENO, "pfs_fileno", "pseudofs fileno bitmap");
47
48static struct mtx pfs_fileno_mutex;
49
50#define PFS_BITMAP_SIZE	4096
51#define PFS_SLOT_BITS	(int)(sizeof(unsigned int) * CHAR_BIT)
52#define PFS_BITMAP_BITS	(PFS_BITMAP_SIZE * PFS_SLOT_BITS)
53struct pfs_bitmap {
54	u_int32_t		 pb_offset;
55	int			 pb_used;
56	unsigned int		 pb_bitmap[PFS_BITMAP_SIZE];
57	struct pfs_bitmap	*pb_next;
58};
59
60/*
61 * Initialization
62 */
63void
64pfs_fileno_load(void)
65{
66	mtx_init(&pfs_fileno_mutex, "pseudofs_fileno", MTX_DEF);
67}
68
69/*
70 * Teardown
71 */
72void
73pfs_fileno_unload(void)
74{
75	mtx_destroy(&pfs_fileno_mutex);
76}
77
78/*
79 * Initialize fileno bitmap
80 */
81void
82pfs_fileno_init(struct pfs_info *pi)
83{
84	struct pfs_bitmap *pb;
85
86	MALLOC(pb, struct pfs_bitmap *, sizeof *pb,
87	    M_PFSFILENO, M_WAITOK|M_ZERO);
88
89	mtx_lock(&pi->pi_mutex);
90
91	pb->pb_bitmap[0] = 07;
92	pb->pb_used = 3;
93	pi->pi_bitmap = pb;
94	pi->pi_root->pn_fileno = 2;
95
96	mtx_unlock(&pi->pi_mutex);
97}
98
99/*
100 * Tear down fileno bitmap
101 */
102void
103pfs_fileno_uninit(struct pfs_info *pi)
104{
105	struct pfs_bitmap *pb, *npb;
106	int used;
107
108	mtx_lock(&pi->pi_mutex);
109
110	pb = pi->pi_bitmap;
111	pi->pi_bitmap = NULL;
112
113	mtx_unlock(&pi->pi_mutex);
114
115	for (used = 0; pb; pb = npb) {
116		npb = pb->pb_next;
117		used += pb->pb_used;
118		FREE(pb, M_PFSFILENO);
119	}
120#if 0
121	/* we currently don't reclaim filenos */
122	if (used > 2)
123		printf("WARNING: %d file numbers still in use\n", used);
124#endif
125}
126
127/*
128 * Get the next available file number
129 */
130static u_int32_t
131pfs_get_fileno(struct pfs_info *pi)
132{
133	struct pfs_bitmap *pb, *ppb;
134	u_int32_t fileno;
135	unsigned int *p;
136	int i;
137
138	mtx_lock(&pi->pi_mutex);
139
140	/* look for the first page with free bits */
141	for (ppb = NULL, pb = pi->pi_bitmap; pb; ppb = pb, pb = pb->pb_next)
142		if (pb->pb_used != PFS_BITMAP_BITS)
143			break;
144
145	/* out of pages? */
146	if (pb == NULL) {
147		mtx_unlock(&pi->pi_mutex);
148		MALLOC(pb, struct pfs_bitmap *, sizeof *pb,
149		    M_PFSFILENO, M_WAITOK|M_ZERO);
150		mtx_lock(&pi->pi_mutex);
151		/* protect against possible race */
152		while (ppb->pb_next)
153			ppb = ppb->pb_next;
154		pb->pb_offset = ppb->pb_offset + PFS_BITMAP_BITS;
155		ppb->pb_next = pb;
156	}
157
158	/* find the first free slot */
159	for (i = 0; i < PFS_BITMAP_SIZE; ++i)
160		if (pb->pb_bitmap[i] != UINT_MAX)
161			break;
162
163	/* find the first available bit and flip it */
164	fileno = pb->pb_offset + i * PFS_SLOT_BITS;
165	p = &pb->pb_bitmap[i];
166	for (i = 0; i < PFS_SLOT_BITS; ++i, ++fileno)
167		if ((*p & (unsigned int)(1 << i)) == 0)
168			break;
169	KASSERT(i < PFS_SLOT_BITS,
170	    ("slot has free bits, yet doesn't"));
171	*p |= (unsigned int)(1 << i);
172	++pb->pb_used;
173
174	mtx_unlock(&pi->pi_mutex);
175
176	return fileno;
177}
178
179/*
180 * Free a file number
181 */
182static void
183pfs_free_fileno(struct pfs_info *pi, u_int32_t fileno)
184{
185	struct pfs_bitmap *pb;
186	unsigned int *p;
187	int i;
188
189	mtx_lock(&pi->pi_mutex);
190
191	/* find the right page */
192	for (pb = pi->pi_bitmap;
193	     pb && fileno >= PFS_BITMAP_BITS;
194	     pb = pb->pb_next, fileno -= PFS_BITMAP_BITS)
195		/* nothing */ ;
196	KASSERT(pb,
197	    ("fileno isn't in any bitmap"));
198
199	/* find the right bit in the right slot and flip it */
200	p = &pb->pb_bitmap[fileno / PFS_SLOT_BITS];
201	i = fileno % PFS_SLOT_BITS;
202	KASSERT(*p & (unsigned int)(1 << i),
203	    ("fileno is already free"));
204	*p &= ~((unsigned int)(1 << i));
205	--pb->pb_used;
206
207	mtx_unlock(&pi->pi_mutex);
208	printf("pfs_free_fileno(): reclaimed %d\n", fileno);
209}
210
211/*
212 * Allocate a file number
213 */
214void
215pfs_fileno_alloc(struct pfs_info *pi, struct pfs_node *pn)
216{
217	/* make sure our parent has a file number */
218	if (pn->pn_parent && !pn->pn_parent->pn_fileno)
219		pfs_fileno_alloc(pi, pn->pn_parent);
220
221	switch (pn->pn_type) {
222	case pfstype_root:
223	case pfstype_dir:
224	case pfstype_file:
225	case pfstype_symlink:
226	case pfstype_procdir:
227		pn->pn_fileno = pfs_get_fileno(pi);
228		break;
229	case pfstype_this:
230		KASSERT(pn->pn_parent != NULL,
231		    ("pfstype_this node has no parent"));
232		pn->pn_fileno = pn->pn_parent->pn_fileno;
233		break;
234	case pfstype_parent:
235		KASSERT(pn->pn_parent != NULL,
236		    ("pfstype_parent node has no parent"));
237		if (pn->pn_parent == pi->pi_root) {
238			pn->pn_fileno = pn->pn_parent->pn_fileno;
239			break;
240		}
241		KASSERT(pn->pn_parent->pn_parent != NULL,
242		    ("pfstype_parent node has no grandparent"));
243		pn->pn_fileno = pn->pn_parent->pn_parent->pn_fileno;
244		break;
245	case pfstype_none:
246		KASSERT(0,
247		    ("pfs_fileno_alloc() called for pfstype_none node"));
248		break;
249 	}
250
251#if 0
252	printf("pfs_fileno_alloc(): %s: ", pi->pi_name);
253	if (pn->pn_parent) {
254		if (pn->pn_parent->pn_parent) {
255			printf("%s/", pn->pn_parent->pn_parent->pn_name);
256		}
257		printf("%s/", pn->pn_parent->pn_name);
258	}
259	printf("%s -> %d\n", pn->pn_name, pn->pn_fileno);
260#endif
261}
262
263/*
264 * Release a file number
265 */
266void
267pfs_fileno_free(struct pfs_info *pi, struct pfs_node *pn)
268{
269	switch (pn->pn_type) {
270	case pfstype_root:
271	case pfstype_dir:
272	case pfstype_file:
273	case pfstype_symlink:
274	case pfstype_procdir:
275		pfs_free_fileno(pi, pn->pn_fileno);
276		break;
277	case pfstype_this:
278	case pfstype_parent:
279		/* ignore these, as they don't "own" their file number */
280		break;
281	case pfstype_none:
282		KASSERT(0,
283		    ("pfs_fileno_free() called for pfstype_none node"));
284		break;
285	}
286}
287