Branch data     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                 :          0 :         return (struct ext4_extent_tail *)(((void *)eh) +
     104                 :          0 :                                            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                 :            :                                         : 0)
     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)) : 0)
     180                 :            : 
     181                 :            : static inline struct ext4_extent_header *ext_inode_hdr(struct inode *inode)
     182                 :            : {
     183                 :          3 :         return (struct ext4_extent_header *) EXT4_I(inode)->i_data;
     184                 :            : }
     185                 :            : 
     186                 :            : static inline struct ext4_extent_header *ext_block_hdr(struct buffer_head *bh)
     187                 :            : {
     188                 :          3 :         return (struct ext4_extent_header *) bh->b_data;
     189                 :            : }
     190                 :            : 
     191                 :            : static inline unsigned short ext_depth(struct inode *inode)
     192                 :            : {
     193                 :          3 :         return le16_to_cpu(ext_inode_hdr(inode)->eh_depth);
     194                 :            : }
     195                 :            : 
     196                 :          3 : static inline void ext4_ext_mark_unwritten(struct ext4_extent *ext)
     197                 :            : {
     198                 :            :         /* We can not have an unwritten extent of zero length! */
     199                 :          3 :         BUG_ON((le16_to_cpu(ext->ee_len) & ~EXT_INIT_MAX_LEN) == 0);
     200                 :          3 :         ext->ee_len |= cpu_to_le16(EXT_INIT_MAX_LEN);
     201                 :          3 : }
     202                 :            : 
     203                 :            : static inline int ext4_ext_is_unwritten(struct ext4_extent *ext)
     204                 :            : {
     205                 :            :         /* Extent with ee_len of 0x8000 is treated as an initialized extent */
     206                 :          3 :         return (le16_to_cpu(ext->ee_len) > EXT_INIT_MAX_LEN);
     207                 :            : }
     208                 :            : 
     209                 :            : static inline int ext4_ext_get_actual_len(struct ext4_extent *ext)
     210                 :            : {
     211                 :          3 :         return (le16_to_cpu(ext->ee_len) <= EXT_INIT_MAX_LEN ?
     212                 :            :                 le16_to_cpu(ext->ee_len) :
     213                 :          3 :                 (le16_to_cpu(ext->ee_len) - EXT_INIT_MAX_LEN));
     214                 :            : }
     215                 :            : 
     216                 :            : static inline void ext4_ext_mark_initialized(struct ext4_extent *ext)
     217                 :            : {
     218                 :          3 :         ext->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ext));
     219                 :            : }
     220                 :            : 
     221                 :            : /*
     222                 :            :  * ext4_ext_pblock:
     223                 :            :  * combine low and high parts of physical block number into ext4_fsblk_t
     224                 :            :  */
     225                 :            : static inline ext4_fsblk_t ext4_ext_pblock(struct ext4_extent *ex)
     226                 :            : {
     227                 :            :         ext4_fsblk_t block;
     228                 :            : 
     229                 :          3 :         block = le32_to_cpu(ex->ee_start_lo);
     230                 :          3 :         block |= ((ext4_fsblk_t) le16_to_cpu(ex->ee_start_hi) << 31) << 1;
     231                 :            :         return block;
     232                 :            : }
     233                 :            : 
     234                 :            : /*
     235                 :            :  * ext4_idx_pblock:
     236                 :            :  * combine low and high parts of a leaf physical block number into ext4_fsblk_t
     237                 :            :  */
     238                 :            : static inline ext4_fsblk_t ext4_idx_pblock(struct ext4_extent_idx *ix)
     239                 :            : {
     240                 :            :         ext4_fsblk_t block;
     241                 :            : 
     242                 :          3 :         block = le32_to_cpu(ix->ei_leaf_lo);
     243                 :          3 :         block |= ((ext4_fsblk_t) le16_to_cpu(ix->ei_leaf_hi) << 31) << 1;
     244                 :            :         return block;
     245                 :            : }
     246                 :            : 
     247                 :            : /*
     248                 :            :  * ext4_ext_store_pblock:
     249                 :            :  * stores a large physical block number into an extent struct,
     250                 :            :  * breaking it into parts
     251                 :            :  */
     252                 :            : static inline void ext4_ext_store_pblock(struct ext4_extent *ex,
     253                 :            :                                          ext4_fsblk_t pb)
     254                 :            : {
     255                 :          3 :         ex->ee_start_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
     256                 :          3 :         ex->ee_start_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) &
     257                 :            :                                       0xffff);
     258                 :            : }
     259                 :            : 
     260                 :            : /*
     261                 :            :  * ext4_idx_store_pblock:
     262                 :            :  * stores a large physical block number into an index struct,
     263                 :            :  * breaking it into parts
     264                 :            :  */
     265                 :            : static inline void ext4_idx_store_pblock(struct ext4_extent_idx *ix,
     266                 :            :                                          ext4_fsblk_t pb)
     267                 :            : {
     268                 :          3 :         ix->ei_leaf_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
     269                 :          3 :         ix->ei_leaf_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) &
     270                 :            :                                      0xffff);
     271                 :            : }
     272                 :            : 
     273                 :            : #define ext4_ext_dirty(handle, inode, path) \
     274                 :            :                 __ext4_ext_dirty(__func__, __LINE__, (handle), (inode), (path))
     275                 :            : int __ext4_ext_dirty(const char *where, unsigned int line, handle_t *handle,
     276                 :            :                      struct inode *inode, struct ext4_ext_path *path);
     277                 :            : 
     278                 :            : #endif /* _EXT4_EXTENTS */
     279                 :            :