1 files changed, 397 insertions, 0 deletions

diff --git a/src/lib/dns/messagerenderer.cc b/src/lib/dns/messagerenderer.cc
new file mode 100644
index 0000000..81b2c92
--- /dev/null
+++ b/src/lib/dns/messagerenderer.cc
@@ -0,0 +1,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();
+}
+
+}
+}