1/*  *********************************************************************
2    *  Broadcom Common Firmware Environment (CFE)
3    *
4    *  Arena Manager				File lib_arena.c
5    *
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.
9    *
10    *  Author:  Mitch Lichtenberg
11    *
12    *********************************************************************
13    *
14    *  Copyright 2000,2001,2002,2003
15    *  Broadcom Corporation. All rights reserved.
16    *
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.
23    *
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.
27    *
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.
33    *
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    ********************************************************************* */
48
49#include "lib_types.h"
50#include "lib_queue.h"
51#include "lib_arena.h"
52#include "lib_malloc.h"
53
54/*  *********************************************************************
55    *  arena_print(arena,msg)
56    *
57    *  Debug routine to print out an arena entry
58    *
59    *  Input parameters:
60    *  	   arena - arena descriptor
61    *  	   msg - heading message
62    *
63    *  Return value:
64    *  	   nothing
65    ********************************************************************* */
66
67#ifdef _TESTPROG_
68static void arena_print(arena_t *arena,char *msg)
69{
70    arena_node_t *node;
71    queue_t *qb;
72
73    printf("%s\n",msg);
74
75    for (qb = (arena->arena_list.q_next); qb != &(arena->arena_list);
76	 qb = qb->q_next) {
77	node = (arena_node_t *) qb;
78
79	printf("Start %5I64d End %5I64d Type %d\n",
80	       node->an_address,
81	       node->an_address+node->an_length,
82	       node->an_type);
83
84	}
85
86}
87#endif
88
89/*  *********************************************************************
90    *  arena_init(arena,physmembase,physmemsize)
91    *
92    *  Initialize an arena descriptor.  The arena is typically
93    *  created to describe the entire physical memory address space.
94    *
95    *  Input parameters:
96    *  	   arena - arena descriptor
97    *  	   physmembase - base of region to manage (usually 0)
98    *  	   physmemsize - size of region to manage (typically maxint)
99    *
100    *  Return value:
101    *  	   nothing
102    ********************************************************************* */
103
104void arena_init(arena_t *arena,uint64_t physmembase,uint64_t physmemsize)
105{
106    arena_node_t *an = NULL;
107
108    an = (arena_node_t *) KMALLOC(sizeof(arena_node_t),sizeof(uint64_t));
109
110    /* XXX check return value */
111
112    arena->arena_base = physmembase;
113    arena->arena_size = physmemsize;
114
115    an->an_address = physmembase;
116    an->an_length = physmemsize;
117    an->an_type = 0;
118    an->an_descr = NULL;
119
120    q_init(&(arena->arena_list));
121    q_enqueue(&(arena->arena_list),(queue_t *) an);
122}
123
124
125/*  *********************************************************************
126    *  arena_find(arena,pt)
127    *
128    *  Locate the arena node containing a particular point in the
129    *  address space.  This routine walks the list and finds the node
130    *  whose address range contains the specified point.
131    *
132    *  Input parameters:
133    *  	   arena - arena descriptor
134    *  	   pt - point to look for
135    *
136    *  Return value:
137    *  	   arena node pointer, or NULL if no node found
138    ********************************************************************* */
139
140static arena_node_t *arena_find(arena_t *arena,uint64_t pt)
141{
142    queue_t *qb;
143    arena_node_t *an;
144
145    for (qb = (arena->arena_list.q_next); qb != &(arena->arena_list);
146	 qb = qb->q_next) {
147	an = (arena_node_t *) qb;
148
149	if ((pt >= an->an_address) &&
150	    (pt < (an->an_address + an->an_length))) return an;
151
152	}
153
154    return NULL;
155}
156
157/*  *********************************************************************
158    *  arena_split(arena,splitpoint)
159    *
160    *  Split the node containing the specified point.  When we carve
161    *  the arena up, we split the arena at the points on the edges
162    *  of the new region, change their types, and then coalesce the
163    *  arena.  This handles the "split" part of that process.
164    *
165    *  Input parameters:
166    *  	   arena - arena descriptor
167    *  	   splitpoint - address to split arena at
168    *
169    *  Return value:
170    *  	   0 if ok
171    *  	   -1 if could not split
172    ********************************************************************* */
173
174static int arena_split(arena_t *arena,uint64_t splitpoint)
175{
176    arena_node_t *node;
177    arena_node_t *newnode;
178
179    /*
180     * Don't need to split if it's the *last* address in the arena
181     */
182
183    if (splitpoint == (arena->arena_base+arena->arena_size)) return 0;
184
185    /*
186     * Find the block that contains the split point.
187     */
188
189    node = arena_find(arena,splitpoint);
190    if (node == NULL) return -1;	/* should not happen */
191
192    /*
193     * If the address matches exactly, don't need to split
194     */
195    if (node->an_address == splitpoint) return 0;
196
197    /*
198     * Allocate a new node and adjust the length of the node we're
199     * splitting.
200     */
201
202    newnode = (arena_node_t *) KMALLOC(sizeof(arena_node_t),sizeof(uint64_t));
203
204    newnode->an_length = node->an_length - (splitpoint - node->an_address);
205    node->an_length = splitpoint - node->an_address;
206    newnode->an_address = splitpoint;
207    newnode->an_type = node->an_type;
208
209    /*
210     * Put the new node in the arena
211     */
212
213    q_enqueue(node->an_next.q_next,(queue_t *) newnode);
214
215    return 0;
216}
217
218/*  *********************************************************************
219    *  arena_coalesce(arena)
220    *
221    *  Coalesce the arena, merging regions that have the same type
222    *  together.  After coalescing, no two adjacent nodes will
223    *  have the same type.
224    *
225    *  Input parameters:
226    *  	   arena - arena descriptor
227    *
228    *  Return value:
229    *      nothing
230    ********************************************************************* */
231
232static void arena_coalesce(arena_t *arena)
233{
234    arena_node_t *node;
235    arena_node_t *nextnode;
236    int removed;
237    queue_t *qb;
238
239    do {
240	removed = 0;
241	for (qb = (arena->arena_list.q_next); qb != &(arena->arena_list);
242	     qb = qb->q_next) {
243
244	    node = (arena_node_t *) qb;
245	    nextnode = (arena_node_t *) node->an_next.q_next;
246
247	    if ((queue_t *) nextnode == &(arena->arena_list)) break;
248
249	    if (node->an_type == nextnode->an_type) {
250		node->an_length += nextnode->an_length;
251		q_dequeue((queue_t *) nextnode);
252		KFREE(nextnode);
253		removed++;
254		}
255	    }
256	} while (removed > 0);
257}
258
259
260/*  *********************************************************************
261    *  arena_markrange(arena,address,length,type,descr)
262    *
263    *  Mark a region in the arena, changing the types of nodes and
264    *  splitting nodes as necessary.  This routine is called for
265    *  each region we want to add.  The order of marking regions is
266    *  important, since new marks overwrite old ones.  Therefore, you
267    *  could mark a whole range as DRAM, and then mark sub-regions
268    *  within that as used by firmware.
269    *
270    *  Input parameters:
271    *  	   arena - arena descriptor
272    *  	   address,length - region to mark
273    *  	   type - type code for region
274    *  	   descr - text description of region (optional)
275    *
276    *  Return value:
277    *  	   0 if ok
278    *  	   -1 if error
279    ********************************************************************* */
280
281int arena_markrange(arena_t *arena,uint64_t address,uint64_t length,int type,char *descr)
282{
283    queue_t *qb;
284    arena_node_t *node;
285
286    /*
287     * Range check the region we want to mark
288     */
289
290    if ((address < arena->arena_base) ||
291	((address+length) > (arena->arena_base + arena->arena_size))) {
292	return -1;
293	}
294
295    /*
296     * Force the arena to be split at the two points at the
297     * beginning and end of the range we want.  If we have
298     * problems, coalesce the arena again and get out.
299     */
300
301    if (arena_split(arena,address) < 0) {
302	/* don't need to coalesce, we didn't split */
303	return -1;
304	}
305    if (arena_split(arena,(address+length)) < 0) {
306	/* recombine nodes split above */
307	arena_coalesce(arena);
308	return -1;
309	}
310
311    /*
312     * Assuming we've split the arena at the beginning and ending
313     * split points, we'll never mark any places outside the range
314     * specified in the "Address,length" args.
315     */
316
317    for (qb = (arena->arena_list.q_next); qb != &(arena->arena_list);
318	 qb = qb->q_next) {
319	node = (arena_node_t *) qb;
320
321	if ((node->an_address >= address) &&
322	    ((node->an_address + node->an_length) <= (address+length))) {
323	    node->an_type = type;
324	    node->an_descr = descr;
325	    }
326	}
327
328    /*
329     * Now, coalesce adjacent pieces with the same type back together again
330     */
331
332    arena_coalesce(arena);
333
334    return 0;
335}
336
337
338
339/*  *********************************************************************
340    *  main(argc,argv)
341    *
342    *  Test program.
343    *
344    *  Input parameters:
345    *  	   argc,argv - guess
346    *
347    *  Return value:
348    *  	   nothing
349    ********************************************************************* */
350
351#ifdef _TESTPROG_
352void main(int argc,char *argv[])
353{
354    arena_t arena;
355
356    arena_init(&arena,0,1024);
357#if 0
358    arena_print(&arena,"empty arena------------");
359
360    arena_split(&arena,5);
361    arena_print(&arena,"split at 5-------------");
362
363    arena_split(&arena,300);
364    arena_print(&arena,"split at 300-----------");
365
366    arena_split(&arena,100);
367    arena_print(&arena,"split at 100-----------");
368
369    arena_coalesce(&arena);
370    arena_print(&arena,"coalesced again--------");
371
372    arena_markrange(&arena,100,50,1);
373    arena_print(&arena,"addrange 100-150-------");
374    arena_markrange(&arena,10,50,1);
375    arena_print(&arena,"addrange 10-60---------");
376    arena_markrange(&arena,1000,24,3);
377    arena_print(&arena,"addrange 1000-1023-----");
378#endif
379
380    arena_markrange(&arena,100,10,1);
381    arena_markrange(&arena,120,10,2);
382    arena_markrange(&arena,140,10,3);
383    arena_print(&arena,"Before big markrange---------");
384
385    arena_markrange(&arena,50,200,4);
386    arena_print(&arena,"after big markrange---------");
387
388}
389#endif
390