dns.c

Go to the documentation of this file.

/*
 *   This library is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU Lesser General Public
 *   License as published by the Free Software Foundation; either
 *   version 2.1 of the License, or (at your option) any later version.
 *
 *   This library is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *   Lesser General Public License for more details.
 *
 *   You should have received a copy of the GNU Lesser General Public
 *   License along with this library; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 */
 
/** Functions to manipulate DNS labels
 *
 * @file src/lib/util/dns.c
 *
 * @copyright 2019 The FreeRADIUS server project
 * @copyright 2019 Network RADIUS SAS (legal@networkradius.com)
 */
RCSID("$Id: 1b6ff71fd6bb4a6a42377f12780b68f5f51a2ae3 $")
 
#include <freeradius-devel/util/misc.h>
#include <freeradius-devel/util/strerror.h>
#include <freeradius-devel/util/value.h>
#include <freeradius-devel/util/dns.h>
#include <freeradius-devel/util/proto.h>
 
#define MAX_OFFSET (1 << 14)
 
static int dns_label_add(fr_dns_labels_t *lb, uint8_t const *start, uint8_t const *end)
{
        size_t offset, size = end - start;
        fr_dns_block_t *block;
 
        /*
         *      If we don't care about tracking the blocks, then don't
         *      do anything.
         */
        if (!lb) return 0;
 
        fr_assert(start >= lb->start);
        fr_assert(end >= start);
 
        offset = start - lb->start;
 
        /*
         *      DNS packets can be up to 64K in size, but the
         *      compressed pointers can only be up to 2^14 in size.
         *      So we just ignore offsets which are greater than 2^14.
         */
        if ((offset + size) >= MAX_OFFSET) return 0;
 
        /*
         *      We're not tracking labels, so don't do anything.
         */
        if (lb->max == 1) return 0;
 
        FR_PROTO_TRACE("adding label at offset %zu", offset);
 
        /*
         *      We add blocks append-only.  No adding new blocks in
         *      the middle of a packet.
         */
        block = &lb->blocks[lb->num - 1];
        fr_assert(block->start <= offset);
        fr_assert(offset);
 
        FR_PROTO_TRACE("Last block (%d) is %u..%u", lb->num - 1, block->start, block->end);
 
        /*
         *      Fits within an existing block.
         */
        if (block->end == offset) {
                block->end += size;
                FR_PROTO_TRACE("Expanding last block (%d) to %u..%u", lb->num - 1, block->start, block->end);
                return 0;
        }
 
        /*
         *      It's full, die.
         */
        if (lb->num == lb->max) return -1;
 
        lb->num++;
        block++;
 
        block->start = offset;
        block->end = offset + size;
        FR_PROTO_TRACE("Appending block (%d) to %u..%u", lb->num - 1, block->start, block->end);
 
        return 0;
}
 
static void dns_label_mark(fr_dns_labels_t *lb, uint8_t const *p)
{
        if (!lb || !lb->mark) return;
 
        fr_assert(p >= (lb->start + 12)); /* can't point to the packet header */
        fr_assert(!lb->end || (p < lb->end));
 
        lb->mark[p - lb->start] = 1;
}
 
 
static bool dns_pointer_valid(fr_dns_labels_t *lb, uint16_t offset)
{
        int i;
 
        if (!lb) return true;   /* we have no idea, so allow it */
 
        if (lb->mark) return (lb->mark[offset] != 0);
 
        /*
         *      Brute-force searching.
         *
         *      @todo - manually walk through the pointers for the block?
         */
        for (i = 0; i < lb->num; i++) {
                FR_PROTO_TRACE("Checking block %d %u..%u against %u",
                               i, lb->blocks[i].start, lb->blocks[i].end, offset);
 
                if (offset < lb->blocks[i].start) return false;
 
                if (offset < lb->blocks[i].end) return true;
        }
 
        return false;
}
 
/** Compare two labels in a case-insensitive fashion.
 *
 *  This function requires that the input is valid, i.e. all
 *  characters are within [-0-9A-Za-z].  If any other input is given,
 *  it will break.
 */
static bool labelcmp(uint8_t const *a, uint8_t const *b, size_t len)
{
        for (/* nothing */; len > 0; len--) {
                if (*a == *b) {
                        a++;
                        b++;
                        continue;
                }
 
                /*
                 *      If one or the other isn't a letter, we can't
                 *      do case insensitive comparisons of them, so
                 *      they can't match.
                 */
                if (!(((*a >= 'a') && (*a <= 'z')) || ((*a >= 'A') && (*a <= 'Z')))) return false;
                if (!(((*b >= 'a') && (*b <= 'z')) || ((*b >= 'A') && (*b <= 'Z')))) return false;
 
                /*
                 *      If they're equal but different case, then the
                 *      only bit that's different is 0x20.
                 */
                if (((*a)^(*b)) != 0x20) {
                        return false;
                }
 
                a++;
                b++;
        }
 
        return true;
}
 
