Extend memory caching of umove* functions

* ucopy.c (cached_raddr): Double the size.
(get_next_unused_idx, lookup_cached_raddr_idx, set_cached_raddr_idx):
New functions.
(vm_read_mem): Use them.  When the data to be fetched resides in
up to 4 adjacent memory pages, fetch these pages and cache them.
* tests/umovestr_cached_adjacent.c: New file.
* tests/pure_executables.list: Add umovestr_cached_adjacent.
* tests/.gitignore: Likewise.
* tests/umovestr_cached.test: Handle the first argument.
* tests/gen_tests.in (umovestr_cached_adjacent): New test.

6 files changed, 134 insertions, 37 deletions

diff --git a/tests/.gitignore b/tests/.gitignore
index 3e3140962..40f10fba4 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -734,6 +734,7 @@ umovestr-illptr
 umovestr2
 umovestr3
 umovestr_cached
+umovestr_cached_adjacent
 uname
 unblock_reset_raise
 unix-pair-send-recv
diff --git a/tests/gen_tests.in b/tests/gen_tests.in
index 8949acded..c3cc27727 100644
--- a/tests/gen_tests.in
+++ b/tests/gen_tests.in
@@ -680,6 +680,7 @@ umask	-a11
 umoven-illptr	-a36 -e trace=nanosleep
 umovestr-illptr	-a11 -e trace=chdir
 umovestr3	-a14 -e trace=chdir
+umovestr_cached_adjacent	+umovestr_cached.test 3
 unlink	-a24
 unlinkat	-a35
 unshare	-a11
diff --git a/tests/pure_executables.list b/tests/pure_executables.list
index 1b22b130b..2d4e36c60 100755
--- a/tests/pure_executables.list
+++ b/tests/pure_executables.list
@@ -593,6 +593,7 @@ umovestr-illptr
 umovestr2
 umovestr3
 umovestr_cached
+umovestr_cached_adjacent
 uname
 unlink
 unlinkat
diff --git a/tests/umovestr_cached.test b/tests/umovestr_cached.test
index 6553a3587..4b9c83266 100755
--- a/tests/umovestr_cached.test
+++ b/tests/umovestr_cached.test
@@ -9,8 +9,10 @@
 
 . "${srcdir=.}/init.sh"
 
+expected_count="${1:-2}"
+
 check_prog grep
-$STRACE -d -enone / > /dev/null 2> "$LOG"
+$STRACE -d -enone / > /dev/null 2> "$LOG" ||:
 grep -x "[^:]*strace: PTRACE_GET_SYSCALL_INFO works" "$LOG" > /dev/null || {
 	# PTRACE_GET_SYSCALL_INFO does not work
 	case "$STRACE_ARCH:$MIPS_ABI" in
@@ -34,6 +36,6 @@ run_strace -qq -esignal=none -eprocess_vm_readv -z \
 count="$(cat count)"
 case "$count" in
 	0) skip_ "$STRACE $args made no process_vm_readv syscall invocations" ;;
-	2) ;;
-	*) fail_ "$STRACE $args made $count != 2 process_vm_readv syscall invocations" ;;
+	$expected_count) ;;
+	*) fail_ "$STRACE $args made $count != $expected_count process_vm_readv syscall invocations" ;;
 esac
diff --git a/tests/umovestr_cached_adjacent.c b/tests/umovestr_cached_adjacent.c
new file mode 100644
index 000000000..53a573b3d
--- /dev/null
+++ b/tests/umovestr_cached_adjacent.c
@@ -0,0 +1,48 @@
+/*
+ * Check effectiveness of umovestr memory caching.
+ *
+ * Copyright (c) 2019-2020 Dmitry V. Levin <ldv@altlinux.org>
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier: GPL-2.0-or-later
+ */
+
+#include "tests.h"
+
+#include <stdio.h>
+#include <string.h>
+#include <unistd.h>
+#include <sys/uio.h>
+
+int
+main(void)
+{
+	const size_t size = get_page_size() + (DEFAULT_STRLEN - 1);
+	char *const buf = tail_alloc(size);
+	fill_memory_ex(buf, DEFAULT_STRLEN * 2, 'a', 'z' - 'a' + 1);
+
+	struct iovec *const io = tail_alloc(sizeof(*io) * DEFAULT_STRLEN);
+	for (unsigned int i = 0; i < DEFAULT_STRLEN; ++i) {
+		io[i].iov_base = buf + i;
+		io[i].iov_len = DEFAULT_STRLEN;
+	}
+
+	tprintf("%s", "");
+
+	int rc = writev(-1, io, DEFAULT_STRLEN);
+	const char *errstr = sprintrc(rc);
+
+	tprintf("writev(-1, [");
+	for (unsigned int i = 0; i < DEFAULT_STRLEN; ++i) {
+		if (i)
+			tprintf(", ");
+		tprintf("{iov_base=\"%.*s\", iov_len=%u}",
+			(int) io[i].iov_len,
+			(char *) io[i].iov_base,
+			(unsigned int) io[i].iov_len);
+	}
+	tprintf("], %u) = %s\n", DEFAULT_STRLEN, errstr);
+
+	tprintf("+++ exited with 0 +++\n");
+	return 0;
+}
diff --git a/ucopy.c b/ucopy.c
index 21f55e28a..13c4103b3 100644
--- a/ucopy.c
+++ b/ucopy.c
@@ -61,7 +61,7 @@ process_read_mem(const pid_t pid, void *const laddr,
 }
 
 static int cached_idx = -1;
