# uDMA: An Efficient User-Level DMA for NVMe SSDs +
## 4 Design of uDMA
### Pinned Memory Pool
#### 4.3.2 Panned Memory Pool Release  
We designed a pinned memory block release algorithm, and the pseudocode is shown in Algorithm 2. The input is the first address of the pinned memory area to be released by the application. The output is the memory block's status, representing the status of the execution result of the release process so that the upper application can judge the execution result. The upper-layer application may mistakenly pass in a memory address that does not exist in the pinned memory pool, shown in lines 2-4 of Algorithm 2.  
```
1:memory_size
2:memory_chunk \(\leftarrow\) alloc_and_pin(pin_size)
3:add_memory_pool(memory_pool,memory_chunk)
4:memory_address \(\leftarrow\) find_memory_region(memory_chunk)
5:update(memory_chunk)
6:return memory_address
7:else
8:formemory_chunk in memory_pool do
9:if mem_free_size(memory_chunk) \(>\) memory_size then
10: memory_address \(\leftarrow\) find_memory_region(memory_chunk)
11: update(memory_chunk)
12:return memory_address
13:endif
14:endfor
15:if total_memory_size + pin_size \(>\) total_pin_size then
16:return null
17:endif
18:memory_chunk \(\leftarrow\) alloc_and_pin(pin_size)
19:memory_address \(\leftarrow\) find_memory_region(memory_chunk)
20:add_memory_pool(memory_pool,memory_chunk)
21:update(memory_chunk)
22:return memory_address
23:endif
```  
**Algorithm 1** Panned memory pool allocation  
We traverse the linked list of pinned memory blocks, finding out if there are contiguous, mergeable memory blocks, shown in lines 9-20 of Algorithm 2. The accessible memory areas before and after merging prevent fragmented memory space when releasing the memory area. If we find blocks that can be merged, we first merge them to get a larger contiguous pinned memory space and then mark it as free. If such memory blocks are not found, we directly mark them as free. After completing the marking of the memory blocks that can be released, as shown in lines 21-24 of Algorithm 2, we detect whether the new time of these memory blocks exceeds the threshold set by the user. Only the memory blocks that exceed the new time set by the user are released.  
```
1:memory_address
2:status
3:memory_chunk \(\leftarrow\) find_memory_chunk(memory_pool, memory_address)
4:ifmemory_chunk is null then
5:return status::error
6:endif
7:pin_memory_free(memory_chunk, memory_address)
8:update(memory_chunk)
9:mem_pre_region \(\leftarrow\) chunk_pre_region(memory_chunk, memory_address)
10:mem_cur_region \(\leftarrow\) memory_address
11:while memory_pre_region is free do
12:merge_free(memory_chunk, mem_pre_region, mem_cur_region)
13:mem_cur_region \(\leftarrow\) mem_pre_region
14:mem_pre_region \(\leftarrow\) chunk_pre_region(memory_chunk, mem_cur_region)
15:endwhile
16:mem_next_region \(\leftarrow\) chunk_pre_region(memory_chunk, memory_address)
17:mem_cur_region \(\leftarrow\) memory_address
18:while memory_next_region is free do
19:merge_free(memory_chunk, mem_next_region, mem_cur_region)
20:mem_cur_region \(\leftarrow\) mem_next_region
21:mem_next_region \(\leftarrow\) chunk_next_region(memory_chunk, mem_cur_region)
22:endwhile
23:ifmemory_chunk is free and memory_chunk_time_interval \(>\) time then
24:delete_memory_chunk(memory_pool, memory_chunk)
25:free_and_unpin(memory_chunk)
26:endif
27:return status::ok
```  
**Algorithm 2** Pinned memory pool release