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