block: blk-merge: don't merge the pages with non-contiguous descriptors

blk_rq_map_sg() function merges the physically contiguous pages to use same scatter-gather node without checking if their page descriptors are contiguous or not.

Now when dma_map_sg() is called on the scatter gather list, it would take the base page pointer from each node (one by one) and iterates through all of the pages in same sg node by keep incrementing the base page pointer with the assumption that physically contiguous pages will have their page descriptor address contiguous which may not be true if SPARSEMEM config is enabled. So here we may end referring to invalid page descriptor.

Following table shows the example of physically contiguous pages but their page descriptor addresses non-contiguous.
-------------------------------------------
| Page Descriptor | Physical Address |
------------------------------------------

| 0xc1e43fdc         |   0xdffff000       |
| 0xc2052000         |   0xe0000000       |

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

With this patch, relevant blk-merge functions will also check if the physically contiguous pages are having page descriptors address contiguous or not? If not then, these pages are separated to be in different scatter-gather nodes.

Quoted 17 lines · Subhash Jadavani

blk_rq_map_sg() function merges the physically contiguous pages to use same scatter-gather node without checking if their page descriptors are contiguous or not.

Now when dma_map_sg() is called on the scatter gather list, it would take the base page pointer from each node (one by one) and iterates through all of the pages in same sg node by keep incrementing the base page pointer with the assumption that physically contiguous pages will have their page descriptor address contiguous which may not be true if SPARSEMEM config is enabled. So here we may end referring to invalid page descriptor.

Following table shows the example of physically contiguous pages but their page descriptor addresses non-contiguous.
-------------------------------------------
| Page Descriptor | Physical Address |
------------------------------------------

Quoted 8 lines

| 0xc1e43fdc         |   0xdffff000       |
| 0xc2052000         |   0xe0000000       |

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

With this patch, relevant blk-merge functions will also check if the physically contiguous pages are having page descriptors address contiguous or not? If not then, these pages are separated to be in different scatter-gather nodes.

How does this manifest as a bug?

The discontinuity is in struct page arrays, which hardware doesn't care about. All we need is to get from struct page to the physical address for programming the hardware, for which we use the sg_phys() inline function.

Even given we have a two page physical contiguity at 0xdffff000 in your example, the sg list entry contains a length of 8192 and a page_link of 0xc1e43fdc, which we transform to the correct physical address and length.

James

--
To unsubscribe from this list: send the line "unsubscribe linux-mmc" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 33 lines · James Bottomley

Quoted 17 lines · Subhash Jadavani

blk_rq_map_sg() function merges the physically contiguous pages to use same scatter-gather node without checking if their page descriptors are contiguous or not.

Now when dma_map_sg() is called on the scatter gather list, it would take the base page pointer from each node (one by one) and iterates through all of the pages in same sg node by keep incrementing the base page pointer with the assumption that physically contiguous pages will have their page descriptor address contiguous which may not be true if SPARSEMEM config is enabled. So here we may end referring to invalid page descriptor.

Following table shows the example of physically contiguous pages but their page descriptor addresses non-contiguous.
-------------------------------------------
| Page Descriptor | Physical Address |
------------------------------------------

Quoted 8 lines

| 0xc1e43fdc         |   0xdffff000       |
| 0xc2052000         |   0xe0000000       |

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

With this patch, relevant blk-merge functions will also check if the physically contiguous pages are having page descriptors address contiguous or not? If not then, these pages are separated to be in different scatter-gather nodes.

How does this manifest as a bug?

The discontinuity is in struct page arrays, which hardware doesn't care about. All we need is to get from struct page to the physical address for programming the hardware, for which we use the sg_phys() inline function.

Quoted 4 lines

Even given we have a two page physical contiguity at 0xdffff000 in your example, the sg list entry contains a length of 8192 and a page_link of 0xc1e43fdc, which we transform to the correct physical address and length.

Thanks James for looking at this patch.

