13dcf5451SChristoph Hellwig /* 23dcf5451SChristoph Hellwig * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com 33dcf5451SChristoph Hellwig * Written by Alex Tomas <alex@clusterfs.com> 43dcf5451SChristoph Hellwig * 53dcf5451SChristoph Hellwig * This program is free software; you can redistribute it and/or modify 63dcf5451SChristoph Hellwig * it under the terms of the GNU General Public License version 2 as 73dcf5451SChristoph Hellwig * published by the Free Software Foundation. 83dcf5451SChristoph Hellwig * 93dcf5451SChristoph Hellwig * This program is distributed in the hope that it will be useful, 103dcf5451SChristoph Hellwig * but WITHOUT ANY WARRANTY; without even the implied warranty of 113dcf5451SChristoph Hellwig * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 123dcf5451SChristoph Hellwig * GNU General Public License for more details. 133dcf5451SChristoph Hellwig * 143dcf5451SChristoph Hellwig * You should have received a copy of the GNU General Public Licens 153dcf5451SChristoph Hellwig * along with this program; if not, write to the Free Software 163dcf5451SChristoph Hellwig * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111- 173dcf5451SChristoph Hellwig */ 183dcf5451SChristoph Hellwig 193dcf5451SChristoph Hellwig #ifndef _EXT4_EXTENTS 203dcf5451SChristoph Hellwig #define _EXT4_EXTENTS 213dcf5451SChristoph Hellwig 223dcf5451SChristoph Hellwig #include "ext4.h" 233dcf5451SChristoph Hellwig 243dcf5451SChristoph Hellwig /* 253dcf5451SChristoph Hellwig * With AGGRESSIVE_TEST defined, the capacity of index/leaf blocks 263dcf5451SChristoph Hellwig * becomes very small, so index split, in-depth growing and 273dcf5451SChristoph Hellwig * other hard changes happen much more often. 283dcf5451SChristoph Hellwig * This is for debug purposes only. 293dcf5451SChristoph Hellwig */ 303dcf5451SChristoph Hellwig #define AGGRESSIVE_TEST_ 313dcf5451SChristoph Hellwig 323dcf5451SChristoph Hellwig /* 333dcf5451SChristoph Hellwig * With EXTENTS_STATS defined, the number of blocks and extents 343dcf5451SChristoph Hellwig * are collected in the truncate path. They'll be shown at 353dcf5451SChristoph Hellwig * umount time. 363dcf5451SChristoph Hellwig */ 373dcf5451SChristoph Hellwig #define EXTENTS_STATS__ 383dcf5451SChristoph Hellwig 393dcf5451SChristoph Hellwig /* 403dcf5451SChristoph Hellwig * If CHECK_BINSEARCH is defined, then the results of the binary search 413dcf5451SChristoph Hellwig * will also be checked by linear search. 423dcf5451SChristoph Hellwig */ 433dcf5451SChristoph Hellwig #define CHECK_BINSEARCH__ 443dcf5451SChristoph Hellwig 453dcf5451SChristoph Hellwig /* 463dcf5451SChristoph Hellwig * If EXT_STATS is defined then stats numbers are collected. 473dcf5451SChristoph Hellwig * These number will be displayed at umount time. 483dcf5451SChristoph Hellwig */ 493dcf5451SChristoph Hellwig #define EXT_STATS_ 503dcf5451SChristoph Hellwig 513dcf5451SChristoph Hellwig 523dcf5451SChristoph Hellwig /* 533dcf5451SChristoph Hellwig * ext4_inode has i_block array (60 bytes total). 543dcf5451SChristoph Hellwig * The first 12 bytes store ext4_extent_header; 553dcf5451SChristoph Hellwig * the remainder stores an array of ext4_extent. 56e6153918SDarrick J. Wong * For non-inode extent blocks, ext4_extent_tail 57e6153918SDarrick J. Wong * follows the array. 583dcf5451SChristoph Hellwig */ 593dcf5451SChristoph Hellwig 603dcf5451SChristoph Hellwig /* 61e6153918SDarrick J. Wong * This is the extent tail on-disk structure. 62e6153918SDarrick J. Wong * All other extent structures are 12 bytes long. It turns out that 63e6153918SDarrick J. Wong * block_size % 12 >= 4 for at least all powers of 2 greater than 512, which 64e6153918SDarrick J. Wong * covers all valid ext4 block sizes. Therefore, this tail structure can be 65e6153918SDarrick J. Wong * crammed into the end of the block without having to rebalance the tree. 66e6153918SDarrick J. Wong */ 67e6153918SDarrick J. Wong struct ext4_extent_tail { 68e6153918SDarrick J. Wong __le32 et_checksum; /* crc32c(uuid+inum+extent_block) */ 69e6153918SDarrick J. Wong }; 70e6153918SDarrick J. Wong 71e6153918SDarrick J. Wong /* 723dcf5451SChristoph Hellwig * This is the extent on-disk structure. 733dcf5451SChristoph Hellwig * It's used at the bottom of the tree. 743dcf5451SChristoph Hellwig */ 753dcf5451SChristoph Hellwig struct ext4_extent { 763dcf5451SChristoph Hellwig __le32 ee_block; /* first logical block extent covers */ 773dcf5451SChristoph Hellwig __le16 ee_len; /* number of blocks covered by extent */ 783dcf5451SChristoph Hellwig __le16 ee_start_hi; /* high 16 bits of physical block */ 793dcf5451SChristoph Hellwig __le32 ee_start_lo; /* low 32 bits of physical block */ 803dcf5451SChristoph Hellwig }; 813dcf5451SChristoph Hellwig 823dcf5451SChristoph Hellwig /* 833dcf5451SChristoph Hellwig * This is index on-disk structure. 843dcf5451SChristoph Hellwig * It's used at all the levels except the bottom. 853dcf5451SChristoph Hellwig */ 863dcf5451SChristoph Hellwig struct ext4_extent_idx { 873dcf5451SChristoph Hellwig __le32 ei_block; /* index covers logical blocks from 'block' */ 883dcf5451SChristoph Hellwig __le32 ei_leaf_lo; /* pointer to the physical block of the next * 893dcf5451SChristoph Hellwig * level. leaf or next index could be there */ 903dcf5451SChristoph Hellwig __le16 ei_leaf_hi; /* high 16 bits of physical block */ 913dcf5451SChristoph Hellwig __u16 ei_unused; 923dcf5451SChristoph Hellwig }; 933dcf5451SChristoph Hellwig 943dcf5451SChristoph Hellwig /* 953dcf5451SChristoph Hellwig * Each block (leaves and indexes), even inode-stored has header. 963dcf5451SChristoph Hellwig */ 973dcf5451SChristoph Hellwig struct ext4_extent_header { 983dcf5451SChristoph Hellwig __le16 eh_magic; /* probably will support different formats */ 993dcf5451SChristoph Hellwig __le16 eh_entries; /* number of valid entries */ 1003dcf5451SChristoph Hellwig __le16 eh_max; /* capacity of store in entries */ 1013dcf5451SChristoph Hellwig __le16 eh_depth; /* has tree real underlying blocks? */ 1023dcf5451SChristoph Hellwig __le32 eh_generation; /* generation of the tree */ 1033dcf5451SChristoph Hellwig }; 1043dcf5451SChristoph Hellwig 1053dcf5451SChristoph Hellwig #define EXT4_EXT_MAGIC cpu_to_le16(0xf30a) 1063dcf5451SChristoph Hellwig 1077ac5990dSDarrick J. Wong #define EXT4_EXTENT_TAIL_OFFSET(hdr) \ 1087ac5990dSDarrick J. Wong (sizeof(struct ext4_extent_header) + \ 1097ac5990dSDarrick J. Wong (sizeof(struct ext4_extent) * le16_to_cpu((hdr)->eh_max))) 1107ac5990dSDarrick J. Wong 1117ac5990dSDarrick J. Wong static inline struct ext4_extent_tail * 1127ac5990dSDarrick J. Wong find_ext4_extent_tail(struct ext4_extent_header *eh) 1137ac5990dSDarrick J. Wong { 1147ac5990dSDarrick J. Wong return (struct ext4_extent_tail *)(((void *)eh) + 1157ac5990dSDarrick J. Wong EXT4_EXTENT_TAIL_OFFSET(eh)); 1167ac5990dSDarrick J. Wong } 1177ac5990dSDarrick J. Wong 1183dcf5451SChristoph Hellwig /* 1193dcf5451SChristoph Hellwig * Array of ext4_ext_path contains path to some extent. 1203dcf5451SChristoph Hellwig * Creation/lookup routines use it for traversal/splitting/etc. 1213dcf5451SChristoph Hellwig * Truncate uses it to simulate recursive walking. 1223dcf5451SChristoph Hellwig */ 1233dcf5451SChristoph Hellwig struct ext4_ext_path { 1243dcf5451SChristoph Hellwig ext4_fsblk_t p_block; 1253dcf5451SChristoph Hellwig __u16 p_depth; 1263dcf5451SChristoph Hellwig struct ext4_extent *p_ext; 1273dcf5451SChristoph Hellwig struct ext4_extent_idx *p_idx; 1283dcf5451SChristoph Hellwig struct ext4_extent_header *p_hdr; 1293dcf5451SChristoph Hellwig struct buffer_head *p_bh; 1303dcf5451SChristoph Hellwig }; 1313dcf5451SChristoph Hellwig 1323dcf5451SChristoph Hellwig /* 1333dcf5451SChristoph Hellwig * structure for external API 1343dcf5451SChristoph Hellwig */ 1353dcf5451SChristoph Hellwig 1366873fa0dSEric Sandeen /* 1373dcf5451SChristoph Hellwig * EXT_INIT_MAX_LEN is the maximum number of blocks we can have in an 1383dcf5451SChristoph Hellwig * initialized extent. This is 2^15 and not (2^16 - 1), since we use the 1393dcf5451SChristoph Hellwig * MSB of ee_len field in the extent datastructure to signify if this 140556615dcSLukas Czerner * particular extent is an initialized extent or an unwritten (i.e. 1413dcf5451SChristoph Hellwig * preallocated). 142556615dcSLukas Czerner * EXT_UNWRITTEN_MAX_LEN is the maximum number of blocks we can have in an 143556615dcSLukas Czerner * unwritten extent. 1443dcf5451SChristoph Hellwig * If ee_len is <= 0x8000, it is an initialized extent. Otherwise, it is an 145556615dcSLukas Czerner * unwritten one. In other words, if MSB of ee_len is set, it is an 146556615dcSLukas Czerner * unwritten extent with only one special scenario when ee_len = 0x8000. 147556615dcSLukas Czerner * In this case we can not have an unwritten extent of zero length and 1483dcf5451SChristoph Hellwig * thus we make it as a special case of initialized extent with 0x8000 length. 1493dcf5451SChristoph Hellwig * This way we get better extent-to-group alignment for initialized extents. 1503dcf5451SChristoph Hellwig * Hence, the maximum number of blocks we can have in an *initialized* 151556615dcSLukas Czerner * extent is 2^15 (32768) and in an *unwritten* extent is 2^15-1 (32767). 1523dcf5451SChristoph Hellwig */ 1533dcf5451SChristoph Hellwig #define EXT_INIT_MAX_LEN (1UL << 15) 154556615dcSLukas Czerner #define EXT_UNWRITTEN_MAX_LEN (EXT_INIT_MAX_LEN - 1) 1553dcf5451SChristoph Hellwig 1563dcf5451SChristoph Hellwig 1573dcf5451SChristoph Hellwig #define EXT_FIRST_EXTENT(__hdr__) \ 1583dcf5451SChristoph Hellwig ((struct ext4_extent *) (((char *) (__hdr__)) + \ 1593dcf5451SChristoph Hellwig sizeof(struct ext4_extent_header))) 1603dcf5451SChristoph Hellwig #define EXT_FIRST_INDEX(__hdr__) \ 1613dcf5451SChristoph Hellwig ((struct ext4_extent_idx *) (((char *) (__hdr__)) + \ 1623dcf5451SChristoph Hellwig sizeof(struct ext4_extent_header))) 1633dcf5451SChristoph Hellwig #define EXT_HAS_FREE_INDEX(__path__) \ 1643dcf5451SChristoph Hellwig (le16_to_cpu((__path__)->p_hdr->eh_entries) \ 1653dcf5451SChristoph Hellwig < le16_to_cpu((__path__)->p_hdr->eh_max)) 1663dcf5451SChristoph Hellwig #define EXT_LAST_EXTENT(__hdr__) \ 1673dcf5451SChristoph Hellwig (EXT_FIRST_EXTENT((__hdr__)) + le16_to_cpu((__hdr__)->eh_entries) - 1) 1683dcf5451SChristoph Hellwig #define EXT_LAST_INDEX(__hdr__) \ 1693dcf5451SChristoph Hellwig (EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_entries) - 1) 1703dcf5451SChristoph Hellwig #define EXT_MAX_EXTENT(__hdr__) \ 1713dcf5451SChristoph Hellwig (EXT_FIRST_EXTENT((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1) 1723dcf5451SChristoph Hellwig #define EXT_MAX_INDEX(__hdr__) \ 1733dcf5451SChristoph Hellwig (EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1) 1743dcf5451SChristoph Hellwig 1753dcf5451SChristoph Hellwig static inline struct ext4_extent_header *ext_inode_hdr(struct inode *inode) 1763dcf5451SChristoph Hellwig { 1773dcf5451SChristoph Hellwig return (struct ext4_extent_header *) EXT4_I(inode)->i_data; 1783dcf5451SChristoph Hellwig } 1793dcf5451SChristoph Hellwig 1803dcf5451SChristoph Hellwig static inline struct ext4_extent_header *ext_block_hdr(struct buffer_head *bh) 1813dcf5451SChristoph Hellwig { 1823dcf5451SChristoph Hellwig return (struct ext4_extent_header *) bh->b_data; 1833dcf5451SChristoph Hellwig } 1843dcf5451SChristoph Hellwig 1853dcf5451SChristoph Hellwig static inline unsigned short ext_depth(struct inode *inode) 1863dcf5451SChristoph Hellwig { 1873dcf5451SChristoph Hellwig return le16_to_cpu(ext_inode_hdr(inode)->eh_depth); 1883dcf5451SChristoph Hellwig } 1893dcf5451SChristoph Hellwig 190556615dcSLukas Czerner static inline void ext4_ext_mark_unwritten(struct ext4_extent *ext) 1913dcf5451SChristoph Hellwig { 192556615dcSLukas Czerner /* We can not have an unwritten extent of zero length! */ 1933dcf5451SChristoph Hellwig BUG_ON((le16_to_cpu(ext->ee_len) & ~EXT_INIT_MAX_LEN) == 0); 1943dcf5451SChristoph Hellwig ext->ee_len |= cpu_to_le16(EXT_INIT_MAX_LEN); 1953dcf5451SChristoph Hellwig } 1963dcf5451SChristoph Hellwig 197556615dcSLukas Czerner static inline int ext4_ext_is_unwritten(struct ext4_extent *ext) 1983dcf5451SChristoph Hellwig { 1993dcf5451SChristoph Hellwig /* Extent with ee_len of 0x8000 is treated as an initialized extent */ 2003dcf5451SChristoph Hellwig return (le16_to_cpu(ext->ee_len) > EXT_INIT_MAX_LEN); 2013dcf5451SChristoph Hellwig } 2023dcf5451SChristoph Hellwig 2033dcf5451SChristoph Hellwig static inline int ext4_ext_get_actual_len(struct ext4_extent *ext) 2043dcf5451SChristoph Hellwig { 2053dcf5451SChristoph Hellwig return (le16_to_cpu(ext->ee_len) <= EXT_INIT_MAX_LEN ? 2063dcf5451SChristoph Hellwig le16_to_cpu(ext->ee_len) : 2073dcf5451SChristoph Hellwig (le16_to_cpu(ext->ee_len) - EXT_INIT_MAX_LEN)); 2083dcf5451SChristoph Hellwig } 2093dcf5451SChristoph Hellwig 2100031462bSMingming Cao static inline void ext4_ext_mark_initialized(struct ext4_extent *ext) 2110031462bSMingming Cao { 2120031462bSMingming Cao ext->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ext)); 2130031462bSMingming Cao } 2140031462bSMingming Cao 215bf89d16fSTheodore Ts'o /* 216bf89d16fSTheodore Ts'o * ext4_ext_pblock: 217bf89d16fSTheodore Ts'o * combine low and high parts of physical block number into ext4_fsblk_t 218bf89d16fSTheodore Ts'o */ 219bf89d16fSTheodore Ts'o static inline ext4_fsblk_t ext4_ext_pblock(struct ext4_extent *ex) 220bf89d16fSTheodore Ts'o { 221bf89d16fSTheodore Ts'o ext4_fsblk_t block; 222bf89d16fSTheodore Ts'o 223bf89d16fSTheodore Ts'o block = le32_to_cpu(ex->ee_start_lo); 224bf89d16fSTheodore Ts'o block |= ((ext4_fsblk_t) le16_to_cpu(ex->ee_start_hi) << 31) << 1; 225bf89d16fSTheodore Ts'o return block; 226bf89d16fSTheodore Ts'o } 227bf89d16fSTheodore Ts'o 228bf89d16fSTheodore Ts'o /* 229bf89d16fSTheodore Ts'o * ext4_idx_pblock: 230bf89d16fSTheodore Ts'o * combine low and high parts of a leaf physical block number into ext4_fsblk_t 231bf89d16fSTheodore Ts'o */ 232bf89d16fSTheodore Ts'o static inline ext4_fsblk_t ext4_idx_pblock(struct ext4_extent_idx *ix) 233bf89d16fSTheodore Ts'o { 234bf89d16fSTheodore Ts'o ext4_fsblk_t block; 235bf89d16fSTheodore Ts'o 236bf89d16fSTheodore Ts'o block = le32_to_cpu(ix->ei_leaf_lo); 237bf89d16fSTheodore Ts'o block |= ((ext4_fsblk_t) le16_to_cpu(ix->ei_leaf_hi) << 31) << 1; 238bf89d16fSTheodore Ts'o return block; 239bf89d16fSTheodore Ts'o } 240bf89d16fSTheodore Ts'o 241bf89d16fSTheodore Ts'o /* 242bf89d16fSTheodore Ts'o * ext4_ext_store_pblock: 243bf89d16fSTheodore Ts'o * stores a large physical block number into an extent struct, 244bf89d16fSTheodore Ts'o * breaking it into parts 245bf89d16fSTheodore Ts'o */ 246bf89d16fSTheodore Ts'o static inline void ext4_ext_store_pblock(struct ext4_extent *ex, 247bf89d16fSTheodore Ts'o ext4_fsblk_t pb) 248bf89d16fSTheodore Ts'o { 249bf89d16fSTheodore Ts'o ex->ee_start_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff)); 250bf89d16fSTheodore Ts'o ex->ee_start_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) & 251bf89d16fSTheodore Ts'o 0xffff); 252bf89d16fSTheodore Ts'o } 253bf89d16fSTheodore Ts'o 254bf89d16fSTheodore Ts'o /* 255bf89d16fSTheodore Ts'o * ext4_idx_store_pblock: 256bf89d16fSTheodore Ts'o * stores a large physical block number into an index struct, 257bf89d16fSTheodore Ts'o * breaking it into parts 258bf89d16fSTheodore Ts'o */ 259bf89d16fSTheodore Ts'o static inline void ext4_idx_store_pblock(struct ext4_extent_idx *ix, 260bf89d16fSTheodore Ts'o ext4_fsblk_t pb) 261bf89d16fSTheodore Ts'o { 262bf89d16fSTheodore Ts'o ix->ei_leaf_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff)); 263bf89d16fSTheodore Ts'o ix->ei_leaf_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) & 264bf89d16fSTheodore Ts'o 0xffff); 265bf89d16fSTheodore Ts'o } 266bf89d16fSTheodore Ts'o 2672656497bSDarrick J. Wong #define ext4_ext_dirty(handle, inode, path) \ 2682656497bSDarrick J. Wong __ext4_ext_dirty(__func__, __LINE__, (handle), (inode), (path)) 2692656497bSDarrick J. Wong int __ext4_ext_dirty(const char *where, unsigned int line, handle_t *handle, 2702656497bSDarrick J. Wong struct inode *inode, struct ext4_ext_path *path); 2712656497bSDarrick J. Wong 2723dcf5451SChristoph Hellwig #endif /* _EXT4_EXTENTS */ 2733dcf5451SChristoph Hellwig 274