[parisc-linux] RFC: I/O tree design

[parisc-linux] RFC: I/O tree design

[Ryan Bradetich]

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

Re: [parisc-linux] RFC: I/O tree design

[Matthew Wilcox]

On Sat, Feb 03, 2001 at 12:17:52AM -0700, Ryan Bradetich wrote:
> 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.

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.

> 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.

> This proposal also calls for a special "root" node at

And you don't ned a root node, just siblings.

-- 
Revolutions do not require corporate support.

Re: [parisc-linux] RFC: I/O tree design

[Ryan Bradetich]

Matthew Wilcox wrote:

> On Sat, Feb 03, 2001 at 12:17:52AM -0700, Ryan Bradetich wrote:
> > 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.
>
> 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?


> > 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?

> > 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


> --
> Revolutions do not require corporate support.
>
> _______________________________________________
> parisc-linux mailing list
> parisc-linux@lists.parisc-linux.org
> http://lists.parisc-linux.org/cgi-bin/mailman/listinfo/parisc-linux

Re: [parisc-linux] RFC: I/O tree design

[Grant Grundler]

Ryan Bradetich wrote:
> 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.

...
> 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

Re: [parisc-linux] RFC: I/O tree design

[Grant Grundler]

Matthew Wilcox wrote:
...
> 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.

> > 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

Re: [parisc-linux] RFC: I/O tree design

[Matthew Wilcox]

On Mon, Feb 05, 2001 at 10:34:48AM -0800, Grant Grundler wrote:
> Matthew Wilcox wrote:
> ...
> > 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.

> 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.

-- 
Revolutions do not require corporate support.

Re: [parisc-linux] RFC: I/O tree design

[Grant Grundler]

Matthew Wilcox wrote:
...
> I was thinking along the lines of:
...
> and then use the pci_bus sysdata to point to the struct hp_device which
> is the parent of this pci_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.

> 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.

> 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

Re: [parisc-linux] RFC: I/O tree design

[Grant Grundler]

Grant Grundler wrote:
> 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