Let's assume this scenario.
PAGE_SIZE = 4096 (4K),
2 page descriptors (as mentioned commit text) whose own addresses are discontingous but they point to physically contiguous memory space, sizeof(struct page) is 36 bytes.
Only one SG node created in Scatter Gather list (by blk_rq_map_sg) with this node's page_link=0xc1e43fdc, length=8192, offset=0

Now consider this call stack from MMC block driver (this is on the ARmv7 based board):

     [   98.918174] [<c001b50c>] (v7_dma_inv_range+0x30/0x48) from 
[<c0017b8c>] (dma_cache_maint_page+0x1c4/0x24c)
     [   98.927819] [<c0017b8c>] (dma_cache_maint_page+0x1c4/0x24c) from 
[<c0017c28>] (___dma_page_cpu_to_dev+0x14/0x1c)
     [   98.937982] [<c0017c28>] (___dma_page_cpu_to_dev+0x14/0x1c) from 
[<c0017ff8>] (dma_map_sg+0x3c/0x114)
     [   98.947169] [<c0017ff8>] (dma_map_sg+0x3c/0x114) from 
[<c0532c40>] (msmsdcc_prep_xfer+0x50/0x10c)
     [   98.956020] [<c0532c40>] (msmsdcc_prep_xfer+0x50/0x10c) from 
[<c0539664>] (msmsdcc_pre_req+0x78/0x98)
     [   98.965237] [<c0539664>] (msmsdcc_pre_req+0x78/0x98) from 
[<c0521d98>] (mmc_start_req+0x4c/0x1c4)
     [   98.974088] [<c0521d98>] (mmc_start_req+0x4c/0x1c4) from 
[<c052faa0>] (mmc_blk_issue_rw_rq+0x3a0/0x84c)
     [   98.983457] [<c052faa0>] (mmc_blk_issue_rw_rq+0x3a0/0x84c) from 
[<c05304b4>] (mmc_blk_issue_rq+0x568/0x5c4)
     [   98.993193] [<c05304b4>] (mmc_blk_issue_rq+0x568/0x5c4) from 
[<c0530718>] (mmc_queue_thread+0xb4/0x120)
     [   99.002563] [<c0530718>] (mmc_queue_thread+0xb4/0x120) from 
[<c0096400>] (kthread+0x80/0x8c)
     [   99.010987] [<c0096400>] (kthread+0x80/0x8c) from [<c000f028>] 

(kernel_thread_exit+0x0/0x8)

dma_cache_maint_page() function iterates through each page in single sg node, maps it to virtual space and then call the cache maintainance operation on that page.

With above scenario, first page descriptor would be 0xc1e43fdc, which would be mapped virtual address by either kmap() (if it's higmem page) or by page_address() (if it's low mem page).

Now as the size of the sg node is 8192 bytes, dma_cache_maint_page() function increments the page pointer (pointed by page_link of sg node) to get to the next descriptor. page++ would yield page descriptor address = 0xc1e44000 (0xc1e43fdc + sizeof (struct page)). 0xc1e44000 is not pointing any real page descriptor so when calls page_address(0xc1e44000) to get virtual address of the page, it returns invalid virtual address. Now when we try to dereference that invalid virtual address in cache maintainance functions, it would result into "Unable to handle kernel paging request at virtual address xxxxxxxx" error and kernel crashes.

Now consider this call stack from MMC block driver (this is on the ARmv7 based board):

     [   98.918174] [<c001b50c>] (v7_dma_inv_range+0x30/0x48) from 
[<c0017b8c>] (dma_cache_maint_page+0x1c4/0x24c)
     [   98.927819] [<c0017b8c>] (dma_cache_maint_page+0x1c4/0x24c) from 
[<c0017c28>] (___dma_page_cpu_to_dev+0x14/0x1c)
     [   98.937982] [<c0017c28>] (___dma_page_cpu_to_dev+0x14/0x1c) from 

[<c0017ff8>] (dma_map_sg+0x3c/0x114)

Quoted 8 lines · Subhash Jadavani

Now consider this call stack from MMC block driver (this is on the ARmv7 based board):

      [   98.918174] [<c001b50c>] (v7_dma_inv_range+0x30/0x48) from
