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