301 lines
7.9 KiB
C
301 lines
7.9 KiB
C
/**
|
|
* bitmap.c - Bitmap handling code. Originated from the Linux-NTFS project.
|
|
*
|
|
* Copyright (c) 2002-2006 Anton Altaparmakov
|
|
* Copyright (c) 2004-2005 Richard Russon
|
|
* Copyright (c) 2004-2008 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_STRING_H
|
|
#include <string.h>
|
|
#endif
|
|
#ifdef HAVE_ERRNO_H
|
|
#include <errno.h>
|
|
#endif
|
|
|
|
#include "types.h"
|
|
#include "attrib.h"
|
|
#include "bitmap.h"
|
|
#include "debug.h"
|
|
#include "logging.h"
|
|
#include "misc.h"
|
|
|
|
/**
|
|
* ntfs_bit_set - set a bit in a field of bits
|
|
* @bitmap: field of bits
|
|
* @bit: bit to set
|
|
* @new_value: value to set bit to (0 or 1)
|
|
*
|
|
* Set the bit @bit in the @bitmap to @new_value. Ignore all errors.
|
|
*/
|
|
void ntfs_bit_set(u8 *bitmap, const u64 bit, const u8 new_value)
|
|
{
|
|
if (!bitmap || new_value > 1)
|
|
return;
|
|
if (!new_value)
|
|
bitmap[bit >> 3] &= ~(1 << (bit & 7));
|
|
else
|
|
bitmap[bit >> 3] |= (1 << (bit & 7));
|
|
}
|
|
|
|
/**
|
|
* ntfs_bit_get - get value of a bit in a field of bits
|
|
* @bitmap: field of bits
|
|
* @bit: bit to get
|
|
*
|
|
* Get and return the value of the bit @bit in @bitmap (0 or 1).
|
|
* Return -1 on error.
|
|
*/
|
|
char ntfs_bit_get(const u8 *bitmap, const u64 bit)
|
|
{
|
|
if (!bitmap)
|
|
return -1;
|
|
return (bitmap[bit >> 3] >> (bit & 7)) & 1;
|
|
}
|
|
|
|
/**
|
|
* ntfs_bit_get_and_set - get value of a bit in a field of bits and set it
|
|
* @bitmap: field of bits
|
|
* @bit: bit to get/set
|
|
* @new_value: value to set bit to (0 or 1)
|
|
*
|
|
* Return the value of the bit @bit and set it to @new_value (0 or 1).
|
|
* Return -1 on error.
|
|
*/
|
|
char ntfs_bit_get_and_set(u8 *bitmap, const u64 bit, const u8 new_value)
|
|
{
|
|
register u8 old_bit, shift;
|
|
|
|
if (!bitmap || new_value > 1)
|
|
return -1;
|
|
shift = bit & 7;
|
|
old_bit = (bitmap[bit >> 3] >> shift) & 1;
|
|
if (new_value != old_bit)
|
|
bitmap[bit >> 3] ^= 1 << shift;
|
|
return old_bit;
|
|
}
|
|
|
|
/**
|
|
* ntfs_bitmap_set_bits_in_run - set a run of bits in a bitmap to a value
|
|
* @na: attribute containing 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)
|
|
*
|
|
* Set @count bits starting at bit @start_bit in the bitmap described by the
|
|
* attribute @na to @value, where @value is either 0 or 1.
|
|
*
|
|
* On success return 0 and on error return -1 with errno set to the error code.
|
|
*/
|
|
static int ntfs_bitmap_set_bits_in_run(ntfs_attr *na, s64 start_bit,
|
|
s64 count, int value)
|
|
{
|
|
s64 bufsize, br;
|
|
u8 *buf, *lastbyte_buf;
|
|
int bit, firstbyte, lastbyte, lastbyte_pos, tmp, ret = -1;
|
|
|
|
if (!na || start_bit < 0 || count < 0) {
|
|
errno = EINVAL;
|
|
ntfs_log_perror("%s: Invalid argument (%p, %lld, %lld)",
|
|
__FUNCTION__, na, (long long)start_bit, (long long)count);
|
|
return -1;
|
|
}
|
|
|
|
bit = start_bit & 7;
|
|
if (bit)
|
|
firstbyte = 1;
|
|
else
|
|
firstbyte = 0;
|
|
|
|
/* Calculate the required buffer size in bytes, capping it at 8kiB. */
|
|
bufsize = ((count - (bit ? 8 - bit : 0) + 7) >> 3) + firstbyte;
|
|
if (bufsize > 8192)
|
|
bufsize = 8192;
|
|
|
|
buf = ntfs_malloc(bufsize);
|
|
if (!buf)
|
|
return -1;
|
|
|
|
/* Depending on @value, zero or set all bits in the allocated buffer. */
|
|
memset(buf, value ? 0xff : 0, bufsize);
|
|
|
|
/* If there is a first partial byte... */
|
|
if (bit) {
|
|
/* read it in... */
|
|
br = ntfs_attr_pread(na, start_bit >> 3, 1, buf);
|
|
if (br != 1) {
|
|
if (br >= 0)
|
|
errno = EIO;
|
|
goto free_err_out;
|
|
}
|
|
/* and set or clear the appropriate bits in it. */
|
|
while ((bit & 7) && count--) {
|
|
if (value)
|
|
*buf |= 1 << bit++;
|
|
else
|
|
*buf &= ~(1 << bit++);
|
|
}
|
|
/* Update @start_bit to the new position. */
|
|
start_bit = (start_bit + 7) & ~7;
|
|
}
|
|
|
|
/* Loop until @count reaches zero. */
|
|
lastbyte = 0;
|
|
lastbyte_buf = NULL;
|
|
bit = count & 7;
|
|
do {
|
|
/* If there is a last partial byte... */
|
|
if (count > 0 && bit) {
|
|
lastbyte_pos = ((count + 7) >> 3) + firstbyte;
|
|
if (!lastbyte_pos) {
|
|
// FIXME: Eeek! BUG!
|
|
ntfs_log_error("Lastbyte is zero. Leaving "
|
|
"inconsistent metadata.\n");
|
|
errno = EIO;
|
|
goto free_err_out;
|
|
}
|
|
/* and it is in the currently loaded bitmap window... */
|
|
if (lastbyte_pos <= bufsize) {
|
|
lastbyte_buf = buf + lastbyte_pos - 1;
|
|
|
|
/* read the byte in... */
|
|
br = ntfs_attr_pread(na, (start_bit + count) >>
|
|
3, 1, lastbyte_buf);
|
|
if (br != 1) {
|
|
// FIXME: Eeek! We need rollback! (AIA)
|
|
if (br >= 0)
|
|
errno = EIO;
|
|
ntfs_log_perror("Reading of last byte "
|
|
"failed (%lld). Leaving inconsistent "
|
|
"metadata", (long long)br);
|
|
goto free_err_out;
|
|
}
|
|
/* and set/clear the appropriate bits in it. */
|
|
while (bit && count--) {
|
|
if (value)
|
|
*lastbyte_buf |= 1 << --bit;
|
|
else
|
|
*lastbyte_buf &= ~(1 << --bit);
|
|
}
|
|
/* We don't want to come back here... */
|
|
bit = 0;
|
|
/* We have a last byte that we have handled. */
|
|
lastbyte = 1;
|
|
}
|
|
}
|
|
|
|
/* Write the prepared buffer to disk. */
|
|
tmp = (start_bit >> 3) - firstbyte;
|
|
br = ntfs_attr_pwrite(na, tmp, bufsize, buf);
|
|
if (br != bufsize) {
|
|
// FIXME: Eeek! We need rollback! (AIA)
|
|
if (br >= 0)
|
|
errno = EIO;
|
|
ntfs_log_perror("Failed to write buffer to bitmap "
|
|
"(%lld != %lld). Leaving inconsistent metadata",
|
|
(long long)br, (long long)bufsize);
|
|
goto free_err_out;
|
|
}
|
|
|
|
/* Update counters. */
|
|
tmp = (bufsize - firstbyte - lastbyte) << 3;
|
|
if (firstbyte) {
|
|
firstbyte = 0;
|
|
/*
|
|
* Re-set the partial first byte so a subsequent write
|
|
* of the buffer does not have stale, incorrect bits.
|
|
*/
|
|
*buf = value ? 0xff : 0;
|
|
}
|
|
start_bit += tmp;
|
|
count -= tmp;
|
|
if (bufsize > (tmp = (count + 7) >> 3))
|
|
bufsize = tmp;
|
|
|
|
if (lastbyte && count != 0) {
|
|
// FIXME: Eeek! BUG!
|
|
ntfs_log_error("Last buffer but count is not zero "
|
|
"(%lld). Leaving inconsistent metadata.\n",
|
|
(long long)count);
|
|
errno = EIO;
|
|
goto free_err_out;
|
|
}
|
|
} while (count > 0);
|
|
|
|
ret = 0;
|
|
|
|
free_err_out:
|
|
free(buf);
|
|
return ret;
|
|
}
|
|
|
|
/**
|
|
* ntfs_bitmap_set_run - set a run of bits in a bitmap
|
|
* @na: attribute containing the bitmap
|
|
* @start_bit: first bit to set
|
|
* @count: number of bits to set
|
|
*
|
|
* Set @count bits starting at bit @start_bit in the bitmap described by the
|
|
* attribute @na.
|
|
*
|
|
* On success return 0 and on error return -1 with errno set to the error code.
|
|
*/
|
|
int ntfs_bitmap_set_run(ntfs_attr *na, s64 start_bit, s64 count)
|
|
{
|
|
int ret;
|
|
|
|
ntfs_log_enter("Set from bit %lld, count %lld\n",
|
|
(long long)start_bit, (long long)count);
|
|
ret = ntfs_bitmap_set_bits_in_run(na, start_bit, count, 1);
|
|
ntfs_log_leave("\n");
|
|
return ret;
|
|
}
|
|
|
|
/**
|
|
* ntfs_bitmap_clear_run - clear a run of bits in a bitmap
|
|
* @na: attribute containing the bitmap
|
|
* @start_bit: first bit to clear
|
|
* @count: number of bits to clear
|
|
*
|
|
* Clear @count bits starting at bit @start_bit in the bitmap described by the
|
|
* attribute @na.
|
|
*
|
|
* On success return 0 and on error return -1 with errno set to the error code.
|
|
*/
|
|
int ntfs_bitmap_clear_run(ntfs_attr *na, s64 start_bit, s64 count)
|
|
{
|
|
int ret;
|
|
|
|
ntfs_log_enter("Clear from bit %lld, count %lld\n",
|
|
(long long)start_bit, (long long)count);
|
|
ret = ntfs_bitmap_set_bits_in_run(na, start_bit, count, 0);
|
|
ntfs_log_leave("\n");
|
|
return ret;
|
|
}
|
|
|