Memory management using segregated free lists
The present disclosure is directed to a memory management method and to a memory management device arranged to execute memory allocation and/or memory deallocation by use of segregated free lists, which provide information on memory chunks, wherein the memory allocation and/or the memory deallocation are executed according to states of the memory chunks, and wherein the states of the memory chunks comprise: an used state indicating that a memory chunk, which is in used state, is in use, and is not available for allocation; a linked state indicating that a memory chunk, which is in linked state, is not used, is linked within a free list of the segregated free lists, and is available for allocation; a free state indicating that a memory chunk, which is in free state, is not used, is not linked within any of the segregated free lists, and is not available for allocation.
1. A memory management method, comprising:
finding a first memory chunk within a free list segregated free lists in a memory block split into memory chunks of different sizes each free list represented by a chain of memory chunks of a same size, each memory chunk in the memory block having information on a state of the memory chunk, wherein the state of the memory chunk is one of a used state, a linked state, or a free state, the used state for indicating a memory chunk in use and not available for allocation, the linked state for indicating a memory chunk that is not used, linked within a free list of the segregated free lists, and available for allocation, and the free state for indicating a memory chunk that is not used, not linked within any of the segregated free lists, and is not available for allocation;
unlinking the first memory chunk from the free list of the segregated free lists, and setting the state of the first memory chunk to the used state;
determining that a right-adjacent memory chunk of the first memory chunk is in the free state; and
linking the right-adjacent memory chunk into a corresponding free list of the segregated free lists and setting the state of the right-adjacent memory chunk to the linked state.
2. The memory management method according to claim 1 , further comprising:
executing memory deallocation by:
verifying a state of a left-adjacent memory chunk of the first memory chunk;
setting the state of the first memory chunk to the linked state and linking the first memory chunk within a corresponding free list of the segregated free lists when the left-adjacent memory chunk is in the used state, or setting the state of the first memory chunk to the free state when the left-adjacent memory chunk is in the linked state; and
merging the first memory chunk and the left-adjacent memory chunk to a new memory chunk and setting the state of the new memory chunk to the free state when the left-adjacent memory chunk is in the free state.
3. The memory management method according to claim 2 , wherein the segregated free lists are singly-linked.
4. The memory management method according to claim 2 , further comprising:
terminating memory allocation when the right-adjacent memory chunk of the first memory chunk is not in the free state.
5. The memory management method according to claim 2 , wherein each memory chunk of the memory chunks comprises a header and a footer, and wherein at least one of the header or the footer indicates the state of the respective memory chunk.
6. The memory management method according to claim 5 , wherein merging the first memory chunk and the left-adjacent memory chunk comprises:
merging a footer of the left-adjacent memory chunk and a header of the first memory chunk to an area for storage of data.
7. A memory management device, comprising:
a processor;
a memory storage plurality of instructions that, when executed by the processor, cause the device to:
find a first memory chunk within a free list of segregated free lists in a memory block split into memory chunks of different sizes, each free list represented by a chain of memory chunks of a same size, each memory chunk in the memory block having information on a state of the memory chunk, wherein the state of the memory chunk is one of a used state, a linked state, or a free state, the used state for indicating a memory chunk in use and not available for allocation, the linked state for indicating a memory chunk that is not used, linked within a free list of the segregated free lists, and available for allocation, and the free state for indicating a memory chunk that is not used, not linked within any of the segregated free lists, and is not available for allocation;
unlink the first memory chunk from the free list of the segregated free lists, and set the state of the first memory chunk to the used state;
verify whether a right-adjacent memory chunk of the first memory chunk in memory is in the free state; and
when the right-adjacent memory chunk is in the free state, link the right-adjacent memory chunk into a corresponding free list of the segregated free lists and set the state of the right-adjacent memory chunk to the linked state.
8. The memory management device according to claim 7 , wherein the instructions, when executed by the processor, cause the device to:
execute memory deallocation comprising:
verify the state of a left-adjacent memory chunk of the first memory chunk;
set the state of the first memory chunk to the linked state and link the first memory chunk within a corresponding free list of the segregated free lists when the left-adjacent memory chunk is in the used state, or set the state of the first memory chunk to the free state when the left-adjacent memory chunk is in the linked state; and
merge the first memory chunk and the left-adjacent memory chunk to a new memory chunk and set the state of the new memory chunk to the free state when the left-adjacent memory chunk is in the free state.
9. The memory management device according to claim 8 , wherein the segregated free lists are singly-linked.
10. The memory management device according to claim 8 , wherein the instructions, when executed by the processor, cause the device to:
terminate the memory allocation action when the right-adjacent memory chunk of the first memory chunk is not in the free state.
11. The memory management device according to claim 8 , wherein each memory chunk of the memory chunks comprises a header and a footer, and wherein at least on of the header or the footer indicates the state of the respective memory chunk.
12. The memory management device according to claim 11 , wherein to merge the first memory chunk and the left-adjacent memory chunk, the instructions, when executed by the processor, cause the device to:
merge a footer of the left-adjacent memory chunk and a header of the first memory chunk to an area for storage of data.
13. A non-transitory machine-readable medium having instructions stored therein for managing memory, the instructions, when executed by a processor, causing the processor to perform operations, the operations comprising:
finding a first memory chunk within a free list of segregated free lists in a memory block split into memory chunks of different sizes, each free list represented by a chain of memory chunks of a same size, each memory chunk in the memory block having information on a state of the memory chunk, wherein the state of the memory chunk is one of a used state, a linked state, or a free state, the used state for indicating a memory chunk in use and not available for allocation, the linked state for indicating a memory chunk that is not used, linked within a free list of the segregated free lists, and available for allocation, and the free state for indicating a memory chunk that is not used, not linked within any of the segregated free lists, and is not available for allocation;
unlinking the first memory chunk from the free list of the segregated free lists, and setting the state of the first memory chunk to the used state;
determining that a right-adjacent memory chunk of the first memory chunk is in the free state; and
linking the right-adjacent memory chunk into a corresponding free list of the segregated free lists and setting the state of the right-adjacent memory chunk to the linked state.
14. The non-transitory machine-readable medium according to claim 13 , the operations further comprising:
executing memory deallocation by:
verifying a state of a left-adjacent memory chunk of the first memory chunk;
setting the state of the first memory chunk to the linked state and linking the first memory chunk within a corresponding free list of the segregated free lists when the left-adjacent memory chunk is in the used state, or setting the state of the first memory chunk to the free state when the left-adjacent memory chunk is in the linked state; and
merging the first memory chunk and the left-adjacent memory chunk to a new memory chunk and setting the state of the new memory chunk to the free state when the left-adjacent memory chunk is in the free state.
15. The non-transitory machine-readable medium according to claim 14 , wherein the segregated free lists are singly-linked.
16. The non-transitory machine-readable medium according to claim 14 , the operations further comprising:
terminating memory allocation when the right-adjacent memory chunk of the first memory chunk is not in the free state.
17. The non-transitory machine-readable medium according to claim 14 , wherein each memory chunk of the memory chunks comprises a header and a footer, and wherein at least one of the header or the footer indicates the state of the respective memory chunk.
18. The non-transitory machine-readable medium according to claim 17 , wherein merging the first memory chunk and the left-adjacent memory chunk comprises:
merging a footer of the left-adjacent memory chunk and a header of the first memory chunk to an area for storage of data.