1// Copyright (c) 2010, Google Inc. 2// All rights reserved. 3// 4// Redistribution and use in source and binary forms, with or without 5// modification, are permitted provided that the following conditions are 6// met: 7// 8// * Redistributions of source code must retain the above copyright 9// notice, this list of conditions and the following disclaimer. 10// * Redistributions in binary form must reproduce the above 11// copyright notice, this list of conditions and the following disclaimer 12// in the documentation and/or other materials provided with the 13// distribution. 14// * Neither the name of Google Inc. nor the names of its 15// contributors may be used to endorse or promote products derived from 16// this software without specific prior written permission. 17// 18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 30// Original author: Jim Blandy <jimb@mozilla.com> <jimb@red-bean.com> 31 32// test_assembler.cc: Implementation of google_breakpad::TestAssembler. 33// See test_assembler.h for details. 34 35#include "common/test_assembler.h" 36 37#include <assert.h> 38#include <stdio.h> 39 40#include <iterator> 41 42namespace google_breakpad { 43namespace test_assembler { 44 45using std::back_insert_iterator; 46 47Label::Label() : value_(new Binding()) { } 48Label::Label(uint64_t value) : value_(new Binding(value)) { } 49Label::Label(const Label &label) { 50 value_ = label.value_; 51 value_->Acquire(); 52} 53Label::~Label() { 54 if (value_->Release()) delete value_; 55} 56 57Label &Label::operator=(uint64_t value) { 58 value_->Set(NULL, value); 59 return *this; 60} 61 62Label &Label::operator=(const Label &label) { 63 value_->Set(label.value_, 0); 64 return *this; 65} 66 67Label Label::operator+(uint64_t addend) const { 68 Label l; 69 l.value_->Set(this->value_, addend); 70 return l; 71} 72 73Label Label::operator-(uint64_t subtrahend) const { 74 Label l; 75 l.value_->Set(this->value_, -subtrahend); 76 return l; 77} 78 79// When NDEBUG is #defined, assert doesn't evaluate its argument. This 80// means you can't simply use assert to check the return value of a 81// function with necessary side effects. 82// 83// ALWAYS_EVALUATE_AND_ASSERT(x) evaluates x regardless of whether 84// NDEBUG is #defined; when NDEBUG is not #defined, it further asserts 85// that x is true. 86#ifdef NDEBUG 87#define ALWAYS_EVALUATE_AND_ASSERT(x) x 88#else 89#define ALWAYS_EVALUATE_AND_ASSERT(x) assert(x) 90#endif 91 92uint64_t Label::operator-(const Label &label) const { 93 uint64_t offset; 94 ALWAYS_EVALUATE_AND_ASSERT(IsKnownOffsetFrom(label, &offset)); 95 return offset; 96} 97 98uint64_t Label::Value() const { 99 uint64_t v = 0; 100 ALWAYS_EVALUATE_AND_ASSERT(IsKnownConstant(&v)); 101 return v; 102}; 103 104bool Label::IsKnownConstant(uint64_t *value_p) const { 105 Binding *base; 106 uint64_t addend; 107 value_->Get(&base, &addend); 108 if (base != NULL) return false; 109 if (value_p) *value_p = addend; 110 return true; 111} 112 113bool Label::IsKnownOffsetFrom(const Label &label, uint64_t *offset_p) const 114{ 115 Binding *label_base, *this_base; 116 uint64_t label_addend, this_addend; 117 label.value_->Get(&label_base, &label_addend); 118 value_->Get(&this_base, &this_addend); 119 // If this and label are related, Get will find their final 120 // common ancestor, regardless of how indirect the relation is. This 121 // comparison also handles the constant vs. constant case. 122 if (this_base != label_base) return false; 123 if (offset_p) *offset_p = this_addend - label_addend; 124 return true; 125} 126 127Label::Binding::Binding() : base_(this), addend_(), reference_count_(1) { } 128 129Label::Binding::Binding(uint64_t addend) 130 : base_(NULL), addend_(addend), reference_count_(1) { } 131 132Label::Binding::~Binding() { 133 assert(reference_count_ == 0); 134 if (base_ && base_ != this && base_->Release()) 135 delete base_; 136} 137 138void Label::Binding::Set(Binding *binding, uint64_t addend) { 139 if (!base_ && !binding) { 140 // We're equating two constants. This could be okay. 141 assert(addend_ == addend); 142 } else if (!base_) { 143 // We are a known constant, but BINDING may not be, so turn the 144 // tables and try to set BINDING's value instead. 145 binding->Set(NULL, addend_ - addend); 146 } else { 147 if (binding) { 148 // Find binding's final value. Since the final value is always either 149 // completely unconstrained or a constant, never a reference to 150 // another variable (otherwise, it wouldn't be final), this 151 // guarantees we won't create cycles here, even for code like this: 152 // l = m, m = n, n = l; 153 uint64_t binding_addend; 154 binding->Get(&binding, &binding_addend); 155 addend += binding_addend; 156 } 157 158 // It seems likely that setting a binding to itself is a bug 159 // (although I can imagine this might turn out to be helpful to 160 // permit). 161 assert(binding != this); 162 163 if (base_ != this) { 164 // Set the other bindings on our chain as well. Note that this 165 // is sufficient even though binding relationships form trees: 166 // All binding operations traverse their chains to the end, and 167 // all bindings related to us share some tail of our chain, so 168 // they will see the changes we make here. 169 base_->Set(binding, addend - addend_); 170 // We're not going to use base_ any more. 171 if (base_->Release()) delete base_; 172 } 173 174 // Adopt BINDING as our base. Note that it should be correct to 175 // acquire here, after the release above, even though the usual 176 // reference-counting rules call for acquiring first, and then 177 // releasing: the self-reference assertion above should have 178 // complained if BINDING were 'this' or anywhere along our chain, 179 // so we didn't release BINDING. 180 if (binding) binding->Acquire(); 181 base_ = binding; 182 addend_ = addend; 183 } 184} 185 186void Label::Binding::Get(Binding **base, uint64_t *addend) { 187 if (base_ && base_ != this) { 188 // Recurse to find the end of our reference chain (the root of our 189 // tree), and then rewrite every binding along the chain to refer 190 // to it directly, adjusting addends appropriately. (This is why 191 // this member function isn't this-const.) 192 Binding *final_base; 193 uint64_t final_addend; 194 base_->Get(&final_base, &final_addend); 195 if (final_base) final_base->Acquire(); 196 if (base_->Release()) delete base_; 197 base_ = final_base; 198 addend_ += final_addend; 199 } 200 *base = base_; 201 *addend = addend_; 202} 203 204template<typename Inserter> 205static inline void InsertEndian(test_assembler::Endianness endianness, 206 size_t size, uint64_t number, Inserter dest) { 207 assert(size > 0); 208 if (endianness == kLittleEndian) { 209 for (size_t i = 0; i < size; i++) { 210 *dest++ = (char) (number & 0xff); 211 number >>= 8; 212 } 213 } else { 214 assert(endianness == kBigEndian); 215 // The loop condition is odd, but it's correct for size_t. 216 for (size_t i = size - 1; i < size; i--) 217 *dest++ = (char) ((number >> (i * 8)) & 0xff); 218 } 219} 220 221Section &Section::Append(Endianness endianness, size_t size, uint64_t number) { 222 InsertEndian(endianness, size, number, 223 back_insert_iterator<string>(contents_)); 224 return *this; 225} 226 227Section &Section::Append(Endianness endianness, size_t size, 228 const Label &label) { 229 // If this label's value is known, there's no reason to waste an 230 // entry in references_ on it. 231 uint64_t value; 232 if (label.IsKnownConstant(&value)) 233 return Append(endianness, size, value); 234 235 // This will get caught when the references are resolved, but it's 236 // nicer to find out earlier. 237 assert(endianness != kUnsetEndian); 238 239 references_.push_back(Reference(contents_.size(), endianness, size, label)); 240 contents_.append(size, 0); 241 return *this; 242} 243 244#define ENDIANNESS_L kLittleEndian 245#define ENDIANNESS_B kBigEndian 246#define ENDIANNESS(e) ENDIANNESS_ ## e 247 248#define DEFINE_SHORT_APPEND_NUMBER_ENDIAN(e, bits) \ 249 Section &Section::e ## bits(uint ## bits ## _t v) { \ 250 InsertEndian(ENDIANNESS(e), bits / 8, v, \ 251 back_insert_iterator<string>(contents_)); \ 252 return *this; \ 253 } 254 255#define DEFINE_SHORT_APPEND_LABEL_ENDIAN(e, bits) \ 256 Section &Section::e ## bits(const Label &v) { \ 257 return Append(ENDIANNESS(e), bits / 8, v); \ 258 } 259 260// Define L16, B32, and friends. 261#define DEFINE_SHORT_APPEND_ENDIAN(e, bits) \ 262 DEFINE_SHORT_APPEND_NUMBER_ENDIAN(e, bits) \ 263 DEFINE_SHORT_APPEND_LABEL_ENDIAN(e, bits) 264 265DEFINE_SHORT_APPEND_LABEL_ENDIAN(L, 8); 266DEFINE_SHORT_APPEND_LABEL_ENDIAN(B, 8); 267DEFINE_SHORT_APPEND_ENDIAN(L, 16); 268DEFINE_SHORT_APPEND_ENDIAN(L, 32); 269DEFINE_SHORT_APPEND_ENDIAN(L, 64); 270DEFINE_SHORT_APPEND_ENDIAN(B, 16); 271DEFINE_SHORT_APPEND_ENDIAN(B, 32); 272DEFINE_SHORT_APPEND_ENDIAN(B, 64); 273 274#define DEFINE_SHORT_APPEND_NUMBER_DEFAULT(bits) \ 275 Section &Section::D ## bits(uint ## bits ## _t v) { \ 276 InsertEndian(endianness_, bits / 8, v, \ 277 back_insert_iterator<string>(contents_)); \ 278 return *this; \ 279 } 280#define DEFINE_SHORT_APPEND_LABEL_DEFAULT(bits) \ 281 Section &Section::D ## bits(const Label &v) { \ 282 return Append(endianness_, bits / 8, v); \ 283 } 284#define DEFINE_SHORT_APPEND_DEFAULT(bits) \ 285 DEFINE_SHORT_APPEND_NUMBER_DEFAULT(bits) \ 286 DEFINE_SHORT_APPEND_LABEL_DEFAULT(bits) 287 288DEFINE_SHORT_APPEND_LABEL_DEFAULT(8) 289DEFINE_SHORT_APPEND_DEFAULT(16); 290DEFINE_SHORT_APPEND_DEFAULT(32); 291DEFINE_SHORT_APPEND_DEFAULT(64); 292 293Section &Section::Append(const Section §ion) { 294 size_t base = contents_.size(); 295 contents_.append(section.contents_); 296 for (vector<Reference>::const_iterator it = section.references_.begin(); 297 it != section.references_.end(); it++) 298 references_.push_back(Reference(base + it->offset, it->endianness, 299 it->size, it->label)); 300 return *this; 301} 302 303Section &Section::LEB128(long long value) { 304 while (value < -0x40 || 0x3f < value) { 305 contents_ += (value & 0x7f) | 0x80; 306 if (value < 0) 307 value = (value >> 7) | ~(((unsigned long long) -1) >> 7); 308 else 309 value = (value >> 7); 310 } 311 contents_ += value & 0x7f; 312 return *this; 313} 314 315Section &Section::ULEB128(uint64_t value) { 316 while (value > 0x7f) { 317 contents_ += (value & 0x7f) | 0x80; 318 value = (value >> 7); 319 } 320 contents_ += value; 321 return *this; 322} 323 324Section &Section::Align(size_t alignment, uint8_t pad_byte) { 325 // ALIGNMENT must be a power of two. 326 assert(((alignment - 1) & alignment) == 0); 327 size_t new_size = (contents_.size() + alignment - 1) & ~(alignment - 1); 328 contents_.append(new_size - contents_.size(), pad_byte); 329 assert((contents_.size() & (alignment - 1)) == 0); 330 return *this; 331} 332 333void Section::Clear() { 334 contents_.clear(); 335 references_.clear(); 336} 337 338bool Section::GetContents(string *contents) { 339 // For each label reference, find the label's value, and patch it into 340 // the section's contents. 341 for (size_t i = 0; i < references_.size(); i++) { 342 Reference &r = references_[i]; 343 uint64_t value; 344 if (!r.label.IsKnownConstant(&value)) { 345 fprintf(stderr, "Undefined label #%zu at offset 0x%zx\n", i, r.offset); 346 return false; 347 } 348 assert(r.offset < contents_.size()); 349 assert(contents_.size() - r.offset >= r.size); 350 InsertEndian(r.endianness, r.size, value, contents_.begin() + r.offset); 351 } 352 contents->clear(); 353 std::swap(contents_, *contents); 354 references_.clear(); 355 return true; 356} 357 358} // namespace test_assembler 359} // namespace google_breakpad 360