US-12625802-B2 - Technique for power optimized memory pools

US12625802B2US 12625802 B2US12625802 B2US 12625802B2US-12625802-B2

Abstract

A system and method for allocating blocks from a memory pool is disclosed. The memory is made up of a plurality of banks, wherein the power to each is independently controlled. Several linked lists are used to ensure that blocks are always allocated from the bank with the fewer free blocks. In this way, the possibility of having banks where all of their blocks are unallocated is increased, and these banks may be powered off during deep sleep mode. The linked lists track the location of the free blocks in each bank, and the number of free blocks in each bank.

Inventors

Jean Francois Deschenes
Cedric Migliorini

Assignees

SILICON LABORATORIES INC.

Dates

Publication Date: 20260512
Application Date: 20240916

Claims (17)

1 . A method of organizing and allocating blocks from a pool of memory, wherein the pool comprising a plurality of blocks disposed in a plurality of banks, the method comprising: creating a first linked list to identify free blocks in a bank, wherein the first linked list comprises block structures, each of which points to a free block in a respective bank; creating a second linked list to identify banks that have a same number of free blocks, wherein the second linked list comprises bank structures; creating a third linked list comprising free count entry structures, wherein each free count entry structure is associated with a specific number of free blocks and the third linked list of free count entry structures is arranged in ascending order of free blocks; pointing a memory pool list head to a head of the third linked list; receiving a request from user level software for a free block; and traversing the third linked list, the second linked list and the first linked list to find a next free block to be allocated to the user level software.
2 . The method of claim 1 , wherein a time to find the next free block to be allocated to the user level software is deterministic.
3 . The method of claim 1 , wherein the next free block is allocated from a bank with the fewest free blocks.
4 . The method of claim 1 , wherein each free count entry structure comprises: a next pointer to a next free count entry structure in the third linked list; a previous pointer to a previous free count entry structure in the third linked list; a free count number, which is a number of free blocks disposed in each bank associated with this free count entry structure; and a bank head pointer to a first bank structure that comprises the number of free blocks associated with this free count entry structure.
5 . The method of claim 4 , wherein each bank structure comprises: a next bank pointer to a next bank structure in the second linked list; a previous bank pointer to a previous bank structure in the second linked list; and a block head pointer to a first block structure associated with the bank.
6 . The method of claim 5 , wherein each bank structure comprises a pointer to an associated free count entry structure.
7 . The method of claim 5 , wherein each block structure comprises: an address of a block; and a next block pointer to a next block structure in the first linked list.
8 . The method of claim 7 , wherein the next free block is determined by: using a bank head pointer disposed in a free count entry structure pointed to by the memory pool list head to find a bank structure having a minimum number of free blocks; using the block head pointer in the bank structure having the minimum number of free blocks to find a first block structure in a bank; and returning the address of the block found in the first block structure as the address of the next free block.
9 . The method of claim 8 , further comprising updating the first linked list, the second linked list and the third linked list after the block has been allocated.
10 . The method of claim 9 , wherein the first linked list is updated by setting the block head pointer of the bank structure to the address found in the next block pointer of the block structure of the block that was allocated.
11 . The method of claim 9 , wherein the second linked list is updated by decoupling the bank structure from the second linked list.
12 . The method of claim 9 , wherein the third linked list is updated by attaching the bank structure to a free count entry structure that has a free count number that is one less than the free count entry structure that the bank structure was previously attached to.
13 . The method of claim 12 , wherein a free count entry structure that has a free count number that is one less than the free count entry structure that the bank structure was previously attached to already exists, and the bank structure is incorporated into the free count entry structure that has a free count number that is one less than the free count entry structure that the bank structure was previously attached to.
14 . The method of claim 12 , wherein the free count entry structure that has a free count number that is one less than the free count entry structure that the bank structure was previously attached to does not exist, and the method further comprises creating a new free count entry structure and attaching the bank structure to the new free count entry structure.
15 . A device comprising: a processing unit; a data memory device comprising a plurality of banks which may be powered independently; and a memory device, in communication with the processing unit, comprising instructions, which when executed by the processing unit, enable the device to: use a first linked list, a second linked list and a third linked list to determine an address of a free block to allocate to user level software, wherein the first linked list is used to identify free blocks in a bank, and the first linked list comprises block structures, each of which points to a free block in a respective bank and wherein the free block to be allocated is disposed in a bank having a fewest number of free blocks.
16 . The device of claim 15 , wherein the second linked list is used to identify banks that have a same number of free blocks, and wherein the second linked list comprises bank structures.
17 . The device of claim 15 , wherein the third linked list comprising free count entry structures, wherein each free count entry structure is associated with a specific number of free blocks and the third linked list of free count entry structures is arranged in ascending order of free blocks.

