Reusing virtual pages via Automatic Pool Allocation
In Automatic Pool Allocation, each pool created by the program at run-time is essentially a distinct heap, managed internally using some allocation algorithm. We can use there mapping approach described above within each pool created by the program at run-time. The key benefit is that, at a pool_destroy, we can release all (shadow and canonical)virtual memory pages of the pool to be reused by future allocations. Note that physical pages will continue to be reused just as in the original program, i.e., the physical memory consumption remains the same as in the original program (except for minor differences potentially caused by using the pool allocator on top of the original heap.
The only significant change in the Allocation and Deallocation operations described above is for reusing virtual pages. This is slightly tricky because we need to reuse virtual pages that might have been aliased with other virtual pages previously. One simple solution would be to use the unmap system call to release previous virtual-to physical mappings for all pages in a pool after a pool destroy.unmap would work for both canonical and shadow pages because these are obtained from the Operating System(OS) via mmap and mremap respectively. Canonical pages are obtained in contiguous blocks from the underlying system (via mmap) and the blocks can be unmapped efficiently.The shadow pages, however, are potentially scattered around in the heap, and in the worst case may requirea separate unmap operation for every individual object allocated from the pool (in addition to the earlier mprotect call when the object was freed). This could be expensive.
We avoid the explicit munmap calls by maintaining afree list of virtual pages shared across pools and adding all pool pages to this free list at a pool_destroy. We modified the underlying pool allocator to obtain (canonical) pages from this free list, if available. If this free list is empty, we use mmap to obtain fresh pages from the systemas before. For each allocated object, the shadow page(s) is (are) obtained using mremap as before to ensure a distinct virtual memory page.
A pool_free operation works just like the Deallocation case described previously, and invokes the underlying pool_free on the canonical page. A pool_destroy operation simply returns all canonical and shadow pages inthe pool to the shared free list of pages.
f(){ Pool PP; poolinit(&PP, sizeof(struct s)); g(p, PP); p->next->val = … ; //p->next is dangling pooldestroy(PP);}g(struct s *p, Pool *PP) { p->next = poolalloc(PP, sizeof(struct s)); create_10_Node_List(p, PP); initialize(p); h(p); free_all_but_head(p, PP);}
Example 1 –> After pool allocation transformation
Considering the example again but after pool allocation (Example 1 ), a fresh pool is created for each list on entry to f() and destroyed before returning from f(). Within this pool, nodes are allocated on separate pages, the pages are protected on free, and the dangling pointer reference is detected as before. On return from f(), however, all the virtual pages of the pool will be released to the free list and reused for future allocations (in future invocations of f() or elsewhere). The key property is that the compiler was able to prove that no pointers to the pool are reachable after f() returns. This is much simpler than compile-time detection of dangling pointers, which would have required predicting at the reference to p->next->val that specific objects within the list have been freed.
If you enjoyed this post, please consider to leave a comment or subscribe to the feed and get future articles delivered to your feed reader.