1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 #pragma ident "%Z%%M% %I% %E% SMI" 28 29 #include <fmd_alloc.h> 30 #include <fmd_subr.h> 31 #include <fmd_conf.h> 32 #include <fmd_error.h> 33 #include <fmd_string.h> 34 #include <fmd_idspace.h> 35 #include <fmd.h> 36 37 static int 38 highbit(ulong_t i) 39 { 40 int h = 1; 41 42 if (i == 0) 43 return (0); 44 45 #ifdef _LP64 46 if (i & 0xffffffff00000000ul) { 47 h += 32; 48 i >>= 32; 49 } 50 #endif 51 52 if (i & 0xffff0000) { 53 h += 16; 54 i >>= 16; 55 } 56 57 if (i & 0xff00) { 58 h += 8; 59 i >>= 8; 60 } 61 62 if (i & 0xf0) { 63 h += 4; 64 i >>= 4; 65 } 66 67 if (i & 0xc) { 68 h += 2; 69 i >>= 2; 70 } 71 72 if (i & 0x2) 73 h += 1; 74 75 return (h); 76 } 77 78 fmd_idspace_t * 79 fmd_idspace_create(const char *name, id_t min, id_t max) 80 { 81 fmd_idspace_t *ids = fmd_alloc(sizeof (fmd_idspace_t), FMD_SLEEP); 82 uint_t ids_avg, ids_max, hashlen, hashmax; 83 84 /* 85 * Dynamically size the hash table bucket array based on the desired 86 * chain length. We hash by indexing on the low-order bits. 87 * Do not permit the hash bucket array to exceed a reasonable size. 88 */ 89 ASSERT(min >= 0 && max >= 0); 90 ASSERT(max >= min); 91 92 (void) fmd_conf_getprop(fmd.d_conf, "ids.avg", &ids_avg); 93 (void) fmd_conf_getprop(fmd.d_conf, "ids.max", &ids_max); 94 95 hashmax = max - min + 1; 96 hashlen = 1 << highbit(hashmax / ids_avg); 97 if (hashlen > ids_max) 98 hashlen = ids_max; 99 100 (void) strlcpy(ids->ids_name, name, sizeof (ids->ids_name)); 101 (void) pthread_mutex_init(&ids->ids_lock, NULL); 102 (void) pthread_cond_init(&ids->ids_cv, NULL); 103 104 ids->ids_hash = fmd_zalloc(sizeof (void *) * hashlen, FMD_SLEEP); 105 ids->ids_hashlen = hashlen; 106 ids->ids_refs = 0; 107 ids->ids_nextid = min - 1; 108 ids->ids_minid = min; 109 ids->ids_maxid = max; 110 ids->ids_count = 0; 111 112 return (ids); 113 } 114 115 void 116 fmd_idspace_destroy(fmd_idspace_t *ids) 117 { 118 fmd_idelem_t *ide, *nde; 119 uint_t i; 120 121 (void) pthread_mutex_lock(&ids->ids_lock); 122 123 while (ids->ids_refs != 0) 124 (void) pthread_cond_wait(&ids->ids_cv, &ids->ids_lock); 125 126 for (i = 0; i < ids->ids_hashlen; i++) { 127 for (ide = ids->ids_hash[i]; ide != NULL; ide = nde) { 128 nde = ide->ide_next; 129 fmd_free(ide, sizeof (fmd_idelem_t)); 130 } 131 } 132 133 fmd_free(ids->ids_hash, sizeof (void *) * ids->ids_hashlen); 134 fmd_free(ids, sizeof (fmd_idspace_t)); 135 } 136 137 void 138 fmd_idspace_apply(fmd_idspace_t *ids, 139 void (*func)(fmd_idspace_t *, id_t, void *), void *arg) 140 { 141 fmd_idelem_t *ide; 142 id_t *ida, *idp; 143 uint_t i, count; 144 145 (void) pthread_mutex_lock(&ids->ids_lock); 146 count = ids->ids_count; 147 ida = idp = fmd_alloc(sizeof (id_t) * count, FMD_SLEEP); 148 149 for (i = 0; i < ids->ids_hashlen; i++) { 150 for (ide = ids->ids_hash[i]; ide != NULL; ide = ide->ide_next) 151 *idp++ = ide->ide_id; 152 } 153 154 ASSERT(idp == ida + count); 155 (void) pthread_mutex_unlock(&ids->ids_lock); 156 157 for (i = 0; i < count; i++) 158 func(ids, ida[i], arg); 159 160 fmd_free(ida, sizeof (id_t) * count); 161 } 162 163 static fmd_idelem_t * 164 fmd_idspace_lookup(fmd_idspace_t *ids, id_t id) 165 { 166 fmd_idelem_t *ide; 167 168 ASSERT(MUTEX_HELD(&ids->ids_lock)); 169 ide = ids->ids_hash[id & (ids->ids_hashlen - 1)]; 170 171 for (; ide != NULL; ide = ide->ide_next) { 172 if (ide->ide_id == id) 173 break; 174 } 175 176 return (ide); 177 } 178 179 void * 180 fmd_idspace_getspecific(fmd_idspace_t *ids, id_t id) 181 { 182 fmd_idelem_t *ide; 183 void *data; 184 185 (void) pthread_mutex_lock(&ids->ids_lock); 186 ide = fmd_idspace_lookup(ids, id); 187 data = ide ? ide->ide_data : NULL; 188 (void) pthread_mutex_unlock(&ids->ids_lock); 189 190 return (data); 191 } 192 193 void 194 fmd_idspace_setspecific(fmd_idspace_t *ids, id_t id, void *data) 195 { 196 fmd_idelem_t *ide; 197 198 (void) pthread_mutex_lock(&ids->ids_lock); 199 200 while (ids->ids_refs != 0) 201 (void) pthread_cond_wait(&ids->ids_cv, &ids->ids_lock); 202 203 if ((ide = fmd_idspace_lookup(ids, id)) == NULL) { 204 fmd_panic("idspace %p (%s) does not contain id %ld", 205 (void *)ids, ids->ids_name, id); 206 } 207 208 ide->ide_data = data; 209 (void) pthread_mutex_unlock(&ids->ids_lock); 210 } 211 212 int 213 fmd_idspace_contains(fmd_idspace_t *ids, id_t id) 214 { 215 fmd_idelem_t *ide; 216 217 (void) pthread_mutex_lock(&ids->ids_lock); 218 ide = fmd_idspace_lookup(ids, id); 219 (void) pthread_mutex_unlock(&ids->ids_lock); 220 221 return (ide != NULL); 222 } 223 224 int 225 fmd_idspace_valid(fmd_idspace_t *ids, id_t id) 226 { 227 return (id >= ids->ids_minid && id <= ids->ids_maxid); 228 } 229 230 static id_t 231 fmd_idspace_xalloc_locked(fmd_idspace_t *ids, id_t id, void *data) 232 { 233 fmd_idelem_t *ide; 234 uint_t h; 235 236 if (id < ids->ids_minid || id > ids->ids_maxid) { 237 fmd_panic("%ld out of range [%ld .. %ld] for idspace %p (%s)\n", 238 id, ids->ids_minid, ids->ids_maxid, 239 (void *)ids, ids->ids_name); 240 } 241 242 if (fmd_idspace_lookup(ids, id) != NULL) 243 return (fmd_set_errno(EALREADY)); 244 245 ide = fmd_alloc(sizeof (fmd_idelem_t), FMD_SLEEP); 246 h = id & (ids->ids_hashlen - 1); 247 248 ide->ide_next = ids->ids_hash[h]; 249 ide->ide_data = data; 250 ide->ide_id = id; 251 252 ids->ids_hash[h] = ide; 253 ids->ids_count++; 254 255 return (id); 256 } 257 258 id_t 259 fmd_idspace_xalloc(fmd_idspace_t *ids, id_t id, void *data) 260 { 261 (void) pthread_mutex_lock(&ids->ids_lock); 262 id = fmd_idspace_xalloc_locked(ids, id, data); 263 (void) pthread_mutex_unlock(&ids->ids_lock); 264 return (id); 265 } 266 267 static id_t 268 fmd_idspace_alloc_locked(fmd_idspace_t *ids, void *data) 269 { 270 id_t id; 271 272 ASSERT(MUTEX_HELD(&ids->ids_lock)); 273 274 if (ids->ids_count == ids->ids_maxid - ids->ids_minid + 1) 275 return (fmd_set_errno(ENOSPC)); 276 277 do { 278 if (++ids->ids_nextid > ids->ids_maxid) 279 ids->ids_nextid = ids->ids_minid; 280 id = ids->ids_nextid; 281 } while (fmd_idspace_xalloc_locked(ids, id, data) != id); 282 283 return (id); 284 } 285 286 id_t 287 fmd_idspace_alloc(fmd_idspace_t *ids, void *data) 288 { 289 id_t id; 290 291 (void) pthread_mutex_lock(&ids->ids_lock); 292 id = fmd_idspace_alloc_locked(ids, data); 293 (void) pthread_mutex_unlock(&ids->ids_lock); 294 295 return (id); 296 } 297 298 /* 299 * For the moment, we use a simple but slow implementation: reset ids_nextid to 300 * the minimum id and search in order from there. If this becomes performance 301 * sensitive we can maintain a freelist of the unallocated identifiers, etc. 302 */ 303 id_t 304 fmd_idspace_alloc_min(fmd_idspace_t *ids, void *data) 305 { 306 id_t id; 307 308 (void) pthread_mutex_lock(&ids->ids_lock); 309 ids->ids_nextid = ids->ids_minid - 1; 310 id = fmd_idspace_alloc_locked(ids, data); 311 (void) pthread_mutex_unlock(&ids->ids_lock); 312 313 return (id); 314 } 315 316 void * 317 fmd_idspace_free(fmd_idspace_t *ids, id_t id) 318 { 319 fmd_idelem_t *ide, **pp; 320 void *data; 321 322 (void) pthread_mutex_lock(&ids->ids_lock); 323 pp = &ids->ids_hash[id & (ids->ids_hashlen - 1)]; 324 325 for (ide = *pp; ide != NULL; ide = ide->ide_next) { 326 if (ide->ide_id != id) 327 pp = &ide->ide_next; 328 else 329 break; 330 } 331 332 if (ide == NULL) { 333 (void) pthread_mutex_unlock(&ids->ids_lock); 334 return (NULL); 335 } 336 337 data = ide->ide_data; 338 *pp = ide->ide_next; 339 fmd_free(ide, sizeof (fmd_idelem_t)); 340 341 ASSERT(ids->ids_count != 0); 342 ids->ids_count--; 343 344 (void) pthread_mutex_unlock(&ids->ids_lock); 345 return (data); 346 } 347 348 /* 349 * Retrieve the id-specific data for the specified id and place a hold on the 350 * id so that it cannot be or deleted until fmd_idspace_rele(ids, id) is 351 * called. For simplicity, we now use a single global reference count for all 352 * holds. If this feature needs to be used in a place where there is high 353 * contention between holders and deleters, the implementation can be modified 354 * to use either a per-hash-bucket or a per-id-element condition variable. 355 */ 356 void * 357 fmd_idspace_hold(fmd_idspace_t *ids, id_t id) 358 { 359 fmd_idelem_t *ide; 360 void *data = NULL; 361 362 (void) pthread_mutex_lock(&ids->ids_lock); 363 364 if ((ide = fmd_idspace_lookup(ids, id)) != NULL) { 365 ids->ids_refs++; 366 ASSERT(ids->ids_refs != 0); 367 data = ide->ide_data; 368 ASSERT(data != NULL); 369 } 370 371 (void) pthread_mutex_unlock(&ids->ids_lock); 372 return (data); 373 } 374 375 void 376 fmd_idspace_rele(fmd_idspace_t *ids, id_t id) 377 { 378 (void) pthread_mutex_lock(&ids->ids_lock); 379 380 ASSERT(fmd_idspace_lookup(ids, id) != NULL); 381 ASSERT(ids->ids_refs != 0); 382 ids->ids_refs--; 383 384 (void) pthread_cond_broadcast(&ids->ids_cv); 385 (void) pthread_mutex_unlock(&ids->ids_lock); 386 } 387