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 13 static const int32 kEntryNotInArray = -1; 14 static const int32 kEntryRemoved = -2; 15 16 17 // #pragma mark - EntryCacheGeneration 18 19 20 EntryCacheGeneration::EntryCacheGeneration() 21 : 22 next_index(0), 23 entries(NULL) 24 { 25 } 26 27 28 EntryCacheGeneration::~EntryCacheGeneration() 29 { 30 delete[] entries; 31 } 32 33 34 status_t 35 EntryCacheGeneration::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 50 EntryCache::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 62 EntryCache::~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 77 status_t 78 EntryCache::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 105 status_t 106 EntryCache::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 147 status_t 148 EntryCache::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 175 bool 176 EntryCache::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 230 const char* 231 EntryCache::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 246 void 247 EntryCache::_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