[PATCH 0/6] Redesign of pciinit.c (take 2)

[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. Add pci_region_entry and linked lists operations in place while still
using the array system to do the allocations. 
3. Switch to lists operations
4. Delete old code. (3 & 4 are split for better readability)
5. Get rid of size element from bus->r structure, now we use entry->size
for the same purpose
6. Make use of list operations in pmm.c and stack.c

src/pciinit.c |  270 ++++++++++++++++++++++++++-------------------------------
 src/pmm.c     |   29 ++----
 src/stacks.c  |    8 +--
 src/util.h    |   32 +++++++
 4 files changed, 165 insertions(+), 174 deletions(-)

P/s
It is basically the same functionality as in previous version. I just
split commit in more pieces to make the changes to be as obvious as
possible.

[PATCH 1/6] Add Linked list operations to util.h

[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/6] Redesign of pciinit.c (take 2)

[Alexey Korolev]

Added pci_region_entry structure and list operations to pciinit.c
List is filled with entries during pci_check_devices.
List is used just for printing space allocation if we were using lists. 
Next step will resource allocation using mapping functions.

Signed-off-by: Alexey Korolev 
---
 src/pciinit.c |  104 +++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 101 insertions(+), 3 deletions(-)

diff --git a/src/pciinit.c b/src/pciinit.c
index 9f3fdd4..2bf5473 100644
--- a/src/pciinit.c
+++ b/src/pciinit.c
@@ -31,6 +31,20 @@ 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 */
@@ -41,6 +55,7 @@ struct pci_bus {
         /* 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;
 };
@@ -352,6 +367,31 @@ pci_bios_get_bar(struct pci_device *pci, int bar, u32 *val, u32 *size)
     *size = (~(*val & mask)) + 1;
 }

+/****************************************************************
+ * 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)
+{
+    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;
+
+    list_add_head(&bus->r[type].list, entry);
+    entry->parent_bus = bus;
+    return entry;
+}
+
 static void pci_bios_bus_reserve(struct pci_bus *bus, int type, u32 size)
 {
     u32 index;
@@ -364,9 +404,10 @@ static void pci_bios_bus_reserve(struct pci_bus *bus, int type, u32 size)
         bus->r[type].max = size;
 }

-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,10 +419,15 @@ 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 type;
             pci_bios_get_bar(pci, i, &val, &size);
             if (val == 0)
                 continue;
+            type = pci_addr_to_type(val);
+            min_size = (type == PCI_REGION_TYPE_IO) ? (1<<PCI_IO_INDEX_SHIFT):
+                     (1<<PCI_MEM_INDEX_SHIFT);
+            size = (size > min_size) ? size : min_size;

pci_bios_bus_reserve(bus, pci_addr_to_type(val), size);
             pci->bars[i].addr = val;
@@ -390,6 +436,11 @@ static void pci_bios_check_devices(struct pci_bus *busses)
                                  (val & PCI_BASE_ADDRESS_MEM_TYPE_MASK)
                                  == PCI_BASE_ADDRESS_MEM_TYPE_64);

+            entry = pci_region_create_entry(bus, pci, size, type, pci->bars[i].is64);
+            if (!entry)
+                return -1;
+            entry->bar = i;
+
             if (pci->bars[i].is64)
                 i++;
         }
@@ -411,6 +462,11 @@ static void pci_bios_check_devices(struct pci_bus *busses)
                 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);
+            entry = pci_region_create_entry(parent, s->bus_dev,
+                                            s->r[type].size, type, 0);
+            if (!entry)
+                return -1;
+            entry->this_bus = s;
         }
         dprintf(1, "PCI: secondary bus %d sizes: io %x, mem %x, prefmem %x\n",
                 secondary_bus,
@@ -418,6 +474,7 @@ static void pci_bios_check_devices(struct pci_bus *busses)
                 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)
@@ -553,6 +610,44 @@ static void pci_bios_map_devices(struct pci_bus *busses)
     }
 }

+static void pci_region_dump_one_entry(struct pci_region_entry *entry)
+{
+    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]);
+    } else {
+        entry->this_bus->r[entry->type].base = entry->base;
+        dprintf(1, "Secondary 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]);
+   }
+}
+
+static void pci_bios_dump_devices(struct pci_bus *busses)
+{
+    struct pci_region_entry *entry, *next;
+
+    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_dump_one_entry(entry);
+                            list_del(entry);
+                            free(entry);
+                    }
+                }
+            }
+        }
+    }
+}

/****************************************************************
  * Main setup code
@@ -588,13 +683,16 @@ pci_setup(void)
         return;
     }
     memset(busses, 0, sizeof(*busses) * (MaxPCIBus + 1));
-    pci_bios_check_devices(busses);
+    if (pci_bios_check_devices(busses))
+        return;
+
     if (pci_bios_init_root_regions(&busses[0], start, end) != 0) {
         panic("PCI: out of address space\n");
     }

dprintf(1, "=== PCI new allocation pass #2 ===\n");
     pci_bios_map_devices(busses);
+    pci_bios_dump_devices(busses);

pci_bios_init_devices();

[PATCH 2/6] Redesign of pciinit.c (take 2)

[Kevin O'Connor]

On Tue, Mar 13, 2012 at 05:45:19PM +1300, Alexey Korolev wrote:
> Added pci_region_entry structure and list operations to pciinit.c
> List is filled with entries during pci_check_devices.
> List is used just for printing space allocation if we were using lists. 
> Next step will resource allocation using mapping functions.

[...]
> +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;
>
> +};

It's fine to introduce a new struct, but a patch that does this should
have something like the following in the same patch:

--- a/src/pci.h
+++ b/src/pci.h
@@ -51,11 +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;

And it should compile and work fine after applying just that one
patch.  That is, you're not introducing a new struct, you're moving
the contents from one struct to another.  The code is being changed -
it's not new code being added and old code being deleted - the patches
need to reflect that.

(If it's a pain to move the struct out of struct pci_device at the
start, then add your new fields into struct pci_device.bars and use a
patch to move the whole thing out of pci.h at the end.)

-Kevin

[PATCH 2/6] Redesign of pciinit.c (take 2)

[Alexey Korolev]

On 14/03/12 13:48, Kevin O'Connor wrote:
> On Tue, Mar 13, 2012 at 05:45:19PM +1300, Alexey Korolev wrote:
> > Added pci_region_entry structure and list operations to pciinit.c
> > List is filled with entries during pci_check_devices.
> > List is used just for printing space allocation if we were using lists. 
> > Next step will resource allocation using mapping functions.
>
> [...]
> > +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;
> >
> > +};
>
> It's fine to introduce a new struct, but a patch that does this should
> have something like the following in the same patch:
>
> --- a/src/pci.h
> +++ b/src/pci.h
> @@ -51,11 +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;
>
> And it should compile and work fine after applying just that one
> patch.  That is, you're not introducing a new struct, you're moving
> the contents from one struct to another.

Yes I see what you mean here.
Basically I kept pci_device->bars and pci_region_entry altogether because they are for different things.
The pci_region_entry describes bridge regions in addition to bars and contains information to build topology.

In your proposal for patches splitting the pci_device->bars are removed and pci_region_entry data
is used to program pci bars. This is reasonable so I've made the changes.  See patch below in this message.

Of course further patches [3-6] won't apply on top of this, so the series should be reposted.
> The code is being changed -
> it's not new code being added and old code being deleted - the patches
> need to reflect that.

Because of structural changes it is not possible to completely avoid this scenario where
new code is added and old deleted.
In this patch series I tried my best to make migration as obvious and safe as possible.
So the existing approach (with your suggestions) for pciinit.c redesign is this:

1. Introduce list operations
2. Introduce pci_region_entry structure and add code which fills this new structure.
We don't modify resource addresses calculations, but we use pci_region_entry data to do resource assignment.
3. Modify resource addresses calculations to be based on linked lists of region entries.
4. Remove code which fills the arrays, remove use of arrays for mapping.
(note 3&4 could be combined altogether but it will be harder to read then)

Could you please have a look at the other parts in this series and let me know if you are happy about this approach,
so I won't have to redo patchwork too many times?

---
 src/pci.h     |    5 --
 src/pciinit.c |  122 ++++++++++++++++++++++++++++++++++++++++++---------------
 2 files changed, 90 insertions(+), 37 deletions(-)

diff --git a/src/pci.h b/src/pci.h
index a2a5a4c..5598100 100644
--- a/src/pci.h
+++ b/src/pci.h
@@ -51,11 +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..f75f393 100644
--- a/src/pciinit.c
+++ b/src/pciinit.c
@@ -31,6 +31,20 @@ 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 */
@@ -41,6 +55,7 @@ struct pci_bus {
         /* 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;
 };
@@ -352,6 +367,31 @@ pci_bios_get_bar(struct pci_device *pci, int bar, u32 *val, u32 *size)
     *size = (~(*val & mask)) + 1;
 }

+/****************************************************************
+ * 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)
+{
+    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;
+
+    list_add_head(&bus->r[type].list, entry);
+    entry->parent_bus = bus;
+    return entry;
+}
+
 static void pci_bios_bus_reserve(struct pci_bus *bus, int type, u32 size)
 {
     u32 index;
@@ -364,9 +404,10 @@ static void pci_bios_bus_reserve(struct pci_bus *bus, int type, u32 size)
         bus->r[type].max = size;
 }

-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 +419,27 @@ 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 type, is64bit;
             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) &&
+            type = pci_addr_to_type(val);
+            min_size = (type == PCI_REGION_TYPE_IO) ? (1<<PCI_IO_INDEX_SHIFT):
+                     (1<<PCI_MEM_INDEX_SHIFT);
+            size = (size > min_size) ? size : min_size;
+            is64bit = (!(val & PCI_BASE_ADDRESS_SPACE_IO) &&
                                  (val & PCI_BASE_ADDRESS_MEM_TYPE_MASK)
                                  == PCI_BASE_ADDRESS_MEM_TYPE_64);

-            if (pci->bars[i].is64)
+            pci_bios_bus_reserve(bus, pci_addr_to_type(val), size);
+
+            entry = pci_region_create_entry(bus, pci, size, type, is64bit);
+            if (!entry)
+                return -1;
+            entry->bar = i;
+
+            if (is64bit)
                 i++;
         }
     }
@@ -411,6 +460,11 @@ static void pci_bios_check_devices(struct pci_bus *busses)
                 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);
+            entry = pci_region_create_entry(parent, s->bus_dev,
+                                            s->r[type].size, type, 0);
+            if (!entry)
+                return -1;
+            entry->this_bus = s;
         }
         dprintf(1, "PCI: secondary bus %d sizes: io %x, mem %x, prefmem %x\n",
                 secondary_bus,
@@ -418,6 +472,7 @@ static void pci_bios_check_devices(struct pci_bus *busses)
                 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)
@@ -526,34 +581,35 @@ static void pci_bios_map_devices(struct pci_bus *busses)
     }

// 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);
-
-            if (pci->bars[i].is64) {
-                i++;
-                pci_set_io_region_addr(pci, i, 0);
+    int bus;
+    struct pci_region_entry *entry, *next;
+    for (bus = 0; bus<=MaxPCIBus; bus++) {
+        int type;
+        for (type = 0; type < PCI_REGION_TYPE_COUNT; type++) {
+            list_foreach_entry_safe(busses[bus].r[type].list,
+                                      next, entry) {
+                if (!entry->this_bus) {
+                    entry->base = pci_bios_bus_get_addr(&busses[bus],
+                                                      entry->type, entry->size);
+                    pci_set_io_region_addr(entry->dev, entry->bar, entry->base);
+                    if (entry->is64bit)
+                        pci_set_io_region_addr(entry->dev, entry->bar, 0);
+
+                    dprintf(1, "PCI: map device bdf=%02x:%02x.%x \tbar %d"
+                                "\tsize\t0x%08x\tbase 0x%x type %s\n",
+                               pci_bdf_to_bus(entry->dev->bdf),
+                               pci_bdf_to_dev(entry->dev->bdf),
+                               pci_bdf_to_fn(entry->dev->bdf),
+                               entry->bar, entry->size, entry->base,
+                               region_type_name[entry->type]);
+                }
+                list_del(entry);
+                free(entry);
             }
         }
     }
 }

-
 /****************************************************************
  * Main setup code
  ****************************************************************/
@@ -588,7 +644,9 @@ pci_setup(void)
         return;
     }
     memset(busses, 0, sizeof(*busses) * (MaxPCIBus + 1));
-    pci_bios_check_devices(busses);
+    if (pci_bios_check_devices(busses))
+        return;
+
     if (pci_bios_init_root_regions(&busses[0], start, end) != 0) {
         panic("PCI: out of address space\n");
     }

[PATCH 2/6] Redesign of pciinit.c (take 2)

[Kevin O'Connor]

On Thu, Mar 15, 2012 at 04:29:30PM +1300, Alexey Korolev wrote:
> On 14/03/12 13:48, Kevin O'Connor wrote:
> > On Tue, Mar 13, 2012 at 05:45:19PM +1300, Alexey Korolev wrote:
> > > Added pci_region_entry structure and list operations to pciinit.c
> > > List is filled with entries during pci_check_devices.
> > > List is used just for printing space allocation if we were using lists. 
> > > Next step will resource allocation using mapping functions.

[...]
> > struct {
> >    u32 addr;
> >    u32 size;
> >    int is64;
> > } bars[PCI_NUM_REGIONS];

[...]
> Yes I see what you mean here.

Thanks - I do find this patch much easier to understand.  I do have
some comments on the patch (see below).
> > The code is being changed -
> > it's not new code being added and old code being deleted - the patches
> > need to reflect that.
>
> Because of structural changes it is not possible to completely avoid
> this scenario where new code is added and old deleted.  In this
> patch series I tried my best to make migration as obvious and safe
> as possible.  So the existing approach (with your suggestions) for
> pciinit.c redesign is this:
> Introduce list operations
> Introduce pci_region_entry structure and add code which fills this new structure.
>
> We don't modify resource addresses calculations, but we use pci_region_entry data to do resource assignment.
> 3. Modify resource addresses calculations to be based on linked lists of region entries.
> 4. Remove code which fills the arrays, remove use of arrays for mapping.
> (note 3&4 could be combined altogether but it will be harder to read then)

On patch 3/4, neither patch should introduce code that isn't actually
used nor leave code that isn't used still in.  So, for example, if the
arrays are still used after patch 3 then it's okay to leave them to
patch 4, but if they are no longer used at all they should be removed
within patch 3.
> Could you please have a look at the other parts in this series and
> let me know if you are happy about this approach, so I won't have to
> redo patchwork too many times?

patch 1/6 - I'd prefer to have a list.h with struct
  hlist_head/hlist_node and container_of before extending to other
  parts of seabios.  That said, I'm okay with what you have for
  pciinit - we can introduce list.h afterwards.

patch 3/4 - was confusing to me as it added new code in one patch and
  removed the replaced code in the second patch.

patch 5 - looked okay to me.

Thanks for looking at this - I know it's time consuming.  Given the
churn in this area I want to make sure there is a good understanding
before any big changes.

comments on the patch:
[...]
> +struct pci_region_entry *
> +pci_region_create_entry(struct pci_bus *bus, struct pci_device *dev,
>                   u32 size, int type, int is64bit)
>
> +{
> struct pci_region_entry *entry= malloc_tmp(sizeof(*entry));
> if (!entry) {
>        warn_noalloc();
>        return NULL;

Minor - whitespace.

[...]
> +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 +419,27 @@ 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 type, is64bit;

Minor - I prefer to use C99 inline variable declarations though it
isn't a requirement.
>        min_size = (type == PCI_REGION_TYPE_IO) ? (1<<PCI_IO_INDEX_SHIFT):
>                 (1<<PCI_MEM_INDEX_SHIFT);
>        size = (size > min_size) ? size : min_size;

My only real comment: Why the min_size change?  Is that a fix of some
sort or is it related to the move to lists?

[...]
> /****************************************************************
> Main setup code

Minor - whitespace change.

-Kevin

[PATCH 2/6] Redesign of pciinit.c (take 2)

[Alexey Korolev]

On 16/03/12 13:55, Kevin O'Connor wrote:
> On Thu, Mar 15, 2012 at 04:29:30PM +1300, Alexey Korolev wrote:
> > On 14/03/12 13:48, Kevin O'Connor wrote:
> > > On Tue, Mar 13, 2012 at 05:45:19PM +1300, Alexey Korolev wrote:
> > > > Added pci_region_entry structure and list operations to pciinit.c
> > > > List is filled with entries during pci_check_devices.
> > > > List is used just for printing space allocation if we were using lists. 
> > > > Next step will resource allocation using mapping functions.
>
> [...]
> > > struct {
> > >    u32 addr;
> > >    u32 size;
> > >    int is64;
> > > } bars[PCI_NUM_REGIONS];
>
> [...]
> > Yes I see what you mean here.
>
> Thanks - I do find this patch much easier to understand.  I do have
> some comments on the patch (see below).
> > > The code is being changed -
> > > it's not new code being added and old code being deleted - the patches
> > > need to reflect that.
> >
> > Because of structural changes it is not possible to completely avoid
> > this scenario where new code is added and old deleted.  In this
> > patch series I tried my best to make migration as obvious and safe
> > as possible.  So the existing approach (with your suggestions) for
> > pciinit.c redesign is this:
> > Introduce list operations
> > Introduce pci_region_entry structure and add code which fills this new structure.
> >
> > We don't modify resource addresses calculations, but we use pci_region_entry data to do resource assignment.
> > 3. Modify resource addresses calculations to be based on linked lists of region entries.
> > 4. Remove code which fills the arrays, remove use of arrays for mapping.
> > (note 3&4 could be combined altogether but it will be harder to read then)
>
> On patch 3/4, neither patch should introduce code that isn't actually
> used nor leave code that isn't used still in.  So, for example, if the
> arrays are still used after patch 3 then it's okay to leave them to
> patch 4, but if they are no longer used at all they should be removed
> within patch 3.
> > Could you please have a look at the other parts in this series and
> > let me know if you are happy about this approach, so I won't have to
> > redo patchwork too many times?
>
> patch 1/6 - I'd prefer to have a list.h with struct
>   hlist_head/hlist_node and container_of before extending to other
>   parts of seabios.  That said, I'm okay with what you have for
>   pciinit - we can introduce list.h afterwards.

Then, it should be a separate patch. It's is better to do this afterwards.
> patch 3/4 - was confusing to me as it added new code in one patch and
>   removed the replaced code in the second patch.
>
> patch 5 - looked okay to me.
>
> Thanks for looking at this - I know it's time consuming.  Given the
> churn in this area I want to make sure there is a good understanding
> before any big changes.
>
> comments on the patch:
> [...]
> > +struct pci_region_entry *
> > +pci_region_create_entry(struct pci_bus *bus, struct pci_device *dev,
> >                   u32 size, int type, int is64bit)
> >
> > +{
> > struct pci_region_entry *entry= malloc_tmp(sizeof(*entry));
> > if (!entry) {
> >        warn_noalloc();
> >        return NULL;
>
> Minor - whitespace.
>
> [...]
> > +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 +419,27 @@ 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 type, is64bit;
>
> Minor - I prefer to use C99 inline variable declarations though it
> isn't a requirement.
> >        min_size = (type == PCI_REGION_TYPE_IO) ? (1<<PCI_IO_INDEX_SHIFT):
> >                 (1<<PCI_MEM_INDEX_SHIFT);
> >        size = (size > min_size) ? size : min_size;
>
> My only real comment: Why the min_size change?  Is that a fix of some
> sort or is it related to the move to lists?

This is a good question.
The min_size changes are to keep the exactly the same behaviour as the original implementation,
when each PCI MEM bar is aligned to 4KB (1<<PCI_MEM_INDEX_SHIFT).
The PCI spec. doesn't state the 4KB align requirement.
So if this 4KB requirement is not coming from qemu, it makes sense to remove the
min_size changes. Probably it will be better to remove this as a separate commit, to simplify
bug location in case of problems.
> [...]
> > /****************************************************************
> > Main setup code
>
> Minor - whitespace change.
>
> -Kevin

[PATCH 3/6] Switch from array based approach to lists of pci_region_entries

[Alexey Korolev]

Now we use the list of pci_region_entries instead of arrays of bases.
In this patch in addition to dumping resource allocations using
pci_region_entry, we add actual PCI resource assignment.

Note: I commented old code and split patches 3/6 and 4/6 just for
better patch readability.

Signed-off-by: Alexey Korolev 
---
 src/pciinit.c |  106 +++++++++++++++++++++++++--------------------------------
 1 files changed, 46 insertions(+), 60 deletions(-)

diff --git a/src/pciinit.c b/src/pciinit.c
index 2bf5473..f766a75 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

@@ -48,38 +47,14 @@ struct pci_region_entry {
 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)
@@ -389,19 +364,10 @@ pci_region_create_entry(struct pci_bus *bus, struct pci_device *dev,

list_add_head(&bus->r[type].list, entry);
     entry->parent_bus = bus;
-    return entry;
-}
-
-static void pci_bios_bus_reserve(struct pci_bus *bus, int type, u32 size)
-{
-    u32 index;
-
-    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;
+    return entry;
 }

static int pci_bios_check_devices(struct pci_bus *busses)
@@ -420,28 +386,24 @@ static int pci_bios_check_devices(struct pci_bus *busses)
         int i;
         for (i = 0; i < PCI_NUM_REGIONS; i++) {
             u32 val, size, min_size;                       entry->dev->bdf, entry->bar, entry->size, entry->base,
                       region_type_name[entry->type]);
-    } else {
-        entry->this_bus->r[entry->type].base = entry->base;
-        dprintf(1, "Secondary bus %d\t\tsize\t0x%08x\tbase 0x%x type %s\n",
+
+        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;
-            int type;
+            int is64, type;
             pci_bios_get_bar(pci, i, &val, &size);
             if (val == 0)
                 continue;
             type = pci_addr_to_type(val);
-            min_size = (type == PCI_REGION_TYPE_IO) ? (1<<PCI_IO_INDEX_SHIFT):
-                     (1<<PCI_MEM_INDEX_SHIFT);
+            min_size = (type == PCI_REGION_TYPE_IO) ? PCI_DEV_IO_MINSIZE:
+                     PCI_DEV_MEM_MINSIZE;
             size = (size > min_size) ? size : min_size;

-            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);
-
-            entry = pci_region_create_entry(bus, pci, size, type, pci->bars[i].is64);
+            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 (pci->bars[i].is64)
+            if (is64)
                 i++;
         }
     }
@@ -461,7 +423,6 @@ static int pci_bios_check_devices(struct pci_bus *busses)
             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);
             entry = pci_region_create_entry(parent, s->bus_dev,
                                             s->r[type].size, type, 0);
             if (!entry)
@@ -503,7 +464,7 @@ 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;
@@ -609,22 +570,48 @@ static void pci_bios_map_devices(struct pci_bus *busses)
         }
     }
 }
-
-static void pci_region_dump_one_entry(struct pci_region_entry *entry)
+*/
+static void pci_region_map_one_entry(struct pci_region_entry *entry)
 {
     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]);
-    } else {
-        entry->this_bus->r[entry->type].base = entry->base;
-        dprintf(1, "Secondary bus %d\t\tsize\t0x%08x\tbase 0x%x type %s\n",
+
+        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;
+    }
+
+    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]);
-   }
+
+    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 >> 8);
+        pci_config_writew(bdf, PCI_IO_LIMIT_UPPER16, 0);
+    }
+    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;
 }

