#include <string.h>
#include <sys/cdefs.h>
#include <kern/locks.h>
#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)
class OSSymbolPool
{
private:
static const unsigned int kInitBucketCount = 16;
typedef struct { unsigned int count; OSSymbol **symbolP; } Bucket;
Bucket *buckets;
unsigned int nBuckets;
unsigned int count;
lck_rw_t *poolGate;
static inline void
hashSymbol(const char *s,
unsigned int *hashP,
unsigned int *lenP)
{
unsigned int hash = 0;
unsigned int len = 0;
for (;;) {
if (!*s) {
break;
}
len++; hash ^= *s++;
if (!*s) {
break;
}
len++; hash ^= *s++ << 8;
if (!*s) {
break;
}
len++; hash ^= *s++ << 16;
if (!*s) {
break;
}
len++; hash ^= *s++ << 24;
}
*lenP = len;
*hashP = hash;
}
static unsigned long log2(unsigned int x);
static unsigned long exp2ml(unsigned int x);
void reconstructSymbols(void);
void reconstructSymbols(bool grow);
public:
static void *operator new(size_t size);
static void operator delete(void *mem, size_t size);
OSSymbolPool()
{
}
OSSymbolPool(const OSSymbolPool *old);
virtual
~OSSymbolPool();
bool init();
inline void
closeReadGate()
{
lck_rw_lock(poolGate, LCK_RW_TYPE_SHARED);
}
inline void
openReadGate()
{
lck_rw_unlock(poolGate, LCK_RW_TYPE_SHARED);
}
inline void
closeWriteGate()
{
lck_rw_lock(poolGate, LCK_RW_TYPE_EXCLUSIVE);
}
inline void
openWriteGate()
{
lck_rw_unlock(poolGate, LCK_RW_TYPE_EXCLUSIVE);
}
LIBKERN_RETURNS_RETAINED OSSymbol *findSymbol(const char *cString) const;
LIBKERN_RETURNS_RETAINED OSSymbol *insertSymbol(OSSymbol *sym);
void removeSymbol(OSSymbol *sym);
OSSymbolPoolState initHashState();
LIBKERN_RETURNS_NOT_RETAINED OSSymbol *nextHashState(OSSymbolPoolState *stateP);
};
void *
OSSymbolPool::operator new(size_t size)
{
void *mem = (void *)kalloc_tag(size, VM_KERN_MEMORY_LIBKERN);
OSMETA_ACCUMSIZE(size);
assert(mem);
bzero(mem, size);
return mem;
}
void
OSSymbolPool::operator delete(void *mem, size_t size)
{
kfree(mem, size);
OSMETA_ACCUMSIZE(-size);
}
extern lck_grp_t *IOLockGroup;
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));
if (!buckets) {
return false;
}
bzero(buckets, nBuckets * sizeof(Bucket));
poolGate = lck_rw_alloc_init(IOLockGroup, LCK_ATTR_NULL);
return poolGate != NULL;
}
OSSymbolPool::OSSymbolPool(const OSSymbolPool *old)
{
count = old->count;
nBuckets = old->nBuckets;
buckets = old->buckets;
poolGate = NULL; }
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)));
}
if (poolGate) {
lck_rw_free(poolGate, IOLockGroup);
}
}
unsigned long
OSSymbolPool::log2(unsigned int x)
{
unsigned long i;
for (i = 0; x > 1; i++) {
x >>= 1;
}
return i;
}
unsigned long
OSSymbolPool::exp2ml(unsigned int x)
{
return (1 << x) - 1;
}
OSSymbolPoolState
OSSymbolPool::initHashState()
{
OSSymbolPoolState newState = { nBuckets, 0 };
return newState;
}
OSSymbol *
OSSymbolPool::nextHashState(OSSymbolPoolState *stateP)
{
Bucket *thisBucket = &buckets[stateP->i];
while (!stateP->j) {
if (!stateP->i) {
return NULL;
}
stateP->i--;
thisBucket--;
stateP->j = thisBucket->count;
}
stateP->j--;
if (thisBucket->count == 1) {
return (OSSymbol *) thisBucket->symbolP;
} else {
return thisBucket->symbolP[stateP->j];
}
}
void
OSSymbolPool::reconstructSymbols(void)
{
this->reconstructSymbols(true);
}
void
OSSymbolPool::reconstructSymbols(bool grow)
{
unsigned int new_nBuckets = nBuckets;
OSSymbol *insert;
OSSymbolPoolState state;
if (grow) {
new_nBuckets += new_nBuckets + 1;
} else {
if (nBuckets <= INITIAL_POOL_SIZE) {
return;
}
new_nBuckets = (new_nBuckets - 1) / 2;
}
OSSymbolPool old(this);
count = 0;
nBuckets = new_nBuckets;
buckets = (Bucket *) kalloc_tag(nBuckets * sizeof(Bucket), VM_KERN_MEMORY_LIBKERN);
OSMETA_ACCUMSIZE(nBuckets * sizeof(Bucket));
bzero(buckets, nBuckets * sizeof(Bucket));
state = old.initHashState();
while ((insert = old.nextHashState(&state))) {
insertSymbol(insert);
}
}
OSSymbol *
OSSymbolPool::findSymbol(const char *cString) const
{
Bucket *thisBucket;
unsigned int j, inLen, hash;
OSSymbol *probeSymbol, **list;
hashSymbol(cString, &hash, &inLen); inLen++;
thisBucket = &buckets[hash % nBuckets];
j = thisBucket->count;
if (!j) {
return NULL;
}
if (j == 1) {
probeSymbol = (OSSymbol *) thisBucket->symbolP;
if (inLen == probeSymbol->length
&& strncmp(probeSymbol->string, cString, probeSymbol->length) == 0
&& probeSymbol->taggedTryRetain(nullptr)) {
return probeSymbol;
}
return NULL;
}
for (list = thisBucket->symbolP; j--; list++) {
probeSymbol = *list;
if (inLen == probeSymbol->length
&& strncmp(probeSymbol->string, cString, probeSymbol->length) == 0
&& probeSymbol->taggedTryRetain(nullptr)) {
return probeSymbol;
}
}
return NULL;
}
OSSymbol *
OSSymbolPool::insertSymbol(OSSymbol *sym)
{
const char *cString = sym->string;
Bucket *thisBucket;
unsigned int j, inLen, hash;
OSSymbol *probeSymbol, **list;
hashSymbol(cString, &hash, &inLen); inLen++;
thisBucket = &buckets[hash % nBuckets];
j = thisBucket->count;
if (!j) {
thisBucket->symbolP = (OSSymbol **) sym;
thisBucket->count++;
count++;
return nullptr;
}
if (j == 1) {
probeSymbol = (OSSymbol *) thisBucket->symbolP;
if (inLen == probeSymbol->length
&& strncmp(probeSymbol->string, cString, probeSymbol->length) == 0
&& probeSymbol->taggedTryRetain(nullptr)) {
return probeSymbol;
}
list = (OSSymbol **) kalloc_tag(2 * sizeof(OSSymbol *), VM_KERN_MEMORY_LIBKERN);
OSMETA_ACCUMSIZE(2 * sizeof(OSSymbol *));
list[0] = sym;
list[1] = probeSymbol;
thisBucket->symbolP = list;
thisBucket->count++;
count++;
GROW_POOL();
return nullptr;
}
for (list = thisBucket->symbolP; j--; list++) {
probeSymbol = *list;
if (inLen == probeSymbol->length
&& strncmp(probeSymbol->string, cString, probeSymbol->length) == 0
&& probeSymbol->taggedTryRetain(nullptr)) {
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[0] = sym;
bcopy(thisBucket->symbolP, list + 1, j * sizeof(OSSymbol *));
kfree(thisBucket->symbolP, j * sizeof(OSSymbol *));
OSMETA_ACCUMSIZE(-(j * sizeof(OSSymbol *)));
thisBucket->symbolP = list;
GROW_POOL();
return nullptr;
}
void
OSSymbolPool::removeSymbol(OSSymbol *sym)
{
Bucket *thisBucket;
unsigned int j, inLen, hash;
OSSymbol *probeSymbol, **list;
hashSymbol(sym->string, &hash, &inLen); inLen++;
thisBucket = &buckets[hash % nBuckets];
j = thisBucket->count;
list = thisBucket->symbolP;
if (!j) {
panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
return;
}
if (j == 1) {
probeSymbol = (OSSymbol *) list;
if (probeSymbol == sym) {
thisBucket->symbolP = NULL;
count--;
thisBucket->count--;
SHRINK_POOL();
return;
}
panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
return;
}
if (j == 2) {
probeSymbol = list[0];
if (probeSymbol == sym) {
thisBucket->symbolP = (OSSymbol **) list[1];
kfree(list, 2 * sizeof(OSSymbol *));
OSMETA_ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
count--;
thisBucket->count--;
SHRINK_POOL();
return;
}
probeSymbol = list[1];
if (probeSymbol == sym) {
thisBucket->symbolP = (OSSymbol **) list[0];
kfree(list, 2 * sizeof(OSSymbol *));
OSMETA_ACCUMSIZE(-(2 * sizeof(OSSymbol *)));
count--;
thisBucket->count--;
SHRINK_POOL();
return;
}
panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
return;
}
for (; j--; list++) {
probeSymbol = *list;
if (probeSymbol == sym) {
list = (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 *));
}
if (j) {
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 *)));
thisBucket->symbolP = list;
count--;
thisBucket->count--;
return;
}
}
panic("removeSymbol %s count %d ", sym->string ? sym->string : "no string", count);
}
OSDefineMetaClassAndStructorsWithInit(OSSymbol, OSString,
OSSymbol::initialize())
OSMetaClassDefineReservedUnused(OSSymbol, 0);
OSMetaClassDefineReservedUnused(OSSymbol, 1);
OSMetaClassDefineReservedUnused(OSSymbol, 2);
OSMetaClassDefineReservedUnused(OSSymbol, 3);
OSMetaClassDefineReservedUnused(OSSymbol, 4);
OSMetaClassDefineReservedUnused(OSSymbol, 5);
OSMetaClassDefineReservedUnused(OSSymbol, 6);
OSMetaClassDefineReservedUnused(OSSymbol, 7);
static OSSymbolPool *pool;
void
OSSymbol::initialize()
{
pool = new OSSymbolPool;
assert(pool);
if (pool && !pool->init()) {
delete pool;
assert(false);
}
;
}
bool
OSSymbol::initWithCStringNoCopy(const char *)
{
return false;
}
bool
OSSymbol::initWithCString(const char *)
{
return false;
}
bool
OSSymbol::initWithString(const OSString *)
{
return false;
}
const OSSymbol *
OSSymbol::withString(const OSString *aString)
{
if (OSDynamicCast(OSSymbol, aString)) {
aString->retain();
return (const OSSymbol *) aString;
} else if (((const OSSymbol *) aString)->flags & kOSStringNoCopy) {
return OSSymbol::withCStringNoCopy(aString->getCStringNoCopy());
} else {
return OSSymbol::withCString(aString->getCStringNoCopy());
}
}
const OSSymbol *
OSSymbol::withCString(const char *cString)
{
const OSSymbol *symbol;
symbol = OSSymbol::existingSymbolForCString(cString);
if (symbol) {
return symbol;
}
OSSymbol *newSymb = new OSSymbol;
if (!newSymb) {
return newSymb;
}
if (newSymb->OSString::initWithCString(cString)) {
pool->closeWriteGate();
symbol = pool->insertSymbol(newSymb);
pool->openWriteGate();
if (symbol) {
newSymb->OSString::free();
return symbol;
}
}
return newSymb; }
const OSSymbol *
OSSymbol::withCStringNoCopy(const char *cString)
{
const OSSymbol *symbol;
OSSymbol *newSymb;
symbol = OSSymbol::existingSymbolForCString(cString);
if (symbol) {
return symbol;
}
newSymb = new OSSymbol;
if (!newSymb) {
return newSymb;
}
if (newSymb->OSString::initWithCStringNoCopy(cString)) {
pool->closeWriteGate();
symbol = pool->insertSymbol(newSymb);
pool->openWriteGate();
if (symbol) {
newSymb->OSString::free();
return symbol;
}
}
return newSymb; }
const OSSymbol *
OSSymbol::existingSymbolForString(const OSString *aString)
{
if (OSDynamicCast(OSSymbol, aString)) {
aString->retain();
return (const OSSymbol *) aString;
}
return OSSymbol::existingSymbolForCString(aString->getCStringNoCopy());
}
const OSSymbol *
OSSymbol::existingSymbolForCString(const char *cString)
{
OSSymbol *symbol;
pool->closeReadGate();
symbol = pool->findSymbol(cString);
pool->openReadGate();
return symbol;
}
void
OSSymbol::checkForPageUnload(void *startAddr, void *endAddr)
{
OSSymbol *probeSymbol;
OSSymbolPoolState state;
pool->closeWriteGate();
state = pool->initHashState();
while ((probeSymbol = pool->nextHashState(&state))) {
if (probeSymbol->string >= startAddr && probeSymbol->string < endAddr) {
probeSymbol->OSString::initWithCString(probeSymbol->string);
}
}
pool->openWriteGate();
}
void
OSSymbol::taggedRelease(const void *tag) const
{
super::taggedRelease(tag);
}
void
OSSymbol::taggedRelease(const void *tag, const int when) const
{
super::taggedRelease(tag, when);
}
void
OSSymbol::free()
{
pool->closeWriteGate();
pool->removeSymbol(this);
pool->openWriteGate();
super::free();
}
bool
OSSymbol::isEqualTo(const char *aCString) const
{
return super::isEqualTo(aCString);
}
bool
OSSymbol::isEqualTo(const OSSymbol *aSymbol) const
{
return aSymbol == this;
}
bool
OSSymbol::isEqualTo(const OSMetaClassBase *obj) const
{
OSSymbol * sym;
OSString * str;
if ((sym = OSDynamicCast(OSSymbol, obj))) {
return isEqualTo(sym);
} else if ((str = OSDynamicCast(OSString, obj))) {
return super::isEqualTo(str);
} 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) {
baseIdx += (lim >> 1) + 1;
lim--;
}
}
return baseIdx + (lim >> 1);
}