From 8642b7fba54727a38f751516bcdc452fb09ef610 Mon Sep 17 00:00:00 2001 From: Brian Swetland Date: Fri, 13 Aug 2010 19:27:48 -0700 Subject: [PATCH] ext4_utils: brought over from master --- ext4_utils/Android.mk | 81 +++++ ext4_utils/MODULE_LICENSE_APACHE2 | 0 ext4_utils/NOTICE | 190 ++++++++++ ext4_utils/allocate.c | 747 ++++++++++++++++++++++++++++++++++++++ ext4_utils/allocate.h | 51 +++ ext4_utils/backed_block.c | 144 ++++++++ ext4_utils/backed_block.h | 38 ++ ext4_utils/contents.c | 241 ++++++++++++ ext4_utils/contents.h | 39 ++ ext4_utils/ext4.h | 577 +++++++++++++++++++++++++++++ ext4_utils/ext4_extents.h | 88 +++++ ext4_utils/ext4_jbd2.h | 53 +++ ext4_utils/ext4_utils.c | 404 +++++++++++++++++++++ ext4_utils/ext4_utils.h | 129 +++++++ ext4_utils/extent.c | 231 ++++++++++++ ext4_utils/extent.h | 30 ++ ext4_utils/indirect.c | 504 +++++++++++++++++++++++++ ext4_utils/indirect.h | 29 ++ ext4_utils/jbd2.h | 141 +++++++ ext4_utils/make_ext4fs.c | 327 +++++++++++++++++ ext4_utils/make_ext4fs.h | 27 ++ ext4_utils/make_ext4fs_main.c | 119 ++++++ ext4_utils/mkuserimg.sh | 48 +++ ext4_utils/output_file.c | 417 +++++++++++++++++++++ ext4_utils/output_file.h | 24 ++ ext4_utils/sha1.c | 271 ++++++++++++++ ext4_utils/sha1.h | 32 ++ ext4_utils/simg2img.c | 198 ++++++++++ ext4_utils/sparse_format.h | 47 +++ ext4_utils/uuid.c | 59 +++ ext4_utils/uuid.h | 24 ++ 31 files changed, 5310 insertions(+) create mode 100644 ext4_utils/Android.mk create mode 100644 ext4_utils/MODULE_LICENSE_APACHE2 create mode 100644 ext4_utils/NOTICE create mode 100644 ext4_utils/allocate.c create mode 100644 ext4_utils/allocate.h create mode 100644 ext4_utils/backed_block.c create mode 100644 ext4_utils/backed_block.h create mode 100644 ext4_utils/contents.c create mode 100644 ext4_utils/contents.h create mode 100644 ext4_utils/ext4.h create mode 100644 ext4_utils/ext4_extents.h create mode 100644 ext4_utils/ext4_jbd2.h create mode 100644 ext4_utils/ext4_utils.c create mode 100644 ext4_utils/ext4_utils.h create mode 100644 ext4_utils/extent.c create mode 100644 ext4_utils/extent.h create mode 100644 ext4_utils/indirect.c create mode 100644 ext4_utils/indirect.h create mode 100644 ext4_utils/jbd2.h create mode 100644 ext4_utils/make_ext4fs.c create mode 100644 ext4_utils/make_ext4fs.h create mode 100644 ext4_utils/make_ext4fs_main.c create mode 100755 ext4_utils/mkuserimg.sh create mode 100644 ext4_utils/output_file.c create mode 100644 ext4_utils/output_file.h create mode 100644 ext4_utils/sha1.c create mode 100644 ext4_utils/sha1.h create mode 100644 ext4_utils/simg2img.c create mode 100644 ext4_utils/sparse_format.h create mode 100644 ext4_utils/uuid.c create mode 100644 ext4_utils/uuid.h diff --git a/ext4_utils/Android.mk b/ext4_utils/Android.mk new file mode 100644 index 00000000..14702540 --- /dev/null +++ b/ext4_utils/Android.mk @@ -0,0 +1,81 @@ +# Copyright 2010 The Android Open Source Project + +LOCAL_PATH:= $(call my-dir) +include $(CLEAR_VARS) + +libext4_utils_src_files := \ + make_ext4fs.c \ + ext4_utils.c \ + allocate.c \ + backed_block.c \ + output_file.c \ + contents.c \ + extent.c \ + indirect.c \ + uuid.c \ + sha1.c \ + +LOCAL_SRC_FILES := $(libext4_utils_src_files) +LOCAL_MODULE := libext4_utils +LOCAL_MODULE_TAGS := optional +LOCAL_C_INCLUDES += external/zlib +LOCAL_SHARED_LIBRARIES := libz +LOCAL_PRELINK_MODULE := false + +include $(BUILD_SHARED_LIBRARY) + +include $(CLEAR_VARS) + +LOCAL_SRC_FILES := $(libext4_utils_src_files) +LOCAL_MODULE := libext4_utils +LOCAL_MODULE_TAGS := optional +LOCAL_C_INCLUDES += external/zlib +LOCAL_STATIC_LIBRARIES := libz +LOCAL_PRELINK_MODULE := false + +include $(BUILD_STATIC_LIBRARY) + +include $(CLEAR_VARS) + +LOCAL_SRC_FILES := $(libext4_utils_src_files) +LOCAL_MODULE := libext4_utils +LOCAL_MODULE_TAGS := optional +LOCAL_SHARED_LIBRARIES := libz + +include $(BUILD_HOST_STATIC_LIBRARY) + +include $(CLEAR_VARS) + +LOCAL_SRC_FILES := make_ext4fs_main.c +LOCAL_MODULE := make_ext4fs +LOCAL_MODULE_TAGS := optional +LOCAL_SHARED_LIBRARIES += libext4_utils libz + +include $(BUILD_EXECUTABLE) + +include $(CLEAR_VARS) + +LOCAL_SRC_FILES := make_ext4fs_main.c +LOCAL_MODULE := make_ext4fs +LOCAL_STATIC_LIBRARIES += libext4_utils libz + +include $(BUILD_HOST_EXECUTABLE) + +include $(CLEAR_VARS) + +LOCAL_SRC_FILES := simg2img.c +LOCAL_MODULE := simg2img + +include $(BUILD_HOST_EXECUTABLE) + +include $(CLEAR_VARS) + +LOCAL_MODULE := mkuserimg.sh +LOCAL_SRC_FILES := mkuserimg.sh +LOCAL_MODULE_CLASS := EXECUTABLES +# We don't need any additional suffix. +LOCAL_MODULE_SUFFIX := +LOCAL_BUILT_MODULE_STEM := $(notdir $(LOCAL_SRC_FILES)) +LOCAL_IS_HOST_MODULE := true + +include $(BUILD_PREBUILT) diff --git a/ext4_utils/MODULE_LICENSE_APACHE2 b/ext4_utils/MODULE_LICENSE_APACHE2 new file mode 100644 index 00000000..e69de29b diff --git a/ext4_utils/NOTICE b/ext4_utils/NOTICE new file mode 100644 index 00000000..5d142934 --- /dev/null +++ b/ext4_utils/NOTICE @@ -0,0 +1,190 @@ + + Copyright (c) 2010, The Android Open Source Project + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. + + + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + + END OF TERMS AND CONDITIONS + diff --git a/ext4_utils/allocate.c b/ext4_utils/allocate.c new file mode 100644 index 00000000..20ba1548 --- /dev/null +++ b/ext4_utils/allocate.c @@ -0,0 +1,747 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include + +#include "ext4_utils.h" +#include "allocate.h" +#include "backed_block.h" +#include "ext4.h" + +struct region_list { + struct region *first; + struct region *last; + struct region *iter; + u32 partial_iter; +}; + +struct block_allocation { + struct region_list list; + struct region_list oob_list; +}; + +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 used_dirs; +}; + +struct block_allocation *create_allocation() +{ + struct block_allocation *alloc = malloc(sizeof(struct block_allocation)); + alloc->list.first = NULL; + alloc->list.last = NULL; + alloc->oob_list.first = NULL; + alloc->oob_list.last = NULL; + alloc->list.iter = NULL; + alloc->list.partial_iter = 0; + alloc->oob_list.iter = NULL; + alloc->oob_list.partial_iter = 0; + return alloc; +} + +static void region_list_remove(struct region_list *list, struct region *reg) +{ + if (reg->prev) + reg->prev->next = reg->next; + + if (reg->next) + reg->next->prev = reg->prev; + + if (list->first == reg) + list->first = reg->next; + + if (list->last == reg) + list->last = reg->prev; + + reg->next = NULL; + reg->prev = NULL; +} + +static void region_list_append(struct region_list *list, struct region *reg) +{ + if (list->first == NULL) { + list->first = reg; + list->last = reg; + list->iter = reg; + list->partial_iter = 0; + reg->prev = NULL; + } else { + list->last->next = reg; + reg->prev = list->last; + list->last = reg; + } + reg->next = NULL; +} + +#if 0 +static void dump_starting_from(struct region *reg) +{ + for (; reg; reg = reg->next) { + printf("%p: Blocks %d-%d (%d)\n", reg, + reg->bg * info.blocks_per_group + reg->block, + reg->bg * info.blocks_per_group + reg->block + reg->len - 1, + reg->len); + } +} + +static void dump_region_lists(struct block_allocation *alloc) { + + printf("Main list:\n"); + dump_starting_from(alloc->list.first); + + printf("OOB list:\n"); + dump_starting_from(alloc->oob_list.first); +} +#endif + +void append_region(struct block_allocation *alloc, + u32 block, u32 len, int bg_num) +{ + struct region *reg; + reg = malloc(sizeof(struct region)); + reg->block = block; + reg->len = len; + reg->bg = bg_num; + reg->next = NULL; + + region_list_append(&alloc->list, reg); +} + +static void allocate_bg_inode_table(struct block_group_info *bg) +{ + if (bg->inode_table != NULL) + return; + + u32 block = bg->first_block + 2; + + if (bg->has_superblock) + block += aux_info.bg_desc_blocks + aux_info.bg_desc_reserve_blocks + 1; + + bg->inode_table = calloc(aux_info.inode_table_blocks, info.block_size); + if (bg->inode_table == NULL) + critical_error_errno("calloc"); + + queue_data_block(bg->inode_table, aux_info.inode_table_blocks + * info.block_size, block); +} + +static int bitmap_set_bit(u8 *bitmap, u32 bit) +{ + if (bitmap[bit / 8] & 1 << (bit % 8)) + return 1; + + bitmap[bit / 8] |= 1 << (bit % 8); + return 0; +} + +static int bitmap_set_8_bits(u8 *bitmap, u32 bit) +{ + int ret = bitmap[bit / 8]; + bitmap[bit / 8] = 0xFF; + return ret; +} + +/* Marks a the first num_blocks blocks in a block group as used, and accounts + for them in the block group free block info. */ +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"); + 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"); + return -1; + } + } + + for (; i < num; i++, block++) { + if (bitmap_set_bit(bg->block_bitmap, block)) { + error("attempted to reserve already reserved block"); + 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) +{ + 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 + to the free pool in their block group. Assumes that the blocks being + returned were the last ones allocated out of the block group */ +void reduce_allocation(struct block_allocation *alloc, u32 len) +{ + while (len) { + struct region *last_reg = alloc->list.last; + + if (last_reg->len > len) { + free_blocks(&aux_info.bgs[last_reg->bg], 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); + len -= last_reg->len; + if (reg) { + reg->next = NULL; + } else { + alloc->list.first = NULL; + alloc->list.last = NULL; + alloc->list.iter = NULL; + alloc->list.partial_iter = 0; + } + free(last_reg); + } + } +} + +static void init_bg(struct block_group_info *bg, unsigned int i) +{ + int header_blocks = 2 + aux_info.inode_table_blocks; + + bg->has_superblock = ext4_bg_has_super_block(i); + + if (bg->has_superblock) + header_blocks += 1 + aux_info.bg_desc_blocks + aux_info.bg_desc_reserve_blocks; + + bg->bitmaps = calloc(info.block_size, 2); + bg->block_bitmap = bg->bitmaps; + bg->inode_bitmap = bg->bitmaps + info.block_size; + + bg->header_blocks = header_blocks; + bg->first_block = aux_info.first_data_block + i * info.blocks_per_group; + + u32 block = bg->first_block; + if (bg->has_superblock) + block += 1 + aux_info.bg_desc_blocks + aux_info.bg_desc_reserve_blocks; + queue_data_block(bg->bitmaps, 2 * info.block_size, block); + + 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; + + if (reserve_blocks(bg, bg->first_free_block, bg->header_blocks) < 0) + error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i); + + u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks; + if (overrun > 0) + reserve_blocks(bg, info.blocks_per_group - overrun, overrun); +} + +void block_allocator_init() +{ + unsigned int i; + + aux_info.bgs = calloc(sizeof(struct block_group_info), aux_info.groups); + if (aux_info.bgs == NULL) + critical_error_errno("calloc"); + + for (i = 0; i < aux_info.groups; i++) + init_bg(&aux_info.bgs[i], i); +} + +void block_allocator_free() +{ + unsigned int i; + + for (i = 0; i < aux_info.groups; i++) { + free(aux_info.bgs[i].bitmaps); + free(aux_info.bgs[i].inode_table); + } + 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; +} + +static struct region *ext4_allocate_contiguous_blocks(u32 len) +{ + unsigned int i; + struct region *reg; + + for (i = 0; i < aux_info.groups; i++) { + u32 block = ext4_allocate_blocks_from_block_group(len, i); + + if (block != EXT4_ALLOCATE_FAILED) { + reg = malloc(sizeof(struct region)); + reg->block = block; + reg->len = len; + reg->next = NULL; + reg->prev = NULL; + reg->bg = i; + return reg; + } + } + + return NULL; +} + +/* 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; + } + + return EXT4_ALLOCATE_FAILED; +} + +static struct region *ext4_allocate_partial(u32 len) +{ + unsigned int i; + struct region *reg; + + for (i = 0; i < aux_info.groups; i++) { + if (aux_info.bgs[i].data_blocks_used == 0) { + u32 bg_len = aux_info.bgs[i].free_blocks; + u32 block; + + if (len <= bg_len) { + /* If the requested length would fit in a block group, + use the regular allocator to try to fit it in a partially + used block group */ + bg_len = len; + reg = ext4_allocate_contiguous_blocks(len); + } else { + block = ext4_allocate_blocks_from_block_group(bg_len, i); + + if (block == EXT4_ALLOCATE_FAILED) { + error("failed to allocate %d blocks in block group %d", bg_len, i); + return NULL; + } + + reg = malloc(sizeof(struct region)); + reg->block = block; + reg->len = bg_len; + reg->next = NULL; + reg->prev = NULL; + reg->bg = i; + } + + return reg; + } + } + return NULL; +} + +static struct region *ext4_allocate_multiple_contiguous_blocks(u32 len) +{ + struct region *first_reg = NULL; + struct region *prev_reg = NULL; + struct region *reg; + + while (len > 0) { + reg = ext4_allocate_partial(len); + if (reg == NULL) + return NULL; + + if (first_reg == NULL) + first_reg = reg; + + if (prev_reg) { + prev_reg->next = reg; + reg->prev = prev_reg; + } + + prev_reg = reg; + len -= reg->len; + } + + return first_reg; +} + +struct region *do_allocate(u32 len) +{ + struct region *reg = ext4_allocate_contiguous_blocks(len); + + if (reg == NULL) + reg = ext4_allocate_multiple_contiguous_blocks(len); + + return reg; +} + +/* 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. Try to allocate the entire block len in each block group + 2. If the request doesn't fit in any block group, allocate as many + blocks as possible into each block group that is completely empty + 3. Put the last set of blocks in the first block group they fit in +*/ +struct block_allocation *allocate_blocks(u32 len) +{ + struct region *reg = do_allocate(len); + + if (reg == NULL) + return NULL; + + struct block_allocation *alloc = create_allocation(); + alloc->list.first = reg; + alloc->list.last = reg; + alloc->list.iter = alloc->list.first; + alloc->list.partial_iter = 0; + return alloc; +} + +/* Returns the number of discontiguous regions used by an allocation */ +int block_allocation_num_regions(struct block_allocation *alloc) +{ + unsigned int i; + struct region *reg = alloc->list.first; + + for (i = 0; reg != NULL; reg = reg->next) + i++; + + return i; +} + +int block_allocation_len(struct block_allocation *alloc) +{ + unsigned int i; + struct region *reg = alloc->list.first; + + for (i = 0; reg != NULL; reg = reg->next) + i += reg->len; + + return i; +} + +/* Returns the block number of the block'th block in an allocation */ +u32 get_block(struct block_allocation *alloc, u32 block) +{ + struct region *reg = alloc->list.iter; + block += alloc->list.partial_iter; + + for (; reg; reg = reg->next) { + if (block < reg->len) + return reg->block + block; + block -= reg->len; + } + return EXT4_ALLOCATE_FAILED; +} + +u32 get_oob_block(struct block_allocation *alloc, u32 block) +{ + struct region *reg = alloc->oob_list.iter; + block += alloc->oob_list.partial_iter; + + for (; reg; reg = reg->next) { + if (block < reg->len) + return reg->block + block; + block -= reg->len; + } + return EXT4_ALLOCATE_FAILED; +} + +/* Gets the starting block and length in blocks of the first region + of an allocation */ +void get_region(struct block_allocation *alloc, u32 *block, u32 *len) +{ + *block = alloc->list.iter->block; + *len = alloc->list.iter->len - alloc->list.partial_iter; +} + +/* Move to the next region in an allocation */ +void get_next_region(struct block_allocation *alloc) +{ + alloc->list.iter = alloc->list.iter->next; + alloc->list.partial_iter = 0; +} + +/* Returns the number of free blocks in a block group */ +u32 get_free_blocks(u32 bg) +{ + return aux_info.bgs[bg].free_blocks; +} + +int last_region(struct block_allocation *alloc) +{ + return (alloc->list.iter == NULL); +} + +void rewind_alloc(struct block_allocation *alloc) +{ + alloc->list.iter = alloc->list.first; + alloc->list.partial_iter = 0; +} + +static struct region *do_split_allocation(struct block_allocation *alloc, u32 len) +{ + struct region *reg = alloc->list.iter; + struct region *new; + struct region *tmp; + + while (reg && len >= reg->len) { + len -= reg->len; + reg = reg->next; + } + + if (reg == NULL && len > 0) + return NULL; + + if (len > 0) { + new = malloc(sizeof(struct region)); + + new->bg = reg->bg; + new->block = reg->block + len; + new->len = reg->len - len; + new->next = reg->next; + new->prev = reg; + + reg->next = new; + reg->len = len; + + tmp = alloc->list.iter; + alloc->list.iter = new; + return tmp; + } else { + return reg; + } +} + +/* Splits an allocation into two allocations. The returned allocation will + point to the first half, and the original allocation ptr will point to the + second half. */ +static struct region *split_allocation(struct block_allocation *alloc, u32 len) +{ + /* First make sure there is a split at the current ptr */ + do_split_allocation(alloc, alloc->list.partial_iter); + + /* Then split off len blocks */ + struct region *middle = do_split_allocation(alloc, len); + alloc->list.partial_iter = 0; + return middle; +} + +/* Reserve the next blocks for oob data (indirect or extent blocks) */ +int reserve_oob_blocks(struct block_allocation *alloc, int blocks) +{ + struct region *oob = split_allocation(alloc, blocks); + struct region *next; + + if (oob == NULL) + return -1; + + while (oob && oob != alloc->list.iter) { + next = oob->next; + region_list_remove(&alloc->list, oob); + region_list_append(&alloc->oob_list, oob); + oob = next; + } + + return 0; +} + +static int advance_list_ptr(struct region_list *list, int blocks) +{ + struct region *reg = list->iter; + + while (reg != NULL && blocks > 0) { + if (reg->len > list->partial_iter + blocks) { + list->partial_iter += blocks; + return 0; + } + + blocks -= (reg->len - list->partial_iter); + list->partial_iter = 0; + reg = reg->next; + } + + if (blocks > 0) + return -1; + + return 0; +} + +/* Move the allocation pointer forward */ +int advance_blocks(struct block_allocation *alloc, int blocks) +{ + return advance_list_ptr(&alloc->list, blocks); +} + +int advance_oob_blocks(struct block_allocation *alloc, int blocks) +{ + return advance_list_ptr(&alloc->oob_list, blocks); +} + +int append_oob_allocation(struct block_allocation *alloc, u32 len) +{ + struct region *reg = do_allocate(len); + + if (reg == NULL) { + error("failed to allocate %d blocks", len); + return -1; + } + + for (; reg; reg = reg->next) + region_list_append(&alloc->oob_list, reg); + + return 0; +} + +/* Returns an ext4_inode structure for an inode number */ +struct ext4_inode *get_inode(u32 inode) +{ + inode -= 1; + int bg = inode / info.inodes_per_group; + inode %= info.inodes_per_group; + + allocate_bg_inode_table(&aux_info.bgs[bg]); + return (struct ext4_inode *)(aux_info.bgs[bg].inode_table + inode * + info.inode_size); +} + +/* Mark the first len inodes in a block group as used */ +u32 reserve_inodes(int bg, u32 num) +{ + unsigned int i; + u32 inode; + + if (get_free_inodes(bg) < num) + return EXT4_ALLOCATE_FAILED; + + for (i = 0; i < num; i++) { + inode = aux_info.bgs[bg].first_free_inode + i - 1; + aux_info.bgs[bg].inode_bitmap[inode / 8] |= 1 << (inode % 8); + } + + inode = aux_info.bgs[bg].first_free_inode; + + aux_info.bgs[bg].first_free_inode += num; + aux_info.bgs[bg].free_inodes -= num; + + return inode; +} + +/* Returns the first free inode number + TODO: Inodes should be allocated in the block group of the data? */ +u32 allocate_inode() +{ + unsigned int bg; + u32 inode; + + for (bg = 0; bg < aux_info.groups; bg++) { + inode = reserve_inodes(bg, 1); + if (inode != EXT4_ALLOCATE_FAILED) + return bg * info.inodes_per_group + inode; + } + + return EXT4_ALLOCATE_FAILED; +} + +/* Returns the number of free inodes in a block group */ +u32 get_free_inodes(u32 bg) +{ + return aux_info.bgs[bg].free_inodes; +} + +/* Increments the directory count of the block group that contains inode */ +void add_directory(u32 inode) +{ + int bg = (inode - 1) / info.inodes_per_group; + aux_info.bgs[bg].used_dirs += 1; +} + +/* Returns the number of inodes in a block group that are directories */ +u16 get_directories(int bg) +{ + return aux_info.bgs[bg].used_dirs; +} + +/* Frees the memory used by a linked list of allocation regions */ +void free_alloc(struct block_allocation *alloc) +{ + struct region *reg; + + reg = alloc->list.first; + while (reg) { + struct region *next = reg->next; + free(reg); + reg = next; + } + + reg = alloc->oob_list.first; + while (reg) { + struct region *next = reg->next; + free(reg); + reg = next; + } + + free(alloc); +} diff --git a/ext4_utils/allocate.h b/ext4_utils/allocate.h new file mode 100644 index 00000000..f4bed412 --- /dev/null +++ b/ext4_utils/allocate.h @@ -0,0 +1,51 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#define EXT4_ALLOCATE_FAILED (u32)(~0) + +#include "ext4_utils.h" +#include "ext4.h" + +struct block_allocation; + +void block_allocator_init(); +void block_allocator_free(); +u32 allocate_block(); +struct block_allocation *allocate_blocks(u32 len); +int block_allocation_num_regions(struct block_allocation *alloc); +int block_allocation_len(struct block_allocation *alloc); +struct ext4_inode *get_inode(u32 inode); +void reduce_allocation(struct block_allocation *alloc, u32 len); +u32 get_block(struct block_allocation *alloc, u32 block); +u32 get_oob_block(struct block_allocation *alloc, u32 block); +void get_next_region(struct block_allocation *alloc); +void get_region(struct block_allocation *alloc, u32 *block, u32 *len); +u32 get_free_blocks(u32 bg); +u32 get_free_inodes(u32 bg); +u32 reserve_inodes(int bg, u32 inodes); +void add_directory(u32 inode); +u16 get_directories(int bg); +u32 allocate_inode(); +void free_alloc(struct block_allocation *alloc); +int reserve_oob_blocks(struct block_allocation *alloc, int blocks); +int advance_blocks(struct block_allocation *alloc, int blocks); +int advance_oob_blocks(struct block_allocation *alloc, int blocks); +int last_region(struct block_allocation *alloc); +void rewind_alloc(struct block_allocation *alloc); +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); diff --git a/ext4_utils/backed_block.c b/ext4_utils/backed_block.c new file mode 100644 index 00000000..c1a2f202 --- /dev/null +++ b/ext4_utils/backed_block.c @@ -0,0 +1,144 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include + +#include "ext4_utils.h" +#include "backed_block.h" + +struct data_block { + u32 block; + u32 len; + u8 *data; + const char *filename; + off_t offset; + struct data_block *next; +}; + +static struct data_block *data_blocks = NULL; +static struct data_block *last_used = NULL; + +static void queue_db(struct data_block *new_db) +{ + struct data_block *db; + + if (data_blocks == NULL) { + data_blocks = new_db; + return; + } + + if (data_blocks->block > new_db->block) { + new_db->next = data_blocks; + data_blocks = new_db; + return; + } + + /* Optimization: blocks are mostly queued in sequence, so save the + pointer to the last db that was added, and start searching from + there if the next block number is higher */ + if (last_used && new_db->block > last_used->block) + db = last_used; + else + db = data_blocks; + last_used = new_db; + + for (; db->next && db->next->block < new_db->block; db = db->next) + ; + + if (db->next == NULL) { + db->next = new_db; + } else { + new_db->next = db->next; + db->next = new_db; + } +} + +/* Queues a block of memory to be written to the specified data blocks */ +void queue_data_block(u8 *data, u32 len, u32 block) +{ + struct data_block *db = malloc(sizeof(struct data_block)); + if (db == NULL) + critical_error_errno("malloc"); + + db->block = block; + db->len = len; + db->data = data; + db->filename = NULL; + db->next = NULL; + + queue_db(db); +} + +/* Queues a chunk of a file on disk to be written to the specified data blocks */ +void queue_data_file(const char *filename, off_t offset, u32 len, + u32 block) +{ + struct data_block *db = malloc(sizeof(struct data_block)); + if (db == NULL) + critical_error_errno("malloc"); + + db->block = block; + db->len = len; + db->filename = strdup(filename); + db->offset = offset; + db->next = NULL; + + queue_db(db); +} + +/* Iterates over the queued data blocks, calling data_func for each contiguous + data block, and file_func for each contiguous file block */ +void for_each_data_block(data_block_callback_t data_func, + data_block_file_callback_t file_func, struct output_file *out) +{ + struct data_block *db; + u32 last_block = 0; + + for (db = data_blocks; db; db = db->next) { + if (db->block < last_block) + error("data blocks out of order: %u < %u", db->block, last_block); + last_block = db->block + DIV_ROUND_UP(db->len, info.block_size) - 1; + + if (db->filename) + file_func(out, (u64)db->block * info.block_size, db->filename, db->offset, db->len); + else + data_func(out, (u64)db->block * info.block_size, db->data, db->len); + } +} + +/* Frees the memory used by the linked list of data blocks */ +void free_data_blocks() +{ + if (!data_blocks) return; + struct data_block *db = data_blocks; + while (db) { + struct data_block *next = db->next; + free((void*)db->filename); + + // There used to be a free() of db->data here, but it + // made the function crash since queue_data_block() is + // sometimes passed pointers it can't take ownership of + // (like a pointer into the middle of an allocated + // block). It's not clear what the queue_data_block + // contract is supposed to be, but we'd rather leak + // memory than crash. + + free(db); + db = next; + } + data_blocks = NULL; + last_used = NULL; +} diff --git a/ext4_utils/backed_block.h b/ext4_utils/backed_block.h new file mode 100644 index 00000000..5304f00e --- /dev/null +++ b/ext4_utils/backed_block.h @@ -0,0 +1,38 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef _BACKED_BLOCK_H_ +#define _BACKED_BLOCK_H_ + +#include +#include +#include "ext4_utils.h" +#include "output_file.h" + +typedef void (*data_block_callback_t)(struct output_file *out, u64 off, + u8 *data, int len); +typedef void (*data_block_file_callback_t)(struct output_file *out, u64 off, + const char *file, off_t offset, + int len); + +void queue_data_block(u8 *data, u32 len, u32 block); +void queue_data_file(const char *filename, off_t offset, u32 len, + u32 block); +void for_each_data_block(data_block_callback_t data_func, + data_block_file_callback_t file_func, struct output_file *out); +void free_data_blocks(); + +#endif diff --git a/ext4_utils/contents.c b/ext4_utils/contents.c new file mode 100644 index 00000000..0ecdfd43 --- /dev/null +++ b/ext4_utils/contents.c @@ -0,0 +1,241 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include +#include + +#include "ext4_utils.h" +#include "ext4.h" +#include "make_ext4fs.h" +#include "allocate.h" +#include "contents.h" +#include "extent.h" +#include "indirect.h" + +static u32 dentry_size(u32 entries, struct dentry *dentries) +{ + u32 len = 24; + unsigned int i; + unsigned int dentry_len; + + for (i = 0; i < entries; i++) { + dentry_len = 8 + ALIGN(strlen(dentries[i].filename), 4); + if (len % info.block_size + dentry_len > info.block_size) + len += info.block_size - (len % info.block_size); + len += dentry_len; + } + + return len; +} + +static struct ext4_dir_entry_2 *add_dentry(u8 *data, u32 *offset, + struct ext4_dir_entry_2 *prev, u32 inode, const char *name, + u8 file_type) +{ + u8 name_len = strlen(name); + u16 rec_len = 8 + ALIGN(name_len, 4); + struct ext4_dir_entry_2 *dentry; + + u32 start_block = *offset / info.block_size; + u32 end_block = (*offset + rec_len) / info.block_size; + if (start_block != end_block) { + /* Adding this dentry will cross a block boundary, so pad the previous + dentry to the block boundary */ + if (!prev) + critical_error("no prev"); + prev->rec_len += end_block * info.block_size - *offset; + *offset = end_block * info.block_size; + } + + dentry = (struct ext4_dir_entry_2 *)(data + *offset); + dentry->inode = inode; + dentry->rec_len = rec_len; + dentry->name_len = name_len; + dentry->file_type = file_type; + memcpy(dentry->name, name, name_len); + + *offset += rec_len; + return dentry; +} + +/* Creates a directory structure for an array of directory entries, dentries, + and stores the location of the structure in an inode. The new inode's + .. link is set to dir_inode_num. Stores the location of the inode number + of each directory entry into dentries[i].inode, to be filled in later + when the inode for the entry is allocated. Returns the inode number of the + new directory */ +u32 make_directory(u32 dir_inode_num, u32 entries, struct dentry *dentries, + u32 dirs) +{ + struct ext4_inode *inode; + u32 blocks; + u32 len; + u32 offset = 0; + u32 inode_num; + u8 *data; + unsigned int i; + struct ext4_dir_entry_2 *dentry; + + blocks = DIV_ROUND_UP(dentry_size(entries, dentries), info.block_size); + len = blocks * info.block_size; + + if (dir_inode_num) { + inode_num = allocate_inode(info); + } else { + dir_inode_num = EXT4_ROOT_INO; + inode_num = EXT4_ROOT_INO; + } + + if (inode_num == EXT4_ALLOCATE_FAILED) { + error("failed to allocate inode\n"); + return EXT4_ALLOCATE_FAILED; + } + + add_directory(inode_num); + + inode = get_inode(inode_num); + if (inode == NULL) { + error("failed to get inode %u", inode_num); + return EXT4_ALLOCATE_FAILED; + } + + data = inode_allocate_data_extents(inode, len, len); + if (data == NULL) { + error("failed to allocate %llu extents", len); + return EXT4_ALLOCATE_FAILED; + } + + inode->i_mode = S_IFDIR; + inode->i_links_count = dirs + 2; + inode->i_flags |= aux_info.default_i_flags; + + dentry = NULL; + + dentry = add_dentry(data, &offset, NULL, inode_num, ".", EXT4_FT_DIR); + if (!dentry) { + error("failed to add . directory"); + return EXT4_ALLOCATE_FAILED; + } + + dentry = add_dentry(data, &offset, dentry, dir_inode_num, "..", EXT4_FT_DIR); + if (!dentry) { + error("failed to add .. directory"); + return EXT4_ALLOCATE_FAILED; + } + + for (i = 0; i < entries; i++) { + dentry = add_dentry(data, &offset, dentry, 0, + dentries[i].filename, dentries[i].file_type); + if (offset > len || (offset == len && i != entries - 1)) + critical_error("internal error: dentry for %s ends at %d, past %d\n", + dentries[i].filename, offset, len); + dentries[i].inode = &dentry->inode; + if (!dentry) { + error("failed to add directory"); + return EXT4_ALLOCATE_FAILED; + } + } + + dentry = (struct ext4_dir_entry_2 *)(data + offset); + dentry->inode = 0; + dentry->rec_len = len - offset; + dentry->name_len = 0; + dentry->file_type = EXT4_FT_UNKNOWN; + + return inode_num; +} + +/* Creates a file on disk. Returns the inode number of the new file */ +u32 make_file(const char *filename, u64 len) +{ + struct ext4_inode *inode; + u32 inode_num; + + inode_num = allocate_inode(info); + if (inode_num == EXT4_ALLOCATE_FAILED) { + error("failed to allocate inode\n"); + return EXT4_ALLOCATE_FAILED; + } + + inode = get_inode(inode_num); + if (inode == NULL) { + error("failed to get inode %u", inode_num); + return EXT4_ALLOCATE_FAILED; + } + + if (len > 0) + inode_allocate_file_extents(inode, len, filename); + + inode->i_mode = S_IFREG; + inode->i_links_count = 1; + inode->i_flags |= aux_info.default_i_flags; + + return inode_num; +} + +/* Creates a file on disk. Returns the inode number of the new file */ +u32 make_link(const char *filename, const char *link) +{ + struct ext4_inode *inode; + u32 inode_num; + u32 len = strlen(link); + + inode_num = allocate_inode(info); + if (inode_num == EXT4_ALLOCATE_FAILED) { + error("failed to allocate inode\n"); + return EXT4_ALLOCATE_FAILED; + } + + inode = get_inode(inode_num); + if (inode == NULL) { + error("failed to get inode %u", inode_num); + return EXT4_ALLOCATE_FAILED; + } + + inode->i_mode = S_IFLNK; + inode->i_links_count = 1; + inode->i_flags |= aux_info.default_i_flags; + inode->i_size_lo = len; + + if (len + 1 <= sizeof(inode->i_block)) { + /* Fast symlink */ + memcpy((char*)inode->i_block, link, len); + } else { + u8 *data = inode_allocate_data_indirect(inode, info.block_size, info.block_size); + memcpy(data, link, len); + inode->i_blocks_lo = info.block_size / 512; + } + + return inode_num; +} + +int inode_set_permissions(u32 inode_num, u16 mode, u16 uid, u16 gid, u32 mtime) +{ + struct ext4_inode *inode = get_inode(inode_num); + + if (!inode) + return -1; + + inode->i_mode |= mode; + inode->i_uid = uid; + inode->i_gid = gid; + inode->i_mtime = mtime; + inode->i_atime = mtime; + inode->i_ctime = mtime; + + return 0; +} diff --git a/ext4_utils/contents.h b/ext4_utils/contents.h new file mode 100644 index 00000000..3aafb1ee --- /dev/null +++ b/ext4_utils/contents.h @@ -0,0 +1,39 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef _DIRECTORY_H_ +#define _DIRECTORY_H_ + +struct dentry { + char *path; + char *full_path; + const char *filename; + char *link; + unsigned long size; + u8 file_type; + u16 mode; + u16 uid; + u16 gid; + u32 *inode; + u32 mtime; +}; + +u32 make_directory(u32 dir_inode_num, u32 entries, struct dentry *dentries, + u32 dirs); +u32 make_file(const char *filename, u64 len); +u32 make_link(const char *filename, const char *link); +int inode_set_permissions(u32 inode_num, u16 mode, u16 uid, u16 gid, u32 mtime); +#endif diff --git a/ext4_utils/ext4.h b/ext4_utils/ext4.h new file mode 100644 index 00000000..68b5233a --- /dev/null +++ b/ext4_utils/ext4.h @@ -0,0 +1,577 @@ +/**************************************************************************** + **************************************************************************** + *** + *** This header was automatically generated from a Linux kernel header + *** of the same name, to make information necessary for userspace to + *** call into the kernel available to libc. It contains only constants, + *** structures, and macros generated from the original header, and thus, + *** contains no copyrightable information. + *** + **************************************************************************** + ****************************************************************************/ +#ifndef _EXT4_H +#define _EXT4_H + +#include + +#undef EXT4FS_DEBUG + +#ifdef EXT4FS_DEBUG +#define ext4_debug(f, a...) do { printk(KERN_DEBUG "EXT4-fs DEBUG (%s, %d): %s:", __FILE__, __LINE__, __func__); printk(KERN_DEBUG f, ## a); } while (0) +#else +#define ext4_debug(f, a...) do {} while (0) +#endif + +#define EXT4_ERROR_INODE(inode, fmt, a...) ext4_error_inode(__func__, (inode), (fmt), ## a); + +#define EXT4_ERROR_FILE(file, fmt, a...) ext4_error_file(__func__, (file), (fmt), ## a); + +typedef int ext4_grpblk_t; + +typedef unsigned long long ext4_fsblk_t; + +typedef __u32 ext4_lblk_t; + +typedef unsigned int ext4_group_t; + +#define EXT4_MB_HINT_MERGE 0x0001 + +#define EXT4_MB_HINT_RESERVED 0x0002 + +#define EXT4_MB_HINT_METADATA 0x0004 + +#define EXT4_MB_HINT_FIRST 0x0008 + +#define EXT4_MB_HINT_BEST 0x0010 + +#define EXT4_MB_HINT_DATA 0x0020 + +#define EXT4_MB_HINT_NOPREALLOC 0x0040 + +#define EXT4_MB_HINT_GROUP_ALLOC 0x0080 + +#define EXT4_MB_HINT_GOAL_ONLY 0x0100 + +#define EXT4_MB_HINT_TRY_GOAL 0x0200 + +#define EXT4_MB_DELALLOC_RESERVED 0x0400 + +#define EXT4_MB_STREAM_ALLOC 0x0800 + +struct ext4_allocation_request { + + struct inode *inode; + + unsigned int len; + + ext4_lblk_t logical; + + ext4_lblk_t lleft; + + ext4_lblk_t lright; + + ext4_fsblk_t goal; + + ext4_fsblk_t pleft; + + ext4_fsblk_t pright; + + unsigned int flags; +}; + +#define EXT4_BAD_INO 1 +#define EXT4_ROOT_INO 2 +#define EXT4_BOOT_LOADER_INO 5 +#define EXT4_UNDEL_DIR_INO 6 +#define EXT4_RESIZE_INO 7 +#define EXT4_JOURNAL_INO 8 + +#define EXT4_GOOD_OLD_FIRST_INO 11 + +#define EXT4_LINK_MAX 65000 + +#define EXT4_MIN_BLOCK_SIZE 1024 +#define EXT4_MAX_BLOCK_SIZE 65536 +#define EXT4_MIN_BLOCK_LOG_SIZE 10 +#define EXT4_BLOCK_SIZE(s) (EXT4_MIN_BLOCK_SIZE << (s)->s_log_block_size) +#define EXT4_ADDR_PER_BLOCK(s) (EXT4_BLOCK_SIZE(s) / sizeof(__u32)) +#define EXT4_BLOCK_SIZE_BITS(s) ((s)->s_log_block_size + 10) +#define EXT4_INODE_SIZE(s) (((s)->s_rev_level == EXT4_GOOD_OLD_REV) ? EXT4_GOOD_OLD_INODE_SIZE : (s)->s_inode_size) +#define EXT4_FIRST_INO(s) (((s)->s_rev_level == EXT4_GOOD_OLD_REV) ? EXT4_GOOD_OLD_FIRST_INO : (s)->s_first_ino) +#define EXT4_BLOCK_ALIGN(size, blkbits) ALIGN((size), (1 << (blkbits))) + +struct ext4_group_desc +{ + __le32 bg_block_bitmap_lo; + __le32 bg_inode_bitmap_lo; + __le32 bg_inode_table_lo; + __le16 bg_free_blocks_count_lo; + __le16 bg_free_inodes_count_lo; + __le16 bg_used_dirs_count_lo; + __le16 bg_flags; + __u32 bg_reserved[2]; + __le16 bg_itable_unused_lo; + __le16 bg_checksum; + __le32 bg_block_bitmap_hi; + __le32 bg_inode_bitmap_hi; + __le32 bg_inode_table_hi; + __le16 bg_free_blocks_count_hi; + __le16 bg_free_inodes_count_hi; + __le16 bg_used_dirs_count_hi; + __le16 bg_itable_unused_hi; + __u32 bg_reserved2[3]; +}; + +#define EXT4_BG_INODE_UNINIT 0x0001 +#define EXT4_BG_BLOCK_UNINIT 0x0002 +#define EXT4_BG_INODE_ZEROED 0x0004 + +#define EXT4_MIN_DESC_SIZE 32 +#define EXT4_MIN_DESC_SIZE_64BIT 64 +#define EXT4_MAX_DESC_SIZE EXT4_MIN_BLOCK_SIZE +#define EXT4_DESC_SIZE(s) (EXT4_SB(s)->s_desc_size) +#define EXT4_BLOCKS_PER_GROUP(s) ((s)->s_blocks_per_group) +#define EXT4_DESC_PER_BLOCK(s) (EXT4_BLOCK_SIZE(s) / EXT4_DESC_SIZE(s)) +#define EXT4_INODES_PER_GROUP(s) ((s)->s_inodes_per_group) + +#define EXT4_NDIR_BLOCKS 12 +#define EXT4_IND_BLOCK EXT4_NDIR_BLOCKS +#define EXT4_DIND_BLOCK (EXT4_IND_BLOCK + 1) +#define EXT4_TIND_BLOCK (EXT4_DIND_BLOCK + 1) +#define EXT4_N_BLOCKS (EXT4_TIND_BLOCK + 1) + +#define EXT4_SECRM_FL 0x00000001 +#define EXT4_UNRM_FL 0x00000002 +#define EXT4_COMPR_FL 0x00000004 +#define EXT4_SYNC_FL 0x00000008 +#define EXT4_IMMUTABLE_FL 0x00000010 +#define EXT4_APPEND_FL 0x00000020 +#define EXT4_NODUMP_FL 0x00000040 +#define EXT4_NOATIME_FL 0x00000080 + +#define EXT4_DIRTY_FL 0x00000100 +#define EXT4_COMPRBLK_FL 0x00000200 +#define EXT4_NOCOMPR_FL 0x00000400 +#define EXT4_ECOMPR_FL 0x00000800 + +#define EXT4_INDEX_FL 0x00001000 +#define EXT4_IMAGIC_FL 0x00002000 +#define EXT4_JOURNAL_DATA_FL 0x00004000 +#define EXT4_NOTAIL_FL 0x00008000 +#define EXT4_DIRSYNC_FL 0x00010000 +#define EXT4_TOPDIR_FL 0x00020000 +#define EXT4_HUGE_FILE_FL 0x00040000 +#define EXT4_EXTENTS_FL 0x00080000 +#define EXT4_EA_INODE_FL 0x00200000 +#define EXT4_EOFBLOCKS_FL 0x00400000 +#define EXT4_RESERVED_FL 0x80000000 + +#define EXT4_FL_USER_VISIBLE 0x004BDFFF +#define EXT4_FL_USER_MODIFIABLE 0x004B80FF + +#define EXT4_FL_INHERITED (EXT4_SECRM_FL | EXT4_UNRM_FL | EXT4_COMPR_FL | EXT4_SYNC_FL | EXT4_IMMUTABLE_FL | EXT4_APPEND_FL | EXT4_NODUMP_FL | EXT4_NOATIME_FL | EXT4_NOCOMPR_FL | EXT4_JOURNAL_DATA_FL | EXT4_NOTAIL_FL | EXT4_DIRSYNC_FL) + +#define EXT4_REG_FLMASK (~(EXT4_DIRSYNC_FL | EXT4_TOPDIR_FL)) + +#define EXT4_OTHER_FLMASK (EXT4_NODUMP_FL | EXT4_NOATIME_FL) + +struct ext4_new_group_data { + __u32 group; + __u64 block_bitmap; + __u64 inode_bitmap; + __u64 inode_table; + __u32 blocks_count; + __u16 reserved_blocks; + __u16 unused; + __u32 free_blocks_count; +}; + +#define EXT4_GET_BLOCKS_CREATE 0x0001 + +#define EXT4_GET_BLOCKS_UNINIT_EXT 0x0002 +#define EXT4_GET_BLOCKS_CREATE_UNINIT_EXT (EXT4_GET_BLOCKS_UNINIT_EXT| EXT4_GET_BLOCKS_CREATE) + +#define EXT4_GET_BLOCKS_DELALLOC_RESERVE 0x0004 + +#define EXT4_GET_BLOCKS_PRE_IO 0x0008 +#define EXT4_GET_BLOCKS_CONVERT 0x0010 +#define EXT4_GET_BLOCKS_IO_CREATE_EXT (EXT4_GET_BLOCKS_PRE_IO| EXT4_GET_BLOCKS_CREATE_UNINIT_EXT) + +#define EXT4_GET_BLOCKS_IO_CONVERT_EXT (EXT4_GET_BLOCKS_CONVERT| EXT4_GET_BLOCKS_CREATE_UNINIT_EXT) + +#define EXT4_FREE_BLOCKS_METADATA 0x0001 +#define EXT4_FREE_BLOCKS_FORGET 0x0002 +#define EXT4_FREE_BLOCKS_VALIDATED 0x0004 + +#define EXT4_IOC_GETFLAGS FS_IOC_GETFLAGS +#define EXT4_IOC_SETFLAGS FS_IOC_SETFLAGS +#define EXT4_IOC_GETVERSION _IOR('f', 3, long) +#define EXT4_IOC_SETVERSION _IOW('f', 4, long) +#define EXT4_IOC_GETVERSION_OLD FS_IOC_GETVERSION +#define EXT4_IOC_SETVERSION_OLD FS_IOC_SETVERSION +#define EXT4_IOC_GETRSVSZ _IOR('f', 5, long) +#define EXT4_IOC_SETRSVSZ _IOW('f', 6, long) +#define EXT4_IOC_GROUP_EXTEND _IOW('f', 7, unsigned long) +#define EXT4_IOC_GROUP_ADD _IOW('f', 8, struct ext4_new_group_input) +#define EXT4_IOC_MIGRATE _IO('f', 9) + +#define EXT4_IOC_ALLOC_DA_BLKS _IO('f', 12) +#define EXT4_IOC_MOVE_EXT _IOWR('f', 15, struct move_extent) + +#define EXT4_IOC32_GETFLAGS FS_IOC32_GETFLAGS +#define EXT4_IOC32_SETFLAGS FS_IOC32_SETFLAGS +#define EXT4_IOC32_GETVERSION _IOR('f', 3, int) +#define EXT4_IOC32_SETVERSION _IOW('f', 4, int) +#define EXT4_IOC32_GETRSVSZ _IOR('f', 5, int) +#define EXT4_IOC32_SETRSVSZ _IOW('f', 6, int) +#define EXT4_IOC32_GROUP_EXTEND _IOW('f', 7, unsigned int) +#define EXT4_IOC32_GETVERSION_OLD FS_IOC32_GETVERSION +#define EXT4_IOC32_SETVERSION_OLD FS_IOC32_SETVERSION + +#define EXT4_MAX_BLOCK_FILE_PHYS 0xFFFFFFFF + +struct ext4_inode { + __le16 i_mode; + __le16 i_uid; + __le32 i_size_lo; + __le32 i_atime; + __le32 i_ctime; + __le32 i_mtime; + __le32 i_dtime; + __le16 i_gid; + __le16 i_links_count; + __le32 i_blocks_lo; + __le32 i_flags; + union { + struct { + __le32 l_i_version; + } linux1; + struct { + __u32 h_i_translator; + } hurd1; + struct { + __u32 m_i_reserved1; + } masix1; + } osd1; + __le32 i_block[EXT4_N_BLOCKS]; + __le32 i_generation; + __le32 i_file_acl_lo; + __le32 i_size_high; + __le32 i_obso_faddr; + union { + struct { + __le16 l_i_blocks_high; + __le16 l_i_file_acl_high; + __le16 l_i_uid_high; + __le16 l_i_gid_high; + __u32 l_i_reserved2; + } linux2; + struct { + __le16 h_i_reserved1; + __u16 h_i_mode_high; + __u16 h_i_uid_high; + __u16 h_i_gid_high; + __u32 h_i_author; + } hurd2; + struct { + __le16 h_i_reserved1; + __le16 m_i_file_acl_high; + __u32 m_i_reserved2[2]; + } masix2; + } osd2; + __le16 i_extra_isize; + __le16 i_pad1; + __le32 i_ctime_extra; + __le32 i_mtime_extra; + __le32 i_atime_extra; + __le32 i_crtime; + __le32 i_crtime_extra; + __le32 i_version_hi; +}; + +struct move_extent { + __u32 reserved; + __u32 donor_fd; + __u64 orig_start; + __u64 donor_start; + __u64 len; + __u64 moved_len; +}; + +#define EXT4_EPOCH_BITS 2 +#define EXT4_EPOCH_MASK ((1 << EXT4_EPOCH_BITS) - 1) +#define EXT4_NSEC_MASK (~0UL << EXT4_EPOCH_BITS) + +#define EXT4_FITS_IN_INODE(ext4_inode, einode, field) ((offsetof(typeof(*ext4_inode), field) + sizeof((ext4_inode)->field)) <= (EXT4_GOOD_OLD_INODE_SIZE + (einode)->i_extra_isize)) +#define EXT4_INODE_SET_XTIME(xtime, inode, raw_inode) do { (raw_inode)->xtime = cpu_to_le32((inode)->xtime.tv_sec); if (EXT4_FITS_IN_INODE(raw_inode, EXT4_I(inode), xtime ## _extra)) (raw_inode)->xtime ## _extra = ext4_encode_extra_time(&(inode)->xtime); } while (0) +#define EXT4_EINODE_SET_XTIME(xtime, einode, raw_inode) do { if (EXT4_FITS_IN_INODE(raw_inode, einode, xtime)) (raw_inode)->xtime = cpu_to_le32((einode)->xtime.tv_sec); if (EXT4_FITS_IN_INODE(raw_inode, einode, xtime ## _extra)) (raw_inode)->xtime ## _extra = ext4_encode_extra_time(&(einode)->xtime); } while (0) +#define EXT4_INODE_GET_XTIME(xtime, inode, raw_inode) do { (inode)->xtime.tv_sec = (signed)le32_to_cpu((raw_inode)->xtime); if (EXT4_FITS_IN_INODE(raw_inode, EXT4_I(inode), xtime ## _extra)) ext4_decode_extra_time(&(inode)->xtime, raw_inode->xtime ## _extra); } while (0) +#define EXT4_EINODE_GET_XTIME(xtime, einode, raw_inode) do { if (EXT4_FITS_IN_INODE(raw_inode, einode, xtime)) (einode)->xtime.tv_sec = (signed)le32_to_cpu((raw_inode)->xtime); if (EXT4_FITS_IN_INODE(raw_inode, einode, xtime ## _extra)) ext4_decode_extra_time(&(einode)->xtime, raw_inode->xtime ## _extra); } while (0) +#define i_disk_version osd1.linux1.l_i_version + +#define i_reserved1 osd1.linux1.l_i_reserved1 +#define i_file_acl_high osd2.linux2.l_i_file_acl_high +#define i_blocks_high osd2.linux2.l_i_blocks_high +#define i_uid_low i_uid +#define i_gid_low i_gid +#define i_uid_high osd2.linux2.l_i_uid_high +#define i_gid_high osd2.linux2.l_i_gid_high +#define i_reserved2 osd2.linux2.l_i_reserved2 + +#define EXT4_VALID_FS 0x0001 +#define EXT4_ERROR_FS 0x0002 +#define EXT4_ORPHAN_FS 0x0004 + +#define EXT2_FLAGS_SIGNED_HASH 0x0001 +#define EXT2_FLAGS_UNSIGNED_HASH 0x0002 +#define EXT2_FLAGS_TEST_FILESYS 0x0004 + +#define EXT4_MOUNT_OLDALLOC 0x00002 +#define EXT4_MOUNT_GRPID 0x00004 +#define EXT4_MOUNT_DEBUG 0x00008 +#define EXT4_MOUNT_ERRORS_CONT 0x00010 +#define EXT4_MOUNT_ERRORS_RO 0x00020 +#define EXT4_MOUNT_ERRORS_PANIC 0x00040 +#define EXT4_MOUNT_MINIX_DF 0x00080 +#define EXT4_MOUNT_NOLOAD 0x00100 +#define EXT4_MOUNT_DATA_FLAGS 0x00C00 +#define EXT4_MOUNT_JOURNAL_DATA 0x00400 +#define EXT4_MOUNT_ORDERED_DATA 0x00800 +#define EXT4_MOUNT_WRITEBACK_DATA 0x00C00 +#define EXT4_MOUNT_UPDATE_JOURNAL 0x01000 +#define EXT4_MOUNT_NO_UID32 0x02000 +#define EXT4_MOUNT_XATTR_USER 0x04000 +#define EXT4_MOUNT_POSIX_ACL 0x08000 +#define EXT4_MOUNT_NO_AUTO_DA_ALLOC 0x10000 +#define EXT4_MOUNT_BARRIER 0x20000 +#define EXT4_MOUNT_NOBH 0x40000 +#define EXT4_MOUNT_QUOTA 0x80000 +#define EXT4_MOUNT_USRQUOTA 0x100000 +#define EXT4_MOUNT_GRPQUOTA 0x200000 +#define EXT4_MOUNT_DIOREAD_NOLOCK 0x400000 +#define EXT4_MOUNT_JOURNAL_CHECKSUM 0x800000 +#define EXT4_MOUNT_JOURNAL_ASYNC_COMMIT 0x1000000 +#define EXT4_MOUNT_I_VERSION 0x2000000 +#define EXT4_MOUNT_DELALLOC 0x8000000 +#define EXT4_MOUNT_DATA_ERR_ABORT 0x10000000 +#define EXT4_MOUNT_BLOCK_VALIDITY 0x20000000 +#define EXT4_MOUNT_DISCARD 0x40000000 + +#define clear_opt(o, opt) o &= ~EXT4_MOUNT_##opt +#define set_opt(o, opt) o |= EXT4_MOUNT_##opt +#define test_opt(sb, opt) (EXT4_SB(sb)->s_mount_opt & EXT4_MOUNT_##opt) + +#define ext4_set_bit ext2_set_bit +#define ext4_set_bit_atomic ext2_set_bit_atomic +#define ext4_clear_bit ext2_clear_bit +#define ext4_clear_bit_atomic ext2_clear_bit_atomic +#define ext4_test_bit ext2_test_bit +#define ext4_find_first_zero_bit ext2_find_first_zero_bit +#define ext4_find_next_zero_bit ext2_find_next_zero_bit +#define ext4_find_next_bit ext2_find_next_bit + +#define EXT4_DFL_MAX_MNT_COUNT 20 +#define EXT4_DFL_CHECKINTERVAL 0 + +#define EXT4_ERRORS_CONTINUE 1 +#define EXT4_ERRORS_RO 2 +#define EXT4_ERRORS_PANIC 3 +#define EXT4_ERRORS_DEFAULT EXT4_ERRORS_CONTINUE + +struct ext4_super_block { + __le32 s_inodes_count; + __le32 s_blocks_count_lo; + __le32 s_r_blocks_count_lo; + __le32 s_free_blocks_count_lo; + __le32 s_free_inodes_count; + __le32 s_first_data_block; + __le32 s_log_block_size; + __le32 s_obso_log_frag_size; + __le32 s_blocks_per_group; + __le32 s_obso_frags_per_group; + __le32 s_inodes_per_group; + __le32 s_mtime; + __le32 s_wtime; + __le16 s_mnt_count; + __le16 s_max_mnt_count; + __le16 s_magic; + __le16 s_state; + __le16 s_errors; + __le16 s_minor_rev_level; + __le32 s_lastcheck; + __le32 s_checkinterval; + __le32 s_creator_os; + __le32 s_rev_level; + __le16 s_def_resuid; + __le16 s_def_resgid; + + __le32 s_first_ino; + __le16 s_inode_size; + __le16 s_block_group_nr; + __le32 s_feature_compat; + __le32 s_feature_incompat; + __le32 s_feature_ro_compat; + __u8 s_uuid[16]; + char s_volume_name[16]; + char s_last_mounted[64]; + __le32 s_algorithm_usage_bitmap; + + __u8 s_prealloc_blocks; + __u8 s_prealloc_dir_blocks; + __le16 s_reserved_gdt_blocks; + + __u8 s_journal_uuid[16]; + __le32 s_journal_inum; + __le32 s_journal_dev; + __le32 s_last_orphan; + __le32 s_hash_seed[4]; + __u8 s_def_hash_version; + __u8 s_reserved_char_pad; + __le16 s_desc_size; + __le32 s_default_mount_opts; + __le32 s_first_meta_bg; + __le32 s_mkfs_time; + __le32 s_jnl_blocks[17]; + + __le32 s_blocks_count_hi; + __le32 s_r_blocks_count_hi; + __le32 s_free_blocks_count_hi; + __le16 s_min_extra_isize; + __le16 s_want_extra_isize; + __le32 s_flags; + __le16 s_raid_stride; + __le16 s_mmp_interval; + __le64 s_mmp_block; + __le32 s_raid_stripe_width; + __u8 s_log_groups_per_flex; + __u8 s_reserved_char_pad2; + __le16 s_reserved_pad; + __le64 s_kbytes_written; + __u32 s_reserved[160]; +}; + +#define EXT4_SB(sb) (sb) + +#define NEXT_ORPHAN(inode) EXT4_I(inode)->i_dtime + +#define EXT4_OS_LINUX 0 +#define EXT4_OS_HURD 1 +#define EXT4_OS_MASIX 2 +#define EXT4_OS_FREEBSD 3 +#define EXT4_OS_LITES 4 + +#define EXT4_GOOD_OLD_REV 0 +#define EXT4_DYNAMIC_REV 1 + +#define EXT4_CURRENT_REV EXT4_GOOD_OLD_REV +#define EXT4_MAX_SUPP_REV EXT4_DYNAMIC_REV + +#define EXT4_GOOD_OLD_INODE_SIZE 128 + +#define EXT4_HAS_COMPAT_FEATURE(sb,mask) ((EXT4_SB(sb)->s_es->s_feature_compat & cpu_to_le32(mask)) != 0) +#define EXT4_HAS_RO_COMPAT_FEATURE(sb,mask) ((EXT4_SB(sb)->s_es->s_feature_ro_compat & cpu_to_le32(mask)) != 0) +#define EXT4_HAS_INCOMPAT_FEATURE(sb,mask) ((EXT4_SB(sb)->s_es->s_feature_incompat & cpu_to_le32(mask)) != 0) +#define EXT4_SET_COMPAT_FEATURE(sb,mask) EXT4_SB(sb)->s_es->s_feature_compat |= cpu_to_le32(mask) +#define EXT4_SET_RO_COMPAT_FEATURE(sb,mask) EXT4_SB(sb)->s_es->s_feature_ro_compat |= cpu_to_le32(mask) +#define EXT4_SET_INCOMPAT_FEATURE(sb,mask) EXT4_SB(sb)->s_es->s_feature_incompat |= cpu_to_le32(mask) +#define EXT4_CLEAR_COMPAT_FEATURE(sb,mask) EXT4_SB(sb)->s_es->s_feature_compat &= ~cpu_to_le32(mask) +#define EXT4_CLEAR_RO_COMPAT_FEATURE(sb,mask) EXT4_SB(sb)->s_es->s_feature_ro_compat &= ~cpu_to_le32(mask) +#define EXT4_CLEAR_INCOMPAT_FEATURE(sb,mask) EXT4_SB(sb)->s_es->s_feature_incompat &= ~cpu_to_le32(mask) + +#define EXT4_FEATURE_COMPAT_DIR_PREALLOC 0x0001 +#define EXT4_FEATURE_COMPAT_IMAGIC_INODES 0x0002 +#define EXT4_FEATURE_COMPAT_HAS_JOURNAL 0x0004 +#define EXT4_FEATURE_COMPAT_EXT_ATTR 0x0008 +#define EXT4_FEATURE_COMPAT_RESIZE_INODE 0x0010 +#define EXT4_FEATURE_COMPAT_DIR_INDEX 0x0020 + +#define EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER 0x0001 +#define EXT4_FEATURE_RO_COMPAT_LARGE_FILE 0x0002 +#define EXT4_FEATURE_RO_COMPAT_BTREE_DIR 0x0004 +#define EXT4_FEATURE_RO_COMPAT_HUGE_FILE 0x0008 +#define EXT4_FEATURE_RO_COMPAT_GDT_CSUM 0x0010 +#define EXT4_FEATURE_RO_COMPAT_DIR_NLINK 0x0020 +#define EXT4_FEATURE_RO_COMPAT_EXTRA_ISIZE 0x0040 + +#define EXT4_FEATURE_INCOMPAT_COMPRESSION 0x0001 +#define EXT4_FEATURE_INCOMPAT_FILETYPE 0x0002 +#define EXT4_FEATURE_INCOMPAT_RECOVER 0x0004 +#define EXT4_FEATURE_INCOMPAT_JOURNAL_DEV 0x0008 +#define EXT4_FEATURE_INCOMPAT_META_BG 0x0010 +#define EXT4_FEATURE_INCOMPAT_EXTENTS 0x0040 +#define EXT4_FEATURE_INCOMPAT_64BIT 0x0080 +#define EXT4_FEATURE_INCOMPAT_MMP 0x0100 +#define EXT4_FEATURE_INCOMPAT_FLEX_BG 0x0200 +#define EXT4_FEATURE_INCOMPAT_EA_INODE 0x0400 +#define EXT4_FEATURE_INCOMPAT_DIRDATA 0x1000 + +#define EXT4_FEATURE_COMPAT_SUPP EXT2_FEATURE_COMPAT_EXT_ATTR +#define EXT4_FEATURE_INCOMPAT_SUPP (EXT4_FEATURE_INCOMPAT_FILETYPE| EXT4_FEATURE_INCOMPAT_RECOVER| EXT4_FEATURE_INCOMPAT_META_BG| EXT4_FEATURE_INCOMPAT_EXTENTS| EXT4_FEATURE_INCOMPAT_64BIT| EXT4_FEATURE_INCOMPAT_FLEX_BG) +#define EXT4_FEATURE_RO_COMPAT_SUPP (EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER| EXT4_FEATURE_RO_COMPAT_LARGE_FILE| EXT4_FEATURE_RO_COMPAT_GDT_CSUM| EXT4_FEATURE_RO_COMPAT_DIR_NLINK | EXT4_FEATURE_RO_COMPAT_EXTRA_ISIZE | EXT4_FEATURE_RO_COMPAT_BTREE_DIR | EXT4_FEATURE_RO_COMPAT_HUGE_FILE) + +#define EXT4_DEF_RESUID 0 +#define EXT4_DEF_RESGID 0 + +#define EXT4_DEF_INODE_READAHEAD_BLKS 32 + +#define EXT4_DEFM_DEBUG 0x0001 +#define EXT4_DEFM_BSDGROUPS 0x0002 +#define EXT4_DEFM_XATTR_USER 0x0004 +#define EXT4_DEFM_ACL 0x0008 +#define EXT4_DEFM_UID16 0x0010 +#define EXT4_DEFM_JMODE 0x0060 +#define EXT4_DEFM_JMODE_DATA 0x0020 +#define EXT4_DEFM_JMODE_ORDERED 0x0040 +#define EXT4_DEFM_JMODE_WBACK 0x0060 + +#define EXT4_DEF_MIN_BATCH_TIME 0 +#define EXT4_DEF_MAX_BATCH_TIME 15000 + +#define EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME 4 + +#define EXT4_NAME_LEN 255 + +struct ext4_dir_entry { + __le32 inode; + __le16 rec_len; + __le16 name_len; + char name[EXT4_NAME_LEN]; +}; + +struct ext4_dir_entry_2 { + __le32 inode; + __le16 rec_len; + __u8 name_len; + __u8 file_type; + char name[EXT4_NAME_LEN]; +}; + +#define EXT4_FT_UNKNOWN 0 +#define EXT4_FT_REG_FILE 1 +#define EXT4_FT_DIR 2 +#define EXT4_FT_CHRDEV 3 +#define EXT4_FT_BLKDEV 4 +#define EXT4_FT_FIFO 5 +#define EXT4_FT_SOCK 6 +#define EXT4_FT_SYMLINK 7 + +#define EXT4_FT_MAX 8 + +#define EXT4_DIR_PAD 4 +#define EXT4_DIR_ROUND (EXT4_DIR_PAD - 1) +#define EXT4_DIR_REC_LEN(name_len) (((name_len) + 8 + EXT4_DIR_ROUND) & ~EXT4_DIR_ROUND) +#define EXT4_MAX_REC_LEN ((1<<16)-1) + +#define is_dx(dir) (EXT4_HAS_COMPAT_FEATURE(dir->i_sb, EXT4_FEATURE_COMPAT_DIR_INDEX) && (EXT4_I(dir)->i_flags & EXT4_INDEX_FL)) +#define EXT4_DIR_LINK_MAX(dir) (!is_dx(dir) && (dir)->i_nlink >= EXT4_LINK_MAX) +#define EXT4_DIR_LINK_EMPTY(dir) ((dir)->i_nlink == 2 || (dir)->i_nlink == 1) + +#define DX_HASH_LEGACY 0 +#define DX_HASH_HALF_MD4 1 +#define DX_HASH_TEA 2 +#define DX_HASH_LEGACY_UNSIGNED 3 +#define DX_HASH_HALF_MD4_UNSIGNED 4 +#define DX_HASH_TEA_UNSIGNED 5 + +#endif + diff --git a/ext4_utils/ext4_extents.h b/ext4_utils/ext4_extents.h new file mode 100644 index 00000000..b1290f4b --- /dev/null +++ b/ext4_utils/ext4_extents.h @@ -0,0 +1,88 @@ +/**************************************************************************** + **************************************************************************** + *** + *** This header was automatically generated from a Linux kernel header + *** of the same name, to make information necessary for userspace to + *** call into the kernel available to libc. It contains only constants, + *** structures, and macros generated from the original header, and thus, + *** contains no copyrightable information. + *** + **************************************************************************** + ****************************************************************************/ +#ifndef _EXT4_EXTENTS +#define _EXT4_EXTENTS + +#include "ext4.h" + +#define AGGRESSIVE_TEST_ + +#define EXTENTS_STATS__ + +#define CHECK_BINSEARCH__ + +#define EXT_DEBUG__ +#ifdef EXT_DEBUG +#define ext_debug(a...) printk(a) +#else +#define ext_debug(a...) +#endif + +#define EXT_STATS_ + +struct ext4_extent { + __le32 ee_block; + __le16 ee_len; + __le16 ee_start_hi; + __le32 ee_start_lo; +}; + +struct ext4_extent_idx { + __le32 ei_block; + __le32 ei_leaf_lo; + __le16 ei_leaf_hi; + __u16 ei_unused; +}; + +struct ext4_extent_header { + __le16 eh_magic; + __le16 eh_entries; + __le16 eh_max; + __le16 eh_depth; + __le32 eh_generation; +}; + +#define EXT4_EXT_MAGIC 0xf30a + +struct ext4_ext_path { + ext4_fsblk_t p_block; + __u16 p_depth; + struct ext4_extent *p_ext; + struct ext4_extent_idx *p_idx; + struct ext4_extent_header *p_hdr; + struct buffer_head *p_bh; +}; + +#define EXT4_EXT_CACHE_NO 0 +#define EXT4_EXT_CACHE_GAP 1 +#define EXT4_EXT_CACHE_EXTENT 2 + +#define EXT_CONTINUE 0 +#define EXT_BREAK 1 +#define EXT_REPEAT 2 + +#define EXT_MAX_BLOCK 0xffffffff + +#define EXT_INIT_MAX_LEN (1UL << 15) +#define EXT_UNINIT_MAX_LEN (EXT_INIT_MAX_LEN - 1) + +#define EXT_FIRST_EXTENT(__hdr__) ((struct ext4_extent *) (((char *) (__hdr__)) + sizeof(struct ext4_extent_header))) +#define EXT_FIRST_INDEX(__hdr__) ((struct ext4_extent_idx *) (((char *) (__hdr__)) + sizeof(struct ext4_extent_header))) +#define EXT_HAS_FREE_INDEX(__path__) (le16_to_cpu((__path__)->p_hdr->eh_entries) < le16_to_cpu((__path__)->p_hdr->eh_max)) +#define EXT_LAST_EXTENT(__hdr__) (EXT_FIRST_EXTENT((__hdr__)) + le16_to_cpu((__hdr__)->eh_entries) - 1) +#define EXT_LAST_INDEX(__hdr__) (EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_entries) - 1) +#define EXT_MAX_EXTENT(__hdr__) (EXT_FIRST_EXTENT((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1) +#define EXT_MAX_INDEX(__hdr__) (EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1) + +#endif + + diff --git a/ext4_utils/ext4_jbd2.h b/ext4_utils/ext4_jbd2.h new file mode 100644 index 00000000..d937f5cd --- /dev/null +++ b/ext4_utils/ext4_jbd2.h @@ -0,0 +1,53 @@ +/**************************************************************************** + **************************************************************************** + *** + *** This header was automatically generated from a Linux kernel header + *** of the same name, to make information necessary for userspace to + *** call into the kernel available to libc. It contains only constants, + *** structures, and macros generated from the original header, and thus, + *** contains no copyrightable information. + *** + **************************************************************************** + ****************************************************************************/ +#ifndef _EXT4_JBD2_H +#define _EXT4_JBD2_H + +#include "ext4.h" + +#define EXT4_JOURNAL(inode) (EXT4_SB((inode)->i_sb)->s_journal) + +#define EXT4_SINGLEDATA_TRANS_BLOCKS(sb) (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS) ? 27U : 8U) + +#define EXT4_XATTR_TRANS_BLOCKS 6U + +#define EXT4_DATA_TRANS_BLOCKS(sb) (EXT4_SINGLEDATA_TRANS_BLOCKS(sb) + EXT4_XATTR_TRANS_BLOCKS - 2 + EXT4_MAXQUOTAS_TRANS_BLOCKS(sb)) + +#define EXT4_META_TRANS_BLOCKS(sb) (EXT4_XATTR_TRANS_BLOCKS + EXT4_MAXQUOTAS_TRANS_BLOCKS(sb)) + +#define EXT4_DELETE_TRANS_BLOCKS(sb) (2 * EXT4_DATA_TRANS_BLOCKS(sb) + 64) + +#define EXT4_MAX_TRANS_DATA 64U + +#define EXT4_RESERVE_TRANS_BLOCKS 12U + +#define EXT4_INDEX_EXTRA_TRANS_BLOCKS 8 + +#define EXT4_QUOTA_TRANS_BLOCKS(sb) 0 +#define EXT4_QUOTA_INIT_BLOCKS(sb) 0 +#define EXT4_QUOTA_DEL_BLOCKS(sb) 0 +#define EXT4_MAXQUOTAS_TRANS_BLOCKS(sb) (MAXQUOTAS*EXT4_QUOTA_TRANS_BLOCKS(sb)) +#define EXT4_MAXQUOTAS_INIT_BLOCKS(sb) (MAXQUOTAS*EXT4_QUOTA_INIT_BLOCKS(sb)) +#define EXT4_MAXQUOTAS_DEL_BLOCKS(sb) (MAXQUOTAS*EXT4_QUOTA_DEL_BLOCKS(sb)) + +#define ext4_journal_get_undo_access(handle, bh) __ext4_journal_get_undo_access(__func__, (handle), (bh)) +#define ext4_journal_get_write_access(handle, bh) __ext4_journal_get_write_access(__func__, (handle), (bh)) +#define ext4_forget(handle, is_metadata, inode, bh, block_nr) __ext4_forget(__func__, (handle), (is_metadata), (inode), (bh), (block_nr)) +#define ext4_journal_get_create_access(handle, bh) __ext4_journal_get_create_access(__func__, (handle), (bh)) +#define ext4_handle_dirty_metadata(handle, inode, bh) __ext4_handle_dirty_metadata(__func__, (handle), (inode), (bh)) + +#define EXT4_NOJOURNAL_MAX_REF_COUNT ((unsigned long) 4096) + +#define ext4_journal_stop(handle) __ext4_journal_stop(__func__, (handle)) + +#endif + diff --git a/ext4_utils/ext4_utils.c b/ext4_utils/ext4_utils.c new file mode 100644 index 00000000..f34985f5 --- /dev/null +++ b/ext4_utils/ext4_utils.c @@ -0,0 +1,404 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include +#include +#include +#include +#include + +#if defined(__linux__) +#include +#elif defined(__APPLE__) && defined(__MACH__) +#include +#endif + +#include "ext4_utils.h" +#include "output_file.h" +#include "backed_block.h" +#include "uuid.h" +#include "allocate.h" +#include "indirect.h" +#include "extent.h" + +#include "ext4.h" +#include "jbd2.h" + +int force = 0; +struct fs_info info; +struct fs_aux_info aux_info; + +/* returns 1 if a is a power of b */ +static int is_power_of(int a, int b) +{ + while (a > b) { + if (a % b) + return 0; + a /= b; + } + + return (a == b) ? 1 : 0; +} + +/* Returns 1 if the bg contains a backup superblock. On filesystems with + the sparse_super feature, only block groups 0, 1, and powers of 3, 5, + and 7 have backup superblocks. Otherwise, all block groups have backup + superblocks */ +int ext4_bg_has_super_block(int bg) +{ + /* Without sparse_super, every block group has a superblock */ + if (!(info.feat_ro_compat & EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER)) + return 1; + + if (bg == 0 || bg == 1) + return 1; + + if (is_power_of(bg, 3) || is_power_of(bg, 5) || is_power_of(bg, 7)) + return 1; + + return 0; +} + +/* Write the filesystem image to a file */ +void write_ext4_image(const char *filename, int gz, int sparse) +{ + int ret = 0; + struct output_file *out = open_output_file(filename, gz, sparse); + off_t off; + + if (!out) + return; + + /* The write_data* functions expect only block aligned calls. + * This is not an issue, except when we write out the super + * block on a system with a block size > 1K. So, we need to + * deal with that here. + */ + if (info.block_size > 1024) { + u8 buf[4096] = { 0 }; /* The larget supported ext4 block size */ + memcpy(buf + 1024, (u8*)aux_info.sb, 1024); + write_data_block(out, 0, buf, info.block_size); + + } else { + write_data_block(out, 1024, (u8*)aux_info.sb, 1024); + } + + write_data_block(out, (u64)(aux_info.first_data_block + 1) * info.block_size, + (u8*)aux_info.bg_desc, + aux_info.bg_desc_blocks * info.block_size); + + for_each_data_block(write_data_block, write_data_file, out); + + pad_output_file(out, info.len); + + close_output_file(out); +} + +/* Compute the rest of the parameters of the filesystem from the basic info */ +void ext4_create_fs_aux_info() +{ + aux_info.first_data_block = (info.block_size > 1024) ? 0 : 1; + aux_info.len_blocks = info.len / info.block_size; + aux_info.inode_table_blocks = DIV_ROUND_UP(info.inodes_per_group * info.inode_size, + info.block_size); + aux_info.groups = DIV_ROUND_UP(aux_info.len_blocks - aux_info.first_data_block, + info.blocks_per_group); + aux_info.blocks_per_ind = info.block_size / sizeof(u32); + aux_info.blocks_per_dind = aux_info.blocks_per_ind * aux_info.blocks_per_ind; + aux_info.blocks_per_tind = aux_info.blocks_per_dind * aux_info.blocks_per_dind; + + aux_info.bg_desc_blocks = + DIV_ROUND_UP(aux_info.groups * sizeof(struct ext2_group_desc), + info.block_size); + + aux_info.bg_desc_reserve_blocks = + DIV_ROUND_UP(aux_info.groups * 1024 * sizeof(struct ext2_group_desc), + info.block_size) - aux_info.bg_desc_blocks; + + if (aux_info.bg_desc_reserve_blocks > aux_info.blocks_per_ind) + aux_info.bg_desc_reserve_blocks = aux_info.blocks_per_ind; + + aux_info.default_i_flags = EXT4_NOATIME_FL; + + u32 last_group_size = aux_info.len_blocks % info.blocks_per_group; + u32 last_header_size = 2 + aux_info.inode_table_blocks; + if (ext4_bg_has_super_block(aux_info.groups - 1)) + last_header_size += 1 + aux_info.bg_desc_blocks + + aux_info.bg_desc_reserve_blocks; + if (last_group_size > 0 && last_group_size < last_header_size) { + aux_info.groups--; + aux_info.len_blocks -= last_group_size; + } + + aux_info.sb = calloc(info.block_size, 1); + if (!aux_info.sb) + critical_error_errno("calloc"); + + aux_info.bg_desc = calloc(info.block_size, aux_info.bg_desc_blocks); + if (!aux_info.bg_desc) + critical_error_errno("calloc"); +} + +void ext4_free_fs_aux_info() +{ + free(aux_info.sb); + free(aux_info.bg_desc); +} + +/* Fill in the superblock memory buffer based on the filesystem parameters */ +void ext4_fill_in_sb() +{ + unsigned int i; + struct ext4_super_block *sb = aux_info.sb; + + sb->s_inodes_count = info.inodes_per_group * aux_info.groups; + sb->s_blocks_count_lo = aux_info.len_blocks; + sb->s_r_blocks_count_lo = 0; + sb->s_free_blocks_count_lo = 0; + sb->s_free_inodes_count = 0; + sb->s_first_data_block = aux_info.first_data_block; + sb->s_log_block_size = log_2(info.block_size / 1024); + sb->s_obso_log_frag_size = log_2(info.block_size / 1024); + sb->s_blocks_per_group = info.blocks_per_group; + sb->s_obso_frags_per_group = info.blocks_per_group; + sb->s_inodes_per_group = info.inodes_per_group; + sb->s_mtime = 0; + sb->s_wtime = 0; + sb->s_mnt_count = 0; + sb->s_max_mnt_count = 0xFFFF; + sb->s_magic = EXT4_SUPER_MAGIC; + sb->s_state = EXT4_VALID_FS; + sb->s_errors = EXT4_ERRORS_RO; + sb->s_minor_rev_level = 0; + sb->s_lastcheck = 0; + sb->s_checkinterval = 0; + sb->s_creator_os = EXT4_OS_LINUX; + sb->s_rev_level = EXT4_DYNAMIC_REV; + sb->s_def_resuid = EXT4_DEF_RESUID; + sb->s_def_resgid = EXT4_DEF_RESGID; + + sb->s_first_ino = EXT4_GOOD_OLD_FIRST_INO; + sb->s_inode_size = info.inode_size; + sb->s_block_group_nr = 0; + sb->s_feature_compat = info.feat_compat; + sb->s_feature_incompat = info.feat_incompat; + sb->s_feature_ro_compat = info.feat_ro_compat; + generate_uuid("extandroid/make_ext4fs", info.label, sb->s_uuid); + memset(sb->s_volume_name, 0, sizeof(sb->s_volume_name)); + strncpy(sb->s_volume_name, info.label, sizeof(sb->s_volume_name)); + memset(sb->s_last_mounted, 0, sizeof(sb->s_last_mounted)); + sb->s_algorithm_usage_bitmap = 0; + + sb->s_reserved_gdt_blocks = aux_info.bg_desc_reserve_blocks; + sb->s_prealloc_blocks = 0; + sb->s_prealloc_dir_blocks = 0; + + //memcpy(sb->s_journal_uuid, sb->s_uuid, sizeof(sb->s_journal_uuid)); + if (info.feat_compat & EXT4_FEATURE_COMPAT_HAS_JOURNAL) + sb->s_journal_inum = EXT4_JOURNAL_INO; + sb->s_journal_dev = 0; + sb->s_last_orphan = 0; + sb->s_hash_seed[0] = 0; /* FIXME */ + sb->s_def_hash_version = DX_HASH_TEA; + sb->s_reserved_char_pad = EXT4_JNL_BACKUP_BLOCKS; + sb->s_desc_size = sizeof(struct ext2_group_desc); + sb->s_default_mount_opts = 0; /* FIXME */ + sb->s_first_meta_bg = 0; + sb->s_mkfs_time = 0; + //sb->s_jnl_blocks[17]; /* FIXME */ + + sb->s_blocks_count_hi = aux_info.len_blocks >> 32; + sb->s_r_blocks_count_hi = 0; + sb->s_free_blocks_count_hi = 0; + sb->s_min_extra_isize = sizeof(struct ext4_inode) - + EXT4_GOOD_OLD_INODE_SIZE; + sb->s_want_extra_isize = sizeof(struct ext4_inode) - + EXT4_GOOD_OLD_INODE_SIZE; + sb->s_flags = 0; + sb->s_raid_stride = 0; + sb->s_mmp_interval = 0; + sb->s_mmp_block = 0; + sb->s_raid_stripe_width = 0; + sb->s_log_groups_per_flex = 0; + sb->s_kbytes_written = 0; + + for (i = 0; i < aux_info.groups; i++) { + u64 group_start_block = aux_info.first_data_block + i * + info.blocks_per_group; + u32 header_size = 0; + if (ext4_bg_has_super_block(i)) { + if (i != 0) { + queue_data_block((u8 *)sb, info.block_size, group_start_block); + queue_data_block((u8 *)aux_info.bg_desc, + aux_info.bg_desc_blocks * info.block_size, + group_start_block + 1); + } + header_size = 1 + aux_info.bg_desc_blocks + aux_info.bg_desc_reserve_blocks; + } + + aux_info.bg_desc[i].bg_block_bitmap = group_start_block + header_size; + aux_info.bg_desc[i].bg_inode_bitmap = group_start_block + header_size + 1; + aux_info.bg_desc[i].bg_inode_table = group_start_block + header_size + 2; + + aux_info.bg_desc[i].bg_free_blocks_count = sb->s_blocks_per_group; + aux_info.bg_desc[i].bg_free_inodes_count = sb->s_inodes_per_group; + aux_info.bg_desc[i].bg_used_dirs_count = 0; + } +} + +void ext4_create_resize_inode() +{ + struct block_allocation *reserve_inode_alloc = create_allocation(); + u32 reserve_inode_len = 0; + unsigned int i; + + struct ext4_inode *inode = get_inode(EXT4_RESIZE_INO); + if (inode == NULL) { + error("failed to get resize inode"); + return; + } + + for (i = 0; i < aux_info.groups; i++) { + if (ext4_bg_has_super_block(i)) { + u64 group_start_block = aux_info.first_data_block + i * + info.blocks_per_group; + u32 reserved_block_start = group_start_block + 1 + + aux_info.bg_desc_blocks; + u32 reserved_block_len = aux_info.bg_desc_reserve_blocks; + append_region(reserve_inode_alloc, reserved_block_start, + reserved_block_len, i); + reserve_inode_len += reserved_block_len; + } + } + + inode_attach_resize(inode, reserve_inode_alloc); + + inode->i_mode = S_IFREG | S_IRUSR | S_IWUSR; + inode->i_links_count = 1; + + free_alloc(reserve_inode_alloc); +} + +/* Allocate the blocks to hold a journal inode and connect them to the + reserved journal inode */ +void ext4_create_journal_inode() +{ + struct ext4_inode *inode = get_inode(EXT4_JOURNAL_INO); + if (inode == NULL) { + error("failed to get journal inode"); + return; + } + + u8 *journal_data = inode_allocate_data_extents(inode, + info.journal_blocks * info.block_size, + info.block_size); + if (!journal_data) { + error("failed to allocate extents for journal data"); + return; + } + + inode->i_mode = S_IFREG | S_IRUSR | S_IWUSR; + inode->i_links_count = 1; + + journal_superblock_t *jsb = (journal_superblock_t *)journal_data; + jsb->s_header.h_magic = htonl(JBD2_MAGIC_NUMBER); + jsb->s_header.h_blocktype = htonl(JBD2_SUPERBLOCK_V2); + jsb->s_blocksize = htonl(info.block_size); + jsb->s_maxlen = htonl(info.journal_blocks); + jsb->s_nr_users = htonl(1); + jsb->s_first = htonl(1); + jsb->s_sequence = htonl(1); + + memcpy(aux_info.sb->s_jnl_blocks, &inode->i_block, sizeof(inode->i_block)); +} + +/* Update the number of free blocks and inodes in the filesystem and in each + block group */ +void ext4_update_free() +{ + unsigned int i; + + for (i = 0; i < aux_info.groups; i++) { + u32 bg_free_blocks = get_free_blocks(i); + u32 bg_free_inodes = get_free_inodes(i); + + aux_info.bg_desc[i].bg_free_blocks_count = bg_free_blocks; + aux_info.sb->s_free_blocks_count_lo += bg_free_blocks; + + aux_info.bg_desc[i].bg_free_inodes_count = bg_free_inodes; + aux_info.sb->s_free_inodes_count += bg_free_inodes; + + aux_info.bg_desc[i].bg_used_dirs_count += get_directories(i); + } +} + +static u64 get_block_device_size(const char *filename) +{ + int fd = open(filename, O_RDONLY); + u64 size = 0; + int ret; + + if (fd < 0) + return 0; + +#if defined(__linux__) + ret = ioctl(fd, BLKGETSIZE64, &size); +#elif defined(__APPLE__) && defined(__MACH__) + ret = ioctl(fd, DKIOCGETBLOCKCOUNT, &size); +#else + return 0; +#endif + + close(fd); + + if (ret) + return 0; + + return size; +} + +u64 get_file_size(const char *filename) +{ + struct stat buf; + int ret; + + ret = stat(filename, &buf); + if (ret) + return 0; + + if (S_ISREG(buf.st_mode)) + return buf.st_size; + else if (S_ISBLK(buf.st_mode)) + return get_block_device_size(filename); + else + return 0; +} + +u64 parse_num(const char *arg) +{ + char *endptr; + u64 num = strtoull(arg, &endptr, 10); + if (*endptr == 'k' || *endptr == 'K') + num *= 1024LL; + else if (*endptr == 'm' || *endptr == 'M') + num *= 1024LL * 1024LL; + else if (*endptr == 'g' || *endptr == 'G') + num *= 1024LL * 1024LL * 1024LL; + + return num; +} + diff --git a/ext4_utils/ext4_utils.h b/ext4_utils/ext4_utils.h new file mode 100644 index 00000000..697c8d90 --- /dev/null +++ b/ext4_utils/ext4_utils.h @@ -0,0 +1,129 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef _EXT4_UTILS_H_ +#define _EXT4_UTILS_H_ + +#include +#include +#include +#include +#include +#include + +extern int force; + +#define warn(fmt, args...) do { fprintf(stderr, "warning: %s: " fmt "\n", __func__, ## args); } while (0) +#define error(fmt, args...) do { fprintf(stderr, "error: %s: " fmt "\n", __func__, ## args); if (!force) exit(EXIT_FAILURE); } while (0) +#define error_errno(s) error(s ": %s", strerror(errno)) +#define critical_error(fmt, args...) do { fprintf(stderr, "critical error: %s: " fmt "\n", __func__, ## args); exit(EXIT_FAILURE); } while (0) +#define critical_error_errno(s) critical_error(s ": %s", strerror(errno)) + +#define EXT4_SUPER_MAGIC 0xEF53 +#define EXT4_JNL_BACKUP_BLOCKS 1 + +#define min(a, b) ((a) < (b) ? (a) : (b)) + +#define DIV_ROUND_UP(x, y) (((x) + (y) - 1)/(y)) +#define ALIGN(x, y) ((y) * DIV_ROUND_UP((x), (y))) + +#define __le64 u64 +#define __le32 u32 +#define __le16 u16 + +#define __be64 u64 +#define __be32 u32 +#define __be16 u16 + +#define __u64 u64 +#define __u32 u32 +#define __u16 u16 +#define __u8 u8 + +typedef unsigned long long u64; +typedef unsigned int u32; +typedef unsigned short int u16; +typedef unsigned char u8; + +struct block_group_info; + +struct ext2_group_desc { + __le32 bg_block_bitmap; + __le32 bg_inode_bitmap; + __le32 bg_inode_table; + __le16 bg_free_blocks_count; + __le16 bg_free_inodes_count; + __le16 bg_used_dirs_count; + __le16 bg_pad; + __le32 bg_reserved[3]; +}; + +struct fs_info { + u64 len; + u32 block_size; + u32 blocks_per_group; + u32 inodes_per_group; + u32 inode_size; + u32 inodes; + u32 journal_blocks; + u16 feat_ro_compat; + u16 feat_compat; + u16 feat_incompat; + const char *label; + u8 no_journal; +}; + +struct fs_aux_info { + struct ext4_super_block *sb; + struct ext2_group_desc *bg_desc; + struct block_group_info *bgs; + u32 first_data_block; + u64 len_blocks; + u32 inode_table_blocks; + u32 groups; + u32 bg_desc_blocks; + u32 bg_desc_reserve_blocks; + u32 default_i_flags; + u32 blocks_per_ind; + u32 blocks_per_dind; + u32 blocks_per_tind; +}; + +extern struct fs_info info; +extern struct fs_aux_info aux_info; + +static inline int log_2(int j) +{ + int i; + + for (i = 0; j > 0; i++) + j >>= 1; + + return i - 1; +} + +int ext4_bg_has_super_block(int bg); +void write_ext4_image(const char *filename, int gz, int sparse); +void ext4_create_fs_aux_info(void); +void ext4_free_fs_aux_info(void); +void ext4_fill_in_sb(void); +void ext4_create_resize_inode(void); +void ext4_create_journal_inode(void); +void ext4_update_free(void); +u64 get_file_size(const char *filename); +u64 parse_num(const char *arg); + +#endif diff --git a/ext4_utils/extent.c b/ext4_utils/extent.c new file mode 100644 index 00000000..1d2581d9 --- /dev/null +++ b/ext4_utils/extent.c @@ -0,0 +1,231 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include + +#include "ext4_utils.h" +#include "ext4.h" +#include "ext4_extents.h" +#include "backed_block.h" + +#include "extent.h" + +/* Creates data buffers for the first backing_len bytes of a block allocation + and queues them to be written */ +static u8 *extent_create_backing(struct block_allocation *alloc, + u64 backing_len) +{ + u8 *data = calloc(backing_len, 1); + if (!data) + critical_error_errno("calloc"); + + u8 *ptr = data; + for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) { + u32 region_block; + u32 region_len; + u32 len; + get_region(alloc, ®ion_block, ®ion_len); + + len = min(region_len * info.block_size, backing_len); + + queue_data_block(ptr, len, region_block); + ptr += len; + backing_len -= len; + } + + return data; +} + +/* Queues each chunk of a file to be written to contiguous data block + regions */ +static void extent_create_backing_file(struct block_allocation *alloc, + u64 backing_len, const char *filename) +{ + off_t offset = 0; + for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) { + u32 region_block; + u32 region_len; + u32 len; + get_region(alloc, ®ion_block, ®ion_len); + + len = min(region_len * info.block_size, backing_len); + + queue_data_file(filename, offset, len, region_block); + offset += len; + backing_len -= len; + } +} + +static struct block_allocation *do_inode_allocate_extents( + struct ext4_inode *inode, u64 len) +{ + u32 block_len = DIV_ROUND_UP(len, info.block_size); + struct block_allocation *alloc = allocate_blocks(block_len + 1); + 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; + } + + int allocation_len = block_allocation_num_regions(alloc); + if (allocation_len <= 3) { + reduce_allocation(alloc, 1); + } else { + reserve_oob_blocks(alloc, 1); + extent_block = get_oob_block(alloc, 0); + } + + if (!extent_block) { + struct ext4_extent_header *hdr = + (struct ext4_extent_header *)&inode->i_block[0]; + hdr->eh_magic = EXT4_EXT_MAGIC; + hdr->eh_entries = allocation_len; + hdr->eh_max = 3; + hdr->eh_generation = 0; + hdr->eh_depth = 0; + + extent = (struct ext4_extent *)&inode->i_block[3]; + } else { + struct ext4_extent_header *hdr = + (struct ext4_extent_header *)&inode->i_block[0]; + hdr->eh_magic = EXT4_EXT_MAGIC; + hdr->eh_entries = 1; + hdr->eh_max = 3; + hdr->eh_generation = 0; + hdr->eh_depth = 1; + + struct ext4_extent_idx *idx = + (struct ext4_extent_idx *)&inode->i_block[3]; + idx->ei_block = 0; + idx->ei_leaf_lo = extent_block; + idx->ei_leaf_hi = 0; + idx->ei_unused = 0; + + u8 *data = calloc(info.block_size, 1); + if (!data) + critical_error_errno("calloc"); + + queue_data_block(data, info.block_size, extent_block); + + if (((int)(info.block_size - sizeof(struct ext4_extent_header) / + sizeof(struct ext4_extent))) < allocation_len) { + error("File size %llu is too big to fit in a single extent block\n", + len); + return NULL; + } + + hdr = (struct ext4_extent_header *)data; + hdr->eh_magic = EXT4_EXT_MAGIC; + hdr->eh_entries = allocation_len; + hdr->eh_max = (info.block_size - sizeof(struct ext4_extent_header)) / + sizeof(struct ext4_extent); + hdr->eh_generation = 0; + hdr->eh_depth = 0; + + extent = (struct ext4_extent *)(data + + sizeof(struct ext4_extent_header)); + } + + for (; !last_region(alloc); extent++, get_next_region(alloc)) { + u32 region_block; + u32 region_len; + + get_region(alloc, ®ion_block, ®ion_len); + extent->ee_block = file_block; + extent->ee_len = region_len; + extent->ee_start_hi = 0; + extent->ee_start_lo = region_block; + file_block += region_len; + } + + if (extent_block) + block_len += 1; + + blocks = (u64)block_len * info.block_size / 512; + + inode->i_flags |= EXT4_EXTENTS_FL; + inode->i_size_lo = len; + inode->i_size_high = len >> 32; + inode->i_blocks_lo = blocks; + inode->osd2.linux2.l_i_blocks_high = blocks >> 32; + + rewind_alloc(alloc); + + return alloc; +} + +/* Allocates enough blocks to hold len bytes, with backing_len bytes in a data + buffer, and connects them to an inode. Returns a pointer to the data + buffer. */ +u8 *inode_allocate_data_extents(struct ext4_inode *inode, u64 len, + u64 backing_len) +{ + struct block_allocation *alloc; + u8 *data = NULL; + + alloc = do_inode_allocate_extents(inode, len); + if (alloc == NULL) { + error("failed to allocate extents for %llu bytes", len); + return NULL; + } + + if (backing_len) { + data = extent_create_backing(alloc, backing_len); + if (!data) + error("failed to create backing for %llu bytes", backing_len); + } + + free_alloc(alloc); + + return data; +} + +/* Allocates enough blocks to hold len bytes, queues them to be written + from a file, and connects them to an inode. */ +void inode_allocate_file_extents(struct ext4_inode *inode, u64 len, + const char *filename) +{ + struct block_allocation *alloc; + + alloc = do_inode_allocate_extents(inode, len); + if (alloc == NULL) { + error("failed to allocate extents for %llu bytes", len); + return; + } + + extent_create_backing_file(alloc, len, filename); + + free_alloc(alloc); +} + +/* Allocates enough blocks to hold len bytes and connects them to an inode */ +void inode_allocate_extents(struct ext4_inode *inode, u64 len) +{ + struct block_allocation *alloc; + + alloc = do_inode_allocate_extents(inode, len); + if (alloc == NULL) { + error("failed to allocate extents for %llu bytes", len); + return; + } + + free_alloc(alloc); +} diff --git a/ext4_utils/extent.h b/ext4_utils/extent.h new file mode 100644 index 00000000..a1ddeb15 --- /dev/null +++ b/ext4_utils/extent.h @@ -0,0 +1,30 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef _EXTENT_H_ +#define _EXTENT_H_ + +#include "allocate.h" +#include "ext4_utils.h" + +void inode_allocate_extents(struct ext4_inode *inode, u64 len); +void inode_allocate_file_extents(struct ext4_inode *inode, u64 len, + const char *filename); +u8 *inode_allocate_data_extents(struct ext4_inode *inode, u64 len, + u64 backing_len); +void free_extent_blocks(); + +#endif diff --git a/ext4_utils/indirect.c b/ext4_utils/indirect.c new file mode 100644 index 00000000..2d9d7104 --- /dev/null +++ b/ext4_utils/indirect.c @@ -0,0 +1,504 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include + +#include "ext4_utils.h" +#include "ext4.h" +#include "ext4_extents.h" +#include "backed_block.h" +#include "indirect.h" +#include "allocate.h" + +/* Creates data buffers for the first backing_len bytes of a block allocation + and queues them to be written */ +static u8 *create_backing(struct block_allocation *alloc, + unsigned long backing_len) +{ + if (DIV_ROUND_UP(backing_len, info.block_size) > EXT4_NDIR_BLOCKS) + critical_error("indirect backing larger than %d blocks", EXT4_NDIR_BLOCKS); + + u8 *data = calloc(backing_len, 1); + if (!data) + critical_error_errno("calloc"); + + u8 *ptr = data; + for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) { + u32 region_block; + u32 region_len; + u32 len; + get_region(alloc, ®ion_block, ®ion_len); + + len = min(region_len * info.block_size, backing_len); + + queue_data_block(ptr, len, region_block); + ptr += len; + backing_len -= len; + } + + return data; +} + +static void reserve_indirect_block(struct block_allocation *alloc, int len) +{ + if (reserve_oob_blocks(alloc, 1)) { + error("failed to reserve oob block"); + return; + } + + if (advance_blocks(alloc, len)) { + error("failed to advance %d blocks", len); + return; + } +} + +static void reserve_dindirect_block(struct block_allocation *alloc, int len) +{ + if (reserve_oob_blocks(alloc, 1)) { + error("failed to reserve oob block"); + return; + } + + while (len > 0) { + int ind_block_len = min((int)aux_info.blocks_per_ind, len); + + reserve_indirect_block(alloc, ind_block_len); + + len -= ind_block_len; + } + +} + +static void reserve_tindirect_block(struct block_allocation *alloc, int len) +{ + if (reserve_oob_blocks(alloc, 1)) { + error("failed to reserve oob block"); + return; + } + + while (len > 0) { + int dind_block_len = min((int)aux_info.blocks_per_dind, len); + + reserve_dindirect_block(alloc, dind_block_len); + + len -= dind_block_len; + } +} + +static void fill_indirect_block(u32 *ind_block, int len, struct block_allocation *alloc) +{ + int i; + for (i = 0; i < len; i++) { + ind_block[i] = get_block(alloc, i); + } +} + +static void fill_dindirect_block(u32 *dind_block, int len, struct block_allocation *alloc) +{ + int i; + u32 ind_block; + + for (i = 0; len > 0; i++) { + ind_block = get_oob_block(alloc, 0); + if (advance_oob_blocks(alloc, 1)) { + error("failed to reserve oob block"); + return; + } + + dind_block[i] = ind_block; + + u32 *ind_block_data = calloc(info.block_size, 1); + queue_data_block((u8*)ind_block_data, info.block_size, ind_block); + int ind_block_len = min((int)aux_info.blocks_per_ind, len); + + fill_indirect_block(ind_block_data, ind_block_len, alloc); + + if (advance_blocks(alloc, ind_block_len)) { + error("failed to advance %d blocks", ind_block_len); + return; + } + + len -= ind_block_len; + } +} + +static void fill_tindirect_block(u32 *tind_block, int len, struct block_allocation *alloc) +{ + int i; + u32 dind_block; + + for (i = 0; len > 0; i++) { + dind_block = get_oob_block(alloc, 0); + if (advance_oob_blocks(alloc, 1)) { + error("failed to reserve oob block"); + return; + } + + tind_block[i] = dind_block; + + u32 *dind_block_data = calloc(info.block_size, 1); + queue_data_block((u8*)dind_block_data, info.block_size, dind_block); + int dind_block_len = min((int)aux_info.blocks_per_dind, len); + + fill_dindirect_block(dind_block_data, dind_block_len, alloc); + + len -= dind_block_len; + } +} + +/* Given an allocation, attach as many blocks as possible to direct inode + blocks, and return the rest */ +static int inode_attach_direct_blocks(struct ext4_inode *inode, + struct block_allocation *alloc, u32 *block_len) +{ + int len = min(*block_len, EXT4_NDIR_BLOCKS); + int i; + + for (i = 0; i < len; i++) { + inode->i_block[i] = get_block(alloc, i); + } + + if (advance_blocks(alloc, len)) { + error("failed to advance %d blocks", len); + return -1; + } + + *block_len -= len; + return 0; +} + +/* Given an allocation, attach as many blocks as possible to indirect blocks, + and return the rest + Assumes that the blocks necessary to hold the indirect blocks were included + as part of the allocation */ +static int inode_attach_indirect_blocks(struct ext4_inode *inode, + struct block_allocation *alloc, u32 *block_len) +{ + int len = min(*block_len, aux_info.blocks_per_ind); + + int ind_block = get_oob_block(alloc, 0); + inode->i_block[EXT4_IND_BLOCK] = ind_block; + + if (advance_oob_blocks(alloc, 1)) { + error("failed to advance oob block"); + return -1; + } + + u32 *ind_block_data = calloc(info.block_size, 1); + queue_data_block((u8*)ind_block_data, info.block_size, ind_block); + + fill_indirect_block(ind_block_data, len, alloc); + + if (advance_blocks(alloc, len)) { + error("failed to advance %d blocks", len); + return -1; + } + + *block_len -= len; + return 0; +} + +/* Given an allocation, attach as many blocks as possible to doubly indirect + blocks, and return the rest. + Assumes that the blocks necessary to hold the indirect and doubly indirect + blocks were included as part of the allocation */ +static int inode_attach_dindirect_blocks(struct ext4_inode *inode, + struct block_allocation *alloc, u32 *block_len) +{ + int len = min(*block_len, aux_info.blocks_per_dind); + + int dind_block = get_oob_block(alloc, 0); + inode->i_block[EXT4_DIND_BLOCK] = dind_block; + + if (advance_oob_blocks(alloc, 1)) { + error("failed to advance oob block"); + return -1; + } + + u32 *dind_block_data = calloc(info.block_size, 1); + queue_data_block((u8*)dind_block_data, info.block_size, dind_block); + + fill_dindirect_block(dind_block_data, len, alloc); + + if (advance_blocks(alloc, len)) { + error("failed to advance %d blocks", len); + return -1; + } + + *block_len -= len; + return 0; +} + +/* Given an allocation, attach as many blocks as possible to triply indirect + blocks, and return the rest. + Assumes that the blocks necessary to hold the indirect, doubly indirect and + triply indirect blocks were included as part of the allocation */ +static int inode_attach_tindirect_blocks(struct ext4_inode *inode, + struct block_allocation *alloc, u32 *block_len) +{ + int len = min(*block_len, aux_info.blocks_per_tind); + + int tind_block = get_oob_block(alloc, 0); + inode->i_block[EXT4_TIND_BLOCK] = tind_block; + + if (advance_oob_blocks(alloc, 1)) { + error("failed to advance oob block"); + return -1; + } + + u32 *tind_block_data = calloc(info.block_size, 1); + queue_data_block((u8*)tind_block_data, info.block_size, tind_block); + + fill_tindirect_block(tind_block_data, len, alloc); + + if (advance_blocks(alloc, len)) { + error("failed to advance %d blocks", len); + return -1; + } + + *block_len -= len; + return 0; +} + +static void reserve_all_indirect_blocks(struct block_allocation *alloc, u32 len) +{ + if (len <= EXT4_NDIR_BLOCKS) + return; + + len -= EXT4_NDIR_BLOCKS; + advance_blocks(alloc, EXT4_NDIR_BLOCKS); + + u32 ind_block_len = min(aux_info.blocks_per_ind, len); + reserve_indirect_block(alloc, ind_block_len); + + len -= ind_block_len; + if (len == 0) + return; + + u32 dind_block_len = min(aux_info.blocks_per_dind, len); + reserve_dindirect_block(alloc, dind_block_len); + + len -= dind_block_len; + if (len == 0) + return; + + u32 tind_block_len = min(aux_info.blocks_per_tind, len); + reserve_tindirect_block(alloc, tind_block_len); + + len -= tind_block_len; + if (len == 0) + return; + + error("%d blocks remaining", len); +} + +static u32 indirect_blocks_needed(u32 len) +{ + u32 ind = 0; + + if (len <= EXT4_NDIR_BLOCKS) + return ind; + + len -= EXT4_NDIR_BLOCKS; + + /* We will need an indirect block for the rest of the blocks */ + ind += DIV_ROUND_UP(len, aux_info.blocks_per_ind); + + if (len <= aux_info.blocks_per_ind) + return ind; + + len -= aux_info.blocks_per_ind; + + ind += DIV_ROUND_UP(len, aux_info.blocks_per_dind); + + if (len <= aux_info.blocks_per_dind) + return ind; + + len -= aux_info.blocks_per_dind; + + ind += DIV_ROUND_UP(len, aux_info.blocks_per_tind); + + if (len <= aux_info.blocks_per_tind) + return ind; + + critical_error("request too large"); + return 0; +} + +static int do_inode_attach_indirect(struct ext4_inode *inode, + struct block_allocation *alloc, u32 block_len) +{ + u32 count = block_len; + + if (inode_attach_direct_blocks(inode, alloc, &count)) { + error("failed to attach direct blocks to inode"); + return -1; + } + + if (count > 0) { + if (inode_attach_indirect_blocks(inode, alloc, &count)) { + error("failed to attach indirect blocks to inode"); + return -1; + } + } + + if (count > 0) { + if (inode_attach_dindirect_blocks(inode, alloc, &count)) { + error("failed to attach dindirect blocks to inode"); + return -1; + } + } + + if (count > 0) { + if (inode_attach_tindirect_blocks(inode, alloc, &count)) { + error("failed to attach tindirect blocks to inode"); + return -1; + } + } + + if (count) { + error("blocks left after triply-indirect allocation"); + return -1; + } + + rewind_alloc(alloc); + + return 0; +} + +static struct block_allocation *do_inode_allocate_indirect( + struct ext4_inode *inode, u32 block_len) +{ + u32 indirect_len = indirect_blocks_needed(block_len); + + struct block_allocation *alloc = allocate_blocks(block_len + indirect_len); + + if (alloc == NULL) { + error("Failed to allocate %d blocks", block_len + indirect_len); + return NULL; + } + + return alloc; +} + +/* Allocates enough blocks to hold len bytes and connects them to an inode */ +void inode_allocate_indirect(struct ext4_inode *inode, unsigned long len) +{ + struct block_allocation *alloc; + u32 block_len = DIV_ROUND_UP(len, info.block_size); + u32 indirect_len = indirect_blocks_needed(block_len); + + alloc = do_inode_allocate_indirect(inode, block_len); + if (alloc == NULL) { + error("failed to allocate extents for %lu bytes", len); + return; + } + + reserve_all_indirect_blocks(alloc, block_len); + rewind_alloc(alloc); + + if (do_inode_attach_indirect(inode, alloc, block_len)) + error("failed to attach blocks to indirect inode"); + + inode->i_flags = 0; + inode->i_blocks_lo = (block_len + indirect_len) * info.block_size / 512; + inode->i_size_lo = len; + + free_alloc(alloc); +} + +void inode_attach_resize(struct ext4_inode *inode, + struct block_allocation *alloc) +{ + u32 block_len = block_allocation_len(alloc); + u32 superblocks = block_len / aux_info.bg_desc_reserve_blocks; + u32 i, j; + u64 blocks; + u64 size; + + if (block_len % aux_info.bg_desc_reserve_blocks) + critical_error("reserved blocks not a multiple of %d", + aux_info.bg_desc_reserve_blocks); + + append_oob_allocation(alloc, 1); + u32 dind_block = get_oob_block(alloc, 0); + + u32 *dind_block_data = calloc(info.block_size, 1); + if (!dind_block_data) + critical_error_errno("calloc"); + queue_data_block((u8 *)dind_block_data, info.block_size, dind_block); + + u32 *ind_block_data = calloc(info.block_size, aux_info.bg_desc_reserve_blocks); + if (!ind_block_data) + critical_error_errno("calloc"); + queue_data_block((u8 *)ind_block_data, + info.block_size * aux_info.bg_desc_reserve_blocks, + get_block(alloc, 0)); + + for (i = 0; i < aux_info.bg_desc_reserve_blocks; i++) { + int r = (i - aux_info.bg_desc_blocks) % aux_info.bg_desc_reserve_blocks; + if (r < 0) + r += aux_info.bg_desc_reserve_blocks; + + dind_block_data[i] = get_block(alloc, r); + + for (j = 1; j < superblocks; j++) { + u32 b = j * aux_info.bg_desc_reserve_blocks + r; + ind_block_data[r * aux_info.blocks_per_ind + j - 1] = get_block(alloc, b); + } + } + + u32 last_block = EXT4_NDIR_BLOCKS + aux_info.blocks_per_ind + + aux_info.blocks_per_ind * (aux_info.bg_desc_reserve_blocks - 1) + + superblocks - 2; + + blocks = ((u64)block_len + 1) * info.block_size / 512; + size = (u64)last_block * info.block_size; + + inode->i_block[EXT4_DIND_BLOCK] = dind_block; + inode->i_flags = 0; + inode->i_blocks_lo = blocks; + inode->osd2.linux2.l_i_blocks_high = blocks >> 32; + inode->i_size_lo = size; + inode->i_size_high = size >> 32; +} + +/* Allocates enough blocks to hold len bytes, with backing_len bytes in a data + buffer, and connects them to an inode. Returns a pointer to the data + buffer. */ +u8 *inode_allocate_data_indirect(struct ext4_inode *inode, unsigned long len, + unsigned long backing_len) +{ + struct block_allocation *alloc; + u8 *data = NULL; + + alloc = do_inode_allocate_indirect(inode, len); + if (alloc == NULL) { + error("failed to allocate extents for %lu bytes", len); + return NULL; + } + + if (backing_len) { + data = create_backing(alloc, backing_len); + if (!data) + error("failed to create backing for %lu bytes", backing_len); + } + + free_alloc(alloc); + + return data; +} diff --git a/ext4_utils/indirect.h b/ext4_utils/indirect.h new file mode 100644 index 00000000..cee89790 --- /dev/null +++ b/ext4_utils/indirect.h @@ -0,0 +1,29 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef _INDIRECT_H_ +#define _INDIRECT_H_ + +#include "allocate.h" + +void inode_allocate_indirect(struct ext4_inode *inode, unsigned long len); +u8 *inode_allocate_data_indirect(struct ext4_inode *inode, unsigned long len, + unsigned long backing_len); +void inode_attach_resize(struct ext4_inode *inode, + struct block_allocation *alloc); +void free_indirect_blocks(); + +#endif diff --git a/ext4_utils/jbd2.h b/ext4_utils/jbd2.h new file mode 100644 index 00000000..1c816417 --- /dev/null +++ b/ext4_utils/jbd2.h @@ -0,0 +1,141 @@ +/**************************************************************************** + **************************************************************************** + *** + *** This header was automatically generated from a Linux kernel header + *** of the same name, to make information necessary for userspace to + *** call into the kernel available to libc. It contains only constants, + *** structures, and macros generated from the original header, and thus, + *** contains no copyrightable information. + *** + **************************************************************************** + ****************************************************************************/ +#ifndef _LINUX_JBD2_H +#define _LINUX_JBD2_H + +#define JBD2_DEBUG +#define jfs_debug jbd_debug + +#define journal_oom_retry 1 + +#undef JBD2_PARANOID_IOFAIL + +#define JBD2_DEFAULT_MAX_COMMIT_AGE 5 + +#define jbd_debug(f, a...) + +#define JBD2_MIN_JOURNAL_BLOCKS 1024 + +#define JBD2_MAGIC_NUMBER 0xc03b3998U + +#define JBD2_DESCRIPTOR_BLOCK 1 +#define JBD2_COMMIT_BLOCK 2 +#define JBD2_SUPERBLOCK_V1 3 +#define JBD2_SUPERBLOCK_V2 4 +#define JBD2_REVOKE_BLOCK 5 + +typedef struct journal_header_s +{ + __be32 h_magic; + __be32 h_blocktype; + __be32 h_sequence; +} journal_header_t; + +#define JBD2_CRC32_CHKSUM 1 +#define JBD2_MD5_CHKSUM 2 +#define JBD2_SHA1_CHKSUM 3 + +#define JBD2_CRC32_CHKSUM_SIZE 4 + +#define JBD2_CHECKSUM_BYTES (32 / sizeof(u32)) + +struct commit_header { + __be32 h_magic; + __be32 h_blocktype; + __be32 h_sequence; + unsigned char h_chksum_type; + unsigned char h_chksum_size; + unsigned char h_padding[2]; + __be32 h_chksum[JBD2_CHECKSUM_BYTES]; + __be64 h_commit_sec; + __be32 h_commit_nsec; +}; + +typedef struct journal_block_tag_s +{ + __be32 t_blocknr; + __be32 t_flags; + __be32 t_blocknr_high; +} journal_block_tag_t; + +#define JBD2_TAG_SIZE32 (offsetof(journal_block_tag_t, t_blocknr_high)) +#define JBD2_TAG_SIZE64 (sizeof(journal_block_tag_t)) + +typedef struct jbd2_journal_revoke_header_s +{ + journal_header_t r_header; + __be32 r_count; +} jbd2_journal_revoke_header_t; + +#define JBD2_FLAG_ESCAPE 1 +#define JBD2_FLAG_SAME_UUID 2 +#define JBD2_FLAG_DELETED 4 +#define JBD2_FLAG_LAST_TAG 8 + +typedef struct journal_superblock_s +{ + + journal_header_t s_header; + + __be32 s_blocksize; + __be32 s_maxlen; + __be32 s_first; + + __be32 s_sequence; + __be32 s_start; + + __be32 s_errno; + + __be32 s_feature_compat; + __be32 s_feature_incompat; + __be32 s_feature_ro_compat; + + __u8 s_uuid[16]; + + __be32 s_nr_users; + + __be32 s_dynsuper; + + __be32 s_max_transaction; + __be32 s_max_trans_data; + + __u32 s_padding[44]; + + __u8 s_users[16*48]; + +} journal_superblock_t; + +#define JBD2_HAS_COMPAT_FEATURE(j,mask) ((j)->j_format_version >= 2 && ((j)->j_superblock->s_feature_compat & cpu_to_be32((mask)))) +#define JBD2_HAS_RO_COMPAT_FEATURE(j,mask) ((j)->j_format_version >= 2 && ((j)->j_superblock->s_feature_ro_compat & cpu_to_be32((mask)))) +#define JBD2_HAS_INCOMPAT_FEATURE(j,mask) ((j)->j_format_version >= 2 && ((j)->j_superblock->s_feature_incompat & cpu_to_be32((mask)))) + +#define JBD2_FEATURE_COMPAT_CHECKSUM 0x00000001 + +#define JBD2_FEATURE_INCOMPAT_REVOKE 0x00000001 +#define JBD2_FEATURE_INCOMPAT_64BIT 0x00000002 +#define JBD2_FEATURE_INCOMPAT_ASYNC_COMMIT 0x00000004 + +#define JBD2_KNOWN_COMPAT_FEATURES JBD2_FEATURE_COMPAT_CHECKSUM +#define JBD2_KNOWN_ROCOMPAT_FEATURES 0 +#define JBD2_KNOWN_INCOMPAT_FEATURES (JBD2_FEATURE_INCOMPAT_REVOKE | JBD2_FEATURE_INCOMPAT_64BIT | JBD2_FEATURE_INCOMPAT_ASYNC_COMMIT) + +#define BJ_None 0 +#define BJ_Metadata 1 +#define BJ_Forget 2 +#define BJ_IO 3 +#define BJ_Shadow 4 +#define BJ_LogCtl 5 +#define BJ_Reserved 6 +#define BJ_Types 7 + +#endif + diff --git a/ext4_utils/make_ext4fs.c b/ext4_utils/make_ext4fs.c new file mode 100644 index 00000000..87588ab6 --- /dev/null +++ b/ext4_utils/make_ext4fs.c @@ -0,0 +1,327 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#define _GNU_SOURCE + +#include +#include +#include +#include +#include +#include +#include +#include + +#include "make_ext4fs.h" +#include "output_file.h" +#include "ext4_utils.h" +#include "allocate.h" +#include "contents.h" +#include "uuid.h" + +#ifdef ANDROID +#include +#endif + +/* TODO: Not implemented: + Allocating blocks in the same block group as the file inode + Hash or binary tree directories + Special files: sockets, devices, fifos + */ + +static int filter_dot(const struct dirent *d) +{ + return (strcmp(d->d_name, "..") && strcmp(d->d_name, ".")); +} + +static u32 build_default_directory_structure() +{ + u32 inode; + u32 root_inode; + struct dentry dentries = { + .filename = "lost+found", + .file_type = EXT4_FT_DIR, + .mode = S_IRWXU, + .uid = 0, + .gid = 0, + .mtime = 0, + }; + root_inode = make_directory(0, 1, &dentries, 1); + inode = make_directory(root_inode, 0, NULL, 0); + *dentries.inode = inode; + inode_set_permissions(inode, dentries.mode, + dentries.uid, dentries.gid, dentries.mtime); + + return root_inode; +} + +/* Read a local directory and create the same tree in the generated filesystem. + Calls itself recursively with each directory in the given directory */ +static u32 build_directory_structure(const char *full_path, const char *dir_path, + u32 dir_inode, int android) +{ + int entries = 0; + struct dentry *dentries; + struct dirent **namelist; + struct stat stat; + int ret; + int i; + u32 inode; + u32 entry_inode; + u32 dirs = 0; + + entries = scandir(full_path, &namelist, filter_dot, (void*)alphasort); + if (entries < 0) { + error_errno("scandir"); + return EXT4_ALLOCATE_FAILED; + } + + dentries = calloc(entries, sizeof(struct dentry)); + if (dentries == NULL) + critical_error_errno("malloc"); + + for (i = 0; i < entries; i++) { + dentries[i].filename = strdup(namelist[i]->d_name); + if (dentries[i].filename == NULL) + critical_error_errno("strdup"); + + asprintf(&dentries[i].path, "%s/%s", dir_path, namelist[i]->d_name); + asprintf(&dentries[i].full_path, "%s/%s", full_path, namelist[i]->d_name); + + free(namelist[i]); + + ret = lstat(dentries[i].full_path, &stat); + if (ret < 0) { + error_errno("lstat"); + i--; + entries--; + continue; + } + + dentries[i].size = stat.st_size; + dentries[i].mode = stat.st_mode & (S_ISUID|S_ISGID|S_ISVTX|S_IRWXU|S_IRWXG|S_IRWXO); + dentries[i].mtime = stat.st_mtime; + if (android) { +#ifdef ANDROID + unsigned int mode = 0; + unsigned int uid = 0; + unsigned int gid = 0; + int dir = S_ISDIR(stat.st_mode); + fs_config(dentries[i].path, dir, &uid, &gid, &mode); + dentries[i].mode = mode; + dentries[i].uid = uid; + dentries[i].gid = gid; +#else + error("can't set android permissions - built without android support"); +#endif + } + + if (S_ISREG(stat.st_mode)) { + dentries[i].file_type = EXT4_FT_REG_FILE; + } else if (S_ISDIR(stat.st_mode)) { + dentries[i].file_type = EXT4_FT_DIR; + dirs++; + } else if (S_ISCHR(stat.st_mode)) { + dentries[i].file_type = EXT4_FT_CHRDEV; + } else if (S_ISBLK(stat.st_mode)) { + dentries[i].file_type = EXT4_FT_BLKDEV; + } else if (S_ISFIFO(stat.st_mode)) { + dentries[i].file_type = EXT4_FT_FIFO; + } else if (S_ISSOCK(stat.st_mode)) { + dentries[i].file_type = EXT4_FT_SOCK; + } else if (S_ISLNK(stat.st_mode)) { + dentries[i].file_type = EXT4_FT_SYMLINK; + dentries[i].link = calloc(info.block_size, 1); + readlink(dentries[i].full_path, dentries[i].link, info.block_size - 1); + } else { + error("unknown file type on %s", dentries[i].path); + i--; + entries--; + } + } + free(namelist); + + inode = make_directory(dir_inode, entries, dentries, dirs); + + for (i = 0; i < entries; i++) { + if (dentries[i].file_type == EXT4_FT_REG_FILE) { + entry_inode = make_file(dentries[i].full_path, dentries[i].size); + } else if (dentries[i].file_type == EXT4_FT_DIR) { + entry_inode = build_directory_structure(dentries[i].full_path, + dentries[i].path, inode, android); + } else if (dentries[i].file_type == EXT4_FT_SYMLINK) { + entry_inode = make_link(dentries[i].full_path, dentries[i].link); + } else { + error("unknown file type on %s", dentries[i].path); + entry_inode = 0; + } + *dentries[i].inode = entry_inode; + + ret = inode_set_permissions(entry_inode, dentries[i].mode, + dentries[i].uid, dentries[i].gid, + dentries[i].mtime); + if (ret) + error("failed to set permissions on %s\n", dentries[i].path); + + free(dentries[i].path); + free(dentries[i].full_path); + free(dentries[i].link); + free((void *)dentries[i].filename); + } + + free(dentries); + return inode; +} + +static u32 compute_block_size() +{ + return 4096; +} + +static u32 compute_journal_blocks() +{ + u32 journal_blocks = DIV_ROUND_UP(info.len, info.block_size) / 64; + if (journal_blocks < 1024) + journal_blocks = 1024; + if (journal_blocks > 32768) + journal_blocks = 32768; + return journal_blocks; +} + +static u32 compute_blocks_per_group() +{ + return info.block_size * 8; +} + +static u32 compute_inodes() +{ + return DIV_ROUND_UP(info.len, info.block_size) / 4; +} + +static u32 compute_inodes_per_group() +{ + u32 blocks = DIV_ROUND_UP(info.len, info.block_size); + u32 block_groups = DIV_ROUND_UP(blocks, info.blocks_per_group); + return DIV_ROUND_UP(info.inodes, block_groups); +} + +void reset_ext4fs_info() { + // Reset all the global data structures used by make_ext4fs so it + // can be called again. + memset(&info, 0, sizeof(info)); + memset(&aux_info, 0, sizeof(aux_info)); + free_data_blocks(); +} + +int make_ext4fs(const char *filename, const char *directory, + char *mountpoint, int android, int gzip, int sparse) +{ + u32 root_inode_num; + u16 root_mode; + + if (info.len == 0) + info.len = get_file_size(filename); + + if (info.len <= 0) { + fprintf(stderr, "Need size of filesystem\n"); + return EXIT_FAILURE; + } + + if (info.block_size <= 0) + info.block_size = compute_block_size(); + + if (info.journal_blocks == 0) + info.journal_blocks = compute_journal_blocks(); + + if (info.no_journal == 0) + info.feat_compat = EXT4_FEATURE_COMPAT_HAS_JOURNAL; + else + info.journal_blocks = 0; + + if (info.blocks_per_group <= 0) + info.blocks_per_group = compute_blocks_per_group(); + + if (info.inodes <= 0) + info.inodes = compute_inodes(); + + if (info.inode_size <= 0) + info.inode_size = 256; + + if (info.label == NULL) + info.label = ""; + + info.inodes_per_group = compute_inodes_per_group(); + + info.feat_compat |= + EXT4_FEATURE_COMPAT_RESIZE_INODE; + + info.feat_ro_compat |= + EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER | + EXT4_FEATURE_RO_COMPAT_LARGE_FILE; + + info.feat_incompat |= + EXT4_FEATURE_INCOMPAT_EXTENTS | + EXT4_FEATURE_INCOMPAT_FILETYPE; + + + printf("Creating filesystem with parameters:\n"); + printf(" Size: %llu\n", info.len); + printf(" Block size: %d\n", info.block_size); + printf(" Blocks per group: %d\n", info.blocks_per_group); + printf(" Inodes per group: %d\n", info.inodes_per_group); + printf(" Inode size: %d\n", info.inode_size); + printf(" Journal blocks: %d\n", info.journal_blocks); + printf(" Label: %s\n", info.label); + + ext4_create_fs_aux_info(); + + printf(" Blocks: %llu\n", aux_info.len_blocks); + printf(" Block groups: %d\n", aux_info.groups); + printf(" Reserved block group size: %d\n", aux_info.bg_desc_reserve_blocks); + + block_allocator_init(); + + ext4_fill_in_sb(); + + if (reserve_inodes(0, 10) == EXT4_ALLOCATE_FAILED) + error("failed to reserve first 10 inodes"); + + if (info.feat_compat & EXT4_FEATURE_COMPAT_HAS_JOURNAL) + ext4_create_journal_inode(); + + if (info.feat_compat & EXT4_FEATURE_COMPAT_RESIZE_INODE) + ext4_create_resize_inode(); + + if (directory) + root_inode_num = build_directory_structure(directory, mountpoint, 0, android); + else + root_inode_num = build_default_directory_structure(); + + root_mode = S_IRWXU | S_IRGRP | S_IXGRP | S_IROTH | S_IXOTH; + inode_set_permissions(root_inode_num, root_mode, 0, 0, 0); + + ext4_update_free(); + + 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, + aux_info.sb->s_blocks_count_lo - aux_info.sb->s_free_blocks_count_lo, + aux_info.sb->s_blocks_count_lo); + + write_ext4_image(filename, gzip, sparse); + + return 0; +} diff --git a/ext4_utils/make_ext4fs.h b/ext4_utils/make_ext4fs.h new file mode 100644 index 00000000..8c6b2592 --- /dev/null +++ b/ext4_utils/make_ext4fs.h @@ -0,0 +1,27 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef _MAKE_EXT4FS_H_ +#define _MAKE_EXT4FS_H_ + +#include "ext4_utils.h" +#include "ext4.h" + +void reset_ext4fs_info(); +int make_ext4fs(const char *filename, const char *directory, + char *mountpoint, int android, int gzip, int sparse); + +#endif diff --git a/ext4_utils/make_ext4fs_main.c b/ext4_utils/make_ext4fs_main.c new file mode 100644 index 00000000..66d7aac6 --- /dev/null +++ b/ext4_utils/make_ext4fs_main.c @@ -0,0 +1,119 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * 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 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include + +#if defined(__linux__) +#include +#elif defined(__APPLE__) && defined(__MACH__) +#include +#endif + +#include "make_ext4fs.h" + +extern struct fs_info info; + + +static void usage(char *path) +{ + fprintf(stderr, "%s [ -l ] [ -j ] [ -b ]\n", basename(path)); + fprintf(stderr, " [ -g ] [ -i ] [ -I ]\n"); + fprintf(stderr, " [ -L