STM CircleOS forum / SimpMalloc

ShadowPhoenix · 2009-07-28 01:23:38

Here's a very simple malloc implementation. Fits in a couple hundreed bytes of flash.

Here are pluses and minuses.

Plus:
•Very small flash usage.
•Easy to integrate into project/CircleOS
•Easy to follow up with adding permission pages and segmenting memory to differend processes.
•Very fast free implementation: O(1). One comparison, one division, one assigment.
•O(n) malloc, where n are half fragmented single pages. Maximum wait time is 42 microseconds in the worst case scenario (request for 2 pages, having one page all written before it. Theoretical calculations, which exclude any pipelining.). Expected time depends primarily on memory usage.
•Big pages are treated as one big page instead of many small ones thus we are able to jump around it when looking for pages.

Minus:
•Only returns multiples of 128 and above. Thus if you want to malloc 2x64 then you should do...

Code:

char* page = malloc(128);
char* page2 = page+64; //voila!

•Consumes 2% of RAM (2 bytes/bucket * 100% / Bucket_size) = 200 / 128 = 1.6%, but this is higher due to linker having to align this to powers of two boundary.

Now, I started working on splitting up pages and requests to map specific memory, with a tree implementation. However, there's quite a few things that would be nice to change with the CircleOS. It's not a good OS. As of now it supports neither preemptive nor cooperative multitasking without jumping through hoops. Why can't we just implement the systick to have threads it can call and have the threads have other resolutions other than MENU_leave, and continue?

Code:

/************************* ***************************** **********************
* File Name          :  memory.h
* Author             :  ShadowPhoenix
* Date First Issued  :  July 21, 2009
* Description        :  Simple malloc implementation.
* Revision           :  0.5
*******************************************************************************/

/*
  Memory map. - Primer2. 
  0x2000000  <-- beggining of memory
  0x200BB80  <-- End of managed memory - 48.00 kb. Beggining of stack.
  0x200D400  <-- End of stack (?kb), beggining of CircleOS Ram
  0x200FFFF  <-- End of memory.

*/
//RAM_BASE                // 0x2000000
//CIRCLEOS_RAM_BASE       // 2: 2000BFFF, 1: 20003FFFF


#ifndef __MEMORY_H
#define __MEMORY_H


#define MANAGED_RAM  0x0000BB80  

/*
The following is untested, but should work. Fiddle with the number. 

#ifdef PRIMER1 
#define MANAGED_RAM 0x000036B0 
#endif 

*/

const unsigned char pool[MANAGED_RAM]; //So that no one else touches our RAM.
const void* floor_managed = &pool;     //the beggining address of our managed RAM.

#define SIZE_OF_POT 128               //tradeof of memory vs allocated.
#define NUMBER_OF_POTS (MANAGED_RAM/SIZE_OF_POT) 

static unsigned short pot[NUMBER_OF_POTS]; //375? Might be aliased to 512.


#define size_t unsigned long //Because it isn't defined anywhere.

//Functions 
void *malloc(size_t size);
void free(void* ptr);

#endif /*__MEMORY_H */

Code:

#include "simpmemory.h" 
 
 
void* malloc(size_t size) 
{ 
if(size==0)  
    return (void*)0x0;  
     
register unsigned int number_of_pots_requested = size/SIZE_OF_POT; 
 
if(size % SIZE_OF_POT != 0) //requested not even size of pot 
        number_of_pots_requested++;  
 
register unsigned int number_of_pots_found=0; 
register unsigned int memory_slot=0; 
 
for(;memory_slot<NUMBER_OF_POTS;memory_slot++) 
   { 
       if(pot[memory_slot]==0) 
           number_of_pots_found++; 
       else /*We found a spot taken, Jump over it.*/ 
           { 
             number_of_pots_found=0; 
             memory_slot+= pot[memory_slot]-1; //skip over taken spots 
           } 
        
       if(number_of_pots_found==number_of_pots_requested) 
       { 
        pot[memory_slot-number_of_pots_found+1]=number_of_pots_requested; 
        return (void*)(floor_managed+(memory_slot-number_of_pots_found+1)*SIZE_OF_POT); 
       } 
                       
   } 
 
      return 0x0; 
} 
 
 
void free(void* ptr) 
{ 
    if(ptr==0x0)  
        return; //free to free per malloc spec. 
     
    register unsigned int slot = (int)(ptr-floor_managed)/SIZE_OF_POT; 
    pot[slot]=0; 
}

ShadowPhoenix · 2009-07-29 15:13:28

Any response on this? I am also thinking about making some changes to the scheduler file to be able to preemptively multitask, but I am not sure if it will be used...

Francis · 2009-08-03 07:16:56

CircleOS is not a preemptive RTOS. It's more something like a BIOS, providing low level functions to handle the hardware peripherals (LCD, MEMS, SDcard...).
Yes, we could think about improving CircleOS (and we think about that possibility). One could be to find a partnership with a RTOS provider. Another would be to add, step by step, some missing features to the existing CircleOS.

ShadowPhoenix · 2009-08-03 15:47:59

It isn't that hard to do as of now .
I've spent a couple hours with the freeRtos code and then microC/OS-II. The latter even has the ported source code needed!

# 1 2009-07-28 01:23:38 SimpMalloc

SimpMalloc

Code:

Code:

Code:

# 2 2009-07-29 15:13:28 SimpMalloc

Re: SimpMalloc

# 3 2009-08-03 07:16:56 SimpMalloc

Re: SimpMalloc

# 4 2009-08-03 15:47:59 SimpMalloc

Re: SimpMalloc

Board footer