mballoc.c 143 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
/*
 * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
 * Written by Alex Tomas <alex@clusterfs.com>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public Licens
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-
 */


/*
 * mballoc.c contains the multiblocks allocation routines
 */

Bobi Jam's avatar
Bobi Jam committed
24
#include "ext4_jbd2.h"
25
#include "mballoc.h"
26
#include <linux/log2.h>
27
#include <linux/module.h>
28
#include <linux/slab.h>
29 30
#include <trace/events/ext4.h>

31 32 33 34 35 36 37
#ifdef CONFIG_EXT4_DEBUG
ushort ext4_mballoc_debug __read_mostly;

module_param_named(mballoc_debug, ext4_mballoc_debug, ushort, 0644);
MODULE_PARM_DESC(mballoc_debug, "Debugging level for ext4's mballoc");
#endif

38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
/*
 * MUSTDO:
 *   - test ext4_ext_search_left() and ext4_ext_search_right()
 *   - search for metadata in few groups
 *
 * TODO v4:
 *   - normalization should take into account whether file is still open
 *   - discard preallocations if no free space left (policy?)
 *   - don't normalize tails
 *   - quota
 *   - reservation for superuser
 *
 * TODO v3:
 *   - bitmap read-ahead (proposed by Oleg Drokin aka green)
 *   - track min/max extents in each group for better group selection
 *   - mb_mark_used() may allocate chunk right after splitting buddy
 *   - tree of groups sorted by number of free blocks
 *   - error handling
 */

/*
 * The allocation request involve request for multiple number of blocks
 * near to the goal(block) value specified.
 *
62 63 64 65 66 67 68 69 70
 * During initialization phase of the allocator we decide to use the
 * group preallocation or inode preallocation depending on the size of
 * the file. The size of the file could be the resulting file size we
 * would have after allocation, or the current file size, which ever
 * is larger. If the size is less than sbi->s_mb_stream_request we
 * select to use the group preallocation. The default value of
 * s_mb_stream_request is 16 blocks. This can also be tuned via
 * /sys/fs/ext4/<partition>/mb_stream_req. The value is represented in
 * terms of number of blocks.
71 72
 *
 * The main motivation for having small file use group preallocation is to
73
 * ensure that we have small files closer together on the disk.
74
 *
75 76 77 78
 * First stage the allocator looks at the inode prealloc list,
 * ext4_inode_info->i_prealloc_list, which contains list of prealloc
 * spaces for this particular inode. The inode prealloc space is
 * represented as:
79 80 81
 *
 * pa_lstart -> the logical start block for this prealloc space
 * pa_pstart -> the physical start block for this prealloc space
82 83
 * pa_len    -> length for this prealloc space (in clusters)
 * pa_free   ->  free space available in this prealloc space (in clusters)
84 85 86
 *
 * The inode preallocation space is used looking at the _logical_ start
 * block. If only the logical file block falls within the range of prealloc
87 88
 * space we will consume the particular prealloc space. This makes sure that
 * we have contiguous physical blocks representing the file blocks
89 90 91 92 93 94 95
 *
 * The important thing to be noted in case of inode prealloc space is that
 * we don't modify the values associated to inode prealloc space except
 * pa_free.
 *
 * If we are not able to find blocks in the inode prealloc space and if we
 * have the group allocation flag set then we look at the locality group
96
 * prealloc space. These are per CPU prealloc list represented as
97 98 99 100 101 102 103
 *
 * ext4_sb_info.s_locality_groups[smp_processor_id()]
 *
 * The reason for having a per cpu locality group is to reduce the contention
 * between CPUs. It is possible to get scheduled at this point.
 *
 * The locality group prealloc space is used looking at whether we have
Lucas De Marchi's avatar
Lucas De Marchi committed
104
 * enough free space (pa_free) within the prealloc space.
105 106 107 108 109 110 111 112 113 114 115 116
 *
 * If we can't allocate blocks via inode prealloc or/and locality group
 * prealloc then we look at the buddy cache. The buddy cache is represented
 * by ext4_sb_info.s_buddy_cache (struct inode) whose file offset gets
 * mapped to the buddy and bitmap information regarding different
 * groups. The buddy information is attached to buddy cache inode so that
 * we can access them through the page cache. The information regarding
 * each group is loaded via ext4_mb_load_buddy.  The information involve
 * block bitmap and buddy information. The information are stored in the
 * inode as:
 *
 *  {                        page                        }
117
 *  [ group 0 bitmap][ group 0 buddy] [group 1][ group 1]...
118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137
 *
 *
 * one block each for bitmap and buddy information.  So for each group we
 * take up 2 blocks. A page can contain blocks_per_page (PAGE_CACHE_SIZE /
 * blocksize) blocks.  So it can have information regarding groups_per_page
 * which is blocks_per_page/2
 *
 * The buddy cache inode is not stored on disk. The inode is thrown
 * away when the filesystem is unmounted.
 *
 * We look for count number of blocks in the buddy cache. If we were able
 * to locate that many free blocks we return with additional information
 * regarding rest of the contiguous physical block available
 *
 * Before allocating blocks via buddy cache we normalize the request
 * blocks. This ensure we ask for more blocks that we needed. The extra
 * blocks that we get after allocation is added to the respective prealloc
 * list. In case of inode preallocation we follow a list of heuristics
 * based on file size. This can be found in ext4_mb_normalize_request. If
 * we are doing a group prealloc we try to normalize the request to
138 139
 * sbi->s_mb_group_prealloc.  The default value of s_mb_group_prealloc is
 * dependent on the cluster size; for non-bigalloc file systems, it is
140
 * 512 blocks. This can be tuned via
141
 * /sys/fs/ext4/<partition>/mb_group_prealloc. The value is represented in
142 143
 * terms of number of blocks. If we have mounted the file system with -O
 * stripe=<value> option the group prealloc request is normalized to the
144 145
 * the smallest multiple of the stripe value (sbi->s_stripe) which is
 * greater than the default mb_group_prealloc.
146
 *
147
 * The regular allocator (using the buddy cache) supports a few tunables.
148
 *
149 150 151
 * /sys/fs/ext4/<partition>/mb_min_to_scan
 * /sys/fs/ext4/<partition>/mb_max_to_scan
 * /sys/fs/ext4/<partition>/mb_order2_req
152
 *
153
 * The regular allocator uses buddy scan only if the request len is power of
154 155
 * 2 blocks and the order of allocation is >= sbi->s_mb_order2_reqs. The
 * value of s_mb_order2_reqs can be tuned via
156
 * /sys/fs/ext4/<partition>/mb_order2_req.  If the request len is equal to
157
 * stripe size (sbi->s_stripe), we try to search for contiguous block in
158 159 160
 * stripe size. This should result in better allocation on RAID setups. If
 * not, we search in the specific group using bitmap for best extents. The
 * tunable min_to_scan and max_to_scan control the behaviour here.
161
 * min_to_scan indicate how long the mballoc __must__ look for a best
162
 * extent and max_to_scan indicates how long the mballoc __can__ look for a
163 164 165
 * best extent in the found extents. Searching for the blocks starts with
 * the group specified as the goal value in allocation context via
 * ac_g_ex. Each group is first checked based on the criteria whether it
166
 * can be used for allocation. ext4_mb_good_group explains how the groups are
167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348
 * checked.
 *
 * Both the prealloc space are getting populated as above. So for the first
 * request we will hit the buddy cache which will result in this prealloc
 * space getting filled. The prealloc space is then later used for the
 * subsequent request.
 */

/*
 * mballoc operates on the following data:
 *  - on-disk bitmap
 *  - in-core buddy (actually includes buddy and bitmap)
 *  - preallocation descriptors (PAs)
 *
 * there are two types of preallocations:
 *  - inode
 *    assiged to specific inode and can be used for this inode only.
 *    it describes part of inode's space preallocated to specific
 *    physical blocks. any block from that preallocated can be used
 *    independent. the descriptor just tracks number of blocks left
 *    unused. so, before taking some block from descriptor, one must
 *    make sure corresponded logical block isn't allocated yet. this
 *    also means that freeing any block within descriptor's range
 *    must discard all preallocated blocks.
 *  - locality group
 *    assigned to specific locality group which does not translate to
 *    permanent set of inodes: inode can join and leave group. space
 *    from this type of preallocation can be used for any inode. thus
 *    it's consumed from the beginning to the end.
 *
 * relation between them can be expressed as:
 *    in-core buddy = on-disk bitmap + preallocation descriptors
 *
 * this mean blocks mballoc considers used are:
 *  - allocated blocks (persistent)
 *  - preallocated blocks (non-persistent)
 *
 * consistency in mballoc world means that at any time a block is either
 * free or used in ALL structures. notice: "any time" should not be read
 * literally -- time is discrete and delimited by locks.
 *
 *  to keep it simple, we don't use block numbers, instead we count number of
 *  blocks: how many blocks marked used/free in on-disk bitmap, buddy and PA.
 *
 * all operations can be expressed as:
 *  - init buddy:			buddy = on-disk + PAs
 *  - new PA:				buddy += N; PA = N
 *  - use inode PA:			on-disk += N; PA -= N
 *  - discard inode PA			buddy -= on-disk - PA; PA = 0
 *  - use locality group PA		on-disk += N; PA -= N
 *  - discard locality group PA		buddy -= PA; PA = 0
 *  note: 'buddy -= on-disk - PA' is used to show that on-disk bitmap
 *        is used in real operation because we can't know actual used
 *        bits from PA, only from on-disk bitmap
 *
 * if we follow this strict logic, then all operations above should be atomic.
 * given some of them can block, we'd have to use something like semaphores
 * killing performance on high-end SMP hardware. let's try to relax it using
 * the following knowledge:
 *  1) if buddy is referenced, it's already initialized
 *  2) while block is used in buddy and the buddy is referenced,
 *     nobody can re-allocate that block
 *  3) we work on bitmaps and '+' actually means 'set bits'. if on-disk has
 *     bit set and PA claims same block, it's OK. IOW, one can set bit in
 *     on-disk bitmap if buddy has same bit set or/and PA covers corresponded
 *     block
 *
 * so, now we're building a concurrency table:
 *  - init buddy vs.
 *    - new PA
 *      blocks for PA are allocated in the buddy, buddy must be referenced
 *      until PA is linked to allocation group to avoid concurrent buddy init
 *    - use inode PA
 *      we need to make sure that either on-disk bitmap or PA has uptodate data
 *      given (3) we care that PA-=N operation doesn't interfere with init
 *    - discard inode PA
 *      the simplest way would be to have buddy initialized by the discard
 *    - use locality group PA
 *      again PA-=N must be serialized with init
 *    - discard locality group PA
 *      the simplest way would be to have buddy initialized by the discard
 *  - new PA vs.
 *    - use inode PA
 *      i_data_sem serializes them
 *    - discard inode PA
 *      discard process must wait until PA isn't used by another process
 *    - use locality group PA
 *      some mutex should serialize them
 *    - discard locality group PA
 *      discard process must wait until PA isn't used by another process
 *  - use inode PA
 *    - use inode PA
 *      i_data_sem or another mutex should serializes them
 *    - discard inode PA
 *      discard process must wait until PA isn't used by another process
 *    - use locality group PA
 *      nothing wrong here -- they're different PAs covering different blocks
 *    - discard locality group PA
 *      discard process must wait until PA isn't used by another process
 *
 * now we're ready to make few consequences:
 *  - PA is referenced and while it is no discard is possible
 *  - PA is referenced until block isn't marked in on-disk bitmap
 *  - PA changes only after on-disk bitmap
 *  - discard must not compete with init. either init is done before
 *    any discard or they're serialized somehow
 *  - buddy init as sum of on-disk bitmap and PAs is done atomically
 *
 * a special case when we've used PA to emptiness. no need to modify buddy
 * in this case, but we should care about concurrent init
 *
 */

 /*
 * Logic in few words:
 *
 *  - allocation:
 *    load group
 *    find blocks
 *    mark bits in on-disk bitmap
 *    release group
 *
 *  - use preallocation:
 *    find proper PA (per-inode or group)
 *    load group
 *    mark bits in on-disk bitmap
 *    release group
 *    release PA
 *
 *  - free:
 *    load group
 *    mark bits in on-disk bitmap
 *    release group
 *
 *  - discard preallocations in group:
 *    mark PAs deleted
 *    move them onto local list
 *    load on-disk bitmap
 *    load group
 *    remove PA from object (inode or locality group)
 *    mark free blocks in-core
 *
 *  - discard inode's preallocations:
 */

/*
 * Locking rules
 *
 * Locks:
 *  - bitlock on a group	(group)
 *  - object (inode/locality)	(object)
 *  - per-pa lock		(pa)
 *
 * Paths:
 *  - new pa
 *    object
 *    group
 *
 *  - find and use pa:
 *    pa
 *
 *  - release consumed pa:
 *    pa
 *    group
 *    object
 *
 *  - generate in-core bitmap:
 *    group
 *        pa
 *
 *  - discard all for given object (inode, locality group):
 *    object
 *        pa
 *    group
 *
 *  - discard all for given group:
 *    group
 *        pa
 *    group
 *        object
 *
 */
349 350
static struct kmem_cache *ext4_pspace_cachep;
static struct kmem_cache *ext4_ac_cachep;
Bobi Jam's avatar
Bobi Jam committed
351
static struct kmem_cache *ext4_free_data_cachep;
352 353 354 355

/* We create slab caches for groupinfo data structures based on the
 * superblock block size.  There will be one per mounted filesystem for
 * each unique s_blocksize_bits */
356
#define NR_GRPINFO_CACHES 8
357 358
static struct kmem_cache *ext4_groupinfo_caches[NR_GRPINFO_CACHES];

359 360 361 362 363 364
static const char *ext4_groupinfo_slab_names[NR_GRPINFO_CACHES] = {
	"ext4_groupinfo_1k", "ext4_groupinfo_2k", "ext4_groupinfo_4k",
	"ext4_groupinfo_8k", "ext4_groupinfo_16k", "ext4_groupinfo_32k",
	"ext4_groupinfo_64k", "ext4_groupinfo_128k"
};

365 366
static void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,
					ext4_group_t group);
367 368
static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
						ext4_group_t group);
Bobi Jam's avatar
Bobi Jam committed
369 370
static void ext4_free_data_callback(struct super_block *sb,
				struct ext4_journal_cb_entry *jce, int rc);
371

372 373
static inline void *mb_correct_addr_and_bit(int *bit, void *addr)
{
374
#if BITS_PER_LONG == 64
375 376
	*bit += ((unsigned long) addr & 7UL) << 3;
	addr = (void *) ((unsigned long) addr & ~7UL);
377
#elif BITS_PER_LONG == 32
378 379
	*bit += ((unsigned long) addr & 3UL) << 3;
	addr = (void *) ((unsigned long) addr & ~3UL);
380 381 382
#else
#error "how many bits you are?!"
#endif
383 384
	return addr;
}
385 386 387 388 389 390 391

static inline int mb_test_bit(int bit, void *addr)
{
	/*
	 * ext4_test_bit on architecture like powerpc
	 * needs unsigned long aligned address
	 */
392
	addr = mb_correct_addr_and_bit(&bit, addr);
393 394 395 396 397
	return ext4_test_bit(bit, addr);
}

static inline void mb_set_bit(int bit, void *addr)
{
398
	addr = mb_correct_addr_and_bit(&bit, addr);
399 400 401 402 403
	ext4_set_bit(bit, addr);
}

static inline void mb_clear_bit(int bit, void *addr)
{
404
	addr = mb_correct_addr_and_bit(&bit, addr);
405 406 407
	ext4_clear_bit(bit, addr);
}

408 409 410 411 412 413
static inline int mb_test_and_clear_bit(int bit, void *addr)
{
	addr = mb_correct_addr_and_bit(&bit, addr);
	return ext4_test_and_clear_bit(bit, addr);
}

414 415
static inline int mb_find_next_zero_bit(void *addr, int max, int start)
{
416
	int fix = 0, ret, tmpmax;
417
	addr = mb_correct_addr_and_bit(&fix, addr);
418
	tmpmax = max + fix;
419 420
	start += fix;

421 422 423 424
	ret = ext4_find_next_zero_bit(addr, tmpmax, start) - fix;
	if (ret > max)
		return max;
	return ret;
425 426 427 428
}

static inline int mb_find_next_bit(void *addr, int max, int start)
{
429
	int fix = 0, ret, tmpmax;
430
	addr = mb_correct_addr_and_bit(&fix, addr);
431
	tmpmax = max + fix;
432 433
	start += fix;

434 435 436 437
	ret = ext4_find_next_bit(addr, tmpmax, start) - fix;
	if (ret > max)
		return max;
	return ret;
438 439
}

440 441 442 443
static void *mb_find_buddy(struct ext4_buddy *e4b, int order, int *max)
{
	char *bb;

444
	BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);
445 446 447 448 449 450 451 452
	BUG_ON(max == NULL);

	if (order > e4b->bd_blkbits + 1) {
		*max = 0;
		return NULL;
	}

	/* at order 0 we see each particular block */
453 454
	if (order == 0) {
		*max = 1 << (e4b->bd_blkbits + 3);
455
		return e4b->bd_bitmap;
456
	}
457

458
	bb = e4b->bd_buddy + EXT4_SB(e4b->bd_sb)->s_mb_offsets[order];
459 460 461 462 463 464 465 466 467 468 469 470 471 472
	*max = EXT4_SB(e4b->bd_sb)->s_mb_maxs[order];

	return bb;
}

#ifdef DOUBLE_CHECK
static void mb_free_blocks_double(struct inode *inode, struct ext4_buddy *e4b,
			   int first, int count)
{
	int i;
	struct super_block *sb = e4b->bd_sb;

	if (unlikely(e4b->bd_info->bb_bitmap == NULL))
		return;
473
	assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));
474 475 476
	for (i = 0; i < count; i++) {
		if (!mb_test_bit(first + i, e4b->bd_info->bb_bitmap)) {
			ext4_fsblk_t blocknr;
477 478

			blocknr = ext4_group_first_block_no(sb, e4b->bd_group);
479
			blocknr += EXT4_C2B(EXT4_SB(sb), first + i);
480
			ext4_grp_locked_error(sb, e4b->bd_group,
481 482 483 484 485
					      inode ? inode->i_ino : 0,
					      blocknr,
					      "freeing block already freed "
					      "(bit %u)",
					      first + i);
486 487 488 489 490 491 492 493 494 495 496
		}
		mb_clear_bit(first + i, e4b->bd_info->bb_bitmap);
	}
}

static void mb_mark_used_double(struct ext4_buddy *e4b, int first, int count)
{
	int i;

	if (unlikely(e4b->bd_info->bb_bitmap == NULL))
		return;
497
	assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
498 499 500 501 502 503 504 505 506 507 508 509 510 511 512
	for (i = 0; i < count; i++) {
		BUG_ON(mb_test_bit(first + i, e4b->bd_info->bb_bitmap));
		mb_set_bit(first + i, e4b->bd_info->bb_bitmap);
	}
}

static void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap)
{
	if (memcmp(e4b->bd_info->bb_bitmap, bitmap, e4b->bd_sb->s_blocksize)) {
		unsigned char *b1, *b2;
		int i;
		b1 = (unsigned char *) e4b->bd_info->bb_bitmap;
		b2 = (unsigned char *) bitmap;
		for (i = 0; i < e4b->bd_sb->s_blocksize; i++) {
			if (b1[i] != b2[i]) {
513 514 515 516 517
				ext4_msg(e4b->bd_sb, KERN_ERR,
					 "corruption in group %u "
					 "at byte %u(%u): %x in copy != %x "
					 "on disk/prealloc",
					 e4b->bd_group, i, i * 8, b1[i], b2[i]);
518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599
				BUG();
			}
		}
	}
}

#else
static inline void mb_free_blocks_double(struct inode *inode,
				struct ext4_buddy *e4b, int first, int count)
{
	return;
}
static inline void mb_mark_used_double(struct ext4_buddy *e4b,
						int first, int count)
{
	return;
}
static inline void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap)
{
	return;
}
#endif

#ifdef AGGRESSIVE_CHECK

#define MB_CHECK_ASSERT(assert)						\
do {									\
	if (!(assert)) {						\
		printk(KERN_EMERG					\
			"Assertion failure in %s() at %s:%d: \"%s\"\n",	\
			function, file, line, # assert);		\
		BUG();							\
	}								\
} while (0)

static int __mb_check_buddy(struct ext4_buddy *e4b, char *file,
				const char *function, int line)
{
	struct super_block *sb = e4b->bd_sb;
	int order = e4b->bd_blkbits + 1;
	int max;
	int max2;
	int i;
	int j;
	int k;
	int count;
	struct ext4_group_info *grp;
	int fragments = 0;
	int fstart;
	struct list_head *cur;
	void *buddy;
	void *buddy2;

	{
		static int mb_check_counter;
		if (mb_check_counter++ % 100 != 0)
			return 0;
	}

	while (order > 1) {
		buddy = mb_find_buddy(e4b, order, &max);
		MB_CHECK_ASSERT(buddy);
		buddy2 = mb_find_buddy(e4b, order - 1, &max2);
		MB_CHECK_ASSERT(buddy2);
		MB_CHECK_ASSERT(buddy != buddy2);
		MB_CHECK_ASSERT(max * 2 == max2);

		count = 0;
		for (i = 0; i < max; i++) {

			if (mb_test_bit(i, buddy)) {
				/* only single bit in buddy2 may be 1 */
				if (!mb_test_bit(i << 1, buddy2)) {
					MB_CHECK_ASSERT(
						mb_test_bit((i<<1)+1, buddy2));
				} else if (!mb_test_bit((i << 1) + 1, buddy2)) {
					MB_CHECK_ASSERT(
						mb_test_bit(i << 1, buddy2));
				}
				continue;
			}

600
			/* both bits in buddy2 must be 1 */
601 602 603 604 605 606
			MB_CHECK_ASSERT(mb_test_bit(i << 1, buddy2));
			MB_CHECK_ASSERT(mb_test_bit((i << 1) + 1, buddy2));

			for (j = 0; j < (1 << order); j++) {
				k = (i * (1 << order)) + j;
				MB_CHECK_ASSERT(
607
					!mb_test_bit(k, e4b->bd_bitmap));
608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641
			}
			count++;
		}
		MB_CHECK_ASSERT(e4b->bd_info->bb_counters[order] == count);
		order--;
	}

	fstart = -1;
	buddy = mb_find_buddy(e4b, 0, &max);
	for (i = 0; i < max; i++) {
		if (!mb_test_bit(i, buddy)) {
			MB_CHECK_ASSERT(i >= e4b->bd_info->bb_first_free);
			if (fstart == -1) {
				fragments++;
				fstart = i;
			}
			continue;
		}
		fstart = -1;
		/* check used bits only */
		for (j = 0; j < e4b->bd_blkbits + 1; j++) {
			buddy2 = mb_find_buddy(e4b, j, &max2);
			k = i >> j;
			MB_CHECK_ASSERT(k < max2);
			MB_CHECK_ASSERT(mb_test_bit(k, buddy2));
		}
	}
	MB_CHECK_ASSERT(!EXT4_MB_GRP_NEED_INIT(e4b->bd_info));
	MB_CHECK_ASSERT(e4b->bd_info->bb_fragments == fragments);

	grp = ext4_get_group_info(sb, e4b->bd_group);
	list_for_each(cur, &grp->bb_prealloc_list) {
		ext4_group_t groupnr;
		struct ext4_prealloc_space *pa;
642 643
		pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
		ext4_get_group_no_and_offset(sb, pa->pa_pstart, &groupnr, &k);
644
		MB_CHECK_ASSERT(groupnr == e4b->bd_group);
645
		for (i = 0; i < pa->pa_len; i++)
646 647 648 649 650 651
			MB_CHECK_ASSERT(mb_test_bit(k + i, buddy));
	}
	return 0;
}
#undef MB_CHECK_ASSERT
#define mb_check_buddy(e4b) __mb_check_buddy(e4b,	\
652
					__FILE__, __func__, __LINE__)
653 654 655 656
#else
#define mb_check_buddy(e4b)
#endif

657 658 659 660 661 662
/*
 * Divide blocks started from @first with length @len into
 * smaller chunks with power of 2 blocks.
 * Clear the bits in bitmap which the blocks of the chunk(s) covered,
 * then increase bb_counters[] for corresponded chunk size.
 */
663
static void ext4_mb_mark_free_simple(struct super_block *sb,
664
				void *buddy, ext4_grpblk_t first, ext4_grpblk_t len,
665 666 667
					struct ext4_group_info *grp)
{
	struct ext4_sb_info *sbi = EXT4_SB(sb);
668 669 670
	ext4_grpblk_t min;
	ext4_grpblk_t max;
	ext4_grpblk_t chunk;
671
	unsigned int border;
672

673
	BUG_ON(len > EXT4_CLUSTERS_PER_GROUP(sb));
674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698

	border = 2 << sb->s_blocksize_bits;

	while (len > 0) {
		/* find how many blocks can be covered since this position */
		max = ffs(first | border) - 1;

		/* find how many blocks of power 2 we need to mark */
		min = fls(len) - 1;

		if (max < min)
			min = max;
		chunk = 1 << min;

		/* mark multiblock chunks only */
		grp->bb_counters[min]++;
		if (min > 0)
			mb_clear_bit(first >> min,
				     buddy + sbi->s_mb_offsets[min]);

		len -= chunk;
		first += chunk;
	}
}

699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719
/*
 * Cache the order of the largest free extent we have available in this block
 * group.
 */
