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 7#include "fat.h" 8 9#include <stdlib.h> 10#include <string.h> 11 12#include <fs_cache.h> 13#include <ByteOrder.h> 14#include <KernelExport.h> 15 16#include "dosfs.h" 17#include "file.h" 18#include "util.h" 19#include "vcache.h" 20 21 22#define END_FAT_ENTRY 0x0fffffff 23#define BAD_FAT_ENTRY 0x0ffffff1 24 25#define DPRINTF(a,b) if (debug_fat > (a)) dprintf b 26 27 28static status_t 29mirror_fats(nspace *vol, uint32 sector, uint8 *buffer) 30{ 31 uint32 i; 32 33 if (!vol->fat_mirrored) 34 return B_OK; 35 36 sector -= vol->active_fat * vol->sectors_per_fat; 37 38 for (i = 0; i < vol->fat_count; i++) { 39 char *blockData; 40 if (i == vol->active_fat) 41 continue; 42 43 blockData = block_cache_get_writable_etc(vol->fBlockCache, sector 44 + i * vol->sectors_per_fat, 0, 1, -1); 45 memcpy(blockData, buffer, vol->bytes_per_sector); 46 block_cache_put(vol->fBlockCache, sector + i * vol->sectors_per_fat); 47 } 48 49 return B_OK; 50} 51 52 53static int32 54_count_free_clusters_fat32(nspace *vol) 55{ 56 int32 count = 0; 57 const uint8 *block; 58 uint32 fat_sector; 59 uint32 i; 60 uint32 cur_sector; 61 62 cur_sector = vol->reserved_sectors + vol->active_fat * vol->sectors_per_fat; 63 64 for (fat_sector = 0; fat_sector < vol->sectors_per_fat; fat_sector++) { 65 block = (uint8 *)block_cache_get(vol->fBlockCache, cur_sector); 66 if(block == NULL) 67 return B_IO_ERROR; 68 69 for (i = 0; i < vol->bytes_per_sector; i += sizeof(uint32)) { 70 uint32 val = read32(block, i); 71 if ((val & 0x0fffffff) == 0) 72 count++; 73 } 74 75 block_cache_put(vol->fBlockCache, cur_sector); 76 cur_sector++; 77 } 78 79 return count; 80} 81 82// count free: no parameters. returns int32 83// get_entry: cluster #. returns int32 entry/status 84// set_entry: cluster #, value. returns int32 status 85// allocate: # clusters in N, returns int32 status/starting cluster 86 87enum { 88 _IOCTL_COUNT_FREE_, 89 _IOCTL_GET_ENTRY_, 90 _IOCTL_SET_ENTRY_, 91 _IOCTL_ALLOCATE_N_ENTRIES_ 92}; 93 94static int32 95_fat_ioctl_(nspace *vol, uint32 action, uint32 cluster, int32 N) 96{ 97 int32 result = 0; 98 uint32 n = 0, first = 0, last = 0; 99 uint32 i; 100 uint32 sector; 101 uint32 offset, value = 0; /* quiet warning */ 102 uint8 *block1, *block2 = NULL; /* quiet warning */ 103 bool readOnly 104 = action != _IOCTL_SET_ENTRY_ && action != _IOCTL_ALLOCATE_N_ENTRIES_; 105 106 // mark end of chain for allocations 107 uint32 endOfChainMarker = (action == _IOCTL_SET_ENTRY_) ? N : 0x0fffffff; 108 109 ASSERT(action >= _IOCTL_COUNT_FREE_ 110 && action <= _IOCTL_ALLOCATE_N_ENTRIES_); 111 112 DPRINTF(3, ("_fat_ioctl_: action %lx, cluster %ld, N %ld\n", action, 113 cluster, N)); 114 115 if (action == _IOCTL_COUNT_FREE_) { 116 if(vol->fat_bits == 32) 117 // use a optimized version of the cluster counting algorithms 118 return _count_free_clusters_fat32(vol); 119 else 120 cluster = 2; 121 } 122 123 if (action == _IOCTL_ALLOCATE_N_ENTRIES_) 124 cluster = vol->last_allocated; 125 126 if (action != _IOCTL_COUNT_FREE_) { 127 if (!IS_DATA_CLUSTER(cluster)) { 128 DPRINTF(0, ("_fat_ioctl_ called with invalid cluster (%ld)\n", 129 cluster)); 130 return B_BAD_VALUE; 131 } 132 } 133 134 offset = cluster * vol->fat_bits / 8; 135 sector = vol->reserved_sectors + vol->active_fat * vol->sectors_per_fat + 136 offset / vol->bytes_per_sector; 137 offset %= vol->bytes_per_sector; 138 139 if (readOnly) { 140 block1 = (uint8 *)block_cache_get(vol->fBlockCache, sector); 141 } else { 142 block1 = (uint8 *)block_cache_get_writable(vol->fBlockCache, sector, 143 -1); 144 } 145 146 if (block1 == NULL) { 147 DPRINTF(0, ("_fat_ioctl_: error reading fat (sector %ld)\n", sector)); 148 return B_IO_ERROR; 149 } 150 151 for (i = 0; i < vol->total_clusters; i++) { 152 ASSERT(IS_DATA_CLUSTER(cluster)); 153 ASSERT(offset == ((cluster * vol->fat_bits / 8) 154 % vol->bytes_per_sector)); 155 156 if (vol->fat_bits == 12) { 157 if (offset == vol->bytes_per_sector - 1) { 158 if (readOnly) { 159 block2 = (uint8 *)block_cache_get(vol->fBlockCache, 160 ++sector); 161 } else { 162 block2 = (uint8 *)block_cache_get_writable(vol->fBlockCache, 163 ++sector, -1); 164 } 165 166 if (block2 == NULL) { 167 DPRINTF(0, ("_fat_ioctl_: error reading fat (sector %ld)\n", 168 sector)); 169 result = B_IO_ERROR; 170 sector--; 171 goto bi; 172 } 173 } 174 175 if (action != _IOCTL_SET_ENTRY_) { 176 if (offset == vol->bytes_per_sector - 1) 177 value = block1[offset] + 0x100 * block2[0]; 178 else 179 value = block1[offset] + 0x100 * block1[offset + 1]; 180 181 if (cluster & 1) 182 value >>= 4; 183 else 184 value &= 0xfff; 185 186 if (value > 0xff0) 187 value |= 0x0ffff000; 188 } 189 190 if (((action == _IOCTL_ALLOCATE_N_ENTRIES_) && (value == 0)) 191 || action == _IOCTL_SET_ENTRY_) { 192 uint32 andmask, ormask; 193 if (cluster & 1) { 194 ormask = (endOfChainMarker & 0xfff) << 4; 195 andmask = 0xf; 196 } else { 197 ormask = endOfChainMarker & 0xfff; 198 andmask = 0xf000; 199 } 200 201 block1[offset] &= (andmask & 0xff); 202 block1[offset] |= (ormask & 0xff); 203 if (offset == vol->bytes_per_sector - 1) { 204 mirror_fats(vol, sector - 1, block1); 205 block2[0] &= (andmask >> 8); 206 block2[0] |= (ormask >> 8); 207 } else { 208 block1[offset + 1] &= (andmask >> 8); 209 block1[offset + 1] |= (ormask >> 8); 210 } 211 } 212 213 if (offset == vol->bytes_per_sector - 1) { 214 offset = (cluster & 1) ? 1 : 0; 215 block_cache_put(vol->fBlockCache, sector - 1); 216 block1 = block2; 217 } else 218 offset += (cluster & 1) ? 2 : 1; 219 220 } else if (vol->fat_bits == 16) { 221 if (action != _IOCTL_SET_ENTRY_) { 222 value = read16(block1, offset); 223 if (value > 0xfff0) 224 value |= 0x0fff0000; 225 } 226 227 if (((action == _IOCTL_ALLOCATE_N_ENTRIES_) && (value == 0)) 228 || action == _IOCTL_SET_ENTRY_) { 229 *(uint16 *)&block1[offset] 230 = B_HOST_TO_LENDIAN_INT16(endOfChainMarker); 231 } 232 233 offset += 2; 234 } else if (vol->fat_bits == 32) { 235 if (action != _IOCTL_SET_ENTRY_) 236 value = read32(block1, offset) & 0x0fffffff; 237 238 if (((action == _IOCTL_ALLOCATE_N_ENTRIES_) && (value == 0)) 239 || action == _IOCTL_SET_ENTRY_) { 240 ASSERT((endOfChainMarker & 0xf0000000) == 0); 241 *(uint32 *)&block1[offset] 242 = B_HOST_TO_LENDIAN_INT32(endOfChainMarker); 243 } 244 245 offset += 4; 246 } else 247 ASSERT(0); 248 249 if (action == _IOCTL_COUNT_FREE_) { 250 if (value == 0) 251 result++; 252 } else if (action == _IOCTL_GET_ENTRY_) { 253 result = value; 254 goto bi; 255 } else if (action == _IOCTL_SET_ENTRY_) { 256 mirror_fats(vol, sector, block1); 257 goto bi; 258 } else if (action == _IOCTL_ALLOCATE_N_ENTRIES_ && value == 0) { 259 vol->free_clusters--; 260 mirror_fats(vol, sector, block1); 261 262 if (n == 0) { 263 ASSERT(first == 0); 264 first = last = cluster; 265 } else { 266 ASSERT(IS_DATA_CLUSTER(first)); 267 ASSERT(IS_DATA_CLUSTER(last)); 268 // set last cluster to point to us 269 270 result = _fat_ioctl_(vol, _IOCTL_SET_ENTRY_, last, cluster); 271 if (result < 0) { 272 ASSERT(0); 273 goto bi; 274 } 275 276 last = cluster; 277 } 278 279 if (++n == N) 280 goto bi; 281 } 282 283 // iterate cluster and sector if needed 284 if (++cluster == vol->total_clusters + 2) { 285 block_cache_put(vol->fBlockCache, sector); 286 287 cluster = 2; 288 offset = cluster * vol->fat_bits / 8; 289 sector = vol->reserved_sectors + vol->active_fat 290 * vol->sectors_per_fat; 291 292 if (readOnly) 293 block1 = (uint8 *)block_cache_get(vol->fBlockCache, sector); 294 else { 295 block1 = (uint8 *)block_cache_get_writable(vol->fBlockCache, 296 sector, -1); 297 } 298 } 299 300 if (offset >= vol->bytes_per_sector) { 301 block_cache_put(vol->fBlockCache, sector); 302 303 sector++; 304 offset -= vol->bytes_per_sector; 305 ASSERT(sector < vol->reserved_sectors + (vol->active_fat + 1) 306 * vol->sectors_per_fat); 307 308 if (readOnly) 309 block1 = (uint8 *)block_cache_get(vol->fBlockCache, sector); 310 else { 311 block1 = (uint8 *)block_cache_get_writable(vol->fBlockCache, 312 sector, -1); 313 } 314 } 315 316 if (block1 == NULL) { 317 DPRINTF(0, ("_fat_ioctl_: error reading fat (sector %ld)\n", sector)); 318 result = B_IO_ERROR; 319 goto bi; 320 } 321 } 322 323bi: 324 if (block1 != NULL) 325 block_cache_put(vol->fBlockCache, sector); 326 327 if (action == _IOCTL_ALLOCATE_N_ENTRIES_) { 328 if (result < 0) { 329 DPRINTF(0, ("pooh. there is a problem. clearing chain (%ld)\n", 330 first)); 331 if (first != 0) 332 clear_fat_chain(vol, first); 333 } else if (n != N) { 334 DPRINTF(0, ("not enough free entries (%ld/%ld found)\n", n, N)); 335 if (first != 0) 336 clear_fat_chain(vol, first); 337 result = B_DEVICE_FULL; 338 } else if (result == 0) { 339 vol->last_allocated = cluster; 340 result = first; 341 ASSERT(IS_DATA_CLUSTER(first)); 342 } 343 } 344 345 if (result < B_OK) { 346 DPRINTF(0, ("_fat_ioctl_ error: action = %lx cluster = %ld N = %ld " 347 "(%s)\n", action, cluster, N, strerror(result))); 348 } 349 350 return result; 351} 352 353 354int32 355count_free_clusters(nspace *vol) 356{ 357 return _fat_ioctl_(vol, _IOCTL_COUNT_FREE_, 0, 0); 358} 359 360 361static int32 362get_fat_entry(nspace *vol, uint32 cluster) 363{ 364 int32 value = _fat_ioctl_(vol, _IOCTL_GET_ENTRY_, cluster, 0); 365 366 if (value < 0) 367 return value; 368 369 if (value == 0 || IS_DATA_CLUSTER(value)) 370 return value; 371 372 if (value > 0x0ffffff7) 373 return END_FAT_ENTRY; 374 375 if (value > 0x0ffffff0) 376 return BAD_FAT_ENTRY; 377 378 DPRINTF(0, ("invalid fat entry: 0x%08lx\n", value)); 379 return BAD_FAT_ENTRY; 380} 381 382 383static status_t 384set_fat_entry(nspace *vol, uint32 cluster, int32 value) 385{ 386 return _fat_ioctl_(vol, _IOCTL_SET_ENTRY_, cluster, value); 387} 388 389 390//! Traverse n fat entries 391int32 392get_nth_fat_entry(nspace *vol, int32 cluster, uint32 n) 393{ 394 while (n--) { 395 cluster = get_fat_entry(vol, cluster); 396 397 if (!IS_DATA_CLUSTER(cluster)) 398 break; 399 } 400 401 ASSERT(cluster != 0); 402 return cluster; 403} 404 405 406// count number of clusters in fat chain starting at given cluster 407// should only be used for calculating directory sizes because it doesn't 408// return proper error codes 409uint32 410count_clusters(nspace *vol, int32 cluster) 411{ 412 int32 count = 0; 413 414 DPRINTF(2, ("count_clusters %ld\n", cluster)); 415 416 // not intended for use on root directory 417 if (!IS_DATA_CLUSTER(cluster)) { 418 DPRINTF(0, ("count_clusters called on invalid cluster (%ld)\n", 419 cluster)); 420 return 0; 421 } 422 423 while (IS_DATA_CLUSTER(cluster)) { 424 count++; 425 426 // break out of circular fat chains in a sketchy manner 427 if (count == vol->total_clusters) 428 return 0; 429 430 cluster = get_fat_entry(vol, cluster); 431 } 432 433 DPRINTF(2, ("count_clusters %ld = %ld\n", cluster, count)); 434 435 if (cluster == END_FAT_ENTRY) 436 return count; 437 438 dprintf("cluster = %ld\n", cluster); 439 ASSERT(0); 440 return 0; 441} 442 443 444status_t 445clear_fat_chain(nspace *vol, uint32 cluster) 446{ 447 int32 c; 448 status_t result; 449 450 if (!IS_DATA_CLUSTER(cluster)) { 451 DPRINTF(0, ("clear_fat_chain called on invalid cluster (%ld)\n", 452 cluster)); 453 return B_BAD_VALUE; 454 } 455 456 ASSERT(count_clusters(vol, cluster) != 0); 457 458 DPRINTF(2, ("clearing fat chain: %ld", cluster)); 459 while (IS_DATA_CLUSTER(cluster)) { 460 if ((c = get_fat_entry(vol, cluster)) < 0) { 461 DPRINTF(0, ("clear_fat_chain: error clearing fat entry for cluster " 462 "%ld (%s)\n", cluster, strerror(c))); 463 return c; 464 } 465 466 if ((result = set_fat_entry(vol, cluster, 0)) != B_OK) { 467 DPRINTF(0, ("clear_fat_chain: error clearing fat entry for cluster " 468 "%ld (%s)\n", cluster, strerror(result))); 469 return result; 470 } 471 472 vol->free_clusters++; 473 cluster = c; 474 DPRINTF(2, (", %ld", cluster)); 475 } 476 DPRINTF(2, ("\n")); 477 478 if (cluster != END_FAT_ENTRY) { 479 dprintf("clear_fat_chain: fat chain terminated improperly with %ld\n", 480 cluster); 481 } 482 483 return 0; 484} 485 486 487status_t 488allocate_n_fat_entries(nspace *vol, int32 n, int32 *start) 489{ 490 int32 c; 491 492 ASSERT(n > 0); 493 494 DPRINTF(2, ("allocating %ld fat entries\n", n)); 495 496 c = _fat_ioctl_(vol, _IOCTL_ALLOCATE_N_ENTRIES_, 0, n); 497 if (c < 0) 498 return c; 499 500 ASSERT(IS_DATA_CLUSTER(c)); 501 ASSERT(count_clusters(vol, c) == n); 502 503 DPRINTF(2, ("allocated %ld fat entries at %ld\n", n, c)); 504 505 *start = c; 506 return 0; 507} 508 509 510status_t 511set_fat_chain_length(nspace *vol, vnode *node, uint32 clusters) 512{ 513 status_t result; 514 int32 i, c, n; 515 516 DPRINTF(1, ("set_fat_chain_length: %Lx to %ld clusters (%ld)\n", node->vnid, 517 clusters, node->cluster)); 518 519 if (IS_FIXED_ROOT(node->cluster) 520 || (!IS_DATA_CLUSTER(node->cluster) && (node->cluster != 0))) { 521 DPRINTF(0, ("set_fat_chain_length called on invalid cluster (%ld)\n", 522 node->cluster)); 523 return B_BAD_VALUE; 524 } 525 526 if (clusters == 0) { 527 DPRINTF(1, ("truncating node to zero bytes\n")); 528 if (node->cluster == 0) 529 return B_OK; 530 531 c = node->cluster; 532 if ((result = clear_fat_chain(vol, c)) != B_OK) 533 return result; 534 535 node->cluster = 0; 536 node->end_cluster = 0; 537 538 // TODO: don't have to do this this way -- can clean up nicely 539 do { 540 result = vcache_set_entry(vol, node->vnid, 541 GENERATE_DIR_INDEX_VNID(node->dir_vnid, node->sindex)); 542 // repeat until memory is freed up 543 if (result != B_OK) 544 snooze(5000LL); 545 } while (result != B_OK); 546 547 /* write to disk so that get_next_dirent doesn't barf */ 548 write_vnode_entry(vol, node); 549 return result; 550 } 551 552 if (node->cluster == 0) { 553 DPRINTF(1, ("node has no clusters. adding %ld clusters\n", clusters)); 554 555 if ((result = allocate_n_fat_entries(vol, clusters, &n)) != B_OK) 556 return result; 557 558 node->cluster = n; 559 node->end_cluster = get_nth_fat_entry(vol, n, clusters - 1); 560 561 // TODO: don't have to do this this way -- can clean up nicely 562 do { 563 result = vcache_set_entry(vol, node->vnid, 564 GENERATE_DIR_CLUSTER_VNID(node->dir_vnid, node->cluster)); 565 // repeat until memory is freed up 566 if (result != B_OK) 567 snooze(5000LL); 568 } while (result != B_OK); 569 570 /* write to disk so that get_next_dirent doesn't barf */ 571 write_vnode_entry(vol, node); 572 return result; 573 } 574 575 i = (node->st_size + vol->bytes_per_sector * vol->sectors_per_cluster - 1) 576 / vol->bytes_per_sector / vol->sectors_per_cluster; 577 if (i == clusters) 578 return B_OK; 579 580 if (clusters > i) { 581 // add new fat entries 582 DPRINTF(1, ("adding %ld new fat entries\n", clusters - i)); 583 if ((result = allocate_n_fat_entries(vol, clusters - i, &n)) != B_OK) 584 return result; 585 586 ASSERT(IS_DATA_CLUSTER(n)); 587 588 result = set_fat_entry(vol, node->end_cluster, n); 589 if (result < B_OK) { 590 clear_fat_chain(vol, n); 591 return result; 592 } 593 594 node->end_cluster = get_nth_fat_entry(vol, n, clusters - i - 1); 595 return result; 596 } 597 598 // traverse fat chain 599 c = node->cluster; 600 n = get_fat_entry(vol, c); 601 for (i = 1; i < clusters; i++) { 602 if (!IS_DATA_CLUSTER(n)) 603 break; 604 605 c = n; 606 n = get_fat_entry(vol, c); 607 } 608 609 ASSERT(i == clusters); 610 ASSERT(n != END_FAT_ENTRY); 611 612 if (i == clusters && n == END_FAT_ENTRY) 613 return B_OK; 614 615 if (n < 0) 616 return n; 617 618 if (n != END_FAT_ENTRY && !IS_DATA_CLUSTER(n)) 619 return B_BAD_VALUE; 620 621 // clear trailing fat entries 622 DPRINTF(1, ("clearing trailing fat entries\n")); 623 if ((result = set_fat_entry(vol, c, 0x0fffffff)) != B_OK) 624 return result; 625 626 node->end_cluster = c; 627 return clear_fat_chain(vol, n); 628} 629 630 631void 632dump_fat_chain(nspace *vol, uint32 cluster) 633{ 634 dprintf("fat chain: %ld", cluster); 635 while (IS_DATA_CLUSTER(cluster)) { 636 cluster = get_fat_entry(vol, cluster); 637 dprintf(" %ld", cluster); 638 } 639 640 dprintf("\n"); 641} 642 643/* 644status_t fragment(nspace *vol, uint32 *pattern) 645{ 646 uint32 sector, offset, previous_entry, i, val; 647 uchar *buffer; 648 bool dirty = FALSE; 649 650 srand(time(NULL)|1); 651 652 if (vol->fat_bits == 16) 653 previous_entry = 0xffff; 654 else if (vol->fat_bits == 32) 655 previous_entry = 0x0fffffff; 656 else { 657 dprintf("fragment: only for FAT16 and FAT32\n"); 658 return ENOSYS; 659 } 660 661 sector = vol->reserved_sectors + vol->active_fat * vol->sectors_per_fat + 662 ((vol->total_clusters + 2 - 1) * (vol->fat_bits / 8)) / 663 vol->bytes_per_sector; 664 offset = ((vol->total_clusters + 2 - 1) * (vol->fat_bits / 8)) % 665 vol->bytes_per_sector; 666 667 buffer = (uchar *)get_block(vol->fd, sector, vol->bytes_per_sector); 668 if (!buffer) { 669 dprintf("fragment: error getting fat block %lx\n", sector); 670 return EINVAL; 671 } 672 673 val = pattern ? *pattern : rand(); 674 675 for (i=vol->total_clusters+1;i>=2;i--) { 676 if (val & (1 << (i & 31))) { 677 if (vol->fat_bits == 16) { 678 if (read16(buffer, offset) == 0) { 679 buffer[offset+0] = (previous_entry ) & 0xff; 680 buffer[offset+1] = (previous_entry >> 8) & 0xff; 681 previous_entry = i; 682 dirty = TRUE; 683 vol->free_clusters--; 684 } 685 } else { 686 if (read32(buffer, offset) == 0) { 687 buffer[offset+0] = (previous_entry ) & 0xff; 688 buffer[offset+1] = (previous_entry >> 8) & 0xff; 689 buffer[offset+2] = (previous_entry >> 16) & 0xff; 690 buffer[offset+3] = (previous_entry >> 24) & 0xff; 691 previous_entry = i; 692 dirty = TRUE; 693 vol->free_clusters--; 694 } 695 } 696 } 697 698 if (!offset) { 699 if (dirty) { 700 mark_blocks_dirty(vol->fd, sector, 1); 701 mirror_fats(vol, sector, buffer); 702 } 703 release_block(vol->fd, sector); 704 705 dirty = FALSE; 706 sector--; 707 708 buffer = (uchar *)get_block(vol->fd, sector, 709 vol->bytes_per_sector); 710 if (!buffer) { 711 dprintf("fragment: error getting fat block %lx\n", sector); 712 return EINVAL; 713 } 714 } 715 716 offset = (offset - vol->fat_bits / 8 + vol->bytes_per_sector) % 717 vol->bytes_per_sector; 718 719 if (!pattern && ((i & 31) == 31)) 720 val = rand(); 721 } 722 723 if (dirty) { 724 mark_blocks_dirty(vol->fd, sector, 1); 725 mirror_fats(vol, sector, buffer); 726 } 727 release_block(vol->fd, sector); 728 729 vol->last_allocated = (rand() % vol->total_clusters) + 2; 730 731 return B_OK; 732} 733*/ 734 735