lcnalloc.c

添加linux下对NTFS格式文件系统访问支持的源代码ntfs-3g

/**
 * 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-2007 Szabolcs Szakacsits
 *
 * 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 1024
#define NTFS_LCNALLOC_SKIP  NTFS_LCNALLOC_BSIZE

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, 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 == 1)
		ntfs_cluster_set_zone_pos(vol->mft_lcn, vol->mft_zone_end,
					  &vol->mft_zone_pos, tc);
	else if (zone == 2)
		ntfs_cluster_set_zone_pos(vol->mft_zone_end, vol->nr_clusters,
					  &vol->data1_zone_pos, tc);
	else /* zone == 4 */
		ntfs_cluster_set_zone_pos(0, vol->mft_zone_start, 
					  &vol->data2_zone_pos, tc);
}

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");
	
	for (i = 0; i < size; i++, buf++) {
		
		for (j = 0; j < 8; j++) {
			
			int bit = *buf & (1 << j);
		
			if (bit) {
				if (run > max_range) {
					max_range = run;
					start_pos = i * 8 + j - run;
				}
				run = 0;
			} else 
				run++;
		}		
	}
	
	if (run > max_range)
		start_pos = 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");
	
	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)", pos, 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_trace("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);
		return NULL;
	}

	/* 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;
		}
		return rl;
	}

	buf = ntfs_malloc(NTFS_LCNALLOC_BSIZE);
	if (!buf)
		return NULL;
	/*
	 * 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 = 4;
	} else if (zone_start < vol->mft_zone_end) {
		zone_end = vol->mft_zone_end;
		search_zone = 1;
	} else {
		zone_end = vol->nr_clusters;
		search_zone = 2;
	}
	
	bmp_pos = zone_start;

	/* Loop until all clusters are allocated. */
	clusters = count;
	rlpos = rlsize = 0;
	while (1) {
		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 (1) {
			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;
			
			/*
			 * Coalesce with previous run if adjacent LCNs.
			 * Otherwise, append a new run.
			 */
			if (prev_lcn == lcn + bmp_pos - prev_run_len && rlpos)
				rl[rlpos - 1].length = ++prev_run_len;
			else {
				if (rlpos)