sys/vfs/devfs/devfs_helper.c

   1 /*
   2  * Copyright (c) 2009-2019 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Alex Hornung <ahornung@gmail.com>
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  * 3. Neither the name of The DragonFly Project nor the names of its
  18  *    contributors may be used to endorse or promote products derived
  19  *    from this software without specific, prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34 #include <sys/param.h>
  35 #include <sys/systm.h>
  36 #include <sys/kernel.h>
  37 #include <sys/malloc.h>
  38 #include <machine/limits.h>
  39 #include <sys/devfs.h>
  40
  41 MALLOC_DECLARE(M_DEVFS);
  42
  43 /*
  44  * Locallized lock to ensure the integrity of the bitmap/cloning
  45  * code.  Callers using chk/set sequences must still check for races
  46  * or have their own locks.
  47  *
  48  * We use a recursive lock only to allow *_get() to call *_set().
  49  */
  50 static struct lock devfs_bitmap_lock =
  51         LOCK_INITIALIZER("dbmap", 0, LK_CANRECURSE);
  52
  53 /*
  54  * DEVFS clone bitmap functions
  55  */
  56 void
  57 devfs_clone_bitmap_init(struct devfs_bitmap *bitmap)
  58 {
  59         bitmap->chunks = DEVFS_BITMAP_INITIAL_SIZE;
  60         bitmap->bitmap = kmalloc(bitmap->chunks * sizeof(u_long),
  61                                  M_DEVFS, M_WAITOK);
  62         memset(bitmap->bitmap, -1, bitmap->chunks * sizeof(u_long));
  63 }
  64
  65
  66 void
  67 devfs_clone_bitmap_uninit(struct devfs_bitmap *bitmap)
  68 {
  69         kfree(bitmap->bitmap, M_DEVFS);
  70 }
  71
  72 /*
  73  * Extend the bitmap past (not just up to) 'newchunks' chunks.  While
  74  * probably not necessary, we go a little further and give ourselves
  75  * one extra chunk's worth of bitmap beyond what is required.
  76  */
  77 static void
  78 devfs_clone_bitmap_extend(struct devfs_bitmap *bitmap, int newchunks)
  79 {
  80         int oldchunks = bitmap->chunks;
  81
  82         bitmap->chunks = newchunks + 2;
  83         bitmap->bitmap = krealloc(bitmap->bitmap,
  84                                   sizeof(u_long) * bitmap->chunks,
  85                                   M_DEVFS, M_WAITOK);
  86         memset(bitmap->bitmap + oldchunks, -1,
  87                sizeof(u_long) * (bitmap->chunks - oldchunks));
  88 }
  89
  90 /*
  91  * This helper function determines the next available free unit in the
  92  * bitmap, extending the bitmap if necessary.  It cannot fail.
  93  */
  94 static int
  95 devfs_clone_bitmap_fff(struct devfs_bitmap *bitmap)
  96 {
  97         u_long curbitmap;
  98         int bit, i;
  99         int chunks;
 100
 101         chunks = bitmap->chunks;
 102
 103         for (i = 0; i < chunks + 1; i++) {
 104                 if (i == chunks)
 105                         devfs_clone_bitmap_extend(bitmap, i);
 106                 curbitmap = bitmap->bitmap[i];
 107
 108                 if (curbitmap) {
 109                         curbitmap &= (~curbitmap)+1;
 110                         for (bit = 1; curbitmap != 1; bit++)
 111                                 curbitmap >>= 1;
 112
 113                         return (bit - 1 + (i << 3) * sizeof(curbitmap));
 114                 }
 115         }
 116
 117         /*
 118          * NOT REACHED
 119          */
 120         panic("devfs_clone_bitmap_fff");
 121         return -1;
 122 }
 123
 124 /*
 125  * Caller wants to know if the specified unit has been allocated
 126  * or not.  Return 0, indicating that it has not been allocated.
 127  *
 128  * Caller must hold a lock to prevent chk-to-set races.  Devfs also
 129  * obtains a temporary lock, juse in case, to ensure structural
 130  * integrity.
 131  *
 132  * (the bitmap implements 0=allocated, 1=not-allocated but the
 133  * return value is inverted).
 134  */
 135 int
 136 devfs_clone_bitmap_chk(struct devfs_bitmap *bitmap, int unit)
 137 {
 138         int chunk;
 139         int res;
 140
 141         chunk = unit / (sizeof(u_long) * 8);
 142         unit -= chunk * (sizeof(u_long) * 8);
 143
 144         lockmgr(&devfs_bitmap_lock, LK_EXCLUSIVE);
 145         if (chunk >= bitmap->chunks) {
 146                 lockmgr(&devfs_bitmap_lock, LK_RELEASE);
 147                 return 0;               /* device does not exist */
 148         }
 149         res = !((bitmap->bitmap[chunk]) & (1UL << unit));
 150         lockmgr(&devfs_bitmap_lock, LK_RELEASE);
 151
 152         return res;
 153 }
 154
 155 /*
 156  * Unconditionally mark the specified unit as allocated in the bitmap.
 157  *
 158  * Caller must hold a lock to prevent chk-to-set races, or otherwise
 159  * check for a return value < 0 from this routine.  If the unit had
 160  * never been allocated in the past, a token lock might not be sufficient
 161  * to avoid races (if this function must extend the bitmap it could block
 162  * temporary in kmalloc()).
 163  *
 164  * devfs acquires a temporary lock to ensure structural integrity.
 165  *
 166  * If the bit is already clear (indicating that the unit is already
 167  * allocated), return -1.  Otherwise return 0.
 168  */
 169 int
 170 devfs_clone_bitmap_set(struct devfs_bitmap *bitmap, int unit)
 171 {
 172         int chunk;
 173         int res;
 174
 175         chunk = unit / (sizeof(u_long) * 8);
 176         unit -= chunk * (sizeof(u_long) * 8);
 177
 178         lockmgr(&devfs_bitmap_lock, LK_EXCLUSIVE);
 179         if (chunk >= bitmap->chunks)
 180                 devfs_clone_bitmap_extend(bitmap, chunk);
 181         if (bitmap->bitmap[chunk] & (1UL << unit)) {
 182                 bitmap->bitmap[chunk] &= ~(1UL << unit);
 183                 res = 0;
 184         } else {
 185                 res = -1;
 186         }
 187         lockmgr(&devfs_bitmap_lock, LK_RELEASE);
 188
 189         return res;
 190 }
 191
 192 /*
 193  * Unconditionally deallocate a unit number.  Caller must synchronize any
 194  * destroy_dev()'s the device called before clearing the bitmap bit to
 195  * avoid races against a new clone.
 196  */
 197 void
 198 devfs_clone_bitmap_put(struct devfs_bitmap *bitmap, int unit)
 199 {
 200         int chunk;
 201
 202         devfs_config();
 203
 204         chunk = unit / (sizeof(u_long) * 8);
 205         unit -= chunk * (sizeof(u_long) * 8);
 206
 207         lockmgr(&devfs_bitmap_lock, LK_EXCLUSIVE);
 208         if (chunk < bitmap->chunks)
 209                 bitmap->bitmap[chunk] |= (1UL << unit);
 210         lockmgr(&devfs_bitmap_lock, LK_RELEASE);
 211 }
 212
 213 /*
 214  * Conditionally allocate a unit from the bitmap.  Returns -1 if no
 215  * more units are available.
 216  *
 217  * Caller must hold a lock to avoid bitmap races.  Since *_fff() below
 218  * pre-extends the bitmap as necessary, a token lock is sufficient.
 219  */
 220 int
 221 devfs_clone_bitmap_get(struct devfs_bitmap *bitmap, int limit)
 222 {
 223         int unit;
 224
 225         lockmgr(&devfs_bitmap_lock, LK_EXCLUSIVE);
 226         unit = devfs_clone_bitmap_fff(bitmap);
 227         if (limit > 0 && unit > limit) {
 228                 unit = -1;
 229         } else {
 230                 devfs_clone_bitmap_set(bitmap, unit);
 231         }
 232         lockmgr(&devfs_bitmap_lock, LK_RELEASE);
 233
 234         return unit;
 235 }