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