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-2006 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, err; 121 122 if (!na || start_bit < 0 || count < 0) { 123 errno = EINVAL; 124 return -1; 125 } 126 127 bit = start_bit & 7; 128 if (bit) 129 firstbyte = 1; 130 else 131 firstbyte = 0; 132 133 /* Calculate the required buffer size in bytes, capping it at 8kiB. */ 134 bufsize = ((count - (bit ? 8 - bit : 0) + 7) >> 3) + firstbyte; 135 if (bufsize > 8192) 136 bufsize = 8192; 137 138 buf = ntfs_malloc(bufsize); 139 if (!buf) 140 return -1; 141 142 /* Depending on @value, zero or set all bits in the allocated buffer. */ 143 memset(buf, value ? 0xff : 0, bufsize); 144 145 /* If there is a first partial byte... */ 146 if (bit) { 147 /* read it in... */ 148 br = ntfs_attr_pread(na, start_bit >> 3, 1, buf); 149 if (br != 1) { 150 free(buf); 151 errno = EIO; 152 return -1; 153 } 154 /* and set or clear the appropriate bits in it. */ 155 while ((bit & 7) && count--) { 156 if (value) 157 *buf |= 1 << bit++; 158 else 159 *buf &= ~(1 << bit++); 160 } 161 /* Update @start_bit to the new position. */ 162 start_bit = (start_bit + 7) & ~7; 163 } 164 165 /* Loop until @count reaches zero. */ 166 lastbyte = 0; 167 lastbyte_buf = NULL; 168 bit = count & 7; 169 do { 170 /* If there is a last partial byte... */ 171 if (count > 0 && bit) { 172 lastbyte_pos = ((count + 7) >> 3) + firstbyte; 173 if (!lastbyte_pos) { 174 // FIXME: Eeek! BUG! 175 ntfs_log_trace("Eeek! lastbyte is zero. Leaving " 176 "inconsistent metadata.\n"); 177 err = EIO; 178 goto free_err_out; 179 } 180 /* and it is in the currently loaded bitmap window... */ 181 if (lastbyte_pos <= bufsize) { 182 lastbyte_buf = buf + lastbyte_pos - 1; 183 184 /* read the byte in... */ 185 br = ntfs_attr_pread(na, (start_bit + count) >> 186 3, 1, lastbyte_buf); 187 if (br != 1) { 188 // FIXME: Eeek! We need rollback! (AIA) 189 ntfs_log_trace("Eeek! Read of last byte " 190 "failed. Leaving " 191 "inconsistent metadata.\n"); 192 err = EIO; 193 goto free_err_out; 194 } 195 /* and set/clear the appropriate bits in it. */ 196 while (bit && count--) { 197 if (value) 198 *lastbyte_buf |= 1 << --bit; 199 else 200 *lastbyte_buf &= ~(1 << --bit); 201 } 202 /* We don't want to come back here... */ 203 bit = 0; 204 /* We have a last byte that we have handled. */ 205 lastbyte = 1; 206 } 207 } 208 209 /* Write the prepared buffer to disk. */ 210 tmp = (start_bit >> 3) - firstbyte; 211 br = ntfs_attr_pwrite(na, tmp, bufsize, buf); 212 if (br != bufsize) { 213 // FIXME: Eeek! We need rollback! (AIA) 214 ntfs_log_trace("Eeek! Failed to write buffer to bitmap. " 215 "Leaving inconsistent metadata.\n"); 216 err = EIO; 217 goto free_err_out; 218 } 219 220 /* Update counters. */ 221 tmp = (bufsize - firstbyte - lastbyte) << 3; 222 if (firstbyte) { 223 firstbyte = 0; 224 /* 225 * Re-set the partial first byte so a subsequent write 226 * of the buffer does not have stale, incorrect bits. 227 */ 228 *buf = value ? 0xff : 0; 229 } 230 start_bit += tmp; 231 count -= tmp; 232 if (bufsize > (tmp = (count + 7) >> 3)) 233 bufsize = tmp; 234 235 if (lastbyte && count != 0) { 236 // FIXME: Eeek! BUG! 237 ntfs_log_trace("Eeek! Last buffer but count is not zero (= " 238 "%lli). Leaving inconsistent metadata.\n", 239 (long long)count); 240 err = EIO; 241 goto free_err_out; 242 } 243 } while (count > 0); 244 245 /* Done! */ 246 free(buf); 247 return 0; 248 249 free_err_out: 250 free(buf); 251 errno = err; 252 return -1; 253 } 254 255 /** 256 * ntfs_bitmap_set_run - set a run of bits in a bitmap 257 * @na: attribute containing the bitmap 258 * @start_bit: first bit to set 259 * @count: number of bits to set 260 * 261 * Set @count bits starting at bit @start_bit in the bitmap described by the 262 * attribute @na. 263 * 264 * On success return 0 and on error return -1 with errno set to the error code. 265 */ 266 int ntfs_bitmap_set_run(ntfs_attr *na, s64 start_bit, s64 count) 267 { 268 return ntfs_bitmap_set_bits_in_run(na, start_bit, count, 1); 269 } 270 271 /** 272 * ntfs_bitmap_clear_run - clear a run of bits in a bitmap 273 * @na: attribute containing the bitmap 274 * @start_bit: first bit to clear 275 * @count: number of bits to clear 276 * 277 * Clear @count bits starting at bit @start_bit in the bitmap described by the 278 * attribute @na. 279 * 280 * On success return 0 and on error return -1 with errno set to the error code. 281 */ 282 int ntfs_bitmap_clear_run(ntfs_attr *na, s64 start_bit, s64 count) 283 { 284 ntfs_log_trace("Dealloc from bit 0x%llx, count 0x%llx.\n", 285 (long long)start_bit, (long long)count); 286 287 return ntfs_bitmap_set_bits_in_run(na, start_bit, count, 0); 288 } 289 290