1 /* 2 * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com 3 * Written by Alex Tomas <alex@clusterfs.com> 4 * 5 * This program is free software; you can redistribute it and/or modify 6 * it under the terms of the GNU General Public License version 2 as 7 * published by the Free Software Foundation. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public Licens 15 * along with this program; if not, write to the Free Software 16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111- 17 */ 18 19 20 /* 21 * mballoc.c contains the multiblocks allocation routines 22 */ 23 24 #include "ext4_jbd2.h" 25 #include "mballoc.h" 26 #include <linux/debugfs.h> 27 #include <linux/slab.h> 28 #include <trace/events/ext4.h> 29 30 /* 31 * MUSTDO: 32 * - test ext4_ext_search_left() and ext4_ext_search_right() 33 * - search for metadata in few groups 34 * 35 * TODO v4: 36 * - normalization should take into account whether file is still open 37 * - discard preallocations if no free space left (policy?) 38 * - don't normalize tails 39 * - quota 40 * - reservation for superuser 41 * 42 * TODO v3: 43 * - bitmap read-ahead (proposed by Oleg Drokin aka green) 44 * - track min/max extents in each group for better group selection 45 * - mb_mark_used() may allocate chunk right after splitting buddy 46 * - tree of groups sorted by number of free blocks 47 * - error handling 48 */ 49 50 /* 51 * The allocation request involve request for multiple number of blocks 52 * near to the goal(block) value specified. 53 * 54 * During initialization phase of the allocator we decide to use the 55 * group preallocation or inode preallocation depending on the size of 56 * the file. The size of the file could be the resulting file size we 57 * would have after allocation, or the current file size, which ever 58 * is larger. If the size is less than sbi->s_mb_stream_request we 59 * select to use the group preallocation. The default value of 60 * s_mb_stream_request is 16 blocks. This can also be tuned via 61 * /sys/fs/ext4/<partition>/mb_stream_req. The value is represented in 62 * terms of number of blocks. 63 * 64 * The main motivation for having small file use group preallocation is to 65 * ensure that we have small files closer together on the disk. 66 * 67 * First stage the allocator looks at the inode prealloc list, 68 * ext4_inode_info->i_prealloc_list, which contains list of prealloc 69 * spaces for this particular inode. The inode prealloc space is 70 * represented as: 71 * 72 * pa_lstart -> the logical start block for this prealloc space 73 * pa_pstart -> the physical start block for this prealloc space 74 * pa_len -> length for this prealloc space (in clusters) 75 * pa_free -> free space available in this prealloc space (in clusters) 76 * 77 * The inode preallocation space is used looking at the _logical_ start 78 * block. If only the logical file block falls within the range of prealloc 79 * space we will consume the particular prealloc space. This makes sure that 80 * we have contiguous physical blocks representing the file blocks 81 * 82 * The important thing to be noted in case of inode prealloc space is that 83 * we don't modify the values associated to inode prealloc space except 84 * pa_free. 85 * 86 * If we are not able to find blocks in the inode prealloc space and if we 87 * have the group allocation flag set then we look at the locality group 88 * prealloc space. These are per CPU prealloc list represented as 89 * 90 * ext4_sb_info.s_locality_groups[smp_processor_id()] 91 * 92 * The reason for having a per cpu locality group is to reduce the contention 93 * between CPUs. It is possible to get scheduled at this point. 94 * 95 * The locality group prealloc space is used looking at whether we have 96 * enough free space (pa_free) within the prealloc space. 97 * 98 * If we can't allocate blocks via inode prealloc or/and locality group 99 * prealloc then we look at the buddy cache. The buddy cache is represented 100 * by ext4_sb_info.s_buddy_cache (struct inode) whose file offset gets 101 * mapped to the buddy and bitmap information regarding different 102 * groups. The buddy information is attached to buddy cache inode so that 103 * we can access them through the page cache. The information regarding 104 * each group is loaded via ext4_mb_load_buddy. The information involve 105 * block bitmap and buddy information. The information are stored in the 106 * inode as: 107 * 108 * { page } 109 * [ group 0 bitmap][ group 0 buddy] [group 1][ group 1]... 110 * 111 * 112 * one block each for bitmap and buddy information. So for each group we 113 * take up 2 blocks. A page can contain blocks_per_page (PAGE_CACHE_SIZE / 114 * blocksize) blocks. So it can have information regarding groups_per_page 115 * which is blocks_per_page/2 116 * 117 * The buddy cache inode is not stored on disk. The inode is thrown 118 * away when the filesystem is unmounted. 119 * 120 * We look for count number of blocks in the buddy cache. If we were able 121 * to locate that many free blocks we return with additional information 122 * regarding rest of the contiguous physical block available 123 * 124 * Before allocating blocks via buddy cache we normalize the request 125 * blocks. This ensure we ask for more blocks that we needed. The extra 126 * blocks that we get after allocation is added to the respective prealloc 127 * list. In case of inode preallocation we follow a list of heuristics 128 * based on file size. This can be found in ext4_mb_normalize_request. If 129 * we are doing a group prealloc we try to normalize the request to 130 * sbi->s_mb_group_prealloc. The default value of s_mb_group_prealloc is 131 * dependent on the cluster size; for non-bigalloc file systems, it is 132 * 512 blocks. This can be tuned via 133 * /sys/fs/ext4/<partition>/mb_group_prealloc. The value is represented in 134 * terms of number of blocks. If we have mounted the file system with -O 135 * stripe=<value> option the group prealloc request is normalized to the 136 * the smallest multiple of the stripe value (sbi->s_stripe) which is 137 * greater than the default mb_group_prealloc. 138 * 139 * The regular allocator (using the buddy cache) supports a few tunables. 140 * 141 * /sys/fs/ext4/<partition>/mb_min_to_scan 142 * /sys/fs/ext4/<partition>/mb_max_to_scan 143 * /sys/fs/ext4/<partition>/mb_order2_req 144 * 145 * The regular allocator uses buddy scan only if the request len is power of 146 * 2 blocks and the order of allocation is >= sbi->s_mb_order2_reqs. The 147 * value of s_mb_order2_reqs can be tuned via 148 * /sys/fs/ext4/<partition>/mb_order2_req. If the request len is equal to 149 * stripe size (sbi->s_stripe), we try to search for contiguous block in 150 * stripe size. This should result in better allocation on RAID setups. If 151 * not, we search in the specific group using bitmap for best extents. The 152 * tunable min_to_scan and max_to_scan control the behaviour here. 153 * min_to_scan indicate how long the mballoc __must__ look for a best 154 * extent and max_to_scan indicates how long the mballoc __can__ look for a 155 * best extent in the found extents. Searching for the blocks starts with 156 * the group specified as the goal value in allocation context via 157 * ac_g_ex. Each group is first checked based on the criteria whether it 158 * can be used for allocation. ext4_mb_good_group explains how the groups are 159 * checked. 160 * 161 * Both the prealloc space are getting populated as above. So for the first 162 * request we will hit the buddy cache which will result in this prealloc 163 * space getting filled. The prealloc space is then later used for the 164 * subsequent request. 165 */ 166 167 /* 168 * mballoc operates on the following data: 169 * - on-disk bitmap 170 * - in-core buddy (actually includes buddy and bitmap) 171 * - preallocation descriptors (PAs) 172 * 173 * there are two types of preallocations: 174 * - inode 175 * assiged to specific inode and can be used for this inode only. 176 * it describes part of inode's space preallocated to specific 177 * physical blocks. any block from that preallocated can be used 178 * independent. the descriptor just tracks number of blocks left 179 * unused. so, before taking some block from descriptor, one must 180 * make sure corresponded logical block isn't allocated yet. this 181 * also means that freeing any block within descriptor's range 182 * must discard all preallocated blocks. 183 * - locality group 184 * assigned to specific locality group which does not translate to 185 * permanent set of inodes: inode can join and leave group. space 186 * from this type of preallocation can be used for any inode. thus 187 * it's consumed from the beginning to the end. 188 * 189 * relation between them can be expressed as: 190 * in-core buddy = on-disk bitmap + preallocation descriptors 191 * 192 * this mean blocks mballoc considers used are: 193 * - allocated blocks (persistent) 194 * - preallocated blocks (non-persistent) 195 * 196 * consistency in mballoc world means that at any time a block is either 197 * free or used in ALL structures. notice: "any time" should not be read 198 * literally -- time is discrete and delimited by locks. 199 * 200 * to keep it simple, we don't use block numbers, instead we count number of 201 * blocks: how many blocks marked used/free in on-disk bitmap, buddy and PA. 202 * 203 * all operations can be expressed as: 204 * - init buddy: buddy = on-disk + PAs 205 * - new PA: buddy += N; PA = N 206 * - use inode PA: on-disk += N; PA -= N 207 * - discard inode PA buddy -= on-disk - PA; PA = 0 208 * - use locality group PA on-disk += N; PA -= N 209 * - discard locality group PA buddy -= PA; PA = 0 210 * note: 'buddy -= on-disk - PA' is used to show that on-disk bitmap 211 * is used in real operation because we can't know actual used 212 * bits from PA, only from on-disk bitmap 213 * 214 * if we follow this strict logic, then all operations above should be atomic. 215 * given some of them can block, we'd have to use something like semaphores 216 * killing performance on high-end SMP hardware. let's try to relax it using 217 * the following knowledge: 218 * 1) if buddy is referenced, it's already initialized 219 * 2) while block is used in buddy and the buddy is referenced, 220 * nobody can re-allocate that block 221 * 3) we work on bitmaps and '+' actually means 'set bits'. if on-disk has 222 * bit set and PA claims same block, it's OK. IOW, one can set bit in 223 * on-disk bitmap if buddy has same bit set or/and PA covers corresponded 224 * block 225 * 226 * so, now we're building a concurrency table: 227 * - init buddy vs. 228 * - new PA 229 * blocks for PA are allocated in the buddy, buddy must be referenced 230 * until PA is linked to allocation group to avoid concurrent buddy init 231 * - use inode PA 232 * we need to make sure that either on-disk bitmap or PA has uptodate data 233 * given (3) we care that PA-=N operation doesn't interfere with init 234 * - discard inode PA 235 * the simplest way would be to have buddy initialized by the discard 236 * - use locality group PA 237 * again PA-=N must be serialized with init 238 * - discard locality group PA 239 * the simplest way would be to have buddy initialized by the discard 240 * - new PA vs. 241 * - use inode PA 242 * i_data_sem serializes them 243 * - discard inode PA 244 * discard process must wait until PA isn't used by another process 245 * - use locality group PA 246 * some mutex should serialize them 247 * - discard locality group PA 248 * discard process must wait until PA isn't used by another process 249 * - use inode PA 250 * - use inode PA 251 * i_data_sem or another mutex should serializes them 252 * - discard inode PA 253 * discard process must wait until PA isn't used by another process 254 * - use locality group PA 255 * nothing wrong here -- they're different PAs covering different blocks 256 * - discard locality group PA 257 * discard process must wait until PA isn't used by another process 258 * 259 * now we're ready to make few consequences: 260 * - PA is referenced and while it is no discard is possible 261 * - PA is referenced until block isn't marked in on-disk bitmap 262 * - PA changes only after on-disk bitmap 263 * - discard must not compete with init. either init is done before 264 * any discard or they're serialized somehow 265 * - buddy init as sum of on-disk bitmap and PAs is done atomically 266 * 267 * a special case when we've used PA to emptiness. no need to modify buddy 268 * in this case, but we should care about concurrent init 269 * 270 */ 271 272 /* 273 * Logic in few words: 274 * 275 * - allocation: 276 * load group 277 * find blocks 278 * mark bits in on-disk bitmap 279 * release group 280 * 281 * - use preallocation: 282 * find proper PA (per-inode or group) 283 * load group 284 * mark bits in on-disk bitmap 285 * release group 286 * release PA 287 * 288 * - free: 289 * load group 290 * mark bits in on-disk bitmap 291 * release group 292 * 293 * - discard preallocations in group: 294 * mark PAs deleted 295 * move them onto local list 296 * load on-disk bitmap 297 * load group 298 * remove PA from object (inode or locality group) 299 * mark free blocks in-core 300 * 301 * - discard inode's preallocations: 302 */ 303 304 /* 305 * Locking rules 306 * 307 * Locks: 308 * - bitlock on a group (group) 309 * - object (inode/locality) (object) 310 * - per-pa lock (pa) 311 * 312 * Paths: 313 * - new pa 314 * object 315 * group 316 * 317 * - find and use pa: 318 * pa 319 * 320 * - release consumed pa: 321 * pa 322 * group 323 * object 324 * 325 * - generate in-core bitmap: 326 * group 327 * pa 328 * 329 * - discard all for given object (inode, locality group): 330 * object 331 * pa 332 * group 333 * 334 * - discard all for given group: 335 * group 336 * pa 337 * group 338 * object 339 * 340 */ 341 static struct kmem_cache *ext4_pspace_cachep; 342 static struct kmem_cache *ext4_ac_cachep; 343 static struct kmem_cache *ext4_free_data_cachep; 344 345 /* We create slab caches for groupinfo data structures based on the 346 * superblock block size. There will be one per mounted filesystem for 347 * each unique s_blocksize_bits */ 348 #define NR_GRPINFO_CACHES 8 349 static struct kmem_cache *ext4_groupinfo_caches[NR_GRPINFO_CACHES]; 350 351 static const char *ext4_groupinfo_slab_names[NR_GRPINFO_CACHES] = { 352 "ext4_groupinfo_1k", "ext4_groupinfo_2k", "ext4_groupinfo_4k", 353 "ext4_groupinfo_8k", "ext4_groupinfo_16k", "ext4_groupinfo_32k", 354 "ext4_groupinfo_64k", "ext4_groupinfo_128k" 355 }; 356 357 static void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap, 358 ext4_group_t group); 359 static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap, 360 ext4_group_t group); 361 static void ext4_free_data_callback(struct super_block *sb, 362 struct ext4_journal_cb_entry *jce, int rc); 363 364 static inline void *mb_correct_addr_and_bit(int *bit, void *addr) 365 { 366 #if BITS_PER_LONG == 64 367 *bit += ((unsigned long) addr & 7UL) << 3; 368 addr = (void *) ((unsigned long) addr & ~7UL); 369 #elif BITS_PER_LONG == 32 370 *bit += ((unsigned long) addr & 3UL) << 3; 371 addr = (void *) ((unsigned long) addr & ~3UL); 372 #else 373 #error "how many bits you are?!" 374 #endif 375 return addr; 376 } 377 378 static inline int mb_test_bit(int bit, void *addr) 379 { 380 /* 381 * ext4_test_bit on architecture like powerpc 382 * needs unsigned long aligned address 383 */ 384 addr = mb_correct_addr_and_bit(&bit, addr); 385 return ext4_test_bit(bit, addr); 386 } 387 388 static inline void mb_set_bit(int bit, void *addr) 389 { 390 addr = mb_correct_addr_and_bit(&bit, addr); 391 ext4_set_bit(bit, addr); 392 } 393 394 static inline void mb_clear_bit(int bit, void *addr) 395 { 396 addr = mb_correct_addr_and_bit(&bit, addr); 397 ext4_clear_bit(bit, addr); 398 } 399 400 static inline int mb_find_next_zero_bit(void *addr, int max, int start) 401 { 402 int fix = 0, ret, tmpmax; 403 addr = mb_correct_addr_and_bit(&fix, addr); 404 tmpmax = max + fix; 405 start += fix; 406 407 ret = ext4_find_next_zero_bit(addr, tmpmax, start) - fix; 408 if (ret > max) 409 return max; 410 return ret; 411 } 412 413 static inline int mb_find_next_bit(void *addr, int max, int start) 414 { 415 int fix = 0, ret, tmpmax; 416 addr = mb_correct_addr_and_bit(&fix, addr); 417 tmpmax = max + fix; 418 start += fix; 419 420 ret = ext4_find_next_bit(addr, tmpmax, start) - fix; 421 if (ret > max) 422 return max; 423 return ret; 424 } 425 426 static void *mb_find_buddy(struct ext4_buddy *e4b, int order, int *max) 427 { 428 char *bb; 429 430 BUG_ON(e4b->bd_bitmap == e4b->bd_buddy); 431 BUG_ON(max == NULL); 432 433 if (order > e4b->bd_blkbits + 1) { 434 *max = 0; 435 return NULL; 436 } 437 438 /* at order 0 we see each particular block */ 439 if (order == 0) { 440 *max = 1 << (e4b->bd_blkbits + 3); 441 return e4b->bd_bitmap; 442 } 443 444 bb = e4b->bd_buddy + EXT4_SB(e4b->bd_sb)->s_mb_offsets[order]; 445 *max = EXT4_SB(e4b->bd_sb)->s_mb_maxs[order]; 446 447 return bb; 448 } 449 450 #ifdef DOUBLE_CHECK 451 static void mb_free_blocks_double(struct inode *inode, struct ext4_buddy *e4b, 452 int first, int count) 453 { 454 int i; 455 struct super_block *sb = e4b->bd_sb; 456 457 if (unlikely(e4b->bd_info->bb_bitmap == NULL)) 458 return; 459 assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group)); 460 for (i = 0; i < count; i++) { 461 if (!mb_test_bit(first + i, e4b->bd_info->bb_bitmap)) { 462 ext4_fsblk_t blocknr; 463 464 blocknr = ext4_group_first_block_no(sb, e4b->bd_group); 465 blocknr += EXT4_C2B(EXT4_SB(sb), first + i); 466 ext4_grp_locked_error(sb, e4b->bd_group, 467 inode ? inode->i_ino : 0, 468 blocknr, 469 "freeing block already freed " 470 "(bit %u)", 471 first + i); 472 } 473 mb_clear_bit(first + i, e4b->bd_info->bb_bitmap); 474 } 475 } 476 477 static void mb_mark_used_double(struct ext4_buddy *e4b, int first, int count) 478 { 479 int i; 480 481 if (unlikely(e4b->bd_info->bb_bitmap == NULL)) 482 return; 483 assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group)); 484 for (i = 0; i < count; i++) { 485 BUG_ON(mb_test_bit(first + i, e4b->bd_info->bb_bitmap)); 486 mb_set_bit(first + i, e4b->bd_info->bb_bitmap); 487 } 488 } 489 490 static void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap) 491 { 492 if (memcmp(e4b->bd_info->bb_bitmap, bitmap, e4b->bd_sb->s_blocksize)) { 493 unsigned char *b1, *b2; 494 int i; 495 b1 = (unsigned char *) e4b->bd_info->bb_bitmap; 496 b2 = (unsigned char *) bitmap; 497 for (i = 0; i < e4b->bd_sb->s_blocksize; i++) { 498 if (b1[i] != b2[i]) { 499 ext4_msg(e4b->bd_sb, KERN_ERR, 500 "corruption in group %u " 501 "at byte %u(%u): %x in copy != %x " 502 "on disk/prealloc", 503 e4b->bd_group, i, i * 8, b1[i], b2[i]); 504 BUG(); 505 } 506 } 507 } 508 } 509 510 #else 511 static inline void mb_free_blocks_double(struct inode *inode, 512 struct ext4_buddy *e4b, int first, int count) 513 { 514 return; 515 } 516 static inline void mb_mark_used_double(struct ext4_buddy *e4b, 517 int first, int count) 518 { 519 return; 520 } 521 static inline void mb_cmp_bitmaps(struct ext4_buddy *e4b, void *bitmap) 522 { 523 return; 524 } 525 #endif 526 527 #ifdef AGGRESSIVE_CHECK 528 529 #define MB_CHECK_ASSERT(assert) \ 530 do { \ 531 if (!(assert)) { \ 532 printk(KERN_EMERG \ 533 "Assertion failure in %s() at %s:%d: \"%s\"\n", \ 534 function, file, line, # assert); \ 535 BUG(); \ 536 } \ 537 } while (0) 538 539 static int __mb_check_buddy(struct ext4_buddy *e4b, char *file, 540 const char *function, int line) 541 { 542 struct super_block *sb = e4b->bd_sb; 543 int order = e4b->bd_blkbits + 1; 544 int max; 545 int max2; 546 int i; 547 int j; 548 int k; 549 int count; 550 struct ext4_group_info *grp; 551 int fragments = 0; 552 int fstart; 553 struct list_head *cur; 554 void *buddy; 555 void *buddy2; 556 557 { 558 static int mb_check_counter; 559 if (mb_check_counter++ % 100 != 0) 560 return 0; 561 } 562 563 while (order > 1) { 564 buddy = mb_find_buddy(e4b, order, &max); 565 MB_CHECK_ASSERT(buddy); 566 buddy2 = mb_find_buddy(e4b, order - 1, &max2); 567 MB_CHECK_ASSERT(buddy2); 568 MB_CHECK_ASSERT(buddy != buddy2); 569 MB_CHECK_ASSERT(max * 2 == max2); 570 571 count = 0; 572 for (i = 0; i < max; i++) { 573 574 if (mb_test_bit(i, buddy)) { 575 /* only single bit in buddy2 may be 1 */ 576 if (!mb_test_bit(i << 1, buddy2)) { 577 MB_CHECK_ASSERT( 578 mb_test_bit((i<<1)+1, buddy2)); 579 } else if (!mb_test_bit((i << 1) + 1, buddy2)) { 580 MB_CHECK_ASSERT( 581 mb_test_bit(i << 1, buddy2)); 582 } 583 continue; 584 } 585 586 /* both bits in buddy2 must be 1 */ 587 MB_CHECK_ASSERT(mb_test_bit(i << 1, buddy2)); 588 MB_CHECK_ASSERT(mb_test_bit((i << 1) + 1, buddy2)); 589 590 for (j = 0; j < (1 << order); j++) { 591 k = (i * (1 << order)) + j; 592 MB_CHECK_ASSERT( 593 !mb_test_bit(k, e4b->bd_bitmap)); 594 } 595 count++; 596 } 597 MB_CHECK_ASSERT(e4b->bd_info->bb_counters[order] == count); 598 order--; 599 } 600 601 fstart = -1; 602 buddy = mb_find_buddy(e4b, 0, &max); 603 for (i = 0; i < max; i++) { 604 if (!mb_test_bit(i, buddy)) { 605 MB_CHECK_ASSERT(i >= e4b->bd_info->bb_first_free); 606 if (fstart == -1) { 607 fragments++; 608 fstart = i; 609 } 610 continue; 611 } 612 fstart = -1; 613 /* check used bits only */ 614 for (j = 0; j < e4b->bd_blkbits + 1; j++) { 615 buddy2 = mb_find_buddy(e4b, j, &max2); 616 k = i >> j; 617 MB_CHECK_ASSERT(k < max2); 618 MB_CHECK_ASSERT(mb_test_bit(k, buddy2)); 619 } 620 } 621 MB_CHECK_ASSERT(!EXT4_MB_GRP_NEED_INIT(e4b->bd_info)); 622 MB_CHECK_ASSERT(e4b->bd_info->bb_fragments == fragments); 623 624 grp = ext4_get_group_info(sb, e4b->bd_group); 625 list_for_each(cur, &grp->bb_prealloc_list) { 626 ext4_group_t groupnr; 627 struct ext4_prealloc_space *pa; 628 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list); 629 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &groupnr, &k); 630 MB_CHECK_ASSERT(groupnr == e4b->bd_group); 631 for (i = 0; i < pa->pa_len; i++) 632 MB_CHECK_ASSERT(mb_test_bit(k + i, buddy)); 633 } 634 return 0; 635 } 636 #undef MB_CHECK_ASSERT 637 #define mb_check_buddy(e4b) __mb_check_buddy(e4b, \ 638 __FILE__, __func__, __LINE__) 639 #else 640 #define mb_check_buddy(e4b) 641 #endif 642 643 /* 644 * Divide blocks started from @first with length @len into 645 * smaller chunks with power of 2 blocks. 646 * Clear the bits in bitmap which the blocks of the chunk(s) covered, 647 * then increase bb_counters[] for corresponded chunk size. 648 */ 649 static void ext4_mb_mark_free_simple(struct super_block *sb, 650 void *buddy, ext4_grpblk_t first, ext4_grpblk_t len, 651 struct ext4_group_info *grp) 652 { 653 struct ext4_sb_info *sbi = EXT4_SB(sb); 654 ext4_grpblk_t min; 655 ext4_grpblk_t max; 656 ext4_grpblk_t chunk; 657 unsigned short border; 658 659 BUG_ON(len > EXT4_CLUSTERS_PER_GROUP(sb)); 660 661 border = 2 << sb->s_blocksize_bits; 662 663 while (len > 0) { 664 /* find how many blocks can be covered since this position */ 665 max = ffs(first | border) - 1; 666 667 /* find how many blocks of power 2 we need to mark */ 668 min = fls(len) - 1; 669 670 if (max < min) 671 min = max; 672 chunk = 1 << min; 673 674 /* mark multiblock chunks only */ 675 grp->bb_counters[min]++; 676 if (min > 0) 677 mb_clear_bit(first >> min, 678 buddy + sbi->s_mb_offsets[min]); 679 680 len -= chunk; 681 first += chunk; 682 } 683 } 684 685 /* 686 * Cache the order of the largest free extent we have available in this block 687 * group. 688 */ 689 static void 690 mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp) 691 { 692 int i; 693 int bits; 694 695 grp->bb_largest_free_order = -1; /* uninit */ 696 697 bits = sb->s_blocksize_bits + 1; 698 for (i = bits; i >= 0; i--) { 699 if (grp->bb_counters[i] > 0) { 700 grp->bb_largest_free_order = i; 701 break; 702 } 703 } 704 } 705 706 static noinline_for_stack 707 void ext4_mb_generate_buddy(struct super_block *sb, 708 void *buddy, void *bitmap, ext4_group_t group) 709 { 710 struct ext4_group_info *grp = ext4_get_group_info(sb, group); 711 ext4_grpblk_t max = EXT4_CLUSTERS_PER_GROUP(sb); 712 ext4_grpblk_t i = 0; 713 ext4_grpblk_t first; 714 ext4_grpblk_t len; 715 unsigned free = 0; 716 unsigned fragments = 0; 717 unsigned long long period = get_cycles(); 718 719 /* initialize buddy from bitmap which is aggregation 720 * of on-disk bitmap and preallocations */ 721 i = mb_find_next_zero_bit(bitmap, max, 0); 722 grp->bb_first_free = i; 723 while (i < max) { 724 fragments++; 725 first = i; 726 i = mb_find_next_bit(bitmap, max, i); 727 len = i - first; 728 free += len; 729 if (len > 1) 730 ext4_mb_mark_free_simple(sb, buddy, first, len, grp); 731 else 732 grp->bb_counters[0]++; 733 if (i < max) 734 i = mb_find_next_zero_bit(bitmap, max, i); 735 } 736 grp->bb_fragments = fragments; 737 738 if (free != grp->bb_free) { 739 ext4_grp_locked_error(sb, group, 0, 0, 740 "%u clusters in bitmap, %u in gd", 741 free, grp->bb_free); 742 /* 743 * If we intent to continue, we consider group descritor 744 * corrupt and update bb_free using bitmap value 745 */ 746 grp->bb_free = free; 747 } 748 mb_set_largest_free_order(sb, grp); 749 750 clear_bit(EXT4_GROUP_INFO_NEED_INIT_BIT, &(grp->bb_state)); 751 752 period = get_cycles() - period; 753 spin_lock(&EXT4_SB(sb)->s_bal_lock); 754 EXT4_SB(sb)->s_mb_buddies_generated++; 755 EXT4_SB(sb)->s_mb_generation_time += period; 756 spin_unlock(&EXT4_SB(sb)->s_bal_lock); 757 } 758 759 /* The buddy information is attached the buddy cache inode 760 * for convenience. The information regarding each group 761 * is loaded via ext4_mb_load_buddy. The information involve 762 * block bitmap and buddy information. The information are 763 * stored in the inode as 764 * 765 * { page } 766 * [ group 0 bitmap][ group 0 buddy] [group 1][ group 1]... 767 * 768 * 769 * one block each for bitmap and buddy information. 770 * So for each group we take up 2 blocks. A page can 771 * contain blocks_per_page (PAGE_CACHE_SIZE / blocksize) blocks. 772 * So it can have information regarding groups_per_page which 773 * is blocks_per_page/2 774 * 775 * Locking note: This routine takes the block group lock of all groups 776 * for this page; do not hold this lock when calling this routine! 777 */ 778 779 static int ext4_mb_init_cache(struct page *page, char *incore) 780 { 781 ext4_group_t ngroups; 782 int blocksize; 783 int blocks_per_page; 784 int groups_per_page; 785 int err = 0; 786 int i; 787 ext4_group_t first_group, group; 788 int first_block; 789 struct super_block *sb; 790 struct buffer_head *bhs; 791 struct buffer_head **bh; 792 struct inode *inode; 793 char *data; 794 char *bitmap; 795 struct ext4_group_info *grinfo; 796 797 mb_debug(1, "init page %lu\n", page->index); 798 799 inode = page->mapping->host; 800 sb = inode->i_sb; 801 ngroups = ext4_get_groups_count(sb); 802 blocksize = 1 << inode->i_blkbits; 803 blocks_per_page = PAGE_CACHE_SIZE / blocksize; 804 805 groups_per_page = blocks_per_page >> 1; 806 if (groups_per_page == 0) 807 groups_per_page = 1; 808 809 /* allocate buffer_heads to read bitmaps */ 810 if (groups_per_page > 1) { 811 i = sizeof(struct buffer_head *) * groups_per_page; 812 bh = kzalloc(i, GFP_NOFS); 813 if (bh == NULL) { 814 err = -ENOMEM; 815 goto out; 816 } 817 } else 818 bh = &bhs; 819 820 first_group = page->index * blocks_per_page / 2; 821 822 /* read all groups the page covers into the cache */ 823 for (i = 0, group = first_group; i < groups_per_page; i++, group++) { 824 if (group >= ngroups) 825 break; 826 827 grinfo = ext4_get_group_info(sb, group); 828 /* 829 * If page is uptodate then we came here after online resize 830 * which added some new uninitialized group info structs, so 831 * we must skip all initialized uptodate buddies on the page, 832 * which may be currently in use by an allocating task. 833 */ 834 if (PageUptodate(page) && !EXT4_MB_GRP_NEED_INIT(grinfo)) { 835 bh[i] = NULL; 836 continue; 837 } 838 if (!(bh[i] = ext4_read_block_bitmap_nowait(sb, group))) { 839 err = -ENOMEM; 840 goto out; 841 } 842 mb_debug(1, "read bitmap for group %u\n", group); 843 } 844 845 /* wait for I/O completion */ 846 for (i = 0, group = first_group; i < groups_per_page; i++, group++) { 847 if (bh[i] && ext4_wait_block_bitmap(sb, group, bh[i])) { 848 err = -EIO; 849 goto out; 850 } 851 } 852 853 first_block = page->index * blocks_per_page; 854 for (i = 0; i < blocks_per_page; i++) { 855 int group; 856 857 group = (first_block + i) >> 1; 858 if (group >= ngroups) 859 break; 860 861 if (!bh[group - first_group]) 862 /* skip initialized uptodate buddy */ 863 continue; 864 865 /* 866 * data carry information regarding this 867 * particular group in the format specified 868 * above 869 * 870 */ 871 data = page_address(page) + (i * blocksize); 872 bitmap = bh[group - first_group]->b_data; 873 874 /* 875 * We place the buddy block and bitmap block 876 * close together 877 */ 878 if ((first_block + i) & 1) { 879 /* this is block of buddy */ 880 BUG_ON(incore == NULL); 881 mb_debug(1, "put buddy for group %u in page %lu/%x\n", 882 group, page->index, i * blocksize); 883 trace_ext4_mb_buddy_bitmap_load(sb, group); 884 grinfo = ext4_get_group_info(sb, group); 885 grinfo->bb_fragments = 0; 886 memset(grinfo->bb_counters, 0, 887 sizeof(*grinfo->bb_counters) * 888 (sb->s_blocksize_bits+2)); 889 /* 890 * incore got set to the group block bitmap below 891 */ 892 ext4_lock_group(sb, group); 893 /* init the buddy */ 894 memset(data, 0xff, blocksize); 895 ext4_mb_generate_buddy(sb, data, incore, group); 896 ext4_unlock_group(sb, group); 897 incore = NULL; 898 } else { 899 /* this is block of bitmap */ 900 BUG_ON(incore != NULL); 901 mb_debug(1, "put bitmap for group %u in page %lu/%x\n", 902 group, page->index, i * blocksize); 903 trace_ext4_mb_bitmap_load(sb, group); 904 905 /* see comments in ext4_mb_put_pa() */ 906 ext4_lock_group(sb, group); 907 memcpy(data, bitmap, blocksize); 908 909 /* mark all preallocated blks used in in-core bitmap */ 910 ext4_mb_generate_from_pa(sb, data, group); 911 ext4_mb_generate_from_freelist(sb, data, group); 912 ext4_unlock_group(sb, group); 913 914 /* set incore so that the buddy information can be 915 * generated using this 916 */ 917 incore = data; 918 } 919 } 920 SetPageUptodate(page); 921 922 out: 923 if (bh) { 924 for (i = 0; i < groups_per_page; i++) 925 brelse(bh[i]); 926 if (bh != &bhs) 927 kfree(bh); 928 } 929 return err; 930 } 931 932 /* 933 * Lock the buddy and bitmap pages. This make sure other parallel init_group 934 * on the same buddy page doesn't happen whild holding the buddy page lock. 935 * Return locked buddy and bitmap pages on e4b struct. If buddy and bitmap 936 * are on the same page e4b->bd_buddy_page is NULL and return value is 0. 937 */ 938 static int ext4_mb_get_buddy_page_lock(struct super_block *sb, 939 ext4_group_t group, struct ext4_buddy *e4b) 940 { 941 struct inode *inode = EXT4_SB(sb)->s_buddy_cache; 942 int block, pnum, poff; 943 int blocks_per_page; 944 struct page *page; 945 946 e4b->bd_buddy_page = NULL; 947 e4b->bd_bitmap_page = NULL; 948 949 blocks_per_page = PAGE_CACHE_SIZE / sb->s_blocksize; 950 /* 951 * the buddy cache inode stores the block bitmap 952 * and buddy information in consecutive blocks. 953 * So for each group we need two blocks. 954 */ 955 block = group * 2; 956 pnum = block / blocks_per_page; 957 poff = block % blocks_per_page; 958 page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS); 959 if (!page) 960 return -EIO; 961 BUG_ON(page->mapping != inode->i_mapping); 962 e4b->bd_bitmap_page = page; 963 e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize); 964 965 if (blocks_per_page >= 2) { 966 /* buddy and bitmap are on the same page */ 967 return 0; 968 } 969 970 block++; 971 pnum = block / blocks_per_page; 972 poff = block % blocks_per_page; 973 page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS); 974 if (!page) 975 return -EIO; 976 BUG_ON(page->mapping != inode->i_mapping); 977 e4b->bd_buddy_page = page; 978 return 0; 979 } 980 981 static void ext4_mb_put_buddy_page_lock(struct ext4_buddy *e4b) 982 { 983 if (e4b->bd_bitmap_page) { 984 unlock_page(e4b->bd_bitmap_page); 985 page_cache_release(e4b->bd_bitmap_page); 986 } 987 if (e4b->bd_buddy_page) { 988 unlock_page(e4b->bd_buddy_page); 989 page_cache_release(e4b->bd_buddy_page); 990 } 991 } 992 993 /* 994 * Locking note: This routine calls ext4_mb_init_cache(), which takes the 995 * block group lock of all groups for this page; do not hold the BG lock when 996 * calling this routine! 997 */ 998 static noinline_for_stack 999 int ext4_mb_init_group(struct super_block *sb, ext4_group_t group) 1000 { 1001 1002 struct ext4_group_info *this_grp; 1003 struct ext4_buddy e4b; 1004 struct page *page; 1005 int ret = 0; 1006 1007 mb_debug(1, "init group %u\n", group); 1008 this_grp = ext4_get_group_info(sb, group); 1009 /* 1010 * This ensures that we don't reinit the buddy cache 1011 * page which map to the group from which we are already 1012 * allocating. If we are looking at the buddy cache we would 1013 * have taken a reference using ext4_mb_load_buddy and that 1014 * would have pinned buddy page to page cache. 1015 */ 1016 ret = ext4_mb_get_buddy_page_lock(sb, group, &e4b); 1017 if (ret || !EXT4_MB_GRP_NEED_INIT(this_grp)) { 1018 /* 1019 * somebody initialized the group 1020 * return without doing anything 1021 */ 1022 goto err; 1023 } 1024 1025 page = e4b.bd_bitmap_page; 1026 ret = ext4_mb_init_cache(page, NULL); 1027 if (ret) 1028 goto err; 1029 if (!PageUptodate(page)) { 1030 ret = -EIO; 1031 goto err; 1032 } 1033 mark_page_accessed(page); 1034 1035 if (e4b.bd_buddy_page == NULL) { 1036 /* 1037 * If both the bitmap and buddy are in 1038 * the same page we don't need to force 1039 * init the buddy 1040 */ 1041 ret = 0; 1042 goto err; 1043 } 1044 /* init buddy cache */ 1045 page = e4b.bd_buddy_page; 1046 ret = ext4_mb_init_cache(page, e4b.bd_bitmap); 1047 if (ret) 1048 goto err; 1049 if (!PageUptodate(page)) { 1050 ret = -EIO; 1051 goto err; 1052 } 1053 mark_page_accessed(page); 1054 err: 1055 ext4_mb_put_buddy_page_lock(&e4b); 1056 return ret; 1057 } 1058 1059 /* 1060 * Locking note: This routine calls ext4_mb_init_cache(), which takes the 1061 * block group lock of all groups for this page; do not hold the BG lock when 1062 * calling this routine! 1063 */ 1064 static noinline_for_stack int 1065 ext4_mb_load_buddy(struct super_block *sb, ext4_group_t group, 1066 struct ext4_buddy *e4b) 1067 { 1068 int blocks_per_page; 1069 int block; 1070 int pnum; 1071 int poff; 1072 struct page *page; 1073 int ret; 1074 struct ext4_group_info *grp; 1075 struct ext4_sb_info *sbi = EXT4_SB(sb); 1076 struct inode *inode = sbi->s_buddy_cache; 1077 1078 mb_debug(1, "load group %u\n", group); 1079 1080 blocks_per_page = PAGE_CACHE_SIZE / sb->s_blocksize; 1081 grp = ext4_get_group_info(sb, group); 1082 1083 e4b->bd_blkbits = sb->s_blocksize_bits; 1084 e4b->bd_info = grp; 1085 e4b->bd_sb = sb; 1086 e4b->bd_group = group; 1087 e4b->bd_buddy_page = NULL; 1088 e4b->bd_bitmap_page = NULL; 1089 1090 if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) { 1091 /* 1092 * we need full data about the group 1093 * to make a good selection 1094 */ 1095 ret = ext4_mb_init_group(sb, group); 1096 if (ret) 1097 return ret; 1098 } 1099 1100 /* 1101 * the buddy cache inode stores the block bitmap 1102 * and buddy information in consecutive blocks. 1103 * So for each group we need two blocks. 1104 */ 1105 block = group * 2; 1106 pnum = block / blocks_per_page; 1107 poff = block % blocks_per_page; 1108 1109 /* we could use find_or_create_page(), but it locks page 1110 * what we'd like to avoid in fast path ... */ 1111 page = find_get_page(inode->i_mapping, pnum); 1112 if (page == NULL || !PageUptodate(page)) { 1113 if (page) 1114 /* 1115 * drop the page reference and try 1116 * to get the page with lock. If we 1117 * are not uptodate that implies 1118 * somebody just created the page but 1119 * is yet to initialize the same. So 1120 * wait for it to initialize. 1121 */ 1122 page_cache_release(page); 1123 page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS); 1124 if (page) { 1125 BUG_ON(page->mapping != inode->i_mapping); 1126 if (!PageUptodate(page)) { 1127 ret = ext4_mb_init_cache(page, NULL); 1128 if (ret) { 1129 unlock_page(page); 1130 goto err; 1131 } 1132 mb_cmp_bitmaps(e4b, page_address(page) + 1133 (poff * sb->s_blocksize)); 1134 } 1135 unlock_page(page); 1136 } 1137 } 1138 if (page == NULL || !PageUptodate(page)) { 1139 ret = -EIO; 1140 goto err; 1141 } 1142 e4b->bd_bitmap_page = page; 1143 e4b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize); 1144 mark_page_accessed(page); 1145 1146 block++; 1147 pnum = block / blocks_per_page; 1148 poff = block % blocks_per_page; 1149 1150 page = find_get_page(inode->i_mapping, pnum); 1151 if (page == NULL || !PageUptodate(page)) { 1152 if (page) 1153 page_cache_release(page); 1154 page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS); 1155 if (page) { 1156 BUG_ON(page->mapping != inode->i_mapping); 1157 if (!PageUptodate(page)) { 1158 ret = ext4_mb_init_cache(page, e4b->bd_bitmap); 1159 if (ret) { 1160 unlock_page(page); 1161 goto err; 1162 } 1163 } 1164 unlock_page(page); 1165 } 1166 } 1167 if (page == NULL || !PageUptodate(page)) { 1168 ret = -EIO; 1169 goto err; 1170 } 1171 e4b->bd_buddy_page = page; 1172 e4b->bd_buddy = page_address(page) + (poff * sb->s_blocksize); 1173 mark_page_accessed(page); 1174 1175 BUG_ON(e4b->bd_bitmap_page == NULL); 1176 BUG_ON(e4b->bd_buddy_page == NULL); 1177 1178 return 0; 1179 1180 err: 1181 if (page) 1182 page_cache_release(page); 1183 if (e4b->bd_bitmap_page) 1184 page_cache_release(e4b->bd_bitmap_page); 1185 if (e4b->bd_buddy_page) 1186 page_cache_release(e4b->bd_buddy_page); 1187 e4b->bd_buddy = NULL; 1188 e4b->bd_bitmap = NULL; 1189 return ret; 1190 } 1191 1192 static void ext4_mb_unload_buddy(struct ext4_buddy *e4b) 1193 { 1194 if (e4b->bd_bitmap_page) 1195 page_cache_release(e4b->bd_bitmap_page); 1196 if (e4b->bd_buddy_page) 1197 page_cache_release(e4b->bd_buddy_page); 1198 } 1199 1200 1201 static int mb_find_order_for_block(struct ext4_buddy *e4b, int block) 1202 { 1203 int order = 1; 1204 void *bb; 1205 1206 BUG_ON(e4b->bd_bitmap == e4b->bd_buddy); 1207 BUG_ON(block >= (1 << (e4b->bd_blkbits + 3))); 1208 1209 bb = e4b->bd_buddy; 1210 while (order <= e4b->bd_blkbits + 1) { 1211 block = block >> 1; 1212 if (!mb_test_bit(block, bb)) { 1213 /* this block is part of buddy of order 'order' */ 1214 return order; 1215 } 1216 bb += 1 << (e4b->bd_blkbits - order); 1217 order++; 1218 } 1219 return 0; 1220 } 1221 1222 static void mb_clear_bits(void *bm, int cur, int len) 1223 { 1224 __u32 *addr; 1225 1226 len = cur + len; 1227 while (cur < len) { 1228 if ((cur & 31) == 0 && (len - cur) >= 32) { 1229 /* fast path: clear whole word at once */ 1230 addr = bm + (cur >> 3); 1231 *addr = 0; 1232 cur += 32; 1233 continue; 1234 } 1235 mb_clear_bit(cur, bm); 1236 cur++; 1237 } 1238 } 1239 1240 void ext4_set_bits(void *bm, int cur, int len) 1241 { 1242 __u32 *addr; 1243 1244 len = cur + len; 1245 while (cur < len) { 1246 if ((cur & 31) == 0 && (len - cur) >= 32) { 1247 /* fast path: set whole word at once */ 1248 addr = bm + (cur >> 3); 1249 *addr = 0xffffffff; 1250 cur += 32; 1251 continue; 1252 } 1253 mb_set_bit(cur, bm); 1254 cur++; 1255 } 1256 } 1257 1258 static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b, 1259 int first, int count) 1260 { 1261 int block = 0; 1262 int max = 0; 1263 int order; 1264 void *buddy; 1265 void *buddy2; 1266 struct super_block *sb = e4b->bd_sb; 1267 1268 BUG_ON(first + count > (sb->s_blocksize << 3)); 1269 assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group)); 1270 mb_check_buddy(e4b); 1271 mb_free_blocks_double(inode, e4b, first, count); 1272 1273 e4b->bd_info->bb_free += count; 1274 if (first < e4b->bd_info->bb_first_free) 1275 e4b->bd_info->bb_first_free = first; 1276 1277 /* let's maintain fragments counter */ 1278 if (first != 0) 1279 block = !mb_test_bit(first - 1, e4b->bd_bitmap); 1280 if (first + count < EXT4_SB(sb)->s_mb_maxs[0]) 1281 max = !mb_test_bit(first + count, e4b->bd_bitmap); 1282 if (block && max) 1283 e4b->bd_info->bb_fragments--; 1284 else if (!block && !max) 1285 e4b->bd_info->bb_fragments++; 1286 1287 /* let's maintain buddy itself */ 1288 while (count-- > 0) { 1289 block = first++; 1290 order = 0; 1291 1292 if (!mb_test_bit(block, e4b->bd_bitmap)) { 1293 ext4_fsblk_t blocknr; 1294 1295 blocknr = ext4_group_first_block_no(sb, e4b->bd_group); 1296 blocknr += EXT4_C2B(EXT4_SB(sb), block); 1297 ext4_grp_locked_error(sb, e4b->bd_group, 1298 inode ? inode->i_ino : 0, 1299 blocknr, 1300 "freeing already freed block " 1301 "(bit %u)", block); 1302 } 1303 mb_clear_bit(block, e4b->bd_bitmap); 1304 e4b->bd_info->bb_counters[order]++; 1305 1306 /* start of the buddy */ 1307 buddy = mb_find_buddy(e4b, order, &max); 1308 1309 do { 1310 block &= ~1UL; 1311 if (mb_test_bit(block, buddy) || 1312 mb_test_bit(block + 1, buddy)) 1313 break; 1314 1315 /* both the buddies are free, try to coalesce them */ 1316 buddy2 = mb_find_buddy(e4b, order + 1, &max); 1317 1318 if (!buddy2) 1319 break; 1320 1321 if (order > 0) { 1322 /* for special purposes, we don't set 1323 * free bits in bitmap */ 1324 mb_set_bit(block, buddy); 1325 mb_set_bit(block + 1, buddy); 1326 } 1327 e4b->bd_info->bb_counters[order]--; 1328 e4b->bd_info->bb_counters[order]--; 1329 1330 block = block >> 1; 1331 order++; 1332 e4b->bd_info->bb_counters[order]++; 1333 1334 mb_clear_bit(block, buddy2); 1335 buddy = buddy2; 1336 } while (1); 1337 } 1338 mb_set_largest_free_order(sb, e4b->bd_info); 1339 mb_check_buddy(e4b); 1340 } 1341 1342 static int mb_find_extent(struct ext4_buddy *e4b, int order, int block, 1343 int needed, struct ext4_free_extent *ex) 1344 { 1345 int next = block; 1346 int max; 1347 void *buddy; 1348 1349 assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group)); 1350 BUG_ON(ex == NULL); 1351 1352 buddy = mb_find_buddy(e4b, order, &max); 1353 BUG_ON(buddy == NULL); 1354 BUG_ON(block >= max); 1355 if (mb_test_bit(block, buddy)) { 1356 ex->fe_len = 0; 1357 ex->fe_start = 0; 1358 ex->fe_group = 0; 1359 return 0; 1360 } 1361 1362 /* FIXME dorp order completely ? */ 1363 if (likely(order == 0)) { 1364 /* find actual order */ 1365 order = mb_find_order_for_block(e4b, block); 1366 block = block >> order; 1367 } 1368 1369 ex->fe_len = 1 << order; 1370 ex->fe_start = block << order; 1371 ex->fe_group = e4b->bd_group; 1372 1373 /* calc difference from given start */ 1374 next = next - ex->fe_start; 1375 ex->fe_len -= next; 1376 ex->fe_start += next; 1377 1378 while (needed > ex->fe_len && 1379 (buddy = mb_find_buddy(e4b, order, &max))) { 1380 1381 if (block + 1 >= max) 1382 break; 1383 1384 next = (block + 1) * (1 << order); 1385 if (mb_test_bit(next, e4b->bd_bitmap)) 1386 break; 1387 1388 order = mb_find_order_for_block(e4b, next); 1389 1390 block = next >> order; 1391 ex->fe_len += 1 << order; 1392 } 1393 1394 BUG_ON(ex->fe_start + ex->fe_len > (1 << (e4b->bd_blkbits + 3))); 1395 return ex->fe_len; 1396 } 1397 1398 static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex) 1399 { 1400 int ord; 1401 int mlen = 0; 1402 int max = 0; 1403 int cur; 1404 int start = ex->fe_start; 1405 int len = ex->fe_len; 1406 unsigned ret = 0; 1407 int len0 = len; 1408 void *buddy; 1409 1410 BUG_ON(start + len > (e4b->bd_sb->s_blocksize << 3)); 1411 BUG_ON(e4b->bd_group != ex->fe_group); 1412 assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group)); 1413 mb_check_buddy(e4b); 1414 mb_mark_used_double(e4b, start, len); 1415 1416 e4b->bd_info->bb_free -= len; 1417 if (e4b->bd_info->bb_first_free == start) 1418 e4b->bd_info->bb_first_free += len; 1419 1420 /* let's maintain fragments counter */ 1421 if (start != 0) 1422 mlen = !mb_test_bit(start - 1, e4b->bd_bitmap); 1423 if (start + len < EXT4_SB(e4b->bd_sb)->s_mb_maxs[0]) 1424 max = !mb_test_bit(start + len, e4b->bd_bitmap); 1425 if (mlen && max) 1426 e4b->bd_info->bb_fragments++; 1427 else if (!mlen && !max) 1428 e4b->bd_info->bb_fragments--; 1429 1430 /* let's maintain buddy itself */ 1431 while (len) { 1432 ord = mb_find_order_for_block(e4b, start); 1433 1434 if (((start >> ord) << ord) == start && len >= (1 << ord)) { 1435 /* the whole chunk may be allocated at once! */ 1436 mlen = 1 << ord; 1437 buddy = mb_find_buddy(e4b, ord, &max); 1438 BUG_ON((start >> ord) >= max); 1439 mb_set_bit(start >> ord, buddy); 1440 e4b->bd_info->bb_counters[ord]--; 1441 start += mlen; 1442 len -= mlen; 1443 BUG_ON(len < 0); 1444 continue; 1445 } 1446 1447 /* store for history */ 1448 if (ret == 0) 1449 ret = len | (ord << 16); 1450 1451 /* we have to split large buddy */ 1452 BUG_ON(ord <= 0); 1453 buddy = mb_find_buddy(e4b, ord, &max); 1454 mb_set_bit(start >> ord, buddy); 1455 e4b->bd_info->bb_counters[ord]--; 1456 1457 ord--; 1458 cur = (start >> ord) & ~1U; 1459 buddy = mb_find_buddy(e4b, ord, &max); 1460 mb_clear_bit(cur, buddy); 1461 mb_clear_bit(cur + 1, buddy); 1462 e4b->bd_info->bb_counters[ord]++; 1463 e4b->bd_info->bb_counters[ord]++; 1464 } 1465 mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info); 1466 1467 ext4_set_bits(e4b->bd_bitmap, ex->fe_start, len0); 1468 mb_check_buddy(e4b); 1469 1470 return ret; 1471 } 1472 1473 /* 1474 * Must be called under group lock! 1475 */ 1476 static void ext4_mb_use_best_found(struct ext4_allocation_context *ac, 1477 struct ext4_buddy *e4b) 1478 { 1479 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb); 1480 int ret; 1481 1482 BUG_ON(ac->ac_b_ex.fe_group != e4b->bd_group); 1483 BUG_ON(ac->ac_status == AC_STATUS_FOUND); 1484 1485 ac->ac_b_ex.fe_len = min(ac->ac_b_ex.fe_len, ac->ac_g_ex.fe_len); 1486 ac->ac_b_ex.fe_logical = ac->ac_g_ex.fe_logical; 1487 ret = mb_mark_used(e4b, &ac->ac_b_ex); 1488 1489 /* preallocation can change ac_b_ex, thus we store actually 1490 * allocated blocks for history */ 1491 ac->ac_f_ex = ac->ac_b_ex; 1492 1493 ac->ac_status = AC_STATUS_FOUND; 1494 ac->ac_tail = ret & 0xffff; 1495 ac->ac_buddy = ret >> 16; 1496 1497 /* 1498 * take the page reference. We want the page to be pinned 1499 * so that we don't get a ext4_mb_init_cache_call for this 1500 * group until we update the bitmap. That would mean we 1501 * double allocate blocks. The reference is dropped 1502 * in ext4_mb_release_context 1503 */ 1504 ac->ac_bitmap_page = e4b->bd_bitmap_page; 1505 get_page(ac->ac_bitmap_page); 1506 ac->ac_buddy_page = e4b->bd_buddy_page; 1507 get_page(ac->ac_buddy_page); 1508 /* store last allocated for subsequent stream allocation */ 1509 if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) { 1510 spin_lock(&sbi->s_md_lock); 1511 sbi->s_mb_last_group = ac->ac_f_ex.fe_group; 1512 sbi->s_mb_last_start = ac->ac_f_ex.fe_start; 1513 spin_unlock(&sbi->s_md_lock); 1514 } 1515 } 1516 1517 /* 1518 * regular allocator, for general purposes allocation 1519 */ 1520 1521 static void ext4_mb_check_limits(struct ext4_allocation_context *ac, 1522 struct ext4_buddy *e4b, 1523 int finish_group) 1524 { 1525 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb); 1526 struct ext4_free_extent *bex = &ac->ac_b_ex; 1527 struct ext4_free_extent *gex = &ac->ac_g_ex; 1528 struct ext4_free_extent ex; 1529 int max; 1530 1531 if (ac->ac_status == AC_STATUS_FOUND) 1532 return; 1533 /* 1534 * We don't want to scan for a whole year 1535 */ 1536 if (ac->ac_found > sbi->s_mb_max_to_scan && 1537 !(ac->ac_flags & EXT4_MB_HINT_FIRST)) { 1538 ac->ac_status = AC_STATUS_BREAK; 1539 return; 1540 } 1541 1542 /* 1543 * Haven't found good chunk so far, let's continue 1544 */ 1545 if (bex->fe_len < gex->fe_len) 1546 return; 1547 1548 if ((finish_group || ac->ac_found > sbi->s_mb_min_to_scan) 1549 && bex->fe_group == e4b->bd_group) { 1550 /* recheck chunk's availability - we don't know 1551 * when it was found (within this lock-unlock 1552 * period or not) */ 1553 max = mb_find_extent(e4b, 0, bex->fe_start, gex->fe_len, &ex); 1554 if (max >= gex->fe_len) { 1555 ext4_mb_use_best_found(ac, e4b); 1556 return; 1557 } 1558 } 1559 } 1560 1561 /* 1562 * The routine checks whether found extent is good enough. If it is, 1563 * then the extent gets marked used and flag is set to the context 1564 * to stop scanning. Otherwise, the extent is compared with the 1565 * previous found extent and if new one is better, then it's stored 1566 * in the context. Later, the best found extent will be used, if 1567 * mballoc can't find good enough extent. 1568 * 1569 * FIXME: real allocation policy is to be designed yet! 1570 */ 1571 static void ext4_mb_measure_extent(struct ext4_allocation_context *ac, 1572 struct ext4_free_extent *ex, 1573 struct ext4_buddy *e4b) 1574 { 1575 struct ext4_free_extent *bex = &ac->ac_b_ex; 1576 struct ext4_free_extent *gex = &ac->ac_g_ex; 1577 1578 BUG_ON(ex->fe_len <= 0); 1579 BUG_ON(ex->fe_len > EXT4_CLUSTERS_PER_GROUP(ac->ac_sb)); 1580 BUG_ON(ex->fe_start >= EXT4_CLUSTERS_PER_GROUP(ac->ac_sb)); 1581 BUG_ON(ac->ac_status != AC_STATUS_CONTINUE); 1582 1583 ac->ac_found++; 1584 1585 /* 1586 * The special case - take what you catch first 1587 */ 1588 if (unlikely(ac->ac_flags & EXT4_MB_HINT_FIRST)) { 1589 *bex = *ex; 1590 ext4_mb_use_best_found(ac, e4b); 1591 return; 1592 } 1593 1594 /* 1595 * Let's check whether the chuck is good enough 1596 */ 1597 if (ex->fe_len == gex->fe_len) { 1598 *bex = *ex; 1599 ext4_mb_use_best_found(ac, e4b); 1600 return; 1601 } 1602 1603 /* 1604 * If this is first found extent, just store it in the context 1605 */ 1606 if (bex->fe_len == 0) { 1607 *bex = *ex; 1608 return; 1609 } 1610 1611 /* 1612 * If new found extent is better, store it in the context 1613 */ 1614 if (bex->fe_len < gex->fe_len) { 1615 /* if the request isn't satisfied, any found extent 1616 * larger than previous best one is better */ 1617 if (ex->fe_len > bex->fe_len) 1618 *bex = *ex; 1619 } else if (ex->fe_len > gex->fe_len) { 1620 /* if the request is satisfied, then we try to find 1621 * an extent that still satisfy the request, but is 1622 * smaller than previous one */ 1623 if (ex->fe_len < bex->fe_len) 1624 *bex = *ex; 1625 } 1626 1627 ext4_mb_check_limits(ac, e4b, 0); 1628 } 1629 1630 static noinline_for_stack 1631 int ext4_mb_try_best_found(struct ext4_allocation_context *ac, 1632 struct ext4_buddy *e4b) 1633 { 1634 struct ext4_free_extent ex = ac->ac_b_ex; 1635 ext4_group_t group = ex.fe_group; 1636 int max; 1637 int err; 1638 1639 BUG_ON(ex.fe_len <= 0); 1640 err = ext4_mb_load_buddy(ac->ac_sb, group, e4b); 1641 if (err) 1642 return err; 1643 1644 ext4_lock_group(ac->ac_sb, group); 1645 max = mb_find_extent(e4b, 0, ex.fe_start, ex.fe_len, &ex); 1646 1647 if (max > 0) { 1648 ac->ac_b_ex = ex; 1649 ext4_mb_use_best_found(ac, e4b); 1650 } 1651 1652 ext4_unlock_group(ac->ac_sb, group); 1653 ext4_mb_unload_buddy(e4b); 1654 1655 return 0; 1656 } 1657 1658 static noinline_for_stack 1659 int ext4_mb_find_by_goal(struct ext4_allocation_context *ac, 1660 struct ext4_buddy *e4b) 1661 { 1662 ext4_group_t group = ac->ac_g_ex.fe_group; 1663 int max; 1664 int err; 1665 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb); 1666 struct ext4_free_extent ex; 1667 1668 if (!(ac->ac_flags & EXT4_MB_HINT_TRY_GOAL)) 1669 return 0; 1670 1671 err = ext4_mb_load_buddy(ac->ac_sb, group, e4b); 1672 if (err) 1673 return err; 1674 1675 ext4_lock_group(ac->ac_sb, group); 1676 max = mb_find_extent(e4b, 0, ac->ac_g_ex.fe_start, 1677 ac->ac_g_ex.fe_len, &ex); 1678 1679 if (max >= ac->ac_g_ex.fe_len && ac->ac_g_ex.fe_len == sbi->s_stripe) { 1680 ext4_fsblk_t start; 1681 1682 start = ext4_group_first_block_no(ac->ac_sb, e4b->bd_group) + 1683 ex.fe_start; 1684 /* use do_div to get remainder (would be 64-bit modulo) */ 1685 if (do_div(start, sbi->s_stripe) == 0) { 1686 ac->ac_found++; 1687 ac->ac_b_ex = ex; 1688 ext4_mb_use_best_found(ac, e4b); 1689 } 1690 } else if (max >= ac->ac_g_ex.fe_len) { 1691 BUG_ON(ex.fe_len <= 0); 1692 BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group); 1693 BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start); 1694 ac->ac_found++; 1695 ac->ac_b_ex = ex; 1696 ext4_mb_use_best_found(ac, e4b); 1697 } else if (max > 0 && (ac->ac_flags & EXT4_MB_HINT_MERGE)) { 1698 /* Sometimes, caller may want to merge even small 1699 * number of blocks to an existing extent */ 1700 BUG_ON(ex.fe_len <= 0); 1701 BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group); 1702 BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start); 1703 ac->ac_found++; 1704 ac->ac_b_ex = ex; 1705 ext4_mb_use_best_found(ac, e4b); 1706 } 1707 ext4_unlock_group(ac->ac_sb, group); 1708 ext4_mb_unload_buddy(e4b); 1709 1710 return 0; 1711 } 1712 1713 /* 1714 * The routine scans buddy structures (not bitmap!) from given order 1715 * to max order and tries to find big enough chunk to satisfy the req 1716 */ 1717 static noinline_for_stack 1718 void ext4_mb_simple_scan_group(struct ext4_allocation_context *ac, 1719 struct ext4_buddy *e4b) 1720 { 1721 struct super_block *sb = ac->ac_sb; 1722 struct ext4_group_info *grp = e4b->bd_info; 1723 void *buddy; 1724 int i; 1725 int k; 1726 int max; 1727 1728 BUG_ON(ac->ac_2order <= 0); 1729 for (i = ac->ac_2order; i <= sb->s_blocksize_bits + 1; i++) { 1730 if (grp->bb_counters[i] == 0) 1731 continue; 1732 1733 buddy = mb_find_buddy(e4b, i, &max); 1734 BUG_ON(buddy == NULL); 1735 1736 k = mb_find_next_zero_bit(buddy, max, 0); 1737 BUG_ON(k >= max); 1738 1739 ac->ac_found++; 1740 1741 ac->ac_b_ex.fe_len = 1 << i; 1742 ac->ac_b_ex.fe_start = k << i; 1743 ac->ac_b_ex.fe_group = e4b->bd_group; 1744 1745 ext4_mb_use_best_found(ac, e4b); 1746 1747 BUG_ON(ac->ac_b_ex.fe_len != ac->ac_g_ex.fe_len); 1748 1749 if (EXT4_SB(sb)->s_mb_stats) 1750 atomic_inc(&EXT4_SB(sb)->s_bal_2orders); 1751 1752 break; 1753 } 1754 } 1755 1756 /* 1757 * The routine scans the group and measures all found extents. 1758 * In order to optimize scanning, caller must pass number of 1759 * free blocks in the group, so the routine can know upper limit. 1760 */ 1761 static noinline_for_stack 1762 void ext4_mb_complex_scan_group(struct ext4_allocation_context *ac, 1763 struct ext4_buddy *e4b) 1764 { 1765 struct super_block *sb = ac->ac_sb; 1766 void *bitmap = e4b->bd_bitmap; 1767 struct ext4_free_extent ex; 1768 int i; 1769 int free; 1770 1771 free = e4b->bd_info->bb_free; 1772 BUG_ON(free <= 0); 1773 1774 i = e4b->bd_info->bb_first_free; 1775 1776 while (free && ac->ac_status == AC_STATUS_CONTINUE) { 1777 i = mb_find_next_zero_bit(bitmap, 1778 EXT4_CLUSTERS_PER_GROUP(sb), i); 1779 if (i >= EXT4_CLUSTERS_PER_GROUP(sb)) { 1780 /* 1781 * IF we have corrupt bitmap, we won't find any 1782 * free blocks even though group info says we 1783 * we have free blocks 1784 */ 1785 ext4_grp_locked_error(sb, e4b->bd_group, 0, 0, 1786 "%d free clusters as per " 1787 "group info. But bitmap says 0", 1788 free); 1789 break; 1790 } 1791 1792 mb_find_extent(e4b, 0, i, ac->ac_g_ex.fe_len, &ex); 1793 BUG_ON(ex.fe_len <= 0); 1794 if (free < ex.fe_len) { 1795 ext4_grp_locked_error(sb, e4b->bd_group, 0, 0, 1796 "%d free clusters as per " 1797 "group info. But got %d blocks", 1798 free, ex.fe_len); 1799 /* 1800 * The number of free blocks differs. This mostly 1801 * indicate that the bitmap is corrupt. So exit 1802 * without claiming the space. 1803 */ 1804 break; 1805 } 1806 1807 ext4_mb_measure_extent(ac, &ex, e4b); 1808 1809 i += ex.fe_len; 1810 free -= ex.fe_len; 1811 } 1812 1813 ext4_mb_check_limits(ac, e4b, 1); 1814 } 1815 1816 /* 1817 * This is a special case for storages like raid5 1818 * we try to find stripe-aligned chunks for stripe-size-multiple requests 1819 */ 1820 static noinline_for_stack 1821 void ext4_mb_scan_aligned(struct ext4_allocation_context *ac, 1822 struct ext4_buddy *e4b) 1823 { 1824 struct super_block *sb = ac->ac_sb; 1825 struct ext4_sb_info *sbi = EXT4_SB(sb); 1826 void *bitmap = e4b->bd_bitmap; 1827 struct ext4_free_extent ex; 1828 ext4_fsblk_t first_group_block; 1829 ext4_fsblk_t a; 1830 ext4_grpblk_t i; 1831 int max; 1832 1833 BUG_ON(sbi->s_stripe == 0); 1834 1835 /* find first stripe-aligned block in group */ 1836 first_group_block = ext4_group_first_block_no(sb, e4b->bd_group); 1837 1838 a = first_group_block + sbi->s_stripe - 1; 1839 do_div(a, sbi->s_stripe); 1840 i = (a * sbi->s_stripe) - first_group_block; 1841 1842 while (i < EXT4_CLUSTERS_PER_GROUP(sb)) { 1843 if (!mb_test_bit(i, bitmap)) { 1844 max = mb_find_extent(e4b, 0, i, sbi->s_stripe, &ex); 1845 if (max >= sbi->s_stripe) { 1846 ac->ac_found++; 1847 ac->ac_b_ex = ex; 1848 ext4_mb_use_best_found(ac, e4b); 1849 break; 1850 } 1851 } 1852 i += sbi->s_stripe; 1853 } 1854 } 1855 1856 /* This is now called BEFORE we load the buddy bitmap. */ 1857 static int ext4_mb_good_group(struct ext4_allocation_context *ac, 1858 ext4_group_t group, int cr) 1859 { 1860 unsigned free, fragments; 1861 int flex_size = ext4_flex_bg_size(EXT4_SB(ac->ac_sb)); 1862 struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group); 1863 1864 BUG_ON(cr < 0 || cr >= 4); 1865 1866 /* We only do this if the grp has never been initialized */ 1867 if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) { 1868 int ret = ext4_mb_init_group(ac->ac_sb, group); 1869 if (ret) 1870 return 0; 1871 } 1872 1873 free = grp->bb_free; 1874 fragments = grp->bb_fragments; 1875 if (free == 0) 1876 return 0; 1877 if (fragments == 0) 1878 return 0; 1879 1880 switch (cr) { 1881 case 0: 1882 BUG_ON(ac->ac_2order == 0); 1883 1884 if (grp->bb_largest_free_order < ac->ac_2order) 1885 return 0; 1886 1887 /* Avoid using the first bg of a flexgroup for data files */ 1888 if ((ac->ac_flags & EXT4_MB_HINT_DATA) && 1889 (flex_size >= EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME) && 1890 ((group % flex_size) == 0)) 1891 return 0; 1892 1893 return 1; 1894 case 1: 1895 if ((free / fragments) >= ac->ac_g_ex.fe_len) 1896 return 1; 1897 break; 1898 case 2: 1899 if (free >= ac->ac_g_ex.fe_len) 1900 return 1; 1901 break; 1902 case 3: 1903 return 1; 1904 default: 1905 BUG(); 1906 } 1907 1908 return 0; 1909 } 1910 1911 static noinline_for_stack int 1912 ext4_mb_regular_allocator(struct ext4_allocation_context *ac) 1913 { 1914 ext4_group_t ngroups, group, i; 1915 int cr; 1916 int err = 0; 1917 struct ext4_sb_info *sbi; 1918 struct super_block *sb; 1919 struct ext4_buddy e4b; 1920 1921 sb = ac->ac_sb; 1922 sbi = EXT4_SB(sb); 1923 ngroups = ext4_get_groups_count(sb); 1924 /* non-extent files are limited to low blocks/groups */ 1925 if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS))) 1926 ngroups = sbi->s_blockfile_groups; 1927 1928 BUG_ON(ac->ac_status == AC_STATUS_FOUND); 1929 1930 /* first, try the goal */ 1931 err = ext4_mb_find_by_goal(ac, &e4b); 1932 if (err || ac->ac_status == AC_STATUS_FOUND) 1933 goto out; 1934 1935 if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY)) 1936 goto out; 1937 1938 /* 1939 * ac->ac2_order is set only if the fe_len is a power of 2 1940 * if ac2_order is set we also set criteria to 0 so that we 1941 * try exact allocation using buddy. 1942 */ 1943 i = fls(ac->ac_g_ex.fe_len); 1944 ac->ac_2order = 0; 1945 /* 1946 * We search using buddy data only if the order of the request 1947 * is greater than equal to the sbi_s_mb_order2_reqs 1948 * You can tune it via /sys/fs/ext4/<partition>/mb_order2_req 1949 */ 1950 if (i >= sbi->s_mb_order2_reqs) { 1951 /* 1952 * This should tell if fe_len is exactly power of 2 1953 */ 1954 if ((ac->ac_g_ex.fe_len & (~(1 << (i - 1)))) == 0) 1955 ac->ac_2order = i - 1; 1956 } 1957 1958 /* if stream allocation is enabled, use global goal */ 1959 if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) { 1960 /* TBD: may be hot point */ 1961 spin_lock(&sbi->s_md_lock); 1962 ac->ac_g_ex.fe_group = sbi->s_mb_last_group; 1963 ac->ac_g_ex.fe_start = sbi->s_mb_last_start; 1964 spin_unlock(&sbi->s_md_lock); 1965 } 1966 1967 /* Let's just scan groups to find more-less suitable blocks */ 1968 cr = ac->ac_2order ? 0 : 1; 1969 /* 1970 * cr == 0 try to get exact allocation, 1971 * cr == 3 try to get anything 1972 */ 1973 repeat: 1974 for (; cr < 4 && ac->ac_status == AC_STATUS_CONTINUE; cr++) { 1975 ac->ac_criteria = cr; 1976 /* 1977 * searching for the right group start 1978 * from the goal value specified 1979 */ 1980 group = ac->ac_g_ex.fe_group; 1981 1982 for (i = 0; i < ngroups; group++, i++) { 1983 if (group == ngroups) 1984 group = 0; 1985 1986 /* This now checks without needing the buddy page */ 1987 if (!ext4_mb_good_group(ac, group, cr)) 1988 continue; 1989 1990 err = ext4_mb_load_buddy(sb, group, &e4b); 1991 if (err) 1992 goto out; 1993 1994 ext4_lock_group(sb, group); 1995 1996 /* 1997 * We need to check again after locking the 1998 * block group 1999 */ 2000 if (!ext4_mb_good_group(ac, group, cr)) { 2001 ext4_unlock_group(sb, group); 2002 ext4_mb_unload_buddy(&e4b); 2003 continue; 2004 } 2005 2006 ac->ac_groups_scanned++; 2007 if (cr == 0) 2008 ext4_mb_simple_scan_group(ac, &e4b); 2009 else if (cr == 1 && sbi->s_stripe && 2010 !(ac->ac_g_ex.fe_len % sbi->s_stripe)) 2011 ext4_mb_scan_aligned(ac, &e4b); 2012 else 2013 ext4_mb_complex_scan_group(ac, &e4b); 2014 2015 ext4_unlock_group(sb, group); 2016 ext4_mb_unload_buddy(&e4b); 2017 2018 if (ac->ac_status != AC_STATUS_CONTINUE) 2019 break; 2020 } 2021 } 2022 2023 if (ac->ac_b_ex.fe_len > 0 && ac->ac_status != AC_STATUS_FOUND && 2024 !(ac->ac_flags & EXT4_MB_HINT_FIRST)) { 2025 /* 2026 * We've been searching too long. Let's try to allocate 2027 * the best chunk we've found so far 2028 */ 2029 2030 ext4_mb_try_best_found(ac, &e4b); 2031 if (ac->ac_status != AC_STATUS_FOUND) { 2032 /* 2033 * Someone more lucky has already allocated it. 2034 * The only thing we can do is just take first 2035 * found block(s) 2036 printk(KERN_DEBUG "EXT4-fs: someone won our chunk\n"); 2037 */ 2038 ac->ac_b_ex.fe_group = 0; 2039 ac->ac_b_ex.fe_start = 0; 2040 ac->ac_b_ex.fe_len = 0; 2041 ac->ac_status = AC_STATUS_CONTINUE; 2042 ac->ac_flags |= EXT4_MB_HINT_FIRST; 2043 cr = 3; 2044 atomic_inc(&sbi->s_mb_lost_chunks); 2045 goto repeat; 2046 } 2047 } 2048 out: 2049 return err; 2050 } 2051 2052 static void *ext4_mb_seq_groups_start(struct seq_file *seq, loff_t *pos) 2053 { 2054 struct super_block *sb = seq->private; 2055 ext4_group_t group; 2056 2057 if (*pos < 0 || *pos >= ext4_get_groups_count(sb)) 2058 return NULL; 2059 group = *pos + 1; 2060 return (void *) ((unsigned long) group); 2061 } 2062 2063 static void *ext4_mb_seq_groups_next(struct seq_file *seq, void *v, loff_t *pos) 2064 { 2065 struct super_block *sb = seq->private; 2066 ext4_group_t group; 2067 2068 ++*pos; 2069 if (*pos < 0 || *pos >= ext4_get_groups_count(sb)) 2070 return NULL; 2071 group = *pos + 1; 2072 return (void *) ((unsigned long) group); 2073 } 2074 2075 static int ext4_mb_seq_groups_show(struct seq_file *seq, void *v) 2076 { 2077 struct super_block *sb = seq->private; 2078 ext4_group_t group = (ext4_group_t) ((unsigned long) v); 2079 int i; 2080 int err; 2081 struct ext4_buddy e4b; 2082 struct sg { 2083 struct ext4_group_info info; 2084 ext4_grpblk_t counters[16]; 2085 } sg; 2086 2087 group--; 2088 if (group == 0) 2089 seq_printf(seq, "#%-5s: %-5s %-5s %-5s " 2090 "[ %-5s %-5s %-5s %-5s %-5s %-5s %-5s " 2091 "%-5s %-5s %-5s %-5s %-5s %-5s %-5s ]\n", 2092 "group", "free", "frags", "first", 2093 "2^0", "2^1", "2^2", "2^3", "2^4", "2^5", "2^6", 2094 "2^7", "2^8", "2^9", "2^10", "2^11", "2^12", "2^13"); 2095 2096 i = (sb->s_blocksize_bits + 2) * sizeof(sg.info.bb_counters[0]) + 2097 sizeof(struct ext4_group_info); 2098 err = ext4_mb_load_buddy(sb, group, &e4b); 2099 if (err) { 2100 seq_printf(seq, "#%-5u: I/O error\n", group); 2101 return 0; 2102 } 2103 ext4_lock_group(sb, group); 2104 memcpy(&sg, ext4_get_group_info(sb, group), i); 2105 ext4_unlock_group(sb, group); 2106 ext4_mb_unload_buddy(&e4b); 2107 2108 seq_printf(seq, "#%-5u: %-5u %-5u %-5u [", group, sg.info.bb_free, 2109 sg.info.bb_fragments, sg.info.bb_first_free); 2110 for (i = 0; i <= 13; i++) 2111 seq_printf(seq, " %-5u", i <= sb->s_blocksize_bits + 1 ? 2112 sg.info.bb_counters[i] : 0); 2113 seq_printf(seq, " ]\n"); 2114 2115 return 0; 2116 } 2117 2118 static void ext4_mb_seq_groups_stop(struct seq_file *seq, void *v) 2119 { 2120 } 2121 2122 static const struct seq_operations ext4_mb_seq_groups_ops = { 2123 .start = ext4_mb_seq_groups_start, 2124 .next = ext4_mb_seq_groups_next, 2125 .stop = ext4_mb_seq_groups_stop, 2126 .show = ext4_mb_seq_groups_show, 2127 }; 2128 2129 static int ext4_mb_seq_groups_open(struct inode *inode, struct file *file) 2130 { 2131 struct super_block *sb = PDE(inode)->data; 2132 int rc; 2133 2134 rc = seq_open(file, &ext4_mb_seq_groups_ops); 2135 if (rc == 0) { 2136 struct seq_file *m = file->private_data; 2137 m->private = sb; 2138 } 2139 return rc; 2140 2141 } 2142 2143 static const struct file_operations ext4_mb_seq_groups_fops = { 2144 .owner = THIS_MODULE, 2145 .open = ext4_mb_seq_groups_open, 2146 .read = seq_read, 2147 .llseek = seq_lseek, 2148 .release = seq_release, 2149 }; 2150 2151 static struct kmem_cache *get_groupinfo_cache(int blocksize_bits) 2152 { 2153 int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE; 2154 struct kmem_cache *cachep = ext4_groupinfo_caches[cache_index]; 2155 2156 BUG_ON(!cachep); 2157 return cachep; 2158 } 2159 2160 /* Create and initialize ext4_group_info data for the given group. */ 2161 int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group, 2162 struct ext4_group_desc *desc) 2163 { 2164 int i; 2165 int metalen = 0; 2166 struct ext4_sb_info *sbi = EXT4_SB(sb); 2167 struct ext4_group_info **meta_group_info; 2168 struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits); 2169 2170 /* 2171 * First check if this group is the first of a reserved block. 2172 * If it's true, we have to allocate a new table of pointers 2173 * to ext4_group_info structures 2174 */ 2175 if (group % EXT4_DESC_PER_BLOCK(sb) == 0) { 2176 metalen = sizeof(*meta_group_info) << 2177 EXT4_DESC_PER_BLOCK_BITS(sb); 2178 meta_group_info = kmalloc(metalen, GFP_KERNEL); 2179 if (meta_group_info == NULL) { 2180 ext4_msg(sb, KERN_ERR, "can't allocate mem " 2181 "for a buddy group"); 2182 goto exit_meta_group_info; 2183 } 2184 sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)] = 2185 meta_group_info; 2186 } 2187 2188 meta_group_info = 2189 sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)]; 2190 i = group & (EXT4_DESC_PER_BLOCK(sb) - 1); 2191 2192 meta_group_info[i] = kmem_cache_alloc(cachep, GFP_KERNEL); 2193 if (meta_group_info[i] == NULL) { 2194 ext4_msg(sb, KERN_ERR, "can't allocate buddy mem"); 2195 goto exit_group_info; 2196 } 2197 memset(meta_group_info[i], 0, kmem_cache_size(cachep)); 2198 set_bit(EXT4_GROUP_INFO_NEED_INIT_BIT, 2199 &(meta_group_info[i]->bb_state)); 2200 2201 /* 2202 * initialize bb_free to be able to skip 2203 * empty groups without initialization 2204 */ 2205 if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) { 2206 meta_group_info[i]->bb_free = 2207 ext4_free_clusters_after_init(sb, group, desc); 2208 } else { 2209 meta_group_info[i]->bb_free = 2210 ext4_free_group_clusters(sb, desc); 2211 } 2212 2213 INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list); 2214 init_rwsem(&meta_group_info[i]->alloc_sem); 2215 meta_group_info[i]->bb_free_root = RB_ROOT; 2216 meta_group_info[i]->bb_largest_free_order = -1; /* uninit */ 2217 2218 #ifdef DOUBLE_CHECK 2219 { 2220 struct buffer_head *bh; 2221 meta_group_info[i]->bb_bitmap = 2222 kmalloc(sb->s_blocksize, GFP_KERNEL); 2223 BUG_ON(meta_group_info[i]->bb_bitmap == NULL); 2224 bh = ext4_read_block_bitmap(sb, group); 2225 BUG_ON(bh == NULL); 2226 memcpy(meta_group_info[i]->bb_bitmap, bh->b_data, 2227 sb->s_blocksize); 2228 put_bh(bh); 2229 } 2230 #endif 2231 2232 return 0; 2233 2234 exit_group_info: 2235 /* If a meta_group_info table has been allocated, release it now */ 2236 if (group % EXT4_DESC_PER_BLOCK(sb) == 0) { 2237 kfree(sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)]); 2238 sbi->s_group_info[group >> EXT4_DESC_PER_BLOCK_BITS(sb)] = NULL; 2239 } 2240 exit_meta_group_info: 2241 return -ENOMEM; 2242 } /* ext4_mb_add_groupinfo */ 2243 2244 static int ext4_mb_init_backend(struct super_block *sb) 2245 { 2246 ext4_group_t ngroups = ext4_get_groups_count(sb); 2247 ext4_group_t i; 2248 struct ext4_sb_info *sbi = EXT4_SB(sb); 2249 struct ext4_super_block *es = sbi->s_es; 2250 int num_meta_group_infos; 2251 int num_meta_group_infos_max; 2252 int array_size; 2253 struct ext4_group_desc *desc; 2254 struct kmem_cache *cachep; 2255 2256 /* This is the number of blocks used by GDT */ 2257 num_meta_group_infos = (ngroups + EXT4_DESC_PER_BLOCK(sb) - 2258 1) >> EXT4_DESC_PER_BLOCK_BITS(sb); 2259 2260 /* 2261 * This is the total number of blocks used by GDT including 2262 * the number of reserved blocks for GDT. 2263 * The s_group_info array is allocated with this value 2264 * to allow a clean online resize without a complex 2265 * manipulation of pointer. 2266 * The drawback is the unused memory when no resize 2267 * occurs but it's very low in terms of pages 2268 * (see comments below) 2269 * Need to handle this properly when META_BG resizing is allowed 2270 */ 2271 num_meta_group_infos_max = num_meta_group_infos + 2272 le16_to_cpu(es->s_reserved_gdt_blocks); 2273 2274 /* 2275 * array_size is the size of s_group_info array. We round it 2276 * to the next power of two because this approximation is done 2277 * internally by kmalloc so we can have some more memory 2278 * for free here (e.g. may be used for META_BG resize). 2279 */ 2280 array_size = 1; 2281 while (array_size < sizeof(*sbi->s_group_info) * 2282 num_meta_group_infos_max) 2283 array_size = array_size << 1; 2284 /* An 8TB filesystem with 64-bit pointers requires a 4096 byte 2285 * kmalloc. A 128kb malloc should suffice for a 256TB filesystem. 2286 * So a two level scheme suffices for now. */ 2287 sbi->s_group_info = ext4_kvzalloc(array_size, GFP_KERNEL); 2288 if (sbi->s_group_info == NULL) { 2289 ext4_msg(sb, KERN_ERR, "can't allocate buddy meta group"); 2290 return -ENOMEM; 2291 } 2292 sbi->s_buddy_cache = new_inode(sb); 2293 if (sbi->s_buddy_cache == NULL) { 2294 ext4_msg(sb, KERN_ERR, "can't get new inode"); 2295 goto err_freesgi; 2296 } 2297 /* To avoid potentially colliding with an valid on-disk inode number, 2298 * use EXT4_BAD_INO for the buddy cache inode number. This inode is 2299 * not in the inode hash, so it should never be found by iget(), but 2300 * this will avoid confusion if it ever shows up during debugging. */ 2301 sbi->s_buddy_cache->i_ino = EXT4_BAD_INO; 2302 EXT4_I(sbi->s_buddy_cache)->i_disksize = 0; 2303 for (i = 0; i < ngroups; i++) { 2304 desc = ext4_get_group_desc(sb, i, NULL); 2305 if (desc == NULL) { 2306 ext4_msg(sb, KERN_ERR, "can't read descriptor %u", i); 2307 goto err_freebuddy; 2308 } 2309 if (ext4_mb_add_groupinfo(sb, i, desc) != 0) 2310 goto err_freebuddy; 2311 } 2312 2313 return 0; 2314 2315 err_freebuddy: 2316 cachep = get_groupinfo_cache(sb->s_blocksize_bits); 2317 while (i-- > 0) 2318 kmem_cache_free(cachep, ext4_get_group_info(sb, i)); 2319 i = num_meta_group_infos; 2320 while (i-- > 0) 2321 kfree(sbi->s_group_info[i]); 2322 iput(sbi->s_buddy_cache); 2323 err_freesgi: 2324 ext4_kvfree(sbi->s_group_info); 2325 return -ENOMEM; 2326 } 2327 2328 static void ext4_groupinfo_destroy_slabs(void) 2329 { 2330 int i; 2331 2332 for (i = 0; i < NR_GRPINFO_CACHES; i++) { 2333 if (ext4_groupinfo_caches[i]) 2334 kmem_cache_destroy(ext4_groupinfo_caches[i]); 2335 ext4_groupinfo_caches[i] = NULL; 2336 } 2337 } 2338 2339 static int ext4_groupinfo_create_slab(size_t size) 2340 { 2341 static DEFINE_MUTEX(ext4_grpinfo_slab_create_mutex); 2342 int slab_size; 2343 int blocksize_bits = order_base_2(size); 2344 int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE; 2345 struct kmem_cache *cachep; 2346 2347 if (cache_index >= NR_GRPINFO_CACHES) 2348 return -EINVAL; 2349 2350 if (unlikely(cache_index < 0)) 2351 cache_index = 0; 2352 2353 mutex_lock(&ext4_grpinfo_slab_create_mutex); 2354 if (ext4_groupinfo_caches[cache_index]) { 2355 mutex_unlock(&ext4_grpinfo_slab_create_mutex); 2356 return 0; /* Already created */ 2357 } 2358 2359 slab_size = offsetof(struct ext4_group_info, 2360 bb_counters[blocksize_bits + 2]); 2361 2362 cachep = kmem_cache_create(ext4_groupinfo_slab_names[cache_index], 2363 slab_size, 0, SLAB_RECLAIM_ACCOUNT, 2364 NULL); 2365 2366 ext4_groupinfo_caches[cache_index] = cachep; 2367 2368 mutex_unlock(&ext4_grpinfo_slab_create_mutex); 2369 if (!cachep) { 2370 printk(KERN_EMERG 2371 "EXT4-fs: no memory for groupinfo slab cache\n"); 2372 return -ENOMEM; 2373 } 2374 2375 return 0; 2376 } 2377 2378 int ext4_mb_init(struct super_block *sb, int needs_recovery) 2379 { 2380 struct ext4_sb_info *sbi = EXT4_SB(sb); 2381 unsigned i, j; 2382 unsigned offset; 2383 unsigned max; 2384 int ret; 2385 2386 i = (sb->s_blocksize_bits + 2) * sizeof(*sbi->s_mb_offsets); 2387 2388 sbi->s_mb_offsets = kmalloc(i, GFP_KERNEL); 2389 if (sbi->s_mb_offsets == NULL) { 2390 ret = -ENOMEM; 2391 goto out; 2392 } 2393 2394 i = (sb->s_blocksize_bits + 2) * sizeof(*sbi->s_mb_maxs); 2395 sbi->s_mb_maxs = kmalloc(i, GFP_KERNEL); 2396 if (sbi->s_mb_maxs == NULL) { 2397 ret = -ENOMEM; 2398 goto out; 2399 } 2400 2401 ret = ext4_groupinfo_create_slab(sb->s_blocksize); 2402 if (ret < 0) 2403 goto out; 2404 2405 /* order 0 is regular bitmap */ 2406 sbi->s_mb_maxs[0] = sb->s_blocksize << 3; 2407 sbi->s_mb_offsets[0] = 0; 2408 2409 i = 1; 2410 offset = 0; 2411 max = sb->s_blocksize << 2; 2412 do { 2413 sbi->s_mb_offsets[i] = offset; 2414 sbi->s_mb_maxs[i] = max; 2415 offset += 1 << (sb->s_blocksize_bits - i); 2416 max = max >> 1; 2417 i++; 2418 } while (i <= sb->s_blocksize_bits + 1); 2419 2420 spin_lock_init(&sbi->s_md_lock); 2421 spin_lock_init(&sbi->s_bal_lock); 2422 2423 sbi->s_mb_max_to_scan = MB_DEFAULT_MAX_TO_SCAN; 2424 sbi->s_mb_min_to_scan = MB_DEFAULT_MIN_TO_SCAN; 2425 sbi->s_mb_stats = MB_DEFAULT_STATS; 2426 sbi->s_mb_stream_request = MB_DEFAULT_STREAM_THRESHOLD; 2427 sbi->s_mb_order2_reqs = MB_DEFAULT_ORDER2_REQS; 2428 /* 2429 * The default group preallocation is 512, which for 4k block 2430 * sizes translates to 2 megabytes. However for bigalloc file 2431 * systems, this is probably too big (i.e, if the cluster size 2432 * is 1 megabyte, then group preallocation size becomes half a 2433 * gigabyte!). As a default, we will keep a two megabyte 2434 * group pralloc size for cluster sizes up to 64k, and after 2435 * that, we will force a minimum group preallocation size of 2436 * 32 clusters. This translates to 8 megs when the cluster 2437 * size is 256k, and 32 megs when the cluster size is 1 meg, 2438 * which seems reasonable as a default. 2439 */ 2440 sbi->s_mb_group_prealloc = max(MB_DEFAULT_GROUP_PREALLOC >> 2441 sbi->s_cluster_bits, 32); 2442 /* 2443 * If there is a s_stripe > 1, then we set the s_mb_group_prealloc 2444 * to the lowest multiple of s_stripe which is bigger than 2445 * the s_mb_group_prealloc as determined above. We want 2446 * the preallocation size to be an exact multiple of the 2447 * RAID stripe size so that preallocations don't fragment 2448 * the stripes. 2449 */ 2450 if (sbi->s_stripe > 1) { 2451 sbi->s_mb_group_prealloc = roundup( 2452 sbi->s_mb_group_prealloc, sbi->s_stripe); 2453 } 2454 2455 sbi->s_locality_groups = alloc_percpu(struct ext4_locality_group); 2456 if (sbi->s_locality_groups == NULL) { 2457 ret = -ENOMEM; 2458 goto out_free_groupinfo_slab; 2459 } 2460 for_each_possible_cpu(i) { 2461 struct ext4_locality_group *lg; 2462 lg = per_cpu_ptr(sbi->s_locality_groups, i); 2463 mutex_init(&lg->lg_mutex); 2464 for (j = 0; j < PREALLOC_TB_SIZE; j++) 2465 INIT_LIST_HEAD(&lg->lg_prealloc_list[j]); 2466 spin_lock_init(&lg->lg_prealloc_lock); 2467 } 2468 2469 /* init file for buddy data */ 2470 ret = ext4_mb_init_backend(sb); 2471 if (ret != 0) 2472 goto out_free_locality_groups; 2473 2474 if (sbi->s_proc) 2475 proc_create_data("mb_groups", S_IRUGO, sbi->s_proc, 2476 &ext4_mb_seq_groups_fops, sb); 2477 2478 return 0; 2479 2480 out_free_locality_groups: 2481 free_percpu(sbi->s_locality_groups); 2482 sbi->s_locality_groups = NULL; 2483 out_free_groupinfo_slab: 2484 ext4_groupinfo_destroy_slabs(); 2485 out: 2486 kfree(sbi->s_mb_offsets); 2487 sbi->s_mb_offsets = NULL; 2488 kfree(sbi->s_mb_maxs); 2489 sbi->s_mb_maxs = NULL; 2490 return ret; 2491 } 2492 2493 /* need to called with the ext4 group lock held */ 2494 static void ext4_mb_cleanup_pa(struct ext4_group_info *grp) 2495 { 2496 struct ext4_prealloc_space *pa; 2497 struct list_head *cur, *tmp; 2498 int count = 0; 2499 2500 list_for_each_safe(cur, tmp, &grp->bb_prealloc_list) { 2501 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list); 2502 list_del(&pa->pa_group_list); 2503 count++; 2504 kmem_cache_free(ext4_pspace_cachep, pa); 2505 } 2506 if (count) 2507 mb_debug(1, "mballoc: %u PAs left\n", count); 2508 2509 } 2510 2511 int ext4_mb_release(struct super_block *sb) 2512 { 2513 ext4_group_t ngroups = ext4_get_groups_count(sb); 2514 ext4_group_t i; 2515 int num_meta_group_infos; 2516 struct ext4_group_info *grinfo; 2517 struct ext4_sb_info *sbi = EXT4_SB(sb); 2518 struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits); 2519 2520 if (sbi->s_group_info) { 2521 for (i = 0; i < ngroups; i++) { 2522 grinfo = ext4_get_group_info(sb, i); 2523 #ifdef DOUBLE_CHECK 2524 kfree(grinfo->bb_bitmap); 2525 #endif 2526 ext4_lock_group(sb, i); 2527 ext4_mb_cleanup_pa(grinfo); 2528 ext4_unlock_group(sb, i); 2529 kmem_cache_free(cachep, grinfo); 2530 } 2531 num_meta_group_infos = (ngroups + 2532 EXT4_DESC_PER_BLOCK(sb) - 1) >> 2533 EXT4_DESC_PER_BLOCK_BITS(sb); 2534 for (i = 0; i < num_meta_group_infos; i++) 2535 kfree(sbi->s_group_info[i]); 2536 ext4_kvfree(sbi->s_group_info); 2537 } 2538 kfree(sbi->s_mb_offsets); 2539 kfree(sbi->s_mb_maxs); 2540 if (sbi->s_buddy_cache) 2541 iput(sbi->s_buddy_cache); 2542 if (sbi->s_mb_stats) { 2543 ext4_msg(sb, KERN_INFO, 2544 "mballoc: %u blocks %u reqs (%u success)", 2545 atomic_read(&sbi->s_bal_allocated), 2546 atomic_read(&sbi->s_bal_reqs), 2547 atomic_read(&sbi->s_bal_success)); 2548 ext4_msg(sb, KERN_INFO, 2549 "mballoc: %u extents scanned, %u goal hits, " 2550 "%u 2^N hits, %u breaks, %u lost", 2551 atomic_read(&sbi->s_bal_ex_scanned), 2552 atomic_read(&sbi->s_bal_goals), 2553 atomic_read(&sbi->s_bal_2orders), 2554 atomic_read(&sbi->s_bal_breaks), 2555 atomic_read(&sbi->s_mb_lost_chunks)); 2556 ext4_msg(sb, KERN_INFO, 2557 "mballoc: %lu generated and it took %Lu", 2558 sbi->s_mb_buddies_generated, 2559 sbi->s_mb_generation_time); 2560 ext4_msg(sb, KERN_INFO, 2561 "mballoc: %u preallocated, %u discarded", 2562 atomic_read(&sbi->s_mb_preallocated), 2563 atomic_read(&sbi->s_mb_discarded)); 2564 } 2565 2566 free_percpu(sbi->s_locality_groups); 2567 if (sbi->s_proc) 2568 remove_proc_entry("mb_groups", sbi->s_proc); 2569 2570 return 0; 2571 } 2572 2573 static inline int ext4_issue_discard(struct super_block *sb, 2574 ext4_group_t block_group, ext4_grpblk_t cluster, int count) 2575 { 2576 ext4_fsblk_t discard_block; 2577 2578 discard_block = (EXT4_C2B(EXT4_SB(sb), cluster) + 2579 ext4_group_first_block_no(sb, block_group)); 2580 count = EXT4_C2B(EXT4_SB(sb), count); 2581 trace_ext4_discard_blocks(sb, 2582 (unsigned long long) discard_block, count); 2583 return sb_issue_discard(sb, discard_block, count, GFP_NOFS, 0); 2584 } 2585 2586 /* 2587 * This function is called by the jbd2 layer once the commit has finished, 2588 * so we know we can free the blocks that were released with that commit. 2589 */ 2590 static void ext4_free_data_callback(struct super_block *sb, 2591 struct ext4_journal_cb_entry *jce, 2592 int rc) 2593 { 2594 struct ext4_free_data *entry = (struct ext4_free_data *)jce; 2595 struct ext4_buddy e4b; 2596 struct ext4_group_info *db; 2597 int err, count = 0, count2 = 0; 2598 2599 mb_debug(1, "gonna free %u blocks in group %u (0x%p):", 2600 entry->efd_count, entry->efd_group, entry); 2601 2602 if (test_opt(sb, DISCARD)) 2603 ext4_issue_discard(sb, entry->efd_group, 2604 entry->efd_start_cluster, entry->efd_count); 2605 2606 err = ext4_mb_load_buddy(sb, entry->efd_group, &e4b); 2607 /* we expect to find existing buddy because it's pinned */ 2608 BUG_ON(err != 0); 2609 2610 2611 db = e4b.bd_info; 2612 /* there are blocks to put in buddy to make them really free */ 2613 count += entry->efd_count; 2614 count2++; 2615 ext4_lock_group(sb, entry->efd_group); 2616 /* Take it out of per group rb tree */ 2617 rb_erase(&entry->efd_node, &(db->bb_free_root)); 2618 mb_free_blocks(NULL, &e4b, entry->efd_start_cluster, entry->efd_count); 2619 2620 /* 2621 * Clear the trimmed flag for the group so that the next 2622 * ext4_trim_fs can trim it. 2623 * If the volume is mounted with -o discard, online discard 2624 * is supported and the free blocks will be trimmed online. 2625 */ 2626 if (!test_opt(sb, DISCARD)) 2627 EXT4_MB_GRP_CLEAR_TRIMMED(db); 2628 2629 if (!db->bb_free_root.rb_node) { 2630 /* No more items in the per group rb tree 2631 * balance refcounts from ext4_mb_free_metadata() 2632 */ 2633 page_cache_release(e4b.bd_buddy_page); 2634 page_cache_release(e4b.bd_bitmap_page); 2635 } 2636 ext4_unlock_group(sb, entry->efd_group); 2637 kmem_cache_free(ext4_free_data_cachep, entry); 2638 ext4_mb_unload_buddy(&e4b); 2639 2640 mb_debug(1, "freed %u blocks in %u structures\n", count, count2); 2641 } 2642 2643 #ifdef CONFIG_EXT4_DEBUG 2644 u8 mb_enable_debug __read_mostly; 2645 2646 static struct dentry *debugfs_dir; 2647 static struct dentry *debugfs_debug; 2648 2649 static void __init ext4_create_debugfs_entry(void) 2650 { 2651 debugfs_dir = debugfs_create_dir("ext4", NULL); 2652 if (debugfs_dir) 2653 debugfs_debug = debugfs_create_u8("mballoc-debug", 2654 S_IRUGO | S_IWUSR, 2655 debugfs_dir, 2656 &mb_enable_debug); 2657 } 2658 2659 static void ext4_remove_debugfs_entry(void) 2660 { 2661 debugfs_remove(debugfs_debug); 2662 debugfs_remove(debugfs_dir); 2663 } 2664 2665 #else 2666 2667 static void __init ext4_create_debugfs_entry(void) 2668 { 2669 } 2670 2671 static void ext4_remove_debugfs_entry(void) 2672 { 2673 } 2674 2675 #endif 2676 2677 int __init ext4_init_mballoc(void) 2678 { 2679 ext4_pspace_cachep = KMEM_CACHE(ext4_prealloc_space, 2680 SLAB_RECLAIM_ACCOUNT); 2681 if (ext4_pspace_cachep == NULL) 2682 return -ENOMEM; 2683 2684 ext4_ac_cachep = KMEM_CACHE(ext4_allocation_context, 2685 SLAB_RECLAIM_ACCOUNT); 2686 if (ext4_ac_cachep == NULL) { 2687 kmem_cache_destroy(ext4_pspace_cachep); 2688 return -ENOMEM; 2689 } 2690 2691 ext4_free_data_cachep = KMEM_CACHE(ext4_free_data, 2692 SLAB_RECLAIM_ACCOUNT); 2693 if (ext4_free_data_cachep == NULL) { 2694 kmem_cache_destroy(ext4_pspace_cachep); 2695 kmem_cache_destroy(ext4_ac_cachep); 2696 return -ENOMEM; 2697 } 2698 ext4_create_debugfs_entry(); 2699 return 0; 2700 } 2701 2702 void ext4_exit_mballoc(void) 2703 { 2704 /* 2705 * Wait for completion of call_rcu()'s on ext4_pspace_cachep 2706 * before destroying the slab cache. 2707 */ 2708 rcu_barrier(); 2709 kmem_cache_destroy(ext4_pspace_cachep); 2710 kmem_cache_destroy(ext4_ac_cachep); 2711 kmem_cache_destroy(ext4_free_data_cachep); 2712 ext4_groupinfo_destroy_slabs(); 2713 ext4_remove_debugfs_entry(); 2714 } 2715 2716 2717 /* 2718 * Check quota and mark chosen space (ac->ac_b_ex) non-free in bitmaps 2719 * Returns 0 if success or error code 2720 */ 2721 static noinline_for_stack int 2722 ext4_mb_mark_diskspace_used(struct ext4_allocation_context *ac, 2723 handle_t *handle, unsigned int reserv_clstrs) 2724 { 2725 struct buffer_head *bitmap_bh = NULL; 2726 struct ext4_group_desc *gdp; 2727 struct buffer_head *gdp_bh; 2728 struct ext4_sb_info *sbi; 2729 struct super_block *sb; 2730 ext4_fsblk_t block; 2731 int err, len; 2732 2733 BUG_ON(ac->ac_status != AC_STATUS_FOUND); 2734 BUG_ON(ac->ac_b_ex.fe_len <= 0); 2735 2736 sb = ac->ac_sb; 2737 sbi = EXT4_SB(sb); 2738 2739 err = -EIO; 2740 bitmap_bh = ext4_read_block_bitmap(sb, ac->ac_b_ex.fe_group); 2741 if (!bitmap_bh) 2742 goto out_err; 2743 2744 err = ext4_journal_get_write_access(handle, bitmap_bh); 2745 if (err) 2746 goto out_err; 2747 2748 err = -EIO; 2749 gdp = ext4_get_group_desc(sb, ac->ac_b_ex.fe_group, &gdp_bh); 2750 if (!gdp) 2751 goto out_err; 2752 2753 ext4_debug("using block group %u(%d)\n", ac->ac_b_ex.fe_group, 2754 ext4_free_group_clusters(sb, gdp)); 2755 2756 err = ext4_journal_get_write_access(handle, gdp_bh); 2757 if (err) 2758 goto out_err; 2759 2760 block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex); 2761 2762 len = EXT4_C2B(sbi, ac->ac_b_ex.fe_len); 2763 if (!ext4_data_block_valid(sbi, block, len)) { 2764 ext4_error(sb, "Allocating blocks %llu-%llu which overlap " 2765 "fs metadata", block, block+len); 2766 /* File system mounted not to panic on error 2767 * Fix the bitmap and repeat the block allocation 2768 * We leak some of the blocks here. 2769 */ 2770 ext4_lock_group(sb, ac->ac_b_ex.fe_group); 2771 ext4_set_bits(bitmap_bh->b_data, ac->ac_b_ex.fe_start, 2772 ac->ac_b_ex.fe_len); 2773 ext4_unlock_group(sb, ac->ac_b_ex.fe_group); 2774 err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh); 2775 if (!err) 2776 err = -EAGAIN; 2777 goto out_err; 2778 } 2779 2780 ext4_lock_group(sb, ac->ac_b_ex.fe_group); 2781 #ifdef AGGRESSIVE_CHECK 2782 { 2783 int i; 2784 for (i = 0; i < ac->ac_b_ex.fe_len; i++) { 2785 BUG_ON(mb_test_bit(ac->ac_b_ex.fe_start + i, 2786 bitmap_bh->b_data)); 2787 } 2788 } 2789 #endif 2790 ext4_set_bits(bitmap_bh->b_data, ac->ac_b_ex.fe_start, 2791 ac->ac_b_ex.fe_len); 2792 if (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) { 2793 gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT); 2794 ext4_free_group_clusters_set(sb, gdp, 2795 ext4_free_clusters_after_init(sb, 2796 ac->ac_b_ex.fe_group, gdp)); 2797 } 2798 len = ext4_free_group_clusters(sb, gdp) - ac->ac_b_ex.fe_len; 2799 ext4_free_group_clusters_set(sb, gdp, len); 2800 gdp->bg_checksum = ext4_group_desc_csum(sbi, ac->ac_b_ex.fe_group, gdp); 2801 2802 ext4_unlock_group(sb, ac->ac_b_ex.fe_group); 2803 percpu_counter_sub(&sbi->s_freeclusters_counter, ac->ac_b_ex.fe_len); 2804 /* 2805 * Now reduce the dirty block count also. Should not go negative 2806 */ 2807 if (!(ac->ac_flags & EXT4_MB_DELALLOC_RESERVED)) 2808 /* release all the reserved blocks if non delalloc */ 2809 percpu_counter_sub(&sbi->s_dirtyclusters_counter, 2810 reserv_clstrs); 2811 2812 if (sbi->s_log_groups_per_flex) { 2813 ext4_group_t flex_group = ext4_flex_group(sbi, 2814 ac->ac_b_ex.fe_group); 2815 atomic_sub(ac->ac_b_ex.fe_len, 2816 &sbi->s_flex_groups[flex_group].free_clusters); 2817 } 2818 2819 err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh); 2820 if (err) 2821 goto out_err; 2822 err = ext4_handle_dirty_metadata(handle, NULL, gdp_bh); 2823 2824 out_err: 2825 ext4_mark_super_dirty(sb); 2826 brelse(bitmap_bh); 2827 return err; 2828 } 2829 2830 /* 2831 * here we normalize request for locality group 2832 * Group request are normalized to s_mb_group_prealloc, which goes to 2833 * s_strip if we set the same via mount option. 2834 * s_mb_group_prealloc can be configured via 2835 * /sys/fs/ext4/<partition>/mb_group_prealloc 2836 * 2837 * XXX: should we try to preallocate more than the group has now? 2838 */ 2839 static void ext4_mb_normalize_group_request(struct ext4_allocation_context *ac) 2840 { 2841 struct super_block *sb = ac->ac_sb; 2842 struct ext4_locality_group *lg = ac->ac_lg; 2843 2844 BUG_ON(lg == NULL); 2845 ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_mb_group_prealloc; 2846 mb_debug(1, "#%u: goal %u blocks for locality group\n", 2847 current->pid, ac->ac_g_ex.fe_len); 2848 } 2849 2850 /* 2851 * Normalization means making request better in terms of 2852 * size and alignment 2853 */ 2854 static noinline_for_stack void 2855 ext4_mb_normalize_request(struct ext4_allocation_context *ac, 2856 struct ext4_allocation_request *ar) 2857 { 2858 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb); 2859 int bsbits, max; 2860 ext4_lblk_t end; 2861 loff_t size, start_off; 2862 loff_t orig_size __maybe_unused; 2863 ext4_lblk_t start; 2864 struct ext4_inode_info *ei = EXT4_I(ac->ac_inode); 2865 struct ext4_prealloc_space *pa; 2866 2867 /* do normalize only data requests, metadata requests 2868 do not need preallocation */ 2869 if (!(ac->ac_flags & EXT4_MB_HINT_DATA)) 2870 return; 2871 2872 /* sometime caller may want exact blocks */ 2873 if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY)) 2874 return; 2875 2876 /* caller may indicate that preallocation isn't 2877 * required (it's a tail, for example) */ 2878 if (ac->ac_flags & EXT4_MB_HINT_NOPREALLOC) 2879 return; 2880 2881 if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) { 2882 ext4_mb_normalize_group_request(ac); 2883 return ; 2884 } 2885 2886 bsbits = ac->ac_sb->s_blocksize_bits; 2887 2888 /* first, let's learn actual file size 2889 * given current request is allocated */ 2890 size = ac->ac_o_ex.fe_logical + EXT4_C2B(sbi, ac->ac_o_ex.fe_len); 2891 size = size << bsbits; 2892 if (size < i_size_read(ac->ac_inode)) 2893 size = i_size_read(ac->ac_inode); 2894 orig_size = size; 2895 2896 /* max size of free chunks */ 2897 max = 2 << bsbits; 2898 2899 #define NRL_CHECK_SIZE(req, size, max, chunk_size) \ 2900 (req <= (size) || max <= (chunk_size)) 2901 2902 /* first, try to predict filesize */ 2903 /* XXX: should this table be tunable? */ 2904 start_off = 0; 2905 if (size <= 16 * 1024) { 2906 size = 16 * 1024; 2907 } else if (size <= 32 * 1024) { 2908 size = 32 * 1024; 2909 } else if (size <= 64 * 1024) { 2910 size = 64 * 1024; 2911 } else if (size <= 128 * 1024) { 2912 size = 128 * 1024; 2913 } else if (size <= 256 * 1024) { 2914 size = 256 * 1024; 2915 } else if (size <= 512 * 1024) { 2916 size = 512 * 1024; 2917 } else if (size <= 1024 * 1024) { 2918 size = 1024 * 1024; 2919 } else if (NRL_CHECK_SIZE(size, 4 * 1024 * 1024, max, 2 * 1024)) { 2920 start_off = ((loff_t)ac->ac_o_ex.fe_logical >> 2921 (21 - bsbits)) << 21; 2922 size = 2 * 1024 * 1024; 2923 } else if (NRL_CHECK_SIZE(size, 8 * 1024 * 1024, max, 4 * 1024)) { 2924 start_off = ((loff_t)ac->ac_o_ex.fe_logical >> 2925 (22 - bsbits)) << 22; 2926 size = 4 * 1024 * 1024; 2927 } else if (NRL_CHECK_SIZE(ac->ac_o_ex.fe_len, 2928 (8<<20)>>bsbits, max, 8 * 1024)) { 2929 start_off = ((loff_t)ac->ac_o_ex.fe_logical >> 2930 (23 - bsbits)) << 23; 2931 size = 8 * 1024 * 1024; 2932 } else { 2933 start_off = (loff_t)ac->ac_o_ex.fe_logical << bsbits; 2934 size = ac->ac_o_ex.fe_len << bsbits; 2935 } 2936 size = size >> bsbits; 2937 start = start_off >> bsbits; 2938 2939 /* don't cover already allocated blocks in selected range */ 2940 if (ar->pleft && start <= ar->lleft) { 2941 size -= ar->lleft + 1 - start; 2942 start = ar->lleft + 1; 2943 } 2944 if (ar->pright && start + size - 1 >= ar->lright) 2945 size -= start + size - ar->lright; 2946 2947 end = start + size; 2948 2949 /* check we don't cross already preallocated blocks */ 2950 rcu_read_lock(); 2951 list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) { 2952 ext4_lblk_t pa_end; 2953 2954 if (pa->pa_deleted) 2955 continue; 2956 spin_lock(&pa->pa_lock); 2957 if (pa->pa_deleted) { 2958 spin_unlock(&pa->pa_lock); 2959 continue; 2960 } 2961 2962 pa_end = pa->pa_lstart + EXT4_C2B(EXT4_SB(ac->ac_sb), 2963 pa->pa_len); 2964 2965 /* PA must not overlap original request */ 2966 BUG_ON(!(ac->ac_o_ex.fe_logical >= pa_end || 2967 ac->ac_o_ex.fe_logical < pa->pa_lstart)); 2968 2969 /* skip PAs this normalized request doesn't overlap with */ 2970 if (pa->pa_lstart >= end || pa_end <= start) { 2971 spin_unlock(&pa->pa_lock); 2972 continue; 2973 } 2974 BUG_ON(pa->pa_lstart <= start && pa_end >= end); 2975 2976 /* adjust start or end to be adjacent to this pa */ 2977 if (pa_end <= ac->ac_o_ex.fe_logical) { 2978 BUG_ON(pa_end < start); 2979 start = pa_end; 2980 } else if (pa->pa_lstart > ac->ac_o_ex.fe_logical) { 2981 BUG_ON(pa->pa_lstart > end); 2982 end = pa->pa_lstart; 2983 } 2984 spin_unlock(&pa->pa_lock); 2985 } 2986 rcu_read_unlock(); 2987 size = end - start; 2988 2989 /* XXX: extra loop to check we really don't overlap preallocations */ 2990 rcu_read_lock(); 2991 list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) { 2992 ext4_lblk_t pa_end; 2993 2994 spin_lock(&pa->pa_lock); 2995 if (pa->pa_deleted == 0) { 2996 pa_end = pa->pa_lstart + EXT4_C2B(EXT4_SB(ac->ac_sb), 2997 pa->pa_len); 2998 BUG_ON(!(start >= pa_end || end <= pa->pa_lstart)); 2999 } 3000 spin_unlock(&pa->pa_lock); 3001 } 3002 rcu_read_unlock(); 3003 3004 if (start + size <= ac->ac_o_ex.fe_logical && 3005 start > ac->ac_o_ex.fe_logical) { 3006 ext4_msg(ac->ac_sb, KERN_ERR, 3007 "start %lu, size %lu, fe_logical %lu", 3008 (unsigned long) start, (unsigned long) size, 3009 (unsigned long) ac->ac_o_ex.fe_logical); 3010 } 3011 BUG_ON(start + size <= ac->ac_o_ex.fe_logical && 3012 start > ac->ac_o_ex.fe_logical); 3013 BUG_ON(size <= 0 || size > EXT4_CLUSTERS_PER_GROUP(ac->ac_sb)); 3014 3015 /* now prepare goal request */ 3016 3017 /* XXX: is it better to align blocks WRT to logical 3018 * placement or satisfy big request as is */ 3019 ac->ac_g_ex.fe_logical = start; 3020 ac->ac_g_ex.fe_len = EXT4_NUM_B2C(sbi, size); 3021 3022 /* define goal start in order to merge */ 3023 if (ar->pright && (ar->lright == (start + size))) { 3024 /* merge to the right */ 3025 ext4_get_group_no_and_offset(ac->ac_sb, ar->pright - size, 3026 &ac->ac_f_ex.fe_group, 3027 &ac->ac_f_ex.fe_start); 3028 ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL; 3029 } 3030 if (ar->pleft && (ar->lleft + 1 == start)) { 3031 /* merge to the left */ 3032 ext4_get_group_no_and_offset(ac->ac_sb, ar->pleft + 1, 3033 &ac->ac_f_ex.fe_group, 3034 &ac->ac_f_ex.fe_start); 3035 ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL; 3036 } 3037 3038 mb_debug(1, "goal: %u(was %u) blocks at %u\n", (unsigned) size, 3039 (unsigned) orig_size, (unsigned) start); 3040 } 3041 3042 static void ext4_mb_collect_stats(struct ext4_allocation_context *ac) 3043 { 3044 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb); 3045 3046 if (sbi->s_mb_stats && ac->ac_g_ex.fe_len > 1) { 3047 atomic_inc(&sbi->s_bal_reqs); 3048 atomic_add(ac->ac_b_ex.fe_len, &sbi->s_bal_allocated); 3049 if (ac->ac_b_ex.fe_len >= ac->ac_o_ex.fe_len) 3050 atomic_inc(&sbi->s_bal_success); 3051 atomic_add(ac->ac_found, &sbi->s_bal_ex_scanned); 3052 if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start && 3053 ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group) 3054 atomic_inc(&sbi->s_bal_goals); 3055 if (ac->ac_found > sbi->s_mb_max_to_scan) 3056 atomic_inc(&sbi->s_bal_breaks); 3057 } 3058 3059 if (ac->ac_op == EXT4_MB_HISTORY_ALLOC) 3060 trace_ext4_mballoc_alloc(ac); 3061 else 3062 trace_ext4_mballoc_prealloc(ac); 3063 } 3064 3065 /* 3066 * Called on failure; free up any blocks from the inode PA for this 3067 * context. We don't need this for MB_GROUP_PA because we only change 3068 * pa_free in ext4_mb_release_context(), but on failure, we've already 3069 * zeroed out ac->ac_b_ex.fe_len, so group_pa->pa_free is not changed. 3070 */ 3071 static void ext4_discard_allocated_blocks(struct ext4_allocation_context *ac) 3072 { 3073 struct ext4_prealloc_space *pa = ac->ac_pa; 3074 int len; 3075 3076 if (pa && pa->pa_type == MB_INODE_PA) { 3077 len = ac->ac_b_ex.fe_len; 3078 pa->pa_free += len; 3079 } 3080 3081 } 3082 3083 /* 3084 * use blocks preallocated to inode 3085 */ 3086 static void ext4_mb_use_inode_pa(struct ext4_allocation_context *ac, 3087 struct ext4_prealloc_space *pa) 3088 { 3089 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb); 3090 ext4_fsblk_t start; 3091 ext4_fsblk_t end; 3092 int len; 3093 3094 /* found preallocated blocks, use them */ 3095 start = pa->pa_pstart + (ac->ac_o_ex.fe_logical - pa->pa_lstart); 3096 end = min(pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len), 3097 start + EXT4_C2B(sbi, ac->ac_o_ex.fe_len)); 3098 len = EXT4_NUM_B2C(sbi, end - start); 3099 ext4_get_group_no_and_offset(ac->ac_sb, start, &ac->ac_b_ex.fe_group, 3100 &ac->ac_b_ex.fe_start); 3101 ac->ac_b_ex.fe_len = len; 3102 ac->ac_status = AC_STATUS_FOUND; 3103 ac->ac_pa = pa; 3104 3105 BUG_ON(start < pa->pa_pstart); 3106 BUG_ON(end > pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len)); 3107 BUG_ON(pa->pa_free < len); 3108 pa->pa_free -= len; 3109 3110 mb_debug(1, "use %llu/%u from inode pa %p\n", start, len, pa); 3111 } 3112 3113 /* 3114 * use blocks preallocated to locality group 3115 */ 3116 static void ext4_mb_use_group_pa(struct ext4_allocation_context *ac, 3117 struct ext4_prealloc_space *pa) 3118 { 3119 unsigned int len = ac->ac_o_ex.fe_len; 3120 3121 ext4_get_group_no_and_offset(ac->ac_sb, pa->pa_pstart, 3122 &ac->ac_b_ex.fe_group, 3123 &ac->ac_b_ex.fe_start); 3124 ac->ac_b_ex.fe_len = len; 3125 ac->ac_status = AC_STATUS_FOUND; 3126 ac->ac_pa = pa; 3127 3128 /* we don't correct pa_pstart or pa_plen here to avoid 3129 * possible race when the group is being loaded concurrently 3130 * instead we correct pa later, after blocks are marked 3131 * in on-disk bitmap -- see ext4_mb_release_context() 3132 * Other CPUs are prevented from allocating from this pa by lg_mutex 3133 */ 3134 mb_debug(1, "use %u/%u from group pa %p\n", pa->pa_lstart-len, len, pa); 3135 } 3136 3137 /* 3138 * Return the prealloc space that have minimal distance 3139 * from the goal block. @cpa is the prealloc 3140 * space that is having currently known minimal distance 3141 * from the goal block. 3142 */ 3143 static struct ext4_prealloc_space * 3144 ext4_mb_check_group_pa(ext4_fsblk_t goal_block, 3145 struct ext4_prealloc_space *pa, 3146 struct ext4_prealloc_space *cpa) 3147 { 3148 ext4_fsblk_t cur_distance, new_distance; 3149 3150 if (cpa == NULL) { 3151 atomic_inc(&pa->pa_count); 3152 return pa; 3153 } 3154 cur_distance = abs(goal_block - cpa->pa_pstart); 3155 new_distance = abs(goal_block - pa->pa_pstart); 3156 3157 if (cur_distance <= new_distance) 3158 return cpa; 3159 3160 /* drop the previous reference */ 3161 atomic_dec(&cpa->pa_count); 3162 atomic_inc(&pa->pa_count); 3163 return pa; 3164 } 3165 3166 /* 3167 * search goal blocks in preallocated space 3168 */ 3169 static noinline_for_stack int 3170 ext4_mb_use_preallocated(struct ext4_allocation_context *ac) 3171 { 3172 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb); 3173 int order, i; 3174 struct ext4_inode_info *ei = EXT4_I(ac->ac_inode); 3175 struct ext4_locality_group *lg; 3176 struct ext4_prealloc_space *pa, *cpa = NULL; 3177 ext4_fsblk_t goal_block; 3178 3179 /* only data can be preallocated */ 3180 if (!(ac->ac_flags & EXT4_MB_HINT_DATA)) 3181 return 0; 3182 3183 /* first, try per-file preallocation */ 3184 rcu_read_lock(); 3185 list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) { 3186 3187 /* all fields in this condition don't change, 3188 * so we can skip locking for them */ 3189 if (ac->ac_o_ex.fe_logical < pa->pa_lstart || 3190 ac->ac_o_ex.fe_logical >= (pa->pa_lstart + 3191 EXT4_C2B(sbi, pa->pa_len))) 3192 continue; 3193 3194 /* non-extent files can't have physical blocks past 2^32 */ 3195 if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)) && 3196 (pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len) > 3197 EXT4_MAX_BLOCK_FILE_PHYS)) 3198 continue; 3199 3200 /* found preallocated blocks, use them */ 3201 spin_lock(&pa->pa_lock); 3202 if (pa->pa_deleted == 0 && pa->pa_free) { 3203 atomic_inc(&pa->pa_count); 3204 ext4_mb_use_inode_pa(ac, pa); 3205 spin_unlock(&pa->pa_lock); 3206 ac->ac_criteria = 10; 3207 rcu_read_unlock(); 3208 return 1; 3209 } 3210 spin_unlock(&pa->pa_lock); 3211 } 3212 rcu_read_unlock(); 3213 3214 /* can we use group allocation? */ 3215 if (!(ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)) 3216 return 0; 3217 3218 /* inode may have no locality group for some reason */ 3219 lg = ac->ac_lg; 3220 if (lg == NULL) 3221 return 0; 3222 order = fls(ac->ac_o_ex.fe_len) - 1; 3223 if (order > PREALLOC_TB_SIZE - 1) 3224 /* The max size of hash table is PREALLOC_TB_SIZE */ 3225 order = PREALLOC_TB_SIZE - 1; 3226 3227 goal_block = ext4_grp_offs_to_block(ac->ac_sb, &ac->ac_g_ex); 3228 /* 3229 * search for the prealloc space that is having 3230 * minimal distance from the goal block. 3231 */ 3232 for (i = order; i < PREALLOC_TB_SIZE; i++) { 3233 rcu_read_lock(); 3234 list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[i], 3235 pa_inode_list) { 3236 spin_lock(&pa->pa_lock); 3237 if (pa->pa_deleted == 0 && 3238 pa->pa_free >= ac->ac_o_ex.fe_len) { 3239 3240 cpa = ext4_mb_check_group_pa(goal_block, 3241 pa, cpa); 3242 } 3243 spin_unlock(&pa->pa_lock); 3244 } 3245 rcu_read_unlock(); 3246 } 3247 if (cpa) { 3248 ext4_mb_use_group_pa(ac, cpa); 3249 ac->ac_criteria = 20; 3250 return 1; 3251 } 3252 return 0; 3253 } 3254 3255 /* 3256 * the function goes through all block freed in the group 3257 * but not yet committed and marks them used in in-core bitmap. 3258 * buddy must be generated from this bitmap 3259 * Need to be called with the ext4 group lock held 3260 */ 3261 static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap, 3262 ext4_group_t group) 3263 { 3264 struct rb_node *n; 3265 struct ext4_group_info *grp; 3266 struct ext4_free_data *entry; 3267 3268 grp = ext4_get_group_info(sb, group); 3269 n = rb_first(&(grp->bb_free_root)); 3270 3271 while (n) { 3272 entry = rb_entry(n, struct ext4_free_data, efd_node); 3273 ext4_set_bits(bitmap, entry->efd_start_cluster, entry->efd_count); 3274 n = rb_next(n); 3275 } 3276 return; 3277 } 3278 3279 /* 3280 * the function goes through all preallocation in this group and marks them 3281 * used in in-core bitmap. buddy must be generated from this bitmap 3282 * Need to be called with ext4 group lock held 3283 */ 3284 static noinline_for_stack 3285 void ext4_mb_generate_from_pa(struct super_block *sb, void *bitmap, 3286 ext4_group_t group) 3287 { 3288 struct ext4_group_info *grp = ext4_get_group_info(sb, group); 3289 struct ext4_prealloc_space *pa; 3290 struct list_head *cur; 3291 ext4_group_t groupnr; 3292 ext4_grpblk_t start; 3293 int preallocated = 0; 3294 int len; 3295 3296 /* all form of preallocation discards first load group, 3297 * so the only competing code is preallocation use. 3298 * we don't need any locking here 3299 * notice we do NOT ignore preallocations with pa_deleted 3300 * otherwise we could leave used blocks available for 3301 * allocation in buddy when concurrent ext4_mb_put_pa() 3302 * is dropping preallocation 3303 */ 3304 list_for_each(cur, &grp->bb_prealloc_list) { 3305 pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list); 3306 spin_lock(&pa->pa_lock); 3307 ext4_get_group_no_and_offset(sb, pa->pa_pstart, 3308 &groupnr, &start); 3309 len = pa->pa_len; 3310 spin_unlock(&pa->pa_lock); 3311 if (unlikely(len == 0)) 3312 continue; 3313 BUG_ON(groupnr != group); 3314 ext4_set_bits(bitmap, start, len); 3315 preallocated += len; 3316 } 3317 mb_debug(1, "prellocated %u for group %u\n", preallocated, group); 3318 } 3319 3320 static void ext4_mb_pa_callback(struct rcu_head *head) 3321 { 3322 struct ext4_prealloc_space *pa; 3323 pa = container_of(head, struct ext4_prealloc_space, u.pa_rcu); 3324 kmem_cache_free(ext4_pspace_cachep, pa); 3325 } 3326 3327 /* 3328 * drops a reference to preallocated space descriptor 3329 * if this was the last reference and the space is consumed 3330 */ 3331 static void ext4_mb_put_pa(struct ext4_allocation_context *ac, 3332 struct super_block *sb, struct ext4_prealloc_space *pa) 3333 { 3334 ext4_group_t grp; 3335 ext4_fsblk_t grp_blk; 3336 3337 if (!atomic_dec_and_test(&pa->pa_count) || pa->pa_free != 0) 3338 return; 3339 3340 /* in this short window concurrent discard can set pa_deleted */ 3341 spin_lock(&pa->pa_lock); 3342 if (pa->pa_deleted == 1) { 3343 spin_unlock(&pa->pa_lock); 3344 return; 3345 } 3346 3347 pa->pa_deleted = 1; 3348 spin_unlock(&pa->pa_lock); 3349 3350 grp_blk = pa->pa_pstart; 3351 /* 3352 * If doing group-based preallocation, pa_pstart may be in the 3353 * next group when pa is used up 3354 */ 3355 if (pa->pa_type == MB_GROUP_PA) 3356 grp_blk--; 3357 3358 ext4_get_group_no_and_offset(sb, grp_blk, &grp, NULL); 3359 3360 /* 3361 * possible race: 3362 * 3363 * P1 (buddy init) P2 (regular allocation) 3364 * find block B in PA 3365 * copy on-disk bitmap to buddy 3366 * mark B in on-disk bitmap 3367 * drop PA from group 3368 * mark all PAs in buddy 3369 * 3370 * thus, P1 initializes buddy with B available. to prevent this 3371 * we make "copy" and "mark all PAs" atomic and serialize "drop PA" 3372 * against that pair 3373 */ 3374 ext4_lock_group(sb, grp); 3375 list_del(&pa->pa_group_list); 3376 ext4_unlock_group(sb, grp); 3377 3378 spin_lock(pa->pa_obj_lock); 3379 list_del_rcu(&pa->pa_inode_list); 3380 spin_unlock(pa->pa_obj_lock); 3381 3382 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback); 3383 } 3384 3385 /* 3386 * creates new preallocated space for given inode 3387 */ 3388 static noinline_for_stack int 3389 ext4_mb_new_inode_pa(struct ext4_allocation_context *ac) 3390 { 3391 struct super_block *sb = ac->ac_sb; 3392 struct ext4_sb_info *sbi = EXT4_SB(sb); 3393 struct ext4_prealloc_space *pa; 3394 struct ext4_group_info *grp; 3395 struct ext4_inode_info *ei; 3396 3397 /* preallocate only when found space is larger then requested */ 3398 BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len); 3399 BUG_ON(ac->ac_status != AC_STATUS_FOUND); 3400 BUG_ON(!S_ISREG(ac->ac_inode->i_mode)); 3401 3402 pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS); 3403 if (pa == NULL) 3404 return -ENOMEM; 3405 3406 if (ac->ac_b_ex.fe_len < ac->ac_g_ex.fe_len) { 3407 int winl; 3408 int wins; 3409 int win; 3410 int offs; 3411 3412 /* we can't allocate as much as normalizer wants. 3413 * so, found space must get proper lstart 3414 * to cover original request */ 3415 BUG_ON(ac->ac_g_ex.fe_logical > ac->ac_o_ex.fe_logical); 3416 BUG_ON(ac->ac_g_ex.fe_len < ac->ac_o_ex.fe_len); 3417 3418 /* we're limited by original request in that 3419 * logical block must be covered any way 3420 * winl is window we can move our chunk within */ 3421 winl = ac->ac_o_ex.fe_logical - ac->ac_g_ex.fe_logical; 3422 3423 /* also, we should cover whole original request */ 3424 wins = EXT4_C2B(sbi, ac->ac_b_ex.fe_len - ac->ac_o_ex.fe_len); 3425 3426 /* the smallest one defines real window */ 3427 win = min(winl, wins); 3428 3429 offs = ac->ac_o_ex.fe_logical % 3430 EXT4_C2B(sbi, ac->ac_b_ex.fe_len); 3431 if (offs && offs < win) 3432 win = offs; 3433 3434 ac->ac_b_ex.fe_logical = ac->ac_o_ex.fe_logical - 3435 EXT4_B2C(sbi, win); 3436 BUG_ON(ac->ac_o_ex.fe_logical < ac->ac_b_ex.fe_logical); 3437 BUG_ON(ac->ac_o_ex.fe_len > ac->ac_b_ex.fe_len); 3438 } 3439 3440 /* preallocation can change ac_b_ex, thus we store actually 3441 * allocated blocks for history */ 3442 ac->ac_f_ex = ac->ac_b_ex; 3443 3444 pa->pa_lstart = ac->ac_b_ex.fe_logical; 3445 pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex); 3446 pa->pa_len = ac->ac_b_ex.fe_len; 3447 pa->pa_free = pa->pa_len; 3448 atomic_set(&pa->pa_count, 1); 3449 spin_lock_init(&pa->pa_lock); 3450 INIT_LIST_HEAD(&pa->pa_inode_list); 3451 INIT_LIST_HEAD(&pa->pa_group_list); 3452 pa->pa_deleted = 0; 3453 pa->pa_type = MB_INODE_PA; 3454 3455 mb_debug(1, "new inode pa %p: %llu/%u for %u\n", pa, 3456 pa->pa_pstart, pa->pa_len, pa->pa_lstart); 3457 trace_ext4_mb_new_inode_pa(ac, pa); 3458 3459 ext4_mb_use_inode_pa(ac, pa); 3460 atomic_add(pa->pa_free, &sbi->s_mb_preallocated); 3461 3462 ei = EXT4_I(ac->ac_inode); 3463 grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group); 3464 3465 pa->pa_obj_lock = &ei->i_prealloc_lock; 3466 pa->pa_inode = ac->ac_inode; 3467 3468 ext4_lock_group(sb, ac->ac_b_ex.fe_group); 3469 list_add(&pa->pa_group_list, &grp->bb_prealloc_list); 3470 ext4_unlock_group(sb, ac->ac_b_ex.fe_group); 3471 3472 spin_lock(pa->pa_obj_lock); 3473 list_add_rcu(&pa->pa_inode_list, &ei->i_prealloc_list); 3474 spin_unlock(pa->pa_obj_lock); 3475 3476 return 0; 3477 } 3478 3479 /* 3480 * creates new preallocated space for locality group inodes belongs to 3481 */ 3482 static noinline_for_stack int 3483 ext4_mb_new_group_pa(struct ext4_allocation_context *ac) 3484 { 3485 struct super_block *sb = ac->ac_sb; 3486 struct ext4_locality_group *lg; 3487 struct ext4_prealloc_space *pa; 3488 struct ext4_group_info *grp; 3489 3490 /* preallocate only when found space is larger then requested */ 3491 BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len); 3492 BUG_ON(ac->ac_status != AC_STATUS_FOUND); 3493 BUG_ON(!S_ISREG(ac->ac_inode->i_mode)); 3494 3495 BUG_ON(ext4_pspace_cachep == NULL); 3496 pa = kmem_cache_alloc(ext4_pspace_cachep, GFP_NOFS); 3497 if (pa == NULL) 3498 return -ENOMEM; 3499 3500 /* preallocation can change ac_b_ex, thus we store actually 3501 * allocated blocks for history */ 3502 ac->ac_f_ex = ac->ac_b_ex; 3503 3504 pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex); 3505 pa->pa_lstart = pa->pa_pstart; 3506 pa->pa_len = ac->ac_b_ex.fe_len; 3507 pa->pa_free = pa->pa_len; 3508 atomic_set(&pa->pa_count, 1); 3509 spin_lock_init(&pa->pa_lock); 3510 INIT_LIST_HEAD(&pa->pa_inode_list); 3511 INIT_LIST_HEAD(&pa->pa_group_list); 3512 pa->pa_deleted = 0; 3513 pa->pa_type = MB_GROUP_PA; 3514 3515 mb_debug(1, "new group pa %p: %llu/%u for %u\n", pa, 3516 pa->pa_pstart, pa->pa_len, pa->pa_lstart); 3517 trace_ext4_mb_new_group_pa(ac, pa); 3518 3519 ext4_mb_use_group_pa(ac, pa); 3520 atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated); 3521 3522 grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group); 3523 lg = ac->ac_lg; 3524 BUG_ON(lg == NULL); 3525 3526 pa->pa_obj_lock = &lg->lg_prealloc_lock; 3527 pa->pa_inode = NULL; 3528 3529 ext4_lock_group(sb, ac->ac_b_ex.fe_group); 3530 list_add(&pa->pa_group_list, &grp->bb_prealloc_list); 3531 ext4_unlock_group(sb, ac->ac_b_ex.fe_group); 3532 3533 /* 3534 * We will later add the new pa to the right bucket 3535 * after updating the pa_free in ext4_mb_release_context 3536 */ 3537 return 0; 3538 } 3539 3540 static int ext4_mb_new_preallocation(struct ext4_allocation_context *ac) 3541 { 3542 int err; 3543 3544 if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) 3545 err = ext4_mb_new_group_pa(ac); 3546 else 3547 err = ext4_mb_new_inode_pa(ac); 3548 return err; 3549 } 3550 3551 /* 3552 * finds all unused blocks in on-disk bitmap, frees them in 3553 * in-core bitmap and buddy. 3554 * @pa must be unlinked from inode and group lists, so that 3555 * nobody else can find/use it. 3556 * the caller MUST hold group/inode locks. 3557 * TODO: optimize the case when there are no in-core structures yet 3558 */ 3559 static noinline_for_stack int 3560 ext4_mb_release_inode_pa(struct ext4_buddy *e4b, struct buffer_head *bitmap_bh, 3561 struct ext4_prealloc_space *pa) 3562 { 3563 struct super_block *sb = e4b->bd_sb; 3564 struct ext4_sb_info *sbi = EXT4_SB(sb); 3565 unsigned int end; 3566 unsigned int next; 3567 ext4_group_t group; 3568 ext4_grpblk_t bit; 3569 unsigned long long grp_blk_start; 3570 int err = 0; 3571 int free = 0; 3572 3573 BUG_ON(pa->pa_deleted == 0); 3574 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit); 3575 grp_blk_start = pa->pa_pstart - EXT4_C2B(sbi, bit); 3576 BUG_ON(group != e4b->bd_group && pa->pa_len != 0); 3577 end = bit + pa->pa_len; 3578 3579 while (bit < end) { 3580 bit = mb_find_next_zero_bit(bitmap_bh->b_data, end, bit); 3581 if (bit >= end) 3582 break; 3583 next = mb_find_next_bit(bitmap_bh->b_data, end, bit); 3584 mb_debug(1, " free preallocated %u/%u in group %u\n", 3585 (unsigned) ext4_group_first_block_no(sb, group) + bit, 3586 (unsigned) next - bit, (unsigned) group); 3587 free += next - bit; 3588 3589 trace_ext4_mballoc_discard(sb, NULL, group, bit, next - bit); 3590 trace_ext4_mb_release_inode_pa(pa, (grp_blk_start + 3591 EXT4_C2B(sbi, bit)), 3592 next - bit); 3593 mb_free_blocks(pa->pa_inode, e4b, bit, next - bit); 3594 bit = next + 1; 3595 } 3596 if (free != pa->pa_free) { 3597 ext4_msg(e4b->bd_sb, KERN_CRIT, 3598 "pa %p: logic %lu, phys. %lu, len %lu", 3599 pa, (unsigned long) pa->pa_lstart, 3600 (unsigned long) pa->pa_pstart, 3601 (unsigned long) pa->pa_len); 3602 ext4_grp_locked_error(sb, group, 0, 0, "free %u, pa_free %u", 3603 free, pa->pa_free); 3604 /* 3605 * pa is already deleted so we use the value obtained 3606 * from the bitmap and continue. 3607 */ 3608 } 3609 atomic_add(free, &sbi->s_mb_discarded); 3610 3611 return err; 3612 } 3613 3614 static noinline_for_stack int 3615 ext4_mb_release_group_pa(struct ext4_buddy *e4b, 3616 struct ext4_prealloc_space *pa) 3617 { 3618 struct super_block *sb = e4b->bd_sb; 3619 ext4_group_t group; 3620 ext4_grpblk_t bit; 3621 3622 trace_ext4_mb_release_group_pa(sb, pa); 3623 BUG_ON(pa->pa_deleted == 0); 3624 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit); 3625 BUG_ON(group != e4b->bd_group && pa->pa_len != 0); 3626 mb_free_blocks(pa->pa_inode, e4b, bit, pa->pa_len); 3627 atomic_add(pa->pa_len, &EXT4_SB(sb)->s_mb_discarded); 3628 trace_ext4_mballoc_discard(sb, NULL, group, bit, pa->pa_len); 3629 3630 return 0; 3631 } 3632 3633 /* 3634 * releases all preallocations in given group 3635 * 3636 * first, we need to decide discard policy: 3637 * - when do we discard 3638 * 1) ENOSPC 3639 * - how many do we discard 3640 * 1) how many requested 3641 */ 3642 static noinline_for_stack int 3643 ext4_mb_discard_group_preallocations(struct super_block *sb, 3644 ext4_group_t group, int needed) 3645 { 3646 struct ext4_group_info *grp = ext4_get_group_info(sb, group); 3647 struct buffer_head *bitmap_bh = NULL; 3648 struct ext4_prealloc_space *pa, *tmp; 3649 struct list_head list; 3650 struct ext4_buddy e4b; 3651 int err; 3652 int busy = 0; 3653 int free = 0; 3654 3655 mb_debug(1, "discard preallocation for group %u\n", group); 3656 3657 if (list_empty(&grp->bb_prealloc_list)) 3658 return 0; 3659 3660 bitmap_bh = ext4_read_block_bitmap(sb, group); 3661 if (bitmap_bh == NULL) { 3662 ext4_error(sb, "Error reading block bitmap for %u", group); 3663 return 0; 3664 } 3665 3666 err = ext4_mb_load_buddy(sb, group, &e4b); 3667 if (err) { 3668 ext4_error(sb, "Error loading buddy information for %u", group); 3669 put_bh(bitmap_bh); 3670 return 0; 3671 } 3672 3673 if (needed == 0) 3674 needed = EXT4_CLUSTERS_PER_GROUP(sb) + 1; 3675 3676 INIT_LIST_HEAD(&list); 3677 repeat: 3678 ext4_lock_group(sb, group); 3679 list_for_each_entry_safe(pa, tmp, 3680 &grp->bb_prealloc_list, pa_group_list) { 3681 spin_lock(&pa->pa_lock); 3682 if (atomic_read(&pa->pa_count)) { 3683 spin_unlock(&pa->pa_lock); 3684 busy = 1; 3685 continue; 3686 } 3687 if (pa->pa_deleted) { 3688 spin_unlock(&pa->pa_lock); 3689 continue; 3690 } 3691 3692 /* seems this one can be freed ... */ 3693 pa->pa_deleted = 1; 3694 3695 /* we can trust pa_free ... */ 3696 free += pa->pa_free; 3697 3698 spin_unlock(&pa->pa_lock); 3699 3700 list_del(&pa->pa_group_list); 3701 list_add(&pa->u.pa_tmp_list, &list); 3702 } 3703 3704 /* if we still need more blocks and some PAs were used, try again */ 3705 if (free < needed && busy) { 3706 busy = 0; 3707 ext4_unlock_group(sb, group); 3708 /* 3709 * Yield the CPU here so that we don't get soft lockup 3710 * in non preempt case. 3711 */ 3712 yield(); 3713 goto repeat; 3714 } 3715 3716 /* found anything to free? */ 3717 if (list_empty(&list)) { 3718 BUG_ON(free != 0); 3719 goto out; 3720 } 3721 3722 /* now free all selected PAs */ 3723 list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) { 3724 3725 /* remove from object (inode or locality group) */ 3726 spin_lock(pa->pa_obj_lock); 3727 list_del_rcu(&pa->pa_inode_list); 3728 spin_unlock(pa->pa_obj_lock); 3729 3730 if (pa->pa_type == MB_GROUP_PA) 3731 ext4_mb_release_group_pa(&e4b, pa); 3732 else 3733 ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa); 3734 3735 list_del(&pa->u.pa_tmp_list); 3736 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback); 3737 } 3738 3739 out: 3740 ext4_unlock_group(sb, group); 3741 ext4_mb_unload_buddy(&e4b); 3742 put_bh(bitmap_bh); 3743 return free; 3744 } 3745 3746 /* 3747 * releases all non-used preallocated blocks for given inode 3748 * 3749 * It's important to discard preallocations under i_data_sem 3750 * We don't want another block to be served from the prealloc 3751 * space when we are discarding the inode prealloc space. 3752 * 3753 * FIXME!! Make sure it is valid at all the call sites 3754 */ 3755 void ext4_discard_preallocations(struct inode *inode) 3756 { 3757 struct ext4_inode_info *ei = EXT4_I(inode); 3758 struct super_block *sb = inode->i_sb; 3759 struct buffer_head *bitmap_bh = NULL; 3760 struct ext4_prealloc_space *pa, *tmp; 3761 ext4_group_t group = 0; 3762 struct list_head list; 3763 struct ext4_buddy e4b; 3764 int err; 3765 3766 if (!S_ISREG(inode->i_mode)) { 3767 /*BUG_ON(!list_empty(&ei->i_prealloc_list));*/ 3768 return; 3769 } 3770 3771 mb_debug(1, "discard preallocation for inode %lu\n", inode->i_ino); 3772 trace_ext4_discard_preallocations(inode); 3773 3774 INIT_LIST_HEAD(&list); 3775 3776 repeat: 3777 /* first, collect all pa's in the inode */ 3778 spin_lock(&ei->i_prealloc_lock); 3779 while (!list_empty(&ei->i_prealloc_list)) { 3780 pa = list_entry(ei->i_prealloc_list.next, 3781 struct ext4_prealloc_space, pa_inode_list); 3782 BUG_ON(pa->pa_obj_lock != &ei->i_prealloc_lock); 3783 spin_lock(&pa->pa_lock); 3784 if (atomic_read(&pa->pa_count)) { 3785 /* this shouldn't happen often - nobody should 3786 * use preallocation while we're discarding it */ 3787 spin_unlock(&pa->pa_lock); 3788 spin_unlock(&ei->i_prealloc_lock); 3789 ext4_msg(sb, KERN_ERR, 3790 "uh-oh! used pa while discarding"); 3791 WARN_ON(1); 3792 schedule_timeout_uninterruptible(HZ); 3793 goto repeat; 3794 3795 } 3796 if (pa->pa_deleted == 0) { 3797 pa->pa_deleted = 1; 3798 spin_unlock(&pa->pa_lock); 3799 list_del_rcu(&pa->pa_inode_list); 3800 list_add(&pa->u.pa_tmp_list, &list); 3801 continue; 3802 } 3803 3804 /* someone is deleting pa right now */ 3805 spin_unlock(&pa->pa_lock); 3806 spin_unlock(&ei->i_prealloc_lock); 3807 3808 /* we have to wait here because pa_deleted 3809 * doesn't mean pa is already unlinked from 3810 * the list. as we might be called from 3811 * ->clear_inode() the inode will get freed 3812 * and concurrent thread which is unlinking 3813 * pa from inode's list may access already 3814 * freed memory, bad-bad-bad */ 3815 3816 /* XXX: if this happens too often, we can 3817 * add a flag to force wait only in case 3818 * of ->clear_inode(), but not in case of 3819 * regular truncate */ 3820 schedule_timeout_uninterruptible(HZ); 3821 goto repeat; 3822 } 3823 spin_unlock(&ei->i_prealloc_lock); 3824 3825 list_for_each_entry_safe(pa, tmp, &list, u.pa_tmp_list) { 3826 BUG_ON(pa->pa_type != MB_INODE_PA); 3827 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, NULL); 3828 3829 err = ext4_mb_load_buddy(sb, group, &e4b); 3830 if (err) { 3831 ext4_error(sb, "Error loading buddy information for %u", 3832 group); 3833 continue; 3834 } 3835 3836 bitmap_bh = ext4_read_block_bitmap(sb, group); 3837 if (bitmap_bh == NULL) { 3838 ext4_error(sb, "Error reading block bitmap for %u", 3839 group); 3840 ext4_mb_unload_buddy(&e4b); 3841 continue; 3842 } 3843 3844 ext4_lock_group(sb, group); 3845 list_del(&pa->pa_group_list); 3846 ext4_mb_release_inode_pa(&e4b, bitmap_bh, pa); 3847 ext4_unlock_group(sb, group); 3848 3849 ext4_mb_unload_buddy(&e4b); 3850 put_bh(bitmap_bh); 3851 3852 list_del(&pa->u.pa_tmp_list); 3853 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback); 3854 } 3855 } 3856 3857 #ifdef CONFIG_EXT4_DEBUG 3858 static void ext4_mb_show_ac(struct ext4_allocation_context *ac) 3859 { 3860 struct super_block *sb = ac->ac_sb; 3861 ext4_group_t ngroups, i; 3862 3863 if (!mb_enable_debug || 3864 (EXT4_SB(sb)->s_mount_flags & EXT4_MF_FS_ABORTED)) 3865 return; 3866 3867 ext4_msg(ac->ac_sb, KERN_ERR, "Can't allocate:" 3868 " Allocation context details:"); 3869 ext4_msg(ac->ac_sb, KERN_ERR, "status %d flags %d", 3870 ac->ac_status, ac->ac_flags); 3871 ext4_msg(ac->ac_sb, KERN_ERR, "orig %lu/%lu/%lu@%lu, " 3872 "goal %lu/%lu/%lu@%lu, " 3873 "best %lu/%lu/%lu@%lu cr %d", 3874 (unsigned long)ac->ac_o_ex.fe_group, 3875 (unsigned long)ac->ac_o_ex.fe_start, 3876 (unsigned long)ac->ac_o_ex.fe_len, 3877 (unsigned long)ac->ac_o_ex.fe_logical, 3878 (unsigned long)ac->ac_g_ex.fe_group, 3879 (unsigned long)ac->ac_g_ex.fe_start, 3880 (unsigned long)ac->ac_g_ex.fe_len, 3881 (unsigned long)ac->ac_g_ex.fe_logical, 3882 (unsigned long)ac->ac_b_ex.fe_group, 3883 (unsigned long)ac->ac_b_ex.fe_start, 3884 (unsigned long)ac->ac_b_ex.fe_len, 3885 (unsigned long)ac->ac_b_ex.fe_logical, 3886 (int)ac->ac_criteria); 3887 ext4_msg(ac->ac_sb, KERN_ERR, "%lu scanned, %d found", 3888 ac->ac_ex_scanned, ac->ac_found); 3889 ext4_msg(ac->ac_sb, KERN_ERR, "groups: "); 3890 ngroups = ext4_get_groups_count(sb); 3891 for (i = 0; i < ngroups; i++) { 3892 struct ext4_group_info *grp = ext4_get_group_info(sb, i); 3893 struct ext4_prealloc_space *pa; 3894 ext4_grpblk_t start; 3895 struct list_head *cur; 3896 ext4_lock_group(sb, i); 3897 list_for_each(cur, &grp->bb_prealloc_list) { 3898 pa = list_entry(cur, struct ext4_prealloc_space, 3899 pa_group_list); 3900 spin_lock(&pa->pa_lock); 3901 ext4_get_group_no_and_offset(sb, pa->pa_pstart, 3902 NULL, &start); 3903 spin_unlock(&pa->pa_lock); 3904 printk(KERN_ERR "PA:%u:%d:%u \n", i, 3905 start, pa->pa_len); 3906 } 3907 ext4_unlock_group(sb, i); 3908 3909 if (grp->bb_free == 0) 3910 continue; 3911 printk(KERN_ERR "%u: %d/%d \n", 3912 i, grp->bb_free, grp->bb_fragments); 3913 } 3914 printk(KERN_ERR "\n"); 3915 } 3916 #else 3917 static inline void ext4_mb_show_ac(struct ext4_allocation_context *ac) 3918 { 3919 return; 3920 } 3921 #endif 3922 3923 /* 3924 * We use locality group preallocation for small size file. The size of the 3925 * file is determined by the current size or the resulting size after 3926 * allocation which ever is larger 3927 * 3928 * One can tune this size via /sys/fs/ext4/<partition>/mb_stream_req 3929 */ 3930 static void ext4_mb_group_or_file(struct ext4_allocation_context *ac) 3931 { 3932 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb); 3933 int bsbits = ac->ac_sb->s_blocksize_bits; 3934 loff_t size, isize; 3935 3936 if (!(ac->ac_flags & EXT4_MB_HINT_DATA)) 3937 return; 3938 3939 if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY)) 3940 return; 3941 3942 size = ac->ac_o_ex.fe_logical + EXT4_C2B(sbi, ac->ac_o_ex.fe_len); 3943 isize = (i_size_read(ac->ac_inode) + ac->ac_sb->s_blocksize - 1) 3944 >> bsbits; 3945 3946 if ((size == isize) && 3947 !ext4_fs_is_busy(sbi) && 3948 (atomic_read(&ac->ac_inode->i_writecount) == 0)) { 3949 ac->ac_flags |= EXT4_MB_HINT_NOPREALLOC; 3950 return; 3951 } 3952 3953 if (sbi->s_mb_group_prealloc <= 0) { 3954 ac->ac_flags |= EXT4_MB_STREAM_ALLOC; 3955 return; 3956 } 3957 3958 /* don't use group allocation for large files */ 3959 size = max(size, isize); 3960 if (size > sbi->s_mb_stream_request) { 3961 ac->ac_flags |= EXT4_MB_STREAM_ALLOC; 3962 return; 3963 } 3964 3965 BUG_ON(ac->ac_lg != NULL); 3966 /* 3967 * locality group prealloc space are per cpu. The reason for having 3968 * per cpu locality group is to reduce the contention between block 3969 * request from multiple CPUs. 3970 */ 3971 ac->ac_lg = __this_cpu_ptr(sbi->s_locality_groups); 3972 3973 /* we're going to use group allocation */ 3974 ac->ac_flags |= EXT4_MB_HINT_GROUP_ALLOC; 3975 3976 /* serialize all allocations in the group */ 3977 mutex_lock(&ac->ac_lg->lg_mutex); 3978 } 3979 3980 static noinline_for_stack int 3981 ext4_mb_initialize_context(struct ext4_allocation_context *ac, 3982 struct ext4_allocation_request *ar) 3983 { 3984 struct super_block *sb = ar->inode->i_sb; 3985 struct ext4_sb_info *sbi = EXT4_SB(sb); 3986 struct ext4_super_block *es = sbi->s_es; 3987 ext4_group_t group; 3988 unsigned int len; 3989 ext4_fsblk_t goal; 3990 ext4_grpblk_t block; 3991 3992 /* we can't allocate > group size */ 3993 len = ar->len; 3994 3995 /* just a dirty hack to filter too big requests */ 3996 if (len >= EXT4_CLUSTERS_PER_GROUP(sb) - 10) 3997 len = EXT4_CLUSTERS_PER_GROUP(sb) - 10; 3998 3999 /* start searching from the goal */ 4000 goal = ar->goal; 4001 if (goal < le32_to_cpu(es->s_first_data_block) || 4002 goal >= ext4_blocks_count(es)) 4003 goal = le32_to_cpu(es->s_first_data_block); 4004 ext4_get_group_no_and_offset(sb, goal, &group, &block); 4005 4006 /* set up allocation goals */ 4007 memset(ac, 0, sizeof(struct ext4_allocation_context)); 4008 ac->ac_b_ex.fe_logical = ar->logical & ~(sbi->s_cluster_ratio - 1); 4009 ac->ac_status = AC_STATUS_CONTINUE; 4010 ac->ac_sb = sb; 4011 ac->ac_inode = ar->inode; 4012 ac->ac_o_ex.fe_logical = ac->ac_b_ex.fe_logical; 4013 ac->ac_o_ex.fe_group = group; 4014 ac->ac_o_ex.fe_start = block; 4015 ac->ac_o_ex.fe_len = len; 4016 ac->ac_g_ex = ac->ac_o_ex; 4017 ac->ac_flags = ar->flags; 4018 4019 /* we have to define context: we'll we work with a file or 4020 * locality group. this is a policy, actually */ 4021 ext4_mb_group_or_file(ac); 4022 4023 mb_debug(1, "init ac: %u blocks @ %u, goal %u, flags %x, 2^%d, " 4024 "left: %u/%u, right %u/%u to %swritable\n", 4025 (unsigned) ar->len, (unsigned) ar->logical, 4026 (unsigned) ar->goal, ac->ac_flags, ac->ac_2order, 4027 (unsigned) ar->lleft, (unsigned) ar->pleft, 4028 (unsigned) ar->lright, (unsigned) ar->pright, 4029 atomic_read(&ar->inode->i_writecount) ? "" : "non-"); 4030 return 0; 4031 4032 } 4033 4034 static noinline_for_stack void 4035 ext4_mb_discard_lg_preallocations(struct super_block *sb, 4036 struct ext4_locality_group *lg, 4037 int order, int total_entries) 4038 { 4039 ext4_group_t group = 0; 4040 struct ext4_buddy e4b; 4041 struct list_head discard_list; 4042 struct ext4_prealloc_space *pa, *tmp; 4043 4044 mb_debug(1, "discard locality group preallocation\n"); 4045 4046 INIT_LIST_HEAD(&discard_list); 4047 4048 spin_lock(&lg->lg_prealloc_lock); 4049 list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[order], 4050 pa_inode_list) { 4051 spin_lock(&pa->pa_lock); 4052 if (atomic_read(&pa->pa_count)) { 4053 /* 4054 * This is the pa that we just used 4055 * for block allocation. So don't 4056 * free that 4057 */ 4058 spin_unlock(&pa->pa_lock); 4059 continue; 4060 } 4061 if (pa->pa_deleted) { 4062 spin_unlock(&pa->pa_lock); 4063 continue; 4064 } 4065 /* only lg prealloc space */ 4066 BUG_ON(pa->pa_type != MB_GROUP_PA); 4067 4068 /* seems this one can be freed ... */ 4069 pa->pa_deleted = 1; 4070 spin_unlock(&pa->pa_lock); 4071 4072 list_del_rcu(&pa->pa_inode_list); 4073 list_add(&pa->u.pa_tmp_list, &discard_list); 4074 4075 total_entries--; 4076 if (total_entries <= 5) { 4077 /* 4078 * we want to keep only 5 entries 4079 * allowing it to grow to 8. This 4080 * mak sure we don't call discard 4081 * soon for this list. 4082 */ 4083 break; 4084 } 4085 } 4086 spin_unlock(&lg->lg_prealloc_lock); 4087 4088 list_for_each_entry_safe(pa, tmp, &discard_list, u.pa_tmp_list) { 4089 4090 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, NULL); 4091 if (ext4_mb_load_buddy(sb, group, &e4b)) { 4092 ext4_error(sb, "Error loading buddy information for %u", 4093 group); 4094 continue; 4095 } 4096 ext4_lock_group(sb, group); 4097 list_del(&pa->pa_group_list); 4098 ext4_mb_release_group_pa(&e4b, pa); 4099 ext4_unlock_group(sb, group); 4100 4101 ext4_mb_unload_buddy(&e4b); 4102 list_del(&pa->u.pa_tmp_list); 4103 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback); 4104 } 4105 } 4106 4107 /* 4108 * We have incremented pa_count. So it cannot be freed at this 4109 * point. Also we hold lg_mutex. So no parallel allocation is 4110 * possible from this lg. That means pa_free cannot be updated. 4111 * 4112 * A parallel ext4_mb_discard_group_preallocations is possible. 4113 * which can cause the lg_prealloc_list to be updated. 4114 */ 4115 4116 static void ext4_mb_add_n_trim(struct ext4_allocation_context *ac) 4117 { 4118 int order, added = 0, lg_prealloc_count = 1; 4119 struct super_block *sb = ac->ac_sb; 4120 struct ext4_locality_group *lg = ac->ac_lg; 4121 struct ext4_prealloc_space *tmp_pa, *pa = ac->ac_pa; 4122 4123 order = fls(pa->pa_free) - 1; 4124 if (order > PREALLOC_TB_SIZE - 1) 4125 /* The max size of hash table is PREALLOC_TB_SIZE */ 4126 order = PREALLOC_TB_SIZE - 1; 4127 /* Add the prealloc space to lg */ 4128 rcu_read_lock(); 4129 list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[order], 4130 pa_inode_list) { 4131 spin_lock(&tmp_pa->pa_lock); 4132 if (tmp_pa->pa_deleted) { 4133 spin_unlock(&tmp_pa->pa_lock); 4134 continue; 4135 } 4136 if (!added && pa->pa_free < tmp_pa->pa_free) { 4137 /* Add to the tail of the previous entry */ 4138 list_add_tail_rcu(&pa->pa_inode_list, 4139 &tmp_pa->pa_inode_list); 4140 added = 1; 4141 /* 4142 * we want to count the total 4143 * number of entries in the list 4144 */ 4145 } 4146 spin_unlock(&tmp_pa->pa_lock); 4147 lg_prealloc_count++; 4148 } 4149 if (!added) 4150 list_add_tail_rcu(&pa->pa_inode_list, 4151 &lg->lg_prealloc_list[order]); 4152 rcu_read_unlock(); 4153 4154 /* Now trim the list to be not more than 8 elements */ 4155 if (lg_prealloc_count > 8) { 4156 ext4_mb_discard_lg_preallocations(sb, lg, 4157 order, lg_prealloc_count); 4158 return; 4159 } 4160 return ; 4161 } 4162 4163 /* 4164 * release all resource we used in allocation 4165 */ 4166 static int ext4_mb_release_context(struct ext4_allocation_context *ac) 4167 { 4168 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb); 4169 struct ext4_prealloc_space *pa = ac->ac_pa; 4170 if (pa) { 4171 if (pa->pa_type == MB_GROUP_PA) { 4172 /* see comment in ext4_mb_use_group_pa() */ 4173 spin_lock(&pa->pa_lock); 4174 pa->pa_pstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len); 4175 pa->pa_lstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len); 4176 pa->pa_free -= ac->ac_b_ex.fe_len; 4177 pa->pa_len -= ac->ac_b_ex.fe_len; 4178 spin_unlock(&pa->pa_lock); 4179 } 4180 } 4181 if (pa) { 4182 /* 4183 * We want to add the pa to the right bucket. 4184 * Remove it from the list and while adding 4185 * make sure the list to which we are adding 4186 * doesn't grow big. 4187 */ 4188 if ((pa->pa_type == MB_GROUP_PA) && likely(pa->pa_free)) { 4189 spin_lock(pa->pa_obj_lock); 4190 list_del_rcu(&pa->pa_inode_list); 4191 spin_unlock(pa->pa_obj_lock); 4192 ext4_mb_add_n_trim(ac); 4193 } 4194 ext4_mb_put_pa(ac, ac->ac_sb, pa); 4195 } 4196 if (ac->ac_bitmap_page) 4197 page_cache_release(ac->ac_bitmap_page); 4198 if (ac->ac_buddy_page) 4199 page_cache_release(ac->ac_buddy_page); 4200 if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) 4201 mutex_unlock(&ac->ac_lg->lg_mutex); 4202 ext4_mb_collect_stats(ac); 4203 return 0; 4204 } 4205 4206 static int ext4_mb_discard_preallocations(struct super_block *sb, int needed) 4207 { 4208 ext4_group_t i, ngroups = ext4_get_groups_count(sb); 4209 int ret; 4210 int freed = 0; 4211 4212 trace_ext4_mb_discard_preallocations(sb, needed); 4213 for (i = 0; i < ngroups && needed > 0; i++) { 4214 ret = ext4_mb_discard_group_preallocations(sb, i, needed); 4215 freed += ret; 4216 needed -= ret; 4217 } 4218 4219 return freed; 4220 } 4221 4222 /* 4223 * Main entry point into mballoc to allocate blocks 4224 * it tries to use preallocation first, then falls back 4225 * to usual allocation 4226 */ 4227 ext4_fsblk_t ext4_mb_new_blocks(handle_t *handle, 4228 struct ext4_allocation_request *ar, int *errp) 4229 { 4230 int freed; 4231 struct ext4_allocation_context *ac = NULL; 4232 struct ext4_sb_info *sbi; 4233 struct super_block *sb; 4234 ext4_fsblk_t block = 0; 4235 unsigned int inquota = 0; 4236 unsigned int reserv_clstrs = 0; 4237 4238 sb = ar->inode->i_sb; 4239 sbi = EXT4_SB(sb); 4240 4241 trace_ext4_request_blocks(ar); 4242 4243 /* Allow to use superuser reservation for quota file */ 4244 if (IS_NOQUOTA(ar->inode)) 4245 ar->flags |= EXT4_MB_USE_ROOT_BLOCKS; 4246 4247 /* 4248 * For delayed allocation, we could skip the ENOSPC and 4249 * EDQUOT check, as blocks and quotas have been already 4250 * reserved when data being copied into pagecache. 4251 */ 4252 if (ext4_test_inode_state(ar->inode, EXT4_STATE_DELALLOC_RESERVED)) 4253 ar->flags |= EXT4_MB_DELALLOC_RESERVED; 4254 else { 4255 /* Without delayed allocation we need to verify 4256 * there is enough free blocks to do block allocation 4257 * and verify allocation doesn't exceed the quota limits. 4258 */ 4259 while (ar->len && 4260 ext4_claim_free_clusters(sbi, ar->len, ar->flags)) { 4261 4262 /* let others to free the space */ 4263 yield(); 4264 ar->len = ar->len >> 1; 4265 } 4266 if (!ar->len) { 4267 *errp = -ENOSPC; 4268 return 0; 4269 } 4270 reserv_clstrs = ar->len; 4271 if (ar->flags & EXT4_MB_USE_ROOT_BLOCKS) { 4272 dquot_alloc_block_nofail(ar->inode, 4273 EXT4_C2B(sbi, ar->len)); 4274 } else { 4275 while (ar->len && 4276 dquot_alloc_block(ar->inode, 4277 EXT4_C2B(sbi, ar->len))) { 4278 4279 ar->flags |= EXT4_MB_HINT_NOPREALLOC; 4280 ar->len--; 4281 } 4282 } 4283 inquota = ar->len; 4284 if (ar->len == 0) { 4285 *errp = -EDQUOT; 4286 goto out; 4287 } 4288 } 4289 4290 ac = kmem_cache_alloc(ext4_ac_cachep, GFP_NOFS); 4291 if (!ac) { 4292 ar->len = 0; 4293 *errp = -ENOMEM; 4294 goto out; 4295 } 4296 4297 *errp = ext4_mb_initialize_context(ac, ar); 4298 if (*errp) { 4299 ar->len = 0; 4300 goto out; 4301 } 4302 4303 ac->ac_op = EXT4_MB_HISTORY_PREALLOC; 4304 if (!ext4_mb_use_preallocated(ac)) { 4305 ac->ac_op = EXT4_MB_HISTORY_ALLOC; 4306 ext4_mb_normalize_request(ac, ar); 4307 repeat: 4308 /* allocate space in core */ 4309 *errp = ext4_mb_regular_allocator(ac); 4310 if (*errp) 4311 goto errout; 4312 4313 /* as we've just preallocated more space than 4314 * user requested orinally, we store allocated 4315 * space in a special descriptor */ 4316 if (ac->ac_status == AC_STATUS_FOUND && 4317 ac->ac_o_ex.fe_len < ac->ac_b_ex.fe_len) 4318 ext4_mb_new_preallocation(ac); 4319 } 4320 if (likely(ac->ac_status == AC_STATUS_FOUND)) { 4321 *errp = ext4_mb_mark_diskspace_used(ac, handle, reserv_clstrs); 4322 if (*errp == -EAGAIN) { 4323 /* 4324 * drop the reference that we took 4325 * in ext4_mb_use_best_found 4326 */ 4327 ext4_mb_release_context(ac); 4328 ac->ac_b_ex.fe_group = 0; 4329 ac->ac_b_ex.fe_start = 0; 4330 ac->ac_b_ex.fe_len = 0; 4331 ac->ac_status = AC_STATUS_CONTINUE; 4332 goto repeat; 4333 } else if (*errp) 4334 errout: 4335 ext4_discard_allocated_blocks(ac); 4336 else { 4337 block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex); 4338 ar->len = ac->ac_b_ex.fe_len; 4339 } 4340 } else { 4341 freed = ext4_mb_discard_preallocations(sb, ac->ac_o_ex.fe_len); 4342 if (freed) 4343 goto repeat; 4344 *errp = -ENOSPC; 4345 } 4346 4347 if (*errp) { 4348 ac->ac_b_ex.fe_len = 0; 4349 ar->len = 0; 4350 ext4_mb_show_ac(ac); 4351 } 4352 ext4_mb_release_context(ac); 4353 out: 4354 if (ac) 4355 kmem_cache_free(ext4_ac_cachep, ac); 4356 if (inquota && ar->len < inquota) 4357 dquot_free_block(ar->inode, EXT4_C2B(sbi, inquota - ar->len)); 4358 if (!ar->len) { 4359 if (!ext4_test_inode_state(ar->inode, 4360 EXT4_STATE_DELALLOC_RESERVED)) 4361 /* release all the reserved blocks if non delalloc */ 4362 percpu_counter_sub(&sbi->s_dirtyclusters_counter, 4363 reserv_clstrs); 4364 } 4365 4366 trace_ext4_allocate_blocks(ar, (unsigned long long)block); 4367 4368 return block; 4369 } 4370 4371 /* 4372 * We can merge two free data extents only if the physical blocks 4373 * are contiguous, AND the extents were freed by the same transaction, 4374 * AND the blocks are associated with the same group. 4375 */ 4376 static int can_merge(struct ext4_free_data *entry1, 4377 struct ext4_free_data *entry2) 4378 { 4379 if ((entry1->efd_tid == entry2->efd_tid) && 4380 (entry1->efd_group == entry2->efd_group) && 4381 ((entry1->efd_start_cluster + entry1->efd_count) == entry2->efd_start_cluster)) 4382 return 1; 4383 return 0; 4384 } 4385 4386 static noinline_for_stack int 4387 ext4_mb_free_metadata(handle_t *handle, struct ext4_buddy *e4b, 4388 struct ext4_free_data *new_entry) 4389 { 4390 ext4_group_t group = e4b->bd_group; 4391 ext4_grpblk_t cluster; 4392 struct ext4_free_data *entry; 4393 struct ext4_group_info *db = e4b->bd_info; 4394 struct super_block *sb = e4b->bd_sb; 4395 struct ext4_sb_info *sbi = EXT4_SB(sb); 4396 struct rb_node **n = &db->bb_free_root.rb_node, *node; 4397 struct rb_node *parent = NULL, *new_node; 4398 4399 BUG_ON(!ext4_handle_valid(handle)); 4400 BUG_ON(e4b->bd_bitmap_page == NULL); 4401 BUG_ON(e4b->bd_buddy_page == NULL); 4402 4403 new_node = &new_entry->efd_node; 4404 cluster = new_entry->efd_start_cluster; 4405 4406 if (!*n) { 4407 /* first free block exent. We need to 4408 protect buddy cache from being freed, 4409 * otherwise we'll refresh it from 4410 * on-disk bitmap and lose not-yet-available 4411 * blocks */ 4412 page_cache_get(e4b->bd_buddy_page); 4413 page_cache_get(e4b->bd_bitmap_page); 4414 } 4415 while (*n) { 4416 parent = *n; 4417 entry = rb_entry(parent, struct ext4_free_data, efd_node); 4418 if (cluster < entry->efd_start_cluster) 4419 n = &(*n)->rb_left; 4420 else if (cluster >= (entry->efd_start_cluster + entry->efd_count)) 4421 n = &(*n)->rb_right; 4422 else { 4423 ext4_grp_locked_error(sb, group, 0, 4424 ext4_group_first_block_no(sb, group) + 4425 EXT4_C2B(sbi, cluster), 4426 "Block already on to-be-freed list"); 4427 return 0; 4428 } 4429 } 4430 4431 rb_link_node(new_node, parent, n); 4432 rb_insert_color(new_node, &db->bb_free_root); 4433 4434 /* Now try to see the extent can be merged to left and right */ 4435 node = rb_prev(new_node); 4436 if (node) { 4437 entry = rb_entry(node, struct ext4_free_data, efd_node); 4438 if (can_merge(entry, new_entry)) { 4439 new_entry->efd_start_cluster = entry->efd_start_cluster; 4440 new_entry->efd_count += entry->efd_count; 4441 rb_erase(node, &(db->bb_free_root)); 4442 ext4_journal_callback_del(handle, &entry->efd_jce); 4443 kmem_cache_free(ext4_free_data_cachep, entry); 4444 } 4445 } 4446 4447 node = rb_next(new_node); 4448 if (node) { 4449 entry = rb_entry(node, struct ext4_free_data, efd_node); 4450 if (can_merge(new_entry, entry)) { 4451 new_entry->efd_count += entry->efd_count; 4452 rb_erase(node, &(db->bb_free_root)); 4453 ext4_journal_callback_del(handle, &entry->efd_jce); 4454 kmem_cache_free(ext4_free_data_cachep, entry); 4455 } 4456 } 4457 /* Add the extent to transaction's private list */ 4458 ext4_journal_callback_add(handle, ext4_free_data_callback, 4459 &new_entry->efd_jce); 4460 return 0; 4461 } 4462 4463 /** 4464 * ext4_free_blocks() -- Free given blocks and update quota 4465 * @handle: handle for this transaction 4466 * @inode: inode 4467 * @block: start physical block to free 4468 * @count: number of blocks to count 4469 * @flags: flags used by ext4_free_blocks 4470 */ 4471 void ext4_free_blocks(handle_t *handle, struct inode *inode, 4472 struct buffer_head *bh, ext4_fsblk_t block, 4473 unsigned long count, int flags) 4474 { 4475 struct buffer_head *bitmap_bh = NULL; 4476 struct super_block *sb = inode->i_sb; 4477 struct ext4_group_desc *gdp; 4478 unsigned long freed = 0; 4479 unsigned int overflow; 4480 ext4_grpblk_t bit; 4481 struct buffer_head *gd_bh; 4482 ext4_group_t block_group; 4483 struct ext4_sb_info *sbi; 4484 struct ext4_buddy e4b; 4485 unsigned int count_clusters; 4486 int err = 0; 4487 int ret; 4488 4489 if (bh) { 4490 if (block) 4491 BUG_ON(block != bh->b_blocknr); 4492 else 4493 block = bh->b_blocknr; 4494 } 4495 4496 sbi = EXT4_SB(sb); 4497 if (!(flags & EXT4_FREE_BLOCKS_VALIDATED) && 4498 !ext4_data_block_valid(sbi, block, count)) { 4499 ext4_error(sb, "Freeing blocks not in datazone - " 4500 "block = %llu, count = %lu", block, count); 4501 goto error_return; 4502 } 4503 4504 ext4_debug("freeing block %llu\n", block); 4505 trace_ext4_free_blocks(inode, block, count, flags); 4506 4507 if (flags & EXT4_FREE_BLOCKS_FORGET) { 4508 struct buffer_head *tbh = bh; 4509 int i; 4510 4511 BUG_ON(bh && (count > 1)); 4512 4513 for (i = 0; i < count; i++) { 4514 if (!bh) 4515 tbh = sb_find_get_block(inode->i_sb, 4516 block + i); 4517 if (unlikely(!tbh)) 4518 continue; 4519 ext4_forget(handle, flags & EXT4_FREE_BLOCKS_METADATA, 4520 inode, tbh, block + i); 4521 } 4522 } 4523 4524 /* 4525 * We need to make sure we don't reuse the freed block until 4526 * after the transaction is committed, which we can do by 4527 * treating the block as metadata, below. We make an 4528 * exception if the inode is to be written in writeback mode 4529 * since writeback mode has weak data consistency guarantees. 4530 */ 4531 if (!ext4_should_writeback_data(inode)) 4532 flags |= EXT4_FREE_BLOCKS_METADATA; 4533 4534 /* 4535 * If the extent to be freed does not begin on a cluster 4536 * boundary, we need to deal with partial clusters at the 4537 * beginning and end of the extent. Normally we will free 4538 * blocks at the beginning or the end unless we are explicitly 4539 * requested to avoid doing so. 4540 */ 4541 overflow = block & (sbi->s_cluster_ratio - 1); 4542 if (overflow) { 4543 if (flags & EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER) { 4544 overflow = sbi->s_cluster_ratio - overflow; 4545 block += overflow; 4546 if (count > overflow) 4547 count -= overflow; 4548 else 4549 return; 4550 } else { 4551 block -= overflow; 4552 count += overflow; 4553 } 4554 } 4555 overflow = count & (sbi->s_cluster_ratio - 1); 4556 if (overflow) { 4557 if (flags & EXT4_FREE_BLOCKS_NOFREE_LAST_CLUSTER) { 4558 if (count > overflow) 4559 count -= overflow; 4560 else 4561 return; 4562 } else 4563 count += sbi->s_cluster_ratio - overflow; 4564 } 4565 4566 do_more: 4567 overflow = 0; 4568 ext4_get_group_no_and_offset(sb, block, &block_group, &bit); 4569 4570 /* 4571 * Check to see if we are freeing blocks across a group 4572 * boundary. 4573 */ 4574 if (EXT4_C2B(sbi, bit) + count > EXT4_BLOCKS_PER_GROUP(sb)) { 4575 overflow = EXT4_C2B(sbi, bit) + count - 4576 EXT4_BLOCKS_PER_GROUP(sb); 4577 count -= overflow; 4578 } 4579 count_clusters = EXT4_B2C(sbi, count); 4580 bitmap_bh = ext4_read_block_bitmap(sb, block_group); 4581 if (!bitmap_bh) { 4582 err = -EIO; 4583 goto error_return; 4584 } 4585 gdp = ext4_get_group_desc(sb, block_group, &gd_bh); 4586 if (!gdp) { 4587 err = -EIO; 4588 goto error_return; 4589 } 4590 4591 if (in_range(ext4_block_bitmap(sb, gdp), block, count) || 4592 in_range(ext4_inode_bitmap(sb, gdp), block, count) || 4593 in_range(block, ext4_inode_table(sb, gdp), 4594 EXT4_SB(sb)->s_itb_per_group) || 4595 in_range(block + count - 1, ext4_inode_table(sb, gdp), 4596 EXT4_SB(sb)->s_itb_per_group)) { 4597 4598 ext4_error(sb, "Freeing blocks in system zone - " 4599 "Block = %llu, count = %lu", block, count); 4600 /* err = 0. ext4_std_error should be a no op */ 4601 goto error_return; 4602 } 4603 4604 BUFFER_TRACE(bitmap_bh, "getting write access"); 4605 err = ext4_journal_get_write_access(handle, bitmap_bh); 4606 if (err) 4607 goto error_return; 4608 4609 /* 4610 * We are about to modify some metadata. Call the journal APIs 4611 * to unshare ->b_data if a currently-committing transaction is 4612 * using it 4613 */ 4614 BUFFER_TRACE(gd_bh, "get_write_access"); 4615 err = ext4_journal_get_write_access(handle, gd_bh); 4616 if (err) 4617 goto error_return; 4618 #ifdef AGGRESSIVE_CHECK 4619 { 4620 int i; 4621 for (i = 0; i < count_clusters; i++) 4622 BUG_ON(!mb_test_bit(bit + i, bitmap_bh->b_data)); 4623 } 4624 #endif 4625 trace_ext4_mballoc_free(sb, inode, block_group, bit, count_clusters); 4626 4627 err = ext4_mb_load_buddy(sb, block_group, &e4b); 4628 if (err) 4629 goto error_return; 4630 4631 if ((flags & EXT4_FREE_BLOCKS_METADATA) && ext4_handle_valid(handle)) { 4632 struct ext4_free_data *new_entry; 4633 /* 4634 * blocks being freed are metadata. these blocks shouldn't 4635 * be used until this transaction is committed 4636 */ 4637 new_entry = kmem_cache_alloc(ext4_free_data_cachep, GFP_NOFS); 4638 if (!new_entry) { 4639 err = -ENOMEM; 4640 goto error_return; 4641 } 4642 new_entry->efd_start_cluster = bit; 4643 new_entry->efd_group = block_group; 4644 new_entry->efd_count = count_clusters; 4645 new_entry->efd_tid = handle->h_transaction->t_tid; 4646 4647 ext4_lock_group(sb, block_group); 4648 mb_clear_bits(bitmap_bh->b_data, bit, count_clusters); 4649 ext4_mb_free_metadata(handle, &e4b, new_entry); 4650 } else { 4651 /* need to update group_info->bb_free and bitmap 4652 * with group lock held. generate_buddy look at 4653 * them with group lock_held 4654 */ 4655 ext4_lock_group(sb, block_group); 4656 mb_clear_bits(bitmap_bh->b_data, bit, count_clusters); 4657 mb_free_blocks(inode, &e4b, bit, count_clusters); 4658 } 4659 4660 ret = ext4_free_group_clusters(sb, gdp) + count_clusters; 4661 ext4_free_group_clusters_set(sb, gdp, ret); 4662 gdp->bg_checksum = ext4_group_desc_csum(sbi, block_group, gdp); 4663 ext4_unlock_group(sb, block_group); 4664 percpu_counter_add(&sbi->s_freeclusters_counter, count_clusters); 4665 4666 if (sbi->s_log_groups_per_flex) { 4667 ext4_group_t flex_group = ext4_flex_group(sbi, block_group); 4668 atomic_add(count_clusters, 4669 &sbi->s_flex_groups[flex_group].free_clusters); 4670 } 4671 4672 ext4_mb_unload_buddy(&e4b); 4673 4674 freed += count; 4675 4676 if (!(flags & EXT4_FREE_BLOCKS_NO_QUOT_UPDATE)) 4677 dquot_free_block(inode, EXT4_C2B(sbi, count_clusters)); 4678 4679 /* We dirtied the bitmap block */ 4680 BUFFER_TRACE(bitmap_bh, "dirtied bitmap block"); 4681 err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh); 4682 4683 /* And the group descriptor block */ 4684 BUFFER_TRACE(gd_bh, "dirtied group descriptor block"); 4685 ret = ext4_handle_dirty_metadata(handle, NULL, gd_bh); 4686 if (!err) 4687 err = ret; 4688 4689 if (overflow && !err) { 4690 block += count; 4691 count = overflow; 4692 put_bh(bitmap_bh); 4693 goto do_more; 4694 } 4695 ext4_mark_super_dirty(sb); 4696 error_return: 4697 brelse(bitmap_bh); 4698 ext4_std_error(sb, err); 4699 return; 4700 } 4701 4702 /** 4703 * ext4_group_add_blocks() -- Add given blocks to an existing group 4704 * @handle: handle to this transaction 4705 * @sb: super block 4706 * @block: start physcial block to add to the block group 4707 * @count: number of blocks to free 4708 * 4709 * This marks the blocks as free in the bitmap and buddy. 4710 */ 4711 int ext4_group_add_blocks(handle_t *handle, struct super_block *sb, 4712 ext4_fsblk_t block, unsigned long count) 4713 { 4714 struct buffer_head *bitmap_bh = NULL; 4715 struct buffer_head *gd_bh; 4716 ext4_group_t block_group; 4717 ext4_grpblk_t bit; 4718 unsigned int i; 4719 struct ext4_group_desc *desc; 4720 struct ext4_sb_info *sbi = EXT4_SB(sb); 4721 struct ext4_buddy e4b; 4722 int err = 0, ret, blk_free_count; 4723 ext4_grpblk_t blocks_freed; 4724 4725 ext4_debug("Adding block(s) %llu-%llu\n", block, block + count - 1); 4726 4727 if (count == 0) 4728 return 0; 4729 4730 ext4_get_group_no_and_offset(sb, block, &block_group, &bit); 4731 /* 4732 * Check to see if we are freeing blocks across a group 4733 * boundary. 4734 */ 4735 if (bit + count > EXT4_BLOCKS_PER_GROUP(sb)) { 4736 ext4_warning(sb, "too much blocks added to group %u\n", 4737 block_group); 4738 err = -EINVAL; 4739 goto error_return; 4740 } 4741 4742 bitmap_bh = ext4_read_block_bitmap(sb, block_group); 4743 if (!bitmap_bh) { 4744 err = -EIO; 4745 goto error_return; 4746 } 4747 4748 desc = ext4_get_group_desc(sb, block_group, &gd_bh); 4749 if (!desc) { 4750 err = -EIO; 4751 goto error_return; 4752 } 4753 4754 if (in_range(ext4_block_bitmap(sb, desc), block, count) || 4755 in_range(ext4_inode_bitmap(sb, desc), block, count) || 4756 in_range(block, ext4_inode_table(sb, desc), sbi->s_itb_per_group) || 4757 in_range(block + count - 1, ext4_inode_table(sb, desc), 4758 sbi->s_itb_per_group)) { 4759 ext4_error(sb, "Adding blocks in system zones - " 4760 "Block = %llu, count = %lu", 4761 block, count); 4762 err = -EINVAL; 4763 goto error_return; 4764 } 4765 4766 BUFFER_TRACE(bitmap_bh, "getting write access"); 4767 err = ext4_journal_get_write_access(handle, bitmap_bh); 4768 if (err) 4769 goto error_return; 4770 4771 /* 4772 * We are about to modify some metadata. Call the journal APIs 4773 * to unshare ->b_data if a currently-committing transaction is 4774 * using it 4775 */ 4776 BUFFER_TRACE(gd_bh, "get_write_access"); 4777 err = ext4_journal_get_write_access(handle, gd_bh); 4778 if (err) 4779 goto error_return; 4780 4781 for (i = 0, blocks_freed = 0; i < count; i++) { 4782 BUFFER_TRACE(bitmap_bh, "clear bit"); 4783 if (!mb_test_bit(bit + i, bitmap_bh->b_data)) { 4784 ext4_error(sb, "bit already cleared for block %llu", 4785 (ext4_fsblk_t)(block + i)); 4786 BUFFER_TRACE(bitmap_bh, "bit already cleared"); 4787 } else { 4788 blocks_freed++; 4789 } 4790 } 4791 4792 err = ext4_mb_load_buddy(sb, block_group, &e4b); 4793 if (err) 4794 goto error_return; 4795 4796 /* 4797 * need to update group_info->bb_free and bitmap 4798 * with group lock held. generate_buddy look at 4799 * them with group lock_held 4800 */ 4801 ext4_lock_group(sb, block_group); 4802 mb_clear_bits(bitmap_bh->b_data, bit, count); 4803 mb_free_blocks(NULL, &e4b, bit, count); 4804 blk_free_count = blocks_freed + ext4_free_group_clusters(sb, desc); 4805 ext4_free_group_clusters_set(sb, desc, blk_free_count); 4806 desc->bg_checksum = ext4_group_desc_csum(sbi, block_group, desc); 4807 ext4_unlock_group(sb, block_group); 4808 percpu_counter_add(&sbi->s_freeclusters_counter, 4809 EXT4_B2C(sbi, blocks_freed)); 4810 4811 if (sbi->s_log_groups_per_flex) { 4812 ext4_group_t flex_group = ext4_flex_group(sbi, block_group); 4813 atomic_add(EXT4_B2C(sbi, blocks_freed), 4814 &sbi->s_flex_groups[flex_group].free_clusters); 4815 } 4816 4817 ext4_mb_unload_buddy(&e4b); 4818 4819 /* We dirtied the bitmap block */ 4820 BUFFER_TRACE(bitmap_bh, "dirtied bitmap block"); 4821 err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh); 4822 4823 /* And the group descriptor block */ 4824 BUFFER_TRACE(gd_bh, "dirtied group descriptor block"); 4825 ret = ext4_handle_dirty_metadata(handle, NULL, gd_bh); 4826 if (!err) 4827 err = ret; 4828 4829 error_return: 4830 brelse(bitmap_bh); 4831 ext4_std_error(sb, err); 4832 return err; 4833 } 4834 4835 /** 4836 * ext4_trim_extent -- function to TRIM one single free extent in the group 4837 * @sb: super block for the file system 4838 * @start: starting block of the free extent in the alloc. group 4839 * @count: number of blocks to TRIM 4840 * @group: alloc. group we are working with 4841 * @e4b: ext4 buddy for the group 4842 * 4843 * Trim "count" blocks starting at "start" in the "group". To assure that no 4844 * one will allocate those blocks, mark it as used in buddy bitmap. This must 4845 * be called with under the group lock. 4846 */ 4847 static void ext4_trim_extent(struct super_block *sb, int start, int count, 4848 ext4_group_t group, struct ext4_buddy *e4b) 4849 { 4850 struct ext4_free_extent ex; 4851 4852 trace_ext4_trim_extent(sb, group, start, count); 4853 4854 assert_spin_locked(ext4_group_lock_ptr(sb, group)); 4855 4856 ex.fe_start = start; 4857 ex.fe_group = group; 4858 ex.fe_len = count; 4859 4860 /* 4861 * Mark blocks used, so no one can reuse them while 4862 * being trimmed. 4863 */ 4864 mb_mark_used(e4b, &ex); 4865 ext4_unlock_group(sb, group); 4866 ext4_issue_discard(sb, group, start, count); 4867 ext4_lock_group(sb, group); 4868 mb_free_blocks(NULL, e4b, start, ex.fe_len); 4869 } 4870 4871 /** 4872 * ext4_trim_all_free -- function to trim all free space in alloc. group 4873 * @sb: super block for file system 4874 * @group: group to be trimmed 4875 * @start: first group block to examine 4876 * @max: last group block to examine 4877 * @minblocks: minimum extent block count 4878 * 4879 * ext4_trim_all_free walks through group's buddy bitmap searching for free 4880 * extents. When the free block is found, ext4_trim_extent is called to TRIM 4881 * the extent. 4882 * 4883 * 4884 * ext4_trim_all_free walks through group's block bitmap searching for free 4885 * extents. When the free extent is found, mark it as used in group buddy 4886 * bitmap. Then issue a TRIM command on this extent and free the extent in 4887 * the group buddy bitmap. This is done until whole group is scanned. 4888 */ 4889 static ext4_grpblk_t 4890 ext4_trim_all_free(struct super_block *sb, ext4_group_t group, 4891 ext4_grpblk_t start, ext4_grpblk_t max, 4892 ext4_grpblk_t minblocks) 4893 { 4894 void *bitmap; 4895 ext4_grpblk_t next, count = 0, free_count = 0; 4896 struct ext4_buddy e4b; 4897 int ret; 4898 4899 trace_ext4_trim_all_free(sb, group, start, max); 4900 4901 ret = ext4_mb_load_buddy(sb, group, &e4b); 4902 if (ret) { 4903 ext4_error(sb, "Error in loading buddy " 4904 "information for %u", group); 4905 return ret; 4906 } 4907 bitmap = e4b.bd_bitmap; 4908 4909 ext4_lock_group(sb, group); 4910 if (EXT4_MB_GRP_WAS_TRIMMED(e4b.bd_info) && 4911 minblocks >= atomic_read(&EXT4_SB(sb)->s_last_trim_minblks)) 4912 goto out; 4913 4914 start = (e4b.bd_info->bb_first_free > start) ? 4915 e4b.bd_info->bb_first_free : start; 4916 4917 while (start <= max) { 4918 start = mb_find_next_zero_bit(bitmap, max + 1, start); 4919 if (start > max) 4920 break; 4921 next = mb_find_next_bit(bitmap, max + 1, start); 4922 4923 if ((next - start) >= minblocks) { 4924 ext4_trim_extent(sb, start, 4925 next - start, group, &e4b); 4926 count += next - start; 4927 } 4928 free_count += next - start; 4929 start = next + 1; 4930 4931 if (fatal_signal_pending(current)) { 4932 count = -ERESTARTSYS; 4933 break; 4934 } 4935 4936 if (need_resched()) { 4937 ext4_unlock_group(sb, group); 4938 cond_resched(); 4939 ext4_lock_group(sb, group); 4940 } 4941 4942 if ((e4b.bd_info->bb_free - free_count) < minblocks) 4943 break; 4944 } 4945 4946 if (!ret) 4947 EXT4_MB_GRP_SET_TRIMMED(e4b.bd_info); 4948 out: 4949 ext4_unlock_group(sb, group); 4950 ext4_mb_unload_buddy(&e4b); 4951 4952 ext4_debug("trimmed %d blocks in the group %d\n", 4953 count, group); 4954 4955 return count; 4956 } 4957 4958 /** 4959 * ext4_trim_fs() -- trim ioctl handle function 4960 * @sb: superblock for filesystem 4961 * @range: fstrim_range structure 4962 * 4963 * start: First Byte to trim 4964 * len: number of Bytes to trim from start 4965 * minlen: minimum extent length in Bytes 4966 * ext4_trim_fs goes through all allocation groups containing Bytes from 4967 * start to start+len. For each such a group ext4_trim_all_free function 4968 * is invoked to trim all free space. 4969 */ 4970 int ext4_trim_fs(struct super_block *sb, struct fstrim_range *range) 4971 { 4972 struct ext4_group_info *grp; 4973 ext4_group_t group, first_group, last_group; 4974 ext4_grpblk_t cnt = 0, first_cluster, last_cluster; 4975 uint64_t start, end, minlen, trimmed = 0; 4976 ext4_fsblk_t first_data_blk = 4977 le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block); 4978 ext4_fsblk_t max_blks = ext4_blocks_count(EXT4_SB(sb)->s_es); 4979 int ret = 0; 4980 4981 start = range->start >> sb->s_blocksize_bits; 4982 end = start + (range->len >> sb->s_blocksize_bits) - 1; 4983 minlen = range->minlen >> sb->s_blocksize_bits; 4984 4985 if (unlikely(minlen > EXT4_CLUSTERS_PER_GROUP(sb)) || 4986 unlikely(start >= max_blks)) 4987 return -EINVAL; 4988 if (end >= max_blks) 4989 end = max_blks - 1; 4990 if (end <= first_data_blk) 4991 goto out; 4992 if (start < first_data_blk) 4993 start = first_data_blk; 4994 4995 /* Determine first and last group to examine based on start and end */ 4996 ext4_get_group_no_and_offset(sb, (ext4_fsblk_t) start, 4997 &first_group, &first_cluster); 4998 ext4_get_group_no_and_offset(sb, (ext4_fsblk_t) end, 4999 &last_group, &last_cluster); 5000 5001 /* end now represents the last cluster to discard in this group */ 5002 end = EXT4_CLUSTERS_PER_GROUP(sb) - 1; 5003 5004 for (group = first_group; group <= last_group; group++) { 5005 grp = ext4_get_group_info(sb, group); 5006 /* We only do this if the grp has never been initialized */ 5007 if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) { 5008 ret = ext4_mb_init_group(sb, group); 5009 if (ret) 5010 break; 5011 } 5012 5013 /* 5014 * For all the groups except the last one, last cluster will 5015 * always be EXT4_CLUSTERS_PER_GROUP(sb)-1, so we only need to 5016 * change it for the last group, note that last_cluster is 5017 * already computed earlier by ext4_get_group_no_and_offset() 5018 */ 5019 if (group == last_group) 5020 end = last_cluster; 5021 5022 if (grp->bb_free >= minlen) { 5023 cnt = ext4_trim_all_free(sb, group, first_cluster, 5024 end, minlen); 5025 if (cnt < 0) { 5026 ret = cnt; 5027 break; 5028 } 5029 trimmed += cnt; 5030 } 5031 5032 /* 5033 * For every group except the first one, we are sure 5034 * that the first cluster to discard will be cluster #0. 5035 */ 5036 first_cluster = 0; 5037 } 5038 5039 if (!ret) 5040 atomic_set(&EXT4_SB(sb)->s_last_trim_minblks, minlen); 5041 5042 out: 5043 range->len = trimmed * sb->s_blocksize; 5044 return ret; 5045 } 5046