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