From 9579198cd7d5b88b3508f1b00ddd77bd8da60682 Mon Sep 17 00:00:00 2001 From: Mohamad Ayyash Date: Sat, 20 Feb 2016 03:46:00 +0000 Subject: Redesign make_ext4fs to incrementally generate ext4 images Allows passing a base fs mapping file through -d which preserves the location of those mapping in existing files Internal Design Doc: go/incremental-ext4 BUG: 26839493 Change-Id: I05e296693429d39466d257d1d0a3daf00510dc26 Signed-off-by: Mohamad Ayyash --- ext4_utils/allocate.c | 220 +++++++++++++++++++++++------------------- ext4_utils/allocate.h | 34 ++++++- ext4_utils/ext4_utils.c | 1 + ext4_utils/ext4_utils.h | 3 +- ext4_utils/extent.c | 59 ++++++++--- ext4_utils/make_ext4fs.c | 186 ++++++++++++++++++++++++++++++++--- ext4_utils/make_ext4fs_main.c | 26 ++++- ext4_utils/mkuserimg.sh | 20 +++- 8 files changed, 419 insertions(+), 130 deletions(-) diff --git a/ext4_utils/allocate.c b/ext4_utils/allocate.c index d18aec56..2118c277 100644 --- a/ext4_utils/allocate.c +++ b/ext4_utils/allocate.c @@ -5,7 +5,7 @@ * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * - * http://www.apache.org/licenses/LICENSE-2.0 + * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, @@ -22,31 +22,6 @@ #include #include -struct region { - u32 block; - u32 len; - int bg; - struct region *next; - struct region *prev; -}; - -struct block_group_info { - u32 first_block; - int header_blocks; - int data_blocks_used; - int has_superblock; - u8 *bitmaps; - u8 *block_bitmap; - u8 *inode_bitmap; - u8 *inode_table; - u32 free_blocks; - u32 first_free_block; - u32 free_inodes; - u32 first_free_inode; - u16 flags; - u16 used_dirs; -}; - struct xattr_list_element { struct ext4_inode *inode; struct ext4_xattr_header *header; @@ -106,7 +81,7 @@ static void region_list_remove(struct region_list *list, struct region *reg) reg->prev = NULL; } -static void region_list_append(struct region_list *list, struct region *reg) +void region_list_append(struct region_list *list, struct region *reg) { if (list->first == NULL) { list->first = reg; @@ -141,15 +116,17 @@ static void dump_region_lists(struct block_allocation *alloc) { } #endif -void print_blocks(FILE* f, struct block_allocation *alloc) +void print_blocks(FILE* f, struct block_allocation *alloc, char separator) { struct region *reg; + fputc(' ', f); for (reg = alloc->list.first; reg; reg = reg->next) { if (reg->len == 1) { - fprintf(f, " %d", reg->block); + fprintf(f, "%d", reg->block); } else { - fprintf(f, " %d-%d", reg->block, reg->block + reg->len - 1); + fprintf(f, "%d-%d", reg->block, reg->block + reg->len - 1); } + fputc(separator, f); } fputc('\n', f); } @@ -210,45 +187,38 @@ static int reserve_blocks(struct block_group_info *bg, u32 start, u32 num) unsigned int i = 0; u32 block = start; - if (num > bg->free_blocks) - return -1; - for (i = 0; i < num && block % 8 != 0; i++, block++) { if (bitmap_set_bit(bg->block_bitmap, block)) { - error("attempted to reserve already reserved block"); + error("attempted to reserve already reserved block %d and num is %d", block, num); return -1; } } for (; i + 8 <= (num & ~7); i += 8, block += 8) { if (bitmap_set_8_bits(bg->block_bitmap, block)) { - error("attempted to reserve already reserved block"); + error("attempted to reserve already reserved block %d and num is %d", block, num); return -1; } } for (; i < num; i++, block++) { if (bitmap_set_bit(bg->block_bitmap, block)) { - error("attempted to reserve already reserved block"); + error("attempted to reserve already reserved block %d and num is %d", block, num); return -1; } } bg->free_blocks -= num; - if (start == bg->first_free_block) - bg->first_free_block = start + num; return 0; } -static void free_blocks(struct block_group_info *bg, u32 num_blocks) +static void free_blocks(struct block_group_info *bg, u32 block, u32 num_blocks) { unsigned int i; - u32 block = bg->first_free_block - 1; for (i = 0; i < num_blocks; i++, block--) bg->block_bitmap[block / 8] &= ~(1 << (block % 8)); bg->free_blocks += num_blocks; - bg->first_free_block -= num_blocks; } /* Reduces an existing allocation by len blocks by return the last blocks @@ -258,14 +228,15 @@ void reduce_allocation(struct block_allocation *alloc, u32 len) { while (len) { struct region *last_reg = alloc->list.last; + struct block_group_info *bg = &aux_info.bgs[last_reg->bg]; if (last_reg->len > len) { - free_blocks(&aux_info.bgs[last_reg->bg], len); + free_blocks(bg, last_reg->block + last_reg->len - bg->first_block - 1, len); last_reg->len -= len; len = 0; } else { struct region *reg = alloc->list.last->prev; - free_blocks(&aux_info.bgs[last_reg->bg], last_reg->len); + free_blocks(bg, last_reg->block + last_reg->len - bg->first_block - 1, last_reg->len); len -= last_reg->len; if (reg) { reg->next = NULL; @@ -304,18 +275,28 @@ static void init_bg(struct block_group_info *bg, unsigned int i) bg->data_blocks_used = 0; bg->free_blocks = info.blocks_per_group; - bg->first_free_block = 0; bg->free_inodes = info.inodes_per_group; bg->first_free_inode = 1; bg->flags = 0; - if (reserve_blocks(bg, bg->first_free_block, bg->header_blocks) < 0) + bg->chunk_count = 0; + bg->max_chunk_count = 1; + bg->chunks = (struct region*) calloc(bg->max_chunk_count, sizeof(struct region)); + + if (reserve_blocks(bg, 0, bg->header_blocks) < 0) error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i); + // Add empty starting delimiter chunk + reserve_bg_chunk(i, bg->header_blocks, 0); if (bg->first_block + info.blocks_per_group > aux_info.len_blocks) { u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks; reserve_blocks(bg, info.blocks_per_group - overrun, overrun); + // Add empty ending delimiter chunk + reserve_bg_chunk(i, info.blocks_per_group - overrun, 0); + } else { + reserve_bg_chunk(i, info.blocks_per_group - 1, 0); } + } void block_allocator_init() @@ -341,73 +322,79 @@ void block_allocator_free() free(aux_info.bgs); } -static u32 ext4_allocate_blocks_from_block_group(u32 len, int bg_num) -{ - if (get_free_blocks(bg_num) < len) - return EXT4_ALLOCATE_FAILED; - - u32 block = aux_info.bgs[bg_num].first_free_block; - struct block_group_info *bg = &aux_info.bgs[bg_num]; - if (reserve_blocks(bg, bg->first_free_block, len) < 0) { - error("failed to reserve %u blocks in block group %u\n", len, bg_num); - return EXT4_ALLOCATE_FAILED; - } - - aux_info.bgs[bg_num].data_blocks_used += len; - - return bg->first_block + block; -} - /* Allocate a single block and return its block number */ u32 allocate_block() { - unsigned int i; - for (i = 0; i < aux_info.groups; i++) { - u32 block = ext4_allocate_blocks_from_block_group(1, i); - - if (block != EXT4_ALLOCATE_FAILED) - return block; + u32 block; + struct block_allocation *blk_alloc = allocate_blocks(1); + if (!blk_alloc) { + return EXT4_ALLOCATE_FAILED; } - - return EXT4_ALLOCATE_FAILED; + block = blk_alloc->list.first->block; + free_alloc(blk_alloc); + return block; } static struct region *ext4_allocate_best_fit_partial(u32 len) { - unsigned int i; - unsigned int found_bg = 0; - u32 found_bg_len = 0; + unsigned int i, j; + unsigned int found_bg = 0, found_prev_chunk = 0, found_block = 0; + u32 found_allocate_len = 0; + bool minimize = false; + struct block_group_info *bgs = aux_info.bgs; + struct region *reg; for (i = 0; i < aux_info.groups; i++) { - u32 bg_len = aux_info.bgs[i].free_blocks; - - if ((len <= bg_len && (found_bg_len == 0 || bg_len < found_bg_len)) || - (len > found_bg_len && bg_len > found_bg_len)) { - found_bg = i; - found_bg_len = bg_len; + for (j = 1; j < bgs[i].chunk_count; j++) { + u32 hole_start, hole_size; + hole_start = bgs[i].chunks[j-1].block + bgs[i].chunks[j-1].len; + hole_size = bgs[i].chunks[j].block - hole_start; + if (hole_size == len) { + // Perfect fit i.e. right between 2 chunks no need to keep searching + found_bg = i; + found_prev_chunk = j - 1; + found_block = hole_start; + found_allocate_len = hole_size; + goto done; + } else if (hole_size > len && (found_allocate_len == 0 || (found_allocate_len > hole_size))) { + found_bg = i; + found_prev_chunk = j - 1; + found_block = hole_start; + found_allocate_len = hole_size; + minimize = true; + } else if (!minimize) { + if (found_allocate_len < hole_size) { + found_bg = i; + found_prev_chunk = j - 1; + found_block = hole_start; + found_allocate_len = hole_size; + } + } } } - if (found_bg_len) { - u32 allocate_len = min(len, found_bg_len); - struct region *reg; - u32 block = ext4_allocate_blocks_from_block_group(allocate_len, found_bg); - if (block == EXT4_ALLOCATE_FAILED) { - error("failed to allocate %d blocks in block group %d", allocate_len, found_bg); - return NULL; - } - reg = malloc(sizeof(struct region)); - reg->block = block; - reg->len = allocate_len; - reg->next = NULL; - reg->prev = NULL; - reg->bg = found_bg; - return reg; - } else { + if (found_allocate_len == 0) { error("failed to allocate %u blocks, out of space?", len); + return NULL; } - - return NULL; + if (found_allocate_len > len) found_allocate_len = len; +done: + // reclaim allocated space in chunk + bgs[found_bg].chunks[found_prev_chunk].len += found_allocate_len; + if (reserve_blocks(&bgs[found_bg], + found_block, + found_allocate_len) < 0) { + error("failed to reserve %u blocks in block group %u\n", found_allocate_len, found_bg); + return NULL; + } + bgs[found_bg].data_blocks_used += found_allocate_len; + reg = malloc(sizeof(struct region)); + reg->block = found_block + bgs[found_bg].first_block; + reg->len = found_allocate_len; + reg->next = NULL; + reg->prev = NULL; + reg->bg = found_bg; + return reg; } static struct region *ext4_allocate_best_fit(u32 len) @@ -439,9 +426,9 @@ static struct region *ext4_allocate_best_fit(u32 len) /* Allocate len blocks. The blocks may be spread across multiple block groups, and are returned in a linked list of the blocks in each block group. The allocation algorithm is: - 1. If the remaining allocation is larger than any available contiguous region, - allocate the largest contiguous region and loop - 2. Otherwise, allocate the smallest contiguous region that it fits in + 1. If the remaining allocation is larger than any available contiguous region, + allocate the largest contiguous region and loop + 2. Otherwise, allocate the smallest contiguous region that it fits in */ struct block_allocation *allocate_blocks(u32 len) { @@ -452,6 +439,8 @@ struct block_allocation *allocate_blocks(u32 len) struct block_allocation *alloc = create_allocation(); alloc->list.first = reg; + while (reg->next != NULL) + reg = reg->next; alloc->list.last = reg; alloc->list.iter = alloc->list.first; alloc->list.partial_iter = 0; @@ -779,3 +768,34 @@ void free_alloc(struct block_allocation *alloc) free(alloc); } + +void reserve_bg_chunk(int bg, u32 start_block, u32 size) { + struct block_group_info *bgs = aux_info.bgs; + int chunk_count; + if (bgs[bg].chunk_count == bgs[bg].max_chunk_count) { + bgs[bg].max_chunk_count *= 2; + bgs[bg].chunks = realloc(bgs[bg].chunks, bgs[bg].max_chunk_count * sizeof(struct region)); + if (!bgs[bg].chunks) + critical_error("realloc failed"); + } + chunk_count = bgs[bg].chunk_count; + bgs[bg].chunks[chunk_count].block = start_block; + bgs[bg].chunks[chunk_count].len = size; + bgs[bg].chunks[chunk_count].bg = bg; + bgs[bg].chunk_count++; +} + +int reserve_blocks_for_allocation(struct block_allocation *alloc) { + struct region *reg; + struct block_group_info *bgs = aux_info.bgs; + + if (!alloc) return 0; + reg = alloc->list.first; + while (reg != NULL) { + if (reserve_blocks(&bgs[reg->bg], reg->block - bgs[reg->bg].first_block, reg->len) < 0) + return -1; + reg = reg->next; + } + return 0; +} + diff --git a/ext4_utils/allocate.h b/ext4_utils/allocate.h index 5c26792c..cac543f5 100644 --- a/ext4_utils/allocate.h +++ b/ext4_utils/allocate.h @@ -5,7 +5,7 @@ * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * - * http://www.apache.org/licenses/LICENSE-2.0 + * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, @@ -21,7 +21,13 @@ #include "ext4_utils.h" -struct region; +struct region { + u32 block; + u32 len; + int bg; + struct region *next; + struct region *prev; +}; struct region_list { struct region *first; @@ -37,6 +43,24 @@ struct block_allocation { struct block_allocation* next; }; +struct block_group_info { + u32 first_block; + int header_blocks; + int data_blocks_used; + int has_superblock; + u8 *bitmaps; + u8 *block_bitmap; + u8 *inode_bitmap; + u8 *inode_table; + u32 free_blocks; + u32 free_inodes; + u32 first_free_inode; + u16 flags; + u16 used_dirs; + int chunk_count; + int max_chunk_count; + struct region *chunks; +}; void block_allocator_init(); void block_allocator_free(); @@ -69,6 +93,8 @@ void append_region(struct block_allocation *alloc, u32 block, u32 len, int bg); struct block_allocation *create_allocation(); int append_oob_allocation(struct block_allocation *alloc, u32 len); -void print_blocks(FILE* f, struct block_allocation *alloc); - +void region_list_append(struct region_list *list, struct region *reg); +void print_blocks(FILE* f, struct block_allocation *alloc, char separator); +void reserve_bg_chunk(int bg, u32 start_block, u32 size); +int reserve_blocks_for_allocation(struct block_allocation *alloc); #endif diff --git a/ext4_utils/ext4_utils.c b/ext4_utils/ext4_utils.c index 28f650d4..fba4f9fa 100644 --- a/ext4_utils/ext4_utils.c +++ b/ext4_utils/ext4_utils.c @@ -49,6 +49,7 @@ int force = 0; struct fs_info info; struct fs_aux_info aux_info; struct sparse_file *ext4_sparse_file; +struct block_allocation *base_fs_allocations = NULL; jmp_buf setjmp_env; diff --git a/ext4_utils/ext4_utils.h b/ext4_utils/ext4_utils.h index 0159dbe2..0fbbdd31 100644 --- a/ext4_utils/ext4_utils.h +++ b/ext4_utils/ext4_utils.h @@ -119,6 +119,7 @@ struct fs_aux_info { extern struct fs_info info; extern struct fs_aux_info aux_info; extern struct sparse_file *ext4_sparse_file; +extern struct block_allocation *base_fs_allocations; extern jmp_buf setjmp_env; @@ -161,7 +162,7 @@ int make_ext4fs_internal(int fd, const char *directory, const char *_target_out_ const char *mountpoint, fs_config_func_t fs_config_func, int gzip, int sparse, int crc, int wipe, int real_uuid, struct selabel_handle *sehnd, int verbose, time_t fixed_time, - FILE* block_list_file); + FILE* block_list_file, FILE* base_alloc_file_in, FILE* base_alloc_file_out); int read_ext(int fd, int verbose); diff --git a/ext4_utils/extent.c b/ext4_utils/extent.c index 1900b104..42ddd97d 100644 --- a/ext4_utils/extent.c +++ b/ext4_utils/extent.c @@ -5,7 +5,7 @@ * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * - * http://www.apache.org/licenses/LICENSE-2.0 + * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, @@ -72,23 +72,43 @@ static void extent_create_backing_file(struct block_allocation *alloc, } static struct block_allocation *do_inode_allocate_extents( - struct ext4_inode *inode, u64 len) + struct ext4_inode *inode, u64 len, struct block_allocation *prealloc) { - u32 block_len = DIV_ROUND_UP(len, info.block_size); - struct block_allocation *alloc = allocate_blocks(block_len + 1); + u32 block_len = DIV_ROUND_UP(len, info.block_size), prealloc_block_len; + struct block_allocation *alloc; u32 extent_block = 0; u32 file_block = 0; struct ext4_extent *extent; u64 blocks; - if (alloc == NULL) { - error("Failed to allocate %d blocks\n", block_len + 1); - return NULL; + if (!prealloc) { + alloc = allocate_blocks(block_len + 1); + if (alloc == NULL) { + error("Failed to allocate %d blocks\n", block_len + 1); + return NULL; + } + } else { + prealloc_block_len = block_allocation_len(prealloc); + if (block_len + 1 > prealloc_block_len) { + alloc = allocate_blocks(block_len + 1 - prealloc_block_len); + if (alloc == NULL) { + error("Failed to allocate %d blocks\n", + block_len + 1 - prealloc_block_len); + return NULL; + } + region_list_append(&prealloc->list, alloc->list.first); + free(alloc); + } + alloc = prealloc; } int allocation_len = block_allocation_num_regions(alloc); if (allocation_len <= 3) { reduce_allocation(alloc, 1); + // IMPORTANT: reduce_allocation may have changed allocation + // length, otherwise file corruption happens when fs thinks + // a block is missing from extent header. + allocation_len = block_allocation_num_regions(alloc); } else { reserve_oob_blocks(alloc, 1); extent_block = get_oob_block(alloc, 0); @@ -183,7 +203,7 @@ u8 *inode_allocate_data_extents(struct ext4_inode *inode, u64 len, struct block_allocation *alloc; u8 *data = NULL; - alloc = do_inode_allocate_extents(inode, len); + alloc = do_inode_allocate_extents(inode, len, NULL); if (alloc == NULL) { error("failed to allocate extents for %"PRIu64" bytes", len); return NULL; @@ -205,9 +225,26 @@ u8 *inode_allocate_data_extents(struct ext4_inode *inode, u64 len, struct block_allocation* inode_allocate_file_extents(struct ext4_inode *inode, u64 len, const char *filename) { - struct block_allocation *alloc; + struct block_allocation *alloc, *prealloc = base_fs_allocations, *prev_prealloc = NULL; + // TODO(mkayyash): base_fs_allocations is sorted by filename, consider + // storing it in an array and then binary searching for a filename match instead + while (prealloc && prealloc->filename != NULL) { + if (!strcmp(filename, prealloc->filename)) { + break; + } + prev_prealloc = prealloc; + prealloc = prealloc->next; + } + if (prealloc) { + if (!prev_prealloc) { + base_fs_allocations = base_fs_allocations->next; + } else { + prev_prealloc->next = prealloc->next; + } + prealloc->next = NULL; + } - alloc = do_inode_allocate_extents(inode, len); + alloc = do_inode_allocate_extents(inode, len, prealloc); if (alloc == NULL) { error("failed to allocate extents for %"PRIu64" bytes", len); return NULL; @@ -222,7 +259,7 @@ void inode_allocate_extents(struct ext4_inode *inode, u64 len) { struct block_allocation *alloc; - alloc = do_inode_allocate_extents(inode, len); + alloc = do_inode_allocate_extents(inode, len, NULL); if (alloc == NULL) { error("failed to allocate extents for %"PRIu64" bytes", len); return; diff --git a/ext4_utils/make_ext4fs.c b/ext4_utils/make_ext4fs.c index 913a40df..7752e6b9 100644 --- a/ext4_utils/make_ext4fs.c +++ b/ext4_utils/make_ext4fs.c @@ -5,7 +5,7 @@ * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * - * http://www.apache.org/licenses/LICENSE-2.0 + * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, @@ -79,6 +79,13 @@ #endif +#define MAX_PATH 4096 +#define MAX_BLK_MAPPING_STR 1000 + +const int blk_file_major_ver = 1; +const int blk_file_minor_ver = 0; +const char *blk_file_header_fmt = "Base EXT4 version %d.%d"; + /* TODO: Not implemented: Allocating blocks in the same block group as the file inode Hash or binary tree directories @@ -91,7 +98,7 @@ static int filter_dot(const struct dirent *d) } static u32 build_default_directory_structure(const char *dir_path, - struct selabel_handle *sehnd) + struct selabel_handle *sehnd) { u32 inode; u32 root_inode; @@ -425,8 +432,8 @@ int make_ext4fs_sparse_fd_directory(int fd, long long len, info.len = len; return make_ext4fs_internal(fd, directory, NULL, mountpoint, NULL, - 0, 1, 0, 0, 0, - sehnd, 0, -1, NULL); + 0, 1, 0, 0, 0, + sehnd, 0, -1, NULL, NULL, NULL); } int make_ext4fs(const char *filename, long long len, @@ -436,8 +443,8 @@ int make_ext4fs(const char *filename, long long len, } int make_ext4fs_directory(const char *filename, long long len, - const char *mountpoint, struct selabel_handle *sehnd, - const char *directory) + const char *mountpoint, struct selabel_handle *sehnd, + const char *directory) { int fd; int status; @@ -452,8 +459,8 @@ int make_ext4fs_directory(const char *filename, long long len, } status = make_ext4fs_internal(fd, directory, NULL, mountpoint, NULL, - 0, 0, 0, 1, 0, - sehnd, 0, -1, NULL); + 0, 0, 0, 1, 0, + sehnd, 0, -1, NULL, NULL, NULL); close(fd); return status; @@ -519,17 +526,158 @@ static char *canonicalize_rel_slashes(const char *str) return canonicalize_slashes(str, false); } +static int compare_chunks(const void* chunk1, const void* chunk2) { + struct region* c1 = (struct region*) chunk1; + struct region* c2 = (struct region*) chunk2; + return c1->block - c2->block; +} + +static int get_block_group(u32 block) { + int i, group = 0; + for(i = 0; i < aux_info.groups; i++) { + if (block >= aux_info.bgs[i].first_block) + group = i; + else + break; + } + return group; +} + +static void extract_base_fs_allocations(const char *directory, const char *mountpoint, + FILE* base_alloc_file_in) { +#define err_msg "base file badly formatted" + // FORMAT Version 1.0: filename blk_mapping + const char *base_alloc_file_in_format = "%s %s"; + const int base_file_format_param_count = 2; + + char stored_file_name[MAX_PATH], real_file_name[MAX_PATH], file_map[MAX_BLK_MAPPING_STR]; + struct block_allocation *fs_alloc; + struct block_group_info *bgs = aux_info.bgs; + int i, major_version = 0, minor_version = 0; + char *base_file_line = NULL; + size_t base_file_line_len = 0; + + printf("[v%d.%d] Generating an Incremental EXT4 image\n", + blk_file_major_ver, blk_file_minor_ver); + if (base_fs_allocations == NULL) + base_fs_allocations = create_allocation(); + fs_alloc = base_fs_allocations; + + fscanf(base_alloc_file_in, blk_file_header_fmt, &major_version, &minor_version); + if (major_version == 0) { + critical_error("Invalid base file"); + } + + if (major_version != blk_file_major_ver) { + critical_error("Incompatible base file: version required is %d.X", + blk_file_major_ver); + } + + if (minor_version < blk_file_minor_ver) { + critical_error("Incompatible base file: version required is %d.%d or above", + blk_file_major_ver, blk_file_minor_ver); + } + + while (getline(&base_file_line, &base_file_line_len, base_alloc_file_in) != -1) { + if (sscanf(base_file_line, base_alloc_file_in_format, &stored_file_name, &file_map) + != base_file_format_param_count) { + continue; + } + if (strlen(stored_file_name) < strlen(mountpoint)) { + continue; + } + snprintf(real_file_name, MAX_PATH, "%s%s", directory, stored_file_name + strlen(mountpoint)); + if (!access(real_file_name, R_OK)) { + char *block_range, *end_string; + int real_file_fd; + u32 start_block, end_block, block_file_size; + u32 real_file_block_size; + + real_file_fd = open(real_file_name, O_RDONLY); + if (real_file_fd == -1) { + critical_error(err_msg); + } + real_file_block_size = get_file_size(real_file_fd); + close(real_file_fd); + real_file_block_size = DIV_ROUND_UP(real_file_block_size, info.block_size); + fs_alloc->filename = strdup(real_file_name); + block_range = strtok_r(file_map, ",", &end_string); + while (block_range && real_file_block_size) { + int block_group; + char *range, *end_token = NULL; + range = strtok_r(block_range, "-", &end_token); + if (!range) { + critical_error(err_msg); + } + start_block = parse_num(range); + range = strtok_r(NULL, "-", &end_token); + if (!range) { + end_block = start_block; + } else { + end_block = parse_num(range); + } + block_file_size = end_block - start_block + 1; + if (block_file_size > real_file_block_size) { + block_file_size = real_file_block_size; + } + // Assummption is that allocations are within the same block group + block_group = get_block_group(start_block); + if (block_group != get_block_group(end_block)) { + critical_error("base file allocation's end block is in a different " + "block group than start block. did you change fs params?"); + } + block_range = strtok_r(NULL, ",", &end_string); + append_region(fs_alloc, start_block, block_file_size, block_group); + reserve_bg_chunk(block_group, start_block - bgs[block_group].first_block, block_file_size); + real_file_block_size -= block_file_size; + } + if (reserve_blocks_for_allocation(fs_alloc) < 0) + critical_error("failed to reserve base fs allocation"); + fs_alloc->next = create_allocation(); + fs_alloc = fs_alloc->next; + } + } + + for (i = 0; i < aux_info.groups; i++) { + qsort(bgs[i].chunks, bgs[i].chunk_count, sizeof(struct region), compare_chunks); + } + + free(base_file_line); + +#undef err_msg +} + +void generate_base_alloc_file_out(FILE* base_alloc_file_out, char* dir, char* mountpoint, + struct block_allocation* p) +{ + size_t dirlen = dir ? strlen(dir) : 0; + fprintf(base_alloc_file_out, blk_file_header_fmt, blk_file_major_ver, blk_file_minor_ver); + fputc('\n', base_alloc_file_out); + while (p) { + if (dir && strncmp(p->filename, dir, dirlen) == 0) { + // substitute mountpoint for the leading directory in the filename, in the output file + fprintf(base_alloc_file_out, "%s%s", mountpoint, p->filename + dirlen); + } else { + fprintf(base_alloc_file_out, "%s", p->filename); + } + print_blocks(base_alloc_file_out, p, ','); + struct block_allocation* pn = p->next; + p = pn; + } +} + int make_ext4fs_internal(int fd, const char *_directory, const char *_target_out_directory, const char *_mountpoint, fs_config_func_t fs_config_func, int gzip, int sparse, int crc, int wipe, int real_uuid, struct selabel_handle *sehnd, int verbose, time_t fixed_time, - FILE* block_list_file) + FILE* block_list_file, FILE* base_alloc_file_in, FILE* base_alloc_file_out) { u32 root_inode_num; u16 root_mode; char *mountpoint; char *directory = NULL; char *target_out_directory = NULL; + struct block_allocation* p; if (setjmp(setjmp_env)) return EXIT_FAILURE; /* Handle a call to longjmp() */ @@ -627,6 +775,9 @@ int make_ext4fs_internal(int fd, const char *_directory, const char *_target_out ext4_fill_in_sb(real_uuid); + if (base_alloc_file_in) { + extract_base_fs_allocations(directory, mountpoint, base_alloc_file_in); + } if (reserve_inodes(0, 10) == EXT4_ALLOCATE_FAILED) error("failed to reserve first 10 inodes"); @@ -670,6 +821,8 @@ int make_ext4fs_internal(int fd, const char *_directory, const char *_target_out ext4_update_free(); + // TODO: Consider migrating the OTA tools to the new base alloc file format + // used for generating incremental images (see go/incremental-ext4) if (block_list_file) { size_t dirlen = directory ? strlen(directory) : 0; struct block_allocation* p = get_saved_allocation_chain(); @@ -680,13 +833,17 @@ int make_ext4fs_internal(int fd, const char *_directory, const char *_target_out } else { fprintf(block_list_file, "%s", p->filename); } - print_blocks(block_list_file, p); + print_blocks(block_list_file, p, ' '); struct block_allocation* pn = p->next; - free_alloc(p); p = pn; } } + if (base_alloc_file_out) { + struct block_allocation* p = get_saved_allocation_chain(); + generate_base_alloc_file_out(base_alloc_file_out, directory, mountpoint, p); + } + printf("Created filesystem with %d/%d inodes and %d/%d blocks\n", aux_info.sb->s_inodes_count - aux_info.sb->s_free_inodes_count, aux_info.sb->s_inodes_count, @@ -702,6 +859,13 @@ int make_ext4fs_internal(int fd, const char *_directory, const char *_target_out sparse_file_destroy(ext4_sparse_file); ext4_sparse_file = NULL; + p = get_saved_allocation_chain(); + while (p) { + struct block_allocation* pn = p->next; + free_alloc(p); + p = pn; + } + free(mountpoint); free(directory); diff --git a/ext4_utils/make_ext4fs_main.c b/ext4_utils/make_ext4fs_main.c index 03872db6..56ced5b5 100644 --- a/ext4_utils/make_ext4fs_main.c +++ b/ext4_utils/make_ext4fs_main.c @@ -57,6 +57,7 @@ static void usage(char *path) fprintf(stderr, " [ -L