// Copyright 2015 The Chromium OS Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#define _GNU_SOURCE
#include "exfile.h"

#include <assert.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>

/*
 * Extent files implementation.  Some things worth noting:
 *
 * - We are using glibc's buffered FILE objects for the underlying file I/O;
 *   this contributes to improved performance, especially with badly fragmented
 *   extents.  However, the FILE handle we return to the caller is decidedly
 *   unbuffered: making it buffered too seems superfluous, causing excess data
 *   copying and memory use.
 *
 * - We maintain the "logical" file position separately from the "physical"
 *   (underlying) file position. The latter is updated lazily whenever actual
 *   file I/O is about to be performed.
 *
 * - The logical position of an extent file is internally represented by the
 *   current extent index (curr_ex_idx) and the position within the current
 *   extent (curr_ex_pos), as well as an absolute logical position (curr_pos).
 *   In general, curr_pos should equal the total length of all extents prior to
 *   curr_ex_idx, plus curr_ex_pos.  Also, curr_ex_idx may range between 0 and
 *   the total extent count; if it is exactly the latter, then curr_ex_pos must
 *   be zero, representing the fact that the we are at the logical end of the
 *   file.  Otherwise, curr_ex_pos may range between 0 and the length of the
 *   current extent; if it is exactly the latter, then this is equivalent to
 *   position zero on the next extent.  All functions should honor this
 *   duality.
 *
 * - Seeking is done efficiently at O(log(D)), where D is the
 *   number of extents between the current position and the new one. This seems
 *   like a good midway for supporting both sequential and random access.
 */


#define TRUE 1
#define FALSE 0

#define arraysize(x) (sizeof(x) / sizeof(*(x)))


/* Extent prefix length. */
typedef struct {
    size_t prec;   /* total length of preceding extents */
    size_t total;  /* total length including current extent */
} prefix_len_t;

/* Extent file logical modes. Used as index to the mapping from logical modes
 * to open(2) and fopen(3) modes below. */
typedef enum {
    EXFILE_MODE_RO,
    EXFILE_MODE_WO,
    EXFILE_MODE_RW,
    EXFILE_MODE_MAX  /* sentinel */
} exfile_mode_t;

/* An extent file control object (aka "cookie"). */
typedef struct {
    int fd;                        /* underlying file descriptor */
    size_t ex_count;               /* number of extents (non-zero) */
    ex_t *ex_arr;                  /* array of extents */
    prefix_len_t *prefix_len_arr;  /* total lengths of extent prefixes */
    void (*ex_free)(void *);       /* extent array free function */
    size_t total_ex_len;	   /* total length of all extents (constant) */
    off_t curr_file_pos;           /* current underlying file position */
    size_t curr_ex_idx;            /* current extent index */
    size_t curr_ex_pos;            /* current position within extent */
    off_t curr_pos;		   /* current logical file position */
} exfile_t;


/* Mapping from fopen(3) modes to extent file logical modes. */
static const struct {
    const char *fopen_mode;
    exfile_mode_t mode;
} fopen_mode_to_mode[] = {
    {"r", EXFILE_MODE_RO},
    {"r+", EXFILE_MODE_RW},
    {"w", EXFILE_MODE_WO},
    {"w+", EXFILE_MODE_RW},
};


/* Mapping from extent file logical modes to open(2) flags. */
static const int mode_to_open_flags[EXFILE_MODE_MAX] = {
    O_RDONLY,
    O_WRONLY,
    O_RDWR,
};


/* Searches an array |ex_arr| of |ex_count| extents and returns the index of
 * the extent that contains the location |pos|.  Uses an array |prefix_len_arr|
 * of corresponding prefix lengths. The total complexity is O(log(D)), where D
 * is the distance between the returned extent index and |init_ex_idx|. */
static size_t
ex_arr_search(size_t ex_count, const ex_t *ex_arr,
	      const prefix_len_t *prefix_len_arr, size_t pos,
	      size_t init_ex_idx)
{
    assert(ex_arr && ex_count);
    const ssize_t last_ex_idx = ex_count - 1;
    assert(init_ex_idx <= ex_count);
    assert(pos < prefix_len_arr[last_ex_idx].total);
    if (init_ex_idx == ex_count)
	init_ex_idx = last_ex_idx;  /* adjustment for purposes of the search below */

    /* First, search in exponentially increasing leaps from the current extent,
     * until an interval bounding the target position was obtained. Here i and j
     * are the left and right (inclusive) index boundaries, respectively. */
    ssize_t i = init_ex_idx;
    ssize_t j = i;
    size_t leap = 1;
    /* Go left, as needed. */
    while (i > 0 && pos < prefix_len_arr[i].prec) {
	j = i - 1;
	if ((i -= leap) < 0)
	    i = 0;
	leap <<= 1;
    }
    /* Go right, as needed. */
    while (j < last_ex_idx && pos >= prefix_len_arr[j].total) {
	i = j + 1;
	if ((j += leap) > last_ex_idx)
	    j = last_ex_idx;
	leap <<= 1;
    }

    /* Then, perform a binary search between i and j. */
    size_t k = 0;
    while (1) {
	k = (i + j) / 2;
	if (pos < prefix_len_arr[k].prec)
	    j = k - 1;
	else if (pos >= prefix_len_arr[k].total)
	    i = k + 1;
	else
	    break;
    }

    return k;
}

