contrib/bind-9.2.4rc7/lib/dns/compress.c

   1 /*
   2  * Copyright (C) 2004  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1999-2001  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: compress.c,v 1.50.2.2 2004/03/09 06:11:00 marka Exp $ */
  19
  20 #define DNS_NAME_USEINLINE 1
  21
  22 #include <config.h>
  23
  24 #include <isc/mem.h>
  25 #include <isc/string.h>
  26 #include <isc/util.h>
  27
  28 #include <dns/compress.h>
  29 #include <dns/fixedname.h>
  30 #include <dns/rbt.h>
  31 #include <dns/result.h>
  32
  33 #define CCTX_MAGIC      ISC_MAGIC('C', 'C', 'T', 'X')
  34 #define VALID_CCTX(x)   ISC_MAGIC_VALID(x, CCTX_MAGIC)
  35
  36 #define DCTX_MAGIC      ISC_MAGIC('D', 'C', 'T', 'X')
  37 #define VALID_DCTX(x)   ISC_MAGIC_VALID(x, DCTX_MAGIC)
  38
  39 /***
  40  ***    Compression
  41  ***/
  42
  43 isc_result_t
  44 dns_compress_init(dns_compress_t *cctx, int edns, isc_mem_t *mctx) {
  45         unsigned int i;
  46
  47         REQUIRE(cctx != NULL);
  48         REQUIRE(mctx != NULL);  /* See: rdataset.c:towiresorted(). */
  49
  50         cctx->allowed = 0;
  51         cctx->edns = edns;
  52         for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++)
  53                 cctx->table[i] = NULL;
  54         cctx->mctx = mctx;
  55         cctx->count = 0;
  56         cctx->magic = CCTX_MAGIC;
  57         return (ISC_R_SUCCESS);
  58 }
  59
  60 void
  61 dns_compress_invalidate(dns_compress_t *cctx) {
  62         dns_compressnode_t *node;
  63         unsigned int i;
  64
  65         REQUIRE(VALID_CCTX(cctx));
  66
  67         cctx->magic = 0;
  68         for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) {
  69                 while (cctx->table[i] != NULL) {
  70                         node = cctx->table[i];
  71                         cctx->table[i] = cctx->table[i]->next;
  72                         if (node->count < DNS_COMPRESS_INITIALNODES)
  73                                 continue;
  74                         isc_mem_put(cctx->mctx, node, sizeof(*node));
  75                 }
  76         }
  77         cctx->allowed = 0;
  78         cctx->edns = -1;
  79 }
  80
  81 void
  82 dns_compress_setmethods(dns_compress_t *cctx, unsigned int allowed) {
  83         REQUIRE(VALID_CCTX(cctx));
  84
  85         cctx->allowed = allowed;
  86 }
  87
  88 unsigned int
  89 dns_compress_getmethods(dns_compress_t *cctx) {
  90         REQUIRE(VALID_CCTX(cctx));
  91         return (cctx->allowed);
  92 }
  93
  94 int
  95 dns_compress_getedns(dns_compress_t *cctx) {
  96         REQUIRE(VALID_CCTX(cctx));
  97         return (cctx->edns);
  98 }
  99
 100 #define NODENAME(node, name) \
 101 do { \
 102         (name)->length = (node)->r.length; \
 103         (name)->labels = (node)->labels; \
 104         (name)->ndata = (node)->r.base; \
 105         (name)->attributes = DNS_NAMEATTR_ABSOLUTE; \
 106 } while (0)
 107
 108 /*
 109  * Find the longest match of name in the table.
 110  * If match is found return ISC_TRUE. prefix, suffix and offset are updated.
 111  * If no match is found return ISC_FALSE.
 112  */
 113 isc_boolean_t
 114 dns_compress_findglobal(dns_compress_t *cctx, dns_name_t *name,
 115                         dns_name_t *prefix, isc_uint16_t *offset)
 116 {
 117         dns_name_t tname, nname;
 118         dns_compressnode_t *node = NULL;
 119         unsigned int labels, hash, n;
 120
 121         REQUIRE(VALID_CCTX(cctx));
 122         REQUIRE(dns_name_isabsolute(name) == ISC_TRUE);
 123         REQUIRE(offset != NULL);
 124
 125         if (cctx->count == 0)
 126                 return (ISC_FALSE);
 127
 128         labels = dns_name_countlabels(name);
 129         INSIST(labels > 0);
 130
 131         dns_name_init(&tname, NULL);
 132         dns_name_init(&nname, NULL);
 133
 134         for (n = 0; n < labels - 1; n++) {
 135                 dns_name_getlabelsequence(name, n, labels - n, &tname);
 136                 hash = dns_name_hash(&tname, ISC_FALSE) %
 137                        DNS_COMPRESS_TABLESIZE;
 138                 for (node = cctx->table[hash]; node != NULL; node = node->next)
 139                 {
 140                         NODENAME(node, &nname);
 141                         if (dns_name_equal(&nname, &tname))
 142                                 break;
 143                 }
 144                 if (node != NULL)
 145                         break;
 146         }
 147
 148         /*
 149          * If node == NULL, we found no match at all.
 150          */
 151         if (node == NULL)
 152                 return (ISC_FALSE);
 153
 154         if (n == 0)
 155                 dns_name_reset(prefix);
 156         else
 157                 dns_name_getlabelsequence(name, 0, n, prefix);
 158
 159         *offset = node->offset;
 160         return (ISC_TRUE);
 161 }
 162
 163 static inline unsigned int
 164 name_length(dns_name_t *name) {
 165         isc_region_t r;
 166         dns_name_toregion(name, &r);
 167         return (r.length);
 168 }
 169
 170 void
 171 dns_compress_add(dns_compress_t *cctx, dns_name_t *name, dns_name_t *prefix,
 172                  isc_uint16_t offset)
 173 {
 174         dns_name_t tname;
 175         unsigned int start;
 176         unsigned int n;
 177         unsigned int count;
 178         unsigned int hash;
 179         dns_compressnode_t *node;
 180         unsigned int length;
 181         unsigned int tlength;
 182         isc_uint16_t toffset;
 183
 184         REQUIRE(VALID_CCTX(cctx));
 185         REQUIRE(dns_name_isabsolute(name));
 186
 187         dns_name_init(&tname, NULL);
 188
 189         n = dns_name_countlabels(name);
 190         count = dns_name_countlabels(prefix);
 191         if (dns_name_isabsolute(prefix))
 192                 count--;
 193         start = 0;
 194         length = name_length(name);
 195         while (count > 0) {
 196                 if (offset >= 0x4000)
 197                         break;
 198                 dns_name_getlabelsequence(name, start, n, &tname);
 199                 hash = dns_name_hash(&tname, ISC_FALSE) %
 200                        DNS_COMPRESS_TABLESIZE;
 201                 tlength = name_length(&tname);
 202                 toffset = (isc_uint16_t)(offset + (length - tlength));
 203                 /*
 204                  * Create a new node and add it.
 205                  */
 206                 if (cctx->count < DNS_COMPRESS_INITIALNODES)
 207                         node = &cctx->initialnodes[cctx->count];
 208                 else {
 209                         node = isc_mem_get(cctx->mctx,
 210                                            sizeof(dns_compressnode_t));
 211                         if (node == NULL)
 212                                 return;
 213                 }
 214                 node->count = cctx->count++;
 215                 node->offset = toffset;
 216                 dns_name_toregion(&tname, &node->r);
 217                 node->labels = (isc_uint8_t)dns_name_countlabels(&tname);
 218                 node->next = cctx->table[hash];
 219                 cctx->table[hash] = node;
 220                 start++;
 221                 n--;
 222                 count--;
 223         }
 224 }
 225
 226 void
 227 dns_compress_rollback(dns_compress_t *cctx, isc_uint16_t offset) {
 228         unsigned int i;
 229         dns_compressnode_t *node;
 230
 231         REQUIRE(VALID_CCTX(cctx));
 232
 233         for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) {
 234                 node = cctx->table[i];
 235                 /*
 236                  * This relies on nodes with greater offsets being
 237                  * closer to the beginning of the list, and the
 238                  * items with the greatest offsets being at the end
 239                  * of the initialnodes[] array.
 240                  */
 241                 while (node != NULL && node->offset >= offset) {
 242                         cctx->table[i] = node->next;
 243                         if (node->count >= DNS_COMPRESS_INITIALNODES)
 244                                 isc_mem_put(cctx->mctx, node, sizeof(*node));
 245                         cctx->count--;
 246                         node = cctx->table[i];
 247                 }
 248         }
 249 }
 250
 251 /***
 252  ***    Decompression
 253  ***/
 254
 255 void
 256 dns_decompress_init(dns_decompress_t *dctx, int edns,
 257                     dns_decompresstype_t type) {
 258
 259         REQUIRE(dctx != NULL);
 260         REQUIRE(edns >= -1 && edns <= 255);
 261
 262         dctx->allowed = DNS_COMPRESS_NONE;
 263         dctx->edns = edns;
 264         dctx->type = type;
 265         dctx->magic = DCTX_MAGIC;
 266 }
 267
 268 void
 269 dns_decompress_invalidate(dns_decompress_t *dctx) {
 270
 271         REQUIRE(VALID_DCTX(dctx));
 272
 273         dctx->magic = 0;
 274 }
 275
 276 void
 277 dns_decompress_setmethods(dns_decompress_t *dctx, unsigned int allowed) {
 278
 279         REQUIRE(VALID_DCTX(dctx));
 280
 281         switch (dctx->type) {
 282         case DNS_DECOMPRESS_ANY:
 283                 dctx->allowed = DNS_COMPRESS_ALL;
 284                 break;
 285         case DNS_DECOMPRESS_NONE:
 286                 dctx->allowed = DNS_COMPRESS_NONE;
 287                 break;
 288         case DNS_DECOMPRESS_STRICT:
 289                 dctx->allowed = allowed;
 290                 break;
 291         }
 292 }
 293
 294 unsigned int
 295 dns_decompress_getmethods(dns_decompress_t *dctx) {
 296
 297         REQUIRE(VALID_DCTX(dctx));
 298
 299         return (dctx->allowed);
 300 }
 301
 302 int
 303 dns_decompress_edns(dns_decompress_t *dctx) {
 304
 305         REQUIRE(VALID_DCTX(dctx));
 306
 307         return (dctx->edns);
 308 }
 309
 310 dns_decompresstype_t
 311 dns_decompress_type(dns_decompress_t *dctx) {
 312
 313         REQUIRE(VALID_DCTX(dctx));
 314
 315         return (dctx->type);
 316 }