text: // 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 size_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 > 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;
      int 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);
  }
  