[SeaBIOS] [PATCH 2/8] Introduce and convert pmm code to use standard list helpers.
Kevin O'Connor
kevin at koconnor.net
Sun Jun 9 04:22:47 CEST 2013
Signed-off-by: Kevin O'Connor <kevin at 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
More information about the SeaBIOS
mailing list