[PATCH 0/3] Redesign of pciinit.c

[Alexey Korolev]

Hi,

This patch series redesigns the existing pciinit.c code and introduces
linked list operations.
Changes are more about structures definitions rather than functionality.
There are no more arrays of bases and counts in new implementation. The
new implementation is based on dynamic allocation of pci_region_entry
structures. 
Each pci_region_entry structure could be a PCI bar or a downstream PCI
region (bridge). Each entry has a set of attributes: type (IO, MEM,
PREFMEM), is64bit, size, base address, PCI device owner, and a
pointer to the pci_bus it belongs to.
Also this series introduces list head operations which could be quite
handy not only for pciinit.c code but for post memory manager and thread
operations.

The patch series includes 3 patches.

1. Introduce List operations
2. Redesign of pciinit.c code to make use of pci_region_entry structure.
3. Make use of list operations in pmm.c and stack.c

src/pci.h     |    6 --
 src/pciinit.c |  266 ++++++++++++++++++++++++++-------------------------------
 src/pmm.c     |   29 ++-----
 src/stacks.c  |    8 +--
 src/util.h    |   32 +++++++
 5 files changed, 163 insertions(+), 178 deletions(-)

[PATCH 1/3] Linked list operations

[Alexey Korolev]

This linked list implementation is partially based on kernel code. So it
should be quite stable :)

Signed-off-by: Alexey Korolev 
---
 src/util.h |   32 ++++++++++++++++++++++++++++++++
 1 files changed, 32 insertions(+), 0 deletions(-)

diff --git a/src/util.h b/src/util.h
index 70d3c4c..d1002a9 100644
--- a/src/util.h
+++ b/src/util.h
@@ -195,6 +195,38 @@ struct descloc_s {
     u32 addr;
 } PACKED;

+// Double linked lists with a single pointer list head
+#define list_foreach_entry(head, entry)    \
+    for (entry = head; entry; entry = entry->next)
+
+#define list_foreach_entry_safe(head, next, entry)    \
+        for (entry = head; entry && ({next=entry->next; 1;}); \
+            entry = next)
+
+#define list_del(entry) \
+       do { \
+           *(entry)->pprev = (entry)->next; \
+           if ((entry)->next) \
+               (entry)->next->pprev = (entry)->pprev; \
+       } while (0)
+
+#define list_add_head(phead, entry) \
+       do { \
+           (entry)->next = *(phead); \
+           if (*(phead)) \
+               (*(phead))->pprev = &(entry)->next; \
+           *(phead) = entry; \
+           (entry)->pprev = phead; \
+       } while (0)
+
+#define list_add_before(pos, entry) \
+       do { \
+           (entry)->pprev = (pos)->pprev; \
+           (entry)->next = pos; \
+           (pos)->pprev = &(entry)->next; \
+           *(entry)->pprev = entry; \
+       } while (0)
+
 // util.c
 void cpuid(u32 index, u32 *eax, u32 *ebx, u32 *ecx, u32 *edx);
 struct bregs;

[PATCH 2/3] Redesign of pciinit.c

[Alexey Korolev]

In this patch we introduce the pri_region_entry structure and
significantly simplify the pci_bus structure. 
Instead of arrays now we are using linked lists to account resources and
assign memory bases.

Since we modify the main structure of pciinit.c this is the minimum
chunk of changes which could keep code workable. I mean further patch
splitting is not possible as there are too many references to pci_bus
members.

Signed-off-by: Alexey Korolev 
---
 src/pci.h     |    6 --
 src/pciinit.c |  266 ++++++++++++++++++++++++++-------------------------------
 2 files changed, 120 insertions(+), 152 deletions(-)

diff --git a/src/pci.h b/src/pci.h
index a2a5a4c..8fa064f 100644
--- a/src/pci.h
+++ b/src/pci.h
@@ -51,12 +51,6 @@ struct pci_device {
     u8 prog_if, revision;
     u8 header_type;
     u8 secondary_bus;
-    struct {
-        u32 addr;
-        u32 size;
-        int is64;
-    } bars[PCI_NUM_REGIONS];
-
     // Local information on device.
     int have_driver;
 };
