1 /*
2 * Copyright 1999-2001, Be Incorporated. All Rights Reserved.
3 * Copyright 2024, Haiku, Inc. All rights reserved.
4 * This file may be used under the terms of the Be Sample Code License.
5 */
6
7
8 /*
9 The FAT file system has no good way of assigning unique persistent values to
10 nodes. The only obvious choice, storing the starting cluster number of the
11 file, is unusable because 0 byte files exist as directory entries only.
12 Further, even if it were usable, it would potentially require a full directory
13 tree traversal to locate an arbitrary node. We must resort to some ickiness
14 in order to make persistent vnode id's (at least across a given mount) work.
15
16 There are three ways to encode a vnode id:
17
18 1. Combine the starting cluster of the entry with the starting cluster of the
19 directory it appears in. This is used for files with data.
20 2. Combine the starting cluster of the directory the entry appears in with the
21 index of the entry in the directory. This is used for 0-byte files.
22 3. A unique number that doesn't match any possible values from encodings 1 or
23 2.
24
25 With the first encoding, the vnode id is invalidated (i.e. no longer describes
26 the file's location) when the file moves to a different directory or when
27 its starting cluster changes (this can occur if the file is truncated and data
28 is subsequently written to it).
29
30 With the second encoding, the vnode id is invalidated when the file position
31 is moved within a directory (as a result of a renaming), when it's moved to a
32 different directory, or when data is written to it.
33
34 The third encoding doesn't describe the file's location on disk, and so it is
35 invalid from the start.
36
37 Since we can't change vnode id's once they are assigned, we have to create a
38 mapping table to translate vnode id's to locations. This file serves this
39 purpose.
40
41 It also allows the FS to check whether a node with a given inode number has been constructed,
42 without calling get_vnode().
43 */
44
45
46 #include "vcache.h"
47
48 #ifdef FS_SHELL
49 #include "fssh_api_wrapper.h"
50 #else // !FS_SHELL
51 #include <new>
52 #include <stdint.h>
53 #include <stdio.h>
54 #include <stdlib.h>
55 #endif // !FS_SHELL
56
57 #ifndef FS_SHELL
58 #include <fs_cache.h>
59 #include <fs_interface.h>
60 #endif // !FS_SHELL
61
62 #define _KERNEL
63 #include "sys/vnode.h"
64
65 #include "debug.h"
66 #include "dosfs.h"
67
68
69 #define LOCK_CACHE_R \
70 rw_lock_read_lock(&vol->vcache.lock)
71
72 #define LOCK_CACHE_W \
73 rw_lock_write_lock(&vol->vcache.lock)
74
75 #define UNLOCK_CACHE_R \
76 rw_lock_read_unlock(&vol->vcache.lock)
77
78 #define UNLOCK_CACHE_W \
79 rw_lock_write_unlock(&vol->vcache.lock)
80
81 #define hash(v) ((v) & (vol->vcache.cache_size-1))
82
83
84 struct vcache_entry {
85 ino_t vnid; /* originally reported vnid */
86 ino_t loc; /* where the file is now */
87 bool constructed; /* has the node been set up by _dosfs_read_vnode */
88 struct vcache_entry *next_vnid; /* next entry in vnid hash table */
89 struct vcache_entry *next_loc; /* next entry in location hash table */
90 #ifdef DEBUG
91 struct vnode* node;
92 #endif
93 };
94
95
96 void
dump_vcache(const mount * vol)97 dump_vcache(const mount* vol)
98 {
99 uint32 i;
100 struct vcache_entry *c;
101 #if defined DEBUG && defined _KERNEL_MODE
102 kprintf("vnid cache size %" B_PRIu32 ", cur vnid = %" B_PRIdINO "\n"
103 "vnid loc %-*s\n", vol->vcache.cache_size, vol->vcache.cur_vnid,
104 B_PRINTF_POINTER_WIDTH, "struct vnode");
105 for (i = 0; i < vol->vcache.cache_size; i++) {
106 for (c = vol->vcache.by_vnid[i]; c ; c = c->next_vnid)
107 kprintf("%19" B_PRIdINO " %16" B_PRIdINO " %p\n", c->vnid, c->loc, c->node);
108 }
109 #else
110 kprintf("vnid cache size %" B_PRIu32 ", cur vnid = %" B_PRIdINO "\n"
111 "vnid loc\n", vol->vcache.cache_size, vol->vcache.cur_vnid);
112 for (i = 0; i < vol->vcache.cache_size; i++) {
113 for (c = vol->vcache.by_vnid[i]; c ; c = c->next_vnid)
114 kprintf("%19" B_PRIdINO " %16" B_PRIdINO "\n", c->vnid, c->loc);
115 }
116 #endif // !DEBUG
117 }
118
119
120 status_t
init_vcache(mount * vol)121 init_vcache(mount* vol)
122 {
123 char name[16];
124 FUNCTION();
125
126 vol->vcache.cur_vnid = ARTIFICIAL_VNID_BITS;
127 #if DEBUG
128 vol->vcache.cache_size = 1;
129 #else
130 vol->vcache.cache_size = 512; /* must be power of 2 */
131 #endif
132
133 vol->vcache.by_vnid = (vcache_entry**)calloc(sizeof(struct vache_entry *),
134 vol->vcache.cache_size);
135 if (vol->vcache.by_vnid == NULL) {
136 INFORM("init_vcache: out of memory\n");
137 return ENOMEM;
138 }
139
140 vol->vcache.by_loc = (vcache_entry**)calloc(sizeof(struct vache_entry *),
141 vol->vcache.cache_size);
142 if (vol->vcache.by_loc == NULL) {
143 INFORM("init_vcache: out of memory\n");
144 free(vol->vcache.by_vnid);
145 vol->vcache.by_vnid = NULL;
146 return ENOMEM;
147 }
148
149 sprintf(name, "fat cache %" B_PRIdDEV, vol->mnt_fsvolume->id);
150 rw_lock_init(&vol->vcache.lock, "fat cache");
151
152 PRINT("init_vcache: initialized vnid cache with %" B_PRIu32
153 " entries\n", vol->vcache.cache_size);
154
155 return 0;
156 }
157
158
159 status_t
uninit_vcache(mount * vol)160 uninit_vcache(mount* vol)
161 {
162 uint32 i, count = 0;
163 struct vcache_entry *c, *n;
164 FUNCTION();
165
166 LOCK_CACHE_W;
167
168 /* free entries */
169 for (i = 0; i < vol->vcache.cache_size; i++) {
170 c = vol->vcache.by_vnid[i];
171 while (c) {
172 count++;
173 n = c->next_vnid;
174 free(c);
175 c = n;
176 }
177 }
178
179 PRINT("%" B_PRIu32 " vcache entries removed\n", count);
180
181 free(vol->vcache.by_vnid); vol->vcache.by_vnid = NULL;
182 free(vol->vcache.by_loc); vol->vcache.by_loc = NULL;
183
184 rw_lock_destroy(&vol->vcache.lock);
185 return B_OK;
186 }
187
188
189 ino_t
generate_unique_vnid(mount * vol)190 generate_unique_vnid(mount* vol)
191 {
192 FUNCTION();
193
194 #ifdef FS_SHELL
195 LOCK_CACHE_W;
196 ino_t current = vol->vcache.cur_vnid++;
197 UNLOCK_CACHE_W;
198
199 return current;
200 #else
201 return atomic_add64(&vol->vcache.cur_vnid, 1);
202 #endif // !FS_SHELL
203 }
204
205
206 static status_t
_add_to_vcache_(mount * vol,ino_t vnid,ino_t loc)207 _add_to_vcache_(mount* vol, ino_t vnid, ino_t loc)
208 {
209 int hash1 = hash(vnid), hash2 = hash(loc);
210 struct vcache_entry *e, *c, *p;
211
212 FUNCTION_START("%" B_PRIdINO "/%" B_PRIdINO "\n", vnid, loc);
213
214 e = (vcache_entry*)malloc(sizeof(struct vcache_entry));
215 if (e == NULL)
216 return ENOMEM;
217
218 e->vnid = vnid; e->loc = loc; e->constructed = false; e->next_vnid = NULL; e->next_loc = NULL;
219
220 c = p = vol->vcache.by_vnid[hash1];
221 while (c) {
222 if (vnid < c->vnid)
223 break;
224 ASSERT(vnid != c->vnid); ASSERT(loc != c->loc);
225 p = c;
226 c = c->next_vnid;
227 }
228 ASSERT(!c || (vnid != c->vnid));
229
230 e->next_vnid = c;
231 if (p == c)
232 vol->vcache.by_vnid[hash1] = e;
233 else
234 p->next_vnid = e;
235
236 c = p = vol->vcache.by_loc[hash2];
237 while (c) {
238 if (loc < c->loc)
239 break;
240 ASSERT(vnid != c->vnid); ASSERT(loc != c->loc);
241 p = c;
242 c = c->next_loc;
243 }
244 ASSERT(!c || (loc != c->loc));
245
246 e->next_loc = c;
247 if (p == c)
248 vol->vcache.by_loc[hash2] = e;
249 else
250 p->next_loc = e;
251
252 return B_OK;
253 }
254
255
256 static status_t
_remove_from_vcache_(mount * vol,ino_t vnid)257 _remove_from_vcache_(mount* vol, ino_t vnid)
258 {
259 int hash1 = hash(vnid), hash2;
260 struct vcache_entry *c, *p, *e;
261
262 FUNCTION_START("%" B_PRIdINO "\n", vnid);
263
264 c = p = vol->vcache.by_vnid[hash1];
265 while (c) {
266 if (vnid == c->vnid)
267 break;
268 ASSERT(c->vnid < vnid);
269 p = c;
270 c = c->next_vnid;
271 }
272 ASSERT(c);
273 if (!c) return ENOENT;
274
275 if (p == c)
276 vol->vcache.by_vnid[hash1] = c->next_vnid;
277 else
278 p->next_vnid = c->next_vnid;
279
280 e = c;
281
282 hash2 = hash(c->loc);
283 c = p = vol->vcache.by_loc[hash2];
284
285 while (c) {
286 if (vnid == c->vnid)
287 break;
288 ASSERT(c->loc < e->loc);
289 p = c;
290 c = c->next_loc;
291 }
292 ASSERT(c);
293 if (!c) return ENOENT;
294 if (p == c)
295 vol->vcache.by_loc[hash2] = c->next_loc;
296 else
297 p->next_loc = c->next_loc;
298
299 free(c);
300
301 return 0;
302 }
303
304
305 static struct vcache_entry *
_find_vnid_in_vcache_(mount * vol,ino_t vnid)306 _find_vnid_in_vcache_(mount* vol, ino_t vnid)
307 {
308 int hash1 = hash(vnid);
309 struct vcache_entry *c;
310 c = vol->vcache.by_vnid[hash1];
311 while (c) {
312 if (c->vnid == vnid)
313 break;
314 if (c->vnid > vnid)
315 return NULL;
316 c = c->next_vnid;
317 }
318
319 return c;
320 }
321
322
323 static struct vcache_entry *
_find_loc_in_vcache_(mount * vol,ino_t loc)324 _find_loc_in_vcache_(mount* vol, ino_t loc)
325 {
326 int hash2 = hash(loc);
327 struct vcache_entry *c;
328 c = vol->vcache.by_loc[hash2];
329 while (c) {
330 if (c->loc == loc)
331 break;
332 if (c->loc > loc)
333 return NULL;
334 c = c->next_loc;
335 }
336
337 return c;
338 }
339
340
341 status_t
add_to_vcache(mount * vol,ino_t vnid,ino_t loc)342 add_to_vcache(mount* vol, ino_t vnid, ino_t loc)
343 {
344 status_t result;
345
346 LOCK_CACHE_W;
347 result = _add_to_vcache_(vol,vnid,loc);
348 UNLOCK_CACHE_W;
349
350 if (result < 0) INFORM("add_to_vcache failed (%s)\n", strerror(result));
351 return result;
352 }
353
354
355 static status_t
_update_loc_in_vcache_(mount * vol,ino_t vnid,ino_t loc)356 _update_loc_in_vcache_(mount* vol, ino_t vnid, ino_t loc)
357 {
358 status_t result;
359 bool constructed;
360 result = vcache_get_constructed(vol, vnid, &constructed);
361 if (result != B_OK)
362 return result;
363 #if DEBUG
364 struct vnode *node;
365 result = vcache_get_node(vol, vnid, &node);
366 if (result != B_OK)
367 return result;
368 #endif // DEBUG
369
370 result = _remove_from_vcache_(vol, vnid);
371 if (result == 0) {
372 result = _add_to_vcache_(vol, vnid, loc);
373 if (result == B_OK && constructed == true)
374 result = vcache_set_constructed(vol, vnid);
375 #if DEBUG
376 if (result == B_OK)
377 result = vcache_set_node(vol, vnid, node);
378 #endif // DEBUG
379 }
380
381 return result;
382 }
383
384
385 status_t
remove_from_vcache(mount * vol,ino_t vnid)386 remove_from_vcache(mount* vol, ino_t vnid)
387 {
388 status_t result;
389
390 LOCK_CACHE_W;
391 result = _remove_from_vcache_(vol, vnid);
392 UNLOCK_CACHE_W;
393
394 if (result < 0) INFORM("remove_from_vcache failed (%s)\n", strerror(result));
395 return result;
396 }
397
398
399 status_t
vcache_vnid_to_loc(mount * vol,ino_t vnid,ino_t * loc)400 vcache_vnid_to_loc(mount* vol, ino_t vnid, ino_t* loc)
401 {
402 struct vcache_entry *e;
403
404 FUNCTION_START("%" B_PRIdINO " %p\n", vnid, loc);
405
406 LOCK_CACHE_R;
407 e = _find_vnid_in_vcache_(vol, vnid);
408 if (loc && e)
409 *loc = e->loc;
410 UNLOCK_CACHE_R;
411
412 return (e) ? B_OK : ENOENT;
413 }
414
415
416 status_t
vcache_loc_to_vnid(mount * vol,ino_t loc,ino_t * vnid)417 vcache_loc_to_vnid(mount* vol, ino_t loc, ino_t* vnid)
418 {
419 struct vcache_entry *e;
420
421 FUNCTION_START("%" B_PRIdINO " %p\n", loc, vnid);
422
423 LOCK_CACHE_R;
424 e = _find_loc_in_vcache_(vol, loc);
425 if (vnid && e)
426 *vnid = e->vnid;
427 UNLOCK_CACHE_R;
428
429 return (e) ? B_OK : ENOENT;
430 }
431
432
433 status_t
vcache_set_entry(mount * vol,ino_t vnid,ino_t loc)434 vcache_set_entry(mount* vol, ino_t vnid, ino_t loc)
435 {
436 struct vcache_entry *e;
437 status_t result = B_OK;
438
439 FUNCTION_START("vcache_set_entry: %" B_PRIdINO " -> %" B_PRIdINO "\n", vnid, loc);
440
441 LOCK_CACHE_W;
442
443 e = _find_vnid_in_vcache_(vol, vnid);
444
445 if (e)
446 result = _update_loc_in_vcache_(vol, vnid, loc);
447 else
448 result = _add_to_vcache_(vol,vnid,loc);
449
450 UNLOCK_CACHE_W;
451
452 return result;
453 }
454
455
456 status_t
vcache_set_constructed(mount * vol,ino_t vnid,bool constructed)457 vcache_set_constructed(mount* vol, ino_t vnid, bool constructed)
458 {
459 struct vcache_entry* cEntry;
460 status_t result = B_OK;
461
462 FUNCTION_START("%" B_PRIdINO "\n", vnid);
463
464 LOCK_CACHE_W;
465
466 cEntry = _find_vnid_in_vcache_(vol, vnid);
467
468 if (cEntry != NULL)
469 cEntry->constructed = constructed;
470 else
471 result = B_BAD_VALUE;
472
473 UNLOCK_CACHE_W;
474
475 return result;
476 }
477
478
479 status_t
vcache_get_constructed(mount * vol,ino_t vnid,bool * constructed)480 vcache_get_constructed(mount* vol, ino_t vnid, bool* constructed)
481 {
482 struct vcache_entry* cEntry;
483 status_t result = B_OK;
484
485 FUNCTION_START("%" B_PRIdINO "\n", vnid);
486
487 LOCK_CACHE_W;
488
489 cEntry = _find_vnid_in_vcache_(vol, vnid);
490
491 if (cEntry != NULL)
492 *constructed = cEntry->constructed;
493 else
494 result = B_BAD_VALUE;
495
496 UNLOCK_CACHE_W;
497
498 return result;
499 }
500
501
502 status_t
sync_all_files(mount * vol)503 sync_all_files(mount* vol)
504 {
505 uint32 count = 0, errors = 0;
506 vnode* bsdNode = NULL;
507 status_t status = B_OK;
508
509 FUNCTION_START("volume @ %p\n", vol);
510
511 LOCK_CACHE_R;
512
513 for (uint32 i = 0; i < vol->vcache.cache_size; i++) {
514 for (vcache_entry* cEntry = vol->vcache.by_vnid[i]; cEntry != NULL ;
515 cEntry = cEntry->next_vnid) {
516 if (cEntry->constructed == true) {
517 status = get_vnode(vol->mnt_fsvolume, cEntry->vnid,
518 reinterpret_cast<void**>(&bsdNode));
519 if (status != B_OK) {
520 INFORM("get_vnode: %s\n", strerror(status));
521 errors++;
522 } else {
523 if (bsdNode->v_type == VREG) {
524 status = file_cache_sync(bsdNode->v_cache);
525 if (status != B_OK)
526 errors++;
527 else
528 count++;
529 }
530 put_vnode(vol->mnt_fsvolume, cEntry->vnid);
531 }
532 }
533 }
534 }
535
536 UNLOCK_CACHE_R;
537
538 PRINT("sync'd %" B_PRIu32 " files with %" B_PRIu32 " errors\n", count, errors);
539
540 return (errors == 0) ? B_OK : B_ERROR;
541 }
542
543
544 #if DEBUG
545 status_t
vcache_set_node(mount * vol,ino_t vnid,struct vnode * node)546 vcache_set_node(mount* vol, ino_t vnid, struct vnode* node)
547 {
548 vcache_entry* cEntry;
549 status_t result = B_OK;
550
551 FUNCTION_START("%" B_PRIdINO "\n", vnid);
552
553 LOCK_CACHE_W;
554
555 cEntry = _find_vnid_in_vcache_(vol, vnid);
556
557 if (cEntry != NULL)
558 cEntry->node = node;
559 else
560 result = B_BAD_VALUE;
561
562 UNLOCK_CACHE_W;
563
564 return result;
565 }
566
567
568 status_t
vcache_get_node(mount * vol,ino_t vnid,struct vnode ** node)569 vcache_get_node(mount* vol, ino_t vnid, struct vnode** node)
570 {
571 vcache_entry* cEntry;
572 status_t result = B_OK;
573
574 FUNCTION_START("%" B_PRIdINO "\n", vnid);
575
576 LOCK_CACHE_W;
577
578 cEntry = _find_vnid_in_vcache_(vol, vnid);
579
580 if (cEntry != NULL)
581 *node = cEntry->node;
582 else
583 result = B_BAD_VALUE;
584
585 UNLOCK_CACHE_W;
586
587 return result;
588 }
589
590
591 int
debug_dfvnid(int argc,char ** argv)592 debug_dfvnid(int argc, char **argv)
593 {
594 int i;
595 mount* vol;
596
597 if (argc < 3) {
598 kprintf("dfvnid volume vnid\n");
599 return B_OK;
600 }
601
602 vol = reinterpret_cast<mount*>(strtoul(argv[1], NULL, 0));
603 if (vol == NULL)
604 return B_OK;
605
606 for (i = 2; i < argc; i++) {
607 ino_t vnid = strtoull(argv[i], NULL, 0);
608 struct vcache_entry *e;
609 if ((e = _find_vnid_in_vcache_(vol, vnid)) != NULL) {
610 kprintf("vnid %" B_PRIdINO " -> loc %" B_PRIdINO " @ %p\n", vnid,
611 e->loc, e);
612 } else {
613 kprintf("vnid %" B_PRIdINO " not found in vnid cache\n", vnid);
614 }
615 }
616
617 return B_OK;
618 }
619
620
621 int
debug_dfloc(int argc,char ** argv)622 debug_dfloc(int argc, char **argv)
623 {
624 int i;
625 mount* vol;
626
627 if (argc < 3) {
628 kprintf("dfloc volume vnid\n");
629 return B_OK;
630 }
631
632 vol = reinterpret_cast<mount*>(strtoul(argv[1], NULL, 0));
633 if (vol == NULL)
634 return B_OK;
635
636 for (i = 2; i < argc; i++) {
637 ino_t loc = strtoull(argv[i], NULL, 0);
638 struct vcache_entry *e;
639 if ((e = _find_loc_in_vcache_(vol, loc)) != NULL) {
640 kprintf("loc %" B_PRIdINO " -> vnid %" B_PRIdINO " @ %p\n", loc,
641 e->vnid, e);
642 } else {
643 kprintf("loc %" B_PRIdINO " not found in vnid cache\n", loc);
644 }
645 }
646
647 return B_OK;
648 }
649 #endif // DEBUG
650