TABLE OF CONTENTS

/Malloc-TLSF [ Modules ]

[ Top ] [ Modules ]

DESCRIPTION

Dynamically allocates and frees blocks of memory in constant time. Uses two segregated bitmaps indexing a matrix holding the Free lists of blocks sorted by size-ranges; good-fit TLSF: http://www.gii.upv.es/tlsf/

Malloc-TLSF/Debug_Settings [ Constants ]

[ Top ] [ Malloc-TLSF ] [ Constants ]

DESCRIPTION

Debugging Settings Level 0: no Debug 

         1: Print available memory
         2: Print out detailed informations after each Malloc/Free

DECLARATION

#if Varexist( "Debug_level_tlsf") = False
   Const Debug_level_tlsf = 0
#endif
#if Debug_level_tlsf >= 1 And Varexist( "Debug_allocated_ram") = False
   Const Debug_allocated_ram = True
#endif
#if Varexist( "Debug_allocated_ram") = False
   Const Debug_allocated_ram = False
#endif

Malloc-TLSF/Settings [ Constants ]

[ Top ] [ Malloc-TLSF ] [ Constants ]

DESCRIPTION

Default values result in the following TLSF data structure (block size ranges):

DECLARATION

'  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   '

#if Varexist( "Max_fli") = False
   ' Max. first level index (organize block sizes < 2 ^ Max_fli   '
   Const Max_fli = 10                                       ' 2^10 = 1024   '
#endif
#if Varexist( "Fli_offset") = False
   ' First level sizes start at 2 ^ (Fli_offset + 1)   '
   Const Fli_offset = 4                                     ' 2 ^ (4 + 1) = 32   '
#endif
#if Varexist( "Max_log2_sli") = False
   ' First level size is sub-divided into 2 ^ Max_log2_sli second level sizes   '
   Const Max_log2_sli = 3                                   ' 2 ^ 3 = 8   '
#endif

Malloc-TLSF/Free [ Functions ]

[ Top ] [ Malloc-TLSF ] [ Functions ]

DESCRIPTION

frees up an allocated block, coalesces with Free neighboring blocks if available and returns it to the Free memory pool

DECLARATION

Sub Free(byref Pointer As Word)

SEE ALSO

    Malloc-TLSF/Malloc

SOURCE

   Local Fli As Byte
   Local Sli As Byte
   Local Temp_block As Word
   Local Block_size As Word
   Local Temp_size As Word
   Local Prev_status As Byte
   #if Debug_level_tlsf >= 1
      Local Debug_pointer As Word
      Debug_pointer = Pointer - Block_header_size
   #endif

   Pointer = Pointer - Block_header_size                    ' set Free bit in block header   '
   Os_enter_critical
   Block_size = Getword(pointer , Ptr_size)
   Prev_status = Block_size.prev_block_status
   Block_size = Block_size And Size_mask

   #if Debug_allocated_ram = True
      Available_memory = Available_memory + Block_size
   #endif

   Setword Pointer , Ptr_prev_free , 0                      ' clear Free list pointers   '
   Setword Pointer , Ptr_next_free , 0

   Temp_block = Block_size + Min_block_size                 ' calc next block address   '
   Temp_block = Temp_block + Pointer
   If Temp_block < Free_ram_end Then                        ' next block address is in range   '
      Temp_block = Temp_block - Free_header_size
      Temp_size = Getword(temp_block , Ptr_size)

      If Temp_size.block_status = Status_free Then          ' coalesce with next block   '
         Temp_size = Temp_size And Size_mask
         Os_tlsf_mapping_insert Temp_size , Fli , Sli       ' remove next block from tlsf structure   '
         Os_tlsf_remove_block Temp_block , Fli , Sli

         Block_size = Block_size + Block_header_size        ' merged block size   '
         Block_size = Block_size + Temp_size

         #if Debug_level_tlsf >= 1
            Available_memory = Available_memory + Block_header_size
         #endif
      End If
   End If
   If Prev_status = Status_free Then                        ' coalesce with previous block   '
      Temp_block = Getword(pointer , Ptr_prev_block)        ' get pointer and size of previous block   '
      Temp_size = Getword(temp_block , Ptr_size)
      Prev_status = Temp_size.prev_block_status
      Temp_size = Temp_size And Size_mask

      Os_tlsf_mapping_insert Temp_size , Fli , Sli          ' remove previous block from tlsf structure   '
      Os_tlsf_remove_block Temp_block , Fli , Sli

      Block_size = Block_size + Block_header_size           ' merged block size   '
      Block_size = Block_size + Temp_size
      Pointer = Temp_block                                  ' merged pointer   '

      #if Debug_level_tlsf >= 1
         Available_memory = Available_memory + Block_header_size
      #endif
   End If

   Temp_size = Block_size
   Block_size.block_status = Status_free                    ' mark block as Free   '
   Block_size.prev_block_status = Prev_status               ' previous occupation status   '
   Setword Pointer , Ptr_size , Block_size

   Os_tlsf_mapping_insert Temp_size , Fli , Sli             ' search fl, sl of suitable Free list   '
   Os_tlsf_insert_block Pointer , Fli , Sli                 ' add block to Free list   '

   Temp_block = Temp_size + Pointer                         ' search next block   '
   Temp_block = Temp_block + Min_block_size
   If Temp_block < Free_ram_end Then                        ' in range   '
      Temp_block = Temp_block - Free_header_size
      Temp_size = Getword(temp_block , Ptr_size)            ' set previous block Free bit   '
      Temp_size.prev_block_status = Status_free
      Setword Temp_block , Ptr_size , Temp_size
      Setword Temp_block , Ptr_prev_block , Pointer         ' point to freed block   '
   End If
   Os_exit_critical

   #if Debug_level_tlsf >= 1
      Print "---- Free " ; Debug_pointer ; " --";
      Print_tlsf_debug
   #endif
