Tree Data Structures

Linux provides a generalized framework to help build data structures in memory. These structures describe the resources available in the system and enable the kernel code to manage and allocate the resources. Significantly, the name of the key structure is resource; it is defined as follows:

struct resource {

resource_size_t start; resource_size_t end; const char *name; unsigned long flags;

struct resource *parent, *sibling, *child;

name stores a string so that the resource can be given a meaningful name. It has no relevance for the kernel but is useful when a resource list (in the proc filesystem) is output in readable form.

The resource itself is characterized by the three parameters below. start and end specify a general area marked by unsigned long numbers; even though theoretically the contents of the two numbers can be interpreted freely, they usually represent an area in an address space. flags enables the resource and its current state to be described more precisely.

Of particular interest are the three pointers to other resource structures. These enable a tree-like hierarchy to be established in which the pointers are often arranged as you will see below.

Figure 6-20 illustrates how the parent, child, and sibling pointers are arranged in a tree structure that is reminiscent of the process network discussed in Chapter 2.

Figure 6-20: Resource management in a tree structure.

The rules for linking the parent, child, and sibling elements are simple.

□ Each child has just one parent.

□ A parent can have any number of children.

□ All children with the same parent are linked on the list of siblings.

The following must be noted when the data structure is represented in memory.

□ Even though there may be a pointer from each child to the parent, there is always only a single pointer from the parent to the first child. All other children can be reconstructed from the sibling list.

□ The pointer to the parent may also be null, in which case there is no higher-level element.

How can this hierarchical structure be used for device drivers? Let us look at the example of a system bus to which a network card is attached. The card supports two outputs, each of which is assigned a specific memory area for data input and output. The bus itself also has a I/O memory area, sections of which are used by the network card.

This scheme fits perfectly into the tree hierarchy. The bus memory area that theoretically occupies the (fictitious) range between 0 and 1,000 acts as the root element (the uppermost parent element). The network card lays claim to the memory area between 100 and 199 and is a child of the root element (the bus itself). The child elements of the network card represent the individual network outputs to which the I/O

ranges from 100 to 149 and from 150 to 199 are assigned. The originally large resource area is repeatedly subdivided into smaller sections, each of which represents a layer of an abstraction model. Consequently, child elements can be used to partition the area into ever smaller and ever more specific sections.

Continue reading here: Requesting Resources

Was this article helpful?

0 0