1 /* $NetBSD: compress.c,v 1.4 2014/12/10 04:37:58 christos 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 47 isc_result_t dns_compress_init(dns_compress_t * cctx,int edns,isc_mem_t * mctx)48 dns_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 64 void dns_compress_invalidate(dns_compress_t * cctx)65 dns_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 85 void dns_compress_setmethods(dns_compress_t * cctx,unsigned int allowed)86 dns_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 93 unsigned int dns_compress_getmethods(dns_compress_t * cctx)94 dns_compress_getmethods(dns_compress_t *cctx) { 95 REQUIRE(VALID_CCTX(cctx)); 96 return (cctx->allowed & DNS_COMPRESS_ALL); 97 } 98 99 void dns_compress_setsensitive(dns_compress_t * cctx,isc_boolean_t sensitive)100 dns_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 109 isc_boolean_t dns_compress_getsensitive(dns_compress_t * cctx)110 dns_compress_getsensitive(dns_compress_t *cctx) { 111 REQUIRE(VALID_CCTX(cctx)); 112 113 return (ISC_TF((cctx->allowed & DNS_COMPRESS_CASESENSITIVE) != 0)); 114 } 115 116 int dns_compress_getedns(dns_compress_t * cctx)117 dns_compress_getedns(dns_compress_t *cctx) { 118 REQUIRE(VALID_CCTX(cctx)); 119 return (cctx->edns); 120 } 121 122 #define NODENAME(node, name) \ 123 do { \ 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 */ 135 isc_boolean_t dns_compress_findglobal(dns_compress_t * cctx,const dns_name_t * name,dns_name_t * prefix,isc_uint16_t * offset)136 dns_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 190 static inline unsigned int name_length(const dns_name_t * name)191 name_length(const dns_name_t *name) { 192 isc_region_t r; 193 dns_name_toregion(name, &r); 194 return (r.length); 195 } 196 197 void dns_compress_add(dns_compress_t * cctx,const dns_name_t * name,const dns_name_t * prefix,isc_uint16_t offset)198 dns_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 253 void dns_compress_rollback(dns_compress_t * cctx,isc_uint16_t offset)254 dns_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 282 void dns_decompress_init(dns_decompress_t * dctx,int edns,dns_decompresstype_t type)283 dns_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 295 void dns_decompress_invalidate(dns_decompress_t * dctx)296 dns_decompress_invalidate(dns_decompress_t *dctx) { 297 298 REQUIRE(VALID_DCTX(dctx)); 299 300 dctx->magic = 0; 301 } 302 303 void dns_decompress_setmethods(dns_decompress_t * dctx,unsigned int allowed)304 dns_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 321 unsigned int dns_decompress_getmethods(dns_decompress_t * dctx)322 dns_decompress_getmethods(dns_decompress_t *dctx) { 323 324 REQUIRE(VALID_DCTX(dctx)); 325 326 return (dctx->allowed); 327 } 328 329 int dns_decompress_edns(dns_decompress_t * dctx)330 dns_decompress_edns(dns_decompress_t *dctx) { 331 332 REQUIRE(VALID_DCTX(dctx)); 333 334 return (dctx->edns); 335 } 336 337 dns_decompresstype_t dns_decompress_type(dns_decompress_t * dctx)338 dns_decompress_type(dns_decompress_t *dctx) { 339 340 REQUIRE(VALID_DCTX(dctx)); 341 342 return (dctx->type); 343 } 344