Snap for 4562879 from 25c79ea1e064ec47b3d61a4fec8a6530c53846ae to pi-release
Change-Id: I8e8c39a8895bbdc5a65735723bfafe07f94d495b
diff --git a/contrib/android/Android.bp b/contrib/android/Android.bp
index f7fbf66..67844f9 100644
--- a/contrib/android/Android.bp
+++ b/contrib/android/Android.bp
@@ -16,7 +16,6 @@
"base_fs.c",
"perms.c",
"basefs_allocator.c",
- "hashmap.c",
],
target: {
host: {
diff --git a/contrib/android/Android.mk b/contrib/android/Android.mk
index bdfdece..68d925d 100644
--- a/contrib/android/Android.mk
+++ b/contrib/android/Android.mk
@@ -10,7 +10,6 @@
base_fs.c \
perms.c \
basefs_allocator.c \
- hashmap.c \
e2fsdroid_cflags := -W -Wall -Werror -Wno-error=macro-redefined
diff --git a/contrib/android/base_fs.c b/contrib/android/base_fs.c
index 2dcb5fe..1420305 100644
--- a/contrib/android/base_fs.c
+++ b/contrib/android/base_fs.c
@@ -99,24 +99,25 @@
}
}
-struct hashmap *basefs_parse(const char *file, const char *mountpoint)
+struct ext2fs_hashmap *basefs_parse(const char *file, const char *mountpoint)
{
int err;
- struct hashmap *entries = NULL;
+ struct ext2fs_hashmap *entries = NULL;
struct basefs_entry *entry;
FILE *f = basefs_open(file);
if (!f)
return NULL;
- entries = hashmap_create(djb2_hash, free_base_fs_entry, 1024);
+ entries = ext2fs_hashmap_create(ext2fs_djb2_hash, free_base_fs_entry, 1024);
if (!entries)
goto end;
while ((entry = basefs_readline(f, mountpoint, &err)))
- hashmap_add(entries, entry, entry->path);
+ ext2fs_hashmap_add(entries, entry, entry->path,
+ strlen(entry->path));
if (err) {
fclose(f);
- hashmap_free(entries);
+ ext2fs_hashmap_free(entries);
return NULL;
}
end:
diff --git a/contrib/android/base_fs.h b/contrib/android/base_fs.h
index 94bae29..e9f46b4 100644
--- a/contrib/android/base_fs.h
+++ b/contrib/android/base_fs.h
@@ -13,6 +13,6 @@
extern struct fsmap_format base_fs_format;
-struct hashmap *basefs_parse(const char *file, const char *mountpoint);
+struct ext2fs_hashmap *basefs_parse(const char *file, const char *mountpoint);
#endif /* !BASE_FS_H */
diff --git a/contrib/android/basefs_allocator.c b/contrib/android/basefs_allocator.c
index 3d014a2..c44532f 100644
--- a/contrib/android/basefs_allocator.c
+++ b/contrib/android/basefs_allocator.c
@@ -6,7 +6,7 @@
#include "base_fs.h"
struct base_fs_allocator {
- struct hashmap *entries;
+ struct ext2fs_hashmap *entries;
struct basefs_entry *cur_entry;
};
@@ -36,9 +36,9 @@
{
errcode_t retval;
struct basefs_entry *e;
- struct hashmap_entry *it = NULL;
+ struct ext2fs_hashmap_entry *it = NULL;
struct base_fs_allocator *allocator;
- struct hashmap *entries = basefs_parse(file, mountpoint);
+ struct ext2fs_hashmap *entries = basefs_parse(file, mountpoint);
if (!entries)
return -1;
@@ -49,7 +49,7 @@
retval = ext2fs_read_bitmaps(fs);
if (retval)
goto err_bitmap;
- while ((e = hashmap_iter_in_order(entries, &it)))
+ while ((e = ext2fs_hashmap_iter_in_order(entries, &it)))
fs_reserve_blocks_range(fs, e->head);
allocator->cur_entry = NULL;
@@ -64,7 +64,7 @@
err_bitmap:
free(allocator);
err_alloc:
- hashmap_free(entries);
+ ext2fs_hashmap_free(entries);
return EXIT_FAILURE;
}
@@ -97,10 +97,10 @@
void base_fs_alloc_cleanup(ext2_filsys fs)
{
struct basefs_entry *e;
- struct hashmap_entry *it = NULL;
+ struct ext2fs_hashmap_entry *it = NULL;
struct base_fs_allocator *allocator = fs->priv_data;
- while ((e = hashmap_iter_in_order(allocator->entries, &it))) {
+ 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;
@@ -108,7 +108,7 @@
fs->priv_data = NULL;
fs->get_alloc_block2 = NULL;
- hashmap_free(allocator->entries);
+ ext2fs_hashmap_free(allocator->entries);
free(allocator);
}
@@ -123,8 +123,9 @@
return 0;
if (allocator)
- allocator->cur_entry = hashmap_lookup(allocator->entries,
- target_path);
+ allocator->cur_entry = ext2fs_hashmap_lookup(allocator->entries,
+ target_path,
+ strlen(target_path));
return 0;
}
diff --git a/contrib/android/e2fsdroid.c b/contrib/android/e2fsdroid.c
index c73b0be..2fe922d 100644
--- a/contrib/android/e2fsdroid.c
+++ b/contrib/android/e2fsdroid.c
@@ -32,7 +32,7 @@
{
fprintf(stderr, "%s [-B block_list] [-D basefs_out] [-T timestamp]\n"
"\t[-C fs_config] [-S file_contexts] [-p product_out]\n"
- "\t[-a mountpoint] [-d basefs_in] [-f src_dir] [-e] image\n",
+ "\t[-a mountpoint] [-d basefs_in] [-f src_dir] [-e] [-s] image\n",
prog_name);
exit(ret);
}
@@ -73,7 +73,7 @@
add_error_table(&et_ext2_error_table);
- while ((c = getopt (argc, argv, "T:C:S:p:a:D:d:B:f:e")) != EOF) {
+ while ((c = getopt (argc, argv, "T:C:S:p:a:D:d:B:f:es")) != EOF) {
switch (c) {
case 'T':
fixed_time = strtoul(optarg, &p, 0);
@@ -119,6 +119,9 @@
case 'e':
android_sparse_file = 0;
break;
+ case 's':
+ flags |= EXT2_FLAG_SHARE_DUP;
+ break;
default:
usage(EXIT_FAILURE);
}
diff --git a/contrib/android/hashmap.c b/contrib/android/hashmap.c
deleted file mode 100644
index eee0071..0000000
--- a/contrib/android/hashmap.c
+++ /dev/null
@@ -1,76 +0,0 @@
-#include "hashmap.h"
-#include <string.h>
-
-uint32_t djb2_hash(const void *str)
-{
- int c;
- const char *s = str;
- uint32_t hash = 5381;
-
- while ((c = *s++))
- hash = ((hash << 5) + hash) + c;
- return hash;
-}
-
-struct hashmap *hashmap_create(uint32_t(*hash_fct)(const void*),
- void(*free_fct)(void*), size_t size)
-{
- struct hashmap *h = calloc(sizeof(struct hashmap) +
- sizeof(struct hashmap_entry) * size, 1);
- h->size = size;
- h->free = free_fct;
- h->hash = hash_fct;
- h->first = h->last = NULL;
- return h;
-}
-
-void hashmap_add(struct hashmap *h, void *data, const void *key)
-{
- uint32_t hash = h->hash(key) % h->size;
- struct hashmap_entry *e = malloc(sizeof(*e));
-
- e->data = data;
- e->key = key;
- e->next = h->entries[hash];
- h->entries[hash] = e;
-
- e->list_prev = NULL;
- e->list_next = h->first;
- if (h->first)
- h->first->list_prev = e;
- h->first = e;
- if (!h->last)
- h->last = e;
-}
-
-void *hashmap_lookup(struct hashmap *h, const void *key)
-{
- struct hashmap_entry *iter;
- uint32_t hash = h->hash(key) % h->size;
-
- for (iter = h->entries[hash]; iter; iter = iter->next)
- if (!strcmp(iter->key, key))
- return iter->data;
- return NULL;
-}
-
-void *hashmap_iter_in_order(struct hashmap *h, struct hashmap_entry **it)
-{
- *it = *it ? (*it)->list_next : h->first;
- return *it ? (*it)->data : NULL;
-}
-
-void hashmap_free(struct hashmap *h)
-{
- for (size_t i = 0; i < h->size; ++i) {
- struct hashmap_entry *it = h->entries[i];
- while (it) {
- struct hashmap_entry *tmp = it->next;
- if (h->free)
- h->free(it->data);
- free(it);
- it = tmp;
- }
- }
- free(h);
-}
diff --git a/contrib/android/hashmap.h b/contrib/android/hashmap.h
deleted file mode 100644
index 70d0ed1..0000000
--- a/contrib/android/hashmap.h
+++ /dev/null
@@ -1,32 +0,0 @@
-#ifndef HASHMAP_H
-# define HASHMAP_H
-
-# include <stdlib.h>
-# include <stdint.h>
-
-struct hashmap {
- uint32_t size;
- uint32_t(*hash)(const void *key);
- void(*free)(void*);
- struct hashmap_entry *first;
- struct hashmap_entry *last;
- struct hashmap_entry {
- void *data;
- const void *key;
- struct hashmap_entry *next;
- struct hashmap_entry *list_next;
- struct hashmap_entry *list_prev;
- } *entries[0];
-};
-
-struct hashmap *hashmap_create(uint32_t(*hash_fct)(const void*),
- void(*free_fct)(void*), size_t size);
-void hashmap_add(struct hashmap *h, void *data, const void *key);
-void *hashmap_lookup(struct hashmap *h, const void *key);
-void *hashmap_iter_in_order(struct hashmap *h, struct hashmap_entry **it);
-void hashmap_del(struct hashmap *h, struct hashmap_entry *e);
-void hashmap_free(struct hashmap *h);
-
-uint32_t djb2_hash(const void *str);
-
-#endif /* !HASHMAP_H */
diff --git a/lib/e2p/feature.c b/lib/e2p/feature.c
index b7f6c1d..0fab9c7 100644
--- a/lib/e2p/feature.c
+++ b/lib/e2p/feature.c
@@ -72,6 +72,8 @@
"read-only" },
{ E2P_FEATURE_RO_INCOMPAT, EXT4_FEATURE_RO_COMPAT_PROJECT,
"project"},
+ { E2P_FEATURE_RO_INCOMPAT, EXT4_FEATURE_RO_COMPAT_SHARED_BLOCKS,
+ "shared_blocks"},
{ E2P_FEATURE_INCOMPAT, EXT2_FEATURE_INCOMPAT_COMPRESSION,
"compression" },
diff --git a/lib/ext2fs/Android.bp b/lib/ext2fs/Android.bp
index 427d93b..06a750e 100644
--- a/lib/ext2fs/Android.bp
+++ b/lib/ext2fs/Android.bp
@@ -47,6 +47,7 @@
"get_pathname.c",
"getsize.c",
"getsectsize.c",
+ "hashmap.c",
"i_block.c",
"icount.c",
"imager.c",
diff --git a/lib/ext2fs/ext2_fs.h b/lib/ext2fs/ext2_fs.h
index 27a7d3a..ab1db6e 100644
--- a/lib/ext2fs/ext2_fs.h
+++ b/lib/ext2fs/ext2_fs.h
@@ -812,6 +812,7 @@
#define EXT4_FEATURE_RO_COMPAT_REPLICA 0x0800
#define EXT4_FEATURE_RO_COMPAT_READONLY 0x1000
#define EXT4_FEATURE_RO_COMPAT_PROJECT 0x2000 /* Project quota */
+#define EXT4_FEATURE_RO_COMPAT_SHARED_BLOCKS 0x4000
#define EXT2_FEATURE_INCOMPAT_COMPRESSION 0x0001
@@ -904,6 +905,7 @@
EXT4_FEATURE_RO_COMPAT_FUNCS(replica, 4, REPLICA)
EXT4_FEATURE_RO_COMPAT_FUNCS(readonly, 4, READONLY)
EXT4_FEATURE_RO_COMPAT_FUNCS(project, 4, PROJECT)
+EXT4_FEATURE_RO_COMPAT_FUNCS(shared_blocks, 4, SHARED_BLOCKS)
EXT4_FEATURE_INCOMPAT_FUNCS(compression, 2, COMPRESSION)
EXT4_FEATURE_INCOMPAT_FUNCS(filetype, 2, FILETYPE)
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index e153c81..470e7d7 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -94,6 +94,8 @@
#include <ext2fs/ext2_ext_attr.h>
#endif
+#include "hashmap.h"
+
/*
* Portability help for Microsoft Visual C++
*/
@@ -195,6 +197,7 @@
#define EXT2_FLAG_DIRECT_IO 0x80000
#define EXT2_FLAG_SKIP_MMP 0x100000
#define EXT2_FLAG_IGNORE_CSUM_ERRORS 0x200000
+#define EXT2_FLAG_SHARE_DUP 0x400000
/*
* Special flag in the ext2 inode i_flag field that means that this is
@@ -295,6 +298,9 @@
blk64_t len, blk64_t *pblk, blk64_t *plen);
void (*block_alloc_stats_range)(ext2_filsys fs, blk64_t blk, blk_t num,
int inuse);
+
+ /* hashmap for SHA of data blocks */
+ struct ext2fs_hashmap* block_sha_map;
};
#if EXT2_FLAT_INCLUDES
@@ -614,7 +620,8 @@
EXT4_FEATURE_RO_COMPAT_QUOTA|\
EXT4_FEATURE_RO_COMPAT_METADATA_CSUM|\
EXT4_FEATURE_RO_COMPAT_READONLY |\
- EXT4_FEATURE_RO_COMPAT_PROJECT)
+ EXT4_FEATURE_RO_COMPAT_PROJECT |\
+ EXT4_FEATURE_RO_COMPAT_SHARED_BLOCKS)
/*
* These features are only allowed if EXT2_FLAG_SOFTSUPP_FEATURES is passed
diff --git a/lib/ext2fs/fileio.c b/lib/ext2fs/fileio.c
index 810a7fd..5bc02d0 100644
--- a/lib/ext2fs/fileio.c
+++ b/lib/ext2fs/fileio.c
@@ -32,6 +32,12 @@
char *buf;
};
+struct block_entry {
+ blk64_t physblock;
+ unsigned char sha[EXT2FS_SHA512_LENGTH];
+};
+typedef struct block_entry *block_entry_t;
+
#define BMAP_BUFFER (file->buf + fs->blocksize)
errcode_t ext2fs_file_open2(ext2_filsys fs, ext2_ino_t ino,
@@ -389,6 +395,8 @@
errcode_t retval = 0;
unsigned int start, c, count = 0;
const char *ptr = (const char *) buf;
+ block_entry_t new_block = NULL, old_block = NULL;
+ int bmap_flags = 0;
EXT2_CHECK_MAGIC(file, EXT2_ET_MAGIC_EXT2_FILE);
fs = file->fs;
@@ -424,22 +432,51 @@
if (retval)
goto fail;
+ file->flags |= EXT2_FILE_BUF_DIRTY;
+ memcpy(file->buf+start, ptr, c);
+
/*
* OK, the physical block hasn't been allocated yet.
* Allocate it.
*/
if (!file->physblock) {
+ bmap_flags = (file->ino ? BMAP_ALLOC : 0);
+ if (fs->flags & EXT2_FLAG_SHARE_DUP) {
+ new_block = calloc(1, sizeof(*new_block));
+ if (!new_block) {
+ retval = EXT2_ET_NO_MEMORY;
+ goto fail;
+ }
+ ext2fs_sha512((const unsigned char*)file->buf,
+ fs->blocksize, new_block->sha);
+ old_block = ext2fs_hashmap_lookup(
+ fs->block_sha_map,
+ new_block->sha,
+ sizeof(new_block->sha));
+ }
+
+ if (old_block) {
+ file->physblock = old_block->physblock;
+ bmap_flags |= BMAP_SET;
+ free(new_block);
+ new_block = NULL;
+ }
+
retval = ext2fs_bmap2(fs, file->ino, &file->inode,
BMAP_BUFFER,
- file->ino ? BMAP_ALLOC : 0,
+ bmap_flags,
file->blockno, 0,
&file->physblock);
if (retval)
goto fail;
+
+ if (new_block) {
+ new_block->physblock = file->physblock;
+ ext2fs_hashmap_add(fs->block_sha_map, new_block,
+ new_block->sha, sizeof(new_block->sha));
+ }
}
- file->flags |= EXT2_FILE_BUF_DIRTY;
- memcpy(file->buf+start, ptr, c);
file->pos += c;
ptr += c;
count += c;
diff --git a/lib/ext2fs/freefs.c b/lib/ext2fs/freefs.c
index ea9742e..68b8e9a 100644
--- a/lib/ext2fs/freefs.c
+++ b/lib/ext2fs/freefs.c
@@ -17,6 +17,7 @@
#include "ext2_fs.h"
#include "ext2fsP.h"
+#include "hashmap.h"
void ext2fs_free(ext2_filsys fs)
{
@@ -59,6 +60,9 @@
if (fs->mmp_cmp)
ext2fs_free_mem(&fs->mmp_cmp);
+ if (fs->block_sha_map)
+ ext2fs_hashmap_free(fs->block_sha_map);
+
fs->magic = 0;
ext2fs_zero_blocks2(NULL, 0, 0, NULL, NULL);
diff --git a/lib/ext2fs/hashmap.c b/lib/ext2fs/hashmap.c
new file mode 100644
index 0000000..ade5d89
--- /dev/null
+++ b/lib/ext2fs/hashmap.c
@@ -0,0 +1,83 @@
+#include "hashmap.h"
+#include <string.h>
+
+uint32_t ext2fs_djb2_hash(const void *str, size_t size)
+{
+ int c;
+ const char *s = str;
+ uint32_t hash = 5381;
+
+ while (size-- > 0) {
+ c = *s++;
+ hash = ((hash << 5) + hash) + c;
+ }
+ return hash;
+}
+
+struct ext2fs_hashmap *ext2fs_hashmap_create(
+ uint32_t(*hash_fct)(const void*, size_t),
+ void(*free_fct)(void*), size_t size)
+{
+ struct ext2fs_hashmap *h = calloc(sizeof(struct ext2fs_hashmap) +
+ sizeof(struct ext2fs_hashmap_entry) * size, 1);
+ h->size = size;
+ h->free = free_fct;
+ h->hash = hash_fct;
+ h->first = h->last = NULL;
+ return h;
+}
+
+void ext2fs_hashmap_add(struct ext2fs_hashmap *h, void *data, const void *key,
+ size_t key_len)
+{
+ uint32_t hash = h->hash(key, key_len) % h->size;
+ struct ext2fs_hashmap_entry *e = malloc(sizeof(*e));
+
+ e->data = data;
+ e->key = key;
+ e->key_len = key_len;
+ e->next = h->entries[hash];
+ h->entries[hash] = e;
+
+ e->list_prev = NULL;
+ e->list_next = h->first;
+ if (h->first)
+ h->first->list_prev = e;
+ h->first = e;
+ if (!h->last)
+ h->last = e;
+}
+
+void *ext2fs_hashmap_lookup(struct ext2fs_hashmap *h, const void *key,
+ size_t key_len)
+{
+ struct ext2fs_hashmap_entry *iter;
+ uint32_t hash = h->hash(key, key_len) % h->size;
+
+ for (iter = h->entries[hash]; iter; iter = iter->next)
+ if (iter->key_len == key_len && !memcmp(iter->key, key, key_len))
+ return iter->data;
+ return NULL;
+}
+
+void *ext2fs_hashmap_iter_in_order(struct ext2fs_hashmap *h,
+ struct ext2fs_hashmap_entry **it)
+{
+ *it = *it ? (*it)->list_next : h->first;
+ return *it ? (*it)->data : NULL;
+}
+
+void ext2fs_hashmap_free(struct ext2fs_hashmap *h)
+{
+ for (size_t i = 0; i < h->size; ++i) {
+ struct ext2fs_hashmap_entry *it = h->entries[i];
+ while (it) {
+ struct ext2fs_hashmap_entry *tmp = it->next;
+ if (h->free)
+ h->free(it->data);
+ free(it);
+ it = tmp;
+ }
+ }
+ free(h);
+}
diff --git a/lib/ext2fs/hashmap.h b/lib/ext2fs/hashmap.h
new file mode 100644
index 0000000..7127186
--- /dev/null
+++ b/lib/ext2fs/hashmap.h
@@ -0,0 +1,38 @@
+#ifndef HASHMAP_H
+# define HASHMAP_H
+
+# include <stdlib.h>
+# include <stdint.h>
+
+struct ext2fs_hashmap {
+ uint32_t size;
+ uint32_t(*hash)(const void *key, size_t len);
+ void(*free)(void*);
+ struct ext2fs_hashmap_entry *first;
+ struct ext2fs_hashmap_entry *last;
+ struct ext2fs_hashmap_entry {
+ void *data;
+ const void *key;
+ size_t key_len;
+ struct ext2fs_hashmap_entry *next;
+ struct ext2fs_hashmap_entry *list_next;
+ struct ext2fs_hashmap_entry *list_prev;
+ } *entries[0];
+};
+
+struct ext2fs_hashmap *ext2fs_hashmap_create(
+ uint32_t(*hash_fct)(const void*, size_t),
+ void(*free_fct)(void*), size_t size);
+void ext2fs_hashmap_add(struct ext2fs_hashmap *h, void *data, const void *key,
+ size_t key_len);
+void *ext2fs_hashmap_lookup(struct ext2fs_hashmap *h, const void *key,
+ size_t key_len);
+void *ext2fs_hashmap_iter_in_order(struct ext2fs_hashmap *h,
+ struct ext2fs_hashmap_entry **it);
+void ext2fs_hashmap_del(struct ext2fs_hashmap *h,
+ struct ext2fs_hashmap_entry *e);
+void ext2fs_hashmap_free(struct ext2fs_hashmap *h);
+
+uint32_t ext2fs_djb2_hash(const void *str, size_t size);
+
+#endif /* !HASHMAP_H */
diff --git a/lib/ext2fs/openfs.c b/lib/ext2fs/openfs.c
index 94d0ef1..43d68ad 100644
--- a/lib/ext2fs/openfs.c
+++ b/lib/ext2fs/openfs.c
@@ -94,6 +94,12 @@
manager, ret_fs);
}
+static void block_sha_map_free_entry(void *data)
+{
+ free(data);
+ return;
+}
+
/*
* Note: if superblock is non-zero, block-size must also be non-zero.
* Superblock and block_size can be zero to use the default size.
@@ -474,6 +480,16 @@
}
}
+ if (fs->flags & EXT2_FLAG_SHARE_DUP) {
+ fs->block_sha_map = ext2fs_hashmap_create(ext2fs_djb2_hash,
+ block_sha_map_free_entry, 4096);
+ if (!fs->block_sha_map) {
+ retval = EXT2_ET_NO_MEMORY;
+ goto cleanup;
+ }
+ ext2fs_set_feature_shared_blocks(fs->super);
+ }
+
fs->flags &= ~EXT2_FLAG_NOFREE_ON_ERROR;
*ret_fs = fs;
