1/*******************************************************************************
2/
3/	File:			atomizer.c
4/
5/	Description:	Kernel module implementing kernel-space atomizer API
6/
7/	Copyright 1999, Be Incorporated, All Rights Reserved.
8/	This file may be used under the terms of the Be Sample Code License.
9/
10*******************************************************************************/
11
12#include <Drivers.h>
13#include <KernelExport.h>
14#include <string.h>
15#include <stdlib.h>
16
17#include <atomizer.h>
18
19
20#if DEBUG > 0
21#define ddprintf(x) dprintf x
22#else
23#define ddprintf(x)
24#endif
25
26typedef struct {
27	sem_id	sem;
28	int32	ben;
29} benaphore;
30
31#define INIT_BEN(x)		x.sem = create_sem(0, "an atomizer benaphore");  x.ben = 0;
32#define ACQUIRE_BEN(x)	if((atomic_add(&(x.ben), 1)) >= 1) acquire_sem(x.sem);
33#define ACQUIRE_BEN_ON_ERROR(x, y) if((atomic_add(&(x.ben), 1)) >= 1) if (acquire_sem(x.sem) != B_OK) y;
34#define RELEASE_BEN(x)	if((atomic_add(&(x.ben), -1)) > 1) release_sem(x.sem);
35#define	DELETE_BEN(x)	delete_sem(x.sem); x.sem = -1; x.ben = 1;
36
37#define MIN_BLOCK_SIZE B_PAGE_SIZE
38
39typedef struct block_list block_list;
40
41struct block_list{
42	block_list	*next;
43	uint8		*free_space;
44	uint32		free_bytes;
45};
46
47typedef struct {
48	benaphore	lock;		/* serializes access to this atomizer */
49	block_list	*blocks;	/* list of blocks holding atomized strings */
50	uint32		count;		/* number of atoms in this list */
51	uint32		slots;		/* total number of spaces in the allocated vector */
52	uint8		**vector;	/* sorted vector of pointers to atomized strings */
53} atomizer_data;
54
55typedef struct atomizer_data_list atomizer_data_list;
56
57struct atomizer_data_list {
58	char				*name;	/* the atomizer's name */
59	atomizer_data		*the_atomizer;	/* the atomizer data */
60	atomizer_data_list	*next;	/* the next atomizer in the list */
61};
62
63
64/* Module static data */
65const char atomizer_module_name[] = B_ATOMIZER_MODULE_NAME;
66const char system_atomizer_name[] = B_SYSTEM_ATOMIZER_NAME;
67
68static benaphore module_lock;
69static atomizer_data_list *atomizer_list;
70
71static atomizer_data *
72make_atomizer(void) {
73	atomizer_data *ad;
74
75	/* get space for atomizer data */
76	ad = (atomizer_data *)malloc(sizeof(atomizer_data));
77	if (ad) {
78		/* init locks */
79		INIT_BEN(ad->lock);
80		if (ad->lock.sem >= 0) {
81			/* get first block for atomized strings */
82			ad->blocks = (block_list *)malloc(MIN_BLOCK_SIZE);
83			if (ad->blocks) {
84				/* get vector for pointers to strings */
85				ad->vector = (uint8 **)malloc(MIN_BLOCK_SIZE);
86				if (ad->vector) {
87					/* fill in the details */
88					ad->blocks->next = 0;
89					ad->blocks->free_space = ((uint8 *)ad->blocks)+sizeof(block_list);
90					ad->blocks->free_bytes = MIN_BLOCK_SIZE - sizeof(block_list);
91					ad->count = 0;
92					ad->slots = MIN_BLOCK_SIZE / sizeof(uint8 *);
93					goto exit0;
94				}
95				/* oops, vector allocation failed */
96				free(ad->blocks);
97			}
98			/* oops, block list allocation failed */
99			DELETE_BEN(ad->lock);
100		}
101		/* oops, sem creation failed */
102		free(ad);
103		ad = 0;
104	}
105exit0:
106	ddprintf(("make_atomizer() returns %p\n", ad));
107	return ad;
108}
109
110static void
111free_atomizer(atomizer_data *ad) {
112	block_list *bl, *blnext;
113
114	/* Acquire the lock or fail trying.  Better to not free
115	the data than corrupt the kernel heap */
116	ACQUIRE_BEN_ON_ERROR(ad->lock, return);
117	/* walk the block_list, freeing them up */
118	bl = ad->blocks;
119	while (bl) {
120		blnext = bl->next;
121		free(bl);
122		bl = blnext;
123	}
124	/* release vector of pointers to atomized strings */
125	free(ad->vector);
126	/* delete the benaphore */
127	DELETE_BEN(ad->lock);
128	/* finaly, release the atomizer data */
129	free(ad);
130}
131
132static const void *
133find_or_make_atomizer(const char *string) {
134	atomizer_data_list *adl = atomizer_list;
135	atomizer_data_list *last = 0;
136	void * at = (void *)0;
137
138	/* null or zero-length string means system atomizer */
139	if (!string || (strlen(string) == 0)) string = system_atomizer_name;
140
141	/* lock the atomizer list or fail returning a bogus atomizer */
142	ACQUIRE_BEN_ON_ERROR(module_lock, return at);
143	ddprintf(("success locking module\n"));
144	while (adl && strcmp(adl->name, string)) {
145		last = adl;
146		adl = adl->next;
147	}
148	if (adl) {
149		at = (void *)adl->the_atomizer;
150		ddprintf(("asked for %s, returning %p\n", string, at));
151		goto exit0;
152	}
153	ddprintf(("didn't find atomizer %s, making it\n", string));
154
155	adl = (atomizer_data_list *)malloc(sizeof(atomizer_data_list));
156	if (adl) {
157		adl->the_atomizer = make_atomizer();
158		if (adl->the_atomizer) {
159			adl->name = strdup(string);
160			if (adl->name) {
161				/* append to list */
162				if (last) last->next = adl;
163				else atomizer_list = adl;
164				adl->next = 0;
165				at = (void *)adl->the_atomizer;
166				goto exit0;
167			}
168			free_atomizer(adl->the_atomizer);
169		}
170		free(adl);
171	}
172exit0:
173	RELEASE_BEN(module_lock);
174	ddprintf(("find_or_make_atomizer() returning %p\n", at));
175	return at;
176}
177
178static status_t
179init()
180{
181	ddprintf((B_ATOMIZER_MODULE_NAME": init()\n"));
182	/* init the module-wide benaphore */
183	INIT_BEN(module_lock);
184	if (module_lock.sem >= 0) {
185		/* create list of atomizers */
186		atomizer_list = 0;
187		if (find_or_make_atomizer(0))
188			return B_OK;
189		/* oops, couldn't create system atomizer */
190		DELETE_BEN(module_lock);
191		module_lock.sem = B_ERROR;
192	}
193	return module_lock.sem;
194}
195
196static status_t
197uninit()
198{
199	atomizer_data_list *adl;
200	/* aquire the module-wide lock.  This is pure paranoia.
201	If it fails, all hell as broken loose, but we won't contribute
202	by corrupting the heap. */
203	ddprintf((B_ATOMIZER_MODULE_NAME": uninit()\n"));
204	ACQUIRE_BEN_ON_ERROR(module_lock, return B_ERROR);
205	if (atomizer_list->next) {
206		ddprintf((B_ATOMIZER_MODULE_NAME": uninit called with non-system atomizers still active!\n"));
207	}
208	/* delete all of the atomizers.  Ideally, there should only
209	be the system atomizer left */
210	adl = atomizer_list;
211	while (adl) {
212		free_atomizer(adl->the_atomizer);
213		free(adl->name);
214		adl = adl->next;
215	}
216	/* free up the module-wide benaphore */
217	DELETE_BEN(module_lock);
218	return B_OK;
219}
220
221static status_t
222std_ops(int32 op, ...)
223{
224	switch(op) {
225	case B_MODULE_INIT:
226		return init();
227	case B_MODULE_UNINIT:
228		return uninit();
229	default:
230		/* do nothing */
231		;
232	}
233	return -1;
234}
235
236static status_t
237delete_atomizer(const void * at) {
238	atomizer_data_list *adl;
239	atomizer_data_list *last = 0;
240	status_t result = B_ERROR;
241
242	ACQUIRE_BEN_ON_ERROR(module_lock, return B_ERROR);
243	adl = atomizer_list;
244	while (adl && (adl->the_atomizer != (atomizer_data *)at)) {
245		last = adl;
246		adl = adl->next;
247	}
248
249	if (adl) {
250		/* don't let clients delete the system atomizer */
251		if (strcmp(adl->name, system_atomizer_name) != 0) {
252			free_atomizer(adl->the_atomizer);
253			free(adl->name);
254			/* the system atomizer is always first, so last will be non-zero */
255			last->next = adl->next;
256			free(adl);
257			result = B_OK;
258		}
259	}
260	RELEASE_BEN(module_lock);
261	return result;
262}
263
264static const void *
265atomize(const void * at, const char *string, int create) {
266	atomizer_data_list *adl;
267	void *result = 0;
268	uint32	len;
269
270	/* NULL and zero length strings aren't interned */
271	if (!string || !(len = strlen(string))) return 0;
272	/* include the null terminator */
273	len++;
274	/* own the list or fail trying */
275	ACQUIRE_BEN_ON_ERROR(module_lock, return 0);
276
277	/* use the system atomizer if none specified */
278	if (at == ((void *)(-1))) at = atomizer_list->the_atomizer;
279
280	/* walk the list of known atomizers, looking for a match */
281	adl = atomizer_list;
282	while (adl && (adl->the_atomizer != (atomizer_data *)at)) {
283		adl = adl->next;
284	}
285	/* lock the atomizer *before* we give up control over the list */
286	if (adl) ACQUIRE_BEN(adl->the_atomizer->lock);
287	/* allow list manipulations */
288	RELEASE_BEN(module_lock);
289	/* did we find the one we wanted? */
290	if (adl) {
291		atomizer_data *ad = adl->the_atomizer;
292		uint8 **vector = ad->vector;
293		uint32 count = ad->count;
294		uint32 low = 0;
295		uint32 high = count;
296		uint32 index = 0;
297		int test = -1;
298		/* do a binary search on the vector for a match */
299		while (low < high) {
300			index = (low + high) / 2;
301			test = strcmp(string, (const char *)vector[index]);
302			if (test < 0)
303				high = index;
304			else if (test > 0)
305				low = ++index;	// if we exit the while loop here, use index + 1
306			else
307				break;
308		}
309		/* if match found, note result and return it */
310		if (test == 0) {
311			result = vector[index];
312		} else {
313			/* if we're not "just checking" */
314			if (create) {
315				/* no match, so add to list */
316				/* find first block with enough room */
317				block_list *bl = ad->blocks;
318				while (bl->next) {
319					if (bl->free_bytes >= len) break;
320					bl = bl->next;
321				}
322				if (bl->free_bytes < len) {
323					/* allocate a block big enough to handle the string */
324					size_t block_size = ((sizeof(block_list)+len+(MIN_BLOCK_SIZE-1)) & ~(MIN_BLOCK_SIZE-1));
325					bl->next = (block_list *)malloc(block_size);
326					if (!bl->next) {
327						RELEASE_BEN(ad->lock);
328						return 0;
329					}
330					bl = bl->next;
331					bl->free_space = (uint8 *)(bl+1);
332					bl->free_bytes = block_size - sizeof(block_list);
333				}
334				/* actually intern an atom */
335				result = bl->free_space;
336				memcpy(result, string, len);
337				bl->free_space += len;
338				bl->free_bytes -= len;
339
340				/* insert the pointer in the vector */
341				/* if the vector isn't big enough, realloc it */
342				if (ad->count == ad->slots) {
343					size_t newslots = ad->slots + (MIN_BLOCK_SIZE / sizeof(uint8 *));
344					uint8 **newvec = realloc(vector, newslots * sizeof(uint8 *));
345					if (!newvec) {
346						/* bail, leaving the atom un-interned */
347						RELEASE_BEN(ad->lock);
348						return 0;
349					}
350					ad->slots = newslots;
351					vector = ad->vector = newvec;
352				}
353				/* move all of the entries starting at index down one slot */
354				memmove(vector + index + 1, vector + index, (count - index) * sizeof(uint8 *));
355				/* insert the new pointer in the vector */
356				vector[index] = result;
357				/* note new count */
358				ad->count++;
359			}
360		}
361		RELEASE_BEN(ad->lock);
362	}
363	return result;
364}
365
366static const char *
367string_for_token(const void *atomizer, const void *atom) {
368	/* someday, check for validity */
369	return atom;
370}
371
372static status_t
373get_next_atomizer_info(void **cookie, atomizer_info *info) {
374	atomizer_data_list *adl;
375	atomizer_data_list *atomizer = (atomizer_data_list *)*cookie;
376	status_t result = B_ERROR;
377
378	ddprintf(("get_next_atomizer_info(cookie: %p, info: %p)\n", *cookie, info));
379	/* a NULL info pointer? */
380	if (!info) return result;
381
382	ACQUIRE_BEN_ON_ERROR(module_lock, return result);
383	/* null? start over */
384	if (!atomizer) atomizer = atomizer_list;
385	adl = atomizer_list;
386	while (adl && (adl != atomizer))
387		adl = adl->next;
388	if (adl) {
389		*cookie = atomizer->next;
390		/* use a bogus cookie if no more left */
391		if (!*cookie) *cookie = (void *)-1;
392		info->atomizer = atomizer->the_atomizer;
393		strncpy(info->name, adl->name, B_OS_NAME_LENGTH);
394		info->name[B_OS_NAME_LENGTH - 1] = '\0';
395		info->atom_count = atomizer->the_atomizer->count;
396		result = B_OK;
397	}
398	RELEASE_BEN(module_lock);
399	return result;
400}
401
402static const void *
403get_next_atom(const void *_atomizer, uint32 *cookie) {
404	atomizer_data_list *adl;
405	atomizer_data *atomizer = (atomizer_data *)_atomizer;
406	void *result = 0;
407
408	/* validate the atomizer */
409	ACQUIRE_BEN_ON_ERROR(module_lock, return 0);
410	adl = atomizer_list;
411	while (adl && (adl->the_atomizer != atomizer))
412		adl = adl->next;
413	/* lock the atomizer *before* we give up control over the list */
414	if (adl) ACQUIRE_BEN(atomizer->lock);
415	/* allow list manipulations */
416	RELEASE_BEN(module_lock);
417	if (adl) {
418		if (*cookie < atomizer->count) {
419			result = atomizer->vector[*cookie];
420			(*cookie)++;
421		}
422		RELEASE_BEN(atomizer->lock);
423	}
424	return result;
425}
426
427static atomizer_module_info atomizer = {
428	{
429		atomizer_module_name,
430		0,
431		std_ops
432	},
433	find_or_make_atomizer,
434	delete_atomizer,
435	atomize,
436	string_for_token,
437	get_next_atomizer_info,
438	get_next_atom
439};
440
441_EXPORT atomizer_module_info *modules[] = {
442        &atomizer,
443        NULL
444};
445
446