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 struct timeval now;
187 double inuse;
188
189 if (stats->test_count) {
190 test_seq_perc = ((float)stats->test_seq /
191 stats->test_count) * 100;
192 test_back_perc = ((float)stats->test_back /
193 stats->test_count) * 100;
194 }
195
196 if (stats->mark_count) {
197 mark_seq_perc = ((float)stats->mark_seq /
198 stats->mark_count) * 100;
199 mark_back_perc = ((float)stats->mark_back /
200 stats->mark_count) * 100;
201 }
202
203 if (gettimeofday(&now, (struct timezone *) NULL) == -1) {
204 perror("gettimeofday");
205 return;
206 }
207
208 inuse = (double) now.tv_sec + \
209 (((double) now.tv_usec) * 0.000001);
210 inuse -= (double) stats->created.tv_sec + \
211 (((double) stats->created.tv_usec) * 0.000001);
212 #endif /* ENABLE_BMAP_STATS_OPS */
213
214 fprintf(stderr, "\n[+] %s bitmap (type %d)\n", bitmap->description,
215 stats->type);
216 fprintf(stderr, "=================================================\n");
217 #ifdef ENABLE_BMAP_STATS_OPS
218 fprintf(stderr, "%16llu bits long\n",
219 bitmap->real_end - bitmap->start);
220 fprintf(stderr, "%16lu copy_bmap\n%16lu resize_bmap\n",
221 stats->copy_count, stats->resize_count);
222 fprintf(stderr, "%16lu mark bmap\n%16lu unmark_bmap\n",
223 stats->mark_count, stats->unmark_count);
224 fprintf(stderr, "%16lu test_bmap\n%16lu mark_bmap_extent\n",
225 stats->test_count, stats->mark_ext_count);
226 fprintf(stderr, "%16lu unmark_bmap_extent\n"
227 "%16lu test_clear_bmap_extent\n",
228 stats->unmark_ext_count, stats->test_ext_count);
229 fprintf(stderr, "%16lu set_bmap_range\n%16lu set_bmap_range\n",
230 stats->set_range_count, stats->get_range_count);
231 fprintf(stderr, "%16lu clear_bmap\n%16lu contiguous bit test (%.2f%%)\n",
232 stats->clear_count, stats->test_seq, test_seq_perc);
233 fprintf(stderr, "%16lu contiguous bit mark (%.2f%%)\n"
234 "%16llu bits tested backwards (%.2f%%)\n",
235 stats->mark_seq, mark_seq_perc,
236 stats->test_back, test_back_perc);
237 fprintf(stderr, "%16llu bits marked backwards (%.2f%%)\n"
238 "%16.2f seconds in use\n",
239 stats->mark_back, mark_back_perc, inuse);
240 #endif /* ENABLE_BMAP_STATS_OPS */
241 }
242 #endif
243
ext2fs_free_generic_bmap(ext2fs_generic_bitmap gen_bmap)244 void ext2fs_free_generic_bmap(ext2fs_generic_bitmap gen_bmap)
245 {
246 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
247
248 if (!bmap)
249 return;
250
251 if (EXT2FS_IS_32_BITMAP(bmap)) {
252 ext2fs_free_generic_bitmap(gen_bmap);
253 return;
254 }
255
256 if (!EXT2FS_IS_64_BITMAP(bmap))
257 return;
258
259 #ifdef ENABLE_BMAP_STATS
260 if (getenv("E2FSPROGS_BITMAP_STATS")) {
261 ext2fs_print_bmap_statistics(bmap);
262 bmap->bitmap_ops->print_stats(bmap);
263 }
264 #endif
265
266 bmap->bitmap_ops->free_bmap(bmap);
267
268 if (bmap->description) {
269 ext2fs_free_mem(&bmap->description);
270 bmap->description = 0;
271 }
272 bmap->magic = 0;
273 ext2fs_free_mem(&bmap);
274 }
275
ext2fs_copy_generic_bmap(ext2fs_generic_bitmap gen_src,ext2fs_generic_bitmap * dest)276 errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap gen_src,
277 ext2fs_generic_bitmap *dest)
278 {
279 ext2fs_generic_bitmap_64 src = (ext2fs_generic_bitmap_64) gen_src;
280 char *descr, *new_descr;
281 ext2fs_generic_bitmap_64 new_bmap;
282 errcode_t retval;
283
284 if (!src)
285 return EINVAL;
286
287 if (EXT2FS_IS_32_BITMAP(src))
288 return ext2fs_copy_generic_bitmap(gen_src, dest);
289
290 if (!EXT2FS_IS_64_BITMAP(src))
291 return EINVAL;
292
293 /* Allocate a new bitmap struct */
294 retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap_64),
295 &new_bmap);
296 if (retval)
297 return retval;
298
299
300 #ifdef ENABLE_BMAP_STATS_OPS
301 src->stats.copy_count++;
302 #endif
303 #ifdef ENABLE_BMAP_STATS
304 if (gettimeofday(&new_bmap->stats.created,
305 (struct timezone *) NULL) == -1) {
306 perror("gettimeofday");
307 ext2fs_free_mem(&new_bmap);
308 return 1;
309 }
310 new_bmap->stats.type = src->stats.type;
311 #endif
312
313 /* Copy all the high-level parts over */
314 new_bmap->magic = src->magic;
315 new_bmap->fs = src->fs;
316 new_bmap->start = src->start;
317 new_bmap->end = src->end;
318 new_bmap->real_end = src->real_end;
319 new_bmap->bitmap_ops = src->bitmap_ops;
320 new_bmap->base_error_code = src->base_error_code;
321 new_bmap->cluster_bits = src->cluster_bits;
322
323 descr = src->description;
324 if (descr) {
325 retval = ext2fs_get_mem(strlen(descr)+10, &new_descr);
326 if (retval) {
327 ext2fs_free_mem(&new_bmap);
328 return retval;
329 }
330 strcpy(new_descr, "copy of ");
331 strcat(new_descr, descr);
332 new_bmap->description = new_descr;
333 }
334
335 retval = src->bitmap_ops->copy_bmap(src, new_bmap);
336 if (retval) {
337 ext2fs_free_mem(&new_bmap->description);
338 ext2fs_free_mem(&new_bmap);
339 return retval;
340 }
341
342 *dest = (ext2fs_generic_bitmap) new_bmap;
343
344 return 0;
345 }
346
ext2fs_resize_generic_bmap(ext2fs_generic_bitmap gen_bmap,__u64 new_end,__u64 new_real_end)347 errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap gen_bmap,
348 __u64 new_end,
349 __u64 new_real_end)
350 {
351 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
352
353 if (!bmap)
354 return EINVAL;
355
356 if (EXT2FS_IS_32_BITMAP(bmap))
357 return ext2fs_resize_generic_bitmap(gen_bmap->magic, new_end,
358 new_real_end, gen_bmap);
359
360 if (!EXT2FS_IS_64_BITMAP(bmap))
361 return EINVAL;
362
363 INC_STAT(bmap, resize_count);
364
365 return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
366 }
367
ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap,errcode_t neq,__u64 end,__u64 * oend)368 errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap,
369 errcode_t neq,
370 __u64 end, __u64 *oend)
371 {
372 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
373
374 if (!bitmap)
375 return EINVAL;
376
377 if (EXT2FS_IS_32_BITMAP(bitmap)) {
378 ext2_ino_t tmp_oend;
379 int retval;
380
381 retval = ext2fs_fudge_generic_bitmap_end(gen_bitmap,
382 bitmap->magic,
383 neq, end, &tmp_oend);
384 if (oend)
385 *oend = tmp_oend;
386 return retval;
387 }
388
389 if (!EXT2FS_IS_64_BITMAP(bitmap))
390 return EINVAL;
391
392 if (end > bitmap->real_end)
393 return neq;
394 if (oend)
395 *oend = bitmap->end;
396 bitmap->end = end;
397 return 0;
398 }
399
ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap gen_bitmap)400 __u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap gen_bitmap)
401 {
402 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
403
404 if (!bitmap)
405 return EINVAL;
406
407 if (EXT2FS_IS_32_BITMAP(bitmap))
408 return ext2fs_get_generic_bitmap_start(gen_bitmap);
409
410 if (!EXT2FS_IS_64_BITMAP(bitmap))
411 return EINVAL;
412
413 return bitmap->start;
414 }
415
ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap)416 __u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap)
417 {
418 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
419
420 if (!bitmap)
421 return EINVAL;
422
423 if (EXT2FS_IS_32_BITMAP(bitmap))
424 return ext2fs_get_generic_bitmap_end(gen_bitmap);
425
426 if (!EXT2FS_IS_64_BITMAP(bitmap))
427 return EINVAL;
428
429 return bitmap->end;
430 }
431
ext2fs_clear_generic_bmap(ext2fs_generic_bitmap gen_bitmap)432 void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap gen_bitmap)
433 {
434 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
435
436 if (EXT2FS_IS_32_BITMAP(bitmap))
437 ext2fs_clear_generic_bitmap(gen_bitmap);
438 else
439 bitmap->bitmap_ops->clear_bmap(bitmap);
440 }
441
ext2fs_mark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,__u64 arg)442 int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
443 __u64 arg)
444 {
445 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
446
447 if (!bitmap)
448 return 0;
449
450 if (EXT2FS_IS_32_BITMAP(bitmap)) {
451 if (arg & ~0xffffffffULL) {
452 ext2fs_warn_bitmap2(gen_bitmap,
453 EXT2FS_MARK_ERROR, 0xffffffff);
454 return 0;
455 }
456 return ext2fs_mark_generic_bitmap(gen_bitmap, arg);
457 }
458
459 if (!EXT2FS_IS_64_BITMAP(bitmap))
460 return 0;
461
462 arg >>= bitmap->cluster_bits;
463
464 #ifdef ENABLE_BMAP_STATS_OPS
465 if (arg == bitmap->stats.last_marked + 1)
466 bitmap->stats.mark_seq++;
467 if (arg < bitmap->stats.last_marked)
468 bitmap->stats.mark_back++;
469 bitmap->stats.last_marked = arg;
470 bitmap->stats.mark_count++;
471 #endif
472
473 if ((arg < bitmap->start) || (arg > bitmap->end)) {
474 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
475 return 0;
476 }
477
478 return bitmap->bitmap_ops->mark_bmap(bitmap, arg);
479 }
480
ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,__u64 arg)481 int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
482 __u64 arg)
483 {
484 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
485
486 if (!bitmap)
487 return 0;
488
489 if (EXT2FS_IS_32_BITMAP(bitmap)) {
490 if (arg & ~0xffffffffULL) {
491 ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_UNMARK_ERROR,
492 0xffffffff);
493 return 0;
494 }
495 return ext2fs_unmark_generic_bitmap(gen_bitmap, arg);
496 }
497
498 if (!EXT2FS_IS_64_BITMAP(bitmap))
499 return 0;
500
501 arg >>= bitmap->cluster_bits;
502
503 INC_STAT(bitmap, unmark_count);
504
505 if ((arg < bitmap->start) || (arg > bitmap->end)) {
506 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
507 return 0;
508 }
509
510 return bitmap->bitmap_ops->unmark_bmap(bitmap, arg);
511 }
512
ext2fs_test_generic_bmap(ext2fs_generic_bitmap gen_bitmap,__u64 arg)513 int ext2fs_test_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
514 __u64 arg)
515 {
516 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
517 if (!bitmap)
518 return 0;
519
520 if (EXT2FS_IS_32_BITMAP(bitmap)) {
521 if (arg & ~0xffffffffULL) {
522 ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_TEST_ERROR,
523 0xffffffff);
524 return 0;
525 }
526 return ext2fs_test_generic_bitmap(gen_bitmap, arg);
527 }
528
529 if (!EXT2FS_IS_64_BITMAP(bitmap))
530 return 0;
531
532 arg >>= bitmap->cluster_bits;
533
534 #ifdef ENABLE_BMAP_STATS_OPS
535 bitmap->stats.test_count++;
536 if (arg == bitmap->stats.last_tested + 1)
537 bitmap->stats.test_seq++;
538 if (arg < bitmap->stats.last_tested)
539 bitmap->stats.test_back++;
540 bitmap->stats.last_tested = arg;
541 #endif
542
543 if ((arg < bitmap->start) || (arg > bitmap->end)) {
544 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
545 return 0;
546 }
547
548 return bitmap->bitmap_ops->test_bmap(bitmap, arg);
549 }
550
ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,__u64 start,unsigned int num,void * in)551 errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,
552 __u64 start, unsigned int num,
553 void *in)
554 {
555 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
556
557 if (!bmap)
558 return EINVAL;
559
560 if (EXT2FS_IS_32_BITMAP(bmap)) {
561 if ((start+num-1) & ~0xffffffffULL) {
562 ext2fs_warn_bitmap2(gen_bmap, EXT2FS_UNMARK_ERROR,
563 0xffffffff);
564 return EINVAL;
565 }
566 return ext2fs_set_generic_bitmap_range(gen_bmap, bmap->magic,
567 start, num, in);
568 }
569
570 if (!EXT2FS_IS_64_BITMAP(bmap))
571 return EINVAL;
572
573 INC_STAT(bmap, set_range_count);
574
575 return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
576 }
577
ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,__u64 start,unsigned int num,void * out)578 errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,
579 __u64 start, unsigned int num,
580 void *out)
581 {
582 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
583
584 if (!bmap)
585 return EINVAL;
586
587 if (EXT2FS_IS_32_BITMAP(bmap)) {
588 if ((start+num-1) & ~0xffffffffULL) {
589 ext2fs_warn_bitmap2(gen_bmap,
590 EXT2FS_UNMARK_ERROR, 0xffffffff);
591 return EINVAL;
592 }
593 return ext2fs_get_generic_bitmap_range(gen_bmap, bmap->magic,
594 start, num, out);
595 }
596
597 if (!EXT2FS_IS_64_BITMAP(bmap))
598 return EINVAL;
599
600 INC_STAT(bmap, get_range_count);
601
602 return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
603 }
604
ext2fs_compare_generic_bmap(errcode_t neq,ext2fs_generic_bitmap gen_bm1,ext2fs_generic_bitmap gen_bm2)605 errcode_t ext2fs_compare_generic_bmap(errcode_t neq,
606 ext2fs_generic_bitmap gen_bm1,
607 ext2fs_generic_bitmap gen_bm2)
608 {
609 ext2fs_generic_bitmap_64 bm1 = (ext2fs_generic_bitmap_64) gen_bm1;
610 ext2fs_generic_bitmap_64 bm2 = (ext2fs_generic_bitmap_64) gen_bm2;
611 blk64_t i;
612
613 if (!bm1 || !bm2)
614 return EINVAL;
615 if (bm1->magic != bm2->magic)
616 return EINVAL;
617
618 /* Now we know both bitmaps have the same magic */
619 if (EXT2FS_IS_32_BITMAP(bm1))
620 return ext2fs_compare_generic_bitmap(bm1->magic, neq,
621 gen_bm1, gen_bm2);
622
623 if (!EXT2FS_IS_64_BITMAP(bm1))
624 return EINVAL;
625
626 if ((bm1->start != bm2->start) ||
627 (bm1->end != bm2->end))
628 return neq;
629
630 for (i = bm1->start; i < bm1->end; i++) {
631 int ret1, ret2;
632 ret1 = !!ext2fs_test_generic_bmap(gen_bm1, i);
633 ret2 = !!ext2fs_test_generic_bmap(gen_bm2, i);
634 if (ret1 != ret2) {
635 return neq;
636 }
637 }
638
639 return 0;
640 }
641
ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap gen_bmap)642 void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap gen_bmap)
643 {
644 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
645 __u64 start, num;
646
647 if (EXT2FS_IS_32_BITMAP(bmap)) {
648 ext2fs_set_generic_bitmap_padding(gen_bmap);
649 return;
650 }
651
652 start = bmap->end + 1;
653 num = bmap->real_end - bmap->end;
654 bmap->bitmap_ops->mark_bmap_extent(bmap, start, num);
655 /* XXX ought to warn on error */
656 }
657
ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,blk64_t block,unsigned int num)658 int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
659 blk64_t block, unsigned int num)
660 {
661 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
662 __u64 end = block + num;
663
664 if (!bmap)
665 return EINVAL;
666
667 if (num == 1)
668 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap)
669 bmap, block);
670
671 if (EXT2FS_IS_32_BITMAP(bmap)) {
672 if ((block & ~0xffffffffULL) ||
673 ((block+num-1) & ~0xffffffffULL)) {
674 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
675 EXT2FS_UNMARK_ERROR, 0xffffffff);
676 return EINVAL;
677 }
678 return ext2fs_test_block_bitmap_range(
679 (ext2fs_generic_bitmap) bmap, block, num);
680 }
681
682 if (!EXT2FS_IS_64_BITMAP(bmap))
683 return EINVAL;
684
685 INC_STAT(bmap, test_ext_count);
686
687 /* convert to clusters if necessary */
688 block >>= bmap->cluster_bits;
689 end += (1ULL << bmap->cluster_bits) - 1;
690 end >>= bmap->cluster_bits;
691 num = end - block;
692
693 if ((block < bmap->start) || (block > bmap->end) ||
694 (block+num-1 > bmap->end)) {
695 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, block,
696 bmap->description);
697 return EINVAL;
698 }
699
700 return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
701 }
702
ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,blk64_t block,unsigned int num)703 void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
704 blk64_t block, unsigned int num)
705 {
706 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
707 __u64 end = block + num;
708
709 if (!bmap)
710 return;
711
712 if (EXT2FS_IS_32_BITMAP(bmap)) {
713 if ((block & ~0xffffffffULL) ||
714 ((block+num-1) & ~0xffffffffULL)) {
715 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
716 EXT2FS_UNMARK_ERROR, 0xffffffff);
717 return;
718 }
719 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
720 block, num);
721 }
722
723 if (!EXT2FS_IS_64_BITMAP(bmap))
724 return;
725
726 INC_STAT(bmap, mark_ext_count);
727
728 /* convert to clusters if necessary */
729 block >>= bmap->cluster_bits;
730 end += (1ULL << bmap->cluster_bits) - 1;
731 end >>= bmap->cluster_bits;
732 num = end - block;
733
734 if ((block < bmap->start) || (block > bmap->end) ||
735 (block+num-1 > bmap->end)) {
736 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
737 bmap->description);
738 return;
739 }
740
741 bmap->bitmap_ops->mark_bmap_extent(bmap, block, num);
742 }
743
ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,blk64_t block,unsigned int num)744 void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
745 blk64_t block, unsigned int num)
746 {
747 ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
748 __u64 end = block + num;
749
750 if (!bmap)
751 return;
752
753 if (EXT2FS_IS_32_BITMAP(bmap)) {
754 if ((block & ~0xffffffffULL) ||
755 ((block+num-1) & ~0xffffffffULL)) {
756 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
757 EXT2FS_UNMARK_ERROR, 0xffffffff);
758 return;
759 }
760 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
761 block, num);
762 }
763
764 if (!EXT2FS_IS_64_BITMAP(bmap))
765 return;
766
767 INC_STAT(bmap, unmark_ext_count);
768
769 /* convert to clusters if necessary */
770 block >>= bmap->cluster_bits;
771 end += (1ULL << bmap->cluster_bits) - 1;
772 end >>= bmap->cluster_bits;
773 num = end - block;
774
775 if ((block < bmap->start) || (block > bmap->end) ||
776 (block+num-1 > bmap->end)) {
777 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
778 bmap->description);
779 return;
780 }
781
782 bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num);
783 }
784
ext2fs_warn_bitmap32(ext2fs_generic_bitmap gen_bitmap,const char * func)785 void ext2fs_warn_bitmap32(ext2fs_generic_bitmap gen_bitmap, const char *func)
786 {
787 ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
788
789 #ifndef OMIT_COM_ERR
790 if (bitmap && bitmap->description)
791 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
792 "called %s with 64-bit bitmap for %s", func,
793 bitmap->description);
794 else
795 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
796 "called %s with 64-bit bitmap", func);
797 #endif
798 }
799
ext2fs_convert_subcluster_bitmap(ext2_filsys fs,ext2fs_block_bitmap * bitmap)800 errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
801 ext2fs_block_bitmap *bitmap)
802 {
803 ext2fs_generic_bitmap_64 bmap, cmap;
804 ext2fs_block_bitmap gen_bmap = *bitmap, gen_cmap;
805 errcode_t retval;
806 blk64_t i, next, b_end, c_end;
807
808 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
809 if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(gen_bmap))
810 return 0; /* Nothing to do */
811
812 retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap",
813 &gen_cmap);
814 if (retval)
815 return retval;
816
817 cmap = (ext2fs_generic_bitmap_64) gen_cmap;
818 i = bmap->start;
819 b_end = bmap->end;
820 bmap->end = bmap->real_end;
821 c_end = cmap->end;
822 cmap->end = cmap->real_end;
823 while (i < bmap->real_end) {
824 retval = ext2fs_find_first_set_block_bitmap2(gen_bmap,
825 i, bmap->real_end, &next);
826 if (retval)
827 break;
828 ext2fs_mark_block_bitmap2(gen_cmap, next);
829 i = EXT2FS_C2B(fs, EXT2FS_B2C(fs, next) + 1);
830 }
831 bmap->end = b_end;
832 cmap->end = c_end;
833 ext2fs_free_block_bitmap(gen_bmap);
834 *bitmap = (ext2fs_block_bitmap) cmap;
835 return 0;
836 }
837
ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,__u64 start,__u64 end,__u64 * out)838 errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
839 __u64 start, __u64 end, __u64 *out)
840 {
841 ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap;
842 __u64 cstart, cend, cout;
843 errcode_t retval;
844
845 if (!bitmap)
846 return EINVAL;
847
848 if (EXT2FS_IS_32_BITMAP(bitmap)) {
849 blk_t blk = 0;
850
851 if (((start) & ~0xffffffffULL) ||
852 ((end) & ~0xffffffffULL)) {
853 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
854 return EINVAL;
855 }
856
857 retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start,
858 end, &blk);
859 if (retval == 0)
860 *out = blk;
861 return retval;
862 }
863
864 if (!EXT2FS_IS_64_BITMAP(bitmap))
865 return EINVAL;
866
867 cstart = start >> bmap64->cluster_bits;
868 cend = end >> bmap64->cluster_bits;
869
870 if (cstart < bmap64->start || cend > bmap64->end || start > end) {
871 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start);
872 return EINVAL;
873 }
874
875 if (bmap64->bitmap_ops->find_first_zero) {
876 retval = bmap64->bitmap_ops->find_first_zero(bmap64, cstart,
877 cend, &cout);
878 if (retval)
879 return retval;
880 found:
881 cout <<= bmap64->cluster_bits;
882 *out = (cout >= start) ? cout : start;
883 return 0;
884 }
885
886 for (cout = cstart; cout <= cend; cout++)
887 if (!bmap64->bitmap_ops->test_bmap(bmap64, cout))
888 goto found;
889
890 return ENOENT;
891 }
892
ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,__u64 start,__u64 end,__u64 * out)893 errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,
894 __u64 start, __u64 end, __u64 *out)
895 {
896 ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap;
897 __u64 cstart, cend, cout;
898 errcode_t retval;
899
900 if (!bitmap)
901 return EINVAL;
902
903 if (EXT2FS_IS_32_BITMAP(bitmap)) {
904 blk_t blk = 0;
905
906 if (((start) & ~0xffffffffULL) ||
907 ((end) & ~0xffffffffULL)) {
908 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
909 return EINVAL;
910 }
911
912 retval = ext2fs_find_first_set_generic_bitmap(bitmap, start,
913 end, &blk);
914 if (retval == 0)
915 *out = blk;
916 return retval;
917 }
918
919 if (!EXT2FS_IS_64_BITMAP(bitmap))
920 return EINVAL;
921
922 cstart = start >> bmap64->cluster_bits;
923 cend = end >> bmap64->cluster_bits;
924
925 if (cstart < bmap64->start || cend > bmap64->end || start > end) {
926 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start);
927 return EINVAL;
928 }
929
930 if (bmap64->bitmap_ops->find_first_set) {
931 retval = bmap64->bitmap_ops->find_first_set(bmap64, cstart,
932 cend, &cout);
933 if (retval)
934 return retval;
935 found:
936 cout <<= bmap64->cluster_bits;
937 *out = (cout >= start) ? cout : start;
938 return 0;
939 }
940
941 for (cout = cstart; cout <= cend; cout++)
942 if (bmap64->bitmap_ops->test_bmap(bmap64, cout))
943 goto found;
944
945 return ENOENT;
946 }
947
ext2fs_count_used_clusters(ext2_filsys fs,blk64_t start,blk64_t end,blk64_t * out)948 errcode_t ext2fs_count_used_clusters(ext2_filsys fs, blk64_t start,
949 blk64_t end, blk64_t *out)
950 {
951 blk64_t next;
952 blk64_t tot_set = 0;
953 errcode_t retval = 0;
954
955 while (start < end) {
956 retval = ext2fs_find_first_set_block_bitmap2(fs->block_map,
957 start, end, &next);
958 if (retval) {
959 if (retval == ENOENT)
960 retval = 0;
961 break;
962 }
963 start = next;
964
965 retval = ext2fs_find_first_zero_block_bitmap2(fs->block_map,
966 start, end, &next);
967 if (retval == 0) {
968 tot_set += next - start;
969 start = next + 1;
970 } else if (retval == ENOENT) {
971 retval = 0;
972 tot_set += end - start + 1;
973 break;
974 } else
975 break;
976 }
977
978 if (!retval)
979 *out = EXT2FS_NUM_B2C(fs, tot_set);
980 return retval;
981 }
982