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