LSF_BUDDY.h文件#ifndef TLSF_BUDDY_H #define TLSF_BUDDY_H #define NULL 0 // TLSF (Two-Level Segregated Fit) Memory Allocator Implementation #define FREE_LIST_SIZE (sizeof(unsigned int)3) // Minimum block size is the size of List_Node, which includes the Base_Node and the pointers for the free list. #define BLOCK_Min_SIZE (sizeof(List_Node)) // Alignment is set to 4 bytes (32 bits) to ensure that memory blocks are aligned to word boundaries. #define ALIGN_BYTES 0x04 typedef unsigned char UINT_8; typedef unsigned int UINT_32; typedef struct Base_Node { struct { unsigned int Block_Size : (sizeof(unsigned int) 3) - 1; unsigned int Used_flag : 1; }; void* Pre_addr; }Base_Node; typedef struct List_Node { Base_Node Base; struct List_Node* Prev; struct List_Node* Next; }List_Node; typedef struct Memory_Head { UINT_32 Total_Size; UINT_32 Available_Size; UINT_32 Map_unit_size; void* End_Addr_Node; UINT_8 Map_bit[FREE_LIST_SIZE]; List_Node* Free_List_Head[FREE_LIST_SIZE][sizeof(UINT_8) 3]; }Memory_Head; unsigned int Get_highest_bit_position(unsigned int x); Base_Node* Partition_block(unsigned int Remain_Size, unsigned int Malloc_block, unsigned int Min_Block_Size,void* start_addr, Memory_Head* Memory); int Find_Block(Memory_Head* Memory, unsigned int Index_len, unsigned int x); unsigned int Align_Index(unsigned int size, unsigned int alignment); void Add_Node(Memory_Head* Head, List_Node* Node); List_Node* Take_Out_Node(Memory_Head* Head, unsigned int Index); void Delete_Node(Memory_Head* Head, List_Node* Node); void Init_Memory(Memory_Head* Memory, void* start_addr, UINT_32 Size); void* TLSF_BUDDY_malloc(Memory_Head* Memory, unsigned int size); void TLSF_BUDDY_free(Memory_Head* Memory, void* ptr); #endifTLSF_BUDDY.c文件// The code is a memory allocator implementation based on the Two-Level Segregated Fit (TLSF) algorithm. It defines the necessary data structures and constants for managing memory blocks and free lists. #include TLSF_BUDDY.h // Macro to align a given size to the nearest multiple of ALIGN_BYTES. #define ALIGN_SIZE(X) (((X) ALIGN_BYTES - 1) ~(ALIGN_BYTES - 1)) // Get_highest_bit_position函数用于获取一个无符号整数的最高二进制位的位置。它通过二分法不断缩小范围直到找到最高位的位置。返回值是从1开始的位位置如果输入为0则返回0。 unsigned int Get_highest_bit_position(unsigned int x) {//获取数值的最高二进制位的位置位置从1开始 unsigned int high_bit sizeof(x) 3, low_bit 0; unsigned int position (high_bit low_bit) 1; if (x 0) return 0; while ((x position) ^ 0x01U) { if (x position) low_bit position; else high_bit position; position (high_bit low_bit) 1; } return position 1; } // Partition_block函数用于将一个内存块分割成多个较小的块以满足内存分配的需求。它根据剩余大小、要分配的块大小、最小块大小和块大小等参数计算出适当的块大小并将其添加到内存管理器的自由列表中。最后它返回一个指向分割后块的指针。 Base_Node* Partition_block(unsigned int Remain_Size,unsigned int Malloc_block ,unsigned int Min_Block_Size, void* start_addr, Memory_Head* Memory) {//将数值分解成不小于16的块块的大小为2的幂次方 Base_Node* Node NULL,*Pre NULL, *Next NULL; unsigned int block_size 0, high_bit_position 0; unsigned int block_bit (0x01 Memory-Map_unit_size) - 1, Block_position Memory-Map_unit_size; Next (Base_Node*)((UINT_8*)start_addr Remain_Size), Remain_Size - Malloc_block; // The loop continues until the remaining size (Remain_Size) is less than the minimum block size. Inside the loop, it calculates the highest bit position of X to determine the block size to be allocated. The block size is calculated as the largest power of two that is less than or equal to X, and it must also be greater than or equal to the minimum block size. The block size is then subtracted from X to update the remaining size. while (Remain_Size Min_Block_Size) { // Calculate the highest bit position of Remain_Size and determine the block size to be allocated. The block size is calculated as the largest power of two that is less than or equal to X, and it must also be greater than or equal to the minimum block size. The block size is then subtracted from X to update the remaining size. high_bit_position Get_highest_bit_position(Remain_Size); block_size (block_bit (high_bit_position - Block_position)) Remain_Size;//计算出不大于X的最大块大小 Remain_Size - block_size; // Here, you would typically add the block of size block_size to the appropriate free list based on its size. Node (Base_Node*)start_addr; Node-Block_Size block_size,Node-Used_flag 0; if (Pre) Node-Pre_addr Pre; Pre Node, start_addr (UINT_8*)start_addr block_size; Add_Node(Memory, (List_Node*)Node); } // After partitioning, the remaining size (Remain_Size) is less than the minimum block size. We create a node for this remaining size and mark it as used, since it will be allocated to the caller. if (Malloc_block) { Node (Base_Node*)start_addr, Node-Block_Size Remain_Size Malloc_block, Node-Used_flag 1; if (Pre) Node-Pre_addr Pre; } // Finally, we set the End_Addr_Node in the memory manager to point to the end of the allocated block, and if there is a next block, we update its Pre_addr to point to the current node. The function then returns a pointer to the allocated block. if(Memory-End_Addr_Node) Next-Pre_addr Node; return Node; } // Find_Block函数用于在位图数组中查找第一个满足条件的块索引。它首先计算出块索引所在的字节位置和位位置然后检查该位置的位是否满足条件。如果不满足条件则继续向后查找直到找到满足条件的块索引或超过索引长度为止。最后它返回找到的块索引或-1表示未找到。 int Find_Block(Memory_Head* Memory, unsigned int Index_len, unsigned int x) { UINT_32 Temp_bit 0; unsigned int Bit_position sizeof(Memory-Map_bit[0]) 2; if (Memory-Map_bit[x Bit_position] (0x01U (x ((sizeof(Memory-Map_bit[0]) 3) - 1)))) { x (sizeof(Memory-Map_bit[0]) 3) - (x ((sizeof(Memory-Map_bit[0]) 3) - 1)); while ((x Bit_position) Index_len !Memory-Map_bit[x Bit_position]) x sizeof(Memory-Map_bit[0]) 3; } if ((x Bit_position) Index_len) return -1; Temp_bit Memory-Map_bit[x Bit_position]; for (unsigned int i (x ((sizeof(Memory-Map_bit[0]) 3) - 1)); i sizeof(Memory-Map_bit[0]) 3; i, x) { if (Temp_bit (0x01 i)) return x; } return -1; } // Align_Index函数用于计算给定大小和对齐要求的内存块在自由列表中的索引位置。它首先计算出大小和对齐要求的最高二进制位位置然后根据这些位位置计算出对应的自由列表索引。最后它返回一个组合了块大小和对齐要求的索引值。 unsigned int Align_Index(unsigned int size, unsigned int alignment) { unsigned int align_bit alignment - 1; unsigned int Position_bit Get_highest_bit_position(size) - 1; alignment ((0x01 align_bit) - 1) (Position_bit - align_bit); size (alignment size) size ? size : ((alignment size) (0x01 (Position_bit - align_bit))); return (Position_bit align_bit) | (((alignment 1) size) (Position_bit - align_bit)); } // Add_Node函数用于将一个内存块节点添加到内存管理器的自由列表中。它首先计算出块大小对应的自由列表索引然后将节点插入到该索引的链表头部并更新相应的位图以标记该索引有可用块。最后它将节点的使用标志设置为0表示该块是空闲的。 void Add_Node(Memory_Head* Head, List_Node* Node) { if (Node NULL) return; unsigned int Index Align_Index(Node-Base.Block_Size, Head-Map_unit_size); List_Node** Current_Head Head-Free_List_Head[Index (Head-Map_unit_size - 1)][Index ((0x01 (Head-Map_unit_size - 1)) - 1)]; // The function first checks if the input node is NULL. If it is, the function returns immediately. Otherwise, it calculates the index in the free list based on the block size of the node and the minimum block size. It then gets a pointer to the current head of the free list at that index. The node is inserted at the head of the free list by updating its next pointer to point to the current head and setting its previous pointer to NULL. If there is a current head, its previous pointer is updated to point to the new node. Finally, the corresponding bit in the bitmap is set to indicate that there is now a free block at that index, and the available size in the memory manager is increased by the block size of the node. Node-Base.Used_flag 0; Node-Prev NULL; Node-Next *Current_Head; if (*Current_Head) (*Current_Head)-Prev Node; // The function then sets the corresponding bit in the bitmap to indicate that there is now a free block at that index. This is done by calculating the byte index and bit index within that byte for the given index, and then using a bitwise OR operation to set the appropriate bit in the bitmap. Head-Map_bit[Index (Head-Map_unit_size - 1)] | (0x01U (Index ((0x01 (Head-Map_unit_size - 1)) - 1))); *Current_Head Node; Head-Available_Size Node-Base.Block_Size; } // Take_Out_Node函数用于从内存管理器的自由列表中取出一个满足条件的内存块节点。它首先计算出块大小对应的自由列表索引然后从该索引的链表头部取出一个节点并更新相应的位图以标记该索引是否还有可用块。最后它将节点的使用标志设置为1表示该块已被占用并返回该节点。 List_Node* Take_Out_Node(Memory_Head* Head,unsigned int Index) { if (Head NULL) return NULL; List_Node** Current_Head Head-Free_List_Head[Index (Head-Map_unit_size - 1)][Index ((0x01 (Head-Map_unit_size - 1)) - 1)]; List_Node* Node *Current_Head; // The function first checks if the head of the free list at the calculated index is NULL. If it is, it means there are no free blocks of that size, and the function returns NULL. Otherwise, it takes out the node at the head of the free list and updates the head to point to the next node in the list. If there is a next node, it updates its previous pointer to NULL since it will now be the new head of the list. Finally, it sets the used flag of the node to 1 and updates the available size in the memory manager. *Current_Head Node-Next; if (*Current_Head) (*Current_Head)-Prev NULL;else Head-Map_bit[Index (Head-Map_unit_size - 1)] ~(0x01U (Index ((0x01 (Head-Map_unit_size - 1)) - 1))); Node-Base.Used_flag 1; Head-Available_Size - Node-Base.Block_Size; return Node; } // Delete_Node函数用于将一个内存块节点从内存管理器的自由列表中删除。它首先获取节点的前一个节点和下一个节点然后根据节点在链表中的位置更新前一个节点和下一个节点的指针。最后它将节点的使用标志设置为1表示该块已被占用并更新相应的位图以标记该索引是否还有可用块。 void Delete_Node(Memory_Head* Head, List_Node* Node) { if (Head NULL || Node NULL) return; unsigned int Index Align_Index(Node-Base.Block_Size, Head-Map_unit_size); List_Node* Prev_Node Node-Prev, * Next_Node Node-Next; List_Node** Current_Head Head-Free_List_Head[Index (Head-Map_unit_size - 1)][Index ((0x01 (Head-Map_unit_size - 1)) - 1)]; // The function first checks if the head of the free list at the calculated index is the node to be deleted. If it is, it updates the head of the free list to point to the next node. If it is not, it updates the previous nodes next pointer to skip over the node being deleted. Then, if there is a next node, it updates its previous pointer to skip over the node being deleted. Finally, if the head of the free list becomes NULL after deletion, it updates the corresponding bit in the bitmap to indicate that there are no more free blocks of that size. if (*Current_Head Node) *Current_Head Node-Next; else Prev_Node-Next Node-Next; // If there is a next node, update its previous pointer to skip over the node being deleted. This ensures that the linked list remains intact after the deletion of the node. if (Next_Node) Next_Node-Prev Node-Prev; if(*Current_Head NULL) Head-Map_bit[Index (Head-Map_unit_size - 1)] ~(0x01U (Index ((0x01 (Head-Map_unit_size - 1)) - 1))); Node-Base.Used_flag 1; Head-Available_Size - Node-Base.Block_Size; } // Init_Memory函数用于初始化内存管理器。它首先检查提供的内存大小是否足够如果不足则返回。然后它将内存大小对齐到最接近的块大小并初始化内存管理器的位图和自由列表。最后它调用Partition_block函数将整个内存块分割成一个可用的块并更新内存管理器的总大小和可用大小。 void Init_Memory(Memory_Head* Memory, void* start_addr, UINT_32 Size) { if (Size BLOCK_Min_SIZE) return; Size ALIGN_SIZE(Size) ~(BLOCK_Min_SIZE-1); for (unsigned int i 0; i FREE_LIST_SIZE; i) { Memory-Map_bit[i] 0; for (unsigned int j 0; j sizeof(UINT_8) 3; j) Memory-Free_List_Head[i][j] NULL; } Memory-Map_unit_size Get_highest_bit_position(sizeof(Memory-Map_bit[0])3); Memory-End_Addr_Node Partition_block(Size , BLOCK_Min_SIZE, BLOCK_Min_SIZE, start_addr, Memory); Memory-Total_Size Memory-Available_Size; } // TLSF_malloc函数用于在内存管理器中分配一个指定大小的内存块。它首先检查内存管理器是否初始化以及请求的大小是否有效。如果无效则返回NULL。然后它将请求的大小对齐到最接近的块大小并计算出对应的自由列表索引。接下来它从自由列表中取出一个满足条件的块如果没有找到合适的块则返回NULL。最后它计算出剩余大小如果剩余大小足够大可以将其分割成一个新的块并添加回自由列表然后返回分配的块的指针。 void* TLSF_BUDDY_malloc(Memory_Head* Memory, unsigned int size) { // Check if the memory manager is initialized and if the requested size is valid. If not, return NULL. if (Memory NULL || size 0 || size Memory-Available_Size) return NULL; size ALIGN_SIZE(size) ALIGN_SIZE(sizeof(Base_Node)); size size BLOCK_Min_SIZE ? BLOCK_Min_SIZE : size; // Calculate the index in the free list based on the requested size and find a suitable block. If no suitable block is found, return NULL. Otherwise, calculate the actual size of the block to be allocated based on the block index. unsigned int Index Align_Index(size, Memory-Map_unit_size); int Block_Index Find_Block(Memory, FREE_LIST_SIZE, Index 1); // If no suitable block is found, return NULL. Otherwise, calculate the actual size of the block to be allocated based on the block index. if (Block_Index -1) return NULL; size ((0x01U (Memory-Map_unit_size-1)) | (Index ((0x01 (Memory-Map_unit_size-1)) - 1))) ((Index (Memory-Map_unit_size-1)) - (Memory-Map_unit_size-1)); // Take out the block from the free list and calculate the remaining size after allocation. If the remaining size is large enough to be a valid block, partition it and add it back to the free list. List_Node* Node Take_Out_Node(Memory, Block_Index); if (Node NULL) return NULL; unsigned int Remaining_Size Node-Base.Block_Size - size; // If the remaining size is greater than or equal to the minimum block size, partition the block and add the remaining part back to the free list. if (Remaining_Size BLOCK_Min_SIZE) { Node (List_Node*)Partition_block(Node-Base.Block_Size, size,BLOCK_Min_SIZE, (UINT_8*)Node , Memory); } return (UINT_8*)Node ALIGN_SIZE(sizeof(Base_Node)); } // TLSF_free函数用于释放一个之前分配的内存块。它首先检查内存管理器和指针是否有效如果无效则返回。然后它获取要释放的块的前一个块和下一个块并检查它们是否是空闲的。如果前一个块是空闲的则将其从自由列表中删除并与当前块合并。同样地如果下一个块是空闲的则将其从自由列表中删除并与当前块合并。最后计算合并后的块的剩余大小如果剩余大小不是最小块大小的倍数则将其分割成一个新的块并添加回自由列表。最后将当前块添加回自由列表作为一个空闲块。 void TLSF_BUDDY_free(Memory_Head* Memory, void* ptr) { if (Memory NULL || ptr NULL) return; Base_Node* Pre_Node NULL, * Next_Node NULL; Base_Node* Node (Base_Node*)((UINT_8*)ptr - ALIGN_SIZE(sizeof(Base_Node))); // Coalesce adjacent free blocks by checking the previous and next blocks. If the previous block is free, delete it from the free list and merge it with the current block. Similarly, if the next block is free, delete it from the free list and merge it with the current block. Finally, partition the merged block and add it back to the free list. while(Node-Pre_addr) { Pre_Node (Base_Node*)Node-Pre_addr; if (Pre_Node-Used_flag) break; Delete_Node(Memory, (List_Node*)Pre_Node); Pre_Node-Block_Size Node-Block_Size; Node Pre_Node; } // The loop continues as long as the next block is within the bounds of the memory and is free. If the next block is free, it is deleted from the free list and merged with the current block by adding their sizes together. The current block pointer is then updated to point to the merged block. while (1) { Next_Node (Base_Node*)((UINT_8*)Node Node-Block_Size); if ((UINT_8*)Next_Node (UINT_8*)Memory-End_Addr_Node || Next_Node-Used_flag) break; Delete_Node(Memory, (List_Node*)Next_Node); Node-Block_Size Next_Node-Block_Size; } // After coalescing adjacent free blocks, the remaining size of the current block is calculated. If the remaining size is not a multiple of the minimum block size, it is partitioned and added back to the free list. Finally, the current block is added back to the free list as a free block. unsigned int Remaining_Size Node-Block_Size; unsigned int Min_Block_Size Remaining_Size (BLOCK_Min_SIZE - 1); if(Min_Block_Size) { Min_Block_Size | BLOCK_Min_SIZE; Partition_block(Min_Block_Size, 0, BLOCK_Min_SIZE, Node, Memory); Node (Base_Node*)((UINT_8*)Node Min_Block_Size), Remaining_Size - Min_Block_Size; } Partition_block(Remaining_Size, 0, BLOCK_Min_SIZE, Node, Memory); }