libkern/c++/OSSymbol.cpp

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