End Sub

Malloc-TLSF/Malloc [ Functions ]

[ Top ] [ Malloc-TLSF ] [ Functions ]

DESCRIPTION

returns the pointer to a memory block of the requested size if possible, zero if not found

DECLARATION

Function Malloc(byval Size As Word) As Word

SEE ALSO

    Malloc-TLSF/Free

SOURCE

   Local Fli As Byte
   Local Sli As Byte
   Local Pointer As Word
   Local Next_block As Word
   Local Split_block As Word
   Local Remaining_size As Word
   Local Prev_state As Byte
   #if Debug_level_tlsf >= 1
      Local Debug_size As Word
      Debug_size = Size
   #endif

   Size = Size + 3                                          ' 4 byte block align (round up)   '
   Size = Size And Size_mask

   Os_enter_critical
   Os_tlsf_mapping_search Size , Fli , Sli                  ' search first and second level indexes for given size   '
   Pointer = Os_tlsf_find_suitable_block(fli , Sli)
   If Pointer = 0 Then                                      ' no Free block found, aborting   '
      Malloc = 0
      Exit Function
   End If

   #if Debug_allocated_ram = True
      Available_memory = Available_memory - Size
      Available_memory = Available_memory - Block_header_size
   #endif

   Os_tlsf_remove_block_head Pointer , Fli , Sli            ' remove first Free block from list   '

   Remaining_size = Getword(pointer , Ptr_size)             ' get size of found block   '
   Prev_state = Remaining_size.prev_block_status
   Remaining_size = Remaining_size And Size_mask
   Next_block = Pointer + Remaining_size                    ' calc address of next block in memory   '
   Next_block = Next_block + Min_block_size
   Remaining_size = Remaining_size - Size

   If Min_block_size <= Remaining_size Then                 ' need to split the block?   '
      Remaining_size = Remaining_size - Block_header_size
      Remaining_size.block_status = Status_free             ' new block status   '
      Remaining_size.prev_block_status = Status_used

      Split_block = Pointer + Size                          ' calc address of new split block   '
      Split_block = Split_block + Block_header_size
      Setword Split_block , Ptr_size , Remaining_size       ' store new block size   '
      If Next_block < Free_ram_end Then
         Next_block = Next_block - Free_header_size
         Setword Next_block , Ptr_prev_block , Split_block  ' update block links   '
      End If

      Os_tlsf_mapping_insert Remaining_size , Fli , Sli     ' insert new block into tlsf structure   '
      Os_tlsf_insert_block Split_block , Fli , Sli

      Size.prev_block_status = Prev_state                   ' copy prev block status from former Free block to the allocated one   '
      Setword Pointer , Ptr_size , Size
   Else                                                     ' no splitting possible   '
      If Next_block < Free_ram_end Then                     ' update prev used status of next block   '
         Next_block = Next_block - Free_header_size
         Split_block = Getword(next_block , Ptr_size)
         Split_block.prev_block_status = Status_used
         Setword Next_block , Ptr_size , Split_block
      End If

      Remaining_size = Remaining_size + Size                ' allocated block is now used   '
      Remaining_size.block_status = Status_used
      Setword Pointer , Ptr_size , Remaining_size
   End If
   Os_exit_critical

   #if Debug_level_tlsf >= 1
      Print "---- Malloc " ; Debug_size ; " ";
      Print_tlsf_debug
   #endif

   Pointer = Pointer + Block_header_size
   Malloc = Pointer
End Function

Malloc-TLSF/Os_malloc_init [ Functions ]

[ Top ] [ Malloc-TLSF ] [ Functions ]

DESCRIPTION

Initializes the Free memory

DECLARATION

Sub Os_malloc_init()
   Local Poolsize As Word , Poolpointer As Word
   Poolpointer = Free_ram_start                             ' create block from Free ram pool   '
   Poolsize = Pool_size - Block_header_size
   Setword Poolpointer , Ptr_size , Poolsize
   Poolpointer = Poolpointer + Block_header_size
   Free Poolpointer                                         ' insert block into the Free memory pool   '
End Sub