1*7c478bd9Sstevel@tonic-gate /* 2*7c478bd9Sstevel@tonic-gate * CDDL HEADER START 3*7c478bd9Sstevel@tonic-gate * 4*7c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the 5*7c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 6*7c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 7*7c478bd9Sstevel@tonic-gate * with the License. 8*7c478bd9Sstevel@tonic-gate * 9*7c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10*7c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 11*7c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions 12*7c478bd9Sstevel@tonic-gate * and limitations under the License. 13*7c478bd9Sstevel@tonic-gate * 14*7c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 15*7c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16*7c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 17*7c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 18*7c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 19*7c478bd9Sstevel@tonic-gate * 20*7c478bd9Sstevel@tonic-gate * CDDL HEADER END 21*7c478bd9Sstevel@tonic-gate */ 22*7c478bd9Sstevel@tonic-gate /* 23*7c478bd9Sstevel@tonic-gate * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 24*7c478bd9Sstevel@tonic-gate * Use is subject to license terms. 25*7c478bd9Sstevel@tonic-gate */ 26*7c478bd9Sstevel@tonic-gate 27*7c478bd9Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 28*7c478bd9Sstevel@tonic-gate 29*7c478bd9Sstevel@tonic-gate #include <fmd_alloc.h> 30*7c478bd9Sstevel@tonic-gate #include <fmd_subr.h> 31*7c478bd9Sstevel@tonic-gate #include <fmd_conf.h> 32*7c478bd9Sstevel@tonic-gate #include <fmd_error.h> 33*7c478bd9Sstevel@tonic-gate #include <fmd_string.h> 34*7c478bd9Sstevel@tonic-gate #include <fmd_idspace.h> 35*7c478bd9Sstevel@tonic-gate #include <fmd.h> 36*7c478bd9Sstevel@tonic-gate 37*7c478bd9Sstevel@tonic-gate static int 38*7c478bd9Sstevel@tonic-gate highbit(ulong_t i) 39*7c478bd9Sstevel@tonic-gate { 40*7c478bd9Sstevel@tonic-gate int h = 1; 41*7c478bd9Sstevel@tonic-gate 42*7c478bd9Sstevel@tonic-gate if (i == 0) 43*7c478bd9Sstevel@tonic-gate return (0); 44*7c478bd9Sstevel@tonic-gate 45*7c478bd9Sstevel@tonic-gate #ifdef _LP64 46*7c478bd9Sstevel@tonic-gate if (i & 0xffffffff00000000ul) { 47*7c478bd9Sstevel@tonic-gate h += 32; 48*7c478bd9Sstevel@tonic-gate i >>= 32; 49*7c478bd9Sstevel@tonic-gate } 50*7c478bd9Sstevel@tonic-gate #endif 51*7c478bd9Sstevel@tonic-gate 52*7c478bd9Sstevel@tonic-gate if (i & 0xffff0000) { 53*7c478bd9Sstevel@tonic-gate h += 16; 54*7c478bd9Sstevel@tonic-gate i >>= 16; 55*7c478bd9Sstevel@tonic-gate } 56*7c478bd9Sstevel@tonic-gate 57*7c478bd9Sstevel@tonic-gate if (i & 0xff00) { 58*7c478bd9Sstevel@tonic-gate h += 8; 59*7c478bd9Sstevel@tonic-gate i >>= 8; 60*7c478bd9Sstevel@tonic-gate } 61*7c478bd9Sstevel@tonic-gate 62*7c478bd9Sstevel@tonic-gate if (i & 0xf0) { 63*7c478bd9Sstevel@tonic-gate h += 4; 64*7c478bd9Sstevel@tonic-gate i >>= 4; 65*7c478bd9Sstevel@tonic-gate } 66*7c478bd9Sstevel@tonic-gate 67*7c478bd9Sstevel@tonic-gate if (i & 0xc) { 68*7c478bd9Sstevel@tonic-gate h += 2; 69*7c478bd9Sstevel@tonic-gate i >>= 2; 70*7c478bd9Sstevel@tonic-gate } 71*7c478bd9Sstevel@tonic-gate 72*7c478bd9Sstevel@tonic-gate if (i & 0x2) 73*7c478bd9Sstevel@tonic-gate h += 1; 74*7c478bd9Sstevel@tonic-gate 75*7c478bd9Sstevel@tonic-gate return (h); 76*7c478bd9Sstevel@tonic-gate } 77*7c478bd9Sstevel@tonic-gate 78*7c478bd9Sstevel@tonic-gate fmd_idspace_t * 79*7c478bd9Sstevel@tonic-gate fmd_idspace_create(const char *name, id_t min, id_t max) 80*7c478bd9Sstevel@tonic-gate { 81*7c478bd9Sstevel@tonic-gate fmd_idspace_t *ids = fmd_alloc(sizeof (fmd_idspace_t), FMD_SLEEP); 82*7c478bd9Sstevel@tonic-gate uint_t ids_avg, ids_max, hashlen, hashmax; 83*7c478bd9Sstevel@tonic-gate 84*7c478bd9Sstevel@tonic-gate /* 85*7c478bd9Sstevel@tonic-gate * Dynamically size the hash table bucket array based on the desired 86*7c478bd9Sstevel@tonic-gate * chain length. We hash by indexing on the low-order bits. 87*7c478bd9Sstevel@tonic-gate * Do not permit the hash bucket array to exceed a reasonable size. 88*7c478bd9Sstevel@tonic-gate */ 89*7c478bd9Sstevel@tonic-gate ASSERT(min >= 0 && max >= 0); 90*7c478bd9Sstevel@tonic-gate ASSERT(max >= min); 91*7c478bd9Sstevel@tonic-gate 92*7c478bd9Sstevel@tonic-gate (void) fmd_conf_getprop(fmd.d_conf, "ids.avg", &ids_avg); 93*7c478bd9Sstevel@tonic-gate (void) fmd_conf_getprop(fmd.d_conf, "ids.max", &ids_max); 94*7c478bd9Sstevel@tonic-gate 95*7c478bd9Sstevel@tonic-gate hashmax = max - min + 1; 96*7c478bd9Sstevel@tonic-gate hashlen = 1 << highbit(hashmax / ids_avg); 97*7c478bd9Sstevel@tonic-gate if (hashlen > ids_max) 98*7c478bd9Sstevel@tonic-gate hashlen = ids_max; 99*7c478bd9Sstevel@tonic-gate 100*7c478bd9Sstevel@tonic-gate (void) strlcpy(ids->ids_name, name, sizeof (ids->ids_name)); 101*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_init(&ids->ids_lock, NULL); 102*7c478bd9Sstevel@tonic-gate 103*7c478bd9Sstevel@tonic-gate ids->ids_hash = fmd_zalloc(sizeof (void *) * hashlen, FMD_SLEEP); 104*7c478bd9Sstevel@tonic-gate ids->ids_hashlen = hashlen; 105*7c478bd9Sstevel@tonic-gate ids->ids_nextid = min - 1; 106*7c478bd9Sstevel@tonic-gate ids->ids_minid = min; 107*7c478bd9Sstevel@tonic-gate ids->ids_maxid = max; 108*7c478bd9Sstevel@tonic-gate ids->ids_count = 0; 109*7c478bd9Sstevel@tonic-gate 110*7c478bd9Sstevel@tonic-gate return (ids); 111*7c478bd9Sstevel@tonic-gate } 112*7c478bd9Sstevel@tonic-gate 113*7c478bd9Sstevel@tonic-gate void 114*7c478bd9Sstevel@tonic-gate fmd_idspace_destroy(fmd_idspace_t *ids) 115*7c478bd9Sstevel@tonic-gate { 116*7c478bd9Sstevel@tonic-gate fmd_idelem_t *ide, *nde; 117*7c478bd9Sstevel@tonic-gate uint_t i; 118*7c478bd9Sstevel@tonic-gate 119*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_lock(&ids->ids_lock); 120*7c478bd9Sstevel@tonic-gate 121*7c478bd9Sstevel@tonic-gate for (i = 0; i < ids->ids_hashlen; i++) { 122*7c478bd9Sstevel@tonic-gate for (ide = ids->ids_hash[i]; ide != NULL; ide = nde) { 123*7c478bd9Sstevel@tonic-gate nde = ide->ide_next; 124*7c478bd9Sstevel@tonic-gate fmd_free(ide, sizeof (fmd_idelem_t)); 125*7c478bd9Sstevel@tonic-gate } 126*7c478bd9Sstevel@tonic-gate } 127*7c478bd9Sstevel@tonic-gate 128*7c478bd9Sstevel@tonic-gate fmd_free(ids->ids_hash, sizeof (void *) * ids->ids_hashlen); 129*7c478bd9Sstevel@tonic-gate fmd_free(ids, sizeof (fmd_idspace_t)); 130*7c478bd9Sstevel@tonic-gate } 131*7c478bd9Sstevel@tonic-gate 132*7c478bd9Sstevel@tonic-gate void 133*7c478bd9Sstevel@tonic-gate fmd_idspace_apply(fmd_idspace_t *ids, void (*func)(void *, id_t), void *arg) 134*7c478bd9Sstevel@tonic-gate { 135*7c478bd9Sstevel@tonic-gate fmd_idelem_t *ide; 136*7c478bd9Sstevel@tonic-gate id_t *ida, *idp; 137*7c478bd9Sstevel@tonic-gate uint_t i, count; 138*7c478bd9Sstevel@tonic-gate 139*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_lock(&ids->ids_lock); 140*7c478bd9Sstevel@tonic-gate count = ids->ids_count; 141*7c478bd9Sstevel@tonic-gate ida = idp = fmd_alloc(sizeof (id_t) * count, FMD_SLEEP); 142*7c478bd9Sstevel@tonic-gate 143*7c478bd9Sstevel@tonic-gate for (i = 0; i < ids->ids_hashlen; i++) { 144*7c478bd9Sstevel@tonic-gate for (ide = ids->ids_hash[i]; ide != NULL; ide = ide->ide_next) 145*7c478bd9Sstevel@tonic-gate *idp++ = ide->ide_id; 146*7c478bd9Sstevel@tonic-gate } 147*7c478bd9Sstevel@tonic-gate 148*7c478bd9Sstevel@tonic-gate ASSERT(idp == ida + count); 149*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&ids->ids_lock); 150*7c478bd9Sstevel@tonic-gate 151*7c478bd9Sstevel@tonic-gate for (i = 0; i < count; i++) 152*7c478bd9Sstevel@tonic-gate func(arg, ida[i]); 153*7c478bd9Sstevel@tonic-gate 154*7c478bd9Sstevel@tonic-gate fmd_free(ida, sizeof (id_t) * count); 155*7c478bd9Sstevel@tonic-gate } 156*7c478bd9Sstevel@tonic-gate 157*7c478bd9Sstevel@tonic-gate static fmd_idelem_t * 158*7c478bd9Sstevel@tonic-gate fmd_idspace_lookup(fmd_idspace_t *ids, id_t id) 159*7c478bd9Sstevel@tonic-gate { 160*7c478bd9Sstevel@tonic-gate fmd_idelem_t *ide; 161*7c478bd9Sstevel@tonic-gate 162*7c478bd9Sstevel@tonic-gate ASSERT(MUTEX_HELD(&ids->ids_lock)); 163*7c478bd9Sstevel@tonic-gate ide = ids->ids_hash[id & (ids->ids_hashlen - 1)]; 164*7c478bd9Sstevel@tonic-gate 165*7c478bd9Sstevel@tonic-gate for (; ide != NULL; ide = ide->ide_next) { 166*7c478bd9Sstevel@tonic-gate if (ide->ide_id == id) 167*7c478bd9Sstevel@tonic-gate break; 168*7c478bd9Sstevel@tonic-gate } 169*7c478bd9Sstevel@tonic-gate 170*7c478bd9Sstevel@tonic-gate return (ide); 171*7c478bd9Sstevel@tonic-gate } 172*7c478bd9Sstevel@tonic-gate 173*7c478bd9Sstevel@tonic-gate void * 174*7c478bd9Sstevel@tonic-gate fmd_idspace_getspecific(fmd_idspace_t *ids, id_t id) 175*7c478bd9Sstevel@tonic-gate { 176*7c478bd9Sstevel@tonic-gate fmd_idelem_t *ide; 177*7c478bd9Sstevel@tonic-gate void *data; 178*7c478bd9Sstevel@tonic-gate 179*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_lock(&ids->ids_lock); 180*7c478bd9Sstevel@tonic-gate ide = fmd_idspace_lookup(ids, id); 181*7c478bd9Sstevel@tonic-gate data = ide ? ide->ide_data : NULL; 182*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&ids->ids_lock); 183*7c478bd9Sstevel@tonic-gate 184*7c478bd9Sstevel@tonic-gate return (data); 185*7c478bd9Sstevel@tonic-gate } 186*7c478bd9Sstevel@tonic-gate 187*7c478bd9Sstevel@tonic-gate void 188*7c478bd9Sstevel@tonic-gate fmd_idspace_setspecific(fmd_idspace_t *ids, id_t id, void *data) 189*7c478bd9Sstevel@tonic-gate { 190*7c478bd9Sstevel@tonic-gate fmd_idelem_t *ide; 191*7c478bd9Sstevel@tonic-gate 192*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_lock(&ids->ids_lock); 193*7c478bd9Sstevel@tonic-gate 194*7c478bd9Sstevel@tonic-gate if ((ide = fmd_idspace_lookup(ids, id)) == NULL) { 195*7c478bd9Sstevel@tonic-gate fmd_panic("idspace %p (%s) does not contain id %ld", 196*7c478bd9Sstevel@tonic-gate (void *)ids, ids->ids_name, id); 197*7c478bd9Sstevel@tonic-gate } 198*7c478bd9Sstevel@tonic-gate 199*7c478bd9Sstevel@tonic-gate ide->ide_data = data; 200*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&ids->ids_lock); 201*7c478bd9Sstevel@tonic-gate } 202*7c478bd9Sstevel@tonic-gate 203*7c478bd9Sstevel@tonic-gate int 204*7c478bd9Sstevel@tonic-gate fmd_idspace_contains(fmd_idspace_t *ids, id_t id) 205*7c478bd9Sstevel@tonic-gate { 206*7c478bd9Sstevel@tonic-gate fmd_idelem_t *ide; 207*7c478bd9Sstevel@tonic-gate 208*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_lock(&ids->ids_lock); 209*7c478bd9Sstevel@tonic-gate ide = fmd_idspace_lookup(ids, id); 210*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&ids->ids_lock); 211*7c478bd9Sstevel@tonic-gate 212*7c478bd9Sstevel@tonic-gate return (ide != NULL); 213*7c478bd9Sstevel@tonic-gate } 214*7c478bd9Sstevel@tonic-gate 215*7c478bd9Sstevel@tonic-gate int 216*7c478bd9Sstevel@tonic-gate fmd_idspace_valid(fmd_idspace_t *ids, id_t id) 217*7c478bd9Sstevel@tonic-gate { 218*7c478bd9Sstevel@tonic-gate return (id >= ids->ids_minid && id <= ids->ids_maxid); 219*7c478bd9Sstevel@tonic-gate } 220*7c478bd9Sstevel@tonic-gate 221*7c478bd9Sstevel@tonic-gate static id_t 222*7c478bd9Sstevel@tonic-gate fmd_idspace_xalloc_locked(fmd_idspace_t *ids, id_t id, void *data) 223*7c478bd9Sstevel@tonic-gate { 224*7c478bd9Sstevel@tonic-gate fmd_idelem_t *ide; 225*7c478bd9Sstevel@tonic-gate uint_t h; 226*7c478bd9Sstevel@tonic-gate 227*7c478bd9Sstevel@tonic-gate if (id < ids->ids_minid || id > ids->ids_maxid) { 228*7c478bd9Sstevel@tonic-gate fmd_panic("%ld out of range [%ld .. %ld] for idspace %p (%s)\n", 229*7c478bd9Sstevel@tonic-gate id, ids->ids_minid, ids->ids_maxid, 230*7c478bd9Sstevel@tonic-gate (void *)ids, ids->ids_name); 231*7c478bd9Sstevel@tonic-gate } 232*7c478bd9Sstevel@tonic-gate 233*7c478bd9Sstevel@tonic-gate if (fmd_idspace_lookup(ids, id) != NULL) 234*7c478bd9Sstevel@tonic-gate return (fmd_set_errno(EALREADY)); 235*7c478bd9Sstevel@tonic-gate 236*7c478bd9Sstevel@tonic-gate ide = fmd_alloc(sizeof (fmd_idelem_t), FMD_SLEEP); 237*7c478bd9Sstevel@tonic-gate h = id & (ids->ids_hashlen - 1); 238*7c478bd9Sstevel@tonic-gate 239*7c478bd9Sstevel@tonic-gate ide->ide_next = ids->ids_hash[h]; 240*7c478bd9Sstevel@tonic-gate ide->ide_data = data; 241*7c478bd9Sstevel@tonic-gate ide->ide_id = id; 242*7c478bd9Sstevel@tonic-gate 243*7c478bd9Sstevel@tonic-gate ids->ids_hash[h] = ide; 244*7c478bd9Sstevel@tonic-gate ids->ids_count++; 245*7c478bd9Sstevel@tonic-gate 246*7c478bd9Sstevel@tonic-gate return (id); 247*7c478bd9Sstevel@tonic-gate } 248*7c478bd9Sstevel@tonic-gate 249*7c478bd9Sstevel@tonic-gate id_t 250*7c478bd9Sstevel@tonic-gate fmd_idspace_xalloc(fmd_idspace_t *ids, id_t id, void *data) 251*7c478bd9Sstevel@tonic-gate { 252*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_lock(&ids->ids_lock); 253*7c478bd9Sstevel@tonic-gate id = fmd_idspace_xalloc_locked(ids, id, data); 254*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&ids->ids_lock); 255*7c478bd9Sstevel@tonic-gate return (id); 256*7c478bd9Sstevel@tonic-gate } 257*7c478bd9Sstevel@tonic-gate 258*7c478bd9Sstevel@tonic-gate id_t 259*7c478bd9Sstevel@tonic-gate fmd_idspace_alloc(fmd_idspace_t *ids, void *data) 260*7c478bd9Sstevel@tonic-gate { 261*7c478bd9Sstevel@tonic-gate id_t id; 262*7c478bd9Sstevel@tonic-gate 263*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_lock(&ids->ids_lock); 264*7c478bd9Sstevel@tonic-gate 265*7c478bd9Sstevel@tonic-gate if (ids->ids_count == ids->ids_maxid - ids->ids_minid + 1) { 266*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&ids->ids_lock); 267*7c478bd9Sstevel@tonic-gate return (fmd_set_errno(ENOSPC)); 268*7c478bd9Sstevel@tonic-gate } 269*7c478bd9Sstevel@tonic-gate 270*7c478bd9Sstevel@tonic-gate do { 271*7c478bd9Sstevel@tonic-gate if (++ids->ids_nextid > ids->ids_maxid) 272*7c478bd9Sstevel@tonic-gate ids->ids_nextid = ids->ids_minid; 273*7c478bd9Sstevel@tonic-gate id = ids->ids_nextid; 274*7c478bd9Sstevel@tonic-gate } while (fmd_idspace_xalloc_locked(ids, id, data) != id); 275*7c478bd9Sstevel@tonic-gate 276*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&ids->ids_lock); 277*7c478bd9Sstevel@tonic-gate return (id); 278*7c478bd9Sstevel@tonic-gate } 279*7c478bd9Sstevel@tonic-gate 280*7c478bd9Sstevel@tonic-gate void * 281*7c478bd9Sstevel@tonic-gate fmd_idspace_free(fmd_idspace_t *ids, id_t id) 282*7c478bd9Sstevel@tonic-gate { 283*7c478bd9Sstevel@tonic-gate fmd_idelem_t *ide, **pp; 284*7c478bd9Sstevel@tonic-gate void *data; 285*7c478bd9Sstevel@tonic-gate 286*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_lock(&ids->ids_lock); 287*7c478bd9Sstevel@tonic-gate pp = &ids->ids_hash[id & (ids->ids_hashlen - 1)]; 288*7c478bd9Sstevel@tonic-gate 289*7c478bd9Sstevel@tonic-gate for (ide = *pp; ide != NULL; ide = ide->ide_next) { 290*7c478bd9Sstevel@tonic-gate if (ide->ide_id != id) 291*7c478bd9Sstevel@tonic-gate pp = &ide->ide_next; 292*7c478bd9Sstevel@tonic-gate else 293*7c478bd9Sstevel@tonic-gate break; 294*7c478bd9Sstevel@tonic-gate } 295*7c478bd9Sstevel@tonic-gate 296*7c478bd9Sstevel@tonic-gate if (ide == NULL) { 297*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&ids->ids_lock); 298*7c478bd9Sstevel@tonic-gate return (NULL); 299*7c478bd9Sstevel@tonic-gate } 300*7c478bd9Sstevel@tonic-gate 301*7c478bd9Sstevel@tonic-gate data = ide->ide_data; 302*7c478bd9Sstevel@tonic-gate *pp = ide->ide_next; 303*7c478bd9Sstevel@tonic-gate fmd_free(ide, sizeof (fmd_idelem_t)); 304*7c478bd9Sstevel@tonic-gate 305*7c478bd9Sstevel@tonic-gate ASSERT(ids->ids_count != 0); 306*7c478bd9Sstevel@tonic-gate ids->ids_count--; 307*7c478bd9Sstevel@tonic-gate 308*7c478bd9Sstevel@tonic-gate (void) pthread_mutex_unlock(&ids->ids_lock); 309*7c478bd9Sstevel@tonic-gate return (data); 310*7c478bd9Sstevel@tonic-gate } 311