xref: /netbsd/external/bsd/nsd/dist/ixfr.c (revision 66a1527d)

/*
 * 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"

/*
 * 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;
	}
}

/* calculate length of dname in uncompressed wireformat in buffer */
static size_t dname_length(const uint8_t* buf, size_t len)
{
	size_t l = 0;
	if(!buf || len == 0)
		return l;
	while(len > 0 && buf[0] != 0) {
		size_t lablen = (size_t)(buf[0]);
		if( (lablen&0xc0) )
			return 0; /* the name should be uncompressed */
		if(lablen+1 > len)
			return 0; /* should fit in the buffer */
		l += lablen+1;
		len -= lablen+1;
		buf += lablen+1;
	}
	if(len == 0)
		return 0; /* end label should fit in buffer */
	if(buf[0] != 0)
		return 0; /* must end in root label */
	l += 1; /* for the end root label */
	return l;
}

/* 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 = 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;
}

/* 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)
{
	size_t oldpos = buffer_position(packet);
	size_t rdpos;
	uint16_t tp;
	int dname_len;
	size_t rdlen;
	size_t i;
	rrtype_descriptor_type* descriptor;

	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 */
	descriptor = rrtype_descriptor_by_type(tp);
	for(i=0; i<descriptor->maximum; i++) {
		size_t copy_len = 0;
		if(rdlen == 0)
			break;

		switch(rdata_atom_wireformat_type(tp, i)) {
		case RDATA_WF_COMPRESSED_DNAME:
			dname_len = pktcompression_write_dname(packet, pcomp,
				rr, rdlen);
			if(dname_len == -1)
				return 1; /* attempt to skip malformed rr */
			if(dname_len == 0) {
				buffer_set_position(packet, oldpos);
				return 0;
			}
			rr += dname_len;
			rdlen -= dname_len;
			break;
		case RDATA_WF_UNCOMPRESSED_DNAME:
		case RDATA_WF_LITERAL_DNAME:
			copy_len = rdlen;
			break;
		case RDATA_WF_BYTE:
			copy_len = 1;
			break;
		case RDATA_WF_SHORT:
			copy_len = 2;
			break;
		case RDATA_WF_LONG:
			copy_len = 4;
			break;
		case RDATA_WF_TEXTS:
		case RDATA_WF_LONG_TEXT:
			copy_len = rdlen;
			break;
		case RDATA_WF_TEXT:
		case RDATA_WF_BINARYWITHLENGTH:
			copy_len = 1;
			if(rdlen > copy_len)
				copy_len += rr[0];
			break;
		case RDATA_WF_A:
			copy_len = 4;
			break;
		case RDATA_WF_AAAA:
			copy_len = 16;
			break;
		case RDATA_WF_ILNP64:
			copy_len = 8;
			break;
		case RDATA_WF_EUI48:
			copy_len = EUI48ADDRLEN;
			break;
		case RDATA_WF_EUI64:
			copy_len = EUI64ADDRLEN;
			break;
		case RDATA_WF_BINARY:
			copy_len = rdlen;
			break;
		case RDATA_WF_APL:
			copy_len = (sizeof(uint16_t)    /* address family */
                                  + sizeof(uint8_t)   /* prefix */
                                  + sizeof(uint8_t)); /* length */
			if(copy_len <= rdlen)
				copy_len += (rr[copy_len-1]&APL_LENGTH_MASK);
			break;
		case RDATA_WF_IPSECGATEWAY:
			copy_len = rdlen;
			break;
		case RDATA_WF_SVCPARAM:
			copy_len = 4;
			if(copy_len <= rdlen)
				copy_len += read_uint16(rr+2);
			break;
		default:
			copy_len = rdlen;
			break;
		}
		if(copy_len) {
			if(!buffer_available(packet, copy_len)) {
				buffer_set_position(packet, oldpos);
				return 0;
			}
			if(copy_len > rdlen)
				return 1; /* assert of skip malformed */
			buffer_write(packet, rr, copy_len);
			rr += copy_len;
			rdlen -= copy_len;
		}
	}
	/* write compressed rdata length */
	buffer_write_u16_at(packet, rdpos, buffer_position(packet)-rdpos-2);
	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 RR */