static void
mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
{
	int i;
	int bits;

	grp->bb_largest_free_order = -1; /* uninit */

	bits = sb->s_blocksize_bits + 1;
	for (i = bits; i >= 0; i--) {
		if (grp->bb_counters[i] > 0) {
			grp->bb_largest_free_order = i;
			break;
		}
	}
}

720 721
static noinline_for_stack
void ext4_mb_generate_buddy(struct super_block *sb,
722 723 724
				void *buddy, void *bitmap, ext4_group_t group)
{
	struct ext4_group_info *grp = ext4_get_group_info(sb, group);
725
	struct ext4_sb_info *sbi = EXT4_SB(sb);
726
	ext4_grpblk_t max = EXT4_CLUSTERS_PER_GROUP(sb);
727 728 729
	ext4_grpblk_t i = 0;
	ext4_grpblk_t first;
	ext4_grpblk_t len;
730 731 732 733 734 735
	unsigned free = 0;
	unsigned fragments = 0;
	unsigned long long period = get_cycles();

	/* initialize buddy from bitmap which is aggregation
	 * of on-disk bitmap and preallocations */
736
	i = mb_find_next_zero_bit(bitmap, max, 0);
737 738 739 740
	grp->bb_first_free = i;
	while (i < max) {
		fragments++;
		first = i;
741
		i = mb_find_next_bit(bitmap, max, i);
742 743 744 745 746 747 748
		len = i - first;
		free += len;
		if (len > 1)
			ext4_mb_mark_free_simple(sb, buddy, first, len, grp);
		else
			grp->bb_counters[0]++;
		if (i < max)
749
			i = mb_find_next_zero_bit(bitmap, max, i);
750 751 752 753
	}
	grp->bb_fragments = fragments;

	if (free != grp->bb_free) {
754
		ext4_grp_locked_error(sb, group, 0, 0,
755 756
				      "block bitmap and bg descriptor "
				      "inconsistent: %u vs %u free clusters",
757
				      free, grp->bb_free);
758
		/*
759
		 * If we intend to continue, we consider group descriptor
760 761
		 * corrupt and update bb_free using bitmap value
		 */
762
		grp->bb_free = free;
763 764 765
		if (!EXT4_MB_GRP_BBITMAP_CORRUPT(grp))
			percpu_counter_sub(&sbi->s_freeclusters_counter,
					   grp->bb_free);
766
		set_bit(EXT4_GROUP_INFO_BBITMAP_CORRUPT_BIT, &grp->bb_state);
767
	}
768
	mb_set_largest_free_order(sb, grp);
769 770 771 772 773 774 775 776 777 778

	clear_bit(EXT4_GROUP_INFO_NEED_INIT_BIT, &(grp->bb_state));

	period = get_cycles() - period;
	spin_lock(&EXT4_SB(sb)->s_bal_lock);
	EXT4_SB(sb)->s_mb_buddies_generated++;
	EXT4_SB(sb)->s_mb_generation_time += period;
	spin_unlock(&EXT4_SB(sb)->s_bal_lock);
}

779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796
static void mb_regenerate_buddy(struct ext4_buddy *e4b)
{
	int count;
	int order = 1;
	void *buddy;

	while ((buddy = mb_find_buddy(e4b, order++, &count))) {
		ext4_set_bits(buddy, 0, count);
	}
	e4b->bd_info->bb_fragments = 0;
	memset(e4b->bd_info->bb_counters, 0,
		sizeof(*e4b->bd_info->bb_counters) *
		(e4b->bd_sb->s_blocksize_bits + 2));

	ext4_mb_generate_buddy(e4b->bd_sb, e4b->bd_buddy,
		e4b->bd_bitmap, e4b->bd_group);
}

797 798 799 800 801 802 803
/* The buddy information is attached the buddy cache inode
 * for convenience. The information regarding each group
 * is loaded via ext4_mb_load_buddy. The information involve
 * block bitmap and buddy information. The information are
 * stored in the inode as
 *
 * {                        page                        }
804
 * [ group 0 bitmap][ group 0 buddy] [group 1][ group 1]...
805 806 807 808 809 810 811
 *
 *
 * one block each for bitmap and buddy information.
 * So for each group we take up 2 blocks. A page can
 * contain blocks_per_page (PAGE_CACHE_SIZE / blocksize)  blocks.
 * So it can have information regarding groups_per_page which
 * is blocks_per_page/2
812 813 814
 *
 * Locking note:  This routine takes the block group lock of all groups
 * for this page; do not hold this lock when calling this routine!
815 816 817 818
 */

static int ext4_mb_init_cache(struct page *page, char *incore)
{
819
	ext4_group_t ngroups;
820 821 822 823 824
	int blocksize;
	int blocks_per_page;
	int groups_per_page;
	int err = 0;
	int i;
825
	ext4_group_t first_group, group;
826 827 828
	int first_block;
	struct super_block *sb;
	struct buffer_head *bhs;
829
	struct buffer_head **bh = NULL;
830 831 832
	struct inode *inode;
	char *data;
	char *bitmap;
833
	struct ext4_group_info *grinfo;
834

835
	mb_debug(1, "init page %lu\n", page->index);
836 837 838

	inode = page->mapping->host;
	sb = inode->i_sb;
839
	ngroups = ext4_get_groups_count(sb);
840 841 842 843 844 845 846 847 848 849 850
	blocksize = 1 << inode->i_blkbits;
	blocks_per_page = PAGE_CACHE_SIZE / blocksize;

	groups_per_page = blocks_per_page >> 1;
	if (groups_per_page == 0)
		groups_per_page = 1;

	/* allocate buffer_heads to read bitmaps */
	if (groups_per_page > 1) {
		i = sizeof(struct buffer_head *) * groups_per_page;
		bh = kzalloc(i, GFP_NOFS);
851 852
		if (bh == NULL) {
			err = -ENOMEM;
853
			goto out;
854
		}
855 856 857 858 859 860
	} else
		bh = &bhs;

	first_group = page->index * blocks_per_page / 2;

	/* read all groups the page covers into the cache */
861 862
	for (i = 0, group = first_group; i < groups_per_page; i++, group++) {
		if (group >= ngroups)
863 864
			break;

865
		grinfo = ext4_get_group_info(sb, group);
866 867 868 869 870 871 872 873 874 875
		/*
		 * If page is uptodate then we came here after online resize
		 * which added some new uninitialized group info structs, so
		 * we must skip all initialized uptodate buddies on the page,
		 * which may be currently in use by an allocating task.
		 */
		if (PageUptodate(page) && !EXT4_MB_GRP_NEED_INIT(grinfo)) {
			bh[i] = NULL;
			continue;
		}
876 877
		if (!(bh[i] = ext4_read_block_bitmap_nowait(sb, group))) {
			err = -ENOMEM;
878
			goto out;
879
		}
880
		mb_debug(1, "read bitmap for group %u\n", group);
881 882 883
	}

	/* wait for I/O completion */
884 885 886
	for (i = 0, group = first_group; i < groups_per_page; i++, group++) {
		if (bh[i] && ext4_wait_block_bitmap(sb, group, bh[i])) {
			err = -EIO;
887
			goto out;
888 889
		}
	}
890 891 892 893

	first_block = page->index * blocks_per_page;
	for (i = 0; i < blocks_per_page; i++) {
		group = (first_block + i) >> 1;
894
		if (group >= ngroups)
895 896
			break;

897 898 899 900
		if (!bh[group - first_group])
			/* skip initialized uptodate buddy */
			continue;

901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916
		/*
		 * data carry information regarding this
		 * particular group in the format specified
		 * above
		 *
		 */
		data = page_address(page) + (i * blocksize);
		bitmap = bh[group - first_group]->b_data;

		/*
		 * We place the buddy block and bitmap block
		 * close together
		 */
		if ((first_block + i) & 1) {
			/* this is block of buddy */
			BUG_ON(incore == NULL);
917
			mb_debug(1, "put buddy for group %u in page %lu/%x\n",
918
				group, page->index, i * blocksize);
919
			trace_ext4_mb_buddy_bitmap_load(sb, group);
920 921 922
			grinfo = ext4_get_group_info(sb, group);
			grinfo->bb_fragments = 0;
			memset(grinfo->bb_counters, 0,
923 924
			       sizeof(*grinfo->bb_counters) *
				(sb->s_blocksize_bits+2));
925 926 927
			/*
			 * incore got set to the group block bitmap below
			 */
928
			ext4_lock_group(sb, group);
929 930
			/* init the buddy */
			memset(data, 0xff, blocksize);
931
			ext4_mb_generate_buddy(sb, data, incore, group);
932
			ext4_unlock_group(sb, group);
933 934 935 936
			incore = NULL;
		} else {
			/* this is block of bitmap */
			BUG_ON(incore != NULL);
937
			mb_debug(1, "put bitmap for group %u in page %lu/%x\n",
938
				group, page->index, i * blocksize);
939
			trace_ext4_mb_bitmap_load(sb, group);
940 941 942 943 944 945 946

			/* see comments in ext4_mb_put_pa() */
			ext4_lock_group(sb, group);
			memcpy(data, bitmap, blocksize);

			/* mark all preallocated blks used in in-core bitmap */
			ext4_mb_generate_from_pa(sb, data, group);
947
			ext4_mb_generate_from_freelist(sb, data, group);
948 949 950 951 952 953 954 955 956 957 958 959
			ext4_unlock_group(sb, group);

			/* set incore so that the buddy information can be
			 * generated using this
			 */
			incore = data;
		}
	}
	SetPageUptodate(page);

out:
	if (bh) {
960
		for (i = 0; i < groups_per_page; i++)
961 962 963 964 965 966 967
			brelse(bh[i]);
		if (bh != &bhs)
			kfree(bh);
	}
	return err;
}

968
/*
969 970 971 972
 * Lock the buddy and bitmap pages. This make sure other parallel init_group
 * on the same buddy page doesn't happen whild holding the buddy page lock.
 * Return locked buddy and bitmap pages on e4b struct. If buddy and bitmap
 * are on the same page e4b->bd_buddy_page is NULL and return value is 0.
973
 */
974 975
static int ext4_mb_get_buddy_page_lock(struct super_block *sb,
		ext4_group_t group, struct ext4_buddy *e4b)
976
{
977 978
	struct inode *inode = EXT4_SB(sb)->s_buddy_cache;
	int block, pnum, poff;
979
	int blocks_per_page;
980 981 982 983
	struct page *page;

	e4b->bd_buddy_page = NULL;
	e4b->bd_bitmap_page = NULL;
984 985 986 987 988 989 990 991 992

	blocks_per_page = PAGE_CACHE_SIZE / sb->s_blocksize;
	/*
	 * the buddy cache inode stores the block bitmap
	 * and buddy information in consecutive blocks.
	 * So for each group we need two blocks.
	 */
	block = group * 2;
	pnum = block / blocks_per_page;
993 994 995
	poff = block % blocks_per_page;
	page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
	if (!page)
996
		return -ENOMEM;
997 998 999 1000 1001 1002 1003
	BUG_ON(page->mapping != inode->i_mapping);
	e4b->bd_bitmap_page = page;
	e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);

	if (blocks_per_page >= 2) {
		/* buddy and bitmap are on the same page */
		return 0;
1004
	}
1005 1006 1007 1008 1009

	block++;
	pnum = block / blocks_per_page;
	page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
	if (!page)
1010
		return -ENOMEM;
1011 1012 1013
	BUG_ON(page->mapping != inode->i_mapping);
	e4b->bd_buddy_page = page;
	return 0;
1014 1015
}

1016
static void ext4_mb_put_buddy_page_lock(struct ext4_buddy *e4b)
1017
{
1018 1019 1020 1021 1022 1023 1024
	if (e4b->bd_bitmap_page) {
		unlock_page(e4b->bd_bitmap_page);
		page_cache_release(e4b->bd_bitmap_page);
	}
	if (e4b->bd_buddy_page) {
		unlock_page(e4b->bd_buddy_page);
		page_cache_release(e4b->bd_buddy_page);
1025 1026 1027
	}
}

1028 1029 1030 1031 1032
/*
 * Locking note:  This routine calls ext4_mb_init_cache(), which takes the
 * block group lock of all groups for this page; do not hold the BG lock when
 * calling this routine!
 */
1033 1034 1035 1036 1037
static noinline_for_stack
int ext4_mb_init_group(struct super_block *sb, ext4_group_t group)
{

	struct ext4_group_info *this_grp;
1038 1039 1040
	struct ext4_buddy e4b;
	struct page *page;
	int ret = 0;
1041

1042
	might_sleep();
1043 1044 1045
	mb_debug(1, "init group %u\n", group);
	this_grp = ext4_get_group_info(sb, group);
	/*
1046 1047 1048 1049
	 * This ensures that we don't reinit the buddy cache
	 * page which map to the group from which we are already
	 * allocating. If we are looking at the buddy cache we would
	 * have taken a reference using ext4_mb_load_buddy and that
1050
	 * would have pinned buddy page to page cache.
1051 1052
	 * The call to ext4_mb_get_buddy_page_lock will mark the
	 * page accessed.
1053
	 */
1054 1055
	ret = ext4_mb_get_buddy_page_lock(sb, group, &e4b);
	if (ret || !EXT4_MB_GRP_NEED_INIT(this_grp)) {
1056 1057 1058 1059 1060 1061
		/*
		 * somebody initialized the group
		 * return without doing anything
		 */
		goto err;
	}
1062 1063 1064 1065 1066 1067

	page = e4b.bd_bitmap_page;
	ret = ext4_mb_init_cache(page, NULL);
	if (ret)
		goto err;
	if (!PageUptodate(page)) {
1068 1069 1070 1071
		ret = -EIO;
		goto err;
	}

1072
	if (e4b.bd_buddy_page == NULL) {
1073 1074 1075 1076 1077
		/*
		 * If both the bitmap and buddy are in
		 * the same page we don't need to force
		 * init the buddy
		 */
1078 1079
		ret = 0;
		goto err;
1080
	}
1081 1082 1083 1084 1085 1086
	/* init buddy cache */
	page = e4b.bd_buddy_page;
	ret = ext4_mb_init_cache(page, e4b.bd_bitmap);
	if (ret)
		goto err;
	if (!PageUptodate(page)) {
1087 1088 1089 1090
		ret = -EIO;
		goto err;
	}
err:
1091
	ext4_mb_put_buddy_page_lock(&e4b);
1092 1093 1094
	return ret;
}

1095 1096 1097 1098 1099
/*
 * Locking note:  This routine calls ext4_mb_init_cache(), which takes the
 * block group lock of all groups for this page; do not hold the BG lock when
 * calling this routine!
 */
1100 1101 1102
static noinline_for_stack int
ext4_mb_load_buddy(struct super_block *sb, ext4_group_t group,
					struct ext4_buddy *e4b)
1103 1104 1105 1106 1107 1108
{
	int blocks_per_page;
	int block;
	int pnum;
	int poff;
	struct page *page;
1109
	int ret;
1110 1111 1112
	struct ext4_group_info *grp;
	struct ext4_sb_info *sbi = EXT4_SB(sb);
	struct inode *inode = sbi->s_buddy_cache;
1113

1114
	might_sleep();
1115
	mb_debug(1, "load group %u\n", group);
1116 1117

	blocks_per_page = PAGE_CACHE_SIZE / sb->s_blocksize;
1118
	grp = ext4_get_group_info(sb, group);
1119 1120

	e4b->bd_blkbits = sb->s_blocksize_bits;
1121
	e4b->bd_info = grp;
1122 1123 1124 1125 1126
	e4b->bd_sb = sb;
	e4b->bd_group = group;
	e4b->bd_buddy_page = NULL;
	e4b->bd_bitmap_page = NULL;

1127 1128 1129 1130 1131 1132 1133 1134 1135 1136
	if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {
		/*
		 * we need full data about the group
		 * to make a good selection
		 */
		ret = ext4_mb_init_group(sb, group);
		if (ret)
			return ret;
	}

1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147
	/*
	 * the buddy cache inode stores the block bitmap
	 * and buddy information in consecutive blocks.
	 * So for each group we need two blocks.
	 */
	block = group * 2;
	pnum = block / blocks_per_page;
	poff = block % blocks_per_page;

	/* we could use find_or_create_page(), but it locks page
	 * what we'd like to avoid in fast path ... */
1148
	page = find_get_page_flags(inode->i_mapping, pnum, FGP_ACCESSED);
1149 1150
	if (page == NULL || !PageUptodate(page)) {
		if (page)
1151 1152 1153 1154 1155 1156 1157 1158
			/*
			 * drop the page reference and try
			 * to get the page with lock. If we
			 * are not uptodate that implies
			 * somebody just created the page but
			 * is yet to initialize the same. So
			 * wait for it to initialize.
			 */
1159 1160 1161 1162 1163
			page_cache_release(page);
		page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
		if (page) {
			BUG_ON(page->mapping != inode->i_mapping);
			if (!PageUptodate(page)) {
1164 1165 1166 1167 1168
				ret = ext4_mb_init_cache(page, NULL);
				if (ret) {
					unlock_page(page);
					goto err;
				}
1169 1170 1171 1172 1173 1174
				mb_cmp_bitmaps(e4b, page_address(page) +
					       (poff * sb->s_blocksize));
			}
			unlock_page(page);
		}
	}
1175 1176 1177 1178 1179
	if (page == NULL) {
		ret = -ENOMEM;
		goto err;
	}
	if (!PageUptodate(page)) {
1180
		ret = -EIO;
1181
		goto err;
1182
	}
1183 1184

	/* Pages marked accessed already */
1185 1186 1187 1188 1189 1190 1191
	e4b->bd_bitmap_page = page;
	e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);

	block++;
	pnum = block / blocks_per_page;
	poff = block % blocks_per_page;

1192
	page = find_get_page_flags(inode->i_mapping, pnum, FGP_ACCESSED);
1193 1194 1195 1196 1197 1198
	if (page == NULL || !PageUptodate(page)) {
		if (page)
			page_cache_release(page);
		page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
		if (page) {
			BUG_ON(page->mapping != inode->i_mapping);
1199 1200 1201 1202 1203 1204 1205
			if (!PageUptodate(page)) {
				ret = ext4_mb_init_cache(page, e4b->bd_bitmap);
				if (ret) {
					unlock_page(page);
					goto err;
				}
			}
1206 1207 1208
			unlock_page(page);
		}
	}
1209 1210 1211 1212 1213
	if (page == NULL) {
		ret = -ENOMEM;
		goto err;
	}
	if (!PageUptodate(page)) {
1214
		ret = -EIO;
1215
		goto err;
1216
	}
1217 1218

	/* Pages marked accessed already */
1219 1220 1221 1222 1223 1224 1225 1226 1227
	e4b->bd_buddy_page = page;
	e4b->bd_buddy = page_address(page) + (poff * sb->s_blocksize);

	BUG_ON(e4b->bd_bitmap_page == NULL);
	BUG_ON(e4b->bd_buddy_page == NULL);

	return 0;

err:
1228 1229
	if (page)
		page_cache_release(page);
1230 1231 1232 1233 1234 1235
	if (e4b->bd_bitmap_page)
		page_cache_release(e4b->bd_bitmap_page);
	if (e4b->bd_buddy_page)
		page_cache_release(e4b->bd_buddy_page);
	e4b->bd_buddy = NULL;
	e4b->bd_bitmap = NULL;
1236
	return ret;
1237 1238
}

1239
static void ext4_mb_unload_buddy(struct ext4_buddy *e4b)
1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250
{
	if (e4b->bd_bitmap_page)
		page_cache_release(e4b->bd_bitmap_page);
	if (e4b->bd_buddy_page)
		page_cache_release(e4b->bd_buddy_page);
}


static int mb_find_order_for_block(struct ext4_buddy *e4b, int block)
{
	int order = 1;
1251
	int bb_incr = 1 << (e4b->bd_blkbits - 1);
1252 1253
	void *bb;

1254
	BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);
1255 1256
	BUG_ON(block >= (1 << (e4b->bd_blkbits + 3)));

1257
	bb = e4b->bd_buddy;
1258 1259 1260 1261 1262 1263
	while (order <= e4b->bd_blkbits + 1) {
		block = block >> 1;
		if (!mb_test_bit(block, bb)) {
			/* this block is part of buddy of order 'order' */
			return order;
		}
1264 1265
		bb += bb_incr;
		bb_incr >>= 1;
1266 1267 1268 1269 1270
		order++;
	}
	return 0;
}

1271
static void mb_clear_bits(void *bm, int cur, int len)
1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283
{
	__u32 *addr;

	len = cur + len;
	while (cur < len) {
		if ((cur & 31) == 0 && (len - cur) >= 32) {
			/* fast path: clear whole word at once */
			addr = bm + (cur >> 3);
			*addr = 0;
			cur += 32;
			continue;
		}
1284
		mb_clear_bit(cur, bm);
1285 1286 1287 1288
		cur++;
	}
}

1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315
/* clear bits in given range
 * will return first found zero bit if any, -1 otherwise
 */
static int mb_test_and_clear_bits(void *bm, int cur, int len)
{
	__u32 *addr;
	int zero_bit = -1;

	len = cur + len;
	while (cur < len) {
		if ((cur & 31) == 0 && (len - cur) >= 32) {
			/* fast path: clear whole word at once */
			addr = bm + (cur >> 3);
			if (*addr != (__u32)(-1) && zero_bit == -1)
				zero_bit = cur + mb_find_next_zero_bit(addr, 32, 0);
			*addr = 0;
			cur += 32;
			continue;
		}
		if (!mb_test_and_clear_bit(cur, bm) && zero_bit == -1)
			zero_bit = cur;
		cur++;
	}

	return zero_bit;
}

1316
void ext4_set_bits(void *bm, int cur, int len)
1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328
{
	__u32 *addr;

	len = cur + len;
	while (cur < len) {
		if ((cur & 31) == 0 && (len - cur) >= 32) {
			/* fast path: set whole word at once */
			addr = bm + (cur >> 3);
			*addr = 0xffffffff;
			cur += 32;
			continue;
		}
1329
		mb_set_bit(cur, bm);
1330 1331 1332 1333
		cur++;
	}
}

1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407
/*
 * _________________________________________________________________ */

static inline int mb_buddy_adjust_border(int* bit, void* bitmap, int side)
{
	if (mb_test_bit(*bit + side, bitmap)) {
		mb_clear_bit(*bit, bitmap);
		(*bit) -= side;
		return 1;
	}
	else {
		(*bit) += side;
		mb_set_bit(*bit, bitmap);
		return -1;
	}
}

static void mb_buddy_mark_free(struct ext4_buddy *e4b, int first, int last)
{
	int max;
	int order = 1;
	void *buddy = mb_find_buddy(e4b, order, &max);

	while (buddy) {
		void *buddy2;

		/* Bits in range [first; last] are known to be set since
		 * corresponding blocks were allocated. Bits in range
		 * (first; last) will stay set because they form buddies on
		 * upper layer. We just deal with borders if they don't
		 * align with upper layer and then go up.
		 * Releasing entire group is all about clearing
		 * single bit of highest order buddy.
		 */

		/* Example:
		 * ---------------------------------
		 * |   1   |   1   |   1   |   1   |
		 * ---------------------------------
		 * | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
		 * ---------------------------------
		 *   0   1   2   3   4   5   6   7
		 *      \_____________________/
		 *
		 * Neither [1] nor [6] is aligned to above layer.
		 * Left neighbour [0] is free, so mark it busy,
		 * decrease bb_counters and extend range to
		 * [0; 6]
		 * Right neighbour [7] is busy. It can't be coaleasced with [6], so
		 * mark [6] free, increase bb_counters and shrink range to
		 * [0; 5].
		 * Then shift range to [0; 2], go up and do the same.
		 */


		if (first & 1)
			e4b->bd_info->bb_counters[order] += mb_buddy_adjust_border(&first, buddy, -1);
		if (!(last & 1))
			e4b->bd_info->bb_counters[order] += mb_buddy_adjust_border(&last, buddy, 1);
		if (first > last)
			break;
		order++;

		if (first == last || !(buddy2 = mb_find_buddy(e4b, order, &max))) {
			mb_clear_bits(buddy, first, last - first + 1);
			e4b->bd_info->bb_counters[order - 1] += last - first + 1;
			break;
		}
		first >>= 1;
		last >>= 1;
		buddy = buddy2;
	}
}

1408
static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,
1409
			   int first, int count)
1410
{
1411 1412 1413 1414
	int left_is_free = 0;
	int right_is_free = 0;
	int block;
	int last = first + count - 1;
1415 1416
	struct super_block *sb = e4b->bd_sb;

1417 1418
	if (WARN_ON(count == 0))
		return;
1419
	BUG_ON(last >= (sb->s_blocksize << 3));
1420
	assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));
1421 1422 1423 1424
	/* Don't bother if the block group is corrupt. */
	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))
		return;

1425 1426 1427 1428 1429 1430 1431
	mb_check_buddy(e4b);
	mb_free_blocks_double(inode, e4b, first, count);

	e4b->bd_info->bb_free += count;
	if (first < e4b->bd_info->bb_first_free)
		e4b->bd_info->bb_first_free = first;

1432 1433 1434
	/* access memory sequentially: check left neighbour,
	 * clear range and then check right neighbour
	 */
1435
	if (first != 0)
