[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH 3/4] Switch from array based resource allocation
From: |
Kevin O'Connor |
Subject: |
Re: [Qemu-devel] [PATCH 3/4] Switch from array based resource allocation to list |
Date: |
Sun, 1 Apr 2012 04:44:15 -0400 |
User-agent: |
Mutt/1.5.21 (2010-09-15) |
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;
}
}
}
- Re: [Qemu-devel] [PATCH 3/4] Switch from array based resource allocation to list, Kevin O'Connor, 2012/04/01
- Re: [Qemu-devel] [PATCH 3/4] Switch from array based resource allocation to list,
Kevin O'Connor <=
- Re: [Qemu-devel] [PATCH 3/4] Switch from array based resource allocation to list, Alexey Korolev, 2012/04/03
- Re: [Qemu-devel] [PATCH 3/4] Switch from array based resource allocation to list, Kevin O'Connor, 2012/04/03
- Re: [Qemu-devel] [PATCH 3/4] Switch from array based resource allocation to list, Alexey Korolev, 2012/04/11
- Re: [Qemu-devel] [PATCH 3/4] Switch from array based resource allocation to list, Kevin O'Connor, 2012/04/11
- Re: [Qemu-devel] [PATCH 3/4] Switch from array based resource allocation to list, Alexey Korolev, 2012/04/11
- Re: [Qemu-devel] [PATCH 3/4] Switch from array based resource allocation to list, Kevin O'Connor, 2012/04/12
- Re: [Qemu-devel] [PATCH 3/4] Switch from array based resource allocation to list, Alexey Korolev, 2012/04/19
- Re: [Qemu-devel] [PATCH 3/4] Switch from array based resource allocation to list, Kevin O'Connor, 2012/04/19
- Re: [Qemu-devel] [PATCH 3/4] Switch from array based resource allocation to list, Alexey Korolev, 2012/04/20