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)