Skip to content

VIP35: Retire libvgz

Jump to bottom Edit New page
Dridi Boukelmoune edited this page Jul 3, 2024 · 2 revisions

Synopsis

We currently vendor zlib rebranded as libvgz in our source tree, patched to collect the bit offsets in the gzip stream:

  • start bit (beginning of the first deflate block)
  • last bit (beginning of the last deflate block)
  • stop bit (end of the last deflate block)

Knowing these bit offsets allow us to stitch multiple gzip streams into a single logical gzip stream for ESI delivery.

We established that with a plain zlib we can collect all three bit offsets during decompression, but only the start and last bit offsets can reliably be collected during compression.

See https://github.com/varnishcache/varnish-cache/pull/3873.

Why

Our patch to zlib has already been submitted and rejected a long time ago, so keeping our fork guarantees a maintenance burden. It prevents us from relying on the OS-supplied library. It also prevents us from switching to other zlib-compatible libraries, claiming significantly better performance:

Note: just after the submission of this VIP, Mark Adler added the missing piece of the puzzle for our use case, so we should be able to eventually transition to a regular zlib and retire libvgz.

How

We can keep zlib for decompression and only change the testGunzip operation to work on deflate block boundaries (Z_BLOCK flag). For compression, we can rely on libslz (https://github.com/wtarreau/libslz) and collect all three bit offsets, at the expense of emitting an empty block if we already are at a block boundary at the end of the compression. The purpose of libslz is to offer a fast deflate compression with a constant memory footprint, which better fits Varnish's worker model than zlib. It relies solely on static huffman trees, at the expense of the compression ratio.

Some benefits of libslz:

  • simple design and API
  • easier to vendor in our source code (self-contained slz.c and slz.h files)
  • usable without modifications (see appendix below)
  • all the primitives we need seem to be exposed
    • able to collect bit offsets
    • we can bring our own gzip header
    • can flush a block to align at a byte boundary (ESI parsing)
    • we can inject existing deflate blocks (ESI stitching)
  • the project is more likely to accept patches

Some drawbacks:

  • the API is not safe, the documentation explains how to avoid overflows
    • however, it is not too hard in practice, see appendix
  • it may not be available on all platforms we care about
    • but it is much easier to embed than zlib
  • lower compression ratio
  • probably needs two buffers in some cases
    • for the input to improve compression
    • for the output when none is available (VDP?)
  • requires two libraries for gzip instead of one
  • to be completed as we learn more...

Using libslz for compression would render gzip_level and gzip_memlevel parameters obsolete.

Collecting bit offsets using libslz was successfully tested on a corpus of 176344 files, ranging from an empty file to 732MB of input for a single file. The test program compresses its standard input with libslz and writes the gzip stream to its standard output. At the end, it prints "vslz: ..." to display the input size, output size, and bit offsets (similarly to Gzip logs in Varnish). If the result is different between libslz and zlib, another line is printed with "zlib: ..." to compare the values. The program can also be linked to libvgz, giving us a definitive verdict on accuracy. As an added bonus, it pads the gzip header with a random comment length to mitigate the BREACH attack.

It can be tested this way:

$ ./vslz </dev/null | zcat -v | sha256sum - /dev/null
vslz: Gzip 190 0 1440 1440 1450
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  -
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  /dev/null
$ ./vslz </dev/null | zcat -v | sha256sum - /dev/null
vslz: Gzip 129 0 952 952 962
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  -
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  /dev/null
$ ./vslz </dev/null | zcat -v | sha256sum - /dev/null
vslz: Gzip 157 0 1176 1176 1186
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  -
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  /dev/null
$ ./vslz </dev/null | zcat -v | sha256sum - /dev/null
vslz: Gzip 225 0 1720 1720 1730
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  -
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  /dev/null
$ ./vslz </dev/null | zcat -v | sha256sum - /dev/null
vslz: Gzip 224 0 1712 1712 1722
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  -
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  /dev/null
$ ./vslz </dev/null | zcat -v | sha256sum - /dev/null
vslz: Gzip 47 0 296 296 306
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  -
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855  /dev/null

We can see that zcat recognizes vslz's output as proper gzip and the original input (or lack thereof) is not altered in the process. We can also see that only offsets derived from libslz are printed, meaning that they match the ones derived from zlib. And finally, we can see that offsets change between invocations, showing that the BREACH mitigation is working as expected.

It should be noted that in the context of Varnish, we would rather add noise during delivery, especially for cache hits.

It can be tested on its own source code too:

$ ./vslz <vslz.c | zcat -v | sha256sum - vslz.c
vslz: Gzip 3742 7167 1464 29855 29865
898959c50dcef584e8c19813b928b828c93879cedcfc5343af16f369d2aa9e5d  -
898959c50dcef584e8c19813b928b828c93879cedcfc5343af16f369d2aa9e5d  vslz.c

To test it on a large number of files, a simple shell script can be used:

$ ./vslz-test.sh $SOME_DIRECTORIES >vslz-test.log
$ grep -B2 '^zlib:' vslz-test.log
<nothing>

Appendix

To compile with zlib:

$ c99 -g -lslz -lz -o vslz vslz.c

vslz.c

/**
 * Author: Dridi
 */

#include <errno.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

#include <slz.h>

#ifdef USE_LIBVGZ
#  define Z_PREFIX
#  include <vgz.h>
#else
#  include <zlib.h>
#endif

#define cache_param_gzip_buffer 32768

/* libslz-based compression */

struct vslz {
	/* TODO: magic */
	struct slz_stream	strm[1];
	uint8_t			*buf;		/* output buffer */
	size_t			buf_len;	/* safe output size*/
	size_t			out_len;	/* available output */
	size_t			out_total;	/* total output */
	size_t			start_bit;	/* first block bit offset */
	size_t			last_bit;	/* last block bit offset */
	size_t			stop_bit;	/* last end-of-block offset */
};

static int
vslz_init(struct vslz *vslz, void *buf, size_t len, unsigned compress)
{

	/* TODO: assert */
	if (len < 512) {
		errno = ENOSPC;
		return (-1);
	}

	memset(vslz, 0, sizeof *vslz);
	if (slz_init(vslz->strm, compress != 0, SLZ_FMT_GZIP)) {
		errno = EINVAL;
		return (-1);
	}
	vslz->buf = buf;
	vslz->buf_len = len - 32; /* headroom rounded up to a power of 2 */
	return (0);
}

static size_t
vslz_space(const struct vslz *vslz)
{

	/* TODO: assert */
	if (vslz->buf_len > vslz->out_len)
		return (vslz->buf_len - vslz->out_len);
	return (0); /* headroom available to end block or finish gzip stream */
}

static void /* TODO: should fail if len > space */
vslz_encode(struct vslz *vslz, const void *ptr, size_t len)
{
	void *dest;
	size_t out;
	int more;

	/* TODO: assert */
	if (vslz->strm->state == SLZ_ST_INIT)
		vslz->start_bit = 80;
	dest = vslz->buf + vslz->out_len;
	more = (len > 0); /* poor man's end of block trigger */
	out = slz_encode(vslz->strm, dest, ptr, len, more);
	vslz->out_total += out;
	vslz->out_len += out; /* TODO: assert */
}

static void
vslz_block(struct vslz *vslz)
{
	unsigned f = 0;

	/* NB: if we are not at a block boundary, we will emit 7 bits to end
	 * the block.
	 */
	/* TODO: assert */
	f = (vslz->strm->state == SLZ_ST_FIXED) ? 7 : 0; 
	vslz_encode(vslz, "", 0);
	/* TODO: assert(vslz->strm->state == SLZ_ST_EOB); */
	vslz->last_bit = (vslz->out_total * 8) + vslz->strm->qbits + f;
	vslz->stop_bit = vslz->last_bit + 10;
}

static void
vslz_flush(struct vslz *vslz)
{

	/* TODO: assert */
	/* TODO: assert(vslz->strm->state != SLZ_ST_FIXED); */
	vslz->out_len = 0;
}

static void
vslz_finish(struct vslz *vslz)
{
	void *dest;
	size_t out;

	/* TODO: assert */
	/* TODO: assert(vslz->strm->state <= SLZ_ST_FIXED); */
	vslz_block(vslz);
	dest = vslz->buf + vslz->out_len;
	out = slz_finish(vslz->strm, dest);
	/* TODO: assert(vslz->strm->state != SLZ_ST_END); */
	vslz->out_total += out;
	vslz->out_len += out; /* TODO: assert */
}

/* BREACH mitigation, pad header with random comment */

static const unsigned char breach_header[] = {
	0x1f, 0x8b,		/* magic markers ID1 and ID2 */
	0x08,			/* deflate compression */
	1 << 4,			/* FCOMMENT flag */
	0x00, 0x00, 0x00, 0x00,	/* no mtime */
	0x04,			/* fastest compression */
	0xff,			/* unknown OS */
};

void
vslz_breach(struct vslz *vslz)
{
	static const char *alpha =
	    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
	    "abcdefghijklmnopqrstuvwxyz"
	    "0123456789!{}$%/&*()_+-=[]";
	char buf[256];
	unsigned l, u;

	/* TODO: assert */

	l = rand() % sizeof buf;
	for (u = 0; u < l - 1; u++)
		buf[u] = alpha[rand() % sizeof alpha];
	buf[u] = '\0';

	memcpy(vslz->buf, breach_header, sizeof breach_header);
	memcpy(vslz->buf + sizeof breach_header, buf, l);
	vslz->out_total = vslz->out_len = sizeof breach_header + l;
	vslz->start_bit = vslz->out_len * 8;
	vslz->strm->state = SLZ_ST_EOB;
}

/* zlib-based decompression */

struct vz {
	z_stream	strm[1];
	size_t		total_bits;
	size_t		start_bit;	/* first block bit offset */
	size_t		last_bit;	/* last block bit offset */
	size_t		stop_bit;	/* last end-of-block offset */
};

static int
vz_init(struct vz *vz)
{

	/* TODO: assert */
	memset(vz, 0, sizeof *vz);
	if (inflateInit2(vz->strm, MAX_WBITS | 16) != Z_OK)
		return (-1);
	return (0);
}

static void
vz_block(struct vz *vz)
{
	size_t bits, pending;
	unsigned type;

	/* NB: zlib.h contains the explanation on how inflate() is
	 * affected by the Z_BLOCK flag. That is where the magic
	 * values 0x80, 0x40 and 0x07 come from.
	 */
	type = vz->strm->data_type;
	pending = (vz->strm->avail_in * 8) + (type & 0x07);
	bits = vz->total_bits - pending;
	if ((type & 0xc0) == 0x80) {
		if (vz->start_bit == 0)
			vz->start_bit = bits;
		vz->last_bit = bits;
	} else if ((type & 0xc0) != 0x40)
		vz->stop_bit = bits;
}

static void /* TODO: failure conditions */
vz_test(struct vz *vz, void *ptr, size_t len)
{
	unsigned char dev_null[4096];
	int z;

	/* TODO: assert */
	vz->strm->next_in = ptr;
	vz->strm->avail_in = len;
	vz->total_bits += len * 8;

	while (vz->strm->avail_in > 0) {
		vz->strm->next_out = dev_null;
		vz->strm->avail_out = sizeof dev_null;
		z = inflate(vz->strm, Z_BLOCK);
		if (z == Z_STREAM_END)
			break;
		else if (z == Z_OK)
			vz_block(vz);
		else if (z != Z_BUF_ERROR) {
			fprintf(stderr, "ZLIB: %s\n", vz->strm->msg);
			abort();
		}
	}

	if (z == Z_STREAM_END && vz->strm->avail_in > 0) /* TODO: reentrant */
		abort(); /* TODO: assert */
}

static int
vz_finish(struct vz *vz)
{

	/* TODO: assert */
	if (inflateEnd(vz->strm) != Z_OK)
		return (-1);
	return (0);
}

int
main(void)
{
	struct vslz vslz[1];
	struct vz vz[1];
	char *gzbuf, buf[4096], *in;
	ssize_t l, e, s;
	int ret;

	gzbuf = malloc(cache_param_gzip_buffer);
	vslz_init(vslz, gzbuf, cache_param_gzip_buffer, 1);
	vz_init(vz);

	srand(time(NULL));
	vslz_breach(vslz);

	do {
		l = read(STDIN_FILENO, buf, sizeof buf);
		in = buf;
		while (l > 0) {
			e = l;
			s = vslz_space(vslz);
			if (s == 0) { /* XXX: if (s < threshold) */
				vslz_block(vslz);
				write(STDOUT_FILENO, vslz->buf, vslz->out_len);
				vz_test(vz, vslz->buf, vslz->out_len);
				vslz_flush(vslz);
			}
			if (e > s)
				e = s;
			vslz_encode(vslz, in, e);
			in += e;
			l -= e;
		}
	} while (in > buf);

	vslz_finish(vslz);

	write(STDOUT_FILENO, vslz->buf, vslz->out_len);
	vz_test(vz, vslz->buf, vslz->out_len);

	/* TODO? vslz_reset(vslz) */
	vz_finish(vz);

	ret = EXIT_SUCCESS;
	fprintf(stderr, "vslz: Gzip %zu %u %zu %zu %zu\n",
	    vslz->out_total, vslz->strm->ilen,
	    vslz->start_bit, vslz->last_bit, vslz->stop_bit);
#if USE_LIBVGZ
	if (vslz->out_total != vz->strm->total_in ||
	    vslz->strm->ilen != vz->strm->total_out ||
	    vslz->start_bit != vz->strm->start_bit ||
	    vslz->last_bit != vz->strm->last_bit ||
	    vslz->stop_bit != vz->strm->stop_bit) {
		fprintf(stderr, "zlib: Gzip %lu %lu %zu %zu %zu\n",
		    vz->strm->total_in, vz->strm->total_out,
		    vz->strm->start_bit, vz->strm->last_bit,
		    vz->strm->stop_bit);
		ret = EXIT_FAILURE;
	}
#else
	if (vslz->out_total != vz->strm->total_in ||
	    vslz->strm->ilen != vz->strm->total_out ||
	    vslz->start_bit != vz->start_bit ||
	    vslz->last_bit != vz->last_bit ||
	    vslz->stop_bit != vz->stop_bit) {
		fprintf(stderr, "zlib: Gzip %lu %lu %zu %zu %zu\n",
		    vz->strm->total_in, vz->strm->total_out,
		    vz->start_bit, vz->last_bit, vz->stop_bit);
		ret = EXIT_FAILURE;
	}
#endif

	free(gzbuf);
	return (ret);
}

vslz-test.sh

#!/bin/sh

set -e
set -u

vslz_check() {
	printf 'file: %s\n' "$1"
	./vslz <"$1" >/dev/null
}

find "$@" -type f |
while read f
do
	vslz_check "$f" 2>&1
done
Add a custom footer
Add a custom sidebar
Clone this wiki locally