Functions to manipulate DNS labels. More...

#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>

Include dependency graph for dns.c:

Go to the source code of this file.

Macros
#define	MAX_OFFSET (1 << 14)

Functions
static int	dns_label_add (fr_dns_labels_t lb, uint8_t const start, uint8_t const *end)

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)
	Compress "label" by looking at the label recursively. More...

static ssize_t	dns_label_decode (uint8_t const packet, uint8_t const end, uint8_t const start, uint8_t const next)

static void	dns_label_mark (fr_dns_labels_t lb, uint8_t const p)

static bool	dns_pointer_valid (fr_dns_labels_t *lb, uint16_t offset)

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)
	Encode a single value box of type string, serializing its contents to a dns label. More...

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)
	Encode a single value box of type string, serializing its contents to a dns label in a dbuff. More...

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)
	Decode a fr_value_box_t from one DNS label. More...

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)
	Get the uncompressed length of a DNS label in a network buffer. More...

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)
	Verify that a network buffer contains valid DNS labels. More...

static bool	labelcmp (uint8_t const a, uint8_t const b, size_t len)
	Compare two labels in a case-insensitive fashion. More...

Detailed Description

Functions to manipulate DNS labels.

Copyright: 2019 The FreeRADIUS server project; 2019 Network RADIUS SAS (legal.nosp@m.@net.nosp@m.workr.nosp@m.adiu.nosp@m.s.com)

Definition in file dns.c.

Macro Definition Documentation

◆ MAX_OFFSET

#define MAX_OFFSET (1 << 14)

Definition at line 32 of file dns.c.

Function Documentation

◆ dns_label_add()

static int dns_label_add	(	fr_dns_labels_t *	lb,
		uint8_t const *	start,
		uint8_t const *	end
	)

static

Definition at line 34 of file dns.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dns_label_compress()

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
	)

static

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.

Parameters

[in]	packet	where the packet starts
[in]	start	input buffer holding one or more labels
[in]	end	end of the input buffer
[out]	new_search	Where the parent call to dns_label_compress() should start searching from, instead of from "start".
[in]	label	label to add to the buffer.
[out]	label_end	updated end of the input label after compression.

Returns

false, we didn't compress the input
true, we did compress the input.

Definition at line 266 of file dns.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dns_label_decode()

static ssize_t dns_label_decode	(	uint8_t const *	packet,
		uint8_t const *	end,
		uint8_t const **	start,
		uint8_t const **	next
	)

static

Definition at line 1156 of file dns.c.

Here is the caller graph for this function:

◆ dns_label_mark()

static void dns_label_mark	(	fr_dns_labels_t *	lb,
		uint8_t const *	p
	)

static

Definition at line 98 of file dns.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dns_pointer_valid()

static bool dns_pointer_valid	(	fr_dns_labels_t *	lb,
		uint16_t	offset
	)

static

Definition at line 109 of file dns.c.

Here is the caller graph for this function:

◆ fr_dns_label_from_value_box()

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
	)

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.

Parameters

[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.
[out]	buf	Buffer where labels are stored
[in]	buf_len	The length of the output buffer
[out]	where	Where to write this label
[in]	compression	Whether or not to do DNS label compression.
[in]	value	to encode.
[in]	lb	label tracking data structure

Returns

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.

Definition at line 639 of file dns.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dns_label_from_value_box_dbuff()

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
	)

Encode a single value box of type string, serializing its contents to a dns label in a dbuff.

Parameters

[in]	dbuff	Buffer where labels are written
[in]	compression	Whether or not to do DNS label compression.
[in]	value	to encode.
[in]	lb	label tracking data structure.

Returns

>0 the number of bytes written to the dbuff
0 could not encode anything, an error has occurred.
<0 the number of bytes the dbuff should have had, instead of "remaining".

Definition at line 604 of file dns.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dns_label_to_value_box()

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
	)

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.

Parameters

[in]	ctx	Where to allocate any talloc buffers required.
[out]	dst	value_box to write the result to.
[in]	src	Start of the buffer containing DNS labels
[in]	len	Length of the buffer to decode
[in]	label	This particular label
[in]	tainted	Whether the value came from a trusted source.
[in]	lb	label tracking data structure

Returns

>= 0 The number of network bytes consumed.
<0 on error.

Definition at line 1225 of file dns.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dns_label_uncompressed_length()

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
	)

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 '.'

Parameters

[in]	packet	where the packet starts
[in]	buf	buffer holding one or more DNS labels
[in]	buf_len	total length of the buffer
[in,out]	next	the DNS label to check, updated to point to the next label
[in]	lb	label tracking data structure

Returns

<=0 on error, offset from buf where the invalid label is located.
> 0 decoded size of this particular DNS label

Definition at line 884 of file dns.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_dns_labels_network_verify()

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
	)

Verify that a network buffer contains valid DNS labels.

Parameters

[in]	packet	where the packet starts
[in]	buf	buffer holding one or more DNS labels
[in]	buf_len	total length of the buffer
[in]	start	where to start looking
[in]	lb	label tracking data structure

Returns

<=0 on error, where in the buffer the invalid label is located.
> 0 total size of the encoded label(s). Will be <= buf_len

Definition at line 1137 of file dns.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ labelcmp()

static bool labelcmp	(	uint8_t const *	a,
		uint8_t const *	b,
		size_t	len
	)

static

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.

Definition at line 140 of file dns.c.

Here is the caller graph for this function:

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ MAX_OFFSET

Function Documentation

◆ dns_label_add()

◆ dns_label_compress()

◆ dns_label_decode()

◆ dns_label_mark()

◆ dns_pointer_valid()

◆ fr_dns_label_from_value_box()

◆ fr_dns_label_from_value_box_dbuff()

◆ fr_dns_label_to_value_box()

◆ fr_dns_label_uncompressed_length()

◆ fr_dns_labels_network_verify()

◆ labelcmp()