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