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