Re: [00/17] Large Blocksize Support V3

[William Lee Irwin III <wli@holomorphy.com>]

David Chinner <dgc@sgi.com> writes:
>>> Right - so how do we efficiently  manipulate data inside a large
>>> block that spans multiple discontigous pages if we don't vmap
>>> it?

On Mon, May 07, 2007 at 12:43:19AM -0600, Eric W. Biederman wrote:
>> You don't manipulate data except for copy_from_user, copy_to_user.
>> That is easy comparatively to deal with, and certainly doesn't
>> need vmap.
>> Meta-data may be trickier, but a lot of that depends on your
>> individual filesystem and how it organizes it's meta-data.

On Sun, May 06, 2007 at 11:49:25PM -0700, William Lee Irwin III wrote:
> I wonder what happened to my pagearray patches.

I never really got the thing working, but I had an idea for a sort of
library to do this. This is/was probably against something like 2.6.5
but I honestly have no idea. Maybe this makes it something of an API
proposal.


-- wli


Index: linux-2.6/include/linux/pagearray.h
===================================================================
--- linux-2.6.orig/include/linux/pagearray.h	2004-04-06 10:56:48.000000000 -0700
+++ linux-2.6/include/linux/pagearray.h	2005-04-22 06:06:02.677494584 -0700
@@ -0,0 +1,24 @@
+#ifndef _LINUX_PAGEARRAY_H
+#define _LINUX_PAGEARRAY_H
+
+struct scatterlist;
+struct vm_area_struct;
+struct page;
+
+struct pagearray {
+	struct page **pages;
+	int nr_pages;
+	size_t length;
+};
+
+int alloc_page_array(struct pagearray *, const int, const size_t);
+void free_page_array(struct pagearray *);
+void zero_page_array(struct pagearray *);
+struct page *nopage_page_array(const struct vm_area_struct *, unsigned long, unsigned long, int *, struct pagearray *);
+int mmap_page_array(const struct vm_area_struct *, struct pagearray *, const size_t, const size_t);
+int copy_page_array_to_user(struct pagearray *, void __user *, const size_t, const size_t);
+int copy_page_array_from_user(struct pagearray *, void __user *, const size_t, const size_t);
+struct scatterlist *pagearray_to_scatterlist(struct pagearray *, size_t, size_t, int *);
+void *vmap_pagearray(struct pagearray *);
+
+#endif /* _LINUX_PAGEARRAY_H */
Index: linux-2.6/mm/Makefile
===================================================================
--- linux-2.6.orig/mm/Makefile	2005-04-22 06:01:29.786980248 -0700
+++ linux-2.6/mm/Makefile	2005-04-22 06:06:02.677494584 -0700
@@ -10,7 +10,7 @@
 obj-y			:= bootmem.o filemap.o mempool.o oom_kill.o fadvise.o \
 			   page_alloc.o page-writeback.o pdflush.o \
 			   readahead.o slab.o swap.o truncate.o vmscan.o \
-			   prio_tree.o $(mmu-y)
+			   prio_tree.o pagearray.o $(mmu-y)
 
 obj-$(CONFIG_SWAP)	+= page_io.o swap_state.o swapfile.o thrash.o
 obj-$(CONFIG_HUGETLBFS)	+= hugetlb.o
