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 } 748