libkern/c++/OSSymbol.cpp

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