1/* 2 * Copyright 2019, Data61 3 * Commonwealth Scientific and Industrial Research Organisation (CSIRO) 4 * ABN 41 687 119 230. 5 * 6 * This software may be distributed and modified according to the terms of 7 * the BSD 2-Clause license. Note that NO WARRANTY is provided. 8 * See "LICENSE_BSD2.txt" for details. 9 * 10 * @TAG(DATA61_BSD) 11 */ 12 13#include <stdio.h> 14#include <stdbool.h> 15 16#include <libfdt.h> 17#include <utils/list.h> 18#include <utils/util.h> 19#include <utils/uthash.h> 20#include <fdtgen.h> 21 22#define MAX_FULL_PATH_LENGTH (4096) 23 24enum device_flag { 25 DEVICE_KEEP = 1, 26 DEVICE_KEEP_AND_DISABLE = 2, 27}; 28 29typedef struct { 30 char *name; 31 int offset; 32 int cnt; 33 enum device_flag flag; 34 UT_hash_handle hh; 35} path_node_t; 36 37static const char *props_with_dep[] = {"phy-handle", "next-level-cache", "interrupt-parent", "interrupts-extended", "clocks", "power-domains"}; 38static const int num_props_with_dep = sizeof(props_with_dep) / sizeof(char *); 39 40typedef struct { 41 char *to_path; 42 uint32_t to_phandle; 43} d_list_node_t; 44 45static int dnode_cmp(void *_a, void *_b) 46{ 47 d_list_node_t *a = _a, *b = _b; 48 return strcmp(a->to_path, b->to_path); 49} 50 51typedef struct { 52 char *from_path; 53 list_t *to_list; 54 UT_hash_handle hh; 55} dependency_t; 56 57struct fdtgen_context { 58 path_node_t *nodes_table; 59 dependency_t *dep_table; 60 int root_offset; 61 void *buffer; 62 int bufsize; 63 char *string_buf; 64}; 65typedef struct fdtgen_context fdtgen_context_t; 66 67static void init_keep_node(fdtgen_context_t *handle, const char **nodes, int num_nodes, enum device_flag flag) 68{ 69 for (int i = 0; i < num_nodes; ++i) { 70 path_node_t *this = NULL; 71 HASH_FIND_STR(handle->nodes_table, nodes[i], this); 72 if (this == NULL) { 73 path_node_t *new = malloc(sizeof(path_node_t)); 74 new->name = strdup(nodes[i]); 75 new->flag = flag; 76 new->cnt = 0; 77 HASH_ADD_STR(handle->nodes_table, name, new); 78 } else { 79 this->flag = flag; 80 } 81 } 82} 83 84static int is_to_keep(fdtgen_context_t *handle, UNUSED int child) 85{ 86 void *dtb = handle->buffer; 87 path_node_t *this; 88 HASH_FIND_STR(handle->nodes_table, handle->string_buf, this); 89 90 return this != NULL; 91} 92 93static int retrive_to_phandle(const void *prop_data, int lenp) 94{ 95 uint32_t handle = fdt32_ld(prop_data); 96 return handle; 97} 98 99static void register_node_dependencies(fdtgen_context_t *handle, int offset); 100 101static int keep_node_and_parents(fdtgen_context_t *handle, int offset, int target) 102{ 103 void *dtb = handle->buffer; 104 if (target == handle->root_offset) { 105 return 0; 106 } 107 if (target == offset) { 108 return 1; 109 } 110 int child; 111 112 fdt_for_each_subnode(child, dtb, offset) { 113 int new_len = strlen(handle->string_buf); 114 strcat(handle->string_buf, "/"); 115 const char *n = fdt_get_name(dtb, child, NULL); 116 strcat(handle->string_buf, n); 117 char *curr = strdup(handle->string_buf); 118 119 int keep = keep_node_and_parents(handle, child, target); 120 if (keep) { 121 path_node_t *target_node = NULL; 122 HASH_FIND_STR(handle->nodes_table, curr, target_node); 123 if (target_node == NULL) { 124 target_node = malloc(sizeof(path_node_t)); 125 target_node->name = strdup(curr); 126 target_node->offset = offset; 127 target_node->cnt = 0; 128 target_node->flag = DEVICE_KEEP; 129 HASH_ADD_STR(handle->nodes_table, name, target_node); 130 } 131 132 dependency_t *dep; 133 HASH_FIND_STR(handle->dep_table, curr, dep); 134 if (dep == NULL) { 135 register_node_dependencies(handle, child); 136 } 137 handle->string_buf[new_len] = '\0'; 138 return 1; 139 } 140 141 handle->string_buf[new_len] = '\0'; 142 free(curr); 143 } 144 145 return 0; 146} 147 148static void register_single_dependency(fdtgen_context_t *handle, int offset, int lenp, const void *data, 149 dependency_t *this) 150{ 151 void *dtb = handle->buffer; 152 d_list_node_t *new_node = malloc(sizeof(d_list_node_t)); 153 uint32_t to_phandle = retrive_to_phandle(data, lenp); 154 int off = fdt_node_offset_by_phandle(dtb, to_phandle); 155 fdt_get_path(dtb, off, handle->string_buf, MAX_FULL_PATH_LENGTH); 156 new_node->to_path = strdup(handle->string_buf); 157 new_node->to_phandle = to_phandle; 158 159 // it is the same node when it refers to itself 160 if (offset == off || list_exists(this->to_list, new_node, dnode_cmp)) { 161 free(new_node->to_path); 162 free(new_node); 163 } else { 164 list_append(this->to_list, new_node); 165 handle->string_buf[0] = '\0'; 166 keep_node_and_parents(handle, handle->root_offset, off); 167 register_node_dependencies(handle, off); 168 } 169} 170 171static void register_clocks_dependency(fdtgen_context_t *handle, int offset, int lenp, const void *data_, 172 dependency_t *this) 173{ 174 void *dtb = handle->buffer; 175 const void *data = data_; 176 int done = 0; 177 while (lenp > done) { 178 data = (data_ + done); 179 int phandle = fdt32_ld(data); 180 int refers_to = fdt_node_offset_by_phandle(dtb, phandle); 181 int len; 182 const void *clock_cells = fdt_getprop(dtb, refers_to, "#clock-cells", &len); 183 int cells = fdt32_ld(clock_cells); 184 185 register_single_dependency(handle, offset, lenp, data, this); 186 187 done += 4 + cells * 4; 188 } 189} 190 191static void register_power_domains_dependency(fdtgen_context_t *handle, int offset, int lenp, const void *data_, 192 dependency_t *this) 193{ 194 void *dtb = handle->buffer; 195 const void *data = data_; 196 int done = 0; 197 while (lenp > done) { 198 data = (data_ + done); 199 register_single_dependency(handle, offset, lenp, data, this); 200 done += 4; 201 } 202} 203 204static void register_node_dependency(fdtgen_context_t *handle, int offset, const char *type, int p_offset) 205{ 206 void *dtb = handle->buffer; 207 int lenp = 0; 208 const void *data = fdt_getprop_by_offset(dtb, p_offset, NULL, &lenp); 209 fdt_get_path(dtb, offset, handle->string_buf, MAX_FULL_PATH_LENGTH); 210 dependency_t *this = NULL; 211 HASH_FIND_STR(handle->dep_table, handle->string_buf, this); 212 213 if (this == NULL) { 214 dependency_t *new = malloc(sizeof(dependency_t)); 215 new->from_path = strdup(handle->string_buf); 216 new->to_list = malloc(sizeof(list_t)); 217 list_init(new->to_list); 218 this = new; 219 HASH_ADD_STR(handle->dep_table, from_path, this); 220 } 221 222 if (strcmp(type, "clocks") == 0) { 223 register_clocks_dependency(handle, offset, lenp, data, this); 224 } else if (strcmp(type, "power-domains") == 0) { 225 register_power_domains_dependency(handle, offset, lenp, data, this); 226 } else { 227 register_single_dependency(handle, offset, lenp, data, this); 228 } 229} 230 231static void register_node_dependencies(fdtgen_context_t *handle, int offset) 232{ 233 if (offset == handle->root_offset) { 234 return; 235 } 236 int prop_off, lenp; 237 void *dtb = handle->buffer; 238 239 fdt_for_each_property_offset(prop_off, dtb, offset) { 240 const struct fdt_property *prop = fdt_get_property_by_offset(dtb, prop_off, NULL); 241 const char *name = fdt_get_string(dtb, fdt32_ld(&prop->nameoff), &lenp); 242 for (int i = 0; i < num_props_with_dep; i++) { 243 if (strcmp(name, props_with_dep[i]) == 0) { 244 register_node_dependency(handle, offset, name, prop_off); 245 } 246 } 247 } 248} 249 250static void resolve_all_dependencies(fdtgen_context_t *handle) 251{ 252 path_node_t *tmp, *el; 253 HASH_ITER(hh, handle->nodes_table, el, tmp) { 254 register_node_dependencies(handle, el->offset); 255 } 256} 257 258/* 259 * prefix traverse the device tree 260 * keep the parent if the child is kept 261 */ 262static int find_nodes_to_keep(fdtgen_context_t *handle, int offset) 263{ 264 void *dtb = handle->buffer; 265 int child; 266 int find = 0; 267 268 fdt_for_each_subnode(child, dtb, offset) { 269 int len_ori = strlen(handle->string_buf); 270 strcat(handle->string_buf, "/"); 271 const char *n = fdt_get_name(dtb, child, NULL); 272 strcat(handle->string_buf, n); 273 274 int child_is_kept = find_nodes_to_keep(handle, child); 275 int in_keep_list = 0; 276 if (child_is_kept == 0) { 277 in_keep_list = is_to_keep(handle, child); 278 } 279 280 if (in_keep_list || child_is_kept) { 281 find = 1; 282 path_node_t *this; 283 HASH_FIND_STR(handle->nodes_table, handle->string_buf, this); 284 285 if (this == NULL) { /* this is not in the keep list */ 286 path_node_t *new = malloc(sizeof(path_node_t)); 287 new->offset = child; 288 new->name = strdup(handle->string_buf); 289 new->cnt = 0; 290 new->flag = DEVICE_KEEP; 291 HASH_ADD_STR(handle->nodes_table, name, new); 292 } else { 293 this->offset = child; 294 } 295 } 296 297 handle->string_buf[len_ori] = '\0'; 298 } 299 300 return find; 301} 302 303static void trim_tree(fdtgen_context_t *handle, int offset) 304{ 305 int child; 306 void *dtb = handle->buffer; 307 308 fdt_for_each_subnode(child, dtb, offset) { 309 int len_ori = strlen(handle->string_buf); 310 const char *n = fdt_get_name(dtb, child, NULL); 311 strcat(handle->string_buf, "/"); 312 strcat(handle->string_buf, n); 313 path_node_t *this; 314 315 HASH_FIND_STR(handle->nodes_table, handle->string_buf, this); 316 if (this == NULL) { 317 int err = fdt_del_node(dtb, child); 318 ZF_LOGF_IF(err != 0, "Failed to delete a node from device tree"); 319 /* NOTE: after deleting a node, all the offsets are invalidated, 320 * we need to repeat this triming process for the same node if 321 * we don't want to miss anything */ 322 handle->string_buf[len_ori] = '\0'; 323 trim_tree(handle, offset); 324 return; 325 } else { 326 this->cnt++; 327 328 if (this->flag == DEVICE_KEEP_AND_DISABLE && this->cnt == 1) { 329 int err = fdt_setprop_string(dtb, child, "status", "disabled"); 330 ZF_LOGF_IF(err, "failed, %d", err); 331 handle->string_buf[len_ori] = '\0'; 332 trim_tree(handle, offset); 333 return; 334 } else { 335 trim_tree(handle, child); 336 } 337 } 338 handle->string_buf[len_ori] = '\0'; 339 } 340} 341 342static void free_list(list_t *l) 343{ 344 struct list_node *a = l->head; 345 while (a != NULL) { 346 struct list_node *next = a->next; 347 d_list_node_t *node = a->data; 348 free(node->to_path); 349 free(node); 350 a = next; 351 } 352 353 list_remove_all(l); 354} 355 356static void clean_up(fdtgen_context_t *handle) 357{ 358 dependency_t *tmp, *el; 359 HASH_ITER(hh, handle->dep_table, el, tmp) { 360 HASH_DEL(handle->dep_table, el); 361 free_list(el->to_list); 362 free(el->to_list); 363 free(el->from_path); 364 free(el); 365 } 366 367 path_node_t *tmp1, *el1; 368 HASH_ITER(hh, handle->nodes_table, el1, tmp1) { 369 if (el1->cnt == 0) { 370 ZF_LOGE("Non-existing node %s specified to be kept", el1->name); 371 } 372 HASH_DEL(handle->nodes_table, el1); 373 free(el1->name); 374 free(el1); 375 } 376 377 free(handle->string_buf); 378} 379 380void fdtgen_keep_nodes(fdtgen_context_t *handle, const char **nodes_to_keep, int num_nodes) 381{ 382 init_keep_node(handle, nodes_to_keep, num_nodes, DEVICE_KEEP); 383} 384 385void fdtgen_keep_nodes_and_disable(fdtgen_context_t *handle, const char **nodes_to_keep, int num_nodes) 386{ 387 init_keep_node(handle, nodes_to_keep, num_nodes, DEVICE_KEEP_AND_DISABLE); 388} 389 390static void keep_node_and_children(fdtgen_context_t *handle, const void *ori_fdt, int offset, enum device_flag flag) 391{ 392 int child; 393 fdt_for_each_subnode(child, ori_fdt, offset) { 394 int len_ori = strlen(handle->string_buf); 395 strcat(handle->string_buf, "/"); 396 const char *n = fdt_get_name(ori_fdt, child, NULL); 397 strcat(handle->string_buf, n); 398 399 path_node_t *this; 400 HASH_FIND_STR(handle->nodes_table, handle->string_buf, this); 401 if (this == NULL) { 402 path_node_t *new = malloc(sizeof(path_node_t)); 403 new->name = strdup(handle->string_buf); 404 new->cnt = 0; 405 new->flag = flag; 406 HASH_ADD_STR(handle->nodes_table, name, new); 407 } else { 408 this->flag = flag; 409 } 410 411 keep_node_and_children(handle, ori_fdt, child, flag); 412 handle->string_buf[len_ori] = '\0'; 413 } 414} 415 416void fdtgen_keep_node_subtree_disable(fdtgen_context_t *handle, const void *ori_fdt, const char *node) 417{ 418 int child = fdt_path_offset(ori_fdt, node); 419 if (child < 0) { 420 ZF_LOGE("Non-existing root node %s", node); 421 } else { 422 fdt_get_path(ori_fdt, child, handle->string_buf, MAX_FULL_PATH_LENGTH); 423 path_node_t *this; 424 HASH_FIND_STR(handle->nodes_table, handle->string_buf, this); 425 if (this == NULL) { 426 path_node_t *new = malloc(sizeof(path_node_t)); 427 new->name = strdup(handle->string_buf); 428 new->cnt = 0; 429 new->flag = DEVICE_KEEP_AND_DISABLE; 430 HASH_ADD_STR(handle->nodes_table, name, new); 431 } else { 432 this->flag = DEVICE_KEEP_AND_DISABLE; 433 } 434 keep_node_and_children(handle, ori_fdt, child, DEVICE_KEEP_AND_DISABLE); 435 } 436} 437 438 439void fdtgen_keep_node_subtree(fdtgen_context_t *handle, const void *ori_fdt, const char *node) 440{ 441 int child = fdt_path_offset(ori_fdt, node); 442 if (child < 0) { 443 ZF_LOGE("Non-existing root node %s", node); 444 } else { 445 fdt_get_path(ori_fdt, child, handle->string_buf, MAX_FULL_PATH_LENGTH); 446 path_node_t *this; 447 HASH_FIND_STR(handle->nodes_table, handle->string_buf, this); 448 if (this == NULL) { 449 path_node_t *new = malloc(sizeof(path_node_t)); 450 new->name = strdup(handle->string_buf); 451 new->cnt = 0; 452 new->flag = DEVICE_KEEP; 453 HASH_ADD_STR(handle->nodes_table, name, new); 454 } else { 455 this->flag = DEVICE_KEEP; 456 } 457 keep_node_and_children(handle, ori_fdt, child, DEVICE_KEEP); 458 } 459} 460 461int fdtgen_generate(fdtgen_context_t *handle, const void *fdt_ori) 462{ 463 if (handle == NULL) { 464 return -1; 465 } 466 void *fdt_gen = handle->buffer; 467 fdt_open_into(fdt_ori, fdt_gen, handle->bufsize); 468 /* just make sure the device tree is valid */ 469 int rst = fdt_check_full(fdt_gen, handle->bufsize); 470 if (rst != 0) { 471 ZF_LOGE("The original fdt is illegal : %d", rst); 472 return -1; 473 } 474 475 /* in case the root node is not at 0 offset. 476 * is that possible? */ 477 handle->root_offset = fdt_path_offset(fdt_gen, "/"); 478 479 handle->string_buf[0] = '\0'; 480 find_nodes_to_keep(handle, handle->root_offset); 481 resolve_all_dependencies(handle); 482 483 // always keep the root node 484 path_node_t *root = malloc(sizeof(path_node_t)); 485 root->name = strdup("/"); 486 root->offset = handle->root_offset; 487 root->cnt = 1; 488 root->flag = DEVICE_KEEP; 489 HASH_ADD_STR(handle->nodes_table, name, root); 490 491 handle->string_buf[0] = '\0'; 492 trim_tree(handle, handle->root_offset); 493 rst = fdt_check_full(fdt_gen, handle->bufsize); 494 if (rst != 0) { 495 ZF_LOGE("The generated fdt is illegal"); 496 return -1; 497 } 498 499 return 0; 500} 501 502fdtgen_context_t *fdtgen_new_context(void *buf, size_t bufsize) 503{ 504 fdtgen_context_t *to_return = malloc(sizeof(fdtgen_context_t)); 505 if (to_return == NULL) { 506 return NULL; 507 } 508 to_return->buffer = buf; 509 to_return->bufsize = bufsize; 510 to_return->nodes_table = NULL; 511 to_return->dep_table = NULL; 512 to_return->root_offset = 0; 513 to_return->string_buf = malloc(MAX_FULL_PATH_LENGTH); 514 return to_return; 515} 516 517void fdtgen_free_context(fdtgen_context_t *h) 518{ 519 if (h) { 520 clean_up(h); 521 free(h); 522 } 523} 524