use memmove() when copying to/from user page

It's possible that calling sendfile() to copy the data from a memfd to itself may result in doing a memcpy() with overlapping arguments. To avoid undefined behavior here, replace memcpy() with memmove() and rename memcpy_to_page()/memcpy_from_page() accordingly.

This problem has been detected with KMSAN and syzkaller.

---
For the record, the following program:
===================================
// autogenerated by syzkaller (http://github.com/google/syzkaller)

  #ifndef __NR_memfd_create
  #define __NR_memfd_create 319
  #endif

  #include <sys/mman.h>
  #include <sys/time.h>
  #include <sys/types.h>
  #include <sys/wait.h>

  #include <pthread.h>
  #include <stdint.h>
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  #include <unistd.h>

  static uint64_t current_time_ms()
  {
    struct timespec ts;
    if (clock_gettime(CLOCK_MONOTONIC, &ts)) _exit(1);
    return (uint64_t)ts.tv_sec * 1000 + (uint64_t)ts.tv_nsec / 1000000;
  }

int fd;
void *page;

  void* thr(void* arg)
  {
    sendfile(fd, fd, page, 0xfec);
    return 0;
  }

  void test()
  {
    int i;
    pthread_t th[2];

    page = mmap(0x20000000, 0x1000, 0x3, 0x32, -1, 0);
    char buf[1] = "\0";
    fd = syscall(__NR_memfd_create, buf, 0);
    write(fd, buf, 1);

    for (i = 0; i < 2; i++) {
      pthread_create(&th[i], 0, thr, NULL);
      usleep(10000);
    }
    usleep(100000);

}

int main()

  {
    int iter;
    for (iter = 0; iter < 10; iter++) {
      int pid = fork();
      if (pid < 0)
        _exit(1);
      if (pid == 0) {
        test();
        _exit(0);
      }
      int status = 0;
      uint64_t start = current_time_ms();
      for (;;) {
        int res;
        if (current_time_ms() - start > 5 * 1000) {
          kill(-pid, SIGKILL);
          kill(pid, SIGKILL);
          while (waitpid(-1, &status, __WALL) != pid) {
          }
          return 0;
        }
        usleep(1000);
      }
    }
    return 0;

}
===================================

triggers calls to memcpy() with overlapping arguments:

==================================================================

BUG: memcpy-param-overlap in generic_perform_write+0x551/0xa20
__msan_memcpy(ffff88013c6e3001, ffff88013c6e3000, 105)
CPU: 0 PID: 1040 Comm: probe Not tainted 4.11.0-rc5+ #2562
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Bochs 01/01/2011
Call Trace:
 __dump_stack lib/dump_stack.c:16
 dump_stack+0x143/0x1b0 lib/dump_stack.c:52
 __msan_memcpy+0x91/0x1e0 mm/kmsan/kmsan_instr.c:359
 memcpy_from_page lib/iov_iter.c:433
 iov_iter_copy_from_user_atomic+0x98e/0x1320 lib/iov_iter.c:721
 generic_perform_write+0x551/0xa20 mm/filemap.c:2843
 __generic_file_write_iter+0x3fa/0x8f0 mm/filemap.c:2960
 generic_file_write_iter+0x705/0xa80 mm/filemap.c:2988
 call_write_iter ./include/linux/fs.h:1733
 vfs_iter_write+0x481/0x580 fs/read_write.c:391
 iter_file_splice_write+0xa87/0x12f0 fs/splice.c:771
 do_splice_from fs/splice.c:873
 direct_splice_actor+0x1ae/0x210 fs/splice.c:1040
 splice_direct_to_actor+0x683/0xd40 fs/splice.c:995
 do_splice_direct+0x327/0x430 fs/splice.c:1083
 do_sendfile+0x8a3/0x12e0 fs/read_write.c:1379
 SYSC_sendfile64+0x1ab/0x2b0 fs/read_write.c:1434
 SyS_sendfile64+0x9a/0xc0 fs/read_write.c:1426
 do_syscall_64+0x72/0xa0 arch/x86/entry/common.c:285
 entry_SYSCALL64_slow_path+0x25/0x25 arch/x86/entry/entry_64.S:246
