journal.c

/*
 * Copyright (C) 2004, 2005  Internet Systems Consortium, Inc. ("ISC")
 * Copyright (C) 1999-2002  Internet Software Consortium.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 */

/* $Id: journal.c,v 1.93 2005/06/08 02:06:58 marka Exp $ */

#include <config.h>

#include <stdlib.h>
#include <unistd.h>

#include <isc/file.h>
#include <isc/mem.h>
#include <isc/stdio.h>
#include <isc/string.h>
#include <isc/util.h>

#include <dns/compress.h>
#include <dns/db.h>
#include <dns/dbiterator.h>
#include <dns/diff.h>
#include <dns/fixedname.h>
#include <dns/journal.h>
#include <dns/log.h>
#include <dns/rdataset.h>
#include <dns/rdatasetiter.h>
#include <dns/result.h>
#include <dns/soa.h>

/*! \file 
 * \brief Journalling.
 *
 * A journal file consists of
 *
 *   \li A fixed-size header of type journal_rawheader_t.
 *
 *   \li The index.  This is an unordered array of index entries
 *     of type journal_rawpos_t giving the locations
 *     of some arbitrary subset of the journal's addressable
 *     transactions.  The index entries are used as hints to
 *     speed up the process of locating a transaction with a given
 *     serial number.  Unused index entries have an "offset"
 *     field of zero.  The size of the index can vary between
 *     journal files, but does not change during the lifetime
 *     of a file.  The size can be zero.
 *
 *   \li The journal data.  This  consists of one or more transactions.
 *     Each transaction begins with a transaction header of type
 *     journal_rawxhdr_t.  The transaction header is followed by a
 *     sequence of RRs, similar in structure to an IXFR difference
 *     sequence (RFC1995).  That is, the pre-transaction SOA,
 *     zero or more other deleted RRs, the post-transaction SOA,
 *     and zero or more other added RRs.  Unlike in IXFR, each RR
 *     is prefixed with a 32-bit length.
 *
 *     The journal data part grows as new transactions are
 *     appended to the file.  Only those transactions
 *     whose serial number is current-(2^31-1) to current
 *     are considered "addressable" and may be pointed
 *     to from the header or index.  They may be preceded
 *     by old transactions that are no longer addressable,
 *     and they may be followed by transactions that were
 *     appended to the journal but never committed by updating
 *     the "end" position in the header.  The latter will
 *     be overwritten when new transactions are added.
 */
/*%
 * When true, accept IXFR difference sequences where the
 * SOA serial number does not change (BIND 8 sends such
 * sequences).
 */
static isc_boolean_t bind8_compat = ISC_TRUE; /* XXX config */

/**************************************************************************/
/*
 * Miscellaneous utilities.
 */

#define JOURNAL_COMMON_LOGARGS \
	dns_lctx, DNS_LOGCATEGORY_GENERAL, DNS_LOGMODULE_JOURNAL

#define JOURNAL_DEBUG_LOGARGS(n) \
	JOURNAL_COMMON_LOGARGS, ISC_LOG_DEBUG(n)

/*%
 * It would be non-sensical (or at least obtuse) to use FAIL() with an
 * ISC_R_SUCCESS code, but the test is there to keep the Solaris compiler
 * from complaining about "end-of-loop code not reached".
 */
#define FAIL(code) \
	do { result = (code);					\
		if (result != ISC_R_SUCCESS) goto failure;	\
	} while (0)

#define CHECK(op) \
     	do { result = (op); 					\
		if (result != ISC_R_SUCCESS) goto failure; 	\
	} while (0)

static isc_result_t index_to_disk(dns_journal_t *);

static inline isc_uint32_t
decode_uint32(unsigned char *p) {
	return ((p[0] << 24) +
		(p[1] << 16) +
		(p[2] <<  8) +
		(p[3] <<  0));
}