/** Compress "label" by looking at the label recursively.
 *
 *  For "ftp.example.com", it searches the input buffer for a matching
 *  "com".  It only does string compares if it finds bytes "03 xx xx
 *  xx 00".  This means that the scan is quick, because most bytes are
 *  skipped.
 *
 *  If a matching string is found, the label is updated to replace
 *  "com" with a 2-byte pointer P1.  The process then proceeds
 *  recursively, with "exampleP1".
 *
 *  The input buffer is the scanned again for labels of matching
 *  length (7 here), AND which either end in the value of "P1", or end
 *  *at* P1.  If we find a match, we replace "exampleP1" with "P2".
 *  The process then proceeds recursively with "ftpP2".
 *
 *  Since the algorithm replaces known suffixes with pointers, we
 *  *never* have to compare full names.  Instead, we only ever compare
 *  one label to one other label.  And then only if the labels have
 *  the same lengths AND the same suffixes (00 byte, or a pointer P).
 *
 *  As an extra optimization, we track the start of the label where we
 *  found the compressed pointer.  e.g. "www.example.com" when
 *  compressing "com".  We know that the "com" string CANNOT appear
 *  before this label.  Because if it did, then the "www.example.com"
 *  name would have instead been compressed, as in "www.exampleP1".
 *
 *  This optimization ensures that we scan as little of the buffer as
 *  possible, by moving the search start ahead in the buffer.  This
 *  optimization also means that in many cases, the suffix we're
 *  looking for (e.g. "example.com") is in the first label we search.
 *  Which means that we end up ignoring most of the buffer.
 *
 *  This algorithm is O(N * B), where N is the number of labels in a
 *  name (e.g. 3 for "ftp.example.com"), and "B" is the size of the
 *  buffer.  It also does linear scans of the buffer, which are good
 *  for read-ahead.  Each input label is compared to labels in the
 *  buffer only when very limited situations apply.  And we never
 *  compare the full input name to full names in the buffer.
 *
 *  In the case where we are adding many names from the same zone to
 *  the input buffer, the input buffer will start with the zone name.
 *  So any searches will match that.  The only reason to continue
 *  scanning the buffer is to see if the name prefix already exists.
 *  If we assume that the records do not contain duplicates, then we
 *  can likely skip that scan, too.
 *
 *  Adding that optimization, however, requires tracking the maximum
 *  size of a name across multiple invocations of the function.  For
 *  example, if the maximum length name in the buffer is 3 labels, and
 *  we're adding a 3 label name, then we can stop scanning the buffer
 *  as soon as we compressed the 2 suffix labels.  Since we are
 *  guaranteed that there are no duplicates, we are sure that there is
 *  no existing 3-label name which matches a 3-label name in the
 *  buffer.
 *
 *  Note that this function does NOT follow pointers in the input
 *  buffer!
 *
 *
 *  A different and more straightforward approach is to loop over all
 *  labels in the name from longest to shortest, and comparing them to
 *  each name in the buffer in turn.  That algorithm ends up being
 *  O(L1 * T * L2), where L1 is the length of the input name, T is the
 *  total number of names in the buffer, and L2 is the average length
 *  of names in the buffer.  This algorithm can result in the buffer
 *  being scanned many, many, times.  The scan is also done forwards
 *  (due to comparing names one after the other), but also backwards
 *  (due to following pointers).  Which makes for poor locality of
 *  reference.
 *
 *  i.e. that approach *has* to scan the entire input buffer, because
 *  that's where all of the names are.  Further, it has to scan it at
 *  least "N" times, because there are N labels in the input name.  So
 *  O(N * B) is the *lower* bound for this algorithm.
 *
 *  It gets worse when the straightforward algorithm does pointer
 *  following instead of pointer comparisons.  It ends up scanning
 *  portions of the input buffer many, many, times.  i.e. it can
 *  compare an input "com" name to "org" once for every "org" name in
 *  the input buffer.  In contrast, because our algorithm does not do
 *  pointer following, it only compares "com" to "org" once.
 *
 * @param[in] packet      where the packet starts
 * @param[in] start       input buffer holding one or more labels
 * @param[in] end         end of the input buffer
 * @param[out] new_search Where the parent call to dns_label_compress()
 *                        should start searching from, instead of from "start".
 * @param[in] label       label to add to the buffer.
 * @param[out] label_end  updated end of the input label after compression.
 * @return
 *      - false, we didn't compress the input
 *      - true, we did compress the input.
 */
