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 * 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)) \ 176c36a71b4SHarshad Shirwadkar : 0) 1773dcf5451SChristoph Hellwig #define EXT_MAX_INDEX(__hdr__) \ 178c36a71b4SHarshad Shirwadkar ((le16_to_cpu((__hdr__)->eh_max)) ? \ 179c36a71b4SHarshad Shirwadkar ((EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1)) : 0) 1803dcf5451SChristoph Hellwig 1813dcf5451SChristoph Hellwig static inline struct ext4_extent_header *ext_inode_hdr(struct inode *inode) 1823dcf5451SChristoph Hellwig { 1833dcf5451SChristoph Hellwig return (struct ext4_extent_header *) EXT4_I(inode)->i_data; 1843dcf5451SChristoph Hellwig } 1853dcf5451SChristoph Hellwig 1863dcf5451SChristoph Hellwig static inline struct ext4_extent_header *ext_block_hdr(struct buffer_head *bh) 1873dcf5451SChristoph Hellwig { 1883dcf5451SChristoph Hellwig return (struct ext4_extent_header *) bh->b_data; 1893dcf5451SChristoph Hellwig } 1903dcf5451SChristoph Hellwig 1913dcf5451SChristoph Hellwig static inline unsigned short ext_depth(struct inode *inode) 1923dcf5451SChristoph Hellwig { 1933dcf5451SChristoph Hellwig return le16_to_cpu(ext_inode_hdr(inode)->eh_depth); 1943dcf5451SChristoph Hellwig } 1953dcf5451SChristoph Hellwig 196556615dcSLukas Czerner static inline void ext4_ext_mark_unwritten(struct ext4_extent *ext) 1973dcf5451SChristoph Hellwig { 198556615dcSLukas Czerner /* We can not have an unwritten extent of zero length! */ 1993dcf5451SChristoph Hellwig BUG_ON((le16_to_cpu(ext->ee_len) & ~EXT_INIT_MAX_LEN) == 0); 2003dcf5451SChristoph Hellwig ext->ee_len |= cpu_to_le16(EXT_INIT_MAX_LEN); 2013dcf5451SChristoph Hellwig } 2023dcf5451SChristoph Hellwig 203556615dcSLukas Czerner static inline int ext4_ext_is_unwritten(struct ext4_extent *ext) 2043dcf5451SChristoph Hellwig { 2053dcf5451SChristoph Hellwig /* Extent with ee_len of 0x8000 is treated as an initialized extent */ 2063dcf5451SChristoph Hellwig return (le16_to_cpu(ext->ee_len) > EXT_INIT_MAX_LEN); 2073dcf5451SChristoph Hellwig } 2083dcf5451SChristoph Hellwig 2093dcf5451SChristoph Hellwig static inline int ext4_ext_get_actual_len(struct ext4_extent *ext) 2103dcf5451SChristoph Hellwig { 2113dcf5451SChristoph Hellwig return (le16_to_cpu(ext->ee_len) <= EXT_INIT_MAX_LEN ? 2123dcf5451SChristoph Hellwig le16_to_cpu(ext->ee_len) : 2133dcf5451SChristoph Hellwig (le16_to_cpu(ext->ee_len) - EXT_INIT_MAX_LEN)); 2143dcf5451SChristoph Hellwig } 2153dcf5451SChristoph Hellwig 2160031462bSMingming Cao static inline void ext4_ext_mark_initialized(struct ext4_extent *ext) 2170031462bSMingming Cao { 2180031462bSMingming Cao ext->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ext)); 2190031462bSMingming Cao } 2200031462bSMingming Cao 221bf89d16fSTheodore Ts'o /* 222bf89d16fSTheodore Ts'o * ext4_ext_pblock: 223bf89d16fSTheodore Ts'o * combine low and high parts of physical block number into ext4_fsblk_t 224bf89d16fSTheodore Ts'o */ 225bf89d16fSTheodore Ts'o static inline ext4_fsblk_t ext4_ext_pblock(struct ext4_extent *ex) 226bf89d16fSTheodore Ts'o { 227bf89d16fSTheodore Ts'o ext4_fsblk_t block; 228bf89d16fSTheodore Ts'o 229bf89d16fSTheodore Ts'o block = le32_to_cpu(ex->ee_start_lo); 230bf89d16fSTheodore Ts'o block |= ((ext4_fsblk_t) le16_to_cpu(ex->ee_start_hi) << 31) << 1; 231bf89d16fSTheodore Ts'o return block; 232bf89d16fSTheodore Ts'o } 233bf89d16fSTheodore Ts'o 234bf89d16fSTheodore Ts'o /* 235bf89d16fSTheodore Ts'o * ext4_idx_pblock: 236bf89d16fSTheodore Ts'o * combine low and high parts of a leaf physical block number into ext4_fsblk_t 237bf89d16fSTheodore Ts'o */ 238bf89d16fSTheodore Ts'o static inline ext4_fsblk_t ext4_idx_pblock(struct ext4_extent_idx *ix) 239bf89d16fSTheodore Ts'o { 240bf89d16fSTheodore Ts'o ext4_fsblk_t block; 241bf89d16fSTheodore Ts'o 242bf89d16fSTheodore Ts'o block = le32_to_cpu(ix->ei_leaf_lo); 243bf89d16fSTheodore Ts'o block |= ((ext4_fsblk_t) le16_to_cpu(ix->ei_leaf_hi) << 31) << 1; 244bf89d16fSTheodore Ts'o return block; 245bf89d16fSTheodore Ts'o } 246bf89d16fSTheodore Ts'o 247bf89d16fSTheodore Ts'o /* 248bf89d16fSTheodore Ts'o * ext4_ext_store_pblock: 249bf89d16fSTheodore Ts'o * stores a large physical block number into an extent struct, 250bf89d16fSTheodore Ts'o * breaking it into parts 251bf89d16fSTheodore Ts'o */ 252bf89d16fSTheodore Ts'o static inline void ext4_ext_store_pblock(struct ext4_extent *ex, 253bf89d16fSTheodore Ts'o ext4_fsblk_t pb) 254bf89d16fSTheodore Ts'o { 255bf89d16fSTheodore Ts'o ex->ee_start_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff)); 256bf89d16fSTheodore Ts'o ex->ee_start_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) & 257bf89d16fSTheodore Ts'o 0xffff); 258bf89d16fSTheodore Ts'o } 259bf89d16fSTheodore Ts'o 260bf89d16fSTheodore Ts'o /* 261bf89d16fSTheodore Ts'o * ext4_idx_store_pblock: 262bf89d16fSTheodore Ts'o * stores a large physical block number into an index struct, 263bf89d16fSTheodore Ts'o * breaking it into parts 264bf89d16fSTheodore Ts'o */ 265bf89d16fSTheodore Ts'o static inline void ext4_idx_store_pblock(struct ext4_extent_idx *ix, 266bf89d16fSTheodore Ts'o ext4_fsblk_t pb) 267bf89d16fSTheodore Ts'o { 268bf89d16fSTheodore Ts'o ix->ei_leaf_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff)); 269bf89d16fSTheodore Ts'o ix->ei_leaf_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) & 270bf89d16fSTheodore Ts'o 0xffff); 271bf89d16fSTheodore Ts'o } 272bf89d16fSTheodore Ts'o 2733dcf5451SChristoph Hellwig #endif /* _EXT4_EXTENTS */ 2743dcf5451SChristoph Hellwig 275