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 45 struct 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 66 typedef DoublyLinkedList<id_generator> GeneratorList; 67 68 69 static GeneratorList sGenerators; 70 static mutex sLock = MUTEX_INITIALIZER("id generator"); 71 72 73 /*! Create new generator. 74 sLock must be held. 75 */ 76 static id_generator* 77 create_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 */ 96 static int32 97 create_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 */ 125 static id_generator* 126 get_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 */ 146 static void 147 release_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 168 void 169 dm_init_id_generator(void) 170 { 171 new(&sGenerators) GeneratorList; 172 } 173 174 175 // #pragma mark - Public module API 176 177 178 /*! Create automatic ID */ 179 int32 180 dm_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 */ 206 status_t 207 dm_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