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