libkern/c++/OSSymbol.cpp

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