[<c0017b8c>] (dma_cache_maint_page+0x1c4/0x24c)
      [   98.927819] [<c0017b8c>] (dma_cache_maint_page+0x1c4/0x24c) from
[<c0017c28>] (___dma_page_cpu_to_dev+0x14/0x1c)
      [   98.937982] [<c0017c28>] (___dma_page_cpu_to_dev+0x14/0x1c) from

[<c0017ff8>] (dma_map_sg+0x3c/0x114)

OK, so this is showing that ARM itself is making the assumption that the pages are contiguous in the page offset map.

Fix this by doing the increment via the pfn, which will do the right thing whatever the memory model.

Signed-off-by James Bottomley <[email protected]>

---

arch/arm/mm/dma-mapping.c +1 -2

index 6b2fb87..ab88c5b 100644
@@ -809,7 +809,7 @@ static void dma_cache_maint_page(struct page *page, unsigned long offset,
  			op(vaddr, len, dir);
  		}
  		offset = 0;
-		page++;
+		page = pfn_to_page(page_to_pfn(page) + 1);
  		left -= len;
  	} while (left);
  }
 
 
--

To unsubscribe from this list: send the line "unsubscribe linux-scsi" in the body of a message to majordomo at vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 8 lines · Subhash Jadavani

Now consider this call stack from MMC block driver (this is on the ARmv7 based board):

      [   98.918174] [<c001b50c>] (v7_dma_inv_range+0x30/0x48) from
[<c0017b8c>] (dma_cache_maint_page+0x1c4/0x24c)
      [   98.927819] [<c0017b8c>] (dma_cache_maint_page+0x1c4/0x24c) from
[<c0017c28>] (___dma_page_cpu_to_dev+0x14/0x1c)
      [   98.937982] [<c0017c28>] (___dma_page_cpu_to_dev+0x14/0x1c) from

[<c0017ff8>] (dma_map_sg+0x3c/0x114)

OK, so this is showing that ARM itself is making the assumption that the pages are contiguous in the page offset map.

Fix this by doing the increment via the pfn, which will do the right thing whatever the memory model.

Signed-off-by James Bottomley <[email protected]>

---

arch/arm/mm/dma-mapping.c +1 -2

index 6b2fb87..ab88c5b 100644
@@ -809,7 +809,7 @@ static void dma_cache_maint_page(struct page *page, unsigned long offset,
  			op(vaddr, len, dir);
  		}
  		offset = 0;
-		page++;
+		page = pfn_to_page(page_to_pfn(page) + 1);
  		left -= len;
  	} while (left);
  }
 
 
--

To unsubscribe from this list: send the line "unsubscribe linux-scsi" in the body of a message to majordomo at vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html

Is it possible to pick up James patch below? Thread here:
http://comments.gmane.org/gmane.linux.kernel.mmc/18670, have the details on the motivation behind this fix.

Quoted 3 lines · Subhash Jadavani

Is it possible to pick up James patch below? Thread here:
http://comments.gmane.org/gmane.linux.kernel.mmc/18670, have the details on the motivation behind this fix.

Someone should also audit the arm kernel code for more of these linear page array assumptions. I'm guessing that when sparsemem was added to arm over a year ago, whoever did it either didn't audit or missed a few.

Quoted 5 lines · James Bottomley

Quoted 3 lines · Subhash Jadavani

Is it possible to pick up James patch below? Thread here:
http://comments.gmane.org/gmane.linux.kernel.mmc/18670, have the details on the motivation behind this fix.

Quoted 3 lines

Someone should also audit the arm kernel code for more of these linear page array assumptions. I'm guessing that when sparsemem was added to arm over a year ago, whoever did it either didn't audit or missed a few.

No, that's a bad assumption. We've had discontigmem for years - maybe something like 12 years.

I switched everything over to sparsemem, and
sparsemem has been used on ARM for years too:

commit 05944d74bc28fffbcce159cb915d0acff82f30a1
Author: Russell King <[email protected]>
Date: Thu Nov 30 20:43:51 2006 +0000

[ARM] Add initial sparsemem support

Signed-off-by Russell King <[email protected]>

