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) 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 if (entry->generation != fCurrentGeneration) { 103 if (entry->index >= 0) { 104 fGenerations[entry->generation].entries[entry->index] = NULL; 105 _AddEntryToCurrentGeneration(entry); 106 } 107 } 108 return B_OK; 109 } 110 111 entry = (EntryCacheEntry*)malloc(sizeof(EntryCacheEntry) + strlen(name)); 112 if (entry == NULL) 113 return B_NO_MEMORY; 114 115 entry->node_id = nodeID; 116 entry->dir_id = dirID; 117 entry->generation = fCurrentGeneration; 118 entry->index = kEntryNotInArray; 119 strcpy(entry->name, name); 120 121 fEntries.Insert(entry); 122 123 _AddEntryToCurrentGeneration(entry); 124 125 return B_OK; 126 } 127 128 129 status_t 130 EntryCache::Remove(ino_t dirID, const char* name) 131 { 132 EntryCacheKey key(dirID, name); 133 134 WriteLocker writeLocker(fLock); 135 136 EntryCacheEntry* entry = fEntries.Lookup(key); 137 if (entry == NULL) 138 return B_ENTRY_NOT_FOUND; 139 140 fEntries.Remove(entry); 141 142 if (entry->index >= 0) { 143 // remove the entry from its generation and delete it 144 fGenerations[entry->generation].entries[entry->index] = NULL; 145 free(entry); 146 } else { 147 // We can't free it, since another thread is about to try to move it 148 // to another generation. We mark it removed and the other thread will 149 // take care of deleting it. 150 entry->index = kEntryRemoved; 151 } 152 153 return B_OK; 154 } 155 156 157 bool 158 EntryCache::Lookup(ino_t dirID, const char* name, ino_t& _nodeID) 159 { 160 EntryCacheKey key(dirID, name); 161 162 ReadLocker readLocker(fLock); 163 164 EntryCacheEntry* entry = fEntries.Lookup(key); 165 if (entry == NULL) 166 return false; 167 168 int32 oldGeneration = atomic_get_and_set(&entry->generation, 169 fCurrentGeneration); 170 if (oldGeneration == fCurrentGeneration || entry->index < 0) { 171 // The entry is already in the current generation or is being moved to 172 // it by another thread. 173 _nodeID = entry->node_id; 174 return true; 175 } 176 177 // remove from old generation array 178 fGenerations[oldGeneration].entries[entry->index] = NULL; 179 entry->index = kEntryNotInArray; 180 181 // add to the current generation 182 int32 index = atomic_add(&fGenerations[oldGeneration].next_index, 1); 183 if (index < kEntriesPerGeneration) { 184 fGenerations[fCurrentGeneration].entries[index] = entry; 185 entry->index = index; 186 _nodeID = entry->node_id; 187 return true; 188 } 189 190 // The current generation is full, so we probably need to clear the oldest 191 // one to make room. We need the write lock for that. 192 readLocker.Unlock(); 193 WriteLocker writeLocker(fLock); 194 195 if (entry->index == kEntryRemoved) { 196 // the entry has been removed in the meantime 197 free(entry); 198 return false; 199 } 200 201 _AddEntryToCurrentGeneration(entry); 202 203 _nodeID = entry->node_id; 204 return true; 205 } 206 207 208 const char* 209 EntryCache::DebugReverseLookup(ino_t nodeID, ino_t& _dirID) 210 { 211 for (EntryTable::Iterator it = fEntries.GetIterator(); 212 EntryCacheEntry* entry = it.Next();) { 213 if (nodeID == entry->node_id && strcmp(entry->name, ".") != 0 214 && strcmp(entry->name, "..") != 0) { 215 _dirID = entry->dir_id; 216 return entry->name; 217 } 218 } 219 220 return NULL; 221 } 222 223 224 void 225 EntryCache::_AddEntryToCurrentGeneration(EntryCacheEntry* entry) 226 { 227 // the generation might not be full yet 228 int32 index = fGenerations[fCurrentGeneration].next_index++; 229 if (index < kEntriesPerGeneration) { 230 fGenerations[fCurrentGeneration].entries[index] = entry; 231 entry->generation = fCurrentGeneration; 232 entry->index = index; 233 return; 234 } 235 236 // we have to clear the oldest generation 237 int32 newGeneration = (fCurrentGeneration + 1) % kGenerationCount; 238 for (int32 i = 0; i < kEntriesPerGeneration; i++) { 239 EntryCacheEntry* otherEntry = fGenerations[newGeneration].entries[i]; 240 if (otherEntry == NULL) 241 continue; 242 243 fGenerations[newGeneration].entries[i] = NULL; 244 fEntries.Remove(otherEntry); 245 free(otherEntry); 246 } 247 248 // set the new generation and add the entry 249 fCurrentGeneration = newGeneration; 250 fGenerations[newGeneration].next_index = 1; 251 fGenerations[newGeneration].entries[0] = entry; 252 entry->generation = newGeneration; 253 entry->index = 0; 254 } 255