/*
 * ixfr.c -- generating IXFR responses.
 *
 * Copyright (c) 2021, NLnet Labs. All rights reserved.
 *
 * See LICENSE for the license.
 *
 */

#include "config.h"

#include <errno.h>
#include <string.h>
#include <ctype.h>
#ifdef HAVE_SYS_TYPES_H
#  include <sys/types.h>
#endif
#ifdef HAVE_SYS_STAT_H
#  include <sys/stat.h>
#endif
#include <unistd.h>

#include "ixfr.h"
#include "packet.h"
#include "rdata.h"
#include "axfr.h"
#include "options.h"
#include "zonec.h"
#include "zone.h"

/*
 * For optimal compression IXFR response packets are limited in size
 * to MAX_COMPRESSION_OFFSET.
 */
#define IXFR_MAX_MESSAGE_LEN MAX_COMPRESSION_OFFSET

/* draft-ietf-dnsop-rfc2845bis-06, section 5.3.1 says to sign every packet */
#define IXFR_TSIG_SIGN_EVERY_NTH	0	/* tsig sign every N packets. */

/* initial space in rrs data for storing records */
#define IXFR_STORE_INITIAL_SIZE 4096

/* store compression for one name */
struct rrcompress_entry {
	/* rbtree node, key is this struct */
	struct rbnode node;
	/* the uncompressed domain name */
	const uint8_t* dname;
	/* the length of the dname, includes terminating 0 label */
	uint16_t len;
	/* the offset of the dname in the packet */
	uint16_t offset;
};

/* structure to store compression data for the packet */
struct pktcompression {
	/* rbtree of rrcompress_entry. sorted by dname */
	struct rbtree tree;
	/* allocation information, how many bytes allocated now */
	size_t alloc_now;
	/* allocation information, total size in block */
	size_t alloc_max;
	/* region to use if block full, this is NULL if unused */
	struct region* region;
	/* block of temp data for allocation */
	uint8_t block[sizeof(struct rrcompress_entry)*1024];
};

/* compare two elements in the compression tree. Returns -1, 0, or 1. */
static int compression_cmp(const void* a, const void* b)
{
	struct rrcompress_entry* rra = (struct rrcompress_entry*)a;
	struct rrcompress_entry* rrb = (struct rrcompress_entry*)b;
	if(rra->len != rrb->len) {
		if(rra->len < rrb->len)
			return -1;
		return 1;
	}
	return memcmp(rra->dname, rrb->dname, rra->len);
}

/* init the pktcompression to a new packet */
static void pktcompression_init(struct pktcompression* pcomp)
{
	pcomp->alloc_now = 0;
	pcomp->alloc_max = sizeof(pcomp->block);
	pcomp->region = NULL;
	pcomp->tree.root = RBTREE_NULL;
	pcomp->tree.count = 0;
	pcomp->tree.region = NULL;
	pcomp->tree.cmp = &compression_cmp;
}

/* freeup the pktcompression data */
static void pktcompression_freeup(struct pktcompression* pcomp)
{
	if(pcomp->region) {
		region_destroy(pcomp->region);
		pcomp->region = NULL;
	}
	pcomp->alloc_now = 0;
	pcomp->tree.root = RBTREE_NULL;
	pcomp->tree.count = 0;
}

/* alloc data in pktcompression */
static void* pktcompression_alloc(struct pktcompression* pcomp, size_t s)
{
	/* first attempt to allocate in the fixed block,
	 * that is very fast and on the stack in the pcomp struct */
	if(pcomp->alloc_now + s <= pcomp->alloc_max) {
		void* ret = pcomp->block + pcomp->alloc_now;
		pcomp->alloc_now += s;
		return ret;
	}

	/* if that fails, create a region to allocate in,
	 * it is freed in the freeup */
	if(!pcomp->region) {
		pcomp->region = region_create(xalloc, free);
		if(!pcomp->region)
			return NULL;
	}
	return region_alloc(pcomp->region, s);
}

/* find a pktcompression name, return offset if found */
static uint16_t pktcompression_find(struct pktcompression* pcomp,
	const uint8_t* dname, size_t len)
{
	struct rrcompress_entry key, *found;
	key.node.key = &key;
	key.dname = dname;
	key.len = len;
	found = (struct rrcompress_entry*)rbtree_search(&pcomp->tree, &key);
	if(found) return found->offset;
	return 0;
}

/* insert a new domain name into the compression tree.
 * it fails silently, no need to compress then. */
static void pktcompression_insert(struct pktcompression* pcomp,
	const uint8_t* dname, size_t len, uint16_t offset)
{
	struct rrcompress_entry* entry;
	if(len > 65535)
		return;
	if(offset > MAX_COMPRESSION_OFFSET)
		return; /* too far for a compression pointer */
	entry = pktcompression_alloc(pcomp, sizeof(*entry));
	if(!entry)
		return;
	memset(&entry->node, 0, sizeof(entry->node));
	entry->node.key = entry;
	entry->dname = dname;
	entry->len = len;
	entry->offset = offset;
	(void)rbtree_insert(&pcomp->tree, &entry->node);
}

/* insert all the labels of a domain name */
static void pktcompression_insert_with_labels(struct pktcompression* pcomp,
	uint8_t* dname, size_t len, uint16_t offset)
{
	if(!dname)
		return;
	if(offset > MAX_COMPRESSION_OFFSET)
		return;

	/* while we have not seen the end root label */
	while(len > 0 && dname[0] != 0) {
		size_t lablen;
		pktcompression_insert(pcomp, dname, len, offset);
		lablen = (size_t)(dname[0]);
		if( (lablen&0xc0) )
			return; /* the dname should be uncompressed */
		if(lablen+1 > len)
			return; /* len should be uncompressed wireformat len */
		if(offset > MAX_COMPRESSION_OFFSET - lablen - 1)
			return; /* offset moves too far for compression */
		/* skip label */
		len -= lablen+1;
		dname += lablen+1;
		offset += lablen+1;
	}
}

/* write a compressed domain name into the packet,
 * returns uncompressed wireformat length,
 * 0 if it does not fit and -1 on failure, bad dname. */
static int pktcompression_write_dname(struct buffer* packet,
	struct pktcompression* pcomp, const uint8_t* rr, size_t rrlen)
{
	size_t wirelen = 0;
	size_t dname_len = buf_dname_length(rr, rrlen);
	if(!rr || rrlen == 0 || dname_len == 0)
		return 0;
	while(rrlen > 0 && rr[0] != 0) {
		size_t lablen = (size_t)(rr[0]);
		uint16_t offset;
		if( (lablen&0xc0) )
			return -1; /* name should be uncompressed */
		if(lablen+1 > rrlen)
			return -1; /* name should fit */

		/* see if the domain name has a compression pointer */
		if((offset=pktcompression_find(pcomp, rr, dname_len))!=0) {
			if(!buffer_available(packet, 2))
				return 0;
			buffer_write_u16(packet, (uint16_t)(0xc000 | offset));
			wirelen += dname_len;
			return wirelen;
		} else {
			if(!buffer_available(packet, lablen+1))
				return 0;
			/* insert the domain name at this position */
			pktcompression_insert(pcomp, rr, dname_len,
				buffer_position(packet));
			/* write it */
			buffer_write(packet, rr, lablen+1);
		}

		wirelen += lablen+1;
		rr += lablen+1;
		rrlen -= lablen+1;
		dname_len -= lablen+1;
	}
	if(rrlen > 0 && rr[0] == 0) {
		/* write end root label */
		if(!buffer_available(packet, 1))
			return 0;
		buffer_write_u8(packet, 0);
		wirelen += 1;
	}
	return wirelen;
}

static int ixfr_write_rdata_pkt(struct buffer* packet, uint16_t tp,
	struct pktcompression* pcomp, const uint8_t* rr, size_t rdlen)
{
	const struct nsd_type_descriptor* descriptor = nsd_type_descriptor(tp);
	size_t i;
	uint16_t offset; /* The offset in rr. */

	/* The rr points at the start of the rdata of length rdlen.
	 * This is uncompressed wireformat. */

	if(!descriptor->is_compressible) {
		if(!buffer_available(packet, rdlen))
			return 0;
		buffer_write(packet, rr, rdlen);
		return 1;
	}

	/* It is compressible, loop over the fields and write compressed
	 * domain names, when the rdata has a compressible name. */
	offset = 0;
	for(i=0; i < descriptor->rdata.length; i++) {
		const nsd_rdata_descriptor_type* field =
			&descriptor->rdata.fields[i];
		uint16_t field_len = 0;
		int already_written = 0;
		if(rdlen == offset && field->is_optional)
			break; /* There are no more rdata fields. */
		if(field->calculate_length_uncompressed_wire) {
			/* Call field length function. */
			/* This is called with an uncompressed wireformat
			 * data buffer, instead of the in-memory data buffer.
			 * For IPSECKEY it does not matter, since it has
			 * a literal dname storage. */
			struct domain* domain;
			int32_t l = field->calculate_length_uncompressed_wire(
				rdlen, rr, offset, &domain);
			if(l < 0)
				return 1; /* attempt to skip malformed rr */
			field_len = l;
			if(domain) {
				/* Treat as uncompressed dname, to be safe. */
				/* Write as an uncompressed name. */
				if(!buffer_available(packet,
					domain_dname(domain)->name_size))
					return 0;
				buffer_write(packet,
					dname_name(domain_dname(domain)),
					domain_dname(domain)->name_size);
				already_written = 1;
			}
		} else if(field->length >= 0) {
			field_len = field->length;
		} else {
			size_t dlen;
			int dname_len;
			switch(field->length) {
				/* The dnames are stored in uncompressed
				 * wireformat in the uncompressed wireformat
				 * string. */
			case RDATA_COMPRESSED_DNAME:
				/* Attempt to compress the compressible
				 * name. */
				dname_len = pktcompression_write_dname(packet,
					pcomp, rr+offset, rdlen-offset);
				if(dname_len == -1)
					return 1; /* attempt to skip malformed rr */
				if(dname_len == 0)
					return 0;
				field_len = dname_len;
				already_written = 1;
				break;
			case RDATA_UNCOMPRESSED_DNAME:
			case RDATA_LITERAL_DNAME:
				/* Write as an uncompressed name. */
				if(rdlen-offset<1)
					return 1; /* attempt to skip malformed rr */
				dlen = buf_dname_length(rr+offset,
					rdlen-offset);
				if(dlen == 0)
					return 1; /* attempt to skip malformed rr */
				field_len = dlen;
				break;
			case RDATA_STRING:
			case RDATA_BINARY:
				if(rdlen-offset<1)
					return 1; /* attempt to skip malformed rr */
				field_len = ((uint16_t)(rr+offset)[0]) + 1;
				break;
			case RDATA_IPSECGATEWAY:
			case RDATA_AMTRELAY_RELAY:
				/* This should have called the callback. */
				return 1; /* attempt to skip malformed rr */
			case RDATA_REMAINDER:
				field_len = rdlen - offset;
				break;
			default:
				/* Unknown specialized value. */
				return 1; /* attempt to skip malformed rr */
			}
		}
		if((size_t)offset+field_len > rdlen)
			return 1; /* attempt to skip malformed rr */
		if(!already_written) {
			if(!buffer_available(packet, field_len))
				return 0;
			buffer_write(packet, rr+offset, field_len);
		}
		offset += field_len;
	}
	return 1;
}

/* write an RR into the packet with compression for domain names,
 * return 0 and resets position if it does not fit in the packet. */
