blob: b882868f46614a789c07a054ecb3896cc4d3e017 [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"
Alex Tomasc9de5602008-01-29 00:19:52 -050025/*
26 * MUSTDO:
27 * - test ext4_ext_search_left() and ext4_ext_search_right()
28 * - search for metadata in few groups
29 *
30 * TODO v4:
31 * - normalization should take into account whether file is still open
32 * - discard preallocations if no free space left (policy?)
33 * - don't normalize tails
34 * - quota
35 * - reservation for superuser
36 *
37 * TODO v3:
38 * - bitmap read-ahead (proposed by Oleg Drokin aka green)
39 * - track min/max extents in each group for better group selection
40 * - mb_mark_used() may allocate chunk right after splitting buddy
41 * - tree of groups sorted by number of free blocks
42 * - error handling
43 */
44
45/*
46 * The allocation request involve request for multiple number of blocks
47 * near to the goal(block) value specified.
48 *
49 * During initialization phase of the allocator we decide to use the group
50 * preallocation or inode preallocation depending on the size file. The
51 * size of the file could be the resulting file size we would have after
52 * allocation or the current file size which ever is larger. If the size is
53 * less that sbi->s_mb_stream_request we select the group
54 * preallocation. The default value of s_mb_stream_request is 16
55 * blocks. This can also be tuned via
56 * /proc/fs/ext4/<partition>/stream_req. The value is represented in terms
57 * of number of blocks.
58 *
59 * The main motivation for having small file use group preallocation is to
60 * ensure that we have small file closer in the disk.
61 *
62 * First stage the allocator looks at the inode prealloc list
63 * ext4_inode_info->i_prealloc_list contain list of prealloc spaces for
64 * this particular inode. The inode prealloc space is represented as:
65 *
66 * pa_lstart -> the logical start block for this prealloc space
67 * pa_pstart -> the physical start block for this prealloc space
68 * pa_len -> lenght for this prealloc space
69 * pa_free -> free space available in this prealloc space
70 *
71 * The inode preallocation space is used looking at the _logical_ start
72 * block. If only the logical file block falls within the range of prealloc
73 * space we will consume the particular prealloc space. This make sure that
74 * that the we have contiguous physical blocks representing the file blocks
75 *
76 * The important thing to be noted in case of inode prealloc space is that
77 * we don't modify the values associated to inode prealloc space except
78 * pa_free.
79 *
80 * If we are not able to find blocks in the inode prealloc space and if we
81 * have the group allocation flag set then we look at the locality group
82 * prealloc space. These are per CPU prealloc list repreasented as
83 *
84 * ext4_sb_info.s_locality_groups[smp_processor_id()]
85 *
86 * The reason for having a per cpu locality group is to reduce the contention
87 * between CPUs. It is possible to get scheduled at this point.
88 *
89 * The locality group prealloc space is used looking at whether we have
90 * enough free space (pa_free) withing the prealloc space.
91 *
92 * If we can't allocate blocks via inode prealloc or/and locality group
93 * prealloc then we look at the buddy cache. The buddy cache is represented
94 * by ext4_sb_info.s_buddy_cache (struct inode) whose file offset gets
95 * mapped to the buddy and bitmap information regarding different
96 * groups. The buddy information is attached to buddy cache inode so that
97 * we can access them through the page cache. The information regarding
98 * each group is loaded via ext4_mb_load_buddy. The information involve
99 * block bitmap and buddy information. The information are stored in the
100 * inode as:
101 *
102 * { page }
103 * [ group 0 buddy][ group 0 bitmap] [group 1][ group 1]...
104 *
105 *
106 * one block each for bitmap and buddy information. So for each group we
107 * take up 2 blocks. A page can contain blocks_per_page (PAGE_CACHE_SIZE /
108 * blocksize) blocks. So it can have information regarding groups_per_page
109 * which is blocks_per_page/2
110 *
111 * The buddy cache inode is not stored on disk. The inode is thrown
112 * away when the filesystem is unmounted.
113 *
114 * We look for count number of blocks in the buddy cache. If we were able
115 * to locate that many free blocks we return with additional information
116 * regarding rest of the contiguous physical block available
117 *
118 * Before allocating blocks via buddy cache we normalize the request
119 * blocks. This ensure we ask for more blocks that we needed. The extra
120 * blocks that we get after allocation is added to the respective prealloc
121 * list. In case of inode preallocation we follow a list of heuristics
122 * based on file size. This can be found in ext4_mb_normalize_request. If
123 * we are doing a group prealloc we try to normalize the request to
124 * sbi->s_mb_group_prealloc. Default value of s_mb_group_prealloc is set to
125 * 512 blocks. This can be tuned via
126 * /proc/fs/ext4/<partition/group_prealloc. The value is represented in
127 * terms of number of blocks. If we have mounted the file system with -O
128 * stripe=<value> option the group prealloc request is normalized to the
129 * stripe value (sbi->s_stripe)
130 *
131 * The regular allocator(using the buddy cache) support few tunables.
132 *
133 * /proc/fs/ext4/<partition>/min_to_scan
134 * /proc/fs/ext4/<partition>/max_to_scan
135 * /proc/fs/ext4/<partition>/order2_req
136 *
137 * The regular allocator use buddy scan only if the request len is power of
138 * 2 blocks and the order of allocation is >= sbi->s_mb_order2_reqs. The
139 * value of s_mb_order2_reqs can be tuned via
140 * /proc/fs/ext4/<partition>/order2_req. If the request len is equal to
141 * stripe size (sbi->s_stripe), we try to search for contigous block in
142 * stripe size. This should result in better allocation on RAID setup. If
143 * not we search in the specific group using bitmap for best extents. The
144 * tunable min_to_scan and max_to_scan controll the behaviour here.
145 * min_to_scan indicate how long the mballoc __must__ look for a best
146 * extent and max_to_scanindicate how long the mballoc __can__ look for a
147 * best extent in the found extents. Searching for the blocks starts with
148 * the group specified as the goal value in allocation context via
149 * ac_g_ex. Each group is first checked based on the criteria whether it
150 * can used for allocation. ext4_mb_good_group explains how the groups are
151 * checked.
152 *
153 * Both the prealloc space are getting populated as above. So for the first
154 * request we will hit the buddy cache which will result in this prealloc
155 * space getting filled. The prealloc space is then later used for the
156 * subsequent request.
157 */
158
159/*
160 * mballoc operates on the following data:
161 * - on-disk bitmap
162 * - in-core buddy (actually includes buddy and bitmap)
163 * - preallocation descriptors (PAs)
164 *
165 * there are two types of preallocations:
166 * - inode
167 * assiged to specific inode and can be used for this inode only.
168 * it describes part of inode's space preallocated to specific
169 * physical blocks. any block from that preallocated can be used
170 * independent. the descriptor just tracks number of blocks left
171 * unused. so, before taking some block from descriptor, one must
172 * make sure corresponded logical block isn't allocated yet. this
173 * also means that freeing any block within descriptor's range
174 * must discard all preallocated blocks.
175 * - locality group
176 * assigned to specific locality group which does not translate to
177 * permanent set of inodes: inode can join and leave group. space
178 * from this type of preallocation can be used for any inode. thus
179 * it's consumed from the beginning to the end.
180 *
181 * relation between them can be expressed as:
182 * in-core buddy = on-disk bitmap + preallocation descriptors
183 *
184 * this mean blocks mballoc considers used are:
185 * - allocated blocks (persistent)
186 * - preallocated blocks (non-persistent)
187 *
188 * consistency in mballoc world means that at any time a block is either
189 * free or used in ALL structures. notice: "any time" should not be read
190 * literally -- time is discrete and delimited by locks.
191 *
192 * to keep it simple, we don't use block numbers, instead we count number of
193 * blocks: how many blocks marked used/free in on-disk bitmap, buddy and PA.
194 *
195 * all operations can be expressed as:
196 * - init buddy: buddy = on-disk + PAs
197 * - new PA: buddy += N; PA = N
198 * - use inode PA: on-disk += N; PA -= N
199 * - discard inode PA buddy -= on-disk - PA; PA = 0
200 * - use locality group PA on-disk += N; PA -= N
201 * - discard locality group PA buddy -= PA; PA = 0
202 * note: 'buddy -= on-disk - PA' is used to show that on-disk bitmap
203 * is used in real operation because we can't know actual used
204 * bits from PA, only from on-disk bitmap
205 *
206 * if we follow this strict logic, then all operations above should be atomic.
207 * given some of them can block, we'd have to use something like semaphores
208 * killing performance on high-end SMP hardware. let's try to relax it using
209 * the following knowledge:
210 * 1) if buddy is referenced, it's already initialized
211 * 2) while block is used in buddy and the buddy is referenced,
212 * nobody can re-allocate that block
213 * 3) we work on bitmaps and '+' actually means 'set bits'. if on-disk has
214 * bit set and PA claims same block, it's OK. IOW, one can set bit in
215 * on-disk bitmap if buddy has same bit set or/and PA covers corresponded
216 * block
217 *
218 * so, now we're building a concurrency table:
219 * - init buddy vs.
220 * - new PA
221 * blocks for PA are allocated in the buddy, buddy must be referenced
222 * until PA is linked to allocation group to avoid concurrent buddy init
223 * - use inode PA
224 * we need to make sure that either on-disk bitmap or PA has uptodate data
225 * given (3) we care that PA-=N operation doesn't interfere with init
226 * - discard inode PA
227 * the simplest way would be to have buddy initialized by the discard
228 * - use locality group PA
229 * again PA-=N must be serialized with init
230 * - discard locality group PA
231 * the simplest way would be to have buddy initialized by the discard
232 * - new PA vs.
233 * - use inode PA
234 * i_data_sem serializes them
235 * - discard inode PA
236 * discard process must wait until PA isn't used by another process
237 * - use locality group PA
238 * some mutex should serialize them
239 * - discard locality group PA
240 * discard process must wait until PA isn't used by another process
241 * - use inode PA
242 * - use inode PA
243 * i_data_sem or another mutex should serializes them
244 * - discard inode PA
245 * discard process must wait until PA isn't used by another process
246 * - use locality group PA
247 * nothing wrong here -- they're different PAs covering different blocks
248 * - discard locality group PA
249 * discard process must wait until PA isn't used by another process
250 *
251 * now we're ready to make few consequences:
252 * - PA is referenced and while it is no discard is possible
253 * - PA is referenced until block isn't marked in on-disk bitmap
254 * - PA changes only after on-disk bitmap
255 * - discard must not compete with init. either init is done before
256 * any discard or they're serialized somehow
257 * - buddy init as sum of on-disk bitmap and PAs is done atomically
258 *
259 * a special case when we've used PA to emptiness. no need to modify buddy
260 * in this case, but we should care about concurrent init
261 *
262 */
263
264 /*
265 * Logic in few words:
266 *
267 * - allocation:
268 * load group
269 * find blocks
270 * mark bits in on-disk bitmap
271 * release group
272 *
273 * - use preallocation:
274 * find proper PA (per-inode or group)
275 * load group
276 * mark bits in on-disk bitmap
277 * release group
278 * release PA
279 *
280 * - free:
281 * load group
282 * mark bits in on-disk bitmap
283 * release group
284 *
285 * - discard preallocations in group:
286 * mark PAs deleted
287 * move them onto local list
288 * load on-disk bitmap
289 * load group
290 * remove PA from object (inode or locality group)
291 * mark free blocks in-core
292 *
293 * - discard inode's preallocations:
294 */
295
296/*
297 * Locking rules
298 *
299 * Locks:
300 * - bitlock on a group (group)
301 * - object (inode/locality) (object)
302 * - per-pa lock (pa)
303 *
304 * Paths:
305 * - new pa
306 * object
307 * group
308 *
309 * - find and use pa:
310 * pa
311 *
312 * - release consumed pa:
313 * pa
314 * group
315 * object
316 *
317 * - generate in-core bitmap:
318 * group
319 * pa
320 *
321 * - discard all for given object (inode, locality group):
322 * object
323 * pa
324 * group
325 *
326 * - discard all for given group:
327 * group
328 * pa
329 * group
330 * object
331 *
332 */
333
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500334static inline void *mb_correct_addr_and_bit(int *bit, void *addr)
335{
Alex Tomasc9de5602008-01-29 00:19:52 -0500336#if BITS_PER_LONG == 64
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500337 *bit += ((unsigned long) addr & 7UL) << 3;
338 addr = (void *) ((unsigned long) addr & ~7UL);
Alex Tomasc9de5602008-01-29 00:19:52 -0500339#elif BITS_PER_LONG == 32
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500340 *bit += ((unsigned long) addr & 3UL) << 3;
341 addr = (void *) ((unsigned long) addr & ~3UL);
Alex Tomasc9de5602008-01-29 00:19:52 -0500342#else
343#error "how many bits you are?!"
344#endif
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500345 return addr;
346}
Alex Tomasc9de5602008-01-29 00:19:52 -0500347
348static inline int mb_test_bit(int bit, void *addr)
349{
350 /*
351 * ext4_test_bit on architecture like powerpc
352 * needs unsigned long aligned address
353 */
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500354 addr = mb_correct_addr_and_bit(&bit, addr);
Alex Tomasc9de5602008-01-29 00:19:52 -0500355 return ext4_test_bit(bit, addr);
356}
357
358static inline void mb_set_bit(int bit, void *addr)
359{
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500360 addr = mb_correct_addr_and_bit(&bit, addr);
Alex Tomasc9de5602008-01-29 00:19:52 -0500361 ext4_set_bit(bit, addr);
362}
363
364static inline void mb_set_bit_atomic(spinlock_t *lock, int bit, void *addr)
365{
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500366 addr = mb_correct_addr_and_bit(&bit, addr);
Alex Tomasc9de5602008-01-29 00:19:52 -0500367 ext4_set_bit_atomic(lock, bit, addr);
368}
369
370static inline void mb_clear_bit(int bit, void *addr)
371{
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500372 addr = mb_correct_addr_and_bit(&bit, addr);
Alex Tomasc9de5602008-01-29 00:19:52 -0500373 ext4_clear_bit(bit, addr);
374}
375
376static inline void mb_clear_bit_atomic(spinlock_t *lock, int bit, void *addr)
377{
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500378 addr = mb_correct_addr_and_bit(&bit, addr);
Alex Tomasc9de5602008-01-29 00:19:52 -0500379 ext4_clear_bit_atomic(lock, bit, addr);
380}
381
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500382static inline int mb_find_next_zero_bit(void *addr, int max, int start)
383{
Aneesh Kumar K.Ve7dfb242008-07-11 19:27:31 -0400384 int fix = 0, ret, tmpmax;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500385 addr = mb_correct_addr_and_bit(&fix, addr);
Aneesh Kumar K.Ve7dfb242008-07-11 19:27:31 -0400386 tmpmax = max + fix;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500387 start += fix;
388
Aneesh Kumar K.Ve7dfb242008-07-11 19:27:31 -0400389 ret = ext4_find_next_zero_bit(addr, tmpmax, start) - fix;
390 if (ret > max)
391 return max;
392 return ret;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500393}
394
395static inline int mb_find_next_bit(void *addr, int max, int start)
396{
Aneesh Kumar K.Ve7dfb242008-07-11 19:27:31 -0400397 int fix = 0, ret, tmpmax;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500398 addr = mb_correct_addr_and_bit(&fix, addr);
Aneesh Kumar K.Ve7dfb242008-07-11 19:27:31 -0400399 tmpmax = max + fix;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500400 start += fix;
401
Aneesh Kumar K.Ve7dfb242008-07-11 19:27:31 -0400402 ret = ext4_find_next_bit(addr, tmpmax, start) - fix;
403 if (ret > max)
404 return max;
405 return ret;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500406}
407
Alex Tomasc9de5602008-01-29 00:19:52 -0500408static void *mb_find_buddy(struct ext4_buddy *e4b, int order, int *max)
409{
410 char *bb;
411
Alex Tomasc9de5602008-01-29 00:19:52 -0500412 BUG_ON(EXT4_MB_BITMAP(e4b) == EXT4_MB_BUDDY(e4b));
413 BUG_ON(max == NULL);
414
415 if (order > e4b->bd_blkbits + 1) {
416 *max = 0;
417 return NULL;
418 }
419
420 /* at order 0 we see each particular block */
421 *max = 1 << (e4b->bd_blkbits + 3);
422 if (order == 0)
423 return EXT4_MB_BITMAP(e4b);
424
425 bb = EXT4_MB_BUDDY(e4b) + EXT4_SB(e4b->bd_sb)->s_mb_offsets[order];
426 *max = EXT4_SB(e4b->bd_sb)->s_mb_maxs[order];
427
428 return bb;
429}
430
431#ifdef DOUBLE_CHECK
432static void mb_free_blocks_double(struct inode *inode, struct ext4_buddy *e4b,
433 int first, int count)
434{
435 int i;
436 struct super_block *sb = e4b->bd_sb;
437
438 if (unlikely(e4b->bd_info->bb_bitmap == NULL))
439 return;
440 BUG_ON(!ext4_is_group_locked(sb, e4b->bd_group));
441 for (i = 0; i < count; i++) {
442 if (!mb_test_bit(first + i, e4b->bd_info->bb_bitmap)) {
443 ext4_fsblk_t blocknr;
444 blocknr = e4b->bd_group * EXT4_BLOCKS_PER_GROUP(sb);
445 blocknr += first + i;
446 blocknr +=
447 le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);
448
Harvey Harrison46e665e2008-04-17 10:38:59 -0400449 ext4_error(sb, __func__, "double-free of inode"
Alex Tomasc9de5602008-01-29 00:19:52 -0500450 " %lu's block %llu(bit %u in group %lu)\n",
451 inode ? inode->i_ino : 0, blocknr,
452 first + i, e4b->bd_group);
453 }
454 mb_clear_bit(first + i, e4b->bd_info->bb_bitmap);
455 }
456}
457
458static void mb_mark_used_double(struct ext4_buddy *e4b, int first, int count)
459{
460 int i;
461
462 if (unlikely(e4b->bd_info->bb_bitmap == NULL))
463 return;
464 BUG_ON(!ext4_is_group_locked(e4b->bd_sb, e4b->bd_group));
465 for (i = 0; i < count; i++) {
466 BUG_ON(mb_test_bit(first + i, e4b->bd_info->bb_bitmap));
467 mb_set_bit(first + i, e4b->bd_info->bb_bitmap);
468 }
469}
470
471static void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap)
472{
473 if (memcmp(e4b->bd_info->bb_bitmap, bitmap, e4b->bd_sb->s_blocksize)) {
474 unsigned char *b1, *b2;
475 int i;
476 b1 = (unsigned char *) e4b->bd_info->bb_bitmap;
477 b2 = (unsigned char *) bitmap;
478 for (i = 0; i < e4b->bd_sb->s_blocksize; i++) {
479 if (b1[i] != b2[i]) {
480 printk("corruption in group %lu at byte %u(%u):"
481 " %x in copy != %x on disk/prealloc\n",
482 e4b->bd_group, i, i * 8, b1[i], b2[i]);
483 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
536 if (!test_opt(sb, MBALLOC))
537 return 0;
538
539 {
540 static int mb_check_counter;
541 if (mb_check_counter++ % 100 != 0)
542 return 0;
543 }
544
545 while (order > 1) {
546 buddy = mb_find_buddy(e4b, order, &max);
547 MB_CHECK_ASSERT(buddy);
548 buddy2 = mb_find_buddy(e4b, order - 1, &max2);
549 MB_CHECK_ASSERT(buddy2);
550 MB_CHECK_ASSERT(buddy != buddy2);
551 MB_CHECK_ASSERT(max * 2 == max2);
552
553 count = 0;
554 for (i = 0; i < max; i++) {
555
556 if (mb_test_bit(i, buddy)) {
557 /* only single bit in buddy2 may be 1 */
558 if (!mb_test_bit(i << 1, buddy2)) {
559 MB_CHECK_ASSERT(
560 mb_test_bit((i<<1)+1, buddy2));
561 } else if (!mb_test_bit((i << 1) + 1, buddy2)) {
562 MB_CHECK_ASSERT(
563 mb_test_bit(i << 1, buddy2));
564 }
565 continue;
566 }
567
568 /* both bits in buddy2 must be 0 */
569 MB_CHECK_ASSERT(mb_test_bit(i << 1, buddy2));
570 MB_CHECK_ASSERT(mb_test_bit((i << 1) + 1, buddy2));
571
572 for (j = 0; j < (1 << order); j++) {
573 k = (i * (1 << order)) + j;
574 MB_CHECK_ASSERT(
575 !mb_test_bit(k, EXT4_MB_BITMAP(e4b)));
576 }
577 count++;
578 }
579 MB_CHECK_ASSERT(e4b->bd_info->bb_counters[order] == count);
580 order--;
581 }
582
583 fstart = -1;
584 buddy = mb_find_buddy(e4b, 0, &max);
585 for (i = 0; i < max; i++) {
586 if (!mb_test_bit(i, buddy)) {
587 MB_CHECK_ASSERT(i >= e4b->bd_info->bb_first_free);
588 if (fstart == -1) {
589 fragments++;
590 fstart = i;
591 }
592 continue;
593 }
594 fstart = -1;
595 /* check used bits only */
596 for (j = 0; j < e4b->bd_blkbits + 1; j++) {
597 buddy2 = mb_find_buddy(e4b, j, &max2);
598 k = i >> j;
599 MB_CHECK_ASSERT(k < max2);
600 MB_CHECK_ASSERT(mb_test_bit(k, buddy2));
601 }
602 }
603 MB_CHECK_ASSERT(!EXT4_MB_GRP_NEED_INIT(e4b->bd_info));
604 MB_CHECK_ASSERT(e4b->bd_info->bb_fragments == fragments);
605
606 grp = ext4_get_group_info(sb, e4b->bd_group);
607 buddy = mb_find_buddy(e4b, 0, &max);
608 list_for_each(cur, &grp->bb_prealloc_list) {
609 ext4_group_t groupnr;
610 struct ext4_prealloc_space *pa;
Solofo Ramangalahy60bd63d2008-04-29 21:59:59 -0400611 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
612 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &groupnr, &k);
Alex Tomasc9de5602008-01-29 00:19:52 -0500613 MB_CHECK_ASSERT(groupnr == e4b->bd_group);
Solofo Ramangalahy60bd63d2008-04-29 21:59:59 -0400614 for (i = 0; i < pa->pa_len; i++)
Alex Tomasc9de5602008-01-29 00:19:52 -0500615 MB_CHECK_ASSERT(mb_test_bit(k + i, buddy));
616 }
617 return 0;
618}
619#undef MB_CHECK_ASSERT
620#define mb_check_buddy(e4b) __mb_check_buddy(e4b, \
Harvey Harrison46e665e2008-04-17 10:38:59 -0400621 __FILE__, __func__, __LINE__)
Alex Tomasc9de5602008-01-29 00:19:52 -0500622#else
623#define mb_check_buddy(e4b)
624#endif
625
626/* FIXME!! need more doc */
627static void ext4_mb_mark_free_simple(struct super_block *sb,
628 void *buddy, unsigned first, int len,
629 struct ext4_group_info *grp)
630{
631 struct ext4_sb_info *sbi = EXT4_SB(sb);
632 unsigned short min;
633 unsigned short max;
634 unsigned short chunk;
635 unsigned short border;
636
Valerie Clementb73fce62008-02-15 13:48:51 -0500637 BUG_ON(len > EXT4_BLOCKS_PER_GROUP(sb));
Alex Tomasc9de5602008-01-29 00:19:52 -0500638
639 border = 2 << sb->s_blocksize_bits;
640
641 while (len > 0) {
642 /* find how many blocks can be covered since this position */
643 max = ffs(first | border) - 1;
644
645 /* find how many blocks of power 2 we need to mark */
646 min = fls(len) - 1;
647
648 if (max < min)
649 min = max;
650 chunk = 1 << min;
651
652 /* mark multiblock chunks only */
653 grp->bb_counters[min]++;
654 if (min > 0)
655 mb_clear_bit(first >> min,
656 buddy + sbi->s_mb_offsets[min]);
657
658 len -= chunk;
659 first += chunk;
660 }
661}
662
663static void ext4_mb_generate_buddy(struct super_block *sb,
664 void *buddy, void *bitmap, ext4_group_t group)
665{
666 struct ext4_group_info *grp = ext4_get_group_info(sb, group);
667 unsigned short max = EXT4_BLOCKS_PER_GROUP(sb);
668 unsigned short i = 0;
669 unsigned short first;
670 unsigned short len;
671 unsigned free = 0;
672 unsigned fragments = 0;
673 unsigned long long period = get_cycles();
674
675 /* initialize buddy from bitmap which is aggregation
676 * of on-disk bitmap and preallocations */
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500677 i = mb_find_next_zero_bit(bitmap, max, 0);
Alex Tomasc9de5602008-01-29 00:19:52 -0500678 grp->bb_first_free = i;
679 while (i < max) {
680 fragments++;
681 first = i;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500682 i = mb_find_next_bit(bitmap, max, i);
Alex Tomasc9de5602008-01-29 00:19:52 -0500683 len = i - first;
684 free += len;
685 if (len > 1)
686 ext4_mb_mark_free_simple(sb, buddy, first, len, grp);
687 else
688 grp->bb_counters[0]++;
689 if (i < max)
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -0500690 i = mb_find_next_zero_bit(bitmap, max, i);
Alex Tomasc9de5602008-01-29 00:19:52 -0500691 }
692 grp->bb_fragments = fragments;
693
694 if (free != grp->bb_free) {
Harvey Harrison46e665e2008-04-17 10:38:59 -0400695 ext4_error(sb, __func__,
Alex Tomasc9de5602008-01-29 00:19:52 -0500696 "EXT4-fs: group %lu: %u blocks in bitmap, %u in gd\n",
697 group, free, grp->bb_free);
Aneesh Kumar K.Ve56eb652008-02-15 13:48:21 -0500698 /*
699 * If we intent to continue, we consider group descritor
700 * corrupt and update bb_free using bitmap value
701 */
Alex Tomasc9de5602008-01-29 00:19:52 -0500702 grp->bb_free = free;
703 }
704
705 clear_bit(EXT4_GROUP_INFO_NEED_INIT_BIT, &(grp->bb_state));
706
707 period = get_cycles() - period;
708 spin_lock(&EXT4_SB(sb)->s_bal_lock);
709 EXT4_SB(sb)->s_mb_buddies_generated++;
710 EXT4_SB(sb)->s_mb_generation_time += period;
711 spin_unlock(&EXT4_SB(sb)->s_bal_lock);
712}
713
714/* The buddy information is attached the buddy cache inode
715 * for convenience. The information regarding each group
716 * is loaded via ext4_mb_load_buddy. The information involve
717 * block bitmap and buddy information. The information are
718 * stored in the inode as
719 *
720 * { page }
721 * [ group 0 buddy][ group 0 bitmap] [group 1][ group 1]...
722 *
723 *
724 * one block each for bitmap and buddy information.
725 * So for each group we take up 2 blocks. A page can
726 * contain blocks_per_page (PAGE_CACHE_SIZE / blocksize) blocks.
727 * So it can have information regarding groups_per_page which
728 * is blocks_per_page/2
729 */
730
731static int ext4_mb_init_cache(struct page *page, char *incore)
732{
733 int blocksize;
734 int blocks_per_page;
735 int groups_per_page;
736 int err = 0;
737 int i;
738 ext4_group_t first_group;
739 int first_block;
740 struct super_block *sb;
741 struct buffer_head *bhs;
742 struct buffer_head **bh;
743 struct inode *inode;
744 char *data;
745 char *bitmap;
746
747 mb_debug("init page %lu\n", page->index);
748
749 inode = page->mapping->host;
750 sb = inode->i_sb;
751 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
774 if (first_group + i >= EXT4_SB(sb)->s_groups_count)
775 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
787 if (bh_uptodate_or_lock(bh[i]))
788 continue;
789
790 if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
791 ext4_init_block_bitmap(sb, bh[i],
792 first_group + i, desc);
793 set_buffer_uptodate(bh[i]);
794 unlock_buffer(bh[i]);
795 continue;
796 }
797 get_bh(bh[i]);
798 bh[i]->b_end_io = end_buffer_read_sync;
799 submit_bh(READ, bh[i]);
800 mb_debug("read bitmap for group %lu\n", first_group + i);
801 }
802
803 /* wait for I/O completion */
804 for (i = 0; i < groups_per_page && bh[i]; i++)
805 wait_on_buffer(bh[i]);
806
807 err = -EIO;
808 for (i = 0; i < groups_per_page && bh[i]; i++)
809 if (!buffer_uptodate(bh[i]))
810 goto out;
811
Mingming Cao31b481d2008-07-11 19:27:31 -0400812 err = 0;
Alex Tomasc9de5602008-01-29 00:19:52 -0500813 first_block = page->index * blocks_per_page;
814 for (i = 0; i < blocks_per_page; i++) {
815 int group;
816 struct ext4_group_info *grinfo;
817
818 group = (first_block + i) >> 1;
819 if (group >= EXT4_SB(sb)->s_groups_count)
820 break;
821
822 /*
823 * data carry information regarding this
824 * particular group in the format specified
825 * above
826 *
827 */
828 data = page_address(page) + (i * blocksize);
829 bitmap = bh[group - first_group]->b_data;
830
831 /*
832 * We place the buddy block and bitmap block
833 * close together
834 */
835 if ((first_block + i) & 1) {
836 /* this is block of buddy */
837 BUG_ON(incore == NULL);
838 mb_debug("put buddy for group %u in page %lu/%x\n",
839 group, page->index, i * blocksize);
840 memset(data, 0xff, blocksize);
841 grinfo = ext4_get_group_info(sb, group);
842 grinfo->bb_fragments = 0;
843 memset(grinfo->bb_counters, 0,
844 sizeof(unsigned short)*(sb->s_blocksize_bits+2));
845 /*
846 * incore got set to the group block bitmap below
847 */
848 ext4_mb_generate_buddy(sb, data, incore, group);
849 incore = NULL;
850 } else {
851 /* this is block of bitmap */
852 BUG_ON(incore != NULL);
853 mb_debug("put bitmap for group %u in page %lu/%x\n",
854 group, page->index, i * blocksize);
855
856 /* see comments in ext4_mb_put_pa() */
857 ext4_lock_group(sb, group);
858 memcpy(data, bitmap, blocksize);
859
860 /* mark all preallocated blks used in in-core bitmap */
861 ext4_mb_generate_from_pa(sb, data, group);
862 ext4_unlock_group(sb, group);
863
864 /* set incore so that the buddy information can be
865 * generated using this
866 */
867 incore = data;
868 }
869 }
870 SetPageUptodate(page);
871
872out:
873 if (bh) {
874 for (i = 0; i < groups_per_page && bh[i]; i++)
875 brelse(bh[i]);
876 if (bh != &bhs)
877 kfree(bh);
878 }
879 return err;
880}
881
Eric Sandeen4ddfef72008-04-29 08:11:12 -0400882static noinline_for_stack int
883ext4_mb_load_buddy(struct super_block *sb, ext4_group_t group,
884 struct ext4_buddy *e4b)
Alex Tomasc9de5602008-01-29 00:19:52 -0500885{
886 struct ext4_sb_info *sbi = EXT4_SB(sb);
887 struct inode *inode = sbi->s_buddy_cache;
888 int blocks_per_page;
889 int block;
890 int pnum;
891 int poff;
892 struct page *page;
Shen Fengfdf6c7a2008-07-11 19:27:31 -0400893 int ret;
Alex Tomasc9de5602008-01-29 00:19:52 -0500894
895 mb_debug("load group %lu\n", group);
896
897 blocks_per_page = PAGE_CACHE_SIZE / sb->s_blocksize;
898
899 e4b->bd_blkbits = sb->s_blocksize_bits;
900 e4b->bd_info = ext4_get_group_info(sb, group);
901 e4b->bd_sb = sb;
902 e4b->bd_group = group;
903 e4b->bd_buddy_page = NULL;
904 e4b->bd_bitmap_page = NULL;
905
906 /*
907 * the buddy cache inode stores the block bitmap
908 * and buddy information in consecutive blocks.
909 * So for each group we need two blocks.
910 */
911 block = group * 2;
912 pnum = block / blocks_per_page;
913 poff = block % blocks_per_page;
914
915 /* we could use find_or_create_page(), but it locks page
916 * what we'd like to avoid in fast path ... */
917 page = find_get_page(inode->i_mapping, pnum);
918 if (page == NULL || !PageUptodate(page)) {
919 if (page)
920 page_cache_release(page);
921 page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
922 if (page) {
923 BUG_ON(page->mapping != inode->i_mapping);
924 if (!PageUptodate(page)) {
Shen Fengfdf6c7a2008-07-11 19:27:31 -0400925 ret = ext4_mb_init_cache(page, NULL);
926 if (ret) {
927 unlock_page(page);
928 goto err;
929 }
Alex Tomasc9de5602008-01-29 00:19:52 -0500930 mb_cmp_bitmaps(e4b, page_address(page) +
931 (poff * sb->s_blocksize));
932 }
933 unlock_page(page);
934 }
935 }
Shen Fengfdf6c7a2008-07-11 19:27:31 -0400936 if (page == NULL || !PageUptodate(page)) {
937 ret = -EIO;
Alex Tomasc9de5602008-01-29 00:19:52 -0500938 goto err;
Shen Fengfdf6c7a2008-07-11 19:27:31 -0400939 }
Alex Tomasc9de5602008-01-29 00:19:52 -0500940 e4b->bd_bitmap_page = page;
941 e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);
942 mark_page_accessed(page);
943
944 block++;
945 pnum = block / blocks_per_page;
946 poff = block % blocks_per_page;
947
948 page = find_get_page(inode->i_mapping, pnum);
949 if (page == NULL || !PageUptodate(page)) {
950 if (page)
951 page_cache_release(page);
952 page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
953 if (page) {
954 BUG_ON(page->mapping != inode->i_mapping);
Shen Fengfdf6c7a2008-07-11 19:27:31 -0400955 if (!PageUptodate(page)) {
956 ret = ext4_mb_init_cache(page, e4b->bd_bitmap);
957 if (ret) {
958 unlock_page(page);
959 goto err;
960 }
961 }
Alex Tomasc9de5602008-01-29 00:19:52 -0500962 unlock_page(page);
963 }
964 }
Shen Fengfdf6c7a2008-07-11 19:27:31 -0400965 if (page == NULL || !PageUptodate(page)) {
966 ret = -EIO;
Alex Tomasc9de5602008-01-29 00:19:52 -0500967 goto err;
Shen Fengfdf6c7a2008-07-11 19:27:31 -0400968 }
Alex Tomasc9de5602008-01-29 00:19:52 -0500969 e4b->bd_buddy_page = page;
970 e4b->bd_buddy = page_address(page) + (poff * sb->s_blocksize);
971 mark_page_accessed(page);
972
973 BUG_ON(e4b->bd_bitmap_page == NULL);
974 BUG_ON(e4b->bd_buddy_page == NULL);
975
976 return 0;
977
978err:
979 if (e4b->bd_bitmap_page)
980 page_cache_release(e4b->bd_bitmap_page);
981 if (e4b->bd_buddy_page)
982 page_cache_release(e4b->bd_buddy_page);
983 e4b->bd_buddy = NULL;
984 e4b->bd_bitmap = NULL;
Shen Fengfdf6c7a2008-07-11 19:27:31 -0400985 return ret;
Alex Tomasc9de5602008-01-29 00:19:52 -0500986}
987
988static void ext4_mb_release_desc(struct ext4_buddy *e4b)
989{
990 if (e4b->bd_bitmap_page)
991 page_cache_release(e4b->bd_bitmap_page);
992 if (e4b->bd_buddy_page)
993 page_cache_release(e4b->bd_buddy_page);
994}
995
996
997static int mb_find_order_for_block(struct ext4_buddy *e4b, int block)
998{
999 int order = 1;
1000 void *bb;
1001
1002 BUG_ON(EXT4_MB_BITMAP(e4b) == EXT4_MB_BUDDY(e4b));
1003 BUG_ON(block >= (1 << (e4b->bd_blkbits + 3)));
1004
1005 bb = EXT4_MB_BUDDY(e4b);
1006 while (order <= e4b->bd_blkbits + 1) {
1007 block = block >> 1;
1008 if (!mb_test_bit(block, bb)) {
1009 /* this block is part of buddy of order 'order' */
1010 return order;
1011 }
1012 bb += 1 << (e4b->bd_blkbits - order);
1013 order++;
1014 }
1015 return 0;
1016}
1017
1018static void mb_clear_bits(spinlock_t *lock, void *bm, int cur, int len)
1019{
1020 __u32 *addr;
1021
1022 len = cur + len;
1023 while (cur < len) {
1024 if ((cur & 31) == 0 && (len - cur) >= 32) {
1025 /* fast path: clear whole word at once */
1026 addr = bm + (cur >> 3);
1027 *addr = 0;
1028 cur += 32;
1029 continue;
1030 }
1031 mb_clear_bit_atomic(lock, cur, bm);
1032 cur++;
1033 }
1034}
1035
1036static void mb_set_bits(spinlock_t *lock, void *bm, int cur, int len)
1037{
1038 __u32 *addr;
1039
1040 len = cur + len;
1041 while (cur < len) {
1042 if ((cur & 31) == 0 && (len - cur) >= 32) {
1043 /* fast path: set whole word at once */
1044 addr = bm + (cur >> 3);
1045 *addr = 0xffffffff;
1046 cur += 32;
1047 continue;
1048 }
1049 mb_set_bit_atomic(lock, cur, bm);
1050 cur++;
1051 }
1052}
1053
Shen Feng7e5a8cd2008-07-13 21:03:31 -04001054static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,
Alex Tomasc9de5602008-01-29 00:19:52 -05001055 int first, int count)
1056{
1057 int block = 0;
1058 int max = 0;
1059 int order;
1060 void *buddy;
1061 void *buddy2;
1062 struct super_block *sb = e4b->bd_sb;
1063
1064 BUG_ON(first + count > (sb->s_blocksize << 3));
1065 BUG_ON(!ext4_is_group_locked(sb, e4b->bd_group));
1066 mb_check_buddy(e4b);
1067 mb_free_blocks_double(inode, e4b, first, count);
1068
1069 e4b->bd_info->bb_free += count;
1070 if (first < e4b->bd_info->bb_first_free)
1071 e4b->bd_info->bb_first_free = first;
1072
1073 /* let's maintain fragments counter */
1074 if (first != 0)
1075 block = !mb_test_bit(first - 1, EXT4_MB_BITMAP(e4b));
1076 if (first + count < EXT4_SB(sb)->s_mb_maxs[0])
1077 max = !mb_test_bit(first + count, EXT4_MB_BITMAP(e4b));
1078 if (block && max)
1079 e4b->bd_info->bb_fragments--;
1080 else if (!block && !max)
1081 e4b->bd_info->bb_fragments++;
1082
1083 /* let's maintain buddy itself */
1084 while (count-- > 0) {
1085 block = first++;
1086 order = 0;
1087
1088 if (!mb_test_bit(block, EXT4_MB_BITMAP(e4b))) {
1089 ext4_fsblk_t blocknr;
1090 blocknr = e4b->bd_group * EXT4_BLOCKS_PER_GROUP(sb);
1091 blocknr += block;
1092 blocknr +=
1093 le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);
Shen Feng7e5a8cd2008-07-13 21:03:31 -04001094 ext4_unlock_group(sb, e4b->bd_group);
Harvey Harrison46e665e2008-04-17 10:38:59 -04001095 ext4_error(sb, __func__, "double-free of inode"
Alex Tomasc9de5602008-01-29 00:19:52 -05001096 " %lu's block %llu(bit %u in group %lu)\n",
1097 inode ? inode->i_ino : 0, blocknr, block,
1098 e4b->bd_group);
Shen Feng7e5a8cd2008-07-13 21:03:31 -04001099 ext4_lock_group(sb, e4b->bd_group);
Alex Tomasc9de5602008-01-29 00:19:52 -05001100 }
1101 mb_clear_bit(block, EXT4_MB_BITMAP(e4b));
1102 e4b->bd_info->bb_counters[order]++;
1103
1104 /* start of the buddy */
1105 buddy = mb_find_buddy(e4b, order, &max);
1106
1107 do {
1108 block &= ~1UL;
1109 if (mb_test_bit(block, buddy) ||
1110 mb_test_bit(block + 1, buddy))
1111 break;
1112
1113 /* both the buddies are free, try to coalesce them */
1114 buddy2 = mb_find_buddy(e4b, order + 1, &max);
1115
1116 if (!buddy2)
1117 break;
1118
1119 if (order > 0) {
1120 /* for special purposes, we don't set
1121 * free bits in bitmap */
1122 mb_set_bit(block, buddy);
1123 mb_set_bit(block + 1, buddy);
1124 }
1125 e4b->bd_info->bb_counters[order]--;
1126 e4b->bd_info->bb_counters[order]--;
1127
1128 block = block >> 1;
1129 order++;
1130 e4b->bd_info->bb_counters[order]++;
1131
1132 mb_clear_bit(block, buddy2);
1133 buddy = buddy2;
1134 } while (1);
1135 }
1136 mb_check_buddy(e4b);
Alex Tomasc9de5602008-01-29 00:19:52 -05001137}
1138
1139static int mb_find_extent(struct ext4_buddy *e4b, int order, int block,
1140 int needed, struct ext4_free_extent *ex)
1141{
1142 int next = block;
1143 int max;
1144 int ord;
1145 void *buddy;
1146
1147 BUG_ON(!ext4_is_group_locked(e4b->bd_sb, e4b->bd_group));
1148 BUG_ON(ex == NULL);
1149
1150 buddy = mb_find_buddy(e4b, order, &max);
1151 BUG_ON(buddy == NULL);
1152 BUG_ON(block >= max);
1153 if (mb_test_bit(block, buddy)) {
1154 ex->fe_len = 0;
1155 ex->fe_start = 0;
1156 ex->fe_group = 0;
1157 return 0;
1158 }
1159
1160 /* FIXME dorp order completely ? */
1161 if (likely(order == 0)) {
1162 /* find actual order */
1163 order = mb_find_order_for_block(e4b, block);
1164 block = block >> order;
1165 }
1166
1167 ex->fe_len = 1 << order;
1168 ex->fe_start = block << order;
1169 ex->fe_group = e4b->bd_group;
1170
1171 /* calc difference from given start */
1172 next = next - ex->fe_start;
1173 ex->fe_len -= next;
1174 ex->fe_start += next;
1175
1176 while (needed > ex->fe_len &&
1177 (buddy = mb_find_buddy(e4b, order, &max))) {
1178
1179 if (block + 1 >= max)
1180 break;
1181
1182 next = (block + 1) * (1 << order);
1183 if (mb_test_bit(next, EXT4_MB_BITMAP(e4b)))
1184 break;
1185
1186 ord = mb_find_order_for_block(e4b, next);
1187
1188 order = ord;
1189 block = next >> order;
1190 ex->fe_len += 1 << order;
1191 }
1192
1193 BUG_ON(ex->fe_start + ex->fe_len > (1 << (e4b->bd_blkbits + 3)));
1194 return ex->fe_len;
1195}
1196
1197static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
1198{
1199 int ord;
1200 int mlen = 0;
1201 int max = 0;
1202 int cur;
1203 int start = ex->fe_start;
1204 int len = ex->fe_len;
1205 unsigned ret = 0;
1206 int len0 = len;
1207 void *buddy;
1208
1209 BUG_ON(start + len > (e4b->bd_sb->s_blocksize << 3));
1210 BUG_ON(e4b->bd_group != ex->fe_group);
1211 BUG_ON(!ext4_is_group_locked(e4b->bd_sb, e4b->bd_group));
1212 mb_check_buddy(e4b);
1213 mb_mark_used_double(e4b, start, len);
1214
1215 e4b->bd_info->bb_free -= len;
1216 if (e4b->bd_info->bb_first_free == start)
1217 e4b->bd_info->bb_first_free += len;
1218
1219 /* let's maintain fragments counter */
1220 if (start != 0)
1221 mlen = !mb_test_bit(start - 1, EXT4_MB_BITMAP(e4b));
1222 if (start + len < EXT4_SB(e4b->bd_sb)->s_mb_maxs[0])
1223 max = !mb_test_bit(start + len, EXT4_MB_BITMAP(e4b));
1224 if (mlen && max)
1225 e4b->bd_info->bb_fragments++;
1226 else if (!mlen && !max)
1227 e4b->bd_info->bb_fragments--;
1228
1229 /* let's maintain buddy itself */
1230 while (len) {
1231 ord = mb_find_order_for_block(e4b, start);
1232
1233 if (((start >> ord) << ord) == start && len >= (1 << ord)) {
1234 /* the whole chunk may be allocated at once! */
1235 mlen = 1 << ord;
1236 buddy = mb_find_buddy(e4b, ord, &max);
1237 BUG_ON((start >> ord) >= max);
1238 mb_set_bit(start >> ord, buddy);
1239 e4b->bd_info->bb_counters[ord]--;
1240 start += mlen;
1241 len -= mlen;
1242 BUG_ON(len < 0);
1243 continue;
1244 }
1245
1246 /* store for history */
1247 if (ret == 0)
1248 ret = len | (ord << 16);
1249
1250 /* we have to split large buddy */
1251 BUG_ON(ord <= 0);
1252 buddy = mb_find_buddy(e4b, ord, &max);
1253 mb_set_bit(start >> ord, buddy);
1254 e4b->bd_info->bb_counters[ord]--;
1255
1256 ord--;
1257 cur = (start >> ord) & ~1U;
1258 buddy = mb_find_buddy(e4b, ord, &max);
1259 mb_clear_bit(cur, buddy);
1260 mb_clear_bit(cur + 1, buddy);
1261 e4b->bd_info->bb_counters[ord]++;
1262 e4b->bd_info->bb_counters[ord]++;
1263 }
1264
1265 mb_set_bits(sb_bgl_lock(EXT4_SB(e4b->bd_sb), ex->fe_group),
1266 EXT4_MB_BITMAP(e4b), ex->fe_start, len0);
1267 mb_check_buddy(e4b);
1268
1269 return ret;
1270}
1271
1272/*
1273 * Must be called under group lock!
1274 */
1275static void ext4_mb_use_best_found(struct ext4_allocation_context *ac,
1276 struct ext4_buddy *e4b)
1277{
1278 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1279 int ret;
1280
1281 BUG_ON(ac->ac_b_ex.fe_group != e4b->bd_group);
1282 BUG_ON(ac->ac_status == AC_STATUS_FOUND);
1283
1284 ac->ac_b_ex.fe_len = min(ac->ac_b_ex.fe_len, ac->ac_g_ex.fe_len);
1285 ac->ac_b_ex.fe_logical = ac->ac_g_ex.fe_logical;
1286 ret = mb_mark_used(e4b, &ac->ac_b_ex);
1287
1288 /* preallocation can change ac_b_ex, thus we store actually
1289 * allocated blocks for history */
1290 ac->ac_f_ex = ac->ac_b_ex;
1291
1292 ac->ac_status = AC_STATUS_FOUND;
1293 ac->ac_tail = ret & 0xffff;
1294 ac->ac_buddy = ret >> 16;
1295
1296 /* XXXXXXX: SUCH A HORRIBLE **CK */
1297 /*FIXME!! Why ? */
1298 ac->ac_bitmap_page = e4b->bd_bitmap_page;
1299 get_page(ac->ac_bitmap_page);
1300 ac->ac_buddy_page = e4b->bd_buddy_page;
1301 get_page(ac->ac_buddy_page);
1302
1303 /* store last allocated for subsequent stream allocation */
1304 if ((ac->ac_flags & EXT4_MB_HINT_DATA)) {
1305 spin_lock(&sbi->s_md_lock);
1306 sbi->s_mb_last_group = ac->ac_f_ex.fe_group;
1307 sbi->s_mb_last_start = ac->ac_f_ex.fe_start;
1308 spin_unlock(&sbi->s_md_lock);
1309 }
1310}
1311
1312/*
1313 * regular allocator, for general purposes allocation
1314 */
1315
1316static void ext4_mb_check_limits(struct ext4_allocation_context *ac,
1317 struct ext4_buddy *e4b,
1318 int finish_group)
1319{
1320 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1321 struct ext4_free_extent *bex = &ac->ac_b_ex;
1322 struct ext4_free_extent *gex = &ac->ac_g_ex;
1323 struct ext4_free_extent ex;
1324 int max;
1325
1326 /*
1327 * We don't want to scan for a whole year
1328 */
1329 if (ac->ac_found > sbi->s_mb_max_to_scan &&
1330 !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
1331 ac->ac_status = AC_STATUS_BREAK;
1332 return;
1333 }
1334
1335 /*
1336 * Haven't found good chunk so far, let's continue
1337 */
1338 if (bex->fe_len < gex->fe_len)
1339 return;
1340
1341 if ((finish_group || ac->ac_found > sbi->s_mb_min_to_scan)
1342 && bex->fe_group == e4b->bd_group) {
1343 /* recheck chunk's availability - we don't know
1344 * when it was found (within this lock-unlock
1345 * period or not) */
1346 max = mb_find_extent(e4b, 0, bex->fe_start, gex->fe_len, &ex);
1347 if (max >= gex->fe_len) {
1348 ext4_mb_use_best_found(ac, e4b);
1349 return;
1350 }
1351 }
1352}
1353
1354/*
1355 * The routine checks whether found extent is good enough. If it is,
1356 * then the extent gets marked used and flag is set to the context
1357 * to stop scanning. Otherwise, the extent is compared with the
1358 * previous found extent and if new one is better, then it's stored
1359 * in the context. Later, the best found extent will be used, if
1360 * mballoc can't find good enough extent.
1361 *
1362 * FIXME: real allocation policy is to be designed yet!
1363 */
1364static void ext4_mb_measure_extent(struct ext4_allocation_context *ac,
1365 struct ext4_free_extent *ex,
1366 struct ext4_buddy *e4b)
1367{
1368 struct ext4_free_extent *bex = &ac->ac_b_ex;
1369 struct ext4_free_extent *gex = &ac->ac_g_ex;
1370
1371 BUG_ON(ex->fe_len <= 0);
1372 BUG_ON(ex->fe_len >= EXT4_BLOCKS_PER_GROUP(ac->ac_sb));
1373 BUG_ON(ex->fe_start >= EXT4_BLOCKS_PER_GROUP(ac->ac_sb));
1374 BUG_ON(ac->ac_status != AC_STATUS_CONTINUE);
1375
1376 ac->ac_found++;
1377
1378 /*
1379 * The special case - take what you catch first
1380 */
1381 if (unlikely(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
1382 *bex = *ex;
1383 ext4_mb_use_best_found(ac, e4b);
1384 return;
1385 }
1386
1387 /*
1388 * Let's check whether the chuck is good enough
1389 */
1390 if (ex->fe_len == gex->fe_len) {
1391 *bex = *ex;
1392 ext4_mb_use_best_found(ac, e4b);
1393 return;
1394 }
1395
1396 /*
1397 * If this is first found extent, just store it in the context
1398 */
1399 if (bex->fe_len == 0) {
1400 *bex = *ex;
1401 return;
1402 }
1403
1404 /*
1405 * If new found extent is better, store it in the context
1406 */
1407 if (bex->fe_len < gex->fe_len) {
1408 /* if the request isn't satisfied, any found extent
1409 * larger than previous best one is better */
1410 if (ex->fe_len > bex->fe_len)
1411 *bex = *ex;
1412 } else if (ex->fe_len > gex->fe_len) {
1413 /* if the request is satisfied, then we try to find
1414 * an extent that still satisfy the request, but is
1415 * smaller than previous one */
1416 if (ex->fe_len < bex->fe_len)
1417 *bex = *ex;
1418 }
1419
1420 ext4_mb_check_limits(ac, e4b, 0);
1421}
1422
1423static int ext4_mb_try_best_found(struct ext4_allocation_context *ac,
1424 struct ext4_buddy *e4b)
1425{
1426 struct ext4_free_extent ex = ac->ac_b_ex;
1427 ext4_group_t group = ex.fe_group;
1428 int max;
1429 int err;
1430
1431 BUG_ON(ex.fe_len <= 0);
1432 err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);
1433 if (err)
1434 return err;
1435
1436 ext4_lock_group(ac->ac_sb, group);
1437 max = mb_find_extent(e4b, 0, ex.fe_start, ex.fe_len, &ex);
1438
1439 if (max > 0) {
1440 ac->ac_b_ex = ex;
1441 ext4_mb_use_best_found(ac, e4b);
1442 }
1443
1444 ext4_unlock_group(ac->ac_sb, group);
1445 ext4_mb_release_desc(e4b);
1446
1447 return 0;
1448}
1449
1450static int ext4_mb_find_by_goal(struct ext4_allocation_context *ac,
1451 struct ext4_buddy *e4b)
1452{
1453 ext4_group_t group = ac->ac_g_ex.fe_group;
1454 int max;
1455 int err;
1456 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1457 struct ext4_super_block *es = sbi->s_es;
1458 struct ext4_free_extent ex;
1459
1460 if (!(ac->ac_flags & EXT4_MB_HINT_TRY_GOAL))
1461 return 0;
1462
1463 err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);
1464 if (err)
1465 return err;
1466
1467 ext4_lock_group(ac->ac_sb, group);
1468 max = mb_find_extent(e4b, 0, ac->ac_g_ex.fe_start,
1469 ac->ac_g_ex.fe_len, &ex);
1470
1471 if (max >= ac->ac_g_ex.fe_len && ac->ac_g_ex.fe_len == sbi->s_stripe) {
1472 ext4_fsblk_t start;
1473
1474 start = (e4b->bd_group * EXT4_BLOCKS_PER_GROUP(ac->ac_sb)) +
1475 ex.fe_start + le32_to_cpu(es->s_first_data_block);
1476 /* use do_div to get remainder (would be 64-bit modulo) */
1477 if (do_div(start, sbi->s_stripe) == 0) {
1478 ac->ac_found++;
1479 ac->ac_b_ex = ex;
1480 ext4_mb_use_best_found(ac, e4b);
1481 }
1482 } else if (max >= ac->ac_g_ex.fe_len) {
1483 BUG_ON(ex.fe_len <= 0);
1484 BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
1485 BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
1486 ac->ac_found++;
1487 ac->ac_b_ex = ex;
1488 ext4_mb_use_best_found(ac, e4b);
1489 } else if (max > 0 && (ac->ac_flags & EXT4_MB_HINT_MERGE)) {
1490 /* Sometimes, caller may want to merge even small
1491 * number of blocks to an existing extent */
1492 BUG_ON(ex.fe_len <= 0);
1493 BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
1494 BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
1495 ac->ac_found++;
1496 ac->ac_b_ex = ex;
1497 ext4_mb_use_best_found(ac, e4b);
1498 }
1499 ext4_unlock_group(ac->ac_sb, group);
1500 ext4_mb_release_desc(e4b);
1501
1502 return 0;
1503}
1504
1505/*
1506 * The routine scans buddy structures (not bitmap!) from given order
1507 * to max order and tries to find big enough chunk to satisfy the req
1508 */
1509static void ext4_mb_simple_scan_group(struct ext4_allocation_context *ac,
1510 struct ext4_buddy *e4b)
1511{
1512 struct super_block *sb = ac->ac_sb;
1513 struct ext4_group_info *grp = e4b->bd_info;
1514 void *buddy;
1515 int i;
1516 int k;
1517 int max;
1518
1519 BUG_ON(ac->ac_2order <= 0);
1520 for (i = ac->ac_2order; i <= sb->s_blocksize_bits + 1; i++) {
1521 if (grp->bb_counters[i] == 0)
1522 continue;
1523
1524 buddy = mb_find_buddy(e4b, i, &max);
1525 BUG_ON(buddy == NULL);
1526
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -05001527 k = mb_find_next_zero_bit(buddy, max, 0);
Alex Tomasc9de5602008-01-29 00:19:52 -05001528 BUG_ON(k >= max);
1529
1530 ac->ac_found++;
1531
1532 ac->ac_b_ex.fe_len = 1 << i;
1533 ac->ac_b_ex.fe_start = k << i;
1534 ac->ac_b_ex.fe_group = e4b->bd_group;
1535
1536 ext4_mb_use_best_found(ac, e4b);
1537
1538 BUG_ON(ac->ac_b_ex.fe_len != ac->ac_g_ex.fe_len);
1539
1540 if (EXT4_SB(sb)->s_mb_stats)
1541 atomic_inc(&EXT4_SB(sb)->s_bal_2orders);
1542
1543 break;
1544 }
1545}
1546
1547/*
1548 * The routine scans the group and measures all found extents.
1549 * In order to optimize scanning, caller must pass number of
1550 * free blocks in the group, so the routine can know upper limit.
1551 */
1552static void ext4_mb_complex_scan_group(struct ext4_allocation_context *ac,
1553 struct ext4_buddy *e4b)
1554{
1555 struct super_block *sb = ac->ac_sb;
1556 void *bitmap = EXT4_MB_BITMAP(e4b);
1557 struct ext4_free_extent ex;
1558 int i;
1559 int free;
1560
1561 free = e4b->bd_info->bb_free;
1562 BUG_ON(free <= 0);
1563
1564 i = e4b->bd_info->bb_first_free;
1565
1566 while (free && ac->ac_status == AC_STATUS_CONTINUE) {
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -05001567 i = mb_find_next_zero_bit(bitmap,
Alex Tomasc9de5602008-01-29 00:19:52 -05001568 EXT4_BLOCKS_PER_GROUP(sb), i);
1569 if (i >= EXT4_BLOCKS_PER_GROUP(sb)) {
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05001570 /*
Aneesh Kumar K.Ve56eb652008-02-15 13:48:21 -05001571 * IF we have corrupt bitmap, we won't find any
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05001572 * free blocks even though group info says we
1573 * we have free blocks
1574 */
Harvey Harrison46e665e2008-04-17 10:38:59 -04001575 ext4_error(sb, __func__, "%d free blocks as per "
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05001576 "group info. But bitmap says 0\n",
1577 free);
Alex Tomasc9de5602008-01-29 00:19:52 -05001578 break;
1579 }
1580
1581 mb_find_extent(e4b, 0, i, ac->ac_g_ex.fe_len, &ex);
1582 BUG_ON(ex.fe_len <= 0);
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05001583 if (free < ex.fe_len) {
Harvey Harrison46e665e2008-04-17 10:38:59 -04001584 ext4_error(sb, __func__, "%d free blocks as per "
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05001585 "group info. But got %d blocks\n",
1586 free, ex.fe_len);
Aneesh Kumar K.Ve56eb652008-02-15 13:48:21 -05001587 /*
1588 * The number of free blocks differs. This mostly
1589 * indicate that the bitmap is corrupt. So exit
1590 * without claiming the space.
1591 */
1592 break;
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05001593 }
Alex Tomasc9de5602008-01-29 00:19:52 -05001594
1595 ext4_mb_measure_extent(ac, &ex, e4b);
1596
1597 i += ex.fe_len;
1598 free -= ex.fe_len;
1599 }
1600
1601 ext4_mb_check_limits(ac, e4b, 1);
1602}
1603
1604/*
1605 * This is a special case for storages like raid5
1606 * we try to find stripe-aligned chunks for stripe-size requests
1607 * XXX should do so at least for multiples of stripe size as well
1608 */
1609static void ext4_mb_scan_aligned(struct ext4_allocation_context *ac,
1610 struct ext4_buddy *e4b)
1611{
1612 struct super_block *sb = ac->ac_sb;
1613 struct ext4_sb_info *sbi = EXT4_SB(sb);
1614 void *bitmap = EXT4_MB_BITMAP(e4b);
1615 struct ext4_free_extent ex;
1616 ext4_fsblk_t first_group_block;
1617 ext4_fsblk_t a;
1618 ext4_grpblk_t i;
1619 int max;
1620
1621 BUG_ON(sbi->s_stripe == 0);
1622
1623 /* find first stripe-aligned block in group */
1624 first_group_block = e4b->bd_group * EXT4_BLOCKS_PER_GROUP(sb)
1625 + le32_to_cpu(sbi->s_es->s_first_data_block);
1626 a = first_group_block + sbi->s_stripe - 1;
1627 do_div(a, sbi->s_stripe);
1628 i = (a * sbi->s_stripe) - first_group_block;
1629
1630 while (i < EXT4_BLOCKS_PER_GROUP(sb)) {
1631 if (!mb_test_bit(i, bitmap)) {
1632 max = mb_find_extent(e4b, 0, i, sbi->s_stripe, &ex);
1633 if (max >= sbi->s_stripe) {
1634 ac->ac_found++;
1635 ac->ac_b_ex = ex;
1636 ext4_mb_use_best_found(ac, e4b);
1637 break;
1638 }
1639 }
1640 i += sbi->s_stripe;
1641 }
1642}
1643
1644static int ext4_mb_good_group(struct ext4_allocation_context *ac,
1645 ext4_group_t group, int cr)
1646{
1647 unsigned free, fragments;
1648 unsigned i, bits;
1649 struct ext4_group_desc *desc;
1650 struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);
1651
1652 BUG_ON(cr < 0 || cr >= 4);
1653 BUG_ON(EXT4_MB_GRP_NEED_INIT(grp));
1654
1655 free = grp->bb_free;
1656 fragments = grp->bb_fragments;
1657 if (free == 0)
1658 return 0;
1659 if (fragments == 0)
1660 return 0;
1661
1662 switch (cr) {
1663 case 0:
1664 BUG_ON(ac->ac_2order == 0);
1665 /* If this group is uninitialized, skip it initially */
1666 desc = ext4_get_group_desc(ac->ac_sb, group, NULL);
1667 if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))
1668 return 0;
1669
1670 bits = ac->ac_sb->s_blocksize_bits + 1;
1671 for (i = ac->ac_2order; i <= bits; i++)
1672 if (grp->bb_counters[i] > 0)
1673 return 1;
1674 break;
1675 case 1:
1676 if ((free / fragments) >= ac->ac_g_ex.fe_len)
1677 return 1;
1678 break;
1679 case 2:
1680 if (free >= ac->ac_g_ex.fe_len)
1681 return 1;
1682 break;
1683 case 3:
1684 return 1;
1685 default:
1686 BUG();
1687 }
1688
1689 return 0;
1690}
1691
Eric Sandeen4ddfef72008-04-29 08:11:12 -04001692static noinline_for_stack int
1693ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
Alex Tomasc9de5602008-01-29 00:19:52 -05001694{
1695 ext4_group_t group;
1696 ext4_group_t i;
1697 int cr;
1698 int err = 0;
1699 int bsbits;
1700 struct ext4_sb_info *sbi;
1701 struct super_block *sb;
1702 struct ext4_buddy e4b;
1703 loff_t size, isize;
1704
1705 sb = ac->ac_sb;
1706 sbi = EXT4_SB(sb);
1707 BUG_ON(ac->ac_status == AC_STATUS_FOUND);
1708
1709 /* first, try the goal */
1710 err = ext4_mb_find_by_goal(ac, &e4b);
1711 if (err || ac->ac_status == AC_STATUS_FOUND)
1712 goto out;
1713
1714 if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
1715 goto out;
1716
1717 /*
1718 * ac->ac2_order is set only if the fe_len is a power of 2
1719 * if ac2_order is set we also set criteria to 0 so that we
1720 * try exact allocation using buddy.
1721 */
1722 i = fls(ac->ac_g_ex.fe_len);
1723 ac->ac_2order = 0;
1724 /*
1725 * We search using buddy data only if the order of the request
1726 * is greater than equal to the sbi_s_mb_order2_reqs
1727 * You can tune it via /proc/fs/ext4/<partition>/order2_req
1728 */
1729 if (i >= sbi->s_mb_order2_reqs) {
1730 /*
1731 * This should tell if fe_len is exactly power of 2
1732 */
1733 if ((ac->ac_g_ex.fe_len & (~(1 << (i - 1)))) == 0)
1734 ac->ac_2order = i - 1;
1735 }
1736
1737 bsbits = ac->ac_sb->s_blocksize_bits;
1738 /* if stream allocation is enabled, use global goal */
1739 size = ac->ac_o_ex.fe_logical + ac->ac_o_ex.fe_len;
1740 isize = i_size_read(ac->ac_inode) >> bsbits;
1741 if (size < isize)
1742 size = isize;
1743
1744 if (size < sbi->s_mb_stream_request &&
1745 (ac->ac_flags & EXT4_MB_HINT_DATA)) {
1746 /* TBD: may be hot point */
1747 spin_lock(&sbi->s_md_lock);
1748 ac->ac_g_ex.fe_group = sbi->s_mb_last_group;
1749 ac->ac_g_ex.fe_start = sbi->s_mb_last_start;
1750 spin_unlock(&sbi->s_md_lock);
1751 }
Alex Tomasc9de5602008-01-29 00:19:52 -05001752 /* Let's just scan groups to find more-less suitable blocks */
1753 cr = ac->ac_2order ? 0 : 1;
1754 /*
1755 * cr == 0 try to get exact allocation,
1756 * cr == 3 try to get anything
1757 */
1758repeat:
1759 for (; cr < 4 && ac->ac_status == AC_STATUS_CONTINUE; cr++) {
1760 ac->ac_criteria = cr;
Aneesh Kumar K.Ved8f9c72008-07-11 19:27:31 -04001761 /*
1762 * searching for the right group start
1763 * from the goal value specified
1764 */
1765 group = ac->ac_g_ex.fe_group;
1766
Alex Tomasc9de5602008-01-29 00:19:52 -05001767 for (i = 0; i < EXT4_SB(sb)->s_groups_count; group++, i++) {
1768 struct ext4_group_info *grp;
1769 struct ext4_group_desc *desc;
1770
1771 if (group == EXT4_SB(sb)->s_groups_count)
1772 group = 0;
1773
1774 /* quick check to skip empty groups */
1775 grp = ext4_get_group_info(ac->ac_sb, group);
1776 if (grp->bb_free == 0)
1777 continue;
1778
1779 /*
1780 * if the group is already init we check whether it is
1781 * a good group and if not we don't load the buddy
1782 */
1783 if (EXT4_MB_GRP_NEED_INIT(grp)) {
1784 /*
1785 * we need full data about the group
1786 * to make a good selection
1787 */
1788 err = ext4_mb_load_buddy(sb, group, &e4b);
1789 if (err)
1790 goto out;
1791 ext4_mb_release_desc(&e4b);
1792 }
1793
1794 /*
1795 * If the particular group doesn't satisfy our
1796 * criteria we continue with the next group
1797 */
1798 if (!ext4_mb_good_group(ac, group, cr))
1799 continue;
1800
1801 err = ext4_mb_load_buddy(sb, group, &e4b);
1802 if (err)
1803 goto out;
1804
1805 ext4_lock_group(sb, group);
1806 if (!ext4_mb_good_group(ac, group, cr)) {
1807 /* someone did allocation from this group */
1808 ext4_unlock_group(sb, group);
1809 ext4_mb_release_desc(&e4b);
1810 continue;
1811 }
1812
1813 ac->ac_groups_scanned++;
1814 desc = ext4_get_group_desc(sb, group, NULL);
1815 if (cr == 0 || (desc->bg_flags &
1816 cpu_to_le16(EXT4_BG_BLOCK_UNINIT) &&
1817 ac->ac_2order != 0))
1818 ext4_mb_simple_scan_group(ac, &e4b);
1819 else if (cr == 1 &&
1820 ac->ac_g_ex.fe_len == sbi->s_stripe)
1821 ext4_mb_scan_aligned(ac, &e4b);
1822 else
1823 ext4_mb_complex_scan_group(ac, &e4b);
1824
1825 ext4_unlock_group(sb, group);
1826 ext4_mb_release_desc(&e4b);
1827
1828 if (ac->ac_status != AC_STATUS_CONTINUE)
1829 break;
1830 }
1831 }
1832
1833 if (ac->ac_b_ex.fe_len > 0 && ac->ac_status != AC_STATUS_FOUND &&
1834 !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
1835 /*
1836 * We've been searching too long. Let's try to allocate
1837 * the best chunk we've found so far
1838 */
1839
1840 ext4_mb_try_best_found(ac, &e4b);
1841 if (ac->ac_status != AC_STATUS_FOUND) {
1842 /*
1843 * Someone more lucky has already allocated it.
1844 * The only thing we can do is just take first
1845 * found block(s)
1846 printk(KERN_DEBUG "EXT4-fs: someone won our chunk\n");
1847 */
1848 ac->ac_b_ex.fe_group = 0;
1849 ac->ac_b_ex.fe_start = 0;
1850 ac->ac_b_ex.fe_len = 0;
1851 ac->ac_status = AC_STATUS_CONTINUE;
1852 ac->ac_flags |= EXT4_MB_HINT_FIRST;
1853 cr = 3;
1854 atomic_inc(&sbi->s_mb_lost_chunks);
1855 goto repeat;
1856 }
1857 }
1858out:
1859 return err;
1860}
1861
1862#ifdef EXT4_MB_HISTORY
1863struct ext4_mb_proc_session {
1864 struct ext4_mb_history *history;
1865 struct super_block *sb;
1866 int start;
1867 int max;
1868};
1869
1870static void *ext4_mb_history_skip_empty(struct ext4_mb_proc_session *s,
1871 struct ext4_mb_history *hs,
1872 int first)
1873{
1874 if (hs == s->history + s->max)
1875 hs = s->history;
1876 if (!first && hs == s->history + s->start)
1877 return NULL;
1878 while (hs->orig.fe_len == 0) {
1879 hs++;
1880 if (hs == s->history + s->max)
1881 hs = s->history;
1882 if (hs == s->history + s->start)
1883 return NULL;
1884 }
1885 return hs;
1886}
1887
1888static void *ext4_mb_seq_history_start(struct seq_file *seq, loff_t *pos)
1889{
1890 struct ext4_mb_proc_session *s = seq->private;
1891 struct ext4_mb_history *hs;
1892 int l = *pos;
1893
1894 if (l == 0)
1895 return SEQ_START_TOKEN;
1896 hs = ext4_mb_history_skip_empty(s, s->history + s->start, 1);
1897 if (!hs)
1898 return NULL;
1899 while (--l && (hs = ext4_mb_history_skip_empty(s, ++hs, 0)) != NULL);
1900 return hs;
1901}
1902
1903static void *ext4_mb_seq_history_next(struct seq_file *seq, void *v,
1904 loff_t *pos)
1905{
1906 struct ext4_mb_proc_session *s = seq->private;
1907 struct ext4_mb_history *hs = v;
1908
1909 ++*pos;
1910 if (v == SEQ_START_TOKEN)
1911 return ext4_mb_history_skip_empty(s, s->history + s->start, 1);
1912 else
1913 return ext4_mb_history_skip_empty(s, ++hs, 0);
1914}
1915
1916static int ext4_mb_seq_history_show(struct seq_file *seq, void *v)
1917{
1918 char buf[25], buf2[25], buf3[25], *fmt;
1919 struct ext4_mb_history *hs = v;
1920
1921 if (v == SEQ_START_TOKEN) {
1922 seq_printf(seq, "%-5s %-8s %-23s %-23s %-23s %-5s "
1923 "%-5s %-2s %-5s %-5s %-5s %-6s\n",
1924 "pid", "inode", "original", "goal", "result", "found",
1925 "grps", "cr", "flags", "merge", "tail", "broken");
1926 return 0;
1927 }
1928
1929 if (hs->op == EXT4_MB_HISTORY_ALLOC) {
1930 fmt = "%-5u %-8u %-23s %-23s %-23s %-5u %-5u %-2u "
1931 "%-5u %-5s %-5u %-6u\n";
1932 sprintf(buf2, "%lu/%d/%u@%u", hs->result.fe_group,
1933 hs->result.fe_start, hs->result.fe_len,
1934 hs->result.fe_logical);
1935 sprintf(buf, "%lu/%d/%u@%u", hs->orig.fe_group,
1936 hs->orig.fe_start, hs->orig.fe_len,
1937 hs->orig.fe_logical);
1938 sprintf(buf3, "%lu/%d/%u@%u", hs->goal.fe_group,
1939 hs->goal.fe_start, hs->goal.fe_len,
1940 hs->goal.fe_logical);
1941 seq_printf(seq, fmt, hs->pid, hs->ino, buf, buf3, buf2,
1942 hs->found, hs->groups, hs->cr, hs->flags,
1943 hs->merged ? "M" : "", hs->tail,
1944 hs->buddy ? 1 << hs->buddy : 0);
1945 } else if (hs->op == EXT4_MB_HISTORY_PREALLOC) {
1946 fmt = "%-5u %-8u %-23s %-23s %-23s\n";
1947 sprintf(buf2, "%lu/%d/%u@%u", hs->result.fe_group,
1948 hs->result.fe_start, hs->result.fe_len,
1949 hs->result.fe_logical);
1950 sprintf(buf, "%lu/%d/%u@%u", hs->orig.fe_group,
1951 hs->orig.fe_start, hs->orig.fe_len,
1952 hs->orig.fe_logical);
1953 seq_printf(seq, fmt, hs->pid, hs->ino, buf, "", buf2);
1954 } else if (hs->op == EXT4_MB_HISTORY_DISCARD) {
1955 sprintf(buf2, "%lu/%d/%u", hs->result.fe_group,
1956 hs->result.fe_start, hs->result.fe_len);
1957 seq_printf(seq, "%-5u %-8u %-23s discard\n",
1958 hs->pid, hs->ino, buf2);
1959 } else if (hs->op == EXT4_MB_HISTORY_FREE) {
1960 sprintf(buf2, "%lu/%d/%u", hs->result.fe_group,
1961 hs->result.fe_start, hs->result.fe_len);
1962 seq_printf(seq, "%-5u %-8u %-23s free\n",
1963 hs->pid, hs->ino, buf2);
1964 }
1965 return 0;
1966}
1967
1968static void ext4_mb_seq_history_stop(struct seq_file *seq, void *v)
1969{
1970}
1971
1972static struct seq_operations ext4_mb_seq_history_ops = {
1973 .start = ext4_mb_seq_history_start,
1974 .next = ext4_mb_seq_history_next,
1975 .stop = ext4_mb_seq_history_stop,
1976 .show = ext4_mb_seq_history_show,
1977};
1978
1979static int ext4_mb_seq_history_open(struct inode *inode, struct file *file)
1980{
1981 struct super_block *sb = PDE(inode)->data;
1982 struct ext4_sb_info *sbi = EXT4_SB(sb);
1983 struct ext4_mb_proc_session *s;
1984 int rc;
1985 int size;
1986
Shen Feng74767c52008-07-11 19:27:31 -04001987 if (unlikely(sbi->s_mb_history == NULL))
1988 return -ENOMEM;
Alex Tomasc9de5602008-01-29 00:19:52 -05001989 s = kmalloc(sizeof(*s), GFP_KERNEL);
1990 if (s == NULL)
1991 return -ENOMEM;
1992 s->sb = sb;
1993 size = sizeof(struct ext4_mb_history) * sbi->s_mb_history_max;
1994 s->history = kmalloc(size, GFP_KERNEL);
1995 if (s->history == NULL) {
1996 kfree(s);
1997 return -ENOMEM;
1998 }
1999
2000 spin_lock(&sbi->s_mb_history_lock);
2001 memcpy(s->history, sbi->s_mb_history, size);
2002 s->max = sbi->s_mb_history_max;
2003 s->start = sbi->s_mb_history_cur % s->max;
2004 spin_unlock(&sbi->s_mb_history_lock);
2005
2006 rc = seq_open(file, &ext4_mb_seq_history_ops);
2007 if (rc == 0) {
2008 struct seq_file *m = (struct seq_file *)file->private_data;
2009 m->private = s;
2010 } else {
2011 kfree(s->history);
2012 kfree(s);
2013 }
2014 return rc;
2015
2016}
2017
2018static int ext4_mb_seq_history_release(struct inode *inode, struct file *file)
2019{
2020 struct seq_file *seq = (struct seq_file *)file->private_data;
2021 struct ext4_mb_proc_session *s = seq->private;
2022 kfree(s->history);
2023 kfree(s);
2024 return seq_release(inode, file);
2025}
2026
2027static ssize_t ext4_mb_seq_history_write(struct file *file,
2028 const char __user *buffer,
2029 size_t count, loff_t *ppos)
2030{
2031 struct seq_file *seq = (struct seq_file *)file->private_data;
2032 struct ext4_mb_proc_session *s = seq->private;
2033 struct super_block *sb = s->sb;
2034 char str[32];
2035 int value;
2036
2037 if (count >= sizeof(str)) {
2038 printk(KERN_ERR "EXT4-fs: %s string too long, max %u bytes\n",
2039 "mb_history", (int)sizeof(str));
2040 return -EOVERFLOW;
2041 }
2042
2043 if (copy_from_user(str, buffer, count))
2044 return -EFAULT;
2045
2046 value = simple_strtol(str, NULL, 0);
2047 if (value < 0)
2048 return -ERANGE;
2049 EXT4_SB(sb)->s_mb_history_filter = value;
2050
2051 return count;
2052}
2053
2054static struct file_operations ext4_mb_seq_history_fops = {
2055 .owner = THIS_MODULE,
2056 .open = ext4_mb_seq_history_open,
2057 .read = seq_read,
2058 .write = ext4_mb_seq_history_write,
2059 .llseek = seq_lseek,
2060 .release = ext4_mb_seq_history_release,
2061};
2062
2063static void *ext4_mb_seq_groups_start(struct seq_file *seq, loff_t *pos)
2064{
2065 struct super_block *sb = seq->private;
2066 struct ext4_sb_info *sbi = EXT4_SB(sb);
2067 ext4_group_t group;
2068
2069 if (*pos < 0 || *pos >= sbi->s_groups_count)
2070 return NULL;
2071
2072 group = *pos + 1;
2073 return (void *) group;
2074}
2075
2076static void *ext4_mb_seq_groups_next(struct seq_file *seq, void *v, loff_t *pos)
2077{
2078 struct super_block *sb = seq->private;
2079 struct ext4_sb_info *sbi = EXT4_SB(sb);
2080 ext4_group_t group;
2081
2082 ++*pos;
2083 if (*pos < 0 || *pos >= sbi->s_groups_count)
2084 return NULL;
2085 group = *pos + 1;
2086 return (void *) group;;
2087}
2088
2089static int ext4_mb_seq_groups_show(struct seq_file *seq, void *v)
2090{
2091 struct super_block *sb = seq->private;
2092 long group = (long) v;
2093 int i;
2094 int err;
2095 struct ext4_buddy e4b;
2096 struct sg {
2097 struct ext4_group_info info;
2098 unsigned short counters[16];
2099 } sg;
2100
2101 group--;
2102 if (group == 0)
2103 seq_printf(seq, "#%-5s: %-5s %-5s %-5s "
2104 "[ %-5s %-5s %-5s %-5s %-5s %-5s %-5s "
2105 "%-5s %-5s %-5s %-5s %-5s %-5s %-5s ]\n",
2106 "group", "free", "frags", "first",
2107 "2^0", "2^1", "2^2", "2^3", "2^4", "2^5", "2^6",
2108 "2^7", "2^8", "2^9", "2^10", "2^11", "2^12", "2^13");
2109
2110 i = (sb->s_blocksize_bits + 2) * sizeof(sg.info.bb_counters[0]) +
2111 sizeof(struct ext4_group_info);
2112 err = ext4_mb_load_buddy(sb, group, &e4b);
2113 if (err) {
2114 seq_printf(seq, "#%-5lu: I/O error\n", group);
2115 return 0;
2116 }
2117 ext4_lock_group(sb, group);
2118 memcpy(&sg, ext4_get_group_info(sb, group), i);
2119 ext4_unlock_group(sb, group);
2120 ext4_mb_release_desc(&e4b);
2121
2122 seq_printf(seq, "#%-5lu: %-5u %-5u %-5u [", group, sg.info.bb_free,
2123 sg.info.bb_fragments, sg.info.bb_first_free);
2124 for (i = 0; i <= 13; i++)
2125 seq_printf(seq, " %-5u", i <= sb->s_blocksize_bits + 1 ?
2126 sg.info.bb_counters[i] : 0);
2127 seq_printf(seq, " ]\n");
2128
2129 return 0;
2130}
2131
2132static void ext4_mb_seq_groups_stop(struct seq_file *seq, void *v)
2133{
2134}
2135
2136static struct seq_operations ext4_mb_seq_groups_ops = {
2137 .start = ext4_mb_seq_groups_start,
2138 .next = ext4_mb_seq_groups_next,
2139 .stop = ext4_mb_seq_groups_stop,
2140 .show = ext4_mb_seq_groups_show,
2141};
2142
2143static int ext4_mb_seq_groups_open(struct inode *inode, struct file *file)
2144{
2145 struct super_block *sb = PDE(inode)->data;
2146 int rc;
2147
2148 rc = seq_open(file, &ext4_mb_seq_groups_ops);
2149 if (rc == 0) {
2150 struct seq_file *m = (struct seq_file *)file->private_data;
2151 m->private = sb;
2152 }
2153 return rc;
2154
2155}
2156
2157static struct file_operations ext4_mb_seq_groups_fops = {
2158 .owner = THIS_MODULE,
2159 .open = ext4_mb_seq_groups_open,
2160 .read = seq_read,
2161 .llseek = seq_lseek,
2162 .release = seq_release,
2163};
2164
2165static void ext4_mb_history_release(struct super_block *sb)
2166{
2167 struct ext4_sb_info *sbi = EXT4_SB(sb);
2168
2169 remove_proc_entry("mb_groups", sbi->s_mb_proc);
2170 remove_proc_entry("mb_history", sbi->s_mb_proc);
2171
2172 kfree(sbi->s_mb_history);
2173}
2174
2175static void ext4_mb_history_init(struct super_block *sb)
2176{
2177 struct ext4_sb_info *sbi = EXT4_SB(sb);
2178 int i;
2179
2180 if (sbi->s_mb_proc != NULL) {
Denis V. Lunev46fe74f2008-04-29 01:02:08 -07002181 proc_create_data("mb_history", S_IRUGO, sbi->s_mb_proc,
2182 &ext4_mb_seq_history_fops, sb);
2183 proc_create_data("mb_groups", S_IRUGO, sbi->s_mb_proc,
2184 &ext4_mb_seq_groups_fops, sb);
Alex Tomasc9de5602008-01-29 00:19:52 -05002185 }
2186
2187 sbi->s_mb_history_max = 1000;
2188 sbi->s_mb_history_cur = 0;
2189 spin_lock_init(&sbi->s_mb_history_lock);
2190 i = sbi->s_mb_history_max * sizeof(struct ext4_mb_history);
Shen Feng74767c52008-07-11 19:27:31 -04002191 sbi->s_mb_history = kzalloc(i, GFP_KERNEL);
Alex Tomasc9de5602008-01-29 00:19:52 -05002192 /* if we can't allocate history, then we simple won't use it */
2193}
2194
Eric Sandeen4ddfef72008-04-29 08:11:12 -04002195static noinline_for_stack void
2196ext4_mb_store_history(struct ext4_allocation_context *ac)
Alex Tomasc9de5602008-01-29 00:19:52 -05002197{
2198 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
2199 struct ext4_mb_history h;
2200
2201 if (unlikely(sbi->s_mb_history == NULL))
2202 return;
2203
2204 if (!(ac->ac_op & sbi->s_mb_history_filter))
2205 return;
2206
2207 h.op = ac->ac_op;
2208 h.pid = current->pid;
2209 h.ino = ac->ac_inode ? ac->ac_inode->i_ino : 0;
2210 h.orig = ac->ac_o_ex;
2211 h.result = ac->ac_b_ex;
2212 h.flags = ac->ac_flags;
2213 h.found = ac->ac_found;
2214 h.groups = ac->ac_groups_scanned;
2215 h.cr = ac->ac_criteria;
2216 h.tail = ac->ac_tail;
2217 h.buddy = ac->ac_buddy;
2218 h.merged = 0;
2219 if (ac->ac_op == EXT4_MB_HISTORY_ALLOC) {
2220 if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&
2221 ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)
2222 h.merged = 1;
2223 h.goal = ac->ac_g_ex;
2224 h.result = ac->ac_f_ex;
2225 }
2226
2227 spin_lock(&sbi->s_mb_history_lock);
2228 memcpy(sbi->s_mb_history + sbi->s_mb_history_cur, &h, sizeof(h));
2229 if (++sbi->s_mb_history_cur >= sbi->s_mb_history_max)
2230 sbi->s_mb_history_cur = 0;
2231 spin_unlock(&sbi->s_mb_history_lock);
2232}
2233
2234#else
2235#define ext4_mb_history_release(sb)
2236#define ext4_mb_history_init(sb)
2237#endif
2238
2239static int ext4_mb_init_backend(struct super_block *sb)
2240{
2241 ext4_group_t i;
2242 int j, len, metalen;
2243 struct ext4_sb_info *sbi = EXT4_SB(sb);
2244 int num_meta_group_infos =
2245 (sbi->s_groups_count + EXT4_DESC_PER_BLOCK(sb) - 1) >>
2246 EXT4_DESC_PER_BLOCK_BITS(sb);
2247 struct ext4_group_info **meta_group_info;
2248
2249 /* An 8TB filesystem with 64-bit pointers requires a 4096 byte
2250 * kmalloc. A 128kb malloc should suffice for a 256TB filesystem.
2251 * So a two level scheme suffices for now. */
2252 sbi->s_group_info = kmalloc(sizeof(*sbi->s_group_info) *
2253 num_meta_group_infos, GFP_KERNEL);
2254 if (sbi->s_group_info == NULL) {
2255 printk(KERN_ERR "EXT4-fs: can't allocate buddy meta group\n");
2256 return -ENOMEM;
2257 }
2258 sbi->s_buddy_cache = new_inode(sb);
2259 if (sbi->s_buddy_cache == NULL) {
2260 printk(KERN_ERR "EXT4-fs: can't get new inode\n");
2261 goto err_freesgi;
2262 }
2263 EXT4_I(sbi->s_buddy_cache)->i_disksize = 0;
2264
2265 metalen = sizeof(*meta_group_info) << EXT4_DESC_PER_BLOCK_BITS(sb);
2266 for (i = 0; i < num_meta_group_infos; i++) {
2267 if ((i + 1) == num_meta_group_infos)
2268 metalen = sizeof(*meta_group_info) *
2269 (sbi->s_groups_count -
2270 (i << EXT4_DESC_PER_BLOCK_BITS(sb)));
2271 meta_group_info = kmalloc(metalen, GFP_KERNEL);
2272 if (meta_group_info == NULL) {
2273 printk(KERN_ERR "EXT4-fs: can't allocate mem for a "
2274 "buddy group\n");
2275 goto err_freemeta;
2276 }
2277 sbi->s_group_info[i] = meta_group_info;
2278 }
2279
2280 /*
2281 * calculate needed size. if change bb_counters size,
2282 * don't forget about ext4_mb_generate_buddy()
2283 */
2284 len = sizeof(struct ext4_group_info);
2285 len += sizeof(unsigned short) * (sb->s_blocksize_bits + 2);
2286 for (i = 0; i < sbi->s_groups_count; i++) {
2287 struct ext4_group_desc *desc;
2288
2289 meta_group_info =
2290 sbi->s_group_info[i >> EXT4_DESC_PER_BLOCK_BITS(sb)];
2291 j = i & (EXT4_DESC_PER_BLOCK(sb) - 1);
2292
2293 meta_group_info[j] = kzalloc(len, GFP_KERNEL);
2294 if (meta_group_info[j] == NULL) {
2295 printk(KERN_ERR "EXT4-fs: can't allocate buddy mem\n");
Alex Tomasc9de5602008-01-29 00:19:52 -05002296 goto err_freebuddy;
2297 }
2298 desc = ext4_get_group_desc(sb, i, NULL);
2299 if (desc == NULL) {
2300 printk(KERN_ERR
2301 "EXT4-fs: can't read descriptor %lu\n", i);
Roel Kluinf1fa3342008-04-29 22:01:15 -04002302 i++;
Alex Tomasc9de5602008-01-29 00:19:52 -05002303 goto err_freebuddy;
2304 }
Alex Tomasc9de5602008-01-29 00:19:52 -05002305 set_bit(EXT4_GROUP_INFO_NEED_INIT_BIT,
2306 &(meta_group_info[j]->bb_state));
2307
2308 /*
2309 * initialize bb_free to be able to skip
2310 * empty groups without initialization
2311 */
2312 if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
2313 meta_group_info[j]->bb_free =
2314 ext4_free_blocks_after_init(sb, i, desc);
2315 } else {
2316 meta_group_info[j]->bb_free =
2317 le16_to_cpu(desc->bg_free_blocks_count);
2318 }
2319
2320 INIT_LIST_HEAD(&meta_group_info[j]->bb_prealloc_list);
2321
2322#ifdef DOUBLE_CHECK
2323 {
2324 struct buffer_head *bh;
2325 meta_group_info[j]->bb_bitmap =
2326 kmalloc(sb->s_blocksize, GFP_KERNEL);
2327 BUG_ON(meta_group_info[j]->bb_bitmap == NULL);
Theodore Ts'o574ca172008-07-11 19:27:31 -04002328 bh = ext4_read_block_bitmap(sb, i);
Alex Tomasc9de5602008-01-29 00:19:52 -05002329 BUG_ON(bh == NULL);
2330 memcpy(meta_group_info[j]->bb_bitmap, bh->b_data,
2331 sb->s_blocksize);
2332 put_bh(bh);
2333 }
2334#endif
2335
2336 }
2337
2338 return 0;
2339
2340err_freebuddy:
Roel Kluinf1fa3342008-04-29 22:01:15 -04002341 while (i-- > 0)
Alex Tomasc9de5602008-01-29 00:19:52 -05002342 kfree(ext4_get_group_info(sb, i));
Alex Tomasc9de5602008-01-29 00:19:52 -05002343 i = num_meta_group_infos;
2344err_freemeta:
Roel Kluinf1fa3342008-04-29 22:01:15 -04002345 while (i-- > 0)
Alex Tomasc9de5602008-01-29 00:19:52 -05002346 kfree(sbi->s_group_info[i]);
2347 iput(sbi->s_buddy_cache);
2348err_freesgi:
2349 kfree(sbi->s_group_info);
2350 return -ENOMEM;
2351}
2352
2353int ext4_mb_init(struct super_block *sb, int needs_recovery)
2354{
2355 struct ext4_sb_info *sbi = EXT4_SB(sb);
2356 unsigned i;
2357 unsigned offset;
2358 unsigned max;
Shen Feng74767c52008-07-11 19:27:31 -04002359 int ret;
Alex Tomasc9de5602008-01-29 00:19:52 -05002360
2361 if (!test_opt(sb, MBALLOC))
2362 return 0;
2363
2364 i = (sb->s_blocksize_bits + 2) * sizeof(unsigned short);
2365
2366 sbi->s_mb_offsets = kmalloc(i, GFP_KERNEL);
2367 if (sbi->s_mb_offsets == NULL) {
2368 clear_opt(sbi->s_mount_opt, MBALLOC);
2369 return -ENOMEM;
2370 }
2371 sbi->s_mb_maxs = kmalloc(i, GFP_KERNEL);
2372 if (sbi->s_mb_maxs == NULL) {
2373 clear_opt(sbi->s_mount_opt, MBALLOC);
2374 kfree(sbi->s_mb_maxs);
2375 return -ENOMEM;
2376 }
2377
2378 /* order 0 is regular bitmap */
2379 sbi->s_mb_maxs[0] = sb->s_blocksize << 3;
2380 sbi->s_mb_offsets[0] = 0;
2381
2382 i = 1;
2383 offset = 0;
2384 max = sb->s_blocksize << 2;
2385 do {
2386 sbi->s_mb_offsets[i] = offset;
2387 sbi->s_mb_maxs[i] = max;
2388 offset += 1 << (sb->s_blocksize_bits - i);
2389 max = max >> 1;
2390 i++;
2391 } while (i <= sb->s_blocksize_bits + 1);
2392
2393 /* init file for buddy data */
Shen Feng74767c52008-07-11 19:27:31 -04002394 ret = ext4_mb_init_backend(sb);
2395 if (ret != 0) {
Alex Tomasc9de5602008-01-29 00:19:52 -05002396 clear_opt(sbi->s_mount_opt, MBALLOC);
2397 kfree(sbi->s_mb_offsets);
2398 kfree(sbi->s_mb_maxs);
Shen Feng74767c52008-07-11 19:27:31 -04002399 return ret;
Alex Tomasc9de5602008-01-29 00:19:52 -05002400 }
2401
2402 spin_lock_init(&sbi->s_md_lock);
2403 INIT_LIST_HEAD(&sbi->s_active_transaction);
2404 INIT_LIST_HEAD(&sbi->s_closed_transaction);
2405 INIT_LIST_HEAD(&sbi->s_committed_transaction);
2406 spin_lock_init(&sbi->s_bal_lock);
2407
2408 sbi->s_mb_max_to_scan = MB_DEFAULT_MAX_TO_SCAN;
2409 sbi->s_mb_min_to_scan = MB_DEFAULT_MIN_TO_SCAN;
2410 sbi->s_mb_stats = MB_DEFAULT_STATS;
2411 sbi->s_mb_stream_request = MB_DEFAULT_STREAM_THRESHOLD;
2412 sbi->s_mb_order2_reqs = MB_DEFAULT_ORDER2_REQS;
2413 sbi->s_mb_history_filter = EXT4_MB_HISTORY_DEFAULT;
2414 sbi->s_mb_group_prealloc = MB_DEFAULT_GROUP_PREALLOC;
2415
2416 i = sizeof(struct ext4_locality_group) * NR_CPUS;
2417 sbi->s_locality_groups = kmalloc(i, GFP_KERNEL);
2418 if (sbi->s_locality_groups == NULL) {
2419 clear_opt(sbi->s_mount_opt, MBALLOC);
2420 kfree(sbi->s_mb_offsets);
2421 kfree(sbi->s_mb_maxs);
2422 return -ENOMEM;
2423 }
2424 for (i = 0; i < NR_CPUS; i++) {
2425 struct ext4_locality_group *lg;
2426 lg = &sbi->s_locality_groups[i];
2427 mutex_init(&lg->lg_mutex);
2428 INIT_LIST_HEAD(&lg->lg_prealloc_list);
2429 spin_lock_init(&lg->lg_prealloc_lock);
2430 }
2431
2432 ext4_mb_init_per_dev_proc(sb);
2433 ext4_mb_history_init(sb);
2434
2435 printk("EXT4-fs: mballoc enabled\n");
2436 return 0;
2437}
2438
2439/* need to called with ext4 group lock (ext4_lock_group) */
2440static void ext4_mb_cleanup_pa(struct ext4_group_info *grp)
2441{
2442 struct ext4_prealloc_space *pa;
2443 struct list_head *cur, *tmp;
2444 int count = 0;
2445
2446 list_for_each_safe(cur, tmp, &grp->bb_prealloc_list) {
2447 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
2448 list_del(&pa->pa_group_list);
2449 count++;
2450 kfree(pa);
2451 }
2452 if (count)
2453 mb_debug("mballoc: %u PAs left\n", count);
2454
2455}
2456
2457int ext4_mb_release(struct super_block *sb)
2458{
2459 ext4_group_t i;
2460 int num_meta_group_infos;
2461 struct ext4_group_info *grinfo;
2462 struct ext4_sb_info *sbi = EXT4_SB(sb);
2463
2464 if (!test_opt(sb, MBALLOC))
2465 return 0;
2466
2467 /* release freed, non-committed blocks */
2468 spin_lock(&sbi->s_md_lock);
2469 list_splice_init(&sbi->s_closed_transaction,
2470 &sbi->s_committed_transaction);
2471 list_splice_init(&sbi->s_active_transaction,
2472 &sbi->s_committed_transaction);
2473 spin_unlock(&sbi->s_md_lock);
2474 ext4_mb_free_committed_blocks(sb);
2475
2476 if (sbi->s_group_info) {
2477 for (i = 0; i < sbi->s_groups_count; i++) {
2478 grinfo = ext4_get_group_info(sb, i);
2479#ifdef DOUBLE_CHECK
2480 kfree(grinfo->bb_bitmap);
2481#endif
2482 ext4_lock_group(sb, i);
2483 ext4_mb_cleanup_pa(grinfo);
2484 ext4_unlock_group(sb, i);
2485 kfree(grinfo);
2486 }
2487 num_meta_group_infos = (sbi->s_groups_count +
2488 EXT4_DESC_PER_BLOCK(sb) - 1) >>
2489 EXT4_DESC_PER_BLOCK_BITS(sb);
2490 for (i = 0; i < num_meta_group_infos; i++)
2491 kfree(sbi->s_group_info[i]);
2492 kfree(sbi->s_group_info);
2493 }
2494 kfree(sbi->s_mb_offsets);
2495 kfree(sbi->s_mb_maxs);
2496 if (sbi->s_buddy_cache)
2497 iput(sbi->s_buddy_cache);
2498 if (sbi->s_mb_stats) {
2499 printk(KERN_INFO
2500 "EXT4-fs: mballoc: %u blocks %u reqs (%u success)\n",
2501 atomic_read(&sbi->s_bal_allocated),
2502 atomic_read(&sbi->s_bal_reqs),
2503 atomic_read(&sbi->s_bal_success));
2504 printk(KERN_INFO
2505 "EXT4-fs: mballoc: %u extents scanned, %u goal hits, "
2506 "%u 2^N hits, %u breaks, %u lost\n",
2507 atomic_read(&sbi->s_bal_ex_scanned),
2508 atomic_read(&sbi->s_bal_goals),
2509 atomic_read(&sbi->s_bal_2orders),
2510 atomic_read(&sbi->s_bal_breaks),
2511 atomic_read(&sbi->s_mb_lost_chunks));
2512 printk(KERN_INFO
2513 "EXT4-fs: mballoc: %lu generated and it took %Lu\n",
2514 sbi->s_mb_buddies_generated++,
2515 sbi->s_mb_generation_time);
2516 printk(KERN_INFO
2517 "EXT4-fs: mballoc: %u preallocated, %u discarded\n",
2518 atomic_read(&sbi->s_mb_preallocated),
2519 atomic_read(&sbi->s_mb_discarded));
2520 }
2521
2522 kfree(sbi->s_locality_groups);
2523
2524 ext4_mb_history_release(sb);
2525 ext4_mb_destroy_per_dev_proc(sb);
2526
2527 return 0;
2528}
2529
Eric Sandeen4ddfef72008-04-29 08:11:12 -04002530static noinline_for_stack void
2531ext4_mb_free_committed_blocks(struct super_block *sb)
Alex Tomasc9de5602008-01-29 00:19:52 -05002532{
2533 struct ext4_sb_info *sbi = EXT4_SB(sb);
2534 int err;
2535 int i;
2536 int count = 0;
2537 int count2 = 0;
2538 struct ext4_free_metadata *md;
2539 struct ext4_buddy e4b;
2540
2541 if (list_empty(&sbi->s_committed_transaction))
2542 return;
2543
2544 /* there is committed blocks to be freed yet */
2545 do {
2546 /* get next array of blocks */
2547 md = NULL;
2548 spin_lock(&sbi->s_md_lock);
2549 if (!list_empty(&sbi->s_committed_transaction)) {
2550 md = list_entry(sbi->s_committed_transaction.next,
2551 struct ext4_free_metadata, list);
2552 list_del(&md->list);
2553 }
2554 spin_unlock(&sbi->s_md_lock);
2555
2556 if (md == NULL)
2557 break;
2558
2559 mb_debug("gonna free %u blocks in group %lu (0x%p):",
2560 md->num, md->group, md);
2561
2562 err = ext4_mb_load_buddy(sb, md->group, &e4b);
2563 /* we expect to find existing buddy because it's pinned */
2564 BUG_ON(err != 0);
2565
2566 /* there are blocks to put in buddy to make them really free */
2567 count += md->num;
2568 count2++;
2569 ext4_lock_group(sb, md->group);
2570 for (i = 0; i < md->num; i++) {
2571 mb_debug(" %u", md->blocks[i]);
Shen Feng7e5a8cd2008-07-13 21:03:31 -04002572 mb_free_blocks(NULL, &e4b, md->blocks[i], 1);
Alex Tomasc9de5602008-01-29 00:19:52 -05002573 }
2574 mb_debug("\n");
2575 ext4_unlock_group(sb, md->group);
2576
2577 /* balance refcounts from ext4_mb_free_metadata() */
2578 page_cache_release(e4b.bd_buddy_page);
2579 page_cache_release(e4b.bd_bitmap_page);
2580
2581 kfree(md);
2582 ext4_mb_release_desc(&e4b);
2583
2584 } while (md);
2585
2586 mb_debug("freed %u blocks in %u structures\n", count, count2);
2587}
2588
Alex Tomasc9de5602008-01-29 00:19:52 -05002589#define EXT4_MB_STATS_NAME "stats"
2590#define EXT4_MB_MAX_TO_SCAN_NAME "max_to_scan"
2591#define EXT4_MB_MIN_TO_SCAN_NAME "min_to_scan"
2592#define EXT4_MB_ORDER2_REQ "order2_req"
2593#define EXT4_MB_STREAM_REQ "stream_req"
2594#define EXT4_MB_GROUP_PREALLOC "group_prealloc"
2595
2596
2597
Alexey Dobriyan91d99822008-07-11 19:27:31 -04002598#define MB_PROC_FOPS(name) \
2599static int ext4_mb_##name##_proc_show(struct seq_file *m, void *v) \
Alex Tomasc9de5602008-01-29 00:19:52 -05002600{ \
Alexey Dobriyan91d99822008-07-11 19:27:31 -04002601 struct ext4_sb_info *sbi = m->private; \
2602 \
2603 seq_printf(m, "%ld\n", sbi->s_mb_##name); \
2604 return 0; \
2605} \
2606 \
2607static int ext4_mb_##name##_proc_open(struct inode *inode, struct file *file)\
Alex Tomasc9de5602008-01-29 00:19:52 -05002608{ \
Alexey Dobriyan91d99822008-07-11 19:27:31 -04002609 return single_open(file, ext4_mb_##name##_proc_show, PDE(inode)->data);\
2610} \
2611 \
2612static ssize_t ext4_mb_##name##_proc_write(struct file *file, \
2613 const char __user *buf, size_t cnt, loff_t *ppos) \
2614{ \
2615 struct ext4_sb_info *sbi = PDE(file->f_path.dentry->d_inode)->data;\
Alex Tomasc9de5602008-01-29 00:19:52 -05002616 char str[32]; \
2617 long value; \
2618 if (cnt >= sizeof(str)) \
2619 return -EINVAL; \
2620 if (copy_from_user(str, buf, cnt)) \
2621 return -EFAULT; \
2622 value = simple_strtol(str, NULL, 0); \
2623 if (value <= 0) \
2624 return -ERANGE; \
2625 sbi->s_mb_##name = value; \
2626 return cnt; \
Alexey Dobriyan91d99822008-07-11 19:27:31 -04002627} \
2628 \
2629static const struct file_operations ext4_mb_##name##_proc_fops = { \
2630 .owner = THIS_MODULE, \
2631 .open = ext4_mb_##name##_proc_open, \
2632 .read = seq_read, \
2633 .llseek = seq_lseek, \
2634 .release = single_release, \
2635 .write = ext4_mb_##name##_proc_write, \
2636};
Alex Tomasc9de5602008-01-29 00:19:52 -05002637
Alexey Dobriyan91d99822008-07-11 19:27:31 -04002638MB_PROC_FOPS(stats);
2639MB_PROC_FOPS(max_to_scan);
2640MB_PROC_FOPS(min_to_scan);
2641MB_PROC_FOPS(order2_reqs);
2642MB_PROC_FOPS(stream_request);
2643MB_PROC_FOPS(group_prealloc);
Alex Tomasc9de5602008-01-29 00:19:52 -05002644
2645#define MB_PROC_HANDLER(name, var) \
2646do { \
Alexey Dobriyan91d99822008-07-11 19:27:31 -04002647 proc = proc_create_data(name, mode, sbi->s_mb_proc, \
2648 &ext4_mb_##var##_proc_fops, sbi); \
Alex Tomasc9de5602008-01-29 00:19:52 -05002649 if (proc == NULL) { \
2650 printk(KERN_ERR "EXT4-fs: can't to create %s\n", name); \
2651 goto err_out; \
2652 } \
Alex Tomasc9de5602008-01-29 00:19:52 -05002653} while (0)
2654
2655static int ext4_mb_init_per_dev_proc(struct super_block *sb)
2656{
2657 mode_t mode = S_IFREG | S_IRUGO | S_IWUSR;
2658 struct ext4_sb_info *sbi = EXT4_SB(sb);
2659 struct proc_dir_entry *proc;
2660 char devname[64];
2661
Shen Fengcfbe7e42008-07-13 21:03:31 -04002662 if (proc_root_ext4 == NULL) {
2663 sbi->s_mb_proc = NULL;
2664 return -EINVAL;
2665 }
Jean Delvaref36f21e2008-05-12 14:02:33 -07002666 bdevname(sb->s_bdev, devname);
Alex Tomasc9de5602008-01-29 00:19:52 -05002667 sbi->s_mb_proc = proc_mkdir(devname, proc_root_ext4);
2668
2669 MB_PROC_HANDLER(EXT4_MB_STATS_NAME, stats);
2670 MB_PROC_HANDLER(EXT4_MB_MAX_TO_SCAN_NAME, max_to_scan);
2671 MB_PROC_HANDLER(EXT4_MB_MIN_TO_SCAN_NAME, min_to_scan);
2672 MB_PROC_HANDLER(EXT4_MB_ORDER2_REQ, order2_reqs);
2673 MB_PROC_HANDLER(EXT4_MB_STREAM_REQ, stream_request);
2674 MB_PROC_HANDLER(EXT4_MB_GROUP_PREALLOC, group_prealloc);
2675
2676 return 0;
2677
2678err_out:
2679 printk(KERN_ERR "EXT4-fs: Unable to create %s\n", devname);
2680 remove_proc_entry(EXT4_MB_GROUP_PREALLOC, sbi->s_mb_proc);
2681 remove_proc_entry(EXT4_MB_STREAM_REQ, sbi->s_mb_proc);
2682 remove_proc_entry(EXT4_MB_ORDER2_REQ, sbi->s_mb_proc);
2683 remove_proc_entry(EXT4_MB_MIN_TO_SCAN_NAME, sbi->s_mb_proc);
2684 remove_proc_entry(EXT4_MB_MAX_TO_SCAN_NAME, sbi->s_mb_proc);
2685 remove_proc_entry(EXT4_MB_STATS_NAME, sbi->s_mb_proc);
2686 remove_proc_entry(devname, proc_root_ext4);
2687 sbi->s_mb_proc = NULL;
2688
2689 return -ENOMEM;
2690}
2691
2692static int ext4_mb_destroy_per_dev_proc(struct super_block *sb)
2693{
2694 struct ext4_sb_info *sbi = EXT4_SB(sb);
2695 char devname[64];
2696
2697 if (sbi->s_mb_proc == NULL)
2698 return -EINVAL;
2699
Jean Delvaref36f21e2008-05-12 14:02:33 -07002700 bdevname(sb->s_bdev, devname);
Alex Tomasc9de5602008-01-29 00:19:52 -05002701 remove_proc_entry(EXT4_MB_GROUP_PREALLOC, sbi->s_mb_proc);
2702 remove_proc_entry(EXT4_MB_STREAM_REQ, sbi->s_mb_proc);
2703 remove_proc_entry(EXT4_MB_ORDER2_REQ, sbi->s_mb_proc);
2704 remove_proc_entry(EXT4_MB_MIN_TO_SCAN_NAME, sbi->s_mb_proc);
2705 remove_proc_entry(EXT4_MB_MAX_TO_SCAN_NAME, sbi->s_mb_proc);
2706 remove_proc_entry(EXT4_MB_STATS_NAME, sbi->s_mb_proc);
2707 remove_proc_entry(devname, proc_root_ext4);
2708
2709 return 0;
2710}
2711
2712int __init init_ext4_mballoc(void)
2713{
2714 ext4_pspace_cachep =
2715 kmem_cache_create("ext4_prealloc_space",
2716 sizeof(struct ext4_prealloc_space),
2717 0, SLAB_RECLAIM_ACCOUNT, NULL);
2718 if (ext4_pspace_cachep == NULL)
2719 return -ENOMEM;
2720
Eric Sandeen256bdb42008-02-10 01:13:33 -05002721 ext4_ac_cachep =
2722 kmem_cache_create("ext4_alloc_context",
2723 sizeof(struct ext4_allocation_context),
2724 0, SLAB_RECLAIM_ACCOUNT, NULL);
2725 if (ext4_ac_cachep == NULL) {
2726 kmem_cache_destroy(ext4_pspace_cachep);
2727 return -ENOMEM;
2728 }
Alex Tomasc9de5602008-01-29 00:19:52 -05002729#ifdef CONFIG_PROC_FS
Alexey Dobriyan36a5aeb2008-04-29 01:01:42 -07002730 proc_root_ext4 = proc_mkdir("fs/ext4", NULL);
Alex Tomasc9de5602008-01-29 00:19:52 -05002731 if (proc_root_ext4 == NULL)
Alexey Dobriyan36a5aeb2008-04-29 01:01:42 -07002732 printk(KERN_ERR "EXT4-fs: Unable to create fs/ext4\n");
Alex Tomasc9de5602008-01-29 00:19:52 -05002733#endif
Alex Tomasc9de5602008-01-29 00:19:52 -05002734 return 0;
2735}
2736
2737void exit_ext4_mballoc(void)
2738{
2739 /* XXX: synchronize_rcu(); */
2740 kmem_cache_destroy(ext4_pspace_cachep);
Eric Sandeen256bdb42008-02-10 01:13:33 -05002741 kmem_cache_destroy(ext4_ac_cachep);
Alex Tomasc9de5602008-01-29 00:19:52 -05002742#ifdef CONFIG_PROC_FS
Alexey Dobriyan36a5aeb2008-04-29 01:01:42 -07002743 remove_proc_entry("fs/ext4", NULL);
Alex Tomasc9de5602008-01-29 00:19:52 -05002744#endif
2745}
2746
2747
2748/*
2749 * Check quota and mark choosed space (ac->ac_b_ex) non-free in bitmaps
2750 * Returns 0 if success or error code
2751 */
Eric Sandeen4ddfef72008-04-29 08:11:12 -04002752static noinline_for_stack int
2753ext4_mb_mark_diskspace_used(struct ext4_allocation_context *ac,
Alex Tomasc9de5602008-01-29 00:19:52 -05002754 handle_t *handle)
2755{
2756 struct buffer_head *bitmap_bh = NULL;
2757 struct ext4_super_block *es;
2758 struct ext4_group_desc *gdp;
2759 struct buffer_head *gdp_bh;
2760 struct ext4_sb_info *sbi;
2761 struct super_block *sb;
2762 ext4_fsblk_t block;
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -04002763 int err, len;
Alex Tomasc9de5602008-01-29 00:19:52 -05002764
2765 BUG_ON(ac->ac_status != AC_STATUS_FOUND);
2766 BUG_ON(ac->ac_b_ex.fe_len <= 0);
2767
2768 sb = ac->ac_sb;
2769 sbi = EXT4_SB(sb);
2770 es = sbi->s_es;
2771
Alex Tomasc9de5602008-01-29 00:19:52 -05002772
2773 err = -EIO;
Theodore Ts'o574ca172008-07-11 19:27:31 -04002774 bitmap_bh = ext4_read_block_bitmap(sb, ac->ac_b_ex.fe_group);
Alex Tomasc9de5602008-01-29 00:19:52 -05002775 if (!bitmap_bh)
2776 goto out_err;
2777
2778 err = ext4_journal_get_write_access(handle, bitmap_bh);
2779 if (err)
2780 goto out_err;
2781
2782 err = -EIO;
2783 gdp = ext4_get_group_desc(sb, ac->ac_b_ex.fe_group, &gdp_bh);
2784 if (!gdp)
2785 goto out_err;
2786
Aneesh Kumar K.V03cddb82008-06-05 20:59:29 -04002787 ext4_debug("using block group %lu(%d)\n", ac->ac_b_ex.fe_group,
2788 gdp->bg_free_blocks_count);
2789
Alex Tomasc9de5602008-01-29 00:19:52 -05002790 err = ext4_journal_get_write_access(handle, gdp_bh);
2791 if (err)
2792 goto out_err;
2793
2794 block = ac->ac_b_ex.fe_group * EXT4_BLOCKS_PER_GROUP(sb)
2795 + ac->ac_b_ex.fe_start
2796 + le32_to_cpu(es->s_first_data_block);
2797
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -04002798 len = ac->ac_b_ex.fe_len;
2799 if (in_range(ext4_block_bitmap(sb, gdp), block, len) ||
2800 in_range(ext4_inode_bitmap(sb, gdp), block, len) ||
2801 in_range(block, ext4_inode_table(sb, gdp),
2802 EXT4_SB(sb)->s_itb_per_group) ||
2803 in_range(block + len - 1, ext4_inode_table(sb, gdp),
2804 EXT4_SB(sb)->s_itb_per_group)) {
Harvey Harrison46e665e2008-04-17 10:38:59 -04002805 ext4_error(sb, __func__,
Alex Tomasc9de5602008-01-29 00:19:52 -05002806 "Allocating block in system zone - block = %llu",
2807 block);
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -04002808 /* File system mounted not to panic on error
2809 * Fix the bitmap and repeat the block allocation
2810 * We leak some of the blocks here.
2811 */
2812 mb_set_bits(sb_bgl_lock(sbi, ac->ac_b_ex.fe_group),
2813 bitmap_bh->b_data, ac->ac_b_ex.fe_start,
2814 ac->ac_b_ex.fe_len);
2815 err = ext4_journal_dirty_metadata(handle, bitmap_bh);
2816 if (!err)
2817 err = -EAGAIN;
2818 goto out_err;
Alex Tomasc9de5602008-01-29 00:19:52 -05002819 }
2820#ifdef AGGRESSIVE_CHECK
2821 {
2822 int i;
2823 for (i = 0; i < ac->ac_b_ex.fe_len; i++) {
2824 BUG_ON(mb_test_bit(ac->ac_b_ex.fe_start + i,
2825 bitmap_bh->b_data));
2826 }
2827 }
2828#endif
2829 mb_set_bits(sb_bgl_lock(sbi, ac->ac_b_ex.fe_group), bitmap_bh->b_data,
2830 ac->ac_b_ex.fe_start, ac->ac_b_ex.fe_len);
2831
2832 spin_lock(sb_bgl_lock(sbi, ac->ac_b_ex.fe_group));
2833 if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
2834 gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
2835 gdp->bg_free_blocks_count =
2836 cpu_to_le16(ext4_free_blocks_after_init(sb,
2837 ac->ac_b_ex.fe_group,
2838 gdp));
2839 }
Marcin Slusarze8546d02008-04-17 10:38:59 -04002840 le16_add_cpu(&gdp->bg_free_blocks_count, -ac->ac_b_ex.fe_len);
Alex Tomasc9de5602008-01-29 00:19:52 -05002841 gdp->bg_checksum = ext4_group_desc_csum(sbi, ac->ac_b_ex.fe_group, gdp);
2842 spin_unlock(sb_bgl_lock(sbi, ac->ac_b_ex.fe_group));
2843 percpu_counter_sub(&sbi->s_freeblocks_counter, ac->ac_b_ex.fe_len);
2844
2845 err = ext4_journal_dirty_metadata(handle, bitmap_bh);
2846 if (err)
2847 goto out_err;
2848 err = ext4_journal_dirty_metadata(handle, gdp_bh);
2849
2850out_err:
2851 sb->s_dirt = 1;
Aneesh Kumar K.V42a10ad2008-02-10 01:07:28 -05002852 brelse(bitmap_bh);
Alex Tomasc9de5602008-01-29 00:19:52 -05002853 return err;
2854}
2855
2856/*
2857 * here we normalize request for locality group
2858 * Group request are normalized to s_strip size if we set the same via mount
2859 * option. If not we set it to s_mb_group_prealloc which can be configured via
2860 * /proc/fs/ext4/<partition>/group_prealloc
2861 *
2862 * XXX: should we try to preallocate more than the group has now?
2863 */
2864static void ext4_mb_normalize_group_request(struct ext4_allocation_context *ac)
2865{
2866 struct super_block *sb = ac->ac_sb;
2867 struct ext4_locality_group *lg = ac->ac_lg;
2868
2869 BUG_ON(lg == NULL);
2870 if (EXT4_SB(sb)->s_stripe)
2871 ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_stripe;
2872 else
2873 ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_mb_group_prealloc;
Solofo Ramangalahy60bd63d2008-04-29 21:59:59 -04002874 mb_debug("#%u: goal %u blocks for locality group\n",
Alex Tomasc9de5602008-01-29 00:19:52 -05002875 current->pid, ac->ac_g_ex.fe_len);
2876}
2877
2878/*
2879 * Normalization means making request better in terms of
2880 * size and alignment
2881 */
Eric Sandeen4ddfef72008-04-29 08:11:12 -04002882static noinline_for_stack void
2883ext4_mb_normalize_request(struct ext4_allocation_context *ac,
Alex Tomasc9de5602008-01-29 00:19:52 -05002884 struct ext4_allocation_request *ar)
2885{
2886 int bsbits, max;
2887 ext4_lblk_t end;
Alex Tomasc9de5602008-01-29 00:19:52 -05002888 loff_t size, orig_size, start_off;
2889 ext4_lblk_t start, orig_start;
2890 struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
Aneesh Kumar K.V9a0762c2008-04-17 10:38:59 -04002891 struct ext4_prealloc_space *pa;
Alex Tomasc9de5602008-01-29 00:19:52 -05002892
2893 /* do normalize only data requests, metadata requests
2894 do not need preallocation */
2895 if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
2896 return;
2897
2898 /* sometime caller may want exact blocks */
2899 if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
2900 return;
2901
2902 /* caller may indicate that preallocation isn't
2903 * required (it's a tail, for example) */
2904 if (ac->ac_flags & EXT4_MB_HINT_NOPREALLOC)
2905 return;
2906
2907 if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) {
2908 ext4_mb_normalize_group_request(ac);
2909 return ;
2910 }
2911
2912 bsbits = ac->ac_sb->s_blocksize_bits;
2913
2914 /* first, let's learn actual file size
2915 * given current request is allocated */
2916 size = ac->ac_o_ex.fe_logical + ac->ac_o_ex.fe_len;
2917 size = size << bsbits;
2918 if (size < i_size_read(ac->ac_inode))
2919 size = i_size_read(ac->ac_inode);
2920
Valerie Clement19304792008-05-13 19:31:14 -04002921 /* max size of free chunks */
2922 max = 2 << bsbits;
Alex Tomasc9de5602008-01-29 00:19:52 -05002923
Valerie Clement19304792008-05-13 19:31:14 -04002924#define NRL_CHECK_SIZE(req, size, max, chunk_size) \
2925 (req <= (size) || max <= (chunk_size))
Alex Tomasc9de5602008-01-29 00:19:52 -05002926
2927 /* first, try to predict filesize */
2928 /* XXX: should this table be tunable? */
2929 start_off = 0;
2930 if (size <= 16 * 1024) {
2931 size = 16 * 1024;
2932 } else if (size <= 32 * 1024) {
2933 size = 32 * 1024;
2934 } else if (size <= 64 * 1024) {
2935 size = 64 * 1024;
2936 } else if (size <= 128 * 1024) {
2937 size = 128 * 1024;
2938 } else if (size <= 256 * 1024) {
2939 size = 256 * 1024;
2940 } else if (size <= 512 * 1024) {
2941 size = 512 * 1024;
2942 } else if (size <= 1024 * 1024) {
2943 size = 1024 * 1024;
Valerie Clement19304792008-05-13 19:31:14 -04002944 } else if (NRL_CHECK_SIZE(size, 4 * 1024 * 1024, max, 2 * 1024)) {
Alex Tomasc9de5602008-01-29 00:19:52 -05002945 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
Valerie Clement19304792008-05-13 19:31:14 -04002946 (21 - bsbits)) << 21;
2947 size = 2 * 1024 * 1024;
2948 } else if (NRL_CHECK_SIZE(size, 8 * 1024 * 1024, max, 4 * 1024)) {
Alex Tomasc9de5602008-01-29 00:19:52 -05002949 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
2950 (22 - bsbits)) << 22;
2951 size = 4 * 1024 * 1024;
2952 } else if (NRL_CHECK_SIZE(ac->ac_o_ex.fe_len,
Valerie Clement19304792008-05-13 19:31:14 -04002953 (8<<20)>>bsbits, max, 8 * 1024)) {
Alex Tomasc9de5602008-01-29 00:19:52 -05002954 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
2955 (23 - bsbits)) << 23;
2956 size = 8 * 1024 * 1024;
2957 } else {
2958 start_off = (loff_t)ac->ac_o_ex.fe_logical << bsbits;
2959 size = ac->ac_o_ex.fe_len << bsbits;
2960 }
2961 orig_size = size = size >> bsbits;
2962 orig_start = start = start_off >> bsbits;
2963
2964 /* don't cover already allocated blocks in selected range */
2965 if (ar->pleft && start <= ar->lleft) {
2966 size -= ar->lleft + 1 - start;
2967 start = ar->lleft + 1;
2968 }
2969 if (ar->pright && start + size - 1 >= ar->lright)
2970 size -= start + size - ar->lright;
2971
2972 end = start + size;
2973
2974 /* check we don't cross already preallocated blocks */
2975 rcu_read_lock();
Aneesh Kumar K.V9a0762c2008-04-17 10:38:59 -04002976 list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
Alex Tomasc9de5602008-01-29 00:19:52 -05002977 unsigned long pa_end;
2978
Alex Tomasc9de5602008-01-29 00:19:52 -05002979 if (pa->pa_deleted)
2980 continue;
2981 spin_lock(&pa->pa_lock);
2982 if (pa->pa_deleted) {
2983 spin_unlock(&pa->pa_lock);
2984 continue;
2985 }
2986
2987 pa_end = pa->pa_lstart + pa->pa_len;
2988
2989 /* PA must not overlap original request */
2990 BUG_ON(!(ac->ac_o_ex.fe_logical >= pa_end ||
2991 ac->ac_o_ex.fe_logical < pa->pa_lstart));
2992
2993 /* skip PA normalized request doesn't overlap with */
2994 if (pa->pa_lstart >= end) {
2995 spin_unlock(&pa->pa_lock);
2996 continue;
2997 }
2998 if (pa_end <= start) {
2999 spin_unlock(&pa->pa_lock);
3000 continue;
3001 }
3002 BUG_ON(pa->pa_lstart <= start && pa_end >= end);
3003
3004 if (pa_end <= ac->ac_o_ex.fe_logical) {
3005 BUG_ON(pa_end < start);
3006 start = pa_end;
3007 }
3008
3009 if (pa->pa_lstart > ac->ac_o_ex.fe_logical) {
3010 BUG_ON(pa->pa_lstart > end);
3011 end = pa->pa_lstart;
3012 }
3013 spin_unlock(&pa->pa_lock);
3014 }
3015 rcu_read_unlock();
3016 size = end - start;
3017
3018 /* XXX: extra loop to check we really don't overlap preallocations */
3019 rcu_read_lock();
Aneesh Kumar K.V9a0762c2008-04-17 10:38:59 -04003020 list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
Alex Tomasc9de5602008-01-29 00:19:52 -05003021 unsigned long pa_end;
Alex Tomasc9de5602008-01-29 00:19:52 -05003022 spin_lock(&pa->pa_lock);
3023 if (pa->pa_deleted == 0) {
3024 pa_end = pa->pa_lstart + pa->pa_len;
3025 BUG_ON(!(start >= pa_end || end <= pa->pa_lstart));
3026 }
3027 spin_unlock(&pa->pa_lock);
3028 }
3029 rcu_read_unlock();
3030
3031 if (start + size <= ac->ac_o_ex.fe_logical &&
3032 start > ac->ac_o_ex.fe_logical) {
3033 printk(KERN_ERR "start %lu, size %lu, fe_logical %lu\n",
3034 (unsigned long) start, (unsigned long) size,
3035 (unsigned long) ac->ac_o_ex.fe_logical);
3036 }
3037 BUG_ON(start + size <= ac->ac_o_ex.fe_logical &&
3038 start > ac->ac_o_ex.fe_logical);
3039 BUG_ON(size <= 0 || size >= EXT4_BLOCKS_PER_GROUP(ac->ac_sb));
3040
3041 /* now prepare goal request */
3042
3043 /* XXX: is it better to align blocks WRT to logical
3044 * placement or satisfy big request as is */
3045 ac->ac_g_ex.fe_logical = start;
3046 ac->ac_g_ex.fe_len = size;
3047
3048 /* define goal start in order to merge */
3049 if (ar->pright && (ar->lright == (start + size))) {
3050 /* merge to the right */
3051 ext4_get_group_no_and_offset(ac->ac_sb, ar->pright - size,
3052 &ac->ac_f_ex.fe_group,
3053 &ac->ac_f_ex.fe_start);
3054 ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
3055 }
3056 if (ar->pleft && (ar->lleft + 1 == start)) {
3057 /* merge to the left */
3058 ext4_get_group_no_and_offset(ac->ac_sb, ar->pleft + 1,
3059 &ac->ac_f_ex.fe_group,
3060 &ac->ac_f_ex.fe_start);
3061 ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
3062 }
3063
3064 mb_debug("goal: %u(was %u) blocks at %u\n", (unsigned) size,
3065 (unsigned) orig_size, (unsigned) start);
3066}
3067
3068static void ext4_mb_collect_stats(struct ext4_allocation_context *ac)
3069{
3070 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3071
3072 if (sbi->s_mb_stats && ac->ac_g_ex.fe_len > 1) {
3073 atomic_inc(&sbi->s_bal_reqs);
3074 atomic_add(ac->ac_b_ex.fe_len, &sbi->s_bal_allocated);
3075 if (ac->ac_o_ex.fe_len >= ac->ac_g_ex.fe_len)
3076 atomic_inc(&sbi->s_bal_success);
3077 atomic_add(ac->ac_found, &sbi->s_bal_ex_scanned);
3078 if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&
3079 ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)
3080 atomic_inc(&sbi->s_bal_goals);
3081 if (ac->ac_found > sbi->s_mb_max_to_scan)
3082 atomic_inc(&sbi->s_bal_breaks);
3083 }
3084
3085 ext4_mb_store_history(ac);
3086}
3087
3088/*
3089 * use blocks preallocated to inode
3090 */
3091static void ext4_mb_use_inode_pa(struct ext4_allocation_context *ac,
3092 struct ext4_prealloc_space *pa)
3093{
3094 ext4_fsblk_t start;
3095 ext4_fsblk_t end;
3096 int len;
3097
3098 /* found preallocated blocks, use them */
3099 start = pa->pa_pstart + (ac->ac_o_ex.fe_logical - pa->pa_lstart);
3100 end = min(pa->pa_pstart + pa->pa_len, start + ac->ac_o_ex.fe_len);
3101 len = end - start;
3102 ext4_get_group_no_and_offset(ac->ac_sb, start, &ac->ac_b_ex.fe_group,
3103 &ac->ac_b_ex.fe_start);
3104 ac->ac_b_ex.fe_len = len;
3105 ac->ac_status = AC_STATUS_FOUND;
3106 ac->ac_pa = pa;
3107
3108 BUG_ON(start < pa->pa_pstart);
3109 BUG_ON(start + len > pa->pa_pstart + pa->pa_len);
3110 BUG_ON(pa->pa_free < len);
3111 pa->pa_free -= len;
3112
Solofo Ramangalahy60bd63d2008-04-29 21:59:59 -04003113 mb_debug("use %llu/%u from inode pa %p\n", start, len, pa);
Alex Tomasc9de5602008-01-29 00:19:52 -05003114}
3115
3116/*
3117 * use blocks preallocated to locality group
3118 */
3119static void ext4_mb_use_group_pa(struct ext4_allocation_context *ac,
3120 struct ext4_prealloc_space *pa)
3121{
Aneesh Kumar K.V03cddb82008-06-05 20:59:29 -04003122 unsigned int len = ac->ac_o_ex.fe_len;
Alex Tomasc9de5602008-01-29 00:19:52 -05003123 ext4_get_group_no_and_offset(ac->ac_sb, pa->pa_pstart,
3124 &ac->ac_b_ex.fe_group,
3125 &ac->ac_b_ex.fe_start);
3126 ac->ac_b_ex.fe_len = len;
3127 ac->ac_status = AC_STATUS_FOUND;
3128 ac->ac_pa = pa;
3129
3130 /* we don't correct pa_pstart or pa_plen here to avoid
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05003131 * possible race when the group is being loaded concurrently
Alex Tomasc9de5602008-01-29 00:19:52 -05003132 * instead we correct pa later, after blocks are marked
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05003133 * in on-disk bitmap -- see ext4_mb_release_context()
3134 * Other CPUs are prevented from allocating from this pa by lg_mutex
Alex Tomasc9de5602008-01-29 00:19:52 -05003135 */
3136 mb_debug("use %u/%u from group pa %p\n", pa->pa_lstart-len, len, pa);
3137}
3138
3139/*
3140 * search goal blocks in preallocated space
3141 */
Eric Sandeen4ddfef72008-04-29 08:11:12 -04003142static noinline_for_stack int
3143ext4_mb_use_preallocated(struct ext4_allocation_context *ac)
Alex Tomasc9de5602008-01-29 00:19:52 -05003144{
3145 struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
3146 struct ext4_locality_group *lg;
3147 struct ext4_prealloc_space *pa;
Alex Tomasc9de5602008-01-29 00:19:52 -05003148
3149 /* only data can be preallocated */
3150 if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
3151 return 0;
3152
3153 /* first, try per-file preallocation */
3154 rcu_read_lock();
Aneesh Kumar K.V9a0762c2008-04-17 10:38:59 -04003155 list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
Alex Tomasc9de5602008-01-29 00:19:52 -05003156
3157 /* all fields in this condition don't change,
3158 * so we can skip locking for them */
3159 if (ac->ac_o_ex.fe_logical < pa->pa_lstart ||
3160 ac->ac_o_ex.fe_logical >= pa->pa_lstart + pa->pa_len)
3161 continue;
3162
3163 /* found preallocated blocks, use them */
3164 spin_lock(&pa->pa_lock);
3165 if (pa->pa_deleted == 0 && pa->pa_free) {
3166 atomic_inc(&pa->pa_count);
3167 ext4_mb_use_inode_pa(ac, pa);
3168 spin_unlock(&pa->pa_lock);
3169 ac->ac_criteria = 10;
3170 rcu_read_unlock();
3171 return 1;
3172 }
3173 spin_unlock(&pa->pa_lock);
3174 }
3175 rcu_read_unlock();
3176
3177 /* can we use group allocation? */
3178 if (!(ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC))
3179 return 0;
3180
3181 /* inode may have no locality group for some reason */
3182 lg = ac->ac_lg;
3183 if (lg == NULL)
3184 return 0;
3185
3186 rcu_read_lock();
Aneesh Kumar K.V9a0762c2008-04-17 10:38:59 -04003187 list_for_each_entry_rcu(pa, &lg->lg_prealloc_list, pa_inode_list) {
Alex Tomasc9de5602008-01-29 00:19:52 -05003188 spin_lock(&pa->pa_lock);
3189 if (pa->pa_deleted == 0 && pa->pa_free >= ac->ac_o_ex.fe_len) {
3190 atomic_inc(&pa->pa_count);
3191 ext4_mb_use_group_pa(ac, pa);
3192 spin_unlock(&pa->pa_lock);
3193 ac->ac_criteria = 20;
3194 rcu_read_unlock();
3195 return 1;
3196 }
3197 spin_unlock(&pa->pa_lock);
3198 }
3199 rcu_read_unlock();
3200
3201 return 0;
3202}
3203
3204/*
3205 * the function goes through all preallocation in this group and marks them
3206 * used in in-core bitmap. buddy must be generated from this bitmap
3207 * Need to be called with ext4 group lock (ext4_lock_group)
3208 */
3209static void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,
3210 ext4_group_t group)
3211{
3212 struct ext4_group_info *grp = ext4_get_group_info(sb, group);
3213 struct ext4_prealloc_space *pa;
3214 struct list_head *cur;
3215 ext4_group_t groupnr;
3216 ext4_grpblk_t start;
3217 int preallocated = 0;
3218 int count = 0;
3219 int len;
3220
3221 /* all form of preallocation discards first load group,
3222 * so the only competing code is preallocation use.
3223 * we don't need any locking here
3224 * notice we do NOT ignore preallocations with pa_deleted
3225 * otherwise we could leave used blocks available for
3226 * allocation in buddy when concurrent ext4_mb_put_pa()
3227 * is dropping preallocation
3228 */
3229 list_for_each(cur, &grp->bb_prealloc_list) {
3230 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
3231 spin_lock(&pa->pa_lock);
3232 ext4_get_group_no_and_offset(sb, pa->pa_pstart,
3233 &groupnr, &start);
3234 len = pa->pa_len;
3235 spin_unlock(&pa->pa_lock);
3236 if (unlikely(len == 0))
3237 continue;
3238 BUG_ON(groupnr != group);
3239 mb_set_bits(sb_bgl_lock(EXT4_SB(sb), group),
3240 bitmap, start, len);
3241 preallocated += len;
3242 count++;
3243 }
3244 mb_debug("prellocated %u for group %lu\n", preallocated, group);
3245}
3246
3247static void ext4_mb_pa_callback(struct rcu_head *head)
3248{
3249 struct ext4_prealloc_space *pa;
3250 pa = container_of(head, struct ext4_prealloc_space, u.pa_rcu);
3251 kmem_cache_free(ext4_pspace_cachep, pa);
3252}
3253
3254/*
3255 * drops a reference to preallocated space descriptor
3256 * if this was the last reference and the space is consumed
3257 */
3258static void ext4_mb_put_pa(struct ext4_allocation_context *ac,
3259 struct super_block *sb, struct ext4_prealloc_space *pa)
3260{
3261 unsigned long grp;
3262
3263 if (!atomic_dec_and_test(&pa->pa_count) || pa->pa_free != 0)
3264 return;
3265
3266 /* in this short window concurrent discard can set pa_deleted */
3267 spin_lock(&pa->pa_lock);
3268 if (pa->pa_deleted == 1) {
3269 spin_unlock(&pa->pa_lock);
3270 return;
3271 }
3272
3273 pa->pa_deleted = 1;
3274 spin_unlock(&pa->pa_lock);
3275
3276 /* -1 is to protect from crossing allocation group */
3277 ext4_get_group_no_and_offset(sb, pa->pa_pstart - 1, &grp, NULL);
3278
3279 /*
3280 * possible race:
3281 *
3282 * P1 (buddy init) P2 (regular allocation)
3283 * find block B in PA
3284 * copy on-disk bitmap to buddy
3285 * mark B in on-disk bitmap
3286 * drop PA from group
3287 * mark all PAs in buddy
3288 *
3289 * thus, P1 initializes buddy with B available. to prevent this
3290 * we make "copy" and "mark all PAs" atomic and serialize "drop PA"
3291 * against that pair
3292 */
3293 ext4_lock_group(sb, grp);
3294 list_del(&pa->pa_group_list);
3295 ext4_unlock_group(sb, grp);
3296
3297 spin_lock(pa->pa_obj_lock);
3298 list_del_rcu(&pa->pa_inode_list);
3299 spin_unlock(pa->pa_obj_lock);
3300
3301 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
3302}
3303
3304/*
3305 * creates new preallocated space for given inode
3306 */
Eric Sandeen4ddfef72008-04-29 08:11:12 -04003307static noinline_for_stack int
3308ext4_mb_new_inode_pa(struct ext4_allocation_context *ac)
Alex Tomasc9de5602008-01-29 00:19:52 -05003309{
3310 struct super_block *sb = ac->ac_sb;
3311 struct ext4_prealloc_space *pa;
3312 struct ext4_group_info *grp;
3313 struct ext4_inode_info *ei;
3314
3315 /* preallocate only when found space is larger then requested */
3316 BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
3317 BUG_ON(ac->ac_status != AC_STATUS_FOUND);
3318 BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
3319
3320 pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS);
3321 if (pa == NULL)
3322 return -ENOMEM;
3323
3324 if (ac->ac_b_ex.fe_len < ac->ac_g_ex.fe_len) {
3325 int winl;
3326 int wins;
3327 int win;
3328 int offs;
3329
3330 /* we can't allocate as much as normalizer wants.
3331 * so, found space must get proper lstart
3332 * to cover original request */
3333 BUG_ON(ac->ac_g_ex.fe_logical > ac->ac_o_ex.fe_logical);
3334 BUG_ON(ac->ac_g_ex.fe_len < ac->ac_o_ex.fe_len);
3335
3336 /* we're limited by original request in that
3337 * logical block must be covered any way
3338 * winl is window we can move our chunk within */
3339 winl = ac->ac_o_ex.fe_logical - ac->ac_g_ex.fe_logical;
3340
3341 /* also, we should cover whole original request */
3342 wins = ac->ac_b_ex.fe_len - ac->ac_o_ex.fe_len;
3343
3344 /* the smallest one defines real window */
3345 win = min(winl, wins);
3346
3347 offs = ac->ac_o_ex.fe_logical % ac->ac_b_ex.fe_len;
3348 if (offs && offs < win)
3349 win = offs;
3350
3351 ac->ac_b_ex.fe_logical = ac->ac_o_ex.fe_logical - win;
3352 BUG_ON(ac->ac_o_ex.fe_logical < ac->ac_b_ex.fe_logical);
3353 BUG_ON(ac->ac_o_ex.fe_len > ac->ac_b_ex.fe_len);
3354 }
3355
3356 /* preallocation can change ac_b_ex, thus we store actually
3357 * allocated blocks for history */
3358 ac->ac_f_ex = ac->ac_b_ex;
3359
3360 pa->pa_lstart = ac->ac_b_ex.fe_logical;
3361 pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
3362 pa->pa_len = ac->ac_b_ex.fe_len;
3363 pa->pa_free = pa->pa_len;
3364 atomic_set(&pa->pa_count, 1);
3365 spin_lock_init(&pa->pa_lock);
3366 pa->pa_deleted = 0;
3367 pa->pa_linear = 0;
3368
3369 mb_debug("new inode pa %p: %llu/%u for %u\n", pa,
3370 pa->pa_pstart, pa->pa_len, pa->pa_lstart);
3371
3372 ext4_mb_use_inode_pa(ac, pa);
3373 atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated);
3374
3375 ei = EXT4_I(ac->ac_inode);
3376 grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
3377
3378 pa->pa_obj_lock = &ei->i_prealloc_lock;
3379 pa->pa_inode = ac->ac_inode;
3380
3381 ext4_lock_group(sb, ac->ac_b_ex.fe_group);
3382 list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
3383 ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
3384
3385 spin_lock(pa->pa_obj_lock);
3386 list_add_rcu(&pa->pa_inode_list, &ei->i_prealloc_list);
3387 spin_unlock(pa->pa_obj_lock);
3388
3389 return 0;
3390}
3391
3392/*
3393 * creates new preallocated space for locality group inodes belongs to
3394 */
Eric Sandeen4ddfef72008-04-29 08:11:12 -04003395static noinline_for_stack int
3396ext4_mb_new_group_pa(struct ext4_allocation_context *ac)
Alex Tomasc9de5602008-01-29 00:19:52 -05003397{
3398 struct super_block *sb = ac->ac_sb;
3399 struct ext4_locality_group *lg;
3400 struct ext4_prealloc_space *pa;
3401 struct ext4_group_info *grp;
3402
3403 /* preallocate only when found space is larger then requested */
3404 BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
3405 BUG_ON(ac->ac_status != AC_STATUS_FOUND);
3406 BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
3407
3408 BUG_ON(ext4_pspace_cachep == NULL);
3409 pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS);
3410 if (pa == NULL)
3411 return -ENOMEM;
3412
3413 /* preallocation can change ac_b_ex, thus we store actually
3414 * allocated blocks for history */
3415 ac->ac_f_ex = ac->ac_b_ex;
3416
3417 pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
3418 pa->pa_lstart = pa->pa_pstart;
3419 pa->pa_len = ac->ac_b_ex.fe_len;
3420 pa->pa_free = pa->pa_len;
3421 atomic_set(&pa->pa_count, 1);
3422 spin_lock_init(&pa->pa_lock);
3423 pa->pa_deleted = 0;
3424 pa->pa_linear = 1;
3425
3426 mb_debug("new group pa %p: %llu/%u for %u\n", pa,
3427 pa->pa_pstart, pa->pa_len, pa->pa_lstart);
3428
3429 ext4_mb_use_group_pa(ac, pa);
3430 atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated);
3431
3432 grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
3433 lg = ac->ac_lg;
3434 BUG_ON(lg == NULL);
3435
3436 pa->pa_obj_lock = &lg->lg_prealloc_lock;
3437 pa->pa_inode = NULL;
3438
3439 ext4_lock_group(sb, ac->ac_b_ex.fe_group);
3440 list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
3441 ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
3442
3443 spin_lock(pa->pa_obj_lock);
3444 list_add_tail_rcu(&pa->pa_inode_list, &lg->lg_prealloc_list);
3445 spin_unlock(pa->pa_obj_lock);
3446
3447 return 0;
3448}
3449
3450static int ext4_mb_new_preallocation(struct ext4_allocation_context *ac)
3451{
3452 int err;
3453
3454 if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
3455 err = ext4_mb_new_group_pa(ac);
3456 else
3457 err = ext4_mb_new_inode_pa(ac);
3458 return err;
3459}
3460
3461/*
3462 * finds all unused blocks in on-disk bitmap, frees them in
3463 * in-core bitmap and buddy.
3464 * @pa must be unlinked from inode and group lists, so that
3465 * nobody else can find/use it.
3466 * the caller MUST hold group/inode locks.
3467 * TODO: optimize the case when there are no in-core structures yet
3468 */
Eric Sandeen4ddfef72008-04-29 08:11:12 -04003469static noinline_for_stack int
3470ext4_mb_release_inode_pa(struct ext4_buddy *e4b, struct buffer_head *bitmap_bh,
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003471 struct ext4_prealloc_space *pa,
3472 struct ext4_allocation_context *ac)
Alex Tomasc9de5602008-01-29 00:19:52 -05003473{
Alex Tomasc9de5602008-01-29 00:19:52 -05003474 struct super_block *sb = e4b->bd_sb;
3475 struct ext4_sb_info *sbi = EXT4_SB(sb);
3476 unsigned long end;
3477 unsigned long next;
3478 ext4_group_t group;
3479 ext4_grpblk_t bit;
3480 sector_t start;
3481 int err = 0;
3482 int free = 0;
3483
3484 BUG_ON(pa->pa_deleted == 0);
3485 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);
3486 BUG_ON(group != e4b->bd_group && pa->pa_len != 0);
3487 end = bit + pa->pa_len;
3488
Eric Sandeen256bdb42008-02-10 01:13:33 -05003489 if (ac) {
3490 ac->ac_sb = sb;
3491 ac->ac_inode = pa->pa_inode;
3492 ac->ac_op = EXT4_MB_HISTORY_DISCARD;
3493 }
Alex Tomasc9de5602008-01-29 00:19:52 -05003494
3495 while (bit < end) {
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -05003496 bit = mb_find_next_zero_bit(bitmap_bh->b_data, end, bit);
Alex Tomasc9de5602008-01-29 00:19:52 -05003497 if (bit >= end)
3498 break;
Aneesh Kumar K.Vffad0a42008-02-23 01:38:34 -05003499 next = mb_find_next_bit(bitmap_bh->b_data, end, bit);
Alex Tomasc9de5602008-01-29 00:19:52 -05003500 start = group * EXT4_BLOCKS_PER_GROUP(sb) + bit +
3501 le32_to_cpu(sbi->s_es->s_first_data_block);
3502 mb_debug(" free preallocated %u/%u in group %u\n",
3503 (unsigned) start, (unsigned) next - bit,
3504 (unsigned) group);
3505 free += next - bit;
3506
Eric Sandeen256bdb42008-02-10 01:13:33 -05003507 if (ac) {
3508 ac->ac_b_ex.fe_group = group;
3509 ac->ac_b_ex.fe_start = bit;
3510 ac->ac_b_ex.fe_len = next - bit;
3511 ac->ac_b_ex.fe_logical = 0;
3512 ext4_mb_store_history(ac);
3513 }
Alex Tomasc9de5602008-01-29 00:19:52 -05003514
3515 mb_free_blocks(pa->pa_inode, e4b, bit, next - bit);
3516 bit = next + 1;
3517 }
3518 if (free != pa->pa_free) {
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05003519 printk(KERN_CRIT "pa %p: logic %lu, phys. %lu, len %lu\n",
Alex Tomasc9de5602008-01-29 00:19:52 -05003520 pa, (unsigned long) pa->pa_lstart,
3521 (unsigned long) pa->pa_pstart,
3522 (unsigned long) pa->pa_len);
Harvey Harrison46e665e2008-04-17 10:38:59 -04003523 ext4_error(sb, __func__, "free %u, pa_free %u\n",
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05003524 free, pa->pa_free);
Aneesh Kumar K.Ve56eb652008-02-15 13:48:21 -05003525 /*
3526 * pa is already deleted so we use the value obtained
3527 * from the bitmap and continue.
3528 */
Alex Tomasc9de5602008-01-29 00:19:52 -05003529 }
Alex Tomasc9de5602008-01-29 00:19:52 -05003530 atomic_add(free, &sbi->s_mb_discarded);
3531
3532 return err;
3533}
3534
Eric Sandeen4ddfef72008-04-29 08:11:12 -04003535static noinline_for_stack int
3536ext4_mb_release_group_pa(struct ext4_buddy *e4b,
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003537 struct ext4_prealloc_space *pa,
3538 struct ext4_allocation_context *ac)
Alex Tomasc9de5602008-01-29 00:19:52 -05003539{
Alex Tomasc9de5602008-01-29 00:19:52 -05003540 struct super_block *sb = e4b->bd_sb;
3541 ext4_group_t group;
3542 ext4_grpblk_t bit;
3543
Eric Sandeen256bdb42008-02-10 01:13:33 -05003544 if (ac)
3545 ac->ac_op = EXT4_MB_HISTORY_DISCARD;
Alex Tomasc9de5602008-01-29 00:19:52 -05003546
3547 BUG_ON(pa->pa_deleted == 0);
3548 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);
3549 BUG_ON(group != e4b->bd_group && pa->pa_len != 0);
3550 mb_free_blocks(pa->pa_inode, e4b, bit, pa->pa_len);
3551 atomic_add(pa->pa_len, &EXT4_SB(sb)->s_mb_discarded);
3552
Eric Sandeen256bdb42008-02-10 01:13:33 -05003553 if (ac) {
3554 ac->ac_sb = sb;
3555 ac->ac_inode = NULL;
3556 ac->ac_b_ex.fe_group = group;
3557 ac->ac_b_ex.fe_start = bit;
3558 ac->ac_b_ex.fe_len = pa->pa_len;
3559 ac->ac_b_ex.fe_logical = 0;
3560 ext4_mb_store_history(ac);
Eric Sandeen256bdb42008-02-10 01:13:33 -05003561 }
Alex Tomasc9de5602008-01-29 00:19:52 -05003562
3563 return 0;
3564}
3565
3566/*
3567 * releases all preallocations in given group
3568 *
3569 * first, we need to decide discard policy:
3570 * - when do we discard
3571 * 1) ENOSPC
3572 * - how many do we discard
3573 * 1) how many requested
3574 */
Eric Sandeen4ddfef72008-04-29 08:11:12 -04003575static noinline_for_stack int
3576ext4_mb_discard_group_preallocations(struct super_block *sb,
Alex Tomasc9de5602008-01-29 00:19:52 -05003577 ext4_group_t group, int needed)
3578{
3579 struct ext4_group_info *grp = ext4_get_group_info(sb, group);
3580 struct buffer_head *bitmap_bh = NULL;
3581 struct ext4_prealloc_space *pa, *tmp;
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003582 struct ext4_allocation_context *ac;
Alex Tomasc9de5602008-01-29 00:19:52 -05003583 struct list_head list;
3584 struct ext4_buddy e4b;
3585 int err;
3586 int busy = 0;
3587 int free = 0;
3588
3589 mb_debug("discard preallocation for group %lu\n", group);
3590
3591 if (list_empty(&grp->bb_prealloc_list))
3592 return 0;
3593
Theodore Ts'o574ca172008-07-11 19:27:31 -04003594 bitmap_bh = ext4_read_block_bitmap(sb, group);
Alex Tomasc9de5602008-01-29 00:19:52 -05003595 if (bitmap_bh == NULL) {
3596 /* error handling here */
3597 ext4_mb_release_desc(&e4b);
3598 BUG_ON(bitmap_bh == NULL);
3599 }
3600
3601 err = ext4_mb_load_buddy(sb, group, &e4b);
3602 BUG_ON(err != 0); /* error handling here */
3603
3604 if (needed == 0)
3605 needed = EXT4_BLOCKS_PER_GROUP(sb) + 1;
3606
3607 grp = ext4_get_group_info(sb, group);
3608 INIT_LIST_HEAD(&list);
3609
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003610 ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
Alex Tomasc9de5602008-01-29 00:19:52 -05003611repeat:
3612 ext4_lock_group(sb, group);
3613 list_for_each_entry_safe(pa, tmp,
3614 &grp->bb_prealloc_list, pa_group_list) {
3615 spin_lock(&pa->pa_lock);
3616 if (atomic_read(&pa->pa_count)) {
3617 spin_unlock(&pa->pa_lock);
3618 busy = 1;
3619 continue;
3620 }
3621 if (pa->pa_deleted) {
3622 spin_unlock(&pa->pa_lock);
3623 continue;
3624 }
3625
3626 /* seems this one can be freed ... */
3627 pa->pa_deleted = 1;
3628
3629 /* we can trust pa_free ... */
3630 free += pa->pa_free;
3631
3632 spin_unlock(&pa->pa_lock);
3633
3634 list_del(&pa->pa_group_list);
3635 list_add(&pa->u.pa_tmp_list, &list);
3636 }
3637
3638 /* if we still need more blocks and some PAs were used, try again */
3639 if (free < needed && busy) {
3640 busy = 0;
3641 ext4_unlock_group(sb, group);
3642 /*
3643 * Yield the CPU here so that we don't get soft lockup
3644 * in non preempt case.
3645 */
3646 yield();
3647 goto repeat;
3648 }
3649
3650 /* found anything to free? */
3651 if (list_empty(&list)) {
3652 BUG_ON(free != 0);
3653 goto out;
3654 }
3655
3656 /* now free all selected PAs */
3657 list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {
3658
3659 /* remove from object (inode or locality group) */
3660 spin_lock(pa->pa_obj_lock);
3661 list_del_rcu(&pa->pa_inode_list);
3662 spin_unlock(pa->pa_obj_lock);
3663
3664 if (pa->pa_linear)
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003665 ext4_mb_release_group_pa(&e4b, pa, ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05003666 else
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003667 ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa, ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05003668
3669 list_del(&pa->u.pa_tmp_list);
3670 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
3671 }
3672
3673out:
3674 ext4_unlock_group(sb, group);
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003675 if (ac)
3676 kmem_cache_free(ext4_ac_cachep, ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05003677 ext4_mb_release_desc(&e4b);
3678 put_bh(bitmap_bh);
3679 return free;
3680}
3681
3682/*
3683 * releases all non-used preallocated blocks for given inode
3684 *
3685 * It's important to discard preallocations under i_data_sem
3686 * We don't want another block to be served from the prealloc
3687 * space when we are discarding the inode prealloc space.
3688 *
3689 * FIXME!! Make sure it is valid at all the call sites
3690 */
3691void ext4_mb_discard_inode_preallocations(struct inode *inode)
3692{
3693 struct ext4_inode_info *ei = EXT4_I(inode);
3694 struct super_block *sb = inode->i_sb;
3695 struct buffer_head *bitmap_bh = NULL;
3696 struct ext4_prealloc_space *pa, *tmp;
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003697 struct ext4_allocation_context *ac;
Alex Tomasc9de5602008-01-29 00:19:52 -05003698 ext4_group_t group = 0;
3699 struct list_head list;
3700 struct ext4_buddy e4b;
3701 int err;
3702
3703 if (!test_opt(sb, MBALLOC) || !S_ISREG(inode->i_mode)) {
3704 /*BUG_ON(!list_empty(&ei->i_prealloc_list));*/
3705 return;
3706 }
3707
3708 mb_debug("discard preallocation for inode %lu\n", inode->i_ino);
3709
3710 INIT_LIST_HEAD(&list);
3711
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003712 ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
Alex Tomasc9de5602008-01-29 00:19:52 -05003713repeat:
3714 /* first, collect all pa's in the inode */
3715 spin_lock(&ei->i_prealloc_lock);
3716 while (!list_empty(&ei->i_prealloc_list)) {
3717 pa = list_entry(ei->i_prealloc_list.next,
3718 struct ext4_prealloc_space, pa_inode_list);
3719 BUG_ON(pa->pa_obj_lock != &ei->i_prealloc_lock);
3720 spin_lock(&pa->pa_lock);
3721 if (atomic_read(&pa->pa_count)) {
3722 /* this shouldn't happen often - nobody should
3723 * use preallocation while we're discarding it */
3724 spin_unlock(&pa->pa_lock);
3725 spin_unlock(&ei->i_prealloc_lock);
3726 printk(KERN_ERR "uh-oh! used pa while discarding\n");
3727 WARN_ON(1);
3728 schedule_timeout_uninterruptible(HZ);
3729 goto repeat;
3730
3731 }
3732 if (pa->pa_deleted == 0) {
3733 pa->pa_deleted = 1;
3734 spin_unlock(&pa->pa_lock);
3735 list_del_rcu(&pa->pa_inode_list);
3736 list_add(&pa->u.pa_tmp_list, &list);
3737 continue;
3738 }
3739
3740 /* someone is deleting pa right now */
3741 spin_unlock(&pa->pa_lock);
3742 spin_unlock(&ei->i_prealloc_lock);
3743
3744 /* we have to wait here because pa_deleted
3745 * doesn't mean pa is already unlinked from
3746 * the list. as we might be called from
3747 * ->clear_inode() the inode will get freed
3748 * and concurrent thread which is unlinking
3749 * pa from inode's list may access already
3750 * freed memory, bad-bad-bad */
3751
3752 /* XXX: if this happens too often, we can
3753 * add a flag to force wait only in case
3754 * of ->clear_inode(), but not in case of
3755 * regular truncate */
3756 schedule_timeout_uninterruptible(HZ);
3757 goto repeat;
3758 }
3759 spin_unlock(&ei->i_prealloc_lock);
3760
3761 list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {
3762 BUG_ON(pa->pa_linear != 0);
3763 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, NULL);
3764
3765 err = ext4_mb_load_buddy(sb, group, &e4b);
3766 BUG_ON(err != 0); /* error handling here */
3767
Theodore Ts'o574ca172008-07-11 19:27:31 -04003768 bitmap_bh = ext4_read_block_bitmap(sb, group);
Alex Tomasc9de5602008-01-29 00:19:52 -05003769 if (bitmap_bh == NULL) {
3770 /* error handling here */
3771 ext4_mb_release_desc(&e4b);
3772 BUG_ON(bitmap_bh == NULL);
3773 }
3774
3775 ext4_lock_group(sb, group);
3776 list_del(&pa->pa_group_list);
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003777 ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa, ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05003778 ext4_unlock_group(sb, group);
3779
3780 ext4_mb_release_desc(&e4b);
3781 put_bh(bitmap_bh);
3782
3783 list_del(&pa->u.pa_tmp_list);
3784 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
3785 }
Aneesh Kumar K.Vc83617d2008-04-29 22:00:47 -04003786 if (ac)
3787 kmem_cache_free(ext4_ac_cachep, ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05003788}
3789
3790/*
3791 * finds all preallocated spaces and return blocks being freed to them
3792 * if preallocated space becomes full (no block is used from the space)
3793 * then the function frees space in buddy
3794 * XXX: at the moment, truncate (which is the only way to free blocks)
3795 * discards all preallocations
3796 */
3797static void ext4_mb_return_to_preallocation(struct inode *inode,
3798 struct ext4_buddy *e4b,
3799 sector_t block, int count)
3800{
3801 BUG_ON(!list_empty(&EXT4_I(inode)->i_prealloc_list));
3802}
3803#ifdef MB_DEBUG
3804static void ext4_mb_show_ac(struct ext4_allocation_context *ac)
3805{
3806 struct super_block *sb = ac->ac_sb;
3807 ext4_group_t i;
3808
3809 printk(KERN_ERR "EXT4-fs: Can't allocate:"
3810 " Allocation context details:\n");
3811 printk(KERN_ERR "EXT4-fs: status %d flags %d\n",
3812 ac->ac_status, ac->ac_flags);
3813 printk(KERN_ERR "EXT4-fs: orig %lu/%lu/%lu@%lu, goal %lu/%lu/%lu@%lu, "
3814 "best %lu/%lu/%lu@%lu cr %d\n",
3815 (unsigned long)ac->ac_o_ex.fe_group,
3816 (unsigned long)ac->ac_o_ex.fe_start,
3817 (unsigned long)ac->ac_o_ex.fe_len,
3818 (unsigned long)ac->ac_o_ex.fe_logical,
3819 (unsigned long)ac->ac_g_ex.fe_group,
3820 (unsigned long)ac->ac_g_ex.fe_start,
3821 (unsigned long)ac->ac_g_ex.fe_len,
3822 (unsigned long)ac->ac_g_ex.fe_logical,
3823 (unsigned long)ac->ac_b_ex.fe_group,
3824 (unsigned long)ac->ac_b_ex.fe_start,
3825 (unsigned long)ac->ac_b_ex.fe_len,
3826 (unsigned long)ac->ac_b_ex.fe_logical,
3827 (int)ac->ac_criteria);
3828 printk(KERN_ERR "EXT4-fs: %lu scanned, %d found\n", ac->ac_ex_scanned,
3829 ac->ac_found);
3830 printk(KERN_ERR "EXT4-fs: groups: \n");
3831 for (i = 0; i < EXT4_SB(sb)->s_groups_count; i++) {
3832 struct ext4_group_info *grp = ext4_get_group_info(sb, i);
3833 struct ext4_prealloc_space *pa;
3834 ext4_grpblk_t start;
3835 struct list_head *cur;
3836 ext4_lock_group(sb, i);
3837 list_for_each(cur, &grp->bb_prealloc_list) {
3838 pa = list_entry(cur, struct ext4_prealloc_space,
3839 pa_group_list);
3840 spin_lock(&pa->pa_lock);
3841 ext4_get_group_no_and_offset(sb, pa->pa_pstart,
3842 NULL, &start);
3843 spin_unlock(&pa->pa_lock);
3844 printk(KERN_ERR "PA:%lu:%d:%u \n", i,
3845 start, pa->pa_len);
3846 }
Solofo Ramangalahy60bd63d2008-04-29 21:59:59 -04003847 ext4_unlock_group(sb, i);
Alex Tomasc9de5602008-01-29 00:19:52 -05003848
3849 if (grp->bb_free == 0)
3850 continue;
3851 printk(KERN_ERR "%lu: %d/%d \n",
3852 i, grp->bb_free, grp->bb_fragments);
3853 }
3854 printk(KERN_ERR "\n");
3855}
3856#else
3857static inline void ext4_mb_show_ac(struct ext4_allocation_context *ac)
3858{
3859 return;
3860}
3861#endif
3862
3863/*
3864 * We use locality group preallocation for small size file. The size of the
3865 * file is determined by the current size or the resulting size after
3866 * allocation which ever is larger
3867 *
3868 * One can tune this size via /proc/fs/ext4/<partition>/stream_req
3869 */
3870static void ext4_mb_group_or_file(struct ext4_allocation_context *ac)
3871{
3872 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3873 int bsbits = ac->ac_sb->s_blocksize_bits;
3874 loff_t size, isize;
3875
3876 if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
3877 return;
3878
3879 size = ac->ac_o_ex.fe_logical + ac->ac_o_ex.fe_len;
3880 isize = i_size_read(ac->ac_inode) >> bsbits;
3881 size = max(size, isize);
3882
3883 /* don't use group allocation for large files */
3884 if (size >= sbi->s_mb_stream_request)
3885 return;
3886
3887 if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
3888 return;
3889
3890 BUG_ON(ac->ac_lg != NULL);
3891 /*
3892 * locality group prealloc space are per cpu. The reason for having
3893 * per cpu locality group is to reduce the contention between block
3894 * request from multiple CPUs.
3895 */
3896 ac->ac_lg = &sbi->s_locality_groups[get_cpu()];
3897 put_cpu();
3898
3899 /* we're going to use group allocation */
3900 ac->ac_flags |= EXT4_MB_HINT_GROUP_ALLOC;
3901
3902 /* serialize all allocations in the group */
3903 mutex_lock(&ac->ac_lg->lg_mutex);
3904}
3905
Eric Sandeen4ddfef72008-04-29 08:11:12 -04003906static noinline_for_stack int
3907ext4_mb_initialize_context(struct ext4_allocation_context *ac,
Alex Tomasc9de5602008-01-29 00:19:52 -05003908 struct ext4_allocation_request *ar)
3909{
3910 struct super_block *sb = ar->inode->i_sb;
3911 struct ext4_sb_info *sbi = EXT4_SB(sb);
3912 struct ext4_super_block *es = sbi->s_es;
3913 ext4_group_t group;
3914 unsigned long len;
3915 unsigned long goal;
3916 ext4_grpblk_t block;
3917
3918 /* we can't allocate > group size */
3919 len = ar->len;
3920
3921 /* just a dirty hack to filter too big requests */
3922 if (len >= EXT4_BLOCKS_PER_GROUP(sb) - 10)
3923 len = EXT4_BLOCKS_PER_GROUP(sb) - 10;
3924
3925 /* start searching from the goal */
3926 goal = ar->goal;
3927 if (goal < le32_to_cpu(es->s_first_data_block) ||
3928 goal >= ext4_blocks_count(es))
3929 goal = le32_to_cpu(es->s_first_data_block);
3930 ext4_get_group_no_and_offset(sb, goal, &group, &block);
3931
3932 /* set up allocation goals */
3933 ac->ac_b_ex.fe_logical = ar->logical;
3934 ac->ac_b_ex.fe_group = 0;
3935 ac->ac_b_ex.fe_start = 0;
3936 ac->ac_b_ex.fe_len = 0;
3937 ac->ac_status = AC_STATUS_CONTINUE;
3938 ac->ac_groups_scanned = 0;
3939 ac->ac_ex_scanned = 0;
3940 ac->ac_found = 0;
3941 ac->ac_sb = sb;
3942 ac->ac_inode = ar->inode;
3943 ac->ac_o_ex.fe_logical = ar->logical;
3944 ac->ac_o_ex.fe_group = group;
3945 ac->ac_o_ex.fe_start = block;
3946 ac->ac_o_ex.fe_len = len;
3947 ac->ac_g_ex.fe_logical = ar->logical;
3948 ac->ac_g_ex.fe_group = group;
3949 ac->ac_g_ex.fe_start = block;
3950 ac->ac_g_ex.fe_len = len;
3951 ac->ac_f_ex.fe_len = 0;
3952 ac->ac_flags = ar->flags;
3953 ac->ac_2order = 0;
3954 ac->ac_criteria = 0;
3955 ac->ac_pa = NULL;
3956 ac->ac_bitmap_page = NULL;
3957 ac->ac_buddy_page = NULL;
3958 ac->ac_lg = NULL;
3959
3960 /* we have to define context: we'll we work with a file or
3961 * locality group. this is a policy, actually */
3962 ext4_mb_group_or_file(ac);
3963
3964 mb_debug("init ac: %u blocks @ %u, goal %u, flags %x, 2^%d, "
3965 "left: %u/%u, right %u/%u to %swritable\n",
3966 (unsigned) ar->len, (unsigned) ar->logical,
3967 (unsigned) ar->goal, ac->ac_flags, ac->ac_2order,
3968 (unsigned) ar->lleft, (unsigned) ar->pleft,
3969 (unsigned) ar->lright, (unsigned) ar->pright,
3970 atomic_read(&ar->inode->i_writecount) ? "" : "non-");
3971 return 0;
3972
3973}
3974
3975/*
3976 * release all resource we used in allocation
3977 */
3978static int ext4_mb_release_context(struct ext4_allocation_context *ac)
3979{
3980 if (ac->ac_pa) {
3981 if (ac->ac_pa->pa_linear) {
3982 /* see comment in ext4_mb_use_group_pa() */
3983 spin_lock(&ac->ac_pa->pa_lock);
3984 ac->ac_pa->pa_pstart += ac->ac_b_ex.fe_len;
3985 ac->ac_pa->pa_lstart += ac->ac_b_ex.fe_len;
3986 ac->ac_pa->pa_free -= ac->ac_b_ex.fe_len;
3987 ac->ac_pa->pa_len -= ac->ac_b_ex.fe_len;
3988 spin_unlock(&ac->ac_pa->pa_lock);
3989 }
3990 ext4_mb_put_pa(ac, ac->ac_sb, ac->ac_pa);
3991 }
3992 if (ac->ac_bitmap_page)
3993 page_cache_release(ac->ac_bitmap_page);
3994 if (ac->ac_buddy_page)
3995 page_cache_release(ac->ac_buddy_page);
3996 if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
3997 mutex_unlock(&ac->ac_lg->lg_mutex);
3998 ext4_mb_collect_stats(ac);
3999 return 0;
4000}
4001
4002static int ext4_mb_discard_preallocations(struct super_block *sb, int needed)
4003{
4004 ext4_group_t i;
4005 int ret;
4006 int freed = 0;
4007
4008 for (i = 0; i < EXT4_SB(sb)->s_groups_count && needed > 0; i++) {
4009 ret = ext4_mb_discard_group_preallocations(sb, i, needed);
4010 freed += ret;
4011 needed -= ret;
4012 }
4013
4014 return freed;
4015}
4016
4017/*
4018 * Main entry point into mballoc to allocate blocks
4019 * it tries to use preallocation first, then falls back
4020 * to usual allocation
4021 */
4022ext4_fsblk_t ext4_mb_new_blocks(handle_t *handle,
4023 struct ext4_allocation_request *ar, int *errp)
4024{
Eric Sandeen256bdb42008-02-10 01:13:33 -05004025 struct ext4_allocation_context *ac = NULL;
Alex Tomasc9de5602008-01-29 00:19:52 -05004026 struct ext4_sb_info *sbi;
4027 struct super_block *sb;
4028 ext4_fsblk_t block = 0;
4029 int freed;
4030 int inquota;
4031
4032 sb = ar->inode->i_sb;
4033 sbi = EXT4_SB(sb);
4034
4035 if (!test_opt(sb, MBALLOC)) {
4036 block = ext4_new_blocks_old(handle, ar->inode, ar->goal,
4037 &(ar->len), errp);
4038 return block;
4039 }
4040
4041 while (ar->len && DQUOT_ALLOC_BLOCK(ar->inode, ar->len)) {
4042 ar->flags |= EXT4_MB_HINT_NOPREALLOC;
4043 ar->len--;
4044 }
4045 if (ar->len == 0) {
4046 *errp = -EDQUOT;
4047 return 0;
4048 }
4049 inquota = ar->len;
4050
Eric Sandeen256bdb42008-02-10 01:13:33 -05004051 ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
4052 if (!ac) {
4053 *errp = -ENOMEM;
4054 return 0;
4055 }
4056
Alex Tomasc9de5602008-01-29 00:19:52 -05004057 ext4_mb_poll_new_transaction(sb, handle);
4058
Eric Sandeen256bdb42008-02-10 01:13:33 -05004059 *errp = ext4_mb_initialize_context(ac, ar);
Alex Tomasc9de5602008-01-29 00:19:52 -05004060 if (*errp) {
4061 ar->len = 0;
4062 goto out;
4063 }
4064
Eric Sandeen256bdb42008-02-10 01:13:33 -05004065 ac->ac_op = EXT4_MB_HISTORY_PREALLOC;
4066 if (!ext4_mb_use_preallocated(ac)) {
Alex Tomasc9de5602008-01-29 00:19:52 -05004067
Eric Sandeen256bdb42008-02-10 01:13:33 -05004068 ac->ac_op = EXT4_MB_HISTORY_ALLOC;
4069 ext4_mb_normalize_request(ac, ar);
Alex Tomasc9de5602008-01-29 00:19:52 -05004070repeat:
4071 /* allocate space in core */
Eric Sandeen256bdb42008-02-10 01:13:33 -05004072 ext4_mb_regular_allocator(ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05004073
4074 /* as we've just preallocated more space than
4075 * user requested orinally, we store allocated
4076 * space in a special descriptor */
Eric Sandeen256bdb42008-02-10 01:13:33 -05004077 if (ac->ac_status == AC_STATUS_FOUND &&
4078 ac->ac_o_ex.fe_len < ac->ac_b_ex.fe_len)
4079 ext4_mb_new_preallocation(ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05004080 }
4081
Eric Sandeen256bdb42008-02-10 01:13:33 -05004082 if (likely(ac->ac_status == AC_STATUS_FOUND)) {
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -04004083 *errp = ext4_mb_mark_diskspace_used(ac, handle);
4084 if (*errp == -EAGAIN) {
4085 ac->ac_b_ex.fe_group = 0;
4086 ac->ac_b_ex.fe_start = 0;
4087 ac->ac_b_ex.fe_len = 0;
4088 ac->ac_status = AC_STATUS_CONTINUE;
4089 goto repeat;
4090 } else if (*errp) {
4091 ac->ac_b_ex.fe_len = 0;
4092 ar->len = 0;
4093 ext4_mb_show_ac(ac);
4094 } else {
4095 block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
4096 ar->len = ac->ac_b_ex.fe_len;
4097 }
Alex Tomasc9de5602008-01-29 00:19:52 -05004098 } else {
Eric Sandeen256bdb42008-02-10 01:13:33 -05004099 freed = ext4_mb_discard_preallocations(sb, ac->ac_o_ex.fe_len);
Alex Tomasc9de5602008-01-29 00:19:52 -05004100 if (freed)
4101 goto repeat;
4102 *errp = -ENOSPC;
Eric Sandeen256bdb42008-02-10 01:13:33 -05004103 ac->ac_b_ex.fe_len = 0;
Alex Tomasc9de5602008-01-29 00:19:52 -05004104 ar->len = 0;
Eric Sandeen256bdb42008-02-10 01:13:33 -05004105 ext4_mb_show_ac(ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05004106 }
4107
Eric Sandeen256bdb42008-02-10 01:13:33 -05004108 ext4_mb_release_context(ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05004109
4110out:
4111 if (ar->len < inquota)
4112 DQUOT_FREE_BLOCK(ar->inode, inquota - ar->len);
4113
Eric Sandeen256bdb42008-02-10 01:13:33 -05004114 kmem_cache_free(ext4_ac_cachep, ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05004115 return block;
4116}
4117static void ext4_mb_poll_new_transaction(struct super_block *sb,
4118 handle_t *handle)
4119{
4120 struct ext4_sb_info *sbi = EXT4_SB(sb);
4121
4122 if (sbi->s_last_transaction == handle->h_transaction->t_tid)
4123 return;
4124
4125 /* new transaction! time to close last one and free blocks for
4126 * committed transaction. we know that only transaction can be
4127 * active, so previos transaction can be being logged and we
4128 * know that transaction before previous is known to be already
4129 * logged. this means that now we may free blocks freed in all
4130 * transactions before previous one. hope I'm clear enough ... */
4131
4132 spin_lock(&sbi->s_md_lock);
4133 if (sbi->s_last_transaction != handle->h_transaction->t_tid) {
4134 mb_debug("new transaction %lu, old %lu\n",
4135 (unsigned long) handle->h_transaction->t_tid,
4136 (unsigned long) sbi->s_last_transaction);
4137 list_splice_init(&sbi->s_closed_transaction,
4138 &sbi->s_committed_transaction);
4139 list_splice_init(&sbi->s_active_transaction,
4140 &sbi->s_closed_transaction);
4141 sbi->s_last_transaction = handle->h_transaction->t_tid;
4142 }
4143 spin_unlock(&sbi->s_md_lock);
4144
4145 ext4_mb_free_committed_blocks(sb);
4146}
4147
Eric Sandeen4ddfef72008-04-29 08:11:12 -04004148static noinline_for_stack int
4149ext4_mb_free_metadata(handle_t *handle, struct ext4_buddy *e4b,
Alex Tomasc9de5602008-01-29 00:19:52 -05004150 ext4_group_t group, ext4_grpblk_t block, int count)
4151{
4152 struct ext4_group_info *db = e4b->bd_info;
4153 struct super_block *sb = e4b->bd_sb;
4154 struct ext4_sb_info *sbi = EXT4_SB(sb);
4155 struct ext4_free_metadata *md;
4156 int i;
4157
4158 BUG_ON(e4b->bd_bitmap_page == NULL);
4159 BUG_ON(e4b->bd_buddy_page == NULL);
4160
4161 ext4_lock_group(sb, group);
4162 for (i = 0; i < count; i++) {
4163 md = db->bb_md_cur;
4164 if (md && db->bb_tid != handle->h_transaction->t_tid) {
4165 db->bb_md_cur = NULL;
4166 md = NULL;
4167 }
4168
4169 if (md == NULL) {
4170 ext4_unlock_group(sb, group);
4171 md = kmalloc(sizeof(*md), GFP_NOFS);
4172 if (md == NULL)
4173 return -ENOMEM;
4174 md->num = 0;
4175 md->group = group;
4176
4177 ext4_lock_group(sb, group);
4178 if (db->bb_md_cur == NULL) {
4179 spin_lock(&sbi->s_md_lock);
4180 list_add(&md->list, &sbi->s_active_transaction);
4181 spin_unlock(&sbi->s_md_lock);
4182 /* protect buddy cache from being freed,
4183 * otherwise we'll refresh it from
4184 * on-disk bitmap and lose not-yet-available
4185 * blocks */
4186 page_cache_get(e4b->bd_buddy_page);
4187 page_cache_get(e4b->bd_bitmap_page);
4188 db->bb_md_cur = md;
4189 db->bb_tid = handle->h_transaction->t_tid;
4190 mb_debug("new md 0x%p for group %lu\n",
4191 md, md->group);
4192 } else {
4193 kfree(md);
4194 md = db->bb_md_cur;
4195 }
4196 }
4197
4198 BUG_ON(md->num >= EXT4_BB_MAX_BLOCKS);
4199 md->blocks[md->num] = block + i;
4200 md->num++;
4201 if (md->num == EXT4_BB_MAX_BLOCKS) {
4202 /* no more space, put full container on a sb's list */
4203 db->bb_md_cur = NULL;
4204 }
4205 }
4206 ext4_unlock_group(sb, group);
4207 return 0;
4208}
4209
4210/*
4211 * Main entry point into mballoc to free blocks
4212 */
4213void ext4_mb_free_blocks(handle_t *handle, struct inode *inode,
4214 unsigned long block, unsigned long count,
4215 int metadata, unsigned long *freed)
4216{
Aneesh Kumar K.V26346ff2008-02-10 01:10:04 -05004217 struct buffer_head *bitmap_bh = NULL;
Alex Tomasc9de5602008-01-29 00:19:52 -05004218 struct super_block *sb = inode->i_sb;
Eric Sandeen256bdb42008-02-10 01:13:33 -05004219 struct ext4_allocation_context *ac = NULL;
Alex Tomasc9de5602008-01-29 00:19:52 -05004220 struct ext4_group_desc *gdp;
4221 struct ext4_super_block *es;
4222 unsigned long overflow;
4223 ext4_grpblk_t bit;
4224 struct buffer_head *gd_bh;
4225 ext4_group_t block_group;
4226 struct ext4_sb_info *sbi;
4227 struct ext4_buddy e4b;
4228 int err = 0;
4229 int ret;
4230
4231 *freed = 0;
4232
4233 ext4_mb_poll_new_transaction(sb, handle);
4234
4235 sbi = EXT4_SB(sb);
4236 es = EXT4_SB(sb)->s_es;
4237 if (block < le32_to_cpu(es->s_first_data_block) ||
4238 block + count < block ||
4239 block + count > ext4_blocks_count(es)) {
Harvey Harrison46e665e2008-04-17 10:38:59 -04004240 ext4_error(sb, __func__,
Alex Tomasc9de5602008-01-29 00:19:52 -05004241 "Freeing blocks not in datazone - "
4242 "block = %lu, count = %lu", block, count);
4243 goto error_return;
4244 }
4245
4246 ext4_debug("freeing block %lu\n", block);
4247
Eric Sandeen256bdb42008-02-10 01:13:33 -05004248 ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS);
4249 if (ac) {
4250 ac->ac_op = EXT4_MB_HISTORY_FREE;
4251 ac->ac_inode = inode;
4252 ac->ac_sb = sb;
4253 }
Alex Tomasc9de5602008-01-29 00:19:52 -05004254
4255do_more:
4256 overflow = 0;
4257 ext4_get_group_no_and_offset(sb, block, &block_group, &bit);
4258
4259 /*
4260 * Check to see if we are freeing blocks across a group
4261 * boundary.
4262 */
4263 if (bit + count > EXT4_BLOCKS_PER_GROUP(sb)) {
4264 overflow = bit + count - EXT4_BLOCKS_PER_GROUP(sb);
4265 count -= overflow;
4266 }
Theodore Ts'o574ca172008-07-11 19:27:31 -04004267 bitmap_bh = ext4_read_block_bitmap(sb, block_group);
Alex Tomasc9de5602008-01-29 00:19:52 -05004268 if (!bitmap_bh)
4269 goto error_return;
4270 gdp = ext4_get_group_desc(sb, block_group, &gd_bh);
4271 if (!gdp)
4272 goto error_return;
4273
4274 if (in_range(ext4_block_bitmap(sb, gdp), block, count) ||
4275 in_range(ext4_inode_bitmap(sb, gdp), block, count) ||
4276 in_range(block, ext4_inode_table(sb, gdp),
4277 EXT4_SB(sb)->s_itb_per_group) ||
4278 in_range(block + count - 1, ext4_inode_table(sb, gdp),
4279 EXT4_SB(sb)->s_itb_per_group)) {
4280
Harvey Harrison46e665e2008-04-17 10:38:59 -04004281 ext4_error(sb, __func__,
Alex Tomasc9de5602008-01-29 00:19:52 -05004282 "Freeing blocks in system zone - "
4283 "Block = %lu, count = %lu", block, count);
Aneesh Kumar K.V519deca2008-05-15 14:43:20 -04004284 /* err = 0. ext4_std_error should be a no op */
4285 goto error_return;
Alex Tomasc9de5602008-01-29 00:19:52 -05004286 }
4287
4288 BUFFER_TRACE(bitmap_bh, "getting write access");
4289 err = ext4_journal_get_write_access(handle, bitmap_bh);
4290 if (err)
4291 goto error_return;
4292
4293 /*
4294 * We are about to modify some metadata. Call the journal APIs
4295 * to unshare ->b_data if a currently-committing transaction is
4296 * using it
4297 */
4298 BUFFER_TRACE(gd_bh, "get_write_access");
4299 err = ext4_journal_get_write_access(handle, gd_bh);
4300 if (err)
4301 goto error_return;
4302
4303 err = ext4_mb_load_buddy(sb, block_group, &e4b);
4304 if (err)
4305 goto error_return;
4306
4307#ifdef AGGRESSIVE_CHECK
4308 {
4309 int i;
4310 for (i = 0; i < count; i++)
4311 BUG_ON(!mb_test_bit(bit + i, bitmap_bh->b_data));
4312 }
4313#endif
4314 mb_clear_bits(sb_bgl_lock(sbi, block_group), bitmap_bh->b_data,
4315 bit, count);
4316
4317 /* We dirtied the bitmap block */
4318 BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
4319 err = ext4_journal_dirty_metadata(handle, bitmap_bh);
4320
Eric Sandeen256bdb42008-02-10 01:13:33 -05004321 if (ac) {
4322 ac->ac_b_ex.fe_group = block_group;
4323 ac->ac_b_ex.fe_start = bit;
4324 ac->ac_b_ex.fe_len = count;
4325 ext4_mb_store_history(ac);
4326 }
Alex Tomasc9de5602008-01-29 00:19:52 -05004327
4328 if (metadata) {
4329 /* blocks being freed are metadata. these blocks shouldn't
4330 * be used until this transaction is committed */
4331 ext4_mb_free_metadata(handle, &e4b, block_group, bit, count);
4332 } else {
4333 ext4_lock_group(sb, block_group);
Shen Feng7e5a8cd2008-07-13 21:03:31 -04004334 mb_free_blocks(inode, &e4b, bit, count);
Alex Tomasc9de5602008-01-29 00:19:52 -05004335 ext4_mb_return_to_preallocation(inode, &e4b, block, count);
4336 ext4_unlock_group(sb, block_group);
Alex Tomasc9de5602008-01-29 00:19:52 -05004337 }
4338
4339 spin_lock(sb_bgl_lock(sbi, block_group));
Marcin Slusarze8546d02008-04-17 10:38:59 -04004340 le16_add_cpu(&gdp->bg_free_blocks_count, count);
Alex Tomasc9de5602008-01-29 00:19:52 -05004341 gdp->bg_checksum = ext4_group_desc_csum(sbi, block_group, gdp);
4342 spin_unlock(sb_bgl_lock(sbi, block_group));
4343 percpu_counter_add(&sbi->s_freeblocks_counter, count);
4344
4345 ext4_mb_release_desc(&e4b);
4346
4347 *freed += count;
4348
4349 /* And the group descriptor block */
4350 BUFFER_TRACE(gd_bh, "dirtied group descriptor block");
4351 ret = ext4_journal_dirty_metadata(handle, gd_bh);
4352 if (!err)
4353 err = ret;
4354
4355 if (overflow && !err) {
4356 block += count;
4357 count = overflow;
4358 put_bh(bitmap_bh);
4359 goto do_more;
4360 }
4361 sb->s_dirt = 1;
4362error_return:
4363 brelse(bitmap_bh);
4364 ext4_std_error(sb, err);
Eric Sandeen256bdb42008-02-10 01:13:33 -05004365 if (ac)
4366 kmem_cache_free(ext4_ac_cachep, ac);
Alex Tomasc9de5602008-01-29 00:19:52 -05004367 return;
4368}