1/*
2 * util.c -- set of various support routines.
3 *
4 * Copyright (c) 2001-2006, NLnet Labs. All rights reserved.
5 *
6 * See LICENSE for the license.
7 *
8 */
9
10#include "config.h"
11
12#include <assert.h>
13#include <ctype.h>
14#include <errno.h>
15#include <stdarg.h>
16#include <stdio.h>
17#include <stdlib.h>
18#include <string.h>
19#ifdef HAVE_SCHED_H
20#include <sched.h>
21#endif /* HAVE_SCHED_H */
22#ifdef HAVE_SYS_CPUSET_H
23#include <sys/cpuset.h>
24#endif /* HAVE_SYS_CPUSET_H */
25#ifdef HAVE_SYSLOG_H
26#include <syslog.h>
27#endif /* HAVE_SYSLOG_H */
28#include <unistd.h>
29#ifdef HAVE_SYS_RANDOM_H
30#include <sys/random.h>
31#endif
32
33#include "util.h"
34#include "region-allocator.h"
35#include "dname.h"
36#include "namedb.h"
37#include "rdata.h"
38#include "zonec.h"
39#include "nsd.h"
40
41#ifdef USE_MMAP_ALLOC
42#include <sys/mman.h>
43
44#if defined(MAP_ANON) && !defined(MAP_ANONYMOUS)
45#define	MAP_ANONYMOUS	MAP_ANON
46#elif defined(MAP_ANONYMOUS) && !defined(MAP_ANON)
47#define	MAP_ANON	MAP_ANONYMOUS
48#endif
49
50#endif /* USE_MMAP_ALLOC */
51
52#ifndef NDEBUG
53unsigned nsd_debug_facilities = 0xffff;
54int nsd_debug_level = 0;
55#endif
56
57#define MSB_32 0x80000000
58
59int verbosity = 0;
60
61static const char *global_ident = NULL;
62static log_function_type *current_log_function = log_file;
63static FILE *current_log_file = NULL;
64int log_time_asc = 1;
65
66void
67log_init(const char *ident)
68{
69	global_ident = ident;
70	current_log_file = stderr;
71}
72
73void
74log_open(int option, int facility, const char *filename)
75{
76#ifdef HAVE_SYSLOG_H
77	openlog(global_ident, option, facility);
78#endif /* HAVE_SYSLOG_H */
79	if (filename) {
80		FILE *file = fopen(filename, "a");
81		if (!file) {
82			log_msg(LOG_ERR, "Cannot open %s for appending (%s), "
83					 "logging to stderr",
84				filename, strerror(errno));
85		} else {
86			current_log_file = file;
87		}
88	}
89}
90
91void
92log_reopen(const char *filename, uint8_t verbose)
93{
94	if (filename) {
95		FILE *file;
96		if(strcmp(filename, "/dev/stdout")==0 || strcmp(filename, "/dev/stderr")==0)
97			return;
98		file = fopen(filename, "a");
99		if (!file) {
100			if (verbose)
101				VERBOSITY(2, (LOG_WARNING,
102                                	"Cannot reopen %s for appending (%s), "
103					"keeping old logfile",
104					filename, strerror(errno)));
105		} else {
106			if (current_log_file && current_log_file != stderr)
107				fclose(current_log_file);
108			current_log_file = file;
109		}
110	}
111}
112
113void
114log_finalize(void)
115{
116#ifdef HAVE_SYSLOG_H
117	closelog();
118#endif /* HAVE_SYSLOG_H */
119	if (current_log_file && current_log_file != stderr) {
120		fclose(current_log_file);
121	}
122	current_log_file = NULL;
123}
124
125static lookup_table_type log_priority_table[] = {
126	{ LOG_ERR, "error" },
127	{ LOG_WARNING, "warning" },
128	{ LOG_NOTICE, "notice" },
129	{ LOG_INFO, "info" },
130	{ 0, NULL }
131};
132
133void
134log_file(int priority, const char *message)
135{
136	size_t length;
137	lookup_table_type *priority_info;
138	const char *priority_text = "unknown";
139
140	assert(global_ident);
141	assert(current_log_file);
142
143	priority_info = lookup_by_id(log_priority_table, priority);
144	if (priority_info) {
145		priority_text = priority_info->name;
146	}
147
148	/* Bug #104, add time_t timestamp */
149#if defined(HAVE_STRFTIME) && defined(HAVE_LOCALTIME_R)
150	if(log_time_asc) {
151		struct timeval tv;
152		char tmbuf[32];
153		tmbuf[0]=0;
154		tv.tv_usec = 0;
155		if(gettimeofday(&tv, NULL) == 0) {
156			struct tm tm;
157			time_t now = (time_t)tv.tv_sec;
158			strftime(tmbuf, sizeof(tmbuf), "%Y-%m-%d %H:%M:%S",
159				localtime_r(&now, &tm));
160		}
161		fprintf(current_log_file, "[%s.%3.3d] %s[%d]: %s: %s",
162			tmbuf, (int)tv.tv_usec/1000,
163			global_ident, (int) getpid(), priority_text, message);
164 	} else
165#endif /* have time functions */
166		fprintf(current_log_file, "[%d] %s[%d]: %s: %s",
167		(int)time(NULL), global_ident, (int) getpid(), priority_text, message);
168	length = strlen(message);
169	if (length == 0 || message[length - 1] != '\n') {
170		fprintf(current_log_file, "\n");
171	}
172	fflush(current_log_file);
173}
174
175void
176log_syslog(int priority, const char *message)
177{
178#ifdef HAVE_SYSLOG_H
179	syslog(priority, "%s", message);
180#endif /* !HAVE_SYSLOG_H */
181	log_file(priority, message);
182}
183
184void
185log_only_syslog(int priority, const char *message)
186{
187#ifdef HAVE_SYSLOG_H
188	syslog(priority, "%s", message);
189#else /* !HAVE_SYSLOG_H */
190	/* no syslog, use stderr */
191	log_file(priority, message);
192#endif
193}
194
195void
196log_set_log_function(log_function_type *log_function)
197{
198	current_log_function = log_function;
199}
200
201void
202log_msg(int priority, const char *format, ...)
203{
204	va_list args;
205	va_start(args, format);
206	log_vmsg(priority, format, args);
207	va_end(args);
208}
209
210void
211log_vmsg(int priority, const char *format, va_list args)
212{
213	char message[MAXSYSLOGMSGLEN];
214	vsnprintf(message, sizeof(message), format, args);
215	current_log_function(priority, message);
216}
217
218void
219set_bit(uint8_t bits[], size_t index)
220{
221	/*
222	 * The bits are counted from left to right, so bit #0 is the
223	 * left most bit.
224	 */
225	bits[index / 8] |= (1 << (7 - index % 8));
226}
227
228void
229clear_bit(uint8_t bits[], size_t index)
230{
231	/*
232	 * The bits are counted from left to right, so bit #0 is the
233	 * left most bit.
234	 */
235	bits[index / 8] &= ~(1 << (7 - index % 8));
236}
237
238int
239get_bit(uint8_t bits[], size_t index)
240{
241	/*
242	 * The bits are counted from left to right, so bit #0 is the
243	 * left most bit.
244	 */
245	return bits[index / 8] & (1 << (7 - index % 8));
246}
247
248lookup_table_type *
249lookup_by_name(lookup_table_type *table, const char *name)
250{
251	while (table->name != NULL) {
252		if (strcasecmp(name, table->name) == 0)
253			return table;
254		table++;
255	}
256	return NULL;
257}
258
259lookup_table_type *
260lookup_by_id(lookup_table_type *table, int id)
261{
262	while (table->name != NULL) {
263		if (table->id == id)
264			return table;
265		table++;
266	}
267	return NULL;
268}
269
270char *
271xstrdup(const char *src)
272{
273	char *result = strdup(src);
274
275	if(!result) {
276		log_msg(LOG_ERR, "strdup failed: %s", strerror(errno));
277		exit(1);
278	}
279
280	return result;
281}
282
283void *
284xalloc(size_t size)
285{
286	void *result = malloc(size);
287
288	if (!result) {
289		log_msg(LOG_ERR, "malloc failed: %s", strerror(errno));
290		exit(1);
291	}
292	return result;
293}
294
295void *
296xmallocarray(size_t num, size_t size)
297{
298        void *result = reallocarray(NULL, num, size);
299
300        if (!result) {
301                log_msg(LOG_ERR, "reallocarray failed: %s", strerror(errno));
302                exit(1);
303        }
304        return result;
305}
306
307void *
308xalloc_zero(size_t size)
309{
310	void *result = calloc(1, size);
311	if (!result) {
312		log_msg(LOG_ERR, "calloc failed: %s", strerror(errno));
313		exit(1);
314	}
315	return result;
316}
317
318void *
319xalloc_array_zero(size_t num, size_t size)
320{
321	void *result = calloc(num, size);
322	if (!result) {
323		log_msg(LOG_ERR, "calloc failed: %s", strerror(errno));
324		exit(1);
325	}
326	return result;
327}
328
329void *
330xrealloc(void *ptr, size_t size)
331{
332	ptr = realloc(ptr, size);
333	if (!ptr) {
334		log_msg(LOG_ERR, "realloc failed: %s", strerror(errno));
335		exit(1);
336	}
337	return ptr;
338}
339
340#ifdef USE_MMAP_ALLOC
341
342void *
343mmap_alloc(size_t size)
344{
345	void *base;
346
347	size += MMAP_ALLOC_HEADER_SIZE;
348#ifdef HAVE_MMAP
349	base = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
350	if (base == MAP_FAILED) {
351		log_msg(LOG_ERR, "mmap failed: %s", strerror(errno));
352		exit(1);
353	}
354#else /* !HAVE_MMAP */
355	log_msg(LOG_ERR, "mmap failed: don't have mmap");
356	exit(1);
357#endif /* HAVE_MMAP */
358
359	*((size_t*) base) = size;
360	return (void*)((uintptr_t)base + MMAP_ALLOC_HEADER_SIZE);
361}
362
363
364void
365mmap_free(void *ptr)
366{
367	void *base;
368	size_t size;
369
370	if (!ptr) return;
371
372	base = (void*)((uintptr_t)ptr - MMAP_ALLOC_HEADER_SIZE);
373	size = *((size_t*) base);
374
375#ifdef HAVE_MUNMAP
376	if (munmap(base, size) == -1) {
377		log_msg(LOG_ERR, "munmap failed: %s", strerror(errno));
378		exit(1);
379	}
380#else /* !HAVE_MUNMAP */
381	log_msg(LOG_ERR, "munmap failed: don't have munmap");
382	exit(1);
383#endif /* HAVE_MUNMAP */
384}
385
386#endif /* USE_MMAP_ALLOC */
387
388int
389write_data(FILE *file, const void *data, size_t size)
390{
391	size_t result;
392
393	if (size == 0)
394		return 1;
395
396	result = fwrite(data, 1, size, file);
397
398	if (result == 0) {
399		log_msg(LOG_ERR, "write failed: %s", strerror(errno));
400		return 0;
401	} else if (result < size) {
402		log_msg(LOG_ERR, "short write (disk full?)");
403		return 0;
404	} else {
405		return 1;
406	}
407}
408
409int
410write_socket(int s, const void *buf, size_t size)
411{
412	const char* data = (const char*)buf;
413	size_t total_count = 0;
414
415	while (total_count < size) {
416		ssize_t count
417			= write(s, data + total_count, size - total_count);
418		if (count == -1) {
419			if (errno != EAGAIN && errno != EINTR) {
420				return 0;
421			} else {
422				continue;
423			}
424		}
425		total_count += count;
426	}
427	return 1;
428}
429
430void get_time(struct timespec* t)
431{
432	struct timeval tv;
433#ifdef HAVE_CLOCK_GETTIME
434	/* first try nanosecond precision */
435	if(clock_gettime(CLOCK_REALTIME, t)>=0) {
436		return; /* success */
437	}
438	log_msg(LOG_ERR, "clock_gettime: %s", strerror(errno));
439#endif
440	/* try millisecond precision */
441	if(gettimeofday(&tv, NULL)>=0) {
442		t->tv_sec = tv.tv_sec;
443		t->tv_nsec = tv.tv_usec*1000;
444		return; /* success */
445	}
446	log_msg(LOG_ERR, "gettimeofday: %s", strerror(errno));
447	/* whole seconds precision */
448	t->tv_sec = time(0);
449	t->tv_nsec = 0;
450}
451
452int
453timespec_compare(const struct timespec *left,
454		 const struct timespec *right)
455{
456	/* Compare seconds.  */
457	if (left->tv_sec < right->tv_sec) {
458		return -1;
459	} else if (left->tv_sec > right->tv_sec) {
460		return 1;
461	} else {
462		/* Seconds are equal, compare nanoseconds.  */
463		if (left->tv_nsec < right->tv_nsec) {
464			return -1;
465		} else if (left->tv_nsec > right->tv_nsec) {
466			return 1;
467		} else {
468			return 0;
469		}
470	}
471}
472
473
474/* One second is 1e9 nanoseconds.  */
475#define NANOSECONDS_PER_SECOND   1000000000L
476
477void
478timespec_add(struct timespec *left,
479	     const struct timespec *right)
480{
481	left->tv_sec += right->tv_sec;
482	left->tv_nsec += right->tv_nsec;
483	if (left->tv_nsec >= NANOSECONDS_PER_SECOND) {
484		/* Carry.  */
485		++left->tv_sec;
486		left->tv_nsec -= NANOSECONDS_PER_SECOND;
487	}
488}
489
490void
491timespec_subtract(struct timespec *left,
492		  const struct timespec *right)
493{
494	left->tv_sec -= right->tv_sec;
495	left->tv_nsec -= right->tv_nsec;
496	if (left->tv_nsec < 0L) {
497		/* Borrow.  */
498		--left->tv_sec;
499		left->tv_nsec += NANOSECONDS_PER_SECOND;
500	}
501}
502
503uint32_t
504strtoserial(const char* nptr, const char** endptr)
505{
506	uint32_t i = 0;
507	uint32_t serial = 0;
508
509	for(*endptr = nptr; **endptr; (*endptr)++) {
510		switch (**endptr) {
511		case ' ':
512		case '\t':
513			break;
514		case '0':
515		case '1':
516		case '2':
517		case '3':
518		case '4':
519		case '5':
520		case '6':
521		case '7':
522		case '8':
523		case '9':
524			if((i*10)/10 != i)
525				/* number too large, return i
526				 * with *endptr != 0 as a failure*/
527				return i;
528			i *= 10;
529			i += (**endptr - '0');
530			break;
531		default:
532			return 0;
533		}
534	}
535	serial += i;
536	return serial;
537}
538
539uint32_t
540strtottl(const char *nptr, const char **endptr)
541{
542	uint32_t i = 0;
543	uint32_t seconds = 0;
544
545	for(*endptr = nptr; **endptr; (*endptr)++) {
546		switch (**endptr) {
547		case ' ':
548		case '\t':
549			break;
550		case 's':
551		case 'S':
552			seconds += i;
553			i = 0;
554			break;
555		case 'm':
556		case 'M':
557			seconds += i * 60;
558			i = 0;
559			break;
560		case 'h':
561		case 'H':
562			seconds += i * 60 * 60;
563			i = 0;
564			break;
565		case 'd':
566		case 'D':
567			seconds += i * 60 * 60 * 24;
568			i = 0;
569			break;
570		case 'w':
571		case 'W':
572			seconds += i * 60 * 60 * 24 * 7;
573			i = 0;
574			break;
575		case '0':
576		case '1':
577		case '2':
578		case '3':
579		case '4':
580		case '5':
581		case '6':
582		case '7':
583		case '8':
584		case '9':
585			i *= 10;
586			i += (**endptr - '0');
587			break;
588		default:
589			seconds += i;
590			/**
591			 * According to RFC2308, Section 8, the MSB
592			 * (sign bit) should be set to zero.
593			 * If we encounter a value larger than 2^31 -1,
594			 * we fall back to the default TTL.
595			 */
596			if ((seconds & MSB_32)) {
597				seconds = DEFAULT_TTL;
598			}
599			return seconds;
600		}
601	}
602	seconds += i;
603	if ((seconds & MSB_32)) {
604		seconds = DEFAULT_TTL;
605	}
606	return seconds;
607}
608
609
610ssize_t
611hex_ntop(uint8_t const *src, size_t srclength, char *target, size_t targsize)
612{
613	static char hexdigits[] = {
614		'0', '1', '2', '3', '4', '5', '6', '7',
615		'8', '9', 'a', 'b', 'c', 'd', 'e', 'f'
616	};
617	size_t i;
618
619	if (targsize < srclength * 2 + 1) {
620		return -1;
621	}
622
623	for (i = 0; i < srclength; ++i) {
624		*target++ = hexdigits[src[i] >> 4U];
625		*target++ = hexdigits[src[i] & 0xfU];
626	}
627	*target = '\0';
628	return 2 * srclength;
629}
630
631ssize_t
632hex_pton(const char* src, uint8_t* target, size_t targsize)
633{
634	uint8_t *t = target;
635	if(strlen(src) % 2 != 0 || strlen(src)/2 > targsize) {
636		return -1;
637	}
638	while(*src) {
639		if(!isxdigit((unsigned char)src[0]) ||
640			!isxdigit((unsigned char)src[1]))
641			return -1;
642		*t++ = hexdigit_to_int(src[0]) * 16 +
643			hexdigit_to_int(src[1]) ;
644		src += 2;
645	}
646	return t-target;
647}
648
649int
650b32_ntop(uint8_t const *src, size_t srclength, char *target, size_t targsize)
651{
652	static char b32[]="0123456789abcdefghijklmnopqrstuv";
653	char buf[9];
654	ssize_t len=0;
655
656	while(srclength > 0)
657	{
658		int t;
659		memset(buf,'\0',sizeof buf);
660
661		/* xxxxx000 00000000 00000000 00000000 00000000 */
662		buf[0]=b32[src[0] >> 3];
663
664		/* 00000xxx xx000000 00000000 00000000 00000000 */
665		t=(src[0]&7) << 2;
666		if(srclength > 1)
667			t+=src[1] >> 6;
668		buf[1]=b32[t];
669		if(srclength == 1)
670			break;
671
672		/* 00000000 00xxxxx0 00000000 00000000 00000000 */
673		buf[2]=b32[(src[1] >> 1)&0x1f];
674
675		/* 00000000 0000000x xxxx0000 00000000 00000000 */
676		t=(src[1]&1) << 4;
677		if(srclength > 2)
678			t+=src[2] >> 4;
679		buf[3]=b32[t];
680		if(srclength == 2)
681			break;
682
683		/* 00000000 00000000 0000xxxx x0000000 00000000 */
684		t=(src[2]&0xf) << 1;
685		if(srclength > 3)
686			t+=src[3] >> 7;
687		buf[4]=b32[t];
688		if(srclength == 3)
689			break;
690
691		/* 00000000 00000000 00000000 0xxxxx00 00000000 */
692		buf[5]=b32[(src[3] >> 2)&0x1f];
693
694		/* 00000000 00000000 00000000 000000xx xxx00000 */
695		t=(src[3]&3) << 3;
696		if(srclength > 4)
697			t+=src[4] >> 5;
698		buf[6]=b32[t];
699		if(srclength == 4)
700			break;
701
702		/* 00000000 00000000 00000000 00000000 000xxxxx */
703		buf[7]=b32[src[4]&0x1f];
704
705		if(targsize < 8)
706			return -1;
707
708		src += 5;
709		srclength -= 5;
710
711		memcpy(target,buf,8);
712		target += 8;
713		targsize -= 8;
714		len += 8;
715	}
716	if(srclength)
717	{
718		size_t tlen = strlcpy(target, buf, targsize);
719		if (tlen >= targsize)
720			return -1;
721		len += tlen;
722	}
723	else if(targsize < 1)
724		return -1;
725	else
726		*target='\0';
727	return len;
728}
729
730int
731b32_pton(const char *src, uint8_t *target, size_t tsize)
732{
733	char ch;
734	size_t p=0;
735
736	memset(target,'\0',tsize);
737	while((ch = *src++)) {
738		uint8_t d;
739		size_t b;
740		size_t n;
741
742		if(p+5 >= tsize*8)
743		       return -1;
744
745		if(isspace((unsigned char)ch))
746			continue;
747
748		if(ch >= '0' && ch <= '9')
749			d=ch-'0';
750		else if(ch >= 'A' && ch <= 'V')
751			d=ch-'A'+10;
752		else if(ch >= 'a' && ch <= 'v')
753			d=ch-'a'+10;
754		else
755			return -1;
756
757		b=7-p%8;
758		n=p/8;
759
760		if(b >= 4)
761			target[n]|=d << (b-4);
762		else {
763			target[n]|=d >> (4-b);
764			target[n+1]|=d << (b+4);
765		}
766		p+=5;
767	}
768	return (p+7)/8;
769}
770
771void
772strip_string(char *str)
773{
774	char *start = str;
775	char *end = str + strlen(str) - 1;
776
777	while (isspace((unsigned char)*start))
778		++start;
779	if (start > end) {
780		/* Completely blank. */
781		str[0] = '\0';
782	} else {
783		while (isspace((unsigned char)*end))
784			--end;
785		*++end = '\0';
786
787		if (str != start)
788			memmove(str, start, end - start + 1);
789	}
790}
791
792int
793hexdigit_to_int(char ch)
794{
795	switch (ch) {
796	case '0': return 0;
797	case '1': return 1;
798	case '2': return 2;
799	case '3': return 3;
800	case '4': return 4;
801	case '5': return 5;
802	case '6': return 6;
803	case '7': return 7;
804	case '8': return 8;
805	case '9': return 9;
806	case 'a': case 'A': return 10;
807	case 'b': case 'B': return 11;
808	case 'c': case 'C': return 12;
809	case 'd': case 'D': return 13;
810	case 'e': case 'E': return 14;
811	case 'f': case 'F': return 15;
812	default:
813		abort();
814	}
815}
816
817/* Number of days per month (except for February in leap years). */
818static const int mdays[] = {
819    31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
820};
821
822static int
823is_leap_year(int year)
824{
825    return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);
826}
827
828static int
829leap_days(int y1, int y2)
830{
831    --y1;
832    --y2;
833    return (y2/4 - y1/4) - (y2/100 - y1/100) + (y2/400 - y1/400);
834}
835
836/*
837 * Code adapted from Python 2.4.1 sources (Lib/calendar.py).
838 */
839time_t
840mktime_from_utc(const struct tm *tm)
841{
842    int year = 1900 + tm->tm_year;
843    time_t days = 365 * (year - 1970) + leap_days(1970, year);
844    time_t hours;
845    time_t minutes;
846    time_t seconds;
847    int i;
848
849    for (i = 0; i < tm->tm_mon; ++i) {
850        days += mdays[i];
851    }
852    if (tm->tm_mon > 1 && is_leap_year(year)) {
853        ++days;
854    }
855    days += tm->tm_mday - 1;
856
857    hours = days * 24 + tm->tm_hour;
858    minutes = hours * 60 + tm->tm_min;
859    seconds = minutes * 60 + tm->tm_sec;
860
861    return seconds;
862}
863
864/* code to calculate CRC. Lifted from BSD 4.4 crc.c in cksum(1). BSD license.
865   http://www.tsfr.org/~orc/Code/bsd/bsd-current/cksum/crc.c.
866   or http://gobsd.com/code/freebsd/usr.bin/cksum/crc.c
867   The polynomial is 0x04c11db7L. */
868static uint32_t crctab[] = {
869	0x0,
870	0x04c11db7, 0x09823b6e, 0x0d4326d9, 0x130476dc, 0x17c56b6b,
871	0x1a864db2, 0x1e475005, 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6,
872	0x2b4bcb61, 0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,
873	0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9, 0x5f15adac,
874	0x5bd4b01b, 0x569796c2, 0x52568b75, 0x6a1936c8, 0x6ed82b7f,
875	0x639b0da6, 0x675a1011, 0x791d4014, 0x7ddc5da3, 0x709f7b7a,
876	0x745e66cd, 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
877	0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5, 0xbe2b5b58,
878	0xbaea46ef, 0xb7a96036, 0xb3687d81, 0xad2f2d84, 0xa9ee3033,
879	0xa4ad16ea, 0xa06c0b5d, 0xd4326d90, 0xd0f37027, 0xddb056fe,
880	0xd9714b49, 0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95,
881	0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1, 0xe13ef6f4,
882	0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d, 0x34867077, 0x30476dc0,
883	0x3d044b19, 0x39c556ae, 0x278206ab, 0x23431b1c, 0x2e003dc5,
884	0x2ac12072, 0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16,
885	0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca, 0x7897ab07,
886	0x7c56b6b0, 0x71159069, 0x75d48dde, 0x6b93dddb, 0x6f52c06c,
887	0x6211e6b5, 0x66d0fb02, 0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1,
888	0x53dc6066, 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
889	0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e, 0xbfa1b04b,
890	0xbb60adfc, 0xb6238b25, 0xb2e29692, 0x8aad2b2f, 0x8e6c3698,
891	0x832f1041, 0x87ee0df6, 0x99a95df3, 0x9d684044, 0x902b669d,
892	0x94ea7b2a, 0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e,
893	0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2, 0xc6bcf05f,
894	0xc27dede8, 0xcf3ecb31, 0xcbffd686, 0xd5b88683, 0xd1799b34,
895	0xdc3abded, 0xd8fba05a, 0x690ce0ee, 0x6dcdfd59, 0x608edb80,
896	0x644fc637, 0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb,
897	0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f, 0x5c007b8a,
898	0x58c1663d, 0x558240e4, 0x51435d53, 0x251d3b9e, 0x21dc2629,
899	0x2c9f00f0, 0x285e1d47, 0x36194d42, 0x32d850f5, 0x3f9b762c,
900	0x3b5a6b9b, 0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
901	0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623, 0xf12f560e,
902	0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7, 0xe22b20d2, 0xe6ea3d65,
903	0xeba91bbc, 0xef68060b, 0xd727bbb6, 0xd3e6a601, 0xdea580d8,
904	0xda649d6f, 0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3,
905	0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7, 0xae3afba2,
906	0xaafbe615, 0xa7b8c0cc, 0xa379dd7b, 0x9b3660c6, 0x9ff77d71,
907	0x92b45ba8, 0x9675461f, 0x8832161a, 0x8cf30bad, 0x81b02d74,
908	0x857130c3, 0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640,
909	0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c, 0x7b827d21,
910	0x7f436096, 0x7200464f, 0x76c15bf8, 0x68860bfd, 0x6c47164a,
911	0x61043093, 0x65c52d24, 0x119b4be9, 0x155a565e, 0x18197087,
912	0x1cd86d30, 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
913	0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088, 0x2497d08d,
914	0x2056cd3a, 0x2d15ebe3, 0x29d4f654, 0xc5a92679, 0xc1683bce,
915	0xcc2b1d17, 0xc8ea00a0, 0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb,
916	0xdbee767c, 0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18,
917	0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4, 0x89b8fd09,
918	0x8d79e0be, 0x803ac667, 0x84fbdbd0, 0x9abc8bd5, 0x9e7d9662,
919	0x933eb0bb, 0x97ffad0c, 0xafb010b1, 0xab710d06, 0xa6322bdf,
920	0xa2f33668, 0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
921};
922
923#define	COMPUTE(var, ch)	(var) = (var) << 8 ^ crctab[(var) >> 24 ^ (ch)]
924
925uint32_t
926compute_crc(uint32_t crc, uint8_t* data, size_t len)
927{
928	size_t i;
929	for(i=0; i<len; ++i)
930		COMPUTE(crc, data[i]);
931	return crc;
932}
933
934int
935write_data_crc(FILE *file, const void *data, size_t size, uint32_t* crc)
936{
937	int ret = write_data(file, data, size);
938	*crc = compute_crc(*crc, (uint8_t*)data, size);
939	return ret;
940}
941
942#define SERIAL_BITS      32
943int
944compare_serial(uint32_t a, uint32_t b)
945{
946        const uint32_t cutoff = ((uint32_t) 1 << (SERIAL_BITS - 1));
947
948        if (a == b) {
949                return 0;
950        } else if ((a < b && b - a < cutoff) || (a > b && a - b > cutoff)) {
951                return -1;
952        } else {
953                return 1;
954        }
955}
956
957uint16_t
958qid_generate(void)
959{
960#ifdef HAVE_GETRANDOM
961	uint16_t r;
962	if(getrandom(&r, sizeof(r), 0) == -1) {
963		log_msg(LOG_ERR, "getrandom failed: %s", strerror(errno));
964		exit(1);
965	}
966	return r;
967#elif defined(HAVE_ARC4RANDOM)
968    /* arc4random_uniform not needed because range is a power of 2 */
969    return (uint16_t) arc4random();
970#else
971    return (uint16_t) random();
972#endif
973}
974
975int
976random_generate(int max)
977{
978#ifdef HAVE_GETRANDOM
979	int r;
980	if(getrandom(&r, sizeof(r), 0) == -1) {
981		log_msg(LOG_ERR, "getrandom failed: %s", strerror(errno));
982		exit(1);
983	}
984	return (int)(((unsigned)r)%max);
985#elif defined(HAVE_ARC4RANDOM_UNIFORM)
986    return (int) arc4random_uniform(max);
987#elif defined(HAVE_ARC4RANDOM)
988    return (int) (arc4random() % max);
989#else
990    return (int) ((unsigned)random() % max);
991#endif
992}
993
994void
995cleanup_region(void *data)
996{
997	region_type *region = (region_type *) data;
998	region_destroy(region);
999}
1000
1001struct state_pretty_rr*
1002create_pretty_rr(struct region* region)
1003{
1004	struct state_pretty_rr* state = (struct state_pretty_rr*)
1005		region_alloc(region, sizeof(struct state_pretty_rr));
1006	state->previous_owner_region = region_create(xalloc, free);
1007	state->previous_owner = NULL;
1008	state->previous_owner_origin = NULL;
1009        region_add_cleanup(region, cleanup_region,
1010		state->previous_owner_region);
1011	return state;
1012}
1013
1014static void
1015set_previous_owner(struct state_pretty_rr *state, const dname_type *dname)
1016{
1017	region_free_all(state->previous_owner_region);
1018	state->previous_owner = dname_copy(state->previous_owner_region, dname);
1019	state->previous_owner_origin = dname_origin(
1020		state->previous_owner_region, state->previous_owner);
1021}
1022
1023int
1024print_rr(FILE *out,
1025         struct state_pretty_rr *state,
1026         rr_type *record,
1027	 region_type* rr_region,
1028	 buffer_type* output)
1029{
1030        rrtype_descriptor_type *descriptor
1031                = rrtype_descriptor_by_type(record->type);
1032        int result;
1033        const dname_type *owner = domain_dname(record->owner);
1034	buffer_clear(output);
1035        if (state) {
1036		if (!state->previous_owner
1037			|| dname_compare(state->previous_owner, owner) != 0) {
1038			const dname_type *owner_origin
1039				= dname_origin(rr_region, owner);
1040			int origin_changed = (!state->previous_owner_origin
1041				|| dname_compare(state->previous_owner_origin,
1042				   owner_origin) != 0);
1043			if (origin_changed) {
1044				buffer_printf(output, "$ORIGIN %s\n",
1045					dname_to_string(owner_origin, NULL));
1046			}
1047
1048			set_previous_owner(state, owner);
1049			buffer_printf(output, "%s",
1050				dname_to_string(owner,
1051					state->previous_owner_origin));
1052			region_free_all(rr_region);
1053		}
1054	} else {
1055		buffer_printf(output, "%s", dname_to_string(owner, NULL));
1056	}
1057
1058	buffer_printf(output, "\t%lu\t%s\t%s",
1059		(unsigned long) record->ttl,
1060		rrclass_to_string(record->klass),
1061		rrtype_to_string(record->type));
1062
1063	result = print_rdata(output, descriptor, record);
1064	if (!result) {
1065		/*
1066		 * Some RDATA failed to print, so print the record's
1067		 * RDATA in unknown format.
1068		 */
1069		result = rdata_atoms_to_unknown_string(output,
1070			descriptor, record->rdata_count, record->rdatas);
1071	}
1072
1073	if (result) {
1074		buffer_printf(output, "\n");
1075		buffer_flip(output);
1076		result = write_data(out, buffer_current(output),
1077		buffer_remaining(output));
1078	}
1079	return result;
1080}
1081
1082const char*
1083rcode2str(int rc)
1084{
1085	switch(rc) {
1086		case RCODE_OK:
1087			return "NO ERROR";
1088		case RCODE_FORMAT:
1089			return "FORMAT ERROR";
1090		case RCODE_SERVFAIL:
1091			return "SERVFAIL";
1092		case RCODE_NXDOMAIN:
1093			return "NAME ERROR";
1094		case RCODE_IMPL:
1095			return "NOT IMPL";
1096		case RCODE_REFUSE:
1097			return "REFUSED";
1098		case RCODE_YXDOMAIN:
1099			return "YXDOMAIN";
1100		case RCODE_YXRRSET:
1101			return "YXRRSET";
1102		case RCODE_NXRRSET:
1103			return "NXRRSET";
1104		case RCODE_NOTAUTH:
1105			return "SERVER NOT AUTHORITATIVE FOR ZONE";
1106		case RCODE_NOTZONE:
1107			/* Name not contained in zone */
1108			return "NOTZONE";
1109		default:
1110			return "UNKNOWN ERROR";
1111	}
1112	return NULL; /* ENOREACH */
1113}
1114
1115void
1116addr2str(
1117#ifdef INET6
1118	struct sockaddr_storage *addr
1119#else
1120	struct sockaddr_in *addr
1121#endif
1122	, char* str, size_t len)
1123{
1124#ifdef INET6
1125	if (addr->ss_family == AF_INET6) {
1126		if (!inet_ntop(AF_INET6,
1127			&((struct sockaddr_in6 *)addr)->sin6_addr, str, len))
1128			strlcpy(str, "[unknown ip6, inet_ntop failed]", len);
1129		return;
1130	}
1131#endif
1132	if (!inet_ntop(AF_INET, &((struct sockaddr_in *)addr)->sin_addr,
1133		str, len))
1134		strlcpy(str, "[unknown ip4, inet_ntop failed]", len);
1135}
1136
1137void
1138addrport2str(
1139#ifdef INET6
1140	struct sockaddr_storage *addr
1141#else
1142	struct sockaddr_in *addr
1143#endif
1144	, char* str, size_t len)
1145{
1146	char ip[256];
1147#ifdef INET6
1148	if (addr->ss_family == AF_INET6) {
1149		if (!inet_ntop(AF_INET6,
1150			&((struct sockaddr_in6 *)addr)->sin6_addr, ip, sizeof(ip)))
1151			strlcpy(ip, "[unknown ip6, inet_ntop failed]", sizeof(ip));
1152		/* append port number */
1153		snprintf(str, len, "%s@%u", ip,
1154			(unsigned)ntohs(((struct sockaddr_in6 *)addr)->sin6_port));
1155		return;
1156	} else
1157#endif
1158	if (!inet_ntop(AF_INET, &((struct sockaddr_in *)addr)->sin_addr,
1159		ip, sizeof(ip)))
1160		strlcpy(ip, "[unknown ip4, inet_ntop failed]", sizeof(ip));
1161	/* append port number */
1162	snprintf(str, len, "%s@%u", ip,
1163		(unsigned)ntohs(((struct sockaddr_in *)addr)->sin_port));
1164}
1165
1166void
1167append_trailing_slash(const char** dirname, region_type* region)
1168{
1169	int l = strlen(*dirname);
1170	if (l>0 && (*dirname)[l-1] != '/' && l < 0xffffff) {
1171		char *dirname_slash = region_alloc(region, l+2);
1172		memcpy(dirname_slash, *dirname, l+1);
1173		strlcat(dirname_slash, "/", l+2);
1174		/* old dirname is leaked, this is only used for chroot, once */
1175		*dirname = dirname_slash;
1176	}
1177}
1178
1179int
1180file_inside_chroot(const char* fname, const char* chr)
1181{
1182	/* true if filename starts with chroot or is not absolute */
1183	return ((fname && fname[0] && strncmp(fname, chr, strlen(chr)) == 0) ||
1184		(fname && fname[0] != '/'));
1185}
1186
1187/*
1188 * Something went wrong, give error messages and exit.
1189 */
1190void
1191error(const char *format, ...)
1192{
1193	va_list args;
1194	va_start(args, format);
1195	log_vmsg(LOG_ERR, format, args);
1196	va_end(args);
1197	exit(1);
1198}
1199
1200#ifdef HAVE_CPUSET_T
1201#if defined(HAVE_SYSCONF) && defined(_SC_NPROCESSORS_CONF)
1202/* exists on Linux and FreeBSD */
1203int number_of_cpus(void)
1204{
1205	return (int)sysconf(_SC_NPROCESSORS_CONF);
1206}
1207#else
1208int number_of_cpus(void)
1209{
1210	return -1;
1211}
1212#endif
1213#ifdef __gnu_hurd__
1214/* HURD has no sched_setaffinity implementation, but links an always fail,
1215 * with a linker error, we print an error when it is used */
1216int set_cpu_affinity(cpuset_t *ATTR_UNUSED(set))
1217{
1218	log_err("sched_setaffinity: not available on this system");
1219	return -1;
1220}
1221#elif defined(HAVE_SCHED_SETAFFINITY)
1222/* Linux */
1223int set_cpu_affinity(cpuset_t *set)
1224{
1225	assert(set != NULL);
1226	return sched_setaffinity(getpid(), sizeof(*set), set);
1227}
1228#else
1229/* FreeBSD */
1230int set_cpu_affinity(cpuset_t *set)
1231{
1232	assert(set != NULL);
1233	return cpuset_setaffinity(
1234		CPU_LEVEL_WHICH, CPU_WHICH_PID, -1, sizeof(*set), set);
1235}
1236#endif
1237#endif /* HAVE_CPUSET_T */
1238
1239void add_cookie_secret(struct nsd* nsd, uint8_t* secret)
1240{
1241	/* New cookie secret becomes the staging secret (position 1)
1242	 * unless there is no active cookie yet, then it becomes the active
1243	 * secret.  If the NSD_COOKIE_HISTORY_SIZE > 2 then all staging cookies
1244	 * are moved one position down.
1245	 */
1246	if(nsd->cookie_count == 0) {
1247		memcpy( nsd->cookie_secrets->cookie_secret
1248		       , secret, NSD_COOKIE_SECRET_SIZE);
1249		nsd->cookie_count = 1;
1250		explicit_bzero(secret, NSD_COOKIE_SECRET_SIZE);
1251		return;
1252	}
1253#if NSD_COOKIE_HISTORY_SIZE > 2
1254	memmove( &nsd->cookie_secrets[2], &nsd->cookie_secrets[1]
1255	       , sizeof(struct cookie_secret) * (NSD_COOKIE_HISTORY_SIZE - 2));
1256#endif
1257	memcpy( nsd->cookie_secrets[1].cookie_secret
1258	      , secret, NSD_COOKIE_SECRET_SIZE);
1259	nsd->cookie_count = nsd->cookie_count     < NSD_COOKIE_HISTORY_SIZE
1260	                  ? nsd->cookie_count + 1 : NSD_COOKIE_HISTORY_SIZE;
1261	explicit_bzero(secret, NSD_COOKIE_SECRET_SIZE);
1262}
1263
1264void activate_cookie_secret(struct nsd* nsd)
1265{
1266	uint8_t active_secret[NSD_COOKIE_SECRET_SIZE];
1267	/* The staging secret becomes the active secret.
1268	 * The active secret becomes a staging secret.
1269	 * If the NSD_COOKIE_HISTORY_SIZE > 2 then all staging secrets are moved
1270	 * one position up and the previously active secret becomes the last
1271	 * staging secret.
1272	 */
1273	if(nsd->cookie_count < 2)
1274		return;
1275	memcpy( active_secret, nsd->cookie_secrets[0].cookie_secret
1276	      , NSD_COOKIE_SECRET_SIZE);
1277	memmove( &nsd->cookie_secrets[0], &nsd->cookie_secrets[1]
1278	       , sizeof(struct cookie_secret) * (NSD_COOKIE_HISTORY_SIZE - 1));
1279	memcpy( nsd->cookie_secrets[nsd->cookie_count - 1].cookie_secret
1280	      , active_secret, NSD_COOKIE_SECRET_SIZE);
1281	explicit_bzero(active_secret, NSD_COOKIE_SECRET_SIZE);
1282}
1283
1284void drop_cookie_secret(struct nsd* nsd)
1285{
1286	/* Drops a staging cookie secret. If there are more than one, it will
1287	 * drop the last staging secret. */
1288	if(nsd->cookie_count < 2)
1289		return;
1290	explicit_bzero( nsd->cookie_secrets[nsd->cookie_count - 1].cookie_secret
1291	              , NSD_COOKIE_SECRET_SIZE);
1292	nsd->cookie_count -= 1;
1293}
1294