static int ixfr_write_rr_pkt(struct query* query, struct buffer* packet,
	struct pktcompression* pcomp, const uint8_t* rr, size_t rrlen,
	uint16_t total_added)
{
	size_t oldpos = buffer_position(packet);
	size_t rdpos;
	uint16_t tp;
	int dname_len;
	size_t rdlen;

	if(total_added == 0) {
		size_t oldmaxlen = query->maxlen;
		/* RR > 16K can be first RR */
		query->maxlen = (query->tcp?TCP_MAX_MESSAGE_LEN:UDP_MAX_MESSAGE_LEN);
		if(query_overflow(query)) {
			query->maxlen = oldmaxlen;
			return 0;
		}
		query->maxlen = oldmaxlen;
	} else {
		if(buffer_position(packet) > MAX_COMPRESSION_OFFSET
			|| query_overflow(query)) {
			/* we are past the maximum length */
			return 0;
		}
	}

	/* write owner */
	dname_len = pktcompression_write_dname(packet, pcomp, rr, rrlen);
	if(dname_len == -1)
		return 1; /* attempt to skip this malformed rr, could assert */
	if(dname_len == 0) {
		buffer_set_position(packet, oldpos);
		return 0;
	}
	rr += dname_len;
	rrlen -= dname_len;

	/* type, class, ttl, rdatalen */
	if(!buffer_available(packet, 10)) {
		buffer_set_position(packet, oldpos);
		return 0;
	}
	if(10 > rrlen)
		return 1; /* attempt to skip this malformed rr, could assert */
	tp = read_uint16(rr);
	buffer_write(packet, rr, 8);
	rr += 8;
	rrlen -= 8;
	rdlen = read_uint16(rr);
	rr += 2;
	rrlen -= 2;
	rdpos = buffer_position(packet);
	buffer_write_u16(packet, 0);
	if(rdlen > rrlen)
		return 1; /* attempt to skip this malformed rr, could assert */

	/* rdata */
	if(!ixfr_write_rdata_pkt(packet, tp, pcomp, rr, rdlen)) {
		buffer_set_position(packet, oldpos);
		return 0;
	}

	/* write compressed rdata length */
	buffer_write_u16_at(packet, rdpos, buffer_position(packet)-rdpos-2);
	if(total_added == 0) {
		size_t oldmaxlen = query->maxlen;
		query->maxlen = (query->tcp?TCP_MAX_MESSAGE_LEN:UDP_MAX_MESSAGE_LEN);
		if(query_overflow(query)) {
			query->maxlen = oldmaxlen;
			buffer_set_position(packet, oldpos);
			return 0;
		}
		query->maxlen = oldmaxlen;
	} else {
		if(query_overflow(query)) {
			/* we are past the maximum length */
			buffer_set_position(packet, oldpos);
			return 0;
		}
	}
	return 1;
}

/* parse the serial number from the IXFR query */
static int parse_qserial(struct buffer* packet, uint32_t* qserial,
	size_t* snip_pos)
{
	unsigned int i;
	uint16_t type, rdlen;
	/* we must have a SOA in the authority section */
	if(NSCOUNT(packet) == 0)
		return 0;
	/* skip over the question section, we want only one */
	buffer_set_position(packet, QHEADERSZ);
	if(QDCOUNT(packet) != 1)
		return 0;
	if(!packet_skip_rr(packet, 1))
		return 0;
	/* set position to snip off the authority section */
	*snip_pos = buffer_position(packet);
	/* skip over the authority section RRs until we find the SOA */
	for(i=0; i<NSCOUNT(packet); i++) {
		/* is this the SOA record? */
		if(!packet_skip_dname(packet))
			return 0; /* malformed name */
		if(!buffer_available(packet, 10))
			return 0; /* no type,class,ttl,rdatalen */
		type = buffer_read_u16(packet);
		buffer_skip(packet, 6);
		rdlen = buffer_read_u16(packet);
		if(!buffer_available(packet, rdlen))
			return 0;
		if(type == TYPE_SOA) {
			/* read serial from rdata, skip two dnames, then
			 * read the 32bit value */
			if(!packet_skip_dname(packet))
				return 0; /* malformed nsname */
			if(!packet_skip_dname(packet))
				return 0; /* malformed rname */
			if(!buffer_available(packet, 4))
				return 0;
			*qserial = buffer_read_u32(packet);
			return 1;
		}
		buffer_skip(packet, rdlen);
	}
	return 0;
}

/* get serial from SOA rdata */
static uint32_t soa_rdata_get_serial(uint8_t* rdata, uint16_t rdlength)
{
	if(rdlength < 2*sizeof(void*) /* name ptr */ + 4 /* serial */)
		return 0;
	return read_uint32(rdata+2*sizeof(void*));
}

/* get serial from SOA RR */
static uint32_t soa_rr_get_serial(struct rr* rr)
{
	return soa_rdata_get_serial(rr->rdata, rr->rdlength);
}

/* get the current serial from the zone */
uint32_t zone_get_current_serial(struct zone* zone)
{
	if(!zone || !zone->soa_rrset)
		return 0;
	if(zone->soa_rrset->rr_count == 0)
		return 0;
	return soa_rr_get_serial(zone->soa_rrset->rrs[0]);
}

/* iterator over ixfr data. find first element, eg. oldest zone version
 * change.
 * The iterator can be started with the ixfr_data_first, but also with
 * ixfr_data_last, or with an existing ixfr_data element to start from.
 * Continue by using ixfr_data_next or ixfr_data_prev to ask for more elements
 * until that returns NULL. NULL because end of list or loop was detected.
 * The ixfr_data_prev uses a counter, start it at 0, it returns NULL when
 * a loop is detected.
 */
static struct ixfr_data* ixfr_data_first(struct zone_ixfr* ixfr)
{
	struct ixfr_data* n;
	if(!ixfr || !ixfr->data || ixfr->data->count==0)
		return NULL;
	n = (struct ixfr_data*)rbtree_search(ixfr->data, &ixfr->oldest_serial);
	if(!n || n == (struct ixfr_data*)RBTREE_NULL)
		return NULL;
	return n;
}

/* iterator over ixfr data. find last element, eg. newest zone version
 * change. */
static struct ixfr_data* ixfr_data_last(struct zone_ixfr* ixfr)
{
	struct ixfr_data* n;
	if(!ixfr || !ixfr->data || ixfr->data->count==0)
		return NULL;
	n = (struct ixfr_data*)rbtree_search(ixfr->data, &ixfr->newest_serial);
	if(!n || n == (struct ixfr_data*)RBTREE_NULL)
		return NULL;
	return n;
}

/* iterator over ixfr data. fetch next item. If loop or nothing, NULL */
static struct ixfr_data* ixfr_data_next(struct zone_ixfr* ixfr,
	struct ixfr_data* cur)
{
	struct ixfr_data* n;
	if(!cur || cur == (struct ixfr_data*)RBTREE_NULL)
		return NULL;
	if(cur->oldserial == ixfr->newest_serial)
		return NULL; /* that was the last element */
	n = (struct ixfr_data*)rbtree_next(&cur->node);
	if(n && n != (struct ixfr_data*)RBTREE_NULL &&
		cur->newserial == n->oldserial) {
		/* the next rbtree item is the next ixfr data item */
		return n;
	}
	/* If the next item is last of tree, and we have to loop around,
	 * the search performs the lookup for the next item we need.
	 * If the next item exists, but also is not connected, the search
	 * finds the correct connected ixfr in the sorted tree. */
	/* try searching for the correct ixfr data item */
	n = (struct ixfr_data*)rbtree_search(ixfr->data, &cur->newserial);
	if(!n || n == (struct ixfr_data*)RBTREE_NULL)
		return NULL;
	return n;
}

/* iterator over ixfr data. fetch the previous item. If loop or nothing NULL.*/
static struct ixfr_data* ixfr_data_prev(struct zone_ixfr* ixfr,
	struct ixfr_data* cur, size_t* prevcount)
{
	struct ixfr_data* prev;
	if(!cur || cur == (struct ixfr_data*)RBTREE_NULL)
		return NULL;
	if(cur->oldserial == ixfr->oldest_serial)
		return NULL; /* this was the first element */
	prev = (struct ixfr_data*)rbtree_previous(&cur->node);
	if(!prev || prev == (struct ixfr_data*)RBTREE_NULL) {
		/* We hit the first element in the tree, go again
		 * at the last one. Wrap around. */
		prev = (struct ixfr_data*)rbtree_last(ixfr->data);
	}
	while(prev && prev != (struct ixfr_data*)RBTREE_NULL) {
		if(prev->newserial == cur->oldserial) {
			/* This is the correct matching previous ixfr data */
			/* Increase the prevcounter every time the routine
			 * returns an item, and if that becomes too large, we
			 * are in a loop. in that case, stop. */
			if(prevcount) {
				(*prevcount)++;
				if(*prevcount > ixfr->data->count + 12) {
					/* Larger than the max number of items
					 * plus a small margin. The longest
					 * chain is all the ixfr elements in
					 * the tree. It loops. */
					return NULL;
				}
			}
			return prev;
		}
		prev = (struct ixfr_data*)rbtree_previous(&prev->node);
		if(!prev || prev == (struct ixfr_data*)RBTREE_NULL) {
			/* We hit the first element in the tree, go again
			 * at the last one. Wrap around. */
			prev = (struct ixfr_data*)rbtree_last(ixfr->data);
		}
	}
	/* no elements in list */
	return NULL;
}

/* connect IXFRs, return true if connected, false if not. Return last serial */
static int connect_ixfrs(struct zone_ixfr* ixfr, struct ixfr_data* data,
	uint32_t* end_serial)
{
	struct ixfr_data* p = data;
	while(p != NULL) {
		struct ixfr_data* next = ixfr_data_next(ixfr, p);
		if(next) {
			if(p->newserial != next->oldserial) {
				/* These ixfrs are not connected,
				 * during IXFR processing that could already
				 * have been deleted, but we check here
				 * in any case */
				return 0;
			}
		} else {
			/* the chain of IXFRs ends in this serial number */
			*end_serial = p->newserial;
		}
		p = next;
	}
	return 1;
}

/* Count length of next record in data */
static size_t count_rr_length(const uint8_t* data, size_t data_len,
	size_t current)
{
	uint8_t label_size;
	uint16_t rdlen;
	size_t i = current;
	if(current >= data_len)
		return 0;
	/* pass the owner dname */
	while(1) {
		if(i+1 > data_len)
			return 0;
		label_size = data[i++];
		if(label_size == 0) {
			break;
		} else if((label_size &0xc0) != 0) {
			return 0; /* uncompressed dnames in IXFR store */
		} else if(i+label_size > data_len) {
			return 0;
		} else {
			i += label_size;
		}
	}
	/* after dname, we pass type, class, ttl, rdatalen */
	if(i+10 > data_len)
		return 0;
	i += 8;
	rdlen = read_uint16(data+i);
	i += 2;
	/* pass over the rdata */
	if(i+((size_t)rdlen) > data_len)
		return 0;
	i += ((size_t)rdlen);
	return i-current;
}

/* Copy RRs into packet until packet full, return number RRs added */
static uint16_t ixfr_copy_rrs_into_packet(struct query* query,
	struct pktcompression* pcomp)
{
	uint16_t total_added = 0;

	/* Copy RRs into the packet until the answer is full,
	 * when an RR does not fit, we return and add no more. */

	/* Add first SOA */
	if(query->ixfr_count_newsoa < query->ixfr_end_data->newsoa_len) {
		/* the new SOA is added from the end_data segment, it is
		 * the final SOA of the result of the IXFR */
		if(ixfr_write_rr_pkt(query, query->packet, pcomp,
			query->ixfr_end_data->newsoa,
			query->ixfr_end_data->newsoa_len, total_added)) {
			query->ixfr_count_newsoa = query->ixfr_end_data->newsoa_len;
			total_added++;
			query->ixfr_pos_of_newsoa = buffer_position(query->packet);
		} else {
			/* cannot add another RR, so return */
			return total_added;
		}
	}

	/* Add second SOA */
	if(query->ixfr_count_oldsoa < query->ixfr_data->oldsoa_len) {
		if(ixfr_write_rr_pkt(query, query->packet, pcomp,
			query->ixfr_data->oldsoa,
			query->ixfr_data->oldsoa_len, total_added)) {
			query->ixfr_count_oldsoa = query->ixfr_data->oldsoa_len;
			total_added++;
		} else {
			/* cannot add another RR, so return */
			return total_added;
		}
	}

