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