1436 1437 1438 1439 1440 1441
		left_is_free = !mb_test_bit(first - 1, e4b->bd_bitmap);
	block = mb_test_and_clear_bits(e4b->bd_bitmap, first, count);
	if (last + 1 < EXT4_SB(sb)->s_mb_maxs[0])
		right_is_free = !mb_test_bit(last + 1, e4b->bd_bitmap);

	if (unlikely(block != -1)) {
1442
		struct ext4_sb_info *sbi = EXT4_SB(sb);
1443 1444 1445 1446 1447 1448 1449 1450
		ext4_fsblk_t blocknr;

		blocknr = ext4_group_first_block_no(sb, e4b->bd_group);
		blocknr += EXT4_C2B(EXT4_SB(sb), block);
		ext4_grp_locked_error(sb, e4b->bd_group,
				      inode ? inode->i_ino : 0,
				      blocknr,
				      "freeing already freed block "
1451 1452
				      "(bit %u); block bitmap corrupt.",
				      block);
1453 1454 1455
		if (!EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info))
			percpu_counter_sub(&sbi->s_freeclusters_counter,
					   e4b->bd_info->bb_free);
1456 1457 1458
		/* Mark the block group as corrupt. */
		set_bit(EXT4_GROUP_INFO_BBITMAP_CORRUPT_BIT,
			&e4b->bd_info->bb_state);
1459 1460 1461 1462 1463 1464
		mb_regenerate_buddy(e4b);
		goto done;
	}

	/* let's maintain fragments counter */
	if (left_is_free && right_is_free)
1465
		e4b->bd_info->bb_fragments--;
1466
	else if (!left_is_free && !right_is_free)
1467 1468
		e4b->bd_info->bb_fragments++;

1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482
	/* buddy[0] == bd_bitmap is a special case, so handle
	 * it right away and let mb_buddy_mark_free stay free of
	 * zero order checks.
	 * Check if neighbours are to be coaleasced,
	 * adjust bitmap bb_counters and borders appropriately.
	 */
	if (first & 1) {
		first += !left_is_free;
		e4b->bd_info->bb_counters[0] += left_is_free ? -1 : 1;
	}
	if (!(last & 1)) {
		last -= !right_is_free;
		e4b->bd_info->bb_counters[0] += right_is_free ? -1 : 1;
	}
1483

1484 1485
	if (first <= last)
		mb_buddy_mark_free(e4b, first >> 1, last >> 1);
1486

1487
done:
1488
	mb_set_largest_free_order(sb, e4b->bd_info);
1489 1490 1491
	mb_check_buddy(e4b);
}

1492
static int mb_find_extent(struct ext4_buddy *e4b, int block,
1493 1494 1495
				int needed, struct ext4_free_extent *ex)
{
	int next = block;
1496
	int max, order;
1497 1498
	void *buddy;

1499
	assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
1500 1501
	BUG_ON(ex == NULL);

1502
	buddy = mb_find_buddy(e4b, 0, &max);
1503 1504 1505 1506 1507 1508 1509 1510 1511
	BUG_ON(buddy == NULL);
	BUG_ON(block >= max);
	if (mb_test_bit(block, buddy)) {
		ex->fe_len = 0;
		ex->fe_start = 0;
		ex->fe_group = 0;
		return 0;
	}

1512 1513 1514
	/* find actual order */
	order = mb_find_order_for_block(e4b, block);
	block = block >> order;
1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525

	ex->fe_len = 1 << order;
	ex->fe_start = block << order;
	ex->fe_group = e4b->bd_group;

	/* calc difference from given start */
	next = next - ex->fe_start;
	ex->fe_len -= next;
	ex->fe_start += next;

	while (needed > ex->fe_len &&
Alan Cox's avatar
Alan Cox committed
1526
	       mb_find_buddy(e4b, order, &max)) {
1527 1528 1529 1530 1531

		if (block + 1 >= max)
			break;

		next = (block + 1) * (1 << order);
1532
		if (mb_test_bit(next, e4b->bd_bitmap))
1533 1534
			break;

1535
		order = mb_find_order_for_block(e4b, next);
1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558

		block = next >> order;
		ex->fe_len += 1 << order;
	}

	BUG_ON(ex->fe_start + ex->fe_len > (1 << (e4b->bd_blkbits + 3)));
	return ex->fe_len;
}

static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
{
	int ord;
	int mlen = 0;
	int max = 0;
	int cur;
	int start = ex->fe_start;
	int len = ex->fe_len;
	unsigned ret = 0;
	int len0 = len;
	void *buddy;

	BUG_ON(start + len > (e4b->bd_sb->s_blocksize << 3));
	BUG_ON(e4b->bd_group != ex->fe_group);
1559
	assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
1560 1561 1562 1563 1564 1565 1566 1567 1568
	mb_check_buddy(e4b);
	mb_mark_used_double(e4b, start, len);

	e4b->bd_info->bb_free -= len;
	if (e4b->bd_info->bb_first_free == start)
		e4b->bd_info->bb_first_free += len;

	/* let's maintain fragments counter */
	if (start != 0)
1569
		mlen = !mb_test_bit(start - 1, e4b->bd_bitmap);
1570
	if (start + len < EXT4_SB(e4b->bd_sb)->s_mb_maxs[0])
1571
		max = !mb_test_bit(start + len, e4b->bd_bitmap);
1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611
	if (mlen && max)
		e4b->bd_info->bb_fragments++;
	else if (!mlen && !max)
		e4b->bd_info->bb_fragments--;

	/* let's maintain buddy itself */
	while (len) {
		ord = mb_find_order_for_block(e4b, start);

		if (((start >> ord) << ord) == start && len >= (1 << ord)) {
			/* the whole chunk may be allocated at once! */
			mlen = 1 << ord;
			buddy = mb_find_buddy(e4b, ord, &max);
			BUG_ON((start >> ord) >= max);
			mb_set_bit(start >> ord, buddy);
			e4b->bd_info->bb_counters[ord]--;
			start += mlen;
			len -= mlen;
			BUG_ON(len < 0);
			continue;
		}

		/* store for history */
		if (ret == 0)
			ret = len | (ord << 16);

		/* we have to split large buddy */
		BUG_ON(ord <= 0);
		buddy = mb_find_buddy(e4b, ord, &max);
		mb_set_bit(start >> ord, buddy);
		e4b->bd_info->bb_counters[ord]--;

		ord--;
		cur = (start >> ord) & ~1U;
		buddy = mb_find_buddy(e4b, ord, &max);
		mb_clear_bit(cur, buddy);
		mb_clear_bit(cur + 1, buddy);
		e4b->bd_info->bb_counters[ord]++;
		e4b->bd_info->bb_counters[ord]++;
	}
1612
	mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info);
1613

1614
	ext4_set_bits(e4b->bd_bitmap, ex->fe_start, len0);
1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643
	mb_check_buddy(e4b);

	return ret;
}

/*
 * Must be called under group lock!
 */
static void ext4_mb_use_best_found(struct ext4_allocation_context *ac,
					struct ext4_buddy *e4b)
{
	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
	int ret;

	BUG_ON(ac->ac_b_ex.fe_group != e4b->bd_group);
	BUG_ON(ac->ac_status == AC_STATUS_FOUND);

	ac->ac_b_ex.fe_len = min(ac->ac_b_ex.fe_len, ac->ac_g_ex.fe_len);
	ac->ac_b_ex.fe_logical = ac->ac_g_ex.fe_logical;
	ret = mb_mark_used(e4b, &ac->ac_b_ex);

	/* preallocation can change ac_b_ex, thus we store actually
	 * allocated blocks for history */
	ac->ac_f_ex = ac->ac_b_ex;

	ac->ac_status = AC_STATUS_FOUND;
	ac->ac_tail = ret & 0xffff;
	ac->ac_buddy = ret >> 16;

1644 1645 1646 1647 1648 1649 1650
	/*
	 * take the page reference. We want the page to be pinned
	 * so that we don't get a ext4_mb_init_cache_call for this
	 * group until we update the bitmap. That would mean we
	 * double allocate blocks. The reference is dropped
	 * in ext4_mb_release_context
	 */
1651 1652 1653 1654 1655
	ac->ac_bitmap_page = e4b->bd_bitmap_page;
	get_page(ac->ac_bitmap_page);
	ac->ac_buddy_page = e4b->bd_buddy_page;
	get_page(ac->ac_buddy_page);
	/* store last allocated for subsequent stream allocation */
1656
	if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {
1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677
		spin_lock(&sbi->s_md_lock);
		sbi->s_mb_last_group = ac->ac_f_ex.fe_group;
		sbi->s_mb_last_start = ac->ac_f_ex.fe_start;
		spin_unlock(&sbi->s_md_lock);
	}
}

/*
 * regular allocator, for general purposes allocation
 */

static void ext4_mb_check_limits(struct ext4_allocation_context *ac,
					struct ext4_buddy *e4b,
					int finish_group)
{
	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
	struct ext4_free_extent *bex = &ac->ac_b_ex;
	struct ext4_free_extent *gex = &ac->ac_g_ex;
	struct ext4_free_extent ex;
	int max;

1678 1679
	if (ac->ac_status == AC_STATUS_FOUND)
		return;
1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699
	/*
	 * We don't want to scan for a whole year
	 */
	if (ac->ac_found > sbi->s_mb_max_to_scan &&
			!(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
		ac->ac_status = AC_STATUS_BREAK;
		return;
	}

	/*
	 * Haven't found good chunk so far, let's continue
	 */
	if (bex->fe_len < gex->fe_len)
		return;

	if ((finish_group || ac->ac_found > sbi->s_mb_min_to_scan)
			&& bex->fe_group == e4b->bd_group) {
		/* recheck chunk's availability - we don't know
		 * when it was found (within this lock-unlock
		 * period or not) */
1700
		max = mb_find_extent(e4b, bex->fe_start, gex->fe_len, &ex);
1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725
		if (max >= gex->fe_len) {
			ext4_mb_use_best_found(ac, e4b);
			return;
		}
	}
}

/*
 * The routine checks whether found extent is good enough. If it is,
 * then the extent gets marked used and flag is set to the context
 * to stop scanning. Otherwise, the extent is compared with the
 * previous found extent and if new one is better, then it's stored
 * in the context. Later, the best found extent will be used, if
 * mballoc can't find good enough extent.
 *
 * FIXME: real allocation policy is to be designed yet!
 */
static void ext4_mb_measure_extent(struct ext4_allocation_context *ac,
					struct ext4_free_extent *ex,
					struct ext4_buddy *e4b)
{
	struct ext4_free_extent *bex = &ac->ac_b_ex;
	struct ext4_free_extent *gex = &ac->ac_g_ex;

	BUG_ON(ex->fe_len <= 0);
1726 1727
	BUG_ON(ex->fe_len > EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));
	BUG_ON(ex->fe_start >= EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));
1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776
	BUG_ON(ac->ac_status != AC_STATUS_CONTINUE);

	ac->ac_found++;

	/*
	 * The special case - take what you catch first
	 */
	if (unlikely(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
		*bex = *ex;
		ext4_mb_use_best_found(ac, e4b);
		return;
	}

	/*
	 * Let's check whether the chuck is good enough
	 */
	if (ex->fe_len == gex->fe_len) {
		*bex = *ex;
		ext4_mb_use_best_found(ac, e4b);
		return;
	}

	/*
	 * If this is first found extent, just store it in the context
	 */
	if (bex->fe_len == 0) {
		*bex = *ex;
		return;
	}

	/*
	 * If new found extent is better, store it in the context
	 */
	if (bex->fe_len < gex->fe_len) {
		/* if the request isn't satisfied, any found extent
		 * larger than previous best one is better */
		if (ex->fe_len > bex->fe_len)
			*bex = *ex;
	} else if (ex->fe_len > gex->fe_len) {
		/* if the request is satisfied, then we try to find
		 * an extent that still satisfy the request, but is
		 * smaller than previous one */
		if (ex->fe_len < bex->fe_len)
			*bex = *ex;
	}

	ext4_mb_check_limits(ac, e4b, 0);
}

1777 1778
static noinline_for_stack
int ext4_mb_try_best_found(struct ext4_allocation_context *ac,
1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791
					struct ext4_buddy *e4b)
{
	struct ext4_free_extent ex = ac->ac_b_ex;
	ext4_group_t group = ex.fe_group;
	int max;
	int err;

	BUG_ON(ex.fe_len <= 0);
	err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);
	if (err)
		return err;

	ext4_lock_group(ac->ac_sb, group);
1792
	max = mb_find_extent(e4b, ex.fe_start, ex.fe_len, &ex);
1793 1794 1795 1796 1797 1798 1799

	if (max > 0) {
		ac->ac_b_ex = ex;
		ext4_mb_use_best_found(ac, e4b);
	}

	ext4_unlock_group(ac->ac_sb, group);
1800
	ext4_mb_unload_buddy(e4b);
1801 1802 1803 1804

	return 0;
}

1805 1806
static noinline_for_stack
int ext4_mb_find_by_goal(struct ext4_allocation_context *ac,
1807 1808 1809 1810 1811 1812
				struct ext4_buddy *e4b)
{
	ext4_group_t group = ac->ac_g_ex.fe_group;
	int max;
	int err;
	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1813
	struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);
1814 1815 1816 1817
	struct ext4_free_extent ex;

	if (!(ac->ac_flags & EXT4_MB_HINT_TRY_GOAL))
		return 0;
1818 1819
	if (grp->bb_free == 0)
		return 0;
1820 1821 1822 1823 1824

	err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);
	if (err)
		return err;

1825 1826 1827 1828 1829
	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info))) {
		ext4_mb_unload_buddy(e4b);
		return 0;
	}

1830
	ext4_lock_group(ac->ac_sb, group);
1831
	max = mb_find_extent(e4b, ac->ac_g_ex.fe_start,
1832
			     ac->ac_g_ex.fe_len, &ex);
1833
	ex.fe_logical = 0xDEADFA11; /* debug value */
1834 1835 1836 1837

	if (max >= ac->ac_g_ex.fe_len && ac->ac_g_ex.fe_len == sbi->s_stripe) {
		ext4_fsblk_t start;

1838 1839
		start = ext4_group_first_block_no(ac->ac_sb, e4b->bd_group) +
			ex.fe_start;
1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863
		/* use do_div to get remainder (would be 64-bit modulo) */
		if (do_div(start, sbi->s_stripe) == 0) {
			ac->ac_found++;
			ac->ac_b_ex = ex;
			ext4_mb_use_best_found(ac, e4b);
		}
	} else if (max >= ac->ac_g_ex.fe_len) {
		BUG_ON(ex.fe_len <= 0);
		BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
		BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
		ac->ac_found++;
		ac->ac_b_ex = ex;
		ext4_mb_use_best_found(ac, e4b);
	} else if (max > 0 && (ac->ac_flags & EXT4_MB_HINT_MERGE)) {
		/* Sometimes, caller may want to merge even small
		 * number of blocks to an existing extent */
		BUG_ON(ex.fe_len <= 0);
		BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
		BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
		ac->ac_found++;
		ac->ac_b_ex = ex;
		ext4_mb_use_best_found(ac, e4b);
	}
	ext4_unlock_group(ac->ac_sb, group);
1864
	ext4_mb_unload_buddy(e4b);
1865 1866 1867 1868 1869 1870 1871 1872

	return 0;
}

/*
 * The routine scans buddy structures (not bitmap!) from given order
 * to max order and tries to find big enough chunk to satisfy the req
 */
1873 1874
static noinline_for_stack
void ext4_mb_simple_scan_group(struct ext4_allocation_context *ac,
1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891
					struct ext4_buddy *e4b)
{
	struct super_block *sb = ac->ac_sb;
	struct ext4_group_info *grp = e4b->bd_info;
	void *buddy;
	int i;
	int k;
	int max;

	BUG_ON(ac->ac_2order <= 0);
	for (i = ac->ac_2order; i <= sb->s_blocksize_bits + 1; i++) {
		if (grp->bb_counters[i] == 0)
			continue;

		buddy = mb_find_buddy(e4b, i, &max);
		BUG_ON(buddy == NULL);

1892
		k = mb_find_next_zero_bit(buddy, max, 0);
1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916
		BUG_ON(k >= max);

		ac->ac_found++;

		ac->ac_b_ex.fe_len = 1 << i;
		ac->ac_b_ex.fe_start = k << i;
		ac->ac_b_ex.fe_group = e4b->bd_group;

		ext4_mb_use_best_found(ac, e4b);

		BUG_ON(ac->ac_b_ex.fe_len != ac->ac_g_ex.fe_len);

		if (EXT4_SB(sb)->s_mb_stats)
			atomic_inc(&EXT4_SB(sb)->s_bal_2orders);

		break;
	}
}

/*
 * The routine scans the group and measures all found extents.
 * In order to optimize scanning, caller must pass number of
 * free blocks in the group, so the routine can know upper limit.
 */
1917 1918
static noinline_for_stack
void ext4_mb_complex_scan_group(struct ext4_allocation_context *ac,
1919 1920 1921
					struct ext4_buddy *e4b)
{
	struct super_block *sb = ac->ac_sb;
1922
	void *bitmap = e4b->bd_bitmap;
1923 1924 1925 1926 1927 1928 1929 1930 1931 1932
	struct ext4_free_extent ex;
	int i;
	int free;

	free = e4b->bd_info->bb_free;
	BUG_ON(free <= 0);

	i = e4b->bd_info->bb_first_free;

	while (free && ac->ac_status == AC_STATUS_CONTINUE) {
1933
		i = mb_find_next_zero_bit(bitmap,
1934 1935
						EXT4_CLUSTERS_PER_GROUP(sb), i);
		if (i >= EXT4_CLUSTERS_PER_GROUP(sb)) {
1936
			/*
1937
			 * IF we have corrupt bitmap, we won't find any
1938 1939 1940
			 * free blocks even though group info says we
			 * we have free blocks
			 */
1941
			ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,
1942
					"%d free clusters as per "
1943
					"group info. But bitmap says 0",
1944
					free);
1945 1946 1947
			break;
		}

1948
		mb_find_extent(e4b, i, ac->ac_g_ex.fe_len, &ex);
1949
		BUG_ON(ex.fe_len <= 0);
1950
		if (free < ex.fe_len) {
1951
			ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,
1952
					"%d free clusters as per "
1953
					"group info. But got %d blocks",
1954
					free, ex.fe_len);
1955 1956 1957 1958 1959 1960
			/*
			 * The number of free blocks differs. This mostly
			 * indicate that the bitmap is corrupt. So exit
			 * without claiming the space.
			 */
			break;
1961
		}
1962
		ex.fe_logical = 0xDEADC0DE; /* debug value */
1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973
		ext4_mb_measure_extent(ac, &ex, e4b);

		i += ex.fe_len;
		free -= ex.fe_len;
	}

	ext4_mb_check_limits(ac, e4b, 1);
}

/*
 * This is a special case for storages like raid5
1974
 * we try to find stripe-aligned chunks for stripe-size-multiple requests
1975
 */
1976 1977
static noinline_for_stack
void ext4_mb_scan_aligned(struct ext4_allocation_context *ac,
1978 1979 1980 1981
				 struct ext4_buddy *e4b)
{
	struct super_block *sb = ac->ac_sb;
	struct ext4_sb_info *sbi = EXT4_SB(sb);
1982
	void *bitmap = e4b->bd_bitmap;
1983 1984 1985 1986 1987 1988 1989 1990 1991
	struct ext4_free_extent ex;
	ext4_fsblk_t first_group_block;
	ext4_fsblk_t a;
	ext4_grpblk_t i;
	int max;

	BUG_ON(sbi->s_stripe == 0);

	/* find first stripe-aligned block in group */
1992 1993
	first_group_block = ext4_group_first_block_no(sb, e4b->bd_group);

1994 1995 1996 1997
	a = first_group_block + sbi->s_stripe - 1;
	do_div(a, sbi->s_stripe);
	i = (a * sbi->s_stripe) - first_group_block;

1998
	while (i < EXT4_CLUSTERS_PER_GROUP(sb)) {
1999
		if (!mb_test_bit(i, bitmap)) {
2000
			max = mb_find_extent(e4b, i, sbi->s_stripe, &ex);
2001 2002
			if (max >= sbi->s_stripe) {
				ac->ac_found++;
2003
				ex.fe_logical = 0xDEADF00D; /* debug value */
2004 2005 2006 2007 2008 2009 2010 2011 2012
				ac->ac_b_ex = ex;
				ext4_mb_use_best_found(ac, e4b);
				break;
			}
		}
		i += sbi->s_stripe;
	}
}

2013
/* This is now called BEFORE we load the buddy bitmap. */
2014 2015 2016 2017
static int ext4_mb_good_group(struct ext4_allocation_context *ac,
				ext4_group_t group, int cr)
{
	unsigned free, fragments;
2018
	int flex_size = ext4_flex_bg_size(EXT4_SB(ac->ac_sb));
2019 2020 2021
	struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);

	BUG_ON(cr < 0 || cr >= 4);
2022

2023 2024 2025 2026 2027 2028
	free = grp->bb_free;
	if (free == 0)
		return 0;
	if (cr <= 2 && free < ac->ac_g_ex.fe_len)
		return 0;

2029 2030 2031
	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(grp)))
		return 0;

2032 2033 2034 2035 2036 2037
	/* We only do this if the grp has never been initialized */
	if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {
		int ret = ext4_mb_init_group(ac->ac_sb, group);
		if (ret)
			return 0;
	}
2038 2039 2040 2041 2042 2043 2044 2045 2046

	fragments = grp->bb_fragments;
	if (fragments == 0)
		return 0;

	switch (cr) {
	case 0:
		BUG_ON(ac->ac_2order == 0);

2047 2048 2049 2050 2051 2052
		/* Avoid using the first bg of a flexgroup for data files */
		if ((ac->ac_flags & EXT4_MB_HINT_DATA) &&
		    (flex_size >= EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME) &&
		    ((group % flex_size) == 0))
			return 0;

2053 2054 2055 2056 2057 2058 2059
		if ((ac->ac_2order > ac->ac_sb->s_blocksize_bits+1) ||
		    (free / fragments) >= ac->ac_g_ex.fe_len)
			return 1;

		if (grp->bb_largest_free_order < ac->ac_2order)
			return 0;

2060
		return 1;
2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077
	case 1:
		if ((free / fragments) >= ac->ac_g_ex.fe_len)
			return 1;
		break;
	case 2:
		if (free >= ac->ac_g_ex.fe_len)
			return 1;
		break;
	case 3:
		return 1;
	default:
		BUG();
	}

	return 0;
}

2078 2079
static noinline_for_stack int
ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
2080
{
2081
	ext4_group_t ngroups, group, i;
2082 2083 2084 2085 2086 2087 2088 2089
	int cr;
	int err = 0;
	struct ext4_sb_info *sbi;
	struct super_block *sb;
	struct ext4_buddy e4b;

	sb = ac->ac_sb;
	sbi = EXT4_SB(sb);
2090
	ngroups = ext4_get_groups_count(sb);
2091
	/* non-extent files are limited to low blocks/groups */
2092
	if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)))
2093 2094
		ngroups = sbi->s_blockfile_groups;

2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114
	BUG_ON(ac->ac_status == AC_STATUS_FOUND);

	/* first, try the goal */
	err = ext4_mb_find_by_goal(ac, &e4b);
	if (err || ac->ac_status == AC_STATUS_FOUND)
		goto out;

	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
		goto out;

	/*
	 * ac->ac2_order is set only if the fe_len is a power of 2
	 * if ac2_order is set we also set criteria to 0 so that we
	 * try exact allocation using buddy.
	 */
	i = fls(ac->ac_g_ex.fe_len);
	ac->ac_2order = 0;
	/*
	 * We search using buddy data only if the order of the request
	 * is greater than equal to the sbi_s_mb_order2_reqs
2115
	 * You can tune it via /sys/fs/ext4/<partition>/mb_order2_req
2116 2117 2118 2119 2120 2121 2122 2123 2124
	 */
	if (i >= sbi->s_mb_order2_reqs) {
		/*
		 * This should tell if fe_len is exactly power of 2
		 */
		if ((ac->ac_g_ex.fe_len & (~(1 << (i - 1)))) == 0)
			ac->ac_2order = i - 1;
	}

2125 2126
	/* if stream allocation is enabled, use global goal */
	if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {
2127 2128 2129 2130 2131 2132
		/* TBD: may be hot point */
		spin_lock(&sbi->s_md_lock);
		ac->ac_g_ex.fe_group = sbi->s_mb_last_group;
		ac->ac_g_ex.fe_start = sbi->s_mb_last_start;
		spin_unlock(&sbi->s_md_lock);
	}
2133

2134 2135 2136 2137 2138 2139 2140 2141 2142
	/* Let's just scan groups to find more-less suitable blocks */
	cr = ac->ac_2order ? 0 : 1;
	/*
	 * cr == 0 try to get exact allocation,
	 * cr == 3  try to get anything
	 */