static inline void
encode_uint32(isc_uint32_t val, unsigned char *p) {
	p[0] = (isc_uint8_t)(val >> 24);
	p[1] = (isc_uint8_t)(val >> 16);
	p[2] = (isc_uint8_t)(val >>  8);
	p[3] = (isc_uint8_t)(val >>  0);
}

isc_result_t
dns_db_createsoatuple(dns_db_t *db, dns_dbversion_t *ver, isc_mem_t *mctx,
		      dns_diffop_t op, dns_difftuple_t **tp)
{
	isc_result_t result;
	dns_dbnode_t *node;
	dns_rdataset_t rdataset;
	dns_rdata_t rdata = DNS_RDATA_INIT;
	dns_name_t *zonename;

	zonename = dns_db_origin(db);

	node = NULL;
	result = dns_db_findnode(db, zonename, ISC_FALSE, &node);
	if (result != ISC_R_SUCCESS)
		goto nonode;

	dns_rdataset_init(&rdataset);
	result = dns_db_findrdataset(db, node, ver, dns_rdatatype_soa, 0,
				     (isc_stdtime_t)0, &rdataset, NULL);
 	if (result != ISC_R_SUCCESS)
		goto freenode;

	result = dns_rdataset_first(&rdataset);
 	if (result != ISC_R_SUCCESS)
		goto freenode;

	dns_rdataset_current(&rdataset, &rdata);

	result = dns_difftuple_create(mctx, op, zonename, rdataset.ttl,
				      &rdata, tp);

	dns_rdataset_disassociate(&rdataset);
	dns_db_detachnode(db, &node);
	return (ISC_R_SUCCESS);

 freenode:
	dns_db_detachnode(db, &node);
 nonode:
	UNEXPECTED_ERROR(__FILE__, __LINE__, "missing SOA");
	return (result);
}

/* Journalling */

/*%
 * On-disk representation of a "pointer" to a journal entry.
 * These are used in the journal header to locate the beginning
 * and end of the journal, and in the journal index to locate
 * other transactions.
 */
typedef struct {
	unsigned char	serial[4];  /*%< SOA serial before update. */
	/*
	 * XXXRTH  Should offset be 8 bytes?
	 * XXXDCL ... probably, since isc_offset_t is 8 bytes on many OSs.
	 * XXXAG  ... but we will not be able to seek >2G anyway on many
	 *            platforms as long as we are using fseek() rather
	 *            than lseek().
	 */
	unsigned char	offset[4];  /*%< Offset from beginning of file. */
} journal_rawpos_t;


/*%
 * The header is of a fixed size, with some spare room for future
 * extensions.
 */
#define JOURNAL_HEADER_SIZE 64 /* Bytes. */

/*%
 * The on-disk representation of the journal header.
 * All numbers are stored in big-endian order.
 */
typedef union {
	struct {
		/*% File format version ID. */
		unsigned char 		format[16];
		/*% Position of the first addressable transaction */
		journal_rawpos_t 	begin;
		/*% Position of the next (yet nonexistent) transaction. */
		journal_rawpos_t 	end;
		/*% Number of index entries following the header. */
		unsigned char 		index_size[4];
	} h;
	/* Pad the header to a fixed size. */
	unsigned char pad[JOURNAL_HEADER_SIZE];
} journal_rawheader_t;

/*%
 * The on-disk representation of the transaction header.
 * There is one of these at the beginning of each transaction.
 */
typedef struct {
	unsigned char	size[4]; 	/*%< In bytes, excluding header. */
	unsigned char	serial0[4];	/*%< SOA serial before update. */
	unsigned char	serial1[4];	/*%< SOA serial after update. */
} journal_rawxhdr_t;

/*%
 * The on-disk representation of the RR header.
 * There is one of these at the beginning of each RR.
 */
typedef struct {
	unsigned char	size[4]; 	/*%< In bytes, excluding header. */
} journal_rawrrhdr_t;

/*%
 * The in-core representation of the journal header.
 */
typedef struct {
	isc_uint32_t	serial;
	isc_offset_t	offset;
} journal_pos_t;