-static void pci_bios_dump_devices(struct pci_bus *busses)
+static void pci_bios_map_devices(struct pci_bus *busses)
 {
     struct pci_region_entry *entry, *next;

@@ -639,7 +626,7 @@ static void pci_bios_dump_devices(struct pci_bus *busses)
                         if (size == entry->size) {
                             entry->base = busses[bus].r[type].base;
                             busses[bus].r[type].base += size;
-                            pci_region_dump_one_entry(entry);
+                            pci_region_map_one_entry(entry);
                             list_del(entry);
                             free(entry);
                     }
@@ -692,7 +679,6 @@ pci_setup(void)

dprintf(1, "=== PCI new allocation pass #2 ===\n");
     pci_bios_map_devices(busses);
-    pci_bios_dump_devices(busses);

pci_bios_init_devices();

[PATCH 4/6] Delete array based resource assignment code.

[Alexey Korolev]

This patch deletes array based code need for resource assignment.

The patches 3 and 4 are split just for better readability.

Signed-off-by: Alexey Korolev 
---
 src/pciinit.c |  109 +--------------------------------------------------------
 1 files changed, 1 insertions(+), 108 deletions(-)

diff --git a/src/pciinit.c b/src/pciinit.c
index f766a75..468aa66 100644
--- a/src/pciinit.c
+++ b/src/pciinit.c
@@ -462,115 +462,8 @@ static int pci_bios_init_root_regions(struct pci_bus *bus, u32 start, u32 end)

/****************************************************************
- * 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)
-{
-    // Setup bases for root bus.
-    dprintf(1, "PCI: init bases bus 0 (primary)\n");
-    pci_bios_init_bus_bases(&busses[0]);
-
-    // 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);
-
-        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);
-        pci_config_writew(bdf, PCI_IO_BASE_UPPER16, 0);
-        pci_config_writeb(bdf, PCI_IO_LIMIT, limit >> PCI_IO_SHIFT);
-        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);
-        pci_config_writel(bdf, PCI_PREF_BASE_UPPER32, 0);
-        pci_config_writel(bdf, PCI_PREF_LIMIT_UPPER32, 0);
-    }
-
-    // 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);
-
-            if (pci->bars[i].is64) {
-                i++;
-                pci_set_io_region_addr(pci, i, 0);
-            }
-        }
-    }
-}
-*/
 static void pci_region_map_one_entry(struct pci_region_entry *entry)
 {
     if (!entry->this_bus ) {

[PATCH 5/6] Get rid of size element of pci_bus->r structure

[Alexey Korolev]

The size element of pci_bus->r structure is no longer need as the
information about bridge region size is stored in pci_region_entry
structure.

Signed-off-by: Alexey Korolev 
---
 src/pciinit.c |   21 +++++++++------------
 1 files changed, 9 insertions(+), 12 deletions(-)

diff --git a/src/pciinit.c b/src/pciinit.c
index 468aa66..0743e68 100644
--- a/src/pciinit.c
+++ b/src/pciinit.c
@@ -48,7 +48,6 @@ struct pci_bus {
     struct {
         /* pci region stats */
         u32 sum, max;
-        u32 size;
         u32 base;
         struct pci_region_entry *list;
     } r[PCI_REGION_TYPE_COUNT];
@@ -416,24 +415,22 @@ static int 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);
-            entry = pci_region_create_entry(parent, s->bus_dev,
-                                            s->r[type].size, type, 0);
+            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;
 }

[PATCH 6/6] Use linked lists in pmm.c and stack.c

[Alexey Korolev]

This patch simplifies a bit complicated 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(