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