Re: [SeaBIOS] [PATCH 3/4] Switch from array based resource allocation to list

[Kevin O'Connor]

On Sun, Apr 01, 2012 at 03:28:34AM -0400, Kevin O'Connor wrote:
> On Wed, Mar 28, 2012 at 05:54:10PM +1300, Alexey Korolev wrote:
> > In this patch instead of array based resource allocation approach
> > we calculate resource addresses linked lists of pci_region_entry structures.
>
> Thanks.  I still think this migration can be done more seamlessly.  I
> played with your patches a bit and came up with the attached patches
> that do just code movement - no alogorithm changes.  See the attached.
>
> Also, I think we should look to commit after the next SeaBIOS release.

Looking closer at your new allocation algorithm, I see that it
effectively allocates largest sizes first.  It occurred to me that an
easy way to do this is to keep the pci_region_entry list sorted by
size.  See the patch below as an example (based on top of the previous
email I sent).

-Kevin

diff --git a/src/pciinit.c b/src/pciinit.c
index f2c839a..bfee178 100644
--- a/src/pciinit.c
+++ b/src/pciinit.c
@@ -41,16 +41,13 @@ struct pci_region_entry {
     struct pci_bus *child_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;
         /* pci region assignments */
-        u32 bases[32 - PCI_MEM_INDEX_SHIFT];
         u32 base;
         struct pci_region_entry *list;
     } r[PCI_REGION_TYPE_COUNT];
@@ -379,11 +376,18 @@ pci_region_create_entry(struct pci_bus *bus, struct pci_device *dev,
     entry->is64 = is64;
     entry->type = type;
     entry->parent_bus = bus;
-    list_add_head(&bus->r[type].list, entry);
+    // Insert into list in sorted order.
+    struct pci_region_entry **pprev;
+    for (pprev = &bus->r[type].list; *pprev; pprev = &(*pprev)->next) {
+        struct pci_region_entry *pos = *pprev;
+        if (pos->size < size)
+            break;
+    }
+    entry->next = *pprev;
+    *pprev = entry;

u32 index = pci_size_to_index(size, type);
     size = pci_index_to_size(index, type);
-    bus->r[type].count[index]++;
     bus->r[type].sum += size;
     if (bus->r[type].max < size)
         bus->r[type].max = size;
@@ -478,46 +482,14 @@ static int pci_bios_init_root_regions(struct pci_bus *bus, u32 start, u32 end)
  * BAR assignment
  ****************************************************************/

-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_region_map_one_entry(struct pci_region_entry *entry)
 {
-    u32 addr = pci_bios_bus_get_addr(
-        entry->parent_bus, entry->type, entry->size);
+    u32 addr = entry->parent_bus->r[entry->type].base;
+    entry->parent_bus->r[entry->type].base += entry->size;
     if (!entry->child_bus) {
         dprintf(1, "PCI: map device bdf=%02x:%02x.%x"
                 "  bar %d, addr %08x, size %08x [%s]\n",
@@ -559,15 +531,14 @@ static void pci_bios_map_devices(struct pci_bus *busses)
     // Map regions on each device.
     int bus;
     for (bus = 0; bus<=MaxPCIBus; bus++) {
-        dprintf(1, "PCI: init bases bus %d\n", bus);
-        pci_bios_init_bus_bases(&busses[bus]);
         int type;
         for (type = 0; type < PCI_REGION_TYPE_COUNT; type++) {
-            struct pci_region_entry *entry, *next;
-            list_foreach_entry_safe(busses[bus].r[type].list, next, entry) {
+            struct pci_region_entry *entry = busses[bus].r[type].list;
+            while (entry) {
                 pci_region_map_one_entry(entry);
-                list_del(entry);
+                struct pci_region_entry *next = entry->next;
                 free(entry);
+                entry = next;
             }
         }
     }