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