Loading...
--- xnu/xnu-3247.10.11/libkern/c++/OSSymbol.cpp
+++ xnu/xnu-201/libkern/c++/OSSymbol.cpp
@@ -1,62 +1,47 @@
/*
- * Copyright (c) 2000-2007 Apple Inc. All rights reserved.
+ * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
*
- * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
+ * @APPLE_LICENSE_HEADER_START@
*
- * This file contains Original Code and/or Modifications of Original Code
- * as defined in and that are subject to the Apple Public Source License
- * Version 2.0 (the 'License'). You may not use this file except in
- * compliance with the License. The rights granted to you under the License
- * may not be used to create, or enable the creation or redistribution of,
- * unlawful or unlicensed copies of an Apple operating system, or to
- * circumvent, violate, or enable the circumvention or violation of, any
- * terms of an Apple operating system software license agreement.
+ * The contents of this file constitute Original Code as defined in and
+ * are subject to the Apple Public Source License Version 1.1 (the
+ * "License"). You may not use this file except in compliance with the
+ * License. Please obtain a copy of the License at
+ * http://www.apple.com/publicsource and read it before using this file.
*
- * Please obtain a copy of the License at
- * http://www.opensource.apple.com/apsl/ and read it before using this file.
- *
- * The Original Code and all software distributed under the License are
- * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * This Original Code and all software distributed under the License are
+ * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
- * Please see the License for the specific language governing rights and
- * limitations under the License.
+ * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
+ * License for the specific language governing rights and limitations
+ * under the License.
*
- * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
+ * @APPLE_LICENSE_HEADER_END@
*/
/* IOSymbol.cpp created by gvdl on Fri 1998-11-17 */
-#include <string.h>
#include <sys/cdefs.h>
-#include <kern/locks.h>
+__BEGIN_DECLS
+#include <kern/lock.h>
+__END_DECLS
#include <libkern/c++/OSSymbol.h>
#include <libkern/c++/OSLib.h>
-#include <string.h>
#define super OSString
-typedef struct { unsigned int i, j; } OSSymbolPoolState;
-
-#define INITIAL_POOL_SIZE (exp2ml(1 + log2(kInitBucketCount)))
-
-#define GROW_FACTOR (1)
-#define SHRINK_FACTOR (3)
-
-#define GROW_POOL() do \
- if (count * GROW_FACTOR > nBuckets) { \
- reconstructSymbols(true); \
- } \
-while (0)
-
-#define SHRINK_POOL() do \
- if (count * SHRINK_FACTOR < nBuckets && \
- nBuckets > INITIAL_POOL_SIZE) { \
- reconstructSymbols(false); \
- } \
-while (0)
+typedef struct { int i, j; } OSSymbolPoolState;
+
+#if OSALLOCDEBUG
+extern "C" {
+ extern int debug_container_malloc_size;
+};
+#define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0)
+#else
+#define ACCUMSIZE(s)
+#endif
class OSSymbolPool
{
@@ -68,7 +53,7 @@
Bucket *buckets;
unsigned int nBuckets;
unsigned int count;
- lck_mtx_t *poolGate;
+ mutex_t *poolGate;
static inline void hashSymbol(const char *s,
unsigned int *hashP,
@@ -91,8 +76,7 @@
static unsigned long log2(unsigned int x);
static unsigned long exp2ml(unsigned int x);
- void reconstructSymbols(void);
- void reconstructSymbols(bool grow);
+ void reconstructSymbols();
public:
static void *operator new(size_t size);
@@ -104,12 +88,12 @@
bool init();
- inline void closeGate() { lck_mtx_lock(poolGate); };
- inline void openGate() { lck_mtx_unlock(poolGate); };
+ inline void closeGate() { mutex_lock(poolGate); };
+ inline void openGate() { mutex_unlock(poolGate); };
OSSymbol *findSymbol(const char *cString) const;
OSSymbol *insertSymbol(OSSymbol *sym);
- void removeSymbol(OSSymbol *sym);
+ void removeSymbol(const char *cString);
OSSymbolPoolState initHashState();
OSSymbol *nextHashState(OSSymbolPoolState *stateP);
@@ -117,8 +101,8 @@
void * OSSymbolPool::operator new(size_t size)
{
- void *mem = (void *)kalloc_tag(size, VM_KERN_MEMORY_LIBKERN);
- OSMETA_ACCUMSIZE(size);
+ void *mem = (void *)kalloc(size);
+ ACCUMSIZE(size);
assert(mem);
bzero(mem, size);
@@ -127,24 +111,22 @@
void OSSymbolPool::operator delete(void *mem, size_t size)
{
- kfree(mem, size);
- OSMETA_ACCUMSIZE(-size);
-}
-
-extern lck_grp_t *IOLockGroup;
+ kfree((vm_offset_t)mem, size);
+ ACCUMSIZE(-size);
+}
bool OSSymbolPool::init()
{
count = 0;
- nBuckets = INITIAL_POOL_SIZE;
- buckets = (Bucket *) kalloc_tag(nBuckets * sizeof(Bucket), VM_KERN_MEMORY_LIBKERN);
- OSMETA_ACCUMSIZE(nBuckets * sizeof(Bucket));
+ nBuckets = exp2ml(1 + log2(kInitBucketCount));
+ buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket));
+ ACCUMSIZE(nBuckets * sizeof(Bucket));
if (!buckets)
return false;
bzero(buckets, nBuckets * sizeof(Bucket));
- poolGate = lck_mtx_alloc_init(IOLockGroup, LCK_ATTR_NULL);
+ poolGate = mutex_alloc(0);
return poolGate != 0;
}
@@ -161,19 +143,12 @@
OSSymbolPool::~OSSymbolPool()
{
if (buckets) {
- Bucket *thisBucket;
- for (thisBucket = &buckets[0]; thisBucket < &buckets[nBuckets]; thisBucket++) {
- if (thisBucket->count > 1) {
- kfree(thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *));
- OSMETA_ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *)));
- }
- }
- kfree(buckets, nBuckets * sizeof(Bucket));
- OSMETA_ACCUMSIZE(-(nBuckets * sizeof(Bucket)));
+ kfree((vm_offset_t)buckets, nBuckets * sizeof(Bucket));
+ ACCUMSIZE(-(nBuckets * sizeof(Bucket)));
}
if (poolGate)
- lck_mtx_free(poolGate, IOLockGroup);
+ kfree((vm_offset_t) poolGate, 36 * 4);
}
unsigned long OSSymbolPool::log2(unsigned int x)
@@ -215,37 +190,16 @@
return thisBucket->symbolP[stateP->j];
}
-void OSSymbolPool::reconstructSymbols(void)
-{
- this->reconstructSymbols(true);
-}
-
-void OSSymbolPool::reconstructSymbols(bool grow)
-{
- unsigned int new_nBuckets = nBuckets;
+void OSSymbolPool::reconstructSymbols()
+{
+ OSSymbolPool old(this);
OSSymbol *insert;
OSSymbolPoolState state;
- if (grow) {
- new_nBuckets += new_nBuckets + 1;
- } else {
- /* Don't shrink the pool below the default initial size.
- */
- if (nBuckets <= INITIAL_POOL_SIZE) {
- return;
- }
- new_nBuckets = (new_nBuckets - 1) / 2;
- }
-
- /* Create old pool to iterate after doing above check, cause it
- * gets finalized at return.
- */
- OSSymbolPool old(this);
-
+ nBuckets += nBuckets + 1;
count = 0;
- nBuckets = new_nBuckets;
- buckets = (Bucket *) kalloc_tag(nBuckets * sizeof(Bucket), VM_KERN_MEMORY_LIBKERN);
- OSMETA_ACCUMSIZE(nBuckets * sizeof(Bucket));
+ buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket));
+ ACCUMSIZE(nBuckets * sizeof(Bucket));
/* @@@ gvdl: Zero test and panic if can't set up pool */
bzero(buckets, nBuckets * sizeof(Bucket));
@@ -271,15 +225,18 @@
probeSymbol = (OSSymbol *) thisBucket->symbolP;
if (inLen == probeSymbol->length
- && (strncmp(probeSymbol->string, cString, probeSymbol->length) == 0))
+ && (strcmp(probeSymbol->string, cString) == 0)
+ && (probeSymbol->getRetainCount() >= 1)) // WRONG need when
return probeSymbol;
- return 0;
+ else
+ return 0;
}
for (list = thisBucket->symbolP; j--; list++) {
probeSymbol = *list;
if (inLen == probeSymbol->length
- && (strncmp(probeSymbol->string, cString, probeSymbol->length) == 0))
+ && (strcmp(probeSymbol->string, cString) == 0)
+ && (probeSymbol->getRetainCount() >= 1)) // WRONG need when
return probeSymbol;
}
@@ -301,117 +258,113 @@
thisBucket->symbolP = (OSSymbol **) sym;
thisBucket->count++;
count++;
- return sym;
+ return 0;
}
if (j == 1) {
probeSymbol = (OSSymbol *) thisBucket->symbolP;
if (inLen == probeSymbol->length
- && strncmp(probeSymbol->string, cString, probeSymbol->length) == 0)
+ && strcmp(probeSymbol->string, cString) == 0)
return probeSymbol;
- list = (OSSymbol **) kalloc_tag(2 * sizeof(OSSymbol *), VM_KERN_MEMORY_LIBKERN);
- OSMETA_ACCUMSIZE(2 * sizeof(OSSymbol *));
+ list = (OSSymbol **) kalloc(2 * sizeof(OSSymbol *));
+ ACCUMSIZE(2 * sizeof(OSSymbol *));
/* @@@ gvdl: Zero test and panic if can't set up pool */
list[0] = sym;
list[1] = probeSymbol;
thisBucket->symbolP = list;
thisBucket->count++;
count++;
- GROW_POOL();
-
- return sym;
+ if (count > nBuckets)
+ reconstructSymbols();
+
+ return 0;
}
for (list = thisBucket->symbolP; j--; list++) {
probeSymbol = *list;
if (inLen == probeSymbol->length
- && strncmp(probeSymbol->string, cString, probeSymbol->length) == 0)
+ && strcmp(probeSymbol->string, cString) == 0)
return probeSymbol;
}
j = thisBucket->count++;
count++;
- list = (OSSymbol **) kalloc_tag(thisBucket->count * sizeof(OSSymbol *), VM_KERN_MEMORY_LIBKERN);
- OSMETA_ACCUMSIZE(thisBucket->count * sizeof(OSSymbol *));
+ list = (OSSymbol **) kalloc(thisBucket->count * sizeof(OSSymbol *));
+ ACCUMSIZE(thisBucket->count * sizeof(OSSymbol *));
/* @@@ gvdl: Zero test and panic if can't set up pool */
list[0] = sym;
bcopy(thisBucket->symbolP, list + 1, j * sizeof(OSSymbol *));
- kfree(thisBucket->symbolP, j * sizeof(OSSymbol *));
- OSMETA_ACCUMSIZE(-(j * sizeof(OSSymbol *)));
+ kfree((vm_offset_t)thisBucket->symbolP, j * sizeof(OSSymbol *));
+ ACCUMSIZE(-(j * sizeof(OSSymbol *)));
thisBucket->symbolP = list;
- GROW_POOL();
-
- return sym;
-}
-
-void OSSymbolPool::removeSymbol(OSSymbol *sym)
+ if (count > nBuckets)
+ reconstructSymbols();
+
+ return 0;
+}
+
+void OSSymbolPool::removeSymbol(const char *cString)
{
Bucket *thisBucket;
unsigned int j, inLen, hash;
OSSymbol *probeSymbol, **list;
- hashSymbol(sym->string, &hash, &inLen); inLen++;
+ hashSymbol(cString, &hash, &inLen); inLen++;
thisBucket = &buckets[hash % nBuckets];
j = thisBucket->count;
list = thisBucket->symbolP;
- if (!j) {
- // couldn't find the symbol; probably means string hash changed
- panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
+ if (!j)
return;
- }
if (j == 1) {
probeSymbol = (OSSymbol *) list;
- if (probeSymbol == sym) {
+ if (inLen == probeSymbol->length
+ && strcmp(probeSymbol->string, cString) == 0) {
thisBucket->symbolP = 0;
count--;
thisBucket->count--;
- SHRINK_POOL();
return;
}
- // couldn't find the symbol; probably means string hash changed
- panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
return;
}
if (j == 2) {
probeSymbol = list[0];
- if (probeSymbol == sym) {
+ if (inLen == probeSymbol->length
+ && strcmp(probeSymbol->string, cString) == 0) {
thisBucket->symbolP = (OSSymbol **) list[1];
- kfree(list, 2 * sizeof(OSSymbol *));
- OSMETA_ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
+ kfree((vm_offset_t)list, 2 * sizeof(OSSymbol *));
+ ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
count--;
thisBucket->count--;
- SHRINK_POOL();
return;
}
probeSymbol = list[1];
- if (probeSymbol == sym) {
+ if (inLen == probeSymbol->length
+ && strcmp(probeSymbol->string, cString) == 0) {
thisBucket->symbolP = (OSSymbol **) list[0];
- kfree(list, 2 * sizeof(OSSymbol *));
- OSMETA_ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
+ kfree((vm_offset_t)list, 2 * sizeof(OSSymbol *));
+ ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
count--;
thisBucket->count--;
- SHRINK_POOL();
return;
}
- // couldn't find the symbol; probably means string hash changed
- panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
return;
}
for (; j--; list++) {
probeSymbol = *list;
- if (probeSymbol == sym) {
+ if (inLen == probeSymbol->length
+ && strcmp(probeSymbol->string, cString) == 0) {
list = (OSSymbol **)
- kalloc_tag((thisBucket->count-1) * sizeof(OSSymbol *), VM_KERN_MEMORY_LIBKERN);
- OSMETA_ACCUMSIZE((thisBucket->count-1) * sizeof(OSSymbol *));
+ kalloc((thisBucket->count-1) * sizeof(OSSymbol *));
+ ACCUMSIZE((thisBucket->count-1) * sizeof(OSSymbol *));
if (thisBucket->count-1 != j)
bcopy(thisBucket->symbolP, list,
(thisBucket->count-1-j) * sizeof(OSSymbol *));
@@ -419,16 +372,14 @@
bcopy(thisBucket->symbolP + thisBucket->count-j,
list + thisBucket->count-1-j,
j * sizeof(OSSymbol *));
- kfree(thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *));
- OSMETA_ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *)));
+ kfree((vm_offset_t)thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *));
+ ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *)));
thisBucket->symbolP = list;
count--;
thisBucket->count--;
return;
}
}
- // couldn't find the symbol; probably means string hash changed
- panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
}
/*
@@ -454,7 +405,7 @@
pool = new OSSymbolPool;
assert(pool);
- if (pool && !pool->init()) {
+ if (!pool->init()) {
delete pool;
assert(false);
};
@@ -481,60 +432,40 @@
{
pool->closeGate();
- OSSymbol *oldSymb = pool->findSymbol(cString);
- if (!oldSymb) {
- OSSymbol *newSymb = new OSSymbol;
- if (!newSymb) {
- pool->openGate();
- return newSymb;
- }
-
+ OSSymbol *newSymb = pool->findSymbol(cString);
+ if (newSymb)
+ newSymb->retain();
+ else if ( (newSymb = new OSSymbol) ) {
if (newSymb->OSString::initWithCString(cString))
- oldSymb = pool->insertSymbol(newSymb);
-
- if (newSymb == oldSymb) {
- pool->openGate();
- return newSymb; // return the newly created & inserted symbol.
- }
- else
- // Somebody else inserted the new symbol so free our copy
- newSymb->OSString::free();
- }
-
- oldSymb->retain(); // Retain the old symbol before releasing the lock.
-
+ pool->insertSymbol(newSymb);
+ else {
+ newSymb->free();
+ newSymb = 0;
+ }
+ }
pool->openGate();
- return oldSymb;
+
+ return newSymb;
}
const OSSymbol *OSSymbol::withCStringNoCopy(const char *cString)
{
pool->closeGate();
- OSSymbol *oldSymb = pool->findSymbol(cString);
- if (!oldSymb) {
- OSSymbol *newSymb = new OSSymbol;
- if (!newSymb) {
- pool->openGate();
- return newSymb;
- }
-
+ OSSymbol *newSymb = pool->findSymbol(cString);
+ if (newSymb)
+ newSymb->retain();
+ else if ( (newSymb = new OSSymbol) ) {
if (newSymb->OSString::initWithCStringNoCopy(cString))
- oldSymb = pool->insertSymbol(newSymb);
-
- if (newSymb == oldSymb) {
- pool->openGate();
- return newSymb; // return the newly created & inserted symbol.
- }
- else
- // Somebody else inserted the new symbol so free our copy
- newSymb->OSString::free();
- }
-
- oldSymb->retain(); // Retain the old symbol before releasing the lock.
-
+ pool->insertSymbol(newSymb);
+ else {
+ newSymb->free();
+ newSymb = 0;
+ }
+ }
pool->openGate();
- return oldSymb;
+
+ return newSymb;
}
void OSSymbol::checkForPageUnload(void *startAddr, void *endAddr)
@@ -546,27 +477,23 @@
state = pool->initHashState();
while ( (probeSymbol = pool->nextHashState(&state)) ) {
if (probeSymbol->string >= startAddr && probeSymbol->string < endAddr) {
- probeSymbol->OSString::initWithCString(probeSymbol->string);
+ const char *oldString = probeSymbol->string;
+
+ probeSymbol->string = (char *) kalloc(probeSymbol->length);
+ ACCUMSIZE(probeSymbol->length);
+ bcopy(oldString, probeSymbol->string, probeSymbol->length);
+ probeSymbol->flags &= ~kOSStringNoCopy;
}
}
pool->openGate();
}
-void OSSymbol::taggedRelease(const void *tag) const
-{
- super::taggedRelease(tag);
-}
-
-void OSSymbol::taggedRelease(const void *tag, const int when) const
+void OSSymbol::free()
{
pool->closeGate();
- super::taggedRelease(tag, when);
+ pool->removeSymbol(string);
pool->openGate();
-}
-
-void OSSymbol::free()
-{
- pool->removeSymbol(this);
+
super::free();
}
@@ -592,33 +519,3 @@
else
return false;
}
-
-unsigned int
-OSSymbol::bsearch(
- const void * key,
- const void * array,
- unsigned int arrayCount,
- size_t memberSize)
-{
- const void **p;
- unsigned int baseIdx = 0;
- unsigned int lim;
-
- for (lim = arrayCount; lim; lim >>= 1)
- {
- p = (typeof(p)) (((uintptr_t) array) + (baseIdx + (lim >> 1)) * memberSize);
- if (key == *p)
- {
- return (baseIdx + (lim >> 1));
- }
- if (key > *p)
- {
- // move right
- baseIdx += (lim >> 1) + 1;
- lim--;
- }
- // else move left
- }
- // not found, insertion point here
- return (baseIdx + (lim >> 1));
-}