static bool dns_label_compress(uint8_t const *packet, uint8_t const *start, uint8_t const *end, uint8_t const **new_search,
                               uint8_t *label, uint8_t **label_end)
{
        uint8_t *next;
        uint8_t const *q, *ptr, *suffix, *search;
        uint16_t offset;
        bool compressed = false;
 
        /*
         *      Don't compress "end of label" byte or pointers.
         */
        if (!*label || (*label > 63)) {
                return false;
        }
 
        /*
         *      Check the next label.  Note that this is *after*
         *      "end".  It also MUST be a valid, uncompressed label.
         */
        next = label + *label + 1;
 
        /*
         *      Note that by design, next > end.  We don't care about
         *      the size of the buffer we put "label" into.  We only
         *      care that all bytes of "label" are valid, and we don't
         *      access memory after "label".
         */
 
        /*
         *      On the first call, begin searching from the start of
         *      the buffer.
         *
         *      For subsequent calls, begin from where we started
         *      searching before.
         */
        if (!new_search) {
                search = start;
        } else {
                search = *new_search;
        }
 
        /*
         *      We're at the last uncompressed label, scan the input
         *      buffer to see if there's a match.
         *
         *      The scan skips ahead until it find both a label length
         *      that matches, AND "next" label which is 0x00.  Only
         *      then does it do the string compare of the label
         *      values.
         *
         *      We speed this up slightly by tracking the previous
         *      uncompressed pointer.  If we do compress the current
         *      label, then we should also tell the caller where the
         *      previous uncompressed label started.  That way the
         *      caller can start looking there for the next piece to
         *      compress.  There's no need to search from the
         *      beginning of the input buffer, as we're sure that
         *      there is no earlier instance of the suffix we found.
         *
         *      i.e. as we compress the current name, we start
         *      searching not at the beginning of the input buffer/
         *      Instead, we start searching at the name which contains
         *      the label that we just compressed.  The previous
         *      sarching guarantees that no name *before* that one
         *      will match the suffix we're looking for.  So we can
         *      skip all of the previous names in subsequent searches,
         */
        if (*next == 0x00) {
                q = search;
                while (q < end) {
                        if (*q == 0x00) {
                                q++;
 
                                /*
                                 *      None of the previous names
                                 *      matched, so we tell the caller
                                 *      to start searching from the
                                 *      next name in the buffer.
                                 */
                                search = q;
                                continue;
                        }
 
                        /*
                         *      Our label is a terminal one.  Which
                         *      can't point to a pointer.
                         */
                        if (*q > 63) {
                                q += 2;
 
                                /*
                                 *      None of the previous
                                 *      uncompressed names matched,
                                 *      and this pointer refers to a
                                 *      compressed name.  So it
                                 *      doesn't match, either.
                                 */
                                search = q;
                                continue;
                        }
 
                        /*
                         *      We now have a label which MIGHT match.
                         *      We have to walk down it until it does
                         *      match.  But we don't update "search"
                         *      here, because there may be a suffix
                         *      which matches.
                         */
                        ptr = q + *q + 1;
                        if (ptr >= end) return false;
 
                        /*
                         *      Label lengths aren't the same, skip
                         *      it.
                         */
                        if (*q != *label) {
                                q = ptr;
                                continue;
                        }
 
                        /*
                         *      Our input label ends with 0x00.  If
                         *      this label doesn't end with 0x00, skip
                         *      it.
                         */
                        if (*ptr != 0x00) {
                                q = ptr;
                                continue;
                        }
 
                        /*
                         *      The pointer is too far away.  Don't
                         *      point to it.  This check is mainly for
                         *      static analyzers.
                         */
                        if ((q - packet) > (1 << 14)) return false;
 
                        /*
                         *      Only now do case-insensitive
                         *      comparisons.
                         */
                        if (!labelcmp(q + 1, label + 1, *label)) {
                                q = ptr;
                                continue;
                        }
 
                        /*
                         *      We have a match.  Replace the input
                         *      label with a compressed pointer.  Tell
                         *      the caller the start of the found
                         *      name, so subsequent searches can start
                         *      from there.  Then return to the caller
                         *      that we managed to compress this
                         *      label.
                         */
                        offset = (q - packet);
                        label[0] = (offset >> 8) | 0xc0;
                        label[1] = offset & 0xff;
                        *label_end = label + 2;
                        if (new_search) *new_search = search;
                        return true;
                }
 
                return false;
        }
 
        /*
         *      The next label is still uncompressed, so we call
         *      ourselves recursively in order to compress it.
         */
        if (*next <= 63) {
                if (!dns_label_compress(packet, start, end, &search, next, label_end)) return false;
 
                /*
                 *      Else it WAS compressed.
                 */
                compressed = true;
        }
 
        /*
         *      The next label wasn't compressed, OR it is invalid,
         *      skip it.  This check is here only to shut up the
         *      static analysis tools.
         */
        if (*next < 0xc0) {
                return compressed;
        }
 
        /*
         *      Remember where our suffix points to.
         */
        suffix = packet + ((next[0] & ~0xc0) << 8) + next[1];
 
        /*
         *      Our label now ends with a compressed pointer.  Scan
         *      the input until we find either an uncompressed label
         *      which ends with the same compressed pointer, OR we
         *      find an uncompressed label which ends AT our
         *      compressed pointer.
         *
         *      Note that we start searching from the beginning of the
         *      label which resulted in us finding the compressed
         *      pointer!
         *
         *      We're guaranteed that any label BEFORE that one
         *      doesn't end with a matching compressed pointer.
         */
        q = search;
        while (q < end) {
                if (*q == 0x00) {
                        q++;
 
                        /*
                         *      None of the previous stuff matched, so
                         *      we tell the caller to start searching
                         *      from the next name.
                         */
                        search = q;
                        continue;
                }
 
                /*
                 *      Skip compressed pointers.  We can't point to
                 *      compressed pointers.
                 */
                if (*q > 63) {
                        q += 2;
 
                        /*
                         *      None of the previous uncompressed
                         *      names matched, and this pointer refers
                         *      to a compressed name.  So it doesn't
                         *      match, either.
                         */
                        search = q;
                        continue;
                }
 
                /*
                 *      We now have an uncompressed label in the input
                 *      buffer.  Check for a match.
                 */
                ptr = q + *q + 1;
                if (ptr >= end) return compressed;
 
                /*
                 *      Label lengths aren't the same, skip it.
                 */
                if (*q != *label) {
                        q = ptr;
                        continue;
                }
 
                /*
                 *      If the NEXT label is uncompressed, then skip
                 *      it unless it's the suffix we're pointing to.
                 */
                if (*ptr <= 63) {
                        if (ptr != suffix) {
                                q = ptr;
                                continue;
                        }
 
                        goto check_label;
                }
 
                /*
                 *      The next label is a compressed pointer.  If
                 *      the compressed pointers are different, then
                 *      skip both this label and the compressed
                 *      pointer after it.
                 */
                if ((ptr[0] != next[0]) ||
                    (ptr[1] != next[1])) {
                        q = ptr + 2;
 
                        /*
                         *      None of the previous uncompressed
                         *      names matched, and this pointer refers
                         *      to a compressed name.  So it doesn't
                         *      match, either.
                         */
                        search = q;
                        continue;
                }
 
        check_label:
                /*
                 *      Pointer is too far away.  Don't point
                 *      to it.
                 */
                if ((q - packet) > (1 << 14)) return compressed;
 
                /*
                 *      Only now do case-insensitive
                 *      comparisons.
                 */
                if (!labelcmp(q + 1, label + 1, *label)) {
                        q = ptr;
                        continue;
                }
 
                /*
                 *      We have a match.  Replace the input
                 *      label with a compressed pointer.  Tell
                 *      the caller the start of the found
                 *      name, so subsequent searches can start
                 *      from there.  Then return to the caller
                 *      that we managed to compress this
                 *      label.
                 */
                offset = (q - packet);
                label[0] = (offset >> 8) | 0xc0;
                label[1] = offset & 0xff;
                *label_end = label + 2;
                if (new_search) *new_search = search;
                return true;
        }
 
        /*
         *      Who knows what it is, we couldn't compress it.
         */
        return compressed;
}
 
 
/** Encode a single value box of type string, serializing its contents to a dns label
 *  in a dbuff
 *
 * @param[in] dbuff     Buffer where labels are written
 * @param[in] compression Whether or not to do DNS label compression.
 * @param[in] value     to encode.
 * @param[in] lb        label tracking data structure.
 * @return
 *      - >=0 the number of bytes written to the dbuff
 *      - <0 error
 */
