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