libkern/c++/OSSymbol.cpp

   1 /*
   2  * Copyright (c) 2000-2016 Apple 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 #include <kern/locks.h>
  34
  35 #include <libkern/c++/OSSymbol.h>
  36 #include <libkern/c++/OSLib.h>
  37 #include <string.h>
  38
  39 #define super OSString
  40
  41 typedef struct { unsigned int i, j; } OSSymbolPoolState;
  42
  43 #define INITIAL_POOL_SIZE  (exp2ml(1 + log2(kInitBucketCount)))
  44
  45 #define GROW_FACTOR   (1)
  46 #define SHRINK_FACTOR (3)
  47
  48 #define GROW_POOL()     do \
  49     if (count * GROW_FACTOR > nBuckets) { \
  50         reconstructSymbols(true); \
  51     } \
  52 while (0)
  53
  54 #define SHRINK_POOL()     do \
  55     if (count * SHRINK_FACTOR < nBuckets && \
  56         nBuckets > INITIAL_POOL_SIZE) { \
  57         reconstructSymbols(false); \
  58     } \
  59 while (0)
  60
  61 class OSSymbolPool
  62 {
  63 private:
  64     static const unsigned int kInitBucketCount = 16;
  65
  66     typedef struct { unsigned int count; OSSymbol **symbolP; } Bucket;
  67
  68     Bucket *buckets;
  69     unsigned int nBuckets;
  70     unsigned int count;
  71     lck_mtx_t *poolGate;
  72
  73     static inline void hashSymbol(const char *s,
  74                                   unsigned int *hashP,
  75                                   unsigned int *lenP)
  76     {
  77         unsigned int hash = 0;
  78         unsigned int len = 0;
  79
  80         /* Unroll the loop. */
  81         for (;;) {
  82             if (!*s) break; len++; hash ^= *s++;
  83             if (!*s) break; len++; hash ^= *s++ <<  8;
  84             if (!*s) break; len++; hash ^= *s++ << 16;
  85             if (!*s) break; len++; hash ^= *s++ << 24;
  86         }
  87         *lenP = len;
  88         *hashP = hash;
  89     }
  90
  91     static unsigned long log2(unsigned int x);
  92     static unsigned long exp2ml(unsigned int x);
  93
  94     void reconstructSymbols(void);
  95     void reconstructSymbols(bool grow);
  96
  97 public:
  98     static void *operator new(size_t size);
  99     static void operator delete(void *mem, size_t size);
 100
 101     OSSymbolPool() { }
 102     OSSymbolPool(const OSSymbolPool *old);
 103     virtual ~OSSymbolPool();
 104
 105     bool init();
 106
 107     inline void closeGate() { lck_mtx_lock(poolGate); }
 108     inline void openGate()  { lck_mtx_unlock(poolGate); }
 109
 110     OSSymbol *findSymbol(const char *cString) const;
 111     OSSymbol *insertSymbol(OSSymbol *sym);
 112     void removeSymbol(OSSymbol *sym);
 113
 114     OSSymbolPoolState initHashState();
 115     OSSymbol *nextHashState(OSSymbolPoolState *stateP);
 116 };
 117
 118 void * OSSymbolPool::operator new(size_t size)
 119 {
 120     void *mem = (void *)kalloc_tag(size, VM_KERN_MEMORY_LIBKERN);
 121     OSMETA_ACCUMSIZE(size);
 122     assert(mem);
 123     bzero(mem, size);
 124
 125     return mem;
 126 }
 127
 128 void OSSymbolPool::operator delete(void *mem, size_t size)
 129 {
 130     kfree(mem, size);
 131     OSMETA_ACCUMSIZE(-size);
 132 }
 133
 134 extern lck_grp_t *IOLockGroup;
 135
 136 bool OSSymbolPool::init()
 137 {
 138     count = 0;
 139     nBuckets = INITIAL_POOL_SIZE;
 140     buckets = (Bucket *) kalloc_tag(nBuckets * sizeof(Bucket), VM_KERN_MEMORY_LIBKERN);
 141     OSMETA_ACCUMSIZE(nBuckets * sizeof(Bucket));
 142     if (!buckets)
 143         return false;
 144
 145     bzero(buckets, nBuckets * sizeof(Bucket));
 146
 147     poolGate = lck_mtx_alloc_init(IOLockGroup, LCK_ATTR_NULL);
 148
 149     return poolGate != 0;
 150 }
 151
 152 OSSymbolPool::OSSymbolPool(const OSSymbolPool *old)
 153 {
 154     count = old->count;
 155     nBuckets = old->nBuckets;
 156     buckets = old->buckets;
 157
 158     poolGate = 0;       // Do not duplicate the poolGate
 159 }
 160
 161 OSSymbolPool::~OSSymbolPool()
 162 {
 163     if (buckets) {
 164         Bucket *thisBucket;
 165         for (thisBucket = &buckets[0]; thisBucket < &buckets[nBuckets]; thisBucket++) {
 166             if (thisBucket->count > 1) {
 167                 kfree(thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *));
 168                 OSMETA_ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *)));
 169             }
 170         }
 171         kfree(buckets, nBuckets * sizeof(Bucket));
 172         OSMETA_ACCUMSIZE(-(nBuckets * sizeof(Bucket)));
 173     }
 174
 175     if (poolGate)
 176         lck_mtx_free(poolGate, IOLockGroup);
 177 }
 178
 179 unsigned long OSSymbolPool::log2(unsigned int x)
 180 {
 181     unsigned long i;
 182
 183     for (i = 0; x > 1 ; i++)
 184         x >>= 1;
 185     return i;
 186 }
 187
 188 unsigned long OSSymbolPool::exp2ml(unsigned int x)
 189 {
 190     return (1 << x) - 1;
 191 }
 192
 193 OSSymbolPoolState OSSymbolPool::initHashState()
 194 {
 195     OSSymbolPoolState newState = { nBuckets, 0 };
 196     return newState;
 197 }
 198
 199 OSSymbol *OSSymbolPool::nextHashState(OSSymbolPoolState *stateP)
 200 {
 201     Bucket *thisBucket = &buckets[stateP->i];
 202
 203     while (!stateP->j) {
 204         if (!stateP->i)
 205             return 0;
 206         stateP->i--;
 207         thisBucket--;
 208         stateP->j = thisBucket->count;
 209     }
 210
 211     stateP->j--;
 212     if (thisBucket->count == 1)
 213         return (OSSymbol *) thisBucket->symbolP;
 214     else
 215         return thisBucket->symbolP[stateP->j];
 216 }
 217
 218 void OSSymbolPool::reconstructSymbols(void)
 219 {
 220     this->reconstructSymbols(true);
 221 }
 222
 223 void OSSymbolPool::reconstructSymbols(bool grow)
 224 {
 225     unsigned int new_nBuckets = nBuckets;
 226     OSSymbol *insert;
 227     OSSymbolPoolState state;
 228
 229     if (grow) {
 230         new_nBuckets += new_nBuckets + 1;
 231     } else {
 232        /* Don't shrink the pool below the default initial size.
 233         */
 234         if (nBuckets <= INITIAL_POOL_SIZE) {
 235             return;
 236         }
 237         new_nBuckets = (new_nBuckets - 1) / 2;
 238     }
 239
 240    /* Create old pool to iterate after doing above check, cause it
 241     * gets finalized at return.
 242     */
 243     OSSymbolPool old(this);
 244
 245     count = 0;
 246     nBuckets = new_nBuckets;
 247     buckets = (Bucket *) kalloc_tag(nBuckets * sizeof(Bucket), VM_KERN_MEMORY_LIBKERN);
 248     OSMETA_ACCUMSIZE(nBuckets * sizeof(Bucket));
 249     /* @@@ gvdl: Zero test and panic if can't set up pool */
 250     bzero(buckets, nBuckets * sizeof(Bucket));
 251
 252     state = old.initHashState();
 253     while ( (insert = old.nextHashState(&state)) )
 254         insertSymbol(insert);
 255 }
 256
 257 OSSymbol *OSSymbolPool::findSymbol(const char *cString) const
 258 {
 259     Bucket *thisBucket;
 260     unsigned int j, inLen, hash;
 261     OSSymbol *probeSymbol, **list;
 262
 263     hashSymbol(cString, &hash, &inLen); inLen++;
 264     thisBucket = &buckets[hash % nBuckets];
 265     j = thisBucket->count;
 266
 267     if (!j)
 268         return 0;
 269
 270     if (j == 1) {
 271         probeSymbol = (OSSymbol *) thisBucket->symbolP;
 272
 273         if (inLen == probeSymbol->length
 274         &&  (strncmp(probeSymbol->string, cString, probeSymbol->length) == 0))
 275             return probeSymbol;
 276         return 0;
 277     }
 278
 279     for (list = thisBucket->symbolP; j--; list++) {
 280         probeSymbol = *list;
 281         if (inLen == probeSymbol->length
 282         &&  (strncmp(probeSymbol->string, cString, probeSymbol->length) == 0))
 283             return probeSymbol;
 284     }
 285
 286     return 0;
 287 }
 288
 289 OSSymbol *OSSymbolPool::insertSymbol(OSSymbol *sym)
 290 {
 291     const char *cString = sym->string;
 292     Bucket *thisBucket;
 293     unsigned int j, inLen, hash;
 294     OSSymbol *probeSymbol, **list;
 295
 296     hashSymbol(cString, &hash, &inLen); inLen++;
 297     thisBucket = &buckets[hash % nBuckets];
 298     j = thisBucket->count;
 299
 300     if (!j) {
 301         thisBucket->symbolP = (OSSymbol **) sym;
 302         thisBucket->count++;
 303         count++;
 304         return sym;
 305     }
 306
 307     if (j == 1) {
 308         probeSymbol = (OSSymbol *) thisBucket->symbolP;
 309
 310         if (inLen == probeSymbol->length
 311         &&  strncmp(probeSymbol->string, cString, probeSymbol->length) == 0)
 312             return probeSymbol;
 313
 314         list = (OSSymbol **) kalloc_tag(2 * sizeof(OSSymbol *), VM_KERN_MEMORY_LIBKERN);
 315         OSMETA_ACCUMSIZE(2 * sizeof(OSSymbol *));
 316         /* @@@ gvdl: Zero test and panic if can't set up pool */
 317         list[0] = sym;
 318         list[1] = probeSymbol;
 319         thisBucket->symbolP = list;
 320         thisBucket->count++;
 321         count++;
 322         GROW_POOL();
 323
 324         return sym;
 325     }
 326
 327     for (list = thisBucket->symbolP; j--; list++) {
 328         probeSymbol = *list;
 329         if (inLen == probeSymbol->length
 330         &&  strncmp(probeSymbol->string, cString, probeSymbol->length) == 0)
 331             return probeSymbol;
 332     }
 333
 334     j = thisBucket->count++;
 335     count++;
 336     list = (OSSymbol **) kalloc_tag(thisBucket->count * sizeof(OSSymbol *), VM_KERN_MEMORY_LIBKERN);
 337     OSMETA_ACCUMSIZE(thisBucket->count * sizeof(OSSymbol *));
 338     /* @@@ gvdl: Zero test and panic if can't set up pool */
 339     list[0] = sym;
 340     bcopy(thisBucket->symbolP, list + 1, j * sizeof(OSSymbol *));
 341     kfree(thisBucket->symbolP, j * sizeof(OSSymbol *));
 342     OSMETA_ACCUMSIZE(-(j * sizeof(OSSymbol *)));
 343     thisBucket->symbolP = list;
 344     GROW_POOL();
 345
 346     return sym;
 347 }
 348
 349 void OSSymbolPool::removeSymbol(OSSymbol *sym)
 350 {
 351     Bucket *thisBucket;
 352     unsigned int j, inLen, hash;
 353     OSSymbol *probeSymbol, **list;
 354
 355     hashSymbol(sym->string, &hash, &inLen); inLen++;
 356     thisBucket = &buckets[hash % nBuckets];
 357     j = thisBucket->count;
 358     list = thisBucket->symbolP;
 359
 360     if (!j) {
 361         // couldn't find the symbol; probably means string hash changed
 362         panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
 363         return;
 364     }
 365
 366     if (j == 1) {
 367         probeSymbol = (OSSymbol *) list;
 368
 369         if (probeSymbol == sym) {
 370             thisBucket->symbolP = 0;
 371             count--;
 372             thisBucket->count--;
 373             SHRINK_POOL();
 374             return;
 375         }
 376         // couldn't find the symbol; probably means string hash changed
 377         panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
 378         return;
 379     }
 380
 381     if (j == 2) {
 382         probeSymbol = list[0];
 383         if (probeSymbol == sym) {
 384             thisBucket->symbolP = (OSSymbol **) list[1];
 385             kfree(list, 2 * sizeof(OSSymbol *));
 386             OSMETA_ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
 387             count--;
 388             thisBucket->count--;
 389             SHRINK_POOL();
 390             return;
 391         }
 392
 393         probeSymbol = list[1];
 394         if (probeSymbol == sym) {
 395             thisBucket->symbolP = (OSSymbol **) list[0];
 396             kfree(list, 2 * sizeof(OSSymbol *));
 397             OSMETA_ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
 398             count--;
 399             thisBucket->count--;
 400             SHRINK_POOL();
 401             return;
 402         }
 403         // couldn't find the symbol; probably means string hash changed
 404         panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
 405         return;
 406     }
 407
 408     for (; j--; list++) {
 409         probeSymbol = *list;
 410         if (probeSymbol == sym) {
 411
 412             list = (OSSymbol **)
 413                 kalloc_tag((thisBucket->count-1) * sizeof(OSSymbol *), VM_KERN_MEMORY_LIBKERN);
 414             OSMETA_ACCUMSIZE((thisBucket->count-1) * sizeof(OSSymbol *));
 415             if (thisBucket->count-1 != j)
 416                 bcopy(thisBucket->symbolP, list,
 417                       (thisBucket->count-1-j) * sizeof(OSSymbol *));
 418             if (j)
 419                 bcopy(thisBucket->symbolP + thisBucket->count-j,
 420                       list + thisBucket->count-1-j,
 421                       j * sizeof(OSSymbol *));
 422             kfree(thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *));
 423             OSMETA_ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *)));
 424             thisBucket->symbolP = list;
 425             count--;
 426             thisBucket->count--;
 427             return;
 428         }
 429     }
 430     // couldn't find the symbol; probably means string hash changed
 431     panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
 432 }
 433
 434 /*
 435  *********************************************************************
 436  * From here on we are actually implementing the OSSymbol class
 437  *********************************************************************
 438  */
 439 OSDefineMetaClassAndStructorsWithInit(OSSymbol, OSString,
 440                                       OSSymbol::initialize())
 441 OSMetaClassDefineReservedUnused(OSSymbol, 0);
 442 OSMetaClassDefineReservedUnused(OSSymbol, 1);
 443 OSMetaClassDefineReservedUnused(OSSymbol, 2);
 444 OSMetaClassDefineReservedUnused(OSSymbol, 3);
 445 OSMetaClassDefineReservedUnused(OSSymbol, 4);
 446 OSMetaClassDefineReservedUnused(OSSymbol, 5);
 447 OSMetaClassDefineReservedUnused(OSSymbol, 6);
 448 OSMetaClassDefineReservedUnused(OSSymbol, 7);
 449
 450 static OSSymbolPool *pool;
 451
 452 void OSSymbol::initialize()
 453 {
 454     pool = new OSSymbolPool;
 455     assert(pool);
 456
 457     if (pool && !pool->init()) {
 458         delete pool;
 459         assert(false);
 460     };
 461 }
 462
 463 bool OSSymbol::initWithCStringNoCopy(const char *) { return false; }
 464 bool OSSymbol::initWithCString(const char *) { return false; }
 465 bool OSSymbol::initWithString(const OSString *) { return false; }
 466
 467 const OSSymbol *OSSymbol::withString(const OSString *aString)
 468 {
 469     // This string may be a OSSymbol already, cheap check.
 470     if (OSDynamicCast(OSSymbol, aString)) {
 471         aString->retain();
 472         return (const OSSymbol *) aString;
 473     }
 474     else if (((const OSSymbol *) aString)->flags & kOSStringNoCopy)
 475         return OSSymbol::withCStringNoCopy(aString->getCStringNoCopy());
 476     else
 477         return OSSymbol::withCString(aString->getCStringNoCopy());
 478 }
 479
 480 const OSSymbol *OSSymbol::withCString(const char *cString)
 481 {
 482     pool->closeGate();
 483
 484     OSSymbol *oldSymb = pool->findSymbol(cString);
 485     if (!oldSymb) {
 486         OSSymbol *newSymb = new OSSymbol;
 487         if (!newSymb) {
 488             pool->openGate();
 489             return newSymb;
 490         }
 491
 492         if (newSymb->OSString::initWithCString(cString))
 493             oldSymb = pool->insertSymbol(newSymb);
 494
 495         if (newSymb == oldSymb) {
 496             pool->openGate();
 497             return newSymb;     // return the newly created & inserted symbol.
 498         }
 499         else
 500             // Somebody else inserted the new symbol so free our copy
 501             newSymb->OSString::free();
 502     }
 503
 504     oldSymb->retain();  // Retain the old symbol before releasing the lock.
 505
 506     pool->openGate();
 507     return oldSymb;
 508 }
 509
 510 const OSSymbol *OSSymbol::withCStringNoCopy(const char *cString)
 511 {
 512     pool->closeGate();
 513
 514     OSSymbol *oldSymb = pool->findSymbol(cString);
 515     if (!oldSymb) {
 516         OSSymbol *newSymb = new OSSymbol;
 517         if (!newSymb) {
 518             pool->openGate();
 519             return newSymb;
 520         }
 521
 522         if (newSymb->OSString::initWithCStringNoCopy(cString))
 523             oldSymb = pool->insertSymbol(newSymb);
 524
 525         if (newSymb == oldSymb) {
 526             pool->openGate();
 527             return newSymb;     // return the newly created & inserted symbol.
 528         }
 529         else
 530             // Somebody else inserted the new symbol so free our copy
 531             newSymb->OSString::free();
 532     }
 533
 534     oldSymb->retain();  // Retain the old symbol before releasing the lock.
 535
 536     pool->openGate();
 537     return oldSymb;
 538 }
 539
 540 void OSSymbol::checkForPageUnload(void *startAddr, void *endAddr)
 541 {
 542     OSSymbol *probeSymbol;
 543     OSSymbolPoolState state;
 544
 545     pool->closeGate();
 546     state = pool->initHashState();
 547     while ( (probeSymbol = pool->nextHashState(&state)) ) {
 548         if (probeSymbol->string >= startAddr && probeSymbol->string < endAddr) {
 549             probeSymbol->OSString::initWithCString(probeSymbol->string);
 550         }
 551     }
 552     pool->openGate();
 553 }
 554
 555 void OSSymbol::taggedRelease(const void *tag) const
 556 {
 557     super::taggedRelease(tag);
 558 }
 559
 560 void OSSymbol::taggedRelease(const void *tag, const int when) const
 561 {
 562     pool->closeGate();
 563     super::taggedRelease(tag, when);
 564     pool->openGate();
 565 }
 566
 567 void OSSymbol::free()
 568 {
 569     pool->removeSymbol(this);
 570     super::free();
 571 }
 572
 573 bool OSSymbol::isEqualTo(const char *aCString) const
 574 {
 575     return super::isEqualTo(aCString);
 576 }
 577
 578 bool OSSymbol::isEqualTo(const OSSymbol *aSymbol) const
 579 {
 580     return aSymbol == this;
 581 }
 582
 583 bool OSSymbol::isEqualTo(const OSMetaClassBase *obj) const
 584 {
 585     OSSymbol *  sym;
 586     OSString *  str;
 587
 588     if ((sym = OSDynamicCast(OSSymbol, obj)))
 589         return isEqualTo(sym);
 590     else if ((str = OSDynamicCast(OSString, obj)))
 591         return super::isEqualTo(str);
 592     else
 593         return false;
 594 }
 595
 596 unsigned int
 597 OSSymbol::bsearch(
 598         const void *  key,
 599         const void *  array,
 600         unsigned int  arrayCount,
 601         size_t        memberSize)
 602 {
 603     const void **p;
 604     unsigned int baseIdx = 0;
 605     unsigned int lim;
 606
 607     for (lim = arrayCount; lim; lim >>= 1)
 608     {
 609         p = (typeof(p)) (((uintptr_t) array) + (baseIdx + (lim >> 1)) * memberSize);
 610         if (key == *p)
 611         {
 612             return (baseIdx + (lim >> 1));
 613         }
 614         if (key > *p)
 615         {
 616             // move right
 617             baseIdx += (lim >> 1) + 1;
 618             lim--;
 619         }
 620         // else move left
 621     }
 622     // not found, insertion point here
 623     return (baseIdx + (lim >> 1));
 624 }