Re: [PATCH 1/4] PCI: optimize pci_bus_get_depth() by enumerating on pci bus hierachy

[Wei Yang <weiyang@linux.vnet.ibm.com>]

On Tue, Jul 09, 2013 at 01:27:42PM -0600, Bjorn Helgaas wrote:
>On Mon, Jul 8, 2013 at 8:38 PM, Wei Yang <weiyang@linux.vnet.ibm.com> wrote:
>> On Mon, Jul 08, 2013 at 02:46:17PM -0600, Bjorn Helgaas wrote:
>>>On Mon, Jul 1, 2013 at 9:10 AM, Wei Yang <weiyang@linux.vnet.ibm.com> wrote:
>>>> Normally, on one pci bus there would be more devices than pci buses. When
>>>> calculating the depth of pci bus, it would be more time efficient by
>>>> enumerating through the child buses instead of the child devices.
>>>>
>>>> Also by doing so, the code seems more self explaining. Previously, it go
>>>> through the pci devices and check whether a bridge introduce a child bus or
>>>> not, which needs more background knowledge to understand it.
>>>>
>>>> This patch caculating the depth by enumerating on pci bus hierachy in an
>>>> iterative way.
>>>
>>>Your code does have the advantage of not being recursive, but the
>>>original code is significantly shorter and, in my opinion, much more
>>>readable.  This is not in a performance path, so I don't see any
>>>advantage in optimizing.
>>
>> Thanks for your comments~
>>
>> Yes, this doesn't benefit a lot on the performance.
>>
>> The benefit of this code is not only the recursive approach, but on
>> calculating the depth of pci bus tree by iterating on pci bus tree instead of
>> the pci device tree.
>>
>> In my mind, there is less pci bus structrue than the pci device structure, and
>> hope the code would be more self explaining for the audience by going through
>> the pci bus tree to calculate the pci bus tree depth.
>>
>> My original code looks like below. Do you think this one is more friendly to
>> the audience?
>
>Yes.

Thanks for your comment.

If you agree, I will re-sent the patch with this recursive version.

>
>> @@ -1300,21 +1300,19 @@ static void pci_bus_dump_resources(struct pci_bus *bus)
>>  static int __init pci_bus_get_depth(struct pci_bus *bus)
>>  {
>>         int depth = 0;
>> -       struct pci_dev *dev;
>> +       struct pci_bus *child_bus;
>>
>> -       list_for_each_entry(dev, &bus->devices, bus_list) {
>> +       list_for_each_entry(child_bus, &bus->children, node){
>>                 int ret;
>> -               struct pci_bus *b = dev->subordinate;
>> -               if (!b)
>> -                       continue;
>>
>> -               ret = pci_bus_get_depth(b);
>> +               ret = pci_bus_get_depth(child_bus);
>>                 if (ret + 1 > depth)
>>                         depth = ret + 1;
>>         }
>>
>>         return depth;
>>  }
>>
>> And yes again, this change will not bring much improvement for the performance.
>> If this is not good, just ignore the code. :-)
>>
>>>
>>>> Signed-off-by: Wei Yang <weiyang@linux.vnet.ibm.com>
>>>> Reviewed-by: Gavin Shan <shangw@linux.vnet.ibm.com>
>>>> Reviewed-by: Ram Pai <linuxram@us.ibm.com>
>>>> Reviewed-by: Xiao Guangrong <xiaoguangrong@linux.vnet.ibm.com>
>>>> Reviewed-by: Mike Qiu <qiudayu@linux.vnet.ibm.com>
>>>> ---
>>>>  drivers/pci/setup-bus.c |   43 ++++++++++++++++++++++++++++++++-----------
>>>>  1 files changed, 32 insertions(+), 11 deletions(-)
>>>>
>>>> diff --git a/drivers/pci/setup-bus.c b/drivers/pci/setup-bus.c
>>>> index 16abaaa..b333f73 100644
>>>> --- a/drivers/pci/setup-bus.c
>>>> +++ b/drivers/pci/setup-bus.c
>>>> @@ -1299,22 +1299,43 @@ static void pci_bus_dump_resources(struct pci_bus *bus)
>>>>
>>>>  static int __init pci_bus_get_depth(struct pci_bus *bus)
>>>>  {
>>>> -       int depth = 0;
>>>> -       struct pci_dev *dev;
>>>> +       int max_depth, depth;
>>>> +       struct pci_bus *parent, *curr;
>>>> +       struct list_head *node;
>>>>
>>>> -       list_for_each_entry(dev, &bus->devices, bus_list) {
>>>> -               int ret;
>>>> -               struct pci_bus *b = dev->subordinate;
>>>> -               if (!b)
>>>> -                       continue;
>>>> +       /* no child? */
>>>> +       if (list_empty(&bus->children))
>>>> +               return 0;
>>>>
>>>> -               ret = pci_bus_get_depth(b);
>>>> -               if (ret + 1 > depth)
>>>> -                       depth = ret + 1;
>>>> +       node = bus->children.next;
>>>> +       parent = bus;
>>>> +       max_depth = depth = 1;
>>>> +
>>>> +       while (parent) {
>>>> +               /* hit the head, go back to parent level */
>>>> +               if (node == &parent->children) {
>>>> +                       node = parent->node.next;
>>>> +                       parent = parent->parent;
>>>> +                       depth--;
>>>> +                       continue;
>>>> +               }
>>>> +               curr = list_entry(node, struct pci_bus, node);
>>>> +               /* depth first */
>>>> +               if (!list_empty(&curr->children)) {
>>>> +                       node = curr->children.next;
>>>> +                       parent = curr;
>>>> +                       depth++;
>>>> +                       if (max_depth < depth)
>>>> +                               max_depth = depth;
>>>> +               }
>>>> +               /* no child, go to the sibling */
>>>> +               else
>>>> +                       node = curr->node.next;
>>>>         }
>>>>
>>>> -       return depth;
>>>> +       return max_depth;
>>>>  }
>>>> +
>>>>  static int __init pci_get_max_depth(void)
>>>>  {
>>>>         int depth = 0;
>>>> --
>>>> 1.7.5.4
>>>>
>>>> --
>>>> To unsubscribe from this list: send the line "unsubscribe linux-pci" in
>>>> the body of a message to majordomo@vger.kernel.org
>>>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>
>> --
>> Richard Yang
>> Help you, Help me
>>

-- 
Richard Yang
Help you, Help me