1/* 2 * rmm.c 3 * 4 * DSP-BIOS Bridge driver support functions for TI OMAP processors. 5 * 6 * Copyright (C) 2005-2006 Texas Instruments, Inc. 7 * 8 * This package is free software; you can redistribute it and/or modify 9 * it under the terms of the GNU General Public License version 2 as 10 * published by the Free Software Foundation. 11 * 12 * THIS PACKAGE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 13 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 14 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. 15 */ 16 17/* 18 * This memory manager provides general heap management and arbitrary 19 * alignment for any number of memory segments. 20 * 21 * Notes: 22 * 23 * Memory blocks are allocated from the end of the first free memory 24 * block large enough to satisfy the request. Alignment requirements 25 * are satisfied by "sliding" the block forward until its base satisfies 26 * the alignment specification; if this is not possible then the next 27 * free block large enough to hold the request is tried. 28 * 29 * Since alignment can cause the creation of a new free block - the 30 * unused memory formed between the start of the original free block 31 * and the start of the allocated block - the memory manager must free 32 * this memory to prevent a memory leak. 33 * 34 * Overlay memory is managed by reserving through rmm_alloc, and freeing 35 * it through rmm_free. The memory manager prevents DSP code/data that is 36 * overlayed from being overwritten as long as the memory it runs at has 37 * been allocated, and not yet freed. 38 */ 39 40#include <linux/types.h> 41#include <linux/list.h> 42 43/* ----------------------------------- Host OS */ 44#include <dspbridge/host_os.h> 45 46/* ----------------------------------- DSP/BIOS Bridge */ 47#include <dspbridge/dbdefs.h> 48 49/* ----------------------------------- This */ 50#include <dspbridge/rmm.h> 51 52/* 53 * ======== rmm_header ======== 54 * This header is used to maintain a list of free memory blocks. 55 */ 56struct rmm_header { 57 struct rmm_header *next; /* form a free memory link list */ 58 u32 size; /* size of the free memory */ 59 u32 addr; /* DSP address of memory block */ 60}; 61 62/* 63 * ======== rmm_ovly_sect ======== 64 * Keeps track of memory occupied by overlay section. 65 */ 66struct rmm_ovly_sect { 67 struct list_head list_elem; 68 u32 addr; /* Start of memory section */ 69 u32 size; /* Length (target MAUs) of section */ 70 s32 page; /* Memory page */ 71}; 72 73/* 74 * ======== rmm_target_obj ======== 75 */ 76struct rmm_target_obj { 77 struct rmm_segment *seg_tab; 78 struct rmm_header **free_list; 79 u32 num_segs; 80 struct list_head ovly_list; /* List of overlay memory in use */ 81}; 82 83static bool alloc_block(struct rmm_target_obj *target, u32 segid, u32 size, 84 u32 align, u32 *dsp_address); 85static bool free_block(struct rmm_target_obj *target, u32 segid, u32 addr, 86 u32 size); 87 88/* 89 * ======== rmm_alloc ======== 90 */ 91int rmm_alloc(struct rmm_target_obj *target, u32 segid, u32 size, 92 u32 align, u32 *dsp_address, bool reserve) 93{ 94 struct rmm_ovly_sect *sect, *prev_sect = NULL; 95 struct rmm_ovly_sect *new_sect; 96 u32 addr; 97 int status = 0; 98 99 if (!reserve) { 100 if (!alloc_block(target, segid, size, align, dsp_address)) { 101 status = -ENOMEM; 102 } else { 103 /* Increment the number of allocated blocks in this 104 * segment */ 105 target->seg_tab[segid].number++; 106 } 107 goto func_end; 108 } 109 /* An overlay section - See if block is already in use. If not, 110 * insert into the list in ascending address size. */ 111 addr = *dsp_address; 112 /* Find place to insert new list element. List is sorted from 113 * smallest to largest address. */ 114 list_for_each_entry(sect, &target->ovly_list, list_elem) { 115 if (addr <= sect->addr) { 116 /* Check for overlap with sect */ 117 if ((addr + size > sect->addr) || (prev_sect && 118 (prev_sect->addr + 119 prev_sect->size > 120 addr))) { 121 status = -ENXIO; 122 } 123 break; 124 } 125 prev_sect = sect; 126 } 127 if (!status) { 128 /* No overlap - allocate list element for new section. */ 129 new_sect = kzalloc(sizeof(struct rmm_ovly_sect), GFP_KERNEL); 130 if (new_sect == NULL) { 131 status = -ENOMEM; 132 } else { 133 new_sect->addr = addr; 134 new_sect->size = size; 135 new_sect->page = segid; 136 if (list_is_last(§->list_elem, &target->ovly_list)) 137 /* Put new section at the end of the list */ 138 list_add_tail(&new_sect->list_elem, 139 &target->ovly_list); 140 else 141 /* Put new section just before sect */ 142 list_add_tail(&new_sect->list_elem, 143 §->list_elem); 144 } 145 } 146func_end: 147 return status; 148} 149 150/* 151 * ======== rmm_create ======== 152 */ 153int rmm_create(struct rmm_target_obj **target_obj, 154 struct rmm_segment seg_tab[], u32 num_segs) 155{ 156 struct rmm_header *hptr; 157 struct rmm_segment *sptr, *tmp; 158 struct rmm_target_obj *target; 159 s32 i; 160 int status = 0; 161 162 /* Allocate DBL target object */ 163 target = kzalloc(sizeof(struct rmm_target_obj), GFP_KERNEL); 164 165 if (target == NULL) 166 status = -ENOMEM; 167 168 if (status) 169 goto func_cont; 170 171 target->num_segs = num_segs; 172 if (!(num_segs > 0)) 173 goto func_cont; 174 175 /* Allocate the memory for freelist from host's memory */ 176 target->free_list = kzalloc(num_segs * sizeof(struct rmm_header *), 177 GFP_KERNEL); 178 if (target->free_list == NULL) { 179 status = -ENOMEM; 180 } else { 181 /* Allocate headers for each element on the free list */ 182 for (i = 0; i < (s32) num_segs; i++) { 183 target->free_list[i] = 184 kzalloc(sizeof(struct rmm_header), GFP_KERNEL); 185 if (target->free_list[i] == NULL) { 186 status = -ENOMEM; 187 break; 188 } 189 } 190 /* Allocate memory for initial segment table */ 191 target->seg_tab = kzalloc(num_segs * sizeof(struct rmm_segment), 192 GFP_KERNEL); 193 if (target->seg_tab == NULL) { 194 status = -ENOMEM; 195 } else { 196 /* Initialize segment table and free list */ 197 sptr = target->seg_tab; 198 for (i = 0, tmp = seg_tab; num_segs > 0; 199 num_segs--, i++) { 200 *sptr = *tmp; 201 hptr = target->free_list[i]; 202 hptr->addr = tmp->base; 203 hptr->size = tmp->length; 204 hptr->next = NULL; 205 tmp++; 206 sptr++; 207 } 208 } 209 } 210func_cont: 211 /* Initialize overlay memory list */ 212 if (!status) 213 INIT_LIST_HEAD(&target->ovly_list); 214 215 if (!status) { 216 *target_obj = target; 217 } else { 218 *target_obj = NULL; 219 if (target) 220 rmm_delete(target); 221 222 } 223 224 return status; 225} 226 227/* 228 * ======== rmm_delete ======== 229 */ 230void rmm_delete(struct rmm_target_obj *target) 231{ 232 struct rmm_ovly_sect *sect, *tmp; 233 struct rmm_header *hptr; 234 struct rmm_header *next; 235 u32 i; 236 237 kfree(target->seg_tab); 238 239 list_for_each_entry_safe(sect, tmp, &target->ovly_list, list_elem) { 240 list_del(§->list_elem); 241 kfree(sect); 242 } 243 244 if (target->free_list != NULL) { 245 /* Free elements on freelist */ 246 for (i = 0; i < target->num_segs; i++) { 247 hptr = next = target->free_list[i]; 248 while (next) { 249 hptr = next; 250 next = hptr->next; 251 kfree(hptr); 252 } 253 } 254 kfree(target->free_list); 255 } 256 257 kfree(target); 258} 259 260/* 261 * ======== rmm_free ======== 262 */ 263bool rmm_free(struct rmm_target_obj *target, u32 segid, u32 dsp_addr, u32 size, 264 bool reserved) 265{ 266 struct rmm_ovly_sect *sect, *tmp; 267 bool ret = false; 268 269 /* 270 * Free or unreserve memory. 271 */ 272 if (!reserved) { 273 ret = free_block(target, segid, dsp_addr, size); 274 if (ret) 275 target->seg_tab[segid].number--; 276 277 } else { 278 /* Unreserve memory */ 279 list_for_each_entry_safe(sect, tmp, &target->ovly_list, 280 list_elem) { 281 if (dsp_addr == sect->addr) { 282 /* Remove from list */ 283 list_del(§->list_elem); 284 kfree(sect); 285 return true; 286 } 287 } 288 } 289 return ret; 290} 291 292/* 293 * ======== rmm_stat ======== 294 */ 295bool rmm_stat(struct rmm_target_obj *target, enum dsp_memtype segid, 296 struct dsp_memstat *mem_stat_buf) 297{ 298 struct rmm_header *head; 299 bool ret = false; 300 u32 max_free_size = 0; 301 u32 total_free_size = 0; 302 u32 free_blocks = 0; 303 304 if ((u32) segid < target->num_segs) { 305 head = target->free_list[segid]; 306 307 /* Collect data from free_list */ 308 while (head != NULL) { 309 max_free_size = max(max_free_size, head->size); 310 total_free_size += head->size; 311 free_blocks++; 312 head = head->next; 313 } 314 315 /* ul_size */ 316 mem_stat_buf->size = target->seg_tab[segid].length; 317 318 /* num_free_blocks */ 319 mem_stat_buf->num_free_blocks = free_blocks; 320 321 /* total_free_size */ 322 mem_stat_buf->total_free_size = total_free_size; 323 324 /* len_max_free_block */ 325 mem_stat_buf->len_max_free_block = max_free_size; 326 327 /* num_alloc_blocks */ 328 mem_stat_buf->num_alloc_blocks = 329 target->seg_tab[segid].number; 330 331 ret = true; 332 } 333 334 return ret; 335} 336 337/* 338 * ======== balloc ======== 339 * This allocation function allocates memory from the lowest addresses 340 * first. 341 */ 342static bool alloc_block(struct rmm_target_obj *target, u32 segid, u32 size, 343 u32 align, u32 *dsp_address) 344{ 345 struct rmm_header *head; 346 struct rmm_header *prevhead = NULL; 347 struct rmm_header *next; 348 u32 tmpalign; 349 u32 alignbytes; 350 u32 hsize; 351 u32 allocsize; 352 u32 addr; 353 354 alignbytes = (align == 0) ? 1 : align; 355 prevhead = NULL; 356 head = target->free_list[segid]; 357 358 do { 359 hsize = head->size; 360 next = head->next; 361 362 addr = head->addr; /* alloc from the bottom */ 363 364 /* align allocation */ 365 (tmpalign = (u32) addr % alignbytes); 366 if (tmpalign != 0) 367 tmpalign = alignbytes - tmpalign; 368 369 allocsize = size + tmpalign; 370 371 if (hsize >= allocsize) { /* big enough */ 372 if (hsize == allocsize && prevhead != NULL) { 373 prevhead->next = next; 374 kfree(head); 375 } else { 376 head->size = hsize - allocsize; 377 head->addr += allocsize; 378 } 379 380 /* free up any hole created by alignment */ 381 if (tmpalign) 382 free_block(target, segid, addr, tmpalign); 383 384 *dsp_address = addr + tmpalign; 385 return true; 386 } 387 388 prevhead = head; 389 head = next; 390 391 } while (head != NULL); 392 393 return false; 394} 395 396/* 397 * ======== free_block ======== 398 * TO DO: free_block() allocates memory, which could result in failure. 399 * Could allocate an rmm_header in rmm_alloc(), to be kept in a pool. 400 * free_block() could use an rmm_header from the pool, freeing as blocks 401 * are coalesced. 402 */ 403static bool free_block(struct rmm_target_obj *target, u32 segid, u32 addr, 404 u32 size) 405{ 406 struct rmm_header *head; 407 struct rmm_header *thead; 408 struct rmm_header *rhead; 409 bool ret = true; 410 411 /* Create a memory header to hold the newly free'd block. */ 412 rhead = kzalloc(sizeof(struct rmm_header), GFP_KERNEL); 413 if (rhead == NULL) { 414 ret = false; 415 } else { 416 /* search down the free list to find the right place for addr */ 417 head = target->free_list[segid]; 418 419 if (addr >= head->addr) { 420 while (head->next != NULL && addr > head->next->addr) 421 head = head->next; 422 423 thead = head->next; 424 425 head->next = rhead; 426 rhead->next = thead; 427 rhead->addr = addr; 428 rhead->size = size; 429 } else { 430 *rhead = *head; 431 head->next = rhead; 432 head->addr = addr; 433 head->size = size; 434 thead = rhead->next; 435 } 436 437 /* join with upper block, if possible */ 438 if (thead != NULL && (rhead->addr + rhead->size) == 439 thead->addr) { 440 head->next = rhead->next; 441 thead->size = size + thead->size; 442 thead->addr = addr; 443 kfree(rhead); 444 rhead = thead; 445 } 446 447 /* join with the lower block, if possible */ 448 if ((head->addr + head->size) == rhead->addr) { 449 head->next = rhead->next; 450 head->size = head->size + rhead->size; 451 kfree(rhead); 452 } 453 } 454 455 return ret; 456} 457