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 bitmap,int code,__u64 arg)71 static void warn_bitmap(ext2fs_generic_bitmap 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", arg, bitmap->description);
78 else
79 com_err(0, bitmap->base_error_code + code, "#%llu", arg);
80 #endif
81 }
82
83 #ifdef ENABLE_BMAP_STATS_OPS
84 #define INC_STAT(map, name) map->stats.name
85 #else
86 #define INC_STAT(map, name) ;;
87 #endif
88
89
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)90 errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
91 int type, __u64 start, __u64 end,
92 __u64 real_end,
93 const char *descr,
94 ext2fs_generic_bitmap *ret)
95 {
96 ext2fs_generic_bitmap bitmap;
97 struct ext2_bitmap_ops *ops;
98 ext2_ino_t num_dirs;
99 errcode_t retval;
100
101 if (!type)
102 type = EXT2FS_BMAP64_BITARRAY;
103
104 switch (type) {
105 case EXT2FS_BMAP64_BITARRAY:
106 ops = &ext2fs_blkmap64_bitarray;
107 break;
108 case EXT2FS_BMAP64_RBTREE:
109 ops = &ext2fs_blkmap64_rbtree;
110 break;
111 case EXT2FS_BMAP64_AUTODIR:
112 retval = ext2fs_get_num_dirs(fs, &num_dirs);
113 if (retval || num_dirs > (fs->super->s_inodes_count / 320))
114 ops = &ext2fs_blkmap64_bitarray;
115 else
116 ops = &ext2fs_blkmap64_rbtree;
117 break;
118 default:
119 return EINVAL;
120 }
121
122 retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap),
123 &bitmap);
124 if (retval)
125 return retval;
126
127 #ifdef ENABLE_BMAP_STATS
128 if (gettimeofday(&bitmap->stats.created,
129 (struct timezone *) NULL) == -1) {
130 perror("gettimeofday");
131 ext2fs_free_mem(&bitmap);
132 return 1;
133 }
134 bitmap->stats.type = type;
135 #endif
136
137 /* XXX factor out, repeated in copy_bmap */
138 bitmap->magic = magic;
139 bitmap->fs = fs;
140 bitmap->start = start;
141 bitmap->end = end;
142 bitmap->real_end = real_end;
143 bitmap->bitmap_ops = ops;
144 bitmap->cluster_bits = 0;
145 switch (magic) {
146 case EXT2_ET_MAGIC_INODE_BITMAP64:
147 bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK;
148 break;
149 case EXT2_ET_MAGIC_BLOCK_BITMAP64:
150 bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK;
151 bitmap->cluster_bits = fs->cluster_ratio_bits;
152 break;
153 default:
154 bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK;
155 }
156 if (descr) {
157 retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description);
158 if (retval) {
159 ext2fs_free_mem(&bitmap);
160 return retval;
161 }
162 strcpy(bitmap->description, descr);
163 } else
164 bitmap->description = 0;
165
166 retval = bitmap->bitmap_ops->new_bmap(fs, bitmap);
167 if (retval) {
168 ext2fs_free_mem(&bitmap->description);
169 ext2fs_free_mem(&bitmap);
170 return retval;
171 }
172
173 *ret = bitmap;
174 return 0;
175 }
176
177 #ifdef ENABLE_BMAP_STATS
ext2fs_print_bmap_statistics(ext2fs_generic_bitmap bitmap)178 static void ext2fs_print_bmap_statistics(ext2fs_generic_bitmap bitmap)
179 {
180 struct ext2_bmap_statistics *stats = &bitmap->stats;
181 #ifdef ENABLE_BMAP_STATS_OPS
182 float mark_seq_perc = 0.0, test_seq_perc = 0.0;
183 float mark_back_perc = 0.0, test_back_perc = 0.0;
184 #endif
185 double inuse;
186 struct timeval now;
187
188 #ifdef ENABLE_BMAP_STATS_OPS
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 #endif
203
204 if (gettimeofday(&now, (struct timezone *) NULL) == -1) {
205 perror("gettimeofday");
206 return;
207 }
208
209 inuse = (double) now.tv_sec + \
210 (((double) now.tv_usec) * 0.000001);
211 inuse -= (double) stats->created.tv_sec + \
212 (((double) stats->created.tv_usec) * 0.000001);
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 bmap)244 void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
245 {
246 if (!bmap)
247 return;
248
249 if (EXT2FS_IS_32_BITMAP(bmap)) {
250 ext2fs_free_generic_bitmap(bmap);
251 return;
252 }
253
254 if (!EXT2FS_IS_64_BITMAP(bmap))
255 return;
256
257 #ifdef ENABLE_BMAP_STATS
258 if (getenv("E2FSPROGS_BITMAP_STATS")) {
259 ext2fs_print_bmap_statistics(bmap);
260 bmap->bitmap_ops->print_stats(bmap);
261 }
262 #endif
263
264 bmap->bitmap_ops->free_bmap(bmap);
265
266 if (bmap->description) {
267 ext2fs_free_mem(&bmap->description);
268 bmap->description = 0;
269 }
270 bmap->magic = 0;
271 ext2fs_free_mem(&bmap);
272 }
273
ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,ext2fs_generic_bitmap * dest)274 errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
275 ext2fs_generic_bitmap *dest)
276 {
277 char *descr, *new_descr;
278 ext2fs_generic_bitmap new_bmap;
279 errcode_t retval;
280
281 if (!src)
282 return EINVAL;
283
284 if (EXT2FS_IS_32_BITMAP(src))
285 return ext2fs_copy_generic_bitmap(src, dest);
286
287 if (!EXT2FS_IS_64_BITMAP(src))
288 return EINVAL;
289
290 /* Allocate a new bitmap struct */
291 retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap),
292 &new_bmap);
293 if (retval)
294 return retval;
295
296
297 #ifdef ENABLE_BMAP_STATS_OPS
298 src->stats.copy_count++;
299 #endif
300 #ifdef ENABLE_BMAP_STATS
301 if (gettimeofday(&new_bmap->stats.created,
302 (struct timezone *) NULL) == -1) {
303 perror("gettimeofday");
304 ext2fs_free_mem(&new_bmap);
305 return 1;
306 }
307 new_bmap->stats.type = src->stats.type;
308 #endif
309
310 /* Copy all the high-level parts over */
311 new_bmap->magic = src->magic;
312 new_bmap->fs = src->fs;
313 new_bmap->start = src->start;
314 new_bmap->end = src->end;
315 new_bmap->real_end = src->real_end;
316 new_bmap->bitmap_ops = src->bitmap_ops;
317 new_bmap->base_error_code = src->base_error_code;
318 new_bmap->cluster_bits = src->cluster_bits;
319
320 descr = src->description;
321 if (descr) {
322 retval = ext2fs_get_mem(strlen(descr)+10, &new_descr);
323 if (retval) {
324 ext2fs_free_mem(&new_bmap);
325 return retval;
326 }
327 strcpy(new_descr, "copy of ");
328 strcat(new_descr, descr);
329 new_bmap->description = new_descr;
330 }
331
332 retval = src->bitmap_ops->copy_bmap(src, new_bmap);
333 if (retval) {
334 ext2fs_free_mem(&new_bmap->description);
335 ext2fs_free_mem(&new_bmap);
336 return retval;
337 }
338
339 *dest = new_bmap;
340
341 return 0;
342 }
343
ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap,__u64 new_end,__u64 new_real_end)344 errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap,
345 __u64 new_end,
346 __u64 new_real_end)
347 {
348 if (!bmap)
349 return EINVAL;
350
351 if (EXT2FS_IS_32_BITMAP(bmap))
352 return ext2fs_resize_generic_bitmap(bmap->magic, new_end,
353 new_real_end, bmap);
354
355 if (!EXT2FS_IS_64_BITMAP(bmap))
356 return EINVAL;
357
358 INC_STAT(bmap, resize_count);
359
360 return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
361 }
362
ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap bitmap,errcode_t neq,__u64 end,__u64 * oend)363 errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap bitmap,
364 errcode_t neq,
365 __u64 end, __u64 *oend)
366 {
367 if (!bitmap)
368 return EINVAL;
369
370 if (EXT2FS_IS_32_BITMAP(bitmap)) {
371 ext2_ino_t tmp_oend;
372 int retval;
373
374 retval = ext2fs_fudge_generic_bitmap_end(bitmap, bitmap->magic,
375 neq, end, &tmp_oend);
376 if (oend)
377 *oend = tmp_oend;
378 return retval;
379 }
380
381 if (!EXT2FS_IS_64_BITMAP(bitmap))
382 return EINVAL;
383
384 if (end > bitmap->real_end)
385 return neq;
386 if (oend)
387 *oend = bitmap->end;
388 bitmap->end = end;
389 return 0;
390 }
391
ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap bitmap)392 __u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap bitmap)
393 {
394 if (!bitmap)
395 return EINVAL;
396
397 if (EXT2FS_IS_32_BITMAP(bitmap))
398 return ext2fs_get_generic_bitmap_start(bitmap);
399
400 if (!EXT2FS_IS_64_BITMAP(bitmap))
401 return EINVAL;
402
403 return bitmap->start;
404 }
405
ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap bitmap)406 __u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap bitmap)
407 {
408 if (!bitmap)
409 return EINVAL;
410
411 if (EXT2FS_IS_32_BITMAP(bitmap))
412 return ext2fs_get_generic_bitmap_end(bitmap);
413
414 if (!EXT2FS_IS_64_BITMAP(bitmap))
415 return EINVAL;
416
417 return bitmap->end;
418 }
419
ext2fs_clear_generic_bmap(ext2fs_generic_bitmap bitmap)420 void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap bitmap)
421 {
422 if (EXT2FS_IS_32_BITMAP(bitmap))
423 ext2fs_clear_generic_bitmap(bitmap);
424 else
425 bitmap->bitmap_ops->clear_bmap (bitmap);
426 }
427
ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap,__u64 arg)428 int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap,
429 __u64 arg)
430 {
431 if (!bitmap)
432 return 0;
433
434 if (EXT2FS_IS_32_BITMAP(bitmap)) {
435 if (arg & ~0xffffffffULL) {
436 ext2fs_warn_bitmap2(bitmap,
437 EXT2FS_MARK_ERROR, 0xffffffff);
438 return 0;
439 }
440 return ext2fs_mark_generic_bitmap(bitmap, arg);
441 }
442
443 if (!EXT2FS_IS_64_BITMAP(bitmap))
444 return 0;
445
446 arg >>= bitmap->cluster_bits;
447
448 #ifdef ENABLE_BMAP_STATS_OPS
449 if (arg == bitmap->stats.last_marked + 1)
450 bitmap->stats.mark_seq++;
451 if (arg < bitmap->stats.last_marked)
452 bitmap->stats.mark_back++;
453 bitmap->stats.last_marked = arg;
454 bitmap->stats.mark_count++;
455 #endif
456
457 if ((arg < bitmap->start) || (arg > bitmap->end)) {
458 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
459 return 0;
460 }
461
462 return bitmap->bitmap_ops->mark_bmap(bitmap, arg);
463 }
464
ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap,__u64 arg)465 int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap,
466 __u64 arg)
467 {
468 if (!bitmap)
469 return 0;
470
471 if (EXT2FS_IS_32_BITMAP(bitmap)) {
472 if (arg & ~0xffffffffULL) {
473 ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR,
474 0xffffffff);
475 return 0;
476 }
477 return ext2fs_unmark_generic_bitmap(bitmap, arg);
478 }
479
480 if (!EXT2FS_IS_64_BITMAP(bitmap))
481 return 0;
482
483 arg >>= bitmap->cluster_bits;
484
485 INC_STAT(bitmap, unmark_count);
486
487 if ((arg < bitmap->start) || (arg > bitmap->end)) {
488 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
489 return 0;
490 }
491
492 return bitmap->bitmap_ops->unmark_bmap(bitmap, arg);
493 }
494
ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap,__u64 arg)495 int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap,
496 __u64 arg)
497 {
498 if (!bitmap)
499 return 0;
500
501 if (EXT2FS_IS_32_BITMAP(bitmap)) {
502 if (arg & ~0xffffffffULL) {
503 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR,
504 0xffffffff);
505 return 0;
506 }
507 return ext2fs_test_generic_bitmap(bitmap, arg);
508 }
509
510 if (!EXT2FS_IS_64_BITMAP(bitmap))
511 return 0;
512
513 arg >>= bitmap->cluster_bits;
514
515 #ifdef ENABLE_BMAP_STATS_OPS
516 bitmap->stats.test_count++;
517 if (arg == bitmap->stats.last_tested + 1)
518 bitmap->stats.test_seq++;
519 if (arg < bitmap->stats.last_tested)
520 bitmap->stats.test_back++;
521 bitmap->stats.last_tested = arg;
522 #endif
523
524 if ((arg < bitmap->start) || (arg > bitmap->end)) {
525 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
526 return 0;
527 }
528
529 return bitmap->bitmap_ops->test_bmap(bitmap, arg);
530 }
531
ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap,__u64 start,unsigned int num,void * in)532 errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap,
533 __u64 start, unsigned int num,
534 void *in)
535 {
536 if (!bmap)
537 return EINVAL;
538
539 if (EXT2FS_IS_32_BITMAP(bmap)) {
540 if ((start+num-1) & ~0xffffffffULL) {
541 ext2fs_warn_bitmap2(bmap, EXT2FS_UNMARK_ERROR,
542 0xffffffff);
543 return EINVAL;
544 }
545 return ext2fs_set_generic_bitmap_range(bmap, bmap->magic,
546 start, num, in);
547 }
548
549 if (!EXT2FS_IS_64_BITMAP(bmap))
550 return EINVAL;
551
552 INC_STAT(bmap, set_range_count);
553
554 return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
555 }
556
ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap,__u64 start,unsigned int num,void * out)557 errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap,
558 __u64 start, unsigned int num,
559 void *out)
560 {
561 if (!bmap)
562 return EINVAL;
563
564 if (EXT2FS_IS_32_BITMAP(bmap)) {
565 if ((start+num-1) & ~0xffffffffULL) {
566 ext2fs_warn_bitmap2(bmap,
567 EXT2FS_UNMARK_ERROR, 0xffffffff);
568 return EINVAL;
569 }
570 return ext2fs_get_generic_bitmap_range(bmap, bmap->magic,
571 start, num, out);
572 }
573
574 if (!EXT2FS_IS_64_BITMAP(bmap))
575 return EINVAL;
576
577 INC_STAT(bmap, get_range_count);
578
579 return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
580 }
581
ext2fs_compare_generic_bmap(errcode_t neq,ext2fs_generic_bitmap bm1,ext2fs_generic_bitmap bm2)582 errcode_t ext2fs_compare_generic_bmap(errcode_t neq,
583 ext2fs_generic_bitmap bm1,
584 ext2fs_generic_bitmap bm2)
585 {
586 blk64_t i;
587
588 if (!bm1 || !bm2)
589 return EINVAL;
590 if (bm1->magic != bm2->magic)
591 return EINVAL;
592
593 /* Now we know both bitmaps have the same magic */
594 if (EXT2FS_IS_32_BITMAP(bm1))
595 return ext2fs_compare_generic_bitmap(bm1->magic, neq, bm1, bm2);
596
597 if (!EXT2FS_IS_64_BITMAP(bm1))
598 return EINVAL;
599
600 if ((bm1->start != bm2->start) ||
601 (bm1->end != bm2->end))
602 return neq;
603
604 for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
605 if (ext2fs_test_generic_bmap(bm1, i) !=
606 ext2fs_test_generic_bmap(bm2, i))
607 return neq;
608
609 return 0;
610 }
611
ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap bmap)612 void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap bmap)
613 {
614 __u64 start, num;
615
616 if (EXT2FS_IS_32_BITMAP(bmap)) {
617 ext2fs_set_generic_bitmap_padding(bmap);
618 return;
619 }
620
621 start = bmap->end + 1;
622 num = bmap->real_end - bmap->end;
623 bmap->bitmap_ops->mark_bmap_extent(bmap, start, num);
624 /* XXX ought to warn on error */
625 }
626
ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap,blk64_t block,unsigned int num)627 int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap,
628 blk64_t block, unsigned int num)
629 {
630 __u64 end = block + num;
631
632 if (!bmap)
633 return EINVAL;
634
635 if (num == 1)
636 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap)
637 bmap, block);
638
639 if (EXT2FS_IS_32_BITMAP(bmap)) {
640 if ((block+num-1) & ~0xffffffffULL) {
641 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
642 EXT2FS_UNMARK_ERROR, 0xffffffff);
643 return EINVAL;
644 }
645 return ext2fs_test_block_bitmap_range(
646 (ext2fs_generic_bitmap) bmap, block, num);
647 }
648
649 if (!EXT2FS_IS_64_BITMAP(bmap))
650 return EINVAL;
651
652 INC_STAT(bmap, test_ext_count);
653
654 /* convert to clusters if necessary */
655 block >>= bmap->cluster_bits;
656 end += (1 << bmap->cluster_bits) - 1;
657 end >>= bmap->cluster_bits;
658 num = end - block;
659
660 if ((block < bmap->start) || (block+num-1 > bmap->end)) {
661 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, block,
662 bmap->description);
663 return EINVAL;
664 }
665
666 return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
667 }
668
ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap,blk64_t block,unsigned int num)669 void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap,
670 blk64_t block, unsigned int num)
671 {
672 __u64 end = block + num;
673
674 if (!bmap)
675 return;
676
677 if (EXT2FS_IS_32_BITMAP(bmap)) {
678 if ((block+num-1) & ~0xffffffffULL) {
679 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
680 EXT2FS_UNMARK_ERROR, 0xffffffff);
681 return;
682 }
683 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
684 block, num);
685 }
686
687 if (!EXT2FS_IS_64_BITMAP(bmap))
688 return;
689
690 INC_STAT(bmap, mark_ext_count);
691
692 /* convert to clusters if necessary */
693 block >>= bmap->cluster_bits;
694 end += (1 << bmap->cluster_bits) - 1;
695 end >>= bmap->cluster_bits;
696 num = end - block;
697
698 if ((block < bmap->start) || (block+num-1 > bmap->end)) {
699 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
700 bmap->description);
701 return;
702 }
703
704 bmap->bitmap_ops->mark_bmap_extent(bmap, block, num);
705 }
706
ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap,blk64_t block,unsigned int num)707 void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap,
708 blk64_t block, unsigned int num)
709 {
710 __u64 end = block + num;
711
712 if (!bmap)
713 return;
714
715 if (EXT2FS_IS_32_BITMAP(bmap)) {
716 if ((block+num-1) & ~0xffffffffULL) {
717 ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
718 EXT2FS_UNMARK_ERROR, 0xffffffff);
719 return;
720 }
721 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
722 block, num);
723 }
724
725 if (!EXT2FS_IS_64_BITMAP(bmap))
726 return;
727
728 INC_STAT(bmap, unmark_ext_count);
729
730 /* convert to clusters if necessary */
731 block >>= bmap->cluster_bits;
732 end += (1 << bmap->cluster_bits) - 1;
733 end >>= bmap->cluster_bits;
734 num = end - block;
735
736 if ((block < bmap->start) || (block+num-1 > bmap->end)) {
737 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
738 bmap->description);
739 return;
740 }
741
742 bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num);
743 }
744
ext2fs_warn_bitmap32(ext2fs_generic_bitmap bitmap,const char * func)745 void ext2fs_warn_bitmap32(ext2fs_generic_bitmap bitmap, const char *func)
746 {
747 #ifndef OMIT_COM_ERR
748 if (bitmap && bitmap->description)
749 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
750 "called %s with 64-bit bitmap for %s", func,
751 bitmap->description);
752 else
753 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
754 "called %s with 64-bit bitmap", func);
755 #endif
756 }
757
ext2fs_convert_subcluster_bitmap(ext2_filsys fs,ext2fs_block_bitmap * bitmap)758 errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
759 ext2fs_block_bitmap *bitmap)
760 {
761 ext2fs_block_bitmap cmap, bmap;
762 errcode_t retval;
763 blk64_t i, b_end, c_end;
764 int n, ratio;
765
766 bmap = *bitmap;
767
768 if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(bmap))
769 return 0; /* Nothing to do */
770
771 retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap",
772 &cmap);
773 if (retval)
774 return retval;
775
776 i = bmap->start;
777 b_end = bmap->end;
778 bmap->end = bmap->real_end;
779 c_end = cmap->end;
780 cmap->end = cmap->real_end;
781 n = 0;
782 ratio = 1 << fs->cluster_ratio_bits;
783 while (i < bmap->real_end) {
784 if (ext2fs_test_block_bitmap2(bmap, i)) {
785 ext2fs_mark_block_bitmap2(cmap, i);
786 i += ratio - n;
787 n = 0;
788 continue;
789 }
790 i++; n++;
791 if (n >= ratio)
792 n = 0;
793 }
794 bmap->end = b_end;
795 cmap->end = c_end;
796 ext2fs_free_block_bitmap(bmap);
797 *bitmap = cmap;
798 return 0;
799 }
800
ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,__u64 start,__u64 end,__u64 * out)801 errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
802 __u64 start, __u64 end, __u64 *out)
803 {
804 __u64 cstart, cend, cout;
805 errcode_t retval;
806
807 if (!bitmap)
808 return EINVAL;
809
810 if (EXT2FS_IS_32_BITMAP(bitmap)) {
811 blk_t blk = 0;
812
813 if (((start) & ~0xffffffffULL) ||
814 ((end) & ~0xffffffffULL)) {
815 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
816 return EINVAL;
817 }
818
819 retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start,
820 end, &blk);
821 if (retval == 0)
822 *out = blk;
823 return retval;
824 }
825
826 if (!EXT2FS_IS_64_BITMAP(bitmap))
827 return EINVAL;
828
829 cstart = start >> bitmap->cluster_bits;
830 cend = end >> bitmap->cluster_bits;
831
832 if (cstart < bitmap->start || cend > bitmap->end || start > end) {
833 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, start);
834 return EINVAL;
835 }
836
837 if (bitmap->bitmap_ops->find_first_zero) {
838 retval = bitmap->bitmap_ops->find_first_zero(bitmap, cstart,
839 cend, &cout);
840 if (retval)
841 return retval;
842 found:
843 cout <<= bitmap->cluster_bits;
844 *out = (cout >= start) ? cout : start;
845 return 0;
846 }
847
848 for (cout = cstart; cout <= cend; cout++)
849 if (!bitmap->bitmap_ops->test_bmap(bitmap, cout))
850 goto found;
851
852 return ENOENT;
853 }
854
ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,__u64 start,__u64 end,__u64 * out)855 errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,
856 __u64 start, __u64 end, __u64 *out)
857 {
858 __u64 cstart, cend, cout;
859 errcode_t retval;
860
861 if (!bitmap)
862 return EINVAL;
863
864 if (EXT2FS_IS_32_BITMAP(bitmap)) {
865 blk_t blk = 0;
866
867 if (((start) & ~0xffffffffULL) ||
868 ((end) & ~0xffffffffULL)) {
869 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
870 return EINVAL;
871 }
872
873 retval = ext2fs_find_first_set_generic_bitmap(bitmap, start,
874 end, &blk);
875 if (retval == 0)
876 *out = blk;
877 return retval;
878 }
879
880 if (!EXT2FS_IS_64_BITMAP(bitmap))
881 return EINVAL;
882
883 cstart = start >> bitmap->cluster_bits;
884 cend = end >> bitmap->cluster_bits;
885
886 if (cstart < bitmap->start || cend > bitmap->end || start > end) {
887 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, start);
888 return EINVAL;
889 }
890
891 if (bitmap->bitmap_ops->find_first_set) {
892 retval = bitmap->bitmap_ops->find_first_set(bitmap, cstart,
893 cend, &cout);
894 if (retval)
895 return retval;
896 found:
897 cout <<= bitmap->cluster_bits;
898 *out = (cout >= start) ? cout : start;
899 return 0;
900 }
901
902 for (cout = cstart; cout <= cend; cout++)
903 if (bitmap->bitmap_ops->test_bmap(bitmap, cout))
904 goto found;
905
906 return ENOENT;
907 }
908