avoid using libc's internal sys/cdefs.h
[project/make_ext4fs.git] / indirect.c
1 /*
2  * Copyright (C) 2010 The Android Open Source Project
3  *
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
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
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.
15  */
16
17 #include "ext4_utils.h"
18 #include "indirect.h"
19 #include "allocate.h"
20
21 #include <sparse/sparse.h>
22
23 #include <stdlib.h>
24 #include <stdio.h>
25
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)
30 {
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);
33
34         u8 *data = calloc(backing_len, 1);
35         if (!data)
36                 critical_error_errno("calloc");
37
38         u8 *ptr = data;
39         for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) {
40                 u32 region_block;
41                 u32 region_len;
42                 u32 len;
43                 get_region(alloc, &region_block, &region_len);
44
45                 len = min(region_len * info.block_size, backing_len);
46
47                 sparse_file_add_data(ext4_sparse_file, ptr, len, region_block);
48                 ptr += len;
49                 backing_len -= len;
50         }
51
52         return data;
53 }
54
55 static void reserve_indirect_block(struct block_allocation *alloc, int len)
56 {
57         if (reserve_oob_blocks(alloc, 1)) {
58                 error("failed to reserve oob block");
59                 return;
60         }
61
62         if (advance_blocks(alloc, len)) {
63                 error("failed to advance %d blocks", len);
64                 return;
65         }
66 }
67
68 static void reserve_dindirect_block(struct block_allocation *alloc, int len)
69 {
70         if (reserve_oob_blocks(alloc, 1)) {
71                 error("failed to reserve oob block");
72                 return;
73         }
74
75         while (len > 0) {
76                 int ind_block_len = min((int)aux_info.blocks_per_ind, len);
77
78                 reserve_indirect_block(alloc, ind_block_len);
79
80                 len -= ind_block_len;
81         }
82
83 }
84
85 static void reserve_tindirect_block(struct block_allocation *alloc, int len)
86 {
87         if (reserve_oob_blocks(alloc, 1)) {
88                 error("failed to reserve oob block");
89                 return;
90         }
91
92         while (len > 0) {
93                 int dind_block_len = min((int)aux_info.blocks_per_dind, len);
94
95                 reserve_dindirect_block(alloc, dind_block_len);
96
97                 len -= dind_block_len;
98         }
99 }
100
101 static void fill_indirect_block(u32 *ind_block, int len, struct block_allocation *alloc)
102 {
103         int i;
104         for (i = 0; i < len; i++) {
105                 ind_block[i] = get_block(alloc, i);
106         }
107 }
108
109 static void fill_dindirect_block(u32 *dind_block, int len, struct block_allocation *alloc)
110 {
111         int i;
112         u32 ind_block;
113
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");
118                         return;
119                 }
120
121                 dind_block[i] = ind_block;
122
123                 u32 *ind_block_data = calloc(info.block_size, 1);
124                 sparse_file_add_data(ext4_sparse_file, ind_block_data, info.block_size,
125                                 ind_block);
126                 int ind_block_len = min((int)aux_info.blocks_per_ind, len);
127
128                 fill_indirect_block(ind_block_data, ind_block_len, alloc);
129
130                 if (advance_blocks(alloc, ind_block_len)) {
131                         error("failed to advance %d blocks", ind_block_len);
132                         return;
133                 }
134
135                 len -= ind_block_len;
136         }
137 }
138
139 static void fill_tindirect_block(u32 *tind_block, int len, struct block_allocation *alloc)
140 {
141         int i;
142         u32 dind_block;
143
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");
148                         return;
149                 }
150
151                 tind_block[i] = dind_block;
152
153                 u32 *dind_block_data = calloc(info.block_size, 1);
154                 sparse_file_add_data(ext4_sparse_file, dind_block_data, info.block_size,
155                                 dind_block);
156                 int dind_block_len = min((int)aux_info.blocks_per_dind, len);
157
158                 fill_dindirect_block(dind_block_data, dind_block_len, alloc);
159
160                 len -= dind_block_len;
161         }
162 }
163
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)
168 {
169         int len = min(*block_len, EXT4_NDIR_BLOCKS);
170         int i;
171
172         for (i = 0; i < len; i++) {
173                 inode->i_block[i] = get_block(alloc, i);
174         }
175
176         if (advance_blocks(alloc, len)) {
177                 error("failed to advance %d blocks", len);
178                 return -1;
179         }
180
181         *block_len -= len;
182         return 0;
183 }
184
185 /* Given an allocation, attach as many blocks as possible to indirect blocks,
186    and return the rest
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)
191 {
192         int len = min(*block_len, aux_info.blocks_per_ind);
193
194         int ind_block = get_oob_block(alloc, 0);
195         inode->i_block[EXT4_IND_BLOCK] = ind_block;
196
197         if (advance_oob_blocks(alloc, 1)) {
198                 error("failed to advance oob block");
199                 return -1;
200         }
201
202         u32 *ind_block_data = calloc(info.block_size, 1);
203         sparse_file_add_data(ext4_sparse_file, ind_block_data, info.block_size,
204                         ind_block);
205
206         fill_indirect_block(ind_block_data, len, alloc);
207
208         if (advance_blocks(alloc, len)) {
209                 error("failed to advance %d blocks", len);
210                 return -1;
211         }
212
213         *block_len -= len;
214         return 0;
215 }
216
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)
223 {
224         int len = min(*block_len, aux_info.blocks_per_dind);
225
226         int dind_block = get_oob_block(alloc, 0);
227         inode->i_block[EXT4_DIND_BLOCK] = dind_block;
228
229         if (advance_oob_blocks(alloc, 1)) {
230                 error("failed to advance oob block");
231                 return -1;
232         }
233
234         u32 *dind_block_data = calloc(info.block_size, 1);
235         sparse_file_add_data(ext4_sparse_file, dind_block_data, info.block_size,
236                         dind_block);
237
238         fill_dindirect_block(dind_block_data, len, alloc);
239
240         if (advance_blocks(alloc, len)) {
241                 error("failed to advance %d blocks", len);
242                 return -1;
243         }
244
245         *block_len -= len;
246         return 0;
247 }
248
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)
255 {
256         int len = min(*block_len, aux_info.blocks_per_tind);
257
258         int tind_block = get_oob_block(alloc, 0);
259         inode->i_block[EXT4_TIND_BLOCK] = tind_block;
260
261         if (advance_oob_blocks(alloc, 1)) {
262                 error("failed to advance oob block");
263                 return -1;
264         }
265
266         u32 *tind_block_data = calloc(info.block_size, 1);
267         sparse_file_add_data(ext4_sparse_file, tind_block_data, info.block_size,
268                         tind_block);
269
270         fill_tindirect_block(tind_block_data, len, alloc);
271
272         if (advance_blocks(alloc, len)) {
273                 error("failed to advance %d blocks", len);
274                 return -1;
275         }
276
277         *block_len -= len;
278         return 0;
279 }
280
281 static void reserve_all_indirect_blocks(struct block_allocation *alloc, u32 len)
282 {
283         if (len <= EXT4_NDIR_BLOCKS)
284                 return;
285
286         len -= EXT4_NDIR_BLOCKS;
287         advance_blocks(alloc, EXT4_NDIR_BLOCKS);
288
289         u32 ind_block_len = min(aux_info.blocks_per_ind, len);
290         reserve_indirect_block(alloc, ind_block_len);
291
292         len -= ind_block_len;
293         if (len == 0)
294                 return;
295
296         u32 dind_block_len = min(aux_info.blocks_per_dind, len);
297         reserve_dindirect_block(alloc, dind_block_len);
298
299         len -= dind_block_len;
300         if (len == 0)
301                 return;
302
303         u32 tind_block_len = min(aux_info.blocks_per_tind, len);
304         reserve_tindirect_block(alloc, tind_block_len);
305
306         len -= tind_block_len;
307         if (len == 0)
308                 return;
309
310         error("%d blocks remaining", len);
311 }
312
313 static u32 indirect_blocks_needed(u32 len)
314 {
315         u32 ind = 0;
316
317         if (len <= EXT4_NDIR_BLOCKS)
318                 return ind;
319
320         len -= EXT4_NDIR_BLOCKS;
321
322         /* We will need an indirect block for the rest of the blocks */
323         ind += DIV_ROUND_UP(len, aux_info.blocks_per_ind);
324
325         if (len <= aux_info.blocks_per_ind)
326                 return ind;
327
328         len -= aux_info.blocks_per_ind;
329
330         ind += DIV_ROUND_UP(len, aux_info.blocks_per_dind);
331
332         if (len <= aux_info.blocks_per_dind)
333                 return ind;
334
335         len -= aux_info.blocks_per_dind;
336
337         ind += DIV_ROUND_UP(len, aux_info.blocks_per_tind);
338
339         if (len <= aux_info.blocks_per_tind)
340                 return ind;
341
342         critical_error("request too large");
343         return 0;
344 }
345
346 static int do_inode_attach_indirect(struct ext4_inode *inode,
347                 struct block_allocation *alloc, u32 block_len)
348 {
349         u32 count = block_len;
350
351         if (inode_attach_direct_blocks(inode, alloc, &count)) {
352                 error("failed to attach direct blocks to inode");
353                 return -1;
354         }
355
356         if (count > 0) {
357                 if (inode_attach_indirect_blocks(inode, alloc, &count)) {
358                         error("failed to attach indirect blocks to inode");
359                         return -1;
360                 }
361         }
362
363         if (count > 0) {
364                 if (inode_attach_dindirect_blocks(inode, alloc, &count)) {
365                         error("failed to attach dindirect blocks to inode");
366                         return -1;
367                 }
368         }
369
370         if (count > 0) {
371                 if (inode_attach_tindirect_blocks(inode, alloc, &count)) {
372                         error("failed to attach tindirect blocks to inode");
373                         return -1;
374                 }
375         }
376
377         if (count) {
378                 error("blocks left after triply-indirect allocation");
379                 return -1;
380         }
381
382         rewind_alloc(alloc);
383
384         return 0;
385 }
386
387 static struct block_allocation *do_inode_allocate_indirect(
388                 u32 block_len)
389 {
390         u32 indirect_len = indirect_blocks_needed(block_len);
391
392         struct block_allocation *alloc = allocate_blocks(block_len + indirect_len);
393
394         if (alloc == NULL) {
395                 error("Failed to allocate %d blocks", block_len + indirect_len);
396                 return NULL;
397         }
398
399         return alloc;
400 }
401
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)
404 {
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);
408
409         alloc = do_inode_allocate_indirect(block_len);
410         if (alloc == NULL) {
411                 error("failed to allocate extents for %lu bytes", len);
412                 return;
413         }
414
415         reserve_all_indirect_blocks(alloc, block_len);
416         rewind_alloc(alloc);
417
418         if (do_inode_attach_indirect(inode, alloc, block_len))
419                 error("failed to attach blocks to indirect inode");
420
421         inode->i_flags = 0;
422         inode->i_blocks_lo = (block_len + indirect_len) * info.block_size / 512;
423         inode->i_size_lo = len;
424
425         free_alloc(alloc);
426 }
427
428 void inode_attach_resize(struct ext4_inode *inode,
429                 struct block_allocation *alloc)
430 {
431         u32 block_len = block_allocation_len(alloc);
432         u32 superblocks = block_len / info.bg_desc_reserve_blocks;
433         u32 i, j;
434         u64 blocks;
435         u64 size;
436
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);
440
441         append_oob_allocation(alloc, 1);
442         u32 dind_block = get_oob_block(alloc, 0);
443
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,
448                         dind_block);
449
450         u32 *ind_block_data = calloc(info.block_size, info.bg_desc_reserve_blocks);
451         if (!ind_block_data)
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));
456
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;
459                 if (r < 0)
460                         r += info.bg_desc_reserve_blocks;
461
462                 dind_block_data[i] = get_block(alloc, r);
463
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);
467                 }
468         }
469
470         u32 last_block = EXT4_NDIR_BLOCKS + aux_info.blocks_per_ind +
471                         aux_info.blocks_per_ind * (info.bg_desc_reserve_blocks - 1) +
472                         superblocks - 2;
473
474         blocks = ((u64)block_len + 1) * info.block_size / 512;
475         size = (u64)last_block * info.block_size;
476
477         inode->i_block[EXT4_DIND_BLOCK] = dind_block;
478         inode->i_flags = 0;
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;
483 }
484
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
487    buffer. */
488 u8 *inode_allocate_data_indirect(struct ext4_inode *inode, unsigned long len,
489                 unsigned long backing_len)
490 {
491         struct block_allocation *alloc;
492         u32 block_len = DIV_ROUND_UP(len, info.block_size);
493         u8 *data = NULL;
494
495         alloc = do_inode_allocate_indirect(block_len);
496         if (alloc == NULL) {
497                 error("failed to allocate extents for %lu bytes", len);
498                 return NULL;
499         }
500
501         if (backing_len) {
502                 data = create_backing(alloc, backing_len);
503                 if (!data)
504                         error("failed to create backing for %lu bytes", backing_len);
505         }
506
507         rewind_alloc(alloc);
508         if (do_inode_attach_indirect(inode, alloc, block_len))
509                 error("failed to attach blocks to indirect inode");
510
511         free_alloc(alloc);
512
513         return data;
514 }