libkern/c++/OSSymbol.cpp

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