Kea  2.1.7-git
messagerenderer.cc
Go to the documentation of this file.
1 // Copyright (C) 2009-2015 Internet Systems Consortium, Inc. ("ISC")
2 //
3 // This Source Code Form is subject to the terms of the Mozilla Public
4 // License, v. 2.0. If a copy of the MPL was not distributed with this
5 // file, You can obtain one at http://mozilla.org/MPL/2.0/.
6 
7 #include <config.h>
8 
10 #include <util/buffer.h>
11 #include <dns/name.h>
12 #include <dns/name_internal.h>
13 #include <dns/labelsequence.h>
14 #include <dns/messagerenderer.h>
15 
16 #include <boost/array.hpp>
17 #include <boost/static_assert.hpp>
18 
19 #include <limits>
20 #include <cassert>
21 #include <vector>
22 
23 using namespace std;
24 using namespace isc::util;
26 
27 namespace isc {
28 namespace dns {
29 
30 namespace { // hide internal-only names from the public namespaces
39 struct OffsetItem {
40  OffsetItem(size_t hash, size_t pos, size_t len) :
41  hash_(hash), pos_(pos), len_(len)
42  {}
43 
46  size_t hash_;
47 
50  uint16_t pos_;
51 
53  uint16_t len_;
54 };
55 
64 template <bool CASE_SENSITIVE>
65 struct NameCompare {
72  NameCompare(const OutputBuffer& buffer, InputBuffer& name_buf,
73  size_t hash) :
74  buffer_(&buffer), name_buf_(&name_buf), hash_(hash)
75  {}
76 
77  bool operator()(const OffsetItem& item) const {
78  // Trivial inequality check. If either the hash or the total length
79  // doesn't match, the names are obviously different.
80  if (item.hash_ != hash_ || item.len_ != name_buf_->getLength()) {
81  return (false);
82  }
83 
84  // Compare the name data, character-by-character.
85  // item_pos keeps track of the position in the buffer corresponding to
86  // the character to compare. item_label_len is the number of
87  // characters in the labels where the character pointed by item_pos
88  // belongs. When it reaches zero, nextPosition() identifies the
89  // position for the subsequent label, taking into account name
90  // compression, and resets item_label_len to the length of the new
91  // label.
92  name_buf_->setPosition(0); // buffer can be reused, so reset position
93  uint16_t item_pos = item.pos_;
94  uint16_t item_label_len = 0;
95  for (size_t i = 0; i < item.len_; ++i, ++item_pos) {
96  item_pos = nextPosition(*buffer_, item_pos, item_label_len);
97  const uint8_t ch1 = (*buffer_)[item_pos];
98  const uint8_t ch2 = name_buf_->readUint8();
99  if (CASE_SENSITIVE) {
100  if (ch1 != ch2) {
101  return (false);
102  }
103  } else {
104  if (maptolower[ch1] != maptolower[ch2]) {
105  return (false);
106  }
107  }
108  }
109 
110  return (true);
111  }
112 
113 private:
114  static uint16_t nextPosition(const OutputBuffer& buffer,
115  uint16_t pos, uint16_t& llen)
116  {
117  if (llen == 0) {
118  size_t i = 0;
119 
120  while ((buffer[pos] & Name::COMPRESS_POINTER_MARK8) ==
121  Name::COMPRESS_POINTER_MARK8) {
122  pos = (buffer[pos] & ~Name::COMPRESS_POINTER_MARK8) *
123  256 + buffer[pos + 1];
124 
125  // This loop should stop as long as the buffer has been
126  // constructed validly and the search/insert argument is based
127  // on a valid name, which is an assumption for this class.
128  // But we'll abort if a bug could cause an infinite loop.
129  i += 2;
130  assert(i < Name::MAX_WIRE);
131  }
132  llen = buffer[pos];
133  } else {
134  --llen;
135  }
136  return (pos);
137  }
138 
139  const OutputBuffer* buffer_;
140  InputBuffer* name_buf_;
141  const size_t hash_;
142 };
143 }
144 
156  // The size of hash buckets and number of hash entries per bucket for
157  // which space is preallocated and kept reserved for subsequent rendering
158  // to provide better performance. These values are derived from the
159  // BIND 9 implementation that uses a similar hash table.
160  static const size_t BUCKETS = 64;
161  static const size_t RESERVED_ITEMS = 16;
162  static const uint16_t NO_OFFSET = 65535; // used as a marker of 'not found'
163 
166  msglength_limit_(512), truncated_(false),
167  compress_mode_(MessageRenderer::CASE_INSENSITIVE)
168  {
169  // Reserve some spaces for hash table items.
170  for (size_t i = 0; i < BUCKETS; ++i) {
171  table_[i].reserve(RESERVED_ITEMS);
172  }
173  }
174 
175  uint16_t findOffset(const OutputBuffer& buffer, InputBuffer& name_buf,
176  size_t hash, bool case_sensitive) const
177  {
178  // Find a matching entry, if any. We use some heuristics here: often
179  // the same name appears consecutively (like repeating the same owner
180  // name for a single RRset), so in case there's a collision in the
181  // bucket it will be more likely to find it in the tail side of the
182  // bucket.
183  const size_t bucket_id = hash % BUCKETS;
184  vector<OffsetItem>::const_reverse_iterator found;
185  if (case_sensitive) {
186  found = find_if(table_[bucket_id].rbegin(),
187  table_[bucket_id].rend(),
188  NameCompare<true>(buffer, name_buf, hash));
189  } else {
190  found = find_if(table_[bucket_id].rbegin(),
191  table_[bucket_id].rend(),
192  NameCompare<false>(buffer, name_buf, hash));
193  }
194  if (found != table_[bucket_id].rend()) {
195  return (found->pos_);
196  }
197  return (NO_OFFSET);
198  }
199 
200  void addOffset(size_t hash, size_t offset, size_t len) {
201  table_[hash % BUCKETS].push_back(OffsetItem(hash, offset, len));
202  }
203 
204  // The hash table for the (offset + position in the buffer) entries
205  vector<OffsetItem> table_[BUCKETS];
214 
215  // Placeholder for hash values as they are calculated in writeName().
216  // Note: we may want to make it a local variable of writeName() if it
217  // works more efficiently.
218  boost::array<size_t, Name::MAX_LABELS> seq_hashes_;
219 };
220 
221 MessageRenderer::MessageRenderer() :
223  impl_(new MessageRendererImpl)
224 {}
225 
227  delete impl_;
228 }
229 
230 void
233  impl_->msglength_limit_ = 512;
234  impl_->truncated_ = false;
236 
237  // Clear the hash table. We reserve the minimum space for possible
238  // subsequent use of the renderer.
239  for (size_t i = 0; i < MessageRendererImpl::BUCKETS; ++i) {
240  if (impl_->table_[i].size() > MessageRendererImpl::RESERVED_ITEMS) {
241  // Trim excessive capacity: swap ensures the new capacity is only
242  // reasonably large for the reserved space.
243  vector<OffsetItem> new_table;
244  new_table.reserve(MessageRendererImpl::RESERVED_ITEMS);
245  new_table.swap(impl_->table_[i]);
246  }
247  impl_->table_[i].clear();
248  }
249 }
250 
251 size_t
253  return (impl_->msglength_limit_);
254 }
255 
256 void
258  impl_->msglength_limit_ = len;
259 }
260 
261 bool
263  return (impl_->truncated_);
264 }
265 
266 void
268  impl_->truncated_ = true;
269 }
270 
273  return (impl_->compress_mode_);
274 }
275 
276 void
278  if (getLength() != 0) {
280  "compress mode cannot be changed during rendering");
281  }
282  impl_->compress_mode_ = mode;
283 }
284 
285 void
286 MessageRenderer::writeName(const LabelSequence& ls, const bool compress) {
287  LabelSequence sequence(ls);
288  const size_t nlabels = sequence.getLabelCount();
289  size_t data_len;
290  const uint8_t* data;
291 
292  // Find the offset in the offset table whose name gives the longest
293  // match against the name to be rendered.
294  size_t nlabels_uncomp;
295  uint16_t ptr_offset = MessageRendererImpl::NO_OFFSET;
296  const bool case_sensitive = (impl_->compress_mode_ ==
298  for (nlabels_uncomp = 0; nlabels_uncomp < nlabels; ++nlabels_uncomp) {
299  if (nlabels_uncomp > 0) {
300  sequence.stripLeft(1);
301  }
302 
303  data = sequence.getData(&data_len);
304  if (data_len == 1) { // trailing dot.
305  ++nlabels_uncomp;
306  break;
307  }
308  // write with range check for safety
309  impl_->seq_hashes_.at(nlabels_uncomp) =
310  sequence.getHash(impl_->compress_mode_);
311  InputBuffer name_buf(data, data_len);
312  ptr_offset = impl_->findOffset(getBuffer(), name_buf,
313  impl_->seq_hashes_[nlabels_uncomp],
314  case_sensitive);
315  if (ptr_offset != MessageRendererImpl::NO_OFFSET) {
316  break;
317  }
318  }
319 
320  // Record the current offset before updating the offset table
321  size_t offset = getLength();
322  // Write uncompress part:
323  if (nlabels_uncomp > 0 || !compress) {
324  LabelSequence uncomp_sequence(ls);
325  if (compress && nlabels > nlabels_uncomp) {
326  // If there's compressed part, strip off that part.
327  uncomp_sequence.stripRight(nlabels - nlabels_uncomp);
328  }
329  data = uncomp_sequence.getData(&data_len);
330  writeData(data, data_len);
331  }
332  // And write compression pointer if available:
333  if (compress && ptr_offset != MessageRendererImpl::NO_OFFSET) {
334  ptr_offset |= Name::COMPRESS_POINTER_MARK16;
335  writeUint16(ptr_offset);
336  }
337 
338  // Finally, record the offset and length for each uncompressed sequence
339  // in the hash table. The renderer's buffer has just stored the
340  // corresponding data, so we use the rendered data to get the length
341  // of each label of the names.
342  size_t seqlen = ls.getDataLength();
343  for (size_t i = 0; i < nlabels_uncomp; ++i) {
344  const uint8_t label_len = getBuffer()[offset];
345  if (label_len == 0) { // offset for root doesn't need to be stored.
346  break;
347  }
348  if (offset > Name::MAX_COMPRESS_POINTER) {
349  break;
350  }
351  // Store the tuple of <hash, offset, len> to the table. Note that we
352  // already know the hash value for each name.
353  impl_->addOffset(impl_->seq_hashes_[i], offset, seqlen);
354  offset += (label_len + 1);
355  seqlen -= (label_len + 1);
356  }
357 }
358 
359 void
360 MessageRenderer::writeName(const Name& name, const bool compress) {
361  const LabelSequence ls(name);
362  writeName(ls, compress);
363 }
364 
366  local_buffer_(0), buffer_(&local_buffer_)
367 {
368 }
369 
370 void
372  if (buffer != NULL && buffer_->getLength() != 0) {
374  "MessageRenderer buffer cannot be set when in use");
375  }
376  if (buffer == NULL && buffer_ == &local_buffer_) {
378  "Default MessageRenderer buffer cannot be reset");
379  }
380 
381  if (buffer == NULL) {
382  // Reset to the default buffer, then clear other internal resources.
383  // The order is important; we need to keep the used buffer intact.
384  buffer_ = &local_buffer_;
385  clear();
386  } else {
387  buffer_ = buffer;
388  }
389 }
390 
391 void
393  buffer_->clear();
394 }
395 
396 }
397 }
void setBuffer(isc::util::OutputBuffer *buffer)
Set or reset a temporary output buffer.
The Name class encapsulates DNS names.
Definition: name.h:223
boost::array< size_t, Name::MAX_LABELS > seq_hashes_
uint16_t findOffset(const OutputBuffer &buffer, InputBuffer &name_buf, size_t hash, bool case_sensitive) const
virtual void setLengthLimit(size_t len)
Set the maximum length of rendered data that can fit in the corresponding DNS message without truncat...
virtual CompressMode getCompressMode() const
Return the compression mode of the renderer class object.
bool truncated_
A boolean flag that indicates truncation has occurred while rendering the data.
void setPosition(size_t position)
Set the read position of the buffer to the given value.
Definition: buffer.h:115
A generic exception that is thrown if a parameter given to a method or function is considered invalid...
virtual void setTruncated()
Mark the renderer to indicate truncation has occurred while rendering.
size_t getLabelCount() const
Returns the current number of labels for this LabelSequence.
AbstractMessageRenderer()
The default constructor.
virtual void clear()
Clear the internal buffer and other internal resources.
size_t getHash(bool case_sensitive) const
Calculate a simple hash for the label sequence.
The MessageRendererImpl class is the actual implementation of MessageRenderer.
STL namespace.
size_t getDataLength() const
Return the length of the wire-format data of this LabelSequence.
size_t getLength() const
Return the length of the data stored in the buffer.
Definition: buffer.h:100
virtual void clear()
Clear the internal buffer and other internal resources.
void writeUint16(uint16_t data)
Write an unsigned 16-bit integer in host byte order into the internal buffer in network byte order...
#define isc_throw(type, stream)
A shortcut macro to insert known values into exception arguments.
Definition: edns.h:19
virtual size_t getLengthLimit() const
Return the maximum length of rendered data that can fit in the corresponding DNS message without trun...
The AbstractMessageRenderer class is an abstract base class that provides common interfaces for rende...
virtual void writeName(const Name &name, bool compress=true)
Write a Name object into the internal buffer in wire format, with or without name compression...
const uint8_t * getData(size_t *len) const
Return the wire-format data for this LabelSequence.
CompressMode
Compression mode constants.
virtual bool isTruncated() const
Return whether truncation has occurred while rendering.
void stripRight(size_t i)
Remove labels from the end of this LabelSequence.
uint16_t msglength_limit_
The maximum length of rendered data that can fit without truncation.
void writeData(const void *data, size_t len)
Copy an arbitrary length of data into the internal buffer of the renderer object. ...
Compress names case-sensitive manner.
void clear()
Clear buffer content.
Definition: buffer.h:451
static const uint16_t MAX_COMPRESS_POINTER
Max possible pointer value for name compression.
Definition: name.h:715
The OutputBuffer class is a buffer abstraction for manipulating mutable data.
Definition: buffer.h:294
size_t getLength() const
Return the length of data written in the buffer.
Definition: buffer.h:403
uint16_t len_
The length of the corresponding sequence (which is a domain name).
Defines the logger used by the top-level component of kea-lfc.
static const uint16_t COMPRESS_POINTER_MARK16
A 16-bit masked value indicating a start of compression pointer.
Definition: name.h:719
const isc::util::OutputBuffer & getBuffer() const
Return the output buffer we render into.
The MessageRenderer is a concrete derived class of AbstractMessageRenderer as a general purpose imple...
void addOffset(size_t hash, size_t offset, size_t len)
CompressMode compress_mode_
The name compression mode.
Compress names case-insensitive manner (default)
size_t getLength() const
Return the length of data written in the internal buffer.
virtual void setCompressMode(CompressMode mode)
This implementation does not allow this call in the middle of rendering (i.e.
The InputBuffer class is a buffer abstraction for manipulating read-only data.
Definition: buffer.h:81
size_t hash_
The hash value for the stored name calculated by LabelSequence.getHash.
uint8_t readUint8()
Read an unsigned 8-bit integer from the buffer and return it.
Definition: buffer.h:130
uint16_t pos_
The position (offset from the beginning) in the buffer where the name starts.
void stripLeft(size_t i)
Remove labels from the front of this LabelSequence.
bool truncated_
Definition: dns/message.cc:224
Light-weight Accessor to Name data.
Definition: labelsequence.h:35
const uint8_t maptolower[]
Definition: name.cc:73