#define POS_VALID(pos) 		((pos).offset != 0)
#define POS_INVALIDATE(pos) 	((pos).offset = 0, (pos).serial = 0)

typedef struct {
	unsigned char 	format[16];
	journal_pos_t 	begin;
	journal_pos_t 	end;
	isc_uint32_t	index_size;
} journal_header_t;

/*%
 * The in-core representation of the transaction header.
 */

typedef struct {
	isc_uint32_t	size;
	isc_uint32_t	serial0;
	isc_uint32_t	serial1;
} journal_xhdr_t;

/*%
 * The in-core representation of the RR header.
 */
typedef struct {
	isc_uint32_t	size;
} journal_rrhdr_t;


/*%
 * Initial contents to store in the header of a newly created
 * journal file.
 *
 * The header starts with the magic string ";BIND LOG V9\n"
 * to identify the file as a BIND 9 journal file.  An ASCII
 * identification string is used rather than a binary magic
 * number to be consistent with BIND 8 (BIND 8 journal files
 * are ASCII text files).
 */

static journal_header_t
initial_journal_header = { ";BIND LOG V9\n", { 0, 0 }, { 0, 0 }, 0 };

#define JOURNAL_EMPTY(h) ((h)->begin.offset == (h)->end.offset)

typedef enum {
	JOURNAL_STATE_INVALID,
	JOURNAL_STATE_READ,
	JOURNAL_STATE_WRITE,
	JOURNAL_STATE_TRANSACTION
} journal_state_t;

struct dns_journal {
	unsigned int		magic;		/*%< JOUR */
	isc_mem_t		*mctx;		/*%< Memory context */
	journal_state_t		state;
	const char 		*filename;	/*%< Journal file name */
	FILE *			fp;		/*%< File handle */
	isc_offset_t		offset;		/*%< Current file offset */
	journal_header_t 	header;		/*%< In-core journal header */
	unsigned char		*rawindex;	/*%< In-core buffer for journal index in on-disk format */
	journal_pos_t		*index;		/*%< In-core journal index */

	/*% Current transaction state (when writing). */
	struct {
		unsigned int	n_soa;		/*%< Number of SOAs seen */
		journal_pos_t	pos[2];		/*%< Begin/end position */
	} x;

	/*% Iteration state (when reading). */
	struct {
		/* These define the part of the journal we iterate over. */
		journal_pos_t bpos;		/*%< Position before first, */
		journal_pos_t epos;		/*%< and after last transaction */
		/* The rest is iterator state. */
		isc_uint32_t current_serial;	/*%< Current SOA serial */
		isc_buffer_t source;		/*%< Data from disk */
		isc_buffer_t target;		/*%< Data from _fromwire check */
		dns_decompress_t dctx;		/*%< Dummy decompression ctx */
		dns_name_t name;		/*%< Current domain name */
		dns_rdata_t rdata;		/*%< Current rdata */
		isc_uint32_t ttl;		/*%< Current TTL */
		unsigned int xsize;		/*%< Size of transaction data */
		unsigned int xpos;		/*%< Current position in it */
		isc_result_t result;		/*%< Result of last call */
	} it;
};

#define DNS_JOURNAL_MAGIC	ISC_MAGIC('J', 'O', 'U', 'R')
#define DNS_JOURNAL_VALID(t)	ISC_MAGIC_VALID(t, DNS_JOURNAL_MAGIC)

static void
journal_pos_decode(journal_rawpos_t *raw, journal_pos_t *cooked) {
	cooked->serial = decode_uint32(raw->serial);
	cooked->offset = decode_uint32(raw->offset);
}

static void
journal_pos_encode(journal_rawpos_t *raw, journal_pos_t *cooked) {
	encode_uint32(cooked->serial, raw->serial);
	encode_uint32(cooked->offset, raw->offset);
}

static void
journal_header_decode(journal_rawheader_t *raw, journal_header_t *cooked) {
	INSIST(sizeof(cooked->format) == sizeof(raw->h.format));
	memcpy(cooked->format, raw->h.format, sizeof(cooked->format));
	journal_pos_decode(&raw->h.begin, &cooked->begin);
	journal_pos_decode(&raw->h.end, &cooked->end);
	cooked->index_size = decode_uint32(raw->h.index_size);
}

