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 /* 6 The FAT file system has no good way of assigning unique persistent values to 7 nodes. The only obvious choice, storing the starting cluster number of the 8 file, is unusable because 0 byte files exist as directory entries only. 9 Further, even if it were usable, it would potentially require a full directory 10 tree traversal to locate an arbitrary node. We must resort to some ickiness 11 in order to make persistent vnode id's (at least across a given mount) work. 12 13 There are three ways to encode a vnode id: 14 15 1. 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. 17 2. 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. 19 3. A unique number that doesn't match any possible values from encodings 1 or 20 2. 21 22 With the first encoding, the vnode id is invalidated (i.e. no longer describes 23 the file's location) when the file moves to a different directory or when 24 its starting cluster changes (this can occur if the file is truncated and data 25 is subsequently written to it). 26 27 With the second encoding, the vnode id is invalidated when the file position 28 is moved within a directory (as a result of a renaming), when it's moved to a 29 different directory, or when data is written to it. 30 31 The third encoding doesn't describe the file's location on disk, and so it is 32 invalid from the start. 33 34 Since we can't change vnode id's once they are assigned, we have to create a 35 mapping table to translate vnode id's to locations. This file serves this 36 purpose. 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 65 struct 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 73 void 74 dump_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 87 status_t 88 init_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 126 status_t 127 uninit_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 156 ino_t 157 generate_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 166 static 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 218 static 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 267 static 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 285 static 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 303 status_t 304 add_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 */ 318 static 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 331 status_t 332 remove_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 345 status_t 346 vcache_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 363 status_t 364 vcache_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 381 status_t 382 vcache_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 418 int 419 debug_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 448 int 449 debug_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