ls-tree.c

   1 /*
   2  *      The PCI Utilities -- Show Bus Tree
   3  *
   4  *      Copyright (c) 1997--2008 Martin Mares <mj@ucw.cz>
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  */
   8
   9 #include <stdio.h>
  10 #include <string.h>
  11
  12 #include "lspci.h"
  13
  14 struct bridge {
  15   struct bridge *chain;                 /* Single-linked list of bridges */
  16   struct bridge *next, *child;          /* Tree of bridges */
  17   struct bus *first_bus;                /* List of buses connected to this bridge */
  18   unsigned int domain;
  19   unsigned int primary, secondary, subordinate; /* Bus numbers */
  20   struct device *br_dev;
  21 };
  22
  23 struct bus {
  24   unsigned int domain;
  25   unsigned int number;
  26   struct bus *sibling;
  27   struct device *first_dev, **last_dev;
  28 };
  29
  30 static struct bridge host_bridge = { NULL, NULL, NULL, NULL, 0, ~0, 0, ~0, NULL };
  31
  32 static struct bus *
  33 find_bus(struct bridge *b, unsigned int domain, unsigned int n)
  34 {
  35   struct bus *bus;
  36
  37   for (bus=b->first_bus; bus; bus=bus->sibling)
  38     if (bus->domain == domain && bus->number == n)
  39       break;
  40   return bus;
  41 }
  42
  43 static struct bus *
  44 new_bus(struct bridge *b, unsigned int domain, unsigned int n)
  45 {
  46   struct bus *bus = xmalloc(sizeof(struct bus));
  47   bus->domain = domain;
  48   bus->number = n;
  49   bus->sibling = b->first_bus;
  50   bus->first_dev = NULL;
  51   bus->last_dev = &bus->first_dev;
  52   b->first_bus = bus;
  53   return bus;
  54 }
  55
  56 static void
  57 insert_dev(struct device *d, struct bridge *b)
  58 {
  59   struct pci_dev *p = d->dev;
  60   struct bus *bus;
  61
  62   if (! (bus = find_bus(b, p->domain, p->bus)))
  63     {
  64       struct bridge *c;
  65       for (c=b->child; c; c=c->next)
  66         if (c->domain == (unsigned)p->domain && c->secondary <= p->bus && p->bus <= c->subordinate)
  67           {
  68             insert_dev(d, c);
  69             return;
  70           }
  71       bus = new_bus(b, p->domain, p->bus);
  72     }
  73   /* Simple insertion at the end _does_ guarantee the correct order as the
  74    * original device list was sorted by (domain, bus, devfn) lexicographically
  75    * and all devices on the new list have the same bus number.
  76    */
  77   *bus->last_dev = d;
  78   bus->last_dev = &d->next;
  79   d->next = NULL;
  80 }
  81
  82 static void
  83 grow_tree(void)
  84 {
  85   struct device *d, *d2;
  86   struct bridge **last_br, *b;
  87
  88   /* Build list of bridges */
  89
  90   last_br = &host_bridge.chain;
  91   for (d=first_dev; d; d=d->next)
  92     {
  93       word class = d->dev->device_class;
  94       byte ht = get_conf_byte(d, PCI_HEADER_TYPE) & 0x7f;
  95       if (class == PCI_CLASS_BRIDGE_PCI &&
  96           (ht == PCI_HEADER_TYPE_BRIDGE || ht == PCI_HEADER_TYPE_CARDBUS))
  97         {
  98           b = xmalloc(sizeof(struct bridge));
  99           b->domain = d->dev->domain;
 100           if (ht == PCI_HEADER_TYPE_BRIDGE)
 101             {
 102               b->primary = get_conf_byte(d, PCI_PRIMARY_BUS);
 103               b->secondary = get_conf_byte(d, PCI_SECONDARY_BUS);
 104               b->subordinate = get_conf_byte(d, PCI_SUBORDINATE_BUS);
 105             }
 106           else
 107             {
 108               b->primary = get_conf_byte(d, PCI_CB_PRIMARY_BUS);
 109               b->secondary = get_conf_byte(d, PCI_CB_CARD_BUS);
 110               b->subordinate = get_conf_byte(d, PCI_CB_SUBORDINATE_BUS);
 111             }
 112           *last_br = b;
 113           last_br = &b->chain;
 114           b->next = b->child = NULL;
 115           b->first_bus = NULL;
 116           b->br_dev = d;
 117         }
 118     }
 119   *last_br = NULL;
 120
 121   /* Create a bridge tree */
 122
 123   for (b=&host_bridge; b; b=b->chain)
 124     {
 125       struct bridge *c, *best;
 126       best = NULL;
 127       for (c=&host_bridge; c; c=c->chain)
 128         if (c != b && (c == &host_bridge || b->domain == c->domain) &&
 129             b->primary >= c->secondary && b->primary <= c->subordinate &&
 130             (!best || best->subordinate - best->primary > c->subordinate - c->primary))
 131           best = c;
 132       if (best)
 133         {
 134           b->next = best->child;
 135           best->child = b;
 136         }
 137     }
 138
 139   /* Insert secondary bus for each bridge */
 140
 141   for (b=&host_bridge; b; b=b->chain)
 142     if (!find_bus(b, b->domain, b->secondary))
 143       new_bus(b, b->domain, b->secondary);
 144
 145   /* Create bus structs and link devices */
 146
 147   for (d=first_dev; d;)
 148     {
 149       d2 = d->next;
 150       insert_dev(d, &host_bridge);
 151       d = d2;
 152     }
 153 }
 154
 155 static void
 156 print_it(char *line, char *p)
 157 {
 158   *p++ = '\n';
 159   *p = 0;
 160   fputs(line, stdout);
 161   for (p=line; *p; p++)
 162     if (*p == '+' || *p == '|')
 163       *p = '|';
 164     else
 165       *p = ' ';
 166 }
 167
 168 static void show_tree_bridge(struct bridge *, char *, char *);
 169
 170 static void
 171 show_tree_dev(struct device *d, char *line, char *p)
 172 {
 173   struct pci_dev *q = d->dev;
 174   struct bridge *b;
 175   char namebuf[256];
 176
 177   p += sprintf(p, "%02x.%x", q->dev, q->func);
 178   for (b=&host_bridge; b; b=b->chain)
 179     if (b->br_dev == d)
 180       {
 181         if (b->secondary == b->subordinate)
 182           p += sprintf(p, "-[%02x]-", b->secondary);
 183         else
 184           p += sprintf(p, "-[%02x-%02x]-", b->secondary, b->subordinate);
 185         show_tree_bridge(b, line, p);
 186         return;
 187       }
 188   if (verbose)
 189     p += sprintf(p, "  %s",
 190                  pci_lookup_name(pacc, namebuf, sizeof(namebuf),
 191                                  PCI_LOOKUP_VENDOR | PCI_LOOKUP_DEVICE,
 192                                  q->vendor_id, q->device_id));
 193   print_it(line, p);
 194 }
 195
 196 static void
 197 show_tree_bus(struct bus *b, char *line, char *p)
 198 {
 199   if (!b->first_dev)
 200     print_it(line, p);
 201   else if (!b->first_dev->next)
 202     {
 203       *p++ = '-';
 204       *p++ = '-';
 205       show_tree_dev(b->first_dev, line, p);
 206     }
 207   else
 208     {
 209       struct device *d = b->first_dev;
 210       while (d->next)
 211         {
 212           p[0] = '+';
 213           p[1] = '-';
 214           show_tree_dev(d, line, p+2);
 215           d = d->next;
 216         }
 217       p[0] = '\\';
 218       p[1] = '-';
 219       show_tree_dev(d, line, p+2);
 220     }
 221 }
 222
 223 static void
 224 show_tree_bridge(struct bridge *b, char *line, char *p)
 225 {
 226   *p++ = '-';
 227   if (!b->first_bus->sibling)
 228     {
 229       if (b == &host_bridge)
 230         p += sprintf(p, "[%04x:%02x]-", b->domain, b->first_bus->number);
 231       show_tree_bus(b->first_bus, line, p);
 232     }
 233   else
 234     {
 235       struct bus *u = b->first_bus;
 236       char *k;
 237
 238       while (u->sibling)
 239         {
 240           k = p + sprintf(p, "+-[%04x:%02x]-", u->domain, u->number);
 241           show_tree_bus(u, line, k);
 242           u = u->sibling;
 243         }
 244       k = p + sprintf(p, "\\-[%04x:%02x]-", u->domain, u->number);
 245       show_tree_bus(u, line, k);
 246     }
 247 }
 248
 249 void
 250 show_forest(void)
 251 {
 252   char line[256];
 253
 254   grow_tree();
 255   show_tree_bridge(&host_bridge, line, line);
 256 }