libkern/c++/OSSymbol.cpp

   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
  41 typedef struct { unsigned int i, j; } OSSymbolPoolState;
  42
  43 #if OSALLOCDEBUG
  44 extern "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     } \
  61 while (0)
  62
  63 #define SHRINK_POOL()     do \
  64     if (count * SHRINK_FACTOR < nBuckets && \
  65         nBuckets > INITIAL_POOL_SIZE) { \
  66         reconstructSymbols(false); \
  67     } \
  68 while (0)
  69
  70 class OSSymbolPool
  71 {
  72 private:
  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
 106 public:
 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
 127 void * 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
 137 void OSSymbolPool::operator delete(void *mem, size_t size)
 138 {
 139     kfree(mem, size);
 140     ACCUMSIZE(-size);
 141 }
 142
 143 extern lck_grp_t *IOLockGroup;
 144
 145 bool 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
 161 OSSymbolPool::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
 170 OSSymbolPool::~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
 188 unsigned 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
 197 unsigned long OSSymbolPool::exp2ml(unsigned int x)
 198 {
 199     return (1 << x) - 1;
 200 }
 201
 202 OSSymbolPoolState OSSymbolPool::initHashState()
 203 {
 204     OSSymbolPoolState newState = { nBuckets, 0 };
 205     return newState;
 206 }
 207
 208 OSSymbol *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
 227 void OSSymbolPool::reconstructSymbols(void)
 228 {
 229     this->reconstructSymbols(true);
 230 }
 231
 232 void 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
 266 OSSymbol *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
 298 OSSymbol *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
 358 void 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  */
 448 OSDefineMetaClassAndStructorsWithInit(OSSymbol, OSString,
 449                                       OSSymbol::initialize())
 450 OSMetaClassDefineReservedUnused(OSSymbol, 0);
 451 OSMetaClassDefineReservedUnused(OSSymbol, 1);
 452 OSMetaClassDefineReservedUnused(OSSymbol, 2);
 453 OSMetaClassDefineReservedUnused(OSSymbol, 3);
 454 OSMetaClassDefineReservedUnused(OSSymbol, 4);
 455 OSMetaClassDefineReservedUnused(OSSymbol, 5);
 456 OSMetaClassDefineReservedUnused(OSSymbol, 6);
 457 OSMetaClassDefineReservedUnused(OSSymbol, 7);
 458
 459 static OSSymbolPool *pool;
 460
 461 void 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
 472 bool OSSymbol::initWithCStringNoCopy(const char *) { return false; }
 473 bool OSSymbol::initWithCString(const char *) { return false; }
 474 bool OSSymbol::initWithString(const OSString *) { return false; }
 475
 476 const 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
 489 const 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
 519 const 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
 549 void 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
 569 void OSSymbol::taggedRelease(const void *tag) const
 570 {
 571     super::taggedRelease(tag);
 572 }
 573
 574 void OSSymbol::taggedRelease(const void *tag, const int when) const
 575 {
 576     pool->closeGate();
 577     super::taggedRelease(tag, when);
 578     pool->openGate();
 579 }
 580
 581 void OSSymbol::free()
 582 {
 583     pool->removeSymbol(this);
 584     super::free();
 585 }
 586
 587 bool OSSymbol::isEqualTo(const char *aCString) const
 588 {
 589     return super::isEqualTo(aCString);
 590 }
 591
 592 bool OSSymbol::isEqualTo(const OSSymbol *aSymbol) const
 593 {
 594     return aSymbol == this;
 595 }
 596
 597 bool 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
 610 unsigned int
 611 OSSymbol::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 }