Lines Matching +full:trim +full:- +full:data +full:- +full:valid
1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
18 #include <linux/backing-dev.h>
25 * - test ext4_ext_search_left() and ext4_ext_search_right()
26 * - search for metadata in few groups
29 * - normalization should take into account whether file is still open
30 * - discard preallocations if no free space left (policy?)
31 * - don't normalize tails
32 * - quota
33 * - reservation for superuser
36 * - bitmap read-ahead (proposed by Oleg Drokin aka green)
37 * - track min/max extents in each group for better group selection
38 * - mb_mark_used() may allocate chunk right after splitting buddy
39 * - tree of groups sorted by number of free blocks
40 * - error handling
51 * is larger. If the size is less than sbi->s_mb_stream_request we
61 * ext4_inode_info->i_prealloc_list, which contains list of prealloc
65 * pa_lstart -> the logical start block for this prealloc space
66 * pa_pstart -> the physical start block for this prealloc space
67 * pa_len -> length for this prealloc space (in clusters)
68 * pa_free -> free space available in this prealloc space (in clusters)
123 * sbi->s_mb_group_prealloc. The default value of s_mb_group_prealloc is
124 * dependent on the cluster size; for non-bigalloc file systems, it is
127 * terms of number of blocks. If we have mounted the file system with -O
129 * smallest multiple of the stripe value (sbi->s_stripe) which is
133 * structures in two data structures:
135 * 1) Array of largest free order xarrays (sbi->s_mb_largest_free_orders)
142 * number of buddy bitmap orders possible) number of xarrays. Group-infos are
145 * 2) Average fragment size xarrays (sbi->s_mb_avg_fragment_size)
149 * This is an array of xarrays where in the i-th xarray there are groups with
151 * is computed as ext4_group_info->bb_free / ext4_group_info->bb_fragments.
153 * groups so we only have MB_NUM_ORDERS(sb) xarrays. Group-infos are placed
157 * information, and a non-empty value indicates the block group is present in
160 * When "mb_optimize_scan" mount option is set, mballoc consults the above data
166 * in the data structure (1) above where largest_free_order = order of the
174 * size group lists (data structure 2) in O(1) time.
180 * CR_GOAL_LEN_SLOW, in CR_BEST_AVAIL_LEN we proactively trim goal length and
198 * 2 blocks and the order of allocation is >= sbi->s_mb_order2_reqs. The
201 * stripe size (sbi->s_stripe), we try to search for contiguous block in
216 * non-linear fashion. While that may not matter on non-rotational devices, for
219 * performing consulting above data structures for more efficient lookups. For
230 * mballoc operates on the following data:
231 * - on-disk bitmap
232 * - in-core buddy (actually includes buddy and bitmap)
233 * - preallocation descriptors (PAs)
236 * - inode
245 * - locality group
252 * in-core buddy = on-disk bitmap + preallocation descriptors
255 * - allocated blocks (persistent)
256 * - preallocated blocks (non-persistent)
260 * literally -- time is discrete and delimited by locks.
263 * blocks: how many blocks marked used/free in on-disk bitmap, buddy and PA.
266 * - init buddy: buddy = on-disk + PAs
267 * - new PA: buddy += N; PA = N
268 * - use inode PA: on-disk += N; PA -= N
269 * - discard inode PA buddy -= on-disk - PA; PA = 0
270 * - use locality group PA on-disk += N; PA -= N
271 * - discard locality group PA buddy -= PA; PA = 0
272 * note: 'buddy -= on-disk - PA' is used to show that on-disk bitmap
274 * bits from PA, only from on-disk bitmap
278 * killing performance on high-end SMP hardware. let's try to relax it using
282 * nobody can re-allocate that block
283 * 3) we work on bitmaps and '+' actually means 'set bits'. if on-disk has
285 * on-disk bitmap if buddy has same bit set or/and PA covers corresponded
289 * - init buddy vs.
290 * - new PA
293 * - use inode PA
294 * we need to make sure that either on-disk bitmap or PA has uptodate data
295 * given (3) we care that PA-=N operation doesn't interfere with init
296 * - discard inode PA
298 * - use locality group PA
299 * again PA-=N must be serialized with init
300 * - discard locality group PA
302 * - new PA vs.
303 * - use inode PA
305 * - discard inode PA
307 * - use locality group PA
309 * - discard locality group PA
311 * - use inode PA
312 * - use inode PA
314 * - discard inode PA
316 * - use locality group PA
317 * nothing wrong here -- they're different PAs covering different blocks
318 * - discard locality group PA
322 * - PA is referenced and while it is no discard is possible
323 * - PA is referenced until block isn't marked in on-disk bitmap
324 * - PA changes only after on-disk bitmap
325 * - discard must not compete with init. either init is done before
327 * - buddy init as sum of on-disk bitmap and PAs is done atomically
337 * - allocation:
340 * mark bits in on-disk bitmap
343 * - use preallocation:
344 * find proper PA (per-inode or group)
346 * mark bits in on-disk bitmap
350 * - free:
352 * mark bits in on-disk bitmap
355 * - discard preallocations in group:
358 * load on-disk bitmap
361 * mark free blocks in-core
363 * - discard inode's preallocations:
370 * - bitlock on a group (group)
371 * - object (inode/locality) (object)
372 * - per-pa lock (pa)
373 * - cr_power2_aligned lists lock (cr_power2_aligned)
374 * - cr_goal_len_fast lists lock (cr_goal_len_fast)
377 * - new pa
381 * - find and use pa:
384 * - release consumed pa:
389 * - generate in-core bitmap:
393 * - discard all for given object (inode, locality group):
398 * - discard all for given group:
404 * - allocation path (ext4_mb_regular_allocator)
412 /* We create slab caches for groupinfo data structures based on the
451 * sure that all the PAs on grp->bb_prealloc_list got freed or if it's empty.
513 ret = ext4_find_next_zero_bit(addr, tmpmax, start) - fix;
526 ret = ext4_find_next_bit(addr, tmpmax, start) - fix;
536 BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);
539 if (order > e4b->bd_blkbits + 1) {
546 *max = 1 << (e4b->bd_blkbits + 3);
547 return e4b->bd_bitmap;
550 bb = e4b->bd_buddy + EXT4_SB(e4b->bd_sb)->s_mb_offsets[order];
551 *max = EXT4_SB(e4b->bd_sb)->s_mb_maxs[order];
561 struct super_block *sb = e4b->bd_sb;
563 if (unlikely(e4b->bd_info->bb_bitmap == NULL))
565 assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));
567 if (!mb_test_bit(first + i, e4b->bd_info->bb_bitmap)) {
570 blocknr = ext4_group_first_block_no(sb, e4b->bd_group);
572 ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,
574 ext4_grp_locked_error(sb, e4b->bd_group,
575 inode ? inode->i_ino : 0,
581 mb_clear_bit(first + i, e4b->bd_info->bb_bitmap);
589 if (unlikely(e4b->bd_info->bb_bitmap == NULL))
591 assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
593 BUG_ON(mb_test_bit(first + i, e4b->bd_info->bb_bitmap));
594 mb_set_bit(first + i, e4b->bd_info->bb_bitmap);
600 if (unlikely(e4b->bd_info->bb_bitmap == NULL))
602 if (memcmp(e4b->bd_info->bb_bitmap, bitmap, e4b->bd_sb->s_blocksize)) {
605 b1 = (unsigned char *) e4b->bd_info->bb_bitmap;
607 for (i = 0; i < e4b->bd_sb->s_blocksize; i++) {
609 ext4_msg(e4b->bd_sb, KERN_ERR,
613 e4b->bd_group, i, i * 8, b1[i], b2[i]);
625 grp->bb_bitmap = kmalloc(sb->s_blocksize, GFP_NOFS);
626 if (!grp->bb_bitmap)
631 kfree(grp->bb_bitmap);
632 grp->bb_bitmap = NULL;
636 memcpy(grp->bb_bitmap, bh->b_data, sb->s_blocksize);
642 kfree(grp->bb_bitmap);
688 * 1. Top-down validation (from highest order down to order 1, excluding order-0 bitmap):
689 * For each pair of adjacent orders, if a higher-order bit is set (indicating a free block),
690 * at most one of the two corresponding lower-order bits may be clear (free).
692 * 2. Order-0 (bitmap) validation, performed on bit pairs:
693 * - If either bit in a pair is set (1, allocated), then all corresponding higher-order bits
695 * - If both bits in a pair are clear (0, free), then exactly one of the corresponding
696 * higher-order bits must be free (0).
700 * - Verify that pa_pstart falls within the bounds of this block group.
701 * - Ensure the corresponding bit(s) in the order-0 bitmap are marked as allocated (1).
706 struct super_block *sb = e4b->bd_sb;
707 int order = e4b->bd_blkbits + 1;
721 if (e4b->bd_info->bb_check_counter++ % 10)
727 buddy2 = mb_find_buddy(e4b, order - 1, &max2);
746 MB_CHECK_ASSERT(e4b->bd_info->bb_counters[order] == count);
747 order--;
750 fstart = -1;
754 MB_CHECK_ASSERT(i >= e4b->bd_info->bb_first_free);
755 if (fstart == -1) {
760 fstart = -1;
766 for (j = 1; j < e4b->bd_blkbits + 2; j++) {
776 MB_CHECK_ASSERT(!EXT4_MB_GRP_NEED_INIT(e4b->bd_info));
777 MB_CHECK_ASSERT(e4b->bd_info->bb_fragments == fragments);
779 grp = ext4_get_group_info(sb, e4b->bd_group);
782 list_for_each(cur, &grp->bb_prealloc_list) {
786 if (!pa->pa_len)
788 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &groupnr, &k);
789 MB_CHECK_ASSERT(groupnr == e4b->bd_group);
790 for (i = 0; i < pa->pa_len; i++)
819 border = 2 << sb->s_blocksize_bits;
823 max = ffs(first | border) - 1;
826 min = fls(len) - 1;
833 grp->bb_counters[min]++;
836 buddy + sbi->s_mb_offsets[min]);
838 len -= chunk;
851 order = fls(len) - 2;
855 order--;
857 order = MB_NUM_ORDERS(sb) - 1;
871 old = grp->bb_avg_fragment_size_order;
872 new = grp->bb_fragments == 0 ? -1 :
873 mb_avg_fragment_size_order(sb, grp->bb_free / grp->bb_fragments);
878 xa_erase(&sbi->s_mb_avg_fragment_size[old], grp->bb_group);
880 grp->bb_avg_fragment_size_order = new;
887 int err = xa_insert(&sbi->s_mb_avg_fragment_size[new],
888 grp->bb_group, grp, GFP_ATOMIC);
891 grp->bb_group, new, err);
899 struct super_block *sb = ac->ac_sb;
901 enum criteria cr = ac->ac_criteria;
909 xa_for_each_range(xa, group, grp, start, end - 1) {
912 if (sbi->s_mb_stats)
913 atomic64_inc(&sbi->s_bal_cX_groups_considered[cr]);
915 err = ext4_mb_scan_group(ac, grp->bb_group);
916 if (err || ac->ac_status != AC_STATUS_CONTINUE)
933 struct xarray *xa = &EXT4_SB(ac->ac_sb)->s_mb_largest_free_orders[order];
948 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
954 end = ext4_get_groups_count(ac->ac_sb);
956 for (i = ac->ac_2order; i < MB_NUM_ORDERS(ac->ac_sb); i++) {
959 if (ret || ac->ac_status != AC_STATUS_CONTINUE)
968 if (sbi->s_mb_stats)
969 atomic64_inc(&sbi->s_bal_cX_failed[ac->ac_criteria]);
972 ac->ac_criteria = CR_GOAL_LEN_FAST;
984 struct xarray *xa = &EXT4_SB(ac->ac_sb)->s_mb_avg_fragment_size[order];
999 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1004 end = ext4_get_groups_count(ac->ac_sb);
1006 i = mb_avg_fragment_size_order(ac->ac_sb, ac->ac_g_ex.fe_len);
1007 for (; i < MB_NUM_ORDERS(ac->ac_sb); i++) {
1010 if (ret || ac->ac_status != AC_STATUS_CONTINUE)
1019 if (sbi->s_mb_stats)
1020 atomic64_inc(&sbi->s_bal_cX_failed[ac->ac_criteria]);
1025 * request len. However, allocation request for non-regular
1029 if (ac->ac_flags & EXT4_MB_HINT_DATA)
1030 ac->ac_criteria = CR_BEST_AVAIL_LEN;
1032 ac->ac_criteria = CR_GOAL_LEN_SLOW;
1039 * order we have and proactively trim the goal request length to that order to
1043 * preallocations. However, we make sure that we don't trim the request too
1050 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1061 order = fls(ac->ac_g_ex.fe_len) - 1;
1062 if (WARN_ON_ONCE(order - 1 > MB_NUM_ORDERS(ac->ac_sb)))
1063 order = MB_NUM_ORDERS(ac->ac_sb);
1064 min_order = order - sbi->s_mb_best_avail_max_trim_order;
1068 if (sbi->s_stripe > 0) {
1073 num_stripe_clusters = EXT4_NUM_B2C(sbi, sbi->s_stripe);
1079 min_order = fls(num_stripe_clusters) - 1;
1082 if (1 << min_order < ac->ac_o_ex.fe_len)
1083 min_order = fls(ac->ac_o_ex.fe_len);
1086 end = ext4_get_groups_count(ac->ac_sb);
1088 for (i = order; i >= min_order; i--) {
1095 ac->ac_g_ex.fe_len = 1 << i;
1103 ac->ac_g_ex.fe_len = roundup(ac->ac_g_ex.fe_len,
1107 frag_order = mb_avg_fragment_size_order(ac->ac_sb,
1108 ac->ac_g_ex.fe_len);
1112 if (ret || ac->ac_status != AC_STATUS_CONTINUE)
1122 ac->ac_g_ex.fe_len = ac->ac_orig_goal_len;
1123 if (sbi->s_mb_stats)
1124 atomic64_inc(&sbi->s_bal_cX_failed[ac->ac_criteria]);
1125 ac->ac_criteria = CR_GOAL_LEN_SLOW;
1132 if (unlikely(!test_opt2(ac->ac_sb, MB_OPTIMIZE_SCAN)))
1134 if (ac->ac_criteria >= CR_GOAL_LEN_SLOW)
1136 if (!ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS))
1147 * Artificially restricted ngroups for non-extent
1157 enum criteria cr = ac->ac_criteria;
1158 struct super_block *sb = ac->ac_sb;
1164 if (ret || ac->ac_status != AC_STATUS_CONTINUE)
1171 ac->ac_criteria++;
1174 if (sbi->s_mb_stats && i == ngroups)
1175 atomic64_inc(&sbi->s_bal_cX_failed[cr]);
1184 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
1185 ext4_group_t ngroups = ext4_get_groups_count(ac->ac_sb);
1187 /* non-extent files are limited to low blocks/groups */
1188 if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)))
1189 ngroups = sbi->s_blockfile_groups;
1192 start = ac->ac_g_ex.fe_group;
1193 ac->ac_prefetch_grp = start;
1194 ac->ac_prefetch_nr = 0;
1204 if (sbi->s_mb_max_linear_groups)
1206 sbi->s_mb_max_linear_groups);
1207 if (ret || ac->ac_status != AC_STATUS_CONTINUE)
1210 switch (ac->ac_criteria) {
1237 int new, old = grp->bb_largest_free_order;
1239 for (new = MB_NUM_ORDERS(sb) - 1; new >= 0; new--)
1240 if (grp->bb_counters[new] > 0)
1248 struct xarray *xa = &sbi->s_mb_largest_free_orders[old];
1250 if (!xa_empty(xa) && xa_load(xa, grp->bb_group))
1251 xa_erase(xa, grp->bb_group);
1254 grp->bb_largest_free_order = new;
1255 if (test_opt2(sb, MB_OPTIMIZE_SCAN) && new >= 0 && grp->bb_free) {
1261 int err = xa_insert(&sbi->s_mb_largest_free_orders[new],
1262 grp->bb_group, grp, GFP_ATOMIC);
1265 grp->bb_group, new, err);
1284 * of on-disk bitmap and preallocations */
1286 grp->bb_first_free = i;
1291 len = i - first;
1296 grp->bb_counters[0]++;
1300 grp->bb_fragments = fragments;
1302 if (free != grp->bb_free) {
1306 free, grp->bb_free);
1311 grp->bb_free = free;
1318 clear_bit(EXT4_GROUP_INFO_NEED_INIT_BIT, &(grp->bb_state));
1320 period = get_cycles() - period;
1321 atomic_inc(&sbi->s_mb_buddies_generated);
1322 atomic64_add(period, &sbi->s_mb_generation_time);
1334 e4b->bd_info->bb_fragments = 0;
1335 memset(e4b->bd_info->bb_counters, 0,
1336 sizeof(*e4b->bd_info->bb_counters) *
1337 (e4b->bd_sb->s_blocksize_bits + 2));
1339 ext4_mb_generate_buddy(e4b->bd_sb, e4b->bd_buddy,
1340 e4b->bd_bitmap, e4b->bd_group, e4b->bd_info);
1376 char *data;
1380 inode = folio->mapping->host;
1381 sb = inode->i_sb;
1388 mb_debug(sb, "init folio %lu\n", folio->index);
1395 return -ENOMEM;
1400 first_group = EXT4_PG_TO_LBLK(inode, folio->index) / 2;
1439 first_block = EXT4_PG_TO_LBLK(inode, folio->index);
1445 if (!bh[group - first_group])
1449 if (!buffer_verified(bh[group - first_group]))
1455 * data carry information regarding this
1460 data = folio_address(folio) + (i * blocksize);
1461 bitmap = bh[group - first_group]->b_data;
1469 err = -EFSCORRUPTED;
1476 group, folio->index, i * blocksize);
1478 grinfo->bb_fragments = 0;
1479 memset(grinfo->bb_counters, 0,
1480 sizeof(*grinfo->bb_counters) *
1487 memset(data, 0xff, blocksize);
1488 ext4_mb_generate_buddy(sb, data, incore, group, grinfo);
1495 group, folio->index, i * blocksize);
1500 memcpy(data, bitmap, blocksize);
1502 /* mark all preallocated blks used in in-core bitmap */
1503 ext4_mb_generate_from_pa(sb, data, group);
1504 WARN_ON_ONCE(!RB_EMPTY_ROOT(&grinfo->bb_free_root));
1510 incore = data;
1529 * are on the same folio e4b->bd_buddy_folio is NULL and return value is 0.
1534 struct inode *inode = EXT4_SB(sb)->s_buddy_cache;
1538 e4b->bd_buddy_folio = NULL;
1539 e4b->bd_bitmap_folio = NULL;
1548 folio = __filemap_get_folio(inode->i_mapping, pnum,
1552 BUG_ON(folio->mapping != inode->i_mapping);
1553 WARN_ON_ONCE(folio_size(folio) < sb->s_blocksize);
1554 e4b->bd_bitmap_folio = folio;
1555 e4b->bd_bitmap = folio_address(folio) +
1566 folio = __filemap_get_folio(inode->i_mapping, pnum,
1570 BUG_ON(folio->mapping != inode->i_mapping);
1571 WARN_ON_ONCE(folio_size(folio) < sb->s_blocksize);
1572 e4b->bd_buddy_folio = folio;
1578 if (e4b->bd_bitmap_folio) {
1579 folio_unlock(e4b->bd_bitmap_folio);
1580 folio_put(e4b->bd_bitmap_folio);
1582 if (e4b->bd_buddy_folio) {
1583 folio_unlock(e4b->bd_buddy_folio);
1584 folio_put(e4b->bd_buddy_folio);
1606 return -EFSCORRUPTED;
1631 ret = -EIO;
1650 ret = -EIO;
1673 struct inode *inode = sbi->s_buddy_cache;
1680 return -EFSCORRUPTED;
1682 e4b->bd_blkbits = sb->s_blocksize_bits;
1683 e4b->bd_info = grp;
1684 e4b->bd_sb = sb;
1685 e4b->bd_group = group;
1686 e4b->bd_buddy_folio = NULL;
1687 e4b->bd_bitmap_folio = NULL;
1691 * we need full data about the group
1708 folio = __filemap_get_folio(inode->i_mapping, pnum, FGP_ACCESSED, 0);
1720 folio = __filemap_get_folio(inode->i_mapping, pnum,
1723 if (WARN_RATELIMIT(folio->mapping != inode->i_mapping,
1724 "ext4: bitmap's mapping != inode->i_mapping\n")) {
1727 ret = -EINVAL;
1748 ret = -EIO;
1753 e4b->bd_bitmap_folio = folio;
1754 e4b->bd_bitmap = folio_address(folio) +
1766 folio = __filemap_get_folio(inode->i_mapping, pnum, FGP_ACCESSED, 0);
1770 folio = __filemap_get_folio(inode->i_mapping, pnum,
1773 if (WARN_RATELIMIT(folio->mapping != inode->i_mapping,
1774 "ext4: buddy bitmap's mapping != inode->i_mapping\n")) {
1777 ret = -EINVAL;
1781 ret = ext4_mb_init_cache(folio, e4b->bd_bitmap,
1796 ret = -EIO;
1802 e4b->bd_buddy_folio = folio;
1803 e4b->bd_buddy = folio_address(folio) +
1811 if (e4b->bd_bitmap_folio)
1812 folio_put(e4b->bd_bitmap_folio);
1814 e4b->bd_buddy = NULL;
1815 e4b->bd_bitmap = NULL;
1827 if (e4b->bd_bitmap_folio)
1828 folio_put(e4b->bd_bitmap_folio);
1829 if (e4b->bd_buddy_folio)
1830 folio_put(e4b->bd_buddy_folio);
1839 BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);
1840 BUG_ON(block >= (1 << (e4b->bd_blkbits + 3)));
1842 while (order <= e4b->bd_blkbits + 1) {
1859 if ((cur & 31) == 0 && (len - cur) >= 32) {
1872 * will return first found zero bit if any, -1 otherwise
1877 int zero_bit = -1;
1881 if ((cur & 31) == 0 && (len - cur) >= 32) {
1884 if (*addr != (__u32)(-1) && zero_bit == -1)
1890 if (!mb_test_and_clear_bit(cur, bm) && zero_bit == -1)
1904 if ((cur & 31) == 0 && (len - cur) >= 32) {
1920 (*bit) -= side;
1926 return -1;
1949 * ---------------------------------
1951 * ---------------------------------
1953 * ---------------------------------
1969 e4b->bd_info->bb_counters[order] += mb_buddy_adjust_border(&first, buddy, -1);
1971 e4b->bd_info->bb_counters[order] += mb_buddy_adjust_border(&last, buddy, 1);
1978 mb_clear_bits(buddy, first, last - first + 1);
1979 e4b->bd_info->bb_counters[order - 1] += last - first + 1;
1994 int last = first + count - 1;
1995 struct super_block *sb = e4b->bd_sb;
1999 BUG_ON(last >= (sb->s_blocksize << 3));
2000 assert_spin_locked(ext4_group_lock_ptr(sb, e4b->bd_group));
2002 if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))
2012 left_is_free = !mb_test_bit(first - 1, e4b->bd_bitmap);
2013 block = mb_test_and_clear_bits(e4b->bd_bitmap, first, count);
2014 if (last + 1 < EXT4_SB(sb)->s_mb_maxs[0])
2015 right_is_free = !mb_test_bit(last + 1, e4b->bd_bitmap);
2017 if (unlikely(block != -1)) {
2025 if (sbi->s_mount_state & EXT4_FC_REPLAY) {
2030 blocknr = ext4_group_first_block_no(sb, e4b->bd_group);
2032 ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,
2034 ext4_grp_locked_error(sb, e4b->bd_group,
2035 inode ? inode->i_ino : 0, blocknr,
2042 e4b->bd_info->bb_free += count;
2043 if (first < e4b->bd_info->bb_first_free)
2044 e4b->bd_info->bb_first_free = first;
2048 e4b->bd_info->bb_fragments--;
2050 e4b->bd_info->bb_fragments++;
2060 e4b->bd_info->bb_counters[0] += left_is_free ? -1 : 1;
2063 last -= !right_is_free;
2064 e4b->bd_info->bb_counters[0] += right_is_free ? -1 : 1;
2070 mb_set_largest_free_order(sb, e4b->bd_info);
2071 mb_update_avg_fragment_size(sb, e4b->bd_info);
2082 assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
2089 ex->fe_len = 0;
2090 ex->fe_start = 0;
2091 ex->fe_group = 0;
2098 ex->fe_len = (1 << order) - (block & ((1 << order) - 1));
2099 ex->fe_start = block;
2100 ex->fe_group = e4b->bd_group;
2104 while (needed > ex->fe_len &&
2111 if (mb_test_bit(next, e4b->bd_bitmap))
2117 ex->fe_len += 1 << order;
2120 if (ex->fe_start + ex->fe_len > EXT4_CLUSTERS_PER_GROUP(e4b->bd_sb)) {
2123 ext4_grp_locked_error(e4b->bd_sb, e4b->bd_group, 0, 0,
2126 block, order, needed, ex->fe_group, ex->fe_start,
2127 ex->fe_len, ex->fe_logical);
2128 ex->fe_len = 0;
2129 ex->fe_start = 0;
2130 ex->fe_group = 0;
2132 return ex->fe_len;
2140 int start = ex->fe_start;
2141 int len = ex->fe_len;
2147 BUG_ON(start + len > (e4b->bd_sb->s_blocksize << 3));
2148 BUG_ON(e4b->bd_group != ex->fe_group);
2149 assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
2154 e4b->bd_info->bb_free -= len;
2155 if (e4b->bd_info->bb_first_free == start)
2156 e4b->bd_info->bb_first_free += len;
2160 mlen = !mb_test_bit(start - 1, e4b->bd_bitmap);
2161 if (start + len < EXT4_SB(e4b->bd_sb)->s_mb_maxs[0])
2162 max = !mb_test_bit(start + len, e4b->bd_bitmap);
2164 e4b->bd_info->bb_fragments++;
2166 e4b->bd_info->bb_fragments--;
2178 e4b->bd_info->bb_counters[ord]--;
2180 len -= mlen;
2192 e4b->bd_info->bb_counters[ord]--;
2198 ext4_mb_mark_free_simple(e4b->bd_sb, e4b->bd_buddy,
2199 ord_start, start - ord_start,
2200 e4b->bd_info);
2204 ext4_mb_mark_free_simple(e4b->bd_sb, e4b->bd_buddy,
2206 ord_end - (start + len),
2207 e4b->bd_info);
2210 len = start + len - ord_end;
2213 mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info);
2215 mb_update_avg_fragment_size(e4b->bd_sb, e4b->bd_info);
2216 mb_set_bits(e4b->bd_bitmap, ex->fe_start, len0);
2228 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
2231 BUG_ON(ac->ac_b_ex.fe_group != e4b->bd_group);
2232 BUG_ON(ac->ac_status == AC_STATUS_FOUND);
2234 ac->ac_b_ex.fe_len = min(ac->ac_b_ex.fe_len, ac->ac_g_ex.fe_len);
2235 ac->ac_b_ex.fe_logical = ac->ac_g_ex.fe_logical;
2236 ret = mb_mark_used(e4b, &ac->ac_b_ex);
2240 ac->ac_f_ex = ac->ac_b_ex;
2242 ac->ac_status = AC_STATUS_FOUND;
2243 ac->ac_tail = ret & 0xffff;
2244 ac->ac_buddy = ret >> 16;
2253 ac->ac_bitmap_folio = e4b->bd_bitmap_folio;
2254 folio_get(ac->ac_bitmap_folio);
2255 ac->ac_buddy_folio = e4b->bd_buddy_folio;
2256 folio_get(ac->ac_buddy_folio);
2258 if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {
2259 int hash = ac->ac_inode->i_ino % sbi->s_mb_nr_global_goals;
2261 WRITE_ONCE(sbi->s_mb_last_groups[hash], ac->ac_f_ex.fe_group);
2269 if (ac->ac_o_ex.fe_len < ac->ac_b_ex.fe_len)
2278 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
2279 struct ext4_free_extent *bex = &ac->ac_b_ex;
2280 struct ext4_free_extent *gex = &ac->ac_g_ex;
2282 if (ac->ac_status == AC_STATUS_FOUND)
2287 if (ac->ac_found > sbi->s_mb_max_to_scan &&
2288 !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
2289 ac->ac_status = AC_STATUS_BREAK;
2296 if (bex->fe_len < gex->fe_len)
2299 if (finish_group || ac->ac_found > sbi->s_mb_min_to_scan)
2317 * upto a max of sbi->s_mb_max_to_scan times (default 200). After
2321 * upto a max of sbi->s_mb_min_to_scan times (default 10) before
2331 struct ext4_free_extent *bex = &ac->ac_b_ex;
2332 struct ext4_free_extent *gex = &ac->ac_g_ex;
2334 BUG_ON(ex->fe_len <= 0);
2335 BUG_ON(ex->fe_len > EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));
2336 BUG_ON(ex->fe_start >= EXT4_CLUSTERS_PER_GROUP(ac->ac_sb));
2337 BUG_ON(ac->ac_status != AC_STATUS_CONTINUE);
2339 ac->ac_found++;
2340 ac->ac_cX_found[ac->ac_criteria]++;
2343 * The special case - take what you catch first
2345 if (unlikely(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
2354 if (ex->fe_len == gex->fe_len) {
2363 if (bex->fe_len == 0) {
2371 if (bex->fe_len < gex->fe_len) {
2374 if (ex->fe_len > bex->fe_len)
2376 } else if (ex->fe_len > gex->fe_len) {
2380 if (ex->fe_len < bex->fe_len)
2391 struct ext4_free_extent ex = ac->ac_b_ex;
2397 err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);
2401 ext4_lock_group(ac->ac_sb, group);
2402 if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))
2408 ac->ac_b_ex = ex;
2413 ext4_unlock_group(ac->ac_sb, group);
2421 ext4_group_t group = ac->ac_g_ex.fe_group;
2424 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
2425 struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);
2429 return -EFSCORRUPTED;
2430 if (!(ac->ac_flags & (EXT4_MB_HINT_TRY_GOAL | EXT4_MB_HINT_GOAL_ONLY)))
2432 if (grp->bb_free == 0)
2435 err = ext4_mb_load_buddy(ac->ac_sb, group, e4b);
2439 ext4_lock_group(ac->ac_sb, group);
2440 if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))
2443 max = mb_find_extent(e4b, ac->ac_g_ex.fe_start,
2444 ac->ac_g_ex.fe_len, &ex);
2447 if (max >= ac->ac_g_ex.fe_len &&
2448 ac->ac_g_ex.fe_len == EXT4_NUM_B2C(sbi, sbi->s_stripe)) {
2451 start = ext4_grp_offs_to_block(ac->ac_sb, &ex);
2452 /* use do_div to get remainder (would be 64-bit modulo) */
2453 if (do_div(start, sbi->s_stripe) == 0) {
2454 ac->ac_found++;
2455 ac->ac_b_ex = ex;
2458 } else if (max >= ac->ac_g_ex.fe_len) {
2460 BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
2461 BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
2462 ac->ac_found++;
2463 ac->ac_b_ex = ex;
2465 } else if (max > 0 && (ac->ac_flags & EXT4_MB_HINT_MERGE)) {
2469 BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
2470 BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
2471 ac->ac_found++;
2472 ac->ac_b_ex = ex;
2476 ext4_unlock_group(ac->ac_sb, group);
2490 struct super_block *sb = ac->ac_sb;
2491 struct ext4_group_info *grp = e4b->bd_info;
2497 BUG_ON(ac->ac_2order <= 0);
2498 for (i = ac->ac_2order; i < MB_NUM_ORDERS(sb); i++) {
2499 if (grp->bb_counters[i] == 0)
2509 ext4_mark_group_bitmap_corrupted(ac->ac_sb,
2510 e4b->bd_group,
2512 ext4_grp_locked_error(ac->ac_sb, e4b->bd_group, 0, 0,
2514 grp->bb_counters[i], i);
2517 ac->ac_found++;
2518 ac->ac_cX_found[ac->ac_criteria]++;
2520 ac->ac_b_ex.fe_len = 1 << i;
2521 ac->ac_b_ex.fe_start = k << i;
2522 ac->ac_b_ex.fe_group = e4b->bd_group;
2526 BUG_ON(ac->ac_f_ex.fe_len != ac->ac_g_ex.fe_len);
2528 if (EXT4_SB(sb)->s_mb_stats)
2529 atomic_inc(&EXT4_SB(sb)->s_bal_2orders);
2544 struct super_block *sb = ac->ac_sb;
2545 void *bitmap = e4b->bd_bitmap;
2550 free = e4b->bd_info->bb_free;
2554 i = e4b->bd_info->bb_first_free;
2556 while (free && ac->ac_status == AC_STATUS_CONTINUE) {
2565 ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,
2567 ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,
2574 if (!ext4_mb_cr_expensive(ac->ac_criteria)) {
2583 freelen = j - i;
2585 if (freelen < ac->ac_g_ex.fe_len) {
2587 free -= freelen;
2592 mb_find_extent(e4b, i, ac->ac_g_ex.fe_len, &ex);
2596 ext4_mark_group_bitmap_corrupted(sb, e4b->bd_group,
2598 ext4_grp_locked_error(sb, e4b->bd_group, 0, 0,
2613 free -= ex.fe_len;
2621 * we try to find stripe-aligned chunks for stripe-size-multiple requests
2627 struct super_block *sb = ac->ac_sb;
2629 void *bitmap = e4b->bd_bitmap;
2636 BUG_ON(sbi->s_stripe == 0);
2638 /* find first stripe-aligned block in group */
2639 first_group_block = ext4_group_first_block_no(sb, e4b->bd_group);
2641 a = first_group_block + sbi->s_stripe - 1;
2642 do_div(a, sbi->s_stripe);
2643 i = (a * sbi->s_stripe) - first_group_block;
2645 stripe = EXT4_NUM_B2C(sbi, sbi->s_stripe);
2651 ac->ac_found++;
2652 ac->ac_cX_found[ac->ac_criteria]++;
2654 ac->ac_b_ex = ex;
2667 enum criteria cr = ac->ac_criteria;
2669 ac->ac_groups_scanned++;
2671 return ext4_mb_simple_scan_group(ac, ac->ac_e4b);
2673 sbi = EXT4_SB(ac->ac_sb);
2675 if ((sbi->s_stripe >= sbi->s_cluster_ratio) &&
2676 !(ac->ac_g_ex.fe_len % EXT4_NUM_B2C(sbi, sbi->s_stripe)))
2681 ext4_mb_scan_aligned(ac, ac->ac_e4b);
2683 if (ac->ac_status == AC_STATUS_CONTINUE)
2684 ext4_mb_complex_scan_group(ac, ac->ac_e4b);
2696 int flex_size = ext4_flex_bg_size(EXT4_SB(ac->ac_sb));
2697 struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);
2704 free = grp->bb_free;
2708 fragments = grp->bb_fragments;
2714 BUG_ON(ac->ac_2order == 0);
2716 /* Avoid using the first bg of a flexgroup for data files */
2717 if ((ac->ac_flags & EXT4_MB_HINT_DATA) &&
2722 if (free < ac->ac_g_ex.fe_len)
2725 if (ac->ac_2order >= MB_NUM_ORDERS(ac->ac_sb))
2728 if (grp->bb_largest_free_order < ac->ac_2order)
2734 if ((free / fragments) >= ac->ac_g_ex.fe_len)
2738 if (free >= ac->ac_g_ex.fe_len)
2764 struct ext4_group_info *grp = ext4_get_group_info(ac->ac_sb, group);
2765 struct super_block *sb = ac->ac_sb;
2767 bool should_lock = ac->ac_flags & EXT4_MB_STRICT_CHECK;
2772 return -EFSCORRUPTED;
2773 if (sbi->s_mb_stats)
2774 atomic64_inc(&sbi->s_bal_cX_groups_considered[ac->ac_criteria]);
2779 free = grp->bb_free;
2787 if (cr < CR_ANY_FREE && free < ac->ac_g_ex.fe_len)
2805 * data is not ready, then this optimization makes no sense. But
2812 (!sbi->s_log_groups_per_flex ||
2813 ((group & ((1 << sbi->s_log_groups_per_flex) - 1)) != 0)) &&
2815 (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))))
2847 while (nr-- > 0) {
2887 if (ac->ac_prefetch_grp != group)
2890 sbi = EXT4_SB(ac->ac_sb);
2891 if (ext4_mb_cr_expensive(ac->ac_criteria) ||
2892 ac->ac_prefetch_ios < sbi->s_mb_prefetch_limit) {
2893 unsigned int nr = sbi->s_mb_prefetch;
2895 if (ext4_has_feature_flex_bg(ac->ac_sb)) {
2896 nr = 1 << sbi->s_log_groups_per_flex;
2897 nr -= group & (nr - 1);
2898 nr = umin(nr, sbi->s_mb_prefetch);
2901 ac->ac_prefetch_nr = nr;
2902 ac->ac_prefetch_grp = ext4_mb_prefetch(ac->ac_sb, group, nr,
2903 &ac->ac_prefetch_ios);
2925 while (nr-- > 0) {
2928 group--;
2944 struct super_block *sb = ac->ac_sb;
2945 enum criteria cr = ac->ac_criteria;
2956 if (!ac->ac_first_err)
2957 ac->ac_first_err = ret;
2961 ret = ext4_mb_load_buddy(sb, group, ac->ac_e4b);
2980 ext4_mb_unload_buddy(ac->ac_e4b);
2989 struct super_block *sb = ac->ac_sb;
2993 BUG_ON(ac->ac_status == AC_STATUS_FOUND);
2997 if (err || ac->ac_status == AC_STATUS_FOUND)
3000 if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
3004 * ac->ac_2order is set only if the fe_len is a power of 2
3005 * if ac->ac_2order is set we also set criteria to CR_POWER2_ALIGNED
3008 i = fls(ac->ac_g_ex.fe_len);
3009 ac->ac_2order = 0;
3011 * We search using buddy data only if the order of the request
3014 * We also support searching for power-of-two requests only for
3017 if (i >= sbi->s_mb_order2_reqs && i <= MB_NUM_ORDERS(sb)) {
3018 if (is_power_of_2(ac->ac_g_ex.fe_len))
3019 ac->ac_2order = array_index_nospec(i - 1,
3024 if (ac->ac_flags & EXT4_MB_STREAM_ALLOC) {
3025 int hash = ac->ac_inode->i_ino % sbi->s_mb_nr_global_goals;
3027 ac->ac_g_ex.fe_group = READ_ONCE(sbi->s_mb_last_groups[hash]);
3028 ac->ac_g_ex.fe_start = -1;
3029 ac->ac_flags &= ~EXT4_MB_HINT_TRY_GOAL;
3033 * Let's just scan groups to find more-less suitable blocks We
3037 ac->ac_criteria = CR_GOAL_LEN_FAST;
3038 if (ac->ac_2order)
3039 ac->ac_criteria = CR_POWER2_ALIGNED;
3041 ac->ac_e4b = &e4b;
3042 ac->ac_prefetch_ios = 0;
3043 ac->ac_first_err = 0;
3045 while (ac->ac_criteria < EXT4_MB_NUM_CRS) {
3050 if (ac->ac_status != AC_STATUS_CONTINUE)
3054 if (ac->ac_b_ex.fe_len > 0 && ac->ac_status != AC_STATUS_FOUND &&
3055 !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
3061 if (ac->ac_status != AC_STATUS_FOUND) {
3069 lost = atomic_inc_return(&sbi->s_mb_lost_chunks);
3071 ac->ac_b_ex.fe_group, ac->ac_b_ex.fe_start,
3072 ac->ac_b_ex.fe_len, lost);
3074 ac->ac_b_ex.fe_group = 0;
3075 ac->ac_b_ex.fe_start = 0;
3076 ac->ac_b_ex.fe_len = 0;
3077 ac->ac_status = AC_STATUS_CONTINUE;
3078 ac->ac_flags |= EXT4_MB_HINT_FIRST;
3079 ac->ac_criteria = CR_ANY_FREE;
3084 if (sbi->s_mb_stats && ac->ac_status == AC_STATUS_FOUND) {
3085 atomic64_inc(&sbi->s_bal_cX_hits[ac->ac_criteria]);
3086 if (ac->ac_flags & EXT4_MB_STREAM_ALLOC &&
3087 ac->ac_b_ex.fe_group == ac->ac_g_ex.fe_group)
3088 atomic_inc(&sbi->s_bal_stream_goals);
3091 if (!err && ac->ac_status != AC_STATUS_FOUND && ac->ac_first_err)
3092 err = ac->ac_first_err;
3095 ac->ac_b_ex.fe_len, ac->ac_o_ex.fe_len, ac->ac_status,
3096 ac->ac_flags, ac->ac_criteria, err);
3098 if (ac->ac_prefetch_nr)
3099 ext4_mb_prefetch_fini(sb, ac->ac_prefetch_grp, ac->ac_prefetch_nr);
3106 struct super_block *sb = pde_data(file_inode(seq->file));
3117 struct super_block *sb = pde_data(file_inode(seq->file));
3129 struct super_block *sb = pde_data(file_inode(seq->file));
3136 sb->s_blocksize_bits,
3141 group--;
3147 i = (blocksize_bits + 2) * sizeof(sg->bb_counters[0]) +
3157 seq_printf(seq, "#%-5u: %s\n", group, ext4_decode_error(NULL, err, nbuf));
3168 seq_printf(seq, "#%-5u: %-5u %-5u %-5u [", group, sg->bb_free,
3169 sg->bb_fragments, sg->bb_first_free);
3171 seq_printf(seq, " %-5u", i <= blocksize_bits + 1 ?
3172 sg->bb_counters[i] : 0);
3193 struct super_block *sb = seq->private;
3197 if (!sbi->s_mb_stats) {
3204 seq_printf(seq, "\treqs: %u\n", atomic_read(&sbi->s_bal_reqs));
3205 seq_printf(seq, "\tsuccess: %u\n", atomic_read(&sbi->s_bal_success));
3208 atomic_read(&sbi->s_bal_groups_scanned));
3213 atomic64_read(&sbi->s_bal_cX_hits[CR_POWER2_ALIGNED]));
3217 &sbi->s_bal_cX_groups_considered[CR_POWER2_ALIGNED]));
3219 atomic_read(&sbi->s_bal_cX_ex_scanned[CR_POWER2_ALIGNED]));
3221 atomic64_read(&sbi->s_bal_cX_failed[CR_POWER2_ALIGNED]));
3226 atomic64_read(&sbi->s_bal_cX_hits[CR_GOAL_LEN_FAST]));
3229 &sbi->s_bal_cX_groups_considered[CR_GOAL_LEN_FAST]));
3231 atomic_read(&sbi->s_bal_cX_ex_scanned[CR_GOAL_LEN_FAST]));
3233 atomic64_read(&sbi->s_bal_cX_failed[CR_GOAL_LEN_FAST]));
3238 atomic64_read(&sbi->s_bal_cX_hits[CR_BEST_AVAIL_LEN]));
3242 &sbi->s_bal_cX_groups_considered[CR_BEST_AVAIL_LEN]));
3244 atomic_read(&sbi->s_bal_cX_ex_scanned[CR_BEST_AVAIL_LEN]));
3246 atomic64_read(&sbi->s_bal_cX_failed[CR_BEST_AVAIL_LEN]));
3251 atomic64_read(&sbi->s_bal_cX_hits[CR_GOAL_LEN_SLOW]));
3254 &sbi->s_bal_cX_groups_considered[CR_GOAL_LEN_SLOW]));
3256 atomic_read(&sbi->s_bal_cX_ex_scanned[CR_GOAL_LEN_SLOW]));
3258 atomic64_read(&sbi->s_bal_cX_failed[CR_GOAL_LEN_SLOW]));
3263 atomic64_read(&sbi->s_bal_cX_hits[CR_ANY_FREE]));
3266 atomic64_read(&sbi->s_bal_cX_groups_considered[CR_ANY_FREE]));
3268 atomic_read(&sbi->s_bal_cX_ex_scanned[CR_ANY_FREE]));
3270 atomic64_read(&sbi->s_bal_cX_failed[CR_ANY_FREE]));
3274 atomic_read(&sbi->s_bal_ex_scanned));
3275 seq_printf(seq, "\t\tgoal_hits: %u\n", atomic_read(&sbi->s_bal_goals));
3277 atomic_read(&sbi->s_bal_stream_goals));
3279 atomic_read(&sbi->s_bal_len_goals));
3280 seq_printf(seq, "\t\t2^n_hits: %u\n", atomic_read(&sbi->s_bal_2orders));
3281 seq_printf(seq, "\t\tbreaks: %u\n", atomic_read(&sbi->s_bal_breaks));
3282 seq_printf(seq, "\t\tlost: %u\n", atomic_read(&sbi->s_mb_lost_chunks));
3284 atomic_read(&sbi->s_mb_buddies_generated),
3287 atomic64_read(&sbi->s_mb_generation_time));
3289 atomic_read(&sbi->s_mb_preallocated));
3290 seq_printf(seq, "\tdiscarded: %u\n", atomic_read(&sbi->s_mb_discarded));
3296 struct super_block *sb = pde_data(file_inode(seq->file));
3307 struct super_block *sb = pde_data(file_inode(seq->file));
3319 struct super_block *sb = pde_data(file_inode(seq->file));
3326 position--;
3328 position -= MB_NUM_ORDERS(sb);
3333 xa_for_each(&sbi->s_mb_avg_fragment_size[position], idx, grp)
3346 xa_for_each(&sbi->s_mb_largest_free_orders[position], idx, grp)
3367 int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;
3375 * Allocate the top-level s_group_info array for the specified number
3384 size = (ngroups + EXT4_DESC_PER_BLOCK(sb) - 1) >>
3386 if (size <= sbi->s_group_info_size)
3389 size = roundup_pow_of_two(sizeof(*sbi->s_group_info) * size);
3393 return -ENOMEM;
3396 old_groupinfo = rcu_dereference(sbi->s_group_info);
3399 sbi->s_group_info_size * sizeof(*sbi->s_group_info));
3401 rcu_assign_pointer(sbi->s_group_info, new_groupinfo);
3402 sbi->s_group_info_size = size / sizeof(*sbi->s_group_info);
3406 sbi->s_group_info_size);
3410 /* Create and initialize ext4_group_info data for the given group. */
3419 struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits);
3433 return -ENOMEM;
3436 rcu_dereference(sbi->s_group_info)[idx] = meta_group_info;
3441 i = group & (EXT4_DESC_PER_BLOCK(sb) - 1);
3449 &(meta_group_info[i]->bb_state));
3456 (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {
3457 meta_group_info[i]->bb_free =
3460 meta_group_info[i]->bb_free =
3464 INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);
3465 init_rwsem(&meta_group_info[i]->alloc_sem);
3466 meta_group_info[i]->bb_free_root = RB_ROOT;
3467 meta_group_info[i]->bb_largest_free_order = -1; /* uninit */
3468 meta_group_info[i]->bb_avg_fragment_size_order = -1; /* uninit */
3469 meta_group_info[i]->bb_group = group;
3480 group_info = rcu_dereference(sbi->s_group_info);
3485 return -ENOMEM;
3502 sbi->s_buddy_cache = new_inode(sb);
3503 if (sbi->s_buddy_cache == NULL) {
3507 /* To avoid potentially colliding with an valid on-disk inode number,
3511 sbi->s_buddy_cache->i_ino = EXT4_BAD_INO;
3512 EXT4_I(sbi->s_buddy_cache)->i_disksize = 0;
3513 ext4_set_inode_mapping_order(sbi->s_buddy_cache);
3531 if (sbi->s_es->s_log_groups_per_flex >= 32) {
3535 sbi->s_mb_prefetch = min_t(uint, 1 << sbi->s_es->s_log_groups_per_flex,
3536 BLK_MAX_SEGMENT_SIZE >> (sb->s_blocksize_bits - 9));
3537 sbi->s_mb_prefetch *= 8; /* 8 prefetch IOs in flight at most */
3539 sbi->s_mb_prefetch = 32;
3541 if (sbi->s_mb_prefetch > ext4_get_groups_count(sb))
3542 sbi->s_mb_prefetch = ext4_get_groups_count(sb);
3545 * CR_POWER2_ALIGNED. Given CR_POWER2_ALIGNED is an CPU-related
3551 sbi->s_mb_prefetch_limit = sbi->s_mb_prefetch * 4;
3552 if (sbi->s_mb_prefetch_limit > ext4_get_groups_count(sb))
3553 sbi->s_mb_prefetch_limit = ext4_get_groups_count(sb);
3558 cachep = get_groupinfo_cache(sb->s_blocksize_bits);
3559 while (i-- > 0) {
3565 i = sbi->s_group_info_size;
3567 group_info = rcu_dereference(sbi->s_group_info);
3568 while (i-- > 0)
3571 iput(sbi->s_buddy_cache);
3574 kvfree(rcu_dereference(sbi->s_group_info));
3576 return -ENOMEM;
3594 int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;
3598 return -EINVAL;
3621 "EXT4-fs: no memory for groupinfo slab cache\n");
3622 return -ENOMEM;
3632 struct super_block *sb = sbi->s_sb;
3639 spin_lock(&sbi->s_md_lock);
3640 list_splice_init(&sbi->s_discard_list, &discard_list);
3641 spin_unlock(&sbi->s_md_lock);
3649 if ((sb->s_flags & SB_ACTIVE) && !err &&
3650 !atomic_read(&sbi->s_retry_alloc_pending)) {
3651 grp = fd->efd_group;
3667 ext4_try_to_trim_range(sb, &e4b, fd->efd_start_cluster,
3668 fd->efd_start_cluster + fd->efd_count - 1, 1);
3680 if (!sbi->s_mb_avg_fragment_size)
3683 for (int i = 0; i < MB_NUM_ORDERS(sbi->s_sb); i++)
3684 xa_destroy(&sbi->s_mb_avg_fragment_size[i]);
3686 kfree(sbi->s_mb_avg_fragment_size);
3687 sbi->s_mb_avg_fragment_size = NULL;
3692 if (!sbi->s_mb_largest_free_orders)
3695 for (int i = 0; i < MB_NUM_ORDERS(sbi->s_sb); i++)
3696 xa_destroy(&sbi->s_mb_largest_free_orders[i]);
3698 kfree(sbi->s_mb_largest_free_orders);
3699 sbi->s_mb_largest_free_orders = NULL;
3710 i = MB_NUM_ORDERS(sb) * sizeof(*sbi->s_mb_offsets);
3712 sbi->s_mb_offsets = kmalloc(i, GFP_KERNEL);
3713 if (sbi->s_mb_offsets == NULL) {
3714 ret = -ENOMEM;
3718 i = MB_NUM_ORDERS(sb) * sizeof(*sbi->s_mb_maxs);
3719 sbi->s_mb_maxs = kmalloc(i, GFP_KERNEL);
3720 if (sbi->s_mb_maxs == NULL) {
3721 ret = -ENOMEM;
3725 ret = ext4_groupinfo_create_slab(sb->s_blocksize);
3730 sbi->s_mb_maxs[0] = sb->s_blocksize << 3;
3731 sbi->s_mb_offsets[0] = 0;
3735 offset_incr = 1 << (sb->s_blocksize_bits - 1);
3736 max = sb->s_blocksize << 2;
3738 sbi->s_mb_offsets[i] = offset;
3739 sbi->s_mb_maxs[i] = max;
3746 sbi->s_mb_avg_fragment_size =
3749 if (!sbi->s_mb_avg_fragment_size) {
3750 ret = -ENOMEM;
3754 xa_init(&sbi->s_mb_avg_fragment_size[i]);
3756 sbi->s_mb_largest_free_orders =
3759 if (!sbi->s_mb_largest_free_orders) {
3760 ret = -ENOMEM;
3764 xa_init(&sbi->s_mb_largest_free_orders[i]);
3766 spin_lock_init(&sbi->s_md_lock);
3767 atomic_set(&sbi->s_mb_free_pending, 0);
3768 INIT_LIST_HEAD(&sbi->s_freed_data_list[0]);
3769 INIT_LIST_HEAD(&sbi->s_freed_data_list[1]);
3770 INIT_LIST_HEAD(&sbi->s_discard_list);
3771 INIT_WORK(&sbi->s_discard_work, ext4_discard_work);
3772 atomic_set(&sbi->s_retry_alloc_pending, 0);
3774 sbi->s_mb_max_to_scan = MB_DEFAULT_MAX_TO_SCAN;
3775 sbi->s_mb_min_to_scan = MB_DEFAULT_MIN_TO_SCAN;
3776 sbi->s_mb_stats = MB_DEFAULT_STATS;
3777 sbi->s_mb_stream_request = MB_DEFAULT_STREAM_THRESHOLD;
3778 sbi->s_mb_order2_reqs = MB_DEFAULT_ORDER2_REQS;
3779 sbi->s_mb_best_avail_max_trim_order = MB_DEFAULT_BEST_AVAIL_TRIM_ORDER;
3793 sbi->s_mb_group_prealloc = max(MB_DEFAULT_GROUP_PREALLOC >>
3794 sbi->s_cluster_bits, 32);
3803 if (sbi->s_stripe > 1) {
3804 sbi->s_mb_group_prealloc = roundup(
3805 sbi->s_mb_group_prealloc, EXT4_NUM_B2C(sbi, sbi->s_stripe));
3808 sbi->s_mb_nr_global_goals = umin(num_possible_cpus(),
3809 DIV_ROUND_UP(sbi->s_groups_count, 4));
3810 sbi->s_mb_last_groups = kcalloc(sbi->s_mb_nr_global_goals,
3812 if (sbi->s_mb_last_groups == NULL) {
3813 ret = -ENOMEM;
3817 sbi->s_locality_groups = alloc_percpu(struct ext4_locality_group);
3818 if (sbi->s_locality_groups == NULL) {
3819 ret = -ENOMEM;
3824 lg = per_cpu_ptr(sbi->s_locality_groups, i);
3825 mutex_init(&lg->lg_mutex);
3827 INIT_LIST_HEAD(&lg->lg_prealloc_list[j]);
3828 spin_lock_init(&lg->lg_prealloc_lock);
3831 if (bdev_nonrot(sb->s_bdev))
3832 sbi->s_mb_max_linear_groups = 0;
3834 sbi->s_mb_max_linear_groups = MB_DEFAULT_LINEAR_LIMIT;
3835 /* init file for buddy data */
3843 free_percpu(sbi->s_locality_groups);
3844 sbi->s_locality_groups = NULL;
3846 kfree(sbi->s_mb_last_groups);
3847 sbi->s_mb_last_groups = NULL;
3851 kfree(sbi->s_mb_offsets);
3852 sbi->s_mb_offsets = NULL;
3853 kfree(sbi->s_mb_maxs);
3854 sbi->s_mb_maxs = NULL;
3865 list_for_each_safe(cur, tmp, &grp->bb_prealloc_list) {
3867 list_del(&pa->pa_group_list);
3881 struct kmem_cache *cachep = get_groupinfo_cache(sb->s_blocksize_bits);
3888 flush_work(&sbi->s_discard_work);
3889 WARN_ON_ONCE(!list_empty(&sbi->s_discard_list));
3892 if (sbi->s_group_info) {
3908 EXT4_DESC_PER_BLOCK(sb) - 1) >>
3911 group_info = rcu_dereference(sbi->s_group_info);
3919 kfree(sbi->s_mb_offsets);
3920 kfree(sbi->s_mb_maxs);
3921 iput(sbi->s_buddy_cache);
3922 if (sbi->s_mb_stats) {
3925 atomic_read(&sbi->s_bal_allocated),
3926 atomic_read(&sbi->s_bal_reqs),
3927 atomic_read(&sbi->s_bal_success));
3931 atomic_read(&sbi->s_bal_ex_scanned),
3932 atomic_read(&sbi->s_bal_groups_scanned),
3933 atomic_read(&sbi->s_bal_goals),
3934 atomic_read(&sbi->s_bal_2orders),
3935 atomic_read(&sbi->s_bal_breaks),
3936 atomic_read(&sbi->s_mb_lost_chunks));
3939 atomic_read(&sbi->s_mb_buddies_generated),
3940 atomic64_read(&sbi->s_mb_generation_time));
3943 atomic_read(&sbi->s_mb_preallocated),
3944 atomic_read(&sbi->s_mb_discarded));
3947 free_percpu(sbi->s_locality_groups);
3948 kfree(sbi->s_mb_last_groups);
3973 entry->efd_count, entry->efd_group, entry);
3975 err = ext4_mb_load_buddy(sb, entry->efd_group, &e4b);
3979 atomic_sub(entry->efd_count, &EXT4_SB(sb)->s_mb_free_pending);
3982 count += entry->efd_count;
3983 ext4_lock_group(sb, entry->efd_group);
3985 rb_erase(&entry->efd_node, &(db->bb_free_root));
3986 mb_free_blocks(NULL, &e4b, entry->efd_start_cluster, entry->efd_count);
3990 * ext4_trim_fs can trim it.
3994 if (!db->bb_free_root.rb_node) {
4001 ext4_unlock_group(sb, entry->efd_group);
4016 struct list_head *s_freed_head = &sbi->s_freed_data_list[commit_tid & 1];
4025 spin_lock(&sbi->s_md_lock);
4026 wake = list_empty(&sbi->s_discard_list);
4027 list_splice_tail(&freed_data_list, &sbi->s_discard_list);
4028 spin_unlock(&sbi->s_md_lock);
4030 queue_work(system_dfl_wq, &sbi->s_discard_work);
4061 return -ENOMEM;
4109 err = -EIO;
4124 (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {
4125 gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
4133 if (mb_test_bit(blkoff + i, bitmap_bh->b_data) ==
4136 changed = len - already;
4140 mb_set_bits(bitmap_bh->b_data, blkoff, len);
4142 ext4_free_group_clusters(sb, gdp) - changed);
4144 mb_clear_bits(bitmap_bh->b_data, blkoff, len);
4155 if (sbi->s_log_groups_per_flex) {
4161 atomic64_sub(changed, &fg->free_clusters);
4163 atomic64_add(changed, &fg->free_clusters);
4184 * Check quota and mark chosen space (ac->ac_b_ex) non-free in bitmaps
4199 BUG_ON(ac->ac_status != AC_STATUS_FOUND);
4200 BUG_ON(ac->ac_b_ex.fe_len <= 0);
4202 sb = ac->ac_sb;
4205 gdp = ext4_get_group_desc(sb, ac->ac_b_ex.fe_group, NULL);
4207 return -EIO;
4208 ext4_debug("using block group %u(%d)\n", ac->ac_b_ex.fe_group,
4211 block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
4212 len = EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
4213 if (!ext4_inode_block_valid(ac->ac_inode, block, len)) {
4214 ext4_error(sb, "Allocating blocks %llu-%llu which overlap "
4221 ac->ac_b_ex.fe_group,
4222 ac->ac_b_ex.fe_start,
4223 ac->ac_b_ex.fe_len,
4226 err = -EFSCORRUPTED;
4233 err = ext4_mb_mark_context(handle, sb, true, ac->ac_b_ex.fe_group,
4234 ac->ac_b_ex.fe_start, ac->ac_b_ex.fe_len,
4241 BUG_ON(changed != ac->ac_b_ex.fe_len);
4243 percpu_counter_sub(&sbi->s_freeclusters_counter, ac->ac_b_ex.fe_len);
4247 if (!(ac->ac_flags & EXT4_MB_DELALLOC_RESERVED))
4249 percpu_counter_sub(&sbi->s_dirtyclusters_counter,
4280 EXT4_BLOCKS_PER_GROUP(sb) - EXT4_C2B(sbi, blkoff));
4284 ext4_error(sb, "Marking blocks in system zone - "
4299 len -= thisgrp_len;
4315 struct super_block *sb = ac->ac_sb;
4316 struct ext4_locality_group *lg = ac->ac_lg;
4319 ac->ac_g_ex.fe_len = EXT4_SB(sb)->s_mb_group_prealloc;
4320 mb_debug(sb, "goal %u blocks for locality group\n", ac->ac_g_ex.fe_len);
4326 * (ei->i_prealloc_lock)
4336 return node->rb_left;
4338 return node->rb_right;
4345 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
4346 struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
4352 read_lock(&ei->i_prealloc_lock);
4353 for (iter = ei->i_prealloc_node.rb_node; iter;
4357 tmp_pa_start = tmp_pa->pa_lstart;
4360 spin_lock(&tmp_pa->pa_lock);
4361 if (tmp_pa->pa_deleted == 0)
4363 spin_unlock(&tmp_pa->pa_lock);
4365 read_unlock(&ei->i_prealloc_lock);
4382 struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
4383 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
4386 ext4_lblk_t new_start, tmp_pa_start, right_pa_start = -1;
4387 loff_t new_end, tmp_pa_end, left_pa_end = -1;
4397 read_lock(&ei->i_prealloc_lock);
4400 for (iter = ei->i_prealloc_node.rb_node; iter;
4401 iter = ext4_mb_pa_rb_next_iter(ac->ac_o_ex.fe_logical,
4405 tmp_pa_start = tmp_pa->pa_lstart;
4409 spin_lock(&tmp_pa->pa_lock);
4410 if (tmp_pa->pa_deleted == 0)
4411 BUG_ON(!(ac->ac_o_ex.fe_logical >= tmp_pa_end ||
4412 ac->ac_o_ex.fe_logical < tmp_pa_start));
4413 spin_unlock(&tmp_pa->pa_lock);
4421 if (tmp_pa->pa_lstart < ac->ac_o_ex.fe_logical) {
4425 tmp = rb_next(&left_pa->pa_node.inode_node);
4435 tmp = rb_prev(&right_pa->pa_node.inode_node);
4446 for (iter = &left_pa->pa_node.inode_node;;
4456 spin_lock(&tmp_pa->pa_lock);
4457 if (tmp_pa->pa_deleted == 0) {
4458 spin_unlock(&tmp_pa->pa_lock);
4461 spin_unlock(&tmp_pa->pa_lock);
4466 for (iter = &right_pa->pa_node.inode_node;;
4476 spin_lock(&tmp_pa->pa_lock);
4477 if (tmp_pa->pa_deleted == 0) {
4478 spin_unlock(&tmp_pa->pa_lock);
4481 spin_unlock(&tmp_pa->pa_lock);
4487 BUG_ON(left_pa_end > ac->ac_o_ex.fe_logical);
4491 right_pa_start = right_pa->pa_lstart;
4492 BUG_ON(right_pa_start <= ac->ac_o_ex.fe_logical);
4495 /* Step 4: trim our normalized range to not overlap with the neighbors */
4505 read_unlock(&ei->i_prealloc_lock);
4522 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
4523 struct ext4_super_block *es = sbi->s_es;
4529 /* do normalize only data requests, metadata requests
4531 if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
4535 if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
4540 if (ac->ac_flags & EXT4_MB_HINT_NOPREALLOC)
4543 if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC) {
4548 bsbits = ac->ac_sb->s_blocksize_bits;
4552 size = extent_logical_end(sbi, &ac->ac_o_ex);
4554 if (size < i_size_read(ac->ac_inode))
4555 size = i_size_read(ac->ac_inode);
4582 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
4583 (21 - bsbits)) << 21;
4586 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
4587 (22 - bsbits)) << 22;
4589 } else if (NRL_CHECK_SIZE(EXT4_C2B(sbi, ac->ac_o_ex.fe_len),
4591 start_off = ((loff_t)ac->ac_o_ex.fe_logical >>
4592 (23 - bsbits)) << 23;
4595 start_off = (loff_t) ac->ac_o_ex.fe_logical << bsbits;
4597 ac->ac_o_ex.fe_len) << bsbits;
4608 start = max(start, rounddown(ac->ac_o_ex.fe_logical,
4609 (ext4_lblk_t)EXT4_BLOCKS_PER_GROUP(ac->ac_sb)));
4613 size = EXT_MAX_BLOCKS - start;
4616 if (ar->pleft && start <= ar->lleft) {
4617 size -= ar->lleft + 1 - start;
4618 start = ar->lleft + 1;
4620 if (ar->pright && start + size - 1 >= ar->lright)
4621 size -= start + size - ar->lright;
4624 * Trim allocation request for filesystems with artificially small
4627 if (size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb))
4628 size = EXT4_BLOCKS_PER_GROUP(ac->ac_sb);
4634 size = end - start;
4640 * ac->ac_o_ex.fe_logical & fe_len should always lie within "start" and
4646 * [pa_pstart + fe_logical - pa_lstart, fe_len/size] from the preallocated
4651 if (start + size <= ac->ac_o_ex.fe_logical ||
4652 start > ac->ac_o_ex.fe_logical) {
4653 ext4_msg(ac->ac_sb, KERN_ERR,
4656 (unsigned long) ac->ac_o_ex.fe_logical);
4659 BUG_ON(size <= 0 || size > EXT4_BLOCKS_PER_GROUP(ac->ac_sb));
4665 ac->ac_g_ex.fe_logical = start;
4666 ac->ac_g_ex.fe_len = EXT4_NUM_B2C(sbi, size);
4667 ac->ac_orig_goal_len = ac->ac_g_ex.fe_len;
4670 if (ar->pright && (ar->lright == (start + size)) &&
4671 ar->pright >= size &&
4672 ar->pright - size >= le32_to_cpu(es->s_first_data_block)) {
4674 ext4_get_group_no_and_offset(ac->ac_sb, ar->pright - size,
4675 &ac->ac_g_ex.fe_group,
4676 &ac->ac_g_ex.fe_start);
4677 ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
4679 if (ar->pleft && (ar->lleft + 1 == start) &&
4680 ar->pleft + 1 < ext4_blocks_count(es)) {
4682 ext4_get_group_no_and_offset(ac->ac_sb, ar->pleft + 1,
4683 &ac->ac_g_ex.fe_group,
4684 &ac->ac_g_ex.fe_start);
4685 ac->ac_flags |= EXT4_MB_HINT_TRY_GOAL;
4688 mb_debug(ac->ac_sb, "goal: %lld(was %lld) blocks at %u\n", size,
4694 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
4696 if (sbi->s_mb_stats && ac->ac_g_ex.fe_len >= 1) {
4697 atomic_inc(&sbi->s_bal_reqs);
4698 atomic_add(ac->ac_b_ex.fe_len, &sbi->s_bal_allocated);
4699 if (ac->ac_b_ex.fe_len >= ac->ac_o_ex.fe_len)
4700 atomic_inc(&sbi->s_bal_success);
4702 atomic_add(ac->ac_found, &sbi->s_bal_ex_scanned);
4704 atomic_add(ac->ac_cX_found[i], &sbi->s_bal_cX_ex_scanned[i]);
4707 atomic_add(ac->ac_groups_scanned, &sbi->s_bal_groups_scanned);
4708 if (ac->ac_g_ex.fe_start == ac->ac_b_ex.fe_start &&
4709 ac->ac_g_ex.fe_group == ac->ac_b_ex.fe_group)
4710 atomic_inc(&sbi->s_bal_goals);
4712 if (ac->ac_f_ex.fe_len == ac->ac_orig_goal_len)
4713 atomic_inc(&sbi->s_bal_len_goals);
4715 if (ac->ac_found > sbi->s_mb_max_to_scan)
4716 atomic_inc(&sbi->s_bal_breaks);
4719 if (ac->ac_op == EXT4_MB_HISTORY_ALLOC)
4729 * zeroed out ac->ac_b_ex.fe_len, so group_pa->pa_free is not changed.
4733 struct ext4_prealloc_space *pa = ac->ac_pa;
4738 if (ac->ac_f_ex.fe_len == 0)
4740 err = ext4_mb_load_buddy(ac->ac_sb, ac->ac_f_ex.fe_group, &e4b);
4749 ext4_lock_group(ac->ac_sb, ac->ac_f_ex.fe_group);
4750 mb_free_blocks(ac->ac_inode, &e4b, ac->ac_f_ex.fe_start,
4751 ac->ac_f_ex.fe_len);
4752 ext4_unlock_group(ac->ac_sb, ac->ac_f_ex.fe_group);
4756 if (pa->pa_type == MB_INODE_PA) {
4757 spin_lock(&pa->pa_lock);
4758 pa->pa_free += ac->ac_b_ex.fe_len;
4759 spin_unlock(&pa->pa_lock);
4769 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
4775 start = pa->pa_pstart + (ac->ac_o_ex.fe_logical - pa->pa_lstart);
4776 end = min(pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len),
4777 start + EXT4_C2B(sbi, ac->ac_o_ex.fe_len));
4778 len = EXT4_NUM_B2C(sbi, end - start);
4779 ext4_get_group_no_and_offset(ac->ac_sb, start, &ac->ac_b_ex.fe_group,
4780 &ac->ac_b_ex.fe_start);
4781 ac->ac_b_ex.fe_len = len;
4782 ac->ac_status = AC_STATUS_FOUND;
4783 ac->ac_pa = pa;
4785 BUG_ON(start < pa->pa_pstart);
4786 BUG_ON(end > pa->pa_pstart + EXT4_C2B(sbi, pa->pa_len));
4787 BUG_ON(pa->pa_free < len);
4788 BUG_ON(ac->ac_b_ex.fe_len <= 0);
4789 pa->pa_free -= len;
4791 mb_debug(ac->ac_sb, "use %llu/%d from inode pa %p\n", start, len, pa);
4800 unsigned int len = ac->ac_o_ex.fe_len;
4802 ext4_get_group_no_and_offset(ac->ac_sb, pa->pa_pstart,
4803 &ac->ac_b_ex.fe_group,
4804 &ac->ac_b_ex.fe_start);
4805 ac->ac_b_ex.fe_len = len;
4806 ac->ac_status = AC_STATUS_FOUND;
4807 ac->ac_pa = pa;
4812 * in on-disk bitmap -- see ext4_mb_release_context()
4815 mb_debug(ac->ac_sb, "use %u/%u from group pa %p\n",
4816 pa->pa_lstart, len, pa);
4833 atomic_inc(&pa->pa_count);
4836 cur_distance = abs(goal_block - cpa->pa_pstart);
4837 new_distance = abs(goal_block - pa->pa_pstart);
4843 atomic_dec(&cpa->pa_count);
4844 atomic_inc(&pa->pa_count);
4855 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
4858 if (likely(!(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY)))
4867 start = pa->pa_pstart +
4868 (ac->ac_g_ex.fe_logical - pa->pa_lstart);
4869 if (ext4_grp_offs_to_block(ac->ac_sb, &ac->ac_g_ex) != start)
4872 if (ac->ac_g_ex.fe_len > pa->pa_len -
4873 EXT4_B2C(sbi, ac->ac_g_ex.fe_logical - pa->pa_lstart))
4885 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
4887 struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
4893 /* only data can be preallocated */
4894 if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
4898 * first, try per-file preallocation by searching the inode pa rbtree.
4904 read_lock(&ei->i_prealloc_lock);
4906 if (RB_EMPTY_ROOT(&ei->i_prealloc_node)) {
4914 * (tmp_pa->pa_lstart never changes so we can skip locking for it).
4916 for (iter = ei->i_prealloc_node.rb_node; iter;
4917 iter = ext4_mb_pa_rb_next_iter(ac->ac_o_ex.fe_logical,
4918 tmp_pa->pa_lstart, iter)) {
4925 * the left adjacent pa. After this step we'd have a valid tmp_pa whose
4928 if (tmp_pa->pa_lstart > ac->ac_o_ex.fe_logical) {
4930 tmp = rb_prev(&tmp_pa->pa_node.inode_node);
4945 BUG_ON(!(tmp_pa && tmp_pa->pa_lstart <= ac->ac_o_ex.fe_logical));
4950 * valid tmp_pa which is guaranteed to be non deleted.
4952 for (iter = &tmp_pa->pa_node.inode_node;; iter = rb_prev(iter)) {
4962 spin_lock(&tmp_pa->pa_lock);
4963 if (tmp_pa->pa_deleted == 0) {
4973 spin_unlock(&tmp_pa->pa_lock);
4977 BUG_ON(!(tmp_pa && tmp_pa->pa_lstart <= ac->ac_o_ex.fe_logical));
4978 BUG_ON(tmp_pa->pa_deleted == 1);
4985 if (ac->ac_o_ex.fe_logical >= pa_logical_end(sbi, tmp_pa)) {
4986 spin_unlock(&tmp_pa->pa_lock);
4990 /* non-extent files can't have physical blocks past 2^32 */
4991 if (!(ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS)) &&
4992 (tmp_pa->pa_pstart + EXT4_C2B(sbi, tmp_pa->pa_len) >
4998 spin_unlock(&tmp_pa->pa_lock);
5002 if (tmp_pa->pa_free && likely(ext4_mb_pa_goal_check(ac, tmp_pa))) {
5003 atomic_inc(&tmp_pa->pa_count);
5005 spin_unlock(&tmp_pa->pa_lock);
5006 read_unlock(&ei->i_prealloc_lock);
5010 * We found a valid overlapping pa but couldn't use it because
5032 * called with i_data_sem held for data allocations, we can be
5036 WARN_ON_ONCE(tmp_pa->pa_free == 0);
5038 spin_unlock(&tmp_pa->pa_lock);
5040 read_unlock(&ei->i_prealloc_lock);
5043 if (!(ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC))
5047 lg = ac->ac_lg;
5050 order = fls(ac->ac_o_ex.fe_len) - 1;
5051 if (order > PREALLOC_TB_SIZE - 1)
5053 order = PREALLOC_TB_SIZE - 1;
5055 goal_block = ext4_grp_offs_to_block(ac->ac_sb, &ac->ac_g_ex);
5062 list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[i],
5064 spin_lock(&tmp_pa->pa_lock);
5065 if (tmp_pa->pa_deleted == 0 &&
5066 tmp_pa->pa_free >= ac->ac_o_ex.fe_len) {
5071 spin_unlock(&tmp_pa->pa_lock);
5084 * used in in-core bitmap. buddy must be generated from this bitmap
5110 list_for_each(cur, &grp->bb_prealloc_list) {
5112 spin_lock(&pa->pa_lock);
5113 ext4_get_group_no_and_offset(sb, pa->pa_pstart,
5115 len = pa->pa_len;
5116 spin_unlock(&pa->pa_lock);
5131 if (pa->pa_deleted) {
5133 pa->pa_type, pa->pa_pstart, pa->pa_lstart,
5134 pa->pa_len);
5138 pa->pa_deleted = 1;
5140 if (pa->pa_type == MB_INODE_PA) {
5141 ei = EXT4_I(pa->pa_inode);
5142 atomic_dec(&ei->i_prealloc_active);
5149 BUG_ON(atomic_read(&pa->pa_count));
5150 BUG_ON(pa->pa_deleted == 0);
5171 struct ext4_inode_info *ei = EXT4_I(ac->ac_inode);
5174 spin_lock(&pa->pa_lock);
5175 if (!atomic_dec_and_test(&pa->pa_count) || pa->pa_free != 0) {
5176 spin_unlock(&pa->pa_lock);
5180 if (pa->pa_deleted == 1) {
5181 spin_unlock(&pa->pa_lock);
5186 spin_unlock(&pa->pa_lock);
5188 grp_blk = pa->pa_pstart;
5190 * If doing group-based preallocation, pa_pstart may be in the
5193 if (pa->pa_type == MB_GROUP_PA)
5194 grp_blk--;
5203 * copy on-disk bitmap to buddy
5204 * mark B in on-disk bitmap
5213 list_del(&pa->pa_group_list);
5216 if (pa->pa_type == MB_INODE_PA) {
5217 write_lock(pa->pa_node_lock.inode_lock);
5218 rb_erase(&pa->pa_node.inode_node, &ei->i_prealloc_node);
5219 write_unlock(pa->pa_node_lock.inode_lock);
5222 spin_lock(pa->pa_node_lock.lg_lock);
5223 list_del_rcu(&pa->pa_node.lg_list);
5224 spin_unlock(pa->pa_node_lock.lg_lock);
5225 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
5231 struct rb_node **iter = &root->rb_node, *parent = NULL;
5240 iter_start = iter_pa->pa_lstart;
5241 new_start = new_pa->pa_lstart;
5245 iter = &((*iter)->rb_left);
5247 iter = &((*iter)->rb_right);
5260 struct super_block *sb = ac->ac_sb;
5267 BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
5268 BUG_ON(ac->ac_status != AC_STATUS_FOUND);
5269 BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
5270 BUG_ON(ac->ac_pa == NULL);
5272 pa = ac->ac_pa;
5274 if (ac->ac_b_ex.fe_len < ac->ac_orig_goal_len) {
5276 .fe_logical = ac->ac_g_ex.fe_logical,
5277 .fe_len = ac->ac_orig_goal_len,
5280 loff_t o_ex_end = extent_logical_end(sbi, &ac->ac_o_ex);
5287 * orig_ex:2045/2055(10), isize:8417280 -> normalized:0/2048
5288 * best_ex:0/200(200) -> adjusted: 1848/2048(200)
5290 BUG_ON(ac->ac_g_ex.fe_logical > ac->ac_o_ex.fe_logical);
5291 BUG_ON(ac->ac_g_ex.fe_len < ac->ac_o_ex.fe_len);
5304 ex.fe_len = ac->ac_b_ex.fe_len;
5306 ex.fe_logical = orig_goal_end - EXT4_C2B(sbi, ex.fe_len);
5307 if (ac->ac_o_ex.fe_logical >= ex.fe_logical)
5310 ex.fe_logical = ac->ac_g_ex.fe_logical;
5314 ex.fe_logical = ac->ac_o_ex.fe_logical;
5316 ac->ac_b_ex.fe_logical = ex.fe_logical;
5318 BUG_ON(ac->ac_o_ex.fe_logical < ac->ac_b_ex.fe_logical);
5322 pa->pa_lstart = ac->ac_b_ex.fe_logical;
5323 pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
5324 pa->pa_len = ac->ac_b_ex.fe_len;
5325 pa->pa_free = pa->pa_len;
5326 spin_lock_init(&pa->pa_lock);
5327 INIT_LIST_HEAD(&pa->pa_group_list);
5328 pa->pa_deleted = 0;
5329 pa->pa_type = MB_INODE_PA;
5331 mb_debug(sb, "new inode pa %p: %llu/%d for %u\n", pa, pa->pa_pstart,
5332 pa->pa_len, pa->pa_lstart);
5335 atomic_add(pa->pa_free, &sbi->s_mb_preallocated);
5338 ei = EXT4_I(ac->ac_inode);
5339 grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
5343 pa->pa_node_lock.inode_lock = &ei->i_prealloc_lock;
5344 pa->pa_inode = ac->ac_inode;
5346 list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
5348 write_lock(pa->pa_node_lock.inode_lock);
5349 ext4_mb_pa_rb_insert(&ei->i_prealloc_node, &pa->pa_node.inode_node);
5350 write_unlock(pa->pa_node_lock.inode_lock);
5351 atomic_inc(&ei->i_prealloc_active);
5360 struct super_block *sb = ac->ac_sb;
5366 BUG_ON(ac->ac_o_ex.fe_len >= ac->ac_b_ex.fe_len);
5367 BUG_ON(ac->ac_status != AC_STATUS_FOUND);
5368 BUG_ON(!S_ISREG(ac->ac_inode->i_mode));
5369 BUG_ON(ac->ac_pa == NULL);
5371 pa = ac->ac_pa;
5373 pa->pa_pstart = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
5374 pa->pa_lstart = pa->pa_pstart;
5375 pa->pa_len = ac->ac_b_ex.fe_len;
5376 pa->pa_free = pa->pa_len;
5377 spin_lock_init(&pa->pa_lock);
5378 INIT_LIST_HEAD(&pa->pa_node.lg_list);
5379 INIT_LIST_HEAD(&pa->pa_group_list);
5380 pa->pa_deleted = 0;
5381 pa->pa_type = MB_GROUP_PA;
5383 mb_debug(sb, "new group pa %p: %llu/%d for %u\n", pa, pa->pa_pstart,
5384 pa->pa_len, pa->pa_lstart);
5388 atomic_add(pa->pa_free, &EXT4_SB(sb)->s_mb_preallocated);
5390 grp = ext4_get_group_info(sb, ac->ac_b_ex.fe_group);
5393 lg = ac->ac_lg;
5396 pa->pa_node_lock.lg_lock = &lg->lg_prealloc_lock;
5397 pa->pa_inode = NULL;
5399 list_add(&pa->pa_group_list, &grp->bb_prealloc_list);
5409 if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
5416 * finds all unused blocks in on-disk bitmap, frees them in
5417 * in-core bitmap and buddy.
5421 * TODO: optimize the case when there are no in-core structures yet
5427 struct super_block *sb = e4b->bd_sb;
5436 BUG_ON(pa->pa_deleted == 0);
5437 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);
5438 grp_blk_start = pa->pa_pstart - EXT4_C2B(sbi, bit);
5439 BUG_ON(group != e4b->bd_group && pa->pa_len != 0);
5440 end = bit + pa->pa_len;
5443 bit = mb_find_next_zero_bit(bitmap_bh->b_data, end, bit);
5446 next = mb_find_next_bit(bitmap_bh->b_data, end, bit);
5449 (unsigned) next - bit, (unsigned) group);
5450 free += next - bit;
5452 trace_ext4_mballoc_discard(sb, NULL, group, bit, next - bit);
5455 next - bit);
5456 mb_free_blocks(pa->pa_inode, e4b, bit, next - bit);
5459 if (free != pa->pa_free) {
5460 ext4_msg(e4b->bd_sb, KERN_CRIT,
5462 pa, (unsigned long) pa->pa_lstart,
5463 (unsigned long) pa->pa_pstart,
5464 pa->pa_len);
5466 free, pa->pa_free);
5472 atomic_add(free, &sbi->s_mb_discarded);
5479 struct super_block *sb = e4b->bd_sb;
5484 BUG_ON(pa->pa_deleted == 0);
5485 ext4_get_group_no_and_offset(sb, pa->pa_pstart, &group, &bit);
5486 if (unlikely(group != e4b->bd_group && pa->pa_len != 0)) {
5488 e4b->bd_group, group, pa->pa_pstart);
5491 mb_free_blocks(pa->pa_inode, e4b, bit, pa->pa_len);
5492 atomic_add(pa->pa_len, &EXT4_SB(sb)->s_mb_discarded);
5493 trace_ext4_mballoc_discard(sb, NULL, group, bit, pa->pa_len);
5500 * - when do we discard
5502 * - how many do we discard
5521 if (list_empty(&grp->bb_prealloc_list))
5527 ext4_error_err(sb, -err,
5543 &grp->bb_prealloc_list, pa_group_list) {
5544 spin_lock(&pa->pa_lock);
5545 if (atomic_read(&pa->pa_count)) {
5546 spin_unlock(&pa->pa_lock);
5550 if (pa->pa_deleted) {
5551 spin_unlock(&pa->pa_lock);
5562 free += pa->pa_free;
5564 spin_unlock(&pa->pa_lock);
5566 list_del(&pa->pa_group_list);
5567 list_add(&pa->u.pa_tmp_list, &list);
5574 if (pa->pa_type == MB_GROUP_PA) {
5575 spin_lock(pa->pa_node_lock.lg_lock);
5576 list_del_rcu(&pa->pa_node.lg_list);
5577 spin_unlock(pa->pa_node_lock.lg_lock);
5579 write_lock(pa->pa_node_lock.inode_lock);
5580 ei = EXT4_I(pa->pa_inode);
5581 rb_erase(&pa->pa_node.inode_node, &ei->i_prealloc_node);
5582 write_unlock(pa->pa_node_lock.inode_lock);
5585 list_del(&pa->u.pa_tmp_list);
5587 if (pa->pa_type == MB_GROUP_PA) {
5589 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
5601 free, group, grp->bb_free);
5606 * releases all non-used preallocated blocks for given inode
5612 * FIXME!! Make sure it is valid at all the call sites
5617 struct super_block *sb = inode->i_sb;
5626 if (!S_ISREG(inode->i_mode))
5629 if (EXT4_SB(sb)->s_mount_state & EXT4_FC_REPLAY)
5633 inode->i_ino);
5635 atomic_read(&ei->i_prealloc_active));
5639 write_lock(&ei->i_prealloc_lock);
5640 for (iter = rb_first(&ei->i_prealloc_node); iter;
5644 BUG_ON(pa->pa_node_lock.inode_lock != &ei->i_prealloc_lock);
5646 spin_lock(&pa->pa_lock);
5647 if (atomic_read(&pa->pa_count)) {
5648 /* this shouldn't happen often - nobody should
5650 spin_unlock(&pa->pa_lock);
5651 write_unlock(&ei->i_prealloc_lock);
5653 "uh-oh! used pa while discarding");
5659 if (pa->pa_deleted == 0) {
5661 spin_unlock(&pa->pa_lock);
5662 rb_erase(&pa->pa_node.inode_node, &ei->i_prealloc_node);
5663 list_add(&pa->u.pa_tmp_list, &list);
5668 spin_unlock(&pa->pa_lock);
5669 write_unlock(&ei->i_prealloc_lock);
5674 * ->clear_inode() the inode will get freed
5677 * freed memory, bad-bad-bad */
5681 * of ->clear_inode(), but not in case of
5686 write_unlock(&ei->i_prealloc_lock);
5689 BUG_ON(pa->pa_type != MB_INODE_PA);
5690 group = ext4_get_group_number(sb, pa->pa_pstart);
5695 ext4_error_err(sb, -err, "Error %d loading buddy information for %u",
5703 ext4_error_err(sb, -err, "Error %d reading block bitmap for %u",
5710 list_del(&pa->pa_group_list);
5717 list_del(&pa->u.pa_tmp_list);
5729 return -ENOMEM;
5730 atomic_set(&pa->pa_count, 1);
5731 ac->ac_pa = pa;
5737 struct ext4_prealloc_space *pa = ac->ac_pa;
5740 ac->ac_pa = NULL;
5741 WARN_ON(!atomic_dec_and_test(&pa->pa_count));
5745 * been added to grp->bb_prealloc_list. So we don't need to lock it
5747 pa->pa_deleted = 1;
5770 list_for_each(cur, &grp->bb_prealloc_list) {
5773 spin_lock(&pa->pa_lock);
5774 ext4_get_group_no_and_offset(sb, pa->pa_pstart,
5776 spin_unlock(&pa->pa_lock);
5778 pa->pa_len);
5781 mb_debug(sb, "%u: %d/%d\n", i, grp->bb_free,
5782 grp->bb_fragments);
5788 struct super_block *sb = ac->ac_sb;
5796 ac->ac_status, ac->ac_flags);
5800 (unsigned long)ac->ac_o_ex.fe_group,
5801 (unsigned long)ac->ac_o_ex.fe_start,
5802 (unsigned long)ac->ac_o_ex.fe_len,
5803 (unsigned long)ac->ac_o_ex.fe_logical,
5804 (unsigned long)ac->ac_g_ex.fe_group,
5805 (unsigned long)ac->ac_g_ex.fe_start,
5806 (unsigned long)ac->ac_g_ex.fe_len,
5807 (unsigned long)ac->ac_g_ex.fe_logical,
5808 (unsigned long)ac->ac_b_ex.fe_group,
5809 (unsigned long)ac->ac_b_ex.fe_start,
5810 (unsigned long)ac->ac_b_ex.fe_len,
5811 (unsigned long)ac->ac_b_ex.fe_logical,
5812 (int)ac->ac_criteria);
5813 mb_debug(sb, "%u found", ac->ac_found);
5814 mb_debug(sb, "used pa: %s, ", str_yes_no(ac->ac_pa));
5815 if (ac->ac_pa)
5816 mb_debug(sb, "pa_type %s\n", ac->ac_pa->pa_type == MB_GROUP_PA ?
5826 ext4_mb_show_pa(ac->ac_sb);
5839 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
5840 int bsbits = ac->ac_sb->s_blocksize_bits;
5844 if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
5847 if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
5850 group_pa_eligible = sbi->s_mb_group_prealloc > 0;
5852 size = extent_logical_end(sbi, &ac->ac_o_ex);
5853 isize = (i_size_read(ac->ac_inode) + ac->ac_sb->s_blocksize - 1)
5858 !inode_is_open_for_write(ac->ac_inode))
5863 if (size > sbi->s_mb_stream_request)
5868 ac->ac_flags |= EXT4_MB_STREAM_ALLOC;
5870 ac->ac_flags |= EXT4_MB_HINT_NOPREALLOC;
5874 BUG_ON(ac->ac_lg != NULL);
5880 ac->ac_lg = raw_cpu_ptr(sbi->s_locality_groups);
5883 ac->ac_flags |= EXT4_MB_HINT_GROUP_ALLOC;
5886 mutex_lock(&ac->ac_lg->lg_mutex);
5893 struct super_block *sb = ar->inode->i_sb;
5895 struct ext4_super_block *es = sbi->s_es;
5902 len = ar->len;
5909 goal = ar->goal;
5910 if (goal < le32_to_cpu(es->s_first_data_block) ||
5912 goal = le32_to_cpu(es->s_first_data_block);
5916 ac->ac_b_ex.fe_logical = EXT4_LBLK_CMASK(sbi, ar->logical);
5917 ac->ac_status = AC_STATUS_CONTINUE;
5918 ac->ac_sb = sb;
5919 ac->ac_inode = ar->inode;
5920 ac->ac_o_ex.fe_logical = ac->ac_b_ex.fe_logical;
5921 ac->ac_o_ex.fe_group = group;
5922 ac->ac_o_ex.fe_start = block;
5923 ac->ac_o_ex.fe_len = len;
5924 ac->ac_g_ex = ac->ac_o_ex;
5925 ac->ac_orig_goal_len = ac->ac_g_ex.fe_len;
5926 ac->ac_flags = ar->flags;
5934 (unsigned) ar->len, (unsigned) ar->logical,
5935 (unsigned) ar->goal, ac->ac_flags, ac->ac_2order,
5936 (unsigned) ar->lleft, (unsigned) ar->pleft,
5937 (unsigned) ar->lright, (unsigned) ar->pright,
5938 inode_is_open_for_write(ar->inode) ? "" : "non-");
5953 spin_lock(&lg->lg_prealloc_lock);
5954 list_for_each_entry_rcu(pa, &lg->lg_prealloc_list[order],
5956 lockdep_is_held(&lg->lg_prealloc_lock)) {
5957 spin_lock(&pa->pa_lock);
5958 if (atomic_read(&pa->pa_count)) {
5964 spin_unlock(&pa->pa_lock);
5967 if (pa->pa_deleted) {
5968 spin_unlock(&pa->pa_lock);
5972 BUG_ON(pa->pa_type != MB_GROUP_PA);
5976 spin_unlock(&pa->pa_lock);
5978 list_del_rcu(&pa->pa_node.lg_list);
5979 list_add(&pa->u.pa_tmp_list, &discard_list);
5981 total_entries--;
5992 spin_unlock(&lg->lg_prealloc_lock);
5997 group = ext4_get_group_number(sb, pa->pa_pstart);
6001 ext4_error_err(sb, -err, "Error %d loading buddy information for %u",
6006 list_del(&pa->pa_group_list);
6011 list_del(&pa->u.pa_tmp_list);
6012 call_rcu(&(pa)->u.pa_rcu, ext4_mb_pa_callback);
6028 struct super_block *sb = ac->ac_sb;
6029 struct ext4_locality_group *lg = ac->ac_lg;
6030 struct ext4_prealloc_space *tmp_pa, *pa = ac->ac_pa;
6032 order = fls(pa->pa_free) - 1;
6033 if (order > PREALLOC_TB_SIZE - 1)
6035 order = PREALLOC_TB_SIZE - 1;
6037 spin_lock(&lg->lg_prealloc_lock);
6038 list_for_each_entry_rcu(tmp_pa, &lg->lg_prealloc_list[order],
6040 lockdep_is_held(&lg->lg_prealloc_lock)) {
6041 spin_lock(&tmp_pa->pa_lock);
6042 if (tmp_pa->pa_deleted) {
6043 spin_unlock(&tmp_pa->pa_lock);
6046 if (!added && pa->pa_free < tmp_pa->pa_free) {
6048 list_add_tail_rcu(&pa->pa_node.lg_list,
6049 &tmp_pa->pa_node.lg_list);
6056 spin_unlock(&tmp_pa->pa_lock);
6060 list_add_tail_rcu(&pa->pa_node.lg_list,
6061 &lg->lg_prealloc_list[order]);
6062 spin_unlock(&lg->lg_prealloc_lock);
6064 /* Now trim the list to be not more than 8 elements */
6075 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
6076 struct ext4_prealloc_space *pa = ac->ac_pa;
6078 if (pa->pa_type == MB_GROUP_PA) {
6080 spin_lock(&pa->pa_lock);
6081 pa->pa_pstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
6082 pa->pa_lstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len);
6083 pa->pa_free -= ac->ac_b_ex.fe_len;
6084 pa->pa_len -= ac->ac_b_ex.fe_len;
6085 spin_unlock(&pa->pa_lock);
6093 if (likely(pa->pa_free)) {
6094 spin_lock(pa->pa_node_lock.lg_lock);
6095 list_del_rcu(&pa->pa_node.lg_list);
6096 spin_unlock(pa->pa_node_lock.lg_lock);
6101 ext4_mb_put_pa(ac, ac->ac_sb, pa);
6103 if (ac->ac_bitmap_folio)
6104 folio_put(ac->ac_bitmap_folio);
6105 if (ac->ac_buddy_folio)
6106 folio_put(ac->ac_buddy_folio);
6107 if (ac->ac_flags & EXT4_MB_HINT_GROUP_ALLOC)
6108 mutex_unlock(&ac->ac_lg->lg_mutex);
6127 needed -= ret;
6146 freed = ext4_mb_discard_preallocations(sb, ac->ac_o_ex.fe_len);
6152 if (!(ac->ac_flags & EXT4_MB_STRICT_CHECK) || seq_retry != *seq) {
6153 ac->ac_flags |= EXT4_MB_STRICT_CHECK;
6172 struct super_block *sb = ar->inode->i_sb;
6179 struct ext4_super_block *es = sbi->s_es;
6181 goal = ar->goal;
6182 if (goal < le32_to_cpu(es->s_first_data_block) ||
6184 goal = le32_to_cpu(es->s_first_data_block);
6186 ar->len = 0;
6188 for (nr = ext4_get_groups_count(sb); nr > 0; nr--) {
6197 i = mb_find_next_zero_bit(bitmap_bh->b_data, max,
6219 *errp = -ENOSPC;
6225 ar->len = 1;
6249 sb = ar->inode->i_sb;
6253 if (sbi->s_mount_state & EXT4_FC_REPLAY)
6257 if (ext4_is_quota_file(ar->inode))
6258 ar->flags |= EXT4_MB_USE_ROOT_BLOCKS;
6260 if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0) {
6265 while (ar->len &&
6266 ext4_claim_free_clusters(sbi, ar->len, ar->flags)) {
6270 ar->len = ar->len >> 1;
6272 if (!ar->len) {
6274 *errp = -ENOSPC;
6277 reserv_clstrs = ar->len;
6278 if (ar->flags & EXT4_MB_USE_ROOT_BLOCKS) {
6279 dquot_alloc_block_nofail(ar->inode,
6280 EXT4_C2B(sbi, ar->len));
6282 while (ar->len &&
6283 dquot_alloc_block(ar->inode,
6284 EXT4_C2B(sbi, ar->len))) {
6286 ar->flags |= EXT4_MB_HINT_NOPREALLOC;
6287 ar->len--;
6290 inquota = ar->len;
6291 if (ar->len == 0) {
6292 *errp = -EDQUOT;
6299 ar->len = 0;
6300 *errp = -ENOMEM;
6306 ac->ac_op = EXT4_MB_HISTORY_PREALLOC;
6309 ac->ac_op = EXT4_MB_HISTORY_ALLOC;
6319 * pa allocated above is added to grp->bb_prealloc_list only
6321 * ac->ac_status == AC_STATUS_FOUND.
6322 * And error from above mean ac->ac_status != AC_STATUS_FOUND
6330 if (ac->ac_status == AC_STATUS_FOUND &&
6331 ac->ac_o_ex.fe_len >= ac->ac_f_ex.fe_len)
6334 if (likely(ac->ac_status == AC_STATUS_FOUND)) {
6340 block = ext4_grp_offs_to_block(sb, &ac->ac_b_ex);
6341 ar->len = ac->ac_b_ex.fe_len;
6352 *errp = -ENOSPC;
6357 ac->ac_b_ex.fe_len = 0;
6358 ar->len = 0;
6364 if (inquota && ar->len < inquota)
6365 dquot_free_block(ar->inode, EXT4_C2B(sbi, inquota - ar->len));
6366 if (!ar->len) {
6367 if ((ar->flags & EXT4_MB_DELALLOC_RESERVED) == 0)
6369 percpu_counter_sub(&sbi->s_dirtyclusters_counter,
6379 * We can merge two free data extents only if the physical blocks
6387 if (entry1->efd_tid != entry2->efd_tid)
6389 if (entry1->efd_start_cluster + entry1->efd_count !=
6390 entry2->efd_start_cluster)
6392 if (WARN_ON_ONCE(entry1->efd_group != entry2->efd_group))
6402 entry1->efd_count += entry2->efd_count;
6403 spin_lock(&sbi->s_md_lock);
6404 list_del(&entry2->efd_list);
6405 spin_unlock(&sbi->s_md_lock);
6406 rb_erase(&entry2->efd_node, root);
6417 node = rb_prev(&entry->efd_node);
6433 node = rb_next(&entry->efd_node);
6446 ext4_group_t group = e4b->bd_group;
6448 ext4_grpblk_t clusters = new_entry->efd_count;
6450 struct ext4_group_info *db = e4b->bd_info;
6451 struct super_block *sb = e4b->bd_sb;
6453 struct rb_root *root = &db->bb_free_root;
6454 struct rb_node **n = &root->rb_node;
6458 BUG_ON(e4b->bd_bitmap_folio == NULL);
6459 BUG_ON(e4b->bd_buddy_folio == NULL);
6461 new_node = &new_entry->efd_node;
6462 cluster = new_entry->efd_start_cluster;
6468 * on-disk bitmap and lose not-yet-available
6470 folio_get(e4b->bd_buddy_folio);
6471 folio_get(e4b->bd_bitmap_folio);
6476 if (cluster < entry->efd_start_cluster)
6477 n = &(*n)->rb_left;
6478 else if (cluster >= (entry->efd_start_cluster + entry->efd_count))
6479 n = &(*n)->rb_right;
6484 "Block already on to-be-freed list");
6490 atomic_add(clusters, &sbi->s_mb_free_pending);
6496 entry->efd_start_cluster = cluster;
6497 entry->efd_count += new_entry->efd_count;
6503 entry->efd_count += new_entry->efd_count;
6512 spin_lock(&sbi->s_md_lock);
6513 list_add_tail(&new_entry->efd_list, &sbi->s_freed_data_list[new_entry->efd_tid & 1]);
6514 spin_unlock(&sbi->s_md_lock);
6520 struct super_block *sb = inode->i_sb;
6532 * ext4_mb_clear_bb() -- helper function for freeing blocks.
6544 struct super_block *sb = inode->i_sb;
6560 ext4_error(sb, "Freeing blocks in system zone - "
6580 overflow = EXT4_C2B(sbi, bit) + count -
6582 count -= overflow;
6597 ext4_error(sb, "Freeing blocks in system zone - "
6620 * written in writeback mode since writeback mode has weak data
6633 new_entry->efd_start_cluster = bit;
6634 new_entry->efd_group = block_group;
6635 new_entry->efd_count = count_clusters;
6636 new_entry->efd_tid = handle->h_transaction->t_tid;
6648 if (err == -EOPNOTSUPP)
6673 percpu_counter_add(&sbi->s_freeclusters_counter,
6693 * ext4_free_blocks() -- Free given blocks and update quota
6705 struct super_block *sb = inode->i_sb;
6713 BUG_ON(block != bh->b_blocknr);
6715 block = bh->b_blocknr;
6718 if (sbi->s_mount_state & EXT4_FC_REPLAY) {
6727 ext4_error(sb, "Freeing blocks not in datazone - "
6753 overflow = sbi->s_cluster_ratio - overflow;
6756 count -= overflow;
6760 block -= overflow;
6770 count -= overflow;
6774 count += sbi->s_cluster_ratio - overflow;
6786 bh = sb_find_get_block_nonatomic(inode->i_sb,
6796 * ext4_group_add_blocks() -- Add given blocks to an existing group
6813 ext4_fsblk_t last_cluster = EXT4_B2C(sbi, block + count - 1);
6814 unsigned long cluster_count = last_cluster - first_cluster + 1;
6817 ext4_debug("Adding block(s) %llu-%llu\n", block, block + count - 1);
6830 err = -EINVAL;
6839 ext4_error(sb, "Adding blocks in system zones - "
6842 err = -EINVAL;
6858 percpu_counter_add(&sbi->s_freeclusters_counter,
6869 * ext4_trim_extent -- function to TRIM one single free extent in the group
6872 * @count: number of blocks to TRIM
6875 * Trim "count" blocks starting at "start" in the "group". To assure that no
6885 ext4_group_t group = e4b->bd_group;
6913 if (grp < (ext4_get_groups_count(sb) - 1))
6916 nr_clusters_in_group = (ext4_blocks_count(EXT4_SB(sb)->s_es) -
6920 return nr_clusters_in_group - 1;
6931 __acquires(ext4_group_lock_ptr(sb, e4b->bd_group))
6932 __releases(ext4_group_lock_ptr(sb, e4b->bd_group))
6938 if (unlikely(EXT4_MB_GRP_BBITMAP_CORRUPT(e4b->bd_info)))
6941 last = ext4_last_grp_cluster(sb, e4b->bd_group);
6942 bitmap = e4b->bd_bitmap;
6946 start = max(e4b->bd_info->bb_first_free, start);
6959 if ((next - start) >= minblocks) {
6960 int ret = ext4_trim_extent(sb, start, next - start, e4b);
6962 if (ret && ret != -EOPNOTSUPP)
6964 count += next - start;
6966 free_count += next - start;
6973 ext4_unlock_group(sb, e4b->bd_group);
6975 ext4_lock_group(sb, e4b->bd_group);
6978 if ((e4b->bd_info->bb_free - free_count) < minblocks)
6983 EXT4_MB_GRP_SET_TRIMMED(e4b->bd_info);
6989 * ext4_trim_all_free -- function to trim all free space in alloc. group
6998 * bitmap. Then issue a TRIM command on this extent and free the extent in
7021 minblocks < EXT4_SB(sb)->s_last_trim_minblks)
7036 * ext4_trim_fs() -- trim ioctl handle function
7040 * start: First Byte to trim
7041 * len: number of Bytes to trim from start
7045 * is invoked to trim all free space.
7049 unsigned int discard_granularity = bdev_discard_granularity(sb->s_bdev);
7055 le32_to_cpu(EXT4_SB(sb)->s_es->s_first_data_block);
7056 ext4_fsblk_t max_blks = ext4_blocks_count(EXT4_SB(sb)->s_es);
7059 start = range->start >> sb->s_blocksize_bits;
7060 end = start + (range->len >> sb->s_blocksize_bits) - 1;
7062 range->minlen >> sb->s_blocksize_bits);
7066 range->len < sb->s_blocksize)
7067 return -EINVAL;
7068 /* No point to try to trim less than discard granularity */
7069 if (range->minlen < discard_granularity) {
7071 discard_granularity >> sb->s_blocksize_bits);
7075 if (end >= max_blks - 1)
7076 end = max_blks - 1;
7089 end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;
7106 * always be EXT4_CLUSTERS_PER_GROUP(sb)-1, so we only need to
7112 if (grp->bb_free >= minlen) {
7130 EXT4_SB(sb)->s_last_trim_minblks = minlen;
7133 range->len = EXT4_C2B(EXT4_SB(sb), trimmed) << sb->s_blocksize_bits;
7160 start = max(e4b.bd_info->bb_first_free, first);
7162 end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;
7167 error = meta_formatter(sb, group, first, start - first,
7180 error = formatter(sb, group, start, next - start, priv);
7196 #include "mballoc-test.c"