ssize_t fr_dns_label_from_value_box_dbuff(fr_dbuff_t *dbuff, bool compression, fr_value_box_t const *value, fr_dns_labels_t *lb)
{
        ssize_t                 slen;
        size_t                  need = 0;
 
        slen = fr_dns_label_from_value_box(&need, dbuff->p, fr_dbuff_remaining(dbuff), dbuff->p, compression, value, lb);
        if (slen < 0) return -need;
 
        fr_dbuff_advance(dbuff, (size_t) slen);
        return slen;
}
 
/** Encode a single value box of type string, serializing its contents to a dns label
 *
 * This functions takes a large buffer and encodes the label in part
 * of the buffer.  This API is necessary in order to allow DNS label
 * compression.
 *
 * @param[out] need     if not NULL, how long "buf_len" should be to
 *                      serialize the rest of the data.
 *                      Note: Only variable length types will be partially
 *                      encoded. Fixed length types will not be partially encoded.
 * @param[out] buf      Buffer where labels are stored
 * @param[in] buf_len   The length of the output buffer
 * @param[out] where    Where to write this label
 * @param[in] compression Whether or not to do DNS label compression.
 * @param[in] value     to encode.
 * @param[in] lb        label tracking data structure
 * @return
 *      - 0 no bytes were written, see need value to determine
 *      - >0 the number of bytes written to "where", NOT "buf + where + outlen"
 *      - <0 on error.
 */