repeat:
	for (; cr < 4 && ac->ac_status == AC_STATUS_CONTINUE; cr++) {
		ac->ac_criteria = cr;
2143 2144 2145 2146 2147 2148
		/*
		 * searching for the right group start
		 * from the goal value specified
		 */
		group = ac->ac_g_ex.fe_group;

2149
		for (i = 0; i < ngroups; group++, i++) {
2150
			cond_resched();
2151 2152 2153 2154 2155
			/*
			 * Artificially restricted ngroups for non-extent
			 * files makes group > ngroups possible on first loop.
			 */
			if (group >= ngroups)
2156 2157
				group = 0;

2158 2159
			/* This now checks without needing the buddy page */
			if (!ext4_mb_good_group(ac, group, cr))
2160 2161 2162 2163 2164 2165 2166
				continue;

			err = ext4_mb_load_buddy(sb, group, &e4b);
			if (err)
				goto out;

			ext4_lock_group(sb, group);
2167 2168 2169 2170 2171

			/*
			 * We need to check again after locking the
			 * block group
			 */
2172 2173
			if (!ext4_mb_good_group(ac, group, cr)) {
				ext4_unlock_group(sb, group);
2174
				ext4_mb_unload_buddy(&e4b);
2175 2176 2177 2178
				continue;
			}

			ac->ac_groups_scanned++;
2179
			if (cr == 0 && ac->ac_2order < sb->s_blocksize_bits+2)
2180
				ext4_mb_simple_scan_group(ac, &e4b);
2181 2182
			else if (cr == 1 && sbi->s_stripe &&
					!(ac->ac_g_ex.fe_len % sbi->s_stripe))
2183 2184 2185 2186 2187
				ext4_mb_scan_aligned(ac, &e4b);
			else
				ext4_mb_complex_scan_group(ac, &e4b);

			ext4_unlock_group(sb, group);
2188
			ext4_mb_unload_buddy(&e4b);
2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228

			if (ac->ac_status != AC_STATUS_CONTINUE)
				break;
		}
	}

	if (ac->ac_b_ex.fe_len > 0 && ac->ac_status != AC_STATUS_FOUND &&
	    !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
		/*
		 * We've been searching too long. Let's try to allocate
		 * the best chunk we've found so far
		 */

		ext4_mb_try_best_found(ac, &e4b);
		if (ac->ac_status != AC_STATUS_FOUND) {
			/*
			 * Someone more lucky has already allocated it.
			 * The only thing we can do is just take first
			 * found block(s)
			printk(KERN_DEBUG "EXT4-fs: someone won our chunk\n");
			 */
			ac->ac_b_ex.fe_group = 0;
			ac->ac_b_ex.fe_start = 0;
			ac->ac_b_ex.fe_len = 0;
			ac->ac_status = AC_STATUS_CONTINUE;
			ac->ac_flags |= EXT4_MB_HINT_FIRST;
			cr = 3;
			atomic_inc(&sbi->s_mb_lost_chunks);
			goto repeat;
		}
	}
out:
	return err;
}

static void *ext4_mb_seq_groups_start(struct seq_file *seq, loff_t *pos)
{
	struct super_block *sb = seq->private;
	ext4_group_t group;

2229
	if (*pos < 0 || *pos >= ext4_get_groups_count(sb))
2230 2231
		return NULL;
	group = *pos + 1;
2232
	return (void *) ((unsigned long) group);
2233 2234 2235 2236 2237 2238 2239 2240
}

static void *ext4_mb_seq_groups_next(struct seq_file *seq, void *v, loff_t *pos)
{
	struct super_block *sb = seq->private;
	ext4_group_t group;

	++*pos;
2241
	if (*pos < 0 || *pos >= ext4_get_groups_count(sb))
2242 2243
		return NULL;
	group = *pos + 1;
2244
	return (void *) ((unsigned long) group);
2245 2246 2247 2248 2249
}

static int ext4_mb_seq_groups_show(struct seq_file *seq, void *v)
{
	struct super_block *sb = seq->private;
2250
	ext4_group_t group = (ext4_group_t) ((unsigned long) v);
2251
	int i;
2252
	int err, buddy_loaded = 0;
2253
	struct ext4_buddy e4b;
2254
	struct ext4_group_info *grinfo;
2255 2256
	struct sg {
		struct ext4_group_info info;
2257
		ext4_grpblk_t counters[EXT4_MAX_BLOCK_LOG_SIZE + 2];
2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270
	} sg;

	group--;
	if (group == 0)
		seq_printf(seq, "#%-5s: %-5s %-5s %-5s "
				"[ %-5s %-5s %-5s %-5s %-5s %-5s %-5s "
				  "%-5s %-5s %-5s %-5s %-5s %-5s %-5s ]\n",
			   "group", "free", "frags", "first",
			   "2^0", "2^1", "2^2", "2^3", "2^4", "2^5", "2^6",
			   "2^7", "2^8", "2^9", "2^10", "2^11", "2^12", "2^13");

	i = (sb->s_blocksize_bits + 2) * sizeof(sg.info.bb_counters[0]) +
		sizeof(struct ext4_group_info);
2271 2272 2273 2274 2275 2276 2277 2278 2279
	grinfo = ext4_get_group_info(sb, group);
	/* Load the group info in memory only if not already loaded. */
	if (unlikely(EXT4_MB_GRP_NEED_INIT(grinfo))) {
		err = ext4_mb_load_buddy(sb, group, &e4b);
		if (err) {
			seq_printf(seq, "#%-5u: I/O error\n", group);
			return 0;
		}
		buddy_loaded = 1;
2280
	}
2281

2282
	memcpy(&sg, ext4_get_group_info(sb, group), i);
2283 2284 2285

	if (buddy_loaded)
		ext4_mb_unload_buddy(&e4b);
2286

2287
	seq_printf(seq, "#%-5u: %-5u %-5u %-5u [", group, sg.info.bb_free,
2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300
			sg.info.bb_fragments, sg.info.bb_first_free);
	for (i = 0; i <= 13; i++)
		seq_printf(seq, " %-5u", i <= sb->s_blocksize_bits + 1 ?
				sg.info.bb_counters[i] : 0);
	seq_printf(seq, " ]\n");

	return 0;
}

static void ext4_mb_seq_groups_stop(struct seq_file *seq, void *v)
{
}

2301
static const struct seq_operations ext4_mb_seq_groups_ops = {
2302 2303 2304 2305 2306 2307 2308 2309
	.start  = ext4_mb_seq_groups_start,
	.next   = ext4_mb_seq_groups_next,
	.stop   = ext4_mb_seq_groups_stop,
	.show   = ext4_mb_seq_groups_show,
};

static int ext4_mb_seq_groups_open(struct inode *inode, struct file *file)
{
2310
	struct super_block *sb = PDE_DATA(inode);
2311 2312 2313 2314
	int rc;

	rc = seq_open(file, &ext4_mb_seq_groups_ops);
	if (rc == 0) {
2315
		struct seq_file *m = file->private_data;
2316 2317 2318 2319 2320 2321
		m->private = sb;
	}
	return rc;

}

2322
static const struct file_operations ext4_mb_seq_groups_fops = {
2323 2324 2325 2326 2327 2328 2329
	.owner		= THIS_MODULE,
	.open		= ext4_mb_seq_groups_open,
	.read		= seq_read,
	.llseek		= seq_lseek,
	.release	= seq_release,
};

2330 2331 2332 2333 2334 2335 2336 2337
static struct kmem_cache *get_groupinfo_cache(int blocksize_bits)
{
	int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;
	struct kmem_cache *cachep = ext4_groupinfo_caches[cache_index];

	BUG_ON(!cachep);
	return cachep;
}
2338

2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362
/*
 * Allocate the top-level s_group_info array for the specified number
 * of groups
 */
int ext4_mb_alloc_groupinfo(struct super_block *sb, ext4_group_t ngroups)
{
	struct ext4_sb_info *sbi = EXT4_SB(sb);
	unsigned size;
	struct ext4_group_info ***new_groupinfo;

	size = (ngroups + EXT4_DESC_PER_BLOCK(sb) - 1) >>
		EXT4_DESC_PER_BLOCK_BITS(sb);
	if (size <= sbi->s_group_info_size)
		return 0;

	size = roundup_pow_of_two(sizeof(*sbi->s_group_info) * size);
	new_groupinfo = ext4_kvzalloc(size, GFP_KERNEL);
	if (!new_groupinfo) {
		ext4_msg(sb, KERN_ERR, "can't allocate buddy meta group");
		return -ENOMEM;
	}
	if (sbi->s_group_info) {
		memcpy(new_groupinfo, sbi->s_group_info,
		       sbi->s_group_info_size * sizeof(*sbi->s_group_info));
Al Viro's avatar
Al Viro committed
2363
		kvfree(sbi->s_group_info);
2364 2365 2366 2367 2368 2369 2370 2371
	}
	sbi->s_group_info = new_groupinfo;
	sbi->s_group_info_size = size / sizeof(*sbi->s_group_info);
	ext4_debug("allocated s_groupinfo array for %d meta_bg's\n", 
		   sbi->s_group_info_size);
	return 0;
}

2372
/* Create and initialize ext4_group_info data for the given group. */
2373
int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group,
2374 2375
			  struct ext4_group_desc *desc)
{
2376
	int i;
2377 2378 2379
	int metalen = 0;
	struct ext4_sb_info *sbi = EXT4_SB(sb);
	struct ext4_group_info **meta_group_info;
2380
	struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits);
2381 2382 2383 2384 2385 2386 2387 2388 2389

	/*
	 * First check if this group is the first of a reserved block.
	 * If it's true, we have to allocate a new table of pointers
	 * to ext4_group_info structures
	 */
	if (group % EXT4_DESC_PER_BLOCK(sb) == 0) {
		metalen = sizeof(*meta_group_info) <<
			EXT4_DESC_PER_BLOCK_BITS(sb);
2390
		meta_group_info = kmalloc(metalen, GFP_NOFS);
2391
		if (meta_group_info == NULL) {
2392
			ext4_msg(sb, KERN_ERR, "can't allocate mem "
2393
				 "for a buddy group");
2394 2395 2396 2397 2398 2399 2400 2401 2402 2403
			goto exit_meta_group_info;
		}
		sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)] =
			meta_group_info;
	}

	meta_group_info =
		sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)];
	i = group & (EXT4_DESC_PER_BLOCK(sb) - 1);

2404
	meta_group_info[i] = kmem_cache_zalloc(cachep, GFP_NOFS);
2405
	if (meta_group_info[i] == NULL) {
2406
		ext4_msg(sb, KERN_ERR, "can't allocate buddy mem");
2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417
		goto exit_group_info;
	}
	set_bit(EXT4_GROUP_INFO_NEED_INIT_BIT,
		&(meta_group_info[i]->bb_state));

	/*
	 * initialize bb_free to be able to skip
	 * empty groups without initialization
	 */
	if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
		meta_group_info[i]->bb_free =
2418
			ext4_free_clusters_after_init(sb, group, desc);
2419 2420
	} else {
		meta_group_info[i]->bb_free =
2421
			ext4_free_group_clusters(sb, desc);
2422 2423 2424
	}

	INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);
2425
	init_rwsem(&meta_group_info[i]->alloc_sem);
2426
	meta_group_info[i]->bb_free_root = RB_ROOT;
2427
	meta_group_info[i]->bb_largest_free_order = -1;  /* uninit */
2428 2429 2430 2431 2432

#ifdef DOUBLE_CHECK
	{
		struct buffer_head *bh;
		meta_group_info[i]->bb_bitmap =
2433
			kmalloc(sb->s_blocksize, GFP_NOFS);
2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446
		BUG_ON(meta_group_info[i]->bb_bitmap == NULL);
		bh = ext4_read_block_bitmap(sb, group);
		BUG_ON(bh == NULL);
		memcpy(meta_group_info[i]->bb_bitmap, bh->b_data,
			sb->s_blocksize);
		put_bh(bh);
	}
#endif

	return 0;

exit_group_info:
	/* If a meta_group_info table has been allocated, release it now */
2447
	if (group % EXT4_DESC_PER_BLOCK(sb) == 0) {
2448
		kfree(sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)]);
2449 2450
		sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)] = NULL;
	}
2451 2452 2453 2454
exit_meta_group_info:
	return -ENOMEM;
} /* ext4_mb_add_groupinfo */

2455 2456
static int ext4_mb_init_backend(struct super_block *sb)
{
2457
	ext4_group_t ngroups = ext4_get_groups_count(sb);
2458 2459
	ext4_group_t i;
	struct ext4_sb_info *sbi = EXT4_SB(sb);
2460
	int err;
2461
	struct ext4_group_desc *desc;
2462
	struct kmem_cache *cachep;
2463

2464 2465 2466
	err = ext4_mb_alloc_groupinfo(sb, ngroups);
	if (err)
		return err;
2467 2468 2469

	sbi->s_buddy_cache = new_inode(sb);
	if (sbi->s_buddy_cache == NULL) {
2470
		ext4_msg(sb, KERN_ERR, "can't get new inode");
2471 2472
		goto err_freesgi;
	}
2473 2474 2475 2476 2477
	/* To avoid potentially colliding with an valid on-disk inode number,
	 * use EXT4_BAD_INO for the buddy cache inode number.  This inode is
	 * not in the inode hash, so it should never be found by iget(), but
	 * this will avoid confusion if it ever shows up during debugging. */
	sbi->s_buddy_cache->i_ino = EXT4_BAD_INO;
2478
	EXT4_I(sbi->s_buddy_cache)->i_disksize = 0;
2479
	for (i = 0; i < ngroups; i++) {
2480 2481
		desc = ext4_get_group_desc(sb, i, NULL);
		if (desc == NULL) {
2482
			ext4_msg(sb, KERN_ERR, "can't read descriptor %u", i);
2483 2484
			goto err_freebuddy;
		}
2485 2486
		if (ext4_mb_add_groupinfo(sb, i, desc) != 0)
			goto err_freebuddy;
2487 2488 2489 2490 2491
	}

	return 0;

err_freebuddy:
2492
	cachep = get_groupinfo_cache(sb->s_blocksize_bits);
2493
	while (i-- > 0)
2494
		kmem_cache_free(cachep, ext4_get_group_info(sb, i));
2495
	i = sbi->s_group_info_size;
2496
	while (i-- > 0)
2497 2498 2499
		kfree(sbi->s_group_info[i]);
	iput(sbi->s_buddy_cache);
err_freesgi:
Al Viro's avatar
Al Viro committed
2500
	kvfree(sbi->s_group_info);
2501 2502 2503
	return -ENOMEM;
}

2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541
static void ext4_groupinfo_destroy_slabs(void)
{
	int i;

	for (i = 0; i < NR_GRPINFO_CACHES; i++) {
		if (ext4_groupinfo_caches[i])
			kmem_cache_destroy(ext4_groupinfo_caches[i]);
		ext4_groupinfo_caches[i] = NULL;
	}
}

static int ext4_groupinfo_create_slab(size_t size)
{
	static DEFINE_MUTEX(ext4_grpinfo_slab_create_mutex);
	int slab_size;
	int blocksize_bits = order_base_2(size);
	int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;
	struct kmem_cache *cachep;

	if (cache_index >= NR_GRPINFO_CACHES)
		return -EINVAL;

	if (unlikely(cache_index < 0))
		cache_index = 0;

	mutex_lock(&ext4_grpinfo_slab_create_mutex);
	if (ext4_groupinfo_caches[cache_index]) {
		mutex_unlock(&ext4_grpinfo_slab_create_mutex);
		return 0;	/* Already created */
	}

	slab_size = offsetof(struct ext4_group_info,
				bb_counters[blocksize_bits + 2]);

	cachep = kmem_cache_create(ext4_groupinfo_slab_names[cache_index],
					slab_size, 0, SLAB_RECLAIM_ACCOUNT,
					NULL);

2542 2543
	ext4_groupinfo_caches[cache_index] = cachep;

2544 2545
	mutex_unlock(&ext4_grpinfo_slab_create_mutex);
	if (!cachep) {
2546 2547
		printk(KERN_EMERG
		       "EXT4-fs: no memory for groupinfo slab cache\n");
2548 2549 2550 2551 2552 2553
		return -ENOMEM;
	}

	return 0;
}

2554
int ext4_mb_init(struct super_block *sb)
2555 2556
{
	struct ext4_sb_info *sbi = EXT4_SB(sb);
2557
	unsigned i, j;
2558
	unsigned offset, offset_incr;
2559
	unsigned max;
2560
	int ret;
2561

2562
	i = (sb->s_blocksize_bits + 2) * sizeof(*sbi->s_mb_offsets);
2563 2564 2565

	sbi->s_mb_offsets = kmalloc(i, GFP_KERNEL);
	if (sbi->s_mb_offsets == NULL) {
2566 2567
		ret = -ENOMEM;
		goto out;
2568
	}
2569

2570
	i = (sb->s_blocksize_bits + 2) * sizeof(*sbi->s_mb_maxs);
2571 2572
	sbi->s_mb_maxs = kmalloc(i, GFP_KERNEL);
	if (sbi->s_mb_maxs == NULL) {
2573 2574 2575 2576
		ret = -ENOMEM;
		goto out;
	}

2577 2578 2579
	ret = ext4_groupinfo_create_slab(sb->s_blocksize);
	if (ret < 0)
		goto out;
2580 2581 2582 2583 2584 2585 2586

	/* order 0 is regular bitmap */
	sbi->s_mb_maxs[0] = sb->s_blocksize << 3;
	sbi->s_mb_offsets[0] = 0;

	i = 1;
	offset = 0;
2587
	offset_incr = 1 << (sb->s_blocksize_bits - 1);
2588 2589 2590 2591
	max = sb->s_blocksize << 2;
	do {
		sbi->s_mb_offsets[i] = offset;
		sbi->s_mb_maxs[i] = max;
2592 2593
		offset += offset_incr;
		offset_incr = offset_incr >> 1;
2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605
		max = max >> 1;
		i++;
	} while (i <= sb->s_blocksize_bits + 1);

	spin_lock_init(&sbi->s_md_lock);
	spin_lock_init(&sbi->s_bal_lock);

	sbi->s_mb_max_to_scan = MB_DEFAULT_MAX_TO_SCAN;
	sbi->s_mb_min_to_scan = MB_DEFAULT_MIN_TO_SCAN;
	sbi->s_mb_stats = MB_DEFAULT_STATS;
	sbi->s_mb_stream_request = MB_DEFAULT_STREAM_THRESHOLD;
	sbi->s_mb_order2_reqs = MB_DEFAULT_ORDER2_REQS;
2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619
	/*
	 * The default group preallocation is 512, which for 4k block
	 * sizes translates to 2 megabytes.  However for bigalloc file
	 * systems, this is probably too big (i.e, if the cluster size
	 * is 1 megabyte, then group preallocation size becomes half a
	 * gigabyte!).  As a default, we will keep a two megabyte
	 * group pralloc size for cluster sizes up to 64k, and after
	 * that, we will force a minimum group preallocation size of
	 * 32 clusters.  This translates to 8 megs when the cluster
	 * size is 256k, and 32 megs when the cluster size is 1 meg,
	 * which seems reasonable as a default.
	 */
	sbi->s_mb_group_prealloc = max(MB_DEFAULT_GROUP_PREALLOC >>
				       sbi->s_cluster_bits, 32);
2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631
	/*
	 * If there is a s_stripe > 1, then we set the s_mb_group_prealloc
	 * to the lowest multiple of s_stripe which is bigger than
	 * the s_mb_group_prealloc as determined above. We want
	 * the preallocation size to be an exact multiple of the
	 * RAID stripe size so that preallocations don't fragment
	 * the stripes.
	 */
	if (sbi->s_stripe > 1) {
		sbi->s_mb_group_prealloc = roundup(
			sbi->s_mb_group_prealloc, sbi->s_stripe);
	}
2632

2633
	sbi->s_locality_groups = alloc_percpu(struct ext4_locality_group);
2634
	if (sbi->s_locality_groups == NULL) {
2635
		ret = -ENOMEM;
2636
		goto out;
2637
	}
2638
	for_each_possible_cpu(i) {
2639
		struct ext4_locality_group *lg;
2640
		lg = per_cpu_ptr(sbi->s_locality_groups, i);
2641
		mutex_init(&lg->lg_mutex);
2642 2643
		for (j = 0; j < PREALLOC_TB_SIZE; j++)
			INIT_LIST_HEAD(&lg->lg_prealloc_list[j]);
2644 2645 2646
		spin_lock_init(&lg->lg_prealloc_lock);
	}

2647 2648
	/* init file for buddy data */
	ret = ext4_mb_init_backend(sb);
2649 2650
	if (ret != 0)
		goto out_free_locality_groups;
2651

2652 2653 2654
	if (sbi->s_proc)
		proc_create_data("mb_groups", S_IRUGO, sbi->s_proc,
				 &ext4_mb_seq_groups_fops, sb);
2655

2656 2657 2658 2659 2660
	return 0;

out_free_locality_groups:
	free_percpu(sbi->s_locality_groups);
	sbi->s_locality_groups = NULL;
2661
out:
2662 2663 2664 2665
	kfree(sbi->s_mb_offsets);
	sbi->s_mb_offsets = NULL;
	kfree(sbi->s_mb_maxs);
	sbi->s_mb_maxs = NULL;
2666
	return ret;
2667 2668
}

2669
/* need to called with the ext4 group lock held */
2670 2671 2672 2673 2674 2675 2676 2677 2678 2679
static void ext4_mb_cleanup_pa(struct ext4_group_info *grp)
{
	struct ext4_prealloc_space *pa;
	struct list_head *cur, *tmp;
	int count = 0;

	list_for_each_safe(cur, tmp, &grp->bb_prealloc_list) {
		pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
		list_del(&pa->pa_group_list);
		count++;
2680
		kmem_cache_free(ext4_pspace_cachep, pa);
2681 2682
	}
	if (count)
2683
		mb_debug(1, "mballoc: %u PAs left\n", count);
2684 2685 2686 2687 2688

}

int ext4_mb_release(struct super_block *sb)
{
2689
	ext4_group_t ngroups = ext4_get_groups_count(sb);
2690 2691 2692 2693
	ext4_group_t i;
	int num_meta_group_infos;
	struct ext4_group_info *grinfo;
	struct ext4_sb_info *sbi = EXT4_SB(sb);
2694
	struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits);
2695

2696 2697 2698
	if (sbi->s_proc)
		remove_proc_entry("mb_groups", sbi->s_proc);

2699
	if (sbi->s_group_info) {
2700
		for (i = 0; i < ngroups; i++) {
2701 2702 2703 2704 2705 2706 2707
			grinfo = ext4_get_group_info(sb, i);
#ifdef DOUBLE_CHECK
			kfree(grinfo->bb_bitmap);
#endif
			ext4_lock_group(sb, i);
			ext4_mb_cleanup_pa(grinfo);
			ext4_unlock_group(sb, i);
2708
			kmem_cache_free(cachep, grinfo);
2709
		}
2710
		num_meta_group_infos = (ngroups +
2711 2712 2713 2714
				EXT4_DESC_PER_BLOCK(sb) - 1) >>
			EXT4_DESC_PER_BLOCK_BITS(sb);
		for (i = 0; i < num_meta_group_infos; i++)
			kfree(sbi->s_group_info[i]);
Al Viro's avatar
Al Viro committed
2715
		kvfree(sbi->s_group_info);
2716 2717 2718
	}
	kfree(sbi->s_mb_offsets);
	kfree(sbi->s_mb_maxs);
2719
	iput(sbi->s_buddy_cache);
2720
	if (sbi->s_mb_stats) {
2721 2722
		ext4_msg(sb, KERN_INFO,
		       "mballoc: %u blocks %u reqs (%u success)",
2723 2724 2725
				atomic_read(&sbi->s_bal_allocated),
				atomic_read(&sbi->s_bal_reqs),
				atomic_read(&sbi->s_bal_success));
2726 2727 2728
		ext4_msg(sb, KERN_INFO,
		      "mballoc: %u extents scanned, %u goal hits, "
				"%u 2^N hits, %u breaks, %u lost",
2729 2730 2731 2732 2733
				atomic_read(&sbi->s_bal_ex_scanned),
				atomic_read(&sbi->s_bal_goals),
				atomic_read(&sbi->s_bal_2orders),
				atomic_read(&sbi->s_bal_breaks),
				atomic_read(&sbi->s_mb_lost_chunks));
2734 2735
		ext4_msg(sb, KERN_INFO,
		       "mballoc: %lu generated and it took %Lu",
2736
				sbi->s_mb_buddies_generated,
2737
				sbi->s_mb_generation_time);
2738 2739
		ext4_msg(sb, KERN_INFO,
		       "mballoc: %u preallocated, %u discarded",
2740 2741 2742 2743
				atomic_read(&sbi->s_mb_preallocated),
				atomic_read(&sbi->s_mb_discarded));
	}

2744
	free_percpu(sbi->s_locality_groups);
2745 2746 2747 2748

	return 0;
}

2749
static inline int ext4_issue_discard(struct super_block *sb,
2750
		ext4_group_t block_group, ext4_grpblk_t cluster, int count)
2751 2752 2753
{
	ext4_fsblk_t discard_block;

2754 2755 2756
	discard_block = (EXT4_C2B(EXT4_SB(sb), cluster) +
			 ext4_group_first_block_no(sb, block_group));
	count = EXT4_C2B(EXT4_SB(sb), count);
2757 2758
	trace_ext4_discard_blocks(sb,
			(unsigned long long) discard_block, count);
2759
	return sb_issue_discard(sb, discard_block, count, GFP_NOFS, 0);
2760 2761
}

2762 2763 2764 2765
/*
 * This function is called by the jbd2 layer once the commit has finished,
 * so we know we can free the blocks that were released with that commit.
 */
Bobi Jam's avatar
Bobi Jam committed
2766 2767 2768
static void ext4_free_data_callback(struct super_block *sb,
				    struct ext4_journal_cb_entry *jce,
				    int rc)
