lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  linux-cve-announce  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:	Thu, 21 Jan 2010 17:29:29 -0800
From:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To:	Chris Frost <frost@...ucla.edu>
Cc:	Heiko Carstens <heiko.carstens@...ibm.com>,
	Alexander Viro <viro@...iv.linux.org.uk>,
	Benny Halevy <bhalevy@...asas.com>,
	Andrew Morton <akpm@...ux-foundation.org>,
	linux-fsdevel@...r.kernel.org, linux-mm@...ck.org,
	linux-kernel@...r.kernel.org,
	Steve VanDeBogart <vandebo-lkml@...dbox.net>
Subject: Re: [PATCH] fs: add fincore(2) (mincore(2) for file descriptors)

On Wed, Jan 20, 2010 at 01:57:12PM -0800, Chris Frost wrote:
> Add the fincore() system call. fincore() is mincore() for file descriptors.
> 
> The functionality of fincore() can be emulated with an mmap(), mincore(),
> and munmap(), but this emulation requires more system calls and requires
> page table modifications. fincore() can provide a significant performance
> improvement for non-sequential in-core queries.
> 
> Signed-off-by: Chris Frost <frost@...ucla.edu>
> Signed-off-by: Steve VanDeBogart <vandebo@...ucla.edu>
> ---
> 
> Notes on micro and macro performance and on a potential optimization:
> 
> For a microbenchmark that sequentially queries whether the pages of a large
> file are in memory fincore is 7-11x faster than mmap+mincore+munmap
> when querying one page a time (Pentium 4 running a 32 bit SMP kernel).
> When querying 1024 pages at a time the two approaches perform comparably.
> However, an application cannot always amortize calls; e.g., non-sequential
> reads. These improvements are increased significantly by amortizing the
> RCU work done by each find_get_page() call, but this optimization does
> not affect our macrobenchmarks (more in third paragraph).
> 
> We introduced this system call while modifying SQLite and the GIMP to
> request large prefetches for what would otherwise be non-sequential reads.
> As a macrobenchmark, we see a 125s SQLite query (72s system time) reduced
> to 75s (18s system time) by using fincore() instead of mincore(). This
> speedup of course varies by benchmark and benchmarks size; we've seen
> both minimal speedups and 1000x speedups. More on these benchmarks in the
> publication _Reducing Seek Overhead with Application-Directed Prefetching_
> in USENIX ATC 2009 and at http://libprefetch.cs.ucla.edu/.
> 
> In this patch find_get_page() is called for each page, which in turn
> calls rcu_read_lock(), for each page. We have found that amortizing
> these RCU calls, e.g., by introducing a variant of find_get_pages_contig()
> that does not skip missing pages, can speedup the above microbenchmark
> by 260x when querying many pages per system call. But we have not observed
> noticeable improvements to our macrobenchmarks. I'd be happy to also post
> this change or look further into it, but this seems like a reasonable
> first patch, at least.

Interesting.  What RCU-related kernel config parameters were in effect
when you ran your microbenchmark tests?  Having rcu_read_lock() be a
bottleneck is a bit unexpected.  ;-)

							Thanx, Paul

