Regarding the persistent allocator design

[Hadi Brais]

Hi,

I've been this blog post about pmem allocator design. In the post, it says:

"Persistent heaps don’t have the luxury of virtual memory mappings. The memory you mmap is the memory you get, we can’t mix it."

I think by this you mean when memory is allocated, the pmem device driver will allocate a contiguous segment of persistent memory, map it to virtual memory and return the base address of that segment. This is very similar to the volatile C heap except that the pmem heap (memory pool) has fixed, predetermined size given as an argument to pmemobj_create. In contrast, when allocating disk-based files, the device driver accepts only fixed-size block allocations. The OS will find and allocate the required blocks from the disk and these blocks may or may not be contiguous. Either way, the OS can map all these blocks to a contiguous virtual memory segment. That's why only pmem suffers from internal fragmentation and that's why the pmem allocator has been designed differently from other traditional NVM allocators. Am I right? If this was the case, then why not designing the pmem device driver the same way as the disk driver?

Also, are there any radical differences between pmem allocator and dlmalloc/ptmalloc?

Also the blog post says:

"Contrasting that to a single allocated memory block. It must be contiguous and once allocated cannot be moved."

I think by "it" you referring to the virtual memory segment, right? Well, if the user obtained direct pointers to persistent memory then yes. But why would you want to move it?

Thanks.

-Hadi

[Piotr Balcer]

Hi Hadi,

Hi,

I've been this blog post about pmem allocator design. In the post, it says:

"Persistent heaps don’t have the luxury of virtual memory mappings. The memory you mmap is the memory you get, we can’t mix it."

I think by this you mean when memory is allocated, the pmem device driver will allocate a contiguous segment of persistent memory, map it to virtual memory and return the base address of that segment. This is very similar to the volatile C heap except that the pmem heap (memory pool) has fixed, predetermined size given as an argument to pmemobj_create. In contrast, when allocating disk-based files, the device driver accepts only fixed-size block allocations. The OS will find and allocate the required blocks from the disk and these blocks may or may not be contiguous. Either way, the OS can map all these blocks to a contiguous virtual memory segment. That's why only pmem suffers from internal fragmentation and that's why the pmem allocator has been designed differently from other traditional NVM allocators. Am I right? If this was the case, then why not designing the pmem device driver the same way as the disk driver?

Yes, that's exactly what I've meant. Regular malloc implementations use
either sbrk or anonymous mmap's to get RAM-backed pages from the OS. In the
case of mmap'ed memory the allocator can simply munmap the pages it no
longer needs or alternatively call madvise to tell the OS that those blocks
are no longer needed - that's the main difference between anonymous and
file backed mmap's. It doesn't matter that the file is on DAX-enabled fs or
not, we simply cannot unmap memory pages from the middle of the file in the
same way we can do it anonymous mmap calls. That's the primary difference.
 

Also, are there any radical differences between pmem allocator and dlmalloc/ptmalloc?

The most radical difference is that the individual memory blocks are
tracked in two separate ways. One is the on-media layout and the second one
are volatile buckets. When allocating, memory block is first reserved
(this is where the bulk of the algorithm happens) from a bucket, then the
constructor is called and finally the persistent state is atomically
modified to reflect the allocation.
If I had to compare to a volatile heap I would say that jemalloc
is the most similar.
 

Also the blog post says:

"Contrasting that to a single allocated memory block. It must be contiguous and once allocated cannot be moved."

I think by "it" you referring to the virtual memory segment, right? Well, if the user obtained direct pointers to persistent memory then yes. But why would you want to move it?

The biggest reason why I would want to move objects around is the same
reason file systems do it - to reduce external fragmentation.
 

Thanks.

-Hadi

Thanks for the thoughtful questions ;) Good to know someone's reading our
blog. I'll try to be more verbose in the future, in retrospect the
sentences you qouted aren't phrased very clearly.

Piotrek

[Hadi Brais]

Hi Piotrek,

I noticed that the terms we used are still not very accurate. The system we are discussing has persistent memory, volatile memory, PCIe-based NVM memory and virtual memory which can be backed by any of the memories. Internal and external fragmentation can happen in virtual address space, the persistent memory physical address space and the volatile memory physical address space (of course, both address spaces constitute a single physical address space).

Now imagine a hypothetical OS in which the OS can differentiate between persistent and volatile memory. When allocating a file of persistent memory of some size, the OS would just reserve a segment of the virtual address space, update the persistent memory metadata about the memory pool but without allocating any physical memory. Only when the a page of that reserved virtual segment is accessed, a page fault is triggered and the OS knows that it should allocate block of persistent memory and map it to the virtual page to reattempt the memory access. Of course, the pmem metadata has to be updated. Notice that in such system, the allocator can actually unmap a virtual page and map to some other page (as long as it's safe to do that - the user has not obtained a direct pointer to it). This solves the problem mentioned in the blog post - you can now minimize external fragmentation. Yes, the memory pool in this case will occupy many virtual memory segments but I don't think this is a problem since you're not giving any guarantee to the user that memory pools are contiguous in any address space. You might notice that this is similar to allocating from volatile memory because both Windows and Linux allocate memory lazily unless the user specified to the allocator the the memory should fully "committed." The OS would only need to allocate page-size blocks from pmem. Overall, I imagine this can reduce both internal and external fragmentation of all memory address spaces and  reduce wasted memory consumption. Did you think about this?

I still don't understand the section "File system similarities" from the blog post. I'm not able to make any sense out of it. It would be great if you guys write a blog post about how the pmem device driver works and how the pmem library interacts with it and the role the OS plays in the current implementation.

Thanks,
Hadi

[Andy Rudoff]

Hi Hadi,

Note that much of what you wrote about below is not part of NVML, but part of the persistent memory programming model that NVML is built on.  If you haven't already, I recommend reading about the programming model here:

http://www.snia.org/forums/sssi/nvmp

And you can find more information about how things work at the Linux driver level here:

https://nvdimm.wiki.kernel.org/

-andy

[Piotr Balcer]

Hi Hadi,
Like Andy said, our library is based on a SNIA programming model which uses
file-backed memory mappings to manage persistent memory. We didn't extend
the underlying semantics. Our library doesn't really build on any special
behaviour provided by the pmem device driver.

What you seem to be thinking about was already researched by someone else:
http://dl.acm.org/citation.cfm?id=2901325

But it's a radically different approach to the problem, one which we didn't
take.

About leveraging the virtual memory mappings to avoid fragmentation: it
might be possible to leverage the fallocate punch hole deallcation method
to move bunch of disjoint pages to the end of the file and dynamically
allocate from the newly created coalescted region of pages but that is
currently we currently do not support. If you have any other ideas how to
use existing POSIX file semantics to do that, I'm all ears ;)

Piotrek
 

[Hadi Brais]

Thanks Andy and Piotrek for the references and responses. I'll do some research and may get back to you.

Hadi