]>
Commit | Line | Data |
---|---|---|
63d2960b KS |
1 | /* |
2 | * Domain search option for DHCP (RFC 3397) | |
3 | * | |
4 | * Copyright (c) 2012 Klaus Stengel | |
5 | * | |
6 | * Permission is hereby granted, free of charge, to any person obtaining a copy | |
7 | * of this software and associated documentation files (the "Software"), to deal | |
8 | * in the Software without restriction, including without limitation the rights | |
9 | * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
10 | * copies of the Software, and to permit persons to whom the Software is | |
11 | * furnished to do so, subject to the following conditions: | |
12 | * | |
13 | * The above copyright notice and this permission notice shall be included in | |
14 | * all copies or substantial portions of the Software. | |
15 | * | |
16 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
17 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
18 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL | |
19 | * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
20 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
21 | * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN | |
22 | * THE SOFTWARE. | |
23 | */ | |
24 | ||
7df7482b | 25 | #include "qemu/osdep.h" |
63d2960b KS |
26 | #include <glib.h> |
27 | #include "slirp.h" | |
28 | ||
29 | static const uint8_t RFC3397_OPT_DOMAIN_SEARCH = 119; | |
30 | static const uint8_t MAX_OPT_LEN = 255; | |
31 | static const uint8_t OPT_HEADER_LEN = 2; | |
32 | static const uint8_t REFERENCE_LEN = 2; | |
33 | ||
34 | struct compact_domain; | |
35 | ||
36 | typedef struct compact_domain { | |
37 | struct compact_domain *self; | |
38 | struct compact_domain *refdom; | |
39 | uint8_t *labels; | |
40 | size_t len; | |
41 | size_t common_octets; | |
42 | } CompactDomain; | |
43 | ||
44 | static size_t | |
45 | domain_suffix_diffoff(const CompactDomain *a, const CompactDomain *b) | |
46 | { | |
47 | size_t la = a->len, lb = b->len; | |
48 | uint8_t *da = a->labels + la, *db = b->labels + lb; | |
49 | size_t i, lm = (la < lb) ? la : lb; | |
50 | ||
51 | for (i = 0; i < lm; i++) { | |
52 | da--; 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 | |
159 | domain_mkxrefs(CompactDomain *doms, CompactDomain *last, 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) | |
219 | + (rd->len - cd->common_octets); | |
220 | if (moff < 0x3FFFu) { | |
221 | cd->len -= cd->common_octets - 2; | |
222 | cd->labels[cd->len - 1] = moff & 0xFFu; | |
223 | cd->labels[cd->len - 2] = 0xC0u | (moff >> 8); | |
224 | } | |
225 | } | |
226 | ||
227 | if (cd->labels != outptr) { | |
228 | memmove(outptr, cd->labels, cd->len); | |
229 | cd->labels = outptr; | |
230 | } | |
231 | outptr += cd->len; | |
232 | } | |
233 | return outptr - start; | |
234 | } | |
235 | ||
236 | int translate_dnssearch(Slirp *s, const char **names) | |
237 | { | |
238 | size_t blocks, bsrc_start, bsrc_end, bdst_start; | |
239 | size_t i, num_domains, memreq = 0; | |
240 | uint8_t *result = NULL, *outptr; | |
241 | CompactDomain *domains = NULL; | |
242 | const char **nameptr = names; | |
243 | ||
244 | while (*nameptr != NULL) { | |
245 | nameptr++; | |
246 | } | |
247 | ||
248 | num_domains = nameptr - names; | |
249 | if (num_domains == 0) { | |
250 | return -2; | |
251 | } | |
252 | ||
253 | domains = g_malloc(num_domains * sizeof(*domains)); | |
254 | ||
255 | for (i = 0; i < num_domains; i++) { | |
256 | size_t nlen = strlen(names[i]); | |
257 | memreq += nlen + 2; /* 1 zero octet + 1 label length octet */ | |
258 | domains[i].self = domains + i; | |
259 | domains[i].len = nlen; | |
260 | domains[i].common_octets = 0; | |
261 | domains[i].refdom = NULL; | |
262 | } | |
263 | ||
264 | /* reserve extra 2 header bytes for each 255 bytes of output */ | |
265 | memreq += ((memreq + MAX_OPT_LEN - 1) / MAX_OPT_LEN) * OPT_HEADER_LEN; | |
266 | result = g_malloc(memreq * sizeof(*result)); | |
267 | ||
268 | outptr = result; | |
269 | for (i = 0; i < num_domains; i++) { | |
270 | domains[i].labels = outptr; | |
271 | domain_mklabels(domains + i, names[i]); | |
272 | outptr += domains[i].len; | |
273 | } | |
274 | ||
275 | if (outptr == result) { | |
276 | g_free(domains); | |
277 | g_free(result); | |
278 | return -1; | |
279 | } | |
280 | ||
281 | qsort(domains, num_domains, sizeof(*domains), domain_suffix_ord); | |
282 | domain_fixup_order(domains, num_domains); | |
283 | ||
284 | for (i = 1; i < num_domains; i++) { | |
285 | size_t cl = domain_common_label(domains + i - 1, domains + i); | |
286 | domains[i - 1].common_octets = cl; | |
287 | } | |
288 | ||
289 | domain_mkxrefs(domains, domains + num_domains - 1, 0); | |
290 | memreq = domain_compactify(domains, num_domains); | |
291 | ||
292 | blocks = (memreq + MAX_OPT_LEN - 1) / MAX_OPT_LEN; | |
293 | bsrc_end = memreq; | |
294 | bsrc_start = (blocks - 1) * MAX_OPT_LEN; | |
295 | bdst_start = bsrc_start + blocks * OPT_HEADER_LEN; | |
296 | memreq += blocks * OPT_HEADER_LEN; | |
297 | ||
298 | while (blocks--) { | |
299 | size_t len = bsrc_end - bsrc_start; | |
300 | memmove(result + bdst_start, result + bsrc_start, len); | |
301 | result[bdst_start - 2] = RFC3397_OPT_DOMAIN_SEARCH; | |
302 | result[bdst_start - 1] = len; | |
303 | bsrc_end = bsrc_start; | |
304 | bsrc_start -= MAX_OPT_LEN; | |
305 | bdst_start -= MAX_OPT_LEN + OPT_HEADER_LEN; | |
306 | } | |
307 | ||
308 | g_free(domains); | |
309 | s->vdnssearch = result; | |
310 | s->vdnssearch_len = memreq; | |
311 | return 0; | |
312 | } |