The fifteenth batch

[thirdparty/git.git] / reftable / block.c

/*
Copyright 2020 Google LLC

Use of this source code is governed by a BSD-style
license that can be found in the LICENSE file or at
https://developers.google.com/open-source/licenses/bsd
*/

#include "block.h"

#include "blocksource.h"
#include "constants.h"
#include "record.h"
#include "reftable-error.h"
#include "system.h"
#include <zlib.h>

int header_size(int version)
{
        switch (version) {
        case 1:
                return 24;
        case 2:
                return 28;
        }
        abort();
}

int footer_size(int version)
{
        switch (version) {
        case 1:
                return 68;
        case 2:
                return 72;
        }
        abort();
}

static int block_writer_register_restart(struct block_writer *w, int n,
                                         int is_restart, struct strbuf *key)
{
        int rlen = w->restart_len;
        if (rlen >= MAX_RESTARTS) {
                is_restart = 0;
        }

        if (is_restart) {
                rlen++;
        }
        if (2 + 3 * rlen + n > w->block_size - w->next)
                return -1;
        if (is_restart) {
                REFTABLE_ALLOC_GROW(w->restarts, w->restart_len + 1, w->restart_cap);
                w->restarts[w->restart_len++] = w->next;
        }

        w->next += n;

        strbuf_reset(&w->last_key);
        strbuf_addbuf(&w->last_key, key);
        w->entries++;
        return 0;
}

void block_writer_init(struct block_writer *bw, uint8_t typ, uint8_t *buf,
                       uint32_t block_size, uint32_t header_off, int hash_size)
{
        bw->buf = buf;
        bw->hash_size = hash_size;
        bw->block_size = block_size;
        bw->header_off = header_off;
        bw->buf[header_off] = typ;
        bw->next = header_off + 4;
        bw->restart_interval = 16;
        bw->entries = 0;
        bw->restart_len = 0;
        bw->last_key.len = 0;
        if (!bw->zstream) {
                REFTABLE_CALLOC_ARRAY(bw->zstream, 1);
                deflateInit(bw->zstream, 9);
        }
}

uint8_t block_writer_type(struct block_writer *bw)
{
        return bw->buf[bw->header_off];
}

/* Adds the reftable_record to the block. Returns -1 if it does not fit, 0 on
   success. Returns REFTABLE_API_ERROR if attempting to write a record with
   empty key. */
int block_writer_add(struct block_writer *w, struct reftable_record *rec)
{
        struct strbuf empty = STRBUF_INIT;
        struct strbuf last =
                w->entries % w->restart_interval == 0 ? empty : w->last_key;
        struct string_view out = {
                .buf = w->buf + w->next,
                .len = w->block_size - w->next,
        };

        struct string_view start = out;

        int is_restart = 0;
        struct strbuf key = STRBUF_INIT;
        int n = 0;
        int err = -1;

        reftable_record_key(rec, &key);
        if (!key.len) {
                err = REFTABLE_API_ERROR;
                goto done;
        }

        n = reftable_encode_key(&is_restart, out, last, key,
                                reftable_record_val_type(rec));
        if (n < 0)
                goto done;
        string_view_consume(&out, n);

        n = reftable_record_encode(rec, out, w->hash_size);
        if (n < 0)
                goto done;
        string_view_consume(&out, n);

        err = block_writer_register_restart(w, start.len - out.len, is_restart,
                                            &key);
done:
        strbuf_release(&key);
        return err;
}

