[f2fs-dev] [PATCH 1/2] libf2fs_io: Add user-space cache
From: Robin Hsu
Implemented cache options in F2FS configuration 'c' (i.e. user
options):
* use c.cache_config.num_cache_entry to set the number of
cache entries (in block), minimum 1024, or 0 to disable cache.
* use c.cache_config.max_hash_collision to set maximum hash
collision (max 16).
* use c.cavhe_config.dbg_en to enable printing of debug messages.
Cache properties:
* Per block save based (block size = f2fs block size = 4K Bytes)
* Device block indices are used to hash (simple modular hash
function) to cache indices.
* A hash collision (when a block is hashed to an already occupied
cache block) will trigger offset-based relocation to max 16
other places, at first empty slot found policy.
* A hash collision with all 17 possible relocating places occupied
will evict the oldest used one (replaced by the new read block).
A global 'use' tick is kept ticking-up per block read for this
purpose.
* On write cache hit, it will update the corresponding cached
block.
* On write cache miss, the data won't be cached.
* Write-through policy only: never delayed write.
* On read cache hit, it returns the cached block.
* On read cache miss, it issues an I/O read to the kernel, and
then caches and returns the block.
* Currently read ahead is not implemented. Yet, the read ahead
logic is kept as before, i.e. using kernel's read ahead
mechanism.
Signed-off-by: Robin Hsu
Signed-off-by: Jaegeuk Kim
---
include/f2fs_fs.h | 18 +++
lib/libf2fs_io.c | 331 +-
2 files changed, 348 insertions(+), 1 deletion(-)
diff --git a/include/f2fs_fs.h b/include/f2fs_fs.h
index 84f3f3e..cb67c7e 100644
--- a/include/f2fs_fs.h
+++ b/include/f2fs_fs.h
@@ -3,6 +3,8 @@
*
* Copyright (c) 2012 Samsung Electronics Co., Ltd.
* http://www.samsung.com/
+ * Copyright (c) 2019 Google Inc.
+ * http://www.google.com/
*
* Dual licensed under the GPL or LGPL version 2 licenses.
*
@@ -329,6 +331,16 @@ struct device_info {
size_t zone_blocks;
};
+typedef struct {
+ /* Value 0 means no cache, minimum 1024 */
+ long num_cache_entry;
+
+ /* Value 0 means always overwrite (no collision allowed). maximum 16 */
+ unsigned max_hash_collision;
+
+ bool dbg_en;
+} dev_cache_config_t;
+
struct f2fs_configuration {
u_int32_t reserved_segments;
u_int32_t new_reserved_segments;
@@ -419,6 +431,9 @@ struct f2fs_configuration {
/* precomputed fs UUID checksum for seeding other checksums */
u_int32_t chksum_seed;
+
+ /* cache parameters */
+ dev_cache_config_t cache_config;
};
#ifdef CONFIG_64BIT
@@ -1185,6 +1200,9 @@ extern int f2fs_init_sparse_file(void);
extern int f2fs_finalize_device(void);
extern int f2fs_fsync_device(void);
+extern void dcache_init(void);
+extern void dcache_release(void);
+
extern int dev_read(void *, __u64, size_t);
#ifdef POSIX_FADV_WILLNEED
extern int dev_readahead(__u64, size_t);
diff --git a/lib/libf2fs_io.c b/lib/libf2fs_io.c
index 4d0ea0d..971ae37 100644
--- a/lib/libf2fs_io.c
+++ b/lib/libf2fs_io.c
@@ -3,6 +3,8 @@
*
* Copyright (c) 2013 Samsung Electronics Co., Ltd.
* http://www.samsung.com/
+ * Copyright (c) 2019 Google Inc.
+ * http://www.google.com/
*
* Dual licensed under the GPL or LGPL version 2 licenses.
*/
@@ -27,7 +29,10 @@
#include
#endif
-#include
+#include
+#include
+#include
+#include "f2fs_fs.h"
struct f2fs_configuration c;
@@ -64,6 +69,318 @@ static inline off64_t lseek64(int fd, __u64 offset, int set)
}
#endif
+/* -- dev_cache, Least Used First (LUF) policy --- */
+/*
+ * Least used block will be the first victim to be replaced when max hash
+ * collision exceeds
+ */
+static bool *dcache_valid; /* is the cached block valid? */
+static off64_t *dcache_blk; /* which block it cached */
+static uint64_t *dcache_lastused; /* last used ticks for cache entries */
+static char *dcache_buf; /* cached block data */
+static uint64_t dcache_usetick; /* current use tick */
+
+static uint64_t dcache_raccess;
+static uint64_t dcache_rhit;
+static uint64_t dcache_rmiss;
+static uint64_t dcache_rreplace;
+
+static bool dcache_exit_registered = false;
+
+/*
+ * Shadow config:
+ *
+ * Active set of the configurations.
+ * Global configuration 'dcache_config' will be transferred here when
+ * when dcache_init() is called
+ */
+static dev_cache_config_t dcache_config = {0, 16, 1};
+static bool dcache_initialized = false;
+
+#define MIN_NUM_CACHE_ENTRY 1024L
+#define MAX_MAX_HASH_COLLISION 16
+
+static long dcache_relocate_offset0[] = {
+ 20, -20, 40, -40, 80, -80, 160, -160,
+ 320, -320, 640, -640, 1280, -1280, 2560, -2560,
+};
+static int dcache_relocate_offset[16];
+
+static void dcache_print_statistics(void)
+{
+ long i;
+ long
Re: [f2fs-dev] [PATCH 1/2] libf2fs_io: Add user-space cache
Hi Robin,
Could you please address this build errors for mac build?
libf2fs_io.c:85:38: error: use of undeclared identifier 'false'
static bool dcache_exit_registered = false;
^
libf2fs_io.c:95:34: error: use of undeclared identifier 'false'
static bool dcache_initialized = false;
^
libf2fs_io.c:127:4: warning: format specifies type 'unsigned long' but the
argument has type 'off64_t' (aka 'long long') [-Wformat]
dcache_config.num_cache_entry,
^
libf2fs_io.c:128:4: warning: format specifies type 'unsigned long' but the
argument has type 'off64_t' (aka 'long long') [-Wformat]
useCnt,
^~
libf2fs_io.c:129:4: warning: format specifies type 'long' but the argument has
type 'int64_t' (aka 'long long') [-Wformat]
dcache_raccess,
^~
libf2fs_io.c:130:4: warning: format specifies type 'long' but the argument has
type 'int64_t' (aka 'long long') [-Wformat]
dcache_rhit,
^~~
libf2fs_io.c:131:4: warning: format specifies type 'long' but the argument has
type 'int64_t' (aka 'long long') [-Wformat]
dcache_rmiss,
^~~~
libf2fs_io.c:132:4: warning: format specifies type 'long' but the argument has
type 'int64_t' (aka 'long long') [-Wformat]
dcache_rreplace);
^~~
libf2fs_io.c:140:23: error: use of undeclared identifier 'false'
dcache_initialized = false;
^
libf2fs_io.c:222:23: error: use of undeclared identifier 'true'
dcache_initialized = true;
^
libf2fs_io.c:225:28: error: use of undeclared identifier 'true'
dcache_exit_registered = true;
^
libf2fs_io.c:273:24: error: use of undeclared identifier 'true'
dcache_valid[entry] = true;
^
libf2fs_io.c:363:50: error: use of undeclared identifier 'true'
return dcache_update_rw(fd, buf, offset, count, true);
^
libf2fs_io.c:369:50: error: use of undeclared identifier 'false'
return dcache_update_rw(fd, buf, offset, count, false);
On 10/29, Robin Hsu wrote:
> Implemented cache options in F2FS configuration 'c':
> * use c.cache_config.num_cache_entry to set the number of
> cache entries (in block), minimum 1024, or 0 to disable cache.
> * use c.cache_config.max_hash_collision to set maximum hash
> collision (max 16).
> * use c.cache_config.dbg_en to enable printing of debug messages.
>
> Signed-off-by: Robin Hsu
> ---
> include/f2fs_fs.h | 20 +++
> lib/libf2fs_io.c | 317 ++
> 2 files changed, 337 insertions(+)
>
> diff --git a/include/f2fs_fs.h b/include/f2fs_fs.h
> index 84f3f3e..a386e61 100644
> --- a/include/f2fs_fs.h
> +++ b/include/f2fs_fs.h
> @@ -3,6 +3,8 @@
> *
> * Copyright (c) 2012 Samsung Electronics Co., Ltd.
> * http://www.samsung.com/
> + * Copyright (c) 2019 Google Inc.
> + * http://www.google.com/
> *
> * Dual licensed under the GPL or LGPL version 2 licenses.
> *
> @@ -329,6 +331,18 @@ struct device_info {
> size_t zone_blocks;
> };
>
> +typedef off_toff64_t;
> +
> +typedef struct {
> + /* Value 0 means no cache, minimum 1024 */
> + off64_t num_cache_entry;
> +
> + /* Value 0 means always overwrite (no collision allowed). maximum 16 */
> + unsigned max_hash_collision;
> +
> + bool dbg_en;
> +} dev_cache_config_t;
> +
> struct f2fs_configuration {
> u_int32_t reserved_segments;
> u_int32_t new_reserved_segments;
> @@ -419,6 +433,9 @@ struct f2fs_configuration {
>
> /* precomputed fs UUID checksum for seeding other checksums */
> u_int32_t chksum_seed;
> +
> + /* cache parameters */
> + dev_cache_config_t cache_config;
> };
>
> #ifdef CONFIG_64BIT
> @@ -1185,6 +1202,9 @@ extern int f2fs_init_sparse_file(void);
> extern int f2fs_finalize_device(void);
> extern int f2fs_fsync_device(void);
>
> +extern void dcache_init(void);
> +extern void dcache_release(void);
> +
> extern int dev_read(void *, __u64, size_t);
> #ifdef POSIX_FADV_WILLNEED
> extern int dev_readahead(__u64, size_t);
> diff --git a/lib/libf2fs_io.c b/lib/libf2fs_io.c
> index 4d0ea0d..4888b6e 100644
> --- a/lib/libf2fs_io.c
> +++ b/lib/libf2fs_io.c
> @@ -3,6 +3,8 @@
> *
> * Copyright (c) 2013 Samsung Electronics Co., Ltd.
> * http://www.samsung.com/
> + * Copyright (c) 2019 Google Inc.
> + * http://www.google.com/
> *
> * Dual licensed under the GPL or LGPL version 2 licenses.
> */
> @@ -64,6 +66,309 @@
[f2fs-dev] [PATCH 1/2] libf2fs_io: Add user-space cache
Implemented cache options in F2FS configuration 'c':
* use c.cache_config.num_cache_entry to set the number of
cache entries (in block), minimum 1024, or 0 to disable cache.
* use c.cache_config.max_hash_collision to set maximum hash
collision (max 16).
* use c.cache_config.dbg_en to enable printing of debug messages.
Signed-off-by: Robin Hsu
---
include/f2fs_fs.h | 20 +++
lib/libf2fs_io.c | 317 ++
2 files changed, 337 insertions(+)
diff --git a/include/f2fs_fs.h b/include/f2fs_fs.h
index 84f3f3e..a386e61 100644
--- a/include/f2fs_fs.h
+++ b/include/f2fs_fs.h
@@ -3,6 +3,8 @@
*
* Copyright (c) 2012 Samsung Electronics Co., Ltd.
* http://www.samsung.com/
+ * Copyright (c) 2019 Google Inc.
+ * http://www.google.com/
*
* Dual licensed under the GPL or LGPL version 2 licenses.
*
@@ -329,6 +331,18 @@ struct device_info {
size_t zone_blocks;
};
+typedef off_t off64_t;
+
+typedef struct {
+ /* Value 0 means no cache, minimum 1024 */
+ off64_t num_cache_entry;
+
+ /* Value 0 means always overwrite (no collision allowed). maximum 16 */
+ unsigned max_hash_collision;
+
+ bool dbg_en;
+} dev_cache_config_t;
+
struct f2fs_configuration {
u_int32_t reserved_segments;
u_int32_t new_reserved_segments;
@@ -419,6 +433,9 @@ struct f2fs_configuration {
/* precomputed fs UUID checksum for seeding other checksums */
u_int32_t chksum_seed;
+
+ /* cache parameters */
+ dev_cache_config_t cache_config;
};
#ifdef CONFIG_64BIT
@@ -1185,6 +1202,9 @@ extern int f2fs_init_sparse_file(void);
extern int f2fs_finalize_device(void);
extern int f2fs_fsync_device(void);
+extern void dcache_init(void);
+extern void dcache_release(void);
+
extern int dev_read(void *, __u64, size_t);
#ifdef POSIX_FADV_WILLNEED
extern int dev_readahead(__u64, size_t);
diff --git a/lib/libf2fs_io.c b/lib/libf2fs_io.c
index 4d0ea0d..4888b6e 100644
--- a/lib/libf2fs_io.c
+++ b/lib/libf2fs_io.c
@@ -3,6 +3,8 @@
*
* Copyright (c) 2013 Samsung Electronics Co., Ltd.
* http://www.samsung.com/
+ * Copyright (c) 2019 Google Inc.
+ * http://www.google.com/
*
* Dual licensed under the GPL or LGPL version 2 licenses.
*/
@@ -64,6 +66,309 @@ static inline off64_t lseek64(int fd, __u64 offset, int set)
}
#endif
+/* -- dev_cache, Least Used First (LUF) policy --- */
+/*
+ * Least used block will be the first victim to be replaced when max hash
+ * collision exceeds
+ */
+static bool *dcache_valid; /* is the cached block valid? */
+static off64_t *dcache_blk; /* which block it cached */
+static uint64_t *dcache_lastused; /* last used ticks for cache entries */
+static char *dcache_buf; /* cached block data */
+static uint64_t dcache_usetick; /* current use tick */
+
+static int64_t dcache_raccess;
+static int64_t dcache_rhit;
+static int64_t dcache_rmiss;
+static int64_t dcache_rreplace;
+
+static bool dcache_exit_registered = false;
+
+/*
+ * Shadow config:
+ *
+ * Active set of the configurations.
+ * Global configuration 'dcache_config' will be transferred here when
+ * when dcache_init() is called
+ */
+static dev_cache_config_t dcache_config = {0, 16, 1};
+static bool dcache_initialized = false;
+
+#define MIN_NUM_CACHE_ENTRY ((off64_t)1024)
+#define MAX_MAX_HASH_COLLISION 16
+
+static int dcache_relocate_offset0[] = {
+ 20, -20, 40, -40, 80, -80, 160, -160,
+ 320, -320, 640, -640, 1280, -1280, 2560, -2560,
+};
+static int dcache_relocate_offset[16];
+
+static void dcache_print_statistics(void)
+{
+ off64_t i;
+ off64_t useCnt;
+
+ /* Number of used cache entries */
+ useCnt = 0;
+ for (i = 0; i < dcache_config.num_cache_entry; i++)
+ if (dcache_valid[i])
+ ++useCnt;
+
+ /*
+* c: number of cache entries
+* u: used entries
+* RA: number of read access blocks
+* CH: cache hit
+* CM: cache miss
+* Repl: read cache replaced
+*/
+ printf ("\nc, u, RA, CH, CM, Repl=\n");
+ printf ("%lu %lu %ld %ld %ld %ld\n",
+ dcache_config.num_cache_entry,
+ useCnt,
+ dcache_raccess,
+ dcache_rhit,
+ dcache_rmiss,
+ dcache_rreplace);
+}
+
+void dcache_release(void)
+{
+ if (!dcache_initialized)
+ return;
+
+ dcache_initialized = false;
+
+ if (c.cache_config.dbg_en)
+ dcache_print_statistics();
+
+ if (dcache_blk != NULL)
+ free(dcache_blk);
+ if (dcache_lastused != NULL)
+ free(dcache_lastused);
+ if (dcache_buf != NULL)
+ free(dcache_buf);
+ if (dcache_valid != NULL)
+