static uint32_t soa_rr_get_serial(struct rr* rr)
{
	if(rr->rdata_count < 3)
		return 0;
	if(rr->rdatas[2].data[0] < 4)
		return 0;
	return read_uint32(&rr->rdatas[2].data[1]);
}

/* 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;
	if(zone->soa_rrset->rrs[0].rdata_count < 3)
		return 0;
	if(zone->soa_rrset->rrs[0].rdatas[2].data[0] < 4)
		return 0;
	return read_uint32(&zone->soa_rrset->rrs[0].rdatas[2].data[1]);
}

/* 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)) {
			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)) {
			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)) {
			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)) {
			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;
			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;
			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;
			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, uint32_t old_serial,
	uint32_t new_serial)
{
	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));
	ixfr_store->data->oldserial = old_serial;
	ixfr_store->data->newserial = new_serial;
	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(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,
	struct buffer* packet, size_t ttlpos)
{
	size_t oldpos, sz = 0;
	uint32_t ttl, serial, refresh, retry, expire, minimum;
	uint16_t rdlen_uncompressed, rdlen_wire;
	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);
	buffer_set_position(packet, ttlpos);

	/* calculate the length */
	sz = domain_dname(ixfr_store->zone->apex)->name_size;
	sz += 2 /* type */ + 2 /* class */;
	/* read ttl */
	if(!buffer_available(packet, 4/*ttl*/+2/*rdlen*/)) {
		/* not possible already parsed, but fail nicely anyway */
		log_msg(LOG_ERR, "ixfr_store: not enough space in packet");
		ixfr_store_cancel(ixfr_store);
		buffer_set_position(packet, oldpos);
		return;
	}
	ttl = buffer_read_u32(packet);
	sz += 4;
	rdlen_wire = buffer_read_u16(packet);
	sz += 2;
	if(!buffer_available(packet, rdlen_wire)) {
		/* 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(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;

	/* 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(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;

	/* 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 */
static int ixfr_putrr(const struct dname* dname, uint16_t type, uint16_t klass,
	uint32_t ttl, rdata_atom_type* rdatas, ssize_t rdata_num,
	uint8_t** rrs, size_t* rrs_len, size_t* rrs_capacity)
{
	size_t rdlen_uncompressed, sz;
	uint8_t* sp;
	int i;

	/* find rdatalen */
	rdlen_uncompressed = 0;
	for(i=0; i<rdata_num; i++) {
		if(rdata_atom_is_domain(type, i)) {
			rdlen_uncompressed += domain_dname(rdatas[i].domain)
				->name_size;
		} else {
			rdlen_uncompressed += rdatas[i].data[0];
		}
	}
	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, type);
	sp += 2;
	write_uint16(sp, klass);
	sp += 2;
	write_uint32(sp, ttl);
	sp += 4;
	write_uint16(sp, rdlen_uncompressed);
	sp += 2;
	for(i=0; i<rdata_num; i++) {
		if(rdata_atom_is_domain(type, i)) {
			memmove(sp, dname_name(domain_dname(rdatas[i].domain)),
				domain_dname(rdatas[i].domain)->name_size);
			sp += domain_dname(rdatas[i].domain)->name_size;
		} else {
			memmove(sp, &rdatas[i].data[1], rdatas[i].data[0]);
			sp += rdatas[i].data[0];
		}
	}
	return 1;
}