-static unsigned long cached_raddr[2];
+static unsigned long cached_raddr[4];
 
 void
 invalidate_umove_cache(void)
@@ -69,17 +69,47 @@ invalidate_umove_cache(void)
 	cached_idx = -1;
 }
 
+static int
+get_next_unused_idx(void)
+{
+	return (cached_idx + 1) % ARRAY_SIZE(cached_raddr);
+}
+
+static int
+lookup_cached_raddr_idx(const unsigned long raddr)
+{
+	if (cached_idx >= 0) {
+		for (int i = cached_idx; i >= 0; --i)
+			if (raddr == cached_raddr[i])
+				return i;
+		for (int i = (int) ARRAY_SIZE(cached_raddr) - 1;
+		     i > cached_idx; --i)
+			if (raddr == cached_raddr[i])
+				return i;
+	}
+	return -1;
+}
+
+static void
+set_cached_raddr_idx(const unsigned long raddr, const int idx)
+{
+	if (cached_idx < 0)
+		memset(cached_raddr, 0, sizeof(cached_raddr));
+	cached_raddr[idx] = raddr;
+	cached_idx = idx;
+}
+
 static ssize_t
-vm_read_mem(const pid_t pid, void *const laddr,
-	    const kernel_ulong_t raddr, const size_t len)
+vm_read_mem(const pid_t pid, void *laddr,
+	    const kernel_ulong_t kraddr, size_t len)
 {
 	if (!len)
 		return len;
 
-	const unsigned long taddr = raddr;
+	unsigned long taddr = kraddr;
 
 #if SIZEOF_LONG < SIZEOF_KERNEL_LONG_T
-	if (raddr != (kernel_ulong_t) taddr) {
+	if (kraddr != (kernel_ulong_t) taddr) {
 		errno = EIO;
 		return -1;
 	}
@@ -87,46 +117,60 @@ vm_read_mem(const pid_t pid, void *const laddr,
 
 	const size_t page_size = get_pagesize();
 	const size_t page_mask = page_size - 1;
-	const unsigned long raddr_page_start =
-		taddr & ~page_mask;
-	const unsigned long raddr_page_next =
+	unsigned long page_start = taddr & ~page_mask;
+	const unsigned long page_after_last =
 		(taddr + len + page_mask) & ~page_mask;
 
-	if (!raddr_page_start ||
-	    raddr_page_next < raddr_page_start ||
-	    raddr_page_next - raddr_page_start != page_size)
+	if (!page_start ||
+	    page_after_last < page_start ||
+	    page_after_last - page_start > ARRAY_SIZE(cached_raddr) * page_size)
 		return process_read_mem(pid, laddr, (void *) taddr, len);
 
-	int idx = -1;
-	if (cached_idx >= 0) {
-		if (raddr_page_start == cached_raddr[cached_idx])
-			idx = cached_idx;
-		else if (raddr_page_start == cached_raddr[!cached_idx])
-			idx = !cached_idx;
-	}
+	size_t total_read = 0;
+
+	for (;;) {
+		static char *buf[ARRAY_SIZE(cached_raddr)];
+		int idx = lookup_cached_raddr_idx(page_start);
+
+		if (idx == -1) {
+			idx = get_next_unused_idx();
 
-	static char *buf[2];
+			if (!buf[idx])
+				buf[idx] = xmalloc(page_size);
 
-	if (idx == -1) {
-		idx = !cached_idx;
+			const ssize_t rc =
+				process_read_mem(pid, buf[idx],
+						 (void *) page_start, page_size);
+			if (rc < 0)
+				return total_read ? (ssize_t) total_read : rc;
+
+			set_cached_raddr_idx(page_start, idx);
+		}
+
+		const unsigned long offset = taddr - page_start;
+		size_t copy_len, next_len;
+
+		if (len <= page_size - offset) {
+			copy_len = len;
+			next_len = 0;
+		} else {
+			copy_len = page_size - offset;
+			next_len = len - copy_len;
+		}
 
-		if (!buf[idx])
-			buf[idx] = xmalloc(page_size);
+		memcpy(laddr, buf[idx] + offset, copy_len);
+		total_read += copy_len;
 
-		const ssize_t rc =
-			process_read_mem(pid, buf[idx],
-					 (void *) raddr_page_start, page_size);
-		if (rc < 0)
-			return rc;
+		if (!next_len)
+			break;
 
-		cached_raddr[idx] = raddr_page_start;
-		if (cached_idx < 0)
-			cached_raddr[!idx] = 0;
-		cached_idx = idx;
+		len = next_len;
+		laddr += copy_len;
+		page_start += page_size;
+		taddr = page_start;
 	}
 
-	memcpy(laddr, buf[idx] + (taddr - cached_raddr[idx]), len);
-	return len;
+	return total_read;
 }
 
 static bool