	/* Add del data, with deleted RRs and a SOA */
	while(query->ixfr_count_del < query->ixfr_data->del_len) {
		size_t rrlen = count_rr_length(query->ixfr_data->del,
			query->ixfr_data->del_len, query->ixfr_count_del);
		if(rrlen && ixfr_write_rr_pkt(query, query->packet, pcomp,
			query->ixfr_data->del + query->ixfr_count_del,
			rrlen, total_added)) {
			query->ixfr_count_del += rrlen;
			total_added++;
		} else {
			/* the next record does not fit in the remaining
			 * space of the packet */
			return total_added;
		}
	}

	/* Add add data, with added RRs and a SOA */
	while(query->ixfr_count_add < query->ixfr_data->add_len) {
		size_t rrlen = count_rr_length(query->ixfr_data->add,
			query->ixfr_data->add_len, query->ixfr_count_add);
		if(rrlen && ixfr_write_rr_pkt(query, query->packet, pcomp,
			query->ixfr_data->add + query->ixfr_count_add,
			rrlen, total_added)) {
			query->ixfr_count_add += rrlen;
			total_added++;
		} else {
			/* the next record does not fit in the remaining
			 * space of the packet */
			return total_added;
		}
	}
	return total_added;
}

query_state_type query_ixfr(struct nsd *nsd, struct query *query)
{
	uint16_t total_added = 0;
	struct pktcompression pcomp;

	if (query->ixfr_is_done)
		return QUERY_PROCESSED;

	pktcompression_init(&pcomp);
	if (query->maxlen > IXFR_MAX_MESSAGE_LEN)
		query->maxlen = IXFR_MAX_MESSAGE_LEN;

	assert(!query_overflow(query));
	/* only keep running values for most packets */
	query->tsig_prepare_it = 0;
	query->tsig_update_it = 1;
	if(query->tsig_sign_it) {
		/* prepare for next updates */
		query->tsig_prepare_it = 1;
		query->tsig_sign_it = 0;
	}

	if (query->ixfr_data == NULL) {
		/* This is the first packet, process the query further */
		uint32_t qserial = 0, current_serial = 0, end_serial = 0;
		struct zone* zone;
		struct ixfr_data* ixfr_data;
		size_t oldpos;

		STATUP(nsd, rixfr);
		/* parse the serial number from the IXFR request */
		oldpos = QHEADERSZ;
		if(!parse_qserial(query->packet, &qserial, &oldpos)) {
			NSCOUNT_SET(query->packet, 0);
			ARCOUNT_SET(query->packet, 0);
			buffer_set_position(query->packet, oldpos);
			RCODE_SET(query->packet, RCODE_FORMAT);
			return QUERY_PROCESSED;
		}
		NSCOUNT_SET(query->packet, 0);
		ARCOUNT_SET(query->packet, 0);
		buffer_set_position(query->packet, oldpos);
		DEBUG(DEBUG_XFRD,1, (LOG_INFO, "ixfr query routine, %s IXFR=%u",
			dname_to_string(query->qname, NULL), (unsigned)qserial));

		/* do we have an IXFR with this serial number? If not, serve AXFR */
		zone = namedb_find_zone(nsd->db, query->qname);
		if(!zone) {
			/* no zone is present */
			RCODE_SET(query->packet, RCODE_NOTAUTH);
			return QUERY_PROCESSED;
		}
		ZTATUP(nsd, zone, rixfr);

		/* if the query is for same or newer serial than our current
		 * serial, then serve a single SOA with our current serial */
		current_serial = zone_get_current_serial(zone);
		if(compare_serial(qserial, current_serial) >= 0) {
			if(!zone->soa_rrset || zone->soa_rrset->rr_count != 1){
				RCODE_SET(query->packet, RCODE_SERVFAIL);
				return QUERY_PROCESSED;
			}
			query_add_compression_domain(query, zone->apex,
				QHEADERSZ);
			if(packet_encode_rr(query, zone->apex,
				zone->soa_rrset->rrs[0],
				zone->soa_rrset->rrs[0]->ttl)) {
				ANCOUNT_SET(query->packet, 1);
			} else {
				RCODE_SET(query->packet, RCODE_SERVFAIL);
			}
			AA_SET(query->packet);
			query_clear_compression_tables(query);
			if(query->tsig.status == TSIG_OK)
				query->tsig_sign_it = 1;
			return QUERY_PROCESSED;
		}

		if(!zone->ixfr) {
			/* we have no ixfr information for the zone, make an AXFR */
			if(query->tsig_prepare_it)
				query->tsig_sign_it = 1;
			VERBOSITY(2, (LOG_INFO, "ixfr fallback to axfr, no ixfr info for zone: %s",
				dname_to_string(query->qname, NULL)));
			return query_axfr(nsd, query, 0);
		}
		ixfr_data = zone_ixfr_find_serial(zone->ixfr, qserial);
		if(!ixfr_data) {
			/* the specific version is not available, make an AXFR */
			if(query->tsig_prepare_it)
				query->tsig_sign_it = 1;
			VERBOSITY(2, (LOG_INFO, "ixfr fallback to axfr, no history for serial for zone: %s",
				dname_to_string(query->qname, NULL)));
			return query_axfr(nsd, query, 0);
		}
		/* see if the IXFRs connect to the next IXFR, and if it ends
		 * at the current served zone, if not, AXFR */
		if(!connect_ixfrs(zone->ixfr, ixfr_data, &end_serial) ||
			end_serial != current_serial) {
			if(query->tsig_prepare_it)
				query->tsig_sign_it = 1;
			VERBOSITY(2, (LOG_INFO, "ixfr fallback to axfr, incomplete history from this serial for zone: %s",
				dname_to_string(query->qname, NULL)));
			return query_axfr(nsd, query, 0);
		}

		query->zone = zone;
		query->ixfr_data = ixfr_data;
		query->ixfr_is_done = 0;
		/* set up to copy the last version's SOA as first SOA */
		query->ixfr_end_data = ixfr_data_last(zone->ixfr);
		query->ixfr_count_newsoa = 0;
		query->ixfr_count_oldsoa = 0;
		query->ixfr_count_del = 0;
		query->ixfr_count_add = 0;
		query->ixfr_pos_of_newsoa = 0;
		/* the query name can be compressed to */
		pktcompression_insert_with_labels(&pcomp,
			buffer_at(query->packet, QHEADERSZ),
			query->qname->name_size, QHEADERSZ);
		if(query->tsig.status == TSIG_OK) {
			query->tsig_sign_it = 1; /* sign first packet in stream */
		}
	} else {
		/*
		 * Query name need not be repeated after the
		 * first response packet.
		 */
		buffer_set_limit(query->packet, QHEADERSZ);
		QDCOUNT_SET(query->packet, 0);
		query_prepare_response(query);
	}

	total_added = ixfr_copy_rrs_into_packet(query, &pcomp);

	while(query->ixfr_count_add >= query->ixfr_data->add_len) {
		struct ixfr_data* next = ixfr_data_next(query->zone->ixfr,
			query->ixfr_data);
		/* finished the ixfr_data */
		if(next) {
			/* move to the next IXFR */
			query->ixfr_data = next;
			/* we need to skip the SOA records, set len to done*/
			/* the newsoa count is already done, at end_data len */
			query->ixfr_count_oldsoa = next->oldsoa_len;
			/* and then set up to copy the del and add sections */
			query->ixfr_count_del = 0;
			query->ixfr_count_add = 0;
			total_added += ixfr_copy_rrs_into_packet(query, &pcomp);
		} else {
			/* we finished the IXFR */
			/* sign the last packet */
			query->tsig_sign_it = 1;
			query->ixfr_is_done = 1;
			break;
		}
	}

	/* return the answer */
	AA_SET(query->packet);
	ANCOUNT_SET(query->packet, total_added);
	NSCOUNT_SET(query->packet, 0);
	ARCOUNT_SET(query->packet, 0);

	if(!query->tcp && !query->ixfr_is_done) {
		TC_SET(query->packet);
		if(query->ixfr_pos_of_newsoa) {
			/* if we recorded the newsoa in the result, snip off
			 * the rest of the response, the RFC1995 response for
			 * when it does not fit is only the latest SOA */
			buffer_set_position(query->packet, query->ixfr_pos_of_newsoa);
			ANCOUNT_SET(query->packet, 1);
		}
		query->ixfr_is_done = 1;
	}

	/* check if it needs tsig signatures */
	if(query->tsig.status == TSIG_OK) {
#if IXFR_TSIG_SIGN_EVERY_NTH > 0
		if(query->tsig.updates_since_last_prepare >= IXFR_TSIG_SIGN_EVERY_NTH) {
#endif
			query->tsig_sign_it = 1;
#if IXFR_TSIG_SIGN_EVERY_NTH > 0
		}
#endif
	}
	pktcompression_freeup(&pcomp);
	return QUERY_IN_IXFR;
}

/* free ixfr_data structure */
static void ixfr_data_free(struct ixfr_data* data)
{
	if(!data)
		return;
	free(data->newsoa);
	free(data->oldsoa);
	free(data->del);
	free(data->add);
	free(data->log_str);
	free(data);
}

size_t ixfr_data_size(struct ixfr_data* data)
{
	return sizeof(struct ixfr_data) + data->newsoa_len + data->oldsoa_len
		+ data->del_len + data->add_len;
}

struct ixfr_store* ixfr_store_start(struct zone* zone,
	struct ixfr_store* ixfr_store_mem)
{
	struct ixfr_store* ixfr_store = ixfr_store_mem;
	memset(ixfr_store, 0, sizeof(*ixfr_store));
	ixfr_store->zone = zone;
	ixfr_store->data = xalloc_zero(sizeof(*ixfr_store->data));
	return ixfr_store;
}

void ixfr_store_cancel(struct ixfr_store* ixfr_store)
{
	ixfr_store->cancelled = 1;
	ixfr_data_free(ixfr_store->data);
	ixfr_store->data = NULL;
}

void ixfr_store_free(struct ixfr_store* ixfr_store)
{
	if(!ixfr_store)
		return;
	ixfr_data_free(ixfr_store->data);
}

/* make space in record data for the new size, grows the allocation */
static void ixfr_rrs_make_space(uint8_t** rrs, size_t* len, size_t* capacity,
	size_t added)
{
	size_t newsize = 0;
	if(*rrs == NULL) {
		newsize = IXFR_STORE_INITIAL_SIZE;
	} else {
		if(*len + added <= *capacity)
			return; /* already enough space */
		newsize = (*capacity)*2;
	}
	if(*len + added > newsize)
		newsize = *len + added;
	if(*rrs == NULL) {
		*rrs = xalloc(newsize);
	} else {
		*rrs = xrealloc(*rrs, newsize);
	}
	*capacity = newsize;
}

/* put new SOA record after delrrs and addrrs */
static void ixfr_put_newsoa(struct ixfr_store* ixfr_store, uint8_t** rrs,
	size_t* len, size_t* capacity)
{
	uint8_t* soa;
	size_t soa_len;
	if(!ixfr_store->data)
		return; /* data should be nonNULL, we are not cancelled */
	soa = ixfr_store->data->newsoa;
	soa_len= ixfr_store->data->newsoa_len;
	ixfr_rrs_make_space(rrs, len, capacity, soa_len);
	if(!*rrs || *len + soa_len > *capacity) {
		log_msg(LOG_ERR, "ixfr_store addrr: cannot allocate space");
		ixfr_store_cancel(ixfr_store);
		return;
	}
	memmove(*rrs + *len, soa, soa_len);
	*len += soa_len;
}

/* trim unused storage from the rrs data */
static void ixfr_trim_capacity(uint8_t** rrs, size_t* len, size_t* capacity)
{
	if(*rrs == NULL)
		return;
	if(*capacity == *len)
		return;
	*rrs = xrealloc(*rrs, *len);
	*capacity = *len;
}

