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/version.h> 206fd058f7STheodore Ts'o #include <linux/blkdev.h> 216fd058f7STheodore Ts'o #include <linux/mutex.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 326fd058f7STheodore Ts'o int __init init_ext4_system_zone(void) 336fd058f7STheodore Ts'o { 346fd058f7STheodore Ts'o ext4_system_zone_cachep = KMEM_CACHE(ext4_system_zone, 356fd058f7STheodore Ts'o SLAB_RECLAIM_ACCOUNT); 366fd058f7STheodore Ts'o if (ext4_system_zone_cachep == NULL) 376fd058f7STheodore Ts'o return -ENOMEM; 386fd058f7STheodore Ts'o return 0; 396fd058f7STheodore Ts'o } 406fd058f7STheodore Ts'o 416fd058f7STheodore Ts'o void exit_ext4_system_zone(void) 426fd058f7STheodore Ts'o { 436fd058f7STheodore Ts'o kmem_cache_destroy(ext4_system_zone_cachep); 446fd058f7STheodore Ts'o } 456fd058f7STheodore Ts'o 466fd058f7STheodore Ts'o static inline int can_merge(struct ext4_system_zone *entry1, 476fd058f7STheodore Ts'o struct ext4_system_zone *entry2) 486fd058f7STheodore Ts'o { 496fd058f7STheodore Ts'o if ((entry1->start_blk + entry1->count) == entry2->start_blk) 506fd058f7STheodore Ts'o return 1; 516fd058f7STheodore Ts'o return 0; 526fd058f7STheodore Ts'o } 536fd058f7STheodore Ts'o 546fd058f7STheodore Ts'o /* 556fd058f7STheodore Ts'o * Mark a range of blocks as belonging to the "system zone" --- that 566fd058f7STheodore Ts'o * is, filesystem metadata blocks which should never be used by 576fd058f7STheodore Ts'o * inodes. 586fd058f7STheodore Ts'o */ 596fd058f7STheodore Ts'o static int add_system_zone(struct ext4_sb_info *sbi, 606fd058f7STheodore Ts'o ext4_fsblk_t start_blk, 616fd058f7STheodore Ts'o unsigned int count) 626fd058f7STheodore Ts'o { 636fd058f7STheodore Ts'o struct ext4_system_zone *new_entry = NULL, *entry; 646fd058f7STheodore Ts'o struct rb_node **n = &sbi->system_blks.rb_node, *node; 656fd058f7STheodore Ts'o struct rb_node *parent = NULL, *new_node = NULL; 666fd058f7STheodore Ts'o 676fd058f7STheodore Ts'o while (*n) { 686fd058f7STheodore Ts'o parent = *n; 696fd058f7STheodore Ts'o entry = rb_entry(parent, struct ext4_system_zone, node); 706fd058f7STheodore Ts'o if (start_blk < entry->start_blk) 716fd058f7STheodore Ts'o n = &(*n)->rb_left; 726fd058f7STheodore Ts'o else if (start_blk >= (entry->start_blk + entry->count)) 736fd058f7STheodore Ts'o n = &(*n)->rb_right; 746fd058f7STheodore Ts'o else { 756fd058f7STheodore Ts'o if (start_blk + count > (entry->start_blk + 766fd058f7STheodore Ts'o entry->count)) 776fd058f7STheodore Ts'o entry->count = (start_blk + count - 786fd058f7STheodore Ts'o entry->start_blk); 796fd058f7STheodore Ts'o new_node = *n; 806fd058f7STheodore Ts'o new_entry = rb_entry(new_node, struct ext4_system_zone, 816fd058f7STheodore Ts'o node); 826fd058f7STheodore Ts'o break; 836fd058f7STheodore Ts'o } 846fd058f7STheodore Ts'o } 856fd058f7STheodore Ts'o 866fd058f7STheodore Ts'o if (!new_entry) { 876fd058f7STheodore Ts'o new_entry = kmem_cache_alloc(ext4_system_zone_cachep, 886fd058f7STheodore Ts'o GFP_KERNEL); 896fd058f7STheodore Ts'o if (!new_entry) 906fd058f7STheodore Ts'o return -ENOMEM; 916fd058f7STheodore Ts'o new_entry->start_blk = start_blk; 926fd058f7STheodore Ts'o new_entry->count = count; 936fd058f7STheodore Ts'o new_node = &new_entry->node; 946fd058f7STheodore Ts'o 956fd058f7STheodore Ts'o rb_link_node(new_node, parent, n); 966fd058f7STheodore Ts'o rb_insert_color(new_node, &sbi->system_blks); 976fd058f7STheodore Ts'o } 986fd058f7STheodore Ts'o 996fd058f7STheodore Ts'o /* Can we merge to the left? */ 1006fd058f7STheodore Ts'o node = rb_prev(new_node); 1016fd058f7STheodore Ts'o if (node) { 1026fd058f7STheodore Ts'o entry = rb_entry(node, struct ext4_system_zone, node); 1036fd058f7STheodore Ts'o if (can_merge(entry, new_entry)) { 1046fd058f7STheodore Ts'o new_entry->start_blk = entry->start_blk; 1056fd058f7STheodore Ts'o new_entry->count += entry->count; 1066fd058f7STheodore Ts'o rb_erase(node, &sbi->system_blks); 1076fd058f7STheodore Ts'o kmem_cache_free(ext4_system_zone_cachep, entry); 1086fd058f7STheodore Ts'o } 1096fd058f7STheodore Ts'o } 1106fd058f7STheodore Ts'o 1116fd058f7STheodore Ts'o /* Can we merge to the right? */ 1126fd058f7STheodore Ts'o node = rb_next(new_node); 1136fd058f7STheodore Ts'o if (node) { 1146fd058f7STheodore Ts'o entry = rb_entry(node, struct ext4_system_zone, node); 1156fd058f7STheodore Ts'o if (can_merge(new_entry, entry)) { 1166fd058f7STheodore Ts'o new_entry->count += entry->count; 1176fd058f7STheodore Ts'o rb_erase(node, &sbi->system_blks); 1186fd058f7STheodore Ts'o kmem_cache_free(ext4_system_zone_cachep, entry); 1196fd058f7STheodore Ts'o } 1206fd058f7STheodore Ts'o } 1216fd058f7STheodore Ts'o return 0; 1226fd058f7STheodore Ts'o } 1236fd058f7STheodore Ts'o 1246fd058f7STheodore Ts'o static void debug_print_tree(struct ext4_sb_info *sbi) 1256fd058f7STheodore Ts'o { 1266fd058f7STheodore Ts'o struct rb_node *node; 1276fd058f7STheodore Ts'o struct ext4_system_zone *entry; 1286fd058f7STheodore Ts'o int first = 1; 1296fd058f7STheodore Ts'o 1306fd058f7STheodore Ts'o printk(KERN_INFO "System zones: "); 1316fd058f7STheodore Ts'o node = rb_first(&sbi->system_blks); 1326fd058f7STheodore Ts'o while (node) { 1336fd058f7STheodore Ts'o entry = rb_entry(node, struct ext4_system_zone, node); 1346fd058f7STheodore Ts'o printk("%s%llu-%llu", first ? "" : ", ", 1356fd058f7STheodore Ts'o entry->start_blk, entry->start_blk + entry->count - 1); 1366fd058f7STheodore Ts'o first = 0; 1376fd058f7STheodore Ts'o node = rb_next(node); 1386fd058f7STheodore Ts'o } 1396fd058f7STheodore Ts'o printk("\n"); 1406fd058f7STheodore Ts'o } 1416fd058f7STheodore Ts'o 1426fd058f7STheodore Ts'o int ext4_setup_system_zone(struct super_block *sb) 1436fd058f7STheodore Ts'o { 1446fd058f7STheodore Ts'o ext4_group_t ngroups = ext4_get_groups_count(sb); 1456fd058f7STheodore Ts'o struct ext4_sb_info *sbi = EXT4_SB(sb); 1466fd058f7STheodore Ts'o struct ext4_group_desc *gdp; 1476fd058f7STheodore Ts'o ext4_group_t i; 1486fd058f7STheodore Ts'o int flex_size = ext4_flex_bg_size(sbi); 1496fd058f7STheodore Ts'o int ret; 1506fd058f7STheodore Ts'o 1516fd058f7STheodore Ts'o if (!test_opt(sb, BLOCK_VALIDITY)) { 1526fd058f7STheodore Ts'o if (EXT4_SB(sb)->system_blks.rb_node) 1536fd058f7STheodore Ts'o ext4_release_system_zone(sb); 1546fd058f7STheodore Ts'o return 0; 1556fd058f7STheodore Ts'o } 1566fd058f7STheodore Ts'o if (EXT4_SB(sb)->system_blks.rb_node) 1576fd058f7STheodore Ts'o return 0; 1586fd058f7STheodore Ts'o 1596fd058f7STheodore Ts'o for (i=0; i < ngroups; i++) { 1606fd058f7STheodore Ts'o if (ext4_bg_has_super(sb, i) && 1616fd058f7STheodore Ts'o ((i < 5) || ((i % flex_size) == 0))) 1626fd058f7STheodore Ts'o add_system_zone(sbi, ext4_group_first_block_no(sb, i), 1636fd058f7STheodore Ts'o sbi->s_gdb_count + 1); 1646fd058f7STheodore Ts'o gdp = ext4_get_group_desc(sb, i, NULL); 1656fd058f7STheodore Ts'o ret = add_system_zone(sbi, ext4_block_bitmap(sb, gdp), 1); 1666fd058f7STheodore Ts'o if (ret) 1676fd058f7STheodore Ts'o return ret; 1686fd058f7STheodore Ts'o ret = add_system_zone(sbi, ext4_inode_bitmap(sb, gdp), 1); 1696fd058f7STheodore Ts'o if (ret) 1706fd058f7STheodore Ts'o return ret; 1716fd058f7STheodore Ts'o ret = add_system_zone(sbi, ext4_inode_table(sb, gdp), 1726fd058f7STheodore Ts'o sbi->s_itb_per_group); 1736fd058f7STheodore Ts'o if (ret) 1746fd058f7STheodore Ts'o return ret; 1756fd058f7STheodore Ts'o } 1766fd058f7STheodore Ts'o 1776fd058f7STheodore Ts'o if (test_opt(sb, DEBUG)) 1786fd058f7STheodore Ts'o debug_print_tree(EXT4_SB(sb)); 1796fd058f7STheodore Ts'o return 0; 1806fd058f7STheodore Ts'o } 1816fd058f7STheodore Ts'o 1826fd058f7STheodore Ts'o /* Called when the filesystem is unmounted */ 1836fd058f7STheodore Ts'o void ext4_release_system_zone(struct super_block *sb) 1846fd058f7STheodore Ts'o { 1856fd058f7STheodore Ts'o struct rb_node *n = EXT4_SB(sb)->system_blks.rb_node; 1866fd058f7STheodore Ts'o struct rb_node *parent; 1876fd058f7STheodore Ts'o struct ext4_system_zone *entry; 1886fd058f7STheodore Ts'o 1896fd058f7STheodore Ts'o while (n) { 1906fd058f7STheodore Ts'o /* Do the node's children first */ 1916fd058f7STheodore Ts'o if (n->rb_left) { 1926fd058f7STheodore Ts'o n = n->rb_left; 1936fd058f7STheodore Ts'o continue; 1946fd058f7STheodore Ts'o } 1956fd058f7STheodore Ts'o if (n->rb_right) { 1966fd058f7STheodore Ts'o n = n->rb_right; 1976fd058f7STheodore Ts'o continue; 1986fd058f7STheodore Ts'o } 1996fd058f7STheodore Ts'o /* 2006fd058f7STheodore Ts'o * The node has no children; free it, and then zero 2016fd058f7STheodore Ts'o * out parent's link to it. Finally go to the 2026fd058f7STheodore Ts'o * beginning of the loop and try to free the parent 2036fd058f7STheodore Ts'o * node. 2046fd058f7STheodore Ts'o */ 2056fd058f7STheodore Ts'o parent = rb_parent(n); 2066fd058f7STheodore Ts'o entry = rb_entry(n, struct ext4_system_zone, node); 2076fd058f7STheodore Ts'o kmem_cache_free(ext4_system_zone_cachep, entry); 2086fd058f7STheodore Ts'o if (!parent) 2096fd058f7STheodore Ts'o EXT4_SB(sb)->system_blks.rb_node = NULL; 2106fd058f7STheodore Ts'o else if (parent->rb_left == n) 2116fd058f7STheodore Ts'o parent->rb_left = NULL; 2126fd058f7STheodore Ts'o else if (parent->rb_right == n) 2136fd058f7STheodore Ts'o parent->rb_right = NULL; 2146fd058f7STheodore Ts'o n = parent; 2156fd058f7STheodore Ts'o } 2166fd058f7STheodore Ts'o EXT4_SB(sb)->system_blks.rb_node = NULL; 2176fd058f7STheodore Ts'o } 2186fd058f7STheodore Ts'o 2196fd058f7STheodore Ts'o /* 2206fd058f7STheodore Ts'o * Returns 1 if the passed-in block region (start_blk, 2216fd058f7STheodore Ts'o * start_blk+count) is valid; 0 if some part of the block region 2226fd058f7STheodore Ts'o * overlaps with filesystem metadata blocks. 2236fd058f7STheodore Ts'o */ 2246fd058f7STheodore Ts'o int ext4_data_block_valid(struct ext4_sb_info *sbi, ext4_fsblk_t start_blk, 2256fd058f7STheodore Ts'o unsigned int count) 2266fd058f7STheodore Ts'o { 2276fd058f7STheodore Ts'o struct ext4_system_zone *entry; 2286fd058f7STheodore Ts'o struct rb_node *n = sbi->system_blks.rb_node; 2296fd058f7STheodore Ts'o 2306fd058f7STheodore Ts'o if ((start_blk <= le32_to_cpu(sbi->s_es->s_first_data_block)) || 2316fd058f7STheodore Ts'o (start_blk + count > ext4_blocks_count(sbi->s_es))) 2326fd058f7STheodore Ts'o return 0; 2336fd058f7STheodore Ts'o while (n) { 2346fd058f7STheodore Ts'o entry = rb_entry(n, struct ext4_system_zone, node); 2356fd058f7STheodore Ts'o if (start_blk + count - 1 < entry->start_blk) 2366fd058f7STheodore Ts'o n = n->rb_left; 2376fd058f7STheodore Ts'o else if (start_blk >= (entry->start_blk + entry->count)) 2386fd058f7STheodore Ts'o n = n->rb_right; 2396fd058f7STheodore Ts'o else 2406fd058f7STheodore Ts'o return 0; 2416fd058f7STheodore Ts'o } 2426fd058f7STheodore Ts'o return 1; 2436fd058f7STheodore Ts'o } 2446fd058f7STheodore Ts'o 245