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/bits.h>
36#include <kern/locks.h>
37#include <kern/smr_hash.h>
38#include <kern/thread_call.h>
39
40#if defined(__arm64__)
41#include <arm64/amcc_rorgn.h> /* rorgn_contains */
42#endif
43#include <libkern/c++/OSSymbol.h>
44#include <libkern/c++/OSSharedPtr.h>
45#include <libkern/c++/OSLib.h>
46#include <os/cpp_util.h>
47#include <os/hash.h>
48#include <string.h>
49
50static ZONE_DEFINE(OSSymbol_zone, "iokit.OSSymbol", sizeof(OSSymbol), ZC_NONE);
51static LCK_GRP_DECLARE(lock_group, "OSSymbolPool");
52
53#pragma clang diagnostic push
54#pragma clang diagnostic ignored "-Winvalid-offsetof"
55
56/*
57 * This implements a relativistic hash table, using <kern/smr.h> as underlying
58 * safe memory reclamation scheme.
59 *
60 * (https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf)
61 *
62 * One twist is that the OSSymbol_smr_free() callback must be
63 * preemption-disabled safe, which means the `kfree_data()` it calls _MUST_ be
64 * smaller than KALLOC_SAFE_ALLOC_SIZE. To deal with that, if a Symbol is made
65 * with a string that is much larger (should be rare), these go on a lock-based
66 * "huge" queue.
67 */
68class OSSymbolPool
69{
70 /* empirically most devices have at least 10+k symbols */
71 static constexpr uint32_t MIN_SIZE = 4096;
72
73 static inline smrh_key_t
74 OSSymbol_get_key(const OSSymbol *sym)
75 {
76 return {
77 .smrk_string = sym->string,
78 .smrk_len = (size_t)(sym->length - 1)
79 };
80 }
81
82 static uint32_t
83 OSSymbol_obj_hash(const struct smrq_slink *link, uint32_t seed)
84 {
85 OSSymbol *sym = __container_of(link, OSSymbol, hashlink);
86
87 return smrh_key_hash_str(key: OSSymbol_get_key(sym), seed);
88 }
89
90 static bool
91 OSSymbol_obj_equ(const struct smrq_slink *link, smrh_key_t key)
92 {
93 OSSymbol *sym = __container_of(link, OSSymbol, hashlink);
94
95 return smrh_key_equ_str(k1: OSSymbol_get_key(sym), k2: key);
96 }
97
98 static bool
99 OSSymbol_obj_try_get(void *obj)
100 {
101 OSSymbol *sym = (OSSymbol *)obj;
102
103 return (sym->flags & kOSSSymbolPermanent) ||
104 sym->taggedTryRetain(tag: nullptr);
105 }
106
107 SMRH_TRAITS_DEFINE_STR(hash_traits, OSSymbol, hashlink,
108 .domain = &smr_iokit,
109 .obj_hash = OSSymbol_obj_hash,
110 .obj_equ = OSSymbol_obj_equ,
111 .obj_try_get = OSSymbol_obj_try_get);
112
113 mutable lck_mtx_t _mutex;
114 struct smr_hash _hash;
115 smrq_slist_head _huge_head;
116 thread_call_t _tcall;
117 uint32_t _hugeCount = 0;
118 bool _tcallScheduled;
119
120private:
121
122 inline void
123 lock() const
124 {
125 lck_mtx_lock(lck: &_mutex);
126 }
127
128 inline void
129 unlock() const
130 {
131 lck_mtx_unlock(lck: &_mutex);
132 }
133
134 inline bool
135 shouldShrink() const
136 {
137 /* shrink if there are more than 2 buckets per 1 symbol */
138 return smr_hash_serialized_should_shrink(smrh: &_hash, min_size: MIN_SIZE, size_factor: 2, count_factor: 1);
139 }
140
141 inline bool
142 shouldGrow() const
143 {
144 /* shrink if there less more than 1 bucket per 4 symbol */
145 return smr_hash_serialized_should_grow(smrh: &_hash, size_factor: 1, count_factor: 4);
146 }
147
148public:
149
150 static void rehash(thread_call_param_t, thread_call_param_t);
151 inline static OSSymbolPool &instance() __pure2;
152
153 OSSymbolPool()
154 {
155 lck_mtx_init(lck: &_mutex, grp: &lock_group, LCK_ATTR_NULL);
156
157 smr_hash_init(smrh: &_hash, size: MIN_SIZE);
158 smrq_init(&_huge_head);
159
160 _tcall = thread_call_allocate_with_options(func: rehash, param0: this,
161 pri: THREAD_CALL_PRIORITY_KERNEL, options: THREAD_CALL_OPTIONS_ONCE);
162 }
163 OSSymbolPool(const OSSymbolPool &) = delete;
164 OSSymbolPool(OSSymbolPool &&) = delete;
165 OSSymbolPool &operator=(const OSSymbolPool &) = delete;
166 OSSymbolPool &operator=(OSSymbolPool &&) = delete;
167
168 ~OSSymbolPool() = delete;
169
170 OSSharedPtr<const OSSymbol> findSymbol(smrh_key_t key) const;
171
172 void insertSymbol(
173 OSSharedPtr<OSSymbol> &sym,
174 smrh_key_t key,
175 bool makePermanent = false);
176
177 void removeSymbol(OSSymbol *sym);
178
179 void rehash();
180
181 void checkForPageUnload(void *startAddr, void *endAddr);
182};
183
184static _Alignas(OSSymbolPool) uint8_t OSSymbolPoolStorage[sizeof(OSSymbolPool)];
185
186OSSymbolPool &
187OSSymbolPool::instance()
188{
189 return reinterpret_cast<OSSymbolPool &>(OSSymbolPoolStorage);
190}
191
192static inline bool
193OSSymbol_is_huge(size_t size)
194{
195 return size > KALLOC_SAFE_ALLOC_SIZE;
196}
197
198OSSharedPtr<const OSSymbol>
199OSSymbolPool::findSymbol(smrh_key_t key) const
200{
201 OSSymbol *sym;
202 OSSharedPtr<const OSSymbol> ret;
203
204 if (!OSSymbol_is_huge(size: key.smrk_len)) {
205 char tmp_buf[128]; /* empirically all keys are < 110 bytes */
206 char *copy_s = NULL;
207
208 /*
209 * rdar://105075708: the key might be in pageable memory,
210 * and smr_hash_get() disable preemption which prevents
211 * faulting the memory.
212 */
213 if (key.smrk_len <= sizeof(tmp_buf)) {
214 memcpy(dst: tmp_buf, src: key.smrk_opaque, n: key.smrk_len);
215 key.smrk_string = tmp_buf;
216 } else {
217 copy_s = (char *)kalloc_data(key.smrk_len,
218 Z_WAITOK_ZERO_NOFAIL);
219 memcpy(dst: copy_s, src: key.smrk_opaque, n: key.smrk_len);
220 key.smrk_string = copy_s;
221 }
222 sym = smr_hash_get(&_hash, key, &hash_traits);
223 if (copy_s) {
224 kfree_data(copy_s, key.smrk_len);
225 }
226 } else {
227 lock();
228 sym = (OSSymbol *)__smr_hash_serialized_find(head: &_huge_head, key,
229 smrht: &hash_traits.smrht);
230 if (sym && !OSSymbol_obj_try_get(obj: sym)) {
231 sym = NULL;
232 }
233 unlock();
234 }
235
236 if (sym) {
237 ret.reset(p: sym, OSNoRetain);
238 }
239
240 return ret;
241}
242
243void
244OSSymbolPool::insertSymbol(
245 OSSharedPtr<OSSymbol> &symToInsert,
246 smrh_key_t key,
247 bool make_permanent)
248{
249 OSSymbol *sym;
250
251 /* make sure no one ever subclassed OSSymbols */
252 zone_require(zone: OSSymbol_zone, addr: symToInsert.get());
253
254 symToInsert->flags |= kOSSSymbolHashed;
255 if (make_permanent) {
256 symToInsert->flags |= kOSSSymbolPermanent;
257 }
258
259 lock();
260
261 if (!OSSymbol_is_huge(size: key.smrk_len)) {
262 sym = smr_hash_serialized_get_or_insert(&_hash, key,
263 &symToInsert->hashlink, &hash_traits);
264
265 if (shouldGrow() && !_tcallScheduled &&
266 startup_phase >= STARTUP_SUB_THREAD_CALL) {
267 _tcallScheduled = true;
268 thread_call_enter(call: _tcall);
269 }
270 } else {
271 sym = (OSSymbol *)__smr_hash_serialized_find(head: &_huge_head, key,
272 smrht: &hash_traits.smrht);
273 if (!sym || !OSSymbol_obj_try_get(obj: sym)) {
274 smrq_serialized_insert_head(&_huge_head,
275 &symToInsert->hashlink);
276 _hugeCount++;
277 sym = NULL;
278 }
279 }
280
281 unlock();
282
283 if (sym) {
284 symToInsert->flags &= ~(kOSSSymbolHashed | kOSSSymbolPermanent);
285 symToInsert.reset(p: sym, OSNoRetain);
286 }
287}
288
289void
290OSSymbolPool::removeSymbol(OSSymbol *sym)
291{
292 lock();
293
294 assert(sym->flags & kOSSSymbolHashed);
295 sym->flags &= ~kOSSSymbolHashed;
296
297 if (!OSSymbol_is_huge(size: sym->length)) {
298 smr_hash_serialized_remove(&_hash, &sym->hashlink, &hash_traits);
299
300 if (shouldShrink() && !_tcallScheduled &&
301 startup_phase >= STARTUP_SUB_THREAD_CALL) {
302 _tcallScheduled = true;
303 thread_call_enter(call: _tcall);
304 }
305 } else {
306 smrq_serialized_remove(&_huge_head, &sym->hashlink);
307 _hugeCount--;
308 }
309
310 unlock();
311}
312
313void
314OSSymbolPool::rehash(thread_call_param_t arg0, thread_call_param_t arg1 __unused)
315{
316 reinterpret_cast<OSSymbolPool *>(arg0)->rehash();
317}
318
319void
320OSSymbolPool::rehash()
321{
322 lock();
323 _tcallScheduled = false;
324
325 if (shouldShrink()) {
326 smr_hash_shrink_and_unlock(&_hash, &_mutex, &hash_traits);
327 } else if (shouldGrow()) {
328 smr_hash_grow_and_unlock(&_hash, &_mutex, &hash_traits);
329 } else {
330 unlock();
331 }
332}
333
334void
335OSSymbolPool::checkForPageUnload(void *startAddr, void *endAddr)
336{
337 OSSymbol *sym;
338 char *s;
339 bool mustSync = false;
340
341 lock();
342 smr_hash_foreach(sym, &_hash, &hash_traits) {
343 if (sym->string >= startAddr && sym->string < endAddr) {
344 assert(sym->flags & kOSStringNoCopy);
345
346 s = (char *)kalloc_data(sym->length,
347 Z_WAITOK_ZERO);
348 if (s) {
349 memcpy(dst: s, src: sym->string, n: sym->length);
350 /*
351 * make sure the memcpy is visible for readers
352 * who dereference `string` below.
353 *
354 * We can't use os_atomic_store(&..., release)
355 * because OSSymbol::string is PACed
356 */
357 os_atomic_thread_fence(release);
358 }
359 sym->string = s;
360 sym->flags &= ~kOSStringNoCopy;
361 mustSync = true;
362 }
363 }
364
365 unlock();
366
367 /* Make sure no readers can see stale pointers that we rewrote */
368 if (mustSync) {
369 smr_iokit_synchronize();
370 }
371}
372
373#pragma clang diagnostic pop /* -Winvalid-offsetof */
374
375/*
376 *********************************************************************
377 * From here on we are actually implementing the OSSymbol class
378 *********************************************************************
379 */
380#define super OSString
381
382OSDefineMetaClassWithInit(OSSymbol, OSString, OSSymbol::initialize());
383OSMetaClassConstructorInit(OSSymbol, OSString, OSSymbol::initialize());
384OSDefineBasicStructors(OSSymbol, OSString)
385OSMetaClassDefineReservedUnused(OSSymbol, 0);
386OSMetaClassDefineReservedUnused(OSSymbol, 1);
387OSMetaClassDefineReservedUnused(OSSymbol, 2);
388OSMetaClassDefineReservedUnused(OSSymbol, 3);
389OSMetaClassDefineReservedUnused(OSSymbol, 4);
390OSMetaClassDefineReservedUnused(OSSymbol, 5);
391OSMetaClassDefineReservedUnused(OSSymbol, 6);
392OSMetaClassDefineReservedUnused(OSSymbol, 7);
393
394static void
395OSSymbol_smr_free(void *sym, vm_size_t size __unused)
396{
397 reinterpret_cast<OSSymbol *>(sym)->smr_free();
398}
399
400void
401OSSymbol::initialize()
402{
403 zone_enable_smr(zone: OSSymbol_zone, smr: &smr_iokit, free_cb: &OSSymbol_smr_free);
404 new (OSSymbolPoolStorage) OSSymbolPool();
405}
406
407bool
408OSSymbol::initWithCStringNoCopy(const char *)
409{
410 return false;
411}
412bool
413OSSymbol::initWithCString(const char *)
414{
415 return false;
416}
417bool
418OSSymbol::initWithString(const OSString *)
419{
420 return false;
421}
422
423OSSharedPtr<const OSSymbol>
424OSSymbol::withString(const OSString *aString)
425{
426 // This string may be a OSSymbol already, cheap check.
427 if (OSDynamicCast(OSSymbol, aString)) {
428 OSSharedPtr<const OSSymbol> aStringNew((const OSSymbol *)aString, OSRetain);
429 return aStringNew;
430 } else if (((const OSSymbol *) aString)->flags & kOSStringNoCopy) {
431 return OSSymbol::withCStringNoCopy(cString: aString->getCStringNoCopy());
432 } else {
433 return OSSymbol::withCString(cString: aString->getCStringNoCopy());
434 }
435}
436
437OSSharedPtr<const OSSymbol>
438OSSymbol::withCString(const char *cString)
439{
440 auto &pool = OSSymbolPool::instance();
441 smrh_key_t key = {
442 .smrk_string = cString,
443 .smrk_len = strnlen(s: cString, n: kMaxStringLength),
444 };
445 bool permanent = false;
446
447 if (key.smrk_len >= kMaxStringLength) {
448 return nullptr;
449 }
450
451 auto symbol = pool.findSymbol(key);
452 if (__probable(symbol)) {
453 return symbol;
454 }
455
456#if defined(KERNEL_INTEGRITY_KTRR) || defined(KERNEL_INTEGRITY_CTRR)
457 /*
458 * Empirically, symbols which string is from the rorgn part of the
459 * kernel are asked about all the time.
460 *
461 * Making them noCopy + permanent avoids a significant amount of
462 * useless refcounting traffic.
463 *
464 * On embedded, this policy causes about 200 extra symbols to be made
465 * from baseline (~6k), but avoiding the string copies saves about 60k.
466 */
467 permanent = rorgn_contains((vm_offset_t)cString, key.smrk_len + 1, false);
468#endif /* defined(KERNEL_INTEGRITY_KTRR) || defined(KERNEL_INTEGRITY_CTRR) */
469
470 /*
471 * can't use OSString::initWithCString* because it calls
472 * OSObject::init() which tries to enroll in IOTracking if it's on.
473 */
474
475 auto newSymb = OSMakeShared<OSSymbol>();
476
477 if (permanent) {
478 newSymb->flags = kOSStringNoCopy;
479 newSymb->length = (uint32_t)(key.smrk_len + 1);
480 newSymb->string = const_cast<char *>(cString);
481 pool.insertSymbol(/* inout */ symToInsert&: newSymb, key, make_permanent: permanent);
482 } else if (char *s = (char *)kalloc_data(key.smrk_len + 1, Z_WAITOK_ZERO)) {
483 memcpy(dst: s, src: cString, n: key.smrk_len);
484 newSymb->flags = 0;
485 newSymb->length = (uint32_t)(key.smrk_len + 1);
486 newSymb->string = s;
487 pool.insertSymbol(/* inout */ symToInsert&: newSymb, key, make_permanent: permanent);
488 } else {
489 newSymb.reset();
490 }
491
492 return os::move(t&: newSymb); // return the newly created & inserted symbol.
493}
494
495OSSharedPtr<const OSSymbol>
496OSSymbol::withCStringNoCopy(const char *cString)
497{
498 auto &pool = OSSymbolPool::instance();
499 smrh_key_t key = {
500 .smrk_string = cString,
501 .smrk_len = strnlen(s: cString, n: kMaxStringLength),
502 };
503 bool permanent = false;
504
505 if (key.smrk_len >= kMaxStringLength) {
506 return nullptr;
507 }
508
509 auto symbol = pool.findSymbol(key);
510 if (__probable(symbol)) {
511 return symbol;
512 }
513
514#if defined(KERNEL_INTEGRITY_KTRR) || defined(KERNEL_INTEGRITY_CTRR)
515 permanent = rorgn_contains((vm_offset_t)cString, key.smrk_len + 1, false);
516#endif /* defined(KERNEL_INTEGRITY_KTRR) || defined(KERNEL_INTEGRITY_CTRR) */
517
518 auto newSymb = OSMakeShared<OSSymbol>();
519
520 /*
521 * can't use OSString::initWithCStringNoCopy because it calls
522 * OSObject::init() which tries to enrol in IOTracking if it's on.
523 */
524 newSymb->flags = kOSStringNoCopy;
525 newSymb->length = (uint32_t)(key.smrk_len + 1);
526 newSymb->string = const_cast<char *>(cString);
527 pool.insertSymbol(/* inout */ symToInsert&: newSymb, key, make_permanent: permanent);
528
529 return os::move(t&: newSymb); // return the newly created & inserted symbol.
530}
531
532OSSharedPtr<const OSSymbol>
533OSSymbol::existingSymbolForString(const OSString *aString)
534{
535 if (!aString) {
536 return NULL;
537 }
538 if (OSDynamicCast(OSSymbol, aString)) {
539 OSSharedPtr<const OSSymbol> aStringNew((const OSSymbol *)aString, OSRetain);
540 return aStringNew;
541 }
542
543 smrh_key_t key = {
544 .smrk_string = aString->getCStringNoCopy(),
545 .smrk_len = aString->getLength(),
546 };
547 return OSSymbolPool::instance().findSymbol(key);
548}
549
550OSSharedPtr<const OSSymbol>
551OSSymbol::existingSymbolForCString(const char *cString)
552{
553 smrh_key_t key = {
554 .smrk_string = cString,
555 .smrk_len = strlen(s: cString),
556 };
557 return OSSymbolPool::instance().findSymbol(key);
558}
559
560void
561OSSymbol::checkForPageUnload(void *startAddr, void *endAddr)
562{
563 OSSymbolPool::instance().checkForPageUnload(startAddr, endAddr);
564}
565
566void
567OSSymbol::taggedRetain(const void *tag) const
568{
569 if ((flags & kOSSSymbolPermanent) == 0) {
570 super::taggedRetain(tag);
571 }
572}
573
574void
575OSSymbol::taggedRelease(const void *tag) const
576{
577 if ((flags & kOSSSymbolPermanent) == 0) {
578 super::taggedRelease(tag);
579 }
580}
581
582void
583OSSymbol::taggedRelease(const void *tag, const int when) const
584{
585 if ((flags & kOSSSymbolPermanent) == 0) {
586 super::taggedRelease(tag, freeWhen: when);
587 }
588}
589
590void *
591OSSymbol::operator new(size_t size __unused)
592{
593 return zalloc_smr(OSSymbol_zone, Z_WAITOK_ZERO_NOFAIL);
594}
595
596void
597OSSymbol::operator delete(void *mem, size_t size)
598{
599 /*
600 * OSSymbol dying is this sequence:
601 *
602 * OSSymbol::taggedRelease() hits 0,
603 * which calls OSSymbol::free(),
604 * which calls zfree_smr().
605 *
606 * At this stage, the memory of the OSSymbol is on a deferred
607 * reclamation queue.
608 *
609 * When the memory is being recycled by zalloc, OSSymbol::smr_free()
610 * is called which terminates with a delete call and only needs
611 * to zero said memory given that the memory has already been
612 * returned to the allocator.
613 */
614 bzero(s: mem, n: size);
615}
616
617void
618OSSymbol::smr_free()
619{
620 /*
621 * This is called when the object is getting reused
622 */
623
624 if (!(flags & kOSStringNoCopy) && string) {
625 kfree_data(string, length);
626 }
627
628 /*
629 * Note: we do not call super::free() on purpose because
630 * it would call OSObject::free() which tries to support
631 * iotracking. iotracking is fundamentally incompatible
632 * with SMR, so we on purpose do not call into these.
633 *
634 * to debug OSSymbol leaks etc, the zone logging feature
635 * can be used instead on the iokit.OSSymbol zone.
636 */
637 OSSymbol::gMetaClass.instanceDestructed();
638
639 delete this;
640}
641
642void
643OSSymbol::free()
644{
645 bool freeNow = true;
646
647 if (flags & kOSSSymbolHashed) {
648 OSSymbolPool::instance().removeSymbol(sym: this);
649 freeNow = OSSymbol_is_huge(size: length);
650 }
651
652 if (freeNow && !(flags & kOSStringNoCopy) && string) {
653 /*
654 * If the element isn't in the hash, it was a failed insertion
655 * racing, and no one will every do a hazardous access,
656 * so we can clean up the string right away.
657 *
658 * If it is huge, then it is not looked up via SMR but under
659 * locks, so we can free right now (actually _must_ because
660 * this free is not preemption disabled safe and can't be done
661 * in smr_free())
662 */
663 kfree_data(string, length);
664 assert(string == nullptr); /* kfree_data nils out */
665 }
666
667 (zfree_smr)(zone: OSSymbol_zone, elem: this);
668}
669
670uint32_t
671OSSymbol::hash() const
672{
673 assert(!OSSymbol_is_huge(length));
674 return os_hash_jenkins(data: string, length: length - 1);
675}
676
677bool
678OSSymbol::isEqualTo(const char *aCString) const
679{
680 return super::isEqualTo(cString: aCString);
681}
682
683bool
684OSSymbol::isEqualTo(const OSSymbol *aSymbol) const
685{
686 return aSymbol == this;
687}
688
689bool
690OSSymbol::isEqualTo(const OSMetaClassBase *obj) const
691{
692 OSSymbol * sym;
693 OSString * str;
694
695 if ((sym = OSDynamicCast(OSSymbol, obj))) {
696 return isEqualTo(aSymbol: sym);
697 } else if ((str = OSDynamicCast(OSString, obj))) {
698 return super::isEqualTo(aString: str);
699 } else {
700 return false;
701 }
702}
703
704unsigned int
705OSSymbol::bsearch(
706 const void * key,
707 const void * array,
708 unsigned int arrayCount,
709 size_t memberSize)
710{
711 const void **p;
712 unsigned int baseIdx = 0;
713 unsigned int lim;
714
715 for (lim = arrayCount; lim; lim >>= 1) {
716 p = (typeof(p))(((uintptr_t) array) + (baseIdx + (lim >> 1)) * memberSize);
717 if (key == *p) {
718 return baseIdx + (lim >> 1);
719 }
720 if (key > *p) {
721 // move right
722 baseIdx += (lim >> 1) + 1;
723 lim--;
724 }
725 // else move left
726 }
727 // not found, insertion point here
728 return baseIdx + (lim >> 1);
729}
730
731#if DEBUG || DEVELOPMENT
732static int
733iokit_symbol_basic_test(int64_t size, int64_t *out)
734{
735 OSSharedPtr<const OSSymbol> sym1;
736 OSSharedPtr<const OSSymbol> sym2;
737 char *data;
738
739 data = (char *)kalloc_data(size, Z_WAITOK);
740 if (!data) {
741 return ENOMEM;
742 }
743
744 memset(data, 'A', size - 1);
745 data[size - 1] = '\0';
746
747 sym1 = OSSymbol::withCString(data);
748 if (sym1 == nullptr) {
749 return ENOMEM;
750 }
751 assert(sym1->getLength() == size - 1);
752
753 sym2 = OSSymbol::withCString(data);
754 assert(sym1 == sym2);
755
756 sym2.reset();
757 sym1.reset();
758
759 *out = 1;
760 return 0;
761}
762SYSCTL_TEST_REGISTER(iokit_symbol_basic, iokit_symbol_basic_test);
763#endif /* DEBUG || DEVELOPMENT */
764