diff --git a/src/pciinit.c b/src/pciinit.c
index 9f3fdd4..02ef108 100644
--- a/src/pciinit.c
+++ b/src/pciinit.c
@@ -12,9 +12,8 @@
 #include "pci_regs.h" // PCI_COMMAND
 #include "xen.h" // usingXen

-#define PCI_IO_INDEX_SHIFT 2
-#define PCI_MEM_INDEX_SHIFT 12
-
+#define PCI_DEV_IO_MINSIZE        0x4
+#define PCI_DEV_MEM_MINSIZE    0x1000
 #define PCI_BRIDGE_IO_MIN      0x1000
 #define PCI_BRIDGE_MEM_MIN   0x100000

@@ -31,40 +30,31 @@ static const char *region_type_name[] = {
     [ PCI_REGION_TYPE_PREFMEM ] = "prefmem",
 };

+struct pci_bus;
+struct pci_region_entry {
+    struct pci_device *dev;
+    int bar;
+    u32 base;
+    u32 size;
+    int is64bit;
+    enum pci_region_type type;
+    struct pci_bus *this_bus;
+    struct pci_bus *parent_bus;
+    struct pci_region_entry *next;
+    struct pci_region_entry **pprev;
+};
+
 struct pci_bus {
     struct {
         /* pci region stats */
-        u32 count[32 - PCI_MEM_INDEX_SHIFT];
         u32 sum, max;
-        /* seconday bus region sizes */
         u32 size;
-        /* pci region assignments */
-        u32 bases[32 - PCI_MEM_INDEX_SHIFT];
         u32 base;
+        struct pci_region_entry *list;
     } r[PCI_REGION_TYPE_COUNT];
     struct pci_device *bus_dev;
 };

-static int pci_size_to_index(u32 size, enum pci_region_type type)
-{
-    int index = __fls(size);
-    int shift = (type == PCI_REGION_TYPE_IO) ?
-        PCI_IO_INDEX_SHIFT : PCI_MEM_INDEX_SHIFT;
-
-    if (index < shift)
-        index = shift;
-    index -= shift;
-    return index;
-}
-
-static u32 pci_index_to_size(int index, enum pci_region_type type)
-{
-    int shift = (type == PCI_REGION_TYPE_IO) ?
-        PCI_IO_INDEX_SHIFT : PCI_MEM_INDEX_SHIFT;
-
-    return 0x1 << (index + shift);
-}
-
 static enum pci_region_type pci_addr_to_type(u32 addr)
 {
     if (addr & PCI_BASE_ADDRESS_SPACE_IO)
@@ -352,21 +342,38 @@ pci_bios_get_bar(struct pci_device *pci, int bar, u32 *val, u32 *size)
     *size = (~(*val & mask)) + 1;
 }

-static void pci_bios_bus_reserve(struct pci_bus *bus, int type, u32 size)
+
+/****************************************************************
+ * Build topology and calculate size of entries
+ ****************************************************************/
+struct pci_region_entry *
+pci_region_create_entry(struct pci_bus *bus, struct pci_device *dev,
+                       u32 size, int type, int is64bit)
 {
-    u32 index;
+    struct pci_region_entry *entry= malloc_tmp(sizeof(*entry));
+    if (!entry) {
+            warn_noalloc();
+            return NULL;
+    }
+    memset(entry, 0, sizeof(*entry));
+
+    entry->dev = dev;
+    entry->type = type;
+    entry->is64bit = is64bit;
+    entry->size = size;

-    index = pci_size_to_index(size, type);
-    size = pci_index_to_size(index, type);
-    bus->r[type].count[index]++;
+    list_add_head(&bus->r[type].list, entry);
+    entry->parent_bus = bus;
     bus->r[type].sum += size;
     if (bus->r[type].max < size)
         bus->r[type].max = size;
+    return entry;
 }

