TLSF Dynamic Memory Allocation: Unterschied zwischen den Versionen
Mat (Diskussion | Beiträge) K (→Samples) |
Mat (Diskussion | Beiträge) K (→Index) |
||
| (2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 5: | Zeile 5: | ||
* [[Bascom Precompiler|''[OOP 3/3] Bascom-Precompiler'']] | * [[Bascom Precompiler|''[OOP 3/3] Bascom-Precompiler'']] | ||
| + | |||
| + | * [https://www.mcselec.com/index2.php?option=com_forum&Itemid=59&page=viewtopic&p=83584#83584 Forum thread] | ||
== Overview == | == Overview == | ||
| Zeile 311: | Zeile 313: | ||
== Download == | == Download == | ||
| − | [ | + | * [http://www.braunecker.at/downloads/memory-allocators/memory-allocators-1-0.zip Memory Allocators & Precompiler Package 1.0] |
Aktuelle Version vom 5. November 2023, 16:51 Uhr
Inhaltsverzeichnis
Index
- [OOP 1a/3] Dynamic Memory Allocation using TLSF
- [OOP 1b/3] Static Memory Allocation
- [OOP 2/3] Object Oriented Programming in Bascom
- [OOP 3/3] Bascom-Precompiler
Overview
TLSF (Two-Level Segregated Fit) is a dynamic memory allocator suited for real-time systems. It is a good-fit algorithm with a bound response time O(1) for any number of managed memory blocks.
Free blocks of memory are organized in lists each containing blocks of a specific size range. Requested blocks are searched in the list with sizes equal or greater the requested size, remaining memory is split up if neccessary and sorted back into the list. Freed blocks are merged with neighboring free blocks and also put back into the list.
The remaining memory from the end of global declared variables to the start of the stack spaces and also external memory (Xram), if available, is managed by the library (configurable).
How to use it
Setup
Create an inc subfolder to your project and copy the files os_common.inc, os_memory.inc and os_malloc_tlsf.inc into the folder.
Include the library:
' any const option must be placed above the file include Const Os_mem_free_size = ### ' mandatory $include "inc\os_malloc_tlsf.inc"
The start adress of the free memory area can not be determined automatically (Bascom-AVR 2.0.8.6). It can be found by examining the compile report, fill in the value from "Space Left".
Compiler report example
Here is a (shortened) example of a compiler report, and where the remaining free memory size could be found. In this example, there are 7477 bytes left.
Report : tlsf-xmem-sample Date : 11-03-2023 Time : 02:51:23 Compiler : BASCOM-AVR LIBRARY V 2.0.8.6 Processor : XM128A1U SRAM : 2000 hex EEPROM : 800 hex ROMSIZE : 22000 hex ROMIMAGE : 324A hex -> Will fit into ROM ROMIMAGE : 12874 dec FLASH USED : 9 % UART1 : 0.01 % ERROR XTAL : 32000000 Hz XRAM : 800000 hex Stack start : 3FFF hex Stack size : 80 hex S-Stacksize : 80 hex S-Stackstart : 3F80 hex Framesize : 80 hex Framestart : 3E80 hex Space left : 7477 dec <------ LCD DB7 : PORTB.7 LCD DB6 : PORTB.6 LCD DB5 : PORTB.5 LCD DB4 : PORTB.4 LCD E : PORTB.3 LCD RS : PORTB.2 LCD mode : 4 bit -------------------------------------------------------------------------------- Variable Type Address(hex) Address(dec) -------------------------------------------------------------------------------- DACA0 Word 0318 792 ...
Managing memory
The library works with memory adresses. If a memory request of given size can be served (consecutive block of free memory has been found), the adress of the start of the block is returned. For a size request bigger than what is managed by the algorithm, as fallback a simple search for a block of suitable size through the last list will be performed (O(n)). If the request can't be fullfilled, the value 0 is returned. The application has to check for that return value and react accordingly, it is also responsible not to write outside of the requested block of memory. Allocated memory is NOT cleared (set to 0) by the library.
With no external memory, 16 bit adress width (Word variable type) is used, with external memory 24 bits are used (DWord type).
Dim Myblockofmemory As [Word/Dword] Myblockofmemory = Malloc([Size]) If Myblockofmemory = 0 Then ' memory allocation error handling (not enough free memory) End If
When the block is no longer needed, it must be returned to the free memory pool by calling:
Free Myblockofmemory
Interface description
The following constants have to be defined prior to including the library. The values shown here are default values if the constant is not defined by the user.
Const Os_mem_free_size = [Compile Report->Space Left]
Const Os_mem_free_start = [&H200/with XRAM: &H2000]
MANDATORY parameter, as described in Setup. For reasons, it has also default values. Set either one, the other will be calculated. Setting Os_mem_free_size is the recommended method.
Const Os_tlsf_fli_offset = 4
Start of first level block size ranges in powers of 2. Size = 2 ^ (Os_tlsf_fli_offset + 1); with a default value of 4, first level sizes start at 32.
Const Os_tlsf_max_fli = [10/with XRAM: 12]
End of first level block size ranges. Size = 2 ^ Os_tlsf_max_fli; defaults without XRAM to 1024, with XRAM to 4096.
Const Os_tlsf_max_log2_sli = 3
Log2 of Second level range count (max. 3). Since the search process is speed up by using bitmaps, this value should match the platform's word width. For 8-Bit AVR it is 2 ^ 3 = 8.
These 3 parameters result in the following block size ranges (default values, no XRAM):
First level | Second level (+4+1) | 0 1 2 3 4 5 6 7 -------------------------------------------------------------------------- 0 | 32 | 0 4 8 12 16 20 24 28 1 | 64 | 32 36 40 44 48 52 56 60 2 | 128 | 64 72 80 88 96 104 112 120 3 | 256 | 128 144 160 176 192 208 224 240 4 | 512 | 256 288 320 352 384 416 448 480 5 | 1024 | 512 576 640 704 768 832 896 960
Index 0 is not used, Index 1 is a list containing blocks up to a size of 4 Bytes, Index 2 list has sizes from 4 to 8 Bytes, Index 8 contains 16-32 Byte blocks, ...
Const Debug_level_tlsf = 0
Set debug output verbosity, 0 = no debug, 1 = Print out available memory each Malloc/Free, 2 = Print out memory pool overview, 3 = Print additional info during Malloc/Free. If debug outputs are activated, option Os_task_debug_metrics is also declared.
Const Os_task_dbg_metrics = 0
Declare Const (value doesn't matter) to enable tracking of available memory. If activated, a variable will be created:
#if Os_big_ram = False Dim Available_memory As Word #else Dim Available_memory As Dword #endif
#if Os_big_ram = False Function Malloc(byval Size As Word) As Word #else Function Malloc(byval Size As Dword) As Dword #endif
Request a block of memory of given size. Returns the starting memory adress or zero if not enough free memory left.
#if Os_big_ram = False Sub Free(byref Block As Word) #else Sub Free(byref Block As Dword) #endif
Returns a previously allocated block to the free memory pool.
#if Os_big_ram = False Function Os_malloc_blocksize(byref Block As Word) As Word #else Function Os_malloc_blocksize(byref Block As Dword) As Dword #endif
Returns the size of a block.
Sub Os_malloc_clear()
Empties all lists, resets the allocator
Sub Os_malloc_init()
Initializes the allocator. This is done when the library is included, in standard applications, it is not needed to call. However, to reset the allocator, use Os_malloc_clear before calling Os_malloc_init.
Samples
M32 internal SRAM (runs in Simulator)
$regfile = "m32def.dat"
$crystal = 1000000
$hwstack = 32
$swstack = 32
$framesize = 64
$baud = 9600
Config Submode = New
' Set start address of the free memory pool manually (examine compile report, "show internal variables" - setting enabled)
Const Os_mem_size_free = 1810
Const Os_task_dbg_metrics = 1 ' constant needs to be defined if we want to see the available memory
' include needed libraries
$include "..\..\src\inc\os_common.inc" ' per default os_common.inc and os_memory.inc are included by the memory allocator and are expected
$include "..\..\src\inc\os_memory.inc" ' in the subdirectory "inc". To accomodate for the different directory structure of the samples,
' we need to override the default includes
$include "..\..\src\inc\os_malloc_tlsf.inc"
Dim Memoryblock1 As Word
Dim Memoryblock2 As Word
Print "Free Memory: " ; Available_memory
Memoryblock1 = Malloc(512)
Memoryblock2 = Malloc(45)
Print "adr1: " ; Memoryblock1 ; " adr2: " ; Memoryblock2
Print "Free Memory: " ; Available_memory
Free Memoryblock1
Free Memoryblock2
Print "Free Memory: " ; Available_memory
End
Output:
Free Memory: 1804 adr1: 210 adr2: 726 Free Memory: 1236 Free Memory: 1804
ATXMega128A1-Xplained (8Mb ext. SRAM)
$regfile = "xm128a1udef.dat"
$crystal = 32000000
$baud = 115200
$hwstack = 128
$swstack = 128
$framesize = 128
Config Submode = New
Config Osc = Disabled , 32mhzosc = Enabled
Config Sysclock = 32mhz , Prescalea = 1 , Prescalebc = 1_1
Config Com1 = 115200 , Mode = Asynchroneous , Parity = None , Stopbits = 1 , Databits = 8
Open "COM1:" For Binary As #1
' =========== XRAM ============
'the XPLAINED has a 64 MBit SDRAM which is 8 MByte, it is connected in 3 port, 4 bit databus mode
'in the PDF of the SDRAM you can see it is connected as 16 Meg x 4. Refreshcount is 4K and the row address is A0-A11, column addressing is A0-A9
$xramsize = 8388608 ' 8 MByte
Config Xram = 3port , Sdbus = 4 , Sdcol = 10 , Sdcas = 3 , Sdrow = 12 , Refresh = 500 , Initdelay = 3200 , Modedelay = 2 , Rowcycledelay = 7 , Rowprechargedelay = 7 , Wrdelay = 1 , Esrdelay = 7 , Rowcoldelay = 7 , Modesel3 = Sdram , Adrsize3 = 8m , Baseadr3 = &H0000
'the config above will set the port registers correct. it will also wait for Ebi_cs3_ctrlb.7
' =========== MEMORY ALLOCATOR ============
' Set size of the free memory pool manually (examine compile report, -> "Space Left")
Const Os_mem_size_free = 7476 ' activated debug info needs an additional byte
Const Os_task_dbg_metrics = 1 ' constant needs to be defined if we want to see the available memory (value doesn't matter)
Const Debug_level_tlsf = 0 ' print out additional debug info, possible values: 0 (no info), 1, 2 and 3 (full info)
' include needed libraries
$include "..\..\src\inc\os_common.inc" ' per default os_common.inc and os_memory.inc are included by the memory allocator and are expected
$include "..\..\src\inc\os_memory.inc" ' in the subdirectory "inc". To accomodate for the different directory structure of the samples,
' we need to override the default includes
$include "..\..\src\inc\os_malloc_tlsf.inc"
' =========== DEMO ============
Dim Memoryblock1 As Dword
Dim Memoryblock2 As Dword
Dim Memoryblock3 As Dword
Dim Memoryblock4 As Dword
Dim Blocksize As Dword
Print "Start, free memory: " ; Available_memory
' allocate some smaller blocks (will be served from internal sram first)
Memoryblock1 = Malloc(123)
Blocksize = Os_malloc_blocksize(memoryblock1)
Print "Alloc 123, free memory: " ; Available_memory
Print "Address 1: " ; Memoryblock1 ; " Size: " ; Blocksize
Memoryblock2 = Malloc(48)
Blocksize = Os_malloc_blocksize(memoryblock2)
Print "Alloc 48, free memory: " ; Available_memory
Print "Address 2: " ; Memoryblock2 ; " Size: " ; Blocksize
' allocate bigger blocks to force allocation from external memory
Memoryblock3 = Malloc(10000)
Blocksize = Os_malloc_blocksize(memoryblock3)
Print "Alloc 10000, free memory: " ; Available_memory
Print "Address 3: " ; Memoryblock3 ; " Size: " ; Blocksize
Memoryblock4 = Malloc(12345)
Blocksize = Os_malloc_blocksize(memoryblock4)
Print "Alloc 12345, free memory: " ; Available_memory
Print "Address 4: " ; Memoryblock4 ; " Size: " ; Blocksize
' free up allocated memory
Free Memoryblock1
Print "Freed block 1, free memory: " ; Available_memory
Free Memoryblock2
Print "Freed block 2, free memory: " ; Available_memory
Free Memoryblock3
Print "Freed block 3, free memory: " ; Available_memory
Free Memoryblock4
Print "Freed block 4, free memory: " ; Available_memory
End
Output:
Start, free memory: 8396068 Alloc 123, free memory: 8395932 Address 1: 8531 Size: 128 Alloc 48, free memory: 8395876 Address 2: 8667 Size: 48 Alloc 10000, free memory: 8385868 Address 3: 16392 Size: 10000 Alloc 12345, free memory: 8373512 Address 4: 26400 Size: 12348 Freed block 1, free memory: 8373640 Freed block 2, free memory: 8373704 Freed block 3, free memory: 8383704 Freed block 4, free memory: 8396068
