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 __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
  43 typedef struct { unsigned int i, j; } OSSymbolPoolState;
  44
  45 #if OSALLOCDEBUG
  46 extern "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     } \
  63 while (0)
  64
  65 #define SHRINK_POOL()     do \
  66     if (count * SHRINK_FACTOR < nBuckets && \
  67         nBuckets > INITIAL_POOL_SIZE) { \
  68         reconstructSymbols(false); \
  69     } \
  70 while (0)
  71
  72 class OSSymbolPool
  73 {
  74 private:
  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
 108 public:
 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
 129 void * 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
 139 void OSSymbolPool::operator delete(void *mem, size_t size)
 140 {
 141     kfree(mem, size);
 142     ACCUMSIZE(-size);
 143 }
 144
 145 extern lck_grp_t *IOLockGroup;
 146
 147 bool 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
 163 OSSymbolPool::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
 172 OSSymbolPool::~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
 190 unsigned 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
 199 unsigned long OSSymbolPool::exp2ml(unsigned int x)
 200 {
 201     return (1 << x) - 1;
 202 }
 203
 204 OSSymbolPoolState OSSymbolPool::initHashState()
 205 {
 206     OSSymbolPoolState newState = { nBuckets, 0 };
 207     return newState;
 208 }
 209
 210 OSSymbol *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
 229 void OSSymbolPool::reconstructSymbols(void)
 230 {
 231     this->reconstructSymbols(true);
 232 }
 233
 234 void 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
 268 OSSymbol *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
 300 OSSymbol *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
 360 void 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  */
 450 OSDefineMetaClassAndStructorsWithInit(OSSymbol, OSString,
 451                                       OSSymbol::initialize())
 452 OSMetaClassDefineReservedUnused(OSSymbol, 0);
 453 OSMetaClassDefineReservedUnused(OSSymbol, 1);
 454 OSMetaClassDefineReservedUnused(OSSymbol, 2);
 455 OSMetaClassDefineReservedUnused(OSSymbol, 3);
 456 OSMetaClassDefineReservedUnused(OSSymbol, 4);
 457 OSMetaClassDefineReservedUnused(OSSymbol, 5);
 458 OSMetaClassDefineReservedUnused(OSSymbol, 6);
 459 OSMetaClassDefineReservedUnused(OSSymbol, 7);
 460
 461 static OSSymbolPool *pool;
 462
 463 void OSSymbol::initialize()
 464 {
 465     pool = new OSSymbolPool;
 466     assert(pool);
 467
 468     if (!pool->init()) {
 469         delete pool;
 470         assert(false);
 471     };
 472 }
 473
 474 bool OSSymbol::initWithCStringNoCopy(const char *) { return false; }
 475 bool OSSymbol::initWithCString(const char *) { return false; }
 476 bool OSSymbol::initWithString(const OSString *) { return false; }
 477
 478 const 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
 491 const 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
 521 const 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
 551 void 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
 571 void OSSymbol::taggedRelease(const void *tag) const
 572 {
 573     super::taggedRelease(tag);
 574 }
 575
 576 void OSSymbol::taggedRelease(const void *tag, const int when) const
 577 {
 578     pool->closeGate();
 579     super::taggedRelease(tag, when);
 580     pool->openGate();
 581 }
 582
 583 void OSSymbol::free()
 584 {
 585     pool->removeSymbol(this);
 586     super::free();
 587 }
 588
 589 bool OSSymbol::isEqualTo(const char *aCString) const
 590 {
 591     return super::isEqualTo(aCString);
 592 }
 593
 594 bool OSSymbol::isEqualTo(const OSSymbol *aSymbol) const
 595 {
 596     return aSymbol == this;
 597 }
 598
 599 bool 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
 612 unsigned int
 613 OSSymbol::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 }