blob: 65162a2946003ee63805d906625023eecd53052a
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 |