16fd058f7STheodore Ts'o /* 26fd058f7STheodore Ts'o * linux/fs/ext4/block_validity.c 36fd058f7STheodore Ts'o * 46fd058f7STheodore Ts'o * Copyright (C) 2009 56fd058f7STheodore Ts'o * Theodore Ts'o (tytso@mit.edu) 66fd058f7STheodore Ts'o * 76fd058f7STheodore Ts'o * Track which blocks in the filesystem are metadata blocks that 86fd058f7STheodore Ts'o * should never be used as data blocks by files or directories. 96fd058f7STheodore Ts'o */ 106fd058f7STheodore Ts'o 116fd058f7STheodore Ts'o #include <linux/time.h> 126fd058f7STheodore Ts'o #include <linux/fs.h> 136fd058f7STheodore Ts'o #include <linux/namei.h> 146fd058f7STheodore Ts'o #include <linux/quotaops.h> 156fd058f7STheodore Ts'o #include <linux/buffer_head.h> 166fd058f7STheodore Ts'o #include <linux/module.h> 176fd058f7STheodore Ts'o #include <linux/swap.h> 186fd058f7STheodore Ts'o #include <linux/pagemap.h> 196fd058f7STheodore Ts'o #include <linux/blkdev.h> 206fd058f7STheodore Ts'o #include <linux/mutex.h> 215a0e3ad6STejun Heo #include <linux/slab.h> 226fd058f7STheodore Ts'o #include "ext4.h" 236fd058f7STheodore Ts'o 246fd058f7STheodore Ts'o struct ext4_system_zone { 256fd058f7STheodore Ts'o struct rb_node node; 266fd058f7STheodore Ts'o ext4_fsblk_t start_blk; 276fd058f7STheodore Ts'o unsigned int count; 286fd058f7STheodore Ts'o }; 296fd058f7STheodore Ts'o 306fd058f7STheodore Ts'o static struct kmem_cache *ext4_system_zone_cachep; 316fd058f7STheodore Ts'o 325dabfc78STheodore Ts'o int __init ext4_init_system_zone(void) 336fd058f7STheodore Ts'o { 3416828088STheodore Ts'o ext4_system_zone_cachep = KMEM_CACHE(ext4_system_zone, 0); 356fd058f7STheodore Ts'o if (ext4_system_zone_cachep == NULL) 366fd058f7STheodore Ts'o return -ENOMEM; 376fd058f7STheodore Ts'o return 0; 386fd058f7STheodore Ts'o } 396fd058f7STheodore Ts'o 405dabfc78STheodore Ts'o void ext4_exit_system_zone(void) 416fd058f7STheodore Ts'o { 426fd058f7STheodore Ts'o kmem_cache_destroy(ext4_system_zone_cachep); 436fd058f7STheodore Ts'o } 446fd058f7STheodore Ts'o 456fd058f7STheodore Ts'o static inline int can_merge(struct ext4_system_zone *entry1, 466fd058f7STheodore Ts'o struct ext4_system_zone *entry2) 476fd058f7STheodore Ts'o { 486fd058f7STheodore Ts'o if ((entry1->start_blk + entry1->count) == entry2->start_blk) 496fd058f7STheodore Ts'o return 1; 506fd058f7STheodore Ts'o return 0; 516fd058f7STheodore Ts'o } 526fd058f7STheodore Ts'o 536fd058f7STheodore Ts'o /* 546fd058f7STheodore Ts'o * Mark a range of blocks as belonging to the "system zone" --- that 556fd058f7STheodore Ts'o * is, filesystem metadata blocks which should never be used by 566fd058f7STheodore Ts'o * inodes. 576fd058f7STheodore Ts'o */ 586fd058f7STheodore Ts'o static int add_system_zone(struct ext4_sb_info *sbi, 596fd058f7STheodore Ts'o ext4_fsblk_t start_blk, 606fd058f7STheodore Ts'o unsigned int count) 616fd058f7STheodore Ts'o { 626fd058f7STheodore Ts'o struct ext4_system_zone *new_entry = NULL, *entry; 636fd058f7STheodore Ts'o struct rb_node **n = &sbi->system_blks.rb_node, *node; 646fd058f7STheodore Ts'o struct rb_node *parent = NULL, *new_node = NULL; 656fd058f7STheodore Ts'o 666fd058f7STheodore Ts'o while (*n) { 676fd058f7STheodore Ts'o parent = *n; 686fd058f7STheodore Ts'o entry = rb_entry(parent, struct ext4_system_zone, node); 696fd058f7STheodore Ts'o if (start_blk < entry->start_blk) 706fd058f7STheodore Ts'o n = &(*n)->rb_left; 716fd058f7STheodore Ts'o else if (start_blk >= (entry->start_blk + entry->count)) 726fd058f7STheodore Ts'o n = &(*n)->rb_right; 736fd058f7STheodore Ts'o else { 746fd058f7STheodore Ts'o if (start_blk + count > (entry->start_blk + 756fd058f7STheodore Ts'o entry->count)) 766fd058f7STheodore Ts'o entry->count = (start_blk + count - 776fd058f7STheodore Ts'o entry->start_blk); 786fd058f7STheodore Ts'o new_node = *n; 796fd058f7STheodore Ts'o new_entry = rb_entry(new_node, struct ext4_system_zone, 806fd058f7STheodore Ts'o node); 816fd058f7STheodore Ts'o break; 826fd058f7STheodore Ts'o } 836fd058f7STheodore Ts'o } 846fd058f7STheodore Ts'o 856fd058f7STheodore Ts'o if (!new_entry) { 866fd058f7STheodore Ts'o new_entry = kmem_cache_alloc(ext4_system_zone_cachep, 876fd058f7STheodore Ts'o GFP_KERNEL); 886fd058f7STheodore Ts'o if (!new_entry) 896fd058f7STheodore Ts'o return -ENOMEM; 906fd058f7STheodore Ts'o new_entry->start_blk = start_blk; 916fd058f7STheodore Ts'o new_entry->count = count; 926fd058f7STheodore Ts'o new_node = &new_entry->node; 936fd058f7STheodore Ts'o 946fd058f7STheodore Ts'o rb_link_node(new_node, parent, n); 956fd058f7STheodore Ts'o rb_insert_color(new_node, &sbi->system_blks); 966fd058f7STheodore Ts'o } 976fd058f7STheodore Ts'o 986fd058f7STheodore Ts'o /* Can we merge to the left? */ 996fd058f7STheodore Ts'o node = rb_prev(new_node); 1006fd058f7STheodore Ts'o if (node) { 1016fd058f7STheodore Ts'o entry = rb_entry(node, struct ext4_system_zone, node); 1026fd058f7STheodore Ts'o if (can_merge(entry, new_entry)) { 1036fd058f7STheodore Ts'o new_entry->start_blk = entry->start_blk; 1046fd058f7STheodore Ts'o new_entry->count += entry->count; 1056fd058f7STheodore Ts'o rb_erase(node, &sbi->system_blks); 1066fd058f7STheodore Ts'o kmem_cache_free(ext4_system_zone_cachep, entry); 1076fd058f7STheodore Ts'o } 1086fd058f7STheodore Ts'o } 1096fd058f7STheodore Ts'o 1106fd058f7STheodore Ts'o /* Can we merge to the right? */ 1116fd058f7STheodore Ts'o node = rb_next(new_node); 1126fd058f7STheodore Ts'o if (node) { 1136fd058f7STheodore Ts'o entry = rb_entry(node, struct ext4_system_zone, node); 1146fd058f7STheodore Ts'o if (can_merge(new_entry, entry)) { 1156fd058f7STheodore Ts'o new_entry->count += entry->count; 1166fd058f7STheodore Ts'o rb_erase(node, &sbi->system_blks); 1176fd058f7STheodore Ts'o kmem_cache_free(ext4_system_zone_cachep, entry); 1186fd058f7STheodore Ts'o } 1196fd058f7STheodore Ts'o } 1206fd058f7STheodore Ts'o return 0; 1216fd058f7STheodore Ts'o } 1226fd058f7STheodore Ts'o 1236fd058f7STheodore Ts'o static void debug_print_tree(struct ext4_sb_info *sbi) 1246fd058f7STheodore Ts'o { 1256fd058f7STheodore Ts'o struct rb_node *node; 1266fd058f7STheodore Ts'o struct ext4_system_zone *entry; 1276fd058f7STheodore Ts'o int first = 1; 1286fd058f7STheodore Ts'o 1296fd058f7STheodore Ts'o printk(KERN_INFO "System zones: "); 1306fd058f7STheodore Ts'o node = rb_first(&sbi->system_blks); 1316fd058f7STheodore Ts'o while (node) { 1326fd058f7STheodore Ts'o entry = rb_entry(node, struct ext4_system_zone, node); 1336fd058f7STheodore Ts'o printk("%s%llu-%llu", first ? "" : ", ", 1346fd058f7STheodore Ts'o entry->start_blk, entry->start_blk + entry->count - 1); 1356fd058f7STheodore Ts'o first = 0; 1366fd058f7STheodore Ts'o node = rb_next(node); 1376fd058f7STheodore Ts'o } 1386fd058f7STheodore Ts'o printk("\n"); 1396fd058f7STheodore Ts'o } 1406fd058f7STheodore Ts'o 1416fd058f7STheodore Ts'o int ext4_setup_system_zone(struct super_block *sb) 1426fd058f7STheodore Ts'o { 1436fd058f7STheodore Ts'o ext4_group_t ngroups = ext4_get_groups_count(sb); 1446fd058f7STheodore Ts'o struct ext4_sb_info *sbi = EXT4_SB(sb); 1456fd058f7STheodore Ts'o struct ext4_group_desc *gdp; 1466fd058f7STheodore Ts'o ext4_group_t i; 1476fd058f7STheodore Ts'o int flex_size = ext4_flex_bg_size(sbi); 1486fd058f7STheodore Ts'o int ret; 1496fd058f7STheodore Ts'o 1506fd058f7STheodore Ts'o if (!test_opt(sb, BLOCK_VALIDITY)) { 1516fd058f7STheodore Ts'o if (EXT4_SB(sb)->system_blks.rb_node) 1526fd058f7STheodore Ts'o ext4_release_system_zone(sb); 1536fd058f7STheodore Ts'o return 0; 1546fd058f7STheodore Ts'o } 1556fd058f7STheodore Ts'o if (EXT4_SB(sb)->system_blks.rb_node) 1566fd058f7STheodore Ts'o return 0; 1576fd058f7STheodore Ts'o 1586fd058f7STheodore Ts'o for (i=0; i < ngroups; i++) { 1596fd058f7STheodore Ts'o if (ext4_bg_has_super(sb, i) && 1606fd058f7STheodore Ts'o ((i < 5) || ((i % flex_size) == 0))) 1616fd058f7STheodore Ts'o add_system_zone(sbi, ext4_group_first_block_no(sb, i), 1621032988cSTheodore Ts'o ext4_bg_num_gdb(sb, i) + 1); 1636fd058f7STheodore Ts'o gdp = ext4_get_group_desc(sb, i, NULL); 1646fd058f7STheodore Ts'o ret = add_system_zone(sbi, ext4_block_bitmap(sb, gdp), 1); 1656fd058f7STheodore Ts'o if (ret) 1666fd058f7STheodore Ts'o return ret; 1676fd058f7STheodore Ts'o ret = add_system_zone(sbi, ext4_inode_bitmap(sb, gdp), 1); 1686fd058f7STheodore Ts'o if (ret) 1696fd058f7STheodore Ts'o return ret; 1706fd058f7STheodore Ts'o ret = add_system_zone(sbi, ext4_inode_table(sb, gdp), 1716fd058f7STheodore Ts'o sbi->s_itb_per_group); 1726fd058f7STheodore Ts'o if (ret) 1736fd058f7STheodore Ts'o return ret; 1746fd058f7STheodore Ts'o } 1756fd058f7STheodore Ts'o 1766fd058f7STheodore Ts'o if (test_opt(sb, DEBUG)) 1776fd058f7STheodore Ts'o debug_print_tree(EXT4_SB(sb)); 1786fd058f7STheodore Ts'o return 0; 1796fd058f7STheodore Ts'o } 1806fd058f7STheodore Ts'o 1816fd058f7STheodore Ts'o /* Called when the filesystem is unmounted */ 1826fd058f7STheodore Ts'o void ext4_release_system_zone(struct super_block *sb) 1836fd058f7STheodore Ts'o { 1846fd058f7STheodore Ts'o struct rb_node *n = EXT4_SB(sb)->system_blks.rb_node; 1856fd058f7STheodore Ts'o struct rb_node *parent; 1866fd058f7STheodore Ts'o struct ext4_system_zone *entry; 1876fd058f7STheodore Ts'o 1886fd058f7STheodore Ts'o while (n) { 1896fd058f7STheodore Ts'o /* Do the node's children first */ 1906fd058f7STheodore Ts'o if (n->rb_left) { 1916fd058f7STheodore Ts'o n = n->rb_left; 1926fd058f7STheodore Ts'o continue; 1936fd058f7STheodore Ts'o } 1946fd058f7STheodore Ts'o if (n->rb_right) { 1956fd058f7STheodore Ts'o n = n->rb_right; 1966fd058f7STheodore Ts'o continue; 1976fd058f7STheodore Ts'o } 1986fd058f7STheodore Ts'o /* 1996fd058f7STheodore Ts'o * The node has no children; free it, and then zero 2006fd058f7STheodore Ts'o * out parent's link to it. Finally go to the 2016fd058f7STheodore Ts'o * beginning of the loop and try to free the parent 2026fd058f7STheodore Ts'o * node. 2036fd058f7STheodore Ts'o */ 2046fd058f7STheodore Ts'o parent = rb_parent(n); 2056fd058f7STheodore Ts'o entry = rb_entry(n, struct ext4_system_zone, node); 2066fd058f7STheodore Ts'o kmem_cache_free(ext4_system_zone_cachep, entry); 2076fd058f7STheodore Ts'o if (!parent) 20864e290ecSVenkatesh Pallipadi EXT4_SB(sb)->system_blks = RB_ROOT; 2096fd058f7STheodore Ts'o else if (parent->rb_left == n) 2106fd058f7STheodore Ts'o parent->rb_left = NULL; 2116fd058f7STheodore Ts'o else if (parent->rb_right == n) 2126fd058f7STheodore Ts'o parent->rb_right = NULL; 2136fd058f7STheodore Ts'o n = parent; 2146fd058f7STheodore Ts'o } 21564e290ecSVenkatesh Pallipadi EXT4_SB(sb)->system_blks = RB_ROOT; 2166fd058f7STheodore Ts'o } 2176fd058f7STheodore Ts'o 2186fd058f7STheodore Ts'o /* 2196fd058f7STheodore Ts'o * Returns 1 if the passed-in block region (start_blk, 2206fd058f7STheodore Ts'o * start_blk+count) is valid; 0 if some part of the block region 2216fd058f7STheodore Ts'o * overlaps with filesystem metadata blocks. 2226fd058f7STheodore Ts'o */ 2236fd058f7STheodore Ts'o int ext4_data_block_valid(struct ext4_sb_info *sbi, ext4_fsblk_t start_blk, 2246fd058f7STheodore Ts'o unsigned int count) 2256fd058f7STheodore Ts'o { 2266fd058f7STheodore Ts'o struct ext4_system_zone *entry; 2276fd058f7STheodore Ts'o struct rb_node *n = sbi->system_blks.rb_node; 2286fd058f7STheodore Ts'o 2296fd058f7STheodore Ts'o if ((start_blk <= le32_to_cpu(sbi->s_es->s_first_data_block)) || 2301585d8d8STheodore Ts'o (start_blk + count < start_blk) || 2311c13d5c0STheodore Ts'o (start_blk + count > ext4_blocks_count(sbi->s_es))) { 2321c13d5c0STheodore Ts'o sbi->s_es->s_last_error_block = cpu_to_le64(start_blk); 2336fd058f7STheodore Ts'o return 0; 2341c13d5c0STheodore Ts'o } 2356fd058f7STheodore Ts'o while (n) { 2366fd058f7STheodore Ts'o entry = rb_entry(n, struct ext4_system_zone, node); 2376fd058f7STheodore Ts'o if (start_blk + count - 1 < entry->start_blk) 2386fd058f7STheodore Ts'o n = n->rb_left; 2396fd058f7STheodore Ts'o else if (start_blk >= (entry->start_blk + entry->count)) 2406fd058f7STheodore Ts'o n = n->rb_right; 2411c13d5c0STheodore Ts'o else { 2421c13d5c0STheodore Ts'o sbi->s_es->s_last_error_block = cpu_to_le64(start_blk); 2436fd058f7STheodore Ts'o return 0; 2446fd058f7STheodore Ts'o } 2451c13d5c0STheodore Ts'o } 2466fd058f7STheodore Ts'o return 1; 2476fd058f7STheodore Ts'o } 2486fd058f7STheodore Ts'o 249