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 */
ntfs_bit_set(u8 * bitmap,const u64 bit,const u8 new_value)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 */
ntfs_bit_get(const u8 * bitmap,const u64 bit)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 */
ntfs_bit_get_and_set(u8 * bitmap,const u64 bit,const u8 new_value)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 */
ntfs_bitmap_set_bits_in_run(ntfs_attr * na,s64 start_bit,s64 count,int value)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 */
ntfs_bitmap_set_run(ntfs_attr * na,s64 start_bit,s64 count)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 */
ntfs_bitmap_clear_run(ntfs_attr * na,s64 start_bit,s64 count)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