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(-)
This linked list implementation is partially based on kernel code. So it should be quite stable :)
Signed-off-by: Alexey Korolev alexey.korolev@endace.com --- 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;
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 alexey.korolev@endace.com --- 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 ****************************************************************/
Now let simplify a bit a cumbersome code in pmm.c and stack.c
Signed-off-by: Alexey Korolev alexey.korolev@endace.com --- 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(
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
-
Alexey Korolev -
Kevin O'Connor