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