RFC: mincore: add a bit to indicate a page is dirty.

I am writing an app which really wants to know if a file is on the disk or not (ie. do I need to sync?).

mincore() bits other than 0 are undefined (as documented in the man page); in fact my Ubuntu 12.10 i386 system seems to write 129 in some bytes, so it really shouldn't break anyone.

Is PG_dirty the right choice? Is that right for huge pages? Should I assume is_migration_entry(entry) means it's not dirty, or is there some other check here?

(quoted diff) +0 -0

@@ -36,7 +39,15 @@ static void mincore_hugetlb_page_range(struct vm_area_struct *vma,
 		 */
 		ptep = huge_pte_offset(current->mm,
 				       addr & huge_page_mask(h));

Quoted 3 lines

Is PG_dirty the right choice? Is that right for huge pages? Should I assume is_migration_entry(entry) means it's not dirty, or is there some other check here?

If your only consequence of finding dirty pages is to sync, would you be better off using fsync/fdatasync maybe?

Quoted 6 lines · On Mon, 11 Feb 2013 11:27:01 -0500 Johannes Weiner <[email protected]> wrote:

Quoted 3 lines

Is PG_dirty the right choice? Is that right for huge pages? Should I assume is_migration_entry(entry) means it's not dirty, or is there some other check here?

If your only consequence of finding dirty pages is to sync, would you be better off using fsync/fdatasync maybe?

Yes, if the data is all on disk then an fsync() will be a no-op. IOW,

	if (I need to fsync)
		fsync();

is equivalent to

	fsync();

Methinks we need to understand the requirement better.

Also, having to mmap the file to be able to query pagecache state is a hack. Whatever happened to the fincore() patch?

Also, having to mmap the file to be able to query pagecache state is a hack. Whatever happened to the fincore() patch?

Quoted 2 lines · Andrew Morton

Also, having to mmap the file to be able to query pagecache state is a hack. Whatever happened to the fincore() patch?

I don't know, but how about this one:

Provide a syscall to determine whether a given file's pages are cached in memory. This is more elegant than mmapping the file for the sole purpose of using mincore(), and also works on NOMMU.

mm/fincore.c new file +15 -0

@@ -0,0 +1,128 @@
+#include <linux/syscalls.h>
+#include <linux/pagemap.h>
+#include <linux/file.h>
+#include <linux/fs.h>
+#include <linux/mm.h>
+
+static long do_fincore(struct address_space *mapping, pgoff_t pgstart,
+		       unsigned long nr_pages, unsigned char *vec)
+{
+	pgoff_t pgend = pgstart + nr_pages;
+	struct radix_tree_iter iter;
+	void **slot;
+	long nr = 0;
+
+	rcu_read_lock();

mm/fincore.c new file +12 -0

+		if (radix_tree_exception(page)) {
+			if (radix_tree_deref_retry(page)) {
+				/*
+				 * Transient condition which can only trigger
+				 * when entry at index 0 moves out of or back
+				 * to root: none yet gotten, safe to restart.
+				 */
+				WARN_ON(iter.index);
+				goto restart;
+			}
+			present = 0;
+		} else {

mm/fincore.c new file +13 -0

+			page_cache_release(page);
+		}
+		vec[nr] = present;
+
+		if (++nr == nr_pages)
+			break;
+	}
+	rcu_read_unlock();
+
+	if (nr < nr_pages)
+		memset(vec + nr, 0, nr_pages - nr);
+
+	return nr_pages;

mm/fincore.c new file +10 -0

+ * Because the status of a page can change after fincore() checks it
+ * but before it returns to the application, the returned vector may
+ * contain stale information.
+ *
+ * return values:
+ *  zero    - success
+ *  -EBADF  - fd isn't a valid open file descriptor
+ *  -EFAULT - vec points to an illegal address
+ *  -EINVAL - start is not a multiple of PAGE_CACHE_SIZE
+ */

mm/fincore.c new file +16 -0

+	pgstart = start >> PAGE_CACHE_SHIFT;
+	nr_pages = DIV_ROUND_UP(len, PAGE_CACHE_SIZE);
+
+	while (nr_pages) {
+		unsigned char tmp[64];
+
+		ret = do_fincore(f.file->f_mapping, pgstart,
+				 min(nr_pages, sizeof(tmp)), tmp);
+		if (ret <= 0)
+			break;
+
+		if (copy_to_user(vec, tmp, ret)) {
+			ret = -EFAULT;
+			break;
+		}
+

Quoted 1 line · On Fri, 15 Feb 2013 01:34:50 -0500 Johannes Weiner <[email protected]> wrote:

On Mon, Feb 11, 2013 at 02:12:39PM -0800, Andrew Morton wrote:

Quoted 4 lines

Quoted 2 lines

Also, having to mmap the file to be able to query pagecache state is a hack. Whatever happened to the fincore() patch?

I don't know, but how about this one:

This appears to be remotely derived from Chris's original
(http://lwn.net/Articles/371540/). The comments, at least ;) Some mention in the changelog would be appropriate.

Quoted 4 lines

Provide a syscall to determine whether a given file's pages are cached in memory. This is more elegant than mmapping the file for the sole purpose of using mincore(), and also works on NOMMU.

Obviously we'll be needing more than this at the appropriate time so Michael can write the manpage.

Please provide a nice tools/testing/selftests/fincore/ along with this code?

Quoted 23 lines

mm/fincore.c new file +20 -0

@@ -0,0 +1,128 @@
+#include <linux/syscalls.h>
+#include <linux/pagemap.h>
+#include <linux/file.h>
+#include <linux/fs.h>
+#include <linux/mm.h>
+
+static long do_fincore(struct address_space *mapping, pgoff_t pgstart,
+		       unsigned long nr_pages, unsigned char *vec)
+{
+	pgoff_t pgend = pgstart + nr_pages;
+	struct radix_tree_iter iter;
+	void **slot;
+	long nr = 0;
+
+	rcu_read_lock();
+restart:
+	radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, pgstart) {
+		unsigned char present;
+		struct page *page;
+

mm/fincore.c line 25

Quoted 5 lines

mm/fincore.c new file +5 -0

+		/* Handle holes */
+		if (iter.index != pgstart + nr) {
+			if (iter.index < pgend)
+				nr_pages = iter.index - pgstart;
+			break;

This break looks odd - it terminates the entire function. Am too lazy to work out why ;)

mm/fincore.c line 30

Quoted 5 lines

mm/fincore.c new file +5 -0

+		}
+repeat:
+		page = radix_tree_deref_slot(slot);
+		if (unlikely(!page))
+			continue;

Is a bug, isn't it? Need to zero vec[nr].

Quoted 17 lines

mm/fincore.c new file +17 -0

+		if (radix_tree_exception(page)) {
+			if (radix_tree_deref_retry(page)) {
+				/*
+				 * Transient condition which can only trigger
+				 * when entry at index 0 moves out of or back
+				 * to root: none yet gotten, safe to restart.
+				 */
+				WARN_ON(iter.index);
+				goto restart;
+			}
+			present = 0;
+		} else {
+			if (!page_cache_get_speculative(page))
+				goto repeat;
+
+			/* Has the page moved? */
+			if (unlikely(page != *slot)) {

mm/fincore.c line 53

Quoted 5 lines

mm/fincore.c new file +5 -0

+				page_cache_release(page);
+				goto repeat;
+			}
+
+			present = PageUptodate(page);

hm, OK, so we assume that test_bit() returns 1 or 0 and not just "true". That's OK, iirc.

Why does it have to be uptodate? It could be present and under read() IO. That's "in core"?

Quoted 20 lines

mm/fincore.c new file +20 -0

+			page_cache_release(page);
+		}
+		vec[nr] = present;
+
+		if (++nr == nr_pages)
+			break;
+	}
+	rcu_read_unlock();
+
+	if (nr < nr_pages)
+		memset(vec + nr, 0, nr_pages - nr);
+
+	return nr_pages;
+}
+
+/*
+ * The fincore(2) system call.
+ *
+ * fincore() returns the memory residency status of the given file's
+ * pages, in the range [start, start + len].

mm/fincore.c line 76

Quoted 3 lines

mm/fincore.c new file +3 -0

+ * The status is returned in a vector of bytes.  The least significant
+ * bit of each byte is 1 if the referenced page is in memory, otherwise
+ * it is zero.

Yes, and there will be immediate calmour to add more goodies to the other seven bits. PageDirty, referenced state, etc. We should think about this now, at the design stage rather than grafting things on later.

Quoted 14 lines

mm/fincore.c new file +14 -0

+ * Because the status of a page can change after fincore() checks it
+ * but before it returns to the application, the returned vector may
+ * contain stale information.
+ *
+ * return values:
+ *  zero    - success
+ *  -EBADF  - fd isn't a valid open file descriptor
+ *  -EFAULT - vec points to an illegal address
+ *  -EINVAL - start is not a multiple of PAGE_CACHE_SIZE
+ */
+SYSCALL_DEFINE4(fincore, unsigned int, fd, loff_t, start, loff_t, len,
+		unsigned char __user *, vec)
+{
+	unsigned long nr_pages;

mm/fincore.c line 97

Quoted 6 lines

mm/fincore.c new file +6 -0

+	pgoff_t pgstart;
+	struct fd f;
+	long ret;
+
+	if (start & ~PAGE_CACHE_MASK)
+		return -EINVAL;

This restriction appears to be unnecessary?

mm/fincore.c line 101

Quoted 3 lines

mm/fincore.c new file +3 -0

+	f = fdget(fd);
+	if (!f.file)
+		return -EBADF;

I fear what happens if we run this syscall against a random fd from /dev/some-gizmo. Suggest adding tests for S_ISREG and non-null ->mapping.

Quoted 4 lines

Yes, and there will be immediate calmour to add more goodies to the other seven bits. PageDirty, referenced state, etc. We should think about this now, at the design stage rather than grafting things on later.

I'm interested in your "etc.". PG_error, PG_active, PG_writeback, page huge?

+ * The status is returned in a vector of bytes. The least significant
+ * bit of each byte is 1 if the referenced page is in memory, otherwise
+ * it is zero.

Quoted 3 lines · On Fri, 15 Feb 2013 01:34:50 -0500 Johannes Weiner <[email protected]> wrote:

+ * The status is returned in a vector of bytes. The least significant
+ * bit of each byte is 1 if the referenced page is in memory, otherwise
+ * it is zero.

Also, this is going to be dreadfully inefficient for some obvious cases.

We could address that by returning the info in some more efficient representation. That will be run-length encoded in some fashion.

The obvious way would be to populate an array of

struct page_status {
	u32 present:1;
	u32 count:31;
};

or whatever.

Another way would be to define the syscall so it returns "number of pages present/absent starting at offset start'". In other words, one call to fincore() will return a single struct page_status'. Userspace can then walk through the file and generate the full picture, if needed.

This also gets inefficient in obvious cases, but it's not as obviously bad?

Quoted 19 lines · Andrew Morton

Quoted 3 lines · On Fri, 15 Feb 2013 01:34:50 -0500 Johannes Weiner <[email protected]> wrote:

+ * The status is returned in a vector of bytes. The least significant
+ * bit of each byte is 1 if the referenced page is in memory, otherwise
+ * it is zero.

Also, this is going to be dreadfully inefficient for some obvious cases.

We could address that by returning the info in some more efficient representation. That will be run-length encoded in some fashion.

The obvious way would be to populate an array of

struct page_status {
	u32 present:1;
	u32 count:31;
};

Quoted 1 line

or whatever.

I'm having a hard time seeing how this could be extended to more status bits without stifling the optimization too much.

If we just
add more status bits to one page_status, the likelihood of long runs where all bits are in agreement decreases. But as the optimization becomes less and less effective, we are stuck with an interface that is more PITA than just using mmap and mincore again.

The user has to supply a worst-case-sized vector with one struct page_status per page in the range, but the per-page item will be bigger than with the byte vector because of the additional run length variable.

However, one struct page_status per run leaves you with a worst case of one syscall per page in the range.

I dunno. The byte vector might not be optimal but its worst cases seem more attractive, is just as extensible, and dead simple to use.

Quoted 2 lines · On Fri, 15 Feb 2013 18:13:04 -0500 Johannes Weiner <[email protected]> wrote:

I dunno. The byte vector might not be optimal but its worst cases seem more attractive, is just as extensible, and dead simple to use.

But I think "which pages from this 4TB file are in core" will not be an uncommon usage, and writing a gig of memory to find three pages is just awful.

Quoted 8 lines · Andrew Morton

Quoted 2 lines · On Fri, 15 Feb 2013 18:13:04 -0500 Johannes Weiner <[email protected]> wrote:

I dunno. The byte vector might not be optimal but its worst cases seem more attractive, is just as extensible, and dead simple to use.

But I think "which pages from this 4TB file are in core" will not be an uncommon usage, and writing a gig of memory to find three pages is just awful.

Actually, I don't know of any usage for this call.

I'd really like to use it for backup programs, so they stop pulling random crap into memory (but leave things already resident). But that needs to madvise(MADV_DONTNEED) on the page, so need mmap.

Quoted 8 lines · Andrew Morton

Quoted 2 lines · On Fri, 15 Feb 2013 18:13:04 -0500 Johannes Weiner <[email protected]> wrote:

I dunno. The byte vector might not be optimal but its worst cases seem more attractive, is just as extensible, and dead simple to use.

But I think "which pages from this 4TB file are in core" will not be an uncommon usage, and writing a gig of memory to find three pages is just awful.

Actually, I don't know of any usage for this call.

I'd really like to use it for backup programs, so they stop pulling random crap into memory (but leave things already resident). But that needs to madvise(MADV_DONTNEED) on the page, so need mmap.

So why not just use mincore?

Quoted 8 lines · Andrew Morton

Quoted 2 lines · On Fri, 15 Feb 2013 18:13:04 -0500 Johannes Weiner <[email protected]> wrote:

I dunno. The byte vector might not be optimal but its worst cases seem more attractive, is just as extensible, and dead simple to use.

But I think "which pages from this 4TB file are in core" will not be an uncommon usage, and writing a gig of memory to find three pages is just awful.

Actually, I don't know of any usage for this call.

Quoted 10 lines · Rusty Russell

Quoted 8 lines · Andrew Morton

Quoted 2 lines · On Fri, 15 Feb 2013 18:13:04 -0500 Johannes Weiner <[email protected]> wrote:

I dunno. The byte vector might not be optimal but its worst cases seem more attractive, is just as extensible, and dead simple to use.

But I think "which pages from this 4TB file are in core" will not be an uncommon usage, and writing a gig of memory to find three pages is just awful.

Quoted 1 line

Actually, I don't know of any usage for this call.

[months later, catching up]

I do. Postgres' could really use something like that for making saner assumptions about the cost of doing an index/heap scan. postgres doesn't use mmap() and mmaping larger files into memory isn't all that cheap (32bit...) so having fincore would be nice.

Quoted 15 lines · Andres Freund

Quoted 11 lines · Rusty Russell

Quoted 8 lines · Andrew Morton

Quoted 2 lines · On Fri, 15 Feb 2013 18:13:04 -0500 Johannes Weiner <[email protected]> wrote:

I dunno. The byte vector might not be optimal but its worst cases seem more attractive, is just as extensible, and dead simple to use.

But I think "which pages from this 4TB file are in core" will not be an uncommon usage, and writing a gig of memory to find three pages is just awful.

Actually, I don't know of any usage for this call.

[months later, catching up]

Quoted 4 lines

I do. Postgres' could really use something like that for making saner assumptions about the cost of doing an index/heap scan. postgres doesn't use mmap() and mmaping larger files into memory isn't all that cheap (32bit...) so having fincore would be nice.

How much of the areas you want to use it against is usually cached? I.e. are those 4TB files with 3 cached pages?

I do wonder if we should just have two separate interfaces. Ugly, but I don't really see how the two requirements (dense but many holes vs. huge sparse areas) could be acceptably met with one interface.

The syscall should handle the common usages very well. But it shouldn't handle uncommon usages very badly!

Quoted 2 lines · Andrew Morton

Also, having to mmap the file to be able to query pagecache state is a hack. Whatever happened to the fincore() patch?

I don't know, but how about this one:

---
From: Johannes Weiner <[email protected]>
Subject: [patch 1/2] mm: fincore()

Provide a syscall to determine whether a given file's pages are cached in memory. This is more elegant than mmapping the file for the sole purpose of using mincore(), and also works on NOMMU.

Signed-off-by Johannes Weiner <[email protected]>

---
  include/linux/syscalls.h |   2 +
  mm/Makefile              |   2 +-
  mm/fincore.c             | 128 +++++++++++++++++++++++++++++++++++++++++++++++
  3 files changed, 131 insertions(+), 1 deletion(-)

create mode 100644 mm/fincore.c

include/linux/syscalls.h +2 -0

index 313a8e0..3ceab2a 100644
@@ -897,4 +897,6 @@ asmlinkage long sys_process_vm_writev(pid_t pid,
  asmlinkage long sys_kcmp(pid_t pid1, pid_t pid2, int type,
  			 unsigned long idx1, unsigned long idx2);
  asmlinkage long sys_finit_module(int fd, const char __user *uargs, int flags);
+asmlinkage long sys_fincore(unsigned int fd, loff_t start, loff_t len,
+			    unsigned char __user * vec);
  #endif

mm/Makefile +1 -1

index 185a22b..221cdae 100644
@@ -17,7 +17,7 @@ obj-y			:= filemap.o mempool.o oom_kill.o fadvise.o \
  			   util.o mmzone.o vmstat.o backing-dev.o \
  			   mm_init.o mmu_context.o percpu.o slab_common.o \
  			   compaction.o balloon_compaction.o \
-			   interval_tree.o $(mmu-y)
+			   interval_tree.o fincore.o $(mmu-y)
 
  obj-y += init-mm.o
 

mm/fincore.c new file +118 -0

new file mode 100644
index 0000000..d504611
@@ -0,0 +1,128 @@
+#include <linux/syscalls.h>
+#include <linux/pagemap.h>
+#include <linux/file.h>
+#include <linux/fs.h>
+#include <linux/mm.h>
+
+static long do_fincore(struct address_space *mapping, pgoff_t pgstart,
+		       unsigned long nr_pages, unsigned char *vec)
+{
+	pgoff_t pgend = pgstart + nr_pages;
+	struct radix_tree_iter iter;
+	void **slot;
+	long nr = 0;
+
+	rcu_read_lock();
+restart:
+	radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, pgstart) {
+		unsigned char present;
+		struct page *page;
+
+		/* Handle holes */
+		if (iter.index != pgstart + nr) {
+			if (iter.index < pgend)
+				nr_pages = iter.index - pgstart;
+			break;
+		}
+repeat:
+		page = radix_tree_deref_slot(slot);
+		if (unlikely(!page))
+			continue;
+
+		if (radix_tree_exception(page)) {
+			if (radix_tree_deref_retry(page)) {
+				/*
+				 * Transient condition which can only trigger
+				 * when entry at index 0 moves out of or back
+				 * to root: none yet gotten, safe to restart.
+				 */
+				WARN_ON(iter.index);
+				goto restart;
+			}
+			present = 0;
+		} else {
+			if (!page_cache_get_speculative(page))
+				goto repeat;
+
+			/* Has the page moved? */
+			if (unlikely(page != *slot)) {
+				page_cache_release(page);
+				goto repeat;
+			}
+
+			present = PageUptodate(page);
+			page_cache_release(page);
+		}
+		vec[nr] = present;
+
+		if (++nr == nr_pages)
+			break;
+	}
+	rcu_read_unlock();
+
+	if (nr < nr_pages)
+		memset(vec + nr, 0, nr_pages - nr);
+
+	return nr_pages;
+}
+
+/*
+ * The fincore(2) system call.
+ *
+ * fincore() returns the memory residency status of the given file's
+ * pages, in the range [start, start + len].
+ * The status is returned in a vector of bytes.  The least significant
+ * bit of each byte is 1 if the referenced page is in memory, otherwise
+ * it is zero.
+ *
+ * Because the status of a page can change after fincore() checks it
+ * but before it returns to the application, the returned vector may
+ * contain stale information.
+ *
+ * return values:
+ *  zero    - success
+ *  -EBADF  - fd isn't a valid open file descriptor
+ *  -EFAULT - vec points to an illegal address
+ *  -EINVAL - start is not a multiple of PAGE_CACHE_SIZE
+ */
+SYSCALL_DEFINE4(fincore, unsigned int, fd, loff_t, start, loff_t, len,
+		unsigned char __user *, vec)
+{
+	unsigned long nr_pages;
+	pgoff_t pgstart;
+	struct fd f;
+	long ret;
+
+	if (start & ~PAGE_CACHE_MASK)
+		return -EINVAL;
+
+	f = fdget(fd);
+	if (!f.file)
+		return -EBADF;
+
+	pgstart = start >> PAGE_CACHE_SHIFT;
+	nr_pages = DIV_ROUND_UP(len, PAGE_CACHE_SIZE);
+
+	while (nr_pages) {
+		unsigned char tmp[64];
+
+		ret = do_fincore(f.file->f_mapping, pgstart,
+				 min(nr_pages, sizeof(tmp)), tmp);
+		if (ret <= 0)
+			break;
+
+		if (copy_to_user(vec, tmp, ret)) {
+			ret = -EFAULT;
+			break;
+		}
+

Quoted 2 lines · Rusty Russell

I am writing an app which really wants to know if a file is on the disk or not (ie. do I need to sync?).

When the page is under writeback, it's not necessarily on disk yet, but you also don't need to sync. Which semantics make more sense?

I'm leaning toward checking both PG_dirty and PG_writeback.