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