However, there's a big problem with this: very few of the lead people have machines which suffer from this disability, so there's very little testing of it - and there's very little testing of new code with it.

The patch which originally introduced this code which your patch touches was part of adding highmem support to ARM:

commit 43377453af83b8ff8c1c731da1508bd6b84ebfea
Author: Nicolas Pitre <[email protected]>
Date: Thu Mar 12 22:52:09 2009 -0400

[ARM] introduce dma_cache_maint_page()

This is a helper to be used by the DMA mapping API to handle cache maintenance for memory identified by a page structure instead of a virtual address. Those pages may or may not be highmem pages, and when they're highmem pages, they may or may not be virtually mapped. When they're not mapped then there is no L1 cache to worry about. But even in that case the L2 cache must be processed since unmapped highmem pages can still be L2 cached.

Signed-off-by Nicolas Pitre <[email protected]>

some three years later, and has been through a number of revisions since.

I'd really like to get rid of sparsemem so it's one less failure case, but alas there's a relatively small bunch of folk who rely upon it. That means it's always going to be more buggy.

Quoted 8 lines · Subhash Jadavani

Now consider this call stack from MMC block driver (this is on the ARmv7 based board):

     [   98.918174] [<c001b50c>] (v7_dma_inv_range+0x30/0x48) from 
[<c0017b8c>] (dma_cache_maint_page+0x1c4/0x24c)
     [   98.927819] [<c0017b8c>] (dma_cache_maint_page+0x1c4/0x24c) from 
[<c0017c28>] (___dma_page_cpu_to_dev+0x14/0x1c)
     [   98.937982] [<c0017c28>] (___dma_page_cpu_to_dev+0x14/0x1c) from 

[<c0017ff8>] (dma_map_sg+0x3c/0x114)

OK, so this is showing that ARM itself is making the assumption that the pages are contiguous in the page offset map.

Fix this by doing the increment via the pfn, which will do the right thing whatever the memory model.

Signed-off-by James Bottomley <[email protected]>

---

arch/arm/mm/dma-mapping.c +1 -1

index 6b2fb87..ab88c5b 100644
@@ -809,7 +809,7 @@ static void dma_cache_maint_page(struct page *page, unsigned long offset,
 			op(vaddr, len, dir);
 		}
 		offset = 0;
-		page++;
+		page = pfn_to_page(page_to_pfn(page) + 1);
 		left -= len;
 	} while (left);
 }

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel at lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Quoted 14 lines · James Bottomley

Quoted 8 lines · Subhash Jadavani

Now consider this call stack from MMC block driver (this is on the ARmv7 based board):

     [   98.918174] [<c001b50c>] (v7_dma_inv_range+0x30/0x48) from 
[<c0017b8c>] (dma_cache_maint_page+0x1c4/0x24c)
     [   98.927819] [<c0017b8c>] (dma_cache_maint_page+0x1c4/0x24c) from 
[<c0017c28>] (___dma_page_cpu_to_dev+0x14/0x1c)
     [   98.937982] [<c0017c28>] (___dma_page_cpu_to_dev+0x14/0x1c) from 

[<c0017ff8>] (dma_map_sg+0x3c/0x114)

OK, so this is showing that ARM itself is making the assumption that the pages are contiguous in the page offset map.

Quoted 4 lines

Fix this by doing the increment via the pfn, which will do the right thing whatever the memory model.

Signed-off-by James Bottomley <[email protected]>

Ok. What would you like the patch summary line for this to be - the existing one seems to be a little wrong given the content of this patch...

Quoted 19 lines

---

arch/arm/mm/dma-mapping.c +1 -1

index 6b2fb87..ab88c5b 100644
@@ -809,7 +809,7 @@ static void dma_cache_maint_page(struct page *page, unsigned long offset,
 			op(vaddr, len, dir);
 		}
 		offset = 0;
-		page++;
+		page = pfn_to_page(page_to_pfn(page) + 1);
 		left -= len;
 	} while (left);
 }

Quoted 4 lines

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel at lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

--
To unsubscribe from this list: send the line "unsubscribe linux-scsi" in the body of a message to majordomo at vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html