2769
{
Bobi Jam's avatar
Bobi Jam committed
2770
	struct ext4_free_data *entry = (struct ext4_free_data *)jce;
2771
	struct ext4_buddy e4b;
2772
	struct ext4_group_info *db;
2773
	int err, count = 0, count2 = 0;
2774

Bobi Jam's avatar
Bobi Jam committed
2775 2776
	mb_debug(1, "gonna free %u blocks in group %u (0x%p):",
		 entry->efd_count, entry->efd_group, entry);
2777

2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788
	if (test_opt(sb, DISCARD)) {
		err = ext4_issue_discard(sb, entry->efd_group,
					 entry->efd_start_cluster,
					 entry->efd_count);
		if (err && err != -EOPNOTSUPP)
			ext4_msg(sb, KERN_WARNING, "discard request in"
				 " group:%d block:%d count:%d failed"
				 " with %d", entry->efd_group,
				 entry->efd_start_cluster,
				 entry->efd_count, err);
	}
2789

Bobi Jam's avatar
Bobi Jam committed
2790 2791 2792
	err = ext4_mb_load_buddy(sb, entry->efd_group, &e4b);
	/* we expect to find existing buddy because it's pinned */
	BUG_ON(err != 0);
2793

2794

Bobi Jam's avatar
Bobi Jam committed
2795 2796 2797 2798 2799 2800 2801 2802
	db = e4b.bd_info;
	/* there are blocks to put in buddy to make them really free */
	count += entry->efd_count;
	count2++;
	ext4_lock_group(sb, entry->efd_group);
	/* Take it out of per group rb tree */
	rb_erase(&entry->efd_node, &(db->bb_free_root));
	mb_free_blocks(NULL, &e4b, entry->efd_start_cluster, entry->efd_count);
2803

Bobi Jam's avatar
Bobi Jam committed
2804 2805 2806 2807 2808 2809 2810 2811
	/*
	 * Clear the trimmed flag for the group so that the next
	 * ext4_trim_fs can trim it.
	 * If the volume is mounted with -o discard, online discard
	 * is supported and the free blocks will be trimmed online.
	 */
	if (!test_opt(sb, DISCARD))
		EXT4_MB_GRP_CLEAR_TRIMMED(db);
2812

Bobi Jam's avatar
Bobi Jam committed
2813 2814 2815 2816 2817 2818
	if (!db->bb_free_root.rb_node) {
		/* No more items in the per group rb tree
		 * balance refcounts from ext4_mb_free_metadata()
		 */
		page_cache_release(e4b.bd_buddy_page);
		page_cache_release(e4b.bd_bitmap_page);
2819
	}
Bobi Jam's avatar
Bobi Jam committed
2820 2821 2822
	ext4_unlock_group(sb, entry->efd_group);
	kmem_cache_free(ext4_free_data_cachep, entry);
	ext4_mb_unload_buddy(&e4b);
2823

2824
	mb_debug(1, "freed %u blocks in %u structures\n", count, count2);
2825 2826
}

2827
int __init ext4_init_mballoc(void)
2828
{
2829 2830
	ext4_pspace_cachep = KMEM_CACHE(ext4_prealloc_space,
					SLAB_RECLAIM_ACCOUNT);
2831 2832 2833
	if (ext4_pspace_cachep == NULL)
		return -ENOMEM;

2834 2835
	ext4_ac_cachep = KMEM_CACHE(ext4_allocation_context,
				    SLAB_RECLAIM_ACCOUNT);
2836 2837 2838 2839
	if (ext4_ac_cachep == NULL) {
		kmem_cache_destroy(ext4_pspace_cachep);
		return -ENOMEM;
	}
2840

Bobi Jam's avatar
Bobi Jam committed
2841 2842 2843
	ext4_free_data_cachep = KMEM_CACHE(ext4_free_data,
					   SLAB_RECLAIM_ACCOUNT);
	if (ext4_free_data_cachep == NULL) {
2844 2845 2846 2847
		kmem_cache_destroy(ext4_pspace_cachep);
		kmem_cache_destroy(ext4_ac_cachep);
		return -ENOMEM;
	}
2848 2849 2850
	return 0;
}

2851
void ext4_exit_mballoc(void)
2852
{
2853
	/*
2854 2855 2856 2857
	 * Wait for completion of call_rcu()'s on ext4_pspace_cachep
	 * before destroying the slab cache.
	 */
	rcu_barrier();
2858
	kmem_cache_destroy(ext4_pspace_cachep);
2859
	kmem_cache_destroy(ext4_ac_cachep);
Bobi Jam's avatar
Bobi Jam committed
2860
	kmem_cache_destroy(ext4_free_data_cachep);
2861
	ext4_groupinfo_destroy_slabs();
2862 2863 2864 2865
}


/*
2866
 * Check quota and mark chosen space (ac->ac_b_ex) non-free in bitmaps
2867 2868
 * Returns 0 if success or error code
 */
2869 2870
static noinline_for_stack int
ext4_mb_mark_diskspace_used(struct ext4_allocation_context *ac,
2871
				handle_t *handle, unsigned int reserv_clstrs)
2872 2873 2874 2875 2876 2877 2878
{
	struct buffer_head *bitmap_bh = NULL;
	struct ext4_group_desc *gdp;
	struct buffer_head *gdp_bh;
	struct ext4_sb_info *sbi;
	struct super_block *sb;
	ext4_fsblk_t block;
2879
	int err, len;
2880 2881 2882 2883 2884 2885 2886 2887

	BUG_ON(ac->ac_status != AC_STATUS_FOUND);
	BUG_ON(ac->ac_b_ex.fe_len <= 0);

	sb = ac->ac_sb;
	sbi = EXT4_SB(sb);

	err = -EIO;
2888
	bitmap_bh = ext4_read_block_bitmap(sb, ac->ac_b_ex.fe_group);
2889 2890 2891
	if (!bitmap_bh)
		goto out_err;

2892
	BUFFER_TRACE(bitmap_bh, "getting write access");
2893 2894 2895 2896 2897 2898 2899 2900 2901
	err = ext4_journal_get_write_access(handle, bitmap_bh);
	if (err)
		goto out_err;

	err = -EIO;
	gdp = ext4_get_group_desc(sb, ac->ac_b_ex.fe_group, &gdp_bh);
	if (!gdp)
		goto out_err;

2902
	ext4_debug("using block group %u(%d)\n", ac->ac_b_ex.fe_group,
2903
			ext4_free_group_clusters(sb, gdp));
2904

2905
	BUFFER_TRACE(gdp_bh, "get_write_access");
2906 2907 2908 2909
	err = ext4_journal_get_write_access(handle, gdp_bh);
	if (err)
		goto out_err;

2910
	block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
2911

2912
	len = EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
2913
	if (!ext4_data_block_valid(sbi, block, len)) {
2914
		ext4_error(sb, "Allocating blocks %llu-%llu which overlap "
2915
			   "fs metadata", block, block+len);
2916 2917 2918 2919
		/* File system mounted not to panic on error
		 * Fix the bitmap and repeat the block allocation
		 * We leak some of the blocks here.
		 */
2920
		ext4_lock_group(sb, ac->ac_b_ex.fe_group);
2921 2922
		ext4_set_bits(bitmap_bh->b_data, ac->ac_b_ex.fe_start,
			      ac->ac_b_ex.fe_len);
2923
		ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
2924
		err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
2925 2926 2927
		if (!err)
			err = -EAGAIN;
		goto out_err;
2928
	}
2929 2930

	ext4_lock_group(sb, ac->ac_b_ex.fe_group);
2931 2932 2933 2934 2935 2936 2937 2938 2939
#ifdef AGGRESSIVE_CHECK
	{
		int i;
		for (i = 0; i < ac->ac_b_ex.fe_len; i++) {
			BUG_ON(mb_test_bit(ac->ac_b_ex.fe_start + i,
						bitmap_bh->b_data));
		}
	}
#endif
2940 2941
	ext4_set_bits(bitmap_bh->b_data, ac->ac_b_ex.fe_start,
		      ac->ac_b_ex.fe_len);
2942 2943
	if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
		gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
2944
		ext4_free_group_clusters_set(sb, gdp,
2945
					     ext4_free_clusters_after_init(sb,
2946
						ac->ac_b_ex.fe_group, gdp));
2947
	}
2948 2949
	len = ext4_free_group_clusters(sb, gdp) - ac->ac_b_ex.fe_len;
	ext4_free_group_clusters_set(sb, gdp, len);
2950
	ext4_block_bitmap_csum_set(sb, ac->ac_b_ex.fe_group, gdp, bitmap_bh);
2951
	ext4_group_desc_csum_set(sb, ac->ac_b_ex.fe_group, gdp);
2952 2953

	ext4_unlock_group(sb, ac->ac_b_ex.fe_group);
2954
	percpu_counter_sub(&sbi->s_freeclusters_counter, ac->ac_b_ex.fe_len);
2955
	/*
2956
	 * Now reduce the dirty block count also. Should not go negative
2957
	 */
2958 2959
	if (!(ac->ac_flags & EXT4_MB_DELALLOC_RESERVED))
		/* release all the reserved blocks if non delalloc */
2960 2961
		percpu_counter_sub(&sbi->s_dirtyclusters_counter,
				   reserv_clstrs);
2962

2963 2964 2965
	if (sbi->s_log_groups_per_flex) {
		ext4_group_t flex_group = ext4_flex_group(sbi,
							  ac->ac_b_ex.fe_group);
2966 2967
		atomic64_sub(ac->ac_b_ex.fe_len,
			     &sbi->s_flex_groups[flex_group].free_clusters);
2968 2969
	}

2970
	err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
2971 2972
	if (err)
		goto out_err;
2973
	err = ext4_handle_dirty_metadata(handle, NULL, gdp_bh);
2974 2975

out_err:
2976
	brelse(bitmap_bh);
2977 2978 2979 2980 2981
	return err;
}

/*
 * here we normalize request for locality group
2982 2983 2984
 * Group request are normalized to s_mb_group_prealloc, which goes to
 * s_strip if we set the same via mount option.
 * s_mb_group_prealloc can be configured via
2985
 * /sys/fs/ext4/<partition>/mb_group_prealloc
2986 2987 2988 2989 2990 2991 2992 2993 2994
 *
 * XXX: should we try to preallocate more than the group has now?
 */
static void ext4_mb_normalize_group_request(struct ext4_allocation_context *ac)
{
	struct super_block *sb = ac->ac_sb;
	struct ext4_locality_group *lg = ac->ac_lg;

	BUG_ON(lg == NULL);
2995
	ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_mb_group_prealloc;
2996
	mb_debug(1, "#%u: goal %u blocks for locality group\n",
2997 2998 2999 3000 3001 3002 3003
		current->pid, ac->ac_g_ex.fe_len);
}

/*
 * Normalization means making request better in terms of
 * size and alignment
 */
3004 3005
static noinline_for_stack void
ext4_mb_normalize_request(struct ext4_allocation_context *ac,
3006 3007
				struct ext4_allocation_request *ar)
{
3008
	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3009 3010
	int bsbits, max;
	ext4_lblk_t end;
3011 3012
	loff_t size, start_off;
	loff_t orig_size __maybe_unused;
3013
	ext4_lblk_t start;
3014
	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
3015
	struct ext4_prealloc_space *pa;
3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039

	/* do normalize only data requests, metadata requests
	   do not need preallocation */
	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
		return;

	/* sometime caller may want exact blocks */
	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
		return;

	/* caller may indicate that preallocation isn't
	 * required (it's a tail, for example) */
	if (ac->ac_flags & EXT4_MB_HINT_NOPREALLOC)
		return;

	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) {
		ext4_mb_normalize_group_request(ac);
		return ;
	}

	bsbits = ac->ac_sb->s_blocksize_bits;

	/* first, let's learn actual file size
	 * given current request is allocated */
3040
	size = ac->ac_o_ex.fe_logical + EXT4_C2B(sbi, ac->ac_o_ex.fe_len);
3041 3042 3043
	size = size << bsbits;
	if (size < i_size_read(ac->ac_inode))
		size = i_size_read(ac->ac_inode);
3044
	orig_size = size;
3045

3046 3047
	/* max size of free chunks */
	max = 2 << bsbits;
3048

3049 3050
#define NRL_CHECK_SIZE(req, size, max, chunk_size)	\
		(req <= (size) || max <= (chunk_size))
3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068

	/* first, try to predict filesize */
	/* XXX: should this table be tunable? */
	start_off = 0;
	if (size <= 16 * 1024) {
		size = 16 * 1024;
	} else if (size <= 32 * 1024) {
		size = 32 * 1024;
	} else if (size <= 64 * 1024) {
		size = 64 * 1024;
	} else if (size <= 128 * 1024) {
		size = 128 * 1024;
	} else if (size <= 256 * 1024) {
		size = 256 * 1024;
	} else if (size <= 512 * 1024) {
		size = 512 * 1024;
	} else if (size <= 1024 * 1024) {
		size = 1024 * 1024;
3069
	} else if (NRL_CHECK_SIZE(size, 4 * 1024 * 1024, max, 2 * 1024)) {
3070
		start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
3071 3072 3073
						(21 - bsbits)) << 21;
		size = 2 * 1024 * 1024;
	} else if (NRL_CHECK_SIZE(size, 8 * 1024 * 1024, max, 4 * 1024)) {
3074 3075 3076 3077
		start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
							(22 - bsbits)) << 22;
		size = 4 * 1024 * 1024;
	} else if (NRL_CHECK_SIZE(ac->ac_o_ex.fe_len,
3078
					(8<<20)>>bsbits, max, 8 * 1024)) {
3079 3080 3081 3082
		start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
							(23 - bsbits)) << 23;
		size = 8 * 1024 * 1024;
	} else {
3083 3084 3085
		start_off = (loff_t) ac->ac_o_ex.fe_logical << bsbits;
		size	  = (loff_t) EXT4_C2B(EXT4_SB(ac->ac_sb),
					      ac->ac_o_ex.fe_len) << bsbits;
3086
	}
3087 3088
	size = size >> bsbits;
	start = start_off >> bsbits;
3089 3090 3091 3092 3093 3094 3095 3096 3097

	/* don't cover already allocated blocks in selected range */
	if (ar->pleft && start <= ar->lleft) {
		size -= ar->lleft + 1 - start;
		start = ar->lleft + 1;
	}
	if (ar->pright && start + size - 1 >= ar->lright)
		size -= start + size - ar->lright;

3098 3099 3100 3101 3102 3103 3104
	/*
	 * Trim allocation request for filesystems with artificially small
	 * groups.
	 */
	if (size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb))
		size = EXT4_BLOCKS_PER_GROUP(ac->ac_sb);

3105 3106 3107 3108
	end = start + size;

	/* check we don't cross already preallocated blocks */
	rcu_read_lock();
3109
	list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
3110
		ext4_lblk_t pa_end;
3111 3112 3113 3114 3115 3116 3117 3118 3119

		if (pa->pa_deleted)
			continue;
		spin_lock(&pa->pa_lock);
		if (pa->pa_deleted) {
			spin_unlock(&pa->pa_lock);
			continue;
		}

3120 3121
		pa_end = pa->pa_lstart + EXT4_C2B(EXT4_SB(ac->ac_sb),
						  pa->pa_len);
3122 3123 3124 3125 3126

		/* PA must not overlap original request */
		BUG_ON(!(ac->ac_o_ex.fe_logical >= pa_end ||
			ac->ac_o_ex.fe_logical < pa->pa_lstart));

3127 3128
		/* skip PAs this normalized request doesn't overlap with */
		if (pa->pa_lstart >= end || pa_end <= start) {
3129 3130 3131 3132 3133
			spin_unlock(&pa->pa_lock);
			continue;
		}
		BUG_ON(pa->pa_lstart <= start && pa_end >= end);

3134
		/* adjust start or end to be adjacent to this pa */
3135 3136 3137
		if (pa_end <= ac->ac_o_ex.fe_logical) {
			BUG_ON(pa_end < start);
			start = pa_end;
3138
		} else if (pa->pa_lstart > ac->ac_o_ex.fe_logical) {
3139 3140 3141 3142 3143 3144 3145 3146 3147 3148
			BUG_ON(pa->pa_lstart > end);
			end = pa->pa_lstart;
		}
		spin_unlock(&pa->pa_lock);
	}
	rcu_read_unlock();
	size = end - start;

	/* XXX: extra loop to check we really don't overlap preallocations */
	rcu_read_lock();
3149
	list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
3150
		ext4_lblk_t pa_end;
3151

3152 3153
		spin_lock(&pa->pa_lock);
		if (pa->pa_deleted == 0) {
3154 3155
			pa_end = pa->pa_lstart + EXT4_C2B(EXT4_SB(ac->ac_sb),
							  pa->pa_len);
3156 3157 3158 3159 3160 3161 3162 3163
			BUG_ON(!(start >= pa_end || end <= pa->pa_lstart));
		}
		spin_unlock(&pa->pa_lock);
	}
	rcu_read_unlock();

	if (start + size <= ac->ac_o_ex.fe_logical &&
			start > ac->ac_o_ex.fe_logical) {
3164 3165 3166 3167
		ext4_msg(ac->ac_sb, KERN_ERR,
			 "start %lu, size %lu, fe_logical %lu",
			 (unsigned long) start, (unsigned long) size,
			 (unsigned long) ac->ac_o_ex.fe_logical);
3168
		BUG();
3169
	}
3170
	BUG_ON(size <= 0 || size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb));
3171 3172 3173 3174 3175 3176

	/* now prepare goal request */

	/* XXX: is it better to align blocks WRT to logical
	 * placement or satisfy big request as is */
	ac->ac_g_ex.fe_logical = start;
3177
	ac->ac_g_ex.fe_len = EXT4_NUM_B2C(sbi, size);
3178 3179 3180 3181 3182 3183 3184 3185 3186 3187 3188 3189 3190 3191 3192 3193 3194

	/* define goal start in order to merge */
	if (ar->pright && (ar->lright == (start + size))) {
		/* merge to the right */
		ext4_get_group_no_and_offset(ac->ac_sb, ar->pright - size,
						&ac->ac_f_ex.fe_group,
						&ac->ac_f_ex.fe_start);
		ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
	}
	if (ar->pleft && (ar->lleft + 1 == start)) {
		/* merge to the left */
		ext4_get_group_no_and_offset(ac->ac_sb, ar->pleft + 1,
						&ac->ac_f_ex.fe_group,
						&ac->ac_f_ex.fe_start);
		ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
	}

3195
	mb_debug(1, "goal: %u(was %u) blocks at %u\n", (unsigned) size,
3196 3197 3198 3199 3200 3201 3202 3203 3204 3205
		(unsigned) orig_size, (unsigned) start);
}

static void ext4_mb_collect_stats(struct ext4_allocation_context *ac)
{
	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);

	if (sbi->s_mb_stats && ac->ac_g_ex.fe_len > 1) {
		atomic_inc(&sbi->s_bal_reqs);
		atomic_add(ac->ac_b_ex.fe_len, &sbi->s_bal_allocated);
3206
		if (ac->ac_b_ex.fe_len >= ac->ac_o_ex.fe_len)
3207 3208 3209 3210 3211 3212 3213 3214 3215
			atomic_inc(&sbi->s_bal_success);
		atomic_add(ac->ac_found, &sbi->s_bal_ex_scanned);
		if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&
				ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)
			atomic_inc(&sbi->s_bal_goals);
		if (ac->ac_found > sbi->s_mb_max_to_scan)
			atomic_inc(&sbi->s_bal_breaks);
	}

3216 3217 3218 3219
	if (ac->ac_op == EXT4_MB_HISTORY_ALLOC)
		trace_ext4_mballoc_alloc(ac);
	else
		trace_ext4_mballoc_prealloc(ac);
3220 3221
}

3222 3223 3224 3225 3226 3227 3228 3229 3230
/*
 * Called on failure; free up any blocks from the inode PA for this
 * context.  We don't need this for MB_GROUP_PA because we only change
 * pa_free in ext4_mb_release_context(), but on failure, we've already
 * zeroed out ac->ac_b_ex.fe_len, so group_pa->pa_free is not changed.
 */
static void ext4_discard_allocated_blocks(struct ext4_allocation_context *ac)
{
	struct ext4_prealloc_space *pa = ac->ac_pa;
3231 3232
	struct ext4_buddy e4b;
	int err;
3233

3234
	if (pa == NULL) {
3235 3236
		if (ac->ac_f_ex.fe_len == 0)
			return;
3237 3238 3239 3240 3241 3242 3243 3244 3245 3246 3247 3248 3249 3250
		err = ext4_mb_load_buddy(ac->ac_sb, ac->ac_f_ex.fe_group, &e4b);
		if (err) {
			/*
			 * This should never happen since we pin the
			 * pages in the ext4_allocation_context so
			 * ext4_mb_load_buddy() should never fail.
			 */
			WARN(1, "mb_load_buddy failed (%d)", err);
			return;
		}
		ext4_lock_group(ac->ac_sb, ac->ac_f_ex.fe_group);
		mb_free_blocks(ac->ac_inode, &e4b, ac->ac_f_ex.fe_start,
			       ac->ac_f_ex.fe_len);
		ext4_unlock_group(ac->ac_sb, ac->ac_f_ex.fe_group);
3251
		ext4_mb_unload_buddy(&e4b);
3252 3253 3254
		return;
	}
	if (pa->pa_type == MB_INODE_PA)
3255
		pa->pa_free += ac->ac_b_ex.fe_len;
3256 3257
}

3258 3259 3260 3261 3262 3263
/*
 * use blocks preallocated to inode
 */
static void ext4_mb_use_inode_pa(struct ext4_allocation_context *ac,
				struct ext4_prealloc_space *pa)
{
3264
	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3265 3266 3267 3268 3269 3270
	ext4_fsblk_t start;
	ext4_fsblk_t end;
	int len;

	/* found preallocated blocks, use them */
	start = pa->pa_pstart + (ac->ac_o_ex.fe_logical - pa->pa_lstart);
3271 3272 3273
	end = min(pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len),
		  start + EXT4_C2B(sbi, ac->ac_o_ex.fe_len));
	len = EXT4_NUM_B2C(sbi, end - start);
3274 3275 3276 3277 3278 3279 3280
	ext4_get_group_no_and_offset(ac->ac_sb, start, &ac->ac_b_ex.fe_group,
					&ac->ac_b_ex.fe_start);
	ac->ac_b_ex.fe_len = len;
	ac->ac_status = AC_STATUS_FOUND;
	ac->ac_pa = pa;

	BUG_ON(start < pa->pa_pstart);
3281
	BUG_ON(end > pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len));
3282 3283 3284
	BUG_ON(pa->pa_free < len);
	pa->pa_free -= len;

3285
	mb_debug(1, "use %llu/%u from inode pa %p\n", start, len, pa);
3286 3287 3288 3289 3290 3291 3292 3293
}

/*
 * use blocks preallocated to locality group
 */
static void ext4_mb_use_group_pa(struct ext4_allocation_context *ac,
				struct ext4_prealloc_space *pa)
{
3294
	unsigned int len = ac->ac_o_ex.fe_len;
3295

3296 3297 3298 3299 3300 3301 3302 3303
	ext4_get_group_no_and_offset(ac->ac_sb, pa->pa_pstart,
					&ac->ac_b_ex.fe_group,
					&ac->ac_b_ex.fe_start);
	ac->ac_b_ex.fe_len = len;
	ac->ac_status = AC_STATUS_FOUND;
	ac->ac_pa = pa;

	/* we don't correct pa_pstart or pa_plen here to avoid
3304
	 * possible race when the group is being loaded concurrently
3305
	 * instead we correct pa later, after blocks are marked
3306 3307
	 * in on-disk bitmap -- see ext4_mb_release_context()
	 * Other CPUs are prevented from allocating from this pa by lg_mutex
3308
	 */
3309
	mb_debug(1, "use %u/%u from group pa %p\n", pa->pa_lstart-len, len, pa);
3310 3311
}

3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331
/*
 * Return the prealloc space that have minimal distance
 * from the goal block. @cpa is the prealloc
 * space that is having currently known minimal distance
 * from the goal block.
 */
static struct ext4_prealloc_space *
ext4_mb_check_group_pa(ext4_fsblk_t goal_block,
			struct ext4_prealloc_space *pa,
			struct ext4_prealloc_space *cpa)
{
	ext4_fsblk_t cur_distance, new_distance;

	if (cpa == NULL) {
		atomic_inc(&pa->pa_count);
		return pa;
	}
	cur_distance = abs(goal_block - cpa->pa_pstart);
	new_distance = abs(goal_block - pa->pa_pstart);

3332
	if (cur_distance <= new_distance)
3333 3334 3335 3336 3337 3338 3339 3340
		return cpa;

	/* drop the previous reference */
	atomic_dec(&cpa->pa_count);
	atomic_inc(&pa->pa_count);
	return pa;
}

3341 3342 3343
/*
 * search goal blocks in preallocated space
 */
3344 3345
static noinline_for_stack int
ext4_mb_use_preallocated(struct ext4_allocation_context *ac)
3346
{
3347
	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
3348
	int order, i;
3349 3350
	struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
	struct ext4_locality_group *lg;
3351 3352
	struct ext4_prealloc_space *pa, *cpa = NULL;
	ext4_fsblk_t goal_block;
3353 3354 3355 3356 3357 3358 3359

	/* only data can be preallocated */
	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
		return 0;

	/* first, try per-file preallocation */
	rcu_read_lock();
3360
	list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
3361 3362 3363 3364

		/* all fields in this condition don't change,
		 * so we can skip locking for them */
		if (ac->ac_o_ex.fe_logical < pa->pa_lstart ||
3365 3366
		    ac->ac_o_ex.fe_logical >= (pa->pa_lstart +
					       EXT4_C2B(sbi, pa->pa_len)))
3367 3368
			continue;

3369
		/* non-extent files can't have physical blocks past 2^32 */
3370
		if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)) &&
3371 3372
		    (pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len) >
		     EXT4_MAX_BLOCK_FILE_PHYS))
3373 3374
			continue;

3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396
		/* found preallocated blocks, use them */
		spin_lock(&pa->pa_lock);
		if (pa->pa_deleted == 0 && pa->pa_free) {
			atomic_inc(&pa->pa_count);
			ext4_mb_use_inode_pa(ac, pa);
			spin_unlock(&pa->pa_lock);
			ac->ac_criteria = 10;
			rcu_read_unlock();
			return 1;
		}
		spin_unlock(&pa->pa_lock);
	}
	rcu_read_unlock();

	/* can we use group allocation? */
	if (!(ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC))
		return 0;

	/* inode may have no locality group for some reason */
	lg = ac->ac_lg;
	if (lg == NULL)
		return 0;
