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