2 * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)
6 * Copyright (c) 2012 Martin Sucha
7 * Copyright (c) 2012 Frantisek Princ
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
14 * - Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * - Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * - The name of the author may not be used to endorse or promote products
20 * derived from this software without specific prior written permission.
22 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
23 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
24 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
25 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
27 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
31 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 /** @addtogroup lwext4
39 * @brief Physical block allocator.
42 #include "ext4_config.h"
43 #include "ext4_balloc.h"
44 #include "ext4_super.h"
45 #include "ext4_crc32c.h"
46 #include "ext4_block_group.h"
48 #include "ext4_bitmap.h"
49 #include "ext4_inode.h"
51 /**@brief Compute number of block group from block address.
52 * @param sb superblock pointer.
53 * @param baddr Absolute address of block.
54 * @return Block group index
56 uint32_t ext4_balloc_get_bgid_of_block(struct ext4_sblock *s,
59 if (ext4_get32(s, first_data_block) && baddr)
62 return baddr / ext4_get32(s, blocks_per_group);
65 /**@brief Compute the starting block address of a block group
66 * @param sb superblock pointer.
67 * @param bgid block group index
68 * @return Block address
70 uint64_t ext4_balloc_get_block_of_bgid(struct ext4_sblock *s,
74 if (ext4_get32(s, first_data_block))
77 baddr += bgid * ext4_get32(s, blocks_per_group);
81 #if CONFIG_META_CSUM_ENABLE
82 static uint32_t ext4_balloc_bitmap_csum(struct ext4_sblock *sb,
85 uint32_t checksum = 0;
86 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
87 uint32_t blocks_per_group =
88 ext4_get32(sb, blocks_per_group);
90 /* First calculate crc32 checksum against fs uuid */
91 checksum = ext4_crc32c(EXT4_CRC32_INIT, sb->uuid,
93 /* Then calculate crc32 checksum against block_group_desc */
94 checksum = ext4_crc32c(checksum, bitmap,
95 blocks_per_group / 8);
100 #define ext4_balloc_bitmap_csum(...) 0
103 void ext4_balloc_set_bitmap_csum(struct ext4_sblock *sb,
104 struct ext4_bgroup *bg,
105 void *bitmap __unused)
107 int desc_size = ext4_sb_get_desc_size(sb);
108 uint32_t checksum = ext4_balloc_bitmap_csum(sb, bitmap);
109 uint16_t lo_checksum = to_le16(checksum & 0xFFFF),
110 hi_checksum = to_le16(checksum >> 16);
112 if (!ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
115 /* See if we need to assign a 32bit checksum */
116 bg->block_bitmap_csum_lo = lo_checksum;
117 if (desc_size == EXT4_MAX_BLOCK_GROUP_DESCRIPTOR_SIZE)
118 bg->block_bitmap_csum_hi = hi_checksum;
122 #if CONFIG_META_CSUM_ENABLE
124 ext4_balloc_verify_bitmap_csum(struct ext4_sblock *sb,
125 struct ext4_bgroup *bg,
126 void *bitmap __unused)
128 int desc_size = ext4_sb_get_desc_size(sb);
129 uint32_t checksum = ext4_balloc_bitmap_csum(sb, bitmap);
130 uint16_t lo_checksum = to_le16(checksum & 0xFFFF),
131 hi_checksum = to_le16(checksum >> 16);
133 if (!ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
136 if (bg->block_bitmap_csum_lo != lo_checksum)
139 if (desc_size == EXT4_MAX_BLOCK_GROUP_DESCRIPTOR_SIZE)
140 if (bg->block_bitmap_csum_hi != hi_checksum)
146 #define ext4_balloc_verify_bitmap_csum(...) true
149 int ext4_balloc_free_block(struct ext4_inode_ref *inode_ref, ext4_fsblk_t baddr)
151 struct ext4_fs *fs = inode_ref->fs;
152 struct ext4_sblock *sb = &fs->sb;
154 uint32_t block_group = ext4_balloc_get_bgid_of_block(sb, baddr);
155 uint32_t index_in_group = ext4_fs_baddr2_index_in_group(sb, baddr);
157 /* Load block group reference */
158 struct ext4_block_group_ref bg_ref;
159 int rc = ext4_fs_get_block_group_ref(fs, block_group, &bg_ref);
163 /* Load block with bitmap */
164 ext4_fsblk_t bitmap_block_addr =
165 ext4_bg_get_block_bitmap(bg_ref.block_group, sb);
167 struct ext4_block bitmap_block;
169 rc = ext4_block_get(fs->bdev, &bitmap_block, bitmap_block_addr);
171 ext4_fs_put_block_group_ref(&bg_ref);
175 if (!ext4_balloc_verify_bitmap_csum(sb,
177 bitmap_block.data)) {
178 ext4_dbg(DEBUG_BALLOC,
179 DBG_WARN "Bitmap checksum failed."
180 "Group: %" PRIu32"\n",
185 ext4_bmap_bit_clr(bitmap_block.data, index_in_group);
186 ext4_balloc_set_bitmap_csum(sb, bg_ref.block_group,
188 bitmap_block.dirty = true;
190 /* Release block with bitmap */
191 rc = ext4_block_set(fs->bdev, &bitmap_block);
193 /* Error in saving bitmap */
194 ext4_fs_put_block_group_ref(&bg_ref);
198 uint32_t block_size = ext4_sb_get_block_size(sb);
200 /* Update superblock free blocks count */
201 uint64_t sb_free_blocks = ext4_sb_get_free_blocks_cnt(sb);
203 ext4_sb_set_free_blocks_cnt(sb, sb_free_blocks);
205 /* Update inode blocks count */
206 uint64_t ino_blocks = ext4_inode_get_blocks_count(sb, inode_ref->inode);
207 ino_blocks -= block_size / EXT4_INODE_BLOCK_SIZE;
208 ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
209 inode_ref->dirty = true;
211 /* Update block group free blocks count */
212 uint32_t free_blocks =
213 ext4_bg_get_free_blocks_count(bg_ref.block_group, sb);
215 ext4_bg_set_free_blocks_count(bg_ref.block_group, sb, free_blocks);
219 /* Release block group reference */
220 return ext4_fs_put_block_group_ref(&bg_ref);
223 int ext4_balloc_free_blocks(struct ext4_inode_ref *inode_ref, ext4_fsblk_t first,
227 struct ext4_fs *fs = inode_ref->fs;
228 struct ext4_sblock *sb = &fs->sb;
230 /* Compute indexes */
231 uint32_t block_group_first = ext4_balloc_get_bgid_of_block(sb, first);
233 /* Compute indexes */
234 uint32_t block_group_last =
235 ext4_balloc_get_bgid_of_block(sb, first + count - 1);
237 if (!ext4_sb_feature_incom(sb, EXT4_FINCOM_FLEX_BG)) {
238 /*It is not possible without flex_bg that blocks are continuous
239 * and and last block belongs to other bg.*/
240 ext4_assert(block_group_first == ext4_balloc_get_bgid_of_block(
241 sb, first + count - 1));
244 /* Load block group reference */
245 struct ext4_block_group_ref bg_ref;
246 while (block_group_first <= block_group_last) {
249 ext4_fs_get_block_group_ref(fs, block_group_first, &bg_ref);
253 uint32_t index_in_group_first =
254 ext4_fs_baddr2_index_in_group(sb, first);
256 /* Load block with bitmap */
257 ext4_fsblk_t bitmap_block_addr =
258 ext4_bg_get_block_bitmap(bg_ref.block_group, sb);
260 struct ext4_block bitmap_block;
262 rc = ext4_block_get(fs->bdev, &bitmap_block, bitmap_block_addr);
264 ext4_fs_put_block_group_ref(&bg_ref);
268 if (!ext4_balloc_verify_bitmap_csum(sb,
270 bitmap_block.data)) {
271 ext4_dbg(DEBUG_BALLOC,
272 DBG_WARN "Bitmap checksum failed."
273 "Group: %" PRIu32"\n",
278 ext4_sb_get_block_size(sb) * 8 - index_in_group_first;
280 /*If last block, free only count blocks*/
281 free_cnt = count > free_cnt ? free_cnt : count;
284 ext4_bmap_bits_free(bitmap_block.data, index_in_group_first,
286 ext4_balloc_set_bitmap_csum(sb, bg_ref.block_group,
288 bitmap_block.dirty = true;
293 /* Release block with bitmap */
294 rc = ext4_block_set(fs->bdev, &bitmap_block);
296 ext4_fs_put_block_group_ref(&bg_ref);
300 uint32_t block_size = ext4_sb_get_block_size(sb);
302 /* Update superblock free blocks count */
303 uint64_t sb_free_blocks = ext4_sb_get_free_blocks_cnt(sb);
304 sb_free_blocks += free_cnt;
305 ext4_sb_set_free_blocks_cnt(sb, sb_free_blocks);
307 /* Update inode blocks count */
308 uint64_t ino_blocks =
309 ext4_inode_get_blocks_count(sb, inode_ref->inode);
310 ino_blocks -= free_cnt * (block_size / EXT4_INODE_BLOCK_SIZE);
311 ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
312 inode_ref->dirty = true;
314 /* Update block group free blocks count */
315 uint32_t free_blocks =
316 ext4_bg_get_free_blocks_count(bg_ref.block_group, sb);
317 free_blocks += free_cnt;
318 ext4_bg_set_free_blocks_count(bg_ref.block_group, sb,
322 /* Release block group reference */
323 rc = ext4_fs_put_block_group_ref(&bg_ref);
330 /*All blocks should be released*/
331 ext4_assert(count == 0);
335 int ext4_balloc_alloc_block(struct ext4_inode_ref *inode_ref,
337 ext4_fsblk_t *fblock)
339 ext4_fsblk_t allocated_block = 0;
340 ext4_fsblk_t bitmap_block_addr;
341 uint32_t rel_block_idx = 0;
342 uint64_t free_blocks;
343 struct ext4_block bitmap_block;
346 struct ext4_sblock *sb = &inode_ref->fs->sb;
348 /* Load block group number for goal and relative index */
349 uint32_t block_group = ext4_balloc_get_bgid_of_block(sb, goal);
350 uint32_t index_in_group = ext4_fs_baddr2_index_in_group(sb, goal);
352 /* Load block group reference */
353 struct ext4_block_group_ref bg_ref;
354 rc = ext4_fs_get_block_group_ref(inode_ref->fs, block_group, &bg_ref);
358 free_blocks = ext4_bg_get_free_blocks_count(bg_ref.block_group, sb);
359 if (free_blocks == 0) {
360 /* This group has no free blocks */
364 /* Compute indexes */
365 ext4_fsblk_t first_in_group = ext4_balloc_get_block_of_bgid(sb, bg_ref.index);
367 uint32_t first_in_group_index =
368 ext4_fs_baddr2_index_in_group(sb, first_in_group);
370 if (index_in_group < first_in_group_index)
371 index_in_group = first_in_group_index;
373 /* Load block with bitmap */
374 bitmap_block_addr = ext4_bg_get_block_bitmap(bg_ref.block_group, sb);
376 rc = ext4_block_get(inode_ref->fs->bdev, &bitmap_block,
379 ext4_fs_put_block_group_ref(&bg_ref);
383 if (!ext4_balloc_verify_bitmap_csum(sb,
385 bitmap_block.data)) {
386 ext4_dbg(DEBUG_BALLOC,
387 DBG_WARN "Bitmap checksum failed."
388 "Group: %" PRIu32"\n",
392 /* Check if goal is free */
393 if (ext4_bmap_is_bit_clr(bitmap_block.data, index_in_group)) {
394 ext4_bmap_bit_set(bitmap_block.data, index_in_group);
395 ext4_balloc_set_bitmap_csum(sb, bg_ref.block_group,
397 bitmap_block.dirty = true;
398 rc = ext4_block_set(inode_ref->fs->bdev, &bitmap_block);
400 ext4_fs_put_block_group_ref(&bg_ref);
404 allocated_block = ext4_fs_index_in_group2_baddr(
405 sb, index_in_group, block_group);
410 uint32_t blocks_in_group = ext4_blocks_in_group_cnt(sb, block_group);
412 uint32_t end_idx = (index_in_group + 63) & ~63;
413 if (end_idx > blocks_in_group)
414 end_idx = blocks_in_group;
416 /* Try to find free block near to goal */
418 for (tmp_idx = index_in_group + 1; tmp_idx < end_idx; ++tmp_idx) {
419 if (ext4_bmap_is_bit_clr(bitmap_block.data, tmp_idx)) {
420 ext4_bmap_bit_set(bitmap_block.data, tmp_idx);
422 ext4_balloc_set_bitmap_csum(sb, bg_ref.block_group,
424 bitmap_block.dirty = true;
425 rc = ext4_block_set(inode_ref->fs->bdev, &bitmap_block);
429 allocated_block = ext4_fs_index_in_group2_baddr(
430 sb, tmp_idx, block_group);
436 /* Find free bit in bitmap */
437 rc = ext4_bmap_bit_find_clr(bitmap_block.data, index_in_group,
438 blocks_in_group, &rel_block_idx);
440 ext4_bmap_bit_set(bitmap_block.data, rel_block_idx);
441 ext4_balloc_set_bitmap_csum(sb, bg_ref.block_group,
443 bitmap_block.dirty = true;
444 rc = ext4_block_set(inode_ref->fs->bdev, &bitmap_block);
448 allocated_block = ext4_fs_index_in_group2_baddr(
449 sb, rel_block_idx, block_group);
454 /* No free block found yet */
455 rc = ext4_block_set(inode_ref->fs->bdev, &bitmap_block);
457 ext4_fs_put_block_group_ref(&bg_ref);
463 rc = ext4_fs_put_block_group_ref(&bg_ref);
467 /* Try other block groups */
468 uint32_t block_group_count = ext4_block_group_cnt(sb);
470 uint32_t bgid = (block_group + 1) % block_group_count;
471 uint32_t count = block_group_count;
474 rc = ext4_fs_get_block_group_ref(inode_ref->fs, bgid, &bg_ref);
479 ext4_bg_get_free_blocks_count(bg_ref.block_group, sb);
480 if (free_blocks == 0) {
481 /* This group has no free blocks */
485 /* Load block with bitmap */
487 ext4_bg_get_block_bitmap(bg_ref.block_group, sb);
489 rc = ext4_block_get(inode_ref->fs->bdev, &bitmap_block,
493 ext4_fs_put_block_group_ref(&bg_ref);
497 if (!ext4_balloc_verify_bitmap_csum(sb,
499 bitmap_block.data)) {
500 ext4_dbg(DEBUG_BALLOC,
501 DBG_WARN "Bitmap checksum failed."
502 "Group: %" PRIu32"\n",
506 /* Compute indexes */
507 first_in_group = ext4_balloc_get_block_of_bgid(sb, bgid);
509 ext4_fs_baddr2_index_in_group(sb, first_in_group);
510 blocks_in_group = ext4_blocks_in_group_cnt(sb, bgid);
512 first_in_group_index =
513 ext4_fs_baddr2_index_in_group(sb, first_in_group);
515 if (index_in_group < first_in_group_index)
516 index_in_group = first_in_group_index;
518 rc = ext4_bmap_bit_find_clr(bitmap_block.data, index_in_group,
519 blocks_in_group, &rel_block_idx);
523 ext4_bmap_bit_set(bitmap_block.data, rel_block_idx);
525 ext4_balloc_set_bitmap_csum(sb, bg_ref.block_group,
527 bitmap_block.dirty = true;
528 rc = ext4_block_set(inode_ref->fs->bdev, &bitmap_block);
530 ext4_fs_put_block_group_ref(&bg_ref);
534 allocated_block = ext4_fs_index_in_group2_baddr(
535 sb, rel_block_idx, bgid);
540 rc = ext4_block_set(inode_ref->fs->bdev, &bitmap_block);
542 ext4_fs_put_block_group_ref(&bg_ref);
547 rc = ext4_fs_put_block_group_ref(&bg_ref);
552 /* Goto next group */
553 bgid = (bgid + 1) % block_group_count;
560 /* Empty command - because of syntax */
563 uint32_t block_size = ext4_sb_get_block_size(sb);
565 /* Update superblock free blocks count */
566 uint64_t sb_free_blocks = ext4_sb_get_free_blocks_cnt(sb);
568 ext4_sb_set_free_blocks_cnt(sb, sb_free_blocks);
570 /* Update inode blocks (different block size!) count */
571 uint64_t ino_blocks = ext4_inode_get_blocks_count(sb, inode_ref->inode);
572 ino_blocks += block_size / EXT4_INODE_BLOCK_SIZE;
573 ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
574 inode_ref->dirty = true;
576 /* Update block group free blocks count */
577 uint64_t bg_free_blocks =
578 ext4_bg_get_free_blocks_count(bg_ref.block_group, sb);
580 ext4_bg_set_free_blocks_count(bg_ref.block_group, sb, bg_free_blocks);
584 rc = ext4_fs_put_block_group_ref(&bg_ref);
586 *fblock = allocated_block;
590 int ext4_balloc_try_alloc_block(struct ext4_inode_ref *inode_ref,
591 ext4_fsblk_t baddr, bool *free)
595 struct ext4_fs *fs = inode_ref->fs;
596 struct ext4_sblock *sb = &fs->sb;
598 /* Compute indexes */
599 uint32_t block_group = ext4_balloc_get_bgid_of_block(sb, baddr);
600 uint32_t index_in_group = ext4_fs_baddr2_index_in_group(sb, baddr);
602 /* Load block group reference */
603 struct ext4_block_group_ref bg_ref;
604 rc = ext4_fs_get_block_group_ref(fs, block_group, &bg_ref);
608 /* Load block with bitmap */
609 ext4_fsblk_t bitmap_block_addr =
610 ext4_bg_get_block_bitmap(bg_ref.block_group, sb);
612 struct ext4_block bitmap_block;
614 rc = ext4_block_get(fs->bdev, &bitmap_block, bitmap_block_addr);
616 ext4_fs_put_block_group_ref(&bg_ref);
620 if (!ext4_balloc_verify_bitmap_csum(sb,
622 bitmap_block.data)) {
623 ext4_dbg(DEBUG_BALLOC,
624 DBG_WARN "Bitmap checksum failed."
625 "Group: %" PRIu32"\n",
629 /* Check if block is free */
630 *free = ext4_bmap_is_bit_clr(bitmap_block.data, index_in_group);
632 /* Allocate block if possible */
634 ext4_bmap_bit_set(bitmap_block.data, index_in_group);
635 ext4_balloc_set_bitmap_csum(sb, bg_ref.block_group,
637 bitmap_block.dirty = true;
640 /* Release block with bitmap */
641 rc = ext4_block_set(fs->bdev, &bitmap_block);
643 /* Error in saving bitmap */
644 ext4_fs_put_block_group_ref(&bg_ref);
648 /* If block is not free, return */
652 uint32_t block_size = ext4_sb_get_block_size(sb);
654 /* Update superblock free blocks count */
655 uint64_t sb_free_blocks = ext4_sb_get_free_blocks_cnt(sb);
657 ext4_sb_set_free_blocks_cnt(sb, sb_free_blocks);
659 /* Update inode blocks count */
660 uint64_t ino_blocks = ext4_inode_get_blocks_count(sb, inode_ref->inode);
661 ino_blocks += block_size / EXT4_INODE_BLOCK_SIZE;
662 ext4_inode_set_blocks_count(sb, inode_ref->inode, ino_blocks);
663 inode_ref->dirty = true;
665 /* Update block group free blocks count */
666 uint32_t free_blocks =
667 ext4_bg_get_free_blocks_count(bg_ref.block_group, sb);
669 ext4_bg_set_free_blocks_count(bg_ref.block_group, sb, free_blocks);
674 return ext4_fs_put_block_group_ref(&bg_ref);