arch/powerpc/boot/flatdevtree.c

   1 /*
   2  * This program is free software; you can redistribute it and/or modify
   3  * it under the terms of the GNU General Public License as published by
   4  * the Free Software Foundation; either version 2 of the License, or
   5  * (at your option) any later version.
   6  *
   7  * This program is distributed in the hope that it will be useful,
   8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10  * GNU General Public License for more details.
  11  *
  12  * You should have received a copy of the GNU General Public License
  13  * along with this program; if not, write to the Free Software
  14  * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  15  *
  16  * Copyright Pantelis Antoniou 2006
  17  * Copyright (C) IBM Corporation 2006
  18  *
  19  * Authors: Pantelis Antoniou <pantelis@embeddedalley.com>
  20  *          Hollis Blanchard <hollisb@us.ibm.com>
  21  *          Mark A. Greer <mgreer@mvista.com>
  22  *          Paul Mackerras <paulus@samba.org>
  23  */
  24
  25 #include <string.h>
  26 #include <stddef.h>
  27 #include "flatdevtree.h"
  28 #include "flatdevtree_env.h"
  29
  30 #define _ALIGN(x, al)   (((x) + (al) - 1) & ~((al) - 1))
  31
  32 /* Routines for keeping node ptrs returned by ft_find_device current */
  33 /* First entry not used b/c it would return 0 and be taken as NULL/error */
  34 static void *ft_node_add(struct ft_cxt *cxt, char *node)
  35 {
  36         unsigned int i;
  37
  38         for (i = 1; i < cxt->nodes_used; i++)   /* already there? */
  39                 if (cxt->node_tbl[i] == node)
  40                         return (void *)i;
  41
  42         if (cxt->nodes_used < cxt->node_max) {
  43                 cxt->node_tbl[cxt->nodes_used] = node;
  44                 return (void *)cxt->nodes_used++;
  45         }
  46
  47         return NULL;
  48 }
  49
  50 static char *ft_node_ph2node(struct ft_cxt *cxt, const void *phandle)
  51 {
  52         unsigned int i = (unsigned int)phandle;
  53
  54         if (i < cxt->nodes_used)
  55                 return cxt->node_tbl[i];
  56         return NULL;
  57 }
  58
  59 static void ft_node_update_before(struct ft_cxt *cxt, char *addr, int shift)
  60 {
  61         unsigned int i;
  62
  63         if (shift == 0)
  64                 return;
  65
  66         for (i = 1; i < cxt->nodes_used; i++)
  67                 if (cxt->node_tbl[i] < addr)
  68                         cxt->node_tbl[i] += shift;
  69 }
  70
  71 static void ft_node_update_after(struct ft_cxt *cxt, char *addr, int shift)
  72 {
  73         unsigned int i;
  74
  75         if (shift == 0)
  76                 return;
  77
  78         for (i = 1; i < cxt->nodes_used; i++)
  79                 if (cxt->node_tbl[i] >= addr)
  80                         cxt->node_tbl[i] += shift;
  81 }
  82
  83 /* Struct used to return info from ft_next() */
  84 struct ft_atom {
  85         u32 tag;
  86         const char *name;
  87         void *data;
  88         u32 size;
  89 };
  90
  91 /* Set ptrs to current one's info; return addr of next one */
  92 static char *ft_next(struct ft_cxt *cxt, char *p, struct ft_atom *ret)
  93 {
  94         u32 sz;
  95
  96         if (p >= cxt->rgn[FT_STRUCT].start + cxt->rgn[FT_STRUCT].size)
  97                 return NULL;
  98
  99         ret->tag = be32_to_cpu(*(u32 *) p);
 100         p += 4;
 101
 102         switch (ret->tag) {     /* Tag */
 103         case OF_DT_BEGIN_NODE:
 104                 ret->name = p;
 105                 ret->data = (void *)(p - 4);    /* start of node */
 106                 p += _ALIGN(strlen(p) + 1, 4);
 107                 break;
 108         case OF_DT_PROP:
 109                 ret->size = sz = be32_to_cpu(*(u32 *) p);
 110                 ret->name = cxt->str_anchor + be32_to_cpu(*(u32 *) (p + 4));
 111                 ret->data = (void *)(p + 8);
 112                 p += 8 + _ALIGN(sz, 4);
 113                 break;
 114         case OF_DT_END_NODE:
 115         case OF_DT_NOP:
 116                 break;
 117         case OF_DT_END:
 118         default:
 119                 p = NULL;
 120                 break;
 121         }
 122
 123         return p;
 124 }
 125
 126 #define HDR_SIZE        _ALIGN(sizeof(struct boot_param_header), 8)
 127 #define EXPAND_INCR     1024    /* alloc this much extra when expanding */
 128
 129 /* See if the regions are in the standard order and non-overlapping */
 130 static int ft_ordered(struct ft_cxt *cxt)
 131 {
 132         char *p = (char *)cxt->bph + HDR_SIZE;
 133         enum ft_rgn_id r;
 134
 135         for (r = FT_RSVMAP; r <= FT_STRINGS; ++r) {
 136                 if (p > cxt->rgn[r].start)
 137                         return 0;
 138                 p = cxt->rgn[r].start + cxt->rgn[r].size;
 139         }
 140         return p <= (char *)cxt->bph + cxt->max_size;
 141 }
 142
 143 /* Copy the tree to a newly-allocated region and put things in order */
 144 static int ft_reorder(struct ft_cxt *cxt, int nextra)
 145 {
 146         unsigned long tot;
 147         enum ft_rgn_id r;
 148         char *p, *pend;
 149         int stroff;
 150
 151         tot = HDR_SIZE + EXPAND_INCR;
 152         for (r = FT_RSVMAP; r <= FT_STRINGS; ++r)
 153                 tot += cxt->rgn[r].size;
 154         if (nextra > 0)
 155                 tot += nextra;
 156         tot = _ALIGN(tot, 8);
 157
 158         if (!cxt->realloc)
 159                 return 0;
 160         p = cxt->realloc(NULL, tot);
 161         if (!p)
 162                 return 0;
 163
 164         memcpy(p, cxt->bph, sizeof(struct boot_param_header));
 165         /* offsets get fixed up later */
 166
 167         cxt->bph = (struct boot_param_header *)p;
 168         cxt->max_size = tot;
 169         pend = p + tot;
 170         p += HDR_SIZE;
 171
 172         memcpy(p, cxt->rgn[FT_RSVMAP].start, cxt->rgn[FT_RSVMAP].size);
 173         cxt->rgn[FT_RSVMAP].start = p;
 174         p += cxt->rgn[FT_RSVMAP].size;
 175
 176         memcpy(p, cxt->rgn[FT_STRUCT].start, cxt->rgn[FT_STRUCT].size);
 177         ft_node_update_after(cxt, cxt->rgn[FT_STRUCT].start,
 178                         p - cxt->rgn[FT_STRUCT].start);
 179         cxt->p += p - cxt->rgn[FT_STRUCT].start;
 180         cxt->rgn[FT_STRUCT].start = p;
 181
 182         p = pend - cxt->rgn[FT_STRINGS].size;
 183         memcpy(p, cxt->rgn[FT_STRINGS].start, cxt->rgn[FT_STRINGS].size);
 184         stroff = cxt->str_anchor - cxt->rgn[FT_STRINGS].start;
 185         cxt->rgn[FT_STRINGS].start = p;
 186         cxt->str_anchor = p + stroff;
 187
 188         cxt->isordered = 1;
 189         return 1;
 190 }
 191
 192 static inline char *prev_end(struct ft_cxt *cxt, enum ft_rgn_id r)
 193 {
 194         if (r > FT_RSVMAP)
 195                 return cxt->rgn[r - 1].start + cxt->rgn[r - 1].size;
 196         return (char *)cxt->bph + HDR_SIZE;
 197 }
 198
 199 static inline char *next_start(struct ft_cxt *cxt, enum ft_rgn_id r)
 200 {
 201         if (r < FT_STRINGS)
 202                 return cxt->rgn[r + 1].start;
 203         return (char *)cxt->bph + cxt->max_size;
 204 }
 205
 206 /*
 207  * See if we can expand region rgn by nextra bytes by using up
 208  * free space after or before the region.
 209  */
 210 static int ft_shuffle(struct ft_cxt *cxt, char **pp, enum ft_rgn_id rgn,
 211                 int nextra)
 212 {
 213         char *p = *pp;
 214         char *rgn_start, *rgn_end;
 215
 216         rgn_start = cxt->rgn[rgn].start;
 217         rgn_end = rgn_start + cxt->rgn[rgn].size;
 218         if (nextra <= 0 || rgn_end + nextra <= next_start(cxt, rgn)) {
 219                 /* move following stuff */
 220                 if (p < rgn_end) {
 221                         if (nextra < 0)
 222                                 memmove(p, p - nextra, rgn_end - p + nextra);
 223                         else
 224                                 memmove(p + nextra, p, rgn_end - p);
 225                         if (rgn == FT_STRUCT)
 226                                 ft_node_update_after(cxt, p, nextra);
 227                 }
 228                 cxt->rgn[rgn].size += nextra;
 229                 if (rgn == FT_STRINGS)
 230                         /* assumes strings only added at beginning */
 231                         cxt->str_anchor += nextra;
 232                 return 1;
 233         }
 234         if (prev_end(cxt, rgn) <= rgn_start - nextra) {
 235                 /* move preceding stuff */
 236                 if (p > rgn_start) {
 237                         memmove(rgn_start - nextra, rgn_start, p - rgn_start);
 238                         if (rgn == FT_STRUCT)
 239                                 ft_node_update_before(cxt, p, -nextra);
 240                 }
 241                 *p -= nextra;
 242                 cxt->rgn[rgn].start -= nextra;
 243                 cxt->rgn[rgn].size += nextra;
 244                 return 1;
 245         }
 246         return 0;
 247 }
 248
 249 static int ft_make_space(struct ft_cxt *cxt, char **pp, enum ft_rgn_id rgn,
 250                          int nextra)
 251 {
 252         unsigned long size, ssize, tot;
 253         char *str, *next;
 254         enum ft_rgn_id r;
 255
 256         if (!cxt->isordered && !ft_reorder(cxt, nextra))
 257                 return 0;
 258         if (ft_shuffle(cxt, pp, rgn, nextra))
 259                 return 1;
 260
 261         /* See if there is space after the strings section */
 262         ssize = cxt->rgn[FT_STRINGS].size;
 263         if (cxt->rgn[FT_STRINGS].start + ssize
 264                         < (char *)cxt->bph + cxt->max_size) {
 265                 /* move strings up as far as possible */
 266                 str = (char *)cxt->bph + cxt->max_size - ssize;
 267                 cxt->str_anchor += str - cxt->rgn[FT_STRINGS].start;
 268                 memmove(str, cxt->rgn[FT_STRINGS].start, ssize);
 269                 cxt->rgn[FT_STRINGS].start = str;
 270                 /* enough space now? */
 271                 if (rgn >= FT_STRUCT && ft_shuffle(cxt, pp, rgn, nextra))
 272                         return 1;
 273         }
 274
 275         /* how much total free space is there following this region? */
 276         tot = 0;
 277         for (r = rgn; r < FT_STRINGS; ++r) {
 278                 char *r_end = cxt->rgn[r].start + cxt->rgn[r].size;
 279                 tot += next_start(cxt, rgn) - r_end;
 280         }
 281
 282         /* cast is to shut gcc up; we know nextra >= 0 */
 283         if (tot < (unsigned int)nextra) {
 284                 /* have to reallocate */
 285                 char *newp, *new_start;
 286                 int shift;
 287
 288                 if (!cxt->realloc)
 289                         return 0;
 290                 size = _ALIGN(cxt->max_size + (nextra - tot) + EXPAND_INCR, 8);
 291                 newp = cxt->realloc(cxt->bph, size);
 292                 if (!newp)
 293                         return 0;
 294                 cxt->max_size = size;
 295                 shift = newp - (char *)cxt->bph;
 296
 297                 if (shift) { /* realloc can return same addr */
 298                         cxt->bph = (struct boot_param_header *)newp;
 299                         ft_node_update_after(cxt, cxt->rgn[FT_STRUCT].start,
 300                                         shift);
 301                         for (r = FT_RSVMAP; r <= FT_STRINGS; ++r) {
 302                                 new_start = cxt->rgn[r].start + shift;
 303                                 cxt->rgn[r].start = new_start;
 304                         }
 305                         *pp += shift;
 306                         cxt->str_anchor += shift;
 307                 }
 308
 309                 /* move strings up to the end */
 310                 str = newp + size - ssize;
 311                 cxt->str_anchor += str - cxt->rgn[FT_STRINGS].start;
 312                 memmove(str, cxt->rgn[FT_STRINGS].start, ssize);
 313                 cxt->rgn[FT_STRINGS].start = str;
 314
 315                 if (ft_shuffle(cxt, pp, rgn, nextra))
 316                         return 1;
 317         }
 318
 319         /* must be FT_RSVMAP and we need to move FT_STRUCT up */
 320         if (rgn == FT_RSVMAP) {
 321                 next = cxt->rgn[FT_RSVMAP].start + cxt->rgn[FT_RSVMAP].size
 322                         + nextra;
 323                 ssize = cxt->rgn[FT_STRUCT].size;
 324                 if (next + ssize >= cxt->rgn[FT_STRINGS].start)
 325                         return 0;       /* "can't happen" */
 326                 memmove(next, cxt->rgn[FT_STRUCT].start, ssize);
 327                 ft_node_update_after(cxt, cxt->rgn[FT_STRUCT].start, nextra);
 328                 cxt->rgn[FT_STRUCT].start = next;
 329
 330                 if (ft_shuffle(cxt, pp, rgn, nextra))
 331                         return 1;
 332         }
 333
 334         return 0;               /* "can't happen" */
 335 }
 336
 337 static void ft_put_word(struct ft_cxt *cxt, u32 v)
 338 {
 339         *(u32 *) cxt->p = cpu_to_be32(v);
 340         cxt->p += 4;
 341 }
 342
 343 static void ft_put_bin(struct ft_cxt *cxt, const void *data, unsigned int sz)
 344 {
 345         unsigned long sza = _ALIGN(sz, 4);
 346
 347         /* zero out the alignment gap if necessary */
 348         if (sz < sza)
 349                 *(u32 *) (cxt->p + sza - 4) = 0;
 350
 351         /* copy in the data */
 352         memcpy(cxt->p, data, sz);
 353
 354         cxt->p += sza;
 355 }
 356
 357 int ft_begin_node(struct ft_cxt *cxt, const char *name)
 358 {
 359         unsigned long nlen = strlen(name) + 1;
 360         unsigned long len = 8 + _ALIGN(nlen, 4);
 361
 362         if (!ft_make_space(cxt, &cxt->p, FT_STRUCT, len))
 363                 return -1;
 364         ft_put_word(cxt, OF_DT_BEGIN_NODE);
 365         ft_put_bin(cxt, name, strlen(name) + 1);
 366         return 0;
 367 }
 368
 369 void ft_end_node(struct ft_cxt *cxt)
 370 {
 371         ft_put_word(cxt, OF_DT_END_NODE);
 372 }
 373
 374 void ft_nop(struct ft_cxt *cxt)
 375 {
 376         if (ft_make_space(cxt, &cxt->p, FT_STRUCT, 4))
 377                 ft_put_word(cxt, OF_DT_NOP);
 378 }
 379
 380 #define NO_STRING       0x7fffffff
 381
 382 static int lookup_string(struct ft_cxt *cxt, const char *name)
 383 {
 384         char *p, *end;
 385
 386         p = cxt->rgn[FT_STRINGS].start;
 387         end = p + cxt->rgn[FT_STRINGS].size;
 388         while (p < end) {
 389                 if (strcmp(p, (char *)name) == 0)
 390                         return p - cxt->str_anchor;
 391                 p += strlen(p) + 1;
 392         }
 393
 394         return NO_STRING;
 395 }
 396
 397 /* lookup string and insert if not found */
 398 static int map_string(struct ft_cxt *cxt, const char *name)
 399 {
 400         int off;
 401         char *p;
 402
 403         off = lookup_string(cxt, name);
 404         if (off != NO_STRING)
 405                 return off;
 406         p = cxt->rgn[FT_STRINGS].start;
 407         if (!ft_make_space(cxt, &p, FT_STRINGS, strlen(name) + 1))
 408                 return NO_STRING;
 409         strcpy(p, name);
 410         return p - cxt->str_anchor;
 411 }
 412
 413 int ft_prop(struct ft_cxt *cxt, const char *name, const void *data,
 414                 unsigned int sz)
 415 {
 416         int off, len;
 417
 418         off = lookup_string(cxt, name);
 419         if (off == NO_STRING)
 420                 return -1;
 421
 422         len = 12 + _ALIGN(sz, 4);
 423         if (!ft_make_space(cxt, &cxt->p, FT_STRUCT, len))
 424                 return -1;
 425
 426         ft_put_word(cxt, OF_DT_PROP);
 427         ft_put_word(cxt, sz);
 428         ft_put_word(cxt, off);
 429         ft_put_bin(cxt, data, sz);
 430         return 0;
 431 }
 432
 433 int ft_prop_str(struct ft_cxt *cxt, const char *name, const char *str)
 434 {
 435         return ft_prop(cxt, name, str, strlen(str) + 1);
 436 }
 437
 438 int ft_prop_int(struct ft_cxt *cxt, const char *name, unsigned int val)
 439 {
 440         u32 v = cpu_to_be32((u32) val);
 441
 442         return ft_prop(cxt, name, &v, 4);
 443 }
 444
 445 /* Calculate the size of the reserved map */
 446 static unsigned long rsvmap_size(struct ft_cxt *cxt)
 447 {
 448         struct ft_reserve *res;
 449
 450         res = (struct ft_reserve *)cxt->rgn[FT_RSVMAP].start;
 451         while (res->start || res->len)
 452                 ++res;
 453         return (char *)(res + 1) - cxt->rgn[FT_RSVMAP].start;
 454 }
 455
 456 /* Calculate the size of the struct region by stepping through it */
 457 static unsigned long struct_size(struct ft_cxt *cxt)
 458 {
 459         char *p = cxt->rgn[FT_STRUCT].start;
 460         char *next;
 461         struct ft_atom atom;
 462
 463         /* make check in ft_next happy */
 464         if (cxt->rgn[FT_STRUCT].size == 0)
 465                 cxt->rgn[FT_STRUCT].size = 0xfffffffful - (unsigned long)p;
 466
 467         while ((next = ft_next(cxt, p, &atom)) != NULL)
 468                 p = next;
 469         return p + 4 - cxt->rgn[FT_STRUCT].start;
 470 }
 471
 472 /* add `adj' on to all string offset values in the struct area */
 473 static void adjust_string_offsets(struct ft_cxt *cxt, int adj)
 474 {
 475         char *p = cxt->rgn[FT_STRUCT].start;
 476         char *next;
 477         struct ft_atom atom;
 478         int off;
 479
 480         while ((next = ft_next(cxt, p, &atom)) != NULL) {
 481                 if (atom.tag == OF_DT_PROP) {
 482                         off = be32_to_cpu(*(u32 *) (p + 8));
 483                         *(u32 *) (p + 8) = cpu_to_be32(off + adj);
 484                 }
 485                 p = next;
 486         }
 487 }
 488
 489 /* start construction of the flat OF tree from scratch */
 490 void ft_begin(struct ft_cxt *cxt, void *blob, unsigned int max_size,
 491                 void *(*realloc_fn) (void *, unsigned long))
 492 {
 493         struct boot_param_header *bph = blob;
 494         char *p;
 495         struct ft_reserve *pres;
 496
 497         /* clear the cxt */
 498         memset(cxt, 0, sizeof(*cxt));
 499
 500         cxt->bph = bph;
 501         cxt->max_size = max_size;
 502         cxt->realloc = realloc_fn;
 503         cxt->isordered = 1;
 504
 505         /* zero everything in the header area */
 506         memset(bph, 0, sizeof(*bph));
 507
 508         bph->magic = cpu_to_be32(OF_DT_HEADER);
 509         bph->version = cpu_to_be32(0x10);
 510         bph->last_comp_version = cpu_to_be32(0x10);
 511
 512         /* start pointers */
 513         cxt->rgn[FT_RSVMAP].start = p = blob + HDR_SIZE;
 514         cxt->rgn[FT_RSVMAP].size = sizeof(struct ft_reserve);
 515         pres = (struct ft_reserve *)p;
 516         cxt->rgn[FT_STRUCT].start = p += sizeof(struct ft_reserve);
 517         cxt->rgn[FT_STRUCT].size = 4;
 518         cxt->rgn[FT_STRINGS].start = blob + max_size;
 519         cxt->rgn[FT_STRINGS].size = 0;
 520
 521         /* init rsvmap and struct */
 522         pres->start = 0;
 523         pres->len = 0;
 524         *(u32 *) p = cpu_to_be32(OF_DT_END);
 525
 526         cxt->str_anchor = blob;
 527 }
 528
 529 /* open up an existing blob to be examined or modified */
 530 int ft_open(struct ft_cxt *cxt, void *blob, unsigned int max_size,
 531                 unsigned int max_find_device,
 532                 void *(*realloc_fn) (void *, unsigned long))
 533 {
 534         struct boot_param_header *bph = blob;
 535
 536         /* can't cope with version < 16 */
 537         if (be32_to_cpu(bph->version) < 16)
 538                 return -1;
 539
 540         /* clear the cxt */
 541         memset(cxt, 0, sizeof(*cxt));
 542
 543         /* alloc node_tbl to track node ptrs returned by ft_find_device */
 544         ++max_find_device;
 545         cxt->node_tbl = realloc_fn(NULL, max_find_device * sizeof(char *));
 546         if (!cxt->node_tbl)
 547                 return -1;
 548         memset(cxt->node_tbl, 0, max_find_device * sizeof(char *));
 549         cxt->node_max = max_find_device;
 550         cxt->nodes_used = 1;    /* don't use idx 0 b/c looks like NULL */
 551
 552         cxt->bph = bph;
 553         cxt->max_size = max_size;
 554         cxt->realloc = realloc_fn;
 555
 556         cxt->rgn[FT_RSVMAP].start = blob + be32_to_cpu(bph->off_mem_rsvmap);
 557         cxt->rgn[FT_RSVMAP].size = rsvmap_size(cxt);
 558         cxt->rgn[FT_STRUCT].start = blob + be32_to_cpu(bph->off_dt_struct);
 559         cxt->rgn[FT_STRUCT].size = struct_size(cxt);
 560         cxt->rgn[FT_STRINGS].start = blob + be32_to_cpu(bph->off_dt_strings);
 561         cxt->rgn[FT_STRINGS].size = be32_to_cpu(bph->dt_strings_size);
 562         /* Leave as '0' to force first ft_make_space call to do a ft_reorder
 563          * and move dt to an area allocated by realloc.
 564         cxt->isordered = ft_ordered(cxt);
 565         */
 566
 567         cxt->p = cxt->rgn[FT_STRUCT].start;
 568         cxt->str_anchor = cxt->rgn[FT_STRINGS].start;
 569
 570         return 0;
 571 }
 572
 573 /* add a reserver physical area to the rsvmap */
 574 int ft_add_rsvmap(struct ft_cxt *cxt, u64 physaddr, u64 size)
 575 {
 576         char *p;
 577         struct ft_reserve *pres;
 578
 579         p = cxt->rgn[FT_RSVMAP].start + cxt->rgn[FT_RSVMAP].size
 580                 - sizeof(struct ft_reserve);
 581         if (!ft_make_space(cxt, &p, FT_RSVMAP, sizeof(struct ft_reserve)))
 582                 return -1;
 583
 584         pres = (struct ft_reserve *)p;
 585         pres->start = cpu_to_be64(physaddr);
 586         pres->len = cpu_to_be64(size);
 587
 588         return 0;
 589 }
 590
 591 void ft_begin_tree(struct ft_cxt *cxt)
 592 {
 593         cxt->p = cxt->rgn[FT_STRUCT].start;
 594 }
 595
 596 void ft_end_tree(struct ft_cxt *cxt)
 597 {
 598         struct boot_param_header *bph = cxt->bph;
 599         char *p, *oldstr, *str, *endp;
 600         unsigned long ssize;
 601         int adj;
 602
 603         if (!cxt->isordered)
 604                 return;         /* we haven't touched anything */
 605
 606         /* adjust string offsets */
 607         oldstr = cxt->rgn[FT_STRINGS].start;
 608         adj = cxt->str_anchor - oldstr;
 609         if (adj)
 610                 adjust_string_offsets(cxt, adj);
 611
 612         /* make strings end on 8-byte boundary */
 613         ssize = cxt->rgn[FT_STRINGS].size;
 614         endp = (char *)_ALIGN((unsigned long)cxt->rgn[FT_STRUCT].start
 615                         + cxt->rgn[FT_STRUCT].size + ssize, 8);
 616         str = endp - ssize;
 617
 618         /* move strings down to end of structs */
 619         memmove(str, oldstr, ssize);
 620         cxt->str_anchor = str;
 621         cxt->rgn[FT_STRINGS].start = str;
 622
 623         /* fill in header fields */
 624         p = (char *)bph;
 625         bph->totalsize = cpu_to_be32(endp - p);
 626         bph->off_mem_rsvmap = cpu_to_be32(cxt->rgn[FT_RSVMAP].start - p);
 627         bph->off_dt_struct = cpu_to_be32(cxt->rgn[FT_STRUCT].start - p);
 628         bph->off_dt_strings = cpu_to_be32(cxt->rgn[FT_STRINGS].start - p);
 629         bph->dt_strings_size = cpu_to_be32(ssize);
 630 }
 631
 632 void *ft_find_device(struct ft_cxt *cxt, const char *srch_path)
 633 {
 634         char *node;
 635
 636         /* require absolute path */
 637         if (srch_path[0] != '/')
 638                 return NULL;
 639         node = ft_find_descendent(cxt, cxt->rgn[FT_STRUCT].start, srch_path);
 640         return ft_node_add(cxt, node);
 641 }
 642
 643 void *ft_find_descendent(struct ft_cxt *cxt, void *top, const char *srch_path)
 644 {
 645         struct ft_atom atom;
 646         char *p;
 647         const char *cp, *q;
 648         int cl;
 649         int depth = -1;
 650         int dmatch = 0;
 651         const char *path_comp[FT_MAX_DEPTH];
 652
 653         cp = srch_path;
 654         cl = 0;
 655         p = top;
 656
 657         while ((p = ft_next(cxt, p, &atom)) != NULL) {
 658                 switch (atom.tag) {
 659                 case OF_DT_BEGIN_NODE:
 660                         ++depth;
 661                         if (depth != dmatch)
 662                                 break;
 663                         cxt->genealogy[depth] = atom.data;
 664                         cxt->genealogy[depth + 1] = NULL;
 665                         if (depth && !(strncmp(atom.name, cp, cl) == 0
 666                                         && (atom.name[cl] == '/'
 667                                                 || atom.name[cl] == '\0'
 668                                                 || atom.name[cl] == '@')))
 669                                 break;
 670                         path_comp[dmatch] = cp;
 671                         /* it matches so far, advance to next path component */
 672                         cp += cl;
 673                         /* skip slashes */
 674                         while (*cp == '/')
 675                                 ++cp;
 676                         /* we're done if this is the end of the string */
 677                         if (*cp == 0)
 678                                 return atom.data;
 679                         /* look for end of this component */
 680                         q = strchr(cp, '/');
 681                         if (q)
 682                                 cl = q - cp;
 683                         else
 684                                 cl = strlen(cp);
 685                         ++dmatch;
 686                         break;
 687                 case OF_DT_END_NODE:
 688                         if (depth == 0)
 689                                 return NULL;
 690                         if (dmatch > depth) {
 691                                 --dmatch;
 692                                 cl = cp - path_comp[dmatch] - 1;
 693                                 cp = path_comp[dmatch];
 694                                 while (cl > 0 && cp[cl - 1] == '/')
 695                                         --cl;
 696                         }
 697                         --depth;
 698                         break;
 699                 }
 700         }
 701         return NULL;
 702 }
 703
 704 void *ft_get_parent(struct ft_cxt *cxt, const void *phandle)
 705 {
 706         void *node;
 707         int d;
 708         struct ft_atom atom;
 709         char *p;
 710
 711         node = ft_node_ph2node(cxt, phandle);
 712         if (node == NULL)
 713                 return NULL;
 714
 715         for (d = 0; cxt->genealogy[d] != NULL; ++d)
 716                 if (cxt->genealogy[d] == node)
 717                         return cxt->genealogy[d > 0 ? d - 1 : 0];
 718
 719         /* have to do it the hard way... */
 720         p = cxt->rgn[FT_STRUCT].start;
 721         d = 0;
 722         while ((p = ft_next(cxt, p, &atom)) != NULL) {
 723                 switch (atom.tag) {
 724                 case OF_DT_BEGIN_NODE:
 725                         cxt->genealogy[d] = atom.data;
 726                         if (node == atom.data) {
 727                                 /* found it */
 728                                 cxt->genealogy[d + 1] = NULL;
 729                                 return d > 0 ? cxt->genealogy[d - 1] : node;
 730                         }
 731                         ++d;
 732                         break;
 733                 case OF_DT_END_NODE:
 734                         --d;
 735                         break;
 736                 }
 737         }
 738         return NULL;
 739 }
 740
 741 int ft_get_prop(struct ft_cxt *cxt, const void *phandle, const char *propname,
 742                 void *buf, const unsigned int buflen)
 743 {
 744         struct ft_atom atom;
 745         void *node;
 746         char *p;
 747         int depth;
 748         unsigned int size;
 749
 750         node = ft_node_ph2node(cxt, phandle);
 751         if (node == NULL)
 752                 return -1;
 753
 754         depth = 0;
 755         p = (char *)node;
 756
 757         while ((p = ft_next(cxt, p, &atom)) != NULL) {
 758                 switch (atom.tag) {
 759                 case OF_DT_BEGIN_NODE:
 760                         ++depth;
 761                         break;
 762                 case OF_DT_PROP:
 763                         if ((depth != 1) || strcmp(atom.name, propname))
 764                                 break;
 765                         size = min(atom.size, buflen);
 766                         memcpy(buf, atom.data, size);
 767                         return atom.size;
 768                 case OF_DT_END_NODE:
 769                         if (--depth <= 0)
 770                                 return -1;
 771                 }
 772         }
 773         return -1;
 774 }
 775
 776 int ft_set_prop(struct ft_cxt *cxt, const void *phandle, const char *propname,
 777                 const void *buf, const unsigned int buflen)
 778 {
 779         struct ft_atom atom;
 780         void *node;
 781         char *p, *next;
 782         int nextra, depth;
 783
 784         node = ft_node_ph2node(cxt, phandle);
 785         if (node == NULL)
 786                 return -1;
 787
 788         depth = 0;
 789         p = node;
 790
 791         while ((next = ft_next(cxt, p, &atom)) != NULL) {
 792                 switch (atom.tag) {
 793                 case OF_DT_BEGIN_NODE:
 794                         ++depth;
 795                         break;
 796                 case OF_DT_END_NODE:
 797                         if (--depth > 0)
 798                                 break;
 799                         /* haven't found the property, insert here */
 800                         cxt->p = p;
 801                         return ft_prop(cxt, propname, buf, buflen);
 802                 case OF_DT_PROP:
 803                         if ((depth != 1) || strcmp(atom.name, propname))
 804                                 break;
 805                         /* found an existing property, overwrite it */
 806                         nextra = _ALIGN(buflen, 4) - _ALIGN(atom.size, 4);
 807                         cxt->p = atom.data;
 808                         if (nextra && !ft_make_space(cxt, &cxt->p, FT_STRUCT,
 809                                                 nextra))
 810                                 return -1;
 811                         *(u32 *) (cxt->p - 8) = cpu_to_be32(buflen);
 812                         ft_put_bin(cxt, buf, buflen);
 813                         return 0;
 814                 }
 815                 p = next;
 816         }
 817         return -1;
 818 }
 819
 820 int ft_del_prop(struct ft_cxt *cxt, const void *phandle, const char *propname)
 821 {
 822         struct ft_atom atom;
 823         void *node;
 824         char *p, *next;
 825         int size;
 826
 827         node = ft_node_ph2node(cxt, phandle);
 828         if (node == NULL)
 829                 return -1;
 830
 831         p = node;
 832         while ((next = ft_next(cxt, p, &atom)) != NULL) {
 833                 switch (atom.tag) {
 834                 case OF_DT_BEGIN_NODE:
 835                 case OF_DT_END_NODE:
 836                         return -1;
 837                 case OF_DT_PROP:
 838                         if (strcmp(atom.name, propname))
 839                                 break;
 840                         /* found the property, remove it */
 841                         size = 12 + -_ALIGN(atom.size, 4);
 842                         cxt->p = p;
 843                         if (!ft_make_space(cxt, &cxt->p, FT_STRUCT, -size))
 844                                 return -1;
 845                         return 0;
 846                 }
 847                 p = next;
 848         }
 849         return -1;
 850 }
 851
 852 void *ft_create_node(struct ft_cxt *cxt, const void *parent, const char *path)
 853 {
 854         struct ft_atom atom;
 855         char *p, *next;
 856         int depth = 0;
 857
 858         p = cxt->rgn[FT_STRUCT].start;
 859         while ((next = ft_next(cxt, p, &atom)) != NULL) {
 860                 switch (atom.tag) {
 861                 case OF_DT_BEGIN_NODE:
 862                         ++depth;
 863                         if (depth == 1 && strcmp(atom.name, path) == 0)
 864                                 /* duplicate node path, return error */
 865                                 return NULL;
 866                         break;
 867                 case OF_DT_END_NODE:
 868                         --depth;
 869                         if (depth > 0)
 870                                 break;
 871                         /* end of node, insert here */
 872                         cxt->p = p;
 873                         ft_begin_node(cxt, path);
 874                         ft_end_node(cxt);
 875                         return p;
 876                 }
 877                 p = next;
 878         }
 879         return NULL;
 880 }