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