xref: /xnu-11215/libkern/c++/OSSymbol.cpp (revision e13b1fa5) 
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 
43 typedef struct { int i, j; } OSSymbolPoolState;
44 
45 #if OSALLOCDEBUG
46 extern "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     } \
63 while (0)
64 
65 #define SHRINK_POOL()     do \
66     if (count * SHRINK_FACTOR < nBuckets && \
67         nBuckets > INITIAL_POOL_SIZE) { \
68         reconstructSymbols(false); \
69     } \
70 while (0)
71 
72 class OSSymbolPool
73 {
74 private:
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 
108 public:
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 
129 void * 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 
139 void OSSymbolPool::operator delete(void *mem, size_t size)
140 {
141     kfree(mem, size);
142     ACCUMSIZE(-size);
143 }
144 
145 bool 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 
161 OSSymbolPool::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 
170 OSSymbolPool::~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 
181 unsigned 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 
190 unsigned long OSSymbolPool::exp2ml(unsigned int x)
191 {
192     return (1 << x) - 1;
193 }
194 
195 OSSymbolPoolState OSSymbolPool::initHashState()
196 {
197     OSSymbolPoolState newState = { nBuckets, 0 };
198     return newState;
199 }
200 
201 OSSymbol *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 
220 void OSSymbolPool::reconstructSymbols(void)
221 {
222     this->reconstructSymbols(true);
223 }
224 
225 void 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 
259 OSSymbol *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 
291 OSSymbol *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 
351 void 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  */
432 OSDefineMetaClassAndStructorsWithInit(OSSymbol, OSString,
433                                       OSSymbol::initialize())
434 OSMetaClassDefineReservedUnused(OSSymbol, 0);
435 OSMetaClassDefineReservedUnused(OSSymbol, 1);
436 OSMetaClassDefineReservedUnused(OSSymbol, 2);
437 OSMetaClassDefineReservedUnused(OSSymbol, 3);
438 OSMetaClassDefineReservedUnused(OSSymbol, 4);
439 OSMetaClassDefineReservedUnused(OSSymbol, 5);
440 OSMetaClassDefineReservedUnused(OSSymbol, 6);
441 OSMetaClassDefineReservedUnused(OSSymbol, 7);
442 
443 static OSSymbolPool *pool;
444 
445 void OSSymbol::initialize()
446 {
447     pool = new OSSymbolPool;
448     assert(pool);
449 
450     if (!pool->init()) {
451         delete pool;
452         assert(false);
453     };
454 }
455 
456 bool OSSymbol::initWithCStringNoCopy(const char *) { return false; }
457 bool OSSymbol::initWithCString(const char *) { return false; }
458 bool OSSymbol::initWithString(const OSString *) { return false; }
459 
460 const 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 
473 const 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 
503 const 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 
533 void 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 
553 void OSSymbol::taggedRelease(const void *tag) const
554 {
555     super::taggedRelease(tag);
556 }
557 
558 void OSSymbol::taggedRelease(const void *tag, const int when) const
559 {
560     pool->closeGate();
561     super::taggedRelease(tag, when);
562     pool->openGate();
563 }
564 
565 void OSSymbol::free()
566 {
567     pool->removeSymbol(this);
568     super::free();
569 }
570 
571 bool OSSymbol::isEqualTo(const char *aCString) const
572 {
573     return super::isEqualTo(aCString);
574 }
575 
576 bool OSSymbol::isEqualTo(const OSSymbol *aSymbol) const
577 {
578     return aSymbol == this;
579 }
580 
581 bool 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