From patchwork Thu Jun 22 22:01:39 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nick Terrell X-Patchwork-Id: 9805349 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 81B9060329 for ; Thu, 22 Jun 2017 22:04:13 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 76CD82866D for ; Thu, 22 Jun 2017 22:04:13 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 6AB6B2866F; Thu, 22 Jun 2017 22:04:13 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 833AE2866D for ; Thu, 22 Jun 2017 22:04:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753862AbdFVWEI (ORCPT ); Thu, 22 Jun 2017 18:04:08 -0400 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:50540 "EHLO mx0b-00082601.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753815AbdFVWEF (ORCPT ); Thu, 22 Jun 2017 18:04:05 -0400 Received: from pps.filterd (m0109332.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.0.20/8.16.0.20) with SMTP id v5MLwnR0001621 for ; Thu, 22 Jun 2017 15:04:00 -0700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-type; s=facebook; bh=BpaZ2G3vJPyIgfxp6HyBdxNBtNkvt4AV3MRUzm///YY=; b=osipq4+m4fXd230AfKylBiN9/qGmPYmTdUPQRWIpB635GAWs0prUFJKz4Wcf8aA9gNcV GsX93JJsOVEds1QP3+4dU8Em1EgFvWVUNJQgCGICEs3m32FGDdRTwAE4RNpRTlwRFE8C GKFf4MpHNxAxYyYpMtWdzLjII88WDpHVMVQ= Received: from mail.thefacebook.com ([199.201.64.23]) by mx0a-00082601.pphosted.com with ESMTP id 2b8m9t8cfj-1 (version=TLSv1 cipher=ECDHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Thu, 22 Jun 2017 15:04:00 -0700 Received: from PRN-CHUB02.TheFacebook.com (192.168.16.12) by PRN-CHUB14.TheFacebook.com (192.168.16.24) with Microsoft SMTP Server (TLS) id 14.3.319.2; Thu, 22 Jun 2017 15:03:58 -0700 Received: from mx-out.facebook.com (192.168.52.123) by PRN-CHUB02.TheFacebook.com (192.168.16.12) with Microsoft SMTP Server (TLS) id 14.3.319.2; Thu, 22 Jun 2017 15:03:53 -0700 Received: from facebook.com (2401:db00:21:6023:face:0:9:0) by mx-out.facebook.com (2401:db00:2050:5102:face:0000:003b:0000) with ESMTP id ad7d842e579611e7a4da0f7588574c86-d65398f0 for ; Thu, 22 Jun 2017 15:03:52 -0700 Received: by dev10183.prn2.facebook.com (Postfix, from userid 32154) id C1E1F21446C7; Thu, 22 Jun 2017 15:03:51 -0700 (PDT) Smtp-Origin-Hostprefix: dev From: Nick Terrell Smtp-Origin-Hostname: dev10183.prn2.facebook.com To: Nick Terrell CC: , Chris Mason , Yann Collet , , , , Sean Purcell Smtp-Origin-Cluster: prn2c22 Subject: [PATCH 4/4] squashfs: Add zstd support Date: Thu, 22 Jun 2017 15:01:39 -0700 Message-ID: <20170622220139.2328978-4-terrelln@fb.com> X-Mailer: git-send-email 2.9.3 In-Reply-To: <20170622220139.2328978-1-terrelln@fb.com> References: <20170622220139.2328978-1-terrelln@fb.com> X-FB-Internal: Safe MIME-Version: 1.0 X-Proofpoint-Spam-Reason: safe X-FB-Internal: Safe X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:, , definitions=2017-06-22_09:, , signatures=0 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Add zstd compression and decompression support to SquashFS. zstd is a great fit for SquashFS because it can compress at ratios approaching xz, while decompressing twice as fast as zlib. For SquashFS in particular, it can decompress as fast as lzo and lz4. It also has the flexibility to turn down the compression ratio for faster compression times. The compression benchmark is run on the file tree from the SquashFS archive found in ubuntu-16.10-desktop-amd64.iso [1]. It uses `mksquashfs` with the default block size (128 KB) and and various compression algorithms/levels. xz and zstd are also benchmarked with 256 KB blocks. The decompression benchmark times how long it takes to `tar` the file tree into `/dev/null`. See the benchmark file in the upstream zstd source repository located under `contrib/linux-kernel/squashfs-benchmark.sh` [2] for details. I ran the benchmarks on a Ubuntu 14.04 VM with 2 cores and 4 GiB of RAM. The VM is running on a MacBook Pro with a 3.1 GHz Intel Core i7 processor, 16 GB of RAM, and a SSD. | Method | Ratio | Compression MB/s | Decompression MB/s | |----------------|-------|------------------|--------------------| | gzip | 2.92 | 15 | 128 | | lzo | 2.64 | 9.5 | 217 | | lz4 | 2.12 | 94 | 218 | | xz | 3.43 | 5.5 | 35 | | xz 256 KB | 3.53 | 5.4 | 40 | | zstd 1 | 2.71 | 96 | 210 | | zstd 5 | 2.93 | 69 | 198 | | zstd 10 | 3.01 | 41 | 225 | | zstd 15 | 3.13 | 11.4 | 224 | | zstd 16 256 KB | 3.24 | 8.1 | 210 | This patch was written by Sean Purcell , but I will be taking over the submission process. [1] http://releases.ubuntu.com/16.10/ [2] https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/squashfs-benchmark.sh zstd source repository: https://github.com/facebook/zstd Cc: Sean Purcell Signed-off-by: Nick Terrell --- fs/squashfs/Kconfig | 14 +++++ fs/squashfs/Makefile | 1 + fs/squashfs/decompressor.c | 7 +++ fs/squashfs/decompressor.h | 4 ++ fs/squashfs/squashfs_fs.h | 1 + fs/squashfs/zstd_wrapper.c | 150 +++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 177 insertions(+) create mode 100644 fs/squashfs/zstd_wrapper.c -- 2.9.3 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html diff --git a/fs/squashfs/Kconfig b/fs/squashfs/Kconfig index ffb093e..1adb334 100644 --- a/fs/squashfs/Kconfig +++ b/fs/squashfs/Kconfig @@ -165,6 +165,20 @@ config SQUASHFS_XZ If unsure, say N. +config SQUASHFS_ZSTD + bool "Include support for ZSTD compressed file systems" + depends on SQUASHFS + select ZSTD_DECOMPRESS + help + Saying Y here includes support for reading Squashfs file systems + compressed with ZSTD compression. ZSTD gives better compression than + the default ZLIB compression, while using less CPU. + + ZSTD is not the standard compression used in Squashfs and so most + file systems will be readable without selecting this option. + + If unsure, say N. + config SQUASHFS_4K_DEVBLK_SIZE bool "Use 4K device block size?" depends on SQUASHFS diff --git a/fs/squashfs/Makefile b/fs/squashfs/Makefile index 246a6f3..6655631 100644 --- a/fs/squashfs/Makefile +++ b/fs/squashfs/Makefile @@ -15,3 +15,4 @@ squashfs-$(CONFIG_SQUASHFS_LZ4) += lz4_wrapper.o squashfs-$(CONFIG_SQUASHFS_LZO) += lzo_wrapper.o squashfs-$(CONFIG_SQUASHFS_XZ) += xz_wrapper.o squashfs-$(CONFIG_SQUASHFS_ZLIB) += zlib_wrapper.o +squashfs-$(CONFIG_SQUASHFS_ZSTD) += zstd_wrapper.o diff --git a/fs/squashfs/decompressor.c b/fs/squashfs/decompressor.c index d2bc136..8366398 100644 --- a/fs/squashfs/decompressor.c +++ b/fs/squashfs/decompressor.c @@ -65,6 +65,12 @@ static const struct squashfs_decompressor squashfs_zlib_comp_ops = { }; #endif +#ifndef CONFIG_SQUASHFS_ZSTD +static const struct squashfs_decompressor squashfs_zstd_comp_ops = { + NULL, NULL, NULL, NULL, ZSTD_COMPRESSION, "zstd", 0 +}; +#endif + static const struct squashfs_decompressor squashfs_unknown_comp_ops = { NULL, NULL, NULL, NULL, 0, "unknown", 0 }; @@ -75,6 +81,7 @@ static const struct squashfs_decompressor *decompressor[] = { &squashfs_lzo_comp_ops, &squashfs_xz_comp_ops, &squashfs_lzma_unsupported_comp_ops, + &squashfs_zstd_comp_ops, &squashfs_unknown_comp_ops }; diff --git a/fs/squashfs/decompressor.h b/fs/squashfs/decompressor.h index a25713c..0f5a8e4 100644 --- a/fs/squashfs/decompressor.h +++ b/fs/squashfs/decompressor.h @@ -58,4 +58,8 @@ extern const struct squashfs_decompressor squashfs_lzo_comp_ops; extern const struct squashfs_decompressor squashfs_zlib_comp_ops; #endif +#ifdef CONFIG_SQUASHFS_ZSTD +extern const struct squashfs_decompressor squashfs_zstd_comp_ops; +#endif + #endif diff --git a/fs/squashfs/squashfs_fs.h b/fs/squashfs/squashfs_fs.h index 506f4ba..24d12fd 100644 --- a/fs/squashfs/squashfs_fs.h +++ b/fs/squashfs/squashfs_fs.h @@ -241,6 +241,7 @@ struct meta_index { #define LZO_COMPRESSION 3 #define XZ_COMPRESSION 4 #define LZ4_COMPRESSION 5 +#define ZSTD_COMPRESSION 6 struct squashfs_super_block { __le32 s_magic; diff --git a/fs/squashfs/zstd_wrapper.c b/fs/squashfs/zstd_wrapper.c new file mode 100644 index 0000000..8cb7c76 --- /dev/null +++ b/fs/squashfs/zstd_wrapper.c @@ -0,0 +1,150 @@ +/* + * Squashfs - a compressed read only filesystem for Linux + * + * Copyright (c) 2016-present, Facebook, Inc. + * All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2, + * or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * zstd_wrapper.c + */ + +#include +#include +#include +#include +#include + +#include "squashfs_fs.h" +#include "squashfs_fs_sb.h" +#include "squashfs.h" +#include "decompressor.h" +#include "page_actor.h" + +struct workspace { + void *mem; + size_t mem_size; +}; + +static void *zstd_init(struct squashfs_sb_info *msblk, void *buff) +{ + struct workspace *wksp = kmalloc(sizeof(*wksp), GFP_KERNEL); + if (wksp == NULL) + goto failed; + wksp->mem_size = ZSTD_DStreamWorkspaceBound(max_t(size_t, + msblk->block_size, SQUASHFS_METADATA_SIZE)); + wksp->mem = vmalloc(wksp->mem_size); + if (wksp->mem == NULL) + goto failed; + + return wksp; + +failed: + ERROR("Failed to allocate zstd workspace\n"); + kfree(wksp); + return ERR_PTR(-ENOMEM); +} + + +static void zstd_free(void *strm) +{ + struct workspace *wksp = strm; + + if (wksp) + vfree(wksp->mem); + kfree(wksp); +} + + +static int zstd_uncompress(struct squashfs_sb_info *msblk, void *strm, + struct buffer_head **bh, int b, int offset, int length, + struct squashfs_page_actor *output) +{ + struct workspace *wksp = strm; + ZSTD_DStream *stream; + size_t total_out = 0; + size_t zstd_err; + int k = 0; + ZSTD_inBuffer in_buf = { NULL, 0, 0 }; + ZSTD_outBuffer out_buf = { NULL, 0, 0 }; + + stream = ZSTD_initDStream(wksp->mem_size, wksp->mem, wksp->mem_size); + + if (!stream) { + ERROR("Failed to initialize zstd decompressor\n"); + goto out; + } + + out_buf.size = PAGE_SIZE; + out_buf.dst = squashfs_first_page(output); + + do { + if (in_buf.pos == in_buf.size && k < b) { + int avail = min(length, msblk->devblksize - offset); + length -= avail; + in_buf.src = bh[k]->b_data + offset; + in_buf.size = avail; + in_buf.pos = 0; + offset = 0; + } + + if (out_buf.pos == out_buf.size) { + out_buf.dst = squashfs_next_page(output); + if (out_buf.dst == NULL) { + /* shouldn't run out of pages before stream is + * done */ + squashfs_finish_page(output); + goto out; + } + out_buf.pos = 0; + out_buf.size = PAGE_SIZE; + } + + total_out -= out_buf.pos; + zstd_err = ZSTD_decompressStream(stream, &out_buf, &in_buf); + total_out += out_buf.pos; /* add the additional data produced */ + + if (in_buf.pos == in_buf.size && k < b) + put_bh(bh[k++]); + } while (zstd_err != 0 && !ZSTD_isError(zstd_err)); + + squashfs_finish_page(output); + + if (ZSTD_isError(zstd_err)) { + ERROR("zstd decompression error: %d\n", + (int)ZSTD_getErrorCode(zstd_err)); + goto out; + } + + if (k < b) + goto out; + + return (int)total_out; + +out: + for (; k < b; k++) + put_bh(bh[k]); + + return -EIO; +} + +const struct squashfs_decompressor squashfs_zstd_comp_ops = { + .init = zstd_init, + .free = zstd_free, + .decompress = zstd_uncompress, + .id = ZSTD_COMPRESSION, + .name = "zstd", + .supported = 1 +};