Linux-f2fs-devel Archive on lore.kernel.org
 help / color / Atom feed
* [f2fs-dev] [PATCH 1/2] libf2fs_io: Add user-space cache
@ 2019-11-23  0:44 Jaegeuk Kim
  2019-11-23  0:44 ` [f2fs-dev] [PATCH 2/2] fsck.f2fs: Enable " Jaegeuk Kim
  0 siblings, 1 reply; 4+ messages in thread
From: Jaegeuk Kim @ 2019-11-23  0:44 UTC (permalink / raw)
  To: linux-f2fs-devel; +Cc: Jaegeuk Kim

From: Robin Hsu <robinhsu@google.com>

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 <robinhsu@google.com>
Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
---
 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 <linux/hdreg.h>
 #endif
 
-#include <f2fs_fs.h>
+#include <stdbool.h>
+#include <assert.h>
+#include <inttypes.h>
+#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 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 ("%ld %ld %" PRIu64 " %" PRIu64 " %" PRIu64 " %" PRIu64 "\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)
+		free(dcache_valid);
+	dcache_config.num_cache_entry = 0;
+	dcache_blk = NULL;
+	dcache_lastused = NULL;
+	dcache_buf = NULL;
+	dcache_valid = NULL;
+}
+
+// return 0 for success, error code for failure.
+static int dcache_alloc_all(long n)
+{
+	if (n <= 0)
+		return -1;
+	if ((dcache_blk = (off64_t *) malloc(sizeof(off64_t) * n)) == NULL
+		|| (dcache_lastused = (uint64_t *)
+				malloc(sizeof(uint64_t) * n)) == NULL
+		|| (dcache_buf = (char *) malloc (F2FS_BLKSIZE * n)) == NULL
+		|| (dcache_valid = (bool *) malloc(sizeof(bool) * n)) == NULL)
+	{
+		dcache_release();
+		return -1;
+	}
+	dcache_config.num_cache_entry = n;
+	return 0;
+}
+
+static void dcache_relocate_init(void)
+{
+	int i;
+	int n0 = (sizeof(dcache_relocate_offset0)
+			/ sizeof(dcache_relocate_offset0[0]));
+	int n = (sizeof(dcache_relocate_offset)
+			/ sizeof(dcache_relocate_offset[0]));
+
+	ASSERT(n == n0);
+	for (i = 0; i < n && i < dcache_config.max_hash_collision; i++) {
+		if (labs(dcache_relocate_offset0[i])
+				> dcache_config.num_cache_entry / 2) {
+			dcache_config.max_hash_collision = i;
+			break;
+		}
+		dcache_relocate_offset[i] =
+				dcache_config.num_cache_entry
+				+ dcache_relocate_offset0[i];
+	}
+}
+
+void dcache_init(void)
+{
+	long n;
+
+	if (c.cache_config.num_cache_entry <= 0)
+		return;
+
+	/* release previous cache init, if any */
+	dcache_release();
+
+	dcache_blk = NULL;
+	dcache_lastused = NULL;
+	dcache_buf = NULL;
+	dcache_valid = NULL;
+
+	dcache_config = c.cache_config;
+
+	n = max(MIN_NUM_CACHE_ENTRY, dcache_config.num_cache_entry);
+
+	/* halve alloc size until alloc succeed, or min cache reached */
+	while (dcache_alloc_all(n) != 0 && n !=  MIN_NUM_CACHE_ENTRY)
+		n = max(MIN_NUM_CACHE_ENTRY, n/2);
+
+	/* must be the last: data dependent on num_cache_entry */
+	dcache_relocate_init();
+	dcache_initialized = true;
+
+	if (!dcache_exit_registered) {
+		dcache_exit_registered = true;
+		atexit(dcache_release); /* auto release */
+	}
+
+	dcache_raccess = 0;
+	dcache_rhit = 0;
+	dcache_rmiss = 0;
+	dcache_rreplace = 0;
+}
+
+static inline char *dcache_addr(long entry)
+{
+	return dcache_buf + F2FS_BLKSIZE * entry;
+}
+
+/* relocate on (n+1)-th collision */
+static inline long dcache_relocate(long entry, int n)
+{
+	assert(dcache_config.num_cache_entry != 0);
+	return (entry + dcache_relocate_offset[n]) %
+			dcache_config.num_cache_entry;
+}
+
+static long dcache_find(off64_t blk)
+{
+	register long n = dcache_config.num_cache_entry;
+	register unsigned m = dcache_config.max_hash_collision;
+	long entry, least_used, target;
+	unsigned try;
+
+	assert(n > 0);
+	target = least_used = entry = blk % n; /* simple modulo hash */
+
+	for (try = 0; try < m; try++) {
+		if (!dcache_valid[target] || dcache_blk[target] == blk)
+			return target;  /* found target or empty cache slot */
+		if (dcache_lastused[target] < dcache_lastused[least_used])
+			least_used = target;
+		target = dcache_relocate(entry, try); /* next target */
+	}
+	return least_used;  /* max search reached, return least used slot */
+}
+
+/* Physical read into cache */
+static int dcache_io_read(int fd, long entry, off64_t offset, off64_t blk)
+{
+	if (lseek64(fd, offset, SEEK_SET) < 0) {
+		MSG(0, "\n lseek64 fail.\n");
+		return -1;
+	}
+	if (read(fd, dcache_buf + entry * F2FS_BLKSIZE, F2FS_BLKSIZE) < 0) {
+		MSG(0, "\n read() fail.\n");
+		return -1;
+	}
+	dcache_lastused[entry] = ++dcache_usetick;
+	dcache_valid[entry] = true;
+	dcache_blk[entry] = blk;
+	return 0;
+}
+
+/*
+ *  - Note: Read/Write are not symmetric:
+ *       For read, we need to do it block by block, due to the cache nature:
+ *           some blocks may be cached, and others don't.
+ *       For write, since we always do a write-thru, we can join all writes into one,
+ *       and write it once at the caller.  This function updates the cache for write, but
+ *       not the do a physical write.  The caller is responsible for the physical write.
+ *  - Note: We concentrate read/write together, due to the fact of similar structure to find
+ *          the relavant cache entries
+ *  - Return values:
+ *       0: success
+ *       1: cache not available (uninitialized)
+ *      -1: error
+ */
+static int dcache_update_rw(int fd, void *buf, off64_t offset,
+		size_t byte_count, bool is_write)
+{
+	off64_t blk;
+	int addr_in_blk;
+	off64_t start;
+
+	if (!dcache_initialized)
+		dcache_init(); /* auto initialize */
+
+	if (!dcache_initialized)
+		return 1; /* not available */
+
+	blk = offset / F2FS_BLKSIZE;
+	addr_in_blk = offset % F2FS_BLKSIZE;
+	start = blk * F2FS_BLKSIZE;
+
+	while (byte_count != 0) {
+		size_t cur_size = min(byte_count,
+				(size_t)(F2FS_BLKSIZE - addr_in_blk));
+		long entry = dcache_find(blk);
+
+		if (!is_write)
+			++dcache_raccess;
+
+		if (dcache_valid[entry] && dcache_blk[entry] == blk) {
+			/* cache hit */
+			if (is_write)  /* write: update cache */
+				memcpy(dcache_addr(entry) + addr_in_blk,
+					buf, cur_size);
+			else
+				++dcache_rhit;
+		} else {
+			/* cache miss */
+			if (!is_write) {
+				int err;
+				++dcache_rmiss;
+				if (dcache_valid[entry])
+					++dcache_rreplace;
+				/* read: physical I/O read into cache */
+				err = dcache_io_read(fd, entry, start, blk);
+				if (err)
+					return err;
+			}
+		}
+
+		/* read: copy data from cache */
+		/* write: nothing to do, since we don't do physical write. */
+		if (!is_write)
+			memcpy(buf, dcache_addr(entry) + addr_in_blk,
+				cur_size);
+
+		/* next block */
+		++blk;
+		buf += cur_size;
+		offset += F2FS_BLKSIZE;
+		byte_count -= cur_size;
+		addr_in_blk = 0;
+	}
+	return 0;
+}
+
+/*
+ * dcache_update_cache() just update cache, won't do physical I/O.
+ * Thus even no error, we need normal non-cache I/O for actual write
+ *
+ * return value: 1: cache not available
+ *               0: success, -1: I/O error
+ */
+inline int dcache_update_cache(int fd, void *buf, off64_t offset, size_t count)
+{
+	return dcache_update_rw(fd, buf, offset, count, true);
+}
+
+/* handles read into cache + read into buffer  */
+inline int dcache_read(int fd, void *buf, off64_t offset, size_t count)
+{
+	return dcache_update_rw(fd, buf, offset, count, false);
+}
+
 /*
  * IO interfaces
  */
@@ -185,6 +502,7 @@ static int sparse_write_zeroed_blk(__u64 block, int count) { return 0; }
 int dev_read(void *buf, __u64 offset, size_t len)
 {
 	int fd;
+	int err;
 
 	if (c.sparse_mode)
 		return sparse_read_blk(offset / F2FS_BLKSIZE,
@@ -194,6 +512,11 @@ int dev_read(void *buf, __u64 offset, size_t len)
 	if (fd < 0)
 		return fd;
 
+	/* err = 1: cache not available, fall back to non-cache R/W */
+	/* err = 0: success, err=-1: I/O error */
+	err = dcache_read(fd, buf, (off64_t)offset, len);
+	if (err <= 0)
+		return err;
 	if (lseek64(fd, (off64_t)offset, SEEK_SET) < 0)
 		return -1;
 	if (read(fd, buf, len) < 0)
@@ -233,6 +556,12 @@ int dev_write(void *buf, __u64 offset, size_t len)
 	if (fd < 0)
 		return fd;
 
+	/*
+	 * dcache_update_cache() just update cache, won't do I/O.
+	 * Thus even no error, we need normal non-cache I/O for actual write
+	 */
+	if (dcache_update_cache(fd, buf, (off64_t)offset, len) < 0)
+		return -1;
 	if (lseek64(fd, (off64_t)offset, SEEK_SET) < 0)
 		return -1;
 	if (write(fd, buf, len) < 0)
-- 
2.19.0.605.g01d371f741-goog



_______________________________________________
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

^ permalink raw reply	[flat|nested] 4+ messages in thread

* [f2fs-dev] [PATCH 2/2] fsck.f2fs: Enable user-space cache
  2019-11-23  0:44 [f2fs-dev] [PATCH 1/2] libf2fs_io: Add user-space cache Jaegeuk Kim
@ 2019-11-23  0:44 ` " Jaegeuk Kim
  0 siblings, 0 replies; 4+ messages in thread
