1 /* 2 * Copyright (c) 2009 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/types.h> 38 #include <sys/param.h> 39 #include <machine/limits.h> 40 #include <vfs/devfs/devfs.h> 41 42 MALLOC_DECLARE(M_DEVFS); 43 44 static struct devfs_unit_hash *devfs_clone_hash_get(int, cdev_t); 45 static void devfs_clone_hash_put(struct devfs_unit_hash *); 46 static int devfs_clone_hash_add(struct devfs_unit_hash **, struct devfs_unit_hash *); 47 static struct devfs_unit_hash *devfs_clone_hash_del(struct devfs_unit_hash **, int); 48 49 /* 50 * DEVFS clone hash functions 51 */ 52 53 static struct devfs_unit_hash * 54 devfs_clone_hash_get(int unit_no, cdev_t dev) 55 { 56 struct devfs_unit_hash *hash = (struct devfs_unit_hash *)kmalloc(sizeof(struct devfs_unit_hash), M_DEVFS, M_WAITOK); 57 hash->next = NULL; 58 hash->unit_no = unit_no; 59 hash->dev = dev; 60 61 return hash; 62 } 63 64 65 static void 66 devfs_clone_hash_put(struct devfs_unit_hash *hash) 67 { 68 kfree(hash, M_DEVFS); 69 } 70 71 72 static int 73 devfs_clone_hash_add(struct devfs_unit_hash **devfs_hash_array, struct devfs_unit_hash *hash) 74 { 75 struct devfs_unit_hash **hashp; 76 hashp = &devfs_hash_array[hash->unit_no & 77 DEVFS_UNIT_HMASK]; 78 while (*hashp) { 79 if ((*hashp)->unit_no == 80 hash->unit_no) 81 return(EEXIST); 82 hashp = &(*hashp)->next; 83 } 84 hash->next = NULL; 85 *hashp = hash; 86 return (0); 87 } 88 89 90 static struct devfs_unit_hash * 91 devfs_clone_hash_del(struct devfs_unit_hash **devfs_hash_array, int unit_no) 92 { 93 struct devfs_unit_hash **hashp; 94 struct devfs_unit_hash *hash; 95 hashp = &devfs_hash_array[unit_no & 96 DEVFS_UNIT_HMASK]; 97 hash = *hashp; 98 while ((*hashp)->unit_no != unit_no) { 99 KKASSERT(*hashp != NULL); 100 hashp = &(*hashp)->next; 101 hash = *hashp; 102 } 103 *hashp = hash->next; 104 105 return hash; 106 } 107 108 /* 109 * DEVFS clone bitmap functions 110 */ 111 void 112 devfs_clone_bitmap_init(struct devfs_bitmap *bitmap) 113 { 114 bitmap->bitmap = (unsigned long *)kmalloc(DEVFS_BITMAP_INITIAL_SIZE*sizeof(unsigned long), M_DEVFS, M_WAITOK); 115 bitmap->chunks = DEVFS_BITMAP_INITIAL_SIZE; 116 memset(bitmap->bitmap, ULONG_MAX, DEVFS_BITMAP_INITIAL_SIZE*sizeof(unsigned long)); 117 } 118 119 120 void 121 devfs_clone_bitmap_uninit(struct devfs_bitmap *bitmap) 122 { 123 kfree(bitmap, M_DEVFS); 124 } 125 126 127 void 128 devfs_clone_bitmap_resize(struct devfs_bitmap *bitmap, int newchunks) 129 { 130 int oldchunks = bitmap->chunks; 131 bitmap->chunks = newchunks+2; 132 bitmap->bitmap = (unsigned long *)krealloc(bitmap->bitmap, sizeof(unsigned long)*bitmap->chunks, M_DEVFS, M_WAITOK); 133 134 devfs_debug(DEVFS_DEBUG_DEBUG, "%d vs %d (oldchunks=%d)\n", bitmap->bitmap, bitmap->bitmap + oldchunks, oldchunks); 135 memset(bitmap->bitmap + oldchunks, ULONG_MAX, sizeof(unsigned long)*(bitmap->chunks - oldchunks)); 136 } 137 138 139 int 140 devfs_clone_bitmap_fff(struct devfs_bitmap *bitmap) 141 { 142 unsigned long curbitmap; 143 int bit, i; 144 int chunks = bitmap->chunks; 145 146 for (i = 0; i < chunks+1; i++) { 147 if (i == chunks) 148 devfs_clone_bitmap_resize(bitmap, i); 149 curbitmap = bitmap->bitmap[i]; 150 151 if (curbitmap > 0) { 152 curbitmap &= (~curbitmap)+1; 153 for (bit = 1; curbitmap != 1; bit++) 154 curbitmap = (unsigned long)curbitmap >> 1; 155 156 return bit-1 + (i<<3) * sizeof(unsigned long); 157 } 158 } 159 160 /* Should never happen as we dynamically resize as needed */ 161 return -1; 162 } 163 164 165 int 166 devfs_clone_bitmap_chk(struct devfs_bitmap *bitmap, int unit) 167 { 168 int chunk = unit / (sizeof(unsigned long)<<3); 169 unit -= chunk<<3 * sizeof(unsigned long); 170 171 if (chunk >= bitmap->chunks) 172 return 1; 173 174 return !((bitmap->bitmap[chunk]) & (1<<(unit))); 175 } 176 177 178 void 179 devfs_clone_bitmap_set(struct devfs_bitmap *bitmap, int unit) 180 { 181 int chunk = unit / (sizeof(unsigned long)<<3); 182 unit -= chunk<<3 * sizeof(unsigned long); 183 184 if (chunk >= bitmap->chunks) { 185 devfs_clone_bitmap_resize(bitmap, chunk); 186 } 187 188 bitmap->bitmap[chunk] ^= (1<<unit); 189 } 190 191 192 void 193 devfs_clone_bitmap_rst(struct devfs_bitmap *bitmap, int unit) 194 { 195 int chunk = unit / (sizeof(unsigned long)<<3); 196 unit -= chunk<<3 * sizeof(unsigned long); 197 198 if (chunk >= bitmap->chunks) 199 return; 200 201 bitmap->bitmap[chunk] |= (1<<unit); 202 } 203 204 205 int 206 devfs_clone_bitmap_get(struct devfs_bitmap *bitmap, int limit) 207 { 208 int unit; 209 unit = devfs_clone_bitmap_fff(bitmap); 210 KKASSERT(unit != -1); 211 212 if ((limit > 0) && (unit > limit)) 213 return -1; 214 215 devfs_clone_bitmap_set(bitmap, unit); 216 217 return unit; 218 } 219 220 /* 221 * DEVFS clone helper functions 222 */ 223 224 void 225 devfs_clone_helper_init(struct devfs_clone_helper *helper) 226 { 227 devfs_clone_bitmap_init(&helper->DEVFS_CLONE_BITMAP(generic)); 228 memset(&helper->DEVFS_CLONE_HASHLIST(generic), 0, DEVFS_UNIT_HSIZE*sizeof(void *)); 229 } 230 231 232 void 233 devfs_clone_helper_uninit(struct devfs_clone_helper *helper) 234 { 235 devfs_clone_bitmap_uninit(&helper->DEVFS_CLONE_BITMAP(generic)); 236 //XXX: free all elements in helper->DEVFS_HASHLIST(generic) 237 } 238 239 240 int 241 devfs_clone_helper_insert(struct devfs_clone_helper *helper, cdev_t dev) 242 { 243 struct devfs_unit_hash *hash; 244 int error = 0; 245 int unit_no; 246 247 try_again: 248 unit_no = devfs_clone_bitmap_fff(&helper->DEVFS_CLONE_BITMAP(generic)); 249 250 devfs_clone_bitmap_set(&helper->DEVFS_CLONE_BITMAP(generic), unit_no); 251 hash = devfs_clone_hash_get(unit_no, dev); 252 253 error = devfs_clone_hash_add(helper->DEVFS_CLONE_HASHLIST(generic), hash); 254 KKASSERT(!error); 255 256 if (error) 257 goto try_again; 258 259 dev->si_uminor = unit_no; 260 return unit_no; 261 } 262 263 264 int 265 devfs_clone_helper_remove(struct devfs_clone_helper *helper, int unit_no) 266 { 267 struct devfs_unit_hash *hash; 268 hash = devfs_clone_hash_del(helper->DEVFS_CLONE_HASHLIST(generic), unit_no); 269 devfs_clone_bitmap_rst(&helper->DEVFS_CLONE_BITMAP(generic), unit_no); 270 kfree(hash, M_DEVFS); 271 272 return 0; 273 } 274