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