i386/libsaio/device_tree.c

   1 /*
   2  * Copyright (c) 2005 Apple Computer, Inc.  All Rights Reserved.
   3  */
   4
   5 #if 1
   6 /*
   7
   8  Structures for a Flattened Device Tree
   9  */
  10
  11 #define kPropNameLength 32
  12
  13 typedef struct DeviceTreeNodeProperty {
  14     char                name[kPropNameLength];  // NUL terminated property name
  15     unsigned long       length;         // Length (bytes) of folloing prop value
  16                                         //  unsigned long       value[1];       // Variable length value of property
  17                                         // Padded to a multiple of a longword?
  18 } DeviceTreeNodeProperty;
  19
  20 typedef struct OpaqueDTEntry {
  21     unsigned long       nProperties;    // Number of props[] elements (0 => end)
  22     unsigned long       nChildren;      // Number of children[] elements
  23                                         //  DeviceTreeNodeProperty      props[];// array size == nProperties
  24                                         //  DeviceTreeNode      children[];     // array size == nChildren
  25 } DeviceTreeNode;
  26
  27 typedef char DTPropertyNameBuf[32];
  28 /* Entry Name Definitions (Entry Names are C-Strings)*/
  29 enum {
  30     kDTMaxEntryNameLength           = 31    /* Max length of a C-String Entry Name (terminator not included) */
  31 };
  32
  33 /* length of DTEntryNameBuf = kDTMaxEntryNameLength +1*/
  34 typedef char DTEntryNameBuf[32];
  35 #endif
  36
  37 #include "libsaio.h"
  38 #include "device_tree.h"
  39
  40 #if DEBUG
  41 #define DPRINTF(args...) printf(args)
  42 #else
  43 #define DPRINTF(args...)
  44 #endif
  45
  46
  47 void
  48 DT__PrintTree(Node *node);
  49
  50 #define RoundToLong(x)  (((x) + 3) & ~3)
  51
  52 static struct _DTSizeInfo {
  53     uint32_t numNodes;
  54     uint32_t numProperties;
  55     uint32_t totalPropertySize;
  56 } DTInfo;
  57
  58 #define kAllocSize 4096
  59
  60 static Node *rootNode;
  61
  62 static Node *freeNodes, *allocedNodes;
  63 static Property *freeProperties, *allocedProperties;
  64
  65 Property *
  66 DT__AddProperty(Node *node, char *name, uint32_t length, void *value)
  67 {
  68     Property *prop;
  69
  70     DPRINTF("DT__AddProperty([Node '%s'], '%s', %d, 0x%x)\n", DT__GetName(node), name, length, value);
  71     if (freeProperties == NULL) {
  72         void *buf = malloc(kAllocSize);
  73         int i;
  74
  75         DPRINTF("Allocating more free properties\n");
  76         if (buf == 0) return 0;
  77         bzero(buf, kAllocSize);
  78         // Use the first property to record the allocated buffer
  79         // for later freeing.
  80         prop = (Property *)buf;
  81         prop->next = allocedProperties;
  82         allocedProperties = prop;
  83         prop->value = buf;
  84         prop++;
  85         for (i=1; i<(kAllocSize / sizeof(Property)); i++) {
  86             prop->next = freeProperties;
  87             freeProperties = prop;
  88             prop++;
  89         }
  90     }
  91     prop = freeProperties;
  92     freeProperties = prop->next;
  93
  94     prop->name = name;
  95     prop->length = length;
  96     prop->value = value;
  97
  98     // Always add to end of list
  99     if (node->properties == 0) {
 100         node->properties = prop;
 101     } else {
 102         node->last_prop->next = prop;
 103     }
 104     node->last_prop = prop;
 105     prop->next = 0;
 106
 107     DPRINTF("Done [0x%x]\n", prop);
 108
 109     DTInfo.numProperties++;
 110     DTInfo.totalPropertySize += RoundToLong(length);
 111
 112     return prop;
 113 }
 114
 115 Node *
 116 DT__AddChild(Node *parent, char *name)
 117 {
 118     Node *node;
 119
 120     if (freeNodes == NULL) {
 121         void *buf = malloc(kAllocSize);
 122         int i;
 123
 124         DPRINTF("Allocating more free nodes\n");
 125         if (buf == 0) return 0;
 126         bzero(buf, kAllocSize);
 127         node = (Node *)buf;
 128         // Use the first node to record the allocated buffer
 129         // for later freeing.
 130         node->next = allocedNodes;
 131         allocedNodes = node;
 132         node->children = (Node *)buf;
 133         node++;
 134         for (i=1; i<(kAllocSize / sizeof(Node)); i++) {
 135             node->next = freeNodes;
 136             freeNodes = node;
 137             node++;
 138         }
 139     }
 140     DPRINTF("DT__AddChild(0x%x, '%s')\n", parent, name);
 141     node = freeNodes;
 142     freeNodes = node->next;
 143     DPRINTF("Got free node 0x%x\n", node);
 144     DPRINTF("prop = 0x%x, children = 0x%x, next = 0x%x\n", node->properties, node->children, node->next);
 145
 146     if (parent == NULL) {
 147         rootNode = node;
 148         node->next = 0;
 149     } else {
 150         node->next = parent->children;
 151         parent->children = node;
 152     }
 153     DTInfo.numNodes++;
 154     DT__AddProperty(node, "name", strlen(name) + 1, name);
 155     return node;
 156 }
 157
 158 void
 159 DT__FreeProperty(Property *prop)
 160 {
 161     prop->next = freeProperties;
 162     freeProperties = prop;
 163 }
 164 void
 165 DT__FreeNode(Node *node)
 166 {
 167     node->next = freeNodes;
 168     freeNodes = node;
 169 }
 170
 171 void
 172 DT__Initialize(void)
 173 {
 174     DPRINTF("DT__Initialize\n");
 175
 176     freeNodes = 0;
 177     allocedNodes = 0;
 178     freeProperties = 0;
 179     allocedProperties = 0;
 180
 181     DTInfo.numNodes = 0;
 182     DTInfo.numProperties = 0;
 183     DTInfo.totalPropertySize = 0;
 184
 185     rootNode = DT__AddChild(NULL, "/");
 186     DPRINTF("DT__Initialize done\n");
 187 }
 188
 189 /*
 190  * Free up memory used by in-memory representation
 191  * of device tree.
 192  */
 193 void
 194 DT__Finalize(void)
 195 {
 196     Node *node;
 197     Property *prop;
 198
 199     DPRINTF("DT__Finalize\n");
 200     for (prop = allocedProperties; prop != NULL; prop = prop->next) {
 201         free(prop->value);
 202     }
 203     allocedProperties = NULL;
 204     freeProperties = NULL;
 205
 206     for (node = allocedNodes; node != NULL; node = node->next) {
 207         free((void *)node->children);
 208     }
 209     allocedNodes = NULL;
 210     freeNodes = NULL;
 211     rootNode = NULL;
 212
 213     // XXX leaks any created strings
 214
 215     DTInfo.numNodes = 0;
 216     DTInfo.numProperties = 0;
 217     DTInfo.totalPropertySize = 0;
 218 }
 219
 220 static void *
 221 FlattenNodes(Node *node, void *buffer)
 222 {
 223     Property *prop;
 224     DeviceTreeNode *flatNode;
 225     DeviceTreeNodeProperty *flatProp;
 226     int count;
 227
 228     if (node == 0) return buffer;
 229
 230     flatNode = (DeviceTreeNode *)buffer;
 231     buffer += sizeof(DeviceTreeNode);
 232
 233     for (count = 0, prop = node->properties; prop != 0; count++, prop = prop->next) {
 234         flatProp = (DeviceTreeNodeProperty *)buffer;
 235         strcpy(flatProp->name, prop->name);
 236         flatProp->length = prop->length;
 237         buffer += sizeof(DeviceTreeNodeProperty);
 238         bcopy(prop->value, buffer, prop->length);
 239         buffer += RoundToLong(prop->length);
 240     }
 241     flatNode->nProperties = count;
 242
 243     for (count = 0, node = node->children; node != 0; count++, node = node->next) {
 244         buffer = FlattenNodes(node, buffer);
 245     }
 246     flatNode->nChildren = count;
 247
 248     return buffer;
 249 }
 250
 251 /*
 252  * Flatten the in-memory representation of the device tree
 253  * into a binary DT block.
 254  * To get the buffer size needed, call with result = 0.
 255  * To have a buffer allocated for you, call with *result = 0.
 256  * To use your own buffer, call with *result = &buffer.
 257  */
 258
 259 void
 260 DT__FlattenDeviceTree(void **buffer_p, uint32_t *length)
 261 {
 262     uint32_t totalSize;
 263     void *buf;
 264
 265     DPRINTF("DT__FlattenDeviceTree(0x%x, 0x%x)\n", buffer_p, length);
 266     if (buffer_p) DT__PrintTree(rootNode);
 267
 268     totalSize = DTInfo.numNodes * sizeof(DeviceTreeNode) +
 269         DTInfo.numProperties * sizeof(DeviceTreeNodeProperty) +
 270         DTInfo.totalPropertySize;
 271
 272     DPRINTF("Total size 0x%x\n", totalSize);
 273     if (buffer_p != 0) {
 274         if (totalSize == 0) {
 275             buf = 0;
 276         } else {
 277             if (*buffer_p == 0) {
 278                 buf = malloc(totalSize);
 279             } else {
 280                 buf = *buffer_p;
 281             }
 282             bzero(buf, totalSize);
 283
 284             FlattenNodes(rootNode, buf);
 285         }
 286         *buffer_p = buf;
 287     }
 288     if (length)
 289         *length = totalSize;
 290 }
 291
 292 char *
 293 DT__GetName(Node *node)
 294 {
 295     Property *prop;
 296
 297     //DPRINTF("DT__GetName(0x%x)\n", node);
 298     //DPRINTF("Node properties = 0x%x\n", node->properties);
 299     for (prop = node->properties; prop; prop = prop->next) {
 300         //DPRINTF("Prop '%s'\n", prop->name);
 301         if (strcmp(prop->name, "name") == 0) {
 302             return prop->value;
 303         }
 304     }
 305     //DPRINTF("DT__GetName returns 0\n");
 306     return "(null)";
 307 }
 308
 309 Node *
 310 DT__FindNode(char *path, bool createIfMissing)
 311 {
 312     Node *node, *child;
 313     DTPropertyNameBuf nameBuf;
 314     char *bp;
 315     int i;
 316
 317     DPRINTF("DT__FindNode('%s', %d)\n", path, createIfMissing);
 318
 319     // Start at root
 320     node = rootNode;
 321     DPRINTF("root = 0x%x\n", rootNode);
 322
 323     while (node) {
 324         // Skip leading slash
 325         while (*path == '/') path++;
 326
 327         for (i=0, bp = nameBuf; ++i < kDTMaxEntryNameLength && *path && *path != '/'; bp++, path++) *bp = *path;
 328         *bp = '\0';
 329
 330         if (nameBuf[0] == '\0') {
 331             // last path entry
 332             break;
 333         }
 334         DPRINTF("Node '%s'\n", nameBuf);
 335
 336         for (child = node->children; child != 0; child = child->next) {
 337             DPRINTF("Child 0x%x\n", child);
 338             if (strcmp(DT__GetName(child), nameBuf) == 0) {
 339                 break;
 340             }
 341         }
 342         if (child == 0 && createIfMissing) {
 343             DPRINTF("Creating node\n");
 344             char *str = malloc(strlen(nameBuf) + 1);
 345             // XXX this will leak
 346             strcpy(str, nameBuf);
 347
 348             child = DT__AddChild(node, str);
 349         }
 350         node = child;
 351     }
 352     return node;
 353 }
 354
 355 void
 356 DT__PrintNode(Node *node, int level)
 357 {
 358     char spaces[10], *cp = spaces;
 359     Property *prop;
 360
 361     if (level > 9) level = 9;
 362     while (level--) *cp++ = ' ';
 363     *cp = '\0';
 364
 365     printf("%s===Node===\n", spaces);
 366     for (prop = node->properties; prop; prop = prop->next) {
 367         char c = *((char *)prop->value);
 368         if (prop->length < 64 && (
 369             strcmp(prop->name, "name") == 0 ||
 370             (c >= '0' && c <= '9') ||
 371             (c >= 'a' && c <= 'z') ||
 372             (c >= 'A' && c <= 'Z') || c == '_')) {
 373             printf("%s Property '%s' [%d] = '%s'\n", spaces, prop->name, prop->length, prop->value);
 374         } else {
 375             printf("%s Property '%s' [%d] = (data)\n", spaces, prop->name, prop->length);
 376         }
 377     }
 378     printf("%s==========\n", spaces);
 379 }
 380
 381 static void
 382 _PrintTree(Node *node, int level)
 383 {
 384     DT__PrintNode(node, level);
 385     level++;
 386     for (node = node->children; node; node = node->next)
 387         _PrintTree(node, level);
 388 }
 389
 390 void
 391 DT__PrintTree(Node *node)
 392 {
 393     if (node == 0) node = rootNode;
 394     _PrintTree(node, 0);
 395 }
 396
 397 #if DEBUG
 398
 399 void
 400 DT__PrintFlattenedNode(DTEntry entry, int level)
 401 {
 402     char spaces[10], *cp = spaces;
 403     DTPropertyIterator                  propIter;
 404     char *name;
 405     void *prop;
 406     int propSize;
 407
 408     if (level > 9) level = 9;
 409     while (level--) *cp++ = ' ';
 410     *cp = '\0';
 411
 412     printf("%s===Entry %p===\n", spaces, entry);
 413     if (kSuccess != DTCreatePropertyIterator(entry, &propIter)) {
 414         printf("Couldn't create property iterator\n");
 415         return;
 416     }
 417     while( kSuccess == DTIterateProperties( propIter, &name)) {
 418         if(  kSuccess != DTGetProperty( entry, name, &prop, &propSize ))
 419             continue;
 420         printf("%s Property %s = %s\n", spaces, name, prop);
 421     }
 422     DTDisposePropertyIterator(propIter);
 423
 424     printf("%s==========\n", spaces);
 425 }
 426
 427 static void
 428 _PrintFlattenedTree(DTEntry entry, int level)
 429 {
 430     DTEntryIterator entryIter;
 431
 432     PrintFlattenedNode(entry, level);
 433
 434     if (kSuccess != DTCreateEntryIterator(entry, &entryIter)) {
 435             printf("Couldn't create entry iterator\n");
 436             return;
 437     }
 438     level++;
 439     while (kSuccess == DTIterateEntries( entryIter, &entry )) {
 440         _PrintFlattenedTree(entry, level);
 441     }
 442     DTDisposeEntryIterator(entryIter);
 443 }
 444
 445 void
 446 DT__PrintFlattenedTree(DTEntry entry)
 447 {
 448     _PrintFlattenedTree(entry, 0);
 449 }
 450
 451
 452 int
 453 main(int argc, char **argv)
 454 {
 455     DTEntry                             dtEntry;
 456     DTPropertyIterator                  propIter;
 457     DTEntryIterator                     entryIter;
 458     void                                *prop;
 459     int                                 propSize;
 460     char                                *name;
 461     void *flatTree;
 462     uint32_t flatSize;
 463
 464     Node *node;
 465
 466     node = AddChild(NULL, "device-tree");
 467     AddProperty(node, "potato", 4, "foo");
 468     AddProperty(node, "chemistry", 4, "bar");
 469     AddProperty(node, "physics", 4, "baz");
 470
 471     node = AddChild(node, "dev");
 472     AddProperty(node, "one", 4, "one");
 473     AddProperty(node, "two", 4, "two");
 474     AddProperty(node, "three", 6, "three");
 475
 476     node = AddChild(rootNode, "foo");
 477     AddProperty(node, "aaa", 4, "aab");
 478     AddProperty(node, "bbb", 4, "bbc");
 479     AddProperty(node, "cccc", 6, "ccccd");
 480
 481     node = FindNode("/this/is/a/test", 1);
 482     AddProperty(node, "dddd", 12, "abcdefghijk");
 483
 484     printf("In-memory tree:\n\n");
 485
 486     PrintTree(rootNode);
 487
 488     FlattenDeviceTree(&flatTree, &flatSize);
 489
 490     printf("Flat tree = %p, size %d\n", flatTree, flatSize);
 491
 492     dtEntry = (DTEntry)flatTree;
 493
 494     printf("\n\nPrinting flat tree\n\n");
 495
 496     DTInit(dtEntry);
 497
 498     PrintFlattenedTree((DTEntry)flatTree);
 499 #if 0
 500         printf("=== Entry %p ===\n", dtEntry);
 501         if (kSuccess != DTCreatePropertyIterator(dtEntry, &propIter)) {
 502             printf("Couldn't create property iterator\n");
 503             return 1;
 504         }
 505         while( kSuccess == DTIterateProperties( propIter, &name)) {
 506             if(  kSuccess != DTGetProperty( dtEntry, name, &prop, &propSize ))
 507                 continue;
 508             printf(" Property %s = %s\n", name, prop);
 509         }
 510         DTDisposePropertyIterator(propIter);
 511         printf("========\n");
 512
 513     if (kSuccess != DTCreateEntryIterator(dtEntry, &entryIter)) {
 514             printf("Couldn't create entry iterator\n");
 515             return 1;
 516     }
 517     while (kSuccess == DTIterateEntries( entryIter, &dtEntry )) {
 518         printf("=== Entry %p ===\n", dtEntry);
 519
 520         if (kSuccess != DTCreatePropertyIterator(dtEntry, &propIter)) {
 521             printf("Couldn't create property iterator\n");
 522             return 1;
 523         }
 524         while( kSuccess == DTIterateProperties( propIter, &name)) {
 525             if(  kSuccess != DTGetProperty( dtEntry, name, &prop, &propSize ))
 526                 continue;
 527             printf(" Property %s = %s\n", name, prop);
 528         }
 529         DTDisposePropertyIterator(propIter);
 530         printf("========\n");
 531     }
 532     DTDisposeEntryIterator(entryIter);
 533 #endif
 534
 535     return 0;
 536 }
 537
 538 #endif
 539