| /* | |
| -*- linux-c -*- | |
| drbd_receiver.c | |
| This file is part of DRBD by Philipp Reisner and Lars Ellenberg. | |
| Copyright (C) 2001-2008, LINBIT Information Technologies GmbH. | |
| Copyright (C) 1999-2008, Philipp Reisner <philipp.reisner@linbit.com>. | |
| Copyright (C) 2002-2008, Lars Ellenberg <lars.ellenberg@linbit.com>. | |
| drbd 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. | |
| drbd 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 drbd; see the file COPYING. If not, write to | |
| the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. | |
| */ | |
| #ifndef _DRBD_VLI_H | |
| #define _DRBD_VLI_H | |
| /* | |
| * At a granularity of 4KiB storage represented per bit, | |
| * and stroage sizes of several TiB, | |
| * and possibly small-bandwidth replication, | |
| * the bitmap transfer time can take much too long, | |
| * if transmitted in plain text. | |
| * | |
| * We try to reduce the transferred bitmap information | |
| * by encoding runlengths of bit polarity. | |
| * | |
| * We never actually need to encode a "zero" (runlengths are positive). | |
| * But then we have to store the value of the first bit. | |
| * The first bit of information thus shall encode if the first runlength | |
| * gives the number of set or unset bits. | |
| * | |
| * We assume that large areas are either completely set or unset, | |
| * which gives good compression with any runlength method, | |
| * even when encoding the runlength as fixed size 32bit/64bit integers. | |
| * | |
| * Still, there may be areas where the polarity flips every few bits, | |
| * and encoding the runlength sequence of those areas with fix size | |
| * integers would be much worse than plaintext. | |
| * | |
| * We want to encode small runlength values with minimum code length, | |
| * while still being able to encode a Huge run of all zeros. | |
| * | |
| * Thus we need a Variable Length Integer encoding, VLI. | |
| * | |
| * For some cases, we produce more code bits than plaintext input. | |
| * We need to send incompressible chunks as plaintext, skip over them | |
| * and then see if the next chunk compresses better. | |
| * | |
| * We don't care too much about "excellent" compression ratio for large | |
| * runlengths (all set/all clear): whether we achieve a factor of 100 | |
| * or 1000 is not that much of an issue. | |
| * We do not want to waste too much on short runlengths in the "noisy" | |
| * parts of the bitmap, though. | |
| * | |
| * There are endless variants of VLI, we experimented with: | |
| * * simple byte-based | |
| * * various bit based with different code word length. | |
| * | |
| * To avoid yet an other configuration parameter (choice of bitmap compression | |
| * algorithm) which was difficult to explain and tune, we just chose the one | |
| * variant that turned out best in all test cases. | |
| * Based on real world usage patterns, with device sizes ranging from a few GiB | |
| * to several TiB, file server/mailserver/webserver/mysql/postgress, | |
| * mostly idle to really busy, the all time winner (though sometimes only | |
| * marginally better) is: | |
| */ | |
| /* | |
| * encoding is "visualised" as | |
| * __little endian__ bitstream, least significant bit first (left most) | |
| * | |
| * this particular encoding is chosen so that the prefix code | |
| * starts as unary encoding the level, then modified so that | |
| * 10 levels can be described in 8bit, with minimal overhead | |
| * for the smaller levels. | |
| * | |
| * Number of data bits follow fibonacci sequence, with the exception of the | |
| * last level (+1 data bit, so it makes 64bit total). The only worse code when | |
| * encoding bit polarity runlength is 1 plain bits => 2 code bits. | |
| prefix data bits max val Nº data bits | |
| 0 x 0x2 1 | |
| 10 x 0x4 1 | |
| 110 xx 0x8 2 | |
| 1110 xxx 0x10 3 | |
| 11110 xxx xx 0x30 5 | |
| 111110 xx xxxxxx 0x130 8 | |
| 11111100 xxxxxxxx xxxxx 0x2130 13 | |
| 11111110 xxxxxxxx xxxxxxxx xxxxx 0x202130 21 | |
| 11111101 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xx 0x400202130 34 | |
| 11111111 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 56 | |
| * maximum encodable value: 0x100000400202130 == 2**56 + some */ | |
| /* compression "table": | |
| transmitted x 0.29 | |
| as plaintext x ........................ | |
| x ........................ | |
| x ........................ | |
| x 0.59 0.21........................ | |
| x ........................................................ | |
| x .. c ................................................... | |
| x 0.44.. o ................................................... | |
| x .......... d ................................................... | |
| x .......... e ................................................... | |
| X............. ................................................... | |
| x.............. b ................................................... | |
| 2.0x............... i ................................................... | |
| #X................ t ................................................... | |
| #................. s ........................... plain bits .......... | |
| -+----------------------------------------------------------------------- | |
| 1 16 32 64 | |
| */ | |
| /* LEVEL: (total bits, prefix bits, prefix value), | |
| * sorted ascending by number of total bits. | |
| * The rest of the code table is calculated at compiletime from this. */ | |
| /* fibonacci data 1, 1, ... */ | |
| #define VLI_L_1_1() do { \ | |
| LEVEL( 2, 1, 0x00); \ | |
| LEVEL( 3, 2, 0x01); \ | |
| LEVEL( 5, 3, 0x03); \ | |
| LEVEL( 7, 4, 0x07); \ | |
| LEVEL(10, 5, 0x0f); \ | |
| LEVEL(14, 6, 0x1f); \ | |
| LEVEL(21, 8, 0x3f); \ | |
| LEVEL(29, 8, 0x7f); \ | |
| LEVEL(42, 8, 0xbf); \ | |
| LEVEL(64, 8, 0xff); \ | |
| } while (0) | |
| /* finds a suitable level to decode the least significant part of in. | |
| * returns number of bits consumed. | |
| * | |
| * BUG() for bad input, as that would mean a buggy code table. */ | |
| static inline int vli_decode_bits(u64 *out, const u64 in) | |
| { | |
| u64 adj = 1; | |
| #define LEVEL(t,b,v) \ | |
| do { \ | |
| if ((in & ((1 << b) -1)) == v) { \ | |
| *out = ((in & ((~0ULL) >> (64-t))) >> b) + adj; \ | |
| return t; \ | |
| } \ | |
| adj += 1ULL << (t - b); \ | |
| } while (0) | |
| VLI_L_1_1(); | |
| /* NOT REACHED, if VLI_LEVELS code table is defined properly */ | |
| BUG(); | |
| #undef LEVEL | |
| } | |
| /* return number of code bits needed, | |
| * or negative error number */ | |
| static inline int __vli_encode_bits(u64 *out, const u64 in) | |
| { | |
| u64 max = 0; | |
| u64 adj = 1; | |
| if (in == 0) | |
| return -EINVAL; | |
| #define LEVEL(t,b,v) do { \ | |
| max += 1ULL << (t - b); \ | |
| if (in <= max) { \ | |
| if (out) \ | |
| *out = ((in - adj) << b) | v; \ | |
| return t; \ | |
| } \ | |
| adj = max + 1; \ | |
| } while (0) | |
| VLI_L_1_1(); | |
| return -EOVERFLOW; | |
| #undef LEVEL | |
| } | |
| #undef VLI_L_1_1 | |
| /* code from here down is independend of actually used bit code */ | |
| /* | |
| * Code length is determined by some unique (e.g. unary) prefix. | |
| * This encodes arbitrary bit length, not whole bytes: we have a bit-stream, | |
| * not a byte stream. | |
| */ | |
| /* for the bitstream, we need a cursor */ | |
| struct bitstream_cursor { | |
| /* the current byte */ | |
| u8 *b; | |
| /* the current bit within *b, nomalized: 0..7 */ | |
| unsigned int bit; | |
| }; | |
| /* initialize cursor to point to first bit of stream */ | |
| static inline void bitstream_cursor_reset(struct bitstream_cursor *cur, void *s) | |
| { | |
| cur->b = s; | |
| cur->bit = 0; | |
| } | |
| /* advance cursor by that many bits; maximum expected input value: 64, | |
| * but depending on VLI implementation, it may be more. */ | |
| static inline void bitstream_cursor_advance(struct bitstream_cursor *cur, unsigned int bits) | |
| { | |
| bits += cur->bit; | |
| cur->b = cur->b + (bits >> 3); | |
| cur->bit = bits & 7; | |
| } | |
| /* the bitstream itself knows its length */ | |
| struct bitstream { | |
| struct bitstream_cursor cur; | |
| unsigned char *buf; | |
| size_t buf_len; /* in bytes */ | |
| /* for input stream: | |
| * number of trailing 0 bits for padding | |
| * total number of valid bits in stream: buf_len * 8 - pad_bits */ | |
| unsigned int pad_bits; | |
| }; | |
| static inline void bitstream_init(struct bitstream *bs, void *s, size_t len, unsigned int pad_bits) | |
| { | |
| bs->buf = s; | |
| bs->buf_len = len; | |
| bs->pad_bits = pad_bits; | |
| bitstream_cursor_reset(&bs->cur, bs->buf); | |
| } | |
| static inline void bitstream_rewind(struct bitstream *bs) | |
| { | |
| bitstream_cursor_reset(&bs->cur, bs->buf); | |
| memset(bs->buf, 0, bs->buf_len); | |
| } | |
| /* Put (at most 64) least significant bits of val into bitstream, and advance cursor. | |
| * Ignores "pad_bits". | |
| * Returns zero if bits == 0 (nothing to do). | |
| * Returns number of bits used if successful. | |
| * | |
| * If there is not enough room left in bitstream, | |
| * leaves bitstream unchanged and returns -ENOBUFS. | |
| */ | |
| static inline int bitstream_put_bits(struct bitstream *bs, u64 val, const unsigned int bits) | |
| { | |
| unsigned char *b = bs->cur.b; | |
| unsigned int tmp; | |
| if (bits == 0) | |
| return 0; | |
| if ((bs->cur.b + ((bs->cur.bit + bits -1) >> 3)) - bs->buf >= bs->buf_len) | |
| return -ENOBUFS; | |
| /* paranoia: strip off hi bits; they should not be set anyways. */ | |
| if (bits < 64) | |
| val &= ~0ULL >> (64 - bits); | |
| *b++ |= (val & 0xff) << bs->cur.bit; | |
| for (tmp = 8 - bs->cur.bit; tmp < bits; tmp += 8) | |
| *b++ |= (val >> tmp) & 0xff; | |
| bitstream_cursor_advance(&bs->cur, bits); | |
| return bits; | |
| } | |
| /* Fetch (at most 64) bits from bitstream into *out, and advance cursor. | |
| * | |
| * If more than 64 bits are requested, returns -EINVAL and leave *out unchanged. | |
| * | |
| * If there are less than the requested number of valid bits left in the | |
| * bitstream, still fetches all available bits. | |
| * | |
| * Returns number of actually fetched bits. | |
| */ | |
| static inline int bitstream_get_bits(struct bitstream *bs, u64 *out, int bits) | |
| { | |
| u64 val; | |
| unsigned int n; | |
| if (bits > 64) | |
| return -EINVAL; | |
| if (bs->cur.b + ((bs->cur.bit + bs->pad_bits + bits -1) >> 3) - bs->buf >= bs->buf_len) | |
| bits = ((bs->buf_len - (bs->cur.b - bs->buf)) << 3) | |
| - bs->cur.bit - bs->pad_bits; | |
| if (bits == 0) { | |
| *out = 0; | |
| return 0; | |
| } | |
| /* get the high bits */ | |
| val = 0; | |
| n = (bs->cur.bit + bits + 7) >> 3; | |
| /* n may be at most 9, if cur.bit + bits > 64 */ | |
| /* which means this copies at most 8 byte */ | |
| if (n) { | |
| memcpy(&val, bs->cur.b+1, n - 1); | |
| val = le64_to_cpu(val) << (8 - bs->cur.bit); | |
| } | |
| /* we still need the low bits */ | |
| val |= bs->cur.b[0] >> bs->cur.bit; | |
| /* and mask out bits we don't want */ | |
| val &= ~0ULL >> (64 - bits); | |
| bitstream_cursor_advance(&bs->cur, bits); | |
| *out = val; | |
| return bits; | |
| } | |
| /* encodes @in as vli into @bs; | |
| * return values | |
| * > 0: number of bits successfully stored in bitstream | |
| * -ENOBUFS @bs is full | |
| * -EINVAL input zero (invalid) | |
| * -EOVERFLOW input too large for this vli code (invalid) | |
| */ | |
| static inline int vli_encode_bits(struct bitstream *bs, u64 in) | |
| { | |
| u64 code = code; | |
| int bits = __vli_encode_bits(&code, in); | |
| if (bits <= 0) | |
| return bits; | |
| return bitstream_put_bits(bs, code, bits); | |
| } | |
| #endif |