int block_writer_finish(struct block_writer *w)
{
        int i;
        for (i = 0; i < w->restart_len; i++) {
                put_be24(w->buf + w->next, w->restarts[i]);
                w->next += 3;
        }

        put_be16(w->buf + w->next, w->restart_len);
        w->next += 2;
        put_be24(w->buf + 1 + w->header_off, w->next);

        /*
         * Log records are stored zlib-compressed. Note that the compression
         * also spans over the restart points we have just written.
         */
        if (block_writer_type(w) == BLOCK_TYPE_LOG) {
                int block_header_skip = 4 + w->header_off;
                uLongf src_len = w->next - block_header_skip, compressed_len;
                int ret;

                ret = deflateReset(w->zstream);
                if (ret != Z_OK)
                        return REFTABLE_ZLIB_ERROR;

                /*
                 * Precompute the upper bound of how many bytes the compressed
                 * data may end up with. Combined with `Z_FINISH`, `deflate()`
                 * is guaranteed to return `Z_STREAM_END`.
                 */
                compressed_len = deflateBound(w->zstream, src_len);
                REFTABLE_ALLOC_GROW(w->compressed, compressed_len, w->compressed_cap);

                w->zstream->next_out = w->compressed;
                w->zstream->avail_out = compressed_len;
                w->zstream->next_in = w->buf + block_header_skip;
                w->zstream->avail_in = src_len;

                /*
                 * We want to perform all decompression in a single step, which
                 * is why we can pass Z_FINISH here. As we have precomputed the
                 * deflated buffer's size via `deflateBound()` this function is
                 * guaranteed to succeed according to the zlib documentation.
                 */
                ret = deflate(w->zstream, Z_FINISH);
                if (ret != Z_STREAM_END)
                        return REFTABLE_ZLIB_ERROR;

                /*
                 * Overwrite the uncompressed data we have already written and
                 * adjust the `next` pointer to point right after the
                 * compressed data.
                 */
                memcpy(w->buf + block_header_skip, w->compressed,
                       w->zstream->total_out);
                w->next = w->zstream->total_out + block_header_skip;
        }

        return w->next;
}

int block_reader_init(struct block_reader *br, struct reftable_block *block,
                      uint32_t header_off, uint32_t table_block_size,
                      int hash_size)
{
        uint32_t full_block_size = table_block_size;
        uint8_t typ = block->data[header_off];
        uint32_t sz = get_be24(block->data + header_off + 1);
        int err = 0;
        uint16_t restart_count = 0;
        uint32_t restart_start = 0;
        uint8_t *restart_bytes = NULL;

        reftable_block_done(&br->block);

        if (!reftable_is_block_type(typ)) {
                err =  REFTABLE_FORMAT_ERROR;
                goto done;
        }

        if (typ == BLOCK_TYPE_LOG) {
                uint32_t block_header_skip = 4 + header_off;
                uLong dst_len = sz - block_header_skip;
                uLong src_len = block->len - block_header_skip;

                /* Log blocks specify the *uncompressed* size in their header. */
                REFTABLE_ALLOC_GROW(br->uncompressed_data, sz,
                                    br->uncompressed_cap);

                /* Copy over the block header verbatim. It's not compressed. */
                memcpy(br->uncompressed_data, block->data, block_header_skip);

                if (!br->zstream) {
                        REFTABLE_CALLOC_ARRAY(br->zstream, 1);
                        err = inflateInit(br->zstream);
                } else {
                        err = inflateReset(br->zstream);
                }
                if (err != Z_OK) {
                        err = REFTABLE_ZLIB_ERROR;
                        goto done;
                }

                br->zstream->next_in = block->data + block_header_skip;
                br->zstream->avail_in = src_len;
                br->zstream->next_out = br->uncompressed_data + block_header_skip;
                br->zstream->avail_out = dst_len;

                /*
                 * We know both input as well as output size, and we know that
                 * the sizes should never be bigger than `uInt_MAX` because
                 * blocks can at most be 16MB large. We can thus use `Z_FINISH`
                 * here to instruct zlib to inflate the data in one go, which
                 * is more efficient than using `Z_NO_FLUSH`.
                 */
                err = inflate(br->zstream, Z_FINISH);
                if (err != Z_STREAM_END) {
                        err = REFTABLE_ZLIB_ERROR;
                        goto done;
                }
                err = 0;

                if (br->zstream->total_out + block_header_skip != sz) {
                        err = REFTABLE_FORMAT_ERROR;
                        goto done;
                }

                /* We're done with the input data. */
                reftable_block_done(block);
                block->data = br->uncompressed_data;
                block->len = sz;
                full_block_size = src_len + block_header_skip - br->zstream->avail_in;
        } else if (full_block_size == 0) {
                full_block_size = sz;
        } else if (sz < full_block_size && sz < block->len &&
                   block->data[sz] != 0) {
                /* If the block is smaller than the full block size, it is
                   padded (data followed by '\0') or the next block is
                   unaligned. */
                full_block_size = sz;
        }

        restart_count = get_be16(block->data + sz - 2);
        restart_start = sz - 2 - 3 * restart_count;
        restart_bytes = block->data + restart_start;

        /* transfer ownership. */
        br->block = *block;
        block->data = NULL;
        block->len = 0;

        br->hash_size = hash_size;
        br->block_len = restart_start;
        br->full_block_size = full_block_size;
        br->header_off = header_off;
        br->restart_count = restart_count;
        br->restart_bytes = restart_bytes;

done:
        return err;
}

