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 2004 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 103 ids->ids_hash = fmd_zalloc(sizeof (void *) * hashlen, FMD_SLEEP); 104 ids->ids_hashlen = hashlen; 105 ids->ids_nextid = min - 1; 106 ids->ids_minid = min; 107 ids->ids_maxid = max; 108 ids->ids_count = 0; 109 110 return (ids); 111 } 112 113 void 114 fmd_idspace_destroy(fmd_idspace_t *ids) 115 { 116 fmd_idelem_t *ide, *nde; 117 uint_t i; 118 119 (void) pthread_mutex_lock(&ids->ids_lock); 120 121 for (i = 0; i < ids->ids_hashlen; i++) { 122 for (ide = ids->ids_hash[i]; ide != NULL; ide = nde) { 123 nde = ide->ide_next; 124 fmd_free(ide, sizeof (fmd_idelem_t)); 125 } 126 } 127 128 fmd_free(ids->ids_hash, sizeof (void *) * ids->ids_hashlen); 129 fmd_free(ids, sizeof (fmd_idspace_t)); 130 } 131 132 void 133 fmd_idspace_apply(fmd_idspace_t *ids, void (*func)(void *, id_t), void *arg) 134 { 135 fmd_idelem_t *ide; 136 id_t *ida, *idp; 137 uint_t i, count; 138 139 (void) pthread_mutex_lock(&ids->ids_lock); 140 count = ids->ids_count; 141 ida = idp = fmd_alloc(sizeof (id_t) * count, FMD_SLEEP); 142 143 for (i = 0; i < ids->ids_hashlen; i++) { 144 for (ide = ids->ids_hash[i]; ide != NULL; ide = ide->ide_next) 145 *idp++ = ide->ide_id; 146 } 147 148 ASSERT(idp == ida + count); 149 (void) pthread_mutex_unlock(&ids->ids_lock); 150 151 for (i = 0; i < count; i++) 152 func(arg, ida[i]); 153 154 fmd_free(ida, sizeof (id_t) * count); 155 } 156 157 static fmd_idelem_t * 158 fmd_idspace_lookup(fmd_idspace_t *ids, id_t id) 159 { 160 fmd_idelem_t *ide; 161 162 ASSERT(MUTEX_HELD(&ids->ids_lock)); 163 ide = ids->ids_hash[id & (ids->ids_hashlen - 1)]; 164 165 for (; ide != NULL; ide = ide->ide_next) { 166 if (ide->ide_id == id) 167 break; 168 } 169 170 return (ide); 171 } 172 173 void * 174 fmd_idspace_getspecific(fmd_idspace_t *ids, id_t id) 175 { 176 fmd_idelem_t *ide; 177 void *data; 178 179 (void) pthread_mutex_lock(&ids->ids_lock); 180 ide = fmd_idspace_lookup(ids, id); 181 data = ide ? ide->ide_data : NULL; 182 (void) pthread_mutex_unlock(&ids->ids_lock); 183 184 return (data); 185 } 186 187 void 188 fmd_idspace_setspecific(fmd_idspace_t *ids, id_t id, void *data) 189 { 190 fmd_idelem_t *ide; 191 192 (void) pthread_mutex_lock(&ids->ids_lock); 193 194 if ((ide = fmd_idspace_lookup(ids, id)) == NULL) { 195 fmd_panic("idspace %p (%s) does not contain id %ld", 196 (void *)ids, ids->ids_name, id); 197 } 198 199 ide->ide_data = data; 200 (void) pthread_mutex_unlock(&ids->ids_lock); 201 } 202 203 int 204 fmd_idspace_contains(fmd_idspace_t *ids, id_t id) 205 { 206 fmd_idelem_t *ide; 207 208 (void) pthread_mutex_lock(&ids->ids_lock); 209 ide = fmd_idspace_lookup(ids, id); 210 (void) pthread_mutex_unlock(&ids->ids_lock); 211 212 return (ide != NULL); 213 } 214 215 int 216 fmd_idspace_valid(fmd_idspace_t *ids, id_t id) 217 { 218 return (id >= ids->ids_minid && id <= ids->ids_maxid); 219 } 220 221 static id_t 222 fmd_idspace_xalloc_locked(fmd_idspace_t *ids, id_t id, void *data) 223 { 224 fmd_idelem_t *ide; 225 uint_t h; 226 227 if (id < ids->ids_minid || id > ids->ids_maxid) { 228 fmd_panic("%ld out of range [%ld .. %ld] for idspace %p (%s)\n", 229 id, ids->ids_minid, ids->ids_maxid, 230 (void *)ids, ids->ids_name); 231 } 232 233 if (fmd_idspace_lookup(ids, id) != NULL) 234 return (fmd_set_errno(EALREADY)); 235 236 ide = fmd_alloc(sizeof (fmd_idelem_t), FMD_SLEEP); 237 h = id & (ids->ids_hashlen - 1); 238 239 ide->ide_next = ids->ids_hash[h]; 240 ide->ide_data = data; 241 ide->ide_id = id; 242 243 ids->ids_hash[h] = ide; 244 ids->ids_count++; 245 246 return (id); 247 } 248 249 id_t 250 fmd_idspace_xalloc(fmd_idspace_t *ids, id_t id, void *data) 251 { 252 (void) pthread_mutex_lock(&ids->ids_lock); 253 id = fmd_idspace_xalloc_locked(ids, id, data); 254 (void) pthread_mutex_unlock(&ids->ids_lock); 255 return (id); 256 } 257 258 id_t 259 fmd_idspace_alloc(fmd_idspace_t *ids, void *data) 260 { 261 id_t id; 262 263 (void) pthread_mutex_lock(&ids->ids_lock); 264 265 if (ids->ids_count == ids->ids_maxid - ids->ids_minid + 1) { 266 (void) pthread_mutex_unlock(&ids->ids_lock); 267 return (fmd_set_errno(ENOSPC)); 268 } 269 270 do { 271 if (++ids->ids_nextid > ids->ids_maxid) 272 ids->ids_nextid = ids->ids_minid; 273 id = ids->ids_nextid; 274 } while (fmd_idspace_xalloc_locked(ids, id, data) != id); 275 276 (void) pthread_mutex_unlock(&ids->ids_lock); 277 return (id); 278 } 279 280 void * 281 fmd_idspace_free(fmd_idspace_t *ids, id_t id) 282 { 283 fmd_idelem_t *ide, **pp; 284 void *data; 285 286 (void) pthread_mutex_lock(&ids->ids_lock); 287 pp = &ids->ids_hash[id & (ids->ids_hashlen - 1)]; 288 289 for (ide = *pp; ide != NULL; ide = ide->ide_next) { 290 if (ide->ide_id != id) 291 pp = &ide->ide_next; 292 else 293 break; 294 } 295 296 if (ide == NULL) { 297 (void) pthread_mutex_unlock(&ids->ids_lock); 298 return (NULL); 299 } 300 301 data = ide->ide_data; 302 *pp = ide->ide_next; 303 fmd_free(ide, sizeof (fmd_idelem_t)); 304 305 ASSERT(ids->ids_count != 0); 306 ids->ids_count--; 307 308 (void) pthread_mutex_unlock(&ids->ids_lock); 309 return (data); 310 } 311