[PATCH 1/5] lib/scatterlist: Fix offset type in sg_alloc_table_from_pages

[PATCH 1/5] lib/scatterlist: Fix offset type in sg_alloc_table_from_pages

[Tvrtko Ursulin]

From: Tvrtko Ursulin <tvrtko.ursulin@intel.com>

Scatterlist entries have an unsigned int for the offset so
correct the sg_alloc_table_from_pages function accordingly.

Since these are offsets withing a page, unsigned int is
wide enough.

Also converts callers which were using unsigned long locally
with the lower_32_bits annotation to make it explicitly
clear what is happening.

v2: Use offset_in_page. (Chris Wilson)

Signed-off-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
Cc: Masahiro Yamada <yamada.masahiro@socionext.com>
Cc: Pawel Osciak <pawel@osciak.com>
Cc: Marek Szyprowski <m.szyprowski@samsung.com>
Cc: Kyungmin Park <kyungmin.park@samsung.com>
Cc: Tomasz Stanislawski <t.stanislaws@samsung.com>
Cc: Matt Porter <mporter@kernel.crashing.org>
Cc: Alexandre Bounine <alexandre.bounine@idt.com>
Cc: linux-media@vger.kernel.org
Cc: linux-kernel@vger.kernel.org
Acked-by: Marek Szyprowski <m.szyprowski@samsung.com> (v1)
Reviewed-by: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Mauro Carvalho Chehab <mchehab@s-opensource.com>
---
 drivers/media/v4l2-core/videobuf2-dma-contig.c | 4 ++--
 drivers/rapidio/devices/rio_mport_cdev.c       | 4 ++--
 include/linux/scatterlist.h                    | 2 +-
 lib/scatterlist.c                              | 2 +-
 4 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/drivers/media/v4l2-core/videobuf2-dma-contig.c b/drivers/media/v4l2-core/videobuf2-dma-contig.c