void ixfr_store_finish_data(struct ixfr_store* ixfr_store)
{
	if(ixfr_store->data_trimmed)
		return;
	ixfr_store->data_trimmed = 1;

	/* put new serial SOA record after delrrs and addrrs */
	ixfr_put_newsoa(ixfr_store, &ixfr_store->data->del,
		&ixfr_store->data->del_len, &ixfr_store->del_capacity);
	ixfr_put_newsoa(ixfr_store, &ixfr_store->data->add,
		&ixfr_store->data->add_len, &ixfr_store->add_capacity);

	/* trim the data in the store, the overhead from capacity is
	 * removed */
	if(!ixfr_store->data)
		return; /* data should be nonNULL, we are not cancelled */
	ixfr_trim_capacity(&ixfr_store->data->del,
		&ixfr_store->data->del_len, &ixfr_store->del_capacity);
	ixfr_trim_capacity(&ixfr_store->data->add,
		&ixfr_store->data->add_len, &ixfr_store->add_capacity);
}

void ixfr_store_finish(struct ixfr_store* ixfr_store, struct nsd* nsd,
	char* log_buf)
{
	if(ixfr_store->cancelled) {
		ixfr_store_free(ixfr_store);
		return;
	}

	ixfr_store_finish_data(ixfr_store);

	if(ixfr_store->cancelled) {
		ixfr_store_free(ixfr_store);
		return;
	}

	if(log_buf && !ixfr_store->data->log_str)
		ixfr_store->data->log_str = strdup(log_buf);

	/* store the data in the zone */
	if(!ixfr_store->zone->ixfr)
		ixfr_store->zone->ixfr = zone_ixfr_create(nsd);
	zone_ixfr_make_space(ixfr_store->zone->ixfr, ixfr_store->zone,
		ixfr_store->data, ixfr_store);
	if(ixfr_store->cancelled) {
		ixfr_store_free(ixfr_store);
		return;
	}
	zone_ixfr_add(ixfr_store->zone->ixfr, ixfr_store->data, 1);
	ixfr_store->data = NULL;

	/* free structure */
	ixfr_store_free(ixfr_store);
}

/* read SOA rdata section for SOA storage */
static int read_soa_rdata_fields(struct buffer* packet, uint8_t* primns,
	int* primns_len, uint8_t* email, int* email_len,
	uint32_t* serial, uint32_t* refresh, uint32_t* retry,
	uint32_t* expire, uint32_t* minimum, size_t* sz)
{
	if(!(*primns_len = dname_make_wire_from_packet(primns, packet, 1))) {
		log_msg(LOG_ERR, "ixfr_store: cannot parse soa nsname in packet");
		return 0;
	}
	*sz += *primns_len;
	if(!(*email_len = dname_make_wire_from_packet(email, packet, 1))) {
		log_msg(LOG_ERR, "ixfr_store: cannot parse soa maintname in packet");
		return 0;
	}
	*sz += *email_len;
	*serial = buffer_read_u32(packet);
	*sz += 4;
	*refresh = buffer_read_u32(packet);
	*sz += 4;
	*retry = buffer_read_u32(packet);
	*sz += 4;
	*expire = buffer_read_u32(packet);
	*sz += 4;
	*minimum = buffer_read_u32(packet);
	*sz += 4;
	return 1;
}

/* store SOA record data in memory buffer */
static void store_soa(uint8_t* soa, struct zone* zone, uint32_t ttl,
	uint16_t rdlen_uncompressed, uint8_t* primns, int primns_len,
	uint8_t* email, int email_len, uint32_t serial, uint32_t refresh,
	uint32_t retry, uint32_t expire, uint32_t minimum)
{
	uint8_t* sp = soa;
	memmove(sp, dname_name(domain_dname(zone->apex)),
		domain_dname(zone->apex)->name_size);
	sp += domain_dname(zone->apex)->name_size;
	write_uint16(sp, TYPE_SOA);
	sp += 2;
	write_uint16(sp, CLASS_IN);
	sp += 2;
	write_uint32(sp, ttl);
	sp += 4;
	write_uint16(sp, rdlen_uncompressed);
	sp += 2;
	memmove(sp, primns, primns_len);
	sp += primns_len;
	memmove(sp, email, email_len);
	sp += email_len;
	write_uint32(sp, serial);
	sp += 4;
	write_uint32(sp, refresh);
	sp += 4;
	write_uint32(sp, retry);
	sp += 4;
	write_uint32(sp, expire);
	sp += 4;
	write_uint32(sp, minimum);
}

void ixfr_store_add_newsoa(struct ixfr_store* ixfr_store, uint32_t ttl,
	struct buffer* packet, size_t rrlen)
{
	size_t oldpos, sz = 0;
	uint32_t serial, refresh, retry, expire, minimum;
	uint16_t rdlen_uncompressed;
	int primns_len = 0, email_len = 0;
	uint8_t primns[MAXDOMAINLEN + 1], email[MAXDOMAINLEN + 1];

	if(ixfr_store->cancelled)
		return;
	if(ixfr_store->data->newsoa) {
		free(ixfr_store->data->newsoa);
		ixfr_store->data->newsoa = NULL;
		ixfr_store->data->newsoa_len = 0;
	}
	oldpos = buffer_position(packet);

	/* calculate the length */
	sz = domain_dname(ixfr_store->zone->apex)->name_size;
	sz += 2 /* type */ + 2 /* class */ + 4 /* ttl */ + 2 /* rdlen */;
	if(!buffer_available(packet, rrlen)) {
		/* not possible already parsed, but fail nicely anyway */
		log_msg(LOG_ERR, "ixfr_store: not enough rdata space in packet");
		ixfr_store_cancel(ixfr_store);
		buffer_set_position(packet, oldpos);
		return;
	}
	if(!read_soa_rdata_fields(packet, primns, &primns_len, email, &email_len,
		&serial, &refresh, &retry, &expire, &minimum, &sz)) {
		log_msg(LOG_ERR, "ixfr_store newsoa: cannot parse packet");
		ixfr_store_cancel(ixfr_store);
		buffer_set_position(packet, oldpos);
		return;
	}
	rdlen_uncompressed = primns_len + email_len + 4 + 4 + 4 + 4 + 4;

	ixfr_store->data->newserial = serial;

	/* store the soa record */
	ixfr_store->data->newsoa = xalloc(sz);
	ixfr_store->data->newsoa_len = sz;
	store_soa(ixfr_store->data->newsoa, ixfr_store->zone, ttl,
		rdlen_uncompressed, primns, primns_len, email, email_len,
		serial, refresh, retry, expire, minimum);

	buffer_set_position(packet, oldpos);
}

void ixfr_store_add_oldsoa(struct ixfr_store* ixfr_store, uint32_t ttl,
	struct buffer* packet, size_t rrlen)
{
	size_t oldpos, sz = 0;
	uint32_t serial, refresh, retry, expire, minimum;
	uint16_t rdlen_uncompressed;
	int primns_len = 0, email_len = 0;
	uint8_t primns[MAXDOMAINLEN + 1], email[MAXDOMAINLEN + 1];

	if(ixfr_store->cancelled)
		return;
	if(ixfr_store->data->oldsoa) {
		free(ixfr_store->data->oldsoa);
		ixfr_store->data->oldsoa = NULL;
		ixfr_store->data->oldsoa_len = 0;
	}
	/* we have the old SOA and thus we are sure it is an IXFR, make space*/
	zone_ixfr_make_space(ixfr_store->zone->ixfr, ixfr_store->zone,
		ixfr_store->data, ixfr_store);
	if(ixfr_store->cancelled)
		return;
	oldpos = buffer_position(packet);

	/* calculate the length */
	sz = domain_dname(ixfr_store->zone->apex)->name_size;
	sz += 2 /*type*/ + 2 /*class*/ + 4 /*ttl*/ + 2 /*rdlen*/;
	if(!buffer_available(packet, rrlen)) {
		/* not possible already parsed, but fail nicely anyway */
		log_msg(LOG_ERR, "ixfr_store oldsoa: not enough rdata space in packet");
		ixfr_store_cancel(ixfr_store);
		buffer_set_position(packet, oldpos);
		return;
	}
	if(!read_soa_rdata_fields(packet, primns, &primns_len, email, &email_len,
		&serial, &refresh, &retry, &expire, &minimum, &sz)) {
		log_msg(LOG_ERR, "ixfr_store oldsoa: cannot parse packet");
		ixfr_store_cancel(ixfr_store);
		buffer_set_position(packet, oldpos);
		return;
	}
	rdlen_uncompressed = primns_len + email_len + 4 + 4 + 4 + 4 + 4;

	ixfr_store->data->oldserial = serial;

	/* store the soa record */
	ixfr_store->data->oldsoa = xalloc(sz);
	ixfr_store->data->oldsoa_len = sz;
	store_soa(ixfr_store->data->oldsoa, ixfr_store->zone, ttl,
		rdlen_uncompressed, primns, primns_len, email, email_len,
		serial, refresh, retry, expire, minimum);

	buffer_set_position(packet, oldpos);
}

/* store RR in data segment.
 * return -1 on fail of wireformat, 0 on allocate failure, or 1 success. */
static int ixfr_putrr(const rr_type* rr, uint8_t** rrs, size_t* rrs_len,
	size_t* rrs_capacity)
{
	int32_t rdlen_uncompressed;
	size_t sz;
	uint8_t* sp;
	const dname_type* dname;

	rdlen_uncompressed = rr_calculate_uncompressed_rdata_length(rr);
	if (rdlen_uncompressed < 0)
		return -1; /* malformed */

	dname = domain_dname(rr->owner);
	sz = dname->name_size + 2 /*type*/ + 2 /*class*/ + 4 /*ttl*/ +
		2 /*rdlen*/ + rdlen_uncompressed;

	/* store RR in IXFR data */
	ixfr_rrs_make_space(rrs, rrs_len, rrs_capacity, sz);
	if(!*rrs || *rrs_len + sz > *rrs_capacity) {
		return 0;
	}
	/* copy data into add */
	sp = *rrs + *rrs_len;
	*rrs_len += sz;
	memmove(sp, dname_name(dname), dname->name_size);
	sp += dname->name_size;
	write_uint16(sp, rr->type);
	write_uint16(sp + 2, rr->klass);
	write_uint32(sp + 4, rr->ttl);
	write_uint16(sp + 8, rdlen_uncompressed);
	rr_write_uncompressed_rdata(rr, sp+10, rdlen_uncompressed);
	return 1;
}

void ixfr_store_putrr(struct ixfr_store* ixfr_store, const rr_type* rr,
	uint8_t** rrs, size_t* rrs_len, size_t* rrs_capacity)
{
	int code;

	if(ixfr_store->cancelled)
		return;

	/* The SOA data is stored with separate calls. And then appended
	 * during the finish operation. We do not have to store it here
	 * when called from difffile's IXFR processing with type SOA. */
	if(rr->type == TYPE_SOA)
		return;
	/* make space for these RRs we have now; basically once we
	 * grow beyond the current allowed amount an older IXFR is deleted. */
	zone_ixfr_make_space(ixfr_store->zone->ixfr, ixfr_store->zone,
		ixfr_store->data, ixfr_store);
	if(ixfr_store->cancelled)
		return;

	/* store rdata */
	code = ixfr_putrr(rr, rrs, rrs_len, rrs_capacity);

	if (code <= 0) {
		if (code == -1)
			log_msg(LOG_ERR, "ixfr_store addrr: cannot parse rdata format");
		else
			log_msg(LOG_ERR, "ixfr_store addrr: cannot allocate space");
		ixfr_store_cancel(ixfr_store);
		return;
	}
}

void ixfr_store_delrr(struct ixfr_store* ixfr_store, const rr_type* rr)
{
	if(ixfr_store->cancelled)
		return;
	ixfr_store_putrr(ixfr_store, rr, &ixfr_store->data->del,
		&ixfr_store->data->del_len, &ixfr_store->del_capacity);
}

