summaryrefslogtreecommitdiffstats
path: root/src/lib/dns/messagerenderer.cc
blob: 81b2c92dd234ccc280323f8fbed175b280bfc581 (plain)
1
2
3
4
5
6
7
8
9
10
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
// Copyright (C) 2009-2015 Internet Systems Consortium, Inc. ("ISC")
//
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.

#include <config.h>

#include <exceptions/exceptions.h>
#include <util/buffer.h>
#include <dns/name.h>
#include <dns/name_internal.h>
#include <dns/labelsequence.h>
#include <dns/messagerenderer.h>

#include <boost/array.hpp>
#include <boost/static_assert.hpp>

#include <limits>
#include <cassert>
#include <vector>

using namespace std;
using namespace isc::util;
using isc::dns::name::internal::maptolower;

namespace isc {
namespace dns {

namespace {     // hide internal-only names from the public namespaces
///
/// \brief The \c OffsetItem class represents a pointer to a name
/// rendered in the internal buffer for the \c MessageRendererImpl object.
///
/// A \c MessageRendererImpl object maintains a set of \c OffsetItem
/// objects in a hash table, and searches the table for the position of the
/// longest match (ancestor) name against each new name to be rendered into
/// the buffer.
struct OffsetItem {
    OffsetItem(size_t hash, size_t pos, size_t len) :
        hash_(hash), pos_(pos), len_(len)
    {}

    /// The hash value for the stored name calculated by LabelSequence.getHash.
    /// This will help make name comparison in \c NameCompare more efficient.
    size_t hash_;

    /// The position (offset from the beginning) in the buffer where the
    /// name starts.
    uint16_t pos_;

    /// The length of the corresponding sequence (which is a domain name).
    uint16_t len_;
};

/// \brief The \c NameCompare class is a functor that checks equality
/// between the name corresponding to an \c OffsetItem object and the name
/// consists of labels represented by a \c LabelSequence object.
///
/// Template parameter CASE_SENSITIVE determines whether to ignore the case
/// of the names.  This policy doesn't change throughout the lifetime of
/// this object, so we separate these using template to avoid unnecessary
/// condition check.
template <bool CASE_SENSITIVE>
struct NameCompare {
    /// \brief Constructor
    ///
    /// \param buffer The buffer for rendering used in the caller renderer
    /// \param name_buf An input buffer storing the wire-format data of the
    /// name to be newly rendered (and only that data).
    /// \param hash The hash value for the name.
    NameCompare(const OutputBuffer& buffer, InputBuffer& name_buf,
                size_t hash) :
        buffer_(&buffer), name_buf_(&name_buf), hash_(hash)
    {}

    bool operator()(const OffsetItem& item) const {
        // Trivial inequality check.  If either the hash or the total length
        // doesn't match, the names are obviously different.
        if (item.hash_  != hash_ || item.len_ != name_buf_->getLength()) {
            return (false);
        }

        // Compare the name data, character-by-character.
        // item_pos keeps track of the position in the buffer corresponding to
        // the character to compare.  item_label_len is the number of
        // characters in the labels where the character pointed by item_pos
        // belongs.  When it reaches zero, nextPosition() identifies the
        // position for the subsequent label, taking into account name
        // compression, and resets item_label_len to the length of the new
        // label.
        name_buf_->setPosition(0); // buffer can be reused, so reset position
        uint16_t item_pos = item.pos_;
        uint16_t item_label_len = 0;
        for (size_t i = 0; i < item.len_; ++i, ++item_pos) {
            item_pos = nextPosition(*buffer_, item_pos, item_label_len);
            const uint8_t ch1 = (*buffer_)[item_pos];
            const uint8_t ch2 = name_buf_->readUint8();
            if (CASE_SENSITIVE) {
                if (ch1 != ch2) {
                    return (false);
                }
            } else {
                if (maptolower[ch1] != maptolower[ch2]) {
                    return (false);
                }
            }
        }

        return (true);
    }

private:
    static uint16_t nextPosition(const OutputBuffer& buffer,
                                 uint16_t pos, uint16_t& llen)
    {
        if (llen == 0) {
            size_t i = 0;

            while ((buffer[pos] & Name::COMPRESS_POINTER_MARK8) ==
                   Name::COMPRESS_POINTER_MARK8) {
                pos = (buffer[pos] & ~Name::COMPRESS_POINTER_MARK8) *
                    256 + buffer[pos + 1];

                // This loop should stop as long as the buffer has been
                // constructed validly and the search/insert argument is based
                // on a valid name, which is an assumption for this class.
                // But we'll abort if a bug could cause an infinite loop.
                i += 2;
                assert(i < Name::MAX_WIRE);
            }
            llen = buffer[pos];
        } else {
            --llen;
        }
        return (pos);
    }

