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