ssize_t fr_dns_label_from_value_box(size_t *need, uint8_t *buf, size_t buf_len, uint8_t *where, bool compression,
                                    fr_value_box_t const *value, fr_dns_labels_t *lb)
{
        uint8_t *label;
        uint8_t const *end;
        uint8_t const *q, *strend, *last;
        uint8_t *data;
        bool underscore = true;
 
        if (!buf || !buf_len || !where || !value) {
                fr_strerror_const("Invalid input");
                return -1;
        }
 
        end = buf + buf_len;
 
        /*
         *      Don't allow stupidities
         */
        if (!((where >= buf) && (where < (buf + buf_len)))) {
                fr_strerror_const("Label to write is outside of buffer");
                return -1;
        }
 
        /*
         *      We can only encode strings.
         */
        if (value->type != FR_TYPE_STRING) {
                fr_strerror_const("Asked to encode non-string type");
                return -1;
        }
 
        /*
         *      '.' or empty string is special, and is encoded as a
         *      plain zero byte.
         *
         *      Since "where < end", we can always write 1 byte to it.
         */
        if ((value->vb_length == 0) ||
            ((value->vb_length == 1) && (value->vb_strvalue[0] == '.'))) {
                *where = 0x00;
                return 1;
        }
 
        /*
         *      Sanity check the name before writing anything to the
         *      buffer.
         *
         *      Only encode [-0-9a-zA-Z].  Anything else is forbidden.
         *      Dots at the start are forbidden.  Double dots are
         *      forbidden.
         */
        q = (uint8_t const *) value->vb_strvalue;
        strend = q + value->vb_length;
        last = q;
 
        if (*q == '.') {
                fr_strerror_const("Empty labels are invalid");
                return -1;
        }
 
        /*
         *      Convert it piece by piece.
         */
        while (q < strend) {
                /*
                 *      Allow underscore at the start of a label.
                 */
                if (underscore) {
                        underscore = false;
 
                        if (*q == '_') goto next;
                }
 
                if (*q == '.') {
                        /*
                         *      Don't count final dot as an
                         *      intermediate dot, and don't bother
                         *      encoding it.
                         */
                        if ((q + 1) == strend) {
                                strend--;
                                break;
                        }
 
                        if (q[1] == '.') {
                                fr_strerror_const("Double dots '..' are forbidden");
                                return -1;
                        }
                        last = q;
 
                        /*
                         *      We had a dot, allow underscore as the
                         *      first character of the next label.
                         */
                        underscore = true;
 
                } else if (!((*q == '-') || ((*q >= '0') && (*q <= '9')) ||
                             ((*q >= 'A') && (*q <= 'Z')) || ((*q >= 'a') && (*q <= 'z')))) {
                        fr_strerror_printf("Invalid character 0x%02x in label", *q);
                        return -1;
                }
 
        next:
                q++;
 
                if ((q - last) > 63) {
                        fr_strerror_const("Label is larger than 63 characters");
                        return -1;
                }
        }
 
        q = (uint8_t const *) value->vb_strvalue;
 
        /*
         *      For now, just encode the value as-is.  We do
         *      compression as a second step.
         *
         *      We need a minimum length of string + beginning length
         *      + trailing zero.  Intermediate '.' are converted to
         *      length bytes.
         */
        if ((where + (strend - q) + 2) > end) {
                if (need) *need = (where + (strend - q) + 2) - buf;
                return 0;
        }
 
        label = where;
        *label = 0;
        data = label + 1;
 
        /*
         *      @todo - encode into a local buffer, and then try to
         *      compress that into the output buffer.  This means that
         *      the output buffer can be a little bit smaller.
         */
        while (q < strend) {
                fr_assert(data < end);
                fr_assert((data - where) < 255);
 
                /*
                 *      '.' is a label delimiter.
                 *
                 *      We've already checked above for '.' at the
                 *      start, for double dots, and have already
                 *      suppressed '.' at the end of the string.
                 *
                 *      Start a new label.
                 */
                if (*q == '.') {
                        label = data;
                        *label = 0;
                        data = label + 1;
 
                        q++;
                        continue;
                }
 
                *(data++) = *(q++);
                (*label)++;
                fr_assert(*label <= 63);
        }
 
        *(data++) = 0;          /* end of label */
 
        /*
         *      If we're compressing it, and we have data to compress,
         *      then do it.
         */
        if (compression && ((data - where) > 2)) {
                if (lb) {
                        int i;
 
                        /*
                         *      Loop over the parts of the packet which have DNS labels.
                         *
                         *      Note that the dns_label_compress() function does NOT follow pointers in the
                         *      start/end block which it's searching!  It just tries to compress the *input*,
                         *      and assumes that the input is compressed last label to first label.
                         *
                         *      In addition, dns_label_compress() tracks where in the block it started
                         *      searching.  So it only scans the block once, even if we pass a NULL search
                         *      parameter to it.
                         *
                         *      We could start compression from the *last* block.  When we add
                         *      "www.example.com" and then "ftp.example.com", we could point "ftp" to the
                         *      "example.com" portion. which is already in the packet.  However, doing that
                         *      would require that dns_label_compress() follows pointers in the block it's
                         *      searching. Which would greatly increase the complexity of the algorithm.
                         *
                         *
                         *      We could still optimize this algorithm a bit, by tracking which parts of the
                         *      buffer have DNS names of label length 1, 2, etc.  Doing that would mean more
                         *      complex data structures, but fewer passes over the packet.
                         */
                        for (i = 0; i < lb->num; i++) {
                                bool compressed;
 
                                FR_PROTO_TRACE("Trying to compress %s in block %d of %u..%u",
                                               value->vb_strvalue, i,
                                               lb->blocks[i].start, lb->blocks[i].end);
 
                                compressed = dns_label_compress(lb->start, lb->start + lb->blocks[i].start,
                                                                lb->start + lb->blocks[i].end,
                                                                NULL, where, &data);
                                if (compressed) {
                                        FR_PROTO_TRACE("Compressed label in block %d", i);
                                        if (*(where + *where + 1) >= 0xc0) {
                                                FR_PROTO_TRACE("Next label is compressed, stopping");
                                        }
                                }
                        }
 
                        dns_label_add(lb, where, data);
 
                } else if (buf != where) {
                        if (dns_label_compress(buf, buf, where, NULL, where, &data)) {
                                FR_PROTO_TRACE("Compressed single label %s to %zu bytes",
                                               value->vb_strvalue, (size_t) (data - where));
                        } else {
                                FR_PROTO_TRACE("Did not compress single label");
                        }
                }
        } else {
                FR_PROTO_TRACE("Not compressing label");
        }
 
        fr_assert(data > where);
        return data - where;
}
 
