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