Allow creating empty filesystem images
[project/make_ext4fs.git] / allocate.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 "allocate.h"
19
20 #include <sparse/sparse.h>
21
22 #include <stdio.h>
23 #include <stdlib.h>
24
25 struct region {
26         u32 block;
27         u32 len;
28         int bg;
29         struct region *next;
30         struct region *prev;
31 };
32
33 struct block_group_info {
34         u32 first_block;
35         int header_blocks;
36         int data_blocks_used;
37         int has_superblock;
38         u8 *bitmaps;
39         u8 *block_bitmap;
40         u8 *inode_bitmap;
41         u8 *inode_table;
42         u32 free_blocks;
43         u32 first_free_block;
44         u32 free_inodes;
45         u32 first_free_inode;
46         u16 flags;
47         u16 used_dirs;
48 };
49
50 struct xattr_list_element {
51         struct ext4_inode *inode;
52         struct ext4_xattr_header *header;
53         struct xattr_list_element *next;
54 };
55
56 struct block_allocation *create_allocation()
57 {
58         struct block_allocation *alloc = malloc(sizeof(struct block_allocation));
59         alloc->list.first = NULL;
60         alloc->list.last = NULL;
61         alloc->oob_list.first = NULL;
62         alloc->oob_list.last = NULL;
63         alloc->list.iter = NULL;
64         alloc->list.partial_iter = 0;
65         alloc->oob_list.iter = NULL;
66         alloc->oob_list.partial_iter = 0;
67         alloc->filename = NULL;
68         alloc->next = NULL;
69         return alloc;
70 }
71
72 static struct ext4_xattr_header *xattr_list_find(struct ext4_inode *inode)
73 {
74         struct xattr_list_element *element;
75         for (element = aux_info.xattrs; element != NULL; element = element->next) {
76                 if (element->inode == inode)
77                         return element->header;
78         }
79         return NULL;
80 }
81
82 static void xattr_list_insert(struct ext4_inode *inode, struct ext4_xattr_header *header)
83 {
84         struct xattr_list_element *element = malloc(sizeof(struct xattr_list_element));
85         element->inode = inode;
86         element->header = header;
87         element->next = aux_info.xattrs;
88         aux_info.xattrs = element;
89 }
90
91 static void region_list_remove(struct region_list *list, struct region *reg)
92 {
93         if (reg->prev)
94                 reg->prev->next = reg->next;
95
96         if (reg->next)
97                 reg->next->prev = reg->prev;
98
99         if (list->first == reg)
100                 list->first = reg->next;
101
102         if (list->last == reg)
103                 list->last = reg->prev;
104
105         reg->next = NULL;
106         reg->prev = NULL;
107 }
108
109 static void region_list_append(struct region_list *list, struct region *reg)
110 {
111         if (list->first == NULL) {
112                 list->first = reg;
113                 list->last = reg;
114                 list->iter = reg;
115                 list->partial_iter = 0;
116                 reg->prev = NULL;
117         } else {
118                 list->last->next = reg;
119                 reg->prev = list->last;
120                 list->last = reg;
121         }
122         reg->next = NULL;
123 }
124
125 #if 0
126 static void dump_starting_from(struct region *reg)
127 {
128         for (; reg; reg = reg->next) {
129                 printf("%p: Blocks %d-%d (%d)\n", reg,
130                            reg->block, reg->block + reg->len - 1, reg->len)
131         }
132 }
133
134 static void dump_region_lists(struct block_allocation *alloc) {
135
136         printf("Main list:\n");
137         dump_starting_from(alloc->list.first);
138
139         printf("OOB list:\n");
140         dump_starting_from(alloc->oob_list.first);
141 }
142 #endif
143
144 void print_blocks(FILE* f, struct block_allocation *alloc)
145 {
146         struct region *reg;
147         for (reg = alloc->list.first; reg; reg = reg->next) {
148                 if (reg->len == 1) {
149                         fprintf(f, " %d", reg->block);
150                 } else {
151                         fprintf(f, " %d-%d", reg->block, reg->block + reg->len - 1);
152                 }
153         }
154         fputc('\n', f);
155 }
156
157 void append_region(struct block_allocation *alloc,
158                 u32 block, u32 len, int bg_num)
159 {
160         struct region *reg;
161         reg = malloc(sizeof(struct region));
162         reg->block = block;
163         reg->len = len;
164         reg->bg = bg_num;
165         reg->next = NULL;
166
167         region_list_append(&alloc->list, reg);
168 }
169
170 static void allocate_bg_inode_table(struct block_group_info *bg)
171 {
172         if (bg->inode_table != NULL)
173                 return;
174
175         u32 block = bg->first_block + 2;
176
177         if (bg->has_superblock)
178                 block += aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks + 1;
179
180         bg->inode_table = calloc(aux_info.inode_table_blocks, info.block_size);
181         if (bg->inode_table == NULL)
182                 critical_error_errno("calloc");
183
184         sparse_file_add_data(ext4_sparse_file, bg->inode_table,
185                         aux_info.inode_table_blocks     * info.block_size, block);
186
187         bg->flags &= ~EXT4_BG_INODE_UNINIT;
188 }
189
190 static int bitmap_set_bit(u8 *bitmap, u32 bit)
191 {
192         if (bitmap[bit / 8] & 1 << (bit % 8))
193                 return 1;
194
195         bitmap[bit / 8] |= 1 << (bit % 8);
196         return 0;
197 }
198
199 static int bitmap_set_8_bits(u8 *bitmap, u32 bit)
200 {
201         int ret = bitmap[bit / 8];
202         bitmap[bit / 8] = 0xFF;
203         return ret;
204 }
205
206 /* Marks a the first num_blocks blocks in a block group as used, and accounts
207  for them in the block group free block info. */
208 static int reserve_blocks(struct block_group_info *bg, u32 start, u32 num)
209 {
210         unsigned int i = 0;
211
212         u32 block = start;
213         if (num > bg->free_blocks)
214                 return -1;
215
216         for (i = 0; i < num && block % 8 != 0; i++, block++) {
217                 if (bitmap_set_bit(bg->block_bitmap, block)) {
218                         error("attempted to reserve already reserved block");
219                         return -1;
220                 }
221         }
222
223         for (; i + 8 <= (num & ~7); i += 8, block += 8) {
224                 if (bitmap_set_8_bits(bg->block_bitmap, block)) {
225                         error("attempted to reserve already reserved block");
226                         return -1;
227                 }
228         }
229
230         for (; i < num; i++, block++) {
231                 if (bitmap_set_bit(bg->block_bitmap, block)) {
232                         error("attempted to reserve already reserved block");
233                         return -1;
234                 }
235         }
236
237         bg->free_blocks -= num;
238         if (start == bg->first_free_block)
239                 bg->first_free_block = start + num;
240
241         return 0;
242 }
243
244 static void free_blocks(struct block_group_info *bg, u32 num_blocks)
245 {
246         unsigned int i;
247         u32 block = bg->first_free_block - 1;
248         for (i = 0; i < num_blocks; i++, block--)
249                 bg->block_bitmap[block / 8] &= ~(1 << (block % 8));
250         bg->free_blocks += num_blocks;
251         bg->first_free_block -= num_blocks;
252 }
253
254 /* Reduces an existing allocation by len blocks by return the last blocks
255    to the free pool in their block group. Assumes that the blocks being
256    returned were the last ones allocated out of the block group */
257 void reduce_allocation(struct block_allocation *alloc, u32 len)
258 {
259         while (len) {
260                 struct region *last_reg = alloc->list.last;
261
262                 if (last_reg->len > len) {
263                         free_blocks(&aux_info.bgs[last_reg->bg], len);
264                         last_reg->len -= len;
265                         len = 0;
266                 } else {
267                         struct region *reg = alloc->list.last->prev;
268                         free_blocks(&aux_info.bgs[last_reg->bg], last_reg->len);
269                         len -= last_reg->len;
270                         if (reg) {
271                                 reg->next = NULL;
272                         } else {
273                                 alloc->list.first = NULL;
274                                 alloc->list.last = NULL;
275                                 alloc->list.iter = NULL;
276                                 alloc->list.partial_iter = 0;
277                         }
278                         free(last_reg);
279                 }
280         }
281 }
282
283 static void init_bg(struct block_group_info *bg, unsigned int i)
284 {
285         int header_blocks = 2 + aux_info.inode_table_blocks;
286
287         bg->has_superblock = ext4_bg_has_super_block(i);
288
289         if (bg->has_superblock)
290                 header_blocks += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks;
291
292         bg->bitmaps = calloc(info.block_size, 2);
293         bg->block_bitmap = bg->bitmaps;
294         bg->inode_bitmap = bg->bitmaps + info.block_size;
295
296         bg->header_blocks = header_blocks;
297         bg->first_block = aux_info.first_data_block + i * info.blocks_per_group;
298
299         u32 block = bg->first_block;
300         if (bg->has_superblock)
301                 block += 1 + aux_info.bg_desc_blocks +  info.bg_desc_reserve_blocks;
302         sparse_file_add_data(ext4_sparse_file, bg->bitmaps, 2 * info.block_size,
303                         block);
304
305         bg->data_blocks_used = 0;
306         bg->free_blocks = info.blocks_per_group;
307         bg->first_free_block = 0;
308         bg->free_inodes = info.inodes_per_group;
309         bg->first_free_inode = 1;
310         bg->flags = EXT4_BG_INODE_UNINIT;
311
312         if (reserve_blocks(bg, bg->first_free_block, bg->header_blocks) < 0)
313                 error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i);
314
315         if (bg->first_block + info.blocks_per_group > aux_info.len_blocks) {
316                 u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks;
317                 reserve_blocks(bg, info.blocks_per_group - overrun, overrun);
318         }
319 }
320
321 void block_allocator_init()
322 {
323         unsigned int i;
324
325         aux_info.bgs = calloc(sizeof(struct block_group_info), aux_info.groups);
326         if (aux_info.bgs == NULL)
327                 critical_error_errno("calloc");
328
329         for (i = 0; i < aux_info.groups; i++)
330                 init_bg(&aux_info.bgs[i], i);
331 }
332
333 void block_allocator_free()
334 {
335         unsigned int i;
336
337         for (i = 0; i < aux_info.groups; i++) {
338                 free(aux_info.bgs[i].bitmaps);
339                 free(aux_info.bgs[i].inode_table);
340         }
341         free(aux_info.bgs);
342 }
343
344 static u32 ext4_allocate_blocks_from_block_group(u32 len, int bg_num)
345 {
346         if (get_free_blocks(bg_num) < len)
347                 return EXT4_ALLOCATE_FAILED;
348
349         u32 block = aux_info.bgs[bg_num].first_free_block;
350         struct block_group_info *bg = &aux_info.bgs[bg_num];
351         if (reserve_blocks(bg, bg->first_free_block, len) < 0) {
352                 error("failed to reserve %u blocks in block group %u\n", len, bg_num);
353                 return EXT4_ALLOCATE_FAILED;
354         }
355
356         aux_info.bgs[bg_num].data_blocks_used += len;
357
358         return bg->first_block + block;
359 }
360
361 /* Allocate a single block and return its block number */
362 u32 allocate_block()
363 {
364         unsigned int i;
365         for (i = 0; i < aux_info.groups; i++) {
366                 u32 block = ext4_allocate_blocks_from_block_group(1, i);
367
368                 if (block != EXT4_ALLOCATE_FAILED)
369                         return block;
370         }
371
372         return EXT4_ALLOCATE_FAILED;
373 }
374
375 static struct region *ext4_allocate_best_fit_partial(u32 len)
376 {
377         unsigned int i;
378         unsigned int found_bg = 0;
379         u32 found_bg_len = 0;
380
381         for (i = 0; i < aux_info.groups; i++) {
382                 u32 bg_len = aux_info.bgs[i].free_blocks;
383
384                 if ((len <= bg_len && (found_bg_len == 0 || bg_len < found_bg_len)) ||
385                     (len > found_bg_len && bg_len > found_bg_len)) {
386                         found_bg = i;
387                         found_bg_len = bg_len;
388                 }
389         }
390
391         if (found_bg_len) {
392                 u32 allocate_len = min(len, found_bg_len);
393                 struct region *reg;
394                 u32 block = ext4_allocate_blocks_from_block_group(allocate_len, found_bg);
395                 if (block == EXT4_ALLOCATE_FAILED) {
396                         error("failed to allocate %d blocks in block group %d", allocate_len, found_bg);
397                         return NULL;
398                 }
399                 reg = malloc(sizeof(struct region));
400                 reg->block = block;
401                 reg->len = allocate_len;
402                 reg->next = NULL;
403                 reg->prev = NULL;
404                 reg->bg = found_bg;
405                 return reg;
406         } else {
407                 error("failed to allocate %u blocks, out of space?", len);
408         }
409
410         return NULL;
411 }
412
413 static struct region *ext4_allocate_best_fit(u32 len)
414 {
415         struct region *first_reg = NULL;
416         struct region *prev_reg = NULL;
417         struct region *reg;
418
419         while (len > 0) {
420                 reg = ext4_allocate_best_fit_partial(len);
421                 if (reg == NULL)
422                         return NULL;
423
424                 if (first_reg == NULL)
425                         first_reg = reg;
426
427                 if (prev_reg) {
428                         prev_reg->next = reg;
429                         reg->prev = prev_reg;
430                 }
431
432                 prev_reg = reg;
433                 len -= reg->len;
434         }
435
436         return first_reg;
437 }
438
439 /* Allocate len blocks.  The blocks may be spread across multiple block groups,
440    and are returned in a linked list of the blocks in each block group.  The
441    allocation algorithm is:
442       1.  If the remaining allocation is larger than any available contiguous region,
443           allocate the largest contiguous region and loop
444       2.  Otherwise, allocate the smallest contiguous region that it fits in
445 */
446 struct block_allocation *allocate_blocks(u32 len)
447 {
448         struct region *reg = ext4_allocate_best_fit(len);
449
450         if (reg == NULL)
451                 return NULL;
452
453         struct block_allocation *alloc = create_allocation();
454         alloc->list.first = reg;
455         alloc->list.last = reg;
456         alloc->list.iter = alloc->list.first;
457         alloc->list.partial_iter = 0;
458         return alloc;
459 }
460
461 /* Returns the number of discontiguous regions used by an allocation */
462 int block_allocation_num_regions(struct block_allocation *alloc)
463 {
464         unsigned int i;
465         struct region *reg = alloc->list.first;
466
467         for (i = 0; reg != NULL; reg = reg->next)
468                 i++;
469
470         return i;
471 }
472
473 int block_allocation_len(struct block_allocation *alloc)
474 {
475         unsigned int i;
476         struct region *reg = alloc->list.first;
477
478         for (i = 0; reg != NULL; reg = reg->next)
479                 i += reg->len;
480
481         return i;
482 }
483
484 /* Returns the block number of the block'th block in an allocation */
485 u32 get_block(struct block_allocation *alloc, u32 block)
486 {
487         struct region *reg = alloc->list.iter;
488         block += alloc->list.partial_iter;
489
490         for (; reg; reg = reg->next) {
491                 if (block < reg->len)
492                         return reg->block + block;
493                 block -= reg->len;
494         }
495         return EXT4_ALLOCATE_FAILED;
496 }
497
498 u32 get_oob_block(struct block_allocation *alloc, u32 block)
499 {
500         struct region *reg = alloc->oob_list.iter;
501         block += alloc->oob_list.partial_iter;
502
503         for (; reg; reg = reg->next) {
504                 if (block < reg->len)
505                         return reg->block + block;
506                 block -= reg->len;
507         }
508         return EXT4_ALLOCATE_FAILED;
509 }
510
511 /* Gets the starting block and length in blocks of the first region
512    of an allocation */
513 void get_region(struct block_allocation *alloc, u32 *block, u32 *len)
514 {
515         *block = alloc->list.iter->block;
516         *len = alloc->list.iter->len - alloc->list.partial_iter;
517 }
518
519 /* Move to the next region in an allocation */
520 void get_next_region(struct block_allocation *alloc)
521 {
522         alloc->list.iter = alloc->list.iter->next;
523         alloc->list.partial_iter = 0;
524 }
525
526 /* Returns the number of free blocks in a block group */
527 u32 get_free_blocks(u32 bg)
528 {
529         return aux_info.bgs[bg].free_blocks;
530 }
531
532 int last_region(struct block_allocation *alloc)
533 {
534         return (alloc->list.iter == NULL);
535 }
536
537 void rewind_alloc(struct block_allocation *alloc)
538 {
539         alloc->list.iter = alloc->list.first;
540         alloc->list.partial_iter = 0;
541 }
542
543 static struct region *do_split_allocation(struct block_allocation *alloc, u32 len)
544 {
545         struct region *reg = alloc->list.iter;
546         struct region *new;
547         struct region *tmp;
548
549         while (reg && len >= reg->len) {
550                 len -= reg->len;
551                 reg = reg->next;
552         }
553
554         if (reg == NULL && len > 0)
555                 return NULL;
556
557         if (len > 0) {
558                 new = malloc(sizeof(struct region));
559
560                 new->bg = reg->bg;
561                 new->block = reg->block + len;
562                 new->len = reg->len - len;
563                 new->next = reg->next;
564                 new->prev = reg;
565
566                 reg->next = new;
567                 reg->len = len;
568
569                 tmp = alloc->list.iter;
570                 alloc->list.iter = new;
571                 return tmp;
572         } else {
573                 return reg;
574         }
575 }
576
577 /* Splits an allocation into two allocations.  The returned allocation will
578    point to the first half, and the original allocation ptr will point to the
579    second half. */
580 static struct region *split_allocation(struct block_allocation *alloc, u32 len)
581 {
582         /* First make sure there is a split at the current ptr */
583         do_split_allocation(alloc, alloc->list.partial_iter);
584
585         /* Then split off len blocks */
586         struct region *middle = do_split_allocation(alloc, len);
587         alloc->list.partial_iter = 0;
588         return middle;
589 }
590
591 /* Reserve the next blocks for oob data (indirect or extent blocks) */
592 int reserve_oob_blocks(struct block_allocation *alloc, int blocks)
593 {
594         struct region *oob = split_allocation(alloc, blocks);
595         struct region *next;
596
597         if (oob == NULL)
598                 return -1;
599
600         while (oob && oob != alloc->list.iter) {
601                 next = oob->next;
602                 region_list_remove(&alloc->list, oob);
603                 region_list_append(&alloc->oob_list, oob);
604                 oob = next;
605         }
606
607         return 0;
608 }
609
610 static int advance_list_ptr(struct region_list *list, int blocks)
611 {
612         struct region *reg = list->iter;
613
614         while (reg != NULL && blocks > 0) {
615                 if (reg->len > list->partial_iter + blocks) {
616                         list->partial_iter += blocks;
617                         return 0;
618                 }
619
620                 blocks -= (reg->len - list->partial_iter);
621                 list->partial_iter = 0;
622                 reg = reg->next;
623         }
624
625         if (blocks > 0)
626                 return -1;
627
628         return 0;
629 }
630
631 /* Move the allocation pointer forward */
632 int advance_blocks(struct block_allocation *alloc, int blocks)
633 {
634         return advance_list_ptr(&alloc->list, blocks);
635 }
636
637 int advance_oob_blocks(struct block_allocation *alloc, int blocks)
638 {
639         return advance_list_ptr(&alloc->oob_list, blocks);
640 }
641
642 int append_oob_allocation(struct block_allocation *alloc, u32 len)
643 {
644         struct region *reg = ext4_allocate_best_fit(len);
645
646         if (reg == NULL) {
647                 error("failed to allocate %d blocks", len);
648                 return -1;
649         }
650
651         for (; reg; reg = reg->next)
652                 region_list_append(&alloc->oob_list, reg);
653
654         return 0;
655 }
656
657 /* Returns an ext4_inode structure for an inode number */
658 struct ext4_inode *get_inode(u32 inode)
659 {
660         inode -= 1;
661         int bg = inode / info.inodes_per_group;
662         inode %= info.inodes_per_group;
663
664         allocate_bg_inode_table(&aux_info.bgs[bg]);
665         return (struct ext4_inode *)(aux_info.bgs[bg].inode_table + inode *
666                 info.inode_size);
667 }
668
669 struct ext4_xattr_header *get_xattr_block_for_inode(struct ext4_inode *inode)
670 {
671         struct ext4_xattr_header *block = xattr_list_find(inode);
672         if (block != NULL)
673                 return block;
674
675         u32 block_num = allocate_block();
676         block = calloc(info.block_size, 1);
677         if (block == NULL) {
678                 error("get_xattr: failed to allocate %d", info.block_size);
679                 return NULL;
680         }
681
682         block->h_magic = cpu_to_le32(EXT4_XATTR_MAGIC);
683         block->h_refcount = cpu_to_le32(1);
684         block->h_blocks = cpu_to_le32(1);
685         inode->i_blocks_lo = cpu_to_le32(le32_to_cpu(inode->i_blocks_lo) + (info.block_size / 512));
686         inode->i_file_acl_lo = cpu_to_le32(block_num);
687
688         int result = sparse_file_add_data(ext4_sparse_file, block, info.block_size, block_num);
689         if (result != 0) {
690                 error("get_xattr: sparse_file_add_data failure %d", result);
691                 free(block);
692                 return NULL;
693         }
694         xattr_list_insert(inode, block);
695         return block;
696 }
697
698 /* Mark the first len inodes in a block group as used */
699 u32 reserve_inodes(int bg, u32 num)
700 {
701         unsigned int i;
702         u32 inode;
703
704         if (get_free_inodes(bg) < num)
705                 return EXT4_ALLOCATE_FAILED;
706
707         for (i = 0; i < num; i++) {
708                 inode = aux_info.bgs[bg].first_free_inode + i - 1;
709                 aux_info.bgs[bg].inode_bitmap[inode / 8] |= 1 << (inode % 8);
710         }
711
712         inode = aux_info.bgs[bg].first_free_inode;
713
714         aux_info.bgs[bg].first_free_inode += num;
715         aux_info.bgs[bg].free_inodes -= num;
716
717         return inode;
718 }
719
720 /* Returns the first free inode number
721    TODO: Inodes should be allocated in the block group of the data? */
722 u32 allocate_inode()
723 {
724         unsigned int bg;
725         u32 inode;
726
727         for (bg = 0; bg < aux_info.groups; bg++) {
728                 inode = reserve_inodes(bg, 1);
729                 if (inode != EXT4_ALLOCATE_FAILED)
730                         return bg * info.inodes_per_group + inode;
731         }
732
733         return EXT4_ALLOCATE_FAILED;
734 }
735
736 /* Returns the number of free inodes in a block group */
737 u32 get_free_inodes(u32 bg)
738 {
739         return aux_info.bgs[bg].free_inodes;
740 }
741
742 /* Increments the directory count of the block group that contains inode */
743 void add_directory(u32 inode)
744 {
745         int bg = (inode - 1) / info.inodes_per_group;
746         aux_info.bgs[bg].used_dirs += 1;
747 }
748
749 /* Returns the number of inodes in a block group that are directories */
750 u16 get_directories(int bg)
751 {
752         return aux_info.bgs[bg].used_dirs;
753 }
754
755 /* Returns the flags for a block group */
756 u16 get_bg_flags(int bg)
757 {
758         return aux_info.bgs[bg].flags;
759 }
760
761 /* Frees the memory used by a linked list of allocation regions */
762 void free_alloc(struct block_allocation *alloc)
763 {
764         struct region *reg;
765
766         reg = alloc->list.first;
767         while (reg) {
768                 struct region *next = reg->next;
769                 free(reg);
770                 reg = next;
771         }
772
773         reg = alloc->oob_list.first;
774         while (reg) {
775                 struct region *next = reg->next;
776                 free(reg);
777                 reg = next;
778         }
779
780         free(alloc);
781 }