Index: linux-2.6/mm/pagearray.c
===================================================================
--- linux-2.6.orig/mm/pagearray.c	2004-04-06 10:56:48.000000000 -0700
+++ linux-2.6/mm/pagearray.c	2005-04-22 06:20:26.154226168 -0700
@@ -0,0 +1,293 @@
+#include <linux/mm.h>
+#include <linux/vmalloc.h>
+#include <linux/module.h>
+#include <linux/highmem.h>
+#include <linux/pagearray.h>
+#include <asm/uaccess.h>
+#include <asm/scatterlist.h>
+
+/**
+ * alloc_page_array - allocate an array of pages
+ * @pages: the array of pages to be allocated
+ * @gfp_mask: the GFP flags to be passed to the allocator
+ * @length: the amount of data the array needs to hold
+ *
+ * Allocate an array of page pointers long enough so that when full of
+ * pages, the amount of data in length may be stored, then allocate the
+ * pages for each position in the array.
+ */
+int alloc_page_array(struct pagearray *pages, const int gfp_mask, const size_t length)
+{
+	int k;
+	pages->length = PAGE_ALIGN(length);
+	pages->nr_pages = PAGE_ALIGN(length) >> PAGE_SHIFT;
+	pages->pages = kmalloc(pages->nr_pages*sizeof(struct page *), gfp_mask);
+	if (!pages->pages)
+		return -ENOMEM;
+	memset(pages->pages, 0, pages->nr_pages*sizeof(struct page *));
+	for (k = 0; k < pages->nr_pages; ++k) {
+		pages->pages[k] = alloc_page(gfp_mask);
+		if (!pages->pages[k])
+			goto enomem;
+	}
+	return 0;
+enomem:
+	for (--k; k >= 0; --k)
+		__free_page(pages->pages[k]);
+	kfree(pages->pages);
+	memset(pages, 0, sizeof(struct pagearray));
+	return -ENOMEM;
+}
+EXPORT_SYMBOL(alloc_page_array);
+
+/**
+ * free_page_array - free an array of pages
+ * @pages: the array of pages to be freed
+ *
+ * Free an array of pages, including the pages pointed to by the array.
+ */
+void free_page_array(struct pagearray *pages)
+{
+	int k;
+	for (k = 0; k < pages->nr_pages; ++k)
+		__free_page(pages->pages[k]);
+	kfree(pages->pages);
+	memset(pages, 0, sizeof(struct pagearray));
+}
+EXPORT_SYMBOL(free_page_array);
+
+/**
+ * zero_page_array - zero an array of pages
+ * @pages: the array of pages
+ *
+ * Zero out a set of pages pointed to by an array of page pointers.
+ */
+void zero_page_array(struct pagearray *pages)
+{
+	int k;
+	for (k = 0; k < pages->nr_pages; ++k)
+		clear_highpage(pages->pages[k]);
+}
+EXPORT_SYMBOL(zero_page_array);
+
+/**
+ * nopage_page_array - retrieve the page to satisfy a fault with
+ * @vma: the user virtual memory area the fault occurred on
+ * @pgoff: an offset into the underlying array to add to ->vm_pgoff
+ * @vaddr: the user virtual address the fault occurred on
+ * @type: the type of fault that occurred, to be returned
+ * @pages: the array of page pointers
+ *
+ * This is a trivial helper for ->nopage() methods. Simply return the
+ * result of this function after retrieving the page array and its
+ * descriptive parameters from vma->vm_private_data, for instance:
+ * return nopage_page_array(vma, pgoff, vaddr, type, pages);
+ * as the last thing in the ->nopage() method after fetching the
+ * parameters from vma->vm_private_data.
+ */
+struct page *nopage_page_array(const struct vm_area_struct *vma, unsigned long pgoff, unsigned long vaddr, int *type, struct pagearray *pages)
+{
+	if (vaddr >= vma->vm_end)
+		goto sigbus;
+	pgoff += vma->vm_pgoff + ((vaddr - vma->vm_start) >> PAGE_SHIFT);
+	if (pgoff > PAGE_ALIGN(pages->length)/PAGE_SIZE)
+		goto sigbus;
+	if (pgoff > pages->nr_pages)
+		goto sigbus;
+	get_page(pages->pages[pgoff]);
+	if (type)
+		*type = VM_FAULT_MINOR;
+	return pages->pages[pgoff];
+sigbus:
+	if (type)
+		*type = VM_FAULT_SIGBUS;
+	return NOPAGE_SIGBUS;
+}
+EXPORT_SYMBOL(nopage_page_array);
+
+/**
+ * mmap_page_array - mmap an array of pages
+ * @vma: the vma where the mmapping is done
+ * @pages: the array of page pointers
+ * @offset: the offset into the vma in bytes where mmapping should be done
+ * @length: the amount of data that should be mmap'd, in bytes
+ *
+ * vma->vm_pgoff specifies how far out into the page array mmapping
+ * should be done. The page array is treated as a list of the pieces
+ * of an object and vma->vm_pgoff the offset into that object.
+ * vma->vm_page_prot in turn specifies the protections to map with.
+ * offset says where in userspace relative to vma->vm_start to put
+ * the mappings of the pieces of the page array. length specifies how
+ * much data should be mapped into userspace.
+ */
+#ifdef CONFIG_MMU
+int mmap_page_array(const struct vm_area_struct *vma, struct pagearray *pages, const size_t offset, const size_t length)
+{
+	int k, ret = 0;
+	unsigned long end, off, vaddr = vma->vm_start + offset;
+	off = (vma->vm_pgoff << PAGE_SHIFT) + offset;
+	end = vaddr + length;
+	if (vaddr >= end)
+		return -EINVAL;
+	else if (offset != PAGE_ALIGN(offset))
+		return -EINVAL;
+	else if (offset + length > pages->length)
+		return -EINVAL;
+	k = off >> PAGE_SHIFT;
+	while (vaddr < end && !ret) {
+		pgd_t *pgd;
+		pud_t *pud;
+
+		spin_lock(&vma->vm_mm->page_table_lock);
+		pgd = pgd_offset(vma->vm_mm, vaddr);
+		pud = pud_alloc(vma->vm_mm, pgd, vaddr);
+		if (!pud) {
+			ret = -ENOMEM;
+			break;
+		} else {
+			pmd_t *pmd = pmd_alloc(vma->vm_mm, pud, vaddr);
+			if (!pmd) {
+				ret = -ENOMEM;
+				break;
+			} else {
+				pte_t val, *pte;
+
+				pte = pte_alloc_map(vma->vm_mm, pmd, vaddr);
+				if (!pte) {
+					ret = -ENOMEM;
+					break;
+				} else {
+					val = mk_pte(pages->pages[k], vma->vm_page_prot);
+					set_pte(pte, val);
+					pte_unmap(pte);
+					update_mmu_cache(vma, vaddr, val);
+				}
+			}
+		}
+		spin_unlock(&vma->vm_mm->page_table_lock);
+		vaddr += PAGE_SIZE;
+		off += PAGE_SIZE;
+		++k;
+	}
+	return ret;
+}
+#else
+int mmap_page_array(const struct vm_area_struct *vma, struct pagearray *pages, const size_t offset, const size_t length)
+{
+	return -ENOSYS;
+}
+#endif
+EXPORT_SYMBOL(mmap_page_array);
+
+static int copy_page_array(struct pagearray *pages, char __user *buf, const size_t offset, const size_t length, const int rw)
+{
+	size_t pos = 0, off = offset, remaining = length;
+	int k;
+
+	if (length > pages->length)
+		return -EFAULT;
+	else if (length > MM_VM_SIZE(current->mm))
+		return -EFAULT;
+	else if ((unsigned long)buf > MM_VM_SIZE(current->mm) - length)
+		return -EFAULT;
+
+	for (k = off >> PAGE_SHIFT; k < pages->nr_pages && remaining > 0; ++k) {
+		unsigned long left, tail, suboff = off & PAGE_MASK;
+		char *kbuf = kmap_atomic(pages->pages[k], KM_USER0);
+		tail = min(PAGE_SIZE - suboff, (unsigned long)remaining);
+		if (rw)
+			left = __copy_to_user(&buf[pos], &kbuf[suboff], tail);
+		else
+			left = __copy_from_user(&kbuf[suboff], &buf[pos], tail);
+		kunmap_atomic(kbuf, KM_USER0);
+		if (left) {
+			kbuf = kmap(pages->pages[k]);
+			if (rw)
+				left = __copy_to_user(&buf[pos], &kbuf[suboff], tail);
+			else
+				left = __copy_from_user(&kbuf[suboff], &buf[pos], tail);
+			kunmap(pages->pages[k]);
+		}
+		BUG_ON(tail - left > remaining);
+		remaining -= tail - left;
+		pos += tail - left;
+		off = (off + PAGE_SIZE) & PAGE_MASK;
+		if (left)
+			break;
+	}
+	return remaining;
+}
+
+/**
+ * copy_page_array_to_user - copy data from a page array to userspace
+ * @pages: the array of page pointers holding the data
+ * @buf: the user virtual address to start depositing the data at
+ * @offset: the offset into the page array to start copying data from
+ * @length: how much data to copy
+ *
+ * Copy data from a page array, starting offset bytes into the array
+ * when it's treated as a list of the pieces of an object in order,
+ * to userspace.
+ */
+int copy_page_array_to_user(struct pagearray *pages, void __user *buf, const size_t offset, const size_t length)
+{
+	return copy_page_array(pages, buf, offset, length, 1);
+}
+EXPORT_SYMBOL(copy_page_array_to_user);
+
+/**
+ * copy_page_array_from_user - copy data from userspace to a page array
+ * @pages: the array of page pointers holding the data
+ * @buf: the user virtual address to start reading the data from
+ * @offset: the offset into the page array to start copying data to
+ * @length: how much data to copy
+ *
+ * Copy data to a page array, starting offset bytes into the array
+ * when it's treated as a list of the pieces of an object in order,
+ * from userspace.
+ */
+int copy_page_array_from_user(struct pagearray *pages, void __user *buf, const size_t offset, const size_t length)
+{
+	return copy_page_array(pages, buf, offset, length, 0);
+}
+EXPORT_SYMBOL(copy_page_array_from_user);
+
+/**
+ * pagearray_to_scatterlist - generate a scatterlist for a slice of a pagearray
+ * @pages: the pagearray to make a scatterlist for
+ * @offset: the offset into the pagearray of the start of the slice
+ * @length: the length of the slice of the pagearray
+ * @sglist_len: the size of the generated scatterlist
+ *
+ * Set up a scatterlist covering a slice of a pagearray, starting at offset
+ * bytes into the pagearray, with length length.
+ */
+struct scatterlist *pagearray_to_scatterlist(struct pagearray *pages, size_t offset, size_t length, int *sglist_len)
+{
+	struct scatterlist *sg;
+	int i, nr_pages =
+		(PAGE_ALIGN(offset + length) - (offset & PAGE_MASK))/PAGE_SIZE;
+	sg = kmalloc(nr_pages * sizeof(struct scatterlist), GFP_KERNEL);
+	if (!sg)
+		return NULL;
+	memset(sg, 0, nr_pages * sizeof(struct scatterlist));
+	sg[0].page = pages->pages[offset >> PAGE_SHIFT];
+	sg[0].offset = offset & ~PAGE_MASK;
+	sg[0].length = PAGE_SIZE - sg[0].offset;
+	offset = (offset + PAGE_SIZE) & PAGE_MASK;
+	for (i = 1; i < nr_pages - 1; ++i) {
+		sg[i].page = pages->pages[i];
+		sg[i].length = PAGE_SIZE;
+	}
+	sg[i].page = pages->pages[i];
+	sg[i].length = (offset + length) & ~PAGE_MASK;
+	*sglist_len = nr_pages;
+	return sg;
+}
+EXPORT_SYMBOL(pagearray_to_scatterlist);
+
+void *vmap_pagearray(struct pagearray *pages)
+{
+	return vmap(pages->pages, pages->nr_pages, VM_MAP, PAGE_KERNEL);
+}
+EXPORT_SYMBOL(vmap_pagearray);