1 | // SPDX-License-Identifier: GPL-2.0 |
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> |
21 | #include <linux/blkdev.h> |
22 | #include <linux/mutex.h> |
23 | #include "ext4_jbd2.h" |
24 | #include "ext4.h" |
25 | |
26 | /* |
27 | * mb_debug() dynamic printk msgs could be used to debug mballoc code. |
28 | */ |
29 | #ifdef CONFIG_EXT4_DEBUG |
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__) |
34 | #else |
35 | #define mb_debug(sb, fmt, ...) no_printk(fmt, ##__VA_ARGS__) |
36 | #endif |
37 | |
38 | #define EXT4_MB_HISTORY_ALLOC 1 /* allocation */ |
39 | #define EXT4_MB_HISTORY_PREALLOC 2 /* preallocated blocks used */ |
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 | /* |
52 | * with 's_mb_stats' allocator will collect stats that will be |
53 | * shown at umount. The collecting costs though! |
54 | */ |
55 | #define MB_DEFAULT_STATS 0 |
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. |
62 | * We can tune the same via /proc/fs/ext4/<partition>/stream_req |
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 | |
76 | /* |
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 | /* |
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. |
92 | */ |
93 | #define MB_DEFAULT_BEST_AVAIL_TRIM_ORDER 3 |
94 | |
95 | /* |
96 | * Number of valid buddy orders |
97 | */ |
98 | #define MB_NUM_ORDERS(sb) ((sb)->s_blocksize_bits + 2) |
99 | |
100 | struct ext4_free_data { |
101 | /* this links the free block information from sb_info */ |
102 | struct list_head efd_list; |
103 | |
104 | /* this links the free block information from group_info */ |
105 | struct rb_node efd_node; |
106 | |
107 | /* group which free block extent belongs */ |
108 | ext4_group_t efd_group; |
109 | |
110 | /* free block extent */ |
111 | ext4_grpblk_t efd_start_cluster; |
112 | ext4_grpblk_t efd_count; |
113 | |
114 | /* transaction which freed this extent */ |
115 | tid_t efd_tid; |
116 | }; |
117 | |
118 | struct ext4_prealloc_space { |
119 | union { |
120 | struct rb_node inode_node; /* for inode PA rbtree */ |
121 | struct list_head lg_list; /* for lg PAs */ |
122 | } pa_node; |
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 */ |
133 | ext4_grpblk_t pa_len; /* len of preallocated chunk */ |
134 | ext4_grpblk_t pa_free; /* how many blocks are free */ |
135 | unsigned short pa_type; /* pa type. inode or group */ |
136 | union { |
137 | rwlock_t *inode_lock; /* locks the rbtree holding this PA */ |
138 | spinlock_t *lg_lock; /* locks the lg list holding this PA */ |
139 | } pa_node_lock; |
140 | struct inode *pa_inode; /* used to get the inode during group discard */ |
141 | }; |
142 | |
143 | enum { |
144 | MB_INODE_PA = 0, |
145 | MB_GROUP_PA = 1 |
146 | }; |
147 | |
148 | struct ext4_free_extent { |
149 | ext4_lblk_t fe_logical; |
150 | ext4_grpblk_t fe_start; /* In cluster units */ |
151 | ext4_group_t fe_group; |
152 | ext4_grpblk_t fe_len; /* In cluster units */ |
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 |
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; |
162 | */ |
163 | #define PREALLOC_TB_SIZE 10 |
164 | struct ext4_locality_group { |
165 | /* for allocator */ |
166 | /* to serialize allocates */ |
167 | struct mutex lg_mutex; |
168 | /* list of preallocations */ |
169 | struct list_head lg_prealloc_list[PREALLOC_TB_SIZE]; |
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 | |
180 | /* goal request (normalized ac_o_ex) */ |
181 | struct ext4_free_extent ac_g_ex; |
182 | |
183 | /* the best found extent */ |
184 | struct ext4_free_extent ac_b_ex; |
185 | |
186 | /* copy of the best found extent taken before preallocation efforts */ |
187 | struct ext4_free_extent ac_f_ex; |
188 | |
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 | |
195 | __u32 ac_flags; /* allocation hints */ |
196 | __u16 ac_groups_scanned; |
197 | __u16 ac_groups_linear_remaining; |
198 | __u16 ac_found; |
199 | __u16 ac_cX_found[EXT4_MB_NUM_CRS]; |
200 | __u16 ac_tail; |
201 | __u16 ac_buddy; |
202 | __u8 ac_status; |
203 | __u8 ac_criteria; |
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 | |
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 | }; |
227 | |
228 | static inline ext4_fsblk_t ext4_grp_offs_to_block(struct super_block *sb, |
229 | struct ext4_free_extent *fex) |
230 | { |
231 | return ext4_group_first_block_no(sb, group_no: fex->fe_group) + |
232 | (fex->fe_start << EXT4_SB(sb)->s_cluster_bits); |
233 | } |
234 | |
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 | |
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 | |
265 | #endif |
266 | |