1 /* $NetBSD: dns_rr.c,v 1.3 2023/12/23 20:30:43 christos Exp $ */
2
3 /*++
4 /* NAME
5 /* dns_rr 3
6 /* SUMMARY
7 /* resource record memory and list management
8 /* SYNOPSIS
9 /* #include <dns.h>
10 /*
11 /* DNS_RR *dns_rr_create(qname, rname, type, class, ttl, preference,
12 /* weight, port, data, data_len)
13 /* const char *qname;
14 /* const char *rname;
15 /* unsigned short type;
16 /* unsigned short class;
17 /* unsigned int ttl;
18 /* unsigned preference;
19 /* unsigned weight;
20 /* unsigned port;
21 /* const char *data;
22 /* size_t data_len;
23 /*
24 /* void dns_rr_free(list)
25 /* DNS_RR *list;
26 /*
27 /* DNS_RR *dns_rr_copy(record)
28 /* DNS_RR *record;
29 /*
30 /* DNS_RR *dns_rr_append(list, record)
31 /* DNS_RR *list;
32 /* DNS_RR *record;
33 /*
34 /* DNS_RR *dns_rr_sort(list, compar)
35 /* DNS_RR *list
36 /* int (*compar)(DNS_RR *, DNS_RR *);
37 /*
38 /* int dns_rr_compare_pref_ipv6(DNS_RR *a, DNS_RR *b)
39 /* DNS_RR *list
40 /* DNS_RR *list
41 /*
42 /* int dns_rr_compare_pref_ipv4(DNS_RR *a, DNS_RR *b)
43 /* DNS_RR *list
44 /* DNS_RR *list
45 /*
46 /* int dns_rr_compare_pref_any(DNS_RR *a, DNS_RR *b)
47 /* DNS_RR *list
48 /* DNS_RR *list
49 /*
50 /* DNS_RR *dns_rr_shuffle(list)
51 /* DNS_RR *list;
52 /*
53 /* DNS_RR *dns_rr_remove(list, record)
54 /* DNS_RR *list;
55 /* DNS_RR *record;
56 /*
57 /* DNS_RR *dns_srv_rr_sort(list)
58 /* DNS_RR *list;
59 /* AUXILIARY FUNCTIONS
60 /* DNS_RR *dns_rr_create_nopref(qname, rname, type, class, ttl,
61 /* data, data_len)
62 /* const char *qname;
63 /* const char *rname;
64 /* unsigned short type;
65 /* unsigned short class;
66 /* unsigned int ttl;
67 /* const char *data;
68 /* size_t data_len;
69 /*
70 /* DNS_RR *dns_rr_create_noport(qname, rname, type, class, ttl,
71 /* preference, data, data_len)
72 /* const char *qname;
73 /* const char *rname;
74 /* unsigned short type;
75 /* unsigned short class;
76 /* unsigned int ttl;
77 /* unsigned preference;
78 /* const char *data;
79 /* size_t data_len;
80 /* DESCRIPTION
81 /* The routines in this module maintain memory for DNS resource record
82 /* information, and maintain lists of DNS resource records.
83 /*
84 /* dns_rr_create() creates and initializes one resource record.
85 /* The \fIqname\fR field specifies the query name.
86 /* The \fIrname\fR field specifies the reply name.
87 /* \fIpreference\fR is used for MX and SRV records; \fIweight\fR
88 /* and \fIport\fR are used for SRV records; \fIdata\fR is a null
89 /* pointer or specifies optional resource-specific data;
90 /* \fIdata_len\fR is the amount of resource-specific data.
91 /*
92 /* dns_rr_create_nopref() and dns_rr_create_noport() are convenience
93 /* wrappers around dns_rr_create() that take fewer arguments.
94 /*
95 /* dns_rr_free() releases the resource used by of zero or more
96 /* resource records.
97 /*
98 /* dns_rr_copy() makes a copy of a resource record.
99 /*
100 /* dns_rr_append() appends a resource record to a (list of) resource
101 /* record(s).
102 /* A null input list is explicitly allowed.
103 /*
104 /* dns_rr_sort() sorts a list of resource records into ascending
105 /* order according to a user-specified criterion. The result is the
106 /* sorted list.
107 /*
108 /* dns_rr_compare_pref_XXX() are dns_rr_sort() helpers to sort
109 /* records by their MX preference and by their address family.
110 /*
111 /* dns_rr_shuffle() randomly permutes a list of resource records.
112 /*
113 /* dns_rr_remove() removes the specified record from the specified list.
114 /* The updated list is the result value.
115 /* The record MUST be a list member.
116 /*
117 /* dns_srv_rr_sort() sorts a list of SRV records according to
118 /* their priority and weight as described in RFC 2782.
119 /* LICENSE
120 /* .ad
121 /* .fi
122 /* The Secure Mailer license must be distributed with this software.
123 /* AUTHOR(S)
124 /* Wietse Venema
125 /* IBM T.J. Watson Research
126 /* P.O. Box 704
127 /* Yorktown Heights, NY 10598, USA
128 /*
129 /* Wietse Venema
130 /* Google, Inc.
131 /* 111 8th Avenue
132 /* New York, NY 10011, USA
133 /*
134 /* SRV Support by
135 /* Tomas Korbar
136 /* Red Hat, Inc.
137 /*--*/
138
139 /* System library. */
140
141 #include <sys_defs.h>
142 #include <string.h>
143 #include <stdlib.h>
144
145 /* Utility library. */
146
147 #include <msg.h>
148 #include <mymalloc.h>
149 #include <myrand.h>
150
151 /* DNS library. */
152
153 #include "dns.h"
154
155 /* dns_rr_create - fill in resource record structure */
156
dns_rr_create(const char * qname,const char * rname,ushort type,ushort class,unsigned int ttl,unsigned pref,unsigned weight,unsigned port,const char * data,size_t data_len)157 DNS_RR *dns_rr_create(const char *qname, const char *rname,
158 ushort type, ushort class,
159 unsigned int ttl, unsigned pref,
160 unsigned weight, unsigned port,
161 const char *data, size_t data_len)
162 {
163 DNS_RR *rr;
164
165 /*
166 * Note: if this function is changed, update dns_rr_copy().
167 */
168 rr = (DNS_RR *) mymalloc(sizeof(*rr));
169 rr->qname = mystrdup(qname);
170 rr->rname = mystrdup(rname);
171 rr->type = type;
172 rr->class = class;
173 rr->ttl = ttl;
174 rr->dnssec_valid = 0;
175 rr->pref = pref;
176 rr->weight = weight;
177 rr->port = port;
178 if (data_len != 0) {
179 rr->data = mymalloc(data_len);
180 memcpy(rr->data, data, data_len);
181 } else {
182 rr->data = 0;
183 }
184 rr->data_len = data_len;
185 rr->next = 0;
186 return (rr);
187 }
188
189 /* dns_rr_free - destroy resource record structure */
190
dns_rr_free(DNS_RR * rr)191 void dns_rr_free(DNS_RR *rr)
192 {
193 if (rr) {
194 if (rr->next)
195 dns_rr_free(rr->next);
196 myfree(rr->qname);
197 myfree(rr->rname);
198 if (rr->data)
199 myfree(rr->data);
200 myfree((void *) rr);
201 }
202 }
203
204 /* dns_rr_copy - copy resource record */
205
dns_rr_copy(DNS_RR * src)206 DNS_RR *dns_rr_copy(DNS_RR *src)
207 {
208 DNS_RR *dst;
209
210 /*
211 * Note: struct copy, because dns_rr_create() would not copy all fields.
212 */
213 dst = (DNS_RR *) mymalloc(sizeof(*dst));
214 *dst = *src;
215 dst->qname = mystrdup(src->qname);
216 dst->rname = mystrdup(src->rname);
217 if (dst->data)
218 dst->data = mymemdup(src->data, src->data_len);
219 dst->next = 0;
220 return (dst);
221 }
222
223 /* dns_rr_append - append resource record to list */
224
dns_rr_append(DNS_RR * list,DNS_RR * rr)225 DNS_RR *dns_rr_append(DNS_RR *list, DNS_RR *rr)
226 {
227 if (list == 0) {
228 list = rr;
229 } else {
230 list->next = dns_rr_append(list->next, rr);
231 }
232 return (list);
233 }
234
235 /* dns_rr_compare_pref_ipv6 - compare records by preference, ipv6 preferred */
236
dns_rr_compare_pref_ipv6(DNS_RR * a,DNS_RR * b)237 int dns_rr_compare_pref_ipv6(DNS_RR *a, DNS_RR *b)
238 {
239 if (a->pref != b->pref)
240 return (a->pref - b->pref);
241 #ifdef HAS_IPV6
242 if (a->type == b->type) /* 200412 */
243 return 0;
244 if (a->type == T_AAAA)
245 return (-1);
246 if (b->type == T_AAAA)
247 return (+1);
248 #endif
249 return 0;
250 }
251
252 /* dns_rr_compare_pref_ipv4 - compare records by preference, ipv4 preferred */
253
dns_rr_compare_pref_ipv4(DNS_RR * a,DNS_RR * b)254 int dns_rr_compare_pref_ipv4(DNS_RR *a, DNS_RR *b)
255 {
256 if (a->pref != b->pref)
257 return (a->pref - b->pref);
258 #ifdef HAS_IPV6
259 if (a->type == b->type)
260 return 0;
261 if (a->type == T_AAAA)
262 return (+1);
263 if (b->type == T_AAAA)
264 return (-1);
265 #endif
266 return 0;
267 }
268
269 /* dns_rr_compare_pref_any - compare records by preference, protocol-neutral */
270
dns_rr_compare_pref_any(DNS_RR * a,DNS_RR * b)271 int dns_rr_compare_pref_any(DNS_RR *a, DNS_RR *b)
272 {
273 if (a->pref != b->pref)
274 return (a->pref - b->pref);
275 return 0;
276 }
277
278 /* dns_rr_compare_pref - binary compatibility helper after name change */
279
dns_rr_compare_pref(DNS_RR * a,DNS_RR * b)280 int dns_rr_compare_pref(DNS_RR *a, DNS_RR *b)
281 {
282 return (dns_rr_compare_pref_ipv6(a, b));
283 }
284
285 /* dns_rr_sort_callback - glue function */
286
287 static int (*dns_rr_sort_user) (DNS_RR *, DNS_RR *);
288
dns_rr_sort_callback(const void * a,const void * b)289 static int dns_rr_sort_callback(const void *a, const void *b)
290 {
291 DNS_RR *aa = *(DNS_RR **) a;
292 DNS_RR *bb = *(DNS_RR **) b;
293
294 return (dns_rr_sort_user(aa, bb));
295 }
296
297 /* dns_rr_sort - sort resource record list */
298
dns_rr_sort(DNS_RR * list,int (* compar)(DNS_RR *,DNS_RR *))299 DNS_RR *dns_rr_sort(DNS_RR *list, int (*compar) (DNS_RR *, DNS_RR *))
300 {
301 int (*saved_user) (DNS_RR *, DNS_RR *);
302 DNS_RR **rr_array;
303 DNS_RR *rr;
304 int len;
305 int i;
306
307 /*
308 * Avoid mymalloc() panic.
309 */
310 if (list == 0)
311 return (list);
312
313 /*
314 * Save state and initialize.
315 */
316 saved_user = dns_rr_sort_user;
317 dns_rr_sort_user = compar;
318
319 /*
320 * Build linear array with pointers to each list element.
321 */
322 for (len = 0, rr = list; rr != 0; len++, rr = rr->next)
323 /* void */ ;
324 rr_array = (DNS_RR **) mymalloc(len * sizeof(*rr_array));
325 for (len = 0, rr = list; rr != 0; len++, rr = rr->next)
326 rr_array[len] = rr;
327
328 /*
329 * Sort by user-specified criterion.
330 */
331 qsort((void *) rr_array, len, sizeof(*rr_array), dns_rr_sort_callback);
332
333 /*
334 * Fix the links.
335 */
336 for (i = 0; i < len - 1; i++)
337 rr_array[i]->next = rr_array[i + 1];
338 rr_array[i]->next = 0;
339 list = rr_array[0];
340
341 /*
342 * Cleanup.
343 */
344 myfree((void *) rr_array);
345 dns_rr_sort_user = saved_user;
346 return (list);
347 }
348
349 /* dns_rr_shuffle - shuffle resource record list */
350
dns_rr_shuffle(DNS_RR * list)351 DNS_RR *dns_rr_shuffle(DNS_RR *list)
352 {
353 DNS_RR **rr_array;
354 DNS_RR *rr;
355 int len;
356 int i;
357 int r;
358
359 /*
360 * Avoid mymalloc() panic.
361 */
362 if (list == 0)
363 return (list);
364
365 /*
366 * Build linear array with pointers to each list element.
367 */
368 for (len = 0, rr = list; rr != 0; len++, rr = rr->next)
369 /* void */ ;
370 rr_array = (DNS_RR **) mymalloc(len * sizeof(*rr_array));
371 for (len = 0, rr = list; rr != 0; len++, rr = rr->next)
372 rr_array[len] = rr;
373
374 /*
375 * Shuffle resource records. Every element has an equal chance of landing
376 * in slot 0. After that every remaining element has an equal chance of
377 * landing in slot 1, ... This is exactly n! states for n! permutations.
378 */
379 for (i = 0; i < len - 1; i++) {
380 r = i + (myrand() % (len - i)); /* Victor&Son */
381 rr = rr_array[i];
382 rr_array[i] = rr_array[r];
383 rr_array[r] = rr;
384 }
385
386 /*
387 * Fix the links.
388 */
389 for (i = 0; i < len - 1; i++)
390 rr_array[i]->next = rr_array[i + 1];
391 rr_array[i]->next = 0;
392 list = rr_array[0];
393
394 /*
395 * Cleanup.
396 */
397 myfree((void *) rr_array);
398 return (list);
399 }
400
401 /* dns_rr_remove - remove record from list, return new list */
402
dns_rr_remove(DNS_RR * list,DNS_RR * record)403 DNS_RR *dns_rr_remove(DNS_RR *list, DNS_RR *record)
404 {
405 if (list == 0)
406 msg_panic("dns_rr_remove: record not found");
407
408 if (list == record) {
409 list = record->next;
410 record->next = 0;
411 dns_rr_free(record);
412 } else {
413 list->next = dns_rr_remove(list->next, record);
414 }
415 return (list);
416 }
417
418 /* weight_order - sort equal-priority records by weight */
419
weight_order(DNS_RR ** array,int count)420 static void weight_order(DNS_RR **array, int count)
421 {
422 int unordered_weights;
423 int i;
424
425 /*
426 * Compute the sum of record weights. If weights are not supplied then
427 * this function would be a noop. In fact this would be a noop when all
428 * weights have the same value, whether that weight is zero or not. There
429 * is no need to give special treatment to zero weights.
430 */
431 for (unordered_weights = 0, i = 0; i < count; i++)
432 unordered_weights += array[i]->weight;
433 if (unordered_weights == 0)
434 return;
435
436 /*
437 * The record ordering code below differs from RFC 2782 when the input
438 * contains a mix of zero and non-zero weights: the code below does not
439 * give special treatment to zero weights. Instead, it treats a zero
440 * weight just like any other small weight. Fewer special cases make for
441 * code that is simpler and more robust.
442 */
443 for (i = 0; i < count - 1; i++) {
444 int running_sum;
445 int threshold;
446 int k;
447 DNS_RR *temp;
448
449 /*
450 * Choose a random threshold [0..unordered_weights] inclusive.
451 */
452 threshold = myrand() % (unordered_weights + 1);
453
454 /*
455 * Move the first record with running_sum >= threshold to the ordered
456 * list, and update unordered_weights.
457 */
458 for (running_sum = 0, k = i; k < count; k++) {
459 running_sum += array[k]->weight;
460 if (running_sum >= threshold) {
461 unordered_weights -= array[k]->weight;
462 temp = array[i];
463 array[i] = array[k];
464 array[k] = temp;
465 break;
466 }
467 }
468 }
469 }
470
471 /* dns_srv_rr_sort - sort resource record list */
472
dns_srv_rr_sort(DNS_RR * list)473 DNS_RR *dns_srv_rr_sort(DNS_RR *list)
474 {
475 int (*saved_user) (DNS_RR *, DNS_RR *);
476 DNS_RR **rr_array;
477 DNS_RR *rr;
478 int len;
479 int i;
480 int r;
481 int cur_pref;
482 int left_bound; /* inclusive */
483 int right_bound; /* non-inclusive */
484
485 /*
486 * Avoid mymalloc() panic, or rr_array[0] fence-post error.
487 */
488 if (list == 0)
489 return (list);
490
491 /*
492 * Save state and initialize.
493 */
494 saved_user = dns_rr_sort_user;
495 dns_rr_sort_user = dns_rr_compare_pref_any;
496
497 /*
498 * Build linear array with pointers to each list element.
499 */
500 for (len = 0, rr = list; rr != 0; len++, rr = rr->next)
501 /* void */ ;
502 rr_array = (DNS_RR **) mymalloc(len * sizeof(*rr_array));
503 for (len = 0, rr = list; rr != 0; len++, rr = rr->next)
504 rr_array[len] = rr;
505
506 /*
507 * Shuffle resource records. Every element has an equal chance of landing
508 * in slot 0. After that every remaining element has an equal chance of
509 * landing in slot 1, ... This is exactly n! states for n! permutations.
510 */
511 for (i = 0; i < len - 1; i++) {
512 r = i + (myrand() % (len - i)); /* Victor&Son */
513 rr = rr_array[i];
514 rr_array[i] = rr_array[r];
515 rr_array[r] = rr;
516 }
517
518 /* First order the records by preference. */
519 qsort((void *) rr_array, len, sizeof(*rr_array), dns_rr_sort_callback);
520
521 /*
522 * Walk through records and sort the records in every same-preference
523 * partition according to their weight. Note that left_bound is
524 * inclusive, and that right-bound is non-inclusive.
525 */
526 left_bound = 0;
527 cur_pref = rr_array[left_bound]->pref; /* assumes len > 0 */
528
529 for (right_bound = 1; /* see below */ ; right_bound++) {
530 if (right_bound == len || rr_array[right_bound]->pref != cur_pref) {
531 if (right_bound - left_bound > 1)
532 weight_order(rr_array + left_bound, right_bound - left_bound);
533 if (right_bound == len)
534 break;
535 left_bound = right_bound;
536 cur_pref = rr_array[left_bound]->pref;
537 }
538 }
539
540 /*
541 * Fix the links.
542 */
543 for (i = 0; i < len - 1; i++)
544 rr_array[i]->next = rr_array[i + 1];
545 rr_array[i]->next = 0;
546 list = rr_array[0];
547
548 /*
549 * Cleanup.
550 */
551 myfree((void *) rr_array);
552 dns_rr_sort_user = saved_user;
553 return (list);
554 }
555