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