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