void block_reader_release(struct block_reader *br)
{
        inflateEnd(br->zstream);
        reftable_free(br->zstream);
        reftable_free(br->uncompressed_data);
        reftable_block_done(&br->block);
}

uint8_t block_reader_type(const struct block_reader *r)
{
        return r->block.data[r->header_off];
}

int block_reader_first_key(const struct block_reader *br, struct strbuf *key)
{
        int off = br->header_off + 4, n;
        struct string_view in = {
                .buf = br->block.data + off,
                .len = br->block_len - off,
        };
        uint8_t extra = 0;

        strbuf_reset(key);

        n = reftable_decode_key(key, &extra, in);
        if (n < 0)
                return n;
        if (!key->len)
                return REFTABLE_FORMAT_ERROR;

        return 0;
}

static uint32_t block_reader_restart_offset(const struct block_reader *br, size_t idx)
{
        return get_be24(br->restart_bytes + 3 * idx);
}

void block_iter_seek_start(struct block_iter *it, const struct block_reader *br)
{
        it->block = br->block.data;
        it->block_len = br->block_len;
        it->hash_size = br->hash_size;
        strbuf_reset(&it->last_key);
        it->next_off = br->header_off + 4;
}

struct restart_needle_less_args {
        int error;
        struct strbuf needle;
        const struct block_reader *reader;
};

static int restart_needle_less(size_t idx, void *_args)
{
        struct restart_needle_less_args *args = _args;
        uint32_t off = block_reader_restart_offset(args->reader, idx);
        struct string_view in = {
                .buf = args->reader->block.data + off,
                .len = args->reader->block_len - off,
        };
        uint64_t prefix_len, suffix_len;
        uint8_t extra;
        int n;

        /*
         * Records at restart points are stored without prefix compression, so
         * there is no need to fully decode the record key here. This removes
         * the need for allocating memory.
         */
        n = reftable_decode_keylen(in, &prefix_len, &suffix_len, &extra);
        if (n < 0 || prefix_len) {
                args->error = 1;
                return -1;
        }

        string_view_consume(&in, n);
        if (suffix_len > in.len) {
                args->error = 1;
                return -1;
        }

        n = memcmp(args->needle.buf, in.buf,
                   args->needle.len < suffix_len ? args->needle.len : suffix_len);
        if (n)
                return n < 0;
        return args->needle.len < suffix_len;
}

int block_iter_next(struct block_iter *it, struct reftable_record *rec)
{
        struct string_view in = {
                .buf = (unsigned char *) it->block + it->next_off,
                .len = it->block_len - it->next_off,
        };
        struct string_view start = in;
        uint8_t extra = 0;
        int n = 0;

        if (it->next_off >= it->block_len)
                return 1;

        n = reftable_decode_key(&it->last_key, &extra, in);
        if (n < 0)
                return -1;
        if (!it->last_key.len)
                return REFTABLE_FORMAT_ERROR;

        string_view_consume(&in, n);
        n = reftable_record_decode(rec, it->last_key, extra, in, it->hash_size,
                                   &it->scratch);
        if (n < 0)
                return -1;
        string_view_consume(&in, n);

        it->next_off += start.len - in.len;
        return 0;
}