    const OutputBuffer* buffer_;
    InputBuffer* name_buf_;
    const size_t hash_;
};
}

///
/// \brief The \c MessageRendererImpl class is the actual implementation of
/// \c MessageRenderer.
///
/// The implementation is hidden from applications.  We can refer to specific
/// members of this class only within the implementation source file.
///
/// It internally holds a hash table for OffsetItem objects corresponding
/// to portions of names rendered in this renderer.  The offset information
/// is used to compress subsequent names to be rendered.
struct MessageRenderer::MessageRendererImpl {
    // The size of hash buckets and number of hash entries per bucket for
    // which space is preallocated and kept reserved for subsequent rendering
    // to provide better performance.  These values are derived from the
    // BIND 9 implementation that uses a similar hash table.
    static const size_t BUCKETS = 64;
    static const size_t RESERVED_ITEMS = 16;
    static const uint16_t NO_OFFSET = 65535; // used as a marker of 'not found'

    /// \brief Constructor
    MessageRendererImpl() :
        msglength_limit_(512), truncated_(false),
        compress_mode_(MessageRenderer::CASE_INSENSITIVE)
    {
        // Reserve some spaces for hash table items.
        for (size_t i = 0; i < BUCKETS; ++i) {
            table_[i].reserve(RESERVED_ITEMS);
        }
    }

    uint16_t findOffset(const OutputBuffer& buffer, InputBuffer& name_buf,
                        size_t hash, bool case_sensitive) const
    {
        // Find a matching entry, if any.  We use some heuristics here: often
        // the same name appears consecutively (like repeating the same owner
        // name for a single RRset), so in case there's a collision in the
        // bucket it will be more likely to find it in the tail side of the
        // bucket.
        const size_t bucket_id = hash % BUCKETS;
        vector<OffsetItem>::const_reverse_iterator found;
        if (case_sensitive) {
            found = find_if(table_[bucket_id].rbegin(),
                            table_[bucket_id].rend(),
                            NameCompare<true>(buffer, name_buf, hash));
        } else {
            found = find_if(table_[bucket_id].rbegin(),
                            table_[bucket_id].rend(),
                            NameCompare<false>(buffer, name_buf, hash));
        }
        if (found != table_[bucket_id].rend()) {
            return (found->pos_);
        }
        return (NO_OFFSET);
    }

    void addOffset(size_t hash, size_t offset, size_t len) {
        table_[hash % BUCKETS].push_back(OffsetItem(hash, offset, len));
    }

    // The hash table for the (offset + position in the buffer) entries
    vector<OffsetItem> table_[BUCKETS];
    /// The maximum length of rendered data that can fit without
    /// truncation.
    uint16_t msglength_limit_;
    /// A boolean flag that indicates truncation has occurred while rendering
    /// the data.
    bool truncated_;
    /// The name compression mode.
    CompressMode compress_mode_;

