Commit | Line | Data |
---|---|---|
8f6e39a7 MC |
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> | |
20 | #include <linux/version.h> | |
8a0aba73 TT |
21 | #include <linux/blkdev.h> |
22 | #include <linux/marker.h> | |
920313a7 | 23 | #include <linux/mutex.h> |
8f6e39a7 MC |
24 | #include "ext4_jbd2.h" |
25 | #include "ext4.h" | |
8f6e39a7 MC |
26 | |
27 | /* | |
28 | * with AGGRESSIVE_CHECK allocator runs consistency checks over | |
29 | * structures. these checks slow things down a lot | |
30 | */ | |
31 | #define AGGRESSIVE_CHECK__ | |
32 | ||
33 | /* | |
34 | * with DOUBLE_CHECK defined mballoc creates persistent in-core | |
35 | * bitmaps, maintains and uses them to check for double allocations | |
36 | */ | |
37 | #define DOUBLE_CHECK__ | |
38 | ||
39 | /* | |
40 | */ | |
41 | #define MB_DEBUG__ | |
42 | #ifdef MB_DEBUG | |
43 | #define mb_debug(fmt, a...) printk(fmt, ##a) | |
44 | #else | |
45 | #define mb_debug(fmt, a...) | |
46 | #endif | |
47 | ||
48 | /* | |
49 | * with EXT4_MB_HISTORY mballoc stores last N allocations in memory | |
50 | * and you can monitor it in /proc/fs/ext4/<dev>/mb_history | |
51 | */ | |
52 | #define EXT4_MB_HISTORY | |
53 | #define EXT4_MB_HISTORY_ALLOC 1 /* allocation */ | |
54 | #define EXT4_MB_HISTORY_PREALLOC 2 /* preallocated blocks used */ | |
55 | #define EXT4_MB_HISTORY_DISCARD 4 /* preallocation discarded */ | |
56 | #define EXT4_MB_HISTORY_FREE 8 /* free */ | |
57 | ||
58 | #define EXT4_MB_HISTORY_DEFAULT (EXT4_MB_HISTORY_ALLOC | \ | |
59 | EXT4_MB_HISTORY_PREALLOC) | |
60 | ||
61 | /* | |
62 | * How long mballoc can look for a best extent (in found extents) | |
63 | */ | |
64 | #define MB_DEFAULT_MAX_TO_SCAN 200 | |
65 | ||
66 | /* | |
67 | * How long mballoc must look for a best extent | |
68 | */ | |
69 | #define MB_DEFAULT_MIN_TO_SCAN 10 | |
70 | ||
71 | /* | |
72 | * How many groups mballoc will scan looking for the best chunk | |
73 | */ | |
74 | #define MB_DEFAULT_MAX_GROUPS_TO_SCAN 5 | |
75 | ||
76 | /* | |
77 | * with 'ext4_mb_stats' allocator will collect stats that will be | |
78 | * shown at umount. The collecting costs though! | |
79 | */ | |
80 | #define MB_DEFAULT_STATS 1 | |
81 | ||
82 | /* | |
83 | * files smaller than MB_DEFAULT_STREAM_THRESHOLD are served | |
84 | * by the stream allocator, which purpose is to pack requests | |
85 | * as close each to other as possible to produce smooth I/O traffic | |
86 | * We use locality group prealloc space for stream request. | |
87 | * We can tune the same via /proc/fs/ext4/<parition>/stream_req | |
88 | */ | |
89 | #define MB_DEFAULT_STREAM_THRESHOLD 16 /* 64K */ | |
90 | ||
91 | /* | |
92 | * for which requests use 2^N search using buddies | |
93 | */ | |
94 | #define MB_DEFAULT_ORDER2_REQS 2 | |
95 | ||
96 | /* | |
97 | * default group prealloc size 512 blocks | |
98 | */ | |
99 | #define MB_DEFAULT_GROUP_PREALLOC 512 | |
100 | ||
8f6e39a7 | 101 | |
c894058d AK |
102 | struct ext4_free_data { |
103 | /* this links the free block information from group_info */ | |
104 | struct rb_node node; | |
8f6e39a7 | 105 | |
c894058d | 106 | /* this links the free block information from ext4_sb_info */ |
8f6e39a7 | 107 | struct list_head list; |
c894058d AK |
108 | |
109 | /* group which free block extent belongs */ | |
110 | ext4_group_t group; | |
111 | ||
112 | /* free block extent */ | |
113 | ext4_grpblk_t start_blk; | |
114 | ext4_grpblk_t count; | |
115 | ||
116 | /* transaction which freed this extent */ | |
117 | tid_t t_tid; | |
8f6e39a7 MC |
118 | }; |
119 | ||
8f6e39a7 MC |
120 | struct ext4_prealloc_space { |
121 | struct list_head pa_inode_list; | |
122 | struct list_head pa_group_list; | |
123 | union { | |
124 | struct list_head pa_tmp_list; | |
125 | struct rcu_head pa_rcu; | |
126 | } u; | |
127 | spinlock_t pa_lock; | |
128 | atomic_t pa_count; | |
129 | unsigned pa_deleted; | |
130 | ext4_fsblk_t pa_pstart; /* phys. block */ | |
131 | ext4_lblk_t pa_lstart; /* log. block */ | |
132 | unsigned short pa_len; /* len of preallocated chunk */ | |
133 | unsigned short pa_free; /* how many blocks are free */ | |
cc0fb9ad | 134 | unsigned short pa_type; /* pa type. inode or group */ |
8f6e39a7 MC |
135 | spinlock_t *pa_obj_lock; |
136 | struct inode *pa_inode; /* hack, for history only */ | |
137 | }; | |
138 | ||
cc0fb9ad AK |
139 | enum { |
140 | MB_INODE_PA = 0, | |
141 | MB_GROUP_PA = 1 | |
142 | }; | |
8f6e39a7 MC |
143 | |
144 | struct ext4_free_extent { | |
145 | ext4_lblk_t fe_logical; | |
146 | ext4_grpblk_t fe_start; | |
147 | ext4_group_t fe_group; | |
148 | int fe_len; | |
149 | }; | |
150 | ||
151 | /* | |
152 | * Locality group: | |
153 | * we try to group all related changes together | |
154 | * so that writeback can flush/allocate them together as well | |
6be2ded1 AK |
155 | * Size of lg_prealloc_list hash is determined by MB_DEFAULT_GROUP_PREALLOC |
156 | * (512). We store prealloc space into the hash based on the pa_free blocks | |
157 | * order value.ie, fls(pa_free)-1; | |
8f6e39a7 | 158 | */ |
6be2ded1 | 159 | #define PREALLOC_TB_SIZE 10 |
8f6e39a7 MC |
160 | struct ext4_locality_group { |
161 | /* for allocator */ | |
6be2ded1 AK |
162 | /* to serialize allocates */ |
163 | struct mutex lg_mutex; | |
164 | /* list of preallocations */ | |
165 | struct list_head lg_prealloc_list[PREALLOC_TB_SIZE]; | |
8f6e39a7 MC |
166 | spinlock_t lg_prealloc_lock; |
167 | }; | |
168 | ||
169 | struct ext4_allocation_context { | |
170 | struct inode *ac_inode; | |
171 | struct super_block *ac_sb; | |
172 | ||
173 | /* original request */ | |
174 | struct ext4_free_extent ac_o_ex; | |
175 | ||
176 | /* goal request (after normalization) */ | |
177 | struct ext4_free_extent ac_g_ex; | |
178 | ||
179 | /* the best found extent */ | |
180 | struct ext4_free_extent ac_b_ex; | |
181 | ||
182 | /* copy of the bext found extent taken before preallocation efforts */ | |
183 | struct ext4_free_extent ac_f_ex; | |
184 | ||
185 | /* number of iterations done. we have to track to limit searching */ | |
186 | unsigned long ac_ex_scanned; | |
187 | __u16 ac_groups_scanned; | |
188 | __u16 ac_found; | |
189 | __u16 ac_tail; | |
190 | __u16 ac_buddy; | |
191 | __u16 ac_flags; /* allocation hints */ | |
192 | __u8 ac_status; | |
193 | __u8 ac_criteria; | |
194 | __u8 ac_repeats; | |
195 | __u8 ac_2order; /* if request is to allocate 2^N blocks and | |
196 | * N > 0, the field stores N, otherwise 0 */ | |
197 | __u8 ac_op; /* operation, for history only */ | |
198 | struct page *ac_bitmap_page; | |
199 | struct page *ac_buddy_page; | |
8556e8f3 AK |
200 | /* |
201 | * pointer to the held semaphore upon successful | |
202 | * block allocation | |
203 | */ | |
204 | struct rw_semaphore *alloc_semp; | |
8f6e39a7 MC |
205 | struct ext4_prealloc_space *ac_pa; |
206 | struct ext4_locality_group *ac_lg; | |
207 | }; | |
208 | ||
209 | #define AC_STATUS_CONTINUE 1 | |
210 | #define AC_STATUS_FOUND 2 | |
211 | #define AC_STATUS_BREAK 3 | |
212 | ||
213 | struct ext4_mb_history { | |
214 | struct ext4_free_extent orig; /* orig allocation */ | |
215 | struct ext4_free_extent goal; /* goal allocation */ | |
216 | struct ext4_free_extent result; /* result allocation */ | |
217 | unsigned pid; | |
218 | unsigned ino; | |
219 | __u16 found; /* how many extents have been found */ | |
220 | __u16 groups; /* how many groups have been scanned */ | |
221 | __u16 tail; /* what tail broke some buddy */ | |
222 | __u16 buddy; /* buddy the tail ^^^ broke */ | |
223 | __u16 flags; | |
224 | __u8 cr:3; /* which phase the result extent was found at */ | |
225 | __u8 op:4; | |
226 | __u8 merged:1; | |
227 | }; | |
228 | ||
229 | struct ext4_buddy { | |
230 | struct page *bd_buddy_page; | |
231 | void *bd_buddy; | |
232 | struct page *bd_bitmap_page; | |
233 | void *bd_bitmap; | |
234 | struct ext4_group_info *bd_info; | |
235 | struct super_block *bd_sb; | |
236 | __u16 bd_blkbits; | |
237 | ext4_group_t bd_group; | |
920313a7 | 238 | struct rw_semaphore *alloc_semp; |
8f6e39a7 MC |
239 | }; |
240 | #define EXT4_MB_BITMAP(e4b) ((e4b)->bd_bitmap) | |
241 | #define EXT4_MB_BUDDY(e4b) ((e4b)->bd_buddy) | |
242 | ||
243 | #ifndef EXT4_MB_HISTORY | |
244 | static inline void ext4_mb_store_history(struct ext4_allocation_context *ac) | |
245 | { | |
246 | return; | |
247 | } | |
8f6e39a7 MC |
248 | #endif |
249 | ||
250 | #define in_range(b, first, len) ((b) >= (first) && (b) <= (first) + (len) - 1) | |
251 | ||
c3a326a6 | 252 | static inline ext4_fsblk_t ext4_grp_offs_to_block(struct super_block *sb, |
8f6e39a7 MC |
253 | struct ext4_free_extent *fex) |
254 | { | |
255 | ext4_fsblk_t block; | |
256 | ||
257 | block = (ext4_fsblk_t) fex->fe_group * EXT4_BLOCKS_PER_GROUP(sb) | |
258 | + fex->fe_start | |
259 | + le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block); | |
260 | return block; | |
261 | } | |
262 | #endif |