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