/** Get the *uncompressed* length of a DNS label in a network buffer.
 *
 *  i.e. how bytes are required to store the uncompressed version of
 *  the label.
 *
 *  Note that a bare 0x00 byte has length 1, to account for '.'
 *
 * @param[in] packet      where the packet starts
 * @param[in] buf       buffer holding one or more DNS labels
 * @param[in] buf_len   total length of the buffer
 * @param[in,out] next  the DNS label to check, updated to point to the next label
 * @param[in] lb        label tracking data structure
 * @return
 *      - <=0 on error, offset from buf where the invalid label is located.
 *      - > 0 decoded size of this particular DNS label
 */
ssize_t fr_dns_label_uncompressed_length(uint8_t const *packet, uint8_t const *buf, size_t buf_len, uint8_t const **next, fr_dns_labels_t *lb)
{
        uint8_t const *p, *q, *end, *label_end;
        uint8_t const *current, *start;
        size_t length;
        bool at_first_label, already_set_next;
 
        if (!packet || !buf || (buf_len == 0) || !next) {
                fr_strerror_printf("Invalid argument");
                return 0;
        }
 
        start = *next;
 
        /*
         *      Don't allow stupidities
         */
        if (!((start >= packet) && (start < (buf + buf_len)))) {
                fr_strerror_printf("Label is not within the buffer");
                return 0;
        }
 
        end = buf + buf_len;
        p = current = start;
        length = 0;
        at_first_label = true;
        already_set_next = false;
 
        /*
         *      We silently accept labels *without* a trailing 0x00,
         *      so long as they end at the end of the input buffer.
         */
        while (p < end) {
                /*
                 *      End of label byte.  Skip it.
                 *
                 *      Empty labels are length 1, to account for the
                 *      '.'.  The caller has to take care of this
                 *      manually.
                 */
                if (*p == 0x00) {
                        p++;
                        if (at_first_label) length++;
 
                        /*
                         *      We're still processing the first
                         *      label, tell the caller where the next
                         *      one is located.
                         */
                        if (current == start) {
                                *next = p;
                                already_set_next = true;
                        }
 
                        break;
                }
 
                /*
                 *      If there's only one byte in the packet, then
                 *      it MUST be 0x00.  If it's not, then the label
                 *      overflows the buffer.
                 */
                if ((p + 1) >= end) goto overflow;
 
                /*
                 *      0b01 and 0b10 are forbidden
                 */
                if ((*p > 63) && (*p < 0xc0)) {
                        fr_strerror_const("Data with invalid high bits");
                        return -(p - packet);
                }
 
                /*
                 *      Maybe it's a compressed pointer.
                 */
                if (*p > 63) {
                        uint16_t offset;
 
                        if ((p + 2) > end) {
                        overflow:
                                fr_strerror_const("Label overflows buffer");
                                return -(p - packet);
                        }
 
                        offset = p[1];
                        offset += ((*p & ~0xc0) << 8);
 
                        /*
                         *      Forward references are forbidden,
                         *      including self-references.
                         *
                         *      This requirement follows RFC 1035
                         *      Section 4.1.4, which says:
                         *
                         *      ... an entire domain name or a list of
                         *      labels at the end of a domain name is
                         *      replaced with a pointer to a prior
                         *      occurrence of the same name.
                         *      ...
                         *
                         *      Note the key word PRIOR.  If we
                         *      enforce that the pointer is backwards,
                         *      and do various other enforcements,
                         *      then it is very difficult for
                         *      attackers to create malicious DNS
                         *      packets which will cause the decoder
                         *      to do bad things.
                         */
                        if (offset >= (p - packet)) {
                                fr_strerror_printf("Pointer %04x at offset %04x is an invalid forward reference",
                                                   offset, (unsigned int) (p - packet));
                                return -(p - packet);
                        }
 
                        q = packet + offset;
 
                        /*
                         *      As an additional sanity check, the
                         *      pointer MUST NOT point to something
                         *      within the label we're parsing.  If
                         *      that happens, we have a loop.
                         *
                         *      i.e. the pointer must point backwards
                         *      to *before* our current label.  When
                         *      that limitation is enforced, pointer
                         *      loops are impossible.
                         */
                        if (q >= current) {
                                fr_strerror_printf("Pointer %04x at offset %04x creates a loop within a label",
                                                   offset, (unsigned int) (p - packet));
                                return -(p - packet);
                        }
 
                        /*
                         *      If we're tracking which labels are
                         *      valid, then check the pointer, too.
                         */
                        if (!dns_pointer_valid(lb, offset)) {
                                fr_strerror_printf("Pointer %04x at offset %04x does not point to a DNS label",
                                                   offset, (unsigned int) (p - packet));
                                return -(p - packet);
                        }
 
                        /*
                         *      The pointer MUST point to a valid
                         *      length field, and not to another
                         *      pointer.
                         */
                        if (*q > 63) {
                                fr_strerror_printf("Pointer %04x at offset %04x does not point to the start of a label",
                                                   offset, (unsigned int) (p - packet));
                                return -(p - packet);
                        }
 
                        /*
                         *      The pointer MUST NOT point to an end of label field.
                         */
                        if (!*q) {
                                fr_strerror_printf("Pointer %04x at offset %04x refers to an invalid field", offset,
                                                   (unsigned int) (p - packet));
                                return -(p - packet);
                        }
 
                        /*
                         *      If we're jumping away from the label
                         *      we started with, tell the caller where
                         *      the next label is in the network
                         *      buffer.
                         */
                        if (current == start) {
                                *next = p + 2;
                                already_set_next = true;
                        }
 
                        p = current = q;
                        continue;
                }
 
                /*
                 *      Else it's an uncompressed label
                 */
                if ((p + *p + 1) > end) goto overflow;
 
                /*
                 *      It's a valid label.  Mark it as such.
                 */
                dns_label_mark(lb, p);
 
                /*
                 *      Account for the '.' on every label after the
                 *      first one.
                 */
                if (!at_first_label) length++;
                at_first_label = false;
                length += *p;
 
                /*
                 *      DNS names can be no more than 255 octets.
                 */
                if (length > 255) {
                        fr_strerror_const("Total length of labels is > 255");
                        return -(p - packet);
                }
 
                q = p + 1;
                label_end = q + *p;
 
                /*
                 *      Allow for underscore at the beginning of a
                 *      label.
                 */
                if (*q == '_') q++;
 
                /*
                 *      Verify that the contents of the label are OK.
                 */
                while (q < label_end) {
                        if (!((*q == '-') || ((*q >= '0') && (*q <= '9')) ||
                              ((*q >= 'A') && (*q <= 'Z')) || ((*q >= 'a') && (*q <= 'z')))) {
                                fr_strerror_printf("Invalid character 0x%02x in label", *q);
                                return -(q - packet);
                        }
 
                        q++;
                }
 
                p += *p + 1;
        }
 
        /*
         *      Return the length of this label.
         */
        if (!already_set_next) *next = p; /* should be <='end' */
 
        /*
         *      Add the label, only if we're not using the markup field.
         */
        if (lb && !lb->mark) (void) dns_label_add(lb, start, *next);
 
        return length;
}
 
