[qemu.git] / slirp / dnssearch.c

/*
 * Domain search option for DHCP (RFC 3397)
 *
 * Copyright (c) 2012 Klaus Stengel
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#include "qemu/osdep.h"
#include "slirp.h"

static const uint8_t RFC3397_OPT_DOMAIN_SEARCH = 119;
static const uint8_t MAX_OPT_LEN = 255;
static const uint8_t OPT_HEADER_LEN = 2;
static const uint8_t REFERENCE_LEN = 2;

struct compact_domain;

typedef struct compact_domain {
    struct compact_domain *self;
    struct compact_domain *refdom;
    uint8_t *labels;
    size_t len;
    size_t common_octets;
} CompactDomain;

static size_t
domain_suffix_diffoff(const CompactDomain *a, const CompactDomain *b)
{
    size_t la = a->len, lb = b->len;
    uint8_t *da = a->labels + la, *db = b->labels + lb;
    size_t i, lm = (la < lb) ? la : lb;

    for (i = 0; i < lm; i++) {
        da--; db--;
        if (*da != *db) {
            break;
        }
    }
    return i;
}

static int domain_suffix_ord(const void *cva, const void *cvb)
{
    const CompactDomain *a = cva, *b = cvb;
    size_t la = a->len, lb = b->len;
    size_t doff = domain_suffix_diffoff(a, b);
    uint8_t ca = a->labels[la - doff];
    uint8_t cb = b->labels[lb - doff];

    if (ca < cb) {
        return -1;
    }
    if (ca > cb) {
        return 1;
    }
    if (la < lb) {
        return -1;
    }
    if (la > lb) {
        return 1;
    }
    return 0;
}

static size_t domain_common_label(CompactDomain *a, CompactDomain *b)
{
    size_t res, doff = domain_suffix_diffoff(a, b);
    uint8_t *first_eq_pos = a->labels + (a->len - doff);
    uint8_t *label = a->labels;

    while (*label && label < first_eq_pos) {
        label += *label + 1;
    }
    res = a->len - (label - a->labels);
    /* only report if it can help to reduce the packet size */
    return (res > REFERENCE_LEN) ? res : 0;
}

static void domain_fixup_order(CompactDomain *cd, size_t n)
{
    size_t i;

    for (i = 0; i < n; i++) {
        CompactDomain *cur = cd + i, *next = cd[i].self;

        while (!cur->common_octets) {
            CompactDomain *tmp = next->self; /* backup target value */

            next->self = cur;
            cur->common_octets++;

            cur = next;
            next = tmp;
        }
    }
}

static void domain_mklabels(CompactDomain *cd, const char *input)
{
    uint8_t *len_marker = cd->labels;
    uint8_t *output = len_marker; /* pre-incremented */
    const char *in = input;
    char cur_chr;
    size_t len = 0;

    if (cd->len == 0) {
        goto fail;
    }
    cd->len++;

    do {
        cur_chr = *in++;
        if (cur_chr == '.' || cur_chr == '\0') {
            len = output - len_marker;
            if ((len == 0 && cur_chr == '.') || len >= 64) {
                goto fail;
            }
            *len_marker = len;

            output++;
            len_marker = output;
        } else {
            output++;
            *output = cur_chr;
        }
    } while (cur_chr != '\0');

    /* ensure proper zero-termination */
    if (len != 0) {
        *len_marker = 0;
        cd->len++;
    }
    return;

fail:
    g_warning("failed to parse domain name '%s'\n", input);
    cd->len = 0;
}

static void
domain_mkxrefs(CompactDomain *doms, CompactDomain *last, size_t depth)
{
    CompactDomain *i = doms, *target = doms;

    do {
        if (i->labels < target->labels) {
            target = i;
        }
    } while (i++ != last);

    for (i = doms; i != last; i++) {
        CompactDomain *group_last;
        size_t next_depth;

        if (i->common_octets == depth) {
            continue;
        }

        next_depth = -1;
        for (group_last = i; group_last != last; group_last++) {
            size_t co = group_last->common_octets;
            if (co <= depth) {
                break;
            }
            if (co < next_depth) {
                next_depth = co;
            }
        }
        domain_mkxrefs(i, group_last, next_depth);

        i = group_last;
        if (i == last) {
            break;
        }
    }

    if (depth == 0) {
        return;
    }

    i = doms;
    do {
        if (i != target && i->refdom == NULL) {
            i->refdom = target;
            i->common_octets = depth;
        }
    } while (i++ != last);
}