static void
journal_header_encode(journal_header_t *cooked, journal_rawheader_t *raw) {
	INSIST(sizeof(cooked->format) == sizeof(raw->h.format));
	memset(raw->pad, 0, sizeof(raw->pad));
	memcpy(raw->h.format, cooked->format, sizeof(raw->h.format));
	journal_pos_encode(&raw->h.begin, &cooked->begin);
	journal_pos_encode(&raw->h.end, &cooked->end);
	encode_uint32(cooked->index_size, raw->h.index_size);
}

/*
 * Journal file I/O subroutines, with error checking and reporting.
 */
static isc_result_t
journal_seek(dns_journal_t *j, isc_uint32_t offset) {
	isc_result_t result;
	result = isc_stdio_seek(j->fp, (long)offset, SEEK_SET);
	if (result != ISC_R_SUCCESS) {
		isc_log_write(JOURNAL_COMMON_LOGARGS, ISC_LOG_ERROR,
			      "%s: seek: %s", j->filename,
			      isc_result_totext(result));
		return (ISC_R_UNEXPECTED);
	}
	j->offset = offset;
	return (ISC_R_SUCCESS);
}

static isc_result_t
journal_read(dns_journal_t *j, void *mem, size_t nbytes) {
	isc_result_t result;

	result = isc_stdio_read(mem, 1, nbytes, j->fp, NULL);
	if (result != ISC_R_SUCCESS) {
		if (result == ISC_R_EOF)
			return (ISC_R_NOMORE);
		isc_log_write(JOURNAL_COMMON_LOGARGS, ISC_LOG_ERROR,
			      "%s: read: %s",
			      j->filename, isc_result_totext(result));
		return (ISC_R_UNEXPECTED);
	}
	j->offset += nbytes;
	return (ISC_R_SUCCESS);
}

static isc_result_t
journal_write(dns_journal_t *j, void *mem, size_t nbytes) {
	isc_result_t result;

	result = isc_stdio_write(mem, 1, nbytes, j->fp, NULL);
	if (result != ISC_R_SUCCESS) {
		isc_log_write(JOURNAL_COMMON_LOGARGS, ISC_LOG_ERROR,
			      "%s: write: %s",
			      j->filename, isc_result_totext(result));
		return (ISC_R_UNEXPECTED);
	}
	j->offset += nbytes;
	return (ISC_R_SUCCESS);
}

static isc_result_t
journal_fsync(dns_journal_t *j) {
	isc_result_t result;
	result = isc_stdio_flush(j->fp);
	if (result != ISC_R_SUCCESS) {
		isc_log_write(JOURNAL_COMMON_LOGARGS, ISC_LOG_ERROR,
			      "%s: flush: %s",
			      j->filename, isc_result_totext(result));
		return (ISC_R_UNEXPECTED);
	}
	result = isc_stdio_sync(j->fp);
	if (result != ISC_R_SUCCESS) {
		isc_log_write(JOURNAL_COMMON_LOGARGS, ISC_LOG_ERROR,
			      "%s: fsync: %s",
			      j->filename, isc_result_totext(result));
		return (ISC_R_UNEXPECTED);
	}
	return (ISC_R_SUCCESS);
}

/*
 * Read/write a transaction header at the current file position.
 */

static isc_result_t
journal_read_xhdr(dns_journal_t *j, journal_xhdr_t *xhdr) {
	journal_rawxhdr_t raw;
	isc_result_t result;
	result = journal_read(j, &raw, sizeof(raw));
	if (result != ISC_R_SUCCESS)
		return (result);
	xhdr->size = decode_uint32(raw.size);
	xhdr->serial0 = decode_uint32(raw.serial0);
	xhdr->serial1 = decode_uint32(raw.serial1);
	return (ISC_R_SUCCESS);
}

