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