/* Performs I/O operations (either read or write) on an extent file, advancing
 * through consecutive extents and updating the logical/physical file position
 * as we go. */
static ssize_t
exfile_io(exfile_t *xf, int do_read, char *buf, size_t size)
{
    if (xf->curr_ex_idx == xf->ex_count)
	return 0;  /* end-of-extent-file */

    /* Reading or writing? */
    typedef ssize_t (io_func_t)(int, void *, size_t);
    io_func_t *io_func;
    ssize_t error_ret_val;
    if (do_read) {
	io_func = read;
	error_ret_val = -1;
    } else {
	io_func = (io_func_t *)write;
	error_ret_val = 0;  /* must not return a negative value when writing */
    }

    /* Start processing data along extents. */
    const ex_t *curr_ex = xf->ex_arr + xf->curr_ex_idx;
    assert(curr_ex->len >= xf->curr_ex_pos);
    size_t curr_ex_rem_len = curr_ex->len - xf->curr_ex_pos;
    ssize_t total_bytes = 0;
    while (size) {
	/* Advance to the next extent of non-zero length. */
	while (curr_ex_rem_len == 0) {
	    xf->curr_ex_idx++;
	    xf->curr_ex_pos = 0;
	    if (xf->curr_ex_idx == xf->ex_count)
		return total_bytes;  /* end-of-extent-file */
	    curr_ex++;
	    curr_ex_rem_len = curr_ex->len;
	}

	const int is_real_ex = (curr_ex->off >= 0);

	/* Seek to the correct file position, as necessary. */
	if (is_real_ex) {
	    const off_t file_pos = curr_ex->off + xf->curr_ex_pos;
	    if (xf->curr_file_pos != file_pos) {
		if (lseek(xf->fd, file_pos, SEEK_SET) == (off_t)-1) {
		    xf->curr_file_pos = -1;  /* unknown file position */
		    return total_bytes ? total_bytes : error_ret_val;
		}
		xf->curr_file_pos = file_pos;
	    }
	}

	/* Process data to the end of the current extent or the requested
	 * count, whichever is smaller. */
	size_t io_count = (size < curr_ex_rem_len ?  size : curr_ex_rem_len);
	ssize_t io_bytes = io_count;
	if (is_real_ex)
	    io_bytes = io_func(xf->fd, buf, io_count);
	else if (do_read)
	    memset(buf, 0, io_count);

	/* Stop on error. */
	if (io_bytes < 0) {
	    if (total_bytes == 0)
		total_bytes = error_ret_val;
	    break;
	}

	/* Update read state. */
	total_bytes += io_bytes;
	if (is_real_ex)
	    xf->curr_file_pos += io_bytes;
	xf->curr_ex_pos += io_bytes;
	xf->curr_pos += io_bytes;

	/* If we didn't read the whole extent, finish; delegate handling of
	 * partial read/write back to the caller. */
	if ((curr_ex_rem_len -= io_bytes) > 0)
	    break;

	/* Update total count and buffer pointer. */
	size -= io_bytes;
	buf += io_bytes;
    }

    return total_bytes;
}

/* Reads up to |size| bytes from an extent file into |buf|. This implements the
 * cookie_read_function_t interface and is a thin wrapper around exfile_io()
 * (see above). Returns the number of bytes read, or -1 on error. */
static ssize_t
exfile_read(void *cookie, char *buf, size_t size)
{
    return exfile_io((exfile_t *)cookie, TRUE, buf, size);
}

/* Writes up to |size| bytes from |buf| to an extent file. This implements the
 * cookie_write_function_t interface and is a thin wrapper around exfile_io()
 * (see above). Returns the number of bytes written; must NOT return a negative
 * value. */
static ssize_t
exfile_write(void *cookie, const char *buf, size_t size)
{
    return exfile_io((exfile_t *)cookie, FALSE, (char *)buf, size);
}

/* Performs seek on an extent file, repositioning it to the value of |*pos_p|
 * according to |whence|. This implements the cookie_seek_function_t interface.
 * On success, stores the resulting logical position measured in bytes along
 * contiguous extents into |*pos_p| and returns 0; otherwise returns -1. */
