aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--contrib/android/base_fs.c11
-rw-r--r--contrib/android/base_fs.h3
-rw-r--r--contrib/android/basefs_allocator.c277
-rw-r--r--contrib/android/basefs_allocator.h2
-rw-r--r--contrib/android/block_list.c25
-rw-r--r--contrib/android/block_range.c46
-rw-r--r--contrib/android/block_range.h17
-rw-r--r--contrib/android/e2fsdroid.c3
8 files changed, 282 insertions, 102 deletions
diff --git a/contrib/android/base_fs.c b/contrib/android/base_fs.c
index 14203050..652317e2 100644
--- a/contrib/android/base_fs.c
+++ b/contrib/android/base_fs.c
@@ -72,8 +72,7 @@ static struct basefs_entry *basefs_readline(FILE *f, const char *mountpoint,
range_start = atoll(block);
block = strtok_r(NULL, "-", &saveptr2);
range_end = block ? atoll(block) : range_start;
- add_blocks_to_range(&entry->head, &entry->tail, range_start,
- range_end);
+ add_blocks_to_range(&entry->blocks, range_start, range_end);
block_range = strtok_r(NULL, ",\n", &saveptr1);
}
end:
@@ -151,7 +150,6 @@ static int start_new_file(char *path, ext2_ino_t ino EXT2FS_ATTR((unused)),
{
struct base_fs *params = data;
- params->entry.head = params->entry.tail = NULL;
params->entry.path = LINUX_S_ISREG(inode->i_mode) ? path : NULL;
return 0;
}
@@ -162,8 +160,7 @@ static int add_block(ext2_filsys fs EXT2FS_ATTR((unused)), blk64_t blocknr,
struct base_fs *params = data;
if (params->entry.path && !metadata)
- add_blocks_to_range(&params->entry.head, &params->entry.tail,
- blocknr, blocknr);
+ add_blocks_to_range(&params->entry.blocks, blocknr, blocknr);
return 0;
}
@@ -181,11 +178,11 @@ static int end_new_file(void *data)
return 0;
if (fprintf(params->file, "%s%s ", params->mountpoint,
params->entry.path) < 0
- || write_block_ranges(params->file, params->entry.head, ",")
+ || write_block_ranges(params->file, params->entry.blocks.head, ",")
|| fwrite("\n", 1, 1, params->file) != 1)
return -1;
- delete_block_ranges(params->entry.head);
+ delete_block_ranges(&params->entry.blocks);
return 0;
}
diff --git a/contrib/android/base_fs.h b/contrib/android/base_fs.h
index e9f46b4a..f53f1ed8 100644
--- a/contrib/android/base_fs.h
+++ b/contrib/android/base_fs.h
@@ -7,8 +7,7 @@
struct basefs_entry {
char *path;
- struct block_range *head;
- struct block_range *tail;
+ struct block_range_list blocks;
};
extern struct fsmap_format base_fs_format;
diff --git a/contrib/android/basefs_allocator.c b/contrib/android/basefs_allocator.c
index a014744a..8a2b27e6 100644
--- a/contrib/android/basefs_allocator.c
+++ b/contrib/android/basefs_allocator.c
@@ -1,3 +1,4 @@
+#include <limits.h>
#include <sys/types.h>
#include <sys/stat.h>
#include "basefs_allocator.h"
@@ -8,108 +9,270 @@
struct base_fs_allocator {
struct ext2fs_hashmap *entries;
struct basefs_entry *cur_entry;
+ /* Blocks which are definitely owned by a single inode in BaseFS. */
+ ext2fs_block_bitmap exclusive_block_map;
+ /* Blocks which are available to the first inode that requests it. */
+ ext2fs_block_bitmap dedup_block_map;
};
static errcode_t basefs_block_allocator(ext2_filsys, blk64_t, blk64_t *,
struct blk_alloc_ctx *ctx);
-static void fs_free_blocks_range(ext2_filsys fs, struct block_range *blocks)
+/*
+ * Free any reserved, but unconsumed block ranges in the allocator. This both
+ * frees the block_range_list data structure and unreserves exclusive blocks
+ * from the block map.
+ */
+static void fs_free_blocks_range(ext2_filsys fs,
+ struct base_fs_allocator *allocator,
+ struct block_range_list *list)
{
- while (blocks) {
- ext2fs_unmark_block_bitmap_range2(fs->block_map, blocks->start,
- blocks->end - blocks->start + 1);
- blocks = blocks->next;
+ ext2fs_block_bitmap exclusive_map = allocator->exclusive_block_map;
+
+ blk64_t block;
+ while (list->head) {
+ block = consume_next_block(list);
+ if (ext2fs_test_block_bitmap2(exclusive_map, block)) {
+ ext2fs_unmark_block_bitmap2(fs->block_map, block);
+ ext2fs_unmark_block_bitmap2(exclusive_map, block);
+ }
+ }
+}
+
+static void basefs_allocator_free(ext2_filsys fs,
+ struct base_fs_allocator *allocator)
+{
+ struct basefs_entry *e;
+ struct ext2fs_hashmap_entry *it = NULL;
+ struct ext2fs_hashmap *entries = allocator->entries;
+
+ if (entries) {
+ while ((e = ext2fs_hashmap_iter_in_order(entries, &it))) {
+ fs_free_blocks_range(fs, allocator, &e->blocks);
+ delete_block_ranges(&e->blocks);
+ }
+ ext2fs_hashmap_free(entries);
+ }
+ ext2fs_free_block_bitmap(allocator->exclusive_block_map);
+ ext2fs_free_block_bitmap(allocator->dedup_block_map);
+ free(allocator);
+}
+
+/*
+ * Build a bitmap of which blocks are definitely owned by exactly one file in
+ * Base FS. Blocks which are not valid or are de-duplicated are skipped. This
+ * is called during allocator initialization, to ensure that libext2fs does
+ * not allocate which we want to re-use.
+ *
+ * If a block was allocated in the initial filesystem, it can never be re-used,
+ * so it will appear in neither the exclusive or dedup set. If a block is used
+ * by multiple files, it will be removed from the owned set and instead added
+ * to the dedup set.
+ *
+ * The dedup set is not removed from fs->block_map. This allows us to re-use
+ * dedup blocks separately and not have them be allocated outside of file data.
+ *
+ * This function returns non-zero if the block was owned, and 0 otherwise.
+ */
+static int fs_reserve_block(ext2_filsys fs,
+ struct base_fs_allocator *allocator,
+ blk64_t block)
+{
+ ext2fs_block_bitmap exclusive_map = allocator->exclusive_block_map;
+ ext2fs_block_bitmap dedup_map = allocator->dedup_block_map;
+
+ if (block >= ext2fs_blocks_count(fs->super))
+ return 0;
+
+ if (ext2fs_test_block_bitmap2(fs->block_map, block)) {
+ if (!ext2fs_test_block_bitmap2(exclusive_map, block))
+ return 0;
+ ext2fs_unmark_block_bitmap2(exclusive_map, block);
+ ext2fs_mark_block_bitmap2(dedup_map, block);
+ return 0;
+ } else {
+ ext2fs_mark_block_bitmap2(fs->block_map, block);
+ ext2fs_mark_block_bitmap2(exclusive_map, block);
+ return 1;
}
}
-static void fs_reserve_blocks_range(ext2_filsys fs, struct block_range *blocks)
+/*
+ * Walk the requested block list and reserve blocks, either into the owned
+ * pool or the dedup pool as appropriate. We stop once the file has enough
+ * owned blocks to satisfy |file_size|. This allows any extra blocks to be
+ * re-used, since otherwise a large block movement between files could
+ * trigger block allocation errors.
+ */
+static void fs_reserve_blocks_range(ext2_filsys fs,
+ struct base_fs_allocator *allocator,
+ struct block_range_list *list,
+ off_t file_size)
{
+ blk64_t block;
+ off_t blocks_needed;
+ off_t blocks_acquired = 0;
+ struct block_range *blocks = list->head;
+
+ blocks_needed = file_size + (fs->blocksize - 1);
+ blocks_needed /= fs->blocksize;
+
while (blocks) {
- ext2fs_mark_block_bitmap_range2(fs->block_map,
- blocks->start, blocks->end - blocks->start + 1);
+ for (block = blocks->start; block <= blocks->end; block++) {
+ if (fs_reserve_block(fs, allocator, block))
+ blocks_acquired++;
+ if (blocks_acquired >= blocks_needed)
+ return;
+ }
blocks = blocks->next;
}
}
-errcode_t base_fs_alloc_load(ext2_filsys fs, const char *file,
- const char *mountpoint)
+/*
+ * For each file in the base FS map, ensure that its blocks are reserved in
+ * the actual block map. This prevents libext2fs from allocating them for
+ * general purpose use, and ensures that if the file needs data blocks, they
+ * can be re-acquired exclusively for that file.
+ *
+ * If a file in the base map is missing, or not a regular file in the new
+ * filesystem, then it's skipped to ensure that its blocks are reusable.
+ */
+static errcode_t fs_reserve_blocks(ext2_filsys fs,
+ struct base_fs_allocator *allocator,
+ const char *src_dir)
{
- errcode_t retval;
+ int nbytes;
+ char full_path[PATH_MAX];
+ const char *sep = "/";
+ struct stat st;
struct basefs_entry *e;
struct ext2fs_hashmap_entry *it = NULL;
+ struct ext2fs_hashmap *entries = allocator->entries;
+
+ if (strlen(src_dir) && src_dir[strlen(src_dir) - 1] == '/')
+ sep = "";
+
+ while ((e = ext2fs_hashmap_iter_in_order(entries, &it))) {
+ nbytes = snprintf(full_path, sizeof(full_path), "%s%s%s",
+ src_dir, sep, e->path);
+ if (nbytes >= sizeof(full_path))
+ return ENAMETOOLONG;
+ if (lstat(full_path, &st) || !S_ISREG(st.st_mode))
+ continue;
+ fs_reserve_blocks_range(fs, allocator, &e->blocks, st.st_size);
+ }
+ return 0;
+}
+
+errcode_t base_fs_alloc_load(ext2_filsys fs, const char *file,
+ const char *mountpoint, const char *src_dir)
+{
+ errcode_t retval = 0;
struct base_fs_allocator *allocator;
- struct ext2fs_hashmap *entries = basefs_parse(file, mountpoint);
- if (!entries)
- return -1;
- allocator = malloc(sizeof(*allocator));
- if (!allocator)
- goto err_alloc;
+ allocator = calloc(1, sizeof(*allocator));
+ if (!allocator) {
+ retval = ENOMEM;
+ goto out;
+ }
retval = ext2fs_read_bitmaps(fs);
if (retval)
- goto err_bitmap;
- while ((e = ext2fs_hashmap_iter_in_order(entries, &it)))
- fs_reserve_blocks_range(fs, e->head);
+ goto err_load;
allocator->cur_entry = NULL;
- allocator->entries = entries;
+ allocator->entries = basefs_parse(file, mountpoint);
+ if (!allocator->entries) {
+ retval = EIO;
+ goto err_load;
+ }
+ retval = ext2fs_allocate_block_bitmap(fs, "exclusive map",
+ &allocator->exclusive_block_map);
+ if (retval)
+ goto err_load;
+ retval = ext2fs_allocate_block_bitmap(fs, "dedup map",
+ &allocator->dedup_block_map);
+ if (retval)
+ goto err_load;
+
+ retval = fs_reserve_blocks(fs, allocator, src_dir);
+ if (retval)
+ goto err_load;
/* Override the default allocator */
fs->get_alloc_block2 = basefs_block_allocator;
fs->priv_data = allocator;
- return 0;
+ goto out;
-err_bitmap:
- free(allocator);
-err_alloc:
- ext2fs_hashmap_free(entries);
- return EXIT_FAILURE;
+err_load:
+ basefs_allocator_free(fs, allocator);
+out:
+ return retval;
+}
+
+/* Try and acquire the next usable block from the Base FS map. */
+static int get_next_block(ext2_filsys fs, struct base_fs_allocator *allocator,
+ struct block_range_list* list, blk64_t *ret)
+{
+ blk64_t block;
+ ext2fs_block_bitmap exclusive_map = allocator->exclusive_block_map;
+ ext2fs_block_bitmap dedup_map = allocator->dedup_block_map;
+
+ while (list->head) {
+ block = consume_next_block(list);
+ if (block >= ext2fs_blocks_count(fs->super))
+ continue;
+ if (ext2fs_test_block_bitmap2(exclusive_map, block)) {
+ ext2fs_unmark_block_bitmap2(exclusive_map, block);
+ *ret = block;
+ return 0;
+ }
+ if (ext2fs_test_block_bitmap2(dedup_map, block)) {
+ ext2fs_unmark_block_bitmap2(dedup_map, block);
+ *ret = block;
+ return 0;
+ }
+ }
+ return -1;
}
static errcode_t basefs_block_allocator(ext2_filsys fs, blk64_t goal,
blk64_t *ret, struct blk_alloc_ctx *ctx)
{
errcode_t retval;
- struct block_range *next_range;
struct base_fs_allocator *allocator = fs->priv_data;
struct basefs_entry *e = allocator->cur_entry;
+ ext2fs_block_bitmap dedup_map = allocator->dedup_block_map;
- /* Try to get a block from the base_fs */
- if (e && e->head && ctx && (ctx->flags & BLOCK_ALLOC_DATA)) {
- *ret = e->head->start;
- e->head->start += 1;
- if (e->head->start > e->head->end) {
- next_range = e->head->next;
- free(e->head);
- e->head = next_range;
- }
- } else { /* Allocate a new block */
- retval = ext2fs_new_block2(fs, goal, fs->block_map, ret);
- if (retval)
- return retval;
+ if (e && ctx && (ctx->flags & BLOCK_ALLOC_DATA)) {
+ if (!get_next_block(fs, allocator, &e->blocks, ret))
+ return 0;
+ }
+
+ retval = ext2fs_new_block2(fs, goal, fs->block_map, ret);
+ if (!retval) {
ext2fs_mark_block_bitmap2(fs->block_map, *ret);
+ return 0;
}
- return 0;
+ if (retval == EXT2_ET_BLOCK_ALLOC_FAIL) {
+ /* Try to steal a block from the dedup pool. */
+ retval = ext2fs_find_first_set_block_bitmap2(dedup_map,
+ fs->super->s_first_data_block,
+ ext2fs_blocks_count(fs->super) - 1, ret);
+ if (!retval) {
+ ext2fs_unmark_block_bitmap2(dedup_map, *ret);
+ return 0;
+ }
+ }
+ return retval;
}
void base_fs_alloc_cleanup(ext2_filsys fs)
{
- struct basefs_entry *e;
- struct ext2fs_hashmap_entry *it = NULL;
- struct base_fs_allocator *allocator = fs->priv_data;
-
- while ((e = ext2fs_hashmap_iter_in_order(allocator->entries, &it))) {
- fs_free_blocks_range(fs, e->head);
- delete_block_ranges(e->head);
- e->head = e->tail = NULL;
- }
-
+ basefs_allocator_free(fs, fs->priv_data);
fs->priv_data = NULL;
fs->get_alloc_block2 = NULL;
- ext2fs_hashmap_free(allocator->entries);
- free(allocator);
}
errcode_t base_fs_alloc_set_target(ext2_filsys fs, const char *target_path,
@@ -140,9 +303,7 @@ errcode_t base_fs_alloc_unset_target(ext2_filsys fs,
if (!allocator || !allocator->cur_entry || mode != S_IFREG)
return 0;
- fs_free_blocks_range(fs, allocator->cur_entry->head);
- delete_block_ranges(allocator->cur_entry->head);
- allocator->cur_entry->head = allocator->cur_entry->tail = NULL;
- allocator->cur_entry = NULL;
+ fs_free_blocks_range(fs, allocator, &allocator->cur_entry->blocks);
+ delete_block_ranges(&allocator->cur_entry->blocks);
return 0;
}
diff --git a/contrib/android/basefs_allocator.h b/contrib/android/basefs_allocator.h
index f1109cd6..6d1c65e3 100644
--- a/contrib/android/basefs_allocator.h
+++ b/contrib/android/basefs_allocator.h
@@ -5,7 +5,7 @@
# include <ext2fs/ext2fs.h>
errcode_t base_fs_alloc_load(ext2_filsys fs, const char *file,
- const char *mountpoint);
+ const char *mountpoint, const char *src_dir);
void base_fs_alloc_cleanup(ext2_filsys fs);
errcode_t base_fs_alloc_set_target(ext2_filsys fs, const char *target_path,
diff --git a/contrib/android/block_list.c b/contrib/android/block_list.c
index 25dcc514..63cc1a22 100644
--- a/contrib/android/block_list.c
+++ b/contrib/android/block_list.c
@@ -9,16 +9,13 @@ struct block_list {
FILE *f;
const char *mountpoint;
- struct {
- const char *filename;
- struct block_range *head;
- struct block_range *tail;
- } entry;
+ const char *filename;
+ struct block_range_list blocks;
};
static void *init(const char *file, const char *mountpoint)
{
- struct block_list *params = malloc(sizeof(*params));
+ struct block_list *params = calloc(1, sizeof(*params));
if (!params)
return NULL;
@@ -37,8 +34,7 @@ static int start_new_file(char *path, ext2_ino_t ino EXT2FS_ATTR((unused)),
{
struct block_list *params = data;
- params->entry.head = params->entry.tail = NULL;
- params->entry.filename = LINUX_S_ISREG(inode->i_mode) ? path : NULL;
+ params->filename = LINUX_S_ISREG(inode->i_mode) ? path : NULL;
return 0;
}
@@ -47,9 +43,8 @@ static int add_block(ext2_filsys fs EXT2FS_ATTR((unused)), blk64_t blocknr,
{
struct block_list *params = data;
- if (params->entry.filename && !metadata)
- add_blocks_to_range(&params->entry.head, &params->entry.tail,
- blocknr, blocknr);
+ if (params->filename && !metadata)
+ add_blocks_to_range(&params->blocks, blocknr, blocknr);
return 0;
}
@@ -63,15 +58,15 @@ static int end_new_file(void *data)
{
struct block_list *params = data;
- if (!params->entry.filename || !params->entry.head)
+ if (!params->filename || !params->blocks.head)
return 0;
if (fprintf(params->f, "%s%s ", params->mountpoint,
- params->entry.filename) < 0
- || write_block_ranges(params->f, params->entry.head, " ")
+ params->filename) < 0
+ || write_block_ranges(params->f, params->blocks.head, " ")
|| fwrite("\n", 1, 1, params->f) != 1)
return -1;
- delete_block_ranges(params->entry.head);
+ delete_block_ranges(&params->blocks);
return 0;
}
diff --git a/contrib/android/block_range.c b/contrib/android/block_range.c
index 2f951c78..0a068826 100644
--- a/contrib/android/block_range.c
+++ b/contrib/android/block_range.c
@@ -12,29 +12,35 @@ struct block_range *new_block_range(blk64_t start, blk64_t end)
return range;
}
-void add_blocks_to_range(struct block_range **head, struct block_range **tail,
- blk64_t blk_start, blk64_t blk_end)
+void add_blocks_to_range(struct block_range_list *list, blk64_t blk_start,
+ blk64_t blk_end)
{
- if (*head == NULL)
- *head = *tail = new_block_range(blk_start, blk_end);
- else if ((*tail)->end + 1 == blk_start)
- (*tail)->end += (blk_end - blk_start + 1);
+ if (list->head == NULL)
+ list->head = list->tail = new_block_range(blk_start, blk_end);
+ else if (list->tail->end + 1 == blk_start)
+ list->tail->end += (blk_end - blk_start + 1);
else {
struct block_range *range = new_block_range(blk_start, blk_end);
- (*tail)->next = range;
- *tail = range;
+ list->tail->next = range;
+ list->tail = range;
}
}
-void delete_block_ranges(struct block_range *head)
+static void remove_head(struct block_range_list *list)
{
- struct block_range *tmp;
+ struct block_range *next_range = list->head->next;
- while (head) {
- tmp = head->next;
- free(head);
- head = tmp;
- }
+ free(list->head);
+ if (next_range == NULL)
+ list->head = list->tail = NULL;
+ else
+ list->head = next_range;
+}
+
+void delete_block_ranges(struct block_range_list *list)
+{
+ while (list->head)
+ remove_head(list);
}
int write_block_ranges(FILE *f, struct block_range *range,
@@ -62,3 +68,13 @@ int write_block_ranges(FILE *f, struct block_range *range,
return -1;
return 0;
}
+
+blk64_t consume_next_block(struct block_range_list *list)
+{
+ blk64_t ret = list->head->start;
+
+ list->head->start += 1;
+ if (list->head->start > list->head->end)
+ remove_head(list);
+ return ret;
+}
diff --git a/contrib/android/block_range.h b/contrib/android/block_range.h
index 31e3c23f..cf7971e8 100644
--- a/contrib/android/block_range.h
+++ b/contrib/android/block_range.h
@@ -10,9 +10,20 @@ struct block_range {
struct block_range *next;
};
-void add_blocks_to_range(struct block_range **head, struct block_range **tail,
- blk64_t blk_start, blk64_t blk_end);
-void delete_block_ranges(struct block_range *head);
+struct block_range_list {
+ struct block_range *head;
+ struct block_range *tail;
+};
+
+void add_blocks_to_range(struct block_range_list *list, blk64_t blk_start,
+ blk64_t blk_end);
+void delete_block_ranges(struct block_range_list *list);
int write_block_ranges(FILE *f, struct block_range *range, char *sep);
+/*
+ * Given a non-empty range list, return the next block and remove it from the
+ * list.
+ */
+blk64_t consume_next_block(struct block_range_list *list);
+
#endif /* !BLOCK_RANGE_H */
diff --git a/contrib/android/e2fsdroid.c b/contrib/android/e2fsdroid.c
index 3264a99f..1beb1e25 100644
--- a/contrib/android/e2fsdroid.c
+++ b/contrib/android/e2fsdroid.c
@@ -301,7 +301,8 @@ int main(int argc, char *argv[])
if (src_dir) {
ext2fs_read_bitmaps(fs);
if (basefs_in) {
- retval = base_fs_alloc_load(fs, basefs_in, mountpoint);
+ retval = base_fs_alloc_load(fs, basefs_in, mountpoint,
+ src_dir);
if (retval) {
com_err(prog_name, retval, "%s",
"while reading base_fs file");
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-17 09:26:56 +0000