0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark AndrewsCopyright (C) 1999-2001, 2004, 2016 Internet Systems Consortium, Inc. ("ISC")
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark AndrewsThis Source Code Form is subject to the terms of the Mozilla Public
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark AndrewsLicense, v. 2.0. If a copy of the MPL was not distributed with this
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark Andrewsfile, You can obtain one at http://mozilla.org/MPL/2.0/.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews Name Compression
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews $Id: compression,v 1.9 2004/03/05 05:04:46 marka Exp $
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews BIND 4.x and BIND 8.x only had one methods of compression to deal
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews with 14 bit compression. BIND 9 has 3 methods of compression
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews to deal with 14 bit, 16 bit and local compression (14 and 16 bit).
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews In addition to this the allowed compression methods vary across
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews types and across client revisions thanks to EDNS.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews To be able to compress a domain name you need to some or all of
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews the following pieces of information.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews 1. where the message starts.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews 2. where the current rdata starts in the message (local compression).
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews 3. what the current owner name is (local compression).
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews 4. existing global 14 bit compression targets.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews 5. existing global 16 bit compression targets.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews 6. existing local compression targets.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews 7. the current domain name.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews 8. what are allowable compression methods, these are not constant
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews across a message.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews BIND 4.x and BIND 8.x used a table of existing 14 bit compression
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews The implicit assumption is that we will use compression whenever
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews possible and when ever there are multiple alternatives available
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews we will choose the one that minimises the size of the message.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews We will need functions that determine the allowable compression
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews methods, find the "best" match among the available compression
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews targets, add new compression targets.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews We need to be able to back out any changes made to the compression
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews targets if we are unable to add a complete RR (RRset?). This is
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews only a problem for the global compression targets.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark AndrewsImplementation:
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews We will maintain two RBT, one for local compression targets and
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews one for global compression targets. The data for these RBT will
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews be the offset values. The local compression RBT only needs to
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews be maintained when local compression is possible. The global
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews compression RBT is maintained regardless. Unless there is a
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews perfect match (or the name is ".") we will add the name to the
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews compression RBTs provide the offset would not be too large for
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews the valid compression methods of the RBT. All nodes of the RBT
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews will have an offset excluding the root node.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews The local compression RBT will be initalised with the owner name
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews and the start of the rdata will be recorded.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews We will use deepest partial match to find the potential
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews compression targets.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews We only need to maintain one global RBT as 16 bit compression
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews pointers are either valid or invalid for the whole message.
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews dns_rdata_towire() will set the allowed methods based on the
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews edns version.
dd3d17d3650d663ac16dcd3ba1f5d43557507e7cMark Andrews dns_result_t
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews dns_compress_init(dns_compress_t *cctx, int edns, isc_mem_t *mctx);
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews Initalises cctx to empty and sets whether 16 bit global
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews compression targets are to be added to the global RBT based on the
dd3d17d3650d663ac16dcd3ba1f5d43557507e7cMark Andrews dns_result_t
dd3d17d3650d663ac16dcd3ba1f5d43557507e7cMark Andrews dns_compress_localinit(dns_compress_t *cctx, dns_name_t *owner,
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews isc_buffer_t *target);
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews Initalise a RBT for local compression, freeing and existing RBT.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews Record current offset.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews dns_compress_invalidate(dns_compress_t *cctx);
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews Free any RBT's and make empty.
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews dns_compress_localinvalidate(dns_compress_t *cctx);
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews Free the local RBT.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews dns_compress_setmethods(dns_compress_t *cctx, unsigned int allowed);
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews unsigned int
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews dns_compress_getmethods(dns_compress_t *cctx);
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews dns_compress_getedns(dns_compress_t *cctx);
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews dns_result_t
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews dns_name_towire(dns_name_t *name, dns_compress_t *cctx,
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews isc_buffer_t *target);
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews 'name' contains the current name to be added to the message 'target'.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews 'target' is assumed to only contain the message.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews 'cctx' contains the compression context and has to hold all the
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews information required that cannot be obtained from 'name' or 'target'.
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews struct dns_compress {
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews unsigned int allowed; /* Allowed methods. */
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews unsigned int rdata; /* Start of local rdata */
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews isc_boolean_t global16; /* 16 bit offsets allowed */
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews dns_rbt_t *local; /* Local RBT */
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews dns_rbt_t *global; /* Global RBT */
d97e14cc78db916ad42bd3fa78d070504430a5f6Mark Andrews isc_mem_t *mctx; /* Required by RBT */
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews sets allowed based on the value of edns.
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews isc_boolean_t
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews dns_compress_findglobal(dns_compress_t *cctx, dns_name_t *name,
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews dns_name_t *prefix, dns_name_t *suffix,
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews isc_uint16_t *offset, isc_buffer_t *workspace);
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews isc_boolean_t
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews dns_compress_findlocal(dns_compress_t *cctx, dns_name_t *name,
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews dns_name_t *prefix, dns_name_t *suffix,
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews isc_uint16_t *offset, isc_buffer_t *workspace);
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews Find the best best match in the global / local RBT. Returns prefix,
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews suffix and offset of the bestmatch. Findglobal(), findlocal()
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews requires as workspace as it may be neccessary to spit a bit stream
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews label. The result prefix will be such that it can be added to the
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews wire format followed by a compression pointer pointing to offset.
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews Suffix is returned so that it is possible to add the compression
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews pointers via dns_compress_add().
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews dns_compress_add(dns_compress_t *cctx, dns_name_t *prefix,
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews dns_name_t *suffix, isc_uint16_t offset);
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews Add compression pointers pointing to lebels (if any) in prefix.
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews The offset to the first label is passed in offset.
dd3d17d3650d663ac16dcd3ba1f5d43557507e7cMark Andrews Requires RBT deepest match.
dd3d17d3650d663ac16dcd3ba1f5d43557507e7cMark Andrews Requires the ability to walk the RBT and remove any node which
dd3d17d3650d663ac16dcd3ba1f5d43557507e7cMark Andrews meets the removal condition.