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