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