compression revision 52637f592f705ca93fadc218e403fd55e8ce4aea
fa9e4066f08beec538e775443c5be79dd423fcabahrens Name Compression
ea8dc4b6d2251b437950c0056bc626b311c73c27eschrock BIND 4.x and BIND 8.x only had one methods of compression to deal
fa9e4066f08beec538e775443c5be79dd423fcabahrens with 14 bit compression. BIND 9 has 3 methods of compression
fa9e4066f08beec538e775443c5be79dd423fcabahrens to deal with 14 bit, 16 bit and local compression (14 and 16 bit).
fa9e4066f08beec538e775443c5be79dd423fcabahrens In addition to this the allowed compression methods vary across
fa9e4066f08beec538e775443c5be79dd423fcabahrens types and across client revisions thanks to EDNS.
fa9e4066f08beec538e775443c5be79dd423fcabahrens To be able to compress a domain name you need to some or all of
fa9e4066f08beec538e775443c5be79dd423fcabahrens the following pieces of information.
fa9e4066f08beec538e775443c5be79dd423fcabahrens 1. where the message starts.
fa9e4066f08beec538e775443c5be79dd423fcabahrens 2. where the current rdata starts in the message (local compression).
fa9e4066f08beec538e775443c5be79dd423fcabahrens 3. what the current owner name is (local compression).
fa9e4066f08beec538e775443c5be79dd423fcabahrens 4. existing global 14 bit compression targets.
fa9e4066f08beec538e775443c5be79dd423fcabahrens 5. existing global 16 bit compression targets.
fa9e4066f08beec538e775443c5be79dd423fcabahrens 6. existing local compression targets.
3f9d6ad73e45c6823b409f93b0c8d4f62861d2d5Lin Ling 7. the current domain name.
ca0cc3918a1789fa839194af2a9245f801a06b1aMatthew Ahrens 8. what are allowable compression methods, these are not constant
a2afb611b30628fb74ad9eade4ae465f9031e262Jerry Jelinek across a message.
bc9014e6a81272073b9854d9f65dd59e18d18c35Justin Gibbs BIND 4.x and BIND 8.x used a table of existing 14 bit compression
fa9e4066f08beec538e775443c5be79dd423fcabahrens The implicit assumption is that we will use compression whenever
fa9e4066f08beec538e775443c5be79dd423fcabahrens possible and when ever there are multiple alternatives available
fa9e4066f08beec538e775443c5be79dd423fcabahrens we will choose the one that minimises the size of the message.
fa9e4066f08beec538e775443c5be79dd423fcabahrens We will need functions that determine the allowable compression
fa9e4066f08beec538e775443c5be79dd423fcabahrens methods, find the "best" match among the available compression
fa9e4066f08beec538e775443c5be79dd423fcabahrens targets, add new compression targets.
fa9e4066f08beec538e775443c5be79dd423fcabahrens We need to be able to back out any changes made to the compression
1d452cf5123cb6ac0a013a4dbd4dcceeb0da314dahrens targets if we are unable to add a complete RR (RRset?). This is
fa9e4066f08beec538e775443c5be79dd423fcabahrens only a problem for the global compression targets.
3b2aab18808792cbd248a12f1edf139b89833c13Matthew AhrensImplementation:
ca0cc3918a1789fa839194af2a9245f801a06b1aMatthew Ahrens We will maintain two RBT, one for local compression targets and
fa9e4066f08beec538e775443c5be79dd423fcabahrens one for global compression targets. The data for these RBT will
fa9e4066f08beec538e775443c5be79dd423fcabahrens be the offset values. The local compression RBT only needs to
fa9e4066f08beec538e775443c5be79dd423fcabahrens be maintained when local compression is possible. The global
fa9e4066f08beec538e775443c5be79dd423fcabahrens compression RBT is maintained regardless. Unless there is a
fa9e4066f08beec538e775443c5be79dd423fcabahrens perfect match (or the name is ".") we will add the name to the
fa9e4066f08beec538e775443c5be79dd423fcabahrens compression RBTs provide the offset would not be too large for
fa9e4066f08beec538e775443c5be79dd423fcabahrens the valid compression methods of the RBT. All nodes of the RBT
fa9e4066f08beec538e775443c5be79dd423fcabahrens will have an offset excluding the root node.
99653d4ee642c6528e88224f12409a5f23060994eschrock The local compression RBT will be initalised with the owner name
745cd3c5371d020efae7a911c58c526aa1fd0dbamaybee and the start of the rdata will be recorded.
2acef22db7808606888f8f92715629ff3ba555b9Matthew Ahrens We will use deepest partial match to find the potential
99653d4ee642c6528e88224f12409a5f23060994eschrock compression targets.
99653d4ee642c6528e88224f12409a5f23060994eschrock We only need to maintain one global RBT as 16 bit compression
99653d4ee642c6528e88224f12409a5f23060994eschrock pointers are either valid or invalid for the whole message.
a9799022bd90b13722204e80112efaa5bf573099ck dns_rdata_towire() will set the allowed methods based on the
a9799022bd90b13722204e80112efaa5bf573099ck edns version.
a9799022bd90b13722204e80112efaa5bf573099ck dns_result_t
a9799022bd90b13722204e80112efaa5bf573099ck dns_compress_init(dns_compress_t *cctx, int edns, isc_mem_t *mctx);
842727c2f41f01b380de4f5e787d905702870f23Chris Kirby Initalises cctx to empty and sets whether 16 bit global
842727c2f41f01b380de4f5e787d905702870f23Chris Kirby compression targets are to be added to the global RBT based on the
842727c2f41f01b380de4f5e787d905702870f23Chris Kirby dns_result_t
c1379625401dfbe1c39b79136dd384a571d47fdeJustin T. Gibbs dns_compress_localinit(dns_compress_t *cctx, dns_name_t *owner,
842727c2f41f01b380de4f5e787d905702870f23Chris Kirby isc_buffer_t *target);
2acef22db7808606888f8f92715629ff3ba555b9Matthew Ahrens Initalise a RBT for local compression, freeing and existing RBT.
2acef22db7808606888f8f92715629ff3ba555b9Matthew Ahrens Record current offset.
2acef22db7808606888f8f92715629ff3ba555b9Matthew Ahrens dns_compress_invalidate(dns_compress_t *cctx);
78f171005391b928aaf1642b3206c534ed644332Matthew Ahrens Free any RBT's and make empty.
78f171005391b928aaf1642b3206c534ed644332Matthew Ahrens dns_compress_localinvalidate(dns_compress_t *cctx);
78f171005391b928aaf1642b3206c534ed644332Matthew Ahrens Free the local RBT.
9c3fd1216fa7fb02cfbc78a2518a686d54b48ab8Matthew Ahrens dns_compress_setmethods(dns_compress_t *cctx, unsigned int allowed);
9c3fd1216fa7fb02cfbc78a2518a686d54b48ab8Matthew Ahrens dns_compress_getmethods(dns_compress_t *cctx);
9c3fd1216fa7fb02cfbc78a2518a686d54b48ab8Matthew Ahrens dns_compress_getedns(dns_compress_t *cctx);
5602294fda888d923d57a78bafdaf48ae6223deaDan Kimmel dns_name_towire(dns_name_t *name, dns_compress_t *cctx,
9c3fd1216fa7fb02cfbc78a2518a686d54b48ab8Matthew Ahrens isc_buffer_t *target);
9c3fd1216fa7fb02cfbc78a2518a686d54b48ab8Matthew Ahrens 'name' contains the current name to be added to the message 'target'.
ab04eb8ef60d9dc9614d6cccffc474f24ca1d162timh 'target' is assumed to only contain the message.
ab04eb8ef60d9dc9614d6cccffc474f24ca1d162timh 'cctx' contains the compression context and has to hold all the
ab04eb8ef60d9dc9614d6cccffc474f24ca1d162timh information required that cannot be obtained from 'name' or 'target'.
ab04eb8ef60d9dc9614d6cccffc474f24ca1d162timh struct dns_compress {
ab04eb8ef60d9dc9614d6cccffc474f24ca1d162timh unsigned int allowed; /* Allowed methods. */
3b2aab18808792cbd248a12f1edf139b89833c13Matthew Ahrens unsigned int rdata; /* Start of local rdata */
3b2aab18808792cbd248a12f1edf139b89833c13Matthew Ahrens isc_boolean_t global16; /* 16 bit offsets allowed */
fa9e4066f08beec538e775443c5be79dd423fcabahrens dns_rbt_t *local; /* Local RBT */
088f389458728c464569a5506b58070254fa4f7dahrens dns_rbt_t *global; /* Global RBT */
088f389458728c464569a5506b58070254fa4f7dahrens isc_mem_t *mctx; /* Required by RBT */
088f389458728c464569a5506b58070254fa4f7dahrens sets allowed based on the value of edns.
fa9e4066f08beec538e775443c5be79dd423fcabahrens isc_boolean_t
fa9e4066f08beec538e775443c5be79dd423fcabahrens dns_compress_findglobal(dns_compress_t *cctx, dns_name_t *name,
cde58dbc6a23d4d38db7c8866312be83221c765fMatthew Ahrens dns_name_t *prefix, dns_name_t *suffix,
ad135b5d644628e791c3188a6ecbd9c257961ef8Christopher Siden isc_uint16_t *offset, isc_buffer_t *workspace);
ad135b5d644628e791c3188a6ecbd9c257961ef8Christopher Siden dns_compress_findlocal(dns_compress_t *cctx, dns_name_t *name,
ad135b5d644628e791c3188a6ecbd9c257961ef8Christopher Siden dns_name_t *prefix, dns_name_t *suffix,
ad135b5d644628e791c3188a6ecbd9c257961ef8Christopher Siden isc_uint16_t *offset, isc_buffer_t *workspace);
fa9e4066f08beec538e775443c5be79dd423fcabahrens Find the best best match in the global / local RBT. Returns prefix,
63360950109af2ce85a962ca61f40b8782f11100mp suffix and offset of the bestmatch. Findglobal(), findlocal()
fa9e4066f08beec538e775443c5be79dd423fcabahrens requires as workspace as it may be neccessary to spit a bit stream
fa9e4066f08beec538e775443c5be79dd423fcabahrens label. The result prefix will be such that it can be added to the
fa9e4066f08beec538e775443c5be79dd423fcabahrens wire format followed by a compression pointer pointing to offset.
fa9e4066f08beec538e775443c5be79dd423fcabahrens Suffix is returned so that it is possible to add the compression
fa9e4066f08beec538e775443c5be79dd423fcabahrens pointers via dns_compress_add().
088f389458728c464569a5506b58070254fa4f7dahrens dns_compress_add(dns_compress_t *cctx, dns_name_t *prefix,
fa9e4066f08beec538e775443c5be79dd423fcabahrens dns_name_t *suffix, isc_uint16_t offset);
bb0ade0978a02d3fe0b0165cd4725fdcb593fbfbahrens Add compression pointers pointing to lebels (if any) in prefix.
842727c2f41f01b380de4f5e787d905702870f23Chris Kirby The offset to the first label is passed in offset.
fa9e4066f08beec538e775443c5be79dd423fcabahrens Requires RBT deepest match.
bc9014e6a81272073b9854d9f65dd59e18d18c35Justin Gibbs Requires the ability to walk the RBT and remove any node which
c166b69d29138aed7a415fe7cef698e54c6ae945Paul Dagnelie meets the removal condition.