sys/fs/pseudofs/pseudofs_fileno.c

   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 }