1/*++
2/* NAME
3/*	dns_rr 3
4/* SUMMARY
5/*	resource record memory and list management
6/* SYNOPSIS
7/*	#include <dns.h>
8/*
9/*	DNS_RR	*dns_rr_create(qname, rname, type, class, ttl, preference,
10/*				data, data_len)
11/*	const char *qname;
12/*	const char *rname;
13/*	unsigned short type;
14/*	unsigned short class;
15/*	unsigned int ttl;
16/*	unsigned preference;
17/*	const char *data;
18/*	size_t data_len;
19/*
20/*	void	dns_rr_free(list)
21/*	DNS_RR	*list;
22/*
23/*	DNS_RR	*dns_rr_copy(record)
24/*	DNS_RR	*record;
25/*
26/*	DNS_RR	*dns_rr_append(list, record)
27/*	DNS_RR	*list;
28/*	DNS_RR	*record;
29/*
30/*	DNS_RR	*dns_rr_sort(list, compar)
31/*	DNS_RR	*list
32/*	int	(*compar)(DNS_RR *, DNS_RR *);
33/*
34/*	int	dns_rr_compare_pref_ipv6(DNS_RR *a, DNS_RR *b)
35/*	DNS_RR	*list
36/*	DNS_RR	*list
37/*
38/*	int	dns_rr_compare_pref_ipv4(DNS_RR *a, DNS_RR *b)
39/*	DNS_RR	*list
40/*	DNS_RR	*list
41/*
42/*	int	dns_rr_compare_pref_any(DNS_RR *a, DNS_RR *b)
43/*	DNS_RR	*list
44/*	DNS_RR	*list
45/*
46/*	DNS_RR	*dns_rr_shuffle(list)
47/*	DNS_RR	*list;
48/*
49/*	DNS_RR	*dns_rr_remove(list, record)
50/*	DNS_RR	*list;
51/*	DNS_RR	*record;
52/* DESCRIPTION
53/*	The routines in this module maintain memory for DNS resource record
54/*	information, and maintain lists of DNS resource records.
55/*
56/*	dns_rr_create() creates and initializes one resource record.
57/*	The \fIqname\fR field specifies the query name.
58/*	The \fIrname\fR field specifies the reply name.
59/*	\fIpreference\fR is used for MX records; \fIdata\fR is a null
60/*	pointer or specifies optional resource-specific data;
61/*	\fIdata_len\fR is the amount of resource-specific data.
62/*
63/*	dns_rr_free() releases the resource used by of zero or more
64/*	resource records.
65/*
66/*	dns_rr_copy() makes a copy of a resource record.
67/*
68/*	dns_rr_append() appends a resource record to a (list of) resource
69/*	record(s).
70/*	A null input list is explicitly allowed.
71/*
72/*	dns_rr_sort() sorts a list of resource records into ascending
73/*	order according to a user-specified criterion. The result is the
74/*	sorted list.
75/*
76/*	dns_rr_compare_pref_XXX() are dns_rr_sort() helpers to sort
77/*	records by their MX preference and by their address family.
78/*
79/*	dns_rr_shuffle() randomly permutes a list of resource records.
80/*
81/*	dns_rr_remove() removes the specified record from the specified list.
82/*	The updated list is the result value.
83/*	The record MUST be a list member.
84/* LICENSE
85/* .ad
86/* .fi
87/*	The Secure Mailer license must be distributed with this software.
88/* AUTHOR(S)
89/*	Wietse Venema
90/*	IBM T.J. Watson Research
91/*	P.O. Box 704
92/*	Yorktown Heights, NY 10598, USA
93/*--*/
94
95/* System library. */
96
97#include <sys_defs.h>
98#include <string.h>
99#include <stdlib.h>
100
101/* Utility library. */
102
103#include <msg.h>
104#include <mymalloc.h>
105#include <myrand.h>
106
107/* DNS library. */
108
109#include "dns.h"
110
111/* dns_rr_create - fill in resource record structure */
112
113DNS_RR *dns_rr_create(const char *qname, const char *rname,
114		              ushort type, ushort class,
115		              unsigned int ttl, unsigned pref,
116		              const char *data, size_t data_len)
117{
118    DNS_RR *rr;
119
120    rr = (DNS_RR *) mymalloc(sizeof(*rr) + data_len - 1);
121    rr->qname = mystrdup(qname);
122    rr->rname = mystrdup(rname);
123    rr->type = type;
124    rr->class = class;
125    rr->ttl = ttl;
126    rr->dnssec_valid = 0;
127    rr->pref = pref;
128    if (data && data_len > 0)
129	memcpy(rr->data, data, data_len);
130    rr->data_len = data_len;
131    rr->next = 0;
132    return (rr);
133}
134
135/* dns_rr_free - destroy resource record structure */
136
137void    dns_rr_free(DNS_RR *rr)
138{
139    if (rr) {
140	if (rr->next)
141	    dns_rr_free(rr->next);
142	myfree(rr->qname);
143	myfree(rr->rname);
144	myfree((char *) rr);
145    }
146}
147
148/* dns_rr_copy - copy resource record */
149
150DNS_RR *dns_rr_copy(DNS_RR *src)
151{
152    ssize_t len = sizeof(*src) + src->data_len - 1;
153    DNS_RR *dst;
154
155    /*
156     * Combine struct assignment and data copy in one block copy operation.
157     */
158    dst = (DNS_RR *) mymalloc(len);
159    memcpy((char *) dst, (char *) src, len);
160    dst->qname = mystrdup(src->qname);
161    dst->rname = mystrdup(src->rname);
162    dst->next = 0;
163    return (dst);
164}
165
166/* dns_rr_append - append resource record to list */
167
168DNS_RR *dns_rr_append(DNS_RR *list, DNS_RR *rr)
169{
170    if (list == 0) {
171	list = rr;
172    } else {
173	list->next = dns_rr_append(list->next, rr);
174    }
175    return (list);
176}
177
178/* dns_rr_compare_pref_ipv6 - compare records by preference, ipv6 preferred */
179
180int     dns_rr_compare_pref_ipv6(DNS_RR *a, DNS_RR *b)
181{
182    if (a->pref != b->pref)
183	return (a->pref - b->pref);
184#ifdef HAS_IPV6
185    if (a->type == b->type)			/* 200412 */
186	return 0;
187    if (a->type == T_AAAA)
188	return (-1);
189    if (b->type == T_AAAA)
190	return (+1);
191#endif
192    return 0;
193}
194
195/* dns_rr_compare_pref_ipv4 - compare records by preference, ipv4 preferred */
196
197int     dns_rr_compare_pref_ipv4(DNS_RR *a, DNS_RR *b)
198{
199    if (a->pref != b->pref)
200	return (a->pref - b->pref);
201#ifdef HAS_IPV6
202    if (a->type == b->type)
203	return 0;
204    if (a->type == T_AAAA)
205	return (+1);
206    if (b->type == T_AAAA)
207	return (-1);
208#endif
209    return 0;
210}
211
212/* dns_rr_compare_pref_any - compare records by preference, protocol-neutral */
213
214int     dns_rr_compare_pref_any(DNS_RR *a, DNS_RR *b)
215{
216    if (a->pref != b->pref)
217	return (a->pref - b->pref);
218    return 0;
219}
220
221/* dns_rr_compare_pref - binary compatibility helper after name change */
222
223int     dns_rr_compare_pref(DNS_RR *a, DNS_RR *b)
224{
225    return (dns_rr_compare_pref_ipv6(a, b));
226}
227
228/* dns_rr_sort_callback - glue function */
229
230static int (*dns_rr_sort_user) (DNS_RR *, DNS_RR *);
231
232static int dns_rr_sort_callback(const void *a, const void *b)
233{
234    DNS_RR *aa = *(DNS_RR **) a;
235    DNS_RR *bb = *(DNS_RR **) b;
236
237    return (dns_rr_sort_user(aa, bb));
238}
239
240/* dns_rr_sort - sort resource record list */
241
242DNS_RR *dns_rr_sort(DNS_RR *list, int (*compar) (DNS_RR *, DNS_RR *))
243{
244    int     (*saved_user) (DNS_RR *, DNS_RR *);
245    DNS_RR **rr_array;
246    DNS_RR *rr;
247    int     len;
248    int     i;
249
250    /*
251     * Save state and initialize.
252     */
253    saved_user = dns_rr_sort_user;
254    dns_rr_sort_user = compar;
255
256    /*
257     * Build linear array with pointers to each list element.
258     */
259    for (len = 0, rr = list; rr != 0; len++, rr = rr->next)
260	 /* void */ ;
261    rr_array = (DNS_RR **) mymalloc(len * sizeof(*rr_array));
262    for (len = 0, rr = list; rr != 0; len++, rr = rr->next)
263	rr_array[len] = rr;
264
265    /*
266     * Sort by user-specified criterion.
267     */
268    qsort((char *) rr_array, len, sizeof(*rr_array), dns_rr_sort_callback);
269
270    /*
271     * Fix the links.
272     */
273    for (i = 0; i < len - 1; i++)
274	rr_array[i]->next = rr_array[i + 1];
275    rr_array[i]->next = 0;
276    list = rr_array[0];
277
278    /*
279     * Cleanup.
280     */
281    myfree((char *) rr_array);
282    dns_rr_sort_user = saved_user;
283    return (list);
284}
285
286/* dns_rr_shuffle - shuffle resource record list */
287
288DNS_RR *dns_rr_shuffle(DNS_RR *list)
289{
290    DNS_RR **rr_array;
291    DNS_RR *rr;
292    int     len;
293    int     i;
294    int     r;
295
296    /*
297     * Build linear array with pointers to each list element.
298     */
299    for (len = 0, rr = list; rr != 0; len++, rr = rr->next)
300	 /* void */ ;
301    rr_array = (DNS_RR **) mymalloc(len * sizeof(*rr_array));
302    for (len = 0, rr = list; rr != 0; len++, rr = rr->next)
303	rr_array[len] = rr;
304
305    /*
306     * Shuffle resource records. Every element has an equal chance of landing
307     * in slot 0.  After that every remaining element has an equal chance of
308     * landing in slot 1, ...  This is exactly n! states for n! permutations.
309     */
310    for (i = 0; i < len - 1; i++) {
311	r = i + (myrand() % (len - i));		/* Victor&Son */
312	rr = rr_array[i];
313	rr_array[i] = rr_array[r];
314	rr_array[r] = rr;
315    }
316
317    /*
318     * Fix the links.
319     */
320    for (i = 0; i < len - 1; i++)
321	rr_array[i]->next = rr_array[i + 1];
322    rr_array[i]->next = 0;
323    list = rr_array[0];
324
325    /*
326     * Cleanup.
327     */
328    myfree((char *) rr_array);
329    return (list);
330}
331
332/* dns_rr_remove - remove record from list, return new list */
333
334DNS_RR *dns_rr_remove(DNS_RR *list, DNS_RR *record)
335{
336    if (list == 0)
337	msg_panic("dns_rr_remove: record not found");
338
339    if (list == record) {
340	list = record->next;
341	record->next = 0;
342	dns_rr_free(record);
343    } else {
344	list->next = dns_rr_remove(list->next, record);
345    }
346    return (list);
347}
348