Initial commit of ext4_utils
Change-Id: I911d5b7fd7170ec81d544850717d8e69976e272b
diff --git a/ext4_utils/Android.mk b/ext4_utils/Android.mk
new file mode 100644
index 0000000..c8bda90
--- /dev/null
+++ b/ext4_utils/Android.mk
@@ -0,0 +1,28 @@
+# Copyright 2010 The Android Open Source Project
+
+LOCAL_PATH:= $(call my-dir)
+include $(CLEAR_VARS)
+
+make_ext4fs_src_files := \
+ make_ext4fs.c \
+ ext_utils.c \
+ allocate.c \
+ backed_block.c \
+ contents.c \
+ extent.c \
+ indirect.c \
+ uuid.c \
+ sha1.c \
+
+LOCAL_SRC_FILES := $(make_ext4fs_src_files)
+LOCAL_MODULE := make_ext4fs
+LOCAL_MODULE_TAGS := optional
+
+include $(BUILD_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := $(make_ext4fs_src_files)
+LOCAL_MODULE := make_ext4fs
+
+include $(BUILD_HOST_EXECUTABLE)
diff --git a/ext4_utils/MODULE_LICENSE_APACHE2 b/ext4_utils/MODULE_LICENSE_APACHE2
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/ext4_utils/MODULE_LICENSE_APACHE2
diff --git a/ext4_utils/NOTICE b/ext4_utils/NOTICE
new file mode 100644
index 0000000..5d14293
--- /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 0000000..7930573
--- /dev/null
+++ b/ext4_utils/allocate.c
@@ -0,0 +1,742 @@
+/*
+ * 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 <stdio.h>
+#include <stdlib.h>
+
+#include "ext4_utils.h"
+#include "allocate.h"
+#include "backed_block.h"
+#include "ext_utils.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;
+ 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 0000000..23c690e
--- /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 0000000..e438498
--- /dev/null
+++ b/ext4_utils/backed_block.c
@@ -0,0 +1,133 @@
+/*
+ * 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 <stdlib.h>
+
+#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, void *priv)
+{
+ 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(priv, db->block, db->filename, db->offset, db->len);
+ else
+ data_func(priv, db->block, db->data, db->len);
+ }
+}
+
+/* Frees the memory used by the linked list of data blocks */
+void free_data_blocks()
+{
+ struct data_block *db = data_blocks;
+ while (db) {
+ struct data_block *next = db->next;
+ free((void*)db->filename);
+ free((void*)db->data);
+ free(db);
+ db = next;
+ }
+}
diff --git a/ext4_utils/backed_block.h b/ext4_utils/backed_block.h
new file mode 100644
index 0000000..fc76229
--- /dev/null
+++ b/ext4_utils/backed_block.h
@@ -0,0 +1,36 @@
+/*
+ * 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 <sys/types.h>
+#include <unistd.h>
+#include "ext4_utils.h"
+
+typedef void (*data_block_callback_t)(void *priv, u32 block, u8 *data,
+ int len);
+typedef void (*data_block_file_callback_t)(void *priv, u32 block,
+ 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, void *priv);
+void free_data_blocks();
+
+#endif
diff --git a/ext4_utils/contents.c b/ext4_utils/contents.c
new file mode 100644
index 0000000..eefb6c6
--- /dev/null
+++ b/ext4_utils/contents.c
@@ -0,0 +1,233 @@
+/*
+ * 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 <sys/stat.h>
+#include <string.h>
+#include <stdio.h>
+
+#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;
+
+ for (i = 0; i < entries; i++) {
+ unsigned int dentry_len = 8 + 4
+ * DIV_ROUND_UP(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;
+}
+
+#define PAD_TO(x, y) (x + (y - (x % y)))
+
+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 + PAD_TO(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 = DIV_ROUND_UP(dentry_size(entries, dentries), info.block_size);
+ u64 len = (u64)blocks * info.block_size;
+ u32 offset = 0;
+ u32 inode_num;
+ u8 *data;
+ unsigned int i;
+ struct ext4_dir_entry_2 *dentry;
+
+ 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);
+ 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;
+ }
+
+ 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)
+{
+ struct ext4_inode *inode = get_inode(inode_num);
+
+ if (!inode)
+ return -1;
+
+ inode->i_mode |= mode;
+ inode->i_uid = uid;
+ inode->i_gid = gid;
+
+ return 0;
+}
diff --git a/ext4_utils/contents.h b/ext4_utils/contents.h
new file mode 100644
index 0000000..b1ae868
--- /dev/null
+++ b/ext4_utils/contents.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 _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 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);
+#endif
diff --git a/ext4_utils/ext4.h b/ext4_utils/ext4.h
new file mode 100644
index 0000000..68b5233
--- /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 <sys/types.h>
+
+#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 0000000..b1290f4
--- /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 0000000..d937f5c
--- /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.h b/ext4_utils/ext4_utils.h
new file mode 100644
index 0000000..40c0676
--- /dev/null
+++ b/ext4_utils/ext4_utils.h
@@ -0,0 +1,116 @@
+/*
+ * 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 <sys/types.h>
+#include <errno.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+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 __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;
+};
+
+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;
+}
+
+#endif
diff --git a/ext4_utils/ext_utils.c b/ext4_utils/ext_utils.c
new file mode 100644
index 0000000..c2764e1
--- /dev/null
+++ b/ext4_utils/ext_utils.c
@@ -0,0 +1,49 @@
+/*
+ * 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 "ext4_utils.h"
+#include "ext4.h"
+
+/* 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;
+}
diff --git a/ext4_utils/ext_utils.h b/ext4_utils/ext_utils.h
new file mode 100644
index 0000000..eacd3a1
--- /dev/null
+++ b/ext4_utils/ext_utils.h
@@ -0,0 +1,24 @@
+/*
+ * 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 _EXT_UTILS_H_
+#define _EXT_UTILS_H_
+
+#include "ext4.h"
+
+int ext4_bg_has_super_block(int bg);
+
+#endif
diff --git a/ext4_utils/extent.c b/ext4_utils/extent.c
new file mode 100644
index 0000000..b1e7749
--- /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 <stdlib.h>
+#include <stdio.h>
+
+#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 0000000..5456a86
--- /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 0000000..cb87602
--- /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 <stdlib.h>
+#include <stdio.h>
+
+#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 0000000..e281b92
--- /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 0000000..1c81641
--- /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 0000000..266f54e
--- /dev/null
+++ b/ext4_utils/make_ext4fs.c
@@ -0,0 +1,810 @@
+/*
+ * 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 <sys/types.h>
+#include <sys/ioctl.h>
+#include <sys/stat.h>
+#include <sys/mman.h>
+#include <limits.h>
+#include <arpa/inet.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <stdlib.h>
+#include <strings.h>
+#include <string.h>
+#include <stdio.h>
+#include <dirent.h>
+#include <libgen.h>
+
+#if defined(linux)
+#include <linux/fs.h>
+#elif defined(__APPLE__) && defined(__MACH__)
+#include <sys/disk.h>
+#endif
+
+#include "make_ext4fs.h"
+#include "ext4_utils.h"
+#include "allocate.h"
+#include "ext_utils.h"
+#include "backed_block.h"
+#include "contents.h"
+#include "extent.h"
+#include "indirect.h"
+#include "uuid.h"
+
+#include "jbd2.h"
+#include "ext4.h"
+
+#ifdef ANDROID
+#include <private/android_filesystem_config.h>
+#endif
+
+/* TODO: Not implemented:
+ Allocating blocks in the same block group as the file inode
+ Hash or binary tree directories
+ Non-extent inodes
+ Special files: symbolic links, sockets, devices, fifos
+ */
+
+int force = 0;
+
+struct fs_info info;
+struct fs_aux_info aux_info;
+
+/* Write a contiguous region of data blocks from a memory buffer */
+static void write_data_block(void *priv, u32 block, u8 *data, int len)
+{
+ int fd = *(int*)priv;
+ off_t off;
+ int ret;
+
+ if (block * info.block_size + len >= info.len) {
+ error("attempted to write block %llu past end of filesystem",
+ block * info.block_size + len - info.len);
+ return;
+ }
+
+ off = (off_t)block * info.block_size;
+ off = lseek(fd, off, SEEK_SET);
+ if (off < 0) {
+ error_errno("lseek");
+ return;
+ }
+
+ ret = write(fd, data, len);
+ if (ret < 0)
+ error_errno("write");
+ else if (ret < len)
+ error("incomplete write");
+}
+
+/* Write a contiguous region of data blocks from a file */
+static void write_data_file(void *priv, u32 block, const char *file,
+ off_t offset, int len)
+{
+ int fd = *(int*)priv;
+ off_t off;
+ int ret;
+
+ if (block * info.block_size + len >= info.len) {
+ error("attempted to write block %llu past end of filesystem",
+ block * info.block_size + len - info.len);
+ return;
+ }
+
+ int file_fd = open(file, O_RDONLY);
+ if (file_fd < 0) {
+ error_errno("open");
+ return;
+ }
+
+ u8 *data = mmap(NULL, len, PROT_READ, MAP_SHARED, file_fd, offset);
+ if (data == MAP_FAILED) {
+ error_errno("mmap");
+ close(fd);
+ return;
+ }
+
+ off = (off_t)block * info.block_size;
+ off = lseek(fd, off, SEEK_SET);
+ if (off < 0) {
+ error_errno("lseek");
+ return;
+ }
+
+ ret = write(fd, data, len);
+ if (ret < 0)
+ error_errno("write");
+ else if (ret < len)
+ error("incomplete write");
+
+ munmap(data, len);
+
+ close(file_fd);
+}
+
+/* Write the filesystem image to a file */
+static void write_ext4_image(const char *filename)
+{
+ int ret = 0;
+ int fd = open(filename, O_WRONLY | O_CREAT | O_TRUNC, 0644);
+ off_t off;
+
+ if (fd < 0) {
+ error_errno("open");
+ return;
+ }
+
+ off = lseek(fd, 1024, SEEK_SET);
+ if (off < 0) {
+ error_errno("lseek");
+ return;
+ }
+
+ ret = write(fd, aux_info.sb, 1024);
+ if (ret < 0)
+ error_errno("write");
+ else if (ret < 1024)
+ error("incomplete write");
+
+ off = (aux_info.first_data_block + 1) * info.block_size;
+ off = lseek(fd, off, SEEK_SET);
+ if (off < 0) {
+ error_errno("lseek");
+ return;
+ }
+
+ ret = write(fd, aux_info.bg_desc,
+ aux_info.bg_desc_blocks * info.block_size);
+ if (ret < 0)
+ error_errno("write");
+ else if (ret < (int)(aux_info.bg_desc_blocks * info.block_size))
+ error("incomplete write");
+
+ for_each_data_block(write_data_block, write_data_file, &fd);
+
+ off = info.len - 1;
+ off = lseek(fd, off, SEEK_SET);
+ if (off < 0) {
+ error_errno("lseek");
+ return;
+ }
+
+ ret = write(fd, "\0", 1);
+ if (ret < 0)
+ error_errno("write");
+ else if (ret < 1)
+ error("incomplete write");
+
+ close(fd);
+}
+
+/* Compute the rest of the parameters of the filesystem from the basic info */
+static 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 */
+static 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;
+ }
+}
+
+static 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 */
+static 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 */
+static 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 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
+ };
+ root_inode = make_directory(0, 1, &dentries, 1);
+ inode = make_directory(root_inode, 0, NULL, 0);
+ *dentries.inode = inode;
+
+ 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, 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);
+ 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);
+ 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_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);
+}
+
+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;
+}
+
+static 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;
+}
+
+static void usage(char *path)
+{
+ fprintf(stderr, "%s [ -l <len> ] [ -j <journal size> ] [ -b <block_size> ]\n", basename(path));
+ fprintf(stderr, " [ -g <blocks per group> ] [ -i <inodes> ] [ -I <inode size> ]\n");
+ fprintf(stderr, " [ -L <label> ] [ -f ] [ -a <android mountpoint> ]\n");
+ fprintf(stderr, " <filename> [<directory>]\n");
+}
+
+static 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;
+}
+
+int main(int argc, char **argv)
+{
+ int opt;
+ const char *filename = NULL;
+ const char *directory = NULL;
+ char *mountpoint = "";
+ int android = 0;
+ u32 root_inode_num;
+ u16 root_mode;
+
+ while ((opt = getopt(argc, argv, "l:j:b:g:i:I:L:a:f")) != -1) {
+ switch (opt) {
+ case 'l':
+ info.len = parse_num(optarg);
+ break;
+ case 'j':
+ info.journal_blocks = parse_num(optarg);
+ break;
+ case 'b':
+ info.block_size = parse_num(optarg);
+ break;
+ case 'g':
+ info.blocks_per_group = parse_num(optarg);
+ break;
+ case 'i':
+ info.inodes = parse_num(optarg);
+ break;
+ case 'I':
+ info.inode_size = parse_num(optarg);
+ break;
+ case 'L':
+ info.label = optarg;
+ break;
+ case 'f':
+ force = 1;
+ break;
+ case 'a':
+ android = 1;
+ mountpoint = optarg;
+ break;
+ default: /* '?' */
+ usage(argv[0]);
+ exit(EXIT_FAILURE);
+ }
+ }
+
+ if (optind >= argc) {
+ fprintf(stderr, "Expected filename after options\n");
+ usage(argv[0]);
+ exit(EXIT_FAILURE);
+ }
+
+ filename = argv[optind++];
+
+ if (optind < argc)
+ directory = argv[optind++];
+
+ if (optind < argc) {
+ fprintf(stderr, "Unexpected argument: %s\n", argv[optind]);
+ usage(argv[0]);
+ exit(EXIT_FAILURE);
+ }
+
+ if (info.len == 0)
+ info.len = get_file_size(filename);
+
+ if (info.len <= 0) {
+ fprintf(stderr, "Need size of filesystem\n");
+ usage(argv[0]);
+ exit(EXIT_FAILURE);
+ }
+
+ if (info.journal_blocks > 0)
+ info.feat_compat = EXT4_FEATURE_COMPAT_HAS_JOURNAL;
+
+ if (info.block_size <= 0)
+ info.block_size = compute_block_size();
+
+ 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(" 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);
+
+ 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);
+
+ return 0;
+}
diff --git a/ext4_utils/make_ext4fs.h b/ext4_utils/make_ext4fs.h
new file mode 100644
index 0000000..11fdf77
--- /dev/null
+++ b/ext4_utils/make_ext4fs.h
@@ -0,0 +1,23 @@
+/*
+ * 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"
+
+#endif
diff --git a/ext4_utils/sha1.c b/ext4_utils/sha1.c
new file mode 100644
index 0000000..1db9134
--- /dev/null
+++ b/ext4_utils/sha1.c
@@ -0,0 +1,271 @@
+/* $NetBSD: sha1.c,v 1.1 2005/12/20 20:29:40 christos Exp $ */
+/* $OpenBSD: sha1.c,v 1.9 1997/07/23 21:12:32 kstailey Exp $ */
+
+/*
+ * SHA-1 in C
+ * By Steve Reid <steve@edmweb.com>
+ * 100% Public Domain
+ *
+ * Test Vectors (from FIPS PUB 180-1)
+ * "abc"
+ * A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D
+ * "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
+ * 84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1
+ * A million repetitions of "a"
+ * 34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F
+ */
+
+#define SHA1HANDSOFF /* Copies data before messing with it. */
+
+#include <sys/cdefs.h>
+#include <sys/types.h>
+#include <assert.h>
+#include <string.h>
+
+#include "sha1.h"
+
+#if HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#if !HAVE_SHA1_H
+
+#define rol(value, bits) (((value) << (bits)) | ((value) >> (32 - (bits))))
+
+/*
+ * blk0() and blk() perform the initial expand.
+ * I got the idea of expanding during the round function from SSLeay
+ */
+#if BYTE_ORDER == LITTLE_ENDIAN
+# define blk0(i) (block->l[i] = (rol(block->l[i],24)&0xFF00FF00) \
+ |(rol(block->l[i],8)&0x00FF00FF))
+#else
+# define blk0(i) block->l[i]
+#endif
+#define blk(i) (block->l[i&15] = rol(block->l[(i+13)&15]^block->l[(i+8)&15] \
+ ^block->l[(i+2)&15]^block->l[i&15],1))
+
+/*
+ * (R0+R1), R2, R3, R4 are the different operations (rounds) used in SHA1
+ */
+#define R0(v,w,x,y,z,i) z+=((w&(x^y))^y)+blk0(i)+0x5A827999+rol(v,5);w=rol(w,30);
+#define R1(v,w,x,y,z,i) z+=((w&(x^y))^y)+blk(i)+0x5A827999+rol(v,5);w=rol(w,30);
+#define R2(v,w,x,y,z,i) z+=(w^x^y)+blk(i)+0x6ED9EBA1+rol(v,5);w=rol(w,30);
+#define R3(v,w,x,y,z,i) z+=(((w|x)&y)|(w&x))+blk(i)+0x8F1BBCDC+rol(v,5);w=rol(w,30);
+#define R4(v,w,x,y,z,i) z+=(w^x^y)+blk(i)+0xCA62C1D6+rol(v,5);w=rol(w,30);
+
+typedef union {
+ u_char c[64];
+ u_int l[16];
+} CHAR64LONG16;
+
+/* old sparc64 gcc could not compile this */
+#undef SPARC64_GCC_WORKAROUND
+#if defined(__sparc64__) && defined(__GNUC__) && __GNUC__ < 3
+#define SPARC64_GCC_WORKAROUND
+#endif
+
+#ifdef SPARC64_GCC_WORKAROUND
+void do_R01(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *);
+void do_R2(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *);
+void do_R3(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *);
+void do_R4(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *);
+
+#define nR0(v,w,x,y,z,i) R0(*v,*w,*x,*y,*z,i)
+#define nR1(v,w,x,y,z,i) R1(*v,*w,*x,*y,*z,i)
+#define nR2(v,w,x,y,z,i) R2(*v,*w,*x,*y,*z,i)
+#define nR3(v,w,x,y,z,i) R3(*v,*w,*x,*y,*z,i)
+#define nR4(v,w,x,y,z,i) R4(*v,*w,*x,*y,*z,i)
+
+void
+do_R01(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *block)
+{
+ nR0(a,b,c,d,e, 0); nR0(e,a,b,c,d, 1); nR0(d,e,a,b,c, 2); nR0(c,d,e,a,b, 3);
+ nR0(b,c,d,e,a, 4); nR0(a,b,c,d,e, 5); nR0(e,a,b,c,d, 6); nR0(d,e,a,b,c, 7);
+ nR0(c,d,e,a,b, 8); nR0(b,c,d,e,a, 9); nR0(a,b,c,d,e,10); nR0(e,a,b,c,d,11);
+ nR0(d,e,a,b,c,12); nR0(c,d,e,a,b,13); nR0(b,c,d,e,a,14); nR0(a,b,c,d,e,15);
+ nR1(e,a,b,c,d,16); nR1(d,e,a,b,c,17); nR1(c,d,e,a,b,18); nR1(b,c,d,e,a,19);
+}
+
+void
+do_R2(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *block)
+{
+ nR2(a,b,c,d,e,20); nR2(e,a,b,c,d,21); nR2(d,e,a,b,c,22); nR2(c,d,e,a,b,23);
+ nR2(b,c,d,e,a,24); nR2(a,b,c,d,e,25); nR2(e,a,b,c,d,26); nR2(d,e,a,b,c,27);
+ nR2(c,d,e,a,b,28); nR2(b,c,d,e,a,29); nR2(a,b,c,d,e,30); nR2(e,a,b,c,d,31);
+ nR2(d,e,a,b,c,32); nR2(c,d,e,a,b,33); nR2(b,c,d,e,a,34); nR2(a,b,c,d,e,35);
+ nR2(e,a,b,c,d,36); nR2(d,e,a,b,c,37); nR2(c,d,e,a,b,38); nR2(b,c,d,e,a,39);
+}
+
+void
+do_R3(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *block)
+{
+ nR3(a,b,c,d,e,40); nR3(e,a,b,c,d,41); nR3(d,e,a,b,c,42); nR3(c,d,e,a,b,43);
+ nR3(b,c,d,e,a,44); nR3(a,b,c,d,e,45); nR3(e,a,b,c,d,46); nR3(d,e,a,b,c,47);
+ nR3(c,d,e,a,b,48); nR3(b,c,d,e,a,49); nR3(a,b,c,d,e,50); nR3(e,a,b,c,d,51);
+ nR3(d,e,a,b,c,52); nR3(c,d,e,a,b,53); nR3(b,c,d,e,a,54); nR3(a,b,c,d,e,55);
+ nR3(e,a,b,c,d,56); nR3(d,e,a,b,c,57); nR3(c,d,e,a,b,58); nR3(b,c,d,e,a,59);
+}
+
+void
+do_R4(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *block)
+{
+ nR4(a,b,c,d,e,60); nR4(e,a,b,c,d,61); nR4(d,e,a,b,c,62); nR4(c,d,e,a,b,63);
+ nR4(b,c,d,e,a,64); nR4(a,b,c,d,e,65); nR4(e,a,b,c,d,66); nR4(d,e,a,b,c,67);
+ nR4(c,d,e,a,b,68); nR4(b,c,d,e,a,69); nR4(a,b,c,d,e,70); nR4(e,a,b,c,d,71);
+ nR4(d,e,a,b,c,72); nR4(c,d,e,a,b,73); nR4(b,c,d,e,a,74); nR4(a,b,c,d,e,75);
+ nR4(e,a,b,c,d,76); nR4(d,e,a,b,c,77); nR4(c,d,e,a,b,78); nR4(b,c,d,e,a,79);
+}
+#endif
+
+/*
+ * Hash a single 512-bit block. This is the core of the algorithm.
+ */
+void SHA1Transform(state, buffer)
+ u_int32_t state[5];
+ const u_char buffer[64];
+{
+ u_int32_t a, b, c, d, e;
+ CHAR64LONG16 *block;
+
+#ifdef SHA1HANDSOFF
+ CHAR64LONG16 workspace;
+#endif
+
+ assert(buffer != 0);
+ assert(state != 0);
+
+#ifdef SHA1HANDSOFF
+ block = &workspace;
+ (void)memcpy(block, buffer, 64);
+#else
+ block = (CHAR64LONG16 *)(void *)buffer;
+#endif
+
+ /* Copy context->state[] to working vars */
+ a = state[0];
+ b = state[1];
+ c = state[2];
+ d = state[3];
+ e = state[4];
+
+#ifdef SPARC64_GCC_WORKAROUND
+ do_R01(&a, &b, &c, &d, &e, block);
+ do_R2(&a, &b, &c, &d, &e, block);
+ do_R3(&a, &b, &c, &d, &e, block);
+ do_R4(&a, &b, &c, &d, &e, block);
+#else
+ /* 4 rounds of 20 operations each. Loop unrolled. */
+ R0(a,b,c,d,e, 0); R0(e,a,b,c,d, 1); R0(d,e,a,b,c, 2); R0(c,d,e,a,b, 3);
+ R0(b,c,d,e,a, 4); R0(a,b,c,d,e, 5); R0(e,a,b,c,d, 6); R0(d,e,a,b,c, 7);
+ R0(c,d,e,a,b, 8); R0(b,c,d,e,a, 9); R0(a,b,c,d,e,10); R0(e,a,b,c,d,11);
+ R0(d,e,a,b,c,12); R0(c,d,e,a,b,13); R0(b,c,d,e,a,14); R0(a,b,c,d,e,15);
+ R1(e,a,b,c,d,16); R1(d,e,a,b,c,17); R1(c,d,e,a,b,18); R1(b,c,d,e,a,19);
+ R2(a,b,c,d,e,20); R2(e,a,b,c,d,21); R2(d,e,a,b,c,22); R2(c,d,e,a,b,23);
+ R2(b,c,d,e,a,24); R2(a,b,c,d,e,25); R2(e,a,b,c,d,26); R2(d,e,a,b,c,27);
+ R2(c,d,e,a,b,28); R2(b,c,d,e,a,29); R2(a,b,c,d,e,30); R2(e,a,b,c,d,31);
+ R2(d,e,a,b,c,32); R2(c,d,e,a,b,33); R2(b,c,d,e,a,34); R2(a,b,c,d,e,35);
+ R2(e,a,b,c,d,36); R2(d,e,a,b,c,37); R2(c,d,e,a,b,38); R2(b,c,d,e,a,39);
+ R3(a,b,c,d,e,40); R3(e,a,b,c,d,41); R3(d,e,a,b,c,42); R3(c,d,e,a,b,43);
+ R3(b,c,d,e,a,44); R3(a,b,c,d,e,45); R3(e,a,b,c,d,46); R3(d,e,a,b,c,47);
+ R3(c,d,e,a,b,48); R3(b,c,d,e,a,49); R3(a,b,c,d,e,50); R3(e,a,b,c,d,51);
+ R3(d,e,a,b,c,52); R3(c,d,e,a,b,53); R3(b,c,d,e,a,54); R3(a,b,c,d,e,55);
+ R3(e,a,b,c,d,56); R3(d,e,a,b,c,57); R3(c,d,e,a,b,58); R3(b,c,d,e,a,59);
+ R4(a,b,c,d,e,60); R4(e,a,b,c,d,61); R4(d,e,a,b,c,62); R4(c,d,e,a,b,63);
+ R4(b,c,d,e,a,64); R4(a,b,c,d,e,65); R4(e,a,b,c,d,66); R4(d,e,a,b,c,67);
+ R4(c,d,e,a,b,68); R4(b,c,d,e,a,69); R4(a,b,c,d,e,70); R4(e,a,b,c,d,71);
+ R4(d,e,a,b,c,72); R4(c,d,e,a,b,73); R4(b,c,d,e,a,74); R4(a,b,c,d,e,75);
+ R4(e,a,b,c,d,76); R4(d,e,a,b,c,77); R4(c,d,e,a,b,78); R4(b,c,d,e,a,79);
+#endif
+
+ /* Add the working vars back into context.state[] */
+ state[0] += a;
+ state[1] += b;
+ state[2] += c;
+ state[3] += d;
+ state[4] += e;
+
+ /* Wipe variables */
+ a = b = c = d = e = 0;
+}
+
+
+/*
+ * SHA1Init - Initialize new context
+ */
+void SHA1Init(context)
+ SHA1_CTX *context;
+{
+
+ assert(context != 0);
+
+ /* SHA1 initialization constants */
+ context->state[0] = 0x67452301;
+ context->state[1] = 0xEFCDAB89;
+ context->state[2] = 0x98BADCFE;
+ context->state[3] = 0x10325476;
+ context->state[4] = 0xC3D2E1F0;
+ context->count[0] = context->count[1] = 0;
+}
+
+
+/*
+ * Run your data through this.
+ */
+void SHA1Update(context, data, len)
+ SHA1_CTX *context;
+ const u_char *data;
+ u_int len;
+{
+ u_int i, j;
+
+ assert(context != 0);
+ assert(data != 0);
+
+ j = context->count[0];
+ if ((context->count[0] += len << 3) < j)
+ context->count[1] += (len>>29)+1;
+ j = (j >> 3) & 63;
+ if ((j + len) > 63) {
+ (void)memcpy(&context->buffer[j], data, (i = 64-j));
+ SHA1Transform(context->state, context->buffer);
+ for ( ; i + 63 < len; i += 64)
+ SHA1Transform(context->state, &data[i]);
+ j = 0;
+ } else {
+ i = 0;
+ }
+ (void)memcpy(&context->buffer[j], &data[i], len - i);
+}
+
+
+/*
+ * Add padding and return the message digest.
+ */
+void SHA1Final(digest, context)
+ u_char digest[20];
+ SHA1_CTX* context;
+{
+ u_int i;
+ u_char finalcount[8];
+
+ assert(digest != 0);
+ assert(context != 0);
+
+ for (i = 0; i < 8; i++) {
+ finalcount[i] = (u_char)((context->count[(i >= 4 ? 0 : 1)]
+ >> ((3-(i & 3)) * 8) ) & 255); /* Endian independent */
+ }
+ SHA1Update(context, (const u_char *)"\200", 1);
+ while ((context->count[0] & 504) != 448)
+ SHA1Update(context, (const u_char *)"\0", 1);
+ SHA1Update(context, finalcount, 8); /* Should cause a SHA1Transform() */
+
+ if (digest) {
+ for (i = 0; i < 20; i++)
+ digest[i] = (u_char)
+ ((context->state[i>>2] >> ((3-(i & 3)) * 8) ) & 255);
+ }
+}
+
+#endif /* HAVE_SHA1_H */
diff --git a/ext4_utils/sha1.h b/ext4_utils/sha1.h
new file mode 100644
index 0000000..71334c8
--- /dev/null
+++ b/ext4_utils/sha1.h
@@ -0,0 +1,32 @@
+/* $NetBSD: sha1.h,v 1.13 2005/12/26 18:41:36 perry Exp $ */
+
+/*
+ * SHA-1 in C
+ * By Steve Reid <steve@edmweb.com>
+ * 100% Public Domain
+ */
+
+#ifndef _SYS_SHA1_H_
+#define _SYS_SHA1_H_
+
+#include <sys/cdefs.h>
+#include <sys/types.h>
+#include <stdint.h>
+
+#define SHA1_DIGEST_LENGTH 20
+#define SHA1_DIGEST_STRING_LENGTH 41
+
+typedef struct {
+ uint32_t state[5];
+ uint32_t count[2];
+ u_char buffer[64];
+} SHA1_CTX;
+
+__BEGIN_DECLS
+void SHA1Transform(uint32_t[5], const u_char[64]);
+void SHA1Init(SHA1_CTX *);
+void SHA1Update(SHA1_CTX *, const u_char *, u_int);
+void SHA1Final(u_char[SHA1_DIGEST_LENGTH], SHA1_CTX *);
+__END_DECLS
+
+#endif /* _SYS_SHA1_H_ */
diff --git a/ext4_utils/uuid.c b/ext4_utils/uuid.c
new file mode 100644
index 0000000..c1bec2a
--- /dev/null
+++ b/ext4_utils/uuid.c
@@ -0,0 +1,59 @@
+/*
+ * 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 <string.h>
+#include <arpa/inet.h>
+
+#include "ext4_utils.h"
+#include "sha1.h"
+#include "uuid.h"
+
+struct uuid {
+ u32 time_low;
+ u32 time_mid;
+ u16 time_hi_and_version;
+ u8 clk_seq_hi_res;
+ u8 clk_seq_low;
+ u16 node0_1;
+ u32 node2_5;
+};
+
+static void sha1_hash(const char *namespace, const char *name,
+ unsigned char sha1[SHA1_DIGEST_LENGTH])
+{
+ SHA1_CTX ctx;
+ SHA1Init(&ctx);
+ SHA1Update(&ctx, (const u8*)namespace, strlen(namespace));
+ SHA1Update(&ctx, (const u8*)name, strlen(name));
+ SHA1Final(sha1, &ctx);
+}
+
+void generate_uuid(const char *namespace, const char *name, u8 result[16])
+{
+ unsigned char sha1[SHA1_DIGEST_LENGTH];
+ struct uuid *uuid = (struct uuid *)result;
+
+ sha1_hash(namespace, name, (unsigned char*)sha1);
+ memcpy(uuid, sha1, sizeof(struct uuid));
+
+ uuid->time_low = ntohl(uuid->time_low);
+ uuid->time_mid = ntohs(uuid->time_mid);
+ uuid->time_hi_and_version = ntohs(uuid->time_hi_and_version);
+ uuid->time_hi_and_version &= 0x0FFF;
+ uuid->time_hi_and_version |= (5 << 12);
+ uuid->clk_seq_hi_res &= ~(1 << 6);
+ uuid->clk_seq_hi_res |= 1 << 7;
+}
diff --git a/ext4_utils/uuid.h b/ext4_utils/uuid.h
new file mode 100644
index 0000000..ff1b438
--- /dev/null
+++ b/ext4_utils/uuid.h
@@ -0,0 +1,24 @@
+/*
+ * 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 _UUID_H_
+#define _UUID_H_
+
+#include "ext4_utils.h"
+
+void generate_uuid(const char *namespace, const char *name, u8 result[16]);
+
+#endif