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 { unsigned 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 Bucket *thisBucket; 176 for (thisBucket = &buckets[0]; thisBucket < &buckets[nBuckets]; thisBucket++) { 177 if (thisBucket->count > 1) { 178 kfree(thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *)); 179 ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *))); 180 } 181 } 182 kfree(buckets, nBuckets * sizeof(Bucket)); 183 ACCUMSIZE(-(nBuckets * sizeof(Bucket))); 184 } 185 186 if (poolGate) 187 lck_mtx_free(poolGate, IOLockGroup); 188} 189 190unsigned long OSSymbolPool::log2(unsigned int x) 191{ 192 unsigned long i; 193 194 for (i = 0; x > 1 ; i++) 195 x >>= 1; 196 return i; 197} 198 199unsigned long OSSymbolPool::exp2ml(unsigned int x) 200{ 201 return (1 << x) - 1; 202} 203 204OSSymbolPoolState OSSymbolPool::initHashState() 205{ 206 OSSymbolPoolState newState = { nBuckets, 0 }; 207 return newState; 208} 209 210OSSymbol *OSSymbolPool::nextHashState(OSSymbolPoolState *stateP) 211{ 212 Bucket *thisBucket = &buckets[stateP->i]; 213 214 while (!stateP->j) { 215 if (!stateP->i) 216 return 0; 217 stateP->i--; 218 thisBucket--; 219 stateP->j = thisBucket->count; 220 } 221 222 stateP->j--; 223 if (thisBucket->count == 1) 224 return (OSSymbol *) thisBucket->symbolP; 225 else 226 return thisBucket->symbolP[stateP->j]; 227} 228 229void OSSymbolPool::reconstructSymbols(void) 230{ 231 this->reconstructSymbols(true); 232} 233 234void OSSymbolPool::reconstructSymbols(bool grow) 235{ 236 unsigned int new_nBuckets = nBuckets; 237 OSSymbol *insert; 238 OSSymbolPoolState state; 239 240 if (grow) { 241 new_nBuckets += new_nBuckets + 1; 242 } else { 243 /* Don't shrink the pool below the default initial size. 244 */ 245 if (nBuckets <= INITIAL_POOL_SIZE) { 246 return; 247 } 248 new_nBuckets = (new_nBuckets - 1) / 2; 249 } 250 251 /* Create old pool to iterate after doing above check, cause it 252 * gets finalized at return. 253 */ 254 OSSymbolPool old(this); 255 256 count = 0; 257 nBuckets = new_nBuckets; 258 buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket)); 259 ACCUMSIZE(nBuckets * sizeof(Bucket)); 260 /* @@@ gvdl: Zero test and panic if can't set up pool */ 261 bzero(buckets, nBuckets * sizeof(Bucket)); 262 263 state = old.initHashState(); 264 while ( (insert = old.nextHashState(&state)) ) 265 insertSymbol(insert); 266} 267 268OSSymbol *OSSymbolPool::findSymbol(const char *cString) const 269{ 270 Bucket *thisBucket; 271 unsigned int j, inLen, hash; 272 OSSymbol *probeSymbol, **list; 273 274 hashSymbol(cString, &hash, &inLen); inLen++; 275 thisBucket = &buckets[hash % nBuckets]; 276 j = thisBucket->count; 277 278 if (!j) 279 return 0; 280 281 if (j == 1) { 282 probeSymbol = (OSSymbol *) thisBucket->symbolP; 283 284 if (inLen == probeSymbol->length 285 && (strncmp(probeSymbol->string, cString, probeSymbol->length) == 0)) 286 return probeSymbol; 287 return 0; 288 } 289 290 for (list = thisBucket->symbolP; j--; list++) { 291 probeSymbol = *list; 292 if (inLen == probeSymbol->length 293 && (strncmp(probeSymbol->string, cString, probeSymbol->length) == 0)) 294 return probeSymbol; 295 } 296 297 return 0; 298} 299 300OSSymbol *OSSymbolPool::insertSymbol(OSSymbol *sym) 301{ 302 const char *cString = sym->string; 303 Bucket *thisBucket; 304 unsigned int j, inLen, hash; 305 OSSymbol *probeSymbol, **list; 306 307 hashSymbol(cString, &hash, &inLen); inLen++; 308 thisBucket = &buckets[hash % nBuckets]; 309 j = thisBucket->count; 310 311 if (!j) { 312 thisBucket->symbolP = (OSSymbol **) sym; 313 thisBucket->count++; 314 count++; 315 return sym; 316 } 317 318 if (j == 1) { 319 probeSymbol = (OSSymbol *) thisBucket->symbolP; 320 321 if (inLen == probeSymbol->length 322 && strncmp(probeSymbol->string, cString, probeSymbol->length) == 0) 323 return probeSymbol; 324 325 list = (OSSymbol **) kalloc(2 * sizeof(OSSymbol *)); 326 ACCUMSIZE(2 * sizeof(OSSymbol *)); 327 /* @@@ gvdl: Zero test and panic if can't set up pool */ 328 list[0] = sym; 329 list[1] = probeSymbol; 330 thisBucket->symbolP = list; 331 thisBucket->count++; 332 count++; 333 GROW_POOL(); 334 335 return sym; 336 } 337 338 for (list = thisBucket->symbolP; j--; list++) { 339 probeSymbol = *list; 340 if (inLen == probeSymbol->length 341 && strncmp(probeSymbol->string, cString, probeSymbol->length) == 0) 342 return probeSymbol; 343 } 344 345 j = thisBucket->count++; 346 count++; 347 list = (OSSymbol **) kalloc(thisBucket->count * sizeof(OSSymbol *)); 348 ACCUMSIZE(thisBucket->count * sizeof(OSSymbol *)); 349 /* @@@ gvdl: Zero test and panic if can't set up pool */ 350 list[0] = sym; 351 bcopy(thisBucket->symbolP, list + 1, j * sizeof(OSSymbol *)); 352 kfree(thisBucket->symbolP, j * sizeof(OSSymbol *)); 353 ACCUMSIZE(-(j * sizeof(OSSymbol *))); 354 thisBucket->symbolP = list; 355 GROW_POOL(); 356 357 return sym; 358} 359 360void OSSymbolPool::removeSymbol(OSSymbol *sym) 361{ 362 Bucket *thisBucket; 363 unsigned int j, inLen, hash; 364 OSSymbol *probeSymbol, **list; 365 366 hashSymbol(sym->string, &hash, &inLen); inLen++; 367 thisBucket = &buckets[hash % nBuckets]; 368 j = thisBucket->count; 369 list = thisBucket->symbolP; 370 371 if (!j) { 372 // couldn't find the symbol; probably means string hash changed 373 panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count); 374 return; 375 } 376 377 if (j == 1) { 378 probeSymbol = (OSSymbol *) list; 379 380 if (probeSymbol == sym) { 381 thisBucket->symbolP = 0; 382 count--; 383 thisBucket->count--; 384 SHRINK_POOL(); 385 return; 386 } 387 // couldn't find the symbol; probably means string hash changed 388 panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count); 389 return; 390 } 391 392 if (j == 2) { 393 probeSymbol = list[0]; 394 if (probeSymbol == sym) { 395 thisBucket->symbolP = (OSSymbol **) list[1]; 396 kfree(list, 2 * sizeof(OSSymbol *)); 397 ACCUMSIZE(-(2 * sizeof(OSSymbol *))); 398 count--; 399 thisBucket->count--; 400 SHRINK_POOL(); 401 return; 402 } 403 404 probeSymbol = list[1]; 405 if (probeSymbol == sym) { 406 thisBucket->symbolP = (OSSymbol **) list[0]; 407 kfree(list, 2 * sizeof(OSSymbol *)); 408 ACCUMSIZE(-(2 * sizeof(OSSymbol *))); 409 count--; 410 thisBucket->count--; 411 SHRINK_POOL(); 412 return; 413 } 414 // couldn't find the symbol; probably means string hash changed 415 panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count); 416 return; 417 } 418 419 for (; j--; list++) { 420 probeSymbol = *list; 421 if (probeSymbol == sym) { 422 423 list = (OSSymbol **) 424 kalloc((thisBucket->count-1) * sizeof(OSSymbol *)); 425 ACCUMSIZE((thisBucket->count-1) * sizeof(OSSymbol *)); 426 if (thisBucket->count-1 != j) 427 bcopy(thisBucket->symbolP, list, 428 (thisBucket->count-1-j) * sizeof(OSSymbol *)); 429 if (j) 430 bcopy(thisBucket->symbolP + thisBucket->count-j, 431 list + thisBucket->count-1-j, 432 j * sizeof(OSSymbol *)); 433 kfree(thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *)); 434 ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *))); 435 thisBucket->symbolP = list; 436 count--; 437 thisBucket->count--; 438 return; 439 } 440 } 441 // couldn't find the symbol; probably means string hash changed 442 panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count); 443} 444 445/* 446 ********************************************************************* 447 * From here on we are actually implementing the OSSymbol class 448 ********************************************************************* 449 */ 450OSDefineMetaClassAndStructorsWithInit(OSSymbol, OSString, 451 OSSymbol::initialize()) 452OSMetaClassDefineReservedUnused(OSSymbol, 0); 453OSMetaClassDefineReservedUnused(OSSymbol, 1); 454OSMetaClassDefineReservedUnused(OSSymbol, 2); 455OSMetaClassDefineReservedUnused(OSSymbol, 3); 456OSMetaClassDefineReservedUnused(OSSymbol, 4); 457OSMetaClassDefineReservedUnused(OSSymbol, 5); 458OSMetaClassDefineReservedUnused(OSSymbol, 6); 459OSMetaClassDefineReservedUnused(OSSymbol, 7); 460 461static OSSymbolPool *pool; 462 463void OSSymbol::initialize() 464{ 465 pool = new OSSymbolPool; 466 assert(pool); 467 468 if (!pool->init()) { 469 delete pool; 470 assert(false); 471 }; 472} 473 474bool OSSymbol::initWithCStringNoCopy(const char *) { return false; } 475bool OSSymbol::initWithCString(const char *) { return false; } 476bool OSSymbol::initWithString(const OSString *) { return false; } 477 478const OSSymbol *OSSymbol::withString(const OSString *aString) 479{ 480 // This string may be a OSSymbol already, cheap check. 481 if (OSDynamicCast(OSSymbol, aString)) { 482 aString->retain(); 483 return (const OSSymbol *) aString; 484 } 485 else if (((const OSSymbol *) aString)->flags & kOSStringNoCopy) 486 return OSSymbol::withCStringNoCopy(aString->getCStringNoCopy()); 487 else 488 return OSSymbol::withCString(aString->getCStringNoCopy()); 489} 490 491const OSSymbol *OSSymbol::withCString(const char *cString) 492{ 493 pool->closeGate(); 494 495 OSSymbol *oldSymb = pool->findSymbol(cString); 496 if (!oldSymb) { 497 OSSymbol *newSymb = new OSSymbol; 498 if (!newSymb) { 499 pool->openGate(); 500 return newSymb; 501 } 502 503 if (newSymb->OSString::initWithCString(cString)) 504 oldSymb = pool->insertSymbol(newSymb); 505 506 if (newSymb == oldSymb) { 507 pool->openGate(); 508 return newSymb; // return the newly created & inserted symbol. 509 } 510 else 511 // Somebody else inserted the new symbol so free our copy 512 newSymb->OSString::free(); 513 } 514 515 oldSymb->retain(); // Retain the old symbol before releasing the lock. 516 517 pool->openGate(); 518 return oldSymb; 519} 520 521const OSSymbol *OSSymbol::withCStringNoCopy(const char *cString) 522{ 523 pool->closeGate(); 524 525 OSSymbol *oldSymb = pool->findSymbol(cString); 526 if (!oldSymb) { 527 OSSymbol *newSymb = new OSSymbol; 528 if (!newSymb) { 529 pool->openGate(); 530 return newSymb; 531 } 532 533 if (newSymb->OSString::initWithCStringNoCopy(cString)) 534 oldSymb = pool->insertSymbol(newSymb); 535 536 if (newSymb == oldSymb) { 537 pool->openGate(); 538 return newSymb; // return the newly created & inserted symbol. 539 } 540 else 541 // Somebody else inserted the new symbol so free our copy 542 newSymb->OSString::free(); 543 } 544 545 oldSymb->retain(); // Retain the old symbol before releasing the lock. 546 547 pool->openGate(); 548 return oldSymb; 549} 550 551void OSSymbol::checkForPageUnload(void *startAddr, void *endAddr) 552{ 553 OSSymbol *probeSymbol; 554 OSSymbolPoolState state; 555 556 pool->closeGate(); 557 state = pool->initHashState(); 558 while ( (probeSymbol = pool->nextHashState(&state)) ) { 559 if (probeSymbol->string >= startAddr && probeSymbol->string < endAddr) { 560 const char *oldString = probeSymbol->string; 561 562 probeSymbol->string = (char *) kalloc(probeSymbol->length); 563 ACCUMSIZE(probeSymbol->length); 564 bcopy(oldString, probeSymbol->string, probeSymbol->length); 565 probeSymbol->flags &= ~kOSStringNoCopy; 566 } 567 } 568 pool->openGate(); 569} 570 571void OSSymbol::taggedRelease(const void *tag) const 572{ 573 super::taggedRelease(tag); 574} 575 576void OSSymbol::taggedRelease(const void *tag, const int when) const 577{ 578 pool->closeGate(); 579 super::taggedRelease(tag, when); 580 pool->openGate(); 581} 582 583void OSSymbol::free() 584{ 585 pool->removeSymbol(this); 586 super::free(); 587} 588 589bool OSSymbol::isEqualTo(const char *aCString) const 590{ 591 return super::isEqualTo(aCString); 592} 593 594bool OSSymbol::isEqualTo(const OSSymbol *aSymbol) const 595{ 596 return aSymbol == this; 597} 598 599bool OSSymbol::isEqualTo(const OSMetaClassBase *obj) const 600{ 601 OSSymbol * sym; 602 OSString * str; 603 604 if ((sym = OSDynamicCast(OSSymbol, obj))) 605 return isEqualTo(sym); 606 else if ((str = OSDynamicCast(OSString, obj))) 607 return super::isEqualTo(str); 608 else 609 return false; 610} 611 612unsigned int 613OSSymbol::bsearch( 614 const void * key, 615 const void * array, 616 unsigned int arrayCount, 617 size_t memberSize) 618{ 619 const void **p; 620 unsigned int baseIdx = 0; 621 unsigned int lim; 622 623 for (lim = arrayCount; lim; lim >>= 1) 624 { 625 p = (typeof(p)) (((uintptr_t) array) + (baseIdx + (lim >> 1)) * memberSize); 626 if (key == *p) 627 { 628 return (baseIdx + (lim >> 1)); 629 } 630 if (key > *p) 631 { 632 // move right 633 baseIdx += (lim >> 1) + 1; 634 lim--; 635 } 636 // else move left 637 } 638 // not found, insertion point here 639 return (baseIdx + (lim >> 1)); 640} 641