    // Placeholder for hash values as they are calculated in writeName().
    // Note: we may want to make it a local variable of writeName() if it
    // works more efficiently.
    boost::array<size_t, Name::MAX_LABELS> seq_hashes_;
};

MessageRenderer::MessageRenderer() :
    AbstractMessageRenderer(),
    impl_(new MessageRendererImpl)
{}

MessageRenderer::~MessageRenderer() {
    delete impl_;
}

void
MessageRenderer::clear() {
    AbstractMessageRenderer::clear();
    impl_->msglength_limit_ = 512;
    impl_->truncated_ = false;
    impl_->compress_mode_ = CASE_INSENSITIVE;

    // Clear the hash table.  We reserve the minimum space for possible
    // subsequent use of the renderer.
    for (size_t i = 0; i < MessageRendererImpl::BUCKETS; ++i) {
        if (impl_->table_[i].size() > MessageRendererImpl::RESERVED_ITEMS) {
            // Trim excessive capacity: swap ensures the new capacity is only
            // reasonably large for the reserved space.
            vector<OffsetItem> new_table;
            new_table.reserve(MessageRendererImpl::RESERVED_ITEMS);
            new_table.swap(impl_->table_[i]);
        }
        impl_->table_[i].clear();
    }
}

size_t
MessageRenderer::getLengthLimit() const {
    return (impl_->msglength_limit_);
}

void
MessageRenderer::setLengthLimit(const size_t len) {
    impl_->msglength_limit_ = len;
}

bool
MessageRenderer::isTruncated() const {
    return (impl_->truncated_);
}

void
MessageRenderer::setTruncated() {
    impl_->truncated_ = true;
}

MessageRenderer::CompressMode
MessageRenderer::getCompressMode() const {
    return (impl_->compress_mode_);
}

void
MessageRenderer::setCompressMode(const CompressMode mode) {
    if (getLength() != 0) {
        isc_throw(isc::InvalidParameter,
                  "compress mode cannot be changed during rendering");
    }
    impl_->compress_mode_ = mode;
}

void
MessageRenderer::writeName(const LabelSequence& ls, const bool compress) {
    LabelSequence sequence(ls);
    const size_t nlabels = sequence.getLabelCount();
    size_t data_len;
    const uint8_t* data;

    // Find the offset in the offset table whose name gives the longest
    // match against the name to be rendered.
    size_t nlabels_uncomp;
    uint16_t ptr_offset = MessageRendererImpl::NO_OFFSET;
    const bool case_sensitive = (impl_->compress_mode_ ==
                                 MessageRenderer::CASE_SENSITIVE);
    for (nlabels_uncomp = 0; nlabels_uncomp < nlabels; ++nlabels_uncomp) {
        if (nlabels_uncomp > 0) {
            sequence.stripLeft(1);
        }

        data = sequence.getData(&data_len);
        if (data_len == 1) { // trailing dot.
            ++nlabels_uncomp;
            break;
        }
        // write with range check for safety
        impl_->seq_hashes_.at(nlabels_uncomp) =
            sequence.getHash(impl_->compress_mode_);
        InputBuffer name_buf(data, data_len);
        ptr_offset = impl_->findOffset(getBuffer(), name_buf,
                                       impl_->seq_hashes_[nlabels_uncomp],
                                       case_sensitive);
        if (ptr_offset != MessageRendererImpl::NO_OFFSET) {
            break;
        }
    }

    // Record the current offset before updating the offset table
    size_t offset = getLength();
    // Write uncompress part:
    if (nlabels_uncomp > 0 || !compress) {
        LabelSequence uncomp_sequence(ls);
        if (compress && nlabels > nlabels_uncomp) {
            // If there's compressed part, strip off that part.
            uncomp_sequence.stripRight(nlabels - nlabels_uncomp);
        }
        data = uncomp_sequence.getData(&data_len);
        writeData(data, data_len);
    }
    // And write compression pointer if available:
    if (compress && ptr_offset != MessageRendererImpl::NO_OFFSET) {
        ptr_offset |= Name::COMPRESS_POINTER_MARK16;
        writeUint16(ptr_offset);
    }

    // Finally, record the offset and length for each uncompressed sequence
    // in the hash table.  The renderer's buffer has just stored the
    // corresponding data, so we use the rendered data to get the length
    // of each label of the names.
    size_t seqlen = ls.getDataLength();
    for (size_t i = 0; i < nlabels_uncomp; ++i) {
        const uint8_t label_len = getBuffer()[offset];
        if (label_len == 0) { // offset for root doesn't need to be stored.
            break;
        }
        if (offset > Name::MAX_COMPRESS_POINTER) {
            break;
        }
        // Store the tuple of <hash, offset, len> to the table.  Note that we
        // already know the hash value for each name.
        impl_->addOffset(impl_->seq_hashes_[i], offset, seqlen);
        offset += (label_len + 1);
        seqlen -= (label_len + 1);
    }
}

void
MessageRenderer::writeName(const Name& name, const bool compress) {
    const LabelSequence ls(name);
    writeName(ls, compress);
}

AbstractMessageRenderer::AbstractMessageRenderer() :
    local_buffer_(0), buffer_(&local_buffer_)
{
}

void
AbstractMessageRenderer::setBuffer(OutputBuffer* buffer) {
    if (buffer != NULL && buffer_->getLength() != 0) {
        isc_throw(isc::InvalidParameter,
                  "MessageRenderer buffer cannot be set when in use");
    }
    if (buffer == NULL && buffer_ == &local_buffer_) {
        isc_throw(isc::InvalidParameter,
                  "Default MessageRenderer buffer cannot be reset");
    }

    if (buffer == NULL) {
        // Reset to the default buffer, then clear other internal resources.
        // The order is important; we need to keep the used buffer intact.
        buffer_ = &local_buffer_;
        clear();
    } else {
        buffer_ = buffer;
    }
}

void
AbstractMessageRenderer::clear() {
    buffer_->clear();
}

}
}