RFC: I/O tree design
Hello parisc-linux hackers,
Here is my proposal for phase 2 of the I/O tree for parisc-linux. This proposal covers the internal structure of the I/O tree itself. I am not providing a patch at this time, because I want to make sure the idea is sound before we start discussing the implimentation details of the patch.
[Note: This proposal is a bit rough and could use some re-working to make it flow better, but I would rather spend my time discussing design ideas and writing code then polishing up the design proposal].
Currently the all the "discovered" devices are either found one of the three following ways:
1. Firmware tells us about the device.
2. Probing in known locations and hoping to find a device.
3. An architect-ed bus walk.
The previous patch for walking the system bus is my first attempt at an bus walk on the system bus. This design proposal is independent of the bus walk patch, but eventually the bus walk code will be needed to fill in the missing nodes in the I/O tree.
Currently all the "discovered" I/O devices are stored in a fixed size array which contains up to 64 devices. This fixed size array has already been established and is known to work, so this proposal does not attempt to replace the fixed size array, but instead uses indexes within the struct hp_device to create the logical I/O tree.
To create the logical I/O tree, three u16 values will be added to the struct hp_device which will contain the index into the fixed array for the logical parent, sibling, and child relationship. I chose a u16 value over the u8 value because it allows future expansion of the device array and I want to reserve the largest value for marking the index uninitialized. The following relationships are defined below:
Parent: This index is always set to device controlling the bus the I/O node exists on. [Note: Just because Node A parent is Node B does not require Node B's child to be Node A]. The device controlling the I/O node is always one of these three components:
- Central Bus
- Bus Converter
- Bus Adapter
The parent index is a quick way to determine which devices are between the given node and the central bus.
Sibling: This index always points to the next device that exists on the same bus. [Note: The list of devices is NOT a doubly linked list. Use parent->child to start at the head of the one-way linked list]. The sibling pointers are useful for performing an action to every device that exists on a given bus.
Child: This index is only set to a valid node if the current node is the Central bus, a Bus Converter, or a Bus adapter. When this index is set to a valid node, it points to the head of the sibling list containing all valid nodes for the given bus.
This proposal also calls for a special "root" node at index 0 of the device array. The root node is the starting point of the I/O tree and does not have a parent, nor any siblings. The root node has a single child pointer which points to the head of the sibling list for the system bus. Existing code needs to be modified that uses the device array to ignore the element at index 0 unless it is using the the device array as a logical I/O tree.
Here is a sample ASCII drawing of a theoretical I/O tree as envisioned by this proposal. I have taken care to make sure the pointer relationship by using arrows to point the directions the pointers are valid for.
+------+ | Root |<- - - -+ +------+ | /|\ | | | \|/ | +------+ +------+ | Node |---->| Node |<- - - - - - - - - - + +------+ +------+<- - - -+ | /|\ /|\ | | | | | | \|/ \|/ | | +------+ +------+ +------+ +------+ | Node | | Node |---->| Node |---->| Node | +------+ +------+ +------+ +------+
Summary:
This phase of the I/O tree design is just to make sure the I/O tree design itself is sound. I will need to add three u16 values into struct hp_device to logically the tree in the device array. This design proposal does not include how to initialize and setup the parent, sibling, and child pointers once they have been added to the struct hp_device, nor does it cover any additional fields that may have to be added to logically connect the devices to form the I/O tree. I wanted to make sure the I/O tree design was sound before I started designing how to initialize the tree from the given devices.
Any feedback, comments, questions, etc is greatly appreciated.
Thanks,
- Ryan
Quoted 6 lines · Ryan Bradetich
Currently all the "discovered" I/O devices are stored in a fixed size array which contains up to 64 devices. This fixed size array has already been established and is known to work, so this proposal does not attempt to replace the fixed size array, but instead uses indexes within the struct
hp_deviceto create the logical I/O tree.
I think you need to be braver. Kill the fixed size array. kmalloc each struct and use pointers to reference between them. If you want, you can use the doubly-linked-list macros in <linux/list.h>, but i suspect self-managed singly-linked-lists will be more appropriate for this. After all, it's not like the tree gets modified on a regular basis.
Quoted 5 lines
Child: This index is only set to a valid node if the current node is the Central bus, a Bus Converter, or a Bus adapter. When this index is set to a valid node, it points to the head of the sibling list containing all valid nodes for the given bus.
One advantage of doing this is that `Child' could be a pointer to a PCI bus.
Quoted 1 line
This proposal also calls for a special "root" node at
And you don't ned a root node, just siblings.
Signature · 1 line
Revolutions do not require corporate support.
Quoted 8 lines · Matthew Wilcox
Quoted 6 lines · Ryan Bradetich
Currently all the "discovered" I/O devices are stored in a fixed size array which contains up to 64 devices. This fixed size array has already been established and is known to work, so this proposal does not attempt to replace the fixed size array, but instead uses indexes within the struct
hp_deviceto create the logical I/O tree.
Quoted 5 lines
I think you need to be braver. Kill the fixed size array. kmalloc each struct and use pointers to reference between them. If you want, you can use the doubly-linked-list macros in <
linux/list.h>, but i suspect self-managed singly-linked-lists will be more appropriate for this. After all, it's not like the tree gets modified on a regular basis.
Ok, I was bored today so I worked on removing the fixed array and replacing it with a linked list structure using kmalloc. After I got this compiled and linked to work with the kernel it promply paniced on the first kmalloc statement. Searching around in arch/parisc/kernel/setup.c I found this comment that fits the description of my kmalloc problem:
/*
** KLUGE ALERT!
**
** We *really* should be using a combination of request_resource() ** and request_region()! But request_region() requires kmalloc since ** returns a new struct resource. And kmalloc just isn't available ** until after mem_init() is called from start_kernel(). **
** FIXME: assume contiguous memory initially.
** Additional chunks of memory might be added to
sysram_resource.sibling.
*/
The do_inventory call is made before mem_init() is called which explains why kmalloc cause the machine to panic.
So I am looking for some guidence here .... do we want to move the do_inventory call after the mem_init call ... or do we want to stick with the fixed size array still?
Quoted 8 lines
Quoted 5 lines
Child: This index is only set to a valid node if the current node is the Central bus, a Bus Converter, or a Bus adapter. When this index is set to a valid node, it points to the head of the sibling list containing all valid nodes for the given bus.
One advantage of doing this is that `Child' could be a pointer to a PCI bus.
I like this proposal ... that is a good justification for me to move to a dynamic tree instead of a fixed array :) Currently I have no idea how the interface would look to hook all the busses togeather via a common I/O tree. Is their a common bus interface that I should be matching in my I/O tree implimentation for parisc-linux?
Quoted 3 lines
Quoted 1 line
This proposal also calls for a special "root" node at
And you don't ned a root node, just siblings.
That would be nice :)
Thanks for the feedback willy. I have already started hacking in an I/O tree into my local tree using the fixed array just to work out some of the design issues, and problems to over come. I will probably scratch this attempt once I get a better understanding of what I am doing.
- Ryan
Quoted 7 lines
--
Revolutions do not require corporate support._______________________________________________
parisc-linux mailing list
[email protected]
http://lists.parisc-linux.org/cgi-bin/mailman/listinfo/parisc-linux
Matthew Wilcox wrote:
...
Quoted 2 lines
One advantage of doing this is that `Child' could be a pointer to a PCI bus.
I don't think I want that. PCI busses have their own heirarchy and I would much rather keep them quite seperate. At least for the moment I would. Future abstraction of native bus access and mgt methods might make this more interesting.
Quoted 3 lines
Quoted 1 line
This proposal also calls for a special "root" node at
And you don't ned a root node, just siblings.
You are right - PCI starts out as a bunch of siblings too. If it makes the code simpler to have a root node, then I think it's ok to keep it.
Sometimes, it's convenient to think of the memory controller(s) as the "parent" of the central bus and memory banks as children (just like CPU would also be a child). This model works under ccNuma as well with memory at multiple levels in the I/O tree.
Note that HPUX walks the "PA I/O tree" in a depth-first fashion like PCI as well. So I expect the "siblings-only for central bus" would be ok.
grant
Grant Grundler
parisc-linux {PCI|IOMMU|SMP} hacker
+1.408.447.7253
Quoted 9 lines · Grant Grundler
Matthew Wilcox wrote:
...Quoted 2 lines
One advantage of doing this is that `Child' could be a pointer to a PCI bus.
I don't think I want that. PCI busses have their own heirarchy and I would much rather keep them quite seperate. At least for the moment I would. Future abstraction of native bus access and mgt methods might make this more interesting.
I was thinking along the lines of:
struct hp_bus;
struct hp_device {
[...]
int bus_type;
union {
struct pci_bus *pci;
struct hp_bus *hp;
} child;
};and then use the pci_bus sysdata to point to the struct hp_device which is the parent of this pci_bus.
Rather than try to abuse the `parent' entry in the pci_bus.
Quoted 4 lines
Sometimes, it's convenient to think of the memory controller(s) as the "parent" of the central bus and memory banks as children (just like CPU would also be a child). This model works under ccNuma as well with memory at multiple levels in the I/O tree.
Yeah, I was thinking about that. In some of the larger systems (say, N class), there's no real central point at which to base the bus walk, other than the Stretch memory controller.
Signature · 1 line
Revolutions do not require corporate support.
Matthew Wilcox wrote:
...
Quoted 1 line
I was thinking along the lines of:
...
Quoted 2 lines
and then use the
pci_bussysdata to point to the structhp_devicewhich is the parent of thispci_bus.
Several levels of indirection are needed here. Currently, we only store PCI bus host adapter (eg dino or elroy) pointer here. We need to store "per device" DMA parameters here as well and similar cruft. ie something like:
struct pa_devinfo {
void * pa_iommu;
void * pa_hba;
}((pa_sysinfo *) pci_device->sysdata)
This should work for both PCI and "PCI-like" bus devices. pa_hba* would point to PCI bus info for dino/elroy.
Quoted 1 line
Rather than try to abuse the `parent' entry in the
pci_bus.
Right. parent field can never point to anything that's not a struct pci_bus. The reason is PCI generic code walks *up* the tree and terminates on a NULL ptr.
Quoted 3 lines
Yeah, I was thinking about that. In some of the larger systems (say, N class), there's no real central point at which to base the bus walk, other than the Stretch memory controller.
Two comments:
1) IMHO N-class really isn't that big.
2) It does have a "central bus" (Merced). Actually two of them but they are peers and for most cases look like one.
grant
Grant Grundler
parisc-linux {PCI|IOMMU|SMP} hacker
+1.408.447.7253
Quoted 6 lines · Grant Grundler
struct pa_devinfo { void * pa_iommu; void * pa_hba; }((
pa_sysinfo*)pci_device->sysdata)
I meant to write
((pa_devinfo *) pci_device->sysdata)->pa_iommu
I also thought the pa_devinfo struct could hold flags/info which describes device and driver DMA behaviors not passed in to pci_map_single(). I don't expect device drivers to be modified to manipulate this flags/info fields unless it is designed to be arch- independent.
Stuff like this is normally stored in the HPUX I/O tree associated with specific nodes (and thus visible to parents). Note that I only expect the parisc-linux "I/O tree" to only deal with PA I/O devices.
grant
Grant Grundler
parisc-linux {PCI|IOMMU|SMP} hacker
+1.408.447.7253
Quoted 1 line · Ryan Bradetich
Here is my proposal for phase 2 of the I/O tree for parisc-linux.
Overall, this sounds ok to me.
Just a nit WRT to terminology.
...
Quoted 6 lines
This proposal also calls for a special "root" node at index 0 of the device array. The root node is the starting point of the I/O tree and does not have a parent, nor any siblings. The root node has a single child pointer which points to the head of the sibling list for the system bus.
I would call the "root" node the "parent psuedo-bus adapter" (or something like that) of the central bus. It's special because it generally won't represent a physical PA I/O device. But it does contain a "lower port address" - the fixed PA IO address your previous bus-walk patch started with.
The idea here is you can pass "hp_device *" to your PA bus walk code and not have seperate code for central bus or GSC bus. The bus walk code could use the "lower port address" as a new starting point to poke around.
thanks,
grant
Grant Grundler
parisc-linux {PCI|IOMMU|SMP} hacker
+1.408.447.7253