1245803Stheraven/*- 2330449Seadler * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 3330449Seadler * 4245803Stheraven * Copyright (c) 2013 David Chisnall 5245803Stheraven * All rights reserved. 6245803Stheraven * 7245803Stheraven * This software was developed by SRI International and the University of 8245803Stheraven * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237) 9245803Stheraven * ("CTSRD"), as part of the DARPA CRASH research programme. 10245803Stheraven * 11245803Stheraven * Redistribution and use in source and binary forms, with or without 12245803Stheraven * modification, are permitted provided that the following conditions 13245803Stheraven * are met: 14245803Stheraven * 1. Redistributions of source code must retain the above copyright 15245803Stheraven * notice, this list of conditions and the following disclaimer. 16245803Stheraven * 2. Redistributions in binary form must reproduce the above copyright 17245803Stheraven * notice, this list of conditions and the following disclaimer in the 18245803Stheraven * documentation and/or other materials provided with the distribution. 19245803Stheraven * 20245803Stheraven * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 21245803Stheraven * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22245803Stheraven * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23245803Stheraven * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 24245803Stheraven * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25245803Stheraven * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26245803Stheraven * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27245803Stheraven * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28245803Stheraven * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29245803Stheraven * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30245803Stheraven * SUCH DAMAGE. 31245803Stheraven * 32245803Stheraven * $FreeBSD: stable/11/usr.bin/dtc/fdt.cc 358205 2020-02-21 04:34:54Z kevans $ 33245803Stheraven */ 34245803Stheraven 35253149Stheraven#define __STDC_LIMIT_MACROS 1 36253149Stheraven 37245803Stheraven#include "fdt.hh" 38289935Stheraven#include "dtb.hh" 39245803Stheraven 40245803Stheraven#include <algorithm> 41318093Sgonzo#include <sstream> 42289935Stheraven 43245839Stheraven#include <ctype.h> 44245839Stheraven#include <fcntl.h> 45245803Stheraven#include <inttypes.h> 46245803Stheraven#include <libgen.h> 47245839Stheraven#include <stdio.h> 48245839Stheraven#include <stdlib.h> 49345881Skevans#include <string.h> 50245839Stheraven#include <unistd.h> 51267317Srpaulo#include <sys/types.h> 52267317Srpaulo#include <sys/stat.h> 53289935Stheraven#include <errno.h> 54245803Stheraven 55318093Sgonzousing std::string; 56318093Sgonzo 57245803Stheravennamespace dtc 58245803Stheraven{ 59245803Stheraven 60245803Stheravennamespace fdt 61245803Stheraven{ 62245803Stheraven 63245803Stheravenuint32_t 64245803Stheravenproperty_value::get_as_uint32() 65245803Stheraven{ 66245803Stheraven if (byte_data.size() != 4) 67245803Stheraven { 68245803Stheraven return 0; 69245803Stheraven } 70245803Stheraven uint32_t v = 0; 71245803Stheraven v &= byte_data[0] << 24; 72245803Stheraven v &= byte_data[1] << 16; 73245803Stheraven v &= byte_data[2] << 8; 74245803Stheraven v &= byte_data[3] << 0; 75245803Stheraven return v; 76245803Stheraven} 77245803Stheraven 78245803Stheravenvoid 79245803Stheravenproperty_value::push_to_buffer(byte_buffer &buffer) 80245803Stheraven{ 81245803Stheraven if (!byte_data.empty()) 82245803Stheraven { 83245803Stheraven buffer.insert(buffer.end(), byte_data.begin(), byte_data.end()); 84245803Stheraven } 85245803Stheraven else 86245803Stheraven { 87318093Sgonzo push_string(buffer, string_data, true); 88245803Stheraven // Trailing nul 89245803Stheraven buffer.push_back(0); 90245803Stheraven } 91245803Stheraven} 92245803Stheraven 93245803Stheravenvoid 94245803Stheravenproperty_value::write_dts(FILE *file) 95245803Stheraven{ 96245803Stheraven resolve_type(); 97245803Stheraven switch (type) 98245803Stheraven { 99245803Stheraven default: 100245803Stheraven assert(0 && "Invalid type"); 101245803Stheraven case STRING: 102245803Stheraven case STRING_LIST: 103245803Stheraven case CROSS_REFERENCE: 104245803Stheraven write_as_string(file); 105245803Stheraven break; 106245803Stheraven case PHANDLE: 107245803Stheraven write_as_cells(file); 108245803Stheraven break; 109245803Stheraven case BINARY: 110245803Stheraven if (byte_data.size() % 4 == 0) 111245803Stheraven { 112245803Stheraven write_as_cells(file); 113245803Stheraven break; 114245803Stheraven } 115245803Stheraven write_as_bytes(file); 116245803Stheraven break; 117245803Stheraven } 118245803Stheraven} 119245803Stheraven 120245803Stheravenvoid 121245803Stheravenproperty_value::resolve_type() 122245803Stheraven{ 123245803Stheraven if (type != UNKNOWN) 124245803Stheraven { 125245803Stheraven return; 126245803Stheraven } 127245803Stheraven if (byte_data.empty()) 128245803Stheraven { 129245803Stheraven type = STRING; 130245803Stheraven return; 131245803Stheraven } 132245803Stheraven if (byte_data.back() == 0) 133245803Stheraven { 134245803Stheraven bool is_all_printable = true; 135245803Stheraven int nuls = 0; 136245803Stheraven int bytes = 0; 137289935Stheraven bool lastWasNull = false; 138289935Stheraven for (auto i : byte_data) 139245803Stheraven { 140245803Stheraven bytes++; 141289935Stheraven is_all_printable &= (i == '\0') || isprint(i); 142289935Stheraven if (i == '\0') 143245803Stheraven { 144289935Stheraven // If there are two nulls in a row, then we're probably binary. 145289935Stheraven if (lastWasNull) 146289935Stheraven { 147289935Stheraven type = BINARY; 148289935Stheraven return; 149289935Stheraven } 150245803Stheraven nuls++; 151289935Stheraven lastWasNull = true; 152245803Stheraven } 153289935Stheraven else 154289935Stheraven { 155289935Stheraven lastWasNull = false; 156289935Stheraven } 157245803Stheraven if (!is_all_printable) 158245803Stheraven { 159245803Stheraven break; 160245803Stheraven } 161245803Stheraven } 162259250Stheraven if ((is_all_printable && (bytes > nuls)) || bytes == 0) 163245803Stheraven { 164245803Stheraven type = STRING; 165289935Stheraven if (nuls > 1) 166245803Stheraven { 167245803Stheraven type = STRING_LIST; 168245803Stheraven } 169245803Stheraven return; 170245803Stheraven } 171245803Stheraven } 172245803Stheraven type = BINARY; 173245803Stheraven} 174245803Stheraven 175318093Sgonzosize_t 176318093Sgonzoproperty_value::size() 177318093Sgonzo{ 178318093Sgonzo if (!byte_data.empty()) 179318093Sgonzo { 180318093Sgonzo return byte_data.size(); 181318093Sgonzo } 182318093Sgonzo return string_data.size() + 1; 183318093Sgonzo} 184318093Sgonzo 185245803Stheravenvoid 186245803Stheravenproperty_value::write_as_string(FILE *file) 187245803Stheraven{ 188245803Stheraven putc('"', file); 189245803Stheraven if (byte_data.empty()) 190245803Stheraven { 191318093Sgonzo fputs(string_data.c_str(), file); 192245803Stheraven } 193245803Stheraven else 194245803Stheraven { 195289935Stheraven bool hasNull = (byte_data.back() == '\0'); 196289935Stheraven // Remove trailing null bytes from the string before printing as dts. 197289935Stheraven if (hasNull) 198245803Stheraven { 199289935Stheraven byte_data.pop_back(); 200289935Stheraven } 201289935Stheraven for (auto i : byte_data) 202289935Stheraven { 203245803Stheraven // FIXME Escape tabs, newlines, and so on. 204289935Stheraven if (i == '\0') 205245803Stheraven { 206245803Stheraven fputs("\", \"", file); 207245803Stheraven continue; 208245803Stheraven } 209289935Stheraven putc(i, file); 210245803Stheraven } 211289935Stheraven if (hasNull) 212289935Stheraven { 213289935Stheraven byte_data.push_back('\0'); 214289935Stheraven } 215245803Stheraven } 216245803Stheraven putc('"', file); 217245803Stheraven} 218245803Stheraven 219245803Stheravenvoid 220245803Stheravenproperty_value::write_as_cells(FILE *file) 221245803Stheraven{ 222245803Stheraven putc('<', file); 223245803Stheraven assert((byte_data.size() % 4) == 0); 224289935Stheraven for (auto i=byte_data.begin(), e=byte_data.end(); i!=e ; ++i) 225245803Stheraven { 226245803Stheraven uint32_t v = 0; 227245803Stheraven v = (v << 8) | *i; 228245803Stheraven ++i; 229245803Stheraven v = (v << 8) | *i; 230245803Stheraven ++i; 231245803Stheraven v = (v << 8) | *i; 232245803Stheraven ++i; 233245803Stheraven v = (v << 8) | *i; 234245803Stheraven fprintf(file, "0x%" PRIx32, v); 235245803Stheraven if (i+1 != e) 236245803Stheraven { 237245803Stheraven putc(' ', file); 238245803Stheraven } 239245803Stheraven } 240245803Stheraven putc('>', file); 241245803Stheraven} 242245803Stheraven 243245803Stheravenvoid 244245803Stheravenproperty_value::write_as_bytes(FILE *file) 245245803Stheraven{ 246245803Stheraven putc('[', file); 247289935Stheraven for (auto i=byte_data.begin(), e=byte_data.end(); i!=e ; i++) 248245803Stheraven { 249259250Stheraven fprintf(file, "%02hhx", *i); 250245803Stheraven if (i+1 != e) 251245803Stheraven { 252245803Stheraven putc(' ', file); 253245803Stheraven } 254245803Stheraven } 255245803Stheraven putc(']', file); 256245803Stheraven} 257245803Stheraven 258245803Stheravenvoid 259318093Sgonzoproperty::parse_string(text_input_buffer &input) 260245803Stheraven{ 261245803Stheraven property_value v; 262318093Sgonzo assert(*input == '"'); 263245803Stheraven ++input; 264318093Sgonzo std::vector<char> bytes; 265318093Sgonzo bool isEscaped = false; 266318093Sgonzo while (char c = *input) 267245803Stheraven { 268318093Sgonzo if (c == '"' && !isEscaped) 269245803Stheraven { 270245803Stheraven input.consume('"'); 271245803Stheraven break; 272245803Stheraven } 273318093Sgonzo isEscaped = (c == '\\'); 274318093Sgonzo bytes.push_back(c); 275245803Stheraven ++input; 276245803Stheraven } 277318093Sgonzo v.string_data = string(bytes.begin(), bytes.end()); 278245803Stheraven values.push_back(v); 279245803Stheraven} 280245803Stheraven 281245803Stheravenvoid 282318093Sgonzoproperty::parse_cells(text_input_buffer &input, int cell_size) 283245803Stheraven{ 284318093Sgonzo assert(*input == '<'); 285245803Stheraven ++input; 286245803Stheraven property_value v; 287245803Stheraven input.next_token(); 288245803Stheraven while (!input.consume('>')) 289245803Stheraven { 290245803Stheraven input.next_token(); 291245803Stheraven // If this is a phandle then we need to get the name of the 292245803Stheraven // referenced node 293245803Stheraven if (input.consume('&')) 294245803Stheraven { 295289935Stheraven if (cell_size != 32) 296289935Stheraven { 297289935Stheraven input.parse_error("reference only permitted in 32-bit arrays"); 298289935Stheraven valid = false; 299289935Stheraven return; 300289935Stheraven } 301245803Stheraven input.next_token(); 302318093Sgonzo string referenced; 303318093Sgonzo if (!input.consume('{')) 304318093Sgonzo { 305318093Sgonzo referenced = input.parse_node_name(); 306318093Sgonzo } 307318093Sgonzo else 308318093Sgonzo { 309318093Sgonzo referenced = input.parse_to('}'); 310318093Sgonzo input.consume('}'); 311318093Sgonzo } 312245803Stheraven if (referenced.empty()) 313245803Stheraven { 314245803Stheraven input.parse_error("Expected node name"); 315245803Stheraven valid = false; 316245803Stheraven return; 317245803Stheraven } 318245803Stheraven input.next_token(); 319245803Stheraven // If we already have some bytes, make the phandle a 320245803Stheraven // separate component. 321245803Stheraven if (!v.byte_data.empty()) 322245803Stheraven { 323245803Stheraven values.push_back(v); 324245803Stheraven v = property_value(); 325245803Stheraven } 326245803Stheraven v.string_data = referenced; 327245803Stheraven v.type = property_value::PHANDLE; 328245803Stheraven values.push_back(v); 329245803Stheraven v = property_value(); 330245803Stheraven } 331245803Stheraven else 332245803Stheraven { 333245803Stheraven //FIXME: We should support labels in the middle 334245803Stheraven //of these, but we don't. 335289935Stheraven unsigned long long val; 336292876Stheraven if (!input.consume_integer_expression(val)) 337245803Stheraven { 338245803Stheraven input.parse_error("Expected numbers in array of cells"); 339245803Stheraven valid = false; 340245803Stheraven return; 341245803Stheraven } 342289935Stheraven switch (cell_size) 343289935Stheraven { 344289935Stheraven case 8: 345289935Stheraven v.byte_data.push_back(val); 346289935Stheraven break; 347289935Stheraven case 16: 348289935Stheraven push_big_endian(v.byte_data, (uint16_t)val); 349289935Stheraven break; 350289935Stheraven case 32: 351289935Stheraven push_big_endian(v.byte_data, (uint32_t)val); 352289935Stheraven break; 353289935Stheraven case 64: 354289935Stheraven push_big_endian(v.byte_data, (uint64_t)val); 355289935Stheraven break; 356289935Stheraven default: 357289935Stheraven assert(0 && "Invalid cell size!"); 358289935Stheraven } 359245803Stheraven input.next_token(); 360245803Stheraven } 361245803Stheraven } 362245803Stheraven // Don't store an empty string value here. 363245803Stheraven if (v.byte_data.size() > 0) 364245803Stheraven { 365245803Stheraven values.push_back(v); 366245803Stheraven } 367245803Stheraven} 368245803Stheraven 369245803Stheravenvoid 370318093Sgonzoproperty::parse_bytes(text_input_buffer &input) 371245803Stheraven{ 372318093Sgonzo assert(*input == '['); 373245803Stheraven ++input; 374245803Stheraven property_value v; 375245803Stheraven input.next_token(); 376245803Stheraven while (!input.consume(']')) 377245803Stheraven { 378245803Stheraven { 379245803Stheraven //FIXME: We should support 380245803Stheraven //labels in the middle of 381245803Stheraven //these, but we don't. 382245803Stheraven uint8_t val; 383245803Stheraven if (!input.consume_hex_byte(val)) 384245803Stheraven { 385245803Stheraven input.parse_error("Expected hex bytes in array of bytes"); 386245803Stheraven valid = false; 387245803Stheraven return; 388245803Stheraven } 389245803Stheraven v.byte_data.push_back(val); 390245803Stheraven input.next_token(); 391245803Stheraven } 392245803Stheraven } 393245803Stheraven values.push_back(v); 394245803Stheraven} 395245803Stheraven 396245803Stheravenvoid 397318093Sgonzoproperty::parse_reference(text_input_buffer &input) 398245803Stheraven{ 399318093Sgonzo assert(*input == '&'); 400245803Stheraven ++input; 401245803Stheraven input.next_token(); 402245803Stheraven property_value v; 403318093Sgonzo v.string_data = input.parse_node_name(); 404245803Stheraven if (v.string_data.empty()) 405245803Stheraven { 406245803Stheraven input.parse_error("Expected node name"); 407245803Stheraven valid = false; 408245803Stheraven return; 409245803Stheraven } 410245803Stheraven v.type = property_value::CROSS_REFERENCE; 411245803Stheraven values.push_back(v); 412245803Stheraven} 413245803Stheraven 414245803Stheravenproperty::property(input_buffer &structs, input_buffer &strings) 415245803Stheraven{ 416245803Stheraven uint32_t name_offset; 417245803Stheraven uint32_t length; 418245803Stheraven valid = structs.consume_binary(length) && 419245803Stheraven structs.consume_binary(name_offset); 420245803Stheraven if (!valid) 421245803Stheraven { 422245803Stheraven fprintf(stderr, "Failed to read property\n"); 423245803Stheraven return; 424245803Stheraven } 425245803Stheraven // Find the name 426245803Stheraven input_buffer name_buffer = strings.buffer_from_offset(name_offset); 427318093Sgonzo if (name_buffer.finished()) 428245803Stheraven { 429245803Stheraven fprintf(stderr, "Property name offset %" PRIu32 430245803Stheraven " is past the end of the strings table\n", 431245803Stheraven name_offset); 432245803Stheraven valid = false; 433245803Stheraven return; 434245803Stheraven } 435318093Sgonzo key = name_buffer.parse_to(0); 436259250Stheraven 437259250Stheraven // If we're empty, do not push anything as value. 438259250Stheraven if (!length) 439259250Stheraven return; 440259250Stheraven 441245803Stheraven // Read the value 442245803Stheraven uint8_t byte; 443245803Stheraven property_value v; 444245803Stheraven for (uint32_t i=0 ; i<length ; i++) 445245803Stheraven { 446245803Stheraven if (!(valid = structs.consume_binary(byte))) 447245803Stheraven { 448245803Stheraven fprintf(stderr, "Failed to read property value\n"); 449245803Stheraven return; 450245803Stheraven } 451245803Stheraven v.byte_data.push_back(byte); 452245803Stheraven } 453245803Stheraven values.push_back(v); 454245803Stheraven} 455245803Stheraven 456318093Sgonzovoid property::parse_define(text_input_buffer &input, define_map *defines) 457245803Stheraven{ 458254522Stheraven input.consume('$'); 459254522Stheraven if (!defines) 460254522Stheraven { 461254522Stheraven input.parse_error("No predefined properties to match name\n"); 462254522Stheraven valid = false; 463254522Stheraven return; 464254522Stheraven } 465318093Sgonzo string name = input.parse_property_name(); 466254522Stheraven define_map::iterator found; 467254522Stheraven if ((name == string()) || 468254522Stheraven ((found = defines->find(name)) == defines->end())) 469254522Stheraven { 470254522Stheraven input.parse_error("Undefined property name\n"); 471254522Stheraven valid = false; 472254522Stheraven return; 473254522Stheraven } 474254522Stheraven values.push_back((*found).second->values[0]); 475254522Stheraven} 476254522Stheraven 477318093Sgonzoproperty::property(text_input_buffer &input, 478318093Sgonzo string &&k, 479318093Sgonzo string_set &&l, 480254522Stheraven bool semicolonTerminated, 481318093Sgonzo define_map *defines) : key(k), labels(l), valid(true) 482254522Stheraven{ 483245803Stheraven do { 484245803Stheraven input.next_token(); 485318093Sgonzo switch (*input) 486245803Stheraven { 487254522Stheraven case '$': 488254522Stheraven { 489254522Stheraven parse_define(input, defines); 490254522Stheraven if (valid) 491254522Stheraven { 492254522Stheraven break; 493254522Stheraven } 494254522Stheraven } 495345881Skevans [[fallthrough]]; 496245803Stheraven default: 497245803Stheraven input.parse_error("Invalid property value."); 498245803Stheraven valid = false; 499245803Stheraven return; 500289935Stheraven case '/': 501289935Stheraven { 502328495Skevans if (input.consume("/incbin/(\"")) 503328495Skevans { 504328495Skevans auto loc = input.location(); 505328495Skevans std::string filename = input.parse_to('"'); 506328495Skevans if (!(valid = input.consume('"'))) 507328495Skevans { 508328495Skevans loc.report_error("Syntax error, expected '\"' to terminate /incbin/("); 509328495Skevans return; 510328495Skevans } 511328495Skevans property_value v; 512328495Skevans if (!(valid = input.read_binary_file(filename, v.byte_data))) 513328495Skevans { 514328495Skevans input.parse_error("Cannot open binary include file"); 515328495Skevans return; 516328495Skevans } 517328495Skevans if (!(valid &= input.consume(')'))) 518328495Skevans { 519328495Skevans input.parse_error("Syntax error, expected ')' to terminate /incbin/("); 520328495Skevans return; 521328495Skevans } 522328495Skevans values.push_back(v); 523328495Skevans break; 524328495Skevans } 525289935Stheraven unsigned long long bits = 0; 526289935Stheraven valid = input.consume("/bits/"); 527289935Stheraven input.next_token(); 528289935Stheraven valid &= input.consume_integer(bits); 529289935Stheraven if ((bits != 8) && 530289935Stheraven (bits != 16) && 531289935Stheraven (bits != 32) && 532289935Stheraven (bits != 64)) { 533289935Stheraven input.parse_error("Invalid size for elements"); 534289935Stheraven valid = false; 535289935Stheraven } 536289935Stheraven if (!valid) return; 537289935Stheraven input.next_token(); 538318093Sgonzo if (*input != '<') 539289935Stheraven { 540289935Stheraven input.parse_error("/bits/ directive is only valid on arrays"); 541289935Stheraven valid = false; 542289935Stheraven return; 543289935Stheraven } 544289935Stheraven parse_cells(input, bits); 545289935Stheraven break; 546289935Stheraven } 547245803Stheraven case '"': 548245803Stheraven parse_string(input); 549245803Stheraven break; 550245803Stheraven case '<': 551289935Stheraven parse_cells(input, 32); 552245803Stheraven break; 553245803Stheraven case '[': 554245803Stheraven parse_bytes(input); 555245803Stheraven break; 556245803Stheraven case '&': 557245803Stheraven parse_reference(input); 558245803Stheraven break; 559245803Stheraven case ';': 560245803Stheraven { 561245803Stheraven break; 562245803Stheraven } 563245803Stheraven } 564245803Stheraven input.next_token(); 565245803Stheraven } while (input.consume(',')); 566254522Stheraven if (semicolonTerminated && !input.consume(';')) 567245803Stheraven { 568245803Stheraven input.parse_error("Expected ; at end of property"); 569245803Stheraven valid = false; 570245803Stheraven } 571245803Stheraven} 572245803Stheraven 573289935Stheravenproperty_ptr 574245803Stheravenproperty::parse_dtb(input_buffer &structs, input_buffer &strings) 575245803Stheraven{ 576289935Stheraven property_ptr p(new property(structs, strings)); 577245803Stheraven if (!p->valid) 578245803Stheraven { 579289935Stheraven p = nullptr; 580245803Stheraven } 581245803Stheraven return p; 582245803Stheraven} 583245803Stheraven 584289935Stheravenproperty_ptr 585318093Sgonzoproperty::parse(text_input_buffer &input, string &&key, string_set &&label, 586254522Stheraven bool semicolonTerminated, define_map *defines) 587245803Stheraven{ 588318093Sgonzo property_ptr p(new property(input, 589318093Sgonzo std::move(key), 590318093Sgonzo std::move(label), 591318093Sgonzo semicolonTerminated, 592318093Sgonzo defines)); 593245803Stheraven if (!p->valid) 594245803Stheraven { 595289935Stheraven p = nullptr; 596245803Stheraven } 597245803Stheraven return p; 598245803Stheraven} 599245803Stheraven 600245803Stheravenvoid 601245803Stheravenproperty::write(dtb::output_writer &writer, dtb::string_table &strings) 602245803Stheraven{ 603245803Stheraven writer.write_token(dtb::FDT_PROP); 604245803Stheraven byte_buffer value_buffer; 605245803Stheraven for (value_iterator i=begin(), e=end() ; i!=e ; ++i) 606245803Stheraven { 607245803Stheraven i->push_to_buffer(value_buffer); 608245803Stheraven } 609245803Stheraven writer.write_data((uint32_t)value_buffer.size()); 610245803Stheraven writer.write_comment(key); 611245803Stheraven writer.write_data(strings.add_string(key)); 612245803Stheraven writer.write_data(value_buffer); 613245803Stheraven} 614245803Stheraven 615289935Stheravenbool 616289935Stheravenproperty_value::try_to_merge(property_value &other) 617289935Stheraven{ 618289935Stheraven resolve_type(); 619289935Stheraven switch (type) 620289935Stheraven { 621289935Stheraven case UNKNOWN: 622289935Stheraven __builtin_unreachable(); 623289935Stheraven assert(0); 624289935Stheraven return false; 625289935Stheraven case EMPTY: 626289935Stheraven *this = other; 627345881Skevans [[fallthrough]]; 628289935Stheraven case STRING: 629289935Stheraven case STRING_LIST: 630289935Stheraven case CROSS_REFERENCE: 631289935Stheraven return false; 632289935Stheraven case PHANDLE: 633289935Stheraven case BINARY: 634289935Stheraven if (other.type == PHANDLE || other.type == BINARY) 635289935Stheraven { 636289935Stheraven type = BINARY; 637289935Stheraven byte_data.insert(byte_data.end(), other.byte_data.begin(), 638289935Stheraven other.byte_data.end()); 639289935Stheraven return true; 640289935Stheraven } 641289935Stheraven } 642289935Stheraven return false; 643289935Stheraven} 644289935Stheraven 645245803Stheravenvoid 646245803Stheravenproperty::write_dts(FILE *file, int indent) 647245803Stheraven{ 648245803Stheraven for (int i=0 ; i<indent ; i++) 649245803Stheraven { 650245803Stheraven putc('\t', file); 651245803Stheraven } 652318093Sgonzo#ifdef PRINT_LABELS 653318093Sgonzo for (auto &l : labels) 654245803Stheraven { 655318093Sgonzo fputs(l.c_str(), file); 656245803Stheraven fputs(": ", file); 657245803Stheraven } 658318093Sgonzo#endif 659245803Stheraven if (key != string()) 660245803Stheraven { 661318093Sgonzo fputs(key.c_str(), file); 662245803Stheraven } 663245803Stheraven if (!values.empty()) 664245803Stheraven { 665289935Stheraven std::vector<property_value> *vals = &values; 666289935Stheraven std::vector<property_value> v; 667289935Stheraven // If we've got multiple values then try to merge them all together. 668289935Stheraven if (values.size() > 1) 669289935Stheraven { 670289935Stheraven vals = &v; 671289935Stheraven v.push_back(values.front()); 672289935Stheraven for (auto i=(++begin()), e=end() ; i!=e ; ++i) 673289935Stheraven { 674289935Stheraven if (!v.back().try_to_merge(*i)) 675289935Stheraven { 676289935Stheraven v.push_back(*i); 677289935Stheraven } 678289935Stheraven } 679289935Stheraven } 680245803Stheraven fputs(" = ", file); 681289935Stheraven for (auto i=vals->begin(), e=vals->end() ; i!=e ; ++i) 682245803Stheraven { 683245803Stheraven i->write_dts(file); 684245803Stheraven if (i+1 != e) 685245803Stheraven { 686245803Stheraven putc(',', file); 687245803Stheraven putc(' ', file); 688245803Stheraven } 689245803Stheraven } 690245803Stheraven } 691245803Stheraven fputs(";\n", file); 692245803Stheraven} 693245803Stheraven 694318093Sgonzosize_t 695318093Sgonzoproperty::offset_of_value(property_value &val) 696318093Sgonzo{ 697318093Sgonzo size_t off = 0; 698318093Sgonzo for (auto &v : values) 699318093Sgonzo { 700318093Sgonzo if (&v == &val) 701318093Sgonzo { 702318093Sgonzo return off; 703318093Sgonzo } 704318093Sgonzo off += v.size(); 705318093Sgonzo } 706318093Sgonzo return -1; 707318093Sgonzo} 708318093Sgonzo 709245803Stheravenstring 710318093Sgonzonode::parse_name(text_input_buffer &input, bool &is_property, const char *error) 711245803Stheraven{ 712245803Stheraven if (!valid) 713245803Stheraven { 714245803Stheraven return string(); 715245803Stheraven } 716245803Stheraven input.next_token(); 717245803Stheraven if (is_property) 718245803Stheraven { 719318093Sgonzo return input.parse_property_name(); 720245803Stheraven } 721318093Sgonzo string n = input.parse_node_or_property_name(is_property); 722245803Stheraven if (n.empty()) 723245803Stheraven { 724245803Stheraven if (n.empty()) 725245803Stheraven { 726245803Stheraven input.parse_error(error); 727245803Stheraven valid = false; 728245803Stheraven } 729245803Stheraven } 730245803Stheraven return n; 731245803Stheraven} 732245803Stheraven 733332562Skevansnode::visit_behavior 734332562Skevansnode::visit(std::function<visit_behavior(node&, node*)> fn, node *parent) 735292876Stheraven{ 736332562Skevans visit_behavior behavior; 737332562Skevans behavior = fn(*this, parent); 738332562Skevans if (behavior == VISIT_BREAK) 739292876Stheraven { 740332562Skevans return VISIT_BREAK; 741292876Stheraven } 742332562Skevans else if (behavior != VISIT_CONTINUE) 743332562Skevans { 744332562Skevans for (auto &&c : children) 745332562Skevans { 746332562Skevans behavior = c->visit(fn, this); 747332562Skevans // Any status other than VISIT_RECURSE stops our execution and 748332562Skevans // bubbles up to our caller. The caller may then either continue 749332562Skevans // visiting nodes that are siblings to this one or completely halt 750332562Skevans // visiting. 751332562Skevans if (behavior != VISIT_RECURSE) 752332562Skevans { 753332562Skevans return behavior; 754332562Skevans } 755332562Skevans } 756332562Skevans } 757332562Skevans // Continue recursion by default 758332562Skevans return VISIT_RECURSE; 759292876Stheraven} 760292876Stheraven 761245803Stheravennode::node(input_buffer &structs, input_buffer &strings) : valid(true) 762245803Stheraven{ 763318093Sgonzo std::vector<char> bytes; 764245803Stheraven while (structs[0] != '\0' && structs[0] != '@') 765245803Stheraven { 766318093Sgonzo bytes.push_back(structs[0]); 767245803Stheraven ++structs; 768245803Stheraven } 769318093Sgonzo name = string(bytes.begin(), bytes.end()); 770318093Sgonzo bytes.clear(); 771245803Stheraven if (structs[0] == '@') 772245803Stheraven { 773245803Stheraven ++structs; 774245803Stheraven while (structs[0] != '\0') 775245803Stheraven { 776318093Sgonzo bytes.push_back(structs[0]); 777245803Stheraven ++structs; 778245803Stheraven } 779318093Sgonzo unit_address = string(bytes.begin(), bytes.end()); 780245803Stheraven } 781245803Stheraven ++structs; 782245803Stheraven uint32_t token; 783245803Stheraven while (structs.consume_binary(token)) 784245803Stheraven { 785245803Stheraven switch (token) 786245803Stheraven { 787245803Stheraven default: 788245803Stheraven fprintf(stderr, "Unexpected token 0x%" PRIx32 789245803Stheraven " while parsing node.\n", token); 790245803Stheraven valid = false; 791245803Stheraven return; 792245803Stheraven // Child node, parse it. 793245803Stheraven case dtb::FDT_BEGIN_NODE: 794245803Stheraven { 795289935Stheraven node_ptr child = node::parse_dtb(structs, strings); 796245803Stheraven if (child == 0) 797245803Stheraven { 798245803Stheraven valid = false; 799245803Stheraven return; 800245803Stheraven } 801289935Stheraven children.push_back(std::move(child)); 802245803Stheraven break; 803245803Stheraven } 804245803Stheraven // End of this node, no errors. 805245803Stheraven case dtb::FDT_END_NODE: 806245803Stheraven return; 807245803Stheraven // Property, parse it. 808245803Stheraven case dtb::FDT_PROP: 809245803Stheraven { 810289935Stheraven property_ptr prop = property::parse_dtb(structs, strings); 811245803Stheraven if (prop == 0) 812245803Stheraven { 813245803Stheraven valid = false; 814245803Stheraven return; 815245803Stheraven } 816292876Stheraven props.push_back(prop); 817245803Stheraven break; 818245803Stheraven } 819245803Stheraven break; 820245803Stheraven // End of structs table. Should appear after 821245803Stheraven // the end of the last node. 822245803Stheraven case dtb::FDT_END: 823245803Stheraven fprintf(stderr, "Unexpected FDT_END token while parsing node.\n"); 824245803Stheraven valid = false; 825245803Stheraven return; 826245803Stheraven // NOPs are padding. Ignore them. 827245803Stheraven case dtb::FDT_NOP: 828245803Stheraven break; 829245803Stheraven } 830245803Stheraven } 831245803Stheraven fprintf(stderr, "Failed to read token from structs table while parsing node.\n"); 832245803Stheraven valid = false; 833245803Stheraven return; 834245803Stheraven} 835245803Stheraven 836318093Sgonzo 837318093Sgonzonode::node(const string &n, 838318093Sgonzo const std::vector<property_ptr> &p) 839318093Sgonzo : name(n) 840245803Stheraven{ 841318093Sgonzo props.insert(props.begin(), p.begin(), p.end()); 842318093Sgonzo} 843318093Sgonzo 844318093Sgonzonode_ptr node::create_special_node(const string &name, 845318093Sgonzo const std::vector<property_ptr> &props) 846318093Sgonzo{ 847318093Sgonzo node_ptr n(new node(name, props)); 848318093Sgonzo return n; 849318093Sgonzo} 850318093Sgonzo 851318093Sgonzonode::node(text_input_buffer &input, 852345881Skevans device_tree &tree, 853318093Sgonzo string &&n, 854318093Sgonzo std::unordered_set<string> &&l, 855318093Sgonzo string &&a, 856318093Sgonzo define_map *defines) 857318093Sgonzo : labels(l), name(n), unit_address(a), valid(true) 858318093Sgonzo{ 859245803Stheraven if (!input.consume('{')) 860245803Stheraven { 861245803Stheraven input.parse_error("Expected { to start new device tree node.\n"); 862245803Stheraven } 863245803Stheraven input.next_token(); 864245803Stheraven while (valid && !input.consume('}')) 865245803Stheraven { 866245803Stheraven // flag set if we find any characters that are only in 867245803Stheraven // the property name character set, not the node 868245803Stheraven bool is_property = false; 869345881Skevans // flag set if our node is marked as /omit-if-no-ref/ to be 870345881Skevans // garbage collected later if nothing references it 871345881Skevans bool marked_omit_if_no_ref = false; 872318093Sgonzo string child_name, child_address; 873318093Sgonzo std::unordered_set<string> child_labels; 874318093Sgonzo auto parse_delete = [&](const char *expected, bool at) 875318093Sgonzo { 876318093Sgonzo if (child_name == string()) 877318093Sgonzo { 878318093Sgonzo input.parse_error(expected); 879318093Sgonzo valid = false; 880318093Sgonzo return; 881318093Sgonzo } 882318093Sgonzo input.next_token(); 883318093Sgonzo if (at && input.consume('@')) 884318093Sgonzo { 885318093Sgonzo child_name += '@'; 886318093Sgonzo child_name += parse_name(input, is_property, "Expected unit address"); 887318093Sgonzo } 888318093Sgonzo if (!input.consume(';')) 889318093Sgonzo { 890318093Sgonzo input.parse_error("Expected semicolon"); 891318093Sgonzo valid = false; 892318093Sgonzo return; 893318093Sgonzo } 894318093Sgonzo input.next_token(); 895318093Sgonzo }; 896318093Sgonzo if (input.consume("/delete-node/")) 897318093Sgonzo { 898318093Sgonzo input.next_token(); 899318093Sgonzo child_name = input.parse_node_name(); 900318093Sgonzo parse_delete("Expected node name", true); 901318093Sgonzo if (valid) 902318093Sgonzo { 903318093Sgonzo deleted_children.insert(child_name); 904318093Sgonzo } 905318093Sgonzo continue; 906318093Sgonzo } 907318093Sgonzo if (input.consume("/delete-property/")) 908318093Sgonzo { 909318093Sgonzo input.next_token(); 910318093Sgonzo child_name = input.parse_property_name(); 911318093Sgonzo parse_delete("Expected property name", false); 912318093Sgonzo if (valid) 913318093Sgonzo { 914318093Sgonzo deleted_props.insert(child_name); 915318093Sgonzo } 916318093Sgonzo continue; 917318093Sgonzo } 918345881Skevans if (input.consume("/omit-if-no-ref/")) 919345881Skevans { 920345881Skevans input.next_token(); 921345881Skevans marked_omit_if_no_ref = true; 922345881Skevans tree.set_needs_garbage_collection(); 923345881Skevans } 924245803Stheraven child_name = parse_name(input, is_property, 925245803Stheraven "Expected property or node name"); 926318093Sgonzo while (input.consume(':')) 927245803Stheraven { 928245803Stheraven // Node labels can contain any characters? The 929245803Stheraven // spec doesn't say, so we guess so... 930245803Stheraven is_property = false; 931318093Sgonzo child_labels.insert(std::move(child_name)); 932245803Stheraven child_name = parse_name(input, is_property, "Expected property or node name"); 933245803Stheraven } 934245803Stheraven if (input.consume('@')) 935245803Stheraven { 936245803Stheraven child_address = parse_name(input, is_property, "Expected unit address"); 937245803Stheraven } 938245803Stheraven if (!valid) 939245803Stheraven { 940245803Stheraven return; 941245803Stheraven } 942245803Stheraven input.next_token(); 943245803Stheraven // If we're parsing a property, then we must actually do that. 944245803Stheraven if (input.consume('=')) 945245803Stheraven { 946318093Sgonzo property_ptr p = property::parse(input, std::move(child_name), 947318093Sgonzo std::move(child_labels), true, defines); 948245803Stheraven if (p == 0) 949245803Stheraven { 950245803Stheraven valid = false; 951245803Stheraven } 952245803Stheraven else 953245803Stheraven { 954292876Stheraven props.push_back(p); 955245803Stheraven } 956245803Stheraven } 957318093Sgonzo else if (!is_property && *input == ('{')) 958245803Stheraven { 959345881Skevans node_ptr child = node::parse(input, tree, std::move(child_name), 960318093Sgonzo std::move(child_labels), std::move(child_address), defines); 961245803Stheraven if (child) 962245803Stheraven { 963345881Skevans child->omit_if_no_ref = marked_omit_if_no_ref; 964289935Stheraven children.push_back(std::move(child)); 965245803Stheraven } 966245803Stheraven else 967245803Stheraven { 968245803Stheraven valid = false; 969245803Stheraven } 970245803Stheraven } 971245803Stheraven else if (input.consume(';')) 972245803Stheraven { 973318093Sgonzo props.push_back(property_ptr(new property(std::move(child_name), std::move(child_labels)))); 974245803Stheraven } 975245803Stheraven else 976245803Stheraven { 977318093Sgonzo input.parse_error("Error parsing property. Expected property value"); 978245803Stheraven valid = false; 979245803Stheraven } 980245803Stheraven input.next_token(); 981245803Stheraven } 982318093Sgonzo input.next_token(); 983245803Stheraven input.consume(';'); 984245803Stheraven} 985245803Stheraven 986245803Stheravenbool 987289935Stheravennode::cmp_properties(property_ptr &p1, property_ptr &p2) 988245803Stheraven{ 989245803Stheraven return p1->get_key() < p2->get_key(); 990245803Stheraven} 991245803Stheraven 992245803Stheravenbool 993289935Stheravennode::cmp_children(node_ptr &c1, node_ptr &c2) 994245803Stheraven{ 995245803Stheraven if (c1->name == c2->name) 996245803Stheraven { 997245803Stheraven return c1->unit_address < c2->unit_address; 998245803Stheraven } 999245803Stheraven return c1->name < c2->name; 1000245803Stheraven} 1001245803Stheraven 1002245803Stheravenvoid 1003245803Stheravennode::sort() 1004245803Stheraven{ 1005245803Stheraven std::sort(property_begin(), property_end(), cmp_properties); 1006245803Stheraven std::sort(child_begin(), child_end(), cmp_children); 1007292876Stheraven for (auto &c : child_nodes()) 1008245803Stheraven { 1009292876Stheraven c->sort(); 1010245803Stheraven } 1011245803Stheraven} 1012245803Stheraven 1013289935Stheravennode_ptr 1014318093Sgonzonode::parse(text_input_buffer &input, 1015345881Skevans device_tree &tree, 1016318093Sgonzo string &&name, 1017318093Sgonzo string_set &&label, 1018318093Sgonzo string &&address, 1019254522Stheraven define_map *defines) 1020245803Stheraven{ 1021318093Sgonzo node_ptr n(new node(input, 1022345881Skevans tree, 1023318093Sgonzo std::move(name), 1024318093Sgonzo std::move(label), 1025318093Sgonzo std::move(address), 1026318093Sgonzo defines)); 1027245803Stheraven if (!n->valid) 1028245803Stheraven { 1029245803Stheraven n = 0; 1030245803Stheraven } 1031245803Stheraven return n; 1032245803Stheraven} 1033245803Stheraven 1034289935Stheravennode_ptr 1035245803Stheravennode::parse_dtb(input_buffer &structs, input_buffer &strings) 1036245803Stheraven{ 1037289935Stheraven node_ptr n(new node(structs, strings)); 1038245803Stheraven if (!n->valid) 1039245803Stheraven { 1040245803Stheraven n = 0; 1041245803Stheraven } 1042245803Stheraven return n; 1043245803Stheraven} 1044245803Stheraven 1045289935Stheravenproperty_ptr 1046318093Sgonzonode::get_property(const string &key) 1047245803Stheraven{ 1048292876Stheraven for (auto &i : props) 1049245803Stheraven { 1050289935Stheraven if (i->get_key() == key) 1051245803Stheraven { 1052289935Stheraven return i; 1053245803Stheraven } 1054245803Stheraven } 1055245803Stheraven return 0; 1056245803Stheraven} 1057245803Stheraven 1058245803Stheravenvoid 1059328495Skevansnode::merge_node(node_ptr &other) 1060245803Stheraven{ 1061318093Sgonzo for (auto &l : other->labels) 1062245803Stheraven { 1063318093Sgonzo labels.insert(l); 1064245803Stheraven } 1065345881Skevans children.erase(std::remove_if(children.begin(), children.end(), 1066345881Skevans [&](const node_ptr &p) { 1067345881Skevans string full_name = p->name; 1068345881Skevans if (p->unit_address != string()) 1069345881Skevans { 1070345881Skevans full_name += '@'; 1071345881Skevans full_name += p->unit_address; 1072345881Skevans } 1073345881Skevans if (other->deleted_children.count(full_name) > 0) 1074345881Skevans { 1075345881Skevans other->deleted_children.erase(full_name); 1076345881Skevans return true; 1077345881Skevans } 1078345881Skevans return false; 1079345881Skevans }), children.end()); 1080345881Skevans props.erase(std::remove_if(props.begin(), props.end(), 1081345881Skevans [&](const property_ptr &p) { 1082345881Skevans if (other->deleted_props.count(p->get_key()) > 0) 1083345881Skevans { 1084345881Skevans other->deleted_props.erase(p->get_key()); 1085345881Skevans return true; 1086345881Skevans } 1087345881Skevans return false; 1088345881Skevans }), props.end()); 1089245803Stheraven // Note: this is an O(n*m) operation. It might be sensible to 1090245803Stheraven // optimise this if we find that there are nodes with very 1091245803Stheraven // large numbers of properties, but for typical usage the 1092245803Stheraven // entire vector will fit (easily) into cache, so iterating 1093245803Stheraven // over it repeatedly isn't that expensive. 1094292876Stheraven for (auto &p : other->properties()) 1095245803Stheraven { 1096289935Stheraven bool found = false; 1097292876Stheraven for (auto &mp : properties()) 1098245803Stheraven { 1099292876Stheraven if (mp->get_key() == p->get_key()) 1100245803Stheraven { 1101292876Stheraven mp = p; 1102289935Stheraven found = true; 1103245803Stheraven break; 1104245803Stheraven } 1105245803Stheraven } 1106289935Stheraven if (!found) 1107289935Stheraven { 1108289935Stheraven add_property(p); 1109289935Stheraven } 1110245803Stheraven } 1111289935Stheraven for (auto &c : other->children) 1112245803Stheraven { 1113245803Stheraven bool found = false; 1114289935Stheraven for (auto &i : children) 1115245803Stheraven { 1116289935Stheraven if (i->name == c->name && i->unit_address == c->unit_address) 1117245803Stheraven { 1118328495Skevans i->merge_node(c); 1119245803Stheraven found = true; 1120245803Stheraven break; 1121245803Stheraven } 1122245803Stheraven } 1123245803Stheraven if (!found) 1124245803Stheraven { 1125289935Stheraven children.push_back(std::move(c)); 1126245803Stheraven } 1127245803Stheraven } 1128245803Stheraven} 1129245803Stheraven 1130245803Stheravenvoid 1131245803Stheravennode::write(dtb::output_writer &writer, dtb::string_table &strings) 1132245803Stheraven{ 1133245803Stheraven writer.write_token(dtb::FDT_BEGIN_NODE); 1134245803Stheraven byte_buffer name_buffer; 1135318093Sgonzo push_string(name_buffer, name); 1136245803Stheraven if (unit_address != string()) 1137245803Stheraven { 1138245803Stheraven name_buffer.push_back('@'); 1139318093Sgonzo push_string(name_buffer, unit_address); 1140245803Stheraven } 1141245803Stheraven writer.write_comment(name); 1142245803Stheraven writer.write_data(name_buffer); 1143245803Stheraven writer.write_data((uint8_t)0); 1144292876Stheraven for (auto p : properties()) 1145245803Stheraven { 1146292876Stheraven p->write(writer, strings); 1147245803Stheraven } 1148292876Stheraven for (auto &c : child_nodes()) 1149245803Stheraven { 1150292876Stheraven c->write(writer, strings); 1151245803Stheraven } 1152245803Stheraven writer.write_token(dtb::FDT_END_NODE); 1153245803Stheraven} 1154245803Stheraven 1155245803Stheravenvoid 1156245803Stheravennode::write_dts(FILE *file, int indent) 1157245803Stheraven{ 1158245803Stheraven for (int i=0 ; i<indent ; i++) 1159245803Stheraven { 1160245803Stheraven putc('\t', file); 1161245803Stheraven } 1162289935Stheraven#ifdef PRINT_LABELS 1163318093Sgonzo for (auto &label : labels) 1164245803Stheraven { 1165318093Sgonzo fprintf(file, "%s: ", label.c_str()); 1166245803Stheraven } 1167289935Stheraven#endif 1168245803Stheraven if (name != string()) 1169245803Stheraven { 1170318093Sgonzo fputs(name.c_str(), file); 1171245803Stheraven } 1172245803Stheraven if (unit_address != string()) 1173245803Stheraven { 1174245803Stheraven putc('@', file); 1175318093Sgonzo fputs(unit_address.c_str(), file); 1176245803Stheraven } 1177245803Stheraven fputs(" {\n\n", file); 1178292876Stheraven for (auto p : properties()) 1179245803Stheraven { 1180292876Stheraven p->write_dts(file, indent+1); 1181245803Stheraven } 1182292876Stheraven for (auto &c : child_nodes()) 1183245803Stheraven { 1184292876Stheraven c->write_dts(file, indent+1); 1185245803Stheraven } 1186245803Stheraven for (int i=0 ; i<indent ; i++) 1187245803Stheraven { 1188245803Stheraven putc('\t', file); 1189245803Stheraven } 1190245803Stheraven fputs("};\n", file); 1191245803Stheraven} 1192245803Stheraven 1193245803Stheravenvoid 1194289935Stheravendevice_tree::collect_names_recursive(node_ptr &n, node_path &path) 1195245803Stheraven{ 1196245803Stheraven path.push_back(std::make_pair(n->name, n->unit_address)); 1197318093Sgonzo for (const string &name : n->labels) 1198245803Stheraven { 1199318093Sgonzo if (name != string()) 1200245803Stheraven { 1201318093Sgonzo auto iter = node_names.find(name); 1202318093Sgonzo if (iter == node_names.end()) 1203245803Stheraven { 1204318093Sgonzo node_names.insert(std::make_pair(name, n.get())); 1205318093Sgonzo node_paths.insert(std::make_pair(name, path)); 1206345881Skevans ordered_node_paths.push_back({name, path}); 1207245803Stheraven } 1208318093Sgonzo else 1209318093Sgonzo { 1210318093Sgonzo node_names.erase(iter); 1211318093Sgonzo auto i = node_paths.find(name); 1212318093Sgonzo if (i != node_paths.end()) 1213318093Sgonzo { 1214318093Sgonzo node_paths.erase(name); 1215318093Sgonzo } 1216318093Sgonzo fprintf(stderr, "Label not unique: %s. References to this label will not be resolved.\n", name.c_str()); 1217318093Sgonzo } 1218245803Stheraven } 1219245803Stheraven } 1220292876Stheraven for (auto &c : n->child_nodes()) 1221245803Stheraven { 1222292876Stheraven collect_names_recursive(c, path); 1223245803Stheraven } 1224245803Stheraven // Now we collect the phandles and properties that reference 1225245803Stheraven // other nodes. 1226292876Stheraven for (auto &p : n->properties()) 1227245803Stheraven { 1228292876Stheraven for (auto &v : *p) 1229245803Stheraven { 1230292876Stheraven if (v.is_phandle()) 1231245803Stheraven { 1232318093Sgonzo fixups.push_back({path, p, v}); 1233245803Stheraven } 1234292876Stheraven if (v.is_cross_reference()) 1235245803Stheraven { 1236292876Stheraven cross_references.push_back(&v); 1237245803Stheraven } 1238245803Stheraven } 1239318093Sgonzo if ((p->get_key() == "phandle") || 1240318093Sgonzo (p->get_key() == "linux,phandle")) 1241245803Stheraven { 1242292876Stheraven if (p->begin()->byte_data.size() != 4) 1243245803Stheraven { 1244318093Sgonzo fprintf(stderr, "Invalid phandle value for node %s. Should be a 4-byte value.\n", n->name.c_str()); 1245245803Stheraven valid = false; 1246245803Stheraven } 1247245803Stheraven else 1248245803Stheraven { 1249292876Stheraven uint32_t phandle = p->begin()->get_as_uint32(); 1250289935Stheraven used_phandles.insert(std::make_pair(phandle, n.get())); 1251245803Stheraven } 1252245803Stheraven } 1253245803Stheraven } 1254318093Sgonzo path.pop_back(); 1255245803Stheraven} 1256245803Stheraven 1257245803Stheravenvoid 1258245803Stheravendevice_tree::collect_names() 1259245803Stheraven{ 1260245803Stheraven node_path p; 1261289935Stheraven node_names.clear(); 1262289935Stheraven node_paths.clear(); 1263345881Skevans ordered_node_paths.clear(); 1264289935Stheraven cross_references.clear(); 1265318093Sgonzo fixups.clear(); 1266245803Stheraven collect_names_recursive(root, p); 1267245803Stheraven} 1268245803Stheraven 1269328495Skevansproperty_ptr 1270328495Skevansdevice_tree::assign_phandle(node *n, uint32_t &phandle) 1271328495Skevans{ 1272328495Skevans // If there is an existing phandle, use it 1273328495Skevans property_ptr p = n->get_property("phandle"); 1274328495Skevans if (p == 0) 1275328495Skevans { 1276328495Skevans p = n->get_property("linux,phandle"); 1277328495Skevans } 1278328495Skevans if (p == 0) 1279328495Skevans { 1280328495Skevans // Otherwise insert a new phandle node 1281328495Skevans property_value v; 1282328495Skevans while (used_phandles.find(phandle) != used_phandles.end()) 1283328495Skevans { 1284328495Skevans // Note that we only don't need to 1285328495Skevans // store this phandle in the set, 1286328495Skevans // because we are monotonically 1287328495Skevans // increasing the value of phandle and 1288328495Skevans // so will only ever revisit this value 1289328495Skevans // if we have used 2^32 phandles, at 1290328495Skevans // which point our blob won't fit in 1291328495Skevans // any 32-bit system and we've done 1292328495Skevans // something badly wrong elsewhere 1293328495Skevans // already. 1294328495Skevans phandle++; 1295328495Skevans } 1296328495Skevans push_big_endian(v.byte_data, phandle++); 1297328495Skevans if (phandle_node_name == BOTH || phandle_node_name == LINUX) 1298328495Skevans { 1299328495Skevans p.reset(new property("linux,phandle")); 1300328495Skevans p->add_value(v); 1301328495Skevans n->add_property(p); 1302328495Skevans } 1303328495Skevans if (phandle_node_name == BOTH || phandle_node_name == EPAPR) 1304328495Skevans { 1305328495Skevans p.reset(new property("phandle")); 1306328495Skevans p->add_value(v); 1307328495Skevans n->add_property(p); 1308328495Skevans } 1309328495Skevans } 1310328495Skevans 1311328495Skevans return (p); 1312328495Skevans} 1313328495Skevans 1314245803Stheravenvoid 1315328495Skevansdevice_tree::assign_phandles(node_ptr &n, uint32_t &next) 1316245803Stheraven{ 1317328495Skevans if (!n->labels.empty()) 1318328495Skevans { 1319328495Skevans assign_phandle(n.get(), next); 1320328495Skevans } 1321328495Skevans 1322328495Skevans for (auto &c : n->child_nodes()) 1323328495Skevans { 1324328495Skevans assign_phandles(c, next); 1325328495Skevans } 1326328495Skevans} 1327328495Skevans 1328328495Skevansvoid 1329328495Skevansdevice_tree::resolve_cross_references(uint32_t &phandle) 1330328495Skevans{ 1331289935Stheraven for (auto *pv : cross_references) 1332245803Stheraven { 1333245803Stheraven node_path path = node_paths[pv->string_data]; 1334318093Sgonzo auto p = path.begin(); 1335318093Sgonzo auto pe = path.end(); 1336318093Sgonzo if (p != pe) 1337245803Stheraven { 1338318093Sgonzo // Skip the first name in the path. It's always "", and implicitly / 1339318093Sgonzo for (++p ; p!=pe ; ++p) 1340245803Stheraven { 1341318093Sgonzo pv->byte_data.push_back('/'); 1342318093Sgonzo push_string(pv->byte_data, p->first); 1343318093Sgonzo if (!(p->second.empty())) 1344318093Sgonzo { 1345318093Sgonzo pv->byte_data.push_back('@'); 1346318093Sgonzo push_string(pv->byte_data, p->second); 1347318093Sgonzo } 1348245803Stheraven } 1349328495Skevans pv->byte_data.push_back(0); 1350245803Stheraven } 1351245803Stheraven } 1352318093Sgonzo std::unordered_map<property_value*, fixup&> phandle_set; 1353318093Sgonzo for (auto &i : fixups) 1354245803Stheraven { 1355318093Sgonzo phandle_set.insert({&i.val, i}); 1356292876Stheraven } 1357318093Sgonzo std::vector<std::reference_wrapper<fixup>> sorted_phandles; 1358339159Skevans root->visit([&](node &n, node *) { 1359292876Stheraven for (auto &p : n.properties()) 1360292876Stheraven { 1361292876Stheraven for (auto &v : *p) 1362292876Stheraven { 1363318093Sgonzo auto i = phandle_set.find(&v); 1364318093Sgonzo if (i != phandle_set.end()) 1365292876Stheraven { 1366318093Sgonzo sorted_phandles.push_back(i->second); 1367292876Stheraven } 1368292876Stheraven } 1369292876Stheraven } 1370332562Skevans // Allow recursion 1371332562Skevans return node::VISIT_RECURSE; 1372332562Skevans }, nullptr); 1373318093Sgonzo assert(sorted_phandles.size() == fixups.size()); 1374292876Stheraven for (auto &i : sorted_phandles) 1375292876Stheraven { 1376318093Sgonzo string target_name = i.get().val.string_data; 1377318093Sgonzo node *target = nullptr; 1378318093Sgonzo string possible; 1379318093Sgonzo // If the node name is a path, then look it up by following the path, 1380318093Sgonzo // otherwise jump directly to the named node. 1381318093Sgonzo if (target_name[0] == '/') 1382245803Stheraven { 1383318093Sgonzo string path; 1384318093Sgonzo target = root.get(); 1385318093Sgonzo std::istringstream ss(target_name); 1386318093Sgonzo string path_element; 1387318093Sgonzo // Read the leading / 1388318093Sgonzo std::getline(ss, path_element, '/'); 1389318093Sgonzo // Iterate over path elements 1390318093Sgonzo while (!ss.eof()) 1391318093Sgonzo { 1392318093Sgonzo path += '/'; 1393318093Sgonzo std::getline(ss, path_element, '/'); 1394318093Sgonzo std::istringstream nss(path_element); 1395318093Sgonzo string node_name, node_address; 1396318093Sgonzo std::getline(nss, node_name, '@'); 1397318093Sgonzo std::getline(nss, node_address, '@'); 1398318093Sgonzo node *next = nullptr; 1399318093Sgonzo for (auto &c : target->child_nodes()) 1400318093Sgonzo { 1401318093Sgonzo if (c->name == node_name) 1402318093Sgonzo { 1403318093Sgonzo if (c->unit_address == node_address) 1404318093Sgonzo { 1405318093Sgonzo next = c.get(); 1406318093Sgonzo break; 1407318093Sgonzo } 1408318093Sgonzo else 1409318093Sgonzo { 1410318093Sgonzo possible = path + c->name; 1411318093Sgonzo if (c->unit_address != string()) 1412318093Sgonzo { 1413318093Sgonzo possible += '@'; 1414318093Sgonzo possible += c->unit_address; 1415318093Sgonzo } 1416318093Sgonzo } 1417318093Sgonzo } 1418318093Sgonzo } 1419318093Sgonzo path += node_name; 1420318093Sgonzo if (node_address != string()) 1421318093Sgonzo { 1422318093Sgonzo path += '@'; 1423318093Sgonzo path += node_address; 1424318093Sgonzo } 1425318093Sgonzo target = next; 1426318093Sgonzo if (target == nullptr) 1427318093Sgonzo { 1428318093Sgonzo break; 1429318093Sgonzo } 1430318093Sgonzo } 1431245803Stheraven } 1432318093Sgonzo else 1433318093Sgonzo { 1434318093Sgonzo target = node_names[target_name]; 1435318093Sgonzo } 1436318093Sgonzo if (target == nullptr) 1437318093Sgonzo { 1438318093Sgonzo if (is_plugin) 1439318093Sgonzo { 1440318093Sgonzo unresolved_fixups.push_back(i); 1441318093Sgonzo continue; 1442318093Sgonzo } 1443318093Sgonzo else 1444318093Sgonzo { 1445318093Sgonzo fprintf(stderr, "Failed to find node with label: %s\n", target_name.c_str()); 1446318093Sgonzo if (possible != string()) 1447318093Sgonzo { 1448318093Sgonzo fprintf(stderr, "Possible intended match: %s\n", possible.c_str()); 1449318093Sgonzo } 1450318093Sgonzo valid = 0; 1451318093Sgonzo return; 1452318093Sgonzo } 1453318093Sgonzo } 1454245803Stheraven // If there is an existing phandle, use it 1455328495Skevans property_ptr p = assign_phandle(target, phandle); 1456318093Sgonzo p->begin()->push_to_buffer(i.get().val.byte_data); 1457318093Sgonzo assert(i.get().val.byte_data.size() == 4); 1458245803Stheraven } 1459245803Stheraven} 1460245803Stheraven 1461345881Skevansbool 1462345881Skevansdevice_tree::garbage_collect_marked_nodes() 1463345881Skevans{ 1464345881Skevans std::unordered_set<node*> previously_referenced_nodes; 1465345881Skevans std::unordered_set<node*> newly_referenced_nodes; 1466289935Stheraven 1467345881Skevans auto mark_referenced_nodes_used = [&](node &n) 1468345881Skevans { 1469345881Skevans for (auto &p : n.properties()) 1470345881Skevans { 1471345881Skevans for (auto &v : *p) 1472345881Skevans { 1473345881Skevans if (v.is_phandle()) 1474345881Skevans { 1475345881Skevans node *nx = node_names[v.string_data]; 1476345881Skevans if (nx == nullptr) 1477345881Skevans { 1478345881Skevans // Try it again, but as a path 1479345881Skevans for (auto &s : node_paths) 1480345881Skevans { 1481345881Skevans if (v.string_data == s.second.to_string()) 1482345881Skevans { 1483345881Skevans nx = node_names[s.first]; 1484345881Skevans break; 1485345881Skevans } 1486345881Skevans } 1487345881Skevans } 1488345881Skevans if (nx == nullptr) 1489345881Skevans { 1490345881Skevans // Couldn't resolve this one? 1491345881Skevans continue; 1492345881Skevans } 1493345881Skevans // Only mark those currently unmarked 1494345881Skevans if (!nx->used) 1495345881Skevans { 1496345881Skevans nx->used = 1; 1497345881Skevans newly_referenced_nodes.insert(nx); 1498345881Skevans } 1499345881Skevans } 1500345881Skevans } 1501345881Skevans } 1502345881Skevans }; 1503345881Skevans 1504345881Skevans // Seed our referenced nodes with those that have been seen by a node that 1505345881Skevans // either will not be omitted if it's unreferenced or has a symbol. 1506345881Skevans // Nodes with symbols are explicitly not garbage collected because they may 1507345881Skevans // be expected for referencing by an overlay, and we do not want surprises 1508345881Skevans // there. 1509345881Skevans root->visit([&](node &n, node *) { 1510345881Skevans if (!n.omit_if_no_ref || (write_symbols && !n.labels.empty())) 1511345881Skevans { 1512345881Skevans mark_referenced_nodes_used(n); 1513345881Skevans } 1514345881Skevans // Recurse as normal 1515345881Skevans return node::VISIT_RECURSE; 1516345881Skevans }, nullptr); 1517345881Skevans 1518345881Skevans while (!newly_referenced_nodes.empty()) 1519345881Skevans { 1520345881Skevans previously_referenced_nodes = std::move(newly_referenced_nodes); 1521345881Skevans for (auto *n : previously_referenced_nodes) 1522345881Skevans { 1523345881Skevans mark_referenced_nodes_used(*n); 1524345881Skevans } 1525345881Skevans } 1526345881Skevans 1527345881Skevans previously_referenced_nodes.clear(); 1528345881Skevans bool children_deleted = false; 1529345881Skevans 1530345881Skevans // Delete 1531345881Skevans root->visit([&](node &n, node *) { 1532345881Skevans bool gc_children = false; 1533345881Skevans 1534345881Skevans for (auto &cn : n.child_nodes()) 1535345881Skevans { 1536345881Skevans if (cn->omit_if_no_ref && !cn->used) 1537345881Skevans { 1538345881Skevans gc_children = true; 1539345881Skevans break; 1540345881Skevans } 1541345881Skevans } 1542345881Skevans 1543345881Skevans if (gc_children) 1544345881Skevans { 1545345881Skevans children_deleted = true; 1546345881Skevans n.delete_children_if([](node_ptr &nx) { 1547345881Skevans return (nx->omit_if_no_ref && !nx->used); 1548345881Skevans }); 1549345881Skevans 1550345881Skevans return node::VISIT_CONTINUE; 1551345881Skevans } 1552345881Skevans 1553345881Skevans return node::VISIT_RECURSE; 1554345881Skevans }, nullptr); 1555345881Skevans 1556345881Skevans return children_deleted; 1557345881Skevans} 1558345881Skevans 1559292876Stheravenvoid 1560318093Sgonzodevice_tree::parse_file(text_input_buffer &input, 1561292876Stheraven std::vector<node_ptr> &roots, 1562292876Stheraven bool &read_header) 1563292876Stheraven{ 1564292876Stheraven input.next_token(); 1565292876Stheraven // Read the header 1566292876Stheraven if (input.consume("/dts-v1/;")) 1567292876Stheraven { 1568292876Stheraven read_header = true; 1569292876Stheraven } 1570292876Stheraven input.next_token(); 1571318093Sgonzo if (input.consume("/plugin/;")) 1572318093Sgonzo { 1573318093Sgonzo is_plugin = true; 1574318093Sgonzo } 1575292876Stheraven input.next_token(); 1576289935Stheraven if (!read_header) 1577289935Stheraven { 1578289935Stheraven input.parse_error("Expected /dts-v1/; version string"); 1579289935Stheraven } 1580289935Stheraven // Read any memory reservations 1581318093Sgonzo while (input.consume("/memreserve/")) 1582289935Stheraven { 1583289935Stheraven unsigned long long start, len; 1584289935Stheraven input.next_token(); 1585289935Stheraven // Read the start and length. 1586292876Stheraven if (!(input.consume_integer_expression(start) && 1587289935Stheraven (input.next_token(), 1588292876Stheraven input.consume_integer_expression(len)))) 1589289935Stheraven { 1590289935Stheraven input.parse_error("Expected size on /memreserve/ node."); 1591289935Stheraven } 1592358205Skevans else 1593358205Skevans { 1594358205Skevans reservations.push_back(reservation(start, len)); 1595358205Skevans } 1596289935Stheraven input.next_token(); 1597289935Stheraven input.consume(';'); 1598318093Sgonzo input.next_token(); 1599289935Stheraven } 1600289935Stheraven while (valid && !input.finished()) 1601289935Stheraven { 1602289935Stheraven node_ptr n; 1603289935Stheraven if (input.consume('/')) 1604289935Stheraven { 1605289935Stheraven input.next_token(); 1606345881Skevans n = node::parse(input, *this, string(), string_set(), string(), &defines); 1607289935Stheraven } 1608289935Stheraven else if (input.consume('&')) 1609289935Stheraven { 1610289935Stheraven input.next_token(); 1611332562Skevans string name; 1612332562Skevans bool name_is_path_reference = false; 1613332562Skevans // This is to deal with names intended as path references, e.g. &{/path}. 1614332562Skevans // While it may make sense in a non-plugin context, we don't support such 1615332562Skevans // usage at this time. 1616332562Skevans if (input.consume('{') && is_plugin) 1617332562Skevans { 1618332562Skevans name = input.parse_to('}'); 1619332562Skevans input.consume('}'); 1620332562Skevans name_is_path_reference = true; 1621332562Skevans } 1622332562Skevans else 1623332562Skevans { 1624332562Skevans name = input.parse_node_name(); 1625332562Skevans } 1626289935Stheraven input.next_token(); 1627345881Skevans n = node::parse(input, *this, std::move(name), string_set(), string(), &defines); 1628346782Skevans if (n) 1629346782Skevans { 1630346782Skevans n->name_is_path_reference = name_is_path_reference; 1631346782Skevans } 1632289935Stheraven } 1633289935Stheraven else 1634289935Stheraven { 1635289935Stheraven input.parse_error("Failed to find root node /."); 1636289935Stheraven } 1637245803Stheraven if (n) 1638245803Stheraven { 1639289935Stheraven roots.push_back(std::move(n)); 1640245803Stheraven } 1641245803Stheraven else 1642245803Stheraven { 1643245803Stheraven valid = false; 1644245803Stheraven } 1645262394Stheraven input.next_token(); 1646245803Stheraven } 1647245803Stheraven} 1648245803Stheraven 1649245803Stheraventemplate<class writer> void 1650245803Stheravendevice_tree::write(int fd) 1651245803Stheraven{ 1652245803Stheraven dtb::string_table st; 1653245803Stheraven dtb::header head; 1654245803Stheraven writer head_writer; 1655245803Stheraven writer reservation_writer; 1656245803Stheraven writer struct_writer; 1657245803Stheraven writer strings_writer; 1658245803Stheraven 1659245803Stheraven // Build the reservation table 1660245803Stheraven reservation_writer.write_comment(string("Memory reservations")); 1661245803Stheraven reservation_writer.write_label(string("dt_reserve_map")); 1662289935Stheraven for (auto &i : reservations) 1663245803Stheraven { 1664245803Stheraven reservation_writer.write_comment(string("Reservation start")); 1665289935Stheraven reservation_writer.write_data(i.first); 1666245803Stheraven reservation_writer.write_comment(string("Reservation length")); 1667358205Skevans reservation_writer.write_data(i.second); 1668245803Stheraven } 1669245803Stheraven // Write n spare reserve map entries, plus the trailing 0. 1670245803Stheraven for (uint32_t i=0 ; i<=spare_reserve_map_entries ; i++) 1671245803Stheraven { 1672245803Stheraven reservation_writer.write_data((uint64_t)0); 1673245803Stheraven reservation_writer.write_data((uint64_t)0); 1674245803Stheraven } 1675245803Stheraven 1676245803Stheraven 1677245803Stheraven struct_writer.write_comment(string("Device tree")); 1678245803Stheraven struct_writer.write_label(string("dt_struct_start")); 1679245803Stheraven root->write(struct_writer, st); 1680245803Stheraven struct_writer.write_token(dtb::FDT_END); 1681245803Stheraven struct_writer.write_label(string("dt_struct_end")); 1682245803Stheraven 1683245803Stheraven st.write(strings_writer); 1684245803Stheraven // Find the strings size before we stick padding on the end. 1685245803Stheraven // Note: We should possibly use a new writer for the padding. 1686245803Stheraven head.size_dt_strings = strings_writer.size(); 1687245803Stheraven 1688245803Stheraven // Stick the padding in the strings writer, but after the 1689245803Stheraven // marker indicating that it's the end. 1690245803Stheraven // Note: We probably should add a padding call to the writer so 1691245803Stheraven // that the asm back end can write padding directives instead 1692245803Stheraven // of a load of 0 bytes. 1693245803Stheraven for (uint32_t i=0 ; i<blob_padding ; i++) 1694245803Stheraven { 1695245803Stheraven strings_writer.write_data((uint8_t)0); 1696245803Stheraven } 1697245803Stheraven head.totalsize = sizeof(head) + strings_writer.size() + 1698245803Stheraven struct_writer.size() + reservation_writer.size(); 1699245803Stheraven while (head.totalsize < minimum_blob_size) 1700245803Stheraven { 1701245803Stheraven head.totalsize++; 1702245803Stheraven strings_writer.write_data((uint8_t)0); 1703245803Stheraven } 1704245803Stheraven head.off_dt_struct = sizeof(head) + reservation_writer.size();; 1705245803Stheraven head.off_dt_strings = head.off_dt_struct + struct_writer.size(); 1706245803Stheraven head.off_mem_rsvmap = sizeof(head); 1707245803Stheraven head.boot_cpuid_phys = boot_cpu; 1708245803Stheraven head.size_dt_struct = struct_writer.size(); 1709245803Stheraven head.write(head_writer); 1710245803Stheraven 1711245803Stheraven head_writer.write_to_file(fd); 1712245803Stheraven reservation_writer.write_to_file(fd); 1713245803Stheraven struct_writer.write_to_file(fd); 1714245803Stheraven strings_writer.write_label(string("dt_blob_end")); 1715245803Stheraven strings_writer.write_to_file(fd); 1716245803Stheraven} 1717245803Stheraven 1718245803Stheravennode* 1719245803Stheravendevice_tree::referenced_node(property_value &v) 1720245803Stheraven{ 1721245803Stheraven if (v.is_phandle()) 1722245803Stheraven { 1723245803Stheraven return node_names[v.string_data]; 1724245803Stheraven } 1725245803Stheraven if (v.is_binary()) 1726245803Stheraven { 1727245803Stheraven return used_phandles[v.get_as_uint32()]; 1728245803Stheraven } 1729245803Stheraven return 0; 1730245803Stheraven} 1731245803Stheraven 1732245803Stheravenvoid 1733245803Stheravendevice_tree::write_binary(int fd) 1734245803Stheraven{ 1735245803Stheraven write<dtb::binary_writer>(fd); 1736245803Stheraven} 1737245803Stheraven 1738245803Stheravenvoid 1739245803Stheravendevice_tree::write_asm(int fd) 1740245803Stheraven{ 1741245803Stheraven write<dtb::asm_writer>(fd); 1742245803Stheraven} 1743245803Stheraven 1744245803Stheravenvoid 1745245803Stheravendevice_tree::write_dts(int fd) 1746245803Stheraven{ 1747245803Stheraven FILE *file = fdopen(fd, "w"); 1748259249Stheraven fputs("/dts-v1/;\n\n", file); 1749245803Stheraven 1750245803Stheraven if (!reservations.empty()) 1751245803Stheraven { 1752245803Stheraven const char msg[] = "/memreserve/"; 1753358205Skevans // Exclude the null byte when we're writing it out to the file. 1754358205Skevans fwrite(msg, sizeof(msg) - 1, 1, file); 1755289935Stheraven for (auto &i : reservations) 1756245803Stheraven { 1757358205Skevans fprintf(file, " 0x%" PRIx64 " 0x%" PRIx64, i.first, i.second); 1758245803Stheraven } 1759245803Stheraven fputs(";\n\n", file); 1760245803Stheraven } 1761245803Stheraven putc('/', file); 1762245803Stheraven putc(' ', file); 1763245803Stheraven root->write_dts(file, 0); 1764245803Stheraven fclose(file); 1765245803Stheraven} 1766245803Stheraven 1767245803Stheravenvoid 1768318093Sgonzodevice_tree::parse_dtb(const string &fn, FILE *) 1769245803Stheraven{ 1770318093Sgonzo auto in = input_buffer::buffer_for_file(fn); 1771245803Stheraven if (in == 0) 1772245803Stheraven { 1773245803Stheraven valid = false; 1774245803Stheraven return; 1775245803Stheraven } 1776245803Stheraven input_buffer &input = *in; 1777245803Stheraven dtb::header h; 1778245803Stheraven valid = h.read_dtb(input); 1779245803Stheraven boot_cpu = h.boot_cpuid_phys; 1780245803Stheraven if (h.last_comp_version > 17) 1781245803Stheraven { 1782245803Stheraven fprintf(stderr, "Don't know how to read this version of the device tree blob"); 1783245803Stheraven valid = false; 1784245803Stheraven } 1785245803Stheraven if (!valid) 1786245803Stheraven { 1787245803Stheraven return; 1788245803Stheraven } 1789245803Stheraven input_buffer reservation_map = 1790245803Stheraven input.buffer_from_offset(h.off_mem_rsvmap, 0); 1791245803Stheraven uint64_t start, length; 1792245803Stheraven do 1793245803Stheraven { 1794245803Stheraven if (!(reservation_map.consume_binary(start) && 1795245803Stheraven reservation_map.consume_binary(length))) 1796245803Stheraven { 1797245803Stheraven fprintf(stderr, "Failed to read memory reservation table\n"); 1798245803Stheraven valid = false; 1799245803Stheraven return; 1800245803Stheraven } 1801358205Skevans if (start != 0 || length != 0) 1802358205Skevans { 1803358205Skevans reservations.push_back(reservation(start, length)); 1804358205Skevans } 1805245803Stheraven } while (!((start == 0) && (length == 0))); 1806245803Stheraven input_buffer struct_table = 1807245803Stheraven input.buffer_from_offset(h.off_dt_struct, h.size_dt_struct); 1808245803Stheraven input_buffer strings_table = 1809245803Stheraven input.buffer_from_offset(h.off_dt_strings, h.size_dt_strings); 1810245803Stheraven uint32_t token; 1811245803Stheraven if (!(struct_table.consume_binary(token) && 1812245803Stheraven (token == dtb::FDT_BEGIN_NODE))) 1813245803Stheraven { 1814245803Stheraven fprintf(stderr, "Expected FDT_BEGIN_NODE token.\n"); 1815245803Stheraven valid = false; 1816245803Stheraven return; 1817245803Stheraven } 1818245803Stheraven root = node::parse_dtb(struct_table, strings_table); 1819245803Stheraven if (!(struct_table.consume_binary(token) && (token == dtb::FDT_END))) 1820245803Stheraven { 1821245803Stheraven fprintf(stderr, "Expected FDT_END token after parsing root node.\n"); 1822245803Stheraven valid = false; 1823245803Stheraven return; 1824245803Stheraven } 1825245803Stheraven valid = (root != 0); 1826245803Stheraven} 1827245803Stheraven 1828318093Sgonzostring 1829318093Sgonzodevice_tree::node_path::to_string() const 1830318093Sgonzo{ 1831318093Sgonzo string path; 1832318093Sgonzo auto p = begin(); 1833318093Sgonzo auto pe = end(); 1834318093Sgonzo if ((p == pe) || (p+1 == pe)) 1835318093Sgonzo { 1836318093Sgonzo return string("/"); 1837318093Sgonzo } 1838318093Sgonzo // Skip the first name in the path. It's always "", and implicitly / 1839318093Sgonzo for (++p ; p!=pe ; ++p) 1840318093Sgonzo { 1841318093Sgonzo path += '/'; 1842318093Sgonzo path += p->first; 1843318093Sgonzo if (!(p->second.empty())) 1844318093Sgonzo { 1845318093Sgonzo path += '@'; 1846318093Sgonzo path += p->second; 1847318093Sgonzo } 1848318093Sgonzo } 1849318093Sgonzo return path; 1850318093Sgonzo} 1851318093Sgonzo 1852328495Skevansnode_ptr 1853328495Skevansdevice_tree::create_fragment_wrapper(node_ptr &node, int &fragnum) 1854328495Skevans{ 1855328495Skevans // In a plugin, we can massage these non-/ root nodes into into a fragment 1856328495Skevans std::string fragment_address = "fragment@" + std::to_string(fragnum); 1857328495Skevans ++fragnum; 1858328495Skevans 1859328495Skevans std::vector<property_ptr> symbols; 1860328495Skevans 1861328495Skevans // Intentionally left empty 1862328495Skevans node_ptr newroot = node::create_special_node("", symbols); 1863328495Skevans node_ptr wrapper = node::create_special_node("__overlay__", symbols); 1864328495Skevans 1865332562Skevans // Generate the fragment with $propname = <&name> 1866328495Skevans property_value v; 1867332562Skevans std::string propname; 1868328495Skevans v.string_data = node->name; 1869332562Skevans if (!node->name_is_path_reference) 1870332562Skevans { 1871332562Skevans propname = "target"; 1872332562Skevans v.type = property_value::PHANDLE; 1873332562Skevans } 1874332562Skevans else 1875332562Skevans { 1876332562Skevans propname = "target-path"; 1877332562Skevans v.type = property_value::STRING; 1878332562Skevans } 1879332562Skevans auto prop = std::make_shared<property>(std::string(propname)); 1880328495Skevans prop->add_value(v); 1881328495Skevans symbols.push_back(prop); 1882328495Skevans 1883328495Skevans node_ptr fragment = node::create_special_node(fragment_address, symbols); 1884328495Skevans 1885328495Skevans wrapper->merge_node(node); 1886328495Skevans fragment->add_child(std::move(wrapper)); 1887328495Skevans newroot->add_child(std::move(fragment)); 1888328495Skevans return newroot; 1889328495Skevans} 1890328495Skevans 1891328495Skevansnode_ptr 1892328495Skevansdevice_tree::generate_root(node_ptr &node, int &fragnum) 1893328495Skevans{ 1894328495Skevans 1895328495Skevans string name = node->name; 1896328495Skevans if (name == string()) 1897328495Skevans { 1898328495Skevans return std::move(node); 1899328495Skevans } 1900328495Skevans else if (!is_plugin) 1901328495Skevans { 1902328495Skevans return nullptr; 1903328495Skevans } 1904328495Skevans 1905328495Skevans return create_fragment_wrapper(node, fragnum); 1906328495Skevans} 1907328495Skevans 1908245803Stheravenvoid 1909328495Skevansdevice_tree::reassign_fragment_numbers(node_ptr &node, int &delta) 1910328495Skevans{ 1911328495Skevans 1912328495Skevans for (auto &c : node->child_nodes()) 1913328495Skevans { 1914328495Skevans if (c->name == std::string("fragment")) 1915328495Skevans { 1916328495Skevans int current_address = std::stoi(c->unit_address, nullptr, 16); 1917328495Skevans std::ostringstream new_address; 1918328495Skevans current_address += delta; 1919328495Skevans // It's possible that we hopped more than one somewhere, so just reset 1920328495Skevans // delta to the next in sequence. 1921328495Skevans delta = current_address + 1; 1922328495Skevans new_address << std::hex << current_address; 1923328495Skevans c->unit_address = new_address.str(); 1924328495Skevans } 1925328495Skevans } 1926328495Skevans} 1927328495Skevans 1928328495Skevansvoid 1929318093Sgonzodevice_tree::parse_dts(const string &fn, FILE *depfile) 1930245803Stheraven{ 1931318093Sgonzo auto in = input_buffer::buffer_for_file(fn); 1932318093Sgonzo if (!in) 1933245803Stheraven { 1934245803Stheraven valid = false; 1935245803Stheraven return; 1936245803Stheraven } 1937289935Stheraven std::vector<node_ptr> roots; 1938318093Sgonzo std::unordered_set<string> defnames; 1939318093Sgonzo for (auto &i : defines) 1940318093Sgonzo { 1941318093Sgonzo defnames.insert(i.first); 1942318093Sgonzo } 1943318093Sgonzo text_input_buffer input(std::move(in), 1944318093Sgonzo std::move(defnames), 1945318093Sgonzo std::vector<string>(include_paths), 1946318093Sgonzo dirname(fn), 1947318093Sgonzo depfile); 1948245803Stheraven bool read_header = false; 1949328495Skevans int fragnum = 0; 1950318093Sgonzo parse_file(input, roots, read_header); 1951245803Stheraven switch (roots.size()) 1952245803Stheraven { 1953245803Stheraven case 0: 1954245803Stheraven valid = false; 1955245803Stheraven input.parse_error("Failed to find root node /."); 1956245803Stheraven return; 1957245803Stheraven case 1: 1958328495Skevans root = generate_root(roots[0], fragnum); 1959328495Skevans if (!root) 1960328495Skevans { 1961328495Skevans valid = false; 1962328495Skevans input.parse_error("Failed to find root node /."); 1963328495Skevans return; 1964328495Skevans } 1965245803Stheraven break; 1966245803Stheraven default: 1967245803Stheraven { 1968328495Skevans root = generate_root(roots[0], fragnum); 1969328495Skevans if (!root) 1970328495Skevans { 1971328495Skevans valid = false; 1972328495Skevans input.parse_error("Failed to find root node /."); 1973328495Skevans return; 1974328495Skevans } 1975289935Stheraven for (auto i=++(roots.begin()), e=roots.end() ; i!=e ; ++i) 1976245803Stheraven { 1977289935Stheraven auto &node = *i; 1978289935Stheraven string name = node->name; 1979289935Stheraven if (name == string()) 1980289935Stheraven { 1981328495Skevans if (is_plugin) 1982328495Skevans { 1983328495Skevans // Re-assign any fragment numbers based on a delta of 1984328495Skevans // fragnum before we merge it 1985328495Skevans reassign_fragment_numbers(node, fragnum); 1986328495Skevans } 1987328495Skevans root->merge_node(node); 1988289935Stheraven } 1989289935Stheraven else 1990289935Stheraven { 1991289935Stheraven auto existing = node_names.find(name); 1992289935Stheraven if (existing == node_names.end()) 1993289935Stheraven { 1994289935Stheraven collect_names(); 1995289935Stheraven existing = node_names.find(name); 1996289935Stheraven } 1997289935Stheraven if (existing == node_names.end()) 1998289935Stheraven { 1999328495Skevans if (is_plugin) 2000328495Skevans { 2001328495Skevans auto fragment = create_fragment_wrapper(node, fragnum); 2002328495Skevans root->merge_node(fragment); 2003328495Skevans } 2004328495Skevans else 2005328495Skevans { 2006328495Skevans fprintf(stderr, "Unable to merge node: %s\n", name.c_str()); 2007328495Skevans } 2008289935Stheraven } 2009318093Sgonzo else 2010318093Sgonzo { 2011328495Skevans existing->second->merge_node(node); 2012318093Sgonzo } 2013289935Stheraven } 2014245803Stheraven } 2015245803Stheraven } 2016245803Stheraven } 2017245803Stheraven collect_names(); 2018345881Skevans // Return value indicates whether we've dirtied the tree or not and need to 2019345881Skevans // recollect names 2020345881Skevans if (garbage_collect && garbage_collect_marked_nodes()) 2021345881Skevans { 2022345881Skevans collect_names(); 2023345881Skevans } 2024328495Skevans uint32_t phandle = 1; 2025328495Skevans // If we're writing symbols, go ahead and assign phandles to the entire 2026328495Skevans // tree. We'll do this before we resolve cross references, just to keep 2027328495Skevans // order semi-predictable and stable. 2028318093Sgonzo if (write_symbols) 2029318093Sgonzo { 2030328495Skevans assign_phandles(root, phandle); 2031328495Skevans } 2032328495Skevans resolve_cross_references(phandle); 2033328495Skevans if (write_symbols) 2034328495Skevans { 2035318093Sgonzo std::vector<property_ptr> symbols; 2036318093Sgonzo // Create a symbol table. Each label in this device tree may be 2037318093Sgonzo // referenced by other plugins, so we create a __symbols__ node inside 2038318093Sgonzo // the root that contains mappings (properties) from label names to 2039318093Sgonzo // paths. 2040345881Skevans for (auto i=ordered_node_paths.rbegin(), e=ordered_node_paths.rend() ; i!=e ; ++i) 2041318093Sgonzo { 2042345881Skevans auto &s = *i; 2043345881Skevans if (node_paths.find(s.first) == node_paths.end()) 2044345881Skevans { 2045345881Skevans // Erased node, skip it. 2046345881Skevans continue; 2047345881Skevans } 2048318093Sgonzo property_value v; 2049318093Sgonzo v.string_data = s.second.to_string(); 2050318093Sgonzo v.type = property_value::STRING; 2051318093Sgonzo string name = s.first; 2052318093Sgonzo auto prop = std::make_shared<property>(std::move(name)); 2053318093Sgonzo prop->add_value(v); 2054318093Sgonzo symbols.push_back(prop); 2055318093Sgonzo } 2056318093Sgonzo root->add_child(node::create_special_node("__symbols__", symbols)); 2057339159Skevans } 2058339159Skevans // If this is a plugin, then we also need to create two extra nodes. 2059339159Skevans // Internal phandles will need to be renumbered to avoid conflicts with 2060339159Skevans // already-loaded nodes and external references will need to be 2061339159Skevans // resolved. 2062339159Skevans if (is_plugin) 2063339159Skevans { 2064339159Skevans std::vector<property_ptr> symbols; 2065339159Skevans // Create the fixups entry. This is of the form: 2066339159Skevans // {target} = {path}:{property name}:{offset} 2067339159Skevans auto create_fixup_entry = [&](fixup &i, string target) 2068339159Skevans { 2069339159Skevans string value = i.path.to_string(); 2070339159Skevans value += ':'; 2071339159Skevans value += i.prop->get_key(); 2072339159Skevans value += ':'; 2073339159Skevans value += std::to_string(i.prop->offset_of_value(i.val)); 2074339159Skevans property_value v; 2075339159Skevans v.string_data = value; 2076339159Skevans v.type = property_value::STRING; 2077339159Skevans auto prop = std::make_shared<property>(std::move(target)); 2078339159Skevans prop->add_value(v); 2079339159Skevans return prop; 2080339159Skevans }; 2081339159Skevans // If we have any unresolved phandle references in this plugin, 2082339159Skevans // then we must update them to 0xdeadbeef and leave a property in 2083339159Skevans // the /__fixups__ node whose key is the label and whose value is 2084339159Skevans // as described above. 2085339159Skevans if (!unresolved_fixups.empty()) 2086318093Sgonzo { 2087339159Skevans for (auto &i : unresolved_fixups) 2088318093Sgonzo { 2089339159Skevans auto &val = i.get().val; 2090339159Skevans symbols.push_back(create_fixup_entry(i, val.string_data)); 2091339159Skevans val.byte_data.push_back(0xde); 2092339159Skevans val.byte_data.push_back(0xad); 2093339159Skevans val.byte_data.push_back(0xbe); 2094339159Skevans val.byte_data.push_back(0xef); 2095339159Skevans val.type = property_value::BINARY; 2096318093Sgonzo } 2097339159Skevans root->add_child(node::create_special_node("__fixups__", symbols)); 2098339159Skevans } 2099339159Skevans symbols.clear(); 2100339159Skevans // If we have any resolved phandle references in this plugin, then 2101339159Skevans // we must create a child in the __local_fixups__ node whose path 2102339159Skevans // matches the node path from the root and whose value contains the 2103339159Skevans // location of the reference within a property. 2104339159Skevans 2105339159Skevans // Create a local_fixups node that is initially empty. 2106339159Skevans node_ptr local_fixups = node::create_special_node("__local_fixups__", symbols); 2107339159Skevans for (auto &i : fixups) 2108339159Skevans { 2109339159Skevans if (!i.val.is_phandle()) 2110318093Sgonzo { 2111339159Skevans continue; 2112339159Skevans } 2113339159Skevans node *n = local_fixups.get(); 2114339159Skevans for (auto &p : i.path) 2115339159Skevans { 2116339159Skevans // Skip the implicit root 2117339159Skevans if (p.first.empty()) 2118318093Sgonzo { 2119318093Sgonzo continue; 2120318093Sgonzo } 2121339159Skevans bool found = false; 2122339159Skevans for (auto &c : n->child_nodes()) 2123328495Skevans { 2124339159Skevans if (c->name == p.first) 2125328495Skevans { 2126345881Skevans if (c->unit_address == p.second) 2127328495Skevans { 2128345881Skevans n = c.get(); 2129345881Skevans found = true; 2130345881Skevans break; 2131328495Skevans } 2132328495Skevans } 2133328495Skevans } 2134339159Skevans if (!found) 2135328495Skevans { 2136345881Skevans string path = p.first; 2137345881Skevans if (!(p.second.empty())) 2138345881Skevans { 2139345881Skevans path += '@'; 2140345881Skevans path += p.second; 2141345881Skevans } 2142345881Skevans n->add_child(node::create_special_node(path, symbols)); 2143339159Skevans n = (--n->child_end())->get(); 2144328495Skevans } 2145339159Skevans } 2146339159Skevans assert(n); 2147339159Skevans property_value pv; 2148339159Skevans push_big_endian(pv.byte_data, static_cast<uint32_t>(i.prop->offset_of_value(i.val))); 2149339159Skevans pv.type = property_value::BINARY; 2150339159Skevans auto key = i.prop->get_key(); 2151339159Skevans property_ptr prop = n->get_property(key); 2152339159Skevans // If we don't have an existing property then create one and 2153339159Skevans // use this property value 2154339159Skevans if (!prop) 2155339159Skevans { 2156339159Skevans prop = std::make_shared<property>(std::move(key)); 2157339159Skevans n->add_property(prop); 2158339159Skevans prop->add_value(pv); 2159339159Skevans } 2160339159Skevans else 2161339159Skevans { 2162339159Skevans // If we do have an existing property value, try to append 2163339159Skevans // this value. 2164339159Skevans property_value &old_val = *(--prop->end()); 2165339159Skevans if (!old_val.try_to_merge(pv)) 2166328495Skevans { 2167339159Skevans prop->add_value(pv); 2168328495Skevans } 2169318093Sgonzo } 2170318093Sgonzo } 2171339159Skevans // We've iterated over all fixups, but only emit the 2172339159Skevans // __local_fixups__ if we found some that were resolved internally. 2173339159Skevans if (local_fixups->child_begin() != local_fixups->child_end()) 2174339159Skevans { 2175339159Skevans root->add_child(std::move(local_fixups)); 2176339159Skevans } 2177318093Sgonzo } 2178245803Stheraven} 2179245803Stheraven 2180254522Stheravenbool device_tree::parse_define(const char *def) 2181254522Stheraven{ 2182310808Sdim const char *val = strchr(def, '='); 2183254522Stheraven if (!val) 2184254522Stheraven { 2185254522Stheraven if (strlen(def) != 0) 2186254522Stheraven { 2187254522Stheraven string name(def); 2188254522Stheraven defines[name]; 2189254522Stheraven return true; 2190254522Stheraven } 2191254522Stheraven return false; 2192254522Stheraven } 2193254522Stheraven string name(def, val-def); 2194318093Sgonzo string name_copy = name; 2195254522Stheraven val++; 2196318093Sgonzo std::unique_ptr<input_buffer> raw(new input_buffer(val, strlen(val))); 2197318093Sgonzo text_input_buffer in(std::move(raw), 2198318093Sgonzo std::unordered_set<string>(), 2199318093Sgonzo std::vector<string>(), 2200318093Sgonzo string(), 2201318093Sgonzo nullptr); 2202318093Sgonzo property_ptr p = property::parse(in, std::move(name_copy), string_set(), false); 2203254522Stheraven if (p) 2204254522Stheraven defines[name] = p; 2205289935Stheraven return (bool)p; 2206254522Stheraven} 2207254522Stheraven 2208245803Stheraven} // namespace fdt 2209245803Stheraven 2210245803Stheraven} // namespace dtc 2211245803Stheraven 2212