1/* 2 * Copyright (c) 2000-2007 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28/* IOSymbol.cpp created by gvdl on Fri 1998-11-17 */ 29 30#include <string.h> 31#include <sys/cdefs.h> 32 33__BEGIN_DECLS 34#include <kern/lock.h> 35__END_DECLS 36 37#include <libkern/c++/OSSymbol.h> 38#include <libkern/c++/OSLib.h> 39#include <string.h> 40 41#define super OSString 42 43typedef struct { int i, j; } OSSymbolPoolState; 44 45#if OSALLOCDEBUG 46extern "C" { 47 extern int debug_container_malloc_size; 48}; 49#define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0) 50#else 51#define ACCUMSIZE(s) 52#endif 53 54#define INITIAL_POOL_SIZE (exp2ml(1 + log2(kInitBucketCount))) 55 56#define GROW_FACTOR (1) 57#define SHRINK_FACTOR (3) 58 59#define GROW_POOL() do \ 60 if (count * GROW_FACTOR > nBuckets) { \ 61 reconstructSymbols(true); \ 62 } \ 63while (0) 64 65#define SHRINK_POOL() do \ 66 if (count * SHRINK_FACTOR < nBuckets && \ 67 nBuckets > INITIAL_POOL_SIZE) { \ 68 reconstructSymbols(false); \ 69 } \ 70while (0) 71 72class OSSymbolPool 73{ 74private: 75 static const unsigned int kInitBucketCount = 16; 76 77 typedef struct { unsigned int count; OSSymbol **symbolP; } Bucket; 78 79 Bucket *buckets; 80 unsigned int nBuckets; 81 unsigned int count; 82 lck_mtx_t *poolGate; 83 84 static inline void hashSymbol(const char *s, 85 unsigned int *hashP, 86 unsigned int *lenP) 87 { 88 unsigned int hash = 0; 89 unsigned int len = 0; 90 91 /* Unroll the loop. */ 92 for (;;) { 93 if (!*s) break; len++; hash ^= *s++; 94 if (!*s) break; len++; hash ^= *s++ << 8; 95 if (!*s) break; len++; hash ^= *s++ << 16; 96 if (!*s) break; len++; hash ^= *s++ << 24; 97 } 98 *lenP = len; 99 *hashP = hash; 100 } 101 102 static unsigned long log2(unsigned int x); 103 static unsigned long exp2ml(unsigned int x); 104 105 void reconstructSymbols(void); 106 void reconstructSymbols(bool grow); 107 108public: 109 static void *operator new(size_t size); 110 static void operator delete(void *mem, size_t size); 111 112 OSSymbolPool() { }; 113 OSSymbolPool(const OSSymbolPool *old); 114 virtual ~OSSymbolPool(); 115 116 bool init(); 117 118 inline void closeGate() { lck_mtx_lock(poolGate); }; 119 inline void openGate() { lck_mtx_unlock(poolGate); }; 120 121 OSSymbol *findSymbol(const char *cString) const; 122 OSSymbol *insertSymbol(OSSymbol *sym); 123 void removeSymbol(OSSymbol *sym); 124 125 OSSymbolPoolState initHashState(); 126 OSSymbol *nextHashState(OSSymbolPoolState *stateP); 127}; 128 129void * OSSymbolPool::operator new(size_t size) 130{ 131 void *mem = (void *)kalloc(size); 132 ACCUMSIZE(size); 133 assert(mem); 134 bzero(mem, size); 135 136 return mem; 137} 138 139void OSSymbolPool::operator delete(void *mem, size_t size) 140{ 141 kfree(mem, size); 142 ACCUMSIZE(-size); 143} 144 145extern lck_grp_t *IOLockGroup; 146 147bool OSSymbolPool::init() 148{ 149 count = 0; 150 nBuckets = INITIAL_POOL_SIZE; 151 buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket)); 152 ACCUMSIZE(nBuckets * sizeof(Bucket)); 153 if (!buckets) 154 return false; 155 156 bzero(buckets, nBuckets * sizeof(Bucket)); 157 158 poolGate = lck_mtx_alloc_init(IOLockGroup, LCK_ATTR_NULL); 159 160 return poolGate != 0; 161} 162 163OSSymbolPool::OSSymbolPool(const OSSymbolPool *old) 164{ 165 count = old->count; 166 nBuckets = old->nBuckets; 167 buckets = old->buckets; 168 169 poolGate = 0; // Do not duplicate the poolGate 170} 171 172OSSymbolPool::~OSSymbolPool() 173{ 174 if (buckets) { 175 kfree(buckets, nBuckets * sizeof(Bucket)); 176 ACCUMSIZE(-(nBuckets * sizeof(Bucket))); 177 } 178 179 if (poolGate) 180 lck_mtx_free(poolGate, IOLockGroup); 181} 182 183unsigned long OSSymbolPool::log2(unsigned int x) 184{ 185 unsigned long i; 186 187 for (i = 0; x > 1 ; i++) 188 x >>= 1; 189 return i; 190} 191 192unsigned long OSSymbolPool::exp2ml(unsigned int x) 193{ 194 return (1 << x) - 1; 195} 196 197OSSymbolPoolState OSSymbolPool::initHashState() 198{ 199 OSSymbolPoolState newState = { nBuckets, 0 }; 200 return newState; 201} 202 203OSSymbol *OSSymbolPool::nextHashState(OSSymbolPoolState *stateP) 204{ 205 Bucket *thisBucket = &buckets[stateP->i]; 206 207 while (!stateP->j) { 208 if (!stateP->i) 209 return 0; 210 stateP->i--; 211 thisBucket--; 212 stateP->j = thisBucket->count; 213 } 214 215 stateP->j--; 216 if (thisBucket->count == 1) 217 return (OSSymbol *) thisBucket->symbolP; 218 else 219 return thisBucket->symbolP[stateP->j]; 220} 221 222void OSSymbolPool::reconstructSymbols(void) 223{ 224 this->reconstructSymbols(true); 225} 226 227void OSSymbolPool::reconstructSymbols(bool grow) 228{ 229 unsigned int new_nBuckets = nBuckets; 230 OSSymbol *insert; 231 OSSymbolPoolState state; 232 233 if (grow) { 234 new_nBuckets += new_nBuckets + 1; 235 } else { 236 /* Don't shrink the pool below the default initial size. 237 */ 238 if (nBuckets <= INITIAL_POOL_SIZE) { 239 return; 240 } 241 new_nBuckets = (new_nBuckets - 1) / 2; 242 } 243 244 /* Create old pool to iterate after doing above check, cause it 245 * gets finalized at return. 246 */ 247 OSSymbolPool old(this); 248 249 count = 0; 250 nBuckets = new_nBuckets; 251 buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket)); 252 ACCUMSIZE(nBuckets * sizeof(Bucket)); 253 /* @@@ gvdl: Zero test and panic if can't set up pool */ 254 bzero(buckets, nBuckets * sizeof(Bucket)); 255 256 state = old.initHashState(); 257 while ( (insert = old.nextHashState(&state)) ) 258 insertSymbol(insert); 259} 260 261OSSymbol *OSSymbolPool::findSymbol(const char *cString) const 262{ 263 Bucket *thisBucket; 264 unsigned int j, inLen, hash; 265 OSSymbol *probeSymbol, **list; 266 267 hashSymbol(cString, &hash, &inLen); inLen++; 268 thisBucket = &buckets[hash % nBuckets]; 269 j = thisBucket->count; 270 271 if (!j) 272 return 0; 273 274 if (j == 1) { 275 probeSymbol = (OSSymbol *) thisBucket->symbolP; 276 277 if (inLen == probeSymbol->length 278 && (strncmp(probeSymbol->string, cString, probeSymbol->length) == 0)) 279 return probeSymbol; 280 return 0; 281 } 282 283 for (list = thisBucket->symbolP; j--; list++) { 284 probeSymbol = *list; 285 if (inLen == probeSymbol->length 286 && (strncmp(probeSymbol->string, cString, probeSymbol->length) == 0)) 287 return probeSymbol; 288 } 289 290 return 0; 291} 292 293OSSymbol *OSSymbolPool::insertSymbol(OSSymbol *sym) 294{ 295 const char *cString = sym->string; 296 Bucket *thisBucket; 297 unsigned int j, inLen, hash; 298 OSSymbol *probeSymbol, **list; 299 300 hashSymbol(cString, &hash, &inLen); inLen++; 301 thisBucket = &buckets[hash % nBuckets]; 302 j = thisBucket->count; 303 304 if (!j) { 305 thisBucket->symbolP = (OSSymbol **) sym; 306 thisBucket->count++; 307 count++; 308 return sym; 309 } 310 311 if (j == 1) { 312 probeSymbol = (OSSymbol *) thisBucket->symbolP; 313 314 if (inLen == probeSymbol->length 315 && strncmp(probeSymbol->string, cString, probeSymbol->length) == 0) 316 return probeSymbol; 317 318 list = (OSSymbol **) kalloc(2 * sizeof(OSSymbol *)); 319 ACCUMSIZE(2 * sizeof(OSSymbol *)); 320 /* @@@ gvdl: Zero test and panic if can't set up pool */ 321 list[0] = sym; 322 list[1] = probeSymbol; 323 thisBucket->symbolP = list; 324 thisBucket->count++; 325 count++; 326 GROW_POOL(); 327 328 return sym; 329 } 330 331 for (list = thisBucket->symbolP; j--; list++) { 332 probeSymbol = *list; 333 if (inLen == probeSymbol->length 334 && strncmp(probeSymbol->string, cString, probeSymbol->length) == 0) 335 return probeSymbol; 336 } 337 338 j = thisBucket->count++; 339 count++; 340 list = (OSSymbol **) kalloc(thisBucket->count * sizeof(OSSymbol *)); 341 ACCUMSIZE(thisBucket->count * sizeof(OSSymbol *)); 342 /* @@@ gvdl: Zero test and panic if can't set up pool */ 343 list[0] = sym; 344 bcopy(thisBucket->symbolP, list + 1, j * sizeof(OSSymbol *)); 345 kfree(thisBucket->symbolP, j * sizeof(OSSymbol *)); 346 ACCUMSIZE(-(j * sizeof(OSSymbol *))); 347 thisBucket->symbolP = list; 348 GROW_POOL(); 349 350 return sym; 351} 352 353void OSSymbolPool::removeSymbol(OSSymbol *sym) 354{ 355 Bucket *thisBucket; 356 unsigned int j, inLen, hash; 357 OSSymbol *probeSymbol, **list; 358 359 hashSymbol(sym->string, &hash, &inLen); inLen++; 360 thisBucket = &buckets[hash % nBuckets]; 361 j = thisBucket->count; 362 list = thisBucket->symbolP; 363 364 if (!j) { 365 // couldn't find the symbol; probably means string hash changed 366 panic("removeSymbol"); 367 return; 368 } 369 370 if (j == 1) { 371 probeSymbol = (OSSymbol *) list; 372 373 if (probeSymbol == sym) { 374 thisBucket->symbolP = 0; 375 count--; 376 thisBucket->count--; 377 SHRINK_POOL(); 378 return; 379 } 380 // couldn't find the symbol; probably means string hash changed 381 panic("removeSymbol"); 382 return; 383 } 384 385 if (j == 2) { 386 probeSymbol = list[0]; 387 if (probeSymbol == sym) { 388 thisBucket->symbolP = (OSSymbol **) list[1]; 389 kfree(list, 2 * sizeof(OSSymbol *)); 390 ACCUMSIZE(-(2 * sizeof(OSSymbol *))); 391 count--; 392 thisBucket->count--; 393 SHRINK_POOL(); 394 return; 395 } 396 397 probeSymbol = list[1]; 398 if (probeSymbol == sym) { 399 thisBucket->symbolP = (OSSymbol **) list[0]; 400 kfree(list, 2 * sizeof(OSSymbol *)); 401 ACCUMSIZE(-(2 * sizeof(OSSymbol *))); 402 count--; 403 thisBucket->count--; 404 SHRINK_POOL(); 405 return; 406 } 407 // couldn't find the symbol; probably means string hash changed 408 panic("removeSymbol"); 409 return; 410 } 411 412 for (; j--; list++) { 413 probeSymbol = *list; 414 if (probeSymbol == sym) { 415 416 list = (OSSymbol **) 417 kalloc((thisBucket->count-1) * sizeof(OSSymbol *)); 418 ACCUMSIZE((thisBucket->count-1) * sizeof(OSSymbol *)); 419 if (thisBucket->count-1 != j) 420 bcopy(thisBucket->symbolP, list, 421 (thisBucket->count-1-j) * sizeof(OSSymbol *)); 422 if (j) 423 bcopy(thisBucket->symbolP + thisBucket->count-j, 424 list + thisBucket->count-1-j, 425 j * sizeof(OSSymbol *)); 426 kfree(thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *)); 427 ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *))); 428 thisBucket->symbolP = list; 429 count--; 430 thisBucket->count--; 431 return; 432 } 433 } 434 // couldn't find the symbol; probably means string hash changed 435 panic("removeSymbol"); 436} 437 438/* 439 ********************************************************************* 440 * From here on we are actually implementing the OSSymbol class 441 ********************************************************************* 442 */ 443OSDefineMetaClassAndStructorsWithInit(OSSymbol, OSString, 444 OSSymbol::initialize()) 445OSMetaClassDefineReservedUnused(OSSymbol, 0); 446OSMetaClassDefineReservedUnused(OSSymbol, 1); 447OSMetaClassDefineReservedUnused(OSSymbol, 2); 448OSMetaClassDefineReservedUnused(OSSymbol, 3); 449OSMetaClassDefineReservedUnused(OSSymbol, 4); 450OSMetaClassDefineReservedUnused(OSSymbol, 5); 451OSMetaClassDefineReservedUnused(OSSymbol, 6); 452OSMetaClassDefineReservedUnused(OSSymbol, 7); 453 454static OSSymbolPool *pool; 455 456void OSSymbol::initialize() 457{ 458 pool = new OSSymbolPool; 459 assert(pool); 460 461 if (!pool->init()) { 462 delete pool; 463 assert(false); 464 }; 465} 466 467bool OSSymbol::initWithCStringNoCopy(const char *) { return false; } 468bool OSSymbol::initWithCString(const char *) { return false; } 469bool OSSymbol::initWithString(const OSString *) { return false; } 470 471const OSSymbol *OSSymbol::withString(const OSString *aString) 472{ 473 // This string may be a OSSymbol already, cheap check. 474 if (OSDynamicCast(OSSymbol, aString)) { 475 aString->retain(); 476 return (const OSSymbol *) aString; 477 } 478 else if (((const OSSymbol *) aString)->flags & kOSStringNoCopy) 479 return OSSymbol::withCStringNoCopy(aString->getCStringNoCopy()); 480 else 481 return OSSymbol::withCString(aString->getCStringNoCopy()); 482} 483 484const OSSymbol *OSSymbol::withCString(const char *cString) 485{ 486 pool->closeGate(); 487 488 OSSymbol *oldSymb = pool->findSymbol(cString); 489 if (!oldSymb) { 490 OSSymbol *newSymb = new OSSymbol; 491 if (!newSymb) { 492 pool->openGate(); 493 return newSymb; 494 } 495 496 if (newSymb->OSString::initWithCString(cString)) 497 oldSymb = pool->insertSymbol(newSymb); 498 499 if (newSymb == oldSymb) { 500 pool->openGate(); 501 return newSymb; // return the newly created & inserted symbol. 502 } 503 else 504 // Somebody else inserted the new symbol so free our copy 505 newSymb->OSString::free(); 506 } 507 508 oldSymb->retain(); // Retain the old symbol before releasing the lock. 509 510 pool->openGate(); 511 return oldSymb; 512} 513 514const OSSymbol *OSSymbol::withCStringNoCopy(const char *cString) 515{ 516 pool->closeGate(); 517 518 OSSymbol *oldSymb = pool->findSymbol(cString); 519 if (!oldSymb) { 520 OSSymbol *newSymb = new OSSymbol; 521 if (!newSymb) { 522 pool->openGate(); 523 return newSymb; 524 } 525 526 if (newSymb->OSString::initWithCStringNoCopy(cString)) 527 oldSymb = pool->insertSymbol(newSymb); 528 529 if (newSymb == oldSymb) { 530 pool->openGate(); 531 return newSymb; // return the newly created & inserted symbol. 532 } 533 else 534 // Somebody else inserted the new symbol so free our copy 535 newSymb->OSString::free(); 536 } 537 538 oldSymb->retain(); // Retain the old symbol before releasing the lock. 539 540 pool->openGate(); 541 return oldSymb; 542} 543 544void OSSymbol::checkForPageUnload(void *startAddr, void *endAddr) 545{ 546 OSSymbol *probeSymbol; 547 OSSymbolPoolState state; 548 549 pool->closeGate(); 550 state = pool->initHashState(); 551 while ( (probeSymbol = pool->nextHashState(&state)) ) { 552 if (probeSymbol->string >= startAddr && probeSymbol->string < endAddr) { 553 const char *oldString = probeSymbol->string; 554 555 probeSymbol->string = (char *) kalloc(probeSymbol->length); 556 ACCUMSIZE(probeSymbol->length); 557 bcopy(oldString, probeSymbol->string, probeSymbol->length); 558 probeSymbol->flags &= ~kOSStringNoCopy; 559 } 560 } 561 pool->openGate(); 562} 563 564void OSSymbol::taggedRelease(const void *tag) const 565{ 566 super::taggedRelease(tag); 567} 568 569void OSSymbol::taggedRelease(const void *tag, const int when) const 570{ 571 pool->closeGate(); 572 super::taggedRelease(tag, when); 573 pool->openGate(); 574} 575 576void OSSymbol::free() 577{ 578 pool->removeSymbol(this); 579 super::free(); 580} 581 582bool OSSymbol::isEqualTo(const char *aCString) const 583{ 584 return super::isEqualTo(aCString); 585} 586 587bool OSSymbol::isEqualTo(const OSSymbol *aSymbol) const 588{ 589 return aSymbol == this; 590} 591 592bool OSSymbol::isEqualTo(const OSMetaClassBase *obj) const 593{ 594 OSSymbol * sym; 595 OSString * str; 596 597 if ((sym = OSDynamicCast(OSSymbol, obj))) 598 return isEqualTo(sym); 599 else if ((str = OSDynamicCast(OSString, obj))) 600 return super::isEqualTo(str); 601 else 602 return false; 603} 604 605unsigned int 606OSSymbol::bsearch( 607 const void * key, 608 const void * array, 609 unsigned int arrayCount, 610 size_t memberSize) 611{ 612 const void **p; 613 unsigned int baseIdx = 0; 614 unsigned int lim; 615 616 for (lim = arrayCount; lim; lim >>= 1) 617 { 618 p = (typeof(p)) (((uintptr_t) array) + (baseIdx + (lim >> 1)) * memberSize); 619 if (key == *p) 620 { 621 return (baseIdx + (lim >> 1)); 622 } 623 if (key > *p) 624 { 625 // move right 626 baseIdx += (lim >> 1) + 1; 627 lim--; 628 } 629 // else move left 630 } 631 // not found, insertion point here 632 return (baseIdx + (lim >> 1)); 633} 634