3397 3398 3399 3400 3401
	order  = fls(ac->ac_o_ex.fe_len) - 1;
	if (order > PREALLOC_TB_SIZE - 1)
		/* The max size of hash table is PREALLOC_TB_SIZE */
		order = PREALLOC_TB_SIZE - 1;

3402
	goal_block = ext4_grp_offs_to_block(ac->ac_sb, &ac->ac_g_ex);
3403 3404 3405 3406
	/*
	 * search for the prealloc space that is having
	 * minimal distance from the goal block.
	 */
3407 3408 3409 3410 3411 3412 3413
	for (i = order; i < PREALLOC_TB_SIZE; i++) {
		rcu_read_lock();
		list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[i],
					pa_inode_list) {
			spin_lock(&pa->pa_lock);
			if (pa->pa_deleted == 0 &&
					pa->pa_free >= ac->ac_o_ex.fe_len) {
3414 3415 3416

				cpa = ext4_mb_check_group_pa(goal_block,
								pa, cpa);
3417
			}
3418 3419
			spin_unlock(&pa->pa_lock);
		}
3420
		rcu_read_unlock();
3421
	}
3422 3423 3424 3425 3426
	if (cpa) {
		ext4_mb_use_group_pa(ac, cpa);
		ac->ac_criteria = 20;
		return 1;
	}
3427 3428 3429
	return 0;
}

3430 3431 3432 3433
/*
 * the function goes through all block freed in the group
 * but not yet committed and marks them used in in-core bitmap.
 * buddy must be generated from this bitmap
3434
 * Need to be called with the ext4 group lock held
3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446
 */
static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
						ext4_group_t group)
{
	struct rb_node *n;
	struct ext4_group_info *grp;
	struct ext4_free_data *entry;

	grp = ext4_get_group_info(sb, group);
	n = rb_first(&(grp->bb_free_root));

	while (n) {
Bobi Jam's avatar
Bobi Jam committed
3447 3448
		entry = rb_entry(n, struct ext4_free_data, efd_node);
		ext4_set_bits(bitmap, entry->efd_start_cluster, entry->efd_count);
3449 3450 3451 3452 3453
		n = rb_next(n);
	}
	return;
}

3454 3455 3456
/*
 * the function goes through all preallocation in this group and marks them
 * used in in-core bitmap. buddy must be generated from this bitmap
3457
 * Need to be called with ext4 group lock held
3458
 */
3459 3460
static noinline_for_stack
void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap,
3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486 3487 3488
					ext4_group_t group)
{
	struct ext4_group_info *grp = ext4_get_group_info(sb, group);
	struct ext4_prealloc_space *pa;
	struct list_head *cur;
	ext4_group_t groupnr;
	ext4_grpblk_t start;
	int preallocated = 0;
	int len;

	/* all form of preallocation discards first load group,
	 * so the only competing code is preallocation use.
	 * we don't need any locking here
	 * notice we do NOT ignore preallocations with pa_deleted
	 * otherwise we could leave used blocks available for
	 * allocation in buddy when concurrent ext4_mb_put_pa()
	 * is dropping preallocation
	 */
	list_for_each(cur, &grp->bb_prealloc_list) {
		pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
		spin_lock(&pa->pa_lock);
		ext4_get_group_no_and_offset(sb, pa->pa_pstart,
					     &groupnr, &start);
		len = pa->pa_len;
		spin_unlock(&pa->pa_lock);
		if (unlikely(len == 0))
			continue;
		BUG_ON(groupnr != group);
3489
		ext4_set_bits(bitmap, start, len);
3490 3491
		preallocated += len;
	}
3492
	mb_debug(1, "prellocated %u for group %u\n", preallocated, group);
3493 3494 3495 3496 3497 3498
}

static void ext4_mb_pa_callback(struct rcu_head *head)
{
	struct ext4_prealloc_space *pa;
	pa = container_of(head, struct ext4_prealloc_space, u.pa_rcu);
3499 3500 3501

	BUG_ON(atomic_read(&pa->pa_count));
	BUG_ON(pa->pa_deleted == 0);
3502 3503 3504 3505 3506 3507 3508 3509 3510 3511
	kmem_cache_free(ext4_pspace_cachep, pa);
}

/*
 * drops a reference to preallocated space descriptor
 * if this was the last reference and the space is consumed
 */
static void ext4_mb_put_pa(struct ext4_allocation_context *ac,
			struct super_block *sb, struct ext4_prealloc_space *pa)
{
3512
	ext4_group_t grp;
3513
	ext4_fsblk_t grp_blk;
3514 3515 3516

	/* in this short window concurrent discard can set pa_deleted */
	spin_lock(&pa->pa_lock);
3517 3518 3519 3520 3521
	if (!atomic_dec_and_test(&pa->pa_count) || pa->pa_free != 0) {
		spin_unlock(&pa->pa_lock);
		return;
	}

3522 3523 3524 3525 3526 3527 3528 3529
	if (pa->pa_deleted == 1) {
		spin_unlock(&pa->pa_lock);
		return;
	}

	pa->pa_deleted = 1;
	spin_unlock(&pa->pa_lock);

3530
	grp_blk = pa->pa_pstart;
3531
	/*
3532 3533 3534 3535
	 * If doing group-based preallocation, pa_pstart may be in the
	 * next group when pa is used up
	 */
	if (pa->pa_type == MB_GROUP_PA)
3536 3537
		grp_blk--;

3538
	grp = ext4_get_group_number(sb, grp_blk);
3539 3540 3541 3542 3543 3544 3545 3546 3547 3548 3549 3550 3551 3552 3553 3554 3555 3556 3557 3558 3559 3560 3561 3562 3563 3564 3565 3566 3567

	/*
	 * possible race:
	 *
	 *  P1 (buddy init)			P2 (regular allocation)
	 *					find block B in PA
	 *  copy on-disk bitmap to buddy
	 *  					mark B in on-disk bitmap
	 *					drop PA from group
	 *  mark all PAs in buddy
	 *
	 * thus, P1 initializes buddy with B available. to prevent this
	 * we make "copy" and "mark all PAs" atomic and serialize "drop PA"
	 * against that pair
	 */
	ext4_lock_group(sb, grp);
	list_del(&pa->pa_group_list);
	ext4_unlock_group(sb, grp);

	spin_lock(pa->pa_obj_lock);
	list_del_rcu(&pa->pa_inode_list);
	spin_unlock(pa->pa_obj_lock);

	call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
}

/*
 * creates new preallocated space for given inode
 */
3568 3569
static noinline_for_stack int
ext4_mb_new_inode_pa(struct ext4_allocation_context *ac)
3570 3571
{
	struct super_block *sb = ac->ac_sb;
3572
	struct ext4_sb_info *sbi = EXT4_SB(sb);
3573 3574 3575 3576 3577 3578 3579 3580 3581 3582 3583 3584 3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 3595 3596 3597 3598 3599 3600 3601 3602 3603
	struct ext4_prealloc_space *pa;
	struct ext4_group_info *grp;
	struct ext4_inode_info *ei;

	/* preallocate only when found space is larger then requested */
	BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
	BUG_ON(ac->ac_status != AC_STATUS_FOUND);
	BUG_ON(!S_ISREG(ac->ac_inode->i_mode));

	pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS);
	if (pa == NULL)
		return -ENOMEM;

	if (ac->ac_b_ex.fe_len < ac->ac_g_ex.fe_len) {
		int winl;
		int wins;
		int win;
		int offs;

		/* we can't allocate as much as normalizer wants.
		 * so, found space must get proper lstart
		 * to cover original request */
		BUG_ON(ac->ac_g_ex.fe_logical > ac->ac_o_ex.fe_logical);
		BUG_ON(ac->ac_g_ex.fe_len < ac->ac_o_ex.fe_len);

		/* we're limited by original request in that
		 * logical block must be covered any way
		 * winl is window we can move our chunk within */
		winl = ac->ac_o_ex.fe_logical - ac->ac_g_ex.fe_logical;

		/* also, we should cover whole original request */
3604
		wins = EXT4_C2B(sbi, ac->ac_b_ex.fe_len - ac->ac_o_ex.fe_len);
3605 3606 3607 3608

		/* the smallest one defines real window */
		win = min(winl, wins);

3609 3610
		offs = ac->ac_o_ex.fe_logical %
			EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
3611 3612 3613
		if (offs && offs < win)
			win = offs;

3614
		ac->ac_b_ex.fe_logical = ac->ac_o_ex.fe_logical -
3615
			EXT4_NUM_B2C(sbi, win);
3616 3617 3618 3619 3620 3621 3622 3623 3624 3625 3626 3627 3628 3629
		BUG_ON(ac->ac_o_ex.fe_logical < ac->ac_b_ex.fe_logical);
		BUG_ON(ac->ac_o_ex.fe_len > ac->ac_b_ex.fe_len);
	}

	/* preallocation can change ac_b_ex, thus we store actually
	 * allocated blocks for history */
	ac->ac_f_ex = ac->ac_b_ex;

	pa->pa_lstart = ac->ac_b_ex.fe_logical;
	pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
	pa->pa_len = ac->ac_b_ex.fe_len;
	pa->pa_free = pa->pa_len;
	atomic_set(&pa->pa_count, 1);
	spin_lock_init(&pa->pa_lock);
3630 3631
	INIT_LIST_HEAD(&pa->pa_inode_list);
	INIT_LIST_HEAD(&pa->pa_group_list);
3632
	pa->pa_deleted = 0;
3633
	pa->pa_type = MB_INODE_PA;
3634

3635
	mb_debug(1, "new inode pa %p: %llu/%u for %u\n", pa,
3636
			pa->pa_pstart, pa->pa_len, pa->pa_lstart);
3637
	trace_ext4_mb_new_inode_pa(ac, pa);
3638 3639

	ext4_mb_use_inode_pa(ac, pa);
3640
	atomic_add(pa->pa_free, &sbi->s_mb_preallocated);
3641 3642 3643 3644 3645 3646 3647 3648 3649 3650 3651 3652 3653 3654 3655 3656 3657 3658 3659 3660 3661

	ei = EXT4_I(ac->ac_inode);
	grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);

	pa->pa_obj_lock = &ei->i_prealloc_lock;
	pa->pa_inode = ac->ac_inode;

	ext4_lock_group(sb, ac->ac_b_ex.fe_group);
	list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
	ext4_unlock_group(sb, ac->ac_b_ex.fe_group);

	spin_lock(pa->pa_obj_lock);
	list_add_rcu(&pa->pa_inode_list, &ei->i_prealloc_list);
	spin_unlock(pa->pa_obj_lock);

	return 0;
}

/*
 * creates new preallocated space for locality group inodes belongs to
 */
3662 3663
static noinline_for_stack int
ext4_mb_new_group_pa(struct ext4_allocation_context *ac)
3664 3665 3666 3667 3668 3669 3670 3671 3672 3673 3674 3675 3676 3677 3678 3679 3680 3681 3682 3683 3684 3685 3686 3687 3688 3689
{
	struct super_block *sb = ac->ac_sb;
	struct ext4_locality_group *lg;
	struct ext4_prealloc_space *pa;
	struct ext4_group_info *grp;

	/* preallocate only when found space is larger then requested */
	BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
	BUG_ON(ac->ac_status != AC_STATUS_FOUND);
	BUG_ON(!S_ISREG(ac->ac_inode->i_mode));

	BUG_ON(ext4_pspace_cachep == NULL);
	pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS);
	if (pa == NULL)
		return -ENOMEM;

	/* preallocation can change ac_b_ex, thus we store actually
	 * allocated blocks for history */
	ac->ac_f_ex = ac->ac_b_ex;

	pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
	pa->pa_lstart = pa->pa_pstart;
	pa->pa_len = ac->ac_b_ex.fe_len;
	pa->pa_free = pa->pa_len;
	atomic_set(&pa->pa_count, 1);
	spin_lock_init(&pa->pa_lock);
3690
	INIT_LIST_HEAD(&pa->pa_inode_list);
3691
	INIT_LIST_HEAD(&pa->pa_group_list);
3692
	pa->pa_deleted = 0;
3693
	pa->pa_type = MB_GROUP_PA;
3694

3695
	mb_debug(1, "new group pa %p: %llu/%u for %u\n", pa,
3696 3697
			pa->pa_pstart, pa->pa_len, pa->pa_lstart);
	trace_ext4_mb_new_group_pa(ac, pa);
3698 3699 3700 3701 3702 3703 3704 3705 3706 3707 3708 3709 3710 3711 3712

	ext4_mb_use_group_pa(ac, pa);
	atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated);

	grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
	lg = ac->ac_lg;
	BUG_ON(lg == NULL);

	pa->pa_obj_lock = &lg->lg_prealloc_lock;
	pa->pa_inode = NULL;

	ext4_lock_group(sb, ac->ac_b_ex.fe_group);
	list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
	ext4_unlock_group(sb, ac->ac_b_ex.fe_group);

3713 3714 3715 3716
	/*
	 * We will later add the new pa to the right bucket
	 * after updating the pa_free in ext4_mb_release_context
	 */
3717 3718 3719 3720 3721 3722 3723 3724 3725 3726 3727 3728 3729 3730 3731 3732 3733 3734 3735 3736 3737 3738
	return 0;
}

static int ext4_mb_new_preallocation(struct ext4_allocation_context *ac)
{
	int err;

	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
		err = ext4_mb_new_group_pa(ac);
	else
		err = ext4_mb_new_inode_pa(ac);
	return err;
}

/*
 * finds all unused blocks in on-disk bitmap, frees them in
 * in-core bitmap and buddy.
 * @pa must be unlinked from inode and group lists, so that
 * nobody else can find/use it.
 * the caller MUST hold group/inode locks.
 * TODO: optimize the case when there are no in-core structures yet
 */
3739 3740
static noinline_for_stack int
ext4_mb_release_inode_pa(struct ext4_buddy *e4b, struct buffer_head *bitmap_bh,
3741
			struct ext4_prealloc_space *pa)
3742 3743 3744
{
	struct super_block *sb = e4b->bd_sb;
	struct ext4_sb_info *sbi = EXT4_SB(sb);
3745 3746
	unsigned int end;
	unsigned int next;
3747 3748
	ext4_group_t group;
	ext4_grpblk_t bit;
3749
	unsigned long long grp_blk_start;
3750 3751 3752 3753 3754
	int err = 0;
	int free = 0;

	BUG_ON(pa->pa_deleted == 0);
	ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);
3755
	grp_blk_start = pa->pa_pstart - EXT4_C2B(sbi, bit);
3756 3757 3758 3759
	BUG_ON(group != e4b->bd_group && pa->pa_len != 0);
	end = bit + pa->pa_len;

	while (bit < end) {
3760
		bit = mb_find_next_zero_bit(bitmap_bh->b_data, end, bit);
3761 3762
		if (bit >= end)
			break;
3763
		next = mb_find_next_bit(bitmap_bh->b_data, end, bit);
3764
		mb_debug(1, "    free preallocated %u/%u in group %u\n",
3765 3766
			 (unsigned) ext4_group_first_block_no(sb, group) + bit,
			 (unsigned) next - bit, (unsigned) group);
3767 3768
		free += next - bit;

3769
		trace_ext4_mballoc_discard(sb, NULL, group, bit, next - bit);
3770 3771
		trace_ext4_mb_release_inode_pa(pa, (grp_blk_start +
						    EXT4_C2B(sbi, bit)),
3772
					       next - bit);
3773 3774 3775 3776
		mb_free_blocks(pa->pa_inode, e4b, bit, next - bit);
		bit = next + 1;
	}
	if (free != pa->pa_free) {
3777 3778 3779 3780 3781
		ext4_msg(e4b->bd_sb, KERN_CRIT,
			 "pa %p: logic %lu, phys. %lu, len %lu",
			 pa, (unsigned long) pa->pa_lstart,
			 (unsigned long) pa->pa_pstart,
			 (unsigned long) pa->pa_len);
3782
		ext4_grp_locked_error(sb, group, 0, 0, "free %u, pa_free %u",
3783
					free, pa->pa_free);
3784 3785 3786 3787
		/*
		 * pa is already deleted so we use the value obtained
		 * from the bitmap and continue.
		 */
3788 3789 3790 3791 3792 3793
	}
	atomic_add(free, &sbi->s_mb_discarded);

	return err;
}

3794 3795
static noinline_for_stack int
ext4_mb_release_group_pa(struct ext4_buddy *e4b,
3796
				struct ext4_prealloc_space *pa)
3797 3798 3799 3800 3801
{
	struct super_block *sb = e4b->bd_sb;
	ext4_group_t group;
	ext4_grpblk_t bit;

3802
	trace_ext4_mb_release_group_pa(sb, pa);
3803 3804 3805 3806 3807
	BUG_ON(pa->pa_deleted == 0);
	ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);
	BUG_ON(group != e4b->bd_group && pa->pa_len != 0);
	mb_free_blocks(pa->pa_inode, e4b, bit, pa->pa_len);
	atomic_add(pa->pa_len, &EXT4_SB(sb)->s_mb_discarded);
3808
	trace_ext4_mballoc_discard(sb, NULL, group, bit, pa->pa_len);
3809 3810 3811 3812 3813 3814 3815 3816 3817 3818 3819 3820 3821

	return 0;
}

/*
 * releases all preallocations in given group
 *
 * first, we need to decide discard policy:
 * - when do we discard
 *   1) ENOSPC
 * - how many do we discard
 *   1) how many requested
 */
3822 3823
static noinline_for_stack int
ext4_mb_discard_group_preallocations(struct super_block *sb,
3824 3825 3826 3827 3828 3829 3830 3831 3832 3833 3834
					ext4_group_t group, int needed)
{
	struct ext4_group_info *grp = ext4_get_group_info(sb, group);
	struct buffer_head *bitmap_bh = NULL;
	struct ext4_prealloc_space *pa, *tmp;
	struct list_head list;
	struct ext4_buddy e4b;
	int err;
	int busy = 0;
	int free = 0;

3835
	mb_debug(1, "discard preallocation for group %u\n", group);
3836 3837 3838 3839

	if (list_empty(&grp->bb_prealloc_list))
		return 0;

3840
	bitmap_bh = ext4_read_block_bitmap(sb, group);
3841
	if (bitmap_bh == NULL) {
3842
		ext4_error(sb, "Error reading block bitmap for %u", group);
3843
		return 0;
3844 3845 3846
	}

	err = ext4_mb_load_buddy(sb, group, &e4b);
3847
	if (err) {
3848
		ext4_error(sb, "Error loading buddy information for %u", group);
3849 3850 3851
		put_bh(bitmap_bh);
		return 0;
	}
3852 3853

	if (needed == 0)
3854
		needed = EXT4_CLUSTERS_PER_GROUP(sb) + 1;
3855 3856 3857 3858 3859 3860 3861 3862 3863 3864 3865 3866 3867 3868 3869 3870 3871 3872 3873 3874 3875 3876 3877 3878 3879 3880 3881 3882 3883 3884 3885 3886 3887

	INIT_LIST_HEAD(&list);
repeat:
	ext4_lock_group(sb, group);
	list_for_each_entry_safe(pa, tmp,
				&grp->bb_prealloc_list, pa_group_list) {
		spin_lock(&pa->pa_lock);
		if (atomic_read(&pa->pa_count)) {
			spin_unlock(&pa->pa_lock);
			busy = 1;
			continue;
		}
		if (pa->pa_deleted) {
			spin_unlock(&pa->pa_lock);
			continue;
		}

		/* seems this one can be freed ... */
		pa->pa_deleted = 1;

		/* we can trust pa_free ... */
		free += pa->pa_free;

		spin_unlock(&pa->pa_lock);

		list_del(&pa->pa_group_list);
		list_add(&pa->u.pa_tmp_list, &list);
	}

	/* if we still need more blocks and some PAs were used, try again */
	if (free < needed && busy) {
		busy = 0;
		ext4_unlock_group(sb, group);
Lukas Czerner's avatar
Lukas Czerner committed
3888
		cond_resched();
3889 3890 3891 3892 3893 3894 3895 3896 3897 3898 3899 3900 3901 3902 3903 3904 3905
		goto repeat;
	}

	/* found anything to free? */
	if (list_empty(&list)) {
		BUG_ON(free != 0);
		goto out;
	}

	/* now free all selected PAs */
	list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {

		/* remove from object (inode or locality group) */
		spin_lock(pa->pa_obj_lock);
		list_del_rcu(&pa->pa_inode_list);
		spin_unlock(pa->pa_obj_lock);

3906
		if (pa->pa_type == MB_GROUP_PA)
3907
			ext4_mb_release_group_pa(&e4b, pa);
3908
		else
3909
			ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa);
3910 3911 3912 3913 3914 3915 3916

		list_del(&pa->u.pa_tmp_list);
		call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
	}

out:
	ext4_unlock_group(sb, group);
3917
	ext4_mb_unload_buddy(&e4b);
3918 3919 3920 3921 3922 3923 3924 3925 3926 3927 3928 3929 3930
	put_bh(bitmap_bh);
	return free;
}

/*
 * releases all non-used preallocated blocks for given inode
 *
 * It's important to discard preallocations under i_data_sem
 * We don't want another block to be served from the prealloc
 * space when we are discarding the inode prealloc space.
 *
 * FIXME!! Make sure it is valid at all the call sites
 */
3931
void ext4_discard_preallocations(struct inode *inode)
3932 3933 3934 3935 3936 3937 3938 3939 3940 3941
{
	struct ext4_inode_info *ei = EXT4_I(inode);
	struct super_block *sb = inode->i_sb;
	struct buffer_head *bitmap_bh = NULL;
	struct ext4_prealloc_space *pa, *tmp;
	ext4_group_t group = 0;
	struct list_head list;
	struct ext4_buddy e4b;
	int err;

3942
	if (!S_ISREG(inode->i_mode)) {
3943 3944 3945 3946
		/*BUG_ON(!list_empty(&ei->i_prealloc_list));*/
		return;
	}

3947
	mb_debug(1, "discard preallocation for inode %lu\n", inode->i_ino);
3948
	trace_ext4_discard_preallocations(inode);
3949 3950 3951 3952 3953 3954 3955 3956 3957 3958 3959 3960 3961 3962 3963 3964

	INIT_LIST_HEAD(&list);

repeat:
	/* first, collect all pa's in the inode */
	spin_lock(&ei->i_prealloc_lock);
	while (!list_empty(&ei->i_prealloc_list)) {
		pa = list_entry(ei->i_prealloc_list.next,
				struct ext4_prealloc_space, pa_inode_list);
		BUG_ON(pa->pa_obj_lock != &ei->i_prealloc_lock);
		spin_lock(&pa->pa_lock);
		if (atomic_read(&pa->pa_count)) {
			/* this shouldn't happen often - nobody should
			 * use preallocation while we're discarding it */
			spin_unlock(&pa->pa_lock);
			spin_unlock(&ei->i_prealloc_lock);
3965 3966
			ext4_msg(sb, KERN_ERR,
				 "uh-oh! used pa while discarding");
3967 3968 3969 3970 3971 3972 3973 3974 3975 3976 3977 3978 3979 3980 3981 3982 3983 3984 3985 3986 3987 3988 3989 3990 3991 3992 3993 3994 3995 3996 3997 3998 3999 4000 4001
			WARN_ON(1);
			schedule_timeout_uninterruptible(HZ);
			goto repeat;

		}
		if (pa->pa_deleted == 0) {
			pa->pa_deleted = 1;
			spin_unlock(&pa->pa_lock);
			list_del_rcu(&pa->pa_inode_list);
			list_add(&pa->u.pa_tmp_list, &list);
			continue;
		}

		/* someone is deleting pa right now */
		spin_unlock(&pa->pa_lock);
		spin_unlock(&ei->i_prealloc_lock);

		/* we have to wait here because pa_deleted
		 * doesn't mean pa is already unlinked from
		 * the list. as we might be called from
		 * ->clear_inode() the inode will get freed
		 * and concurrent thread which is unlinking
		 * pa from inode's list may access already
		 * freed memory, bad-bad-bad */

		/* XXX: if this happens too often, we can
		 * add a flag to force wait only in case
		 * of ->clear_inode(), but not in case of
		 * regular truncate */
		schedule_timeout_uninterruptible(HZ);
		goto repeat;
	}
	spin_unlock(&ei->i_prealloc_lock);

	list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) {
4002
		BUG_ON(pa->pa_type != MB_INODE_PA);
4003
		group = ext4_get_group_number(sb, pa->pa_pstart);
4004 4005

		err = ext4_mb_load_buddy(sb, group, &e4b);
4006
		if (err) {
4007 4008
			ext4_error(sb, "Error loading buddy information for %u",
					group);
4009 4010
			continue;
		}
4011

4012
		bitmap_bh = ext4_read_block_bitmap(sb, group);
4013
		if (bitmap_bh == NULL) {
4014 4015
			ext4_error(sb, "Error reading block bitmap for %u",
					group);
4016
			ext4_mb_unload_buddy(&e4b);
4017
			continue;
4018 4019 4020 4021
		}

		ext4_lock_group(sb, group);
		list_del(&pa->pa_group_list);
4022
		ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa);
4023 4024
		ext4_unlock_group(sb, group);

4025
		ext4_mb_unload_buddy(&e4b);
4026 4027 4028 4029 4030 4031 4032
		put_bh(bitmap_bh);

		list_del(&pa->u.pa_tmp_list);
		call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
	}
}

