Skip to contentSkip to conversation

Support vrange for anonymous page

RFC In review Minchan Kim 7 participants 33 messages Mar 12, 2013 – Apr 16, 2013

Subsystems (15)
lore
Share & tools
lore
#0 lore raw

v7 cover Support vrange for anonymous page

First of all, let's define the term.

Quoted 1 line

From now on, I'd like to call it as vrange(a.k.a volatile range)

for anonymous page. If you have a better name in mind, please suggest.

This version is still *RFC* because it's just quick prototype so it doesn't support THP/HugeTLB/KSM and even couldn't build on !x86. Before further sorting out issues, I'd like to post current direction and discuss it. Of course, I'd like to extend this discussion in comming LSF/MM.

In this version, I changed lots of thing, expecially removed vma-based approach because it needs write-side lock for mmap_sem, which will drop performance in mutli-threaded big SMP system, KOSAKI pointed out. And vma-based approach is hard to meet requirement of new system call by John Stultz's suggested semantic for consistent purged handling.
(http://linux-kernel.2935.n7.nabble.com/RFC-v5-0-8-Support-volatile-for-anonymous-range-tt575773.html#none)

I tested this patchset with modified jemalloc allocator which was leaded by Jason Evans(jemalloc author) who was interest in this feature and was happy to port his allocator to use new system call. Super Thanks Jason!

The benchmark for test is ebizzy. It have been used for testing the allocator performance so it's good for me. Again, thanks for recommending the benchmark, Jason.
(http://people.freebsd.org/~kris/scaling/ebizzy.html)

The result is good on my machine (12 CPU, 1.2GHz, DRAM 2G)

ebizzy -S 20

jemalloc-vanilla: 52389 records/sec
jemalloc-vrange: 203414 records/sec

ebizzy -S 20 with background memory pressure

jemalloc-vanilla: 40746 records/sec
jemalloc-vrange: 174910 records/sec

And it's much improved on KVM virtual machine.

This patchset is based on v3.9-rc2

- What's the sys_vrange(addr, length, mode, behavior)?

It's a hint that user deliver to kernel so kernel can *discard* pages in a range anytime. mode is one of VRANGE_VOLATILE and VRANGE_NOVOLATILE. VRANGE_NOVOLATILE is memory pin operation so kernel coudn't discard any pages any more while VRANGE_VOLATILE is memory unpin opeartion so kernel can discard pages in vrange anytime. At a moment, behavior is one of VRANGE_FULL and VRANGE PARTIAL. VRANGE_FULL tell kernel that once kernel decide to discard page in a vrange, please, discard all of pages in a vrange selected by victim vrange. VRANGE_PARTIAL tell kernel that please discard of some pages in a vrange. But now I didn't implemented VRANGE_PARTIAL handling yet.

- What happens if user access page(ie, virtual address) discarded by kernel?

The user can encounter SIGBUS.

- What should user do for avoding SIGBUS?
He should call vrange(addr, length, VRANGE_NOVOLATILE, mode) before accessing the range which was called
vrange(addr, length, VRANGE_VOLATILE, mode)

- What happens if user access page(ie, virtual address) doesn't discarded by kernel?

The user can see vaild data which was there before calling
vrange(., VRANGE_VOLATILE) without page fault.

- What's different with madvise(DONTNEED)?

System call semantic

DONTNEED makes sure user always can see zero-fill pages after he calls madvise while vrange can see data or encounter SIGBUS.

Internal implementation

The madvise(DONTNEED) should zap all mapped pages in range so overhead is increased linearly with the number of mapped pages. Even, if user access zapped pages as write mode, page fault + page allocation + memset should be happened.

The vrange just register a address range instead of zapping all of pte n the vma so it doesn't touch ptes any more.

- What's the benefit compared to DONTNEED?

1. The system call overhead is smaller because vrange just registers a range using interval tree instead of zapping all the page in a range so overhead should be really cheap.

2. It has a chance to eliminate overheads (ex, zapping pte + page fault
+ page allocation + memset(PAGE_SIZE)) if memory pressure isn't severe.

3. It has a potential to zap all ptes and free the pages if memory pressure is severe so discard scanning overhead could be smaller - TODO

- What's for targetting?

Firstly, user-space allocator like ptmalloc, jemalloc or heap management of virtual machine like Dalvik. Also, it comes in handy for embedded which doesn't have swap device so they can't reclaim anonymous pages. By discarding instead of swapout, it could be used in the non-swap system.

Changelog from v6 - There are many changes.
* Remove vma-based approach
* Change system call semantic
* Add more meaningful experiment

Changelog from v5 - There are many changes.

* Support CONFIG_VOLATILE_PAGE
* Working with THP/KSM
* Remove vma hacking logic in m[no]volatile system call
* Discard page without swap cache
* Kswapd discard volatile page so we can discard volatile pages although we don't have swap.

Changelog from v4

* Add new system call mvolatile/mnovolatile
* Add sigbus when user try to access volatile range
* Rebased on v3.7
* Applied bug fix from John Stultz, Thanks!

Changelog from v3

* Removing madvise(addr, length, MADV_NOVOLATILE).
* add vmstat about the number of discarded volatile pages
* discard volatile pages without promotion in reclaim path

Minchan Kim (11):
vrange: enable generic interval tree
add vrange basic data structure and functions
add new system call vrange(2)
add proc/pid/vrange information
Add purge operation
send SIGBUS when user try to access purged page
keep mm_struct to vrange when system call context
add LRU handling for victim vrange
Get rid of depenceny that all pages is from a zone in shrink_page_list Purging vrange pages without swap
add purged page information in vmstat

 arch/x86/include/asm/pgtable_types.h   |   2 +
 arch/x86/syscalls/syscall_64.tbl       |   1 +
 fs/proc/base.c                         |   1 +
 fs/proc/internal.h                     |   6 +
 fs/proc/task_mmu.c                     | 129 ++++++
 include/asm-generic/pgtable.h          |  11 +
 include/linux/mm_types.h               |   5 +
 include/linux/rmap.h                   |  15 +-
 include/linux/swap.h                   |   1 +
 include/linux/vm_event_item.h          |   4 +
 include/linux/vrange.h                 |  59 +++
 include/uapi/asm-generic/mman-common.h |   5 +
 init/main.c                            |   2 +
 kernel/fork.c                          |   3 +
 lib/Makefile                           |   2 +-
 mm/Makefile                            |   2 +-
 mm/ksm.c                               |   2 +-
 mm/memory.c                            |  24 +-
 mm/rmap.c                              |  23 +-
 mm/swapfile.c                          |  36 ++
 mm/vmscan.c                            |  74 +++-
 mm/vmstat.c                            |   4 +
 mm/vrange.c                            | 754 +++++++++++++++++++++++++++++++++
 23 files changed, 1143 insertions(+), 22 deletions(-)
 create mode 100644 include/linux/vrange.h
 create mode 100644 mm/vrange.c
Signature · 7 lines
1.8.1.1

--
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>
#1 lore raw

RFC v7 1/11 vrange: enable generic interval tree

Anon vrange patch will use generic interval tree so let's enable it.

Cc Michel Lespinasse <[email protected]>
---
 lib/Makefile | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
lib/Makefile +1 -1
index d7946ff..17986fb 100644
@@ -13,7 +13,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \
 	 proportions.o flex_proportions.o prio_heap.o ratelimit.o show_mem.o \
 	 is_single_threaded.o plist.o decompress.o kobject_uevent.o \
-	 earlycpio.o
+	 earlycpio.o interval_tree.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
Signature · 7 lines
1.8.1.1

--
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>
#2 lore raw

RFC v7 2/11 add vrange basic data structure and functions

In reply to Minchan Kim

This patch adds vrange data structure(interval tree) and related functions.

The vrange uses generic interval tree as main data structure because it handles address range so generic interval tree fits well for the purpose.

The add_vrange/remove_vrange are core functions for system call will be introdcued next patch.

1. add_vrange inserts new address range into interval tree. If new address range crosses over existing volatile range, existing volatile range will be expanded to cover new range. Then, if existing volatile range has purged state, new range will have a purged state.
It's not good and we need more fine-grained purged state handling in a vrange(TODO)

If new address range is inside existing range, we ignore it

2. remove_vrange removes address range
Then, return a purged state of the address ranges.

This patch copied some part from John Stultz's work but different semantic.

---
 include/linux/mm_types.h |   5 ++
 include/linux/vrange.h   |  45 ++++++++++++++
 init/main.c              |   2 +
 kernel/fork.c            |   3 +
 mm/Makefile              |   2 +-
 mm/vrange.c              | 157 +++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 213 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/vrange.h
 create mode 100644 mm/vrange.c
include/linux/mm_types.h +5 -0
index ace9a5f..080bf74 100644
@@ -13,6 +13,7 @@
 #include <linux/page-debug-flags.h>
 #include <linux/uprobes.h>
 #include <linux/page-flags-layout.h>
+#include <linux/mutex.h>
 #include <asm/page.h>
 #include <asm/mmu.h>
 
@@ -351,6 +352,10 @@ struct mm_struct {
 						 */
 
 
+#ifdef CONFIG_MMU
+	struct rb_root v_rb;		/* vrange rb tree */
+	struct mutex v_lock;		/* Protect v_rb */
+#endif
 	unsigned long hiwater_rss;	/* High-watermark of RSS usage */
 	unsigned long hiwater_vm;	/* High-water virtual memory usage */
 
include/linux/vrange.h new file +45 -0

45 lines not on this page · raw message

init/main.c +2 -0
index 63534a1..0b9e0b5 100644
@@ -72,6 +72,7 @@
 #include <linux/ptrace.h>
 #include <linux/blkdev.h>
 #include <linux/elevator.h>
+#include <linux/vrange.h>
 
 #include <asm/io.h>
 #include <asm/bugs.h>
@@ -605,6 +606,7 @@ asmlinkage void __init start_kernel(void)
 	calibrate_delay();
 	pidmap_init();
 	anon_vma_init();
+	vrange_init();
 #ifdef CONFIG_X86
 	if (efi_enabled(EFI_RUNTIME_SERVICES))
 		efi_enter_virtual_mode();
kernel/fork.c +3 -0
index 8d932b1..e3aa120 100644
@@ -70,6 +70,7 @@
 #include <linux/khugepaged.h>
 #include <linux/signalfd.h>
 #include <linux/uprobes.h>
+#include <linux/vrange.h>
 
 #include <asm/pgtable.h>
 #include <asm/pgalloc.h>
@@ -541,6 +542,7 @@ static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p)
 	spin_lock_init(&mm->page_table_lock);
 	mm->free_area_cache = TASK_UNMAPPED_BASE;
 	mm->cached_hole_size = ~0UL;
+	mm_init_vrange(mm);
 	mm_init_aio(mm);
 	mm_init_owner(mm, p);
 
@@ -612,6 +614,7 @@ void mmput(struct mm_struct *mm)
 
 	if (atomic_dec_and_test(&mm->mm_users)) {
 		uprobe_clear_state(mm);
+		exit_vrange(mm);
 		exit_aio(mm);
 		ksm_exit(mm);
 		khugepaged_exit(mm); /* must run before exit_mmap */
mm/Makefile +1 -1
index 3a46287..a31235e 100644
@@ -5,7 +5,7 @@
 mmu-y			:= nommu.o
 mmu-$(CONFIG_MMU)	:= fremap.o highmem.o madvise.o memory.o mincore.o \
 			   mlock.o mmap.o mprotect.o mremap.o msync.o rmap.o \
-			   vmalloc.o pagewalk.o pgtable-generic.o
+			   vmalloc.o pagewalk.o pgtable-generic.o vrange.o
 
 ifdef CONFIG_CROSS_MEMORY_ATTACH
 mmu-$(CONFIG_MMU)	+= process_vm_access.o
mm/vrange.c new file +157 -0

157 lines not on this page · raw message

Signature · 7 lines
1.8.1.1

--
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>
#3 lore raw

RFC v7 3/11 add new system call vrange(2)

In reply to Minchan Kim

This patch adds new system call sys_vrange.

NAME
vrange - give pin/unpin hint for kernel to help reclaim.

SYNOPSIS

	int vrange(unsigned_long start, size_t length, int mode, int behavior);

DESCRIPTOIN
Applications can use vrange(2) to advise the kernel how it should handle paging I/O in this VM area. The idea is to help the kernel discard pages of vrange instead of reclaiming when memory pressure happens. It means kernel doesn't discard any pages of vrange if ther is no memory pressure.

mode:

VRANGE_VOLATILE
hint to kernel so VM can discard in vrange pages when memory pressure happens.
VRANGE_NOVOLATILE
hint to kernel so VM doesn't discard vrange pages any more.

behavior:

VRANGE_FULL_MODE
Once VM start to discard pages, it discards all pages in a vrange.
VRANGE_PARTIAL_MODE
VM discards some pages of all vranges by round-robin return values:

If user try to access purged memory without VRANGE_NOVOLATILE call, he can encounter SIGBUS if the page was discarded by kernel.

RETURN VALUE
On success vrange returns zero or 1. zero means kernel doesn't discard any pages on [start, start + length). 1 means kernel did discard one of pages on the range.

ERRORS
EINVAL This error can occur for the following reasons:

* The value length is negative.
* addr is not page-aligned
* mode or behavior are not a vaild value.

ENOMEM Not enough memory

---
 arch/x86/syscalls/syscall_64.tbl       |  1 +
 include/uapi/asm-generic/mman-common.h |  5 +++
 mm/vrange.c                            | 58 ++++++++++++++++++++++++++++++++++
 3 files changed, 64 insertions(+)
arch/x86/syscalls/syscall_64.tbl +1 -0
index 38ae65d..dc332bd 100644
@@ -320,6 +320,7 @@
 311	64	process_vm_writev	sys_process_vm_writev
 312	common	kcmp			sys_kcmp
 313	common	finit_module		sys_finit_module
+314	common	vrange			sys_vrange
 
 #
 # x32-specific system call numbers start at 512 to avoid cache impact
include/uapi/asm-generic/mman-common.h +5 -0
index 4164529..736696e 100644
@@ -66,4 +66,9 @@
 #define MAP_HUGE_SHIFT	26
 #define MAP_HUGE_MASK	0x3f
 
+#define VRANGE_VOLATILE	0	/* unpin all pages so VM can discard them */
+#define VRANGE_NOVOLATILE	1	/* pin all pages so VM can't discard them */
+
+#define VRANGE_FULL_MODE	0	/* discard all pages of the range */
+#define VRANGE_PARTIAL_MODE	1	/* discard a few pages of the range */
 #endif /* __ASM_GENERIC_MMAN_COMMON_H */
mm/vrange.c +58 -0

67 lines not on this page · raw message

Signature · 7 lines
1.8.1.1

--
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>
#4 lore raw

RFC v7 4/11 add proc/pid/vrange information

In reply to Minchan Kim

Add vrange per perocess information.
It would help debugging.

---
 fs/proc/base.c     |   1 +
 fs/proc/internal.h |   6 +++
 fs/proc/task_mmu.c | 129 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 mm/vrange.c        |   2 +-
 4 files changed, 137 insertions(+), 1 deletion(-)
fs/proc/base.c +1 -0
index 69078c7..c1a8506 100644
@@ -2523,6 +2523,7 @@ static const struct pid_entry tgid_base_stuff[] = {
 	ONE("stat",       S_IRUGO, proc_tgid_stat),
 	ONE("statm",      S_IRUGO, proc_pid_statm),
 	REG("maps",       S_IRUGO, proc_pid_maps_operations),
+	REG("vrange",     S_IRUGO, proc_pid_vrange_operations),
 #ifdef CONFIG_NUMA
 	REG("numa_maps",  S_IRUGO, proc_pid_numa_maps_operations),
 #endif
fs/proc/internal.h +6 -0
index 85ff3a4..0584035 100644
@@ -60,6 +60,7 @@ extern loff_t mem_lseek(struct file *file, loff_t offset, int orig);
 
 extern const struct file_operations proc_tid_children_operations;
 extern const struct file_operations proc_pid_maps_operations;
+extern const struct file_operations proc_pid_vrange_operations;
 extern const struct file_operations proc_tid_maps_operations;
 extern const struct file_operations proc_pid_numa_maps_operations;
 extern const struct file_operations proc_tid_numa_maps_operations;
@@ -82,6 +83,11 @@ struct proc_maps_private {
 #endif
 };
 
+struct proc_vrange_private {
+	struct pid *pid;
+	struct task_struct *task;
+};
+
 void proc_init_inodecache(void);
 
 static inline struct pid *proc_pid(struct inode *inode)
fs/proc/task_mmu.c +129 -0

141 lines not on this page · raw message

mm/vrange.c +1 -1
index 2f77d89..f8b6f0e 100644
@@ -199,7 +199,7 @@ SYSCALL_DEFINE4(vrange, unsigned long, start,
 	if (!len)
 		goto out;
 
-	end = start  len;
+	end = start + len;
 	if (end < start)
 		goto out;
 
Signature · 7 lines
1.8.1.1

--
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>
#5 lore raw

RFC v7 5/11 Add purge operation

In reply to Minchan Kim

This patch adds discarding function part.
Logic is following as.

1. Memory pressure happens
2. VM start to reclaim anonymous page if system has a swap device
3. Check the page is in volatile range.
4. If so, zap the page from the process's page table.
(By sematic vrange(2), we should mark it with another one to
make page fault when you try to access the address. It will be introduced later patch)
5. If page is unmapped from all processes, discard it instead of swapping.

---
 include/linux/rmap.h   |  12 ++-
 include/linux/swap.h   |   1 +
 include/linux/vrange.h |   9 ++
 mm/ksm.c               |   2 +-
 mm/rmap.c              |  23 +++--
 mm/swapfile.c          |  36 ++++++++
 mm/vmscan.c            |  16 +++-
 mm/vrange.c            | 235 +++++++++++++++++++++++++++++++++++++++++++++++++
 8 files changed, 320 insertions(+), 14 deletions(-)
include/linux/rmap.h +9 -3
index 6dacb93..6432dfb 100644
@@ -83,6 +83,8 @@ enum ttu_flags {
 };
 
 #ifdef CONFIG_MMU
+unsigned long vma_address(struct page *page, struct vm_area_struct *vma);
+
 static inline void get_anon_vma(struct anon_vma *anon_vma)
 {
 	atomic_inc(&anon_vma->refcount);
@@ -182,9 +184,11 @@ static inline void page_dup_rmap(struct page *page)
  * Called from mm/vmscan.c to handle paging out
  */
 int page_referenced(struct page *, int is_locked,
-			struct mem_cgroup *memcg, unsigned long *vm_flags);
+			struct mem_cgroup *memcg, unsigned long *vm_flags,
+			int *is_vrange);
 int page_referenced_one(struct page *, struct vm_area_struct *,
-	unsigned long address, unsigned int *mapcount, unsigned long *vm_flags);
+	unsigned long address, unsigned int *mapcount, unsigned long *vm_flags,
+	int *is_vrange);
 
 #define TTU_ACTION(x) ((x) & TTU_ACTION_MASK)
 
@@ -249,9 +253,11 @@ int rmap_walk(struct page *page, int (*rmap_one)(struct page *,
 
 static inline int page_referenced(struct page *page, int is_locked,
 				  struct mem_cgroup *memcg,
-				  unsigned long *vm_flags)
+				  unsigned long *vm_flags,
+				  int *is_vrange)
 {
 	*vm_flags = 0;
+	*is_vrange = 0;
 	return 0;
 }
 
include/linux/swap.h +1 -0
index 2818a12..bf56fb4 100644
@@ -379,6 +379,7 @@ extern int swap_duplicate(swp_entry_t);
 extern int swapcache_prepare(swp_entry_t);
 extern void swap_free(swp_entry_t);
 extern void swapcache_free(swp_entry_t, struct page *page);
+extern int __free_swap_and_cache(swp_entry_t);
 extern int free_swap_and_cache(swp_entry_t);
 extern int swap_type_of(dev_t, sector_t, struct block_device **);
 extern unsigned int count_swap_pages(int, int);
include/linux/vrange.h +9 -0
index 74b5e37..eb3f941 100644
@@ -5,6 +5,9 @@
 #include <linux/interval_tree.h>
 #include <linux/mm.h>
 
+/* To protect race with forker */
+static DECLARE_RWSEM(vrange_fork_lock);
+
 struct vrange {
 	struct interval_tree_node node;
 	bool purged;
@@ -34,6 +37,9 @@ static inline void vrange_unlock(struct mm_struct *mm)
 
 extern void exit_vrange(struct mm_struct *mm);
 void vrange_init(void);
+int discard_vpage(struct page *page);
+bool vrange_address(struct mm_struct *mm, unsigned long start,
+			unsigned long end);
 
 #else
 
@@ -41,5 +47,8 @@ static inline void vrange_init(void) {};
 static inline void mm_init_vrange(struct mm_struct *mm) {};
 static inline void exit_vrange(struct mm_struct *mm);
 
+static inline bool vrange_address(struct mm_struct *mm, unsigned long start,
+		unsigned long end) { return false; };
+static inline int discard_vpage(struct page *page) { return 0 };
 #endif
 #endif /* _LINIUX_VRANGE_H */
mm/ksm.c +1 -1
index b6afe0c..debc20c 100644
@@ -1932,7 +1932,7 @@ again:
 				continue;
 
 			referenced += page_referenced_one(page, vma,
-				rmap_item->address, &mapcount, vm_flags);
+				rmap_item->address, &mapcount, vm_flags, NULL);
 			if (!search_new_forks || !mapcount)
 				break;
 		}
mm/rmap.c +15 -8
index 807c96b..90cf51c 100644
@@ -57,6 +57,8 @@
 #include <linux/migrate.h>
 #include <linux/hugetlb.h>
 #include <linux/backing-dev.h>
+#include <linux/vrange.h>
+#include <linux/rmap.h>
 
 #include <asm/tlbflush.h>
 
@@ -523,8 +525,7 @@ __vma_address(struct page *page, struct vm_area_struct *vma)
 	return vma->vm_start + ((pgoff - vma->vm_pgoff) << PAGE_SHIFT);
 }
 
-inline unsigned long
-vma_address(struct page *page, struct vm_area_struct *vma)
+unsigned long vma_address(struct page *page, struct vm_area_struct *vma)
 {
 	unsigned long address = __vma_address(page, vma);
 
@@ -662,7 +663,7 @@ int page_mapped_in_vma(struct page *page, struct vm_area_struct *vma)
  */
 int page_referenced_one(struct page *page, struct vm_area_struct *vma,
 			unsigned long address, unsigned int *mapcount,
-			unsigned long *vm_flags)
+			unsigned long *vm_flags, int *is_vrange)
 {
 	struct mm_struct *mm = vma->vm_mm;
 	int referenced = 0;
@@ -724,6 +725,9 @@ int page_referenced_one(struct page *page, struct vm_area_struct *vma,
 				referenced++;
 		}
 		pte_unmap_unlock(pte, ptl);
+		if (is_vrange &&
+			vrange_address(mm, address, address + PAGE_SIZE -1))
+			*is_vrange = 1;
 	}
 
 	(*mapcount)--;
@@ -736,7 +740,8 @@ out:
 
 static int page_referenced_anon(struct page *page,
 				struct mem_cgroup *memcg,
-				unsigned long *vm_flags)
+				unsigned long *vm_flags,
+				int *is_vrange)
 {
 	unsigned int mapcount;
 	struct anon_vma *anon_vma;
@@ -761,7 +766,7 @@ static int page_referenced_anon(struct page *page,
 		if (memcg && !mm_match_cgroup(vma->vm_mm, memcg))
 			continue;
 		referenced += page_referenced_one(page, vma, address,
-						  &mapcount, vm_flags);
+					&mapcount, vm_flags, is_vrange);
 		if (!mapcount)
 			break;
 	}
@@ -826,7 +831,7 @@ static int page_referenced_file(struct page *page,
 		if (memcg && !mm_match_cgroup(vma->vm_mm, memcg))
 			continue;
 		referenced += page_referenced_one(page, vma, address,
-						  &mapcount, vm_flags);
+						  &mapcount, vm_flags, NULL);
 		if (!mapcount)
 			break;
 	}
@@ -841,6 +846,7 @@ static int page_referenced_file(struct page *page,
  * @is_locked: caller holds lock on the page
  * @memcg: target memory cgroup
  * @vm_flags: collect encountered vma->vm_flags who actually referenced the page
+ * @is_vrange: the page in vrange of some process
  *
  * Quick test_and_clear_referenced for all mappings to a page,
  * returns the number of ptes which referenced the page.
@@ -848,7 +854,8 @@ static int page_referenced_file(struct page *page,
 int page_referenced(struct page *page,
 		    int is_locked,
 		    struct mem_cgroup *memcg,
-		    unsigned long *vm_flags)
+		    unsigned long *vm_flags,
+		    int *is_vrange)
 {
 	int referenced = 0;
 	int we_locked = 0;
@@ -867,7 +874,7 @@ int page_referenced(struct page *page,
 								vm_flags);
 		else if (PageAnon(page))
 			referenced += page_referenced_anon(page, memcg,
-								vm_flags);
+							vm_flags, is_vrange);
 		else if (page->mapping)
 			referenced += page_referenced_file(page, memcg,
 								vm_flags);
mm/swapfile.c +36 -0
index a1f7772..962024c 100644
@@ -734,6 +734,42 @@ int try_to_free_swap(struct page *page)
 }
 
 /*
+ * It's almost same with free_swap_and_cache except page is already
+ * locked.
+ */
+int __free_swap_and_cache(swp_entry_t entry)
+{
+	struct swap_info_struct *p;
+	struct page *page = NULL;
+
+	if (non_swap_entry(entry))
+		return 1;
+
+	p = swap_info_get(entry);
+	if (p) {
+		if (swap_entry_free(p, entry, 1) == SWAP_HAS_CACHE) {
+			page = find_get_page(swap_address_space(entry),
+						entry.val);
+		}
+		spin_unlock(&swap_lock);
+	}
+
+	if (page) {
+		/*
+		 * Not mapped elsewhere, or swap space full? Free it!
+		 * Also recheck PageSwapCache now page is locked (above).
+		 */
+		if (PageSwapCache(page) && !PageWriteback(page) &&
+				(!page_mapped(page) || vm_swap_full())) {
+			delete_from_swap_cache(page);
+			SetPageDirty(page);
+		}
+		page_cache_release(page);
+	}
+	return p != NULL;
+}
+
+/*
  * Free the swap entry like above, but also try to
  * free the page cache entry if it is the last user.
  */
mm/vmscan.c +14 -2
index 88c5fed..6ba4e8ea 100644
@@ -42,6 +42,7 @@
 #include <linux/sysctl.h>
 #include <linux/oom.h>
 #include <linux/prefetch.h>
+#include <linux/vrange.h>
 
 #include <asm/tlbflush.h>
 #include <asm/div64.h>
@@ -610,6 +611,7 @@ enum page_references {
 	PAGEREF_RECLAIM,
 	PAGEREF_RECLAIM_CLEAN,
 	PAGEREF_KEEP,
+	PAGEREF_DISCARD,
 	PAGEREF_ACTIVATE,
 };
 
@@ -618,9 +620,10 @@ static enum page_references page_check_references(struct page *page,
 {
 	int referenced_ptes, referenced_page;
 	unsigned long vm_flags;
+	int is_vrange = 0;
 
 	referenced_ptes = page_referenced(page, 1, sc->target_mem_cgroup,
-					  &vm_flags);
+					  &vm_flags, &is_vrange);
 	referenced_page = TestClearPageReferenced(page);
 
 	/*
@@ -630,6 +633,12 @@ static enum page_references page_check_references(struct page *page,
 	if (vm_flags & VM_LOCKED)
 		return PAGEREF_RECLAIM;
 
+	/*
+	 * Bail out if the page is in vrange and try to discard.
+	 */
+	if (is_vrange)
+		return PAGEREF_DISCARD;
+
 	if (referenced_ptes) {
 		if (PageSwapBacked(page))
 			return PAGEREF_ACTIVATE;
@@ -768,6 +777,9 @@ static unsigned long shrink_page_list(struct list_head *page_list,
 			goto activate_locked;
 		case PAGEREF_KEEP:
 			goto keep_locked;
+		case PAGEREF_DISCARD:
+			if (discard_vpage(page))
+				goto free_it;
 		case PAGEREF_RECLAIM:
 		case PAGEREF_RECLAIM_CLEAN:
 			; /* try to reclaim the page below */
@@ -1496,7 +1508,7 @@ static void shrink_active_list(unsigned long nr_to_scan,
 		}
 
 		if (page_referenced(page, 0, sc->target_mem_cgroup,
-				    &vm_flags)) {
+				    &vm_flags, NULL)) {
 			nr_rotated += hpage_nr_pages(page);
 			/*
 			 * Identify referenced, file-backed active pages and
mm/vrange.c +235 -0

244 lines not on this page · raw message

Signature · 7 lines
1.8.1.1

--
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>
#6 lore raw

RFC v7 6/11 send SIGBUS when user try to access purged page

In reply to Minchan Kim

By vrange(2) semantic, user should see SIGBUG if he try to access purged page without vrange(...VRANGE_NOVOLATILE).

This patch implements it.

I reused PSE bit for quick prototype without enough considering so need time to see what's empty bit and I am surely missing many places to handle vrange pte bit. I should investigate all of pte handling places, especially pte_none case. TODO

---
 arch/x86/include/asm/pgtable_types.h |  2 ++
 include/asm-generic/pgtable.h        | 11 +++++++++++
 include/linux/vrange.h               |  2 ++
 mm/memory.c                          | 23 +++++++++++++++++++++--
 mm/vrange.c                          | 26 ++++++++++++++++++++++++--
 5 files changed, 60 insertions(+), 4 deletions(-)
arch/x86/include/asm/pgtable_types.h +2 -0
index 567b5d0..8c5163f 100644
@@ -64,6 +64,8 @@
 #define _PAGE_FILE	(_AT(pteval_t, 1) << _PAGE_BIT_FILE)
 #define _PAGE_PROTNONE	(_AT(pteval_t, 1) << _PAGE_BIT_PROTNONE)
 
+#define _PAGE_VRANGE	_PAGE_BIT_PSE
+
 /*
  * _PAGE_NUMA indicates that this page will trigger a numa hinting
  * minor page fault to gather numa placement statistics (see
include/asm-generic/pgtable.h +11 -0
index bfd8768..1486d42 100644
@@ -469,6 +469,17 @@ static inline unsigned long my_zero_pfn(unsigned long addr)
 
 #ifdef CONFIG_MMU
 
+static inline pte_t pte_mkvrange(pte_t pte)
+{
+	pte = pte_set_flags(pte, _PAGE_VRANGE);
+	return pte_clear_flags(pte, _PAGE_PRESENT);
+}
+
+static inline int pte_vrange(pte_t pte)
+{
+	return ((pte_flags(pte) | _PAGE_PRESENT) == _PAGE_VRANGE);
+}
+
 #ifndef CONFIG_TRANSPARENT_HUGEPAGE
 static inline int pmd_trans_huge(pmd_t pmd)
 {
include/linux/vrange.h +2 -0
index eb3f941..24ed4c1 100644
@@ -41,6 +41,8 @@ int discard_vpage(struct page *page);
 bool vrange_address(struct mm_struct *mm, unsigned long start,
 			unsigned long end);
 
+extern bool is_purged_vrange(struct mm_struct *mm, unsigned long address);
+
 #else
 
 static inline void vrange_init(void) {};
mm/memory.c +21 -2
index 494526a..cc369ab 100644
@@ -59,6 +59,7 @@
 #include <linux/gfp.h>
 #include <linux/migrate.h>
 #include <linux/string.h>
+#include <linux/vrange.h>
 
 #include <asm/io.h>
 #include <asm/pgalloc.h>
@@ -840,7 +841,7 @@ copy_one_pte(struct mm_struct *dst_mm, struct mm_struct *src_mm,
 
 	/* pte contains position in swap or file, so copy. */
 	if (unlikely(!pte_present(pte))) {
-		if (!pte_file(pte)) {
+		if (!pte_file(pte) && !pte_vrange(pte)) {
 			swp_entry_t entry = pte_to_swp_entry(pte);
 
 			if (swap_duplicate(entry) < 0)
@@ -1180,7 +1181,7 @@ again:
 		if (pte_file(ptent)) {
 			if (unlikely(!(vma->vm_flags & VM_NONLINEAR)))
 				print_bad_pte(vma, addr, ptent, NULL);
-		} else {
+		} else if (!pte_vrange(ptent)) {
 			swp_entry_t entry = pte_to_swp_entry(ptent);
 
 			if (!non_swap_entry(entry))
@@ -3663,9 +3664,27 @@ int handle_pte_fault(struct mm_struct *mm,
 					return do_linear_fault(mm, vma, address,
 						pte, pmd, flags, entry);
 			}
+anon:
 			return do_anonymous_page(mm, vma, address,
 						 pte, pmd, flags);
 		}
+
+		if (unlikely(pte_vrange(entry))) {
+			if (!is_purged_vrange(mm, address)) {
+				/* zap pte */
+				ptl = pte_lockptr(mm, pmd);
+				spin_lock(ptl);
+				if (unlikely(!pte_same(*pte, entry)))
+					goto unlock;
+				flush_cache_page(vma, address, pte_pfn(*pte));
+				ptep_clear_flush(vma, address, pte);
+				pte_unmap_unlock(pte, ptl);
+				goto anon;
+			}
+
+			return VM_FAULT_SIGBUS;
+		}
+
 		if (pte_file(entry))
 			return do_nonlinear_fault(mm, vma, address,
 					pte, pmd, flags, entry);
mm/vrange.c +24 -2
index 78aa252..89fcae4 100644
@@ -343,7 +343,9 @@ int try_to_discard_one(struct page *page, struct vm_area_struct *vma,
 
 	present = pte_present(*pte);
 	flush_cache_page(vma, address, page_to_pfn(page));
-	pteval = ptep_clear_flush(vma, address, pte);
+
+	ptep_clear_flush(vma, address, pte);
+	pteval = pte_mkvrange(*pte);
 
 	update_hiwater_rss(mm);
 	dec_mm_counter(mm, MM_ANONPAGES);
@@ -357,10 +359,12 @@ int try_to_discard_one(struct page *page, struct vm_area_struct *vma,
 			BUG_ON(1);
 	}
 
+	set_pte_at(mm, address, pte, pteval);
+	__vrange_purge(mm, address, address + PAGE_SIZE -1);
 	pte_unmap_unlock(pte, ptl);
 	mmu_notifier_invalidate_page(mm, address);
+	vrange_unlock(mm);
 	ret = 1;
-	__vrange_purge(mm, address, address + PAGE_SIZE -1);
 out:
 	return ret;
 }
@@ -448,3 +452,21 @@ int discard_vpage(struct page *page)
 
 	return 0;
 }
+
+bool is_purged_vrange(struct mm_struct *mm, unsigned long address)
+{
+	struct rb_root *root = &mm->v_rb;
+	struct interval_tree_node *node;
+	struct vrange *range;
+	bool ret = false;
+
+	vrange_lock(mm);
+	node = interval_tree_iter_first(root, address, address + PAGE_SIZE - 1);
+	if (node) {
+		range = container_of(node, struct vrange, node);
+		if (range->purged)
+			ret = true;
+	}
+	vrange_unlock(mm);
+	return ret;
+}
Signature · 7 lines
1.8.1.1

--
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>
#7 lore raw

RFC v7 7/11 keep mm_struct to vrange when system call context

In reply to Minchan Kim

We need mm_struct for discarding vrange pages in kswapd context. It's a preparatoin for it.

---
 include/linux/vrange.h |  1 +
 mm/vrange.c            | 20 +++++++++++---------
 2 files changed, 12 insertions(+), 9 deletions(-)
include/linux/vrange.h +1 -0
index 24ed4c1..5238a67 100644
@@ -11,6 +11,7 @@ static DECLARE_RWSEM(vrange_fork_lock);
 struct vrange {
 	struct interval_tree_node node;
 	bool purged;
+	struct mm_struct *mm;
 };
 
 #define vrange_entry(ptr) \
mm/vrange.c +11 -9
index 89fcae4..f4c1d04 100644
@@ -29,8 +29,9 @@ static inline void __set_vrange(struct vrange *range,
 }
 
 static void __add_range(struct vrange *range,
-				struct rb_root *root)
+			struct rb_root *root, struct mm_struct *mm)
 {
+	range->mm = mm;
 	interval_tree_insert(&range->node, root);
 }
 
@@ -52,11 +53,12 @@ static void free_vrange(struct vrange *range)
 
 static inline void range_resize(struct rb_root *root,
 		struct vrange *range,
-		unsigned long start, unsigned long end)
+		unsigned long start, unsigned long end,
+		struct mm_struct *mm)
 {
 	__remove_range(range, root);
 	__set_vrange(range, start, end);
-	__add_range(range, root);
+	__add_range(range, root, mm);
 }
 
 int add_vrange(struct mm_struct *mm,
@@ -95,8 +97,7 @@ int add_vrange(struct mm_struct *mm,
 
 	__set_vrange(new_range, start, end);
 	new_range->purged = purged;
-
-	__add_range(new_range, root);
+	__add_range(new_range, root, mm);
 out:
 	vrange_unlock(mm);
 	return 0;
@@ -129,15 +130,16 @@ int remove_vrange(struct mm_struct *mm,
 			__remove_range(range, root);
 			free_vrange(range);
 		} else if (node->start >= start) {
-			range_resize(root, range, end, node->last);
+			range_resize(root, range, end, node->last, mm);
 		} else if (node->last <= end) {
-			range_resize(root, range, node->start, start);
+			range_resize(root, range, node->start, start, mm);
 		} else {
 			used_new = true;
 			__set_vrange(new_range, end, node->last);
 			new_range->purged = range->purged;
-			range_resize(root, range, node->start, start);
-			__add_range(new_range, root);
+			new_range->mm = mm;
+			range_resize(root, range, node->start, start, mm);
+			__add_range(new_range, root, mm);
 			break;
 		}
 
Signature · 7 lines
1.8.1.1

--
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>
#8 lore raw

RFC v7 8/11 add LRU handling for victim vrange

In reply to Minchan Kim

This patch adds LRU data structure for selecting victim vrange when memory pressure happens.

Basically, VM will select old vrange but if user try to access purged page recenlty, the vrange includes the page will be activated because page fault means one of them which user process will be killed or recover SIGBUS and continue the work. For latter case, we have to keep the vrange out of vicim selection.

I admit LRU might be not best but I can't imagine better idea so wanted to make it simple. I think user space can handle better with enough information so hope they handle it via mempressure notifier. Otherwise, if you have better idea, welcome!

---
 include/linux/vrange.h |  4 ++++
 mm/memory.c            |  1 +
 mm/vrange.c            | 48 +++++++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 52 insertions(+), 1 deletion(-)
include/linux/vrange.h +4 -0
index 5238a67..26db168 100644
@@ -12,6 +12,7 @@ struct vrange {
 	struct interval_tree_node node;
 	bool purged;
 	struct mm_struct *mm;
+	struct list_head lru; /* protected by lru_lock */
 };
 
 #define vrange_entry(ptr) \
@@ -44,6 +45,9 @@ bool vrange_address(struct mm_struct *mm, unsigned long start,
 
 extern bool is_purged_vrange(struct mm_struct *mm, unsigned long address);
 
+unsigned int discard_vrange_pages(struct zone *zone, int nr_to_discard);
+void lru_move_vrange_to_head(struct mm_struct *mm, unsigned long address);
+
 #else
 
 static inline void vrange_init(void) {};
mm/memory.c +1 -0
index cc369ab..3cb0633 100644
@@ -3671,6 +3671,7 @@ anon:
 
 		if (unlikely(pte_vrange(entry))) {
 			if (!is_purged_vrange(mm, address)) {
+				lru_move_vrange_to_head(mm, address);
 				/* zap pte */
 				ptl = pte_lockptr(mm, pmd);
 				spin_lock(ptl);
mm/vrange.c +47 -1

74 lines not on this page · raw message

Signature · 7 lines
1.8.1.1

--
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>
#9 lore raw

RFC v7 9/11 Get rid of depenceny that all pages is from a zone in shrink_page_list

In reply to Minchan Kim

Now shrink_page_list expect all pages come from a same zone but it's too limited to use it.

This patch removes the dependency and add may_discard in scan_control so next patch can use shrink_page_list with pages from multiple zonnes.

---
 mm/vmscan.c | 13 +++++++++++--
 1 file changed, 11 insertions(+), 2 deletions(-)
mm/vmscan.c +11 -2
index 6ba4e8ea..e36ee51 100644
@@ -77,6 +77,9 @@ struct scan_control {
 	/* Can pages be swapped as part of reclaim? */
 	int may_swap;
 
+	/* Discard pages in vrange */
+	int may_discard;
+
 	int order;
 
 	/* Scan (total_size >> priority) pages at once */
@@ -714,7 +717,8 @@ static unsigned long shrink_page_list(struct list_head *page_list,
 			goto keep;
 
 		VM_BUG_ON(PageActive(page));
-		VM_BUG_ON(page_zone(page) != zone);
+		if (zone)
+			VM_BUG_ON(page_zone(page) != zone);
 
 		sc->nr_scanned++;
 
@@ -785,6 +789,10 @@ static unsigned long shrink_page_list(struct list_head *page_list,
 			; /* try to reclaim the page below */
 		}
 
+		/* Fail to discard a page and returns a page to caller */
+		if (sc->may_discard)
+			goto keep_locked;
+				
 		/*
 		 * Anonymous process memory has backing store?
 		 * Try to allocate it some swap space here.
@@ -963,7 +971,8 @@ keep:
 	 * back off and wait for congestion to clear because further reclaim
 	 * will encounter the same problem
 	 */
-	if (nr_dirty && nr_dirty == nr_congested && global_reclaim(sc))
+	if (nr_dirty && nr_dirty == nr_congested && global_reclaim(sc) &&
+		zone)
 		zone_set_flag(zone, ZONE_CONGESTED);
 
 	free_hot_cold_page_list(&free_pages, 1);
Signature · 7 lines
1.8.1.1

--
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>
#10 lore raw

RFC v7 10/11 Purging vrange pages without swap

In reply to Minchan Kim

Now one of problem in vrange is VM reclaim anonymous pages if only there is a swap system. This patch adds new hook in kswapd where above scanning normal LRU pages.

This patch discards all of pages of vmas in vrange without considering VRANGE_[FULL|PARTIAL]_MODE, which will be considered in future work.

I should confess that I didn't spend enough time to investigate where is good place for hook. Even, It might be better to add new kvranged thread because there are a few bugs these days in kswapd, which was very sensitive for a small change so adding new hooks may make subtle another problem.

It could be better to move vrange code into kswapd after settle down in kvrangd. Otherwise, we could leave at it is in kvranged.

Other issue is scanning cost of virtual address. We don't have any information of rss in each VMA so kswapd can scan all address without any gain. It can burn out CPU. I have a plan to account rss by per-VMA at least, anonymous vma.

Any comment are welcome!

---
 include/linux/rmap.h   |   3 +
 include/linux/vrange.h |   4 +-
 mm/vmscan.c            |  45 +++++++++-
 mm/vrange.c            | 239 +++++++++++++++++++++++++++++++++++++++++++++++--
 4 files changed, 279 insertions(+), 12 deletions(-)
include/linux/rmap.h +3 -0
index 6432dfb..e822a30 100644
@@ -83,6 +83,9 @@ enum ttu_flags {
 };
 
 #ifdef CONFIG_MMU
+unsigned long discard_vrange_page_list(struct zone *zone,
+		struct list_head *page_list);
+
 unsigned long vma_address(struct page *page, struct vm_area_struct *vma);
 
 static inline void get_anon_vma(struct anon_vma *anon_vma)
include/linux/vrange.h +1 -3
index 26db168..4bcec40 100644
@@ -5,14 +5,12 @@
 #include <linux/interval_tree.h>
 #include <linux/mm.h>
 
-/* To protect race with forker */
-static DECLARE_RWSEM(vrange_fork_lock);
-
 struct vrange {
 	struct interval_tree_node node;
 	bool purged;
 	struct mm_struct *mm;
 	struct list_head lru; /* protected by lru_lock */
+	atomic_t refcount;
 };
 
 #define vrange_entry(ptr) \
mm/vmscan.c +43 -2

75 lines not on this page · raw message

mm/vrange.c +232 -7

310 lines not on this page · raw message

Signature · 7 lines
1.8.1.1

--
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>
#11 lore raw

RFC v7 11/11 add purged page information in vmstat

In reply to Minchan Kim

This patch adds vmstat information about discarded page in vrange so admin can see how many of volatile pages are discarded by VM and efficieny. it could be indicator for seeing vrange working well.

PG_VRANGE_SCAN : the number of scanned pages for discarding
PG_VRANGE_DISCARD: the number of discarded pages in kswapd's vrange LRU order PGDISCARD_DIRECT : the number of discarded pages in process context PGDISCARD_KSWAPD : the number of discarded pages in kswapd's page LRU order

---
 include/linux/vm_event_item.h | 4 ++++
 mm/vmstat.c                   | 4 ++++
 mm/vrange.c                   | 9 +++++++++
 3 files changed, 17 insertions(+)
include/linux/vm_event_item.h +4 -0
index bd6cf61..3d8ad18 100644
@@ -25,6 +25,10 @@ enum vm_event_item { PGPGIN, PGPGOUT, PSWPIN, PSWPOUT,
 		FOR_ALL_ZONES(PGALLOC),
 		PGFREE, PGACTIVATE, PGDEACTIVATE,
 		PGFAULT, PGMAJFAULT,
+		PG_VRANGE_SCAN,
+		PG_VRANGE_DISCARD,
+		PGDISCARD_DIRECT,
+		PGDISCARD_KSWAPD,
 		FOR_ALL_ZONES(PGREFILL),
 		FOR_ALL_ZONES(PGSTEAL_KSWAPD),
 		FOR_ALL_ZONES(PGSTEAL_DIRECT),
mm/vmstat.c +4 -0
index e1d8ed1..55806d2 100644
@@ -754,6 +754,10 @@ const char * const vmstat_text[] = {
 
 	"pgfault",
 	"pgmajfault",
+	"pgvrange_scan",
+	"pgvrange_discard",
+	"pgdiscard_direct",
+	"pgdiscard_kswapd",
 
 	TEXTS_FOR_ZONES("pgrefill")
 	TEXTS_FOR_ZONES("pgsteal_kswapd")
mm/vrange.c +9 -0
index 2f56d36..c0c5d50 100644
@@ -518,6 +518,10 @@ int discard_vpage(struct page *page)
 		if (page_freeze_refs(page, 1)) {
 			unlock_page(page);
 			dec_zone_page_state(page, NR_ISOLATED_ANON);
+			if (current_is_kswapd())
+				count_vm_event(PGDISCARD_KSWAPD);
+			else
+				count_vm_event(PGDISCARD_DIRECT);
 			return 1;
 		}
 	}
@@ -584,11 +588,15 @@ static int vrange_pte_range(pmd_t *pmd, unsigned long addr, unsigned long end,
 {
 	pte_t *pte;
 	spinlock_t *ptl;
+	unsigned long start = addr;
 
 	pte = pte_offset_map_lock(walk->mm, pmd, addr, &ptl);
 	for (; addr != end; pte++, addr += PAGE_SIZE)
 		vrange_pte_entry(*pte, addr, PAGE_SIZE, walk);
 	pte_unmap_unlock(pte - 1, ptl);
+
+	count_vm_events(PG_VRANGE_SCAN, (end - start) / PAGE_SIZE);
+
 	cond_resched();
 	return 0;
 
@@ -741,5 +749,6 @@ unsigned int discard_vrange_pages(struct zone *zone, int nr_to_discard)
 	if (start_vrange)
 		put_victim_range(start_vrange);
 
+	count_vm_events(PG_VRANGE_DISCARD, nr_discarded);
 	return nr_discarded;
 }
Signature · 7 lines
1.8.1.1

--
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>
#12 lore raw
In reply to Minchan Kim
Quoted 103 lines · Minchan Kim

First of all, let's define the term.
From now on, I'd like to call it as vrange(a.k.a volatile range) for anonymous page. If you have a better name in mind, please suggest.

This version is still *RFC* because it's just quick prototype so it doesn't support THP/HugeTLB/KSM and even couldn't build on !x86. Before further sorting out issues, I'd like to post current direction and discuss it. Of course, I'd like to extend this discussion in comming LSF/MM.

In this version, I changed lots of thing, expecially removed vma-based approach because it needs write-side lock for mmap_sem, which will drop performance in mutli-threaded big SMP system, KOSAKI pointed out. And vma-based approach is hard to meet requirement of new system call by John Stultz's suggested semantic for consistent purged handling.
(http://linux-kernel.2935.n7.nabble.com/RFC-v5-0-8-Support-volatile-for-anonymous-range-tt575773.html#none)

I tested this patchset with modified jemalloc allocator which was leaded by Jason Evans(jemalloc author) who was interest in this feature and was happy to port his allocator to use new system call. Super Thanks Jason!

The benchmark for test is ebizzy. It have been used for testing the allocator performance so it's good for me. Again, thanks for recommending the benchmark, Jason.
(http://people.freebsd.org/~kris/scaling/ebizzy.html)

The result is good on my machine (12 CPU, 1.2GHz, DRAM 2G)

ebizzy -S 20

jemalloc-vanilla: 52389 records/sec
jemalloc-vrange: 203414 records/sec

ebizzy -S 20 with background memory pressure

jemalloc-vanilla: 40746 records/sec
jemalloc-vrange: 174910 records/sec

And it's much improved on KVM virtual machine.

This patchset is based on v3.9-rc2

- What's the sys_vrange(addr, length, mode, behavior)?

It's a hint that user deliver to kernel so kernel can *discard* pages in a range anytime. mode is one of VRANGE_VOLATILE and VRANGE_NOVOLATILE. VRANGE_NOVOLATILE is memory pin operation so kernel coudn't discard any pages any more while VRANGE_VOLATILE is memory unpin opeartion so kernel can discard pages in vrange anytime. At a moment, behavior is one of VRANGE_FULL and VRANGE PARTIAL. VRANGE_FULL tell kernel that once kernel decide to discard page in a vrange, please, discard all of pages in a vrange selected by victim vrange. VRANGE_PARTIAL tell kernel that please discard of some pages in a vrange. But now I didn't implemented VRANGE_PARTIAL handling yet.

- What happens if user access page(ie, virtual address) discarded by kernel?

The user can encounter SIGBUS.

- What should user do for avoding SIGBUS?
He should call vrange(addr, length, VRANGE_NOVOLATILE, mode) before accessing the range which was called
vrange(addr, length, VRANGE_VOLATILE, mode)

- What happens if user access page(ie, virtual address) doesn't discarded by kernel?

The user can see vaild data which was there before calling
vrange(., VRANGE_VOLATILE) without page fault.

- What's different with madvise(DONTNEED)?

System call semantic

DONTNEED makes sure user always can see zero-fill pages after he calls madvise while vrange can see data or encounter SIGBUS.

Internal implementation

The madvise(DONTNEED) should zap all mapped pages in range so overhead is increased linearly with the number of mapped pages. Even, if user access zapped pages as write mode, page fault + page allocation + memset should be happened.

The vrange just register a address range instead of zapping all of pte n the vma so it doesn't touch ptes any more.

- What's the benefit compared to DONTNEED?

1. The system call overhead is smaller because vrange just registers a range using interval tree instead of zapping all the page in a range so overhead should be really cheap.

2. It has a chance to eliminate overheads (ex, zapping pte + page fault
+ page allocation + memset(PAGE_SIZE)) if memory pressure isn't severe.

3. It has a potential to zap all ptes and free the pages if memory pressure is severe so discard scanning overhead could be smaller - TODO

Quoted 6 lines

- What's for targetting?

Firstly, user-space allocator like ptmalloc, jemalloc or heap management of virtual machine like Dalvik. Also, it comes in handy for embedded which doesn't have swap device so they can't reclaim anonymous pages. By discarding instead of swapout, it could be used in the non-swap system.

I think that another potentially useful use-case would be using this -- or a similar API -- to opportunistically return deep user stack frames.

This is another place where we strongly care about the time-to-free as well as the time-to-reallocate in the case of relatively immediate re-use.

Quoted 68 lines

Changelog from v6 - There are many changes.
* Remove vma-based approach
* Change system call semantic
* Add more meaningful experiment

Changelog from v5 - There are many changes.

* Support CONFIG_VOLATILE_PAGE
* Working with THP/KSM
* Remove vma hacking logic in m[no]volatile system call
* Discard page without swap cache
* Kswapd discard volatile page so we can discard volatile pages although we don't have swap.

Changelog from v4

* Add new system call mvolatile/mnovolatile
* Add sigbus when user try to access volatile range
* Rebased on v3.7
* Applied bug fix from John Stultz, Thanks!

Changelog from v3

* Removing madvise(addr, length, MADV_NOVOLATILE).
* add vmstat about the number of discarded volatile pages
* discard volatile pages without promotion in reclaim path

Minchan Kim (11):
vrange: enable generic interval tree
add vrange basic data structure and functions
add new system call vrange(2)
add proc/pid/vrange information
Add purge operation
send SIGBUS when user try to access purged page
keep mm_struct to vrange when system call context
add LRU handling for victim vrange
Get rid of depenceny that all pages is from a zone in shrink_page_list Purging vrange pages without swap
add purged page information in vmstat

 arch/x86/include/asm/pgtable_types.h   |   2 +
 arch/x86/syscalls/syscall_64.tbl       |   1 +
 fs/proc/base.c                         |   1 +
 fs/proc/internal.h                     |   6 +
 fs/proc/task_mmu.c                     | 129 ++++++
 include/asm-generic/pgtable.h          |  11 +
 include/linux/mm_types.h               |   5 +
 include/linux/rmap.h                   |  15 +-
 include/linux/swap.h                   |   1 +
 include/linux/vm_event_item.h          |   4 +
 include/linux/vrange.h                 |  59 +++
 include/uapi/asm-generic/mman-common.h |   5 +
 init/main.c                            |   2 +
 kernel/fork.c                          |   3 +
 lib/Makefile                           |   2 +-
 mm/Makefile                            |   2 +-
 mm/ksm.c                               |   2 +-
 mm/memory.c                            |  24 +-
 mm/rmap.c                              |  23 +-
 mm/swapfile.c                          |  36 ++
 mm/vmscan.c                            |  74 +++-
 mm/vmstat.c                            |   4 +
 mm/vrange.c                            | 754 +++++++++++++++++++++++++++++++++
 23 files changed, 1143 insertions(+), 22 deletions(-)
 create mode 100644 include/linux/vrange.h
 create mode 100644 mm/vrange.c
Quoted 3 lines

--
1.8.1.1

--
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>

#13 lore raw
Quoted 111 lines · Paul Turner
Quoted 103 lines · Minchan Kim

First of all, let's define the term.
From now on, I'd like to call it as vrange(a.k.a volatile range) for anonymous page. If you have a better name in mind, please suggest.

This version is still *RFC* because it's just quick prototype so it doesn't support THP/HugeTLB/KSM and even couldn't build on !x86. Before further sorting out issues, I'd like to post current direction and discuss it. Of course, I'd like to extend this discussion in comming LSF/MM.

In this version, I changed lots of thing, expecially removed vma-based approach because it needs write-side lock for mmap_sem, which will drop performance in mutli-threaded big SMP system, KOSAKI pointed out. And vma-based approach is hard to meet requirement of new system call by John Stultz's suggested semantic for consistent purged handling.
(http://linux-kernel.2935.n7.nabble.com/RFC-v5-0-8-Support-volatile-for-anonymous-range-tt575773.html#none)

I tested this patchset with modified jemalloc allocator which was leaded by Jason Evans(jemalloc author) who was interest in this feature and was happy to port his allocator to use new system call. Super Thanks Jason!

The benchmark for test is ebizzy. It have been used for testing the allocator performance so it's good for me. Again, thanks for recommending the benchmark, Jason.
(http://people.freebsd.org/~kris/scaling/ebizzy.html)

The result is good on my machine (12 CPU, 1.2GHz, DRAM 2G)

ebizzy -S 20

jemalloc-vanilla: 52389 records/sec
jemalloc-vrange: 203414 records/sec

ebizzy -S 20 with background memory pressure

jemalloc-vanilla: 40746 records/sec
jemalloc-vrange: 174910 records/sec

And it's much improved on KVM virtual machine.

This patchset is based on v3.9-rc2

- What's the sys_vrange(addr, length, mode, behavior)?

It's a hint that user deliver to kernel so kernel can *discard* pages in a range anytime. mode is one of VRANGE_VOLATILE and VRANGE_NOVOLATILE. VRANGE_NOVOLATILE is memory pin operation so kernel coudn't discard any pages any more while VRANGE_VOLATILE is memory unpin opeartion so kernel can discard pages in vrange anytime. At a moment, behavior is one of VRANGE_FULL and VRANGE PARTIAL. VRANGE_FULL tell kernel that once kernel decide to discard page in a vrange, please, discard all of pages in a vrange selected by victim vrange. VRANGE_PARTIAL tell kernel that please discard of some pages in a vrange. But now I didn't implemented VRANGE_PARTIAL handling yet.

- What happens if user access page(ie, virtual address) discarded by kernel?

The user can encounter SIGBUS.

- What should user do for avoding SIGBUS?
He should call vrange(addr, length, VRANGE_NOVOLATILE, mode) before accessing the range which was called
vrange(addr, length, VRANGE_VOLATILE, mode)

- What happens if user access page(ie, virtual address) doesn't discarded by kernel?

The user can see vaild data which was there before calling
vrange(., VRANGE_VOLATILE) without page fault.

- What's different with madvise(DONTNEED)?

System call semantic

DONTNEED makes sure user always can see zero-fill pages after he calls madvise while vrange can see data or encounter SIGBUS.

Internal implementation

The madvise(DONTNEED) should zap all mapped pages in range so overhead is increased linearly with the number of mapped pages. Even, if user access zapped pages as write mode, page fault + page allocation + memset should be happened.

The vrange just register a address range instead of zapping all of pte n the vma so it doesn't touch ptes any more.

- What's the benefit compared to DONTNEED?

1. The system call overhead is smaller because vrange just registers a range using interval tree instead of zapping all the page in a range so overhead should be really cheap.

2. It has a chance to eliminate overheads (ex, zapping pte + page fault
+ page allocation + memset(PAGE_SIZE)) if memory pressure isn't severe.

3. It has a potential to zap all ptes and free the pages if memory pressure is severe so discard scanning overhead could be smaller - TODO

Quoted 6 lines

- What's for targetting?

Firstly, user-space allocator like ptmalloc, jemalloc or heap management of virtual machine like Dalvik. Also, it comes in handy for embedded which doesn't have swap device so they can't reclaim anonymous pages. By discarding instead of swapout, it could be used in the non-swap system.

Quoted 7 lines

I think that another potentially useful use-case would be using this -- or a similar API -- to opportunistically return deep user stack frames.

This is another place where we strongly care about the time-to-free as well as the time-to-reallocate in the case of relatively immediate re-use.

Indeed. Great idea!
Thanks, Paul.

Signature · 8 lines
Kind regards,
Minchan Kim

--
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>
#14 lore raw
In reply to Minchan Kim
Quoted 45 lines · Minchan Kim

First of all, let's define the term.
From now on, I'd like to call it as vrange(a.k.a volatile range)
for anonymous page. If you have a better name in mind, please suggest.

This version is still *RFC* because it's just quick prototype so it doesn't support THP/HugeTLB/KSM and even couldn't build on !x86. Before further sorting out issues, I'd like to post current direction and discuss it. Of course, I'd like to extend this discussion in comming LSF/MM.

In this version, I changed lots of thing, expecially removed vma-based approach because it needs write-side lock for mmap_sem, which will drop performance in mutli-threaded big SMP system, KOSAKI pointed out. And vma-based approach is hard to meet requirement of new system call by John Stultz's suggested semantic for consistent purged handling.
(http://linux-kernel.2935.n7.nabble.com/RFC-v5-0-8-Support-volatile-for-anonymous-range-tt575773.html#none)

I tested this patchset with modified jemalloc allocator which was leaded by Jason Evans(jemalloc author) who was interest in this feature and was happy to port his allocator to use new system call. Super Thanks Jason!

The benchmark for test is ebizzy. It have been used for testing the allocator performance so it's good for me. Again, thanks for recommending the benchmark, Jason.
(http://people.freebsd.org/~kris/scaling/ebizzy.html)

The result is good on my machine (12 CPU, 1.2GHz, DRAM 2G)

ebizzy -S 20

jemalloc-vanilla: 52389 records/sec
jemalloc-vrange: 203414 records/sec

ebizzy -S 20 with background memory pressure

jemalloc-vanilla: 40746 records/sec
jemalloc-vrange: 174910 records/sec

And it's much improved on KVM virtual machine.

This patchset is based on v3.9-rc2

- What's the sys_vrange(addr, length, mode, behavior)?

Quoted 11 lines

It's a hint that user deliver to kernel so kernel can *discard* pages in a range anytime. mode is one of VRANGE_VOLATILE and VRANGE_NOVOLATILE. VRANGE_NOVOLATILE is memory pin operation so kernel coudn't discard any pages any more while VRANGE_VOLATILE is memory unpin opeartion so kernel can discard pages in vrange anytime. At a moment, behavior is one of VRANGE_FULL and VRANGE PARTIAL. VRANGE_FULL tell kernel that once kernel decide to discard page in a vrange, please, discard all of pages in a vrange selected by victim vrange. VRANGE_PARTIAL tell kernel that please discard of some pages in a vrange. But now I didn't implemented VRANGE_PARTIAL handling yet.

So I'm very excited to see this new revision! Moving away from the VMA based approach I think is really necessary, since managing the volatile ranges on a per-mm basis really isn't going to work when we want shared volatile ranges between processes (such as the shmem/tmpfs case Android uses).

Just a few questions and observations from my initial playing around with the patch:

1) So, I'm not sure I understand the benefit of VRANGE_PARTIAL. Why would VRANGE_PARTIAL be useful?

2) I've got a trivial test program that I've used previously with ashmem & my earlier file based efforts that allocates 26megs of page aligned memory, and marks every other meg as volatile. Then it forks and the child generates a ton of memory pressure, causing pages to be purged (and the child killed by the OOM killer). Initially I didn't see my test purging any pages with your patches. The problem of course was the child's COW pages were not also marked volatile, so they could not be purged. Once I over-wrote the data in the child, breaking the COW links, the data in the parent was purged under pressure. This is good, because it makes sure we don't purge cow pages if the volatility state isn't consistent, but it also brings up a few questions:

- Should volatility be inherited on fork? If volatility is not
inherited on fork(), that could cause some strange behavior if the data was purged prior to the fork, and also its not clear what the behavior of the child should be with regards to data that was volatile at fork time. However, we also don't want strange behavior on exec if overwritten volatile pages were unexpectedly purged.

- At this moment, maybe not having thought it through enough, I'm
wondering if it makes sense to have volatility inherited on fork, but cleared on exec? What are your thoughts here? Its been awhile, so I'm not sure if that's consistent with my earlier comments on the topic.

3) Oddly, in my test case, once I changed the child to over-write the volatile range and break the COW pages, the OOM killer more frequently seems to favor killing the parent process, instead of the memory hogging child process. I need to spend some more time looking at this, and I know the OOM killer may go for the parent process sometimes, but it definitely happens more frequently then when the COW pages are not broken and no data is purged. Again, I need to dig in more here.

4) One of the harder aspects I'm trying to get my head around is how your patches seem to use both the page list shrinkers (discard_vpage) to purge ranges when particular pages selected, and a zone shrinker (discard_vrange_pages) which manages its own lru of vranges. I get that this is one way to handle purging anonymous pages when we are on a swapless system, but the dual purging systems definitely make the code harder to follow. Would something like my earlier attempts at changing vmscan to shrink anonymous pages be simpler? Or is that just not going to fly w/ the mm folks?

I'll continue working with the patches and try to get tmpfs support added here soon.

Also, attached is a simple cleanup patch that you might want to fold in.

thanks
-john

#15 lore raw
Quoted 65 lines · John Stultz
Quoted 45 lines · Minchan Kim

First of all, let's define the term.
From now on, I'd like to call it as vrange(a.k.a volatile range) for anonymous page. If you have a better name in mind, please suggest.

This version is still *RFC* because it's just quick prototype so it doesn't support THP/HugeTLB/KSM and even couldn't build on !x86. Before further sorting out issues, I'd like to post current direction and discuss it. Of course, I'd like to extend this discussion in comming LSF/MM.

In this version, I changed lots of thing, expecially removed vma-based approach because it needs write-side lock for mmap_sem, which will drop performance in mutli-threaded big SMP system, KOSAKI pointed out. And vma-based approach is hard to meet requirement of new system call by John Stultz's suggested semantic for consistent purged handling.
(http://linux-kernel.2935.n7.nabble.com/RFC-v5-0-8-Support-volatile-for-anonymous-range-tt575773.html#none)

I tested this patchset with modified jemalloc allocator which was leaded by Jason Evans(jemalloc author) who was interest in this feature and was happy to port his allocator to use new system call. Super Thanks Jason!

The benchmark for test is ebizzy. It have been used for testing the allocator performance so it's good for me. Again, thanks for recommending the benchmark, Jason.
(http://people.freebsd.org/~kris/scaling/ebizzy.html)

The result is good on my machine (12 CPU, 1.2GHz, DRAM 2G)

ebizzy -S 20

jemalloc-vanilla: 52389 records/sec
jemalloc-vrange: 203414 records/sec

ebizzy -S 20 with background memory pressure

jemalloc-vanilla: 40746 records/sec
jemalloc-vrange: 174910 records/sec

And it's much improved on KVM virtual machine.

This patchset is based on v3.9-rc2

- What's the sys_vrange(addr, length, mode, behavior)?

Quoted 11 lines

It's a hint that user deliver to kernel so kernel can *discard* pages in a range anytime. mode is one of VRANGE_VOLATILE and VRANGE_NOVOLATILE. VRANGE_NOVOLATILE is memory pin operation so kernel coudn't discard any pages any more while VRANGE_VOLATILE is memory unpin opeartion so kernel can discard pages in vrange anytime. At a moment, behavior is one of VRANGE_FULL and VRANGE PARTIAL. VRANGE_FULL tell kernel that once kernel decide to discard page in a vrange, please, discard all of pages in a vrange selected by victim vrange. VRANGE_PARTIAL tell kernel that please discard of some pages in a vrange. But now I didn't implemented VRANGE_PARTIAL handling yet.

So I'm very excited to see this new revision! Moving away from the VMA based approach I think is really necessary, since managing the volatile ranges on a per-mm basis really isn't going to work when we want shared volatile ranges between processes (such as the shmem/tmpfs case Android uses).

Quoted 5 lines

Just a few questions and observations from my initial playing around with the patch:

1) So, I'm not sure I understand the benefit of VRANGE_PARTIAL. Why would VRANGE_PARTIAL be useful?

For exmaple, some process makes 64M vranges and now kernel needs 8M pages to flee from memory pressure state. In this case, we don't need to discard 64M all at once because if we discard only 8M page, the cost of allocator is (8M/4K) * page(falut + allocation + zero-clearing) while (64M/4K) * page(falut + allocation + zero-clearing), otherwise.

If it were temporal image extracted on some compressed format, it's not easy to regenerate punched hole data from original source so it would be better to discard all pages in the vrange, which will be very far from memory reclaimer.

Quoted 14 lines

2) I've got a trivial test program that I've used previously with ashmem & my earlier file based efforts that allocates 26megs of page aligned memory, and marks every other meg as volatile. Then it forks and the child generates a ton of memory pressure, causing pages to be purged (and the child killed by the OOM killer). Initially I didn't see my test purging any pages with your patches. The problem of course was the child's COW pages were not also marked volatile, so they could not be purged. Once I over-wrote the data in the child, breaking the COW links, the data in the parent was purged under pressure. This is good, because it makes sure we don't purge cow pages if the volatility state isn't consistent, but it also brings up a few questions:

Quoted 6 lines

- Should volatility be inherited on fork? If volatility is not
inherited on fork(), that could cause some strange behavior if the data was purged prior to the fork, and also its not clear what the behavior of the child should be with regards to data that was volatile at fork time. However, we also don't want strange behavior on exec if overwritten volatile pages were unexpectedly purged.

I don't know why we should inherit volatility to child at least, for anon vrange. Because it's not proper way to share the data. For data sharing for anonymous page, we should use shmem so the work could be done when we work tmpfs work, I guess.

Currently, I implemented it to protect only COW pages.
If the data was purged prio to fork, the page should be never mapped logically so child should see newly zero-cleared page if he try to access the address. But you pointed out the bug, I should have handled it in copy_one_pte. I guess the bug might cause OOM kill for parent by wrong rss count. I will fix it.

I'm not sure it could be a good answer for your question because I couldn't understand your question fully.
If my answer isn't enough, could you elaborate it more?

Quoted 6 lines

- At this moment, maybe not having thought it through enough,
I'm wondering if it makes sense to have volatility inherited on fork, but cleared on exec? What are your thoughts here? Its been awhile, so I'm not sure if that's consistent with my earlier comments on the topic.

I already said my opinion above.

Quoted 10 lines

3) Oddly, in my test case, once I changed the child to over-write the volatile range and break the COW pages, the OOM killer more frequently seems to favor killing the parent process, instead of the memory hogging child process. I need to spend some more time looking at this, and I know the OOM killer may go for the parent process sometimes, but it definitely happens more frequently then when the COW pages are not broken and no data is purged. Again, I need to dig in more here.

It should be a problem wrong RSS count.
Could you send test program? I will fix it if you don't have enough time.

Quoted 9 lines

4) One of the harder aspects I'm trying to get my head around is how your patches seem to use both the page list shrinkers (discard_vpage) to purge ranges when particular pages selected, and a zone shrinker (discard_vrange_pages) which manages its own lru of vranges. I get that this is one way to handle purging anonymous pages when we are on a swapless system, but the dual purging systems definitely make the code harder to follow. Would something like my

discard_vpage is for avoiding swapping out in direct reclaim path when kswapd miss the page.

discard_vrange_pages is for handling volatile pages as top prioirty prio to reclaim non-volatile pages.

I think it's very clear, NOT to understand. :)
And discard_vpage is basic core function to discard volatile page so it could be used many places.

Quoted 2 lines

earlier attempts at changing vmscan to shrink anonymous pages be simpler? Or is that just not going to fly w/ the mm folks?

There were many attempt at old. Could you point out?

Quoted 6 lines

I'll continue working with the patches and try to get tmpfs support added here soon.

Also, attached is a simple cleanup patch that you might want to fold in.

Thanks, John!

Quoted 105 lines

thanks
-john

Quoted 1 line

From 10f50e53ae706d61591b3247bc494b47a79f2b69 Mon Sep 17 00:00:00 2001

From: John Stultz <[email protected]>
Date: Wed, 20 Mar 2013 18:24:56 -0700
Subject: [PATCH] vrange: Make various vrange.c local functions static

Make a number of local functions in vrange.c static.

---
 mm/vrange.c |   18 +++++++++---------
 1 file changed, 9 insertions(+), 9 deletions(-)
mm/vrange.c +9 -9
index c0c5d50..d07884d 100644
@@ -45,7 +45,7 @@ static inline void __set_vrange(struct vrange *range,
 	range->node.last = end_idx;
 }
 
-void lru_add_vrange(struct vrange *vrange)
+static void lru_add_vrange(struct vrange *vrange)
 {
 	spin_lock(&lru_lock);
 	WARN_ON(!list_empty(&vrange->lru));
@@ -53,7 +53,7 @@ void lru_add_vrange(struct vrange *vrange)
 	spin_unlock(&lru_lock);
 }
 
-void lru_remove_vrange(struct vrange *vrange)
+static void lru_remove_vrange(struct vrange *vrange)
 {
 	spin_lock(&lru_lock);
 	if (!list_empty(&vrange->lru))
@@ -130,7 +130,7 @@ static inline void range_resize(struct rb_root *root,
 	__add_range(range, root, mm);
 }
 
-int add_vrange(struct mm_struct *mm,
+static int add_vrange(struct mm_struct *mm,
 			unsigned long start, unsigned long end)
 {
 	struct rb_root *root;
@@ -172,7 +172,7 @@ out:
 	return 0;
 }
 
-int remove_vrange(struct mm_struct *mm,
+static int remove_vrange(struct mm_struct *mm,
 		unsigned long start, unsigned long end)
 {
 	struct rb_root *root;
@@ -292,7 +292,7 @@ out:
 	return ret;
 }
 
-bool __vrange_address(struct mm_struct *mm,
+static bool __vrange_address(struct mm_struct *mm,
 			unsigned long start, unsigned long end)
 {
 	struct rb_root *root = &mm->v_rb;
@@ -387,7 +387,7 @@ static void __vrange_purge(struct mm_struct *mm,
 	}
 }
 
-int try_to_discard_one(struct page *page, struct vm_area_struct *vma,
+static int try_to_discard_one(struct page *page, struct vm_area_struct *vma,
 		unsigned long address)
 {
 	struct mm_struct *mm = vma->vm_mm;
@@ -602,7 +602,7 @@ static int vrange_pte_range(pmd_t *pmd, unsigned long addr, unsigned long end,
 
 }
 
-unsigned int discard_vma_pages(struct zone *zone, struct mm_struct *mm,
+static unsigned int discard_vma_pages(struct zone *zone, struct mm_struct *mm,
 		struct vm_area_struct *vma, unsigned long start,
 		unsigned long end, unsigned int nr_to_discard)
 {
@@ -669,7 +669,7 @@ out:
  * Get next victim vrange from LRU and hold a vrange refcount
  * and vrange->mm's refcount.
  */
-struct vrange *get_victim_vrange(void)
+static struct vrange *get_victim_vrange(void)
 {
 	struct mm_struct *mm;
 	struct vrange *vrange = NULL;
@@ -711,7 +711,7 @@ struct vrange *get_victim_vrange(void)
 	return vrange;
 }
 
-void put_victim_range(struct vrange *vrange)
+static void put_victim_range(struct vrange *vrange)
 {
 	put_vrange(vrange);
 	mmdrop(vrange->mm);
Signature · 1 line
1.7.10.4
Signature · 8 lines
Kind regards,
Minchan Kim

--
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>
#16 lore raw
Quoted 76 lines · Minchan Kim
Quoted 64 lines · John Stultz
Quoted 45 lines · Minchan Kim

First of all, let's define the term.
From now on, I'd like to call it as vrange(a.k.a volatile range)
for anonymous page. If you have a better name in mind, please suggest.

This version is still *RFC* because it's just quick prototype so it doesn't support THP/HugeTLB/KSM and even couldn't build on !x86. Before further sorting out issues, I'd like to post current direction and discuss it. Of course, I'd like to extend this discussion in comming LSF/MM.

In this version, I changed lots of thing, expecially removed vma-based approach because it needs write-side lock for mmap_sem, which will drop performance in mutli-threaded big SMP system, KOSAKI pointed out. And vma-based approach is hard to meet requirement of new system call by John Stultz's suggested semantic for consistent purged handling.
(http://linux-kernel.2935.n7.nabble.com/RFC-v5-0-8-Support-volatile-for-anonymous-range-tt575773.html#none)

I tested this patchset with modified jemalloc allocator which was leaded by Jason Evans(jemalloc author) who was interest in this feature and was happy to port his allocator to use new system call. Super Thanks Jason!

The benchmark for test is ebizzy. It have been used for testing the allocator performance so it's good for me. Again, thanks for recommending the benchmark, Jason.
(http://people.freebsd.org/~kris/scaling/ebizzy.html)

The result is good on my machine (12 CPU, 1.2GHz, DRAM 2G)

ebizzy -S 20

jemalloc-vanilla: 52389 records/sec
jemalloc-vrange: 203414 records/sec

ebizzy -S 20 with background memory pressure

jemalloc-vanilla: 40746 records/sec
jemalloc-vrange: 174910 records/sec

And it's much improved on KVM virtual machine.

This patchset is based on v3.9-rc2

- What's the sys_vrange(addr, length, mode, behavior)?

Quoted 11 lines

It's a hint that user deliver to kernel so kernel can *discard* pages in a range anytime. mode is one of VRANGE_VOLATILE and VRANGE_NOVOLATILE. VRANGE_NOVOLATILE is memory pin operation so kernel coudn't discard any pages any more while VRANGE_VOLATILE is memory unpin opeartion so kernel can discard pages in vrange anytime. At a moment, behavior is one of VRANGE_FULL and VRANGE PARTIAL. VRANGE_FULL tell kernel that once kernel decide to discard page in a vrange, please, discard all of pages in a vrange selected by victim vrange. VRANGE_PARTIAL tell kernel that please discard of some pages in a vrange. But now I didn't implemented VRANGE_PARTIAL handling yet.

So I'm very excited to see this new revision! Moving away from the VMA based approach I think is really necessary, since managing the volatile ranges on a per-mm basis really isn't going to work when we want shared volatile ranges between processes (such as the shmem/tmpfs case Android uses).

Quoted 5 lines

Just a few questions and observations from my initial playing around with the patch:

1) So, I'm not sure I understand the benefit of VRANGE_PARTIAL. Why would VRANGE_PARTIAL be useful?

For exmaple, some process makes 64M vranges and now kernel needs 8M pages to flee from memory pressure state. In this case, we don't need to discard 64M all at once because if we discard only 8M page, the cost of allocator is (8M/4K) * page(falut + allocation + zero-clearing) while (64M/4K) * page(falut + allocation + zero-clearing), otherwise.

Quoted 4 lines

If it were temporal image extracted on some compressed format, it's not easy to regenerate punched hole data from original source so it would be better to discard all pages in the vrange, which will be very far from memory reclaimer.

So, if I understand you properly, its more an issue of the the added cost of making the purged range non-volatile, and re-faulting in the pages if we purge them all, when we didn't actually have the memory pressure to warrant purging the entire range?

Hrm. Ok, I can sort of see that.

So if we do partial-purging, all the data in the range is invalid - since we don't know which pages in particular were purged, but the costs when marking the range non-volatile and the costs of over-writing the pages with the re-created data will be slightly cheaper.

I guess the other benefit is if you're using the SIGBUS semantics, you might luck out and not actually touch a purged page. Where as if the entire range is purged, the process will definitely hit the SIGBUS if its accessing the volatile data.

So yea, its starting to make sense.

Much of my earlier confusion comes from comment in the vrange syscall implementation that suggests VRANGE_PARTIAL will purge from ranges intentionally in round-robin order, which I think is probably not advantageous, as it will invalidate more ranges causing more overhead. Instead using the normal page eviction order with _PARTIAL would probably be best.

Quoted 19 lines
Quoted 13 lines

2) I've got a trivial test program that I've used previously with ashmem & my earlier file based efforts that allocates 26megs of page aligned memory, and marks every other meg as volatile. Then it forks and the child generates a ton of memory pressure, causing pages to be purged (and the child killed by the OOM killer). Initially I didn't see my test purging any pages with your patches. The problem of course was the child's COW pages were not also marked volatile, so they could not be purged. Once I over-wrote the data in the child, breaking the COW links, the data in the parent was purged under pressure. This is good, because it makes sure we don't purge cow pages if the volatility state isn't consistent, but it also brings up a few questions:

Quoted 6 lines

- Should volatility be inherited on fork? If volatility is not
inherited on fork(), that could cause some strange behavior if the data was purged prior to the fork, and also its not clear what the behavior of the child should be with regards to data that was volatile at fork time. However, we also don't want strange behavior on exec if overwritten volatile pages were unexpectedly purged.

Quoted 4 lines

I don't know why we should inherit volatility to child at least, for anon vrange. Because it's not proper way to share the data. For data sharing for anonymous page, we should use shmem so the work could be done when we work tmpfs work, I guess.

I'm not suggesting the volatile *pages* on fork would be shared (other then they are COW), instead my point is the volatile *state* of the pages should probably be preserved over a fork.

Given the following example:

buf = malloc(BIGBUF);
memset(buf, 'P', BIGBUF);
vrange(buf, BIGBUF, VRANGE_VOLATILE, VRANGE_FULL); pid = fork();

if (!pid) /* break COW sharing*/

    memset(buf, 'C', BIGBUF);

generate_memory_pressure();
purged = vrange(buf, BIGBUF, VRANGE_NOVOLATILE, VRANGE_FULL);

Currently, because vrange is set before the fork, in this example, only the parent's volatile range will be purged. However, if we were to move the fork() one line up, then both parent and child would see their separate ranges purged. This behavior is not quite intuitive, as I usually expect the childs state to be identical to the parents at fork time.

In my mind, what would be less surprising is if in the above code, the volatility state of buf would be inherited to the child as well (basically copying the vrange tree at fork).

And the cow breaking in the above is just for clarification, even if the COW links weren't broken and the pages were still shared between the child and parent after fork, since they both would consider the buffer state as volatile, it would still be ok to purge the pages.

Now, the other side of the coin, is that if we have volatile data at fork time, but the child then goes on to call exec, we don't want the new process to randomly hit sigfaults when the earlier set volatile range is purged. So if we inherit volatile state to children, my thought is we probably want to clear all volatile state on exec.

Quoted 8 lines
Quoted 8 lines

4) One of the harder aspects I'm trying to get my head around is how your patches seem to use both the page list shrinkers (discard_vpage) to purge ranges when particular pages selected, and a zone shrinker (discard_vrange_pages) which manages its own lru of vranges. I get that this is one way to handle purging anonymous pages when we are on a swapless system, but the dual purging systems definitely make the code harder to follow. Would something like my

Quoted 5 lines

discard_vpage is for avoiding swapping out in direct reclaim path when kswapd miss the page.

discard_vrange_pages is for handling volatile pages as top prioirty prio to reclaim non-volatile pages.

So one note: while I've pushed for freeing volatile pages first in the past, I know Mel has had some objections to this, for instance, he thought there are cases where freeing the volatile data first wasn't the right thing to do, such as the case with streaming data, and that we probably want to leave it to the page eviction LRUs to pick the pages for us.

Quoted 4 lines

I think it's very clear, NOT to understand. :)
And discard_vpage is basic core function to discard volatile page so it could be used many places.

Ok, I suspect it will make more sense as I get more familiar with it. :)

Quoted 4 lines
Quoted 3 lines

earlier attempts at changing vmscan to shrink anonymous pages be simpler? Or is that just not going to fly w/ the mm folks?

There were many attempt at old. Could you point out?

https://lkml.org/lkml/2012/6/12/587
Although I know you had objections to my specific implementation, since it kept non-volatile anonymous pages on the active list.

thanks
-john

--
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>

#17 lore raw
Quoted 87 lines · John Stultz
Quoted 76 lines · Minchan Kim
Quoted 64 lines · John Stultz
Quoted 45 lines · Minchan Kim

First of all, let's define the term.
From now on, I'd like to call it as vrange(a.k.a volatile range) for anonymous page. If you have a better name in mind, please suggest.

This version is still *RFC* because it's just quick prototype so it doesn't support THP/HugeTLB/KSM and even couldn't build on !x86. Before further sorting out issues, I'd like to post current direction and discuss it. Of course, I'd like to extend this discussion in comming LSF/MM.

In this version, I changed lots of thing, expecially removed vma-based approach because it needs write-side lock for mmap_sem, which will drop performance in mutli-threaded big SMP system, KOSAKI pointed out. And vma-based approach is hard to meet requirement of new system call by John Stultz's suggested semantic for consistent purged handling.
(http://linux-kernel.2935.n7.nabble.com/RFC-v5-0-8-Support-volatile-for-anonymous-range-tt575773.html#none)

I tested this patchset with modified jemalloc allocator which was leaded by Jason Evans(jemalloc author) who was interest in this feature and was happy to port his allocator to use new system call. Super Thanks Jason!

The benchmark for test is ebizzy. It have been used for testing the allocator performance so it's good for me. Again, thanks for recommending the benchmark, Jason.
(http://people.freebsd.org/~kris/scaling/ebizzy.html)

The result is good on my machine (12 CPU, 1.2GHz, DRAM 2G)

ebizzy -S 20

jemalloc-vanilla: 52389 records/sec
jemalloc-vrange: 203414 records/sec

ebizzy -S 20 with background memory pressure

jemalloc-vanilla: 40746 records/sec
jemalloc-vrange: 174910 records/sec

And it's much improved on KVM virtual machine.

This patchset is based on v3.9-rc2

- What's the sys_vrange(addr, length, mode, behavior)?

Quoted 11 lines

It's a hint that user deliver to kernel so kernel can *discard* pages in a range anytime. mode is one of VRANGE_VOLATILE and VRANGE_NOVOLATILE. VRANGE_NOVOLATILE is memory pin operation so kernel coudn't discard any pages any more while VRANGE_VOLATILE is memory unpin opeartion so kernel can discard pages in vrange anytime. At a moment, behavior is one of VRANGE_FULL and VRANGE PARTIAL. VRANGE_FULL tell kernel that once kernel decide to discard page in a vrange, please, discard all of pages in a vrange selected by victim vrange. VRANGE_PARTIAL tell kernel that please discard of some pages in a vrange. But now I didn't implemented VRANGE_PARTIAL handling yet.

So I'm very excited to see this new revision! Moving away from the VMA based approach I think is really necessary, since managing the volatile ranges on a per-mm basis really isn't going to work when we want shared volatile ranges between processes (such as the shmem/tmpfs case Android uses).

Quoted 5 lines

Just a few questions and observations from my initial playing around with the patch:

1) So, I'm not sure I understand the benefit of VRANGE_PARTIAL. Why would VRANGE_PARTIAL be useful?

For exmaple, some process makes 64M vranges and now kernel needs 8M pages to flee from memory pressure state. In this case, we don't need to discard 64M all at once because if we discard only 8M page, the cost of allocator is (8M/4K) * page(falut + allocation + zero-clearing) while (64M/4K) * page(falut + allocation + zero-clearing), otherwise.

Quoted 4 lines

If it were temporal image extracted on some compressed format, it's not easy to regenerate punched hole data from original source so it would be better to discard all pages in the vrange, which will be very far from memory reclaimer.

So, if I understand you properly, its more an issue of the the added cost of making the purged range non-volatile, and re-faulting in the pages if we purge them all, when we didn't actually have the memory pressure to warrant purging the entire range?

Quoted 7 lines

Hrm. Ok, I can sort of see that.

So if we do partial-purging, all the data in the range is invalid - since we don't know which pages in particular were purged, but the costs when marking the range non-volatile and the costs of over-writing the pages with the re-created data will be slightly cheaper.

It could be heavily cheaper with my experiment in this patchset. Allocator could avoid minor fault from 105799867 to 9401.

Quoted 5 lines

I guess the other benefit is if you're using the SIGBUS semantics, you might luck out and not actually touch a purged page. Where as if the entire range is purged, the process will definitely hit the SIGBUS if its accessing the volatile data.

Yes. I guess that's why Taras liked it.
Quote from old version
"
4) Having a new system call makes it easier for userspace apps to detect kernels without this functionality.

I really like the proposed interface. I like the suggestion of having explicit FULL|PARTIAL_VOLATILE. Why not include PARTIAL_VOLATILE as a required 3rd param in first version with expectation that FULL_VOLATILE will be added later(and returning some not-supported error in meantime)?
"

Quoted 10 lines

So yea, its starting to make sense.

Much of my earlier confusion comes from comment in the vrange syscall implementation that suggests VRANGE_PARTIAL will purge from ranges intentionally in round-robin order, which I think is probably not advantageous, as it will invalidate more ranges causing more overhead. Instead using the normal page eviction order with _PARTIAL would probably be best.

As you know, I insisted on several time "volatile pages" is nothing special so we should reclaim them in normal page order. But I changed my mind because in allocator's POV, if we reclaim in normal page order, VM can swapout other working set pages instead of volatile pages. What happens if we don't have this feature in kernel? They may call madvise(DONTNEED) or munmap so there wouldn't be swpped out(it could be major fault afterward).

A major fault could mitigate this feature's benefit so I'd like to sweep volatile pages out firstly.

If we really want to reclaim some vrange pages in normal page order, we can add new argument in vrange system call and handle it later. But I'm not sure we really need it.

Quoted 60 lines
Quoted 21 lines
Quoted 15 lines

2) I've got a trivial test program that I've used previously with ashmem & my earlier file based efforts that allocates 26megs of page aligned memory, and marks every other meg as volatile. Then it forks and the child generates a ton of memory pressure, causing pages to be purged (and the child killed by the OOM killer). Initially I didn't see my test purging any pages with your patches. The problem of course was the child's COW pages were not also marked volatile, so they could not be purged. Once I over-wrote the data in the child, breaking the COW links, the data in the parent was purged under pressure. This is good, because it makes sure we don't purge cow pages if the volatility state isn't consistent, but it also brings up a few questions:

Quoted 6 lines

- Should volatility be inherited on fork? If volatility is not
inherited on fork(), that could cause some strange behavior if the data was purged prior to the fork, and also its not clear what the behavior of the child should be with regards to data that was volatile at fork time. However, we also don't want strange behavior on exec if overwritten volatile pages were unexpectedly purged.

Quoted 4 lines

I don't know why we should inherit volatility to child at least, for anon vrange. Because it's not proper way to share the data. For data sharing for anonymous page, we should use shmem so the work could be done when we work tmpfs work, I guess.

I'm not suggesting the volatile *pages* on fork would be shared (other then they are COW), instead my point is the volatile *state* of the pages should probably be preserved over a fork.

Given the following example:

buf = malloc(BIGBUF);
memset(buf, 'P', BIGBUF);
vrange(buf, BIGBUF, VRANGE_VOLATILE, VRANGE_FULL); pid = fork();

if (!pid) /* break COW sharing*/

    memset(buf, 'C', BIGBUF);

generate_memory_pressure();
purged = vrange(buf, BIGBUF, VRANGE_NOVOLATILE, VRANGE_FULL);

Currently, because vrange is set before the fork, in this example, only the parent's volatile range will be purged. However, if we were to move the fork() one line up, then both parent and child would see their separate ranges purged. This behavior is not quite intuitive, as I usually expect the childs state to be identical to the parents at fork time.

In my mind, what would be less surprising is if in the above code, the volatility state of buf would be inherited to the child as well (basically copying the vrange tree at fork).

And the cow breaking in the above is just for clarification, even if the COW links weren't broken and the pages were still shared between the child and parent after fork, since they both would consider the buffer state as volatile, it would still be ok to purge the pages.

Quoted 6 lines

Now, the other side of the coin, is that if we have volatile data at fork time, but the child then goes on to call exec, we don't want the new process to randomly hit sigfaults when the earlier set volatile range is purged. So if we inherit volatile state to children, my thought is we probably want to clear all volatile state on exec.

Indeed, I got a your point and frankly speaking, I implemented it with odd lock schemem in this version, then decided to drop it because I was not sure who want to use such usecase scenario between parent and child so tempted to drop it. ;-)

Okay. I have a idea, I will support it in next spin and I don't think it is never odd that child has volatile data at forktime and exec of child clear them.

Quoted 12 lines
Quoted 12 lines
Quoted 12 lines

4) One of the harder aspects I'm trying to get my head around is how your patches seem to use both the page list shrinkers (discard_vpage) to purge ranges when particular pages selected, and a zone shrinker (discard_vrange_pages) which manages its own lru of vranges. I get that this is one way to handle purging anonymous pages when we are on a swapless system, but the dual purging systems definitely make the code harder to follow. Would something like my

Quoted 8 lines
Quoted 5 lines

discard_vpage is for avoiding swapping out in direct reclaim path when kswapd miss the page.

discard_vrange_pages is for handling volatile pages as top prioirty prio to reclaim non-volatile pages.

So one note: while I've pushed for freeing volatile pages first in the past, I know Mel has had some objections to this, for instance,

Me, too at that time. But I changed my mind as I mentioned earlier.

Quoted 4 lines

he thought there are cases where freeing the volatile data first wasn't the right thing to do, such as the case with streaming data, and that we probably want to leave it to the page eviction LRUs to pick the pages for us.

I agree on streaming data. It would be great to reclaim them rather than vrange pages. But current VM isn't smart to detect streaming data and reclaim them as top priority without user's help.

If user helps kernel with hint(ex, fadvise), kernel free them instantly so there isn't any remained pages in LRU and if kernel can't free pages with some reason(dirty or locked), kernel can move them into inactive LRU's tail so in next turn, kernel can reclaim them as top-priority if they meet free-condition.

It means what we have to care is remained streaming data in LRU when user helps kernel with some advise.
If it's really severe problem, I'd like to introduce new LRU list called by easy-reclaimable so kernel can move them in easy-lru list and reclaim them as top-priority before discarding vrange pages.

Quoted 10 lines
Quoted 6 lines

I think it's very clear, NOT to understand. :)
And discard_vpage is basic core function to discard volatile page so it could be used many places.

Ok, I suspect it will make more sense as I get more familiar with it. :)

Quoted 1 line
Quoted 7 lines
Quoted 3 lines
Quoted 2 lines

earlier attempts at changing vmscan to shrink anonymous pages be simpler? Or is that just not going to fly w/ the mm folks?

There were many attempt at old. Could you point out?

https://lkml.org/lkml/2012/6/12/587
Although I know you had objections to my specific implementation, since it kept non-volatile anonymous pages on the active list.

It breaks my goal "Hint system call should be cheap" because we need something to move pages from active list to inactive's one in volatile system call context and it would be never cheap.

Quoted 5 lines

thanks
-john

Signature · 8 lines
Kind regards,
Minchan Kim

--
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>
#18 lore raw
Quoted 15 lines · Minchan Kim
Quoted 1 line · John Stultz

So, if I understand you properly, its more an issue of the the added cost of making the purged range non-volatile, and re-faulting in the pages if we purge them all, when we didn't actually have the memory pressure to warrant purging the entire range? Hrm. Ok, I can sort of see that. So if we do partial-purging, all the data in the range is invalid - since we don't know which pages in particular were purged, but the costs when marking the range non-volatile and the costs of over-writing the pages with the re-created data will be slightly cheaper.

It could be heavily cheaper with my experiment in this patchset. Allocator could avoid minor fault from 105799867 to 9401.

Quoted 4 lines

I guess the other benefit is if you're using the SIGBUS semantics, you might luck out and not actually touch a purged page. Where as if the entire range is purged, the process will definitely hit the SIGBUS if its accessing the volatile data.

Yes. I guess that's why Taras liked it.
Quote from old version
"
4) Having a new system call makes it easier for userspace apps to detect kernels without this functionality.

Quoted 6 lines

I really like the proposed interface. I like the suggestion of having explicit FULL|PARTIAL_VOLATILE. Why not include PARTIAL_VOLATILE as a required 3rd param in first version with expectation that FULL_VOLATILE will be added later(and returning some not-supported error in meantime)?
"

Thanks again for the clarifications on your though process here!

I'm currently trying to rework your patches so we can reuse this for file data as well as pure anonymous memory. The idea being that we add one level of indirection: a vrange_root structure, which manages the root of the rb interval tree as well as the lock. This vrange_root can then be included in the mm_struct as well as address_space structures depending on which type of memory we're dealing with. That way most of the same infrastructure can be used to manage per-mm volatile ranges as well as per-inode volatile ranges.

Sorting out how to handle vrange() calls that cross both anonymous and file vmas will be interesting, and may have some of the drawbacks of the vma based approach, but I think it will still be simpler. To start we may just be able to require that any vrange() calls don't cross vma types (possibly using separate syscalls for file and anonymous vranges).

Anyway, that's my current thinkig. You can preview my current attempt here:
http://git.linaro.org/gitweb?p=people/jstultz/android-dev.git;a=shortlog;h=refs/heads/dev/vrange-minchan

Thanks so much again for your moving this work forward! -john

--
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>

#19 lore raw
Quoted 34 lines · John Stultz
Quoted 24 lines · Minchan Kim
Quoted 10 lines · John Stultz

So, if I understand you properly, its more an issue of the the added cost of making the purged range non-volatile, and re-faulting in the pages if we purge them all, when we didn't actually have the memory pressure to warrant purging the entire range? Hrm. Ok, I can sort of see that. So if we do partial-purging, all the data in the range is invalid - since we don't know which pages in particular were purged, but the costs when marking the range non-volatile and the costs of over-writing the pages with the re-created data will be slightly cheaper.

It could be heavily cheaper with my experiment in this patchset. Allocator could avoid minor fault from 105799867 to 9401.

Quoted 4 lines

I guess the other benefit is if you're using the SIGBUS semantics, you might luck out and not actually touch a purged page. Where as if the entire range is purged, the process will definitely hit the SIGBUS if its accessing the volatile data.

Yes. I guess that's why Taras liked it.
Quote from old version
"
4) Having a new system call makes it easier for userspace apps to detect kernels without this functionality.

Quoted 6 lines

I really like the proposed interface. I like the suggestion of having explicit FULL|PARTIAL_VOLATILE. Why not include PARTIAL_VOLATILE as a required 3rd param in first version with expectation that FULL_VOLATILE will be added later(and returning some not-supported error in meantime)?
"

Thanks again for the clarifications on your though process here!

Quoted 9 lines

I'm currently trying to rework your patches so we can reuse this for file data as well as pure anonymous memory. The idea being that we add one level of indirection: a vrange_root structure, which manages the root of the rb interval tree as well as the lock. This vrange_root can then be included in the mm_struct as well as address_space structures depending on which type of memory we're dealing with. That way most of the same infrastructure can be used to manage per-mm volatile ranges as well as per-inode volatile ranges.

Yeb.

Quoted 4 lines

Sorting out how to handle vrange() calls that cross both anonymous and file vmas will be interesting, and may have some of the drawbacks of the vma based approach, but I think it will still be

Do you have any specific drawback examples?
I'd like to solve it if it is critical and I believe we shouldn't do that for simpler implementation.

Quoted 3 lines

simpler. To start we may just be able to require that any vrange() calls don't cross vma types (possibly using separate syscalls for file and anonymous vranges).

I can't parse what's the problem you have a concern. Why should we have separate syscall?

Quoted 4 lines

Anyway, that's my current thinkig. You can preview my current attempt here:
http://git.linaro.org/gitweb?p=people/jstultz/android-dev.git;a=shortlog;h=refs/heads/dev/vrange-minchan

I saw it roughly and it seems good to me.
I will review it in detail if you send formal patch. :)

Off-topic

Let's think another vrange usecase for file pages.
I'm thinking now it might be useful as hint interface for kernel. As you know, we already have hint interface, madivse and fadvise. But they are always heavy because kernel should spend a time to handle all pages of the range so the cost is increased linearly as range's size. Another problem is it doesn't consider system global wide view. One example is that look at below.
Look at the http://permalink.gmane.org/gmane.linux.kernel.mm/95424
There were similar several trial long time ago but rejected because it could change current behavior if the system call move pages into inactive list without freeing pages instanlty.

Andrew also suggested it "let's create another advise rather than replace old advise" for compatibility.

So the what I want is new interface but totally different system call ,vrange. Because I believe hint system call should be very cheap so that many user can use it frequently. If user don't use it often, kernel doesn't have any benefit, either.

The vrange system call could be cheap because we can move hot path overhead to slow path(reclaim path). And we can define new behavior to vrange so we could implement new idea freely.

I think it's good for system memory handling.
As you know well, there are several trial to handle memory management in userspace. One of example is lowmemory notifier. Kernel just send signal and user can free pages. Frankly speaking, I don't like that idea. Because there are several factors to limit userspace daemon's bounded reaction and could have false-positive alarm if system has streaming data, mlocked pages or many dirty pages and so on.

Anyway, my point is that I'd like to control page reclaiming in only kernel itself. For it, userspace can register their volatile or reclaimable memory ranges to kernel and define to the threshold. If kernel find memory is below threshold user defined, kernel can reclaim every pages in registered range freely.

It means kernel has a ownership of page freeing. It makes system more deterministic and not out-of-control.

So vrange system call's semantic is following as.

1. vrange for anonymous page -> Discard wthout swapout
2. vrange for file-backed page except shmem/tmpfs -> Discard without sync
3. vrange for shmem/tmpfs -> hole punching

It's just my two cents. ;-)

Quoted 1 line

Thanks so much again for your moving this work forward!

Thanks for your collaboration!

Signature · 8 lines
Kind regards,
Minchan Kim

--
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>
#20 lore raw
Quoted 7 lines · Minchan Kim
Quoted 3 lines · John Stultz

Sorting out how to handle vrange() calls that cross both anonymous and file vmas will be interesting, and may have some of the drawbacks of the vma based approach, but I think it will still be

Do you have any specific drawback examples?
I'd like to solve it if it is critical and I believe we shouldn't do that for simpler implementation.

My current thought is that we manage volatile memory on both a per-mm (for anonymous memory) and per-address_space (for file memory) basis.

The down side, if we manage both file and anonymous volatile ranges with the same interface, we may have similar problems to the per-vma approach you were trying before. Specifically, if a single range covers both anonymous and file memory, we'll have to do a similar iterating over the different types of ranges, as we did with your earlier vma approach.

This adds some complexity since with the single interval tree method in your current patch, we know we only have to allocate one additional range per insert/remove. So we can do that right off the bat, and return any enomem errors without having made any state changes. This is a nice quality to have.

Where as if we're iterating over different types of ranges, with possibly multiple trees (ie: different mmapped files), we don't know how many new ranges we may have to allocate, so we could fail half way which causes ambiguous results on the marking ranges non-volatile (since returning the error leaves the range possibly half-unmarked).

I'm still thinking it through, but that's my concern.

Some ways we can avoid this:
1) Require that any vrange() call not cross different types of memory.
2) Provide a different vrange call (fvrange?)to be used with file backed memory.

Any other thoughts?

Quoted 5 lines
Quoted 3 lines

Anyway, that's my current thinkig. You can preview my current attempt here:
http://git.linaro.org/gitweb?p=people/jstultz/android-dev.git;a=shortlog;h=refs/heads/dev/vrange-minchan

I saw it roughly and it seems good to me.
I will review it in detail if you send formal patch. :)

Ok. I'm still working on some changes (been slow this week), but hope to have more to send your way next week.

Quoted 6 lines

As you know well, there are several trial to handle memory management in userspace. One of example is lowmemory notifier. Kernel just send signal and user can free pages. Frankly speaking, I don't like that idea. Because there are several factors to limit userspace daemon's bounded reaction and could have false-positive alarm if system has streaming data, mlocked pages or many dirty pages and so on.

True. However, I think that there are valid use cases lowmemory notification (Android's low-memory killer is one, where we're not just freeing pages, but killing processes), and I think both approaches have valid use.

Quoted 6 lines

Anyway, my point is that I'd like to control page reclaiming in only kernel itself. For it, userspace can register their volatile or reclaimable memory ranges to kernel and define to the threshold. If kernel find memory is below threshold user defined, kernel can reclaim every pages in registered range freely.

Quoted 8 lines

It means kernel has a ownership of page freeing. It makes system more deterministic and not out-of-control.

So vrange system call's semantic is following as.

1. vrange for anonymous page -> Discard wthout swapout
2. vrange for file-backed page except shmem/tmpfs -> Discard without sync
3. vrange for shmem/tmpfs -> hole punching

I think on non-shmem file backed pages (case #2) hole punching will be required as well. Though I'm not totally convinced volatile ranges on non-tmpfs files actually makes sense (I still have yet to understand a use case).

Thanks again for your thoughts here.

thanks
-john

--
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>

#21 lore raw
Quoted 5 lines · John Stultz
Quoted 4 lines · Minchan Kim
Quoted 3 lines · John Stultz

Sorting out how to handle vrange() calls that cross both anonymous and file vmas will be interesting, and may have some of the drawbacks of the vma based approach, but I think it will still be

Quoted 7 lines
Quoted 3 lines

Do you have any specific drawback examples?
I'd like to solve it if it is critical and I believe we shouldn't do that for simpler implementation.

My current thought is that we manage volatile memory on both a per-mm (for anonymous memory) and per-address_space (for file memory) basis.

First of all, I should have a dumb question because I didn't thought about tmpfs usecase deeply as you had so I hope this stupid question opens my eye.

I thought like this

1. vrange system call doesn't care about whether the range is anonymous or not.
2. Discarder(At the moment, kswapd hook or kvranged in the future, direct page reclaim) can parse whether a vma could be anonymous or file-backed
3. If a vma which in vrange is anonymous, it could discard a page rather than swapping out.
4. If a vma which in vrange is file-backed(ie, tmpfs), it could discard a page rather than swappint out. => It would be same effect punch hole.

Both 3 and 4 could be handled by rmap so it couldn't discard a page if anyone mapped a page with non-volatile.

In this scenario, I can't imagine what kind of role per-address_space does. So, my question is that why we need per-address space vrange management.

If I read you mind, are you considering fd-based system call, not mmaped-address space approach to replace ashmem?

Quoted 7 lines

The down side, if we manage both file and anonymous volatile ranges with the same interface, we may have similar problems to the per-vma approach you were trying before. Specifically, if a single range covers both anonymous and file memory, we'll have to do a similar iterating over the different types of ranges, as we did with your earlier vma approach.

As I said earlier, I don't want to care about new range is anonymous or file-backed on vrange system call context. It's just vrange then could be handled properly later when memory pressure happens.

Quoted 7 lines

This adds some complexity since with the single interval tree method in your current patch, we know we only have to allocate one additional range per insert/remove. So we can do that right off the bat, and return any enomem errors without having made any state changes. This is a nice quality to have.

Quoted 6 lines

Where as if we're iterating over different types of ranges, with possibly multiple trees (ie: different mmapped files), we don't know how many new ranges we may have to allocate, so we could fail half way which causes ambiguous results on the marking ranges non-volatile (since returning the error leaves the range possibly half-unmarked).

Maybe, I can understand your point after seeing your concern with more concrete example. :)

Quoted 27 lines

I'm still thinking it through, but that's my concern.

Some ways we can avoid this:
1) Require that any vrange() call not cross different types of memory.
2) Provide a different vrange call (fvrange?)to be used with file backed memory.

Any other thoughts?

Quoted 5 lines
Quoted 3 lines

Anyway, that's my current thinkig. You can preview my current attempt here:
http://git.linaro.org/gitweb?p=people/jstultz/android-dev.git;a=shortlog;h=refs/heads/dev/vrange-minchan

I saw it roughly and it seems good to me.
I will review it in detail if you send formal patch. :)

Ok. I'm still working on some changes (been slow this week), but hope to have more to send your way next week.

Quoted 6 lines

As you know well, there are several trial to handle memory management in userspace. One of example is lowmemory notifier. Kernel just send signal and user can free pages. Frankly speaking, I don't like that idea. Because there are several factors to limit userspace daemon's bounded reaction and could have false-positive alarm if system has streaming data, mlocked pages or many dirty pages and so on.

Quoted 4 lines

True. However, I think that there are valid use cases lowmemory notification (Android's low-memory killer is one, where we're not just freeing pages, but killing processes), and I think both approaches have valid use.

Yeb. I didn't say userspace memory notifier is useless.
My point is userspace memory notifier could be very fragile by several reasons so it works well if system has some freed memory, I mean it doesn't work well if system has big memory pressure. In this case, it would be better for kernel to reclaim pages rather than depending user's response.

Yeb. Of course, there is a trade-off there.
Kernel doesn't have enough knowledge rather than user space so kernel would work with sub-optimal pages.
So my suggestion is that plaform can use lowmemory notifier when system memory pressure is mild but when system memory pressure is approaching OOM, kernel should reclaim them instantly and before that, user can give a hint to kernel which range of the address space is recovery-possible. And it could be another usecases of vrange.

Quoted 10 lines
Quoted 10 lines

Anyway, my point is that I'd like to control page reclaiming in only kernel itself. For it, userspace can register their volatile or reclaimable memory ranges to kernel and define to the threshold. If kernel find memory is below threshold user defined, kernel can reclaim every pages in registered range freely.

It means kernel has a ownership of page freeing. It makes system more deterministic and not out-of-control.

Quoted 7 lines
Quoted 5 lines

So vrange system call's semantic is following as.

1. vrange for anonymous page -> Discard wthout swapout
2. vrange for file-backed page except shmem/tmpfs -> Discard without sync
3. vrange for shmem/tmpfs -> hole punching

I think on non-shmem file backed pages (case #2) hole punching will be required as well. Though I'm not totally convinced volatile

What I mean to is let's use vrange system call instead of madvise/fadvise. so for file-backed pages excpet shmem/tmpfs couldn't be discarded but just could be reclaimed.

Quoted 2 lines

ranges on non-tmpfs files actually makes sense (I still have yet to understand a use case).

1. The fadvise/madvise reclaim pages instantly if memory pressure doesn't happen.
2. It doesn't consider system-wide view but per-process's one
3. System call cost could be increased by range size of the system call.

vrange could recover above problems.

I'm not serious about this usecase but had just out of curiosity for how others think about it.

Signature · 8 lines
Kind regards,
Minchan Kim

--
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>
#22 lore raw
In reply to Minchan Kim

Hi,

Quoted 31 lines · On Tuesday 12 March 2013 08:38:24 Minchan Kim wrote:

First of all, let's define the term.
From now on, I'd like to call it as vrange(a.k.a volatile range) for anonymous page. If you have a better name in mind, please suggest.

This version is still *RFC* because it's just quick prototype so it doesn't support THP/HugeTLB/KSM and even couldn't build on !x86. Before further sorting out issues, I'd like to post current direction and discuss it. Of course, I'd like to extend this discussion in comming LSF/MM.

In this version, I changed lots of thing, expecially removed vma-based approach because it needs write-side lock for mmap_sem, which will drop performance in mutli-threaded big SMP system, KOSAKI pointed out. And vma-based approach is hard to meet requirement of new system call by John Stultz's suggested semantic for consistent purged handling.
(http://linux-kernel.2935.n7.nabble.com/RFC-v5-0-8-Support-volatile-for-anonymous-range-tt575773.html#none)

I tested this patchset with modified jemalloc allocator which was leaded by Jason Evans(jemalloc author) who was interest in this feature and was happy to port his allocator to use new system call. Super Thanks Jason!

The benchmark for test is ebizzy. It have been used for testing the allocator performance so it's good for me. Again, thanks for recommending the benchmark, Jason.
(http://people.freebsd.org/~kris/scaling/ebizzy.html)

The result is good on my machine (12 CPU, 1.2GHz, DRAM 2G)

ebizzy -S 20

Quoted 7 lines

jemalloc-vanilla: 52389 records/sec
jemalloc-vrange: 203414 records/sec

ebizzy -S 20 with background memory pressure

jemalloc-vanilla: 40746 records/sec
jemalloc-vrange: 174910 records/sec

Could you please make the modified jemalloc/ebizzy available somewhere so there is a easy way to test your patchset?

Best regards,
--
Bartlomiej Zolnierkiewicz
Samsung Poland R&D Center

--
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>

#23 lore raw

Hi Bart,

Quoted 38 lines · Bartlomiej Zolnierkiewicz

Hi,

Quoted 34 lines · On Tuesday 12 March 2013 08:38:24 Minchan Kim wrote:

First of all, let's define the term.
From now on, I'd like to call it as vrange(a.k.a volatile range) for anonymous page. If you have a better name in mind, please suggest.

This version is still *RFC* because it's just quick prototype so it doesn't support THP/HugeTLB/KSM and even couldn't build on !x86. Before further sorting out issues, I'd like to post current direction and discuss it. Of course, I'd like to extend this discussion in comming LSF/MM.

In this version, I changed lots of thing, expecially removed vma-based approach because it needs write-side lock for mmap_sem, which will drop performance in mutli-threaded big SMP system, KOSAKI pointed out. And vma-based approach is hard to meet requirement of new system call by John Stultz's suggested semantic for consistent purged handling.
(http://linux-kernel.2935.n7.nabble.com/RFC-v5-0-8-Support-volatile-for-anonymous-range-tt575773.html#none)

I tested this patchset with modified jemalloc allocator which was leaded by Jason Evans(jemalloc author) who was interest in this feature and was happy to port his allocator to use new system call. Super Thanks Jason!

The benchmark for test is ebizzy. It have been used for testing the allocator performance so it's good for me. Again, thanks for recommending the benchmark, Jason.
(http://people.freebsd.org/~kris/scaling/ebizzy.html)

The result is good on my machine (12 CPU, 1.2GHz, DRAM 2G)

ebizzy -S 20

jemalloc-vanilla: 52389 records/sec
jemalloc-vrange: 203414 records/sec

Quoted 7 lines
Quoted 4 lines

ebizzy -S 20 with background memory pressure

jemalloc-vanilla: 40746 records/sec
jemalloc-vrange: 174910 records/sec

Could you please make the modified jemalloc/ebizzy available somewhere so there is a easy way to test your patchset?

I will try it in next spin.
Thanks for your interest!

-
Kind regards,
Minchan Kim

--
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>

#24 lore raw
In reply to Minchan Kim
Quoted 73 lines · Minchan Kim

First of all, let's define the term.
From now on, I'd like to call it as vrange(a.k.a volatile range) for anonymous page. If you have a better name in mind, please suggest.

This version is still *RFC* because it's just quick prototype so it doesn't support THP/HugeTLB/KSM and even couldn't build on !x86. Before further sorting out issues, I'd like to post current direction and discuss it. Of course, I'd like to extend this discussion in comming LSF/MM.

In this version, I changed lots of thing, expecially removed vma-based approach because it needs write-side lock for mmap_sem, which will drop performance in mutli-threaded big SMP system, KOSAKI pointed out. And vma-based approach is hard to meet requirement of new system call by John Stultz's suggested semantic for consistent purged handling.
(http://linux-kernel.2935.n7.nabble.com/RFC-v5-0-8-Support-volatile-for-anonymous-range-tt575773.html#none)

I tested this patchset with modified jemalloc allocator which was leaded by Jason Evans(jemalloc author) who was interest in this feature and was happy to port his allocator to use new system call. Super Thanks Jason!

The benchmark for test is ebizzy. It have been used for testing the allocator performance so it's good for me. Again, thanks for recommending the benchmark, Jason.
(http://people.freebsd.org/~kris/scaling/ebizzy.html)

The result is good on my machine (12 CPU, 1.2GHz, DRAM 2G)

ebizzy -S 20

jemalloc-vanilla: 52389 records/sec
jemalloc-vrange: 203414 records/sec

ebizzy -S 20 with background memory pressure

jemalloc-vanilla: 40746 records/sec
jemalloc-vrange: 174910 records/sec

And it's much improved on KVM virtual machine.

This patchset is based on v3.9-rc2

- What's the sys_vrange(addr, length, mode, behavior)?

It's a hint that user deliver to kernel so kernel can *discard* pages in a range anytime. mode is one of VRANGE_VOLATILE and VRANGE_NOVOLATILE. VRANGE_NOVOLATILE is memory pin operation so kernel coudn't discard any pages any more while VRANGE_VOLATILE is memory unpin opeartion so kernel can discard pages in vrange anytime. At a moment, behavior is one of VRANGE_FULL and VRANGE PARTIAL. VRANGE_FULL tell kernel that once kernel decide to discard page in a vrange, please, discard all of pages in a vrange selected by victim vrange. VRANGE_PARTIAL tell kernel that please discard of some pages in a vrange. But now I didn't implemented VRANGE_PARTIAL handling yet.

- What happens if user access page(ie, virtual address) discarded by kernel?

The user can encounter SIGBUS.

- What should user do for avoding SIGBUS?
He should call vrange(addr, length, VRANGE_NOVOLATILE, mode) before accessing the range which was called
vrange(addr, length, VRANGE_VOLATILE, mode)

- What happens if user access page(ie, virtual address) doesn't discarded by kernel?

The user can see vaild data which was there before calling
vrange(., VRANGE_VOLATILE) without page fault.

Quoted 6 lines

- What's different with madvise(DONTNEED)?

System call semantic

DONTNEED makes sure user always can see zero-fill pages after he calls madvise while vrange can see data or encounter SIGBUS.

For replacing DONTNEED, user want to zero-fill pages like DONTNEED instead of SIGBUS. So, new flag option would be nice.

I played a bit this patch. The result looks really promissing. (i.e. 20x faster)

My machine have 24cpus, 8GB ram, kvm guest. I guess current DONTNEED implementation doesn't fit kvm at all.

# of     # of   # of
thread   iter   iter (patched glibc)
----------------------------------
  1      438    10740
  2      842    20916
  4      987    32534
  8      717    15155
 12      714    14109
 16      708    13457
 20      720    13742
 24      727    13642
 28      715    13328
 32      709    13096
 36      705    13661
 40      708    13634
 44      707    13367
 48      714    13377

---------libc patch (just dirty hack) ----------------------

malloc/arena.c +21 -2
index 12a48ad..da04f67 100644
@@ -365,6 +365,8 @@ extern struct dl_open_hook *_dl_open_hook;
 libc_hidden_proto (_dl_open_hook);
 #endif
 
+int vrange_enabled = 0;
+
 static void
 ptmalloc_init (void)
 {
@@ -457,6 +459,18 @@ ptmalloc_init (void)
     if (check_action != 0)
       __malloc_check_init();
   }
+
+  {
+    char *vrange = getenv("MALLOC_VRANGE");
+    if (vrange) {
+      int val = atoi(vrange);
+      if (val) {
+       printf("glibc: vrange enabled\n");
+       vrange_enabled = !!val;
+      }
+    }
+  }
+
   void (*hook) (void) = force_reg (__malloc_initialize_hook);
   if (hook != NULL)
     (*hook)();
@@ -628,9 +642,14 @@ shrink_heap(heap_info *h, long diff)
        return -2;
       h->mprotect_size = new_size;
     }
-  else
-    __madvise ((char *)h + new_size, diff, MADV_DONTNEED);
+  else {
+    if (vrange_enabled) {
+      syscall(314, (char *)h + new_size, diff, 0, 1);
+    } else {
+      __madvise ((char *)h + new_size, diff, MADV_DONTNEED);
+    }
   /*fprintf(stderr, "shrink %p %08lx\n", h, new_size);*/
+  }
 
   h->size = new_size;
   return 0;
malloc/malloc.c +7 -1
index 70b9329..3782244 100644
@@ -4403,6 +4403,7 @@ _int_pvalloc(mstate av, size_t bytes)
 /*
   ------------------------------ malloc_trim ------------------------------
 */
+extern int vrange_enabled;
 
 static int mtrim(mstate av, size_t pad)
 {
@@ -4443,7 +4444,12 @@ static int mtrim(mstate av, size_t pad)
                       content.  */
                    memset (paligned_mem, 0x89, size & ~psm1);
 #endif
-                   __madvise (paligned_mem, size & ~psm1, MADV_DONTNEED);
+
+                   if (vrange_enabled) {
+                     syscall(314, paligned_mem, size & ~psm1, 0, 1);
+                   } else {
+                     __madvise (paligned_mem, size & ~psm1, MADV_DONTNEED);
+                   }
 
                    result = 1;
                  }

(END)

--
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>

#25 lore raw
Quoted 76 lines · KOSAKI Motohiro
Quoted 75 lines · Minchan Kim

First of all, let's define the term.
From now on, I'd like to call it as vrange(a.k.a volatile range) for anonymous page. If you have a better name in mind, please suggest.

This version is still *RFC* because it's just quick prototype so it doesn't support THP/HugeTLB/KSM and even couldn't build on !x86. Before further sorting out issues, I'd like to post current direction and discuss it. Of course, I'd like to extend this discussion in comming LSF/MM.

In this version, I changed lots of thing, expecially removed vma-based approach because it needs write-side lock for mmap_sem, which will drop performance in mutli-threaded big SMP system, KOSAKI pointed out. And vma-based approach is hard to meet requirement of new system call by John Stultz's suggested semantic for consistent purged handling.
(http://linux-kernel.2935.n7.nabble.com/RFC-v5-0-8-Support-volatile-for-anonymous-range-tt575773.html#none)

I tested this patchset with modified jemalloc allocator which was leaded by Jason Evans(jemalloc author) who was interest in this feature and was happy to port his allocator to use new system call. Super Thanks Jason!

The benchmark for test is ebizzy. It have been used for testing the allocator performance so it's good for me. Again, thanks for recommending the benchmark, Jason.
(http://people.freebsd.org/~kris/scaling/ebizzy.html)

The result is good on my machine (12 CPU, 1.2GHz, DRAM 2G)

ebizzy -S 20

jemalloc-vanilla: 52389 records/sec
jemalloc-vrange: 203414 records/sec

ebizzy -S 20 with background memory pressure

jemalloc-vanilla: 40746 records/sec
jemalloc-vrange: 174910 records/sec

And it's much improved on KVM virtual machine.

This patchset is based on v3.9-rc2

- What's the sys_vrange(addr, length, mode, behavior)?

It's a hint that user deliver to kernel so kernel can *discard* pages in a range anytime. mode is one of VRANGE_VOLATILE and VRANGE_NOVOLATILE. VRANGE_NOVOLATILE is memory pin operation so kernel coudn't discard any pages any more while VRANGE_VOLATILE is memory unpin opeartion so kernel can discard pages in vrange anytime. At a moment, behavior is one of VRANGE_FULL and VRANGE PARTIAL. VRANGE_FULL tell kernel that once kernel decide to discard page in a vrange, please, discard all of pages in a vrange selected by victim vrange. VRANGE_PARTIAL tell kernel that please discard of some pages in a vrange. But now I didn't implemented VRANGE_PARTIAL handling yet.

- What happens if user access page(ie, virtual address) discarded by kernel?

The user can encounter SIGBUS.

- What should user do for avoding SIGBUS?
He should call vrange(addr, length, VRANGE_NOVOLATILE, mode) before accessing the range which was called
vrange(addr, length, VRANGE_VOLATILE, mode)

- What happens if user access page(ie, virtual address) doesn't discarded by kernel?

The user can see vaild data which was there before calling
vrange(., VRANGE_VOLATILE) without page fault.

- What's different with madvise(DONTNEED)?

Quoted 7 lines
Quoted 4 lines

System call semantic

DONTNEED makes sure user always can see zero-fill pages after he calls madvise while vrange can see data or encounter SIGBUS.

For replacing DONTNEED, user want to zero-fill pages like DONTNEED instead of SIGBUS. So, new flag option would be nice.

If userspace people want it, I can do it.
But not sure they want it at the moment becaue vrange is rather different concept of madvise(DONTNEED) POV usage.

As you know well, in case of DONTNEED, user calls madvise _once_ and VM releases memory as soon as he called system call.
But vrange is same with delayed free when the system memory pressure happens so user can't know OS frees the pages anytime.
It means user should call pair of system call both VRANGE_VOLATILE and VRANGE_NOVOLATILE for right usage of volatile range (for simple, I don't want to tell SIGBUS fault recovery method). If he took a mistake(ie, NOT to call VRANGE_NOVOLATILE) on the range which is used by current process, pages used by some process could be disappeared suddenly.

In summary, I don't think vrange is a replacement of madvise(DONTNEED) but could be useful with madvise(DONTNEED) friend. For example, we can make return 1 in vrange(VRANGE_VOLATILE) if memory pressure was already severe so user can catch up memory pressure by return value and calls madvise(DONTNEED) if memory pressure was already severe. Of course, we can handle it vrange system call itself(ex, change vrange system call to madvise(DONTNEED) but don't want it because I want to keep vrange hinting sytem call very light at all times so user can expect latency.

Quoted 3 lines

I played a bit this patch. The result looks really promissing. (i.e. 20x faster)

Thanks for the testing with Glibc!
Yes. Although I didn't post my KVM test result with jemalloc, it could be very good, too.

Quoted 3 lines

My machine have 24cpus, 8GB ram, kvm guest. I guess current DONTNEED implementation doesn't fit kvm at all.

Yes. I expect virtual machine MMU/cache/TLB handling would be expensive than bare box.

Quoted 4 lines

# of     # of   # of
thread   iter   iter (patched glibc)

What's the workload?

Quoted 94 lines

----------------------------------

  1      438    10740
  2      842    20916
  4      987    32534
  8      717    15155
 12      714    14109
 16      708    13457
 20      720    13742
 24      727    13642
 28      715    13328
 32      709    13096
 36      705    13661
 40      708    13634
 44      707    13367
 48      714    13377

---------libc patch (just dirty hack) ----------------------

malloc/arena.c +21 -2
index 12a48ad..da04f67 100644
@@ -365,6 +365,8 @@ extern struct dl_open_hook *_dl_open_hook;
 libc_hidden_proto (_dl_open_hook);
 #endif
 
+int vrange_enabled = 0;
+
 static void
 ptmalloc_init (void)
 {
@@ -457,6 +459,18 @@ ptmalloc_init (void)
     if (check_action != 0)
       __malloc_check_init();
   }
+
+  {
+    char *vrange = getenv("MALLOC_VRANGE");
+    if (vrange) {
+      int val = atoi(vrange);
+      if (val) {
+       printf("glibc: vrange enabled\n");
+       vrange_enabled = !!val;
+      }
+    }
+  }
+
   void (*hook) (void) = force_reg (__malloc_initialize_hook);
   if (hook != NULL)
     (*hook)();
@@ -628,9 +642,14 @@ shrink_heap(heap_info *h, long diff)
        return -2;
       h->mprotect_size = new_size;
     }
-  else
-    __madvise ((char *)h + new_size, diff, MADV_DONTNEED);
+  else {
+    if (vrange_enabled) {
+      syscall(314, (char *)h + new_size, diff, 0, 1);
+    } else {
+      __madvise ((char *)h + new_size, diff, MADV_DONTNEED);
+    }
   /*fprintf(stderr, "shrink %p %08lx\n", h, new_size);*/
+  }
 
   h->size = new_size;
   return 0;
malloc/malloc.c +7 -1
index 70b9329..3782244 100644
@@ -4403,6 +4403,7 @@ _int_pvalloc(mstate av, size_t bytes)
 /*
   ------------------------------ malloc_trim ------------------------------
 */
+extern int vrange_enabled;
 
 static int mtrim(mstate av, size_t pad)
 {
@@ -4443,7 +4444,12 @@ static int mtrim(mstate av, size_t pad)
                       content.  */
                    memset (paligned_mem, 0x89, size & ~psm1);
 #endif
-                   __madvise (paligned_mem, size & ~psm1, MADV_DONTNEED);
+
+                   if (vrange_enabled) {
+                     syscall(314, paligned_mem, size & ~psm1, 0, 1);
+                   } else {
+                     __madvise (paligned_mem, size & ~psm1, MADV_DONTNEED);
+                   }
 
                    result = 1;
                  }
Quoted 1 line

(END)

I can't find VRANGE_NOVOLATILE call in your patch so I think you just test with enough memory. I expect you wanted just fast prototype to see the performance gain. Yes, looks good although above code isn't complete since it doesn't handle purged pages.

Next step of us would optimize reclaim path so when memory pressure is severe, vrange could have a improved result rather than vanilla for avoing swap out. Any suggestion are welcome.

Signature · 8 lines
Kind regards,
Minchan Kim

--
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>
#26 lore raw
Quoted 21 lines
Quoted 5 lines
Quoted 2 lines

DONTNEED makes sure user always can see zero-fill pages after he calls madvise while vrange can see data or encounter SIGBUS.

For replacing DONTNEED, user want to zero-fill pages like DONTNEED instead of SIGBUS. So, new flag option would be nice.

If userspace people want it, I can do it.
But not sure they want it at the moment becaue vrange is rather different concept of madvise(DONTNEED) POV usage.

As you know well, in case of DONTNEED, user calls madvise _once_ and VM releases memory as soon as he called system call.
But vrange is same with delayed free when the system memory pressure happens so user can't know OS frees the pages anytime.
It means user should call pair of system call both VRANGE_VOLATILE and VRANGE_NOVOLATILE for right usage of volatile range (for simple, I don't want to tell SIGBUS fault recovery method). If he took a mistake(ie, NOT to call VRANGE_NOVOLATILE) on the range which is used by current process, pages used by some process could be disappeared suddenly.

Quoted 3 lines

In summary, I don't think vrange is a replacement of madvise(DONTNEED) but could be useful with madvise(DONTNEED) friend. For example, we can make return 1 in vrange(VRANGE_VOLATILE) if memory pressure was already

Do you mean vrange(VRANGE_UNVOLATILE)?
btw, assign new error number to asm-generic/errno.h is better than strange '1'.

Quoted 5 lines

severe so user can catch up memory pressure by return value and calls madvise(DONTNEED) if memory pressure was already severe. Of course, we can handle it vrange system call itself(ex, change vrange system call to madvise(DONTNEED) but don't want it because I want to keep vrange hinting sytem call very light at all times so user can expect latency.

For allocator usage, vrange(UNVOLATILE) is annoying and don't need at all. When data has already been purged, just return new zero filled page. so, maybe adding new flag is worthwhile. Because malloc is definitely fast path and adding new syscall invokation is unwelcome.

Quoted 4 lines
Quoted 2 lines
# of     # of   # of
thread   iter   iter (patched glibc)

What's the workload?

Ahh, sorry. I forgot to write. I use ebizzy, your favolite workload.

--
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>

#27 lore raw
Quoted 21 lines · KOSAKI Motohiro
Quoted 21 lines
Quoted 5 lines
Quoted 2 lines

DONTNEED makes sure user always can see zero-fill pages after he calls madvise while vrange can see data or encounter SIGBUS.

For replacing DONTNEED, user want to zero-fill pages like DONTNEED instead of SIGBUS. So, new flag option would be nice.

If userspace people want it, I can do it.
But not sure they want it at the moment becaue vrange is rather different concept of madvise(DONTNEED) POV usage.

As you know well, in case of DONTNEED, user calls madvise _once_ and VM releases memory as soon as he called system call.
But vrange is same with delayed free when the system memory pressure happens so user can't know OS frees the pages anytime.
It means user should call pair of system call both VRANGE_VOLATILE and VRANGE_NOVOLATILE for right usage of volatile range (for simple, I don't want to tell SIGBUS fault recovery method). If he took a mistake(ie, NOT to call VRANGE_NOVOLATILE) on the range which is used by current process, pages used by some process could be disappeared suddenly.

Quoted 5 lines
Quoted 3 lines

In summary, I don't think vrange is a replacement of madvise(DONTNEED) but could be useful with madvise(DONTNEED) friend. For example, we can make return 1 in vrange(VRANGE_VOLATILE) if memory pressure was already

Do you mean vrange(VRANGE_UNVOLATILE)?

I meant VRANGE_VOLATILE. It seems my explanation was poor. Here it goes, again. Now vrange's semantic return just 0 if the system call is successful, otherwise, return error. But we can change it as folows

1. return 0 if the system call is successful and memory pressure isn't severe
2. return 1 if the system call is successful and memory pressure is severe
3. return -ERRXXX if the system call is failed by some reason

So the process can know system-wide memory pressure without peeking the vmstat and then call madvise(DONTNEED) right after vrange call. The benefit is system can zap all pages instantly.

Quoted 1 line

btw, assign new error number to asm-generic/errno.h is better than strange '1'.

I can and admit "1" is rather weired.
But it's not error, either.

Quoted 11 lines
Quoted 7 lines

severe so user can catch up memory pressure by return value and calls madvise(DONTNEED) if memory pressure was already severe. Of course, we can handle it vrange system call itself(ex, change vrange system call to madvise(DONTNEED) but don't want it because I want to keep vrange hinting sytem call very light at all times so user can expect latency.

For allocator usage, vrange(UNVOLATILE) is annoying and don't need at all. When data has already been purged, just return new zero filled page. so, maybe adding new flag is worthwhile. Because malloc is definitely fast path

I really want it and it's exactly same with madvise(MADV_FREE). But for implementation, we need page granularity someting in address range in system call context like zap_pte_range(ex, clear page table bits and mark something to page flags for reclaimer to detect it).
It means vrange system call is still bigger although we are able to remove lazy page fault.

Do you have any idea to remove it? If so, I'm very open to implement it.

Quoted 1 line

and adding new syscall invokation is unwelcome.

Sure. But one more system call could be cheaper than page-granuarity operation on purged range.

Quoted 16 lines
Quoted 6 lines
Quoted 4 lines

# of     # of   # of
thread   iter   iter (patched glibc)

What's the workload?

Ahh, sorry. I forgot to write. I use ebizzy, your favolite workload.

--
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>

Signature · 8 lines
Kind regards,
Minchan Kim

--
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>
#28 lore raw
Quoted 32 lines · Minchan Kim
Quoted 21 lines · KOSAKI Motohiro
Quoted 21 lines
Quoted 5 lines
Quoted 2 lines

DONTNEED makes sure user always can see zero-fill pages after he calls madvise while vrange can see data or encounter SIGBUS.

For replacing DONTNEED, user want to zero-fill pages like DONTNEED instead of SIGBUS. So, new flag option would be nice.

If userspace people want it, I can do it.
But not sure they want it at the moment becaue vrange is rather different concept of madvise(DONTNEED) POV usage.

As you know well, in case of DONTNEED, user calls madvise _once_ and VM releases memory as soon as he called system call.
But vrange is same with delayed free when the system memory pressure happens so user can't know OS frees the pages anytime.
It means user should call pair of system call both VRANGE_VOLATILE and VRANGE_NOVOLATILE for right usage of volatile range (for simple, I don't want to tell SIGBUS fault recovery method). If he took a mistake(ie, NOT to call VRANGE_NOVOLATILE) on the range which is used by current process, pages used by some process could be disappeared suddenly.

Quoted 5 lines
Quoted 3 lines

In summary, I don't think vrange is a replacement of madvise(DONTNEED) but could be useful with madvise(DONTNEED) friend. For example, we can make return 1 in vrange(VRANGE_VOLATILE) if memory pressure was already

Do you mean vrange(VRANGE_UNVOLATILE)?

I meant VRANGE_VOLATILE. It seems my explanation was poor. Here it goes, again. Now vrange's semantic return just 0 if the system call is successful, otherwise, return error. But we can change it as folows

Quoted 7 lines

1. return 0 if the system call is successful and memory pressure isn't severe
2. return 1 if the system call is successful and memory pressure is severe
3. return -ERRXXX if the system call is failed by some reason

So the process can know system-wide memory pressure without peeking the vmstat and then call madvise(DONTNEED) right after vrange call. The benefit is system can zap all pages instantly.

Do you mean your patchset is not latest? and when do you use this feature? what's happen VRANGE_VOLATILE return 0 and purge the range just after returning syscall.

Quoted 4 lines
Quoted 1 line

btw, assign new error number to asm-generic/errno.h is better than strange '1'.

I can and admit "1" is rather weired.
But it's not error, either.

If this is really necessary, I don't oppose it. However I am still not convinced.

Quoted 10 lines
Quoted 9 lines
Quoted 5 lines

severe so user can catch up memory pressure by return value and calls madvise(DONTNEED) if memory pressure was already severe. Of course, we can handle it vrange system call itself(ex, change vrange system call to madvise(DONTNEED) but don't want it because I want to keep vrange hinting sytem call very light at all times so user can expect latency.

For allocator usage, vrange(UNVOLATILE) is annoying and don't need at all. When data has already been purged, just return new zero filled page. so, maybe adding new flag is worthwhile. Because malloc is definitely fast path

Quoted 8 lines

I really want it and it's exactly same with madvise(MADV_FREE). But for implementation, we need page granularity someting in address range in system call context like zap_pte_range(ex, clear page table bits and mark something to page flags for reclaimer to detect it).
It means vrange system call is still bigger although we are able to remove lazy page fault.

Do you have any idea to remove it? If so, I'm very open to implement it.

Hm. Maybe I am missing something. I'll look the code closely after LFS.

Quoted 4 lines
Quoted 1 line

and adding new syscall invokation is unwelcome.

Sure. But one more system call could be cheaper than page-granuarity operation on purged range.

I don't think vrange(VOLATILE) cost is the related of this discusstion. Whether sending SIGBUS or just nuke pte, purge should be done on vmscan, not vrange() syscall.

--
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>

#29 lore raw
Quoted 37 lines · KOSAKI Motohiro
Quoted 36 lines · Minchan Kim
Quoted 21 lines · KOSAKI Motohiro
Quoted 21 lines
Quoted 5 lines
Quoted 2 lines

DONTNEED makes sure user always can see zero-fill pages after he calls madvise while vrange can see data or encounter SIGBUS.

For replacing DONTNEED, user want to zero-fill pages like DONTNEED instead of SIGBUS. So, new flag option would be nice.

If userspace people want it, I can do it.
But not sure they want it at the moment becaue vrange is rather different concept of madvise(DONTNEED) POV usage.

As you know well, in case of DONTNEED, user calls madvise _once_ and VM releases memory as soon as he called system call.
But vrange is same with delayed free when the system memory pressure happens so user can't know OS frees the pages anytime.
It means user should call pair of system call both VRANGE_VOLATILE and VRANGE_NOVOLATILE for right usage of volatile range (for simple, I don't want to tell SIGBUS fault recovery method). If he took a mistake(ie, NOT to call VRANGE_NOVOLATILE) on the range which is used by current process, pages used by some process could be disappeared suddenly.

Quoted 5 lines
Quoted 3 lines

In summary, I don't think vrange is a replacement of madvise(DONTNEED) but could be useful with madvise(DONTNEED) friend. For example, we can make return 1 in vrange(VRANGE_VOLATILE) if memory pressure was already

Do you mean vrange(VRANGE_UNVOLATILE)?

I meant VRANGE_VOLATILE. It seems my explanation was poor. Here it goes, again. Now vrange's semantic return just 0 if the system call is successful, otherwise, return error. But we can change it as folows

1. return 0 if the system call is successful and memory pressure isn't severe
2. return 1 if the system call is successful and memory pressure is severe
3. return -ERRXXX if the system call is failed by some reason

Quoted 5 lines
Quoted 3 lines

So the process can know system-wide memory pressure without peeking the vmstat and then call madvise(DONTNEED) right after vrange call. The benefit is system can zap all pages instantly.

Do you mean your patchset is not latest? and when do you use this feature? what's

Yes. I meant I can it in next spin up for hearing the opinion.

Quoted 1 line

happen VRANGE_VOLATILE return 0 and purge the range just after returning syscall.

It could be an idea but I will think it over.

Quoted 28 lines
Quoted 6 lines
Quoted 3 lines

btw, assign new error number to asm-generic/errno.h is better than strange '1'.

I can and admit "1" is rather weired.
But it's not error, either.

If this is really necessary, I don't oppose it. However I am still not convinced.

Quoted 17 lines
Quoted 9 lines
Quoted 5 lines

severe so user can catch up memory pressure by return value and calls madvise(DONTNEED) if memory pressure was already severe. Of course, we can handle it vrange system call itself(ex, change vrange system call to madvise(DONTNEED) but don't want it because I want to keep vrange hinting sytem call very light at all times so user can expect latency.

For allocator usage, vrange(UNVOLATILE) is annoying and don't need at all. When data has already been purged, just return new zero filled page. so, maybe adding new flag is worthwhile. Because malloc is definitely fast path

I really want it and it's exactly same with madvise(MADV_FREE). But for implementation, we need page granularity someting in address range in system call context like zap_pte_range(ex, clear page table bits and mark something to page flags for reclaimer to detect it).
It means vrange system call is still bigger although we are able to remove lazy page fault.

Quoted 3 lines
Quoted 1 line

Do you have any idea to remove it? If so, I'm very open to implement it.

Hm. Maybe I am missing something. I'll look the code closely after LFS.

Please see the Rik's old work about MADV_FREE.

Quoted 10 lines
Quoted 6 lines
Quoted 3 lines

and adding new syscall invokation is unwelcome.

Sure. But one more system call could be cheaper than page-granuarity operation on purged range.

I don't think vrange(VOLATILE) cost is the related of this discusstion. Whether sending SIGBUS or just nuke pte, purge should be done on vmscan, not vrange() syscall.

Again, please see the MADV_FREE. http://lwn.net/Articles/230799/
It does changes pte and page flags on all pages of the range through zap_pte_range. So it would make vrange(VOLASTILE) expensive and the bigger cost is, the bigger range is.

Quoted 14 lines

--
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>

Signature · 8 lines
Kind regards,
Minchan Kim

--
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>
#30 lore raw
Quoted 5 lines
Quoted 5 lines
Quoted 4 lines
Quoted 1 line

and adding new syscall invokation is unwelcome.

Sure. But one more system call could be cheaper than page-granuarity operation on purged range.

Quoted 8 lines
Quoted 3 lines

I don't think vrange(VOLATILE) cost is the related of this discusstion. Whether sending SIGBUS or just nuke pte, purge should be done on vmscan, not vrange() syscall.

Again, please see the MADV_FREE. http://lwn.net/Articles/230799/
It does changes pte and page flags on all pages of the range through zap_pte_range. So it would make vrange(VOLASTILE) expensive and the bigger cost is, the bigger range is.

This haven't been crossed my mind. now try_to_discard_one() insert vrange for making SIGBUS. then, we can insert pte_none() as the same cost too. Am I missing something?

I couldn't imazine why pte should be zapping on vrange(VOLATILE).

--
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>

#31 lore raw

Hi KOSAKI,

Quoted 9 lines · KOSAKI Motohiro
Quoted 9 lines
Quoted 8 lines
Quoted 4 lines
Quoted 1 line

and adding new syscall invokation is unwelcome.

Sure. But one more system call could be cheaper than page-granuarity operation on purged range.

I don't think vrange(VOLATILE) cost is the related of this discusstion. Whether sending SIGBUS or just nuke pte, purge should be done on vmscan, not vrange() syscall.

Quoted 8 lines
Quoted 4 lines

Again, please see the MADV_FREE. http://lwn.net/Articles/230799/
It does changes pte and page flags on all pages of the range through zap_pte_range. So it would make vrange(VOLASTILE) expensive and the bigger cost is, the bigger range is.

This haven't been crossed my mind. now try_to_discard_one() insert vrange for making SIGBUS. then, we can insert pte_none() as the same cost too. Am I missing something?

For your requirement, we need some tracking model to detect some page is using by the process currently before VM discards it *if* we don't give vrange(NOVOLATILE) pair system call(Look at below). So the tracking model should be formed in vrange(VOLATILE) system call context.

Quoted 2 lines

I couldn't imazine why pte should be zapping on vrange(VOLATILE).

Sorry, my explanation was too bad to understand.
I will try again.

First of all, thing you want is almost like MADV_FREE. So let's look at it firstly.

If you call madvise(range, MADV_FREE), VM should investigate all of pages mapped at page table for range(start, start + len) so we need page table lookup for the range and mark a flag to all page descriptor (ex,PG_lazyfree) to give hint to kernel for discarding the page instead of swappint out when reclaim happens. Another thing we need is to clear out a dirty bit from PTE to detect the pages is dirtied or not, since we call madvise(range, MADV_FREE) because we can't discard them, which are using by some process since he called madvise. So if VM find the page has PG_lazyfree but the page is dirtied recenlty by peeking PTE, VM can't discard the page. So madivse system call's overhead is folloinwg as in madvise(MADV_FREE)

1. look up all pages from page table for the range.
2. mark some bit(PG_lazyfree) for page descriptors of pages mapped at range
3. clear dirty bit and TLB flush

So, madvise(MADV_FREE) would be better than madvise(DONTNEED) because it can avoid page fault if memory pressure doesn't happen but system call overhead could be still huge and expecially the overhead is increased proportionally by range size.

Let's talk about vrange(range, VOLATILE)
The overhead of it is very small, which is just mark a flag into a structure which represents the range (ie, struct vrange). When VM want to reclaim some pages, VM find a page is mapped at VOLATILE area, so it could discard it instead of swapping out. It moves the ovehead from system call itself to VM reclaim path which is very slow path in the system and I think it's desirable design(And that's why we have rmap).
But the problem is remained. VM can't detect page using by process after he calls vrange(range, VOLATILE) because we didn't do anything in vrange(VOLATILE) so VM might discard the page under the process. It didn't happen in madvise(MADV_FREE) because it cleared out dirty bit of PTE to detect the page is used or not since madvise is called.

Solution in vrange is to make new vrange(range, NOVOLATILE) system call, which give the hint to kernel for preventing descarding pages in the range any more. The cost of vrange(range, NOVOLATILE) is very small, too.
It just clear out the flags from a struct vrange which represents a range.

So I think calling of pair system call about volatile would be cheaper than a only madvise(MADV_FREE).

I hope it helps your understanding but not sure because I am writing this in airport which are very hard to focus my work. :(

Quoted 6 lines

--
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>

Signature · 8 lines
Kind regards,
Minchan Kim

--
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>
#32 lore raw
Quoted 13 lines · Minchan Kim

Hi KOSAKI,

Quoted 10 lines · KOSAKI Motohiro
Quoted 10 lines
Quoted 6 lines
Quoted 3 lines
Quoted 1 line

and adding new syscall invokation is unwelcome.

Sure. But one more system call could be cheaper than page-granuarity operation on purged range.

I don't think vrange(VOLATILE) cost is the related of this discusstion. Whether sending SIGBUS or just nuke pte, purge should be done on vmscan, not vrange() syscall.

Again, please see the MADV_FREE. http://lwn.net/Articles/230799/
It does changes pte and page flags on all pages of the range through zap_pte_range. So it would make vrange(VOLASTILE) expensive and the bigger cost is, the bigger range is.

Quoted 7 lines
Quoted 3 lines

This haven't been crossed my mind. now try_to_discard_one() insert vrange for making SIGBUS. then, we can insert pte_none() as the same cost too. Am I missing something?

For your requirement, we need some tracking model to detect some page is using by the process currently before VM discards it *if* we don't give vrange(NOVOLATILE) pair system call(Look at below). So the tracking model should be formed in vrange(VOLATILE) system call context.

To further clarify Minchan's note here, the reason its important for the application to use vrange(NOVOLATILE), its really to help define _when the range stops being volatile_.

In your libc hack to use vrange(), you see the benfit of not immediately purging the memory as you do with MADV_DONTNEED. However, if the heap grows again, and those address are re-used, nothing has stopped those pages from continuing to be volatile. Thus the kernel could then decide to purge those pages after they start to be used again, and you'd lose data. I suspect that's not what you want. :)

Rik's MADV_FREE implementation is very similar to vrange(VOLATILE), but has an implicit vrange(NOVOLATILE) on any page write. So by dirtying a page, it stops the kernel from later purging it.

This MADV_FREE semantic works very well if you always want zerofill (as in the case of malloc/free). But for other data, its important to know something was lost (as a zero page could be valid data), and that's why we provide the SIGBUS, as well as the purged notification on vrange(NOVOLATILE).

In other-words, as long as you do a vrange(NOVOLATILE) when you grow the heap again (before its used), it should be very similar to the MADV_FREE behavior, but is more flexible for other use cases.

thanks
-john

--
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>