1/* 2 * Copyright 2004-2008, Axel D��rfler, axeld@pinc-software.de. All rights reserved. 3 * Copyright 2002-2004, Thomas Kurschel. All rights reserved. 4 * 5 * Distributed under the terms of the MIT License. 6 */ 7 8/*! Generators are created on demand and deleted if all their 9 IDs are freed. They have a ref_count which is increased 10 whenever someone messes with the generator. 11 12 Whenever a generator is searched for, generator_lock is held. 13 14 To find out which ID are allocated, a bitmap is used that 15 contain up to GENERATOR_MAX_ID bits. This is a hard limit, 16 but it's simple to implement. If someone really needs lots of 17 IDs, we can still rewrite the code. For simplicity, we use 18 sGeneratorLock instead of a generator specific lock during 19 allocation; changing it is straightforward as everything 20 is prepared for that. 21*/ 22 23 24#include "id_generator.h" 25 26#include <new> 27#include <stdlib.h> 28#include <string.h> 29 30#include <KernelExport.h> 31 32#include <util/AutoLock.h> 33#include <util/DoublyLinkedList.h> 34 35 36//#define TRACE_ID_GENERATOR 37#ifdef TRACE_ID_GENERATOR 38# define TRACE(x) dprintf x 39#else 40# define TRACE(x) ; 41#endif 42 43#define GENERATOR_MAX_ID 64 44 45struct id_generator : DoublyLinkedListLinkImpl<id_generator> { 46 id_generator(const char* name) 47 : 48 ref_count(1), 49 name(strdup(name)), 50 num_ids(0) 51 { 52 memset(&alloc_map, 0, sizeof(alloc_map)); 53 } 54 55 ~id_generator() 56 { 57 free(name); 58 } 59 60 int32 ref_count; 61 char* name; 62 uint32 num_ids; 63 uint8 alloc_map[(GENERATOR_MAX_ID + 7) / 8]; 64}; 65 66typedef DoublyLinkedList<id_generator> GeneratorList; 67 68 69static GeneratorList sGenerators; 70static mutex sLock = MUTEX_INITIALIZER("id generator"); 71 72 73/*! Create new generator. 74 sLock must be held. 75*/ 76static id_generator* 77create_generator(const char* name) 78{ 79 TRACE(("create_generator(name: %s)\n", name)); 80 81 id_generator* generator = new(std::nothrow) id_generator(name); 82 if (generator == NULL) 83 return NULL; 84 85 if (generator->name == NULL) { 86 delete generator; 87 return NULL; 88 } 89 90 sGenerators.Add(generator); 91 return generator; 92} 93 94 95/*! Allocate ID */ 96static int32 97create_id_internal(id_generator* generator) 98{ 99 uint32 id; 100 101 TRACE(("create_id_internal(name: %s)\n", generator->name)); 102 103 // see above: we use global instead of local lock 104 MutexLocker _(sLock); 105 106 // simple bit search 107 for (id = 0; id < GENERATOR_MAX_ID; ++id) { 108 if ((generator->alloc_map[id / 8] & (1 << (id & 7))) == 0) { 109 TRACE((" id: %lu\n", id)); 110 111 generator->alloc_map[id / 8] |= 1 << (id & 7); 112 generator->num_ids++; 113 114 return id; 115 } 116 } 117 118 return B_ERROR; 119} 120 121 122/*! Gets a generator by name, and acquires a reference to it. 123 sLock must be held. 124*/ 125static id_generator* 126get_generator(const char* name) 127{ 128 TRACE(("find_generator(name: %s)\n", name)); 129 130 GeneratorList::Iterator iterator = sGenerators.GetIterator(); 131 while (iterator.HasNext()) { 132 id_generator* generator = iterator.Next(); 133 134 if (!strcmp(generator->name, name)) { 135 // increase ref_count, so it won't go away 136 generator->ref_count++; 137 return generator; 138 } 139 } 140 141 return NULL; 142} 143 144 145/*! Decrease ref_count, deleting generator if not used anymore */ 146static void 147release_generator(id_generator *generator) 148{ 149 TRACE(("release_generator(name: %s)\n", generator->name)); 150 151 MutexLocker _(sLock); 152 153 if (--generator->ref_count == 0) { 154 // no one messes with generator 155 if (generator->num_ids == 0) { 156 TRACE((" Destroy %s\n", generator->name)); 157 // no IDs is allocated - destroy generator 158 sGenerators.Remove(generator); 159 delete generator; 160 } 161 } 162} 163 164 165// #pragma mark - Private kernel API 166 167 168void 169dm_init_id_generator(void) 170{ 171 new(&sGenerators) GeneratorList; 172} 173 174 175// #pragma mark - Public module API 176 177 178/*! Create automatic ID */ 179int32 180dm_create_id(const char* name) 181{ 182 183 // find generator, create new if not there 184 mutex_lock(&sLock); 185 186 id_generator* generator = get_generator(name); 187 if (generator == NULL) 188 generator = create_generator(name); 189 190 mutex_unlock(&sLock); 191 192 if (generator == NULL) 193 return B_NO_MEMORY; 194 195 // get ID 196 int32 id = create_id_internal(generator); 197 198 release_generator(generator); 199 200 TRACE(("dm_create_id: name: %s, id: %ld\n", name, id)); 201 return id; 202} 203 204 205/*! Free automatically generated ID */ 206status_t 207dm_free_id(const char* name, uint32 id) 208{ 209 TRACE(("dm_free_id(name: %s, id: %ld)\n", name, id)); 210 211 // find generator 212 mutex_lock(&sLock); 213 214 id_generator* generator = get_generator(name); 215 216 mutex_unlock(&sLock); 217 218 if (generator == NULL) { 219 TRACE((" Generator %s doesn't exist\n", name)); 220 return B_NAME_NOT_FOUND; 221 } 222 223 // free ID 224 225 // make sure it's really allocated 226 // (very important to keep <num_ids> in sync 227 if ((generator->alloc_map[id / 8] & (1 << (id & 7))) == 0) { 228 dprintf("id %" B_PRIu32 " of generator %s wasn't allocated\n", id, 229 generator->name); 230 231 release_generator(generator); 232 return B_BAD_VALUE; 233 } 234 235 generator->alloc_map[id / 8] &= ~(1 << (id & 7)); 236 generator->num_ids--; 237 238 release_generator(generator); 239 return B_OK; 240} 241