>  include/linux/syscalls.h           |    2 
>  fs/fincore.c                       |  135 +++++++++++++++++++++++++++
>  fs/Makefile                        |    2 
>  arch/x86/ia32/ia32entry.S          |    1 
>  arch/x86/include/asm/unistd_32.h   |    3 
>  arch/x86/include/asm/unistd_64.h   |    2 
>  arch/x86/kernel/syscall_table_32.S |    1 
>  include/asm-generic/unistd.h       |    5 -
>  8 files changed, 148 insertions(+), 3 deletions(-)
> 
> diff --git a/include/linux/syscalls.h b/include/linux/syscalls.h
> index a990ace..1e8f00f 100644
> --- a/include/linux/syscalls.h
> +++ b/include/linux/syscalls.h
> @@ -534,6 +534,8 @@ asmlinkage long sys_munlockall(void);
>  asmlinkage long sys_madvise(unsigned long start, size_t len, int behavior);
>  asmlinkage long sys_mincore(unsigned long start, size_t len,
>  				unsigned char __user * vec);
> +asmlinkage long sys_fincore(unsigned int fd, loff_t start, loff_t len,
> +				unsigned char __user *vec);
> 
>  asmlinkage long sys_pivot_root(const char __user *new_root,
>  				const char __user *put_old);
> diff --git a/fs/fincore.c b/fs/fincore.c
> new file mode 100644
> index 0000000..6b74cc4
> --- /dev/null
> +++ b/fs/fincore.c
> @@ -0,0 +1,135 @@
> +/*
> + *	fs/fincore.c
> + *
> + * Copyright (C) 2009, 2010 Chris Frost, UC Regents
> + * Copyright (C) 2008 Steve VanDeBogart, UC Regents
> + */
> +
> +/*
> + * The fincore() system call.
> + */
> +#include <linux/fs.h>
> +#include <linux/file.h>
> +#include <linux/pagemap.h>
> +#include <linux/syscalls.h>
> +#include <linux/uaccess.h>
> +
> +static unsigned char fincore_page(struct address_space *mapping, pgoff_t pgoff)
> +{
> +	unsigned char present = 0;
> +	struct page *page = find_get_page(mapping, pgoff);
> +	if (page) {
> +		present = PageUptodate(page);
> +		page_cache_release(page);
> +	}
> +
> +	return present;
> +}
> +
> +/*
> + * The fincore(2) system call.
> + *
> + * fincore() returns the memory residency status of the pages backing
> + * a file range specified by fd and [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.  Only locked pages are guaranteed to
> + * remain in memory.
> + *
> + * return values:
> + *  zero    - success
> + *  -EBADF  - fd is an illegal file descriptor
> + *  -EFAULT - vec points to an illegal address
> + *  -EINVAL - start is not a multiple of PAGE_CACHE_SIZE or start + len
> + *		is larger than the size of the file
> + *  -EAGAIN - A kernel resource was temporarily unavailable.
> + */
> +SYSCALL_DEFINE4(fincore, unsigned int, fd, loff_t, start, loff_t, len,
> +		unsigned char __user *, vec)
> +{
> +	long retval;
> +	loff_t pgoff = start >> PAGE_SHIFT;
> +	loff_t pgend;
> +	loff_t npages;
> +	struct file *filp;
> +	int fput_needed;
> +	loff_t file_nbytes;
> +	loff_t file_npages;
> +	unsigned char *tmp = NULL;
> +	unsigned char tmp_small[64];
> +	unsigned tmp_count;
> +	int i;
> +
> +	/* Check the start address: needs to be page-aligned.. */
> +	if (start & ~PAGE_CACHE_MASK)
> +		return -EINVAL;
> +
> +	npages = len >> PAGE_SHIFT;
> +	npages += (len & ~PAGE_MASK) != 0;
> +
> +	pgend = pgoff + npages;
> +
> +	filp = fget_light(fd, &fput_needed);
> +	if (!filp)
> +		return -EBADF;
> +
> +	if (filp->f_dentry->d_inode->i_mode & S_IFBLK)
> +		file_nbytes = filp->f_dentry->d_inode->i_bdev->bd_inode->i_size << 9;
> +	else
> +		file_nbytes = filp->f_dentry->d_inode->i_size;
> +
> +	file_npages = file_nbytes >> PAGE_SHIFT;
> +	file_npages += (file_nbytes & ~PAGE_MASK) != 0;
> +
> +	if (pgoff >= file_npages || pgend > file_npages) {
> +		retval = -EINVAL;
> +		goto done;
> +	}
> +
> +	if (!access_ok(VERIFY_WRITE, vec, npages)) {
> +		retval = -EFAULT;
> +		goto done;
> +	}
> +
> +	/*
> +	 * Allocate buffer vector page.
> +	 * Optimize allocation for small values of npages because the
> +	 * __get_free_page() call doubles fincore(2) runtime when npages == 1.
> +	 */
> +	if (npages <= sizeof(tmp_small)) {
> +		tmp = tmp_small;
> +		tmp_count = sizeof(tmp_small);
> +	} else {
> +		tmp = (void *) __get_free_page(GFP_USER);
> +		if (!tmp) {
> +			retval = -EAGAIN;
> +			goto done;
> +		}
> +		tmp_count = PAGE_SIZE;
> +	}
> +
> +	while (pgoff < pgend) {
> +		/*
> +		 * Do at most tmp_count entries per iteration, due to
> +		 * the temporary buffer size.
> +		 */
> +		for (i = 0; pgoff < pgend && i < tmp_count; pgoff++, i++)
> +			tmp[i] = fincore_page(filp->f_mapping, pgoff);
> +
> +		if (copy_to_user(vec, tmp, i)) {
> +			retval = -EFAULT;
> +			break;
> +		}
> +		vec += i;
> +	}
> +	retval = 0;
> +done:
> +	if (tmp && tmp != tmp_small)
> +		free_page((unsigned long) tmp);
> +	fput_light(filp, fput_needed);
> +	return retval;
> +}
> diff --git a/fs/Makefile b/fs/Makefile
> index af6d047..a3ccd6b 100644
> --- a/fs/Makefile
> +++ b/fs/Makefile
> @@ -11,7 +11,7 @@ obj-y :=	open.o read_write.o file_table.o super.o \
>  		attr.o bad_inode.o file.o filesystems.o namespace.o \
>  		seq_file.o xattr.o libfs.o fs-writeback.o \
>  		pnode.o drop_caches.o splice.o sync.o utimes.o \
> -		stack.o fs_struct.o
> +		stack.o fs_struct.o fincore.o
> 
>  ifeq ($(CONFIG_BLOCK),y)
>  obj-y +=	buffer.o bio.o block_dev.o direct-io.o mpage.o ioprio.o
> diff --git a/include/asm-generic/unistd.h b/include/asm-generic/unistd.h
> index d76b66a..ce76dc8 100644
> --- a/include/asm-generic/unistd.h
> +++ b/include/asm-generic/unistd.h
> @@ -623,8 +623,11 @@ __SYSCALL(__NR_rt_tgsigqueueinfo, sys_rt_tgsigqueueinfo)
>  #define __NR_perf_event_open 241
>  __SYSCALL(__NR_perf_event_open, sys_perf_event_open)
> 
> +#define __NR_fincore 242
> +__SYSCALL(__NR_fincore, sys_fincore)
> +
>  #undef __NR_syscalls
> -#define __NR_syscalls 242
> +#define __NR_syscalls 243
> 
>  /*
>   * All syscalls below here should go away really,
> diff --git a/arch/x86/ia32/ia32entry.S b/arch/x86/ia32/ia32entry.S
> index 581b056..cbf96e6 100644
> --- a/arch/x86/ia32/ia32entry.S
> +++ b/arch/x86/ia32/ia32entry.S
> @@ -841,4 +841,5 @@ ia32_sys_call_table:
>  	.quad compat_sys_pwritev
>  	.quad compat_sys_rt_tgsigqueueinfo	/* 335 */
>  	.quad sys_perf_event_open
> +	.quad sys_fincore
>  ia32_syscall_end:
> diff --git a/arch/x86/include/asm/unistd_32.h b/arch/x86/include/asm/unistd_32.h
> index 6fb3c20..088b235 100644
> --- a/arch/x86/include/asm/unistd_32.h
> +++ b/arch/x86/include/asm/unistd_32.h
> @@ -342,10 +342,11 @@
>  #define __NR_pwritev		334
>  #define __NR_rt_tgsigqueueinfo	335
>  #define __NR_perf_event_open	336
> +#define __NR_fincore		337
> 
>  #ifdef __KERNEL__
> 
> -#define NR_syscalls 337
> +#define NR_syscalls 338
> 
>  #define __ARCH_WANT_IPC_PARSE_VERSION
>  #define __ARCH_WANT_OLD_READDIR
> diff --git a/arch/x86/include/asm/unistd_64.h b/arch/x86/include/asm/unistd_64.h
> index 8d3ad0a..ebc04b5 100644
> --- a/arch/x86/include/asm/unistd_64.h
> +++ b/arch/x86/include/asm/unistd_64.h
> @@ -661,6 +661,8 @@ __SYSCALL(__NR_pwritev, sys_pwritev)
>  __SYSCALL(__NR_rt_tgsigqueueinfo, sys_rt_tgsigqueueinfo)
>  #define __NR_perf_event_open			298
>  __SYSCALL(__NR_perf_event_open, sys_perf_event_open)
> +#define __NR_fincore				299
> +__SYSCALL(__NR_fincore, sys_fincore)
> 
>  #ifndef __NO_STUBS
>  #define __ARCH_WANT_OLD_READDIR
> diff --git a/arch/x86/kernel/syscall_table_32.S b/arch/x86/kernel/syscall_table_32.S
> index 0157cd2..1fdc8bc 100644
> --- a/arch/x86/kernel/syscall_table_32.S
> +++ b/arch/x86/kernel/syscall_table_32.S
> @@ -336,3 +336,4 @@ ENTRY(sys_call_table)
>  	.long sys_pwritev
>  	.long sys_rt_tgsigqueueinfo	/* 335 */
>  	.long sys_perf_event_open
> +	.long sys_fincore
> -- 
> 1.5.4.3
> 
> -- 
> Chris Frost
> http://www.frostnet.net/chris/
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@...r.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists