Changeset 961c0484 in mainline

Timestamp:

2011-12-04T22:33:03Z (13 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

b4e59b3

Parents:

375fc3f

Message:

WIP: Implement ra_alloc().

Location:

kernel/generic

Files:

• include/lib/ra.h (modified) (2 diffs)
• src/lib/ra.c (modified) (8 diffs)

kernel/generic/include/lib/ra.h

@@ -45 +45 @@
 
 typedef struct {
-        link_t span_link;       /**< Link for the arena's list of spans. */
+        link_t span_link;       /**< Arena's list of spans link. */
 
         list_t segments;        /**< List of span's segments. */
@@ -53 +53 @@
 
         hash_table_t used;
+
+        uintptr_t base;         /**< Span base. */
+        size_t size;            /**< Span size. */
 } ra_span_t;
 
+/*
+ * We would like to achieve a good ratio of the size of one unit of the
+ * represented resource (e.g. a page) and sizeof(ra_segment_t).  We therefore
+ * attempt to have as few redundant information in the segment as possible. For
+ * example, the size of the segment needs to be calculated from the segment
+ * base and the base of the following segment.
+ */
 typedef struct {
-        link_t segment_link;    /**< Link for the span's list of segments. */
-        link_t free_link;       /**< Link for the span's free list. */
-        link_t used_link;       /**< Link for the span's used hash table. */
+        link_t segment_link;    /**< Span's segment list link. */
+        link_t fu_link;         /**< Span's free list or used hash link. */
 
         uintptr_t base;         /**< Segment base. */
-        uintptr_t size;         /**< Segment size. */
-        
 } ra_segment_t;
 
 extern ra_arena_t *ra_arena_create(uintptr_t, size_t);
-extern void ra_span_add(ra_arena_t *, uintptr_t, size_t);
+extern bool ra_span_add(ra_arena_t *, uintptr_t, size_t);
 extern uintptr_t ra_alloc(ra_arena_t *, size_t, size_t);
 extern void ra_free(ra_arena_t *, uintptr_t, size_t);

kernel/generic/src/lib/ra.c

@@ -48 +48 @@
 #include <bitops.h>
 #include <debug.h>
+#include <panic.h>
+#include <adt/list.h>
+#include <adt/hash_table.h>
+#include <align.h>
+#include <macros.h>
+
+/*
+ * The last segment on the segment list will be a special sentinel segment which
+ * is neither in any free list nor in the used segment hash.
+ */
+#define IS_LAST_SEG(seg)        (!(seg)->fu_link.next)
 
 static hash_table_operations_t used_ops = {
@@ -55 +66 @@
 };
 
-static ra_segment_t *ra_segment_create(uintptr_t base, size_t size)
+/** Calculate the segment size. */
+static size_t ra_segment_size_get(ra_segment_t *seg)
+{
+        ra_segment_t *nextseg;
+
+        ASSERT(!IS_LAST_SEG(seg));
+
+        nextseg = list_get_instance(seg->segment_link.next, ra_segment_t,
+            segment_link);
+        return nextseg->base - seg->base;
+}
+
+static ra_segment_t *ra_segment_create(uintptr_t base)
 {
         ra_segment_t *seg;
@@ -64 +87 @@
 
         link_initialize(&seg->segment_link);
-        link_initialize(&seg->free_link);
-        link_initialize(&seg->used_link);
+        link_initialize(&seg->fu_link);
 
         seg->base = base;
-        seg->size = size;
 
         return seg;
 }
 
-/*
 static void ra_segment_destroy(ra_segment_t *seg)
 {
         free(seg);
 }
-*/
 
 static ra_span_t *ra_span_create(uintptr_t base, size_t size)
 {
         ra_span_t *span;
-        ra_segment_t *seg;
+        ra_segment_t *seg, *lastseg;
         unsigned int i;
 
@@ -91 +110 @@
 
         span->max_order = fnzb(size);
+        span->base = base;
+        span->size = size;
 
         span->free = (list_t *) malloc((span->max_order + 1) * sizeof(list_t),
@@ -98 +119 @@
                 return NULL;
         }
-        seg = ra_segment_create(base, size);
+
+        /*
+         * Create a segment to represent the entire size of the span.
+         */
+        seg = ra_segment_create(base);
         if (!seg) {
                 free(span->free);
@@ -105 +130 @@
         }
 
+        /*
+         * The last segment will be used as a sentinel at the end of the
+         * segment list so that it is possible to calculate the size for
+         * all other segments. It will not be placed in any free list or
+         * in the used segment hash and adjacent segments will not be
+         * coalesced with it.
+         */
+        lastseg = ra_segment_create(base + size);
+        if (!lastseg) {
+                ra_segment_destroy(seg);
+                free(span->free);
+                free(span);
+                return NULL;
+        }
+        /* Make sure we have NULL here so that we can recognize the sentinel. */
+        lastseg->fu_link.next = NULL;
+
         link_initialize(&span->span_link);
         list_initialize(&span->segments);
@@ -113 +155 @@
                 list_initialize(&span->free[i]);
 
+        /* Insert the first segment into the list of segments. */
         list_append(&seg->segment_link, &span->segments);
-        list_append(&seg->free_link, &span->free[span->max_order]);
+        /* Insert the last segment into the list of segments. */
+        list_append(&lastseg->segment_link, &span->segments);
+
+        /* Insert the first segment into the respective free list. */
+        list_append(&seg->fu_link, &span->free[span->max_order]);
 
         return span;
 }
 
+/** Create arena with initial span. */
 ra_arena_t *ra_arena_create(uintptr_t base, size_t size)
 {
         ra_arena_t *arena;
         ra_span_t *span;
+
+        /*
+         * At the moment, we can only create resources that don't include 0.
+         * If 0 needs to be considered as a valid resource, we would need to
+         * slightly change the API of the resource allocator.
+         */
+        if (base == 0)
+                return NULL;
 
         arena = (ra_arena_t *) malloc(sizeof(ra_arena_t), FRAME_ATOMIC);
@@ -140 +196 @@
 }
 
-void ra_span_add(ra_arena_t *arena, uintptr_t base, size_t size)
+/** Add additional span to arena. */
+bool ra_span_add(ra_arena_t *arena, uintptr_t base, size_t size)
 {
         ra_span_t *span;
 
+        if (base == 0)
+                return false;
+
         span = ra_span_create(base, size);
-        ASSERT(span);
+        if (!span)
+                return false;
 
         /* TODO: check for overlaps */
         list_append(&span->span_link, &arena->spans);
-}
-
+        return true;
+}
+
+static uintptr_t ra_span_alloc(ra_span_t *span, size_t size, size_t align)
+{
+        /*
+         * We need to add the maximum of align - 1 to be able to compensate for
+         * the worst case unaligned segment.
+         */
+        size_t needed = size + align - 1;
+        size_t order = ispwr2(needed) ? fnzb(needed) : fnzb(needed) + 1;
+        ra_segment_t *pred = NULL;
+        ra_segment_t *succ = NULL;
+
+        /*
+         * Find the free list of the smallest order which can satisfy this
+         * request.
+         */
+        for (; order <= span->max_order; order++) {
+                ra_segment_t *seg;
+                uintptr_t newbase;
+
+                if (list_empty(&span->free[order]))
+                        continue;
+
+                /* Take the first segment from the free list. */
+                seg = list_get_instance(list_first(&span->free[order]),
+                    ra_segment_t, fu_link);
+
+                /*
+                 * See if we need to allocate new segments for the chopped-off
+                 * parts of this segment.
+                 */
+                if (!IS_ALIGNED(seg->base, align)) {
+                        pred = ra_segment_create(seg->base);
+                        if (!pred) {
+                                /*
+                                 * Fail as we are unable to split the segment.
+                                 */
+                                break;
+                        }
+                }
+                newbase = ALIGN_UP(seg->base, align);
+                if (newbase + size != seg->base + ra_segment_size_get(seg)) {
+                        ASSERT(newbase + size < seg->base +
+                            ra_segment_size_get(seg));
+                        succ = ra_segment_create(newbase + size);
+                        if (!succ) {
+                                if (pred)
+                                        ra_segment_destroy(pred);
+                                /*
+                                 * Fail as we are unable to split the segment.
+                                 */
+                                break;
+                        }
+                }
+                
+        
+                /* Put unneeded parts back. */
+                if (pred) {
+                        size_t pred_order;
+
+                        list_insert_before(&pred->segment_link,
+                            &seg->segment_link);
+                        pred_order = fnzb(ra_segment_size_get(pred));
+                        list_append(&pred->fu_link, &span->free[pred_order]);
+                }
+                if (succ) {
+                        size_t succ_order;
+
+                        list_insert_after(&succ->segment_link,
+                            &seg->segment_link);
+                        succ_order = fnzb(ra_segment_size_get(succ));
+                        list_append(&succ->fu_link, &span->free[succ_order]);
+                }
+
+                /* Now remove the found segment from the free list. */
+                list_remove(&seg->fu_link);
+                seg->base = newbase;
+
+                /* Hash-in the segment into the used hash. */
+                sysarg_t key = seg->base;
+                hash_table_insert(&span->used, &key, &seg->fu_link);
+
+                return newbase;
+        }
+
+        return 0;
+}
+
+static void ra_span_free(ra_span_t *span, size_t base, size_t size)
+{
+}
+
+/** Allocate resources from arena. */
 uintptr_t ra_alloc(ra_arena_t *arena, size_t size, size_t alignment)
 {
-        return 0;
-}
-
+        uintptr_t base = 0;
+
+        ASSERT(size >= 1);
+        ASSERT(alignment >= 1);
+        ASSERT(ispwr2(alignment));
+
+        list_foreach(arena->spans, cur) {
+                ra_span_t *span = list_get_instance(cur, ra_span_t, span_link);
+
+                base = ra_span_alloc(span, size, alignment);
+                if (base)
+                        break;
+        }
+
+        return base;
+}
+
+/* Return resources to arena. */
 void ra_free(ra_arena_t *arena, uintptr_t base, size_t size)
 {
+        list_foreach(arena->spans, cur) {
+                ra_span_t *span = list_get_instance(cur, ra_span_t, span_link);
+
+                if (iswithin(span->base, span->size, base, size)) {
+                        ra_span_free(span, base, size);
+                        return;
+                }
+        }
+
+        panic("Freeing to wrong arena (base=%" PRIxn ", size=%" PRIdn ").",
+            base, size);
 }