src/system/kernel/fs/EntryCache.cpp

   1 /*
   2  * Copyright 2008-2010, Ingo Weinhold, ingo_weinhold@gmx.de.
   3  * Distributed under the terms of the MIT License.
   4  */
   5
   6
   7 #include "EntryCache.h"
   8
   9 #include <new>
  10
  11
  12 static const int32 kEntriesPerGeneration = 1024;
  13
  14 static const int32 kEntryNotInArray = -1;
  15 static const int32 kEntryRemoved = -2;
  16
  17
  18 // #pragma mark - EntryCacheGeneration
  19
  20
  21 EntryCacheGeneration::EntryCacheGeneration()
  22         :
  23         next_index(0),
  24         entries(NULL)
  25 {
  26 }
  27
  28
  29 EntryCacheGeneration::~EntryCacheGeneration()
  30 {
  31         delete[] entries;
  32 }
  33
  34
  35 status_t
  36 EntryCacheGeneration::Init()
  37 {
  38         entries = new(std::nothrow) EntryCacheEntry*[kEntriesPerGeneration];
  39         if (entries == NULL)
  40                 return B_NO_MEMORY;
  41
  42         memset(entries, 0, sizeof(EntryCacheEntry*) * kEntriesPerGeneration);
  43
  44         return B_OK;
  45 }
  46
  47
  48 // #pragma mark - EntryCache
  49
  50
  51 EntryCache::EntryCache()
  52         :
  53         fCurrentGeneration(0)
  54 {
  55         rw_lock_init(&fLock, "entry cache");
  56
  57         new(&fEntries) EntryTable;
  58 }
  59
  60
  61 EntryCache::~EntryCache()
  62 {
  63         // delete entries
  64         EntryCacheEntry* entry = fEntries.Clear(true);
  65         while (entry != NULL) {
  66                 EntryCacheEntry* next = entry->hash_link;
  67                 free(entry);
  68                 entry = next;
  69         }
  70
  71         rw_lock_destroy(&fLock);
  72 }
  73
  74
  75 status_t
  76 EntryCache::Init()
  77 {
  78         status_t error = fEntries.Init();
  79         if (error != B_OK)
  80                 return error;
  81
  82         for (int32 i = 0; i < kGenerationCount; i++) {
  83                 error = fGenerations[i].Init();
  84                 if (error != B_OK)
  85                         return error;
  86         }
  87
  88         return B_OK;
  89 }
  90
  91
  92 status_t
  93 EntryCache::Add(ino_t dirID, const char* name, ino_t nodeID, bool missing)
  94 {
  95         EntryCacheKey key(dirID, name);
  96
  97         WriteLocker _(fLock);
  98
  99         EntryCacheEntry* entry = fEntries.Lookup(key);
 100         if (entry != NULL) {
 101                 entry->node_id = nodeID;
 102                 entry->missing = missing;
 103                 if (entry->generation != fCurrentGeneration) {
 104                         if (entry->index >= 0) {
 105                                 fGenerations[entry->generation].entries[entry->index] = NULL;
 106                                 _AddEntryToCurrentGeneration(entry);
 107                         }
 108                 }
 109                 return B_OK;
 110         }
 111
 112         entry = (EntryCacheEntry*)malloc(sizeof(EntryCacheEntry) + strlen(name));
 113         if (entry == NULL)
 114                 return B_NO_MEMORY;
 115
 116         entry->node_id = nodeID;
 117         entry->dir_id = dirID;
 118         entry->missing = missing;
 119         entry->generation = fCurrentGeneration;
 120         entry->index = kEntryNotInArray;
 121         strcpy(entry->name, name);
 122
 123         fEntries.Insert(entry);
 124
 125         _AddEntryToCurrentGeneration(entry);
 126
 127         return B_OK;
 128 }
 129
 130
 131 status_t
 132 EntryCache::Remove(ino_t dirID, const char* name)
 133 {
 134         EntryCacheKey key(dirID, name);
 135
 136         WriteLocker writeLocker(fLock);
 137
 138         EntryCacheEntry* entry = fEntries.Lookup(key);
 139         if (entry == NULL)
 140                 return B_ENTRY_NOT_FOUND;
 141
 142         fEntries.Remove(entry);
 143
 144         if (entry->index >= 0) {
 145                 // remove the entry from its generation and delete it
 146                 fGenerations[entry->generation].entries[entry->index] = NULL;
 147                 free(entry);
 148         } else {
 149                 // We can't free it, since another thread is about to try to move it
 150                 // to another generation. We mark it removed and the other thread will
 151                 // take care of deleting it.
 152                 entry->index = kEntryRemoved;
 153         }
 154
 155         return B_OK;
 156 }
 157
 158
 159 bool
 160 EntryCache::Lookup(ino_t dirID, const char* name, ino_t& _nodeID,
 161         bool& _missing)
 162 {
 163         EntryCacheKey key(dirID, name);
 164
 165         ReadLocker readLocker(fLock);
 166
 167         EntryCacheEntry* entry = fEntries.Lookup(key);
 168         if (entry == NULL)
 169                 return false;
 170
 171         int32 oldGeneration = atomic_get_and_set(&entry->generation,
 172                         fCurrentGeneration);
 173         if (oldGeneration == fCurrentGeneration || entry->index < 0) {
 174                 // The entry is already in the current generation or is being moved to
 175                 // it by another thread.
 176                 _nodeID = entry->node_id;
 177                 _missing = entry->missing;
 178                 return true;
 179         }
 180
 181         // remove from old generation array
 182         fGenerations[oldGeneration].entries[entry->index] = NULL;
 183         entry->index = kEntryNotInArray;
 184
 185         // add to the current generation
 186         int32 index = atomic_add(&fGenerations[oldGeneration].next_index, 1);
 187         if (index < kEntriesPerGeneration) {
 188                 fGenerations[fCurrentGeneration].entries[index] = entry;
 189                 entry->index = index;
 190                 _nodeID = entry->node_id;
 191                 _missing = entry->missing;
 192                 return true;
 193         }
 194
 195         // The current generation is full, so we probably need to clear the oldest
 196         // one to make room. We need the write lock for that.
 197         readLocker.Unlock();
 198         WriteLocker writeLocker(fLock);
 199
 200         if (entry->index == kEntryRemoved) {
 201                 // the entry has been removed in the meantime
 202                 free(entry);
 203                 return false;
 204         }
 205
 206         _AddEntryToCurrentGeneration(entry);
 207
 208         _nodeID = entry->node_id;
 209         _missing = entry->missing;
 210         return true;
 211 }
 212
 213
 214 const char*
 215 EntryCache::DebugReverseLookup(ino_t nodeID, ino_t& _dirID)
 216 {
 217         for (EntryTable::Iterator it = fEntries.GetIterator();
 218                         EntryCacheEntry* entry = it.Next();) {
 219                 if (nodeID == entry->node_id && strcmp(entry->name, ".") != 0
 220                                 && strcmp(entry->name, "..") != 0) {
 221                         _dirID = entry->dir_id;
 222                         return entry->name;
 223                 }
 224         }
 225
 226         return NULL;
 227 }
 228
 229
 230 void
 231 EntryCache::_AddEntryToCurrentGeneration(EntryCacheEntry* entry)
 232 {
 233         // the generation might not be full yet
 234         int32 index = fGenerations[fCurrentGeneration].next_index++;
 235         if (index < kEntriesPerGeneration) {
 236                 fGenerations[fCurrentGeneration].entries[index] = entry;
 237                 entry->generation = fCurrentGeneration;
 238                 entry->index = index;
 239                 return;
 240         }
 241
 242         // we have to clear the oldest generation
 243         int32 newGeneration = (fCurrentGeneration + 1) % kGenerationCount;
 244         for (int32 i = 0; i < kEntriesPerGeneration; i++) {
 245                 EntryCacheEntry* otherEntry = fGenerations[newGeneration].entries[i];
 246                 if (otherEntry == NULL)
 247                         continue;
 248
 249                 fGenerations[newGeneration].entries[i] = NULL;
 250                 fEntries.Remove(otherEntry);
 251                 free(otherEntry);
 252         }
 253
 254         // set the new generation and add the entry
 255         fCurrentGeneration = newGeneration;
 256         fGenerations[newGeneration].next_index = 1;
 257         fGenerations[newGeneration].entries[0] = entry;
 258         entry->generation = newGeneration;
 259         entry->index = 0;
 260 }