Kea  2.1.7-git
labelsequence.cc
Go to the documentation of this file.
1 // Copyright (C) 2012-2019 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 
9 #include <dns/labelsequence.h>
10 #include <dns/name_internal.h>
11 #include <exceptions/exceptions.h>
12 #include <exceptions/isc_assert.h>
13 
14 #include <boost/functional/hash.hpp>
15 
16 #include <cstring>
17 
18 namespace isc {
19 namespace dns {
20 
21 LabelSequence::LabelSequence(const void* buf) {
22 #ifdef ENABLE_DEBUG
23  // In non-debug mode, dereferencing the NULL pointer further below
24  // will lead to a crash, so disabling this check is not
25  // unsafe. Except for a programming mistake, this case should not
26  // happen.
27  if (buf == NULL) {
29  "Null pointer passed to LabelSequence constructor");
30  }
31 #endif
32 
33  const uint8_t* bp = reinterpret_cast<const uint8_t*>(buf);
34  first_label_ = 0;
35  const uint8_t offsets_len = *bp++;
36 
37 #ifdef ENABLE_DEBUG
38  if (offsets_len == 0 || offsets_len > Name::MAX_LABELS) {
40  "Bad offsets len in serialized LabelSequence data: "
41  << static_cast<unsigned int>(offsets_len));
42  }
43 #endif
44 
45  last_label_ = offsets_len - 1;
46  offsets_ = bp;
47  data_ = bp + offsets_len;
48 
49 #ifdef ENABLE_DEBUG
50  // Check the integrity on the offsets and the name data
51  const uint8_t* dp = data_;
52  for (size_t cur_offset = 0; cur_offset < offsets_len; ++cur_offset) {
53  if (dp - data_ != offsets_[cur_offset] || *dp > Name::MAX_LABELLEN) {
55  "Broken offset or name data in serialized "
56  "LabelSequence data");
57  }
58  dp += (1 + *dp);
59  }
60 #endif
61 }
62 
64  uint8_t buf[MAX_SERIALIZED_LENGTH])
65 {
66  size_t data_len;
67  const uint8_t *data = src.getData(&data_len);
68  std::memcpy(buf, data, data_len);
69 
70  for (size_t i = 0; i < src.getLabelCount(); ++i) {
71  buf[Name::MAX_WIRE + i] = src.offsets_[i + src.first_label_] -
72  src.offsets_[src.first_label_];
73  }
74 
75  first_label_ = 0;
76  last_label_ = src.last_label_ - src.first_label_;
77  data_ = buf;
78  offsets_ = &buf[Name::MAX_WIRE];
79 }
80 
81 
82 const uint8_t*
83 LabelSequence::getData(size_t *len) const {
84  *len = getDataLength();
85  return (&data_[offsets_[first_label_]]);
86 }
87 
88 size_t
90  const size_t last_label_len = data_[offsets_[last_label_]] + 1;
91  return (offsets_[last_label_] - offsets_[first_label_] + last_label_len);
92 }
93 
94 size_t
96  return (1 + getLabelCount() + getDataLength());
97 }
98 
99 namespace {
100 // Check if buf is not in the range of [bp, ep), which means
101 // - end of buffer is before bp, or
102 // - beginning of buffer is on or after ep
103 bool
104 isOutOfRange(const uint8_t* bp, const uint8_t* ep,
105  const uint8_t* buf, size_t buf_len)
106 {
107  return (bp >= buf + buf_len || // end of buffer is before bp
108  ep <= buf); // beginning of buffer is on or after ep
109 }
110 }
111 
112 void
113 LabelSequence::serialize(void* buf, size_t buf_len) const {
114  const size_t expected_size = getSerializedLength();
115  if (expected_size > buf_len) {
116  isc_throw(BadValue, "buffer too short for LabelSequence::serialize");
117  }
118 
119  const size_t offsets_len = getLabelCount();
120  isc_throw_assert(offsets_len < 256); // should be in the 8-bit range
121 
122  // Overridden check. Buffer shouldn't overwrap the offset of name data
123  // regions.
124  uint8_t* bp = reinterpret_cast<uint8_t*>(buf);
125  const size_t ndata_len = getDataLength();
126  if (!isOutOfRange(offsets_, offsets_ + offsets_len, bp, buf_len) ||
127  !isOutOfRange(data_, data_ + ndata_len, bp, buf_len)) {
128  isc_throw(BadValue, "serialize would break the source sequence");
129  }
130 
131  *bp++ = offsets_len;
132  for (size_t i = 0; i < offsets_len; ++i) {
133  *bp++ = offsets_[first_label_ + i] - offsets_[first_label_];
134  }
135  std::memcpy(bp, &data_[offsets_[first_label_]], ndata_len);
136  bp += ndata_len;
137 
138  isc_throw_assert(bp - reinterpret_cast<const uint8_t*>(buf) == expected_size);
139 }
140 
141 bool
142 LabelSequence::equals(const LabelSequence& other, bool case_sensitive) const {
143  size_t len, other_len;
144  const uint8_t* data = getData(&len);
145  const uint8_t* other_data = other.getData(&other_len);
146 
147  if (len != other_len) {
148  return (false);
149  }
150  if (case_sensitive) {
151  return (std::memcmp(data, other_data, len) == 0);
152  }
153 
154  // As long as the data was originally validated as (part of) a name,
155  // label length must never be a capital ascii character, so we can
156  // simply compare them after converting to lower characters.
157  for (size_t i = 0; i < len; ++i) {
158  const uint8_t ch = data[i];
159  const uint8_t other_ch = other_data[i];
162  return (false);
163  }
164  }
165  return (true);
166 }
167 
170  bool case_sensitive) const
171 {
172  // Determine the relative ordering under the DNSSEC order relation of
173  // 'this' and 'other', and also determine the hierarchical relationship
174  // of the labels.
175 
176  unsigned int nlabels = 0;
177  int l1 = getLabelCount();
178  int l2 = other.getLabelCount();
179  const int ldiff = static_cast<int>(l1) - static_cast<int>(l2);
180  unsigned int l = (ldiff < 0) ? l1 : l2;
181 
182  while (l > 0) {
183  --l;
184  --l1;
185  --l2;
186  size_t pos1 = offsets_[l1 + first_label_];
187  size_t pos2 = other.offsets_[l2 + other.first_label_];
188  unsigned int count1 = data_[pos1++];
189  unsigned int count2 = other.data_[pos2++];
190 
191  // We don't support any extended label types including now-obsolete
192  // bitstring labels.
194 
195  const int cdiff = static_cast<int>(count1) - static_cast<int>(count2);
196  unsigned int count = (cdiff < 0) ? count1 : count2;
197 
198  while (count > 0) {
199  const uint8_t label1 = data_[pos1];
200  const uint8_t label2 = other.data_[pos2];
201  int chdiff;
202 
203  if (case_sensitive) {
204  chdiff = static_cast<int>(label1) - static_cast<int>(label2);
205  } else {
206  chdiff = static_cast<int>(
208  static_cast<int>(
210  }
211 
212  if (chdiff != 0) {
213  return (NameComparisonResult(
214  chdiff, nlabels,
215  nlabels == 0 ? NameComparisonResult::NONE :
217  }
218  --count;
219  ++pos1;
220  ++pos2;
221  }
222  if (cdiff != 0) {
223  return (NameComparisonResult(
224  cdiff, nlabels,
225  nlabels == 0 ? NameComparisonResult::NONE :
227  }
228  ++nlabels;
229  }
230 
231  if (ldiff < 0) {
232  return (NameComparisonResult(ldiff, nlabels,
234  } else if (ldiff > 0) {
235  return (NameComparisonResult(ldiff, nlabels,
237  }
238 
239  return (NameComparisonResult(ldiff, nlabels, NameComparisonResult::EQUAL));
240 }
241 
242 void
244  if (i >= getLabelCount()) {
245  isc_throw(OutOfRange, "Cannot strip to zero or less labels; " << i <<
246  " (labelcount: " << getLabelCount() << ")");
247  }
248  first_label_ += i;
249 }
250 
251 void
253  if (i >= getLabelCount()) {
254  isc_throw(OutOfRange, "Cannot strip to zero or less labels; " << i <<
255  " (labelcount: " << getLabelCount() << ")");
256  }
257  last_label_ -= i;
258 }
259 
260 bool
262  return (data_[offsets_[last_label_]] == 0);
263 }
264 
265 size_t
266 LabelSequence::getHash(bool case_sensitive) const {
267  size_t length;
268  const uint8_t* s = getData(&length);
269  if (length > 16) {
270  length = 16;
271  }
272 
273  size_t hash_val = 0;
274  while (length > 0) {
275  const uint8_t c = *s++;
276  boost::hash_combine(hash_val, case_sensitive ? c :
278  --length;
279  }
280  return (hash_val);
281 }
282 
283 std::string
284 LabelSequence::toRawText(bool omit_final_dot) const {
285  const uint8_t* np = &data_[offsets_[first_label_]];
286  const uint8_t* np_end = np + getDataLength();
287 
288  // use for integrity check
289  unsigned int labels = getLabelCount();
290  // init with an impossible value to catch error cases in the end:
291  unsigned int count = Name::MAX_LABELLEN + 1;
292 
293  // result string: it will roughly have the same length as the wire format
294  // label sequence data. reserve that length to minimize reallocation.
295  std::string result;
296  result.reserve(getDataLength());
297 
298  while (np != np_end) {
299  labels--;
300  count = *np++;
301 
302  if (count == 0) {
303  // We've reached the "final dot". If we've not dumped any
304  // character, the entire label sequence is the root name.
305  // In that case we don't omit the final dot.
306  if (!omit_final_dot || result.empty()) {
307  result.push_back('.');
308  }
309  break;
310  }
311 
312  if (count <= Name::MAX_LABELLEN) {
313  isc_throw_assert(np_end - np >= count);
314 
315  if (!result.empty()) {
316  // just after a non-empty label. add a separating dot.
317  result.push_back('.');
318  }
319 
320  while (count-- > 0) {
321  const uint8_t c = *np++;
322  result.push_back(c);
323  }
324  } else {
325  isc_throw(BadLabelType, "unknown label type in name data");
326  }
327  }
328 
329  // We should be at the end of the data and have consumed all labels.
330  isc_throw_assert(np == np_end);
331  isc_throw_assert(labels == 0);
332 
333  return (result);
334 }
335 
336 
337 std::string
338 LabelSequence::toText(bool omit_final_dot) const {
339  const uint8_t* np = &data_[offsets_[first_label_]];
340  const uint8_t* np_end = np + getDataLength();
341 
342  // use for integrity check
343  unsigned int labels = getLabelCount();
344  // init with an impossible value to catch error cases in the end:
345  unsigned int count = Name::MAX_LABELLEN + 1;
346 
347  // result string: it will roughly have the same length as the wire format
348  // label sequence data. reserve that length to minimize reallocation.
349  std::string result;
350  result.reserve(getDataLength());
351 
352  while (np != np_end) {
353  labels--;
354  count = *np++;
355 
356  if (count == 0) {
357  // We've reached the "final dot". If we've not dumped any
358  // character, the entire label sequence is the root name.
359  // In that case we don't omit the final dot.
360  if (!omit_final_dot || result.empty()) {
361  result.push_back('.');
362  }
363  break;
364  }
365 
366  if (count <= Name::MAX_LABELLEN) {
367  isc_throw_assert(np_end - np >= count);
368 
369  if (!result.empty()) {
370  // just after a non-empty label. add a separating dot.
371  result.push_back('.');
372  }
373 
374  while (count-- > 0) {
375  const uint8_t c = *np++;
376  switch (c) {
377  case 0x22: // '"'
378  case 0x28: // '('
379  case 0x29: // ')'
380  case 0x2E: // '.'
381  case 0x3B: // ';'
382  case 0x5C: // '\\'
383  // Special modifiers in zone files.
384  case 0x40: // '@'
385  case 0x24: // '$'
386  result.push_back('\\');
387  result.push_back(c);
388  break;
389  default:
390  if (c > 0x20 && c < 0x7f) {
391  // append printable characters intact
392  result.push_back(c);
393  } else {
394  // encode non-printable characters in the form of \DDD
395  result.push_back(0x5c);
396  result.push_back(0x30 + ((c / 100) % 10));
397  result.push_back(0x30 + ((c / 10) % 10));
398  result.push_back(0x30 + (c % 10));
399  }
400  }
401  }
402  } else {
403  isc_throw(BadLabelType, "unknown label type in name data");
404  }
405  }
406 
407  // We should be at the end of the data and have consumed all labels.
408  isc_throw_assert(np == np_end);
409  isc_throw_assert(labels == 0);
410 
411  return (result);
412 }
413 
414 std::string
416  return (toText(!isAbsolute()));
417 }
418 
419 void
421  uint8_t buf[MAX_SERIALIZED_LENGTH])
422 {
423  // collect data to perform steps before anything is changed
424  size_t label_count = last_label_ + 1;
425  // Since we may have been stripped, do not use getDataLength(), but
426  // calculate actual data size this labelsequence currently uses
427  size_t data_pos = offsets_[last_label_] + data_[offsets_[last_label_]] + 1;
428 
429  // If this labelsequence is absolute, virtually strip the root label.
430  if (isAbsolute()) {
431  data_pos--;
432  label_count--;
433  }
434  const size_t append_label_count = labels.getLabelCount();
435  size_t data_len;
436  const uint8_t *data = labels.getData(&data_len);
437 
438  // Sanity checks
439  if (data_ != buf || offsets_ != &buf[Name::MAX_WIRE]) {
441  "extend() called with unrelated buffer");
442  }
443  // Check MAX_LABELS before MAX_WIRE or it will be never reached
444  if (label_count + append_label_count > Name::MAX_LABELS) {
446  "extend() would exceed maximum number of labels");
447  }
448  if (data_pos + data_len > Name::MAX_WIRE) {
450  "extend() would exceed maximum wire length");
451  }
452 
453  // All seems to be reasonably ok, let's proceed.
454  std::memmove(&buf[data_pos], data, data_len);
455 
456  for (size_t i = 0; i < append_label_count; ++i) {
457  buf[Name::MAX_WIRE + label_count + i] =
458  data_pos +
459  labels.offsets_[i + labels.first_label_] -
460  labels.offsets_[labels.first_label_];
461  }
462  last_label_ = label_count + append_label_count - 1;
463 }
464 
465 std::ostream&
466 operator<<(std::ostream& os, const LabelSequence& label_sequence) {
467  os << label_sequence.toText();
468  return (os);
469 }
470 
471 } // end namespace dns
472 } // end namespace isc
#define isc_throw_assert(expr)
Replacement for assert() that throws if the expression is false.
Definition: isc_assert.h:18
LabelSequence(const Name &name)
Constructs a LabelSequence for the given name.
Definition: labelsequence.h:64
ostream & operator<<(std::ostream &os, const EDNS &edns)
Insert the EDNS as a string into stream.
Definition: edns.cc:172
static const size_t MAX_SERIALIZED_LENGTH
Max possible size of serialized image generated by serialize.
Definition: labelsequence.h:45
size_t getLabelCount() const
Returns the current number of labels for this LabelSequence.
void serialize(void *buf, size_t buf_len) const
Serialize the LabelSequence object in to a buffer.
size_t getHash(bool case_sensitive) const
Calculate a simple hash for the label sequence.
size_t getDataLength() const
Return the length of the wire-format data of this LabelSequence.
This is a supplemental class used only as a return value of Name::compare() and LabelSequence::compar...
Definition: name.h:117
void extend(const LabelSequence &labels, uint8_t buf[MAX_SERIALIZED_LENGTH])
Extend this LabelSequence with the given labelsequence.
static const size_t MAX_WIRE
Max allowable length of domain names.
Definition: name.h:699
#define isc_throw(type, stream)
A shortcut macro to insert known values into exception arguments.
A generic exception that is thrown if a parameter given to a method is considered invalid in that con...
const uint8_t * getData(size_t *len) const
Return the wire-format data for this LabelSequence.
void stripRight(size_t i)
Remove labels from the end of this LabelSequence.
std::string toText() const
Convert the LabelSequence to a string.
NameComparisonResult compare(const LabelSequence &other, bool case_sensitive=false) const
Compares two label sequences.
A standard DNS module exception that is thrown if the name parser encounters an obsolete or incomplet...
Definition: name.h:62
Defines the logger used by the top-level component of kea-lfc.
bool equals(const LabelSequence &other, bool case_sensitive=false) const
Compares two label sequences for equality.
size_t getSerializedLength() const
Return the size of serialized image of the LabelSequence.
std::string toRawText(bool omit_final_dot) const
Convert the LabelSequence to a string without escape sequences.
static const size_t MAX_LABELLEN
Max allowable length of labels of a domain name.
Definition: name.h:708
static const size_t MAX_LABELS
Max allowable labels of domain names.
Definition: name.h:705
A generic exception that is thrown if a parameter given to a method would refer to or modify out-of-r...
bool isAbsolute() const
Checks whether the label sequence is absolute.
void stripLeft(size_t i)
Remove labels from the front of this LabelSequence.
Light-weight Accessor to Name data.
Definition: labelsequence.h:35
const uint8_t maptolower[]
Definition: name.cc:73