index 4f246d166111..2405077fdc71 100644
--- a/drivers/media/v4l2-core/videobuf2-dma-contig.c
+++ b/drivers/media/v4l2-core/videobuf2-dma-contig.c
@@ -479,7 +479,7 @@ static void *vb2_dc_get_userptr(struct device *dev, unsigned long vaddr,
 {
 	struct vb2_dc_buf *buf;
 	struct frame_vector *vec;
-	unsigned long offset;
+	unsigned int offset;
 	int n_pages, i;
 	int ret = 0;
 	struct sg_table *sgt;
@@ -507,7 +507,7 @@ static void *vb2_dc_get_userptr(struct device *dev, unsigned long vaddr,
 	buf->dev = dev;
 	buf->dma_dir = dma_dir;
 
-	offset = vaddr & ~PAGE_MASK;
+	offset = lower_32_bits(offset_in_page(vaddr));
 	vec = vb2_create_framevec(vaddr, size, dma_dir == DMA_FROM_DEVICE);
 	if (IS_ERR(vec)) {
 		ret = PTR_ERR(vec);
diff --git a/drivers/rapidio/devices/rio_mport_cdev.c b/drivers/rapidio/devices/rio_mport_cdev.c
index 5beb0c361076..5c1b6388122a 100644
--- a/drivers/rapidio/devices/rio_mport_cdev.c
+++ b/drivers/rapidio/devices/rio_mport_cdev.c
@@ -876,10 +876,10 @@ rio_dma_transfer(struct file *filp, u32 transfer_mode,
 	 * offset within the internal buffer specified by handle parameter.
 	 */
 	if (xfer->loc_addr) {
-		unsigned long offset;
+		unsigned int offset;
 		long pinned;
 
-		offset = (unsigned long)(uintptr_t)xfer->loc_addr & ~PAGE_MASK;
+		offset = lower_32_bits(offset_in_page(xfer->loc_addr));
 		nr_pages = PAGE_ALIGN(xfer->length + offset) >> PAGE_SHIFT;
 
 		page_list = kmalloc_array(nr_pages,
diff --git a/include/linux/scatterlist.h b/include/linux/scatterlist.h
index 4b3286ac60c8..205aefb4ed93 100644
--- a/include/linux/scatterlist.h
+++ b/include/linux/scatterlist.h
@@ -263,7 +263,7 @@ int __sg_alloc_table(struct sg_table *, unsigned int, unsigned int,
 int sg_alloc_table(struct sg_table *, unsigned int, gfp_t);
 int sg_alloc_table_from_pages(struct sg_table *sgt,
 	struct page **pages, unsigned int n_pages,
-	unsigned long offset, unsigned long size,
+	unsigned int offset, unsigned long size,
 	gfp_t gfp_mask);
 
 size_t sg_copy_buffer(struct scatterlist *sgl, unsigned int nents, void *buf,
diff --git a/lib/scatterlist.c b/lib/scatterlist.c
index be7b4dd6b68d..dee0c5004e2f 100644
--- a/lib/scatterlist.c
+++ b/lib/scatterlist.c
@@ -391,7 +391,7 @@ EXPORT_SYMBOL(sg_alloc_table);
  */
 int sg_alloc_table_from_pages(struct sg_table *sgt,
 	struct page **pages, unsigned int n_pages,
-	unsigned long offset, unsigned long size,
+	unsigned int offset, unsigned long size,
 	gfp_t gfp_mask)
 {
 	unsigned int chunks;
-- 
2.9.4

[PATCH 2/5] lib/scatterlist: Avoid potential scatterlist entry overflow

[Tvrtko Ursulin]

From: Tvrtko Ursulin <tvrtko.ursulin@intel.com>

Since the scatterlist length field is an unsigned int, make
sure that sg_alloc_table_from_pages does not overflow it while
coallescing pages to a single entry.

v2: Drop reference to future use. Use UINT_MAX.
v3: max_segment must be page aligned.
v4: Do not rely on compiler to optimise out the rounddown.
    (Joonas Lahtinen)
v5: Simplified loops and use post-increments rather than
    pre-increments. Use PAGE_MASK and fix comment typo.
    (Andy Shevchenko)

Signed-off-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
Cc: Masahiro Yamada <yamada.masahiro@socionext.com>
Cc: linux-kernel@vger.kernel.org
Reviewed-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Cc: Andy Shevchenko <andy.shevchenko@gmail.com>
---
 include/linux/scatterlist.h |  6 ++++++
 lib/scatterlist.c           | 31 ++++++++++++++++++++-----------
 2 files changed, 26 insertions(+), 11 deletions(-)

diff --git a/include/linux/scatterlist.h b/include/linux/scatterlist.h
index 205aefb4ed93..6dd2ddbc6230 100644
--- a/include/linux/scatterlist.h
+++ b/include/linux/scatterlist.h
@@ -21,6 +21,12 @@ struct scatterlist {
 };
 
 /*
+ * Since the above length field is an unsigned int, below we define the maximum
+ * length in bytes that can be stored in one scatterlist entry.
+ */
+#define SCATTERLIST_MAX_SEGMENT (UINT_MAX & PAGE_MASK)
+
+/*
  * These macros should be used after a dma_map_sg call has been done
  * to get bus addresses of each of the SG entries and their lengths.
  * You should only work with the number of sg entries dma_map_sg
diff --git a/lib/scatterlist.c b/lib/scatterlist.c
index dee0c5004e2f..7b2e74da2c44 100644
--- a/lib/scatterlist.c
+++ b/lib/scatterlist.c
@@ -394,17 +394,22 @@ int sg_alloc_table_from_pages(struct sg_table *sgt,
 	unsigned int offset, unsigned long size,
 	gfp_t gfp_mask)
 {
-	unsigned int chunks;
-	unsigned int i;
-	unsigned int cur_page;
+	const unsigned int max_segment = SCATTERLIST_MAX_SEGMENT;
+	unsigned int chunks, cur_page, seg_len, i;
 	int ret;
 	struct scatterlist *s;
 
 	/* compute number of contiguous chunks */
 	chunks = 1;
-	for (i = 1; i < n_pages; ++i)
-		if (page_to_pfn(pages[i]) != page_to_pfn(pages[i - 1]) + 1)
-			++chunks;
+	seg_len = 0;
+	for (i = 1; i < n_pages; i++) {
+		seg_len += PAGE_SIZE;
+		if (seg_len >= max_segment ||
+		    page_to_pfn(pages[i]) != page_to_pfn(pages[i - 1]) + 1) {
+			chunks++;
+			seg_len = 0;
+		}
+	}
 
 	ret = sg_alloc_table(sgt, chunks, gfp_mask);
 	if (unlikely(ret))
@@ -413,17 +418,21 @@ int sg_alloc_table_from_pages(struct sg_table *sgt,
 	/* merging chunks and putting them into the scatterlist */
 	cur_page = 0;
 	for_each_sg(sgt->sgl, s, sgt->orig_nents, i) {
-		unsigned long chunk_size;
-		unsigned int j;
+		unsigned int j, chunk_size;
 
 		/* look for the end of the current chunk */
-		for (j = cur_page + 1; j < n_pages; ++j)
-			if (page_to_pfn(pages[j]) !=
+		seg_len = 0;
+		for (j = cur_page + 1; j < n_pages; j++) {
+			seg_len += PAGE_SIZE;
+			if (seg_len >= max_segment ||
+			    page_to_pfn(pages[j]) !=
 			    page_to_pfn(pages[j - 1]) + 1)
 				break;
+		}
 
 		chunk_size = ((j - cur_page) << PAGE_SHIFT) - offset;
-		sg_set_page(s, pages[cur_page], min(size, chunk_size), offset);
+		sg_set_page(s, pages[cur_page],
+			    min_t(unsigned long, size, chunk_size), offset);
 		size -= chunk_size;
 		offset = 0;
 		cur_page = j;
-- 
2.9.4

[PATCH v6 2/5] lib/scatterlist: Avoid potential scatterlist entry overflow

[Tvrtko Ursulin]

From: Tvrtko Ursulin <tvrtko.ursulin@intel.com>

Since the scatterlist length field is an unsigned int, make
sure that sg_alloc_table_from_pages does not overflow it while
coalescing pages to a single entry.

v2: Drop reference to future use. Use UINT_MAX.
v3: max_segment must be page aligned.
v4: Do not rely on compiler to optimise out the rounddown.
    (Joonas Lahtinen)
v5: Simplified loops and use post-increments rather than
    pre-increments. Use PAGE_MASK and fix comment typo.
    (Andy Shevchenko)
v6: Commit spelling fix.

Signed-off-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
Cc: Masahiro Yamada <yamada.masahiro@socionext.com>
Cc: linux-kernel@vger.kernel.org
Reviewed-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Cc: Andy Shevchenko <andy.shevchenko@gmail.com>
---
 include/linux/scatterlist.h |  6 ++++++
 lib/scatterlist.c           | 31 ++++++++++++++++++++-----------
 2 files changed, 26 insertions(+), 11 deletions(-)

diff --git a/include/linux/scatterlist.h b/include/linux/scatterlist.h
index 205aefb4ed93..6dd2ddbc6230 100644
--- a/include/linux/scatterlist.h
+++ b/include/linux/scatterlist.h
@@ -21,6 +21,12 @@ struct scatterlist {
 };
 
 /*
+ * Since the above length field is an unsigned int, below we define the maximum
+ * length in bytes that can be stored in one scatterlist entry.
+ */
+#define SCATTERLIST_MAX_SEGMENT (UINT_MAX & PAGE_MASK)
+
+/*
  * These macros should be used after a dma_map_sg call has been done
  * to get bus addresses of each of the SG entries and their lengths.
  * You should only work with the number of sg entries dma_map_sg
diff --git a/lib/scatterlist.c b/lib/scatterlist.c
index dee0c5004e2f..7b2e74da2c44 100644
--- a/lib/scatterlist.c
+++ b/lib/scatterlist.c
@@ -394,17 +394,22 @@ int sg_alloc_table_from_pages(struct sg_table *sgt,
 	unsigned int offset, unsigned long size,
 	gfp_t gfp_mask)
 {
-	unsigned int chunks;
-	unsigned int i;
-	unsigned int cur_page;
+	const unsigned int max_segment = SCATTERLIST_MAX_SEGMENT;
+	unsigned int chunks, cur_page, seg_len, i;
 	int ret;
 	struct scatterlist *s;
 
 	/* compute number of contiguous chunks */
 	chunks = 1;
-	for (i = 1; i < n_pages; ++i)
-		if (page_to_pfn(pages[i]) != page_to_pfn(pages[i - 1]) + 1)
-			++chunks;
+	seg_len = 0;
+	for (i = 1; i < n_pages; i++) {
+		seg_len += PAGE_SIZE;
+		if (seg_len >= max_segment ||
+		    page_to_pfn(pages[i]) != page_to_pfn(pages[i - 1]) + 1) {
+			chunks++;
+			seg_len = 0;
+		}
+	}
 
 	ret = sg_alloc_table(sgt, chunks, gfp_mask);
 	if (unlikely(ret))
@@ -413,17 +418,21 @@ int sg_alloc_table_from_pages(struct sg_table *sgt,
 	/* merging chunks and putting them into the scatterlist */
 	cur_page = 0;
 	for_each_sg(sgt->sgl, s, sgt->orig_nents, i) {
-		unsigned long chunk_size;
-		unsigned int j;
+		unsigned int j, chunk_size;
 
 		/* look for the end of the current chunk */
-		for (j = cur_page + 1; j < n_pages; ++j)
-			if (page_to_pfn(pages[j]) !=
+		seg_len = 0;
+		for (j = cur_page + 1; j < n_pages; j++) {
+			seg_len += PAGE_SIZE;
+			if (seg_len >= max_segment ||
+			    page_to_pfn(pages[j]) !=
 			    page_to_pfn(pages[j - 1]) + 1)
 				break;
+		}
 
 		chunk_size = ((j - cur_page) << PAGE_SHIFT) - offset;
-		sg_set_page(s, pages[cur_page], min(size, chunk_size), offset);
+		sg_set_page(s, pages[cur_page],
+			    min_t(unsigned long, size, chunk_size), offset);
 		size -= chunk_size;
 		offset = 0;
 		cur_page = j;
-- 
2.9.4

[PATCH 3/5] lib/scatterlist: Introduce and export __sg_alloc_table_from_pages

[Tvrtko Ursulin]

From: Tvrtko Ursulin <tvrtko.ursulin@intel.com>

Drivers like i915 benefit from being able to control the maxium
size of the sg coallesced segment while building the scatter-
gather list.

Introduce and export the __sg_alloc_table_from_pages function
which will allow it that control.

v2: Reorder parameters. (Chris Wilson)
v3: Fix incomplete reordering in v2.
v4: max_segment needs to be page aligned.
v5: Rebase.
v6: Rebase.

Signed-off-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
Cc: Masahiro Yamada <yamada.masahiro@socionext.com>
Cc: linux-kernel@vger.kernel.org
Cc: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
---
 include/linux/scatterlist.h | 11 +++++----
 lib/scatterlist.c           | 58 +++++++++++++++++++++++++++++++++++----------
 2 files changed, 52 insertions(+), 17 deletions(-)

diff --git a/include/linux/scatterlist.h b/include/linux/scatterlist.h
index 6dd2ddbc6230..874b50c232de 100644
--- a/include/linux/scatterlist.h
+++ b/include/linux/scatterlist.h
@@ -267,10 +267,13 @@ void sg_free_table(struct sg_table *);
 int __sg_alloc_table(struct sg_table *, unsigned int, unsigned int,
 		     struct scatterlist *, gfp_t, sg_alloc_fn *);
 int sg_alloc_table(struct sg_table *, unsigned int, gfp_t);
-int sg_alloc_table_from_pages(struct sg_table *sgt,
-	struct page **pages, unsigned int n_pages,
-	unsigned int offset, unsigned long size,
-	gfp_t gfp_mask);
+int __sg_alloc_table_from_pages(struct sg_table *sgt, struct page **pages,
+				unsigned int n_pages, unsigned int offset,
+				unsigned long size, unsigned int max_segment,
+				gfp_t gfp_mask);
+int sg_alloc_table_from_pages(struct sg_table *sgt, struct page **pages,
+			      unsigned int n_pages, unsigned int offset,
+			      unsigned long size, gfp_t gfp_mask);
 
 size_t sg_copy_buffer(struct scatterlist *sgl, unsigned int nents, void *buf,
 		      size_t buflen, off_t skip, bool to_buffer);
diff --git a/lib/scatterlist.c b/lib/scatterlist.c
index 7b2e74da2c44..1a5900f9a057 100644
--- a/lib/scatterlist.c
+++ b/lib/scatterlist.c
@@ -370,14 +370,15 @@ int sg_alloc_table(struct sg_table *table, unsigned int nents, gfp_t gfp_mask)
 EXPORT_SYMBOL(sg_alloc_table);
 
 /**
- * sg_alloc_table_from_pages - Allocate and initialize an sg table from
- *			       an array of pages
- * @sgt:	The sg table header to use
- * @pages:	Pointer to an array of page pointers
- * @n_pages:	Number of pages in the pages array
- * @offset:     Offset from start of the first page to the start of a buffer
- * @size:       Number of valid bytes in the buffer (after offset)
- * @gfp_mask:	GFP allocation mask
+ * __sg_alloc_table_from_pages - Allocate and initialize an sg table from
+ *			         an array of pages
+ * @sgt:	 The sg table header to use
+ * @pages:	 Pointer to an array of page pointers
+ * @n_pages:	 Number of pages in the pages array
+ * @offset:      Offset from start of the first page to the start of a buffer
+ * @size:        Number of valid bytes in the buffer (after offset)
+ * @max_segment: Maximum size of a scatterlist node in bytes (page aligned)
+ * @gfp_mask:	 GFP allocation mask
  *
  *  Description:
  *    Allocate and initialize an sg table from a list of pages. Contiguous
@@ -389,16 +390,18 @@ EXPORT_SYMBOL(sg_alloc_table);
  * Returns:
  *   0 on success, negative error on failure
  */
-int sg_alloc_table_from_pages(struct sg_table *sgt,
-	struct page **pages, unsigned int n_pages,
-	unsigned int offset, unsigned long size,
-	gfp_t gfp_mask)
+int __sg_alloc_table_from_pages(struct sg_table *sgt, struct page **pages,
+				unsigned int n_pages, unsigned int offset,
+				unsigned long size, unsigned int max_segment,
+				gfp_t gfp_mask)
 {
-	const unsigned int max_segment = SCATTERLIST_MAX_SEGMENT;
 	unsigned int chunks, cur_page, seg_len, i;
 	int ret;
 	struct scatterlist *s;
 
+	if (WARN_ON(!max_segment || offset_in_page(max_segment)))
+		return -EINVAL;
+
 	/* compute number of contiguous chunks */
 	chunks = 1;
 	seg_len = 0;
@@ -440,6 +443,35 @@ int sg_alloc_table_from_pages(struct sg_table *sgt,
 
 	return 0;
 }
+EXPORT_SYMBOL(__sg_alloc_table_from_pages);
+
+/**
+ * sg_alloc_table_from_pages - Allocate and initialize an sg table from
+ *			       an array of pages
+ * @sgt:	 The sg table header to use
+ * @pages:	 Pointer to an array of page pointers
+ * @n_pages:	 Number of pages in the pages array
+ * @offset:      Offset from start of the first page to the start of a buffer
+ * @size:        Number of valid bytes in the buffer (after offset)
+ * @gfp_mask:	 GFP allocation mask
+ *
+ *  Description:
+ *    Allocate and initialize an sg table from a list of pages. Contiguous
+ *    ranges of the pages are squashed into a single scatterlist node. A user
+ *    may provide an offset at a start and a size of valid data in a buffer
+ *    specified by the page array. The returned sg table is released by
+ *    sg_free_table.
+ *
+ * Returns:
+ *   0 on success, negative error on failure
+ */
+int sg_alloc_table_from_pages(struct sg_table *sgt, struct page **pages,
+			      unsigned int n_pages, unsigned int offset,
+			      unsigned long size, gfp_t gfp_mask)
+{
+	return __sg_alloc_table_from_pages(sgt, pages, n_pages, offset, size,
+					   SCATTERLIST_MAX_SEGMENT, gfp_mask);
+}
 EXPORT_SYMBOL(sg_alloc_table_from_pages);
 
 void __sg_page_iter_start(struct sg_page_iter *piter,
-- 
2.9.4

[PATCH v7 3/5] lib/scatterlist: Introduce and export __sg_alloc_table_from_pages

[Tvrtko Ursulin]

From: Tvrtko Ursulin <tvrtko.ursulin@intel.com>

Drivers like i915 benefit from being able to control the maxium
size of the sg coalesced segment while building the scatter-
gather list.

Introduce and export the __sg_alloc_table_from_pages function
which will allow it that control.

v2: Reorder parameters. (Chris Wilson)
v3: Fix incomplete reordering in v2.
v4: max_segment needs to be page aligned.
v5: Rebase.
v6: Rebase.
v7: Fix spelling in commit and mention max segment size in
    __sg_alloc_table_from_pages kerneldoc. (Andrew Morton)

Signed-off-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
Cc: Masahiro Yamada <yamada.masahiro@socionext.com>
Cc: linux-kernel@vger.kernel.org
Cc: Chris Wilson <chris@chris-wilson.co.uk>
Reviewed-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
---
 include/linux/scatterlist.h | 11 +++++---
 lib/scatterlist.c           | 66 +++++++++++++++++++++++++++++++++------------
 2 files changed, 56 insertions(+), 21 deletions(-)

diff --git a/include/linux/scatterlist.h b/include/linux/scatterlist.h
index 6dd2ddbc6230..874b50c232de 100644
--- a/include/linux/scatterlist.h
+++ b/include/linux/scatterlist.h
@@ -267,10 +267,13 @@ void sg_free_table(struct sg_table *);
 int __sg_alloc_table(struct sg_table *, unsigned int, unsigned int,
 		     struct scatterlist *, gfp_t, sg_alloc_fn *);
 int sg_alloc_table(struct sg_table *, unsigned int, gfp_t);
-int sg_alloc_table_from_pages(struct sg_table *sgt,
-	struct page **pages, unsigned int n_pages,
-	unsigned int offset, unsigned long size,
-	gfp_t gfp_mask);
+int __sg_alloc_table_from_pages(struct sg_table *sgt, struct page **pages,
+				unsigned int n_pages, unsigned int offset,
+				unsigned long size, unsigned int max_segment,
+				gfp_t gfp_mask);
+int sg_alloc_table_from_pages(struct sg_table *sgt, struct page **pages,
+			      unsigned int n_pages, unsigned int offset,
+			      unsigned long size, gfp_t gfp_mask);
 
 size_t sg_copy_buffer(struct scatterlist *sgl, unsigned int nents, void *buf,
 		      size_t buflen, off_t skip, bool to_buffer);
diff --git a/lib/scatterlist.c b/lib/scatterlist.c
index 7b2e74da2c44..7c1c55f7daaa 100644
--- a/lib/scatterlist.c
+++ b/lib/scatterlist.c
@@ -370,35 +370,38 @@ int sg_alloc_table(struct sg_table *table, unsigned int nents, gfp_t gfp_mask)
 EXPORT_SYMBOL(sg_alloc_table);
 
 /**
- * sg_alloc_table_from_pages - Allocate and initialize an sg table from
- *			       an array of pages
- * @sgt:	The sg table header to use
- * @pages:	Pointer to an array of page pointers
- * @n_pages:	Number of pages in the pages array
- * @offset:     Offset from start of the first page to the start of a buffer
- * @size:       Number of valid bytes in the buffer (after offset)
- * @gfp_mask:	GFP allocation mask
+ * __sg_alloc_table_from_pages - Allocate and initialize an sg table from
+ *			         an array of pages
+ * @sgt:	 The sg table header to use
+ * @pages:	 Pointer to an array of page pointers
+ * @n_pages:	 Number of pages in the pages array
+ * @offset:      Offset from start of the first page to the start of a buffer
+ * @size:        Number of valid bytes in the buffer (after offset)
+ * @max_segment: Maximum size of a scatterlist node in bytes (page aligned)
+ * @gfp_mask:	 GFP allocation mask
  *
  *  Description:
  *    Allocate and initialize an sg table from a list of pages. Contiguous
- *    ranges of the pages are squashed into a single scatterlist node. A user
- *    may provide an offset at a start and a size of valid data in a buffer
- *    specified by the page array. The returned sg table is released by
- *    sg_free_table.
+ *    ranges of the pages are squashed into a single scatterlist node up to the
+ *    maximum size specified in @max_segment. An user may provide an offset at a
+ *    start and a size of valid data in a buffer specified by the page array.
+ *    The returned sg table is released by sg_free_table.
  *
  * Returns:
  *   0 on success, negative error on failure
  */
-int sg_alloc_table_from_pages(struct sg_table *sgt,
-	struct page **pages, unsigned int n_pages,
-	unsigned int offset, unsigned long size,
-	gfp_t gfp_mask)
+int __sg_alloc_table_from_pages(struct sg_table *sgt, struct page **pages,
+				unsigned int n_pages, unsigned int offset,
+				unsigned long size, unsigned int max_segment,
+				gfp_t gfp_mask)
 {
-	const unsigned int max_segment = SCATTERLIST_MAX_SEGMENT;
 	unsigned int chunks, cur_page, seg_len, i;
 	int ret;
 	struct scatterlist *s;
 
+	if (WARN_ON(!max_segment || offset_in_page(max_segment)))
+		return -EINVAL;
+
 	/* compute number of contiguous chunks */
 	chunks = 1;
 	seg_len = 0;
@@ -440,6 +443,35 @@ int sg_alloc_table_from_pages(struct sg_table *sgt,
 
 	return 0;
 }
+EXPORT_SYMBOL(__sg_alloc_table_from_pages);
+
+/**
+ * sg_alloc_table_from_pages - Allocate and initialize an sg table from
+ *			       an array of pages
+ * @sgt:	 The sg table header to use
+ * @pages:	 Pointer to an array of page pointers
+ * @n_pages:	 Number of pages in the pages array
+ * @offset:      Offset from start of the first page to the start of a buffer
+ * @size:        Number of valid bytes in the buffer (after offset)
+ * @gfp_mask:	 GFP allocation mask
+ *
+ *  Description:
+ *    Allocate and initialize an sg table from a list of pages. Contiguous
+ *    ranges of the pages are squashed into a single scatterlist node. A user
+ *    may provide an offset at a start and a size of valid data in a buffer
+ *    specified by the page array. The returned sg table is released by
+ *    sg_free_table.
+ *
+ * Returns:
+ *   0 on success, negative error on failure
+ */
+int sg_alloc_table_from_pages(struct sg_table *sgt, struct page **pages,
+			      unsigned int n_pages, unsigned int offset,
+			      unsigned long size, gfp_t gfp_mask)
+{
+	return __sg_alloc_table_from_pages(sgt, pages, n_pages, offset, size,
+					   SCATTERLIST_MAX_SEGMENT, gfp_mask);
+}
 EXPORT_SYMBOL(sg_alloc_table_from_pages);
 
 void __sg_page_iter_start(struct sg_page_iter *piter,
-- 
2.9.4

[PATCH 4/5] drm/i915: Use __sg_alloc_table_from_pages for userptr allocations

[Tvrtko Ursulin]

From: Tvrtko Ursulin <tvrtko.ursulin@intel.com>

With the addition of __sg_alloc_table_from_pages we can control
the maximum coallescing size and eliminate a separate path for
allocating backing store here.

Similar to 871dfbd67d4e ("drm/i915: Allow compaction upto
SWIOTLB max segment size") this enables more compact sg lists to
be created and so has a beneficial effect on workloads with many
and/or large objects of this class.

v2:
 * Rename helper to i915_sg_segment_size and fix swiotlb override.
 * Commit message update.

v3:
 * Actually include the swiotlb override fix.

v4:
 * Regroup parameters a bit. (Chris Wilson)

v5:
 * Rebase for swiotlb_max_segment.
 * Add DMA map failure handling as in abb0deacb5a6
   ("drm/i915: Fallback to single PAGE_SIZE segments for DMA remapping").

v6: Handle swiotlb_max_segment() returning 1. (Joonas Lahtinen)

v7: Rebase.

Signed-off-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
Cc: Chris Wilson <chris@chris-wilson.co.uk>
Cc: linux-kernel@vger.kernel.org
Reviewed-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
---
 drivers/gpu/drm/i915/i915_drv.h         | 15 +++++++
 drivers/gpu/drm/i915/i915_gem.c         |  6 +--
 drivers/gpu/drm/i915/i915_gem_userptr.c | 79 ++++++++++++---------------------
 3 files changed, 45 insertions(+), 55 deletions(-)

diff --git a/drivers/gpu/drm/i915/i915_drv.h b/drivers/gpu/drm/i915/i915_drv.h
index 2c7456f4ed38..6383940e8d55 100644
--- a/drivers/gpu/drm/i915/i915_drv.h
+++ b/drivers/gpu/drm/i915/i915_drv.h
@@ -2749,6 +2749,21 @@ static inline struct scatterlist *__sg_next(struct scatterlist *sg)
 	     (((__iter).curr += PAGE_SIZE) < (__iter).max) ||		\
 	     ((__iter) = __sgt_iter(__sg_next((__iter).sgp), false), 0))
 
+static inline unsigned int i915_sg_segment_size(void)
+{
+	unsigned int size = swiotlb_max_segment();
+
+	if (size == 0)
+		return SCATTERLIST_MAX_SEGMENT;
+
+	size = rounddown(size, PAGE_SIZE);
+	/* swiotlb_max_segment_size can return 1 byte when it means one page. */
+	if (size < PAGE_SIZE)
+		size = PAGE_SIZE;
+
+	return size;
+}
+
 static inline const struct intel_device_info *
 intel_info(const struct drm_i915_private *dev_priv)
 {
diff --git a/drivers/gpu/drm/i915/i915_gem.c b/drivers/gpu/drm/i915/i915_gem.c
index 6faabf34f142..a60885d6231b 100644
--- a/drivers/gpu/drm/i915/i915_gem.c
+++ b/drivers/gpu/drm/i915/i915_gem.c
@@ -2339,7 +2339,7 @@ i915_gem_object_get_pages_gtt(struct drm_i915_gem_object *obj)
 	struct sgt_iter sgt_iter;
 	struct page *page;
 	unsigned long last_pfn = 0;	/* suppress gcc warning */
-	unsigned int max_segment;
+	unsigned int max_segment = i915_sg_segment_size();
 	gfp_t noreclaim;
 	int ret;
 
@@ -2350,10 +2350,6 @@ i915_gem_object_get_pages_gtt(struct drm_i915_gem_object *obj)
 	GEM_BUG_ON(obj->base.read_domains & I915_GEM_GPU_DOMAINS);
 	GEM_BUG_ON(obj->base.write_domain & I915_GEM_GPU_DOMAINS);
 
-	max_segment = swiotlb_max_segment();
-	if (!max_segment)
-		max_segment = rounddown(UINT_MAX, PAGE_SIZE);
-
 	st = kmalloc(sizeof(*st), GFP_KERNEL);
 	if (st == NULL)
 		return ERR_PTR(-ENOMEM);
diff --git a/drivers/gpu/drm/i915/i915_gem_userptr.c b/drivers/gpu/drm/i915/i915_gem_userptr.c
index ccd09e8419f5..60c10d4118ae 100644
--- a/drivers/gpu/drm/i915/i915_gem_userptr.c
+++ b/drivers/gpu/drm/i915/i915_gem_userptr.c
@@ -399,64 +399,42 @@ struct get_pages_work {
 	struct task_struct *task;
 };
 
-#if IS_ENABLED(CONFIG_SWIOTLB)
-#define swiotlb_active() swiotlb_nr_tbl()
-#else
-#define swiotlb_active() 0
-#endif
-
-static int
-st_set_pages(struct sg_table **st, struct page **pvec, int num_pages)
-{
-	struct scatterlist *sg;
-	int ret, n;
-
-	*st = kmalloc(sizeof(**st), GFP_KERNEL);
-	if (*st == NULL)
-		return -ENOMEM;
-
-	if (swiotlb_active()) {
-		ret = sg_alloc_table(*st, num_pages, GFP_KERNEL);
-		if (ret)
-			goto err;
-
-		for_each_sg((*st)->sgl, sg, num_pages, n)
-			sg_set_page(sg, pvec[n], PAGE_SIZE, 0);
-	} else {
-		ret = sg_alloc_table_from_pages(*st, pvec, num_pages,
-						0, num_pages << PAGE_SHIFT,
-						GFP_KERNEL);
-		if (ret)
-			goto err;
-	}
-
-	return 0;
-
-err:
-	kfree(*st);
-	*st = NULL;
-	return ret;
-}
-
 static struct sg_table *
-__i915_gem_userptr_set_pages(struct drm_i915_gem_object *obj,
-			     struct page **pvec, int num_pages)
+__i915_gem_userptr_alloc_pages(struct drm_i915_gem_object *obj,
+			       struct page **pvec, int num_pages)
 {
-	struct sg_table *pages;
+	unsigned int max_segment = i915_sg_segment_size();
+	struct sg_table *st;
 	int ret;
 
-	ret = st_set_pages(&pages, pvec, num_pages);
-	if (ret)
+	st = kmalloc(sizeof(*st), GFP_KERNEL);
+	if (!st)
+		return ERR_PTR(-ENOMEM);
+
+alloc_table:
+	ret = __sg_alloc_table_from_pages(st, pvec, num_pages,
+					  0, num_pages << PAGE_SHIFT,
+					  max_segment,
+					  GFP_KERNEL);
+	if (ret) {
+		kfree(st);
 		return ERR_PTR(ret);
+	}
 
-	ret = i915_gem_gtt_prepare_pages(obj, pages);
+	ret = i915_gem_gtt_prepare_pages(obj, st);
 	if (ret) {
-		sg_free_table(pages);
-		kfree(pages);
+		sg_free_table(st);
+
+		if (max_segment > PAGE_SIZE) {
+			max_segment = PAGE_SIZE;
+			goto alloc_table;
+		}
+
+		kfree(st);
 		return ERR_PTR(ret);
 	}
 
-	return pages;
+	return st;
 }
 
 static int
@@ -540,7 +518,8 @@ __i915_gem_userptr_get_pages_worker(struct work_struct *_work)
 		struct sg_table *pages = ERR_PTR(ret);
 
 		if (pinned == npages) {
-			pages = __i915_gem_userptr_set_pages(obj, pvec, npages);
+			pages = __i915_gem_userptr_alloc_pages(obj, pvec,
+							       npages);
 			if (!IS_ERR(pages)) {
 				__i915_gem_object_set_pages(obj, pages);
 				pinned = 0;
@@ -661,7 +640,7 @@ i915_gem_userptr_get_pages(struct drm_i915_gem_object *obj)
 		pages = __i915_gem_userptr_get_pages_schedule(obj);
 		active = pages == ERR_PTR(-EAGAIN);
 	} else {
-		pages = __i915_gem_userptr_set_pages(obj, pvec, num_pages);
+		pages = __i915_gem_userptr_alloc_pages(obj, pvec, num_pages);
 		active = !IS_ERR(pages);
 	}
 	if (active)
-- 
2.9.4

[PATCH v8 4/5] drm/i915: Use __sg_alloc_table_from_pages for userptr allocations

[Tvrtko Ursulin]

From: Tvrtko Ursulin <tvrtko.ursulin@intel.com>

With the addition of __sg_alloc_table_from_pages we can control
the maximum coalescing size and eliminate a separate path for
allocating backing store here.

Similar to 871dfbd67d4e ("drm/i915: Allow compaction upto
SWIOTLB max segment size") this enables more compact sg lists to
be created and so has a beneficial effect on workloads with many
and/or large objects of this class.

v2:
 * Rename helper to i915_sg_segment_size and fix swiotlb override.
 * Commit message update.

v3:
 * Actually include the swiotlb override fix.

v4:
 * Regroup parameters a bit. (Chris Wilson)

v5:
 * Rebase for swiotlb_max_segment.
 * Add DMA map failure handling as in abb0deacb5a6
   ("drm/i915: Fallback to single PAGE_SIZE segments for DMA remapping").

v6: Handle swiotlb_max_segment() returning 1. (Joonas Lahtinen)

v7: Rebase.
v8: Commit spelling fix.

Signed-off-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
Cc: Chris Wilson <chris@chris-wilson.co.uk>
Cc: linux-kernel@vger.kernel.org
Reviewed-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
---
 drivers/gpu/drm/i915/i915_drv.h         | 15 +++++++
 drivers/gpu/drm/i915/i915_gem.c         |  6 +--
 drivers/gpu/drm/i915/i915_gem_userptr.c | 79 ++++++++++++---------------------
 3 files changed, 45 insertions(+), 55 deletions(-)

diff --git a/drivers/gpu/drm/i915/i915_drv.h b/drivers/gpu/drm/i915/i915_drv.h
index 2c7456f4ed38..6383940e8d55 100644
--- a/drivers/gpu/drm/i915/i915_drv.h
+++ b/drivers/gpu/drm/i915/i915_drv.h
@@ -2749,6 +2749,21 @@ static inline struct scatterlist *__sg_next(struct scatterlist *sg)
 	     (((__iter).curr += PAGE_SIZE) < (__iter).max) ||		\
 	     ((__iter) = __sgt_iter(__sg_next((__iter).sgp), false), 0))
 
+static inline unsigned int i915_sg_segment_size(void)
+{
+	unsigned int size = swiotlb_max_segment();
+
+	if (size == 0)
+		return SCATTERLIST_MAX_SEGMENT;
+
+	size = rounddown(size, PAGE_SIZE);
+	/* swiotlb_max_segment_size can return 1 byte when it means one page. */
+	if (size < PAGE_SIZE)
+		size = PAGE_SIZE;
+
+	return size;
+}
+
 static inline const struct intel_device_info *
 intel_info(const struct drm_i915_private *dev_priv)
 {
diff --git a/drivers/gpu/drm/i915/i915_gem.c b/drivers/gpu/drm/i915/i915_gem.c
index 6faabf34f142..a60885d6231b 100644
--- a/drivers/gpu/drm/i915/i915_gem.c
+++ b/drivers/gpu/drm/i915/i915_gem.c
@@ -2339,7 +2339,7 @@ i915_gem_object_get_pages_gtt(struct drm_i915_gem_object *obj)
 	struct sgt_iter sgt_iter;
 	struct page *page;
 	unsigned long last_pfn = 0;	/* suppress gcc warning */
-	unsigned int max_segment;
+	unsigned int max_segment = i915_sg_segment_size();
 	gfp_t noreclaim;
 	int ret;
 
@@ -2350,10 +2350,6 @@ i915_gem_object_get_pages_gtt(struct drm_i915_gem_object *obj)
 	GEM_BUG_ON(obj->base.read_domains & I915_GEM_GPU_DOMAINS);
 	GEM_BUG_ON(obj->base.write_domain & I915_GEM_GPU_DOMAINS);
 
-	max_segment = swiotlb_max_segment();
-	if (!max_segment)
-		max_segment = rounddown(UINT_MAX, PAGE_SIZE);
-
 	st = kmalloc(sizeof(*st), GFP_KERNEL);
 	if (st == NULL)
 		return ERR_PTR(-ENOMEM);
diff --git a/drivers/gpu/drm/i915/i915_gem_userptr.c b/drivers/gpu/drm/i915/i915_gem_userptr.c
index ccd09e8419f5..60c10d4118ae 100644
--- a/drivers/gpu/drm/i915/i915_gem_userptr.c
+++ b/drivers/gpu/drm/i915/i915_gem_userptr.c
@@ -399,64 +399,42 @@ struct get_pages_work {
 	struct task_struct *task;
 };
 
-#if IS_ENABLED(CONFIG_SWIOTLB)
-#define swiotlb_active() swiotlb_nr_tbl()
-#else
-#define swiotlb_active() 0
-#endif
-
-static int
-st_set_pages(struct sg_table **st, struct page **pvec, int num_pages)
-{
-	struct scatterlist *sg;
-	int ret, n;
-
-	*st = kmalloc(sizeof(**st), GFP_KERNEL);
-	if (*st == NULL)
-		return -ENOMEM;
-
-	if (swiotlb_active()) {
-		ret = sg_alloc_table(*st, num_pages, GFP_KERNEL);
-		if (ret)
-			goto err;
-
-		for_each_sg((*st)->sgl, sg, num_pages, n)
-			sg_set_page(sg, pvec[n], PAGE_SIZE, 0);
-	} else {
-		ret = sg_alloc_table_from_pages(*st, pvec, num_pages,
-						0, num_pages << PAGE_SHIFT,
-						GFP_KERNEL);
-		if (ret)
-			goto err;
-	}
-
-	return 0;
-
-err:
-	kfree(*st);
-	*st = NULL;
-	return ret;
-}
-
 static struct sg_table *
-__i915_gem_userptr_set_pages(struct drm_i915_gem_object *obj,
-			     struct page **pvec, int num_pages)
+__i915_gem_userptr_alloc_pages(struct drm_i915_gem_object *obj,
+			       struct page **pvec, int num_pages)
 {
-	struct sg_table *pages;
+	unsigned int max_segment = i915_sg_segment_size();
+	struct sg_table *st;
 	int ret;
 
-	ret = st_set_pages(&pages, pvec, num_pages);
-	if (ret)
+	st = kmalloc(sizeof(*st), GFP_KERNEL);
+	if (!st)
+		return ERR_PTR(-ENOMEM);
+
+alloc_table:
+	ret = __sg_alloc_table_from_pages(st, pvec, num_pages,
+					  0, num_pages << PAGE_SHIFT,
+					  max_segment,
+					  GFP_KERNEL);
+	if (ret) {
+		kfree(st);
 		return ERR_PTR(ret);
+	}
 
-	ret = i915_gem_gtt_prepare_pages(obj, pages);
+	ret = i915_gem_gtt_prepare_pages(obj, st);
 	if (ret) {
-		sg_free_table(pages);
-		kfree(pages);
+		sg_free_table(st);
+
+		if (max_segment > PAGE_SIZE) {
+			max_segment = PAGE_SIZE;
+			goto alloc_table;
+		}
+
+		kfree(st);
 		return ERR_PTR(ret);
 	}
 
-	return pages;
+	return st;
 }
 
 static int
@@ -540,7 +518,8 @@ __i915_gem_userptr_get_pages_worker(struct work_struct *_work)
 		struct sg_table *pages = ERR_PTR(ret);
 
 		if (pinned == npages) {
-			pages = __i915_gem_userptr_set_pages(obj, pvec, npages);
+			pages = __i915_gem_userptr_alloc_pages(obj, pvec,
+							       npages);
 			if (!IS_ERR(pages)) {
 				__i915_gem_object_set_pages(obj, pages);
 				pinned = 0;
@@ -661,7 +640,7 @@ i915_gem_userptr_get_pages(struct drm_i915_gem_object *obj)
 		pages = __i915_gem_userptr_get_pages_schedule(obj);
 		active = pages == ERR_PTR(-EAGAIN);
 	} else {
-		pages = __i915_gem_userptr_set_pages(obj, pvec, num_pages);
+		pages = __i915_gem_userptr_alloc_pages(obj, pvec, num_pages);
 		active = !IS_ERR(pages);
 	}
 	if (active)
-- 
2.9.4

[PATCH 5/5] tools/testing/scatterlist: Test new __sg_alloc_table_from_pages

[Tvrtko Ursulin]

From: Tvrtko Ursulin <tvrtko.ursulin@intel.com>

Exercise the new __sg_alloc_table_from_pages API (and through
it also the old sg_alloc_table_from_pages), checking that the
created table has the expected number of segments depending on
the sequence of input pages and other conditions.

Signed-off-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
Cc: Chris Wilson <chris@chris-wilson.co.uk>
Cc: linux-kernel@vger.kernel.org
---
 tools/testing/scatterlist/Makefile   |  30 +++++++++
 tools/testing/scatterlist/linux/mm.h | 125 +++++++++++++++++++++++++++++++++++
 tools/testing/scatterlist/main.c     | 112 +++++++++++++++++++++++++++++++
 3 files changed, 267 insertions(+)
 create mode 100644 tools/testing/scatterlist/Makefile
 create mode 100644 tools/testing/scatterlist/linux/mm.h
 create mode 100644 tools/testing/scatterlist/main.c

diff --git a/tools/testing/scatterlist/Makefile b/tools/testing/scatterlist/Makefile
new file mode 100644
index 000000000000..0867e0ef32d6
--- /dev/null
+++ b/tools/testing/scatterlist/Makefile
@@ -0,0 +1,30 @@
+CFLAGS += -I. -I../../include -g -O2 -Wall -fsanitize=address
+LDFLAGS += -fsanitize=address
+TARGETS = main
+OFILES = main.o scatterlist.o
+
+ifeq ($(BUILD), 32)
+        CFLAGS += -m32
+        LDFLAGS += -m32
+endif
+
+targets: include $(TARGETS)
+
+main: $(OFILES)
+
+clean:
+	$(RM) $(TARGETS) $(OFILES) scatterlist.c linux/scatterlist.h linux/highmem.h linux/kmemleak.h asm/io.h
+	@rmdir asm
+
+scatterlist.c: ../../../lib/scatterlist.c
+	@sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@
+
+.PHONY: include
+
+include: ../../../include/linux/scatterlist.h
+	@mkdir -p linux
+	@mkdir -p asm
+	@touch asm/io.h
+	@touch linux/highmem.h
+	@touch linux/kmemleak.h
+	@cp $< linux/scatterlist.h
diff --git a/tools/testing/scatterlist/linux/mm.h b/tools/testing/scatterlist/linux/mm.h
new file mode 100644
index 000000000000..ccbb248ebdc1
--- /dev/null
+++ b/tools/testing/scatterlist/linux/mm.h
@@ -0,0 +1,125 @@
+#ifndef _LINUX_MM_H
+#define _LINUX_MM_H
+
+#include <assert.h>
+#include <string.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <limits.h>
+#include <stdio.h>
+
+typedef unsigned long dma_addr_t;
+
+#define unlikely
+
+#define BUG_ON(x) assert(!(x))
+
+#define WARN_ON(condition) ({                                           \
+        int __ret_warn_on = !!(condition);                              \
+        unlikely(__ret_warn_on);                                        \
+})
+
+#define WARN_ON_ONCE(condition) ({                              \
+        int __ret_warn_on = !!(condition);                      \
+        if (unlikely(__ret_warn_on))                            \
+                assert(0);                                      \
+        unlikely(__ret_warn_on);                                \
+})
+
+#define PAGE_SIZE	(4096)
+#define PAGE_SHIFT	(12)
+#define PAGE_MASK	(~(PAGE_SIZE-1))
+
+#define __ALIGN_KERNEL(x, a)            __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
+#define __ALIGN_KERNEL_MASK(x, mask)    (((x) + (mask)) & ~(mask))
+#define ALIGN(x, a)             __ALIGN_KERNEL((x), (a))
+
+#define PAGE_ALIGN(addr) ALIGN(addr, PAGE_SIZE)
+
+#define offset_in_page(p)	((unsigned long)(p) & ~PAGE_MASK)
+
+#define virt_to_page(x)	((void *)x)
+#define page_address(x)	((void *)x)
+
+static inline unsigned long page_to_phys(struct page *page)
+{
+	assert(0);
+
+	return 0;
+}
+
+#define page_to_pfn(page) ((unsigned long)(page) / PAGE_SIZE)
+#define pfn_to_page(pfn) (void *)((pfn) * PAGE_SIZE)
+#define nth_page(page,n) pfn_to_page(page_to_pfn((page)) + (n))
+
+#define __min(t1, t2, min1, min2, x, y) ({              \
+        t1 min1 = (x);                                  \
+        t2 min2 = (y);                                  \
+        (void) (&min1 == &min2);                        \
+        min1 < min2 ? min1 : min2; })
+
+#define ___PASTE(a,b) a##b
+#define __PASTE(a,b) ___PASTE(a,b)
+
+#define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __COUNTER__)
+
+#define min(x, y)                                       \
+        __min(typeof(x), typeof(y),                     \
+              __UNIQUE_ID(min1_), __UNIQUE_ID(min2_),   \
+              x, y)
+
+#define min_t(type, x, y)                               \
+        __min(type, type,                               \
+              __UNIQUE_ID(min1_), __UNIQUE_ID(min2_),   \
+              x, y)
+
+#define preemptible() (1)
+
+static inline void *kmap(struct page *page)
+{
+	assert(0);
+
+	return NULL;
+}
+
+static inline void *kmap_atomic(struct page *page)
+{
+	assert(0);
+
+	return NULL;
+}
+
+static inline void kunmap(void *addr)
+{
+	assert(0);
+}
+
+static inline void kunmap_atomic(void *addr)
+{
+	assert(0);
+}
+
+static inline unsigned long __get_free_page(unsigned int flags)
+{
+	return (unsigned long)malloc(PAGE_SIZE);
+}
+
+static inline void free_page(unsigned long page)
+{
+	free((void *)page);
+}
+
+static inline void *kmalloc(unsigned int size, unsigned int flags)
+{
+	return malloc(size);
+}
+
+#define kfree(x) free(x)
+
+#define kmemleak_alloc(a, b, c, d)
+#define kmemleak_free(a)
+
+#define PageSlab(p) (0)
+#define flush_kernel_dcache_page(p)
+
+#endif
diff --git a/tools/testing/scatterlist/main.c b/tools/testing/scatterlist/main.c
new file mode 100644
index 000000000000..edf9b2960734
--- /dev/null
+++ b/tools/testing/scatterlist/main.c
@@ -0,0 +1,112 @@
+#include <stdio.h>
+#include <assert.h>
+
+#include <linux/scatterlist.h>
+
+#define MAX_PAGES (64)
+
+static unsigned
+_set_pages(struct page **pages, const unsigned *array, unsigned num)
+{
+	unsigned int i;
+
+	assert(num < MAX_PAGES);
+
+	for (i = 0; i < num; i++)
+		pages[i] = (struct page *)(unsigned long)
+			   ((1 + array[i]) * PAGE_SIZE);
+
+	return num;
+}
+
+#define set_pages(p, a) _set_pages((p), (a), sizeof(a) / sizeof(a[0]))
+
+#define check_and_free(_st, _ret, _nents) \
+{ \
+	assert((_ret) == 0); \
+	assert((_st)->nents == _nents); \
+	assert((_st)->orig_nents == _nents); \
+	sg_free_table(_st); \
+}
+
+static int
+alloc_tbl(struct sg_table *st, struct page **pages, unsigned nr_pages,
+	  unsigned offset, unsigned size, unsigned max)
+{
+	return __sg_alloc_table_from_pages(st, pages, nr_pages, offset, size,
+					   max, GFP_KERNEL);
+}
+
+int main(void)
+{
+	const unsigned int sgmax = SCATTERLIST_MAX_SEGMENT;
+	struct page *pages[MAX_PAGES];
+	struct sg_table st;
+	int ret;
+
+	ret = set_pages(pages, ((unsigned []){ 0 }));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, PAGE_SIZE + 1);
+	assert(ret == -EINVAL);
+
+	ret = set_pages(pages, ((unsigned []){ 0 }));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, 0);
+	assert(ret == -EINVAL);
+
+	ret = set_pages(pages, ((unsigned []){ 0 }));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, sgmax);
+	check_and_free(&st, ret, 1);
+
+	ret = set_pages(pages, ((unsigned []){ 0 }));
+	ret = alloc_tbl(&st, pages, ret, 0, ret, sgmax);
+	check_and_free(&st, ret, 1);
+
+	ret = set_pages(pages, ((unsigned []){ 0, 1 }));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, sgmax);
+	check_and_free(&st, ret, 1);
+
+	ret = set_pages(pages, ((unsigned []){ 0, 2 }));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, sgmax);
+	check_and_free(&st, ret, 2);
+
+	ret = set_pages(pages, ((unsigned []){ 0, 1, 3 }));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, sgmax);
+	check_and_free(&st, ret, 2);
+
+	ret = set_pages(pages, ((unsigned []){ 0, 1, 3, 4 }));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, sgmax);
+	check_and_free(&st, ret, 2);
+
+	ret = set_pages(pages, ((unsigned []){ 0, 1, 3, 4, 5 }));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, sgmax);
+	check_and_free(&st, ret, 2);
+
+	ret = set_pages(pages, ((unsigned []){ 0, 1, 3, 4, 6 }));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, sgmax);
+	check_and_free(&st, ret, 3);
+
+	ret = set_pages(pages, ((unsigned []){ 0, 2, 4, 6, 8 }));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, sgmax);
+	check_and_free(&st, ret, 5);
+
+	ret = set_pages(pages, ((unsigned []){ 0, 1, 2, 3, 4 }));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, sgmax);
+	check_and_free(&st, ret, 1);
+
+	ret = set_pages(pages, ((unsigned []){ 0, 1, 2, 3, 4 }));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, 2 * PAGE_SIZE);
+	check_and_free(&st, ret, 3);
+
+	ret = set_pages(pages, ((unsigned []){ 0, 1, 2, 3, 4, 5}));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, 2 * PAGE_SIZE);
+	check_and_free(&st, ret, 3);
+
+	ret = set_pages(pages, ((unsigned []){ 0, 2, 3, 4, 5, 6}));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, 2 * PAGE_SIZE);
+	check_and_free(&st, ret, 4);
+
+	ret = set_pages(pages, ((unsigned []){ 0, 1, 3, 4, 5, 6}));
+	ret = alloc_tbl(&st, pages, ret, 0, ret * PAGE_SIZE, 2 * PAGE_SIZE);
+	check_and_free(&st, ret, 3);
+
+	return 0;
+}
-- 
2.9.4

[PATCH v2 5/5] tools/testing/scatterlist: Test new __sg_alloc_table_from_pages

[Tvrtko Ursulin]

From: Tvrtko Ursulin <tvrtko.ursulin@intel.com>

Exercise the new __sg_alloc_table_from_pages API (and through
it also the old sg_alloc_table_from_pages), checking that the
created table has the expected number of segments depending on
the sequence of input pages and other conditions.

v2: Move to data driven for readability.

Signed-off-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
Cc: Chris Wilson <chris@chris-wilson.co.uk>
Cc: linux-kernel@vger.kernel.org
---
 tools/testing/scatterlist/Makefile   |  30 +++++++++
 tools/testing/scatterlist/linux/mm.h | 125 +++++++++++++++++++++++++++++++++++
 tools/testing/scatterlist/main.c     |  74 +++++++++++++++++++++
 3 files changed, 229 insertions(+)
 create mode 100644 tools/testing/scatterlist/Makefile
 create mode 100644 tools/testing/scatterlist/linux/mm.h
 create mode 100644 tools/testing/scatterlist/main.c

diff --git a/tools/testing/scatterlist/Makefile b/tools/testing/scatterlist/Makefile
new file mode 100644
index 000000000000..0867e0ef32d6
--- /dev/null
+++ b/tools/testing/scatterlist/Makefile
@@ -0,0 +1,30 @@
+CFLAGS += -I. -I../../include -g -O2 -Wall -fsanitize=address
+LDFLAGS += -fsanitize=address
+TARGETS = main
+OFILES = main.o scatterlist.o
+
+ifeq ($(BUILD), 32)
+        CFLAGS += -m32
+        LDFLAGS += -m32
+endif
+
+targets: include $(TARGETS)
+
+main: $(OFILES)
+
+clean:
+	$(RM) $(TARGETS) $(OFILES) scatterlist.c linux/scatterlist.h linux/highmem.h linux/kmemleak.h asm/io.h
+	@rmdir asm
+
+scatterlist.c: ../../../lib/scatterlist.c
+	@sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@
+
+.PHONY: include
+
+include: ../../../include/linux/scatterlist.h
+	@mkdir -p linux
+	@mkdir -p asm
+	@touch asm/io.h
+	@touch linux/highmem.h
+	@touch linux/kmemleak.h
+	@cp $< linux/scatterlist.h
diff --git a/tools/testing/scatterlist/linux/mm.h b/tools/testing/scatterlist/linux/mm.h
new file mode 100644
index 000000000000..ccbb248ebdc1
--- /dev/null
+++ b/tools/testing/scatterlist/linux/mm.h
@@ -0,0 +1,125 @@
+#ifndef _LINUX_MM_H
+#define _LINUX_MM_H
+
+#include <assert.h>
+#include <string.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <limits.h>
+#include <stdio.h>
+
+typedef unsigned long dma_addr_t;
+
+#define unlikely
+
+#define BUG_ON(x) assert(!(x))
+
+#define WARN_ON(condition) ({                                           \
+        int __ret_warn_on = !!(condition);                              \
+        unlikely(__ret_warn_on);                                        \
+})
+
+#define WARN_ON_ONCE(condition) ({                              \
+        int __ret_warn_on = !!(condition);                      \
+        if (unlikely(__ret_warn_on))                            \
+                assert(0);                                      \
+        unlikely(__ret_warn_on);                                \
+})
+
+#define PAGE_SIZE	(4096)
+#define PAGE_SHIFT	(12)
+#define PAGE_MASK	(~(PAGE_SIZE-1))
+
+#define __ALIGN_KERNEL(x, a)            __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
+#define __ALIGN_KERNEL_MASK(x, mask)    (((x) + (mask)) & ~(mask))
+#define ALIGN(x, a)             __ALIGN_KERNEL((x), (a))
+
+#define PAGE_ALIGN(addr) ALIGN(addr, PAGE_SIZE)
+
+#define offset_in_page(p)	((unsigned long)(p) & ~PAGE_MASK)
+
+#define virt_to_page(x)	((void *)x)
+#define page_address(x)	((void *)x)
+
+static inline unsigned long page_to_phys(struct page *page)
+{
+	assert(0);
+
+	return 0;
+}
+
+#define page_to_pfn(page) ((unsigned long)(page) / PAGE_SIZE)
+#define pfn_to_page(pfn) (void *)((pfn) * PAGE_SIZE)
+#define nth_page(page,n) pfn_to_page(page_to_pfn((page)) + (n))
+
+#define __min(t1, t2, min1, min2, x, y) ({              \
+        t1 min1 = (x);                                  \
+        t2 min2 = (y);                                  \
+        (void) (&min1 == &min2);                        \
+        min1 < min2 ? min1 : min2; })
+
+#define ___PASTE(a,b) a##b
+#define __PASTE(a,b) ___PASTE(a,b)
+
+#define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __COUNTER__)
+
+#define min(x, y)                                       \
+        __min(typeof(x), typeof(y),                     \
+              __UNIQUE_ID(min1_), __UNIQUE_ID(min2_),   \
+              x, y)
+
+#define min_t(type, x, y)                               \
+        __min(type, type,                               \
+              __UNIQUE_ID(min1_), __UNIQUE_ID(min2_),   \
+              x, y)
+
+#define preemptible() (1)
+
+static inline void *kmap(struct page *page)
+{
+	assert(0);
+
+	return NULL;
+}
+
+static inline void *kmap_atomic(struct page *page)
+{
+	assert(0);
+
+	return NULL;
+}
+
+static inline void kunmap(void *addr)
+{
+	assert(0);
+}
+
+static inline void kunmap_atomic(void *addr)
+{
+	assert(0);
+}
+
+static inline unsigned long __get_free_page(unsigned int flags)
+{
+	return (unsigned long)malloc(PAGE_SIZE);
+}
+
+static inline void free_page(unsigned long page)
+{
+	free((void *)page);
+}
+
+static inline void *kmalloc(unsigned int size, unsigned int flags)
+{
+	return malloc(size);
+}
+
+#define kfree(x) free(x)
+
+#define kmemleak_alloc(a, b, c, d)
+#define kmemleak_free(a)
+
+#define PageSlab(p) (0)
+#define flush_kernel_dcache_page(p)
+
+#endif
diff --git a/tools/testing/scatterlist/main.c b/tools/testing/scatterlist/main.c
new file mode 100644
index 000000000000..8ca5c8703eb7
--- /dev/null
+++ b/tools/testing/scatterlist/main.c
@@ -0,0 +1,74 @@
+#include <stdio.h>
+#include <assert.h>
+
+#include <linux/scatterlist.h>
+
+#define MAX_PAGES (64)
+
+static void set_pages(struct page **pages, const unsigned *array, unsigned num)
+{
+	unsigned int i;
+
+	assert(num < MAX_PAGES);
+	for (i = 0; i < num; i++)
+		pages[i] = (struct page *)(unsigned long)
+			   ((1 + array[i]) * PAGE_SIZE);
+}
+
+#define pfn(...) (unsigned []){ __VA_ARGS__ }
+
+int main(void)
+{
+	const unsigned int sgmax = SCATTERLIST_MAX_SEGMENT;
+	struct test {
+		int alloc_ret;
+		unsigned num_pages;
+		unsigned *pfn;
+		unsigned size;
+		unsigned int max_seg;
+		unsigned int expected_segments;
+	} *test, tests[] = {
+		{ -EINVAL, 1, pfn(0), PAGE_SIZE, PAGE_SIZE + 1, 1 },
+		{ -EINVAL, 1, pfn(0), PAGE_SIZE, 0, 1 },
+		{ -EINVAL, 1, pfn(0), PAGE_SIZE, sgmax + 1, 1 },
+		{ 0, 1, pfn(0), PAGE_SIZE, sgmax, 1 },
+		{ 0, 1, pfn(0), 1, sgmax, 1 },
+		{ 0, 2, pfn(0, 1), 2 * PAGE_SIZE, sgmax, 1 },
+		{ 0, 3, pfn(0, 1, 3), 3 * PAGE_SIZE, sgmax, 2 },
+		{ 0, 4, pfn(0, 1, 3, 4), 4 * PAGE_SIZE, sgmax, 2 },
+		{ 0, 5, pfn(0, 1, 3, 4, 5), 5 * PAGE_SIZE, sgmax, 2 },
+		{ 0, 5, pfn(0, 1, 3, 4, 6), 5 * PAGE_SIZE, sgmax, 3 },
+		{ 0, 5, pfn(0, 1, 2, 3, 4), 5 * PAGE_SIZE, sgmax, 1 },
+		{ 0, 5, pfn(0, 1, 2, 3, 4), 5 * PAGE_SIZE, 2 * PAGE_SIZE, 3 },
+		{ 0, 6, pfn(0, 1, 2, 3, 4, 5), 6 * PAGE_SIZE, 2 * PAGE_SIZE, 3 },
+		{ 0, 6, pfn(0, 2, 3, 4, 5, 6), 6 * PAGE_SIZE, 2 * PAGE_SIZE, 4 },
+		{ 0, 6, pfn(0, 1, 3, 4, 5, 6), 6 * PAGE_SIZE, 2 * PAGE_SIZE, 3 },
+		{ 0, 0, NULL, 0, 0, 0 },
+	};
+	unsigned i;
+
+	for (i = 0, test = tests; test->expected_segments; test++, i++) {
+		struct page *pages[MAX_PAGES];
+		struct sg_table st;
+		int ret;
+
+		set_pages(pages, test->pfn, test->num_pages);
+
+		ret = __sg_alloc_table_from_pages(&st, pages, test->num_pages,
+						  0, test->size, test->max_seg,
+						  GFP_KERNEL);
+		assert(ret == test->alloc_ret);
+
+		if (test->alloc_ret)
+			continue;
+
+		assert(st.nents == test->expected_segments);
+		assert(st.orig_nents == test->expected_segments);
+
+		sg_free_table(&st);
+	}
+
+	assert(i == (sizeof(tests) / sizeof(tests[0])) - 1);
+
+	return 0;
+}
-- 
2.9.5

