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 45isc_result_t 46dns_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 62void 63dns_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 83void 84dns_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 91unsigned int 92dns_compress_getmethods(dns_compress_t *cctx) { 93 REQUIRE(VALID_CCTX(cctx)); 94 return (cctx->allowed & DNS_COMPRESS_ALL); 95} 96 97void 98dns_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 107isc_boolean_t 108dns_compress_getsensitive(dns_compress_t *cctx) { 109 REQUIRE(VALID_CCTX(cctx)); 110 111 return (ISC_TF((cctx->allowed & DNS_COMPRESS_CASESENSITIVE) != 0)); 112} 113 114int 115dns_compress_getedns(dns_compress_t *cctx) { 116 REQUIRE(VALID_CCTX(cctx)); 117 return (cctx->edns); 118} 119 120#define NODENAME(node, name) \ 121do { \ 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 */ 133isc_boolean_t 134dns_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 188static inline unsigned int 189name_length(const dns_name_t *name) { 190 isc_region_t r; 191 dns_name_toregion(name, &r); 192 return (r.length); 193} 194 195void 196dns_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 251void 252dns_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 280void 281dns_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 293void 294dns_decompress_invalidate(dns_decompress_t *dctx) { 295 296 REQUIRE(VALID_DCTX(dctx)); 297 298 dctx->magic = 0; 299} 300 301void 302dns_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 319unsigned int 320dns_decompress_getmethods(dns_decompress_t *dctx) { 321 322 REQUIRE(VALID_DCTX(dctx)); 323 324 return (dctx->allowed); 325} 326 327int 328dns_decompress_edns(dns_decompress_t *dctx) { 329 330 REQUIRE(VALID_DCTX(dctx)); 331 332 return (dctx->edns); 333} 334 335dns_decompresstype_t 336dns_decompress_type(dns_decompress_t *dctx) { 337 338 REQUIRE(VALID_DCTX(dctx)); 339 340 return (dctx->type); 341} 342