1f5166768STheodore Ts'o // SPDX-License-Identifier: GPL-2.0
23dcf5451SChristoph Hellwig /*
33dcf5451SChristoph Hellwig * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
43dcf5451SChristoph Hellwig * Written by Alex Tomas <alex@clusterfs.com>
53dcf5451SChristoph Hellwig */
63dcf5451SChristoph Hellwig
73dcf5451SChristoph Hellwig #ifndef _EXT4_EXTENTS
83dcf5451SChristoph Hellwig #define _EXT4_EXTENTS
93dcf5451SChristoph Hellwig
103dcf5451SChristoph Hellwig #include "ext4.h"
113dcf5451SChristoph Hellwig
123dcf5451SChristoph Hellwig /*
133dcf5451SChristoph Hellwig * With AGGRESSIVE_TEST defined, the capacity of index/leaf blocks
143dcf5451SChristoph Hellwig * becomes very small, so index split, in-depth growing and
153dcf5451SChristoph Hellwig * other hard changes happen much more often.
163dcf5451SChristoph Hellwig * This is for debug purposes only.
173dcf5451SChristoph Hellwig */
183dcf5451SChristoph Hellwig #define AGGRESSIVE_TEST_
193dcf5451SChristoph Hellwig
203dcf5451SChristoph Hellwig /*
213dcf5451SChristoph Hellwig * With EXTENTS_STATS defined, the number of blocks and extents
223dcf5451SChristoph Hellwig * are collected in the truncate path. They'll be shown at
233dcf5451SChristoph Hellwig * umount time.
243dcf5451SChristoph Hellwig */
253dcf5451SChristoph Hellwig #define EXTENTS_STATS__
263dcf5451SChristoph Hellwig
273dcf5451SChristoph Hellwig /*
283dcf5451SChristoph Hellwig * If CHECK_BINSEARCH is defined, then the results of the binary search
293dcf5451SChristoph Hellwig * will also be checked by linear search.
303dcf5451SChristoph Hellwig */
313dcf5451SChristoph Hellwig #define CHECK_BINSEARCH__
323dcf5451SChristoph Hellwig
333dcf5451SChristoph Hellwig /*
343dcf5451SChristoph Hellwig * If EXT_STATS is defined then stats numbers are collected.
353dcf5451SChristoph Hellwig * These number will be displayed at umount time.
363dcf5451SChristoph Hellwig */
373dcf5451SChristoph Hellwig #define EXT_STATS_
383dcf5451SChristoph Hellwig
393dcf5451SChristoph Hellwig
403dcf5451SChristoph Hellwig /*
413dcf5451SChristoph Hellwig * ext4_inode has i_block array (60 bytes total).
423dcf5451SChristoph Hellwig * The first 12 bytes store ext4_extent_header;
433dcf5451SChristoph Hellwig * the remainder stores an array of ext4_extent.
44e6153918SDarrick J. Wong * For non-inode extent blocks, ext4_extent_tail
45e6153918SDarrick J. Wong * follows the array.
463dcf5451SChristoph Hellwig */
473dcf5451SChristoph Hellwig
483dcf5451SChristoph Hellwig /*
49e6153918SDarrick J. Wong * This is the extent tail on-disk structure.
50e6153918SDarrick J. Wong * All other extent structures are 12 bytes long. It turns out that
51e6153918SDarrick J. Wong * block_size % 12 >= 4 for at least all powers of 2 greater than 512, which
52e6153918SDarrick J. Wong * covers all valid ext4 block sizes. Therefore, this tail structure can be
53e6153918SDarrick J. Wong * crammed into the end of the block without having to rebalance the tree.
54e6153918SDarrick J. Wong */
55e6153918SDarrick J. Wong struct ext4_extent_tail {
56e6153918SDarrick J. Wong __le32 et_checksum; /* crc32c(uuid+inum+extent_block) */
57e6153918SDarrick J. Wong };
58e6153918SDarrick J. Wong
59e6153918SDarrick J. Wong /*
603dcf5451SChristoph Hellwig * This is the extent on-disk structure.
613dcf5451SChristoph Hellwig * It's used at the bottom of the tree.
623dcf5451SChristoph Hellwig */
633dcf5451SChristoph Hellwig struct ext4_extent {
643dcf5451SChristoph Hellwig __le32 ee_block; /* first logical block extent covers */
653dcf5451SChristoph Hellwig __le16 ee_len; /* number of blocks covered by extent */
663dcf5451SChristoph Hellwig __le16 ee_start_hi; /* high 16 bits of physical block */
673dcf5451SChristoph Hellwig __le32 ee_start_lo; /* low 32 bits of physical block */
683dcf5451SChristoph Hellwig };
693dcf5451SChristoph Hellwig
703dcf5451SChristoph Hellwig /*
713dcf5451SChristoph Hellwig * This is index on-disk structure.
723dcf5451SChristoph Hellwig * It's used at all the levels except the bottom.
733dcf5451SChristoph Hellwig */
743dcf5451SChristoph Hellwig struct ext4_extent_idx {
753dcf5451SChristoph Hellwig __le32 ei_block; /* index covers logical blocks from 'block' */
763dcf5451SChristoph Hellwig __le32 ei_leaf_lo; /* pointer to the physical block of the next *
773dcf5451SChristoph Hellwig * level. leaf or next index could be there */
783dcf5451SChristoph Hellwig __le16 ei_leaf_hi; /* high 16 bits of physical block */
793dcf5451SChristoph Hellwig __u16 ei_unused;
803dcf5451SChristoph Hellwig };
813dcf5451SChristoph Hellwig
823dcf5451SChristoph Hellwig /*
833dcf5451SChristoph Hellwig * Each block (leaves and indexes), even inode-stored has header.
843dcf5451SChristoph Hellwig */
853dcf5451SChristoph Hellwig struct ext4_extent_header {
863dcf5451SChristoph Hellwig __le16 eh_magic; /* probably will support different formats */
873dcf5451SChristoph Hellwig __le16 eh_entries; /* number of valid entries */
883dcf5451SChristoph Hellwig __le16 eh_max; /* capacity of store in entries */
893dcf5451SChristoph Hellwig __le16 eh_depth; /* has tree real underlying blocks? */
903dcf5451SChristoph Hellwig __le32 eh_generation; /* generation of the tree */
913dcf5451SChristoph Hellwig };
923dcf5451SChristoph Hellwig
933dcf5451SChristoph Hellwig #define EXT4_EXT_MAGIC cpu_to_le16(0xf30a)
94bc890a60STheodore Ts'o #define EXT4_MAX_EXTENT_DEPTH 5
953dcf5451SChristoph Hellwig
967ac5990dSDarrick J. Wong #define EXT4_EXTENT_TAIL_OFFSET(hdr) \
977ac5990dSDarrick J. Wong (sizeof(struct ext4_extent_header) + \
987ac5990dSDarrick J. Wong (sizeof(struct ext4_extent) * le16_to_cpu((hdr)->eh_max)))
997ac5990dSDarrick J. Wong
1007ac5990dSDarrick J. Wong static inline struct ext4_extent_tail *
find_ext4_extent_tail(struct ext4_extent_header * eh)1017ac5990dSDarrick J. Wong find_ext4_extent_tail(struct ext4_extent_header *eh)
1027ac5990dSDarrick J. Wong {
1037ac5990dSDarrick J. Wong return (struct ext4_extent_tail *)(((void *)eh) +
1047ac5990dSDarrick J. Wong EXT4_EXTENT_TAIL_OFFSET(eh));
1057ac5990dSDarrick J. Wong }
1067ac5990dSDarrick J. Wong
1073dcf5451SChristoph Hellwig /*
1083dcf5451SChristoph Hellwig * Array of ext4_ext_path contains path to some extent.
1093dcf5451SChristoph Hellwig * Creation/lookup routines use it for traversal/splitting/etc.
1103dcf5451SChristoph Hellwig * Truncate uses it to simulate recursive walking.
1113dcf5451SChristoph Hellwig */
1123dcf5451SChristoph Hellwig struct ext4_ext_path {
1133dcf5451SChristoph Hellwig ext4_fsblk_t p_block;
1143dcf5451SChristoph Hellwig __u16 p_depth;
11510809df8STheodore Ts'o __u16 p_maxdepth;
1163dcf5451SChristoph Hellwig struct ext4_extent *p_ext;
1173dcf5451SChristoph Hellwig struct ext4_extent_idx *p_idx;
1183dcf5451SChristoph Hellwig struct ext4_extent_header *p_hdr;
1193dcf5451SChristoph Hellwig struct buffer_head *p_bh;
1203dcf5451SChristoph Hellwig };
1213dcf5451SChristoph Hellwig
1223dcf5451SChristoph Hellwig /*
1239fe67149SEric Whitney * Used to record a portion of a cluster found at the beginning or end
1249fe67149SEric Whitney * of an extent while traversing the extent tree during space removal.
1259fe67149SEric Whitney * A partial cluster may be removed if it does not contain blocks shared
1269fe67149SEric Whitney * with extents that aren't being deleted (tofree state). Otherwise,
1279fe67149SEric Whitney * it cannot be removed (nofree state).
1289fe67149SEric Whitney */
1299fe67149SEric Whitney struct partial_cluster {
1309fe67149SEric Whitney ext4_fsblk_t pclu; /* physical cluster number */
1319fe67149SEric Whitney ext4_lblk_t lblk; /* logical block number within logical cluster */
1329fe67149SEric Whitney enum {initial, tofree, nofree} state;
1339fe67149SEric Whitney };
1349fe67149SEric Whitney
1359fe67149SEric Whitney /*
1363dcf5451SChristoph Hellwig * structure for external API
1373dcf5451SChristoph Hellwig */
1383dcf5451SChristoph Hellwig
1396873fa0dSEric Sandeen /*
1403dcf5451SChristoph Hellwig * EXT_INIT_MAX_LEN is the maximum number of blocks we can have in an
1413dcf5451SChristoph Hellwig * initialized extent. This is 2^15 and not (2^16 - 1), since we use the
1423dcf5451SChristoph Hellwig * MSB of ee_len field in the extent datastructure to signify if this
143556615dcSLukas Czerner * particular extent is an initialized extent or an unwritten (i.e.
1443dcf5451SChristoph Hellwig * preallocated).
145556615dcSLukas Czerner * EXT_UNWRITTEN_MAX_LEN is the maximum number of blocks we can have in an
146556615dcSLukas Czerner * unwritten extent.
1473dcf5451SChristoph Hellwig * If ee_len is <= 0x8000, it is an initialized extent. Otherwise, it is an
148556615dcSLukas Czerner * unwritten one. In other words, if MSB of ee_len is set, it is an
149556615dcSLukas Czerner * unwritten extent with only one special scenario when ee_len = 0x8000.
150556615dcSLukas Czerner * In this case we can not have an unwritten extent of zero length and
1513dcf5451SChristoph Hellwig * thus we make it as a special case of initialized extent with 0x8000 length.
1523dcf5451SChristoph Hellwig * This way we get better extent-to-group alignment for initialized extents.
1533dcf5451SChristoph Hellwig * Hence, the maximum number of blocks we can have in an *initialized*
154556615dcSLukas Czerner * extent is 2^15 (32768) and in an *unwritten* extent is 2^15-1 (32767).
1553dcf5451SChristoph Hellwig */
1563dcf5451SChristoph Hellwig #define EXT_INIT_MAX_LEN (1UL << 15)
157556615dcSLukas Czerner #define EXT_UNWRITTEN_MAX_LEN (EXT_INIT_MAX_LEN - 1)
1583dcf5451SChristoph Hellwig
1593dcf5451SChristoph Hellwig
1603dcf5451SChristoph Hellwig #define EXT_FIRST_EXTENT(__hdr__) \
1613dcf5451SChristoph Hellwig ((struct ext4_extent *) (((char *) (__hdr__)) + \
1623dcf5451SChristoph Hellwig sizeof(struct ext4_extent_header)))
1633dcf5451SChristoph Hellwig #define EXT_FIRST_INDEX(__hdr__) \
1643dcf5451SChristoph Hellwig ((struct ext4_extent_idx *) (((char *) (__hdr__)) + \
1653dcf5451SChristoph Hellwig sizeof(struct ext4_extent_header)))
1663dcf5451SChristoph Hellwig #define EXT_HAS_FREE_INDEX(__path__) \
1673dcf5451SChristoph Hellwig (le16_to_cpu((__path__)->p_hdr->eh_entries) \
1683dcf5451SChristoph Hellwig < le16_to_cpu((__path__)->p_hdr->eh_max))
1693dcf5451SChristoph Hellwig #define EXT_LAST_EXTENT(__hdr__) \
1703dcf5451SChristoph Hellwig (EXT_FIRST_EXTENT((__hdr__)) + le16_to_cpu((__hdr__)->eh_entries) - 1)
1713dcf5451SChristoph Hellwig #define EXT_LAST_INDEX(__hdr__) \
1723dcf5451SChristoph Hellwig (EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_entries) - 1)
1733dcf5451SChristoph Hellwig #define EXT_MAX_EXTENT(__hdr__) \
174c36a71b4SHarshad Shirwadkar ((le16_to_cpu((__hdr__)->eh_max)) ? \
175c36a71b4SHarshad Shirwadkar ((EXT_FIRST_EXTENT((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1)) \
176*a5fda113STheodore Ts'o : NULL)
1773dcf5451SChristoph Hellwig #define EXT_MAX_INDEX(__hdr__) \
178c36a71b4SHarshad Shirwadkar ((le16_to_cpu((__hdr__)->eh_max)) ? \
179*a5fda113STheodore Ts'o ((EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1)) \
180*a5fda113STheodore Ts'o : NULL)
1813dcf5451SChristoph Hellwig
ext_inode_hdr(struct inode * inode)1823dcf5451SChristoph Hellwig static inline struct ext4_extent_header *ext_inode_hdr(struct inode *inode)
1833dcf5451SChristoph Hellwig {
1843dcf5451SChristoph Hellwig return (struct ext4_extent_header *) EXT4_I(inode)->i_data;
1853dcf5451SChristoph Hellwig }
1863dcf5451SChristoph Hellwig
ext_block_hdr(struct buffer_head * bh)1873dcf5451SChristoph Hellwig static inline struct ext4_extent_header *ext_block_hdr(struct buffer_head *bh)
1883dcf5451SChristoph Hellwig {
1893dcf5451SChristoph Hellwig return (struct ext4_extent_header *) bh->b_data;
1903dcf5451SChristoph Hellwig }
1913dcf5451SChristoph Hellwig
ext_depth(struct inode * inode)1923dcf5451SChristoph Hellwig static inline unsigned short ext_depth(struct inode *inode)
1933dcf5451SChristoph Hellwig {
1943dcf5451SChristoph Hellwig return le16_to_cpu(ext_inode_hdr(inode)->eh_depth);
1953dcf5451SChristoph Hellwig }
1963dcf5451SChristoph Hellwig
ext4_ext_mark_unwritten(struct ext4_extent * ext)197556615dcSLukas Czerner static inline void ext4_ext_mark_unwritten(struct ext4_extent *ext)
1983dcf5451SChristoph Hellwig {
199556615dcSLukas Czerner /* We can not have an unwritten extent of zero length! */
2003dcf5451SChristoph Hellwig BUG_ON((le16_to_cpu(ext->ee_len) & ~EXT_INIT_MAX_LEN) == 0);
2013dcf5451SChristoph Hellwig ext->ee_len |= cpu_to_le16(EXT_INIT_MAX_LEN);
2023dcf5451SChristoph Hellwig }
2033dcf5451SChristoph Hellwig
ext4_ext_is_unwritten(struct ext4_extent * ext)204556615dcSLukas Czerner static inline int ext4_ext_is_unwritten(struct ext4_extent *ext)
2053dcf5451SChristoph Hellwig {
2063dcf5451SChristoph Hellwig /* Extent with ee_len of 0x8000 is treated as an initialized extent */
2073dcf5451SChristoph Hellwig return (le16_to_cpu(ext->ee_len) > EXT_INIT_MAX_LEN);
2083dcf5451SChristoph Hellwig }
2093dcf5451SChristoph Hellwig
ext4_ext_get_actual_len(struct ext4_extent * ext)2103dcf5451SChristoph Hellwig static inline int ext4_ext_get_actual_len(struct ext4_extent *ext)
2113dcf5451SChristoph Hellwig {
2123dcf5451SChristoph Hellwig return (le16_to_cpu(ext->ee_len) <= EXT_INIT_MAX_LEN ?
2133dcf5451SChristoph Hellwig le16_to_cpu(ext->ee_len) :
2143dcf5451SChristoph Hellwig (le16_to_cpu(ext->ee_len) - EXT_INIT_MAX_LEN));
2153dcf5451SChristoph Hellwig }
2163dcf5451SChristoph Hellwig
ext4_ext_mark_initialized(struct ext4_extent * ext)2170031462bSMingming Cao static inline void ext4_ext_mark_initialized(struct ext4_extent *ext)
2180031462bSMingming Cao {
2190031462bSMingming Cao ext->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ext));
2200031462bSMingming Cao }
2210031462bSMingming Cao
222bf89d16fSTheodore Ts'o /*
223bf89d16fSTheodore Ts'o * ext4_ext_pblock:
224bf89d16fSTheodore Ts'o * combine low and high parts of physical block number into ext4_fsblk_t
225bf89d16fSTheodore Ts'o */
ext4_ext_pblock(struct ext4_extent * ex)226bf89d16fSTheodore Ts'o static inline ext4_fsblk_t ext4_ext_pblock(struct ext4_extent *ex)
227bf89d16fSTheodore Ts'o {
228bf89d16fSTheodore Ts'o ext4_fsblk_t block;
229bf89d16fSTheodore Ts'o
230bf89d16fSTheodore Ts'o block = le32_to_cpu(ex->ee_start_lo);
231bf89d16fSTheodore Ts'o block |= ((ext4_fsblk_t) le16_to_cpu(ex->ee_start_hi) << 31) << 1;
232bf89d16fSTheodore Ts'o return block;
233bf89d16fSTheodore Ts'o }
234bf89d16fSTheodore Ts'o
235bf89d16fSTheodore Ts'o /*
236bf89d16fSTheodore Ts'o * ext4_idx_pblock:
237bf89d16fSTheodore Ts'o * combine low and high parts of a leaf physical block number into ext4_fsblk_t
238bf89d16fSTheodore Ts'o */
ext4_idx_pblock(struct ext4_extent_idx * ix)239bf89d16fSTheodore Ts'o static inline ext4_fsblk_t ext4_idx_pblock(struct ext4_extent_idx *ix)
240bf89d16fSTheodore Ts'o {
241bf89d16fSTheodore Ts'o ext4_fsblk_t block;
242bf89d16fSTheodore Ts'o
243bf89d16fSTheodore Ts'o block = le32_to_cpu(ix->ei_leaf_lo);
244bf89d16fSTheodore Ts'o block |= ((ext4_fsblk_t) le16_to_cpu(ix->ei_leaf_hi) << 31) << 1;
245bf89d16fSTheodore Ts'o return block;
246bf89d16fSTheodore Ts'o }
247bf89d16fSTheodore Ts'o
248bf89d16fSTheodore Ts'o /*
249bf89d16fSTheodore Ts'o * ext4_ext_store_pblock:
250bf89d16fSTheodore Ts'o * stores a large physical block number into an extent struct,
251bf89d16fSTheodore Ts'o * breaking it into parts
252bf89d16fSTheodore Ts'o */
ext4_ext_store_pblock(struct ext4_extent * ex,ext4_fsblk_t pb)253bf89d16fSTheodore Ts'o static inline void ext4_ext_store_pblock(struct ext4_extent *ex,
254bf89d16fSTheodore Ts'o ext4_fsblk_t pb)
255bf89d16fSTheodore Ts'o {
256bf89d16fSTheodore Ts'o ex->ee_start_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
257bf89d16fSTheodore Ts'o ex->ee_start_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) &
258bf89d16fSTheodore Ts'o 0xffff);
259bf89d16fSTheodore Ts'o }
260bf89d16fSTheodore Ts'o
261bf89d16fSTheodore Ts'o /*
262bf89d16fSTheodore Ts'o * ext4_idx_store_pblock:
263bf89d16fSTheodore Ts'o * stores a large physical block number into an index struct,
264bf89d16fSTheodore Ts'o * breaking it into parts
265bf89d16fSTheodore Ts'o */
ext4_idx_store_pblock(struct ext4_extent_idx * ix,ext4_fsblk_t pb)266bf89d16fSTheodore Ts'o static inline void ext4_idx_store_pblock(struct ext4_extent_idx *ix,
267bf89d16fSTheodore Ts'o ext4_fsblk_t pb)
268bf89d16fSTheodore Ts'o {
269bf89d16fSTheodore Ts'o ix->ei_leaf_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
270bf89d16fSTheodore Ts'o ix->ei_leaf_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) &
271bf89d16fSTheodore Ts'o 0xffff);
272bf89d16fSTheodore Ts'o }
273bf89d16fSTheodore Ts'o
2743dcf5451SChristoph Hellwig #endif /* _EXT4_EXTENTS */
2753dcf5451SChristoph Hellwig
276