Received: from list by lists.gnu.org with archive (Exim 4.71) id 1U2JtA-00089t-BR for mharc-grub-devel@gnu.org; Mon, 04 Feb 2013 06:07:04 -0500 Received: from eggs.gnu.org ([208.118.235.92]:57354) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1U2Jt5-00089d-Fh for grub-devel@gnu.org; Mon, 04 Feb 2013 06:07:02 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1U2Jt1-00005a-27 for grub-devel@gnu.org; Mon, 04 Feb 2013 06:06:59 -0500 Received: from mmserver.massimo-maggi.eu ([94.23.66.90]:34926 helo=mmserver.localdomain) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1U2Jt0-00005Q-PV for grub-devel@gnu.org; Mon, 04 Feb 2013 06:06:55 -0500 Received: from [IPv6:2001:b05:f:ffff::25] (unknown [IPv6:2001:b05:f:ffff::25]) by mmserver.localdomain (Postfix) with ESMTPSA id B8AA63C0 for ; Mon, 4 Feb 2013 12:06:53 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=massimo-maggi.eu; s=mmserver; t=1359976014; bh=RKik849pUyxFeAf2xh10cwxYabTtuvQdeTv8XAg390M=; h=Date:From:To:Subject:References:In-Reply-To; b=Tp67StWpD6m+YvCxOMfmfE7IlGEj47ZzyvpCGUq6OxJuy7dHJQdfY95U8NMUSmwGC tFpuiToX2EJ/yHYjICW7FWomT9d0mgVLtpB4gRg1z76ylhlvXIev4swRu5q/mFYEE1 fuOLMLSHSOf8UqSrWwR0wRDDpgRS98rm/1GVuTmU= Message-ID: <510F9710.6040600@massimo-maggi.eu> Date: Mon, 04 Feb 2013 12:10:08 +0100 From: Massimo Maggi User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130128 Thunderbird/17.0.2 MIME-Version: 1.0 To: grub-devel@gnu.org Subject: [PATCH 5/5] LZ4 compression in ZFS References: In-Reply-To: X-Enigmail-Version: 1.5 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="----enig2ABXANENMTFKKLBRQUNIC" X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 94.23.66.90 X-BeenThere: grub-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list Reply-To: The development of GNU GRUB List-Id: The development of GNU GRUB List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 04 Feb 2013 11:07:03 -0000 This is an OpenPGP/MIME signed message (RFC 4880 and 3156) ------enig2ABXANENMTFKKLBRQUNIC Content-Type: multipart/mixed; boundary="------------010209020205020509080507" This is a multi-part message in MIME format. --------------010209020205020509080507 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable IllumOS issue #3035 - original commit a6f561b4aee75d0d028e7b36b151c8ed8a86bc76 Author: Saso Kiselkov Ported-by: Massimo Maggi --- Makefile.util.def | 1 + grub-core/Makefile.core.def | 1 + grub-core/fs/zfs/zfs.c | 7 +- grub-core/fs/zfs/zfs_lz4.c | 321 ++++++++++++++++++++++++++++++++++++++++++++ include/grub/zfs/zio.h | 1 + po/POTFILES.in | 1 + 6 files changed, 330 insertions(+), 2 deletions(-) create mode 100644 grub-core/fs/zfs/zfs_lz4.c diff --git a/Makefile.util.def b/Makefile.util.def index 3ee5e4e..3ab043a 100644 --- a/Makefile.util.def +++ b/Makefile.util.def @@ -96,6 +96,7 @@ library =3D { common =3D grub-core/fs/zfs/zfs.c; common =3D grub-core/fs/zfs/zfsinfo.c; common =3D grub-core/fs/zfs/zfs_lzjb.c; + common =3D grub-core/fs/zfs/zfs_lz4.c; common =3D grub-core/fs/zfs/zfs_sha256.c; common =3D grub-core/fs/zfs/zfs_fletcher.c; common =3D grub-core/lib/envblk.c; diff --git a/grub-core/Makefile.core.def b/grub-core/Makefile.core.def index 4609a4b..94dc6c9 100644 --- a/grub-core/Makefile.core.def +++ b/grub-core/Makefile.core.def @@ -1224,6 +1224,7 @@ module =3D { name =3D zfs; common =3D fs/zfs/zfs.c; common =3D fs/zfs/zfs_lzjb.c; + common =3D fs/zfs/zfs_lz4.c; common =3D fs/zfs/zfs_sha256.c; common =3D fs/zfs/zfs_fletcher.c; }; diff --git a/grub-core/fs/zfs/zfs.c b/grub-core/fs/zfs/zfs.c index cf10534..aaf1af4 100644 --- a/grub-core/fs/zfs/zfs.c +++ b/grub-core/fs/zfs/zfs.c @@ -154,11 +154,13 @@ ZAP_LEAF_ENTRY(zap_leaf_phys_t *l, int bs, int idx)= /* - * Decompression Entry - lzjb + * Decompression Entry - lzjb & lz4 */ extern grub_err_t lzjb_decompress (void *, void *, grub_size_t, grub_size_t); +extern grub_err_t lz4_decompress (void *, void *, grub_size_t, grub_size_t); + typedef grub_err_t zfs_decomp_func_t (void *s_start, void *d_start, grub_size_t s_len, grub_size_t d_len); typedef struct decomp_entry @@ -278,7 +280,7 @@ grub_crypto_cipher_handle_t (*grub_zfs_load_key) (const struct grub_zfs_key *key * to be listed here since grub opens pools in read-only mode. */ static const char *spa_feature_names[] =3D { - "max.test:feat1",NULL + "org.illumos:lz4_compress",NULL }; static int @@ -344,6 +346,7 @@ static decomp_entry_t decomp_table[ZIO_COMPRESS_FUNCTIONS] =3D { {"gzip-8", zlib_decompress}, /* ZIO_COMPRESS_GZIP8 */ {"gzip-9", zlib_decompress}, /* ZIO_COMPRESS_GZIP9 */ {"zle", zle_decompress}, /* ZIO_COMPRESS_ZLE */ + {"lz4", lz4_decompress}, /* ZIO_COMPRESS_LZ4 */ }; static grub_err_t zio_read_data (blkptr_t * bp, grub_zfs_endian_t endia= n, diff --git a/grub-core/fs/zfs/zfs_lz4.c b/grub-core/fs/zfs/zfs_lz4.c new file mode 100644 index 0000000..f199434 --- /dev/null +++ b/grub-core/fs/zfs/zfs_lz4.c @@ -0,0 +1,321 @@ +/* + * LZ4 - Fast LZ compression algorithm + * Header File + * Copyright (C) 2011-2013, Yann Collet. + * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions ar= e + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaime= r + * in the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR= + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,= + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,= + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY= + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE= + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * You can contact the author at : + * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html + * - LZ4 source repository : http://code.google.com/p/lz4/ + */ + +#include +#include +#include +#include + +static int LZ4_uncompress_unknownOutputSize(const char *source, char *de= st, + int isize, int maxOutputSize); + +/* + * CPU Feature Detection + */ + +/* 32 or 64 bits ? */ +#if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || \= + defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || \ + defined(__LP64__) || defined(_LP64)) +#define LZ4_ARCH64 1 +#else +#define LZ4_ARCH64 0 +#endif + +/* + * Little Endian or Big Endian? + * Note: overwrite the below #define if you know your architecture endianess. + */ +#if (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || \ + defined(_BIG_ENDIAN) || defined(_ARCH_PPC) || defined(__PPC__) || \ + defined(__PPC) || defined(PPC) || defined(__powerpc__) || \ + defined(__powerpc) || defined(powerpc) || \ + ((defined(__BYTE_ORDER__)&&(__BYTE_ORDER__ =3D=3D __ORDER_BIG_ENDIAN__)= ))) +#define LZ4_BIG_ENDIAN 1 +#else + /* + * Little Endian assumed. PDP Endian and other very rare endian format + * are unsupported. + */ +#endif + +/* + * Compiler Options + */ + +#if __STDC_VERSION__ >=3D 199901L /* C99 */ +/* "restrict" is a known keyword */ +#else +/* Disable restrict */ +#ifndef restrict +#define restrict /* Only if somebody already didn't take care of that.*/= +#endif +#endif + +#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) + +#define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) \ + | (((x) & 0xffu) << 8))) + +#if (GCC_VERSION >=3D 302) || (__INTEL_COMPILER >=3D 800) || defined(__c= lang__) +#define expect(expr, value) (__builtin_expect((expr), (value))) +#else +#define expect(expr, value) (expr) +#endif + +#define likely(expr) expect((expr) !=3D 0, 1) +#define unlikely(expr) expect((expr) !=3D 0, 0) + +/* Basic types */ +#define BYTE grub_uint8_t +#define U16 grub_uint16_t +#define U32 grub_uint32_t +#define S32 grub_int32_t +#define U64 grub_uint64_t +typedef grub_size_t size_t; + +typedef struct _U16_S { + U16 v; +} U16_S; +typedef struct _U32_S { + U32 v; +} U32_S; +typedef struct _U64_S { + U64 v; +} U64_S; + +#define A64(x) (((U64_S *)(x))->v) +#define A32(x) (((U32_S *)(x))->v) +#define A16(x) (((U16_S *)(x))->v) + +/* + * Constants + */ +#define MINMATCH 4 + +#define COPYLENGTH 8 +#define LASTLITERALS 5 + +#define ML_BITS 4 +#define ML_MASK ((1U< s_len) + return grub_error(GRUB_ERR_BAD_FS,"lz4 decompression failed."); + + /* + * Returns 0 on success (decompression function returned non-negative) + * and appropriate error on failure (decompression function returned negative). + */ + return (LZ4_uncompress_unknownOutputSize((char*)s_start + 4, d_start, bufsiz, + d_len) < 0)?grub_error(GRUB_ERR_BAD_FS,"lz4 decompression failed.")= :0; +} + +static int +LZ4_uncompress_unknownOutputSize(const char *source, + char *dest, int isize, int maxOutputSize) +{ + /* Local Variables */ + const BYTE *restrict ip =3D (const BYTE *) source; + const BYTE *const iend =3D ip + isize; + const BYTE *restrict ref; + + BYTE *restrict op =3D (BYTE *) dest; + BYTE *const oend =3D op + maxOutputSize; + BYTE *cpy; + + size_t dec[] =3D { 0, 3, 2, 3, 0, 0, 0, 0 }; + + /* Main Loop */ + while (ip < iend) { + BYTE token; + int length; + + /* get runlength */ + token =3D *ip++; + if ((length =3D (token >> ML_BITS)) =3D=3D RUN_MASK) { + int s =3D 255; + while ((ip < iend) && (s =3D=3D 255)) { + s =3D *ip++; + length +=3D s; + } + } + /* copy literals */ + cpy =3D op + length; + if ((cpy > oend - COPYLENGTH) || + (ip + length > iend - COPYLENGTH)) { + if (cpy > oend) + /* + * Error: request to write beyond destination + * buffer. + */ + goto _output_error; + if (ip + length > iend) + /* + * Error : request to read beyond source + * buffer. + */ + goto _output_error; + grub_memcpy(op, ip, length); + op +=3D length; + ip +=3D length; + if (ip < iend) + /* Error : LZ4 format violation */ + goto _output_error; + /* Necessarily EOF, due to parsing restrictions. */ + break; + } + LZ4_WILDCOPY(ip, op, cpy); + ip -=3D (op - cpy); + op =3D cpy; + + /* get offset */ + LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip); + ip +=3D 2; + if (ref < (BYTE * const) dest) + /* + * Error: offset creates reference outside of + * destination buffer. + */ + goto _output_error; + + /* get matchlength */ + if ((length =3D (token & ML_MASK)) =3D=3D ML_MASK) { + while (ip < iend) { + int s =3D *ip++; + length +=3D s; + if (s =3D=3D 255) + continue; + break; + } + } + /* copy repeated sequence */ + if unlikely(op - ref < STEPSIZE) { +#if LZ4_ARCH64 + size_t dec2table[] =3D { 0, 0, 0, -1, 0, 1, 2, 3 }; + size_t dec2 =3D dec2table[op - ref]; +#else + const int dec2 =3D 0; +#endif + *op++ =3D *ref++; + *op++ =3D *ref++; + *op++ =3D *ref++; + *op++ =3D *ref++; + ref -=3D dec[op - ref]; + A32(op) =3D A32(ref); + op +=3D STEPSIZE - 4; + ref -=3D dec2; + } else { + LZ4_COPYSTEP(ref, op); + } + cpy =3D op + length - (STEPSIZE - 4); + if (cpy > oend - COPYLENGTH) { + if (cpy > oend) + /* + * Error: request to write outside of + * destination buffer. + */ + goto _output_error; + LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH)); + while (op < cpy) + *op++ =3D *ref++; + op =3D cpy; + if (op =3D=3D oend) + /* + * Check EOF (should never happen, since last + * 5 bytes are supposed to be literals). + */ + break; + continue; + } + LZ4_SECURECOPY(ref, op, cpy); + op =3D cpy; /* correction */ + } + + /* end of decoding */ + return (int)(((char *)op) - dest); + + /* write overflow error detected */ + _output_error: + return (int)(-(((char *)ip) - source)); +} diff --git a/include/grub/zfs/zio.h b/include/grub/zfs/zio.h index b1c46da..8fad2cc 100644 --- a/include/grub/zfs/zio.h +++ b/include/grub/zfs/zio.h @@ -88,6 +88,7 @@ enum zio_compress { ZIO_COMPRESS_GZIP8, ZIO_COMPRESS_GZIP9, ZIO_COMPRESS_ZLE, + ZIO_COMPRESS_LZ4, ZIO_COMPRESS_FUNCTIONS }; diff --git a/po/POTFILES.in b/po/POTFILES.in index 01cc53c..a0a5d60 100644 --- a/po/POTFILES.in +++ b/po/POTFILES.in @@ -174,6 +174,7 @@ ./grub-core/fs/zfs/zfs_fletcher.c ./grub-core/fs/zfs/zfsinfo.c ./grub-core/fs/zfs/zfs_lzjb.c +./grub-core/fs/zfs/zfs_lz4.c ./grub-core/fs/zfs/zfs_sha256.c ./grub-core/gdb/cstub.c ./grub-core/gdb/gdb.c --=20 1.8.1.1 --------------010209020205020509080507 Content-Type: text/plain; charset=ISO-8859-1; name="Attached Message Part" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="Attached Message Part" --------------010209020205020509080507-- ------enig2ABXANENMTFKKLBRQUNIC Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.19 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQEcBAEBAgAGBQJRD5cRAAoJEEO073X3hHDOJL8H/0vpn/58TAfM1VCHS7wKS4v2 +0LQKY4NvTmBumwGY4BKjyKInKW1lop5j44U8FRTW4j/sUMeeVrDo47eVWedX+UR bdVPlAyUP8CcEtg5hsMETN+DpQ2HTpVeKr1Z/MJcvWC4GzSuS246XfN4VPn4z5AM 7o9o43AhdaoPFI+7xEjdE+ACIqiln/DWmE/FsHzQVYu1xnf/ECBAB1Ws6hrAP5Mh xuSvCImt8ekCYvY2qwqivYvowzFkTxCb0NUBHUJn/7ZjZrY7JHfb5R8rjuhPtZso 6CKGOOgrPYD60C7JOzS5+uOlaft/rTEcdyhd+BwSC4jLKmvT3WFdxjm6hDr0PQ0= =YYQz -----END PGP SIGNATURE----- ------enig2ABXANENMTFKKLBRQUNIC--