msdosfs_fat.c revision 171747
1/* $FreeBSD: head/sys/fs/msdosfs/msdosfs_fat.c 171747 2007-08-07 01:07:16Z bde $ */ 2/* $NetBSD: msdosfs_fat.c,v 1.28 1997/11/17 15:36:49 ws Exp $ */ 3 4/*- 5 * Copyright (C) 1994, 1995, 1997 Wolfgang Solfrank. 6 * Copyright (C) 1994, 1995, 1997 TooLs GmbH. 7 * All rights reserved. 8 * Original code by Paul Popelka (paulp@uts.amdahl.com) (see below). 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by TooLs GmbH. 21 * 4. The name of TooLs GmbH may not be used to endorse or promote products 22 * derived from this software without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY TOOLS GMBH ``AS IS'' AND ANY EXPRESS OR 25 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 26 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 27 * IN NO EVENT SHALL TOOLS GMBH BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 29 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 30 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 31 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 32 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 33 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34 */ 35/*- 36 * Written by Paul Popelka (paulp@uts.amdahl.com) 37 * 38 * You can do anything you want with this software, just don't say you wrote 39 * it, and don't remove this notice. 40 * 41 * This software is provided "as is". 42 * 43 * The author supplies this software to be publicly redistributed on the 44 * understanding that the author is not responsible for the correct 45 * functioning of this software in any circumstances and is not liable for 46 * any damages caused by this software. 47 * 48 * October 1992 49 */ 50 51/* 52 * kernel include files. 53 */ 54#include <sys/param.h> 55#include <sys/systm.h> 56#include <sys/buf.h> 57#include <sys/mount.h> /* to define statfs structure */ 58#include <sys/vnode.h> /* to define vattr structure */ 59 60/* 61 * msdosfs include files. 62 */ 63#include <fs/msdosfs/bpb.h> 64#include <fs/msdosfs/msdosfsmount.h> 65#include <fs/msdosfs/direntry.h> 66#include <fs/msdosfs/denode.h> 67#include <fs/msdosfs/fat.h> 68 69/* 70 * Fat cache stats. 71 */ 72static int fc_fileextends; /* # of file extends */ 73static int fc_lfcempty; /* # of time last file cluster cache entry 74 * was empty */ 75static int fc_bmapcalls; /* # of times pcbmap was called */ 76 77#define LMMAX 20 78static int fc_lmdistance[LMMAX];/* counters for how far off the last 79 * cluster mapped entry was. */ 80static int fc_largedistance; /* off by more than LMMAX */ 81static int fc_wherefrom, fc_whereto, fc_lastclust; 82static int pm_fatblocksize; 83 84static int chainalloc(struct msdosfsmount *pmp, u_long start, 85 u_long count, u_long fillwith, u_long *retcluster, 86 u_long *got); 87static int chainlength(struct msdosfsmount *pmp, u_long start, 88 u_long count); 89static void fatblock(struct msdosfsmount *pmp, u_long ofs, u_long *bnp, 90 u_long *sizep, u_long *bop); 91static int fatchain(struct msdosfsmount *pmp, u_long start, u_long count, 92 u_long fillwith); 93static void fc_lookup(struct denode *dep, u_long findcn, u_long *frcnp, 94 u_long *fsrcnp); 95static void updatefats(struct msdosfsmount *pmp, struct buf *bp, 96 u_long fatbn); 97static __inline void 98 usemap_alloc(struct msdosfsmount *pmp, u_long cn); 99static __inline void 100 usemap_free(struct msdosfsmount *pmp, u_long cn); 101 102static void 103fatblock(pmp, ofs, bnp, sizep, bop) 104 struct msdosfsmount *pmp; 105 u_long ofs; 106 u_long *bnp; 107 u_long *sizep; 108 u_long *bop; 109{ 110 u_long bn, size; 111 112 bn = ofs / pmp->pm_fatblocksize * pmp->pm_fatblocksec; 113 size = min(pmp->pm_fatblocksec, pmp->pm_FATsecs - bn) 114 * DEV_BSIZE; 115 bn += pmp->pm_fatblk + pmp->pm_curfat * pmp->pm_FATsecs; 116 117 if (bnp) 118 *bnp = bn; 119 if (sizep) 120 *sizep = size; 121 if (bop) 122 *bop = ofs % pmp->pm_fatblocksize; 123 pm_fatblocksize = pmp->pm_fatblocksize; 124} 125 126/* 127 * Map the logical cluster number of a file into a physical disk sector 128 * that is filesystem relative. 129 * 130 * dep - address of denode representing the file of interest 131 * findcn - file relative cluster whose filesystem relative cluster number 132 * and/or block number are/is to be found 133 * bnp - address of where to place the filesystem relative block number. 134 * If this pointer is null then don't return this quantity. 135 * cnp - address of where to place the filesystem relative cluster number. 136 * If this pointer is null then don't return this quantity. 137 * 138 * NOTE: Either bnp or cnp must be non-null. 139 * This function has one side effect. If the requested file relative cluster 140 * is beyond the end of file, then the actual number of clusters in the file 141 * is returned in *cnp. This is useful for determining how long a directory is. 142 * If cnp is null, nothing is returned. 143 */ 144int 145pcbmap(dep, findcn, bnp, cnp, sp) 146 struct denode *dep; 147 u_long findcn; /* file relative cluster to get */ 148 daddr_t *bnp; /* returned filesys relative blk number */ 149 u_long *cnp; /* returned cluster number */ 150 int *sp; /* returned block size */ 151{ 152 int error; 153 u_long i; 154 u_long cn; 155 u_long prevcn = 0; /* XXX: prevcn could be used unititialized */ 156 u_long byteoffset; 157 u_long bn; 158 u_long bo; 159 struct buf *bp = NULL; 160 u_long bp_bn = -1; 161 struct msdosfsmount *pmp = dep->de_pmp; 162 u_long bsize; 163 164 fc_bmapcalls++; 165 166 /* 167 * If they don't give us someplace to return a value then don't 168 * bother doing anything. 169 */ 170 if (bnp == NULL && cnp == NULL && sp == NULL) 171 return (0); 172 173 cn = dep->de_StartCluster; 174 /* 175 * The "file" that makes up the root directory is contiguous, 176 * permanently allocated, of fixed size, and is not made up of 177 * clusters. If the cluster number is beyond the end of the root 178 * directory, then return the number of clusters in the file. 179 */ 180 if (cn == MSDOSFSROOT) { 181 if (dep->de_Attributes & ATTR_DIRECTORY) { 182 if (de_cn2off(pmp, findcn) >= dep->de_FileSize) { 183 if (cnp) 184 *cnp = de_bn2cn(pmp, pmp->pm_rootdirsize); 185 return (E2BIG); 186 } 187 if (bnp) 188 *bnp = pmp->pm_rootdirblk + de_cn2bn(pmp, findcn); 189 if (cnp) 190 *cnp = MSDOSFSROOT; 191 if (sp) 192 *sp = min(pmp->pm_bpcluster, 193 dep->de_FileSize - de_cn2off(pmp, findcn)); 194 return (0); 195 } else { /* just an empty file */ 196 if (cnp) 197 *cnp = 0; 198 return (E2BIG); 199 } 200 } 201 202 /* 203 * All other files do I/O in cluster sized blocks 204 */ 205 if (sp) 206 *sp = pmp->pm_bpcluster; 207 208 /* 209 * Rummage around in the fat cache, maybe we can avoid tromping 210 * thru every fat entry for the file. And, keep track of how far 211 * off the cache was from where we wanted to be. 212 */ 213 i = 0; 214 fc_lookup(dep, findcn, &i, &cn); 215 if ((bn = findcn - i) >= LMMAX) { 216 fc_largedistance++; 217 fc_wherefrom = i; 218 fc_whereto = findcn; 219 fc_lastclust = dep->de_fc[FC_LASTFC].fc_frcn; 220 } else 221 fc_lmdistance[bn]++; 222 223 /* 224 * Handle all other files or directories the normal way. 225 */ 226 for (; i < findcn; i++) { 227 /* 228 * Stop with all reserved clusters, not just with EOF. 229 */ 230 if ((cn | ~pmp->pm_fatmask) >= CLUST_RSRVD) 231 goto hiteof; 232 byteoffset = FATOFS(pmp, cn); 233 fatblock(pmp, byteoffset, &bn, &bsize, &bo); 234 if (bn != bp_bn) { 235 if (bp) 236 brelse(bp); 237 error = bread(pmp->pm_devvp, bn, bsize, NOCRED, &bp); 238 if (error) { 239 brelse(bp); 240 return (error); 241 } 242 bp_bn = bn; 243 } 244 prevcn = cn; 245 if (bo >= bsize) { 246 if (bp) 247 brelse(bp); 248 return (EIO); 249 } 250 if (FAT32(pmp)) 251 cn = getulong(&bp->b_data[bo]); 252 else 253 cn = getushort(&bp->b_data[bo]); 254 if (FAT12(pmp) && (prevcn & 1)) 255 cn >>= 4; 256 cn &= pmp->pm_fatmask; 257 258 /* 259 * Force the special cluster numbers 260 * to be the same for all cluster sizes 261 * to let the rest of msdosfs handle 262 * all cases the same. 263 */ 264 if ((cn | ~pmp->pm_fatmask) >= CLUST_RSRVD) 265 cn |= ~pmp->pm_fatmask; 266 } 267 268 if (!MSDOSFSEOF(pmp, cn)) { 269 if (bp) 270 brelse(bp); 271 if (bnp) 272 *bnp = cntobn(pmp, cn); 273 if (cnp) 274 *cnp = cn; 275 fc_setcache(dep, FC_LASTMAP, i, cn); 276 return (0); 277 } 278 279hiteof:; 280 if (cnp) 281 *cnp = i; 282 if (bp) 283 brelse(bp); 284 /* update last file cluster entry in the fat cache */ 285 fc_setcache(dep, FC_LASTFC, i - 1, prevcn); 286 return (E2BIG); 287} 288 289/* 290 * Find the closest entry in the fat cache to the cluster we are looking 291 * for. 292 */ 293static void 294fc_lookup(dep, findcn, frcnp, fsrcnp) 295 struct denode *dep; 296 u_long findcn; 297 u_long *frcnp; 298 u_long *fsrcnp; 299{ 300 int i; 301 u_long cn; 302 struct fatcache *closest = 0; 303 304 for (i = 0; i < FC_SIZE; i++) { 305 cn = dep->de_fc[i].fc_frcn; 306 if (cn != FCE_EMPTY && cn <= findcn) { 307 if (closest == 0 || cn > closest->fc_frcn) 308 closest = &dep->de_fc[i]; 309 } 310 } 311 if (closest) { 312 *frcnp = closest->fc_frcn; 313 *fsrcnp = closest->fc_fsrcn; 314 } 315} 316 317/* 318 * Purge the fat cache in denode dep of all entries relating to file 319 * relative cluster frcn and beyond. 320 */ 321void 322fc_purge(dep, frcn) 323 struct denode *dep; 324 u_int frcn; 325{ 326 int i; 327 struct fatcache *fcp; 328 329 fcp = dep->de_fc; 330 for (i = 0; i < FC_SIZE; i++, fcp++) { 331 if (fcp->fc_frcn >= frcn) 332 fcp->fc_frcn = FCE_EMPTY; 333 } 334} 335 336/* 337 * Update the fat. 338 * If mirroring the fat, update all copies, with the first copy as last. 339 * Else update only the current fat (ignoring the others). 340 * 341 * pmp - msdosfsmount structure for filesystem to update 342 * bp - addr of modified fat block 343 * fatbn - block number relative to begin of filesystem of the modified fat block. 344 */ 345static void 346updatefats(pmp, bp, fatbn) 347 struct msdosfsmount *pmp; 348 struct buf *bp; 349 u_long fatbn; 350{ 351 int i; 352 struct buf *bpn; 353 354#ifdef MSDOSFS_DEBUG 355 printf("updatefats(pmp %p, bp %p, fatbn %lu)\n", pmp, bp, fatbn); 356#endif 357 358 /* 359 * If we have an FSInfo block, update it. 360 */ 361 if (pmp->pm_fsinfo) { 362 u_long cn = pmp->pm_nxtfree; 363 364 if (pmp->pm_freeclustercount 365 && (pmp->pm_inusemap[cn / N_INUSEBITS] 366 & (1 << (cn % N_INUSEBITS)))) { 367 /* 368 * The cluster indicated in FSInfo isn't free 369 * any longer. Got get a new free one. 370 */ 371 for (cn = 0; cn < pmp->pm_maxcluster; cn += N_INUSEBITS) 372 if (pmp->pm_inusemap[cn / N_INUSEBITS] != (u_int)-1) 373 break; 374 pmp->pm_nxtfree = cn 375 + ffs(pmp->pm_inusemap[cn / N_INUSEBITS] 376 ^ (u_int)-1) - 1; 377 } 378 if (bread(pmp->pm_devvp, pmp->pm_fsinfo, pmp->pm_BytesPerSec, 379 NOCRED, &bpn) != 0) { 380 /* 381 * Ignore the error, but turn off FSInfo update for the future. 382 */ 383 pmp->pm_fsinfo = 0; 384 brelse(bpn); 385 } else { 386 struct fsinfo *fp = (struct fsinfo *)bpn->b_data; 387 388 putulong(fp->fsinfree, pmp->pm_freeclustercount); 389 putulong(fp->fsinxtfree, pmp->pm_nxtfree); 390 if (pmp->pm_flags & MSDOSFSMNT_WAITONFAT) 391 bwrite(bpn); 392 else 393 bdwrite(bpn); 394 } 395 } 396 397 if (pmp->pm_flags & MSDOSFS_FATMIRROR) { 398 /* 399 * Now copy the block(s) of the modified fat to the other copies of 400 * the fat and write them out. This is faster than reading in the 401 * other fats and then writing them back out. This could tie up 402 * the fat for quite a while. Preventing others from accessing it. 403 * To prevent us from going after the fat quite so much we use 404 * delayed writes, unless they specfied "synchronous" when the 405 * filesystem was mounted. If synch is asked for then use 406 * bwrite()'s and really slow things down. 407 */ 408 for (i = 1; i < pmp->pm_FATs; i++) { 409 fatbn += pmp->pm_FATsecs; 410 /* getblk() never fails */ 411 bpn = getblk(pmp->pm_devvp, fatbn, bp->b_bcount, 412 0, 0, 0); 413 bcopy(bp->b_data, bpn->b_data, bp->b_bcount); 414 if (pmp->pm_flags & MSDOSFSMNT_WAITONFAT) 415 bwrite(bpn); 416 else 417 bdwrite(bpn); 418 } 419 } 420 421 /* 422 * Write out the first (or current) fat last. 423 */ 424 if (pmp->pm_flags & MSDOSFSMNT_WAITONFAT) 425 bwrite(bp); 426 else 427 bdwrite(bp); 428 /* 429 * Maybe update fsinfo sector here? 430 */ 431} 432 433/* 434 * Updating entries in 12 bit fats is a pain in the butt. 435 * 436 * The following picture shows where nibbles go when moving from a 12 bit 437 * cluster number into the appropriate bytes in the FAT. 438 * 439 * byte m byte m+1 byte m+2 440 * +----+----+ +----+----+ +----+----+ 441 * | 0 1 | | 2 3 | | 4 5 | FAT bytes 442 * +----+----+ +----+----+ +----+----+ 443 * 444 * +----+----+----+ +----+----+----+ 445 * | 3 0 1 | | 4 5 2 | 446 * +----+----+----+ +----+----+----+ 447 * cluster n cluster n+1 448 * 449 * Where n is even. m = n + (n >> 2) 450 * 451 */ 452static __inline void 453usemap_alloc(pmp, cn) 454 struct msdosfsmount *pmp; 455 u_long cn; 456{ 457 458 pmp->pm_inusemap[cn / N_INUSEBITS] |= 1 << (cn % N_INUSEBITS); 459 pmp->pm_freeclustercount--; 460} 461 462static __inline void 463usemap_free(pmp, cn) 464 struct msdosfsmount *pmp; 465 u_long cn; 466{ 467 468 pmp->pm_freeclustercount++; 469 pmp->pm_inusemap[cn / N_INUSEBITS] &= ~(1 << (cn % N_INUSEBITS)); 470} 471 472int 473clusterfree(pmp, cluster, oldcnp) 474 struct msdosfsmount *pmp; 475 u_long cluster; 476 u_long *oldcnp; 477{ 478 int error; 479 u_long oldcn; 480 481 usemap_free(pmp, cluster); 482 error = fatentry(FAT_GET_AND_SET, pmp, cluster, &oldcn, MSDOSFSFREE); 483 if (error) { 484 usemap_alloc(pmp, cluster); 485 return (error); 486 } 487 /* 488 * If the cluster was successfully marked free, then update 489 * the count of free clusters, and turn off the "allocated" 490 * bit in the "in use" cluster bit map. 491 */ 492 if (oldcnp) 493 *oldcnp = oldcn; 494 return (0); 495} 496 497/* 498 * Get or Set or 'Get and Set' the cluster'th entry in the fat. 499 * 500 * function - whether to get or set a fat entry 501 * pmp - address of the msdosfsmount structure for the filesystem 502 * whose fat is to be manipulated. 503 * cn - which cluster is of interest 504 * oldcontents - address of a word that is to receive the contents of the 505 * cluster'th entry if this is a get function 506 * newcontents - the new value to be written into the cluster'th element of 507 * the fat if this is a set function. 508 * 509 * This function can also be used to free a cluster by setting the fat entry 510 * for a cluster to 0. 511 * 512 * All copies of the fat are updated if this is a set function. NOTE: If 513 * fatentry() marks a cluster as free it does not update the inusemap in 514 * the msdosfsmount structure. This is left to the caller. 515 */ 516int 517fatentry(function, pmp, cn, oldcontents, newcontents) 518 int function; 519 struct msdosfsmount *pmp; 520 u_long cn; 521 u_long *oldcontents; 522 u_long newcontents; 523{ 524 int error; 525 u_long readcn; 526 u_long bn, bo, bsize, byteoffset; 527 struct buf *bp; 528 529#ifdef MSDOSFS_DEBUG 530 printf("fatentry(func %d, pmp %p, clust %lu, oldcon %p, newcon %lx)\n", 531 function, pmp, cn, oldcontents, newcontents); 532#endif 533 534#ifdef DIAGNOSTIC 535 /* 536 * Be sure they asked us to do something. 537 */ 538 if ((function & (FAT_SET | FAT_GET)) == 0) { 539 printf("fatentry(): function code doesn't specify get or set\n"); 540 return (EINVAL); 541 } 542 543 /* 544 * If they asked us to return a cluster number but didn't tell us 545 * where to put it, give them an error. 546 */ 547 if ((function & FAT_GET) && oldcontents == NULL) { 548 printf("fatentry(): get function with no place to put result\n"); 549 return (EINVAL); 550 } 551#endif 552 553 /* 554 * Be sure the requested cluster is in the filesystem. 555 */ 556 if (cn < CLUST_FIRST || cn > pmp->pm_maxcluster) 557 return (EINVAL); 558 559 byteoffset = FATOFS(pmp, cn); 560 fatblock(pmp, byteoffset, &bn, &bsize, &bo); 561 error = bread(pmp->pm_devvp, bn, bsize, NOCRED, &bp); 562 if (error) { 563 brelse(bp); 564 return (error); 565 } 566 567 if (function & FAT_GET) { 568 if (FAT32(pmp)) 569 readcn = getulong(&bp->b_data[bo]); 570 else 571 readcn = getushort(&bp->b_data[bo]); 572 if (FAT12(pmp) & (cn & 1)) 573 readcn >>= 4; 574 readcn &= pmp->pm_fatmask; 575 /* map reserved fat entries to same values for all fats */ 576 if ((readcn | ~pmp->pm_fatmask) >= CLUST_RSRVD) 577 readcn |= ~pmp->pm_fatmask; 578 *oldcontents = readcn; 579 } 580 if (function & FAT_SET) { 581 switch (pmp->pm_fatmask) { 582 case FAT12_MASK: 583 readcn = getushort(&bp->b_data[bo]); 584 if (cn & 1) { 585 readcn &= 0x000f; 586 readcn |= newcontents << 4; 587 } else { 588 readcn &= 0xf000; 589 readcn |= newcontents & 0xfff; 590 } 591 putushort(&bp->b_data[bo], readcn); 592 break; 593 case FAT16_MASK: 594 putushort(&bp->b_data[bo], newcontents); 595 break; 596 case FAT32_MASK: 597 /* 598 * According to spec we have to retain the 599 * high order bits of the fat entry. 600 */ 601 readcn = getulong(&bp->b_data[bo]); 602 readcn &= ~FAT32_MASK; 603 readcn |= newcontents & FAT32_MASK; 604 putulong(&bp->b_data[bo], readcn); 605 break; 606 } 607 updatefats(pmp, bp, bn); 608 bp = NULL; 609 pmp->pm_fmod = 1; 610 } 611 if (bp) 612 brelse(bp); 613 return (0); 614} 615 616/* 617 * Update a contiguous cluster chain 618 * 619 * pmp - mount point 620 * start - first cluster of chain 621 * count - number of clusters in chain 622 * fillwith - what to write into fat entry of last cluster 623 */ 624static int 625fatchain(pmp, start, count, fillwith) 626 struct msdosfsmount *pmp; 627 u_long start; 628 u_long count; 629 u_long fillwith; 630{ 631 int error; 632 u_long bn, bo, bsize, byteoffset, readcn, newc; 633 struct buf *bp; 634 635#ifdef MSDOSFS_DEBUG 636 printf("fatchain(pmp %p, start %lu, count %lu, fillwith %lx)\n", 637 pmp, start, count, fillwith); 638#endif 639 /* 640 * Be sure the clusters are in the filesystem. 641 */ 642 if (start < CLUST_FIRST || start + count - 1 > pmp->pm_maxcluster) 643 return (EINVAL); 644 645 while (count > 0) { 646 byteoffset = FATOFS(pmp, start); 647 fatblock(pmp, byteoffset, &bn, &bsize, &bo); 648 error = bread(pmp->pm_devvp, bn, bsize, NOCRED, &bp); 649 if (error) { 650 brelse(bp); 651 return (error); 652 } 653 while (count > 0) { 654 start++; 655 newc = --count > 0 ? start : fillwith; 656 switch (pmp->pm_fatmask) { 657 case FAT12_MASK: 658 readcn = getushort(&bp->b_data[bo]); 659 if (start & 1) { 660 readcn &= 0xf000; 661 readcn |= newc & 0xfff; 662 } else { 663 readcn &= 0x000f; 664 readcn |= newc << 4; 665 } 666 putushort(&bp->b_data[bo], readcn); 667 bo++; 668 if (!(start & 1)) 669 bo++; 670 break; 671 case FAT16_MASK: 672 putushort(&bp->b_data[bo], newc); 673 bo += 2; 674 break; 675 case FAT32_MASK: 676 readcn = getulong(&bp->b_data[bo]); 677 readcn &= ~pmp->pm_fatmask; 678 readcn |= newc & pmp->pm_fatmask; 679 putulong(&bp->b_data[bo], readcn); 680 bo += 4; 681 break; 682 } 683 if (bo >= bsize) 684 break; 685 } 686 updatefats(pmp, bp, bn); 687 } 688 pmp->pm_fmod = 1; 689 return (0); 690} 691 692/* 693 * Check the length of a free cluster chain starting at start. 694 * 695 * pmp - mount point 696 * start - start of chain 697 * count - maximum interesting length 698 */ 699static int 700chainlength(pmp, start, count) 701 struct msdosfsmount *pmp; 702 u_long start; 703 u_long count; 704{ 705 u_long idx, max_idx; 706 u_int map; 707 u_long len; 708 709 max_idx = pmp->pm_maxcluster / N_INUSEBITS; 710 idx = start / N_INUSEBITS; 711 start %= N_INUSEBITS; 712 map = pmp->pm_inusemap[idx]; 713 map &= ~((1 << start) - 1); 714 if (map) { 715 len = ffs(map) - 1 - start; 716 return (len > count ? count : len); 717 } 718 len = N_INUSEBITS - start; 719 if (len >= count) 720 return (count); 721 while (++idx <= max_idx) { 722 if (len >= count) 723 break; 724 map = pmp->pm_inusemap[idx]; 725 if (map) { 726 len += ffs(map) - 1; 727 break; 728 } 729 len += N_INUSEBITS; 730 } 731 return (len > count ? count : len); 732} 733 734/* 735 * Allocate contigous free clusters. 736 * 737 * pmp - mount point. 738 * start - start of cluster chain. 739 * count - number of clusters to allocate. 740 * fillwith - put this value into the fat entry for the 741 * last allocated cluster. 742 * retcluster - put the first allocated cluster's number here. 743 * got - how many clusters were actually allocated. 744 */ 745static int 746chainalloc(pmp, start, count, fillwith, retcluster, got) 747 struct msdosfsmount *pmp; 748 u_long start; 749 u_long count; 750 u_long fillwith; 751 u_long *retcluster; 752 u_long *got; 753{ 754 int error; 755 u_long cl, n; 756 757 for (cl = start, n = count; n-- > 0;) 758 usemap_alloc(pmp, cl++); 759 760 error = fatchain(pmp, start, count, fillwith); 761 if (error != 0) 762 return (error); 763#ifdef MSDOSFS_DEBUG 764 printf("clusteralloc(): allocated cluster chain at %lu (%lu clusters)\n", 765 start, count); 766#endif 767 if (retcluster) 768 *retcluster = start; 769 if (got) 770 *got = count; 771 pmp->pm_nxtfree = start + count; 772 if (pmp->pm_nxtfree > pmp->pm_maxcluster) 773 pmp->pm_nxtfree = CLUST_FIRST; 774 return (0); 775} 776 777/* 778 * Allocate contiguous free clusters. 779 * 780 * pmp - mount point. 781 * start - preferred start of cluster chain. 782 * count - number of clusters requested. 783 * fillwith - put this value into the fat entry for the 784 * last allocated cluster. 785 * retcluster - put the first allocated cluster's number here. 786 * got - how many clusters were actually allocated. 787 */ 788int 789clusteralloc(pmp, start, count, fillwith, retcluster, got) 790 struct msdosfsmount *pmp; 791 u_long start; 792 u_long count; 793 u_long fillwith; 794 u_long *retcluster; 795 u_long *got; 796{ 797 u_long idx; 798 u_long len, newst, foundl, cn, l; 799 u_long foundcn = 0; /* XXX: foundcn could be used unititialized */ 800 u_int map; 801 802#ifdef MSDOSFS_DEBUG 803 printf("clusteralloc(): find %lu clusters\n",count); 804#endif 805 if (start) { 806 if ((len = chainlength(pmp, start, count)) >= count) 807 return (chainalloc(pmp, start, count, fillwith, retcluster, got)); 808 } else 809 len = 0; 810 811 newst = pmp->pm_nxtfree; 812 foundl = 0; 813 814 for (cn = newst; cn <= pmp->pm_maxcluster;) { 815 idx = cn / N_INUSEBITS; 816 map = pmp->pm_inusemap[idx]; 817 map |= (1 << (cn % N_INUSEBITS)) - 1; 818 if (map != (u_int)-1) { 819 cn = idx * N_INUSEBITS + ffs(map^(u_int)-1) - 1; 820 if ((l = chainlength(pmp, cn, count)) >= count) 821 return (chainalloc(pmp, cn, count, fillwith, retcluster, got)); 822 if (l > foundl) { 823 foundcn = cn; 824 foundl = l; 825 } 826 cn += l + 1; 827 continue; 828 } 829 cn += N_INUSEBITS - cn % N_INUSEBITS; 830 } 831 for (cn = 0; cn < newst;) { 832 idx = cn / N_INUSEBITS; 833 map = pmp->pm_inusemap[idx]; 834 map |= (1 << (cn % N_INUSEBITS)) - 1; 835 if (map != (u_int)-1) { 836 cn = idx * N_INUSEBITS + ffs(map^(u_int)-1) - 1; 837 if ((l = chainlength(pmp, cn, count)) >= count) 838 return (chainalloc(pmp, cn, count, fillwith, retcluster, got)); 839 if (l > foundl) { 840 foundcn = cn; 841 foundl = l; 842 } 843 cn += l + 1; 844 continue; 845 } 846 cn += N_INUSEBITS - cn % N_INUSEBITS; 847 } 848 849 if (!foundl) 850 return (ENOSPC); 851 852 if (len) 853 return (chainalloc(pmp, start, len, fillwith, retcluster, got)); 854 else 855 return (chainalloc(pmp, foundcn, foundl, fillwith, retcluster, got)); 856} 857 858 859/* 860 * Free a chain of clusters. 861 * 862 * pmp - address of the msdosfs mount structure for the filesystem 863 * containing the cluster chain to be freed. 864 * startcluster - number of the 1st cluster in the chain of clusters to be 865 * freed. 866 */ 867int 868freeclusterchain(pmp, cluster) 869 struct msdosfsmount *pmp; 870 u_long cluster; 871{ 872 int error; 873 struct buf *bp = NULL; 874 u_long bn, bo, bsize, byteoffset; 875 u_long readcn, lbn = -1; 876 877 while (cluster >= CLUST_FIRST && cluster <= pmp->pm_maxcluster) { 878 byteoffset = FATOFS(pmp, cluster); 879 fatblock(pmp, byteoffset, &bn, &bsize, &bo); 880 if (lbn != bn) { 881 if (bp) 882 updatefats(pmp, bp, lbn); 883 error = bread(pmp->pm_devvp, bn, bsize, NOCRED, &bp); 884 if (error) { 885 brelse(bp); 886 return (error); 887 } 888 lbn = bn; 889 } 890 usemap_free(pmp, cluster); 891 switch (pmp->pm_fatmask) { 892 case FAT12_MASK: 893 readcn = getushort(&bp->b_data[bo]); 894 if (cluster & 1) { 895 cluster = readcn >> 4; 896 readcn &= 0x000f; 897 readcn |= MSDOSFSFREE << 4; 898 } else { 899 cluster = readcn; 900 readcn &= 0xf000; 901 readcn |= MSDOSFSFREE & 0xfff; 902 } 903 putushort(&bp->b_data[bo], readcn); 904 break; 905 case FAT16_MASK: 906 cluster = getushort(&bp->b_data[bo]); 907 putushort(&bp->b_data[bo], MSDOSFSFREE); 908 break; 909 case FAT32_MASK: 910 cluster = getulong(&bp->b_data[bo]); 911 putulong(&bp->b_data[bo], 912 (MSDOSFSFREE & FAT32_MASK) | (cluster & ~FAT32_MASK)); 913 break; 914 } 915 cluster &= pmp->pm_fatmask; 916 if ((cluster | ~pmp->pm_fatmask) >= CLUST_RSRVD) 917 cluster |= pmp->pm_fatmask; 918 } 919 if (bp) 920 updatefats(pmp, bp, bn); 921 return (0); 922} 923 924/* 925 * Read in fat blocks looking for free clusters. For every free cluster 926 * found turn off its corresponding bit in the pm_inusemap. 927 */ 928int 929fillinusemap(pmp) 930 struct msdosfsmount *pmp; 931{ 932 struct buf *bp = NULL; 933 u_long cn, readcn; 934 int error; 935 u_long bn, bo, bsize, byteoffset; 936 937 /* 938 * Mark all clusters in use, we mark the free ones in the fat scan 939 * loop further down. 940 */ 941 for (cn = 0; cn < (pmp->pm_maxcluster + N_INUSEBITS) / N_INUSEBITS; cn++) 942 pmp->pm_inusemap[cn] = (u_int)-1; 943 944 /* 945 * Figure how many free clusters are in the filesystem by ripping 946 * through the fat counting the number of entries whose content is 947 * zero. These represent free clusters. 948 */ 949 pmp->pm_freeclustercount = 0; 950 for (cn = CLUST_FIRST; cn <= pmp->pm_maxcluster; cn++) { 951 byteoffset = FATOFS(pmp, cn); 952 bo = byteoffset % pmp->pm_fatblocksize; 953 if (!bo || !bp) { 954 /* Read new FAT block */ 955 if (bp) 956 brelse(bp); 957 fatblock(pmp, byteoffset, &bn, &bsize, NULL); 958 error = bread(pmp->pm_devvp, bn, bsize, NOCRED, &bp); 959 if (error) { 960 brelse(bp); 961 return (error); 962 } 963 } 964 if (FAT32(pmp)) 965 readcn = getulong(&bp->b_data[bo]); 966 else 967 readcn = getushort(&bp->b_data[bo]); 968 if (FAT12(pmp) && (cn & 1)) 969 readcn >>= 4; 970 readcn &= pmp->pm_fatmask; 971 972 if (readcn == 0) 973 usemap_free(pmp, cn); 974 } 975 brelse(bp); 976 return (0); 977} 978 979/* 980 * Allocate a new cluster and chain it onto the end of the file. 981 * 982 * dep - the file to extend 983 * count - number of clusters to allocate 984 * bpp - where to return the address of the buf header for the first new 985 * file block 986 * ncp - where to put cluster number of the first newly allocated cluster 987 * If this pointer is 0, do not return the cluster number. 988 * flags - see fat.h 989 * 990 * NOTE: This function is not responsible for turning on the DE_UPDATE bit of 991 * the de_flag field of the denode and it does not change the de_FileSize 992 * field. This is left for the caller to do. 993 */ 994int 995extendfile(dep, count, bpp, ncp, flags) 996 struct denode *dep; 997 u_long count; 998 struct buf **bpp; 999 u_long *ncp; 1000 int flags; 1001{ 1002 int error; 1003 u_long frcn; 1004 u_long cn, got; 1005 struct msdosfsmount *pmp = dep->de_pmp; 1006 struct buf *bp; 1007 daddr_t blkno; 1008 1009 /* 1010 * Don't try to extend the root directory 1011 */ 1012 if (dep->de_StartCluster == MSDOSFSROOT 1013 && (dep->de_Attributes & ATTR_DIRECTORY)) { 1014 printf("extendfile(): attempt to extend root directory\n"); 1015 return (ENOSPC); 1016 } 1017 1018 /* 1019 * If the "file's last cluster" cache entry is empty, and the file 1020 * is not empty, then fill the cache entry by calling pcbmap(). 1021 */ 1022 fc_fileextends++; 1023 if (dep->de_fc[FC_LASTFC].fc_frcn == FCE_EMPTY && 1024 dep->de_StartCluster != 0) { 1025 fc_lfcempty++; 1026 error = pcbmap(dep, 0xffff, 0, &cn, 0); 1027 /* we expect it to return E2BIG */ 1028 if (error != E2BIG) 1029 return (error); 1030 } 1031 1032 fc_last_to_nexttolast(dep); 1033 while (count > 0) { 1034 /* 1035 * Allocate a new cluster chain and cat onto the end of the 1036 * file. * If the file is empty we make de_StartCluster point 1037 * to the new block. Note that de_StartCluster being 0 is 1038 * sufficient to be sure the file is empty since we exclude 1039 * attempts to extend the root directory above, and the root 1040 * dir is the only file with a startcluster of 0 that has 1041 * blocks allocated (sort of). 1042 */ 1043 if (dep->de_StartCluster == 0) 1044 cn = 0; 1045 else 1046 cn = dep->de_fc[FC_LASTFC].fc_fsrcn + 1; 1047 error = clusteralloc(pmp, cn, count, CLUST_EOFE, &cn, &got); 1048 if (error) 1049 return (error); 1050 1051 count -= got; 1052 1053 /* 1054 * Give them the filesystem relative cluster number if they want 1055 * it. 1056 */ 1057 if (ncp) { 1058 *ncp = cn; 1059 ncp = NULL; 1060 } 1061 1062 if (dep->de_StartCluster == 0) { 1063 dep->de_StartCluster = cn; 1064 frcn = 0; 1065 } else { 1066 error = fatentry(FAT_SET, pmp, 1067 dep->de_fc[FC_LASTFC].fc_fsrcn, 1068 0, cn); 1069 if (error) { 1070 clusterfree(pmp, cn, NULL); 1071 return (error); 1072 } 1073 frcn = dep->de_fc[FC_LASTFC].fc_frcn + 1; 1074 } 1075 1076 /* 1077 * Update the "last cluster of the file" entry in the denode's fat 1078 * cache. 1079 */ 1080 fc_setcache(dep, FC_LASTFC, frcn + got - 1, cn + got - 1); 1081 1082 if (flags & DE_CLEAR) { 1083 while (got-- > 0) { 1084 /* 1085 * Get the buf header for the new block of the file. 1086 */ 1087 if (dep->de_Attributes & ATTR_DIRECTORY) 1088 bp = getblk(pmp->pm_devvp, 1089 cntobn(pmp, cn++), 1090 pmp->pm_bpcluster, 0, 0, 0); 1091 else { 1092 bp = getblk(DETOV(dep), 1093 de_cn2bn(pmp, frcn++), 1094 pmp->pm_bpcluster, 0, 0, 0); 1095 /* 1096 * Do the bmap now, as in msdosfs_write 1097 */ 1098 if (pcbmap(dep, 1099 de_bn2cn(pmp, bp->b_lblkno), 1100 &blkno, 0, 0)) 1101 bp->b_blkno = -1; 1102 if (bp->b_blkno == -1) 1103 panic("extendfile: pcbmap"); 1104 else 1105 bp->b_blkno = blkno; 1106 } 1107 vfs_bio_clrbuf(bp); 1108 if (bpp) { 1109 *bpp = bp; 1110 bpp = NULL; 1111 } else 1112 bdwrite(bp); 1113 } 1114 } 1115 } 1116 1117 return (0); 1118} 1119 1120/*- 1121 * Routine to mark a FAT16 or FAT32 volume as "clean" or "dirty" by 1122 * manipulating the upper bit of the FAT entry for cluster 1. Note that 1123 * this bit is not defined for FAT12 volumes, which are always assumed to 1124 * be dirty. 1125 * 1126 * The fatentry() routine only works on cluster numbers that a file could 1127 * occupy, so it won't manipulate the entry for cluster 1. So we have to do 1128 * it here. The code was stolen from fatentry() and tailored for cluster 1. 1129 * 1130 * Inputs: 1131 * pmp The MS-DOS volume to mark 1132 * dirty Non-zero if the volume should be marked dirty; zero if it 1133 * should be marked clean 1134 * 1135 * Result: 1136 * 0 Success 1137 * EROFS Volume is read-only 1138 * ? (other errors from called routines) 1139 */ 1140int 1141markvoldirty(struct msdosfsmount *pmp, int dirty) 1142{ 1143 struct buf *bp; 1144 u_long bn, bo, bsize, byteoffset, fatval; 1145 int error; 1146 1147 /* 1148 * FAT12 does not support a "clean" bit, so don't do anything for 1149 * FAT12. 1150 */ 1151 if (FAT12(pmp)) 1152 return (0); 1153 1154 /* Can't change the bit on a read-only filesystem. */ 1155 if (pmp->pm_flags & MSDOSFSMNT_RONLY) 1156 return (EROFS); 1157 1158 /* 1159 * Fetch the block containing the FAT entry. It is given by the 1160 * pseudo-cluster 1. 1161 */ 1162 byteoffset = FATOFS(pmp, 1); 1163 fatblock(pmp, byteoffset, &bn, &bsize, &bo); 1164 error = bread(pmp->pm_devvp, bn, bsize, NOCRED, &bp); 1165 if (error) { 1166 brelse(bp); 1167 return (error); 1168 } 1169 1170 /* 1171 * Get the current value of the FAT entry and set/clear the relevant 1172 * bit. Dirty means clear the "clean" bit; clean means set the 1173 * "clean" bit. 1174 */ 1175 if (FAT32(pmp)) { 1176 /* FAT32 uses bit 27. */ 1177 fatval = getulong(&bp->b_data[bo]); 1178 if (dirty) 1179 fatval &= 0xF7FFFFFF; 1180 else 1181 fatval |= 0x08000000; 1182 putulong(&bp->b_data[bo], fatval); 1183 } else { 1184 /* Must be FAT16; use bit 15. */ 1185 fatval = getushort(&bp->b_data[bo]); 1186 if (dirty) 1187 fatval &= 0x7FFF; 1188 else 1189 fatval |= 0x8000; 1190 putushort(&bp->b_data[bo], fatval); 1191 } 1192 1193 /* Write out the modified FAT block synchronously. */ 1194 return (bwrite(bp)); 1195} 1196