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