1 /* 2 -*- linux-c -*- 3 drbd_receiver.c 4 This file is part of DRBD by Philipp Reisner and Lars Ellenberg. 5 6 Copyright (C) 2001-2008, LINBIT Information Technologies GmbH. 7 Copyright (C) 1999-2008, Philipp Reisner <philipp.reisner@linbit.com>. 8 Copyright (C) 2002-2008, Lars Ellenberg <lars.ellenberg@linbit.com>. 9 10 drbd is free software; you can redistribute it and/or modify 11 it under the terms of the GNU General Public License as published by 12 the Free Software Foundation; either version 2, or (at your option) 13 any later version. 14 15 drbd is distributed in the hope that it will be useful, 16 but WITHOUT ANY WARRANTY; without even the implied warranty of 17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 GNU General Public License for more details. 19 20 You should have received a copy of the GNU General Public License 21 along with drbd; see the file COPYING. If not, write to 22 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. 23 */ 24 25 #ifndef _DRBD_VLI_H 26 #define _DRBD_VLI_H 27 28 /* 29 * At a granularity of 4KiB storage represented per bit, 30 * and stroage sizes of several TiB, 31 * and possibly small-bandwidth replication, 32 * the bitmap transfer time can take much too long, 33 * if transmitted in plain text. 34 * 35 * We try to reduce the transferred bitmap information 36 * by encoding runlengths of bit polarity. 37 * 38 * We never actually need to encode a "zero" (runlengths are positive). 39 * But then we have to store the value of the first bit. 40 * The first bit of information thus shall encode if the first runlength 41 * gives the number of set or unset bits. 42 * 43 * We assume that large areas are either completely set or unset, 44 * which gives good compression with any runlength method, 45 * even when encoding the runlength as fixed size 32bit/64bit integers. 46 * 47 * Still, there may be areas where the polarity flips every few bits, 48 * and encoding the runlength sequence of those areas with fix size 49 * integers would be much worse than plaintext. 50 * 51 * We want to encode small runlength values with minimum code length, 52 * while still being able to encode a Huge run of all zeros. 53 * 54 * Thus we need a Variable Length Integer encoding, VLI. 55 * 56 * For some cases, we produce more code bits than plaintext input. 57 * We need to send incompressible chunks as plaintext, skip over them 58 * and then see if the next chunk compresses better. 59 * 60 * We don't care too much about "excellent" compression ratio for large 61 * runlengths (all set/all clear): whether we achieve a factor of 100 62 * or 1000 is not that much of an issue. 63 * We do not want to waste too much on short runlengths in the "noisy" 64 * parts of the bitmap, though. 65 * 66 * There are endless variants of VLI, we experimented with: 67 * * simple byte-based 68 * * various bit based with different code word length. 69 * 70 * To avoid yet an other configuration parameter (choice of bitmap compression 71 * algorithm) which was difficult to explain and tune, we just chose the one 72 * variant that turned out best in all test cases. 73 * Based on real world usage patterns, with device sizes ranging from a few GiB 74 * to several TiB, file server/mailserver/webserver/mysql/postgress, 75 * mostly idle to really busy, the all time winner (though sometimes only 76 * marginally better) is: 77 */ 78 79 /* 80 * encoding is "visualised" as 81 * __little endian__ bitstream, least significant bit first (left most) 82 * 83 * this particular encoding is chosen so that the prefix code 84 * starts as unary encoding the level, then modified so that 85 * 10 levels can be described in 8bit, with minimal overhead 86 * for the smaller levels. 87 * 88 * Number of data bits follow fibonacci sequence, with the exception of the 89 * last level (+1 data bit, so it makes 64bit total). The only worse code when 90 * encoding bit polarity runlength is 1 plain bits => 2 code bits. 91 prefix data bits max val Nº data bits 92 0 x 0x2 1 93 10 x 0x4 1 94 110 xx 0x8 2 95 1110 xxx 0x10 3 96 11110 xxx xx 0x30 5 97 111110 xx xxxxxx 0x130 8 98 11111100 xxxxxxxx xxxxx 0x2130 13 99 11111110 xxxxxxxx xxxxxxxx xxxxx 0x202130 21 100 11111101 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xx 0x400202130 34 101 11111111 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 56 102 * maximum encodable value: 0x100000400202130 == 2**56 + some */ 103 104 /* compression "table": 105 transmitted x 0.29 106 as plaintext x ........................ 107 x ........................ 108 x ........................ 109 x 0.59 0.21........................ 110 x ........................................................ 111 x .. c ................................................... 112 x 0.44.. o ................................................... 113 x .......... d ................................................... 114 x .......... e ................................................... 115 X............. ................................................... 116 x.............. b ................................................... 117 2.0x............... i ................................................... 118 #X................ t ................................................... 119 #................. s ........................... plain bits .......... 120 -+----------------------------------------------------------------------- 121 1 16 32 64 122 */ 123 124 /* LEVEL: (total bits, prefix bits, prefix value), 125 * sorted ascending by number of total bits. 126 * The rest of the code table is calculated at compiletime from this. */ 127 128 /* fibonacci data 1, 1, ... */ 129 #define VLI_L_1_1() do { \ 130 LEVEL( 2, 1, 0x00); \ 131 LEVEL( 3, 2, 0x01); \ 132 LEVEL( 5, 3, 0x03); \ 133 LEVEL( 7, 4, 0x07); \ 134 LEVEL(10, 5, 0x0f); \ 135 LEVEL(14, 6, 0x1f); \ 136 LEVEL(21, 8, 0x3f); \ 137 LEVEL(29, 8, 0x7f); \ 138 LEVEL(42, 8, 0xbf); \ 139 LEVEL(64, 8, 0xff); \ 140 } while (0) 141 142 /* finds a suitable level to decode the least significant part of in. 143 * returns number of bits consumed. 144 * 145 * BUG() for bad input, as that would mean a buggy code table. */ 146 static inline int vli_decode_bits(u64 *out, const u64 in) 147 { 148 u64 adj = 1; 149 150 #define LEVEL(t,b,v) \ 151 do { \ 152 if ((in & ((1 << b) -1)) == v) { \ 153 *out = ((in & ((~0ULL) >> (64-t))) >> b) + adj; \ 154 return t; \ 155 } \ 156 adj += 1ULL << (t - b); \ 157 } while (0) 158 159 VLI_L_1_1(); 160 161 /* NOT REACHED, if VLI_LEVELS code table is defined properly */ 162 BUG(); 163 #undef LEVEL 164 } 165 166 /* return number of code bits needed, 167 * or negative error number */ 168 static inline int __vli_encode_bits(u64 *out, const u64 in) 169 { 170 u64 max = 0; 171 u64 adj = 1; 172 173 if (in == 0) 174 return -EINVAL; 175 176 #define LEVEL(t,b,v) do { \ 177 max += 1ULL << (t - b); \ 178 if (in <= max) { \ 179 if (out) \ 180 *out = ((in - adj) << b) | v; \ 181 return t; \ 182 } \ 183 adj = max + 1; \ 184 } while (0) 185 186 VLI_L_1_1(); 187 188 return -EOVERFLOW; 189 #undef LEVEL 190 } 191 192 #undef VLI_L_1_1 193 194 /* code from here down is independend of actually used bit code */ 195 196 /* 197 * Code length is determined by some unique (e.g. unary) prefix. 198 * This encodes arbitrary bit length, not whole bytes: we have a bit-stream, 199 * not a byte stream. 200 */ 201 202 /* for the bitstream, we need a cursor */ 203 struct bitstream_cursor { 204 /* the current byte */ 205 u8 *b; 206 /* the current bit within *b, nomalized: 0..7 */ 207 unsigned int bit; 208 }; 209 210 /* initialize cursor to point to first bit of stream */ 211 static inline void bitstream_cursor_reset(struct bitstream_cursor *cur, void *s) 212 { 213 cur->b = s; 214 cur->bit = 0; 215 } 216 217 /* advance cursor by that many bits; maximum expected input value: 64, 218 * but depending on VLI implementation, it may be more. */ 219 static inline void bitstream_cursor_advance(struct bitstream_cursor *cur, unsigned int bits) 220 { 221 bits += cur->bit; 222 cur->b = cur->b + (bits >> 3); 223 cur->bit = bits & 7; 224 } 225 226 /* the bitstream itself knows its length */ 227 struct bitstream { 228 struct bitstream_cursor cur; 229 unsigned char *buf; 230 size_t buf_len; /* in bytes */ 231 232 /* for input stream: 233 * number of trailing 0 bits for padding 234 * total number of valid bits in stream: buf_len * 8 - pad_bits */ 235 unsigned int pad_bits; 236 }; 237 238 static inline void bitstream_init(struct bitstream *bs, void *s, size_t len, unsigned int pad_bits) 239 { 240 bs->buf = s; 241 bs->buf_len = len; 242 bs->pad_bits = pad_bits; 243 bitstream_cursor_reset(&bs->cur, bs->buf); 244 } 245 246 static inline void bitstream_rewind(struct bitstream *bs) 247 { 248 bitstream_cursor_reset(&bs->cur, bs->buf); 249 memset(bs->buf, 0, bs->buf_len); 250 } 251 252 /* Put (at most 64) least significant bits of val into bitstream, and advance cursor. 253 * Ignores "pad_bits". 254 * Returns zero if bits == 0 (nothing to do). 255 * Returns number of bits used if successful. 256 * 257 * If there is not enough room left in bitstream, 258 * leaves bitstream unchanged and returns -ENOBUFS. 259 */ 260 static inline int bitstream_put_bits(struct bitstream *bs, u64 val, const unsigned int bits) 261 { 262 unsigned char *b = bs->cur.b; 263 unsigned int tmp; 264 265 if (bits == 0) 266 return 0; 267 268 if ((bs->cur.b + ((bs->cur.bit + bits -1) >> 3)) - bs->buf >= bs->buf_len) 269 return -ENOBUFS; 270 271 /* paranoia: strip off hi bits; they should not be set anyways. */ 272 if (bits < 64) 273 val &= ~0ULL >> (64 - bits); 274 275 *b++ |= (val & 0xff) << bs->cur.bit; 276 277 for (tmp = 8 - bs->cur.bit; tmp < bits; tmp += 8) 278 *b++ |= (val >> tmp) & 0xff; 279 280 bitstream_cursor_advance(&bs->cur, bits); 281 return bits; 282 } 283 284 /* Fetch (at most 64) bits from bitstream into *out, and advance cursor. 285 * 286 * If more than 64 bits are requested, returns -EINVAL and leave *out unchanged. 287 * 288 * If there are less than the requested number of valid bits left in the 289 * bitstream, still fetches all available bits. 290 * 291 * Returns number of actually fetched bits. 292 */ 293 static inline int bitstream_get_bits(struct bitstream *bs, u64 *out, int bits) 294 { 295 u64 val; 296 unsigned int n; 297 298 if (bits > 64) 299 return -EINVAL; 300 301 if (bs->cur.b + ((bs->cur.bit + bs->pad_bits + bits -1) >> 3) - bs->buf >= bs->buf_len) 302 bits = ((bs->buf_len - (bs->cur.b - bs->buf)) << 3) 303 - bs->cur.bit - bs->pad_bits; 304 305 if (bits == 0) { 306 *out = 0; 307 return 0; 308 } 309 310 /* get the high bits */ 311 val = 0; 312 n = (bs->cur.bit + bits + 7) >> 3; 313 /* n may be at most 9, if cur.bit + bits > 64 */ 314 /* which means this copies at most 8 byte */ 315 if (n) { 316 memcpy(&val, bs->cur.b+1, n - 1); 317 val = le64_to_cpu(val) << (8 - bs->cur.bit); 318 } 319 320 /* we still need the low bits */ 321 val |= bs->cur.b[0] >> bs->cur.bit; 322 323 /* and mask out bits we don't want */ 324 val &= ~0ULL >> (64 - bits); 325 326 bitstream_cursor_advance(&bs->cur, bits); 327 *out = val; 328 329 return bits; 330 } 331 332 /* encodes @in as vli into @bs; 333 334 * return values 335 * > 0: number of bits successfully stored in bitstream 336 * -ENOBUFS @bs is full 337 * -EINVAL input zero (invalid) 338 * -EOVERFLOW input too large for this vli code (invalid) 339 */ 340 static inline int vli_encode_bits(struct bitstream *bs, u64 in) 341 { 342 u64 code = code; 343 int bits = __vli_encode_bits(&code, in); 344 345 if (bits <= 0) 346 return bits; 347 348 return bitstream_put_bits(bs, code, bits); 349 } 350 351 #endif 352