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