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