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