Date: Sat, 24 May 2014 16:33:27 GMT From: dpl@FreeBSD.org To: svn-soc-all@FreeBSD.org Subject: socsvn commit: r268551 - in soc2014/dpl: bpfjit netmap-ipfw netmap-ipfw/extra netmap-ipfw/extra/sys netmap-ipfw/extra/sys/contrib netmap-ipfw/extra/sys/contrib/pf netmap-ipfw/extra/sys/contrib/pf/n... Message-ID: <201405241633.s4OGXRbW067748@socsvn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: dpl Date: Sat May 24 16:33:26 2014 New Revision: 268551 URL: http://svnweb.FreeBSD.org/socsvn/?view=rev&rev=268551 Log: Add the code of netmap-ipfw and a theraven@ implementation of bpd using JIT. It will be used as an example. Added: soc2014/dpl/bpfjit/ soc2014/dpl/bpfjit/Makefile soc2014/dpl/bpfjit/dtc.cc soc2014/dpl/bpfjit/jit.cc soc2014/dpl/bpfjit/mktest.c soc2014/dpl/bpfjit/runtest.sh soc2014/dpl/netmap-ipfw/ soc2014/dpl/netmap-ipfw/BSDmakefile soc2014/dpl/netmap-ipfw/Makefile soc2014/dpl/netmap-ipfw/Makefile.inc soc2014/dpl/netmap-ipfw/Makefile.kipfw soc2014/dpl/netmap-ipfw/README soc2014/dpl/netmap-ipfw/extra/ soc2014/dpl/netmap-ipfw/extra/expand_number.c soc2014/dpl/netmap-ipfw/extra/glue.c soc2014/dpl/netmap-ipfw/extra/glue.h soc2014/dpl/netmap-ipfw/extra/humanize_number.c soc2014/dpl/netmap-ipfw/extra/ipfw2_mod.c soc2014/dpl/netmap-ipfw/extra/linux_defs.h soc2014/dpl/netmap-ipfw/extra/missing.c soc2014/dpl/netmap-ipfw/extra/missing.h soc2014/dpl/netmap-ipfw/extra/netmap_io.c soc2014/dpl/netmap-ipfw/extra/session.c soc2014/dpl/netmap-ipfw/extra/sys/ soc2014/dpl/netmap-ipfw/extra/sys/contrib/ soc2014/dpl/netmap-ipfw/extra/sys/contrib/pf/ soc2014/dpl/netmap-ipfw/extra/sys/contrib/pf/net/ soc2014/dpl/netmap-ipfw/extra/sys/contrib/pf/net/pfvar.h soc2014/dpl/netmap-ipfw/extra/sys/sys/ soc2014/dpl/netmap-ipfw/extra/sys/sys/kernel.h soc2014/dpl/netmap-ipfw/extra/sys/sys/malloc.h soc2014/dpl/netmap-ipfw/extra/sys/sys/mbuf.h soc2014/dpl/netmap-ipfw/extra/sys/sys/module.h soc2014/dpl/netmap-ipfw/extra/sys/sys/systm.h soc2014/dpl/netmap-ipfw/extra/sys/sys/taskqueue.h soc2014/dpl/netmap-ipfw/ipfw/ soc2014/dpl/netmap-ipfw/ipfw/Makefile soc2014/dpl/netmap-ipfw/ipfw/altq.c soc2014/dpl/netmap-ipfw/ipfw/dummynet.c soc2014/dpl/netmap-ipfw/ipfw/ipfw2.c soc2014/dpl/netmap-ipfw/ipfw/ipfw2.h soc2014/dpl/netmap-ipfw/ipfw/ipv6.c soc2014/dpl/netmap-ipfw/ipfw/main.c soc2014/dpl/netmap-ipfw/ipfw/nat.c soc2014/dpl/netmap-ipfw/sys/ soc2014/dpl/netmap-ipfw/sys/net/ soc2014/dpl/netmap-ipfw/sys/net/pfil.h soc2014/dpl/netmap-ipfw/sys/net/radix.c soc2014/dpl/netmap-ipfw/sys/net/radix.h soc2014/dpl/netmap-ipfw/sys/netgraph/ soc2014/dpl/netmap-ipfw/sys/netgraph/ng_ipfw.h soc2014/dpl/netmap-ipfw/sys/netinet/ soc2014/dpl/netmap-ipfw/sys/netinet/in_cksum.c soc2014/dpl/netmap-ipfw/sys/netinet/ip_dummynet.h soc2014/dpl/netmap-ipfw/sys/netinet/ip_fw.h soc2014/dpl/netmap-ipfw/sys/netinet/tcp.h soc2014/dpl/netmap-ipfw/sys/netinet/udp.h soc2014/dpl/netmap-ipfw/sys/netpfil/ soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/ soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/dn_heap.c soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/dn_heap.h soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/dn_sched.h soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/dn_sched_fifo.c soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/dn_sched_prio.c soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/dn_sched_qfq.c soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/dn_sched_rr.c soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/dn_sched_wf2q.c soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/ip_dn_glue.c soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/ip_dn_io.c soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/ip_dn_private.h soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/ip_dummynet.c soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/ip_fw2.c soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/ip_fw_dynamic.c soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/ip_fw_log.c soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/ip_fw_pfil.c soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/ip_fw_private.h soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/ip_fw_sockopt.c soc2014/dpl/netmap-ipfw/sys/netpfil/ipfw/ip_fw_table.c Added: soc2014/dpl/bpfjit/Makefile ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ soc2014/dpl/bpfjit/Makefile Sat May 24 16:33:26 2014 (r268551) @@ -0,0 +1,9 @@ + +jit: jit.cc + clang++ jit.cc `llvm-config --cxxflags --ldflags --libs mcjit jit bitwriter ipo instrumentation x86` -std=c++0x -g + +mktest: mktest.c + clang mktest.c -o mktest + +clean: + rm -f mktest jit out.bin Added: soc2014/dpl/bpfjit/dtc.cc ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ soc2014/dpl/bpfjit/dtc.cc Sat May 24 16:33:26 2014 (r268551) @@ -0,0 +1,3858 @@ +/*- + * Copyright (c) 2012 David Chisnall + * All rights reserved. + * + * This software was developed by SRI International and the University of + * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237) + * ("CTSRD"), as part of the DARPA CRASH research programme. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. + * + * $FreeBSD$ + */ + +//////////////////////////////////////////////////////////////////////////////// +// NOTE: This file has numerous 80-column violations. It needs splitting into +// multiple files and some method definitions moving out of line, which will +// reduce some lines. Most of the very long lines are for loops with +// iterators, which can be shortened a lot when we move this to C++11. +//////////////////////////////////////////////////////////////////////////////// + +#include <sys/mman.h> +#include <sys/stat.h> +#include <sys/types.h> +#include <sys/resource.h> + +#include <time.h> +#include <string.h> +#include <stdlib.h> +#include <stdio.h> +#include <ctype.h> +#include <fcntl.h> +#include <assert.h> +#include <unistd.h> +#include <libgen.h> +#include <inttypes.h> + + +#include <map> +#include <set> +#include <vector> +#include <memory> +#include <algorithm> + +#if __cplusplus < 201103L +#define static_assert(x, y) ((void)0) +#endif + +namespace dtc { + +/** + * Type for a buffer of bytes. This is used for a lot of short-lived temporary + * variables, so may eventually be changed to something like LLVM's + * SmallVector, but currently the program runs in a tiny fraction of a second, + * so this is not an issue. + */ +typedef std::vector<uint8_t> byte_buffer; + +/** + * Helper function to push a big endian value into a byte buffer. We use + * native-endian values for all of the in-memory data structures and only + * transform them into big endian form for output. + */ +template<typename T> +void push_big_endian(byte_buffer &v, T val) +{ + static_assert(sizeof(T) > 1, + "Big endian doesn't make sense for single-byte values"); + for (int bit=(sizeof(T) - 1)*8 ; bit>=0 ; bit-= 8) + { + v.push_back((val >> bit) & 0xff); + } +} + +/** + * Simple inline non-locale-aware check that this is a valid ASCII + * digit. + */ +inline bool isdigit(char c) +{ + return (c >= '0') && (c <= '9'); +} + +/** + * Simple inline non-locale-aware check that this is a valid ASCII + * hex digit. + */ +inline bool ishexdigit(char c) +{ + return ((c >= '0') && (c <= '9')) || ((c >= 'a') && (c <= 'f')) || ((c >= 'A') && (c <= 'Z')); +} + +/** + * Class encapsulating the input file. Can be used as a const char*, but has + * range checking. Attempting to access anything out of range will return a 0 + * byte. The input buffer can be cheaply copied, without copying the + * underlying memory, however it is the user's responsibility to ensure that + * such copies do not persist beyond the lifetime of the underlying memory. + * + * This also contains methods for reporting errors and for consuming the token + * stream. + */ +class input_buffer +{ + protected: + /** + * The buffer. This class doesn't own the buffer, but the + * mmap_input_buffer subclass does. + */ + const char* buffer; + /** + * The size of the buffer. + */ + size_t size; + private: + /** + * The current place in the buffer where we are reading. This class + * keeps a separate size, pointer, and cursor so that we can move + * forwards and backwards and still have checks that we haven't fallen + * off either end. + */ + int cursor; + /** + * Private constructor. This is used to create input buffers that + * refer to the same memory, but have different cursors. + */ + input_buffer(const char* b, size_t s, int c) : buffer(b), size(s), + cursor(c) {} + /** + * Reads forward past any spaces. The DTS format is not whitespace + * sensitive and so we want to scan past whitespace when reading it. + */ + void skip_spaces() + { + if (cursor >= size) { return; } + if (cursor < 0) { return; } + char c = buffer[cursor]; + while ((c == ' ') || (c == '\t') || (c == '\n') || (c == '\f') + || (c == '\v') || (c == '\r')) + { + cursor++; + if (cursor > size) + { + c = '\0'; + } + else + { + c = buffer[cursor]; + } + } + } + public: + /** + * Virtual destructor. Does nothing, but exists so that subclasses + * that own the memory can run cleanup code for deallocating it. + */ + virtual ~input_buffer() {}; + /** + * Constructs an empty buffer. + */ + input_buffer() : buffer(0), size(0), cursor(0) {} + /** + * Constructs a new buffer with a specified memory region and size. + */ + input_buffer(const char* b, size_t s) : buffer(b), size(s), cursor(0){} + /** + * Returns a new input buffer referring into this input, clamped to the + * specified size. If the requested buffer would fall outside the + * range of this one, then it returns an empty buffer. + * + * The returned buffer shares the same underlying storage as the + * original. This is intended to be used for splitting up the various + * sections of a device tree blob. Requesting a size of 0 will give a + * buffer that extends to the end of the available memory. + */ + input_buffer buffer_from_offset(size_t offset, size_t s=0) + { + if (s == 0) + { + s = size - offset; + } + if (offset > size) + { + return input_buffer(); + } + if (s > (size-offset)) + { + return input_buffer(); + } + return input_buffer(&buffer[offset], s); + } + /** + * Returns true if this buffer has no unconsumed space in it. + */ + bool empty() + { + return cursor >= size; + } + /** + * Dereferencing operator, allows the buffer to be treated as a char* + * and dereferenced to give a character. This returns a null byte if + * the cursor is out of range. + */ + inline char operator*() + { + if (cursor >= size) { return '\0'; } + if (cursor < 0) { return '\0'; } + return buffer[cursor]; + } + /** + * Array subscripting operator, returns a character at the specified + * index offset from the current cursor. The offset may be negative, + * to reread characters that have already been read. If the current + * cursor plus offset is outside of the range, this returns a nul + * byte. + */ + inline char operator[](int offset) + { + if (cursor + offset >= size) { return '\0'; } + if (cursor + offset < 0) { return '\0'; } + return buffer[cursor + offset]; + } + /** + * Increments the cursor, iterating forward in the buffer. + */ + inline input_buffer &operator++() + { + cursor++; + return *this; + } + /** + * Cast to char* operator. Returns a pointer into the buffer that can + * be used for constructing strings. + */ + inline operator const char*() + { + if (cursor >= size) { return 0; } + if (cursor < 0) { return 0; } + return &buffer[cursor]; + } + /** + * Consumes a character. Moves the cursor one character forward if the + * next character matches the argument, returning true. If the current + * character does not match the argument, returns false. + */ + inline bool consume(char c) + { + if ((*this)[0] == c) + { + ++(*this); + return true; + } + return false; + } + /** + * Consumes a string. If the (null-terminated) string passed as the + * argument appears in the input, advances the cursor to the end and + * returns true. Returns false if the string does not appear at the + * current point in the input. + */ + bool consume(const char *str) + { + size_t len = strlen(str); + if (len > size - cursor) + { + return false; + } + else + { + for (int i=0 ; i<len ; ++i) + { + if (str[i] != buffer[cursor + i]) + { + return false; + } + } + cursor += len; + return true; + } + return false; + } + /** + * Reads an integer in base 8, 10, or 16. Returns true and advances + * the cursor to the end of the integer if the cursor points to an + * integer, returns false and does not move the cursor otherwise. + * + * The parsed value is returned via the argument. + */ + bool consume_integer(long long &outInt) + { + // The first character must be a digit. Hex and octal strings + // are prefixed by 0 and 0x, respectively. + if (!isdigit((*this)[0])) + { + return false; + } + char *end=0; + outInt = strtoll(&buffer[cursor], &end, 0); + if (end == &buffer[cursor]) + { + return false; + } + cursor = end - buffer; + return true; + } + /** + * Template function that consumes a binary value in big-endian format + * from the input stream. Returns true and advances the cursor if + * there is a value of the correct size. This function assumes that + * all values must be natively aligned, and so advances the cursor to + * the correct alignment before reading. + */ + template<typename T> + bool consume_binary(T &out) + { + int align = 0; + if (cursor % sizeof(T) != 0) + { + align = sizeof(T) - (cursor % sizeof(T)); + } + if (size < cursor + align + sizeof(T)) + { + return false; + } + cursor += align; + assert(cursor % sizeof(T) == 0); + out = 0; + for (int i=0 ; i<sizeof(T) ; ++i) + { + out <<= 8; + out |= (((T)buffer[cursor++]) & 0xff); + } + return true; + } + /** + * Consumes two hex digits and return the resulting byte via the first + * argument. If the next two characters are hex digits, returns true + * and advances the cursor. If not, then returns false and leaves the + * cursor in place. + */ + bool consume_hex_byte(uint8_t &outByte) + { + if (!ishexdigit((*this)[0]) && !ishexdigit((*this)[1])) + { + return false; + } + outByte = (digittoint((*this)[0]) << 4) | digittoint((*this)[1]); + cursor += 2; + return true; + } + /** + * Advances the cursor to the start of the next token, skipping + * comments and whitespace. If the cursor already points to the start + * of a token, then this function does nothing. + */ + input_buffer &next_token() + { + int start; + do { + start = cursor; + skip_spaces(); + // Parse /* comments + if (((*this)[0] == '/') && ((*this)[1] == '*')) + { + // eat the start of the comment + ++(*this); + ++(*this); + do { + // Find the ending * of */ + while ((**this != '\0') && (**this != '*')) + { + ++(*this); + } + // Eat the * + ++(*this); + } while ((**this != '\0') && (**this != '/')); + // Eat the / + ++(*this); + } + // Parse // comments + if (((*this)[0] == '/') && ((*this)[1] == '/')) + { + // eat the start of the comment + ++(*this); + ++(*this); + // Find the ending * of */ + while (**this != '\n') + { + ++(*this); + } + // Eat the \n + ++(*this); + } + } while (start != cursor); + return *this; + } + /** + * Prints a message indicating the location of a parse error. + */ + void parse_error(const char *msg) + { + int line_count = 1; + int line_start = 0; + int line_end = cursor; + for (int i=cursor ; i>0 ; --i) + { + if (buffer[i] == '\n') + { + line_count++; + if (line_start == 0) + { + line_start = i+1; + } + } + } + for (int i=cursor+1 ; i<size ; ++i) + { + if (buffer[i] == '\n') + { + line_end = i; + break; + } + } + fprintf(stderr, "Error on line %d: %s\n", line_count, msg); + fwrite(&buffer[line_start], line_end-line_start, 1, stderr); + putc('\n', stderr); + for (int i=0 ; i<(cursor-line_start) ; ++i) + { + putc(' ', stderr); + } + putc('^', stderr); + putc('\n', stderr); + } + /** + * Dumps the current cursor value and the unconsumed values in the + * input buffer to the standard error. This method is intended solely + * for debugging. + */ + void dump() + { + fprintf(stderr, "Current cursor: %d\n", cursor); + fwrite(&buffer[cursor], size-cursor, 1, stderr); + } +}; +/** + * Explicit specialisation for reading a single byte. + */ +template<> +bool input_buffer::consume_binary(uint8_t &out) +{ + if (size < cursor + 1) + { + return false; + } + out = buffer[cursor++]; + return true; +} + +/** + * Subclass of input_buffer that mmap()s a file and owns the resulting memory. + * When this object is destroyed, the memory is unmapped. + */ +struct mmap_input_buffer : public input_buffer +{ + /** + * Constructs a new buffer from the file passed in as a file + * descriptor. + */ + mmap_input_buffer(int fd) : input_buffer(0, 0) + { + struct stat sb; + if (fstat(fd, &sb)) + { + perror("Failed to stat file"); + } + size = sb.st_size; + buffer = (const char*)mmap(0, size, PROT_READ, + MAP_PREFAULT_READ, fd, 0); + if (buffer == 0) + { + perror("Failed to mmap file"); + } + } + /** + * Unmaps the buffer, if one exists. + */ + virtual ~mmap_input_buffer() + { + if (buffer != 0) + { + munmap((void*)buffer, size); + } + } +}; +/** + * Input buffer read from standard input. This is used for reading device tree + * blobs and source from standard input. It reads the entire input into + * malloc'd memory, so will be very slow for large inputs. DTS and DTB files + * are very rarely more than 10KB though, so this is probably not a problem. + */ +struct stream_input_buffer : public input_buffer +{ + /** + * The buffer that will store the data read from the standard input. + */ + std::vector<char> b; + /** + * Constructs a new buffer from the file passed in as a file + * descriptor. + */ + stream_input_buffer() : input_buffer(0, 0) + { + int c; + while ((c = fgetc(stdin)) != EOF) + { + b.push_back(c); + } + buffer = b.data(); + size = b.size(); + } +}; + + + +/** + * String, referring to a place in the input file. We don't bother copying + * strings until we write them to the final output. These strings should be + * two words long: a start and a length. They are intended to be cheap to copy + * and store in collections. Copying the string object does not copy the + * underlying storage. + * + * Strings are not nul-terminated. + */ +class string +{ + /** + * The source files are ASCII, so we provide a non-locale-aware version of + * isalpha. This is a class so that it can be used with a template + * function for parsing strings. + */ + struct is_alpha + { + static inline bool check(const char c) + { + return ((c >= 'a') && (c <= 'z')) || ((c >= 'A') && + (c <= 'Z')); + } + }; + /** + * Check whether a character is in the set allowed for node names. + * This is a class so that it can be used with a template function for + * parsing strings. + */ + struct is_node_name_character + { + static inline bool check(const char c) + { + switch(c) + { + default: + return false; + case 'a'...'z': case 'A'...'Z': case '0'...'9': + case ',': case '.': case '+': case '-': + case '_': + return true; + } + } + }; + /** + * Check whether a character is in the set allowed for property names. + * This is a class so that it can be used with a template function for + * parsing strings. + */ + struct is_property_name_character + { + static inline bool check(const char c) + { + switch(c) + { + default: + return false; + case 'a'...'z': case 'A'...'Z': case '0'...'9': + case ',': case '.': case '+': case '-': + case '_': case '#': + return true; + } + } + }; + /** Start address. Contained within the mmap()'d input file and not + * owned by this object. */ + const char *start; + /** length of the string. DTS strings are allowed to contain nuls */ + int length; + /** Generic function for parsing strings matching the character set + * defined by the template argument. */ + template<class T> + static string parse(input_buffer &s) + { + const char *start = s; + int l=0; + while (T::check(*s)) { l++; ++s; } + return string(start, l); + } + public: + /** + * Constructs a string referring into another buffer. + */ + string(const char *s, int l) : start(s), length(l) {} + /** Constructs a string from a C string. */ + string(const char *s) : start(s), length(strlen(s)) {} + /** Default constructor, returns an empty string. */ + string() : start(0), length(0) {} + /** Construct a from an input buffer, ending with a nul terminator. */ + string(input_buffer &s) : start((const char*)s), length(0) + { + while(s[length] != '\0') + { + length++; + } + } + /** + * Returns the longest string in the input buffer starting at the + * current cursor and composed entirely of characters that are valid in + * node names. + */ + static string parse_node_name(input_buffer &s) + { + return parse<is_node_name_character>(s); + } + /** + * Returns the longest string in the input buffer starting at the + * current cursor and composed entirely of characters that are valid in + * property names. + */ + static string parse_property_name(input_buffer &s) + { + return parse<is_property_name_character>(s); + } + /** + * Parses either a node or a property name. If is_property is true on + * entry, then only property names are parsed. If it is false, then it + * will be set, on return, to indicate whether the parsed name is only + * valid as a property. + */ + static string parse_node_or_property_name(input_buffer &s, + bool &is_property) + { + if (is_property) + { + return parse_property_name(s); + } + const char *start = s; + int l=0; + while (is_node_name_character::check(*s)) + { + l++; + ++s; + } + while (is_property_name_character::check(*s)) + { + l++; + ++s; + is_property = true; + } + return string(start, l); + } + /** + * Compares two strings for equality. Strings are equal if they refer + * to identical byte sequences. + */ + bool operator==(const string& other) const + { + return (length == other.length) && + (memcmp(start, other.start, length) == 0); + } + /** + * Compares a string against a C string. The trailing nul in the C + * string is ignored for the purpose of comparison, so this will always + * fail if the string contains nul bytes. + */ + bool operator==(const char *other) const + { + return strncmp(other, start, length) == 0; + } + /** + * Inequality operator, defined as the inverse of the equality + * operator. + */ + template <typename T> + bool operator!=(T other) + { + return !(*this == other); + } + /** + * Comparison operator, defined to allow strings to be used as keys in + * maps. + */ + bool operator<(const string& other) const + { + if (length < other.length) { return true; } + if (length > other.length) { return false; } + return memcmp(start, other.start, length) < 0; + } + /** + * Returns true if this is the empty string, false otherwise. + */ + bool empty() const + { + return length == 0; + } + /** + * Returns the size of the string, in bytes. + */ + size_t size() { return length; } + /** + * Writes the string to the specified buffer. + */ + void push_to_buffer(byte_buffer &buffer, bool escapes=false) + { + for (int i=0 ; i<length ; ++i) + { + uint8_t c = start[i]; + if (escapes && c == '\\' && i+1 < length) + { + c = start[++i]; + switch (c) + { + // For now, we just ignore invalid escape sequences. + default: + case '"': + case '\'': + case '\\': + break; + case 'a': + c = '\a'; + break; + case 'b': + c = '\b'; + break; + case 't': + c = '\t'; + break; + case 'n': + c = '\n'; + break; + case 'v': + c = '\v'; + break; + case 'f': + c = '\f'; + break; + case 'r': + c = '\r'; + break; + case '0'...'7': + { + int v = digittoint(c); + if (i+1 < length && start[i+1] <= '7' && start[i+1] >= '0') + { + v <<= 3; + v |= digittoint(start[i+1]); + i++; + if (i+1 < length && start[i+1] <= '7' && start[i+1] >= '0') + { + v <<= 3; + v |= digittoint(start[i+1]); + } + } + c = (uint8_t)v; + break; + } + case 'x': + { + ++i; + if (i >= length) + { + break; + } + int v = digittoint(start[i]); + if (i+1 < length && ishexdigit(start[i+1])) + { + v <<= 4; + v |= digittoint(start[++i]); + } + c = (uint8_t)v; + break; + } + } + } + buffer.push_back(c); + } + } + /** + * Prints the string to the specified output stream. + */ + void print(FILE *file) + { + fwrite(start, length, 1, file); + } + /** + * Dumps the string to the standard error stream. Intended to be used + * for debugging. + */ + void dump() + { + print(stderr); + } +}; + + + +/** + * The dtb namespace contains code related to the generation of device tree + * blobs, the binary representation of flattened device trees. The abstract + * tree representation calls into this code to generate the output. + */ +namespace dtb +{ +/** The token types in the DTB, as defined by ยง7.4.1 of the ePAPR + * specification. All of these values are written in big-endian format in the + * output. + */ +enum token_type +{ + /** + * Marker indicating the start of a node in the tree. This is followed + * by the nul-terminated name. If a unit address is specified, then + * the name also contains the address, with an @ symbol between the end + * of the name and the start of the address. + * + * The name is then padded such that the next token begins on a 4-byte + * boundary. The node may contain properties, other nodes, both, or be + * empty. + */ + FDT_BEGIN_NODE = 0x00000001, + /** + * Marker indicating the end of a node. + */ + FDT_END_NODE = 0x00000002, + /** + * The start of a property. This is followed by two 32-bit big-endian + * values. The first indicates the length of the property value, the + * second its index in the strings table. It is then followed by the + * property value, if the value is of non-zero length. + */ + FDT_PROP = 0x00000003, + /** + * Ignored token. May be used for padding inside DTB nodes. + */ + FDT_NOP = 0x00000004, + /** + * Marker indicating the end of the tree. + */ + FDT_END = 0x00000009 +}; + +/** + * Returns the token as a string. This is used for debugging and for printing + * human-friendly error messages about malformed DTB input. + */ +const char *token_type_name(token_type t) +{ + switch(t) + { + case FDT_BEGIN_NODE: + return "FDT_BEGIN_NODE"; + case FDT_END_NODE: + return "FDT_END_NODE"; + case FDT_PROP: + return "FDT_PROP"; + case FDT_NOP: + return "FDT_NOP"; + case FDT_END: + return "FDT_END"; + } + assert(0); +} + +/** + * Abstract class for writing a section of the output. We create one + * of these for each section that needs to be written. It is intended to build + * a temporary buffer of the output in memory and then write it to a file + * stream. The size can be returned after all of the data has been written + * into the internal buffer, so the sizes of the three tables can be calculated + * before storing them in the buffer. + */ +struct output_writer +{ + /** + * Writes a label into the output stream. This is only applicable for + * assembly output, where the labels become symbols that can be + * resolved at link time. + */ + virtual void write_label(string name) = 0; + /** + * Writes a comment into the output stream. Useful only when debugging + * the output. + */ + virtual void write_comment(string name) = 0; + /** + * Writes a string. A nul terminator is implicitly added. + */ + virtual void write_string(string name) = 0; + /** + * Writes a single 8-bit value. + */ + virtual void write_data(uint8_t) = 0; + /** + * Writes a single 32-bit value. The value is written in big-endian + * format, but should be passed in the host's native endian. + */ + virtual void write_data(uint32_t) = 0; + /** + * Writes a single 64-bit value. The value is written in big-endian + * format, but should be passed in the host's native endian. + */ + virtual void write_data(uint64_t) = 0; + /** + * Writes the collected output to the specified file descriptor. + */ + virtual void write_to_file(int fd) = 0; + /** + * Returns the number of bytes. + */ + virtual uint32_t size() = 0; + /** + * Helper for writing tokens to the output stream. This writes a + * comment above the token describing its value, for easier debugging + * of the output. + */ + void write_token(token_type t) + { + write_comment(token_type_name(t)); + write_data((uint32_t)t); + } + /** + * Helper function that writes a byte buffer to the output, one byte at + * a time. + */ + void write_data(byte_buffer b) + { + for (byte_buffer::iterator i=b.begin(), e=b.end(); i!=e ; i++) + { + write_data(*i); + } + } +}; + +/** + * Binary file writer. This class is responsible for writing the DTB output + * directly in blob format. + */ +class binary_writer : public output_writer +{ + /** + * The internal buffer used to store the blob while it is being + * constructed. + */ + byte_buffer buffer; + public: + /** + * The binary format does not support labels, so this method + * does nothing. + */ + virtual void write_label(string name) {} + /** + * Comments are ignored by the binary writer. *** DIFF OUTPUT TRUNCATED AT 1000 LINES ***
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201405241633.s4OGXRbW067748>