static isc_result_t
journal_write_xhdr(dns_journal_t *j, isc_uint32_t size,
		   isc_uint32_t serial0, isc_uint32_t serial1)
{
	journal_rawxhdr_t raw;
	encode_uint32(size, raw.size);
	encode_uint32(serial0, raw.serial0);
	encode_uint32(serial1, raw.serial1);
	return (journal_write(j, &raw, sizeof(raw)));
}


/*
 * Read an RR header at the current file position.
 */

static isc_result_t
journal_read_rrhdr(dns_journal_t *j, journal_rrhdr_t *rrhdr) {
	journal_rawrrhdr_t raw;
	isc_result_t result;
	result = journal_read(j, &raw, sizeof(raw));
	if (result != ISC_R_SUCCESS)
		return (result);
	rrhdr->size = decode_uint32(raw.size);
	return (ISC_R_SUCCESS);
}

static isc_result_t
journal_file_create(isc_mem_t *mctx, const char *filename) {
	FILE *fp = NULL;
	isc_result_t result;
	journal_header_t header;
	journal_rawheader_t rawheader;
	int index_size = 56; /* XXX configurable */
	int size;
	void *mem; /* Memory for temporary index image. */

	INSIST(sizeof(journal_rawheader_t) == JOURNAL_HEADER_SIZE);

	result = isc_stdio_open(filename, "wb", &fp);
	if (result != ISC_R_SUCCESS) {
		isc_log_write(JOURNAL_COMMON_LOGARGS, ISC_LOG_ERROR,
			      "%s: create: %s",
			      filename, isc_result_totext(result));
		return (ISC_R_UNEXPECTED);
	}

	header = initial_journal_header;
	header.index_size = index_size;
	journal_header_encode(&header, &rawheader);

	size = sizeof(journal_rawheader_t) +
		index_size * sizeof(journal_rawpos_t);

	mem = isc_mem_get(mctx, size);
	if (mem == NULL) {
		(void)isc_stdio_close(fp);
		(void)isc_file_remove(filename);
		return (ISC_R_NOMEMORY);
	}
	memset(mem, 0, size);
	memcpy(mem, &rawheader, sizeof(rawheader));

	result = isc_stdio_write(mem, 1, (size_t) size, fp, NULL);
	if (result != ISC_R_SUCCESS) {
		isc_log_write(JOURNAL_COMMON_LOGARGS, ISC_LOG_ERROR,
				 "%s: write: %s",
				 filename, isc_result_totext(result));
		(void)isc_stdio_close(fp);
		(void)isc_file_remove(filename);
		isc_mem_put(mctx, mem, size);
		return (ISC_R_UNEXPECTED);
	}
	isc_mem_put(mctx, mem, size);

	result = isc_stdio_close(fp);
	if (result != ISC_R_SUCCESS) {
		isc_log_write(JOURNAL_COMMON_LOGARGS, ISC_LOG_ERROR,
				 "%s: close: %s",
				 filename, isc_result_totext(result));
		(void)isc_file_remove(filename);
		return (ISC_R_UNEXPECTED);
	}

	return (ISC_R_SUCCESS);
}

