From patchwork Mon Mar 21 01:45:25 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Nelson X-Patchwork-Id: 599942 X-Patchwork-Delegate: trini@ti.com Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from theia.denx.de (theia.denx.de [85.214.87.163]) by ozlabs.org (Postfix) with ESMTP id 3qSzF46qtTz9s5l for ; Mon, 21 Mar 2016 12:46:00 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id DF92CA7647; Mon, 21 Mar 2016 02:45:56 +0100 (CET) Received: from theia.denx.de ([127.0.0.1]) by localhost (theia.denx.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 6gHwxMILdniy; Mon, 21 Mar 2016 02:45:56 +0100 (CET) Received: from theia.denx.de (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id D8B73A76A3; Mon, 21 Mar 2016 02:45:52 +0100 (CET) Received: from localhost (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id 36D67A7498 for ; Mon, 21 Mar 2016 02:45:47 +0100 (CET) Received: from theia.denx.de ([127.0.0.1]) by localhost (theia.denx.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id j3-88km7dOKU for ; Mon, 21 Mar 2016 02:45:47 +0100 (CET) X-policyd-weight: NOT_IN_SBL_XBL_SPAMHAUS=-1.5 NOT_IN_SPAMCOP=-1.5 NOT_IN_BL_NJABL=-1.5 (only DNSBL check requested) Received: from fed1rmfepo103.cox.net (fed1rmfepo103.cox.net [68.230.241.145]) by theia.denx.de (Postfix) with ESMTP id 0C5A3A748F for ; Mon, 21 Mar 2016 02:45:43 +0100 (CET) Received: from fed1rmimpo210.cox.net ([68.230.241.161]) by fed1rmfepo103.cox.net (InterMail vM.8.01.05.15 201-2260-151-145-20131218) with ESMTP id <20160321014541.MCJX17588.fed1rmfepo103.cox.net@fed1rmimpo210.cox.net> for ; Sun, 20 Mar 2016 21:45:41 -0400 Received: from localhost.localdomain ([98.165.107.234]) by fed1rmimpo210.cox.net with cox id YRlg1s00553Tyga01RlhV4; Sun, 20 Mar 2016 21:45:41 -0400 X-CT-Class: Clean X-CT-Score: 0.00 X-CT-RefID: str=0001.0A020205.56EF5245.00A3, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CT-Spam: 0 X-Authority-Analysis: v=2.1 cv=P+Oa/n0u c=1 sm=1 tr=0 a=mmedTQiI2PtWY+RDxZIZmw==:117 a=mmedTQiI2PtWY+RDxZIZmw==:17 a=L9H7d07YOLsA:10 a=9cW_t1CCXrUA:10 a=s5jvgZ67dGcA:10 a=9_1hYV8uAAAA:8 a=H39xMOVNT9mNbQCryacA:9 a=EGmhV7C9KxvZzCaR:21 a=KqfkGJbebGc9G7vX:21 X-CM-Score: 0.00 Authentication-Results: cox.net; auth=pass (CRAM-MD5) smtp.auth=eric.a.nelson@cox.net From: Eric Nelson To: u-boot@lists.denx.de, ioan.nicu.ext@nsn.com, swarren@wwwdotorg.org, trini@konsulko.com, sjg@chromium.org Date: Sun, 20 Mar 2016 18:45:25 -0700 Message-Id: <1458524727-4643-2-git-send-email-eric@nelint.com> X-Mailer: git-send-email 2.6.2 In-Reply-To: <1458524727-4643-1-git-send-email-eric@nelint.com> References: <1458524727-4643-1-git-send-email-eric@nelint.com> Cc: marex@denx.de Subject: [U-Boot] [RFC V2 PATCH 1/3] drivers: block: add block device cache X-BeenThere: u-boot@lists.denx.de X-Mailman-Version: 2.1.15 Precedence: list List-Id: U-Boot discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: u-boot-bounces@lists.denx.de Sender: "U-Boot" Add a block device cache to speed up repeated reads of block devices by various filesystems. This small amount of cache can dramatically speed up filesystem operations by skipping repeated reads of common areas of a block device (typically directory structures). This has shown to have some benefit on FAT filesystem operations of loading a kernel and RAM disk, but more dramatic benefits on ext4 filesystems when the kernel and/or RAM disk are spread across multiple extent header structures as described in commit fc0fc50. The cache is implemented through a minimal list (block_cache) maintained in most-recently-used order and count of the current number of entries (cache_count). It uses a maximum block count setting to prevent copies of large block reads and an upper bound on the number of cached areas. The maximum number of entries in the cache defaults to 4 and the maximum number of blocks per cache entry has a default of 1, which matches the current implementation of at least FAT and ext4 that only read a single block at a time. The 'blkcache' command (enabled through CONFIG_CMD_BLOCK_CACHE) allows changing these values and can be used to tune for a particular filesystem layout. Signed-off-by: Eric Nelson --- drivers/block/Makefile | 1 + drivers/block/cache_block.c | 240 ++++++++++++++++++++++++++++++++++++++++++++ include/part.h | 69 +++++++++++++ 3 files changed, 310 insertions(+) create mode 100644 drivers/block/cache_block.c diff --git a/drivers/block/Makefile b/drivers/block/Makefile index b5c7ae1..056a48b 100644 --- a/drivers/block/Makefile +++ b/drivers/block/Makefile @@ -24,3 +24,4 @@ obj-$(CONFIG_IDE_SIL680) += sil680.o obj-$(CONFIG_SANDBOX) += sandbox.o obj-$(CONFIG_SCSI_SYM53C8XX) += sym53c8xx.o obj-$(CONFIG_SYSTEMACE) += systemace.o +obj-$(CONFIG_BLOCK_CACHE) += cache_block.o diff --git a/drivers/block/cache_block.c b/drivers/block/cache_block.c new file mode 100644 index 0000000..e4ebeda --- /dev/null +++ b/drivers/block/cache_block.c @@ -0,0 +1,240 @@ +/* + * Copyright (C) Nelson Integration, LLC 2016 + * Author: Eric Nelson + * + * SPDX-License-Identifier: GPL-2.0+ + * + */ +#include +#include +#include +#include +#include +#include + +struct block_cache_node { + struct list_head lh; + int iftype; + int devnum; + lbaint_t start; + lbaint_t blkcnt; + unsigned long blksz; + char *cache; +}; + +static LIST_HEAD(block_cache); +static unsigned cache_count; + +static unsigned long max_blocks_per_entry = 1; +static unsigned long max_cache_entries = 4; + +static unsigned block_cache_misses; +static unsigned block_cache_hits; + +static int trace; + +/* + * search for a set of blocks in the cache + * + * remove and return the node if found so it can be + * added back at the start of the list and maintain MRU order) + */ +static struct block_cache_node *cache_find + (int iftype, int devnum, + lbaint_t start, lbaint_t blkcnt, + unsigned long blksz) +{ + struct block_cache_node *node; + + list_for_each_entry(node, &block_cache, lh) + if ((node->iftype == iftype) && + (node->devnum == devnum) && + (node->blksz == blksz) && + (node->start <= start) && + (node->start + node->blkcnt >= start + blkcnt)) { + list_del(&node->lh); + return node; + } + return 0; +} + +int cache_block_read(int iftype, int devnum, + lbaint_t start, lbaint_t blkcnt, + unsigned long blksz, void *buffer) +{ + struct block_cache_node *node = cache_find(iftype, devnum, start, + blkcnt, blksz); + if (node) { + const char *src = node->cache + (start - node->start) * blksz; + list_add(&node->lh, &block_cache); + memcpy(buffer, src, blksz*blkcnt); + if (trace) + printf("hit: start " LBAF ", count " LBAFU "\n", + start, blkcnt); + ++block_cache_hits; + return 1; + } + + if (trace) + printf("miss: start " LBAF ", count " LBAFU "\n", + start, blkcnt); + ++block_cache_misses; + return 0; +} + +void cache_block_fill(int iftype, int devnum, + lbaint_t start, lbaint_t blkcnt, + unsigned long blksz, void const *buffer) +{ + lbaint_t bytes; + struct block_cache_node *node; + + /* don't cache big stuff */ + if (blkcnt > max_blocks_per_entry) + return; + + if (max_cache_entries == 0) + return; + + bytes = blksz * blkcnt; + if (max_cache_entries <= cache_count) { + /* pop LRU */ + node = (struct block_cache_node *)block_cache.prev; + list_del(&node->lh); + cache_count--; + if (node->blkcnt * node->blksz < bytes) { + free(node->cache); + node->cache = 0; + } + } else { + node = malloc(sizeof(*node)); + if (!node) + return; + node->cache = 0; + } + + if (node->cache == 0) { + node->cache = malloc(bytes); + if (!node->cache) { + free(node); + return; + } + } + + if (trace) + printf("fill: start " LBAF ", count " LBAFU "\n", + start, blkcnt); + + node->iftype = iftype; + node->devnum = devnum; + node->start = start; + node->blkcnt = blkcnt; + node->blksz = blksz; + memcpy(node->cache, buffer, bytes); + list_add(&node->lh, &block_cache); + cache_count++; +} + +void cache_block_invalidate(int iftype, int devnum) +{ + struct list_head *entry, *n; + struct block_cache_node *node; + + list_for_each_safe(entry, n, &block_cache) { + node = (struct block_cache_node *)entry; + if ((node->iftype == iftype) && + (node->devnum == devnum)) { + list_del(entry); + free(node->cache); + free(node); + --cache_count; + } + } +} + +void cache_block_invalidate_all(void) +{ + struct list_head *entry, *n; + struct block_cache_node *node; + + list_for_each_safe(entry, n, &block_cache) { + node = (struct block_cache_node *)entry; + list_del(entry); + free(node->cache); + free(node); + } + + cache_count = 0; +} + +#ifdef CONFIG_CMD_BLOCK_CACHE + +static void dump_block_cache(void) +{ + struct list_head *entry, *n; + struct block_cache_node *node; + int i = 0; + + list_for_each_safe(entry, n, &block_cache) { + node = (struct block_cache_node *)entry; + printf("----- cache entry[%d]\n", i++); + printf("iftype %d\n", node->iftype); + printf("devnum %d\n", node->devnum); + printf("blksize " LBAFU "\n", node->blksz); + printf("start " LBAF "\n", node->start); + printf("count " LBAFU "\n", node->blkcnt); + } +} + +static int do_blkcache(cmd_tbl_t *cmdtp, int flag, + int argc, char * const argv[]) +{ + if ((argc == 1) || !strcmp("show", argv[1])) { + printf("block cache:\n" + "%u\thits\n" + "%u\tmisses\n" + "%u\tentries in cache\n" + "trace %s\n" + "max blocks/entry %lu\n" + "max entries %lu\n", + block_cache_hits, block_cache_misses, cache_count, + trace ? "on" : "off", + max_blocks_per_entry, max_cache_entries); + } else if ((argc == 2) && ('c' == argv[1][0])) { + block_cache_hits = 0; + block_cache_misses = 0; + } else if ((argc == 2) && ('d' == argv[1][0])) { + dump_block_cache(); + } else if ((argc == 2) && ('i' == argv[1][0])) { + cache_block_invalidate_all(); + } else if ((argc >= 2) && ('t' == argv[1][0])) { + if ((argc == 3) && !strcmp("off", argv[2])) + trace = 0; + else + trace = 1; + } else if ((argc == 3) && isdigit(argv[1][0]) && isdigit(argv[2][0])) { + max_blocks_per_entry = simple_strtoul(argv[1], 0, 0); + max_cache_entries = simple_strtoul(argv[2], 0, 0); + cache_block_invalidate_all(); + printf("changed to max of %lu entries of %lu blocks each\n", + max_cache_entries, max_blocks_per_entry); + } else { + return CMD_RET_USAGE; + } + + return 0; +} + +U_BOOT_CMD( + blkcache, 3, 0, do_blkcache, + "block cache control/statistics", + "[show] - show statistics\n" + "blkcache c[lear] - clear statistics\n" + "blkcache d[ump] - dump cache entries\n" + "blkcache i[nvalidate] - invalidate cache\n" + "blkcache #maxblocks #maxentries\n" + "\tset maximum blocks per cache entry, maximum entries\n" + "blkcache t[race] [off] - enable (disable) tracing" +); + +#endif diff --git a/include/part.h b/include/part.h index dc8e72e..1ac73dcc 100644 --- a/include/part.h +++ b/include/part.h @@ -376,4 +376,73 @@ int gpt_verify_partitions(struct blk_desc *dev_desc, gpt_header *gpt_head, gpt_entry **gpt_pte); #endif +#ifdef CONFIG_BLOCK_CACHE +/** + * cache_block_read() - attempt to read a set of blocks from cache + * + * @param iftype - IF_TYPE_x for type of device + * @param dev - device index of particular type + * @param start - starting block number + * @param blkcnt - number of blocks to read + * @param blksz - size in bytes of each block + * @param buf - buffer to contain cached data + * + * @return - '1' if block returned from cache, '0' otherwise. + */ +int cache_block_read + (int iftype, int dev, + lbaint_t start, lbaint_t blkcnt, + unsigned long blksz, void *buffer); + +/** + * cache_block_fill() - make data read from a block device available + * to the block cache + * + * @param iftype - IF_TYPE_x for type of device + * @param dev - device index of particular type + * @param start - starting block number + * @param blkcnt - number of blocks available + * @param blksz - size in bytes of each block + * @param buf - buffer containing data to cache + * + */ +void cache_block_fill + (int iftype, int dev, + lbaint_t start, lbaint_t blkcnt, + unsigned long blksz, void const *buffer); + +/** + * cache_block_invalidate() - discard the cache for a set of blocks + * because of a write or device (re)initialization. + * + * @param iftype - IF_TYPE_x for type of device + * @param dev - device index of particular type + */ +void cache_block_invalidate + (int iftype, int dev); + +void cache_block_invalidate_all(void); + +#else + +static inline int cache_block_read + (int iftype, int dev, + lbaint_t start, lbaint_t blkcnt, + unsigned long blksz, void *buffer) +{ + return 0; +} + +static inline void cache_block_fill + (int iftype, int dev, + lbaint_t start, lbaint_t blkcnt, + unsigned long blksz, void const *buffer) {} + +static inline void cache_block_invalidate + (int iftype, int dev) {} + +static inline void cache_block_invalidate_all(void){} + +#endif + #endif /* _PART_H */