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/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 47 static MALLOC_DEFINE(M_PFSFILENO, "pfs_fileno", "pseudofs fileno bitmap"); 48 49 static 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) 54 struct 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 */ 64 void 65 pfs_fileno_load(void) 66 { 67 mtx_init(&pfs_fileno_mutex, "pseudofs_fileno", MTX_DEF); 68 } 69 70 /* 71 * Teardown 72 */ 73 void 74 pfs_fileno_unload(void) 75 { 76 mtx_destroy(&pfs_fileno_mutex); 77 } 78 79 /* 80 * Initialize fileno bitmap 81 */ 82 void 83 pfs_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 */ 103 void 104 pfs_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 */ 131 static u_int32_t 132 pfs_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 */ 183 static void 184 pfs_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 */ 215 void 216 pfs_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 */ 267 void 268 pfs_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