]> CyberLeo.Net >> Repos - FreeBSD/stable/9.git/blob - contrib/bind9/lib/dns/diff.c
MFC r363988:
[FreeBSD/stable/9.git] / contrib / bind9 / lib / dns / diff.c
1 /*
2  * Copyright (C) 2004, 2005, 2007-2009, 2011, 2013-2015  Internet Systems Consortium, Inc. ("ISC")
3  * Copyright (C) 2000-2003  Internet Software Consortium.
4  *
5  * Permission to use, copy, modify, and/or distribute this software for any
6  * purpose with or without fee is hereby granted, provided that the above
7  * copyright notice and this permission notice appear in all copies.
8  *
9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
10  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
11  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
12  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
13  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
14  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
15  * PERFORMANCE OF THIS SOFTWARE.
16  */
17
18 /* $Id: diff.c,v 1.26 2011/03/25 23:53:02 each Exp $ */
19
20 /*! \file */
21
22 #include <config.h>
23
24 #include <stdlib.h>
25
26 #include <isc/buffer.h>
27 #include <isc/file.h>
28 #include <isc/mem.h>
29 #include <isc/print.h>
30 #include <isc/string.h>
31 #include <isc/util.h>
32
33 #include <dns/db.h>
34 #include <dns/diff.h>
35 #include <dns/log.h>
36 #include <dns/rdataclass.h>
37 #include <dns/rdatalist.h>
38 #include <dns/rdataset.h>
39 #include <dns/rdatastruct.h>
40 #include <dns/rdatatype.h>
41 #include <dns/result.h>
42
43 #define CHECK(op) \
44         do { result = (op);                                     \
45                 if (result != ISC_R_SUCCESS) goto failure;      \
46         } while (0)
47
48 #define DIFF_COMMON_LOGARGS \
49         dns_lctx, DNS_LOGCATEGORY_GENERAL, DNS_LOGMODULE_DIFF
50
51 static dns_rdatatype_t
52 rdata_covers(dns_rdata_t *rdata) {
53         return (rdata->type == dns_rdatatype_rrsig ?
54                 dns_rdata_covers(rdata) : 0);
55 }
56
57 isc_result_t
58 dns_difftuple_create(isc_mem_t *mctx,
59                      dns_diffop_t op, dns_name_t *name, dns_ttl_t ttl,
60                      dns_rdata_t *rdata, dns_difftuple_t **tp)
61 {
62         dns_difftuple_t *t;
63         unsigned int size;
64         unsigned char *datap;
65
66         REQUIRE(tp != NULL && *tp == NULL);
67
68         /*
69          * Create a new tuple.  The variable-size wire-format name data and
70          * rdata immediately follow the dns_difftuple_t structure
71          * in memory.
72          */
73         size = sizeof(*t) + name->length + rdata->length;
74         t = isc_mem_allocate(mctx, size);
75         if (t == NULL)
76                 return (ISC_R_NOMEMORY);
77         t->mctx = NULL;
78         isc_mem_attach(mctx, &t->mctx);
79         t->op = op;
80
81         datap = (unsigned char *)(t + 1);
82
83         memmove(datap, name->ndata, name->length);
84         dns_name_init(&t->name, NULL);
85         dns_name_clone(name, &t->name);
86         t->name.ndata = datap;
87         datap += name->length;
88
89         t->ttl = ttl;
90
91         memmove(datap, rdata->data, rdata->length);
92         dns_rdata_init(&t->rdata);
93         dns_rdata_clone(rdata, &t->rdata);
94         t->rdata.data = datap;
95         datap += rdata->length;
96
97         ISC_LINK_INIT(&t->rdata, link);
98         ISC_LINK_INIT(t, link);
99         t->magic = DNS_DIFFTUPLE_MAGIC;
100
101         INSIST(datap == (unsigned char *)t + size);
102
103         *tp = t;
104         return (ISC_R_SUCCESS);
105 }
106
107 void
108 dns_difftuple_free(dns_difftuple_t **tp) {
109         dns_difftuple_t *t = *tp;
110         isc_mem_t *mctx;
111
112         REQUIRE(DNS_DIFFTUPLE_VALID(t));
113
114         dns_name_invalidate(&t->name);
115         t->magic = 0;
116         mctx = t->mctx;
117         isc_mem_free(mctx, t);
118         isc_mem_detach(&mctx);
119         *tp = NULL;
120 }
121
122 isc_result_t
123 dns_difftuple_copy(dns_difftuple_t *orig, dns_difftuple_t **copyp) {
124         return (dns_difftuple_create(orig->mctx, orig->op, &orig->name,
125                                      orig->ttl, &orig->rdata, copyp));
126 }
127
128 void
129 dns_diff_init(isc_mem_t *mctx, dns_diff_t *diff) {
130         diff->mctx = mctx;
131         diff->resign = 0;
132         ISC_LIST_INIT(diff->tuples);
133         diff->magic = DNS_DIFF_MAGIC;
134 }
135
136 void
137 dns_diff_clear(dns_diff_t *diff) {
138         dns_difftuple_t *t;
139         REQUIRE(DNS_DIFF_VALID(diff));
140         while ((t = ISC_LIST_HEAD(diff->tuples)) != NULL) {
141                 ISC_LIST_UNLINK(diff->tuples, t, link);
142                 dns_difftuple_free(&t);
143         }
144         ENSURE(ISC_LIST_EMPTY(diff->tuples));
145 }
146
147 void
148 dns_diff_append(dns_diff_t *diff, dns_difftuple_t **tuplep)
149 {
150         ISC_LIST_APPEND(diff->tuples, *tuplep, link);
151         *tuplep = NULL;
152 }
153
154 /* XXX this is O(N) */
155
156 void
157 dns_diff_appendminimal(dns_diff_t *diff, dns_difftuple_t **tuplep)
158 {
159         dns_difftuple_t *ot, *next_ot;
160
161         REQUIRE(DNS_DIFF_VALID(diff));
162         REQUIRE(DNS_DIFFTUPLE_VALID(*tuplep));
163
164         /*
165          * Look for an existing tuple with the same owner name,
166          * rdata, and TTL.   If we are doing an addition and find a
167          * deletion or vice versa, remove both the old and the
168          * new tuple since they cancel each other out (assuming
169          * that we never delete nonexistent data or add existing
170          * data).
171          *
172          * If we find an old update of the same kind as
173          * the one we are doing, there must be a programming
174          * error.  We report it but try to continue anyway.
175          */
176         for (ot = ISC_LIST_HEAD(diff->tuples); ot != NULL;
177              ot = next_ot)
178         {
179                 next_ot = ISC_LIST_NEXT(ot, link);
180                 if (dns_name_equal(&ot->name, &(*tuplep)->name) &&
181                     dns_rdata_compare(&ot->rdata, &(*tuplep)->rdata) == 0 &&
182                     ot->ttl == (*tuplep)->ttl)
183                 {
184                         ISC_LIST_UNLINK(diff->tuples, ot, link);
185                         if ((*tuplep)->op == ot->op) {
186                                 UNEXPECTED_ERROR(__FILE__, __LINE__,
187                                          "unexpected non-minimal diff");
188                         } else {
189                                 dns_difftuple_free(tuplep);
190                         }
191                         dns_difftuple_free(&ot);
192                         break;
193                 }
194         }
195
196         if (*tuplep != NULL) {
197                 ISC_LIST_APPEND(diff->tuples, *tuplep, link);
198                 *tuplep = NULL;
199         }
200
201         ENSURE(*tuplep == NULL);
202 }
203
204 static isc_stdtime_t
205 setresign(dns_rdataset_t *modified, isc_uint32_t delta) {
206         dns_rdata_t rdata = DNS_RDATA_INIT;
207         dns_rdata_rrsig_t sig;
208         isc_stdtime_t when;
209         isc_result_t result;
210
211         result = dns_rdataset_first(modified);
212         INSIST(result == ISC_R_SUCCESS);
213         dns_rdataset_current(modified, &rdata);
214         (void)dns_rdata_tostruct(&rdata, &sig, NULL);
215         if ((rdata.flags & DNS_RDATA_OFFLINE) != 0)
216                 when = 0;
217         else
218                 when = sig.timeexpire - delta;
219         dns_rdata_reset(&rdata);
220
221         result = dns_rdataset_next(modified);
222         while (result == ISC_R_SUCCESS) {
223                 dns_rdataset_current(modified, &rdata);
224                 (void)dns_rdata_tostruct(&rdata, &sig, NULL);
225                 if ((rdata.flags & DNS_RDATA_OFFLINE) != 0) {
226                         goto next_rr;
227                 }
228                 if (when == 0 || sig.timeexpire - delta < when)
229                         when = sig.timeexpire - delta;
230  next_rr:
231                 dns_rdata_reset(&rdata);
232                 result = dns_rdataset_next(modified);
233         }
234         INSIST(result == ISC_R_NOMORE);
235         return (when);
236 }
237
238 static isc_result_t
239 diff_apply(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver,
240            isc_boolean_t warn)
241 {
242         dns_difftuple_t *t;
243         dns_dbnode_t *node = NULL;
244         isc_result_t result;
245         char namebuf[DNS_NAME_FORMATSIZE];
246         char typebuf[DNS_RDATATYPE_FORMATSIZE];
247         char classbuf[DNS_RDATACLASS_FORMATSIZE];
248
249         REQUIRE(DNS_DIFF_VALID(diff));
250         REQUIRE(DNS_DB_VALID(db));
251
252         t = ISC_LIST_HEAD(diff->tuples);
253         while (t != NULL) {
254                 dns_name_t *name;
255
256                 INSIST(node == NULL);
257                 name = &t->name;
258                 /*
259                  * Find the node.
260                  * We create the node if it does not exist.
261                  * This will cause an empty node to be created if the diff
262                  * contains a deletion of an RR at a nonexistent name,
263                  * but such diffs should never be created in the first
264                  * place.
265                  */
266
267                 while (t != NULL && dns_name_equal(&t->name, name)) {
268                         dns_rdatatype_t type, covers;
269                         dns_diffop_t op;
270                         dns_rdatalist_t rdl;
271                         dns_rdataset_t rds;
272                         dns_rdataset_t ardataset;
273                         dns_rdataset_t *modified = NULL;
274
275                         op = t->op;
276                         type = t->rdata.type;
277                         covers = rdata_covers(&t->rdata);
278
279                         /*
280                          * Collect a contiguous set of updates with
281                          * the same operation (add/delete) and RR type
282                          * into a single rdatalist so that the
283                          * database rrset merging/subtraction code
284                          * can work more efficiently than if each
285                          * RR were merged into / subtracted from
286                          * the database separately.
287                          *
288                          * This is done by linking rdata structures from the
289                          * diff into "rdatalist".  This uses the rdata link
290                          * field, not the diff link field, so the structure
291                          * of the diff itself is not affected.
292                          */
293
294                         dns_rdatalist_init(&rdl);
295                         rdl.type = type;
296                         rdl.covers = covers;
297                         rdl.rdclass = t->rdata.rdclass;
298                         rdl.ttl = t->ttl;
299
300                         node = NULL;
301                         if (type != dns_rdatatype_nsec3 &&
302                             covers != dns_rdatatype_nsec3)
303                                 CHECK(dns_db_findnode(db, name, ISC_TRUE,
304                                                       &node));
305                         else
306                                 CHECK(dns_db_findnsec3node(db, name, ISC_TRUE,
307                                                            &node));
308
309                         while (t != NULL &&
310                                dns_name_equal(&t->name, name) &&
311                                t->op == op &&
312                                t->rdata.type == type &&
313                                rdata_covers(&t->rdata) == covers)
314                         {
315                                 dns_name_format(name, namebuf, sizeof(namebuf));
316                                 dns_rdatatype_format(t->rdata.type, typebuf,
317                                                      sizeof(typebuf));
318                                 dns_rdataclass_format(t->rdata.rdclass,
319                                                       classbuf,
320                                                       sizeof(classbuf));
321                                 if (t->ttl != rdl.ttl && warn)
322                                         isc_log_write(DIFF_COMMON_LOGARGS,
323                                                 ISC_LOG_WARNING,
324                                                 "'%s/%s/%s': TTL differs in "
325                                                 "rdataset, adjusting "
326                                                 "%lu -> %lu",
327                                                 namebuf, typebuf, classbuf,
328                                                 (unsigned long) t->ttl,
329                                                 (unsigned long) rdl.ttl);
330                                 ISC_LIST_APPEND(rdl.rdata, &t->rdata, link);
331                                 t = ISC_LIST_NEXT(t, link);
332                         }
333
334                         /*
335                          * Convert the rdatalist into a rdataset.
336                          */
337                         dns_rdataset_init(&rds);
338                         CHECK(dns_rdatalist_tordataset(&rdl, &rds));
339                         if (rds.type == dns_rdatatype_rrsig)
340                                 switch (op) {
341                                 case DNS_DIFFOP_ADDRESIGN:
342                                 case DNS_DIFFOP_DELRESIGN:
343                                         modified = &ardataset;
344                                         dns_rdataset_init(modified);
345                                         break;
346                                 default:
347                                         break;
348                                 }
349                         rds.trust = dns_trust_ultimate;
350
351                         /*
352                          * Merge the rdataset into the database.
353                          */
354                         switch (op) {
355                         case DNS_DIFFOP_ADD:
356                         case DNS_DIFFOP_ADDRESIGN:
357                                 result = dns_db_addrdataset(db, node, ver,
358                                                             0, &rds,
359                                                             DNS_DBADD_MERGE|
360                                                             DNS_DBADD_EXACT|
361                                                             DNS_DBADD_EXACTTTL,
362                                                             modified);
363                                 break;
364                         case DNS_DIFFOP_DEL:
365                         case DNS_DIFFOP_DELRESIGN:
366                                 result = dns_db_subtractrdataset(db, node, ver,
367                                                                &rds,
368                                                                DNS_DBSUB_EXACT,
369                                                                modified);
370                                 break;
371                         default:
372                                 INSIST(0);
373                         }
374
375                         if (result == ISC_R_SUCCESS) {
376                                 if (modified != NULL) {
377                                         isc_stdtime_t resign;
378                                         resign = setresign(modified,
379                                                            diff->resign);
380                                         dns_db_setsigningtime(db, modified,
381                                                               resign);
382                                 }
383                         } else if (result == DNS_R_UNCHANGED) {
384                                 /*
385                                  * This will not happen when executing a
386                                  * dynamic update, because that code will
387                                  * generate strictly minimal diffs.
388                                  * It may happen when receiving an IXFR
389                                  * from a server that is not as careful.
390                                  * Issue a warning and continue.
391                                  */
392                                 if (warn) {
393                                         dns_name_format(dns_db_origin(db),
394                                                         namebuf,
395                                                         sizeof(namebuf));
396                                         dns_rdataclass_format(dns_db_class(db),
397                                                               classbuf,
398                                                               sizeof(classbuf));
399                                         isc_log_write(DIFF_COMMON_LOGARGS,
400                                                       ISC_LOG_WARNING,
401                                                       "%s/%s: dns_diff_apply: "
402                                                       "update with no effect",
403                                                       namebuf, classbuf);
404                                 }
405                         } else if (result == DNS_R_NXRRSET) {
406                                 /*
407                                  * OK.
408                                  */
409                         } else {
410                                 if (modified != NULL &&
411                                     dns_rdataset_isassociated(modified))
412                                         dns_rdataset_disassociate(modified);
413                                 CHECK(result);
414                         }
415                         dns_db_detachnode(db, &node);
416                         if (modified != NULL &&
417                             dns_rdataset_isassociated(modified))
418                                 dns_rdataset_disassociate(modified);
419                 }
420         }
421         return (ISC_R_SUCCESS);
422
423  failure:
424         if (node != NULL)
425                 dns_db_detachnode(db, &node);
426         return (result);
427 }
428
429 isc_result_t
430 dns_diff_apply(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver) {
431         return (diff_apply(diff, db, ver, ISC_TRUE));
432 }
433
434 isc_result_t
435 dns_diff_applysilently(dns_diff_t *diff, dns_db_t *db, dns_dbversion_t *ver) {
436         return (diff_apply(diff, db, ver, ISC_FALSE));
437 }
438
439 /* XXX this duplicates lots of code in diff_apply(). */
440
441 isc_result_t
442 dns_diff_load(dns_diff_t *diff, dns_addrdatasetfunc_t addfunc,
443               void *add_private)
444 {
445         dns_difftuple_t *t;
446         isc_result_t result;
447
448         REQUIRE(DNS_DIFF_VALID(diff));
449
450         t = ISC_LIST_HEAD(diff->tuples);
451         while (t != NULL) {
452                 dns_name_t *name;
453
454                 name = &t->name;
455                 while (t != NULL && dns_name_equal(&t->name, name)) {
456                         dns_rdatatype_t type, covers;
457                         dns_diffop_t op;
458                         dns_rdatalist_t rdl;
459                         dns_rdataset_t rds;
460
461                         op = t->op;
462                         type = t->rdata.type;
463                         covers = rdata_covers(&t->rdata);
464
465                         dns_rdatalist_init(&rdl);
466                         rdl.type = type;
467                         rdl.covers = covers;
468                         rdl.rdclass = t->rdata.rdclass;
469                         rdl.ttl = t->ttl;
470
471                         while (t != NULL && dns_name_equal(&t->name, name) &&
472                                t->op == op && t->rdata.type == type &&
473                                rdata_covers(&t->rdata) == covers)
474                         {
475                                 ISC_LIST_APPEND(rdl.rdata, &t->rdata, link);
476                                 t = ISC_LIST_NEXT(t, link);
477                         }
478
479                         /*
480                          * Convert the rdatalist into a rdataset.
481                          */
482                         dns_rdataset_init(&rds);
483                         CHECK(dns_rdatalist_tordataset(&rdl, &rds));
484                         rds.trust = dns_trust_ultimate;
485
486                         INSIST(op == DNS_DIFFOP_ADD);
487                         result = (*addfunc)(add_private, name, &rds);
488                         if (result == DNS_R_UNCHANGED) {
489                                 isc_log_write(DIFF_COMMON_LOGARGS,
490                                               ISC_LOG_WARNING,
491                                               "dns_diff_load: "
492                                               "update with no effect");
493                         } else if (result == ISC_R_SUCCESS ||
494                                    result == DNS_R_NXRRSET) {
495                                 /*
496                                  * OK.
497                                  */
498                         } else {
499                                 CHECK(result);
500                         }
501                 }
502         }
503         result = ISC_R_SUCCESS;
504  failure:
505         return (result);
506 }
507
508 /*
509  * XXX uses qsort(); a merge sort would be more natural for lists,
510  * and perhaps safer wrt thread stack overflow.
511  */
512 isc_result_t
513 dns_diff_sort(dns_diff_t *diff, dns_diff_compare_func *compare) {
514         unsigned int length = 0;
515         unsigned int i;
516         dns_difftuple_t **v;
517         dns_difftuple_t *p;
518         REQUIRE(DNS_DIFF_VALID(diff));
519
520         for (p = ISC_LIST_HEAD(diff->tuples);
521              p != NULL;
522              p = ISC_LIST_NEXT(p, link))
523                 length++;
524         if (length == 0)
525                 return (ISC_R_SUCCESS);
526         v = isc_mem_get(diff->mctx, length * sizeof(dns_difftuple_t *));
527         if (v == NULL)
528                 return (ISC_R_NOMEMORY);
529         for (i = 0; i < length; i++) {
530                 p = ISC_LIST_HEAD(diff->tuples);
531                 v[i] = p;
532                 ISC_LIST_UNLINK(diff->tuples, p, link);
533         }
534         INSIST(ISC_LIST_HEAD(diff->tuples) == NULL);
535         qsort(v, length, sizeof(v[0]), compare);
536         for (i = 0; i < length; i++) {
537                 ISC_LIST_APPEND(diff->tuples, v[i], link);
538         }
539         isc_mem_put(diff->mctx, v, length * sizeof(dns_difftuple_t *));
540         return (ISC_R_SUCCESS);
541 }
542
543
544 /*
545  * Create an rdataset containing the single RR of the given
546  * tuple.  The caller must allocate the rdata, rdataset and
547  * an rdatalist structure for it to refer to.
548  */
549
550 static isc_result_t
551 diff_tuple_tordataset(dns_difftuple_t *t, dns_rdata_t *rdata,
552                       dns_rdatalist_t *rdl, dns_rdataset_t *rds)
553 {
554         REQUIRE(DNS_DIFFTUPLE_VALID(t));
555         REQUIRE(rdl != NULL);
556         REQUIRE(rds != NULL);
557
558         dns_rdatalist_init(rdl);
559         rdl->type = t->rdata.type;
560         rdl->rdclass = t->rdata.rdclass;
561         rdl->ttl = t->ttl;
562         dns_rdataset_init(rds);
563         ISC_LINK_INIT(rdata, link);
564         dns_rdata_clone(&t->rdata, rdata);
565         ISC_LIST_APPEND(rdl->rdata, rdata, link);
566         return (dns_rdatalist_tordataset(rdl, rds));
567 }
568
569 isc_result_t
570 dns_diff_print(dns_diff_t *diff, FILE *file) {
571         isc_result_t result;
572         dns_difftuple_t *t;
573         char *mem = NULL;
574         unsigned int size = 2048;
575         const char *op = NULL;
576
577         REQUIRE(DNS_DIFF_VALID(diff));
578
579         mem = isc_mem_get(diff->mctx, size);
580         if (mem == NULL)
581                 return (ISC_R_NOMEMORY);
582
583         for (t = ISC_LIST_HEAD(diff->tuples); t != NULL;
584              t = ISC_LIST_NEXT(t, link))
585         {
586                 isc_buffer_t buf;
587                 isc_region_t r;
588
589                 dns_rdatalist_t rdl;
590                 dns_rdataset_t rds;
591                 dns_rdata_t rd = DNS_RDATA_INIT;
592
593                 result = diff_tuple_tordataset(t, &rd, &rdl, &rds);
594                 if (result != ISC_R_SUCCESS) {
595                         UNEXPECTED_ERROR(__FILE__, __LINE__,
596                                          "diff_tuple_tordataset failed: %s",
597                                          dns_result_totext(result));
598                         result =  ISC_R_UNEXPECTED;
599                         goto cleanup;
600                 }
601  again:
602                 isc_buffer_init(&buf, mem, size);
603                 result = dns_rdataset_totext(&rds, &t->name,
604                                              ISC_FALSE, ISC_FALSE, &buf);
605
606                 if (result == ISC_R_NOSPACE) {
607                         isc_mem_put(diff->mctx, mem, size);
608                         size += 1024;
609                         mem = isc_mem_get(diff->mctx, size);
610                         if (mem == NULL) {
611                                 result = ISC_R_NOMEMORY;
612                                 goto cleanup;
613                         }
614                         goto again;
615                 }
616
617                 if (result != ISC_R_SUCCESS)
618                         goto cleanup;
619                 /*
620                  * Get rid of final newline.
621                  */
622                 INSIST(buf.used >= 1 &&
623                        ((char *) buf.base)[buf.used-1] == '\n');
624                 buf.used--;
625
626                 isc_buffer_usedregion(&buf, &r);
627                 switch (t->op) {
628                 case DNS_DIFFOP_EXISTS: op = "exists"; break;
629                 case DNS_DIFFOP_ADD: op = "add"; break;
630                 case DNS_DIFFOP_DEL: op = "del"; break;
631                 case DNS_DIFFOP_ADDRESIGN: op = "add re-sign"; break;
632                 case DNS_DIFFOP_DELRESIGN: op = "del re-sign"; break;
633                 }
634                 if (file != NULL)
635                         fprintf(file, "%s %.*s\n", op, (int) r.length,
636                                 (char *) r.base);
637                 else
638                         isc_log_write(DIFF_COMMON_LOGARGS, ISC_LOG_DEBUG(7),
639                                       "%s %.*s", op, (int) r.length,
640                                       (char *) r.base);
641         }
642         result = ISC_R_SUCCESS;
643  cleanup:
644         if (mem != NULL)
645                 isc_mem_put(diff->mctx, mem, size);
646         return (result);
647 }