static size_t domain_compactify(CompactDomain *domains, size_t n)
{
    uint8_t *start = domains->self->labels, *outptr = start;
    size_t i;

    for (i = 0; i < n; i++) {
        CompactDomain *cd = domains[i].self;
        CompactDomain *rd = cd->refdom;

        if (rd != NULL) {
            size_t moff = (rd->labels - start)
                    + (rd->len - cd->common_octets);
            if (moff < 0x3FFFu) {
                cd->len -= cd->common_octets - 2;
                cd->labels[cd->len - 1] = moff & 0xFFu;
                cd->labels[cd->len - 2] = 0xC0u | (moff >> 8);
            }
        }

        if (cd->labels != outptr) {
            memmove(outptr, cd->labels, cd->len);
            cd->labels = outptr;
        }
        outptr += cd->len;
    }
    return outptr - start;
}

int translate_dnssearch(Slirp *s, const char **names)
{
    size_t blocks, bsrc_start, bsrc_end, bdst_start;
    size_t i, num_domains, memreq = 0;
    uint8_t *result = NULL, *outptr;
    CompactDomain *domains = NULL;
    const char **nameptr = names;

    while (*nameptr != NULL) {
        nameptr++;
    }

    num_domains = nameptr - names;
    if (num_domains == 0) {
        return -2;
    }

    domains = g_malloc(num_domains * sizeof(*domains));

    for (i = 0; i < num_domains; i++) {
        size_t nlen = strlen(names[i]);
        memreq += nlen + 2; /* 1 zero octet + 1 label length octet */
        domains[i].self = domains + i;
        domains[i].len = nlen;
        domains[i].common_octets = 0;
        domains[i].refdom = NULL;
    }

    /* reserve extra 2 header bytes for each 255 bytes of output */
    memreq += DIV_ROUND_UP(memreq, MAX_OPT_LEN) * OPT_HEADER_LEN;
    result = g_malloc(memreq * sizeof(*result));

    outptr = result;
    for (i = 0; i < num_domains; i++) {
        domains[i].labels = outptr;
        domain_mklabels(domains + i, names[i]);
        outptr += domains[i].len;
    }

    if (outptr == result) {
        g_free(domains);
        g_free(result);
        return -1;
    }

    qsort(domains, num_domains, sizeof(*domains), domain_suffix_ord);
    domain_fixup_order(domains, num_domains);

    for (i = 1; i < num_domains; i++) {
        size_t cl = domain_common_label(domains + i - 1, domains + i);
        domains[i - 1].common_octets = cl;
    }

    domain_mkxrefs(domains, domains + num_domains - 1, 0);
    memreq = domain_compactify(domains, num_domains);

    blocks = DIV_ROUND_UP(memreq, MAX_OPT_LEN);
    bsrc_end = memreq;
    bsrc_start = (blocks - 1) * MAX_OPT_LEN;
    bdst_start = bsrc_start + blocks * OPT_HEADER_LEN;
    memreq += blocks * OPT_HEADER_LEN;

    while (blocks--) {
        size_t len = bsrc_end - bsrc_start;
        memmove(result + bdst_start, result + bsrc_start, len);
        result[bdst_start - 2] = RFC3397_OPT_DOMAIN_SEARCH;
        result[bdst_start - 1] = len;
        bsrc_end = bsrc_start;
        bsrc_start -= MAX_OPT_LEN;
        bdst_start -= MAX_OPT_LEN + OPT_HEADER_LEN;
    }

    g_free(domains);
    s->vdnssearch = result;
    s->vdnssearch_len = memreq;
    return 0;
}
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 "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 OPT_HEADER_LEN = 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
	44	domain_suffix_diffoff(const CompactDomain a, 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--; db--;
	52	if (da != db) {
	53	break;
	54	}
	55	}
	56	return i;
	57	}
	58
	59	static int domain_suffix_ord(const void cva, const void cvb)
	60	{
	61	const CompactDomain a = cva, b = cvb;
	62	size_t la = a->len, lb = b->len;
	63	size_t doff = domain_suffix_diffoff(a, b);
	64	uint8_t ca = a->labels[la - doff];
	65	uint8_t cb = b->labels[lb - doff];
	66
	67	if (ca < cb) {
	68	return -1;
	69	}
	70	if (ca > cb) {
	71	return 1;
	72	}
	73	if (la < lb) {
	74	return -1;
	75	}
	76	if (la > lb) {
	77	return 1;
	78	}
	79	return 0;
	80	}
	81
	82	static size_t domain_common_label(CompactDomain a, CompactDomain b)
	83	{
	84	size_t res, doff = domain_suffix_diffoff(a, b);
	85	uint8_t *first_eq_pos = a->labels + (a->len - doff);
	86	uint8_t *label = a->labels;
	87
	88	while (*label && label < first_eq_pos) {
	89	label += *label + 1;
90	}
91	res = a->len - (label - a->labels);
92	/* only report if it can help to reduce the packet size */
93	return (res > REFERENCE_LEN) ? res : 0;
94	}
95
96	static void domain_fixup_order(CompactDomain *cd, size_t n)
97	{
98	size_t i;
99
100	for (i = 0; i < n; i++) {
101	CompactDomain cur = cd + i, next = cd[i].self;
102
103	while (!cur->common_octets) {
104	CompactDomain tmp = next->self; / backup target value */
105
106	next->self = cur;
107	cur->common_octets++;
108
109	cur = next;
110	next = tmp;
111	}
112	}
113	}
114
115	static void domain_mklabels(CompactDomain cd, const char input)
116	{
117	uint8_t *len_marker = cd->labels;
118	uint8_t output = len_marker; / pre-incremented */
119	const char *in = input;
120	char cur_chr;
121	size_t len = 0;
122
123	if (cd->len == 0) {
124	goto fail;
125	}
126	cd->len++;
127
128	do {
129	cur_chr = *in++;
130	if (cur_chr == '.' \|\| cur_chr == '\0') {
131	len = output - len_marker;
132	if ((len == 0 && cur_chr == '.') \|\| len >= 64) {
133	goto fail;
134	}
135	*len_marker = len;
136
137	output++;
138	len_marker = output;
139	} else {
140	output++;
141	*output = cur_chr;
142	}
143	} while (cur_chr != '\0');
144
145	/* ensure proper zero-termination */
146	if (len != 0) {
147	*len_marker = 0;
148	cd->len++;
149	}
150	return;
151
152	fail:
153	g_warning("failed to parse domain name '%s'\n", input);
154	cd->len = 0;
155	}
156
157	static void
158	domain_mkxrefs(CompactDomain doms, CompactDomain last, size_t depth)
159	{
160	CompactDomain i = doms, target = doms;
161
162	do {
163	if (i->labels < target->labels) {
164	target = i;
165	}
166	} while (i++ != last);
167
168	for (i = doms; i != last; i++) {
169	CompactDomain *group_last;
170	size_t next_depth;
171
172	if (i->common_octets == depth) {
173	continue;
174	}
175
176	next_depth = -1;
177	for (group_last = i; group_last != last; group_last++) {
178	size_t co = group_last->common_octets;
179	if (co <= depth) {
180	break;
181	}
182	if (co < next_depth) {
183	next_depth = co;
184	}
185	}
186	domain_mkxrefs(i, group_last, next_depth);
187
188	i = group_last;
189	if (i == last) {
190	break;
191	}
192	}
193
194	if (depth == 0) {
195	return;
196	}
197
198	i = doms;
199	do {
200	if (i != target && i->refdom == NULL) {
201	i->refdom = target;
202	i->common_octets = depth;
203	}
204	} while (i++ != last);
205	}
206
207	static size_t domain_compactify(CompactDomain *domains, size_t n)
208	{
209	uint8_t start = domains->self->labels, outptr = start;
210	size_t i;
211
212	for (i = 0; i < n; i++) {
213	CompactDomain *cd = domains[i].self;
214	CompactDomain *rd = cd->refdom;
215
216	if (rd != NULL) {
217	size_t moff = (rd->labels - start)
218	+ (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 */
80695683	264	memreq += DIV_ROUND_UP(memreq, MAX_OPT_LEN) * OPT_HEADER_LEN;
63d2960b KS	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
80695683	291	blocks = DIV_ROUND_UP(memreq, MAX_OPT_LEN);
63d2960b KS	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	}