2 * Copyright (C) 2010 The Android Open Source Project
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 #include "ext4_utils.h"
21 #include <sparse/sparse.h>
26 /* Creates data buffers for the first backing_len bytes of a block allocation
27 and queues them to be written */
28 static u8
*create_backing(struct block_allocation
*alloc
,
29 unsigned long backing_len
)
31 if (DIV_ROUND_UP(backing_len
, info
.block_size
) > EXT4_NDIR_BLOCKS
)
32 critical_error("indirect backing larger than %d blocks", EXT4_NDIR_BLOCKS
);
34 u8
*data
= calloc(backing_len
, 1);
36 critical_error_errno("calloc");
39 for (; alloc
!= NULL
&& backing_len
> 0; get_next_region(alloc
)) {
43 get_region(alloc
, ®ion_block
, ®ion_len
);
45 len
= min(region_len
* info
.block_size
, backing_len
);
47 sparse_file_add_data(ext4_sparse_file
, ptr
, len
, region_block
);
55 static void reserve_indirect_block(struct block_allocation
*alloc
, int len
)
57 if (reserve_oob_blocks(alloc
, 1)) {
58 error("failed to reserve oob block");
62 if (advance_blocks(alloc
, len
)) {
63 error("failed to advance %d blocks", len
);
68 static void reserve_dindirect_block(struct block_allocation
*alloc
, int len
)
70 if (reserve_oob_blocks(alloc
, 1)) {
71 error("failed to reserve oob block");
76 int ind_block_len
= min((int)aux_info
.blocks_per_ind
, len
);
78 reserve_indirect_block(alloc
, ind_block_len
);
85 static void reserve_tindirect_block(struct block_allocation
*alloc
, int len
)
87 if (reserve_oob_blocks(alloc
, 1)) {
88 error("failed to reserve oob block");
93 int dind_block_len
= min((int)aux_info
.blocks_per_dind
, len
);
95 reserve_dindirect_block(alloc
, dind_block_len
);
97 len
-= dind_block_len
;
101 static void fill_indirect_block(u32
*ind_block
, int len
, struct block_allocation
*alloc
)
104 for (i
= 0; i
< len
; i
++) {
105 ind_block
[i
] = get_block(alloc
, i
);
109 static void fill_dindirect_block(u32
*dind_block
, int len
, struct block_allocation
*alloc
)
114 for (i
= 0; len
> 0; i
++) {
115 ind_block
= get_oob_block(alloc
, 0);
116 if (advance_oob_blocks(alloc
, 1)) {
117 error("failed to reserve oob block");
121 dind_block
[i
] = ind_block
;
123 u32
*ind_block_data
= calloc(info
.block_size
, 1);
124 sparse_file_add_data(ext4_sparse_file
, ind_block_data
, info
.block_size
,
126 int ind_block_len
= min((int)aux_info
.blocks_per_ind
, len
);
128 fill_indirect_block(ind_block_data
, ind_block_len
, alloc
);
130 if (advance_blocks(alloc
, ind_block_len
)) {
131 error("failed to advance %d blocks", ind_block_len
);
135 len
-= ind_block_len
;
139 static void fill_tindirect_block(u32
*tind_block
, int len
, struct block_allocation
*alloc
)
144 for (i
= 0; len
> 0; i
++) {
145 dind_block
= get_oob_block(alloc
, 0);
146 if (advance_oob_blocks(alloc
, 1)) {
147 error("failed to reserve oob block");
151 tind_block
[i
] = dind_block
;
153 u32
*dind_block_data
= calloc(info
.block_size
, 1);
154 sparse_file_add_data(ext4_sparse_file
, dind_block_data
, info
.block_size
,
156 int dind_block_len
= min((int)aux_info
.blocks_per_dind
, len
);
158 fill_dindirect_block(dind_block_data
, dind_block_len
, alloc
);
160 len
-= dind_block_len
;
164 /* Given an allocation, attach as many blocks as possible to direct inode
165 blocks, and return the rest */
166 static int inode_attach_direct_blocks(struct ext4_inode
*inode
,
167 struct block_allocation
*alloc
, u32
*block_len
)
169 int len
= min(*block_len
, EXT4_NDIR_BLOCKS
);
172 for (i
= 0; i
< len
; i
++) {
173 inode
->i_block
[i
] = get_block(alloc
, i
);
176 if (advance_blocks(alloc
, len
)) {
177 error("failed to advance %d blocks", len
);
185 /* Given an allocation, attach as many blocks as possible to indirect blocks,
187 Assumes that the blocks necessary to hold the indirect blocks were included
188 as part of the allocation */
189 static int inode_attach_indirect_blocks(struct ext4_inode
*inode
,
190 struct block_allocation
*alloc
, u32
*block_len
)
192 int len
= min(*block_len
, aux_info
.blocks_per_ind
);
194 int ind_block
= get_oob_block(alloc
, 0);
195 inode
->i_block
[EXT4_IND_BLOCK
] = ind_block
;
197 if (advance_oob_blocks(alloc
, 1)) {
198 error("failed to advance oob block");
202 u32
*ind_block_data
= calloc(info
.block_size
, 1);
203 sparse_file_add_data(ext4_sparse_file
, ind_block_data
, info
.block_size
,
206 fill_indirect_block(ind_block_data
, len
, alloc
);
208 if (advance_blocks(alloc
, len
)) {
209 error("failed to advance %d blocks", len
);
217 /* Given an allocation, attach as many blocks as possible to doubly indirect
218 blocks, and return the rest.
219 Assumes that the blocks necessary to hold the indirect and doubly indirect
220 blocks were included as part of the allocation */
221 static int inode_attach_dindirect_blocks(struct ext4_inode
*inode
,
222 struct block_allocation
*alloc
, u32
*block_len
)
224 int len
= min(*block_len
, aux_info
.blocks_per_dind
);
226 int dind_block
= get_oob_block(alloc
, 0);
227 inode
->i_block
[EXT4_DIND_BLOCK
] = dind_block
;
229 if (advance_oob_blocks(alloc
, 1)) {
230 error("failed to advance oob block");
234 u32
*dind_block_data
= calloc(info
.block_size
, 1);
235 sparse_file_add_data(ext4_sparse_file
, dind_block_data
, info
.block_size
,
238 fill_dindirect_block(dind_block_data
, len
, alloc
);
240 if (advance_blocks(alloc
, len
)) {
241 error("failed to advance %d blocks", len
);
249 /* Given an allocation, attach as many blocks as possible to triply indirect
250 blocks, and return the rest.
251 Assumes that the blocks necessary to hold the indirect, doubly indirect and
252 triply indirect blocks were included as part of the allocation */
253 static int inode_attach_tindirect_blocks(struct ext4_inode
*inode
,
254 struct block_allocation
*alloc
, u32
*block_len
)
256 int len
= min(*block_len
, aux_info
.blocks_per_tind
);
258 int tind_block
= get_oob_block(alloc
, 0);
259 inode
->i_block
[EXT4_TIND_BLOCK
] = tind_block
;
261 if (advance_oob_blocks(alloc
, 1)) {
262 error("failed to advance oob block");
266 u32
*tind_block_data
= calloc(info
.block_size
, 1);
267 sparse_file_add_data(ext4_sparse_file
, tind_block_data
, info
.block_size
,
270 fill_tindirect_block(tind_block_data
, len
, alloc
);
272 if (advance_blocks(alloc
, len
)) {
273 error("failed to advance %d blocks", len
);
281 static void reserve_all_indirect_blocks(struct block_allocation
*alloc
, u32 len
)
283 if (len
<= EXT4_NDIR_BLOCKS
)
286 len
-= EXT4_NDIR_BLOCKS
;
287 advance_blocks(alloc
, EXT4_NDIR_BLOCKS
);
289 u32 ind_block_len
= min(aux_info
.blocks_per_ind
, len
);
290 reserve_indirect_block(alloc
, ind_block_len
);
292 len
-= ind_block_len
;
296 u32 dind_block_len
= min(aux_info
.blocks_per_dind
, len
);
297 reserve_dindirect_block(alloc
, dind_block_len
);
299 len
-= dind_block_len
;
303 u32 tind_block_len
= min(aux_info
.blocks_per_tind
, len
);
304 reserve_tindirect_block(alloc
, tind_block_len
);
306 len
-= tind_block_len
;
310 error("%d blocks remaining", len
);
313 static u32
indirect_blocks_needed(u32 len
)
317 if (len
<= EXT4_NDIR_BLOCKS
)
320 len
-= EXT4_NDIR_BLOCKS
;
322 /* We will need an indirect block for the rest of the blocks */
323 ind
+= DIV_ROUND_UP(len
, aux_info
.blocks_per_ind
);
325 if (len
<= aux_info
.blocks_per_ind
)
328 len
-= aux_info
.blocks_per_ind
;
330 ind
+= DIV_ROUND_UP(len
, aux_info
.blocks_per_dind
);
332 if (len
<= aux_info
.blocks_per_dind
)
335 len
-= aux_info
.blocks_per_dind
;
337 ind
+= DIV_ROUND_UP(len
, aux_info
.blocks_per_tind
);
339 if (len
<= aux_info
.blocks_per_tind
)
342 critical_error("request too large");
346 static int do_inode_attach_indirect(struct ext4_inode
*inode
,
347 struct block_allocation
*alloc
, u32 block_len
)
349 u32 count
= block_len
;
351 if (inode_attach_direct_blocks(inode
, alloc
, &count
)) {
352 error("failed to attach direct blocks to inode");
357 if (inode_attach_indirect_blocks(inode
, alloc
, &count
)) {
358 error("failed to attach indirect blocks to inode");
364 if (inode_attach_dindirect_blocks(inode
, alloc
, &count
)) {
365 error("failed to attach dindirect blocks to inode");
371 if (inode_attach_tindirect_blocks(inode
, alloc
, &count
)) {
372 error("failed to attach tindirect blocks to inode");
378 error("blocks left after triply-indirect allocation");
387 static struct block_allocation
*do_inode_allocate_indirect(
390 u32 indirect_len
= indirect_blocks_needed(block_len
);
392 struct block_allocation
*alloc
= allocate_blocks(block_len
+ indirect_len
);
395 error("Failed to allocate %d blocks", block_len
+ indirect_len
);
402 /* Allocates enough blocks to hold len bytes and connects them to an inode */
403 void inode_allocate_indirect(struct ext4_inode
*inode
, unsigned long len
)
405 struct block_allocation
*alloc
;
406 u32 block_len
= DIV_ROUND_UP(len
, info
.block_size
);
407 u32 indirect_len
= indirect_blocks_needed(block_len
);
409 alloc
= do_inode_allocate_indirect(block_len
);
411 error("failed to allocate extents for %lu bytes", len
);
415 reserve_all_indirect_blocks(alloc
, block_len
);
418 if (do_inode_attach_indirect(inode
, alloc
, block_len
))
419 error("failed to attach blocks to indirect inode");
422 inode
->i_blocks_lo
= (block_len
+ indirect_len
) * info
.block_size
/ 512;
423 inode
->i_size_lo
= len
;
428 void inode_attach_resize(struct ext4_inode
*inode
,
429 struct block_allocation
*alloc
)
431 u32 block_len
= block_allocation_len(alloc
);
432 u32 superblocks
= block_len
/ info
.bg_desc_reserve_blocks
;
437 if (block_len
% info
.bg_desc_reserve_blocks
)
438 critical_error("reserved blocks not a multiple of %d",
439 info
.bg_desc_reserve_blocks
);
441 append_oob_allocation(alloc
, 1);
442 u32 dind_block
= get_oob_block(alloc
, 0);
444 u32
*dind_block_data
= calloc(info
.block_size
, 1);
445 if (!dind_block_data
)
446 critical_error_errno("calloc");
447 sparse_file_add_data(ext4_sparse_file
, dind_block_data
, info
.block_size
,
450 u32
*ind_block_data
= calloc(info
.block_size
, info
.bg_desc_reserve_blocks
);
452 critical_error_errno("calloc");
453 sparse_file_add_data(ext4_sparse_file
, ind_block_data
,
454 info
.block_size
* info
.bg_desc_reserve_blocks
,
455 get_block(alloc
, 0));
457 for (i
= 0; i
< info
.bg_desc_reserve_blocks
; i
++) {
458 int r
= (i
- aux_info
.bg_desc_blocks
) % info
.bg_desc_reserve_blocks
;
460 r
+= info
.bg_desc_reserve_blocks
;
462 dind_block_data
[i
] = get_block(alloc
, r
);
464 for (j
= 1; j
< superblocks
; j
++) {
465 u32 b
= j
* info
.bg_desc_reserve_blocks
+ r
;
466 ind_block_data
[r
* aux_info
.blocks_per_ind
+ j
- 1] = get_block(alloc
, b
);
470 u32 last_block
= EXT4_NDIR_BLOCKS
+ aux_info
.blocks_per_ind
+
471 aux_info
.blocks_per_ind
* (info
.bg_desc_reserve_blocks
- 1) +
474 blocks
= ((u64
)block_len
+ 1) * info
.block_size
/ 512;
475 size
= (u64
)last_block
* info
.block_size
;
477 inode
->i_block
[EXT4_DIND_BLOCK
] = dind_block
;
479 inode
->i_blocks_lo
= blocks
;
480 inode
->osd2
.linux2
.l_i_blocks_high
= blocks
>> 32;
481 inode
->i_size_lo
= size
;
482 inode
->i_size_high
= size
>> 32;
485 /* Allocates enough blocks to hold len bytes, with backing_len bytes in a data
486 buffer, and connects them to an inode. Returns a pointer to the data
488 u8
*inode_allocate_data_indirect(struct ext4_inode
*inode
, unsigned long len
,
489 unsigned long backing_len
)
491 struct block_allocation
*alloc
;
492 u32 block_len
= DIV_ROUND_UP(len
, info
.block_size
);
495 alloc
= do_inode_allocate_indirect(block_len
);
497 error("failed to allocate extents for %lu bytes", len
);
502 data
= create_backing(alloc
, backing_len
);
504 error("failed to create backing for %lu bytes", backing_len
);
508 if (do_inode_attach_indirect(inode
, alloc
, block_len
))
509 error("failed to attach blocks to indirect inode");