RIP: 0033:0x43f4da
RSP: 002b:00007f1f1bba4db8 EFLAGS: 00000206 ORIG_RAX: 0000000000000028
RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 000000000043f4da
RDX: 0000000020000000 RSI: 0000000000000003 RDI: 0000000000000003
RBP: 00007f1f1bba4dd0 R08: 00007f1f1bba5700 R09: 00007f1f1bba5700
R10: 0000000000000fec R11: 0000000000000206 R12: 0000000000000000
R13: 0000000000000000 R14: 00007f1f1bba59c0 R15: 00007f1f1bba5700
==================================================================

---
 lib/iov_iter.c | 36 +++++++++++++++++++-----------------
 1 file changed, 19 insertions(+), 17 deletions(-)

index f835964c9485..097a8820e930 100644
@@ -427,17 +427,19 @@ void iov_iter_init(struct iov_iter *i, int direction,
 }
 EXPORT_SYMBOL(iov_iter_init);
 
-static void memcpy_from_page(char *to, struct page *page, size_t offset, size_t len)
+static void memmove_from_page(char *to, struct page *page, size_t offset,
+			      size_t len)
 {
 	char *from = kmap_atomic(page);
-	memcpy(to, from + offset, len);
+	memmove(to, from + offset, len);
 	kunmap_atomic(from);
 }
 
-static void memcpy_to_page(struct page *page, size_t offset, const char *from, size_t len)
+static void memmove_to_page(struct page *page, size_t offset, const char *from,
+			    size_t len)
 {
 	char *to = kmap_atomic(page);
-	memcpy(to + offset, from, len);
+	memmove(to + offset, from, len);
 	kunmap_atomic(to);
 }
 

@@ -525,7 +527,7 @@ static size_t copy_pipe_to_iter(const void *addr, size_t bytes,
 		return 0;
 	for ( ; n; idx = next_idx(idx, pipe), off = 0) {
 		size_t chunk = min_t(size_t, n, PAGE_SIZE - off);
-		memcpy_to_page(pipe->bufs[idx].page, off, addr, chunk);
+		memmove_to_page(pipe->bufs[idx].page, off, addr, chunk);
 		i->idx = idx;
 		i->iov_offset = off + chunk;
 		n -= chunk;

@@ -543,8 +545,8 @@ size_t copy_to_iter(const void *addr, size_t bytes, struct iov_iter *i)
 	iterate_and_advance(i, bytes, v,
 		__copy_to_user(v.iov_base, (from += v.iov_len) - v.iov_len,
 			       v.iov_len),
-		memcpy_to_page(v.bv_page, v.bv_offset,
-			       (from += v.bv_len) - v.bv_len, v.bv_len),
+		memmove_to_page(v.bv_page, v.bv_offset,
+				(from += v.bv_len) - v.bv_len, v.bv_len),
 		memcpy(v.iov_base, (from += v.iov_len) - v.iov_len, v.iov_len)
 	)
 

@@ -562,8 +564,8 @@ size_t copy_from_iter(void *addr, size_t bytes, struct iov_iter *i)
 	iterate_and_advance(i, bytes, v,
 		__copy_from_user((to += v.iov_len) - v.iov_len, v.iov_base,
 				 v.iov_len),
-		memcpy_from_page((to += v.bv_len) - v.bv_len, v.bv_page,
-				 v.bv_offset, v.bv_len),
+		memmove_from_page((to += v.bv_len) - v.bv_len, v.bv_page,
+				  v.bv_offset, v.bv_len),
 		memcpy((to += v.iov_len) - v.iov_len, v.iov_base, v.iov_len)
 	)
 

@@ -586,8 +588,8 @@ bool copy_from_iter_full(void *addr, size_t bytes, struct iov_iter *i)
 				      v.iov_base, v.iov_len))
 			return false;
 		0;}),
-		memcpy_from_page((to += v.bv_len) - v.bv_len, v.bv_page,
-				 v.bv_offset, v.bv_len),
+		memmove_from_page((to += v.bv_len) - v.bv_len, v.bv_page,
+				  v.bv_offset, v.bv_len),
 		memcpy((to += v.iov_len) - v.iov_len, v.iov_base, v.iov_len)
 	)
 

