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> {
id_generatorid_generator46 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
~id_generatorid_generator55 ~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*
create_generator(const char * name)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
create_id_internal(id_generator * generator)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*
get_generator(const char * name)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
release_generator(id_generator * generator)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
dm_init_id_generator(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
dm_create_id(const char * name)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
dm_free_id(const char * name,uint32 id)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