Line data    Source code

       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 *
     101             : find_ext4_extent_tail(struct ext4_extent_header *eh)
     102             : {
     103    14360991 :         return (struct ext4_extent_tail *)(((void *)eh) +
     104    14360991 :                                            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             : 
     182             : static inline struct ext4_extent_header *ext_inode_hdr(struct inode *inode)
     183             : {
     184    21892175 :         return (struct ext4_extent_header *) EXT4_I(inode)->i_data;
     185             : }
     186             : 
     187             : static inline struct ext4_extent_header *ext_block_hdr(struct buffer_head *bh)
     188             : {
     189    38495819 :         return (struct ext4_extent_header *) bh->b_data;
     190             : }
     191             : 
     192             : static inline unsigned short ext_depth(struct inode *inode)
     193             : {
     194   109130387 :         return le16_to_cpu(ext_inode_hdr(inode)->eh_depth);
     195             : }
     196             : 
     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    13119468 :         BUG_ON((le16_to_cpu(ext->ee_len) & ~EXT_INIT_MAX_LEN) == 0);
     201     2567121 :         ext->ee_len |= cpu_to_le16(EXT_INIT_MAX_LEN);
     202    10552347 : }
     203             : 
     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    42160389 :         return (le16_to_cpu(ext->ee_len) > EXT_INIT_MAX_LEN);
     208             : }
     209             : 
     210             : static inline int ext4_ext_get_actual_len(struct ext4_extent *ext)
     211             : {
     212    99701209 :         return (le16_to_cpu(ext->ee_len) <= EXT_INIT_MAX_LEN ?
     213    86095879 :                 le16_to_cpu(ext->ee_len) :
     214    54488491 :                 (le16_to_cpu(ext->ee_len) - EXT_INIT_MAX_LEN));
     215             : }
     216             : 
     217             : static inline void ext4_ext_mark_initialized(struct ext4_extent *ext)
     218             : {
     219     3311632 :         ext->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ext));
     220       24002 : }
     221             : 
     222             : /*
     223             :  * ext4_ext_pblock:
     224             :  * combine low and high parts of physical block number into ext4_fsblk_t
     225             :  */
     226             : static inline ext4_fsblk_t ext4_ext_pblock(struct ext4_extent *ex)
     227             : {
     228    71496977 :         ext4_fsblk_t block;
     229             : 
     230    71496977 :         block = le32_to_cpu(ex->ee_start_lo);
     231    71496977 :         block |= ((ext4_fsblk_t) le16_to_cpu(ex->ee_start_hi) << 31) << 1;
     232    62237576 :         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             :  */
     239             : static inline ext4_fsblk_t ext4_idx_pblock(struct ext4_extent_idx *ix)
     240             : {
     241    48232553 :         ext4_fsblk_t block;
     242             : 
     243    48232553 :         block = le32_to_cpu(ix->ei_leaf_lo);
     244    48232553 :         block |= ((ext4_fsblk_t) le16_to_cpu(ix->ei_leaf_hi) << 31) << 1;
     245    48232553 :         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             :  */
     253             : static inline void ext4_ext_store_pblock(struct ext4_extent *ex,
     254             :                                          ext4_fsblk_t pb)
     255             : {
     256    15124808 :         ex->ee_start_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
     257    13033917 :         ex->ee_start_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) &
     258             :                                       0xffff);
     259     2090891 : }
     260             : 
     261             : /*
     262             :  * ext4_idx_store_pblock:
     263             :  * stores a large physical block number into an index struct,
     264             :  * breaking it into parts
     265             :  */
     266             : static inline void ext4_idx_store_pblock(struct ext4_extent_idx *ix,
     267             :                                          ext4_fsblk_t pb)
     268             : {
     269       68343 :         ix->ei_leaf_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
     270       68343 :         ix->ei_leaf_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) &
     271             :                                      0xffff);
     272             : }
     273             : 
     274             : #endif /* _EXT4_EXTENTS */
     275             :