release/src/router/ntfs-3g/libntfs-3g/bitmap.c

   1 /**
   2  * bitmap.c - Bitmap handling code. Originated from the Linux-NTFS project.
   3  *
   4  * Copyright (c) 2002-2006 Anton Altaparmakov
   5  * Copyright (c) 2004-2005 Richard Russon
   6  * Copyright (c) 2004-2008 Szabolcs Szakacsits
   7  *
   8  * This program/include file is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU General Public License as published
  10  * by the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program/include file is distributed in the hope that it will be
  14  * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  15  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program (in the main directory of the NTFS-3G
  20  * distribution in the file COPYING); if not, write to the Free Software
  21  * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  22  */
  23
  24 #ifdef HAVE_CONFIG_H
  25 #include "config.h"
  26 #endif
  27
  28 #ifdef HAVE_STDLIB_H
  29 #include <stdlib.h>
  30 #endif
  31 #ifdef HAVE_STDIO_H
  32 #include <stdio.h>
  33 #endif
  34 #ifdef HAVE_STRING_H
  35 #include <string.h>
  36 #endif
  37 #ifdef HAVE_ERRNO_H
  38 #include <errno.h>
  39 #endif
  40
  41 #include "types.h"
  42 #include "attrib.h"
  43 #include "bitmap.h"
  44 #include "debug.h"
  45 #include "logging.h"
  46 #include "misc.h"
  47
  48 /**
  49  * ntfs_bit_set - set a bit in a field of bits
  50  * @bitmap:     field of bits
  51  * @bit:        bit to set
  52  * @new_value:  value to set bit to (0 or 1)
  53  *
  54  * Set the bit @bit in the @bitmap to @new_value. Ignore all errors.
  55  */
  56 void ntfs_bit_set(u8 *bitmap, const u64 bit, const u8 new_value)
  57 {
  58         if (!bitmap || new_value > 1)
  59                 return;
  60         if (!new_value)
  61                 bitmap[bit >> 3] &= ~(1 << (bit & 7));
  62         else
  63                 bitmap[bit >> 3] |= (1 << (bit & 7));
  64 }
  65
  66 /**
  67  * ntfs_bit_get - get value of a bit in a field of bits
  68  * @bitmap:     field of bits
  69  * @bit:        bit to get
  70  *
  71  * Get and return the value of the bit @bit in @bitmap (0 or 1).
  72  * Return -1 on error.
  73  */
  74 char ntfs_bit_get(const u8 *bitmap, const u64 bit)
  75 {
  76         if (!bitmap)
  77                 return -1;
  78         return (bitmap[bit >> 3] >> (bit & 7)) & 1;
  79 }
  80
  81 /**
  82  * ntfs_bit_get_and_set - get value of a bit in a field of bits and set it
  83  * @bitmap:     field of bits
  84  * @bit:        bit to get/set
  85  * @new_value:  value to set bit to (0 or 1)
  86  *
  87  * Return the value of the bit @bit and set it to @new_value (0 or 1).
  88  * Return -1 on error.
  89  */
  90 char ntfs_bit_get_and_set(u8 *bitmap, const u64 bit, const u8 new_value)
  91 {
  92         register u8 old_bit, shift;
  93
  94         if (!bitmap || new_value > 1)
  95                 return -1;
  96         shift = bit & 7;
  97         old_bit = (bitmap[bit >> 3] >> shift) & 1;
  98         if (new_value != old_bit)
  99                 bitmap[bit >> 3] ^= 1 << shift;
 100         return old_bit;
 101 }
 102
 103 /**
 104  * ntfs_bitmap_set_bits_in_run - set a run of bits in a bitmap to a value
 105  * @na:         attribute containing the bitmap
 106  * @start_bit:  first bit to set
 107  * @count:      number of bits to set
 108  * @value:      value to set the bits to (i.e. 0 or 1)
 109  *
 110  * Set @count bits starting at bit @start_bit in the bitmap described by the
 111  * attribute @na to @value, where @value is either 0 or 1.
 112  *
 113  * On success return 0 and on error return -1 with errno set to the error code.
 114  */
 115 static int ntfs_bitmap_set_bits_in_run(ntfs_attr *na, s64 start_bit,
 116                                        s64 count, int value)
 117 {
 118         s64 bufsize, br;
 119         u8 *buf, *lastbyte_buf;
 120         int bit, firstbyte, lastbyte, lastbyte_pos, tmp, ret = -1;
 121
 122         if (!na || start_bit < 0 || count < 0) {
 123                 errno = EINVAL;
 124                 ntfs_log_perror("%s: Invalid argument (%p, %lld, %lld)",
 125                         __FUNCTION__, na, (long long)start_bit, (long long)count);
 126                 return -1;
 127         }
 128
 129         bit = start_bit & 7;
 130         if (bit)
 131                 firstbyte = 1;
 132         else
 133                 firstbyte = 0;
 134
 135         /* Calculate the required buffer size in bytes, capping it at 8kiB. */
 136         bufsize = ((count - (bit ? 8 - bit : 0) + 7) >> 3) + firstbyte;
 137         if (bufsize > 8192)
 138                 bufsize = 8192;
 139
 140         buf = ntfs_malloc(bufsize);
 141         if (!buf)
 142                 return -1;
 143
 144         /* Depending on @value, zero or set all bits in the allocated buffer. */
 145         memset(buf, value ? 0xff : 0, bufsize);
 146
 147         /* If there is a first partial byte... */
 148         if (bit) {
 149                 /* read it in... */
 150                 br = ntfs_attr_pread(na, start_bit >> 3, 1, buf);
 151                 if (br != 1) {
 152                         if (br >= 0)
 153                                 errno = EIO;
 154                         goto free_err_out;
 155                 }
 156                 /* and set or clear the appropriate bits in it. */
 157                 while ((bit & 7) && count--) {
 158                         if (value)
 159                                 *buf |= 1 << bit++;
 160                         else
 161                                 *buf &= ~(1 << bit++);
 162                 }
 163                 /* Update @start_bit to the new position. */
 164                 start_bit = (start_bit + 7) & ~7;
 165         }
 166
 167         /* Loop until @count reaches zero. */
 168         lastbyte = 0;
 169         lastbyte_buf = NULL;
 170         bit = count & 7;
 171         do {
 172                 /* If there is a last partial byte... */
 173                 if (count > 0 && bit) {
 174                         lastbyte_pos = ((count + 7) >> 3) + firstbyte;
 175                         if (!lastbyte_pos) {
 176                                 // FIXME: Eeek! BUG!
 177                                 ntfs_log_error("Lastbyte is zero. Leaving "
 178                                                 "inconsistent metadata.\n");
 179                                 errno = EIO;
 180                                 goto free_err_out;
 181                         }
 182                         /* and it is in the currently loaded bitmap window... */
 183                         if (lastbyte_pos <= bufsize) {
 184                                 lastbyte_buf = buf + lastbyte_pos - 1;
 185
 186                                 /* read the byte in... */
 187                                 br = ntfs_attr_pread(na, (start_bit + count) >>
 188                                                 3, 1, lastbyte_buf);
 189                                 if (br != 1) {
 190                                         // FIXME: Eeek! We need rollback! (AIA)
 191                                         if (br >= 0)
 192                                                 errno = EIO;
 193                                         ntfs_log_perror("Reading of last byte "
 194                                                 "failed (%lld). Leaving inconsistent "
 195                                                 "metadata", (long long)br);
 196                                         goto free_err_out;
 197                                 }
 198                                 /* and set/clear the appropriate bits in it. */
 199                                 while (bit && count--) {
 200                                         if (value)
 201                                                 *lastbyte_buf |= 1 << --bit;
 202                                         else
 203                                                 *lastbyte_buf &= ~(1 << --bit);
 204                                 }
 205                                 /* We don't want to come back here... */
 206                                 bit = 0;
 207                                 /* We have a last byte that we have handled. */
 208                                 lastbyte = 1;
 209                         }
 210                 }
 211
 212                 /* Write the prepared buffer to disk. */
 213                 tmp = (start_bit >> 3) - firstbyte;
 214                 br = ntfs_attr_pwrite(na, tmp, bufsize, buf);
 215                 if (br != bufsize) {
 216                         // FIXME: Eeek! We need rollback! (AIA)
 217                         if (br >= 0)
 218                                 errno = EIO;
 219                         ntfs_log_perror("Failed to write buffer to bitmap "
 220                                 "(%lld != %lld). Leaving inconsistent metadata",
 221                                 (long long)br, (long long)bufsize);
 222                         goto free_err_out;
 223                 }
 224
 225                 /* Update counters. */
 226                 tmp = (bufsize - firstbyte - lastbyte) << 3;
 227                 if (firstbyte) {
 228                         firstbyte = 0;
 229                         /*
 230                          * Re-set the partial first byte so a subsequent write
 231                          * of the buffer does not have stale, incorrect bits.
 232                          */
 233                         *buf = value ? 0xff : 0;
 234                 }
 235                 start_bit += tmp;
 236                 count -= tmp;
 237                 if (bufsize > (tmp = (count + 7) >> 3))
 238                         bufsize = tmp;
 239
 240                 if (lastbyte && count != 0) {
 241                         // FIXME: Eeek! BUG!
 242                         ntfs_log_error("Last buffer but count is not zero "
 243                                        "(%lld). Leaving inconsistent metadata.\n",
 244                                        (long long)count);
 245                         errno = EIO;
 246                         goto free_err_out;
 247                 }
 248         } while (count > 0);
 249
 250         ret = 0;
 251
 252 free_err_out:
 253         free(buf);
 254         return ret;
 255 }
 256
 257 /**
 258  * ntfs_bitmap_set_run - set a run of bits in a bitmap
 259  * @na:         attribute containing the bitmap
 260  * @start_bit:  first bit to set
 261  * @count:      number of bits to set
 262  *
 263  * Set @count bits starting at bit @start_bit in the bitmap described by the
 264  * attribute @na.
 265  *
 266  * On success return 0 and on error return -1 with errno set to the error code.
 267  */
 268 int ntfs_bitmap_set_run(ntfs_attr *na, s64 start_bit, s64 count)
 269 {
 270         int ret;
 271
 272         ntfs_log_enter("Set from bit %lld, count %lld\n",
 273                        (long long)start_bit, (long long)count);
 274         ret = ntfs_bitmap_set_bits_in_run(na, start_bit, count, 1);
 275         ntfs_log_leave("\n");
 276         return ret;
 277 }
 278
 279 /**
 280  * ntfs_bitmap_clear_run - clear a run of bits in a bitmap
 281  * @na:         attribute containing the bitmap
 282  * @start_bit:  first bit to clear
 283  * @count:      number of bits to clear
 284  *
 285  * Clear @count bits starting at bit @start_bit in the bitmap described by the
 286  * attribute @na.
 287  *
 288  * On success return 0 and on error return -1 with errno set to the error code.
 289  */
 290 int ntfs_bitmap_clear_run(ntfs_attr *na, s64 start_bit, s64 count)
 291 {
 292         int ret;
 293
 294         ntfs_log_enter("Clear from bit %lld, count %lld\n",
 295                        (long long)start_bit, (long long)count);
 296         ret = ntfs_bitmap_set_bits_in_run(na, start_bit, count, 0);
 297         ntfs_log_leave("\n");
 298         return ret;
 299 }
 300