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