MADV_FREE support

mm/madvise.c +3 -0

+static int madvise_free_pte_range(pmd_t *pmd, unsigned long addr,
+                               unsigned long end, struct mm_walk *walk)
+

Hi Minchan,

On (11/04/15 10:25), Minchan Kim wrote:
[..]

Quoted 3 lines

mm/madvise.c +3 -0

+static int madvise_free_pte_range(pmd_t *pmd, unsigned long addr,
+                               unsigned long end, struct mm_walk *walk)
+

...

Review

Quoted 2 lines

(quoted diff) +2 -0

+	if (pmd_trans_unstable(pmd))
+		return 0;

I think it makes sense to update pmd_trans_unstable() and pmd_none_or_trans_huge_or_clear_bad() comments in asm-generic/pgtable.h Because they explicitly mention MADV_DONTNEED only. Just a thought.

mm/madvise.c madvise_vma(struct vm_area_struct *vma, struct vm_area_struct **prev, · line 507

Quoted 9 lines

mm/madvise.c +3 -0

@@ -379,6 +502,14 @@ madvise_vma(struct vm_area_struct *vma, struct vm_area_struct **prev,
 		return madvise_remove(vma, prev, start, end);
 	case MADV_WILLNEED:
 		return madvise_willneed(vma, prev, start, end);
+	case MADV_FREE:
+		/*
+		 * XXX: In this implementation, MADV_FREE works like

		  ^^^^
		XXX

mm/madvise.c madvise_vma(struct vm_area_struct *vma, struct vm_area_struct **prev, · line 512

Quoted 6 lines

mm/madvise.c +5 -0

+		 * MADV_DONTNEED on swapless system or full swap.
+		 */
+		if (get_nr_swap_pages() > 0)
+			return madvise_free(vma, prev, start, end);
+		/* passthrough */

	-ss

Quoted 4 lines

I think it makes sense to update pmd_trans_unstable() and pmd_none_or_trans_huge_or_clear_bad() comments in asm-generic/pgtable.h Because they explicitly mention MADV_DONTNEED only. Just a thought.

Hmm, When I read comments(but actually I don't understand it 100%), it says pmd disappearing from MADV_DONTNEED with mmap_sem read-side lock. But MADV_FREE doesn't remove the pmd. So, I don't understand what I should add comment. Please suggest if I am missing something.

Quoted 9 lines

mm/madvise.c madvise_vma(struct vm_area_struct *vma, struct vm_area_struct **prev, · line 507

Quoted 7 lines

mm/madvise.c +3 -0

@@ -379,6 +502,14 @@ madvise_vma(struct vm_area_struct *vma, struct vm_area_struct **prev,
 		return madvise_remove(vma, prev, start, end);
 	case MADV_WILLNEED:
 		return madvise_willneed(vma, prev, start, end);
+	case MADV_FREE:
+		/*
+		 * XXX: In this implementation, MADV_FREE works like

		  ^^^^
		XXX

What does it mean?

mm/madvise.c +6 -0

+	split_huge_page_pmd(vma, addr, pmd);
+	if (pmd_trans_unstable(pmd))
+		return 0;
+
+	pte = pte_offset_map_lock(mm, pmd, addr, &ptl);
+	arch_enter_lazy_mmu_mode();

On (11/04/15 10:25), Minchan Kim wrote:
[..]

mm/madvise.c static long madvise_willneed(struct vm_area_struct *vma, · line 272

Quoted 10 lines

mm/madvise.c +10 -0

+static int madvise_free_pte_range(pmd_t *pmd, unsigned long addr,
+				unsigned long end, struct mm_walk *walk)
+
+{
+	struct mmu_gather *tlb = walk->private;
+	struct mm_struct *mm = tlb->mm;
+	struct vm_area_struct *vma = walk->vma;
+	spinlock_t *ptl;
+	pte_t *pte, ptent;
+	struct page *page;

I'll just ask (probably I'm missing something)

+ pmd_trans_huge_lock() ?

Quoted 7 lines

mm/madvise.c +6 -0

+	split_huge_page_pmd(vma, addr, pmd);
+	if (pmd_trans_unstable(pmd))
+		return 0;
+
+	pte = pte_offset_map_lock(mm, pmd, addr, &ptl);
+	arch_enter_lazy_mmu_mode();

mm/madvise.c static long madvise_willneed(struct vm_area_struct *vma, · line 289

Quoted 10 lines

mm/madvise.c +10 -0

+	for (; addr != end; pte++, addr += PAGE_SIZE) {
+		ptent = *pte;
+
+		if (!pte_present(ptent))
+			continue;
+
+		page = vm_normal_page(vma, addr, ptent);
+		if (!page)
+			continue;
+

	-ss

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Linux doesn't have an ability to free pages lazy while other OS already have been supported that named by madvise(MADV_FREE).

The gain is clear that kernel can discard freed pages rather than swapping out or OOM if memory pressure happens.

Without memory pressure, freed pages would be reused by userspace without another additional overhead(ex, page fault + allocation + zeroing).

How it works:

When madvise syscall is called, VM clears dirty bit of ptes of the range. If memory pressure happens, VM checks dirty bit of page table and if it found still "clean", it means it's a "lazyfree pages" so VM could discard the page instead of swapping out. Once there was store operation for the page before VM peek a page to reclaim, dirty bit is set so VM can swap out the page instead of discarding.

Does this set the write protect bit?

What happens on architectures without hardware dirty tracking?

Using the dirty bit for these semantics scares me. This API creates a page that can have visible nonzero contents and then can asynchronously and magically zero itself thereafter. That makes me nervous. Could we use the accessed bit instead? Then the observable semantics would be equivalent to having MADV_FREE either zero the page or do nothing, except that it doesn't make up its mind until the next read.

mm/madvise.c static long madvise_willneed(struct vm_area_struct *vma, · line 316

Quoted 4 lines

mm/madvise.c +4 -0

+                       ptent = pte_mkold(ptent);
+                       ptent = pte_mkclean(ptent);
+                       set_pte_at(mm, addr, pte, ptent);
+                       tlb_remove_tlb_entry(tlb, pte, addr);

It looks like you are flushing the TLB. In a multithreaded program, that's rather expensive. Potentially silly question: would it be better to just zero the page immediately in a multithreaded program and then, when swapping out, check the page is zeroed and, if so, skip swapping it out? That could be done without forcing an IPI.

In the common case it will be passed many pages by the allocator. There will still be a layer of purging logic on top of MADV_FREE but it can be much thinner than the current workarounds for MADV_DONTNEED. So the allocator would still be coalescing dirty ranges and only purging when the ratio of dirty:clean pages rises above some threshold. It would be able to weight the largest ranges for purging first rather than logic based on stuff like aging as is used for MADV_DONTNEED.

Quoted 7 lines

In the common case it will be passed many pages by the allocator. There will still be a layer of purging logic on top of MADV_FREE but it can be much thinner than the current workarounds for MADV_DONTNEED. So the allocator would still be coalescing dirty ranges and only purging when the ratio of dirty:clean pages rises above some threshold. It would be able to weight the largest ranges for purging first rather than logic based on stuff like aging as is used for MADV_DONTNEED.

I would expect that jemalloc would just start putting the dirty ranges into the usual pair of red-black trees (with coalescing) and then doing purging starting from the largest spans to get back down below whatever dirty:clean ratio it's trying to keep. Right now, it has all lots of other logic to deal with this since each MADV_DONTNEED call results in lots of zeroing and then page faults.

Quoted 3 lines

Does this set the write protect bit?

What happens on architectures without hardware dirty tracking?

It's supposed to avoid needing page faults when the data is accessed again, but it can just be implemented via page faults on architectures without a way to check for access or writes. MADV_DONTNEED is also a valid implementation of MADV_FREE if it comes to that (which is what it does on swapless systems for now).

Quoted 8 lines

Using the dirty bit for these semantics scares me. This API creates a page that can have visible nonzero contents and then can asynchronously and magically zero itself thereafter. That makes me nervous. Could we use the accessed bit instead? Then the observable semantics would be equivalent to having MADV_FREE either zero the page or do nothing, except that it doesn't make up its mind until the next read.

FWIW, those are already basically the semantics provided by GCC and LLVM for data the compiler considers uninitialized (they could be more aggressive since C just says it's undefined, but in practice they allow it but can produce inconsistent results even if it isn't touched).

http://llvm.org/docs/LangRef.html#undefined-values

It doesn't seem like there would be an advantage to checking if the data was written to vs. whether it was accessed if checking for both of those is comparable in performance. I don't know enough about that.

Quoted 11 lines

mm/madvise.c static long madvise_willneed(struct vm_area_struct *vma, · line 316

Quoted 5 lines

mm/madvise.c +4 -0

+                       ptent = pte_mkold(ptent);
+                       ptent = pte_mkclean(ptent);
+                       set_pte_at(mm, addr, pte, ptent);
+                       tlb_remove_tlb_entry(tlb, pte, addr);

It looks like you are flushing the TLB. In a multithreaded program, that's rather expensive. Potentially silly question: would it be better to just zero the page immediately in a multithreaded program and then, when swapping out, check the page is zeroed and, if so, skip swapping it out? That could be done without forcing an IPI.

In the common case it will be passed many pages by the allocator. There will still be a layer of purging logic on top of MADV_FREE but it can be much thinner than the current workarounds for MADV_DONTNEED. So the allocator would still be coalescing dirty ranges and only purging when the ratio of dirty:clean pages rises above some threshold. It would be able to weight the largest ranges for purging first rather than logic based on stuff like aging as is used for MADV_DONTNEED.

With enough pages at once, though, munmap would be fine, too.

Maybe what's really needed is a MADV_FREE variant that takes an iovec. On an all-cores multithreaded mm, the TLB shootdown broadcast takes thousands of cycles on each core more or less regardless of how much of the TLB gets zapped.

Quoted 1 line

With enough pages at once, though, munmap would be fine, too.

That implies lots of page faults and zeroing though. The zeroing alone is a major performance issue.

There are separate issues with munmap since it ends up resulting in a lot more virtual memory fragmentation. It would help if the kernel used first-best-fit for mmap instead of the current naive algorithm (bonus:
O(log n) worst-case, not O(n)). Since allocators like jemalloc and PartitionAlloc want 2M aligned spans, mixing them with other allocators can also accelerate the VM fragmentation caused by the dumb mmap algorithm (i.e. they make a 2M aligned mapping, some other mmap user does 4k, now there's a nearly 2M gap when the next 2M region is made and the kernel keeps going rather than reusing it). Anyway, that's a totally separate issue from this. Just felt like complaining :).

Quoted 4 lines

Maybe what's really needed is a MADV_FREE variant that takes an iovec. On an all-cores multithreaded mm, the TLB shootdown broadcast takes thousands of cycles on each core more or less regardless of how much of the TLB gets zapped.

That would work very well. The allocator ends up having a sequence of dirty spans that it needs to purge in one go. As long as purging is fairly spread out, the cost of a single TLB shootdown isn't that bad. It is extremely bad if it needs to do it over and over to purge a bunch of ranges, which can happen if the memory has ended up being very, very fragmentated despite the efforts to compact it (depends on what the application ends up doing).

I posted a patch doing exactly iovec madvise. Doesn't support MADV_FREE yet though, but should be easy to do it.

http://marc.info/?l=linux-mm&m=144615663522661&w=2

active:clean

Quoted 10 lines · Minchan Kim

Linux doesn't have an ability to free pages lazy while other OS already have been supported that named by madvise(MADV_FREE).

The gain is clear that kernel can discard freed pages rather than swapping out or OOM if memory pressure happens.

Without memory pressure, freed pages would be reused by userspace without another additional overhead(ex, page fault + allocation + zeroing).

[...]

Quoted 9 lines

How it works:

When madvise syscall is called, VM clears dirty bit of ptes of the range. If memory pressure happens, VM checks dirty bit of page table and if it found still "clean", it means it's a "lazyfree pages" so VM could discard the page instead of swapping out. Once there was store operation for the page before VM peek a page to reclaim, dirty bit is set so VM can swap out the page instead of discarding.

What happens if you MADV_FREE something that's MAP_SHARED or isn't ordinary anonymous memory? There's a long history of MADV_DONTNEED on such mappings causing exploitable problems, and I think it would be nice if MADV_FREE were obviously safe.

Does this set the write protect bit?

What happens on architectures without hardware dirty tracking? For that matter, even on architecture with hardware dirty tracking, what happens in multithreaded processes that have the dirty TLB state cached in a different CPU's TLB?

Using the dirty bit for these semantics scares me. This API creates a page that can have visible nonzero contents and then can asynchronously and magically zero itself thereafter. That makes me nervous. Could we use the accessed bit instead? Then the observable

semantics would be equivalent to having MADV_FREE either zero the page or do nothing, except that it doesn't make up its mind until the next read.

mm/madvise.c static long madvise_willneed(struct vm_area_struct *vma, · line 316

Quoted 4 lines

mm/madvise.c +4 -0

+                       ptent = pte_mkold(ptent);
+                       ptent = pte_mkclean(ptent);
+                       set_pte_at(mm, addr, pte, ptent);
+                       tlb_remove_tlb_entry(tlb, pte, addr);

It looks like you are flushing the TLB. In a multithreaded program, that's rather expensive. Potentially silly question: would it be better to just zero the page immediately in a multithreaded program and then, when swapping out, check the page is zeroed and, if so, skip swapping it out? That could be done without forcing an IPI.

Quoted 4 lines

mm/madvise.c +3 -0

+static int madvise_free_single_vma(struct vm_area_struct *vma,
+                       unsigned long start_addr, unsigned long end_addr)
+{

mm/madvise.c static long madvise_willneed(struct vm_area_struct *vma, · line 353

Quoted 10 lines

mm/madvise.c +10 -0

+       unsigned long start, end;
+       struct mm_struct *mm = vma->vm_mm;
+       struct mmu_gather tlb;
+
+       if (vma->vm_flags & (VM_LOCKED|VM_HUGETLB|VM_PFNMAP))
+               return -EINVAL;
+
+       /* MADV_FREE works for only anon vma at the moment */
+       if (!vma_is_anonymous(vma))
+               return -EINVAL;

Does anything weird happen if it's shared?

mm/rmap.c static int try_to_unmap_one(struct page *page, struct vm_area_struct *vma, · line 1381

Quoted 6 lines

mm/rmap.c +5 -0

+               if (!PageDirty(page) && (flags & TTU_FREE)) {
+                       /* It's a freeable page by MADV_FREE */
+                       dec_mm_counter(mm, MM_ANONPAGES);
+                       goto discard;
+               }

Does something clear TTU_FREE the next time the page gets marked clean?

--Andy

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Quoted 24 lines · Andy Lutomirski

Quoted 10 lines · Minchan Kim

Linux doesn't have an ability to free pages lazy while other OS already have been supported that named by madvise(MADV_FREE).

The gain is clear that kernel can discard freed pages rather than swapping out or OOM if memory pressure happens.

Without memory pressure, freed pages would be reused by userspace without another additional overhead(ex, page fault + allocation + zeroing).

[...]

Quoted 9 lines

How it works:

When madvise syscall is called, VM clears dirty bit of ptes of the range. If memory pressure happens, VM checks dirty bit of page table and if it found still "clean", it means it's a "lazyfree pages" so VM could discard the page instead of swapping out. Once there was store operation for the page before VM peek a page to reclaim, dirty bit is set so VM can swap out the page instead of discarding.

Quoted 4 lines

What happens if you MADV_FREE something that's MAP_SHARED or isn't ordinary anonymous memory? There's a long history of MADV_DONTNEED on such mappings causing exploitable problems, and I think it would be nice if MADV_FREE were obviously safe.

It filter out VM_LOCKED|VM_HUGETLB|VM_PFNMAP and file-backed vma and MAP_SHARED with vma_is_anonymous.

Quoted 2 lines

Does this set the write protect bit?

No.

Quoted 10 lines

What happens on architectures without hardware dirty tracking? For that matter, even on architecture with hardware dirty tracking, what happens in multithreaded processes that have the dirty TLB state cached in a different CPU's TLB?

Using the dirty bit for these semantics scares me. This API creates a page that can have visible nonzero contents and then can asynchronously and magically zero itself thereafter. That makes me nervous. Could we use the accessed bit instead? Then the observable

Access bit is used by aging algorithm for reclaim. In addition, we have supported clear_refs feacture.
IOW, it could be reset anytime so it's hard to use marker for lazy freeing at the moment.

Quoted 8 lines

mm/rmap.c static int try_to_unmap_one(struct page *page, struct vm_area_struct *vma, · line 1381

Quoted 6 lines

mm/rmap.c +5 -0

+               if (!PageDirty(page) && (flags & TTU_FREE)) {
+                       /* It's a freeable page by MADV_FREE */
+                       dec_mm_counter(mm, MM_ANONPAGES);
+                       goto discard;
+               }

Does something clear TTU_FREE the next time the page gets marked clean?

Sorry, I don't understand. Could you elaborate it more?

Quoted 49 lines · Minchan Kim

Quoted 24 lines · Andy Lutomirski

Quoted 10 lines · Minchan Kim

Linux doesn't have an ability to free pages lazy while other OS already have been supported that named by madvise(MADV_FREE).

The gain is clear that kernel can discard freed pages rather than swapping out or OOM if memory pressure happens.

Without memory pressure, freed pages would be reused by userspace without another additional overhead(ex, page fault + allocation + zeroing).

[...]

Quoted 9 lines

How it works:

When madvise syscall is called, VM clears dirty bit of ptes of the range. If memory pressure happens, VM checks dirty bit of page table and if it found still "clean", it means it's a "lazyfree pages" so VM could discard the page instead of swapping out. Once there was store operation for the page before VM peek a page to reclaim, dirty bit is set so VM can swap out the page instead of discarding.

Quoted 4 lines

What happens if you MADV_FREE something that's MAP_SHARED or isn't ordinary anonymous memory? There's a long history of MADV_DONTNEED on such mappings causing exploitable problems, and I think it would be nice if MADV_FREE were obviously safe.

It filter out VM_LOCKED|VM_HUGETLB|VM_PFNMAP and file-backed vma and MAP_SHARED with vma_is_anonymous.

Quoted 2 lines

Does this set the write protect bit?

No.

Quoted 10 lines

What happens on architectures without hardware dirty tracking? For that matter, even on architecture with hardware dirty tracking, what happens in multithreaded processes that have the dirty TLB state cached in a different CPU's TLB?

Using the dirty bit for these semantics scares me. This API creates a page that can have visible nonzero contents and then can asynchronously and magically zero itself thereafter. That makes me nervous. Could we use the accessed bit instead? Then the observable

Quoted 5 lines

Access bit is used by aging algorithm for reclaim. In addition, we have supported clear_refs feacture.
IOW, it could be reset anytime so it's hard to use marker for lazy freeing at the moment.

That's unfortunate. I think that the ABI would be much nicer if it used the accessed bit.

In any case, shouldn't the aging algorithm be irrelevant here? A MADV_FREE page that isn't accessed can be discarded, whereas we could hopefully just say that a MADV_FREE page that is accessed gets moved to whatever list holds recently accessed pages and also stops being a candidate for discarding due to MADV_FREE?

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines

mm/rmap.c +5 -0

+               if (!PageDirty(page) && (flags & TTU_FREE)) {
+                       /* It's a freeable page by MADV_FREE */
+                       dec_mm_counter(mm, MM_ANONPAGES);
+                       goto discard;
+               }

Quoted 3 lines

Quoted 1 line

Does something clear TTU_FREE the next time the page gets marked clean?

Sorry, I don't understand. Could you elaborate it more?

I don't fully understand how TTU_FREE ends up being set here, but, if the page is dirtied by user code and then cleaned later by the kernel, what prevents TTU_FREE from being incorrectly set here?

--Andy

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Quoted 56 lines · Andy Lutomirski

Quoted 49 lines · Minchan Kim

Quoted 24 lines · Andy Lutomirski

Quoted 10 lines · Minchan Kim

Linux doesn't have an ability to free pages lazy while other OS already have been supported that named by madvise(MADV_FREE).

The gain is clear that kernel can discard freed pages rather than swapping out or OOM if memory pressure happens.

Without memory pressure, freed pages would be reused by userspace without another additional overhead(ex, page fault + allocation + zeroing).

[...]

Quoted 9 lines

How it works:

When madvise syscall is called, VM clears dirty bit of ptes of the range. If memory pressure happens, VM checks dirty bit of page table and if it found still "clean", it means it's a "lazyfree pages" so VM could discard the page instead of swapping out. Once there was store operation for the page before VM peek a page to reclaim, dirty bit is set so VM can swap out the page instead of discarding.

Quoted 4 lines

What happens if you MADV_FREE something that's MAP_SHARED or isn't ordinary anonymous memory? There's a long history of MADV_DONTNEED on such mappings causing exploitable problems, and I think it would be nice if MADV_FREE were obviously safe.

It filter out VM_LOCKED|VM_HUGETLB|VM_PFNMAP and file-backed vma and MAP_SHARED with vma_is_anonymous.

Quoted 2 lines

Does this set the write protect bit?

No.

Quoted 10 lines

What happens on architectures without hardware dirty tracking? For that matter, even on architecture with hardware dirty tracking, what happens in multithreaded processes that have the dirty TLB state cached in a different CPU's TLB?

Using the dirty bit for these semantics scares me. This API creates a page that can have visible nonzero contents and then can asynchronously and magically zero itself thereafter. That makes me nervous. Could we use the accessed bit instead? Then the observable

Quoted 5 lines

Access bit is used by aging algorithm for reclaim. In addition, we have supported clear_refs feacture.
IOW, it could be reset anytime so it's hard to use marker for lazy freeing at the moment.

Quoted 8 lines

That's unfortunate. I think that the ABI would be much nicer if it used the accessed bit.

In any case, shouldn't the aging algorithm be irrelevant here? A MADV_FREE page that isn't accessed can be discarded, whereas we could hopefully just say that a MADV_FREE page that is accessed gets moved to whatever list holds recently accessed pages and also stops being a candidate for discarding due to MADV_FREE?

I meant if we use access bit as indicator for lazy-freeing page, we could discard valid page which is never hinted by MADV_FREE but just doesn't mark access bit in page table by aging algorithm.

Quoted 66 lines · Minchan Kim

Quoted 64 lines · Andy Lutomirski

Quoted 49 lines · Minchan Kim

Quoted 24 lines · Andy Lutomirski

Quoted 10 lines · Minchan Kim

Linux doesn't have an ability to free pages lazy while other OS already have been supported that named by madvise(MADV_FREE).

The gain is clear that kernel can discard freed pages rather than swapping out or OOM if memory pressure happens.

Without memory pressure, freed pages would be reused by userspace without another additional overhead(ex, page fault + allocation + zeroing).

[...]

Quoted 9 lines

How it works:

When madvise syscall is called, VM clears dirty bit of ptes of the range. If memory pressure happens, VM checks dirty bit of page table and if it found still "clean", it means it's a "lazyfree pages" so VM could discard the page instead of swapping out. Once there was store operation for the page before VM peek a page to reclaim, dirty bit is set so VM can swap out the page instead of discarding.

Quoted 4 lines

What happens if you MADV_FREE something that's MAP_SHARED or isn't ordinary anonymous memory? There's a long history of MADV_DONTNEED on such mappings causing exploitable problems, and I think it would be nice if MADV_FREE were obviously safe.

It filter out VM_LOCKED|VM_HUGETLB|VM_PFNMAP and file-backed vma and MAP_SHARED with vma_is_anonymous.

Quoted 2 lines

Does this set the write protect bit?

No.

Quoted 10 lines

What happens on architectures without hardware dirty tracking? For that matter, even on architecture with hardware dirty tracking, what happens in multithreaded processes that have the dirty TLB state cached in a different CPU's TLB?

Using the dirty bit for these semantics scares me. This API creates a page that can have visible nonzero contents and then can asynchronously and magically zero itself thereafter. That makes me nervous. Could we use the accessed bit instead? Then the observable

Quoted 5 lines

Access bit is used by aging algorithm for reclaim. In addition, we have supported clear_refs feacture.
IOW, it could be reset anytime so it's hard to use marker for lazy freeing at the moment.

That's unfortunate. I think that the ABI would be much nicer if it used the accessed bit.

In any case, shouldn't the aging algorithm be irrelevant here? A MADV_FREE page that isn't accessed can be discarded, whereas we could hopefully just say that a MADV_FREE page that is accessed gets moved to whatever list holds recently accessed pages and also stops being a candidate for discarding due to MADV_FREE?

Quoted 3 lines

I meant if we use access bit as indicator for lazy-freeing page, we could discard valid page which is never hinted by MADV_FREE but just doesn't mark access bit in page table by aging algorithm.

Oh, is the rule that the anonymous pages that are clean are discarded instead of swapped out? That is, does your patch set detect that an

anonymous page can be discarded if it's clean and that the lack of a dirty bit is the only indication that the page has been hit with MADV_FREE?

If so, that seems potentially error prone -- I had assumed that pages that were swapped in but not written since swap-in would also be clean, and I don't see how you distinguish them.

--Andy

Linux doesn't have an ability to free pages lazy while other OS already have been supported that named by madvise(MADV_FREE).

The gain is clear that kernel can discard freed pages rather than swapping out or OOM if memory pressure happens.

Without memory pressure, freed pages would be reused by userspace without another additional overhead(ex, page fault + allocation + zeroing).

Jason Evans said:

: Facebook has been using MAP_UNINITIALIZED
: (https://lkml.org/lkml/2012/1/18/308) in some of its applications for : several years, but there are operational costs to maintaining this : out-of-tree in our kernel and in jemalloc, and we are anxious to retire it : in favor of MADV_FREE. When we first enabled MAP_UNINITIALIZED it : increased throughput for much of our workload by ~5%, and although the : benefit has decreased using newer hardware and kernels, there is still : enough benefit that we cannot reasonably retire it without a replacement. :
: Aside from Facebook operations, there are numerous broadly used : applications that would benefit from MADV_FREE. The ones that immediately : come to mind are redis, varnish, and MariaDB. I don't have much insight : into Android internals and development process, but I would hope to see : MADV_FREE support eventually end up there as well to benefit applications : linked with the integrated jemalloc.
:
: jemalloc will use MADV_FREE once it becomes available in the Linux kernel. : In fact, jemalloc already uses MADV_FREE or equivalent everywhere it's : available: *BSD, OS X, Windows, and Solaris -- every platform except Linux : (and AIX, but I'm not sure it even compiles on AIX). The lack of : MADV_FREE on Linux forced me down a long series of increasingly : sophisticated heuristics for madvise() volume reduction, and even so this : remains a common performance issue for people using jemalloc on Linux. : Please integrate MADV_FREE; many people will benefit substantially.

How it works:

When madvise syscall is called, VM clears dirty bit of ptes of the range. If memory pressure happens, VM checks dirty bit of page table and if it found still "clean", it means it's a "lazyfree pages" so VM could discard the page instead of swapping out. Once there was store operation for the page before VM peek a page to reclaim, dirty bit is set so VM can swap out the page instead of discarding.

Firstly, heavy users would be general allocators(ex, jemalloc, tcmalloc and hope glibc supports it) and jemalloc/tcmalloc already have supported the feature for other OS(ex, FreeBSD)

barrios@blaptop:~/benchmark/ebizzy$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                12
On-line CPU(s) list:   0-11
Thread(s) per core:    1
Core(s) per socket:    1
Socket(s):             12
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 2
Stepping:              3
CPU MHz:               3200.185
BogoMIPS:              6400.53
Virtualization:        VT-x
Hypervisor vendor:     KVM
Virtualization type:   full
L1d cache:             32K
L1i cache:             32K
L2 cache:              4096K
NUMA node0 CPU(s):     0-11
ebizzy benchmark(./ebizzy -S 10 -n 512)

Higher avg is better.

vanilla-jemalloc MADV_free-jemalloc

1 thread
records: 10 records: 10
avg: 2961.90 avg: 12069.70
std: 71.96(2.43%) std: 186.68(1.55%)

max:	3070.00			    max:   12385.00
min:	2796.00			    min:   11746.00

2 thread
records: 10 records: 10
avg: 5020.00 avg: 17827.00
std: 264.87(5.28%) std: 358.52(2.01%)

max:	5244.00			    max:   18760.00
min:	4251.00			    min:   17382.00

4 thread
records: 10 records: 10

avg:	8988.80			    avg:   27930.80
std:	1175.33(13.08%)		    std:    3317.33(11.88%)
max:	9508.00			    max:   30879.00
min:	5477.00			    min:   21024.00

8 thread
records: 10 records: 10
avg: 13036.50 avg: 33739.40
std: 170.67(1.31%) std: 5146.22(15.25%)

max:   13371.00			    max:   40572.00
min:   12785.00			    min:   24088.00

16 thread
records: 10 records: 10
avg: 11092.40 avg: 31424.20
std: 710.60(6.41%) std: 3763.89(11.98%)
max: 12446.00 max: 36635.00
min: 9949.00 min: 25669.00

32 thread
records: 10 records: 10
avg: 11067.00 avg: 34495.80
std: 971.06(8.77%) std: 2721.36(7.89%)
max: 12010.00 max: 38598.00
min: 9002.00 min: 30636.00

In summary, MADV_FREE is about much faster than MADV_DONTNEED.

Compared to MADV_DONTNEED, MADV_FREE's lazy memory free is a huge win to reduce page fault. But there is one issue remaining, the TLB flush. Both MADV_DONTNEED and MADV_FREE do TLB flush. TLB flush overhead is quite big in contemporary multi-thread applications. In our production workload, we observed 80% CPU spending on TLB flush triggered by jemalloc madvise(MADV_DONTNEED) sometimes. We haven't tested MADV_FREE yet, but the result should be similar. It's hard to avoid the TLB flush issue with MADV_FREE, because it helps avoid data corruption.

The new proposal tries to fix the TLB issue. We introduce two madvise verbs:

MARK_FREE. Userspace notifies kernel the memory range can be discarded. Kernel just records the range in current stage. Should memory pressure happen, page reclaim can free the memory directly regardless the pte state.

MARK_NOFREE. Userspace notifies kernel the memory range will be reused soon. Kernel deletes the record and prevents page reclaim discards the memory. If the memory isn't reclaimed, userspace will access the old memory, otherwise do normal page fault handling.

The point is to let userspace notify kernel if memory can be discarded, instead of depending on pte dirty bit used by MADV_FREE. With these, no TLB flush is required till page reclaim actually frees the memory (page reclaim need do the TLB flush for MADV_FREE too). It still preserves the lazy memory free merit of MADV_FREE.

Compared to MADV_FREE, reusing memory with the new proposal isn't transparent, eg must call MARK_NOFREE. But it's easy to utilize the new API in jemalloc.

We don't have code to backup this yet, sorry. We'd like to discuss it if it makes sense.

That's comparable to Android's pinning / unpinning API for ashmem and I think it makes sense if it's faster. It's different than the MADV_FREE API though, because the new allocations that are handed out won't have the usual lazy commit which MADV_FREE provides. Pages in an allocation that's handed out can still be dropped until they are actually written to. It's considered active by jemalloc either way, but only a subset of the active pages are actually committed. There's probably a use case for both of these systems.

The new proposal tries to fix the TLB issue. We introduce two madvise verbs:

MARK_FREE. Userspace notifies kernel the memory range can be discarded. Kernel just records the range in current stage. Should memory pressure happen, page reclaim can free the memory directly regardless the pte state.

MARK_NOFREE. Userspace notifies kernel the memory range will be reused soon. Kernel deletes the record and prevents page reclaim discards the memory. If the memory isn't reclaimed, userspace will access the old memory, otherwise do normal page fault handling.

The point is to let userspace notify kernel if memory can be discarded, instead of depending on pte dirty bit used by MADV_FREE. With these, no TLB flush is required till page reclaim actually frees the memory (page reclaim need do the TLB flush for MADV_FREE too). It still preserves the lazy memory free merit of MADV_FREE.

Compared to MADV_FREE, reusing memory with the new proposal isn't transparent, eg must call MARK_NOFREE. But it's easy to utilize the new API in jemalloc.

Quoted 113 lines · Minchan Kim

Linux doesn't have an ability to free pages lazy while other OS already have been supported that named by madvise(MADV_FREE).

The gain is clear that kernel can discard freed pages rather than swapping out or OOM if memory pressure happens.

Without memory pressure, freed pages would be reused by userspace without another additional overhead(ex, page fault + allocation + zeroing).

Jason Evans said:

: Facebook has been using MAP_UNINITIALIZED
: (https://lkml.org/lkml/2012/1/18/308) in some of its applications for : several years, but there are operational costs to maintaining this : out-of-tree in our kernel and in jemalloc, and we are anxious to retire it : in favor of MADV_FREE. When we first enabled MAP_UNINITIALIZED it : increased throughput for much of our workload by ~5%, and although the : benefit has decreased using newer hardware and kernels, there is still : enough benefit that we cannot reasonably retire it without a replacement. :
: Aside from Facebook operations, there are numerous broadly used : applications that would benefit from MADV_FREE. The ones that immediately : come to mind are redis, varnish, and MariaDB. I don't have much insight : into Android internals and development process, but I would hope to see : MADV_FREE support eventually end up there as well to benefit applications : linked with the integrated jemalloc.
:
: jemalloc will use MADV_FREE once it becomes available in the Linux kernel. : In fact, jemalloc already uses MADV_FREE or equivalent everywhere it's : available: *BSD, OS X, Windows, and Solaris -- every platform except Linux : (and AIX, but I'm not sure it even compiles on AIX). The lack of : MADV_FREE on Linux forced me down a long series of increasingly : sophisticated heuristics for madvise() volume reduction, and even so this : remains a common performance issue for people using jemalloc on Linux. : Please integrate MADV_FREE; many people will benefit substantially.

How it works:

When madvise syscall is called, VM clears dirty bit of ptes of the range. If memory pressure happens, VM checks dirty bit of page table and if it found still "clean", it means it's a "lazyfree pages" so VM could discard the page instead of swapping out. Once there was store operation for the page before VM peek a page to reclaim, dirty bit is set so VM can swap out the page instead of discarding.

Firstly, heavy users would be general allocators(ex, jemalloc, tcmalloc and hope glibc supports it) and jemalloc/tcmalloc already have supported the feature for other OS(ex, FreeBSD)

barrios@blaptop:~/benchmark/ebizzy$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                12
On-line CPU(s) list:   0-11
Thread(s) per core:    1
Core(s) per socket:    1
Socket(s):             12
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 2
Stepping:              3
CPU MHz:               3200.185
BogoMIPS:              6400.53
Virtualization:        VT-x
Hypervisor vendor:     KVM
Virtualization type:   full
L1d cache:             32K
L1i cache:             32K
L2 cache:              4096K
NUMA node0 CPU(s):     0-11
ebizzy benchmark(./ebizzy -S 10 -n 512)

Higher avg is better.

vanilla-jemalloc MADV_free-jemalloc

1 thread
records: 10 records: 10
avg: 2961.90 avg: 12069.70
std: 71.96(2.43%) std: 186.68(1.55%)

max:	3070.00			    max:   12385.00
min:	2796.00			    min:   11746.00

2 thread
records: 10 records: 10
avg: 5020.00 avg: 17827.00
std: 264.87(5.28%) std: 358.52(2.01%)

max:	5244.00			    max:   18760.00
min:	4251.00			    min:   17382.00

4 thread
records: 10 records: 10

avg:	8988.80			    avg:   27930.80
std:	1175.33(13.08%)		    std:    3317.33(11.88%)
max:	9508.00			    max:   30879.00
min:	5477.00			    min:   21024.00

8 thread
records: 10 records: 10
avg: 13036.50 avg: 33739.40
std: 170.67(1.31%) std: 5146.22(15.25%)

max:   13371.00			    max:   40572.00
min:   12785.00			    min:   24088.00

16 thread
records: 10 records: 10
avg: 11092.40 avg: 31424.20
std: 710.60(6.41%) std: 3763.89(11.98%)
max: 12446.00 max: 36635.00
min: 9949.00 min: 25669.00

Quoted 8 lines

32 thread
records: 10 records: 10
avg: 11067.00 avg: 34495.80
std: 971.06(8.77%) std: 2721.36(7.89%)
max: 12010.00 max: 38598.00
min: 9002.00 min: 30636.00

In summary, MADV_FREE is about much faster than MADV_DONTNEED.

The MADV_FREE is discussed for a while, it probably is too late to propose something new, but we had the new idea (from Ben Maurer, CCed) recently and think it's better. Our target is still jemalloc.

Compared to MADV_DONTNEED, MADV_FREE's lazy memory free is a huge win to reduce page fault. But there is one issue remaining, the TLB flush. Both MADV_DONTNEED and MADV_FREE do TLB flush. TLB flush overhead is quite big in contemporary multi-thread applications. In our production workload, we observed 80% CPU spending on TLB flush triggered by jemalloc madvise(MADV_DONTNEED) sometimes. We haven't tested MADV_FREE yet, but the result should be similar. It's hard to avoid the TLB flush issue with MADV_FREE, because it helps avoid data corruption.

The new proposal tries to fix the TLB issue. We introduce two madvise verbs:

MARK_FREE. Userspace notifies kernel the memory range can be discarded. Kernel just records the range in current stage. Should memory pressure happen, page reclaim can free the memory directly regardless the pte state.

MARK_NOFREE. Userspace notifies kernel the memory range will be reused soon. Kernel deletes the record and prevents page reclaim discards the memory. If the memory isn't reclaimed, userspace will access the old memory, otherwise do normal page fault handling.

The point is to let userspace notify kernel if memory can be discarded, instead of depending on pte dirty bit used by MADV_FREE. With these, no TLB flush is required till page reclaim actually frees the memory (page reclaim need do the TLB flush for MADV_FREE too). It still preserves the lazy memory free merit of MADV_FREE.

Compared to MADV_FREE, reusing memory with the new proposal isn't transparent, eg must call MARK_NOFREE. But it's easy to utilize the new API in jemalloc.

We don't have code to backup this yet, sorry. We'd like to discuss it if it makes sense.

Thanks,
Shaohua

Quoted 153 lines · Shaohua Li

Quoted 113 lines · Minchan Kim

Linux doesn't have an ability to free pages lazy while other OS already have been supported that named by madvise(MADV_FREE).

The gain is clear that kernel can discard freed pages rather than swapping out or OOM if memory pressure happens.

Without memory pressure, freed pages would be reused by userspace without another additional overhead(ex, page fault + allocation + zeroing).

Jason Evans said:

: Facebook has been using MAP_UNINITIALIZED
: (https://lkml.org/lkml/2012/1/18/308) in some of its applications for : several years, but there are operational costs to maintaining this : out-of-tree in our kernel and in jemalloc, and we are anxious to retire it : in favor of MADV_FREE. When we first enabled MAP_UNINITIALIZED it : increased throughput for much of our workload by ~5%, and although the : benefit has decreased using newer hardware and kernels, there is still : enough benefit that we cannot reasonably retire it without a replacement. :
: Aside from Facebook operations, there are numerous broadly used : applications that would benefit from MADV_FREE. The ones that immediately : come to mind are redis, varnish, and MariaDB. I don't have much insight : into Android internals and development process, but I would hope to see : MADV_FREE support eventually end up there as well to benefit applications : linked with the integrated jemalloc.
:
: jemalloc will use MADV_FREE once it becomes available in the Linux kernel. : In fact, jemalloc already uses MADV_FREE or equivalent everywhere it's : available: *BSD, OS X, Windows, and Solaris -- every platform except Linux : (and AIX, but I'm not sure it even compiles on AIX). The lack of : MADV_FREE on Linux forced me down a long series of increasingly : sophisticated heuristics for madvise() volume reduction, and even so this : remains a common performance issue for people using jemalloc on Linux. : Please integrate MADV_FREE; many people will benefit substantially.

How it works:

When madvise syscall is called, VM clears dirty bit of ptes of the range. If memory pressure happens, VM checks dirty bit of page table and if it found still "clean", it means it's a "lazyfree pages" so VM could discard the page instead of swapping out. Once there was store operation for the page before VM peek a page to reclaim, dirty bit is set so VM can swap out the page instead of discarding.

Firstly, heavy users would be general allocators(ex, jemalloc, tcmalloc and hope glibc supports it) and jemalloc/tcmalloc already have supported the feature for other OS(ex, FreeBSD)

barrios@blaptop:~/benchmark/ebizzy$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                12
On-line CPU(s) list:   0-11
Thread(s) per core:    1
Core(s) per socket:    1
Socket(s):             12
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 2
Stepping:              3
CPU MHz:               3200.185
BogoMIPS:              6400.53
Virtualization:        VT-x
Hypervisor vendor:     KVM
Virtualization type:   full
L1d cache:             32K
L1i cache:             32K
L2 cache:              4096K
NUMA node0 CPU(s):     0-11
ebizzy benchmark(./ebizzy -S 10 -n 512)

Higher avg is better.

vanilla-jemalloc MADV_free-jemalloc

1 thread
records: 10 records: 10
avg: 2961.90 avg: 12069.70
std: 71.96(2.43%) std: 186.68(1.55%)

max:	3070.00			    max:   12385.00
min:	2796.00			    min:   11746.00

2 thread
records: 10 records: 10
avg: 5020.00 avg: 17827.00
std: 264.87(5.28%) std: 358.52(2.01%)

max:	5244.00			    max:   18760.00
min:	4251.00			    min:   17382.00

4 thread
records: 10 records: 10

avg:	8988.80			    avg:   27930.80
std:	1175.33(13.08%)		    std:    3317.33(11.88%)
max:	9508.00			    max:   30879.00
min:	5477.00			    min:   21024.00

8 thread
records: 10 records: 10
avg: 13036.50 avg: 33739.40
std: 170.67(1.31%) std: 5146.22(15.25%)

max:   13371.00			    max:   40572.00
min:   12785.00			    min:   24088.00

16 thread
records: 10 records: 10
avg: 11092.40 avg: 31424.20
std: 710.60(6.41%) std: 3763.89(11.98%)
max: 12446.00 max: 36635.00
min: 9949.00 min: 25669.00

Quoted 8 lines

32 thread
records: 10 records: 10
avg: 11067.00 avg: 34495.80
std: 971.06(8.77%) std: 2721.36(7.89%)
max: 12010.00 max: 38598.00
min: 9002.00 min: 30636.00

In summary, MADV_FREE is about much faster than MADV_DONTNEED.

The MADV_FREE is discussed for a while, it probably is too late to propose something new, but we had the new idea (from Ben Maurer, CCed) recently and think it's better. Our target is still jemalloc.

Compared to MADV_DONTNEED, MADV_FREE's lazy memory free is a huge win to reduce page fault. But there is one issue remaining, the TLB flush. Both MADV_DONTNEED and MADV_FREE do TLB flush. TLB flush overhead is quite big in contemporary multi-thread applications. In our production workload, we observed 80% CPU spending on TLB flush triggered by jemalloc madvise(MADV_DONTNEED) sometimes. We haven't tested MADV_FREE yet, but the result should be similar. It's hard to avoid the TLB flush issue with MADV_FREE, because it helps avoid data corruption.

The new proposal tries to fix the TLB issue. We introduce two madvise verbs:

MARK_FREE. Userspace notifies kernel the memory range can be discarded. Kernel just records the range in current stage. Should memory pressure happen, page reclaim can free the memory directly regardless the pte state.

MARK_NOFREE. Userspace notifies kernel the memory range will be reused soon. Kernel deletes the record and prevents page reclaim discards the memory. If the memory isn't reclaimed, userspace will access the old memory, otherwise do normal page fault handling.

The point is to let userspace notify kernel if memory can be discarded, instead of depending on pte dirty bit used by MADV_FREE. With these, no TLB flush is required till page reclaim actually frees the memory (page reclaim need do the TLB flush for MADV_FREE too). It still preserves the lazy memory free merit of MADV_FREE.

Quoted 5 lines

Compared to MADV_FREE, reusing memory with the new proposal isn't transparent, eg must call MARK_NOFREE. But it's easy to utilize the new API in jemalloc.

We don't have code to backup this yet, sorry. We'd like to discuss it if it makes sense.

It's really what volatile range did.
John Stultz and me tried it for a *long* time but it had lots of troubles. It's really hard to write it down in my time due to really long history and even I forgot lots of detail(ie, dead brain).
Please search volatile ranges in google.
Finally, people in LSF/MM suggested MADV_FREE to help anonymous page side rather than stucking hich prevent useful feature. :(

Compared to MADV_DONTNEED, MADV_FREE's lazy memory free is a huge win to reduce page fault. But there is one issue remaining, the TLB flush. Both MADV_DONTNEED and MADV_FREE do TLB flush. TLB flush overhead is quite big in contemporary multi-thread applications. In our production workload, we observed 80% CPU spending on TLB flush triggered by jemalloc madvise(MADV_DONTNEED) sometimes. We haven't tested MADV_FREE yet, but the result should be similar. It's hard to avoid the TLB flush issue with MADV_FREE, because it helps avoid data corruption.

The new proposal tries to fix the TLB issue. We introduce two madvise verbs:

MARK_FREE. Userspace notifies kernel the memory range can be discarded. Kernel just records the range in current stage. Should memory pressure happen, page reclaim can free the memory directly regardless the pte state.

MARK_NOFREE. Userspace notifies kernel the memory range will be reused soon. Kernel deletes the record and prevents page reclaim discards the memory. If the memory isn't reclaimed, userspace will access the old memory, otherwise do normal page fault handling.

The point is to let userspace notify kernel if memory can be discarded, instead of depending on pte dirty bit used by MADV_FREE. With these, no TLB flush is required till page reclaim actually frees the memory (page reclaim need do the TLB flush for MADV_FREE too). It still preserves the lazy memory free merit of MADV_FREE.

Compared to MADV_FREE, reusing memory with the new proposal isn't transparent, eg must call MARK_NOFREE. But it's easy to utilize the new API in jemalloc.

We don't have code to backup this yet, sorry. We'd like to discuss it if it makes sense.

MADV_FREE is on linux-next so long time. The reason was two, I think.

1. MADV_FREE code on reclaim path was really mess.

Quoted 3 lines · Minchan Kim

MADV_FREE is on linux-next so long time. The reason was two, I think.

1. MADV_FREE code on reclaim path was really mess.

Could you explain what MADV_FREE does?

Comment in code says 'free the page only when there's memory pressure'. So I mark my caches MADV_FREE, no memory pressure, I can keep using it? And if there's memory pressure, what happens? I get zeros? SIGSEGV?