Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 1 | /* |
| 2 | * fs/ext4/mballoc.h |
| 3 | * |
| 4 | * Written by: Alex Tomas <alex@clusterfs.com> |
| 5 | * |
| 6 | */ |
| 7 | #ifndef _EXT4_MBALLOC_H |
| 8 | #define _EXT4_MBALLOC_H |
| 9 | |
| 10 | #include <linux/time.h> |
| 11 | #include <linux/fs.h> |
| 12 | #include <linux/namei.h> |
| 13 | #include <linux/quotaops.h> |
| 14 | #include <linux/buffer_head.h> |
| 15 | #include <linux/module.h> |
| 16 | #include <linux/swap.h> |
| 17 | #include <linux/proc_fs.h> |
| 18 | #include <linux/pagemap.h> |
| 19 | #include <linux/seq_file.h> |
Theodore Ts'o | 8a0aba7 | 2008-10-16 10:06:27 -0400 | [diff] [blame] | 20 | #include <linux/blkdev.h> |
Aneesh Kumar K.V | 920313a | 2009-01-05 21:36:19 -0500 | [diff] [blame] | 21 | #include <linux/mutex.h> |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 22 | #include "ext4_jbd2.h" |
| 23 | #include "ext4.h" |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 24 | |
| 25 | /* |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 26 | */ |
Theodore Ts'o | 6ba495e | 2009-09-18 13:38:55 -0400 | [diff] [blame] | 27 | #ifdef CONFIG_EXT4_DEBUG |
Theodore Ts'o | a0b30c1 | 2013-02-09 16:28:20 -0500 | [diff] [blame] | 28 | extern ushort ext4_mballoc_debug; |
Theodore Ts'o | 6ba495e | 2009-09-18 13:38:55 -0400 | [diff] [blame] | 29 | |
Joe Perches | d74f3d2 | 2016-10-15 09:57:31 -0400 | [diff] [blame] | 30 | #define mb_debug(n, fmt, ...) \ |
| 31 | do { \ |
| 32 | if ((n) <= ext4_mballoc_debug) { \ |
| 33 | printk(KERN_DEBUG "(%s, %d): %s: " fmt, \ |
| 34 | __FILE__, __LINE__, __func__, ##__VA_ARGS__); \ |
| 35 | } \ |
| 36 | } while (0) |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 37 | #else |
Joe Perches | d74f3d2 | 2016-10-15 09:57:31 -0400 | [diff] [blame] | 38 | #define mb_debug(n, fmt, ...) no_printk(fmt, ##__VA_ARGS__) |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 39 | #endif |
| 40 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 41 | #define EXT4_MB_HISTORY_ALLOC 1 /* allocation */ |
| 42 | #define EXT4_MB_HISTORY_PREALLOC 2 /* preallocated blocks used */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 43 | |
| 44 | /* |
| 45 | * How long mballoc can look for a best extent (in found extents) |
| 46 | */ |
| 47 | #define MB_DEFAULT_MAX_TO_SCAN 200 |
| 48 | |
| 49 | /* |
| 50 | * How long mballoc must look for a best extent |
| 51 | */ |
| 52 | #define MB_DEFAULT_MIN_TO_SCAN 10 |
| 53 | |
| 54 | /* |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 55 | * with 'ext4_mb_stats' allocator will collect stats that will be |
| 56 | * shown at umount. The collecting costs though! |
| 57 | */ |
Theodore Ts'o | 90576c0 | 2009-09-29 15:51:30 -0400 | [diff] [blame] | 58 | #define MB_DEFAULT_STATS 0 |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 59 | |
| 60 | /* |
| 61 | * files smaller than MB_DEFAULT_STREAM_THRESHOLD are served |
| 62 | * by the stream allocator, which purpose is to pack requests |
| 63 | * as close each to other as possible to produce smooth I/O traffic |
| 64 | * We use locality group prealloc space for stream request. |
| 65 | * We can tune the same via /proc/fs/ext4/<parition>/stream_req |
| 66 | */ |
| 67 | #define MB_DEFAULT_STREAM_THRESHOLD 16 /* 64K */ |
| 68 | |
| 69 | /* |
| 70 | * for which requests use 2^N search using buddies |
| 71 | */ |
| 72 | #define MB_DEFAULT_ORDER2_REQS 2 |
| 73 | |
| 74 | /* |
| 75 | * default group prealloc size 512 blocks |
| 76 | */ |
| 77 | #define MB_DEFAULT_GROUP_PREALLOC 512 |
| 78 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 79 | |
Aneesh Kumar K.V | c894058 | 2008-10-16 10:14:27 -0400 | [diff] [blame] | 80 | struct ext4_free_data { |
Bobi Jam | 18aadd4 | 2012-02-20 17:53:02 -0500 | [diff] [blame] | 81 | /* MUST be the first member */ |
| 82 | struct ext4_journal_cb_entry efd_jce; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 83 | |
Bobi Jam | 18aadd4 | 2012-02-20 17:53:02 -0500 | [diff] [blame] | 84 | /* ext4_free_data private data starts from here */ |
| 85 | |
| 86 | /* this links the free block information from group_info */ |
| 87 | struct rb_node efd_node; |
Aneesh Kumar K.V | c894058 | 2008-10-16 10:14:27 -0400 | [diff] [blame] | 88 | |
| 89 | /* group which free block extent belongs */ |
Bobi Jam | 18aadd4 | 2012-02-20 17:53:02 -0500 | [diff] [blame] | 90 | ext4_group_t efd_group; |
Aneesh Kumar K.V | c894058 | 2008-10-16 10:14:27 -0400 | [diff] [blame] | 91 | |
| 92 | /* free block extent */ |
Bobi Jam | 18aadd4 | 2012-02-20 17:53:02 -0500 | [diff] [blame] | 93 | ext4_grpblk_t efd_start_cluster; |
| 94 | ext4_grpblk_t efd_count; |
Aneesh Kumar K.V | c894058 | 2008-10-16 10:14:27 -0400 | [diff] [blame] | 95 | |
| 96 | /* transaction which freed this extent */ |
Bobi Jam | 18aadd4 | 2012-02-20 17:53:02 -0500 | [diff] [blame] | 97 | tid_t efd_tid; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 98 | }; |
| 99 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 100 | struct ext4_prealloc_space { |
| 101 | struct list_head pa_inode_list; |
| 102 | struct list_head pa_group_list; |
| 103 | union { |
| 104 | struct list_head pa_tmp_list; |
| 105 | struct rcu_head pa_rcu; |
| 106 | } u; |
| 107 | spinlock_t pa_lock; |
| 108 | atomic_t pa_count; |
| 109 | unsigned pa_deleted; |
| 110 | ext4_fsblk_t pa_pstart; /* phys. block */ |
| 111 | ext4_lblk_t pa_lstart; /* log. block */ |
Eric Sandeen | a36b449 | 2009-08-25 22:36:45 -0400 | [diff] [blame] | 112 | ext4_grpblk_t pa_len; /* len of preallocated chunk */ |
| 113 | ext4_grpblk_t pa_free; /* how many blocks are free */ |
Aneesh Kumar K.V | cc0fb9a | 2009-03-27 17:16:58 -0400 | [diff] [blame] | 114 | unsigned short pa_type; /* pa type. inode or group */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 115 | spinlock_t *pa_obj_lock; |
| 116 | struct inode *pa_inode; /* hack, for history only */ |
| 117 | }; |
| 118 | |
Aneesh Kumar K.V | cc0fb9a | 2009-03-27 17:16:58 -0400 | [diff] [blame] | 119 | enum { |
| 120 | MB_INODE_PA = 0, |
| 121 | MB_GROUP_PA = 1 |
| 122 | }; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 123 | |
| 124 | struct ext4_free_extent { |
| 125 | ext4_lblk_t fe_logical; |
Theodore Ts'o | 53accfa | 2011-09-09 18:48:51 -0400 | [diff] [blame] | 126 | ext4_grpblk_t fe_start; /* In cluster units */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 127 | ext4_group_t fe_group; |
Theodore Ts'o | 53accfa | 2011-09-09 18:48:51 -0400 | [diff] [blame] | 128 | ext4_grpblk_t fe_len; /* In cluster units */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 129 | }; |
| 130 | |
| 131 | /* |
| 132 | * Locality group: |
| 133 | * we try to group all related changes together |
| 134 | * so that writeback can flush/allocate them together as well |
Aneesh Kumar K.V | 6be2ded | 2008-07-23 14:14:05 -0400 | [diff] [blame] | 135 | * Size of lg_prealloc_list hash is determined by MB_DEFAULT_GROUP_PREALLOC |
| 136 | * (512). We store prealloc space into the hash based on the pa_free blocks |
| 137 | * order value.ie, fls(pa_free)-1; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 138 | */ |
Aneesh Kumar K.V | 6be2ded | 2008-07-23 14:14:05 -0400 | [diff] [blame] | 139 | #define PREALLOC_TB_SIZE 10 |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 140 | struct ext4_locality_group { |
| 141 | /* for allocator */ |
Aneesh Kumar K.V | 6be2ded | 2008-07-23 14:14:05 -0400 | [diff] [blame] | 142 | /* to serialize allocates */ |
| 143 | struct mutex lg_mutex; |
| 144 | /* list of preallocations */ |
| 145 | struct list_head lg_prealloc_list[PREALLOC_TB_SIZE]; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 146 | spinlock_t lg_prealloc_lock; |
| 147 | }; |
| 148 | |
| 149 | struct ext4_allocation_context { |
| 150 | struct inode *ac_inode; |
| 151 | struct super_block *ac_sb; |
| 152 | |
| 153 | /* original request */ |
| 154 | struct ext4_free_extent ac_o_ex; |
| 155 | |
Coly Li | 58696f3 | 2011-02-24 14:10:00 -0500 | [diff] [blame] | 156 | /* goal request (normalized ac_o_ex) */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 157 | struct ext4_free_extent ac_g_ex; |
| 158 | |
| 159 | /* the best found extent */ |
| 160 | struct ext4_free_extent ac_b_ex; |
| 161 | |
Robin Dong | ff3fc17 | 2011-10-31 18:55:50 -0400 | [diff] [blame] | 162 | /* copy of the best found extent taken before preallocation efforts */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 163 | struct ext4_free_extent ac_f_ex; |
| 164 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 165 | __u16 ac_groups_scanned; |
| 166 | __u16 ac_found; |
| 167 | __u16 ac_tail; |
| 168 | __u16 ac_buddy; |
| 169 | __u16 ac_flags; /* allocation hints */ |
| 170 | __u8 ac_status; |
| 171 | __u8 ac_criteria; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 172 | __u8 ac_2order; /* if request is to allocate 2^N blocks and |
| 173 | * N > 0, the field stores N, otherwise 0 */ |
| 174 | __u8 ac_op; /* operation, for history only */ |
| 175 | struct page *ac_bitmap_page; |
| 176 | struct page *ac_buddy_page; |
| 177 | struct ext4_prealloc_space *ac_pa; |
| 178 | struct ext4_locality_group *ac_lg; |
| 179 | }; |
| 180 | |
| 181 | #define AC_STATUS_CONTINUE 1 |
| 182 | #define AC_STATUS_FOUND 2 |
| 183 | #define AC_STATUS_BREAK 3 |
| 184 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 185 | struct ext4_buddy { |
| 186 | struct page *bd_buddy_page; |
| 187 | void *bd_buddy; |
| 188 | struct page *bd_bitmap_page; |
| 189 | void *bd_bitmap; |
| 190 | struct ext4_group_info *bd_info; |
| 191 | struct super_block *bd_sb; |
| 192 | __u16 bd_blkbits; |
| 193 | ext4_group_t bd_group; |
| 194 | }; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 195 | |
Aneesh Kumar K.V | c3a326a | 2008-11-25 15:11:52 -0500 | [diff] [blame] | 196 | static inline ext4_fsblk_t ext4_grp_offs_to_block(struct super_block *sb, |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 197 | struct ext4_free_extent *fex) |
| 198 | { |
Theodore Ts'o | 3212a80 | 2011-09-09 18:46:51 -0400 | [diff] [blame] | 199 | return ext4_group_first_block_no(sb, fex->fe_group) + |
| 200 | (fex->fe_start << EXT4_SB(sb)->s_cluster_bits); |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 201 | } |
Darrick J. Wong | 0c9ec4b | 2017-04-30 00:36:53 -0400 | [diff] [blame] | 202 | |
| 203 | typedef int (*ext4_mballoc_query_range_fn)( |
| 204 | struct super_block *sb, |
| 205 | ext4_group_t agno, |
| 206 | ext4_grpblk_t start, |
| 207 | ext4_grpblk_t len, |
| 208 | void *priv); |
| 209 | |
| 210 | int |
| 211 | ext4_mballoc_query_range( |
| 212 | struct super_block *sb, |
| 213 | ext4_group_t agno, |
| 214 | ext4_grpblk_t start, |
| 215 | ext4_grpblk_t end, |
| 216 | ext4_mballoc_query_range_fn formatter, |
| 217 | void *priv); |
| 218 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 219 | #endif |