pseudofs_fileno.c revision 78073 
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 78073 2001-06-11 15:04:48Z des $
29 */
30
31#include <sys/param.h>
32#include <sys/kernel.h>
33#include <sys/systm.h>
34#include <sys/lock.h>
35#include <sys/malloc.h>
36#include <sys/mount.h>
37#include <sys/mutex.h>
38#include <sys/proc.h>
39#include <sys/sbuf.h>
40#include <sys/sysctl.h>
41
42#include <machine/limits.h>
43
44#include <fs/pseudofs/pseudofs.h>
45#include <fs/pseudofs/pseudofs_internal.h>
46
47static MALLOC_DEFINE(M_PFSFILENO, "pfs_fileno", "pseudofs fileno bitmap");
48
49static struct mtx pfs_fileno_mutex;
50
51#define PFS_BITMAP_SIZE	4096
52#define PFS_SLOT_BITS	(int)(sizeof(unsigned int) * CHAR_BIT)
53#define PFS_BITMAP_BITS	(PFS_BITMAP_SIZE * PFS_SLOT_BITS)
54struct pfs_bitmap {
55	u_int32_t		 pb_offset;
56	int			 pb_used;
57	unsigned int		 pb_bitmap[PFS_BITMAP_SIZE];
58	struct pfs_bitmap	*pb_next;
59};
60
61/*
62 * Initialization
63 */
64void
65pfs_fileno_load(void)
66{
67	mtx_init(&pfs_fileno_mutex, "pseudofs_fileno", MTX_DEF);
68}
69
70/*
71 * Teardown
72 */
73void
74pfs_fileno_unload(void)
75{
76	mtx_destroy(&pfs_fileno_mutex);
77}
78
79/*
80 * Initialize fileno bitmap
81 */
82void
83pfs_fileno_init(struct pfs_info *pi)
84{
85	struct pfs_bitmap *pb;
86
87	MALLOC(pb, struct pfs_bitmap *, sizeof *pb,
88	    M_PFSFILENO, M_WAITOK|M_ZERO);
89
90	mtx_lock(&pi->pi_mutex);
91
92	pb->pb_bitmap[0] = 07;
93	pb->pb_used = 3;
94	pi->pi_bitmap = pb;
95	pi->pi_root->pn_fileno = 2;
96
97	mtx_unlock(&pi->pi_mutex);
98}
99
100/*
101 * Tear down fileno bitmap
102 */
103void
104pfs_fileno_uninit(struct pfs_info *pi)
105{
106	struct pfs_bitmap *pb, *npb;
107	int used;
108
109	mtx_lock(&pi->pi_mutex);
110
111	pb = pi->pi_bitmap;
112	pi->pi_bitmap = NULL;
113
114	mtx_unlock(&pi->pi_mutex);
115
116	for (used = 0; pb; pb = npb) {
117		npb = pb->pb_next;
118		used += pb->pb_used;
119		FREE(pb, M_PFSFILENO);
120	}
121#if 0
122	/* we currently don't reclaim filenos */
123	if (used > 2)
124		printf("WARNING: %d file numbers still in use\n", used);
125#endif
126}
127
128/*
129 * Get the next available file number
130 */
131static u_int32_t
132pfs_get_fileno(struct pfs_info *pi)
133{
134	struct pfs_bitmap *pb, *ppb;
135	u_int32_t fileno;
136	unsigned int *p;
137	int i;
138
139	mtx_lock(&pi->pi_mutex);
140
141	/* look for the first page with free bits */
142	for (ppb = NULL, pb = pi->pi_bitmap; pb; ppb = pb, pb = pb->pb_next)
143		if (pb->pb_used != PFS_BITMAP_BITS)
144			break;
145
146	/* out of pages? */
147	if (pb == NULL) {
148		mtx_unlock(&pi->pi_mutex);
149		MALLOC(pb, struct pfs_bitmap *, sizeof *pb,
150		    M_PFSFILENO, M_WAITOK|M_ZERO);
151		mtx_lock(&pi->pi_mutex);
152		/* protect against possible race */
153		while (ppb->pb_next)
154			ppb = ppb->pb_next;
155		pb->pb_offset = ppb->pb_offset + PFS_BITMAP_BITS;
156		ppb->pb_next = pb;
157	}
158
159	/* find the first free slot */
160	for (i = 0; i < PFS_BITMAP_SIZE; ++i)
161		if (pb->pb_bitmap[i] != UINT_MAX)
162			break;
163
164	/* find the first available bit and flip it */
165	fileno = pb->pb_offset + i * PFS_SLOT_BITS;
166	p = &pb->pb_bitmap[i];
167	for (i = 0; i < PFS_SLOT_BITS; ++i, ++fileno)
168		if ((*p & (unsigned int)(1 << i)) == 0)
169			break;
170	KASSERT(i < PFS_SLOT_BITS,
171	    ("slot has free bits, yet doesn't"));
172	*p |= (unsigned int)(1 << i);
173	++pb->pb_used;
174
175	mtx_unlock(&pi->pi_mutex);
176
177	return fileno;
178}
179
180/*
181 * Free a file number
182 */
183static void
184pfs_free_fileno(struct pfs_info *pi, u_int32_t fileno)
185{
186	struct pfs_bitmap *pb;
187	unsigned int *p;
188	int i;
189
190	mtx_lock(&pi->pi_mutex);
191
192	/* find the right page */
193	for (pb = pi->pi_bitmap;
194	     pb && fileno >= PFS_BITMAP_BITS;
195	     pb = pb->pb_next, fileno -= PFS_BITMAP_BITS)
196		/* nothing */ ;
197	KASSERT(pb,
198	    ("fileno isn't in any bitmap"));
199
200	/* find the right bit in the right slot and flip it */
201	p = &pb->pb_bitmap[fileno / PFS_SLOT_BITS];
202	i = fileno % PFS_SLOT_BITS;
203	KASSERT(*p & (unsigned int)(1 << i),
204	    ("fileno is already free"));
205	*p &= ~((unsigned int)(1 << i));
206	--pb->pb_used;
207
208	mtx_unlock(&pi->pi_mutex);
209	printf("pfs_free_fileno(): reclaimed %d\n", fileno);
210}
211
212/*
213 * Allocate a file number
214 */
215void
216pfs_fileno_alloc(struct pfs_info *pi, struct pfs_node *pn)
217{
218	/* make sure our parent has a file number */
219	if (pn->pn_parent && !pn->pn_parent->pn_fileno)
220		pfs_fileno_alloc(pi, pn->pn_parent);
221
222	switch (pn->pn_type) {
223	case pfstype_root:
224	case pfstype_dir:
225	case pfstype_file:
226	case pfstype_symlink:
227	case pfstype_procdir:
228		pn->pn_fileno = pfs_get_fileno(pi);
229		break;
230	case pfstype_this:
231		KASSERT(pn->pn_parent != NULL,
232		    ("pfstype_this node has no parent"));
233		pn->pn_fileno = pn->pn_parent->pn_fileno;
234		break;
235	case pfstype_parent:
236		KASSERT(pn->pn_parent != NULL,
237		    ("pfstype_parent node has no parent"));
238		if (pn->pn_parent == pi->pi_root) {
239			pn->pn_fileno = pn->pn_parent->pn_fileno;
240			break;
241		}
242		KASSERT(pn->pn_parent->pn_parent != NULL,
243		    ("pfstype_parent node has no grandparent"));
244		pn->pn_fileno = pn->pn_parent->pn_parent->pn_fileno;
245		break;
246	case pfstype_none:
247		KASSERT(0,
248		    ("pfs_fileno_alloc() called for pfstype_none node"));
249		break;
250 	}
251
252#if 0
253	printf("pfs_fileno_alloc(): %s: ", pi->pi_name);
254	if (pn->pn_parent) {
255		if (pn->pn_parent->pn_parent) {
256			printf("%s/", pn->pn_parent->pn_parent->pn_name);
257		}
258		printf("%s/", pn->pn_parent->pn_name);
259	}
260	printf("%s -> %d\n", pn->pn_name, pn->pn_fileno);
261#endif
262}
263
264/*
265 * Release a file number
266 */
267void
268pfs_fileno_free(struct pfs_info *pi, struct pfs_node *pn)
269{
270	switch (pn->pn_type) {
271	case pfstype_root:
272	case pfstype_dir:
273	case pfstype_file:
274	case pfstype_symlink:
275	case pfstype_procdir:
276		pfs_free_fileno(pi, pn->pn_fileno);
277		break;
278	case pfstype_this:
279	case pfstype_parent:
280		/* ignore these, as they don't "own" their file number */
281		break;
282	case pfstype_none:
283		KASSERT(0,
284		    ("pfs_fileno_free() called for pfstype_none node"));
285		break;
286	}
287}
288