libf2fs_io: Add user-space cache
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.
--- include/f2fs_fs.h | 20 +++ lib/libf2fs_io.c | 317 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 337 insertions(+)
include/f2fs_fs.h +20 -0
@@ -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 );
lib/libf2fs_io.c +317 -0
347 lines not on this page · raw message
Signature · 1 line
2.24.0.rc0.303.g954a862665-goog
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);Quoted 423 lines · Robin Hsu
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 <[email protected]>--- include/f2fs_fs.h | 20 +++ lib/libf2fs_io.c | 317 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 337 insertions(+)include/f2fs_fs.h +20
-0@@ -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 );lib/libf2fs_io.c +317
-0@@ -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) +{ + registeroff64_t n = dcache_config.num_cache_entry; + registerunsigned 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 )Signature · 1 line
2.24.0.rc0.303.g954a862665-goog