/** Verify that a network buffer contains valid DNS labels.
 *
 * @param[in] packet      where the packet starts
 * @param[in] buf       buffer holding one or more DNS labels
 * @param[in] buf_len   total length of the buffer
 * @param[in] start     where to start looking
 * @param[in] lb        label tracking data structure
 * @return
 *      - <=0 on error, where in the buffer the invalid label is located.
 *      - > 0 total size of the encoded label(s).  Will be <= buf_len
 */
ssize_t fr_dns_labels_network_verify(uint8_t const *packet, uint8_t const *buf, size_t buf_len, uint8_t const *start, fr_dns_labels_t *lb)
{
        ssize_t slen;
        uint8_t const *label = start;
        uint8_t const *end = buf + buf_len;
 
        while (label < end) {
                if (*label == 0x00) {
                        label++;
                        break;
                }
 
                slen = fr_dns_label_uncompressed_length(packet, buf, buf_len, &label, lb);
                if (slen <= 0) return slen; /* already is offset from 'buf' and not 'label' */
        }
 
        return label - buf;
}
 
static ssize_t dns_label_decode(uint8_t const *packet, uint8_t const *end, uint8_t const **start, uint8_t const **next)
{
        uint8_t const *p, *q;
 
        p = *start;
 
        if (end == packet) return -1;
 
        if (*p == 0x00) {
                *next = p + 1;
                return 0;
        }
 
        /*
         *      Pointer, which points somewhere in the packet.
         */
        if (*p >= 0xc0) {
                uint16_t offset;
 
                if ((end - p) < 2) {
                        return -(p - packet);
                }
 
                offset = p[1];
                offset += ((*p & ~0xc0) << 8);
 
                q = packet + offset;
                if (q >= p) {
                        return -(p - packet);
                }
                p = q;
        }
 
        /*
         *      0b01 and 0b10 are forbidden, and pointers can't point to other pointers.
         */
        if (*p > 63) return -(p - packet);
 
        if ((p + *p + 1) > end) {
                return -(p - packet);
        }
 
        /*
         *      Tell the caller where the actual label is located.
         */
        *start = p;
        *next = p + *p + 1;
        return *p;
}
 
 
/** Decode a #fr_value_box_t from one DNS label
 *
 * The output type is always FR_TYPE_STRING
 *
 * Note that the caller MUST call fr_dns_labels_network_verify(src, len, start)
 * before calling this function.  Otherwise bad things will happen.
 *
 * @param[in] ctx       Where to allocate any talloc buffers required.
 * @param[out] dst      value_box to write the result to.
 * @param[in] src       Start of the buffer containing DNS labels
 * @param[in] len       Length of the buffer to decode
 * @param[in] label     This particular label
 * @param[in] tainted   Whether the value came from a trusted source.
 * @param[in] lb        label tracking data structure
 * @return
 *      - >= 0 The number of network bytes consumed.
 *      - <0 on error.
 */