@@ -606,8 +608,8 @@ size_t copy_from_iter_nocache(void *addr, size_t bytes, struct iov_iter *i)
 	iterate_and_advance(i, bytes, v,
 		__copy_from_user_inatomic_nocache((to += v.iov_len) - v.iov_len,
 					 v.iov_base, v.iov_len),
-		memcpy_from_page((to += v.bv_len) - v.bv_len, v.bv_page,
-				 v.bv_offset, v.bv_len),
+		memmove_from_page((to += v.bv_len) - v.bv_len, v.bv_page,
+				  v.bv_offset, v.bv_len),
 		memcpy((to += v.iov_len) - v.iov_len, v.iov_base, v.iov_len)
 	)
 

@@ -629,8 +631,8 @@ bool copy_from_iter_full_nocache(void *addr, size_t bytes, struct iov_iter *i)
 					     v.iov_base, v.iov_len))
 			return false;
 		0;}),
-		memcpy_from_page((to += v.bv_len) - v.bv_len, v.bv_page,
-				 v.bv_offset, v.bv_len),
+		memmove_from_page((to += v.bv_len) - v.bv_len, v.bv_page,
+				  v.bv_offset, v.bv_len),
 		memcpy((to += v.iov_len) - v.iov_len, v.iov_base, v.iov_len)
 	)
 

