Loading...
--- xnu/xnu-1228/libkern/c++/OSSymbol.cpp
+++ xnu/xnu-4570.71.2/libkern/c++/OSSymbol.cpp
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2000-2007 Apple Inc. All rights reserved.
+ * Copyright (c) 2000-2016 Apple Inc. All rights reserved.
*
* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
*
@@ -30,9 +30,7 @@
#include <string.h>
#include <sys/cdefs.h>
-__BEGIN_DECLS
-#include <kern/lock.h>
-__END_DECLS
+#include <kern/locks.h>
#include <libkern/c++/OSSymbol.h>
#include <libkern/c++/OSLib.h>
@@ -40,16 +38,7 @@
#define super OSString
-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
+typedef struct { unsigned int i, j; } OSSymbolPoolState;
#define INITIAL_POOL_SIZE (exp2ml(1 + log2(kInitBucketCount)))
@@ -79,7 +68,7 @@
Bucket *buckets;
unsigned int nBuckets;
unsigned int count;
- mutex_t *poolGate;
+ lck_mtx_t *poolGate;
static inline void hashSymbol(const char *s,
unsigned int *hashP,
@@ -109,14 +98,14 @@
static void *operator new(size_t size);
static void operator delete(void *mem, size_t size);
- OSSymbolPool() { };
+ OSSymbolPool() { }
OSSymbolPool(const OSSymbolPool *old);
virtual ~OSSymbolPool();
bool init();
- inline void closeGate() { mutex_lock(poolGate); };
- inline void openGate() { mutex_unlock(poolGate); };
+ inline void closeGate() { lck_mtx_lock(poolGate); }
+ inline void openGate() { lck_mtx_unlock(poolGate); }
OSSymbol *findSymbol(const char *cString) const;
OSSymbol *insertSymbol(OSSymbol *sym);
@@ -128,8 +117,8 @@
void * OSSymbolPool::operator new(size_t size)
{
- void *mem = (void *)kalloc(size);
- ACCUMSIZE(size);
+ void *mem = (void *)kalloc_tag(size, VM_KERN_MEMORY_LIBKERN);
+ OSMETA_ACCUMSIZE(size);
assert(mem);
bzero(mem, size);
@@ -139,21 +128,23 @@
void OSSymbolPool::operator delete(void *mem, size_t size)
{
kfree(mem, size);
- ACCUMSIZE(-size);
-}
+ OSMETA_ACCUMSIZE(-size);
+}
+
+extern lck_grp_t *IOLockGroup;
bool OSSymbolPool::init()
{
count = 0;
nBuckets = INITIAL_POOL_SIZE;
- buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket));
- ACCUMSIZE(nBuckets * sizeof(Bucket));
+ buckets = (Bucket *) kalloc_tag(nBuckets * sizeof(Bucket), VM_KERN_MEMORY_LIBKERN);
+ OSMETA_ACCUMSIZE(nBuckets * sizeof(Bucket));
if (!buckets)
return false;
bzero(buckets, nBuckets * sizeof(Bucket));
- poolGate = mutex_alloc(0);
+ poolGate = lck_mtx_alloc_init(IOLockGroup, LCK_ATTR_NULL);
return poolGate != 0;
}
@@ -170,12 +161,19 @@
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));
- ACCUMSIZE(-(nBuckets * sizeof(Bucket)));
+ OSMETA_ACCUMSIZE(-(nBuckets * sizeof(Bucket)));
}
if (poolGate)
- kfree(poolGate, 36 * 4);
+ lck_mtx_free(poolGate, IOLockGroup);
}
unsigned long OSSymbolPool::log2(unsigned int x)
@@ -246,8 +244,8 @@
count = 0;
nBuckets = new_nBuckets;
- buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket));
- ACCUMSIZE(nBuckets * sizeof(Bucket));
+ buckets = (Bucket *) kalloc_tag(nBuckets * sizeof(Bucket), VM_KERN_MEMORY_LIBKERN);
+ OSMETA_ACCUMSIZE(nBuckets * sizeof(Bucket));
/* @@@ gvdl: Zero test and panic if can't set up pool */
bzero(buckets, nBuckets * sizeof(Bucket));
@@ -273,7 +271,7 @@
probeSymbol = (OSSymbol *) thisBucket->symbolP;
if (inLen == probeSymbol->length
- && (strcmp(probeSymbol->string, cString) == 0))
+ && (strncmp(probeSymbol->string, cString, probeSymbol->length) == 0))
return probeSymbol;
return 0;
}
@@ -281,7 +279,7 @@
for (list = thisBucket->symbolP; j--; list++) {
probeSymbol = *list;
if (inLen == probeSymbol->length
- && (strcmp(probeSymbol->string, cString) == 0))
+ && (strncmp(probeSymbol->string, cString, probeSymbol->length) == 0))
return probeSymbol;
}
@@ -310,11 +308,11 @@
probeSymbol = (OSSymbol *) thisBucket->symbolP;
if (inLen == probeSymbol->length
- && strcmp(probeSymbol->string, cString) == 0)
+ && strncmp(probeSymbol->string, cString, probeSymbol->length) == 0)
return probeSymbol;
- list = (OSSymbol **) kalloc(2 * sizeof(OSSymbol *));
- ACCUMSIZE(2 * sizeof(OSSymbol *));
+ list = (OSSymbol **) kalloc_tag(2 * sizeof(OSSymbol *), VM_KERN_MEMORY_LIBKERN);
+ OSMETA_ACCUMSIZE(2 * sizeof(OSSymbol *));
/* @@@ gvdl: Zero test and panic if can't set up pool */
list[0] = sym;
list[1] = probeSymbol;
@@ -329,19 +327,19 @@
for (list = thisBucket->symbolP; j--; list++) {
probeSymbol = *list;
if (inLen == probeSymbol->length
- && strcmp(probeSymbol->string, cString) == 0)
+ && strncmp(probeSymbol->string, cString, probeSymbol->length) == 0)
return probeSymbol;
}
j = thisBucket->count++;
count++;
- list = (OSSymbol **) kalloc(thisBucket->count * sizeof(OSSymbol *));
- ACCUMSIZE(thisBucket->count * sizeof(OSSymbol *));
+ list = (OSSymbol **) kalloc_tag(thisBucket->count * sizeof(OSSymbol *), VM_KERN_MEMORY_LIBKERN);
+ OSMETA_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 *));
- ACCUMSIZE(-(j * sizeof(OSSymbol *)));
+ OSMETA_ACCUMSIZE(-(j * sizeof(OSSymbol *)));
thisBucket->symbolP = list;
GROW_POOL();
@@ -359,8 +357,11 @@
j = thisBucket->count;
list = thisBucket->symbolP;
- if (!j)
+ if (!j) {
+ // 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 == 1) {
probeSymbol = (OSSymbol *) list;
@@ -372,6 +373,8 @@
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;
}
@@ -380,7 +383,7 @@
if (probeSymbol == sym) {
thisBucket->symbolP = (OSSymbol **) list[1];
kfree(list, 2 * sizeof(OSSymbol *));
- ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
+ OSMETA_ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
count--;
thisBucket->count--;
SHRINK_POOL();
@@ -391,12 +394,14 @@
if (probeSymbol == sym) {
thisBucket->symbolP = (OSSymbol **) list[0];
kfree(list, 2 * sizeof(OSSymbol *));
- ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
+ OSMETA_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;
}
@@ -405,8 +410,8 @@
if (probeSymbol == sym) {
list = (OSSymbol **)
- kalloc((thisBucket->count-1) * sizeof(OSSymbol *));
- ACCUMSIZE((thisBucket->count-1) * sizeof(OSSymbol *));
+ kalloc_tag((thisBucket->count-1) * sizeof(OSSymbol *), VM_KERN_MEMORY_LIBKERN);
+ OSMETA_ACCUMSIZE((thisBucket->count-1) * sizeof(OSSymbol *));
if (thisBucket->count-1 != j)
bcopy(thisBucket->symbolP, list,
(thisBucket->count-1-j) * sizeof(OSSymbol *));
@@ -415,13 +420,15 @@
list + thisBucket->count-1-j,
j * sizeof(OSSymbol *));
kfree(thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *));
- ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *)));
+ OSMETA_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);
}
/*
@@ -447,7 +454,7 @@
pool = new OSSymbolPool;
assert(pool);
- if (!pool->init()) {
+ if (pool && !pool->init()) {
delete pool;
assert(false);
};
@@ -494,7 +501,7 @@
newSymb->OSString::free();
}
- oldSymb->retain(); // Retain the old symbol before releasing the lock.
+ if (oldSymb) oldSymb->retain(); // Retain the old symbol before releasing the lock.
pool->openGate();
return oldSymb;
@@ -539,12 +546,7 @@
state = pool->initHashState();
while ( (probeSymbol = pool->nextHashState(&state)) ) {
if (probeSymbol->string >= startAddr && probeSymbol->string < endAddr) {
- const char *oldString = probeSymbol->string;
-
- probeSymbol->string = (char *) kalloc(probeSymbol->length);
- ACCUMSIZE(probeSymbol->length);
- bcopy(oldString, probeSymbol->string, probeSymbol->length);
- probeSymbol->flags &= ~kOSStringNoCopy;
+ probeSymbol->OSString::initWithCString(probeSymbol->string);
}
}
pool->openGate();
@@ -590,3 +592,33 @@
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));
+}