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