Re: [PATCH v2 5/5] tools/testing/scatterlist: Test new __sg_alloc_table_from_pages

[Chris Wilson]

Quoting Tvrtko Ursulin (2017-09-05 11:24:03)
> From: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
> 
> Exercise the new __sg_alloc_table_from_pages API (and through
> it also the old sg_alloc_table_from_pages), checking that the
> created table has the expected number of segments depending on
> the sequence of input pages and other conditions.
> 
> v2: Move to data driven for readability.
> 
> Signed-off-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
> Cc: Chris Wilson <chris@chris-wilson.co.uk>
> Cc: linux-kernel@vger.kernel.org
> ---
>  tools/testing/scatterlist/Makefile   |  30 +++++++++
>  tools/testing/scatterlist/linux/mm.h | 125 +++++++++++++++++++++++++++++++++++
>  tools/testing/scatterlist/main.c     |  74 +++++++++++++++++++++
>  3 files changed, 229 insertions(+)
>  create mode 100644 tools/testing/scatterlist/Makefile
>  create mode 100644 tools/testing/scatterlist/linux/mm.h
>  create mode 100644 tools/testing/scatterlist/main.c
> 
> diff --git a/tools/testing/scatterlist/Makefile b/tools/testing/scatterlist/Makefile
> new file mode 100644
> index 000000000000..0867e0ef32d6
> --- /dev/null
> +++ b/tools/testing/scatterlist/Makefile
> @@ -0,0 +1,30 @@
> +CFLAGS += -I. -I../../include -g -O2 -Wall -fsanitize=address
> +LDFLAGS += -fsanitize=address
> +TARGETS = main
> +OFILES = main.o scatterlist.o
> +
> +ifeq ($(BUILD), 32)
> +        CFLAGS += -m32
> +        LDFLAGS += -m32
> +endif

