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     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
 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() { 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
 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 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 = mutex_alloc(0);
 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         kfree(buckets, nBuckets * sizeof(Bucket));
 174         ACCUMSIZE(-(nBuckets * sizeof(Bucket)));
 175     }
 176
 177     if (poolGate)
 178         kfree(poolGate, 36 * 4);
 179 }
 180
 181 unsigned 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
 190 unsigned long OSSymbolPool::exp2ml(unsigned int x)
 191 {
 192     return (1 << x) - 1;
 193 }
 194
 195 OSSymbolPoolState OSSymbolPool::initHashState()
 196 {
 197     OSSymbolPoolState newState = { nBuckets, 0 };
 198     return newState;
 199 }
 200
 201 OSSymbol *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
 220 void OSSymbolPool::reconstructSymbols(void)
 221 {
 222     this->reconstructSymbols(true);
 223 }
 224
 225 void 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
 259 OSSymbol *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
 291 OSSymbol *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
 351 void 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  */
 432 OSDefineMetaClassAndStructorsWithInit(OSSymbol, OSString,
 433                                       OSSymbol::initialize())
 434 OSMetaClassDefineReservedUnused(OSSymbol, 0);
 435 OSMetaClassDefineReservedUnused(OSSymbol, 1);
 436 OSMetaClassDefineReservedUnused(OSSymbol, 2);
 437 OSMetaClassDefineReservedUnused(OSSymbol, 3);
 438 OSMetaClassDefineReservedUnused(OSSymbol, 4);
 439 OSMetaClassDefineReservedUnused(OSSymbol, 5);
 440 OSMetaClassDefineReservedUnused(OSSymbol, 6);
 441 OSMetaClassDefineReservedUnused(OSSymbol, 7);
 442
 443 static OSSymbolPool *pool;
 444
 445 void OSSymbol::initialize()
 446 {
 447     pool = new OSSymbolPool;
 448     assert(pool);
 449
 450     if (!pool->init()) {
 451         delete pool;
 452         assert(false);
 453     };
 454 }
 455
 456 bool OSSymbol::initWithCStringNoCopy(const char *) { return false; }
 457 bool OSSymbol::initWithCString(const char *) { return false; }
 458 bool OSSymbol::initWithString(const OSString *) { return false; }
 459
 460 const 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
 473 const 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
 503 const 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
 533 void 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
 553 void OSSymbol::taggedRelease(const void *tag) const
 554 {
 555     super::taggedRelease(tag);
 556 }
 557
 558 void OSSymbol::taggedRelease(const void *tag, const int when) const
 559 {
 560     pool->closeGate();
 561     super::taggedRelease(tag, when);
 562     pool->openGate();
 563 }
 564
 565 void OSSymbol::free()
 566 {
 567     pool->removeSymbol(this);
 568     super::free();
 569 }
 570
 571 bool OSSymbol::isEqualTo(const char *aCString) const
 572 {
 573     return super::isEqualTo(aCString);
 574 }
 575
 576 bool OSSymbol::isEqualTo(const OSSymbol *aSymbol) const
 577 {
 578     return aSymbol == this;
 579 }
 580
 581 bool 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 }