[haiku-commits] r34950 - haiku/trunk/src/system/kernel/fs
- From: ingo_weinhold@xxxxxx
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Fri, 8 Jan 2010 18:02:24 +0100 (CET)
Author: bonefish
Date: 2010-01-08 18:02:24 +0100 (Fri, 08 Jan 2010)
New Revision: 34950
Changeset: http://dev.haiku-os.org/changeset/34950/haiku
Added:
haiku/trunk/src/system/kernel/fs/EntryCache.cpp
Modified:
haiku/trunk/src/system/kernel/fs/EntryCache.h
haiku/trunk/src/system/kernel/fs/Jamfile
Log:
Entry cache:
* Moved hash computations out of the critical sections.
* Replaced the LRU entry queue by an array of entry "generations", each
containing a sparse array of entries of that generation. Whenever a
generation is full, we clear the oldest generation and continue with that
one. The main advantage of this algorithm is that entry cache's mutex could
be replaced by an r/w lock, that most of the time only has to be read
locked in Lookup(). This does dramatically decrease contention of that
lock.
The total -j8 Haiku image build speedup is marginal, but the kernel time
drops about 7% (now being smaller than the real time).
Added: haiku/trunk/src/system/kernel/fs/EntryCache.cpp
===================================================================
--- haiku/trunk/src/system/kernel/fs/EntryCache.cpp
(rev 0)
+++ haiku/trunk/src/system/kernel/fs/EntryCache.cpp 2010-01-08 17:02:24 UTC
(rev 34950)
@@ -0,0 +1,237 @@
+/*
+ * Copyright 2008-2010, Ingo Weinhold, ingo_weinhold@xxxxxxx
+ * Distributed under the terms of the MIT License.
+ */
+
+
+#include "EntryCache.h"
+
+#include <new>
+
+
+static const int32 kEntriesPerGeneration = 1024;
+
+static const int32 kEntryNotInArray = -1;
+static const int32 kEntryRemoved = -2;
+
+
+// #pragma mark - EntryCacheGeneration
+
+
+EntryCacheGeneration::EntryCacheGeneration()
+ :
+ next_index(0),
+ entries(NULL)
+{
+}
+
+
+EntryCacheGeneration::~EntryCacheGeneration()
+{
+ delete[] entries;
+}
+
+
+status_t
+EntryCacheGeneration::Init()
+{
+ entries = new(std::nothrow) EntryCacheEntry*[kEntriesPerGeneration];
+ if (entries == NULL)
+ return B_NO_MEMORY;
+
+ memset(entries, 0, sizeof(EntryCacheEntry*) * kEntriesPerGeneration);
+
+ return B_OK;
+}
+
+
+// #pragma mark - EntryCache
+
+
+EntryCache::EntryCache()
+ :
+ fCurrentGeneration(0)
+{
+ rw_lock_init(&fLock, "entry cache");
+
+ new(&fEntries) EntryTable;
+}
+
+
+EntryCache::~EntryCache()
+{
+ // delete entries
+ EntryCacheEntry* entry = fEntries.Clear(true);
+ while (entry != NULL) {
+ EntryCacheEntry* next = entry->hash_link;
+ free(entry);
+ entry = next;
+ }
+
+ rw_lock_destroy(&fLock);
+}
+
+
+status_t
+EntryCache::Init()
+{
+ status_t error = fEntries.Init();
+ if (error != B_OK)
+ return error;
+
+ for (int32 i = 0; i < kGenerationCount; i++) {
+ error = fGenerations[i].Init();
+ if (error != B_OK)
+ return error;
+ }
+
+ return B_OK;
+}
+
+
+status_t
+EntryCache::Add(ino_t dirID, const char* name, ino_t nodeID)
+{
+ EntryCacheKey key(dirID, name);
+
+ WriteLocker _(fLock);
+
+ EntryCacheEntry* entry = fEntries.Lookup(key);
+ if (entry != NULL) {
+ entry->node_id = nodeID;
+ if (entry->generation != fCurrentGeneration) {
+ if (entry->index >= 0) {
+
fGenerations[entry->generation].entries[entry->index] = NULL;
+ _AddEntryToCurrentGeneration(entry);
+ }
+ }
+ return B_OK;
+ }
+
+ entry = (EntryCacheEntry*)malloc(sizeof(EntryCacheEntry) +
strlen(name));
+ if (entry == NULL)
+ return B_NO_MEMORY;
+
+ entry->node_id = nodeID;
+ entry->dir_id = dirID;
+ entry->generation = fCurrentGeneration;
+ entry->index = kEntryNotInArray;
+ strcpy(entry->name, name);
+
+ fEntries.Insert(entry);
+
+ _AddEntryToCurrentGeneration(entry);
+
+ return B_OK;
+}
+
+
+status_t
+EntryCache::Remove(ino_t dirID, const char* name)
+{
+ EntryCacheKey key(dirID, name);
+
+ WriteLocker writeLocker(fLock);
+
+ EntryCacheEntry* entry = fEntries.Lookup(key);
+ if (entry == NULL)
+ return B_ENTRY_NOT_FOUND;
+
+ fEntries.Remove(entry);
+
+ if (entry->index >= 0) {
+ // remove the entry from its generation and delete it
+ fGenerations[entry->generation].entries[entry->index] = NULL;
+ free(entry);
+ } else {
+ // We can't free it, since another thread is about to try to
move it
+ // to another generation. We mark it removed and the other
thread will
+ // take care of deleting it.
+ entry->index = kEntryRemoved;
+ }
+
+ return B_OK;
+}
+
+
+bool
+EntryCache::Lookup(ino_t dirID, const char* name, ino_t& _nodeID)
+{
+ EntryCacheKey key(dirID, name);
+
+ ReadLocker readLocker(fLock);
+
+ EntryCacheEntry* entry = fEntries.Lookup(key);
+ if (entry == NULL)
+ return false;
+
+ int32 oldGeneration = atomic_set(&entry->generation,
fCurrentGeneration);
+ if (oldGeneration == fCurrentGeneration || entry->index < 0) {
+ // The entry is already in the current generation or is being
moved to
+ // it by another thread.
+ _nodeID = entry->node_id;
+ return true;
+ }
+
+ // remove from old generation array
+ fGenerations[oldGeneration].entries[entry->index] = NULL;
+ entry->index = kEntryNotInArray;
+
+ // add to the current generation
+ int32 index = atomic_add(&fGenerations[oldGeneration].next_index, 1);
+ if (index < kEntriesPerGeneration) {
+ fGenerations[fCurrentGeneration].entries[index] = entry;
+ entry->index = index;
+ _nodeID = entry->node_id;
+ return true;
+ }
+
+ // The current generation is full, so we probably need to clear the
oldest
+ // one to make room. We need the write lock for that.
+ readLocker.Unlock();
+ WriteLocker writeLocker(fLock);
+
+ if (entry->index == kEntryRemoved) {
+ // the entry has been removed in the meantime
+ free(entry);
+ return false;
+ }
+
+ _AddEntryToCurrentGeneration(entry);
+
+ _nodeID = entry->node_id;
+ return true;
+}
+
+
+void
+EntryCache::_AddEntryToCurrentGeneration(EntryCacheEntry* entry)
+{
+ // the generation might not be full yet
+ int32 index = fGenerations[fCurrentGeneration].next_index++;
+ if (index < kEntriesPerGeneration) {
+ fGenerations[fCurrentGeneration].entries[index] = entry;
+ entry->generation = fCurrentGeneration;
+ entry->index = index;
+ return;
+ }
+
+ // we have to clear the oldest generation
+ int32 newGeneration = (fCurrentGeneration + 1) % kGenerationCount;
+ for (int32 i = 0; i < kEntriesPerGeneration; i++) {
+ EntryCacheEntry* otherEntry =
fGenerations[newGeneration].entries[i];
+ if (otherEntry == NULL)
+ continue;
+
+ fGenerations[newGeneration].entries[i] = NULL;
+ fEntries.Remove(otherEntry);
+ free(otherEntry);
+ }
+
+ // set the new generation and add the entry
+ fCurrentGeneration = newGeneration;
+ fGenerations[newGeneration].next_index = 1;
+ fGenerations[newGeneration].entries[0] = entry;
+ entry->generation = newGeneration;
+ entry->index = 0;
+}
Modified: haiku/trunk/src/system/kernel/fs/EntryCache.h
===================================================================
--- haiku/trunk/src/system/kernel/fs/EntryCache.h 2010-01-08 16:41:57 UTC
(rev 34949)
+++ haiku/trunk/src/system/kernel/fs/EntryCache.h 2010-01-08 17:02:24 UTC
(rev 34950)
@@ -1,5 +1,5 @@
/*
- * Copyright 2008-2009, Ingo Weinhold, ingo_weinhold@xxxxxxx
+ * Copyright 2008-2010, Ingo Weinhold, ingo_weinhold@xxxxxxx
* Distributed under the terms of the MIT License.
*/
#ifndef ENTRY_CACHE_H
@@ -9,43 +9,55 @@
#include <stdlib.h>
#include <util/AutoLock.h>
-#include <util/DoublyLinkedList.h>
#include <util/khash.h>
#include <util/OpenHashTable.h>
-const static uint32 kMaxEntryCacheEntryCount = 8192;
- // Maximum number of entries per entry cache. It's a hard limit ATM.
-
struct EntryCacheKey {
EntryCacheKey(ino_t dirID, const char* name)
:
dir_id(dirID),
name(name)
{
+ hash = (uint32)dir_id ^ (uint32)(dir_id >> 32) ^
hash_hash_string(name);
+ // We cache the hash value, so we can easily compute it
before
+ // holding any locks.
}
ino_t dir_id;
const char* name;
+ size_t hash;
};
-struct EntryCacheEntry : DoublyLinkedListLinkImpl<EntryCacheEntry> {
- EntryCacheEntry* hash_link;
- ino_t node_id;
- ino_t dir_id;
- char name[1];
+struct EntryCacheEntry {
+ EntryCacheEntry* hash_link;
+ ino_t node_id;
+ ino_t dir_id;
+ vint32 generation;
+ vint32 index;
+ char name[1];
};
+struct EntryCacheGeneration {
+ vint32 next_index;
+ EntryCacheEntry** entries;
+
+
EntryCacheGeneration();
+
~EntryCacheGeneration();
+
+ status_t Init();
+};
+
+
struct EntryCacheHashDefinition {
typedef EntryCacheKey KeyType;
typedef EntryCacheEntry ValueType;
uint32 HashKey(const EntryCacheKey& key) const
{
- return (uint32)key.dir_id ^ (uint32)(key.dir_id >> 32)
- ^ hash_hash_string(key.name);
+ return key.hash;
}
size_t Hash(const EntryCacheEntry* value) const
@@ -69,102 +81,34 @@
class EntryCache {
public:
- EntryCache()
- {
- mutex_init(&fLock, "entry cache");
+ EntryCache();
+ ~EntryCache();
- new(&fEntries) EntryTable;
- new(&fUsedEntries) EntryList;
- fEntryCount = 0;
- }
+ status_t Init();
- ~EntryCache()
- {
- while (EntryCacheEntry* entry = fUsedEntries.Head())
- _Remove(entry);
+ status_t Add(ino_t dirID, const
char* name,
+ ino_t
nodeID);
- mutex_destroy(&fLock);
- }
+ status_t Remove(ino_t dirID,
const char* name);
- status_t Init()
- {
- return fEntries.Init();
- }
+ bool Lookup(ino_t dirID,
const char* name,
+ ino_t&
nodeID);
- status_t Add(ino_t dirID, const char* name, ino_t nodeID)
- {
- MutexLocker _(fLock);
+private:
+ static const int32 kGenerationCount = 8;
- EntryCacheEntry* entry = fEntries.Lookup(EntryCacheKey(dirID,
name));
- if (entry != NULL) {
- entry->node_id = nodeID;
- return B_OK;
- }
+ typedef BOpenHashTable<EntryCacheHashDefinition>
EntryTable;
+ typedef DoublyLinkedList<EntryCacheEntry> EntryList;
- if (fEntryCount >= kMaxEntryCacheEntryCount)
- _Remove(fUsedEntries.Head());
-
- entry = (EntryCacheEntry*)malloc(sizeof(EntryCacheEntry)
- + strlen(name));
- if (entry == NULL)
- return B_NO_MEMORY;
-
- entry->node_id = nodeID;
- entry->dir_id = dirID;
- strcpy(entry->name, name);
-
- fEntries.Insert(entry);
- fUsedEntries.Add(entry);
- fEntryCount++;
-
- return B_OK;
- }
-
- status_t Remove(ino_t dirID, const char* name)
- {
- MutexLocker _(fLock);
-
- EntryCacheEntry* entry = fEntries.Lookup(EntryCacheKey(dirID,
name));
- if (entry == NULL)
- return B_ENTRY_NOT_FOUND;
-
- _Remove(entry);
-
- return B_OK;
- }
-
- bool Lookup(ino_t dirID, const char* name, ino_t& nodeID)
- {
- MutexLocker _(fLock);
-
- EntryCacheEntry* entry = fEntries.Lookup(EntryCacheKey(dirID,
name));
- if (entry == NULL)
- return false;
-
- // requeue at the end
- fUsedEntries.Remove(entry);
- fUsedEntries.Add(entry);
-
- nodeID = entry->node_id;
- return true;
- }
-
- void _Remove(EntryCacheEntry* entry)
- {
- fEntries.Remove(entry);
- fUsedEntries.Remove(entry);
- free(entry);
- fEntryCount--;
- }
-
private:
- typedef BOpenHashTable<EntryCacheHashDefinition> EntryTable;
- typedef DoublyLinkedList<EntryCacheEntry> EntryList;
+ void
_AddEntryToCurrentGeneration(
+
EntryCacheEntry* entry);
- mutex fLock;
- EntryTable fEntries;
- EntryList fUsedEntries; // LRU queue (LRU entry at the head)
- uint32 fEntryCount;
+private:
+ rw_lock fLock;
+ EntryTable fEntries;
+ EntryCacheGeneration fGenerations[kGenerationCount];
+ int32 fCurrentGeneration;
};
Modified: haiku/trunk/src/system/kernel/fs/Jamfile
===================================================================
--- haiku/trunk/src/system/kernel/fs/Jamfile 2010-01-08 16:41:57 UTC (rev
34949)
+++ haiku/trunk/src/system/kernel/fs/Jamfile 2010-01-08 17:02:24 UTC (rev
34950)
@@ -8,6 +8,7 @@
UseHeaders [ FDirName $(SUBDIR) $(DOTDOT) device_manager ] ;
KernelMergeObject kernel_fs.o :
+ EntryCache.cpp
fd.cpp
fifo.cpp
KPath.cpp
Other related posts:
- » [haiku-commits] r34950 - haiku/trunk/src/system/kernel/fs - ingo_weinhold
