Copyright (C) 1999, 2000 Internet Software Consortium.

See COPYRIGHT in the source root or http://www.isc.org/copyright for terms.

Name Compression

$Id: compression,v 1.6 2000/08/01 01:18:07 tale Exp $

Overview.

BIND 4.x and BIND 8.x only had one methods of compression to deal

with 14 bit compression. BIND 9 has 3 methods of compression

to deal with 14 bit, 16 bit and local compression (14 and 16 bit).

In addition to this the allowed compression methods vary across

types and across client revisions thanks to EDNS.

To be able to compress a domain name you need to some or all of

the following pieces of information.

1. where the message starts.

2. where the current rdata starts in the message (local compression).

3. what the current owner name is (local compression).

4. existing global 14 bit compression targets.

5. existing global 16 bit compression targets.

6. existing local compression targets.

7. the current domain name.

8. what are allowable compression methods, these are not constant

across a message.

BIND 4.x and BIND 8.x used a table of existing 14 bit compression

targets.

The implicit assumption is that we will use compression whenever

possible and when ever there are multiple alternatives available

we will choose the one that minimises the size of the message.

We will need functions that determine the allowable compression

methods, find the "best" match among the available compression

targets, add new compression targets.

We need to be able to back out any changes made to the compression

targets if we are unable to add a complete RR (RRset?). This is

only a problem for the global compression targets.

Implementation:

We will maintain two RBT, one for local compression targets and

one for global compression targets. The data for these RBT will

be the offset values. The local compression RBT only needs to

be maintained when local compression is possible. The global

compression RBT is maintained regardless. Unless there is a

perfect match (or the name is ".") we will add the name to the

compression RBTs provide the offset would not be too large for

the valid compression methods of the RBT. All nodes of the RBT

will have an offset excluding the root node.

The local compression RBT will be initalised with the owner name

and the start of the rdata will be recorded.

We will use deepest partial match to find the potential

compression targets.

We only need to maintain one global RBT as 16 bit compression

pointers are either valid or invalid for the whole message.

dns_rdata_towire() will set the allowed methods based on the

edns version.

Functions:

dns_result_t

dns_compress_init(dns_compress_t *cctx, int edns, isc_mem_t *mctx);

Initalises cctx to empty and sets whether 16 bit global

compression targets are to be added to the global RBT based on the

edns value.

dns_result_t

dns_compress_localinit(dns_compress_t *cctx, dns_name_t *owner,

isc_buffer_t *target);

Initalise a RBT for local compression, freeing and existing RBT.

Record current offset.

dns_compress_invalidate(dns_compress_t *cctx);

Free any RBT's and make empty.

dns_compress_localinvalidate(dns_compress_t *cctx);

Free the local RBT.

void

dns_compress_setmethods(dns_compress_t *cctx, unsigned int allowed);

unsigned int

dns_compress_getmethods(dns_compress_t *cctx);

int

dns_compress_getedns(dns_compress_t *cctx);

dns_result_t

dns_name_towire(dns_name_t *name, dns_compress_t *cctx,

isc_buffer_t *target);

'name' contains the current name to be added to the message 'target'.

'target' is assumed to only contain the message.

'cctx' contains the compression context and has to hold all the

information required that cannot be obtained from 'name' or 'target'.

struct dns_compress {

unsigned int allowed; /* Allowed methods. */

unsigned int rdata; /* Start of local rdata */

isc_boolean_t global16; /* 16 bit offsets allowed */

dns_rbt_t *local; /* Local RBT */

dns_rbt_t *global; /* Global RBT */

isc_mem_t *mctx; /* Required by RBT */

};

sets allowed based on the value of edns.

isc_boolean_t

dns_compress_findglobal(dns_compress_t *cctx, dns_name_t *name,

dns_name_t *prefix, dns_name_t *suffix,

isc_uint16_t *offset, isc_buffer_t *workspace);

isc_boolean_t

dns_compress_findlocal(dns_compress_t *cctx, dns_name_t *name,

dns_name_t *prefix, dns_name_t *suffix,

isc_uint16_t *offset, isc_buffer_t *workspace);

Find the best best match in the global / local RBT. Returns prefix,

suffix and offset of the bestmatch. Findglobal(), findlocal()

requires as workspace as it may be neccessary to spit a bit stream

label. The result prefix will be such that it can be added to the

wire format followed by a compression pointer pointing to offset.

Suffix is returned so that it is possible to add the compression

pointers via dns_compress_add().

void

dns_compress_add(dns_compress_t *cctx, dns_name_t *prefix,

dns_name_t *suffix, isc_uint16_t offset);

Add compression pointers pointing to lebels (if any) in prefix.

The offset to the first label is passed in offset.

Dependancy:

Requires RBT deepest match.

Requires the ability to walk the RBT and remove any node which

meets the removal condition.