1 /*
2 * gen_bitmap64.c --- routines to read, write, and manipulate the new qinode and
3 * block bitmaps.
4 *
5 * Copyright (C) 2007, 2008 Theodore Ts'o.
6 *
7 * %Begin-Header%
8 * This file may be redistributed under the terms of the GNU Public
9 * License.
10 * %End-Header%
11 */
12
13 #include "config.h"
14 #include <stdio.h>
15 #include <string.h>
16 #if HAVE_UNISTD_H
17 #include <unistd.h>
18 #endif
19 #include <fcntl.h>
20 #include <time.h>
21 #include <errno.h>
22 #if HAVE_SYS_STAT_H
23 #include <sys/stat.h>
24 #endif
25 #if HAVE_SYS_TYPES_H
26 #include <sys/types.h>
27 #endif
28 #ifdef HAVE_SYS_TIME_H
29 #include <sys/time.h>
30 #endif
31
32 #include "ext2_fs.h"
33 #include "ext2fsP.h"
34 #include "bmap64.h"
35
36 /*
37 * Design of 64-bit bitmaps
38 *
39 * In order maintain ABI compatibility with programs that don't
40 * understand about 64-bit blocks/inodes,
41 * ext2fs_allocate_inode_bitmap() and ext2fs_allocate_block_bitmap()
42 * will create old-style bitmaps unless the application passes the
43 * flag EXT2_FLAG_64BITS to ext2fs_open(). If this flag is
44 * passed, then we know the application has been recompiled, so we can
45 * use the new-style bitmaps. If it is not passed, we have to return
46 * an error if trying to open a filesystem which needs 64-bit bitmaps.
47 *
48 * The new bitmaps use a new set of structure magic numbers, so that
49 * both the old-style and new-style interfaces can identify which
50 * version of the data structure was used. Both the old-style and
51 * new-style interfaces will support either type of bitmap, although
52 * of course 64-bit operation will only be possible when both the
53 * new-style interface and the new-style bitmap are used.
54 *
55 * For example, the new bitmap interfaces will check the structure
56 * magic numbers and so will be able to detect old-stype bitmap. If
57 * they see an old-style bitmap, they will pass it to the gen_bitmap.c
58 * functions for handling. The same will be true for the old
59 * interfaces as well.
60 *
61 * The new-style interfaces will have several different back-end
62 * implementations, so we can support different encodings that are
63 * appropriate for different applications. In general the default
64 * should be whatever makes sense, and what the application/library
65 * will use. However, e2fsck may need specialized implementations for
66 * its own uses. For example, when doing parent directory pointer
67 * loop detections in pass 3, the bitmap will *always* be sparse, so
68 * e2fsck can request an encoding which is optimized for that.
69 */
70
warn_bitmap(ext2fs_generic_bitmap_64 bitmap,int code,__u64 arg)71 static void warn_bitmap(ext2fs_generic_bitmap_64 bitmap,
72 int code, __u64 arg)
73 {
74 #ifndef OMIT_COM_ERR
75 if (bitmap->description)
76 com_err(0, bitmap->base_error_code+code,
77 "#%llu for %s", (unsigned long long) arg,
78 bitmap->description);
79 else
80 com_err(0, bitmap->base_error_code + code, "#%llu",
81 (unsigned long long) arg);
82 #endif
83 }
84
85 #ifdef ENABLE_BMAP_STATS_OPS
86 #define INC_STAT(map, name) map->stats.name
87 #else
88 #define INC_STAT(map, name) ;;
89 #endif
90
91
ext2fs_alloc_generic_bmap(ext2_filsys fs,errcode_t magic,int type,__u64 start,__u64 end,__u64 real_end,const char * descr,ext2fs_generic_bitmap * ret)92 errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
93 int type, __u64 start, __u64 end,
94 __u64 real_end,
95 const char *descr,
96 ext2fs_generic_bitmap *ret)
97 {
98 ext2fs_generic_bitmap_64 bitmap;
99 struct ext2_bitmap_ops *ops;
100 ext2_ino_t num_dirs;
101 errcode_t retval;
102
103 if (!type)
104 type = EXT2FS_BMAP64_BITARRAY;
105
106 switch (type) {
107 case EXT2FS_BMAP64_BITARRAY:
108 ops = &ext2fs_blkmap64_bitarray;
109 break;
110 case EXT2FS_BMAP64_RBTREE:
111 ops = &ext2fs_blkmap64_rbtree;
112 break;
113 case EXT2FS_BMAP64_AUTODIR:
114 retval = ext2fs_get_num_dirs(fs, &num_dirs);
115 if (retval || num_dirs > (fs->super->s_inodes_count / 320))
116 ops = &ext2fs_blkmap64_bitarray;
117 else
118 ops = &ext2fs_blkmap64_rbtree;
119 break;
120 default:
121 return EINVAL;
122 }
123
124 retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap_64),
125 &bitmap);
126 if (retval)
127 return retval;
128
129 #ifdef ENABLE_BMAP_STATS
130 if (gettimeofday(&bitmap->stats.created,
131 (struct timezone *) NULL) == -1) {
132 perror("gettimeofday");
133 ext2fs_free_mem(&bitmap);
134 return 1;
135 }
136 bitmap->stats.type = type;
137 #endif
138
139 /* XXX factor out, repeated in copy_bmap */
140 bitmap->magic = magic;
141 bitmap->fs = fs;
142 bitmap->start = start;
143 bitmap->end = end;
144 bitmap->real_end = real_end;
145 bitmap->bitmap_ops = ops;
146 bitmap->cluster_bits = 0;
147 switch (magic) {
148 case EXT2_ET_MAGIC_INODE_BITMAP64:
149 bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK;
150 break;
151 case EXT2_ET_MAGIC_BLOCK_BITMAP64:
152 bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK;
153 bitmap->cluster_bits = fs->cluster_ratio_bits;
154 break;
155 default:
156 bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK;
157 }
158 if (descr) {
159 retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description);
160 if (retval) {
161 ext2fs_free_mem(&bitmap);
162 return retval;
163 }
164 strcpy(bitmap->description, descr);
165 } else
166 bitmap->description = 0;
167
168 retval = bitmap->bitmap_ops->new_bmap(fs, bitmap);
169 if (retval) {
170 ext2fs_free_mem(&bitmap->description);
171 ext2fs_free_mem(&bitmap);
172 return retval;
173 }
174
175 *ret = (ext2fs_generic_bitmap) bitmap;
176 return 0;
177 }
178
179 #ifdef ENABLE_BMAP_STATS
ext2fs_print_bmap_statistics(ext2fs_generic_bitmap_64 bitmap)180 static void ext2fs_print_bmap_statistics(ext2fs_generic_bitmap_64 bitmap)
181 {
182 struct ext2_bmap_statistics *stats = &bitmap->stats;
183 #ifdef ENABLE_BMAP_STATS_OPS
184 float mark_seq_perc = 0.0, test_seq_perc = 0.0;
185 float mark_back_perc = 0.0, test_back_perc = 0.0;
186 #endif
187 double inuse;
188 struct timeval now;
189
190 #ifdef ENABLE_BMAP_STATS_OPS
191 if (stats->test_count) {
192 test_seq_perc = ((float)stats->test_seq /
193 stats->test_count) * 100;
194 test_back_perc = ((float)stats->test_back /
195 stats->test_count) * 100;
196 }
197
198 if (stats->mark_count) {
199 mark_seq_perc = ((float)stats->mark_seq /
200 stats->mark_count) * 100;
201 mark_back_perc = ((float)stats->mark_back /
202 stats->mark_count) * 100;
203 }
204 #endif
205
206 if (gettimeofday(&now, (struct timezone *) NULL) == -1) {
207 perror("gettimeofday");
208 return;
209 }
210
211 inuse = (double) now.tv_sec + \
212 (((double) now.tv_usec) * 0.000001);
213 inuse -= (double) stats->created.tv_sec + \
214 (((double) stats->created.tv_usec) * 0.000001);
215
216 fprintf(stderr, "\n[+] %s bitmap (type %d)\n", bitmap->description,
217 stats->type);
218 fprintf(stderr, "=================================================\n");
219 #ifdef ENABLE_BMAP_STATS_OPS
220 fprintf(stderr, "%16llu bits long\n",
221 bitmap->real_end - bitmap->start);
222 fprintf(stderr, "%16lu copy_bmap\n%16lu resize_bmap\n",
223 stats->copy_count, stats->resize_count);
224 fprintf(stderr, "%16lu mark bmap\n%16lu unmark_bmap\n",
225 stats->mark_count, stats->unmark_count);
226 fprintf(stderr, "%16lu test_bmap\n%16lu mark_bmap_extent\n",
227 stats->test_count, stats->mark_ext_count);
228 fprintf(stderr, "%16lu unmark_bmap_extent\n"
229 "%16lu test_clear_bmap_extent\n",
230 stats->unmark_ext_count, stats->test_ext_count);
231 fprintf(stderr, "%16lu set_bmap_range\n%16lu set_bmap_range\n",
232 stats->set_range_count, stats->get_range_count);
233 fprintf(stderr, "%16lu clear_bmap\n%16lu contiguous bit test (%.2f%%)\n",
234 stats->clear_count, stats->test_seq, test_seq_perc);
235 fprintf(stderr, "%16lu contiguous bit mark (%.2f%%)\n"
236 "%16llu bits tested backwards (%.2f%%)\n",
237 stats->mark_seq, mark_seq_perc,
238 stats->test_back, test_back_perc);
239 fprintf(stderr, "%16llu bits marked backwards (%.2f%%)\n"
240 "%16.2f seconds in use\n",
241 stats->mark_back, mark_back_perc, inuse);
242 #endif /* ENABLE_BMAP_STATS_OPS */
243 }
244 #endif
245
ext2fs_free_generic_bmap(ext2fs_generic_bitmap gen_bmap)246 void ext2fs_free_generic_bmap(ext2fs_generic_bitmap gen_bmap)
247 {
248 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
249
250 if (!bmap)
251 return;
252
253 if (EXT2FS_IS_32_BITMAP(bmap)) {
254 ext2fs_free_generic_bitmap(gen_bmap);
255 return;
256 }
257
258 if (!EXT2FS_IS_64_BITMAP(bmap))
259 return;
260
261 #ifdef ENABLE_BMAP_STATS
262 if (getenv("E2FSPROGS_BITMAP_STATS")) {
263 ext2fs_print_bmap_statistics(bmap);
264 bmap->bitmap_ops->print_stats(bmap);
265 }
266 #endif
267
268 bmap->bitmap_ops->free_bmap(bmap);
269
270 if (bmap->description) {
271 ext2fs_free_mem(&bmap->description);
272 bmap->description = 0;
273 }
274 bmap->magic = 0;
275 ext2fs_free_mem(&bmap);
276 }
277
ext2fs_copy_generic_bmap(ext2fs_generic_bitmap gen_src,ext2fs_generic_bitmap * dest)278 errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap gen_src,
279 ext2fs_generic_bitmap *dest)
280 {
281 ext2fs_generic_bitmap_64 src = (ext2fs_generic_bitmap_64) gen_src;
282 char *descr, *new_descr;
283 ext2fs_generic_bitmap_64 new_bmap;
284 errcode_t retval;
285
286 if (!src)
287 return EINVAL;
288
289 if (EXT2FS_IS_32_BITMAP(src))
290 return ext2fs_copy_generic_bitmap(gen_src, dest);
291
292 if (!EXT2FS_IS_64_BITMAP(src))
293 return EINVAL;
294
295 /* Allocate a new bitmap struct */
296 retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap_64),
297 &new_bmap);
298 if (retval)
299 return retval;
300
301
302 #ifdef ENABLE_BMAP_STATS_OPS
303 src->stats.copy_count++;
304 #endif
305 #ifdef ENABLE_BMAP_STATS
306 if (gettimeofday(&new_bmap->stats.created,
307 (struct timezone *) NULL) == -1) {
308 perror("gettimeofday");
309 ext2fs_free_mem(&new_bmap);
310 return 1;
311 }
312 new_bmap->stats.type = src->stats.type;
313 #endif
314
315 /* Copy all the high-level parts over */
316 new_bmap->magic = src->magic;
317 new_bmap->fs = src->fs;
318 new_bmap->start = src->start;
319 new_bmap->end = src->end;
320 new_bmap->real_end = src->real_end;
321 new_bmap->bitmap_ops = src->bitmap_ops;
322 new_bmap->base_error_code = src->base_error_code;
323 new_bmap->cluster_bits = src->cluster_bits;
324
325 descr = src->description;
326 if (descr) {
327 retval = ext2fs_get_mem(strlen(descr)+10, &new_descr);
328 if (retval) {
329 ext2fs_free_mem(&new_bmap);
330 return retval;
331 }
332 strcpy(new_descr, "copy of ");
333 strcat(new_descr, descr);
334 new_bmap->description = new_descr;
335 }
336
337 retval = src->bitmap_ops->copy_bmap(src, new_bmap);
338 if (retval) {
339 ext2fs_free_mem(&new_bmap->description);
340 ext2fs_free_mem(&new_bmap);
341 return retval;
342 }
343
344 *dest = (ext2fs_generic_bitmap) new_bmap;
345
346 return 0;
347 }
348
ext2fs_resize_generic_bmap(ext2fs_generic_bitmap gen_bmap,__u64 new_end,__u64 new_real_end)349 errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap gen_bmap,
350 __u64 new_end,
351 __u64 new_real_end)
352 {
353 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
354
355 if (!bmap)
356 return EINVAL;
357
358 if (EXT2FS_IS_32_BITMAP(bmap))
359 return ext2fs_resize_generic_bitmap(gen_bmap->magic, new_end,
360 new_real_end, gen_bmap);
361
362 if (!EXT2FS_IS_64_BITMAP(bmap))
363 return EINVAL;
364
365 INC_STAT(bmap, resize_count);
366
367 return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
368 }
369
ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap,errcode_t neq,__u64 end,__u64 * oend)370 errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap,
371 errcode_t neq,
372 __u64 end, __u64 *oend)
373 {
374 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
375
376 if (!bitmap)
377 return EINVAL;
378
379 if (EXT2FS_IS_32_BITMAP(bitmap)) {
380 ext2_ino_t tmp_oend;
381 int retval;
382
383 retval = ext2fs_fudge_generic_bitmap_end(gen_bitmap,
384 bitmap->magic,
385 neq, end, &tmp_oend);
386 if (oend)
387 *oend = tmp_oend;
388 return retval;
389 }
390
391 if (!EXT2FS_IS_64_BITMAP(bitmap))
392 return EINVAL;
393
394 if (end > bitmap->real_end)
395 return neq;
396 if (oend)
397 *oend = bitmap->end;
398 bitmap->end = end;
399 return 0;
400 }
401
ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap gen_bitmap)402 __u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap gen_bitmap)
403 {
404 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
405
406 if (!bitmap)
407 return EINVAL;
408
409 if (EXT2FS_IS_32_BITMAP(bitmap))
410 return ext2fs_get_generic_bitmap_start(gen_bitmap);
411
412 if (!EXT2FS_IS_64_BITMAP(bitmap))
413 return EINVAL;
414
415 return bitmap->start;
416 }
417
ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap)418 __u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap)
419 {
420 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
421
422 if (!bitmap)
423 return EINVAL;
424
425 if (EXT2FS_IS_32_BITMAP(bitmap))
426 return ext2fs_get_generic_bitmap_end(gen_bitmap);
427
428 if (!EXT2FS_IS_64_BITMAP(bitmap))
429 return EINVAL;
430
431 return bitmap->end;
432 }
433
ext2fs_clear_generic_bmap(ext2fs_generic_bitmap gen_bitmap)434 void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap gen_bitmap)
435 {
436 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
437
438 if (EXT2FS_IS_32_BITMAP(bitmap))
439 ext2fs_clear_generic_bitmap(gen_bitmap);
440 else
441 bitmap->bitmap_ops->clear_bmap(bitmap);
442 }
443
ext2fs_mark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,__u64 arg)444 int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
445 __u64 arg)
446 {
447 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
448
449 if (!bitmap)
450 return 0;
451
452 if (EXT2FS_IS_32_BITMAP(bitmap)) {
453 if (arg & ~0xffffffffULL) {
454 ext2fs_warn_bitmap2(gen_bitmap,
455 EXT2FS_MARK_ERROR, 0xffffffff);
456 return 0;
457 }
458 return ext2fs_mark_generic_bitmap(gen_bitmap, arg);
459 }
460
461 if (!EXT2FS_IS_64_BITMAP(bitmap))
462 return 0;
463
464 arg >>= bitmap->cluster_bits;
465
466 #ifdef ENABLE_BMAP_STATS_OPS
467 if (arg == bitmap->stats.last_marked + 1)
468 bitmap->stats.mark_seq++;
469 if (arg < bitmap->stats.last_marked)
470 bitmap->stats.mark_back++;
471 bitmap->stats.last_marked = arg;
472 bitmap->stats.mark_count++;
473 #endif
474
475 if ((arg < bitmap->start) || (arg > bitmap->end)) {
476 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
477 return 0;
478 }
479
480 return bitmap->bitmap_ops->mark_bmap(bitmap, arg);
481 }
482
ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,__u64 arg)483 int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
484 __u64 arg)
485 {
486 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
487
488 if (!bitmap)
489 return 0;
490
491 if (EXT2FS_IS_32_BITMAP(bitmap)) {
492 if (arg & ~0xffffffffULL) {
493 ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_UNMARK_ERROR,
494 0xffffffff);
495 return 0;
496 }
497 return ext2fs_unmark_generic_bitmap(gen_bitmap, arg);
498 }
499
500 if (!EXT2FS_IS_64_BITMAP(bitmap))
501 return 0;
502
503 arg >>= bitmap->cluster_bits;
504
505 INC_STAT(bitmap, unmark_count);
506
507 if ((arg < bitmap->start) || (arg > bitmap->end)) {
508 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
509 return 0;
510 }
511
512 return bitmap->bitmap_ops->unmark_bmap(bitmap, arg);
513 }
514
ext2fs_test_generic_bmap(ext2fs_generic_bitmap gen_bitmap,__u64 arg)515 int ext2fs_test_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
516 __u64 arg)
517 {
518 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
519 if (!bitmap)
520 return 0;
521
522 if (EXT2FS_IS_32_BITMAP(bitmap)) {
523 if (arg & ~0xffffffffULL) {
524 ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_TEST_ERROR,
525 0xffffffff);
526 return 0;
527 }
528 return ext2fs_test_generic_bitmap(gen_bitmap, arg);
529 }
530
531 if (!EXT2FS_IS_64_BITMAP(bitmap))
532 return 0;
533
534 arg >>= bitmap->cluster_bits;
535
536 #ifdef ENABLE_BMAP_STATS_OPS
537 bitmap->stats.test_count++;
538 if (arg == bitmap->stats.last_tested + 1)
539 bitmap->stats.test_seq++;
540 if (arg < bitmap->stats.last_tested)
541 bitmap->stats.test_back++;
542 bitmap->stats.last_tested = arg;
543 #endif
544
545 if ((arg < bitmap->start) || (arg > bitmap->end)) {
546 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
547 return 0;
548 }
549
550 return bitmap->bitmap_ops->test_bmap(bitmap, arg);
551 }
552
ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,__u64 start,unsigned int num,void * in)553 errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,
554 __u64 start, unsigned int num,
555 void *in)
556 {
557 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
558
559 if (!bmap)
560 return EINVAL;
561
562 if (EXT2FS_IS_32_BITMAP(bmap)) {
563 if ((start+num-1) & ~0xffffffffULL) {
564 ext2fs_warn_bitmap2(gen_bmap, EXT2FS_UNMARK_ERROR,
565 0xffffffff);
566 return EINVAL;
567 }
568 return ext2fs_set_generic_bitmap_range(gen_bmap, bmap->magic,
569 start, num, in);
570 }
571
572 if (!EXT2FS_IS_64_BITMAP(bmap))
573 return EINVAL;
574
575 INC_STAT(bmap, set_range_count);
576
577 return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
578 }
579
ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,__u64 start,unsigned int num,void * out)580 errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,
581 __u64 start, unsigned int num,
582 void *out)
583 {
584 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
585
586 if (!bmap)
587 return EINVAL;
588
589 if (EXT2FS_IS_32_BITMAP(bmap)) {
590 if ((start+num-1) & ~0xffffffffULL) {
591 ext2fs_warn_bitmap2(gen_bmap,
592 EXT2FS_UNMARK_ERROR, 0xffffffff);
593 return EINVAL;
594 }
595 return ext2fs_get_generic_bitmap_range(gen_bmap, bmap->magic,
596 start, num, out);
597 }
598
599 if (!EXT2FS_IS_64_BITMAP(bmap))
600 return EINVAL;
601
602 INC_STAT(bmap, get_range_count);
603
604 return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
605 }
606
ext2fs_compare_generic_bmap(errcode_t neq,ext2fs_generic_bitmap gen_bm1,ext2fs_generic_bitmap gen_bm2)607 errcode_t ext2fs_compare_generic_bmap(errcode_t neq,
608 ext2fs_generic_bitmap gen_bm1,
609 ext2fs_generic_bitmap gen_bm2)
610 {
611 ext2fs_generic_bitmap_64 bm1 = (ext2fs_generic_bitmap_64) gen_bm1;
612 ext2fs_generic_bitmap_64 bm2 = (ext2fs_generic_bitmap_64) gen_bm2;
613 blk64_t i;
614
615 if (!bm1 || !bm2)
616 return EINVAL;
617 if (bm1->magic != bm2->magic)
618 return EINVAL;
619
620 /* Now we know both bitmaps have the same magic */
621 if (EXT2FS_IS_32_BITMAP(bm1))
622 return ext2fs_compare_generic_bitmap(bm1->magic, neq,
623 gen_bm1, gen_bm2);
624
625 if (!EXT2FS_IS_64_BITMAP(bm1))
626 return EINVAL;
627
628 if ((bm1->start != bm2->start) ||
629 (bm1->end != bm2->end))
630 return neq;
631
632 for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
633 if (ext2fs_test_generic_bmap(gen_bm1, i) !=
634 ext2fs_test_generic_bmap(gen_bm2, i))
635 return neq;
636
637 return 0;
638 }
639
ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap gen_bmap)640 void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap gen_bmap)
641 {
642 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
643 __u64 start, num;
644
645 if (EXT2FS_IS_32_BITMAP(bmap)) {
646 ext2fs_set_generic_bitmap_padding(gen_bmap);
647 return;
648 }
649
650 start = bmap->end + 1;
651 num = bmap->real_end - bmap->end;
652 bmap->bitmap_ops->mark_bmap_extent(bmap, start, num);
653 /* XXX ought to warn on error */
654 }
655
ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,blk64_t block,unsigned int num)656 int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
657 blk64_t block, unsigned int num)
658 {
659 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
660 __u64 end = block + num;
661
662 if (!bmap)
663 return EINVAL;
664
665 if (num == 1)
666 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap)
667 bmap, block);
668
669 if (EXT2FS_IS_32_BITMAP(bmap)) {
670 if ((block & ~0xffffffffULL) ||
671 ((block+num-1) & ~0xffffffffULL)) {
672 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
673 EXT2FS_UNMARK_ERROR, 0xffffffff);
674 return EINVAL;
675 }
676 return ext2fs_test_block_bitmap_range(
677 (ext2fs_generic_bitmap) bmap, block, num);
678 }
679
680 if (!EXT2FS_IS_64_BITMAP(bmap))
681 return EINVAL;
682
683 INC_STAT(bmap, test_ext_count);
684
685 /* convert to clusters if necessary */
686 block >>= bmap->cluster_bits;
687 end += (1 << bmap->cluster_bits) - 1;
688 end >>= bmap->cluster_bits;
689 num = end - block;
690
691 if ((block < bmap->start) || (block > bmap->end) ||
692 (block+num-1 > bmap->end)) {
693 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, block,
694 bmap->description);
695 return EINVAL;
696 }
697
698 return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
699 }
700
ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,blk64_t block,unsigned int num)701 void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
702 blk64_t block, unsigned int num)
703 {
704 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
705 __u64 end = block + num;
706
707 if (!bmap)
708 return;
709
710 if (EXT2FS_IS_32_BITMAP(bmap)) {
711 if ((block & ~0xffffffffULL) ||
712 ((block+num-1) & ~0xffffffffULL)) {
713 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
714 EXT2FS_UNMARK_ERROR, 0xffffffff);
715 return;
716 }
717 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
718 block, num);
719 }
720
721 if (!EXT2FS_IS_64_BITMAP(bmap))
722 return;
723
724 INC_STAT(bmap, mark_ext_count);
725
726 /* convert to clusters if necessary */
727 block >>= bmap->cluster_bits;
728 end += (1 << bmap->cluster_bits) - 1;
729 end >>= bmap->cluster_bits;
730 num = end - block;
731
732 if ((block < bmap->start) || (block > bmap->end) ||
733 (block+num-1 > bmap->end)) {
734 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
735 bmap->description);
736 return;
737 }
738
739 bmap->bitmap_ops->mark_bmap_extent(bmap, block, num);
740 }
741
ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,blk64_t block,unsigned int num)742 void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
743 blk64_t block, unsigned int num)
744 {
745 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
746 __u64 end = block + num;
747
748 if (!bmap)
749 return;
750
751 if (EXT2FS_IS_32_BITMAP(bmap)) {
752 if ((block & ~0xffffffffULL) ||
753 ((block+num-1) & ~0xffffffffULL)) {
754 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
755 EXT2FS_UNMARK_ERROR, 0xffffffff);
756 return;
757 }
758 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
759 block, num);
760 }
761
762 if (!EXT2FS_IS_64_BITMAP(bmap))
763 return;
764
765 INC_STAT(bmap, unmark_ext_count);
766
767 /* convert to clusters if necessary */
768 block >>= bmap->cluster_bits;
769 end += (1 << bmap->cluster_bits) - 1;
770 end >>= bmap->cluster_bits;
771 num = end - block;
772
773 if ((block < bmap->start) || (block > bmap->end) ||
774 (block+num-1 > bmap->end)) {
775 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
776 bmap->description);
777 return;
778 }
779
780 bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num);
781 }
782
ext2fs_warn_bitmap32(ext2fs_generic_bitmap gen_bitmap,const char * func)783 void ext2fs_warn_bitmap32(ext2fs_generic_bitmap gen_bitmap, const char *func)
784 {
785 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
786
787 #ifndef OMIT_COM_ERR
788 if (bitmap && bitmap->description)
789 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
790 "called %s with 64-bit bitmap for %s", func,
791 bitmap->description);
792 else
793 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
794 "called %s with 64-bit bitmap", func);
795 #endif
796 }
797
ext2fs_convert_subcluster_bitmap(ext2_filsys fs,ext2fs_block_bitmap * bitmap)798 errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
799 ext2fs_block_bitmap *bitmap)
800 {
801 ext2fs_generic_bitmap_64 bmap, cmap;
802 ext2fs_block_bitmap gen_bmap = *bitmap, gen_cmap;
803 errcode_t retval;
804 blk64_t i, next, b_end, c_end;
805
806 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
807 if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(gen_bmap))
808 return 0; /* Nothing to do */
809
810 retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap",
811 &gen_cmap);
812 if (retval)
813 return retval;
814
815 cmap = (ext2fs_generic_bitmap_64) gen_cmap;
816 i = bmap->start;
817 b_end = bmap->end;
818 bmap->end = bmap->real_end;
819 c_end = cmap->end;
820 cmap->end = cmap->real_end;
821 while (i < bmap->real_end) {
822 retval = ext2fs_find_first_set_block_bitmap2(gen_bmap,
823 i, bmap->real_end, &next);
824 if (retval)
825 break;
826 ext2fs_mark_block_bitmap2(gen_cmap, next);
827 i = EXT2FS_C2B(fs, EXT2FS_B2C(fs, next) + 1);
828 }
829 bmap->end = b_end;
830 cmap->end = c_end;
831 ext2fs_free_block_bitmap(gen_bmap);
832 *bitmap = (ext2fs_block_bitmap) cmap;
833 return 0;
834 }
835
ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,__u64 start,__u64 end,__u64 * out)836 errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
837 __u64 start, __u64 end, __u64 *out)
838 {
839 ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap;
840 __u64 cstart, cend, cout;
841 errcode_t retval;
842
843 if (!bitmap)
844 return EINVAL;
845
846 if (EXT2FS_IS_32_BITMAP(bitmap)) {
847 blk_t blk = 0;
848
849 if (((start) & ~0xffffffffULL) ||
850 ((end) & ~0xffffffffULL)) {
851 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
852 return EINVAL;
853 }
854
855 retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start,
856 end, &blk);
857 if (retval == 0)
858 *out = blk;
859 return retval;
860 }
861
862 if (!EXT2FS_IS_64_BITMAP(bitmap))
863 return EINVAL;
864
865 cstart = start >> bmap64->cluster_bits;
866 cend = end >> bmap64->cluster_bits;
867
868 if (cstart < bmap64->start || cend > bmap64->end || start > end) {
869 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start);
870 return EINVAL;
871 }
872
873 if (bmap64->bitmap_ops->find_first_zero) {
874 retval = bmap64->bitmap_ops->find_first_zero(bmap64, cstart,
875 cend, &cout);
876 if (retval)
877 return retval;
878 found:
879 cout <<= bmap64->cluster_bits;
880 *out = (cout >= start) ? cout : start;
881 return 0;
882 }
883
884 for (cout = cstart; cout <= cend; cout++)
885 if (!bmap64->bitmap_ops->test_bmap(bmap64, cout))
886 goto found;
887
888 return ENOENT;
889 }
890
ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,__u64 start,__u64 end,__u64 * out)891 errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,
892 __u64 start, __u64 end, __u64 *out)
893 {
894 ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap;
895 __u64 cstart, cend, cout;
896 errcode_t retval;
897
898 if (!bitmap)
899 return EINVAL;
900
901 if (EXT2FS_IS_32_BITMAP(bitmap)) {
902 blk_t blk = 0;
903
904 if (((start) & ~0xffffffffULL) ||
905 ((end) & ~0xffffffffULL)) {
906 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
907 return EINVAL;
908 }
909
910 retval = ext2fs_find_first_set_generic_bitmap(bitmap, start,
911 end, &blk);
912 if (retval == 0)
913 *out = blk;
914 return retval;
915 }
916
917 if (!EXT2FS_IS_64_BITMAP(bitmap))
918 return EINVAL;
919
920 cstart = start >> bmap64->cluster_bits;
921 cend = end >> bmap64->cluster_bits;
922
923 if (cstart < bmap64->start || cend > bmap64->end || start > end) {
924 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start);
925 return EINVAL;
926 }
927
928 if (bmap64->bitmap_ops->find_first_set) {
929 retval = bmap64->bitmap_ops->find_first_set(bmap64, cstart,
930 cend, &cout);
931 if (retval)
932 return retval;
933 found:
934 cout <<= bmap64->cluster_bits;
935 *out = (cout >= start) ? cout : start;
936 return 0;
937 }
938
939 for (cout = cstart; cout <= cend; cout++)
940 if (bmap64->bitmap_ops->test_bmap(bmap64, cout))
941 goto found;
942
943 return ENOENT;
944 }
945
ext2fs_count_used_clusters(ext2_filsys fs,blk64_t start,blk64_t end,blk64_t * out)946 errcode_t ext2fs_count_used_clusters(ext2_filsys fs, blk64_t start,
947 blk64_t end, blk64_t *out)
948 {
949 blk64_t next;
950 blk64_t tot_set = 0;
951 errcode_t retval = 0;
952
953 while (start < end) {
954 retval = ext2fs_find_first_set_block_bitmap2(fs->block_map,
955 start, end, &next);
956 if (retval) {
957 if (retval == ENOENT)
958 retval = 0;
959 break;
960 }
961 start = next;
962
963 retval = ext2fs_find_first_zero_block_bitmap2(fs->block_map,
964 start, end, &next);
965 if (retval == 0) {
966 tot_set += next - start;
967 start = next + 1;
968 } else if (retval == ENOENT) {
969 retval = 0;
970 tot_set += end - start + 1;
971 break;
972 } else
973 break;
974 }
975
976 if (!retval)
977 *out = EXT2FS_NUM_B2C(fs, tot_set);
978 return retval;
979 }
980