summaryrefslogtreecommitdiffstats
path: root/cfe/cfe/lib/lib_arena.c
diff options
context:
space:
mode:
Diffstat (limited to 'cfe/cfe/lib/lib_arena.c')
-rw-r--r--cfe/cfe/lib/lib_arena.c389
1 files changed, 389 insertions, 0 deletions
diff --git a/cfe/cfe/lib/lib_arena.c b/cfe/cfe/lib/lib_arena.c
new file mode 100644
index 0000000..41867dc
--- /dev/null
+++ b/cfe/cfe/lib/lib_arena.c
@@ -0,0 +1,389 @@
+/* *********************************************************************
+ * Broadcom Common Firmware Environment (CFE)
+ *
+ * Arena Manager File lib_arena.c
+ *
+ * This module manages the _arena_, a sorted linked list of
+ * memory regions and attributes. We use this to keep track
+ * of physical memory regions and what is assigned to them.
+ *
+ * Author: Mitch Lichtenberg (mpl@broadcom.com)
+ *
+ *********************************************************************
+ *
+ * Copyright 2000,2001,2002,2003
+ * Broadcom Corporation. All rights reserved.
+ *
+ * This software is furnished under license and may be used and
+ * copied only in accordance with the following terms and
+ * conditions. Subject to these conditions, you may download,
+ * copy, install, use, modify and distribute modified or unmodified
+ * copies of this software in source and/or binary form. No title
+ * or ownership is transferred hereby.
+ *
+ * 1) Any source code used, modified or distributed must reproduce
+ * and retain this copyright notice and list of conditions
+ * as they appear in the source file.
+ *
+ * 2) No right is granted to use any trade name, trademark, or
+ * logo of Broadcom Corporation. The "Broadcom Corporation"
+ * name may not be used to endorse or promote products derived
+ * from this software without the prior written permission of
+ * Broadcom Corporation.
+ *
+ * 3) THIS SOFTWARE IS PROVIDED "AS-IS" AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING BUT NOT LIMITED TO, ANY IMPLIED
+ * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
+ * PURPOSE, OR NON-INFRINGEMENT ARE DISCLAIMED. IN NO EVENT
+ * SHALL BROADCOM BE LIABLE FOR ANY DAMAGES WHATSOEVER, AND IN
+ * PARTICULAR, BROADCOM SHALL NOT BE LIABLE FOR DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
+ * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
+ * TORT (INCLUDING NEGLIGENCE OR OTHERWISE), EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ ********************************************************************* */
+
+#include "lib_types.h"
+#include "lib_queue.h"
+#include "lib_arena.h"
+#include "lib_malloc.h"
+
+/* *********************************************************************
+ * arena_print(arena,msg)
+ *
+ * Debug routine to print out an arena entry
+ *
+ * Input parameters:
+ * arena - arena descriptor
+ * msg - heading message
+ *
+ * Return value:
+ * nothing
+ ********************************************************************* */
+
+#ifdef _TESTPROG_
+static void arena_print(arena_t *arena,char *msg)
+{
+ arena_node_t *node;
+ queue_t *qb;
+
+ printf("%s\n",msg);
+
+ for (qb = (arena->arena_list.q_next); qb != &(arena->arena_list);
+ qb = qb->q_next) {
+ node = (arena_node_t *) qb;
+
+ printf("Start %5I64d End %5I64d Type %d\n",
+ node->an_address,
+ node->an_address+node->an_length,
+ node->an_type);
+
+ }
+
+}
+#endif
+
+/* *********************************************************************
+ * arena_init(arena,physmembase,physmemsize)
+ *
+ * Initialize an arena descriptor. The arena is typically
+ * created to describe the entire physical memory address space.
+ *
+ * Input parameters:
+ * arena - arena descriptor
+ * physmembase - base of region to manage (usually 0)
+ * physmemsize - size of region to manage (typically maxint)
+ *
+ * Return value:
+ * nothing
+ ********************************************************************* */
+
+void arena_init(arena_t *arena,uint64_t physmembase,uint64_t physmemsize)
+{
+ arena_node_t *an = NULL;
+
+ an = (arena_node_t *) KMALLOC(sizeof(arena_node_t),sizeof(uint64_t));
+
+ /* XXX check return value */
+
+ arena->arena_base = physmembase;
+ arena->arena_size = physmemsize;
+
+ an->an_address = physmembase;
+ an->an_length = physmemsize;
+ an->an_type = 0;
+ an->an_descr = NULL;
+
+ q_init(&(arena->arena_list));
+ q_enqueue(&(arena->arena_list),(queue_t *) an);
+}
+
+
+/* *********************************************************************
+ * arena_find(arena,pt)
+ *
+ * Locate the arena node containing a particular point in the
+ * address space. This routine walks the list and finds the node
+ * whose address range contains the specified point.
+ *
+ * Input parameters:
+ * arena - arena descriptor
+ * pt - point to look for
+ *
+ * Return value:
+ * arena node pointer, or NULL if no node found
+ ********************************************************************* */
+
+static arena_node_t *arena_find(arena_t *arena,uint64_t pt)
+{
+ queue_t *qb;
+ arena_node_t *an;
+
+ for (qb = (arena->arena_list.q_next); qb != &(arena->arena_list);
+ qb = qb->q_next) {
+ an = (arena_node_t *) qb;
+
+ if ((pt >= an->an_address) &&
+ (pt < (an->an_address + an->an_length))) return an;
+
+ }
+
+ return NULL;
+}
+
+/* *********************************************************************
+ * arena_split(arena,splitpoint)
+ *
+ * Split the node containing the specified point. When we carve
+ * the arena up, we split the arena at the points on the edges
+ * of the new region, change their types, and then coalesce the
+ * arena. This handles the "split" part of that process.
+ *
+ * Input parameters:
+ * arena - arena descriptor
+ * splitpoint - address to split arena at
+ *
+ * Return value:
+ * 0 if ok
+ * -1 if could not split
+ ********************************************************************* */
+
+static int arena_split(arena_t *arena,uint64_t splitpoint)
+{
+ arena_node_t *node;
+ arena_node_t *newnode;
+
+ /*
+ * Don't need to split if it's the *last* address in the arena
+ */
+
+ if (splitpoint == (arena->arena_base+arena->arena_size)) return 0;
+
+ /*
+ * Find the block that contains the split point.
+ */
+
+ node = arena_find(arena,splitpoint);
+ if (node == NULL) return -1; /* should not happen */
+
+ /*
+ * If the address matches exactly, don't need to split
+ */
+ if (node->an_address == splitpoint) return 0;
+
+ /*
+ * Allocate a new node and adjust the length of the node we're
+ * splitting.
+ */
+
+ newnode = (arena_node_t *) KMALLOC(sizeof(arena_node_t),sizeof(uint64_t));
+
+ newnode->an_length = node->an_length - (splitpoint - node->an_address);
+ node->an_length = splitpoint - node->an_address;
+ newnode->an_address = splitpoint;
+ newnode->an_type = node->an_type;
+
+ /*
+ * Put the new node in the arena
+ */
+
+ q_enqueue(node->an_next.q_next,(queue_t *) newnode);
+
+ return 0;
+}
+
+/* *********************************************************************
+ * arena_coalesce(arena)
+ *
+ * Coalesce the arena, merging regions that have the same type
+ * together. After coalescing, no two adjacent nodes will
+ * have the same type.
+ *
+ * Input parameters:
+ * arena - arena descriptor
+ *
+ * Return value:
+ * nothing
+ ********************************************************************* */
+
+static void arena_coalesce(arena_t *arena)
+{
+ arena_node_t *node;
+ arena_node_t *nextnode;
+ int removed;
+ queue_t *qb;
+
+ do {
+ removed = 0;
+ for (qb = (arena->arena_list.q_next); qb != &(arena->arena_list);
+ qb = qb->q_next) {
+
+ node = (arena_node_t *) qb;
+ nextnode = (arena_node_t *) node->an_next.q_next;
+
+ if ((queue_t *) nextnode == &(arena->arena_list)) break;
+
+ if (node->an_type == nextnode->an_type) {
+ node->an_length += nextnode->an_length;
+ q_dequeue((queue_t *) nextnode);
+ KFREE(nextnode);
+ removed++;
+ }
+ }
+ } while (removed > 0);
+}
+
+
+/* *********************************************************************
+ * arena_markrange(arena,address,length,type,descr)
+ *
+ * Mark a region in the arena, changing the types of nodes and
+ * splitting nodes as necessary. This routine is called for
+ * each region we want to add. The order of marking regions is
+ * important, since new marks overwrite old ones. Therefore, you
+ * could mark a whole range as DRAM, and then mark sub-regions
+ * within that as used by firmware.
+ *
+ * Input parameters:
+ * arena - arena descriptor
+ * address,length - region to mark
+ * type - type code for region
+ * descr - text description of region (optional)
+ *
+ * Return value:
+ * 0 if ok
+ * -1 if error
+ ********************************************************************* */
+
+int arena_markrange(arena_t *arena,uint64_t address,uint64_t length,int type,char *descr)
+{
+ queue_t *qb;
+ arena_node_t *node;
+
+ /*
+ * Range check the region we want to mark
+ */
+
+ if ((address < arena->arena_base) ||
+ ((address+length) > (arena->arena_base + arena->arena_size))) {
+ return -1;
+ }
+
+ /*
+ * Force the arena to be split at the two points at the
+ * beginning and end of the range we want. If we have
+ * problems, coalesce the arena again and get out.
+ */
+
+ if (arena_split(arena,address) < 0) {
+ /* don't need to coalesce, we didn't split */
+ return -1;
+ }
+ if (arena_split(arena,(address+length)) < 0) {
+ /* recombine nodes split above */
+ arena_coalesce(arena);
+ return -1;
+ }
+
+ /*
+ * Assuming we've split the arena at the beginning and ending
+ * split points, we'll never mark any places outside the range
+ * specified in the "Address,length" args.
+ */
+
+ for (qb = (arena->arena_list.q_next); qb != &(arena->arena_list);
+ qb = qb->q_next) {
+ node = (arena_node_t *) qb;
+
+ if ((node->an_address >= address) &&
+ ((node->an_address + node->an_length) <= (address+length))) {
+ node->an_type = type;
+ node->an_descr = descr;
+ }
+ }
+
+ /*
+ * Now, coalesce adjacent pieces with the same type back together again
+ */
+
+ arena_coalesce(arena);
+
+ return 0;
+}
+
+
+
+/* *********************************************************************
+ * main(argc,argv)
+ *
+ * Test program.
+ *
+ * Input parameters:
+ * argc,argv - guess
+ *
+ * Return value:
+ * nothing
+ ********************************************************************* */
+
+#ifdef _TESTPROG_
+void main(int argc,char *argv[])
+{
+ arena_t arena;
+
+ arena_init(&arena,0,1024);
+#if 0
+ arena_print(&arena,"empty arena------------");
+
+ arena_split(&arena,5);
+ arena_print(&arena,"split at 5-------------");
+
+ arena_split(&arena,300);
+ arena_print(&arena,"split at 300-----------");
+
+ arena_split(&arena,100);
+ arena_print(&arena,"split at 100-----------");
+
+ arena_coalesce(&arena);
+ arena_print(&arena,"coalesced again--------");
+
+ arena_markrange(&arena,100,50,1);
+ arena_print(&arena,"addrange 100-150-------");
+ arena_markrange(&arena,10,50,1);
+ arena_print(&arena,"addrange 10-60---------");
+ arena_markrange(&arena,1000,24,3);
+ arena_print(&arena,"addrange 1000-1023-----");
+#endif
+
+ arena_markrange(&arena,100,10,1);
+ arena_markrange(&arena,120,10,2);
+ arena_markrange(&arena,140,10,3);
+ arena_print(&arena,"Before big markrange---------");
+
+ arena_markrange(&arena,50,200,4);
+ arena_print(&arena,"after big markrange---------");
+
+}
+#endif
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-17 05:17:24 +0000