1 /* *********************************************************************
2 * Broadcom Common Firmware Environment (CFE)
4 * Arena Manager File lib_arena.c
6 * This module manages the _arena_, a sorted linked list of
7 * memory regions and attributes. We use this to keep track
8 * of physical memory regions and what is assigned to them.
10 * Author: Mitch Lichtenberg (mpl@broadcom.com)
12 *********************************************************************
14 * Copyright 2000,2001,2002,2003
15 * Broadcom Corporation. All rights reserved.
17 * This software is furnished under license and may be used and
18 * copied only in accordance with the following terms and
19 * conditions. Subject to these conditions, you may download,
20 * copy, install, use, modify and distribute modified or unmodified
21 * copies of this software in source and/or binary form. No title
22 * or ownership is transferred hereby.
24 * 1) Any source code used, modified or distributed must reproduce
25 * and retain this copyright notice and list of conditions
26 * as they appear in the source file.
28 * 2) No right is granted to use any trade name, trademark, or
29 * logo of Broadcom Corporation. The "Broadcom Corporation"
30 * name may not be used to endorse or promote products derived
31 * from this software without the prior written permission of
32 * Broadcom Corporation.
34 * 3) THIS SOFTWARE IS PROVIDED "AS-IS" AND ANY EXPRESS OR
35 * IMPLIED WARRANTIES, INCLUDING BUT NOT LIMITED TO, ANY IMPLIED
36 * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
37 * PURPOSE, OR NON-INFRINGEMENT ARE DISCLAIMED. IN NO EVENT
38 * SHALL BROADCOM BE LIABLE FOR ANY DAMAGES WHATSOEVER, AND IN
39 * PARTICULAR, BROADCOM SHALL NOT BE LIABLE FOR DIRECT, INDIRECT,
40 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
41 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
42 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
43 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
44 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
45 * TORT (INCLUDING NEGLIGENCE OR OTHERWISE), EVEN IF ADVISED OF
46 * THE POSSIBILITY OF SUCH DAMAGE.
47 ********************************************************************* */
49 #include "lib_types.h"
50 #include "lib_queue.h"
51 #include "lib_arena.h"
52 #include "lib_malloc.h"
54 /* *********************************************************************
55 * arena_print(arena,msg)
57 * Debug routine to print out an arena entry
60 * arena - arena descriptor
61 * msg - heading message
65 ********************************************************************* */
68 static void arena_print(arena_t
*arena
,char *msg
)
75 for (qb
= (arena
->arena_list
.q_next
); qb
!= &(arena
->arena_list
);
77 node
= (arena_node_t
*) qb
;
79 printf("Start %5I64d End %5I64d Type %d\n",
81 node
->an_address
+node
->an_length
,
89 /* *********************************************************************
90 * arena_init(arena,physmembase,physmemsize)
92 * Initialize an arena descriptor. The arena is typically
93 * created to describe the entire physical memory address space.
96 * arena - arena descriptor
97 * physmembase - base of region to manage (usually 0)
98 * physmemsize - size of region to manage (typically maxint)
102 ********************************************************************* */
104 void arena_init(arena_t
*arena
,uint64_t physmembase
,uint64_t physmemsize
)
106 arena_node_t
*an
= NULL
;
108 an
= (arena_node_t
*) KMALLOC(sizeof(arena_node_t
),sizeof(uint64_t));
111 arena
->arena_base
= physmembase
;
112 arena
->arena_size
= physmemsize
;
114 an
->an_address
= physmembase
;
115 an
->an_length
= physmemsize
;
119 q_init(&(arena
->arena_list
));
120 q_enqueue(&(arena
->arena_list
),(queue_t
*) an
);
124 /* *********************************************************************
125 * arena_find(arena,pt)
127 * Locate the arena node containing a particular point in the
128 * address space. This routine walks the list and finds the node
129 * whose address range contains the specified point.
132 * arena - arena descriptor
133 * pt - point to look for
136 * arena node pointer, or NULL if no node found
137 ********************************************************************* */
139 static arena_node_t
*arena_find(arena_t
*arena
,uint64_t pt
)
144 for (qb
= (arena
->arena_list
.q_next
); qb
!= &(arena
->arena_list
);
146 an
= (arena_node_t
*) qb
;
148 if ((pt
>= an
->an_address
) &&
149 (pt
< (an
->an_address
+ an
->an_length
))) return an
;
156 /* *********************************************************************
157 * arena_split(arena,splitpoint)
159 * Split the node containing the specified point. When we carve
160 * the arena up, we split the arena at the points on the edges
161 * of the new region, change their types, and then coalesce the
162 * arena. This handles the "split" part of that process.
165 * arena - arena descriptor
166 * splitpoint - address to split arena at
170 * -1 if could not split
171 ********************************************************************* */
173 static int arena_split(arena_t
*arena
,uint64_t splitpoint
)
176 arena_node_t
*newnode
;
179 * Don't need to split if it's the *last* address in the arena
182 if (splitpoint
== (arena
->arena_base
+arena
->arena_size
)) return 0;
185 * Find the block that contains the split point.
188 node
= arena_find(arena
,splitpoint
);
189 if (node
== NULL
) return -1; /* should not happen */
192 * If the address matches exactly, don't need to split
194 if (node
->an_address
== splitpoint
) return 0;
197 * Allocate a new node and adjust the length of the node we're
201 newnode
= (arena_node_t
*) KMALLOC(sizeof(arena_node_t
),sizeof(uint64_t));
203 newnode
->an_length
= node
->an_length
- (splitpoint
- node
->an_address
);
204 node
->an_length
= splitpoint
- node
->an_address
;
205 newnode
->an_address
= splitpoint
;
206 newnode
->an_type
= node
->an_type
;
209 * Put the new node in the arena
212 q_enqueue(node
->an_next
.q_next
,(queue_t
*) newnode
);
217 /* *********************************************************************
218 * arena_coalesce(arena)
220 * Coalesce the arena, merging regions that have the same type
221 * together. After coalescing, no two adjacent nodes will
222 * have the same type.
225 * arena - arena descriptor
229 ********************************************************************* */
231 static void arena_coalesce(arena_t
*arena
)
234 arena_node_t
*nextnode
;
240 for (qb
= (arena
->arena_list
.q_next
); qb
!= &(arena
->arena_list
);
243 node
= (arena_node_t
*) qb
;
244 nextnode
= (arena_node_t
*) node
->an_next
.q_next
;
246 if ((queue_t
*) nextnode
== &(arena
->arena_list
)) break;
248 if (node
->an_type
== nextnode
->an_type
) {
249 node
->an_length
+= nextnode
->an_length
;
250 q_dequeue((queue_t
*) nextnode
);
255 } while (removed
> 0);
259 /* *********************************************************************
260 * arena_markrange(arena,address,length,type,descr)
262 * Mark a region in the arena, changing the types of nodes and
263 * splitting nodes as necessary. This routine is called for
264 * each region we want to add. The order of marking regions is
265 * important, since new marks overwrite old ones. Therefore, you
266 * could mark a whole range as DRAM, and then mark sub-regions
267 * within that as used by firmware.
270 * arena - arena descriptor
271 * address,length - region to mark
272 * type - type code for region
273 * descr - text description of region (optional)
278 ********************************************************************* */
280 int arena_markrange(arena_t
*arena
,uint64_t address
,uint64_t length
,int type
,char *descr
)
286 * Range check the region we want to mark
289 if ((address
< arena
->arena_base
) ||
290 ((address
+length
) > (arena
->arena_base
+ arena
->arena_size
))) {
295 * Force the arena to be split at the two points at the
296 * beginning and end of the range we want. If we have
297 * problems, coalesce the arena again and get out.
300 if (arena_split(arena
,address
) < 0) {
301 /* don't need to coalesce, we didn't split */
304 if (arena_split(arena
,(address
+length
)) < 0) {
305 /* recombine nodes split above */
306 arena_coalesce(arena
);
311 * Assuming we've split the arena at the beginning and ending
312 * split points, we'll never mark any places outside the range
313 * specified in the "Address,length" args.
316 for (qb
= (arena
->arena_list
.q_next
); qb
!= &(arena
->arena_list
);
318 node
= (arena_node_t
*) qb
;
320 if ((node
->an_address
>= address
) &&
321 ((node
->an_address
+ node
->an_length
) <= (address
+length
))) {
322 node
->an_type
= type
;
323 node
->an_descr
= descr
;
328 * Now, coalesce adjacent pieces with the same type back together again
331 arena_coalesce(arena
);
338 /* *********************************************************************
348 ********************************************************************* */
351 void main(int argc
,char *argv
[])
355 arena_init(&arena
,0,1024);
357 arena_markrange(&arena
,100,10,1);
358 arena_markrange(&arena
,120,10,2);
359 arena_markrange(&arena
,140,10,3);
360 arena_print(&arena
,"Before big markrange---------");
362 arena_markrange(&arena
,50,200,4);
363 arena_print(&arena
,"after big markrange---------");