Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
ext4_extents.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2003-2006, Cluster File Systems, Inc, [email protected]
3  * Written by Alex Tomas <[email protected]>
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public Licens
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-
17  */
18 
19 #ifndef _EXT4_EXTENTS
20 #define _EXT4_EXTENTS
21 
22 #include "ext4.h"
23 
24 /*
25  * With AGGRESSIVE_TEST defined, the capacity of index/leaf blocks
26  * becomes very small, so index split, in-depth growing and
27  * other hard changes happen much more often.
28  * This is for debug purposes only.
29  */
30 #define AGGRESSIVE_TEST_
31 
32 /*
33  * With EXTENTS_STATS defined, the number of blocks and extents
34  * are collected in the truncate path. They'll be shown at
35  * umount time.
36  */
37 #define EXTENTS_STATS__
38 
39 /*
40  * If CHECK_BINSEARCH is defined, then the results of the binary search
41  * will also be checked by linear search.
42  */
43 #define CHECK_BINSEARCH__
44 
45 /*
46  * Turn on EXT_DEBUG to get lots of info about extents operations.
47  */
48 #define EXT_DEBUG__
49 #ifdef EXT_DEBUG
50 #define ext_debug(fmt, ...) printk(fmt, ##__VA_ARGS__)
51 #else
52 #define ext_debug(fmt, ...) no_printk(fmt, ##__VA_ARGS__)
53 #endif
54 
55 /*
56  * If EXT_STATS is defined then stats numbers are collected.
57  * These number will be displayed at umount time.
58  */
59 #define EXT_STATS_
60 
61 
62 /*
63  * ext4_inode has i_block array (60 bytes total).
64  * The first 12 bytes store ext4_extent_header;
65  * the remainder stores an array of ext4_extent.
66  * For non-inode extent blocks, ext4_extent_tail
67  * follows the array.
68  */
69 
70 /*
71  * This is the extent tail on-disk structure.
72  * All other extent structures are 12 bytes long. It turns out that
73  * block_size % 12 >= 4 for at least all powers of 2 greater than 512, which
74  * covers all valid ext4 block sizes. Therefore, this tail structure can be
75  * crammed into the end of the block without having to rebalance the tree.
76  */
78  __le32 et_checksum; /* crc32c(uuid+inum+extent_block) */
79 };
80 
81 /*
82  * This is the extent on-disk structure.
83  * It's used at the bottom of the tree.
84  */
85 struct ext4_extent {
86  __le32 ee_block; /* first logical block extent covers */
87  __le16 ee_len; /* number of blocks covered by extent */
88  __le16 ee_start_hi; /* high 16 bits of physical block */
89  __le32 ee_start_lo; /* low 32 bits of physical block */
90 };
91 
92 /*
93  * This is index on-disk structure.
94  * It's used at all the levels except the bottom.
95  */
97  __le32 ei_block; /* index covers logical blocks from 'block' */
98  __le32 ei_leaf_lo; /* pointer to the physical block of the next *
99  * level. leaf or next index could be there */
100  __le16 ei_leaf_hi; /* high 16 bits of physical block */
102 };
103 
104 /*
105  * Each block (leaves and indexes), even inode-stored has header.
106  */
108  __le16 eh_magic; /* probably will support different formats */
109  __le16 eh_entries; /* number of valid entries */
110  __le16 eh_max; /* capacity of store in entries */
111  __le16 eh_depth; /* has tree real underlying blocks? */
112  __le32 eh_generation; /* generation of the tree */
113 };
114 
115 #define EXT4_EXT_MAGIC cpu_to_le16(0xf30a)
116 
117 #define EXT4_EXTENT_TAIL_OFFSET(hdr) \
118  (sizeof(struct ext4_extent_header) + \
119  (sizeof(struct ext4_extent) * le16_to_cpu((hdr)->eh_max)))
120 
121 static inline struct ext4_extent_tail *
122 find_ext4_extent_tail(struct ext4_extent_header *eh)
123 {
124  return (struct ext4_extent_tail *)(((void *)eh) +
126 }
127 
128 /*
129  * Array of ext4_ext_path contains path to some extent.
130  * Creation/lookup routines use it for traversal/splitting/etc.
131  * Truncate uses it to simulate recursive walking.
132  */
139  struct buffer_head *p_bh;
140 };
141 
142 /*
143  * structure for external API
144  */
145 
146 /*
147  * to be called by ext4_ext_walk_space()
148  * negative retcode - error
149  * positive retcode - signal for ext4_ext_walk_space(), see below
150  * callback must return valid extent (passed or newly created)
151  */
153  struct ext4_ext_cache *,
154  struct ext4_extent *, void *);
155 
156 #define EXT_CONTINUE 0
157 #define EXT_BREAK 1
158 #define EXT_REPEAT 2
159 
160 /*
161  * Maximum number of logical blocks in a file; ext4_extent's ee_block is
162  * __le32.
163  */
164 #define EXT_MAX_BLOCKS 0xffffffff
165 
166 /*
167  * EXT_INIT_MAX_LEN is the maximum number of blocks we can have in an
168  * initialized extent. This is 2^15 and not (2^16 - 1), since we use the
169  * MSB of ee_len field in the extent datastructure to signify if this
170  * particular extent is an initialized extent or an uninitialized (i.e.
171  * preallocated).
172  * EXT_UNINIT_MAX_LEN is the maximum number of blocks we can have in an
173  * uninitialized extent.
174  * If ee_len is <= 0x8000, it is an initialized extent. Otherwise, it is an
175  * uninitialized one. In other words, if MSB of ee_len is set, it is an
176  * uninitialized extent with only one special scenario when ee_len = 0x8000.
177  * In this case we can not have an uninitialized extent of zero length and
178  * thus we make it as a special case of initialized extent with 0x8000 length.
179  * This way we get better extent-to-group alignment for initialized extents.
180  * Hence, the maximum number of blocks we can have in an *initialized*
181  * extent is 2^15 (32768) and in an *uninitialized* extent is 2^15-1 (32767).
182  */
183 #define EXT_INIT_MAX_LEN (1UL << 15)
184 #define EXT_UNINIT_MAX_LEN (EXT_INIT_MAX_LEN - 1)
185 
186 
187 #define EXT_FIRST_EXTENT(__hdr__) \
188  ((struct ext4_extent *) (((char *) (__hdr__)) + \
189  sizeof(struct ext4_extent_header)))
190 #define EXT_FIRST_INDEX(__hdr__) \
191  ((struct ext4_extent_idx *) (((char *) (__hdr__)) + \
192  sizeof(struct ext4_extent_header)))
193 #define EXT_HAS_FREE_INDEX(__path__) \
194  (le16_to_cpu((__path__)->p_hdr->eh_entries) \
195  < le16_to_cpu((__path__)->p_hdr->eh_max))
196 #define EXT_LAST_EXTENT(__hdr__) \
197  (EXT_FIRST_EXTENT((__hdr__)) + le16_to_cpu((__hdr__)->eh_entries) - 1)
198 #define EXT_LAST_INDEX(__hdr__) \
199  (EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_entries) - 1)
200 #define EXT_MAX_EXTENT(__hdr__) \
201  (EXT_FIRST_EXTENT((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1)
202 #define EXT_MAX_INDEX(__hdr__) \
203  (EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1)
204 
205 static inline struct ext4_extent_header *ext_inode_hdr(struct inode *inode)
206 {
207  return (struct ext4_extent_header *) EXT4_I(inode)->i_data;
208 }
209 
210 static inline struct ext4_extent_header *ext_block_hdr(struct buffer_head *bh)
211 {
212  return (struct ext4_extent_header *) bh->b_data;
213 }
214 
215 static inline unsigned short ext_depth(struct inode *inode)
216 {
217  return le16_to_cpu(ext_inode_hdr(inode)->eh_depth);
218 }
219 
220 static inline void
221 ext4_ext_invalidate_cache(struct inode *inode)
222 {
223  EXT4_I(inode)->i_cached_extent.ec_len = 0;
224 }
225 
226 static inline void ext4_ext_mark_uninitialized(struct ext4_extent *ext)
227 {
228  /* We can not have an uninitialized extent of zero length! */
229  BUG_ON((le16_to_cpu(ext->ee_len) & ~EXT_INIT_MAX_LEN) == 0);
231 }
232 
233 static inline int ext4_ext_is_uninitialized(struct ext4_extent *ext)
234 {
235  /* Extent with ee_len of 0x8000 is treated as an initialized extent */
236  return (le16_to_cpu(ext->ee_len) > EXT_INIT_MAX_LEN);
237 }
238 
239 static inline int ext4_ext_get_actual_len(struct ext4_extent *ext)
240 {
241  return (le16_to_cpu(ext->ee_len) <= EXT_INIT_MAX_LEN ?
242  le16_to_cpu(ext->ee_len) :
244 }
245 
246 static inline void ext4_ext_mark_initialized(struct ext4_extent *ext)
247 {
248  ext->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ext));
249 }
250 
251 /*
252  * ext4_ext_pblock:
253  * combine low and high parts of physical block number into ext4_fsblk_t
254  */
255 static inline ext4_fsblk_t ext4_ext_pblock(struct ext4_extent *ex)
256 {
258 
259  block = le32_to_cpu(ex->ee_start_lo);
260  block |= ((ext4_fsblk_t) le16_to_cpu(ex->ee_start_hi) << 31) << 1;
261  return block;
262 }
263 
264 /*
265  * ext4_idx_pblock:
266  * combine low and high parts of a leaf physical block number into ext4_fsblk_t
267  */
268 static inline ext4_fsblk_t ext4_idx_pblock(struct ext4_extent_idx *ix)
269 {
271 
272  block = le32_to_cpu(ix->ei_leaf_lo);
273  block |= ((ext4_fsblk_t) le16_to_cpu(ix->ei_leaf_hi) << 31) << 1;
274  return block;
275 }
276 
277 /*
278  * ext4_ext_store_pblock:
279  * stores a large physical block number into an extent struct,
280  * breaking it into parts
281  */
282 static inline void ext4_ext_store_pblock(struct ext4_extent *ex,
283  ext4_fsblk_t pb)
284 {
285  ex->ee_start_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
286  ex->ee_start_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) &
287  0xffff);
288 }
289 
290 /*
291  * ext4_idx_store_pblock:
292  * stores a large physical block number into an index struct,
293  * breaking it into parts
294  */
295 static inline void ext4_idx_store_pblock(struct ext4_extent_idx *ix,
296  ext4_fsblk_t pb)
297 {
298  ix->ei_leaf_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
299  ix->ei_leaf_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) &
300  0xffff);
301 }
302 
303 extern int ext4_ext_calc_metadata_amount(struct inode *inode,
304  ext4_lblk_t lblocks);
305 extern int ext4_extent_tree_init(handle_t *, struct inode *);
306 extern int ext4_ext_calc_credits_for_single_extent(struct inode *inode,
307  int num,
308  struct ext4_ext_path *path);
309 extern int ext4_can_extents_be_merged(struct inode *inode,
310  struct ext4_extent *ex1,
311  struct ext4_extent *ex2);
312 extern int ext4_ext_insert_extent(handle_t *, struct inode *, struct ext4_ext_path *, struct ext4_extent *, int);
313 extern struct ext4_ext_path *ext4_ext_find_extent(struct inode *, ext4_lblk_t,
314  struct ext4_ext_path *);
315 extern void ext4_ext_drop_refs(struct ext4_ext_path *);
316 extern int ext4_ext_check_inode(struct inode *inode);
317 extern int ext4_find_delalloc_cluster(struct inode *inode, ext4_lblk_t lblk,
318  int search_hint_reverse);
319 #endif /* _EXT4_EXTENTS */
320