-static void pci_bios_check_devices(struct pci_bus *busses)
+static int pci_bios_check_devices(struct pci_bus *busses)
 {
     dprintf(1, "PCI: check devices\n");
+    struct pci_region_entry *entry;

// Calculate resources needed for regular (non-bus) devices.
     struct pci_device *pci;
@@ -378,19 +385,25 @@ static void pci_bios_check_devices(struct pci_bus *busses)
         struct pci_bus *bus = &busses[pci_bdf_to_bus(pci->bdf)];
         int i;
         for (i = 0; i < PCI_NUM_REGIONS; i++) {
-            u32 val, size;
+            u32 val, size, min_size;
+            int is64, type;
             pci_bios_get_bar(pci, i, &val, &size);
             if (val == 0)
                 continue;
-
-            pci_bios_bus_reserve(bus, pci_addr_to_type(val), size);
-            pci->bars[i].addr = val;
-            pci->bars[i].size = size;
-            pci->bars[i].is64 = (!(val & PCI_BASE_ADDRESS_SPACE_IO) &&
-                                 (val & PCI_BASE_ADDRESS_MEM_TYPE_MASK)
-                                 == PCI_BASE_ADDRESS_MEM_TYPE_64);
-
-            if (pci->bars[i].is64)
+            type = pci_addr_to_type(val);
+            min_size = (type == PCI_REGION_TYPE_IO) ? PCI_DEV_IO_MINSIZE:
+                     PCI_DEV_MEM_MINSIZE;
+            size = (size > min_size) ? size : min_size;
+
+            is64 = (!(val & PCI_BASE_ADDRESS_SPACE_IO) &&
+                      (val & PCI_BASE_ADDRESS_MEM_TYPE_MASK)
+                       == PCI_BASE_ADDRESS_MEM_TYPE_64);
+            entry = pci_region_create_entry(bus, pci, size, type, is64);
+            if (!entry)
+                return -1;
+            entry->bar = i;
+
+            if (is64)
                 i++;
         }
     }
@@ -403,21 +416,24 @@ static void pci_bios_check_devices(struct pci_bus *busses)
             continue;
         struct pci_bus *parent = &busses[pci_bdf_to_bus(s->bus_dev->bdf)];
         int type;
+        u32 size;
         for (type = 0; type < PCI_REGION_TYPE_COUNT; type++) {
             u32 limit = (type == PCI_REGION_TYPE_IO) ?
                 PCI_BRIDGE_IO_MIN : PCI_BRIDGE_MEM_MIN;
-            s->r[type].size = s->r[type].sum;
-            if (s->r[type].size < limit)
-                s->r[type].size = limit;
-            s->r[type].size = pci_size_roundup(s->r[type].size);
-            pci_bios_bus_reserve(parent, type, s->r[type].size);
+            size = s->r[type].sum;
+            if (size < limit)
+                size = limit;
+            size = pci_size_roundup(size);
+            entry = pci_region_create_entry(parent, s->bus_dev, size, type, 0);
+            if (!entry)
+                return -1;
+            entry->this_bus = s;
+            dprintf(1, "PCI: secondary bus %d size 0x%x type %s\n",
+                      entry->dev->secondary_bus, size,
+                      region_type_name[entry->type]);
         }
-        dprintf(1, "PCI: secondary bus %d sizes: io %x, mem %x, prefmem %x\n",
-                secondary_bus,
-                s->r[PCI_REGION_TYPE_IO].size,
-                s->r[PCI_REGION_TYPE_MEM].size,
-                s->r[PCI_REGION_TYPE_PREFMEM].size);
     }
+    return 0;
 }

#define ROOT_BASE(top, sum, max) ALIGN_DOWN((top)-(sum),(max) ?: 1)
@@ -442,118 +458,76 @@ static int pci_bios_init_root_regions(struct pci_bus *bus, u32 start, u32 end)
     return 0;
 }

-
 /****************************************************************
- * BAR assignment
+ * Map pci region entries
  ****************************************************************/

-static void pci_bios_init_bus_bases(struct pci_bus *bus)
-{
-    u32 base, newbase, size;
-    int type, i;
-
-    for (type = 0; type < PCI_REGION_TYPE_COUNT; type++) {
-        dprintf(1, "  type %s max %x sum %x base %x\n", region_type_name[type],
-                bus->r[type].max, bus->r[type].sum, bus->r[type].base);
-        base = bus->r[type].base;
-        for (i = ARRAY_SIZE(bus->r[type].count)-1; i >= 0; i--) {
-            size = pci_index_to_size(i, type);
-            if (!bus->r[type].count[i])
-                continue;
-            newbase = base + size * bus->r[type].count[i];
-            dprintf(1, "    size %8x: %d bar(s), %8x -> %8x\n",
-                    size, bus->r[type].count[i], base, newbase - 1);
-            bus->r[type].bases[i] = base;
-            base = newbase;
-        }
-    }
-}
-
-static u32 pci_bios_bus_get_addr(struct pci_bus *bus, int type, u32 size)
-{
-    u32 index, addr;
-
-    index = pci_size_to_index(size, type);
-    addr = bus->r[type].bases[index];
-    bus->r[type].bases[index] += pci_index_to_size(index, type);
-    return addr;
-}
-
-#define PCI_IO_SHIFT            8
-#define PCI_MEMORY_SHIFT        16
-#define PCI_PREF_MEMORY_SHIFT   16

