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 301