[POC PATCH] Speeding up squashfs with a compressed block cache

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[POC PATCH] Speeding up squashfs with a compressed block cache

Jeff Epler
The attached patch adds a cache of compressed blocks to the xz backend.
Basically, before actually compressing a block, the cryptographic
checksum (SHA256) of the block is computed; the compressed content is
looked up by the hash, and if it is found it is used directly.  
Otherwise, the block is compressed and its compressed form is put in the
cache.

I chose xz because this is the compressor selected by vmdebootstrap in
debian stretch, and I made it unconditional because there's not a
convenient way to pass a flag all the way from the program I'm
interested in running (lwr) down to vmdebootstrap.

The hash library I chose is librhash, in part because it does not seem
to have license problems when combined with GPLv2 software like
mksquashfs (MIT license), unlike OpenSSL.

The organization of this patch is quick and dirty, making it a proof of
concept rather than something I believe is ready for inclusion in
squashfs.  However, I think it shows real promise and if the community
is interested I'll work with you to put it into an acceptable form.

These refinements might include moving it so it can apply to all
compressors; managing the cache so that it does not exceed a selected
size; choosing a higher-performance cryptographich hash; making the
cache location selectable; choosing a different hash or hash library; or
using a proper key-value store instead of ~/.cache.

In my timings, it has been quite effective.  Running live-wrapper (lwr)
twice to produce a 1.1GB image gave the following timings:

Unmodified: 1081.67user 39.64system 5:44.23elapsed 325%CPU
Uncached:   1092.58user 41.91system 5:51.95elapsed 322%CPU
Cached:      217.48user 24.47system 3:54.03elapsed 103%CPU

As expected, there is a slight increase in runtime when there is no
compressed block cache, due to the time to compute the cryptographic
checksum of each block (computing SHA256 with /usr/bin/sha256sum runs at
262MB/s on this same machine) and writing to the cache, but when there
are matching compressed blocks in the cache, the speedup is dramatic.

lwr [roughly] runs vmdebootstrap, then additional commands inside the
fresh image, mksquashfs, adds debian installer components, and finally
creates a hybrid iso image with all of the above.  So reducing the
elapsed time by 1/3 with any single change is pretty amazing.

In my lwr test I made sure disk was "cold" with sysctl vm.drop_caches=3
before each run, and removed everything from ~/.cache before the first
run.  The host is Intel(R) Core(TM) i7-4790K CPU @ 4.00GHz and was
otherwise idle during the tests.  Packages are coming out of a fast
local proxy server, and the temporary directory where vmdebootstrap
works is a ramdisk (/dev/shm remounted -o dev).

Index: squashfs-tools-4.3/squashfs-tools/Makefile
===================================================================
--- squashfs-tools-4.3.orig/squashfs-tools/Makefile
+++ squashfs-tools-4.3/squashfs-tools/Makefile
@@ -153,7 +153,7 @@ ifeq ($(XZ_SUPPORT),1)
 CFLAGS += -DXZ_SUPPORT
 MKSQUASHFS_OBJS += xz_wrapper.o
 UNSQUASHFS_OBJS += xz_wrapper.o
-LIBS += -llzma
+LIBS += -llzma -lrhash
 COMPRESSORS += xz
 endif
 
Index: squashfs-tools-4.3/squashfs-tools/xz_wrapper.c
===================================================================
--- squashfs-tools-4.3.orig/squashfs-tools/xz_wrapper.c
+++ squashfs-tools-4.3/squashfs-tools/xz_wrapper.c
@@ -22,14 +22,62 @@
  * http://tukaani.org/xz/
  */
 
+#include <assert.h>
+#include <errno.h>
+#include <fcntl.h>
 #include <stdio.h>
 #include <string.h>
 #include <stdlib.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
 #include <lzma.h>
+#include <rhash.h>
 
 #include "squashfs_fs.h"
 #include "xz_wrapper.h"
 #include "compressor.h"
+#include "error.h"
+
+static int read_bytes(int fd, void *buff, int bytes)
+{
+ int res, count;
+
+ for(count = 0; count < bytes; count += res) {
+ res = read(fd, buff + count, bytes - count);
+ if(res < 1) {
+ if(res == 0)
+ goto bytes_read;
+ else if(errno != EINTR) {
+ ERROR("Read failed because %s\n",
+ strerror(errno));
+ return -1;
+ } else
+ res = 0;
+ }
+ }
+
+bytes_read:
+ return count;
+}
+
+static int write_bytes(int fd, const void *buff, int bytes) {
+ int res, count;
+
+ for(count = 0; count < bytes; count += res) {
+ res = write(fd, buff + count, bytes - count);
+ if(res == -1) {
+ if(errno != EINTR) {
+ ERROR("Write failed because %s\n",
+ strerror(errno));
+ return -1;
+ }
+ res = 0;
+ }
+ }
+
+ return 0;
+}
 
 static struct bcj bcj[] = {
  { "x86", LZMA_FILTER_X86, 0 },
@@ -432,6 +480,71 @@ failed:
  return -1;
 }
 
