1/* 2 * Copyright (c) 2000-2011,2013 Apple Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23/* $FreeBSD: src/sys/msdosfs/msdosfs_fat.c,v 1.24 2000/05/05 09:58:35 phk Exp $ */ 24/* $NetBSD: msdosfs_fat.c,v 1.28 1997/11/17 15:36:49 ws Exp $ */ 25 26/*- 27 * Copyright (C) 1994, 1995, 1997 Wolfgang Solfrank. 28 * Copyright (C) 1994, 1995, 1997 TooLs GmbH. 29 * All rights reserved. 30 * Original code by Paul Popelka (paulp@uts.amdahl.com) (see below). 31 * 32 * Redistribution and use in source and binary forms, with or without 33 * modification, are permitted provided that the following conditions 34 * are met: 35 * 1. Redistributions of source code must retain the above copyright 36 * notice, this list of conditions and the following disclaimer. 37 * 2. Redistributions in binary form must reproduce the above copyright 38 * notice, this list of conditions and the following disclaimer in the 39 * documentation and/or other materials provided with the distribution. 40 * 3. All advertising materials mentioning features or use of this software 41 * must display the following acknowledgement: 42 * This product includes software developed by TooLs GmbH. 43 * 4. The name of TooLs GmbH may not be used to endorse or promote products 44 * derived from this software without specific prior written permission. 45 * 46 * THIS SOFTWARE IS PROVIDED BY TOOLS GMBH ``AS IS'' AND ANY EXPRESS OR 47 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 48 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 49 * IN NO EVENT SHALL TOOLS GMBH BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 50 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 51 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 52 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 53 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 54 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 55 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 56 */ 57/* 58 * Written by Paul Popelka (paulp@uts.amdahl.com) 59 * 60 * You can do anything you want with this software, just don't say you wrote 61 * it, and don't remove this notice. 62 * 63 * This software is provided "as is". 64 * 65 * The author supplies this software to be publicly redistributed on the 66 * understanding that the author is not responsible for the correct 67 * functioning of this software in any circumstances and is not liable for 68 * any damages caused by this software. 69 * 70 * October 1992 71 */ 72 73/* 74 * kernel include files. 75 */ 76#include <sys/param.h> 77#include <sys/systm.h> 78#include <sys/buf.h> 79#include <sys/mount.h> /* to define statfs structure */ 80#include <sys/vnode.h> /* to define vattr structure */ 81#include <sys/ubc.h> 82#include <mach/boolean.h> 83#include <libkern/OSBase.h> 84#include <libkern/OSAtomic.h> 85#include <kern/thread_call.h> 86#include <libkern/OSMalloc.h> 87#include <IOKit/IOTypes.h> 88 89/* 90 * msdosfs include files. 91 */ 92#include "bpb.h" 93#include "msdosfsmount.h" 94#include "direntry.h" 95#include "denode.h" 96#include "fat.h" 97#include "msdosfs_kdebug.h" 98 99uint32_t msdosfs_meta_delay = 50; /* in milliseconds */ 100 101#ifndef DEBUG 102#define DEBUG 0 103#endif 104 105/* 106 * The fs private data used with FAT vnodes. 107 */ 108struct msdosfs_fat_node { 109 struct msdosfsmount *pmp; 110 u_int32_t start_block; /* device block number of first sector */ 111 u_int32_t file_size; /* number of bytes covered by this vnode */ 112}; 113 114/* 115 * Internal routines 116 */ 117int msdosfs_fat_cache_flush(struct msdosfsmount *pmp, int ioflags); 118int msdosfs_fatentry_internal(int function, struct msdosfsmount *pmp, uint32_t cn, 119 uint32_t *oldcontents, uint32_t newcontents); 120int msdosfs_clusteralloc_internal(struct msdosfsmount *pmp, uint32_t start, uint32_t count, 121 uint32_t fillwith, uint32_t *retcluster, uint32_t *got); 122int msdosfs_chainalloc(struct msdosfsmount *pmp, uint32_t start, uint32_t count, 123 uint32_t fillwith, uint32_t *retcluster, uint32_t *got); 124uint32_t msdosfs_chainlength(struct msdosfsmount *pmp, uint32_t start, uint32_t count); 125int msdosfs_fatchain(struct msdosfsmount *pmp, uint32_t start, uint32_t count, uint32_t fillwith); 126int msdosfs_count_free_clusters(struct msdosfsmount *pmp); 127void *msdosfs_fat_map(struct msdosfsmount *pmp, u_int32_t cn, u_int32_t *offp, u_int32_t *sizep, int *error_out); 128void msdosfs_meta_flush_internal(struct msdosfsmount *pmp, int sync); 129 130/* 131 * vnode operations for the FAT vnode 132 */ 133typedef int vnop_t(void *); 134int msdosfs_fat_pagein(struct vnop_pagein_args *ap); 135int msdosfs_fat_pageout(struct vnop_pageout_args *ap); 136int msdosfs_fat_strategy(struct vnop_strategy_args *ap); 137int msdosfs_fat_blockmap(struct vnop_blockmap_args *ap); 138int msdosfs_fat_fsync(struct vnop_fsync_args *ap); 139int msdosfs_fat_inactive(struct vnop_inactive_args *ap); 140int msdosfs_fat_reclaim(struct vnop_reclaim_args *ap); 141 142int msdosfs_fat_pagein(struct vnop_pagein_args *ap) 143{ 144 struct msdosfs_fat_node *node = vnode_fsnode(ap->a_vp); 145 146 return cluster_pagein(ap->a_vp, ap->a_pl, ap->a_pl_offset, ap->a_f_offset, 147 (int)ap->a_size, node->file_size, ap->a_flags); 148} 149 150int msdosfs_fat_pageout(struct vnop_pageout_args *ap) 151{ 152 struct msdosfs_fat_node *node = vnode_fsnode(ap->a_vp); 153 154 return cluster_pageout(ap->a_vp, ap->a_pl, ap->a_pl_offset, ap->a_f_offset, 155 (int)ap->a_size, node->file_size, ap->a_flags); 156} 157 158int msdosfs_fat_strategy(struct vnop_strategy_args *ap) 159{ 160 struct msdosfs_fat_node *node = vnode_fsnode(buf_vnode(ap->a_bp)); 161 162 return buf_strategy(node->pmp->pm_devvp, ap); 163} 164 165int msdosfs_fat_blockmap(struct vnop_blockmap_args *ap) 166{ 167 struct msdosfs_fat_node *node = vnode_fsnode(ap->a_vp); 168 169 if (ap->a_bpn == NULL) 170 return 0; 171 172 /* 173 * Return the physical sector number corresponding to ap->a_foffset, 174 * where a_foffset is relative to the start of the first copy of the FAT. 175 */ 176 *ap->a_bpn = node->start_block + (ap->a_foffset / node->pmp->pm_BlockSize); 177 178 /* Return the number of contiguous bytes, up to ap->a_size */ 179 if (ap->a_run) 180 { 181 if (ap->a_foffset + ap->a_size > node->file_size) 182 *ap->a_run = (size_t)(node->file_size - ap->a_foffset); 183 else 184 *ap->a_run = ap->a_size; 185 } 186 187 return 0; 188} 189 190int msdosfs_fat_fsync(struct vnop_fsync_args *ap) 191{ 192 int error = 0; 193 int ioflags = 0; 194 vnode_t vp = ap->a_vp; 195 struct msdosfs_fat_node *node = vnode_fsnode(ap->a_vp); 196 struct msdosfsmount *pmp = node->pmp; 197 198 if (ap->a_waitfor == MNT_WAIT) 199 ioflags = IO_SYNC; 200 201 KERNEL_DEBUG_CONSTANT(MSDOSFS_FAT_FSYNC|DBG_FUNC_START, pmp, ioflags, 0, 0, 0); 202 203 if (pmp->pm_fat_flags & FAT_CACHE_DIRTY) 204 { 205 lck_mtx_lock(pmp->pm_fat_lock); 206 error = msdosfs_fat_cache_flush(pmp, ioflags); 207 lck_mtx_unlock(pmp->pm_fat_lock); 208 } 209 if (!error) 210 cluster_push(vp, ioflags); 211 212 KERNEL_DEBUG_CONSTANT(MSDOSFS_FAT_FSYNC|DBG_FUNC_END, error, 0, 0, 0, 0); 213 return error; 214} 215 216int msdosfs_fat_inactive(struct vnop_inactive_args *ap) 217{ 218 vnode_recycle(ap->a_vp); 219 return 0; 220} 221 222int msdosfs_fat_reclaim(struct vnop_reclaim_args *ap) 223{ 224 vnode_t vp = ap->a_vp; 225 struct msdosfs_fat_node *node = vnode_fsnode(vp); 226 227 vnode_clearfsnode(vp); 228 OSFree(node, sizeof(*node), msdosfs_malloc_tag); 229 return 0; 230} 231 232static int (**msdosfs_fat_vnodeop_p)(void *); 233static struct vnodeopv_entry_desc msdosfs_fat_vnodeop_entries[] = { 234 { &vnop_default_desc, (vnop_t *) vn_default_error }, 235 { &vnop_pagein_desc, (vnop_t *) msdosfs_fat_pagein }, 236 { &vnop_pageout_desc, (vnop_t *) msdosfs_fat_pageout }, 237 { &vnop_strategy_desc, (vnop_t *) msdosfs_fat_strategy }, 238 { &vnop_blockmap_desc, (vnop_t *) msdosfs_fat_blockmap }, 239 { &vnop_blktooff_desc, (vnop_t *) msdosfs_vnop_blktooff }, 240 { &vnop_offtoblk_desc, (vnop_t *) msdosfs_vnop_offtoblk }, 241 { &vnop_fsync_desc, (vnop_t *) msdosfs_fat_fsync }, 242 { &vnop_inactive_desc, (vnop_t *) msdosfs_fat_inactive }, 243 { &vnop_reclaim_desc, (vnop_t *) msdosfs_fat_reclaim }, 244 { &vnop_bwrite_desc, (vnop_t *) vn_bwrite }, 245 { NULL, NULL } 246}; 247 248__private_extern__ 249struct vnodeopv_desc msdosfs_fat_vnodeop_opv_desc = 250 { &msdosfs_fat_vnodeop_p, msdosfs_fat_vnodeop_entries }; 251 252int msdosfs_fat_init_vol(struct msdosfsmount *pmp) 253{ 254 errno_t error; 255 struct vnode_fsparam vfsp; 256 struct msdosfs_fat_node *node; 257 258 lck_mtx_lock(pmp->pm_fat_lock); 259 260 /* 261 * Create a vnode to use to access the active FAT. 262 */ 263 node = OSMalloc(sizeof(*node), msdosfs_malloc_tag); 264 if (node == NULL) 265 { 266 error = ENOMEM; 267 goto exit; 268 } 269 node->pmp = pmp; 270 node->start_block = pmp->pm_ResSectors * pmp->pm_BlocksPerSec; 271 node->file_size = pmp->pm_fat_bytes; 272 vfsp.vnfs_mp = pmp->pm_mountp; 273 vfsp.vnfs_vtype = VREG; 274 vfsp.vnfs_str = "msdosfs"; 275 vfsp.vnfs_dvp = NULL; 276 vfsp.vnfs_fsnode = node; 277 vfsp.vnfs_vops = msdosfs_fat_vnodeop_p; 278 vfsp.vnfs_markroot = 0; 279 vfsp.vnfs_marksystem = 1; 280 vfsp.vnfs_rdev = 0; 281 vfsp.vnfs_filesize = pmp->pm_fat_bytes; 282 vfsp.vnfs_cnp = NULL; 283 vfsp.vnfs_flags = VNFS_CANTCACHE; 284 error = vnode_create(VNCREATE_FLAVOR, VCREATESIZE, &vfsp, &pmp->pm_fat_active_vp); 285 if (error) 286 { 287 OSFree(node, sizeof(*node), msdosfs_malloc_tag); 288 goto exit; 289 } 290 vnode_ref(pmp->pm_fat_active_vp); 291 vnode_put(pmp->pm_fat_active_vp); 292 293 if (pmp->pm_flags & MSDOSFS_FATMIRROR) 294 { 295 /* 296 * Create a vnode to use to access the alternate FAT. 297 */ 298 node = OSMalloc(sizeof(*node), msdosfs_malloc_tag); 299 if (node == NULL) 300 { 301 error = ENOMEM; 302 goto exit; 303 } 304 node->pmp = pmp; 305 node->start_block = pmp->pm_ResSectors * pmp->pm_BlocksPerSec + pmp->pm_fat_bytes / pmp->pm_BlockSize; 306 node->file_size = (pmp->pm_FATs - 1) * pmp->pm_fat_bytes; 307 vfsp.vnfs_mp = pmp->pm_mountp; 308 vfsp.vnfs_vtype = VREG; 309 vfsp.vnfs_str = "msdosfs"; 310 vfsp.vnfs_dvp = NULL; 311 vfsp.vnfs_fsnode = node; 312 vfsp.vnfs_vops = msdosfs_fat_vnodeop_p; 313 vfsp.vnfs_markroot = 0; 314 vfsp.vnfs_marksystem = 1; 315 vfsp.vnfs_rdev = 0; 316 vfsp.vnfs_filesize = node->file_size; 317 vfsp.vnfs_cnp = NULL; 318 vfsp.vnfs_flags = VNFS_CANTCACHE; 319 error = vnode_create(VNCREATE_FLAVOR, VCREATESIZE, &vfsp, &pmp->pm_fat_mirror_vp); 320 if (error) 321 { 322 OSFree(node, sizeof(*node), msdosfs_malloc_tag); 323 goto exit; 324 } 325 vnode_ref(pmp->pm_fat_mirror_vp); 326 vnode_put(pmp->pm_fat_mirror_vp); 327 } 328 329 /* 330 * Initialize the cache for most recently used FAT block. 331 */ 332 pmp->pm_fat_cache = OSMalloc(pmp->pm_fatblocksize, msdosfs_malloc_tag); 333 if (pmp->pm_fat_cache == NULL) 334 { 335 error = ENOMEM; 336 goto exit; 337 } 338 pmp->pm_fat_cache_offset = -1; /* invalid; no cached content */ 339 pmp->pm_fat_flags = 0; /* Nothing is dirty yet */ 340 341 /* 342 * Allocate space for a list of free extents, used when searching for 343 * free space (especially when free space is highly fragmented). 344 */ 345 pmp->pm_free_extents = OSMalloc(PAGE_SIZE, msdosfs_malloc_tag); 346 if (pmp->pm_free_extents == NULL) 347 { 348 error = ENOMEM; 349 goto exit; 350 } 351 pmp->pm_free_extent_count = 0; 352 353 /* 354 * We need to read through the FAT to determine the number of free clusters. 355 */ 356 error = msdosfs_count_free_clusters(pmp); 357 358exit: 359 /* 360 * NOTE: All memory allocated above gets freed in msdosfs_fat_uninit_vol. 361 */ 362 lck_mtx_unlock(pmp->pm_fat_lock); 363 return error; 364} 365 366void msdosfs_fat_uninit_vol(struct msdosfsmount *pmp) 367{ 368 /* 369 * Try one last time to flush the FAT before we get rid of the FAT vnodes. 370 * 371 * During a force unmount, the FAT may be dirty, and the device already 372 * gone. In that case, the flush will fail, but we must mark the FAT as 373 * no longer dirty. If we don't, releasing the vnodes below will again 374 * try to flush the FAT, and will panic due to a NULL vnode pointer. 375 */ 376 if (pmp->pm_fat_flags & FAT_CACHE_DIRTY) 377 { 378 int error; 379 lck_mtx_lock(pmp->pm_fat_lock); 380 error = msdosfs_fat_cache_flush(pmp, IO_SYNC); 381 if (error) 382 printf("msdosfs_fat_uninit_vol: error %d from msdosfs_fat_cache_flush\n", error); 383 pmp->pm_fat_flags = 0; /* Ignore anything dirty or in need of update */ 384 lck_mtx_unlock(pmp->pm_fat_lock); 385 } 386 387 if (pmp->pm_fat_active_vp) 388 { 389 /* Would it be better to push async, then wait for writes to complete? */ 390 cluster_push(pmp->pm_fat_active_vp, IO_SYNC); 391 vnode_recycle(pmp->pm_fat_active_vp); 392 vnode_rele(pmp->pm_fat_active_vp); 393 pmp->pm_fat_active_vp = NULL; 394 } 395 396 if (pmp->pm_fat_mirror_vp) 397 { 398 cluster_push(pmp->pm_fat_mirror_vp, IO_SYNC); 399 vnode_recycle(pmp->pm_fat_mirror_vp); 400 vnode_rele(pmp->pm_fat_mirror_vp); 401 pmp->pm_fat_mirror_vp = NULL; 402 } 403 404 if (pmp->pm_fat_cache) 405 { 406 OSFree(pmp->pm_fat_cache, pmp->pm_fatblocksize, msdosfs_malloc_tag); 407 pmp->pm_fat_cache = NULL; 408 } 409 410 if (pmp->pm_free_extents) 411 { 412 OSFree(pmp->pm_free_extents, PAGE_SIZE, msdosfs_malloc_tag); 413 pmp->pm_free_extents = NULL; 414 pmp->pm_free_extent_count = 0; 415 } 416} 417 418 419 420/* 421 * Update the free cluster count and next free cluster number in the FSInfo 422 * sector of a FAT32 volume. This is called during VFS_SYNC. 423 */ 424int msdosfs_update_fsinfo(struct msdosfsmount *pmp, int waitfor, vfs_context_t context) 425{ 426 int error = 0; 427 buf_t bp; 428 struct fsinfo *fp; 429 430 KERNEL_DEBUG_CONSTANT(MSDOSFS_UPDATE_FSINFO|DBG_FUNC_START, pmp, waitfor, 0, 0, 0); 431 /* 432 * If we don't have an FSInfo sector, or if there has been no change 433 * to the FAT since the last FSInfo update, then there's nothing to do. 434 */ 435 if (pmp->pm_fsinfo_size == 0 || !(pmp->pm_fat_flags & FSINFO_DIRTY)) 436 { 437 goto done; 438 } 439 440 error = buf_meta_bread(pmp->pm_devvp, pmp->pm_fsinfo_sector, pmp->pm_fsinfo_size, 441 vfs_context_ucred(context), &bp); 442 if (error) 443 { 444 /* 445 * Turn off FSInfo update for the future. 446 */ 447 printf("msdosfs_update_fsinfo: error %d reading FSInfo\n", error); 448 pmp->pm_fsinfo_size = 0; 449 buf_brelse(bp); 450 } 451 else 452 { 453 fp = (struct fsinfo *) (buf_dataptr(bp) + pmp->pm_fsinfo_offset); 454 455 putuint32(fp->fsinfree, pmp->pm_freeclustercount); 456 putuint32(fp->fsinxtfree, pmp->pm_nxtfree); 457 if (waitfor || pmp->pm_flags & MSDOSFSMNT_WAITONFAT) 458 error = buf_bwrite(bp); 459 else 460 error = buf_bawrite(bp); 461 } 462 463 pmp->pm_fat_flags &= ~FSINFO_DIRTY; 464done: 465 KERNEL_DEBUG_CONSTANT(MSDOSFS_UPDATE_FSINFO|DBG_FUNC_END, error, 0, 0, 0, 0); 466 return error; 467} 468 469 470/* 471 * If the FAT cache is dirty, then write it back via Cluster I/O. 472 * 473 * NOTE: Cluster I/O will typically cache this write in UBC, so the write 474 * will not necessarily go to disk right away. You must explicitly fsync 475 * the vnode(s) to force changes to the media. 476 */ 477int msdosfs_fat_cache_flush(struct msdosfsmount *pmp, int ioflags) 478{ 479 int error = 0; 480 u_int32_t fat_file_size; 481 u_int32_t block_size; 482 uio_t uio; 483 484 KERNEL_DEBUG_CONSTANT(MSDOSFS_FAT_CACHE_FLUSH|DBG_FUNC_START, pmp, ioflags, 0, 0, 0); 485 486 if (DEBUG) lck_mtx_assert(pmp->pm_fat_lock, LCK_MTX_ASSERT_OWNED); 487 488 if ((pmp->pm_fat_flags & FAT_CACHE_DIRTY) == 0) 489 goto done; 490 491 fat_file_size = pmp->pm_fat_bytes; 492 block_size = pmp->pm_fatblocksize; 493 if (pmp->pm_fat_cache_offset + block_size > pmp->pm_fat_bytes) 494 block_size = pmp->pm_fat_bytes - pmp->pm_fat_cache_offset; 495 496 uio = uio_create(1, pmp->pm_fat_cache_offset, UIO_SYSSPACE, UIO_WRITE); 497 if (uio == NULL) 498 { 499 error = ENOMEM; 500 goto done; 501 } 502 uio_addiov(uio, CAST_USER_ADDR_T(pmp->pm_fat_cache), block_size); 503 error = cluster_write(pmp->pm_fat_active_vp, uio, fat_file_size, fat_file_size, 0, 0, ioflags); 504 if (!error) 505 pmp->pm_fat_flags &= ~FAT_CACHE_DIRTY; 506 507 /* 508 * If we're mirroring the FAT, then write to all of the other copies now. 509 * By definition, mirroring means that pmp->pm_curfat == 0, so we just 510 * need to loop over 1 .. maximum here. 511 */ 512 if (pmp->pm_flags & MSDOSFS_FATMIRROR) 513 { 514 int i; 515 516 fat_file_size = (pmp->pm_FATs - 1) * pmp->pm_fat_bytes; 517 for (i=0; i<pmp->pm_FATs-1; ++i) 518 { 519 uio_reset(uio, pmp->pm_fat_cache_offset + i * pmp->pm_fat_bytes, UIO_SYSSPACE, UIO_WRITE); 520 uio_addiov(uio, CAST_USER_ADDR_T(pmp->pm_fat_cache), block_size); 521 error = cluster_write(pmp->pm_fat_mirror_vp, uio, fat_file_size, fat_file_size, 0, 0, ioflags); 522 } 523 } 524 525 /* We're finally done with the uio */ 526 uio_free(uio); 527 528done: 529 KERNEL_DEBUG_CONSTANT(MSDOSFS_FAT_CACHE_FLUSH|DBG_FUNC_END, error, 0, 0, 0, 0); 530 return error; 531} 532 533 534/* 535 * Given a cluster number, bring the corresponding block of the FAT into 536 * the pm_fat_cache (after writing a dirty cache block, if needed). Returns 537 * a pointer to the given cluster's entry. 538 * 539 * Inputs: 540 * pmp 541 * cn 542 * 543 * Outputs (optional): 544 * offp Offset of entryp from start of FAT block, in bytes 545 * sizep Number of valid bytes in this block. For the last FAT block, 546 * this may be less than the block size (it will be the offset 547 * following the entry for the last cluster). 548 * 549 * Return value: Pointer to cluster cn's entry in the FAT block 550 */ 551void *msdosfs_fat_map(struct msdosfsmount *pmp, u_int32_t cn, u_int32_t *offp, u_int32_t *sizep, int *error_out) 552{ 553 int error = 0; 554 u_int32_t offset; 555 u_int32_t block_offset; 556 u_int32_t block_size; 557 558 KERNEL_DEBUG_CONSTANT(MSDOSFS_FAT_MAP|DBG_FUNC_START, pmp, cn, 0, 0, 0); 559 560 if (DEBUG) lck_mtx_assert(pmp->pm_fat_lock, LCK_MTX_ASSERT_OWNED); 561 562 offset = cn * pmp->pm_fatmult / pmp->pm_fatdiv; 563 block_offset = offset / pmp->pm_fatblocksize * pmp->pm_fatblocksize; /* Round to start of page */ 564 block_size = pmp->pm_fatblocksize; 565 if (block_offset + block_size > pmp->pm_fat_bytes) 566 block_size = pmp->pm_fat_bytes - block_offset; 567 568 if (pmp->pm_fat_cache_offset != block_offset) 569 { 570 uio_t uio; 571 572 if (pmp->pm_fat_flags & FAT_CACHE_DIRTY) 573 error = msdosfs_fat_cache_flush(pmp, 0); 574 575 if (!error) 576 { 577 pmp->pm_fat_cache_offset = block_offset; 578 uio = uio_create(1, block_offset, UIO_SYSSPACE, UIO_READ); 579 if (uio == NULL) 580 { 581 error = ENOMEM; 582 } 583 else 584 { 585 uio_addiov(uio, CAST_USER_ADDR_T(pmp->pm_fat_cache), block_size); 586 error = cluster_read(pmp->pm_fat_active_vp, uio, pmp->pm_fat_bytes, 0); 587 uio_free(uio); 588 } 589 } 590 } 591 592 offset -= block_offset; 593 594 if (offp) 595 *offp = offset; 596 597 if (sizep) 598 { 599 u_int32_t last_offset; 600 601 /* 602 * If this is the last block of the FAT, then constrain the size to the 603 * end of the entry for the last cluster. 604 */ 605 last_offset = (pmp->pm_maxcluster + 1) * pmp->pm_fatmult / pmp->pm_fatdiv; 606 if (last_offset - block_offset < block_size) 607 block_size = last_offset - block_offset; 608 *sizep = block_size; 609 } 610 611 if (error_out) 612 *error_out = error; 613 614 KERNEL_DEBUG_CONSTANT(MSDOSFS_FAT_MAP|DBG_FUNC_END, error, 0, 0, 0, 0); 615 616 if (error) 617 { 618 /* Invalidate the state of the FAT cache */ 619 pmp->pm_fat_cache_offset = -1; 620 pmp->pm_fat_flags &= ~FAT_CACHE_DIRTY; 621 return NULL; 622 } 623 624 return (char *) pmp->pm_fat_cache + offset; 625} 626 627 628/* 629 * Flush the primary/active copy of the FAT, and all directory blocks. 630 * This skips the boot sector, FSInfo sector, and non-active copies 631 * of the FAT. 632 * 633 * If sync is non-zero, the data is flushed syncrhonously. 634 */ 635void msdosfs_meta_flush_internal(struct msdosfsmount *pmp, int sync) 636{ 637 int error; 638 639 KERNEL_DEBUG_CONSTANT(MSDOSFS_META_FLUSH_INTERNAL|DBG_FUNC_START, pmp, sync, 0, 0, 0); 640 641 /* 642 * Push out any changes to the FAT. First, any dirty data in the FAT 643 * cache gets written to the FAT vnodes, then the vnodes get pushed to 644 * disk. 645 * 646 * We take the FAT lock here to delay other threads that may be trying 647 * to use the FAT, and thus delay them from activating the flush timer. 648 * We also pass IO_SYNC to cluster_push to make sure the push has completed 649 * before we return. 650 * 651 * Otherwise, we get into a vicious cycle where one change is being flushed, 652 * another change starts the flush timer, and a third change is blocked 653 * waiting for the first change's writes to complete. Meanwhile, the 654 * flush timer fires, starting a new flush. At this point, every change 655 * results in its own flush, effectively becoming synchronous. 656 */ 657 lck_mtx_lock(pmp->pm_fat_lock); 658 if (pmp->pm_fat_flags & FAT_CACHE_DIRTY) 659 { 660 error = msdosfs_fat_cache_flush(pmp, 0); 661 if (error) 662 { 663 printf("msdosfs_meta_flush_internal: error %d flushing FAT cache!\n", error); 664 pmp->pm_fat_flags &= ~FAT_CACHE_DIRTY; 665 } 666 } 667 cluster_push(pmp->pm_fat_active_vp, IO_SYNC); 668 if (pmp->pm_fat_mirror_vp) 669 cluster_push(pmp->pm_fat_mirror_vp, IO_SYNC); 670 lck_mtx_unlock(pmp->pm_fat_lock); 671 672 /* 673 * Push out any changes to directory blocks. 674 */ 675 buf_flushdirtyblks(pmp->pm_devvp, sync, 0, "msdosfs_meta_flush"); 676 677 KERNEL_DEBUG_CONSTANT(MSDOSFS_META_FLUSH_INTERNAL|DBG_FUNC_END, 0, 0, 0, 0, 0); 678} 679 680void msdosfs_meta_flush(struct msdosfsmount *pmp, int sync) 681{ 682 KERNEL_DEBUG_CONSTANT(MSDOSFS_META_FLUSH|DBG_FUNC_START, pmp, sync, 0, 0, 0); 683 684 if (sync) goto flush_now; 685 686 /* 687 * If the volume was mounted async, and we're not being told to make 688 * this flush synchronously, then ignore it. 689 */ 690 if (vfs_flags(pmp->pm_mountp) & MNT_ASYNC) 691 { 692 KERNEL_DEBUG_CONSTANT(MSDOSFS_META_FLUSH|DBG_FUNC_END, 0, MNT_ASYNC, 0, 0, 0); 693 return; 694 } 695 696 /* 697 * If we have a timer, but it has not been scheduled yet, then schedule 698 * it now. It is possible that some or all of the metadata changed by the 699 * caller has already been written out. We're merely guaranteeing that 700 * there will be a future metadata flush. 701 * 702 * If multiple threads are racing into this routine, they could all end 703 * up (re)scheduling the timer. The first thread to schedule the timer 704 * ends up incrementing both pm_sync_scheduled and pm_sync_incomplete. 705 * Any other thread will both increment and decrement pm_sync_scheduled, 706 * leaving it unchanged in the end (but greater than 1 for a brief time). 707 * 708 * NOTE: We can't rely on just a single counter (pm_sync_incomplete) because 709 * it doesn't get decremented until the callback has completed, so it 710 * could be non-zero if the flush has already begun and the iterator has 711 * already passed the newly dirtied blocks. (And unmount definitely needs 712 * to know when the last callback is *complete*, not just started.) 713 */ 714 if (pmp->pm_sync_timer) 715 { 716 if (pmp->pm_sync_scheduled == 0) 717 { 718 AbsoluteTime deadline; 719 720 clock_interval_to_deadline(msdosfs_meta_delay, kMillisecondScale, &deadline); 721 722 KERNEL_DEBUG_CONSTANT(MSDOSFS_META_FLUSH|DBG_FUNC_NONE, 0, 0, 0, 0, 0); 723 724 /* 725 * Increment pm_sync_scheduled on the assumption that we're the 726 * first thread to schedule the timer. If some other thread beat 727 * us, then we'll decrement it. If we *were* the first to 728 * schedule the timer, then we need to keep track that the 729 * callback is waiting to complete. 730 */ 731 OSIncrementAtomic(&pmp->pm_sync_scheduled); 732 if (thread_call_enter_delayed(pmp->pm_sync_timer, deadline)) 733 OSDecrementAtomic(&pmp->pm_sync_scheduled); 734 else 735 OSIncrementAtomic(&pmp->pm_sync_incomplete); 736 } 737 738 return; 739 } 740 741flush_now: 742 msdosfs_meta_flush_internal(pmp, sync); 743 KERNEL_DEBUG_CONSTANT(MSDOSFS_META_FLUSH|DBG_FUNC_END, 0, 0, 0, 0, 0); 744} 745 746 747void msdosfs_meta_sync_callback(void *arg0, void *unused) 748{ 749#pragma unused(unused) 750 struct msdosfsmount *pmp = arg0; 751 752 KERNEL_DEBUG_CONSTANT(MSDOSFS_META_SYNC_CALLBACK|DBG_FUNC_START, pmp, 0, 0, 0, 0); 753 754 OSDecrementAtomic(&pmp->pm_sync_scheduled); 755 msdosfs_meta_flush_internal(pmp, 0); 756 OSDecrementAtomic(&pmp->pm_sync_incomplete); 757 wakeup(&pmp->pm_sync_incomplete); 758 759 KERNEL_DEBUG_CONSTANT(MSDOSFS_META_SYNC_CALLBACK|DBG_FUNC_END, 0, 0, 0, 0, 0); 760} 761 762 763 764/* 765 * Map the logical cluster number of a file into a physical disk sector 766 * that is filesystem relative. 767 * 768 * dep - address of denode representing the file of interest 769 * findcn - file relative cluster whose filesystem relative cluster number 770 * and/or block number are/is to be found 771 * bnp - address of where to place the file system relative block number. 772 * If this pointer is null then don't return this quantity. 773 * cnp - address of where to place the file system relative cluster number. 774 * If this pointer is null then don't return this quantity. 775 * sp - address of where to place the number of contiguous bytes. 776 * If this pointer is null then don't return this quantity. 777 * 778 * NOTE: Either bnp or cnp must be non-null. 779 * 780 * This function has one side effect. If the requested file relative cluster 781 * is beyond the end of file, then the actual number of clusters in the file 782 * is returned in *cnp, and the file's last cluster number is returned in *sp. 783 * This is useful for determining how long a directory is, or for initializing 784 * the de_LastCluster field. 785 */ 786int msdosfs_pcbmap_internal( 787 struct denode *dep, 788 uint32_t findcn, /* file relative cluster to get */ 789 uint32_t numclusters, /* maximum number of contiguous clusters to map */ 790 daddr64_t *bnp, /* returned filesys relative blk number */ 791 uint32_t *cnp, /* returned cluster number */ 792 uint32_t *sp) /* number of contiguous bytes */ 793{ 794 int error=0; 795 uint32_t i; /* A temporary */ 796 uint32_t cn; /* The current cluster number being examined */ 797 uint32_t prevcn=0; /* The cluster previous to cn */ 798 uint32_t cluster_logical; /* First file-relative cluster in extent */ 799 uint32_t cluster_physical; /* First volume-relative cluster in extent */ 800 uint32_t cluster_count; /* Number of clusters in extent */ 801 struct msdosfsmount *pmp = dep->de_pmp; 802 void *entry; 803 daddr64_t result_block = 0; 804 uint32_t result_cluster = 0; 805 uint32_t result_contig = 0; 806 807 cn = dep->de_StartCluster; 808 809 KERNEL_DEBUG_CONSTANT(MSDOSFS_PCBMAP_INTERNAL|DBG_FUNC_START, pmp, cn, findcn, numclusters, 0); 810 811 if (numclusters == 0) 812 panic("msdosfs_pcbmap: numclusters == 0"); 813 814 /* 815 * If they don't give us someplace to return a value then don't 816 * bother doing anything. 817 */ 818 if (bnp == NULL && cnp == NULL && sp == NULL) 819 goto done; 820 821 /* 822 * The "file" that makes up the root directory is contiguous, 823 * permanently allocated, of fixed size, and is not made up of 824 * clusters. If the cluster number is beyond the end of the root 825 * directory, then return the number of clusters in the file. 826 */ 827 if (cn == MSDOSFSROOT) { 828 if (dep->de_Attributes & ATTR_DIRECTORY) { 829 if (de_cn2off(pmp, findcn) >= dep->de_FileSize) { 830 result_cluster = de_bn2cn(pmp, pmp->pm_rootdirsize); 831 error = E2BIG; 832 goto done; 833 } 834 result_block = pmp->pm_rootdirblk + de_cn2bn(pmp, findcn); 835 result_cluster = MSDOSFSROOT; 836 result_contig = min(pmp->pm_bpcluster, dep->de_FileSize - de_cn2off(pmp, findcn)); 837 goto done; 838 } else { /* just an empty file */ 839 result_cluster = 0; 840 error = E2BIG; 841 goto done; 842 } 843 } 844 845 /* 846 * If the requested position is within the currently cached extent, 847 * we can return all of the information without walking the cluster 848 * chain. 849 */ 850 if (findcn >= dep->de_cluster_logical && 851 findcn < (dep->de_cluster_logical + dep->de_cluster_count)) 852 { 853 i = findcn - dep->de_cluster_logical; /* # clusters into cached extent */ 854 cn = dep->de_cluster_physical + i; /* Starting cluster number */ 855 856 result_block = cntobn(pmp, cn); 857 result_cluster = cn; 858 result_contig = min(dep->de_cluster_count - i, numclusters) * pmp->pm_bpcluster; 859 goto done; 860 } 861 862 /* Default to scanning from the beginning of the chain. */ 863 cluster_logical = 0; 864 cluster_physical = 0; 865 cluster_count = 0; 866 /* From above: cn = dep->de_StartCluster */ 867 868 /* 869 * If the requested position is after the cached extent, then start scanning 870 * from the last cluster of the cached extent. We set up the state 871 * (cluster_xxx and cn) as if the loop below had just finished scanning 872 * the cached extent, with cn being the first cluster of the next extent. 873 */ 874 if (dep->de_cluster_count && findcn > dep->de_cluster_logical) 875 { 876 cluster_logical = dep->de_cluster_logical; 877 cluster_physical = dep->de_cluster_physical; 878 cluster_count = dep->de_cluster_count; 879 prevcn = dep->de_cluster_physical+dep->de_cluster_count-1; 880 error = msdosfs_fatentry_internal(FAT_GET, pmp, prevcn, &cn, 0); 881 if (error) 882 goto done; 883 } 884 885 /* 886 * Iterate through the extents (runs of contiguous clusters) in the file 887 * until we find the extent containing findcn, or we hit end of file. 888 */ 889 while ((cluster_logical + cluster_count) <= findcn) 890 { 891 /* 892 * Stop with all reserved clusters, not just with EOF. 893 */ 894 if ((cn | ~pmp->pm_fatmask) >= CLUST_RSRVD) 895 goto hiteof; 896 897 /* 898 * Detect infinite cycles in the cluster chain. (Generally only useful 899 * for directories, where findcn is (-1).) 900 */ 901 if (cluster_logical > pmp->pm_maxcluster) 902 { 903 printf("msdosfs: msdosfs_pcbmap: Corrupt cluster chain detected\n"); 904 pmp->pm_flags |= MSDOSFS_CORRUPT; 905 error = EIO; 906 goto done; 907 } 908 909 /* 910 * Stop and return an error if we hit an out-of-range cluster number. 911 */ 912 if (cn < CLUST_FIRST || cn > pmp->pm_maxcluster) 913 { 914 if (DEBUG) 915 panic("msdosfs_pcbmap_internal: invalid cluster: cn=%u, name='%11.11s'", cn, dep->de_Name); 916 error = EIO; 917 goto done; 918 } 919 920 /* 921 * Keep track of the start of the extent. 922 * 923 * The count is initialized to zero because it will be incremented to 924 * account for cluster "cn" at the end of the do ... while loop. 925 */ 926 cluster_logical += cluster_count; /* Skip past previous extent */ 927 cluster_physical = cn; 928 cluster_count = 0; 929 930 /* 931 * Loop over contiguous clusters starting with #cn. 932 */ 933 do { 934 /* 935 * Make sure we have the block containing the cn'th entry in the FAT. 936 */ 937 entry = msdosfs_fat_map(pmp, cn, NULL, NULL, &error); 938 if (!entry) 939 goto done; 940 941 /* 942 * Fetch the next cluster in the chain. 943 */ 944 prevcn = cn; 945 if (FAT32(pmp)) 946 cn = getuint32(entry); 947 else 948 cn = getuint16(entry); 949 if (FAT12(pmp) && (prevcn & 1)) 950 cn >>= 4; 951 cn &= pmp->pm_fatmask; 952 953 /* 954 * Force the special cluster numbers 955 * to be the same for all cluster sizes 956 * to let the rest of msdosfs handle 957 * all cases the same. 958 */ 959 if ((cn | ~pmp->pm_fatmask) >= CLUST_RSRVD) 960 cn |= ~pmp->pm_fatmask; 961 962 cluster_count++; 963 } while (cn == prevcn + 1); 964 965 /* 966 * Falling out of the do..while loop means that cn is the start of a 967 * new extent (or a reserved/EOF value). 968 */ 969 } 970 971 /* 972 * We have found the extent containing findcn. Remember it, and return 973 * the mapping information. 974 */ 975 dep->de_cluster_logical = cluster_logical; 976 dep->de_cluster_physical = cluster_physical; 977 dep->de_cluster_count = cluster_count; 978 979 i = findcn - cluster_logical; /* # of clusters into found extent */ 980 cn = cluster_physical + i; /* findcn'th physical (volume-relative) cluster */ 981 982 result_block = cntobn(pmp, cn); 983 result_cluster = cn; 984 result_contig = min(cluster_count-i, numclusters) * pmp->pm_bpcluster; 985 986done: 987 if (bnp) 988 *bnp = result_block; 989 if (cnp) 990 *cnp = result_cluster; 991 if (sp) 992 *sp = result_contig; 993 KERNEL_DEBUG_CONSTANT(MSDOSFS_PCBMAP_INTERNAL|DBG_FUNC_END, error, result_block, result_cluster, result_contig, 0); 994 return error; 995 996hiteof: 997 result_cluster = cluster_logical + cluster_count; 998 result_contig = prevcn; 999 error = E2BIG; 1000 goto done; 1001} 1002 1003 1004int msdosfs_pcbmap( 1005 struct denode *dep, 1006 uint32_t findcn, /* file relative cluster to get */ 1007 uint32_t numclusters, /* maximum number of contiguous clusters to map */ 1008 daddr64_t *bnp, /* returned filesys relative blk number */ 1009 uint32_t *cnp, /* returned cluster number */ 1010 uint32_t *sp) /* number of contiguous bytes */ 1011{ 1012 int error; 1013 1014 KERNEL_DEBUG_CONSTANT(MSDOSFS_PCBMAP|DBG_FUNC_START, dep->de_pmp, dep->de_StartCluster, findcn, numclusters, 0); 1015 1016 lck_mtx_lock(dep->de_cluster_lock); 1017 lck_mtx_lock(dep->de_pmp->pm_fat_lock); 1018 error = msdosfs_pcbmap_internal(dep, findcn, numclusters, bnp, cnp, sp); 1019 lck_mtx_unlock(dep->de_pmp->pm_fat_lock); 1020 lck_mtx_unlock(dep->de_cluster_lock); 1021 1022 KERNEL_DEBUG_CONSTANT(MSDOSFS_PCBMAP|DBG_FUNC_END, error, 0, 0, 0, 0); 1023 1024 return error; 1025} 1026 1027 1028/* 1029 * Get or Set or 'Get and Set' the cluster'th entry in the fat. 1030 * 1031 * function - whether to get or set a fat entry 1032 * pmp - address of the msdosfsmount structure for the filesystem 1033 * whose fat is to be manipulated. 1034 * cn - which cluster is of interest 1035 * oldcontents - address of a word that is to receive the contents of the 1036 * cluster'th entry if this is a get function 1037 * newcontents - the new value to be written into the cluster'th element of 1038 * the fat if this is a set function. 1039 * 1040 * This function can also be used to free a cluster by setting the fat entry 1041 * for a cluster to 0. 1042 * 1043 * All copies of the fat are updated if this is a set function. NOTE: If 1044 * msdosfs_fatentry() marks a cluster as free it does not update the inusemap in 1045 * the msdosfsmount structure. This is left to the caller. 1046 * 1047 * Updating entries in 12 bit fats is a pain in the butt. 1048 * 1049 * The following picture shows where nibbles go when moving from a 12 bit 1050 * cluster number into the appropriate bytes in the FAT. 1051 * 1052 * byte m byte m+1 byte m+2 1053 * +----+----+ +----+----+ +----+----+ 1054 * | 0 1 | | 2 3 | | 4 5 | FAT bytes 1055 * +----+----+ +----+----+ +----+----+ 1056 * 1057 * +----+----+----+ +----+----+----+ 1058 * | 3 0 1 | | 4 5 2 | 1059 * +----+----+----+ +----+----+----+ 1060 * cluster n cluster n+1 1061 * 1062 * Where n is even. m = n + (n >> 2) 1063 * 1064 */ 1065int msdosfs_fatentry_internal(int function, struct msdosfsmount *pmp, uint32_t cn, uint32_t *oldcontents, uint32_t newcontents) 1066{ 1067 int error = 0; 1068 uint32_t readcn; 1069 void *entry; 1070 uint32_t result_old = 0; 1071 1072 KERNEL_DEBUG_CONSTANT(MSDOSFS_FATENTRY_INTERNAL|DBG_FUNC_START, pmp, cn, function, newcontents, 0); 1073 1074 /* 1075 * Be sure the requested cluster is in the filesystem. 1076 */ 1077 if (cn < CLUST_FIRST || cn > pmp->pm_maxcluster) 1078 { 1079 if (DEBUG) 1080 { 1081 printf("msdosfs: msdosfs_fatentry_internal: cn=%u, function=%d, new=%u\n", cn, function, newcontents); 1082 } 1083 error = EIO; 1084 goto done; 1085 } 1086 1087 entry = msdosfs_fat_map(pmp, cn, NULL, NULL, &error); 1088 if (!entry) 1089 goto done; 1090 1091 if (function & FAT_GET) { 1092 if (FAT32(pmp)) 1093 readcn = getuint32(entry); 1094 else 1095 readcn = getuint16(entry); 1096 if (FAT12(pmp) & (cn & 1)) 1097 readcn >>= 4; 1098 readcn &= pmp->pm_fatmask; 1099 /* map reserved fat entries to same values for all fats */ 1100 if ((readcn | ~pmp->pm_fatmask) >= CLUST_RSRVD) 1101 readcn |= ~pmp->pm_fatmask; 1102 *oldcontents = readcn; 1103 result_old = readcn; 1104 } 1105 if (function & FAT_SET) { 1106 switch (pmp->pm_fatmask) { 1107 case FAT12_MASK: 1108 readcn = getuint16(entry); 1109 if (cn & 1) { 1110 readcn &= 0x000f; 1111 readcn |= newcontents << 4; 1112 } else { 1113 readcn &= 0xf000; 1114 readcn |= newcontents & 0xfff; 1115 } 1116 putuint16(entry, readcn); 1117 break; 1118 case FAT16_MASK: 1119 putuint16(entry, newcontents); 1120 break; 1121 case FAT32_MASK: 1122 /* 1123 * According to spec we have to retain the 1124 * high order bits of the fat entry. 1125 */ 1126 readcn = getuint32(entry); 1127 readcn &= ~FAT32_MASK; 1128 readcn |= newcontents & FAT32_MASK; 1129 putuint32(entry, readcn); 1130 break; 1131 } 1132 pmp->pm_fat_flags |= FAT_CACHE_DIRTY | FSINFO_DIRTY; 1133 } 1134 1135done: 1136 KERNEL_DEBUG_CONSTANT(MSDOSFS_FATENTRY_INTERNAL|DBG_FUNC_END, error, result_old, 0, 0, 0); 1137 return 0; 1138} 1139 1140int msdosfs_fatentry(int function, struct msdosfsmount *pmp, uint32_t cn, uint32_t *oldcontents, uint32_t newcontents) 1141{ 1142 int error; 1143 1144 KERNEL_DEBUG_CONSTANT(MSDOSFS_FATENTRY|DBG_FUNC_START, pmp, cn, function, newcontents, 0); 1145 1146 lck_mtx_lock(pmp->pm_fat_lock); 1147 error = msdosfs_fatentry_internal(function, pmp, cn, oldcontents, newcontents); 1148 lck_mtx_unlock(pmp->pm_fat_lock); 1149 1150 KERNEL_DEBUG_CONSTANT(MSDOSFS_FATENTRY|DBG_FUNC_END, error, 0, 0, 0, 0); 1151 1152 return error; 1153} 1154 1155 1156/* 1157 * Update a contiguous cluster chain 1158 * 1159 * pmp - mount point 1160 * start - first cluster of chain 1161 * count - number of clusters in chain 1162 * fillwith - what to write into fat entry of last cluster 1163 */ 1164int msdosfs_fatchain(struct msdosfsmount *pmp, uint32_t start, uint32_t count, uint32_t fillwith) 1165{ 1166 int error = 0; 1167 u_int32_t bo, bsize; 1168 uint32_t readcn, newc; 1169 char *entry; 1170 char *block_end; 1171 1172 KERNEL_DEBUG_CONSTANT(MSDOSFS_FATCHAIN|DBG_FUNC_START, pmp, start, count, fillwith, 0); 1173 1174 /* 1175 * Be sure the clusters are in the filesystem. 1176 */ 1177 if (start < CLUST_FIRST || start + count - 1 > pmp->pm_maxcluster) 1178 { 1179 printf("msdosfs: msdosfs_fatchain: start=%u, count=%u, fill=%u\n", start, count, fillwith); 1180 error = EIO; 1181 goto done; 1182 } 1183 1184 /* Loop over all clusters in the chain */ 1185 while (count > 0) { 1186 entry = msdosfs_fat_map(pmp, start, &bo, &bsize, &error); 1187 if (!entry) 1188 break; 1189 1190 block_end = entry - bo + bsize; 1191 1192 /* Loop over all clusters in this FAT block */ 1193 while (count > 0) { 1194 start++; 1195 newc = --count > 0 ? start : fillwith; 1196 switch (pmp->pm_fatmask) { 1197 case FAT12_MASK: 1198 readcn = getuint16(entry); 1199 if (start & 1) { 1200 readcn &= 0xf000; 1201 readcn |= newc & 0xfff; 1202 } else { 1203 readcn &= 0x000f; 1204 readcn |= newc << 4; 1205 } 1206 putuint16(entry, readcn); 1207 entry++; 1208 if (!(start & 1)) 1209 entry++; 1210 break; 1211 case FAT16_MASK: 1212 putuint16(entry, newc); 1213 entry += 2; 1214 break; 1215 case FAT32_MASK: 1216 readcn = getuint32(entry); 1217 readcn &= ~pmp->pm_fatmask; 1218 readcn |= newc & pmp->pm_fatmask; 1219 putuint32(entry, readcn); 1220 entry += 4; 1221 break; 1222 } 1223 if (entry >= block_end) 1224 break; 1225 } 1226 pmp->pm_fat_flags |= FAT_CACHE_DIRTY | FSINFO_DIRTY; 1227 } 1228 1229done: 1230 KERNEL_DEBUG_CONSTANT(MSDOSFS_FATCHAIN|DBG_FUNC_END, error, 0, 0, 0, 0); 1231 return error; 1232} 1233 1234/* 1235 * Check the length of a free cluster chain starting at start. 1236 * 1237 * pmp - mount point 1238 * start - start of chain 1239 * count - maximum interesting length 1240 */ 1241uint32_t msdosfs_chainlength(struct msdosfsmount *pmp, uint32_t start, uint32_t count) 1242{ 1243 uint32_t found = 0; /* Number of contiguous free clusters found so far */ 1244 uint32_t readcn = 0; /* A cluster number read from the FAT */ 1245 char *entry; /* Current FAT entry (points into FAT cache block) */ 1246 char *block_end; /* End of current entry's FAT cache block */ 1247 uint32_t bo, bsize; /* Offset into, and size of, FAT cache block */ 1248 int error = 0; 1249 1250 KERNEL_DEBUG_CONSTANT(MSDOSFS_CHAINLENGTH|DBG_FUNC_START, pmp, start, count, 0, 0); 1251 1252 /* Loop over all clusters from "start" to end of volume. */ 1253 while (found < count && start <= pmp->pm_maxcluster) 1254 { 1255 /* Find the entry for the start'th cluster in the FAT */ 1256 entry = msdosfs_fat_map(pmp, start, &bo, &bsize, &error); 1257 if (!entry) 1258 { 1259 printf("msdosfs chainlength: error %d reading FAT for cluster %u\n", error, start); 1260 break; 1261 } 1262 1263 /* Find the end of the current FAT block. */ 1264 block_end = entry - bo + bsize; 1265 1266 /* Loop over all entries in this FAT block. */ 1267 while (found < count && entry < block_end) 1268 { 1269 /* Extract the value from the current FAT entry into "readcn" */ 1270 switch (pmp->pm_fatmask) 1271 { 1272 case FAT12_MASK: 1273 readcn = getuint16(entry); 1274 if (start & 1) 1275 { 1276 readcn >>= 4; 1277 entry += 2; 1278 } 1279 else 1280 { 1281 readcn &= FAT12_MASK; 1282 entry++; 1283 } 1284 break; 1285 case FAT16_MASK: 1286 readcn = getuint16(entry); 1287 entry += 2; 1288 break; 1289 case FAT32_MASK: 1290 readcn = getuint32(entry); 1291 entry += 4; 1292 readcn &= FAT32_MASK; 1293 break; 1294 } 1295 1296 if (readcn == 0) 1297 found++; 1298 else 1299 goto done; 1300 1301 start++; 1302 } 1303 } 1304 1305done: 1306 KERNEL_DEBUG_CONSTANT(MSDOSFS_CHAINLENGTH|DBG_FUNC_END, error, found, 0, 0, 0); 1307 return found; 1308} 1309 1310/* 1311 * Allocate contigous free clusters. 1312 * 1313 * pmp - mount point. 1314 * start - start of cluster chain. 1315 * count - number of clusters to allocate. 1316 * fillwith - put this value into the fat entry for the 1317 * last allocated cluster. 1318 * retcluster - put the first allocated cluster's number here. 1319 * got - how many clusters were actually allocated. 1320 */ 1321int msdosfs_chainalloc( 1322 struct msdosfsmount *pmp, 1323 uint32_t start, 1324 uint32_t count, 1325 uint32_t fillwith, 1326 uint32_t *retcluster, 1327 uint32_t *got) 1328{ 1329 int error = 0; 1330 1331 KERNEL_DEBUG_CONSTANT(MSDOSFS_CHAINALLOC|DBG_FUNC_START, pmp, start, count, fillwith, 0); 1332 pmp->pm_freeclustercount -= count; 1333 1334 error = msdosfs_fatchain(pmp, start, count, fillwith); 1335 if (error != 0) 1336 goto done; 1337 1338 if (retcluster) 1339 *retcluster = start; 1340 if (got) 1341 *got = count; 1342done: 1343 KERNEL_DEBUG_CONSTANT(MSDOSFS_FREESPACE, pmp, pmp->pm_freeclustercount, 0, 0, 0); 1344 KERNEL_DEBUG_CONSTANT(MSDOSFS_CHAINALLOC|DBG_FUNC_END, error, start, count, 0, 0); 1345 return error; 1346} 1347 1348/* 1349 * Allocate contiguous free clusters. 1350 * 1351 * pmp - mount point. 1352 * start - preferred start of cluster chain. 1353 * count - number of clusters requested. 1354 * fillwith - put this value into the fat entry for the 1355 * last allocated cluster. 1356 * retcluster - put the first allocated cluster's number here. 1357 * got - how many clusters were actually allocated. 1358 */ 1359int msdosfs_clusteralloc_internal( 1360 struct msdosfsmount *pmp, 1361 uint32_t start, 1362 uint32_t count, 1363 uint32_t fillwith, 1364 uint32_t *retcluster, 1365 uint32_t *got) 1366{ 1367 int error = 0; 1368 uint32_t len; /* The number of free clusters at "start" */ 1369 uint32_t cn; /* A cluster number (loop index) */ 1370 uint32_t l; /* The number of contiguous free clusters at "cn" */ 1371 uint32_t foundl; /* The largest contiguous run of free clusters found so far */ 1372 uint32_t foundcn; /* The starting cluster of largest run found */ 1373 1374 KERNEL_DEBUG_CONSTANT(MSDOSFS_CLUSTERALLOC_INTERNAL|DBG_FUNC_START, pmp, start, count, fillwith, 0); 1375 1376 if (start) { 1377 /* 1378 * If the caller had a specific starting cluster, then look there 1379 * first. (This happens when extending an existing file or directory.) 1380 * 1381 * If there are enough contiguous free clusters at "start", just use them. 1382 */ 1383 if ((len = msdosfs_chainlength(pmp, start, count)) >= count) 1384 { 1385 error = msdosfs_chainalloc(pmp, start, count, fillwith, retcluster, got); 1386 goto done; 1387 } 1388 1389 /* 1390 * If we fall through here, "len" = the number of contiguous free clusters 1391 * starting at "start". 1392 */ 1393 } else { 1394 /* No specific starting point requested, so use the "next free" pointer. */ 1395 start = pmp->pm_nxtfree; 1396 len = 0; 1397 } 1398 1399 /* 1400 * "foundl" is the largest number of contiguous free clusters found so far. 1401 * "foundcn" is the corresponding starting cluster. 1402 */ 1403 foundl = 0; 1404 foundcn = 0; 1405 1406 /* 1407 * Scan through the FAT for contiguous free clusters. 1408 * 1409 * TODO: Should we just return any free clusters starting at "start" 1410 * (if it was non-zero), or else the first free clusters at or after 1411 * pmp->pm_nxtfree (with wrap-around)? 1412 */ 1413 for (cn = start; cn <= pmp->pm_maxcluster; cn += l+1) { 1414 /* 1415 * TODO: This is wasteful when skipping over a large range of clusters 1416 * that are allocated. Perhaps the routine should return how many 1417 * contiguous clusters and whether they were free or allocated? 1418 * Or should this routine examine the FAT directly? Or just have a 1419 * "skip used clusters and return the count" routine? 1420 */ 1421 l = msdosfs_chainlength(pmp, cn, count); 1422 if (l >= count) 1423 { 1424 /* We found enough free space, so look here next time. */ 1425 pmp->pm_nxtfree = cn + count; 1426 error = msdosfs_chainalloc(pmp, cn, count, fillwith, retcluster, got); 1427 goto done; 1428 } 1429 1430 /* Keep track of longest free extent found */ 1431 if (l > foundl) 1432 { 1433 foundcn = cn; 1434 foundl = l; 1435 } 1436 } 1437 for (cn = CLUST_FIRST; cn < start; cn += l+1) { 1438 l = msdosfs_chainlength(pmp, cn, count); 1439 if (l >= count) 1440 { 1441 /* We found enough free space, so look here next time. */ 1442 pmp->pm_nxtfree = cn + count; 1443 error = msdosfs_chainalloc(pmp, cn, count, fillwith, retcluster, got); 1444 goto done; 1445 } 1446 1447 /* Keep track of longest free extent found */ 1448 if (l > foundl) 1449 { 1450 foundcn = cn; 1451 foundl = l; 1452 } 1453 } 1454 1455 /* 1456 * If we get here, there was no single contiguous chain as long as we 1457 * wanted. Check to see if we found *any* free chains. 1458 */ 1459 if (!foundl) 1460 { 1461 error = ENOSPC; 1462 goto done; 1463 } 1464 1465 /* 1466 * There was no single contiguous chain long enough. If the caller passed 1467 * a specific starting cluster, and there were free clusters there, then 1468 * return that chain (under the assumption they're at least contiguous 1469 * with the previous bit of the file -- which might result in fewer 1470 * total extents). 1471 * 1472 * Otherwise, just return the largest free chain we found. 1473 * 1474 * TODO: Should we instead try to use the first free chain at or after 1475 * pmp->pm_nxtfree? 1476 */ 1477 if (len) 1478 { 1479 /* Don't update pm_nxtfree since we didn't allocate from there. */ 1480 error = msdosfs_chainalloc(pmp, start, len, fillwith, retcluster, got); 1481 } 1482 else 1483 { 1484 /* 1485 * TODO: Is updating pm_nxtfree really correct? Perhaps only if 1486 * foundcn == pmp->pm_nxtfree? 1487 */ 1488 pmp->pm_nxtfree = foundcn + foundl; 1489 error = msdosfs_chainalloc(pmp, foundcn, foundl, fillwith, retcluster, got); 1490 } 1491 1492done: 1493 KERNEL_DEBUG_CONSTANT(MSDOSFS_CLUSTERALLOC_INTERNAL|DBG_FUNC_END, error, 0, 0, 0, 0); 1494 return error; 1495} 1496 1497int msdosfs_clusteralloc( 1498 struct msdosfsmount *pmp, 1499 uint32_t start, 1500 uint32_t count, 1501 uint32_t fillwith, 1502 uint32_t *retcluster, 1503 uint32_t *got) 1504{ 1505 int error; 1506 1507 KERNEL_DEBUG_CONSTANT(MSDOSFS_CLUSTERALLOC|DBG_FUNC_START, pmp, start, count, fillwith, 0); 1508 1509 lck_mtx_lock(pmp->pm_fat_lock); 1510 error = msdosfs_clusteralloc_internal(pmp, start, count, fillwith, retcluster, got); 1511 lck_mtx_unlock(pmp->pm_fat_lock); 1512 1513 KERNEL_DEBUG_CONSTANT(MSDOSFS_CLUSTERALLOC|DBG_FUNC_END, error, 0, 0, 0, 0); 1514 1515 return error; 1516} 1517 1518 1519/* 1520 * Free a chain of clusters. 1521 * 1522 * pmp - address of the msdosfs mount structure for the filesystem 1523 * containing the cluster chain to be freed. 1524 * startcluster - number of the 1st cluster in the chain of clusters to be 1525 * freed. 1526 */ 1527int msdosfs_freeclusterchain(struct msdosfsmount *pmp, uint32_t cluster) 1528{ 1529 int error = 0; 1530 uint32_t readcn; 1531 void *entry; 1532 1533 KERNEL_DEBUG_CONSTANT(MSDOSFS_FREECLUSTERCHAIN|DBG_FUNC_START, pmp, cluster, 0, 0, 0); 1534 1535 lck_mtx_lock(pmp->pm_fat_lock); 1536 1537 while (cluster >= CLUST_FIRST && cluster <= pmp->pm_maxcluster) { 1538 entry = msdosfs_fat_map(pmp, cluster, NULL, NULL, &error); 1539 if (!entry) 1540 break; 1541 1542 pmp->pm_freeclustercount++; 1543 switch (pmp->pm_fatmask) { 1544 case FAT12_MASK: 1545 readcn = getuint16(entry); 1546 if (cluster & 1) { 1547 cluster = readcn >> 4; 1548 readcn &= 0x000f; 1549 readcn |= MSDOSFSFREE << 4; 1550 } else { 1551 cluster = readcn; 1552 readcn &= 0xf000; 1553 readcn |= MSDOSFSFREE & 0xfff; 1554 } 1555 putuint16(entry, readcn); 1556 break; 1557 case FAT16_MASK: 1558 cluster = getuint16(entry); 1559 putuint16(entry, MSDOSFSFREE); 1560 break; 1561 case FAT32_MASK: 1562 cluster = getuint32(entry); 1563 putuint32(entry, (MSDOSFSFREE & FAT32_MASK) | (cluster & ~FAT32_MASK)); 1564 break; 1565 } 1566 pmp->pm_fat_flags |= FAT_CACHE_DIRTY | FSINFO_DIRTY; 1567 cluster &= pmp->pm_fatmask; 1568 if ((cluster | ~pmp->pm_fatmask) >= CLUST_RSRVD) 1569 cluster |= ~pmp->pm_fatmask; 1570 } 1571 KERNEL_DEBUG_CONSTANT(MSDOSFS_FREESPACE, pmp, pmp->pm_freeclustercount, 0, 0, 0); 1572 lck_mtx_unlock(pmp->pm_fat_lock); 1573 1574 if (cluster < CLUST_RSRVD) 1575 printf("msdosfs_freeclusterchain: found out-of-range cluster (%u)\n", cluster); 1576 1577 KERNEL_DEBUG_CONSTANT(MSDOSFS_FREECLUSTERCHAIN|DBG_FUNC_END, error, cluster, 0, 0, 0); 1578 1579 return error; 1580} 1581 1582/* 1583 * Read in fat blocks to count the number of free clusters. 1584 */ 1585int msdosfs_count_free_clusters(struct msdosfsmount *pmp) 1586{ 1587 uint32_t cn, readcn=0; 1588 int error = 0; 1589 char *entry, *last_entry; 1590 u_int32_t offset, block_size; 1591 1592 KERNEL_DEBUG_CONSTANT(MSDOSFS_COUNT_FREE_CLUSTERS|DBG_FUNC_START, pmp, 0, 0, 0, 0); 1593 1594 /* 1595 * We're going to be reading the entire FAT, so advise Cluster I/O 1596 * that it should begin the read now. 1597 */ 1598 (void) advisory_read(pmp->pm_fat_active_vp, pmp->pm_fat_bytes, 0, pmp->pm_fat_bytes); 1599 1600 /* 1601 * Figure how many free clusters are in the filesystem by ripping 1602 * through the fat counting the number of entries whose content is 1603 * zero. These represent free clusters. 1604 */ 1605 pmp->pm_freeclustercount = 0; 1606 for (cn = CLUST_FIRST; cn <= pmp->pm_maxcluster; ) { 1607 entry = msdosfs_fat_map(pmp, cn, &offset, &block_size, &error); 1608 if (!entry) 1609 break; 1610 1611 /* Get a pointer past the last valid entry in the block */ 1612 last_entry = entry - offset + block_size; 1613 1614 while (entry < last_entry && cn <= pmp->pm_maxcluster) 1615 { 1616 switch (pmp->pm_fatmask) 1617 { 1618 case FAT12_MASK: 1619 readcn = getuint16(entry); 1620 if (cn & 1) 1621 { 1622 readcn >>= 4; 1623 entry += 2; 1624 } 1625 else 1626 { 1627 readcn &= FAT12_MASK; 1628 entry++; 1629 } 1630 break; 1631 case FAT16_MASK: 1632 readcn = getuint16(entry); 1633 entry += 2; 1634 break; 1635 case FAT32_MASK: 1636 readcn = getuint32(entry); 1637 entry += 4; 1638 readcn &= FAT32_MASK; 1639 break; 1640 } 1641 1642 if (readcn == 0) 1643 pmp->pm_freeclustercount++; 1644 1645 cn++; 1646 } 1647 } 1648 1649 KERNEL_DEBUG_CONSTANT(MSDOSFS_FREESPACE, pmp, pmp->pm_freeclustercount, 0, 0, 0); 1650 KERNEL_DEBUG_CONSTANT(MSDOSFS_COUNT_FREE_CLUSTERS|DBG_FUNC_END, error, pmp->pm_freeclustercount, 0, 0, 0); 1651 return error; 1652} 1653 1654struct extent { 1655 uint32_t start; 1656 uint32_t count; 1657}; 1658 1659int msdosfs_find_free_extents(struct msdosfsmount *pmp, uint32_t start, uint32_t count); 1660int msdosfs_find_next_free(struct msdosfsmount *pmp, uint32_t start, uint32_t end, uint32_t maxCount, 1661 uint32_t *foundStart, uint32_t *foundCount); 1662void msdosfs_insert_free_extent(struct msdosfsmount *pmp, uint32_t start, uint32_t count); 1663 1664/* 1665 * msdosfs_find_next_free - Search through the FAT looking for a single contiguous 1666 * extent of free clusters. 1667 * 1668 * Searches clusters start through end-1, inclusive. Exits immediately if it finds 1669 * at least maxCount contiguous clusters. The found extent is returned in 1670 * *foundStart and *foundCount. 1671 */ 1672int msdosfs_find_next_free(struct msdosfsmount *pmp, uint32_t start, uint32_t end, uint32_t maxCount, 1673 uint32_t *foundStart, uint32_t *foundCount) 1674{ 1675 uint32_t cn = start; /* Current cluster number being examined. */ 1676 uint32_t found = 0; /* Number of contiguous free extents found so far. */ 1677 uint32_t readcn = 0; /* A cluster number read from the FAT */ 1678 char *entry; /* Current FAT entry (points into FAT cache block) */ 1679 char *block_end; /* End of current entry's FAT cache block */ 1680 u_int32_t bo, bsize; /* Offset into, and size of, FAT cache block */ 1681 int error = 0; 1682 1683 KERNEL_DEBUG_CONSTANT(MSDOSFS_FIND_NEXT_FREE|DBG_FUNC_START, pmp, start, end, maxCount, 0); 1684 1685 while (found < maxCount && cn < end) 1686 { 1687 /* Find the entry for the cn'th cluster in the FAT */ 1688 entry = msdosfs_fat_map(pmp, cn, &bo, &bsize, &error); 1689 if (!entry) 1690 { 1691 printf("msdosfs_find_next_free: error %d reading FAT for cluster %u\n", error, cn); 1692 break; 1693 } 1694 1695 /* Find the end of the current FAT block. */ 1696 block_end = entry - bo + bsize; 1697 1698 /* Loop over all entries in this FAT block. */ 1699 while (found < maxCount && cn < end && entry < block_end) 1700 { 1701 /* Extract the value from the current FAT entry into "readcn" */ 1702 switch (pmp->pm_fatmask) 1703 { 1704 case FAT12_MASK: 1705 readcn = getuint16(entry); 1706 if (cn & 1) 1707 { 1708 readcn >>= 4; 1709 entry += 2; 1710 } 1711 else 1712 { 1713 readcn &= FAT12_MASK; 1714 entry++; 1715 } 1716 break; 1717 case FAT16_MASK: 1718 readcn = getuint16(entry); 1719 entry += 2; 1720 break; 1721 case FAT32_MASK: 1722 readcn = getuint32(entry); 1723 entry += 4; 1724 readcn &= FAT32_MASK; 1725 break; 1726 } 1727 1728 if (readcn == 0) 1729 { 1730 /* 1731 * Found a free cluster. If this was the first one, then 1732 * return the start of the extent. 1733 */ 1734 if (found == 0) 1735 { 1736 *foundStart = cn; 1737 } 1738 ++ found; 1739 } 1740 else 1741 { 1742 /* 1743 * Found a used cluster. If we already found some free 1744 * clusters, then we've found the end of a free exent, 1745 * and we're done. 1746 */ 1747 if (found != 0) 1748 goto done; 1749 } 1750 1751 cn++; 1752 } 1753 } 1754 1755done: 1756 *foundCount = found; 1757 KERNEL_DEBUG_CONSTANT(MSDOSFS_FIND_NEXT_FREE|DBG_FUNC_END, error, *foundStart, *foundCount, 0, 0); 1758 return error; 1759} 1760 1761void msdosfs_insert_free_extent(struct msdosfsmount *pmp, uint32_t start, uint32_t count) 1762{ 1763 uint32_t maxExtents = PAGE_SIZE / sizeof(struct extent); 1764 struct extent *extents = (struct extent *) pmp->pm_free_extents; 1765 1766 /* 1767 * If the free extent list is full, and the given extent is no better than the 1768 * worst we already know about, then ignore it. 1769 */ 1770 if (pmp->pm_free_extent_count == maxExtents && count <= extents[maxExtents-1].count) 1771 return; 1772 1773 /* 1774 * Find the index in the free extent table to insert the given extent. 1775 * When we're done with the loop, the given extent should be inserted 1776 * before extents[i]. NOTE: i < maxExtents. 1777 * 1778 * TODO: Use a binary search to find the right spot for the insertion. 1779 */ 1780 uint32_t i = pmp->pm_free_extent_count; 1781 while (i > 0 && extents[i-1].count < count) 1782 --i; 1783 if (i >= maxExtents) 1784 panic("msdosfs_insert_free_extent: invalid insertion index"); 1785 1786 /* 1787 * Make room for the new extent to be inserted. Grow the array if it isn't 1788 * full yet. Shift any worse extents (index i+1 or larger) down in the array. 1789 */ 1790 if (pmp->pm_free_extent_count < maxExtents) 1791 pmp->pm_free_extent_count++; 1792 size_t bytes = (pmp->pm_free_extent_count - (i + 1)) * sizeof(struct extent); 1793 if (bytes) 1794 memmove(&extents[i+1], &extents[i], bytes); 1795 1796 extents[i].start = start; 1797 extents[i].count = count; 1798} 1799 1800/* 1801 * msdosfs_find_free_extents - Search through the FAT looking for contiguous free clusters. 1802 * It populates the free extent cache (pm_free_extents). 1803 * 1804 * start - Desired cluster number for starting the search, or zero for anywhere. 1805 * count - Maximum number of contiguous clusters needed. 1806 */ 1807int msdosfs_find_free_extents(struct msdosfsmount *pmp, uint32_t start, uint32_t count) 1808{ 1809 int error = 0; 1810 uint32_t next; /* Cluster number for next search. */ 1811 uint32_t foundStart, foundCount; 1812 struct extent *extents = pmp->pm_free_extents; 1813 1814 KERNEL_DEBUG_CONSTANT(MSDOSFS_FIND_FREE_EXTENTS|DBG_FUNC_START, pmp, start, count, 0, 0); 1815 1816 if (start < CLUST_FIRST || start > pmp->pm_maxcluster) 1817 start = CLUST_FIRST; 1818 1819 /* Forget about extents we found previously. */ 1820 pmp->pm_free_extent_count = 0; 1821 1822 /* Look for free extents from "start" to end of FAT. */ 1823 next = start; 1824 while (next <= pmp->pm_maxcluster) 1825 { 1826 error = msdosfs_find_next_free(pmp, next, pmp->pm_maxcluster+1, count, &foundStart, &foundCount); 1827 if (error != 0) goto done; 1828 if (foundCount == count) 1829 { 1830 extents[0].start = foundStart; 1831 extents[0].count = foundCount; 1832 pmp->pm_free_extent_count = 1; 1833 goto done; 1834 } 1835 if (foundCount == 0) break; 1836 msdosfs_insert_free_extent(pmp, foundStart, foundCount); 1837 next = foundStart + foundCount; 1838 } 1839 1840 /* Wrap around. Look for extents from start of FAT to "start". */ 1841 next = CLUST_FIRST; 1842 while (next < start) 1843 { 1844 error = msdosfs_find_next_free(pmp, next, start, count, &foundStart, &foundCount); 1845 if (error != 0) goto done; 1846 if (foundCount == count) 1847 { 1848 extents[0].start = foundStart; 1849 extents[0].count = foundCount; 1850 pmp->pm_free_extent_count = 1; 1851 goto done; 1852 } 1853 if (foundCount == 0) break; 1854 msdosfs_insert_free_extent(pmp, foundStart, foundCount); 1855 next = foundStart + foundCount; 1856 } 1857 1858done: 1859 KERNEL_DEBUG_CONSTANT(MSDOSFS_FIND_FREE_EXTENTS|DBG_FUNC_END, error, pmp->pm_free_extent_count, extents[0].start, extents[0].count, 0); 1860 return error; 1861} 1862 1863 1864/* 1865 * Allocate new clusters and chain them onto the end of the file. 1866 * 1867 * dep - the file to extend 1868 * count - maximum number of clusters to allocate 1869 * numAllocated - actual number of clusters allocated 1870 * 1871 * Allocates up to "count" clusters and appends them to the end of the 1872 * file's cluster chain. If fewer than "count" clusters are free, then 1873 * allocate and append all remaining clusters. 1874 * 1875 * NOTE: This function is not responsible for turning on the DE_UPDATE bit of 1876 * the de_flag field of the denode and it does not change the de_FileSize 1877 * field. This is left for the caller to do. 1878 */ 1879int msdosfs_extendfile(struct denode *dep, uint32_t count, uint32_t *numAllocated) 1880{ 1881 int error=0; 1882 uint32_t cn, got, totalAllocated; 1883 uint32_t i; 1884 struct msdosfsmount *pmp = dep->de_pmp; 1885 struct buf *bp = NULL; 1886 struct extent *extent = NULL; 1887 1888 KERNEL_DEBUG_CONSTANT(MSDOSFS_EXTENDFILE|DBG_FUNC_START, pmp, dep->de_StartCluster, count, 0, 0); 1889 1890 totalAllocated = 0; 1891 1892 lck_mtx_lock(dep->de_cluster_lock); 1893 lck_mtx_lock(pmp->pm_fat_lock); 1894 1895 /* 1896 * Don't try to extend the root directory on FAT12 or FAT16. 1897 */ 1898 if (dep->de_StartCluster == MSDOSFSROOT 1899 && (dep->de_Attributes & ATTR_DIRECTORY)) 1900 { 1901 printf("msdosfs_extendfile: Cannot grow the root directory on FAT12 or FAT16; returning ENOSPC.\n"); 1902 error = ENOSPC; 1903 goto done; 1904 } 1905 1906 /* 1907 * If the "file's last cluster" is uninitialized, and the file 1908 * is not empty, then calculate the last cluster. 1909 */ 1910 if (dep->de_LastCluster == 0 && 1911 dep->de_StartCluster != 0) 1912 { 1913 error = msdosfs_pcbmap_internal(dep, 0xFFFFFFFF, 1, NULL, NULL, &dep->de_LastCluster); 1914 /* we expect it to return E2BIG */ 1915 if (error != E2BIG) 1916 goto done; 1917 error = 0; 1918 1919 if (dep->de_LastCluster == 0) 1920 { 1921 printf("msdosfs: msdosfs_extendfile: dep->de_LastCluster == 0!\n"); 1922 error = EIO; 1923 goto done; 1924 } 1925 } 1926 1927 /* 1928 * First look for free space contiguous with the end of file. 1929 */ 1930 if (dep->de_StartCluster != 0) 1931 { 1932 cn = dep->de_LastCluster + 1; 1933 1934 got = msdosfs_chainlength(pmp, cn, count); 1935 if (got != 0) 1936 { 1937 error = msdosfs_chainalloc(pmp, cn, got, CLUST_EOFE, NULL, NULL); 1938 if (error) goto done; 1939 1940 /* See if we need to update the cluster extent cache. */ 1941 if (cn == (dep->de_LastCluster+1) && 1942 cn == (dep->de_cluster_physical + dep->de_cluster_count)) 1943 { 1944 /* 1945 * We extended the file's last extent, and it was cached, so 1946 * update its length to include the new allocation. 1947 */ 1948 dep->de_cluster_count += got; 1949 } 1950 1951 /* Point the old end of file to the newly allocated extent. */ 1952 error = msdosfs_fatentry_internal(FAT_SET, pmp, dep->de_LastCluster, NULL, cn); 1953 if (error) 1954 { 1955 msdosfs_freeclusterchain(pmp, cn); 1956 goto done; 1957 } 1958 1959 /* 1960 * Clear directory clusters here, file clusters are cleared by the caller 1961 */ 1962 if (dep->de_Attributes & ATTR_DIRECTORY) { 1963 for (i = 0; i < got; ++i) 1964 { 1965 bp = buf_getblk(pmp->pm_devvp, cntobn(pmp, cn + i), pmp->pm_bpcluster, 0, 0, BLK_META); 1966 buf_clear(bp); 1967 buf_bdwrite(bp); 1968 } 1969 } 1970 1971 count -= got; 1972 dep->de_LastCluster += got; 1973 totalAllocated += got; 1974 } 1975 } 1976 1977 if (count == 0) 1978 goto done; 1979 1980 /* 1981 * Look for contiguous free space, populating the free extent cache. 1982 */ 1983 error = msdosfs_find_free_extents(pmp, pmp->pm_nxtfree, count); 1984 if (error) 1985 goto done; 1986 1987 /* Start by using the known free extents found above. */ 1988 for (i = 0, extent = (struct extent *) pmp->pm_free_extents; 1989 count > 0 && i < pmp->pm_free_extent_count; 1990 ++i, ++extent) 1991 { 1992 /* Grab the next largest free extent. */ 1993 cn = extent->start; 1994 got = extent->count; 1995 if (got > count) 1996 got = count; 1997 1998 /* Allocate it in the FAT. */ 1999 error = msdosfs_chainalloc(pmp, cn, got, CLUST_EOFE, NULL, NULL); 2000 if (error) goto done; 2001 2002 /* Point the old end of file to the newly allocated extent. */ 2003 if (dep->de_LastCluster) 2004 error = msdosfs_fatentry_internal(FAT_SET, pmp, dep->de_LastCluster, NULL, cn); 2005 if (error) 2006 { 2007 msdosfs_freeclusterchain(pmp, cn); 2008 goto done; 2009 } 2010 2011 /* 2012 * Clear directory clusters here, file clusters are cleared by the caller 2013 */ 2014 if (dep->de_Attributes & ATTR_DIRECTORY) { 2015 for (i = 0; i < got; ++i) 2016 { 2017 bp = buf_getblk(pmp->pm_devvp, cntobn(pmp, cn + i), pmp->pm_bpcluster, 0, 0, BLK_META); 2018 buf_clear(bp); 2019 buf_bdwrite(bp); 2020 } 2021 } 2022 2023 /* If the file was empty, set the starting cluster. */ 2024 if (dep->de_StartCluster == 0) 2025 dep->de_StartCluster = cn; 2026 /* Update the file's last cluster. */ 2027 dep->de_LastCluster = cn + got - 1; 2028 2029 count -= got; 2030 totalAllocated += got; 2031 } 2032 2033 /* 2034 * If we used everything in the free extent cache, and it wasn't full, then 2035 * there is no more free space. 2036 */ 2037 if (count > 0 && pmp->pm_free_extent_count < (PAGE_SIZE / sizeof(struct extent))) 2038 { 2039 error = ENOSPC; 2040 goto done; 2041 } 2042 2043 /* Just use whatever free space we can find. */ 2044 while (count > 0) 2045 { 2046 /* Find the next free extent and use it. */ 2047 error = msdosfs_find_next_free(pmp, pmp->pm_nxtfree, pmp->pm_maxcluster+1, count, &cn, &got); 2048 if (error) break; 2049 if (got == 0) 2050 { 2051 error = ENOSPC; 2052 break; 2053 } 2054 2055 /* Allocate it in the FAT. */ 2056 error = msdosfs_chainalloc(pmp, cn, got, CLUST_EOFE, NULL, NULL); 2057 if (error) goto done; 2058 2059 /* 2060 * Point the old end of file to the newly allocated extent. 2061 * NOTE: dep->de_LastCluster must be non-zero by now. 2062 */ 2063 error = msdosfs_fatentry_internal(FAT_SET, pmp, dep->de_LastCluster, NULL, cn); 2064 if (error) 2065 { 2066 msdosfs_freeclusterchain(pmp, cn); 2067 goto done; 2068 } 2069 2070 /* 2071 * Clear directory clusters here, file clusters are cleared by the caller 2072 */ 2073 if (dep->de_Attributes & ATTR_DIRECTORY) { 2074 for (i = 0; i < got; ++i) 2075 { 2076 bp = buf_getblk(pmp->pm_devvp, cntobn(pmp, cn + i), pmp->pm_bpcluster, 0, 0, BLK_META); 2077 buf_clear(bp); 2078 buf_bdwrite(bp); 2079 } 2080 } 2081 2082 /* 2083 * NOTE: The file couldn't have been empty, so no need to set de_StartCluster. 2084 * The file must have had extents allocated via the free extent cache, above. 2085 */ 2086 2087 /* Update the file's last cluster. */ 2088 dep->de_LastCluster = cn + got - 1; 2089 2090 count -= got; 2091 totalAllocated += got; 2092 pmp->pm_nxtfree = cn + got; 2093 } 2094 2095done: 2096 lck_mtx_unlock(pmp->pm_fat_lock); 2097 lck_mtx_unlock(dep->de_cluster_lock); 2098 if (numAllocated) 2099 *numAllocated = totalAllocated; 2100 KERNEL_DEBUG_CONSTANT(MSDOSFS_EXTENDFILE|DBG_FUNC_END, error, totalAllocated, 0, 0, 0); 2101 return error; 2102} 2103 2104 2105/* [2753891] 2106 * Routine to mark a FAT16 or FAT32 volume as "clean" or "dirty" by manipulating the upper bit 2107 * of the FAT entry for cluster 1. Note that this bit is not defined for FAT12 volumes, which 2108 * are always assumed to be dirty. 2109 * 2110 * The msdosfs_fatentry() routine only works on cluster numbers that a file could occupy, so it won't 2111 * manipulate the entry for cluster 1. So we have to do it here. The code is ripped from 2112 * msdosfs_fatentry(), and tailored for cluster 1. 2113 * 2114 * Inputs: 2115 * pmp The MS-DOS volume to mark 2116 * dirty Non-zero if the volume should be marked dirty; zero if it should be marked clean. 2117 * 2118 * Result: 2119 * 0 Success 2120 * EROFS Volume is read-only 2121 * ? (other errors from called routines) 2122 */ 2123int msdosfs_markvoldirty(struct msdosfsmount *pmp, int dirty) 2124{ 2125 int error = 0; 2126 uint32_t fatval; 2127 void *entry; 2128 2129 KERNEL_DEBUG_CONSTANT(MSDOSFS_MARKVOLDIRTY|DBG_FUNC_START, pmp, dirty, 0, 0, 0); 2130 2131 /* FAT12 does not support a "clean" bit, so don't do anything */ 2132 if (FAT12(pmp)) 2133 goto done2; 2134 2135 /* Can't change the bit on a read-only filesystem */ 2136 if (pmp->pm_flags & MSDOSFSMNT_RONLY) 2137 { 2138 error = EROFS; 2139 goto done2; 2140 } 2141 2142 lck_mtx_lock(pmp->pm_fat_lock); 2143 2144 /* Fetch the block containing the FAT entry */ 2145 entry = msdosfs_fat_map(pmp, 1, NULL, NULL, &error); 2146 if (!entry) 2147 goto done; 2148 2149 /* Get the current value of the FAT entry and set/clear the high bit */ 2150 if (FAT32(pmp)) { 2151 /* FAT32 uses bit 27 */ 2152 fatval = getuint32(entry); 2153 if (dirty) 2154 fatval &= 0xF7FFFFFF; /* dirty means clear the "clean" bit */ 2155 else 2156 fatval |= 0x08000000; /* clean means set the "clean" bit */ 2157 putuint32(entry, fatval); 2158 } 2159 else { 2160 /* Must be FAT16; use bit 15 */ 2161 fatval = getuint16(entry); 2162 if (dirty) 2163 fatval &= 0x7FFF; /* dirty means clear the "clean" bit */ 2164 else 2165 fatval |= 0x8000; /* clean means set the "clean" bit */ 2166 putuint16(entry, fatval); 2167 } 2168 2169 /* Write out the modified FAT block immediately */ 2170 pmp->pm_fat_flags |= FAT_CACHE_DIRTY; 2171 error = msdosfs_fat_cache_flush(pmp, IO_SYNC); 2172 2173done: 2174 lck_mtx_unlock(pmp->pm_fat_lock); 2175done2: 2176 KERNEL_DEBUG_CONSTANT(MSDOSFS_MARKVOLDIRTY|DBG_FUNC_END, error, 0, 0, 0, 0); 2177 return error; 2178} 2179 2180