Global Sources
EE Times-Asia
Stay in touch with EE Times Asia
?
EE Times-Asia > Embedded
?
?
Embedded??

Device tree partitioning for embedded software design

Posted: 26 Nov 2014 ?? ?Print Version ?Bookmark and Share

Keywords:Symmetric multi-processing? OS? multi-core processing? Flattened device trees? partitioning?

Listing 2 shows two Linux OSes as guests, each to be run on one of the cores supported by the hardware platform. Guest 0 has access to UART while GPIO is only available to Guest 1. Both guests share a virtIO-based virtual console device supported by the hypervisor. [4]

The two device tree structures are combined to a get single DTS representation for the tool to process.

?

?

 Listing 2

 Listing 2

Listing 2: Device tree annotations for supervised heterogeneous dual guest configuration.

Figure 2 shows a graphical form of the combined DTS. Nodes in blue come from the master DTS while the yellow nodes represent the data coming from partitioning annotation.

 Device tree structure with annotated data

Figure 2: Device tree structure with annotated data.

The next step is to mark up nodes in the combined device tree shown in figure 2. This is done by traversing the dependency sub-trees formed by the label-reference combination. The device tree compiler assigns a unique ID to every labelled node in the device trees structure. This ID is stored in a property called 'phandle'. When a labelled node is referenced, this phandle can be used to traverse to that node.

Figure 3 shows the dependency graphs for both guests in our use case. Yellow nodes highlight the nodes that would only be valid for guest 0, blue and orange nodes represent the shared nodes, which need to be retained in either guest's device tree blob. The dotted edges indicates the nodes on either side are additional metadata for helping to traverse the dependency graphs, while the solid edges actually link the the device nodes that need to be retained. The dotted blue path circles the device nodes that would be marked up for inclusion in the generated device tree blob for guest 0.

 Device Dependency graphs

Figure 3: Dependency graphs in annotated device tree structure.

Figure 4 shows the resulting device tree structure generated by the partitioning tool. The yellow node represents a new node inserted by the partition tool to configure a virtual console device. The node has been moved from annotated data to the base of the new device tree.

 Device Dependency graphs

Figure 4: Filtered platform information available to one of the guests.

Eliminating tree complexity
Figure 3 shows the dependency subtree of a guest is a directed acyclic graph, with edges indicating that phandle references and vertices are the device nodes. In order to mark all the dependent sub-nodes, one can use the Depth First Search (DFS) [5] algorithm, whose complexity is O(n+m) where n are the vertices and 'm' the edges connecting those vertices. For our case, this complexity is linear with the number of guest OSes in the system as DFS would be repeated for each guest. Filtering and inserting new node(s) adds a constant factor to the complexity.

References
1. G.Likely and J. Boyer A symphony of flavors: Using the device tree to describe embedded hardware
2. Enabling device tree support on ARM platform. http://www.linaro.org/blog/enabling-device-tree-support-on-arm-platforms/
3. Device tree compiler and libfdt sources. http://devicetree.org/Device_Tree_Compiler
4. VirtIO specs. http://ozlabs.org/~rusty/virtio-spec/virtio-0.9.4-vs-0.9.5.pdf
5. Online lecture on directed graphs and DAG. http://www.csl.mtu.edu/cs2321/www/newLectures/28_Directed_Graphs_and_DAG.html

About the author
Faheem Sheikh is a staff engineer in the embedded software division of Mentor Graphics working on embedded virtualisation technology. He has many years of development experience with multi-core high-performance computing systems. He has a PhD in computer engineering from Lahore University of Management Sciences.


?First Page?Previous Page 1???2???3



Article Comments - Device tree partitioning for embedde...
Comments:??
*? You can enter [0] more charecters.
*Verify code:
?
?
Webinars

Seminars

Visit Asia Webinars to learn about the latest in technology and get practical design tips.

?
?
Back to Top