void ixfr_store_addrr(struct ixfr_store* ixfr_store, const rr_type* rr)
{
	if(ixfr_store->cancelled)
		return;
	ixfr_store_putrr(ixfr_store, rr, &ixfr_store->data->add,
		&ixfr_store->data->add_len, &ixfr_store->add_capacity);
}

int ixfr_store_addrr_rdatas(struct ixfr_store* ixfr_store, const rr_type *rr)
{
	if(ixfr_store->cancelled)
		return 1;
	if(rr->type == TYPE_SOA)
		return 1;
	if(ixfr_putrr(rr, &ixfr_store->data->add, &ixfr_store->data->add_len,
		&ixfr_store->add_capacity) <= 0)
		return 0;
	return 1;
}

int ixfr_store_add_newsoa_rdatas(struct ixfr_store* ixfr_store,
	const rr_type* rr)
{
	size_t capacity = 0;
	if(ixfr_store->cancelled)
		return 1;
	if(!retrieve_soa_rdata_serial(rr, &ixfr_store->data->newserial))
		return 0;
	if(ixfr_putrr(rr, &ixfr_store->data->newsoa,
		&ixfr_store->data->newsoa_len, &ixfr_store->add_capacity) <= 0)
		return 0;
	ixfr_trim_capacity(&ixfr_store->data->newsoa,
		&ixfr_store->data->newsoa_len, &capacity);
	return 1;
}

/* store rr uncompressed */
int ixfr_storerr_uncompressed(uint8_t* dname, size_t dname_len, uint16_t type,
	uint16_t klass, uint32_t ttl, uint8_t* rdata, size_t rdata_len,
	uint8_t** rrs, size_t* rrs_len, size_t* rrs_capacity)
{
	size_t sz;
	uint8_t* sp;

	/* find rdatalen */
	sz = dname_len + 2 /*type*/ + 2 /*class*/ + 4 /*ttl*/ +
		2 /*rdlen*/ + rdata_len;

	/* store RR in IXFR data */
	ixfr_rrs_make_space(rrs, rrs_len, rrs_capacity, sz);
	if(!*rrs || *rrs_len + sz > *rrs_capacity) {
		return 0;
	}
	/* copy data into add */
	sp = *rrs + *rrs_len;
	*rrs_len += sz;
	memmove(sp, dname, dname_len);
	sp += dname_len;
	write_uint16(sp, type);
	sp += 2;
	write_uint16(sp, klass);
	sp += 2;
	write_uint32(sp, ttl);
	sp += 4;
	write_uint16(sp, rdata_len);
	sp += 2;
	memmove(sp, rdata, rdata_len);
	return 1;
}

int ixfr_store_delrr_uncompressed(struct ixfr_store* ixfr_store,
	uint8_t* dname, size_t dname_len, uint16_t type, uint16_t klass,
	uint32_t ttl, uint8_t* rdata, size_t rdata_len)
{
	if(ixfr_store->cancelled)
		return 1;
	if(type == TYPE_SOA)
		return 1;
	return ixfr_storerr_uncompressed(dname, dname_len, type, klass,
		ttl, rdata, rdata_len, &ixfr_store->data->del,
		&ixfr_store->data->del_len, &ixfr_store->del_capacity);
}

static size_t skip_dname(uint8_t* rdata, size_t rdata_len)
{
	for (size_t index=0; index < rdata_len; ) {
		uint8_t label_size = rdata[index];
		if (label_size == 0) {
			return index + 1;
		} else if ((label_size & 0xc0) != 0) {
			return (index + 1 < rdata_len) ? index + 2 : 0;
		} else {
			/* loop breaks if index exceeds rdata_len */
			index += label_size + 1;
		}
	}

	return 0;
}

int ixfr_store_oldsoa_uncompressed(struct ixfr_store* ixfr_store,
	uint8_t* dname, size_t dname_len, uint16_t type, uint16_t klass,
	uint32_t ttl, uint8_t* rdata, size_t rdata_len)
{
	uint32_t serial;
	size_t capacity = 0, index, count;
	if(ixfr_store->cancelled)
		return 1;
	if(!ixfr_storerr_uncompressed(dname, dname_len, type, klass,
		ttl, rdata, rdata_len, &ixfr_store->data->oldsoa,
		&ixfr_store->data->oldsoa_len, &capacity))
		return 0;

	if (!(count = skip_dname(rdata, rdata_len)))
		return 0;
	index = count;
	if (!(count = skip_dname(rdata+index, rdata_len-index)))
		return 0;
	index += count;
	if (rdata_len - index < 4)
		return 0;
	memcpy(&serial, rdata+index, sizeof(serial));
	ixfr_store->data->oldserial = ntohl(serial);

	ixfr_trim_capacity(&ixfr_store->data->oldsoa,
		&ixfr_store->data->oldsoa_len, &capacity);
	return 1;
}

int zone_is_ixfr_enabled(struct zone* zone)
{
	return zone->opts->pattern->store_ixfr;
}

/* compare ixfr elements */
static int ixfrcompare(const void* x, const void* y)
{
	uint32_t* serial_x = (uint32_t*)x;
	uint32_t* serial_y = (uint32_t*)y;
	if(*serial_x < *serial_y)
		return -1;
	if(*serial_x > *serial_y)
		return 1;
	return 0;
}

struct zone_ixfr* zone_ixfr_create(struct nsd* nsd)
{
	struct zone_ixfr* ixfr = xalloc_zero(sizeof(struct zone_ixfr));
	ixfr->data = rbtree_create(nsd->region, &ixfrcompare);
	return ixfr;
}

/* traverse tree postorder */
static void ixfr_tree_del(struct rbnode* node)
{
	if(node == NULL || node == RBTREE_NULL)
		return;
	ixfr_tree_del(node->left);
	ixfr_tree_del(node->right);
	ixfr_data_free((struct ixfr_data*)node);
}

/* clear the ixfr data elements */
static void zone_ixfr_clear(struct zone_ixfr* ixfr)
{
	if(!ixfr)
		return;
	if(ixfr->data) {
		ixfr_tree_del(ixfr->data->root);
		ixfr->data->root = RBTREE_NULL;
		ixfr->data->count = 0;
	}
	ixfr->total_size = 0;
	ixfr->oldest_serial = 0;
	ixfr->newest_serial = 0;
}

void zone_ixfr_free(struct zone_ixfr* ixfr)
{
	if(!ixfr)
		return;
	if(ixfr->data) {
		ixfr_tree_del(ixfr->data->root);
		ixfr->data = NULL;
	}
	free(ixfr);
}

void ixfr_store_delixfrs(struct zone* zone)
{
	if(!zone)
		return;
	zone_ixfr_clear(zone->ixfr);
}

/* remove the oldest data entry from the ixfr versions */
static void zone_ixfr_remove_oldest(struct zone_ixfr* ixfr)
{
	if(ixfr->data->count > 0) {
		struct ixfr_data* oldest = ixfr_data_first(ixfr);
		if(ixfr->oldest_serial == oldest->oldserial) {
			if(ixfr->data->count > 1) {
				struct ixfr_data* next = ixfr_data_next(ixfr, oldest);
				assert(next);
				if(next)
					ixfr->oldest_serial = next->oldserial;
				else 	ixfr->oldest_serial = oldest->newserial;
			} else {
				ixfr->oldest_serial = 0;
			}
		}
		if(ixfr->newest_serial == oldest->oldserial) {
			ixfr->newest_serial = 0;
		}
		zone_ixfr_remove(ixfr, oldest);
	}
}

void zone_ixfr_make_space(struct zone_ixfr* ixfr, struct zone* zone,
	struct ixfr_data* data, struct ixfr_store* ixfr_store)
{
	size_t addsize;
	if(!ixfr || !data)
		return;
	if(zone->opts->pattern->ixfr_number == 0) {
		ixfr_store_cancel(ixfr_store);
		return;
	}

	/* Check the number of IXFRs allowed for this zone, if too many,
	 * shorten the number to make space for another one */
	while(ixfr->data->count >= zone->opts->pattern->ixfr_number) {
		zone_ixfr_remove_oldest(ixfr);
	}

	if(zone->opts->pattern->ixfr_size == 0) {
		/* no size limits imposed */
		return;
	}

	/* Check the size of the current added data element 'data', and
	 * see if that overflows the maximum storage size for IXFRs for
	 * this zone, and if so, delete the oldest IXFR to make space */
	addsize = ixfr_data_size(data);
	while(ixfr->data->count > 0 && ixfr->total_size + addsize >
		zone->opts->pattern->ixfr_size) {
		zone_ixfr_remove_oldest(ixfr);
	}

	/* if deleting the oldest elements does not work, then this
	 * IXFR is too big to store and we cancel it */
	if(ixfr->data->count == 0 && ixfr->total_size + addsize >
		zone->opts->pattern->ixfr_size) {
		ixfr_store_cancel(ixfr_store);
		return;
	}
}

void zone_ixfr_remove(struct zone_ixfr* ixfr, struct ixfr_data* data)
{
	rbtree_delete(ixfr->data, data->node.key);
	ixfr->total_size -= ixfr_data_size(data);
	ixfr_data_free(data);
}

void zone_ixfr_add(struct zone_ixfr* ixfr, struct ixfr_data* data, int isnew)
{
	memset(&data->node, 0, sizeof(data->node));
	if(ixfr->data->count == 0) {
		ixfr->oldest_serial = data->oldserial;
		ixfr->newest_serial = data->oldserial;
	} else if(isnew) {
		/* newest entry is last there is */
		ixfr->newest_serial = data->oldserial;
	} else {
		/* added older entry, before the others */
		ixfr->oldest_serial = data->oldserial;
	}
	data->node.key = &data->oldserial;
	rbtree_insert(ixfr->data, &data->node);
	ixfr->total_size += ixfr_data_size(data);
}

struct ixfr_data* zone_ixfr_find_serial(struct zone_ixfr* ixfr,
	uint32_t qserial)
{
	struct ixfr_data* data;
	if(!ixfr)
		return NULL;
	if(!ixfr->data)
		return NULL;
	data = (struct ixfr_data*)rbtree_search(ixfr->data, &qserial);
	if(data) {
		assert(data->oldserial == qserial);
		return data;
	}
	/* not found */
	return NULL;
}

/* calculate the number of files we want */
static int ixfr_target_number_files(struct zone* zone)
{
	int dest_num_files;
	if(!zone->ixfr || !zone->ixfr->data)
		return 0;
	if(!zone_is_ixfr_enabled(zone))
		return 0;
	/* if we store ixfr, it is the configured number of files */
	dest_num_files = (int)zone->opts->pattern->ixfr_number;
	/* but if the number of available transfers is smaller, store less */
	if(dest_num_files > (int)zone->ixfr->data->count)
		dest_num_files = (int)zone->ixfr->data->count;
	return dest_num_files;
}

/* create ixfrfile name in buffer for file_num. The num is 1 .. number. */
static void make_ixfr_name(char* buf, size_t len, const char* zfile,
	int file_num)
{
	if(file_num == 1)
		snprintf(buf, len, "%s.ixfr", zfile);
	else snprintf(buf, len, "%s.ixfr.%d", zfile, file_num);
}

/* create temp ixfrfile name in buffer for file_num. The num is 1 .. number. */
static void make_ixfr_name_temp(char* buf, size_t len, const char* zfile,
	int file_num, int temp)
{
	if(file_num == 1)
		snprintf(buf, len, "%s.ixfr%s", zfile, (temp?".temp":""));
	else snprintf(buf, len, "%s.ixfr.%d%s", zfile, file_num,
		(temp?".temp":""));
}

/* see if ixfr file exists */
static int ixfr_file_exists_ctmp(const char* zfile, int file_num, int temp)
{
	struct stat statbuf;
	char ixfrfile[1024+24];
	make_ixfr_name_temp(ixfrfile, sizeof(ixfrfile), zfile, file_num, temp);
	memset(&statbuf, 0, sizeof(statbuf));
	if(stat(ixfrfile, &statbuf) < 0) {
		if(errno == ENOENT)
			return 0;
		/* file is not usable */
		return 0;
	}
	return 1;
}