From: Jaegeuk Kim @ 2019-11-23  0:44 UTC (permalink / raw)
  To: linux-f2fs-devel; +Cc: Jaegeuk Kim

From: Robin Hsu <robinhsu@google.com>

Added command line options -c <num_cache_entry> and -m <max_hash_collision>
to activate cache for fsck.  It may significantly speed up fsck.

Signed-off-by: Robin Hsu <robinhsu@google.com>
Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
---
 fsck/main.c | 27 +++++++++++++++++++++++++--
 1 file changed, 25 insertions(+), 2 deletions(-)

diff --git a/fsck/main.c b/fsck/main.c
index 8c62a14..8edb177 100644
--- a/fsck/main.c
+++ b/fsck/main.c
@@ -10,6 +10,9 @@
  *   Liu Shuoran <liushuoran@huawei.com>
  *   Jaegeuk Kim <jaegeuk@kernel.org>
  *  : add sload.f2fs
+ * Copyright (c) 2019 Google Inc.
+ *   Robin Hsu <robinhsu@google.com>
+ *  : add cache layer
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 2 as
@@ -20,6 +23,7 @@
 #include <ctype.h>
 #include <time.h>
 #include <getopt.h>
+#include <stdbool.h>
 #include "quotaio.h"
 
 struct f2fs_fsck gfsck;