static isc_result_t
journal_open(isc_mem_t *mctx, const char *filename, isc_boolean_t write,
	     isc_boolean_t create, dns_journal_t **journalp) {
	FILE *fp = NULL;
	isc_result_t result;
	journal_rawheader_t rawheader;
	dns_journal_t *j;

	INSIST(journalp != NULL && *journalp == NULL);
	j = isc_mem_get(mctx, sizeof(*j));
	if (j == NULL)
		return (ISC_R_NOMEMORY);

	j->mctx = mctx;
	j->state = JOURNAL_STATE_INVALID;
	j->fp = NULL;
	j->filename = filename;
	j->index = NULL;
	j->rawindex = NULL;

	result = isc_stdio_open(j->filename, write ? "rb+" : "rb", &fp);

	if (result == ISC_R_FILENOTFOUND) {
		if (create) {
			isc_log_write(JOURNAL_COMMON_LOGARGS,
				      ISC_LOG_INFO,
				      "journal file %s does not exist, "
				      "creating it",
				      j->filename);
			CHECK(journal_file_create(mctx, filename));
			/*
			 * Retry.
			 */
			result = isc_stdio_open(j->filename, "rb+", &fp);
		} else {
			FAIL(ISC_R_NOTFOUND);
		}
	}
	if (result != ISC_R_SUCCESS) {
		isc_log_write(JOURNAL_COMMON_LOGARGS, ISC_LOG_ERROR,
			      "%s: open: %s",
			      j->filename, isc_result_totext(result));
		FAIL(ISC_R_UNEXPECTED);
	}

	j->fp = fp;

	/*
	 * Set magic early so that seek/read can succeed.
	 */
	j->magic = DNS_JOURNAL_MAGIC;

	CHECK(journal_seek(j, 0));
	CHECK(journal_read(j, &rawheader, sizeof(rawheader)));

	if (memcmp(rawheader.h.format, initial_journal_header.format,
		   sizeof(initial_journal_header.format)) != 0) {
		isc_log_write(JOURNAL_COMMON_LOGARGS, ISC_LOG_ERROR,
				 "%s: journal format not recognized",
				 j->filename);
		FAIL(ISC_R_UNEXPECTED);
	}
	journal_header_decode(&rawheader, &j->header);

	/*
	 * If there is an index, read the raw index into a dynamically
	 * allocated buffer and then convert it into a cooked index.
	 */
	if (j->header.index_size != 0) {
		unsigned int i;
		unsigned int rawbytes;
		unsigned char *p;

		rawbytes = j->header.index_size * sizeof(journal_rawpos_t);
		j->rawindex = isc_mem_get(mctx, rawbytes);
		if (j->rawindex == NULL)
			FAIL(ISC_R_NOMEMORY);

		CHECK(journal_read(j, j->rawindex, rawbytes));

		j->index = isc_mem_get(mctx, j->header.index_size *
				       sizeof(journal_pos_t));
		if (j->index == NULL)
			FAIL(ISC_R_NOMEMORY);

		p = j->rawindex;
		for (i = 0; i < j->header.index_size; i++) {
			j->index[i].serial = decode_uint32(p);
			p += 4;
			j->index[i].offset = decode_uint32(p);
			p += 4;
		}
		INSIST(p == j->rawindex + rawbytes);
	}
	j->offset = -1; /* Invalid, must seek explicitly. */

	/*
	 * Initialize the iterator.
	 */
	dns_name_init(&j->it.name, NULL);
	dns_rdata_init(&j->it.rdata);

	/*
	 * Set up empty initial buffers for uncheched and checked
	 * wire format RR data.  They will be reallocated
	 * later.
	 */
	isc_buffer_init(&j->it.source, NULL, 0);
	isc_buffer_init(&j->it.target, NULL, 0);
	dns_decompress_init(&j->it.dctx, -1, DNS_DECOMPRESS_NONE);

	j->state =
		write ? JOURNAL_STATE_WRITE : JOURNAL_STATE_READ;

	*journalp = j;
	return (ISC_R_SUCCESS);

 failure:
	j->magic = 0;
	if (j->index != NULL) {
		isc_mem_put(j->mctx, j->index, j->header.index_size *
			    sizeof(journal_rawpos_t));
		j->index = NULL;
	}
	if (j->fp != NULL)
		(void)isc_stdio_close(j->fp);
	isc_mem_put(j->mctx, j, sizeof(*j));
	return (result);
}

isc_result_t
dns_journal_open(isc_mem_t *mctx, const char *filename, isc_boolean_t write,
		 dns_journal_t **journalp) {
	return (journal_open(mctx, filename, write, write, journalp));
}

/*
 * A comparison function defining the sorting order for
 * entries in the IXFR-style journal file.
 *
 * The IXFR format requires that deletions are sorted before
 * additions, and within either one, SOA records are sorted
 * before others.
 *
 * Also sort the non-SOA records by type as a courtesy to the
 * server receiving the IXFR - it may help reduce the amount of
 * rdataset merging it has to do.
 */
