Lines Matching +full:last +full:- +full:level
1 // SPDX-License-Identifier: GPL-2.0
11 * Laboratoire MASI - Institut Blaise Pascal
20 * Goal-directed block allocation by Stephen Tweedie
39 p->key = *(p->p = v); in add_chain()
40 p->bh = bh; in add_chain()
44 * ext4_block_to_path - parse the block number into array of offsets
48 * @boundary: set this non-zero if the referred-to block is likely to be
52 * for UNIX filesystems - tree of pointers anchored in the inode, with
54 * This function translates the block number into path in that tree -
61 * inode->i_sb).
65 * Portability note: the last comparison (check that we fit into triple
67 * architecture with 32-bit longs and 8Kb pages we might get into trouble
69 * kill us on x86. Oh, well, at least the sign propagation does not matter -
78 int ptrs = EXT4_ADDR_PER_BLOCK(inode->i_sb); in ext4_block_to_path()
79 int ptrs_bits = EXT4_ADDR_PER_BLOCK_BITS(inode->i_sb); in ext4_block_to_path()
89 } else if ((i_block -= direct_blocks) < indirect_blocks) { in ext4_block_to_path()
93 } else if ((i_block -= indirect_blocks) < double_blocks) { in ext4_block_to_path()
96 offsets[n++] = i_block & (ptrs - 1); in ext4_block_to_path()
98 } else if (((i_block -= double_blocks) >> (ptrs_bits * 2)) < ptrs) { in ext4_block_to_path()
101 offsets[n++] = (i_block >> ptrs_bits) & (ptrs - 1); in ext4_block_to_path()
102 offsets[n++] = i_block & (ptrs - 1); in ext4_block_to_path()
105 ext4_warning(inode->i_sb, "block %lu > max in inode %lu", in ext4_block_to_path()
107 indirect_blocks + double_blocks, inode->i_ino); in ext4_block_to_path()
110 *boundary = final - 1 - (i_block & (ptrs - 1)); in ext4_block_to_path()
115 * ext4_get_branch - read the chain of indirect blocks leading to data
117 * @depth: depth of the chain (1 - direct pointer, etc.)
123 * if everything went OK or the pointer to the last filled triple
125 * the number of (i+1)-th block in the chain (as it is stored in memory,
126 * i.e. little-endian 32-bit), chain[i].p contains the address of that
127 * number (it points into struct inode for i==0 and into the bh->b_data
128 * for i>0) and chain[i].bh points to the buffer_head of i-th indirect
135 * (pointer to last triple returned, *@err == 0)
137 * (ditto, *@err == -EIO)
138 * or when it reads all @depth-1 indirect blocks successfully and finds
142 * down_read(&EXT4_I(inode)->i_data_sem)
148 struct super_block *sb = inode->i_sb; in ext4_get_branch()
151 int ret = -EIO; in ext4_get_branch()
155 add_chain(chain, NULL, EXT4_I(inode)->i_data + *offsets); in ext4_get_branch()
156 if (!p->key) in ext4_get_branch()
158 while (--depth) { in ext4_get_branch()
159 bh = sb_getblk(sb, le32_to_cpu(p->key)); in ext4_get_branch()
161 ret = -ENOMEM; in ext4_get_branch()
177 add_chain(++p, bh, (__le32 *)bh->b_data + *++offsets); in ext4_get_branch()
179 if (!p->key) in ext4_get_branch()
191 * ext4_find_near - find a place for allocation with sufficient locality
198 * + if there is a block to the left of our position - allocate near it.
199 * + if pointer will live in indirect block - allocate near that block.
200 * + if pointer will live in inode - allocate in the same
206 * files will be close-by on-disk.
213 __le32 *start = ind->bh ? (__le32 *) ind->bh->b_data : ei->i_data; in ext4_find_near()
217 for (p = ind->p - 1; p >= start; p--) { in ext4_find_near()
223 if (ind->bh) in ext4_find_near()
224 return ind->bh->b_blocknr; in ext4_find_near()
234 * ext4_find_goal - find a preferred place for allocation.
237 * @partial: pointer to the last triple within a chain
241 * Because this is only used for non-extent files, we limit the block nr
259 * ext4_blks_to_allocate - Look up the block map and count the number
297 * ext4_alloc_branch() - allocate and set up a chain of blocks
304 * This function allocates blocks, zeroes out all but the last one,
309 * we had read the existing part of chain and partial points to the last
310 * triple of that (one with zero ->key). Upon the exit we have the same
312 * place chain is disconnected - *branch->p is still zero (we did not
313 * set the last link), but branch->key contains the number that should
314 * be placed into *branch->p to fill that gap.
318 * ext4_alloc_block() (normally -ENOSPC). Otherwise we set the chain
335 ar->goal = new_blocks[i] = ext4_new_meta_blocks(handle, in ext4_alloc_branch()
336 ar->inode, ar->goal, in ext4_alloc_branch()
337 ar->flags & EXT4_MB_DELALLOC_RESERVED, in ext4_alloc_branch()
343 i--; in ext4_alloc_branch()
350 bh = branch[i].bh = sb_getblk(ar->inode->i_sb, new_blocks[i-1]); in ext4_alloc_branch()
352 err = -ENOMEM; in ext4_alloc_branch()
357 err = ext4_journal_get_create_access(handle, ar->inode->i_sb, in ext4_alloc_branch()
364 memset(bh->b_data, 0, bh->b_size); in ext4_alloc_branch()
365 p = branch[i].p = (__le32 *) bh->b_data + offsets[i]; in ext4_alloc_branch()
369 len = ar->len; in ext4_alloc_branch()
378 err = ext4_handle_dirty_metadata(handle, ar->inode, bh); in ext4_alloc_branch()
386 ext4_free_blocks(handle, ar->inode, NULL, new_blocks[i], in ext4_alloc_branch()
387 ar->len, 0); in ext4_alloc_branch()
388 i--; in ext4_alloc_branch()
390 for (; i >= 0; i--) { in ext4_alloc_branch()
400 ext4_free_blocks(handle, ar->inode, branch[i+1].bh, in ext4_alloc_branch()
408 * ext4_splice_branch() - splice the allocated branch onto inode.
415 * inode (->i_blocks, etc.). In case of success we end up with the full
431 if (where->bh) { in ext4_splice_branch()
432 BUFFER_TRACE(where->bh, "get_write_access"); in ext4_splice_branch()
433 err = ext4_journal_get_write_access(handle, ar->inode->i_sb, in ext4_splice_branch()
434 where->bh, EXT4_JTR_NONE); in ext4_splice_branch()
440 *where->p = where->key; in ext4_splice_branch()
446 if (num == 0 && ar->len > 1) { in ext4_splice_branch()
447 current_block = le32_to_cpu(where->key) + 1; in ext4_splice_branch()
448 for (i = 1; i < ar->len; i++) in ext4_splice_branch()
449 *(where->p + i) = cpu_to_le32(current_block++); in ext4_splice_branch()
454 if (where->bh) { in ext4_splice_branch()
460 * the new i_size. But that is not done here - it is done in in ext4_splice_branch()
461 * generic_commit_write->__mark_inode_dirty->ext4_dirty_inode. in ext4_splice_branch()
464 BUFFER_TRACE(where->bh, "call ext4_handle_dirty_metadata"); in ext4_splice_branch()
465 err = ext4_handle_dirty_metadata(handle, ar->inode, where->bh); in ext4_splice_branch()
472 err = ext4_mark_inode_dirty(handle, ar->inode); in ext4_splice_branch()
486 ext4_free_blocks(handle, ar->inode, where[i].bh, 0, 1, in ext4_splice_branch()
489 ext4_free_blocks(handle, ar->inode, NULL, le32_to_cpu(where[num].key), in ext4_splice_branch()
490 ar->len, 0); in ext4_splice_branch()
496 * The ext4_ind_map_blocks() function handles non-extents inodes
497 * (i.e., using the traditional indirect/double-indirect i_blocks
504 * set the last missing link (that will protect us from any truncate-generated
505 * removals - all blocks on the path are immune now) and possibly force the
508 * allocations is needed - we simply release blocks and do not touch anything
518 * down_write(&EXT4_I(inode)->i_data_sem) if allocating filesystem
520 * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system
528 int err = -EIO; in ext4_ind_map_blocks()
538 trace_ext4_ind_map_blocks_enter(inode, map->m_lblk, map->m_len, flags); in ext4_ind_map_blocks()
541 depth = ext4_block_to_path(inode, map->m_lblk, offsets, in ext4_ind_map_blocks()
549 /* Simplest case - block found, no allocation needed */ in ext4_ind_map_blocks()
551 first_block = le32_to_cpu(chain[depth - 1].key); in ext4_ind_map_blocks()
554 while (count < map->m_len && count <= blocks_to_boundary) { in ext4_ind_map_blocks()
557 blk = le32_to_cpu(*(chain[depth-1].p + count)); in ext4_ind_map_blocks()
567 /* Next simple case - plain lookup failed */ in ext4_ind_map_blocks()
569 unsigned epb = inode->i_sb->s_blocksize / sizeof(u32); in ext4_ind_map_blocks()
574 * level we count number of complete empty subtrees beyond in ext4_ind_map_blocks()
579 for (i = partial - chain + 1; i < depth; i++) in ext4_ind_map_blocks()
580 count = count * epb + (epb - offsets[i] - 1); in ext4_ind_map_blocks()
583 map->m_pblk = 0; in ext4_ind_map_blocks()
584 map->m_len = min_t(unsigned int, map->m_len, count); in ext4_ind_map_blocks()
589 if (err == -EIO) in ext4_ind_map_blocks()
595 if (ext4_has_feature_bigalloc(inode->i_sb)) { in ext4_ind_map_blocks()
597 "non-extent mapped inodes with bigalloc"); in ext4_ind_map_blocks()
598 err = -EFSCORRUPTED; in ext4_ind_map_blocks()
605 ar.logical = map->m_lblk; in ext4_ind_map_blocks()
606 if (S_ISREG(inode->i_mode)) in ext4_ind_map_blocks()
613 ar.goal = ext4_find_goal(inode, map->m_lblk, partial); in ext4_ind_map_blocks()
616 indirect_blks = (chain + depth) - partial - 1; in ext4_ind_map_blocks()
623 map->m_len, blocks_to_boundary); in ext4_ind_map_blocks()
629 offsets + (partial - chain), partial); in ext4_ind_map_blocks()
636 * may need to return -EAGAIN upwards in the worst case. --sct in ext4_ind_map_blocks()
643 map->m_flags |= EXT4_MAP_NEW; in ext4_ind_map_blocks()
648 map->m_flags |= EXT4_MAP_MAPPED; in ext4_ind_map_blocks()
649 map->m_pblk = le32_to_cpu(chain[depth-1].key); in ext4_ind_map_blocks()
650 map->m_len = count; in ext4_ind_map_blocks()
652 map->m_flags |= EXT4_MAP_BOUNDARY; in ext4_ind_map_blocks()
655 partial = chain + depth - 1; /* the whole chain */ in ext4_ind_map_blocks()
658 BUFFER_TRACE(partial->bh, "call brelse"); in ext4_ind_map_blocks()
659 brelse(partial->bh); in ext4_ind_map_blocks()
660 partial--; in ext4_ind_map_blocks()
675 * N/EXT4_ADDR_PER_BLOCK(inode->i_sb) + 1 indirect blocks, in ext4_ind_trans_blocks()
678 return DIV_ROUND_UP(nrblocks, EXT4_ADDR_PER_BLOCK(inode->i_sb)) + 4; in ext4_ind_trans_blocks()
703 up_write(&EXT4_I(inode)->i_data_sem); in ext4_ind_trunc_restart_fn()
728 down_write(&EXT4_I(inode)->i_data_sem); in ext4_ind_truncate_ensure_credits()
733 ret = ext4_journal_get_write_access(handle, inode->i_sb, bh, in ext4_ind_truncate_ensure_credits()
742 * Probably it should be a library function... search for first non-zero word
755 * ext4_find_shared - find the indirect blocks for partial truncation.
772 * require special attention - pageout below the truncation point
777 * partially truncated blocks - in @chain[].bh and pointers to
778 * their last elements that should not be removed - in
779 * @chain[].p. Return value is the pointer to last filled element
785 * (@chain[i].p+1 .. end of @chain[i].bh->b_data)
797 /* Make k index the deepest non-null offset + 1 */ in ext4_find_shared()
798 for (k = depth; k > 1 && !offsets[k-1]; k--) in ext4_find_shared()
803 partial = chain + k-1; in ext4_find_shared()
805 * If the branch acquired continuation since we've looked at it - in ext4_find_shared()
808 if (!partial->key && *partial->p) in ext4_find_shared()
811 for (p = partial; (p > chain) && all_zeroes((__le32 *) p->bh->b_data, p->p); p--) in ext4_find_shared()
814 * OK, we've found the last block that must survive. The rest of our in ext4_find_shared()
817 * it's easier to cheat and just decrement partial->p. in ext4_find_shared()
819 if (p == chain + k - 1 && p > chain) { in ext4_find_shared()
820 p->p--; in ext4_find_shared()
822 *top = *p->p; in ext4_find_shared()
825 *p->p = 0; in ext4_find_shared()
831 brelse(partial->bh); in ext4_find_shared()
832 partial--; in ext4_find_shared()
843 * We release `count' blocks on disk, but (last - first) may be greater
853 __le32 *last) in ext4_clear_blocks() argument
859 if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode) || in ext4_clear_blocks()
877 for (p = first; p < last; p++) in ext4_clear_blocks()
883 ext4_std_error(inode->i_sb, err); in ext4_clear_blocks()
888 * ext4_free_data - free a list of data blocks
891 * @this_bh: indirect buffer_head which contains *@first and *@last
893 * @last: points immediately past the end of array
896 * little-endian 32-bit) and updating @inode->i_blocks appropriately.
903 * @this_bh will be %NULL if @first and @last point into the inode's direct
908 __le32 *first, __le32 *last) in ext4_free_data() argument
922 err = ext4_journal_get_write_access(handle, inode->i_sb, in ext4_free_data()
930 for (p = first; p < last; p++) { in ext4_free_data()
975 (unsigned long long) this_bh->b_blocknr); in ext4_free_data()
980 * ext4_free_branches - free an array of branches
983 * @parent_bh: the buffer_head which contains *@first and *@last
985 * @last: pointer immediately past the end of array
989 * stored as little-endian 32-bit) and updating @inode->i_blocks
994 __le32 *first, __le32 *last, int depth) in ext4_free_branches() argument
1002 if (depth--) { in ext4_free_branches()
1004 int addr_per_block = EXT4_ADDR_PER_BLOCK(inode->i_sb); in ext4_free_branches()
1005 p = last; in ext4_free_branches()
1006 while (--p >= first) { in ext4_free_branches()
1014 "block %lu (level %d)", in ext4_free_branches()
1019 /* Go read the buffer for the next level down */ in ext4_free_branches()
1020 bh = ext4_sb_bread(inode->i_sb, nr, 0); in ext4_free_branches()
1027 ext4_error_inode_block(inode, nr, -PTR_ERR(bh), in ext4_free_branches()
1035 (__le32 *) bh->b_data, in ext4_free_branches()
1036 (__le32 *) bh->b_data + addr_per_block, in ext4_free_branches()
1042 * released. Now let this top-of-subtree go. in ext4_free_branches()
1061 inode->i_sb, 1)) < 0) in ext4_free_branches()
1086 inode->i_sb, parent_bh, in ext4_free_branches()
1100 ext4_free_data(handle, inode, parent_bh, first, last); in ext4_free_branches()
1107 __le32 *i_data = ei->i_data; in ext4_ind_truncate()
1108 int addr_per_block = EXT4_ADDR_PER_BLOCK(inode->i_sb); in ext4_ind_truncate()
1115 unsigned blocksize = inode->i_sb->s_blocksize; in ext4_ind_truncate()
1117 last_block = (inode->i_size + blocksize-1) in ext4_ind_truncate()
1118 >> EXT4_BLOCK_SIZE_BITS(inode->i_sb); in ext4_ind_truncate()
1119 max_block = (EXT4_SB(inode->i_sb)->s_bitmap_maxbytes + blocksize-1) in ext4_ind_truncate()
1120 >> EXT4_BLOCK_SIZE_BITS(inode->i_sb); in ext4_ind_truncate()
1128 ext4_es_remove_extent(inode, last_block, EXT_MAX_BLOCKS - last_block); in ext4_ind_truncate()
1134 * on-disk inode. We do this via i_disksize, which is the value which in ext4_ind_truncate()
1137 ei->i_disksize = inode->i_size; in ext4_ind_truncate()
1157 &nr, &nr+1, (chain+n-1) - partial); in ext4_ind_truncate()
1158 *partial->p = 0; in ext4_ind_truncate()
1165 BUFFER_TRACE(partial->bh, "get_write_access"); in ext4_ind_truncate()
1166 ext4_free_branches(handle, inode, partial->bh, in ext4_ind_truncate()
1167 partial->p, in ext4_ind_truncate()
1168 partial->p+1, (chain+n-1) - partial); in ext4_ind_truncate()
1173 ext4_free_branches(handle, inode, partial->bh, partial->p + 1, in ext4_ind_truncate()
1174 (__le32*)partial->bh->b_data+addr_per_block, in ext4_ind_truncate()
1175 (chain+n-1) - partial); in ext4_ind_truncate()
1176 BUFFER_TRACE(partial->bh, "call brelse"); in ext4_ind_truncate()
1177 brelse(partial->bh); in ext4_ind_truncate()
1178 partial--; in ext4_ind_truncate()
1210 * ext4_ind_remove_space - remove space from the range
1214 * @end: One block after the last block to remove (exclusive)
1223 __le32 *i_data = ei->i_data; in ext4_ind_remove_space()
1224 int addr_per_block = EXT4_ADDR_PER_BLOCK(inode->i_sb); in ext4_ind_remove_space()
1232 unsigned blocksize = inode->i_sb->s_blocksize; in ext4_ind_remove_space()
1234 max_block = (EXT4_SB(inode->i_sb)->s_bitmap_maxbytes + blocksize-1) in ext4_ind_remove_space()
1235 >> EXT4_BLOCK_SIZE_BITS(inode->i_sb); in ext4_ind_remove_space()
1261 * Start is at the direct block level, free in ext4_ind_remove_space()
1262 * everything to the end of the level. in ext4_ind_remove_space()
1275 &nr, &nr+1, (chain+n-1) - partial); in ext4_ind_remove_space()
1276 *partial->p = 0; in ext4_ind_remove_space()
1279 BUFFER_TRACE(partial->bh, "get_write_access"); in ext4_ind_remove_space()
1280 ext4_free_branches(handle, inode, partial->bh, in ext4_ind_remove_space()
1281 partial->p, in ext4_ind_remove_space()
1282 partial->p+1, (chain+n-1) - partial); in ext4_ind_remove_space()
1291 ext4_free_branches(handle, inode, partial->bh, in ext4_ind_remove_space()
1292 partial->p + 1, in ext4_ind_remove_space()
1293 (__le32 *)partial->bh->b_data+addr_per_block, in ext4_ind_remove_space()
1294 (chain+n-1) - partial); in ext4_ind_remove_space()
1295 partial--; in ext4_ind_remove_space()
1304 * the start of the next level we're not going in ext4_ind_remove_space()
1313 * points to the last element which should not be in ext4_ind_remove_space()
1317 partial2->p++; in ext4_ind_remove_space()
1325 ext4_free_branches(handle, inode, partial2->bh, in ext4_ind_remove_space()
1326 (__le32 *)partial2->bh->b_data, in ext4_ind_remove_space()
1327 partial2->p, in ext4_ind_remove_space()
1328 (chain2+n2-1) - partial2); in ext4_ind_remove_space()
1329 partial2--; in ext4_ind_remove_space()
1334 /* Punch happened within the same level (n == n2) */ in ext4_ind_remove_space()
1340 int level = min(partial - chain, partial2 - chain2); in ext4_ind_remove_space() local
1344 for (i = 0; i <= level; i++) { in ext4_ind_remove_space()
1356 (chain+n-1) - partial); in ext4_ind_remove_space()
1357 *partial->p = 0; in ext4_ind_remove_space()
1360 BUFFER_TRACE(partial->bh, "get_write_access"); in ext4_ind_remove_space()
1361 ext4_free_branches(handle, inode, partial->bh, in ext4_ind_remove_space()
1362 partial->p, in ext4_ind_remove_space()
1363 partial->p+1, in ext4_ind_remove_space()
1364 (chain+n-1) - partial); in ext4_ind_remove_space()
1372 * points to the last element which should not be in ext4_ind_remove_space()
1376 partial2->p++; in ext4_ind_remove_space()
1380 int depth = (chain+n-1) - partial; in ext4_ind_remove_space()
1381 int depth2 = (chain2+n2-1) - partial2; in ext4_ind_remove_space()
1384 partial->bh->b_blocknr == partial2->bh->b_blocknr) { in ext4_ind_remove_space()
1389 ext4_free_branches(handle, inode, partial->bh, in ext4_ind_remove_space()
1390 partial->p + 1, in ext4_ind_remove_space()
1391 partial2->p, in ext4_ind_remove_space()
1392 (chain+n-1) - partial); in ext4_ind_remove_space()
1398 * level even though the punch happened within one level. So, we in ext4_ind_remove_space()
1399 * give them a chance to arrive at the same level, then walk in ext4_ind_remove_space()
1404 ext4_free_branches(handle, inode, partial->bh, in ext4_ind_remove_space()
1405 partial->p + 1, in ext4_ind_remove_space()
1406 (__le32 *)partial->bh->b_data+addr_per_block, in ext4_ind_remove_space()
1407 (chain+n-1) - partial); in ext4_ind_remove_space()
1408 partial--; in ext4_ind_remove_space()
1411 ext4_free_branches(handle, inode, partial2->bh, in ext4_ind_remove_space()
1412 (__le32 *)partial2->bh->b_data, in ext4_ind_remove_space()
1413 partial2->p, in ext4_ind_remove_space()
1414 (chain2+n2-1) - partial2); in ext4_ind_remove_space()
1415 partial2--; in ext4_ind_remove_space()
1421 BUFFER_TRACE(p->bh, "call brelse"); in ext4_ind_remove_space()
1422 brelse(p->bh); in ext4_ind_remove_space()
1423 p--; in ext4_ind_remove_space()
1426 BUFFER_TRACE(p2->bh, "call brelse"); in ext4_ind_remove_space()
1427 brelse(p2->bh); in ext4_ind_remove_space()
1428 p2--; in ext4_ind_remove_space()