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