Commit | Line | Data |
---|---|---|
6fd058f7 TT |
1 | /* |
2 | * linux/fs/ext4/block_validity.c | |
3 | * | |
4 | * Copyright (C) 2009 | |
5 | * Theodore Ts'o (tytso@mit.edu) | |
6 | * | |
7 | * Track which blocks in the filesystem are metadata blocks that | |
8 | * should never be used as data blocks by files or directories. | |
9 | */ | |
10 | ||
11 | #include <linux/time.h> | |
12 | #include <linux/fs.h> | |
13 | #include <linux/namei.h> | |
14 | #include <linux/quotaops.h> | |
15 | #include <linux/buffer_head.h> | |
16 | #include <linux/module.h> | |
17 | #include <linux/swap.h> | |
18 | #include <linux/pagemap.h> | |
6fd058f7 TT |
19 | #include <linux/blkdev.h> |
20 | #include <linux/mutex.h> | |
21 | #include "ext4.h" | |
22 | ||
23 | struct ext4_system_zone { | |
24 | struct rb_node node; | |
25 | ext4_fsblk_t start_blk; | |
26 | unsigned int count; | |
27 | }; | |
28 | ||
29 | static struct kmem_cache *ext4_system_zone_cachep; | |
30 | ||
31 | int __init init_ext4_system_zone(void) | |
32 | { | |
33 | ext4_system_zone_cachep = KMEM_CACHE(ext4_system_zone, | |
34 | SLAB_RECLAIM_ACCOUNT); | |
35 | if (ext4_system_zone_cachep == NULL) | |
36 | return -ENOMEM; | |
37 | return 0; | |
38 | } | |
39 | ||
40 | void exit_ext4_system_zone(void) | |
41 | { | |
42 | kmem_cache_destroy(ext4_system_zone_cachep); | |
43 | } | |
44 | ||
45 | static inline int can_merge(struct ext4_system_zone *entry1, | |
46 | struct ext4_system_zone *entry2) | |
47 | { | |
48 | if ((entry1->start_blk + entry1->count) == entry2->start_blk) | |
49 | return 1; | |
50 | return 0; | |
51 | } | |
52 | ||
53 | /* | |
54 | * Mark a range of blocks as belonging to the "system zone" --- that | |
55 | * is, filesystem metadata blocks which should never be used by | |
56 | * inodes. | |
57 | */ | |
58 | static int add_system_zone(struct ext4_sb_info *sbi, | |
59 | ext4_fsblk_t start_blk, | |
60 | unsigned int count) | |
61 | { | |
62 | struct ext4_system_zone *new_entry = NULL, *entry; | |
63 | struct rb_node **n = &sbi->system_blks.rb_node, *node; | |
64 | struct rb_node *parent = NULL, *new_node = NULL; | |
65 | ||
66 | while (*n) { | |
67 | parent = *n; | |
68 | entry = rb_entry(parent, struct ext4_system_zone, node); | |
69 | if (start_blk < entry->start_blk) | |
70 | n = &(*n)->rb_left; | |
71 | else if (start_blk >= (entry->start_blk + entry->count)) | |
72 | n = &(*n)->rb_right; | |
73 | else { | |
74 | if (start_blk + count > (entry->start_blk + | |
75 | entry->count)) | |
76 | entry->count = (start_blk + count - | |
77 | entry->start_blk); | |
78 | new_node = *n; | |
79 | new_entry = rb_entry(new_node, struct ext4_system_zone, | |
80 | node); | |
81 | break; | |
82 | } | |
83 | } | |
84 | ||
85 | if (!new_entry) { | |
86 | new_entry = kmem_cache_alloc(ext4_system_zone_cachep, | |
87 | GFP_KERNEL); | |
88 | if (!new_entry) | |
89 | return -ENOMEM; | |
90 | new_entry->start_blk = start_blk; | |
91 | new_entry->count = count; | |
92 | new_node = &new_entry->node; | |
93 | ||
94 | rb_link_node(new_node, parent, n); | |
95 | rb_insert_color(new_node, &sbi->system_blks); | |
96 | } | |
97 | ||
98 | /* Can we merge to the left? */ | |
99 | node = rb_prev(new_node); | |
100 | if (node) { | |
101 | entry = rb_entry(node, struct ext4_system_zone, node); | |
102 | if (can_merge(entry, new_entry)) { | |
103 | new_entry->start_blk = entry->start_blk; | |
104 | new_entry->count += entry->count; | |
105 | rb_erase(node, &sbi->system_blks); | |
106 | kmem_cache_free(ext4_system_zone_cachep, entry); | |
107 | } | |
108 | } | |
109 | ||
110 | /* Can we merge to the right? */ | |
111 | node = rb_next(new_node); | |
112 | if (node) { | |
113 | entry = rb_entry(node, struct ext4_system_zone, node); | |
114 | if (can_merge(new_entry, entry)) { | |
115 | new_entry->count += entry->count; | |
116 | rb_erase(node, &sbi->system_blks); | |
117 | kmem_cache_free(ext4_system_zone_cachep, entry); | |
118 | } | |
119 | } | |
120 | return 0; | |
121 | } | |
122 | ||
123 | static void debug_print_tree(struct ext4_sb_info *sbi) | |
124 | { | |
125 | struct rb_node *node; | |
126 | struct ext4_system_zone *entry; | |
127 | int first = 1; | |
128 | ||
129 | printk(KERN_INFO "System zones: "); | |
130 | node = rb_first(&sbi->system_blks); | |
131 | while (node) { | |
132 | entry = rb_entry(node, struct ext4_system_zone, node); | |
133 | printk("%s%llu-%llu", first ? "" : ", ", | |
134 | entry->start_blk, entry->start_blk + entry->count - 1); | |
135 | first = 0; | |
136 | node = rb_next(node); | |
137 | } | |
138 | printk("\n"); | |
139 | } | |
140 | ||
141 | int ext4_setup_system_zone(struct super_block *sb) | |
142 | { | |
143 | ext4_group_t ngroups = ext4_get_groups_count(sb); | |
144 | struct ext4_sb_info *sbi = EXT4_SB(sb); | |
145 | struct ext4_group_desc *gdp; | |
146 | ext4_group_t i; | |
147 | int flex_size = ext4_flex_bg_size(sbi); | |
148 | int ret; | |
149 | ||
150 | if (!test_opt(sb, BLOCK_VALIDITY)) { | |
151 | if (EXT4_SB(sb)->system_blks.rb_node) | |
152 | ext4_release_system_zone(sb); | |
153 | return 0; | |
154 | } | |
155 | if (EXT4_SB(sb)->system_blks.rb_node) | |
156 | return 0; | |
157 | ||
158 | for (i=0; i < ngroups; i++) { | |
159 | if (ext4_bg_has_super(sb, i) && | |
160 | ((i < 5) || ((i % flex_size) == 0))) | |
161 | add_system_zone(sbi, ext4_group_first_block_no(sb, i), | |
1032988c | 162 | ext4_bg_num_gdb(sb, i) + 1); |
6fd058f7 TT |
163 | gdp = ext4_get_group_desc(sb, i, NULL); |
164 | ret = add_system_zone(sbi, ext4_block_bitmap(sb, gdp), 1); | |
165 | if (ret) | |
166 | return ret; | |
167 | ret = add_system_zone(sbi, ext4_inode_bitmap(sb, gdp), 1); | |
168 | if (ret) | |
169 | return ret; | |
170 | ret = add_system_zone(sbi, ext4_inode_table(sb, gdp), | |
171 | sbi->s_itb_per_group); | |
172 | if (ret) | |
173 | return ret; | |
174 | } | |
175 | ||
176 | if (test_opt(sb, DEBUG)) | |
177 | debug_print_tree(EXT4_SB(sb)); | |
178 | return 0; | |
179 | } | |
180 | ||
181 | /* Called when the filesystem is unmounted */ | |
182 | void ext4_release_system_zone(struct super_block *sb) | |
183 | { | |
184 | struct rb_node *n = EXT4_SB(sb)->system_blks.rb_node; | |
185 | struct rb_node *parent; | |
186 | struct ext4_system_zone *entry; | |
187 | ||
188 | while (n) { | |
189 | /* Do the node's children first */ | |
190 | if (n->rb_left) { | |
191 | n = n->rb_left; | |
192 | continue; | |
193 | } | |
194 | if (n->rb_right) { | |
195 | n = n->rb_right; | |
196 | continue; | |
197 | } | |
198 | /* | |
199 | * The node has no children; free it, and then zero | |
200 | * out parent's link to it. Finally go to the | |
201 | * beginning of the loop and try to free the parent | |
202 | * node. | |
203 | */ | |
204 | parent = rb_parent(n); | |
205 | entry = rb_entry(n, struct ext4_system_zone, node); | |
206 | kmem_cache_free(ext4_system_zone_cachep, entry); | |
207 | if (!parent) | |
208 | EXT4_SB(sb)->system_blks.rb_node = NULL; | |
209 | else if (parent->rb_left == n) | |
210 | parent->rb_left = NULL; | |
211 | else if (parent->rb_right == n) | |
212 | parent->rb_right = NULL; | |
213 | n = parent; | |
214 | } | |
215 | EXT4_SB(sb)->system_blks.rb_node = NULL; | |
216 | } | |
217 | ||
218 | /* | |
219 | * Returns 1 if the passed-in block region (start_blk, | |
220 | * start_blk+count) is valid; 0 if some part of the block region | |
221 | * overlaps with filesystem metadata blocks. | |
222 | */ | |
223 | int ext4_data_block_valid(struct ext4_sb_info *sbi, ext4_fsblk_t start_blk, | |
224 | unsigned int count) | |
225 | { | |
226 | struct ext4_system_zone *entry; | |
227 | struct rb_node *n = sbi->system_blks.rb_node; | |
228 | ||
229 | if ((start_blk <= le32_to_cpu(sbi->s_es->s_first_data_block)) || | |
1585d8d8 | 230 | (start_blk + count < start_blk) || |
6fd058f7 TT |
231 | (start_blk + count > ext4_blocks_count(sbi->s_es))) |
232 | return 0; | |
233 | while (n) { | |
234 | entry = rb_entry(n, struct ext4_system_zone, node); | |
235 | if (start_blk + count - 1 < entry->start_blk) | |
236 | n = n->rb_left; | |
237 | else if (start_blk >= (entry->start_blk + entry->count)) | |
238 | n = n->rb_right; | |
239 | else | |
240 | return 0; | |
241 | } | |
242 | return 1; | |
243 | } | |
244 |