1  // SPDX-License-Identifier: GPL-2.0
2  /*
3   * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
4   * Written by Alex Tomas <alex@clusterfs.com>
5   */
6  
7  #ifndef _EXT4_EXTENTS
8  #define _EXT4_EXTENTS
9  
10  #include "ext4.h"
11  
12  /*
13   * With AGGRESSIVE_TEST defined, the capacity of index/leaf blocks
14   * becomes very small, so index split, in-depth growing and
15   * other hard changes happen much more often.
16   * This is for debug purposes only.
17   */
18  #define AGGRESSIVE_TEST_
19  
20  /*
21   * With EXTENTS_STATS defined, the number of blocks and extents
22   * are collected in the truncate path. They'll be shown at
23   * umount time.
24   */
25  #define EXTENTS_STATS__
26  
27  /*
28   * If CHECK_BINSEARCH is defined, then the results of the binary search
29   * will also be checked by linear search.
30   */
31  #define CHECK_BINSEARCH__
32  
33  /*
34   * If EXT_STATS is defined then stats numbers are collected.
35   * These number will be displayed at umount time.
36   */
37  #define EXT_STATS_
38  
39  
40  /*
41   * ext4_inode has i_block array (60 bytes total).
42   * The first 12 bytes store ext4_extent_header;
43   * the remainder stores an array of ext4_extent.
44   * For non-inode extent blocks, ext4_extent_tail
45   * follows the array.
46   */
47  
48  /*
49   * This is the extent tail on-disk structure.
50   * All other extent structures are 12 bytes long.  It turns out that
51   * block_size % 12 >= 4 for at least all powers of 2 greater than 512, which
52   * covers all valid ext4 block sizes.  Therefore, this tail structure can be
53   * crammed into the end of the block without having to rebalance the tree.
54   */
55  struct ext4_extent_tail {
56  	__le32	et_checksum;	/* crc32c(uuid+inum+extent_block) */
57  };
58  
59  /*
60   * This is the extent on-disk structure.
61   * It's used at the bottom of the tree.
62   */
63  struct ext4_extent {
64  	__le32	ee_block;	/* first logical block extent covers */
65  	__le16	ee_len;		/* number of blocks covered by extent */
66  	__le16	ee_start_hi;	/* high 16 bits of physical block */
67  	__le32	ee_start_lo;	/* low 32 bits of physical block */
68  };
69  
70  /*
71   * This is index on-disk structure.
72   * It's used at all the levels except the bottom.
73   */
74  struct ext4_extent_idx {
75  	__le32	ei_block;	/* index covers logical blocks from 'block' */
76  	__le32	ei_leaf_lo;	/* pointer to the physical block of the next *
77  				 * level. leaf or next index could be there */
78  	__le16	ei_leaf_hi;	/* high 16 bits of physical block */
79  	__u16	ei_unused;
80  };
81  
82  /*
83   * Each block (leaves and indexes), even inode-stored has header.
84   */
85  struct ext4_extent_header {
86  	__le16	eh_magic;	/* probably will support different formats */
87  	__le16	eh_entries;	/* number of valid entries */
88  	__le16	eh_max;		/* capacity of store in entries */
89  	__le16	eh_depth;	/* has tree real underlying blocks? */
90  	__le32	eh_generation;	/* generation of the tree */
91  };
92  
93  #define EXT4_EXT_MAGIC		cpu_to_le16(0xf30a)
94  #define EXT4_MAX_EXTENT_DEPTH 5
95  
96  #define EXT4_EXTENT_TAIL_OFFSET(hdr) \
97  	(sizeof(struct ext4_extent_header) + \
98  	 (sizeof(struct ext4_extent) * le16_to_cpu((hdr)->eh_max)))
99  
100  static inline struct ext4_extent_tail *
find_ext4_extent_tail(struct ext4_extent_header * eh)101  find_ext4_extent_tail(struct ext4_extent_header *eh)
102  {
103  	return (struct ext4_extent_tail *)(((void *)eh) +
104  					   EXT4_EXTENT_TAIL_OFFSET(eh));
105  }
106  
107  /*
108   * Array of ext4_ext_path contains path to some extent.
109   * Creation/lookup routines use it for traversal/splitting/etc.
110   * Truncate uses it to simulate recursive walking.
111   */
112  struct ext4_ext_path {
113  	ext4_fsblk_t			p_block;
114  	__u16				p_depth;
115  	__u16				p_maxdepth;
116  	struct ext4_extent		*p_ext;
117  	struct ext4_extent_idx		*p_idx;
118  	struct ext4_extent_header	*p_hdr;
119  	struct buffer_head		*p_bh;
120  };
121  
122  /*
123   * Used to record a portion of a cluster found at the beginning or end
124   * of an extent while traversing the extent tree during space removal.
125   * A partial cluster may be removed if it does not contain blocks shared
126   * with extents that aren't being deleted (tofree state).  Otherwise,
127   * it cannot be removed (nofree state).
128   */
129  struct partial_cluster {
130  	ext4_fsblk_t pclu;  /* physical cluster number */
131  	ext4_lblk_t lblk;   /* logical block number within logical cluster */
132  	enum {initial, tofree, nofree} state;
133  };
134  
135  /*
136   * structure for external API
137   */
138  
139  /*
140   * EXT_INIT_MAX_LEN is the maximum number of blocks we can have in an
141   * initialized extent. This is 2^15 and not (2^16 - 1), since we use the
142   * MSB of ee_len field in the extent datastructure to signify if this
143   * particular extent is an initialized extent or an unwritten (i.e.
144   * preallocated).
145   * EXT_UNWRITTEN_MAX_LEN is the maximum number of blocks we can have in an
146   * unwritten extent.
147   * If ee_len is <= 0x8000, it is an initialized extent. Otherwise, it is an
148   * unwritten one. In other words, if MSB of ee_len is set, it is an
149   * unwritten extent with only one special scenario when ee_len = 0x8000.
150   * In this case we can not have an unwritten extent of zero length and
151   * thus we make it as a special case of initialized extent with 0x8000 length.
152   * This way we get better extent-to-group alignment for initialized extents.
153   * Hence, the maximum number of blocks we can have in an *initialized*
154   * extent is 2^15 (32768) and in an *unwritten* extent is 2^15-1 (32767).
155   */
156  #define EXT_INIT_MAX_LEN	(1UL << 15)
157  #define EXT_UNWRITTEN_MAX_LEN	(EXT_INIT_MAX_LEN - 1)
158  
159  
160  #define EXT_FIRST_EXTENT(__hdr__) \
161  	((struct ext4_extent *) (((char *) (__hdr__)) +		\
162  				 sizeof(struct ext4_extent_header)))
163  #define EXT_FIRST_INDEX(__hdr__) \
164  	((struct ext4_extent_idx *) (((char *) (__hdr__)) +	\
165  				     sizeof(struct ext4_extent_header)))
166  #define EXT_HAS_FREE_INDEX(__path__) \
167  	(le16_to_cpu((__path__)->p_hdr->eh_entries) \
168  				     < le16_to_cpu((__path__)->p_hdr->eh_max))
169  #define EXT_LAST_EXTENT(__hdr__) \
170  	(EXT_FIRST_EXTENT((__hdr__)) + le16_to_cpu((__hdr__)->eh_entries) - 1)
171  #define EXT_LAST_INDEX(__hdr__) \
172  	(EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_entries) - 1)
173  #define EXT_MAX_EXTENT(__hdr__)	\
174  	((le16_to_cpu((__hdr__)->eh_max)) ? \
175  	((EXT_FIRST_EXTENT((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1)) \
176  					: NULL)
177  #define EXT_MAX_INDEX(__hdr__) \
178  	((le16_to_cpu((__hdr__)->eh_max)) ? \
179  	((EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1)) \
180  					: NULL)
181  
ext_inode_hdr(struct inode * inode)182  static inline struct ext4_extent_header *ext_inode_hdr(struct inode *inode)
183  {
184  	return (struct ext4_extent_header *) EXT4_I(inode)->i_data;
185  }
186  
ext_block_hdr(struct buffer_head * bh)187  static inline struct ext4_extent_header *ext_block_hdr(struct buffer_head *bh)
188  {
189  	return (struct ext4_extent_header *) bh->b_data;
190  }
191  
ext_depth(struct inode * inode)192  static inline unsigned short ext_depth(struct inode *inode)
193  {
194  	return le16_to_cpu(ext_inode_hdr(inode)->eh_depth);
195  }
196  
ext4_ext_mark_unwritten(struct ext4_extent * ext)197  static inline void ext4_ext_mark_unwritten(struct ext4_extent *ext)
198  {
199  	/* We can not have an unwritten extent of zero length! */
200  	BUG_ON((le16_to_cpu(ext->ee_len) & ~EXT_INIT_MAX_LEN) == 0);
201  	ext->ee_len |= cpu_to_le16(EXT_INIT_MAX_LEN);
202  }
203  
ext4_ext_is_unwritten(struct ext4_extent * ext)204  static inline int ext4_ext_is_unwritten(struct ext4_extent *ext)
205  {
206  	/* Extent with ee_len of 0x8000 is treated as an initialized extent */
207  	return (le16_to_cpu(ext->ee_len) > EXT_INIT_MAX_LEN);
208  }
209  
ext4_ext_get_actual_len(struct ext4_extent * ext)210  static inline int ext4_ext_get_actual_len(struct ext4_extent *ext)
211  {
212  	return (le16_to_cpu(ext->ee_len) <= EXT_INIT_MAX_LEN ?
213  		le16_to_cpu(ext->ee_len) :
214  		(le16_to_cpu(ext->ee_len) - EXT_INIT_MAX_LEN));
215  }
216  
ext4_ext_mark_initialized(struct ext4_extent * ext)217  static inline void ext4_ext_mark_initialized(struct ext4_extent *ext)
218  {
219  	ext->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ext));
220  }
221  
222  /*
223   * ext4_ext_pblock:
224   * combine low and high parts of physical block number into ext4_fsblk_t
225   */
ext4_ext_pblock(struct ext4_extent * ex)226  static inline ext4_fsblk_t ext4_ext_pblock(struct ext4_extent *ex)
227  {
228  	ext4_fsblk_t block;
229  
230  	block = le32_to_cpu(ex->ee_start_lo);
231  	block |= ((ext4_fsblk_t) le16_to_cpu(ex->ee_start_hi) << 31) << 1;
232  	return block;
233  }
234  
235  /*
236   * ext4_idx_pblock:
237   * combine low and high parts of a leaf physical block number into ext4_fsblk_t
238   */
ext4_idx_pblock(struct ext4_extent_idx * ix)239  static inline ext4_fsblk_t ext4_idx_pblock(struct ext4_extent_idx *ix)
240  {
241  	ext4_fsblk_t block;
242  
243  	block = le32_to_cpu(ix->ei_leaf_lo);
244  	block |= ((ext4_fsblk_t) le16_to_cpu(ix->ei_leaf_hi) << 31) << 1;
245  	return block;
246  }
247  
248  /*
249   * ext4_ext_store_pblock:
250   * stores a large physical block number into an extent struct,
251   * breaking it into parts
252   */
ext4_ext_store_pblock(struct ext4_extent * ex,ext4_fsblk_t pb)253  static inline void ext4_ext_store_pblock(struct ext4_extent *ex,
254  					 ext4_fsblk_t pb)
255  {
256  	ex->ee_start_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
257  	ex->ee_start_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) &
258  				      0xffff);
259  }
260  
261  /*
262   * ext4_idx_store_pblock:
263   * stores a large physical block number into an index struct,
264   * breaking it into parts
265   */
ext4_idx_store_pblock(struct ext4_extent_idx * ix,ext4_fsblk_t pb)266  static inline void ext4_idx_store_pblock(struct ext4_extent_idx *ix,
267  					 ext4_fsblk_t pb)
268  {
269  	ix->ei_leaf_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
270  	ix->ei_leaf_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) &
271  				     0xffff);
272  }
273  
274  #endif /* _EXT4_EXTENTS */
275  
276