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 | |
50 | static ZONE_DEFINE(OSSymbol_zone, "iokit.OSSymbol" , sizeof(OSSymbol), ZC_NONE); |
51 | static 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 | */ |
68 | class 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 | |
120 | private: |
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 | |
148 | public: |
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 | |
184 | static _Alignas(OSSymbolPool) uint8_t OSSymbolPoolStorage[sizeof(OSSymbolPool)]; |
185 | |
186 | OSSymbolPool & |
187 | OSSymbolPool::instance() |
188 | { |
189 | return reinterpret_cast<OSSymbolPool &>(OSSymbolPoolStorage); |
190 | } |
191 | |
192 | static inline bool |
193 | OSSymbol_is_huge(size_t size) |
194 | { |
195 | return size > KALLOC_SAFE_ALLOC_SIZE; |
196 | } |
197 | |
198 | OSSharedPtr<const OSSymbol> |
199 | OSSymbolPool::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 | |
243 | void |
244 | OSSymbolPool::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 | |
289 | void |
290 | OSSymbolPool::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 | |
313 | void |
314 | OSSymbolPool::rehash(thread_call_param_t arg0, thread_call_param_t arg1 __unused) |
315 | { |
316 | reinterpret_cast<OSSymbolPool *>(arg0)->rehash(); |
317 | } |
318 | |
319 | void |
320 | OSSymbolPool::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 | |
334 | void |
335 | OSSymbolPool::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 | |
382 | OSDefineMetaClassWithInit(OSSymbol, OSString, OSSymbol::initialize()); |
383 | OSMetaClassConstructorInit(OSSymbol, OSString, OSSymbol::initialize()); |
384 | OSDefineBasicStructors(OSSymbol, OSString) |
385 | OSMetaClassDefineReservedUnused(OSSymbol, 0); |
386 | OSMetaClassDefineReservedUnused(OSSymbol, 1); |
387 | OSMetaClassDefineReservedUnused(OSSymbol, 2); |
388 | OSMetaClassDefineReservedUnused(OSSymbol, 3); |
389 | OSMetaClassDefineReservedUnused(OSSymbol, 4); |
390 | OSMetaClassDefineReservedUnused(OSSymbol, 5); |
391 | OSMetaClassDefineReservedUnused(OSSymbol, 6); |
392 | OSMetaClassDefineReservedUnused(OSSymbol, 7); |
393 | |
394 | static void |
395 | OSSymbol_smr_free(void *sym, vm_size_t size __unused) |
396 | { |
397 | reinterpret_cast<OSSymbol *>(sym)->smr_free(); |
398 | } |
399 | |
400 | void |
401 | OSSymbol::initialize() |
402 | { |
403 | zone_enable_smr(zone: OSSymbol_zone, smr: &smr_iokit, free_cb: &OSSymbol_smr_free); |
404 | new (OSSymbolPoolStorage) OSSymbolPool(); |
405 | } |
406 | |
407 | bool |
408 | OSSymbol::initWithCStringNoCopy(const char *) |
409 | { |
410 | return false; |
411 | } |
412 | bool |
413 | OSSymbol::initWithCString(const char *) |
414 | { |
415 | return false; |
416 | } |
417 | bool |
418 | OSSymbol::initWithString(const OSString *) |
419 | { |
420 | return false; |
421 | } |
422 | |
423 | OSSharedPtr<const OSSymbol> |
424 | OSSymbol::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 | |
437 | OSSharedPtr<const OSSymbol> |
438 | OSSymbol::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 | |
495 | OSSharedPtr<const OSSymbol> |
496 | OSSymbol::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 | |
532 | OSSharedPtr<const OSSymbol> |
533 | OSSymbol::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 | |
550 | OSSharedPtr<const OSSymbol> |
551 | OSSymbol::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 | |
560 | void |
561 | OSSymbol::checkForPageUnload(void *startAddr, void *endAddr) |
562 | { |
563 | OSSymbolPool::instance().checkForPageUnload(startAddr, endAddr); |
564 | } |
565 | |
566 | void |
567 | OSSymbol::taggedRetain(const void *tag) const |
568 | { |
569 | if ((flags & kOSSSymbolPermanent) == 0) { |
570 | super::taggedRetain(tag); |
571 | } |
572 | } |
573 | |
574 | void |
575 | OSSymbol::taggedRelease(const void *tag) const |
576 | { |
577 | if ((flags & kOSSSymbolPermanent) == 0) { |
578 | super::taggedRelease(tag); |
579 | } |
580 | } |
581 | |
582 | void |
583 | OSSymbol::taggedRelease(const void *tag, const int when) const |
584 | { |
585 | if ((flags & kOSSSymbolPermanent) == 0) { |
586 | super::taggedRelease(tag, freeWhen: when); |
587 | } |
588 | } |
589 | |
590 | void * |
591 | OSSymbol::operator new(size_t size __unused) |
592 | { |
593 | return zalloc_smr(OSSymbol_zone, Z_WAITOK_ZERO_NOFAIL); |
594 | } |
595 | |
596 | void |
597 | OSSymbol::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 | |
617 | void |
618 | OSSymbol::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 | |
642 | void |
643 | OSSymbol::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 | |
670 | uint32_t |
671 | OSSymbol::hash() const |
672 | { |
673 | assert(!OSSymbol_is_huge(length)); |
674 | return os_hash_jenkins(data: string, length: length - 1); |
675 | } |
676 | |
677 | bool |
678 | OSSymbol::isEqualTo(const char *aCString) const |
679 | { |
680 | return super::isEqualTo(cString: aCString); |
681 | } |
682 | |
683 | bool |
684 | OSSymbol::isEqualTo(const OSSymbol *aSymbol) const |
685 | { |
686 | return aSymbol == this; |
687 | } |
688 | |
689 | bool |
690 | OSSymbol::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 | |
704 | unsigned int |
705 | OSSymbol::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 |
732 | static int |
733 | iokit_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 | } |
762 | SYSCTL_TEST_REGISTER(iokit_symbol_basic, iokit_symbol_basic_test); |
763 | #endif /* DEBUG || DEVELOPMENT */ |
764 | |