@@ -721,8 +723,8 @@ size_t iov_iter_copy_from_user_atomic(struct page *page,
 	iterate_all_kinds(i, bytes, v,
 		__copy_from_user_inatomic((p += v.iov_len) - v.iov_len,
 					  v.iov_base, v.iov_len),
-		memcpy_from_page((p += v.bv_len) - v.bv_len, v.bv_page,
-				 v.bv_offset, v.bv_len),
+		memmove_from_page((p += v.bv_len) - v.bv_len, v.bv_page,
+				  v.bv_offset, v.bv_len),
 		memcpy((p += v.iov_len) - v.iov_len, v.iov_base, v.iov_len)
 	)
 	kunmap_atomic(kaddr);

2.13.0.303.g4ebf302169-goog

Er... And what semantics would you assign to such sendfile()? I really want to see details, because it sounds like memmove() here will not be any more useful than memcpy() - you still can esily get odd behaviour.

What odd behavior can we get with memmove?

Case that I am thinking of is when you want to delete part of the file in the middle. To do that you move tail of the file and then truncate. Memmove will do the intended thing. While memcpy can lost of data and duplicate another.

Oh, lovely. While we are trading idiotic use cases - what about inserting something in the middle of a file? No? Why is it any different?

There are two sides to it:
* real nasal demons resulting from that memcpy() with overlapping
source and destination - as in, "it not only trashed the page contents, it has led to memory corruption/leaked data/etc". Any such would be a real problem.
* behaviour of sendfile() in such a case. And there I've no problem
with saying "contents after operation is undefined". If you wish to change that, by all means start with documenting the semantics you want to promise to userland.

I never used this. But moving a part of file does not look completely idiotic. What do you mean about inserting into the middle? How is it related?

Let's put this aside.

I would say it's already documented.
sendfile says that it "copies data". memmove says that it "copies data". memcpy says that it "copies data, but data must not overlap". sendfile does not say that "data must not overlap".

But in the end I don't understand why you are so opposed to this change. Arguing about saving a single branch can make sense on the very low level. When if we are talking about syscalls and syscall semantics, a single branch does not matter while providing higher quality of implementation and following the principle of least surprise does matter.
Let's imagine we have memmove there now, would you argue strongly that we need to change it to memcpy?

In that case your patch does not suffice. Overlapping move _forwards_ still yields unexpected results, doesn't it? I'm all for documenting that resulting contents is undefined in case of overlap. The same goes for write() from mmap'ed area, BTW. You suggest changing that undefined behaviour *and* either pretending that it's not undefined anymore (obviously false) or failing to describe the new cases when it is not undefined anymore.

It's not the cost of extra branch; it's ill-defined rules that would need to be followed to be able to rely upon the "improvement".

Why? memmove can move both ways. Do we need to change more memcpy's to memmove's?

Why is it false?

I would say it just fixes a bug in current impl. Sendfile docs always said "sendfile() copies data" (without any but's), but we failed to do this.

Because it's not going to be *one* call of memcpy() or memmove(). It's one per page.

I missed that.

I assumed that in the case of sendfile from memfd to memfd data will be copied directly. But it goes through a pipe with multiple buffers. Does not look easily fixable.

Which leaves us only with "will nasal demons really fly there?".

Note, BTW, that memmove() warranties in libc (and in kernel) are somewhat weaker than what C99 promises - if the same page is mmapped at two addresses, memmove() between the pointers in those area does not guarantee what 7.21.2.2 says ("Copying takes place as if the n characters from the object pointed to by s2 are first copied into a temporary array of n characters that does not overlap the objects pointed to by s1 and s2, and then the n characters from the temporary array are copied into the object pointed to by s1"). It's out of scope for C99, but SUS has memmove() definition not only copying that from C99, but explicitly deferring to it and saying that any differences are unintentional. And mmap() *is* within the scope of SUS. There's no practical way to get C99-compliant behaviour when such aliases are possible, of course - nothing short of bounce buffers will do. The thing is, we can't assume their absense - the copying requested in copy_to_iter/copy_from_iter can bloody well be between different virtual addresses of the same page. Including the case when one of the aliases is in kernel space and another - in userland. IOW, copy_from_user() and its ilk really can have overlaps between source and destination. When called by read() and write().

Consider the case of write() from an mmapped piece of file to overlapping piece of the same file. It is possible and not hard to trigger; all we can guarantee is the lack of infoleaks, filesystem corruption or memory corruption. File *contents* in the affected area can't be sanely relied upon.

This case is not different. BTW, neither SUS, nor our manpages for write(2) mention these issues with mmap()-created aliases between the source and destination.

Hi!

It seems so:

Date: Tue, 16 May 2017 14:27:34 +0200
From: Alexander Potapenko <[email protected]>
Subject: [PATCH] [iov_iter] use memmove() when copying to/from user page

BUG: memcpy-param-overlap in generic_perform_write+0x551/0xa20
__msan_memcpy(ffff88013c6e3001, ffff88013c6e3000, 105)
CPU: 0 PID: 1040 Comm: probe Not tainted 4.11.0-rc5+ #2562
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Bochs

01/01/2011

At the very least, we do not want userland to trigger kernel BUG()s... so this needs fixes beyond documentation.

Added people doing documentation; seems like we have some updates to do there, too.
Pavel

(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

To be fair, this BUG() only happens because Alexander added one in memcpy() , testing for the cases where memmove() should have been used.

Kind of a debugging trap if you prefer.

This is not something that a pristine kernel would do.

Aha, so BUG() is not realy a problem. Problem is that memcpy() may not be called on overlapping regions, and may do something stupid; but we don't have evidence that it does.

Pavel

(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

Sure. Which is to say, the instrumentation that throws such BUG() is broken and needs to be fixed.

This is bullshit; the _only_ value memmove() would have here is "doesn't yield false positives from fuck knows what out-of-tree patches".

It does not make overlapping sendfile() work reliably (while creating an impression that it just might, as we'd seen in this thread). It does not do anything to kernel-vs-userland aliasing either - copy_from_user() is definitely memcpy()-like, not memmove()-like. Not that memmove() worked in situations when source and destination point to the same memory object seen at two virtial addresses...

BTW, the last part goes both for kernel and for userland:

#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>

void f(char *p, char *q)

{
	memset(p, 0, 4096);
	p[254] = 1;
        memmove(q, p + 127, 256);
        memmove(p, q + 127, 256);
	printf("%d\n", p[0]);
}

main()

{
        static char p[4096];
        int fd = creat("/tmp/foo", 0600);
        unsigned char *p1, *p2;
        int i;

        write(fd, p, 4096);
        close(fd);
        fd = open("/tmp/foo", O_RDWR);
        p1 = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
        p2 = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);

	f(p1, p1);
	f(p1, p2);
	f(p2, p1);
}

should've printed 1 three times, according to C99/SuS. On stretch/amd64 (with 2.24-10 glibc) we get
1
1
0
instead. mmap() is out of scope for C99, of course, but not for SuS. And SuS treatment of memmove() is:

[CX] [Option Start] The functionality described on this reference page is aligned with the ISO C standard. Any conflict between the requirements described here and the ISO C standard is unintentional. This volume of POSIX.1-2008 defers to the ISO C standard. [Option End]

The memmove() function shall copy n bytes from the object pointed to by s2 into the object pointed to by s1. Copying takes place as if the n bytes from the object pointed to by s2 are first copied into a temporary array of n bytes that does not overlap the objects pointed to by s1 and s2, and then the n bytes from the temporary array are copied into the object pointed to by s1.

In case when physical memory areas overlap but addresses do not, results of memmove(3) are impossible to rely upon on all implementations I've seen.