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 { 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        kfree(buckets, nBuckets * sizeof(Bucket));
176        ACCUMSIZE(-(nBuckets * sizeof(Bucket)));
177    }
178
179    if (poolGate)
180        lck_mtx_free(poolGate, IOLockGroup);
181}
182
183unsigned long OSSymbolPool::log2(unsigned int x)
184{
185    unsigned long i;
186
187    for (i = 0; x > 1 ; i++)
188        x >>= 1;
189    return i;
190}
191
192unsigned long OSSymbolPool::exp2ml(unsigned int x)
193{
194    return (1 << x) - 1;
195}
196
197OSSymbolPoolState OSSymbolPool::initHashState()
198{
199    OSSymbolPoolState newState = { nBuckets, 0 };
200    return newState;
201}
202
203OSSymbol *OSSymbolPool::nextHashState(OSSymbolPoolState *stateP)
204{
205    Bucket *thisBucket = &buckets[stateP->i];
206
207    while (!stateP->j) {
208        if (!stateP->i)
209            return 0;
210        stateP->i--;
211        thisBucket--;
212        stateP->j = thisBucket->count;
213    }
214
215    stateP->j--;
216    if (thisBucket->count == 1)
217        return (OSSymbol *) thisBucket->symbolP;
218    else
219        return thisBucket->symbolP[stateP->j];
220}
221
222void OSSymbolPool::reconstructSymbols(void)
223{
224    this->reconstructSymbols(true);
225}
226
227void OSSymbolPool::reconstructSymbols(bool grow)
228{
229    unsigned int new_nBuckets = nBuckets;
230    OSSymbol *insert;
231    OSSymbolPoolState state;
232
233    if (grow) {
234        new_nBuckets += new_nBuckets + 1;
235    } else {
236       /* Don't shrink the pool below the default initial size.
237        */
238        if (nBuckets <= INITIAL_POOL_SIZE) {
239            return;
240        }
241        new_nBuckets = (new_nBuckets - 1) / 2;
242    }
243
244   /* Create old pool to iterate after doing above check, cause it
245    * gets finalized at return.
246    */
247    OSSymbolPool old(this);
248
249    count = 0;
250    nBuckets = new_nBuckets;
251    buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket));
252    ACCUMSIZE(nBuckets * sizeof(Bucket));
253    /* @@@ gvdl: Zero test and panic if can't set up pool */
254    bzero(buckets, nBuckets * sizeof(Bucket));
255
256    state = old.initHashState();
257    while ( (insert = old.nextHashState(&state)) )
258        insertSymbol(insert);
259}
260
261OSSymbol *OSSymbolPool::findSymbol(const char *cString) const
262{
263    Bucket *thisBucket;
264    unsigned int j, inLen, hash;
265    OSSymbol *probeSymbol, **list;
266
267    hashSymbol(cString, &hash, &inLen); inLen++;
268    thisBucket = &buckets[hash % nBuckets];
269    j = thisBucket->count;
270
271    if (!j)
272        return 0;
273
274    if (j == 1) {
275        probeSymbol = (OSSymbol *) thisBucket->symbolP;
276
277        if (inLen == probeSymbol->length
278        &&  (strncmp(probeSymbol->string, cString, probeSymbol->length) == 0))
279            return probeSymbol;
280	return 0;
281    }
282
283    for (list = thisBucket->symbolP; j--; list++) {
284        probeSymbol = *list;
285        if (inLen == probeSymbol->length
286        &&  (strncmp(probeSymbol->string, cString, probeSymbol->length) == 0))
287            return probeSymbol;
288    }
289
290    return 0;
291}
292
293OSSymbol *OSSymbolPool::insertSymbol(OSSymbol *sym)
294{
295    const char *cString = sym->string;
296    Bucket *thisBucket;
297    unsigned int j, inLen, hash;
298    OSSymbol *probeSymbol, **list;
299
300    hashSymbol(cString, &hash, &inLen); inLen++;
301    thisBucket = &buckets[hash % nBuckets];
302    j = thisBucket->count;
303
304    if (!j) {
305        thisBucket->symbolP = (OSSymbol **) sym;
306        thisBucket->count++;
307        count++;
308        return sym;
309    }
310
311    if (j == 1) {
312        probeSymbol = (OSSymbol *) thisBucket->symbolP;
313
314        if (inLen == probeSymbol->length
315        &&  strncmp(probeSymbol->string, cString, probeSymbol->length) == 0)
316            return probeSymbol;
317
318        list = (OSSymbol **) kalloc(2 * sizeof(OSSymbol *));
319        ACCUMSIZE(2 * sizeof(OSSymbol *));
320        /* @@@ gvdl: Zero test and panic if can't set up pool */
321        list[0] = sym;
322        list[1] = probeSymbol;
323        thisBucket->symbolP = list;
324        thisBucket->count++;
325        count++;
326        GROW_POOL();
327
328        return sym;
329    }
330
331    for (list = thisBucket->symbolP; j--; list++) {
332        probeSymbol = *list;
333        if (inLen == probeSymbol->length
334        &&  strncmp(probeSymbol->string, cString, probeSymbol->length) == 0)
335            return probeSymbol;
336    }
337
338    j = thisBucket->count++;
339    count++;
340    list = (OSSymbol **) kalloc(thisBucket->count * sizeof(OSSymbol *));
341    ACCUMSIZE(thisBucket->count * sizeof(OSSymbol *));
342    /* @@@ gvdl: Zero test and panic if can't set up pool */
343    list[0] = sym;
344    bcopy(thisBucket->symbolP, list + 1, j * sizeof(OSSymbol *));
345    kfree(thisBucket->symbolP, j * sizeof(OSSymbol *));
346    ACCUMSIZE(-(j * sizeof(OSSymbol *)));
347    thisBucket->symbolP = list;
348    GROW_POOL();
349
350    return sym;
351}
352
353void OSSymbolPool::removeSymbol(OSSymbol *sym)
354{
355    Bucket *thisBucket;
356    unsigned int j, inLen, hash;
357    OSSymbol *probeSymbol, **list;
358
359    hashSymbol(sym->string, &hash, &inLen); inLen++;
360    thisBucket = &buckets[hash % nBuckets];
361    j = thisBucket->count;
362    list = thisBucket->symbolP;
363
364    if (!j) {
365	// couldn't find the symbol; probably means string hash changed
366        panic("removeSymbol");
367        return;
368    }
369
370    if (j == 1) {
371        probeSymbol = (OSSymbol *) list;
372
373        if (probeSymbol == sym) {
374            thisBucket->symbolP = 0;
375            count--;
376            thisBucket->count--;
377            SHRINK_POOL();
378            return;
379        }
380	// couldn't find the symbol; probably means string hash changed
381    	panic("removeSymbol");
382        return;
383    }
384
385    if (j == 2) {
386        probeSymbol = list[0];
387        if (probeSymbol == sym) {
388            thisBucket->symbolP = (OSSymbol **) list[1];
389            kfree(list, 2 * sizeof(OSSymbol *));
390	    ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
391            count--;
392            thisBucket->count--;
393            SHRINK_POOL();
394            return;
395        }
396
397        probeSymbol = list[1];
398        if (probeSymbol == sym) {
399            thisBucket->symbolP = (OSSymbol **) list[0];
400            kfree(list, 2 * sizeof(OSSymbol *));
401	    ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
402            count--;
403            thisBucket->count--;
404            SHRINK_POOL();
405            return;
406        }
407	// couldn't find the symbol; probably means string hash changed
408    	panic("removeSymbol");
409        return;
410    }
411
412    for (; j--; list++) {
413        probeSymbol = *list;
414        if (probeSymbol == sym) {
415
416            list = (OSSymbol **)
417                kalloc((thisBucket->count-1) * sizeof(OSSymbol *));
418	    ACCUMSIZE((thisBucket->count-1) * sizeof(OSSymbol *));
419            if (thisBucket->count-1 != j)
420                bcopy(thisBucket->symbolP, list,
421                      (thisBucket->count-1-j) * sizeof(OSSymbol *));
422            if (j)
423                bcopy(thisBucket->symbolP + thisBucket->count-j,
424                      list + thisBucket->count-1-j,
425                      j * sizeof(OSSymbol *));
426            kfree(thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *));
427	    ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *)));
428            thisBucket->symbolP = list;
429            count--;
430            thisBucket->count--;
431            return;
432        }
433    }
434    // couldn't find the symbol; probably means string hash changed
435    panic("removeSymbol");
436}
437
438/*
439 *********************************************************************
440 * From here on we are actually implementing the OSSymbol class
441 *********************************************************************
442 */
443OSDefineMetaClassAndStructorsWithInit(OSSymbol, OSString,
444                                      OSSymbol::initialize())
445OSMetaClassDefineReservedUnused(OSSymbol, 0);
446OSMetaClassDefineReservedUnused(OSSymbol, 1);
447OSMetaClassDefineReservedUnused(OSSymbol, 2);
448OSMetaClassDefineReservedUnused(OSSymbol, 3);
449OSMetaClassDefineReservedUnused(OSSymbol, 4);
450OSMetaClassDefineReservedUnused(OSSymbol, 5);
451OSMetaClassDefineReservedUnused(OSSymbol, 6);
452OSMetaClassDefineReservedUnused(OSSymbol, 7);
453
454static OSSymbolPool *pool;
455
456void OSSymbol::initialize()
457{
458    pool = new OSSymbolPool;
459    assert(pool);
460
461    if (!pool->init()) {
462        delete pool;
463        assert(false);
464    };
465}
466
467bool OSSymbol::initWithCStringNoCopy(const char *) { return false; }
468bool OSSymbol::initWithCString(const char *) { return false; }
469bool OSSymbol::initWithString(const OSString *) { return false; }
470
471const OSSymbol *OSSymbol::withString(const OSString *aString)
472{
473    // This string may be a OSSymbol already, cheap check.
474    if (OSDynamicCast(OSSymbol, aString)) {
475	aString->retain();
476	return (const OSSymbol *) aString;
477    }
478    else if (((const OSSymbol *) aString)->flags & kOSStringNoCopy)
479        return OSSymbol::withCStringNoCopy(aString->getCStringNoCopy());
480    else
481        return OSSymbol::withCString(aString->getCStringNoCopy());
482}
483
484const OSSymbol *OSSymbol::withCString(const char *cString)
485{
486    pool->closeGate();
487
488    OSSymbol *oldSymb = pool->findSymbol(cString);
489    if (!oldSymb) {
490        OSSymbol *newSymb = new OSSymbol;
491        if (!newSymb) {
492            pool->openGate();
493            return newSymb;
494        }
495
496	if (newSymb->OSString::initWithCString(cString))
497	    oldSymb = pool->insertSymbol(newSymb);
498
499        if (newSymb == oldSymb) {
500            pool->openGate();
501            return newSymb;	// return the newly created & inserted symbol.
502        }
503        else
504            // Somebody else inserted the new symbol so free our copy
505	    newSymb->OSString::free();
506    }
507
508    oldSymb->retain();	// Retain the old symbol before releasing the lock.
509
510    pool->openGate();
511    return oldSymb;
512}
513
514const OSSymbol *OSSymbol::withCStringNoCopy(const char *cString)
515{
516    pool->closeGate();
517
518    OSSymbol *oldSymb = pool->findSymbol(cString);
519    if (!oldSymb) {
520        OSSymbol *newSymb = new OSSymbol;
521        if (!newSymb) {
522            pool->openGate();
523            return newSymb;
524        }
525
526	if (newSymb->OSString::initWithCStringNoCopy(cString))
527	    oldSymb = pool->insertSymbol(newSymb);
528
529        if (newSymb == oldSymb) {
530            pool->openGate();
531            return newSymb;	// return the newly created & inserted symbol.
532        }
533        else
534            // Somebody else inserted the new symbol so free our copy
535	    newSymb->OSString::free();
536    }
537
538    oldSymb->retain();	// Retain the old symbol before releasing the lock.
539
540    pool->openGate();
541    return oldSymb;
542}
543
544void OSSymbol::checkForPageUnload(void *startAddr, void *endAddr)
545{
546    OSSymbol *probeSymbol;
547    OSSymbolPoolState state;
548
549    pool->closeGate();
550    state = pool->initHashState();
551    while ( (probeSymbol = pool->nextHashState(&state)) ) {
552        if (probeSymbol->string >= startAddr && probeSymbol->string < endAddr) {
553            const char *oldString = probeSymbol->string;
554
555            probeSymbol->string = (char *) kalloc(probeSymbol->length);
556	    ACCUMSIZE(probeSymbol->length);
557            bcopy(oldString, probeSymbol->string, probeSymbol->length);
558            probeSymbol->flags &= ~kOSStringNoCopy;
559        }
560    }
561    pool->openGate();
562}
563
564void OSSymbol::taggedRelease(const void *tag) const
565{
566    super::taggedRelease(tag);
567}
568
569void OSSymbol::taggedRelease(const void *tag, const int when) const
570{
571    pool->closeGate();
572    super::taggedRelease(tag, when);
573    pool->openGate();
574}
575
576void OSSymbol::free()
577{
578    pool->removeSymbol(this);
579    super::free();
580}
581
582bool OSSymbol::isEqualTo(const char *aCString) const
583{
584    return super::isEqualTo(aCString);
585}
586
587bool OSSymbol::isEqualTo(const OSSymbol *aSymbol) const
588{
589    return aSymbol == this;
590}
591
592bool OSSymbol::isEqualTo(const OSMetaClassBase *obj) const
593{
594    OSSymbol *	sym;
595    OSString *	str;
596
597    if ((sym = OSDynamicCast(OSSymbol, obj)))
598	return isEqualTo(sym);
599    else if ((str = OSDynamicCast(OSString, obj)))
600	return super::isEqualTo(str);
601    else
602	return false;
603}
604
605unsigned int
606OSSymbol::bsearch(
607	const void *  key,
608	const void *  array,
609	unsigned int  arrayCount,
610	size_t        memberSize)
611{
612    const void **p;
613    unsigned int baseIdx = 0;
614    unsigned int lim;
615
616    for (lim = arrayCount; lim; lim >>= 1)
617    {
618	p = (typeof(p)) (((uintptr_t) array) + (baseIdx + (lim >> 1)) * memberSize);
619	if (key == *p)
620	{
621	    return (baseIdx + (lim >> 1));
622	}
623	if (key > *p)
624	{
625	    // move right
626	    baseIdx += (lim >> 1) + 1;
627	    lim--;
628	}
629	// else move left
630    }
631    // not found, insertion point here
632    return (baseIdx + (lim >> 1));
633}
634