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