[PATCH 0/8] Introduce list.h abstraction
This series implements a doubly linked list (hlist) abstraction and adds helper code for manipulating these lists. Common users of linked lists in the code are then converted to use these abstractions. -Kevin Kevin O'Connor (8): Minor - move "tracked memory alloc" code in pmm.c. Introduce and convert pmm code to use standard list helpers. Minor - relocate code in stacks.c to keep low-level thread code together. Introduce helper function have_threads() in stacks.c. Convert stacks.c to use standard list manipulation code. Convert boot.c to use standard list manipulation code. Convert pciinit.c to use standard list manipulation code. Convert PCIDevices list to use standard list manipultion code. src/ata.c | 2 +- src/boot.c | 37 ++++---- src/list.h | 76 +++++++++++++++++ src/mptable.c | 2 +- src/pci.c | 7 +- src/pci.h | 9 +- src/pciinit.c | 64 +++++++------- src/pmm.c | 265 ++++++++++++++++++++++++++------------------------------- src/stacks.c | 149 ++++++++++++++++---------------- src/types.h | 3 + src/usb-ehci.c | 2 +- src/usb.c | 8 +- 12 files changed, 341 insertions(+), 283 deletions(-) create mode 100644 src/list.h -- 1.7.11.7
Move the "pmm_malloc" code closer to the low level alloc functions it calls. Signed-off-by: Kevin O'Connor <kevin@koconnor.net> --- src/pmm.c | 196 +++++++++++++++++++++++++++++++------------------------------- 1 file changed, 98 insertions(+), 98 deletions(-) diff --git a/src/pmm.c b/src/pmm.c index c4156ba..abacb28 100644 --- a/src/pmm.c +++ b/src/pmm.c @@ -164,6 +164,104 @@ findLast(struct zone_s *zone) /**************************************************************** + * tracked memory allocations + ****************************************************************/ + +// Allocate memory from the given zone and track it as a PMM allocation +void * __malloc +pmm_malloc(struct zone_s *zone, u32 handle, u32 size, u32 align) +{ + ASSERT32FLAT(); + if (!size) + return NULL; + + // Find and reserve space for bookkeeping. + struct allocdetail_s *detail = allocSpace( + &ZoneTmpHigh, sizeof(*detail), MALLOC_MIN_ALIGN, NULL); + if (!detail) { + detail = allocSpace(&ZoneTmpLow, sizeof(*detail) + , MALLOC_MIN_ALIGN, NULL); + if (!detail) + return NULL; + } + + // Find and reserve space for main allocation + void *data = allocSpace(zone, size, align, &detail->datainfo); + if (!data) { + freeSpace(&detail->detailinfo); + return NULL; + } + + dprintf(8, "pmm_malloc zone=%p handle=%x size=%d align=%x" + " ret=%p (detail=%p)\n" + , zone, handle, size, align + , data, detail); + detail->handle = handle; + + return data; +} + +// Free a data block allocated with pmm_malloc +int +pmm_free(void *data) +{ + ASSERT32FLAT(); + struct allocinfo_s *info = findAlloc(data); + if (!info || data == (void*)info || data == info->dataend) + return -1; + struct allocdetail_s *detail = container_of( + info, struct allocdetail_s, datainfo); + dprintf(8, "pmm_free %p (detail=%p)\n", data, detail); + freeSpace(info); + freeSpace(&detail->detailinfo); + return 0; +} + +// Find the amount of free space in a given zone. +static u32 +pmm_getspace(struct zone_s *zone) +{ + // XXX - doesn't account for ZoneLow being able to grow. + // XXX - results not reliable when CONFIG_THREAD_OPTIONROMS + u32 maxspace = 0; + struct allocinfo_s *info; + for (info = zone->info; info; info = info->next) { + u32 space = info->allocend - info->dataend; + if (space > maxspace) + maxspace = space; + } + + if (zone != &ZoneTmpHigh && zone != &ZoneTmpLow) + return maxspace; + // Account for space needed for PMM tracking. + u32 reserve = ALIGN(sizeof(struct allocdetail_s), MALLOC_MIN_ALIGN); + if (maxspace <= reserve) + return 0; + return maxspace - reserve; +} + +// Find the data block allocated with pmm_malloc with a given handle. +static void * +pmm_find(u32 handle) +{ + int i; + for (i=0; i<ARRAY_SIZE(Zones); i++) { + struct zone_s *zone = Zones[i]; + struct allocinfo_s *info; + for (info = zone->info; info; info = info->next) { + if (info->data != (void*)info) + continue; + struct allocdetail_s *detail = container_of( + info, struct allocdetail_s, detailinfo); + if (detail->handle == handle) + return detail->datainfo.data; + } + } + return NULL; +} + + +/**************************************************************** * 0xc0000-0xf0000 management ****************************************************************/ @@ -359,104 +457,6 @@ malloc_prepboot(void) /**************************************************************** - * tracked memory allocations - ****************************************************************/ - -// Allocate memory from the given zone and track it as a PMM allocation -void * __malloc -pmm_malloc(struct zone_s *zone, u32 handle, u32 size, u32 align) -{ - ASSERT32FLAT(); - if (!size) - return NULL; - - // Find and reserve space for bookkeeping. - struct allocdetail_s *detail = allocSpace( - &ZoneTmpHigh, sizeof(*detail), MALLOC_MIN_ALIGN, NULL); - if (!detail) { - detail = allocSpace(&ZoneTmpLow, sizeof(*detail) - , MALLOC_MIN_ALIGN, NULL); - if (!detail) - return NULL; - } - - // Find and reserve space for main allocation - void *data = allocSpace(zone, size, align, &detail->datainfo); - if (!data) { - freeSpace(&detail->detailinfo); - return NULL; - } - - dprintf(8, "pmm_malloc zone=%p handle=%x size=%d align=%x" - " ret=%p (detail=%p)\n" - , zone, handle, size, align - , data, detail); - detail->handle = handle; - - return data; -} - -// Free a data block allocated with pmm_malloc -int -pmm_free(void *data) -{ - ASSERT32FLAT(); - struct allocinfo_s *info = findAlloc(data); - if (!info || data == (void*)info || data == info->dataend) - return -1; - struct allocdetail_s *detail = container_of( - info, struct allocdetail_s, datainfo); - dprintf(8, "pmm_free %p (detail=%p)\n", data, detail); - freeSpace(info); - freeSpace(&detail->detailinfo); - return 0; -} - -// Find the amount of free space in a given zone. -static u32 -pmm_getspace(struct zone_s *zone) -{ - // XXX - doesn't account for ZoneLow being able to grow. - // XXX - results not reliable when CONFIG_THREAD_OPTIONROMS - u32 maxspace = 0; - struct allocinfo_s *info; - for (info = zone->info; info; info = info->next) { - u32 space = info->allocend - info->dataend; - if (space > maxspace) - maxspace = space; - } - - if (zone != &ZoneTmpHigh && zone != &ZoneTmpLow) - return maxspace; - // Account for space needed for PMM tracking. - u32 reserve = ALIGN(sizeof(struct allocdetail_s), MALLOC_MIN_ALIGN); - if (maxspace <= reserve) - return 0; - return maxspace - reserve; -} - -// Find the data block allocated with pmm_malloc with a given handle. -static void * -pmm_find(u32 handle) -{ - int i; - for (i=0; i<ARRAY_SIZE(Zones); i++) { - struct zone_s *zone = Zones[i]; - struct allocinfo_s *info; - for (info = zone->info; info; info = info->next) { - if (info->data != (void*)info) - continue; - struct allocdetail_s *detail = container_of( - info, struct allocdetail_s, detailinfo); - if (detail->handle == handle) - return detail->datainfo.data; - } - } - return NULL; -} - - -/**************************************************************** * pmm interface ****************************************************************/ -- 1.7.11.7
Signed-off-by: Kevin O'Connor <kevin@koconnor.net> --- src/list.h | 76 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/pmm.c | 77 +++++++++++++++++++++++-------------------------------------- src/types.h | 3 +++ 3 files changed, 108 insertions(+), 48 deletions(-) create mode 100644 src/list.h diff --git a/src/list.h b/src/list.h new file mode 100644 index 0000000..db7e962 --- /dev/null +++ b/src/list.h @@ -0,0 +1,76 @@ +#ifndef __LIST_H +#define __LIST_H + +#include "types.h" // container_of + + +/**************************************************************** + * hlist - Double linked lists with a single pointer list head + ****************************************************************/ + +struct hlist_node { + struct hlist_node *next, **pprev; +}; + +struct hlist_head { + struct hlist_node *first; +}; + +static inline int +hlist_empty(const struct hlist_head *h) +{ + return !h->first; +} + +static inline void +hlist_del(struct hlist_node *n) +{ + struct hlist_node *next = n->next; + struct hlist_node **pprev = n->pprev; + *pprev = next; + if (next) + next->pprev = pprev; +} + +static inline void +hlist_add(struct hlist_node *n, struct hlist_node **pprev) +{ + struct hlist_node *next = *pprev; + n->pprev = pprev; + n->next = next; + if (next) + next->pprev = &n->next; + *pprev = n; +} + +static inline void +hlist_add_head(struct hlist_node *n, struct hlist_head *h) +{ + hlist_add(n, &h->first); +} + +static inline void +hlist_add_before(struct hlist_node *n, struct hlist_node *next) +{ + hlist_add(n, next->pprev); +} + +static inline void +hlist_add_after(struct hlist_node *n, struct hlist_node *prev) +{ + hlist_add(n, &prev->next); +} + +#define hlist_for_each_entry(pos, head, member) \ + for (pos = container_of((head)->first, typeof(*pos), member) \ + ; pos != container_of(NULL, typeof(*pos), member) \ + ; pos = container_of(pos->member.next, typeof(*pos), member)) + +#define hlist_for_each_entry_safe(pos, pprev, head, member) \ + for (pprev = &(head)->first \ + ; *pprev \ + && ({ pos=container_of((*pprev)->next, typeof(*pos), member); 1; }) \ + ; pprev = &(*pprev)->next) + + +#endif // list.h diff --git a/src/pmm.c b/src/pmm.c index abacb28..da97283 100644 --- a/src/pmm.c +++ b/src/pmm.c @@ -10,10 +10,11 @@ #include "farptr.h" // GET_FARVAR #include "biosvar.h" // GET_BDA #include "optionroms.h" // OPTION_ROM_ALIGN +#include "list.h" // hlist_node // Information on a reserved area. struct allocinfo_s { - struct allocinfo_s *next, **pprev; + struct hlist_node node; void *data, *dataend, *allocend; }; @@ -26,7 +27,7 @@ struct allocdetail_s { // The various memory zones. struct zone_s { - struct allocinfo_s *info; + struct hlist_head head; }; struct zone_s ZoneLow VARVERIFY32INIT, ZoneHigh VARVERIFY32INIT; @@ -47,24 +48,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) { + hlist_for_each_entry(info, &zone->head, node) { 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; fill->data = newallocend; fill->dataend = newallocend + size; fill->allocend = allocend; info->allocend = newallocend; - info->pprev = &fill->next; - *pprev = fill; + hlist_add_before(&fill->node, &info->node); return newallocend; } } @@ -75,14 +72,11 @@ allocSpace(struct zone_s *zone, u32 size, u32 align, struct allocinfo_s *fill) 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) - next->allocend = info->allocend; - next->pprev = pprev; - } + struct allocinfo_s *next = container_of_or_null( + info->node.next, struct allocinfo_s, node); + if (next && next->allocend == info->data) + next->allocend = info->allocend; + hlist_del(&info->node); } // Add new memory to a zone @@ -90,23 +84,18 @@ static void addSpace(struct zone_s *zone, void *start, void *end) { // Find position to add space - struct allocinfo_s **pprev = &zone->info, *info; - for (;;) { - info = *pprev; - if (!info || info->data < start) + struct allocinfo_s *info; + struct hlist_node **pprev; + hlist_for_each_entry_safe(info, pprev, &zone->head, node) { + if (info->data < start) break; - pprev = &info->next; } // 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; + hlist_add(&tempdetail.datainfo.node, pprev); // Allocate final allocation info. struct allocdetail_s *detail = allocSpace( @@ -115,21 +104,18 @@ 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; + hlist_del(&tempdetail.datainfo.node); warn_noalloc(); return; } } // Replace temp alloc space with final alloc space + pprev = tempdetail.datainfo.node.pprev; + hlist_del(&tempdetail.datainfo.node); memcpy(&detail->datainfo, &tempdetail.datainfo, sizeof(detail->datainfo)); detail->handle = PMM_DEFAULT_HANDLE; - - *tempdetail.datainfo.pprev = &detail->datainfo; - if (tempdetail.datainfo.next) - tempdetail.datainfo.next->pprev = &detail->datainfo.next; + hlist_add(&detail->datainfo.node, pprev); } // Search all zones for an allocation obtained from allocSpace() @@ -138,11 +124,11 @@ findAlloc(void *data) { int i; for (i=0; i<ARRAY_SIZE(Zones); i++) { - struct zone_s *zone = Zones[i]; struct allocinfo_s *info; - for (info = zone->info; info; info = info->next) + hlist_for_each_entry(info, &Zones[i]->head, node) { if (info->data == data) return info; + } } return NULL; } @@ -151,15 +137,11 @@ findAlloc(void *data) static struct allocinfo_s * findLast(struct zone_s *zone) { - struct allocinfo_s *info = zone->info; - if (!info) - return NULL; - for (;;) { - struct allocinfo_s *next = info->next; - if (!next) - return info; - info = next; + struct allocinfo_s *info, *last = NULL; + hlist_for_each_entry(info, &zone->head, node) { + last = info; } + return last; } @@ -225,7 +207,7 @@ pmm_getspace(struct zone_s *zone) // XXX - results not reliable when CONFIG_THREAD_OPTIONROMS u32 maxspace = 0; struct allocinfo_s *info; - for (info = zone->info; info; info = info->next) { + hlist_for_each_entry(info, &zone->head, node) { u32 space = info->allocend - info->dataend; if (space > maxspace) maxspace = space; @@ -246,9 +228,8 @@ pmm_find(u32 handle) { int i; for (i=0; i<ARRAY_SIZE(Zones); i++) { - struct zone_s *zone = Zones[i]; struct allocinfo_s *info; - for (info = zone->info; info; info = info->next) { + hlist_for_each_entry(info, &Zones[i]->head, node) { if (info->data != (void*)info) continue; struct allocdetail_s *detail = container_of( @@ -405,8 +386,8 @@ malloc_init(void) int i; for (i=0; i<ARRAY_SIZE(Zones); i++) { struct zone_s *zone = Zones[i]; - if (zone->info) - zone->info->pprev = &zone->info; + if (zone->head.first) + zone->head.first->pprev = &zone->head.first; } } diff --git a/src/types.h b/src/types.h index 84582ac..9e22ab5 100644 --- a/src/types.h +++ b/src/types.h @@ -117,6 +117,9 @@ extern void __force_link_error__only_in_16bit(void) __noreturn; #define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) +#define container_of_or_null(ptr, type, member) ({ \ + const typeof( ((type *)0)->member ) *___mptr = (ptr); \ + ___mptr ? container_of(___mptr, type, member) : NULL; }) #define likely(x) __builtin_expect(!!(x), 1) #define unlikely(x) __builtin_expect(!!(x), 0) -- 1.7.11.7
Just code movement - no actual code changes. Signed-off-by: Kevin O'Connor <kevin@koconnor.net> --- src/stacks.c | 109 +++++++++++++++++++++++++++++++---------------------------- 1 file changed, 57 insertions(+), 52 deletions(-) diff --git a/src/stacks.c b/src/stacks.c index 7423939..bf9db06 100644 --- a/src/stacks.c +++ b/src/stacks.c @@ -279,58 +279,6 @@ switch_next(struct thread_info *cur) : "ebx", "edx", "esi", "edi", "cc", "memory"); } -// Low-level irq enable. -void VISIBLE16 -check_irqs(void) -{ - asm volatile("sti ; nop ; rep ; nop ; cli ; cld" : : :"memory"); -} - -// Briefly permit irqs to occur. -void -yield(void) -{ - if (MODESEGMENT) { - stack_hop_back(0, 0, check_irqs); - return; - } - extern void _cfunc16_check_irqs(void); - if (!CONFIG_THREADS) { - call16big(0, _cfunc16_check_irqs); - return; - } - struct thread_info *cur = getCurThread(); - if (cur == &MainThread) - // Permit irqs to fire - call16big(0, _cfunc16_check_irqs); - - // Switch to the next thread - switch_next(cur); -} - -void VISIBLE16 -wait_irq(void) -{ - asm volatile("sti ; hlt ; cli ; cld": : :"memory"); -} - -// Wait for next irq to occur. -void -yield_toirq(void) -{ - if (MODESEGMENT) { - stack_hop_back(0, 0, wait_irq); - return; - } - if (CONFIG_THREADS && MainThread.next != &MainThread) { - // Threads still active - do a yield instead. - yield(); - return; - } - extern void _cfunc16_wait_irq(void); - call16big(0, _cfunc16_wait_irq); -} - // Last thing called from a thread (called on "next" stack). static void __end_thread(struct thread_info *old) @@ -388,6 +336,63 @@ fail: func(data); } + +/**************************************************************** + * Thread helpers + ****************************************************************/ + +// Low-level irq enable. +void VISIBLE16 +check_irqs(void) +{ + asm volatile("sti ; nop ; rep ; nop ; cli ; cld" : : :"memory"); +} + +// Briefly permit irqs to occur. +void +yield(void) +{ + if (MODESEGMENT) { + stack_hop_back(0, 0, check_irqs); + return; + } + extern void _cfunc16_check_irqs(void); + if (!CONFIG_THREADS) { + call16big(0, _cfunc16_check_irqs); + return; + } + struct thread_info *cur = getCurThread(); + if (cur == &MainThread) + // Permit irqs to fire + call16big(0, _cfunc16_check_irqs); + + // Switch to the next thread + switch_next(cur); +} + +void VISIBLE16 +wait_irq(void) +{ + asm volatile("sti ; hlt ; cli ; cld": : :"memory"); +} + +// Wait for next irq to occur. +void +yield_toirq(void) +{ + if (MODESEGMENT) { + stack_hop_back(0, 0, wait_irq); + return; + } + if (CONFIG_THREADS && MainThread.next != &MainThread) { + // Threads still active - do a yield instead. + yield(); + return; + } + extern void _cfunc16_wait_irq(void); + call16big(0, _cfunc16_wait_irq); +} + // Wait for all threads (other than the main thread) to complete. void wait_threads(void) -- 1.7.11.7
Signed-off-by: Kevin O'Connor <kevin@koconnor.net> --- src/stacks.c | 22 ++++++++++++---------- 1 file changed, 12 insertions(+), 10 deletions(-) diff --git a/src/stacks.c b/src/stacks.c index bf9db06..65f2c99 100644 --- a/src/stacks.c +++ b/src/stacks.c @@ -248,6 +248,13 @@ struct thread_info MainThread VARFSEG = { }; #define THREADSTACKSIZE 4096 +// Check if any threads are running. +static int +have_threads(void) +{ + return CONFIG_THREADS && GET_FLATPTR(MainThread.next) != &MainThread; +} + // Return the 'struct thread_info' for the currently running thread. struct thread_info * getCurThread(void) @@ -287,7 +294,7 @@ __end_thread(struct thread_info *old) *old->pprev = old->next; free(old); dprintf(DEBUG_thread, "\\%08x/ End thread\n", (u32)old); - if (MainThread.next == &MainThread) + if (!have_threads()) dprintf(1, "All threads complete.\n"); } @@ -384,7 +391,7 @@ yield_toirq(void) stack_hop_back(0, 0, wait_irq); return; } - if (CONFIG_THREADS && MainThread.next != &MainThread) { + if (have_threads()) { // Threads still active - do a yield instead. yield(); return; @@ -398,9 +405,7 @@ void wait_threads(void) { ASSERT32FLAT(); - if (! CONFIG_THREADS) - return; - while (MainThread.next != &MainThread) + while (have_threads()) yield(); } @@ -480,10 +485,7 @@ yield_preempt(void) void check_preempt(void) { - if (! CONFIG_THREAD_OPTIONROMS || !GET_GLOBAL(CanPreempt) - || GET_FLATPTR(MainThread.next) == &MainThread) - return; - extern void _cfunc32flat_yield_preempt(void); - call32(_cfunc32flat_yield_preempt, 0, 0); + if (CONFIG_THREAD_OPTIONROMS && GET_GLOBAL(CanPreempt) && have_threads()) + call32(_cfunc32flat_yield_preempt, 0, 0); } -- 1.7.11.7
Signed-off-by: Kevin O'Connor <kevin@koconnor.net> --- src/stacks.c | 32 +++++++++++++++----------------- 1 file changed, 15 insertions(+), 17 deletions(-) diff --git a/src/stacks.c b/src/stacks.c index 65f2c99..0640a30 100644 --- a/src/stacks.c +++ b/src/stacks.c @@ -7,6 +7,7 @@ #include "biosvar.h" // GET_GLOBAL #include "util.h" // dprintf #include "bregs.h" // CR0_PE +#include "list.h" // hlist_node /**************************************************************** @@ -239,12 +240,11 @@ __call16_int(struct bregs *callregs, u16 offset) // Thread info - stored at bottom of each thread stack - don't change // without also updating the inline assembler below. struct thread_info { - struct thread_info *next; void *stackpos; - struct thread_info **pprev; + struct hlist_node node; }; struct thread_info MainThread VARFSEG = { - &MainThread, NULL, &MainThread.next + NULL, { &MainThread.node, &MainThread.node.next } }; #define THREADSTACKSIZE 4096 @@ -252,7 +252,8 @@ struct thread_info MainThread VARFSEG = { static int have_threads(void) { - return CONFIG_THREADS && GET_FLATPTR(MainThread.next) != &MainThread; + return (CONFIG_THREADS + && GET_FLATPTR(MainThread.node.next) != &MainThread.node); } // Return the 'struct thread_info' for the currently running thread. @@ -269,15 +270,16 @@ getCurThread(void) static void switch_next(struct thread_info *cur) { - struct thread_info *next = cur->next; + struct thread_info *next = container_of( + cur->node.next, struct thread_info, node); if (cur == next) // Nothing to do. return; asm volatile( " pushl $1f\n" // store return pc " pushl %%ebp\n" // backup %ebp - " movl %%esp, 4(%%eax)\n" // cur->stackpos = %esp - " movl 4(%%ecx), %%esp\n" // %esp = next->stackpos + " movl %%esp, (%%eax)\n" // cur->stackpos = %esp + " movl (%%ecx), %%esp\n" // %esp = next->stackpos " popl %%ebp\n" // restore %ebp " retl\n" // restore pc "1:\n" @@ -290,8 +292,7 @@ switch_next(struct thread_info *cur) static void __end_thread(struct thread_info *old) { - old->next->pprev = old->pprev; - *old->pprev = old->next; + hlist_del(&old->node); free(old); dprintf(DEBUG_thread, "\\%08x/ End thread\n", (u32)old); if (!have_threads()) @@ -312,23 +313,20 @@ 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; + hlist_add_after(&thread->node, &cur->node); dprintf(DEBUG_thread, "/%08x\\ Start thread\n", (u32)thread); asm volatile( // Start thread " pushl $1f\n" // store return pc " pushl %%ebp\n" // backup %ebp - " movl %%esp, 4(%%edx)\n" // cur->stackpos = %esp - " movl 4(%%ebx), %%esp\n" // %esp = thread->stackpos + " movl %%esp, (%%edx)\n" // cur->stackpos = %esp + " movl (%%ebx), %%esp\n" // %esp = thread->stackpos " calll *%%ecx\n" // Call func // End thread - " movl (%%ebx), %%ecx\n" // %ecx = thread->next - " movl 4(%%ecx), %%esp\n" // %esp = next->stackpos + " movl 4(%%ebx), %%ecx\n" // %ecx = thread->node.next + " movl -4(%%ecx), %%esp\n" // %esp = next->stackpos " movl %%ebx, %%eax\n" " calll %4\n" // call __end_thread(thread) " popl %%ebp\n" // restore %ebp -- 1.7.11.7
Signed-off-by: Kevin O'Connor <kevin@koconnor.net> --- src/boot.c | 37 +++++++++++++++++-------------------- 1 file changed, 17 insertions(+), 20 deletions(-) diff --git a/src/boot.c b/src/boot.c index c308602..6286e3c 100644 --- a/src/boot.c +++ b/src/boot.c @@ -15,6 +15,7 @@ #include "pci.h" // pci_bdf_to_* #include "usb.h" // struct usbdevice_s #include "csm.h" // csm_bootprio_* +#include "list.h" // hlist_node /**************************************************************** @@ -291,9 +292,9 @@ struct bootentry_s { }; int priority; const char *description; - struct bootentry_s *next; + struct hlist_node node; }; -static struct bootentry_s *BootList VARVERIFY32INIT; +static struct hlist_head BootList VARVERIFY32INIT; #define IPL_TYPE_FLOPPY 0x01 #define IPL_TYPE_HARDDISK 0x02 @@ -321,9 +322,9 @@ bootentry_add(int type, int prio, u32 data, const char *desc) , be->description, type, prio, data); // Add entry in sorted order. - struct bootentry_s **pprev; - for (pprev = &BootList; *pprev; pprev = &(*pprev)->next) { - struct bootentry_s *pos = *pprev; + struct hlist_node **pprev; + struct bootentry_s *pos; + hlist_for_each_entry_safe(pos, pprev, &BootList, node) { if (be->priority < pos->priority) break; if (be->priority > pos->priority) @@ -338,8 +339,7 @@ bootentry_add(int type, int prio, u32 data, const char *desc) && be->drive->cntl_id < pos->drive->cntl_id))) break; } - be->next = *pprev; - *pprev = be; + hlist_add(&be->node, pprev); } // Return the given priority if it's set - defaultprio otherwise. @@ -430,14 +430,13 @@ interactive_bootmenu(void) wait_threads(); // Show menu items - struct bootentry_s *pos = BootList; int maxmenu = 0; - while (pos) { + struct bootentry_s *pos; + hlist_for_each_entry(pos, &BootList, node) { char desc[60]; maxmenu++; printf("%d. %s\n", maxmenu , strtcpy(desc, pos->description, ARRAY_SIZE(desc))); - pos = pos->next; } // Get key press @@ -453,14 +452,13 @@ interactive_bootmenu(void) // Find entry and make top priority. int choice = scan_code - 1; - struct bootentry_s **pprev = &BootList; - while (--choice) - pprev = &(*pprev)->next; - pos = *pprev; - *pprev = pos->next; - pos->next = BootList; - BootList = pos; + hlist_for_each_entry(pos, &BootList, node) { + if (! --choice) + break; + } + hlist_del(&pos->node); pos->priority = 0; + hlist_add_head(&pos->node, &BootList); } // BEV (Boot Execution Vector) list @@ -498,8 +496,8 @@ bcv_prepboot(void) bootentry_add(IPL_TYPE_HALT, haltprio, 0, "HALT"); // Map drives and populate BEV list - struct bootentry_s *pos = BootList; - while (pos) { + struct bootentry_s *pos; + hlist_for_each_entry(pos, &BootList, node) { switch (pos->type) { case IPL_TYPE_BCV: call_bcv(pos->vector.seg, pos->vector.offset); @@ -520,7 +518,6 @@ bcv_prepboot(void) add_bev(pos->type, pos->data); break; } - pos = pos->next; } // If nothing added a floppy/hd boot - add it manually. -- 1.7.11.7
Signed-off-by: Kevin O'Connor <kevin@koconnor.net> --- src/pciinit.c | 64 ++++++++++++++++++++++++++++------------------------------- 1 file changed, 30 insertions(+), 34 deletions(-) diff --git a/src/pciinit.c b/src/pciinit.c index bb9355f..446dddf 100644 --- a/src/pciinit.c +++ b/src/pciinit.c @@ -13,7 +13,8 @@ #include "config.h" // CONFIG_* #include "memmap.h" // add_e820 #include "paravirt.h" // RamSize -#include "dev-q35.h" +#include "dev-q35.h" // Q35_HOST_BRIDGE_PCIEXBAR_ADDR +#include "list.h" // struct hlist_node /* PM Timer ticks per second (HZ) */ #define PM_TIMER_FREQUENCY 3579545 @@ -47,13 +48,13 @@ struct pci_region_entry { u64 align; int is64; enum pci_region_type type; - struct pci_region_entry *next; + struct hlist_node node; }; struct pci_region { /* pci region assignments */ u64 base; - struct pci_region_entry *list; + struct hlist_head list; }; struct pci_bus { @@ -539,30 +540,30 @@ static int pci_bios_bridge_region_is64(struct pci_region *r, } if ((pmem & PCI_PREF_RANGE_TYPE_MASK) != PCI_PREF_RANGE_TYPE_64) return 0; - struct pci_region_entry *entry = r->list; - while (entry) { + struct pci_region_entry *entry; + hlist_for_each_entry(entry, &r->list, node) { if (!entry->is64) return 0; - entry = entry->next; } return 1; } static u64 pci_region_align(struct pci_region *r) { - if (!r->list) - return 1; - // The first entry in the sorted list has the largest alignment - return r->list->align; + struct pci_region_entry *entry; + hlist_for_each_entry(entry, &r->list, node) { + // The first entry in the sorted list has the largest alignment + return entry->align; + } + return 1; } static u64 pci_region_sum(struct pci_region *r) { - struct pci_region_entry *entry = r->list; u64 sum = 0; - while (entry) { + struct pci_region_entry *entry; + hlist_for_each_entry(entry, &r->list, node) { sum += entry->size; - entry = entry->next; } return sum; } @@ -570,18 +571,14 @@ static u64 pci_region_sum(struct pci_region *r) static void pci_region_migrate_64bit_entries(struct pci_region *from, struct pci_region *to) { - struct pci_region_entry **pprev = &from->list, **last = &to->list; - while (*pprev) { - struct pci_region_entry *entry = *pprev; - if (!entry->is64) { - pprev = &entry->next; + struct hlist_node **pprev, **last = &to->list.first; + struct pci_region_entry *entry; + hlist_for_each_entry_safe(entry, pprev, &from->list, node) { + if (!entry->is64) continue; - } // Move from source list to destination list. - *pprev = entry->next; - entry->next = NULL; - *last = entry; - last = &entry->next; + hlist_del(&entry->node); + hlist_add(&entry->node, last); } } @@ -602,14 +599,13 @@ pci_region_create_entry(struct pci_bus *bus, struct pci_device *dev, entry->is64 = is64; entry->type = type; // 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; + struct hlist_node **pprev; + struct pci_region_entry *pos; + hlist_for_each_entry_safe(pos, pprev, &bus->r[type].list, node) { if (pos->align < align || (pos->align == align && pos->size < size)) break; } - entry->next = *pprev; - *pprev = entry; + hlist_add(&entry->node, pprev); return entry; } @@ -748,17 +744,17 @@ pci_region_map_one_entry(struct pci_region_entry *entry, u64 addr) static void pci_region_map_entries(struct pci_bus *busses, struct pci_region *r) { - struct pci_region_entry *entry = r->list; - while (entry) { + struct hlist_node **pprev; + struct pci_region_entry *entry; + hlist_for_each_entry_safe(entry, pprev, &r->list, node) { u64 addr = r->base; r->base += entry->size; if (entry->bar == -1) // Update bus base address if entry is a bridge region busses[entry->dev->secondary_bus].r[entry->type].base = addr; pci_region_map_one_entry(entry, addr); - struct pci_region_entry *next = entry->next; + hlist_del(&entry->node); free(entry); - entry = next; } } @@ -766,8 +762,8 @@ static void pci_bios_map_devices(struct pci_bus *busses) { if (pci_bios_init_root_regions(busses)) { struct pci_region r64_mem, r64_pref; - r64_mem.list = NULL; - r64_pref.list = NULL; + r64_mem.list.first = NULL; + r64_pref.list.first = NULL; pci_region_migrate_64bit_entries(&busses[0].r[PCI_REGION_TYPE_MEM], &r64_mem); pci_region_migrate_64bit_entries(&busses[0].r[PCI_REGION_TYPE_PREFMEM], -- 1.7.11.7
Signed-off-by: Kevin O'Connor <kevin@koconnor.net> --- src/ata.c | 2 +- src/mptable.c | 2 +- src/pci.c | 7 +++---- src/pci.h | 9 +++++---- src/usb-ehci.c | 2 +- src/usb.c | 8 ++++---- 6 files changed, 15 insertions(+), 15 deletions(-) diff --git a/src/ata.c b/src/ata.c index 59ae765..55bfa9a 100644 --- a/src/ata.c +++ b/src/ata.c @@ -1008,7 +1008,7 @@ static const struct pci_device_id pci_ata_tbl[] = { static void ata_scan(void) { - if (CONFIG_QEMU && !PCIDevices) { + if (CONFIG_QEMU && hlist_empty(&PCIDevices)) { // No PCI devices found - probably a QEMU "-M isapc" machine. // Try using ISA ports for ATA controllers. init_controller(NULL, IRQ_ATA1 diff --git a/src/mptable.c b/src/mptable.c index 7d485eb..0413063 100644 --- a/src/mptable.c +++ b/src/mptable.c @@ -67,7 +67,7 @@ mptable_setup(void) // PCI bus struct mpt_bus *buses = (void*)cpu, *bus = buses; - if (PCIDevices) { + if (!hlist_empty(&PCIDevices)) { memset(bus, 0, sizeof(*bus)); bus->type = MPT_TYPE_BUS; bus->busid = 0; diff --git a/src/pci.c b/src/pci.c index a92fb9b..6163a29 100644 --- a/src/pci.c +++ b/src/pci.c @@ -85,7 +85,7 @@ pci_next(int bdf, int bus) } } -struct pci_device *PCIDevices VARVERIFY32INIT; +struct hlist_head PCIDevices VARVERIFY32INIT; int MaxPCIBus VARFSEG; // Check if PCI is available at all @@ -107,7 +107,7 @@ pci_probe_devices(void) dprintf(3, "PCI probe\n"); struct pci_device *busdevs[256]; memset(busdevs, 0, sizeof(busdevs)); - struct pci_device **pprev = &PCIDevices; + struct hlist_node **pprev = &PCIDevices.first; int extraroots = romfile_loadint("etc/extra-pci-roots", 0); int bus = -1, lastbus = 0, rootbuses = 0, count=0; while (bus < 0xff && (bus < MaxPCIBus || rootbuses < extraroots)) { @@ -121,8 +121,7 @@ pci_probe_devices(void) return; } memset(dev, 0, sizeof(*dev)); - *pprev = dev; - pprev = &dev->next; + hlist_add(&dev->node, pprev); count++; // Find parent device. diff --git a/src/pci.h b/src/pci.h index aa54dd7..7760d21 100644 --- a/src/pci.h +++ b/src/pci.h @@ -2,6 +2,7 @@ #define __PCI_H #include "types.h" // u32 +#include "list.h" // hlist_node #define PCI_ROM_SLOT 6 #define PCI_NUM_REGIONS 7 @@ -43,7 +44,7 @@ struct pci_device *pci_find_class(u16 classid); struct pci_device { u16 bdf; u8 rootbus; - struct pci_device *next; + struct hlist_node node; struct pci_device *parent; // Configuration space device information @@ -58,7 +59,7 @@ struct pci_device { }; extern u64 pcimem_start, pcimem_end; extern u64 pcimem64_start, pcimem64_end; -extern struct pci_device *PCIDevices; +extern struct hlist_head PCIDevices; extern int MaxPCIBus; int pci_probe_host(void); void pci_probe_devices(void); @@ -66,8 +67,8 @@ static inline u32 pci_classprog(struct pci_device *pci) { return (pci->class << 8) | pci->prog_if; } -#define foreachpci(PCI) \ - for (PCI=PCIDevices; PCI; PCI=PCI->next) +#define foreachpci(PCI) \ + hlist_for_each_entry(PCI, &PCIDevices, node) int pci_next(int bdf, int bus); #define foreachbdf(BDF, BUS) \ diff --git a/src/usb-ehci.c b/src/usb-ehci.c index 69a9194..144dec4 100644 --- a/src/usb-ehci.c +++ b/src/usb-ehci.c @@ -368,7 +368,7 @@ ehci_setup(struct pci_device *pci, int busid, struct pci_device *comppci) cntl->companion[count++] = comppci; else if (pci_classprog(comppci) == PCI_CLASS_SERIAL_USB_OHCI) cntl->companion[count++] = comppci; - comppci = comppci->next; + comppci = container_of(comppci->node.next, struct pci_device, node); } run_thread(configure_ehci, cntl); diff --git a/src/usb.c b/src/usb.c index 6e43f13..ecccd75 100644 --- a/src/usb.c +++ b/src/usb.c @@ -422,13 +422,12 @@ usb_setup(void) // Look for USB controllers int count = 0; - struct pci_device *ehcipci = PCIDevices; - struct pci_device *pci; + struct pci_device *pci, *ehcipci = NULL; foreachpci(pci) { if (pci->class != PCI_CLASS_SERIAL_USB) continue; - if (pci->bdf >= ehcipci->bdf) { + if (!ehcipci || pci->bdf >= ehcipci->bdf) { // Check to see if this device has an ehci controller int found = 0; ehcipci = pci; @@ -445,7 +444,8 @@ usb_setup(void) } if (ehcipci->class == PCI_CLASS_SERIAL_USB) found++; - ehcipci = ehcipci->next; + ehcipci = container_of( + ehcipci->node.next, struct pci_device, node); if (!ehcipci || (pci_bdf_to_busdev(ehcipci->bdf) != pci_bdf_to_busdev(pci->bdf))) // No ehci controller found. -- 1.7.11.7
participants (1)
-
Kevin O'Connor