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/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 } 284