void ixfr_store_putrr(struct ixfr_store* ixfr_store, const struct dname* dname,
	uint16_t type, uint16_t klass, uint32_t ttl, struct buffer* packet,
	uint16_t rrlen, struct region* temp_region, uint8_t** rrs,
	size_t* rrs_len, size_t* rrs_capacity)
{
	domain_table_type *temptable;
	rdata_atom_type *rdatas;
	ssize_t rdata_num;
	size_t oldpos;

	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(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;

	/* parse rdata */
	oldpos = buffer_position(packet);
	temptable = domain_table_create(temp_region);
	rdata_num = rdata_wireformat_to_rdata_atoms(temp_region, temptable,
		type, rrlen, packet, &rdatas);
	buffer_set_position(packet, oldpos);
	if(rdata_num == -1) {
		log_msg(LOG_ERR, "ixfr_store addrr: cannot parse packet");
		ixfr_store_cancel(ixfr_store);
		return;
	}

	if(!ixfr_putrr(dname, type, klass, ttl, rdatas, rdata_num,
		rrs, rrs_len, rrs_capacity)) {
		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 struct dname* dname,
	uint16_t type, uint16_t klass, uint32_t ttl, struct buffer* packet,
	uint16_t rrlen, struct region* temp_region)
{
	ixfr_store_putrr(ixfr_store, dname, type, klass, ttl, packet, rrlen,
		temp_region, &ixfr_store->data->del,
		&ixfr_store->data->del_len, &ixfr_store->del_capacity);
}

void ixfr_store_addrr(struct ixfr_store* ixfr_store, const struct dname* dname,
	uint16_t type, uint16_t klass, uint32_t ttl, struct buffer* packet,
	uint16_t rrlen, struct region* temp_region)
{
	ixfr_store_putrr(ixfr_store, dname, type, klass, ttl, packet, rrlen,
		temp_region, &ixfr_store->data->add,
		&ixfr_store->data->add_len, &ixfr_store->add_capacity);
}

int ixfr_store_addrr_rdatas(struct ixfr_store* ixfr_store,
	const struct dname* dname, uint16_t type, uint16_t klass,
	uint32_t ttl, rdata_atom_type* rdatas, ssize_t rdata_num)
{
	if(ixfr_store->cancelled)
		return 1;
	if(type == TYPE_SOA)
		return 1;
	return ixfr_putrr(dname, type, klass, ttl, rdatas, rdata_num,
		&ixfr_store->data->add, &ixfr_store->data->add_len,
		&ixfr_store->add_capacity);
}

int ixfr_store_add_newsoa_rdatas(struct ixfr_store* ixfr_store,
	const struct dname* dname, uint16_t type, uint16_t klass,
	uint32_t ttl, rdata_atom_type* rdatas, ssize_t rdata_num)
{
	size_t capacity = 0;
	if(ixfr_store->cancelled)
		return 1;
	if(!ixfr_putrr(dname, type, klass, ttl, rdatas, rdata_num,
		&ixfr_store->data->newsoa, &ixfr_store->data->newsoa_len,
		&ixfr_store->add_capacity))
		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);
}

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)
{
	size_t capacity = 0;
	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;
	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;
}