4033
#ifdef CONFIG_EXT4_DEBUG
4034 4035 4036
static void ext4_mb_show_ac(struct ext4_allocation_context *ac)
{
	struct super_block *sb = ac->ac_sb;
4037
	ext4_group_t ngroups, i;
4038

4039
	if (!ext4_mballoc_debug ||
4040
	    (EXT4_SB(sb)->s_mount_flags & EXT4_MF_FS_ABORTED))
4041 4042
		return;

4043
	ext4_msg(ac->ac_sb, KERN_ERR, "Can't allocate:"
4044
			" Allocation context details:");
4045
	ext4_msg(ac->ac_sb, KERN_ERR, "status %d flags %d",
4046
			ac->ac_status, ac->ac_flags);
4047
	ext4_msg(ac->ac_sb, KERN_ERR, "orig %lu/%lu/%lu@%lu, "
4048 4049
		 	"goal %lu/%lu/%lu@%lu, "
			"best %lu/%lu/%lu@%lu cr %d",
4050 4051 4052 4053 4054 4055 4056 4057 4058 4059 4060 4061 4062
			(unsigned long)ac->ac_o_ex.fe_group,
			(unsigned long)ac->ac_o_ex.fe_start,
			(unsigned long)ac->ac_o_ex.fe_len,
			(unsigned long)ac->ac_o_ex.fe_logical,
			(unsigned long)ac->ac_g_ex.fe_group,
			(unsigned long)ac->ac_g_ex.fe_start,
			(unsigned long)ac->ac_g_ex.fe_len,
			(unsigned long)ac->ac_g_ex.fe_logical,
			(unsigned long)ac->ac_b_ex.fe_group,
			(unsigned long)ac->ac_b_ex.fe_start,
			(unsigned long)ac->ac_b_ex.fe_len,
			(unsigned long)ac->ac_b_ex.fe_logical,
			(int)ac->ac_criteria);
4063
	ext4_msg(ac->ac_sb, KERN_ERR, "%d found", ac->ac_found);
4064
	ext4_msg(ac->ac_sb, KERN_ERR, "groups: ");
4065 4066
	ngroups = ext4_get_groups_count(sb);
	for (i = 0; i < ngroups; i++) {
4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 4078
		struct ext4_group_info *grp = ext4_get_group_info(sb, i);
		struct ext4_prealloc_space *pa;
		ext4_grpblk_t start;
		struct list_head *cur;
		ext4_lock_group(sb, i);
		list_for_each(cur, &grp->bb_prealloc_list) {
			pa = list_entry(cur, struct ext4_prealloc_space,
					pa_group_list);
			spin_lock(&pa->pa_lock);
			ext4_get_group_no_and_offset(sb, pa->pa_pstart,
						     NULL, &start);
			spin_unlock(&pa->pa_lock);
4079 4080
			printk(KERN_ERR "PA:%u:%d:%u \n", i,
			       start, pa->pa_len);
4081
		}
4082
		ext4_unlock_group(sb, i);
4083 4084 4085

		if (grp->bb_free == 0)
			continue;
4086
		printk(KERN_ERR "%u: %d/%d \n",
4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102
		       i, grp->bb_free, grp->bb_fragments);
	}
	printk(KERN_ERR "\n");
}
#else
static inline void ext4_mb_show_ac(struct ext4_allocation_context *ac)
{
	return;
}
#endif

/*
 * We use locality group preallocation for small size file. The size of the
 * file is determined by the current size or the resulting size after
 * allocation which ever is larger
 *
4103
 * One can tune this size via /sys/fs/ext4/<partition>/mb_stream_req
4104 4105 4106 4107 4108 4109 4110 4111 4112 4113
 */
static void ext4_mb_group_or_file(struct ext4_allocation_context *ac)
{
	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
	int bsbits = ac->ac_sb->s_blocksize_bits;
	loff_t size, isize;

	if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
		return;

4114 4115 4116
	if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
		return;

4117
	size = ac->ac_o_ex.fe_logical + EXT4_C2B(sbi, ac->ac_o_ex.fe_len);
4118 4119
	isize = (i_size_read(ac->ac_inode) + ac->ac_sb->s_blocksize - 1)
		>> bsbits;
4120

4121 4122 4123 4124 4125 4126 4127
	if ((size == isize) &&
	    !ext4_fs_is_busy(sbi) &&
	    (atomic_read(&ac->ac_inode->i_writecount) == 0)) {
		ac->ac_flags |= EXT4_MB_HINT_NOPREALLOC;
		return;
	}

4128 4129 4130 4131 4132
	if (sbi->s_mb_group_prealloc <= 0) {
		ac->ac_flags |= EXT4_MB_STREAM_ALLOC;
		return;
	}

4133
	/* don't use group allocation for large files */
4134
	size = max(size, isize);
4135
	if (size > sbi->s_mb_stream_request) {
4136
		ac->ac_flags |= EXT4_MB_STREAM_ALLOC;
4137
		return;
4138
	}
4139 4140 4141 4142 4143 4144 4145

	BUG_ON(ac->ac_lg != NULL);
	/*
	 * locality group prealloc space are per cpu. The reason for having
	 * per cpu locality group is to reduce the contention between block
	 * request from multiple CPUs.
	 */
4146
	ac->ac_lg = raw_cpu_ptr(sbi->s_locality_groups);
4147 4148 4149 4150 4151 4152 4153 4154

	/* we're going to use group allocation */
	ac->ac_flags |= EXT4_MB_HINT_GROUP_ALLOC;

	/* serialize all allocations in the group */
	mutex_lock(&ac->ac_lg->lg_mutex);
}

4155 4156
static noinline_for_stack int
ext4_mb_initialize_context(struct ext4_allocation_context *ac,
4157 4158 4159 4160 4161 4162
				struct ext4_allocation_request *ar)
{
	struct super_block *sb = ar->inode->i_sb;
	struct ext4_sb_info *sbi = EXT4_SB(sb);
	struct ext4_super_block *es = sbi->s_es;
	ext4_group_t group;
4163 4164
	unsigned int len;
	ext4_fsblk_t goal;
4165 4166 4167 4168 4169 4170
	ext4_grpblk_t block;

	/* we can't allocate > group size */
	len = ar->len;

	/* just a dirty hack to filter too big requests  */
4171 4172
	if (len >= EXT4_CLUSTERS_PER_GROUP(sb))
		len = EXT4_CLUSTERS_PER_GROUP(sb);
4173 4174 4175 4176 4177 4178 4179 4180 4181

	/* start searching from the goal */
	goal = ar->goal;
	if (goal < le32_to_cpu(es->s_first_data_block) ||
			goal >= ext4_blocks_count(es))
		goal = le32_to_cpu(es->s_first_data_block);
	ext4_get_group_no_and_offset(sb, goal, &group, &block);

	/* set up allocation goals */
4182
	ac->ac_b_ex.fe_logical = EXT4_LBLK_CMASK(sbi, ar->logical);
4183 4184 4185
	ac->ac_status = AC_STATUS_CONTINUE;
	ac->ac_sb = sb;
	ac->ac_inode = ar->inode;
4186
	ac->ac_o_ex.fe_logical = ac->ac_b_ex.fe_logical;
4187 4188 4189
	ac->ac_o_ex.fe_group = group;
	ac->ac_o_ex.fe_start = block;
	ac->ac_o_ex.fe_len = len;
4190
	ac->ac_g_ex = ac->ac_o_ex;
4191 4192 4193 4194 4195 4196
	ac->ac_flags = ar->flags;

	/* we have to define context: we'll we work with a file or
	 * locality group. this is a policy, actually */
	ext4_mb_group_or_file(ac);

4197
	mb_debug(1, "init ac: %u blocks @ %u, goal %u, flags %x, 2^%d, "
4198 4199 4200 4201 4202 4203 4204 4205 4206 4207
			"left: %u/%u, right %u/%u to %swritable\n",
			(unsigned) ar->len, (unsigned) ar->logical,
			(unsigned) ar->goal, ac->ac_flags, ac->ac_2order,
			(unsigned) ar->lleft, (unsigned) ar->pleft,
			(unsigned) ar->lright, (unsigned) ar->pright,
			atomic_read(&ar->inode->i_writecount) ? "" : "non-");
	return 0;

}

4208 4209 4210 4211 4212 4213 4214 4215 4216 4217
static noinline_for_stack void
ext4_mb_discard_lg_preallocations(struct super_block *sb,
					struct ext4_locality_group *lg,
					int order, int total_entries)
{
	ext4_group_t group = 0;
	struct ext4_buddy e4b;
	struct list_head discard_list;
	struct ext4_prealloc_space *pa, *tmp;

4218
	mb_debug(1, "discard locality group preallocation\n");
4219 4220 4221 4222 4223 4224 4225 4226 4227 4228 4229 4230 4231 4232 4233 4234 4235 4236 4237 4238 4239

	INIT_LIST_HEAD(&discard_list);

	spin_lock(&lg->lg_prealloc_lock);
	list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[order],
						pa_inode_list) {
		spin_lock(&pa->pa_lock);
		if (atomic_read(&pa->pa_count)) {
			/*
			 * This is the pa that we just used
			 * for block allocation. So don't
			 * free that
			 */
			spin_unlock(&pa->pa_lock);
			continue;
		}
		if (pa->pa_deleted) {
			spin_unlock(&pa->pa_lock);
			continue;
		}
		/* only lg prealloc space */
4240
		BUG_ON(pa->pa_type != MB_GROUP_PA);
4241 4242 4243 4244 4245 4246 4247 4248 4249 4250 4251 4252 4253 4254 4255 4256 4257 4258 4259 4260 4261 4262 4263

		/* seems this one can be freed ... */
		pa->pa_deleted = 1;
		spin_unlock(&pa->pa_lock);

		list_del_rcu(&pa->pa_inode_list);
		list_add(&pa->u.pa_tmp_list, &discard_list);

		total_entries--;
		if (total_entries <= 5) {
			/*
			 * we want to keep only 5 entries
			 * allowing it to grow to 8. This
			 * mak sure we don't call discard
			 * soon for this list.
			 */
			break;
		}
	}
	spin_unlock(&lg->lg_prealloc_lock);

	list_for_each_entry_safe(pa, tmp, &discard_list, u.pa_tmp_list) {

4264
		group = ext4_get_group_number(sb, pa->pa_pstart);
4265
		if (ext4_mb_load_buddy(sb, group, &e4b)) {
4266 4267
			ext4_error(sb, "Error loading buddy information for %u",
					group);
4268 4269 4270 4271
			continue;
		}
		ext4_lock_group(sb, group);
		list_del(&pa->pa_group_list);
4272
		ext4_mb_release_group_pa(&e4b, pa);
4273 4274
		ext4_unlock_group(sb, group);

4275
		ext4_mb_unload_buddy(&e4b);
4276 4277 4278 4279 4280 4281 4282 4283 4284 4285 4286 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301
		list_del(&pa->u.pa_tmp_list);
		call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
	}
}

/*
 * We have incremented pa_count. So it cannot be freed at this
 * point. Also we hold lg_mutex. So no parallel allocation is
 * possible from this lg. That means pa_free cannot be updated.
 *
 * A parallel ext4_mb_discard_group_preallocations is possible.
 * which can cause the lg_prealloc_list to be updated.
 */

static void ext4_mb_add_n_trim(struct ext4_allocation_context *ac)
{
	int order, added = 0, lg_prealloc_count = 1;
	struct super_block *sb = ac->ac_sb;
	struct ext4_locality_group *lg = ac->ac_lg;
	struct ext4_prealloc_space *tmp_pa, *pa = ac->ac_pa;

	order = fls(pa->pa_free) - 1;
	if (order > PREALLOC_TB_SIZE - 1)
		/* The max size of hash table is PREALLOC_TB_SIZE */
		order = PREALLOC_TB_SIZE - 1;
	/* Add the prealloc space to lg */
4302
	spin_lock(&lg->lg_prealloc_lock);
4303 4304 4305 4306
	list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[order],
						pa_inode_list) {
		spin_lock(&tmp_pa->pa_lock);
		if (tmp_pa->pa_deleted) {
4307
			spin_unlock(&tmp_pa->pa_lock);
4308 4309 4310 4311 4312 4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325
			continue;
		}
		if (!added && pa->pa_free < tmp_pa->pa_free) {
			/* Add to the tail of the previous entry */
			list_add_tail_rcu(&pa->pa_inode_list,
						&tmp_pa->pa_inode_list);
			added = 1;
			/*
			 * we want to count the total
			 * number of entries in the list
			 */
		}
		spin_unlock(&tmp_pa->pa_lock);
		lg_prealloc_count++;
	}
	if (!added)
		list_add_tail_rcu(&pa->pa_inode_list,
					&lg->lg_prealloc_list[order]);
4326
	spin_unlock(&lg->lg_prealloc_lock);
4327 4328 4329 4330

	/* Now trim the list to be not more than 8 elements */
	if (lg_prealloc_count > 8) {
		ext4_mb_discard_lg_preallocations(sb, lg,
4331
						  order, lg_prealloc_count);
4332 4333 4334 4335 4336
		return;
	}
	return ;
}

4337 4338 4339 4340 4341
/*
 * release all resource we used in allocation
 */
static int ext4_mb_release_context(struct ext4_allocation_context *ac)
{
4342
	struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
4343 4344
	struct ext4_prealloc_space *pa = ac->ac_pa;
	if (pa) {
4345
		if (pa->pa_type == MB_GROUP_PA) {
4346
			/* see comment in ext4_mb_use_group_pa() */
4347
			spin_lock(&pa->pa_lock);
4348 4349
			pa->pa_pstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
			pa->pa_lstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
4350 4351 4352
			pa->pa_free -= ac->ac_b_ex.fe_len;
			pa->pa_len -= ac->ac_b_ex.fe_len;
			spin_unlock(&pa->pa_lock);
4353 4354
		}
	}
Aneesh Kumar K.V's avatar
Aneesh Kumar K.V committed
4355 4356 4357 4358 4359
	if (pa) {
		/*
		 * We want to add the pa to the right bucket.
		 * Remove it from the list and while adding
		 * make sure the list to which we are adding
Amir Goldstein's avatar
Amir Goldstein committed
4360
		 * doesn't grow big.
Aneesh Kumar K.V's avatar
Aneesh Kumar K.V committed
4361
		 */
4362
		if ((pa->pa_type == MB_GROUP_PA) && likely(pa->pa_free)) {
Aneesh Kumar K.V's avatar
Aneesh Kumar K.V committed
4363 4364 4365 4366 4367 4368 4369
			spin_lock(pa->pa_obj_lock);
			list_del_rcu(&pa->pa_inode_list);
			spin_unlock(pa->pa_obj_lock);
			ext4_mb_add_n_trim(ac);
		}
		ext4_mb_put_pa(ac, ac->ac_sb, pa);
	}
4370 4371 4372 4373 4374 4375 4376 4377 4378 4379 4380 4381
	if (ac->ac_bitmap_page)
		page_cache_release(ac->ac_bitmap_page);
	if (ac->ac_buddy_page)
		page_cache_release(ac->ac_buddy_page);
	if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
		mutex_unlock(&ac->ac_lg->lg_mutex);
	ext4_mb_collect_stats(ac);
	return 0;
}

static int ext4_mb_discard_preallocations(struct super_block *sb, int needed)
{
4382
	ext4_group_t i, ngroups = ext4_get_groups_count(sb);
4383 4384 4385
	int ret;
	int freed = 0;

4386
	trace_ext4_mb_discard_preallocations(sb, needed);
4387
	for (i = 0; i < ngroups && needed > 0; i++) {
4388 4389 4390 4391 4392 4393 4394 4395 4396 4397 4398 4399 4400 4401
		ret = ext4_mb_discard_group_preallocations(sb, i, needed);
		freed += ret;
		needed -= ret;
	}

	return freed;
}

/*
 * Main entry point into mballoc to allocate blocks
 * it tries to use preallocation first, then falls back
 * to usual allocation
 */
ext4_fsblk_t ext4_mb_new_blocks(handle_t *handle,
4402
				struct ext4_allocation_request *ar, int *errp)
4403
{
4404
	int freed;
4405
	struct ext4_allocation_context *ac = NULL;
4406 4407 4408
	struct ext4_sb_info *sbi;
	struct super_block *sb;
	ext4_fsblk_t block = 0;
4409
	unsigned int inquota = 0;
4410
	unsigned int reserv_clstrs = 0;
4411

4412
	might_sleep();
4413 4414 4415
	sb = ar->inode->i_sb;
	sbi = EXT4_SB(sb);

4416
	trace_ext4_request_blocks(ar);
4417

4418 4419 4420 4421
	/* Allow to use superuser reservation for quota file */
	if (IS_NOQUOTA(ar->inode))
		ar->flags |= EXT4_MB_USE_ROOT_BLOCKS;

4422
	if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0) {
4423 4424 4425
		/* Without delayed allocation we need to verify
		 * there is enough free blocks to do block allocation
		 * and verify allocation doesn't exceed the quota limits.
4426
		 */
4427
		while (ar->len &&
4428
			ext4_claim_free_clusters(sbi, ar->len, ar->flags)) {
4429

4430
			/* let others to free the space */
Lukas Czerner's avatar
Lukas Czerner committed
4431
			cond_resched();
4432 4433 4434
			ar->len = ar->len >> 1;
		}
		if (!ar->len) {
4435 4436 4437
			*errp = -ENOSPC;
			return 0;
		}
4438
		reserv_clstrs = ar->len;
4439
		if (ar->flags & EXT4_MB_USE_ROOT_BLOCKS) {
4440 4441
			dquot_alloc_block_nofail(ar->inode,
						 EXT4_C2B(sbi, ar->len));
4442 4443
		} else {
			while (ar->len &&
4444 4445
				dquot_alloc_block(ar->inode,
						  EXT4_C2B(sbi, ar->len))) {
4446 4447 4448 4449

				ar->flags |= EXT4_MB_HINT_NOPREALLOC;
				ar->len--;
			}
4450 4451 4452 4453
		}
		inquota = ar->len;
		if (ar->len == 0) {
			*errp = -EDQUOT;
4454
			goto out;
4455
		}
4456
	}
4457

4458
	ac = kmem_cache_zalloc(ext4_ac_cachep, GFP_NOFS);
4459
	if (!ac) {
4460
		ar->len = 0;
4461
		*errp = -ENOMEM;
4462
		goto out;
4463 4464 4465
	}

	*errp = ext4_mb_initialize_context(ac, ar);
4466 4467
	if (*errp) {
		ar->len = 0;
4468
		goto out;
4469 4470
	}

4471 4472 4473 4474
	ac->ac_op = EXT4_MB_HISTORY_PREALLOC;
	if (!ext4_mb_use_preallocated(ac)) {
		ac->ac_op = EXT4_MB_HISTORY_ALLOC;
		ext4_mb_normalize_request(ac, ar);
4475 4476
repeat:
		/* allocate space in core */
4477
		*errp = ext4_mb_regular_allocator(ac);
4478 4479
		if (*errp)
			goto discard_and_exit;
4480 4481

		/* as we've just preallocated more space than
4482
		 * user requested originally, we store allocated
4483
		 * space in a special descriptor */
4484
		if (ac->ac_status == AC_STATUS_FOUND &&
4485 4486 4487 4488 4489 4490 4491
		    ac->ac_o_ex.fe_len < ac->ac_b_ex.fe_len)
			*errp = ext4_mb_new_preallocation(ac);
		if (*errp) {
		discard_and_exit:
			ext4_discard_allocated_blocks(ac);
			goto errout;
		}
4492
	}
4493
	if (likely(ac->ac_status == AC_STATUS_FOUND)) {
4494
		*errp = ext4_mb_mark_diskspace_used(ac, handle, reserv_clstrs);
4495
		if (*errp == -EAGAIN) {
4496 4497 4498 4499 4500
			/*
			 * drop the reference that we took
			 * in ext4_mb_use_best_found
			 */
			ext4_mb_release_context(ac);
4501 4502 4503 4504 4505
			ac->ac_b_ex.fe_group = 0;
			ac->ac_b_ex.fe_start = 0;
			ac->ac_b_ex.fe_len = 0;
			ac->ac_status = AC_STATUS_CONTINUE;
			goto repeat;
4506
		} else if (*errp) {
4507
			ext4_discard_allocated_blocks(ac);
4508 4509
			goto errout;
		} else {
4510 4511 4512
			block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
			ar->len = ac->ac_b_ex.fe_len;
		}
4513
	} else {
4514
		freed  = ext4_mb_discard_preallocations(sb, ac->ac_o_ex.fe_len);
4515 4516 4517
		if (freed)
			goto repeat;
		*errp = -ENOSPC;
4518 4519
	}

4520
errout:
4521
	if (*errp) {
4522
		ac->ac_b_ex.fe_len = 0;
4523
		ar->len = 0;
4524
		ext4_mb_show_ac(ac);
4525
	}
4526
	ext4_mb_release_context(ac);
4527 4528 4529
out:
	if (ac)
		kmem_cache_free(ext4_ac_cachep, ac);
4530
	if (inquota && ar->len < inquota)
4531
		dquot_free_block(ar->inode, EXT4_C2B(sbi, inquota - ar->len));
4532
	if (!ar->len) {
4533
		if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0)
4534
			/* release all the reserved blocks if non delalloc */
4535
			percpu_counter_sub(&sbi->s_dirtyclusters_counter,
4536
						reserv_clstrs);
4537
	}
4538

4539
	trace_ext4_allocate_blocks(ar, (unsigned long long)block);
4540

4541 4542 4543
	return block;
}

4544 4545 4546 4547 4548 4549 4550 4551
/*
 * We can merge two free data extents only if the physical blocks
 * are contiguous, AND the extents were freed by the same transaction,
 * AND the blocks are associated with the same group.
 */
static int can_merge(struct ext4_free_data *entry1,
			struct ext4_free_data *entry2)
{
Bobi Jam's avatar
Bobi Jam committed
4552 4553 4554
	if ((entry1->efd_tid == entry2->efd_tid) &&
	    (entry1->efd_group == entry2->efd_group) &&
	    ((entry1->efd_start_cluster + entry1->efd_count) == entry2->efd_start_cluster))
4555 4556 4557 4558
		return 1;
	return 0;
}

4559 4560
static noinline_for_stack int
ext4_mb_free_metadata(handle_t *handle, struct ext4_buddy *e4b,
4561
		      struct ext4_free_data *new_entry)
4562
{
4563
	ext4_group_t group = e4b->bd_group;
4564
	ext4_grpblk_t cluster;
4565
	struct ext4_free_data *entry;
4566 4567 4568
	struct ext4_group_info *db = e4b->bd_info;
	struct super_block *sb = e4b->bd_sb;
	struct ext4_sb_info *sbi = EXT4_SB(sb);
4569 4570 4571
	struct rb_node **n = &db->bb_free_root.rb_node, *node;
	struct rb_node *parent = NULL, *new_node;

4572
	BUG_ON(!ext4_handle_valid(handle));
4573 4574 4575
	BUG_ON(e4b->bd_bitmap_page == NULL);
	BUG_ON(e4b->bd_buddy_page == NULL);

Bobi Jam's avatar
Bobi Jam committed
4576 4577
	new_node = &new_entry->efd_node;
	cluster = new_entry->efd_start_cluster;
4578 4579 4580 4581 4582 4583 4584 4585 4586 4587 4588 4589

	if (!*n) {
		/* first free block exent. We need to
		   protect buddy cache from being freed,
		 * otherwise we'll refresh it from
		 * on-disk bitmap and lose not-yet-available
		 * blocks */
		page_cache_get(e4b->bd_buddy_page);
		page_cache_get(e4b->bd_bitmap_page);
	}
	while (*n) {
		parent = *n;
Bobi Jam's avatar
Bobi Jam committed
4590 4591
		entry = rb_entry(parent, struct ext4_free_data, efd_node);
		if (cluster < entry->efd_start_cluster)
4592
			n = &(*n)->rb_left;
Bobi Jam's avatar
Bobi Jam committed
4593
		else if (cluster >= (entry->efd_start_cluster + entry->efd_count))
4594 4595
			n = &(*n)->rb_right;
		else {
4596
			ext4_grp_locked_error(sb, group, 0,
4597 4598
				ext4_group_first_block_no(sb, group) +
				EXT4_C2B(sbi, cluster),
4599
				"Block already on to-be-freed list");
4600
			return 0;
4601
		}
4602
	}
4603

4604 4605 4606 4607 4608 4609
	rb_link_node(new_node, parent, n);
	rb_insert_color(new_node, &db->bb_free_root);

	/* Now try to see the extent can be merged to left and right */
	node = rb_prev(new_node);
	if (node) {
Bobi Jam's avatar
Bobi Jam committed
4610
		entry = rb_entry(node, struct ext4_free_data, efd_node);
4611 4612
		if (can_merge(entry, new_entry) &&
		    ext4_journal_callback_try_del(handle, &entry->efd_jce)) {
Bobi Jam's avatar
Bobi Jam committed
4613 4614
			new_entry->efd_start_cluster = entry->efd_start_cluster;
			new_entry->efd_count += entry->efd_count;
4615
			rb_erase(node, &(db->bb_free_root));
Bobi Jam's avatar
Bobi Jam committed
4616
			kmem_cache_free(ext4_free_data_cachep, entry);
4617
		}
4618
	}
4619

4620 4621
	node = rb_next(new_node);
	if (node) {
Bobi Jam's avatar
Bobi Jam committed
4622
		entry = rb_entry(node, struct ext4_free_data, efd_node);
4623 4624
		if (can_merge(new_entry, entry) &&
		    ext4_journal_callback_try_del(handle, &entry->efd_jce)) {
Bobi Jam's avatar
Bobi Jam committed
4625
			new_entry->efd_count += entry->efd_count;
4626
			rb_erase(node, &(db->bb_free_root));
Bobi Jam's avatar
Bobi Jam committed
4627
			kmem_cache_free(ext4_free_data_cachep, entry);
4628 4629
		}
	}
4630
	/* Add the extent to transaction's private list */
Bobi Jam's avatar
Bobi Jam committed
4631 4632
	ext4_journal_callback_add(handle, ext4_free_data_callback,
				  &new_entry->efd_jce);
4633 4634 4635
	return 0;
}

