1 | /* SPDX-License-Identifier: MIT */ |
2 | /* |
3 | * Domain search option for DHCP (RFC 3397) |
4 | * |
5 | * Copyright (c) 2012 Klaus Stengel |
6 | * |
7 | * Permission is hereby granted, free of charge, to any person obtaining a copy |
8 | * of this software and associated documentation files (the "Software"), to deal |
9 | * in the Software without restriction, including without limitation the rights |
10 | * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
11 | * copies of the Software, and to permit persons to whom the Software is |
12 | * furnished to do so, subject to the following conditions: |
13 | * |
14 | * The above copyright notice and this permission notice shall be included in |
15 | * all copies or substantial portions of the Software. |
16 | * |
17 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
18 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
19 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
20 | * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
21 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
22 | * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
23 | * THE SOFTWARE. |
24 | */ |
25 | |
26 | #include "slirp.h" |
27 | |
28 | static const uint8_t RFC3397_OPT_DOMAIN_SEARCH = 119; |
29 | static const uint8_t MAX_OPT_LEN = 255; |
30 | static const uint8_t = 2; |
31 | static const uint8_t REFERENCE_LEN = 2; |
32 | |
33 | struct compact_domain; |
34 | |
35 | typedef struct compact_domain { |
36 | struct compact_domain *self; |
37 | struct compact_domain *refdom; |
38 | uint8_t *labels; |
39 | size_t len; |
40 | size_t common_octets; |
41 | } CompactDomain; |
42 | |
43 | static size_t domain_suffix_diffoff(const CompactDomain *a, |
44 | const CompactDomain *b) |
45 | { |
46 | size_t la = a->len, lb = b->len; |
47 | uint8_t *da = a->labels + la, *db = b->labels + lb; |
48 | size_t i, lm = (la < lb) ? la : lb; |
49 | |
50 | for (i = 0; i < lm; i++) { |
51 | da--; |
52 | db--; |
53 | if (*da != *db) { |
54 | break; |
55 | } |
56 | } |
57 | return i; |
58 | } |
59 | |
60 | static int domain_suffix_ord(const void *cva, const void *cvb) |
61 | { |
62 | const CompactDomain *a = cva, *b = cvb; |
63 | size_t la = a->len, lb = b->len; |
64 | size_t doff = domain_suffix_diffoff(a, b); |
65 | uint8_t ca = a->labels[la - doff]; |
66 | uint8_t cb = b->labels[lb - doff]; |
67 | |
68 | if (ca < cb) { |
69 | return -1; |
70 | } |
71 | if (ca > cb) { |
72 | return 1; |
73 | } |
74 | if (la < lb) { |
75 | return -1; |
76 | } |
77 | if (la > lb) { |
78 | return 1; |
79 | } |
80 | return 0; |
81 | } |
82 | |
83 | static size_t domain_common_label(CompactDomain *a, CompactDomain *b) |
84 | { |
85 | size_t res, doff = domain_suffix_diffoff(a, b); |
86 | uint8_t *first_eq_pos = a->labels + (a->len - doff); |
87 | uint8_t *label = a->labels; |
88 | |
89 | while (*label && label < first_eq_pos) { |
90 | label += *label + 1; |
91 | } |
92 | res = a->len - (label - a->labels); |
93 | /* only report if it can help to reduce the packet size */ |
94 | return (res > REFERENCE_LEN) ? res : 0; |
95 | } |
96 | |
97 | static void domain_fixup_order(CompactDomain *cd, size_t n) |
98 | { |
99 | size_t i; |
100 | |
101 | for (i = 0; i < n; i++) { |
102 | CompactDomain *cur = cd + i, *next = cd[i].self; |
103 | |
104 | while (!cur->common_octets) { |
105 | CompactDomain *tmp = next->self; /* backup target value */ |
106 | |
107 | next->self = cur; |
108 | cur->common_octets++; |
109 | |
110 | cur = next; |
111 | next = tmp; |
112 | } |
113 | } |
114 | } |
115 | |
116 | static void domain_mklabels(CompactDomain *cd, const char *input) |
117 | { |
118 | uint8_t *len_marker = cd->labels; |
119 | uint8_t *output = len_marker; /* pre-incremented */ |
120 | const char *in = input; |
121 | char cur_chr; |
122 | size_t len = 0; |
123 | |
124 | if (cd->len == 0) { |
125 | goto fail; |
126 | } |
127 | cd->len++; |
128 | |
129 | do { |
130 | cur_chr = *in++; |
131 | if (cur_chr == '.' || cur_chr == '\0') { |
132 | len = output - len_marker; |
133 | if ((len == 0 && cur_chr == '.') || len >= 64) { |
134 | goto fail; |
135 | } |
136 | *len_marker = len; |
137 | |
138 | output++; |
139 | len_marker = output; |
140 | } else { |
141 | output++; |
142 | *output = cur_chr; |
143 | } |
144 | } while (cur_chr != '\0'); |
145 | |
146 | /* ensure proper zero-termination */ |
147 | if (len != 0) { |
148 | *len_marker = 0; |
149 | cd->len++; |
150 | } |
151 | return; |
152 | |
153 | fail: |
154 | g_warning("failed to parse domain name '%s'\n" , input); |
155 | cd->len = 0; |
156 | } |
157 | |
158 | static void domain_mkxrefs(CompactDomain *doms, CompactDomain *last, |
159 | size_t depth) |
160 | { |
161 | CompactDomain *i = doms, *target = doms; |
162 | |
163 | do { |
164 | if (i->labels < target->labels) { |
165 | target = i; |
166 | } |
167 | } while (i++ != last); |
168 | |
169 | for (i = doms; i != last; i++) { |
170 | CompactDomain *group_last; |
171 | size_t next_depth; |
172 | |
173 | if (i->common_octets == depth) { |
174 | continue; |
175 | } |
176 | |
177 | next_depth = -1; |
178 | for (group_last = i; group_last != last; group_last++) { |
179 | size_t co = group_last->common_octets; |
180 | if (co <= depth) { |
181 | break; |
182 | } |
183 | if (co < next_depth) { |
184 | next_depth = co; |
185 | } |
186 | } |
187 | domain_mkxrefs(i, group_last, next_depth); |
188 | |
189 | i = group_last; |
190 | if (i == last) { |
191 | break; |
192 | } |
193 | } |
194 | |
195 | if (depth == 0) { |
196 | return; |
197 | } |
198 | |
199 | i = doms; |
200 | do { |
201 | if (i != target && i->refdom == NULL) { |
202 | i->refdom = target; |
203 | i->common_octets = depth; |
204 | } |
205 | } while (i++ != last); |
206 | } |
207 | |
208 | static size_t domain_compactify(CompactDomain *domains, size_t n) |
209 | { |
210 | uint8_t *start = domains->self->labels, *outptr = start; |
211 | size_t i; |
212 | |
213 | for (i = 0; i < n; i++) { |
214 | CompactDomain *cd = domains[i].self; |
215 | CompactDomain *rd = cd->refdom; |
216 | |
217 | if (rd != NULL) { |
218 | size_t moff = (rd->labels - start) + (rd->len - cd->common_octets); |
219 | if (moff < 0x3FFFu) { |
220 | cd->len -= cd->common_octets - 2; |
221 | cd->labels[cd->len - 1] = moff & 0xFFu; |
222 | cd->labels[cd->len - 2] = 0xC0u | (moff >> 8); |
223 | } |
224 | } |
225 | |
226 | if (cd->labels != outptr) { |
227 | memmove(outptr, cd->labels, cd->len); |
228 | cd->labels = outptr; |
229 | } |
230 | outptr += cd->len; |
231 | } |
232 | return outptr - start; |
233 | } |
234 | |
235 | int translate_dnssearch(Slirp *s, const char **names) |
236 | { |
237 | size_t blocks, bsrc_start, bsrc_end, bdst_start; |
238 | size_t i, num_domains, memreq = 0; |
239 | uint8_t *result = NULL, *outptr; |
240 | CompactDomain *domains = NULL; |
241 | const char **nameptr = names; |
242 | |
243 | while (*nameptr != NULL) { |
244 | nameptr++; |
245 | } |
246 | |
247 | num_domains = nameptr - names; |
248 | if (num_domains == 0) { |
249 | return -2; |
250 | } |
251 | |
252 | domains = g_malloc(num_domains * sizeof(*domains)); |
253 | |
254 | for (i = 0; i < num_domains; i++) { |
255 | size_t nlen = strlen(names[i]); |
256 | memreq += nlen + 2; /* 1 zero octet + 1 label length octet */ |
257 | domains[i].self = domains + i; |
258 | domains[i].len = nlen; |
259 | domains[i].common_octets = 0; |
260 | domains[i].refdom = NULL; |
261 | } |
262 | |
263 | /* reserve extra 2 header bytes for each 255 bytes of output */ |
264 | memreq += DIV_ROUND_UP(memreq, MAX_OPT_LEN) * OPT_HEADER_LEN; |
265 | result = g_malloc(memreq * sizeof(*result)); |
266 | |
267 | outptr = result; |
268 | for (i = 0; i < num_domains; i++) { |
269 | domains[i].labels = outptr; |
270 | domain_mklabels(domains + i, names[i]); |
271 | outptr += domains[i].len; |
272 | } |
273 | |
274 | if (outptr == result) { |
275 | g_free(domains); |
276 | g_free(result); |
277 | return -1; |
278 | } |
279 | |
280 | qsort(domains, num_domains, sizeof(*domains), domain_suffix_ord); |
281 | domain_fixup_order(domains, num_domains); |
282 | |
283 | for (i = 1; i < num_domains; i++) { |
284 | size_t cl = domain_common_label(domains + i - 1, domains + i); |
285 | domains[i - 1].common_octets = cl; |
286 | } |
287 | |
288 | domain_mkxrefs(domains, domains + num_domains - 1, 0); |
289 | memreq = domain_compactify(domains, num_domains); |
290 | |
291 | blocks = DIV_ROUND_UP(memreq, MAX_OPT_LEN); |
292 | bsrc_end = memreq; |
293 | bsrc_start = (blocks - 1) * MAX_OPT_LEN; |
294 | bdst_start = bsrc_start + blocks * OPT_HEADER_LEN; |
295 | memreq += blocks * OPT_HEADER_LEN; |
296 | |
297 | while (blocks--) { |
298 | size_t len = bsrc_end - bsrc_start; |
299 | memmove(result + bdst_start, result + bsrc_start, len); |
300 | result[bdst_start - 2] = RFC3397_OPT_DOMAIN_SEARCH; |
301 | result[bdst_start - 1] = len; |
302 | bsrc_end = bsrc_start; |
303 | bsrc_start -= MAX_OPT_LEN; |
304 | bdst_start -= MAX_OPT_LEN + OPT_HEADER_LEN; |
305 | } |
306 | |
307 | g_free(domains); |
308 | s->vdnssearch = result; |
309 | s->vdnssearch_len = memreq; |
310 | return 0; |
311 | } |
312 | |