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