/*

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;

}