1 /*
2 * Written by Paul Popelka (paulp@uts.amdahl.com)
3 *
4 * You can do anything you want with this software,
5 * just don't say you wrote it,
6 * and don't remove this notice.
7 *
8 * This software is provided "as is".
9 *
10 * The author supplies this software to be publicly
11 * redistributed on the understanding that the author
12 * is not responsible for the correct functioning of
13 * this software in any circumstances and is not liable
14 * for any damages caused by this software.
15 *
16 * October 1992
17 *
18 * $Id: dosfs_fat.c,v 1.1 94/10/19 23:46:48 bill Exp $
19 */
20
21 /*
22 * kernel include files.
23 */
24 #include "sys/param.h"
25 #include "sys/mount.h" /* to define statfs structure */
26 #include "systm.h"
27 #include "buf.h"
28 #include "sys/file.h"
29 #include "sys/time.h"
30 #include "ucred.h"
31 #include "uio.h"
32 #include "namei.h"
33 #include "vnode.h" /* to define vattr structure */
34 #include "sys/errno.h"
35
36 /*
37 * pcfs include files.
38 */
39 #include "bpb.h"
40 #include "dosfs_mount.h"
41 #include "direntry.h"
42 #include "denode.h"
43 #include "fat.h"
44
45 /*
46 * Fat cache stats.
47 */
48 int fc_fileextends; /* # of file extends */
49 int fc_lfcempty; /* # of time last file cluster cache entry
50 * was empty */
51 int fc_bmapcalls; /* # of times pcbmap was called */
52 #define LMMAX 20
53 int fc_lmdistance[LMMAX]; /* counters for how far off the last cluster
54 * mapped entry was. */
55 int fc_largedistance; /* off by more than LMMAX */
56
57 /* Byte offset in FAT on filesystem pmp, cluster cn */
58 #define FATOFS(pmp, cn) (FAT12(pmp) ? (cn) * 3 / 2 : (cn) * 2)
59
60
fatblock(pmp,ofs,bnp,sizep,bop)61 static void fatblock (pmp, ofs, bnp, sizep, bop)
62 struct pcfsmount *pmp;
63 u_long ofs;
64 u_long *bnp;
65 u_long *sizep;
66 u_long *bop;
67 {
68 u_long bn, size;
69
70 bn = ofs / pmp->pm_fatblocksize * pmp->pm_fatblocksec;
71 size = min (pmp->pm_fatblocksec, pmp->pm_FATsecs - bn)
72 * pmp->pm_BytesPerSec;
73 bn += pmp->pm_fatblk;
74 if (bnp)
75 *bnp = bn;
76 if (sizep)
77 *sizep = size;
78 if (bop)
79 *bop = ofs % pmp->pm_fatblocksize;
80 }
81
82 /*
83 * Map the logical cluster number of a file into
84 * a physical disk sector that is filesystem relative.
85 * dep - address of denode representing the file of interest
86 * findcn - file relative cluster whose filesystem relative
87 * cluster number and/or block number are/is to be found
88 * bnp - address of where to place the file system relative
89 * block number. If this pointer is null then don't return
90 * this quantity.
91 * cnp - address of where to place the file system relative
92 * cluster number. If this pointer is null then don't return
93 * this quantity.
94 * NOTE:
95 * Either bnp or cnp must be non-null.
96 * This function has one side effect. If the requested
97 * file relative cluster is beyond the end of file, then
98 * the actual number of clusters in the file is returned
99 * in *cnp. This is useful for determining how long a
100 * directory is. If cnp is null, nothing is returned.
101 */
102 int
pcbmap(dep,findcn,bnp,cnp)103 pcbmap(dep, findcn, bnp, cnp)
104 struct denode *dep;
105 u_long findcn; /* file relative cluster to get */
106 daddr_t *bnp; /* returned filesys relative blk number */
107 u_long *cnp; /* returned cluster number */
108 {
109 int error;
110 u_long i;
111 u_long cn;
112 u_long prevcn;
113 u_long byteoffset;
114 u_long bn;
115 u_long bo;
116 struct buf *bp = NULL;
117 u_long bp_bn = -1;
118 struct pcfsmount *pmp = dep->de_pmp;
119 u_long bsize;
120 int fat12 = FAT12(pmp); /* 12 bit fat */
121
122 fc_bmapcalls++;
123
124 /*
125 * If they don't give us someplace to return a value
126 * then don't bother doing anything.
127 */
128 if (bnp == NULL && cnp == NULL)
129 return 0;
130
131 cn = dep->de_StartCluster;
132 /*
133 * The "file" that makes up the root directory is contiguous,
134 * permanently allocated, of fixed size, and is not made up
135 * of clusters. If the cluster number is beyond the end of
136 * the root directory, then return the number of clusters in
137 * the file.
138 */
139 if (cn == PCFSROOT) {
140 if (dep->de_Attributes & ATTR_DIRECTORY) {
141 if (findcn * pmp->pm_SectPerClust > pmp->pm_rootdirsize) {
142 if (cnp)
143 *cnp = pmp->pm_rootdirsize / pmp->pm_SectPerClust;
144 return E2BIG;
145 }
146 if (bnp)
147 *bnp = pmp->pm_rootdirblk + (findcn * pmp->pm_SectPerClust);
148 if (cnp)
149 *cnp = PCFSROOT;
150 return 0;
151 }
152 else { /* just an empty file */
153 if (cnp)
154 *cnp = 0;
155 return E2BIG;
156 }
157 }
158
159 /*
160 * Rummage around in the fat cache, maybe we can avoid
161 * tromping thru every fat entry for the file.
162 * And, keep track of how far off the cache was from
163 * where we wanted to be.
164 */
165 i = 0;
166 fc_lookup(dep, findcn, &i, &cn);
167 if ((bn = findcn - i) >= LMMAX)
168 fc_largedistance++;
169 else
170 fc_lmdistance[bn]++;
171
172 /*
173 * Handle all other files or directories the normal way.
174 */
175 for (; i < findcn; i++) {
176 if (PCFSEOF(cn))
177 goto hiteof;
178 byteoffset = FATOFS(pmp, cn);
179 fatblock(pmp, byteoffset, &bn, &bsize, &bo);
180 if (bn != bp_bn) {
181 if (bp)
182 brelse(bp);
183 error = bread(pmp->pm_devvp, bn, bsize, NOCRED, &bp);
184 if (error)
185 return error;
186 bp_bn = bn;
187 }
188 prevcn = cn;
189 cn = getushort(&bp->b_un.b_addr[bo]);
190 if (fat12) {
191 if (prevcn & 1)
192 cn >>= 4;
193 cn &= 0x0fff;
194 /*
195 * Force the special cluster numbers in the range
196 * 0x0ff0-0x0fff to be the same as for 16 bit cluster
197 * numbers to let the rest of pcfs think it is always
198 * dealing with 16 bit fats.
199 */
200 if ((cn & 0x0ff0) == 0x0ff0)
201 cn |= 0xf000;
202 }
203 }
204
205 if (!PCFSEOF(cn)) {
206 if (bp)
207 brelse(bp);
208 if (bnp)
209 *bnp = cntobn(pmp, cn);
210 if (cnp)
211 *cnp = cn;
212 fc_setcache(dep, FC_LASTMAP, i, cn);
213 return 0;
214 }
215
216 hiteof:;
217 if (cnp)
218 *cnp = i;
219 if (bp)
220 brelse(bp);
221 /* update last file cluster entry in the fat cache */
222 fc_setcache(dep, FC_LASTFC, i-1, prevcn);
223 return E2BIG;
224 }
225
226 /*
227 * Find the closest entry in the fat cache to the
228 * cluster we are looking for.
229 */
230 fc_lookup(dep, findcn, frcnp, fsrcnp)
231 struct denode *dep;
232 u_long findcn;
233 u_long *frcnp;
234 u_long *fsrcnp;
235 {
236 int i;
237 u_long cn;
238 struct fatcache *closest = 0;
239
240 for (i = 0; i < FC_SIZE; i++) {
241 cn = dep->de_fc[i].fc_frcn;
242 if (cn != FCE_EMPTY && cn <= findcn) {
243 if (closest == 0 || cn > closest->fc_frcn)
244 closest = &dep->de_fc[i];
245 }
246 }
247 if (closest) {
248 *frcnp = closest->fc_frcn;
249 *fsrcnp = closest->fc_fsrcn;
250 }
251 }
252
253 /*
254 * Purge the fat cache in denode dep of all entries
255 * relating to file relative cluster frcn and beyond.
256 */
257 fc_purge(dep, frcn)
258 struct denode *dep;
259 u_int frcn;
260 {
261 int i;
262 struct fatcache *fcp;
263
264 fcp = dep->de_fc;
265 for (i = 0; i < FC_SIZE; i++, fcp++) {
266 if (fcp->fc_frcn != FCE_EMPTY && fcp->fc_frcn >= frcn)
267 fcp->fc_frcn = FCE_EMPTY;
268 }
269 }
270
271 /*
272 * Once the first fat is updated the other copies of
273 * the fat must also be updated. This function does
274 * this.
275 * pmp - pcfsmount structure for filesystem to update
276 * bp - addr of modified fat block
277 * fatbn - block number relative to begin of filesystem
278 * of the modified fat block.
279 */
280 void
updateotherfats(pmp,bp,fatbn)281 updateotherfats(pmp, bp, fatbn)
282 struct pcfsmount *pmp;
283 struct buf *bp;
284 u_long fatbn;
285 {
286 int i;
287 struct buf *bpn;
288
289 #if defined(PCFSDEBUG)
290 printf("updateotherfats(pmp %08x, bp %08x, fatbn %d)\n",
291 pmp, bp, fatbn);
292 #endif /* defined(PCFSDEBUG) */
293
294 /*
295 * Now copy the block(s) of the modified fat to the other
296 * copies of the fat and write them out. This is faster
297 * than reading in the other fats and then writing them
298 * back out. This could tie up the fat for quite a while.
299 * Preventing others from accessing it. To prevent us
300 * from going after the fat quite so much we use delayed
301 * writes, unless they specfied "synchronous" when the
302 * filesystem was mounted. If synch is asked for then
303 * use bwrite()'s and really slow things down.
304 */
305 for (i = 1; i < pmp->pm_FATs; i++) {
306 fatbn += pmp->pm_FATsecs;
307 /* getblk() never fails */
308 bpn = getblk(pmp->pm_devvp, fatbn, bp->b_bcount);
309 (void)memcpy(bpn->b_un.b_addr, bp->b_un.b_addr, bp->b_bcount);
310 /*bcopy(bp->b_un.b_addr, bpn->b_un.b_addr,
311 bp->b_bcount);*/
312 if (pmp->pm_waitonfat)
313 bwrite(bpn);
314 else
315 bdwrite(bpn, bpn->b_vp);
316 }
317 }
318
319 /*
320 * Updating entries in 12 bit fats is a pain in the butt.
321 *
322 * The following picture shows where nibbles go when
323 * moving from a 12 bit cluster number into the appropriate
324 * bytes in the FAT.
325 *
326 * byte m byte m+1 byte m+2
327 * +----+----+ +----+----+ +----+----+
328 * | 0 1 | | 2 3 | | 4 5 | FAT bytes
329 * +----+----+ +----+----+ +----+----+
330 *
331 * +----+----+----+ +----+----+----+
332 * | 3 0 1 | | 4 5 2 |
333 * +----+----+----+ +----+----+----+
334 * cluster n cluster n+1
335 *
336 * Where n is even.
337 * m = n + (n >> 2)
338 *
339 * (Function no longer used)
340 */
341
342
343 extern inline void
usemap_alloc(struct pcfsmount * pmp,u_long cn)344 usemap_alloc (struct pcfsmount *pmp, u_long cn)
345 {
346 pmp->pm_inusemap[cn / 8] |= 1 << (cn % 8);
347 pmp->pm_freeclustercount--;
348 /* This assumes that the lowest available cluster was allocated */
349 pmp->pm_lookhere = cn + 1;
350 }
351
352 extern inline void
usemap_free(struct pcfsmount * pmp,u_long cn)353 usemap_free (struct pcfsmount *pmp, u_long cn)
354 {
355 pmp->pm_freeclustercount++;
356 pmp->pm_inusemap[cn / 8] &= ~(1 << (cn % 8));
357 if (pmp->pm_lookhere > cn)
358 pmp->pm_lookhere = cn;
359 }
360
361 int
clusterfree(pmp,cluster,oldcnp)362 clusterfree(pmp, cluster, oldcnp)
363 struct pcfsmount *pmp;
364 u_long cluster;
365 u_long *oldcnp;
366 {
367 int error;
368 u_long oldcn;
369
370 error = fatentry(FAT_GET_AND_SET, pmp, cluster, &oldcn, PCFSFREE);
371 if (error == 0) {
372 /*
373 * If the cluster was successfully marked free, then update the count of
374 * free clusters, and turn off the "allocated" bit in the
375 * "in use" cluster bit map.
376 */
377 usemap_free(pmp, cluster);
378 if (oldcnp)
379 *oldcnp = oldcn;
380 }
381 return error;
382 }
383
384 /*
385 * Get or Set or 'Get and Set' the cluster'th entry in the
386 * fat.
387 * function - whether to get or set a fat entry
388 * pmp - address of the pcfsmount structure for the
389 * filesystem whose fat is to be manipulated.
390 * cluster - which cluster is of interest
391 * oldcontents - address of a word that is to receive
392 * the contents of the cluster'th entry if this is
393 * a get function
394 * newcontents - the new value to be written into the
395 * cluster'th element of the fat if this is a set
396 * function.
397 *
398 * This function can also be used to free a cluster
399 * by setting the fat entry for a cluster to 0.
400 *
401 * All copies of the fat are updated if this is a set
402 * function.
403 * NOTE:
404 * If fatentry() marks a cluster as free it does not
405 * update the inusemap in the pcfsmount structure.
406 * This is left to the caller.
407 */
408 int
fatentry(function,pmp,cn,oldcontents,newcontents)409 fatentry(function, pmp, cn, oldcontents, newcontents)
410 int function;
411 struct pcfsmount *pmp;
412 u_long cn;
413 u_long *oldcontents;
414 u_long newcontents;
415 {
416 int error;
417 u_long readcn;
418 u_long bn, bo, bsize, byteoffset;
419 struct buf *bp;
420 /*printf("fatentry(func %d, pmp %08x, clust %d, oldcon %08x, newcon %d)\n",
421 function, pmp, cluster, oldcontents, newcontents);*/
422
423 #ifdef DIAGNOSTIC
424 /*
425 * Be sure they asked us to do something.
426 */
427 if ((function & (FAT_SET | FAT_GET)) == 0) {
428 printf("fatentry(): function code doesn't specify get or set\n");
429 return EINVAL;
430 }
431
432 /*
433 * If they asked us to return a cluster number
434 * but didn't tell us where to put it, give them
435 * an error.
436 */
437 if ((function & FAT_GET) && oldcontents == NULL) {
438 printf("fatentry(): get function with no place to put result\n");
439 return EINVAL;
440 }
441 #endif
442
443 /*
444 * Be sure the requested cluster is in the filesystem.
445 */
446 if (cn < CLUST_FIRST || cn > pmp->pm_maxcluster)
447 return EINVAL;
448
449 byteoffset = FATOFS(pmp, cn);
450 fatblock(pmp, byteoffset, &bn, &bsize, &bo);
451 error = bread(pmp->pm_devvp, bn, bsize, NOCRED, &bp);
452 if (function & FAT_GET) {
453 readcn = getushort(&bp->b_un.b_addr[bo]);
454 if (FAT12(pmp)) {
455 if (cn & 1)
456 readcn >>= 4;
457 readcn &= 0x0fff;
458 /* map certain 12 bit fat entries to 16 bit */
459 if ((readcn & 0x0ff0) == 0x0ff0)
460 readcn |= 0xf000;
461 }
462 *oldcontents = readcn;
463 }
464 if (function & FAT_SET) {
465 if (FAT12(pmp)) {
466 readcn = getushort(&bp->b_un.b_addr[bo]);
467 if (cn & 1) {
468 readcn &= 0x000f;
469 readcn |= (newcontents << 4);
470 }
471 else {
472 readcn &= 0xf000;
473 readcn |= (newcontents << 0);
474 }
475 putushort(&bp->b_un.b_addr[bo], readcn);
476 }
477 else
478 putushort(&bp->b_un.b_addr[bo], newcontents);
479 updateotherfats(pmp, bp, bn);
480 /*
481 * Write out the first fat last.
482 */
483 if (pmp->pm_waitonfat)
484 bwrite(bp);
485 else
486 bdwrite(bp, bp->b_vp);
487 bp = NULL;
488 pmp->pm_fmod++;
489 }
490 if (bp)
491 brelse(bp);
492 return 0;
493 }
494
495 /*
496 * Allocate a free cluster.
497 * pmp -
498 * retcluster - put the allocated cluster's number here.
499 * fillwith - put this value into the fat entry for the
500 * allocated cluster.
501 */
502 int
clusteralloc(pmp,retcluster,fillwith)503 clusteralloc(pmp, retcluster, fillwith)
504 struct pcfsmount *pmp;
505 u_long *retcluster;
506 u_long fillwith;
507 {
508 int error;
509 u_long cn;
510 u_long idx, max_idx, bit, map;
511
512 max_idx = pmp->pm_maxcluster / 8;
513 for (idx = pmp->pm_lookhere / 8; idx <= max_idx; idx++) {
514 map = pmp->pm_inusemap[idx];
515 if (map != 0xff) {
516 for (bit = 0; bit < 8; bit++) {
517 if ((map & (1 << bit)) == 0) {
518 cn = idx * 8 + bit;
519 goto found_one;
520 }
521 }
522 }
523 }
524 return ENOSPC;
525
526 found_one:;
527 error = fatentry(FAT_SET, pmp, cn, 0, fillwith);
528 if (error == 0) {
529 usemap_alloc(pmp, cn);
530 *retcluster = cn;
531 }
532 #if defined(PCFSDEBUG)
533 printf("clusteralloc(): allocated cluster %d\n", cn);
534 #endif /* defined(PCFSDEBUG) */
535 return error;
536 }
537
538 /*
539 * Free a chain of clusters.
540 * pmp - address of the pcfs mount structure for the
541 * filesystem containing the cluster chain to be freed.
542 * startcluster - number of the 1st cluster in the chain
543 * of clusters to be freed.
544 */
545 int
freeclusterchain(pmp,startcluster)546 freeclusterchain(pmp, startcluster)
547 struct pcfsmount *pmp;
548 u_long startcluster;
549 {
550 u_long nextcluster;
551 int error = 0;
552
553 while (startcluster >= CLUST_FIRST && startcluster <= pmp->pm_maxcluster) {
554 error = clusterfree(pmp, startcluster, &nextcluster);
555 if (error) {
556 printf("freeclusterchain(): free failed, cluster %d\n",
557 startcluster);
558 break;
559 }
560 startcluster = nextcluster;
561 }
562 return error;
563 }
564
565 /*
566 * Read in fat blocks looking for free clusters.
567 * For every free cluster found turn off its
568 * corresponding bit in the pm_inusemap.
569 */
570 int
fillinusemap(pmp)571 fillinusemap(pmp)
572 struct pcfsmount *pmp;
573 {
574 struct buf *bp = NULL;
575 u_long cn, readcn;
576 int error;
577 int fat12 = FAT12(pmp);
578 u_long bn, bo, bsize, byteoffset;
579
580 /*
581 * Mark all clusters in use, we mark the free ones in the
582 * fat scan loop further down.
583 */
584 for (cn = 0; cn < (pmp->pm_maxcluster >> 3) + 1; cn++)
585 pmp->pm_inusemap[cn] = 0xff;
586
587 /*
588 * Figure how many free clusters are in the filesystem
589 * by ripping thougth the fat counting the number of
590 * entries whose content is zero. These represent free
591 * clusters.
592 */
593 pmp->pm_freeclustercount = 0;
594 pmp->pm_lookhere = pmp->pm_maxcluster + 1;
595 for (cn = CLUST_FIRST; cn <= pmp->pm_maxcluster; cn++) {
596 byteoffset = FATOFS(pmp, cn);
597 bo = byteoffset % pmp->pm_fatblocksize;
598 if (!bo || !bp) {
599 /* Read new FAT block */
600 if (bp)
601 brelse(bp);
602 fatblock(pmp, byteoffset, &bn, &bsize, NULL);
603 error = bread(pmp->pm_devvp, bn, bsize, NOCRED, &bp);
604 if (error)
605 return error;
606 }
607 readcn = getushort(&bp->b_un.b_addr[bo]);
608 if (fat12) {
609 if (cn & 1)
610 readcn >>= 4;
611 readcn &= 0x0fff;
612 }
613
614 if (readcn == 0)
615 usemap_free(pmp, cn);
616 }
617 brelse(bp);
618 return 0;
619 }
620
621 /*
622 * Allocate a new cluster and chain it onto the end of the
623 * file.
624 * dep - the file to extend
625 * bpp - where to return the address of the buf header for the
626 * new file block
627 * ncp - where to put cluster number of the newly allocated file block
628 * If this pointer is 0, do not return the cluster number.
629 *
630 * NOTE:
631 * This function is not responsible for turning on the DEUPD
632 * bit if the de_flag field of the denode and it does not
633 * change the de_FileSize field. This is left for the caller
634 * to do.
635 */
636 int
extendfile(dep,bpp,ncp)637 extendfile(dep, bpp, ncp)
638 struct denode *dep;
639 struct buf **bpp;
640 u_int *ncp;
641 {
642 int error = 0;
643 u_long frcn;
644 u_long cn;
645 struct pcfsmount *pmp = dep->de_pmp;
646
647 /*
648 * Don't try to extend the root directory
649 */
650 if (DETOV(dep)->v_flag & VROOT) {
651 printf("extendfile(): attempt to extend root directory\n");
652 return ENOSPC;
653 }
654
655 /*
656 * If the "file's last cluster" cache entry is empty,
657 * and the file is not empty,
658 * then fill the cache entry by calling pcbmap().
659 */
660 fc_fileextends++;
661 if (dep->de_fc[FC_LASTFC].fc_frcn == FCE_EMPTY &&
662 dep->de_StartCluster != 0) {
663 fc_lfcempty++;
664 error = pcbmap(dep, 0xffff, 0, &cn);
665 /* we expect it to return E2BIG */
666 if (error != E2BIG)
667 return error;
668 error = 0;
669 }
670
671 /*
672 * Allocate another cluster and chain onto the end of the file.
673 * If the file is empty we make de_StartCluster point to the
674 * new block. Note that de_StartCluster being 0 is sufficient
675 * to be sure the file is empty since we exclude attempts to
676 * extend the root directory above, and the root dir is the
677 * only file with a startcluster of 0 that has blocks allocated
678 * (sort of).
679 */
680 if (error = clusteralloc(pmp, &cn, CLUST_EOFE))
681 return error;
682 if (dep->de_StartCluster == 0) {
683 dep->de_StartCluster = cn;
684 frcn = 0;
685 } else {
686 error = fatentry(FAT_SET, pmp, dep->de_fc[FC_LASTFC].fc_fsrcn,
687 0, cn);
688 if (error) {
689 clusterfree(pmp, cn, NULL);
690 return error;
691 }
692
693 frcn = dep->de_fc[FC_LASTFC].fc_frcn + 1;
694 }
695
696 /*
697 * Update the "last cluster of the file" entry in the denode's
698 * fat cache.
699 */
700 fc_setcache(dep, FC_LASTFC, frcn, cn);
701
702 /*
703 * Get the buf header for the new block of the file.
704 */
705 if (dep->de_Attributes & ATTR_DIRECTORY) {
706 *bpp = getblk(pmp->pm_devvp, cntobn(pmp, cn),
707 pmp->pm_bpcluster);
708 } else {
709 *bpp = getblk(DETOV(dep), frcn,
710 pmp->pm_bpcluster);
711 }
712 clrbuf(*bpp);
713
714 /*
715 * Give them the filesystem relative cluster number
716 * if they want it.
717 */
718 if (ncp)
719 *ncp = cn;
720 return 0;
721 }
722