aboutsummaryrefslogtreecommitdiff
path: root/src/common/test_assembler.h
blob: 560f7aef32f30ea48853dc5747ee93f161531588 (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
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
// -*- mode: C++ -*-

// Copyright (c) 2010, Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// Original author: Jim Blandy <jimb@mozilla.com> <jimb@red-bean.com>

// test-assembler.h: interface to class for building complex binary streams.

// To test the Breakpad symbol dumper and processor thoroughly, for
// all combinations of host system and minidump processor
// architecture, we need to be able to easily generate complex test
// data like debugging information and minidump files.
// 
// For example, if we want our unit tests to provide full code
// coverage for stack walking, it may be difficult to persuade the
// compiler to generate every possible sort of stack walking
// information that we want to support; there are probably DWARF CFI
// opcodes that GCC never emits. Similarly, if we want to test our
// error handling, we will need to generate damaged minidumps or
// debugging information that (we hope) the client or compiler will
// never produce on its own.
//
// google_breakpad::TestAssembler provides a predictable and
// (relatively) simple way to generate complex formatted data streams
// like minidumps and CFI. Furthermore, because TestAssembler is
// portable, developers without access to (say) Visual Studio or a
// SPARC assembler can still work on test data for those targets.

#ifndef PROCESSOR_TEST_ASSEMBLER_H_
#define PROCESSOR_TEST_ASSEMBLER_H_

#include <list>
#include <vector>
#include <string>

#include "google_breakpad/common/breakpad_types.h"

namespace google_breakpad {

using std::list;
using std::string;
using std::vector;

namespace TestAssembler {

// A Label represents a value not yet known that we need to store in a
// section. As long as all the labels a section refers to are defined
// by the time we retrieve its contents as bytes, we can use undefined
// labels freely in that section's construction.
//
// A label can be in one of three states:
// - undefined,
// - defined as the sum of some other label and a constant, or
// - a constant.
// 
// A label's value never changes, but it can accumulate constraints.
// Adding labels and integers is permitted, and yields a label.
// Subtracting a constant from a label is permitted, and also yields a
// label. Subtracting two labels that have some relationship to each
// other is permitted, and yields a constant.
//
// For example:
//
//   Label a;               // a's value is undefined
//   Label b;               // b's value is undefined
//   {
//     Label c = a + 4;     // okay, even though a's value is unknown
//     b = c + 4;           // also okay; b is now a+8
//   }
//   Label d = b - 2;       // okay; d == a+6, even though c is gone
//   d.Value();             // error: d's value is not yet known
//   d - a;                 // is 6, even though their values are not known
//   a = 12;                // now b == 20, and d == 18
//   d.Value();             // 18: no longer an error
//   b.Value();             // 20
//   d = 10;                // error: d is already defined.
//
// Label objects' lifetimes are unconstrained: notice that, in the
// above example, even though a and b are only related through c, and
// c goes out of scope, the assignment to a sets b's value as well. In
// particular, it's not necessary to ensure that a Label lives beyond
// Sections that refer to it.
class Label {
 public:
  Label();                      // An undefined label.
  Label(u_int64_t value);       // A label with a fixed value
  Label(const Label &value);    // A label equal to another.
  ~Label();

  // Return this label's value; it must be known.
  //
  // Providing this as a cast operator is nifty, but the conversions
  // happen in unexpected places. In particular, ISO C++ says that
  // Label + size_t becomes ambigious, because it can't decide whether
  // to convert the Label to a u_int64_t and then to a size_t, or use
  // the overloaded operator that returns a new label, even though the
  // former could fail if the label is not yet defined and the latter won't.
  u_int64_t Value() const;

  Label &operator=(u_int64_t value);
  Label &operator=(const Label &value);
  Label operator+(u_int64_t addend) const;
  Label operator-(u_int64_t subtrahend) const;
  u_int64_t operator-(const Label &subtrahend) const;

  // We could also provide == and != that work on undefined, but
  // related, labels.

  // Return true if this label's value is known. If VALUE_P is given,
  // set *VALUE_P to the known value if returning true.
  bool IsKnownConstant(u_int64_t *value_p = NULL) const;

  // Return true if the offset from LABEL to this label is known. If
  // OFFSET_P is given, set *OFFSET_P to the offset when returning true.
  //
  // You can think of l.KnownOffsetFrom(m, &d) as being like 'd = l-m',
  // except that it also returns a value indicating whether the
  // subtraction is possible given what we currently know of l and m.
  // It can be possible even if we don't know l and m's values. For
  // example:
  // 
  //   Label l, m;
  //   m = l + 10;
  //   l.IsKnownConstant();             // false
  //   m.IsKnownConstant();             // false
  //   u_int64_t d;                     
  //   l.IsKnownOffsetFrom(m, &d);      // true, and sets d to -10.
  //   l-m                              // -10
  //   m-l                              // 10
  //   m.Value()                        // error: m's value is not known
  bool IsKnownOffsetFrom(const Label &label, u_int64_t *offset_p = NULL) const;

 private:
  // A label's value, or if that is not yet known, how the value is
  // related to other labels' values. A binding may be:
  // - a known constant,
  // - constrained to be equal to some other binding plus a constant, or
  // - unconstrained, and free to take on any value.
  //
  // Many labels may point to a single binding, and each binding may
  // refer to another, so bindings and labels form trees whose leaves
  // are labels, whose interior nodes (and roots) are bindings, and
  // where links point from children to parents. Bindings are
  // reference counted, allowing labels to be lightweight, copyable,
  // assignable, placed in containers, and so on.
  class Binding {
   public:
    Binding();
    Binding(u_int64_t addend);
    ~Binding();

    // Increment our reference count.
    void Acquire() { reference_count_++; };
    // Decrement our reference count, and return true if it is zero.
    bool Release() { return --reference_count_ == 0; }

    // Set this binding to be equal to BINDING + ADDEND. If BINDING is
    // NULL, then set this binding to the known constant ADDEND.
    // Update every binding on this binding's chain to point directly
    // to BINDING, or to be a constant, with addends adjusted
    // appropriately.
    void Set(Binding *binding, u_int64_t value);

    // Return what we know about the value of this binding.
    // - If this binding's value is a known constant, set BASE to
    //   NULL, and set ADDEND to its value.
    // - If this binding is not a known constant but related to other
    //   bindings, set BASE to the binding at the end of the relation
    //   chain (which will always be unconstrained), and set ADDEND to the
    //   value to add to that binding's value to get this binding's
    //   value.
    // - If this binding is unconstrained, set BASE to this, and leave
    //   ADDEND unchanged.
    void Get(Binding **base, u_int64_t *addend);

   private:
    // There are three cases:
    //
    // - A binding representing a known constant value has base_ NULL,
    //   and addend_ equal to the value.
    //
    // - A binding representing a completely unconstrained value has
    //   base_ pointing to this; addend_ is unused.
    //
    // - A binding whose value is related to some other binding's
    //   value has base_ pointing to that other binding, and addend_
    //   set to the amount to add to that binding's value to get this
    //   binding's value. We only represent relationships of the form
    //   x = y+c.
    //
    // Thus, the bind_ links form a chain terminating in either a
    // known constant value or a completely unconstrained value. Most
    // operations on bindings do path compression: they change every
    // binding on the chain to point directly to the final value,
    // adjusting addends as appropriate.
    Binding *base_;
    u_int64_t addend_;

    // The number of Labels and Bindings pointing to this binding.
    // (When a binding points to itself, indicating a completely
    // unconstrained binding, that doesn't count as a reference.)
    int reference_count_;
  };

  // This label's value.
  Binding *value_;
};

inline Label operator+(u_int64_t a, const Label &l) { return l + a; }
// Note that int-Label isn't defined, as negating a Label is not an
// operation we support.

// Conventions for representing larger numbers as sequences of bytes.
enum Endianness {
  kBigEndian,        // Big-endian: the most significant byte comes first.
  kLittleEndian,     // Little-endian: the least significant byte comes first.
  kUnsetEndian,      // used internally
};
 
// A section is a sequence of bytes, constructed by appending bytes
// to the end. Sections have a convenient and flexible set of member
// functions for appending data in various formats: big-endian and
// little-endian signed and unsigned values of different sizes;
// LEB128 and ULEB128 values (see below), and raw blocks of bytes.
//
// If you need to append a value to a section that is not convenient
// to compute immediately, you can create a label, append the
// label's value to the section, and then set the label's value
// later, when it's convenient to do so. Once a label's value is
// known, the section class takes care of updating all previously
// appended references to it.
//
// Once all the labels to which a section refers have had their
// values determined, you can get a copy of the section's contents
// as a string.
//
// Note that there is no specified "start of section" label. This is
// because there are typically several different meanings for "the
// start of a section": the offset of the section within an object
// file, the address in memory at which the section's content appear,
// and so on. It's up to the code that uses the Section class to 
// keep track of these explicitly, as they depend on the application.
class Section {
 public:
  Section(Endianness endianness = kUnsetEndian)
      : endianness_(endianness) { };
  ~Section() { };

  // Set the default endianness of this section to ENDIANNESS. This
  // sets the behavior of the D<N> appending functions. If the
  // assembler's default endianness was set, this is the 
  void set_endianness(Endianness endianness) {
    endianness_ = endianness;
  }

  // Return the default endianness of this section.
  Endianness endianness() const { return endianness_; }

  // Append the SIZE bytes at DATA or the contents of STRING to the
  // end of this section. Return a reference to this section.
  Section &Append(const u_int8_t *data, size_t size) {
    contents_.append(reinterpret_cast<const char *>(data), size);
    return *this;
  };
  Section &Append(const string &data) {
    contents_.append(data);
    return *this;
  };

  // Append SIZE copies of BYTE to the end of this section. Return a
  // reference to this section.
  Section &Append(size_t size, u_int8_t byte) {
    contents_.append(size, (char) byte);
    return *this;
  }
      
  // Append NUMBER to this section. ENDIANNESS is the endianness to
  // use to write the number. SIZE is the length of the number in
  // bytes. Return a reference to this section.
  Section &Append(Endianness endianness, size_t size, u_int64_t number);
  Section &Append(Endianness endianness, size_t size, const Label &label);

  // Append SECTION to the end of this section. The labels SECTION
  // refers to need not be defined yet.
  //
  // Note that this has no effect on any Labels' values, or on
  // SECTION. If placing SECTION within 'this' provides new
  // constraints on existing labels' values, then it's up to the
  // caller to fiddle with those labels as needed.
  Section &Append(const Section &section);

  // Append the contents of DATA as a series of bytes terminated by
  // a NULL character.
  Section &AppendCString(const string &data) {
    Append(data);
    contents_ += '\0';
    return *this;
  }

  // Append VALUE or LABEL to this section, with the given bit width and
  // endianness. Return a reference to this section.
  //
  // The names of these functions have the form <ENDIANNESS><BITWIDTH>:
  // <ENDIANNESS> is either 'L' (little-endian, least significant byte first),
  //                        'B' (big-endian, most significant byte first), or
  //                        'D' (default, the section's default endianness)
  // <BITWIDTH> is 8, 16, 32, or 64.
  //
  // Since endianness doesn't matter for a single byte, all the
  // <BITWIDTH>=8 functions are equivalent.
  //
  // These can be used to write both signed and unsigned values, as
  // the compiler will properly sign-extend a signed value before
  // passing it to the function, at which point the function's
  // behavior is the same either way.
  Section &L8(u_int8_t value) { contents_ += value; return *this; }
  Section &B8(u_int8_t value) { contents_ += value; return *this; }
  Section &D8(u_int8_t value) { contents_ += value; return *this; }
  Section &L16(u_int16_t), &L32(u_int32_t), &L64(u_int64_t),
          &B16(u_int16_t), &B32(u_int32_t), &B64(u_int64_t),
          &D16(u_int16_t), &D32(u_int32_t), &D64(u_int64_t);
  Section &L8(const Label &label),  &L16(const Label &label),
          &L32(const Label &label), &L64(const Label &label),
          &B8(const Label &label),  &B16(const Label &label),
          &B32(const Label &label), &B64(const Label &label),
          &D8(const Label &label),  &D16(const Label &label),
          &D32(const Label &label), &D64(const Label &label);

  // Append VALUE in a signed LEB128 (Little-Endian Base 128) form.
  // 
  // The signed LEB128 representation of an integer N is a variable
  // number of bytes:
  //
  // - If N is between -0x40 and 0x3f, then its signed LEB128
  //   representation is a single byte whose value is N.
  // 
  // - Otherwise, its signed LEB128 representation is (N & 0x7f) |
  //   0x80, followed by the signed LEB128 representation of N / 128,
  //   rounded towards negative infinity.
  //
  // In other words, we break VALUE into groups of seven bits, put
  // them in little-endian order, and then write them as eight-bit
  // bytes with the high bit on all but the last.
  //
  // Note that VALUE cannot be a Label (we would have to implement
  // relaxation).
  Section &LEB128(long long value);

  // Append VALUE in unsigned LEB128 (Little-Endian Base 128) form.
  // 
  // The unsigned LEB128 representation of an integer N is a variable
  // number of bytes:
  //
  // - If N is between 0 and 0x7f, then its unsigned LEB128
  //   representation is a single byte whose value is N.
  // 
  // - Otherwise, its unsigned LEB128 representation is (N & 0x7f) |
  //   0x80, followed by the unsigned LEB128 representation of N /
  //   128, rounded towards negative infinity.
  //
  // Note that VALUE cannot be a Label (we would have to implement
  // relaxation).
  Section &ULEB128(u_int64_t value);

  // Jump to the next location aligned on an ALIGNMENT-byte boundary,
  // relative to the start of the section. Fill the gap with PAD_BYTE.
  // ALIGNMENT must be a power of two. Return a reference to this
  // section.
  Section &Align(size_t alignment, u_int8_t pad_byte = 0);

  // Clear the contents of this section.
  void Clear();

  // Return the current size of the section.
  size_t Size() const { return contents_.size(); }

  // Return a label representing the start of the section.
  // 
  // It is up to the user whether this label represents the section's
  // position in an object file, the section's address in memory, or
  // what have you; some applications may need both, in which case
  // this simple-minded interface won't be enough. This class only
  // provides a single start label, for use with the Here and Mark
  // member functions.
  //
  // Ideally, we'd provide this in a subclass that actually knows more
  // about the application at hand and can provide an appropriate
  // collection of start labels. But then the appending member
  // functions like Append and D32 would return a reference to the
  // base class, not the derived class, and the chaining won't work.
  // Since the only value here is in pretty notation, that's a fatal
  // flaw.
  Label start() const { return start_; }

  // Return a label representing the point at which the next Appended
  // item will appear in the section, relative to start().
  Label Here() const { return start_ + Size(); }

  // Set *LABEL to Here, and return a reference to this section.
  Section &Mark(Label *label) { *label = Here(); return *this; }

  // If there are no undefined label references left in this
  // section, set CONTENTS to the contents of this section, as a
  // string, and clear this section. Return true on success, or false
  // if there were still undefined labels.
  bool GetContents(string *contents);

 private:
  // Used internally. A reference to a label's value.
  struct Reference {
    Reference(size_t set_offset, Endianness set_endianness,  size_t set_size,
              const Label &set_label)
        : offset(set_offset), endianness(set_endianness), size(set_size),
          label(set_label) { }
      
    // The offset of the reference within the section.
    size_t offset;

    // The endianness of the reference.
    Endianness endianness;

    // The size of the reference.
    size_t size;

    // The label to which this is a reference.
    Label label;
  };

  // The default endianness of this section.
  Endianness endianness_;

  // The contents of the section.
  string contents_;
  
  // References to labels within those contents.
  vector<Reference> references_;

  // A label referring to the beginning of the section.
  Label start_;
};

}  // namespace TestAssembler
}  // namespace google_breakpad

#endif  // PROCESSOR_TEST_ASSEMBLER_H_