static int
ixfr_order(const void *av, const void *bv) {
	dns_difftuple_t const * const *ap = av;
	dns_difftuple_t const * const *bp = bv;
	dns_difftuple_t const *a = *ap;
	dns_difftuple_t const *b = *bp;
	int r;

	r = (b->op == DNS_DIFFOP_DEL) - (a->op == DNS_DIFFOP_DEL);
	if (r != 0)
		return (r);

	r = (b->rdata.type == dns_rdatatype_soa) -
		(a->rdata.type == dns_rdatatype_soa);
	if (r != 0)
		return (r);

	r = (a->rdata.type - b->rdata.type);
	return (r);
}

/*
 * Advance '*pos' to the next journal transaction.
 *
 * Requires:
 *	*pos refers to a valid journal transaction.
 *
 * Ensures:
 *	When ISC_R_SUCCESS is returned,
 *	*pos refers to the next journal transaction.
 *
 * Returns one of:
 *
 *    ISC_R_SUCCESS
 *    ISC_R_NOMORE 	*pos pointed at the last transaction
 *    Other results due to file errors are possible.
 */
static isc_result_t
journal_next(dns_journal_t *j, journal_pos_t *pos) {
	isc_result_t result;
	journal_xhdr_t xhdr;
	REQUIRE(DNS_JOURNAL_VALID(j));

	result = journal_seek(j, pos->offset);
	if (result != ISC_R_SUCCESS)
		return (result);

	if (pos->serial == j->header.end.serial)
		return (ISC_R_NOMORE);
	/*
	 * Read the header of the current transaction.
	 * This will return ISC_R_NOMORE if we are at EOF.
	 */
	result = journal_read_xhdr(j, &xhdr);
	if (result != ISC_R_SUCCESS)
		return (result);

	/*
	 * Check serial number consistency.
	 */
	if (xhdr.serial0 != pos->serial) {
		isc_log_write(JOURNAL_COMMON_LOGARGS, ISC_LOG_ERROR,
			      "%s: journal file corrupt: "
			      "expected serial %u, got %u",
			      j->filename, pos->serial, xhdr.serial0);
		return (ISC_R_UNEXPECTED);
	}

	/*
	 * Check for offset wraparound.
	 */
	if ((isc_offset_t)(pos->offset + sizeof(journal_rawxhdr_t) + xhdr.size)
	    < pos->offset) {
		isc_log_write(JOURNAL_COMMON_LOGARGS, ISC_LOG_ERROR,
			      "%s: offset too large", j->filename);
		return (ISC_R_UNEXPECTED);
	}

	pos->offset += sizeof(journal_rawxhdr_t) + xhdr.size;
	pos->serial = xhdr.serial1;
	return (ISC_R_SUCCESS);
}

/*
 * If the index of the journal 'j' contains an entry "better"
 * than '*best_guess', replace '*best_guess' with it.
 *
 * "Better" means having a serial number closer to 'serial'
 * but not greater than 'serial'.
 */
static void
index_find(dns_journal_t *j, isc_uint32_t serial, journal_pos_t *best_guess) {
	unsigned int i;
	if (j->index == NULL)
		return;
	for (i = 0; i < j->header.index_size; i++) {
		if (POS_VALID(j->index[i]) &&
		    DNS_SERIAL_GE(serial, j->index[i].serial) &&
		    DNS_SERIAL_GT(j->index[i].serial, best_guess->serial))
			*best_guess = j->index[i];
	}
}

/*
 * Add a new index entry.  If there is no room, make room by removing
 * the odd-numbered entries and compacting the others into the first
 * half of the index.  This decimates old index entries exponentially
 * over time, so that the index always contains a much larger fraction
 * of recent serial numbers than of old ones.  This is deliberate -
 * most index searches are for outgoing IXFR, and IXFR tends to request
 * recent versions more often than old ones.
 */
