blob: cd258463e2a9e017f949367b403d87332e5a3d24 [file] [log] [blame]
Alex Tomasc9de5602008-01-29 00:19:52 -05001/*
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
19
20/*
21 * mballoc.c contains the multiblocks allocation routines
22 */
23
Mingming Cao8f6e39a2008-04-29 22:01:31 -040024#include "mballoc.h"
Theodore Ts'o9bffad12009-06-17 11:48:11 -040025#include <trace/events/ext4.h>
26
Alex Tomasc9de5602008-01-29 00:19:52 -050027/*
28 * MUSTDO:
29 * - test ext4_ext_search_left() and ext4_ext_search_right()
30 * - search for metadata in few groups
31 *
32 * TODO v4:
33 * - normalization should take into account whether file is still open
34 * - discard preallocations if no free space left (policy?)
35 * - don't normalize tails
36 * - quota
37 * - reservation for superuser
38 *
39 * TODO v3:
40 * - bitmap read-ahead (proposed by Oleg Drokin aka green)
41 * - track min/max extents in each group for better group selection
42 * - mb_mark_used() may allocate chunk right after splitting buddy
43 * - tree of groups sorted by number of free blocks
44 * - error handling
45 */
46
47/*
48 * The allocation request involve request for multiple number of blocks
49 * near to the goal(block) value specified.
50 *
Theodore Ts'ob713a5e2009-03-31 09:11:14 -040051 * During initialization phase of the allocator we decide to use the
52 * group preallocation or inode preallocation depending on the size of
53 * the file. The size of the file could be the resulting file size we
54 * would have after allocation, or the current file size, which ever
55 * is larger. If the size is less than sbi->s_mb_stream_request we
56 * select to use the group preallocation. The default value of
57 * s_mb_stream_request is 16 blocks. This can also be tuned via
58 * /sys/fs/ext4/<partition>/mb_stream_req. The value is represented in
59 * terms of number of blocks.
Alex Tomasc9de5602008-01-29 00:19:52 -050060 *
61 * The main motivation for having small file use group preallocation is to
Theodore Ts'ob713a5e2009-03-31 09:11:14 -040062 * ensure that we have small files closer together on the disk.
Alex Tomasc9de5602008-01-29 00:19:52 -050063 *
Theodore Ts'ob713a5e2009-03-31 09:11:14 -040064 * First stage the allocator looks at the inode prealloc list,
65 * ext4_inode_info->i_prealloc_list, which contains list of prealloc
66 * spaces for this particular inode. The inode prealloc space is
67 * represented as:
Alex Tomasc9de5602008-01-29 00:19:52 -050068 *
69 * pa_lstart -> the logical start block for this prealloc space
70 * pa_pstart -> the physical start block for this prealloc space
71 * pa_len -> lenght for this prealloc space
72 * pa_free -> free space available in this prealloc space
73 *
74 * The inode preallocation space is used looking at the _logical_ start
75 * block. If only the logical file block falls within the range of prealloc
76 * space we will consume the particular prealloc space. This make sure that
77 * that the we have contiguous physical blocks representing the file blocks
78 *
79 * The important thing to be noted in case of inode prealloc space is that
80 * we don't modify the values associated to inode prealloc space except
81 * pa_free.
82 *
83 * If we are not able to find blocks in the inode prealloc space and if we
84 * have the group allocation flag set then we look at the locality group
85 * prealloc space. These are per CPU prealloc list repreasented as
86 *
87 * ext4_sb_info.s_locality_groups[smp_processor_id()]
88 *
89 * The reason for having a per cpu locality group is to reduce the contention
90 * between CPUs. It is possible to get scheduled at this point.
91 *
92 * The locality group prealloc space is used looking at whether we have
93 * enough free space (pa_free) withing the prealloc space.
94 *
95 * If we can't allocate blocks via inode prealloc or/and locality group
96 * prealloc then we look at the buddy cache. The buddy cache is represented
97 * by ext4_sb_info.s_buddy_cache (struct inode) whose file offset gets
98 * mapped to the buddy and bitmap information regarding different
99 * groups. The buddy information is attached to buddy cache inode so that
100 * we can access them through the page cache. The information regarding
101 * each group is loaded via ext4_mb_load_buddy. The information involve
102 * block bitmap and buddy information. The information are stored in the
103 * inode as:
104 *
105 * { page }
Aneesh Kumar K.Vc3a326a2008-11-25 15:11:52 -0500106 * [ group 0 bitmap][ group 0 buddy] [group 1][ group 1]...
Alex Tomasc9de5602008-01-29 00:19:52 -0500107 *
108 *
109 * one block each for bitmap and buddy information. So for each group we
110 * take up 2 blocks. A page can contain blocks_per_page (PAGE_CACHE_SIZE /
111 * blocksize) blocks. So it can have information regarding groups_per_page
112 * which is blocks_per_page/2
113 *
114 * The buddy cache inode is not stored on disk. The inode is thrown
115 * away when the filesystem is unmounted.
116 *
117 * We look for count number of blocks in the buddy cache. If we were able
118 * to locate that many free blocks we return with additional information
119 * regarding rest of the contiguous physical block available
120 *
121 * Before allocating blocks via buddy cache we normalize the request
122 * blocks. This ensure we ask for more blocks that we needed. The extra
123 * blocks that we get after allocation is added to the respective prealloc
124 * list. In case of inode preallocation we follow a list of heuristics
125 * based on file size. This can be found in ext4_mb_normalize_request. If
126 * we are doing a group prealloc we try to normalize the request to
Theodore Ts'ob713a5e2009-03-31 09:11:14 -0400127 * sbi->s_mb_group_prealloc. Default value of s_mb_group_prealloc is
Alex Tomasc9de5602008-01-29 00:19:52 -0500128 * 512 blocks. This can be tuned via
Theodore Ts'ob713a5e2009-03-31 09:11:14 -0400129 * /sys/fs/ext4/<partition/mb_group_prealloc. The value is represented in
Alex Tomasc9de5602008-01-29 00:19:52 -0500130 * terms of number of blocks. If we have mounted the file system with -O
131 * stripe=<value> option the group prealloc request is normalized to the
132 * stripe value (sbi->s_stripe)
133 *
Theodore Ts'ob713a5e2009-03-31 09:11:14 -0400134 * The regular allocator(using the buddy cache) supports few tunables.
Alex Tomasc9de5602008-01-29 00:19:52 -0500135 *
Theodore Ts'ob713a5e2009-03-31 09:11:14 -0400136 * /sys/fs/ext4/<partition>/mb_min_to_scan
137 * /sys/fs/ext4/<partition>/mb_max_to_scan
138 * /sys/fs/ext4/<partition>/mb_order2_req
Alex Tomasc9de5602008-01-29 00:19:52 -0500139 *
Theodore Ts'ob713a5e2009-03-31 09:11:14 -0400140 * The regular allocator uses buddy scan only if the request len is power of
Alex Tomasc9de5602008-01-29 00:19:52 -0500141 * 2 blocks and the order of allocation is >= sbi->s_mb_order2_reqs. The
142 * value of s_mb_order2_reqs can be tuned via
Theodore Ts'ob713a5e2009-03-31 09:11:14 -0400143 * /sys/fs/ext4/<partition>/mb_order2_req. If the request len is equal to
Alex Tomasc9de5602008-01-29 00:19:52 -0500144 * stripe size (sbi->s_stripe), we try to search for contigous block in
Theodore Ts'ob713a5e2009-03-31 09:11:14 -0400145 * stripe size. This should result in better allocation on RAID setups. If
146 * not, we search in the specific group using bitmap for best extents. The
147 * tunable min_to_scan and max_to_scan control the behaviour here.
Alex Tomasc9de5602008-01-29 00:19:52 -0500148 * min_to_scan indicate how long the mballoc __must__ look for a best
Theodore Ts'ob713a5e2009-03-31 09:11:14 -0400149 * extent and max_to_scan indicates how long the mballoc __can__ look for a
Alex Tomasc9de5602008-01-29 00:19:52 -0500150 * best extent in the found extents. Searching for the blocks starts with
151 * the group specified as the goal value in allocation context via
152 * ac_g_ex. Each group is first checked based on the criteria whether it
153 * can used for allocation. ext4_mb_good_group explains how the groups are
154 * checked.
155 *
156 * Both the prealloc space are getting populated as above. So for the first
157 * request we will hit the buddy cache which will result in this prealloc
158 * space getting filled. The prealloc space is then later used for the
159 * subsequent request.
160 */
161
162/*
163 * mballoc operates on the following data:
164 * - on-disk bitmap
165 * - in-core buddy (actually includes buddy and bitmap)
166 * - preallocation descriptors (PAs)
167 *
168 * there are two types of preallocations:
169 * - inode
170 * assiged to specific inode and can be used for this inode only.
171 * it describes part of inode's space preallocated to specific
172 * physical blocks. any block from that preallocated can be used
173 * independent. the descriptor just tracks number of blocks left
174 * unused. so, before taking some block from descriptor, one must
175 * make sure corresponded logical block isn't allocated yet. this
176 * also means that freeing any block within descriptor's range
177 * must discard all preallocated blocks.
178 * - locality group
179 * assigned to specific locality group which does not translate to
180 * permanent set of inodes: inode can join and leave group. space
181 * from this type of preallocation can be used for any inode. thus
182 * it's consumed from the beginning to the end.
183 *
184 * relation between them can be expressed as:
185 * in-core buddy = on-disk bitmap + preallocation descriptors
186 *
187 * this mean blocks mballoc considers used are:
188 * - allocated blocks (persistent)
189 * - preallocated blocks (non-persistent)
190 *
191 * consistency in mballoc world means that at any time a block is either
192 * free or used in ALL structures. notice: "any time" should not be read
193 * literally -- time is discrete and delimited by locks.
194 *
195 * to keep it simple, we don't use block numbers, instead we count number of
196 * blocks: how many blocks marked used/free in on-disk bitmap, buddy and PA.
197 *
198 * all operations can be expressed as:
199 * - init buddy: buddy = on-disk + PAs
200 * - new PA: buddy += N; PA = N
201 * - use inode PA: on-disk += N; PA -= N
202 * - discard inode PA buddy -= on-disk - PA; PA = 0
203 * - use locality group PA on-disk += N; PA -= N
204 * - discard locality group PA buddy -= PA; PA = 0
205 * note: 'buddy -= on-disk - PA' is used to show that on-disk bitmap
206 * is used in real operation because we can't know actual used
207 * bits from PA, only from on-disk bitmap
208 *
209 * if we follow this strict logic, then all operations above should be atomic.
210 * given some of them can block, we'd have to use something like semaphores
211 * killing performance on high-end SMP hardware. let's try to relax it using
212 * the following knowledge:
213 * 1) if buddy is referenced, it's already initialized
214 * 2) while block is used in buddy and the buddy is referenced,
215 * nobody can re-allocate that block
216 * 3) we work on bitmaps and '+' actually means 'set bits'. if on-disk has
217 * bit set and PA claims same block, it's OK. IOW, one can set bit in
218 * on-disk bitmap if buddy has same bit set or/and PA covers corresponded
219 * block
220 *
221 * so, now we're building a concurrency table:
222 * - init buddy vs.
223 * - new PA
224 * blocks for PA are allocated in the buddy, buddy must be referenced
225 * until PA is linked to allocation group to avoid concurrent buddy init
226 * - use inode PA
227 * we need to make sure that either on-disk bitmap or PA has uptodate data
228 * given (3) we care that PA-=N operation doesn't interfere with init
229 * - discard inode PA
230 * the simplest way would be to have buddy initialized by the discard
231 * - use locality group PA
232 * again PA-=N must be serialized with init
233 * - discard locality group PA
234 * the simplest way would be to have buddy initialized by the discard
235 * - new PA vs.
236 * - use inode PA
237 * i_data_sem serializes them
238 * - discard inode PA
239 * discard process must wait until PA isn't used by another process
240 * - use locality group PA
241 * some mutex should serialize them
242 * - discard locality group PA
243 * discard process must wait until PA isn't used by another process
244 * - use inode PA
245 * - use inode PA
246 * i_data_sem or another mutex should serializes them
247 * - discard inode PA
248 * discard process must wait until PA isn't used by another process
249 * - use locality group PA
250 * nothing wrong here -- they're different PAs covering different blocks
251 * - discard locality group PA
252 * discard process must wait until PA isn't used by another process
253 *
254 * now we're ready to make few consequences:
255 * - PA is referenced and while it is no discard is possible
256 * - PA is referenced until block isn't marked in on-disk bitmap
257 * - PA changes only after on-disk bitmap
258 * - discard must not compete with init. either init is done before
259 * any discard or they're serialized somehow
260 * - buddy init as sum of on-disk bitmap and PAs is done atomically
261 *
262 * a special case when we've used PA to emptiness. no need to modify buddy
263 * in this case, but we should care about concurrent init
264 *
265 */
266
267 /*
268 * Logic in few words:
269 *
270 * - allocation:
271 * load group
272 * find blocks
273 * mark bits in on-disk bitmap
274 * release group
275 *
276 * - use preallocation:
277 * find proper PA (per-inode or group)
278 * load group
279 * mark bits in on-disk bitmap
280 * release group
281 * release PA
282 *
283 * - free:
284 * load group
285 * mark bits in on-disk bitmap
286 * release group
287 *
288 * - discard preallocations in group:
289 * mark PAs deleted
290 * move them onto local list
291 * load on-disk bitmap
292 * load group
293 * remove PA from object (inode or locality group)
294 * mark free blocks in-core
295 *
296 * - discard inode's preallocations:
297 */
298
299/*
300 * Locking rules
301 *
302 * Locks:
303 * - bitlock on a group (group)
304 * - object (inode/locality) (object)
305 * - per-pa lock (pa)
306 *
307 * Paths:
308 * - new pa
309 * object
310 * group
311 *
312 * - find and use pa:
313 * pa
314 *
315 * - release consumed pa:
316 * pa
317 * group
318 * object
319 *
320 * - generate in-core bitmap:
321 * group
322 * pa
323 *
324 * - discard all for given object (inode, locality group):
325 * object
326 * pa
327 * group
328 *
329 * - discard all for given group:
330 * group
331 * pa
332 * group
333 * object
334 *
335 */
Aneesh Kumar K.Vc3a326a2008-11-25 15:11:52 -0500336static struct kmem_cache *ext4_pspace_cachep;
337static struct kmem_cache *ext4_ac_cachep;
338static struct kmem_cache *ext4_free_ext_cachep;
339static void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,
340 ext4_group_t group);
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -0500341static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
342 ext4_group_t group);
Aneesh Kumar K.Vc3a326a2008-11-25 15:11:52 -0500343static void release_blocks_on_commit(journal_t *journal, transaction_t *txn);
344
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500345static inline void *mb_correct_addr_and_bit(int *bit, void *addr)
346{
Alex Tomasc9de5602008-01-29 00:19:52 -0500347#if BITS_PER_LONG == 64
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500348 *bit += ((unsigned long) addr & 7UL) << 3;
349 addr = (void *) ((unsigned long) addr & ~7UL);
Alex Tomasc9de5602008-01-29 00:19:52 -0500350#elif BITS_PER_LONG == 32
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500351 *bit += ((unsigned long) addr & 3UL) << 3;
352 addr = (void *) ((unsigned long) addr & ~3UL);
Alex Tomasc9de5602008-01-29 00:19:52 -0500353#else
354#error "how many bits you are?!"
355#endif
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500356 return addr;
357}
Alex Tomasc9de5602008-01-29 00:19:52 -0500358
359static inline int mb_test_bit(int bit, void *addr)
360{
361 /*
362 * ext4_test_bit on architecture like powerpc
363 * needs unsigned long aligned address
364 */
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500365 addr = mb_correct_addr_and_bit(&bit, addr);
Alex Tomasc9de5602008-01-29 00:19:52 -0500366 return ext4_test_bit(bit, addr);
367}
368
369static inline void mb_set_bit(int bit, void *addr)
370{
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500371 addr = mb_correct_addr_and_bit(&bit, addr);
Alex Tomasc9de5602008-01-29 00:19:52 -0500372 ext4_set_bit(bit, addr);
373}
374
Alex Tomasc9de5602008-01-29 00:19:52 -0500375static inline void mb_clear_bit(int bit, void *addr)
376{
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500377 addr = mb_correct_addr_and_bit(&bit, addr);
Alex Tomasc9de5602008-01-29 00:19:52 -0500378 ext4_clear_bit(bit, addr);
379}
380
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500381static inline int mb_find_next_zero_bit(void *addr, int max, int start)
382{
Aneesh Kumar K.Ve7dfb242008-07-11 19:27:31 -0400383 int fix = 0, ret, tmpmax;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500384 addr = mb_correct_addr_and_bit(&fix, addr);
Aneesh Kumar K.Ve7dfb242008-07-11 19:27:31 -0400385 tmpmax = max + fix;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500386 start += fix;
387
Aneesh Kumar K.Ve7dfb242008-07-11 19:27:31 -0400388 ret = ext4_find_next_zero_bit(addr, tmpmax, start) - fix;
389 if (ret > max)
390 return max;
391 return ret;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500392}
393
394static inline int mb_find_next_bit(void *addr, int max, int start)
395{
Aneesh Kumar K.Ve7dfb242008-07-11 19:27:31 -0400396 int fix = 0, ret, tmpmax;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500397 addr = mb_correct_addr_and_bit(&fix, addr);
Aneesh Kumar K.Ve7dfb242008-07-11 19:27:31 -0400398 tmpmax = max + fix;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500399 start += fix;
400
Aneesh Kumar K.Ve7dfb242008-07-11 19:27:31 -0400401 ret = ext4_find_next_bit(addr, tmpmax, start) - fix;
402 if (ret > max)
403 return max;
404 return ret;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500405}
406
Alex Tomasc9de5602008-01-29 00:19:52 -0500407static void *mb_find_buddy(struct ext4_buddy *e4b, int order, int *max)
408{
409 char *bb;
410
Alex Tomasc9de5602008-01-29 00:19:52 -0500411 BUG_ON(EXT4_MB_BITMAP(e4b) == EXT4_MB_BUDDY(e4b));
412 BUG_ON(max == NULL);
413
414 if (order > e4b->bd_blkbits + 1) {
415 *max = 0;
416 return NULL;
417 }
418
419 /* at order 0 we see each particular block */
420 *max = 1 << (e4b->bd_blkbits + 3);
421 if (order == 0)
422 return EXT4_MB_BITMAP(e4b);
423
424 bb = EXT4_MB_BUDDY(e4b) + EXT4_SB(e4b->bd_sb)->s_mb_offsets[order];
425 *max = EXT4_SB(e4b->bd_sb)->s_mb_maxs[order];
426
427 return bb;
428}
429
430#ifdef DOUBLE_CHECK
431static void mb_free_blocks_double(struct inode *inode, struct ext4_buddy *e4b,
432 int first, int count)
433{
434 int i;
435 struct super_block *sb = e4b->bd_sb;
436
437 if (unlikely(e4b->bd_info->bb_bitmap == NULL))
438 return;
Vincent Minetbc8e6742009-05-15 08:33:18 -0400439 assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));
Alex Tomasc9de5602008-01-29 00:19:52 -0500440 for (i = 0; i < count; i++) {
441 if (!mb_test_bit(first + i, e4b->bd_info->bb_bitmap)) {
442 ext4_fsblk_t blocknr;
443 blocknr = e4b->bd_group * EXT4_BLOCKS_PER_GROUP(sb);
444 blocknr += first + i;
445 blocknr +=
446 le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);
Aneesh Kumar K.V5d1b1b32009-01-05 22:19:52 -0500447 ext4_grp_locked_error(sb, e4b->bd_group,
448 __func__, "double-free of inode"
Theodore Ts'oa9df9a42009-01-05 22:18:16 -0500449 " %lu's block %llu(bit %u in group %u)",
Alex Tomasc9de5602008-01-29 00:19:52 -0500450 inode ? inode->i_ino : 0, blocknr,
451 first + i, e4b->bd_group);
452 }
453 mb_clear_bit(first + i, e4b->bd_info->bb_bitmap);
454 }
455}
456
457static void mb_mark_used_double(struct ext4_buddy *e4b, int first, int count)
458{
459 int i;
460
461 if (unlikely(e4b->bd_info->bb_bitmap == NULL))
462 return;
Vincent Minetbc8e6742009-05-15 08:33:18 -0400463 assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
Alex Tomasc9de5602008-01-29 00:19:52 -0500464 for (i = 0; i < count; i++) {
465 BUG_ON(mb_test_bit(first + i, e4b->bd_info->bb_bitmap));
466 mb_set_bit(first + i, e4b->bd_info->bb_bitmap);
467 }
468}
469
470static void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap)
471{
472 if (memcmp(e4b->bd_info->bb_bitmap, bitmap, e4b->bd_sb->s_blocksize)) {
473 unsigned char *b1, *b2;
474 int i;
475 b1 = (unsigned char *) e4b->bd_info->bb_bitmap;
476 b2 = (unsigned char *) bitmap;
477 for (i = 0; i < e4b->bd_sb->s_blocksize; i++) {
478 if (b1[i] != b2[i]) {
Theodore Ts'oa9df9a42009-01-05 22:18:16 -0500479 printk(KERN_ERR "corruption in group %u "
Theodore Ts'o4776004f2008-09-08 23:00:52 -0400480 "at byte %u(%u): %x in copy != %x "
481 "on disk/prealloc\n",
482 e4b->bd_group, i, i * 8, b1[i], b2[i]);
Alex Tomasc9de5602008-01-29 00:19:52 -0500483 BUG();
484 }
485 }
486 }
487}
488
489#else
490static inline void mb_free_blocks_double(struct inode *inode,
491 struct ext4_buddy *e4b, int first, int count)
492{
493 return;
494}
495static inline void mb_mark_used_double(struct ext4_buddy *e4b,
496 int first, int count)
497{
498 return;
499}
500static inline void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap)
501{
502 return;
503}
504#endif
505
506#ifdef AGGRESSIVE_CHECK
507
508#define MB_CHECK_ASSERT(assert) \
509do { \
510 if (!(assert)) { \
511 printk(KERN_EMERG \
512 "Assertion failure in %s() at %s:%d: \"%s\"\n", \
513 function, file, line, # assert); \
514 BUG(); \
515 } \
516} while (0)
517
518static int __mb_check_buddy(struct ext4_buddy *e4b, char *file,
519 const char *function, int line)
520{
521 struct super_block *sb = e4b->bd_sb;
522 int order = e4b->bd_blkbits + 1;
523 int max;
524 int max2;
525 int i;
526 int j;
527 int k;
528 int count;
529 struct ext4_group_info *grp;
530 int fragments = 0;
531 int fstart;
532 struct list_head *cur;
533 void *buddy;
534 void *buddy2;
535
Alex Tomasc9de5602008-01-29 00:19:52 -0500536 {
537 static int mb_check_counter;
538 if (mb_check_counter++ % 100 != 0)
539 return 0;
540 }
541
542 while (order > 1) {
543 buddy = mb_find_buddy(e4b, order, &max);
544 MB_CHECK_ASSERT(buddy);
545 buddy2 = mb_find_buddy(e4b, order - 1, &max2);
546 MB_CHECK_ASSERT(buddy2);
547 MB_CHECK_ASSERT(buddy != buddy2);
548 MB_CHECK_ASSERT(max * 2 == max2);
549
550 count = 0;
551 for (i = 0; i < max; i++) {
552
553 if (mb_test_bit(i, buddy)) {
554 /* only single bit in buddy2 may be 1 */
555 if (!mb_test_bit(i << 1, buddy2)) {
556 MB_CHECK_ASSERT(
557 mb_test_bit((i<<1)+1, buddy2));
558 } else if (!mb_test_bit((i << 1) + 1, buddy2)) {
559 MB_CHECK_ASSERT(
560 mb_test_bit(i << 1, buddy2));
561 }
562 continue;
563 }
564
565 /* both bits in buddy2 must be 0 */
566 MB_CHECK_ASSERT(mb_test_bit(i << 1, buddy2));
567 MB_CHECK_ASSERT(mb_test_bit((i << 1) + 1, buddy2));
568
569 for (j = 0; j < (1 << order); j++) {
570 k = (i * (1 << order)) + j;
571 MB_CHECK_ASSERT(
572 !mb_test_bit(k, EXT4_MB_BITMAP(e4b)));
573 }
574 count++;
575 }
576 MB_CHECK_ASSERT(e4b->bd_info->bb_counters[order] == count);
577 order--;
578 }
579
580 fstart = -1;
581 buddy = mb_find_buddy(e4b, 0, &max);
582 for (i = 0; i < max; i++) {
583 if (!mb_test_bit(i, buddy)) {
584 MB_CHECK_ASSERT(i >= e4b->bd_info->bb_first_free);
585 if (fstart == -1) {
586 fragments++;
587 fstart = i;
588 }
589 continue;
590 }
591 fstart = -1;
592 /* check used bits only */
593 for (j = 0; j < e4b->bd_blkbits + 1; j++) {
594 buddy2 = mb_find_buddy(e4b, j, &max2);
595 k = i >> j;
596 MB_CHECK_ASSERT(k < max2);
597 MB_CHECK_ASSERT(mb_test_bit(k, buddy2));
598 }
599 }
600 MB_CHECK_ASSERT(!EXT4_MB_GRP_NEED_INIT(e4b->bd_info));
601 MB_CHECK_ASSERT(e4b->bd_info->bb_fragments == fragments);
602
603 grp = ext4_get_group_info(sb, e4b->bd_group);
604 buddy = mb_find_buddy(e4b, 0, &max);
605 list_for_each(cur, &grp->bb_prealloc_list) {
606 ext4_group_t groupnr;
607 struct ext4_prealloc_space *pa;
Solofo Ramangalahy60bd63d2008-04-29 21:59:59 -0400608 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
609 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &groupnr, &k);
Alex Tomasc9de5602008-01-29 00:19:52 -0500610 MB_CHECK_ASSERT(groupnr == e4b->bd_group);
Solofo Ramangalahy60bd63d2008-04-29 21:59:59 -0400611 for (i = 0; i < pa->pa_len; i++)
Alex Tomasc9de5602008-01-29 00:19:52 -0500612 MB_CHECK_ASSERT(mb_test_bit(k + i, buddy));
613 }
614 return 0;
615}
616#undef MB_CHECK_ASSERT
617#define mb_check_buddy(e4b) __mb_check_buddy(e4b, \
Harvey Harrison46e665e2008-04-17 10:38:59 -0400618 __FILE__, __func__, __LINE__)
Alex Tomasc9de5602008-01-29 00:19:52 -0500619#else
620#define mb_check_buddy(e4b)
621#endif
622
623/* FIXME!! need more doc */
624static void ext4_mb_mark_free_simple(struct super_block *sb,
625 void *buddy, unsigned first, int len,
626 struct ext4_group_info *grp)
627{
628 struct ext4_sb_info *sbi = EXT4_SB(sb);
629 unsigned short min;
630 unsigned short max;
631 unsigned short chunk;
632 unsigned short border;
633
Valerie Clementb73fce62008-02-15 13:48:51 -0500634 BUG_ON(len > EXT4_BLOCKS_PER_GROUP(sb));
Alex Tomasc9de5602008-01-29 00:19:52 -0500635
636 border = 2 << sb->s_blocksize_bits;
637
638 while (len > 0) {
639 /* find how many blocks can be covered since this position */
640 max = ffs(first | border) - 1;
641
642 /* find how many blocks of power 2 we need to mark */
643 min = fls(len) - 1;
644
645 if (max < min)
646 min = max;
647 chunk = 1 << min;
648
649 /* mark multiblock chunks only */
650 grp->bb_counters[min]++;
651 if (min > 0)
652 mb_clear_bit(first >> min,
653 buddy + sbi->s_mb_offsets[min]);
654
655 len -= chunk;
656 first += chunk;
657 }
658}
659
Eric Sandeen089ceec2009-07-05 22:17:31 -0400660static noinline_for_stack
661void ext4_mb_generate_buddy(struct super_block *sb,
Alex Tomasc9de5602008-01-29 00:19:52 -0500662 void *buddy, void *bitmap, ext4_group_t group)
663{
664 struct ext4_group_info *grp = ext4_get_group_info(sb, group);
665 unsigned short max = EXT4_BLOCKS_PER_GROUP(sb);
666 unsigned short i = 0;
667 unsigned short first;
668 unsigned short len;
669 unsigned free = 0;
670 unsigned fragments = 0;
671 unsigned long long period = get_cycles();
672
673 /* initialize buddy from bitmap which is aggregation
674 * of on-disk bitmap and preallocations */
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500675 i = mb_find_next_zero_bit(bitmap, max, 0);
Alex Tomasc9de5602008-01-29 00:19:52 -0500676 grp->bb_first_free = i;
677 while (i < max) {
678 fragments++;
679 first = i;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500680 i = mb_find_next_bit(bitmap, max, i);
Alex Tomasc9de5602008-01-29 00:19:52 -0500681 len = i - first;
682 free += len;
683 if (len > 1)
684 ext4_mb_mark_free_simple(sb, buddy, first, len, grp);
685 else
686 grp->bb_counters[0]++;
687 if (i < max)
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500688 i = mb_find_next_zero_bit(bitmap, max, i);
Alex Tomasc9de5602008-01-29 00:19:52 -0500689 }
690 grp->bb_fragments = fragments;
691
692 if (free != grp->bb_free) {
Aneesh Kumar K.V5d1b1b32009-01-05 22:19:52 -0500693 ext4_grp_locked_error(sb, group, __func__,
Theodore Ts'oa9df9a42009-01-05 22:18:16 -0500694 "EXT4-fs: group %u: %u blocks in bitmap, %u in gd",
Alex Tomasc9de5602008-01-29 00:19:52 -0500695 group, free, grp->bb_free);
Aneesh Kumar K.Ve56eb652008-02-15 13:48:21 -0500696 /*
697 * If we intent to continue, we consider group descritor
698 * corrupt and update bb_free using bitmap value
699 */
Alex Tomasc9de5602008-01-29 00:19:52 -0500700 grp->bb_free = free;
701 }
702
703 clear_bit(EXT4_GROUP_INFO_NEED_INIT_BIT, &(grp->bb_state));
704
705 period = get_cycles() - period;
706 spin_lock(&EXT4_SB(sb)->s_bal_lock);
707 EXT4_SB(sb)->s_mb_buddies_generated++;
708 EXT4_SB(sb)->s_mb_generation_time += period;
709 spin_unlock(&EXT4_SB(sb)->s_bal_lock);
710}
711
712/* The buddy information is attached the buddy cache inode
713 * for convenience. The information regarding each group
714 * is loaded via ext4_mb_load_buddy. The information involve
715 * block bitmap and buddy information. The information are
716 * stored in the inode as
717 *
718 * { page }
Aneesh Kumar K.Vc3a326a2008-11-25 15:11:52 -0500719 * [ group 0 bitmap][ group 0 buddy] [group 1][ group 1]...
Alex Tomasc9de5602008-01-29 00:19:52 -0500720 *
721 *
722 * one block each for bitmap and buddy information.
723 * So for each group we take up 2 blocks. A page can
724 * contain blocks_per_page (PAGE_CACHE_SIZE / blocksize) blocks.
725 * So it can have information regarding groups_per_page which
726 * is blocks_per_page/2
727 */
728
729static int ext4_mb_init_cache(struct page *page, char *incore)
730{
Theodore Ts'o8df96752009-05-01 08:50:38 -0400731 ext4_group_t ngroups;
Alex Tomasc9de5602008-01-29 00:19:52 -0500732 int blocksize;
733 int blocks_per_page;
734 int groups_per_page;
735 int err = 0;
736 int i;
737 ext4_group_t first_group;
738 int first_block;
739 struct super_block *sb;
740 struct buffer_head *bhs;
741 struct buffer_head **bh;
742 struct inode *inode;
743 char *data;
744 char *bitmap;
745
746 mb_debug("init page %lu\n", page->index);
747
748 inode = page->mapping->host;
749 sb = inode->i_sb;
Theodore Ts'o8df96752009-05-01 08:50:38 -0400750 ngroups = ext4_get_groups_count(sb);
Alex Tomasc9de5602008-01-29 00:19:52 -0500751 blocksize = 1 << inode->i_blkbits;
752 blocks_per_page = PAGE_CACHE_SIZE / blocksize;
753
754 groups_per_page = blocks_per_page >> 1;
755 if (groups_per_page == 0)
756 groups_per_page = 1;
757
758 /* allocate buffer_heads to read bitmaps */
759 if (groups_per_page > 1) {
760 err = -ENOMEM;
761 i = sizeof(struct buffer_head *) * groups_per_page;
762 bh = kzalloc(i, GFP_NOFS);
763 if (bh == NULL)
764 goto out;
765 } else
766 bh = &bhs;
767
768 first_group = page->index * blocks_per_page / 2;
769
770 /* read all groups the page covers into the cache */
771 for (i = 0; i < groups_per_page; i++) {
772 struct ext4_group_desc *desc;
773
Theodore Ts'o8df96752009-05-01 08:50:38 -0400774 if (first_group + i >= ngroups)
Alex Tomasc9de5602008-01-29 00:19:52 -0500775 break;
776
777 err = -EIO;
778 desc = ext4_get_group_desc(sb, first_group + i, NULL);
779 if (desc == NULL)
780 goto out;
781
782 err = -ENOMEM;
783 bh[i] = sb_getblk(sb, ext4_block_bitmap(sb, desc));
784 if (bh[i] == NULL)
785 goto out;
786
Aneesh Kumar K.V2ccb5fb2009-01-05 21:49:55 -0500787 if (bitmap_uptodate(bh[i]))
Alex Tomasc9de5602008-01-29 00:19:52 -0500788 continue;
789
Frederic Bohec806e682008-10-10 08:09:18 -0400790 lock_buffer(bh[i]);
Aneesh Kumar K.V2ccb5fb2009-01-05 21:49:55 -0500791 if (bitmap_uptodate(bh[i])) {
792 unlock_buffer(bh[i]);
793 continue;
794 }
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -0400795 ext4_lock_group(sb, first_group + i);
Alex Tomasc9de5602008-01-29 00:19:52 -0500796 if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
797 ext4_init_block_bitmap(sb, bh[i],
798 first_group + i, desc);
Aneesh Kumar K.V2ccb5fb2009-01-05 21:49:55 -0500799 set_bitmap_uptodate(bh[i]);
Alex Tomasc9de5602008-01-29 00:19:52 -0500800 set_buffer_uptodate(bh[i]);
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -0400801 ext4_unlock_group(sb, first_group + i);
Aneesh Kumar K.V3300bed2009-01-03 22:33:39 -0500802 unlock_buffer(bh[i]);
Alex Tomasc9de5602008-01-29 00:19:52 -0500803 continue;
804 }
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -0400805 ext4_unlock_group(sb, first_group + i);
Aneesh Kumar K.V2ccb5fb2009-01-05 21:49:55 -0500806 if (buffer_uptodate(bh[i])) {
807 /*
808 * if not uninit if bh is uptodate,
809 * bitmap is also uptodate
810 */
811 set_bitmap_uptodate(bh[i]);
812 unlock_buffer(bh[i]);
813 continue;
814 }
Alex Tomasc9de5602008-01-29 00:19:52 -0500815 get_bh(bh[i]);
Aneesh Kumar K.V2ccb5fb2009-01-05 21:49:55 -0500816 /*
817 * submit the buffer_head for read. We can
818 * safely mark the bitmap as uptodate now.
819 * We do it here so the bitmap uptodate bit
820 * get set with buffer lock held.
821 */
822 set_bitmap_uptodate(bh[i]);
Alex Tomasc9de5602008-01-29 00:19:52 -0500823 bh[i]->b_end_io = end_buffer_read_sync;
824 submit_bh(READ, bh[i]);
Theodore Ts'oa9df9a42009-01-05 22:18:16 -0500825 mb_debug("read bitmap for group %u\n", first_group + i);
Alex Tomasc9de5602008-01-29 00:19:52 -0500826 }
827
828 /* wait for I/O completion */
829 for (i = 0; i < groups_per_page && bh[i]; i++)
830 wait_on_buffer(bh[i]);
831
832 err = -EIO;
833 for (i = 0; i < groups_per_page && bh[i]; i++)
834 if (!buffer_uptodate(bh[i]))
835 goto out;
836
Mingming Cao31b481d2008-07-11 19:27:31 -0400837 err = 0;
Alex Tomasc9de5602008-01-29 00:19:52 -0500838 first_block = page->index * blocks_per_page;
Aneesh Kumar K.V29eaf022009-01-05 21:48:56 -0500839 /* init the page */
840 memset(page_address(page), 0xff, PAGE_CACHE_SIZE);
Alex Tomasc9de5602008-01-29 00:19:52 -0500841 for (i = 0; i < blocks_per_page; i++) {
842 int group;
843 struct ext4_group_info *grinfo;
844
845 group = (first_block + i) >> 1;
Theodore Ts'o8df96752009-05-01 08:50:38 -0400846 if (group >= ngroups)
Alex Tomasc9de5602008-01-29 00:19:52 -0500847 break;
848
849 /*
850 * data carry information regarding this
851 * particular group in the format specified
852 * above
853 *
854 */
855 data = page_address(page) + (i * blocksize);
856 bitmap = bh[group - first_group]->b_data;
857
858 /*
859 * We place the buddy block and bitmap block
860 * close together
861 */
862 if ((first_block + i) & 1) {
863 /* this is block of buddy */
864 BUG_ON(incore == NULL);
865 mb_debug("put buddy for group %u in page %lu/%x\n",
866 group, page->index, i * blocksize);
Alex Tomasc9de5602008-01-29 00:19:52 -0500867 grinfo = ext4_get_group_info(sb, group);
868 grinfo->bb_fragments = 0;
869 memset(grinfo->bb_counters, 0,
870 sizeof(unsigned short)*(sb->s_blocksize_bits+2));
871 /*
872 * incore got set to the group block bitmap below
873 */
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -0500874 ext4_lock_group(sb, group);
Alex Tomasc9de5602008-01-29 00:19:52 -0500875 ext4_mb_generate_buddy(sb, data, incore, group);
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -0500876 ext4_unlock_group(sb, group);
Alex Tomasc9de5602008-01-29 00:19:52 -0500877 incore = NULL;
878 } else {
879 /* this is block of bitmap */
880 BUG_ON(incore != NULL);
881 mb_debug("put bitmap for group %u in page %lu/%x\n",
882 group, page->index, i * blocksize);
883
884 /* see comments in ext4_mb_put_pa() */
885 ext4_lock_group(sb, group);
886 memcpy(data, bitmap, blocksize);
887
888 /* mark all preallocated blks used in in-core bitmap */
889 ext4_mb_generate_from_pa(sb, data, group);
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -0500890 ext4_mb_generate_from_freelist(sb, data, group);
Alex Tomasc9de5602008-01-29 00:19:52 -0500891 ext4_unlock_group(sb, group);
892
893 /* set incore so that the buddy information can be
894 * generated using this
895 */
896 incore = data;
897 }
898 }
899 SetPageUptodate(page);
900
901out:
902 if (bh) {
903 for (i = 0; i < groups_per_page && bh[i]; i++)
904 brelse(bh[i]);
905 if (bh != &bhs)
906 kfree(bh);
907 }
908 return err;
909}
910
Eric Sandeen4ddfef72008-04-29 08:11:12 -0400911static noinline_for_stack int
912ext4_mb_load_buddy(struct super_block *sb, ext4_group_t group,
913 struct ext4_buddy *e4b)
Alex Tomasc9de5602008-01-29 00:19:52 -0500914{
Alex Tomasc9de5602008-01-29 00:19:52 -0500915 int blocks_per_page;
916 int block;
917 int pnum;
918 int poff;
919 struct page *page;
Shen Fengfdf6c7a2008-07-11 19:27:31 -0400920 int ret;
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -0500921 struct ext4_group_info *grp;
922 struct ext4_sb_info *sbi = EXT4_SB(sb);
923 struct inode *inode = sbi->s_buddy_cache;
Alex Tomasc9de5602008-01-29 00:19:52 -0500924
Theodore Ts'oa9df9a42009-01-05 22:18:16 -0500925 mb_debug("load group %u\n", group);
Alex Tomasc9de5602008-01-29 00:19:52 -0500926
927 blocks_per_page = PAGE_CACHE_SIZE / sb->s_blocksize;
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -0500928 grp = ext4_get_group_info(sb, group);
Alex Tomasc9de5602008-01-29 00:19:52 -0500929
930 e4b->bd_blkbits = sb->s_blocksize_bits;
931 e4b->bd_info = ext4_get_group_info(sb, group);
932 e4b->bd_sb = sb;
933 e4b->bd_group = group;
934 e4b->bd_buddy_page = NULL;
935 e4b->bd_bitmap_page = NULL;
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -0500936 e4b->alloc_semp = &grp->alloc_sem;
937
938 /* Take the read lock on the group alloc
939 * sem. This would make sure a parallel
940 * ext4_mb_init_group happening on other
941 * groups mapped by the page is blocked
942 * till we are done with allocation
943 */
944 down_read(e4b->alloc_semp);
Alex Tomasc9de5602008-01-29 00:19:52 -0500945
946 /*
947 * the buddy cache inode stores the block bitmap
948 * and buddy information in consecutive blocks.
949 * So for each group we need two blocks.
950 */
951 block = group * 2;
952 pnum = block / blocks_per_page;
953 poff = block % blocks_per_page;
954
955 /* we could use find_or_create_page(), but it locks page
956 * what we'd like to avoid in fast path ... */
957 page = find_get_page(inode->i_mapping, pnum);
958 if (page == NULL || !PageUptodate(page)) {
959 if (page)
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -0500960 /*
961 * drop the page reference and try
962 * to get the page with lock. If we
963 * are not uptodate that implies
964 * somebody just created the page but
965 * is yet to initialize the same. So
966 * wait for it to initialize.
967 */
Alex Tomasc9de5602008-01-29 00:19:52 -0500968 page_cache_release(page);
969 page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
970 if (page) {
971 BUG_ON(page->mapping != inode->i_mapping);
972 if (!PageUptodate(page)) {
Shen Fengfdf6c7a2008-07-11 19:27:31 -0400973 ret = ext4_mb_init_cache(page, NULL);
974 if (ret) {
975 unlock_page(page);
976 goto err;
977 }
Alex Tomasc9de5602008-01-29 00:19:52 -0500978 mb_cmp_bitmaps(e4b, page_address(page) +
979 (poff * sb->s_blocksize));
980 }
981 unlock_page(page);
982 }
983 }
Shen Fengfdf6c7a2008-07-11 19:27:31 -0400984 if (page == NULL || !PageUptodate(page)) {
985 ret = -EIO;
Alex Tomasc9de5602008-01-29 00:19:52 -0500986 goto err;
Shen Fengfdf6c7a2008-07-11 19:27:31 -0400987 }
Alex Tomasc9de5602008-01-29 00:19:52 -0500988 e4b->bd_bitmap_page = page;
989 e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);
990 mark_page_accessed(page);
991
992 block++;
993 pnum = block / blocks_per_page;
994 poff = block % blocks_per_page;
995
996 page = find_get_page(inode->i_mapping, pnum);
997 if (page == NULL || !PageUptodate(page)) {
998 if (page)
999 page_cache_release(page);
1000 page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
1001 if (page) {
1002 BUG_ON(page->mapping != inode->i_mapping);
Shen Fengfdf6c7a2008-07-11 19:27:31 -04001003 if (!PageUptodate(page)) {
1004 ret = ext4_mb_init_cache(page, e4b->bd_bitmap);
1005 if (ret) {
1006 unlock_page(page);
1007 goto err;
1008 }
1009 }
Alex Tomasc9de5602008-01-29 00:19:52 -05001010 unlock_page(page);
1011 }
1012 }
Shen Fengfdf6c7a2008-07-11 19:27:31 -04001013 if (page == NULL || !PageUptodate(page)) {
1014 ret = -EIO;
Alex Tomasc9de5602008-01-29 00:19:52 -05001015 goto err;
Shen Fengfdf6c7a2008-07-11 19:27:31 -04001016 }
Alex Tomasc9de5602008-01-29 00:19:52 -05001017 e4b->bd_buddy_page = page;
1018 e4b->bd_buddy = page_address(page) + (poff * sb->s_blocksize);
1019 mark_page_accessed(page);
1020
1021 BUG_ON(e4b->bd_bitmap_page == NULL);
1022 BUG_ON(e4b->bd_buddy_page == NULL);
1023
1024 return 0;
1025
1026err:
1027 if (e4b->bd_bitmap_page)
1028 page_cache_release(e4b->bd_bitmap_page);
1029 if (e4b->bd_buddy_page)
1030 page_cache_release(e4b->bd_buddy_page);
1031 e4b->bd_buddy = NULL;
1032 e4b->bd_bitmap = NULL;
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -05001033
1034 /* Done with the buddy cache */
1035 up_read(e4b->alloc_semp);
Shen Fengfdf6c7a2008-07-11 19:27:31 -04001036 return ret;
Alex Tomasc9de5602008-01-29 00:19:52 -05001037}
1038
1039static void ext4_mb_release_desc(struct ext4_buddy *e4b)
1040{
1041 if (e4b->bd_bitmap_page)
1042 page_cache_release(e4b->bd_bitmap_page);
1043 if (e4b->bd_buddy_page)
1044 page_cache_release(e4b->bd_buddy_page);
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -05001045 /* Done with the buddy cache */
Aneesh Kumar K.V8556e8f2009-01-05 21:46:55 -05001046 if (e4b->alloc_semp)
1047 up_read(e4b->alloc_semp);
Alex Tomasc9de5602008-01-29 00:19:52 -05001048}
1049
1050
1051static int mb_find_order_for_block(struct ext4_buddy *e4b, int block)
1052{
1053 int order = 1;
1054 void *bb;
1055
1056 BUG_ON(EXT4_MB_BITMAP(e4b) == EXT4_MB_BUDDY(e4b));
1057 BUG_ON(block >= (1 << (e4b->bd_blkbits + 3)));
1058
1059 bb = EXT4_MB_BUDDY(e4b);
1060 while (order <= e4b->bd_blkbits + 1) {
1061 block = block >> 1;
1062 if (!mb_test_bit(block, bb)) {
1063 /* this block is part of buddy of order 'order' */
1064 return order;
1065 }
1066 bb += 1 << (e4b->bd_blkbits - order);
1067 order++;
1068 }
1069 return 0;
1070}
1071
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04001072static void mb_clear_bits(void *bm, int cur, int len)
Alex Tomasc9de5602008-01-29 00:19:52 -05001073{
1074 __u32 *addr;
1075
1076 len = cur + len;
1077 while (cur < len) {
1078 if ((cur & 31) == 0 && (len - cur) >= 32) {
1079 /* fast path: clear whole word at once */
1080 addr = bm + (cur >> 3);
1081 *addr = 0;
1082 cur += 32;
1083 continue;
1084 }
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04001085 mb_clear_bit(cur, bm);
Alex Tomasc9de5602008-01-29 00:19:52 -05001086 cur++;
1087 }
1088}
1089
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04001090static void mb_set_bits(void *bm, int cur, int len)
Alex Tomasc9de5602008-01-29 00:19:52 -05001091{
1092 __u32 *addr;
1093
1094 len = cur + len;
1095 while (cur < len) {
1096 if ((cur & 31) == 0 && (len - cur) >= 32) {
1097 /* fast path: set whole word at once */
1098 addr = bm + (cur >> 3);
1099 *addr = 0xffffffff;
1100 cur += 32;
1101 continue;
1102 }
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04001103 mb_set_bit(cur, bm);
Alex Tomasc9de5602008-01-29 00:19:52 -05001104 cur++;
1105 }
1106}
1107
Shen Feng7e5a8cd2008-07-13 21:03:31 -04001108static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,
Alex Tomasc9de5602008-01-29 00:19:52 -05001109 int first, int count)
1110{
1111 int block = 0;
1112 int max = 0;
1113 int order;
1114 void *buddy;
1115 void *buddy2;
1116 struct super_block *sb = e4b->bd_sb;
1117
1118 BUG_ON(first + count > (sb->s_blocksize << 3));
Vincent Minetbc8e6742009-05-15 08:33:18 -04001119 assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));
Alex Tomasc9de5602008-01-29 00:19:52 -05001120 mb_check_buddy(e4b);
1121 mb_free_blocks_double(inode, e4b, first, count);
1122
1123 e4b->bd_info->bb_free += count;
1124 if (first < e4b->bd_info->bb_first_free)
1125 e4b->bd_info->bb_first_free = first;
1126
1127 /* let's maintain fragments counter */
1128 if (first != 0)
1129 block = !mb_test_bit(first - 1, EXT4_MB_BITMAP(e4b));
1130 if (first + count < EXT4_SB(sb)->s_mb_maxs[0])
1131 max = !mb_test_bit(first + count, EXT4_MB_BITMAP(e4b));
1132 if (block && max)
1133 e4b->bd_info->bb_fragments--;
1134 else if (!block && !max)
1135 e4b->bd_info->bb_fragments++;
1136
1137 /* let's maintain buddy itself */
1138 while (count-- > 0) {
1139 block = first++;
1140 order = 0;
1141
1142 if (!mb_test_bit(block, EXT4_MB_BITMAP(e4b))) {
1143 ext4_fsblk_t blocknr;
1144 blocknr = e4b->bd_group * EXT4_BLOCKS_PER_GROUP(sb);
1145 blocknr += block;
1146 blocknr +=
1147 le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);
Aneesh Kumar K.V5d1b1b32009-01-05 22:19:52 -05001148 ext4_grp_locked_error(sb, e4b->bd_group,
1149 __func__, "double-free of inode"
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05001150 " %lu's block %llu(bit %u in group %u)",
Alex Tomasc9de5602008-01-29 00:19:52 -05001151 inode ? inode->i_ino : 0, blocknr, block,
1152 e4b->bd_group);
1153 }
1154 mb_clear_bit(block, EXT4_MB_BITMAP(e4b));
1155 e4b->bd_info->bb_counters[order]++;
1156
1157 /* start of the buddy */
1158 buddy = mb_find_buddy(e4b, order, &max);
1159
1160 do {
1161 block &= ~1UL;
1162 if (mb_test_bit(block, buddy) ||
1163 mb_test_bit(block + 1, buddy))
1164 break;
1165
1166 /* both the buddies are free, try to coalesce them */
1167 buddy2 = mb_find_buddy(e4b, order + 1, &max);
1168
1169 if (!buddy2)
1170 break;
1171
1172 if (order > 0) {
1173 /* for special purposes, we don't set
1174 * free bits in bitmap */
1175 mb_set_bit(block, buddy);
1176 mb_set_bit(block + 1, buddy);
1177 }
1178 e4b->bd_info->bb_counters[order]--;
1179 e4b->bd_info->bb_counters[order]--;
1180
1181 block = block >> 1;
1182 order++;
1183 e4b->bd_info->bb_counters[order]++;
1184
1185 mb_clear_bit(block, buddy2);
1186 buddy = buddy2;
1187 } while (1);
1188 }
1189 mb_check_buddy(e4b);
Alex Tomasc9de5602008-01-29 00:19:52 -05001190}
1191
1192static int mb_find_extent(struct ext4_buddy *e4b, int order, int block,
1193 int needed, struct ext4_free_extent *ex)
1194{
1195 int next = block;
1196 int max;
1197 int ord;
1198 void *buddy;
1199
Vincent Minetbc8e6742009-05-15 08:33:18 -04001200 assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
Alex Tomasc9de5602008-01-29 00:19:52 -05001201 BUG_ON(ex == NULL);
1202
1203 buddy = mb_find_buddy(e4b, order, &max);
1204 BUG_ON(buddy == NULL);
1205 BUG_ON(block >= max);
1206 if (mb_test_bit(block, buddy)) {
1207 ex->fe_len = 0;
1208 ex->fe_start = 0;
1209 ex->fe_group = 0;
1210 return 0;
1211 }
1212
1213 /* FIXME dorp order completely ? */
1214 if (likely(order == 0)) {
1215 /* find actual order */
1216 order = mb_find_order_for_block(e4b, block);
1217 block = block >> order;
1218 }
1219
1220 ex->fe_len = 1 << order;
1221 ex->fe_start = block << order;
1222 ex->fe_group = e4b->bd_group;
1223
1224 /* calc difference from given start */
1225 next = next - ex->fe_start;
1226 ex->fe_len -= next;
1227 ex->fe_start += next;
1228
1229 while (needed > ex->fe_len &&
1230 (buddy = mb_find_buddy(e4b, order, &max))) {
1231
1232 if (block + 1 >= max)
1233 break;
1234
1235 next = (block + 1) * (1 << order);
1236 if (mb_test_bit(next, EXT4_MB_BITMAP(e4b)))
1237 break;
1238
1239 ord = mb_find_order_for_block(e4b, next);
1240
1241 order = ord;
1242 block = next >> order;
1243 ex->fe_len += 1 << order;
1244 }
1245
1246 BUG_ON(ex->fe_start + ex->fe_len > (1 << (e4b->bd_blkbits + 3)));
1247 return ex->fe_len;
1248}
1249
1250static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
1251{
1252 int ord;
1253 int mlen = 0;
1254 int max = 0;
1255 int cur;
1256 int start = ex->fe_start;
1257 int len = ex->fe_len;
1258 unsigned ret = 0;
1259 int len0 = len;
1260 void *buddy;
1261
1262 BUG_ON(start + len > (e4b->bd_sb->s_blocksize << 3));
1263 BUG_ON(e4b->bd_group != ex->fe_group);
Vincent Minetbc8e6742009-05-15 08:33:18 -04001264 assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
Alex Tomasc9de5602008-01-29 00:19:52 -05001265 mb_check_buddy(e4b);
1266 mb_mark_used_double(e4b, start, len);
1267
1268 e4b->bd_info->bb_free -= len;
1269 if (e4b->bd_info->bb_first_free == start)
1270 e4b->bd_info->bb_first_free += len;
1271
1272 /* let's maintain fragments counter */
1273 if (start != 0)
1274 mlen = !mb_test_bit(start - 1, EXT4_MB_BITMAP(e4b));
1275 if (start + len < EXT4_SB(e4b->bd_sb)->s_mb_maxs[0])
1276 max = !mb_test_bit(start + len, EXT4_MB_BITMAP(e4b));
1277 if (mlen && max)
1278 e4b->bd_info->bb_fragments++;
1279 else if (!mlen && !max)
1280 e4b->bd_info->bb_fragments--;
1281
1282 /* let's maintain buddy itself */
1283 while (len) {
1284 ord = mb_find_order_for_block(e4b, start);
1285
1286 if (((start >> ord) << ord) == start && len >= (1 << ord)) {
1287 /* the whole chunk may be allocated at once! */
1288 mlen = 1 << ord;
1289 buddy = mb_find_buddy(e4b, ord, &max);
1290 BUG_ON((start >> ord) >= max);
1291 mb_set_bit(start >> ord, buddy);
1292 e4b->bd_info->bb_counters[ord]--;
1293 start += mlen;
1294 len -= mlen;
1295 BUG_ON(len < 0);
1296 continue;
1297 }
1298
1299 /* store for history */
1300 if (ret == 0)
1301 ret = len | (ord << 16);
1302
1303 /* we have to split large buddy */
1304 BUG_ON(ord <= 0);
1305 buddy = mb_find_buddy(e4b, ord, &max);
1306 mb_set_bit(start >> ord, buddy);
1307 e4b->bd_info->bb_counters[ord]--;
1308
1309 ord--;
1310 cur = (start >> ord) & ~1U;
1311 buddy = mb_find_buddy(e4b, ord, &max);
1312 mb_clear_bit(cur, buddy);
1313 mb_clear_bit(cur + 1, buddy);
1314 e4b->bd_info->bb_counters[ord]++;
1315 e4b->bd_info->bb_counters[ord]++;
1316 }
1317
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04001318 mb_set_bits(EXT4_MB_BITMAP(e4b), ex->fe_start, len0);
Alex Tomasc9de5602008-01-29 00:19:52 -05001319 mb_check_buddy(e4b);
1320
1321 return ret;
1322}
1323
1324/*
1325 * Must be called under group lock!
1326 */
1327static void ext4_mb_use_best_found(struct ext4_allocation_context *ac,
1328 struct ext4_buddy *e4b)
1329{
1330 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1331 int ret;
1332
1333 BUG_ON(ac->ac_b_ex.fe_group != e4b->bd_group);
1334 BUG_ON(ac->ac_status == AC_STATUS_FOUND);
1335
1336 ac->ac_b_ex.fe_len = min(ac->ac_b_ex.fe_len, ac->ac_g_ex.fe_len);
1337 ac->ac_b_ex.fe_logical = ac->ac_g_ex.fe_logical;
1338 ret = mb_mark_used(e4b, &ac->ac_b_ex);
1339
1340 /* preallocation can change ac_b_ex, thus we store actually
1341 * allocated blocks for history */
1342 ac->ac_f_ex = ac->ac_b_ex;
1343
1344 ac->ac_status = AC_STATUS_FOUND;
1345 ac->ac_tail = ret & 0xffff;
1346 ac->ac_buddy = ret >> 16;
1347
Aneesh Kumar K.Vc3a326a2008-11-25 15:11:52 -05001348 /*
1349 * take the page reference. We want the page to be pinned
1350 * so that we don't get a ext4_mb_init_cache_call for this
1351 * group until we update the bitmap. That would mean we
1352 * double allocate blocks. The reference is dropped
1353 * in ext4_mb_release_context
1354 */
Alex Tomasc9de5602008-01-29 00:19:52 -05001355 ac->ac_bitmap_page = e4b->bd_bitmap_page;
1356 get_page(ac->ac_bitmap_page);
1357 ac->ac_buddy_page = e4b->bd_buddy_page;
1358 get_page(ac->ac_buddy_page);
Aneesh Kumar K.V8556e8f2009-01-05 21:46:55 -05001359 /* on allocation we use ac to track the held semaphore */
1360 ac->alloc_semp = e4b->alloc_semp;
1361 e4b->alloc_semp = NULL;
Alex Tomasc9de5602008-01-29 00:19:52 -05001362 /* store last allocated for subsequent stream allocation */
1363 if ((ac->ac_flags & EXT4_MB_HINT_DATA)) {
1364 spin_lock(&sbi->s_md_lock);
1365 sbi->s_mb_last_group = ac->ac_f_ex.fe_group;
1366 sbi->s_mb_last_start = ac->ac_f_ex.fe_start;
1367 spin_unlock(&sbi->s_md_lock);
1368 }
1369}
1370
1371/*
1372 * regular allocator, for general purposes allocation
1373 */
1374
1375static void ext4_mb_check_limits(struct ext4_allocation_context *ac,
1376 struct ext4_buddy *e4b,
1377 int finish_group)
1378{
1379 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1380 struct ext4_free_extent *bex = &ac->ac_b_ex;
1381 struct ext4_free_extent *gex = &ac->ac_g_ex;
1382 struct ext4_free_extent ex;
1383 int max;
1384
Aneesh Kumar K.V032115f2009-01-05 21:34:30 -05001385 if (ac->ac_status == AC_STATUS_FOUND)
1386 return;
Alex Tomasc9de5602008-01-29 00:19:52 -05001387 /*
1388 * We don't want to scan for a whole year
1389 */
1390 if (ac->ac_found > sbi->s_mb_max_to_scan &&
1391 !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
1392 ac->ac_status = AC_STATUS_BREAK;
1393 return;
1394 }
1395
1396 /*
1397 * Haven't found good chunk so far, let's continue
1398 */
1399 if (bex->fe_len < gex->fe_len)
1400 return;
1401
1402 if ((finish_group || ac->ac_found > sbi->s_mb_min_to_scan)
1403 && bex->fe_group == e4b->bd_group) {
1404 /* recheck chunk's availability - we don't know
1405 * when it was found (within this lock-unlock
1406 * period or not) */
1407 max = mb_find_extent(e4b, 0, bex->fe_start, gex->fe_len, &ex);
1408 if (max >= gex->fe_len) {
1409 ext4_mb_use_best_found(ac, e4b);
1410 return;
1411 }
1412 }
1413}
1414
1415/*
1416 * The routine checks whether found extent is good enough. If it is,
1417 * then the extent gets marked used and flag is set to the context
1418 * to stop scanning. Otherwise, the extent is compared with the
1419 * previous found extent and if new one is better, then it's stored
1420 * in the context. Later, the best found extent will be used, if
1421 * mballoc can't find good enough extent.
1422 *
1423 * FIXME: real allocation policy is to be designed yet!
1424 */
1425static void ext4_mb_measure_extent(struct ext4_allocation_context *ac,
1426 struct ext4_free_extent *ex,
1427 struct ext4_buddy *e4b)
1428{
1429 struct ext4_free_extent *bex = &ac->ac_b_ex;
1430 struct ext4_free_extent *gex = &ac->ac_g_ex;
1431
1432 BUG_ON(ex->fe_len <= 0);
Eric Sandeen8d03c7a2009-03-14 11:51:46 -04001433 BUG_ON(ex->fe_len > EXT4_BLOCKS_PER_GROUP(ac->ac_sb));
Alex Tomasc9de5602008-01-29 00:19:52 -05001434 BUG_ON(ex->fe_start >= EXT4_BLOCKS_PER_GROUP(ac->ac_sb));
1435 BUG_ON(ac->ac_status != AC_STATUS_CONTINUE);
1436
1437 ac->ac_found++;
1438
1439 /*
1440 * The special case - take what you catch first
1441 */
1442 if (unlikely(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
1443 *bex = *ex;
1444 ext4_mb_use_best_found(ac, e4b);
1445 return;
1446 }
1447
1448 /*
1449 * Let's check whether the chuck is good enough
1450 */
1451 if (ex->fe_len == gex->fe_len) {
1452 *bex = *ex;
1453 ext4_mb_use_best_found(ac, e4b);
1454 return;
1455 }
1456
1457 /*
1458 * If this is first found extent, just store it in the context
1459 */
1460 if (bex->fe_len == 0) {
1461 *bex = *ex;
1462 return;
1463 }
1464
1465 /*
1466 * If new found extent is better, store it in the context
1467 */
1468 if (bex->fe_len < gex->fe_len) {
1469 /* if the request isn't satisfied, any found extent
1470 * larger than previous best one is better */
1471 if (ex->fe_len > bex->fe_len)
1472 *bex = *ex;
1473 } else if (ex->fe_len > gex->fe_len) {
1474 /* if the request is satisfied, then we try to find
1475 * an extent that still satisfy the request, but is
1476 * smaller than previous one */
1477 if (ex->fe_len < bex->fe_len)
1478 *bex = *ex;
1479 }
1480
1481 ext4_mb_check_limits(ac, e4b, 0);
1482}
1483
Eric Sandeen089ceec2009-07-05 22:17:31 -04001484static noinline_for_stack
1485int ext4_mb_try_best_found(struct ext4_allocation_context *ac,
Alex Tomasc9de5602008-01-29 00:19:52 -05001486 struct ext4_buddy *e4b)
1487{
1488 struct ext4_free_extent ex = ac->ac_b_ex;
1489 ext4_group_t group = ex.fe_group;
1490 int max;
1491 int err;
1492
1493 BUG_ON(ex.fe_len <= 0);
1494 err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);
1495 if (err)
1496 return err;
1497
1498 ext4_lock_group(ac->ac_sb, group);
1499 max = mb_find_extent(e4b, 0, ex.fe_start, ex.fe_len, &ex);
1500
1501 if (max > 0) {
1502 ac->ac_b_ex = ex;
1503 ext4_mb_use_best_found(ac, e4b);
1504 }
1505
1506 ext4_unlock_group(ac->ac_sb, group);
1507 ext4_mb_release_desc(e4b);
1508
1509 return 0;
1510}
1511
Eric Sandeen089ceec2009-07-05 22:17:31 -04001512static noinline_for_stack
1513int ext4_mb_find_by_goal(struct ext4_allocation_context *ac,
Alex Tomasc9de5602008-01-29 00:19:52 -05001514 struct ext4_buddy *e4b)
1515{
1516 ext4_group_t group = ac->ac_g_ex.fe_group;
1517 int max;
1518 int err;
1519 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1520 struct ext4_super_block *es = sbi->s_es;
1521 struct ext4_free_extent ex;
1522
1523 if (!(ac->ac_flags & EXT4_MB_HINT_TRY_GOAL))
1524 return 0;
1525
1526 err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);
1527 if (err)
1528 return err;
1529
1530 ext4_lock_group(ac->ac_sb, group);
1531 max = mb_find_extent(e4b, 0, ac->ac_g_ex.fe_start,
1532 ac->ac_g_ex.fe_len, &ex);
1533
1534 if (max >= ac->ac_g_ex.fe_len && ac->ac_g_ex.fe_len == sbi->s_stripe) {
1535 ext4_fsblk_t start;
1536
1537 start = (e4b->bd_group * EXT4_BLOCKS_PER_GROUP(ac->ac_sb)) +
1538 ex.fe_start + le32_to_cpu(es->s_first_data_block);
1539 /* use do_div to get remainder (would be 64-bit modulo) */
1540 if (do_div(start, sbi->s_stripe) == 0) {
1541 ac->ac_found++;
1542 ac->ac_b_ex = ex;
1543 ext4_mb_use_best_found(ac, e4b);
1544 }
1545 } else if (max >= ac->ac_g_ex.fe_len) {
1546 BUG_ON(ex.fe_len <= 0);
1547 BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
1548 BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
1549 ac->ac_found++;
1550 ac->ac_b_ex = ex;
1551 ext4_mb_use_best_found(ac, e4b);
1552 } else if (max > 0 && (ac->ac_flags & EXT4_MB_HINT_MERGE)) {
1553 /* Sometimes, caller may want to merge even small
1554 * number of blocks to an existing extent */
1555 BUG_ON(ex.fe_len <= 0);
1556 BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
1557 BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
1558 ac->ac_found++;
1559 ac->ac_b_ex = ex;
1560 ext4_mb_use_best_found(ac, e4b);
1561 }
1562 ext4_unlock_group(ac->ac_sb, group);
1563 ext4_mb_release_desc(e4b);
1564
1565 return 0;
1566}
1567
1568/*
1569 * The routine scans buddy structures (not bitmap!) from given order
1570 * to max order and tries to find big enough chunk to satisfy the req
1571 */
Eric Sandeen089ceec2009-07-05 22:17:31 -04001572static noinline_for_stack
1573void ext4_mb_simple_scan_group(struct ext4_allocation_context *ac,
Alex Tomasc9de5602008-01-29 00:19:52 -05001574 struct ext4_buddy *e4b)
1575{
1576 struct super_block *sb = ac->ac_sb;
1577 struct ext4_group_info *grp = e4b->bd_info;
1578 void *buddy;
1579 int i;
1580 int k;
1581 int max;
1582
1583 BUG_ON(ac->ac_2order <= 0);
1584 for (i = ac->ac_2order; i <= sb->s_blocksize_bits + 1; i++) {
1585 if (grp->bb_counters[i] == 0)
1586 continue;
1587
1588 buddy = mb_find_buddy(e4b, i, &max);
1589 BUG_ON(buddy == NULL);
1590
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -05001591 k = mb_find_next_zero_bit(buddy, max, 0);
Alex Tomasc9de5602008-01-29 00:19:52 -05001592 BUG_ON(k >= max);
1593
1594 ac->ac_found++;
1595
1596 ac->ac_b_ex.fe_len = 1 << i;
1597 ac->ac_b_ex.fe_start = k << i;
1598 ac->ac_b_ex.fe_group = e4b->bd_group;
1599
1600 ext4_mb_use_best_found(ac, e4b);
1601
1602 BUG_ON(ac->ac_b_ex.fe_len != ac->ac_g_ex.fe_len);
1603
1604 if (EXT4_SB(sb)->s_mb_stats)
1605 atomic_inc(&EXT4_SB(sb)->s_bal_2orders);
1606
1607 break;
1608 }
1609}
1610
1611/*
1612 * The routine scans the group and measures all found extents.
1613 * In order to optimize scanning, caller must pass number of
1614 * free blocks in the group, so the routine can know upper limit.
1615 */
Eric Sandeen089ceec2009-07-05 22:17:31 -04001616static noinline_for_stack
1617void ext4_mb_complex_scan_group(struct ext4_allocation_context *ac,
Alex Tomasc9de5602008-01-29 00:19:52 -05001618 struct ext4_buddy *e4b)
1619{
1620 struct super_block *sb = ac->ac_sb;
1621 void *bitmap = EXT4_MB_BITMAP(e4b);
1622 struct ext4_free_extent ex;
1623 int i;
1624 int free;
1625
1626 free = e4b->bd_info->bb_free;
1627 BUG_ON(free <= 0);
1628
1629 i = e4b->bd_info->bb_first_free;
1630
1631 while (free && ac->ac_status == AC_STATUS_CONTINUE) {
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -05001632 i = mb_find_next_zero_bit(bitmap,
Alex Tomasc9de5602008-01-29 00:19:52 -05001633 EXT4_BLOCKS_PER_GROUP(sb), i);
1634 if (i >= EXT4_BLOCKS_PER_GROUP(sb)) {
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05001635 /*
Aneesh Kumar K.Ve56eb652008-02-15 13:48:21 -05001636 * IF we have corrupt bitmap, we won't find any
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05001637 * free blocks even though group info says we
1638 * we have free blocks
1639 */
Aneesh Kumar K.V5d1b1b32009-01-05 22:19:52 -05001640 ext4_grp_locked_error(sb, e4b->bd_group,
1641 __func__, "%d free blocks as per "
Theodore Ts'ofde4d952009-01-05 22:17:35 -05001642 "group info. But bitmap says 0",
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05001643 free);
Alex Tomasc9de5602008-01-29 00:19:52 -05001644 break;
1645 }
1646
1647 mb_find_extent(e4b, 0, i, ac->ac_g_ex.fe_len, &ex);
1648 BUG_ON(ex.fe_len <= 0);
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05001649 if (free < ex.fe_len) {
Aneesh Kumar K.V5d1b1b32009-01-05 22:19:52 -05001650 ext4_grp_locked_error(sb, e4b->bd_group,
1651 __func__, "%d free blocks as per "
Theodore Ts'ofde4d952009-01-05 22:17:35 -05001652 "group info. But got %d blocks",
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05001653 free, ex.fe_len);
Aneesh Kumar K.Ve56eb652008-02-15 13:48:21 -05001654 /*
1655 * The number of free blocks differs. This mostly
1656 * indicate that the bitmap is corrupt. So exit
1657 * without claiming the space.
1658 */
1659 break;
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05001660 }
Alex Tomasc9de5602008-01-29 00:19:52 -05001661
1662 ext4_mb_measure_extent(ac, &ex, e4b);
1663
1664 i += ex.fe_len;
1665 free -= ex.fe_len;
1666 }
1667
1668 ext4_mb_check_limits(ac, e4b, 1);
1669}
1670
1671/*
1672 * This is a special case for storages like raid5
1673 * we try to find stripe-aligned chunks for stripe-size requests
1674 * XXX should do so at least for multiples of stripe size as well
1675 */
Eric Sandeen089ceec2009-07-05 22:17:31 -04001676static noinline_for_stack
1677void ext4_mb_scan_aligned(struct ext4_allocation_context *ac,
Alex Tomasc9de5602008-01-29 00:19:52 -05001678 struct ext4_buddy *e4b)
1679{
1680 struct super_block *sb = ac->ac_sb;
1681 struct ext4_sb_info *sbi = EXT4_SB(sb);
1682 void *bitmap = EXT4_MB_BITMAP(e4b);
1683 struct ext4_free_extent ex;
1684 ext4_fsblk_t first_group_block;
1685 ext4_fsblk_t a;
1686 ext4_grpblk_t i;
1687 int max;
1688
1689 BUG_ON(sbi->s_stripe == 0);
1690
1691 /* find first stripe-aligned block in group */
1692 first_group_block = e4b->bd_group * EXT4_BLOCKS_PER_GROUP(sb)
1693 + le32_to_cpu(sbi->s_es->s_first_data_block);
1694 a = first_group_block + sbi->s_stripe - 1;
1695 do_div(a, sbi->s_stripe);
1696 i = (a * sbi->s_stripe) - first_group_block;
1697
1698 while (i < EXT4_BLOCKS_PER_GROUP(sb)) {
1699 if (!mb_test_bit(i, bitmap)) {
1700 max = mb_find_extent(e4b, 0, i, sbi->s_stripe, &ex);
1701 if (max >= sbi->s_stripe) {
1702 ac->ac_found++;
1703 ac->ac_b_ex = ex;
1704 ext4_mb_use_best_found(ac, e4b);
1705 break;
1706 }
1707 }
1708 i += sbi->s_stripe;
1709 }
1710}
1711
1712static int ext4_mb_good_group(struct ext4_allocation_context *ac,
1713 ext4_group_t group, int cr)
1714{
1715 unsigned free, fragments;
1716 unsigned i, bits;
Theodore Ts'oa4912122009-03-12 12:18:34 -04001717 int flex_size = ext4_flex_bg_size(EXT4_SB(ac->ac_sb));
Alex Tomasc9de5602008-01-29 00:19:52 -05001718 struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);
1719
1720 BUG_ON(cr < 0 || cr >= 4);
1721 BUG_ON(EXT4_MB_GRP_NEED_INIT(grp));
1722
1723 free = grp->bb_free;
1724 fragments = grp->bb_fragments;
1725 if (free == 0)
1726 return 0;
1727 if (fragments == 0)
1728 return 0;
1729
1730 switch (cr) {
1731 case 0:
1732 BUG_ON(ac->ac_2order == 0);
Alex Tomasc9de5602008-01-29 00:19:52 -05001733
Theodore Ts'oa4912122009-03-12 12:18:34 -04001734 /* Avoid using the first bg of a flexgroup for data files */
1735 if ((ac->ac_flags & EXT4_MB_HINT_DATA) &&
1736 (flex_size >= EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME) &&
1737 ((group % flex_size) == 0))
1738 return 0;
1739
Alex Tomasc9de5602008-01-29 00:19:52 -05001740 bits = ac->ac_sb->s_blocksize_bits + 1;
1741 for (i = ac->ac_2order; i <= bits; i++)
1742 if (grp->bb_counters[i] > 0)
1743 return 1;
1744 break;
1745 case 1:
1746 if ((free / fragments) >= ac->ac_g_ex.fe_len)
1747 return 1;
1748 break;
1749 case 2:
1750 if (free >= ac->ac_g_ex.fe_len)
1751 return 1;
1752 break;
1753 case 3:
1754 return 1;
1755 default:
1756 BUG();
1757 }
1758
1759 return 0;
1760}
1761
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -05001762/*
1763 * lock the group_info alloc_sem of all the groups
1764 * belonging to the same buddy cache page. This
1765 * make sure other parallel operation on the buddy
1766 * cache doesn't happen whild holding the buddy cache
1767 * lock
1768 */
1769int ext4_mb_get_buddy_cache_lock(struct super_block *sb, ext4_group_t group)
1770{
1771 int i;
1772 int block, pnum;
1773 int blocks_per_page;
1774 int groups_per_page;
Theodore Ts'o8df96752009-05-01 08:50:38 -04001775 ext4_group_t ngroups = ext4_get_groups_count(sb);
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -05001776 ext4_group_t first_group;
1777 struct ext4_group_info *grp;
1778
1779 blocks_per_page = PAGE_CACHE_SIZE / sb->s_blocksize;
1780 /*
1781 * the buddy cache inode stores the block bitmap
1782 * and buddy information in consecutive blocks.
1783 * So for each group we need two blocks.
1784 */
1785 block = group * 2;
1786 pnum = block / blocks_per_page;
1787 first_group = pnum * blocks_per_page / 2;
1788
1789 groups_per_page = blocks_per_page >> 1;
1790 if (groups_per_page == 0)
1791 groups_per_page = 1;
1792 /* read all groups the page covers into the cache */
1793 for (i = 0; i < groups_per_page; i++) {
1794
Theodore Ts'o8df96752009-05-01 08:50:38 -04001795 if ((first_group + i) >= ngroups)
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -05001796 break;
1797 grp = ext4_get_group_info(sb, first_group + i);
1798 /* take all groups write allocation
1799 * semaphore. This make sure there is
1800 * no block allocation going on in any
1801 * of that groups
1802 */
Aneesh Kumar K.Vb7be0192008-11-23 23:51:53 -05001803 down_write_nested(&grp->alloc_sem, i);
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -05001804 }
1805 return i;
1806}
1807
1808void ext4_mb_put_buddy_cache_lock(struct super_block *sb,
1809 ext4_group_t group, int locked_group)
1810{
1811 int i;
1812 int block, pnum;
1813 int blocks_per_page;
1814 ext4_group_t first_group;
1815 struct ext4_group_info *grp;
1816
1817 blocks_per_page = PAGE_CACHE_SIZE / sb->s_blocksize;
1818 /*
1819 * the buddy cache inode stores the block bitmap
1820 * and buddy information in consecutive blocks.
1821 * So for each group we need two blocks.
1822 */
1823 block = group * 2;
1824 pnum = block / blocks_per_page;
1825 first_group = pnum * blocks_per_page / 2;
1826 /* release locks on all the groups */
1827 for (i = 0; i < locked_group; i++) {
1828
1829 grp = ext4_get_group_info(sb, first_group + i);
1830 /* take all groups write allocation
1831 * semaphore. This make sure there is
1832 * no block allocation going on in any
1833 * of that groups
1834 */
1835 up_write(&grp->alloc_sem);
1836 }
1837
1838}
1839
Eric Sandeen089ceec2009-07-05 22:17:31 -04001840static noinline_for_stack
1841int ext4_mb_init_group(struct super_block *sb, ext4_group_t group)
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -05001842{
1843
1844 int ret;
1845 void *bitmap;
1846 int blocks_per_page;
1847 int block, pnum, poff;
1848 int num_grp_locked = 0;
1849 struct ext4_group_info *this_grp;
1850 struct ext4_sb_info *sbi = EXT4_SB(sb);
1851 struct inode *inode = sbi->s_buddy_cache;
1852 struct page *page = NULL, *bitmap_page = NULL;
1853
1854 mb_debug("init group %lu\n", group);
1855 blocks_per_page = PAGE_CACHE_SIZE / sb->s_blocksize;
1856 this_grp = ext4_get_group_info(sb, group);
1857 /*
1858 * This ensures we don't add group
1859 * to this buddy cache via resize
1860 */
1861 num_grp_locked = ext4_mb_get_buddy_cache_lock(sb, group);
1862 if (!EXT4_MB_GRP_NEED_INIT(this_grp)) {
1863 /*
1864 * somebody initialized the group
1865 * return without doing anything
1866 */
1867 ret = 0;
1868 goto err;
1869 }
1870 /*
1871 * the buddy cache inode stores the block bitmap
1872 * and buddy information in consecutive blocks.
1873 * So for each group we need two blocks.
1874 */
1875 block = group * 2;
1876 pnum = block / blocks_per_page;
1877 poff = block % blocks_per_page;
1878 page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
1879 if (page) {
1880 BUG_ON(page->mapping != inode->i_mapping);
1881 ret = ext4_mb_init_cache(page, NULL);
1882 if (ret) {
1883 unlock_page(page);
1884 goto err;
1885 }
1886 unlock_page(page);
1887 }
1888 if (page == NULL || !PageUptodate(page)) {
1889 ret = -EIO;
1890 goto err;
1891 }
1892 mark_page_accessed(page);
1893 bitmap_page = page;
1894 bitmap = page_address(page) + (poff * sb->s_blocksize);
1895
1896 /* init buddy cache */
1897 block++;
1898 pnum = block / blocks_per_page;
1899 poff = block % blocks_per_page;
1900 page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
1901 if (page == bitmap_page) {
1902 /*
1903 * If both the bitmap and buddy are in
1904 * the same page we don't need to force
1905 * init the buddy
1906 */
1907 unlock_page(page);
1908 } else if (page) {
1909 BUG_ON(page->mapping != inode->i_mapping);
1910 ret = ext4_mb_init_cache(page, bitmap);
1911 if (ret) {
1912 unlock_page(page);
1913 goto err;
1914 }
1915 unlock_page(page);
1916 }
1917 if (page == NULL || !PageUptodate(page)) {
1918 ret = -EIO;
1919 goto err;
1920 }
1921 mark_page_accessed(page);
1922err:
1923 ext4_mb_put_buddy_cache_lock(sb, group, num_grp_locked);
1924 if (bitmap_page)
1925 page_cache_release(bitmap_page);
1926 if (page)
1927 page_cache_release(page);
1928 return ret;
1929}
1930
Eric Sandeen4ddfef72008-04-29 08:11:12 -04001931static noinline_for_stack int
1932ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
Alex Tomasc9de5602008-01-29 00:19:52 -05001933{
Theodore Ts'o8df96752009-05-01 08:50:38 -04001934 ext4_group_t ngroups, group, i;
Alex Tomasc9de5602008-01-29 00:19:52 -05001935 int cr;
1936 int err = 0;
1937 int bsbits;
1938 struct ext4_sb_info *sbi;
1939 struct super_block *sb;
1940 struct ext4_buddy e4b;
1941 loff_t size, isize;
1942
1943 sb = ac->ac_sb;
1944 sbi = EXT4_SB(sb);
Theodore Ts'o8df96752009-05-01 08:50:38 -04001945 ngroups = ext4_get_groups_count(sb);
Alex Tomasc9de5602008-01-29 00:19:52 -05001946 BUG_ON(ac->ac_status == AC_STATUS_FOUND);
1947
1948 /* first, try the goal */
1949 err = ext4_mb_find_by_goal(ac, &e4b);
1950 if (err || ac->ac_status == AC_STATUS_FOUND)
1951 goto out;
1952
1953 if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
1954 goto out;
1955
1956 /*
1957 * ac->ac2_order is set only if the fe_len is a power of 2
1958 * if ac2_order is set we also set criteria to 0 so that we
1959 * try exact allocation using buddy.
1960 */
1961 i = fls(ac->ac_g_ex.fe_len);
1962 ac->ac_2order = 0;
1963 /*
1964 * We search using buddy data only if the order of the request
1965 * is greater than equal to the sbi_s_mb_order2_reqs
Theodore Ts'ob713a5e2009-03-31 09:11:14 -04001966 * You can tune it via /sys/fs/ext4/<partition>/mb_order2_req
Alex Tomasc9de5602008-01-29 00:19:52 -05001967 */
1968 if (i >= sbi->s_mb_order2_reqs) {
1969 /*
1970 * This should tell if fe_len is exactly power of 2
1971 */
1972 if ((ac->ac_g_ex.fe_len & (~(1 << (i - 1)))) == 0)
1973 ac->ac_2order = i - 1;
1974 }
1975
1976 bsbits = ac->ac_sb->s_blocksize_bits;
1977 /* if stream allocation is enabled, use global goal */
1978 size = ac->ac_o_ex.fe_logical + ac->ac_o_ex.fe_len;
1979 isize = i_size_read(ac->ac_inode) >> bsbits;
1980 if (size < isize)
1981 size = isize;
1982
1983 if (size < sbi->s_mb_stream_request &&
1984 (ac->ac_flags & EXT4_MB_HINT_DATA)) {
1985 /* TBD: may be hot point */
1986 spin_lock(&sbi->s_md_lock);
1987 ac->ac_g_ex.fe_group = sbi->s_mb_last_group;
1988 ac->ac_g_ex.fe_start = sbi->s_mb_last_start;
1989 spin_unlock(&sbi->s_md_lock);
1990 }
Alex Tomasc9de5602008-01-29 00:19:52 -05001991 /* Let's just scan groups to find more-less suitable blocks */
1992 cr = ac->ac_2order ? 0 : 1;
1993 /*
1994 * cr == 0 try to get exact allocation,
1995 * cr == 3 try to get anything
1996 */
1997repeat:
1998 for (; cr < 4 && ac->ac_status == AC_STATUS_CONTINUE; cr++) {
1999 ac->ac_criteria = cr;
Aneesh Kumar K.Ved8f9c72008-07-11 19:27:31 -04002000 /*
2001 * searching for the right group start
2002 * from the goal value specified
2003 */
2004 group = ac->ac_g_ex.fe_group;
2005
Theodore Ts'o8df96752009-05-01 08:50:38 -04002006 for (i = 0; i < ngroups; group++, i++) {
Alex Tomasc9de5602008-01-29 00:19:52 -05002007 struct ext4_group_info *grp;
2008 struct ext4_group_desc *desc;
2009
Theodore Ts'o8df96752009-05-01 08:50:38 -04002010 if (group == ngroups)
Alex Tomasc9de5602008-01-29 00:19:52 -05002011 group = 0;
2012
2013 /* quick check to skip empty groups */
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -05002014 grp = ext4_get_group_info(sb, group);
Alex Tomasc9de5602008-01-29 00:19:52 -05002015 if (grp->bb_free == 0)
2016 continue;
2017
2018 /*
2019 * if the group is already init we check whether it is
2020 * a good group and if not we don't load the buddy
2021 */
2022 if (EXT4_MB_GRP_NEED_INIT(grp)) {
2023 /*
2024 * we need full data about the group
2025 * to make a good selection
2026 */
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -05002027 err = ext4_mb_init_group(sb, group);
Alex Tomasc9de5602008-01-29 00:19:52 -05002028 if (err)
2029 goto out;
Alex Tomasc9de5602008-01-29 00:19:52 -05002030 }
2031
2032 /*
2033 * If the particular group doesn't satisfy our
2034 * criteria we continue with the next group
2035 */
2036 if (!ext4_mb_good_group(ac, group, cr))
2037 continue;
2038
2039 err = ext4_mb_load_buddy(sb, group, &e4b);
2040 if (err)
2041 goto out;
2042
2043 ext4_lock_group(sb, group);
2044 if (!ext4_mb_good_group(ac, group, cr)) {
2045 /* someone did allocation from this group */
2046 ext4_unlock_group(sb, group);
2047 ext4_mb_release_desc(&e4b);
2048 continue;
2049 }
2050
2051 ac->ac_groups_scanned++;
2052 desc = ext4_get_group_desc(sb, group, NULL);
Theodore Ts'o75507ef2009-05-01 12:58:36 -04002053 if (cr == 0)
Alex Tomasc9de5602008-01-29 00:19:52 -05002054 ext4_mb_simple_scan_group(ac, &e4b);
2055 else if (cr == 1 &&
2056 ac->ac_g_ex.fe_len == sbi->s_stripe)
2057 ext4_mb_scan_aligned(ac, &e4b);
2058 else
2059 ext4_mb_complex_scan_group(ac, &e4b);
2060
2061 ext4_unlock_group(sb, group);
2062 ext4_mb_release_desc(&e4b);
2063
2064 if (ac->ac_status != AC_STATUS_CONTINUE)
2065 break;
2066 }
2067 }
2068
2069 if (ac->ac_b_ex.fe_len > 0 && ac->ac_status != AC_STATUS_FOUND &&
2070 !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
2071 /*
2072 * We've been searching too long. Let's try to allocate
2073 * the best chunk we've found so far
2074 */
2075
2076 ext4_mb_try_best_found(ac, &e4b);
2077 if (ac->ac_status != AC_STATUS_FOUND) {
2078 /*
2079 * Someone more lucky has already allocated it.
2080 * The only thing we can do is just take first
2081 * found block(s)
2082 printk(KERN_DEBUG "EXT4-fs: someone won our chunk\n");
2083 */
2084 ac->ac_b_ex.fe_group = 0;
2085 ac->ac_b_ex.fe_start = 0;
2086 ac->ac_b_ex.fe_len = 0;
2087 ac->ac_status = AC_STATUS_CONTINUE;
2088 ac->ac_flags |= EXT4_MB_HINT_FIRST;
2089 cr = 3;
2090 atomic_inc(&sbi->s_mb_lost_chunks);
2091 goto repeat;
2092 }
2093 }
2094out:
2095 return err;
2096}
2097
2098#ifdef EXT4_MB_HISTORY
2099struct ext4_mb_proc_session {
2100 struct ext4_mb_history *history;
2101 struct super_block *sb;
2102 int start;
2103 int max;
2104};
2105
2106static void *ext4_mb_history_skip_empty(struct ext4_mb_proc_session *s,
2107 struct ext4_mb_history *hs,
2108 int first)
2109{
2110 if (hs == s->history + s->max)
2111 hs = s->history;
2112 if (!first && hs == s->history + s->start)
2113 return NULL;
2114 while (hs->orig.fe_len == 0) {
2115 hs++;
2116 if (hs == s->history + s->max)
2117 hs = s->history;
2118 if (hs == s->history + s->start)
2119 return NULL;
2120 }
2121 return hs;
2122}
2123
2124static void *ext4_mb_seq_history_start(struct seq_file *seq, loff_t *pos)
2125{
2126 struct ext4_mb_proc_session *s = seq->private;
2127 struct ext4_mb_history *hs;
2128 int l = *pos;
2129
2130 if (l == 0)
2131 return SEQ_START_TOKEN;
2132 hs = ext4_mb_history_skip_empty(s, s->history + s->start, 1);
2133 if (!hs)
2134 return NULL;
2135 while (--l && (hs = ext4_mb_history_skip_empty(s, ++hs, 0)) != NULL);
2136 return hs;
2137}
2138
2139static void *ext4_mb_seq_history_next(struct seq_file *seq, void *v,
2140 loff_t *pos)
2141{
2142 struct ext4_mb_proc_session *s = seq->private;
2143 struct ext4_mb_history *hs = v;
2144
2145 ++*pos;
2146 if (v == SEQ_START_TOKEN)
2147 return ext4_mb_history_skip_empty(s, s->history + s->start, 1);
2148 else
2149 return ext4_mb_history_skip_empty(s, ++hs, 0);
2150}
2151
2152static int ext4_mb_seq_history_show(struct seq_file *seq, void *v)
2153{
2154 char buf[25], buf2[25], buf3[25], *fmt;
2155 struct ext4_mb_history *hs = v;
2156
2157 if (v == SEQ_START_TOKEN) {
2158 seq_printf(seq, "%-5s %-8s %-23s %-23s %-23s %-5s "
2159 "%-5s %-2s %-5s %-5s %-5s %-6s\n",
2160 "pid", "inode", "original", "goal", "result", "found",
2161 "grps", "cr", "flags", "merge", "tail", "broken");
2162 return 0;
2163 }
2164
2165 if (hs->op == EXT4_MB_HISTORY_ALLOC) {
2166 fmt = "%-5u %-8u %-23s %-23s %-23s %-5u %-5u %-2u "
2167 "%-5u %-5s %-5u %-6u\n";
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002168 sprintf(buf2, "%u/%d/%u@%u", hs->result.fe_group,
Alex Tomasc9de5602008-01-29 00:19:52 -05002169 hs->result.fe_start, hs->result.fe_len,
2170 hs->result.fe_logical);
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002171 sprintf(buf, "%u/%d/%u@%u", hs->orig.fe_group,
Alex Tomasc9de5602008-01-29 00:19:52 -05002172 hs->orig.fe_start, hs->orig.fe_len,
2173 hs->orig.fe_logical);
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002174 sprintf(buf3, "%u/%d/%u@%u", hs->goal.fe_group,
Alex Tomasc9de5602008-01-29 00:19:52 -05002175 hs->goal.fe_start, hs->goal.fe_len,
2176 hs->goal.fe_logical);
2177 seq_printf(seq, fmt, hs->pid, hs->ino, buf, buf3, buf2,
2178 hs->found, hs->groups, hs->cr, hs->flags,
2179 hs->merged ? "M" : "", hs->tail,
2180 hs->buddy ? 1 << hs->buddy : 0);
2181 } else if (hs->op == EXT4_MB_HISTORY_PREALLOC) {
2182 fmt = "%-5u %-8u %-23s %-23s %-23s\n";
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002183 sprintf(buf2, "%u/%d/%u@%u", hs->result.fe_group,
Alex Tomasc9de5602008-01-29 00:19:52 -05002184 hs->result.fe_start, hs->result.fe_len,
2185 hs->result.fe_logical);
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002186 sprintf(buf, "%u/%d/%u@%u", hs->orig.fe_group,
Alex Tomasc9de5602008-01-29 00:19:52 -05002187 hs->orig.fe_start, hs->orig.fe_len,
2188 hs->orig.fe_logical);
2189 seq_printf(seq, fmt, hs->pid, hs->ino, buf, "", buf2);
2190 } else if (hs->op == EXT4_MB_HISTORY_DISCARD) {
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002191 sprintf(buf2, "%u/%d/%u", hs->result.fe_group,
Alex Tomasc9de5602008-01-29 00:19:52 -05002192 hs->result.fe_start, hs->result.fe_len);
2193 seq_printf(seq, "%-5u %-8u %-23s discard\n",
2194 hs->pid, hs->ino, buf2);
2195 } else if (hs->op == EXT4_MB_HISTORY_FREE) {
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002196 sprintf(buf2, "%u/%d/%u", hs->result.fe_group,
Alex Tomasc9de5602008-01-29 00:19:52 -05002197 hs->result.fe_start, hs->result.fe_len);
2198 seq_printf(seq, "%-5u %-8u %-23s free\n",
2199 hs->pid, hs->ino, buf2);
2200 }
2201 return 0;
2202}
2203
2204static void ext4_mb_seq_history_stop(struct seq_file *seq, void *v)
2205{
2206}
2207
2208static struct seq_operations ext4_mb_seq_history_ops = {
2209 .start = ext4_mb_seq_history_start,
2210 .next = ext4_mb_seq_history_next,
2211 .stop = ext4_mb_seq_history_stop,
2212 .show = ext4_mb_seq_history_show,
2213};
2214
2215static int ext4_mb_seq_history_open(struct inode *inode, struct file *file)
2216{
2217 struct super_block *sb = PDE(inode)->data;
2218 struct ext4_sb_info *sbi = EXT4_SB(sb);
2219 struct ext4_mb_proc_session *s;
2220 int rc;
2221 int size;
2222
Shen Feng74767c52008-07-11 19:27:31 -04002223 if (unlikely(sbi->s_mb_history == NULL))
2224 return -ENOMEM;
Alex Tomasc9de5602008-01-29 00:19:52 -05002225 s = kmalloc(sizeof(*s), GFP_KERNEL);
2226 if (s == NULL)
2227 return -ENOMEM;
2228 s->sb = sb;
2229 size = sizeof(struct ext4_mb_history) * sbi->s_mb_history_max;
2230 s->history = kmalloc(size, GFP_KERNEL);
2231 if (s->history == NULL) {
2232 kfree(s);
2233 return -ENOMEM;
2234 }
2235
2236 spin_lock(&sbi->s_mb_history_lock);
2237 memcpy(s->history, sbi->s_mb_history, size);
2238 s->max = sbi->s_mb_history_max;
2239 s->start = sbi->s_mb_history_cur % s->max;
2240 spin_unlock(&sbi->s_mb_history_lock);
2241
2242 rc = seq_open(file, &ext4_mb_seq_history_ops);
2243 if (rc == 0) {
2244 struct seq_file *m = (struct seq_file *)file->private_data;
2245 m->private = s;
2246 } else {
2247 kfree(s->history);
2248 kfree(s);
2249 }
2250 return rc;
2251
2252}
2253
2254static int ext4_mb_seq_history_release(struct inode *inode, struct file *file)
2255{
2256 struct seq_file *seq = (struct seq_file *)file->private_data;
2257 struct ext4_mb_proc_session *s = seq->private;
2258 kfree(s->history);
2259 kfree(s);
2260 return seq_release(inode, file);
2261}
2262
2263static ssize_t ext4_mb_seq_history_write(struct file *file,
2264 const char __user *buffer,
2265 size_t count, loff_t *ppos)
2266{
2267 struct seq_file *seq = (struct seq_file *)file->private_data;
2268 struct ext4_mb_proc_session *s = seq->private;
2269 struct super_block *sb = s->sb;
2270 char str[32];
2271 int value;
2272
2273 if (count >= sizeof(str)) {
2274 printk(KERN_ERR "EXT4-fs: %s string too long, max %u bytes\n",
2275 "mb_history", (int)sizeof(str));
2276 return -EOVERFLOW;
2277 }
2278
2279 if (copy_from_user(str, buffer, count))
2280 return -EFAULT;
2281
2282 value = simple_strtol(str, NULL, 0);
2283 if (value < 0)
2284 return -ERANGE;
2285 EXT4_SB(sb)->s_mb_history_filter = value;
2286
2287 return count;
2288}
2289
2290static struct file_operations ext4_mb_seq_history_fops = {
2291 .owner = THIS_MODULE,
2292 .open = ext4_mb_seq_history_open,
2293 .read = seq_read,
2294 .write = ext4_mb_seq_history_write,
2295 .llseek = seq_lseek,
2296 .release = ext4_mb_seq_history_release,
2297};
2298
2299static void *ext4_mb_seq_groups_start(struct seq_file *seq, loff_t *pos)
2300{
2301 struct super_block *sb = seq->private;
Alex Tomasc9de5602008-01-29 00:19:52 -05002302 ext4_group_t group;
2303
Theodore Ts'o8df96752009-05-01 08:50:38 -04002304 if (*pos < 0 || *pos >= ext4_get_groups_count(sb))
Alex Tomasc9de5602008-01-29 00:19:52 -05002305 return NULL;
Alex Tomasc9de5602008-01-29 00:19:52 -05002306 group = *pos + 1;
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002307 return (void *) ((unsigned long) group);
Alex Tomasc9de5602008-01-29 00:19:52 -05002308}
2309
2310static void *ext4_mb_seq_groups_next(struct seq_file *seq, void *v, loff_t *pos)
2311{
2312 struct super_block *sb = seq->private;
Alex Tomasc9de5602008-01-29 00:19:52 -05002313 ext4_group_t group;
2314
2315 ++*pos;
Theodore Ts'o8df96752009-05-01 08:50:38 -04002316 if (*pos < 0 || *pos >= ext4_get_groups_count(sb))
Alex Tomasc9de5602008-01-29 00:19:52 -05002317 return NULL;
2318 group = *pos + 1;
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002319 return (void *) ((unsigned long) group);
Alex Tomasc9de5602008-01-29 00:19:52 -05002320}
2321
2322static int ext4_mb_seq_groups_show(struct seq_file *seq, void *v)
2323{
2324 struct super_block *sb = seq->private;
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002325 ext4_group_t group = (ext4_group_t) ((unsigned long) v);
Alex Tomasc9de5602008-01-29 00:19:52 -05002326 int i;
2327 int err;
2328 struct ext4_buddy e4b;
2329 struct sg {
2330 struct ext4_group_info info;
2331 unsigned short counters[16];
2332 } sg;
2333
2334 group--;
2335 if (group == 0)
2336 seq_printf(seq, "#%-5s: %-5s %-5s %-5s "
2337 "[ %-5s %-5s %-5s %-5s %-5s %-5s %-5s "
2338 "%-5s %-5s %-5s %-5s %-5s %-5s %-5s ]\n",
2339 "group", "free", "frags", "first",
2340 "2^0", "2^1", "2^2", "2^3", "2^4", "2^5", "2^6",
2341 "2^7", "2^8", "2^9", "2^10", "2^11", "2^12", "2^13");
2342
2343 i = (sb->s_blocksize_bits + 2) * sizeof(sg.info.bb_counters[0]) +
2344 sizeof(struct ext4_group_info);
2345 err = ext4_mb_load_buddy(sb, group, &e4b);
2346 if (err) {
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002347 seq_printf(seq, "#%-5u: I/O error\n", group);
Alex Tomasc9de5602008-01-29 00:19:52 -05002348 return 0;
2349 }
2350 ext4_lock_group(sb, group);
2351 memcpy(&sg, ext4_get_group_info(sb, group), i);
2352 ext4_unlock_group(sb, group);
2353 ext4_mb_release_desc(&e4b);
2354
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002355 seq_printf(seq, "#%-5u: %-5u %-5u %-5u [", group, sg.info.bb_free,
Alex Tomasc9de5602008-01-29 00:19:52 -05002356 sg.info.bb_fragments, sg.info.bb_first_free);
2357 for (i = 0; i <= 13; i++)
2358 seq_printf(seq, " %-5u", i <= sb->s_blocksize_bits + 1 ?
2359 sg.info.bb_counters[i] : 0);
2360 seq_printf(seq, " ]\n");
2361
2362 return 0;
2363}
2364
2365static void ext4_mb_seq_groups_stop(struct seq_file *seq, void *v)
2366{
2367}
2368
2369static struct seq_operations ext4_mb_seq_groups_ops = {
2370 .start = ext4_mb_seq_groups_start,
2371 .next = ext4_mb_seq_groups_next,
2372 .stop = ext4_mb_seq_groups_stop,
2373 .show = ext4_mb_seq_groups_show,
2374};
2375
2376static int ext4_mb_seq_groups_open(struct inode *inode, struct file *file)
2377{
2378 struct super_block *sb = PDE(inode)->data;
2379 int rc;
2380
2381 rc = seq_open(file, &ext4_mb_seq_groups_ops);
2382 if (rc == 0) {
2383 struct seq_file *m = (struct seq_file *)file->private_data;
2384 m->private = sb;
2385 }
2386 return rc;
2387
2388}
2389
2390static struct file_operations ext4_mb_seq_groups_fops = {
2391 .owner = THIS_MODULE,
2392 .open = ext4_mb_seq_groups_open,
2393 .read = seq_read,
2394 .llseek = seq_lseek,
2395 .release = seq_release,
2396};
2397
2398static void ext4_mb_history_release(struct super_block *sb)
2399{
2400 struct ext4_sb_info *sbi = EXT4_SB(sb);
2401
Theodore Ts'o9f6200b2008-09-23 09:18:24 -04002402 if (sbi->s_proc != NULL) {
2403 remove_proc_entry("mb_groups", sbi->s_proc);
Curt Wohlgemuthf4033902009-05-01 20:27:20 -04002404 if (sbi->s_mb_history_max)
2405 remove_proc_entry("mb_history", sbi->s_proc);
Theodore Ts'o9f6200b2008-09-23 09:18:24 -04002406 }
Alex Tomasc9de5602008-01-29 00:19:52 -05002407 kfree(sbi->s_mb_history);
2408}
2409
2410static void ext4_mb_history_init(struct super_block *sb)
2411{
2412 struct ext4_sb_info *sbi = EXT4_SB(sb);
2413 int i;
2414
Theodore Ts'o9f6200b2008-09-23 09:18:24 -04002415 if (sbi->s_proc != NULL) {
Curt Wohlgemuthf4033902009-05-01 20:27:20 -04002416 if (sbi->s_mb_history_max)
2417 proc_create_data("mb_history", S_IRUGO, sbi->s_proc,
2418 &ext4_mb_seq_history_fops, sb);
Theodore Ts'o9f6200b2008-09-23 09:18:24 -04002419 proc_create_data("mb_groups", S_IRUGO, sbi->s_proc,
Denis V. Lunev46fe74f2008-04-29 01:02:08 -07002420 &ext4_mb_seq_groups_fops, sb);
Alex Tomasc9de5602008-01-29 00:19:52 -05002421 }
2422
Alex Tomasc9de5602008-01-29 00:19:52 -05002423 sbi->s_mb_history_cur = 0;
2424 spin_lock_init(&sbi->s_mb_history_lock);
2425 i = sbi->s_mb_history_max * sizeof(struct ext4_mb_history);
Curt Wohlgemuthf4033902009-05-01 20:27:20 -04002426 sbi->s_mb_history = i ? kzalloc(i, GFP_KERNEL) : NULL;
Alex Tomasc9de5602008-01-29 00:19:52 -05002427 /* if we can't allocate history, then we simple won't use it */
2428}
2429
Eric Sandeen4ddfef72008-04-29 08:11:12 -04002430static noinline_for_stack void
2431ext4_mb_store_history(struct ext4_allocation_context *ac)
Alex Tomasc9de5602008-01-29 00:19:52 -05002432{
2433 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
2434 struct ext4_mb_history h;
2435
Curt Wohlgemuthf4033902009-05-01 20:27:20 -04002436 if (sbi->s_mb_history == NULL)
Alex Tomasc9de5602008-01-29 00:19:52 -05002437 return;
2438
2439 if (!(ac->ac_op & sbi->s_mb_history_filter))
2440 return;
2441
2442 h.op = ac->ac_op;
2443 h.pid = current->pid;
2444 h.ino = ac->ac_inode ? ac->ac_inode->i_ino : 0;
2445 h.orig = ac->ac_o_ex;
2446 h.result = ac->ac_b_ex;
2447 h.flags = ac->ac_flags;
2448 h.found = ac->ac_found;
2449 h.groups = ac->ac_groups_scanned;
2450 h.cr = ac->ac_criteria;
2451 h.tail = ac->ac_tail;
2452 h.buddy = ac->ac_buddy;
2453 h.merged = 0;
2454 if (ac->ac_op == EXT4_MB_HISTORY_ALLOC) {
2455 if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&
2456 ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)
2457 h.merged = 1;
2458 h.goal = ac->ac_g_ex;
2459 h.result = ac->ac_f_ex;
2460 }
2461
2462 spin_lock(&sbi->s_mb_history_lock);
2463 memcpy(sbi->s_mb_history + sbi->s_mb_history_cur, &h, sizeof(h));
2464 if (++sbi->s_mb_history_cur >= sbi->s_mb_history_max)
2465 sbi->s_mb_history_cur = 0;
2466 spin_unlock(&sbi->s_mb_history_lock);
2467}
2468
2469#else
2470#define ext4_mb_history_release(sb)
2471#define ext4_mb_history_init(sb)
2472#endif
2473
Frederic Bohe5f21b0e2008-07-11 19:27:31 -04002474
2475/* Create and initialize ext4_group_info data for the given group. */
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -05002476int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group,
Frederic Bohe5f21b0e2008-07-11 19:27:31 -04002477 struct ext4_group_desc *desc)
2478{
2479 int i, len;
2480 int metalen = 0;
2481 struct ext4_sb_info *sbi = EXT4_SB(sb);
2482 struct ext4_group_info **meta_group_info;
2483
2484 /*
2485 * First check if this group is the first of a reserved block.
2486 * If it's true, we have to allocate a new table of pointers
2487 * to ext4_group_info structures
2488 */
2489 if (group % EXT4_DESC_PER_BLOCK(sb) == 0) {
2490 metalen = sizeof(*meta_group_info) <<
2491 EXT4_DESC_PER_BLOCK_BITS(sb);
2492 meta_group_info = kmalloc(metalen, GFP_KERNEL);
2493 if (meta_group_info == NULL) {
2494 printk(KERN_ERR "EXT4-fs: can't allocate mem for a "
2495 "buddy group\n");
2496 goto exit_meta_group_info;
2497 }
2498 sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)] =
2499 meta_group_info;
2500 }
2501
2502 /*
2503 * calculate needed size. if change bb_counters size,
2504 * don't forget about ext4_mb_generate_buddy()
2505 */
2506 len = offsetof(typeof(**meta_group_info),
2507 bb_counters[sb->s_blocksize_bits + 2]);
2508
2509 meta_group_info =
2510 sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)];
2511 i = group & (EXT4_DESC_PER_BLOCK(sb) - 1);
2512
2513 meta_group_info[i] = kzalloc(len, GFP_KERNEL);
2514 if (meta_group_info[i] == NULL) {
2515 printk(KERN_ERR "EXT4-fs: can't allocate buddy mem\n");
2516 goto exit_group_info;
2517 }
2518 set_bit(EXT4_GROUP_INFO_NEED_INIT_BIT,
2519 &(meta_group_info[i]->bb_state));
2520
2521 /*
2522 * initialize bb_free to be able to skip
2523 * empty groups without initialization
2524 */
2525 if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
2526 meta_group_info[i]->bb_free =
2527 ext4_free_blocks_after_init(sb, group, desc);
2528 } else {
2529 meta_group_info[i]->bb_free =
Aneesh Kumar K.V560671a2009-01-05 22:20:24 -05002530 ext4_free_blks_count(sb, desc);
Frederic Bohe5f21b0e2008-07-11 19:27:31 -04002531 }
2532
2533 INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -05002534 init_rwsem(&meta_group_info[i]->alloc_sem);
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04002535 meta_group_info[i]->bb_free_root.rb_node = NULL;;
Frederic Bohe5f21b0e2008-07-11 19:27:31 -04002536
2537#ifdef DOUBLE_CHECK
2538 {
2539 struct buffer_head *bh;
2540 meta_group_info[i]->bb_bitmap =
2541 kmalloc(sb->s_blocksize, GFP_KERNEL);
2542 BUG_ON(meta_group_info[i]->bb_bitmap == NULL);
2543 bh = ext4_read_block_bitmap(sb, group);
2544 BUG_ON(bh == NULL);
2545 memcpy(meta_group_info[i]->bb_bitmap, bh->b_data,
2546 sb->s_blocksize);
2547 put_bh(bh);
2548 }
2549#endif
2550
2551 return 0;
2552
2553exit_group_info:
2554 /* If a meta_group_info table has been allocated, release it now */
2555 if (group % EXT4_DESC_PER_BLOCK(sb) == 0)
2556 kfree(sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)]);
2557exit_meta_group_info:
2558 return -ENOMEM;
2559} /* ext4_mb_add_groupinfo */
2560
2561/*
Frederic Bohe5f21b0e2008-07-11 19:27:31 -04002562 * Update an existing group.
2563 * This function is used for online resize
2564 */
2565void ext4_mb_update_group_info(struct ext4_group_info *grp, ext4_grpblk_t add)
2566{
2567 grp->bb_free += add;
2568}
2569
Alex Tomasc9de5602008-01-29 00:19:52 -05002570static int ext4_mb_init_backend(struct super_block *sb)
2571{
Theodore Ts'o8df96752009-05-01 08:50:38 -04002572 ext4_group_t ngroups = ext4_get_groups_count(sb);
Alex Tomasc9de5602008-01-29 00:19:52 -05002573 ext4_group_t i;
Frederic Bohe5f21b0e2008-07-11 19:27:31 -04002574 int metalen;
Alex Tomasc9de5602008-01-29 00:19:52 -05002575 struct ext4_sb_info *sbi = EXT4_SB(sb);
Frederic Bohe5f21b0e2008-07-11 19:27:31 -04002576 struct ext4_super_block *es = sbi->s_es;
2577 int num_meta_group_infos;
2578 int num_meta_group_infos_max;
2579 int array_size;
Alex Tomasc9de5602008-01-29 00:19:52 -05002580 struct ext4_group_info **meta_group_info;
Frederic Bohe5f21b0e2008-07-11 19:27:31 -04002581 struct ext4_group_desc *desc;
Alex Tomasc9de5602008-01-29 00:19:52 -05002582
Frederic Bohe5f21b0e2008-07-11 19:27:31 -04002583 /* This is the number of blocks used by GDT */
Theodore Ts'o8df96752009-05-01 08:50:38 -04002584 num_meta_group_infos = (ngroups + EXT4_DESC_PER_BLOCK(sb) -
Frederic Bohe5f21b0e2008-07-11 19:27:31 -04002585 1) >> EXT4_DESC_PER_BLOCK_BITS(sb);
2586
2587 /*
2588 * This is the total number of blocks used by GDT including
2589 * the number of reserved blocks for GDT.
2590 * The s_group_info array is allocated with this value
2591 * to allow a clean online resize without a complex
2592 * manipulation of pointer.
2593 * The drawback is the unused memory when no resize
2594 * occurs but it's very low in terms of pages
2595 * (see comments below)
2596 * Need to handle this properly when META_BG resizing is allowed
2597 */
2598 num_meta_group_infos_max = num_meta_group_infos +
2599 le16_to_cpu(es->s_reserved_gdt_blocks);
2600
2601 /*
2602 * array_size is the size of s_group_info array. We round it
2603 * to the next power of two because this approximation is done
2604 * internally by kmalloc so we can have some more memory
2605 * for free here (e.g. may be used for META_BG resize).
2606 */
2607 array_size = 1;
2608 while (array_size < sizeof(*sbi->s_group_info) *
2609 num_meta_group_infos_max)
2610 array_size = array_size << 1;
Alex Tomasc9de5602008-01-29 00:19:52 -05002611 /* An 8TB filesystem with 64-bit pointers requires a 4096 byte
2612 * kmalloc. A 128kb malloc should suffice for a 256TB filesystem.
2613 * So a two level scheme suffices for now. */
Frederic Bohe5f21b0e2008-07-11 19:27:31 -04002614 sbi->s_group_info = kmalloc(array_size, GFP_KERNEL);
Alex Tomasc9de5602008-01-29 00:19:52 -05002615 if (sbi->s_group_info == NULL) {
2616 printk(KERN_ERR "EXT4-fs: can't allocate buddy meta group\n");
2617 return -ENOMEM;
2618 }
2619 sbi->s_buddy_cache = new_inode(sb);
2620 if (sbi->s_buddy_cache == NULL) {
2621 printk(KERN_ERR "EXT4-fs: can't get new inode\n");
2622 goto err_freesgi;
2623 }
2624 EXT4_I(sbi->s_buddy_cache)->i_disksize = 0;
2625
2626 metalen = sizeof(*meta_group_info) << EXT4_DESC_PER_BLOCK_BITS(sb);
2627 for (i = 0; i < num_meta_group_infos; i++) {
2628 if ((i + 1) == num_meta_group_infos)
2629 metalen = sizeof(*meta_group_info) *
Theodore Ts'o8df96752009-05-01 08:50:38 -04002630 (ngroups -
Alex Tomasc9de5602008-01-29 00:19:52 -05002631 (i << EXT4_DESC_PER_BLOCK_BITS(sb)));
2632 meta_group_info = kmalloc(metalen, GFP_KERNEL);
2633 if (meta_group_info == NULL) {
2634 printk(KERN_ERR "EXT4-fs: can't allocate mem for a "
2635 "buddy group\n");
2636 goto err_freemeta;
2637 }
2638 sbi->s_group_info[i] = meta_group_info;
2639 }
2640
Theodore Ts'o8df96752009-05-01 08:50:38 -04002641 for (i = 0; i < ngroups; i++) {
Alex Tomasc9de5602008-01-29 00:19:52 -05002642 desc = ext4_get_group_desc(sb, i, NULL);
2643 if (desc == NULL) {
2644 printk(KERN_ERR
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002645 "EXT4-fs: can't read descriptor %u\n", i);
Alex Tomasc9de5602008-01-29 00:19:52 -05002646 goto err_freebuddy;
2647 }
Frederic Bohe5f21b0e2008-07-11 19:27:31 -04002648 if (ext4_mb_add_groupinfo(sb, i, desc) != 0)
2649 goto err_freebuddy;
Alex Tomasc9de5602008-01-29 00:19:52 -05002650 }
2651
2652 return 0;
2653
2654err_freebuddy:
Roel Kluinf1fa3342008-04-29 22:01:15 -04002655 while (i-- > 0)
Alex Tomasc9de5602008-01-29 00:19:52 -05002656 kfree(ext4_get_group_info(sb, i));
Alex Tomasc9de5602008-01-29 00:19:52 -05002657 i = num_meta_group_infos;
2658err_freemeta:
Roel Kluinf1fa3342008-04-29 22:01:15 -04002659 while (i-- > 0)
Alex Tomasc9de5602008-01-29 00:19:52 -05002660 kfree(sbi->s_group_info[i]);
2661 iput(sbi->s_buddy_cache);
2662err_freesgi:
2663 kfree(sbi->s_group_info);
2664 return -ENOMEM;
2665}
2666
2667int ext4_mb_init(struct super_block *sb, int needs_recovery)
2668{
2669 struct ext4_sb_info *sbi = EXT4_SB(sb);
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04002670 unsigned i, j;
Alex Tomasc9de5602008-01-29 00:19:52 -05002671 unsigned offset;
2672 unsigned max;
Shen Feng74767c52008-07-11 19:27:31 -04002673 int ret;
Alex Tomasc9de5602008-01-29 00:19:52 -05002674
Alex Tomasc9de5602008-01-29 00:19:52 -05002675 i = (sb->s_blocksize_bits + 2) * sizeof(unsigned short);
2676
2677 sbi->s_mb_offsets = kmalloc(i, GFP_KERNEL);
2678 if (sbi->s_mb_offsets == NULL) {
Alex Tomasc9de5602008-01-29 00:19:52 -05002679 return -ENOMEM;
2680 }
Yasunori Gotoff7ef322008-12-17 00:48:39 -05002681
2682 i = (sb->s_blocksize_bits + 2) * sizeof(unsigned int);
Alex Tomasc9de5602008-01-29 00:19:52 -05002683 sbi->s_mb_maxs = kmalloc(i, GFP_KERNEL);
2684 if (sbi->s_mb_maxs == NULL) {
Dan Carpentera7b19442009-03-27 19:42:54 -04002685 kfree(sbi->s_mb_offsets);
Alex Tomasc9de5602008-01-29 00:19:52 -05002686 return -ENOMEM;
2687 }
2688
2689 /* order 0 is regular bitmap */
2690 sbi->s_mb_maxs[0] = sb->s_blocksize << 3;
2691 sbi->s_mb_offsets[0] = 0;
2692
2693 i = 1;
2694 offset = 0;
2695 max = sb->s_blocksize << 2;
2696 do {
2697 sbi->s_mb_offsets[i] = offset;
2698 sbi->s_mb_maxs[i] = max;
2699 offset += 1 << (sb->s_blocksize_bits - i);
2700 max = max >> 1;
2701 i++;
2702 } while (i <= sb->s_blocksize_bits + 1);
2703
2704 /* init file for buddy data */
Shen Feng74767c52008-07-11 19:27:31 -04002705 ret = ext4_mb_init_backend(sb);
2706 if (ret != 0) {
Alex Tomasc9de5602008-01-29 00:19:52 -05002707 kfree(sbi->s_mb_offsets);
2708 kfree(sbi->s_mb_maxs);
Shen Feng74767c52008-07-11 19:27:31 -04002709 return ret;
Alex Tomasc9de5602008-01-29 00:19:52 -05002710 }
2711
2712 spin_lock_init(&sbi->s_md_lock);
Alex Tomasc9de5602008-01-29 00:19:52 -05002713 spin_lock_init(&sbi->s_bal_lock);
2714
2715 sbi->s_mb_max_to_scan = MB_DEFAULT_MAX_TO_SCAN;
2716 sbi->s_mb_min_to_scan = MB_DEFAULT_MIN_TO_SCAN;
2717 sbi->s_mb_stats = MB_DEFAULT_STATS;
2718 sbi->s_mb_stream_request = MB_DEFAULT_STREAM_THRESHOLD;
2719 sbi->s_mb_order2_reqs = MB_DEFAULT_ORDER2_REQS;
2720 sbi->s_mb_history_filter = EXT4_MB_HISTORY_DEFAULT;
2721 sbi->s_mb_group_prealloc = MB_DEFAULT_GROUP_PREALLOC;
2722
Eric Sandeen730c2132008-09-13 15:23:29 -04002723 sbi->s_locality_groups = alloc_percpu(struct ext4_locality_group);
Alex Tomasc9de5602008-01-29 00:19:52 -05002724 if (sbi->s_locality_groups == NULL) {
Alex Tomasc9de5602008-01-29 00:19:52 -05002725 kfree(sbi->s_mb_offsets);
2726 kfree(sbi->s_mb_maxs);
2727 return -ENOMEM;
2728 }
Eric Sandeen730c2132008-09-13 15:23:29 -04002729 for_each_possible_cpu(i) {
Alex Tomasc9de5602008-01-29 00:19:52 -05002730 struct ext4_locality_group *lg;
Eric Sandeen730c2132008-09-13 15:23:29 -04002731 lg = per_cpu_ptr(sbi->s_locality_groups, i);
Alex Tomasc9de5602008-01-29 00:19:52 -05002732 mutex_init(&lg->lg_mutex);
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04002733 for (j = 0; j < PREALLOC_TB_SIZE; j++)
2734 INIT_LIST_HEAD(&lg->lg_prealloc_list[j]);
Alex Tomasc9de5602008-01-29 00:19:52 -05002735 spin_lock_init(&lg->lg_prealloc_lock);
2736 }
2737
Alex Tomasc9de5602008-01-29 00:19:52 -05002738 ext4_mb_history_init(sb);
2739
Frank Mayhar03901312009-01-07 00:06:22 -05002740 if (sbi->s_journal)
2741 sbi->s_journal->j_commit_callback = release_blocks_on_commit;
Theodore Ts'o3e624fc2008-10-16 20:00:24 -04002742
Theodore Ts'o4776004f2008-09-08 23:00:52 -04002743 printk(KERN_INFO "EXT4-fs: mballoc enabled\n");
Alex Tomasc9de5602008-01-29 00:19:52 -05002744 return 0;
2745}
2746
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04002747/* need to called with the ext4 group lock held */
Alex Tomasc9de5602008-01-29 00:19:52 -05002748static void ext4_mb_cleanup_pa(struct ext4_group_info *grp)
2749{
2750 struct ext4_prealloc_space *pa;
2751 struct list_head *cur, *tmp;
2752 int count = 0;
2753
2754 list_for_each_safe(cur, tmp, &grp->bb_prealloc_list) {
2755 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
2756 list_del(&pa->pa_group_list);
2757 count++;
Aneesh Kumar K.V688f05a2008-10-13 12:14:14 -04002758 kmem_cache_free(ext4_pspace_cachep, pa);
Alex Tomasc9de5602008-01-29 00:19:52 -05002759 }
2760 if (count)
2761 mb_debug("mballoc: %u PAs left\n", count);
2762
2763}
2764
2765int ext4_mb_release(struct super_block *sb)
2766{
Theodore Ts'o8df96752009-05-01 08:50:38 -04002767 ext4_group_t ngroups = ext4_get_groups_count(sb);
Alex Tomasc9de5602008-01-29 00:19:52 -05002768 ext4_group_t i;
2769 int num_meta_group_infos;
2770 struct ext4_group_info *grinfo;
2771 struct ext4_sb_info *sbi = EXT4_SB(sb);
2772
Alex Tomasc9de5602008-01-29 00:19:52 -05002773 if (sbi->s_group_info) {
Theodore Ts'o8df96752009-05-01 08:50:38 -04002774 for (i = 0; i < ngroups; i++) {
Alex Tomasc9de5602008-01-29 00:19:52 -05002775 grinfo = ext4_get_group_info(sb, i);
2776#ifdef DOUBLE_CHECK
2777 kfree(grinfo->bb_bitmap);
2778#endif
2779 ext4_lock_group(sb, i);
2780 ext4_mb_cleanup_pa(grinfo);
2781 ext4_unlock_group(sb, i);
2782 kfree(grinfo);
2783 }
Theodore Ts'o8df96752009-05-01 08:50:38 -04002784 num_meta_group_infos = (ngroups +
Alex Tomasc9de5602008-01-29 00:19:52 -05002785 EXT4_DESC_PER_BLOCK(sb) - 1) >>
2786 EXT4_DESC_PER_BLOCK_BITS(sb);
2787 for (i = 0; i < num_meta_group_infos; i++)
2788 kfree(sbi->s_group_info[i]);
2789 kfree(sbi->s_group_info);
2790 }
2791 kfree(sbi->s_mb_offsets);
2792 kfree(sbi->s_mb_maxs);
2793 if (sbi->s_buddy_cache)
2794 iput(sbi->s_buddy_cache);
2795 if (sbi->s_mb_stats) {
2796 printk(KERN_INFO
2797 "EXT4-fs: mballoc: %u blocks %u reqs (%u success)\n",
2798 atomic_read(&sbi->s_bal_allocated),
2799 atomic_read(&sbi->s_bal_reqs),
2800 atomic_read(&sbi->s_bal_success));
2801 printk(KERN_INFO
2802 "EXT4-fs: mballoc: %u extents scanned, %u goal hits, "
2803 "%u 2^N hits, %u breaks, %u lost\n",
2804 atomic_read(&sbi->s_bal_ex_scanned),
2805 atomic_read(&sbi->s_bal_goals),
2806 atomic_read(&sbi->s_bal_2orders),
2807 atomic_read(&sbi->s_bal_breaks),
2808 atomic_read(&sbi->s_mb_lost_chunks));
2809 printk(KERN_INFO
2810 "EXT4-fs: mballoc: %lu generated and it took %Lu\n",
2811 sbi->s_mb_buddies_generated++,
2812 sbi->s_mb_generation_time);
2813 printk(KERN_INFO
2814 "EXT4-fs: mballoc: %u preallocated, %u discarded\n",
2815 atomic_read(&sbi->s_mb_preallocated),
2816 atomic_read(&sbi->s_mb_discarded));
2817 }
2818
Eric Sandeen730c2132008-09-13 15:23:29 -04002819 free_percpu(sbi->s_locality_groups);
Alex Tomasc9de5602008-01-29 00:19:52 -05002820 ext4_mb_history_release(sb);
Alex Tomasc9de5602008-01-29 00:19:52 -05002821
2822 return 0;
2823}
2824
Theodore Ts'o3e624fc2008-10-16 20:00:24 -04002825/*
2826 * This function is called by the jbd2 layer once the commit has finished,
2827 * so we know we can free the blocks that were released with that commit.
2828 */
2829static void release_blocks_on_commit(journal_t *journal, transaction_t *txn)
Alex Tomasc9de5602008-01-29 00:19:52 -05002830{
Theodore Ts'o3e624fc2008-10-16 20:00:24 -04002831 struct super_block *sb = journal->j_private;
Alex Tomasc9de5602008-01-29 00:19:52 -05002832 struct ext4_buddy e4b;
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04002833 struct ext4_group_info *db;
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04002834 int err, count = 0, count2 = 0;
2835 struct ext4_free_data *entry;
Theodore Ts'o8a0aba72008-10-16 10:06:27 -04002836 ext4_fsblk_t discard_block;
Theodore Ts'o3e624fc2008-10-16 20:00:24 -04002837 struct list_head *l, *ltmp;
Alex Tomasc9de5602008-01-29 00:19:52 -05002838
Theodore Ts'o3e624fc2008-10-16 20:00:24 -04002839 list_for_each_safe(l, ltmp, &txn->t_private_list) {
2840 entry = list_entry(l, struct ext4_free_data, list);
Alex Tomasc9de5602008-01-29 00:19:52 -05002841
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002842 mb_debug("gonna free %u blocks in group %u (0x%p):",
Theodore Ts'o3e624fc2008-10-16 20:00:24 -04002843 entry->count, entry->group, entry);
Alex Tomasc9de5602008-01-29 00:19:52 -05002844
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04002845 err = ext4_mb_load_buddy(sb, entry->group, &e4b);
Alex Tomasc9de5602008-01-29 00:19:52 -05002846 /* we expect to find existing buddy because it's pinned */
2847 BUG_ON(err != 0);
2848
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04002849 db = e4b.bd_info;
Alex Tomasc9de5602008-01-29 00:19:52 -05002850 /* there are blocks to put in buddy to make them really free */
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04002851 count += entry->count;
Alex Tomasc9de5602008-01-29 00:19:52 -05002852 count2++;
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04002853 ext4_lock_group(sb, entry->group);
2854 /* Take it out of per group rb tree */
2855 rb_erase(&entry->node, &(db->bb_free_root));
2856 mb_free_blocks(NULL, &e4b, entry->start_blk, entry->count);
2857
2858 if (!db->bb_free_root.rb_node) {
2859 /* No more items in the per group rb tree
2860 * balance refcounts from ext4_mb_free_metadata()
2861 */
2862 page_cache_release(e4b.bd_buddy_page);
2863 page_cache_release(e4b.bd_bitmap_page);
Alex Tomasc9de5602008-01-29 00:19:52 -05002864 }
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04002865 ext4_unlock_group(sb, entry->group);
Theodore Ts'o8a0aba72008-10-16 10:06:27 -04002866 discard_block = (ext4_fsblk_t) entry->group * EXT4_BLOCKS_PER_GROUP(sb)
2867 + entry->start_blk
2868 + le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);
Theodore Ts'o9bffad12009-06-17 11:48:11 -04002869 trace_ext4_discard_blocks(sb, (unsigned long long)discard_block,
2870 entry->count);
Theodore Ts'o8a0aba72008-10-16 10:06:27 -04002871 sb_issue_discard(sb, discard_block, entry->count);
Alex Tomasc9de5602008-01-29 00:19:52 -05002872
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04002873 kmem_cache_free(ext4_free_ext_cachep, entry);
Alex Tomasc9de5602008-01-29 00:19:52 -05002874 ext4_mb_release_desc(&e4b);
Theodore Ts'o3e624fc2008-10-16 20:00:24 -04002875 }
Alex Tomasc9de5602008-01-29 00:19:52 -05002876
2877 mb_debug("freed %u blocks in %u structures\n", count, count2);
2878}
2879
Alex Tomasc9de5602008-01-29 00:19:52 -05002880int __init init_ext4_mballoc(void)
2881{
2882 ext4_pspace_cachep =
2883 kmem_cache_create("ext4_prealloc_space",
2884 sizeof(struct ext4_prealloc_space),
2885 0, SLAB_RECLAIM_ACCOUNT, NULL);
2886 if (ext4_pspace_cachep == NULL)
2887 return -ENOMEM;
2888
Eric Sandeen256bdb42008-02-10 01:13:33 -05002889 ext4_ac_cachep =
2890 kmem_cache_create("ext4_alloc_context",
2891 sizeof(struct ext4_allocation_context),
2892 0, SLAB_RECLAIM_ACCOUNT, NULL);
2893 if (ext4_ac_cachep == NULL) {
2894 kmem_cache_destroy(ext4_pspace_cachep);
2895 return -ENOMEM;
2896 }
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04002897
2898 ext4_free_ext_cachep =
2899 kmem_cache_create("ext4_free_block_extents",
2900 sizeof(struct ext4_free_data),
2901 0, SLAB_RECLAIM_ACCOUNT, NULL);
2902 if (ext4_free_ext_cachep == NULL) {
2903 kmem_cache_destroy(ext4_pspace_cachep);
2904 kmem_cache_destroy(ext4_ac_cachep);
2905 return -ENOMEM;
2906 }
Alex Tomasc9de5602008-01-29 00:19:52 -05002907 return 0;
2908}
2909
2910void exit_ext4_mballoc(void)
2911{
Jesper Dangaard Brouer3e03f9c2009-07-05 22:29:27 -04002912 /*
2913 * Wait for completion of call_rcu()'s on ext4_pspace_cachep
2914 * before destroying the slab cache.
2915 */
2916 rcu_barrier();
Alex Tomasc9de5602008-01-29 00:19:52 -05002917 kmem_cache_destroy(ext4_pspace_cachep);
Eric Sandeen256bdb42008-02-10 01:13:33 -05002918 kmem_cache_destroy(ext4_ac_cachep);
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04002919 kmem_cache_destroy(ext4_free_ext_cachep);
Alex Tomasc9de5602008-01-29 00:19:52 -05002920}
2921
2922
2923/*
2924 * Check quota and mark choosed space (ac->ac_b_ex) non-free in bitmaps
2925 * Returns 0 if success or error code
2926 */
Eric Sandeen4ddfef72008-04-29 08:11:12 -04002927static noinline_for_stack int
2928ext4_mb_mark_diskspace_used(struct ext4_allocation_context *ac,
Theodore Ts'o498e5f22008-11-05 00:14:04 -05002929 handle_t *handle, unsigned int reserv_blks)
Alex Tomasc9de5602008-01-29 00:19:52 -05002930{
2931 struct buffer_head *bitmap_bh = NULL;
2932 struct ext4_super_block *es;
2933 struct ext4_group_desc *gdp;
2934 struct buffer_head *gdp_bh;
2935 struct ext4_sb_info *sbi;
2936 struct super_block *sb;
2937 ext4_fsblk_t block;
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -04002938 int err, len;
Alex Tomasc9de5602008-01-29 00:19:52 -05002939
2940 BUG_ON(ac->ac_status != AC_STATUS_FOUND);
2941 BUG_ON(ac->ac_b_ex.fe_len <= 0);
2942
2943 sb = ac->ac_sb;
2944 sbi = EXT4_SB(sb);
2945 es = sbi->s_es;
2946
Alex Tomasc9de5602008-01-29 00:19:52 -05002947
2948 err = -EIO;
Theodore Ts'o574ca172008-07-11 19:27:31 -04002949 bitmap_bh = ext4_read_block_bitmap(sb, ac->ac_b_ex.fe_group);
Alex Tomasc9de5602008-01-29 00:19:52 -05002950 if (!bitmap_bh)
2951 goto out_err;
2952
2953 err = ext4_journal_get_write_access(handle, bitmap_bh);
2954 if (err)
2955 goto out_err;
2956
2957 err = -EIO;
2958 gdp = ext4_get_group_desc(sb, ac->ac_b_ex.fe_group, &gdp_bh);
2959 if (!gdp)
2960 goto out_err;
2961
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05002962 ext4_debug("using block group %u(%d)\n", ac->ac_b_ex.fe_group,
Thadeu Lima de Souza Cascardo9fd97842009-01-26 19:26:26 -05002963 ext4_free_blks_count(sb, gdp));
Aneesh Kumar K.V03cddb82008-06-05 20:59:29 -04002964
Alex Tomasc9de5602008-01-29 00:19:52 -05002965 err = ext4_journal_get_write_access(handle, gdp_bh);
2966 if (err)
2967 goto out_err;
2968
2969 block = ac->ac_b_ex.fe_group * EXT4_BLOCKS_PER_GROUP(sb)
2970 + ac->ac_b_ex.fe_start
2971 + le32_to_cpu(es->s_first_data_block);
2972
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -04002973 len = ac->ac_b_ex.fe_len;
Theodore Ts'o6fd058f2009-05-17 15:38:01 -04002974 if (!ext4_data_block_valid(sbi, block, len)) {
Harvey Harrison46e665e2008-04-17 10:38:59 -04002975 ext4_error(sb, __func__,
Theodore Ts'o6fd058f2009-05-17 15:38:01 -04002976 "Allocating blocks %llu-%llu which overlap "
2977 "fs metadata\n", block, block+len);
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -04002978 /* File system mounted not to panic on error
2979 * Fix the bitmap and repeat the block allocation
2980 * We leak some of the blocks here.
2981 */
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04002982 ext4_lock_group(sb, ac->ac_b_ex.fe_group);
2983 mb_set_bits(bitmap_bh->b_data, ac->ac_b_ex.fe_start,
2984 ac->ac_b_ex.fe_len);
2985 ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
Frank Mayhar03901312009-01-07 00:06:22 -05002986 err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -04002987 if (!err)
2988 err = -EAGAIN;
2989 goto out_err;
Alex Tomasc9de5602008-01-29 00:19:52 -05002990 }
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04002991
2992 ext4_lock_group(sb, ac->ac_b_ex.fe_group);
Alex Tomasc9de5602008-01-29 00:19:52 -05002993#ifdef AGGRESSIVE_CHECK
2994 {
2995 int i;
2996 for (i = 0; i < ac->ac_b_ex.fe_len; i++) {
2997 BUG_ON(mb_test_bit(ac->ac_b_ex.fe_start + i,
2998 bitmap_bh->b_data));
2999 }
3000 }
3001#endif
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04003002 mb_set_bits(bitmap_bh->b_data, ac->ac_b_ex.fe_start,ac->ac_b_ex.fe_len);
Alex Tomasc9de5602008-01-29 00:19:52 -05003003 if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
3004 gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
Aneesh Kumar K.V560671a2009-01-05 22:20:24 -05003005 ext4_free_blks_set(sb, gdp,
3006 ext4_free_blocks_after_init(sb,
3007 ac->ac_b_ex.fe_group, gdp));
Alex Tomasc9de5602008-01-29 00:19:52 -05003008 }
Aneesh Kumar K.V560671a2009-01-05 22:20:24 -05003009 len = ext4_free_blks_count(sb, gdp) - ac->ac_b_ex.fe_len;
3010 ext4_free_blks_set(sb, gdp, len);
Alex Tomasc9de5602008-01-29 00:19:52 -05003011 gdp->bg_checksum = ext4_group_desc_csum(sbi, ac->ac_b_ex.fe_group, gdp);
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04003012
3013 ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04003014 percpu_counter_sub(&sbi->s_freeblocks_counter, ac->ac_b_ex.fe_len);
Mingming Caod2a17632008-07-14 17:52:37 -04003015 /*
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04003016 * Now reduce the dirty block count also. Should not go negative
Mingming Caod2a17632008-07-14 17:52:37 -04003017 */
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04003018 if (!(ac->ac_flags & EXT4_MB_DELALLOC_RESERVED))
3019 /* release all the reserved blocks if non delalloc */
3020 percpu_counter_sub(&sbi->s_dirtyblocks_counter, reserv_blks);
Mingming Cao60e58e02009-01-22 18:13:05 +01003021 else {
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04003022 percpu_counter_sub(&sbi->s_dirtyblocks_counter,
3023 ac->ac_b_ex.fe_len);
Mingming Cao60e58e02009-01-22 18:13:05 +01003024 /* convert reserved quota blocks to real quota blocks */
3025 vfs_dq_claim_block(ac->ac_inode, ac->ac_b_ex.fe_len);
3026 }
Alex Tomasc9de5602008-01-29 00:19:52 -05003027
Jose R. Santos772cb7c2008-07-11 19:27:31 -04003028 if (sbi->s_log_groups_per_flex) {
3029 ext4_group_t flex_group = ext4_flex_group(sbi,
3030 ac->ac_b_ex.fe_group);
Theodore Ts'o9f24e422009-03-04 19:09:10 -05003031 atomic_sub(ac->ac_b_ex.fe_len,
3032 &sbi->s_flex_groups[flex_group].free_blocks);
Jose R. Santos772cb7c2008-07-11 19:27:31 -04003033 }
3034
Frank Mayhar03901312009-01-07 00:06:22 -05003035 err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
Alex Tomasc9de5602008-01-29 00:19:52 -05003036 if (err)
3037 goto out_err;
Frank Mayhar03901312009-01-07 00:06:22 -05003038 err = ext4_handle_dirty_metadata(handle, NULL, gdp_bh);
Alex Tomasc9de5602008-01-29 00:19:52 -05003039
3040out_err:
3041 sb->s_dirt = 1;
Aneesh Kumar K.V42a10ad2008-02-10 01:07:28 -05003042 brelse(bitmap_bh);
Alex Tomasc9de5602008-01-29 00:19:52 -05003043 return err;
3044}
3045
3046/*
3047 * here we normalize request for locality group
3048 * Group request are normalized to s_strip size if we set the same via mount
3049 * option. If not we set it to s_mb_group_prealloc which can be configured via
Theodore Ts'ob713a5e2009-03-31 09:11:14 -04003050 * /sys/fs/ext4/<partition>/mb_group_prealloc
Alex Tomasc9de5602008-01-29 00:19:52 -05003051 *
3052 * XXX: should we try to preallocate more than the group has now?
3053 */
3054static void ext4_mb_normalize_group_request(struct ext4_allocation_context *ac)
3055{
3056 struct super_block *sb = ac->ac_sb;
3057 struct ext4_locality_group *lg = ac->ac_lg;
3058
3059 BUG_ON(lg == NULL);
3060 if (EXT4_SB(sb)->s_stripe)
3061 ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_stripe;
3062 else
3063 ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_mb_group_prealloc;
Solofo Ramangalahy60bd63d2008-04-29 21:59:59 -04003064 mb_debug("#%u: goal %u blocks for locality group\n",
Alex Tomasc9de5602008-01-29 00:19:52 -05003065 current->pid, ac->ac_g_ex.fe_len);
3066}
3067
3068/*
3069 * Normalization means making request better in terms of
3070 * size and alignment
3071 */
Eric Sandeen4ddfef72008-04-29 08:11:12 -04003072static noinline_for_stack void
3073ext4_mb_normalize_request(struct ext4_allocation_context *ac,
Alex Tomasc9de5602008-01-29 00:19:52 -05003074 struct ext4_allocation_request *ar)
3075{
3076 int bsbits, max;
3077 ext4_lblk_t end;
Alex Tomasc9de5602008-01-29 00:19:52 -05003078 loff_t size, orig_size, start_off;
3079 ext4_lblk_t start, orig_start;
3080 struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
Aneesh Kumar K.V9a0762c2008-04-17 10:38:59 -04003081 struct ext4_prealloc_space *pa;
Alex Tomasc9de5602008-01-29 00:19:52 -05003082
3083 /* do normalize only data requests, metadata requests
3084 do not need preallocation */
3085 if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
3086 return;
3087
3088 /* sometime caller may want exact blocks */
3089 if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
3090 return;
3091
3092 /* caller may indicate that preallocation isn't
3093 * required (it's a tail, for example) */
3094 if (ac->ac_flags & EXT4_MB_HINT_NOPREALLOC)
3095 return;
3096
3097 if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) {
3098 ext4_mb_normalize_group_request(ac);
3099 return ;
3100 }
3101
3102 bsbits = ac->ac_sb->s_blocksize_bits;
3103
3104 /* first, let's learn actual file size
3105 * given current request is allocated */
3106 size = ac->ac_o_ex.fe_logical + ac->ac_o_ex.fe_len;
3107 size = size << bsbits;
3108 if (size < i_size_read(ac->ac_inode))
3109 size = i_size_read(ac->ac_inode);
3110
Valerie Clement19304792008-05-13 19:31:14 -04003111 /* max size of free chunks */
3112 max = 2 << bsbits;
Alex Tomasc9de5602008-01-29 00:19:52 -05003113
Valerie Clement19304792008-05-13 19:31:14 -04003114#define NRL_CHECK_SIZE(req, size, max, chunk_size) \
3115 (req <= (size) || max <= (chunk_size))
Alex Tomasc9de5602008-01-29 00:19:52 -05003116
3117 /* first, try to predict filesize */
3118 /* XXX: should this table be tunable? */
3119 start_off = 0;
3120 if (size <= 16 * 1024) {
3121 size = 16 * 1024;
3122 } else if (size <= 32 * 1024) {
3123 size = 32 * 1024;
3124 } else if (size <= 64 * 1024) {
3125 size = 64 * 1024;
3126 } else if (size <= 128 * 1024) {
3127 size = 128 * 1024;
3128 } else if (size <= 256 * 1024) {
3129 size = 256 * 1024;
3130 } else if (size <= 512 * 1024) {
3131 size = 512 * 1024;
3132 } else if (size <= 1024 * 1024) {
3133 size = 1024 * 1024;
Valerie Clement19304792008-05-13 19:31:14 -04003134 } else if (NRL_CHECK_SIZE(size, 4 * 1024 * 1024, max, 2 * 1024)) {
Alex Tomasc9de5602008-01-29 00:19:52 -05003135 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
Valerie Clement19304792008-05-13 19:31:14 -04003136 (21 - bsbits)) << 21;
3137 size = 2 * 1024 * 1024;
3138 } else if (NRL_CHECK_SIZE(size, 8 * 1024 * 1024, max, 4 * 1024)) {
Alex Tomasc9de5602008-01-29 00:19:52 -05003139 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
3140 (22 - bsbits)) << 22;
3141 size = 4 * 1024 * 1024;
3142 } else if (NRL_CHECK_SIZE(ac->ac_o_ex.fe_len,
Valerie Clement19304792008-05-13 19:31:14 -04003143 (8<<20)>>bsbits, max, 8 * 1024)) {
Alex Tomasc9de5602008-01-29 00:19:52 -05003144 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
3145 (23 - bsbits)) << 23;
3146 size = 8 * 1024 * 1024;
3147 } else {
3148 start_off = (loff_t)ac->ac_o_ex.fe_logical << bsbits;
3149 size = ac->ac_o_ex.fe_len << bsbits;
3150 }
3151 orig_size = size = size >> bsbits;
3152 orig_start = start = start_off >> bsbits;
3153
3154 /* don't cover already allocated blocks in selected range */
3155 if (ar->pleft && start <= ar->lleft) {
3156 size -= ar->lleft + 1 - start;
3157 start = ar->lleft + 1;
3158 }
3159 if (ar->pright && start + size - 1 >= ar->lright)
3160 size -= start + size - ar->lright;
3161
3162 end = start + size;
3163
3164 /* check we don't cross already preallocated blocks */
3165 rcu_read_lock();
Aneesh Kumar K.V9a0762c2008-04-17 10:38:59 -04003166 list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
Theodore Ts'o498e5f22008-11-05 00:14:04 -05003167 ext4_lblk_t pa_end;
Alex Tomasc9de5602008-01-29 00:19:52 -05003168
Alex Tomasc9de5602008-01-29 00:19:52 -05003169 if (pa->pa_deleted)
3170 continue;
3171 spin_lock(&pa->pa_lock);
3172 if (pa->pa_deleted) {
3173 spin_unlock(&pa->pa_lock);
3174 continue;
3175 }
3176
3177 pa_end = pa->pa_lstart + pa->pa_len;
3178
3179 /* PA must not overlap original request */
3180 BUG_ON(!(ac->ac_o_ex.fe_logical >= pa_end ||
3181 ac->ac_o_ex.fe_logical < pa->pa_lstart));
3182
3183 /* skip PA normalized request doesn't overlap with */
3184 if (pa->pa_lstart >= end) {
3185 spin_unlock(&pa->pa_lock);
3186 continue;
3187 }
3188 if (pa_end <= start) {
3189 spin_unlock(&pa->pa_lock);
3190 continue;
3191 }
3192 BUG_ON(pa->pa_lstart <= start && pa_end >= end);
3193
3194 if (pa_end <= ac->ac_o_ex.fe_logical) {
3195 BUG_ON(pa_end < start);
3196 start = pa_end;
3197 }
3198
3199 if (pa->pa_lstart > ac->ac_o_ex.fe_logical) {
3200 BUG_ON(pa->pa_lstart > end);
3201 end = pa->pa_lstart;
3202 }
3203 spin_unlock(&pa->pa_lock);
3204 }
3205 rcu_read_unlock();
3206 size = end - start;
3207
3208 /* XXX: extra loop to check we really don't overlap preallocations */
3209 rcu_read_lock();
Aneesh Kumar K.V9a0762c2008-04-17 10:38:59 -04003210 list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
Theodore Ts'o498e5f22008-11-05 00:14:04 -05003211 ext4_lblk_t pa_end;
Alex Tomasc9de5602008-01-29 00:19:52 -05003212 spin_lock(&pa->pa_lock);
3213 if (pa->pa_deleted == 0) {
3214 pa_end = pa->pa_lstart + pa->pa_len;
3215 BUG_ON(!(start >= pa_end || end <= pa->pa_lstart));
3216 }
3217 spin_unlock(&pa->pa_lock);
3218 }
3219 rcu_read_unlock();
3220
3221 if (start + size <= ac->ac_o_ex.fe_logical &&
3222 start > ac->ac_o_ex.fe_logical) {
3223 printk(KERN_ERR "start %lu, size %lu, fe_logical %lu\n",
3224 (unsigned long) start, (unsigned long) size,
3225 (unsigned long) ac->ac_o_ex.fe_logical);
3226 }
3227 BUG_ON(start + size <= ac->ac_o_ex.fe_logical &&
3228 start > ac->ac_o_ex.fe_logical);
Eric Sandeen8d03c7a2009-03-14 11:51:46 -04003229 BUG_ON(size <= 0 || size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb));
Alex Tomasc9de5602008-01-29 00:19:52 -05003230
3231 /* now prepare goal request */
3232
3233 /* XXX: is it better to align blocks WRT to logical
3234 * placement or satisfy big request as is */
3235 ac->ac_g_ex.fe_logical = start;
3236 ac->ac_g_ex.fe_len = size;
3237
3238 /* define goal start in order to merge */
3239 if (ar->pright && (ar->lright == (start + size))) {
3240 /* merge to the right */
3241 ext4_get_group_no_and_offset(ac->ac_sb, ar->pright - size,
3242 &ac->ac_f_ex.fe_group,
3243 &ac->ac_f_ex.fe_start);
3244 ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
3245 }
3246 if (ar->pleft && (ar->lleft + 1 == start)) {
3247 /* merge to the left */
3248 ext4_get_group_no_and_offset(ac->ac_sb, ar->pleft + 1,
3249 &ac->ac_f_ex.fe_group,
3250 &ac->ac_f_ex.fe_start);
3251 ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
3252 }
3253
3254 mb_debug("goal: %u(was %u) blocks at %u\n", (unsigned) size,
3255 (unsigned) orig_size, (unsigned) start);
3256}
3257
3258static void ext4_mb_collect_stats(struct ext4_allocation_context *ac)
3259{
3260 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3261
3262 if (sbi->s_mb_stats && ac->ac_g_ex.fe_len > 1) {
3263 atomic_inc(&sbi->s_bal_reqs);
3264 atomic_add(ac->ac_b_ex.fe_len, &sbi->s_bal_allocated);
3265 if (ac->ac_o_ex.fe_len >= ac->ac_g_ex.fe_len)
3266 atomic_inc(&sbi->s_bal_success);
3267 atomic_add(ac->ac_found, &sbi->s_bal_ex_scanned);
3268 if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&
3269 ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)
3270 atomic_inc(&sbi->s_bal_goals);
3271 if (ac->ac_found > sbi->s_mb_max_to_scan)
3272 atomic_inc(&sbi->s_bal_breaks);
3273 }
3274
3275 ext4_mb_store_history(ac);
3276}
3277
3278/*
3279 * use blocks preallocated to inode
3280 */
3281static void ext4_mb_use_inode_pa(struct ext4_allocation_context *ac,
3282 struct ext4_prealloc_space *pa)
3283{
3284 ext4_fsblk_t start;
3285 ext4_fsblk_t end;
3286 int len;
3287
3288 /* found preallocated blocks, use them */
3289 start = pa->pa_pstart + (ac->ac_o_ex.fe_logical - pa->pa_lstart);
3290 end = min(pa->pa_pstart + pa->pa_len, start + ac->ac_o_ex.fe_len);
3291 len = end - start;
3292 ext4_get_group_no_and_offset(ac->ac_sb, start, &ac->ac_b_ex.fe_group,
3293 &ac->ac_b_ex.fe_start);
3294 ac->ac_b_ex.fe_len = len;
3295 ac->ac_status = AC_STATUS_FOUND;
3296 ac->ac_pa = pa;
3297
3298 BUG_ON(start < pa->pa_pstart);
3299 BUG_ON(start + len > pa->pa_pstart + pa->pa_len);
3300 BUG_ON(pa->pa_free < len);
3301 pa->pa_free -= len;
3302
Solofo Ramangalahy60bd63d2008-04-29 21:59:59 -04003303 mb_debug("use %llu/%u from inode pa %p\n", start, len, pa);
Alex Tomasc9de5602008-01-29 00:19:52 -05003304}
3305
3306/*
3307 * use blocks preallocated to locality group
3308 */
3309static void ext4_mb_use_group_pa(struct ext4_allocation_context *ac,
3310 struct ext4_prealloc_space *pa)
3311{
Aneesh Kumar K.V03cddb82008-06-05 20:59:29 -04003312 unsigned int len = ac->ac_o_ex.fe_len;
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04003313
Alex Tomasc9de5602008-01-29 00:19:52 -05003314 ext4_get_group_no_and_offset(ac->ac_sb, pa->pa_pstart,
3315 &ac->ac_b_ex.fe_group,
3316 &ac->ac_b_ex.fe_start);
3317 ac->ac_b_ex.fe_len = len;
3318 ac->ac_status = AC_STATUS_FOUND;
3319 ac->ac_pa = pa;
3320
3321 /* we don't correct pa_pstart or pa_plen here to avoid
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05003322 * possible race when the group is being loaded concurrently
Alex Tomasc9de5602008-01-29 00:19:52 -05003323 * instead we correct pa later, after blocks are marked
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05003324 * in on-disk bitmap -- see ext4_mb_release_context()
3325 * Other CPUs are prevented from allocating from this pa by lg_mutex
Alex Tomasc9de5602008-01-29 00:19:52 -05003326 */
3327 mb_debug("use %u/%u from group pa %p\n", pa->pa_lstart-len, len, pa);
3328}
3329
3330/*
Aneesh Kumar K.V5e745b02008-08-18 18:00:57 -04003331 * Return the prealloc space that have minimal distance
3332 * from the goal block. @cpa is the prealloc
3333 * space that is having currently known minimal distance
3334 * from the goal block.
3335 */
3336static struct ext4_prealloc_space *
3337ext4_mb_check_group_pa(ext4_fsblk_t goal_block,
3338 struct ext4_prealloc_space *pa,
3339 struct ext4_prealloc_space *cpa)
3340{
3341 ext4_fsblk_t cur_distance, new_distance;
3342
3343 if (cpa == NULL) {
3344 atomic_inc(&pa->pa_count);
3345 return pa;
3346 }
3347 cur_distance = abs(goal_block - cpa->pa_pstart);
3348 new_distance = abs(goal_block - pa->pa_pstart);
3349
3350 if (cur_distance < new_distance)
3351 return cpa;
3352
3353 /* drop the previous reference */
3354 atomic_dec(&cpa->pa_count);
3355 atomic_inc(&pa->pa_count);
3356 return pa;
3357}
3358
3359/*
Alex Tomasc9de5602008-01-29 00:19:52 -05003360 * search goal blocks in preallocated space
3361 */
Eric Sandeen4ddfef72008-04-29 08:11:12 -04003362static noinline_for_stack int
3363ext4_mb_use_preallocated(struct ext4_allocation_context *ac)
Alex Tomasc9de5602008-01-29 00:19:52 -05003364{
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04003365 int order, i;
Alex Tomasc9de5602008-01-29 00:19:52 -05003366 struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
3367 struct ext4_locality_group *lg;
Aneesh Kumar K.V5e745b02008-08-18 18:00:57 -04003368 struct ext4_prealloc_space *pa, *cpa = NULL;
3369 ext4_fsblk_t goal_block;
Alex Tomasc9de5602008-01-29 00:19:52 -05003370
3371 /* only data can be preallocated */
3372 if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
3373 return 0;
3374
3375 /* first, try per-file preallocation */
3376 rcu_read_lock();
Aneesh Kumar K.V9a0762c2008-04-17 10:38:59 -04003377 list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
Alex Tomasc9de5602008-01-29 00:19:52 -05003378
3379 /* all fields in this condition don't change,
3380 * so we can skip locking for them */
3381 if (ac->ac_o_ex.fe_logical < pa->pa_lstart ||
3382 ac->ac_o_ex.fe_logical >= pa->pa_lstart + pa->pa_len)
3383 continue;
3384
3385 /* found preallocated blocks, use them */
3386 spin_lock(&pa->pa_lock);
3387 if (pa->pa_deleted == 0 && pa->pa_free) {
3388 atomic_inc(&pa->pa_count);
3389 ext4_mb_use_inode_pa(ac, pa);
3390 spin_unlock(&pa->pa_lock);
3391 ac->ac_criteria = 10;
3392 rcu_read_unlock();
3393 return 1;
3394 }
3395 spin_unlock(&pa->pa_lock);
3396 }
3397 rcu_read_unlock();
3398
3399 /* can we use group allocation? */
3400 if (!(ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC))
3401 return 0;
3402
3403 /* inode may have no locality group for some reason */
3404 lg = ac->ac_lg;
3405 if (lg == NULL)
3406 return 0;
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04003407 order = fls(ac->ac_o_ex.fe_len) - 1;
3408 if (order > PREALLOC_TB_SIZE - 1)
3409 /* The max size of hash table is PREALLOC_TB_SIZE */
3410 order = PREALLOC_TB_SIZE - 1;
Alex Tomasc9de5602008-01-29 00:19:52 -05003411
Aneesh Kumar K.V5e745b02008-08-18 18:00:57 -04003412 goal_block = ac->ac_g_ex.fe_group * EXT4_BLOCKS_PER_GROUP(ac->ac_sb) +
3413 ac->ac_g_ex.fe_start +
3414 le32_to_cpu(EXT4_SB(ac->ac_sb)->s_es->s_first_data_block);
3415 /*
3416 * search for the prealloc space that is having
3417 * minimal distance from the goal block.
3418 */
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04003419 for (i = order; i < PREALLOC_TB_SIZE; i++) {
3420 rcu_read_lock();
3421 list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[i],
3422 pa_inode_list) {
3423 spin_lock(&pa->pa_lock);
3424 if (pa->pa_deleted == 0 &&
3425 pa->pa_free >= ac->ac_o_ex.fe_len) {
Aneesh Kumar K.V5e745b02008-08-18 18:00:57 -04003426
3427 cpa = ext4_mb_check_group_pa(goal_block,
3428 pa, cpa);
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04003429 }
Alex Tomasc9de5602008-01-29 00:19:52 -05003430 spin_unlock(&pa->pa_lock);
Alex Tomasc9de5602008-01-29 00:19:52 -05003431 }
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04003432 rcu_read_unlock();
Alex Tomasc9de5602008-01-29 00:19:52 -05003433 }
Aneesh Kumar K.V5e745b02008-08-18 18:00:57 -04003434 if (cpa) {
3435 ext4_mb_use_group_pa(ac, cpa);
3436 ac->ac_criteria = 20;
3437 return 1;
3438 }
Alex Tomasc9de5602008-01-29 00:19:52 -05003439 return 0;
3440}
3441
3442/*
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -05003443 * the function goes through all block freed in the group
3444 * but not yet committed and marks them used in in-core bitmap.
3445 * buddy must be generated from this bitmap
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04003446 * Need to be called with the ext4 group lock held
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -05003447 */
3448static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
3449 ext4_group_t group)
3450{
3451 struct rb_node *n;
3452 struct ext4_group_info *grp;
3453 struct ext4_free_data *entry;
3454
3455 grp = ext4_get_group_info(sb, group);
3456 n = rb_first(&(grp->bb_free_root));
3457
3458 while (n) {
3459 entry = rb_entry(n, struct ext4_free_data, node);
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04003460 mb_set_bits(bitmap, entry->start_blk, entry->count);
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -05003461 n = rb_next(n);
3462 }
3463 return;
3464}
3465
3466/*
Alex Tomasc9de5602008-01-29 00:19:52 -05003467 * the function goes through all preallocation in this group and marks them
3468 * used in in-core bitmap. buddy must be generated from this bitmap
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04003469 * Need to be called with ext4 group lock held
Alex Tomasc9de5602008-01-29 00:19:52 -05003470 */
Eric Sandeen089ceec2009-07-05 22:17:31 -04003471static noinline_for_stack
3472void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,
Alex Tomasc9de5602008-01-29 00:19:52 -05003473 ext4_group_t group)
3474{
3475 struct ext4_group_info *grp = ext4_get_group_info(sb, group);
3476 struct ext4_prealloc_space *pa;
3477 struct list_head *cur;
3478 ext4_group_t groupnr;
3479 ext4_grpblk_t start;
3480 int preallocated = 0;
3481 int count = 0;
3482 int len;
3483
3484 /* all form of preallocation discards first load group,
3485 * so the only competing code is preallocation use.
3486 * we don't need any locking here
3487 * notice we do NOT ignore preallocations with pa_deleted
3488 * otherwise we could leave used blocks available for
3489 * allocation in buddy when concurrent ext4_mb_put_pa()
3490 * is dropping preallocation
3491 */
3492 list_for_each(cur, &grp->bb_prealloc_list) {
3493 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
3494 spin_lock(&pa->pa_lock);
3495 ext4_get_group_no_and_offset(sb, pa->pa_pstart,
3496 &groupnr, &start);
3497 len = pa->pa_len;
3498 spin_unlock(&pa->pa_lock);
3499 if (unlikely(len == 0))
3500 continue;
3501 BUG_ON(groupnr != group);
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04003502 mb_set_bits(bitmap, start, len);
Alex Tomasc9de5602008-01-29 00:19:52 -05003503 preallocated += len;
3504 count++;
3505 }
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05003506 mb_debug("prellocated %u for group %u\n", preallocated, group);
Alex Tomasc9de5602008-01-29 00:19:52 -05003507}
3508
3509static void ext4_mb_pa_callback(struct rcu_head *head)
3510{
3511 struct ext4_prealloc_space *pa;
3512 pa = container_of(head, struct ext4_prealloc_space, u.pa_rcu);
3513 kmem_cache_free(ext4_pspace_cachep, pa);
3514}
3515
3516/*
3517 * drops a reference to preallocated space descriptor
3518 * if this was the last reference and the space is consumed
3519 */
3520static void ext4_mb_put_pa(struct ext4_allocation_context *ac,
3521 struct super_block *sb, struct ext4_prealloc_space *pa)
3522{
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05003523 ext4_group_t grp;
Eric Sandeend33a1972009-03-16 23:25:40 -04003524 ext4_fsblk_t grp_blk;
Alex Tomasc9de5602008-01-29 00:19:52 -05003525
3526 if (!atomic_dec_and_test(&pa->pa_count) || pa->pa_free != 0)
3527 return;
3528
3529 /* in this short window concurrent discard can set pa_deleted */
3530 spin_lock(&pa->pa_lock);
3531 if (pa->pa_deleted == 1) {
3532 spin_unlock(&pa->pa_lock);
3533 return;
3534 }
3535
3536 pa->pa_deleted = 1;
3537 spin_unlock(&pa->pa_lock);
3538
Eric Sandeend33a1972009-03-16 23:25:40 -04003539 grp_blk = pa->pa_pstart;
Aneesh Kumar K.Vcc0fb9a2009-03-27 17:16:58 -04003540 /*
3541 * If doing group-based preallocation, pa_pstart may be in the
3542 * next group when pa is used up
3543 */
3544 if (pa->pa_type == MB_GROUP_PA)
Eric Sandeend33a1972009-03-16 23:25:40 -04003545 grp_blk--;
3546
3547 ext4_get_group_no_and_offset(sb, grp_blk, &grp, NULL);
Alex Tomasc9de5602008-01-29 00:19:52 -05003548
3549 /*
3550 * possible race:
3551 *
3552 * P1 (buddy init) P2 (regular allocation)
3553 * find block B in PA
3554 * copy on-disk bitmap to buddy
3555 * mark B in on-disk bitmap
3556 * drop PA from group
3557 * mark all PAs in buddy
3558 *
3559 * thus, P1 initializes buddy with B available. to prevent this
3560 * we make "copy" and "mark all PAs" atomic and serialize "drop PA"
3561 * against that pair
3562 */
3563 ext4_lock_group(sb, grp);
3564 list_del(&pa->pa_group_list);
3565 ext4_unlock_group(sb, grp);
3566
3567 spin_lock(pa->pa_obj_lock);
3568 list_del_rcu(&pa->pa_inode_list);
3569 spin_unlock(pa->pa_obj_lock);
3570
3571 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
3572}
3573
3574/*
3575 * creates new preallocated space for given inode
3576 */
Eric Sandeen4ddfef72008-04-29 08:11:12 -04003577static noinline_for_stack int
3578ext4_mb_new_inode_pa(struct ext4_allocation_context *ac)
Alex Tomasc9de5602008-01-29 00:19:52 -05003579{
3580 struct super_block *sb = ac->ac_sb;
3581 struct ext4_prealloc_space *pa;
3582 struct ext4_group_info *grp;
3583 struct ext4_inode_info *ei;
3584
3585 /* preallocate only when found space is larger then requested */
3586 BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
3587 BUG_ON(ac->ac_status != AC_STATUS_FOUND);
3588 BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
3589
3590 pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS);
3591 if (pa == NULL)
3592 return -ENOMEM;
3593
3594 if (ac->ac_b_ex.fe_len < ac->ac_g_ex.fe_len) {
3595 int winl;
3596 int wins;
3597 int win;
3598 int offs;
3599
3600 /* we can't allocate as much as normalizer wants.
3601 * so, found space must get proper lstart
3602 * to cover original request */
3603 BUG_ON(ac->ac_g_ex.fe_logical > ac->ac_o_ex.fe_logical);
3604 BUG_ON(ac->ac_g_ex.fe_len < ac->ac_o_ex.fe_len);
3605
3606 /* we're limited by original request in that
3607 * logical block must be covered any way
3608 * winl is window we can move our chunk within */
3609 winl = ac->ac_o_ex.fe_logical - ac->ac_g_ex.fe_logical;
3610
3611 /* also, we should cover whole original request */
3612 wins = ac->ac_b_ex.fe_len - ac->ac_o_ex.fe_len;
3613
3614 /* the smallest one defines real window */
3615 win = min(winl, wins);
3616
3617 offs = ac->ac_o_ex.fe_logical % ac->ac_b_ex.fe_len;
3618 if (offs && offs < win)
3619 win = offs;
3620
3621 ac->ac_b_ex.fe_logical = ac->ac_o_ex.fe_logical - win;
3622 BUG_ON(ac->ac_o_ex.fe_logical < ac->ac_b_ex.fe_logical);
3623 BUG_ON(ac->ac_o_ex.fe_len > ac->ac_b_ex.fe_len);
3624 }
3625
3626 /* preallocation can change ac_b_ex, thus we store actually
3627 * allocated blocks for history */
3628 ac->ac_f_ex = ac->ac_b_ex;
3629
3630 pa->pa_lstart = ac->ac_b_ex.fe_logical;
3631 pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
3632 pa->pa_len = ac->ac_b_ex.fe_len;
3633 pa->pa_free = pa->pa_len;
3634 atomic_set(&pa->pa_count, 1);
3635 spin_lock_init(&pa->pa_lock);
Aneesh Kumar K.Vd794bf82009-02-14 10:31:16 -05003636 INIT_LIST_HEAD(&pa->pa_inode_list);
3637 INIT_LIST_HEAD(&pa->pa_group_list);
Alex Tomasc9de5602008-01-29 00:19:52 -05003638 pa->pa_deleted = 0;
Aneesh Kumar K.Vcc0fb9a2009-03-27 17:16:58 -04003639 pa->pa_type = MB_INODE_PA;
Alex Tomasc9de5602008-01-29 00:19:52 -05003640
3641 mb_debug("new inode pa %p: %llu/%u for %u\n", pa,
3642 pa->pa_pstart, pa->pa_len, pa->pa_lstart);
Theodore Ts'o9bffad12009-06-17 11:48:11 -04003643 trace_ext4_mb_new_inode_pa(ac, pa);
Alex Tomasc9de5602008-01-29 00:19:52 -05003644
3645 ext4_mb_use_inode_pa(ac, pa);
3646 atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated);
3647
3648 ei = EXT4_I(ac->ac_inode);
3649 grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
3650
3651 pa->pa_obj_lock = &ei->i_prealloc_lock;
3652 pa->pa_inode = ac->ac_inode;
3653
3654 ext4_lock_group(sb, ac->ac_b_ex.fe_group);
3655 list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
3656 ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
3657
3658 spin_lock(pa->pa_obj_lock);
3659 list_add_rcu(&pa->pa_inode_list, &ei->i_prealloc_list);
3660 spin_unlock(pa->pa_obj_lock);
3661
3662 return 0;
3663}
3664
3665/*
3666 * creates new preallocated space for locality group inodes belongs to
3667 */
Eric Sandeen4ddfef72008-04-29 08:11:12 -04003668static noinline_for_stack int
3669ext4_mb_new_group_pa(struct ext4_allocation_context *ac)
Alex Tomasc9de5602008-01-29 00:19:52 -05003670{
3671 struct super_block *sb = ac->ac_sb;
3672 struct ext4_locality_group *lg;
3673 struct ext4_prealloc_space *pa;
3674 struct ext4_group_info *grp;
3675
3676 /* preallocate only when found space is larger then requested */
3677 BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
3678 BUG_ON(ac->ac_status != AC_STATUS_FOUND);
3679 BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
3680
3681 BUG_ON(ext4_pspace_cachep == NULL);
3682 pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS);
3683 if (pa == NULL)
3684 return -ENOMEM;
3685
3686 /* preallocation can change ac_b_ex, thus we store actually
3687 * allocated blocks for history */
3688 ac->ac_f_ex = ac->ac_b_ex;
3689
3690 pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
3691 pa->pa_lstart = pa->pa_pstart;
3692 pa->pa_len = ac->ac_b_ex.fe_len;
3693 pa->pa_free = pa->pa_len;
3694 atomic_set(&pa->pa_count, 1);
3695 spin_lock_init(&pa->pa_lock);
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04003696 INIT_LIST_HEAD(&pa->pa_inode_list);
Aneesh Kumar K.Vd794bf82009-02-14 10:31:16 -05003697 INIT_LIST_HEAD(&pa->pa_group_list);
Alex Tomasc9de5602008-01-29 00:19:52 -05003698 pa->pa_deleted = 0;
Aneesh Kumar K.Vcc0fb9a2009-03-27 17:16:58 -04003699 pa->pa_type = MB_GROUP_PA;
Alex Tomasc9de5602008-01-29 00:19:52 -05003700
3701 mb_debug("new group pa %p: %llu/%u for %u\n", pa,
Theodore Ts'o9bffad12009-06-17 11:48:11 -04003702 pa->pa_pstart, pa->pa_len, pa->pa_lstart);
3703 trace_ext4_mb_new_group_pa(ac, pa);
Alex Tomasc9de5602008-01-29 00:19:52 -05003704
3705 ext4_mb_use_group_pa(ac, pa);
3706 atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated);
3707
3708 grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
3709 lg = ac->ac_lg;
3710 BUG_ON(lg == NULL);
3711
3712 pa->pa_obj_lock = &lg->lg_prealloc_lock;
3713 pa->pa_inode = NULL;
3714
3715 ext4_lock_group(sb, ac->ac_b_ex.fe_group);
3716 list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
3717 ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
3718
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04003719 /*
3720 * We will later add the new pa to the right bucket
3721 * after updating the pa_free in ext4_mb_release_context
3722 */
Alex Tomasc9de5602008-01-29 00:19:52 -05003723 return 0;
3724}
3725
3726static int ext4_mb_new_preallocation(struct ext4_allocation_context *ac)
3727{
3728 int err;
3729
3730 if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
3731 err = ext4_mb_new_group_pa(ac);
3732 else
3733 err = ext4_mb_new_inode_pa(ac);
3734 return err;
3735}
3736
3737/*
3738 * finds all unused blocks in on-disk bitmap, frees them in
3739 * in-core bitmap and buddy.
3740 * @pa must be unlinked from inode and group lists, so that
3741 * nobody else can find/use it.
3742 * the caller MUST hold group/inode locks.
3743 * TODO: optimize the case when there are no in-core structures yet
3744 */
Eric Sandeen4ddfef72008-04-29 08:11:12 -04003745static noinline_for_stack int
3746ext4_mb_release_inode_pa(struct ext4_buddy *e4b, struct buffer_head *bitmap_bh,
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003747 struct ext4_prealloc_space *pa,
3748 struct ext4_allocation_context *ac)
Alex Tomasc9de5602008-01-29 00:19:52 -05003749{
Alex Tomasc9de5602008-01-29 00:19:52 -05003750 struct super_block *sb = e4b->bd_sb;
3751 struct ext4_sb_info *sbi = EXT4_SB(sb);
Theodore Ts'o498e5f22008-11-05 00:14:04 -05003752 unsigned int end;
3753 unsigned int next;
Alex Tomasc9de5602008-01-29 00:19:52 -05003754 ext4_group_t group;
3755 ext4_grpblk_t bit;
Theodore Ts'oba80b102009-01-03 20:03:21 -05003756 unsigned long long grp_blk_start;
Alex Tomasc9de5602008-01-29 00:19:52 -05003757 sector_t start;
3758 int err = 0;
3759 int free = 0;
3760
3761 BUG_ON(pa->pa_deleted == 0);
3762 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);
Theodore Ts'oba80b102009-01-03 20:03:21 -05003763 grp_blk_start = pa->pa_pstart - bit;
Alex Tomasc9de5602008-01-29 00:19:52 -05003764 BUG_ON(group != e4b->bd_group && pa->pa_len != 0);
3765 end = bit + pa->pa_len;
3766
Eric Sandeen256bdb42008-02-10 01:13:33 -05003767 if (ac) {
3768 ac->ac_sb = sb;
3769 ac->ac_inode = pa->pa_inode;
3770 ac->ac_op = EXT4_MB_HISTORY_DISCARD;
3771 }
Alex Tomasc9de5602008-01-29 00:19:52 -05003772
3773 while (bit < end) {
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -05003774 bit = mb_find_next_zero_bit(bitmap_bh->b_data, end, bit);
Alex Tomasc9de5602008-01-29 00:19:52 -05003775 if (bit >= end)
3776 break;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -05003777 next = mb_find_next_bit(bitmap_bh->b_data, end, bit);
Alex Tomasc9de5602008-01-29 00:19:52 -05003778 start = group * EXT4_BLOCKS_PER_GROUP(sb) + bit +
3779 le32_to_cpu(sbi->s_es->s_first_data_block);
3780 mb_debug(" free preallocated %u/%u in group %u\n",
3781 (unsigned) start, (unsigned) next - bit,
3782 (unsigned) group);
3783 free += next - bit;
3784
Eric Sandeen256bdb42008-02-10 01:13:33 -05003785 if (ac) {
3786 ac->ac_b_ex.fe_group = group;
3787 ac->ac_b_ex.fe_start = bit;
3788 ac->ac_b_ex.fe_len = next - bit;
3789 ac->ac_b_ex.fe_logical = 0;
3790 ext4_mb_store_history(ac);
3791 }
Alex Tomasc9de5602008-01-29 00:19:52 -05003792
Theodore Ts'o9bffad12009-06-17 11:48:11 -04003793 trace_ext4_mb_release_inode_pa(ac, pa, grp_blk_start + bit,
3794 next - bit);
Alex Tomasc9de5602008-01-29 00:19:52 -05003795 mb_free_blocks(pa->pa_inode, e4b, bit, next - bit);
3796 bit = next + 1;
3797 }
3798 if (free != pa->pa_free) {
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05003799 printk(KERN_CRIT "pa %p: logic %lu, phys. %lu, len %lu\n",
Alex Tomasc9de5602008-01-29 00:19:52 -05003800 pa, (unsigned long) pa->pa_lstart,
3801 (unsigned long) pa->pa_pstart,
3802 (unsigned long) pa->pa_len);
Aneesh Kumar K.V5d1b1b32009-01-05 22:19:52 -05003803 ext4_grp_locked_error(sb, group,
3804 __func__, "free %u, pa_free %u",
3805 free, pa->pa_free);
Aneesh Kumar K.Ve56eb652008-02-15 13:48:21 -05003806 /*
3807 * pa is already deleted so we use the value obtained
3808 * from the bitmap and continue.
3809 */
Alex Tomasc9de5602008-01-29 00:19:52 -05003810 }
Alex Tomasc9de5602008-01-29 00:19:52 -05003811 atomic_add(free, &sbi->s_mb_discarded);
3812
3813 return err;
3814}
3815
Eric Sandeen4ddfef72008-04-29 08:11:12 -04003816static noinline_for_stack int
3817ext4_mb_release_group_pa(struct ext4_buddy *e4b,
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003818 struct ext4_prealloc_space *pa,
3819 struct ext4_allocation_context *ac)
Alex Tomasc9de5602008-01-29 00:19:52 -05003820{
Alex Tomasc9de5602008-01-29 00:19:52 -05003821 struct super_block *sb = e4b->bd_sb;
3822 ext4_group_t group;
3823 ext4_grpblk_t bit;
3824
Eric Sandeen256bdb42008-02-10 01:13:33 -05003825 if (ac)
3826 ac->ac_op = EXT4_MB_HISTORY_DISCARD;
Alex Tomasc9de5602008-01-29 00:19:52 -05003827
Theodore Ts'o9bffad12009-06-17 11:48:11 -04003828 trace_ext4_mb_release_group_pa(ac, pa);
Alex Tomasc9de5602008-01-29 00:19:52 -05003829 BUG_ON(pa->pa_deleted == 0);
3830 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);
3831 BUG_ON(group != e4b->bd_group && pa->pa_len != 0);
3832 mb_free_blocks(pa->pa_inode, e4b, bit, pa->pa_len);
3833 atomic_add(pa->pa_len, &EXT4_SB(sb)->s_mb_discarded);
3834
Eric Sandeen256bdb42008-02-10 01:13:33 -05003835 if (ac) {
3836 ac->ac_sb = sb;
3837 ac->ac_inode = NULL;
3838 ac->ac_b_ex.fe_group = group;
3839 ac->ac_b_ex.fe_start = bit;
3840 ac->ac_b_ex.fe_len = pa->pa_len;
3841 ac->ac_b_ex.fe_logical = 0;
3842 ext4_mb_store_history(ac);
Eric Sandeen256bdb42008-02-10 01:13:33 -05003843 }
Alex Tomasc9de5602008-01-29 00:19:52 -05003844
3845 return 0;
3846}
3847
3848/*
3849 * releases all preallocations in given group
3850 *
3851 * first, we need to decide discard policy:
3852 * - when do we discard
3853 * 1) ENOSPC
3854 * - how many do we discard
3855 * 1) how many requested
3856 */
Eric Sandeen4ddfef72008-04-29 08:11:12 -04003857static noinline_for_stack int
3858ext4_mb_discard_group_preallocations(struct super_block *sb,
Alex Tomasc9de5602008-01-29 00:19:52 -05003859 ext4_group_t group, int needed)
3860{
3861 struct ext4_group_info *grp = ext4_get_group_info(sb, group);
3862 struct buffer_head *bitmap_bh = NULL;
3863 struct ext4_prealloc_space *pa, *tmp;
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003864 struct ext4_allocation_context *ac;
Alex Tomasc9de5602008-01-29 00:19:52 -05003865 struct list_head list;
3866 struct ext4_buddy e4b;
3867 int err;
3868 int busy = 0;
3869 int free = 0;
3870
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05003871 mb_debug("discard preallocation for group %u\n", group);
Alex Tomasc9de5602008-01-29 00:19:52 -05003872
3873 if (list_empty(&grp->bb_prealloc_list))
3874 return 0;
3875
Theodore Ts'o574ca172008-07-11 19:27:31 -04003876 bitmap_bh = ext4_read_block_bitmap(sb, group);
Alex Tomasc9de5602008-01-29 00:19:52 -05003877 if (bitmap_bh == NULL) {
Aneesh Kumar K.Vce89f462008-07-23 14:09:29 -04003878 ext4_error(sb, __func__, "Error in reading block "
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05003879 "bitmap for %u", group);
Aneesh Kumar K.Vce89f462008-07-23 14:09:29 -04003880 return 0;
Alex Tomasc9de5602008-01-29 00:19:52 -05003881 }
3882
3883 err = ext4_mb_load_buddy(sb, group, &e4b);
Aneesh Kumar K.Vce89f462008-07-23 14:09:29 -04003884 if (err) {
3885 ext4_error(sb, __func__, "Error in loading buddy "
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05003886 "information for %u", group);
Aneesh Kumar K.Vce89f462008-07-23 14:09:29 -04003887 put_bh(bitmap_bh);
3888 return 0;
3889 }
Alex Tomasc9de5602008-01-29 00:19:52 -05003890
3891 if (needed == 0)
3892 needed = EXT4_BLOCKS_PER_GROUP(sb) + 1;
3893
Alex Tomasc9de5602008-01-29 00:19:52 -05003894 INIT_LIST_HEAD(&list);
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003895 ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
Theodore Ts'o9bffad12009-06-17 11:48:11 -04003896 if (ac)
3897 ac->ac_sb = sb;
Alex Tomasc9de5602008-01-29 00:19:52 -05003898repeat:
3899 ext4_lock_group(sb, group);
3900 list_for_each_entry_safe(pa, tmp,
3901 &grp->bb_prealloc_list, pa_group_list) {
3902 spin_lock(&pa->pa_lock);
3903 if (atomic_read(&pa->pa_count)) {
3904 spin_unlock(&pa->pa_lock);
3905 busy = 1;
3906 continue;
3907 }
3908 if (pa->pa_deleted) {
3909 spin_unlock(&pa->pa_lock);
3910 continue;
3911 }
3912
3913 /* seems this one can be freed ... */
3914 pa->pa_deleted = 1;
3915
3916 /* we can trust pa_free ... */
3917 free += pa->pa_free;
3918
3919 spin_unlock(&pa->pa_lock);
3920
3921 list_del(&pa->pa_group_list);
3922 list_add(&pa->u.pa_tmp_list, &list);
3923 }
3924
3925 /* if we still need more blocks and some PAs were used, try again */
3926 if (free < needed && busy) {
3927 busy = 0;
3928 ext4_unlock_group(sb, group);
3929 /*
3930 * Yield the CPU here so that we don't get soft lockup
3931 * in non preempt case.
3932 */
3933 yield();
3934 goto repeat;
3935 }
3936
3937 /* found anything to free? */
3938 if (list_empty(&list)) {
3939 BUG_ON(free != 0);
3940 goto out;
3941 }
3942
3943 /* now free all selected PAs */
3944 list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {
3945
3946 /* remove from object (inode or locality group) */
3947 spin_lock(pa->pa_obj_lock);
3948 list_del_rcu(&pa->pa_inode_list);
3949 spin_unlock(pa->pa_obj_lock);
3950
Aneesh Kumar K.Vcc0fb9a2009-03-27 17:16:58 -04003951 if (pa->pa_type == MB_GROUP_PA)
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003952 ext4_mb_release_group_pa(&e4b, pa, ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05003953 else
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003954 ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa, ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05003955
3956 list_del(&pa->u.pa_tmp_list);
3957 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
3958 }
3959
3960out:
3961 ext4_unlock_group(sb, group);
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003962 if (ac)
3963 kmem_cache_free(ext4_ac_cachep, ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05003964 ext4_mb_release_desc(&e4b);
3965 put_bh(bitmap_bh);
3966 return free;
3967}
3968
3969/*
3970 * releases all non-used preallocated blocks for given inode
3971 *
3972 * It's important to discard preallocations under i_data_sem
3973 * We don't want another block to be served from the prealloc
3974 * space when we are discarding the inode prealloc space.
3975 *
3976 * FIXME!! Make sure it is valid at all the call sites
3977 */
Theodore Ts'oc2ea3fd2008-10-10 09:40:52 -04003978void ext4_discard_preallocations(struct inode *inode)
Alex Tomasc9de5602008-01-29 00:19:52 -05003979{
3980 struct ext4_inode_info *ei = EXT4_I(inode);
3981 struct super_block *sb = inode->i_sb;
3982 struct buffer_head *bitmap_bh = NULL;
3983 struct ext4_prealloc_space *pa, *tmp;
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003984 struct ext4_allocation_context *ac;
Alex Tomasc9de5602008-01-29 00:19:52 -05003985 ext4_group_t group = 0;
3986 struct list_head list;
3987 struct ext4_buddy e4b;
3988 int err;
3989
Theodore Ts'oc2ea3fd2008-10-10 09:40:52 -04003990 if (!S_ISREG(inode->i_mode)) {
Alex Tomasc9de5602008-01-29 00:19:52 -05003991 /*BUG_ON(!list_empty(&ei->i_prealloc_list));*/
3992 return;
3993 }
3994
3995 mb_debug("discard preallocation for inode %lu\n", inode->i_ino);
Theodore Ts'o9bffad12009-06-17 11:48:11 -04003996 trace_ext4_discard_preallocations(inode);
Alex Tomasc9de5602008-01-29 00:19:52 -05003997
3998 INIT_LIST_HEAD(&list);
3999
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04004000 ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
Theodore Ts'o9bffad12009-06-17 11:48:11 -04004001 if (ac) {
4002 ac->ac_sb = sb;
4003 ac->ac_inode = inode;
4004 }
Alex Tomasc9de5602008-01-29 00:19:52 -05004005repeat:
4006 /* first, collect all pa's in the inode */
4007 spin_lock(&ei->i_prealloc_lock);
4008 while (!list_empty(&ei->i_prealloc_list)) {
4009 pa = list_entry(ei->i_prealloc_list.next,
4010 struct ext4_prealloc_space, pa_inode_list);
4011 BUG_ON(pa->pa_obj_lock != &ei->i_prealloc_lock);
4012 spin_lock(&pa->pa_lock);
4013 if (atomic_read(&pa->pa_count)) {
4014 /* this shouldn't happen often - nobody should
4015 * use preallocation while we're discarding it */
4016 spin_unlock(&pa->pa_lock);
4017 spin_unlock(&ei->i_prealloc_lock);
4018 printk(KERN_ERR "uh-oh! used pa while discarding\n");
4019 WARN_ON(1);
4020 schedule_timeout_uninterruptible(HZ);
4021 goto repeat;
4022
4023 }
4024 if (pa->pa_deleted == 0) {
4025 pa->pa_deleted = 1;
4026 spin_unlock(&pa->pa_lock);
4027 list_del_rcu(&pa->pa_inode_list);
4028 list_add(&pa->u.pa_tmp_list, &list);
4029 continue;
4030 }
4031
4032 /* someone is deleting pa right now */
4033 spin_unlock(&pa->pa_lock);
4034 spin_unlock(&ei->i_prealloc_lock);
4035
4036 /* we have to wait here because pa_deleted
4037 * doesn't mean pa is already unlinked from
4038 * the list. as we might be called from
4039 * ->clear_inode() the inode will get freed
4040 * and concurrent thread which is unlinking
4041 * pa from inode's list may access already
4042 * freed memory, bad-bad-bad */
4043
4044 /* XXX: if this happens too often, we can
4045 * add a flag to force wait only in case
4046 * of ->clear_inode(), but not in case of
4047 * regular truncate */
4048 schedule_timeout_uninterruptible(HZ);
4049 goto repeat;
4050 }
4051 spin_unlock(&ei->i_prealloc_lock);
4052
4053 list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {
Aneesh Kumar K.Vcc0fb9a2009-03-27 17:16:58 -04004054 BUG_ON(pa->pa_type != MB_INODE_PA);
Alex Tomasc9de5602008-01-29 00:19:52 -05004055 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, NULL);
4056
4057 err = ext4_mb_load_buddy(sb, group, &e4b);
Aneesh Kumar K.Vce89f462008-07-23 14:09:29 -04004058 if (err) {
4059 ext4_error(sb, __func__, "Error in loading buddy "
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05004060 "information for %u", group);
Aneesh Kumar K.Vce89f462008-07-23 14:09:29 -04004061 continue;
4062 }
Alex Tomasc9de5602008-01-29 00:19:52 -05004063
Theodore Ts'o574ca172008-07-11 19:27:31 -04004064 bitmap_bh = ext4_read_block_bitmap(sb, group);
Alex Tomasc9de5602008-01-29 00:19:52 -05004065 if (bitmap_bh == NULL) {
Aneesh Kumar K.Vce89f462008-07-23 14:09:29 -04004066 ext4_error(sb, __func__, "Error in reading block "
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05004067 "bitmap for %u", group);
Alex Tomasc9de5602008-01-29 00:19:52 -05004068 ext4_mb_release_desc(&e4b);
Aneesh Kumar K.Vce89f462008-07-23 14:09:29 -04004069 continue;
Alex Tomasc9de5602008-01-29 00:19:52 -05004070 }
4071
4072 ext4_lock_group(sb, group);
4073 list_del(&pa->pa_group_list);
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04004074 ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa, ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05004075 ext4_unlock_group(sb, group);
4076
4077 ext4_mb_release_desc(&e4b);
4078 put_bh(bitmap_bh);
4079
4080 list_del(&pa->u.pa_tmp_list);
4081 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
4082 }
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04004083 if (ac)
4084 kmem_cache_free(ext4_ac_cachep, ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05004085}
4086
4087/*
4088 * finds all preallocated spaces and return blocks being freed to them
4089 * if preallocated space becomes full (no block is used from the space)
4090 * then the function frees space in buddy
4091 * XXX: at the moment, truncate (which is the only way to free blocks)
4092 * discards all preallocations
4093 */
4094static void ext4_mb_return_to_preallocation(struct inode *inode,
4095 struct ext4_buddy *e4b,
4096 sector_t block, int count)
4097{
4098 BUG_ON(!list_empty(&EXT4_I(inode)->i_prealloc_list));
4099}
4100#ifdef MB_DEBUG
4101static void ext4_mb_show_ac(struct ext4_allocation_context *ac)
4102{
4103 struct super_block *sb = ac->ac_sb;
Theodore Ts'o8df96752009-05-01 08:50:38 -04004104 ext4_group_t ngroups, i;
Alex Tomasc9de5602008-01-29 00:19:52 -05004105
4106 printk(KERN_ERR "EXT4-fs: Can't allocate:"
4107 " Allocation context details:\n");
4108 printk(KERN_ERR "EXT4-fs: status %d flags %d\n",
4109 ac->ac_status, ac->ac_flags);
4110 printk(KERN_ERR "EXT4-fs: orig %lu/%lu/%lu@%lu, goal %lu/%lu/%lu@%lu, "
4111 "best %lu/%lu/%lu@%lu cr %d\n",
4112 (unsigned long)ac->ac_o_ex.fe_group,
4113 (unsigned long)ac->ac_o_ex.fe_start,
4114 (unsigned long)ac->ac_o_ex.fe_len,
4115 (unsigned long)ac->ac_o_ex.fe_logical,
4116 (unsigned long)ac->ac_g_ex.fe_group,
4117 (unsigned long)ac->ac_g_ex.fe_start,
4118 (unsigned long)ac->ac_g_ex.fe_len,
4119 (unsigned long)ac->ac_g_ex.fe_logical,
4120 (unsigned long)ac->ac_b_ex.fe_group,
4121 (unsigned long)ac->ac_b_ex.fe_start,
4122 (unsigned long)ac->ac_b_ex.fe_len,
4123 (unsigned long)ac->ac_b_ex.fe_logical,
4124 (int)ac->ac_criteria);
4125 printk(KERN_ERR "EXT4-fs: %lu scanned, %d found\n", ac->ac_ex_scanned,
4126 ac->ac_found);
4127 printk(KERN_ERR "EXT4-fs: groups: \n");
Theodore Ts'o8df96752009-05-01 08:50:38 -04004128 ngroups = ext4_get_groups_count(sb);
4129 for (i = 0; i < ngroups; i++) {
Alex Tomasc9de5602008-01-29 00:19:52 -05004130 struct ext4_group_info *grp = ext4_get_group_info(sb, i);
4131 struct ext4_prealloc_space *pa;
4132 ext4_grpblk_t start;
4133 struct list_head *cur;
4134 ext4_lock_group(sb, i);
4135 list_for_each(cur, &grp->bb_prealloc_list) {
4136 pa = list_entry(cur, struct ext4_prealloc_space,
4137 pa_group_list);
4138 spin_lock(&pa->pa_lock);
4139 ext4_get_group_no_and_offset(sb, pa->pa_pstart,
4140 NULL, &start);
4141 spin_unlock(&pa->pa_lock);
4142 printk(KERN_ERR "PA:%lu:%d:%u \n", i,
4143 start, pa->pa_len);
4144 }
Solofo Ramangalahy60bd63d2008-04-29 21:59:59 -04004145 ext4_unlock_group(sb, i);
Alex Tomasc9de5602008-01-29 00:19:52 -05004146
4147 if (grp->bb_free == 0)
4148 continue;
4149 printk(KERN_ERR "%lu: %d/%d \n",
4150 i, grp->bb_free, grp->bb_fragments);
4151 }
4152 printk(KERN_ERR "\n");
4153}
4154#else
4155static inline void ext4_mb_show_ac(struct ext4_allocation_context *ac)
4156{
4157 return;
4158}
4159#endif
4160
4161/*
4162 * We use locality group preallocation for small size file. The size of the
4163 * file is determined by the current size or the resulting size after
4164 * allocation which ever is larger
4165 *
Theodore Ts'ob713a5e2009-03-31 09:11:14 -04004166 * One can tune this size via /sys/fs/ext4/<partition>/mb_stream_req
Alex Tomasc9de5602008-01-29 00:19:52 -05004167 */
4168static void ext4_mb_group_or_file(struct ext4_allocation_context *ac)
4169{
4170 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
4171 int bsbits = ac->ac_sb->s_blocksize_bits;
4172 loff_t size, isize;
4173
4174 if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
4175 return;
4176
4177 size = ac->ac_o_ex.fe_logical + ac->ac_o_ex.fe_len;
4178 isize = i_size_read(ac->ac_inode) >> bsbits;
4179 size = max(size, isize);
4180
4181 /* don't use group allocation for large files */
4182 if (size >= sbi->s_mb_stream_request)
4183 return;
4184
4185 if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
4186 return;
4187
4188 BUG_ON(ac->ac_lg != NULL);
4189 /*
4190 * locality group prealloc space are per cpu. The reason for having
4191 * per cpu locality group is to reduce the contention between block
4192 * request from multiple CPUs.
4193 */
Eric Sandeen730c2132008-09-13 15:23:29 -04004194 ac->ac_lg = per_cpu_ptr(sbi->s_locality_groups, raw_smp_processor_id());
Alex Tomasc9de5602008-01-29 00:19:52 -05004195
4196 /* we're going to use group allocation */
4197 ac->ac_flags |= EXT4_MB_HINT_GROUP_ALLOC;
4198
4199 /* serialize all allocations in the group */
4200 mutex_lock(&ac->ac_lg->lg_mutex);
4201}
4202
Eric Sandeen4ddfef72008-04-29 08:11:12 -04004203static noinline_for_stack int
4204ext4_mb_initialize_context(struct ext4_allocation_context *ac,
Alex Tomasc9de5602008-01-29 00:19:52 -05004205 struct ext4_allocation_request *ar)
4206{
4207 struct super_block *sb = ar->inode->i_sb;
4208 struct ext4_sb_info *sbi = EXT4_SB(sb);
4209 struct ext4_super_block *es = sbi->s_es;
4210 ext4_group_t group;
Theodore Ts'o498e5f22008-11-05 00:14:04 -05004211 unsigned int len;
4212 ext4_fsblk_t goal;
Alex Tomasc9de5602008-01-29 00:19:52 -05004213 ext4_grpblk_t block;
4214
4215 /* we can't allocate > group size */
4216 len = ar->len;
4217
4218 /* just a dirty hack to filter too big requests */
4219 if (len >= EXT4_BLOCKS_PER_GROUP(sb) - 10)
4220 len = EXT4_BLOCKS_PER_GROUP(sb) - 10;
4221
4222 /* start searching from the goal */
4223 goal = ar->goal;
4224 if (goal < le32_to_cpu(es->s_first_data_block) ||
4225 goal >= ext4_blocks_count(es))
4226 goal = le32_to_cpu(es->s_first_data_block);
4227 ext4_get_group_no_and_offset(sb, goal, &group, &block);
4228
4229 /* set up allocation goals */
Theodore Ts'o833576b2009-07-13 09:45:52 -04004230 memset(ac, 0, sizeof(struct ext4_allocation_context));
Alex Tomasc9de5602008-01-29 00:19:52 -05004231 ac->ac_b_ex.fe_logical = ar->logical;
Alex Tomasc9de5602008-01-29 00:19:52 -05004232 ac->ac_status = AC_STATUS_CONTINUE;
Alex Tomasc9de5602008-01-29 00:19:52 -05004233 ac->ac_sb = sb;
4234 ac->ac_inode = ar->inode;
4235 ac->ac_o_ex.fe_logical = ar->logical;
4236 ac->ac_o_ex.fe_group = group;
4237 ac->ac_o_ex.fe_start = block;
4238 ac->ac_o_ex.fe_len = len;
4239 ac->ac_g_ex.fe_logical = ar->logical;
4240 ac->ac_g_ex.fe_group = group;
4241 ac->ac_g_ex.fe_start = block;
4242 ac->ac_g_ex.fe_len = len;
Alex Tomasc9de5602008-01-29 00:19:52 -05004243 ac->ac_flags = ar->flags;
Alex Tomasc9de5602008-01-29 00:19:52 -05004244
4245 /* we have to define context: we'll we work with a file or
4246 * locality group. this is a policy, actually */
4247 ext4_mb_group_or_file(ac);
4248
4249 mb_debug("init ac: %u blocks @ %u, goal %u, flags %x, 2^%d, "
4250 "left: %u/%u, right %u/%u to %swritable\n",
4251 (unsigned) ar->len, (unsigned) ar->logical,
4252 (unsigned) ar->goal, ac->ac_flags, ac->ac_2order,
4253 (unsigned) ar->lleft, (unsigned) ar->pleft,
4254 (unsigned) ar->lright, (unsigned) ar->pright,
4255 atomic_read(&ar->inode->i_writecount) ? "" : "non-");
4256 return 0;
4257
4258}
4259
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04004260static noinline_for_stack void
4261ext4_mb_discard_lg_preallocations(struct super_block *sb,
4262 struct ext4_locality_group *lg,
4263 int order, int total_entries)
4264{
4265 ext4_group_t group = 0;
4266 struct ext4_buddy e4b;
4267 struct list_head discard_list;
4268 struct ext4_prealloc_space *pa, *tmp;
4269 struct ext4_allocation_context *ac;
4270
4271 mb_debug("discard locality group preallocation\n");
4272
4273 INIT_LIST_HEAD(&discard_list);
4274 ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
Theodore Ts'o9bffad12009-06-17 11:48:11 -04004275 if (ac)
4276 ac->ac_sb = sb;
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04004277
4278 spin_lock(&lg->lg_prealloc_lock);
4279 list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[order],
4280 pa_inode_list) {
4281 spin_lock(&pa->pa_lock);
4282 if (atomic_read(&pa->pa_count)) {
4283 /*
4284 * This is the pa that we just used
4285 * for block allocation. So don't
4286 * free that
4287 */
4288 spin_unlock(&pa->pa_lock);
4289 continue;
4290 }
4291 if (pa->pa_deleted) {
4292 spin_unlock(&pa->pa_lock);
4293 continue;
4294 }
4295 /* only lg prealloc space */
Aneesh Kumar K.Vcc0fb9a2009-03-27 17:16:58 -04004296 BUG_ON(pa->pa_type != MB_GROUP_PA);
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04004297
4298 /* seems this one can be freed ... */
4299 pa->pa_deleted = 1;
4300 spin_unlock(&pa->pa_lock);
4301
4302 list_del_rcu(&pa->pa_inode_list);
4303 list_add(&pa->u.pa_tmp_list, &discard_list);
4304
4305 total_entries--;
4306 if (total_entries <= 5) {
4307 /*
4308 * we want to keep only 5 entries
4309 * allowing it to grow to 8. This
4310 * mak sure we don't call discard
4311 * soon for this list.
4312 */
4313 break;
4314 }
4315 }
4316 spin_unlock(&lg->lg_prealloc_lock);
4317
4318 list_for_each_entry_safe(pa, tmp, &discard_list, u.pa_tmp_list) {
4319
4320 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, NULL);
4321 if (ext4_mb_load_buddy(sb, group, &e4b)) {
4322 ext4_error(sb, __func__, "Error in loading buddy "
Theodore Ts'oa9df9a42009-01-05 22:18:16 -05004323 "information for %u", group);
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04004324 continue;
4325 }
4326 ext4_lock_group(sb, group);
4327 list_del(&pa->pa_group_list);
4328 ext4_mb_release_group_pa(&e4b, pa, ac);
4329 ext4_unlock_group(sb, group);
4330
4331 ext4_mb_release_desc(&e4b);
4332 list_del(&pa->u.pa_tmp_list);
4333 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
4334 }
4335 if (ac)
4336 kmem_cache_free(ext4_ac_cachep, ac);
4337}
4338
4339/*
4340 * We have incremented pa_count. So it cannot be freed at this
4341 * point. Also we hold lg_mutex. So no parallel allocation is
4342 * possible from this lg. That means pa_free cannot be updated.
4343 *
4344 * A parallel ext4_mb_discard_group_preallocations is possible.
4345 * which can cause the lg_prealloc_list to be updated.
4346 */
4347
4348static void ext4_mb_add_n_trim(struct ext4_allocation_context *ac)
4349{
4350 int order, added = 0, lg_prealloc_count = 1;
4351 struct super_block *sb = ac->ac_sb;
4352 struct ext4_locality_group *lg = ac->ac_lg;
4353 struct ext4_prealloc_space *tmp_pa, *pa = ac->ac_pa;
4354
4355 order = fls(pa->pa_free) - 1;
4356 if (order > PREALLOC_TB_SIZE - 1)
4357 /* The max size of hash table is PREALLOC_TB_SIZE */
4358 order = PREALLOC_TB_SIZE - 1;
4359 /* Add the prealloc space to lg */
4360 rcu_read_lock();
4361 list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[order],
4362 pa_inode_list) {
4363 spin_lock(&tmp_pa->pa_lock);
4364 if (tmp_pa->pa_deleted) {
Theodore Ts'oe7c9e3e2009-03-27 19:43:21 -04004365 spin_unlock(&tmp_pa->pa_lock);
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04004366 continue;
4367 }
4368 if (!added && pa->pa_free < tmp_pa->pa_free) {
4369 /* Add to the tail of the previous entry */
4370 list_add_tail_rcu(&pa->pa_inode_list,
4371 &tmp_pa->pa_inode_list);
4372 added = 1;
4373 /*
4374 * we want to count the total
4375 * number of entries in the list
4376 */
4377 }
4378 spin_unlock(&tmp_pa->pa_lock);
4379 lg_prealloc_count++;
4380 }
4381 if (!added)
4382 list_add_tail_rcu(&pa->pa_inode_list,
4383 &lg->lg_prealloc_list[order]);
4384 rcu_read_unlock();
4385
4386 /* Now trim the list to be not more than 8 elements */
4387 if (lg_prealloc_count > 8) {
4388 ext4_mb_discard_lg_preallocations(sb, lg,
4389 order, lg_prealloc_count);
4390 return;
4391 }
4392 return ;
4393}
4394
Alex Tomasc9de5602008-01-29 00:19:52 -05004395/*
4396 * release all resource we used in allocation
4397 */
4398static int ext4_mb_release_context(struct ext4_allocation_context *ac)
4399{
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04004400 struct ext4_prealloc_space *pa = ac->ac_pa;
4401 if (pa) {
Aneesh Kumar K.Vcc0fb9a2009-03-27 17:16:58 -04004402 if (pa->pa_type == MB_GROUP_PA) {
Alex Tomasc9de5602008-01-29 00:19:52 -05004403 /* see comment in ext4_mb_use_group_pa() */
Aneesh Kumar K.V6be2ded2008-07-23 14:14:05 -04004404 spin_lock(&pa->pa_lock);
4405 pa->pa_pstart += ac->ac_b_ex.fe_len;
4406 pa->pa_lstart += ac->ac_b_ex.fe_len;
4407 pa->pa_free -= ac->ac_b_ex.fe_len;
4408 pa->pa_len -= ac->ac_b_ex.fe_len;
4409 spin_unlock(&pa->pa_lock);
Alex Tomasc9de5602008-01-29 00:19:52 -05004410 }
Alex Tomasc9de5602008-01-29 00:19:52 -05004411 }
Aneesh Kumar K.V8556e8f2009-01-05 21:46:55 -05004412 if (ac->alloc_semp)
4413 up_read(ac->alloc_semp);
Aneesh Kumar K.Vba443912009-02-10 11:14:34 -05004414 if (pa) {
4415 /*
4416 * We want to add the pa to the right bucket.
4417 * Remove it from the list and while adding
4418 * make sure the list to which we are adding
4419 * doesn't grow big. We need to release
4420 * alloc_semp before calling ext4_mb_add_n_trim()
4421 */
Aneesh Kumar K.Vcc0fb9a2009-03-27 17:16:58 -04004422 if ((pa->pa_type == MB_GROUP_PA) && likely(pa->pa_free)) {
Aneesh Kumar K.Vba443912009-02-10 11:14:34 -05004423 spin_lock(pa->pa_obj_lock);
4424 list_del_rcu(&pa->pa_inode_list);
4425 spin_unlock(pa->pa_obj_lock);
4426 ext4_mb_add_n_trim(ac);
4427 }
4428 ext4_mb_put_pa(ac, ac->ac_sb, pa);
4429 }
Alex Tomasc9de5602008-01-29 00:19:52 -05004430 if (ac->ac_bitmap_page)
4431 page_cache_release(ac->ac_bitmap_page);
4432 if (ac->ac_buddy_page)
4433 page_cache_release(ac->ac_buddy_page);
4434 if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
4435 mutex_unlock(&ac->ac_lg->lg_mutex);
4436 ext4_mb_collect_stats(ac);
4437 return 0;
4438}
4439
4440static int ext4_mb_discard_preallocations(struct super_block *sb, int needed)
4441{
Theodore Ts'o8df96752009-05-01 08:50:38 -04004442 ext4_group_t i, ngroups = ext4_get_groups_count(sb);
Alex Tomasc9de5602008-01-29 00:19:52 -05004443 int ret;
4444 int freed = 0;
4445
Theodore Ts'o9bffad12009-06-17 11:48:11 -04004446 trace_ext4_mb_discard_preallocations(sb, needed);
Theodore Ts'o8df96752009-05-01 08:50:38 -04004447 for (i = 0; i < ngroups && needed > 0; i++) {
Alex Tomasc9de5602008-01-29 00:19:52 -05004448 ret = ext4_mb_discard_group_preallocations(sb, i, needed);
4449 freed += ret;
4450 needed -= ret;
4451 }
4452
4453 return freed;
4454}
4455
4456/*
4457 * Main entry point into mballoc to allocate blocks
4458 * it tries to use preallocation first, then falls back
4459 * to usual allocation
4460 */
4461ext4_fsblk_t ext4_mb_new_blocks(handle_t *handle,
4462 struct ext4_allocation_request *ar, int *errp)
4463{
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04004464 int freed;
Eric Sandeen256bdb42008-02-10 01:13:33 -05004465 struct ext4_allocation_context *ac = NULL;
Alex Tomasc9de5602008-01-29 00:19:52 -05004466 struct ext4_sb_info *sbi;
4467 struct super_block *sb;
4468 ext4_fsblk_t block = 0;
Mingming Cao60e58e02009-01-22 18:13:05 +01004469 unsigned int inquota = 0;
Theodore Ts'o498e5f22008-11-05 00:14:04 -05004470 unsigned int reserv_blks = 0;
Alex Tomasc9de5602008-01-29 00:19:52 -05004471
4472 sb = ar->inode->i_sb;
4473 sbi = EXT4_SB(sb);
4474
Theodore Ts'o9bffad12009-06-17 11:48:11 -04004475 trace_ext4_request_blocks(ar);
Theodore Ts'oba80b102009-01-03 20:03:21 -05004476
Mingming Cao60e58e02009-01-22 18:13:05 +01004477 /*
4478 * For delayed allocation, we could skip the ENOSPC and
4479 * EDQUOT check, as blocks and quotas have been already
4480 * reserved when data being copied into pagecache.
4481 */
4482 if (EXT4_I(ar->inode)->i_delalloc_reserved_flag)
4483 ar->flags |= EXT4_MB_DELALLOC_RESERVED;
4484 else {
4485 /* Without delayed allocation we need to verify
4486 * there is enough free blocks to do block allocation
4487 * and verify allocation doesn't exceed the quota limits.
Mingming Caod2a17632008-07-14 17:52:37 -04004488 */
Aneesh Kumar K.V030ba6b2008-09-08 23:14:50 -04004489 while (ar->len && ext4_claim_free_blocks(sbi, ar->len)) {
4490 /* let others to free the space */
4491 yield();
4492 ar->len = ar->len >> 1;
4493 }
4494 if (!ar->len) {
Aneesh Kumar K.Va30d542a2008-10-09 10:56:23 -04004495 *errp = -ENOSPC;
4496 return 0;
4497 }
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04004498 reserv_blks = ar->len;
Jan Karaa269eb12009-01-26 17:04:39 +01004499 while (ar->len && vfs_dq_alloc_block(ar->inode, ar->len)) {
Mingming Cao60e58e02009-01-22 18:13:05 +01004500 ar->flags |= EXT4_MB_HINT_NOPREALLOC;
4501 ar->len--;
4502 }
4503 inquota = ar->len;
4504 if (ar->len == 0) {
4505 *errp = -EDQUOT;
4506 goto out3;
4507 }
Mingming Caod2a17632008-07-14 17:52:37 -04004508 }
Mingming Caod2a17632008-07-14 17:52:37 -04004509
Eric Sandeen256bdb42008-02-10 01:13:33 -05004510 ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
Theodore Ts'o833576b2009-07-13 09:45:52 -04004511 if (!ac) {
Shen Feng363d4252008-07-11 19:27:31 -04004512 ar->len = 0;
Eric Sandeen256bdb42008-02-10 01:13:33 -05004513 *errp = -ENOMEM;
Shen Feng363d4252008-07-11 19:27:31 -04004514 goto out1;
Eric Sandeen256bdb42008-02-10 01:13:33 -05004515 }
4516
Eric Sandeen256bdb42008-02-10 01:13:33 -05004517 *errp = ext4_mb_initialize_context(ac, ar);
Alex Tomasc9de5602008-01-29 00:19:52 -05004518 if (*errp) {
4519 ar->len = 0;
Shen Feng363d4252008-07-11 19:27:31 -04004520 goto out2;
Alex Tomasc9de5602008-01-29 00:19:52 -05004521 }
4522
Eric Sandeen256bdb42008-02-10 01:13:33 -05004523 ac->ac_op = EXT4_MB_HISTORY_PREALLOC;
4524 if (!ext4_mb_use_preallocated(ac)) {
Eric Sandeen256bdb42008-02-10 01:13:33 -05004525 ac->ac_op = EXT4_MB_HISTORY_ALLOC;
4526 ext4_mb_normalize_request(ac, ar);
Alex Tomasc9de5602008-01-29 00:19:52 -05004527repeat:
4528 /* allocate space in core */
Eric Sandeen256bdb42008-02-10 01:13:33 -05004529 ext4_mb_regular_allocator(ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05004530
4531 /* as we've just preallocated more space than
4532 * user requested orinally, we store allocated
4533 * space in a special descriptor */
Eric Sandeen256bdb42008-02-10 01:13:33 -05004534 if (ac->ac_status == AC_STATUS_FOUND &&
4535 ac->ac_o_ex.fe_len < ac->ac_b_ex.fe_len)
4536 ext4_mb_new_preallocation(ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05004537 }
Eric Sandeen256bdb42008-02-10 01:13:33 -05004538 if (likely(ac->ac_status == AC_STATUS_FOUND)) {
Aneesh Kumar K.V6bc6e632008-10-10 09:39:00 -04004539 *errp = ext4_mb_mark_diskspace_used(ac, handle, reserv_blks);
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -04004540 if (*errp == -EAGAIN) {
Aneesh Kumar K.V8556e8f2009-01-05 21:46:55 -05004541 /*
4542 * drop the reference that we took
4543 * in ext4_mb_use_best_found
4544 */
4545 ext4_mb_release_context(ac);
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -04004546 ac->ac_b_ex.fe_group = 0;
4547 ac->ac_b_ex.fe_start = 0;
4548 ac->ac_b_ex.fe_len = 0;
4549 ac->ac_status = AC_STATUS_CONTINUE;
4550 goto repeat;
4551 } else if (*errp) {
4552 ac->ac_b_ex.fe_len = 0;
4553 ar->len = 0;
4554 ext4_mb_show_ac(ac);
4555 } else {
4556 block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
4557 ar->len = ac->ac_b_ex.fe_len;
4558 }
Alex Tomasc9de5602008-01-29 00:19:52 -05004559 } else {
Eric Sandeen256bdb42008-02-10 01:13:33 -05004560 freed = ext4_mb_discard_preallocations(sb, ac->ac_o_ex.fe_len);
Alex Tomasc9de5602008-01-29 00:19:52 -05004561 if (freed)
4562 goto repeat;
4563 *errp = -ENOSPC;
Eric Sandeen256bdb42008-02-10 01:13:33 -05004564 ac->ac_b_ex.fe_len = 0;
Alex Tomasc9de5602008-01-29 00:19:52 -05004565 ar->len = 0;
Eric Sandeen256bdb42008-02-10 01:13:33 -05004566 ext4_mb_show_ac(ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05004567 }
4568
Eric Sandeen256bdb42008-02-10 01:13:33 -05004569 ext4_mb_release_context(ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05004570
Shen Feng363d4252008-07-11 19:27:31 -04004571out2:
4572 kmem_cache_free(ext4_ac_cachep, ac);
4573out1:
Mingming Cao60e58e02009-01-22 18:13:05 +01004574 if (inquota && ar->len < inquota)
Jan Karaa269eb12009-01-26 17:04:39 +01004575 vfs_dq_free_block(ar->inode, inquota - ar->len);
Aneesh Kumar K.V0087d9f2009-01-05 21:49:12 -05004576out3:
4577 if (!ar->len) {
4578 if (!EXT4_I(ar->inode)->i_delalloc_reserved_flag)
4579 /* release all the reserved blocks if non delalloc */
4580 percpu_counter_sub(&sbi->s_dirtyblocks_counter,
4581 reserv_blks);
4582 }
Alex Tomasc9de5602008-01-29 00:19:52 -05004583
Theodore Ts'o9bffad12009-06-17 11:48:11 -04004584 trace_ext4_allocate_blocks(ar, (unsigned long long)block);
Theodore Ts'oba80b102009-01-03 20:03:21 -05004585
Alex Tomasc9de5602008-01-29 00:19:52 -05004586 return block;
4587}
Alex Tomasc9de5602008-01-29 00:19:52 -05004588
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04004589/*
4590 * We can merge two free data extents only if the physical blocks
4591 * are contiguous, AND the extents were freed by the same transaction,
4592 * AND the blocks are associated with the same group.
4593 */
4594static int can_merge(struct ext4_free_data *entry1,
4595 struct ext4_free_data *entry2)
4596{
4597 if ((entry1->t_tid == entry2->t_tid) &&
4598 (entry1->group == entry2->group) &&
4599 ((entry1->start_blk + entry1->count) == entry2->start_blk))
4600 return 1;
4601 return 0;
4602}
4603
Eric Sandeen4ddfef72008-04-29 08:11:12 -04004604static noinline_for_stack int
4605ext4_mb_free_metadata(handle_t *handle, struct ext4_buddy *e4b,
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -05004606 struct ext4_free_data *new_entry)
Alex Tomasc9de5602008-01-29 00:19:52 -05004607{
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -05004608 ext4_grpblk_t block;
4609 struct ext4_free_data *entry;
Alex Tomasc9de5602008-01-29 00:19:52 -05004610 struct ext4_group_info *db = e4b->bd_info;
4611 struct super_block *sb = e4b->bd_sb;
4612 struct ext4_sb_info *sbi = EXT4_SB(sb);
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04004613 struct rb_node **n = &db->bb_free_root.rb_node, *node;
4614 struct rb_node *parent = NULL, *new_node;
4615
Frank Mayhar03901312009-01-07 00:06:22 -05004616 BUG_ON(!ext4_handle_valid(handle));
Alex Tomasc9de5602008-01-29 00:19:52 -05004617 BUG_ON(e4b->bd_bitmap_page == NULL);
4618 BUG_ON(e4b->bd_buddy_page == NULL);
4619
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04004620 new_node = &new_entry->node;
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -05004621 block = new_entry->start_blk;
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04004622
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04004623 if (!*n) {
4624 /* first free block exent. We need to
4625 protect buddy cache from being freed,
4626 * otherwise we'll refresh it from
4627 * on-disk bitmap and lose not-yet-available
4628 * blocks */
4629 page_cache_get(e4b->bd_buddy_page);
4630 page_cache_get(e4b->bd_bitmap_page);
4631 }
4632 while (*n) {
4633 parent = *n;
4634 entry = rb_entry(parent, struct ext4_free_data, node);
4635 if (block < entry->start_blk)
4636 n = &(*n)->rb_left;
4637 else if (block >= (entry->start_blk + entry->count))
4638 n = &(*n)->rb_right;
4639 else {
Aneesh Kumar K.V5d1b1b32009-01-05 22:19:52 -05004640 ext4_grp_locked_error(sb, e4b->bd_group, __func__,
4641 "Double free of blocks %d (%d %d)",
4642 block, entry->start_blk, entry->count);
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04004643 return 0;
Alex Tomasc9de5602008-01-29 00:19:52 -05004644 }
4645 }
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04004646
4647 rb_link_node(new_node, parent, n);
4648 rb_insert_color(new_node, &db->bb_free_root);
4649
4650 /* Now try to see the extent can be merged to left and right */
4651 node = rb_prev(new_node);
4652 if (node) {
4653 entry = rb_entry(node, struct ext4_free_data, node);
4654 if (can_merge(entry, new_entry)) {
4655 new_entry->start_blk = entry->start_blk;
4656 new_entry->count += entry->count;
4657 rb_erase(node, &(db->bb_free_root));
4658 spin_lock(&sbi->s_md_lock);
4659 list_del(&entry->list);
4660 spin_unlock(&sbi->s_md_lock);
4661 kmem_cache_free(ext4_free_ext_cachep, entry);
4662 }
4663 }
4664
4665 node = rb_next(new_node);
4666 if (node) {
4667 entry = rb_entry(node, struct ext4_free_data, node);
4668 if (can_merge(new_entry, entry)) {
4669 new_entry->count += entry->count;
4670 rb_erase(node, &(db->bb_free_root));
4671 spin_lock(&sbi->s_md_lock);
4672 list_del(&entry->list);
4673 spin_unlock(&sbi->s_md_lock);
4674 kmem_cache_free(ext4_free_ext_cachep, entry);
4675 }
4676 }
Theodore Ts'o3e624fc2008-10-16 20:00:24 -04004677 /* Add the extent to transaction's private list */
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04004678 spin_lock(&sbi->s_md_lock);
Theodore Ts'o3e624fc2008-10-16 20:00:24 -04004679 list_add(&new_entry->list, &handle->h_transaction->t_private_list);
Aneesh Kumar K.Vc8940582008-10-16 10:14:27 -04004680 spin_unlock(&sbi->s_md_lock);
Alex Tomasc9de5602008-01-29 00:19:52 -05004681 return 0;
4682}
4683
4684/*
4685 * Main entry point into mballoc to free blocks
4686 */
4687void ext4_mb_free_blocks(handle_t *handle, struct inode *inode,
Theodore Ts'o0610b6e2009-06-15 03:45:05 -04004688 ext4_fsblk_t block, unsigned long count,
Alex Tomasc9de5602008-01-29 00:19:52 -05004689 int metadata, unsigned long *freed)
4690{
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05004691 struct buffer_head *bitmap_bh = NULL;
Alex Tomasc9de5602008-01-29 00:19:52 -05004692 struct super_block *sb = inode->i_sb;
Eric Sandeen256bdb42008-02-10 01:13:33 -05004693 struct ext4_allocation_context *ac = NULL;
Alex Tomasc9de5602008-01-29 00:19:52 -05004694 struct ext4_group_desc *gdp;
4695 struct ext4_super_block *es;
Theodore Ts'o498e5f22008-11-05 00:14:04 -05004696 unsigned int overflow;
Alex Tomasc9de5602008-01-29 00:19:52 -05004697 ext4_grpblk_t bit;
4698 struct buffer_head *gd_bh;
4699 ext4_group_t block_group;
4700 struct ext4_sb_info *sbi;
4701 struct ext4_buddy e4b;
4702 int err = 0;
4703 int ret;
4704
4705 *freed = 0;
4706
Alex Tomasc9de5602008-01-29 00:19:52 -05004707 sbi = EXT4_SB(sb);
4708 es = EXT4_SB(sb)->s_es;
4709 if (block < le32_to_cpu(es->s_first_data_block) ||
4710 block + count < block ||
4711 block + count > ext4_blocks_count(es)) {
Harvey Harrison46e665e2008-04-17 10:38:59 -04004712 ext4_error(sb, __func__,
Alex Tomasc9de5602008-01-29 00:19:52 -05004713 "Freeing blocks not in datazone - "
Theodore Ts'o0610b6e2009-06-15 03:45:05 -04004714 "block = %llu, count = %lu", block, count);
Alex Tomasc9de5602008-01-29 00:19:52 -05004715 goto error_return;
4716 }
4717
Theodore Ts'o0610b6e2009-06-15 03:45:05 -04004718 ext4_debug("freeing block %llu\n", block);
Theodore Ts'o9bffad12009-06-17 11:48:11 -04004719 trace_ext4_free_blocks(inode, block, count, metadata);
Alex Tomasc9de5602008-01-29 00:19:52 -05004720
Eric Sandeen256bdb42008-02-10 01:13:33 -05004721 ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
4722 if (ac) {
4723 ac->ac_op = EXT4_MB_HISTORY_FREE;
4724 ac->ac_inode = inode;
4725 ac->ac_sb = sb;
4726 }
Alex Tomasc9de5602008-01-29 00:19:52 -05004727
4728do_more:
4729 overflow = 0;
4730 ext4_get_group_no_and_offset(sb, block, &block_group, &bit);
4731
4732 /*
4733 * Check to see if we are freeing blocks across a group
4734 * boundary.
4735 */
4736 if (bit + count > EXT4_BLOCKS_PER_GROUP(sb)) {
4737 overflow = bit + count - EXT4_BLOCKS_PER_GROUP(sb);
4738 count -= overflow;
4739 }
Theodore Ts'o574ca172008-07-11 19:27:31 -04004740 bitmap_bh = ext4_read_block_bitmap(sb, block_group);
Aneesh Kumar K.Vce89f462008-07-23 14:09:29 -04004741 if (!bitmap_bh) {
4742 err = -EIO;
Alex Tomasc9de5602008-01-29 00:19:52 -05004743 goto error_return;
Aneesh Kumar K.Vce89f462008-07-23 14:09:29 -04004744 }
Alex Tomasc9de5602008-01-29 00:19:52 -05004745 gdp = ext4_get_group_desc(sb, block_group, &gd_bh);
Aneesh Kumar K.Vce89f462008-07-23 14:09:29 -04004746 if (!gdp) {
4747 err = -EIO;
Alex Tomasc9de5602008-01-29 00:19:52 -05004748 goto error_return;
Aneesh Kumar K.Vce89f462008-07-23 14:09:29 -04004749 }
Alex Tomasc9de5602008-01-29 00:19:52 -05004750
4751 if (in_range(ext4_block_bitmap(sb, gdp), block, count) ||
4752 in_range(ext4_inode_bitmap(sb, gdp), block, count) ||
4753 in_range(block, ext4_inode_table(sb, gdp),
4754 EXT4_SB(sb)->s_itb_per_group) ||
4755 in_range(block + count - 1, ext4_inode_table(sb, gdp),
4756 EXT4_SB(sb)->s_itb_per_group)) {
4757
Harvey Harrison46e665e2008-04-17 10:38:59 -04004758 ext4_error(sb, __func__,
Alex Tomasc9de5602008-01-29 00:19:52 -05004759 "Freeing blocks in system zone - "
Theodore Ts'o0610b6e2009-06-15 03:45:05 -04004760 "Block = %llu, count = %lu", block, count);
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -04004761 /* err = 0. ext4_std_error should be a no op */
4762 goto error_return;
Alex Tomasc9de5602008-01-29 00:19:52 -05004763 }
4764
4765 BUFFER_TRACE(bitmap_bh, "getting write access");
4766 err = ext4_journal_get_write_access(handle, bitmap_bh);
4767 if (err)
4768 goto error_return;
4769
4770 /*
4771 * We are about to modify some metadata. Call the journal APIs
4772 * to unshare ->b_data if a currently-committing transaction is
4773 * using it
4774 */
4775 BUFFER_TRACE(gd_bh, "get_write_access");
4776 err = ext4_journal_get_write_access(handle, gd_bh);
4777 if (err)
4778 goto error_return;
Alex Tomasc9de5602008-01-29 00:19:52 -05004779#ifdef AGGRESSIVE_CHECK
4780 {
4781 int i;
4782 for (i = 0; i < count; i++)
4783 BUG_ON(!mb_test_bit(bit + i, bitmap_bh->b_data));
4784 }
4785#endif
Eric Sandeen256bdb42008-02-10 01:13:33 -05004786 if (ac) {
4787 ac->ac_b_ex.fe_group = block_group;
4788 ac->ac_b_ex.fe_start = bit;
4789 ac->ac_b_ex.fe_len = count;
4790 ext4_mb_store_history(ac);
4791 }
Alex Tomasc9de5602008-01-29 00:19:52 -05004792
Aneesh Kumar K.V920313a2009-01-05 21:36:19 -05004793 err = ext4_mb_load_buddy(sb, block_group, &e4b);
4794 if (err)
4795 goto error_return;
Frank Mayhar03901312009-01-07 00:06:22 -05004796 if (metadata && ext4_handle_valid(handle)) {
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -05004797 struct ext4_free_data *new_entry;
4798 /*
4799 * blocks being freed are metadata. these blocks shouldn't
4800 * be used until this transaction is committed
4801 */
4802 new_entry = kmem_cache_alloc(ext4_free_ext_cachep, GFP_NOFS);
4803 new_entry->start_blk = bit;
4804 new_entry->group = block_group;
4805 new_entry->count = count;
4806 new_entry->t_tid = handle->h_transaction->t_tid;
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04004807
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -05004808 ext4_lock_group(sb, block_group);
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04004809 mb_clear_bits(bitmap_bh->b_data, bit, count);
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -05004810 ext4_mb_free_metadata(handle, &e4b, new_entry);
Alex Tomasc9de5602008-01-29 00:19:52 -05004811 } else {
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -05004812 /* need to update group_info->bb_free and bitmap
4813 * with group lock held. generate_buddy look at
4814 * them with group lock_held
4815 */
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04004816 ext4_lock_group(sb, block_group);
4817 mb_clear_bits(bitmap_bh->b_data, bit, count);
Shen Feng7e5a8cd2008-07-13 21:03:31 -04004818 mb_free_blocks(inode, &e4b, bit, count);
Alex Tomasc9de5602008-01-29 00:19:52 -05004819 ext4_mb_return_to_preallocation(inode, &e4b, block, count);
Alex Tomasc9de5602008-01-29 00:19:52 -05004820 }
4821
Aneesh Kumar K.V560671a2009-01-05 22:20:24 -05004822 ret = ext4_free_blks_count(sb, gdp) + count;
4823 ext4_free_blks_set(sb, gdp, ret);
Alex Tomasc9de5602008-01-29 00:19:52 -05004824 gdp->bg_checksum = ext4_group_desc_csum(sbi, block_group, gdp);
Aneesh Kumar K.V955ce5f2009-05-02 20:35:09 -04004825 ext4_unlock_group(sb, block_group);
Alex Tomasc9de5602008-01-29 00:19:52 -05004826 percpu_counter_add(&sbi->s_freeblocks_counter, count);
4827
Jose R. Santos772cb7c2008-07-11 19:27:31 -04004828 if (sbi->s_log_groups_per_flex) {
4829 ext4_group_t flex_group = ext4_flex_group(sbi, block_group);
Theodore Ts'o9f24e422009-03-04 19:09:10 -05004830 atomic_add(count, &sbi->s_flex_groups[flex_group].free_blocks);
Jose R. Santos772cb7c2008-07-11 19:27:31 -04004831 }
4832
Alex Tomasc9de5602008-01-29 00:19:52 -05004833 ext4_mb_release_desc(&e4b);
4834
4835 *freed += count;
4836
Aneesh Kumar K.V7a2fcbf2009-01-05 21:36:55 -05004837 /* We dirtied the bitmap block */
4838 BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
4839 err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
4840
Alex Tomasc9de5602008-01-29 00:19:52 -05004841 /* And the group descriptor block */
4842 BUFFER_TRACE(gd_bh, "dirtied group descriptor block");
Frank Mayhar03901312009-01-07 00:06:22 -05004843 ret = ext4_handle_dirty_metadata(handle, NULL, gd_bh);
Alex Tomasc9de5602008-01-29 00:19:52 -05004844 if (!err)
4845 err = ret;
4846
4847 if (overflow && !err) {
4848 block += count;
4849 count = overflow;
4850 put_bh(bitmap_bh);
4851 goto do_more;
4852 }
4853 sb->s_dirt = 1;
4854error_return:
4855 brelse(bitmap_bh);
4856 ext4_std_error(sb, err);
Eric Sandeen256bdb42008-02-10 01:13:33 -05004857 if (ac)
4858 kmem_cache_free(ext4_ac_cachep, ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05004859 return;
4860}