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