/src/e2fsprogs/lib/ext2fs/blkmap64_ba.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * blkmap64_ba.c --- Simple bitarray implementation for bitmaps |
3 | | * |
4 | | * Copyright (C) 2008 Theodore Ts'o. |
5 | | * |
6 | | * %Begin-Header% |
7 | | * This file may be redistributed under the terms of the GNU Public |
8 | | * License. |
9 | | * %End-Header% |
10 | | */ |
11 | | |
12 | | #include "config.h" |
13 | | #include <stdio.h> |
14 | | #include <string.h> |
15 | | #if HAVE_UNISTD_H |
16 | | #include <unistd.h> |
17 | | #endif |
18 | | #include <fcntl.h> |
19 | | #include <time.h> |
20 | | #if HAVE_SYS_STAT_H |
21 | | #include <sys/stat.h> |
22 | | #endif |
23 | | #if HAVE_SYS_TYPES_H |
24 | | #include <sys/types.h> |
25 | | #endif |
26 | | |
27 | | #include "ext2_fs.h" |
28 | | #include "ext2fsP.h" |
29 | | #include "bmap64.h" |
30 | | |
31 | | /* |
32 | | * Private data for bit array implementation of bitmap ops. |
33 | | * Currently, this is just a pointer to our big flat hunk of memory, |
34 | | * exactly equivalent to the old-skool char * bitmap member. |
35 | | */ |
36 | | |
37 | | struct ext2fs_ba_private_struct { |
38 | | char *bitarray; |
39 | | }; |
40 | | |
41 | | typedef struct ext2fs_ba_private_struct *ext2fs_ba_private; |
42 | | |
43 | | static errcode_t ba_alloc_private_data (ext2fs_generic_bitmap_64 bitmap) |
44 | 0 | { |
45 | 0 | ext2fs_ba_private bp; |
46 | 0 | errcode_t retval; |
47 | 0 | size_t size; |
48 | | |
49 | | /* |
50 | | * Since we only have the one pointer, we could just shove our |
51 | | * private data in the void *private field itself, but then |
52 | | * we'd have to do a fair bit of rewriting if we ever added a |
53 | | * field. I'm agnostic. |
54 | | */ |
55 | 0 | retval = ext2fs_get_mem(sizeof (ext2fs_ba_private), &bp); |
56 | 0 | if (retval) |
57 | 0 | return retval; |
58 | | |
59 | 0 | size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1); |
60 | |
|
61 | 0 | retval = ext2fs_get_mem(size, &bp->bitarray); |
62 | 0 | if (retval) { |
63 | 0 | ext2fs_free_mem(&bp); |
64 | 0 | bp = 0; |
65 | 0 | return retval; |
66 | 0 | } |
67 | 0 | bitmap->private = (void *) bp; |
68 | 0 | return 0; |
69 | 0 | } |
70 | | |
71 | | static errcode_t ba_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)), |
72 | | ext2fs_generic_bitmap_64 bitmap) |
73 | 0 | { |
74 | 0 | ext2fs_ba_private bp; |
75 | 0 | errcode_t retval; |
76 | 0 | size_t size; |
77 | |
|
78 | 0 | retval = ba_alloc_private_data (bitmap); |
79 | 0 | if (retval) |
80 | 0 | return retval; |
81 | | |
82 | 0 | bp = (ext2fs_ba_private) bitmap->private; |
83 | 0 | size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1); |
84 | 0 | memset(bp->bitarray, 0, size); |
85 | |
|
86 | 0 | return 0; |
87 | 0 | } |
88 | | |
89 | | static void ba_free_bmap(ext2fs_generic_bitmap_64 bitmap) |
90 | 0 | { |
91 | 0 | ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
92 | |
|
93 | 0 | if (!bp) |
94 | 0 | return; |
95 | | |
96 | 0 | if (bp->bitarray) { |
97 | 0 | ext2fs_free_mem (&bp->bitarray); |
98 | 0 | bp->bitarray = 0; |
99 | 0 | } |
100 | 0 | ext2fs_free_mem (&bp); |
101 | 0 | bp = 0; |
102 | 0 | } |
103 | | |
104 | | static errcode_t ba_copy_bmap(ext2fs_generic_bitmap_64 src, |
105 | | ext2fs_generic_bitmap_64 dest) |
106 | 0 | { |
107 | 0 | ext2fs_ba_private src_bp = (ext2fs_ba_private) src->private; |
108 | 0 | ext2fs_ba_private dest_bp; |
109 | 0 | errcode_t retval; |
110 | 0 | size_t size; |
111 | |
|
112 | 0 | retval = ba_alloc_private_data (dest); |
113 | 0 | if (retval) |
114 | 0 | return retval; |
115 | | |
116 | 0 | dest_bp = (ext2fs_ba_private) dest->private; |
117 | |
|
118 | 0 | size = (size_t) (((src->real_end - src->start) / 8) + 1); |
119 | 0 | memcpy (dest_bp->bitarray, src_bp->bitarray, size); |
120 | |
|
121 | 0 | return 0; |
122 | 0 | } |
123 | | |
124 | | static errcode_t ba_resize_bmap(ext2fs_generic_bitmap_64 bmap, |
125 | | __u64 new_end, __u64 new_real_end) |
126 | 0 | { |
127 | 0 | ext2fs_ba_private bp = (ext2fs_ba_private) bmap->private; |
128 | 0 | errcode_t retval; |
129 | 0 | size_t size, new_size; |
130 | 0 | __u64 bitno; |
131 | | |
132 | | /* |
133 | | * If we're expanding the bitmap, make sure all of the new |
134 | | * parts of the bitmap are zero. |
135 | | */ |
136 | 0 | if (new_end > bmap->end) { |
137 | 0 | bitno = bmap->real_end; |
138 | 0 | if (bitno > new_end) |
139 | 0 | bitno = new_end; |
140 | 0 | for (; bitno > bmap->end; bitno--) |
141 | 0 | ext2fs_clear_bit64(bitno - bmap->start, bp->bitarray); |
142 | 0 | } |
143 | 0 | if (new_real_end == bmap->real_end) { |
144 | 0 | bmap->end = new_end; |
145 | 0 | return 0; |
146 | 0 | } |
147 | | |
148 | 0 | size = ((bmap->real_end - bmap->start) / 8) + 1; |
149 | 0 | new_size = ((new_real_end - bmap->start) / 8) + 1; |
150 | |
|
151 | 0 | if (size != new_size) { |
152 | 0 | retval = ext2fs_resize_mem(size, new_size, &bp->bitarray); |
153 | 0 | if (retval) |
154 | 0 | return retval; |
155 | 0 | } |
156 | 0 | if (new_size > size) |
157 | 0 | memset(bp->bitarray + size, 0, new_size - size); |
158 | |
|
159 | 0 | bmap->end = new_end; |
160 | 0 | bmap->real_end = new_real_end; |
161 | 0 | return 0; |
162 | |
|
163 | 0 | } |
164 | | |
165 | | static int ba_mark_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg) |
166 | 0 | { |
167 | 0 | ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
168 | 0 | blk64_t bitno = (blk64_t) arg; |
169 | |
|
170 | 0 | return ext2fs_set_bit64(bitno - bitmap->start, bp->bitarray); |
171 | 0 | } |
172 | | |
173 | | static int ba_unmark_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg) |
174 | 0 | { |
175 | 0 | ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
176 | 0 | blk64_t bitno = (blk64_t) arg; |
177 | |
|
178 | 0 | return ext2fs_clear_bit64(bitno - bitmap->start, bp->bitarray); |
179 | 0 | } |
180 | | |
181 | | static int ba_test_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg) |
182 | 0 | { |
183 | 0 | ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
184 | 0 | blk64_t bitno = (blk64_t) arg; |
185 | |
|
186 | 0 | return ext2fs_test_bit64(bitno - bitmap->start, bp->bitarray); |
187 | 0 | } |
188 | | |
189 | | static void ba_mark_bmap_extent(ext2fs_generic_bitmap_64 bitmap, __u64 arg, |
190 | | unsigned int num) |
191 | 0 | { |
192 | 0 | ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
193 | 0 | blk64_t bitno = (blk64_t) arg; |
194 | 0 | unsigned int i; |
195 | |
|
196 | 0 | for (i = 0; i < num; i++) |
197 | 0 | ext2fs_fast_set_bit64(bitno + i - bitmap->start, bp->bitarray); |
198 | 0 | } |
199 | | |
200 | | static void ba_unmark_bmap_extent(ext2fs_generic_bitmap_64 bitmap, __u64 arg, |
201 | | unsigned int num) |
202 | 0 | { |
203 | 0 | ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
204 | 0 | blk64_t bitno = (blk64_t) arg; |
205 | 0 | unsigned int i; |
206 | |
|
207 | 0 | for (i = 0; i < num; i++) |
208 | 0 | ext2fs_fast_clear_bit64(bitno + i - bitmap->start, bp->bitarray); |
209 | 0 | } |
210 | | |
211 | | static int ba_test_clear_bmap_extent(ext2fs_generic_bitmap_64 bitmap, |
212 | | __u64 start, unsigned int len) |
213 | 0 | { |
214 | 0 | ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
215 | 0 | __u64 start_byte, len_byte = len >> 3; |
216 | 0 | unsigned int start_bit, len_bit = len % 8; |
217 | 0 | unsigned int first_bit = 0; |
218 | 0 | unsigned int last_bit = 0; |
219 | 0 | int mark_count = 0; |
220 | 0 | int mark_bit = 0; |
221 | 0 | int i; |
222 | 0 | const char *ADDR; |
223 | |
|
224 | 0 | ADDR = bp->bitarray; |
225 | 0 | start -= bitmap->start; |
226 | 0 | start_byte = start >> 3; |
227 | 0 | start_bit = start % 8; |
228 | |
|
229 | 0 | if (start_bit != 0) { |
230 | | /* |
231 | | * The compared start block number or start inode number |
232 | | * is not the first bit in a byte. |
233 | | */ |
234 | 0 | mark_count = 8 - start_bit; |
235 | 0 | if (len < 8 - start_bit) { |
236 | 0 | mark_count = (int)len; |
237 | 0 | mark_bit = len + start_bit - 1; |
238 | 0 | } else |
239 | 0 | mark_bit = 7; |
240 | |
|
241 | 0 | for (i = mark_count; i > 0; i--, mark_bit--) |
242 | 0 | first_bit |= 1 << mark_bit; |
243 | | |
244 | | /* |
245 | | * Compare blocks or inodes in the first byte. |
246 | | * If there is any marked bit, this function returns 0. |
247 | | */ |
248 | 0 | if (first_bit & ADDR[start_byte]) |
249 | 0 | return 0; |
250 | 0 | else if (len <= 8 - start_bit) |
251 | 0 | return 1; |
252 | | |
253 | 0 | start_byte++; |
254 | 0 | len_bit = (len - mark_count) % 8; |
255 | 0 | len_byte = (len - mark_count) >> 3; |
256 | 0 | } |
257 | | |
258 | | /* |
259 | | * The compared start block number or start inode number is |
260 | | * the first bit in a byte. |
261 | | */ |
262 | 0 | if (len_bit != 0) { |
263 | | /* |
264 | | * The compared end block number or end inode number is |
265 | | * not the last bit in a byte. |
266 | | */ |
267 | 0 | for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--) |
268 | 0 | last_bit |= 1 << mark_bit; |
269 | | |
270 | | /* |
271 | | * Compare blocks or inodes in the last byte. |
272 | | * If there is any marked bit, this function returns 0. |
273 | | */ |
274 | 0 | if (last_bit & ADDR[start_byte + len_byte]) |
275 | 0 | return 0; |
276 | 0 | else if (len_byte == 0) |
277 | 0 | return 1; |
278 | 0 | } |
279 | | |
280 | | /* Check whether all bytes are 0 */ |
281 | 0 | return ext2fs_mem_is_zero(ADDR + start_byte, len_byte); |
282 | 0 | } |
283 | | |
284 | | |
285 | | static errcode_t ba_set_bmap_range(ext2fs_generic_bitmap_64 bitmap, |
286 | | __u64 start, size_t num, void *in) |
287 | 0 | { |
288 | 0 | ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
289 | |
|
290 | 0 | memcpy (bp->bitarray + (start >> 3), in, (num + 7) >> 3); |
291 | |
|
292 | 0 | return 0; |
293 | 0 | } |
294 | | |
295 | | static errcode_t ba_get_bmap_range(ext2fs_generic_bitmap_64 bitmap, |
296 | | __u64 start, size_t num, void *out) |
297 | 0 | { |
298 | 0 | ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
299 | |
|
300 | 0 | memcpy (out, bp->bitarray + (start >> 3), (num + 7) >> 3); |
301 | |
|
302 | 0 | return 0; |
303 | 0 | } |
304 | | |
305 | | static void ba_clear_bmap(ext2fs_generic_bitmap_64 bitmap) |
306 | 0 | { |
307 | 0 | ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private; |
308 | |
|
309 | 0 | memset(bp->bitarray, 0, |
310 | 0 | (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1)); |
311 | 0 | } |
312 | | |
313 | | #ifdef ENABLE_BMAP_STATS |
314 | | static void ba_print_stats(ext2fs_generic_bitmap_64 bitmap) |
315 | 0 | { |
316 | 0 | fprintf(stderr, "%16llu Bytes used by bitarray\n", (unsigned long long) |
317 | 0 | ((bitmap->real_end - bitmap->start) >> 3) + 1 + |
318 | 0 | sizeof(struct ext2fs_ba_private_struct)); |
319 | 0 | } |
320 | | #else |
321 | | static void ba_print_stats(ext2fs_generic_bitmap_64 bitmap EXT2FS_ATTR((unused))) |
322 | | { |
323 | | } |
324 | | #endif |
325 | | |
326 | | /* Find the first zero bit between start and end, inclusive. */ |
327 | | static errcode_t ba_find_first_zero(ext2fs_generic_bitmap_64 bitmap, |
328 | | __u64 start, __u64 end, __u64 *out) |
329 | 0 | { |
330 | 0 | ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private; |
331 | 0 | unsigned long bitpos = start - bitmap->start; |
332 | 0 | unsigned long count = end - start + 1; |
333 | 0 | int byte_found = 0; /* whether a != 0xff byte has been found */ |
334 | 0 | const unsigned char *pos; |
335 | 0 | unsigned long max_loop_count, i; |
336 | | |
337 | | /* scan bits until we hit a byte boundary */ |
338 | 0 | while ((bitpos & 0x7) != 0 && count > 0) { |
339 | 0 | if (!ext2fs_test_bit64(bitpos, bp->bitarray)) { |
340 | 0 | *out = bitpos + bitmap->start; |
341 | 0 | return 0; |
342 | 0 | } |
343 | 0 | bitpos++; |
344 | 0 | count--; |
345 | 0 | } |
346 | | |
347 | 0 | if (!count) |
348 | 0 | return ENOENT; |
349 | | |
350 | 0 | pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3); |
351 | | /* scan bytes until 8-byte (64-bit) aligned */ |
352 | 0 | while (count >= 8 && (((uintptr_t)pos) & 0x07)) { |
353 | 0 | if (*pos != 0xff) { |
354 | 0 | byte_found = 1; |
355 | 0 | break; |
356 | 0 | } |
357 | 0 | pos++; |
358 | 0 | count -= 8; |
359 | 0 | bitpos += 8; |
360 | 0 | } |
361 | |
|
362 | 0 | if (!byte_found) { |
363 | 0 | max_loop_count = count >> 6; /* 8-byte blocks */ |
364 | 0 | i = max_loop_count; |
365 | 0 | while (i) { |
366 | 0 | if (*((const __u64 *)pos) != ((__u64)-1)) |
367 | 0 | break; |
368 | 0 | pos += 8; |
369 | 0 | i--; |
370 | 0 | } |
371 | 0 | count -= 64 * (max_loop_count - i); |
372 | 0 | bitpos += 64 * (max_loop_count - i); |
373 | |
|
374 | 0 | max_loop_count = count >> 3; |
375 | 0 | i = max_loop_count; |
376 | 0 | while (i) { |
377 | 0 | if (*pos != 0xff) { |
378 | 0 | byte_found = 1; |
379 | 0 | break; |
380 | 0 | } |
381 | 0 | pos++; |
382 | 0 | i--; |
383 | 0 | } |
384 | 0 | count -= 8 * (max_loop_count - i); |
385 | 0 | bitpos += 8 * (max_loop_count - i); |
386 | 0 | } |
387 | | |
388 | | /* Here either count < 8 or byte_found == 1. */ |
389 | 0 | while (count-- > 0) { |
390 | 0 | if (!ext2fs_test_bit64(bitpos, bp->bitarray)) { |
391 | 0 | *out = bitpos + bitmap->start; |
392 | 0 | return 0; |
393 | 0 | } |
394 | 0 | bitpos++; |
395 | 0 | } |
396 | | |
397 | 0 | return ENOENT; |
398 | 0 | } |
399 | | |
400 | | /* Find the first one bit between start and end, inclusive. */ |
401 | | static errcode_t ba_find_first_set(ext2fs_generic_bitmap_64 bitmap, |
402 | | __u64 start, __u64 end, __u64 *out) |
403 | 0 | { |
404 | 0 | ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private; |
405 | 0 | unsigned long bitpos = start - bitmap->start; |
406 | 0 | unsigned long count = end - start + 1; |
407 | 0 | int byte_found = 0; /* whether a != 0xff byte has been found */ |
408 | 0 | const unsigned char *pos; |
409 | 0 | unsigned long max_loop_count, i; |
410 | | |
411 | | /* scan bits until we hit a byte boundary */ |
412 | 0 | while ((bitpos & 0x7) != 0 && count > 0) { |
413 | 0 | if (ext2fs_test_bit64(bitpos, bp->bitarray)) { |
414 | 0 | *out = bitpos + bitmap->start; |
415 | 0 | return 0; |
416 | 0 | } |
417 | 0 | bitpos++; |
418 | 0 | count--; |
419 | 0 | } |
420 | | |
421 | 0 | if (!count) |
422 | 0 | return ENOENT; |
423 | | |
424 | 0 | pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3); |
425 | | /* scan bytes until 8-byte (64-bit) aligned */ |
426 | 0 | while (count >= 8 && (((uintptr_t)pos) & 0x07)) { |
427 | 0 | if (*pos != 0) { |
428 | 0 | byte_found = 1; |
429 | 0 | break; |
430 | 0 | } |
431 | 0 | pos++; |
432 | 0 | count -= 8; |
433 | 0 | bitpos += 8; |
434 | 0 | } |
435 | |
|
436 | 0 | if (!byte_found) { |
437 | 0 | max_loop_count = count >> 6; /* 8-byte blocks */ |
438 | 0 | i = max_loop_count; |
439 | 0 | while (i) { |
440 | 0 | if (*((const __u64 *)pos) != 0) |
441 | 0 | break; |
442 | 0 | pos += 8; |
443 | 0 | i--; |
444 | 0 | } |
445 | 0 | count -= 64 * (max_loop_count - i); |
446 | 0 | bitpos += 64 * (max_loop_count - i); |
447 | |
|
448 | 0 | max_loop_count = count >> 3; |
449 | 0 | i = max_loop_count; |
450 | 0 | while (i) { |
451 | 0 | if (*pos != 0) { |
452 | 0 | byte_found = 1; |
453 | 0 | break; |
454 | 0 | } |
455 | 0 | pos++; |
456 | 0 | i--; |
457 | 0 | } |
458 | 0 | count -= 8 * (max_loop_count - i); |
459 | 0 | bitpos += 8 * (max_loop_count - i); |
460 | 0 | } |
461 | | |
462 | | /* Here either count < 8 or byte_found == 1. */ |
463 | 0 | while (count-- > 0) { |
464 | 0 | if (ext2fs_test_bit64(bitpos, bp->bitarray)) { |
465 | 0 | *out = bitpos + bitmap->start; |
466 | 0 | return 0; |
467 | 0 | } |
468 | 0 | bitpos++; |
469 | 0 | } |
470 | | |
471 | 0 | return ENOENT; |
472 | 0 | } |
473 | | |
474 | | struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = { |
475 | | .type = EXT2FS_BMAP64_BITARRAY, |
476 | | .new_bmap = ba_new_bmap, |
477 | | .free_bmap = ba_free_bmap, |
478 | | .copy_bmap = ba_copy_bmap, |
479 | | .resize_bmap = ba_resize_bmap, |
480 | | .mark_bmap = ba_mark_bmap, |
481 | | .unmark_bmap = ba_unmark_bmap, |
482 | | .test_bmap = ba_test_bmap, |
483 | | .test_clear_bmap_extent = ba_test_clear_bmap_extent, |
484 | | .mark_bmap_extent = ba_mark_bmap_extent, |
485 | | .unmark_bmap_extent = ba_unmark_bmap_extent, |
486 | | .set_bmap_range = ba_set_bmap_range, |
487 | | .get_bmap_range = ba_get_bmap_range, |
488 | | .clear_bmap = ba_clear_bmap, |
489 | | .print_stats = ba_print_stats, |
490 | | .find_first_zero = ba_find_first_zero, |
491 | | .find_first_set = ba_find_first_set |
492 | | }; |