+static void hash_block(const void *message, size_t message_size,
+ char *hash_out, size_t hash_size)
+{
+ struct rhash_context *ctx;
+        assert(rhash_get_hash_length(RHASH_SHA256) < hash_size);
+
+ ctx = rhash_init(RHASH_SHA256);
+ rhash_update(ctx, (const unsigned char *)message, message_size);
+ rhash_final(ctx, 0);
+ rhash_print(hash_out, ctx, 0, RHPR_UPPERCASE);
+ rhash_free(ctx);
+}
+
+static char *kvstore_filename_by_hash(const char *hash, const char *suffix,
+ char *filename_out, size_t filename_size)
+{
+ snprintf(filename_out, filename_size, "%s/.cache/squashfs.%s%s",
+ getenv("HOME"), hash, suffix);
+ return filename_out;
+}
+
+static char *kvstore_find_block_by_hash(const char *hash, size_t *size_out)
+{
+ int fd;
+ char filename[65536];
+ char *result;
+ struct stat st;
+
+ fd = open(kvstore_filename_by_hash(hash, "",
+ filename, sizeof(filename)), O_RDONLY);
+ if(fd < 0) return NULL;
+
+ if(fstat(fd, &st) < 0) {
+ close(fd);
+ return NULL;
+ }
+
+ *size_out = (size_t)st.st_size;
+
+ result = malloc(*size_out);
+ read_bytes(fd, result, *size_out);
+
+ close(fd);
+ return result;
+}
+
+static void kvstore_store_block_by_hash(const char *hash, const void *data,
+ size_t data_size)
+{
+ char tmp_filename[65536], final_filename[65536];
+ int fd = open(kvstore_filename_by_hash(hash, ".tmp",
+ tmp_filename, sizeof(tmp_filename)),
+ O_WRONLY | O_CREAT | O_EXCL, 0666);
+ if(fd < 0) return;
+
+ if(write_bytes(fd, data, data_size) < 0) {
+ close(fd);
+ unlink(tmp_filename);
+ }
+ rename(tmp_filename, kvstore_filename_by_hash(hash, "",
+ final_filename, sizeof(final_filename)));
+
+ close(fd);
+}
+
 
 static int xz_compress(void *strm, void *dest, void *src,  int size,
  int block_size, int *error)
@@ -440,6 +553,17 @@ static int xz_compress(void *strm, void
         lzma_ret res = 0;
  struct xz_stream *stream = strm;
  struct filter *selected = NULL;
+ void *cached = NULL;
+ size_t cached_size = 0;
+ char hash[130];
+
+ hash_block(src, size, hash, sizeof(hash));
+
+ if((cached = kvstore_find_block_by_hash(hash, &cached_size))) {
+ memcpy(dest, cached, cached_size);
+ free(cached);
+ return (int) cached_size;
+ }
 
  stream->filter[0].buffer = dest;
 
@@ -472,6 +596,8 @@ static int xz_compress(void *strm, void
  if(selected->buffer != dest)
  memcpy(dest, selected->buffer, selected->length);
 
+ kvstore_store_block_by_hash(hash, selected->buffer, selected->length);
+
  return (int) selected->length;
 
 failed:

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Squashfs-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/squashfs-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [POC PATCH] Speeding up squashfs with a compressed block cache

Jeff Epler
On Tue, Jun 27, 2017 at 08:29:03AM -0500, Jeff Epler wrote:
>The attached patch adds a cache of compressed blocks to the xz backend.
>Basically, before actually compressing a block, the cryptographic
>checksum (SHA256) of the block is computed; the compressed content is
>looked up by the hash, and if it is found it is used directly.  
>Otherwise, the block is compressed and its compressed form is put in
>the cache.

.. I see that something (probably my mailer) munged the patch.  A
correct copy (though one that also includes a change in the debian
packaging metadata, that can just be deleted) is at
https://emergent.unpythonic.net/files/sandbox/compression-cache

Jeff

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Squashfs-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/squashfs-devel
Loading...