Hmm, are there no HOST_CFLAGS? No. I wonder how menuconfig/xconfig get
compiled.

HOSTCC, HOSTCFLAGS.

hostprogs-y := main
always := $(hostprogs-y)

But nothing else seems to use HOSTCC in testing/selftests

> +targets: include $(TARGETS)
> +
> +main: $(OFILES)
> +
> +clean:
> +       $(RM) $(TARGETS) $(OFILES) scatterlist.c linux/scatterlist.h linux/highmem.h linux/kmemleak.h asm/io.h
> +       @rmdir asm
> +
> +scatterlist.c: ../../../lib/scatterlist.c
> +       @sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@

I think I would have used

#define __always_inline inline
#include "../../../lib/scatterlist.c"

> diff --git a/tools/testing/scatterlist/main.c b/tools/testing/scatterlist/main.c
> new file mode 100644
> index 000000000000..8ca5c8703eb7
> --- /dev/null
> +++ b/tools/testing/scatterlist/main.c
> @@ -0,0 +1,74 @@
> +#include <stdio.h>
> +#include <assert.h>
> +
> +#include <linux/scatterlist.h>
> +
> +#define MAX_PAGES (64)
> +
> +static void set_pages(struct page **pages, const unsigned *array, unsigned num)
> +{
> +       unsigned int i;
> +
> +       assert(num < MAX_PAGES);
> +       for (i = 0; i < num; i++)
> +               pages[i] = (struct page *)(unsigned long)
> +                          ((1 + array[i]) * PAGE_SIZE);

pfn_to_page(PFN_BIAS + array[i]) ? Ah, that relies on headers. Ok.

> +}
> +
> +#define pfn(...) (unsigned []){ __VA_ARGS__ }
> +
> +int main(void)
> +{
> +       const unsigned int sgmax = SCATTERLIST_MAX_SEGMENT;
> +       struct test {
> +               int alloc_ret;
> +               unsigned num_pages;
> +               unsigned *pfn;
> +               unsigned size;
> +               unsigned int max_seg;
> +               unsigned int expected_segments;
> +       } *test, tests[] = {
> +               { -EINVAL, 1, pfn(0), PAGE_SIZE, PAGE_SIZE + 1, 1 },
> +               { -EINVAL, 1, pfn(0), PAGE_SIZE, 0, 1 },
> +               { -EINVAL, 1, pfn(0), PAGE_SIZE, sgmax + 1, 1 },
> +               { 0, 1, pfn(0), PAGE_SIZE, sgmax, 1 },
> +               { 0, 1, pfn(0), 1, sgmax, 1 },
> +               { 0, 2, pfn(0, 1), 2 * PAGE_SIZE, sgmax, 1 },
> +               { 0, 3, pfn(0, 1, 3), 3 * PAGE_SIZE, sgmax, 2 },
> +               { 0, 4, pfn(0, 1, 3, 4), 4 * PAGE_SIZE, sgmax, 2 },
> +               { 0, 5, pfn(0, 1, 3, 4, 5), 5 * PAGE_SIZE, sgmax, 2 },
> +               { 0, 5, pfn(0, 1, 3, 4, 6), 5 * PAGE_SIZE, sgmax, 3 },
> +               { 0, 5, pfn(0, 1, 2, 3, 4), 5 * PAGE_SIZE, sgmax, 1 },
> +               { 0, 5, pfn(0, 1, 2, 3, 4), 5 * PAGE_SIZE, 2 * PAGE_SIZE, 3 },
> +               { 0, 6, pfn(0, 1, 2, 3, 4, 5), 6 * PAGE_SIZE, 2 * PAGE_SIZE, 3 },
> +               { 0, 6, pfn(0, 2, 3, 4, 5, 6), 6 * PAGE_SIZE, 2 * PAGE_SIZE, 4 },
> +               { 0, 6, pfn(0, 1, 3, 4, 5, 6), 6 * PAGE_SIZE, 2 * PAGE_SIZE, 3 },

All ascending. Interesting challenge for 3,2,1,0; it can be coalesced,
we just don't. I wonder if we are missing some like that. But for the
moment, 0, 2, 1, would be a good addition to the above set.

Is there any value in checking overflows in this interface?

Lgtm, throw in a couple of inverted positions,
Reviewed-by: Chris Wilson <chris@chris-wilson.co.uk>
-Chris

Re: [Intel-gfx] [PATCH v2 5/5] tools/testing/scatterlist: Test new __sg_alloc_table_from_pages

[Tvrtko Ursulin]

On 06/09/2017 11:48, Chris Wilson wrote:
> Quoting Tvrtko Ursulin (2017-09-05 11:24:03)
>> From: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
>>
>> Exercise the new __sg_alloc_table_from_pages API (and through
>> it also the old sg_alloc_table_from_pages), checking that the
>> created table has the expected number of segments depending on
>> the sequence of input pages and other conditions.
>>
>> v2: Move to data driven for readability.
>>
>> Signed-off-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
>> Cc: Chris Wilson <chris@chris-wilson.co.uk>
>> Cc: linux-kernel@vger.kernel.org
>> ---
>>   tools/testing/scatterlist/Makefile   |  30 +++++++++
>>   tools/testing/scatterlist/linux/mm.h | 125 +++++++++++++++++++++++++++++++++++
>>   tools/testing/scatterlist/main.c     |  74 +++++++++++++++++++++
>>   3 files changed, 229 insertions(+)
>>   create mode 100644 tools/testing/scatterlist/Makefile
>>   create mode 100644 tools/testing/scatterlist/linux/mm.h
>>   create mode 100644 tools/testing/scatterlist/main.c
>>
>> diff --git a/tools/testing/scatterlist/Makefile b/tools/testing/scatterlist/Makefile
>> new file mode 100644
>> index 000000000000..0867e0ef32d6
>> --- /dev/null
>> +++ b/tools/testing/scatterlist/Makefile
>> @@ -0,0 +1,30 @@
>> +CFLAGS += -I. -I../../include -g -O2 -Wall -fsanitize=address
>> +LDFLAGS += -fsanitize=address
>> +TARGETS = main
>> +OFILES = main.o scatterlist.o
>> +
>> +ifeq ($(BUILD), 32)
>> +        CFLAGS += -m32
>> +        LDFLAGS += -m32
>> +endif
> 
> Hmm, are there no HOST_CFLAGS? No. I wonder how menuconfig/xconfig get
> compiled.
> 
> HOSTCC, HOSTCFLAGS.
> 
> hostprogs-y := main
> always := $(hostprogs-y)
> 
> But nothing else seems to use HOSTCC in testing/selftests

I lifted it frim an existing makefile. I think this means no one was 
interested in building tests while doing a cross compile.

>> +targets: include $(TARGETS)
>> +
>> +main: $(OFILES)
>> +
>> +clean:
>> +       $(RM) $(TARGETS) $(OFILES) scatterlist.c linux/scatterlist.h linux/highmem.h linux/kmemleak.h asm/io.h
>> +       @rmdir asm
>> +
>> +scatterlist.c: ../../../lib/scatterlist.c
>> +       @sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@
> 
> I think I would have used
> 
> #define __always_inline inline
> #include "../../../lib/scatterlist.c"

Again, I lifted the approach from one of the existing tests. It might be 
beneficial to have a local copy when debugging, but it is probably very 
marginal and both approaches look OK.

>> diff --git a/tools/testing/scatterlist/main.c b/tools/testing/scatterlist/main.c
>> new file mode 100644
>> index 000000000000..8ca5c8703eb7
>> --- /dev/null
>> +++ b/tools/testing/scatterlist/main.c
>> @@ -0,0 +1,74 @@
>> +#include <stdio.h>
>> +#include <assert.h>
>> +
>> +#include <linux/scatterlist.h>
>> +
>> +#define MAX_PAGES (64)
>> +
>> +static void set_pages(struct page **pages, const unsigned *array, unsigned num)
>> +{
>> +       unsigned int i;
>> +
>> +       assert(num < MAX_PAGES);
>> +       for (i = 0; i < num; i++)
>> +               pages[i] = (struct page *)(unsigned long)
>> +                          ((1 + array[i]) * PAGE_SIZE);
> 
> pfn_to_page(PFN_BIAS + array[i]) ? Ah, that relies on headers. Ok.
> 
>> +}
>> +
>> +#define pfn(...) (unsigned []){ __VA_ARGS__ }
>> +
>> +int main(void)
>> +{
>> +       const unsigned int sgmax = SCATTERLIST_MAX_SEGMENT;
>> +       struct test {
>> +               int alloc_ret;
>> +               unsigned num_pages;
>> +               unsigned *pfn;
>> +               unsigned size;
>> +               unsigned int max_seg;
>> +               unsigned int expected_segments;
>> +       } *test, tests[] = {
>> +               { -EINVAL, 1, pfn(0), PAGE_SIZE, PAGE_SIZE + 1, 1 },
>> +               { -EINVAL, 1, pfn(0), PAGE_SIZE, 0, 1 },
>> +               { -EINVAL, 1, pfn(0), PAGE_SIZE, sgmax + 1, 1 },
>> +               { 0, 1, pfn(0), PAGE_SIZE, sgmax, 1 },
>> +               { 0, 1, pfn(0), 1, sgmax, 1 },
>> +               { 0, 2, pfn(0, 1), 2 * PAGE_SIZE, sgmax, 1 },
>> +               { 0, 3, pfn(0, 1, 3), 3 * PAGE_SIZE, sgmax, 2 },
>> +               { 0, 4, pfn(0, 1, 3, 4), 4 * PAGE_SIZE, sgmax, 2 },
>> +               { 0, 5, pfn(0, 1, 3, 4, 5), 5 * PAGE_SIZE, sgmax, 2 },
>> +               { 0, 5, pfn(0, 1, 3, 4, 6), 5 * PAGE_SIZE, sgmax, 3 },
>> +               { 0, 5, pfn(0, 1, 2, 3, 4), 5 * PAGE_SIZE, sgmax, 1 },
>> +               { 0, 5, pfn(0, 1, 2, 3, 4), 5 * PAGE_SIZE, 2 * PAGE_SIZE, 3 },
>> +               { 0, 6, pfn(0, 1, 2, 3, 4, 5), 6 * PAGE_SIZE, 2 * PAGE_SIZE, 3 },
>> +               { 0, 6, pfn(0, 2, 3, 4, 5, 6), 6 * PAGE_SIZE, 2 * PAGE_SIZE, 4 },
>> +               { 0, 6, pfn(0, 1, 3, 4, 5, 6), 6 * PAGE_SIZE, 2 * PAGE_SIZE, 3 },
> 
> All ascending. Interesting challenge for 3,2,1,0; it can be coalesced,
> we just don't. I wonder if we are missing some like that. But for the

Hm, how do you think descending pages could be coalesced? By 
re-arranging the pages? But that would break everything, do I don't get it.

> moment, 0, 2, 1, would be a good addition to the above set.
> 
> Is there any value in checking overflows in this interface?

Overflows as in size > num_pages * PAGE_SIZE as passed in to 
__sg_alloc_table_from_pages ? It is not checked in the implementation at 
the moment and it looks it is harmless.

There is one test above which checks for underflow (size < num_pages * 
PAGE_SIZE).

> Lgtm, throw in a couple of inverted positions,
> Reviewed-by: Chris Wilson <chris@chris-wilson.co.uk>

Will do, thanks!

Regards,

Tvrtko

Re: [Intel-gfx] [PATCH v2 5/5] tools/testing/scatterlist: Test new __sg_alloc_table_from_pages

[Chris Wilson]

Quoting Tvrtko Ursulin (2017-09-06 13:10:57)
> 
> On 06/09/2017 11:48, Chris Wilson wrote:
> > All ascending. Interesting challenge for 3,2,1,0; it can be coalesced,
> > we just don't. I wonder if we are missing some like that. But for the
> 
> Hm, how do you think descending pages could be coalesced? By 
> re-arranging the pages? But that would break everything, do I don't get it.

Wishful thinking; I wasn't considering the order inside the object, just
their physical addresses.
> 
> > moment, 0, 2, 1, would be a good addition to the above set.
> > 
> > Is there any value in checking overflows in this interface?
> 
> Overflows as in size > num_pages * PAGE_SIZE as passed in to 
> __sg_alloc_table_from_pages ? It is not checked in the implementation at 
> the moment and it looks it is harmless.

Just thinking aloud if there was a way to get a mult/add overflow. That
we do page size coalescing, the only avenue is from a buggy max_seg.

Going back to the makefile, perhaps add the magic for ubsan as well?
-fsanitize=address -fsanitize=undefined
-Chris

[PATCH v3 5/5] tools/testing/scatterlist: Test new __sg_alloc_table_from_pages

[Tvrtko Ursulin]

From: Tvrtko Ursulin <tvrtko.ursulin@intel.com>

Exercise the new __sg_alloc_table_from_pages API (and through
it also the old sg_alloc_table_from_pages), checking that the
created table has the expected number of segments depending on
the sequence of input pages and other conditions.

v2: Move to data driven for readability.
v3: Add some more testcases and -fsanitize=undefined. (Chris Wilson)

Signed-off-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
Cc: Chris Wilson <chris@chris-wilson.co.uk>
Cc: linux-kernel@vger.kernel.org
Reviewed-by: Chris Wilson <chris@chris-wilson.co.uk>
---
 tools/testing/scatterlist/Makefile   |  30 +++++++++
 tools/testing/scatterlist/linux/mm.h | 125 +++++++++++++++++++++++++++++++++++
 tools/testing/scatterlist/main.c     |  79 ++++++++++++++++++++++
 3 files changed, 234 insertions(+)
 create mode 100644 tools/testing/scatterlist/Makefile
 create mode 100644 tools/testing/scatterlist/linux/mm.h
 create mode 100644 tools/testing/scatterlist/main.c

diff --git a/tools/testing/scatterlist/Makefile b/tools/testing/scatterlist/Makefile
new file mode 100644
index 000000000000..933c3a6e4d77
--- /dev/null
+++ b/tools/testing/scatterlist/Makefile
@@ -0,0 +1,30 @@
+CFLAGS += -I. -I../../include -g -O2 -Wall -fsanitize=address
+LDFLAGS += -fsanitize=address -fsanitize=undefined
+TARGETS = main
+OFILES = main.o scatterlist.o
+
+ifeq ($(BUILD), 32)
+        CFLAGS += -m32
+        LDFLAGS += -m32
+endif
+
+targets: include $(TARGETS)
+
+main: $(OFILES)
+
+clean:
+	$(RM) $(TARGETS) $(OFILES) scatterlist.c linux/scatterlist.h linux/highmem.h linux/kmemleak.h asm/io.h
+	@rmdir asm
+
+scatterlist.c: ../../../lib/scatterlist.c
+	@sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@
+
+.PHONY: include
+
+include: ../../../include/linux/scatterlist.h
+	@mkdir -p linux
+	@mkdir -p asm
+	@touch asm/io.h
+	@touch linux/highmem.h
+	@touch linux/kmemleak.h
+	@cp $< linux/scatterlist.h
diff --git a/tools/testing/scatterlist/linux/mm.h b/tools/testing/scatterlist/linux/mm.h
new file mode 100644
index 000000000000..ccbb248ebdc1
--- /dev/null
+++ b/tools/testing/scatterlist/linux/mm.h
@@ -0,0 +1,125 @@
+#ifndef _LINUX_MM_H
+#define _LINUX_MM_H
+
+#include <assert.h>
+#include <string.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <limits.h>
+#include <stdio.h>
+
+typedef unsigned long dma_addr_t;
+
+#define unlikely
+
+#define BUG_ON(x) assert(!(x))
+
+#define WARN_ON(condition) ({                                           \
+        int __ret_warn_on = !!(condition);                              \
+        unlikely(__ret_warn_on);                                        \
+})
+
+#define WARN_ON_ONCE(condition) ({                              \
+        int __ret_warn_on = !!(condition);                      \
+        if (unlikely(__ret_warn_on))                            \
+                assert(0);                                      \
+        unlikely(__ret_warn_on);                                \
+})
+
+#define PAGE_SIZE	(4096)
+#define PAGE_SHIFT	(12)
+#define PAGE_MASK	(~(PAGE_SIZE-1))
+
+#define __ALIGN_KERNEL(x, a)            __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
+#define __ALIGN_KERNEL_MASK(x, mask)    (((x) + (mask)) & ~(mask))
+#define ALIGN(x, a)             __ALIGN_KERNEL((x), (a))
+
+#define PAGE_ALIGN(addr) ALIGN(addr, PAGE_SIZE)
+
+#define offset_in_page(p)	((unsigned long)(p) & ~PAGE_MASK)
+
+#define virt_to_page(x)	((void *)x)
+#define page_address(x)	((void *)x)
+
+static inline unsigned long page_to_phys(struct page *page)
+{
+	assert(0);
+
+	return 0;
+}
+
+#define page_to_pfn(page) ((unsigned long)(page) / PAGE_SIZE)
+#define pfn_to_page(pfn) (void *)((pfn) * PAGE_SIZE)
+#define nth_page(page,n) pfn_to_page(page_to_pfn((page)) + (n))
+
+#define __min(t1, t2, min1, min2, x, y) ({              \
+        t1 min1 = (x);                                  \
+        t2 min2 = (y);                                  \
+        (void) (&min1 == &min2);                        \
+        min1 < min2 ? min1 : min2; })
+
+#define ___PASTE(a,b) a##b
+#define __PASTE(a,b) ___PASTE(a,b)
+
+#define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __COUNTER__)
+
+#define min(x, y)                                       \
+        __min(typeof(x), typeof(y),                     \
+              __UNIQUE_ID(min1_), __UNIQUE_ID(min2_),   \
+              x, y)
+
+#define min_t(type, x, y)                               \
+        __min(type, type,                               \
+              __UNIQUE_ID(min1_), __UNIQUE_ID(min2_),   \
+              x, y)
+
+#define preemptible() (1)
+
+static inline void *kmap(struct page *page)
+{
+	assert(0);
+
+	return NULL;
+}
+
+static inline void *kmap_atomic(struct page *page)
+{
+	assert(0);
+
+	return NULL;
+}
+
+static inline void kunmap(void *addr)
+{
+	assert(0);
+}
+
+static inline void kunmap_atomic(void *addr)
+{
+	assert(0);
+}
+
+static inline unsigned long __get_free_page(unsigned int flags)
+{
+	return (unsigned long)malloc(PAGE_SIZE);
+}
+
+static inline void free_page(unsigned long page)
+{
+	free((void *)page);
+}
+
+static inline void *kmalloc(unsigned int size, unsigned int flags)
+{
+	return malloc(size);
+}
+
+#define kfree(x) free(x)
+
+#define kmemleak_alloc(a, b, c, d)
+#define kmemleak_free(a)
+
+#define PageSlab(p) (0)
+#define flush_kernel_dcache_page(p)
+
+#endif
diff --git a/tools/testing/scatterlist/main.c b/tools/testing/scatterlist/main.c
new file mode 100644
index 000000000000..0a1464181226
--- /dev/null
+++ b/tools/testing/scatterlist/main.c
@@ -0,0 +1,79 @@
+#include <stdio.h>
+#include <assert.h>
+
+#include <linux/scatterlist.h>
+
+#define MAX_PAGES (64)
+
+static void set_pages(struct page **pages, const unsigned *array, unsigned num)
+{
+	unsigned int i;
+
+	assert(num < MAX_PAGES);
+	for (i = 0; i < num; i++)
+		pages[i] = (struct page *)(unsigned long)
+			   ((1 + array[i]) * PAGE_SIZE);
+}
+
+#define pfn(...) (unsigned []){ __VA_ARGS__ }
+
+int main(void)
+{
+	const unsigned int sgmax = SCATTERLIST_MAX_SEGMENT;
+	struct test {
+		int alloc_ret;
+		unsigned num_pages;
+		unsigned *pfn;
+		unsigned size;
+		unsigned int max_seg;
+		unsigned int expected_segments;
+	} *test, tests[] = {
+		{ -EINVAL, 1, pfn(0), PAGE_SIZE, PAGE_SIZE + 1, 1 },
+		{ -EINVAL, 1, pfn(0), PAGE_SIZE, 0, 1 },
+		{ -EINVAL, 1, pfn(0), PAGE_SIZE, sgmax + 1, 1 },
+		{ 0, 1, pfn(0), PAGE_SIZE, sgmax, 1 },
+		{ 0, 1, pfn(0), 1, sgmax, 1 },
+		{ 0, 2, pfn(0, 1), 2 * PAGE_SIZE, sgmax, 1 },
+		{ 0, 2, pfn(1, 0), 2 * PAGE_SIZE, sgmax, 2 },
+		{ 0, 3, pfn(0, 1, 2), 3 * PAGE_SIZE, sgmax, 1 },
+		{ 0, 3, pfn(0, 2, 1), 3 * PAGE_SIZE, sgmax, 3 },
+		{ 0, 3, pfn(0, 1, 3), 3 * PAGE_SIZE, sgmax, 2 },
+		{ 0, 3, pfn(1, 2, 4), 3 * PAGE_SIZE, sgmax, 2 },
+		{ 0, 3, pfn(1, 3, 4), 3 * PAGE_SIZE, sgmax, 2 },
+		{ 0, 4, pfn(0, 1, 3, 4), 4 * PAGE_SIZE, sgmax, 2 },
+		{ 0, 5, pfn(0, 1, 3, 4, 5), 5 * PAGE_SIZE, sgmax, 2 },
+		{ 0, 5, pfn(0, 1, 3, 4, 6), 5 * PAGE_SIZE, sgmax, 3 },
+		{ 0, 5, pfn(0, 1, 2, 3, 4), 5 * PAGE_SIZE, sgmax, 1 },
+		{ 0, 5, pfn(0, 1, 2, 3, 4), 5 * PAGE_SIZE, 2 * PAGE_SIZE, 3 },
+		{ 0, 6, pfn(0, 1, 2, 3, 4, 5), 6 * PAGE_SIZE, 2 * PAGE_SIZE, 3 },
+		{ 0, 6, pfn(0, 2, 3, 4, 5, 6), 6 * PAGE_SIZE, 2 * PAGE_SIZE, 4 },
+		{ 0, 6, pfn(0, 1, 3, 4, 5, 6), 6 * PAGE_SIZE, 2 * PAGE_SIZE, 3 },
+		{ 0, 0, NULL, 0, 0, 0 },
+	};
+	unsigned int i;
+
+	for (i = 0, test = tests; test->expected_segments; test++, i++) {
+		struct page *pages[MAX_PAGES];
+		struct sg_table st;
+		int ret;
+
+		set_pages(pages, test->pfn, test->num_pages);
+
+		ret = __sg_alloc_table_from_pages(&st, pages, test->num_pages,
+						  0, test->size, test->max_seg,
+						  GFP_KERNEL);
+		assert(ret == test->alloc_ret);
+
+		if (test->alloc_ret)
+			continue;
+
+		assert(st.nents == test->expected_segments);
+		assert(st.orig_nents == test->expected_segments);
+
+		sg_free_table(&st);
+	}
+
+	assert(i == (sizeof(tests) / sizeof(tests[0])) - 1);
+
+	return 0;
+}
-- 
2.9.5