Description

FIELD This disclosure describes systems and methods for allocating and pools of volatile memory. BACKGROUND Many wireless protocols, such as Bluetooth Low Energy (BLE) and others, are enabling the Internet of Things (IOTs). One aspect of these IOT devices is their low power consumption, often allowing them to operate for extended periods of time using a battery. This is often accomplished by placing the device into a low power sleep mode. In this deep sleep mode, many components may be powered down, such as the network interface, the processing unit and others. Therefore, in deep sleep mode, one of the largest consumers of power is the volatile memory device. To combat this issue, the volatile memory in these devices may be divided into banks, where each bank may be powered on or powered off independently. Thus, if a bank is unused, or only contains data that is disposable, this bank may be powered off during the deep sleep mode. On the other hand, if a bank contains instructions, a network stack, or other important information, it may remain powered during the deep sleep mode so that the information is retained. These banks are typically relatively large, such as 16 Kbytes or larger. Thus, the allocation of information into the volatile memory is key to determining how many of the memory banks may be powered off during deep sleep mode. Thus, an improved method and system for allocating pools of memory so as to minimize the number of banks that must remain powered during deep sleep mode would be beneficial. SUMMARY A system and method for allocating blocks from a memory pool is disclosed. The memory is made up of a plurality of banks, wherein the power to each is independently controlled. Several linked lists are used to ensure that blocks are always allocated from the bank with the fewer free blocks. In this way, the possibility of having banks where all of their blocks are unallocated is increased, and these banks may be powered off during deep sleep mode. The linked lists track the location of the free blocks in each bank, and the number of free blocks in each bank. According to one embodiment, a method of organizing and allocating blocks from a pool of memory, wherein the pool comprising a plurality of blocks disposed in a plurality of banks, is disclosed. The method comprises creating a first linked list to identify free blocks in a bank, wherein the first linked list comprises block structures, each of which points to a free block in a respective bank; creating a second linked list to identify the banks that have a same number of free blocks, wherein the second linked list comprises bank structures; creating a third linked list comprising free count entry structures, wherein each free count entry structure is associated with a specific number of free blocks and the third linked list of free count entry structures is arranged in ascending order of free blocks; pointing a memory pool list head to a head of the third linked list; receiving a request from user level software for a free block; and traversing the third linked list, the second linked list and the first linked list to find a next free block to be allocated to the user level software. In some embodiments, a time to find the next free block to be allocated to the user level software is deterministic. In some embodiments, the next free block is allocated from the bank with the fewest free blocks. In some embodiments, the free count entry structure comprises: a next pointer to a next free count entry structure in the third linked list; a previous pointer to a previous free count entry structure in the third linked list; a free count number, which is a number of free blocks disposed in each bank associated with this free count entry structure; and a bank head pointer to a first bank structure that comprises the number of free blocks associated with this free count entry structure. In certain embodiments, the bank structure comprises: a next bank pointer to a next bank structure in the second linked list; a previous bank pointer to a previous bank structure in the second linked list; and a block head pointer to a first block structure associated with the bank. In certain embodiments, the bank structure comprises a pointer to an associated free count entry structure. In certain embodiments, the block structure comprises: an address of a block; and a next block pointer to a next block structure in the first linked list. In certain embodiments, the next free block is determined by: using the bank head pointer disposed in the free count entry structure pointed to by the memory pool list head to find a bank structure having a minimum number of free blocks; using the block head pointer in the bank structure having the minimum number of free blocks to find a first block structure in the bank; and returning the address of the block found in the first block structure as the address of the next free block. In certain embodiments, the method includes updating