static int
exfile_seek(void *cookie, off64_t *pos_p, int whence)
{
    exfile_t *xf = (exfile_t *)cookie;

    /* Compute the absolute logical target position. */
    off64_t new_pos = *pos_p;
    if (whence == SEEK_CUR)
	new_pos += xf->curr_pos;
    else if (whence == SEEK_END)
	new_pos += xf->total_ex_len;

    /* Ensure that the target position is valid.  Note that repositioning the
     * file right past the last extent is considered valid, in line with normal
     * seek behavior, although no write (nor read) can be performed there. */
    if (new_pos < 0 || new_pos > (off64_t)xf->total_ex_len)
	return -1;

    if (new_pos != (off64_t)xf->curr_pos) {
	/* Find the extend that contains the requested logical position; handle
	 * special case upfront, for efficiency. */
	size_t new_ex_idx = 0;
	if (new_pos == (off64_t)xf->total_ex_len)
	    new_ex_idx = xf->ex_count;
	else if (new_pos)
	    new_ex_idx = ex_arr_search(xf->ex_count, xf->ex_arr,
				       xf->prefix_len_arr, new_pos,
				       xf->curr_ex_idx);

	/* Set the logical position markers. */
	xf->curr_ex_idx = new_ex_idx;
	xf->curr_ex_pos =
	    (new_ex_idx < xf->ex_count ?
	     (size_t)(new_pos - xf->prefix_len_arr[new_ex_idx].prec) : 0);
	xf->curr_pos = (off_t)new_pos;
    }

    *pos_p = new_pos;
    return 0;
}

/* Closes an open extent file. This implements the cookie_close_function_t
 * interface. Always returns 0 (success). */
static int
exfile_close(void *cookie)
{
    exfile_t *xf = (exfile_t *)cookie;
    if (xf) {
	if (xf->fd >= 0)
	    close(xf->fd);
	free(xf->prefix_len_arr);
	if (xf->ex_free)
	    xf->ex_free(xf->ex_arr);
	free(xf);
    }
    return 0;
}

static const cookie_io_functions_t cookie_io_funcs = {
    .read = exfile_read,
    .write = exfile_write,
    .seek = exfile_seek,
    .close = exfile_close,
};

static FILE *
exfile_open(int fd, const char *path, const char *fopen_mode, ex_t *ex_arr,
	    size_t ex_count, void (*ex_free)(void *))
{
    /* Argument sanity check. */
    if (!(ex_arr && ex_count && (fd >= 0 || path) && (fd < 0 || !path)))
	return NULL;

    /* Validate mode argument. */
    exfile_mode_t mode = EXFILE_MODE_MAX;
    size_t i;
    for (i = 0; i < arraysize(fopen_mode_to_mode); i++)
	if (!strcmp(fopen_mode_to_mode[i].fopen_mode, fopen_mode)) {
	    mode = fopen_mode_to_mode[i].mode;
	    break;
	}
    if (mode == EXFILE_MODE_MAX)
	return NULL;

    /* Open the underlying file, if not already provided. */
    int do_close_fd = FALSE;
    if (fd < 0) {
	if ((fd = open(path, mode_to_open_flags[mode])) < 0)
	    return NULL;
	do_close_fd = TRUE;
    }

    /* Allocate memory and open file streams, for both the underlying file and
     * the handle returned to the caller. */
    exfile_t *xf = NULL;
    prefix_len_t *prefix_len_arr = NULL;
    FILE *handle = NULL;
    if (!((xf = (exfile_t *)calloc(1, sizeof(exfile_t))) &&
	  (prefix_len_arr =
	   (prefix_len_t *)malloc(sizeof(prefix_len_t) * ex_count)) &&
	  (handle = fopencookie(xf, fopen_mode, cookie_io_funcs)))) {
	/* If a file was opened above, close it. */
	if (do_close_fd)
	    close(fd);
	if (xf)
	    xf->fd = -1;  /* invalidate prior to calling exfile_close() */

	free(prefix_len_arr);
	if (handle)
	    fclose(handle);  /* will call exfile_close already */
	else
	    exfile_close(xf);
	return NULL;
    }

    /* Compute the prefix lengths. */
    size_t prefix_len = 0;
    for (i = 0; i < ex_count; i++) {
	prefix_len_arr[i].prec = prefix_len;
	prefix_len += ex_arr[i].len;
	prefix_len_arr[i].total = prefix_len;
    }

    /* Configure control object, including physical/logical file position. */
    xf->fd = fd;
    xf->ex_count = ex_count;
    xf->ex_arr = ex_arr;
    xf->prefix_len_arr = prefix_len_arr;
    xf->ex_free = ex_free;
    xf->total_ex_len = prefix_len_arr[ex_count - 1].total;
    xf->curr_file_pos = lseek(fd, 0, SEEK_CUR);
    xf->curr_ex_idx = 0;
    xf->curr_ex_pos = 0;
    xf->curr_pos = 0;

    /* Return the external stream handle. */
    return handle;
}

FILE *
exfile_fopen(const char *path, const char *fopen_mode, ex_t *ex_arr,
	     size_t ex_count, void (*ex_free)(void *))
{
    return exfile_open(-1, path, fopen_mode, ex_arr, ex_count, ex_free);
}

FILE *
exfile_fdopen(int fd, const char *fopen_mode, ex_t *ex_arr,
	      size_t ex_count, void (*ex_free)(void *))
{
    return exfile_open(fd, NULL, fopen_mode, ex_arr, ex_count, ex_free);
}