ssize_t fr_dns_label_to_value_box(TALLOC_CTX *ctx, fr_value_box_t *dst,
                                  uint8_t const *src, size_t len, uint8_t const *label,
                                  bool tainted, fr_dns_labels_t *lb)
{
        ssize_t slen;
        uint8_t const *after = label;
        uint8_t const *current, *next = NULL;
        uint8_t const *packet = src;
        uint8_t const *end = packet + len;
        uint8_t *p;
        char *q;
 
        if (!len) return -1;
 
        /*
         *      The label must be within the current buffer we're
         *      passed.
         */
        if ((label < src) || (label >= end)) return -1;
 
        /*
         *      The actual packet might start earlier than the buffer,
         *      so reset it if necessary.
         */
        if (lb) packet = lb->start;
 
        /*
         *      Get the uncompressed length of the label, and the
         *      label after this one.
         */
        slen = fr_dns_label_uncompressed_length(packet, src, len, &after, lb);
        if (slen <= 0) {
                FR_PROTO_TRACE("dns_label_to_value_box - Failed getting length");
                return slen;
        }
 
        fr_value_box_init_null(dst);
 
        /*
         *      An empty label is a 0x00 byte.  Just create an empty
         *      string.
         */
        if (slen == 1) {
                if (fr_value_box_bstr_alloc(ctx, &q, dst, NULL, 1, tainted) < 0) return -1;
                q[0] = '.';
                return after - label;
        }
 
        /*
         *      Allocate the string and set up the value_box
         */
        if (fr_value_box_bstr_alloc(ctx, &q, dst, NULL, slen, tainted) < 0) return -1;
 
        current = label;
        p = (uint8_t *) q;
        q += slen;
 
        while (current && (current < after) && (*current != 0x00)) {
                /*
                 *      Get how many bytes this label has, and where
                 *      we will go to obtain the next label.
                 */
                slen = dns_label_decode(packet, end, &current, &next);
                if (slen < 0) return slen;
 
                /*
                 *      As a sanity check, ensure we don't have a
                 *      buffer overflow.
                 */
                if ((p + slen) > (uint8_t *) q) {
                        FR_PROTO_TRACE("dns_label_to_value_box - length %zd Failed at %d", slen, __LINE__);
 
                fail:
                        fr_value_box_clear(dst);
                        return -1;
                }
 
                /*
                 *      Add '.' before the label, but only for the
                 *      second and subsequent labels.
                 */
                if (p != (uint8_t const *) dst->vb_strvalue) {
                        *(p++) = '.';
                }
 
                /*
                 *      Copy the raw bytes from the network.
                 */
                memcpy(p, current + 1, slen);
 
                /*
                 *      Go ahead in the output string, and go to the
                 *      next label for decoding.
                 */
                p += slen;
                current = next;
        }
 
        /*
         *      As a last sanity check, ensure that we've filled the
         *      buffer exactly.
         */
        if (p != (uint8_t *) q) {
                FR_PROTO_TRACE("dns_label_to_value_box - Failed at %d", __LINE__);
                goto fail;
        }
 
        *p = '\0';
 
        /*
         *      Return the number of network bytes used to parse this
         *      part of the label.
         */
        return after - label;
}