2 * Copyright (c) 2012 Frantisek Princ
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 /** @addtogroup libext4
33 * @file libext4_balloc.c
34 * @brief Physical block allocator.
38 #include <sys/types.h>
41 /** Compute number of block group from block address.
43 * @param sb Superblock pointer.
44 * @param block_addr Absolute address of block.
46 * @return Block group index
49 static uint32_t ext4_balloc_get_bgid_of_block(ext4_superblock_t
*sb
,
52 uint32_t blocks_per_group
=
53 ext4_superblock_get_blocks_per_group(sb
);
54 uint32_t first_block
=
55 ext4_superblock_get_first_data_block(sb
);
57 /* First block == 0 or 1 */
59 return block_addr
/ blocks_per_group
;
61 return (block_addr
- 1) / blocks_per_group
;
66 * @param inode_ref Inode, where the block is allocated
67 * @param block_addr Absolute block address to free
72 int ext4_balloc_free_block(ext4_inode_ref_t
*inode_ref
, uint32_t block_addr
)
74 ext4_filesystem_t
*fs
= inode_ref
->fs
;
75 ext4_superblock_t
*sb
= fs
->superblock
;
78 uint32_t block_group
= ext4_balloc_get_bgid_of_block(sb
, block_addr
);
79 uint32_t index_in_group
=
80 ext4_filesystem_blockaddr2_index_in_group(sb
, block_addr
);
82 /* Load block group reference */
83 ext4_block_group_ref_t
*bg_ref
;
84 int rc
= ext4_filesystem_get_block_group_ref(fs
, block_group
, &bg_ref
);
88 /* Load block with bitmap */
89 uint32_t bitmap_block_addr
=
90 ext4_block_group_get_block_bitmap(bg_ref
->block_group
, sb
);
91 block_t
*bitmap_block
;
92 rc
= block_get(&bitmap_block
, fs
->device
, bitmap_block_addr
, 0);
97 ext4_bitmap_free_bit(bitmap_block
->data
, index_in_group
);
98 bitmap_block
->dirty
= true;
100 /* Release block with bitmap */
101 rc
= block_put(bitmap_block
);
103 /* Error in saving bitmap */
104 ext4_filesystem_put_block_group_ref(bg_ref
);
108 uint32_t block_size
= ext4_superblock_get_block_size(sb
);
110 /* Update superblock free blocks count */
111 uint32_t sb_free_blocks
=
112 ext4_superblock_get_free_blocks_count(sb
);
114 ext4_superblock_set_free_blocks_count(sb
, sb_free_blocks
);
116 /* Update inode blocks count */
117 uint64_t ino_blocks
=
118 ext4_inode_get_blocks_count(sb
, inode_ref
->inode
);
119 ino_blocks
-= block_size
/ EXT4_INODE_BLOCK_SIZE
;
120 ext4_inode_set_blocks_count(sb
, inode_ref
->inode
, ino_blocks
);
121 inode_ref
->dirty
= true;
123 /* Update block group free blocks count */
124 uint32_t free_blocks
=
125 ext4_block_group_get_free_blocks_count(bg_ref
->block_group
, sb
);
127 ext4_block_group_set_free_blocks_count(bg_ref
->block_group
,
129 bg_ref
->dirty
= true;
131 /* Release block group reference */
132 return ext4_filesystem_put_block_group_ref(bg_ref
);
135 /** Free continuous set of blocks.
137 * @param inode_ref Inode, where the blocks are allocated
138 * @param first First block to release
139 * @param count Number of blocks to release
142 int ext4_balloc_free_blocks(ext4_inode_ref_t
*inode_ref
,
143 uint32_t first
, uint32_t count
)
145 ext4_filesystem_t
*fs
= inode_ref
->fs
;
146 ext4_superblock_t
*sb
= fs
->superblock
;
148 /* Compute indexes */
149 uint32_t block_group_first
=
150 ext4_balloc_get_bgid_of_block(sb
, first
);
151 uint32_t block_group_last
=
152 ext4_balloc_get_bgid_of_block(sb
, first
+ count
- 1);
154 assert(block_group_first
== block_group_last
);
156 /* Load block group reference */
157 ext4_block_group_ref_t
*bg_ref
;
158 int rc
= ext4_filesystem_get_block_group_ref(fs
, block_group_first
, &bg_ref
);
162 uint32_t index_in_group_first
=
163 ext4_filesystem_blockaddr2_index_in_group(sb
, first
);
165 /* Load block with bitmap */
166 uint32_t bitmap_block_addr
=
167 ext4_block_group_get_block_bitmap(bg_ref
->block_group
, sb
);
169 block_t
*bitmap_block
;
170 rc
= block_get(&bitmap_block
, fs
->device
, bitmap_block_addr
, 0);
175 ext4_bitmap_free_bits(bitmap_block
->data
, index_in_group_first
, count
);
176 bitmap_block
->dirty
= true;
178 /* Release block with bitmap */
179 rc
= block_put(bitmap_block
);
181 /* Error in saving bitmap */
182 ext4_filesystem_put_block_group_ref(bg_ref
);
186 uint32_t block_size
= ext4_superblock_get_block_size(sb
);
188 /* Update superblock free blocks count */
189 uint32_t sb_free_blocks
=
190 ext4_superblock_get_free_blocks_count(sb
);
191 sb_free_blocks
+= count
;
192 ext4_superblock_set_free_blocks_count(sb
, sb_free_blocks
);
194 /* Update inode blocks count */
195 uint64_t ino_blocks
=
196 ext4_inode_get_blocks_count(sb
, inode_ref
->inode
);
197 ino_blocks
-= count
* (block_size
/ EXT4_INODE_BLOCK_SIZE
);
198 ext4_inode_set_blocks_count(sb
, inode_ref
->inode
, ino_blocks
);
199 inode_ref
->dirty
= true;
201 /* Update block group free blocks count */
202 uint32_t free_blocks
=
203 ext4_block_group_get_free_blocks_count(bg_ref
->block_group
, sb
);
204 free_blocks
+= count
;
205 ext4_block_group_set_free_blocks_count(bg_ref
->block_group
,
207 bg_ref
->dirty
= true;
209 /* Release block group reference */
210 return ext4_filesystem_put_block_group_ref(bg_ref
);
213 /** Compute first block for data in block group.
215 * @param sb Pointer to superblock
216 * @param bg Pointer to block group
217 * @param bgid Index of block group
219 * @return Absolute block index of first block
222 uint32_t ext4_balloc_get_first_data_block_in_group(ext4_superblock_t
*sb
,
223 ext4_block_group_ref_t
*bg_ref
)
225 uint32_t block_group_count
= ext4_superblock_get_block_group_count(sb
);
226 uint32_t inode_table_first_block
=
227 ext4_block_group_get_inode_table_first_block(bg_ref
->block_group
, sb
);
228 uint16_t inode_table_item_size
= ext4_superblock_get_inode_size(sb
);
229 uint32_t inodes_per_group
= ext4_superblock_get_inodes_per_group(sb
);
230 uint32_t block_size
= ext4_superblock_get_block_size(sb
);
231 uint32_t inode_table_bytes
;
233 if (bg_ref
->index
< block_group_count
- 1) {
234 inode_table_bytes
= inodes_per_group
* inode_table_item_size
;
236 /* Last block group could be smaller */
237 uint32_t inodes_count_total
= ext4_superblock_get_inodes_count(sb
);
239 (inodes_count_total
- ((block_group_count
- 1) * inodes_per_group
)) *
240 inode_table_item_size
;
243 uint32_t inode_table_blocks
= inode_table_bytes
/ block_size
;
245 if (inode_table_bytes
% block_size
)
246 inode_table_blocks
++;
248 return inode_table_first_block
+ inode_table_blocks
;
251 /** Compute 'goal' for allocation algorithm.
253 * @param inode_ref Reference to inode, to allocate block for
255 * @return Goal block number
258 static int ext4_balloc_find_goal(ext4_inode_ref_t
*inode_ref
, uint32_t *goal
)
261 ext4_superblock_t
*sb
= inode_ref
->fs
->superblock
;
263 uint64_t inode_size
= ext4_inode_get_size(sb
, inode_ref
->inode
);
264 uint32_t block_size
= ext4_superblock_get_block_size(sb
);
265 uint32_t inode_block_count
= inode_size
/ block_size
;
267 if (inode_size
% block_size
!= 0)
270 /* If inode has some blocks, get last block address + 1 */
271 if (inode_block_count
> 0) {
272 int rc
= ext4_filesystem_get_inode_data_block_index(inode_ref
,
273 inode_block_count
- 1, goal
);
282 /* If goal == 0, sparse file -> continue */
285 /* Identify block group of inode */
286 uint32_t inodes_per_group
= ext4_superblock_get_inodes_per_group(sb
);
287 uint32_t block_group
= (inode_ref
->index
- 1) / inodes_per_group
;
288 block_size
= ext4_superblock_get_block_size(sb
);
290 /* Load block group reference */
291 ext4_block_group_ref_t
*bg_ref
;
292 int rc
= ext4_filesystem_get_block_group_ref(inode_ref
->fs
,
293 block_group
, &bg_ref
);
297 /* Compute indexes */
298 uint32_t block_group_count
= ext4_superblock_get_block_group_count(sb
);
299 uint32_t inode_table_first_block
=
300 ext4_block_group_get_inode_table_first_block(bg_ref
->block_group
, sb
);
301 uint16_t inode_table_item_size
= ext4_superblock_get_inode_size(sb
);
302 uint32_t inode_table_bytes
;
304 /* Check for last block group */
305 if (block_group
< block_group_count
- 1) {
306 inode_table_bytes
= inodes_per_group
* inode_table_item_size
;
308 /* Last block group could be smaller */
309 uint32_t inodes_count_total
= ext4_superblock_get_inodes_count(sb
);
311 (inodes_count_total
- ((block_group_count
- 1) * inodes_per_group
)) *
312 inode_table_item_size
;
315 uint32_t inode_table_blocks
= inode_table_bytes
/ block_size
;
317 if (inode_table_bytes
% block_size
)
318 inode_table_blocks
++;
320 *goal
= inode_table_first_block
+ inode_table_blocks
;
322 return ext4_filesystem_put_block_group_ref(bg_ref
);
325 /** Data block allocation algorithm.
327 * @param inode_ref Inode to allocate block for
328 * @param fblock Allocated block address
333 int ext4_balloc_alloc_block(ext4_inode_ref_t
*inode_ref
, uint32_t *fblock
)
335 uint32_t allocated_block
= 0;
337 uint32_t bitmap_block_addr
;
338 block_t
*bitmap_block
;
339 uint32_t rel_block_idx
= 0;
343 int rc
= ext4_balloc_find_goal(inode_ref
, &goal
);
346 else if (goal
== 0) {
347 /* no goal found => partition is full */
351 ext4_superblock_t
*sb
= inode_ref
->fs
->superblock
;
353 /* Load block group number for goal and relative index */
354 uint32_t block_group
= ext4_balloc_get_bgid_of_block(sb
, goal
);
355 uint32_t index_in_group
=
356 ext4_filesystem_blockaddr2_index_in_group(sb
, goal
);
358 /* Load block group reference */
359 ext4_block_group_ref_t
*bg_ref
;
360 rc
= ext4_filesystem_get_block_group_ref(inode_ref
->fs
,
361 block_group
, &bg_ref
);
365 /* Compute indexes */
366 uint32_t first_in_group
=
367 ext4_balloc_get_first_data_block_in_group(sb
, bg_ref
);
369 uint32_t first_in_group_index
=
370 ext4_filesystem_blockaddr2_index_in_group(sb
, first_in_group
);
372 if (index_in_group
< first_in_group_index
)
373 index_in_group
= first_in_group_index
;
375 /* Load block with bitmap */
377 ext4_block_group_get_block_bitmap(bg_ref
->block_group
, sb
);
379 rc
= block_get(&bitmap_block
, inode_ref
->fs
->device
,
380 bitmap_block_addr
, BLOCK_FLAGS_NONE
);
382 ext4_filesystem_put_block_group_ref(bg_ref
);
386 /* Check if goal is free */
387 if (ext4_bitmap_is_free_bit(bitmap_block
->data
, index_in_group
)) {
388 ext4_bitmap_set_bit(bitmap_block
->data
, index_in_group
);
389 bitmap_block
->dirty
= true;
390 rc
= block_put(bitmap_block
);
392 ext4_filesystem_put_block_group_ref(bg_ref
);
397 ext4_filesystem_index_in_group2blockaddr(sb
, index_in_group
,
403 uint32_t blocks_in_group
=
404 ext4_superblock_get_blocks_in_group(sb
, block_group
);
406 uint32_t end_idx
= (index_in_group
+ 63) & ~63;
407 if (end_idx
> blocks_in_group
)
408 end_idx
= blocks_in_group
;
410 /* Try to find free block near to goal */
411 for (uint32_t tmp_idx
= index_in_group
+ 1; tmp_idx
< end_idx
;
413 if (ext4_bitmap_is_free_bit(bitmap_block
->data
, tmp_idx
)) {
414 ext4_bitmap_set_bit(bitmap_block
->data
, tmp_idx
);
415 bitmap_block
->dirty
= true;
416 rc
= block_put(bitmap_block
);
421 ext4_filesystem_index_in_group2blockaddr(sb
, tmp_idx
,
428 /* Find free BYTE in bitmap */
429 rc
= ext4_bitmap_find_free_byte_and_set_bit(bitmap_block
->data
,
430 index_in_group
, &rel_block_idx
, blocks_in_group
);
432 bitmap_block
->dirty
= true;
433 rc
= block_put(bitmap_block
);
438 ext4_filesystem_index_in_group2blockaddr(sb
, rel_block_idx
,
444 /* Find free bit in bitmap */
445 rc
= ext4_bitmap_find_free_bit_and_set(bitmap_block
->data
,
446 index_in_group
, &rel_block_idx
, blocks_in_group
);
448 bitmap_block
->dirty
= true;
449 rc
= block_put(bitmap_block
);
454 ext4_filesystem_index_in_group2blockaddr(sb
, rel_block_idx
,
460 /* No free block found yet */
461 rc
= block_put(bitmap_block
);
463 ext4_filesystem_put_block_group_ref(bg_ref
);
467 rc
= ext4_filesystem_put_block_group_ref(bg_ref
);
471 /* Try other block groups */
472 uint32_t block_group_count
= ext4_superblock_get_block_group_count(sb
);
474 uint32_t bgid
= (block_group
+ 1) % block_group_count
;
475 uint32_t count
= block_group_count
;
478 rc
= ext4_filesystem_get_block_group_ref(inode_ref
->fs
, bgid
,
483 /* Load block with bitmap */
485 ext4_block_group_get_block_bitmap(bg_ref
->block_group
, sb
);
487 rc
= block_get(&bitmap_block
, inode_ref
->fs
->device
,
488 bitmap_block_addr
, 0);
490 ext4_filesystem_put_block_group_ref(bg_ref
);
494 /* Compute indexes */
496 ext4_balloc_get_first_data_block_in_group(sb
, bg_ref
);
498 ext4_filesystem_blockaddr2_index_in_group(sb
, first_in_group
);
499 blocks_in_group
= ext4_superblock_get_blocks_in_group(sb
, bgid
);
501 first_in_group_index
=
502 ext4_filesystem_blockaddr2_index_in_group(sb
, first_in_group
);
504 if (index_in_group
< first_in_group_index
)
505 index_in_group
= first_in_group_index
;
507 /* Try to find free byte in bitmap */
508 rc
= ext4_bitmap_find_free_byte_and_set_bit(bitmap_block
->data
,
509 index_in_group
, &rel_block_idx
, blocks_in_group
);
511 bitmap_block
->dirty
= true;
512 rc
= block_put(bitmap_block
);
517 ext4_filesystem_index_in_group2blockaddr(sb
, rel_block_idx
,
523 /* Try to find free bit in bitmap */
524 rc
= ext4_bitmap_find_free_bit_and_set(bitmap_block
->data
,
525 index_in_group
, &rel_block_idx
, blocks_in_group
);
527 bitmap_block
->dirty
= true;
528 rc
= block_put(bitmap_block
);
533 ext4_filesystem_index_in_group2blockaddr(sb
, rel_block_idx
,
539 rc
= block_put(bitmap_block
);
541 ext4_filesystem_put_block_group_ref(bg_ref
);
545 rc
= ext4_filesystem_put_block_group_ref(bg_ref
);
549 /* Goto next group */
550 bgid
= (bgid
+ 1) % block_group_count
;
557 /* Empty command - because of syntax */
560 uint32_t block_size
= ext4_superblock_get_block_size(sb
);
562 /* Update superblock free blocks count */
563 uint32_t sb_free_blocks
= ext4_superblock_get_free_blocks_count(sb
);
565 ext4_superblock_set_free_blocks_count(sb
, sb_free_blocks
);
567 /* Update inode blocks (different block size!) count */
568 uint64_t ino_blocks
=
569 ext4_inode_get_blocks_count(sb
, inode_ref
->inode
);
570 ino_blocks
+= block_size
/ EXT4_INODE_BLOCK_SIZE
;
571 ext4_inode_set_blocks_count(sb
, inode_ref
->inode
, ino_blocks
);
572 inode_ref
->dirty
= true;
574 /* Update block group free blocks count */
575 uint32_t bg_free_blocks
=
576 ext4_block_group_get_free_blocks_count(bg_ref
->block_group
, sb
);
578 ext4_block_group_set_free_blocks_count(bg_ref
->block_group
, sb
,
580 bg_ref
->dirty
= true;
582 rc
= ext4_filesystem_put_block_group_ref(bg_ref
);
584 *fblock
= allocated_block
;
588 /** Try to allocate concrete block.
590 * @param inode_ref Inode to allocate block for
591 * @param fblock Block address to allocate
592 * @param free Output value - if target block is free
597 int ext4_balloc_try_alloc_block(ext4_inode_ref_t
*inode_ref
, uint32_t fblock
,
602 ext4_filesystem_t
*fs
= inode_ref
->fs
;
603 ext4_superblock_t
*sb
= fs
->superblock
;
605 /* Compute indexes */
606 uint32_t block_group
= ext4_balloc_get_bgid_of_block(sb
, fblock
);
607 uint32_t index_in_group
=
608 ext4_filesystem_blockaddr2_index_in_group(sb
, fblock
);
610 /* Load block group reference */
611 ext4_block_group_ref_t
*bg_ref
;
612 rc
= ext4_filesystem_get_block_group_ref(fs
, block_group
, &bg_ref
);
616 /* Load block with bitmap */
617 uint32_t bitmap_block_addr
=
618 ext4_block_group_get_block_bitmap(bg_ref
->block_group
, sb
);
619 block_t
*bitmap_block
;
620 rc
= block_get(&bitmap_block
, fs
->device
, bitmap_block_addr
, 0);
624 /* Check if block is free */
625 *free
= ext4_bitmap_is_free_bit(bitmap_block
->data
, index_in_group
);
627 /* Allocate block if possible */
629 ext4_bitmap_set_bit(bitmap_block
->data
, index_in_group
);
630 bitmap_block
->dirty
= true;
633 /* Release block with bitmap */
634 rc
= block_put(bitmap_block
);
636 /* Error in saving bitmap */
637 ext4_filesystem_put_block_group_ref(bg_ref
);
641 /* If block is not free, return */
645 uint32_t block_size
= ext4_superblock_get_block_size(sb
);
647 /* Update superblock free blocks count */
648 uint32_t sb_free_blocks
= ext4_superblock_get_free_blocks_count(sb
);
650 ext4_superblock_set_free_blocks_count(sb
, sb_free_blocks
);
652 /* Update inode blocks count */
653 uint64_t ino_blocks
=
654 ext4_inode_get_blocks_count(sb
, inode_ref
->inode
);
655 ino_blocks
+= block_size
/ EXT4_INODE_BLOCK_SIZE
;
656 ext4_inode_set_blocks_count(sb
, inode_ref
->inode
, ino_blocks
);
657 inode_ref
->dirty
= true;
659 /* Update block group free blocks count */
660 uint32_t free_blocks
=
661 ext4_block_group_get_free_blocks_count(bg_ref
->block_group
, sb
);
663 ext4_block_group_set_free_blocks_count(bg_ref
->block_group
,
665 bg_ref
->dirty
= true;
668 return ext4_filesystem_put_block_group_ref(bg_ref
);