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