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