2 * rw_bitmaps.c --- routines to read and write the inode and block bitmaps.
4 * Copyright (C) 1993, 1994, 1994, 1996 Theodore Ts'o.
7 * This file may be redistributed under the terms of the GNU Library
8 * General Public License, version 2.
20 #ifdef HAVE_SYS_STAT_H
23 #ifdef HAVE_SYS_TYPES_H
24 #include <sys/types.h>
35 typedef pthread_mutex_t mutex_t;
37 static void unix_pthread_mutex_lock(mutex_t *mutex)
40 pthread_mutex_lock(mutex);
42 static void unix_pthread_mutex_unlock(mutex_t *mutex)
45 pthread_mutex_unlock(mutex);
49 #define unix_pthread_mutex_lock(mutex_t) do {} while (0)
50 #define unix_pthread_mutex_unlock(mutex_t) do {} while (0)
53 static errcode_t write_bitmaps(ext2_filsys fs, int do_inode, int do_block)
57 int block_nbytes, inode_nbytes;
60 char *block_buf = NULL, *inode_buf = NULL;
63 blk64_t blk_itr = EXT2FS_B2C(fs, fs->super->s_first_data_block);
64 ext2_ino_t ino_itr = 1;
66 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
68 if (!(fs->flags & EXT2_FLAG_RW))
69 return EXT2_ET_RO_FILSYS;
71 csum_flag = ext2fs_has_group_desc_csum(fs);
73 inode_nbytes = block_nbytes = 0;
75 block_nbytes = EXT2_CLUSTERS_PER_GROUP(fs->super) / 8;
76 retval = io_channel_alloc_buf(fs->io, 0, &block_buf);
79 memset(block_buf, 0xff, fs->blocksize);
82 inode_nbytes = (size_t)
83 ((EXT2_INODES_PER_GROUP(fs->super)+7) / 8);
84 retval = io_channel_alloc_buf(fs->io, 0, &inode_buf);
87 memset(inode_buf, 0xff, fs->blocksize);
90 for (i = 0; i < fs->group_desc_count; i++) {
92 goto skip_block_bitmap;
94 if (csum_flag && ext2fs_bg_flags_test(fs, i, EXT2_BG_BLOCK_UNINIT)
96 goto skip_this_block_bitmap;
98 retval = ext2fs_get_block_bitmap_range2(fs->block_map,
99 blk_itr, block_nbytes << 3, block_buf);
103 if (i == fs->group_desc_count - 1) {
104 /* Force bitmap padding for the last group */
105 nbits = EXT2FS_NUM_B2C(fs,
106 ((ext2fs_blocks_count(fs->super)
107 - (__u64) fs->super->s_first_data_block)
108 % (__u64) EXT2_BLOCKS_PER_GROUP(fs->super)));
110 for (j = nbits; j < fs->blocksize * 8; j++)
111 ext2fs_set_bit(j, block_buf);
114 retval = ext2fs_block_bitmap_csum_set(fs, i, block_buf,
118 ext2fs_group_desc_csum_set(fs, i);
119 fs->flags |= EXT2_FLAG_DIRTY;
121 blk = ext2fs_block_bitmap_loc(fs, i);
123 retval = io_channel_write_blk64(fs->io, blk, 1,
126 retval = EXT2_ET_BLOCK_BITMAP_WRITE;
130 skip_this_block_bitmap:
131 blk_itr += block_nbytes << 3;
137 if (csum_flag && ext2fs_bg_flags_test(fs, i, EXT2_BG_INODE_UNINIT)
139 goto skip_this_inode_bitmap;
141 retval = ext2fs_get_inode_bitmap_range2(fs->inode_map,
142 ino_itr, inode_nbytes << 3, inode_buf);
146 retval = ext2fs_inode_bitmap_csum_set(fs, i, inode_buf,
150 ext2fs_group_desc_csum_set(fs, i);
151 fs->flags |= EXT2_FLAG_DIRTY;
153 blk = ext2fs_inode_bitmap_loc(fs, i);
155 retval = io_channel_write_blk64(fs->io, blk, 1,
158 retval = EXT2_ET_INODE_BITMAP_WRITE;
162 skip_this_inode_bitmap:
163 ino_itr += inode_nbytes << 3;
167 fs->flags &= ~EXT2_FLAG_BB_DIRTY;
168 ext2fs_free_mem(&block_buf);
171 fs->flags &= ~EXT2_FLAG_IB_DIRTY;
172 ext2fs_free_mem(&inode_buf);
177 ext2fs_free_mem(&inode_buf);
179 ext2fs_free_mem(&block_buf);
183 static errcode_t mark_uninit_bg_group_blocks(ext2_filsys fs)
187 ext2fs_block_bitmap bmap = fs->block_map;
189 for (i = 0; i < fs->group_desc_count; i++) {
190 if (!ext2fs_bg_flags_test(fs, i, EXT2_BG_BLOCK_UNINIT))
193 ext2fs_reserve_super_and_bgd(fs, i, bmap);
196 * Mark the blocks used for the inode table
198 blk = ext2fs_inode_table_loc(fs, i);
200 ext2fs_mark_block_bitmap_range2(bmap, blk,
201 fs->inode_blocks_per_group);
204 * Mark block used for the block bitmap
206 blk = ext2fs_block_bitmap_loc(fs, i);
208 ext2fs_mark_block_bitmap2(bmap, blk);
211 * Mark block used for the inode bitmap
213 blk = ext2fs_inode_bitmap_loc(fs, i);
215 ext2fs_mark_block_bitmap2(bmap, blk);
220 static int bitmap_tail_verify(unsigned char *bitmap, int first, int last)
224 for (i = first; i <= last; i++)
225 if (bitmap[i] != 0xff)
230 static errcode_t read_bitmaps_range_prepare(ext2_filsys fs, int flags)
233 int block_nbytes = EXT2_CLUSTERS_PER_GROUP(fs->super) / 8;
234 int inode_nbytes = EXT2_INODES_PER_GROUP(fs->super) / 8;
237 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
239 if ((block_nbytes > (int) fs->blocksize) ||
240 (inode_nbytes > (int) fs->blocksize))
241 return EXT2_ET_CORRUPT_SUPERBLOCK;
243 fs->write_bitmaps = ext2fs_write_bitmaps;
245 retval = ext2fs_get_mem(strlen(fs->device_name) + 80, &buf);
249 if (flags & EXT2FS_BITMAPS_BLOCK) {
251 ext2fs_free_block_bitmap(fs->block_map);
252 strcpy(buf, "block bitmap for ");
253 strcat(buf, fs->device_name);
254 retval = ext2fs_allocate_block_bitmap(fs, buf, &fs->block_map);
259 if (flags & EXT2FS_BITMAPS_INODE) {
261 ext2fs_free_inode_bitmap(fs->inode_map);
262 strcpy(buf, "inode bitmap for ");
263 strcat(buf, fs->device_name);
264 retval = ext2fs_allocate_inode_bitmap(fs, buf, &fs->inode_map);
268 ext2fs_free_mem(&buf);
272 if (flags & EXT2FS_BITMAPS_BLOCK) {
273 ext2fs_free_block_bitmap(fs->block_map);
276 if (flags & EXT2FS_BITMAPS_INODE) {
277 ext2fs_free_inode_bitmap(fs->inode_map);
280 ext2fs_free_mem(&buf);
284 static errcode_t read_bitmaps_range_start(ext2_filsys fs, int flags,
285 dgrp_t start, dgrp_t end,
290 char *block_bitmap = 0, *inode_bitmap = 0;
291 errcode_t retval = 0;
292 int block_nbytes = EXT2_CLUSTERS_PER_GROUP(fs->super) / 8;
293 int inode_nbytes = EXT2_INODES_PER_GROUP(fs->super) / 8;
297 blk64_t blk_itr = EXT2FS_B2C(fs, fs->super->s_first_data_block);
299 ext2_ino_t ino_itr = 1;
302 csum_flag = ext2fs_has_group_desc_csum(fs);
304 if (flags & EXT2FS_BITMAPS_BLOCK) {
305 retval = io_channel_alloc_buf(fs->io, 0, &block_bitmap);
312 if (flags & EXT2FS_BITMAPS_INODE) {
313 retval = io_channel_alloc_buf(fs->io, 0, &inode_bitmap);
320 /* io should be null */
321 if (fs->flags & EXT2_FLAG_IMAGE_FILE) {
322 blk = (ext2fs_le32_to_cpu(fs->image_header->offset_inodemap) / fs->blocksize);
323 ino_cnt = fs->super->s_inodes_count;
324 while (inode_bitmap && ino_cnt > 0) {
325 retval = io_channel_read_blk64(fs->image_io, blk++,
329 cnt = fs->blocksize << 3;
332 retval = ext2fs_set_inode_bitmap_range2(fs->inode_map,
333 ino_itr, cnt, inode_bitmap);
339 blk = (ext2fs_le32_to_cpu(fs->image_header->offset_blockmap) /
341 blk_cnt = EXT2_GROUPS_TO_CLUSTERS(fs->super,
342 fs->group_desc_count);
343 while (block_bitmap && blk_cnt > 0) {
344 retval = io_channel_read_blk64(fs->image_io, blk++,
348 cnt = fs->blocksize << 3;
351 retval = ext2fs_set_block_bitmap_range2(fs->block_map,
352 blk_itr, cnt, block_bitmap);
361 blk_itr += ((blk64_t)start * (block_nbytes << 3));
362 ino_itr += ((blk64_t)start * (inode_nbytes << 3));
363 for (i = start; i <= end; i++) {
365 blk = ext2fs_block_bitmap_loc(fs, i);
367 ext2fs_bg_flags_test(fs, i, EXT2_BG_BLOCK_UNINIT) &&
368 ext2fs_group_desc_csum_verify(fs, i)) ||
369 (blk >= ext2fs_blocks_count(fs->super)))
372 retval = io_channel_read_blk64(fs->io, blk,
375 retval = EXT2_ET_BLOCK_BITMAP_READ;
378 /* verify block bitmap checksum */
380 EXT2_FLAG_IGNORE_CSUM_ERRORS) &&
381 !ext2fs_block_bitmap_csum_verify(fs, i,
382 block_bitmap, block_nbytes)) {
384 EXT2_ET_BLOCK_BITMAP_CSUM_INVALID;
387 if (!bitmap_tail_verify((unsigned char *) block_bitmap,
388 block_nbytes, fs->blocksize - 1))
389 *tail_flags |= EXT2_FLAG_BBITMAP_TAIL_PROBLEM;
391 memset(block_bitmap, 0, block_nbytes);
392 cnt = block_nbytes << 3;
393 unix_pthread_mutex_lock(mutex);
394 retval = ext2fs_set_block_bitmap_range2(fs->block_map,
395 blk_itr, cnt, block_bitmap);
396 unix_pthread_mutex_unlock(mutex);
399 blk_itr += block_nbytes << 3;
402 blk = ext2fs_inode_bitmap_loc(fs, i);
404 ext2fs_bg_flags_test(fs, i, EXT2_BG_INODE_UNINIT) &&
405 ext2fs_group_desc_csum_verify(fs, i)) ||
406 (blk >= ext2fs_blocks_count(fs->super)))
409 retval = io_channel_read_blk64(fs->io, blk,
412 retval = EXT2_ET_INODE_BITMAP_READ;
416 /* verify inode bitmap checksum */
418 EXT2_FLAG_IGNORE_CSUM_ERRORS) &&
419 !ext2fs_inode_bitmap_csum_verify(fs, i,
420 inode_bitmap, inode_nbytes)) {
422 EXT2_ET_INODE_BITMAP_CSUM_INVALID;
425 if (!bitmap_tail_verify((unsigned char *) inode_bitmap,
426 inode_nbytes, fs->blocksize - 1))
427 *tail_flags |= EXT2_FLAG_IBITMAP_TAIL_PROBLEM;
429 memset(inode_bitmap, 0, inode_nbytes);
430 cnt = inode_nbytes << 3;
431 unix_pthread_mutex_lock(mutex);
432 retval = ext2fs_set_inode_bitmap_range2(fs->inode_map,
433 ino_itr, cnt, inode_bitmap);
434 unix_pthread_mutex_unlock(mutex);
437 ino_itr += inode_nbytes << 3;
443 ext2fs_free_mem(&inode_bitmap);
445 ext2fs_free_mem(&block_bitmap);
449 static errcode_t read_bitmaps_range_end(ext2_filsys fs, int flags,
454 /* Mark group blocks for any BLOCK_UNINIT groups */
455 if (flags & EXT2FS_BITMAPS_BLOCK) {
456 retval = mark_uninit_bg_group_blocks(fs);
459 fs->flags &= ~EXT2_FLAG_BBITMAP_TAIL_PROBLEM;
461 if (flags & EXT2FS_BITMAPS_INODE)
462 fs->flags &= ~EXT2_FLAG_IBITMAP_TAIL_PROBLEM;
463 fs->flags |= tail_flags;
468 static void read_bitmaps_cleanup_on_error(ext2_filsys fs, int flags)
470 if (flags & EXT2FS_BITMAPS_BLOCK) {
471 ext2fs_free_block_bitmap(fs->block_map);
474 if (flags & EXT2FS_BITMAPS_INODE) {
475 ext2fs_free_inode_bitmap(fs->inode_map);
480 static errcode_t read_bitmaps_range(ext2_filsys fs, int flags,
481 dgrp_t start, dgrp_t end)
486 retval = read_bitmaps_range_prepare(fs, flags);
490 retval = read_bitmaps_range_start(fs, flags, start, end,
493 retval = read_bitmaps_range_end(fs, flags, tail_flags);
495 read_bitmaps_cleanup_on_error(fs, flags);
500 struct read_bitmaps_thread_info {
503 dgrp_t rbt_grp_start;
505 errcode_t rbt_retval;
506 pthread_mutex_t *rbt_mutex;
510 static void *read_bitmaps_thread(void *data)
512 struct read_bitmaps_thread_info *rbt = data;
514 rbt->rbt_retval = read_bitmaps_range_start(rbt->rbt_fs, rbt->rbt_flags,
515 rbt->rbt_grp_start, rbt->rbt_grp_end,
516 rbt->rbt_mutex, &rbt->rbt_tail_flags);
521 errcode_t ext2fs_rw_bitmaps(ext2_filsys fs, int flags, int num_threads)
525 pthread_t *thread_ids = NULL;
526 struct read_bitmaps_thread_info *thread_infos = NULL;
527 pthread_mutex_t rbt_mutex = PTHREAD_MUTEX_INITIALIZER;
530 unsigned flexbg_size = 1 << fs->super->s_log_groups_per_flex;
531 dgrp_t average_group;
532 int i, tail_flags = 0;
535 if (flags & ~EXT2FS_BITMAPS_VALID_FLAGS)
536 return EXT2_ET_INVALID_ARGUMENT;
538 if (flags & EXT2FS_BITMAPS_WRITE)
539 return write_bitmaps(fs, flags & EXT2FS_BITMAPS_INODE,
540 flags & EXT2FS_BITMAPS_BLOCK);
543 if (((fs->io->flags & CHANNEL_FLAGS_THREADS) == 0) ||
544 (num_threads == 1) || (fs->flags & EXT2_FLAG_IMAGE_FILE))
547 #if defined(HAVE_SYSCONF) && defined(_SC_NPROCESSORS_CONF)
549 num_threads = sysconf(_SC_NPROCESSORS_CONF);
552 * Guess for now; eventually we should probably define
553 * ext2fs_get_num_cpus() and teach it how to get this info on
554 * MacOS, FreeBSD, etc.
555 * ref: https://stackoverflow.com/questions/150355
560 if ((unsigned) num_threads > fs->group_desc_count)
561 num_threads = fs->group_desc_count;
562 average_group = fs->group_desc_count / num_threads;
563 if (ext2fs_has_feature_flex_bg(fs->super)) {
564 average_group = (average_group / flexbg_size) * flexbg_size;
566 if ((num_threads <= 1) || (average_group == 0))
569 io_channel_set_options(fs->io, "cache=off");
570 retval = pthread_attr_init(&attr);
574 thread_ids = calloc(sizeof(pthread_t), num_threads);
578 thread_infos = calloc(sizeof(struct read_bitmaps_thread_info),
583 retval = read_bitmaps_range_prepare(fs, flags);
587 // fprintf(stdout, "Multiple threads triggered to read bitmaps\n");
588 for (i = 0; i < num_threads; i++) {
589 thread_infos[i].rbt_fs = fs;
590 thread_infos[i].rbt_flags = flags;
591 thread_infos[i].rbt_mutex = &rbt_mutex;
592 thread_infos[i].rbt_tail_flags = 0;
594 thread_infos[i].rbt_grp_start = 0;
596 thread_infos[i].rbt_grp_start = average_group * i + 1;
598 if (i == num_threads - 1)
599 thread_infos[i].rbt_grp_end = fs->group_desc_count - 1;
601 thread_infos[i].rbt_grp_end = average_group * (i + 1);
602 retval = pthread_create(&thread_ids[i], &attr,
603 &read_bitmaps_thread, &thread_infos[i]);
607 for (i = 0; i < num_threads; i++) {
610 rc = pthread_join(thread_ids[i], NULL);
613 rc = thread_infos[i].rbt_retval;
616 tail_flags |= thread_infos[i].rbt_tail_flags;
619 rc = pthread_attr_destroy(&attr);
626 retval = read_bitmaps_range_end(fs, flags, tail_flags);
628 read_bitmaps_cleanup_on_error(fs, flags);
629 /* XXX should save and restore cache setting */
630 io_channel_set_options(fs->io, "cache=on");
633 #endif /* HAVE_PTHREAD */
634 return read_bitmaps_range(fs, flags, 0, fs->group_desc_count - 1);
637 errcode_t ext2fs_read_inode_bitmap(ext2_filsys fs)
639 return ext2fs_rw_bitmaps(fs, EXT2FS_BITMAPS_INODE, -1);
642 errcode_t ext2fs_read_block_bitmap(ext2_filsys fs)
644 return ext2fs_rw_bitmaps(fs, EXT2FS_BITMAPS_BLOCK, -1);
647 errcode_t ext2fs_write_inode_bitmap(ext2_filsys fs)
649 return write_bitmaps(fs, 1, 0);
652 errcode_t ext2fs_write_block_bitmap (ext2_filsys fs)
654 return write_bitmaps(fs, 0, 1);
657 errcode_t ext2fs_read_bitmaps(ext2_filsys fs)
662 flags |= EXT2FS_BITMAPS_INODE;
664 flags |= EXT2FS_BITMAPS_BLOCK;
667 return ext2fs_rw_bitmaps(fs, flags, -1);
670 errcode_t ext2fs_write_bitmaps(ext2_filsys fs)
672 int do_inode = fs->inode_map && ext2fs_test_ib_dirty(fs);
673 int do_block = fs->block_map && ext2fs_test_bb_dirty(fs);
675 if (!do_inode && !do_block)
678 return write_bitmaps(fs, do_inode, do_block);