[haiku-commits] haiku: hrev48670 - src/system/kernel/cache src/tools/fs_shell src/system/kernel/util src/tests/system/kernel/cache headers/private/kernel/util
- From: pulkomandy@xxxxxxxxxxxxx
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Tue, 13 Jan 2015 15:49:59 +0100 (CET)
hrev48670 adds 5 changesets to branch 'master'
old head: be60c04c8932758e86a1121605ea340af53e90c0
new head: a7d444d14560a4cb9836ccfe39c649f3dc1f028a
overview: http://cgit.haiku-os.org/haiku/log/?qt=range&q=a7d444d+%5Ebe60c04
----------------------------------------------------------------------------
9d1c3b8: block cache: convert to BOpenHashTable.
9d053f5: BOpenHashTable: document some subtleties
Mainly the interaction of resizing the table with iterators.
bb3092b: rootfs: convert to BOpenHashTable.
* Add an fs-shell compatible version of BOpenHashTable in the fs_shell
to keep it working. The header is renamed to KOpenHashTable to avoid a
conflict with the OpenHashTable.h available in private/shared which is
not API compatible.
ace7496: Remove khash from the sources.
Fixes #9552.
a7d444d: Remove old block cache implementation
This was not used anywhere except the tests written for it (which is
also removed).
[ Adrien Destugues <pulkomandy@xxxxxxxxx> ]
----------------------------------------------------------------------------
13 files changed, 718 insertions(+), 1120 deletions(-)
headers/private/kernel/util/OpenHashTable.h | 39 +-
headers/private/kernel/util/khash.h | 61 ---
.../file_systems/userlandfs/server/haiku/Jamfile | 5 -
src/system/kernel/cache/BlockMap.cpp | 240 ---------
src/system/kernel/cache/BlockMap.h | 35 --
src/system/kernel/cache/block_cache.cpp | 290 +++++------
src/system/kernel/fs/rootfs.cpp | 94 ++--
src/system/kernel/util/Jamfile | 1 -
src/system/kernel/util/khash.cpp | 424 ----------------
src/tests/add-ons/kernel/kernelland_emu/Jamfile | 3 +-
src/tests/system/kernel/cache/BlockMapTest.cpp | 143 ------
src/tests/system/kernel/cache/Jamfile | 6 -
src/tools/fs_shell/KOpenHashTable.h | 497 +++++++++++++++++++
############################################################################
Commit: 9d1c3b8d4b93abd805a1cba96134d090200f04b2
URL: http://cgit.haiku-os.org/haiku/commit/?id=9d1c3b8
Author: Adrien Destugues <pulkomandy@xxxxxxxxx>
Date: Tue Jan 13 12:28:35 2015 UTC
block cache: convert to BOpenHashTable.
----------------------------------------------------------------------------
diff --git a/src/system/kernel/cache/block_cache.cpp
b/src/system/kernel/cache/block_cache.cpp
index ba6f71a..36af948 100644
--- a/src/system/kernel/cache/block_cache.cpp
+++ b/src/system/kernel/cache/block_cache.cpp
@@ -22,7 +22,6 @@
#include <util/kernel_cpp.h>
#include <util/DoublyLinkedList.h>
#include <util/AutoLock.h>
-#include <util/khash.h>
#include <vm/vm_page.h>
#include "kernel_debug_config.h"
@@ -104,9 +103,6 @@ struct cached_block {
bool CanBeWritten() const;
int32 LastAccess() const
{ return system_time() / 1000000L - last_accessed; }
-
- static int Compare(void* _cacheEntry, const void* _block);
- static uint32 Hash(void* _cacheEntry, const void* _block, uint32 range);
};
typedef DoublyLinkedList<cached_block,
@@ -124,15 +120,60 @@ struct cache_notification :
DoublyLinkedListLinkImpl<cache_notification> {
typedef DoublyLinkedList<cache_notification> NotificationList;
+struct BlockHash {
+ typedef off_t KeyType;
+ typedef cached_block ValueType;
+
+ size_t HashKey(KeyType key) const
+ {
+ return key;
+ }
+
+ size_t Hash(ValueType* block) const
+ {
+ return block->block_number;
+ }
+
+ bool Compare(KeyType key, ValueType* block) const
+ {
+ return block->block_number == key;
+ }
+
+ ValueType*& GetLink(ValueType* value) const
+ {
+ return value->next;
+ }
+};
+
+typedef BOpenHashTable<BlockHash> BlockTable;
+
+
+struct TransactionHash {
+ typedef int32 KeyType;
+ typedef cache_transaction ValueType;
+
+ size_t HashKey(KeyType key) const
+ {
+ return key;
+ }
+
+ size_t Hash(ValueType* transaction) const;
+ bool Compare(KeyType key, ValueType* transaction) const;
+ ValueType*& GetLink(ValueType* value) const;
+};
+
+typedef BOpenHashTable<TransactionHash> TransactionTable;
+
+
struct block_cache : DoublyLinkedListLinkImpl<block_cache> {
- hash_table* hash;
+ BlockTable* hash;
mutex lock;
int fd;
off_t max_blocks;
size_t block_size;
int32 next_transaction_id;
cache_transaction* last_transaction;
- hash_table* transaction_hash;
+ TransactionTable* transaction_hash;
object_cache* buffer_cache;
block_list unused_blocks;
@@ -211,12 +252,11 @@ public:
~BlockWriter();
bool Add(cached_block* block,
-
hash_iterator* iterator = NULL);
+
cache_transaction* transaction = NULL);
bool Add(cache_transaction*
transaction,
-
hash_iterator* iterator,
bool&
hasLeftOvers);
- status_t Write(hash_iterator*
iterator = NULL,
+ status_t
Write(cache_transaction* transaction = NULL,
bool
canUnlock = true);
bool DeletedTransaction()
const
@@ -229,7 +269,7 @@ private:
void* _Data(cached_block*
block) const;
status_t
_WriteBlock(cached_block* block);
void
_BlockDone(cached_block* block,
-
hash_iterator* iterator);
+
cache_transaction* transaction);
void
_UnmarkWriting(cached_block* block);
static int _CompareBlocks(const
void* _blockA,
@@ -943,44 +983,39 @@ cache_transaction::cache_transaction()
}
-static int
-transaction_compare(void* _transaction, const void* _id)
+static void
+delete_transaction(block_cache* cache, cache_transaction* transaction)
{
- cache_transaction* transaction = (cache_transaction*)_transaction;
- const int32* id = (const int32*)_id;
+ if (cache->last_transaction == transaction)
+ cache->last_transaction = NULL;
- return transaction->id - *id;
+ remove_transaction_listeners(cache, transaction);
+ delete transaction;
}
-static uint32
-transaction_hash(void* _transaction, const void* _id, uint32 range)
+static cache_transaction*
+lookup_transaction(block_cache* cache, int32 id)
{
- cache_transaction* transaction = (cache_transaction*)_transaction;
- const int32* id = (const int32*)_id;
+ return cache->transaction_hash->Lookup(id);
+}
- if (transaction != NULL)
- return transaction->id % range;
- return (uint32)*id % range;
+size_t TransactionHash::Hash(cache_transaction* transaction) const
+{
+ return transaction->id;
}
-static void
-delete_transaction(block_cache* cache, cache_transaction* transaction)
+bool TransactionHash::Compare(int32 key, cache_transaction* transaction) const
{
- if (cache->last_transaction == transaction)
- cache->last_transaction = NULL;
-
- remove_transaction_listeners(cache, transaction);
- delete transaction;
+ return transaction->id == key;
}
-static cache_transaction*
-lookup_transaction(block_cache* cache, int32 id)
+cache_transaction*& TransactionHash::GetLink(cache_transaction* value) const
{
- return (cache_transaction*)hash_lookup(cache->transaction_hash, &id);
+ return value->next;
}
@@ -1017,33 +1052,6 @@ cached_block::CanBeWritten() const
}
-/*static*/ int
-cached_block::Compare(void* _cacheEntry, const void* _block)
-{
- cached_block* cacheEntry = (cached_block*)_cacheEntry;
- const off_t* block = (const off_t*)_block;
-
- off_t diff = cacheEntry->block_number - *block;
- if (diff > 0)
- return 1;
-
- return diff < 0 ? -1 : 0;
-}
-
-
-/*static*/ uint32
-cached_block::Hash(void* _cacheEntry, const void* _block, uint32 range)
-{
- cached_block* cacheEntry = (cached_block*)_cacheEntry;
- const off_t* block = (const off_t*)_block;
-
- if (cacheEntry != NULL)
- return cacheEntry->block_number % range;
-
- return (uint64)*block % range;
-}
-
-
// #pragma mark - BlockWriter
@@ -1072,7 +1080,7 @@ BlockWriter::~BlockWriter()
be added, false is returned, otherwise true.
*/
bool
-BlockWriter::Add(cached_block* block, hash_iterator* iterator)
+BlockWriter::Add(cached_block* block, cache_transaction* transaction)
{
ASSERT(block->CanBeWritten());
@@ -1093,7 +1101,7 @@ BlockWriter::Add(cached_block* block, hash_iterator*
iterator)
if (newBlocks == NULL) {
// Allocating a larger array failed - we need to write
back what
// we have synchronously now (this will also clear the
array)
- Write(iterator, false);
+ Write(transaction, false);
} else {
if (fBlocks == fBuffer)
memcpy(newBlocks, fBuffer, kBufferSize *
sizeof(void*));
@@ -1118,8 +1126,7 @@ BlockWriter::Add(cached_block* block, hash_iterator*
iterator)
If no more blocks can be added, false is returned, otherwise true.
*/
bool
-BlockWriter::Add(cache_transaction* transaction, hash_iterator* iterator,
- bool& hasLeftOvers)
+BlockWriter::Add(cache_transaction* transaction, bool& hasLeftOvers)
{
ASSERT(!transaction->open);
@@ -1138,7 +1145,7 @@ BlockWriter::Add(cache_transaction* transaction,
hash_iterator* iterator,
hasLeftOvers = true;
continue;
}
- if (!Add(block, iterator))
+ if (!Add(block, transaction))
return false;
if (DeletedTransaction())
@@ -1153,7 +1160,7 @@ BlockWriter::Add(cache_transaction* transaction,
hash_iterator* iterator,
while the blocks are written back.
*/
status_t
-BlockWriter::Write(hash_iterator* iterator, bool canUnlock)
+BlockWriter::Write(cache_transaction* transaction, bool canUnlock)
{
if (fCount == 0)
return B_OK;
@@ -1184,7 +1191,7 @@ BlockWriter::Write(hash_iterator* iterator, bool
canUnlock)
mutex_lock(&fCache->lock);
for (uint32 i = 0; i < fCount; i++)
- _BlockDone(fBlocks[i], iterator);
+ _BlockDone(fBlocks[i], transaction);
fCount = 0;
return fStatus;
@@ -1245,7 +1252,8 @@ BlockWriter::_WriteBlock(cached_block* block)
void
-BlockWriter::_BlockDone(cached_block* block, hash_iterator* iterator)
+BlockWriter::_BlockDone(cached_block* block,
+ cache_transaction* transaction)
{
if (block == NULL) {
// An error occured when trying to write this block
@@ -1280,10 +1288,14 @@ BlockWriter::_BlockDone(cached_block* block,
hash_iterator* iterator)
notify_transaction_listeners(fCache, previous,
TRANSACTION_WRITTEN);
- if (iterator != NULL)
- hash_remove_current(fCache->transaction_hash,
iterator);
- else
- hash_remove(fCache->transaction_hash, previous);
+ if (transaction != NULL) {
+ // This function is called while iterating
transaction_hash. We
+ // use RemoveUnchecked so the iterator is still
valid. A regular
+ // Remove can trigger a resize of the hash
table which would
+ // result in the linked items in the table
changing order.
+
fCache->transaction_hash->RemoveUnchecked(transaction);
+ } else
+ fCache->transaction_hash->Remove(previous);
delete_transaction(fCache, previous);
fDeletedTransaction = true;
@@ -1362,8 +1374,8 @@ block_cache::~block_cache()
{
unregister_low_resource_handler(&_LowMemoryHandler, this);
- hash_uninit(transaction_hash);
- hash_uninit(hash);
+ delete transaction_hash;
+ delete hash;
delete_object_cache(buffer_cache);
@@ -1384,16 +1396,12 @@ block_cache::Init()
if (buffer_cache == NULL)
return B_NO_MEMORY;
- cached_block dummyBlock;
- hash = hash_init(1024, offset_of_member(dummyBlock, next),
- &cached_block::Compare, &cached_block::Hash);
- if (hash == NULL)
+ hash = new BlockTable();
+ if (hash == NULL || hash->Init(1024) != B_OK)
return B_NO_MEMORY;
- cache_transaction dummyTransaction;
- transaction_hash = hash_init(16, offset_of_member(dummyTransaction,
next),
- &transaction_compare, &::transaction_hash);
- if (transaction_hash == NULL)
+ transaction_hash = new(std::nothrow) TransactionTable();
+ if (transaction_hash == NULL || transaction_hash->Init(16) != B_OK)
return B_NO_MEMORY;
return register_low_resource_handler(&_LowMemoryHandler, this,
@@ -1549,7 +1557,7 @@ block_cache::RemoveUnusedBlocks(int32 count, int32
minSecondsOld)
void
block_cache::RemoveBlock(cached_block* block)
{
- hash_remove(hash, block);
+ hash->Remove(block);
FreeBlock(block);
}
@@ -1638,7 +1646,7 @@ block_cache::_GetUnusedBlock()
// remove block from lists
iterator.Remove();
unused_block_count--;
- hash_remove(hash, block);
+ hash->Remove(block);
ASSERT(block->original_data == NULL && block->parent_data ==
NULL);
block->unused = false;
@@ -1822,7 +1830,7 @@ put_cached_block(block_cache* cache, off_t blockNumber)
blockNumber, cache->max_blocks - 1);
}
- cached_block* block = (cached_block*)hash_lookup(cache->hash,
&blockNumber);
+ cached_block* block = cache->hash->Lookup(blockNumber);
if (block != NULL)
put_cached_block(cache, block);
else {
@@ -1855,8 +1863,7 @@ get_cached_block(block_cache* cache, off_t blockNumber,
bool* _allocated,
}
retry:
- cached_block* block = (cached_block*)hash_lookup(cache->hash,
- &blockNumber);
+ cached_block* block = cache->hash->Lookup(blockNumber);
*_allocated = false;
if (block == NULL) {
@@ -1865,7 +1872,7 @@ retry:
if (block == NULL)
return NULL;
- hash_insert_grow(cache->hash, block);
+ cache->hash->Insert(block);
*_allocated = true;
} else if (block->busy_reading) {
// The block is currently busy_reading - wait and try again
later
@@ -2179,8 +2186,7 @@ dump_cache(int argc, char** argv)
off_t blockNumber = -1;
if (i + 1 < argc) {
blockNumber = parse_expression(argv[i + 1]);
- cached_block* block = (cached_block*)hash_lookup(cache->hash,
- &blockNumber);
+ cached_block* block = cache->hash->Lookup(blockNumber);
if (block != NULL)
dump_block_long(block);
else
@@ -2218,14 +2224,13 @@ dump_cache(int argc, char** argv)
kprintf(" transactions:\n");
kprintf("address id state blocks main sub\n");
- hash_iterator iterator;
- hash_open(cache->transaction_hash, &iterator);
+ TransactionTable::Iterator iterator(cache->transaction_hash);
- cache_transaction* transaction;
- while ((transaction = (cache_transaction*)hash_next(
- cache->transaction_hash, &iterator)) != NULL) {
- kprintf("%p %5" B_PRId32 " %-7s %5" B_PRId32 " %5"
B_PRId32 " %5" B_PRId32 "\n",
- transaction, transaction->id, transaction->open
? "open" : "closed",
+ while (iterator.HasNext()) {
+ cache_transaction* transaction = iterator.Next();
+ kprintf("%p %5" B_PRId32 " %-7s %5" B_PRId32 " %5"
B_PRId32 " %5"
+ B_PRId32 "\n", transaction, transaction->id,
+ transaction->open ? "open" : "closed",
transaction->num_blocks,
transaction->main_num_blocks,
transaction->sub_num_blocks);
}
@@ -2241,10 +2246,9 @@ dump_cache(int argc, char** argv)
uint32 count = 0;
uint32 dirty = 0;
uint32 discarded = 0;
- hash_iterator iterator;
- hash_open(cache->hash, &iterator);
- cached_block* block;
- while ((block = (cached_block*)hash_next(cache->hash, &iterator)) !=
NULL) {
+ BlockTable::Iterator iterator(cache->hash);
+ while (iterator.HasNext()) {
+ cached_block* block = iterator.Next();
if (showBlocks)
dump_block(block);
@@ -2257,12 +2261,11 @@ dump_cache(int argc, char** argv)
count++;
}
- kprintf(" %" B_PRIu32 " blocks total, %" B_PRIu32 " dirty, %" B_PRIu32
" discarded"
- ", %" B_PRIu32 " referenced, %" B_PRIu32 " busy, %" B_PRIu32 "
in unused.\n",
+ kprintf(" %" B_PRIu32 " blocks total, %" B_PRIu32 " dirty, %" B_PRIu32
+ " discarded, %" B_PRIu32 " referenced, %" B_PRIu32 " busy, %"
B_PRIu32
+ " in unused.\n",
count, dirty, discarded, referenced, cache->busy_reading_count,
cache->unused_block_count);
-
- hash_close(cache->hash, &iterator, false);
return 0;
}
@@ -2534,24 +2537,19 @@ block_notifier_and_writer(void* /*data*/)
if (cache->num_dirty_blocks) {
// This cache is not using transactions, we'll
scan the blocks
// directly
- hash_iterator iterator;
- hash_open(cache->hash, &iterator);
+ BlockTable::Iterator iterator(cache->hash);
- cached_block* block;
- while ((block =
(cached_block*)hash_next(cache->hash, &iterator))
- != NULL) {
+ while (iterator.HasNext()) {
+ cached_block* block = iterator.Next();
if (block->CanBeWritten() &&
!writer.Add(block))
break;
}
- hash_close(cache->hash, &iterator, false);
} else {
- hash_iterator iterator;
- hash_open(cache->transaction_hash, &iterator);
+ TransactionTable::Iterator
iterator(cache->transaction_hash);
- cache_transaction* transaction;
- while ((transaction =
(cache_transaction*)hash_next(
- cache->transaction_hash,
&iterator)) != NULL) {
+ while (iterator.HasNext()) {
+ cache_transaction* transaction =
iterator.Next();
if (transaction->open) {
if (system_time() >
transaction->last_used
+
kTransactionIdleTime) {
@@ -2564,11 +2562,9 @@ block_notifier_and_writer(void* /*data*/)
bool hasLeftOvers;
// we ignore this one
- if (!writer.Add(transaction, &iterator,
hasLeftOvers))
+ if (!writer.Add(transaction,
hasLeftOvers))
break;
}
-
- hash_close(cache->transaction_hash, &iterator,
false);
}
writer.Write();
@@ -2734,7 +2730,7 @@ cache_start_transaction(void* _cache)
TRACE(("cache_start_transaction(): id %" B_PRId32 " started\n",
transaction->id));
T(Action("start", cache, transaction));
- hash_insert_grow(cache->transaction_hash, transaction);
+ cache->transaction_hash->Insert(transaction);
return transaction->id;
}
@@ -2753,13 +2749,11 @@ cache_sync_transaction(void* _cache, int32 id)
hadBusy = false;
BlockWriter writer(cache);
- hash_iterator iterator;
- hash_open(cache->transaction_hash, &iterator);
+ TransactionTable::Iterator iterator(cache->transaction_hash);
- cache_transaction* transaction;
- while ((transaction = (cache_transaction*)hash_next(
- cache->transaction_hash, &iterator)) != NULL) {
+ while (iterator.HasNext()) {
// close all earlier transactions which haven't been
closed yet
+ cache_transaction* transaction = iterator.Next();
if (transaction->busy_writing_count != 0) {
hadBusy = true;
@@ -2770,7 +2764,7 @@ cache_sync_transaction(void* _cache, int32 id)
T(Action("sync", cache, transaction));
bool hasLeftOvers;
- writer.Add(transaction, &iterator,
hasLeftOvers);
+ writer.Add(transaction, hasLeftOvers);
if (hasLeftOvers) {
// This transaction contains blocks
that a previous
@@ -2780,8 +2774,6 @@ cache_sync_transaction(void* _cache, int32 id)
}
}
- hash_close(cache->transaction_hash, &iterator, false);
-
status_t status = writer.Write();
if (status != B_OK)
return status;
@@ -2903,7 +2895,7 @@ cache_abort_transaction(void* _cache, int32 id)
block->is_dirty = false;
}
- hash_remove(cache->transaction_hash, transaction);
+ cache->transaction_hash->Remove(transaction);
delete_transaction(cache, transaction);
return B_OK;
}
@@ -3010,7 +3002,7 @@ cache_detach_sub_transaction(void* _cache, int32 id,
transaction->num_blocks = transaction->main_num_blocks;
transaction->sub_num_blocks = 0;
- hash_insert_grow(cache->transaction_hash, newTransaction);
+ cache->transaction_hash->Insert(newTransaction);
cache->last_transaction = newTransaction;
return newTransaction->id;
@@ -3326,20 +3318,20 @@ block_cache_delete(void* _cache, bool allowWrites)
// free all blocks
- uint32 cookie = 0;
- cached_block* block;
- while ((block = (cached_block*)hash_remove_first(cache->hash,
- &cookie)) != NULL) {
+ cached_block* block = cache->hash->Clear(true);
+ while (block != NULL) {
+ cached_block* next = block->next;
cache->FreeBlock(block);
+ block = next;
}
// free all transactions (they will all be aborted)
- cookie = 0;
- cache_transaction* transaction;
- while ((transaction = (cache_transaction*)hash_remove_first(
- cache->transaction_hash, &cookie)) != NULL) {
+ cache_transaction* transaction = cache->transaction_hash->Clear(true);
+ while (transaction != NULL) {
+ cache_transaction* next = transaction->next;
delete transaction;
+ transaction = next;
}
delete cache;
@@ -3377,17 +3369,14 @@ block_cache_sync(void* _cache)
MutexLocker locker(&cache->lock);
BlockWriter writer(cache);
- hash_iterator iterator;
- hash_open(cache->hash, &iterator);
+ BlockTable::Iterator iterator(cache->hash);
- cached_block* block;
- while ((block = (cached_block*)hash_next(cache->hash, &iterator)) !=
NULL) {
+ while (iterator.HasNext()) {
+ cached_block* block = iterator.Next();
if (block->CanBeWritten())
writer.Add(block);
}
- hash_close(cache->hash, &iterator, false);
-
status_t status = writer.Write();
locker.Unlock();
@@ -3408,7 +3397,8 @@ block_cache_sync_etc(void* _cache, off_t blockNumber,
size_t numBlocks)
// transaction or no transaction only
if (blockNumber < 0 || blockNumber >= cache->max_blocks) {
- panic("block_cache_sync_etc: invalid block number %" B_PRIdOFF
" (max %" B_PRIdOFF ")",
+ panic("block_cache_sync_etc: invalid block number %" B_PRIdOFF
+ " (max %" B_PRIdOFF ")",
blockNumber, cache->max_blocks - 1);
return B_BAD_VALUE;
}
@@ -3417,8 +3407,7 @@ block_cache_sync_etc(void* _cache, off_t blockNumber,
size_t numBlocks)
BlockWriter writer(cache);
for (; numBlocks > 0; numBlocks--, blockNumber++) {
- cached_block* block = (cached_block*)hash_lookup(cache->hash,
- &blockNumber);
+ cached_block* block = cache->hash->Lookup(blockNumber);
if (block == NULL)
continue;
@@ -3452,8 +3441,7 @@ block_cache_discard(void* _cache, off_t blockNumber,
size_t numBlocks)
BlockWriter writer(cache);
for (size_t i = 0; i < numBlocks; i++, blockNumber++) {
- cached_block* block = (cached_block*)hash_lookup(cache->hash,
- &blockNumber);
+ cached_block* block = cache->hash->Lookup(blockNumber);
if (block != NULL && block->previous_transaction != NULL)
writer.Add(block);
}
@@ -3465,8 +3453,7 @@ block_cache_discard(void* _cache, off_t blockNumber,
size_t numBlocks)
// reset blockNumber to its original value
for (size_t i = 0; i < numBlocks; i++, blockNumber++) {
- cached_block* block = (cached_block*)hash_lookup(cache->hash,
- &blockNumber);
+ cached_block* block = cache->hash->Lookup(blockNumber);
if (block == NULL)
continue;
@@ -3598,8 +3585,7 @@ block_cache_set_dirty(void* _cache, off_t blockNumber,
bool dirty,
block_cache* cache = (block_cache*)_cache;
MutexLocker locker(&cache->lock);
- cached_block* block = (cached_block*)hash_lookup(cache->hash,
- &blockNumber);
+ cached_block* block = cache->hash->Lookup(blockNumber);
if (block == NULL)
return B_BAD_VALUE;
if (block->is_dirty == dirty) {
############################################################################
Commit: 9d053f5975230e98e3a570697381a27ca6d51094
URL: http://cgit.haiku-os.org/haiku/commit/?id=9d053f5
Author: Adrien Destugues <pulkomandy@xxxxxxxxx>
Date: Tue Jan 13 12:31:26 2015 UTC
BOpenHashTable: document some subtleties
Mainly the interaction of resizing the table with iterators.
----------------------------------------------------------------------------
diff --git a/headers/private/kernel/util/OpenHashTable.h
b/headers/private/kernel/util/OpenHashTable.h
index 1baea62..9f54849 100644
--- a/headers/private/kernel/util/OpenHashTable.h
+++ b/headers/private/kernel/util/OpenHashTable.h
@@ -70,6 +70,16 @@ struct MallocAllocator {
};
+/** Implements an hash table with open hashing, that is, colliding entries are
+ * stored in a linked list. The table may be made to adjust its number of slots
+ * depending on the load factor (this should be enabled unless the object is to
+ * be used at times where memory allocations aren't possible, such as code
+ * called byt he memory allocator).
+ *
+ * The link between entries is part of the ValueType stored items, which makes
+ * sure the table can always accept new items and will never fail because it is
+ * out of memory (except at Init time).
+ */
template<typename Definition, bool AutoExpand = true,
bool CheckDuplicates = false, typename Allocator = MallocAllocator>
class BOpenHashTable {
@@ -168,6 +178,11 @@ public:
return B_OK;
}
+ /*! \brief Inserts a value without resizing the table.
+
+ Use this method if you need to insert a value into the table
while
+ iterating it, as regular insertion can invalidate iterators.
+ */
void InsertUnchecked(ValueType* value)
{
if (CheckDuplicates && _ExhaustiveSearch(value)) {
@@ -196,6 +211,15 @@ public:
return true;
}
+ /*! \brief Removes a value without resizing the table.
+
+ Use this method if you need to remove a value from the table
while
+ iterating it, as Remove can invalidate iterators.
+
+ Also use this method if you know you are going to reinsert the
item soon
+ (possibly with a different hash) to avoid shrinking then
growing the
+ table again.
+ */
bool RemoveUnchecked(ValueType* value)
{
size_t index = fDefinition.Hash(value) & (fTableSize - 1);
@@ -232,9 +256,11 @@ public:
return true;
}
- /*! Removes all elements from the hash table. No resizing happens.
The
- elements are not deleted. If \a returnElements is \c true, the
method
- returns all elements chained via their hash table link.
+ /*! \brief Removes all elements from the hash table.
+
+ No resizing happens. The elements are not deleted. If \a
returnElements
+ is \c true, the method returns all elements chained via their
hash table
+ link.
*/
ValueType* Clear(bool returnElements = false)
{
@@ -296,7 +322,7 @@ public:
}
/*! Resizes the table using the given allocation. The allocation
must not
- be \c NULL. It must be of size \a size, which must a value
returned
+ be \c NULL. It must be of size \a size, which must be a value
returned
earlier by ResizeNeeded(). If the size requirements have
changed in the
meantime, the method free()s the given allocation and returns
\c false,
unless \a force is \c true, in which case the supplied
allocation is
@@ -317,6 +343,11 @@ public:
return true;
}
+ /*! \brief Iterator for BOpenHashMap
+
+ The iterator is not invalidated when removing the current
element from
+ the table, unless the removal triggers a resize.
+ */
class Iterator {
public:
Iterator(const HashTable* table)
############################################################################
Commit: bb3092b298f13b7d382ea656ee9e615f677b11e0
URL: http://cgit.haiku-os.org/haiku/commit/?id=bb3092b
Author: Adrien Destugues <pulkomandy@xxxxxxxxx>
Date: Tue Jan 13 13:52:01 2015 UTC
rootfs: convert to BOpenHashTable.
* Add an fs-shell compatible version of BOpenHashTable in the fs_shell
to keep it working. The header is renamed to KOpenHashTable to avoid a
conflict with the OpenHashTable.h available in private/shared which is
not API compatible.
----------------------------------------------------------------------------
diff --git a/src/system/kernel/fs/rootfs.cpp b/src/system/kernel/fs/rootfs.cpp
index 9c1db88..e16329a 100644
--- a/src/system/kernel/fs/rootfs.cpp
+++ b/src/system/kernel/fs/rootfs.cpp
@@ -8,9 +8,11 @@
#if FS_SHELL
+# include <new>
+
# include "fssh_api_wrapper.h"
-# include "hash.h"
+# include "KOpenHashTable.h"
# include "list.h"
#else
# include <stdio.h>
@@ -23,14 +25,15 @@
# include <NodeMonitor.h>
# include <debug.h>
-# include <khash.h>
# include <lock.h>
+# include <OpenHashTable.h>
# include <util/AutoLock.h>
# include <vfs.h>
# include <vm/vm.h>
#endif
+
#if FS_SHELL
using namespace FSShell;
# define user_strlcpy(to, from, len) (strlcpy(to, from, len),
FSSH_B_OK)
@@ -71,12 +74,39 @@ struct rootfs_vnode {
struct rootfs_stream stream;
};
+struct VnodeHash {
+ typedef ino_t KeyType;
+ typedef rootfs_vnode ValueType;
+
+ size_t HashKey(KeyType key) const
+ {
+ return key;
+ }
+
+ size_t Hash(ValueType* vnode) const
+ {
+ return vnode->id;
+ }
+
+ bool Compare(KeyType key, ValueType* vnode) const
+ {
+ return vnode->id == key;
+ }
+
+ ValueType*& GetLink(ValueType* value) const
+ {
+ return value->all_next;
+ }
+};
+
+typedef BOpenHashTable<VnodeHash> VnodeTable;
+
struct rootfs {
fs_volume* volume;
dev_t id;
rw_lock lock;
ino_t next_vnode_id;
- hash_table* vnode_list_hash;
+ VnodeTable* vnode_list_hash;
struct rootfs_vnode* root_vnode;
};
@@ -117,32 +147,6 @@ current_timespec()
}
-static uint32
-rootfs_vnode_hash_func(void* _v, const void* _key, uint32 range)
-{
- struct rootfs_vnode* vnode = (rootfs_vnode*)_v;
- const ino_t* key = (const ino_t*)_key;
-
- if (vnode != NULL)
- return vnode->id % range;
-
- return (uint64)*key % range;
-}
-
-
-static int
-rootfs_vnode_compare_func(void* _v, const void* _key)
-{
- struct rootfs_vnode* v = (rootfs_vnode*)_v;
- const ino_t* key = (const ino_t*)_key;
-
- if (v->id == *key)
- return 0;
-
- return -1;
-}
-
-
static struct rootfs_vnode*
rootfs_create_vnode(struct rootfs* fs, struct rootfs_vnode* parent,
const char* name, int type)
@@ -188,7 +192,7 @@ rootfs_delete_vnode(struct rootfs* fs, struct rootfs_vnode*
v, bool force_delete
return EPERM;
// remove it from the global hash table
- hash_remove(fs->vnode_list_hash, v);
+ fs->vnode_list_hash->Remove(v);
if (S_ISDIR(v->stream.type))
mutex_destroy(&v->stream.dir.cookie_lock);
@@ -376,10 +380,9 @@ rootfs_mount(fs_volume* volume, const char* device, uint32
flags,
rw_lock_init(&fs->lock, "rootfs");
- fs->vnode_list_hash = hash_init(ROOTFS_HASH_SIZE,
- offsetof(rootfs_vnode, all_next), &rootfs_vnode_compare_func,
- &rootfs_vnode_hash_func);
- if (fs->vnode_list_hash == NULL) {
+ fs->vnode_list_hash = new(std::nothrow) VnodeTable();
+ if (fs->vnode_list_hash == NULL
+ || fs->vnode_list_hash->Init(ROOTFS_HASH_SIZE) != B_OK)
{
err = B_NO_MEMORY;
goto err2;
}
@@ -393,7 +396,7 @@ rootfs_mount(fs_volume* volume, const char* device, uint32
flags,
vnode->parent = vnode;
fs->root_vnode = vnode;
- hash_insert(fs->vnode_list_hash, vnode);
+ fs->vnode_list_hash->Insert(vnode);
publish_vnode(volume, vnode->id, vnode, &sVnodeOps, vnode->stream.type,
0);
*_rootID = vnode->id;
@@ -401,7 +404,7 @@ rootfs_mount(fs_volume* volume, const char* device, uint32
flags,
return B_OK;
err3:
- hash_uninit(fs->vnode_list_hash);
+ delete fs->vnode_list_hash;
err2:
rw_lock_destroy(&fs->lock);
free(fs);
@@ -421,17 +424,14 @@ rootfs_unmount(fs_volume* _volume)
put_vnode(fs->volume, fs->root_vnode->id);
// delete all of the vnodes
- struct hash_iterator i;
- hash_open(fs->vnode_list_hash, &i);
+ VnodeTable::Iterator i(fs->vnode_list_hash);
- while (struct rootfs_vnode* vnode = (struct rootfs_vnode*)
- hash_next(fs->vnode_list_hash, &i)) {
+ while (i.HasNext()) {
+ struct rootfs_vnode* vnode = i.Next();
rootfs_delete_vnode(fs, vnode, true);
}
- hash_close(fs->vnode_list_hash, &i, false);
-
- hash_uninit(fs->vnode_list_hash);
+ delete fs->vnode_list_hash;
rw_lock_destroy(&fs->lock);
free(fs);
@@ -503,7 +503,7 @@ rootfs_get_vnode(fs_volume* _volume, ino_t id, fs_vnode*
_vnode, int* _type,
if (!reenter)
rw_lock_read_lock(&fs->lock);
- vnode = (rootfs_vnode*)hash_lookup(fs->vnode_list_hash, &id);
+ vnode = fs->vnode_list_hash->Lookup(id);
if (!reenter)
rw_lock_read_unlock(&fs->lock);
@@ -644,7 +644,7 @@ rootfs_create_dir(fs_volume* _volume, fs_vnode* _dir, const
char* name,
return B_NO_MEMORY;
rootfs_insert_in_dir(fs, dir, vnode);
- hash_insert(fs->vnode_list_hash, vnode);
+ fs->vnode_list_hash->Insert(vnode);
entry_cache_add(fs->volume->id, dir->id, name, vnode->id);
notify_entry_created(fs->id, dir->id, name, vnode->id);
@@ -877,7 +877,7 @@ rootfs_symlink(fs_volume* _volume, fs_vnode* _dir, const
char* name,
return B_NO_MEMORY;
rootfs_insert_in_dir(fs, dir, vnode);
- hash_insert(fs->vnode_list_hash, vnode);
+ fs->vnode_list_hash->Insert(vnode);
vnode->stream.symlink.path = strdup(path);
if (vnode->stream.symlink.path == NULL) {
@@ -1086,7 +1086,7 @@ rootfs_create_special_node(fs_volume* _volume, fs_vnode*
_dir, const char* name,
else
flags |= B_VNODE_PUBLISH_REMOVED;
- hash_insert(fs->vnode_list_hash, vnode);
+ fs->vnode_list_hash->Insert(vnode);
_superVnode->private_node = vnode;
_superVnode->ops = &sVnodeOps;
diff --git a/src/tools/fs_shell/KOpenHashTable.h
b/src/tools/fs_shell/KOpenHashTable.h
new file mode 100644
index 0000000..363c225
--- /dev/null
+++ b/src/tools/fs_shell/KOpenHashTable.h
@@ -0,0 +1,497 @@
+/*
+ * Copyright 2007, Hugo Santos. All Rights Reserved.
+ * Distributed under the terms of the MIT License.
+ */
+#ifndef _KERNEL_UTIL_OPEN_HASH_TABLE_H
+#define _KERNEL_UTIL_OPEN_HASH_TABLE_H
+
+
+#include "fssh_api_wrapper.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#ifdef _KERNEL_MODE
+# include <KernelExport.h>
+# include <util/kernel_cpp.h>
+# include <util/TypeOperation.h>
+#else
+# include <TypeOperation.h>
+#endif
+
+
+/*!
+ The Definition template must have four methods: `HashKey', `Hash',
+ `Compare' and `GetLink;. It must also define several types as shown in
the
+ following example:
+
+ struct Foo {
+ int bar;
+
+ Foo* fNext;
+ };
+
+ struct HashTableDefinition {
+ typedef int KeyType;
+ typedef Foo ValueType;
+
+ size_t HashKey(KeyType key) const
+ {
+ return key >> 1;
+ }
+
+ size_t Hash(ValueType* value) const
+ {
+ return HashKey(value->bar);
+ }
+
+ bool Compare(KeyType key, ValueType* value) const
+ {
+ return value->bar == key;
+ }
+
+ ValueType*& GetLink(ValueType* value) const
+ {
+ return value->fNext;
+ }
+ };
+*/
+
+
+struct MallocAllocator {
+ void* Allocate(size_t size) const
+ {
+ return malloc(size);
+ }
+
+ void Free(void* memory) const
+ {
+ free(memory);
+ }
+};
+
+
+/** Implements an hash table with open hashing, that is, colliding entries are
+ * stored in a linked list. The table may be made to adjust its number of slots
+ * depending on the load factor (this should be enabled unless the object is to
+ * be used at times where memory allocations aren't possible, such as code
+ * called byt he memory allocator).
+ *
+ * The link between entries is part of the ValueType stored items, which makes
+ * sure the table can always accept new items and will never fail because it is
+ * out of memory (except at Init time).
+ */
+template<typename Definition, bool AutoExpand = true,
+ bool CheckDuplicates = false, typename Allocator = MallocAllocator>
+class BOpenHashTable {
+public:
+ typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates>
HashTable;
+ typedef typename Definition::KeyType KeyType;
+ typedef typename Definition::ValueType ValueType;
+
+ static const size_t kMinimumSize = 8;
+
+ // All allocations are of power of 2 lengths.
+
+ // regrowth factor: 200 / 256 = 78.125%
+ // 50 / 256 = 19.53125%
+
+ BOpenHashTable()
+ :
+ fTableSize(0),
+ fItemCount(0),
+ fTable(NULL)
+ {
+ }
+
+ BOpenHashTable(const Definition& definition)
+ :
+ fDefinition(definition),
+ fTableSize(0),
+ fItemCount(0),
+ fTable(NULL)
+ {
+ }
+
+ BOpenHashTable(const Definition& definition, const Allocator& allocator)
+ :
+ fDefinition(definition),
+ fAllocator(allocator),
+ fTableSize(0),
+ fItemCount(0),
+ fTable(NULL)
+ {
+ }
+
+ ~BOpenHashTable()
+ {
+ fAllocator.Free(fTable);
+ }
+
+ status_t Init(size_t initialSize = kMinimumSize)
+ {
+ if (initialSize > 0 && !_Resize(initialSize))
+ return B_NO_MEMORY;
+ return B_OK;
+ }
+
+ size_t TableSize() const
+ {
+ return fTableSize;
+ }
+
+ bool IsEmpty() const
+ {
+ return fItemCount == 0;
+ }
+
+ size_t CountElements() const
+ {
+ return fItemCount;
+ }
+
+ ValueType* Lookup(typename TypeOperation<KeyType>::ConstRefT key) const
+ {
+ if (fTableSize == 0)
+ return NULL;
+
+ size_t index = fDefinition.HashKey(key) & (fTableSize - 1);
+ ValueType* slot = fTable[index];
+
+ while (slot) {
+ if (fDefinition.Compare(key, slot))
+ break;
+ slot = _Link(slot);
+ }
+
+ return slot;
+ }
+
+ status_t Insert(ValueType* value)
+ {
+ if (fTableSize == 0) {
+ if (!_Resize(kMinimumSize))
+ return B_NO_MEMORY;
+ } else if (AutoExpand && fItemCount >= (fTableSize * 200 / 256))
+ _Resize(fTableSize * 2);
+
+ InsertUnchecked(value);
+ return B_OK;
+ }
+
+ /*! \brief Inserts a value without resizing the table.
+
+ Use this method if you need to insert a value into the table
while
+ iterating it, as regular insertion can invalidate iterators.
+ */
+ void InsertUnchecked(ValueType* value)
+ {
+ if (CheckDuplicates && _ExhaustiveSearch(value)) {
+#if defined(_KERNEL_MODE) || defined(FS_SHELL)
+ panic("Hash Table: value already in table.");
+#else
+ debugger("Hash Table: value already in table.");
+#endif
+ }
+
+ _Insert(fTable, fTableSize, value);
+ fItemCount++;
+ }
+
+ // TODO: a ValueType* Remove(const KeyType& key) method is missing
+
+ bool Remove(ValueType* value)
+ {
+ if (!RemoveUnchecked(value))
+ return false;
+
+ if (AutoExpand && fTableSize > kMinimumSize
+ && fItemCount < (fTableSize * 50 / 256))
+ _Resize(fTableSize / 2);
+
+ return true;
+ }
+
+ /*! \brief Removes a value without resizing the table.
+
+ Use this method if you need to remove a value from the table
while
+ iterating it, as Remove can invalidate iterators.
+
+ Also use this method if you know you are going to reinsert the
item soon
+ (possibly with a different hash) to avoid shrinking then
growing the
+ table again.
+ */
+ bool RemoveUnchecked(ValueType* value)
+ {
+ size_t index = fDefinition.Hash(value) & (fTableSize - 1);
+ ValueType* previous = NULL;
+ ValueType* slot = fTable[index];
+
+ while (slot) {
+ ValueType* next = _Link(slot);
+
+ if (value == slot) {
+ if (previous)
+ _Link(previous) = next;
+ else
+ fTable[index] = next;
+ break;
+ }
+
+ previous = slot;
+ slot = next;
+ }
+
+ if (slot == NULL)
+ return false;
+
+ if (CheckDuplicates && _ExhaustiveSearch(value)) {
+#if defined(_KERNEL_MODE) || defined(FS_SHELL)
+ panic("Hash Table: duplicate detected.");
+#else
+ debugger("Hash Table: duplicate detected.");
+#endif
+ }
+
+ fItemCount--;
+ return true;
+ }
+
+ /*! \brief Removes all elements from the hash table.
+
+ No resizing happens. The elements are not deleted. If \a
returnElements
+ is \c true, the method returns all elements chained via their
hash table
+ link.
+ */
+ ValueType* Clear(bool returnElements = false)
+ {
+ if (fItemCount == 0)
+ return NULL;
+
+ ValueType* result = NULL;
+
+ if (returnElements) {
+ ValueType** nextPointer = &result;
+
+ // iterate through all buckets
+ for (size_t i = 0; i < fTableSize; i++) {
+ ValueType* element = fTable[i];
+ if (element != NULL) {
+ // add the bucket to the list
+ *nextPointer = element;
+
+ // update nextPointer to point to the
fNext of the last
+ // element in the bucket
+ while (element != NULL) {
+ nextPointer = &_Link(element);
+ element = *nextPointer;
+ }
+ }
+ }
+ }
+
+ memset(this->fTable, 0, sizeof(ValueType*) * this->fTableSize);
+ fItemCount = 0;
+
+ return result;
+ }
+
+ /*! If the table needs resizing, the number of bytes for the
required
+ allocation is returned. If no resizing is needed, 0 is returned.
+ */
+ size_t ResizeNeeded() const
+ {
+ size_t size = fTableSize;
+ if (size == 0 || fItemCount >= (size * 200 / 256)) {
+ // grow table
+ if (size == 0)
+ size = kMinimumSize;
+ while (fItemCount >= size * 200 / 256)
+ size <<= 1;
+ } else if (size > kMinimumSize && fItemCount < size * 50 / 256)
{
+ // shrink table
+ while (fItemCount < size * 50 / 256)
+ size >>= 1;
+ if (size < kMinimumSize)
+ size = kMinimumSize;
+ }
+
+ if (size == fTableSize)
+ return 0;
+
+ return size * sizeof(ValueType*);
+ }
+
+ /*! Resizes the table using the given allocation. The allocation
must not
+ be \c NULL. It must be of size \a size, which must be a value
returned
+ earlier by ResizeNeeded(). If the size requirements have
changed in the
+ meantime, the method free()s the given allocation and returns
\c false,
+ unless \a force is \c true, in which case the supplied
allocation is
+ used in any event.
+ Otherwise \c true is returned.
+ If \a oldTable is non-null and resizing is successful, the old
table
+ will not be freed, but will be returned via this parameter
instead.
+ */
+ bool Resize(void* allocation, size_t size, bool force = false,
+ void** oldTable = NULL)
+ {
+ if (!force && size != ResizeNeeded()) {
+ fAllocator.Free(allocation);
+ return false;
+ }
+
+ _Resize((ValueType**)allocation, size / sizeof(ValueType*),
oldTable);
+ return true;
+ }
+
+ /*! \brief Iterator for BOpenHashMap
+
+ The iterator is not invalidated when removing the current
element from
+ the table, unless the removal triggers a resize.
+ */
+ class Iterator {
+ public:
+ Iterator(const HashTable* table)
+ : fTable(table)
+ {
+ Rewind();
+ }
+
+ Iterator(const HashTable* table, size_t index, ValueType* value)
+ : fTable(table), fIndex(index), fNext(value) {}
+
+ bool HasNext() const { return fNext != NULL; }
+
+ ValueType* Next()
+ {
+ ValueType* current = fNext;
+ _GetNext();
+ return current;
+ }
+
+ void Rewind()
+ {
+ // get the first one
+ fIndex = 0;
+ fNext = NULL;
+ _GetNext();
+ }
+
+ protected:
+ Iterator() {}
+
+ void _GetNext()
+ {
+ if (fNext)
+ fNext = fTable->_Link(fNext);
+
+ while (fNext == NULL && fIndex < fTable->fTableSize)
+ fNext = fTable->fTable[fIndex++];
+ }
+
+ const HashTable* fTable;
+ size_t fIndex;
+ ValueType* fNext;
+ };
+
+ Iterator GetIterator() const
+ {
+ return Iterator(this);
+ }
+
+ Iterator GetIterator(typename TypeOperation<KeyType>::ConstRefT key)
const
+ {
+ if (fTableSize == 0)
+ return Iterator(this, fTableSize, NULL);
+
+ size_t index = fDefinition.HashKey(key) & (fTableSize - 1);
+ ValueType* slot = fTable[index];
+
+ while (slot) {
+ if (fDefinition.Compare(key, slot))
+ break;
+ slot = _Link(slot);
+ }
+
+ if (slot == NULL)
+ return Iterator(this, fTableSize, NULL);
+
+ return Iterator(this, index + 1, slot);
+ }
+
+protected:
+ // for g++ 2.95
+ friend class Iterator;
+
+ void _Insert(ValueType** table, size_t tableSize, ValueType* value)
+ {
+ size_t index = fDefinition.Hash(value) & (tableSize - 1);
+
+ _Link(value) = table[index];
+ table[index] = value;
+ }
+
+ bool _Resize(size_t newSize)
+ {
+ ValueType** newTable
+ = (ValueType**)fAllocator.Allocate(sizeof(ValueType*) *
newSize);
+ if (newTable == NULL)
+ return false;
+
+ _Resize(newTable, newSize);
+ return true;
+ }
+
+ void _Resize(ValueType** newTable, size_t newSize, void** _oldTable =
NULL)
+ {
+ for (size_t i = 0; i < newSize; i++)
+ newTable[i] = NULL;
+
+ if (fTable) {
+ for (size_t i = 0; i < fTableSize; i++) {
+ ValueType* bucket = fTable[i];
+ while (bucket) {
+ ValueType* next = _Link(bucket);
+ _Insert(newTable, newSize, bucket);
+ bucket = next;
+ }
+ }
+
+ if (_oldTable != NULL)
+ *_oldTable = fTable;
+ else
+ fAllocator.Free(fTable);
+ } else if (_oldTable != NULL)
+ *_oldTable = NULL;
+
+ fTableSize = newSize;
+ fTable = newTable;
+ }
+
+ ValueType*& _Link(ValueType* bucket) const
+ {
+ return fDefinition.GetLink(bucket);
+ }
+
+ bool _ExhaustiveSearch(ValueType* value) const
+ {
+ for (size_t i = 0; i < fTableSize; i++) {
+ ValueType* bucket = fTable[i];
+ while (bucket) {
+ if (bucket == value)
+ return true;
+ bucket = _Link(bucket);
+ }
+ }
+
+ return false;
+ }
+
+ Definition fDefinition;
+ Allocator fAllocator;
+ size_t fTableSize;
+ size_t fItemCount;
+ ValueType** fTable;
+};
+
+#endif // _KERNEL_UTIL_OPEN_HASH_TABLE_H
############################################################################
Commit: ace74964f1cc6cf459950ce03240d6b2b28cbb38
URL: http://cgit.haiku-os.org/haiku/commit/?id=ace7496
Author: Adrien Destugues <pulkomandy@xxxxxxxxx>
Date: Tue Jan 13 14:11:34 2015 UTC
Ticket: https://dev.haiku-os.org/ticket/9552
Remove khash from the sources.
Fixes #9552.
----------------------------------------------------------------------------
diff --git a/headers/private/kernel/util/khash.h
b/headers/private/kernel/util/khash.h
deleted file mode 100644
index 609b08a..0000000
--- a/headers/private/kernel/util/khash.h
+++ /dev/null
@@ -1,61 +0,0 @@
-/*
- * Copyright 2002-2008, Haiku Inc. All rights reserved.
- * Distributed under the terms of the MIT License.
- *
- * Copyright 2001-2002, Travis Geiselbrecht. All rights reserved.
- * Distributed under the terms of the NewOS License.
- */
-#ifndef _KERNEL_UTIL_KHASH_H
-#define _KERNEL_UTIL_KHASH_H
-
-
-#include <util/StringHash.h>
-
-
-// can be allocated on the stack
-typedef struct hash_iterator {
- void *current;
- int bucket;
-} hash_iterator;
-
-typedef struct hash_table hash_table;
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-struct hash_table *hash_init(uint32 table_size, int next_ptr_offset,
- int compare_func(void *element, const void *key),
- uint32 hash_func(void *element, const void *key, uint32 range));
-int hash_uninit(struct hash_table *table);
-status_t hash_insert(struct hash_table *table, void *_element);
-status_t hash_insert_grow(struct hash_table *table, void *_element);
-status_t hash_remove(struct hash_table *table, void *_element);
-void hash_remove_current(struct hash_table *table, struct hash_iterator
*iterator);
-void *hash_remove_first(struct hash_table *table, uint32 *_cookie);
-void *hash_find(struct hash_table *table, void *e);
-void *hash_lookup(struct hash_table *table, const void *key);
-struct hash_iterator *hash_open(struct hash_table *table, struct hash_iterator
*i);
-void hash_close(struct hash_table *table, struct hash_iterator *i, bool
free_iterator);
-void *hash_next(struct hash_table *table, struct hash_iterator *i);
-void hash_rewind(struct hash_table *table, struct hash_iterator *i);
-uint32 hash_count_elements(struct hash_table *table);
-uint32 hash_count_used_slots(struct hash_table *table);
-void hash_dump_table(struct hash_table* table);
-
-/* function pointers must look like this:
- *
- * uint32 hash_func(void *e, const void *key, uint32 range);
- * hash function should calculate hash on either e or key,
- * depending on which one is not NULL - they also need
- * to make sure the returned value is within range.
- * int compare_func(void *e, const void *key);
- * compare function should compare the element with
- * the key, returning 0 if equal, other if not
- */
-
-#ifdef __cplusplus
-}
-#endif
-
-#endif /* _KERNEL_UTIL_KHASH_H */
diff --git a/src/add-ons/kernel/file_systems/userlandfs/server/haiku/Jamfile
b/src/add-ons/kernel/file_systems/userlandfs/server/haiku/Jamfile
index a0fd48c..b59ea6c 100644
--- a/src/add-ons/kernel/file_systems/userlandfs/server/haiku/Jamfile
+++ b/src/add-ons/kernel/file_systems/userlandfs/server/haiku/Jamfile
@@ -35,7 +35,6 @@ SharedLibrary libuserlandfs_haiku_kernel.so
# kernel
block_cache.cpp
file_map.cpp
- khash.cpp
Notifications.cpp
Referenceable.cpp
@@ -66,9 +65,5 @@ SEARCH on [ FGristFiles
] = [ FDirName $(HAIKU_TOP) src system kernel cache ] ;
SEARCH on [ FGristFiles
- khash.cpp
- ] = [ FDirName $(HAIKU_TOP) src system kernel util ] ;
-
-SEARCH on [ FGristFiles
Referenceable.cpp
] = [ FDirName $(HAIKU_TOP) src kits support ] ;
diff --git a/src/system/kernel/util/Jamfile b/src/system/kernel/util/Jamfile
index 42fa42e..5d709e1 100644
--- a/src/system/kernel/util/Jamfile
+++ b/src/system/kernel/util/Jamfile
@@ -10,7 +10,6 @@ KernelMergeObject kernel_util.o :
inet_ntop.c
kernel_cpp.cpp
KernelReferenceable.cpp
- khash.cpp
list.cpp
queue.cpp
ring_buffer.cpp
diff --git a/src/system/kernel/util/khash.cpp b/src/system/kernel/util/khash.cpp
deleted file mode 100644
index 4b626ee..0000000
--- a/src/system/kernel/util/khash.cpp
+++ /dev/null
@@ -1,424 +0,0 @@
-/*
- * Copyright 2002-2008, Haiku Inc. All rights reserved.
- * Distributed under the terms of the MIT License.
- *
- * Copyright 2001, Travis Geiselbrecht. All rights reserved.
- * Distributed under the terms of the NewOS License.
- */
-
-//! Generic hash table
-
-
-#include <KernelExport.h>
-#include <debug.h>
-#include <util/khash.h>
-
-#include <stdlib.h>
-#include <string.h>
-
-#define TRACE_HASH 0
-#if TRACE_HASH
-# define TRACE(x) dprintf x
-#else
-# define TRACE(x) ;
-#endif
-
-// TODO: the hashtable is not expanded when necessary (no load factor, nothing)
-// resizing should be optional, though, in case the hash is used
at times
-// that forbid resizing.
-
-struct hash_table {
- struct hash_element **table;
- int next_ptr_offset;
- uint32 table_size;
- int num_elements;
- int flags;
- int (*compare_func)(void *e, const void *key);
- uint32 (*hash_func)(void *e, const void *key, uint32 range);
-};
-
-// XXX gross hack
-#define NEXT_ADDR(t, e) ((void *)(((unsigned long)(e)) + (t)->next_ptr_offset))
-#define NEXT(t, e) ((void *)(*(unsigned long *)NEXT_ADDR(t, e)))
-#define PUT_IN_NEXT(t, e, val) (*(unsigned long *)NEXT_ADDR(t, e) =
(long)(val))
-
-
-const uint32 kPrimes [] = {
- 13, 31, 61, 127, 251,
- 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139,
- 524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393,
67108859,
- 134217689, 268435399, 536870909, 1073741789, 2147483647, 0
-};
-
-
-static uint32
-get_prime_table_size(uint32 size)
-{
- int i;
- for (i = 0; kPrimes[i] != 0; i++) {
- if (kPrimes[i] > size)
- return kPrimes[i];
- }
-
- return kPrimes[i - 1];
-}
-
-
-static inline void *
-next_element(hash_table *table, void *element)
-{
- // ToDo: should we use this instead of the NEXT() macro?
- return (void *)(*(unsigned long *)NEXT_ADDR(table, element));
-}
-
-
-static status_t
-hash_grow(struct hash_table *table)
-{
- uint32 newSize = get_prime_table_size(table->num_elements);
- struct hash_element **newTable;
- uint32 index;
-
- if (table->table_size >= newSize)
- return B_OK;
-
- newTable = (struct hash_element **)malloc(sizeof(void *) * newSize);
- if (newTable == NULL)
- return B_NO_MEMORY;
-
- memset(newTable, 0, sizeof(void *) * newSize);
-
- // rehash all the entries and add them to the new table
- for (index = 0; index < table->table_size; index++) {
- void *element;
- void *next;
-
- for (element = table->table[index]; element != NULL; element =
next) {
- uint32 hash = table->hash_func(element, NULL, newSize);
- next = NEXT(table, element);
- PUT_IN_NEXT(table, element, newTable[hash]);
- newTable[hash] = (struct hash_element *)element;
- }
- }
-
- free(table->table);
-
- table->table = newTable;
- table->table_size = newSize;
-
- TRACE(("hash_grow: grown table %p, new size %lu\n", table, newSize));
- return B_OK;
-}
-
-
-// #pragma mark - kernel private API
-
-
-struct hash_table *
-hash_init(uint32 tableSize, int nextPointerOffset,
- int compareFunc(void *e, const void *key),
- uint32 hashFunc(void *e, const void *key, uint32 range))
-{
- struct hash_table *t;
- uint32 i;
-
- tableSize = get_prime_table_size(tableSize);
-
- if (compareFunc == NULL || hashFunc == NULL) {
- dprintf("hash_init() called with NULL function pointer\n");
- return NULL;
- }
-
- t = (struct hash_table *)malloc(sizeof(struct hash_table));
- if (t == NULL)
- return NULL;
-
- t->table = (struct hash_element **)malloc(sizeof(void *) * tableSize);
- if (t->table == NULL) {
- free(t);
- return NULL;
- }
-
- for (i = 0; i < tableSize; i++)
- t->table[i] = NULL;
-
- t->table_size = tableSize;
- t->next_ptr_offset = nextPointerOffset;
- t->flags = 0;
- t->num_elements = 0;
- t->compare_func = compareFunc;
- t->hash_func = hashFunc;
-
- TRACE(("hash_init: created table %p, next_ptr_offset %d, compare_func
%p, hash_func %p\n",
- t, nextPointerOffset, compareFunc, hashFunc));
-
- return t;
-}
-
-
-int
-hash_uninit(struct hash_table *table)
-{
- ASSERT(table->num_elements == 0);
-
- free(table->table);
- free(table);
-
- return 0;
-}
-
-
-status_t
-hash_insert(struct hash_table *table, void *element)
-{
- uint32 hash;
-
- ASSERT(table != NULL && element != NULL);
- TRACE(("hash_insert: table %p, element %p\n", table, element));
-
- hash = table->hash_func(element, NULL, table->table_size);
- PUT_IN_NEXT(table, element, table->table[hash]);
- table->table[hash] = (struct hash_element *)element;
- table->num_elements++;
-
- return B_OK;
-}
-
-
-status_t
-hash_insert_grow(struct hash_table *table, void *element)
-{
- uint32 hash;
-
- ASSERT(table != NULL && element != NULL);
- TRACE(("hash_insert_grow: table %p, element %p\n", table, element));
-
- hash = table->hash_func(element, NULL, table->table_size);
- PUT_IN_NEXT(table, element, table->table[hash]);
- table->table[hash] = (struct hash_element *)element;
- table->num_elements++;
-
- if ((uint32)table->num_elements > table->table_size) {
- //dprintf("hash_insert: table has grown too much: %d in %d\n",
table->num_elements, (int)table->table_size);
- hash_grow(table);
- }
-
- return B_OK;
-}
-
-
-status_t
-hash_remove(struct hash_table *table, void *_element)
-{
- uint32 hash = table->hash_func(_element, NULL, table->table_size);
- void *element, *lastElement = NULL;
-
- for (element = table->table[hash]; element != NULL;
- lastElement = element, element = NEXT(table, element)) {
- if (element == _element) {
- if (lastElement != NULL) {
- // connect the previous entry with the next one
- PUT_IN_NEXT(table, lastElement, NEXT(table,
element));
- } else
- table->table[hash] = (struct hash_element
*)NEXT(table, element);
- table->num_elements--;
-
- return B_OK;
- }
- }
-
- return B_ERROR;
-}
-
-
-void
-hash_remove_current(struct hash_table *table, struct hash_iterator *iterator)
-{
- uint32 index = iterator->bucket;
- void *element;
- void *lastElement = NULL;
-
- if (iterator->current == NULL || (element = table->table[index]) ==
NULL) {
- panic("hash_remove_current(): invalid iteration state");
- return;
- }
-
- while (element != NULL) {
- if (element == iterator->current) {
- iterator->current = lastElement;
-
- if (lastElement != NULL) {
- // connect the previous entry with the next one
- PUT_IN_NEXT(table, lastElement, NEXT(table,
element));
- } else {
- table->table[index] = (struct hash_element
*)NEXT(table,
- element);
-
- // We need to rewind the bucket, as hash_next()
advances to the
- // next bucket when iterator->current is NULL.
With this we
- // basically move the iterator between the end
of the last
- // bucket and before the start of this one so
hash_next()
- // doesn't skip the rest of this bucket.
- iterator->bucket--;
- }
-
- table->num_elements--;
- return;
- }
-
- lastElement = element;
- element = NEXT(table, element);
- }
-
- panic("hash_remove_current(): current element not found!");
-}
-
-
-void *
-hash_remove_first(struct hash_table *table, uint32 *_cookie)
-{
- uint32 index;
-
- for (index = _cookie ? *_cookie : 0; index < table->table_size;
index++) {
- void *element = table->table[index];
- if (element != NULL) {
- // remove the first element we find
- table->table[index] = (struct hash_element
*)NEXT(table, element);
- table->num_elements--;
- if (_cookie)
- *_cookie = index;
- return element;
- }
- }
-
- return NULL;
-}
-
-
-void *
-hash_find(struct hash_table *table, void *searchedElement)
-{
- uint32 hash = table->hash_func(searchedElement, NULL,
table->table_size);
- void *element;
-
- for (element = table->table[hash]; element != NULL; element =
NEXT(table, element)) {
- if (element == searchedElement)
- return element;
- }
-
- return NULL;
-}
-
-
-void *
-hash_lookup(struct hash_table *table, const void *key)
-{
- uint32 hash = table->hash_func(NULL, key, table->table_size);
- void *element;
-
- for (element = table->table[hash]; element != NULL; element =
NEXT(table, element)) {
- if (table->compare_func(element, key) == 0)
- return element;
- }
-
- return NULL;
-}
-
-
-struct hash_iterator *
-hash_open(struct hash_table *table, struct hash_iterator *iterator)
-{
- if (iterator == NULL) {
- iterator = (struct hash_iterator *)malloc(sizeof(struct
hash_iterator));
- if (iterator == NULL)
- return NULL;
- }
-
- hash_rewind(table, iterator);
-
- return iterator;
-}
-
-
-void
-hash_close(struct hash_table *table, struct hash_iterator *iterator, bool
freeIterator)
-{
- if (freeIterator)
- free(iterator);
-}
-
-
-void
-hash_rewind(struct hash_table *table, struct hash_iterator *iterator)
-{
- iterator->current = NULL;
- iterator->bucket = -1;
-}
-
-
-void *
-hash_next(struct hash_table *table, struct hash_iterator *iterator)
-{
- uint32 index;
-
-restart:
- if (iterator->current == NULL) {
- // get next bucket
- for (index = (uint32)(iterator->bucket + 1); index <
table->table_size; index++) {
- if (table->table[index]) {
- iterator->bucket = index;
- iterator->current = table->table[index];
- break;
- }
- }
- } else {
- iterator->current = NEXT(table, iterator->current);
- if (!iterator->current)
- goto restart;
- }
-
- return iterator->current;
-}
-
-
-uint32
-hash_count_elements(struct hash_table *table)
-{
- return table->num_elements;
-}
-
-
-uint32
-hash_count_used_slots(struct hash_table *table)
-{
- uint32 usedSlots = 0;
- uint32 i;
- for (i = 0; i < table->table_size; i++) {
- if (table->table[i] != NULL)
- usedSlots++;
- }
-
- return usedSlots;
-}
-
-
-void
-hash_dump_table(struct hash_table* table)
-{
- uint32 i;
-
- dprintf("hash table %p, table size: %" B_PRIu32 ", elements: %u\n",
table,
- table->table_size, table->num_elements);
-
- for (i = 0; i < table->table_size; i++) {
- struct hash_element* element = table->table[i];
- if (element != NULL) {
- dprintf("%6" B_PRIu32 ":", i);
- while (element != NULL) {
- dprintf(" %p", element);
- element = (hash_element*)NEXT(table, element);
- }
- dprintf("\n");
- }
- }
-}
diff --git a/src/tests/add-ons/kernel/kernelland_emu/Jamfile
b/src/tests/add-ons/kernel/kernelland_emu/Jamfile
index 761394b..f5d182e 100644
--- a/src/tests/add-ons/kernel/kernelland_emu/Jamfile
+++ b/src/tests/add-ons/kernel/kernelland_emu/Jamfile
@@ -15,7 +15,6 @@ SharedLibrary libkernelland_emu.so :
smp.cpp
vm.cpp
- khash.cpp
list.cpp
: be [ TargetLibstdc++ ] ;
@@ -24,5 +23,5 @@ AbsSymLink <boot!home!config!lib>libkernelland_emu.so :
libkernelland_emu.so
: /boot/home/config/lib : false ;
SEARCH on [ FGristFiles
- list.cpp khash.cpp
+ list.cpp
] = [ FDirName $(HAIKU_TOP) src system kernel util ] ;
diff --git a/src/tests/system/kernel/cache/Jamfile
b/src/tests/system/kernel/cache/Jamfile
index b17bead..90a03b7 100644
--- a/src/tests/system/kernel/cache/Jamfile
+++ b/src/tests/system/kernel/cache/Jamfile
@@ -14,7 +14,6 @@ StdBinCommands
SimpleTest BlockMapTest :
BlockMapTest.cpp
BlockMap.cpp
- khash.cpp
: libkernelland_emu.so ;
SimpleTest block_cache_test :
############################################################################
Revision: hrev48670
Commit: a7d444d14560a4cb9836ccfe39c649f3dc1f028a
URL: http://cgit.haiku-os.org/haiku/commit/?id=a7d444d
Author: Adrien Destugues <pulkomandy@xxxxxxxxx>
Date: Tue Jan 13 08:21:40 2015 UTC
Remove old block cache implementation
This was not used anywhere except the tests written for it (which is
also removed).
----------------------------------------------------------------------------
diff --git a/src/system/kernel/cache/BlockMap.cpp
b/src/system/kernel/cache/BlockMap.cpp
deleted file mode 100644
index 1ef3ead..0000000
--- a/src/system/kernel/cache/BlockMap.cpp
+++ /dev/null
@@ -1,240 +0,0 @@
-/*
-** Copyright 2004, Axel Dörfler, axeld@xxxxxxxxxxxxxxxx. All rights reserved.
-** Distributed under the terms of the Haiku License.
-*/
-
-
-/** The BlockMap stores offset:address pairs; you can map an offset to a
specific address.
- * It has been designed to contain few and mostly contiguous offset
mappings - it is used
- * by the file cache to keep track about which blocks of the file are
already in memory.
- * The offsets may spread over a very large amount.
- *
- * Internally, it stores small and contiguous address arrays of a certain
size, and
- * accesses those using a hash table. Address values of NULL are equal to
non existing
- * mappings; that value cannot be stored. At the current size, each hash
entry can
- * map 60 addresses which corresponds to a file range of 240 kB.
- * It currently does not do any locking; it assumes a safe environment
which you are
- * responsible for to create when you call its functions.
- */
-
-
-#include "BlockMap.h"
-
-#include <KernelExport.h>
-#include <util/kernel_cpp.h>
-
-#include <stdlib.h>
-#include <string.h>
-
-
-//#define TRACE_BLOCK_MAP
-#ifdef TRACE_BLOCK_MAP
-# define TRACE(x) dprintf x
-#else
-# define TRACE(x)
-#endif
-
-
-// ToDo: when we have a better allocator, change the number of addresses to a
power of two
-// currently, this structure takes 256 bytes total
-
-struct BlockMap::block_entry {
- block_entry *next;
- uint32 used;
- off_t offset;
- addr_t address[60];
-};
-
-#define BLOCK_ARRAY_SIZE (sizeof(BlockMap::block_entry::address) /
sizeof(addr_t))
-
-static inline off_t
-to_block_entry_offset(off_t offset, uint32 &index)
-{
- // ToDo: improve this once we have a power of two array size
- off_t baseOffset = (offset / BLOCK_ARRAY_SIZE) * BLOCK_ARRAY_SIZE;
- index = uint32(offset - baseOffset);
-
- return baseOffset;
-}
-
-
-static int
-block_entry_compare(void *_entry, const void *_offset)
-{
- BlockMap::block_entry *entry = (BlockMap::block_entry *)_entry;
- const off_t *offset = (const off_t *)_offset;
-
- return entry->offset - *offset;
-}
-
-
-static uint32
-block_entry_hash(void *_entry, const void *_offset, uint32 range)
-{
- BlockMap::block_entry *entry = (BlockMap::block_entry *)_entry;
- const off_t *offset = (const off_t *)_offset;
-
- if (entry != NULL)
- return entry->offset % range;
-
- return *offset % range;
-}
-
-
-// #pragma mark -
-
-
-BlockMap::BlockMap(off_t size)
- :
- fSize(size)
-{
- fHashTable = hash_init(16, 0, &block_entry_compare, &block_entry_hash);
-}
-
-
-BlockMap::~BlockMap()
-{
-}
-
-
-/** Checks whether or not the construction of the BlockMap were successful.
- */
-
-status_t
-BlockMap::InitCheck() const
-{
- return fHashTable != NULL ? B_OK : B_NO_MEMORY;
-}
-
-
-/** Sets the size of the block map - all existing entries beyond this size
will be
- * removed from the map, and their memory is freed.
- */
-
-void
-BlockMap::SetSize(off_t size)
-{
- TRACE(("BlockMap::SetSize(%Ld)\n", size));
-
- if (size >= fSize) {
- // nothing to do
- fSize = size;
- return;
- }
-
- // ToDo: remove all mappings beyond the file size
-}
-
-
-/** Upon successful exit which is indicated by a return value of B_OK, the
"_entry"
- * argument points to a block_entry structure containing the data for the
given
- * offset.
- * The offset must have been normalized to the base offset values of a
block entry
- * already.
- */
-
-status_t
-BlockMap::GetBlockEntry(off_t baseOffset, block_entry **_entry)
-{
- block_entry *entry = (block_entry *)hash_lookup(fHashTable,
&baseOffset);
- if (entry == NULL)
- return B_ENTRY_NOT_FOUND;
-
- *_entry = entry;
- return B_OK;
-}
-
-
-status_t
-BlockMap::Remove(off_t offset, off_t count)
-{
- TRACE(("BlockMap::Remove(offset = %Ld, count = %Ld)\n", offset, count));
-
- uint32 index;
- off_t baseOffset = to_block_entry_offset(offset, index);
- block_entry *entry;
-
- while (count > 0) {
- int32 max = min_c(BLOCK_ARRAY_SIZE, index + count);
- int32 blocks = max - index;
-
- if (GetBlockEntry(baseOffset, &entry) == B_OK) {
- for (int32 i = index; i < max; i++) {
- if (entry->address[i] != NULL)
- entry->used--;
-
- entry->address[i] = NULL;
- }
-
- if (entry->used == 0) {
- // release entry if it's no longer used
- hash_remove(fHashTable, entry);
- free(entry);
- }
- }
-
- baseOffset += BLOCK_ARRAY_SIZE;
- count -= blocks;
- index = 0;
- }
-
- return B_OK;
-}
-
-
-status_t
-BlockMap::Set(off_t offset, addr_t address)
-{
- TRACE(("BlockMap::Set(offset = %Ld, address = %08lx)\n", offset,
address));
-
- uint32 index;
- off_t baseOffset = to_block_entry_offset(offset, index);
-
- block_entry *entry;
- if (GetBlockEntry(baseOffset, &entry) == B_OK) {
- // the block already exists, we just need to fill in our new
address
- if (entry->address[index] == NULL && address != NULL)
- entry->used++;
- else if (entry->address[index] != NULL && address == NULL)
- entry->used--;
-
- entry->address[index] = address;
- return B_OK;
- }
-
- // allocate new block and fill it
-
- entry = (block_entry *)malloc(sizeof(struct block_entry));
- if (entry == NULL)
- return B_NO_MEMORY;
-
- memset(entry->address, 0, sizeof(entry->address));
-
- entry->used = 1;
- entry->offset = baseOffset;
-
- hash_insert(fHashTable, entry);
-
- entry->address[index] = address;
- return B_OK;
-}
-
-
-status_t
-BlockMap::Get(off_t offset, addr_t &address)
-{
- TRACE(("BlockMap::Get(offset = %Ld)\n", offset));
-
- uint32 index;
- off_t baseOffset = to_block_entry_offset(offset, index);
-
- block_entry *entry;
- if (GetBlockEntry(baseOffset, &entry) == B_OK
- && entry->address[index] != NULL) {
- address = entry->address[index];
- return B_OK;
- }
-
- return B_ENTRY_NOT_FOUND;
-}
-
diff --git a/src/system/kernel/cache/BlockMap.h
b/src/system/kernel/cache/BlockMap.h
deleted file mode 100644
index 3967fa8..0000000
--- a/src/system/kernel/cache/BlockMap.h
+++ /dev/null
@@ -1,35 +0,0 @@
-/*
- * Copyright 2004-2005, Axel Dörfler, axeld@xxxxxxxxxxxxxxxx. All rights
reserved.
- * Distributed under the terms of the MIT License.
- */
-#ifndef BLOCK_MAP_H
-#define BLOCK_MAP_H
-
-
-#include <OS.h>
-#include <util/khash.h>
-
-
-class BlockMap {
- public:
- BlockMap(off_t size);
- ~BlockMap();
-
- status_t InitCheck() const;
-
- void SetSize(off_t size);
- off_t Size() const { return fSize; }
-
- status_t Remove(off_t offset, off_t count = 1);
- status_t Set(off_t offset, addr_t address);
- status_t Get(off_t offset, addr_t &address);
-
- private:
- struct block_entry;
- status_t GetBlockEntry(off_t offset, block_entry **_entry);
-
- hash_table *fHashTable;
- off_t fSize;
-};
-
-#endif /* BLOCK_MAP_H */
diff --git a/src/tests/system/kernel/cache/BlockMapTest.cpp
b/src/tests/system/kernel/cache/BlockMapTest.cpp
deleted file mode 100644
index 92aba01..0000000
--- a/src/tests/system/kernel/cache/BlockMapTest.cpp
+++ /dev/null
@@ -1,143 +0,0 @@
-/*
-** Copyright 2004, Axel Dörfler, axeld@xxxxxxxxxxxxxxxx. All rights reserved.
-** Distributed under the terms of the Haiku License.
-*/
-
-
-#include <BlockMap.h>
-
-#include <string.h>
-#include <stdlib.h>
-#include <stdio.h>
-
-
-static const off_t kSize = 262144; // 4096 * 262144 == 1 GB of file size
-static const int32 kLoops = 4096; // 4096 * 4096 == 16 MB in cache
(completely arbitrary which will never be the case)
-
-
-int32
-offset_in_array(off_t *array, int32 maxSize, off_t offset)
-{
- for (int32 i = 0; i < maxSize; i++) {
- if (array[i] == offset)
- return i;
- }
-
- return B_ENTRY_NOT_FOUND;
-}
-
-
-int
-main(int argc, char **argv)
-{
- BlockMap map(kSize);
-
- status_t status = map.InitCheck();
- if (status != B_OK) {
- fprintf(stderr, "map creation failed: %s\n", strerror(status));
- return 1;
- }
-
- printf("Adding %ld offsets from 0 to %Ld...\n", kLoops, kSize);
-
- off_t offsets[kLoops];
- for (int32 i = 0; i < kLoops; i++) {
- off_t offset;
- do {
- offset = rand() * kSize / RAND_MAX;
- } while (offset_in_array(offsets, i, offset) >= B_OK);
-
- offsets[i] = offset;
- map.Set(offsets[i], i + 1);
- }
-
- printf("Testing all offsets in the map...\n");
-
- for (off_t offset = 0; offset < kSize; offset++) {
- // look for offset in array
- int32 index = offset_in_array(offsets, kLoops, offset);
-
- addr_t address;
- if (map.Get(offset, address) == B_OK) {
- if (index >= 0) {
- if (address != (uint32)index + 1)
- fprintf(stderr, " offset %Ld contains
wrong address %lx, should have been %lx\n", offset, address, index + 1);
- } else
- fprintf(stderr, " offset %Ld found in map but
never added\n", offset);
- } else {
- if (index >= 0)
- fprintf(stderr, " offset %Ld not found in map
but should be there\n", offset);
- }
- }
-
- printf("Remove last offset...\n");
-
- // remove last offset
- map.Remove(offsets[kLoops - 1]);
- addr_t address;
- if (map.Get(offsets[kLoops - 1], address) == B_OK)
- fprintf(stderr, " Removing offset %Ld failed (got address
%lx)!\n", offsets[kLoops - 1], address);
-
- // remove offsets in the middle
- off_t start = kSize / 4;
- off_t num = kSize / 2;
- off_t end = start + num;
-
- printf("Remove all offsets from %Ld to %Ld (and add bounds check
offsets)...\n", start, end);
-
- bool startWall[3] = {false};
- for (int32 i = 0; i < 3; i++) {
- if (offset_in_array(offsets, kLoops, start - 1 + i) < B_OK) {
- startWall[i] = true;
- map.Set(start - 1 + i, i + 1);
- }
- }
-
- bool endWall[3] = {false};
- for (int32 i = 0; i < 3; i++) {
- if (offset_in_array(offsets, kLoops, end - 1 + i) < B_OK) {
- endWall[i] = true;
- map.Set(end - 1 + i, i + 1);
- }
- }
-
- map.Remove(start, num);
-
- printf("Testing all offsets in the map...\n");
-
- for (off_t offset = 0; offset < kSize; offset++) {
- // look for offset in array
- int32 index = offset_in_array(offsets, kLoops - 1, offset);
-
- addr_t address;
- if (map.Get(offset, address) == B_OK) {
- if (offset >= start && offset < end) {
- fprintf(stderr, " should not contain removed
offset %Ld:%lx!\n", offset, address);
- } else if (index >= 0) {
- if (address != (uint32)index + 1)
- fprintf(stderr, " offset %Ld contains
wrong address %lx, should have been %lx\n", offset, address, index + 1);
- } else {
- if (offset >= start -1 && offset <= start + 1) {
- // start && start + 1 must not be in
the map anymore
- if (offset >= start && offset <= start
+ 1)
- fprintf(stderr, " start wall
%Ld in map\n", offset);
- } else if (offset >= end - 1 && offset <= end +
1) {
- // end - 1 must not be in the map
anymore
- if (offset == end - 1)
- fprintf(stderr, " end wall %Ld
in map\n", offset);
- } else
- fprintf(stderr, " offset %Ld found in
map but never added\n", offset);
- }
- } else {
- if (index >= 0 && (offset < start || offset >= end))
- fprintf(stderr, " offset %Ld not found in map
but should be there\n", offset);
-
- if (offset == start - 1 && startWall[offset - start -
1])
- fprintf(stderr, " start wall %Ld not in
map\n", offset);
- else if (offset >= end && offset <= end + 1 &&
endWall[offset - end - 1])
- fprintf(stderr, " end wall %Ld not in map\n",
offset);
- }
- }
-
- return 0;
-}
diff --git a/src/tests/system/kernel/cache/Jamfile
b/src/tests/system/kernel/cache/Jamfile
index 90a03b7..cd2cd56 100644
--- a/src/tests/system/kernel/cache/Jamfile
+++ b/src/tests/system/kernel/cache/Jamfile
@@ -11,11 +11,6 @@ StdBinCommands
cache_control.cpp
;
-SimpleTest BlockMapTest :
- BlockMapTest.cpp
- BlockMap.cpp
- : libkernelland_emu.so ;
-
SimpleTest block_cache_test :
block_cache_test.cpp
: libkernelland_emu.so ;
Other related posts:
- » [haiku-commits] haiku: hrev48670 - src/system/kernel/cache src/tools/fs_shell src/system/kernel/util src/tests/system/kernel/cache headers/private/kernel/util - pulkomandy
