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
40#include "vcache.h"
41
42#include <stdio.h>
43#include <string.h>
44#include <stdlib.h>
45
46#include <KernelExport.h>
47
48#include "dosfs.h"
49#include "util.h"
50
51
52#define DPRINTF(a,b) if (debug_vcache > (a)) dprintf b
53
54#define LOCK_CACHE_R \
55	rw_lock_read_lock(&vol->vcache.lock)
56
57#define LOCK_CACHE_W \
58	rw_lock_write_lock(&vol->vcache.lock)
59
60#define UNLOCK_CACHE_R \
61	rw_lock_read_unlock(&vol->vcache.lock)
62
63#define UNLOCK_CACHE_W \
64	rw_lock_write_unlock(&vol->vcache.lock)
65
66#define hash(v) ((v) & (vol->vcache.cache_size-1))
67
68
69struct vcache_entry {
70	ino_t	vnid;		/* originally reported vnid */
71	ino_t	loc;		/* where the file is now */
72	struct vcache_entry *next_vnid; /* next entry in vnid hash table */
73	struct vcache_entry *next_loc;  /* next entry in location hash table */
74};
75
76
77void
78dump_vcache(nspace *vol)
79{
80	uint32 i;
81	struct vcache_entry *c;
82	kprintf("vnid cache size %lx, cur vnid = %Lx\n"
83		"vnid             loc\n",
84		vol->vcache.cache_size, vol->vcache.cur_vnid);
85	for (i = 0; i < vol->vcache.cache_size; i++) {
86		for (c = vol->vcache.by_vnid[i]; c ; c = c->next_vnid)
87			kprintf("%16Lx %16Lx\n", c->vnid, c->loc);
88	}
89}
90
91
92status_t
93init_vcache(nspace *vol)
94{
95	char name[16];
96	DPRINTF(0, ("init_vcache called\n"));
97
98	vol->vcache.cur_vnid = ARTIFICIAL_VNID_BITS;
99#if DEBUG
100	vol->vcache.cache_size = 1;
101#else
102	vol->vcache.cache_size = 512; /* must be power of 2 */
103#endif
104
105	vol->vcache.by_vnid = calloc(sizeof(struct vache_entry *),
106		vol->vcache.cache_size);
107	if (vol->vcache.by_vnid == NULL) {
108		dprintf("init_vcache: out of memory\n");
109		return ENOMEM;
110	}
111
112	vol->vcache.by_loc = calloc(sizeof(struct vache_entry *),
113		vol->vcache.cache_size);
114	if (vol->vcache.by_loc == NULL) {
115		dprintf("init_vcache: out of memory\n");
116		free(vol->vcache.by_vnid);
117		vol->vcache.by_vnid = NULL;
118		return ENOMEM;
119	}
120
121	sprintf(name, "fat cache %lx", vol->id);
122	rw_lock_init(&vol->vcache.lock, "fat cache");
123
124	DPRINTF(0, ("init_vcache: initialized vnid cache with %lx entries\n",
125		vol->vcache.cache_size));
126
127	return 0;
128}
129
130
131status_t
132uninit_vcache(nspace *vol)
133{
134	uint32 i, count = 0;
135	struct vcache_entry *c, *n;
136	DPRINTF(0, ("uninit_vcache called\n"));
137
138	LOCK_CACHE_W;
139
140	/* free entries */
141	for (i = 0; i < vol->vcache.cache_size; i++) {
142		c = vol->vcache.by_vnid[i];
143		while (c) {
144			count++;
145			n = c->next_vnid;
146			free(c);
147			c = n;
148		}
149	}
150
151	DPRINTF(0, ("%lx vcache entries removed\n", count));
152
153	free(vol->vcache.by_vnid); vol->vcache.by_vnid = NULL;
154	free(vol->vcache.by_loc); vol->vcache.by_loc = NULL;
155
156	rw_lock_destroy(&vol->vcache.lock);
157	return B_OK;
158}
159
160
161ino_t
162generate_unique_vnid(nspace *vol)
163{
164	DPRINTF(0, ("generate_unique_vnid\n"));
165	/* only one thread per volume will be in here at any given time anyway
166	 * due to volume locking */
167	return vol->vcache.cur_vnid++;
168}
169
170
171static status_t
172_add_to_vcache_(nspace *vol, ino_t vnid, ino_t loc)
173{
174	int hash1 = hash(vnid), hash2 = hash(loc);
175	struct vcache_entry *e, *c, *p;
176
177	DPRINTF(0, ("add_to_vcache %Lx/%Lx\n", vnid, loc));
178
179	ASSERT(vnid != loc);
180
181	e = malloc(sizeof(struct vcache_entry));
182	if (e == NULL)
183		return ENOMEM;
184
185	e->vnid = vnid; e->loc = loc; e->next_vnid = NULL; e->next_loc = NULL;
186
187	c = p = vol->vcache.by_vnid[hash1];
188	while (c) {
189		if (vnid < c->vnid)
190			break;
191		ASSERT(vnid != c->vnid); ASSERT(loc != c->loc);
192		p = c;
193		c = c->next_vnid;
194	}
195	ASSERT(!c || (vnid != c->vnid));
196
197	e->next_vnid = c;
198	if (p == c)
199		vol->vcache.by_vnid[hash1] = e;
200	else
201		p->next_vnid = e;
202
203	c = p = vol->vcache.by_loc[hash2];
204	while (c) {
205		if (loc < c->loc)
206			break;
207		ASSERT(vnid != c->vnid); ASSERT(loc != c->loc);
208		p = c;
209		c = c->next_loc;
210	}
211	ASSERT(!c || (loc != c->loc));
212
213	e->next_loc = c;
214	if (p == c)
215		vol->vcache.by_loc[hash2] = e;
216	else
217		p->next_loc = e;
218
219	return B_OK;
220}
221
222
223static status_t
224_remove_from_vcache_(nspace *vol, ino_t vnid)
225{
226	int hash1 = hash(vnid), hash2;
227	struct vcache_entry *c, *p, *e;
228
229	DPRINTF(0, ("remove_from_vcache %Lx\n", vnid));
230
231	c = p = vol->vcache.by_vnid[hash1];
232	while (c) {
233		if (vnid == c->vnid)
234			break;
235		ASSERT(c->vnid < vnid);
236		p = c;
237		c = c->next_vnid;
238	}
239	ASSERT(c);
240	if (!c) return ENOENT;
241
242	if (p == c)
243		vol->vcache.by_vnid[hash1] = c->next_vnid;
244	else
245		p->next_vnid = c->next_vnid;
246
247	e = c;
248
249	hash2 = hash(c->loc);
250	c = p = vol->vcache.by_loc[hash2];
251
252	while (c) {
253		if (vnid == c->vnid)
254			break;
255		ASSERT(c->loc < e->loc);
256		p = c;
257		c = c->next_loc;
258	}
259	ASSERT(c);
260	if (!c) return ENOENT;
261	if (p == c)
262		vol->vcache.by_loc[hash2] = c->next_loc;
263	else
264		p->next_loc = c->next_loc;
265
266	free(c);
267
268	return 0;
269}
270
271
272static struct vcache_entry *
273_find_vnid_in_vcache_(nspace *vol, ino_t vnid)
274{
275	int hash1 = hash(vnid);
276	struct vcache_entry *c;
277	c = vol->vcache.by_vnid[hash1];
278	while (c) {
279		if (c->vnid == vnid)
280			break;
281		if (c->vnid > vnid)
282			return NULL;
283		c = c->next_vnid;
284	}
285
286	return c;
287}
288
289
290static struct vcache_entry *
291_find_loc_in_vcache_(nspace *vol, ino_t loc)
292{
293	int hash2 = hash(loc);
294	struct vcache_entry *c;
295	c = vol->vcache.by_loc[hash2];
296	while (c) {
297		if (c->loc == loc)
298			break;
299		if (c->loc > loc)
300			return NULL;
301		c = c->next_loc;
302	}
303
304	return c;
305}
306
307
308status_t
309add_to_vcache(nspace *vol, ino_t vnid, ino_t loc)
310{
311	status_t result;
312
313	LOCK_CACHE_W;
314	result = _add_to_vcache_(vol,vnid,loc);
315	UNLOCK_CACHE_W;
316
317	if (result < 0) DPRINTF(0, ("add_to_vcache failed (%s)\n", strerror(result)));
318	return result;
319}
320
321
322/* XXX: do this in a smarter fashion */
323static status_t
324_update_loc_in_vcache_(nspace *vol, ino_t vnid, ino_t loc)
325{
326	status_t result;
327
328	result = _remove_from_vcache_(vol, vnid);
329	if (result == 0)
330		result = _add_to_vcache_(vol, vnid, loc);
331
332	return result;
333}
334
335
336status_t
337remove_from_vcache(nspace *vol, ino_t vnid)
338{
339	status_t result;
340
341	LOCK_CACHE_W;
342	result = _remove_from_vcache_(vol, vnid);
343	UNLOCK_CACHE_W;
344
345	if (result < 0) DPRINTF(0, ("remove_from_vcache failed (%s)\n", strerror(result)));
346	return result;
347}
348
349
350status_t
351vcache_vnid_to_loc(nspace *vol, ino_t vnid, ino_t *loc)
352{
353	struct vcache_entry *e;
354
355	DPRINTF(1, ("vcache_vnid_to_loc %Lx %lx\n", vnid, (uint32)loc));
356
357	LOCK_CACHE_R;
358	e = _find_vnid_in_vcache_(vol, vnid);
359	if (loc && e)
360			*loc = e->loc;
361	UNLOCK_CACHE_R;
362
363	return (e) ? B_OK : ENOENT;
364}
365
366
367status_t
368vcache_loc_to_vnid(nspace *vol, ino_t loc, ino_t *vnid)
369{
370	struct vcache_entry *e;
371
372	DPRINTF(1, ("vcache_loc_to_vnid %Lx %lx\n", loc, (uint32)vnid));
373
374	LOCK_CACHE_R;
375	e = _find_loc_in_vcache_(vol, loc);
376	if (vnid && e)
377			*vnid = e->vnid;
378	UNLOCK_CACHE_R;
379
380	return (e) ? B_OK : ENOENT;
381}
382
383
384status_t
385vcache_set_entry(nspace *vol, ino_t vnid, ino_t loc)
386{
387	struct vcache_entry *e;
388	status_t result = B_OK;
389
390	DPRINTF(0, ("vcache_set_entry: %Lx -> %Lx\n", vnid, loc));
391
392	/*if (is_vnode_removed(vol->id, vnid) > 0) {
393		if (!IS_ARTIFICIAL_VNID(loc))
394			return B_OK;
395	} else {
396		ASSERT(is_vnode_removed(vol->id, vnid) == 0);
397	}*/
398
399	LOCK_CACHE_W;
400
401	e = _find_vnid_in_vcache_(vol, vnid);
402
403	if (e) {
404		if (e->vnid == loc)
405			result = _remove_from_vcache_(vol, vnid);
406		else
407			result = _update_loc_in_vcache_(vol, vnid, loc);
408	} else {
409		if (vnid != loc)
410			result = _add_to_vcache_(vol,vnid,loc);
411	}
412
413	UNLOCK_CACHE_W;
414
415	return result;
416}
417
418#if DEBUG
419
420int
421debug_dfvnid(int argc, char **argv)
422{
423	int i;
424	nspace *vol;
425
426	if (argc < 3) {
427		kprintf("dfvnid nspace vnid\n");
428		return B_OK;
429	}
430
431	vol = (nspace *)strtoul(argv[1], NULL, 0);
432	if (vol == NULL)
433		return B_OK;
434
435	for (i = 2; i < argc; i++) {
436		ino_t vnid = strtoull(argv[i], NULL, 0);
437		struct vcache_entry *e;
438		if ((e = _find_vnid_in_vcache_(vol, vnid)) != NULL) {
439			kprintf("vnid %Lx -> loc %Lx @ %p\n", vnid, e->loc, e);
440		} else {
441			kprintf("vnid %Lx not found in vnid cache\n", vnid);
442		}
443	}
444
445	return B_OK;
446}
447
448
449int
450debug_dfloc(int argc, char **argv)
451{
452	int i;
453	nspace *vol;
454
455	if (argc < 3) {
456		kprintf("dfloc nspace vnid\n");
457		return B_OK;
458	}
459
460	vol = (nspace *)strtoul(argv[1], NULL, 0);
461	if (vol == NULL)
462		return B_OK;
463
464	for (i = 2; i < argc; i++) {
465		ino_t loc = strtoull(argv[i], NULL, 0);
466		struct vcache_entry *e;
467		if ((e = _find_loc_in_vcache_(vol, loc)) != NULL) {
468			kprintf("loc %Lx -> vnid %Lx @ %p\n", loc, e->vnid, e);
469		} else {
470			kprintf("loc %Lx not found in vnid cache\n", loc);
471		}
472	}
473
474	return B_OK;
475}
476
477#endif
478