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.6 2020/09/14 08:40:43 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
dns_compress_init(dns_compress_t * cctx,int edns)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
dns_compress_invalidate(dns_compress_t * cctx)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
dns_compress_setmethods(dns_compress_t * cctx,unsigned int allowed)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
dns_compress_getmethods(dns_compress_t * cctx)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 1. prefix, suffix and offset are updated.
86 * If no match is found return 0.
87 */
88 int
dns_compress_findglobal(dns_compress_t * cctx,const dns_name_t * name,dns_name_t * prefix,uint16_t * offset)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));
97 REQUIRE(offset != NULL);
98
99 if (cctx->count == 0)
100 return (0);
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, 0) %
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 (0);
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 (1);
140 }
141
142 void
dns_compress_add(dns_compress_t * cctx,const dns_name_t * name,const dns_name_t * prefix,uint16_t offset)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, 0) %
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
dns_compress_rollback(dns_compress_t * cctx,uint16_t offset)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
dns_decompress_init(dns_decompress_t * dctx,int edns,dns_decompresstype_t type)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
dns_decompress_setmethods(dns_decompress_t * dctx,unsigned int allowed)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