Whamcloud - gitweb
e2fsck: merge bitmaps after thread completes
[tools/e2fsprogs.git] / lib / ext2fs / gen_bitmap64.c
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
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
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
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
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
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
349 errcode_t ext2fs_merge_generic_bmap(ext2fs_generic_bitmap gen_src,
350                                     ext2fs_generic_bitmap gen_dest,
351                                     ext2fs_generic_bitmap gen_dup,
352                                     ext2fs_generic_bitmap gen_dup_allowed)
353 {
354         ext2fs_generic_bitmap_64 src = (ext2fs_generic_bitmap_64)gen_src;
355         ext2fs_generic_bitmap_64 dest = (ext2fs_generic_bitmap_64)gen_dest;
356         ext2fs_generic_bitmap_64 dup = (ext2fs_generic_bitmap_64)gen_dup;
357         ext2fs_generic_bitmap_64 dup_allowed = (ext2fs_generic_bitmap_64)gen_dup_allowed;
358
359         if (!src || !dest)
360                 return EINVAL;
361
362         if (!EXT2FS_IS_64_BITMAP(src) || !EXT2FS_IS_64_BITMAP(dest) ||
363             (dup && !EXT2FS_IS_64_BITMAP(dup)) ||
364                 (dup_allowed && !EXT2FS_IS_64_BITMAP(dup_allowed)))
365                 return EINVAL;
366
367         if (src->bitmap_ops != dest->bitmap_ops ||
368             (dup && src->bitmap_ops != dup->bitmap_ops) ||
369             (dup_allowed && src->bitmap_ops != dup_allowed->bitmap_ops))
370                 return EINVAL;
371
372         if (src->bitmap_ops->merge_bmap == NULL)
373                 return EOPNOTSUPP;
374
375         return src->bitmap_ops->merge_bmap(src, dest, dup, dup_allowed);
376 }
377
378 errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap gen_bmap,
379                                      __u64 new_end,
380                                      __u64 new_real_end)
381 {
382         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
383
384         if (!bmap)
385                 return EINVAL;
386
387         if (EXT2FS_IS_32_BITMAP(bmap))
388                 return ext2fs_resize_generic_bitmap(gen_bmap->magic, new_end,
389                                                     new_real_end, gen_bmap);
390
391         if (!EXT2FS_IS_64_BITMAP(bmap))
392                 return EINVAL;
393
394         INC_STAT(bmap, resize_count);
395
396         return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
397 }
398
399 errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap,
400                                         errcode_t neq,
401                                         __u64 end, __u64 *oend)
402 {
403         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
404
405         if (!bitmap)
406                 return EINVAL;
407
408         if (EXT2FS_IS_32_BITMAP(bitmap)) {
409                 ext2_ino_t tmp_oend;
410                 int retval;
411
412                 retval = ext2fs_fudge_generic_bitmap_end(gen_bitmap,
413                                                          bitmap->magic,
414                                                          neq, end, &tmp_oend);
415                 if (oend)
416                         *oend = tmp_oend;
417                 return retval;
418         }
419
420         if (!EXT2FS_IS_64_BITMAP(bitmap))
421                 return EINVAL;
422
423         if (end > bitmap->real_end)
424                 return neq;
425         if (oend)
426                 *oend = bitmap->end;
427         bitmap->end = end;
428         return 0;
429 }
430
431 __u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap gen_bitmap)
432 {
433         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
434
435         if (!bitmap)
436                 return EINVAL;
437
438         if (EXT2FS_IS_32_BITMAP(bitmap))
439                 return ext2fs_get_generic_bitmap_start(gen_bitmap);
440
441         if (!EXT2FS_IS_64_BITMAP(bitmap))
442                 return EINVAL;
443
444         return bitmap->start;
445 }
446
447 __u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap)
448 {
449         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
450
451         if (!bitmap)
452                 return EINVAL;
453
454         if (EXT2FS_IS_32_BITMAP(bitmap))
455                 return ext2fs_get_generic_bitmap_end(gen_bitmap);
456
457         if (!EXT2FS_IS_64_BITMAP(bitmap))
458                 return EINVAL;
459
460         return bitmap->end;
461 }
462
463 void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap gen_bitmap)
464 {
465         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
466
467         if (EXT2FS_IS_32_BITMAP(bitmap))
468                 ext2fs_clear_generic_bitmap(gen_bitmap);
469         else
470                 bitmap->bitmap_ops->clear_bmap(bitmap);
471 }
472
473 int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
474                              __u64 arg)
475 {
476         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
477
478         if (!bitmap)
479                 return 0;
480
481         if (EXT2FS_IS_32_BITMAP(bitmap)) {
482                 if (arg & ~0xffffffffULL) {
483                         ext2fs_warn_bitmap2(gen_bitmap,
484                                             EXT2FS_MARK_ERROR, 0xffffffff);
485                         return 0;
486                 }
487                 return ext2fs_mark_generic_bitmap(gen_bitmap, arg);
488         }
489
490         if (!EXT2FS_IS_64_BITMAP(bitmap))
491                 return 0;
492
493         arg >>= bitmap->cluster_bits;
494
495 #ifdef ENABLE_BMAP_STATS_OPS
496         if (arg == bitmap->stats.last_marked + 1)
497                 bitmap->stats.mark_seq++;
498         if (arg < bitmap->stats.last_marked)
499                 bitmap->stats.mark_back++;
500         bitmap->stats.last_marked = arg;
501         bitmap->stats.mark_count++;
502 #endif
503
504         if ((arg < bitmap->start) || (arg > bitmap->end)) {
505                 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
506                 return 0;
507         }
508
509         return bitmap->bitmap_ops->mark_bmap(bitmap, arg);
510 }
511
512 int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
513                                __u64 arg)
514 {
515         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
516
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_UNMARK_ERROR,
523                                             0xffffffff);
524                         return 0;
525                 }
526                 return ext2fs_unmark_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         INC_STAT(bitmap, unmark_count);
535
536         if ((arg < bitmap->start) || (arg > bitmap->end)) {
537                 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
538                 return 0;
539         }
540
541         return bitmap->bitmap_ops->unmark_bmap(bitmap, arg);
542 }
543
544 int ext2fs_test_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
545                              __u64 arg)
546 {
547         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
548         if (!bitmap)
549                 return 0;
550
551         if (EXT2FS_IS_32_BITMAP(bitmap)) {
552                 if (arg & ~0xffffffffULL) {
553                         ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_TEST_ERROR,
554                                             0xffffffff);
555                         return 0;
556                 }
557                 return ext2fs_test_generic_bitmap(gen_bitmap, arg);
558         }
559
560         if (!EXT2FS_IS_64_BITMAP(bitmap))
561                 return 0;
562
563         arg >>= bitmap->cluster_bits;
564
565 #ifdef ENABLE_BMAP_STATS_OPS
566         bitmap->stats.test_count++;
567         if (arg == bitmap->stats.last_tested + 1)
568                 bitmap->stats.test_seq++;
569         if (arg < bitmap->stats.last_tested)
570                 bitmap->stats.test_back++;
571         bitmap->stats.last_tested = arg;
572 #endif
573
574         if ((arg < bitmap->start) || (arg > bitmap->end)) {
575                 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
576                 return 0;
577         }
578
579         return bitmap->bitmap_ops->test_bmap(bitmap, arg);
580 }
581
582 errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,
583                                         __u64 start, unsigned int num,
584                                         void *in)
585 {
586         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
587
588         if (!bmap)
589                 return EINVAL;
590
591         if (EXT2FS_IS_32_BITMAP(bmap)) {
592                 if ((start+num-1) & ~0xffffffffULL) {
593                         ext2fs_warn_bitmap2(gen_bmap, EXT2FS_UNMARK_ERROR,
594                                             0xffffffff);
595                         return EINVAL;
596                 }
597                 return ext2fs_set_generic_bitmap_range(gen_bmap, bmap->magic,
598                                                        start, num, in);
599         }
600
601         if (!EXT2FS_IS_64_BITMAP(bmap))
602                 return EINVAL;
603
604         INC_STAT(bmap, set_range_count);
605
606         return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
607 }
608
609 errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,
610                                         __u64 start, unsigned int num,
611                                         void *out)
612 {
613         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
614
615         if (!bmap)
616                 return EINVAL;
617
618         if (EXT2FS_IS_32_BITMAP(bmap)) {
619                 if ((start+num-1) & ~0xffffffffULL) {
620                         ext2fs_warn_bitmap2(gen_bmap,
621                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
622                         return EINVAL;
623                 }
624                 return ext2fs_get_generic_bitmap_range(gen_bmap, bmap->magic,
625                                                        start, num, out);
626         }
627
628         if (!EXT2FS_IS_64_BITMAP(bmap))
629                 return EINVAL;
630
631         INC_STAT(bmap, get_range_count);
632
633         return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
634 }
635
636 errcode_t ext2fs_compare_generic_bmap(errcode_t neq,
637                                       ext2fs_generic_bitmap gen_bm1,
638                                       ext2fs_generic_bitmap gen_bm2)
639 {
640         ext2fs_generic_bitmap_64 bm1 = (ext2fs_generic_bitmap_64) gen_bm1;
641         ext2fs_generic_bitmap_64 bm2 = (ext2fs_generic_bitmap_64) gen_bm2;
642         blk64_t i;
643
644         if (!bm1 || !bm2)
645                 return EINVAL;
646         if (bm1->magic != bm2->magic)
647                 return EINVAL;
648
649         /* Now we know both bitmaps have the same magic */
650         if (EXT2FS_IS_32_BITMAP(bm1))
651                 return ext2fs_compare_generic_bitmap(bm1->magic, neq,
652                                                      gen_bm1, gen_bm2);
653
654         if (!EXT2FS_IS_64_BITMAP(bm1))
655                 return EINVAL;
656
657         if ((bm1->start != bm2->start) ||
658             (bm1->end != bm2->end))
659                 return neq;
660
661         for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
662                 if (ext2fs_test_generic_bmap(gen_bm1, i) !=
663                     ext2fs_test_generic_bmap(gen_bm2, i))
664                         return neq;
665
666         return 0;
667 }
668
669 void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap gen_bmap)
670 {
671         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
672         __u64   start, num;
673
674         if (EXT2FS_IS_32_BITMAP(bmap)) {
675                 ext2fs_set_generic_bitmap_padding(gen_bmap);
676                 return;
677         }
678
679         start = bmap->end + 1;
680         num = bmap->real_end - bmap->end;
681         bmap->bitmap_ops->mark_bmap_extent(bmap, start, num);
682         /* XXX ought to warn on error */
683 }
684
685 int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
686                                     blk64_t block, unsigned int num)
687 {
688         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
689         __u64   end = block + num;
690
691         if (!bmap)
692                 return EINVAL;
693
694         if (num == 1)
695                 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap)
696                                                  bmap, block);
697
698         if (EXT2FS_IS_32_BITMAP(bmap)) {
699                 if ((block & ~0xffffffffULL) ||
700                     ((block+num-1) & ~0xffffffffULL)) {
701                         ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
702                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
703                         return EINVAL;
704                 }
705                 return ext2fs_test_block_bitmap_range(
706                         (ext2fs_generic_bitmap) bmap, block, num);
707         }
708
709         if (!EXT2FS_IS_64_BITMAP(bmap))
710                 return EINVAL;
711
712         INC_STAT(bmap, test_ext_count);
713
714         /* convert to clusters if necessary */
715         block >>= bmap->cluster_bits;
716         end += (1ULL << bmap->cluster_bits) - 1;
717         end >>= bmap->cluster_bits;
718         num = end - block;
719
720         if ((block < bmap->start) || (block > bmap->end) ||
721             (block+num-1 > bmap->end)) {
722                 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, block,
723                                    bmap->description);
724                 return EINVAL;
725         }
726
727         return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
728 }
729
730 void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
731                                      blk64_t block, unsigned int num)
732 {
733         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
734         __u64   end = block + num;
735
736         if (!bmap)
737                 return;
738
739         if (EXT2FS_IS_32_BITMAP(bmap)) {
740                 if ((block & ~0xffffffffULL) ||
741                     ((block+num-1) & ~0xffffffffULL)) {
742                         ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
743                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
744                         return;
745                 }
746                 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
747                                                block, num);
748         }
749
750         if (!EXT2FS_IS_64_BITMAP(bmap))
751                 return;
752
753         INC_STAT(bmap, mark_ext_count);
754
755         /* convert to clusters if necessary */
756         block >>= bmap->cluster_bits;
757         end += (1ULL << bmap->cluster_bits) - 1;
758         end >>= bmap->cluster_bits;
759         num = end - block;
760
761         if ((block < bmap->start) || (block > bmap->end) ||
762             (block+num-1 > bmap->end)) {
763                 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
764                                    bmap->description);
765                 return;
766         }
767
768         bmap->bitmap_ops->mark_bmap_extent(bmap, block, num);
769 }
770
771 void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
772                                        blk64_t block, unsigned int num)
773 {
774         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
775         __u64   end = block + num;
776
777         if (!bmap)
778                 return;
779
780         if (EXT2FS_IS_32_BITMAP(bmap)) {
781                 if ((block & ~0xffffffffULL) ||
782                     ((block+num-1) & ~0xffffffffULL)) {
783                         ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
784                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
785                         return;
786                 }
787                 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
788                                                  block, num);
789         }
790
791         if (!EXT2FS_IS_64_BITMAP(bmap))
792                 return;
793
794         INC_STAT(bmap, unmark_ext_count);
795
796         /* convert to clusters if necessary */
797         block >>= bmap->cluster_bits;
798         end += (1ULL << bmap->cluster_bits) - 1;
799         end >>= bmap->cluster_bits;
800         num = end - block;
801
802         if ((block < bmap->start) || (block > bmap->end) ||
803             (block+num-1 > bmap->end)) {
804                 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
805                                    bmap->description);
806                 return;
807         }
808
809         bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num);
810 }
811
812 void ext2fs_warn_bitmap32(ext2fs_generic_bitmap gen_bitmap, const char *func)
813 {
814         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
815
816 #ifndef OMIT_COM_ERR
817         if (bitmap && bitmap->description)
818                 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
819                         "called %s with 64-bit bitmap for %s", func,
820                         bitmap->description);
821         else
822                 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
823                         "called %s with 64-bit bitmap", func);
824 #endif
825 }
826
827 errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
828                                            ext2fs_block_bitmap *bitmap)
829 {
830         ext2fs_generic_bitmap_64 bmap, cmap;
831         ext2fs_block_bitmap     gen_bmap = *bitmap, gen_cmap;
832         errcode_t               retval;
833         blk64_t                 i, next, b_end, c_end;
834
835         bmap = (ext2fs_generic_bitmap_64) gen_bmap;
836         if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(gen_bmap))
837                 return 0;       /* Nothing to do */
838
839         retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap",
840                                               &gen_cmap);
841         if (retval)
842                 return retval;
843
844         cmap = (ext2fs_generic_bitmap_64) gen_cmap;
845         i = bmap->start;
846         b_end = bmap->end;
847         bmap->end = bmap->real_end;
848         c_end = cmap->end;
849         cmap->end = cmap->real_end;
850         while (i < bmap->real_end) {
851                 retval = ext2fs_find_first_set_block_bitmap2(gen_bmap,
852                                                 i, bmap->real_end, &next);
853                 if (retval)
854                         break;
855                 ext2fs_mark_block_bitmap2(gen_cmap, next);
856                 i = EXT2FS_C2B(fs, EXT2FS_B2C(fs, next) + 1);
857         }
858         bmap->end = b_end;
859         cmap->end = c_end;
860         ext2fs_free_block_bitmap(gen_bmap);
861         *bitmap = (ext2fs_block_bitmap) cmap;
862         return 0;
863 }
864
865 errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
866                                               __u64 start, __u64 end, __u64 *out)
867 {
868         ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap;
869         __u64 cstart, cend, cout;
870         errcode_t retval;
871
872         if (!bitmap)
873                 return EINVAL;
874
875         if (EXT2FS_IS_32_BITMAP(bitmap)) {
876                 blk_t blk = 0;
877
878                 if (((start) & ~0xffffffffULL) ||
879                     ((end) & ~0xffffffffULL)) {
880                         ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
881                         return EINVAL;
882                 }
883
884                 retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start,
885                                                                end, &blk);
886                 if (retval == 0)
887                         *out = blk;
888                 return retval;
889         }
890
891         if (!EXT2FS_IS_64_BITMAP(bitmap))
892                 return EINVAL;
893
894         cstart = start >> bmap64->cluster_bits;
895         cend = end >> bmap64->cluster_bits;
896
897         if (cstart < bmap64->start || cend > bmap64->end || start > end) {
898                 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start);
899                 return EINVAL;
900         }
901
902         if (bmap64->bitmap_ops->find_first_zero) {
903                 retval = bmap64->bitmap_ops->find_first_zero(bmap64, cstart,
904                                                              cend, &cout);
905                 if (retval)
906                         return retval;
907         found:
908                 cout <<= bmap64->cluster_bits;
909                 *out = (cout >= start) ? cout : start;
910                 return 0;
911         }
912
913         for (cout = cstart; cout <= cend; cout++)
914                 if (!bmap64->bitmap_ops->test_bmap(bmap64, cout))
915                         goto found;
916
917         return ENOENT;
918 }
919
920 errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,
921                                              __u64 start, __u64 end, __u64 *out)
922 {
923         ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap;
924         __u64 cstart, cend, cout;
925         errcode_t retval;
926
927         if (!bitmap)
928                 return EINVAL;
929
930         if (EXT2FS_IS_32_BITMAP(bitmap)) {
931                 blk_t blk = 0;
932
933                 if (((start) & ~0xffffffffULL) ||
934                     ((end) & ~0xffffffffULL)) {
935                         ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
936                         return EINVAL;
937                 }
938
939                 retval = ext2fs_find_first_set_generic_bitmap(bitmap, start,
940                                                               end, &blk);
941                 if (retval == 0)
942                         *out = blk;
943                 return retval;
944         }
945
946         if (!EXT2FS_IS_64_BITMAP(bitmap))
947                 return EINVAL;
948
949         cstart = start >> bmap64->cluster_bits;
950         cend = end >> bmap64->cluster_bits;
951
952         if (cstart < bmap64->start || cend > bmap64->end || start > end) {
953                 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start);
954                 return EINVAL;
955         }
956
957         if (bmap64->bitmap_ops->find_first_set) {
958                 retval = bmap64->bitmap_ops->find_first_set(bmap64, cstart,
959                                                             cend, &cout);
960                 if (retval)
961                         return retval;
962         found:
963                 cout <<= bmap64->cluster_bits;
964                 *out = (cout >= start) ? cout : start;
965                 return 0;
966         }
967
968         for (cout = cstart; cout <= cend; cout++)
969                 if (bmap64->bitmap_ops->test_bmap(bmap64, cout))
970                         goto found;
971
972         return ENOENT;
973 }
974
975 errcode_t ext2fs_count_used_clusters(ext2_filsys fs, blk64_t start,
976                                      blk64_t end, blk64_t *out)
977 {
978         blk64_t         next;
979         blk64_t         tot_set = 0;
980         errcode_t       retval = 0;
981
982         while (start < end) {
983                 retval = ext2fs_find_first_set_block_bitmap2(fs->block_map,
984                                                         start, end, &next);
985                 if (retval) {
986                         if (retval == ENOENT)
987                                 retval = 0;
988                         break;
989                 }
990                 start = next;
991
992                 retval = ext2fs_find_first_zero_block_bitmap2(fs->block_map,
993                                                         start, end, &next);
994                 if (retval == 0) {
995                         tot_set += next - start;
996                         start  = next + 1;
997                 } else if (retval == ENOENT) {
998                         retval = 0;
999                         tot_set += end - start + 1;
1000                         break;
1001                 } else
1002                         break;
1003         }
1004
1005         if (!retval)
1006                 *out = EXT2FS_NUM_B2C(fs, tot_set);
1007         return retval;
1008 }