contrib/bind-9.3/lib/dns/nsec.c

   1 /*
   2  * Copyright (C) 2004  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1999-2001, 2003  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and 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: nsec.c,v 1.5.2.1 2004/03/08 02:07:55 marka Exp $ */
  19
  20 #include <config.h>
  21
  22 #include <isc/string.h>
  23 #include <isc/util.h>
  24
  25 #include <dns/db.h>
  26 #include <dns/nsec.h>
  27 #include <dns/rdata.h>
  28 #include <dns/rdatalist.h>
  29 #include <dns/rdataset.h>
  30 #include <dns/rdatasetiter.h>
  31 #include <dns/rdatastruct.h>
  32 #include <dns/result.h>
  33
  34 #define RETERR(x) do { \
  35         result = (x); \
  36         if (result != ISC_R_SUCCESS) \
  37                 goto failure; \
  38         } while (0)
  39
  40 static void
  41 set_bit(unsigned char *array, unsigned int index, unsigned int bit) {
  42         unsigned int shift, mask;
  43
  44         shift = 7 - (index % 8);
  45         mask = 1 << shift;
  46
  47         if (bit != 0)
  48                 array[index / 8] |= mask;
  49         else
  50                 array[index / 8] &= (~mask & 0xFF);
  51 }
  52
  53 static unsigned int
  54 bit_isset(unsigned char *array, unsigned int index) {
  55         unsigned int byte, shift, mask;
  56
  57         byte = array[index / 8];
  58         shift = 7 - (index % 8);
  59         mask = 1 << shift;
  60
  61         return ((byte & mask) != 0);
  62 }
  63
  64 isc_result_t
  65 dns_nsec_buildrdata(dns_db_t *db, dns_dbversion_t *version,
  66                     dns_dbnode_t *node, dns_name_t *target,
  67                     unsigned char *buffer, dns_rdata_t *rdata)
  68 {
  69         isc_result_t result;
  70         dns_rdataset_t rdataset;
  71         isc_region_t r;
  72         unsigned int i, window;
  73         int octet;
  74
  75         unsigned char *nsec_bits, *bm;
  76         unsigned int max_type;
  77         dns_rdatasetiter_t *rdsiter;
  78
  79         memset(buffer, 0, DNS_NSEC_BUFFERSIZE);
  80         dns_name_toregion(target, &r);
  81         memcpy(buffer, r.base, r.length);
  82         r.base = buffer;
  83         /*
  84          * Use the end of the space for a raw bitmap leaving enough
  85          * space for the window identifiers and length octets.
  86          */
  87         bm = r.base + r.length + 512;
  88         nsec_bits = r.base + r.length;
  89         set_bit(bm, dns_rdatatype_nsec, 1);
  90         max_type = dns_rdatatype_nsec;
  91         dns_rdataset_init(&rdataset);
  92         rdsiter = NULL;
  93         result = dns_db_allrdatasets(db, node, version, 0, &rdsiter);
  94         if (result != ISC_R_SUCCESS)
  95                 return (result);
  96         for (result = dns_rdatasetiter_first(rdsiter);
  97              result == ISC_R_SUCCESS;
  98              result = dns_rdatasetiter_next(rdsiter))
  99         {
 100                 dns_rdatasetiter_current(rdsiter, &rdataset);
 101                 if (rdataset.type != dns_rdatatype_nsec) {
 102                         if (rdataset.type > max_type)
 103                                 max_type = rdataset.type;
 104                         set_bit(bm, rdataset.type, 1);
 105                 }
 106                 dns_rdataset_disassociate(&rdataset);
 107         }
 108
 109         /*
 110          * At zone cuts, deny the existence of glue in the parent zone.
 111          */
 112         if (bit_isset(bm, dns_rdatatype_ns) &&
 113             ! bit_isset(bm, dns_rdatatype_soa)) {
 114                 for (i = 0; i <= max_type; i++) {
 115                         if (bit_isset(bm, i) &&
 116                             ! dns_rdatatype_iszonecutauth((dns_rdatatype_t)i))
 117                                 set_bit(bm, i, 0);
 118                 }
 119         }
 120
 121         dns_rdatasetiter_destroy(&rdsiter);
 122         if (result != ISC_R_NOMORE)
 123                 return (result);
 124
 125         for (window = 0; window < 256; window++) {
 126                 if (window * 256 > max_type)
 127                         break;
 128                 for (octet = 31; octet >= 0; octet--)
 129                         if (bm[window * 32 + octet] != 0)
 130                                 break;
 131                 if (octet < 0)
 132                         continue;
 133                 nsec_bits[0] = window;
 134                 nsec_bits[1] = octet + 1;
 135                 /*
 136                  * Note: potential overlapping move.
 137                  */
 138                 memmove(&nsec_bits[2], &bm[window * 32], octet + 1);
 139                 nsec_bits += 3 + octet;
 140         }
 141         r.length = nsec_bits - r.base;
 142         INSIST(r.length <= DNS_NSEC_BUFFERSIZE);
 143         dns_rdata_fromregion(rdata,
 144                              dns_db_class(db),
 145                              dns_rdatatype_nsec,
 146                              &r);
 147
 148         return (ISC_R_SUCCESS);
 149 }
 150
 151
 152 isc_result_t
 153 dns_nsec_build(dns_db_t *db, dns_dbversion_t *version, dns_dbnode_t *node,
 154                dns_name_t *target, dns_ttl_t ttl)
 155 {
 156         isc_result_t result;
 157         dns_rdata_t rdata = DNS_RDATA_INIT;
 158         unsigned char data[DNS_NSEC_BUFFERSIZE];
 159         dns_rdatalist_t rdatalist;
 160         dns_rdataset_t rdataset;
 161
 162         dns_rdataset_init(&rdataset);
 163         dns_rdata_init(&rdata);
 164
 165         RETERR(dns_nsec_buildrdata(db, version, node, target, data, &rdata));
 166
 167         rdatalist.rdclass = dns_db_class(db);
 168         rdatalist.type = dns_rdatatype_nsec;
 169         rdatalist.covers = 0;
 170         rdatalist.ttl = ttl;
 171         ISC_LIST_INIT(rdatalist.rdata);
 172         ISC_LIST_APPEND(rdatalist.rdata, &rdata, link);
 173         RETERR(dns_rdatalist_tordataset(&rdatalist, &rdataset));
 174         result = dns_db_addrdataset(db, node, version, 0, &rdataset,
 175                                     0, NULL);
 176         if (result == DNS_R_UNCHANGED)
 177                 result = ISC_R_SUCCESS;
 178         RETERR(result);
 179  failure:
 180         if (dns_rdataset_isassociated(&rdataset))
 181                 dns_rdataset_disassociate(&rdataset);
 182         return (result);
 183 }
 184
 185 isc_boolean_t
 186 dns_nsec_typepresent(dns_rdata_t *nsec, dns_rdatatype_t type) {
 187         dns_rdata_nsec_t nsecstruct;
 188         isc_result_t result;
 189         isc_boolean_t present;
 190         unsigned int i, len, window;
 191
 192         REQUIRE(nsec != NULL);
 193         REQUIRE(nsec->type == dns_rdatatype_nsec);
 194
 195         /* This should never fail */
 196         result = dns_rdata_tostruct(nsec, &nsecstruct, NULL);
 197         INSIST(result == ISC_R_SUCCESS);
 198
 199         present = ISC_FALSE;
 200         for (i = 0; i < nsecstruct.len; i += len) {
 201                 INSIST(i + 2 <= nsecstruct.len);
 202                 window = nsecstruct.typebits[i];
 203                 len = nsecstruct.typebits[i + 1];
 204                 INSIST(len > 0 && len <= 32);
 205                 i += 2;
 206                 INSIST(i + len <= nsecstruct.len);
 207                 if (window * 256 > type)
 208                         break;
 209                 if ((window + 1) * 256 <= type)
 210                         continue;
 211                 if (type < (window * 256) + len * 8)
 212                         present = ISC_TF(bit_isset(&nsecstruct.typebits[i],
 213                                                    type % 256));
 214                 break;
 215         }
 216         dns_rdata_freestruct(&nsec);
 217         return (present);
 218 }