@@ -54,7 +58,12 @@ void fsck_usage()
 	MSG(0, "\nUsage: fsck.f2fs [options] device\n");
 	MSG(0, "[options]:\n");
 	MSG(0, "  -a check/fix potential corruption, reported by f2fs\n");
-	MSG(0, "  -C encoding[:flag1,flag2] Set options for enabling casefolding\n");
+	MSG(0, "  -c <num-cache-entry>  set number of cache entries"
+			" (default 0)\n");
+	MSG(0, "  -m <max-hash-collision>  set max cache hash collision"
+			" (default 16)\n");
+	MSG(0, "  -C encoding[:flag1,flag2] Set options for enabling"
+			" casefolding\n");
 	MSG(0, "  -d debug level [default:0]\n");
 	MSG(0, "  -f check/fix entire partition\n");
 	MSG(0, "  -g add default options\n");
@@ -66,6 +75,7 @@ void fsck_usage()
 	MSG(0, "  -y fix all the time\n");
 	MSG(0, "  -V print the version number and exit\n");
 	MSG(0, "  --dry-run do not really fix corruptions\n");
+	MSG(0, "  --debug-cache to debug cache when -c is used\n");
 	exit(1);
 }
 
@@ -187,15 +197,18 @@ void f2fs_parse_options(int argc, char *argv[])
 	}
 
 	if (!strcmp("fsck.f2fs", prog)) {
-		const char *option_string = ":aC:d:fg:O:p:q:StyV";
+		const char *option_string = ":aC:c:m:d:fg:O:p:q:StyV";
 		int opt = 0, val;
 		char *token;
 		struct option long_opt[] = {
 			{"dry-run", no_argument, 0, 1},
+			{"debug-cache", no_argument, 0, 2},
 			{0, 0, 0, 0}
 		};
 
 		c.func = FSCK;
+		c.cache_config.max_hash_collision = 16;
+		c.cache_config.dbg_en = false;
 		while ((option = getopt_long(argc, argv, option_string,
 						long_opt, &opt)) != EOF) {
 			switch (option) {
@@ -203,10 +216,20 @@ void f2fs_parse_options(int argc, char *argv[])
 				c.dry_run = 1;
 				MSG(0, "Info: Dry run\n");
 				break;
+			case 2:
+				c.cache_config.dbg_en = true;
+				break;
 			case 'a':
 				c.auto_fix = 1;
 				MSG(0, "Info: Fix the reported corruption.\n");
 				break;
+			case 'c':
+				c.cache_config.num_cache_entry = atoi(optarg);
+				break;
+			case 'm':
+				c.cache_config.max_hash_collision =
+						atoi(optarg);
+				break;
 			case 'g':
 				if (!strcmp(optarg, "android"))
 					c.defset = CONF_ANDROID;
-- 
2.19.0.605.g01d371f741-goog



_______________________________________________
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [f2fs-dev] [PATCH 1/2] libf2fs_io: Add user-space cache
  2019-10-29  7:47 [f2fs-dev] [PATCH 1/2] libf2fs_io: Add " Robin Hsu via Linux-f2fs-devel
@ 2019-10-30 16:46 ` Jaegeuk Kim
  0 siblings, 0 replies; 4+ messages in thread
From: Jaegeuk Kim @ 2019-10-30 16:46 UTC (permalink / raw)
  To: Robin Hsu; +Cc: linux-kernel, linux-f2fs-devel

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 <robinhsu@google.com>
> ---
>  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)
> +		free(dcache_valid);
> +	dcache_config.num_cache_entry = 0;
> +	dcache_blk = NULL;
> +	dcache_lastused = NULL;
> +	dcache_buf = NULL;
> +	dcache_valid = NULL;
> +}
> +
> +// return 0 for success, error code for failure.
> +static int dcache_alloc_all(int n)
> +{
> +	if ((dcache_blk = (off64_t *) malloc(sizeof(off64_t) * n)) == NULL
> +		|| (dcache_lastused = (uint64_t *)
> +				malloc(sizeof(uint64_t) * n)) == NULL
> +		|| (dcache_buf = (char *) malloc (F2FS_BLKSIZE * n)) == NULL
> +		|| (dcache_valid = (bool *) malloc(sizeof(bool) * n)) == NULL)
> +	{
> +		dcache_release();
> +		return -1;
> +	}
> +	dcache_config.num_cache_entry = n;
> +	return 0;
> +}
> +
> +static void dcache_relocate_init(void)
> +{
> +	int i;
> +	int n0 = (sizeof(dcache_relocate_offset0)
> +			/ sizeof(dcache_relocate_offset0[0]));
> +	int n = (sizeof(dcache_relocate_offset)
> +			/ sizeof(dcache_relocate_offset[0]));
> +
> +	ASSERT(n == n0);
> +	for (i = 0; i < n && i < dcache_config.max_hash_collision; i++) {
> +		if (abs(dcache_relocate_offset0[i])
> +				> dcache_config.num_cache_entry / 2) {
> +			dcache_config.max_hash_collision = i;
> +			break;
> +		}
> +		dcache_relocate_offset[i] =
> +				dcache_config.num_cache_entry
> +				+ dcache_relocate_offset0[i];
> +	}
> +}
> +
> +void dcache_init(void)
> +{
> +	off64_t n;
> +
> +	if (c.cache_config.num_cache_entry == 0)
> +		return;
> +
> +	/* release previous cache init, if any */
> +	dcache_release();
> +
> +	dcache_blk = NULL;
> +	dcache_lastused = NULL;
> +	dcache_buf = NULL;
> +	dcache_valid = NULL;
> +
> +	dcache_config = c.cache_config;
> +
> +	n = max(MIN_NUM_CACHE_ENTRY, dcache_config.num_cache_entry);
> +
> +	/* halve alloc size until alloc succeed, or min cache reached */
> +	while (dcache_alloc_all(n) != 0 && n !=  MIN_NUM_CACHE_ENTRY)
> +		n = max(MIN_NUM_CACHE_ENTRY, n/2);
> +
> +	/* must be the last: data dependent on num_cache_entry */
> +	dcache_relocate_init();
> +	dcache_initialized = true;
> +
> +	if (!dcache_exit_registered) {
> +		dcache_exit_registered = true;
> +		atexit(dcache_release); /* auto release */
> +	}
> +}
> +
> +static inline char *dcache_addr(off64_t entry)
> +{
> +	return dcache_buf + F2FS_BLKSIZE * entry;
> +}
> +
> +/* relocate on (n+1)-th collision */
> +static inline off64_t dcache_relocate(off64_t entry, int n)
> +{
> +	return (entry + dcache_relocate_offset[n]) %
> +			dcache_config.num_cache_entry;
> +}
> +
> +static off64_t dcache_find(off64_t blk)
> +{
> +	register off64_t n = dcache_config.num_cache_entry;
> +	register unsigned m = dcache_config.max_hash_collision;
> +	off64_t entry, least_used, target;
> +	unsigned try;
> +
> +	target = least_used = entry = blk % n;
> +
> +	for (try = 0; try < m; try++) {
> +		if (!dcache_valid[target] || dcache_blk[target] == blk)
> +			return target;  /* found target or empty cache slot */
> +		if (dcache_lastused[target] < dcache_lastused[least_used])
> +			least_used = target;
> +		target = dcache_relocate(entry, try); /* next target */
> +	}
> +	return least_used;  /* max search reached, return least used slot */
> +}
> +
> +/* Physical read into cache */
> +static int dcache_io_read(int fd, off64_t entry, off64_t offset, off64_t blk)
> +{
> +	if (lseek64(fd, (off64_t)offset, SEEK_SET) < 0) {
> +		MSG(0, "\n lseek64 fail.\n");
> +		return -1;
> +	}
> +	if (read(fd, dcache_buf + entry * F2FS_BLKSIZE, F2FS_BLKSIZE) < 0) {
> +		MSG(0, "\n read() fail.\n");
> +		return -1;
> +	}
> +	dcache_lastused[entry] = ++dcache_usetick;
> +	dcache_valid[entry] = true;
> +	dcache_blk[entry] = blk;
> +	return 0;
> +}
> +
> +/*
> + *  - Note: Read/Write are not symmetric:
> + *       For read, we need to do it block by block, due to the cache nature:
> + *           some blocks may be cached, and others don't.
> + *       For write, since we always do a write-thru, we can join all writes into one,
> + *       and write it once at the caller.  This function updates the cache for write, but
> + *       not the do a physical write.  The caller is responsible for the physical write.
> + *  - Note: We concentrate read/write together, due to the fact of similar structure to find
> + *          the relevant cache entries
> + *  - Return values:
> + *       0: success
> + *       1: cache not available (uninitialized)
> + *      -1: error
> + */
> +static int dcache_update_rw(int fd, void *buf, off64_t offset,
> +		size_t byte_count, bool is_write)
> +{
> +	off64_t blk;
> +	int32_t addr_in_blk;
> +	off64_t start;
> +
> +	if (!dcache_initialized)
> +		dcache_init(); /* auto initialize */
> +
> +	if (!dcache_initialized)
> +		return 1; /* not available */
> +
> +	blk = offset / F2FS_BLKSIZE;
> +	addr_in_blk = offset % F2FS_BLKSIZE;
> +	start = blk * F2FS_BLKSIZE;
> +
> +	while (byte_count != 0) {
> +		int32_t cur_size = min(byte_count,
> +				(size_t)(F2FS_BLKSIZE - addr_in_blk));
> +		off64_t entry = dcache_find(blk);
> +
> +		if (!is_write)
> +			++dcache_raccess;
> +
> +		if (dcache_valid[entry] && dcache_blk[entry] == blk) {
> +			/* cache hit */
> +			if (is_write)  /* write: update cache */
> +				memcpy(dcache_addr(entry) + addr_in_blk,
> +					buf, cur_size);
> +			else
> +				++dcache_rhit;
> +		} else {
> +			/* cache miss */
> +			if (!is_write) {
> +				int err;
> +				++dcache_rmiss;
> +				if (dcache_valid[entry])
> +					++dcache_rreplace;
> +				/* read: physical I/O read into cache */
> +				err = dcache_io_read(fd, entry, start, blk);
> +				if (err)
> +					return err;
> +			}
> +		}
> +
> +		/* read: copy data from cache */
> +		/* write: nothing to do, since we don't do physical write. */
> +		if (!is_write)
> +			memcpy(buf, dcache_addr(entry) + addr_in_blk,
> +				cur_size);
> +
> +		/* next block */
> +		++blk;
> +		buf += cur_size;
> +		offset += F2FS_BLKSIZE;
> +		byte_count -= cur_size;
> +		addr_in_blk = 0;
> +	}
> +	return 0;
> +}
> +
> +/*
> + * dcache_update_cache() just update cache, won't do physical I/O.
> + * Thus even no error, we need normal non-cache I/O for actual write
> + *
> + * return value: 1: cache not available
> + *               0: success, -1: I/O error
> + */
> +inline int dcache_update_cache(int fd, void *buf, off64_t offset, size_t count)
> +{
> +	return dcache_update_rw(fd, buf, offset, count, true);
> +}
> +
> +/* handles read into cache + read into buffer  */
> +inline int dcache_read(int fd, void *buf, off64_t offset, size_t count)
> +{
> +	return dcache_update_rw(fd, buf, offset, count, false);
> +}
> +
>  /*
>   * IO interfaces
>   */
> @@ -185,6 +490,7 @@ static int sparse_write_zeroed_blk(__u64 block, int count) { return 0; }
>  int dev_read(void *buf, __u64 offset, size_t len)
>  {
>  	int fd;
> +	int err;
>  
>  	if (c.sparse_mode)
>  		return sparse_read_blk(offset / F2FS_BLKSIZE,
> @@ -194,6 +500,11 @@ int dev_read(void *buf, __u64 offset, size_t len)
>  	if (fd < 0)
>  		return fd;
>  
> +	/* err = 1: cache not available, fall back to non-cache R/W */
> +	/* err = 0: success, err=-1: I/O error */
> +	err = dcache_read(fd, buf, (off64_t)offset, len);
> +	if (err <= 0)
> +		return err;
>  	if (lseek64(fd, (off64_t)offset, SEEK_SET) < 0)
>  		return -1;
>  	if (read(fd, buf, len) < 0)
> @@ -233,6 +544,12 @@ int dev_write(void *buf, __u64 offset, size_t len)
>  	if (fd < 0)
>  		return fd;
>  
> +	/*
> +	 * dcache_update_cache() just update cache, won't do I/O.
> +	 * Thus even no error, we need normal non-cache I/O for actual write
> +	 */
> +	if (dcache_update_cache(fd, buf, (off64_t)offset, len) < 0)
> +		return -1;
>  	if (lseek64(fd, (off64_t)offset, SEEK_SET) < 0)
>  		return -1;
>  	if (write(fd, buf, len) < 0)
> -- 
> 2.24.0.rc0.303.g954a862665-goog


_______________________________________________
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

^ permalink raw reply	[flat|nested] 4+ messages in thread

* [f2fs-dev] [PATCH 1/2] libf2fs_io: Add user-space cache
@ 2019-10-29  7:47 " Robin Hsu via Linux-f2fs-devel
  2019-10-30 16:46 ` Jaegeuk Kim
  0 siblings, 1 reply; 4+ messages in thread
From: Robin Hsu via Linux-f2fs-devel @ 2019-10-29  7:47 UTC (permalink / raw)
  To: jaegeuk, yuchao0, linux-f2fs-devel, linux-kernel

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 <robinhsu@google.com>
---
 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)
+		free(dcache_valid);
+	dcache_config.num_cache_entry = 0;
+	dcache_blk = NULL;
+	dcache_lastused = NULL;
+	dcache_buf = NULL;
+	dcache_valid = NULL;
+}
+
+// return 0 for success, error code for failure.
+static int dcache_alloc_all(int n)
+{
+	if ((dcache_blk = (off64_t *) malloc(sizeof(off64_t) * n)) == NULL
+		|| (dcache_lastused = (uint64_t *)
+				malloc(sizeof(uint64_t) * n)) == NULL
+		|| (dcache_buf = (char *) malloc (F2FS_BLKSIZE * n)) == NULL
+		|| (dcache_valid = (bool *) malloc(sizeof(bool) * n)) == NULL)
+	{
+		dcache_release();
+		return -1;
+	}
+	dcache_config.num_cache_entry = n;
+	return 0;
+}
+
+static void dcache_relocate_init(void)
+{
+	int i;
+	int n0 = (sizeof(dcache_relocate_offset0)
+			/ sizeof(dcache_relocate_offset0[0]));
+	int n = (sizeof(dcache_relocate_offset)
+			/ sizeof(dcache_relocate_offset[0]));
+
+	ASSERT(n == n0);
+	for (i = 0; i < n && i < dcache_config.max_hash_collision; i++) {
+		if (abs(dcache_relocate_offset0[i])
+				> dcache_config.num_cache_entry / 2) {
+			dcache_config.max_hash_collision = i;
+			break;
+		}
+		dcache_relocate_offset[i] =
+				dcache_config.num_cache_entry
+				+ dcache_relocate_offset0[i];
+	}
+}
+
+void dcache_init(void)
+{
+	off64_t n;
+
+	if (c.cache_config.num_cache_entry == 0)
+		return;
+
+	/* release previous cache init, if any */
+	dcache_release();
+
+	dcache_blk = NULL;
+	dcache_lastused = NULL;
+	dcache_buf = NULL;
+	dcache_valid = NULL;
+
+	dcache_config = c.cache_config;
+
+	n = max(MIN_NUM_CACHE_ENTRY, dcache_config.num_cache_entry);
+
+	/* halve alloc size until alloc succeed, or min cache reached */
+	while (dcache_alloc_all(n) != 0 && n !=  MIN_NUM_CACHE_ENTRY)
+		n = max(MIN_NUM_CACHE_ENTRY, n/2);
+
+	/* must be the last: data dependent on num_cache_entry */
+	dcache_relocate_init();
+	dcache_initialized = true;
+
+	if (!dcache_exit_registered) {
+		dcache_exit_registered = true;
+		atexit(dcache_release); /* auto release */
+	}
+}
+
+static inline char *dcache_addr(off64_t entry)
+{
+	return dcache_buf + F2FS_BLKSIZE * entry;
+}
+
+/* relocate on (n+1)-th collision */
+static inline off64_t dcache_relocate(off64_t entry, int n)
+{
+	return (entry + dcache_relocate_offset[n]) %
+			dcache_config.num_cache_entry;
+}
+
+static off64_t dcache_find(off64_t blk)
+{
+	register off64_t n = dcache_config.num_cache_entry;
+	register unsigned m = dcache_config.max_hash_collision;
+	off64_t entry, least_used, target;
+	unsigned try;
+
+	target = least_used = entry = blk % n;
+
+	for (try = 0; try < m; try++) {
+		if (!dcache_valid[target] || dcache_blk[target] == blk)
+			return target;  /* found target or empty cache slot */
+		if (dcache_lastused[target] < dcache_lastused[least_used])
+			least_used = target;
+		target = dcache_relocate(entry, try); /* next target */
+	}
+	return least_used;  /* max search reached, return least used slot */
+}
+
+/* Physical read into cache */
+static int dcache_io_read(int fd, off64_t entry, off64_t offset, off64_t blk)
+{
+	if (lseek64(fd, (off64_t)offset, SEEK_SET) < 0) {
+		MSG(0, "\n lseek64 fail.\n");
+		return -1;
+	}
+	if (read(fd, dcache_buf + entry * F2FS_BLKSIZE, F2FS_BLKSIZE) < 0) {
+		MSG(0, "\n read() fail.\n");
+		return -1;
+	}
+	dcache_lastused[entry] = ++dcache_usetick;
+	dcache_valid[entry] = true;
+	dcache_blk[entry] = blk;
+	return 0;
+}
+
+/*
+ *  - Note: Read/Write are not symmetric:
+ *       For read, we need to do it block by block, due to the cache nature:
+ *           some blocks may be cached, and others don't.
+ *       For write, since we always do a write-thru, we can join all writes into one,
+ *       and write it once at the caller.  This function updates the cache for write, but
+ *       not the do a physical write.  The caller is responsible for the physical write.
+ *  - Note: We concentrate read/write together, due to the fact of similar structure to find
+ *          the relevant cache entries
+ *  - Return values:
+ *       0: success
+ *       1: cache not available (uninitialized)
+ *      -1: error
+ */
+static int dcache_update_rw(int fd, void *buf, off64_t offset,
+		size_t byte_count, bool is_write)
+{
+	off64_t blk;
+	int32_t addr_in_blk;
+	off64_t start;
+
+	if (!dcache_initialized)
+		dcache_init(); /* auto initialize */
+
+	if (!dcache_initialized)
+		return 1; /* not available */
+
+	blk = offset / F2FS_BLKSIZE;
+	addr_in_blk = offset % F2FS_BLKSIZE;
+	start = blk * F2FS_BLKSIZE;
+
+	while (byte_count != 0) {
+		int32_t cur_size = min(byte_count,
+				(size_t)(F2FS_BLKSIZE - addr_in_blk));
+		off64_t entry = dcache_find(blk);
+
+		if (!is_write)
+			++dcache_raccess;
+
+		if (dcache_valid[entry] && dcache_blk[entry] == blk) {
+			/* cache hit */
+			if (is_write)  /* write: update cache */
+				memcpy(dcache_addr(entry) + addr_in_blk,
+					buf, cur_size);
+			else
+				++dcache_rhit;
+		} else {
+			/* cache miss */
+			if (!is_write) {
+				int err;
+				++dcache_rmiss;
+				if (dcache_valid[entry])
+					++dcache_rreplace;
+				/* read: physical I/O read into cache */
+				err = dcache_io_read(fd, entry, start, blk);
+				if (err)
+					return err;
+			}
+		}
+
+		/* read: copy data from cache */
+		/* write: nothing to do, since we don't do physical write. */
+		if (!is_write)
+			memcpy(buf, dcache_addr(entry) + addr_in_blk,
+				cur_size);
+
+		/* next block */
+		++blk;
+		buf += cur_size;
+		offset += F2FS_BLKSIZE;
+		byte_count -= cur_size;
+		addr_in_blk = 0;
+	}
+	return 0;
+}
+
+/*
+ * dcache_update_cache() just update cache, won't do physical I/O.
+ * Thus even no error, we need normal non-cache I/O for actual write
+ *
+ * return value: 1: cache not available
+ *               0: success, -1: I/O error
+ */
+inline int dcache_update_cache(int fd, void *buf, off64_t offset, size_t count)
+{
+	return dcache_update_rw(fd, buf, offset, count, true);
+}
+
+/* handles read into cache + read into buffer  */
+inline int dcache_read(int fd, void *buf, off64_t offset, size_t count)
+{
+	return dcache_update_rw(fd, buf, offset, count, false);
+}
+
 /*
  * IO interfaces
  */
@@ -185,6 +490,7 @@ static int sparse_write_zeroed_blk(__u64 block, int count) { return 0; }
 int dev_read(void *buf, __u64 offset, size_t len)
 {
 	int fd;
+	int err;
 
 	if (c.sparse_mode)
 		return sparse_read_blk(offset / F2FS_BLKSIZE,
@@ -194,6 +500,11 @@ int dev_read(void *buf, __u64 offset, size_t len)
 	if (fd < 0)
 		return fd;
 
+	/* err = 1: cache not available, fall back to non-cache R/W */
+	/* err = 0: success, err=-1: I/O error */
+	err = dcache_read(fd, buf, (off64_t)offset, len);
+	if (err <= 0)
+		return err;
 	if (lseek64(fd, (off64_t)offset, SEEK_SET) < 0)
 		return -1;
 	if (read(fd, buf, len) < 0)
@@ -233,6 +544,12 @@ int dev_write(void *buf, __u64 offset, size_t len)
 	if (fd < 0)
 		return fd;
 
+	/*
+	 * dcache_update_cache() just update cache, won't do I/O.
+	 * Thus even no error, we need normal non-cache I/O for actual write
+	 */
+	if (dcache_update_cache(fd, buf, (off64_t)offset, len) < 0)
+		return -1;
 	if (lseek64(fd, (off64_t)offset, SEEK_SET) < 0)
 		return -1;
 	if (write(fd, buf, len) < 0)
-- 
2.24.0.rc0.303.g954a862665-goog



_______________________________________________
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

^ permalink raw reply	[flat|nested] 4+ messages in thread

end of thread, back to index

Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-11-23  0:44 [f2fs-dev] [PATCH 1/2] libf2fs_io: Add user-space cache Jaegeuk Kim
2019-11-23  0:44 ` [f2fs-dev] [PATCH 2/2] fsck.f2fs: Enable " Jaegeuk Kim
  -- strict thread matches above, loose matches on Subject: below --
2019-10-29  7:47 [f2fs-dev] [PATCH 1/2] libf2fs_io: Add " Robin Hsu via Linux-f2fs-devel
2019-10-30 16:46 ` Jaegeuk Kim

Linux-f2fs-devel Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-f2fs-devel/0 linux-f2fs-devel/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-f2fs-devel linux-f2fs-devel/ https://lore.kernel.org/linux-f2fs-devel \
		linux-f2fs-devel@lists.sourceforge.net
	public-inbox-index linux-f2fs-devel

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/net.sourceforge.lists.linux-f2fs-devel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git