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 }