[PATCH 0/5] Avoid pessimistic scatter-gather allocation

[Tvrtko Ursulin]

From: Tvrtko Ursulin <tvrtko.ursulin@intel.com>

We can decrease the i915 kernel memory usage by doing more sg list
coallescing and avoiding the pessimistic list allocation.

At the moment we got two places in our code, the main shmemfs backed
object allocator, and the userptr object allocator, which both can
allocate sg list size pessimistically, and in the latter case also do
not exploit entry coallescing when it is possible.

This results in between one to six megabytes of memory wasted on unused
sg list entries under some common workloads:

    * Logging into KDE there is 1-2 MiB of unused sg entries.
    * Running the T-Rex benchamrk aroun 3 Mib.
    * Similarly for Manhattan 5-6 MiB.

To remove this wastage this series starts with some cleanups in the
sg_alloc_table_from_pages implementation and then adds and exports a new
__sg_alloc_table_from_pages function.

This then gets used by the i915 driver to achieve the described savings.

Tvrtko Ursulin (5):
  lib/scatterlist: Fix offset type in sg_alloc_table_from_pages
  lib/scatterlist: Avoid potential scatterlist entry overflow
  lib/scatterlist: Introduce and export __sg_alloc_table_from_pages
  drm/i915: Use __sg_alloc_table_from_pages for allocating object
    backing store
  drm/i915: Use __sg_alloc_table_from_pages for userptr allocations

 drivers/gpu/drm/i915/i915_drv.h                |  9 +++
 drivers/gpu/drm/i915/i915_gem.c                | 77 +++++++++++--------------
 drivers/gpu/drm/i915/i915_gem_userptr.c        | 29 +++-------
 drivers/media/v4l2-core/videobuf2-dma-contig.c |  4 +-
 drivers/rapidio/devices/rio_mport_cdev.c       |  4 +-
 include/linux/scatterlist.h                    | 11 ++--
 lib/scatterlist.c                              | 78 ++++++++++++++++++++------
 7 files changed, 120 insertions(+), 92 deletions(-)

