libkern/c++/OSSymbol.cpp

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_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. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23 /* IOSymbol.cpp created by gvdl on Fri 1998-11-17 */
  24
  25 #include <string.h>
  26 #include <sys/cdefs.h>
  27
  28 __BEGIN_DECLS
  29 #include <kern/lock.h>
  30 __END_DECLS
  31
  32 #include <libkern/c++/OSSymbol.h>
  33 #include <libkern/c++/OSLib.h>
  34 #include <string.h>
  35
  36 #define super OSString
  37
  38 typedef struct { int i, j; } OSSymbolPoolState;
  39
  40 #if OSALLOCDEBUG
  41 extern "C" {
  42     extern int debug_container_malloc_size;
  43 };
  44 #define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
  45 #else
  46 #define ACCUMSIZE(s)
  47 #endif
  48
  49 class OSSymbolPool
  50 {
  51 private:
  52     static const unsigned int kInitBucketCount = 16;
  53
  54     typedef struct { unsigned int count; OSSymbol **symbolP; } Bucket;
  55
  56     Bucket *buckets;
  57     unsigned int nBuckets;
  58     unsigned int count;
  59     mutex_t *poolGate;
  60
  61     static inline void hashSymbol(const char *s,
  62                                   unsigned int *hashP,
  63                                   unsigned int *lenP)
  64     {
  65         unsigned int hash = 0;
  66         unsigned int len = 0;
  67
  68         /* Unroll the loop. */
  69         for (;;) {
  70             if (!*s) break; len++; hash ^= *s++;
  71             if (!*s) break; len++; hash ^= *s++ <<  8;
  72             if (!*s) break; len++; hash ^= *s++ << 16;
  73             if (!*s) break; len++; hash ^= *s++ << 24;
  74         }
  75         *lenP = len;
  76         *hashP = hash;
  77     }
  78
  79     static unsigned long log2(unsigned int x);
  80     static unsigned long exp2ml(unsigned int x);
  81
  82     void reconstructSymbols();
  83
  84 public:
  85     static void *operator new(size_t size);
  86     static void operator delete(void *mem, size_t size);
  87
  88     OSSymbolPool() { };
  89     OSSymbolPool(const OSSymbolPool *old);
  90     virtual ~OSSymbolPool();
  91
  92     bool init();
  93
  94     inline void closeGate() { mutex_lock(poolGate); };
  95     inline void openGate()  { mutex_unlock(poolGate); };
  96
  97     OSSymbol *findSymbol(const char *cString) const;
  98     OSSymbol *insertSymbol(OSSymbol *sym);
  99     void removeSymbol(OSSymbol *sym);
 100
 101     OSSymbolPoolState initHashState();
 102     OSSymbol *nextHashState(OSSymbolPoolState *stateP);
 103 };
 104
 105 void * OSSymbolPool::operator new(size_t size)
 106 {
 107     void *mem = (void *)kalloc(size);
 108     ACCUMSIZE(size);
 109     assert(mem);
 110     bzero(mem, size);
 111
 112     return mem;
 113 }
 114
 115 void OSSymbolPool::operator delete(void *mem, size_t size)
 116 {
 117     kfree((vm_offset_t)mem, size);
 118     ACCUMSIZE(-size);
 119 }
 120
 121 bool OSSymbolPool::init()
 122 {
 123     count = 0;
 124     nBuckets = exp2ml(1 + log2(kInitBucketCount));
 125     buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket));
 126     ACCUMSIZE(nBuckets * sizeof(Bucket));
 127     if (!buckets)
 128         return false;
 129
 130     bzero(buckets, nBuckets * sizeof(Bucket));
 131
 132     poolGate = mutex_alloc(0);
 133
 134     return poolGate != 0;
 135 }
 136
 137 OSSymbolPool::OSSymbolPool(const OSSymbolPool *old)
 138 {
 139     count = old->count;
 140     nBuckets = old->nBuckets;
 141     buckets = old->buckets;
 142
 143     poolGate = 0;       // Do not duplicate the poolGate
 144 }
 145
 146 OSSymbolPool::~OSSymbolPool()
 147 {
 148     if (buckets) {
 149         kfree((vm_offset_t)buckets, nBuckets * sizeof(Bucket));
 150         ACCUMSIZE(-(nBuckets * sizeof(Bucket)));
 151     }
 152
 153     if (poolGate)
 154         kfree((vm_offset_t) poolGate, 36 * 4);
 155 }
 156
 157 unsigned long OSSymbolPool::log2(unsigned int x)
 158 {
 159     unsigned long i;
 160
 161     for (i = 0; x > 1 ; i++)
 162         x >>= 1;
 163     return i;
 164 }
 165
 166 unsigned long OSSymbolPool::exp2ml(unsigned int x)
 167 {
 168     return (1 << x) - 1;
 169 }
 170
 171 OSSymbolPoolState OSSymbolPool::initHashState()
 172 {
 173     OSSymbolPoolState newState = { nBuckets, 0 };
 174     return newState;
 175 }
 176
 177 OSSymbol *OSSymbolPool::nextHashState(OSSymbolPoolState *stateP)
 178 {
 179     Bucket *thisBucket = &buckets[stateP->i];
 180
 181     while (!stateP->j) {
 182         if (!stateP->i)
 183             return 0;
 184         stateP->i--;
 185         thisBucket--;
 186         stateP->j = thisBucket->count;
 187     }
 188
 189     stateP->j--;
 190     if (thisBucket->count == 1)
 191         return (OSSymbol *) thisBucket->symbolP;
 192     else
 193         return thisBucket->symbolP[stateP->j];
 194 }
 195
 196 void OSSymbolPool::reconstructSymbols()
 197 {
 198     OSSymbolPool old(this);
 199     OSSymbol *insert;
 200     OSSymbolPoolState state;
 201
 202     nBuckets += nBuckets + 1;
 203     count = 0;
 204     buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket));
 205     ACCUMSIZE(nBuckets * sizeof(Bucket));
 206     /* @@@ gvdl: Zero test and panic if can't set up pool */
 207     bzero(buckets, nBuckets * sizeof(Bucket));
 208
 209     state = old.initHashState();
 210     while ( (insert = old.nextHashState(&state)) )
 211         insertSymbol(insert);
 212 }
 213
 214 OSSymbol *OSSymbolPool::findSymbol(const char *cString) const
 215 {
 216     Bucket *thisBucket;
 217     unsigned int j, inLen, hash;
 218     OSSymbol *probeSymbol, **list;
 219
 220     hashSymbol(cString, &hash, &inLen); inLen++;
 221     thisBucket = &buckets[hash % nBuckets];
 222     j = thisBucket->count;
 223
 224     if (!j)
 225         return 0;
 226
 227     if (j == 1) {
 228         probeSymbol = (OSSymbol *) thisBucket->symbolP;
 229
 230         if (inLen == probeSymbol->length
 231         &&  (strcmp(probeSymbol->string, cString) == 0))
 232             return probeSymbol;
 233         return 0;
 234     }
 235
 236     for (list = thisBucket->symbolP; j--; list++) {
 237         probeSymbol = *list;
 238         if (inLen == probeSymbol->length
 239         &&  (strcmp(probeSymbol->string, cString) == 0))
 240             return probeSymbol;
 241     }
 242
 243     return 0;
 244 }
 245
 246 OSSymbol *OSSymbolPool::insertSymbol(OSSymbol *sym)
 247 {
 248     const char *cString = sym->string;
 249     Bucket *thisBucket;
 250     unsigned int j, inLen, hash;
 251     OSSymbol *probeSymbol, **list;
 252
 253     hashSymbol(cString, &hash, &inLen); inLen++;
 254     thisBucket = &buckets[hash % nBuckets];
 255     j = thisBucket->count;
 256
 257     if (!j) {
 258         thisBucket->symbolP = (OSSymbol **) sym;
 259         thisBucket->count++;
 260         count++;
 261         return sym;
 262     }
 263
 264     if (j == 1) {
 265         probeSymbol = (OSSymbol *) thisBucket->symbolP;
 266
 267         if (inLen == probeSymbol->length
 268         &&  strcmp(probeSymbol->string, cString) == 0)
 269             return probeSymbol;
 270
 271         list = (OSSymbol **) kalloc(2 * sizeof(OSSymbol *));
 272         ACCUMSIZE(2 * sizeof(OSSymbol *));
 273         /* @@@ gvdl: Zero test and panic if can't set up pool */
 274         list[0] = sym;
 275         list[1] = probeSymbol;
 276         thisBucket->symbolP = list;
 277         thisBucket->count++;
 278         count++;
 279         if (count > nBuckets)
 280             reconstructSymbols();
 281
 282         return sym;
 283     }
 284
 285     for (list = thisBucket->symbolP; j--; list++) {
 286         probeSymbol = *list;
 287         if (inLen == probeSymbol->length
 288         &&  strcmp(probeSymbol->string, cString) == 0)
 289             return probeSymbol;
 290     }
 291
 292     j = thisBucket->count++;
 293     count++;
 294     list = (OSSymbol **) kalloc(thisBucket->count * sizeof(OSSymbol *));
 295     ACCUMSIZE(thisBucket->count * sizeof(OSSymbol *));
 296     /* @@@ gvdl: Zero test and panic if can't set up pool */
 297     list[0] = sym;
 298     bcopy(thisBucket->symbolP, list + 1, j * sizeof(OSSymbol *));
 299     kfree((vm_offset_t)thisBucket->symbolP, j * sizeof(OSSymbol *));
 300     ACCUMSIZE(-(j * sizeof(OSSymbol *)));
 301     thisBucket->symbolP = list;
 302     if (count > nBuckets)
 303         reconstructSymbols();
 304
 305     return sym;
 306 }
 307
 308 void OSSymbolPool::removeSymbol(OSSymbol *sym)
 309 {
 310     Bucket *thisBucket;
 311     unsigned int j, inLen, hash;
 312     OSSymbol *probeSymbol, **list;
 313
 314     hashSymbol(sym->string, &hash, &inLen); inLen++;
 315     thisBucket = &buckets[hash % nBuckets];
 316     j = thisBucket->count;
 317     list = thisBucket->symbolP;
 318
 319     if (!j)
 320         return;
 321
 322     if (j == 1) {
 323         probeSymbol = (OSSymbol *) list;
 324
 325         if (probeSymbol == sym) {
 326             thisBucket->symbolP = 0;
 327             count--;
 328             thisBucket->count--;
 329             return;
 330         }
 331         return;
 332     }
 333
 334     if (j == 2) {
 335         probeSymbol = list[0];
 336         if (probeSymbol == sym) {
 337             thisBucket->symbolP = (OSSymbol **) list[1];
 338             kfree((vm_offset_t)list, 2 * sizeof(OSSymbol *));
 339             ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
 340             count--;
 341             thisBucket->count--;
 342             return;
 343         }
 344
 345         probeSymbol = list[1];
 346         if (probeSymbol == sym) {
 347             thisBucket->symbolP = (OSSymbol **) list[0];
 348             kfree((vm_offset_t)list, 2 * sizeof(OSSymbol *));
 349             ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
 350             count--;
 351             thisBucket->count--;
 352             return;
 353         }
 354         return;
 355     }
 356
 357     for (; j--; list++) {
 358         probeSymbol = *list;
 359         if (probeSymbol == sym) {
 360
 361             list = (OSSymbol **)
 362                 kalloc((thisBucket->count-1) * sizeof(OSSymbol *));
 363             ACCUMSIZE((thisBucket->count-1) * sizeof(OSSymbol *));
 364             if (thisBucket->count-1 != j)
 365                 bcopy(thisBucket->symbolP, list,
 366                       (thisBucket->count-1-j) * sizeof(OSSymbol *));
 367             if (j)
 368                 bcopy(thisBucket->symbolP + thisBucket->count-j,
 369                       list + thisBucket->count-1-j,
 370                       j * sizeof(OSSymbol *));
 371             kfree((vm_offset_t)thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *));
 372             ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *)));
 373             thisBucket->symbolP = list;
 374             count--;
 375             thisBucket->count--;
 376             return;
 377         }
 378     }
 379 }
 380
 381 /*
 382  *********************************************************************
 383  * From here on we are actually implementing the OSSymbol class
 384  *********************************************************************
 385  */
 386 OSDefineMetaClassAndStructorsWithInit(OSSymbol, OSString,
 387                                       OSSymbol::initialize())
 388 OSMetaClassDefineReservedUnused(OSSymbol, 0);
 389 OSMetaClassDefineReservedUnused(OSSymbol, 1);
 390 OSMetaClassDefineReservedUnused(OSSymbol, 2);
 391 OSMetaClassDefineReservedUnused(OSSymbol, 3);
 392 OSMetaClassDefineReservedUnused(OSSymbol, 4);
 393 OSMetaClassDefineReservedUnused(OSSymbol, 5);
 394 OSMetaClassDefineReservedUnused(OSSymbol, 6);
 395 OSMetaClassDefineReservedUnused(OSSymbol, 7);
 396
 397 static OSSymbolPool *pool;
 398
 399 void OSSymbol::initialize()
 400 {
 401     pool = new OSSymbolPool;
 402     assert(pool);
 403
 404     if (!pool->init()) {
 405         delete pool;
 406         assert(false);
 407     };
 408 }
 409
 410 bool OSSymbol::initWithCStringNoCopy(const char *) { return false; }
 411 bool OSSymbol::initWithCString(const char *) { return false; }
 412 bool OSSymbol::initWithString(const OSString *) { return false; }
 413
 414 const OSSymbol *OSSymbol::withString(const OSString *aString)
 415 {
 416     // This string may be a OSSymbol already, cheap check.
 417     if (OSDynamicCast(OSSymbol, aString)) {
 418         aString->retain();
 419         return (const OSSymbol *) aString;
 420     }
 421     else if (((const OSSymbol *) aString)->flags & kOSStringNoCopy)
 422         return OSSymbol::withCStringNoCopy(aString->getCStringNoCopy());
 423     else
 424         return OSSymbol::withCString(aString->getCStringNoCopy());
 425 }
 426
 427 const OSSymbol *OSSymbol::withCString(const char *cString)
 428 {
 429     pool->closeGate();
 430
 431     OSSymbol *oldSymb = pool->findSymbol(cString);
 432     if (!oldSymb) {
 433         OSSymbol *newSymb = new OSSymbol;
 434         if (!newSymb) {
 435             pool->openGate();
 436             return newSymb;
 437         }
 438
 439         if (newSymb->OSString::initWithCString(cString))
 440             oldSymb = pool->insertSymbol(newSymb);
 441
 442         if (newSymb == oldSymb) {
 443             pool->openGate();
 444             return newSymb;     // return the newly created & inserted symbol.
 445         }
 446         else
 447             // Somebody else inserted the new symbol so free our copy
 448             newSymb->OSString::free();
 449     }
 450
 451     oldSymb->retain();  // Retain the old symbol before releasing the lock.
 452
 453     pool->openGate();
 454     return oldSymb;
 455 }
 456
 457 const OSSymbol *OSSymbol::withCStringNoCopy(const char *cString)
 458 {
 459     pool->closeGate();
 460
 461     OSSymbol *oldSymb = pool->findSymbol(cString);
 462     if (!oldSymb) {
 463         OSSymbol *newSymb = new OSSymbol;
 464         if (!newSymb) {
 465             pool->openGate();
 466             return newSymb;
 467         }
 468
 469         if (newSymb->OSString::initWithCStringNoCopy(cString))
 470             oldSymb = pool->insertSymbol(newSymb);
 471
 472         if (newSymb == oldSymb) {
 473             pool->openGate();
 474             return newSymb;     // return the newly created & inserted symbol.
 475         }
 476         else
 477             // Somebody else inserted the new symbol so free our copy
 478             newSymb->OSString::free();
 479     }
 480
 481     oldSymb->retain();  // Retain the old symbol before releasing the lock.
 482
 483     pool->openGate();
 484     return oldSymb;
 485 }
 486
 487 void OSSymbol::checkForPageUnload(void *startAddr, void *endAddr)
 488 {
 489     OSSymbol *probeSymbol;
 490     OSSymbolPoolState state;
 491
 492     pool->closeGate();
 493     state = pool->initHashState();
 494     while ( (probeSymbol = pool->nextHashState(&state)) ) {
 495         if (probeSymbol->string >= startAddr && probeSymbol->string < endAddr) {
 496             const char *oldString = probeSymbol->string;
 497
 498             probeSymbol->string = (char *) kalloc(probeSymbol->length);
 499             ACCUMSIZE(probeSymbol->length);
 500             bcopy(oldString, probeSymbol->string, probeSymbol->length);
 501             probeSymbol->flags &= ~kOSStringNoCopy;
 502         }
 503     }
 504     pool->openGate();
 505 }
 506
 507 void OSSymbol::taggedRelease(const void *tag) const
 508 {
 509     super::taggedRelease(tag);
 510 }
 511
 512 void OSSymbol::taggedRelease(const void *tag, const int when) const
 513 {
 514     pool->closeGate();
 515     super::taggedRelease(tag, when);
 516     pool->openGate();
 517 }
 518
 519 void OSSymbol::free()
 520 {
 521     pool->removeSymbol(this);
 522     super::free();
 523 }
 524
 525 bool OSSymbol::isEqualTo(const char *aCString) const
 526 {
 527     return super::isEqualTo(aCString);
 528 }
 529
 530 bool OSSymbol::isEqualTo(const OSSymbol *aSymbol) const
 531 {
 532     return aSymbol == this;
 533 }
 534
 535 bool OSSymbol::isEqualTo(const OSMetaClassBase *obj) const
 536 {
 537     OSSymbol *  sym;
 538     OSString *  str;
 539
 540     if ((sym = OSDynamicCast(OSSymbol, obj)))
 541         return isEqualTo(sym);
 542     else if ((str = OSDynamicCast(OSString, obj)))
 543         return super::isEqualTo(str);
 544     else
 545         return false;
 546 }