/** * lcnalloc.c - Cluster (de)allocation code. Originated from the Linux-NTFS project. * * Copyright (c) 2002-2004 Anton Altaparmakov * Copyright (c) 2004 Yura Pakhuchiy * Copyright (c) 2004-2008 Szabolcs Szakacsits * Copyright (c) 2008-2009 Jean-Pierre Andre * * This program/include file is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as published * by the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program/include file is distributed in the hope that it will be * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program (in the main directory of the NTFS-3G * distribution in the file COPYING); if not, write to the Free Software * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #ifdef HAVE_CONFIG_H #include "config.h" #endif #ifdef HAVE_STDLIB_H #include <stdlib.h> #endif #ifdef HAVE_STDIO_H #include <stdio.h> #endif #ifdef HAVE_ERRNO_H #include <errno.h> #endif #include "types.h" #include "attrib.h" #include "bitmap.h" #include "debug.h" #include "runlist.h" #include "volume.h" #include "lcnalloc.h" #include "logging.h" #include "misc.h" /* * Plenty possibilities for big optimizations all over in the cluster * allocation, however at the moment the dominant bottleneck (~ 90%) is * the update of the mapping pairs which converges to the cubic Faulhaber's * formula as the function of the number of extents (fragments, runs). */ #define NTFS_LCNALLOC_BSIZE 4096 #define NTFS_LCNALLOC_SKIP NTFS_LCNALLOC_BSIZE enum { ZONE_MFT = 1, ZONE_DATA1 = 2, ZONE_DATA2 = 4 } ; static void ntfs_cluster_set_zone_pos(LCN start, LCN end, LCN *pos, LCN tc) { ntfs_log_trace("pos: %lld tc: %lld\n", (long long)*pos, (long long)tc); if (tc >= end) *pos = start; else if (tc >= start) *pos = tc; } static void ntfs_cluster_update_zone_pos(ntfs_volume *vol, u8 zone, LCN tc) { ntfs_log_trace("tc = %lld, zone = %d\n", (long long)tc, zone); if (zone == ZONE_MFT) ntfs_cluster_set_zone_pos(vol->mft_lcn, vol->mft_zone_end, &vol->mft_zone_pos, tc); else if (zone == ZONE_DATA1) ntfs_cluster_set_zone_pos(vol->mft_zone_end, vol->nr_clusters, &vol->data1_zone_pos, tc); else /* zone == ZONE_DATA2 */ ntfs_cluster_set_zone_pos(0, vol->mft_zone_start, &vol->data2_zone_pos, tc); } /* * Unmark full zones when a cluster has been freed in a full zone * * Next allocation will reuse the freed cluster */ static void update_full_status(ntfs_volume *vol, LCN lcn) { if (lcn >= vol->mft_zone_end) { if (vol->full_zones & ZONE_DATA1) { ntfs_cluster_update_zone_pos(vol, ZONE_DATA1, lcn); vol->full_zones &= ~ZONE_DATA1; } } else if (lcn < vol->mft_zone_start) { if (vol->full_zones & ZONE_DATA2) { ntfs_cluster_update_zone_pos(vol, ZONE_DATA2, lcn); vol->full_zones &= ~ZONE_DATA2; } } else { if (vol->full_zones & ZONE_MFT) { ntfs_cluster_update_zone_pos(vol, ZONE_MFT, lcn); vol->full_zones &= ~ZONE_MFT; } } } static s64 max_empty_bit_range(unsigned char *buf, int size) { int i, j, run = 0; int max_range = 0; s64 start_pos = -1; ntfs_log_trace("Entering\n"); i = 0; while (i < size) { switch (*buf) { case 0 : do { buf++; run += 8; i++; } while ((i < size) && !*buf); break; case 255 : if (run > max_range) { max_range = run; start_pos = (s64)i * 8 - run; } run = 0; do { buf++; i++; } while ((i < size) && (*buf == 255)); break; default : for (j = 0; j < 8; j++) { int bit = *buf & (1 << j); if (bit) { if (run > max_range) { max_range = run; start_pos = (s64)i * 8 + (j - run); } run = 0; } else run++; } i++; buf++; } } if (run > max_range) start_pos = (s64)i * 8 - run; return start_pos; } static int bitmap_writeback(ntfs_volume *vol, s64 pos, s64 size, void *b, u8 *writeback) { s64 written; ntfs_log_trace("Entering\n"); if (!*writeback) return 0; *writeback = 0; written = ntfs_attr_pwrite(vol->lcnbmp_na, pos, size, b); if (written != size) { if (!written) errno = EIO; ntfs_log_perror("Bitmap write error (%lld, %lld)", (long long)pos, (long long)size); return -1; } return 0; } /** * ntfs_cluster_alloc - allocate clusters on an ntfs volume * @vol: mounted ntfs volume on which to allocate the clusters * @start_vcn: vcn to use for the first allocated cluster * @count: number of clusters to allocate * @start_lcn: starting lcn at which to allocate the clusters (or -1 if none) * @zone: zone from which to allocate the clusters * * Allocate @count clusters preferably starting at cluster @start_lcn or at the * current allocator position if @start_lcn is -1, on the mounted ntfs volume * @vol. @zone is either DATA_ZONE for allocation of normal clusters and * MFT_ZONE for allocation of clusters for the master file table, i.e. the * $MFT/$DATA attribute. * * On success return a runlist describing the allocated cluster(s). * * On error return NULL with errno set to the error code. * * Notes on the allocation algorithm * ================================= * * There are two data zones. First is the area between the end of the mft zone * and the end of the volume, and second is the area between the start of the * volume and the start of the mft zone. On unmodified/standard NTFS 1.x * volumes, the second data zone doesn't exist due to the mft zone being * expanded to cover the start of the volume in order to reserve space for the * mft bitmap attribute. * * The complexity stems from the need of implementing the mft vs data zoned * approach and from the fact that we have access to the lcn bitmap via up to * NTFS_LCNALLOC_BSIZE bytes at a time, so we need to cope with crossing over * boundaries of two buffers. Further, the fact that the allocator allows for * caller supplied hints as to the location of where allocation should begin * and the fact that the allocator keeps track of where in the data zones the * next natural allocation should occur, contribute to the complexity of the * function. But it should all be worthwhile, because this allocator: * 1) implements MFT zone reservation * 2) causes reduction in fragmentation. * The code is not optimized for speed. */ runlist *ntfs_cluster_alloc(ntfs_volume *vol, VCN start_vcn, s64 count, LCN start_lcn, const NTFS_CLUSTER_ALLOCATION_ZONES zone) { LCN zone_start, zone_end; /* current search range */ LCN last_read_pos, lcn; LCN bmp_pos; /* current bit position inside the bitmap */ LCN prev_lcn = 0, prev_run_len = 0; s64 clusters, br; runlist *rl = NULL, *trl; u8 *buf, *byte, bit, writeback; u8 pass = 1; /* 1: inside zone; 2: start of zone */ u8 search_zone; /* 4: data2 (start) 1: mft (middle) 2: data1 (end) */ u8 done_zones = 0; u8 has_guess, used_zone_pos; int err = 0, rlpos, rlsize, buf_size; ntfs_log_enter("Entering with count = 0x%llx, start_lcn = 0x%llx, " "zone = %s_ZONE.\n", (long long)count, (long long) start_lcn, zone == MFT_ZONE ? "MFT" : "DATA"); if (!vol || count < 0 || start_lcn < -1 || !vol->lcnbmp_na || (s8)zone < FIRST_ZONE || zone > LAST_ZONE) { errno = EINVAL; ntfs_log_perror("%s: vcn: %lld, count: %lld, lcn: %lld", __FUNCTION__, (long long)start_vcn, (long long)count, (long long)start_lcn); goto out; } /* Return empty runlist if @count == 0 */ if (!count) { rl = ntfs_malloc(0x1000); if (rl) { rl[0].vcn = start_vcn; rl[0].lcn = LCN_RL_NOT_MAPPED; rl[0].length = 0; } goto out; } buf = ntfs_malloc(NTFS_LCNALLOC_BSIZE); if (!buf) goto out; /* * If no @start_lcn was requested, use the current zone * position otherwise use the requested @start_lcn. */ has_guess = 1; zone_start = start_lcn; if (zone_start < 0) { if (zone == DATA_ZONE) zone_start = vol->data1_zone_pos; else zone_start = vol->mft_zone_pos; has_guess = 0; } used_zone_pos = has_guess ? 0 : 1; if (!zone_start || zone_start == vol->mft_zone_start || zone_start == vol->mft_zone_end) pass = 2; if (zone_start < vol->mft_zone_start) { zone_end = vol->mft_zone_start; search_zone = ZONE_DATA2; } else if (zone_start < vol->mft_zone_end) { zone_end = vol->mft_zone_end; search_zone = ZONE_MFT; } else { zone_end = vol->nr_clusters; search_zone = ZONE_DATA1; } bmp_pos = zone_start; /* Loop until all clusters are allocated. */ clusters = count; rlpos = rlsize = 0; while (1) { /* check whether we have exhausted the current zone */ if (search_zone & vol->full_zones) goto zone_pass_done; last_read_pos = bmp_pos >> 3; br = ntfs_attr_pread(vol->lcnbmp_na, last_read_pos, NTFS_LCNALLOC_BSIZE, buf); if (br <= 0) { if (!br) goto zone_pass_done; err = errno; ntfs_log_perror("Reading $BITMAP failed"); goto err_ret; } /* * We might have read less than NTFS_LCNALLOC_BSIZE bytes * if we are close to the end of the attribute. */ buf_size = (int)br << 3; lcn = bmp_pos & 7; bmp_pos &= ~7; writeback = 0; while (lcn < buf_size) { byte = buf + (lcn >> 3); bit = 1 << (lcn & 7); if (has_guess) { if (*byte & bit) { has_guess = 0; break; } } else { lcn = max_empty_bit_range(buf, br); if (lcn < 0) break; has_guess = 1; continue; } /* First free bit is at lcn + bmp_pos. */ /* Reallocate memory if necessary. */ if ((rlpos + 2) * (int)sizeof(runlist) >= rlsize) { rlsize += 4096; trl = realloc(rl, rlsize); if (!trl) { err = ENOMEM; ntfs_log_perror("realloc() failed"); goto wb_err_ret; } rl = trl; } /* Allocate the bitmap bit. */ *byte |= bit; writeback = 1; if (vol->free_clusters <= 0) ntfs_log_error("Non-positive free clusters " "(%lld)!\n", (long long)vol->free_clusters); else vol->free_clusters--; /* * Coalesce with previous run if adjacent LCNs. * Otherwise, append a new run. */ if (prev_lcn == lcn + bmp_pos - prev_run_len && rlpos) { ntfs_log_debug("Cluster coalesce: prev_lcn: " "%lld lcn: %lld bmp_pos: %lld " "prev_run_len: %lld\n", (long long)prev_lcn, (long long)lcn, (long long)bmp_pos, (long long)prev_run_len); rl[rlpos - 1].length = ++prev_run_len; } else { if (rlpos) rl[rlpos].vcn = rl[rlpos - 1].vcn + prev_run_len; else { rl[rlpos].vcn = start_vcn; ntfs_log_debug("Start_vcn: %lld\n", (long long)start_vcn); } rl[rlpos].lcn = prev_lcn = lcn + bmp_pos; rl[rlpos].length = prev_run_len = 1; rlpos++; } ntfs_log_debug("RUN: %-16lld %-16lld %-16lld\n", (long long)rl[rlpos - 1].vcn, (long long)rl[rlpos - 1].lcn, (long long)rl[rlpos - 1].length); /* Done? */ if (!--clusters) { if (used_zone_pos) ntfs_cluster_update_zone_pos(vol, search_zone, lcn + bmp_pos + 1 + NTFS_LCNALLOC_SKIP); goto done_ret; } lcn++; } if (bitmap_writeback(vol, last_read_pos, br, buf, &writeback)) { err = errno; goto err_ret; } if (!used_zone_pos) { used_zone_pos = 1; if (search_zone == ZONE_MFT) zone_start = vol->mft_zone_pos; else if (search_zone == ZONE_DATA1) zone_start = vol->data1_zone_pos; else zone_start = vol->data2_zone_pos; if (!zone_start || zone_start == vol->mft_zone_start || zone_start == vol->mft_zone_end) pass = 2; bmp_pos = zone_start; } else bmp_pos += buf_size; if (bmp_pos < zone_end) continue; zone_pass_done: ntfs_log_trace("Finished current zone pass(%i).\n", pass); if (pass == 1) { pass = 2; zone_end = zone_start; if (search_zone == ZONE_MFT) zone_start = vol->mft_zone_start; else if (search_zone == ZONE_DATA1) zone_start = vol->mft_zone_end; else zone_start = 0; /* Sanity check. */ if (zone_end < zone_start) zone_end = zone_start; bmp_pos = zone_start; continue; } /* pass == 2 */ done_zones_check: done_zones |= search_zone; vol->full_zones |= search_zone; if (done_zones < (ZONE_MFT + ZONE_DATA1 + ZONE_DATA2)) { ntfs_log_trace("Switching zone.\n"); pass = 1; if (rlpos) { LCN tc = rl[rlpos - 1].lcn + rl[rlpos - 1].length + NTFS_LCNALLOC_SKIP; if (used_zone_pos) ntfs_cluster_update_zone_pos(vol, search_zone, tc); } switch (search_zone) { case ZONE_MFT: ntfs_log_trace("Zone switch: mft -> data1\n"); switch_to_data1_zone: search_zone = ZONE_DATA1; zone_start = vol->data1_zone_pos; zone_end = vol->nr_clusters; if (zone_start == vol->mft_zone_end) pass = 2; break; case ZONE_DATA1: ntfs_log_trace("Zone switch: data1 -> data2\n"); search_zone = ZONE_DATA2; zone_start = vol->data2_zone_pos; zone_end = vol->mft_zone_start; if (!zone_start) pass = 2; break; case ZONE_DATA2: if (!(done_zones & ZONE_DATA1)) { ntfs_log_trace("data2 -> data1\n"); goto switch_to_data1_zone; } ntfs_log_trace("Zone switch: data2 -> mft\n"); search_zone = ZONE_MFT; zone_start = vol->mft_zone_pos; zone_end = vol->mft_zone_end; if (zone_start == vol->mft_zone_start) pass = 2; break; } bmp_pos = zone_start; if (zone_start == zone_end) { ntfs_log_trace("Empty zone, skipped.\n"); goto done_zones_check; } continue; } ntfs_log_trace("All zones are finished, no space on device.\n"); err = ENOSPC; goto err_ret; } done_ret: ntfs_log_debug("At done_ret.\n"); /* Add runlist terminator element. */ rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length; rl[rlpos].lcn = LCN_RL_NOT_MAPPED; rl[rlpos].length = 0; if (bitmap_writeback(vol, last_read_pos, br, buf, &writeback)) { err = errno; goto err_ret; } done_err_ret: free(buf); if (err) { errno = err; ntfs_log_perror("Failed to allocate clusters"); rl = NULL; } out: ntfs_log_leave("\n"); return rl; wb_err_ret: ntfs_log_trace("At wb_err_ret.\n"); if (bitmap_writeback(vol, last_read_pos, br, buf, &writeback)) err = errno; err_ret: ntfs_log_trace("At err_ret.\n"); if (rl) { /* Add runlist terminator element. */ rl[rlpos].vcn = rl[rlpos - 1].vcn + rl[rlpos - 1].length; rl[rlpos].lcn = LCN_RL_NOT_MAPPED; rl[rlpos].length = 0; ntfs_debug_runlist_dump(rl); ntfs_cluster_free_from_rl(vol, rl); free(rl); rl = NULL; } goto done_err_ret; } /** * ntfs_cluster_free_from_rl - free clusters from runlist * @vol: mounted ntfs volume on which to free the clusters * @rl: runlist from which deallocate clusters * * On success return 0 and on error return -1 with errno set to the error code. */ int ntfs_cluster_free_from_rl(ntfs_volume *vol, runlist *rl) { s64 nr_freed = 0; int ret = -1; ntfs_log_trace("Entering.\n"); for (; rl->length; rl++) { ntfs_log_trace("Dealloc lcn 0x%llx, len 0x%llx.\n", (long long)rl->lcn, (long long)rl->length); if (rl->lcn >= 0) { update_full_status(vol,rl->lcn); if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn, rl->length)) { ntfs_log_perror("Cluster deallocation failed " "(%lld, %lld)", (long long)rl->lcn, (long long)rl->length); goto out; } nr_freed += rl->length ; } } ret = 0; out: vol->free_clusters += nr_freed; if (vol->free_clusters > vol->nr_clusters) ntfs_log_error("Too many free clusters (%lld > %lld)!", (long long)vol->free_clusters, (long long)vol->nr_clusters); return ret; } /* * Basic cluster run free * Returns 0 if successful */ int ntfs_cluster_free_basic(ntfs_volume *vol, s64 lcn, s64 count) { s64 nr_freed = 0; int ret = -1; ntfs_log_trace("Entering.\n"); ntfs_log_trace("Dealloc lcn 0x%llx, len 0x%llx.\n", (long long)lcn, (long long)count); if (lcn >= 0) { update_full_status(vol,lcn); if (ntfs_bitmap_clear_run(vol->lcnbmp_na, lcn, count)) { ntfs_log_perror("Cluster deallocation failed " "(%lld, %lld)", (long long)lcn, (long long)count); goto out; } nr_freed += count; } ret = 0; out: vol->free_clusters += nr_freed; if (vol->free_clusters > vol->nr_clusters) ntfs_log_error("Too many free clusters (%lld > %lld)!", (long long)vol->free_clusters, (long long)vol->nr_clusters); return ret; } /** * ntfs_cluster_free - free clusters on an ntfs volume * @vol: mounted ntfs volume on which to free the clusters * @na: attribute whose runlist describes the clusters to free * @start_vcn: vcn in @rl at which to start freeing clusters * @count: number of clusters to free or -1 for all clusters * * Free @count clusters starting at the cluster @start_vcn in the runlist * described by the attribute @na from the mounted ntfs volume @vol. * * If @count is -1, all clusters from @start_vcn to the end of the runlist * are deallocated. * * On success return the number of deallocated clusters (not counting sparse * clusters) and on error return -1 with errno set to the error code. */ int ntfs_cluster_free(ntfs_volume *vol, ntfs_attr *na, VCN start_vcn, s64 count) { runlist *rl; s64 delta, to_free, nr_freed = 0; int ret = -1; if (!vol || !vol->lcnbmp_na || !na || start_vcn < 0 || (count < 0 && count != -1)) { ntfs_log_trace("Invalid arguments!\n"); errno = EINVAL; return -1; } ntfs_log_enter("Entering for inode 0x%llx, attr 0x%x, count 0x%llx, " "vcn 0x%llx.\n", (unsigned long long)na->ni->mft_no, na->type, (long long)count, (long long)start_vcn); rl = ntfs_attr_find_vcn(na, start_vcn); if (!rl) { if (errno == ENOENT) ret = 0; goto leave; } if (rl->lcn < 0 && rl->lcn != LCN_HOLE) { errno = EIO; ntfs_log_perror("%s: Unexpected lcn (%lld)", __FUNCTION__, (long long)rl->lcn); goto leave; } /* Find the starting cluster inside the run that needs freeing. */ delta = start_vcn - rl->vcn; /* The number of clusters in this run that need freeing. */ to_free = rl->length - delta; if (count >= 0 && to_free > count) to_free = count; if (rl->lcn != LCN_HOLE) { /* Do the actual freeing of the clusters in this run. */ update_full_status(vol,rl->lcn + delta); if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn + delta, to_free)) goto leave; nr_freed = to_free; } /* Go to the next run and adjust the number of clusters left to free. */ ++rl; if (count >= 0) count -= to_free; /* * Loop over the remaining runs, using @count as a capping value, and * free them. */ for (; rl->length && count != 0; ++rl) { // FIXME: Need to try ntfs_attr_map_runlist() for attribute // list support! (AIA) if (rl->lcn < 0 && rl->lcn != LCN_HOLE) { // FIXME: Eeek! We need rollback! (AIA) errno = EIO; ntfs_log_perror("%s: Invalid lcn (%lli)", __FUNCTION__, (long long)rl->lcn); goto out; } /* The number of clusters in this run that need freeing. */ to_free = rl->length; if (count >= 0 && to_free > count) to_free = count; if (rl->lcn != LCN_HOLE) { update_full_status(vol,rl->lcn); if (ntfs_bitmap_clear_run(vol->lcnbmp_na, rl->lcn, to_free)) { // FIXME: Eeek! We need rollback! (AIA) ntfs_log_perror("%s: Clearing bitmap run failed", __FUNCTION__); goto out; } nr_freed += to_free; } if (count >= 0) count -= to_free; } if (count != -1 && count != 0) { // FIXME: Eeek! BUG() errno = EIO; ntfs_log_perror("%s: count still not zero (%lld)", __FUNCTION__, (long long)count); goto out; } ret = nr_freed; out: vol->free_clusters += nr_freed ; if (vol->free_clusters > vol->nr_clusters) ntfs_log_error("Too many free clusters (%lld > %lld)!", (long long)vol->free_clusters, (long long)vol->nr_clusters); leave: ntfs_log_leave("\n"); return ret; }