ntfs_bitmap.c   [plain text]


/*
 * ntfs_bitmap.c - NTFS kernel bitmap handling.
 *
 * Copyright (c) 2006-2008 Anton Altaparmakov.  All Rights Reserved.
 * Portions Copyright (c) 2006-2008 Apple Inc.  All Rights Reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer. 
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution. 
 * 3. Neither the name of Apple Inc. ("Apple") nor the names of its
 *    contributors may be used to endorse or promote products derived from this
 *    software without specific prior written permission. 
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * ALTERNATIVELY, provided that this notice and licensing terms are retained in
 * full, this file may be redistributed and/or modified under the terms of the
 * GNU General Public License (GPL) Version 2, in which case the provisions of
 * that version of the GPL will apply to you instead of the license terms
 * above.  You can obtain a copy of the GPL Version 2 at
 * http://developer.apple.com/opensource/licenses/gpl-2.txt.
 */

#include <sys/errno.h>

#include <string.h>

#include <kern/debug.h>

#include "ntfs_bitmap.h"
#include "ntfs_debug.h"
#include "ntfs_inode.h"
#include "ntfs_page.h"
#include "ntfs_types.h"
#include "ntfs_volume.h"

/**
 * __ntfs_bitmap_set_bits_in_run - set a run of bits in a bitmap to a value
 * @ni:			ntfs inode describing the bitmap
 * @start_bit:		first bit to set
 * @count:		number of bits to set
 * @value:		value to set the bits to (i.e. 0 or 1)
 * @is_rollback:	if true this is a rollback operation
 *
 * Set @count bits starting at bit @start_bit in the bitmap described by the
 * ntfs inode @ni to @value, where @value is either 0 or 1.
 *
 * @is_rollback should always be false, it is for internal use to rollback
 * errors.  You probably want to use ntfs_bitmap_set_bits_in_run() instead.
 *
 * Return 0 on success and errno on error.
 *
 * Locking: The caller must hold @ni->lock.
 */
errno_t __ntfs_bitmap_set_bits_in_run(ntfs_inode *ni, const s64 start_bit,
		const s64 count, const u8 value, const BOOL is_rollback)
{
	s64 rem, cnt = count;
	u64 ofs, end_ofs;
	upl_t upl;
	upl_page_info_array_t pl;
	u8 *kaddr;
	unsigned pos, len;
	errno_t err, err2;
	u8 bit;

	if (!ni)
		panic("%s(): !ni\n", __FUNCTION__);
	ntfs_debug("Entering for mft_no 0x%llx, start_bit 0x%llx, count "
			"0x%llx, value %u.%s", (unsigned long long)ni->mft_no,
			(unsigned long long)start_bit, (unsigned long long)cnt,
			(unsigned)value, is_rollback ? " (rollback)" : "");
	if (start_bit < 0)
		panic("%s(): start_bit < 0\n", __FUNCTION__);
	if (cnt < 0)
		panic("%s(): cnt < 0\n", __FUNCTION__);
	if (value > 1)
		panic("%s(): value > 1\n", __FUNCTION__);
	/*
	 * Calculate the offsets for the pages containing the first and last
	 * bits, i.e. @start_bit and @start_bit + @cnt - 1, respectively.
	 */
	ofs = (start_bit >> 3) & ~PAGE_MASK_64;
	end_ofs = ((start_bit + cnt - 1) >> 3) & ~PAGE_MASK_64;
	/* Get the page containing the first bit (@start_bit). */
	err = ntfs_page_map(ni, ofs, &upl, &pl, &kaddr, TRUE);
	if (err) {
		if (!is_rollback)
			ntfs_error(ni->vol->mp, "Failed to map first page "
					"(error %d), aborting.", err);
		return err;
	}
	/* Set @pos to the position of the byte containing @start_bit. */
	pos = (start_bit >> 3) & PAGE_MASK;
	/* Calculate the position of @start_bit in the first byte. */
	bit = start_bit & 7;
	/* If the first byte is partial, modify the appropriate bits in it. */
	if (bit) {
		u8 *byte = kaddr + pos;
		while ((bit & 7) && cnt) {
			cnt--;
			if (value)
				*byte |= 1 << bit++;
			else
				*byte &= ~(1 << bit++);
		}
		/* If we are done, unmap the page and return success. */
		if (!cnt)
			goto done;
		/* Update @pos to the new position. */
		pos++;
	}
	/*
	 * Depending on @value, modify all remaining whole bytes in the page up
	 * to @cnt.
	 */
	len = PAGE_SIZE - pos;
	rem = cnt >> 3;
	if (len > rem)
		len = rem;
	memset(kaddr + pos, value ? 0xff : 0, len);
	cnt -= len << 3;
	/* Update @len to point to the first not-done byte in the page. */
	if (cnt < 8)
		len += pos;
	/* If we are not in the last page, deal with all subsequent pages. */
	while (ofs < end_ofs) {
		if (cnt <= 0)
			panic("%s(): cnt <= 0\n", __FUNCTION__);
		/* Mark the current page dirty and unmap it. */
		ntfs_page_unmap(ni, upl, pl, TRUE);
		/* Update @ofs and get the next page. */
		ofs += PAGE_SIZE;
		err = ntfs_page_map(ni, ofs, &upl, &pl, &kaddr, TRUE);
		if (err)
			goto rollback;
		/*
		 * Depending on @value, modify all remaining whole bytes in the
		 * page up to @cnt.
		 */
		len = PAGE_SIZE;
		rem = cnt >> 3;
		if (len > rem)
			len = rem;
		memset(kaddr, value ? 0xff : 0, len);
		cnt -= len << 3;
	}
	/*
	 * The currently mapped page is the last one.  If the last byte is
	 * partial, modify the appropriate bits in it.  Note, @len is the
	 * position of the last byte inside the page.
	 */
	if (cnt) {
		u8 *byte;

		if (cnt > 7)
			panic("%s(): cnt > 7\n", __FUNCTION__);
		bit = cnt;
		byte = kaddr + len;
		while (bit--) {
			if (value)
				*byte |= 1 << bit;
			else
				*byte &= ~(1 << bit);
		}
	}
done:
	/* We are done.  Unmap the page and return success. */
	ntfs_page_unmap(ni, upl, pl, TRUE);
	ntfs_debug("Done.");
	return 0;
rollback:
	/*
	 * Current state:
	 *	- no pages are mapped
	 *	- @count - @cnt is the number of bits that have been modified
	 */
	if (is_rollback)
		return err;
	err2 = 0;
	if (count != cnt)
		err2 = __ntfs_bitmap_set_bits_in_run(ni, start_bit,
				count - cnt, value ? 0 : 1, TRUE);
	if (!err2) {
		/* Rollback was successful. */
		ntfs_error(ni->vol->mp, "Failed to map subsequent page (error "
				"%d), aborting.", err);
	} else {
		/* Rollback failed. */
		ntfs_error(ni->vol->mp, "Failed to map subsequent page (error "
				"%d) and rollback failed (error %d).  "
				"Aborting and leaving inconsistent metadata.  "
				"Unmount and run chkdsk.", err, err2);
		NVolSetErrors(ni->vol);
	}
	return err;
}