void block_iter_reset(struct block_iter *it)
{
        strbuf_reset(&it->last_key);
        it->next_off = 0;
        it->block = NULL;
        it->block_len = 0;
        it->hash_size = 0;
}

void block_iter_close(struct block_iter *it)
{
        strbuf_release(&it->last_key);
        strbuf_release(&it->scratch);
}

int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,
                        struct strbuf *want)
{
        struct restart_needle_less_args args = {
                .needle = *want,
                .reader = br,
        };
        struct reftable_record rec;
        int err = 0;
        size_t i;

        /*
         * Perform a binary search over the block's restart points, which
         * avoids doing a linear scan over the whole block. Like this, we
         * identify the section of the block that should contain our key.
         *
         * Note that we explicitly search for the first restart point _greater_
         * than the sought-after record, not _greater or equal_ to it. In case
         * the sought-after record is located directly at the restart point we
         * would otherwise start doing the linear search at the preceding
         * restart point. While that works alright, we would end up scanning
         * too many record.
         */
        i = binsearch(br->restart_count, &restart_needle_less, &args);
        if (args.error) {
                err = REFTABLE_FORMAT_ERROR;
                goto done;
        }

        /*
         * Now there are multiple cases:
         *
         *   - `i == 0`: The wanted record is smaller than the record found at
         *     the first restart point. As the first restart point is the first
         *     record in the block, our wanted record cannot be located in this
         *     block at all. We still need to position the iterator so that the
         *     next call to `block_iter_next()` will yield an end-of-iterator
         *     signal.
         *
         *   - `i == restart_count`: The wanted record was not found at any of
         *     the restart points. As there is no restart point at the end of
         *     the section the record may thus be contained in the last block.
         *
         *   - `i > 0`: The wanted record must be contained in the section
         *     before the found restart point. We thus do a linear search
         *     starting from the preceding restart point.
         */
        if (i > 0)
                it->next_off = block_reader_restart_offset(br, i - 1);
        else
                it->next_off = br->header_off + 4;
        it->block = br->block.data;
        it->block_len = br->block_len;
        it->hash_size = br->hash_size;

        reftable_record_init(&rec, block_reader_type(br));

        /*
         * We're looking for the last entry less than the wanted key so that
         * the next call to `block_reader_next()` would yield the wanted
         * record. We thus don't want to position our reader at the sought
         * after record, but one before. To do so, we have to go one entry too
         * far and then back up.
         */
        while (1) {
                size_t prev_off = it->next_off;

                err = block_iter_next(it, &rec);
                if (err < 0)
                        goto done;
                if (err > 0) {
                        it->next_off = prev_off;
                        err = 0;
                        goto done;
                }

                /*
                 * Check whether the current key is greater or equal to the
                 * sought-after key. In case it is greater we know that the
                 * record does not exist in the block and can thus abort early.
                 * In case it is equal to the sought-after key we have found
                 * the desired record.
                 *
                 * Note that we store the next record's key record directly in
                 * `last_key` without restoring the key of the preceding record
                 * in case we need to go one record back. This is safe to do as
                 * `block_iter_next()` would return the ref whose key is equal
                 * to `last_key` now, and naturally all keys share a prefix
                 * with themselves.
                 */
                reftable_record_key(&rec, &it->last_key);
                if (strbuf_cmp(&it->last_key, want) >= 0) {
                        it->next_off = prev_off;
                        goto done;
                }
        }

done:
        reftable_record_release(&rec);
        return err;
}

void block_writer_release(struct block_writer *bw)
{
        deflateEnd(bw->zstream);
        FREE_AND_NULL(bw->zstream);
        FREE_AND_NULL(bw->restarts);
        FREE_AND_NULL(bw->compressed);
        strbuf_release(&bw->last_key);
        /* the block is not owned. */
}

void reftable_block_done(struct reftable_block *blockp)
{
        struct reftable_block_source source = blockp->source;
        if (blockp && source.ops)
                source.ops->return_block(source.arg, blockp);
        blockp->data = NULL;
        blockp->len = 0;
        blockp->source.ops = NULL;
        blockp->source.arg = NULL;
}