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