/* print rdata on one line */
static int
oneline_print_rdata(buffer_type *output, rrtype_descriptor_type *descriptor,
	rr_type* record)
{
	size_t i;
	size_t saved_position = buffer_position(output);

	for (i = 0; i < record->rdata_count; ++i) {
		if (i == 0) {
			buffer_printf(output, "\t");
		} else {
			buffer_printf(output, " ");
		}
		if (!rdata_atom_to_string(
			    output,
			    (rdata_zoneformat_type) descriptor->zoneformat[i],
			    record->rdatas[i], record))
		{
			buffer_set_position(output, saved_position);
			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;
	ssize_t rdata_num;
	buffer_type packet;
	domain_table_type* owners;
	owners = domain_table_create(temp);
	memset(rr, 0, sizeof(*rr));
	*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;
	}
	rr->type = read_uint16(buf+bufpos);
	bufpos += 2;
	rr->klass = read_uint16(buf+bufpos);
	bufpos += 2;
	rr->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;
	}
	buffer_create_from(&packet, buf+bufpos, rdlen);
	rdata_num = rdata_wireformat_to_rdata_atoms(
		temp, owners, rr->type, rdlen, &packet, &rr->rdatas);
	if(rdata_num == -1) {
		log_msg(LOG_ERR, "failed to write zone %s IXFR data %s: cannot parse rdata", zone->opts->name, fname);
		return 0;
	}
	rr->rdata_count = rdata_num;
	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)
{
	rrtype_descriptor_type *descriptor;
	descriptor = rrtype_descriptor_by_type(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(!oneline_print_rdata(rr_buffer, descriptor, rr)) {
		if(!rdata_atoms_to_unknown_string(rr_buffer,
			descriptor, rr->rdata_count, rr->rdatas)) {
			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);
}

/* skip whitespace */
static char* skipwhite(char* str)
{
	while(isspace((unsigned char)*str))
		str++;
	return str;
}

/* read one RR from file */
static int ixfr_data_readrr(struct zone* zone, FILE* in, const char* ixfrfile,
	struct region* tempregion, struct domain_table* temptable,
	struct zone* tempzone, struct rr** rr)
{
	char line[65536];
	char* str;
	struct domain* domain_parsed = NULL;
	int num_rrs = 0;
	line[sizeof(line)-1]=0;
	while(!feof(in)) {
		if(!fgets(line, sizeof(line), in)) {
			if(errno == 0) {
				log_msg(LOG_ERR, "zone %s IXFR data %s: "
					"unexpected end of file", zone->opts->name, ixfrfile);
				return 0;
			}
			log_msg(LOG_ERR, "zone %s IXFR data %s: "
				"cannot read: %s", zone->opts->name, ixfrfile,
				strerror(errno));
			return 0;
		}
		str = skipwhite(line);
		if(str[0] == 0) {
			/* empty line */
			continue;
		}
		if(str[0] == ';') {
			/* comment line */
			continue;
		}
		if(zonec_parse_string(tempregion, temptable, tempzone,
			line, &domain_parsed, &num_rrs)) {
			log_msg(LOG_ERR, "zone %s IXFR data %s: parse error",
				zone->opts->name, ixfrfile);
			return 0;
		}
		if(num_rrs != 1) {
			log_msg(LOG_ERR, "zone %s IXFR data %s: parse error",
				zone->opts->name, ixfrfile);
			return 0;
		}
		*rr = &domain_parsed->rrsets->rrs[0];
		return 1;
	}
	log_msg(LOG_ERR, "zone %s IXFR data %s: file too short, no newsoa",
		zone->opts->name, ixfrfile);
	return 0;
}

/* delete from domain table */
static void domain_table_delete(struct domain_table* table,
	struct domain* domain)
{
#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* p;
	if(!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(!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)
{
#if 0 /* clear out by removing everything, alternate for the cleanout code */
	/* clear domains from the tempzone,
	 * the only domain left is the zone apex and its parents */
	domain_type* domain;
#ifdef USE_RADIX_TREE
	struct radnode* first = radix_first(temptable->nametree);
	domain = first?(domain_type*)first->elem:NULL;
#else
	domain = (domain_type*)rbtree_first(temptable->names_to_domains);
#endif
	while(domain != (domain_type*)RBTREE_NULL && domain) {
		domain_type* next = domain_next(domain);
		if(domain != tempzone->apex &&
			!domain_is_subdomain(tempzone->apex, domain)) {
			domain_table_delete(temptable, domain);
		} else {
			if(!domain->parent /* is the root */ ||
				domain == tempzone->apex)
				domain->usage = 1;
			else	domain->usage = 0;
		}
		domain = next;
	}

	if(rr->owner == tempzone->apex) {
		tempzone->apex->rrsets = NULL;
		tempzone->soa_rrset = NULL;
		tempzone->soa_nx_rrset = NULL;
		tempzone->ns_rrset = NULL;
	}
	return;
#endif

	/* clear domains in the rdata */
	unsigned i;
	for(i=0; i<rr->rdata_count; i++) {
		if(rdata_atom_is_domain(rr->type, i)) {
			/* clear out that dname */
			struct domain* domain =
				rdata_atom_domain(rr->rdatas[i]);
			domain->usage --;
			if(domain != tempzone->apex && domain->usage == 0)
				ixfr_temp_deldomain(temptable, domain);
		}
	}

	/* 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);
		}
	}
}

/* read ixfr data new SOA */
static int ixfr_data_readnewsoa(struct ixfr_data* data, struct zone* zone,
	FILE* in, const char* ixfrfile, struct region* tempregion,
	struct domain_table* temptable, struct zone* tempzone,
	uint32_t dest_serial)
{
	struct rr* rr;
	size_t capacity = 0;
	if(!ixfr_data_readrr(zone, in, ixfrfile, tempregion, temptable,
		tempzone, &rr))
		return 0;
	if(rr->type != TYPE_SOA) {
		log_msg(LOG_ERR, "zone %s ixfr data %s: IXFR data does not start with SOA",
			zone->opts->name, ixfrfile);
		return 0;
	}
	if(rr->klass != CLASS_IN) {
		log_msg(LOG_ERR, "zone %s ixfr data %s: IXFR data is not class IN",
			zone->opts->name, ixfrfile);
		return 0;
	}
	if(!zone->apex) {
		log_msg(LOG_ERR, "zone %s ixfr data %s: zone has no apex, no zone data",
			zone->opts->name, ixfrfile);
		return 0;
	}
	if(dname_compare(domain_dname(zone->apex), domain_dname(rr->owner)) != 0) {
		log_msg(LOG_ERR, "zone %s ixfr data %s: IXFR data wrong SOA for zone %s",
			zone->opts->name, ixfrfile, domain_to_string(rr->owner));
		return 0;
	}
	data->newserial = soa_rr_get_serial(rr);
	if(data->newserial != dest_serial) {
		log_msg(LOG_ERR, "zone %s ixfr data %s: IXFR data contains the wrong version, serial %u but want destination serial %u",
			zone->opts->name, ixfrfile, data->newserial,
			dest_serial);
		return 0;
	}
	if(!ixfr_putrr(domain_dname(rr->owner), rr->type, rr->klass, rr->ttl, rr->rdatas, rr->rdata_count, &data->newsoa, &data->newsoa_len, &capacity)) {
		log_msg(LOG_ERR, "zone %s ixfr data %s: cannot allocate space",
			zone->opts->name, ixfrfile);
		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,
	FILE* in, const char* ixfrfile, struct region* tempregion,
	struct domain_table* temptable, struct zone* tempzone,
	uint32_t* dest_serial)
{
	struct rr* rr;
	size_t capacity = 0;
	if(!ixfr_data_readrr(zone, in, ixfrfile, tempregion, temptable,
		tempzone, &rr))
		return 0;
	if(rr->type != TYPE_SOA) {
		log_msg(LOG_ERR, "zone %s ixfr data %s: IXFR data 2nd RR is not SOA",
			zone->opts->name, ixfrfile);
		return 0;
	}
	if(rr->klass != CLASS_IN) {
		log_msg(LOG_ERR, "zone %s ixfr data %s: IXFR data 2ndSOA is not class IN",
			zone->opts->name, ixfrfile);
		return 0;
	}
	if(!zone->apex) {
		log_msg(LOG_ERR, "zone %s ixfr data %s: zone has no apex, no zone data",
			zone->opts->name, ixfrfile);
		return 0;
	}
	if(dname_compare(domain_dname(zone->apex), domain_dname(rr->owner)) != 0) {
		log_msg(LOG_ERR, "zone %s ixfr data %s: IXFR data wrong 2nd SOA for zone %s",
			zone->opts->name, ixfrfile, domain_to_string(rr->owner));
		return 0;
	}
	data->oldserial = soa_rr_get_serial(rr);
	if(!ixfr_putrr(domain_dname(rr->owner), rr->type, rr->klass, rr->ttl, rr->rdatas, rr->rdata_count, &data->oldsoa, &data->oldsoa_len, &capacity)) {
		log_msg(LOG_ERR, "zone %s ixfr data %s: cannot allocate space",
			zone->opts->name, ixfrfile);
		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,
	FILE* in, const char* ixfrfile, struct region* tempregion,
	struct domain_table* temptable, struct zone* tempzone)
{
	struct rr* rr;
	size_t capacity = 0;
	while(1) {
		if(!ixfr_data_readrr(zone, in, ixfrfile, tempregion, temptable,
			tempzone, &rr))
			return 0;
		if(!ixfr_putrr(domain_dname(rr->owner), rr->type, rr->klass, rr->ttl, rr->rdatas, rr->rdata_count, &data->del, &data->del_len, &capacity)) {
			log_msg(LOG_ERR, "zone %s ixfr data %s: cannot allocate space",
				zone->opts->name, ixfrfile);
			return 0;
		}
		/* 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) {
			/* end of del section. */
			clear_temp_table_of_rr(temptable, tempzone, rr);
			region_free_all(tempregion);
			break;
		}
		clear_temp_table_of_rr(temptable, tempzone, rr);
		region_free_all(tempregion);
	}
	ixfr_trim_capacity(&data->del, &data->del_len, &capacity);
	return 1;
}

/* read ixfr data add section */
static int ixfr_data_readadd(struct ixfr_data* data, struct zone* zone,
	FILE* in, const char* ixfrfile, struct region* tempregion,
	struct domain_table* temptable, struct zone* tempzone)
{
	struct rr* rr;
	size_t capacity = 0;
	while(1) {
		if(!ixfr_data_readrr(zone, in, ixfrfile, tempregion, temptable,
			tempzone, &rr))
			return 0;
		if(!ixfr_putrr(domain_dname(rr->owner), rr->type, rr->klass, rr->ttl, rr->rdatas, rr->rdata_count, &data->add, &data->add_len, &capacity)) {
			log_msg(LOG_ERR, "zone %s ixfr data %s: cannot allocate space",
				zone->opts->name, ixfrfile);
			return 0;
		}
		if(rr->type == TYPE_SOA &&
			soa_rr_get_serial(rr) == data->newserial) {
			/* end of add section. */
			clear_temp_table_of_rr(temptable, tempzone, rr);
			region_free_all(tempregion);
			break;
		}
		clear_temp_table_of_rr(temptable, tempzone, rr);
		region_free_all(tempregion);
	}
	ixfr_trim_capacity(&data->add, &data->add_len, &capacity);
	return 1;
}

/* read ixfr data from file */
static int ixfr_data_read(struct nsd* nsd, struct zone* zone, FILE* in,
	const char* ixfrfile, uint32_t* dest_serial, int file_num)
{
	struct ixfr_data* data = NULL;
	struct region* tempregion, *stayregion;
	struct domain_table* temptable;
	struct zone* tempzone;

	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. */
	data = xalloc_zero(sizeof(*data));
	data->file_num = file_num;

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

	if(!ixfr_data_readnewsoa(data, zone, in, ixfrfile, tempregion,
		temptable, tempzone, *dest_serial)) {
		ixfr_data_free(data);
		region_destroy(tempregion);
		region_destroy(stayregion);
		return 0;
	}
	if(!ixfr_data_readoldsoa(data, zone, in, ixfrfile, tempregion,
		temptable, tempzone, dest_serial)) {
		ixfr_data_free(data);
		region_destroy(tempregion);
		region_destroy(stayregion);
		return 0;
	}
	if(!ixfr_data_readdel(data, zone, in, ixfrfile, tempregion, temptable,
		tempzone)) {
		ixfr_data_free(data);
		region_destroy(tempregion);
		region_destroy(stayregion);
		return 0;
	}
	if(!ixfr_data_readadd(data, zone, in, ixfrfile, tempregion, temptable,
		tempzone)) {
		ixfr_data_free(data);
		region_destroy(tempregion);
		region_destroy(stayregion);
		return 0;
	}

	region_destroy(tempregion);
	region_destroy(stayregion);

	if(!zone->ixfr)
		zone->ixfr = zone_ixfr_create(nsd);
	if(zone->opts->pattern->ixfr_size != 0 &&
		zone->ixfr->total_size + ixfr_data_size(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(data)));
		ixfr_data_free(data);
		return 0;
	}
	zone_ixfr_add(zone->ixfr, data, 0);
	VERBOSITY(3, (LOG_INFO, "zone %s read %s IXFR data of %u bytes",
		zone->opts->name, ixfrfile, (unsigned)ixfr_data_size(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];
	FILE* in;
	int file_num = num_files+1;
	make_ixfr_name(ixfrfile, sizeof(ixfrfile), zfile, file_num);
	in = fopen(ixfrfile, "r");
	if(!in) {
		if(errno == ENOENT) {
			/* the file does not exist, we reached the end
			 * of the list of IXFR files */
			return 0;
		}
		log_msg(LOG_ERR, "could not read zone %s IXFR file %s: %s",
			zone->opts->name, ixfrfile, strerror(errno));
		return 0;
	}
	warn_if_directory("IXFR data", in, ixfrfile);
	if(!ixfr_data_read(nsd, zone, in, ixfrfile, dest_serial, file_num)) {
		fclose(in);
		return 0;
	}
	fclose(in);
	return 1;
}

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));
	}
}