From ba2ae6bc9583420a07245b4a7af2a779fb02b6c9 Mon Sep 17 00:00:00 2001 From: Xiaohong Bao Date: Fri, 2 Sep 2011 11:17:03 -0600 Subject: re-write the hash table code to eliminate potential flaws and simplify the implementation. --- indra/llcommon/llmemory.cpp | 153 ++++++++++++++++++++------------------------ indra/llcommon/llmemory.h | 24 +++++-- 2 files changed, 91 insertions(+), 86 deletions(-) diff --git a/indra/llcommon/llmemory.cpp b/indra/llcommon/llmemory.cpp index 0d36009fc4..8c02ad8290 100644 --- a/indra/llcommon/llmemory.cpp +++ b/indra/llcommon/llmemory.cpp @@ -781,7 +781,6 @@ void LLPrivateMemoryPool::LLMemoryChunk::init(char* buffer, U32 buffer_size, U32 mBlocks[0].setBuffer(mDataBuffer, buffer_size - (mDataBuffer - mBuffer)) ; addToFreeSpace(&mBlocks[0]) ; - mHashNext = NULL ; mNext = NULL ; mPrev = NULL ; } @@ -1457,26 +1456,6 @@ void LLPrivateMemoryPool::destroyPool() { lock() ; -#if 0 - if(mNumOfChunks > 0) - { - //Warn: - //should crash here because there is memory leaking if reach here. - // - - for(U32 i = 0 ; i < mHashFactor; i++) - { - while(mChunkHashList[i]) - { - removeChunk(mChunkHashList[i]) ; - } - } - } - - llassert_always(mNumOfChunks == 0) ; - llassert_always(mReservedPoolSize == 0) ; -#endif - if(mNumOfChunks > 0) { llwarns << "There is some memory not freed when destroy the memory pool!" << llendl ; @@ -1609,14 +1588,7 @@ LLPrivateMemoryPool::LLMemoryChunk* LLPrivateMemoryPool::findChunk(const char* a return NULL ; } - //check the hash value "key" - LLMemoryChunk* chunk = mChunkHashList[key] ; - while(chunk && !chunk->containsAddress(addr)) - { - chunk = chunk->mHashNext ; - } - - return chunk ; + return mChunkHashList[key].findChunk(addr) ; } void LLPrivateMemoryPool::addToHashTable(LLMemoryChunk* chunk) @@ -1634,43 +1606,20 @@ void LLPrivateMemoryPool::addToHashTable(LLMemoryChunk* chunk) U16 end_key = findHashKey(chunk->getBuffer() + chunk->getBufferSize() - 1) ; bool need_rehash = false ; - if(mChunkHashList[start_key]) + if(mChunkHashList[start_key].hasElement(chunk)) { - if(mChunkHashList[start_key] == chunk) - { - return; //already inserted. - } - - llassert_always(!chunk->mHashNext) ; - - chunk->mHashNext = mChunkHashList[start_key] ; - mChunkHashList[start_key] = chunk ; + return; //already inserted. } - else - { - mChunkHashList[start_key] = chunk ; - } - if(start_key == end_key) + need_rehash = mChunkHashList[start_key].add(chunk) ; + + if(start_key == end_key && !need_rehash) { return ; //done } if(!need_rehash) { - if(mChunkHashList[end_key]) - { - llassert_always(mChunkHashList[end_key] != chunk) - - need_rehash = mChunkHashList[end_key]->mHashNext != NULL || mChunkHashList[end_key] == chunk->mHashNext; - if(!need_rehash) - { - mChunkHashList[end_key]->mHashNext = chunk ; - } - } - else - { - mChunkHashList[end_key] = chunk ; - } + need_rehash = mChunkHashList[end_key].add(chunk) ; } if(!need_rehash) @@ -1706,38 +1655,30 @@ void LLPrivateMemoryPool::removeFromHashTable(LLMemoryChunk* chunk) U16 start_key = findHashKey(chunk->getBuffer()) ; U16 end_key = findHashKey(chunk->getBuffer() + chunk->getBufferSize() - 1) ; - mChunkHashList[start_key] = chunk->mHashNext ; - chunk->mHashNext = NULL ; + mChunkHashList[start_key].remove(chunk) ; if(start_key == end_key) { return ; //done } - if(mChunkHashList[end_key] != chunk) - { - mChunkHashList[end_key]->mHashNext = NULL ; - } - else - { - mChunkHashList[end_key] = NULL ; - } - + mChunkHashList[end_key].remove(chunk) ; + if(end_key < start_key) { for(U16 i = start_key + 1 ; i < mHashFactor; i++) { - mChunkHashList[i] = NULL ; + mChunkHashList[i].remove(chunk) ; } for(U16 i = 0 ; i < end_key; i++) { - mChunkHashList[i] = NULL ; + mChunkHashList[i].remove(chunk) ; } } else { for(U16 i = start_key + 1 ; i < end_key; i++) { - mChunkHashList[i] = NULL ; + mChunkHashList[i].remove(chunk) ; } } } @@ -1747,7 +1688,7 @@ void LLPrivateMemoryPool::rehash() llinfos << "new hash factor: " << mHashFactor << llendl ; mChunkHashList.clear() ; - mChunkHashList.resize(mHashFactor, NULL) ; + mChunkHashList.resize(mHashFactor) ; LLMemoryChunk* chunk ; for(U16 i = 0 ; i < SUPER_ALLOCATION ; i++) @@ -1755,7 +1696,6 @@ void LLPrivateMemoryPool::rehash() chunk = mChunkList[i] ; while(chunk) { - chunk->mHashNext = NULL ; addToHashTable(chunk) ; chunk = chunk->mNext ; } @@ -1766,20 +1706,69 @@ bool LLPrivateMemoryPool::fillHashTable(U16 start, U16 end, LLMemoryChunk* chunk { for(U16 i = start; i < end; i++) { - if(mChunkHashList[i]) //the slot is occupied. - { - llassert_always(mChunkHashList[i] != chunk) ; + if(mChunkHashList[i].add(chunk)) + { return true ; - } - else - { - mChunkHashList[i] = chunk ; - } + } + } + + return false ; +} + +//-------------------------------------------------------------------- +// class LLChunkHashElement +//-------------------------------------------------------------------- +LLPrivateMemoryPool::LLMemoryChunk* LLPrivateMemoryPool::LLChunkHashElement::findChunk(const char* addr) +{ + if(mFirst && mFirst->containsAddress(addr)) + { + return mFirst ; + } + else if(mSecond && mSecond->containsAddress(addr)) + { + return mSecond ; + } + + return NULL ; +} + +//return false if successfully inserted to the hash slot. +bool LLPrivateMemoryPool::LLChunkHashElement::add(LLPrivateMemoryPool::LLMemoryChunk* chunk) +{ + llassert_always(!hasElement(chunk)) ; + + if(!mFirst) + { + mFirst = chunk ; + } + else if(!mSecond) + { + mSecond = chunk ; + } + else + { + return true ; //failed } return false ; } +void LLPrivateMemoryPool::LLChunkHashElement::remove(LLPrivateMemoryPool::LLMemoryChunk* chunk) +{ + if(mFirst == chunk) + { + mFirst = NULL ; + } + else if(mSecond ==chunk) + { + mSecond = NULL ; + } + else + { + llerrs << "This slot does not contain this chunk!" << llendl ; + } +} + //-------------------------------------------------------------------- //class LLPrivateMemoryPoolManager //-------------------------------------------------------------------- diff --git a/indra/llcommon/llmemory.h b/indra/llcommon/llmemory.h index f9099da612..db753f0d8b 100644 --- a/indra/llcommon/llmemory.h +++ b/indra/llcommon/llmemory.h @@ -300,8 +300,6 @@ public: //form a linked list LLMemoryChunk* mNext ; LLMemoryChunk* mPrev ; - - LLMemoryChunk* mHashNext ; } ; private: @@ -356,12 +354,30 @@ private: U32 mMaxPoolSize; U32 mReservedPoolSize ; - LLMemoryChunk* mChunkList[SUPER_ALLOCATION] ; //all memory chunks reserved by this pool, sorted by address - std::vector mChunkHashList ; + LLMemoryChunk* mChunkList[SUPER_ALLOCATION] ; //all memory chunks reserved by this pool, sorted by address U16 mNumOfChunks ; U16 mHashFactor ; S32 mType ; + + class LLChunkHashElement + { + public: + LLChunkHashElement() {mFirst = NULL ; mSecond = NULL ;} + + bool add(LLMemoryChunk* chunk) ; + void remove(LLMemoryChunk* chunk) ; + LLMemoryChunk* findChunk(const char* addr) ; + + bool empty() {return !mFirst && !mSecond; } + bool full() {return mFirst && mSecond; } + bool hasElement(LLMemoryChunk* chunk) {return mFirst == chunk || mSecond == chunk;} + + private: + LLMemoryChunk* mFirst ; + LLMemoryChunk* mSecond ; + }; + std::vector mChunkHashList ; }; class LL_COMMON_API LLPrivateMemoryPoolManager -- cgit v1.2.3