-- 
2.7.4

[PATCH 2/5] lib/scatterlist: Avoid potential scatterlist entry overflow

[Tvrtko Ursulin]

From: Tvrtko Ursulin <tvrtko.ursulin@intel.com>

Since the scatterlist length field is an unsigned int, make
sure that sg_alloc_table_from_pages does not overflow it while
coallescing pages to a single entry.

It is I think only a theoretical possibility at the moment,
but the ability to limit the coallesced size will have
another use in following patches.

Signed-off-by: Tvrtko Ursulin <tvrtko.ursulin@intel.com>
Cc: Masahiro Yamada <yamada.masahiro@socionext.com>
Cc: linux-kernel@vger.kernel.org
---
 lib/scatterlist.c | 25 +++++++++++++++++++------
 1 file changed, 19 insertions(+), 6 deletions(-)

diff --git a/lib/scatterlist.c b/lib/scatterlist.c
index e05e7fc98892..d928fa04aee3 100644
--- a/lib/scatterlist.c
+++ b/lib/scatterlist.c
@@ -394,7 +394,8 @@ int sg_alloc_table_from_pages(struct sg_table *sgt,
 	unsigned int offset, unsigned long size,
 	gfp_t gfp_mask)
 {
-	unsigned int chunks;
+	const unsigned int max_segment = ~0;
+	unsigned int seg_len, chunks;
 	unsigned int i;
 	unsigned int cur_page;
 	int ret;
@@ -402,9 +403,16 @@ int sg_alloc_table_from_pages(struct sg_table *sgt,
 
 	/* compute number of contiguous chunks */
 	chunks = 1;
-	for (i = 1; i < n_pages; ++i)
-		if (page_to_pfn(pages[i]) != page_to_pfn(pages[i - 1]) + 1)
+	seg_len = PAGE_SIZE;
+	for (i = 1; i < n_pages; ++i) {
+		if (seg_len >= max_segment ||
+		    page_to_pfn(pages[i]) != page_to_pfn(pages[i - 1]) + 1) {
 			++chunks;
+			seg_len = PAGE_SIZE;
+		} else {
+			seg_len += PAGE_SIZE;
+		}
+	}
 
 	ret = sg_alloc_table(sgt, chunks, gfp_mask);
 	if (unlikely(ret))
@@ -413,17 +421,22 @@ int sg_alloc_table_from_pages(struct sg_table *sgt,
 	/* merging chunks and putting them into the scatterlist */
 	cur_page = 0;
 	for_each_sg(sgt->sgl, s, sgt->orig_nents, i) {
-		unsigned long chunk_size;
+		unsigned int chunk_size;
 		unsigned int j;
 
 		/* look for the end of the current chunk */
+		seg_len = PAGE_SIZE;
 		for (j = cur_page + 1; j < n_pages; ++j)
-			if (page_to_pfn(pages[j]) !=
+			if (seg_len >= max_segment ||
+			    page_to_pfn(pages[j]) !=
 			    page_to_pfn(pages[j - 1]) + 1)
 				break;
+			else
+				seg_len += PAGE_SIZE;
 
 		chunk_size = ((j - cur_page) << PAGE_SHIFT) - offset;
-		sg_set_page(s, pages[cur_page], min(size, chunk_size), offset);
+		sg_set_page(s, pages[cur_page],
+			    min_t(unsigned long, size, chunk_size), offset);
 		size -= chunk_size;
 		offset = 0;
 		cur_page = j;
-- 
2.7.4