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