Add cache for block devices

   blkc 1 $n ; blkc c ; blkc i ; 
   load mmc 0:2 10008000 /boot/zImage ; 

done

Add a block device cache to speed up repeated reads of block devices by various filesystems.

Signed-off-by Eric Nelson <[email protected]>

---
 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

include/part.h +5 -0

+#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

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.

+void cache_block_fill(int iftype, int devnum,

+void cache_block_invalidate(int iftype, int devnum)

+void cache_block_invalidate_all(void)

+static void dump_block_cache(void)

drivers/block/cache_block.c +4 -0

+static int do_blkcache(cmd_tbl_t *cmdtp, int flag,
+		       int argc, char * const argv[])
+{
+	if ((argc == 1) || !strcmp("show", argv[1])) {

Quoted 17 lines · Eric Nelson

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.

Quoted 4 lines

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.

If the maximum size of the cache is fixed and small (which judging by the description it is), why not use an array rather than a linked list. That would be far simpler to manage.

Quoted 3 lines

The 'blkcache' command (enabled through CONFIG_CMD_BLOCK_CACHE) allows changing these values and can be used to tune for a particular filesystem layout.

Even with this dynamic adjustment, using an array still feels simpler, although I have't looked at the code yet.

drivers/block/cache_block.c line 41

Quoted 8 lines

drivers/block/cache_block.c +6 -0

 
+/*
+ * 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)
+ */

Splitting the remove/add feels a bit dangerous, since forgetting to re-do the add (or e.g. some error causing that to be skipped) could cause cache_count to become inconsistent.

The function name "find" is a bit misleading. cache_find_and_remove() would make its semantics more obvious. Or, simply put the list_del() somewhere else; it doesn't feel like part of a "find" operation to me. Or, put the entire move-to-front operation inside this function so it isn't split up - if so, cache_find_and_move_to_head().

drivers/block/cache_block.c line 43

Quoted 2 lines

drivers/block/cache_block.c +2 -0

+static struct block_cache_node *cache_find
+    (int iftype, int devnum,

Nit: the ( and first n arguments shouldn't be wrapped.

drivers/block/cache_block.c line 70

Quoted 5 lines

drivers/block/cache_block.c +4 -0

+int cache_block_read(int iftype, int devnum,
+             lbaint_t start, lbaint_t blkcnt,
+             unsigned long blksz, void *buffer)
 
+        memcpy(buffer, src, blksz*blkcnt);

Nit: Space around operators. checkpatch should catch this.

drivers/block/cache_block.c line 73

Quoted 3 lines

drivers/block/cache_block.c +3 -0

+        if (trace)
+            printf("hit: start " LBAF ", count " LBAFU "\n",
+                   start, blkcnt);

I guess I'll find that trace can be adjusted at run-time somewhere later in this patch, but it's more typical to use debug() without the if statement for this. It would be awesome if debug() could be adjusted at run-time...

Quoted 1 line

+void cache_block_fill(int iftype, int devnum,

...

drivers/block/cache_block.c line 118

Quoted 3 lines

drivers/block/cache_block.c +3 -0

+    if (node->cache == 0) {
+        node->cache = malloc(bytes);
+        if (!node->cache) {

Nit: may as well be consistent with those NULL checks.

Quoted 1 line

+void cache_block_invalidate(int iftype, int devnum)

...

Quoted 1 line

+void cache_block_invalidate_all(void)

There's no invalidate_blocks(); I imagine that writing-to/erasing (some blocks of) a device must call cache_block_invalidate() which will wipe out even data that wasn't written.

Quoted 1 line

+static void dump_block_cache(void)

...

Quoted 1 line

+ list_for_each_safe(entry, n, &block_cache) {

Nit: This doesn't need to be _safe since the list is not being modified.

Quoted 4 lines

drivers/block/cache_block.c +4 -0

+static int do_blkcache(cmd_tbl_t *cmdtp, int flag,
+               int argc, char * const argv[])
+{
+    if ((argc == 1) || !strcmp("show", argv[1])) {

drivers/block/cache_block.c line 202

Quoted 10 lines

drivers/block/cache_block.c +10 -0

+        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);

Nit: Let's print the value and "label" in a consistent order. I would suggest everything being formatted as:

" description: %u"

so that it's indented, has a delimiter between description and value, and so that irrespective of the length of the converted value, the indentation of the other parts of the string don't change (\t doesn't guarantee this after a certain number length).

I would rather have expected "show" to dump the entries too, but I suppose it's fine that they're separate.

Quoted 1 line

+ } else if ((argc == 2) && ('c' == argv[1][0])) {

Nit: the value of 'c' is always 'c', so it's pointless to test whether it's equal to something. The value being compared is arv[1][0], so the parameters to == should be swapped. I'm aware that == is mathematically commutative, but typical English reading of the operator is "is equal to" which has non-commutative implications re: what is being tested. I'm also aware that this construct is used to trigger compiler warnings if someone types = instead of ==. However, (a) you didn't and (b) compilers warn about this these days, so there's no need to write unusual code to get that feature anymore.

I worry that being imprecise in command-line parsing (i.e. treating both "crud" and "clear" as the same thing) will lead to problems expanding the command-line format in the future; we won't be able to ever add another option starting with "c" and maintain the same abbreviation semantics. I'd suggest requiring the full option name always.

Quoted 2 lines

+ } else if ((argc == 3) && isdigit(argv[1][0]) &&
isdigit(argv[2][0])) {

Let's make this "blkcache set" or "blkcache configure" so that other sub-commands can take numeric parameters in the future, and have consistent command-line syntax.

Quoted 7 lines

drivers/block/cache_block.c +7 -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"

drivers/block/cache_block.c line 238

Quoted 4 lines

drivers/block/cache_block.c +4 -0

+    "blkcache #maxblocks #maxentries\n"
+    "\tset maximum blocks per cache entry, maximum entries\n"
+    "blkcache t[race] [off] - enable (disable) tracing"
+);

BTW, isn't there some support in U-Boot for sub-commands already, so you can write a separate function per sub-command and skip writing all the strcmp logic to select between them? I'm pretty sure I saw that somewhere.

include/part.h

Quoted 3 lines

include/part.h +1 -0

 
+static inline void cache_block_invalidate_all(void){}

Is that useful outside of the debug commands?

Allow the selection of CONFIG_BLOCK_CACHE, CONFIG_CMD_BLOCK_CACHE using menuconfig.

Quoted 2 lines · Eric Nelson

Allow the selection of CONFIG_BLOCK_CACHE, CONFIG_CMD_BLOCK_CACHE using menuconfig.

I think this should be part of patch 1.

Quoted 1 line · Eric Nelson

drivers/mmc/mmc.c +0 -0

drivers/mmc/mmc.c line 9

Quoted 6 lines

drivers/mmc/mmc.c +0 -1

@@ -6,7 +6,6 @@
   *
   * SPDX-License-Identifier:    GPL-2.0+
   */
-
  #include <config.h>

Unrelated change?

I don't see any cache invalidation call when the SD device is re-initialized.

I think I mentioned these two points last time.

Here's a more full-featured implementation of a cache for block devices that uses a small linked list of cache blocks.

Experimentation loading a 4.5 MiB kernel from the root directory of a FAT filesystem shows that a single cache entry of a single block is the only

Loading the same from the /boot directory of an ext4 filesystem shows a benefit with 4 cache entries, though the single biggest benefit is also with the first cache entry:

=> for n in 0 1 2 4 8 ; do

Quoted 3 lines

   blkc 1 $n ; blkc c ; blkc i ; 
   load mmc 0:2 10008000 /boot/zImage ; 

done

changed to max of 0 entries of 1 blocks each
4955304 bytes read in 503 ms (9.4 MiB/s)
changed to max of 1 entries of 1 blocks each
4955304 bytes read in 284 ms (16.6 MiB/s)
changed to max of 2 entries of 1 blocks each
4955304 bytes read in 284 ms (16.6 MiB/s)
changed to max of 4 entries of 1 blocks each
4955304 bytes read in 255 ms (18.5 MiB/s)
changed to max of 8 entries of 1 blocks each
4955304 bytes read in 255 ms (18.5 MiB/s)

As mentioned earlier in this thread, the modification to the mmc layer should probably be simpler and easier to apply to other block subsystems.

Eric Nelson (3):
drivers: block: add block device cache
block: add Kconfig options for BLOCK_CACHE, CMD_BLOCK_CACHE
mmc: add support for block device cache

 drivers/block/Kconfig       |  19 ++++
 drivers/block/Makefile      |   1 +
 drivers/block/cache_block.c | 240 ++++++++++++++++++++++++++++++++++++++++++++
 drivers/mmc/mmc.c           |  10 +-
 drivers/mmc/mmc_write.c     |   7 ++
 include/part.h              |  69 +++++++++++++
 6 files changed, 345 insertions(+), 1 deletion(-)
 create mode 100644 drivers/block/cache_block.c

Quoted 2 lines · Eric Nelson

Here's a more full-featured implementation of a cache for block devices that uses a small linked list of cache blocks.

Why do you use linked list ? You have four entries, you can as well use fixed array. Maybe you should implement an adaptive cache would would use the unpopulated malloc area and hash the sector number(s) into that area ?

Quoted 3 lines

Experimentation loading a 4.5 MiB kernel from the root directory of
a FAT filesystem shows that a single cache entry of a single
block is the only

only ... what ? This is where things started to be interesting, but you leave us hanging :)

Hi Marek,

Quoted 9 lines · Marek Vasut

Quoted 2 lines · Eric Nelson

Here's a more full-featured implementation of a cache for block devices that uses a small linked list of cache blocks.

Why do you use linked list ? You have four entries, you can as well use fixed array. Maybe you should implement an adaptive cache would would use the unpopulated malloc area and hash the sector number(s) into that area ?

I was looking for a simple implementation that would allow tweaking of the max entries/size per entry.

We could get higher performance through hashing, but with such a small cache, it's probably not worth extra code.

Using an array and re-allocating on changes to the max entries variable is feasible, but I think it would be slightly more code.

Quoted 7 lines

Quoted 3 lines

Experimentation loading a 4.5 MiB kernel from the root directory of
a FAT filesystem shows that a single cache entry of a single
block is the only

only ... what ? This is where things started to be interesting, but you leave us hanging :)

Oops.

... I was planning on re-wording that.

My testing showed no gain in performance (additional cache hits) past a single entry of a single block. This was done on a small (32MiB) partition with a small number of files (~10) and only a single read is skipped.

=> blkc c ; blkc i ; blkc 0 0 ;
changed to max of 0 entries of 0 blocks each
=> load mmc 0 10008000 /zImage
reading /zImage
4955304 bytes read in 247 ms (19.1 MiB/s)
=> blkc
block cache:
0 hits
7 misses
0 entries in cache
trace off
max blocks/entry 0
max entries 0
=> blkc c ; blkc i ; blkc 1 1 ;
changed to max of 1 entries of 1 blocks each
=> load mmc 0 10008000 /zImage
reading /zImage
4955304 bytes read in 243 ms (19.4 MiB/s)
=> blkc
block cache:
1 hits
6 misses
1 entries in cache
trace off
max blocks/entry 1
max entries 1

I don't believe that enabling the cache is worth the extra code for this use case.

By comparison, a load of 150 MiB compressed disk image from ext4 showed a 30x speedup with the V1 patch (single block, single entry) from ~150s to 5s.

Without some form of cache, the 150s was long enough to make a user (me) think something is broken.

Quoted 11 lines · Eric Nelson

Quoted 9 lines · Marek Vasut

Quoted 2 lines · Eric Nelson

Here's a more full-featured implementation of a cache for block devices that uses a small linked list of cache blocks.

Why do you use linked list ? You have four entries, you can as well use fixed array. Maybe you should implement an adaptive cache would would use the unpopulated malloc area and hash the sector number(s) into that area ?

Quoted 5 lines

I was looking for a simple implementation that would allow tweaking of the max entries/size per entry.

We could get higher performance through hashing, but with such a small cache, it's probably not worth extra code.

The hashing function can be a simple modulo on sector number ;-) That'd be less code than linked lists.

Quoted 2 lines

Using an array and re-allocating on changes to the max entries variable is feasible, but I think it would be slightly more code.

That would indeed be more code.

Quoted 10 lines

Quoted 7 lines

Quoted 3 lines

Experimentation loading a 4.5 MiB kernel from the root directory of
a FAT filesystem shows that a single cache entry of a single
block is the only

only ... what ? This is where things started to be interesting, but you leave us hanging :)

Oops.

Quoted 6 lines

... I was planning on re-wording that.

My testing showed no gain in performance (additional cache hits) past a single entry of a single block. This was done on a small (32MiB) partition with a small number of files (~10) and only a single read is skipped.

I'd kinda expect that indeed.

Quoted 30 lines

=> blkc c ; blkc i ; blkc 0 0 ;
changed to max of 0 entries of 0 blocks each
=> load mmc 0 10008000 /zImage
reading /zImage
4955304 bytes read in 247 ms (19.1 MiB/s)
=> blkc
block cache:
0 hits
7 misses
0 entries in cache
trace off
max blocks/entry 0
max entries 0
=> blkc c ; blkc i ; blkc 1 1 ;
changed to max of 1 entries of 1 blocks each
=> load mmc 0 10008000 /zImage
reading /zImage
4955304 bytes read in 243 ms (19.4 MiB/s)
=> blkc
block cache:
1 hits
6 misses
1 entries in cache
trace off
max blocks/entry 1
max entries 1

I don't believe that enabling the cache is worth the extra code for this use case.

Quoted 6 lines

By comparison, a load of 150 MiB compressed disk image from ext4 showed a 30x speedup with the V1 patch (single block, single entry) from ~150s to 5s.

Without some form of cache, the 150s was long enough to make a user (me) think something is broken.

I'm obviously loving this improvement.

Hi Marek,

Quoted 18 lines · Eric Nelson

Quoted 16 lines · Marek Vasut

Quoted 9 lines · Eric Nelson

Quoted 2 lines

Here's a more full-featured implementation of a cache for block devices that uses a small linked list of cache blocks.

Why do you use linked list ? You have four entries, you can as well use fixed array. Maybe you should implement an adaptive cache would would use the unpopulated malloc area and hash the sector number(s) into that area ?

I was looking for a simple implementation that would allow tweaking of the max entries/size per entry.

We could get higher performance through hashing, but with such a small cache, it's probably not worth extra code.

Quoted 3 lines

The hashing function can be a simple modulo on sector number ;-) That'd be less code than linked lists.

I'm not seeing how.

I'm going look first at a better way to integrate than the approach taken in patch 3.

Quoted 15 lines

Quoted 2 lines

Using an array and re-allocating on changes to the max entries variable is feasible, but I think it would be slightly more code.

That would indeed be more code.

Quoted 10 lines

Quoted 7 lines

Quoted 3 lines

Experimentation loading a 4.5 MiB kernel from the root directory of
a FAT filesystem shows that a single cache entry of a single
block is the only

only ... what ? This is where things started to be interesting, but you leave us hanging :)

Oops.

Quoted 9 lines

Quoted 6 lines

... I was planning on re-wording that.

My testing showed no gain in performance (additional cache hits) past a single entry of a single block. This was done on a small (32MiB) partition with a small number of files (~10) and only a single read is skipped.

I'd kinda expect that indeed.

Yeah, and the single-digit-ms improvement isn't worth much.

Quoted 34 lines

Quoted 34 lines

=> blkc c ; blkc i ; blkc 0 0 ;
changed to max of 0 entries of 0 blocks each
=> load mmc 0 10008000 /zImage
reading /zImage
4955304 bytes read in 247 ms (19.1 MiB/s)
=> blkc
block cache:
0 hits
7 misses
0 entries in cache
trace off
max blocks/entry 0
max entries 0
=> blkc c ; blkc i ; blkc 1 1 ;
changed to max of 1 entries of 1 blocks each
=> load mmc 0 10008000 /zImage
reading /zImage
4955304 bytes read in 243 ms (19.4 MiB/s)
=> blkc
block cache:
1 hits
6 misses
1 entries in cache
trace off
max blocks/entry 1
max entries 1

I don't believe that enabling the cache is worth the extra code for this use case.

By comparison, a load of 150 MiB compressed disk image from ext4 showed a 30x speedup with the V1 patch (single block, single entry) from ~150s to 5s.

Quoted 5 lines

Quoted 2 lines

Without some form of cache, the 150s was long enough to make a user (me) think something is broken.

I'm obviously loving this improvement.

Glad to hear it.

+++ b/drivers/block/blkcache.c

+static int trace;

+#ifdef CONFIG_CMD_BLOCK_CACHE

Quoted 1 line · Eric Nelson

+++ b/drivers/block/blkcache.c

[snip]

Quoted 1 line

+static int trace;

I see where you can toggle this at run-time. But do we really think that this will be useful outside of debug? My first reaction is that we should move the trace stuff into debug() statements instead.

[snip]

Quoted 1 line

+#ifdef CONFIG_CMD_BLOCK_CACHE

Please split the command code into cmd/blkcache.c. And yes, this might require thinking harder about what to expose or making an API for some of it. I'm also not sure that's a bad thing as tuning the cache seems useful long term but dumping the stats seems more like debug work.

[snip]

drivers/block/blkcache.c line 270

Quoted 3 lines

drivers/block/blkcache.c new file +3 -0

+	/* Strip off leading 'i2c' command argument */
+	argc--;
+	argv++;

I see you borrowed from i2c here :)

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 32 and the maximum number of blocks per cache entry has a default of 2, which has shown to produce the best results on testing of ext4 and FAT filesystems.

The 'blkcache' command (enabled through CONFIG_CMD_BLOCK_CACHE) allows changing these values and can be used to tune for a particular filesystem layout.

cmd/blkcache.c +1 -0

 
+static int blkc_show(cmd_tbl_t *cmdtp, int flag,

drivers/block/blkcache.c +6 -0

 
+struct block_cache_node {
+	struct list_head lh;
+	int iftype;
+	int devnum;
+	lbaint_t start;
+	lbaint_t blkcnt;

Quoted 24 lines · Eric Nelson

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 32 and the maximum number of blocks per cache entry has a default of 2, which has shown to produce the best results on testing of ext4 and FAT filesystems.

The 'blkcache' command (enabled through CONFIG_CMD_BLOCK_CACHE) allows changing these values and can be used to tune for a particular filesystem layout.

Quoted 6 lines

disk/part.c +0 -0

@@ -268,6 +268,8 @@ void part_init(struct blk_desc *dev_desc)
 	const int n_ents = ll_entry_count(struct part_driver, part_driver);
 	struct part_driver *entry;
 

disk/part.c void part_init(struct blk_desc *dev_desc) · line 271

Quoted 1 line

disk/part.c +1 -0

+	blkcache_invalidate(dev_desc->if_type, dev_desc->devnum);

Doesn't this invalidate the cache far too often? I expect that function is called for command the user executes from the command-line, whereas it'd be nice if the cache persisted across commands. I suppose this is a reasonable (and very safe) first implementation though, and saves having to go through each storage provider type and find out the right place to detect media changes.

Quoted 8 lines

drivers/block/blkcache.c +6 -0

 
+struct block_cache_node {
+	struct list_head lh;
+	int iftype;
+	int devnum;
+	lbaint_t start;
+	lbaint_t blkcnt;

drivers/block/blkcache.c line 30

Quoted 10 lines

drivers/block/blkcache.c +10 -0

+	unsigned long blksz;
+	char *cache;
+};
+
+static LIST_HEAD(block_cache);
+
+static struct block_cache_stats _stats = {
+	.max_blocks_per_entry = 2,
+	.max_entries = 32
+};

Now is a good time to mention another reason why I don't like using a dynamically allocated linked list for this: Memory fragmentation. By dynamically allocating the cache, we could easily run into a

situation where the user runs a command that allocates memory and also adds to the block cache, then most of that memory gets freed when U-Boot returns to the command prompt, then the user runs the command again but it fails since it can't allocate the memory due to fragmentation of the heap. This is a real problem I've seen e.g. with the "ums" and "dfu" commands, since they might initialize the USB controller the first time they're run, which allocates some new memory. Statically allocation would avoid this.

Quoted 25 lines · Stephen Warren

Quoted 24 lines · Eric Nelson

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 32 and the maximum number of blocks per cache entry has a default of 2, which has shown to produce the best results on testing of ext4 and FAT filesystems.

The 'blkcache' command (enabled through CONFIG_CMD_BLOCK_CACHE) allows changing these values and can be used to tune for a particular filesystem layout.

[snip]

Quoted 6 lines

Quoted 6 lines

disk/part.c +0 -0

@@ -268,6 +268,8 @@ void part_init(struct blk_desc *dev_desc)
  	const int n_ents = ll_entry_count(struct part_driver, part_driver);
  	struct part_driver *entry;
 

Quoted 8 lines

disk/part.c void part_init(struct blk_desc *dev_desc) · line 271

Quoted 1 line

disk/part.c +1 -0

+	blkcache_invalidate(dev_desc->if_type, dev_desc->devnum);

Doesn't this invalidate the cache far too often? I expect that function is called for command the user executes from the command-line, whereas it'd be nice if the cache persisted across commands. I suppose this is a reasonable (and very safe) first implementation though, and saves having to go through each storage provider type and find out the right place to detect media changes.

My initial reaction here is that we should stay conservative and invalidate the cache more often rather than too infrequent. I mean, what's the worst case here, an extra read? A few extra reads? We want to make sure we keep the complexity to functionality ratio right here, if we make the recovery/flashing/factory cases a whole lot better but are leaving 1 second of wall clock time on the table when we've just gained a minute, we're OK.

Quoted 22 lines

Quoted 8 lines

drivers/block/blkcache.c +6 -0

 
+struct block_cache_node {
+	struct list_head lh;
+	int iftype;
+	int devnum;
+	lbaint_t start;
+	lbaint_t blkcnt;

drivers/block/blkcache.c line 30

Quoted 10 lines

drivers/block/blkcache.c +10 -0

+	unsigned long blksz;
+	char *cache;
+};
+
+static LIST_HEAD(block_cache);
+
+static struct block_cache_stats _stats = {
+	.max_blocks_per_entry = 2,
+	.max_entries = 32
+};

Now is a good time to mention another reason why I don't like using a dynamically allocated linked list for this: Memory fragmentation. By dynamically allocating the cache, we could easily run into a

Quoted 8 lines

situation where the user runs a command that allocates memory and also adds to the block cache, then most of that memory gets freed when U-Boot returns to the command prompt, then the user runs the command again but it fails since it can't allocate the memory due to fragmentation of the heap. This is a real problem I've seen e.g. with the "ums" and "dfu" commands, since they might initialize the USB controller the first time they're run, which allocates some new memory. Statically allocation would avoid this.

That is a good point. But how would you hit this? The problem in ums/dfu was that it was several megabytes, yes? My quick read over the code right now has me thinking this is something measured in kilobytes.

Quoted 4 lines · Stephen Warren

Quoted 3 lines · Eric Nelson

Add a block device cache to speed up repeated reads of block devices by various filesystems.

Quoted 4 lines

Quoted 4 lines

disk/part.c +0 -0

@@ -268,6 +268,8 @@ void part_init(struct blk_desc *dev_desc)
 	const int n_ents = ll_entry_count(struct part_driver, part_driver);
 	struct part_driver *entry;
 

Quoted 8 lines

disk/part.c void part_init(struct blk_desc *dev_desc) · line 271

Quoted 1 line

disk/part.c +1 -0

+	blkcache_invalidate(dev_desc->if_type, dev_desc->devnum);

Doesn't this invalidate the cache far too often? I expect that function is called for command the user executes from the command-line, whereas it'd be nice if the cache persisted across commands. I suppose this is a reasonable (and very safe) first implementation though, and saves having to go through each storage provider type and find out the right place to detect media changes.

My initial reaction here is that we should stay conservative and invalidate the cache more often rather than too infrequent. I mean, what's the worst case here, an extra read? A few extra reads? We want to make sure we keep the complexity to functionality ratio right here, if we make the recovery/flashing/factory cases a whole lot better but are leaving 1 second of wall clock time on the table when we've just gained a minute, we're OK.

Quoted 22 lines

Quoted 8 lines

drivers/block/blkcache.c +6 -0

 
+struct block_cache_node {
+	struct list_head lh;
+	int iftype;
+	int devnum;
+	lbaint_t start;
+	lbaint_t blkcnt;

drivers/block/blkcache.c line 30

Quoted 10 lines

drivers/block/blkcache.c +10 -0

+	unsigned long blksz;
+	char *cache;
+};
+
+static LIST_HEAD(block_cache);
+
+static struct block_cache_stats _stats = {
+	.max_blocks_per_entry = 2,
+	.max_entries = 32
+};

Now is a good time to mention another reason why I don't like using a dynamically allocated linked list for this: Memory fragmentation. By dynamically allocating the cache, we could easily run into a

Quoted 8 lines

situation where the user runs a command that allocates memory and also adds to the block cache, then most of that memory gets freed when U-Boot returns to the command prompt, then the user runs the command again but it fails since it can't allocate the memory due to fragmentation of the heap. This is a real problem I've seen e.g. with the "ums" and "dfu" commands, since they might initialize the USB controller the first time they're run, which allocates some new memory. Statically allocation would avoid this.

That is a good point. But how would you hit this? The problem in ums/dfu was that it was several megabytes, yes? My quick read over the code right now has me thinking this is something measured in kilobytes.

Quoted 3 lines · Eric Nelson

Add a block device cache to speed up repeated reads of block devices by various filesystems.

cmd/blkcache.c line 23

Quoted 6 lines

cmd/blkcache.c new file +6 -0

+
+    printf("    hits: %u\n"
+           "    misses: %u\n"
+           "    entries: %u\n"
+           "    max blocks/entry: %u\n"
+           "    max cache entries: %u\n",

Nit: I'm not sure why all that command output is indented. Perhaps it made sense before if some kind of title was printed before that text, but I don't think it is any more.

cmd/blkcache.c line 81

Quoted 6 lines

cmd/blkcache.c new file +6 -0

+    if (c)
+        return c->cmd(cmdtp, flag, argc, argv);
+    else
+        return CMD_RET_USAGE;
+
+    return 0;

Nit: I'd prefer to see the error handling immediately follow the function call whose result is being tested, and the non-failure-case code be not indented, i.e.:

c = find_cmd_tbl(argv[0], &cmd_blkc_sub[0], ARRAY_SIZE(cmd_blkc_sub)); if (!c)

    return CMD_RET_USAGE;

return c->cmd(cmdtp, flag, argc, argv);

Quoted 6 lines

disk/part.c +0 -0

@@ -268,6 +268,8 @@ void part_init(struct blk_desc *dev_desc)
      const int n_ents = ll_entry_count(struct part_driver, part_driver);
      struct part_driver *entry;
 

disk/part.c void part_init(struct blk_desc *dev_desc) · line 271

Quoted 1 line

disk/part.c +1 -0

+    blkcache_invalidate(dev_desc->if_type, dev_desc->devnum);

Doesn't this invalidate the cache far too often? I expect that function is called for command the user executes from the command-line, whereas it'd be nice if the cache persisted across commands. I suppose this is a reasonable (and very safe) first implementation though, and saves having to go through each storage provider type and find out the right place to detect media changes.

Quoted 8 lines

drivers/block/blkcache.c +6 -0

 
+struct block_cache_node {
+    struct list_head lh;
+    int iftype;
+    int devnum;
+    lbaint_t start;
+    lbaint_t blkcnt;

drivers/block/blkcache.c line 30

Quoted 10 lines

drivers/block/blkcache.c +10 -0

+    unsigned long blksz;
+    char *cache;
+};
+
+static LIST_HEAD(block_cache);
+
+static struct block_cache_stats _stats = {
+    .max_blocks_per_entry = 2,
+    .max_entries = 32
+};

Now is a good time to mention another reason why I don't like using a dynamically allocated linked list for this: Memory fragmentation. By dynamically allocating the cache, we could easily run into a situation

where the user runs a command that allocates memory and also adds to the block cache, then most of that memory gets freed when U-Boot returns to the command prompt, then the user runs the command again but it fails since it can't allocate the memory due to fragmentation of the heap. This is a real problem I've seen e.g. with the "ums" and "dfu" commands, since they might initialize the USB controller the first time they're run, which allocates some new memory. Statically allocation would avoid this.

include/blk.h struct blk_desc { · line 102

Quoted 6 lines

include/blk.h +4 -0

 
+int blkcache_read
+    (int iftype, int dev,
+     lbaint_t start, lbaint_t blkcnt,
+     unsigned long blksz, void *buffer);

Nit: The opening ( and first n arguments should be wrapped onto the same line as the function name.

Thanks again for the detailed review, Stephen.

Quoted 10 lines · Stephen Warren

Quoted 9 lines · Eric Nelson

Add a block device cache to speed up repeated reads of block devices by various filesystems.

disk/part.c +0 -0

@@ -268,6 +268,8 @@ void part_init(struct blk_desc *dev_desc)
       const int n_ents = ll_entry_count(struct part_driver, part_driver);
       struct part_driver *entry;
 

Quoted 8 lines

disk/part.c void part_init(struct blk_desc *dev_desc) · line 271

Quoted 1 line

disk/part.c +1 -0

+    blkcache_invalidate(dev_desc->if_type, dev_desc->devnum);

Doesn't this invalidate the cache far too often? I expect that function is called for command the user executes from the command-line, whereas it'd be nice if the cache persisted across commands. I suppose this is a reasonable (and very safe) first implementation though, and saves having to go through each storage provider type and find out the right place to detect media changes.

I'm not sure it does. I traced through the mmc initialization and it's only called when the card itself is initialized.

Quoted 22 lines

Quoted 8 lines

drivers/block/blkcache.c +6 -0

 
+struct block_cache_node {
+    struct list_head lh;
+    int iftype;
+    int devnum;
+    lbaint_t start;
+    lbaint_t blkcnt;

drivers/block/blkcache.c line 30

Quoted 10 lines

drivers/block/blkcache.c +10 -0

+    unsigned long blksz;
+    char *cache;
+};
+
+static LIST_HEAD(block_cache);
+
+static struct block_cache_stats _stats = {
+    .max_blocks_per_entry = 2,
+    .max_entries = 32
+};

Now is a good time to mention another reason why I don't like using a dynamically allocated linked list for this: Memory fragmentation. By dynamically allocating the cache, we could easily run into a situation

Quoted 8 lines

where the user runs a command that allocates memory and also adds to the block cache, then most of that memory gets freed when U-Boot returns to the command prompt, then the user runs the command again but it fails since it can't allocate the memory due to fragmentation of the heap. This is a real problem I've seen e.g. with the "ums" and "dfu" commands, since they might initialize the USB controller the first time they're run, which allocates some new memory. Statically allocation would avoid this.

We're going to allocate a block or set of blocks every time we allocate a new node for the list, so having the list in an array doesn't fix the problem.

While re-working the code, I also thought more about using an array and still don't see how the implementation doesn't get more complex.

The key bit is that the list is implemented in MRU order so invalidating the oldest is trivial.

Quoted 22 lines · Eric Nelson

Thanks again for the detailed review, Stephen.

Quoted 10 lines · Stephen Warren

Quoted 9 lines · Eric Nelson

Add a block device cache to speed up repeated reads of block devices by various filesystems.

disk/part.c +0 -0

@@ -268,6 +268,8 @@ void part_init(struct blk_desc *dev_desc)
       const int n_ents = ll_entry_count(struct part_driver,
 part_driver);
       struct part_driver *entry;
 

Quoted 8 lines

disk/part.c void part_init(struct blk_desc *dev_desc) · line 271

Quoted 1 line

disk/part.c +1 -0

+    blkcache_invalidate(dev_desc->if_type, dev_desc->devnum);

Doesn't this invalidate the cache far too often? I expect that function is called for command the user executes from the command-line, whereas it'd be nice if the cache persisted across commands. I suppose this is a reasonable (and very safe) first implementation though, and saves having to go through each storage provider type and find out the right place to detect media changes.

Quoted 2 lines

I'm not sure it does. I traced through the mmc initialization and it's only called when the card itself is initialized.

I don't believe U-Boot caches the partition structure across user commands. Doesn't each user command (e.g. part list, ls, load, save) first look up the block device, then scan the partition table, then "mount" the filesystem, then perform its action, then throw all that state away? Conversely, "mmc rescan" only happens under explicit user control. Still as I said, the current implementation is probably fine to start with, and at least is safe.

Quoted 31 lines

Quoted 30 lines

Quoted 8 lines

drivers/block/blkcache.c +6 -0

 
+struct block_cache_node {
+    struct list_head lh;
+    int iftype;
+    int devnum;
+    lbaint_t start;
+    lbaint_t blkcnt;

drivers/block/blkcache.c line 30

Quoted 10 lines

drivers/block/blkcache.c +10 -0

+    unsigned long blksz;
+    char *cache;
+};
+
+static LIST_HEAD(block_cache);
+
+static struct block_cache_stats _stats = {
+    .max_blocks_per_entry = 2,
+    .max_entries = 32
+};

Now is a good time to mention another reason why I don't like using a dynamically allocated linked list for this: Memory fragmentation. By dynamically allocating the cache, we could easily run into a situation where the user runs a command that allocates memory and also adds to the block cache, then most of that memory gets freed when U-Boot returns to the command prompt, then the user runs the command again but it fails since it can't allocate the memory due to fragmentation of the heap. This is a real problem I've seen e.g. with the "ums" and "dfu" commands, since they might initialize the USB controller the first time they're run, which allocates some new memory. Statically allocation would avoid this.

Quoted 3 lines

We're going to allocate a block or set of blocks every time we allocate a new node for the list, so having the list in an array doesn't fix the problem.

We could allocate the data storage for the block cache at the top of RAM before relocation, like many other things are allocated, and hence not use malloc() for that.

Quoted 5 lines

While re-working the code, I also thought more about using an array and still don't see how the implementation doesn't get more complex.

The key bit is that the list is implemented in MRU order so invalidating the oldest is trivial.

Yes, the MRU logic would make it more complex. Is that particularly useful, i.e. is it an intrinsic part of the speedup?

Hi Stephen,

Quoted 26 lines · Stephen Warren

Quoted 22 lines · Eric Nelson

Thanks again for the detailed review, Stephen.

Quoted 10 lines · Stephen Warren

Quoted 9 lines · Eric Nelson

Add a block device cache to speed up repeated reads of block devices by various filesystems.

disk/part.c +0 -0

@@ -268,6 +268,8 @@ void part_init(struct blk_desc *dev_desc)
        const int n_ents = ll_entry_count(struct part_driver,
 part_driver);
        struct part_driver *entry;
 

Quoted 8 lines

disk/part.c void part_init(struct blk_desc *dev_desc) · line 271

Quoted 1 line

disk/part.c +1 -0

+    blkcache_invalidate(dev_desc->if_type, dev_desc->devnum);

Doesn't this invalidate the cache far too often? I expect that function is called for command the user executes from the command-line, whereas it'd be nice if the cache persisted across commands. I suppose this is a reasonable (and very safe) first implementation though, and saves having to go through each storage provider type and find out the right place to detect media changes.

Quoted 2 lines

I'm not sure it does. I traced through the mmc initialization and it's only called when the card itself is initialized.

Quoted 8 lines

I don't believe U-Boot caches the partition structure across user commands. Doesn't each user command (e.g. part list, ls, load, save) first look up the block device, then scan the partition table, then "mount" the filesystem, then perform its action, then throw all that state away? Conversely, "mmc rescan" only happens under explicit user control. Still as I said, the current implementation is probably fine to start with, and at least is safe.

At least for MMC, this isn't the case. Various filesystem commands operate without calling part_init.

Quoted 31 lines

Quoted 31 lines

Quoted 30 lines

Quoted 8 lines

drivers/block/blkcache.c +6 -0

 
+struct block_cache_node {
+    struct list_head lh;
+    int iftype;
+    int devnum;
+    lbaint_t start;
+    lbaint_t blkcnt;

drivers/block/blkcache.c line 30

Quoted 10 lines

drivers/block/blkcache.c +10 -0

+    unsigned long blksz;
+    char *cache;
+};
+
+static LIST_HEAD(block_cache);
+
+static struct block_cache_stats _stats = {
+    .max_blocks_per_entry = 2,
+    .max_entries = 32
+};

Now is a good time to mention another reason why I don't like using a dynamically allocated linked list for this: Memory fragmentation. By dynamically allocating the cache, we could easily run into a situation where the user runs a command that allocates memory and also adds to the block cache, then most of that memory gets freed when U-Boot returns to the command prompt, then the user runs the command again but it fails since it can't allocate the memory due to fragmentation of the heap. This is a real problem I've seen e.g. with the "ums" and "dfu" commands, since they might initialize the USB controller the first time they're run, which allocates some new memory. Statically allocation would avoid this.

Quoted 7 lines

Quoted 3 lines

We're going to allocate a block or set of blocks every time we allocate a new node for the list, so having the list in an array doesn't fix the problem.

We could allocate the data storage for the block cache at the top of RAM before relocation, like many other things are allocated, and hence not use malloc() for that.

Hmmm. We seem to have gone from a discussion about data structures to type of allocation.

I'm interested in seeing how that works. Can you provide hints about what's doing this now?

Quoted 8 lines

Quoted 5 lines

While re-working the code, I also thought more about using an array and still don't see how the implementation doesn't get more complex.

The key bit is that the list is implemented in MRU order so invalidating the oldest is trivial.

Yes, the MRU logic would make it more complex. Is that particularly useful, i.e. is it an intrinsic part of the speedup?

It's not a question of speed with small numbers of entries. The code to handle eviction would just be more complex.

Given that the command "blkcache configure 0 0" will discard all cache and since both dfu and ums should properly have the cache disabled, I'd like to proceed as-is with the list and heap approach.

Quoted 4 lines · Eric Nelson

Quoted 3 lines · Stephen Warren

Quoted 2 lines · Eric Nelson

Quoted 1 line · Stephen Warren

On 03/28/2016 11:05 AM, Eric Nelson wrote:

Quoted 8 lines

Quoted 4 lines

We could allocate the data storage for the block cache at the top of RAM before relocation, like many other things are allocated, and hence not use malloc() for that.

Hmmm. We seem to have gone from a discussion about data structures to type of allocation.

Quoted 2 lines

I'm interested in seeing how that works. Can you provide hints about what's doing this now?

Something like common/board_f.c:reserve_mmu() and many other functions there. relocaddr starts at approximately the top of RAM, continually gets adjusted down as many static allocations are reserved, and eventually becomes the address that U-Boot is relocated to. Simply adding another entry into init_sequence_f[] for the disk cache might work.

Quoted 9 lines

Quoted 8 lines

Quoted 5 lines

While re-working the code, I also thought more about using an array and still don't see how the implementation doesn't get more complex.

The key bit is that the list is implemented in MRU order so invalidating the oldest is trivial.

Yes, the MRU logic would make it more complex. Is that particularly useful, i.e. is it an intrinsic part of the speedup?

Quoted 2 lines

It's not a question of speed with small numbers of entries. The code to handle eviction would just be more complex.

My thought was that if the eviction algorithm wasn't important (i.e. most of the speedup comes from have some (any) kind of cache, but the eviction algorithm makes little difference to the gain from having the cache), we could just drop MRU completely. If that's not possible, then indeed a list would make implementing MRU easier.

You could still do a list with a statically allocated set of list nodes, especially since the length of the list is bounded.

Quoted 3 lines

Given that the command "blkcache configure 0 0" will discard all cache and since both dfu and ums should properly have the cache disabled, I'd like to proceed as-is with the list and heap approach.

I don't understand "since both dfu and ums should properly have the cache disabled"; I didn't see anything that did that. Perhaps you're referring to the fact that writes invalidate the cache?

Eventually it seems better to keep the cache enabled for at least DFU to a filesystem (rather than raw block device) since presumably parsing the directory structure to write to a file for DFU would benefit from the cache just like anything else.

Hi Stephen,

Quoted 5 lines · Stephen Warren

Quoted 4 lines · Eric Nelson

Quoted 3 lines · Stephen Warren

Quoted 2 lines · Eric Nelson

Quoted 1 line · Stephen Warren

On 03/28/2016 11:05 AM, Eric Nelson wrote:

<snip>

Quoted 8 lines

Quoted 8 lines

Quoted 4 lines

We could allocate the data storage for the block cache at the top of RAM before relocation, like many other things are allocated, and hence not use malloc() for that.

Hmmm. We seem to have gone from a discussion about data structures to type of allocation.

Quoted 9 lines

Quoted 2 lines

I'm interested in seeing how that works. Can you provide hints about what's doing this now?

Something like common/board_f.c:reserve_mmu() and many other functions there. relocaddr starts at approximately the top of RAM, continually gets adjusted down as many static allocations are reserved, and eventually becomes the address that U-Boot is relocated to. Simply adding another entry into init_sequence_f[] for the disk cache might work.

Thanks for the pointer. I'll review that when time permits.

This would remove the opportunity to re-configure the cache though, right?

I'm not sure whether how important this feature is, and I think only time and use will tell.

I'd prefer to keep that ability at least for a cycle or two so that I and others can test.

Quoted 9 lines

Quoted 9 lines

Quoted 8 lines

Quoted 5 lines

While re-working the code, I also thought more about using an array and still don't see how the implementation doesn't get more complex.

The key bit is that the list is implemented in MRU order so invalidating the oldest is trivial.

Yes, the MRU logic would make it more complex. Is that particularly useful, i.e. is it an intrinsic part of the speedup?

Quoted 9 lines

Quoted 2 lines

It's not a question of speed with small numbers of entries. The code to handle eviction would just be more complex.

My thought was that if the eviction algorithm wasn't important (i.e. most of the speedup comes from have some (any) kind of cache, but the eviction algorithm makes little difference to the gain from having the cache), we could just drop MRU completely. If that's not possible, then indeed a list would make implementing MRU easier.

How would we decide which block to discard? I haven't traced enough to know what algorithm(s) might be best, but I can say that there's a preponderance of repeated accesses to the last-accessed block, especially in ext4.

Quoted 3 lines

You could still do a list with a statically allocated set of list nodes, especially since the length of the list is bounded.

Sure. A pooled allocator (pool of free nodes) works well with array-based allocation.

Having a fixed upper limit on the number of blocks would require additional checking unless we just sized it for (max entries * max blocks/entry).

Quoted 8 lines

Quoted 3 lines

Given that the command "blkcache configure 0 0" will discard all cache and since both dfu and ums should properly have the cache disabled, I'd like to proceed as-is with the list and heap approach.

I don't understand "since both dfu and ums should properly have the cache disabled"; I didn't see anything that did that. Perhaps you're referring to the fact that writes invalidate the cache?

Yes, but also that the host will cache blocks in the ums case, so having the cache enabled will only slow things down slightly by lots of memcpy's to cached blocks that won't be helpful.

I think I was a bit flippant by including dfu in this statement, since I haven't used it to access anything except SPI-NOR.

Quoted 4 lines

Eventually it seems better to keep the cache enabled for at least DFU to a filesystem (rather than raw block device) since presumably parsing the directory structure to write to a file for DFU would benefit from the cache just like anything else.

I'm not in a position to comment about dfu.

Quoted 8 lines · Eric Nelson

Hi Stephen,

Quoted 5 lines · Stephen Warren

Quoted 4 lines · Eric Nelson

Quoted 3 lines · Stephen Warren

Quoted 2 lines · Eric Nelson

Quoted 1 line · Stephen Warren

On 03/28/2016 11:05 AM, Eric Nelson wrote:

Quoted 12 lines

Yes, but also that the host will cache blocks in the ums case, so having the cache enabled will only slow things down slightly by lots of memcpy's to cached blocks that won't be helpful.

I think I was a bit flippant by including dfu in this statement, since I haven't used it to access anything except SPI-NOR.

Quoted 4 lines

Eventually it seems better to keep the cache enabled for at least DFU to a filesystem (rather than raw block device) since presumably parsing the directory structure to write to a file for DFU would benefit from the cache just like anything else.

Quoted 1 line

I'm not in a position to comment about dfu.

For the record, I think this discussion is good and important, but not a blocker for getting the initial functionality in.

Hi Stephen,

Quoted 5 lines · Stephen Warren

Quoted 4 lines · Eric Nelson

Quoted 3 lines · Stephen Warren

Quoted 2 lines · Eric Nelson

Quoted 1 line · Stephen Warren

On 03/28/2016 11:05 AM, Eric Nelson wrote:

<snip>

Quoted 8 lines

Quoted 8 lines

Quoted 4 lines

We could allocate the data storage for the block cache at the top of RAM before relocation, like many other things are allocated, and hence not use malloc() for that.

Hmmm. We seem to have gone from a discussion about data structures to type of allocation.

Quoted 9 lines

Quoted 2 lines

I'm interested in seeing how that works. Can you provide hints about what's doing this now?

Something like common/board_f.c:reserve_mmu() and many other functions there. relocaddr starts at approximately the top of RAM, continually gets adjusted down as many static allocations are reserved, and eventually becomes the address that U-Boot is relocated to. Simply adding another entry into init_sequence_f[] for the disk cache might work.

Thanks for the pointer. I'll review that when time permits.

This would remove the opportunity to re-configure the cache though, right?

I'm not sure whether how important this feature is, and I think only time and use will tell.

I'd prefer to keep that ability at least for a cycle or two so that I and others can test.

Quoted 9 lines

Quoted 9 lines

Quoted 8 lines

Quoted 5 lines

While re-working the code, I also thought more about using an array and still don't see how the implementation doesn't get more complex.

The key bit is that the list is implemented in MRU order so invalidating the oldest is trivial.

Yes, the MRU logic would make it more complex. Is that particularly useful, i.e. is it an intrinsic part of the speedup?

Quoted 9 lines

Quoted 2 lines

It's not a question of speed with small numbers of entries. The code to handle eviction would just be more complex.

My thought was that if the eviction algorithm wasn't important (i.e. most of the speedup comes from have some (any) kind of cache, but the eviction algorithm makes little difference to the gain from having the cache), we could just drop MRU completely. If that's not possible, then indeed a list would make implementing MRU easier.

How would we decide which block to discard? I haven't traced enough to know what algorithm(s) might be best, but I can say that there's a preponderance of repeated accesses to the last-accessed block, especially in ext4.

Quoted 29 lines · Eric Nelson

Quoted 5 lines · Stephen Warren

Quoted 4 lines · Eric Nelson

Quoted 3 lines · Stephen Warren

Quoted 2 lines · Eric Nelson

Quoted 1 line · Stephen Warren

On 03/28/2016 11:05 AM, Eric Nelson wrote:

<snip>

Quoted 19 lines

Quoted 11 lines

Quoted 5 lines

We could allocate the data storage for the block cache at the top of RAM
before relocation, like many other things are allocated, and hence not use malloc() for that.

Hmmm. We seem to have gone from a discussion about data structures to type of allocation.

I'm interested in seeing how that works. Can you provide hints about what's doing this now?

Something like common/board_f.c:reserve_mmu() and many other functions there. relocaddr starts at approximately the top of RAM, continually gets adjusted down as many static allocations are reserved, and eventually becomes the address that U-Boot is relocated to. Simply adding another entry into init_sequence_f[] for the disk cache might work.

Quoted 4 lines

Thanks for the pointer. I'll review that when time permits.

This would remove the opportunity to re-configure the cache though, right?

Well, it would make it impossible to use less RAM. One could use more by having a mix of the initial static allocation plus some additional dynamic allocation, but that might get a bit painful to manage.

It might be interesting to use the MMU more and allow de-fragmentation of VA space. That is, assuming there's much more VA space than RAM, such as is true on current 64-bit architectures. Then I wouldn't dislike dynamic allocation so much:-)

Quoted 26 lines

I'm not sure whether how important this feature is, and I think only time and use will tell.

I'd prefer to keep that ability at least for a cycle or two so that I and others can test.

Quoted 19 lines

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

While re-working the code, I also thought more about using an array and
still don't see how the implementation doesn't get more complex.

Quoted 8 lines

Quoted 5 lines

Quoted 2 lines

The key bit is that the list is implemented in MRU order so invalidating the oldest is trivial.

Yes, the MRU logic would make it more complex. Is that particularly useful, i.e. is it an intrinsic part of the speedup?

It's not a question of speed with small numbers of entries. The code to handle eviction would just be more complex.

My thought was that if the eviction algorithm wasn't important (i.e. most of the speedup comes from have some (any) kind of cache, but the eviction algorithm makes little difference to the gain from having the cache), we could just drop MRU completely. If that's not possible, then indeed a list would make implementing MRU easier.

Quoted 4 lines

How would we decide which block to discard? I haven't traced enough to know what algorithm(s) might be best, but I can say that there's a preponderance of repeated accesses to the last-accessed block, especially in ext4.

Perhaps just keep an index into the array, use that index any time something is written to the cache, and then increment it each time. Probably not anywhere near as optimal as MRU/LRU though.

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 32 and the maximum number of blocks per cache entry has a default of 2, which has shown to produce the best results on testing of ext4 and FAT filesystems.

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 <[email protected]>

Quoted 21 lines · Eric Nelson

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 32 and the maximum number of blocks per cache entry has a default of 2, which has shown to produce the best results on testing of ext4 and FAT filesystems.

Quoted 5 lines

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 <[email protected]>

Applied to u-boot/master, thanks!

Signed-off-by Eric Nelson <[email protected]>

Signed-off-by Eric Nelson <[email protected]>

Acked-by Stephen Warren <[email protected]>

Signed-off-by Eric Nelson <[email protected]>

Call blk_dread, blk_dwrite, blk_derase to ensure that the block cache is used if enabled and to remove build breakage when CONFIG_BLK is enabled.

Signed-off-by Eric Nelson <[email protected]>

Call blk_dread, blk_dwrite, blk_derase to ensure that the block cache is used if enabled and to remove build breakage when CONFIG_BLK is enabled.

Signed-off-by Eric Nelson <[email protected]>

Reviewed-by Tom Rini <[email protected]>

Call blk_dread, blk_dwrite, blk_derase to ensure that the block cache is used if enabled and to remove build breakage when CONFIG_BLK is enabled.

Signed-off-by Eric Nelson <[email protected]>

Call blk_dread, blk_dwrite, blk_derase to ensure that the block cache is used if enabled and to remove build breakage when CONFIG_BLK is enabled.

Signed-off-by Eric Nelson <[email protected]>

Reviewed-by Tom Rini <[email protected]>