int ixfr_file_exists(const char* zfile, int file_num)
{
	return ixfr_file_exists_ctmp(zfile, file_num, 0);
}

/* see if ixfr file exists */
static int ixfr_file_exists_temp(const char* zfile, int file_num)
{
	return ixfr_file_exists_ctmp(zfile, file_num, 1);
}

/* unlink an ixfr file */
static int ixfr_unlink_it_ctmp(const char* zname, const char* zfile,
	int file_num, int silent_enoent, int temp)
{
	char ixfrfile[1024+24];
	make_ixfr_name_temp(ixfrfile, sizeof(ixfrfile), zfile, file_num, temp);
	VERBOSITY(3, (LOG_INFO, "delete zone %s IXFR data file %s",
		zname, ixfrfile));
	if(unlink(ixfrfile) < 0) {
		if(silent_enoent && errno == ENOENT)
			return 0;
		log_msg(LOG_ERR, "error to delete file %s: %s", ixfrfile,
			strerror(errno));
		return 0;
	}
	return 1;
}

int ixfr_unlink_it(const char* zname, const char* zfile, int file_num,
	int silent_enoent)
{
	return ixfr_unlink_it_ctmp(zname, zfile, file_num, silent_enoent, 0);
}

/* unlink an ixfr file */
static int ixfr_unlink_it_temp(const char* zname, const char* zfile,
	int file_num, int silent_enoent)
{
	return ixfr_unlink_it_ctmp(zname, zfile, file_num, silent_enoent, 1);
}

/* read ixfr file header */
int ixfr_read_file_header(const char* zname, const char* zfile,
	int file_num, uint32_t* oldserial, uint32_t* newserial,
	size_t* data_size, int enoent_is_err)
{
	char ixfrfile[1024+24];
	char buf[1024];
	FILE* in;
	int num_lines = 0, got_old = 0, got_new = 0, got_datasize = 0;
	make_ixfr_name(ixfrfile, sizeof(ixfrfile), zfile, file_num);
	in = fopen(ixfrfile, "r");
	if(!in) {
		if((errno == ENOENT && enoent_is_err) || (errno != ENOENT))
			log_msg(LOG_ERR, "could not open %s: %s", ixfrfile,
				strerror(errno));
		return 0;
	}
	/* read about 10 lines, this is where the header is */
	while(!(got_old && got_new && got_datasize) && num_lines < 10) {
		buf[0]=0;
		buf[sizeof(buf)-1]=0;
		if(!fgets(buf, sizeof(buf), in)) {
			log_msg(LOG_ERR, "could not read %s: %s", ixfrfile,
				strerror(errno));
			fclose(in);
			return 0;
		}
		num_lines++;
		if(buf[0]!=0 && buf[strlen(buf)-1]=='\n')
			buf[strlen(buf)-1]=0;
		if(strncmp(buf, "; zone ", 7) == 0) {
			if(strcmp(buf+7, zname) != 0) {
				log_msg(LOG_ERR, "file has wrong zone, expected zone %s, but found %s in file %s",
					zname, buf+7, ixfrfile);
				fclose(in);
				return 0;
			}
		} else if(strncmp(buf, "; from_serial ", 14) == 0) {
			*oldserial = atoi(buf+14);
			got_old = 1;
		} else if(strncmp(buf, "; to_serial ", 12) == 0) {
			*newserial = atoi(buf+12);
			got_new = 1;
		} else if(strncmp(buf, "; data_size ", 12) == 0) {
			*data_size = (size_t)atoi(buf+12);
			got_datasize = 1;
		}
	}
	fclose(in);
	if(!got_old)
		return 0;
	if(!got_new)
		return 0;
	if(!got_datasize)
		return 0;
	return 1;
}

/* delete rest ixfr files, that are after the current item */
static void ixfr_delete_rest_files(struct zone* zone, struct ixfr_data* from,
	const char* zfile, int temp)
{
	size_t prevcount = 0;
	struct ixfr_data* data = from;
	while(data) {
		if(data->file_num != 0) {
			(void)ixfr_unlink_it_ctmp(zone->opts->name, zfile,
				data->file_num, 0, temp);
			data->file_num = 0;
		}
		data = ixfr_data_prev(zone->ixfr, data, &prevcount);
	}
}

void ixfr_delete_superfluous_files(struct zone* zone, const char* zfile,
	int dest_num_files)
{
	int i = dest_num_files + 1;
	if(!ixfr_file_exists(zfile, i))
		return;
	while(ixfr_unlink_it(zone->opts->name, zfile, i, 1)) {
		i++;
	}
}

int ixfr_rename_it(const char* zname, const char* zfile, int oldnum,
	int oldtemp, int newnum, int newtemp)
{
	char ixfrfile_old[1024+24];
	char ixfrfile_new[1024+24];
	make_ixfr_name_temp(ixfrfile_old, sizeof(ixfrfile_old), zfile, oldnum,
		oldtemp);
	make_ixfr_name_temp(ixfrfile_new, sizeof(ixfrfile_new), zfile, newnum,
		newtemp);
	VERBOSITY(3, (LOG_INFO, "rename zone %s IXFR data file %s to %s",
		zname, ixfrfile_old, ixfrfile_new));
	if(rename(ixfrfile_old, ixfrfile_new) < 0) {
		log_msg(LOG_ERR, "error to rename file %s: %s", ixfrfile_old,
			strerror(errno));
		return 0;
	}
	return 1;
}

/* delete if we have too many items in memory */
static void ixfr_delete_memory_items(struct zone* zone, int dest_num_files)
{
	if(!zone->ixfr || !zone->ixfr->data)
		return;
	if(dest_num_files == (int)zone->ixfr->data->count)
		return;
	if(dest_num_files > (int)zone->ixfr->data->count) {
		/* impossible, dest_num_files should be smaller */
		return;
	}

	/* delete oldest ixfr, until we have dest_num_files entries */
	while(dest_num_files < (int)zone->ixfr->data->count) {
		zone_ixfr_remove_oldest(zone->ixfr);
	}
}

/* rename the ixfr files that need to change name */
static int ixfr_rename_files(struct zone* zone, const char* zfile,
	int dest_num_files)
{
	struct ixfr_data* data, *startspot = NULL;
	size_t prevcount = 0;
	int destnum;
	if(!zone->ixfr || !zone->ixfr->data)
		return 1;

	/* the oldest file is at the largest number */
	data = ixfr_data_first(zone->ixfr);
	destnum = dest_num_files;
	if(!data)
		return 1; /* nothing to do */
	if(data->file_num == destnum)
		return 1; /* nothing to do for rename */

	/* rename the files to temporary files, because otherwise the
	 * items would overwrite each other when the list touches itself.
	 * On fail, the temporary files are removed and we end up with
	 * the newly written data plus the remaining files, in order.
	 * Thus, start the temporary rename at the oldest, then rename
	 * to the final names starting from the newest. */
	while(data && data->file_num != 0) {
		/* if existing file at temporary name, delete that */
		if(ixfr_file_exists_temp(zfile, data->file_num)) {
			(void)ixfr_unlink_it_temp(zone->opts->name, zfile,
				data->file_num, 0);
		}

		/* rename to temporary name */
		if(!ixfr_rename_it(zone->opts->name, zfile, data->file_num, 0,
			data->file_num, 1)) {
			/* failure, we cannot store files */
			/* delete the renamed files */
			ixfr_delete_rest_files(zone, data, zfile, 1);
			return 0;
		}

		/* the next cycle should start at the newest file that
		 * has been renamed to a temporary name */
		startspot = data;
		data = ixfr_data_next(zone->ixfr, data);
		destnum--;
	}

	/* rename the files to their final name position */
	data = startspot;
	while(data && data->file_num != 0) {
		destnum++;

		/* if there is an existing file, delete it */
		if(ixfr_file_exists(zfile, destnum)) {
			(void)ixfr_unlink_it(zone->opts->name, zfile,
				destnum, 0);
		}

		if(!ixfr_rename_it(zone->opts->name, zfile, data->file_num, 1, destnum, 0)) {
			/* failure, we cannot store files */
			ixfr_delete_rest_files(zone, data, zfile, 1);
			/* delete the previously renamed files, so in
			 * memory stays as is, on disk we have the current
			 * item (and newer transfers) okay. */
			return 0;
		}
		data->file_num = destnum;

		data = ixfr_data_prev(zone->ixfr, data, &prevcount);
	}
	return 1;
}

/* write the ixfr data file header */
static int ixfr_write_file_header(struct zone* zone, struct ixfr_data* data,
	FILE* out)
{
	if(!fprintf(out, "; IXFR data file\n"))
		return 0;
	if(!fprintf(out, "; zone %s\n", zone->opts->name))
		return 0;
	if(!fprintf(out, "; from_serial %u\n", (unsigned)data->oldserial))
		return 0;
	if(!fprintf(out, "; to_serial %u\n", (unsigned)data->newserial))
		return 0;
	if(!fprintf(out, "; data_size %u\n", (unsigned)ixfr_data_size(data)))
		return 0;
	if(data->log_str) {
		if(!fprintf(out, "; %s\n", data->log_str))
			return 0;
	}
	return 1;
}

/* parse wireformat RR into a struct RR in temp region */
static int parse_wirerr_into_temp(struct zone* zone, char* fname,
	struct region* temp, uint8_t* buf, size_t len,
	const dname_type** dname, struct rr** rr)
{
	size_t bufpos = 0;
	uint16_t rdlen, tp, klass;
	uint32_t ttl;
	int32_t code;
	const struct nsd_type_descriptor *descriptor;
	buffer_type packet;
	domain_table_type* owners;
	struct domain *domain;
	owners = domain_table_create(temp);
	*dname = dname_make(temp, buf, 1);
	if(!*dname) {
		log_msg(LOG_ERR, "failed to write zone %s IXFR data %s: failed to parse dname", zone->opts->name, fname);
		return 0;
	}
	bufpos = (*dname)->name_size;
	if(bufpos+10 > len) {
		log_msg(LOG_ERR, "failed to write zone %s IXFR data %s: buffer too short", zone->opts->name, fname);
		return 0;
	}
	tp = read_uint16(buf+bufpos);
	bufpos += 2;
	klass = read_uint16(buf+bufpos);
	bufpos += 2;
	ttl = read_uint32(buf+bufpos);
	bufpos += 4;
	rdlen = read_uint16(buf+bufpos);
	bufpos += 2;
	if(bufpos + rdlen > len) {
		log_msg(LOG_ERR, "failed to write zone %s IXFR data %s: buffer too short for rdatalen", zone->opts->name, fname);
		return 0;
	}
	domain = domain_table_insert(owners, *dname);
	buffer_create_from(&packet, buf+bufpos, rdlen);
	descriptor = nsd_type_descriptor(tp);
	code = descriptor->read_rdata(owners, rdlen, &packet, rr);
	if(code < 0) {
		log_msg(LOG_ERR, "failed to write zone %s IXFR data %s: cannot parse rdata %s %s %s", zone->opts->name, fname,
			dname_to_string(*dname,0), rrtype_to_string(tp),
			read_rdata_fail_str(code));
		return 0;
	}
	(*rr)->owner = domain;
	(*rr)->type = tp;
	(*rr)->klass = klass;
	(*rr)->ttl = ttl;
	return 1;
}

/* print RR on one line in output buffer. caller must zeroterminate, if
 * that is needed. */
static int print_rr_oneline(struct buffer* rr_buffer, const dname_type* dname,
	struct rr* rr)
{
	const nsd_type_descriptor_type *descriptor = nsd_type_descriptor(
		rr->type);
	buffer_printf(rr_buffer, "%s", dname_to_string(dname, NULL));
	buffer_printf(rr_buffer, "\t%lu\t%s\t%s", (unsigned long)rr->ttl,
		rrclass_to_string(rr->klass), rrtype_to_string(rr->type));
	if (!print_rdata(rr_buffer, descriptor, rr)) {
		if(!print_unknown_rdata(rr_buffer, descriptor, rr))
			return 0;
	}
	return 1;
}

