lib/ext2fs/ext3_extents.h

   1 /*
   2  * Copyright (c) 2003,2004 Cluster File Systems, Inc, info@clusterfs.com
   3  * Written by Alex Tomas <alex@clusterfs.com>
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License version 2 as
   7  * published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public Licens
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-
  17  */
  18
  19 #ifndef _LINUX_EXT3_EXTENTS
  20 #define _LINUX_EXT3_EXTENTS
  21
  22 /*
  23  * with AGRESSIVE_TEST defined capacity of index/leaf blocks
  24  * become very little, so index split, in-depth growing and
  25  * other hard changes happens much more often
  26  * this is for debug purposes only
  27  */
  28 #define AGRESSIVE_TEST_
  29
  30 /*
  31  * if CHECK_BINSEARCH defined, then results of binary search
  32  * will be checked by linear search
  33  */
  34 #define CHECK_BINSEARCH_
  35
  36 /*
  37  * if EXT_DEBUG is defined you can use 'extdebug' mount option
  38  * to get lots of info what's going on
  39  */
  40 //#define EXT_DEBUG
  41 #ifdef EXT_DEBUG
  42 #define ext_debug(tree,fmt,a...)                        \
  43 do {                                                    \
  44         if (test_opt((tree)->inode->i_sb, EXTDEBUG))    \
  45                 printk(fmt, ##a);                       \
  46 } while (0);
  47 #else
  48 #define ext_debug(tree,fmt,a...)
  49 #endif
  50
  51 /*
  52  * if EXT_STATS is defined then stats numbers are collected
  53  * these number will be displayed at umount time
  54  */
  55 #define EXT_STATS_
  56
  57
  58 #define EXT3_ALLOC_NEEDED       3       /* block bitmap + group desc. + sb */
  59
  60 /*
  61  * ext3_inode has i_block array (total 60 bytes)
  62  * first 4 bytes are used to store:
  63  *  - tree depth (0 mean there is no tree yet. all extents in the inode)
  64  *  - number of alive extents in the inode
  65  */
  66
  67 /*
  68  * this is extent on-disk structure
  69  * it's used at the bottom of the tree
  70  */
  71 struct ext3_extent {
  72         __u32   ee_block;       /* first logical block extent covers */
  73         __u16   ee_len;         /* number of blocks covered by extent */
  74         __u16   ee_start_hi;    /* high 16 bits of physical block */
  75         __u32   ee_start;       /* low 32 bigs of physical block */
  76 };
  77
  78 /*
  79  * this is index on-disk structure
  80  * it's used at all the levels, but the bottom
  81  */
  82 struct ext3_extent_idx {
  83         __u32   ei_block;       /* index covers logical blocks from 'block' */
  84         __u32   ei_leaf;        /* pointer to the physical block of the next *
  85                                  * level. leaf or next index could bet here */
  86         __u16   ei_leaf_hi;     /* high 16 bits of physical block */
  87         __u16   ei_unused;
  88 };
  89
  90 /*
  91  * each block (leaves and indexes), even inode-stored has header
  92  */
  93 struct ext3_extent_header {
  94         __u16   eh_magic;       /* probably will support different formats */
  95         __u16   eh_entries;     /* number of valid entries */
  96         __u16   eh_max;         /* capacity of store in entries */
  97         __u16   eh_depth;       /* has tree real underlaying blocks? */
  98         __u32   eh_generation;  /* generation of the tree */
  99 };
 100
 101 #define EXT3_EXT_MAGIC          0xf30a
 102
 103 /*
 104  * array of ext3_ext_path contains path to some extent
 105  * creation/lookup routines use it for traversal/splitting/etc
 106  * truncate uses it to simulate recursive walking
 107  */
 108 struct ext3_ext_path {
 109         __u32                           p_block;
 110         __u16                           p_depth;
 111         struct ext3_extent              *p_ext;
 112         struct ext3_extent_idx          *p_idx;
 113         struct ext3_extent_header       *p_hdr;
 114         struct buffer_head              *p_bh;
 115 };
 116
 117 /*
 118  * structure for external API
 119  */
 120
 121 #define EXT_CONTINUE    0
 122 #define EXT_BREAK       1
 123 #define EXT_REPEAT      2
 124
 125
 126 #define EXT_MAX_BLOCK   0xffffffff
 127 #define EXT_CACHE_MARK  0xffff
 128
 129
 130 #define EXT_FIRST_EXTENT(__hdr__) \
 131         ((struct ext3_extent *) (((char *) (__hdr__)) +         \
 132                                  sizeof(struct ext3_extent_header)))
 133 #define EXT_FIRST_INDEX(__hdr__) \
 134         ((struct ext3_extent_idx *) (((char *) (__hdr__)) +     \
 135                                      sizeof(struct ext3_extent_header)))
 136 #define EXT_HAS_FREE_INDEX(__path__) \
 137         ((__path__)->p_hdr->eh_entries < (__path__)->p_hdr->eh_max)
 138 #define EXT_LAST_EXTENT(__hdr__) \
 139         (EXT_FIRST_EXTENT((__hdr__)) + (__hdr__)->eh_entries - 1)
 140 #define EXT_LAST_INDEX(__hdr__) \
 141         (EXT_FIRST_INDEX((__hdr__)) + (__hdr__)->eh_entries - 1)
 142 #define EXT_MAX_EXTENT(__hdr__) \
 143         (EXT_FIRST_EXTENT((__hdr__)) + (__hdr__)->eh_max - 1)
 144 #define EXT_MAX_INDEX(__hdr__) \
 145         (EXT_FIRST_INDEX((__hdr__)) + (__hdr__)->eh_max - 1)
 146
 147 #define EXT_ROOT_HDR(tree) \
 148         ((struct ext3_extent_header *) (tree)->root)
 149 #define EXT_BLOCK_HDR(bh) \
 150         ((struct ext3_extent_header *) (bh)->b_data)
 151 #define EXT_DEPTH(_t_)  \
 152         (((struct ext3_extent_header *)((_t_)->root))->eh_depth)
 153 #define EXT_GENERATION(_t_)     \
 154         (((struct ext3_extent_header *)((_t_)->root))->eh_generation)
 155
 156
 157 #define EXT_ASSERT(__x__) if (!(__x__)) BUG();
 158
 159
 160 /*
 161  * this structure is used to gather extents from the tree via ioctl
 162  */
 163 struct ext3_extent_buf {
 164         unsigned long start;
 165         int buflen;
 166         void *buffer;
 167         void *cur;
 168         int err;
 169 };
 170
 171 /*
 172  * this structure is used to collect stats info about the tree
 173  */
 174 struct ext3_extent_tree_stats {
 175         int depth;
 176         int extents_num;
 177         int leaf_num;
 178 };
 179
 180 #ifdef __KERNEL__
 181 /*
 182  * ext3_extents_tree is used to pass initial information
 183  * to top-level extents API
 184  */
 185 struct ext3_extents_helpers;
 186 struct ext3_extents_tree {
 187         struct inode *inode;    /* inode which tree belongs to */
 188         void *root;             /* ptr to data top of tree resides at */
 189         void *buffer;           /* will be passed as arg to ^^ routines */
 190         int buffer_len;
 191         void *private;
 192         struct ext3_extent *cex;/* last found extent */
 193         struct ext3_extents_helpers *ops;
 194 };
 195
 196 struct ext3_extents_helpers {
 197         int (*get_write_access)(handle_t *h, void *buffer);
 198         int (*mark_buffer_dirty)(handle_t *h, void *buffer);
 199         int (*mergable)(struct ext3_extent *ex1, struct ext3_extent *ex2);
 200         int (*remove_extent_credits)(struct ext3_extents_tree *,
 201                                         struct ext3_extent *, unsigned long,
 202                                         unsigned long);
 203         int (*remove_extent)(struct ext3_extents_tree *,
 204                                 struct ext3_extent *, unsigned long,
 205                                 unsigned long);
 206         int (*new_block)(handle_t *, struct ext3_extents_tree *,
 207                                 struct ext3_ext_path *, struct ext3_extent *,
 208                                 int *);
 209 };
 210
 211 /*
 212  * to be called by ext3_ext_walk_space()
 213  * negative retcode - error
 214  * positive retcode - signal for ext3_ext_walk_space(), see below
 215  * callback must return valid extent (passed or newly created)
 216  */
 217 typedef int (*ext_prepare_callback)(struct ext3_extents_tree *,
 218                                         struct ext3_ext_path *,
 219                                         struct ext3_extent *, int);
 220 void ext3_init_tree_desc(struct ext3_extents_tree *, struct inode *);
 221 extern int ext3_extent_tree_init(handle_t *, struct ext3_extents_tree *);
 222 extern int ext3_ext_calc_credits_for_insert(struct ext3_extents_tree *, struct ext3_ext_path *);
 223 extern int ext3_ext_insert_extent(handle_t *, struct ext3_extents_tree *, struct ext3_ext_path *, struct ext3_extent *);
 224 extern int ext3_ext_walk_space(struct ext3_extents_tree *, unsigned long, unsigned long, ext_prepare_callback);
 225 extern int ext3_ext_remove_space(struct ext3_extents_tree *, unsigned long, unsigned long);
 226 extern struct ext3_ext_path * ext3_ext_find_extent(struct ext3_extents_tree *, int, struct ext3_ext_path *);
 227
 228 static inline void
 229 ext3_ext_invalidate_cache(struct ext3_extents_tree *tree)
 230 {
 231         if (tree->cex)
 232                 tree->cex->ee_len = 0;
 233 }
 234 #endif /* __KERNEL__ */
 235
 236
 237 #endif /* _LINUX_EXT3_EXTENTS */
 238