Branch data Line data Source code
1 : : // Copyright (C) 2009 Internet Systems Consortium, Inc. ("ISC")
2 : : //
3 : : // Permission to use, copy, modify, and/or distribute this software for any
4 : : // purpose with or without fee is hereby granted, provided that the above
5 : : // copyright notice and this permission notice appear in all copies.
6 : : //
7 : : // THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
8 : : // REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
9 : : // AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
10 : : // INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
11 : : // LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
12 : : // OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
13 : : // PERFORMANCE OF THIS SOFTWARE.
14 : :
15 : : #include <exceptions/exceptions.h>
16 : : #include <util/buffer.h>
17 : : #include <dns/name.h>
18 : : #include <dns/name_internal.h>
19 : : #include <dns/labelsequence.h>
20 : : #include <dns/messagerenderer.h>
21 : :
22 : : #include <boost/array.hpp>
23 : : #include <boost/static_assert.hpp>
24 : :
25 : : #include <limits>
26 : : #include <cassert>
27 : : #include <vector>
28 : :
29 : : using namespace std;
30 : : using namespace isc::util;
31 : : using isc::dns::name::internal::maptolower;
32 : :
33 : : namespace isc {
34 : : namespace dns {
35 : :
36 : : namespace { // hide internal-only names from the public namespaces
37 : : ///
38 : : /// \brief The \c OffsetItem class represents a pointer to a name
39 : : /// rendered in the internal buffer for the \c MessageRendererImpl object.
40 : : ///
41 : : /// A \c MessageRendererImpl object maintains a set of \c OffsetItem
42 : : /// objects in a hash table, and searches the table for the position of the
43 : : /// longest match (ancestor) name against each new name to be rendered into
44 : : /// the buffer.
45 : 0 : struct OffsetItem {
46 : : OffsetItem(size_t hash, size_t pos, size_t len) :
47 : 3777 : hash_(hash), pos_(pos), len_(len)
48 : : {}
49 : :
50 : : /// The hash value for the stored name calculated by LabelSequence.getHash.
51 : : /// This will help make name comparison in \c NameCompare more efficient.
52 : : size_t hash_;
53 : :
54 : : /// The position (offset from the beginning) in the buffer where the
55 : : /// name starts.
56 : : uint16_t pos_;
57 : :
58 : : /// The length of the corresponding sequence (which is a domain name).
59 : : uint16_t len_;
60 : : };
61 : :
62 : : /// \brief The \c NameCompare class is a functor that checks equality
63 : : /// between the name corresponding to an \c OffsetItem object and the name
64 : : /// consists of labels represented by a \c LabelSequence object.
65 : : ///
66 : : /// Template parameter CASE_SENSITIVE determines whether to ignore the case
67 : : /// of the names. This policy doesn't change throughout the lifetime of
68 : : /// this object, so we separate these using template to avoid unnecessary
69 : : /// condition check.
70 : : template <bool CASE_SENSITIVE>
71 : : struct NameCompare {
72 : : /// \brief Constructor
73 : : ///
74 : : /// \param buffer The buffer for rendering used in the caller renderer
75 : : /// \param name_buf An input buffer storing the wire-format data of the
76 : : /// name to be newly rendered (and only that data).
77 : : /// \param hash The hash value for the name.
78 : : NameCompare(const OutputBuffer& buffer, InputBuffer& name_buf,
79 : : size_t hash) :
80 : : buffer_(&buffer), name_buf_(&name_buf), hash_(hash)
81 : : {}
82 : :
83 : 20105 : bool operator()(const OffsetItem& item) const {
84 : : // Trivial inequality check. If either the hash or the total length
85 : : // doesn't match, the names are obviously different.
86 [ + + ][ + - ]: 20105 : if (item.hash_ != hash_ || item.len_ != name_buf_->getLength()) {
[ + + ][ + + ]
[ + - ][ + + ]
87 : : return (false);
88 : : }
89 : :
90 : : // Compare the name data, character-by-character.
91 : : // item_pos keeps track of the position in the buffer corresponding to
92 : : // the character to compare. item_label_len is the number of
93 : : // characters in the labels where the character pointed by item_pos
94 : : // belongs. When it reaches zero, nextPosition() identifies the
95 : : // position for the subsequent label, taking into account name
96 : : // compression, and resets item_label_len to the length of the new
97 : : // label.
98 : 2275 : name_buf_->setPosition(0); // buffer can be reused, so reset position
99 : 2275 : uint16_t item_pos = item.pos_;
100 : 2275 : uint16_t item_label_len = 0;
101 [ + + ][ + + ]: 47487 : for (size_t i = 0; i < item.len_; ++i, ++item_pos) {
102 : 54764 : item_pos = nextPosition(*buffer_, item_pos, item_label_len);
103 : 27382 : const unsigned char ch1 = (*buffer_)[item_pos];
104 : 27382 : const unsigned char ch2 = name_buf_->readUint8();
105 : : if (CASE_SENSITIVE) {
106 [ + - ]: 2999 : if (ch1 != ch2) {
107 : : return (false);
108 : : }
109 : : } else {
110 [ + - ]: 24383 : if (maptolower[ch1] != maptolower[ch2]) {
111 : : return (false);
112 : : }
113 : : }
114 : : }
115 : :
116 : : return (true);
117 : : }
118 : :
119 : : private:
120 : 0 : uint16_t nextPosition(const OutputBuffer& buffer,
121 : : uint16_t pos, uint16_t& llen) const
122 : : {
123 [ # # ][ # # ]: 27382 : if (llen == 0) {
[ + + ][ + + ]
124 : : size_t i = 0;
125 : :
126 [ # # ][ # # ]: 6370 : while ((buffer[pos] & Name::COMPRESS_POINTER_MARK8) ==
[ + + ][ + + ]
127 : : Name::COMPRESS_POINTER_MARK8) {
128 : 134 : pos = (buffer[pos] & ~Name::COMPRESS_POINTER_MARK8) *
129 : : 256 + buffer[pos + 1];
130 : :
131 : : // This loop should stop as long as the buffer has been
132 : : // constructed validly and the search/insert argument is based
133 : : // on a valid name, which is an assumption for this class.
134 : : // But we'll abort if a bug could cause an infinite loop.
135 : 134 : i += 2;
136 [ # # ][ # # ]: 6370 : assert(i < Name::MAX_WIRE);
[ - + ][ - + ]
137 : : }
138 : 6236 : llen = buffer[pos];
139 : : } else {
140 : 21146 : --llen;
141 : : }
142 : 0 : return (pos);
143 : : }
144 : :
145 : : const OutputBuffer* buffer_;
146 : : InputBuffer* name_buf_;
147 : : const size_t hash_;
148 : : };
149 : : }
150 : :
151 : : ///
152 : : /// \brief The \c MessageRendererImpl class is the actual implementation of
153 : : /// \c MessageRenderer.
154 : : ///
155 : : /// The implementation is hidden from applications. We can refer to specific
156 : : /// members of this class only within the implementation source file.
157 : : ///
158 : : /// It internally holds a hash table for OffsetItem objects corresponding
159 : : /// to portions of names rendered in this renderer. The offset information
160 : : /// is used to compress subsequent names to be rendered.
161 [ + - ][ + + ]: 79560 : struct MessageRenderer::MessageRendererImpl {
162 : : // The size of hash buckets and number of hash entries per bucket for
163 : : // which space is preallocated and kept reserved for subsequent rendering
164 : : // to provide better performance. These values are derived from the
165 : : // BIND 9 implementation that uses a similar hash table.
166 : : static const size_t BUCKETS = 64;
167 : : static const size_t RESERVED_ITEMS = 16;
168 : : static const uint16_t NO_OFFSET = 65535; // used as a marker of 'not found'
169 : :
170 : : /// \brief Constructor
171 : : MessageRendererImpl() :
172 : : msglength_limit_(512), truncated_(false),
173 [ + + ]: 79560 : compress_mode_(MessageRenderer::CASE_INSENSITIVE)
174 : : {
175 : : // Reserve some spaces for hash table items.
176 [ + + ]: 79560 : for (size_t i = 0; i < BUCKETS; ++i) {
177 [ + - ]: 78336 : table_[i].reserve(RESERVED_ITEMS);
178 : : }
179 [ # # ][ # # ]: 0 : }
180 : :
181 : : uint16_t findOffset(const OutputBuffer& buffer, InputBuffer& name_buf,
182 : : size_t hash, bool case_sensitive) const
183 : : {
184 : : // Find a matching entry, if any. We use some heuristics here: often
185 : : // the same name appers consecutively (like repeating the same owner
186 : : // name for a single RRset), so in case there's a collision in the
187 : : // bucket it will be more likely to find it in the tail side of the
188 : : // bucket.
189 : 6069 : const size_t bucket_id = hash % BUCKETS;
190 : : vector<OffsetItem>::const_reverse_iterator found;
191 [ + + ]: 6069 : if (case_sensitive) {
192 : : found = find_if(table_[bucket_id].rbegin(),
193 : : table_[bucket_id].rend(),
194 : 1087 : NameCompare<true>(buffer, name_buf, hash));
195 : : } else {
196 : : found = find_if(table_[bucket_id].rbegin(),
197 : : table_[bucket_id].rend(),
198 : 4982 : NameCompare<false>(buffer, name_buf, hash));
199 : : }
200 [ + + ]: 6069 : if (found != table_[bucket_id].rend()) {
201 : 2275 : return (found->pos_);
202 : : }
203 : : return (NO_OFFSET);
204 : : }
205 : :
206 : : void addOffset(size_t hash, size_t offset, size_t len) {
207 : 3777 : table_[hash % BUCKETS].push_back(OffsetItem(hash, offset, len));
208 : : }
209 : :
210 : : // The hash table for the (offset + position in the buffer) entries
211 : : vector<OffsetItem> table_[BUCKETS];
212 : : /// The maximum length of rendered data that can fit without
213 : : /// truncation.
214 : : uint16_t msglength_limit_;
215 : : /// A boolean flag that indicates truncation has occurred while rendering
216 : : /// the data.
217 : : bool truncated_;
218 : : /// The name compression mode.
219 : : CompressMode compress_mode_;
220 : :
221 : : // Placeholder for hash values as they are calculated in writeName().
222 : : // Note: we may want to make it a local variable of writeName() if it
223 : : // works more efficiently.
224 : : boost::array<size_t, Name::MAX_LABELS> seq_hashes_;
225 : : };
226 : :
227 : 1224 : MessageRenderer::MessageRenderer() :
228 : : AbstractMessageRenderer(),
229 [ + - ]: 1224 : impl_(new MessageRendererImpl)
230 : 1224 : {}
231 : :
232 : 1224 : MessageRenderer::~MessageRenderer() {
233 [ + - ]: 2448 : delete impl_;
234 : 1683 : }
235 : :
236 : : void
237 : 630 : MessageRenderer::clear() {
238 : 630 : AbstractMessageRenderer::clear();
239 : 630 : impl_->msglength_limit_ = 512;
240 : 630 : impl_->truncated_ = false;
241 : 630 : impl_->compress_mode_ = CASE_INSENSITIVE;
242 : :
243 : : // Clear the hash table. We reserve the minimum space for possible
244 : : // subsequent use of the renderer.
245 [ + + ]: 40950 : for (size_t i = 0; i < MessageRendererImpl::BUCKETS; ++i) {
246 [ + + ]: 40320 : if (impl_->table_[i].size() > MessageRendererImpl::RESERVED_ITEMS) {
247 : : // Trim excessive capacity: swap ensures the new capacity is only
248 : : // reasonably large for the reserved space.
249 : : vector<OffsetItem> new_table;
250 [ + - ]: 28 : new_table.reserve(MessageRendererImpl::RESERVED_ITEMS);
251 : 28 : new_table.swap(impl_->table_[i]);
252 : : }
253 : 40320 : impl_->table_[i].clear();
254 : : }
255 : 630 : }
256 : :
257 : : size_t
258 : 3662 : MessageRenderer::getLengthLimit() const {
259 : 3662 : return (impl_->msglength_limit_);
260 : : }
261 : :
262 : : void
263 : 502 : MessageRenderer::setLengthLimit(const size_t len) {
264 : 502 : impl_->msglength_limit_ = len;
265 : 502 : }
266 : :
267 : : bool
268 : 5177 : MessageRenderer::isTruncated() const {
269 : 5177 : return (impl_->truncated_);
270 : : }
271 : :
272 : : void
273 : 21 : MessageRenderer::setTruncated() {
274 : 21 : impl_->truncated_ = true;
275 : 21 : }
276 : :
277 : : MessageRenderer::CompressMode
278 : 927 : MessageRenderer::getCompressMode() const {
279 : 927 : return (impl_->compress_mode_);
280 : : }
281 : :
282 : : void
283 : 152 : MessageRenderer::setCompressMode(const CompressMode mode) {
284 [ + + ]: 152 : if (getLength() != 0) {
285 [ + - ][ + - ]: 2 : isc_throw(isc::InvalidParameter,
286 : : "compress mode cannot be changed during rendering");
287 : : }
288 : 151 : impl_->compress_mode_ = mode;
289 : 151 : }
290 : :
291 : : void
292 : 3441 : MessageRenderer::writeName(const Name& name, const bool compress) {
293 : : LabelSequence sequence(name);
294 : 6882 : const size_t nlabels = sequence.getLabelCount();
295 : : size_t data_len;
296 : : const char* data;
297 : :
298 : : // Find the offset in the offset table whose name gives the longest
299 : : // match against the name to be rendered.
300 : : size_t nlabels_uncomp;
301 : 3441 : uint16_t ptr_offset = MessageRendererImpl::NO_OFFSET;
302 : : const bool case_sensitive = (impl_->compress_mode_ ==
303 : 3441 : MessageRenderer::CASE_SENSITIVE);
304 [ + - ]: 7235 : for (nlabels_uncomp = 0; nlabels_uncomp < nlabels; ++nlabels_uncomp) {
305 : 7235 : data = sequence.getData(&data_len);
306 [ + + ]: 7235 : if (data_len == 1) { // trailing dot.
307 : 1166 : ++nlabels_uncomp;
308 : 1166 : break;
309 : : }
310 : : // write with range check for safety
311 : 6069 : impl_->seq_hashes_.at(nlabels_uncomp) =
312 : 6069 : sequence.getHash(impl_->compress_mode_);
313 : 6069 : InputBuffer name_buf(data, data_len);
314 : : ptr_offset = impl_->findOffset(getBuffer(), name_buf,
315 : 6069 : impl_->seq_hashes_[nlabels_uncomp],
316 : 18207 : case_sensitive);
317 [ + + ]: 6069 : if (ptr_offset != MessageRendererImpl::NO_OFFSET) {
318 : : break;
319 : : }
320 : 3794 : sequence.stripLeft(1);
321 : : }
322 : :
323 : : // Record the current offset before updating the offset table
324 : 3441 : size_t offset = getLength();
325 : : // Write uncompress part:
326 [ + + ][ + + ]: 3441 : if (nlabels_uncomp > 0 || !compress) {
327 : : LabelSequence uncomp_sequence(name);
328 [ + + ][ + + ]: 2660 : if (compress && nlabels > nlabels_uncomp) {
329 : : // If there's compressed part, strip off that part.
330 : 1338 : uncomp_sequence.stripRight(nlabels - nlabels_uncomp);
331 : : }
332 : 2660 : data = uncomp_sequence.getData(&data_len);
333 : 2660 : writeData(data, data_len);
334 : : }
335 : : // And write compression pointer if available:
336 [ + + ][ + + ]: 3441 : if (compress && ptr_offset != MessageRendererImpl::NO_OFFSET) {
337 : 2119 : ptr_offset |= Name::COMPRESS_POINTER_MARK16;
338 : 2119 : writeUint16(ptr_offset);
339 : : }
340 : :
341 : : // Finally, record the offset and length for each uncompressed sequence
342 : : // in the hash table. The renderer's buffer has just stored the
343 : : // corresponding data, so we use the rendered data to get the length
344 : : // of each label of the names.
345 : 3441 : size_t seqlen = name.getLength();
346 [ + + ]: 7218 : for (size_t i = 0; i < nlabels_uncomp; ++i) {
347 : 4943 : const uint8_t label_len = getBuffer()[offset];
348 [ + + ]: 4943 : if (label_len == 0) { // offset for root doesn't need to be stored.
349 : : break;
350 : : }
351 [ + + ]: 3783 : if (offset > Name::MAX_COMPRESS_POINTER) {
352 : : break;
353 : : }
354 : : // Store the tuple of <hash, offset, len> to the table. Note that we
355 : : // already know the hash value for each name.
356 : 7554 : impl_->addOffset(impl_->seq_hashes_[i], offset, seqlen);
357 : 3777 : offset += (label_len + 1);
358 : 3777 : seqlen -= (label_len + 1);
359 : : }
360 : 3441 : }
361 : :
362 : 1232 : AbstractMessageRenderer::AbstractMessageRenderer() :
363 : 2464 : local_buffer_(0), buffer_(&local_buffer_)
364 : : {
365 : 1232 : }
366 : :
367 : : void
368 : 674 : AbstractMessageRenderer::setBuffer(OutputBuffer* buffer) {
369 [ + + ][ + + ]: 674 : if (buffer != NULL && buffer_->getLength() != 0) {
[ + + ]
370 [ + - ][ + - ]: 4 : isc_throw(isc::InvalidParameter,
371 : : "MessageRenderer buffer cannot be set when in use");
372 [ + + ][ + + ]: 672 : } if (buffer == NULL && buffer_ == &local_buffer_) {
373 [ + - ][ + - ]: 2 : isc_throw(isc::InvalidParameter,
374 : : "Default MessageRenderer buffer cannot be reset");
375 : : }
376 : :
377 [ + + ]: 671 : if (buffer == NULL) {
378 : : // Reset to the default buffer, then clear other internal resources.
379 : : // The order is important; we need to keep the used buffer intact.
380 : 322 : buffer_ = &local_buffer_;
381 : 322 : clear();
382 : : } else {
383 : 349 : buffer_ = buffer;
384 : : }
385 : 671 : }
386 : :
387 : : void
388 : 630 : AbstractMessageRenderer::clear() {
389 : 630 : buffer_->clear();
390 : 630 : }
391 : :
392 : : }
393 : 414193 : }
|
