1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/toolkit/crashreporter/google-breakpad/src/common/test_assembler.cc Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,359 @@
1.4 +// Copyright (c) 2010, Google Inc.
1.5 +// All rights reserved.
1.6 +//
1.7 +// Redistribution and use in source and binary forms, with or without
1.8 +// modification, are permitted provided that the following conditions are
1.9 +// met:
1.10 +//
1.11 +// * Redistributions of source code must retain the above copyright
1.12 +// notice, this list of conditions and the following disclaimer.
1.13 +// * Redistributions in binary form must reproduce the above
1.14 +// copyright notice, this list of conditions and the following disclaimer
1.15 +// in the documentation and/or other materials provided with the
1.16 +// distribution.
1.17 +// * Neither the name of Google Inc. nor the names of its
1.18 +// contributors may be used to endorse or promote products derived from
1.19 +// this software without specific prior written permission.
1.20 +//
1.21 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.22 +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.23 +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.24 +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1.25 +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.26 +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.27 +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.28 +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.29 +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.30 +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.31 +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.32 +
1.33 +// Original author: Jim Blandy <jimb@mozilla.com> <jimb@red-bean.com>
1.34 +
1.35 +// test_assembler.cc: Implementation of google_breakpad::TestAssembler.
1.36 +// See test_assembler.h for details.
1.37 +
1.38 +#include "common/test_assembler.h"
1.39 +
1.40 +#include <assert.h>
1.41 +#include <stdio.h>
1.42 +
1.43 +#include <iterator>
1.44 +
1.45 +namespace google_breakpad {
1.46 +namespace test_assembler {
1.47 +
1.48 +using std::back_insert_iterator;
1.49 +
1.50 +Label::Label() : value_(new Binding()) { }
1.51 +Label::Label(uint64_t value) : value_(new Binding(value)) { }
1.52 +Label::Label(const Label &label) {
1.53 + value_ = label.value_;
1.54 + value_->Acquire();
1.55 +}
1.56 +Label::~Label() {
1.57 + if (value_->Release()) delete value_;
1.58 +}
1.59 +
1.60 +Label &Label::operator=(uint64_t value) {
1.61 + value_->Set(NULL, value);
1.62 + return *this;
1.63 +}
1.64 +
1.65 +Label &Label::operator=(const Label &label) {
1.66 + value_->Set(label.value_, 0);
1.67 + return *this;
1.68 +}
1.69 +
1.70 +Label Label::operator+(uint64_t addend) const {
1.71 + Label l;
1.72 + l.value_->Set(this->value_, addend);
1.73 + return l;
1.74 +}
1.75 +
1.76 +Label Label::operator-(uint64_t subtrahend) const {
1.77 + Label l;
1.78 + l.value_->Set(this->value_, -subtrahend);
1.79 + return l;
1.80 +}
1.81 +
1.82 +// When NDEBUG is #defined, assert doesn't evaluate its argument. This
1.83 +// means you can't simply use assert to check the return value of a
1.84 +// function with necessary side effects.
1.85 +//
1.86 +// ALWAYS_EVALUATE_AND_ASSERT(x) evaluates x regardless of whether
1.87 +// NDEBUG is #defined; when NDEBUG is not #defined, it further asserts
1.88 +// that x is true.
1.89 +#ifdef NDEBUG
1.90 +#define ALWAYS_EVALUATE_AND_ASSERT(x) x
1.91 +#else
1.92 +#define ALWAYS_EVALUATE_AND_ASSERT(x) assert(x)
1.93 +#endif
1.94 +
1.95 +uint64_t Label::operator-(const Label &label) const {
1.96 + uint64_t offset;
1.97 + ALWAYS_EVALUATE_AND_ASSERT(IsKnownOffsetFrom(label, &offset));
1.98 + return offset;
1.99 +}
1.100 +
1.101 +uint64_t Label::Value() const {
1.102 + uint64_t v = 0;
1.103 + ALWAYS_EVALUATE_AND_ASSERT(IsKnownConstant(&v));
1.104 + return v;
1.105 +};
1.106 +
1.107 +bool Label::IsKnownConstant(uint64_t *value_p) const {
1.108 + Binding *base;
1.109 + uint64_t addend;
1.110 + value_->Get(&base, &addend);
1.111 + if (base != NULL) return false;
1.112 + if (value_p) *value_p = addend;
1.113 + return true;
1.114 +}
1.115 +
1.116 +bool Label::IsKnownOffsetFrom(const Label &label, uint64_t *offset_p) const
1.117 +{
1.118 + Binding *label_base, *this_base;
1.119 + uint64_t label_addend, this_addend;
1.120 + label.value_->Get(&label_base, &label_addend);
1.121 + value_->Get(&this_base, &this_addend);
1.122 + // If this and label are related, Get will find their final
1.123 + // common ancestor, regardless of how indirect the relation is. This
1.124 + // comparison also handles the constant vs. constant case.
1.125 + if (this_base != label_base) return false;
1.126 + if (offset_p) *offset_p = this_addend - label_addend;
1.127 + return true;
1.128 +}
1.129 +
1.130 +Label::Binding::Binding() : base_(this), addend_(), reference_count_(1) { }
1.131 +
1.132 +Label::Binding::Binding(uint64_t addend)
1.133 + : base_(NULL), addend_(addend), reference_count_(1) { }
1.134 +
1.135 +Label::Binding::~Binding() {
1.136 + assert(reference_count_ == 0);
1.137 + if (base_ && base_ != this && base_->Release())
1.138 + delete base_;
1.139 +}
1.140 +
1.141 +void Label::Binding::Set(Binding *binding, uint64_t addend) {
1.142 + if (!base_ && !binding) {
1.143 + // We're equating two constants. This could be okay.
1.144 + assert(addend_ == addend);
1.145 + } else if (!base_) {
1.146 + // We are a known constant, but BINDING may not be, so turn the
1.147 + // tables and try to set BINDING's value instead.
1.148 + binding->Set(NULL, addend_ - addend);
1.149 + } else {
1.150 + if (binding) {
1.151 + // Find binding's final value. Since the final value is always either
1.152 + // completely unconstrained or a constant, never a reference to
1.153 + // another variable (otherwise, it wouldn't be final), this
1.154 + // guarantees we won't create cycles here, even for code like this:
1.155 + // l = m, m = n, n = l;
1.156 + uint64_t binding_addend;
1.157 + binding->Get(&binding, &binding_addend);
1.158 + addend += binding_addend;
1.159 + }
1.160 +
1.161 + // It seems likely that setting a binding to itself is a bug
1.162 + // (although I can imagine this might turn out to be helpful to
1.163 + // permit).
1.164 + assert(binding != this);
1.165 +
1.166 + if (base_ != this) {
1.167 + // Set the other bindings on our chain as well. Note that this
1.168 + // is sufficient even though binding relationships form trees:
1.169 + // All binding operations traverse their chains to the end, and
1.170 + // all bindings related to us share some tail of our chain, so
1.171 + // they will see the changes we make here.
1.172 + base_->Set(binding, addend - addend_);
1.173 + // We're not going to use base_ any more.
1.174 + if (base_->Release()) delete base_;
1.175 + }
1.176 +
1.177 + // Adopt BINDING as our base. Note that it should be correct to
1.178 + // acquire here, after the release above, even though the usual
1.179 + // reference-counting rules call for acquiring first, and then
1.180 + // releasing: the self-reference assertion above should have
1.181 + // complained if BINDING were 'this' or anywhere along our chain,
1.182 + // so we didn't release BINDING.
1.183 + if (binding) binding->Acquire();
1.184 + base_ = binding;
1.185 + addend_ = addend;
1.186 + }
1.187 +}
1.188 +
1.189 +void Label::Binding::Get(Binding **base, uint64_t *addend) {
1.190 + if (base_ && base_ != this) {
1.191 + // Recurse to find the end of our reference chain (the root of our
1.192 + // tree), and then rewrite every binding along the chain to refer
1.193 + // to it directly, adjusting addends appropriately. (This is why
1.194 + // this member function isn't this-const.)
1.195 + Binding *final_base;
1.196 + uint64_t final_addend;
1.197 + base_->Get(&final_base, &final_addend);
1.198 + if (final_base) final_base->Acquire();
1.199 + if (base_->Release()) delete base_;
1.200 + base_ = final_base;
1.201 + addend_ += final_addend;
1.202 + }
1.203 + *base = base_;
1.204 + *addend = addend_;
1.205 +}
1.206 +
1.207 +template<typename Inserter>
1.208 +static inline void InsertEndian(test_assembler::Endianness endianness,
1.209 + size_t size, uint64_t number, Inserter dest) {
1.210 + assert(size > 0);
1.211 + if (endianness == kLittleEndian) {
1.212 + for (size_t i = 0; i < size; i++) {
1.213 + *dest++ = (char) (number & 0xff);
1.214 + number >>= 8;
1.215 + }
1.216 + } else {
1.217 + assert(endianness == kBigEndian);
1.218 + // The loop condition is odd, but it's correct for size_t.
1.219 + for (size_t i = size - 1; i < size; i--)
1.220 + *dest++ = (char) ((number >> (i * 8)) & 0xff);
1.221 + }
1.222 +}
1.223 +
1.224 +Section &Section::Append(Endianness endianness, size_t size, uint64_t number) {
1.225 + InsertEndian(endianness, size, number,
1.226 + back_insert_iterator<string>(contents_));
1.227 + return *this;
1.228 +}
1.229 +
1.230 +Section &Section::Append(Endianness endianness, size_t size,
1.231 + const Label &label) {
1.232 + // If this label's value is known, there's no reason to waste an
1.233 + // entry in references_ on it.
1.234 + uint64_t value;
1.235 + if (label.IsKnownConstant(&value))
1.236 + return Append(endianness, size, value);
1.237 +
1.238 + // This will get caught when the references are resolved, but it's
1.239 + // nicer to find out earlier.
1.240 + assert(endianness != kUnsetEndian);
1.241 +
1.242 + references_.push_back(Reference(contents_.size(), endianness, size, label));
1.243 + contents_.append(size, 0);
1.244 + return *this;
1.245 +}
1.246 +
1.247 +#define ENDIANNESS_L kLittleEndian
1.248 +#define ENDIANNESS_B kBigEndian
1.249 +#define ENDIANNESS(e) ENDIANNESS_ ## e
1.250 +
1.251 +#define DEFINE_SHORT_APPEND_NUMBER_ENDIAN(e, bits) \
1.252 + Section &Section::e ## bits(uint ## bits ## _t v) { \
1.253 + InsertEndian(ENDIANNESS(e), bits / 8, v, \
1.254 + back_insert_iterator<string>(contents_)); \
1.255 + return *this; \
1.256 + }
1.257 +
1.258 +#define DEFINE_SHORT_APPEND_LABEL_ENDIAN(e, bits) \
1.259 + Section &Section::e ## bits(const Label &v) { \
1.260 + return Append(ENDIANNESS(e), bits / 8, v); \
1.261 + }
1.262 +
1.263 +// Define L16, B32, and friends.
1.264 +#define DEFINE_SHORT_APPEND_ENDIAN(e, bits) \
1.265 + DEFINE_SHORT_APPEND_NUMBER_ENDIAN(e, bits) \
1.266 + DEFINE_SHORT_APPEND_LABEL_ENDIAN(e, bits)
1.267 +
1.268 +DEFINE_SHORT_APPEND_LABEL_ENDIAN(L, 8);
1.269 +DEFINE_SHORT_APPEND_LABEL_ENDIAN(B, 8);
1.270 +DEFINE_SHORT_APPEND_ENDIAN(L, 16);
1.271 +DEFINE_SHORT_APPEND_ENDIAN(L, 32);
1.272 +DEFINE_SHORT_APPEND_ENDIAN(L, 64);
1.273 +DEFINE_SHORT_APPEND_ENDIAN(B, 16);
1.274 +DEFINE_SHORT_APPEND_ENDIAN(B, 32);
1.275 +DEFINE_SHORT_APPEND_ENDIAN(B, 64);
1.276 +
1.277 +#define DEFINE_SHORT_APPEND_NUMBER_DEFAULT(bits) \
1.278 + Section &Section::D ## bits(uint ## bits ## _t v) { \
1.279 + InsertEndian(endianness_, bits / 8, v, \
1.280 + back_insert_iterator<string>(contents_)); \
1.281 + return *this; \
1.282 + }
1.283 +#define DEFINE_SHORT_APPEND_LABEL_DEFAULT(bits) \
1.284 + Section &Section::D ## bits(const Label &v) { \
1.285 + return Append(endianness_, bits / 8, v); \
1.286 + }
1.287 +#define DEFINE_SHORT_APPEND_DEFAULT(bits) \
1.288 + DEFINE_SHORT_APPEND_NUMBER_DEFAULT(bits) \
1.289 + DEFINE_SHORT_APPEND_LABEL_DEFAULT(bits)
1.290 +
1.291 +DEFINE_SHORT_APPEND_LABEL_DEFAULT(8)
1.292 +DEFINE_SHORT_APPEND_DEFAULT(16);
1.293 +DEFINE_SHORT_APPEND_DEFAULT(32);
1.294 +DEFINE_SHORT_APPEND_DEFAULT(64);
1.295 +
1.296 +Section &Section::Append(const Section §ion) {
1.297 + size_t base = contents_.size();
1.298 + contents_.append(section.contents_);
1.299 + for (vector<Reference>::const_iterator it = section.references_.begin();
1.300 + it != section.references_.end(); it++)
1.301 + references_.push_back(Reference(base + it->offset, it->endianness,
1.302 + it->size, it->label));
1.303 + return *this;
1.304 +}
1.305 +
1.306 +Section &Section::LEB128(long long value) {
1.307 + while (value < -0x40 || 0x3f < value) {
1.308 + contents_ += (value & 0x7f) | 0x80;
1.309 + if (value < 0)
1.310 + value = (value >> 7) | ~(((unsigned long long) -1) >> 7);
1.311 + else
1.312 + value = (value >> 7);
1.313 + }
1.314 + contents_ += value & 0x7f;
1.315 + return *this;
1.316 +}
1.317 +
1.318 +Section &Section::ULEB128(uint64_t value) {
1.319 + while (value > 0x7f) {
1.320 + contents_ += (value & 0x7f) | 0x80;
1.321 + value = (value >> 7);
1.322 + }
1.323 + contents_ += value;
1.324 + return *this;
1.325 +}
1.326 +
1.327 +Section &Section::Align(size_t alignment, uint8_t pad_byte) {
1.328 + // ALIGNMENT must be a power of two.
1.329 + assert(((alignment - 1) & alignment) == 0);
1.330 + size_t new_size = (contents_.size() + alignment - 1) & ~(alignment - 1);
1.331 + contents_.append(new_size - contents_.size(), pad_byte);
1.332 + assert((contents_.size() & (alignment - 1)) == 0);
1.333 + return *this;
1.334 +}
1.335 +
1.336 +void Section::Clear() {
1.337 + contents_.clear();
1.338 + references_.clear();
1.339 +}
1.340 +
1.341 +bool Section::GetContents(string *contents) {
1.342 + // For each label reference, find the label's value, and patch it into
1.343 + // the section's contents.
1.344 + for (size_t i = 0; i < references_.size(); i++) {
1.345 + Reference &r = references_[i];
1.346 + uint64_t value;
1.347 + if (!r.label.IsKnownConstant(&value)) {
1.348 + fprintf(stderr, "Undefined label #%zu at offset 0x%zx\n", i, r.offset);
1.349 + return false;
1.350 + }
1.351 + assert(r.offset < contents_.size());
1.352 + assert(contents_.size() - r.offset >= r.size);
1.353 + InsertEndian(r.endianness, r.size, value, contents_.begin() + r.offset);
1.354 + }
1.355 + contents->clear();
1.356 + std::swap(contents_, *contents);
1.357 + references_.clear();
1.358 + return true;
1.359 +}
1.360 +
1.361 +} // namespace test_assembler
1.362 +} // namespace google_breakpad
