1 /* 2 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 3 * 4 * Permission to use, copy, modify, and/or distribute this software for any 5 * purpose with or without fee is hereby granted, provided that the above 6 * copyright notice and this permission notice appear in all copies. 7 * 8 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 9 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 10 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 11 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 12 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 13 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 14 * PERFORMANCE OF THIS SOFTWARE. 15 */ 16 17 /* $Id: compress.c,v 1.5 2020/02/18 18:11:27 florian Exp $ */ 18 19 /*! \file */ 20 21 #include <stdlib.h> 22 23 #include <isc/util.h> 24 25 #include <dns/compress.h> 26 #include <dns/fixedname.h> 27 28 /*** 29 *** Compression 30 ***/ 31 32 isc_result_t 33 dns_compress_init(dns_compress_t *cctx, int edns) { 34 unsigned int i; 35 36 REQUIRE(cctx != NULL); 37 38 cctx->allowed = 0; 39 cctx->edns = edns; 40 for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) 41 cctx->table[i] = NULL; 42 cctx->count = 0; 43 return (ISC_R_SUCCESS); 44 } 45 46 void 47 dns_compress_invalidate(dns_compress_t *cctx) { 48 dns_compressnode_t *node; 49 unsigned int i; 50 51 for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) { 52 while (cctx->table[i] != NULL) { 53 node = cctx->table[i]; 54 cctx->table[i] = cctx->table[i]->next; 55 if (node->count < DNS_COMPRESS_INITIALNODES) 56 continue; 57 free(node); 58 } 59 } 60 cctx->allowed = 0; 61 cctx->edns = -1; 62 } 63 64 void 65 dns_compress_setmethods(dns_compress_t *cctx, unsigned int allowed) { 66 cctx->allowed &= ~DNS_COMPRESS_ALL; 67 cctx->allowed |= (allowed & DNS_COMPRESS_ALL); 68 } 69 70 unsigned int 71 dns_compress_getmethods(dns_compress_t *cctx) { 72 return (cctx->allowed & DNS_COMPRESS_ALL); 73 } 74 75 #define NODENAME(node, name) \ 76 do { \ 77 (name)->length = (node)->r.length; \ 78 (name)->labels = (node)->labels; \ 79 (name)->ndata = (node)->r.base; \ 80 (name)->attributes = DNS_NAMEATTR_ABSOLUTE; \ 81 } while (0) 82 83 /* 84 * Find the longest match of name in the table. 85 * If match is found return ISC_TRUE. prefix, suffix and offset are updated. 86 * If no match is found return ISC_FALSE. 87 */ 88 isc_boolean_t 89 dns_compress_findglobal(dns_compress_t *cctx, const dns_name_t *name, 90 dns_name_t *prefix, uint16_t *offset) 91 { 92 dns_name_t tname, nname; 93 dns_compressnode_t *node = NULL; 94 unsigned int labels, hash, n; 95 96 REQUIRE(dns_name_isabsolute(name) == ISC_TRUE); 97 REQUIRE(offset != NULL); 98 99 if (cctx->count == 0) 100 return (ISC_FALSE); 101 102 labels = dns_name_countlabels(name); 103 INSIST(labels > 0); 104 105 dns_name_init(&tname, NULL); 106 dns_name_init(&nname, NULL); 107 108 for (n = 0; n < labels - 1; n++) { 109 dns_name_getlabelsequence(name, n, labels - n, &tname); 110 hash = dns_name_hash(&tname, ISC_FALSE) % 111 DNS_COMPRESS_TABLESIZE; 112 for (node = cctx->table[hash]; node != NULL; node = node->next) 113 { 114 NODENAME(node, &nname); 115 if ((cctx->allowed & DNS_COMPRESS_CASESENSITIVE) != 0) { 116 if (dns_name_caseequal(&nname, &tname)) 117 break; 118 } else { 119 if (dns_name_equal(&nname, &tname)) 120 break; 121 } 122 } 123 if (node != NULL) 124 break; 125 } 126 127 /* 128 * If node == NULL, we found no match at all. 129 */ 130 if (node == NULL) 131 return (ISC_FALSE); 132 133 if (n == 0) 134 dns_name_reset(prefix); 135 else 136 dns_name_getlabelsequence(name, 0, n, prefix); 137 138 *offset = node->offset; 139 return (ISC_TRUE); 140 } 141 142 void 143 dns_compress_add(dns_compress_t *cctx, const dns_name_t *name, 144 const dns_name_t *prefix, uint16_t offset) 145 { 146 dns_name_t tname; 147 unsigned int start; 148 unsigned int n; 149 unsigned int count; 150 unsigned int hash; 151 dns_compressnode_t *node; 152 unsigned int length; 153 unsigned int tlength; 154 uint16_t toffset; 155 156 REQUIRE(dns_name_isabsolute(name)); 157 158 dns_name_init(&tname, NULL); 159 160 n = dns_name_countlabels(name); 161 count = dns_name_countlabels(prefix); 162 if (dns_name_isabsolute(prefix)) 163 count--; 164 start = 0; 165 length = name->length; 166 while (count > 0) { 167 if (offset >= 0x4000) 168 break; 169 dns_name_getlabelsequence(name, start, n, &tname); 170 hash = dns_name_hash(&tname, ISC_FALSE) % 171 DNS_COMPRESS_TABLESIZE; 172 tlength = tname.length; 173 toffset = (uint16_t)(offset + (length - tlength)); 174 /* 175 * Create a new node and add it. 176 */ 177 if (cctx->count < DNS_COMPRESS_INITIALNODES) 178 node = &cctx->initialnodes[cctx->count]; 179 else { 180 node = malloc(sizeof(dns_compressnode_t)); 181 if (node == NULL) 182 return; 183 } 184 node->count = cctx->count++; 185 node->offset = toffset; 186 dns_name_toregion(&tname, &node->r); 187 node->labels = (uint8_t)dns_name_countlabels(&tname); 188 node->next = cctx->table[hash]; 189 cctx->table[hash] = node; 190 start++; 191 n--; 192 count--; 193 } 194 } 195 196 void 197 dns_compress_rollback(dns_compress_t *cctx, uint16_t offset) { 198 unsigned int i; 199 dns_compressnode_t *node; 200 201 for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) { 202 node = cctx->table[i]; 203 /* 204 * This relies on nodes with greater offsets being 205 * closer to the beginning of the list, and the 206 * items with the greatest offsets being at the end 207 * of the initialnodes[] array. 208 */ 209 while (node != NULL && node->offset >= offset) { 210 cctx->table[i] = node->next; 211 if (node->count >= DNS_COMPRESS_INITIALNODES) 212 free(node); 213 cctx->count--; 214 node = cctx->table[i]; 215 } 216 } 217 } 218 219 /*** 220 *** Decompression 221 ***/ 222 223 void 224 dns_decompress_init(dns_decompress_t *dctx, int edns, 225 dns_decompresstype_t type) { 226 227 REQUIRE(dctx != NULL); 228 REQUIRE(edns >= -1 && edns <= 255); 229 230 dctx->allowed = DNS_COMPRESS_NONE; 231 dctx->edns = edns; 232 dctx->type = type; 233 } 234 235 void 236 dns_decompress_setmethods(dns_decompress_t *dctx, unsigned int allowed) { 237 switch (dctx->type) { 238 case DNS_DECOMPRESS_ANY: 239 dctx->allowed = DNS_COMPRESS_ALL; 240 break; 241 case DNS_DECOMPRESS_NONE: 242 dctx->allowed = DNS_COMPRESS_NONE; 243 break; 244 case DNS_DECOMPRESS_STRICT: 245 dctx->allowed = allowed; 246 break; 247 } 248 } 249