/* write one RR to file, on one line */
static int ixfr_write_rr(struct zone* zone, FILE* out, char* fname,
	uint8_t* buf, size_t len, struct region* temp, buffer_type* rr_buffer)
{
	const dname_type* dname;
	struct rr* rr;

	if(!parse_wirerr_into_temp(zone, fname, temp, buf, len, &dname, &rr)) {
		region_free_all(temp);
		return 0;
	}

	buffer_clear(rr_buffer);
	if(!print_rr_oneline(rr_buffer, dname, rr)) {
		log_msg(LOG_ERR, "failed to write zone %s IXFR data %s: cannot spool RR string into buffer", zone->opts->name, fname);
		region_free_all(temp);
		return 0;
	}
	buffer_write_u8(rr_buffer, 0);
	buffer_flip(rr_buffer);

	if(!fprintf(out, "%s\n", buffer_begin(rr_buffer))) {
		log_msg(LOG_ERR, "failed to write zone %s IXFR data %s: cannot print RR string to file: %s", zone->opts->name, fname, strerror(errno));
		region_free_all(temp);
		return 0;
	}
	region_free_all(temp);
	return 1;
}

/* write ixfr RRs to file */
static int ixfr_write_rrs(struct zone* zone, FILE* out, char* fname,
	uint8_t* buf, size_t len, struct region* temp, buffer_type* rr_buffer)
{
	size_t current = 0;
	if(!buf || len == 0)
		return 1;
	while(current < len) {
		size_t rrlen = count_rr_length(buf, len, current);
		if(rrlen == 0)
			return 0;
		if(current + rrlen > len)
			return 0;
		if(!ixfr_write_rr(zone, out, fname, buf+current, rrlen,
			temp, rr_buffer))
			return 0;
		current += rrlen;
	}
	return 1;
}

/* write the ixfr data file data */
static int ixfr_write_file_data(struct zone* zone, struct ixfr_data* data,
	FILE* out, char* fname)
{
	struct region* temp, *rrtemp;
	buffer_type* rr_buffer;
	temp = region_create(xalloc, free);
	rrtemp = region_create(xalloc, free);
	rr_buffer = buffer_create(rrtemp, MAX_RDLENGTH);

	if(!ixfr_write_rrs(zone, out, fname, data->newsoa, data->newsoa_len,
		temp, rr_buffer)) {
		region_destroy(temp);
		region_destroy(rrtemp);
		return 0;
	}
	if(!ixfr_write_rrs(zone, out, fname, data->oldsoa, data->oldsoa_len,
		temp, rr_buffer)) {
		region_destroy(temp);
		region_destroy(rrtemp);
		return 0;
	}
	if(!ixfr_write_rrs(zone, out, fname, data->del, data->del_len,
		temp, rr_buffer)) {
		region_destroy(temp);
		region_destroy(rrtemp);
		return 0;
	}
	if(!ixfr_write_rrs(zone, out, fname, data->add, data->add_len,
		temp, rr_buffer)) {
		region_destroy(temp);
		region_destroy(rrtemp);
		return 0;
	}
	region_destroy(temp);
	region_destroy(rrtemp);
	return 1;
}

int ixfr_write_file(struct zone* zone, struct ixfr_data* data,
	const char* zfile, int file_num)
{
	char ixfrfile[1024+24];
	FILE* out;
	make_ixfr_name(ixfrfile, sizeof(ixfrfile), zfile, file_num);
	VERBOSITY(1, (LOG_INFO, "writing zone %s IXFR data to file %s",
		zone->opts->name, ixfrfile));
	out = fopen(ixfrfile, "w");
	if(!out) {
		log_msg(LOG_ERR, "could not open for writing zone %s IXFR file %s: %s",
			zone->opts->name, ixfrfile, strerror(errno));
		return 0;
	}

	if(!ixfr_write_file_header(zone, data, out)) {
		log_msg(LOG_ERR, "could not write file header for zone %s IXFR file %s: %s",
			zone->opts->name, ixfrfile, strerror(errno));
		fclose(out);
		return 0;
	}
	if(!ixfr_write_file_data(zone, data, out, ixfrfile)) {
		fclose(out);
		return 0;
	}

	fclose(out);
	data->file_num = file_num;
	return 1;
}

/* write the ixfr files that need to be stored on disk */
static void ixfr_write_files(struct zone* zone, const char* zfile)
{
	size_t prevcount = 0;
	int num;
	struct ixfr_data* data;
	if(!zone->ixfr || !zone->ixfr->data)
		return; /* nothing to write */

	/* write unwritten files to disk */
	data = ixfr_data_last(zone->ixfr);
	num=1;
	while(data && data->file_num == 0) {
		if(!ixfr_write_file(zone, data, zfile, num)) {
			/* There could be more files that are sitting on the
			 * disk, remove them, they are not used without
			 * this ixfr file.
			 *
			 * Give this element a file num, so it can be
			 * deleted, it failed to write. It may be partial,
			 * and we do not want to read that back in.
			 * We are left with the newer transfers, that form
			 * a correct list of transfers, that are wholly
			 * written. */
			data->file_num = num;
			ixfr_delete_rest_files(zone, data, zfile, 0);
			return;
		}
		num++;
		data = ixfr_data_prev(zone->ixfr, data, &prevcount);
	}
}

void ixfr_write_to_file(struct zone* zone, const char* zfile)
{
	int dest_num_files = 0;
	/* we just wrote the zonefile zfile, and it is time to write
	 * the IXFR contents to the disk too. */
	/* find out what the target number of files is that we want on
	 * the disk */
	dest_num_files = ixfr_target_number_files(zone);

	/* delete if we have more than we need */
	ixfr_delete_superfluous_files(zone, zfile, dest_num_files);

	/* delete if we have too much in memory */
	ixfr_delete_memory_items(zone, dest_num_files);

	/* rename the transfers that we have that already have a file */
	if(!ixfr_rename_files(zone, zfile, dest_num_files))
		return;

	/* write the transfers that are not written yet */
	ixfr_write_files(zone, zfile);
}

/* delete from domain table */
static void domain_table_delete(struct domain_table* table,
	struct domain* domain)
{
	/* first adjust the number list so that domain is the last one */
	numlist_make_last(table, domain);
	/* pop off the domain from the number list */
	(void)numlist_pop_last(table);

#ifdef USE_RADIX_TREE
	radix_delete(table->nametree, domain->rnode);
#else
	rbtree_delete(table->names_to_domains, domain->node.key);
#endif
}

/* can we delete temp domain */
static int can_del_temp_domain(struct domain* domain)
{
	struct domain* n;
	/* we want to keep the zone apex */
	if(domain->is_apex)
		return 0;
	if(domain->rrsets)
		return 0;
	if(domain->usage)
		return 0;
	/* check if there are domains under it */
	n = domain_next(domain);
	if(n && domain_is_subdomain(n, domain))
		return 0;
	return 1;
}

/* delete temporary domain */
static void ixfr_temp_deldomain(struct domain_table* temptable,
	struct domain* domain, struct domain* avoid)
{
	struct domain* p;
	if(domain == avoid || !can_del_temp_domain(domain))
		return;
	p = domain->parent;
	/* see if this domain is someones wildcard-child-closest-match,
	 * which can only be the parent, and then it should use the
	 * one-smaller than this domain as closest-match. */
	if(domain->parent &&
		domain->parent->wildcard_child_closest_match == domain)
		domain->parent->wildcard_child_closest_match =
			domain_previous_existing_child(domain);
	domain_table_delete(temptable, domain);
	while(p) {
		struct domain* up = p->parent;
		if(p == avoid || !can_del_temp_domain(p))
			break;
		if(p->parent && p->parent->wildcard_child_closest_match == p)
			p->parent->wildcard_child_closest_match =
				domain_previous_existing_child(p);
		domain_table_delete(temptable, p);
		p = up;
	}
}

/* clear out the just read RR from the temp table */
static void clear_temp_table_of_rr(struct domain_table* temptable,
	struct zone* tempzone, struct rr* rr)
{
	const nsd_type_descriptor_type* descriptor =
		nsd_type_descriptor(rr->type);

	/* clear domains in the rdata */
	if(descriptor->has_references) {
		uint16_t offset = 0;
		size_t i;
		for(i=0; i < descriptor->rdata.length; i++) {
			uint16_t field_len;
			struct domain* domain;
			if(rr->rdlength == offset &&
				descriptor->rdata.fields[i].is_optional)
				break; /* There are no more rdata fields. */
			if(!lookup_rdata_field_entry(descriptor, i, rr, offset,
				&field_len, &domain))
				break; /* malformed */
			if(domain != NULL) {
				/* The field is a domain reference. */
				/* clear out that dname */
				domain->usage --;
				if(domain != tempzone->apex &&
					domain->usage == 0)
					ixfr_temp_deldomain(temptable, domain,
						rr->owner);
			}
			offset += field_len;
		}
	}

	/* clear domain_parsed */
	if(rr->owner == tempzone->apex) {
		tempzone->apex->rrsets = NULL;
		tempzone->soa_rrset = NULL;
		tempzone->soa_nx_rrset = NULL;
		tempzone->ns_rrset = NULL;
	} else {
		rr->owner->rrsets = NULL;
		if(rr->owner->usage == 0) {
			ixfr_temp_deldomain(temptable, rr->owner, NULL);
		}
	}
}

/* read ixfr data new SOA */
static int ixfr_data_readnewsoa(struct ixfr_data* data, struct zone* zone,
	struct rr *rr, zone_parser_t *parser, struct region* tempregion,
	struct domain_table* temptable, struct zone* tempzone,
	uint32_t dest_serial)
{
	size_t capacity = 0;
	int code;
	if(rr->type != TYPE_SOA) {
		zone_error(parser, "zone %s ixfr data: IXFR data does not start with SOA",
			zone->opts->name);
		return 0;
	}
	if(rr->klass != CLASS_IN) {
		zone_error(parser, "zone %s ixfr data: IXFR data is not class IN",
			zone->opts->name);
		return 0;
	}
	if(!zone->apex) {
		zone_error(parser, "zone %s ixfr data: zone has no apex, no zone data",
			zone->opts->name);
		return 0;
	}
	if(dname_compare(domain_dname(zone->apex), domain_dname(rr->owner)) != 0) {
		zone_error(parser, "zone %s ixfr data: IXFR data wrong SOA for zone %s",
			zone->opts->name, domain_to_string(rr->owner));
		return 0;
	}
	data->newserial = soa_rr_get_serial(rr);
	if(data->newserial != dest_serial) {
		zone_error(parser, "zone %s ixfr data: IXFR data contains the wrong version, serial %u but want destination serial %u",
			zone->opts->name, data->newserial,
			dest_serial);
		return 0;
	}
	if((code=ixfr_putrr(rr, &data->newsoa, &data->newsoa_len, &capacity))
		<= 0) {
		if(code == -1)
			zone_error(parser, "zone %s ixfr data: cannot parse rdata format",
				zone->opts->name);
		else zone_error(parser, "zone %s ixfr data: cannot allocate space",
				zone->opts->name);
		return 0;
	}
	clear_temp_table_of_rr(temptable, tempzone, rr);
	region_free_all(tempregion);
	ixfr_trim_capacity(&data->newsoa, &data->newsoa_len, &capacity);
	return 1;
}

