compression 5.06 KB
Newer Older
Mark Andrews's avatar
Mark Andrews committed
1
2
3

			Name Compression

Mark Andrews's avatar
Mark Andrews committed
4
5
	$Id: compression,v 1.4 1999/02/24 00:59:44 marka Exp $

Mark Andrews's avatar
Mark Andrews committed
6
7
8
9
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
Mark Andrews's avatar
Mark Andrews committed
10
	to deal with 14 bit, 16 bit and local compression (14 and 16 bit).
Mark Andrews's avatar
Mark Andrews committed
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

	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.

Mark Andrews's avatar
Mark Andrews committed
64
65
	dns_rdata_towire() will set the allowed methods based on the
	edns version.
Mark Andrews's avatar
Mark Andrews committed
66

Mark Andrews's avatar
Mark Andrews committed
67
Functions:
Mark Andrews's avatar
Mark Andrews committed
68

69
	dns_result_t
Mark Andrews's avatar
Mark Andrews committed
70
	dns_compress_init(dns_compress_t *cctx, int edns, isc_mem_t *mctx);
Mark Andrews's avatar
Mark Andrews committed
71
72

	Initalises cctx to empty and sets whether 16 bit global
Mark Andrews's avatar
Mark Andrews committed
73
74
	compression targets are to be added to the global RBT based on the
	edns value.
Mark Andrews's avatar
Mark Andrews committed
75

76
77
	dns_result_t
	dns_compress_localinit(dns_compress_t *cctx, dns_name_t *owner,
Mark Andrews's avatar
Mark Andrews committed
78
79
80
81
82
83
84
85
86
			       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.

Mark Andrews's avatar
Mark Andrews committed
87
88
89
90
	dns_compress_localinvalidate(dns_compress_t *cctx);

	Free the local RBT.

Mark Andrews's avatar
Mark Andrews committed
91
92
93
94
95
96
	void
	dns_compress_setmethods(dns_compress_t *cctx, unsigned int allowed);

	unsigned int
	dns_compress_getmethods(dns_compress_t *cctx);

Mark Andrews's avatar
Mark Andrews committed
97
98
99
	int
	dns_compress_getedns(dns_compress_t *cctx);

Mark Andrews's avatar
Mark Andrews committed
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
	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 */
	};
117

Mark Andrews's avatar
Mark Andrews committed
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
	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.

145
146
147
148
149
Dependancy:

	Requires RBT deepest match.
	Requires the ability to walk the RBT and remove any node which
	meets the removal condition.