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