lib/libfdt/fdt_region.c

   1 /*
   2  * libfdt - Flat Device Tree manipulation
   3  * Copyright (C) 2013 Google, Inc
   4  * Written by Simon Glass <sjg@chromium.org>
   5  * SPDX-License-Identifier:     GPL-2.0+ BSD-2-Clause
   6  */
   7
   8 #include "libfdt_env.h"
   9
  10 #ifndef USE_HOSTCC
  11 #include <fdt.h>
  12 #include <libfdt.h>
  13 #else
  14 #include "fdt_host.h"
  15 #endif
  16
  17 #include "libfdt_internal.h"
  18
  19 /**
  20  * fdt_add_region() - Add a new region to our list
  21  *
  22  * The region is added if there is space, but in any case we increment the
  23  * count. If permitted, and the new region overlaps the last one, we merge
  24  * them.
  25  *
  26  * @info: State information
  27  * @offset: Start offset of region
  28  * @size: Size of region
  29  */
  30 static int fdt_add_region(struct fdt_region_state *info, int offset, int size)
  31 {
  32         struct fdt_region *reg;
  33
  34         reg = info->region ? &info->region[info->count - 1] : NULL;
  35         if (info->can_merge && info->count &&
  36             info->count <= info->max_regions &&
  37             reg && offset <= reg->offset + reg->size) {
  38                 reg->size = offset + size - reg->offset;
  39         } else if (info->count++ < info->max_regions) {
  40                 if (reg) {
  41                         reg++;
  42                         reg->offset = offset;
  43                         reg->size = size;
  44                 }
  45         } else {
  46                 return -1;
  47         }
  48
  49         return 0;
  50 }
  51
  52 static int region_list_contains_offset(struct fdt_region_state *info,
  53                                        const void *fdt, int target)
  54 {
  55         struct fdt_region *reg;
  56         int num;
  57
  58         target += fdt_off_dt_struct(fdt);
  59         for (reg = info->region, num = 0; num < info->count; reg++, num++) {
  60                 if (target >= reg->offset && target < reg->offset + reg->size)
  61                         return 1;
  62         }
  63
  64         return 0;
  65 }
  66
  67 int fdt_add_alias_regions(const void *fdt, struct fdt_region *region, int count,
  68                           int max_regions, struct fdt_region_state *info)
  69 {
  70         int base = fdt_off_dt_struct(fdt);
  71         int node, node_end, offset;
  72         int did_alias_header;
  73
  74         node = fdt_subnode_offset(fdt, 0, "aliases");
  75         if (node < 0)
  76                 return -FDT_ERR_NOTFOUND;
  77
  78         /* The aliases node must come before the others */
  79         node_end = fdt_next_subnode(fdt, node);
  80         if (node_end <= 0)
  81                 return -FDT_ERR_BADLAYOUT;
  82         node_end -= sizeof(fdt32_t);
  83
  84         did_alias_header = 0;
  85         info->region = region;
  86         info->count = count;
  87         info->can_merge = 0;
  88         info->max_regions = max_regions;
  89
  90         for (offset = fdt_first_property_offset(fdt, node);
  91              offset >= 0;
  92              offset = fdt_next_property_offset(fdt, offset)) {
  93                 const struct fdt_property *prop;
  94                 const char *name;
  95                 int target, next;
  96
  97                 prop = fdt_get_property_by_offset(fdt, offset, NULL);
  98                 name = fdt_string(fdt, fdt32_to_cpu(prop->nameoff));
  99                 target = fdt_path_offset(fdt, name);
 100                 if (!region_list_contains_offset(info, fdt, target))
 101                         continue;
 102                 next = fdt_next_property_offset(fdt, offset);
 103                 if (next < 0)
 104                         next = node_end - sizeof(fdt32_t);
 105
 106                 if (!did_alias_header) {
 107                         fdt_add_region(info, base + node, 12);
 108                         did_alias_header = 1;
 109                 }
 110                 fdt_add_region(info, base + offset, next - offset);
 111         }
 112
 113         /* Add the 'end' tag */
 114         if (did_alias_header)
 115                 fdt_add_region(info, base + node_end, sizeof(fdt32_t));
 116
 117         return info->count < max_regions ? info->count : -FDT_ERR_NOSPACE;
 118 }
 119
 120 /**
 121  * fdt_include_supernodes() - Include supernodes required by this node
 122  *
 123  * When we decided to include a node or property which is not at the top
 124  * level, this function forces the inclusion of higher level nodes. For
 125  * example, given this tree:
 126  *
 127  * / {
 128  *     testing {
 129  *     }
 130  * }
 131  *
 132  * If we decide to include testing then we need the root node to have a valid
 133  * tree. This function adds those regions.
 134  *
 135  * @info: State information
 136  * @depth: Current stack depth
 137  */
 138 static int fdt_include_supernodes(struct fdt_region_state *info, int depth)
 139 {
 140         int base = fdt_off_dt_struct(info->fdt);
 141         int start, stop_at;
 142         int i;
 143
 144         /*
 145          * Work down the stack looking for supernodes that we didn't include.
 146          * The algortihm here is actually pretty simple, since we know that
 147          * no previous subnode had to include these nodes, or if it did, we
 148          * marked them as included (on the stack) already.
 149          */
 150         for (i = 0; i <= depth; i++) {
 151                 if (!info->stack[i].included) {
 152                         start = info->stack[i].offset;
 153
 154                         /* Add the FDT_BEGIN_NODE tag of this supernode */
 155                         fdt_next_tag(info->fdt, start, &stop_at);
 156                         if (fdt_add_region(info, base + start, stop_at - start))
 157                                 return -1;
 158
 159                         /* Remember that this supernode is now included */
 160                         info->stack[i].included = 1;
 161                         info->can_merge = 1;
 162                 }
 163
 164                 /* Force (later) generation of the FDT_END_NODE tag */
 165                 if (!info->stack[i].want)
 166                         info->stack[i].want = WANT_NODES_ONLY;
 167         }
 168
 169         return 0;
 170 }
 171
 172 enum {
 173         FDT_DONE_NOTHING,
 174         FDT_DONE_MEM_RSVMAP,
 175         FDT_DONE_STRUCT,
 176         FDT_DONE_END,
 177         FDT_DONE_STRINGS,
 178         FDT_DONE_ALL,
 179 };
 180
 181 int fdt_first_region(const void *fdt,
 182                 int (*h_include)(void *priv, const void *fdt, int offset,
 183                                  int type, const char *data, int size),
 184                 void *priv, struct fdt_region *region,
 185                 char *path, int path_len, int flags,
 186                 struct fdt_region_state *info)
 187 {
 188         struct fdt_region_ptrs *p = &info->ptrs;
 189
 190         /* Set up our state */
 191         info->fdt = fdt;
 192         info->can_merge = 1;
 193         info->max_regions = 1;
 194         info->start = -1;
 195         p->want = WANT_NOTHING;
 196         p->end = path;
 197         *p->end = '\0';
 198         p->nextoffset = 0;
 199         p->depth = -1;
 200         p->done = FDT_DONE_NOTHING;
 201
 202         return fdt_next_region(fdt, h_include, priv, region,
 203                                path, path_len, flags, info);
 204 }
 205
 206 /*
 207  * Theory of operation
 208  *
 209  *
 210  *
 211
 212 Note: in this description 'included' means that a node (or other part of
 213 the tree) should be included in the region list, i.e. it will have a region
 214 which covers its part of the tree.
 215
 216 This function maintains some state from the last time it is called. It
 217 checks the next part of the tree that it is supposed to look at
 218 (p.nextoffset) to see if that should be included or not. When it finds
 219 something to include, it sets info->start to its offset. This marks the
 220 start of the region we want to include.
 221
 222 Once info->start is set to the start (i.e. not -1), we continue scanning
 223 until we find something that we don't want included. This will be the end
 224 of a region. At this point we can close off the region and add it to the
 225 list. So we do so, and reset info->start to -1.
 226
 227 One complication here is that we want to merge regions. So when we come to
 228 add another region later, we may in fact merge it with the previous one if
 229 one ends where the other starts.
 230
 231 The function fdt_add_region() will return -1 if it fails to add the region,
 232 because we already have a region ready to be returned, and the new one
 233 cannot be merged in with it. In this case, we must return the region we
 234 found, and wait for another call to this function. When it comes, we will
 235 repeat the processing of the tag and again try to add a region. This time it
 236 will succeed.
 237
 238 The current state of the pointers (stack, offset, etc.) is maintained in
 239 a ptrs member. At the start of every loop iteration we make a copy of it.
 240 The copy is then updated as the tag is processed. Only if we get to the end
 241 of the loop iteration (and successfully call fdt_add_region() if we need
 242 to) can we commit the changes we have made to these pointers. For example,
 243 if we see an FDT_END_NODE tag we will decrement the depth value. But if we
 244 need to add a region for this tag (let's say because the previous tag is
 245 included and this FDT_END_NODE tag is not included) then we will only commit
 246 the result if we were able to add the region. That allows us to retry again
 247 next time.
 248
 249 We keep track of a variable called 'want' which tells us what we want to
 250 include when there is no specific information provided by the h_include
 251 function for a particular property. This basically handles the inclusion of
 252 properties which are pulled in by virtue of the node they are in. So if you
 253 include a node, its properties are also included. In this case 'want' will
 254 be WANT_NODES_AND_PROPS. The FDT_REG_DIRECT_SUBNODES feature also makes use
 255 of 'want'. While we are inside the subnode, 'want' will be set to
 256 WANT_NODES_ONLY, so that only the subnode's FDT_BEGIN_NODE and FDT_END_NODE
 257 tags will be included, and properties will be skipped. If WANT_NOTHING is
 258 selected, then we will just rely on what the h_include() function tells us.
 259
 260 Using 'want' we work out 'include', which tells us whether this current tag
 261 should be included or not. As you can imagine, if the value of 'include'
 262 changes, that means we are on a boundary between nodes to include and nodes
 263 to exclude. At this point we either close off a previous region and add it
 264 to the list, or mark the start of a new region.
 265
 266 Apart from the nodes, we have mem_rsvmap, the FDT_END tag and the string
 267 list. Each of these dealt with as a whole (i.e. we create a region for each
 268 if it is to be included). For mem_rsvmap we don't allow it to merge with
 269 the first struct region. For the stringlist we don't allow it to merge with
 270 the last struct region (which contains at minimum the FDT_END tag).
 271 */
 272 int fdt_next_region(const void *fdt,
 273                 int (*h_include)(void *priv, const void *fdt, int offset,
 274                                  int type, const char *data, int size),
 275                 void *priv, struct fdt_region *region,
 276                 char *path, int path_len, int flags,
 277                 struct fdt_region_state *info)
 278 {
 279         int base = fdt_off_dt_struct(fdt);
 280         int last_node = 0;
 281         const char *str;
 282
 283         info->region = region;
 284         info->count = 0;
 285         if (info->ptrs.done < FDT_DONE_MEM_RSVMAP &&
 286             (flags & FDT_REG_ADD_MEM_RSVMAP)) {
 287                 /* Add the memory reserve map into its own region */
 288                 if (fdt_add_region(info, fdt_off_mem_rsvmap(fdt),
 289                                    fdt_off_dt_struct(fdt) -
 290                                    fdt_off_mem_rsvmap(fdt)))
 291                         return 0;
 292                 info->can_merge = 0;    /* Don't allow merging with this */
 293                 info->ptrs.done = FDT_DONE_MEM_RSVMAP;
 294         }
 295
 296         /*
 297          * Work through the tags one by one, deciding whether each needs to
 298          * be included or not. We set the variable 'include' to indicate our
 299          * decision. 'want' is used to track what we want to include - it
 300          * allows us to pick up all the properties (and/or subnode tags) of
 301          * a node.
 302          */
 303         while (info->ptrs.done < FDT_DONE_STRUCT) {
 304                 const struct fdt_property *prop;
 305                 struct fdt_region_ptrs p;
 306                 const char *name;
 307                 int include = 0;
 308                 int stop_at = 0;
 309                 uint32_t tag;
 310                 int offset;
 311                 int val;
 312                 int len;
 313
 314                 /*
 315                  * Make a copy of our pointers. If we make it to the end of
 316                  * this block then we will commit them back to info->ptrs.
 317                  * Otherwise we can try again from the same starting state
 318                  * next time we are called.
 319                  */
 320                 p = info->ptrs;
 321
 322                 /*
 323                  * Find the tag, and the offset of the next one. If we need to
 324                  * stop including tags, then by default we stop *after*
 325                  * including the current tag
 326                  */
 327                 offset = p.nextoffset;
 328                 tag = fdt_next_tag(fdt, offset, &p.nextoffset);
 329                 stop_at = p.nextoffset;
 330
 331                 switch (tag) {
 332                 case FDT_PROP:
 333                         stop_at = offset;
 334                         prop = fdt_get_property_by_offset(fdt, offset, NULL);
 335                         str = fdt_string(fdt, fdt32_to_cpu(prop->nameoff));
 336                         val = h_include(priv, fdt, last_node, FDT_IS_PROP, str,
 337                                             strlen(str) + 1);
 338                         if (val == -1) {
 339                                 include = p.want >= WANT_NODES_AND_PROPS;
 340                         } else {
 341                                 include = val;
 342                                 /*
 343                                  * Make sure we include the } for this block.
 344                                  * It might be more correct to have this done
 345                                  * by the call to fdt_include_supernodes() in
 346                                  * the case where it adds the node we are
 347                                  * currently in, but this is equivalent.
 348                                  */
 349                                 if ((flags & FDT_REG_SUPERNODES) && val &&
 350                                     !p.want)
 351                                         p.want = WANT_NODES_ONLY;
 352                         }
 353
 354                         /* Value grepping is not yet supported */
 355                         break;
 356
 357                 case FDT_NOP:
 358                         include = p.want >= WANT_NODES_AND_PROPS;
 359                         stop_at = offset;
 360                         break;
 361
 362                 case FDT_BEGIN_NODE:
 363                         last_node = offset;
 364                         p.depth++;
 365                         if (p.depth == FDT_MAX_DEPTH)
 366                                 return -FDT_ERR_TOODEEP;
 367                         name = fdt_get_name(fdt, offset, &len);
 368                         if (p.end - path + 2 + len >= path_len)
 369                                 return -FDT_ERR_NOSPACE;
 370
 371                         /* Build the full path of this node */
 372                         if (p.end != path + 1)
 373                                 *p.end++ = '/';
 374                         strcpy(p.end, name);
 375                         p.end += len;
 376                         info->stack[p.depth].want = p.want;
 377                         info->stack[p.depth].offset = offset;
 378
 379                         /*
 380                          * If we are not intending to include this node unless
 381                          * it matches, make sure we stop *before* its tag.
 382                          */
 383                         if (p.want == WANT_NODES_ONLY ||
 384                             !(flags & (FDT_REG_DIRECT_SUBNODES |
 385                                        FDT_REG_ALL_SUBNODES))) {
 386                                 stop_at = offset;
 387                                 p.want = WANT_NOTHING;
 388                         }
 389                         val = h_include(priv, fdt, offset, FDT_IS_NODE, path,
 390                                         p.end - path + 1);
 391
 392                         /* Include this if requested */
 393                         if (val) {
 394                                 p.want = (flags & FDT_REG_ALL_SUBNODES) ?
 395                                         WANT_ALL_NODES_AND_PROPS :
 396                                         WANT_NODES_AND_PROPS;
 397                         }
 398
 399                         /* If not requested, decay our 'p.want' value */
 400                         else if (p.want) {
 401                                 if (p.want != WANT_ALL_NODES_AND_PROPS)
 402                                         p.want--;
 403
 404                         /* Not including this tag, so stop now */
 405                         } else {
 406                                 stop_at = offset;
 407                         }
 408
 409                         /*
 410                          * Decide whether to include this tag, and update our
 411                          * stack with the state for this node
 412                          */
 413                         include = p.want;
 414                         info->stack[p.depth].included = include;
 415                         break;
 416
 417                 case FDT_END_NODE:
 418                         include = p.want;
 419                         if (p.depth < 0)
 420                                 return -FDT_ERR_BADSTRUCTURE;
 421
 422                         /*
 423                          * If we don't want this node, stop right away, unless
 424                          * we are including subnodes
 425                          */
 426                         if (!p.want && !(flags & FDT_REG_DIRECT_SUBNODES))
 427                                 stop_at = offset;
 428                         p.want = info->stack[p.depth].want;
 429                         p.depth--;
 430                         while (p.end > path && *--p.end != '/')
 431                                 ;
 432                         *p.end = '\0';
 433                         break;
 434
 435                 case FDT_END:
 436                         /* We always include the end tag */
 437                         include = 1;
 438                         p.done = FDT_DONE_STRUCT;
 439                         break;
 440                 }
 441
 442                 /* If this tag is to be included, mark it as region start */
 443                 if (include && info->start == -1) {
 444                         /* Include any supernodes required by this one */
 445                         if (flags & FDT_REG_SUPERNODES) {
 446                                 if (fdt_include_supernodes(info, p.depth))
 447                                         return 0;
 448                         }
 449                         info->start = offset;
 450                 }
 451
 452                 /*
 453                  * If this tag is not to be included, finish up the current
 454                  * region.
 455                  */
 456                 if (!include && info->start != -1) {
 457                         if (fdt_add_region(info, base + info->start,
 458                                            stop_at - info->start))
 459                                 return 0;
 460                         info->start = -1;
 461                         info->can_merge = 1;
 462                 }
 463
 464                 /* If we have made it this far, we can commit our pointers */
 465                 info->ptrs = p;
 466         }
 467
 468         /* Add a region for the END tag and a separate one for string table */
 469         if (info->ptrs.done < FDT_DONE_END) {
 470                 if (info->ptrs.nextoffset != fdt_size_dt_struct(fdt))
 471                         return -FDT_ERR_BADSTRUCTURE;
 472
 473                 if (fdt_add_region(info, base + info->start,
 474                                    info->ptrs.nextoffset - info->start))
 475                         return 0;
 476                 info->ptrs.done++;
 477         }
 478         if (info->ptrs.done < FDT_DONE_STRINGS) {
 479                 if (flags & FDT_REG_ADD_STRING_TAB) {
 480                         info->can_merge = 0;
 481                         if (fdt_off_dt_strings(fdt) <
 482                             base + info->ptrs.nextoffset)
 483                                 return -FDT_ERR_BADLAYOUT;
 484                         if (fdt_add_region(info, fdt_off_dt_strings(fdt),
 485                                            fdt_size_dt_strings(fdt)))
 486                                 return 0;
 487                 }
 488                 info->ptrs.done++;
 489         }
 490
 491         return info->count > 0 ? 0 : -FDT_ERR_NOTFOUND;
 492 }