static void
index_add(dns_journal_t *j, journal_pos_t *pos) {
	unsigned int i;
	if (j->index == NULL)
		return;
	/*
	 * Search for a vacant position.
	 */
	for (i = 0; i < j->header.index_size; i++) {
		if (! POS_VALID(j->index[i]))
			break;
	}
	if (i == j->header.index_size) {
		unsigned int k = 0;
		/*
		 * Found no vacant position.  Make some room.
		 */
		for (i = 0; i < j->header.index_size; i += 2) {
			j->index[k++] = j->index[i];
		}
		i = k; /* 'i' identifies the first vacant position. */
		while (k < j->header.index_size) {
			POS_INVALIDATE(j->index[k]);
			k++;
		}
	}
	INSIST(i < j->header.index_size);
	INSIST(! POS_VALID(j->index[i]));

	/*
	 * Store the new index entry.
	 */
	j->index[i] = *pos;
}

/*
 * Invalidate any existing index entries that could become
 * ambiguous when a new transaction with number 'serial' is added.
 */
static void
index_invalidate(dns_journal_t *j, isc_uint32_t serial) {
	unsigned int i;
	if (j->index == NULL)
		return;
	for (i = 0; i < j->header.index_size; i++) {
		if (! DNS_SERIAL_GT(serial, j->index[i].serial))
			POS_INVALIDATE(j->index[i]);
	}
}

/*
 * Try to find a transaction with initial serial number 'serial'
 * in the journal 'j'.
 *
 * If found, store its position at '*pos' and return ISC_R_SUCCESS.
 *
 * If 'serial' is current (= the ending serial number of the
 * last transaction in the journal), set '*pos' to
 * the position immediately following the last transaction and
 * return ISC_R_SUCCESS.
 *
 * If 'serial' is within the range of addressable serial numbers
 * covered by the journal but that particular serial number is missing
 * (from the journal, not just from the index), return ISC_R_NOTFOUND.
 *
 * If 'serial' is outside the range of addressable serial numbers
 * covered by the journal, return ISC_R_RANGE.
 *
 */
static isc_result_t
journal_find(dns_journal_t *j, isc_uint32_t serial, journal_pos_t *pos) {
	isc_result_t result;
	journal_pos_t current_pos;
	REQUIRE(DNS_JOURNAL_VALID(j));

	if (DNS_SERIAL_GT(j->header.begin.serial, serial))
		return (ISC_R_RANGE);
	if (DNS_SERIAL_GT(serial, j->header.end.serial))
		return (ISC_R_RANGE);
	if (serial == j->header.end.serial) {
		*pos = j->header.end;
		return (ISC_R_SUCCESS);
	}

	current_pos = j->header.begin;
	index_find(j, serial, &current_pos);

	while (current_pos.serial != serial) {
		if (DNS_SERIAL_GT(current_pos.serial, serial))
			return (ISC_R_NOTFOUND);
		result = journal_next(j, &current_pos);
		if (result != ISC_R_SUCCESS)
			return (result);
	}
	*pos = current_pos;
	return (ISC_R_SUCCESS);
}

isc_result_t
dns_journal_begin_transaction(dns_journal_t *j) {
	isc_uint32_t offset;
	isc_result_t result;
	journal_rawxhdr_t hdr;

	REQUIRE(DNS_JOURNAL_VALID(j));
	REQUIRE(j->state == JOURNAL_STATE_WRITE);

	/*
	 * Find the file offset where the new transaction should
	 * be written, and seek there.
	 */
	if (JOURNAL_EMPTY(&j->header)) {
		offset = sizeof(journal_rawheader_t) +
			j->header.index_size * sizeof(journal_rawpos_t);
	} else {
		offset = j->header.end.offset;
	}
	j->x.pos[0].offset = offset;
	j->x.pos[1].offset = offset; /* Initial value, will be incremented. */
	j->x.n_soa = 0;

	CHECK(journal_seek(j, offset));

	/*