arch/arm/mm/dma-mapping.c static void dma_cache_maint_page(struct page *page, unsigned long offset, · line 812

Quoted 10 lines · James Bottomley

arch/arm/mm/dma-mapping.c +1 -1

index 6b2fb87..ab88c5b 100644
@@ -809,7 +809,7 @@ static void dma_cache_maint_page(struct page *page, unsigned long offset,
 			op(vaddr, len, dir);
 		}
 		offset = 0;
-		page++;
+		page = pfn_to_page(page_to_pfn(page) + 1);

Probably page = nth_page(page, 1) is the better form.

Quoted 13 lines · Tejun Heo

arch/arm/mm/dma-mapping.c static void dma_cache_maint_page(struct page *page, unsigned long offset, · line 812

Quoted 10 lines · James Bottomley

arch/arm/mm/dma-mapping.c +1 -1

index 6b2fb87..ab88c5b 100644
@@ -809,7 +809,7 @@ static void dma_cache_maint_page(struct page *page, unsigned long offset,
 			op(vaddr, len, dir);
 		}
 		offset = 0;
-		page++;
+		page = pfn_to_page(page_to_pfn(page) + 1);

Probably page = nth_page(page, 1) is the better form.

It's the same thing.

I'd actually prefer page = pfn_to_page(page_to_pfn(page) + 1); because it makes the code look like the hack it is. The preferred form for all iterators like this should be to iterate over the pfn instead of a pointer into the page arrays, because that will always work correctly no matter how many weird and wonderful memory schemes we come up with.

Quoted 5 lines · James Bottomley

I'd actually prefer page = pfn_to_page(page_to_pfn(page) + 1); because it makes the code look like the hack it is. The preferred form for all iterators like this should be to iterate over the pfn instead of a pointer into the page arrays, because that will always work correctly no matter how many weird and wonderful memory schemes we come up with.

So, why don't we update the code to do that then?

Quoted 8 lines · Russell King - ARM Linux

Quoted 5 lines · James Bottomley

I'd actually prefer page = pfn_to_page(page_to_pfn(page) + 1); because it makes the code look like the hack it is. The preferred form for all iterators like this should be to iterate over the pfn instead of a pointer into the page arrays, because that will always work correctly no matter how many weird and wonderful memory schemes we come up with.

So, why don't we update the code to do that then?

Also, couldn't the addition of the scatterlist offset to the page also be buggy too?

So, what about this patch which addresses both additions by keeping our iterator as a pfn as you suggest. It also simplifies some of the code in the loop too.

Can the original folk with the problem test this patch?

 arch/arm/mm/dma-mapping.c |   18 ++++++++++--------
 1 files changed, 10 insertions(+), 8 deletions(-)

arch/arm/mm/dma-mapping.c +9 -7

index 6b2fb87..076c26d 100644
@@ -774,25 +774,27 @@ static void dma_cache_maint_page(struct page *page, unsigned long offset,
 	size_t size, enum dma_data_direction dir,
 	void (*op)(const void *, size_t, int))
 {
+	unsigned long pfn;
+	size_t left = size;
+
+	pfn = page_to_pfn(page) + offset / PAGE_SIZE;
+	offset %= PAGE_SIZE;
+
 	/*
 	 * A single sg entry may refer to multiple physically contiguous
 	 * pages.  But we still need to process highmem pages individually.
 	 * If highmem is not configured then the bulk of this loop gets
 	 * optimized out.
 	 */
-	size_t left = size;
 	do {
 		size_t len = left;
 		void *vaddr;
 
+		page = pfn_to_page(pfn);
+
 		if (PageHighMem(page)) {
-			if (len + offset > PAGE_SIZE) {
-				if (offset >= PAGE_SIZE) {
-					page += offset / PAGE_SIZE;
-					offset %= PAGE_SIZE;
-				}
+			if (len + offset > PAGE_SIZE)
 				len = PAGE_SIZE - offset;
-			}
 			vaddr = kmap_high_get(page);
 			if (vaddr) {
 				vaddr += offset;

Quoted 2 lines · Russell King - ARM Linux

Also, couldn't the addition of the scatterlist offset to the page also be buggy too?

No, fortunately, offset must be within the first page from the point of view of block generated sg lists. As long as nothing within arm violates this, it should be a safe assumption ... although the code seems to assume otherwise.

Quoted 8 lines · James Bottomley

Quoted 2 lines · Russell King - ARM Linux

Also, couldn't the addition of the scatterlist offset to the page also be buggy too?

No, fortunately, offset must be within the first page from the point of view of block generated sg lists. As long as nothing within arm violates this, it should be a safe assumption ... although the code seems to assume otherwise.

Are you absolutely sure about that? I believe I have seen cases where that has been violated in the past, though it was many years ago.

From the point of view of the block layer, absolutely: the scatterlist

From the point of view of other arm stuff, I don't know.

Quoted 10 lines · Russell King - ARM Linux

Quoted 8 lines · James Bottomley

Quoted 2 lines · Russell King - ARM Linux

Also, couldn't the addition of the scatterlist offset to the page also be buggy too?

No, fortunately, offset must be within the first page from the point of view of block generated sg lists. As long as nothing within arm violates this, it should be a safe assumption ... although the code seems to assume otherwise.

Quoted 4 lines

Are you absolutely sure about that? I believe I have seen cases where that has been violated in the past, though it was many years ago.

From the point of view of the block layer, absolutely: the scatterlist

is generated from an array of bio_vecs. Each bio_vec is a page, offset and length element and obeys the rule that offset must be within the page and offset + length cannot stray over the page.

Quoted 1 line

From the point of view of other arm stuff, I don't know.

Quoted 7 lines · Russell King - ARM Linux

Quoted 5 lines · James Bottomley

I'd actually prefer page = pfn_to_page(page_to_pfn(page) + 1); because it makes the code look like the hack it is. The preferred form for all iterators like this should be to iterate over the pfn instead of a pointer into the page arrays, because that will always work correctly no matter how many weird and wonderful memory schemes we come up with.

So, why don't we update the code to do that then?

Also, couldn't the addition of the scatterlist offset to the page also be buggy too?

So, what about this patch which addresses both additions by keeping our iterator as a pfn as you suggest. It also simplifies some of the code in the loop too.

Can the original folk with the problem test this patch?

  arch/arm/mm/dma-mapping.c |   18 ++++++++++--------
  1 files changed, 10 insertions(+), 8 deletions(-)

arch/arm/mm/dma-mapping.c +10 -9

index 6b2fb87..076c26d 100644
@@ -774,25 +774,27 @@ static void dma_cache_maint_page(struct page *page, unsigned long offset,
  	size_t size, enum dma_data_direction dir,
  	void (*op)(const void *, size_t, int))
  {
+	unsigned long pfn;
+	size_t left = size;
+
+	pfn = page_to_pfn(page) + offset / PAGE_SIZE;
+	offset %= PAGE_SIZE;
+
  	/*
  	 * A single sg entry may refer to multiple physically contiguous
  	 * pages.  But we still need to process highmem pages individually.
  	 * If highmem is not configured then the bulk of this loop gets
  	 * optimized out.
  	 */
-	size_t left = size;
  	do {
  		size_t len = left;
  		void *vaddr;
 
+		page = pfn_to_page(pfn);
+
  		if (PageHighMem(page)) {
-			if (len + offset > PAGE_SIZE) {
-				if (offset >= PAGE_SIZE) {
-					page += offset / PAGE_SIZE;
-					offset %= PAGE_SIZE;
-				}
+			if (len + offset > PAGE_SIZE)
  				len = PAGE_SIZE - offset;
-			}
  			vaddr = kmap_high_get(page);
  			if (vaddr) {
  				vaddr += offset;

@@ -809,7 +811,7 @@ static void dma_cache_maint_page(struct page *page, unsigned long offset,
  			op(vaddr, len, dir);
  		}
  		offset = 0;
-		page++;
+		pfn++;
  		left -= len;
  	} while (left);
  }
 
--

To unsubscribe from this list: send the line "unsubscribe linux-scsi" in the body of a message to majordomo at vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html