usr.bin/dtc/fdt.cc

   1 /*-
   2  * Copyright (c) 2013 David Chisnall
   3  * All rights reserved.
   4  *
   5  * This software was developed by SRI International and the University of
   6  * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
   7  * ("CTSRD"), as part of the DARPA CRASH research programme.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  19  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  22  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  23  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  24  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  25  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  26  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  27  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  28  * SUCH DAMAGE.
  29  *
  30  * $FreeBSD$
  31  */
  32
  33 #define __STDC_LIMIT_MACROS 1
  34
  35 #include "fdt.hh"
  36
  37 #include <algorithm>
  38 #include <ctype.h>
  39 #include <fcntl.h>
  40 #include <inttypes.h>
  41 #include <libgen.h>
  42 #include <stdio.h>
  43 #include <stdlib.h>
  44 #include <unistd.h>
  45 #include <sys/types.h>
  46 #include <sys/stat.h>
  47 #include "dtb.hh"
  48
  49 namespace dtc
  50 {
  51
  52 namespace fdt
  53 {
  54
  55 uint32_t
  56 property_value::get_as_uint32()
  57 {
  58         if (byte_data.size() != 4)
  59         {
  60                 return 0;
  61         }
  62         uint32_t v = 0;
  63         v &= byte_data[0] << 24;
  64         v &= byte_data[1] << 16;
  65         v &= byte_data[2] << 8;
  66         v &= byte_data[3] << 0;
  67         return v;
  68 }
  69
  70 void
  71 property_value::push_to_buffer(byte_buffer &buffer)
  72 {
  73         if (!byte_data.empty())
  74         {
  75                 buffer.insert(buffer.end(), byte_data.begin(), byte_data.end());
  76         }
  77         else
  78         {
  79                 string_data.push_to_buffer(buffer, true);
  80                 // Trailing nul
  81                 buffer.push_back(0);
  82         }
  83 }
  84
  85 void
  86 property_value::write_dts(FILE *file)
  87 {
  88         resolve_type();
  89         switch (type)
  90         {
  91                 default:
  92                         assert(0 && "Invalid type");
  93                 case STRING:
  94                 case STRING_LIST:
  95                 case CROSS_REFERENCE:
  96                         write_as_string(file);
  97                         break;
  98                 case PHANDLE:
  99                         write_as_cells(file);
 100                         break;
 101                 case BINARY:
 102                         if (byte_data.size() % 4 == 0)
 103                         {
 104                                 write_as_cells(file);
 105                                 break;
 106                         }
 107                         write_as_bytes(file);
 108                         break;
 109         }
 110 }
 111
 112 void
 113 property_value::resolve_type()
 114 {
 115         if (type != UNKNOWN)
 116         {
 117                 return;
 118         }
 119         if (byte_data.empty())
 120         {
 121                 type = STRING;
 122                 return;
 123         }
 124         if (byte_data.back() == 0)
 125         {
 126                 bool is_all_printable = true;
 127                 int nuls = 0;
 128                 int bytes = 0;
 129                 for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end()-1; i<e ; i++)
 130                 {
 131                         bytes++;
 132                         is_all_printable &= (*i == '\0') || isprint(*i);
 133                         if (*i == '\0')
 134                         {
 135                                 nuls++;
 136                         }
 137                         if (!is_all_printable)
 138                         {
 139                                 break;
 140                         }
 141                 }
 142                 if ((is_all_printable && (bytes > nuls)) || bytes == 0)
 143                 {
 144                         type = STRING;
 145                         if (nuls > 0)
 146                         {
 147                                 type = STRING_LIST;
 148                         }
 149                         return;
 150                 }
 151         }
 152         type = BINARY;
 153 }
 154
 155 void
 156 property_value::write_as_string(FILE *file)
 157 {
 158         putc('"', file);
 159         if (byte_data.empty())
 160         {
 161                 string_data.print(file);
 162         }
 163         else
 164         {
 165                 for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end()-1; i!=e ; ++i)
 166                 {
 167                         // FIXME Escape tabs, newlines, and so on.
 168                         if (*i == '\0')
 169                         {
 170                                 fputs("\", \"", file);
 171                                 continue;
 172                         }
 173                         putc(*i, file);
 174                 }
 175         }
 176         putc('"', file);
 177 }
 178
 179 void
 180 property_value::write_as_cells(FILE *file)
 181 {
 182         putc('<', file);
 183         assert((byte_data.size() % 4) == 0);
 184         for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end(); i!=e ; ++i)
 185         {
 186                 uint32_t v = 0;
 187                 v = (v << 8) | *i;
 188                 ++i;
 189                 v = (v << 8) | *i;
 190                 ++i;
 191                 v = (v << 8) | *i;
 192                 ++i;
 193                 v = (v << 8) | *i;
 194                 fprintf(file, "0x%" PRIx32, v);
 195                 if (i+1 != e)
 196                 {
 197                         putc(' ', file);
 198                 }
 199         }
 200         putc('>', file);
 201 }
 202
 203 void
 204 property_value::write_as_bytes(FILE *file)
 205 {
 206         putc('[', file);
 207         for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end(); i!=e ; i++)
 208         {
 209                 fprintf(file, "%02hhx", *i);
 210                 if (i+1 != e)
 211                 {
 212                         putc(' ', file);
 213                 }
 214         }
 215         putc(']', file);
 216 }
 217
 218 void
 219 property::parse_string(input_buffer &input)
 220 {
 221         property_value v;
 222         assert(input[0] == '"');
 223         ++input;
 224         const char *start = (const char*)input;
 225         int length = 0;
 226         while (char c = input[0])
 227         {
 228                 if (c == '"' && input[-1] != '\\')
 229                 {
 230                         input.consume('"');
 231                         break;
 232                 }
 233                 ++input;
 234                 ++length;
 235         }
 236         v.string_data = string(start, length);
 237         values.push_back(v);
 238 }
 239
 240 void
 241 property::parse_cells(input_buffer &input)
 242 {
 243         assert(input[0] == '<');
 244         ++input;
 245         property_value v;
 246         input.next_token();
 247         while (!input.consume('>'))
 248         {
 249                 input.next_token();
 250                 // If this is a phandle then we need to get the name of the
 251                 // referenced node
 252                 if (input.consume('&'))
 253                 {
 254                         input.next_token();
 255                         // FIXME: We should support full paths here, but we
 256                         // don't.
 257                         string referenced = string::parse_node_name(input);
 258                         if (referenced.empty())
 259                         {
 260                                 input.parse_error("Expected node name");
 261                                 valid = false;
 262                                 return;
 263                         }
 264                         input.next_token();
 265                         // If we already have some bytes, make the phandle a
 266                         // separate component.
 267                         if (!v.byte_data.empty())
 268                         {
 269                                 values.push_back(v);
 270                                 v = property_value();
 271                         }
 272                         v.string_data = referenced;
 273                         v.type = property_value::PHANDLE;
 274                         values.push_back(v);
 275                         v = property_value();
 276                 }
 277                 else
 278                 {
 279                         //FIXME: We should support labels in the middle
 280                         //of these, but we don't.
 281                         long long val;
 282                         if (!input.consume_integer(val))
 283                         {
 284                                 input.parse_error("Expected numbers in array of cells");
 285                                 valid = false;
 286                                 return;
 287                         }
 288                         if ((val < 0) || (val > UINT32_MAX))
 289                         {
 290                                 input.parse_error("Value out of range");
 291                                 valid = false;
 292                                 return;
 293                         }
 294                         push_big_endian(v.byte_data, (uint32_t)val);
 295                         input.next_token();
 296                 }
 297         }
 298         // Don't store an empty string value here.
 299         if (v.byte_data.size() > 0)
 300         {
 301                 values.push_back(v);
 302         }
 303 }
 304
 305 void
 306 property::parse_bytes(input_buffer &input)
 307 {
 308         assert(input[0] == '[');
 309         ++input;
 310         property_value v;
 311         input.next_token();
 312         while (!input.consume(']'))
 313         {
 314                 {
 315                         //FIXME: We should support
 316                         //labels in the middle of
 317                         //these, but we don't.
 318                         uint8_t val;
 319                         if (!input.consume_hex_byte(val))
 320                         {
 321                                 input.parse_error("Expected hex bytes in array of bytes");
 322                                 valid = false;
 323                                 return;
 324                         }
 325                         v.byte_data.push_back(val);
 326                         input.next_token();
 327                 }
 328         }
 329         values.push_back(v);
 330 }
 331
 332 void
 333 property::parse_reference(input_buffer &input)
 334 {
 335         assert(input[0] == '&');
 336         ++input;
 337         input.next_token();
 338         property_value v;
 339         v.string_data = string::parse_node_name(input);
 340         if (v.string_data.empty())
 341         {
 342                 input.parse_error("Expected node name");
 343                 valid = false;
 344                 return;
 345         }
 346         v.type = property_value::CROSS_REFERENCE;
 347         values.push_back(v);
 348 }
 349
 350 property::property(input_buffer &structs, input_buffer &strings)
 351 {
 352         uint32_t name_offset;
 353         uint32_t length;
 354         valid = structs.consume_binary(length) &&
 355                 structs.consume_binary(name_offset);
 356         if (!valid)
 357         {
 358                 fprintf(stderr, "Failed to read property\n");
 359                 return;
 360         }
 361         // Find the name
 362         input_buffer name_buffer = strings.buffer_from_offset(name_offset);
 363         if (name_buffer.empty())
 364         {
 365                 fprintf(stderr, "Property name offset %" PRIu32
 366                         " is past the end of the strings table\n",
 367                         name_offset);
 368                 valid = false;
 369                 return;
 370         }
 371         key = string(name_buffer);
 372
 373         // If we're empty, do not push anything as value.
 374         if (!length)
 375                 return;
 376
 377         // Read the value
 378         uint8_t byte;
 379         property_value v;
 380         for (uint32_t i=0 ; i<length ; i++)
 381         {
 382                 if (!(valid = structs.consume_binary(byte)))
 383                 {
 384                         fprintf(stderr, "Failed to read property value\n");
 385                         return;
 386                 }
 387                 v.byte_data.push_back(byte);
 388         }
 389         values.push_back(v);
 390 }
 391
 392 void property::parse_define(input_buffer &input, define_map *defines)
 393 {
 394         input.consume('$');
 395         if (!defines)
 396         {
 397                 input.parse_error("No predefined properties to match name\n");
 398                 valid = false;
 399                 return;
 400         }
 401         string name = string::parse_property_name(input);
 402         define_map::iterator found;
 403         if ((name == string()) ||
 404             ((found = defines->find(name)) == defines->end()))
 405         {
 406                 input.parse_error("Undefined property name\n");
 407                 valid = false;
 408                 return;
 409         }
 410         values.push_back((*found).second->values[0]);
 411 }
 412
 413 property::property(input_buffer &input,
 414                    string k,
 415                    string l,
 416                    bool semicolonTerminated,
 417                    define_map *defines) : key(k), label(l), valid(true)
 418 {
 419         do {
 420                 input.next_token();
 421                 switch (input[0])
 422                 {
 423                         case '$':
 424                         {
 425                                 parse_define(input, defines);
 426                                 if (valid)
 427                                 {
 428                                         break;
 429                                 }
 430                         }
 431                         default:
 432                                 input.parse_error("Invalid property value.");
 433                                 valid = false;
 434                                 return;
 435                         case '"':
 436                                 parse_string(input);
 437                                 break;
 438                         case '<':
 439                                 parse_cells(input);
 440                                 break;
 441                         case '[':
 442                                 parse_bytes(input);
 443                                 break;
 444                         case '&':
 445                                 parse_reference(input);
 446                                 break;
 447                         case ';':
 448                         {
 449                                 break;
 450                         }
 451                 }
 452                 input.next_token();
 453         } while (input.consume(','));
 454         if (semicolonTerminated && !input.consume(';'))
 455         {
 456                 input.parse_error("Expected ; at end of property");
 457                 valid = false;
 458         }
 459 }
 460
 461 property*
 462 property::parse_dtb(input_buffer &structs, input_buffer &strings)
 463 {
 464         property *p = new property(structs, strings);
 465         if (!p->valid)
 466         {
 467                 delete p;
 468                 p = 0;
 469         }
 470         return p;
 471 }
 472
 473 property*
 474 property::parse(input_buffer &input, string key, string label,
 475                 bool semicolonTerminated, define_map *defines)
 476 {
 477         property *p = new property(input, key, label, semicolonTerminated, defines);
 478         if (!p->valid)
 479         {
 480                 delete p;
 481                 p = 0;
 482         }
 483         return p;
 484 }
 485
 486 void
 487 property::write(dtb::output_writer &writer, dtb::string_table &strings)
 488 {
 489         writer.write_token(dtb::FDT_PROP);
 490         byte_buffer value_buffer;
 491         for (value_iterator i=begin(), e=end() ; i!=e ; ++i)
 492         {
 493                 i->push_to_buffer(value_buffer);
 494         }
 495         writer.write_data((uint32_t)value_buffer.size());
 496         writer.write_comment(key);
 497         writer.write_data(strings.add_string(key));
 498         writer.write_data(value_buffer);
 499 }
 500
 501 void
 502 property::write_dts(FILE *file, int indent)
 503 {
 504         for (int i=0 ; i<indent ; i++)
 505         {
 506                 putc('\t', file);
 507         }
 508         if (label != string())
 509         {
 510                 label.print(file);
 511                 fputs(": ", file);
 512         }
 513         if (key != string())
 514         {
 515                 key.print(file);
 516         }
 517         if (!values.empty())
 518         {
 519                 fputs(" = ", file);
 520                 for (value_iterator i=begin(), e=end() ; i!=e ; ++i)
 521                 {
 522                         i->write_dts(file);
 523                         if (i+1 != e)
 524                         {
 525                                 putc(',', file);
 526                                 putc(' ', file);
 527                         }
 528                 }
 529         }
 530         fputs(";\n", file);
 531 }
 532
 533 string
 534 node::parse_name(input_buffer &input, bool &is_property, const char *error)
 535 {
 536         if (!valid)
 537         {
 538                 return string();
 539         }
 540         input.next_token();
 541         if (is_property)
 542         {
 543                 return string::parse_property_name(input);
 544         }
 545         string n = string::parse_node_or_property_name(input, is_property);
 546         if (n.empty())
 547         {
 548                 if (n.empty())
 549                 {
 550                         input.parse_error(error);
 551                         valid = false;
 552                 }
 553         }
 554         return n;
 555 }
 556
 557 node::node(input_buffer &structs, input_buffer &strings) : valid(true)
 558 {
 559         const char *name_start = (const char*)structs;
 560         int name_length = 0;
 561         while (structs[0] != '\0' && structs[0] != '@')
 562         {
 563                 name_length++;
 564                 ++structs;
 565         }
 566         name = string(name_start, name_length);
 567         if (structs[0] == '@')
 568         {
 569                 ++structs;
 570                 name_start = (const char*)structs;
 571                 name_length = 0;
 572                 while (structs[0] != '\0')
 573                 {
 574                         name_length++;
 575                         ++structs;
 576                 }
 577                 unit_address = string(name_start, name_length);
 578         }
 579         ++structs;
 580         uint32_t token;
 581         while (structs.consume_binary(token))
 582         {
 583                 switch (token)
 584                 {
 585                         default:
 586                                 fprintf(stderr, "Unexpected token 0x%" PRIx32
 587                                         " while parsing node.\n", token);
 588                                 valid = false;
 589                                 return;
 590                         // Child node, parse it.
 591                         case dtb::FDT_BEGIN_NODE:
 592                         {
 593                                 node *child = node::parse_dtb(structs, strings);
 594                                 if (child == 0)
 595                                 {
 596                                         valid = false;
 597                                         return;
 598                                 }
 599                                 children.push_back(child);
 600                                 break;
 601                         }
 602                         // End of this node, no errors.
 603                         case dtb::FDT_END_NODE:
 604                                 return;
 605                         // Property, parse it.
 606                         case dtb::FDT_PROP:
 607                         {
 608                                 property *prop = property::parse_dtb(structs, strings);
 609                                 if (prop == 0)
 610                                 {
 611                                         valid = false;
 612                                         return;
 613                                 }
 614                                 properties.push_back(prop);
 615                                 break;
 616                         }
 617                                 break;
 618                         // End of structs table.  Should appear after
 619                         // the end of the last node.
 620                         case dtb::FDT_END:
 621                                 fprintf(stderr, "Unexpected FDT_END token while parsing node.\n");
 622                                 valid = false;
 623                                 return;
 624                         // NOPs are padding.  Ignore them.
 625                         case dtb::FDT_NOP:
 626                                 break;
 627                 }
 628         }
 629         fprintf(stderr, "Failed to read token from structs table while parsing node.\n");
 630         valid = false;
 631         return;
 632 }
 633
 634 node::node(input_buffer &input, string n, string l, string a, define_map *defines) :
 635         label(l), name(n), unit_address(a), valid(true)
 636 {
 637         if (!input.consume('{'))
 638         {
 639                 input.parse_error("Expected { to start new device tree node.\n");
 640         }
 641         input.next_token();
 642         while (valid && !input.consume('}'))
 643         {
 644                 // flag set if we find any characters that are only in
 645                 // the property name character set, not the node
 646                 bool is_property = false;
 647                 string child_name, child_label, child_address;
 648                 child_name = parse_name(input, is_property,
 649                                 "Expected property or node name");
 650                 if (input.consume(':'))
 651                 {
 652                         // Node labels can contain any characters?  The
 653                         // spec doesn't say, so we guess so...
 654                         is_property = false;
 655                         child_label = child_name;
 656                         child_name = parse_name(input, is_property, "Expected property or node name");
 657                 }
 658                 if (input.consume('@'))
 659                 {
 660                         child_address = parse_name(input, is_property, "Expected unit address");
 661                 }
 662                 if (!valid)
 663                 {
 664                         return;
 665                 }
 666                 input.next_token();
 667                 // If we're parsing a property, then we must actually do that.
 668                 if (input.consume('='))
 669                 {
 670                         property *p= property::parse(input, child_name,
 671                                         child_label, true, defines);
 672                         if (p == 0)
 673                         {
 674                                 valid = false;
 675                         }
 676                         else
 677                         {
 678                                 properties.push_back(p);
 679                         }
 680                 }
 681                 else if (!is_property && input[0] == ('{'))
 682                 {
 683                         node *child = node::parse(input, child_name,
 684                                         child_label, child_address, defines);
 685                         if (child)
 686                         {
 687                                 children.push_back(child);
 688                         }
 689                         else
 690                         {
 691                                 valid = false;
 692                         }
 693                 }
 694                 else if (input.consume(';'))
 695                 {
 696                         properties.push_back(new property(child_name, child_label));
 697                 }
 698                 else
 699                 {
 700                         input.parse_error("Error parsing property.");
 701                         valid = false;
 702                 }
 703                 input.next_token();
 704         }
 705         input.consume(';');
 706 }
 707
 708 bool
 709 node::cmp_properties(property *p1, property *p2)
 710 {
 711         return p1->get_key() < p2->get_key();
 712 }
 713
 714 bool
 715 node::cmp_children(node *c1, node *c2)
 716 {
 717         if (c1->name == c2->name)
 718         {
 719                 return c1->unit_address < c2->unit_address;
 720         }
 721         return c1->name < c2->name;
 722 }
 723
 724 void
 725 node::sort()
 726 {
 727         std::sort(property_begin(), property_end(), cmp_properties);
 728         std::sort(child_begin(), child_end(), cmp_children);
 729         for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
 730         {
 731                 (*i)->sort();
 732         }
 733 }
 734
 735 node*
 736 node::parse(input_buffer &input,
 737             string name,
 738             string label,
 739             string address,
 740             define_map *defines)
 741 {
 742         node *n = new node(input, name, label, address, defines);
 743         if (!n->valid)
 744         {
 745                 delete n;
 746                 n = 0;
 747         }
 748         return n;
 749 }
 750
 751 node*
 752 node::parse_dtb(input_buffer &structs, input_buffer &strings)
 753 {
 754         node *n = new node(structs, strings);
 755         if (!n->valid)
 756         {
 757                 delete n;
 758                 n = 0;
 759         }
 760         return n;
 761 }
 762
 763 node::~node()
 764 {
 765         while (!children.empty())
 766         {
 767                 delete children.back();
 768                 children.pop_back();
 769         }
 770         while (!properties.empty())
 771         {
 772                 delete properties.back();
 773                 properties.pop_back();
 774         }
 775 }
 776
 777 property*
 778 node::get_property(string key)
 779 {
 780         for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
 781         {
 782                 if ((*i)->get_key() == key)
 783                 {
 784                         return *i;
 785                 }
 786         }
 787         return 0;
 788 }
 789
 790 void
 791 node::merge_node(node *other)
 792 {
 793         if (!other->label.empty())
 794         {
 795                 label = other->label;
 796         }
 797         // Note: this is an O(n*m) operation.  It might be sensible to
 798         // optimise this if we find that there are nodes with very
 799         // large numbers of properties, but for typical usage the
 800         // entire vector will fit (easily) into cache, so iterating
 801         // over it repeatedly isn't that expensive.
 802         while (!other->properties.empty())
 803         {
 804                 property *p = other->properties.front();
 805                 for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
 806                 {
 807                         if ((*i)->get_key() == p->get_key())
 808                         {
 809                                 delete *i;
 810                                 properties.erase(i);
 811                                 break;
 812                         }
 813                 }
 814                 add_property(p);
 815                 other->properties.erase(other->properties.begin());
 816         }
 817         while (!other->children.empty())
 818         {
 819                 node *c = other->children.front();
 820                 bool found = false;
 821                 for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
 822                 {
 823                         if ((*i)->name == c->name && (*i)->unit_address == c->unit_address)
 824                         {
 825                                 (*i)->merge_node(c);
 826                                 delete c;
 827                                 found = true;
 828                                 break;
 829                         }
 830                 }
 831                 if (!found)
 832                 {
 833                         children.push_back(c);
 834                 }
 835                 other->children.erase(other->children.begin());
 836         }
 837 }
 838
 839 void
 840 node::write(dtb::output_writer &writer, dtb::string_table &strings)
 841 {
 842         writer.write_token(dtb::FDT_BEGIN_NODE);
 843         byte_buffer name_buffer;
 844         name.push_to_buffer(name_buffer);
 845         if (unit_address != string())
 846         {
 847                 name_buffer.push_back('@');
 848                 unit_address.push_to_buffer(name_buffer);
 849         }
 850         writer.write_comment(name);
 851         writer.write_data(name_buffer);
 852         writer.write_data((uint8_t)0);
 853         for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
 854         {
 855                 (*i)->write(writer, strings);
 856         }
 857         for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
 858         {
 859                 (*i)->write(writer, strings);
 860         }
 861         writer.write_token(dtb::FDT_END_NODE);
 862 }
 863
 864 void
 865 node::write_dts(FILE *file, int indent)
 866 {
 867         for (int i=0 ; i<indent ; i++)
 868         {
 869                 putc('\t', file);
 870         }
 871         if (label != string())
 872         {
 873                 label.print(file);
 874                 fputs(": ", file);
 875         }
 876         if (name != string())
 877         {
 878                 name.print(file);
 879         }
 880         if (unit_address != string())
 881         {
 882                 putc('@', file);
 883                 unit_address.print(file);
 884         }
 885         fputs(" {\n\n", file);
 886         for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
 887         {
 888                 (*i)->write_dts(file, indent+1);
 889         }
 890         for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
 891         {
 892                 (*i)->write_dts(file, indent+1);
 893         }
 894         for (int i=0 ; i<indent ; i++)
 895         {
 896                 putc('\t', file);
 897         }
 898         fputs("};\n", file);
 899 }
 900
 901 void
 902 device_tree::collect_names_recursive(node* n, node_path &path)
 903 {
 904         string name = n->label;
 905         path.push_back(std::make_pair(n->name, n->unit_address));
 906         if (name != string())
 907         {
 908                 if (node_names.find(name) == node_names.end())
 909                 {
 910                         node_names.insert(std::make_pair(name, n));
 911                         node_paths.insert(std::make_pair(name, path));
 912                 }
 913                 else
 914                 {
 915                         node_names[name] = (node*)-1;
 916                         std::map<string, node_path>::iterator i = node_paths.find(name);
 917                         if (i != node_paths.end())
 918                         {
 919                                 node_paths.erase(name);
 920                         }
 921                         fprintf(stderr, "Label not unique: ");
 922                         name.dump();
 923                         fprintf(stderr, ".  References to this label will not be resolved.");
 924                 }
 925         }
 926         for (node::child_iterator i=n->child_begin(), e=n->child_end() ; i!=e ; ++i)
 927         {
 928                 collect_names_recursive(*i, path);
 929         }
 930         path.pop_back();
 931         // Now we collect the phandles and properties that reference
 932         // other nodes.
 933         for (node::property_iterator i=n->property_begin(), e=n->property_end() ; i!=e ; ++i)
 934         {
 935                 for (property::value_iterator p=(*i)->begin(),pe=(*i)->end() ; p!=pe ; ++p)
 936                 {
 937                         if (p->is_phandle())
 938                         {
 939                                 phandles.push_back(&*p);
 940                         }
 941                         if (p->is_cross_reference())
 942                         {
 943                                 cross_references.push_back(&*p);
 944                         }
 945                 }
 946                 if ((*i)->get_key() == string("phandle") ||
 947                     (*i)->get_key() == string("linux,phandle"))
 948                 {
 949                         if ((*i)->begin()->byte_data.size() != 4)
 950                         {
 951                                 fprintf(stderr, "Invalid phandle value for node ");
 952                                 n->name.dump();
 953                                 fprintf(stderr, ".  Should be a 4-byte value.\n");
 954                                 valid = false;
 955                         }
 956                         else
 957                         {
 958                                 uint32_t phandle = (*i)->begin()->get_as_uint32();
 959                                 used_phandles.insert(std::make_pair(phandle, n));
 960                         }
 961                 }
 962         }
 963 }
 964
 965 void
 966 device_tree::collect_names()
 967 {
 968         node_path p;
 969         collect_names_recursive(root, p);
 970 }
 971
 972 void
 973 device_tree::resolve_cross_references()
 974 {
 975         for (std::vector<property_value*>::iterator i=cross_references.begin(), e=cross_references.end() ; i!=e ; ++i)
 976         {
 977                 property_value* pv = *i;
 978                 node_path path = node_paths[pv->string_data];
 979                 // Skip the first name in the path.  It's always "", and implicitly /
 980                 for (node_path::iterator p=path.begin()+1, pe=path.end() ; p!=pe ; ++p)
 981                 {
 982                         pv->byte_data.push_back('/');
 983                         p->first.push_to_buffer(pv->byte_data);
 984                         if (!(p->second.empty()))
 985                         {
 986                                 pv->byte_data.push_back('@');
 987                                 p->second.push_to_buffer(pv->byte_data);
 988                         }
 989                 }
 990                 pv->byte_data.push_back(0);
 991         }
 992         uint32_t phandle = 1;
 993         for (std::vector<property_value*>::iterator i=phandles.begin(), e=phandles.end() ; i!=e ; ++i)
 994         {
 995                 string target_name = (*i)->string_data;
 996                 node *target = node_names[target_name];
 997                 if (target == 0)
 998                 {
 999                         fprintf(stderr, "Failed to find node with label:");
1000                         target_name.dump();
1001                         fprintf(stderr, "\n");
1002                         valid = 0;
1003                         return;
1004                 }
1005                 // If there is an existing phandle, use it
1006                 property *p = target->get_property("phandle");
1007                 if (p == 0)
1008                 {
1009                         p = target->get_property("linux,phandle");
1010                 }
1011                 if (p == 0)
1012                 {
1013                         // Otherwise insert a new phandle node
1014                         property_value v;
1015                         while (used_phandles.find(phandle) != used_phandles.end())
1016                         {
1017                                 // Note that we only don't need to
1018                                 // store this phandle in the set,
1019                                 // because we are monotonically
1020                                 // increasing the value of phandle and
1021                                 // so will only ever revisit this value
1022                                 // if we have used 2^32 phandles, at
1023                                 // which point our blob won't fit in
1024                                 // any 32-bit system and we've done
1025                                 // something badly wrong elsewhere
1026                                 // already.
1027                                 phandle++;
1028                         }
1029                         push_big_endian(v.byte_data, phandle++);
1030                         if (phandle_node_name == BOTH || phandle_node_name == LINUX)
1031                         {
1032                                 p = new property(string("linux,phandle"));
1033                                 p->add_value(v);
1034                                 target->add_property(p);
1035                         }
1036                         if (phandle_node_name == BOTH || phandle_node_name == EPAPR)
1037                         {
1038                                 p = new property(string("phandle"));
1039                                 p->add_value(v);
1040                                 target->add_property(p);
1041                         }
1042                 }
1043                 p->begin()->push_to_buffer((*i)->byte_data);
1044                 assert((*i)->byte_data.size() == 4);
1045         }
1046 }
1047
1048 void
1049 device_tree::parse_roots(input_buffer &input, std::vector<node*> &roots)
1050 {
1051         input.next_token();
1052         while (valid && input.consume('/'))
1053         {
1054                 input.next_token();
1055                 node *n = node::parse(input, string("", 1), string(), string(), &defines);
1056                 if (n)
1057                 {
1058                         roots.push_back(n);
1059                 }
1060                 else
1061                 {
1062                         valid = false;
1063                 }
1064                 input.next_token();
1065         }
1066 }
1067
1068 input_buffer*
1069 device_tree::buffer_for_file(const char *path)
1070 {
1071         if (string(path) == string("-"))
1072         {
1073                 input_buffer *b = new stream_input_buffer();
1074                 buffers.push_back(b);
1075                 return b;
1076         }
1077         int source = open(path, O_RDONLY);
1078         if (source == -1)
1079         {
1080                 fprintf(stderr, "Unable to open file %s\n", path);
1081                 return 0;
1082         }
1083         struct stat st;
1084         if (fstat(source, &st) == 0 && S_ISDIR(st.st_mode))
1085         {
1086                 fprintf(stderr, "File %s is a directory\n", path);
1087                 close(source);
1088                 return 0;
1089         }
1090         input_buffer *b = new mmap_input_buffer(source);
1091         // Keep the buffer that owns the memory around for the lifetime
1092         // of this FDT.  Ones simply referring to it may have shorter
1093         // lifetimes.
1094         buffers.push_back(b);
1095         close(source);
1096         return b;
1097 }
1098
1099 template<class writer> void
1100 device_tree::write(int fd)
1101 {
1102         dtb::string_table st;
1103         dtb::header head;
1104         writer head_writer;
1105         writer reservation_writer;
1106         writer struct_writer;
1107         writer strings_writer;
1108
1109         // Build the reservation table
1110         reservation_writer.write_comment(string("Memory reservations"));
1111         reservation_writer.write_label(string("dt_reserve_map"));
1112         for (std::vector<reservation>::iterator i=reservations.begin(),
1113              e=reservations.end() ; i!=e ; ++i)
1114         {
1115                 reservation_writer.write_comment(string("Reservation start"));
1116                 reservation_writer.write_data(i->first);
1117                 reservation_writer.write_comment(string("Reservation length"));
1118                 reservation_writer.write_data(i->first);
1119         }
1120         // Write n spare reserve map entries, plus the trailing 0.
1121         for (uint32_t i=0 ; i<=spare_reserve_map_entries ; i++)
1122         {
1123                 reservation_writer.write_data((uint64_t)0);
1124                 reservation_writer.write_data((uint64_t)0);
1125         }
1126
1127
1128         struct_writer.write_comment(string("Device tree"));
1129         struct_writer.write_label(string("dt_struct_start"));
1130         root->write(struct_writer, st);
1131         struct_writer.write_token(dtb::FDT_END);
1132         struct_writer.write_label(string("dt_struct_end"));
1133
1134         st.write(strings_writer);
1135         // Find the strings size before we stick padding on the end.
1136         // Note: We should possibly use a new writer for the padding.
1137         head.size_dt_strings = strings_writer.size();
1138
1139         // Stick the padding in the strings writer, but after the
1140         // marker indicating that it's the end.
1141         // Note: We probably should add a padding call to the writer so
1142         // that the asm back end can write padding directives instead
1143         // of a load of 0 bytes.
1144         for (uint32_t i=0 ; i<blob_padding ; i++)
1145         {
1146                 strings_writer.write_data((uint8_t)0);
1147         }
1148         head.totalsize = sizeof(head) + strings_writer.size() +
1149                 struct_writer.size() + reservation_writer.size();
1150         while (head.totalsize < minimum_blob_size)
1151         {
1152                 head.totalsize++;
1153                 strings_writer.write_data((uint8_t)0);
1154         }
1155         head.off_dt_struct = sizeof(head) + reservation_writer.size();;
1156         head.off_dt_strings = head.off_dt_struct + struct_writer.size();
1157         head.off_mem_rsvmap = sizeof(head);
1158         head.boot_cpuid_phys = boot_cpu;
1159         head.size_dt_struct = struct_writer.size();
1160         head.write(head_writer);
1161
1162         head_writer.write_to_file(fd);
1163         reservation_writer.write_to_file(fd);
1164         struct_writer.write_to_file(fd);
1165         strings_writer.write_label(string("dt_blob_end"));
1166         strings_writer.write_to_file(fd);
1167 }
1168
1169 node*
1170 device_tree::referenced_node(property_value &v)
1171 {
1172         if (v.is_phandle())
1173         {
1174                 return node_names[v.string_data];
1175         }
1176         if (v.is_binary())
1177         {
1178                 return used_phandles[v.get_as_uint32()];
1179         }
1180         return 0;
1181 }
1182
1183 void
1184 device_tree::write_binary(int fd)
1185 {
1186         write<dtb::binary_writer>(fd);
1187 }
1188
1189 void
1190 device_tree::write_asm(int fd)
1191 {
1192         write<dtb::asm_writer>(fd);
1193 }
1194
1195 void
1196 device_tree::write_dts(int fd)
1197 {
1198         FILE *file = fdopen(fd, "w");
1199         fputs("/dts-v1/;\n\n", file);
1200
1201         if (!reservations.empty())
1202         {
1203                 const char msg[] = "/memreserve/";
1204                 fwrite(msg, sizeof(msg), 1, file);
1205                 for (std::vector<reservation>::iterator i=reservations.begin(),
1206                      e=reservations.end() ; i!=e ; ++i)
1207                 {
1208                         fprintf(file, " %" PRIx64 " %" PRIx64, i->first, i->second);
1209                 }
1210                 fputs(";\n\n", file);
1211         }
1212         putc('/', file);
1213         putc(' ', file);
1214         root->write_dts(file, 0);
1215         fclose(file);
1216 }
1217
1218 void
1219 device_tree::parse_dtb(const char *fn, FILE *depfile)
1220 {
1221         input_buffer *in = buffer_for_file(fn);
1222         if (in == 0)
1223         {
1224                 valid = false;
1225                 return;
1226         }
1227         input_buffer &input = *in;
1228         dtb::header h;
1229         valid = h.read_dtb(input);
1230         boot_cpu = h.boot_cpuid_phys;
1231         if (h.last_comp_version > 17)
1232         {
1233                 fprintf(stderr, "Don't know how to read this version of the device tree blob");
1234                 valid = false;
1235         }
1236         if (!valid)
1237         {
1238                 return;
1239         }
1240         input_buffer reservation_map =
1241                 input.buffer_from_offset(h.off_mem_rsvmap, 0);
1242         uint64_t start, length;
1243         do
1244         {
1245                 if (!(reservation_map.consume_binary(start) &&
1246                       reservation_map.consume_binary(length)))
1247                 {
1248                         fprintf(stderr, "Failed to read memory reservation table\n");
1249                         valid = false;
1250                         return;
1251                 }
1252         } while (!((start == 0) && (length == 0)));
1253         input_buffer struct_table =
1254                 input.buffer_from_offset(h.off_dt_struct, h.size_dt_struct);
1255         input_buffer strings_table =
1256                 input.buffer_from_offset(h.off_dt_strings, h.size_dt_strings);
1257         uint32_t token;
1258         if (!(struct_table.consume_binary(token) &&
1259                 (token == dtb::FDT_BEGIN_NODE)))
1260         {
1261                 fprintf(stderr, "Expected FDT_BEGIN_NODE token.\n");
1262                 valid = false;
1263                 return;
1264         }
1265         root = node::parse_dtb(struct_table, strings_table);
1266         if (!(struct_table.consume_binary(token) && (token == dtb::FDT_END)))
1267         {
1268                 fprintf(stderr, "Expected FDT_END token after parsing root node.\n");
1269                 valid = false;
1270                 return;
1271         }
1272         valid = (root != 0);
1273 }
1274
1275 void
1276 device_tree::parse_dts(const char *fn, FILE *depfile)
1277 {
1278         input_buffer *in = buffer_for_file(fn);
1279         if (in == 0)
1280         {
1281                 valid = false;
1282                 return;
1283         }
1284         std::vector<node*> roots;
1285         input_buffer &input = *in;
1286         input.next_token();
1287         bool read_header = false;
1288         // Read the header
1289         if (input.consume("/dts-v1/;"))
1290         {
1291                 read_header = true;
1292         }
1293         input.next_token();
1294         while(input.consume("/include/"))
1295         {
1296                 bool reallyInclude = true;
1297                 if (input.consume("if "))
1298                 {
1299                         input.next_token();
1300                         string name = string::parse_property_name(input);
1301                         // XXX: Error handling
1302                         if (defines.find(name) == defines.end())
1303                         {
1304                                 reallyInclude = false;
1305                         }
1306                         input.consume('/');
1307                 }
1308                 input.next_token();
1309                 if (!input.consume('"'))
1310                 {
1311                         input.parse_error("Expected quoted filename");
1312                         valid = false;
1313                         return;
1314                 }
1315                 int length = 0;
1316                 while (input[length] != '"') length++;
1317
1318                 const char *file = (const char*)input;
1319                 const char *dir = dirname(fn);
1320                 int dir_length = strlen(dir);
1321                 char *include_file = (char*)malloc(strlen(dir) + length + 2);
1322                 memcpy(include_file, dir, dir_length);
1323                 include_file[dir_length] = '/';
1324                 memcpy(include_file+dir_length+1, file, length);
1325                 include_file[dir_length+length+1] = 0;
1326
1327                 input.consume(include_file+dir_length+1);
1328                 input.consume('"');
1329                 if (!reallyInclude)
1330                 {
1331                         continue;
1332                 }
1333
1334                 input_buffer *include_buffer = buffer_for_file(include_file);
1335
1336                 if (include_buffer == 0)
1337                 {
1338                         for (std::vector<const char*>::iterator i=include_paths.begin(), e=include_paths.end() ; e!=i ; ++i)
1339                         {
1340                                 free(include_file);
1341                                 dir = *i;
1342                                 dir_length = strlen(dir);
1343                                 include_file = (char*)malloc(strlen(dir) +
1344                                                 length + 2);
1345                                 memcpy(include_file, dir, dir_length);
1346                                 include_file[dir_length] = '/';
1347                                 memcpy(include_file+dir_length+1, file, length);
1348                                 include_file[dir_length+length+1] = 0;
1349                                 include_buffer = buffer_for_file(include_file);
1350                                 if (include_buffer != 0)
1351                                 {
1352                                         break;
1353                                 }
1354                         }
1355                 }
1356                 if (depfile != 0)
1357                 {
1358                         putc(' ', depfile);
1359                         fputs(include_file, depfile);
1360                 }
1361                 if (include_buffer == 0)
1362                 {
1363                         valid = false;
1364                         return;
1365                 }
1366                 input_buffer &include = *include_buffer;
1367                 free((void*)include_file);
1368
1369                 if (!read_header)
1370                 {
1371                         include.next_token();
1372                         read_header = include.consume("/dts-v1/;");
1373                 }
1374                 parse_roots(include, roots);
1375         }
1376         input.next_token();
1377         if (!read_header)
1378         {
1379                 input.parse_error("Expected /dts-v1/; version string");
1380         }
1381         // Read any memory reservations
1382         while(input.consume("/memreserve/"))
1383         {
1384                 long long start, len;
1385                 input.next_token();
1386                 // Read the start and length.
1387                 if (!(input.consume_integer(start) &&
1388                     (input.next_token(),
1389                     input.consume_integer(len))))
1390                 {
1391                         input.parse_error("Expected size on /memreserve/ node.");
1392                 }
1393                 input.next_token();
1394                 input.consume(';');
1395                 reservations.push_back(reservation(start, len));
1396         }
1397         parse_roots(input, roots);
1398         switch (roots.size())
1399         {
1400                 case 0:
1401                         valid = false;
1402                         input.parse_error("Failed to find root node /.");
1403                         return;
1404                 case 1:
1405                         root = roots[0];
1406                         break;
1407                 default:
1408                 {
1409                         root = roots[0];
1410                         for (std::vector<node*>::iterator i=roots.begin()+1,
1411                              e=roots.end() ; i!=e ; ++i)
1412                         {
1413                                 root->merge_node(*i);
1414                                 delete *i;
1415                         }
1416                         roots.resize(1);
1417                 }
1418         }
1419         collect_names();
1420         resolve_cross_references();
1421 }
1422
1423 device_tree::~device_tree()
1424 {
1425         if (root != 0)
1426         {
1427                 delete root;
1428         }
1429         while (!buffers.empty())
1430         {
1431                 delete buffers.back();
1432                 buffers.pop_back();
1433         }
1434         for (define_map::iterator i=defines.begin(), e=defines.end() ;
1435              i!=e ; ++i)
1436         {
1437                 delete i->second;
1438         }
1439 }
1440
1441 bool device_tree::parse_define(const char *def)
1442 {
1443         char *val = strchr(def, '=');
1444         if (!val)
1445         {
1446                 if (strlen(def) != 0)
1447                 {
1448                         string name(def);
1449                         defines[name];
1450                         return true;
1451                 }
1452                 return false;
1453         }
1454         string name(def, val-def);
1455         val++;
1456         input_buffer in = input_buffer(val, strlen(val));
1457         property *p = property::parse(in, name, string(), false);
1458         if (p)
1459                 defines[name] = p;
1460         return p;
1461 }
1462
1463 } // namespace fdt
1464
1465 } // namespace dtc
1466