contrib/bind/lib/dns/compress.c

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