Theodore Ts'o | f516676 | 2017-12-17 22:00:59 -0500 | [diff] [blame] | 1 | // SPDX-License-Identifier: GPL-2.0 |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 2 | /* |
| 3 | * fs/ext4/mballoc.h |
| 4 | * |
| 5 | * Written by: Alex Tomas <alex@clusterfs.com> |
| 6 | * |
| 7 | */ |
| 8 | #ifndef _EXT4_MBALLOC_H |
| 9 | #define _EXT4_MBALLOC_H |
| 10 | |
| 11 | #include <linux/time.h> |
| 12 | #include <linux/fs.h> |
| 13 | #include <linux/namei.h> |
| 14 | #include <linux/quotaops.h> |
| 15 | #include <linux/buffer_head.h> |
| 16 | #include <linux/module.h> |
| 17 | #include <linux/swap.h> |
| 18 | #include <linux/proc_fs.h> |
| 19 | #include <linux/pagemap.h> |
| 20 | #include <linux/seq_file.h> |
Theodore Ts'o | 8a0aba7 | 2008-10-16 10:06:27 -0400 | [diff] [blame] | 21 | #include <linux/blkdev.h> |
Aneesh Kumar K.V | 920313a | 2009-01-05 21:36:19 -0500 | [diff] [blame] | 22 | #include <linux/mutex.h> |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 23 | #include "ext4_jbd2.h" |
| 24 | #include "ext4.h" |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 25 | |
| 26 | /* |
Ritesh Harjani | d3df145 | 2020-05-10 11:54:54 +0530 | [diff] [blame] | 27 | * mb_debug() dynamic printk msgs could be used to debug mballoc code. |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 28 | */ |
Theodore Ts'o | 6ba495e | 2009-09-18 13:38:55 -0400 | [diff] [blame] | 29 | #ifdef CONFIG_EXT4_DEBUG |
Ritesh Harjani | d3df145 | 2020-05-10 11:54:54 +0530 | [diff] [blame] | 30 | #define mb_debug(sb, fmt, ...) \ |
| 31 | pr_debug("[%s/%d] EXT4-fs (%s): (%s, %d): %s: " fmt, \ |
| 32 | current->comm, task_pid_nr(current), sb->s_id, \ |
| 33 | __FILE__, __LINE__, __func__, ##__VA_ARGS__) |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 34 | #else |
Ritesh Harjani | d3df145 | 2020-05-10 11:54:54 +0530 | [diff] [blame] | 35 | #define mb_debug(sb, fmt, ...) no_printk(fmt, ##__VA_ARGS__) |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 36 | #endif |
| 37 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 38 | #define EXT4_MB_HISTORY_ALLOC 1 /* allocation */ |
| 39 | #define EXT4_MB_HISTORY_PREALLOC 2 /* preallocated blocks used */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 40 | |
| 41 | /* |
| 42 | * How long mballoc can look for a best extent (in found extents) |
| 43 | */ |
| 44 | #define MB_DEFAULT_MAX_TO_SCAN 200 |
| 45 | |
| 46 | /* |
| 47 | * How long mballoc must look for a best extent |
| 48 | */ |
| 49 | #define MB_DEFAULT_MIN_TO_SCAN 10 |
| 50 | |
| 51 | /* |
Ritesh Harjani | 5730cce | 2023-05-30 18:03:41 +0530 | [diff] [blame] | 52 | * with 's_mb_stats' allocator will collect stats that will be |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 53 | * shown at umount. The collecting costs though! |
| 54 | */ |
Theodore Ts'o | 90576c0 | 2009-09-29 15:51:30 -0400 | [diff] [blame] | 55 | #define MB_DEFAULT_STATS 0 |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 56 | |
| 57 | /* |
| 58 | * files smaller than MB_DEFAULT_STREAM_THRESHOLD are served |
| 59 | * by the stream allocator, which purpose is to pack requests |
| 60 | * as close each to other as possible to produce smooth I/O traffic |
| 61 | * We use locality group prealloc space for stream request. |
Bhaskar Chowdhury | 3088e5a | 2021-03-27 16:00:05 +0530 | [diff] [blame] | 62 | * We can tune the same via /proc/fs/ext4/<partition>/stream_req |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 63 | */ |
| 64 | #define MB_DEFAULT_STREAM_THRESHOLD 16 /* 64K */ |
| 65 | |
| 66 | /* |
| 67 | * for which requests use 2^N search using buddies |
| 68 | */ |
| 69 | #define MB_DEFAULT_ORDER2_REQS 2 |
| 70 | |
| 71 | /* |
| 72 | * default group prealloc size 512 blocks |
| 73 | */ |
| 74 | #define MB_DEFAULT_GROUP_PREALLOC 512 |
| 75 | |
brookxu | 27bc446 | 2020-08-17 15:36:15 +0800 | [diff] [blame] | 76 | /* |
Harshad Shirwadkar | 196e402 | 2021-04-01 10:21:27 -0700 | [diff] [blame] | 77 | * Number of groups to search linearly before performing group scanning |
| 78 | * optimization. |
| 79 | */ |
| 80 | #define MB_DEFAULT_LINEAR_LIMIT 4 |
| 81 | |
| 82 | /* |
| 83 | * Minimum number of groups that should be present in the file system to perform |
| 84 | * group scanning optimizations. |
| 85 | */ |
| 86 | #define MB_DEFAULT_LINEAR_SCAN_THRESHOLD 16 |
| 87 | |
| 88 | /* |
Ojaswin Mujoo | f52f3d2 | 2023-05-30 18:03:50 +0530 | [diff] [blame] | 89 | * The maximum order upto which CR_BEST_AVAIL_LEN can trim a particular |
| 90 | * allocation request. Example, if we have an order 7 request and max trim order |
| 91 | * of 3, we can trim this request upto order 4. |
Ojaswin Mujoo | 7e17092 | 2023-05-30 18:03:49 +0530 | [diff] [blame] | 92 | */ |
Ojaswin Mujoo | f52f3d2 | 2023-05-30 18:03:50 +0530 | [diff] [blame] | 93 | #define MB_DEFAULT_BEST_AVAIL_TRIM_ORDER 3 |
Ojaswin Mujoo | 7e17092 | 2023-05-30 18:03:49 +0530 | [diff] [blame] | 94 | |
| 95 | /* |
Harshad Shirwadkar | 4b68f6d | 2021-04-01 10:21:26 -0700 | [diff] [blame] | 96 | * Number of valid buddy orders |
| 97 | */ |
| 98 | #define MB_NUM_ORDERS(sb) ((sb)->s_blocksize_bits + 2) |
| 99 | |
Aneesh Kumar K.V | c894058 | 2008-10-16 10:14:27 -0400 | [diff] [blame] | 100 | struct ext4_free_data { |
Daeho Jeong | a015434 | 2017-06-22 23:54:33 -0400 | [diff] [blame] | 101 | /* this links the free block information from sb_info */ |
| 102 | struct list_head efd_list; |
Bobi Jam | 18aadd4 | 2012-02-20 17:53:02 -0500 | [diff] [blame] | 103 | |
| 104 | /* this links the free block information from group_info */ |
| 105 | struct rb_node efd_node; |
Aneesh Kumar K.V | c894058 | 2008-10-16 10:14:27 -0400 | [diff] [blame] | 106 | |
| 107 | /* group which free block extent belongs */ |
Bobi Jam | 18aadd4 | 2012-02-20 17:53:02 -0500 | [diff] [blame] | 108 | ext4_group_t efd_group; |
Aneesh Kumar K.V | c894058 | 2008-10-16 10:14:27 -0400 | [diff] [blame] | 109 | |
| 110 | /* free block extent */ |
Bobi Jam | 18aadd4 | 2012-02-20 17:53:02 -0500 | [diff] [blame] | 111 | ext4_grpblk_t efd_start_cluster; |
| 112 | ext4_grpblk_t efd_count; |
Aneesh Kumar K.V | c894058 | 2008-10-16 10:14:27 -0400 | [diff] [blame] | 113 | |
| 114 | /* transaction which freed this extent */ |
Bobi Jam | 18aadd4 | 2012-02-20 17:53:02 -0500 | [diff] [blame] | 115 | tid_t efd_tid; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 116 | }; |
| 117 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 118 | struct ext4_prealloc_space { |
Ojaswin Mujoo | a8e38fd | 2023-03-25 13:43:40 +0530 | [diff] [blame] | 119 | union { |
Ojaswin Mujoo | 3872778 | 2023-03-25 13:43:41 +0530 | [diff] [blame] | 120 | struct rb_node inode_node; /* for inode PA rbtree */ |
Ojaswin Mujoo | a8e38fd | 2023-03-25 13:43:40 +0530 | [diff] [blame] | 121 | struct list_head lg_list; /* for lg PAs */ |
| 122 | } pa_node; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 123 | struct list_head pa_group_list; |
| 124 | union { |
| 125 | struct list_head pa_tmp_list; |
| 126 | struct rcu_head pa_rcu; |
| 127 | } u; |
| 128 | spinlock_t pa_lock; |
| 129 | atomic_t pa_count; |
| 130 | unsigned pa_deleted; |
| 131 | ext4_fsblk_t pa_pstart; /* phys. block */ |
| 132 | ext4_lblk_t pa_lstart; /* log. block */ |
Eric Sandeen | a36b449 | 2009-08-25 22:36:45 -0400 | [diff] [blame] | 133 | ext4_grpblk_t pa_len; /* len of preallocated chunk */ |
| 134 | ext4_grpblk_t pa_free; /* how many blocks are free */ |
Aneesh Kumar K.V | cc0fb9a | 2009-03-27 17:16:58 -0400 | [diff] [blame] | 135 | unsigned short pa_type; /* pa type. inode or group */ |
Ojaswin Mujoo | a8e38fd | 2023-03-25 13:43:40 +0530 | [diff] [blame] | 136 | union { |
Ojaswin Mujoo | 3872778 | 2023-03-25 13:43:41 +0530 | [diff] [blame] | 137 | rwlock_t *inode_lock; /* locks the rbtree holding this PA */ |
Ojaswin Mujoo | a8e38fd | 2023-03-25 13:43:40 +0530 | [diff] [blame] | 138 | spinlock_t *lg_lock; /* locks the lg list holding this PA */ |
| 139 | } pa_node_lock; |
Ojaswin Mujoo | 3872778 | 2023-03-25 13:43:41 +0530 | [diff] [blame] | 140 | struct inode *pa_inode; /* used to get the inode during group discard */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 141 | }; |
| 142 | |
Aneesh Kumar K.V | cc0fb9a | 2009-03-27 17:16:58 -0400 | [diff] [blame] | 143 | enum { |
| 144 | MB_INODE_PA = 0, |
| 145 | MB_GROUP_PA = 1 |
| 146 | }; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 147 | |
| 148 | struct ext4_free_extent { |
| 149 | ext4_lblk_t fe_logical; |
Theodore Ts'o | 53accfa | 2011-09-09 18:48:51 -0400 | [diff] [blame] | 150 | ext4_grpblk_t fe_start; /* In cluster units */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 151 | ext4_group_t fe_group; |
Theodore Ts'o | 53accfa | 2011-09-09 18:48:51 -0400 | [diff] [blame] | 152 | ext4_grpblk_t fe_len; /* In cluster units */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 153 | }; |
| 154 | |
| 155 | /* |
| 156 | * Locality group: |
| 157 | * we try to group all related changes together |
| 158 | * so that writeback can flush/allocate them together as well |
Aneesh Kumar K.V | 6be2ded | 2008-07-23 14:14:05 -0400 | [diff] [blame] | 159 | * Size of lg_prealloc_list hash is determined by MB_DEFAULT_GROUP_PREALLOC |
| 160 | * (512). We store prealloc space into the hash based on the pa_free blocks |
| 161 | * order value.ie, fls(pa_free)-1; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 162 | */ |
Aneesh Kumar K.V | 6be2ded | 2008-07-23 14:14:05 -0400 | [diff] [blame] | 163 | #define PREALLOC_TB_SIZE 10 |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 164 | struct ext4_locality_group { |
| 165 | /* for allocator */ |
Aneesh Kumar K.V | 6be2ded | 2008-07-23 14:14:05 -0400 | [diff] [blame] | 166 | /* to serialize allocates */ |
| 167 | struct mutex lg_mutex; |
| 168 | /* list of preallocations */ |
| 169 | struct list_head lg_prealloc_list[PREALLOC_TB_SIZE]; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 170 | spinlock_t lg_prealloc_lock; |
| 171 | }; |
| 172 | |
| 173 | struct ext4_allocation_context { |
| 174 | struct inode *ac_inode; |
| 175 | struct super_block *ac_sb; |
| 176 | |
| 177 | /* original request */ |
| 178 | struct ext4_free_extent ac_o_ex; |
| 179 | |
Coly Li | 58696f3 | 2011-02-24 14:10:00 -0500 | [diff] [blame] | 180 | /* goal request (normalized ac_o_ex) */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 181 | struct ext4_free_extent ac_g_ex; |
| 182 | |
| 183 | /* the best found extent */ |
| 184 | struct ext4_free_extent ac_b_ex; |
| 185 | |
Robin Dong | ff3fc17 | 2011-10-31 18:55:50 -0400 | [diff] [blame] | 186 | /* copy of the best found extent taken before preallocation efforts */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 187 | struct ext4_free_extent ac_f_ex; |
| 188 | |
Ojaswin Mujoo | 7e17092 | 2023-05-30 18:03:49 +0530 | [diff] [blame] | 189 | /* |
| 190 | * goal len can change in CR1.5, so save the original len. This is |
| 191 | * used while adjusting the PA window and for accounting. |
| 192 | */ |
| 193 | ext4_grpblk_t ac_orig_goal_len; |
| 194 | |
Harshad Shirwadkar | 196e402 | 2021-04-01 10:21:27 -0700 | [diff] [blame] | 195 | __u32 ac_flags; /* allocation hints */ |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 196 | __u16 ac_groups_scanned; |
Harshad Shirwadkar | 196e402 | 2021-04-01 10:21:27 -0700 | [diff] [blame] | 197 | __u16 ac_groups_linear_remaining; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 198 | __u16 ac_found; |
Ojaswin Mujoo | fdd9a00 | 2023-05-30 18:03:43 +0530 | [diff] [blame] | 199 | __u16 ac_cX_found[EXT4_MB_NUM_CRS]; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 200 | __u16 ac_tail; |
| 201 | __u16 ac_buddy; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 202 | __u8 ac_status; |
| 203 | __u8 ac_criteria; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 204 | __u8 ac_2order; /* if request is to allocate 2^N blocks and |
| 205 | * N > 0, the field stores N, otherwise 0 */ |
| 206 | __u8 ac_op; /* operation, for history only */ |
| 207 | struct page *ac_bitmap_page; |
| 208 | struct page *ac_buddy_page; |
| 209 | struct ext4_prealloc_space *ac_pa; |
| 210 | struct ext4_locality_group *ac_lg; |
| 211 | }; |
| 212 | |
| 213 | #define AC_STATUS_CONTINUE 1 |
| 214 | #define AC_STATUS_FOUND 2 |
| 215 | #define AC_STATUS_BREAK 3 |
| 216 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 217 | struct ext4_buddy { |
| 218 | struct page *bd_buddy_page; |
| 219 | void *bd_buddy; |
| 220 | struct page *bd_bitmap_page; |
| 221 | void *bd_bitmap; |
| 222 | struct ext4_group_info *bd_info; |
| 223 | struct super_block *bd_sb; |
| 224 | __u16 bd_blkbits; |
| 225 | ext4_group_t bd_group; |
| 226 | }; |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 227 | |
Aneesh Kumar K.V | c3a326a | 2008-11-25 15:11:52 -0500 | [diff] [blame] | 228 | 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] | 229 | struct ext4_free_extent *fex) |
| 230 | { |
Theodore Ts'o | 3212a80 | 2011-09-09 18:46:51 -0400 | [diff] [blame] | 231 | return ext4_group_first_block_no(sb, fex->fe_group) + |
| 232 | (fex->fe_start << EXT4_SB(sb)->s_cluster_bits); |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 233 | } |
Darrick J. Wong | 0c9ec4b | 2017-04-30 00:36:53 -0400 | [diff] [blame] | 234 | |
Baokun Li | 43bbddc | 2023-07-24 20:10:57 +0800 | [diff] [blame] | 235 | static inline loff_t extent_logical_end(struct ext4_sb_info *sbi, |
| 236 | struct ext4_free_extent *fex) |
| 237 | { |
| 238 | /* Use loff_t to avoid end exceeding ext4_lblk_t max. */ |
| 239 | return (loff_t)fex->fe_logical + EXT4_C2B(sbi, fex->fe_len); |
| 240 | } |
| 241 | |
| 242 | static inline loff_t pa_logical_end(struct ext4_sb_info *sbi, |
| 243 | struct ext4_prealloc_space *pa) |
| 244 | { |
| 245 | /* Use loff_t to avoid end exceeding ext4_lblk_t max. */ |
| 246 | return (loff_t)pa->pa_lstart + EXT4_C2B(sbi, pa->pa_len); |
| 247 | } |
| 248 | |
Darrick J. Wong | 0c9ec4b | 2017-04-30 00:36:53 -0400 | [diff] [blame] | 249 | typedef int (*ext4_mballoc_query_range_fn)( |
| 250 | struct super_block *sb, |
| 251 | ext4_group_t agno, |
| 252 | ext4_grpblk_t start, |
| 253 | ext4_grpblk_t len, |
| 254 | void *priv); |
| 255 | |
| 256 | int |
| 257 | ext4_mballoc_query_range( |
| 258 | struct super_block *sb, |
| 259 | ext4_group_t agno, |
| 260 | ext4_grpblk_t start, |
| 261 | ext4_grpblk_t end, |
| 262 | ext4_mballoc_query_range_fn formatter, |
| 263 | void *priv); |
| 264 | |
Mingming Cao | 8f6e39a | 2008-04-29 22:01:31 -0400 | [diff] [blame] | 265 | #endif |