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