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