-static void pci_bios_map_devices(struct pci_bus *busses)
+static void pci_region_map_one_entry(struct pci_region_entry *entry)
 {
-    // Setup bases for root bus.
-    dprintf(1, "PCI: init bases bus 0 (primary)\n");
-    pci_bios_init_bus_bases(&busses[0]);
+    if (!entry->this_bus ) {
+        dprintf(1, "PCI: bdf %d bar %d\tsize\t0x%08x\tbase 0x%x type %s\n",
+                      entry->dev->bdf, entry->bar, entry->size, entry->base,
+                      region_type_name[entry->type]);
+
+        pci_set_io_region_addr(entry->dev, entry->bar, entry->base);
+        if (entry->is64bit)
+            pci_set_io_region_addr(entry->dev, entry->bar + 1, 0);
+        return;
+    }

-    // Map regions on each secondary bus.
-    int secondary_bus;
-    for (secondary_bus=1; secondary_bus<=MaxPCIBus; secondary_bus++) {
-        struct pci_bus *s = &busses[secondary_bus];
-        if (!s->bus_dev)
-            continue;
-        u16 bdf = s->bus_dev->bdf;
-        struct pci_bus *parent = &busses[pci_bdf_to_bus(bdf)];
-        int type;
-        for (type = 0; type < PCI_REGION_TYPE_COUNT; type++) {
-            s->r[type].base = pci_bios_bus_get_addr(
-                parent, type, s->r[type].size);
-        }
-        dprintf(1, "PCI: init bases bus %d (secondary)\n", secondary_bus);
-        pci_bios_init_bus_bases(s);
+    entry->this_bus->r[entry->type].base = entry->base;
+    dprintf(1, "PCI-2-PCI bus %d\t\tsize\t0x%08x\tbase 0x%x type %s\n",
+                  entry->dev->secondary_bus, entry->size, entry->base,
+                  region_type_name[entry->type]);

-        u32 base = s->r[PCI_REGION_TYPE_IO].base;
-        u32 limit = base + s->r[PCI_REGION_TYPE_IO].size - 1;
-        pci_config_writeb(bdf, PCI_IO_BASE, base >> PCI_IO_SHIFT);
+    u16 bdf = entry->dev->bdf;
+    u32 base = entry->base;
+    u32 limit = entry->base + entry->size - 1;
+    if (entry->type == PCI_REGION_TYPE_IO) {
+        pci_config_writeb(bdf, PCI_IO_BASE, base >> 8);
         pci_config_writew(bdf, PCI_IO_BASE_UPPER16, 0);
-        pci_config_writeb(bdf, PCI_IO_LIMIT, limit >> PCI_IO_SHIFT);
+        pci_config_writeb(bdf, PCI_IO_LIMIT, limit >> 8);
         pci_config_writew(bdf, PCI_IO_LIMIT_UPPER16, 0);
-
-        base = s->r[PCI_REGION_TYPE_MEM].base;
-        limit = base + s->r[PCI_REGION_TYPE_MEM].size - 1;
-        pci_config_writew(bdf, PCI_MEMORY_BASE, base >> PCI_MEMORY_SHIFT);
-        pci_config_writew(bdf, PCI_MEMORY_LIMIT, limit >> PCI_MEMORY_SHIFT);
-
-        base = s->r[PCI_REGION_TYPE_PREFMEM].base;
-        limit = base + s->r[PCI_REGION_TYPE_PREFMEM].size - 1;
-        pci_config_writew(bdf, PCI_PREF_MEMORY_BASE, base >> PCI_PREF_MEMORY_SHIFT);
-        pci_config_writew(bdf, PCI_PREF_MEMORY_LIMIT, limit >> PCI_PREF_MEMORY_SHIFT);
+    }
+    if (entry->type == PCI_REGION_TYPE_MEM) {
+        pci_config_writew(bdf, PCI_MEMORY_BASE, base >> 16);
+        pci_config_writew(bdf, PCI_MEMORY_LIMIT, limit >> 16);
+    }
+    if (entry->type == PCI_REGION_TYPE_PREFMEM) {
+        pci_config_writew(bdf, PCI_PREF_MEMORY_BASE, base >> 16);
+        pci_config_writew(bdf, PCI_PREF_MEMORY_LIMIT, limit >> 16);
         pci_config_writel(bdf, PCI_PREF_BASE_UPPER32, 0);
         pci_config_writel(bdf, PCI_PREF_LIMIT_UPPER32, 0);
     }
+    return;
+}

-    // Map regions on each device.
-    struct pci_device *pci;
-    foreachpci(pci) {
-        if (pci->class == PCI_CLASS_BRIDGE_PCI)
-            continue;
-        u16 bdf = pci->bdf;
-        dprintf(1, "PCI: map device bdf=%02x:%02x.%x\n"
-                , pci_bdf_to_bus(bdf), pci_bdf_to_dev(bdf), pci_bdf_to_fn(bdf));
-        struct pci_bus *bus = &busses[pci_bdf_to_bus(bdf)];
-        int i;
-        for (i = 0; i < PCI_NUM_REGIONS; i++) {
-            if (pci->bars[i].addr == 0)
-                continue;
-
-            int type = pci_addr_to_type(pci->bars[i].addr);
-            u32 addr = pci_bios_bus_get_addr(bus, type, pci->bars[i].size);
-            dprintf(1, "  bar %d, addr %x, size %x [%s]\n",
-                    i, addr, pci->bars[i].size, region_type_name[type]);
-            pci_set_io_region_addr(pci, i, addr);
+static void pci_bios_map_devices(struct pci_bus *busses)
+{
+    struct pci_region_entry *entry, *next;

-            if (pci->bars[i].is64) {
-                i++;
-                pci_set_io_region_addr(pci, i, 0);
+    int bus;
+    for (bus = 0; bus<=MaxPCIBus; bus++) {
+        int type;
+        for (type = 0; type < PCI_REGION_TYPE_COUNT; type++) {
+            u32 size;
+            for (size = busses[bus].r[type].max; size > 0; size >>= 1) {
+                    list_foreach_entry_safe(busses[bus].r[type].list,
+                                              next, entry) {
+                        if (size == entry->size) {
+                            entry->base = busses[bus].r[type].base;
+                            busses[bus].r[type].base += size;
+                            pci_region_map_one_entry(entry);
+                            list_del(entry);
+                            free(entry);
+                    }
+                }
             }
         }
     }
 }

-
 /****************************************************************
  * Main setup code
  ****************************************************************/

[PATCH 2/3] Redesign of pciinit.c

[Kevin O'Connor]

On Fri, Mar 09, 2012 at 07:51:06PM +1300, Alexey Korolev wrote:
> In this patch we introduce the pri_region_entry structure and
> significantly simplify the pci_bus structure. 
> Instead of arrays now we are using linked lists to account resources and
> assign memory bases.
>
> Since we modify the main structure of pciinit.c this is the minimum
> chunk of changes which could keep code workable. I mean further patch
> splitting is not possible as there are too many references to pci_bus
> members.

Thanks Alexey.  This is better than the previous patch, but I still
don't feel comfortable with the amount of change in a single patch.
I'm having a hard time reviewing the change.  I'd much prefer to see
one patch (or more) with just the data structure changes, and then one
patch (or more) with the change from the array based allocation system
to the list traversal allocation system.  (That is, it should be
possible to have all the linked lists in place while still using the
array system to do the allocations, and then in a separate patch
delete the arrays and convert over to list traversal.)

-Kevin

[PATCH 3/3] Use linked list operations in pmm.c and stack.c

[Alexey Korolev]

Now let simplify a bit a cumbersome code in pmm.c and stack.c

Signed-off-by: Alexey Korolev 
---
 src/pmm.c    |   29 +++++++++--------------------
 src/stacks.c |    8 ++------
 2 files changed, 11 insertions(+), 26 deletions(-)

diff --git a/src/pmm.c b/src/pmm.c
index c649fd8..996981c 100644
--- a/src/pmm.c
+++ b/src/pmm.c
@@ -44,24 +44,20 @@ static void *
 allocSpace(struct zone_s *zone, u32 size, u32 align, struct allocinfo_s *fill)
 {
     struct allocinfo_s *info;
-    for (info = zone->info; info; info = info->next) {
+    list_foreach_entry(zone->info, info) {
         void *dataend = info->dataend;
         void *allocend = info->allocend;
         void *newallocend = (void*)ALIGN_DOWN((u32)allocend - size, align);
         if (newallocend >= dataend && newallocend <= allocend) {
             // Found space - now reserve it.
-            struct allocinfo_s **pprev = info->pprev;
             if (!fill)
                 fill = newallocend;
-            fill->next = info;
-            fill->pprev = pprev;
+            list_add_before(info, fill);
             fill->data = newallocend;
             fill->dataend = newallocend + size;
             fill->allocend = allocend;

info->allocend = newallocend;
-            info->pprev = &fill->next;
-            *pprev = fill;
             return newallocend;
         }
     }
@@ -73,13 +69,9 @@ static void
 freeSpace(struct allocinfo_s *info)
 {
     struct allocinfo_s *next = info->next;
-    struct allocinfo_s **pprev = info->pprev;
-    *pprev = next;
-    if (next) {
-        if (next->allocend == info->data)
+    if (next && (next->allocend == info->data))
             next->allocend = info->allocend;
-        next->pprev = pprev;
-    }
+    list_del(info);
 }

// Add new memory to a zone
@@ -97,13 +89,12 @@ addSpace(struct zone_s *zone, void *start, void *end)

// Add space using temporary allocation info.
     struct allocdetail_s tempdetail;
-    tempdetail.datainfo.next = info;
-    tempdetail.datainfo.pprev = pprev;
     tempdetail.datainfo.data = tempdetail.datainfo.dataend = start;
     tempdetail.datainfo.allocend = end;
-    *pprev = &tempdetail.datainfo;
-    if (info)
-        info->pprev = &tempdetail.datainfo.next;
+
+    tempdetail.datainfo.data = tempdetail.datainfo.dataend = start;
+    tempdetail.datainfo.allocend = end;
+    list_add_head(pprev, &tempdetail.datainfo);

// Allocate final allocation info.
     struct allocdetail_s *detail = allocSpace(
@@ -112,9 +103,7 @@ addSpace(struct zone_s *zone, void *start, void *end)
         detail = allocSpace(&ZoneTmpLow, sizeof(*detail)
                             , MALLOC_MIN_ALIGN, NULL);
         if (!detail) {
-            *tempdetail.datainfo.pprev = tempdetail.datainfo.next;
-            if (tempdetail.datainfo.next)
-                tempdetail.datainfo.next->pprev = tempdetail.datainfo.pprev;
+            list_del(&tempdetail.datainfo);
             warn_noalloc();
             return;
         }
diff --git a/src/stacks.c b/src/stacks.c
index 17f1a4a..2b10188 100644
--- a/src/stacks.c
+++ b/src/stacks.c
@@ -240,8 +240,7 @@ yield(void)
 static void
 __end_thread(struct thread_info *old)
 {
-    old->next->pprev = old->pprev;
-    *old->pprev = old->next;
+    list_del(old);
     free(old);
     dprintf(DEBUG_thread, "\%08x/ End thread\n", (u32)old);
     if (MainThread.next == &MainThread)
@@ -262,10 +261,7 @@ run_thread(void (*func)(void*), void *data)

thread->stackpos = (void*)thread + THREADSTACKSIZE;
     struct thread_info *cur = getCurThread();
-    thread->next = cur;
-    thread->pprev = cur->pprev;
-    cur->pprev = &thread->next;
-    *thread->pprev = thread;
+    list_add_before(cur, thread);

dprintf(DEBUG_thread, "/%08x\ Start thread\n", (u32)thread);
     asm volatile(