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