# uDMA: An Efficient User-Level DMA for NVMe SSDs +
## 4 Design of uDMA
### Pinned Memory Pool
#### 4.3.1 Pinned Memory Pool Allocation  
We dynamically allocate and pin memory blocks for I/O requests, but we do not release blocks of memory that have been pinned immediately after the DMA operation. Instead, we recycle the used and pinned memory blocks into the pinned memory pool for management. The pseudocode of the algorithm is shown in Algorithm 1. The input information is the size of the pinned memory area the application needs to allocate. The output information is the first address information of the memory area found in the pinned memory pool using the algorithm designed in this section. Algorithm 1 needs to deal with three possible situations. The first is when the pinned memory pool does not exist or is empty. The second is when the pinned memory pool is not empty, but the available pinned memory does not meet the demand. The third is when the pinned memory pool is not empty, and the available pinned memory can meet the demand.  
For the first situation, we create a pinned memory pool when the application initializes the NVMe SSD's usage environment, shown in lines 1-6 of Algorithm 1. The pinned memory pool is empty at this stage, causing the application to initiate the first NVMe SSD's access request. When the applicant applies for memory allocation for the first time, we allocate and pin a memory block according to the memory block size configured by the user. After that, we put the memory block into the index for the next memory I/O request (see line 3). We mark the memory area as used, update the memory block's meta information, and return the first address of the memory area to the application. When this pinned memory is used up, we change its state to unused and manage it using a linked list rather than unpinning and releasing it directly.  
For the second and third situations, we do not immediately apply for and pin new memory blocks because there may be blocks of memory that meet the requirements in the pool. Alternatively, we first find the pinned memory pool and get the information through the index of the linked list, shown in lines 8-17 of Algorithm 1. The core idea is to find out whether there is a pinned memory block that meets the memory pool requirements. Moreover, we implement a new pinned memory block management method based on scatter/gather lists in find_memory_region. As shown in Figure 4, benefiting from the scatter/gather lists, we can connect discrete pinned memory blocks to construct a large block. If enough blocks can meet the demand, we directly fetch the corresponding memory from the memory pool instead of allocating and pinning a new memory block. At this time, the time cost of pinning memory is saved. However, if the difference cannot find pinned memory that meets the requirements, we allocate and pin a new memory block, shown in lines 18-22 of Algorithm 1.  
Figure 4: The pinned memory pool design.  
The memory blocks used by traditional DMA must be contiguous, so if the free memory blocks in the pinned memory pool are large enough but not contiguous, we cannot use the free memory. Instead, we must allocate and pin new blocks of memory. This reduces the utilization of memory blocks and increases the I/O latency by allocating and pinning new memory blocks. We implemented a pinned memory management method based on the scatter/gather lists to solve this problem. The scatter/gather lists concatenated the discontiguous memory blocks in the pinned memory pool. Thus, we could assign them to serve user-level DMA transfers.