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 <sys/cdefs.h>
  25
  26 __BEGIN_DECLS
  27 #include <kern/lock.h>
  28 __END_DECLS
  29
  30 #include <libkern/c++/OSSymbol.h>
  31 #include <libkern/c++/OSLib.h>
  32
  33 #define super OSString
  34
  35 typedef struct { int i, j; } OSSymbolPoolState;
  36
  37 #if OSALLOCDEBUG
  38 extern "C" {
  39     extern int debug_container_malloc_size;
  40 };
  41 #define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
  42 #else
  43 #define ACCUMSIZE(s)
  44 #endif
  45
  46 class OSSymbolPool
  47 {
  48 private:
  49     static const unsigned int kInitBucketCount = 16;
  50
  51     typedef struct { unsigned int count; OSSymbol **symbolP; } Bucket;
  52
  53     Bucket *buckets;
  54     unsigned int nBuckets;
  55     unsigned int count;
  56     mutex_t *poolGate;
  57
  58     static inline void hashSymbol(const char *s,
  59                                   unsigned int *hashP,
  60                                   unsigned int *lenP)
  61     {
  62         unsigned int hash = 0;
  63         unsigned int len = 0;
  64
  65         /* Unroll the loop. */
  66         for (;;) {
  67             if (!*s) break; len++; hash ^= *s++;
  68             if (!*s) break; len++; hash ^= *s++ <<  8;
  69             if (!*s) break; len++; hash ^= *s++ << 16;
  70             if (!*s) break; len++; hash ^= *s++ << 24;
  71         }
  72         *lenP = len;
  73         *hashP = hash;
  74     }
  75
  76     static unsigned long log2(unsigned int x);
  77     static unsigned long exp2ml(unsigned int x);
  78
  79     void reconstructSymbols();
  80
  81 public:
  82     static void *operator new(size_t size);
  83     static void operator delete(void *mem, size_t size);
  84
  85     OSSymbolPool() { };
  86     OSSymbolPool(const OSSymbolPool *old);
  87     virtual ~OSSymbolPool();
  88
  89     bool init();
  90
  91     inline void closeGate() { mutex_lock(poolGate); };
  92     inline void openGate()  { mutex_unlock(poolGate); };
  93
  94     OSSymbol *findSymbol(const char *cString) const;
  95     OSSymbol *insertSymbol(OSSymbol *sym);
  96     void removeSymbol(const char *cString);
  97
  98     OSSymbolPoolState initHashState();
  99     OSSymbol *nextHashState(OSSymbolPoolState *stateP);
 100 };
 101
 102 void * OSSymbolPool::operator new(size_t size)
 103 {
 104     void *mem = (void *)kalloc(size);
 105     ACCUMSIZE(size);
 106     assert(mem);
 107     bzero(mem, size);
 108
 109     return mem;
 110 }
 111
 112 void OSSymbolPool::operator delete(void *mem, size_t size)
 113 {
 114     kfree((vm_offset_t)mem, size);
 115     ACCUMSIZE(-size);
 116 }
 117
 118 bool OSSymbolPool::init()
 119 {
 120     count = 0;
 121     nBuckets = exp2ml(1 + log2(kInitBucketCount));
 122     buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket));
 123     ACCUMSIZE(nBuckets * sizeof(Bucket));
 124     if (!buckets)
 125         return false;
 126
 127     bzero(buckets, nBuckets * sizeof(Bucket));
 128
 129     poolGate = mutex_alloc(0);
 130
 131     return poolGate != 0;
 132 }
 133
 134 OSSymbolPool::OSSymbolPool(const OSSymbolPool *old)
 135 {
 136     count = old->count;
 137     nBuckets = old->nBuckets;
 138     buckets = old->buckets;
 139
 140     poolGate = 0;       // Do not duplicate the poolGate
 141 }
 142
 143 OSSymbolPool::~OSSymbolPool()
 144 {
 145     if (buckets) {
 146         kfree((vm_offset_t)buckets, nBuckets * sizeof(Bucket));
 147         ACCUMSIZE(-(nBuckets * sizeof(Bucket)));
 148     }
 149
 150     if (poolGate)
 151         kfree((vm_offset_t) poolGate, 36 * 4);
 152 }
 153
 154 unsigned long OSSymbolPool::log2(unsigned int x)
 155 {
 156     unsigned long i;
 157
 158     for (i = 0; x > 1 ; i++)
 159         x >>= 1;
 160     return i;
 161 }
 162
 163 unsigned long OSSymbolPool::exp2ml(unsigned int x)
 164 {
 165     return (1 << x) - 1;
 166 }
 167
 168 OSSymbolPoolState OSSymbolPool::initHashState()
 169 {
 170     OSSymbolPoolState newState = { nBuckets, 0 };
 171     return newState;
 172 }
 173
 174 OSSymbol *OSSymbolPool::nextHashState(OSSymbolPoolState *stateP)
 175 {
 176     Bucket *thisBucket = &buckets[stateP->i];
 177
 178     while (!stateP->j) {
 179         if (!stateP->i)
 180             return 0;
 181         stateP->i--;
 182         thisBucket--;
 183         stateP->j = thisBucket->count;
 184     }
 185
 186     stateP->j--;
 187     if (thisBucket->count == 1)
 188         return (OSSymbol *) thisBucket->symbolP;
 189     else
 190         return thisBucket->symbolP[stateP->j];
 191 }
 192
 193 void OSSymbolPool::reconstructSymbols()
 194 {
 195     OSSymbolPool old(this);
 196     OSSymbol *insert;
 197     OSSymbolPoolState state;
 198
 199     nBuckets += nBuckets + 1;
 200     count = 0;
 201     buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket));
 202     ACCUMSIZE(nBuckets * sizeof(Bucket));
 203     /* @@@ gvdl: Zero test and panic if can't set up pool */
 204     bzero(buckets, nBuckets * sizeof(Bucket));
 205
 206     state = old.initHashState();
 207     while ( (insert = old.nextHashState(&state)) )
 208         insertSymbol(insert);
 209 }
 210
 211 OSSymbol *OSSymbolPool::findSymbol(const char *cString) const
 212 {
 213     Bucket *thisBucket;
 214     unsigned int j, inLen, hash;
 215     OSSymbol *probeSymbol, **list;
 216
 217     hashSymbol(cString, &hash, &inLen); inLen++;
 218     thisBucket = &buckets[hash % nBuckets];
 219     j = thisBucket->count;
 220
 221     if (!j)
 222         return 0;
 223
 224     if (j == 1) {
 225         probeSymbol = (OSSymbol *) thisBucket->symbolP;
 226
 227         if (inLen == probeSymbol->length
 228         &&  (strcmp(probeSymbol->string, cString) == 0)
 229         &&  (probeSymbol->getRetainCount() >= 1))       // WRONG need when
 230             return probeSymbol;
 231         else
 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         &&  (probeSymbol->getRetainCount() >= 1))       // WRONG need when
 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 0;
 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 0;
 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 0;
 306 }
 307
 308 void OSSymbolPool::removeSymbol(const char *cString)
 309 {
 310     Bucket *thisBucket;
 311     unsigned int j, inLen, hash;
 312     OSSymbol *probeSymbol, **list;
 313
 314     hashSymbol(cString, &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 (inLen == probeSymbol->length
 326         &&  strcmp(probeSymbol->string, cString) == 0) {
 327             thisBucket->symbolP = 0;
 328             count--;
 329             thisBucket->count--;
 330             return;
 331         }
 332         return;
 333     }
 334
 335     if (j == 2) {
 336         probeSymbol = list[0];
 337         if (inLen == probeSymbol->length
 338         &&  strcmp(probeSymbol->string, cString) == 0) {
 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 (inLen == probeSymbol->length
 349         &&  strcmp(probeSymbol->string, cString) == 0) {
 350             thisBucket->symbolP = (OSSymbol **) list[0];
 351             kfree((vm_offset_t)list, 2 * sizeof(OSSymbol *));
 352             ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
 353             count--;
 354             thisBucket->count--;
 355             return;
 356         }
 357         return;
 358     }
 359
 360     for (; j--; list++) {
 361         probeSymbol = *list;
 362         if (inLen == probeSymbol->length
 363         &&  strcmp(probeSymbol->string, cString) == 0) {
 364
 365             list = (OSSymbol **)
 366                 kalloc((thisBucket->count-1) * sizeof(OSSymbol *));
 367             ACCUMSIZE((thisBucket->count-1) * sizeof(OSSymbol *));
 368             if (thisBucket->count-1 != j)
 369                 bcopy(thisBucket->symbolP, list,
 370                       (thisBucket->count-1-j) * sizeof(OSSymbol *));
 371             if (j)
 372                 bcopy(thisBucket->symbolP + thisBucket->count-j,
 373                       list + thisBucket->count-1-j,
 374                       j * sizeof(OSSymbol *));
 375             kfree((vm_offset_t)thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *));
 376             ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *)));
 377             thisBucket->symbolP = list;
 378             count--;
 379             thisBucket->count--;
 380             return;
 381         }
 382     }
 383 }
 384
 385 /*
 386  *********************************************************************
 387  * From here on we are actually implementing the OSSymbol class
 388  *********************************************************************
 389  */
 390 OSDefineMetaClassAndStructorsWithInit(OSSymbol, OSString,
 391                                       OSSymbol::initialize())
 392 OSMetaClassDefineReservedUnused(OSSymbol, 0);
 393 OSMetaClassDefineReservedUnused(OSSymbol, 1);
 394 OSMetaClassDefineReservedUnused(OSSymbol, 2);
 395 OSMetaClassDefineReservedUnused(OSSymbol, 3);
 396 OSMetaClassDefineReservedUnused(OSSymbol, 4);
 397 OSMetaClassDefineReservedUnused(OSSymbol, 5);
 398 OSMetaClassDefineReservedUnused(OSSymbol, 6);
 399 OSMetaClassDefineReservedUnused(OSSymbol, 7);
 400
 401 static OSSymbolPool *pool;
 402
 403 void OSSymbol::initialize()
 404 {
 405     pool = new OSSymbolPool;
 406     assert(pool);
 407
 408     if (!pool->init()) {
 409         delete pool;
 410         assert(false);
 411     };
 412 }
 413
 414 bool OSSymbol::initWithCStringNoCopy(const char *) { return false; }
 415 bool OSSymbol::initWithCString(const char *) { return false; }
 416 bool OSSymbol::initWithString(const OSString *) { return false; }
 417
 418 const OSSymbol *OSSymbol::withString(const OSString *aString)
 419 {
 420     // This string may be a OSSymbol already, cheap check.
 421     if (OSDynamicCast(OSSymbol, aString)) {
 422         aString->retain();
 423         return (const OSSymbol *) aString;
 424     }
 425     else if (((const OSSymbol *) aString)->flags & kOSStringNoCopy)
 426         return OSSymbol::withCStringNoCopy(aString->getCStringNoCopy());
 427     else
 428         return OSSymbol::withCString(aString->getCStringNoCopy());
 429 }
 430
 431 const OSSymbol *OSSymbol::withCString(const char *cString)
 432 {
 433     pool->closeGate();
 434
 435     OSSymbol *newSymb = pool->findSymbol(cString);
 436     if (newSymb)
 437         newSymb->retain();
 438     else if ( (newSymb = new OSSymbol) ) {
 439         if (newSymb->OSString::initWithCString(cString))
 440             pool->insertSymbol(newSymb);
 441         else {
 442             newSymb->free();
 443             newSymb = 0;
 444         }
 445     }
 446     pool->openGate();
 447
 448     return newSymb;
 449 }
 450
 451 const OSSymbol *OSSymbol::withCStringNoCopy(const char *cString)
 452 {
 453     pool->closeGate();
 454
 455     OSSymbol *newSymb = pool->findSymbol(cString);
 456     if (newSymb)
 457         newSymb->retain();
 458     else if ( (newSymb = new OSSymbol) ) {
 459         if (newSymb->OSString::initWithCStringNoCopy(cString))
 460             pool->insertSymbol(newSymb);
 461         else {
 462             newSymb->free();
 463             newSymb = 0;
 464         }
 465     }
 466     pool->openGate();
 467
 468     return newSymb;
 469 }
 470
 471 void OSSymbol::checkForPageUnload(void *startAddr, void *endAddr)
 472 {
 473     OSSymbol *probeSymbol;
 474     OSSymbolPoolState state;
 475
 476     pool->closeGate();
 477     state = pool->initHashState();
 478     while ( (probeSymbol = pool->nextHashState(&state)) ) {
 479         if (probeSymbol->string >= startAddr && probeSymbol->string < endAddr) {
 480             const char *oldString = probeSymbol->string;
 481
 482             probeSymbol->string = (char *) kalloc(probeSymbol->length);
 483             ACCUMSIZE(probeSymbol->length);
 484             bcopy(oldString, probeSymbol->string, probeSymbol->length);
 485             probeSymbol->flags &= ~kOSStringNoCopy;
 486         }
 487     }
 488     pool->openGate();
 489 }
 490
 491 void OSSymbol::free()
 492 {
 493     pool->closeGate();
 494     pool->removeSymbol(string);
 495     pool->openGate();
 496
 497     super::free();
 498 }
 499
 500 bool OSSymbol::isEqualTo(const char *aCString) const
 501 {
 502     return super::isEqualTo(aCString);
 503 }
 504
 505 bool OSSymbol::isEqualTo(const OSSymbol *aSymbol) const
 506 {
 507     return aSymbol == this;
 508 }
 509
 510 bool OSSymbol::isEqualTo(const OSMetaClassBase *obj) const
 511 {
 512     OSSymbol *  sym;
 513     OSString *  str;
 514
 515     if ((sym = OSDynamicCast(OSSymbol, obj)))
 516         return isEqualTo(sym);
 517     else if ((str = OSDynamicCast(OSString, obj)))
 518         return super::isEqualTo(str);
 519     else
 520         return false;
 521 }