1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0 26fd058f7STheodore Ts'o /* 36fd058f7STheodore Ts'o * linux/fs/ext4/block_validity.c 46fd058f7STheodore Ts'o * 56fd058f7STheodore Ts'o * Copyright (C) 2009 66fd058f7STheodore Ts'o * Theodore Ts'o (tytso@mit.edu) 76fd058f7STheodore Ts'o * 86fd058f7STheodore Ts'o * Track which blocks in the filesystem are metadata blocks that 96fd058f7STheodore Ts'o * should never be used as data blocks by files or directories. 106fd058f7STheodore Ts'o */ 116fd058f7STheodore Ts'o 126fd058f7STheodore Ts'o #include <linux/time.h> 136fd058f7STheodore Ts'o #include <linux/fs.h> 146fd058f7STheodore Ts'o #include <linux/namei.h> 156fd058f7STheodore Ts'o #include <linux/quotaops.h> 166fd058f7STheodore Ts'o #include <linux/buffer_head.h> 176fd058f7STheodore Ts'o #include <linux/swap.h> 186fd058f7STheodore Ts'o #include <linux/pagemap.h> 196fd058f7STheodore Ts'o #include <linux/blkdev.h> 205a0e3ad6STejun Heo #include <linux/slab.h> 216fd058f7STheodore Ts'o #include "ext4.h" 226fd058f7STheodore Ts'o 236fd058f7STheodore Ts'o struct ext4_system_zone { 246fd058f7STheodore Ts'o struct rb_node node; 256fd058f7STheodore Ts'o ext4_fsblk_t start_blk; 266fd058f7STheodore Ts'o unsigned int count; 276fd058f7STheodore Ts'o }; 286fd058f7STheodore Ts'o 296fd058f7STheodore Ts'o static struct kmem_cache *ext4_system_zone_cachep; 306fd058f7STheodore Ts'o 315dabfc78STheodore Ts'o int __init ext4_init_system_zone(void) 326fd058f7STheodore Ts'o { 3316828088STheodore Ts'o ext4_system_zone_cachep = KMEM_CACHE(ext4_system_zone, 0); 346fd058f7STheodore Ts'o if (ext4_system_zone_cachep == NULL) 356fd058f7STheodore Ts'o return -ENOMEM; 366fd058f7STheodore Ts'o return 0; 376fd058f7STheodore Ts'o } 386fd058f7STheodore Ts'o 395dabfc78STheodore Ts'o void ext4_exit_system_zone(void) 406fd058f7STheodore Ts'o { 416fd058f7STheodore Ts'o kmem_cache_destroy(ext4_system_zone_cachep); 426fd058f7STheodore Ts'o } 436fd058f7STheodore Ts'o 446fd058f7STheodore Ts'o static inline int can_merge(struct ext4_system_zone *entry1, 456fd058f7STheodore Ts'o struct ext4_system_zone *entry2) 466fd058f7STheodore Ts'o { 476fd058f7STheodore Ts'o if ((entry1->start_blk + entry1->count) == entry2->start_blk) 486fd058f7STheodore Ts'o return 1; 496fd058f7STheodore Ts'o return 0; 506fd058f7STheodore Ts'o } 516fd058f7STheodore Ts'o 526fd058f7STheodore Ts'o /* 536fd058f7STheodore Ts'o * Mark a range of blocks as belonging to the "system zone" --- that 546fd058f7STheodore Ts'o * is, filesystem metadata blocks which should never be used by 556fd058f7STheodore Ts'o * inodes. 566fd058f7STheodore Ts'o */ 576fd058f7STheodore Ts'o static int add_system_zone(struct ext4_sb_info *sbi, 586fd058f7STheodore Ts'o ext4_fsblk_t start_blk, 596fd058f7STheodore Ts'o unsigned int count) 606fd058f7STheodore Ts'o { 616fd058f7STheodore Ts'o struct ext4_system_zone *new_entry = NULL, *entry; 626fd058f7STheodore Ts'o struct rb_node **n = &sbi->system_blks.rb_node, *node; 636fd058f7STheodore Ts'o struct rb_node *parent = NULL, *new_node = NULL; 646fd058f7STheodore Ts'o 656fd058f7STheodore Ts'o while (*n) { 666fd058f7STheodore Ts'o parent = *n; 676fd058f7STheodore Ts'o entry = rb_entry(parent, struct ext4_system_zone, node); 686fd058f7STheodore Ts'o if (start_blk < entry->start_blk) 696fd058f7STheodore Ts'o n = &(*n)->rb_left; 706fd058f7STheodore Ts'o else if (start_blk >= (entry->start_blk + entry->count)) 716fd058f7STheodore Ts'o n = &(*n)->rb_right; 726fd058f7STheodore Ts'o else { 736fd058f7STheodore Ts'o if (start_blk + count > (entry->start_blk + 746fd058f7STheodore Ts'o entry->count)) 756fd058f7STheodore Ts'o entry->count = (start_blk + count - 766fd058f7STheodore Ts'o entry->start_blk); 776fd058f7STheodore Ts'o new_node = *n; 786fd058f7STheodore Ts'o new_entry = rb_entry(new_node, struct ext4_system_zone, 796fd058f7STheodore Ts'o node); 806fd058f7STheodore Ts'o break; 816fd058f7STheodore Ts'o } 826fd058f7STheodore Ts'o } 836fd058f7STheodore Ts'o 846fd058f7STheodore Ts'o if (!new_entry) { 856fd058f7STheodore Ts'o new_entry = kmem_cache_alloc(ext4_system_zone_cachep, 866fd058f7STheodore Ts'o GFP_KERNEL); 876fd058f7STheodore Ts'o if (!new_entry) 886fd058f7STheodore Ts'o return -ENOMEM; 896fd058f7STheodore Ts'o new_entry->start_blk = start_blk; 906fd058f7STheodore Ts'o new_entry->count = count; 916fd058f7STheodore Ts'o new_node = &new_entry->node; 926fd058f7STheodore Ts'o 936fd058f7STheodore Ts'o rb_link_node(new_node, parent, n); 946fd058f7STheodore Ts'o rb_insert_color(new_node, &sbi->system_blks); 956fd058f7STheodore Ts'o } 966fd058f7STheodore Ts'o 976fd058f7STheodore Ts'o /* Can we merge to the left? */ 986fd058f7STheodore Ts'o node = rb_prev(new_node); 996fd058f7STheodore Ts'o if (node) { 1006fd058f7STheodore Ts'o entry = rb_entry(node, struct ext4_system_zone, node); 1016fd058f7STheodore Ts'o if (can_merge(entry, new_entry)) { 1026fd058f7STheodore Ts'o new_entry->start_blk = entry->start_blk; 1036fd058f7STheodore Ts'o new_entry->count += entry->count; 1046fd058f7STheodore Ts'o rb_erase(node, &sbi->system_blks); 1056fd058f7STheodore Ts'o kmem_cache_free(ext4_system_zone_cachep, entry); 1066fd058f7STheodore Ts'o } 1076fd058f7STheodore Ts'o } 1086fd058f7STheodore Ts'o 1096fd058f7STheodore Ts'o /* Can we merge to the right? */ 1106fd058f7STheodore Ts'o node = rb_next(new_node); 1116fd058f7STheodore Ts'o if (node) { 1126fd058f7STheodore Ts'o entry = rb_entry(node, struct ext4_system_zone, node); 1136fd058f7STheodore Ts'o if (can_merge(new_entry, entry)) { 1146fd058f7STheodore Ts'o new_entry->count += entry->count; 1156fd058f7STheodore Ts'o rb_erase(node, &sbi->system_blks); 1166fd058f7STheodore Ts'o kmem_cache_free(ext4_system_zone_cachep, entry); 1176fd058f7STheodore Ts'o } 1186fd058f7STheodore Ts'o } 1196fd058f7STheodore Ts'o return 0; 1206fd058f7STheodore Ts'o } 1216fd058f7STheodore Ts'o 1226fd058f7STheodore Ts'o static void debug_print_tree(struct ext4_sb_info *sbi) 1236fd058f7STheodore Ts'o { 1246fd058f7STheodore Ts'o struct rb_node *node; 1256fd058f7STheodore Ts'o struct ext4_system_zone *entry; 1266fd058f7STheodore Ts'o int first = 1; 1276fd058f7STheodore Ts'o 1286fd058f7STheodore Ts'o printk(KERN_INFO "System zones: "); 1296fd058f7STheodore Ts'o node = rb_first(&sbi->system_blks); 1306fd058f7STheodore Ts'o while (node) { 1316fd058f7STheodore Ts'o entry = rb_entry(node, struct ext4_system_zone, node); 132d74f3d25SJoe Perches printk(KERN_CONT "%s%llu-%llu", first ? "" : ", ", 1336fd058f7STheodore Ts'o entry->start_blk, entry->start_blk + entry->count - 1); 1346fd058f7STheodore Ts'o first = 0; 1356fd058f7STheodore Ts'o node = rb_next(node); 1366fd058f7STheodore Ts'o } 137d74f3d25SJoe Perches printk(KERN_CONT "\n"); 1386fd058f7STheodore Ts'o } 1396fd058f7STheodore Ts'o 140345c0dbfSTheodore Ts'o static int ext4_protect_reserved_inode(struct super_block *sb, u32 ino) 141345c0dbfSTheodore Ts'o { 142345c0dbfSTheodore Ts'o struct inode *inode; 143345c0dbfSTheodore Ts'o struct ext4_sb_info *sbi = EXT4_SB(sb); 144345c0dbfSTheodore Ts'o struct ext4_map_blocks map; 145fbbbbd2fSColin Ian King u32 i = 0, num; 146fbbbbd2fSColin Ian King int err = 0, n; 147345c0dbfSTheodore Ts'o 148345c0dbfSTheodore Ts'o if ((ino < EXT4_ROOT_INO) || 149345c0dbfSTheodore Ts'o (ino > le32_to_cpu(sbi->s_es->s_inodes_count))) 150345c0dbfSTheodore Ts'o return -EINVAL; 151345c0dbfSTheodore Ts'o inode = ext4_iget(sb, ino, EXT4_IGET_SPECIAL); 152345c0dbfSTheodore Ts'o if (IS_ERR(inode)) 153345c0dbfSTheodore Ts'o return PTR_ERR(inode); 154345c0dbfSTheodore Ts'o num = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits; 155345c0dbfSTheodore Ts'o while (i < num) { 156345c0dbfSTheodore Ts'o map.m_lblk = i; 157345c0dbfSTheodore Ts'o map.m_len = num - i; 158345c0dbfSTheodore Ts'o n = ext4_map_blocks(NULL, inode, &map, 0); 159345c0dbfSTheodore Ts'o if (n < 0) { 160345c0dbfSTheodore Ts'o err = n; 161345c0dbfSTheodore Ts'o break; 162345c0dbfSTheodore Ts'o } 163345c0dbfSTheodore Ts'o if (n == 0) { 164345c0dbfSTheodore Ts'o i++; 165345c0dbfSTheodore Ts'o } else { 166345c0dbfSTheodore Ts'o if (!ext4_data_block_valid(sbi, map.m_pblk, n)) { 167345c0dbfSTheodore Ts'o ext4_error(sb, "blocks %llu-%llu from inode %u " 168345c0dbfSTheodore Ts'o "overlap system zone", map.m_pblk, 169345c0dbfSTheodore Ts'o map.m_pblk + map.m_len - 1, ino); 170345c0dbfSTheodore Ts'o err = -EFSCORRUPTED; 171345c0dbfSTheodore Ts'o break; 172345c0dbfSTheodore Ts'o } 173345c0dbfSTheodore Ts'o err = add_system_zone(sbi, map.m_pblk, n); 174345c0dbfSTheodore Ts'o if (err < 0) 175345c0dbfSTheodore Ts'o break; 176345c0dbfSTheodore Ts'o i += n; 177345c0dbfSTheodore Ts'o } 178345c0dbfSTheodore Ts'o } 179345c0dbfSTheodore Ts'o iput(inode); 180345c0dbfSTheodore Ts'o return err; 181345c0dbfSTheodore Ts'o } 182345c0dbfSTheodore Ts'o 1836fd058f7STheodore Ts'o int ext4_setup_system_zone(struct super_block *sb) 1846fd058f7STheodore Ts'o { 1856fd058f7STheodore Ts'o ext4_group_t ngroups = ext4_get_groups_count(sb); 1866fd058f7STheodore Ts'o struct ext4_sb_info *sbi = EXT4_SB(sb); 1876fd058f7STheodore Ts'o struct ext4_group_desc *gdp; 1886fd058f7STheodore Ts'o ext4_group_t i; 1896fd058f7STheodore Ts'o int flex_size = ext4_flex_bg_size(sbi); 1906fd058f7STheodore Ts'o int ret; 1916fd058f7STheodore Ts'o 1926fd058f7STheodore Ts'o if (!test_opt(sb, BLOCK_VALIDITY)) { 19349598e04SJun Piao if (sbi->system_blks.rb_node) 1946fd058f7STheodore Ts'o ext4_release_system_zone(sb); 1956fd058f7STheodore Ts'o return 0; 1966fd058f7STheodore Ts'o } 19749598e04SJun Piao if (sbi->system_blks.rb_node) 1986fd058f7STheodore Ts'o return 0; 1996fd058f7STheodore Ts'o 2006fd058f7STheodore Ts'o for (i=0; i < ngroups; i++) { 2014b99faa2SKhazhismel Kumykov cond_resched(); 2026fd058f7STheodore Ts'o if (ext4_bg_has_super(sb, i) && 2036fd058f7STheodore Ts'o ((i < 5) || ((i % flex_size) == 0))) 2046fd058f7STheodore Ts'o add_system_zone(sbi, ext4_group_first_block_no(sb, i), 2051032988cSTheodore Ts'o ext4_bg_num_gdb(sb, i) + 1); 2066fd058f7STheodore Ts'o gdp = ext4_get_group_desc(sb, i, NULL); 2076fd058f7STheodore Ts'o ret = add_system_zone(sbi, ext4_block_bitmap(sb, gdp), 1); 2086fd058f7STheodore Ts'o if (ret) 2096fd058f7STheodore Ts'o return ret; 2106fd058f7STheodore Ts'o ret = add_system_zone(sbi, ext4_inode_bitmap(sb, gdp), 1); 2116fd058f7STheodore Ts'o if (ret) 2126fd058f7STheodore Ts'o return ret; 2136fd058f7STheodore Ts'o ret = add_system_zone(sbi, ext4_inode_table(sb, gdp), 2146fd058f7STheodore Ts'o sbi->s_itb_per_group); 2156fd058f7STheodore Ts'o if (ret) 2166fd058f7STheodore Ts'o return ret; 2176fd058f7STheodore Ts'o } 218345c0dbfSTheodore Ts'o if (ext4_has_feature_journal(sb) && sbi->s_es->s_journal_inum) { 219345c0dbfSTheodore Ts'o ret = ext4_protect_reserved_inode(sb, 220345c0dbfSTheodore Ts'o le32_to_cpu(sbi->s_es->s_journal_inum)); 221345c0dbfSTheodore Ts'o if (ret) 222345c0dbfSTheodore Ts'o return ret; 223345c0dbfSTheodore Ts'o } 2246fd058f7STheodore Ts'o 2256fd058f7STheodore Ts'o if (test_opt(sb, DEBUG)) 22649598e04SJun Piao debug_print_tree(sbi); 2276fd058f7STheodore Ts'o return 0; 2286fd058f7STheodore Ts'o } 2296fd058f7STheodore Ts'o 2306fd058f7STheodore Ts'o /* Called when the filesystem is unmounted */ 2316fd058f7STheodore Ts'o void ext4_release_system_zone(struct super_block *sb) 2326fd058f7STheodore Ts'o { 233d1866bd0SCody P Schafer struct ext4_system_zone *entry, *n; 2346fd058f7STheodore Ts'o 235d1866bd0SCody P Schafer rbtree_postorder_for_each_entry_safe(entry, n, 236d1866bd0SCody P Schafer &EXT4_SB(sb)->system_blks, node) 2376fd058f7STheodore Ts'o kmem_cache_free(ext4_system_zone_cachep, entry); 238d1866bd0SCody P Schafer 23964e290ecSVenkatesh Pallipadi EXT4_SB(sb)->system_blks = RB_ROOT; 2406fd058f7STheodore Ts'o } 2416fd058f7STheodore Ts'o 2426fd058f7STheodore Ts'o /* 2436fd058f7STheodore Ts'o * Returns 1 if the passed-in block region (start_blk, 2446fd058f7STheodore Ts'o * start_blk+count) is valid; 0 if some part of the block region 2456fd058f7STheodore Ts'o * overlaps with filesystem metadata blocks. 2466fd058f7STheodore Ts'o */ 2476fd058f7STheodore Ts'o int ext4_data_block_valid(struct ext4_sb_info *sbi, ext4_fsblk_t start_blk, 2486fd058f7STheodore Ts'o unsigned int count) 2496fd058f7STheodore Ts'o { 2506fd058f7STheodore Ts'o struct ext4_system_zone *entry; 2516fd058f7STheodore Ts'o struct rb_node *n = sbi->system_blks.rb_node; 2526fd058f7STheodore Ts'o 2536fd058f7STheodore Ts'o if ((start_blk <= le32_to_cpu(sbi->s_es->s_first_data_block)) || 2541585d8d8STheodore Ts'o (start_blk + count < start_blk) || 2551c13d5c0STheodore Ts'o (start_blk + count > ext4_blocks_count(sbi->s_es))) { 2561c13d5c0STheodore Ts'o sbi->s_es->s_last_error_block = cpu_to_le64(start_blk); 2576fd058f7STheodore Ts'o return 0; 2581c13d5c0STheodore Ts'o } 2596fd058f7STheodore Ts'o while (n) { 2606fd058f7STheodore Ts'o entry = rb_entry(n, struct ext4_system_zone, node); 2616fd058f7STheodore Ts'o if (start_blk + count - 1 < entry->start_blk) 2626fd058f7STheodore Ts'o n = n->rb_left; 2636fd058f7STheodore Ts'o else if (start_blk >= (entry->start_blk + entry->count)) 2646fd058f7STheodore Ts'o n = n->rb_right; 2651c13d5c0STheodore Ts'o else { 2661c13d5c0STheodore Ts'o sbi->s_es->s_last_error_block = cpu_to_le64(start_blk); 2676fd058f7STheodore Ts'o return 0; 2686fd058f7STheodore Ts'o } 2691c13d5c0STheodore Ts'o } 2706fd058f7STheodore Ts'o return 1; 2716fd058f7STheodore Ts'o } 2726fd058f7STheodore Ts'o 2731f7d1e77STheodore Ts'o int ext4_check_blockref(const char *function, unsigned int line, 2741f7d1e77STheodore Ts'o struct inode *inode, __le32 *p, unsigned int max) 2751f7d1e77STheodore Ts'o { 2761f7d1e77STheodore Ts'o struct ext4_super_block *es = EXT4_SB(inode->i_sb)->s_es; 2771f7d1e77STheodore Ts'o __le32 *bref = p; 2781f7d1e77STheodore Ts'o unsigned int blk; 2791f7d1e77STheodore Ts'o 2801f7d1e77STheodore Ts'o while (bref < p+max) { 2811f7d1e77STheodore Ts'o blk = le32_to_cpu(*bref++); 2821f7d1e77STheodore Ts'o if (blk && 2831f7d1e77STheodore Ts'o unlikely(!ext4_data_block_valid(EXT4_SB(inode->i_sb), 2841f7d1e77STheodore Ts'o blk, 1))) { 2851f7d1e77STheodore Ts'o es->s_last_error_block = cpu_to_le64(blk); 2861f7d1e77STheodore Ts'o ext4_error_inode(inode, function, line, blk, 2871f7d1e77STheodore Ts'o "invalid block"); 2886a797d27SDarrick J. Wong return -EFSCORRUPTED; 2891f7d1e77STheodore Ts'o } 2901f7d1e77STheodore Ts'o } 2911f7d1e77STheodore Ts'o return 0; 2921f7d1e77STheodore Ts'o } 293dae1e52cSAmir Goldstein 294