1/*
2	Copyright 1999-2001, Be Incorporated.   All Rights Reserved.
3	This file may be used under the terms of the Be Sample Code License.
4*/
5/*
6The FAT file system has no good way of assigning unique persistent values to
7nodes. The only obvious choice, storing the starting cluster number of the
8file, is unusable because 0 byte files exist as directory entries only.
9Further, even if it were usable, it would potentially require a full directory
10tree traversal to locate an arbitrary node. We must resort to some ickiness
11in order to make persistent vnode id's (at least across a given mount) work.
12
13There are three ways to encode a vnode id:
14
151. Combine the starting cluster of the entry with the starting cluster of the
16   directory it appears in. This is used for files with data.
172. Combine the starting cluster of the directory the entry appears in with the
18   index of the entry in the directory. This is used for 0-byte files.
193. A unique number that doesn't match any possible values from encodings 1 or
20   2.
21
22With the first encoding, the vnode id is invalidated (i.e. no longer describes
23the file's location) when the file moves to a different directory or when
24its starting cluster changes (this can occur if the file is truncated and data
25is subsequently written to it).
26
27With the second encoding, the vnode id is invalidated when the file position
28is moved within a directory (as a result of a renaming), when it's moved to a
29different directory, or when data is written to it.
30
31The third encoding doesn't describe the file's location on disk, and so it is
32invalid from the start.
33
34Since we can't change vnode id's once they are assigned, we have to create a
35mapping table to translate vnode id's to locations. This file serves this
36purpose.
37*/
38
39#define DPRINTF(a,b) if (debug_vcache > (a)) dprintf b
40
41#define LOCK_CACHE_R \
42	acquire_sem(vol->vcache.vc_sem)
43
44#define LOCK_CACHE_W \
45	acquire_sem_etc(vol->vcache.vc_sem, READERS, 0, 0)
46
47#define UNLOCK_CACHE_R \
48	release_sem(vol->vcache.vc_sem)
49
50#define UNLOCK_CACHE_W \
51	release_sem_etc(vol->vcache.vc_sem, READERS, 0)
52
53#include <fsproto.h>
54#include <KernelExport.h>
55
56#include <stdio.h>
57#include <string.h>
58#include <stdlib.h>
59
60#include "dosfs.h"
61#include "vcache.h"
62
63#include "util.h"
64
65struct vcache_entry {
66	vnode_id	vnid;		/* originally reported vnid */
67	vnode_id	loc;		/* where the file is now */
68	struct vcache_entry *next_vnid; /* next entry in vnid hash table */
69	struct vcache_entry *next_loc;  /* next entry in location hash table */
70};
71
72void dump_vcache(nspace *vol)
73{
74	uint32 i;
75	struct vcache_entry *c;
76	dprintf("vnid cache size %lx, cur vnid = %Lx\n"
77			"vnid             loc\n",
78			vol->vcache.cache_size, vol->vcache.cur_vnid);
79	for (i=0;i<vol->vcache.cache_size;i++)
80		for (c = vol->vcache.by_vnid[i];c;c=c->next_vnid)
81			dprintf("%16Lx %16Lx\n", c->vnid, c->loc);
82}
83
84#define hash(v) ((v) & (vol->vcache.cache_size-1))
85
86status_t init_vcache(nspace *vol)
87{
88	char name[16];
89	DPRINTF(0, ("init_vcache called\n"));
90
91	vol->vcache.cur_vnid = ARTIFICIAL_VNID_BITS;
92#if DEBUG
93	vol->vcache.cache_size = 1;
94#else
95	vol->vcache.cache_size = 512; /* must be power of 2 */
96#endif
97	vol->vcache.by_vnid = calloc(sizeof(struct vache_entry *), vol->vcache.cache_size);
98	if (vol->vcache.by_vnid == NULL) {
99		dprintf("init_vcache: out of core\n");
100		return ENOMEM;
101	}
102	vol->vcache.by_loc = calloc(sizeof(struct vache_entry *), vol->vcache.cache_size);
103	if (vol->vcache.by_loc == NULL) {
104		dprintf("init_vcache: out of core\n");
105		free(vol->vcache.by_vnid);
106		vol->vcache.by_vnid = NULL;
107		return ENOMEM;
108	}
109
110	sprintf(name, "fat cache %lx", vol->id);
111	if ((vol->vcache.vc_sem = create_sem(READERS, name)) < 0) {
112		free(vol->vcache.by_vnid); vol->vcache.by_vnid = NULL;
113		free(vol->vcache.by_loc); vol->vcache.by_loc = NULL;
114		return vol->vcache.vc_sem;
115	}
116
117	DPRINTF(0, ("init_vcache: initialized vnid cache with %lx entries\n", vol->vcache.cache_size));
118
119	return 0;
120}
121
122status_t uninit_vcache(nspace *vol)
123{
124	uint32 i, count = 0;
125	struct vcache_entry *c, *n;
126	DPRINTF(0, ("uninit_vcache called\n"));
127
128	LOCK_CACHE_W;
129
130	/* free entries */
131	for (i=0;i<vol->vcache.cache_size;i++) {
132		c = vol->vcache.by_vnid[i];
133		while (c) {
134			count++;
135			n = c->next_vnid;
136			free(c);
137			c = n;
138		}
139	}
140
141	DPRINTF(0, ("%lx vcache entries removed\n", count));
142
143	free(vol->vcache.by_vnid); vol->vcache.by_vnid = NULL;
144	free(vol->vcache.by_loc); vol->vcache.by_loc = NULL;
145
146	delete_sem(vol->vcache.vc_sem);
147
148	return 0;
149}
150
151vnode_id generate_unique_vnid(nspace *vol)
152{
153	DPRINTF(0, ("generate_unique_vnid\n"));
154	/* only one thread per volume will be in here at any given time anyway
155	 * due to volume locking */
156	return vol->vcache.cur_vnid++;
157}
158
159static status_t _add_to_vcache_(nspace *vol, vnode_id vnid, vnode_id loc)
160{
161	int hash1 = hash(vnid), hash2 = hash(loc);
162	struct vcache_entry *e, *c, *p;
163
164	DPRINTF(0, ("add_to_vcache %Lx/%Lx\n", vnid, loc));
165
166	ASSERT(vnid != loc);
167
168	e = malloc(sizeof(struct vcache_entry));
169	if (e == NULL)
170		return ENOMEM;
171
172	e->vnid = vnid; e->loc = loc; e->next_vnid = NULL; e->next_loc = NULL;
173
174	c = p = vol->vcache.by_vnid[hash1];
175	while (c) {
176		if (vnid < c->vnid)
177			break;
178		ASSERT(vnid != c->vnid); ASSERT(loc != c->loc);
179		p = c;
180		c = c->next_vnid;
181	}
182	ASSERT(!c || (vnid != c->vnid));
183
184	e->next_vnid = c;
185	if (p == c)
186		vol->vcache.by_vnid[hash1] = e;
187	else
188		p->next_vnid = e;
189
190	c = p = vol->vcache.by_loc[hash2];
191	while (c) {
192		if (loc < c->loc)
193			break;
194		ASSERT(vnid != c->vnid); ASSERT(loc != c->loc);
195		p = c;
196		c = c->next_loc;
197	}
198	ASSERT(!c || (loc != c->loc));
199
200	e->next_loc = c;
201	if (p == c)
202		vol->vcache.by_loc[hash2] = e;
203	else
204		p->next_loc = e;
205
206	return B_OK;
207}
208
209static status_t _remove_from_vcache_(nspace *vol, vnode_id vnid)
210{
211	int hash1 = hash(vnid), hash2;
212	struct vcache_entry *c, *p, *e;
213
214	DPRINTF(0, ("remove_from_vcache %Lx\n", vnid));
215
216	c = p = vol->vcache.by_vnid[hash1];
217	while (c) {
218		if (vnid == c->vnid)
219			break;
220		ASSERT(c->vnid < vnid);
221		p = c;
222		c = c->next_vnid;
223	}
224	ASSERT(c);
225	if (!c) return ENOENT;
226
227	if (p == c)
228		vol->vcache.by_vnid[hash1] = c->next_vnid;
229	else
230		p->next_vnid = c->next_vnid;
231
232	e = c;
233
234	hash2 = hash(c->loc);
235	c = p = vol->vcache.by_loc[hash2];
236
237	while (c) {
238		if (vnid == c->vnid)
239			break;
240		ASSERT(c->loc < e->loc);
241		p = c;
242		c = c->next_loc;
243	}
244	ASSERT(c);
245	if (!c) return ENOENT;
246	if (p == c)
247		vol->vcache.by_loc[hash2] = c->next_loc;
248	else
249		p->next_loc = c->next_loc;
250
251	free(c);
252
253	return 0;
254}
255
256static struct vcache_entry *_find_vnid_in_vcache_(nspace *vol, vnode_id vnid)
257{
258	int hash1 = hash(vnid);
259	struct vcache_entry *c;
260	c = vol->vcache.by_vnid[hash1];
261	while (c) {
262		if (c->vnid == vnid)
263			break;
264		if (c->vnid > vnid)
265			return NULL;
266		c = c->next_vnid;
267	}
268
269	return c;
270}
271
272static struct vcache_entry *_find_loc_in_vcache_(nspace *vol, vnode_id loc)
273{
274	int hash2 = hash(loc);
275	struct vcache_entry *c;
276	c = vol->vcache.by_loc[hash2];
277	while (c) {
278		if (c->loc == loc)
279			break;
280		if (c->loc > loc)
281			return NULL;
282		c = c->next_loc;
283	}
284
285	return c;
286}
287
288status_t add_to_vcache(nspace *vol, vnode_id vnid, vnode_id loc)
289{
290	status_t result;
291
292	LOCK_CACHE_W;
293	result = _add_to_vcache_(vol,vnid,loc);
294	UNLOCK_CACHE_W;
295
296	if (result < 0) DPRINTF(0, ("add_to_vcache failed (%s)\n", strerror(result)));
297	return result;
298}
299
300/* XXX: do this in a smarter fashion */
301static status_t _update_loc_in_vcache_(nspace *vol, vnode_id vnid, vnode_id loc)
302{
303	status_t result;
304
305	result = _remove_from_vcache_(vol, vnid);
306	if (result == 0)
307		result = _add_to_vcache_(vol, vnid, loc);
308
309	return result;
310}
311
312status_t remove_from_vcache(nspace *vol, vnode_id vnid)
313{
314	status_t result;
315
316	LOCK_CACHE_W;
317	result = _remove_from_vcache_(vol, vnid);
318	UNLOCK_CACHE_W;
319
320	if (result < 0) DPRINTF(0, ("remove_from_vcache failed (%s)\n", strerror(result)));
321	return result;
322}
323
324status_t vcache_vnid_to_loc(nspace *vol, vnode_id vnid, vnode_id *loc)
325{
326	struct vcache_entry *e;
327
328	DPRINTF(1, ("vcache_vnid_to_loc %Lx %lx\n", vnid, (uint32)loc));
329
330	LOCK_CACHE_R;
331	e = _find_vnid_in_vcache_(vol, vnid);
332	if (loc && e)
333			*loc = e->loc;
334	UNLOCK_CACHE_R;
335
336	return (e) ? B_OK : ENOENT;
337}
338
339status_t vcache_loc_to_vnid(nspace *vol, vnode_id loc, vnode_id *vnid)
340{
341	struct vcache_entry *e;
342
343	DPRINTF(1, ("vcache_loc_to_vnid %Lx %lx\n", loc, (uint32)vnid));
344
345	LOCK_CACHE_R;
346	e = _find_loc_in_vcache_(vol, loc);
347	if (vnid && e)
348			*vnid = e->vnid;
349	UNLOCK_CACHE_R;
350
351	return (e) ? B_OK : ENOENT;
352}
353
354status_t vcache_set_entry(nspace *vol, vnode_id vnid, vnode_id loc)
355{
356	struct vcache_entry *e;
357	status_t result = B_OK;
358
359	DPRINTF(0, ("vcache_set_entry: %Lx -> %Lx\n", vnid, loc));
360
361	if (is_vnode_removed(vol->id, vnid) > 0) {
362		if (!IS_ARTIFICIAL_VNID(loc))
363			return B_OK;
364	} else {
365		ASSERT(is_vnode_removed(vol->id, vnid) == 0);
366	}
367
368	LOCK_CACHE_W;
369
370	e = _find_vnid_in_vcache_(vol, vnid);
371
372	if (e) {
373		if (e->vnid == loc)
374			result = _remove_from_vcache_(vol, vnid);
375		else
376			result = _update_loc_in_vcache_(vol, vnid, loc);
377	} else {
378		if (vnid != loc)
379			result = _add_to_vcache_(vol,vnid,loc);
380	}
381
382	UNLOCK_CACHE_W;
383
384	return result;
385}
386
387#if DEBUG
388
389int debug_dfvnid(int argc, char **argv)
390{
391	int i;
392	nspace *vol;
393
394	if (argc < 3) {
395		kprintf("dfvnid nspace vnid\n");
396		return B_OK;
397	}
398
399	vol = (nspace *)strtoul(argv[1], NULL, 0);
400	if (vol == NULL)
401		return B_OK;
402
403	for (i=2;i<argc;i++) {
404		vnode_id vnid = strtoull(argv[i], NULL, 0);
405		struct vcache_entry *e;
406		if ((e = _find_vnid_in_vcache_(vol, vnid)) != NULL) {
407			kprintf("vnid %Lx -> loc %Lx @ %p\n", vnid, e->loc, e);
408		} else {
409			kprintf("vnid %Lx not found in vnid cache\n", vnid);
410		}
411	}
412
413	return B_OK;
414}
415
416int debug_dfloc(int argc, char **argv)
417{
418	int i;
419	nspace *vol;
420
421	if (argc < 3) {
422		kprintf("dfloc nspace vnid\n");
423		return B_OK;
424	}
425
426	vol = (nspace *)strtoul(argv[1], NULL, 0);
427	if (vol == NULL)
428		return B_OK;
429
430	for (i=2;i<argc;i++) {
431		vnode_id loc = strtoull(argv[i], NULL, 0);
432		struct vcache_entry *e;
433		if ((e = _find_loc_in_vcache_(vol, loc)) != NULL) {
434			kprintf("loc %Lx -> vnid %Lx @ %p\n", loc, e->vnid, e);
435		} else {
436			kprintf("loc %Lx not found in vnid cache\n", loc);
437		}
438	}
439
440	return B_OK;
441}
442
443#endif
444