acl: fix memory leak
[qemu.git] / slirp / dnssearch.c
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
25 #include <stdlib.h>
26 #include <string.h>
27 #include <stdio.h>
28 #include <glib.h>
29 #include "slirp.h"
30
31 static const uint8_t RFC3397_OPT_DOMAIN_SEARCH = 119;
32 static const uint8_t MAX_OPT_LEN = 255;
33 static const uint8_t OPT_HEADER_LEN = 2;
34 static const uint8_t REFERENCE_LEN = 2;
35
36 struct compact_domain;
37
38 typedef struct compact_domain {
39 struct compact_domain *self;
40 struct compact_domain *refdom;
41 uint8_t *labels;
42 size_t len;
43 size_t common_octets;
44 } CompactDomain;
45
46 static size_t
47 domain_suffix_diffoff(const CompactDomain *a, const CompactDomain *b)
48 {
49 size_t la = a->len, lb = b->len;
50 uint8_t *da = a->labels + la, *db = b->labels + lb;
51 size_t i, lm = (la < lb) ? la : lb;
52
53 for (i = 0; i < lm; i++) {
54 da--; db--;
55 if (*da != *db) {
56 break;
57 }
58 }
59 return i;
60 }
61
62 static int domain_suffix_ord(const void *cva, const void *cvb)
63 {
64 const CompactDomain *a = cva, *b = cvb;
65 size_t la = a->len, lb = b->len;
66 size_t doff = domain_suffix_diffoff(a, b);
67 uint8_t ca = a->labels[la - doff];
68 uint8_t cb = b->labels[lb - doff];
69
70 if (ca < cb) {
71 return -1;
72 }
73 if (ca > cb) {
74 return 1;
75 }
76 if (la < lb) {
77 return -1;
78 }
79 if (la > lb) {
80 return 1;
81 }
82 return 0;
83 }
84
85 static size_t domain_common_label(CompactDomain *a, CompactDomain *b)
86 {
87 size_t res, doff = domain_suffix_diffoff(a, b);
88 uint8_t *first_eq_pos = a->labels + (a->len - doff);
89 uint8_t *label = a->labels;
90
91 while (*label && label < first_eq_pos) {
92 label += *label + 1;
93 }
94 res = a->len - (label - a->labels);
95 /* only report if it can help to reduce the packet size */
96 return (res > REFERENCE_LEN) ? res : 0;
97 }
98
99 static void domain_fixup_order(CompactDomain *cd, size_t n)
100 {
101 size_t i;
102
103 for (i = 0; i < n; i++) {
104 CompactDomain *cur = cd + i, *next = cd[i].self;
105
106 while (!cur->common_octets) {
107 CompactDomain *tmp = next->self; /* backup target value */
108
109 next->self = cur;
110 cur->common_octets++;
111
112 cur = next;
113 next = tmp;
114 }
115 }
116 }
117
118 static void domain_mklabels(CompactDomain *cd, const char *input)
119 {
120 uint8_t *len_marker = cd->labels;
121 uint8_t *output = len_marker; /* pre-incremented */
122 const char *in = input;
123 char cur_chr;
124 size_t len = 0;
125
126 if (cd->len == 0) {
127 goto fail;
128 }
129 cd->len++;
130
131 do {
132 cur_chr = *in++;
133 if (cur_chr == '.' || cur_chr == '\0') {
134 len = output - len_marker;
135 if ((len == 0 && cur_chr == '.') || len >= 64) {
136 goto fail;
137 }
138 *len_marker = len;
139
140 output++;
141 len_marker = output;
142 } else {
143 output++;
144 *output = cur_chr;
145 }
146 } while (cur_chr != '\0');
147
148 /* ensure proper zero-termination */
149 if (len != 0) {
150 *len_marker = 0;
151 cd->len++;
152 }
153 return;
154
155 fail:
156 g_warning("failed to parse domain name '%s'\n", input);
157 cd->len = 0;
158 }
159
160 static void
161 domain_mkxrefs(CompactDomain *doms, CompactDomain *last, size_t depth)
162 {
163 CompactDomain *i = doms, *target = doms;
164
165 do {
166 if (i->labels < target->labels) {
167 target = i;
168 }
169 } while (i++ != last);
170
171 for (i = doms; i != last; i++) {
172 CompactDomain *group_last;
173 size_t next_depth;
174
175 if (i->common_octets == depth) {
176 continue;
177 }
178
179 next_depth = -1;
180 for (group_last = i; group_last != last; group_last++) {
181 size_t co = group_last->common_octets;
182 if (co <= depth) {
183 break;
184 }
185 if (co < next_depth) {
186 next_depth = co;
187 }
188 }
189 domain_mkxrefs(i, group_last, next_depth);
190
191 i = group_last;
192 if (i == last) {
193 break;
194 }
195 }
196
197 if (depth == 0) {
198 return;
199 }
200
201 i = doms;
202 do {
203 if (i != target && i->refdom == NULL) {
204 i->refdom = target;
205 i->common_octets = depth;
206 }
207 } while (i++ != last);
208 }
209
210 static size_t domain_compactify(CompactDomain *domains, size_t n)
211 {
212 uint8_t *start = domains->self->labels, *outptr = start;
213 size_t i;
214
215 for (i = 0; i < n; i++) {
216 CompactDomain *cd = domains[i].self;
217 CompactDomain *rd = cd->refdom;
218
219 if (rd != NULL) {
220 size_t moff = (rd->labels - start)
221 + (rd->len - cd->common_octets);
222 if (moff < 0x3FFFu) {
223 cd->len -= cd->common_octets - 2;
224 cd->labels[cd->len - 1] = moff & 0xFFu;
225 cd->labels[cd->len - 2] = 0xC0u | (moff >> 8);
226 }
227 }
228
229 if (cd->labels != outptr) {
230 memmove(outptr, cd->labels, cd->len);
231 cd->labels = outptr;
232 }
233 outptr += cd->len;
234 }
235 return outptr - start;
236 }
237
238 int translate_dnssearch(Slirp *s, const char **names)
239 {
240 size_t blocks, bsrc_start, bsrc_end, bdst_start;
241 size_t i, num_domains, memreq = 0;
242 uint8_t *result = NULL, *outptr;
243 CompactDomain *domains = NULL;
244 const char **nameptr = names;
245
246 while (*nameptr != NULL) {
247 nameptr++;
248 }
249
250 num_domains = nameptr - names;
251 if (num_domains == 0) {
252 return -2;
253 }
254
255 domains = g_malloc(num_domains * sizeof(*domains));
256
257 for (i = 0; i < num_domains; i++) {
258 size_t nlen = strlen(names[i]);
259 memreq += nlen + 2; /* 1 zero octet + 1 label length octet */
260 domains[i].self = domains + i;
261 domains[i].len = nlen;
262 domains[i].common_octets = 0;
263 domains[i].refdom = NULL;
264 }
265
266 /* reserve extra 2 header bytes for each 255 bytes of output */
267 memreq += ((memreq + MAX_OPT_LEN - 1) / MAX_OPT_LEN) * OPT_HEADER_LEN;
268 result = g_malloc(memreq * sizeof(*result));
269
270 outptr = result;
271 for (i = 0; i < num_domains; i++) {
272 domains[i].labels = outptr;
273 domain_mklabels(domains + i, names[i]);
274 outptr += domains[i].len;
275 }
276
277 if (outptr == result) {
278 g_free(domains);
279 g_free(result);
280 return -1;
281 }
282
283 qsort(domains, num_domains, sizeof(*domains), domain_suffix_ord);
284 domain_fixup_order(domains, num_domains);
285
286 for (i = 1; i < num_domains; i++) {
287 size_t cl = domain_common_label(domains + i - 1, domains + i);
288 domains[i - 1].common_octets = cl;
289 }
290
291 domain_mkxrefs(domains, domains + num_domains - 1, 0);
292 memreq = domain_compactify(domains, num_domains);
293
294 blocks = (memreq + MAX_OPT_LEN - 1) / MAX_OPT_LEN;
295 bsrc_end = memreq;
296 bsrc_start = (blocks - 1) * MAX_OPT_LEN;
297 bdst_start = bsrc_start + blocks * OPT_HEADER_LEN;
298 memreq += blocks * OPT_HEADER_LEN;
299
300 while (blocks--) {
301 size_t len = bsrc_end - bsrc_start;
302 memmove(result + bdst_start, result + bsrc_start, len);
303 result[bdst_start - 2] = RFC3397_OPT_DOMAIN_SEARCH;
304 result[bdst_start - 1] = len;
305 bsrc_end = bsrc_start;
306 bsrc_start -= MAX_OPT_LEN;
307 bdst_start -= MAX_OPT_LEN + OPT_HEADER_LEN;
308 }
309
310 g_free(domains);
311 s->vdnssearch = result;
312 s->vdnssearch_len = memreq;
313 return 0;
314 }