/* read ixfr data old SOA */
static int ixfr_data_readoldsoa(struct ixfr_data* data, struct zone* zone,
	struct rr *rr, zone_parser_t *parser, struct region* tempregion,
	struct domain_table* temptable, struct zone* tempzone,
	uint32_t* dest_serial)
{
	size_t capacity = 0;
	if(rr->type != TYPE_SOA) {
		zone_error(parser, "zone %s ixfr data: IXFR data 2nd RR is not SOA",
			zone->opts->name);
		return 0;
	}
	if(rr->klass != CLASS_IN) {
		zone_error(parser, "zone %s ixfr data: IXFR data 2ndSOA is not class IN",
			zone->opts->name);
		return 0;
	}
	if(!zone->apex) {
		zone_error(parser, "zone %s ixfr data: zone has no apex, no zone data",
			zone->opts->name);
		return 0;
	}
	if(dname_compare(domain_dname(zone->apex), domain_dname(rr->owner)) != 0) {
		zone_error(parser, "zone %s ixfr data: IXFR data wrong 2nd SOA for zone %s",
			zone->opts->name, domain_to_string(rr->owner));
		return 0;
	}
	data->oldserial = soa_rr_get_serial(rr);
	if(!ixfr_putrr(rr, &data->oldsoa, &data->oldsoa_len, &capacity)) {
		zone_error(parser, "zone %s ixfr data: cannot allocate space",
			zone->opts->name);
		return 0;
	}
	clear_temp_table_of_rr(temptable, tempzone, rr);
	region_free_all(tempregion);
	ixfr_trim_capacity(&data->oldsoa, &data->oldsoa_len, &capacity);
	*dest_serial = data->oldserial;
	return 1;
}

/* read ixfr data del section */
static int ixfr_data_readdel(struct ixfr_data* data, struct zone* zone,
	struct rr *rr, zone_parser_t *parser, struct region* tempregion,
	struct domain_table* temptable, struct zone* tempzone)
{
	size_t capacity = 0;
	if(!ixfr_putrr(rr, &data->del, &data->del_len, &capacity)) {
		zone_error(parser, "zone %s ixdr data: cannot allocate space",
			zone->opts->name);
		return 0;
	}
	clear_temp_table_of_rr(temptable, tempzone, rr);
	/* check SOA and also serial, because there could be other
	 * add and del sections from older versions collated, we can
	 * see this del section end when it has the serial */
	if(rr->type != TYPE_SOA && soa_rr_get_serial(rr) != data->newserial) {
		region_free_all(tempregion);
		return 1;
	}
	region_free_all(tempregion);
	ixfr_trim_capacity(&data->del, &data->del_len, &capacity);
	return 2;
}

/* read ixfr data add section */
static int ixfr_data_readadd(struct ixfr_data* data, struct zone* zone,
	struct rr *rr, zone_parser_t *parser, struct region* tempregion,
	struct domain_table* temptable, struct zone* tempzone)
{
	size_t capacity = 0;
	if(!ixfr_putrr(rr, &data->add, &data->add_len, &capacity)) {
		zone_error(parser, "zone %s ixfr data: cannot allocate space",
			zone->opts->name);
		return 0;
	}
	clear_temp_table_of_rr(temptable, tempzone, rr);
	if(rr->type != TYPE_SOA || soa_rr_get_serial(rr) != data->newserial) {
		region_free_all(tempregion);
		return 1;
	}
	region_free_all(tempregion);
	ixfr_trim_capacity(&data->add, &data->add_len, &capacity);
	return 2;
}

struct ixfr_data_state {
	struct zone *zone;
	struct ixfr_data *data;
	struct region *stayregion;
	struct region *tempregion;
	struct domain_table *temptable;
	struct zone *tempzone;
	uint32_t *dest_serial;
	size_t rr_count, soa_rr_count;
};

/* read one RR from file */
static int32_t ixfr_data_accept(
	zone_parser_t *parser,
	const zone_name_t *name,
	uint16_t type,
	uint16_t class,
	uint32_t ttl,
	uint16_t rdlength,
	const uint8_t *rdata,
	void *user_data)
{
	struct rr *rr;
	const struct dname *dname;
	struct domain *domain;
	struct buffer buffer;
	struct ixfr_data_state *state = (struct ixfr_data_state *)user_data;
	const struct nsd_type_descriptor *descriptor;
	int32_t code;

	assert(parser);

	buffer_create_from(&buffer, rdata, rdlength);

	dname = dname_make(state->tempregion, name->octets, 1);
	assert(dname);
	domain = domain_table_insert(state->temptable, dname);
	assert(domain);

	descriptor = nsd_type_descriptor(type);
	code = descriptor->read_rdata(state->temptable, rdlength, &buffer, &rr);
	/* This has validated the fields on the rdata. The content can be
	 * dealt with, if this is successful, later on by iterating over the
	 * rdata fields. For compression, and for printout, the rdata field
	 * format is known to be good.
	 * If the field validation is not needed, the wireformat in the
	 * rdata, rdlength could have been used to add to the ixfr store.
	 * But it is more prudent to validate the rdata fields. */
	if(code < 0) {
		if(verbosity >= 3) {
			zone_log(parser, ZONE_ERROR, "the RR rdata fields are wrong for the type");
		}
		VERBOSITY(3, (LOG_INFO, "zone %s IXFR bad RR, cannot parse "
			"rdata of %s %s %s", state->zone->opts->name,
			dname_to_string(dname, NULL), rrtype_to_string(type),
			read_rdata_fail_str(code)));
		if(code == TRUNCATED)
			return ZONE_OUT_OF_MEMORY;
		return ZONE_BAD_PARAMETER;
	}
	assert(rr);
	rr->owner = domain;
	rr->ttl = ttl;
	rr->type = type;
	rr->klass = class;

	if (state->rr_count == 0) {
		if (!ixfr_data_readnewsoa(state->data, state->zone, rr, parser,
		                          state->tempregion, state->temptable,
		                          state->tempzone, *state->dest_serial))
			return ZONE_SEMANTIC_ERROR;
	} else if (state->rr_count == 1) {
		if(!ixfr_data_readoldsoa(state->data, state->zone, rr, parser,
		                         state->tempregion, state->temptable,
		                         state->tempzone, state->dest_serial))
			return ZONE_SEMANTIC_ERROR;
	} else if (state->soa_rr_count == 0) {
		switch (ixfr_data_readdel(state->data, state->zone, rr, parser,
		                          state->tempregion, state->temptable,
		                          state->tempzone))
		{
			case 0:
				return ZONE_SEMANTIC_ERROR;
			case 1:
				break;
			case 2:
				state->soa_rr_count++;
				break;
		}
	} else if (state->soa_rr_count == 1) {
		switch (ixfr_data_readadd(state->data, state->zone, rr, parser,
		                          state->tempregion, state->temptable,
		                          state->tempzone))
		{
			case 0:
				return ZONE_SEMANTIC_ERROR;
			case 1:
				break;
			case 2:
				state->soa_rr_count++;
				break;
		}
	}

	state->rr_count++;
	return 0;
}

static void ixfr_data_log(
	zone_parser_t *parser,
	uint32_t category,
	const char *file,
	size_t line,
	const char *message,
	void *user_data)
{
	int priority = LOG_ERR;
	(void)parser;
	(void)file;
	(void)line;
	(void)user_data;
	if (category == ZONE_WARNING)
		priority = LOG_WARNING;
	log_msg(priority, "%s", message);
}

/* read ixfr data from file */
static int ixfr_data_read(struct nsd* nsd, struct zone* zone,
	const char* ixfrfile, uint32_t* dest_serial, int file_num)
{
	struct ixfr_data_state state = { 0 };

	if(!zone->apex) {
		return 0;
	}
	if(zone->ixfr &&
		zone->ixfr->data->count == zone->opts->pattern->ixfr_number) {
		VERBOSITY(3, (LOG_INFO, "zone %s skip %s IXFR data because only %d ixfr-number configured",
			zone->opts->name, ixfrfile, (int)zone->opts->pattern->ixfr_number));
		return 0;
	}

	/* the file has header comments, new soa, old soa, delsection,
	 * addsection. The delsection and addsection end in a SOA of oldver
	 * and newver respectively. */
	state.zone = zone;
	state.data = xalloc_zero(sizeof(*state.data));
	state.data->file_num = file_num;

	state.dest_serial = dest_serial;
	/* the temp region is cleared after every RR */
	state.tempregion = region_create(xalloc, free);
	/* the stay region holds the temporary data that stays between RRs */
	state.stayregion = region_create(xalloc, free);
	state.temptable = domain_table_create(state.stayregion);
	state.tempzone = region_alloc_zero(state.stayregion, sizeof(*state.tempzone));
	if(!zone->apex) {
		ixfr_data_free(state.data);
		region_destroy(state.tempregion);
		region_destroy(state.stayregion);
		return 0;
	}
	state.tempzone->apex = domain_table_insert(state.temptable,
		domain_dname(zone->apex));
	state.temptable->root->usage++;
	state.tempzone->apex->usage++;
	state.tempzone->opts = zone->opts;
	/* switch to per RR region for new allocations in temp domain table */
	state.temptable->region = state.tempregion;

  {
		const struct dname *origin;
		zone_parser_t parser;
		zone_options_t options;
		zone_name_buffer_t name_buffer;
		zone_rdata_buffer_t rdata_buffer;
		zone_buffers_t buffers = { 1, &name_buffer, &rdata_buffer };
		memset(&options, 0, sizeof(options));

		origin = domain_dname(zone->apex);
		options.origin.octets = dname_name(origin);
		options.origin.length = origin->name_size;
		options.no_includes = true;
		options.pretty_ttls = false;
		options.default_ttl = DEFAULT_TTL;
		options.default_class = CLASS_IN;
		options.log.callback = &ixfr_data_log;
		options.accept.callback = &ixfr_data_accept;

		if(zone_parse(&parser, &options, &buffers, ixfrfile, &state) != 0) {
			ixfr_data_free(state.data);
			region_destroy(state.tempregion);
			region_destroy(state.stayregion);
			return 0;
		}
	}

	region_destroy(state.tempregion);
	region_destroy(state.stayregion);

	if(!zone->ixfr)
		zone->ixfr = zone_ixfr_create(nsd);
	if(zone->opts->pattern->ixfr_size != 0 &&
		zone->ixfr->total_size + ixfr_data_size(state.data) >
		zone->opts->pattern->ixfr_size) {
		VERBOSITY(3, (LOG_INFO, "zone %s skip %s IXFR data because only ixfr-size: %u configured, and it is %u size",
			zone->opts->name, ixfrfile, (unsigned)zone->opts->pattern->ixfr_size, (unsigned)ixfr_data_size(state.data)));
		ixfr_data_free(state.data);
		return 0;
	}
	zone_ixfr_add(zone->ixfr, state.data, 0);
	VERBOSITY(3, (LOG_INFO, "zone %s read %s IXFR data of %u bytes",
		zone->opts->name, ixfrfile, (unsigned)ixfr_data_size(state.data)));
	return 1;
}

/* try to read the next ixfr file. returns false if it fails or if it
 * does not fit in the configured sizes */
static int ixfr_read_one_more_file(struct nsd* nsd, struct zone* zone,
	const char* zfile, int num_files, uint32_t *dest_serial)
{
	char ixfrfile[1024+24];
	struct stat statbuf;
	int file_num = num_files+1;
	make_ixfr_name(ixfrfile, sizeof(ixfrfile), zfile, file_num);
	/* if the file does not exist, all transfers have been read */
	if (stat(ixfrfile, &statbuf) != 0 && errno == ENOENT)
		return 0;
	return ixfr_data_read(nsd, zone, ixfrfile, dest_serial, file_num);
}

void ixfr_read_from_file(struct nsd* nsd, struct zone* zone, const char* zfile)
{
	uint32_t serial;
	int num_files = 0;
	/* delete the existing data, the zone data in memory has likely
	 * changed, eg. due to reading a new zonefile. So that needs new
	 * IXFRs */
	zone_ixfr_clear(zone->ixfr);

	/* track the serial number that we need to end up with, and check
	 * that the IXFRs match up and result in the required version */
	serial = zone_get_current_serial(zone);

	while(ixfr_read_one_more_file(nsd, zone, zfile, num_files, &serial)) {
		num_files++;
	}
	if(num_files > 0) {
		VERBOSITY(1, (LOG_INFO, "zone %s read %d IXFR transfers with success",
			zone->opts->name, num_files));
	}
}