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