ext4_fs_extents.h 5.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198
  1. /*
  2. * Copyright (c) 2003-2006, 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. #ifndef _LINUX_EXT4_EXTENTS
  19. #define _LINUX_EXT4_EXTENTS
  20. #include <linux/ext4_fs.h>
  21. /*
  22. * With AGGRESSIVE_TEST defined, the capacity of index/leaf blocks
  23. * becomes very small, so index split, in-depth growing and
  24. * other hard changes happen much more often.
  25. * This is for debug purposes only.
  26. */
  27. #define AGGRESSIVE_TEST_
  28. /*
  29. * With EXTENTS_STATS defined, the number of blocks and extents
  30. * are collected in the truncate path. They'll be shown at
  31. * umount time.
  32. */
  33. #define EXTENTS_STATS__
  34. /*
  35. * If CHECK_BINSEARCH is defined, then the results of the binary search
  36. * will also be checked by linear search.
  37. */
  38. #define CHECK_BINSEARCH__
  39. /*
  40. * If EXT_DEBUG is defined you can use the 'extdebug' mount option
  41. * to get lots of info about what's going on.
  42. */
  43. #define EXT_DEBUG__
  44. #ifdef EXT_DEBUG
  45. #define ext_debug(a...) printk(a)
  46. #else
  47. #define ext_debug(a...)
  48. #endif
  49. /*
  50. * If EXT_STATS is defined then stats numbers are collected.
  51. * These number will be displayed at umount time.
  52. */
  53. #define EXT_STATS_
  54. /*
  55. * ext4_inode has i_block array (60 bytes total).
  56. * The first 12 bytes store ext4_extent_header;
  57. * the remainder stores an array of ext4_extent.
  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; /* low 32 bits of physical block */
  68. };
  69. /*
  70. * This is index on-disk structure.
  71. * It's used at all the levels except the bottom.
  72. */
  73. struct ext4_extent_idx {
  74. __le32 ei_block; /* index covers logical blocks from 'block' */
  75. __le32 ei_leaf; /* pointer to the physical block of the next *
  76. * level. leaf or next index could be there */
  77. __le16 ei_leaf_hi; /* high 16 bits of physical block */
  78. __u16 ei_unused;
  79. };
  80. /*
  81. * Each block (leaves and indexes), even inode-stored has header.
  82. */
  83. struct ext4_extent_header {
  84. __le16 eh_magic; /* probably will support different formats */
  85. __le16 eh_entries; /* number of valid entries */
  86. __le16 eh_max; /* capacity of store in entries */
  87. __le16 eh_depth; /* has tree real underlying blocks? */
  88. __le32 eh_generation; /* generation of the tree */
  89. };
  90. #define EXT4_EXT_MAGIC cpu_to_le16(0xf30a)
  91. /*
  92. * Array of ext4_ext_path contains path to some extent.
  93. * Creation/lookup routines use it for traversal/splitting/etc.
  94. * Truncate uses it to simulate recursive walking.
  95. */
  96. struct ext4_ext_path {
  97. ext4_fsblk_t p_block;
  98. __u16 p_depth;
  99. struct ext4_extent *p_ext;
  100. struct ext4_extent_idx *p_idx;
  101. struct ext4_extent_header *p_hdr;
  102. struct buffer_head *p_bh;
  103. };
  104. /*
  105. * structure for external API
  106. */
  107. #define EXT4_EXT_CACHE_NO 0
  108. #define EXT4_EXT_CACHE_GAP 1
  109. #define EXT4_EXT_CACHE_EXTENT 2
  110. /*
  111. * to be called by ext4_ext_walk_space()
  112. * negative retcode - error
  113. * positive retcode - signal for ext4_ext_walk_space(), see below
  114. * callback must return valid extent (passed or newly created)
  115. */
  116. typedef int (*ext_prepare_callback)(struct inode *, struct ext4_ext_path *,
  117. struct ext4_ext_cache *,
  118. void *);
  119. #define EXT_CONTINUE 0
  120. #define EXT_BREAK 1
  121. #define EXT_REPEAT 2
  122. #define EXT_MAX_BLOCK 0xffffffff
  123. #define EXT_MAX_LEN ((1UL << 15) - 1)
  124. #define EXT_FIRST_EXTENT(__hdr__) \
  125. ((struct ext4_extent *) (((char *) (__hdr__)) + \
  126. sizeof(struct ext4_extent_header)))
  127. #define EXT_FIRST_INDEX(__hdr__) \
  128. ((struct ext4_extent_idx *) (((char *) (__hdr__)) + \
  129. sizeof(struct ext4_extent_header)))
  130. #define EXT_HAS_FREE_INDEX(__path__) \
  131. (le16_to_cpu((__path__)->p_hdr->eh_entries) \
  132. < le16_to_cpu((__path__)->p_hdr->eh_max))
  133. #define EXT_LAST_EXTENT(__hdr__) \
  134. (EXT_FIRST_EXTENT((__hdr__)) + le16_to_cpu((__hdr__)->eh_entries) - 1)
  135. #define EXT_LAST_INDEX(__hdr__) \
  136. (EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_entries) - 1)
  137. #define EXT_MAX_EXTENT(__hdr__) \
  138. (EXT_FIRST_EXTENT((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1)
  139. #define EXT_MAX_INDEX(__hdr__) \
  140. (EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1)
  141. static inline struct ext4_extent_header *ext_inode_hdr(struct inode *inode)
  142. {
  143. return (struct ext4_extent_header *) EXT4_I(inode)->i_data;
  144. }
  145. static inline struct ext4_extent_header *ext_block_hdr(struct buffer_head *bh)
  146. {
  147. return (struct ext4_extent_header *) bh->b_data;
  148. }
  149. static inline unsigned short ext_depth(struct inode *inode)
  150. {
  151. return le16_to_cpu(ext_inode_hdr(inode)->eh_depth);
  152. }
  153. static inline void ext4_ext_tree_changed(struct inode *inode)
  154. {
  155. EXT4_I(inode)->i_ext_generation++;
  156. }
  157. static inline void
  158. ext4_ext_invalidate_cache(struct inode *inode)
  159. {
  160. EXT4_I(inode)->i_cached_extent.ec_type = EXT4_EXT_CACHE_NO;
  161. }
  162. extern int ext4_extent_tree_init(handle_t *, struct inode *);
  163. extern int ext4_ext_calc_credits_for_insert(struct inode *, struct ext4_ext_path *);
  164. extern int ext4_ext_insert_extent(handle_t *, struct inode *, struct ext4_ext_path *, struct ext4_extent *);
  165. extern int ext4_ext_walk_space(struct inode *, unsigned long, unsigned long, ext_prepare_callback, void *);
  166. extern struct ext4_ext_path * ext4_ext_find_extent(struct inode *, int, struct ext4_ext_path *);
  167. #endif /* _LINUX_EXT4_EXTENTS */