4636 4637 4638 4639 4640 4641
/**
 * ext4_free_blocks() -- Free given blocks and update quota
 * @handle:		handle for this transaction
 * @inode:		inode
 * @block:		start physical block to free
 * @count:		number of blocks to count
4642
 * @flags:		flags used by ext4_free_blocks
4643
 */
4644
void ext4_free_blocks(handle_t *handle, struct inode *inode,
4645 4646
		      struct buffer_head *bh, ext4_fsblk_t block,
		      unsigned long count, int flags)
4647
{
4648
	struct buffer_head *bitmap_bh = NULL;
4649 4650
	struct super_block *sb = inode->i_sb;
	struct ext4_group_desc *gdp;
4651
	unsigned int overflow;
4652 4653 4654 4655 4656
	ext4_grpblk_t bit;
	struct buffer_head *gd_bh;
	ext4_group_t block_group;
	struct ext4_sb_info *sbi;
	struct ext4_buddy e4b;
4657
	unsigned int count_clusters;
4658 4659 4660
	int err = 0;
	int ret;

4661
	might_sleep();
4662 4663 4664 4665 4666 4667
	if (bh) {
		if (block)
			BUG_ON(block != bh->b_blocknr);
		else
			block = bh->b_blocknr;
	}
4668 4669

	sbi = EXT4_SB(sb);
4670 4671
	if (!(flags & EXT4_FREE_BLOCKS_VALIDATED) &&
	    !ext4_data_block_valid(sbi, block, count)) {
4672
		ext4_error(sb, "Freeing blocks not in datazone - "
4673
			   "block = %llu, count = %lu", block, count);
4674 4675 4676
		goto error_return;
	}

4677
	ext4_debug("freeing block %llu\n", block);
4678 4679 4680 4681 4682 4683 4684 4685 4686
	trace_ext4_free_blocks(inode, block, count, flags);

	if (flags & EXT4_FREE_BLOCKS_FORGET) {
		struct buffer_head *tbh = bh;
		int i;

		BUG_ON(bh && (count > 1));

		for (i = 0; i < count; i++) {
4687
			cond_resched();
4688 4689 4690
			if (!bh)
				tbh = sb_find_get_block(inode->i_sb,
							block + i);
4691
			if (!tbh)
4692
				continue;
4693
			ext4_forget(handle, flags & EXT4_FREE_BLOCKS_METADATA,
4694 4695 4696 4697
				    inode, tbh, block + i);
		}
	}

4698
	/*
4699 4700 4701 4702 4703 4704 4705 4706
	 * We need to make sure we don't reuse the freed block until
	 * after the transaction is committed, which we can do by
	 * treating the block as metadata, below.  We make an
	 * exception if the inode is to be written in writeback mode
	 * since writeback mode has weak data consistency guarantees.
	 */
	if (!ext4_should_writeback_data(inode))
		flags |= EXT4_FREE_BLOCKS_METADATA;
4707

4708 4709 4710 4711 4712 4713 4714
	/*
	 * If the extent to be freed does not begin on a cluster
	 * boundary, we need to deal with partial clusters at the
	 * beginning and end of the extent.  Normally we will free
	 * blocks at the beginning or the end unless we are explicitly
	 * requested to avoid doing so.
	 */
4715
	overflow = EXT4_PBLK_COFF(sbi, block);
4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728
	if (overflow) {
		if (flags & EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER) {
			overflow = sbi->s_cluster_ratio - overflow;
			block += overflow;
			if (count > overflow)
				count -= overflow;
			else
				return;
		} else {
			block -= overflow;
			count += overflow;
		}
	}
4729
	overflow = EXT4_LBLK_COFF(sbi, count);
4730 4731 4732 4733 4734 4735 4736 4737 4738 4739
	if (overflow) {
		if (flags & EXT4_FREE_BLOCKS_NOFREE_LAST_CLUSTER) {
			if (count > overflow)
				count -= overflow;
			else
				return;
		} else
			count += sbi->s_cluster_ratio - overflow;
	}

4740 4741 4742 4743
do_more:
	overflow = 0;
	ext4_get_group_no_and_offset(sb, block, &block_group, &bit);

4744 4745 4746 4747
	if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(
			ext4_get_group_info(sb, block_group))))
		return;

4748 4749 4750 4751
	/*
	 * Check to see if we are freeing blocks across a group
	 * boundary.
	 */
4752 4753 4754
	if (EXT4_C2B(sbi, bit) + count > EXT4_BLOCKS_PER_GROUP(sb)) {
		overflow = EXT4_C2B(sbi, bit) + count -
			EXT4_BLOCKS_PER_GROUP(sb);
4755 4756
		count -= overflow;
	}
4757
	count_clusters = EXT4_NUM_B2C(sbi, count);
4758
	bitmap_bh = ext4_read_block_bitmap(sb, block_group);
4759 4760
	if (!bitmap_bh) {
		err = -EIO;
4761
		goto error_return;
4762
	}
4763
	gdp = ext4_get_group_desc(sb, block_group, &gd_bh);
4764 4765
	if (!gdp) {
		err = -EIO;
4766
		goto error_return;
4767
	}
4768 4769 4770 4771

	if (in_range(ext4_block_bitmap(sb, gdp), block, count) ||
	    in_range(ext4_inode_bitmap(sb, gdp), block, count) ||
	    in_range(block, ext4_inode_table(sb, gdp),
4772
		     EXT4_SB(sb)->s_itb_per_group) ||
4773
	    in_range(block + count - 1, ext4_inode_table(sb, gdp),
4774
		     EXT4_SB(sb)->s_itb_per_group)) {
4775

4776
		ext4_error(sb, "Freeing blocks in system zone - "
4777
			   "Block = %llu, count = %lu", block, count);
4778 4779
		/* err = 0. ext4_std_error should be a no op */
		goto error_return;
4780 4781 4782 4783 4784 4785 4786 4787 4788 4789 4790 4791 4792 4793 4794 4795 4796 4797 4798
	}

	BUFFER_TRACE(bitmap_bh, "getting write access");
	err = ext4_journal_get_write_access(handle, bitmap_bh);
	if (err)
		goto error_return;

	/*
	 * We are about to modify some metadata.  Call the journal APIs
	 * to unshare ->b_data if a currently-committing transaction is
	 * using it
	 */
	BUFFER_TRACE(gd_bh, "get_write_access");
	err = ext4_journal_get_write_access(handle, gd_bh);
	if (err)
		goto error_return;
#ifdef AGGRESSIVE_CHECK
	{
		int i;
4799
		for (i = 0; i < count_clusters; i++)
4800 4801 4802
			BUG_ON(!mb_test_bit(bit + i, bitmap_bh->b_data));
	}
#endif
4803
	trace_ext4_mballoc_free(sb, inode, block_group, bit, count_clusters);
4804

4805 4806 4807
	err = ext4_mb_load_buddy(sb, block_group, &e4b);
	if (err)
		goto error_return;
4808 4809

	if ((flags & EXT4_FREE_BLOCKS_METADATA) && ext4_handle_valid(handle)) {
4810 4811 4812 4813
		struct ext4_free_data *new_entry;
		/*
		 * blocks being freed are metadata. these blocks shouldn't
		 * be used until this transaction is committed
4814 4815 4816
		 *
		 * We use __GFP_NOFAIL because ext4_free_blocks() is not allowed
		 * to fail.
4817
		 */
4818 4819
		new_entry = kmem_cache_alloc(ext4_free_data_cachep,
				GFP_NOFS|__GFP_NOFAIL);
Bobi Jam's avatar
Bobi Jam committed
4820 4821 4822 4823
		new_entry->efd_start_cluster = bit;
		new_entry->efd_group = block_group;
		new_entry->efd_count = count_clusters;
		new_entry->efd_tid = handle->h_transaction->t_tid;
4824

4825
		ext4_lock_group(sb, block_group);
4826
		mb_clear_bits(bitmap_bh->b_data, bit, count_clusters);
4827
		ext4_mb_free_metadata(handle, &e4b, new_entry);
4828
	} else {
4829 4830 4831 4832
		/* need to update group_info->bb_free and bitmap
		 * with group lock held. generate_buddy look at
		 * them with group lock_held
		 */
4833 4834 4835 4836 4837 4838 4839
		if (test_opt(sb, DISCARD)) {
			err = ext4_issue_discard(sb, block_group, bit, count);
			if (err && err != -EOPNOTSUPP)
				ext4_msg(sb, KERN_WARNING, "discard request in"
					 " group:%d block:%d count:%lu failed"
					 " with %d", block_group, bit, count,
					 err);
4840 4841
		} else
			EXT4_MB_GRP_CLEAR_TRIMMED(e4b.bd_info);
4842

4843
		ext4_lock_group(sb, block_group);
4844 4845
		mb_clear_bits(bitmap_bh->b_data, bit, count_clusters);
		mb_free_blocks(inode, &e4b, bit, count_clusters);
4846 4847
	}

4848 4849
	ret = ext4_free_group_clusters(sb, gdp) + count_clusters;
	ext4_free_group_clusters_set(sb, gdp, ret);
4850
	ext4_block_bitmap_csum_set(sb, block_group, gdp, bitmap_bh);
4851
	ext4_group_desc_csum_set(sb, block_group, gdp);
4852
	ext4_unlock_group(sb, block_group);
4853

4854 4855
	if (sbi->s_log_groups_per_flex) {
		ext4_group_t flex_group = ext4_flex_group(sbi, block_group);
4856 4857
		atomic64_add(count_clusters,
			     &sbi->s_flex_groups[flex_group].free_clusters);
4858 4859
	}

4860
	if (!(flags & EXT4_FREE_BLOCKS_NO_QUOT_UPDATE))
4861
		dquot_free_block(inode, EXT4_C2B(sbi, count_clusters));
4862 4863 4864
	percpu_counter_add(&sbi->s_freeclusters_counter, count_clusters);

	ext4_mb_unload_buddy(&e4b);
4865

4866 4867 4868 4869
	/* We dirtied the bitmap block */
	BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
	err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);

4870 4871
	/* And the group descriptor block */
	BUFFER_TRACE(gd_bh, "dirtied group descriptor block");
4872
	ret = ext4_handle_dirty_metadata(handle, NULL, gd_bh);
4873 4874 4875 4876 4877 4878 4879 4880 4881 4882 4883 4884 4885 4886
	if (!err)
		err = ret;

	if (overflow && !err) {
		block += count;
		count = overflow;
		put_bh(bitmap_bh);
		goto do_more;
	}
error_return:
	brelse(bitmap_bh);
	ext4_std_error(sb, err);
	return;
}
4887

4888
/**
4889
 * ext4_group_add_blocks() -- Add given blocks to an existing group
4890 4891
 * @handle:			handle to this transaction
 * @sb:				super block
4892
 * @block:			start physical block to add to the block group
4893 4894
 * @count:			number of blocks to free
 *
4895
 * This marks the blocks as free in the bitmap and buddy.
4896
 */
4897
int ext4_group_add_blocks(handle_t *handle, struct super_block *sb,
4898 4899 4900 4901 4902 4903 4904 4905 4906
			 ext4_fsblk_t block, unsigned long count)
{
	struct buffer_head *bitmap_bh = NULL;
	struct buffer_head *gd_bh;
	ext4_group_t block_group;
	ext4_grpblk_t bit;
	unsigned int i;
	struct ext4_group_desc *desc;
	struct ext4_sb_info *sbi = EXT4_SB(sb);
4907
	struct ext4_buddy e4b;
4908 4909 4910 4911 4912
	int err = 0, ret, blk_free_count;
	ext4_grpblk_t blocks_freed;

	ext4_debug("Adding block(s) %llu-%llu\n", block, block + count - 1);

4913 4914 4915
	if (count == 0)
		return 0;

4916 4917 4918 4919 4920
	ext4_get_group_no_and_offset(sb, block, &block_group, &bit);
	/*
	 * Check to see if we are freeing blocks across a group
	 * boundary.
	 */
4921 4922 4923 4924
	if (bit + count > EXT4_BLOCKS_PER_GROUP(sb)) {
		ext4_warning(sb, "too much blocks added to group %u\n",
			     block_group);
		err = -EINVAL;
4925
		goto error_return;
4926
	}
4927

4928
	bitmap_bh = ext4_read_block_bitmap(sb, block_group);
4929 4930
	if (!bitmap_bh) {
		err = -EIO;
4931
		goto error_return;
4932 4933
	}

4934
	desc = ext4_get_group_desc(sb, block_group, &gd_bh);
4935 4936
	if (!desc) {
		err = -EIO;
4937
		goto error_return;
4938
	}
4939 4940 4941 4942 4943 4944 4945 4946 4947

	if (in_range(ext4_block_bitmap(sb, desc), block, count) ||
	    in_range(ext4_inode_bitmap(sb, desc), block, count) ||
	    in_range(block, ext4_inode_table(sb, desc), sbi->s_itb_per_group) ||
	    in_range(block + count - 1, ext4_inode_table(sb, desc),
		     sbi->s_itb_per_group)) {
		ext4_error(sb, "Adding blocks in system zones - "
			   "Block = %llu, count = %lu",
			   block, count);
4948
		err = -EINVAL;
4949 4950 4951
		goto error_return;
	}

4952 4953
	BUFFER_TRACE(bitmap_bh, "getting write access");
	err = ext4_journal_get_write_access(handle, bitmap_bh);
4954 4955 4956 4957 4958 4959 4960 4961 4962 4963 4964 4965
	if (err)
		goto error_return;

	/*
	 * We are about to modify some metadata.  Call the journal APIs
	 * to unshare ->b_data if a currently-committing transaction is
	 * using it
	 */
	BUFFER_TRACE(gd_bh, "get_write_access");
	err = ext4_journal_get_write_access(handle, gd_bh);
	if (err)
		goto error_return;
4966

4967 4968
	for (i = 0, blocks_freed = 0; i < count; i++) {
		BUFFER_TRACE(bitmap_bh, "clear bit");
4969
		if (!mb_test_bit(bit + i, bitmap_bh->b_data)) {
4970 4971 4972 4973 4974 4975 4976
			ext4_error(sb, "bit already cleared for block %llu",
				   (ext4_fsblk_t)(block + i));
			BUFFER_TRACE(bitmap_bh, "bit already cleared");
		} else {
			blocks_freed++;
		}
	}
4977 4978 4979 4980 4981 4982 4983 4984 4985 4986

	err = ext4_mb_load_buddy(sb, block_group, &e4b);
	if (err)
		goto error_return;

	/*
	 * need to update group_info->bb_free and bitmap
	 * with group lock held. generate_buddy look at
	 * them with group lock_held
	 */
4987
	ext4_lock_group(sb, block_group);
4988 4989
	mb_clear_bits(bitmap_bh->b_data, bit, count);
	mb_free_blocks(NULL, &e4b, bit, count);
4990 4991
	blk_free_count = blocks_freed + ext4_free_group_clusters(sb, desc);
	ext4_free_group_clusters_set(sb, desc, blk_free_count);
4992
	ext4_block_bitmap_csum_set(sb, block_group, desc, bitmap_bh);
4993
	ext4_group_desc_csum_set(sb, block_group, desc);
4994
	ext4_unlock_group(sb, block_group);
4995
	percpu_counter_add(&sbi->s_freeclusters_counter,
4996
			   EXT4_NUM_B2C(sbi, blocks_freed));
4997 4998 4999

	if (sbi->s_log_groups_per_flex) {
		ext4_group_t flex_group = ext4_flex_group(sbi, block_group);
5000 5001
		atomic64_add(EXT4_NUM_B2C(sbi, blocks_freed),
			     &sbi->s_flex_groups[flex_group].free_clusters);
5002
	}
5003 5004

	ext4_mb_unload_buddy(&e4b);
5005 5006 5007 5008 5009 5010 5011 5012 5013 5014 5015 5016 5017 5018

	/* We dirtied the bitmap block */
	BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
	err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);

	/* And the group descriptor block */
	BUFFER_TRACE(gd_bh, "dirtied group descriptor block");
	ret = ext4_handle_dirty_metadata(handle, NULL, gd_bh);
	if (!err)
		err = ret;

error_return:
	brelse(bitmap_bh);
	ext4_std_error(sb, err);
5019
	return err;
5020 5021
}

5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033
/**
 * ext4_trim_extent -- function to TRIM one single free extent in the group
 * @sb:		super block for the file system
 * @start:	starting block of the free extent in the alloc. group
 * @count:	number of blocks to TRIM
 * @group:	alloc. group we are working with
 * @e4b:	ext4 buddy for the group
 *
 * Trim "count" blocks starting at "start" in the "group". To assure that no
 * one will allocate those blocks, mark it as used in buddy bitmap. This must
 * be called with under the group lock.
 */
5034
static int ext4_trim_extent(struct super_block *sb, int start, int count,
5035
			     ext4_group_t group, struct ext4_buddy *e4b)
5036 5037
__releases(bitlock)
__acquires(bitlock)
5038 5039
{
	struct ext4_free_extent ex;
5040
	int ret = 0;
5041

Tao Ma's avatar
Tao Ma committed
5042 5043
	trace_ext4_trim_extent(sb, group, start, count);

5044 5045 5046 5047 5048 5049 5050 5051 5052 5053 5054 5055
	assert_spin_locked(ext4_group_lock_ptr(sb, group));

	ex.fe_start = start;
	ex.fe_group = group;
	ex.fe_len = count;

	/*
	 * Mark blocks used, so no one can reuse them while
	 * being trimmed.
	 */
	mb_mark_used(e4b, &ex);
	ext4_unlock_group(sb, group);
5056
	ret = ext4_issue_discard(sb, group, start, count);
5057 5058
	ext4_lock_group(sb, group);
	mb_free_blocks(NULL, e4b, start, ex.fe_len);
5059
	return ret;
5060 5061 5062 5063 5064
}

/**
 * ext4_trim_all_free -- function to trim all free space in alloc. group
 * @sb:			super block for file system
5065
 * @group:		group to be trimmed
5066 5067 5068 5069 5070 5071 5072 5073 5074 5075 5076 5077 5078 5079
 * @start:		first group block to examine
 * @max:		last group block to examine
 * @minblocks:		minimum extent block count
 *
 * ext4_trim_all_free walks through group's buddy bitmap searching for free
 * extents. When the free block is found, ext4_trim_extent is called to TRIM
 * the extent.
 *
 *
 * ext4_trim_all_free walks through group's block bitmap searching for free
 * extents. When the free extent is found, mark it as used in group buddy
 * bitmap. Then issue a TRIM command on this extent and free the extent in
 * the group buddy bitmap. This is done until whole group is scanned.
 */
5080
static ext4_grpblk_t
5081 5082 5083
ext4_trim_all_free(struct super_block *sb, ext4_group_t group,
		   ext4_grpblk_t start, ext4_grpblk_t max,
		   ext4_grpblk_t minblocks)
5084 5085
{
	void *bitmap;
5086
	ext4_grpblk_t next, count = 0, free_count = 0;
5087
	struct ext4_buddy e4b;
5088
	int ret = 0;
5089

Tao Ma's avatar
Tao Ma committed
5090 5091
	trace_ext4_trim_all_free(sb, group, start, max);

5092 5093 5094 5095 5096 5097 5098
	ret = ext4_mb_load_buddy(sb, group, &e4b);
	if (ret) {
		ext4_error(sb, "Error in loading buddy "
				"information for %u", group);
		return ret;
	}
	bitmap = e4b.bd_bitmap;
5099 5100

	ext4_lock_group(sb, group);
5101 5102 5103 5104
	if (EXT4_MB_GRP_WAS_TRIMMED(e4b.bd_info) &&
	    minblocks >= atomic_read(&EXT4_SB(sb)->s_last_trim_minblks))
		goto out;

5105 5106
	start = (e4b.bd_info->bb_first_free > start) ?
		e4b.bd_info->bb_first_free : start;
5107

5108 5109 5110
	while (start <= max) {
		start = mb_find_next_zero_bit(bitmap, max + 1, start);
		if (start > max)
5111
			break;
5112
		next = mb_find_next_bit(bitmap, max + 1, start);
5113 5114

		if ((next - start) >= minblocks) {
5115 5116 5117 5118 5119
			ret = ext4_trim_extent(sb, start,
					       next - start, group, &e4b);
			if (ret && ret != -EOPNOTSUPP)
				break;
			ret = 0;
5120 5121
			count += next - start;
		}
5122
		free_count += next - start;
5123 5124 5125 5126 5127 5128 5129 5130 5131 5132 5133 5134 5135
		start = next + 1;

		if (fatal_signal_pending(current)) {
			count = -ERESTARTSYS;
			break;
		}

		if (need_resched()) {
			ext4_unlock_group(sb, group);
			cond_resched();
			ext4_lock_group(sb, group);
		}

5136
		if ((e4b.bd_info->bb_free - free_count) < minblocks)
5137 5138
			break;
	}
5139

5140 5141
	if (!ret) {
		ret = count;
5142
		EXT4_MB_GRP_SET_TRIMMED(e4b.bd_info);
5143
	}
5144
out:
5145
	ext4_unlock_group(sb, group);
5146
	ext4_mb_unload_buddy(&e4b);
5147 5148 5149 5150

	ext4_debug("trimmed %d blocks in the group %d\n",
		count, group);

5151
	return ret;
5152 5153 5154 5155 5156 5157 5158 5159 5160 5161 5162 5163 5164 5165 5166 5167
}

/**
 * ext4_trim_fs() -- trim ioctl handle function
 * @sb:			superblock for filesystem
 * @range:		fstrim_range structure
 *
 * start:	First Byte to trim
 * len:		number of Bytes to trim from start
 * minlen:	minimum extent length in Bytes
 * ext4_trim_fs goes through all allocation groups containing Bytes from
 * start to start+len. For each such a group ext4_trim_all_free function
 * is invoked to trim all free space.
 */
int ext4_trim_fs(struct super_block *sb, struct fstrim_range *range)
{
5168
	struct ext4_group_info *grp;
5169
	ext4_group_t group, first_group, last_group;
5170
	ext4_grpblk_t cnt = 0, first_cluster, last_cluster;
5171
	uint64_t start, end, minlen, trimmed = 0;
5172 5173
	ext4_fsblk_t first_data_blk =
			le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);
5174
	ext4_fsblk_t max_blks = ext4_blocks_count(EXT4_SB(sb)->s_es);
5175 5176 5177
	int ret = 0;

	start = range->start >> sb->s_blocksize_bits;
5178
	end = start + (range->len >> sb->s_blocksize_bits) - 1;
5179 5180
	minlen = EXT4_NUM_B2C(EXT4_SB(sb),
			      range->minlen >> sb->s_blocksize_bits);
5181

5182 5183 5184
	if (minlen > EXT4_CLUSTERS_PER_GROUP(sb) ||
	    start >= max_blks ||
	    range->len < sb->s_blocksize)
5185
		return -EINVAL;
5186 5187 5188
	if (end >= max_blks)
		end = max_blks - 1;
	if (end <= first_data_blk)
5189
		goto out;
5190
	if (start < first_data_blk)
5191
		start = first_data_blk;
5192

5193
	/* Determine first and last group to examine based on start and end */
5194
	ext4_get_group_no_and_offset(sb, (ext4_fsblk_t) start,
5195
				     &first_group, &first_cluster);
5196
	ext4_get_group_no_and_offset(sb, (ext4_fsblk_t) end,
5197
				     &last_group, &last_cluster);
5198

5199 5200
	/* end now represents the last cluster to discard in this group */
	end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;
5201 5202

	for (group = first_group; group <= last_group; group++) {
5203 5204 5205 5206 5207 5208
		grp = ext4_get_group_info(sb, group);
		/* We only do this if the grp has never been initialized */
		if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {
			ret = ext4_mb_init_group(sb, group);
			if (ret)
				break;
5209 5210
		}

5211
		/*
5212 5213 5214 5215
		 * For all the groups except the last one, last cluster will
		 * always be EXT4_CLUSTERS_PER_GROUP(sb)-1, so we only need to
		 * change it for the last group, note that last_cluster is
		 * already computed earlier by ext4_get_group_no_and_offset()
5216
		 */
5217 5218
		if (group == last_group)
			end = last_cluster;
5219

5220
		if (grp->bb_free >= minlen) {
5221
			cnt = ext4_trim_all_free(sb, group, first_cluster,
5222
						end, minlen);
5223 5224 5225 5226
			if (cnt < 0) {
				ret = cnt;
				break;
			}
5227
			trimmed += cnt;
5228
		}
5229 5230 5231 5232 5233

		/*
		 * For every group except the first one, we are sure
		 * that the first cluster to discard will be cluster #0.
		 */
5234
		first_cluster = 0;
5235 5236
	}

5237 5238 5239
	if (!ret)
		atomic_set(&EXT4_SB(sb)->s_last_trim_minblks, minlen);

5240
out:
5241
	range->len = EXT4_C2B(EXT4_SB(sb), trimmed) << sb->s_blocksize_bits;
5242 5243
	return ret;
}