Skip to contentSkip to conversation

new feature: monitoring page cache events

PATCH In review George Amvrosiadis 2 participants 9 messages Jul 26, 2016 – Aug 1, 2016

Subsystems (8)
Memory management x86 VFS MM core +4 more subsystems
lore
Share & tools
lore
#0 lore raw

cover new feature: monitoring page cache events

I'm attaching a patch set implementing a mechanism we call Duet, which allows applications to monitor events at the page cache level: page additions, removals, dirtying, and flushing. Using such events, applications can identify and prioritize processing of cached data, thereby reducing their I/O footprint.

One user of these events are maintenance tasks that scan large amounts of data (e.g., backup, defrag, scrubbing). Knowing what is currently cached allows them to piggy-back on each other and other applications running in the system. I've managed to run up to 3 such applications together (backup, scrubbing, defrag) and have them finish their work with 1/3rd of the I/O by using Duet. In this case, the task that traversed the data the fastest (scrubber) allowed the rest of the tasks to piggyback on the data brought into the cache. I.e., a file that was read to be backed up was also picked up by the scrubber and defrag process.

I've found adapting applications to be straight-forward. Although I don't include examples in this patch set, I've adapted btrfs scrubbing, btrfs send (backup), btrfs defrag, rsync, and f2fs garbage collection in a few hundred lines of code each (basically just had to add an event handler and wire it up to the task's processing loop). You can read more about this in our full paper:
http://dl.acm.org/citation.cfm?id=2815424. I'd be happy to generate subsequent patch sets for individual tasks if there's interest in this one. We've also used Duet to speed up Hadoop and Spark by taking into account cache residency of HDFS blocks across the cluster, when scheduling tasks, by up to 54% depending on overlap on the data processed:
https://www.usenix.org/conference/hotstorage16/workshop-program/presentation/deslauriers

Syscall interface (and how it works): Duet uses hooks into the page cache (see the "mm: support for duet hooks" patch). These hooks inform Duet of page events, which are stored in a hash table. Only events that are of interest to running tasks are stored, and only one copy of each event is stored for all interested tasks. To register for events, the following syscalls are used (see the "mm/duet: syscall wiring" patch for prototypes):

- sys_duet_init(char *taskname, u32 regmask, char *path): returns an fd that watches for events under PATH (e.g. '/home') and are also described in the REGMASK (e.g. DUET_PAGE_ADDED | DUET_PAGE_REMOVED). TASKNAME is an optional, human-readable name for the task.

- sys_duet_bmap(u16 flags, struct duet_uuid_arg *uuid): Duet allows applications to track processed items on an internal bitmap (which improves performance by being used to filter unnecessary events). The specified UUID is what read() returns on the fd created with sys_duet_init(), and uniquely identifies a file. FLAGS allow the bitmap to be set, reset, or have its state checked.

- sys_duet_get_path(struct duet_uuid_arg *uuid, char *buf, int bufsize):
Applications running with Duet do not understand UUIDs, but pathnames. This syscall traverses the dentry cache and returns the corresponding path in BUF.

- sys_duet_status(u16 flags, struct duet_status_args *arg): Currently, the Duet framework can be turned on/off manually. This allows the admin to specify the number of max applications that will be registered concurrently, which allows us to size the internal hash table nodes appropriately (and limit performance or memory overhead). The syscall is also used for debugging purposes. I think this functionality should probably be exposed through ioctl()s to a device, and I'm open to suggestions on how to improve the current implementation.

The framework itself (a bit less than 2300 LoC) is currently placed under mm/duet and the code is included in the "mm/duet: framework code" patch.

Application interface: Applications interface with Duet through a user library, which is available at https://github.com/gamvrosi/duet-tools. In the same repo, I have included a dummy_task application which provides an example of how Duet can be used.

Changelog: The patches are based on Linus' v4.7 tag, and touch on the following parts of the kernel:

- mm/filemap.c and include/linux/page-flags.h: hooks in the page cache to track page events on page addition, removal, dirtying, and flushing.

- arch/x86/*, include/linux/syscalls.h, kernel/sys_ni.h: wiring the 4 syscalls

- mm/duet/*: framework code

George Amvrosiadis (3):
mm: support for duet hooks
mm/duet: syscall wiring
mm/duet: framework code

 arch/x86/entry/syscalls/syscall_32.tbl |   4 +
 arch/x86/entry/syscalls/syscall_64.tbl |   4 +
 include/linux/duet.h                   |  43 +++
 include/linux/page-flags.h             |  53 +++
 include/linux/syscalls.h               |   8 +
 include/uapi/asm-generic/unistd.h      |  12 +-
 init/Kconfig                           |   2 +
 kernel/sys_ni.c                        |   6 +
 mm/Makefile                            |   1 +
 mm/duet/Kconfig                        |  31 ++
 mm/duet/Makefile                       |   7 +
 mm/duet/bittree.c                      | 537 ++++++++++++++++++++++++++++++
 mm/duet/common.h                       | 211 ++++++++++++
 mm/duet/debug.c                        |  98 ++++++
 mm/duet/hash.c                         | 315 ++++++++++++++++++
 mm/duet/hook.c                         |  81 +++++
 mm/duet/init.c                         | 172 ++++++++++
 mm/duet/path.c                         | 184 +++++++++++
 mm/duet/syscall.h                      |  61 ++++
 mm/duet/task.c                         | 584 +++++++++++++++++++++++++++++++++
 mm/filemap.c                           |  11 +
 21 files changed, 2424 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/duet.h
 create mode 100644 mm/duet/Kconfig
 create mode 100644 mm/duet/Makefile
 create mode 100644 mm/duet/bittree.c
 create mode 100644 mm/duet/common.h
 create mode 100644 mm/duet/debug.c
 create mode 100644 mm/duet/hash.c
 create mode 100644 mm/duet/hook.c
 create mode 100644 mm/duet/init.c
 create mode 100644 mm/duet/path.c
 create mode 100644 mm/duet/syscall.h
 create mode 100644 mm/duet/task.c
Signature · 7 lines
2.7.4

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#1 lore raw

PATCH 1/3 mm: support for duet hooks

Adds the Duet hooks in the page cache. In filemap.c, two hooks are added at the time of addition and removal of a page descriptor. In page-flags.h, two more hooks are added to track page dirtying and flushing.

The hooks are inactive while Duet is offline.

---
 include/linux/duet.h       | 43 +++++++++++++++++++++++++++++++++++++
 include/linux/page-flags.h | 53 ++++++++++++++++++++++++++++++++++++++++++++++
 mm/filemap.c               | 11 ++++++++++
 3 files changed, 107 insertions(+)
 create mode 100644 include/linux/duet.h
include/linux/duet.h new file +43 -0
new file mode 100644
index 0000000..80491e2
@@ -0,0 +1,43 @@
+/*
+ * Defs necessary for Duet hooks
+ *
+ * Author: George Amvrosiadis <[email protected]>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public
+ * License v2 as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ */
+#ifndef _DUET_H
+#define _DUET_H
+
+/*
+ * Duet hooks into the page cache to monitor four types of events:
+ *   ADDED:	a page __descriptor__ was inserted into the page cache
+ *   REMOVED:	a page __describptor__ was removed from the page cache
+ *   DIRTY:	page's dirty bit was set
+ *   FLUSHED:	page's dirty bit was cleared
+ */
+#define DUET_PAGE_ADDED		0x0001
+#define DUET_PAGE_REMOVED	0x0002
+#define DUET_PAGE_DIRTY		0x0004
+#define DUET_PAGE_FLUSHED	0x0008
+
+#define DUET_HOOK(funp, evt, data) \
+	do { \
+		rcu_read_lock(); \
+		funp = rcu_dereference(duet_hook_fp); \
+		if (funp) \
+			funp(evt, (void *)data); \
+		rcu_read_unlock(); \
+	} while (0)
+
+/* Hook function pointer initialized by the Duet framework */
+typedef void (duet_hook_t) (__u16, void *);
+extern duet_hook_t *duet_hook_fp;
+
+#endif /* _DUET_H */
include/linux/page-flags.h +53 -0

67 lines not on this page · raw message

mm/filemap.c +11 -0
index 20f3b1f..f06ebc0 100644
@@ -166,6 +166,11 @@ static void page_cache_tree_delete(struct address_space *mapping,
 void __delete_from_page_cache(struct page *page, void *shadow)
 {
 	struct address_space *mapping = page->mapping;
+#ifdef CONFIG_DUET
+	duet_hook_t *dhfp = NULL;
+
+	DUET_HOOK(dhfp, DUET_PAGE_REMOVED, page);
+#endif /* CONFIG_DUET */
 
 	trace_mm_filemap_delete_from_page_cache(page);
 	/*
@@ -628,6 +633,9 @@ static int __add_to_page_cache_locked(struct page *page,
 	int huge = PageHuge(page);
 	struct mem_cgroup *memcg;
 	int error;
+#ifdef CONFIG_DUET
+	duet_hook_t *dhfp = NULL;
+#endif
 
 	VM_BUG_ON_PAGE(!PageLocked(page), page);
 	VM_BUG_ON_PAGE(PageSwapBacked(page), page);
@@ -663,6 +671,9 @@ static int __add_to_page_cache_locked(struct page *page,
 	if (!huge)
 		mem_cgroup_commit_charge(page, memcg, false, false);
 	trace_mm_filemap_add_to_page_cache(page);
+#ifdef CONFIG_DUET
+	DUET_HOOK(dhfp, DUET_PAGE_ADDED, page);
+#endif
 	return 0;
 err_insert:
 	page->mapping = NULL;
Signature · 7 lines
2.7.4

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#2 lore raw

PATCH 2/3 mm/duet: syscall wiring

In reply to George Amvrosiadis

Usual syscall wiring for the four Duet syscalls.

---
 arch/x86/entry/syscalls/syscall_32.tbl |  4 ++++
 arch/x86/entry/syscalls/syscall_64.tbl |  4 ++++
 include/linux/syscalls.h               |  8 ++++++++
 include/uapi/asm-generic/unistd.h      | 12 +++++++++++-
 kernel/sys_ni.c                        |  6 ++++++
 5 files changed, 33 insertions(+), 1 deletion(-)
arch/x86/entry/syscalls/syscall_32.tbl +4 -0
index 4cddd17..f34ff94 100644
@@ -386,3 +386,7 @@
 377	i386	copy_file_range		sys_copy_file_range
 378	i386	preadv2			sys_preadv2			compat_sys_preadv2
 379	i386	pwritev2		sys_pwritev2			compat_sys_pwritev2
+380	i386	duet_status		sys_duet_status
+381	i386	duet_init		sys_duet_init
+382	i386	duet_bmap		sys_duet_bmap
+383	i386	duet_get_path		sys_duet_get_path
arch/x86/entry/syscalls/syscall_64.tbl +4 -0
index 555263e..d04efaa 100644
@@ -335,6 +335,10 @@
 326	common	copy_file_range		sys_copy_file_range
 327	64	preadv2			sys_preadv2
 328	64	pwritev2		sys_pwritev2
+329	common	duet_status		sys_duet_status
+330	common	duet_init		sys_duet_init
+331	common	duet_bmap		sys_duet_bmap
+332	common	duet_get_path		sys_duet_get_path
 
 #
 # x32-specific system call numbers start at 512 to avoid cache impact
include/linux/syscalls.h +8 -0
index d022390..da1049e 100644
@@ -65,6 +65,8 @@ struct old_linux_dirent;
 struct perf_event_attr;
 struct file_handle;
 struct sigaltstack;
+struct duet_status_args;
+struct duet_uuid_arg;
 union bpf_attr;
 
 #include <linux/types.h>
@@ -898,4 +900,10 @@ asmlinkage long sys_copy_file_range(int fd_in, loff_t __user *off_in,
 
 asmlinkage long sys_mlock2(unsigned long start, size_t len, int flags);
 
+asmlinkage long sys_duet_status(u16 flags, struct duet_status_args __user *arg);
+asmlinkage long sys_duet_init(const char __user *taskname, u32 regmask,
+			      const char __user *pathname);
+asmlinkage long sys_duet_bmap(u16 flags, struct duet_uuid_arg __user *arg);
+asmlinkage long sys_duet_get_path(struct duet_uuid_arg __user *uarg,
+				  char __user *pathbuf, int pathbufsize);
 #endif
include/uapi/asm-generic/unistd.h +11 -1
index a26415b..7c287c0 100644
@@ -725,8 +725,18 @@ __SC_COMP(__NR_preadv2, sys_preadv2, compat_sys_preadv2)
 #define __NR_pwritev2 287
 __SC_COMP(__NR_pwritev2, sys_pwritev2, compat_sys_pwritev2)
 
+/* mm/duet/syscall.c */
+#define __NR_duet_status 288
+__SYSCALL(__NR_duet_status, sys_duet_status)
+#define __NR_duet_init 289
+__SYSCALL(__NR_duet_init, sys_duet_init)
+#define __NR_duet_bmap 290
+__SYSCALL(__NR_duet_bmap, sys_duet_bmap)
+#define __NR_duet_get_path 291
+__SYSCALL(__NR_duet_get_path, sys_duet_get_path)
+
 #undef __NR_syscalls
-#define __NR_syscalls 288
+#define __NR_syscalls 292
 
 /*
  * All syscalls below here should go away really,
kernel/sys_ni.c +6 -0
index 2c5e3a8..3d4c53a 100644
@@ -176,6 +176,12 @@ cond_syscall(sys_capget);
 cond_syscall(sys_capset);
 cond_syscall(sys_copy_file_range);
 
+/* Duet syscall entries */
+cond_syscall(sys_duet_status);
+cond_syscall(sys_duet_init);
+cond_syscall(sys_duet_bmap);
+cond_syscall(sys_duet_get_path);
+
 /* arch-specific weak syscall entries */
 cond_syscall(sys_pciconfig_read);
 cond_syscall(sys_pciconfig_write);
Signature · 7 lines
2.7.4

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#3 lore raw

PATCH 3/3 mm/duet: framework code

In reply to George Amvrosiadis

The Duet framework code:

- bittree.c: red-black bitmap tree that keeps track of items of interest
- debug.c: functions used to print information used to debug Duet
- hash.c: implementation of the global hash table where page events are stored for all tasks
- hook.c: the function invoked by the page cache hooks when Duet is online
- init.c: routines used to bring Duet online or offline
- path.c: routines performing resolution of UUIDs to paths using d_path
- task.c: implementation of Duet task fd operations

---
 init/Kconfig      |   2 +
 mm/Makefile       |   1 +
 mm/duet/Kconfig   |  31 +++
 mm/duet/Makefile  |   7 +
 mm/duet/bittree.c | 537 +++++++++++++++++++++++++++++++++++++++++++++++++
 mm/duet/common.h  | 211 ++++++++++++++++++++
 mm/duet/debug.c   |  98 +++++++++
 mm/duet/hash.c    | 315 +++++++++++++++++++++++++++++
 mm/duet/hook.c    |  81 ++++++++
 mm/duet/init.c    | 172 ++++++++++++++++
 mm/duet/path.c    | 184 +++++++++++++++++
 mm/duet/syscall.h |  61 ++++++
 mm/duet/task.c    | 584 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 13 files changed, 2284 insertions(+)
 create mode 100644 mm/duet/Kconfig
 create mode 100644 mm/duet/Makefile
 create mode 100644 mm/duet/bittree.c
 create mode 100644 mm/duet/common.h
 create mode 100644 mm/duet/debug.c
 create mode 100644 mm/duet/hash.c
 create mode 100644 mm/duet/hook.c
 create mode 100644 mm/duet/init.c
 create mode 100644 mm/duet/path.c
 create mode 100644 mm/duet/syscall.h
 create mode 100644 mm/duet/task.c
init/Kconfig +2 -0
index c02d897..6f94b5a 100644
@@ -294,6 +294,8 @@ config USELIB
 	  earlier, you may need to enable this syscall.  Current systems
 	  running glibc can safely disable this.
 
+source mm/duet/Kconfig
+
 config AUDIT
 	bool "Auditing support"
 	depends on NET
mm/Makefile +1 -0
index 78c6f7d..074c15f 100644
@@ -99,3 +99,4 @@ obj-$(CONFIG_USERFAULTFD) += userfaultfd.o
 obj-$(CONFIG_IDLE_PAGE_TRACKING) += page_idle.o
 obj-$(CONFIG_FRAME_VECTOR) += frame_vector.o
 obj-$(CONFIG_DEBUG_PAGE_REF) += debug_page_ref.o
+obj-$(CONFIG_DUET) += duet/
mm/duet/Kconfig new file +31 -0
new file mode 100644
index 0000000..2f3a0c5
@@ -0,0 +1,31 @@
+config DUET
+	bool "Duet framework support"
+
+	help
+	  Duet is a framework aiming to reduce the IO footprint of analytics
+	  and maintenance work. By exposing page cache events to these tasks,
+	  it allows them to adapt their data processing order, in order to
+	  benefit from data available in the page cache. Duet's operation is
+	  based on hooks into the page cache.
+
+	  To compile support for Duet, say Y.
+
+config DUET_STATS
+	bool "Duet statistics collection"
+	depends on DUET
+	help
+	  This option enables support for the collection of statistics on the
+	  operation of Duet. It will print information about the data structures
+	  used internally, and profiling information about the framework.
+
+	  If unsure, say N.
+
+config DUET_DEBUG
+	bool "Duet debugging support"
+	depends on DUET
+	help
+	  Enable runtime debugging support for the Duet framework. This may
+	  enable additional and expensive checks with negative impact on
+	  performance.
+
+	  To compile debugging support for Duet, say Y. If unsure, say N.
mm/duet/Makefile new file +7 -0
new file mode 100644
index 0000000..c0c9e11
@@ -0,0 +1,7 @@
+#
+# Makefile for the linux Duet framework.
+#
+
+obj-$(CONFIG_DUET) += duet.o
+
+duet-y := init.o hash.o hook.o task.o bittree.o path.o debug.o
mm/duet/bittree.c new file +537 -0

537 lines not on this page · raw message

mm/duet/common.h new file +211 -0

211 lines not on this page · raw message

mm/duet/debug.c new file +98 -0

98 lines not on this page · raw message

mm/duet/hash.c new file +315 -0

315 lines not on this page · raw message

mm/duet/hook.c new file +81 -0

81 lines not on this page · raw message

mm/duet/init.c new file +172 -0

172 lines not on this page · raw message

mm/duet/path.c new file +184 -0

184 lines not on this page · raw message

mm/duet/syscall.h new file +61 -0

61 lines not on this page · raw message

mm/duet/task.c new file +584 -0

584 lines not on this page · raw message

Signature · 7 lines
2.7.4

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
#4 lore raw
In reply to George Amvrosiadis
Quoted 1 line · George Amvrosiadis
 21 files changed, 2424 insertions(+), 1 deletion(-)

I like the idea, but yikes, that's a lot of code.

Have you considered using or augmenting the kernel's existing tracing mechanisms? Have you considered using something like netlink for transporting the data out of the kernel?

The PageDirty() hooks look simple but turn out to be horribly deep. Where we used to have a plain old bit set, we now have new locks, potentially long periods of irq disabling, and loops over all the tasks doing duet, even path lookup!

Given a big system, I would imagine these locks slowing down SetPageDirty() and things like write() pretty severely. Have you done
an assessment of the performance impact of this change? I can't
imagine this being used in any kind of performance or scalability-sensitive environment.

The current tracing code has a model where the trace producers put data in *one* place, then all the mulitple consumers pull it out of that place. Duet seems to have the model that the producer puts the data in multiple places and consumers consume it from their own private copies.
That seems a bit backwards and puts cost directly in to hot code paths. Even a single task watching a single file on the system makes everyone
go in and pay some of this cost for every SetPageDirty().

Let's say we had a big system with virtually everything sitting in the page cache. Does duet have a way to find things currently _in_ the cache, or only when things move in/out of it?

Tasks seem to have a fixed 'struct path' ->regpath at duet_task_init() time. The code goes page->mapping->inode->i_dentry and then tries to compare that with the originally recorded path. Does this even work in the face of things like bind mounts, mounts that change after duet_task_init(), or mounting a fs with a different superblock underneath a watched path? It seems awfully fragile.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#5 lore raw
Quoted 9 lines · Dave Hansen
Quoted 1 line · George Amvrosiadis
 21 files changed, 2424 insertions(+), 1 deletion(-)

I like the idea, but yikes, that's a lot of code.

Have you considered using or augmenting the kernel's existing tracing mechanisms? Have you considered using something like netlink for transporting the data out of the kernel?

We contemplated a couple other solutions. One was extending existing debugging mechanisms. E.g., there are already tracepoints at __add_to_page_cache_locked() and __delete_from_page_cache(). A consistent reaction I got for doing that, however, was that of exposing an unruly interface to user applications, which is certainly not an elegant solution. After that experience, and reading up on issues of the auditing subsystem (https://lwn.net/Articles/600568/) I decided to avoid going further down that path.

Quoted 5 lines

The PageDirty() hooks look simple but turn out to be horribly deep. Where we used to have a plain old bit set, we now have new locks, potentially long periods of irq disabling, and loops over all the tasks doing duet, even path lookup!

It's true that the hooks are deep, but they are fully exercised only once per inode, per task. The reasoning behind the 'struct bmap_rbnode'->seen bitmap is to remember whether an inode was seen before by a given task. During that first access is when we do the path lookup to decide whether this inode is relevant to the task and mark 'struct bmap_rbnode'->relv accordingly. If it is not, we ignore future events from it. Tasks can also use the 'structu bmap_rbnode'->done bitmap to indicate that they are done with a specific inode, which also stops those events from passing that task loop.

Quoted 6 lines

Given a big system, I would imagine these locks slowing down SetPageDirty() and things like write() pretty severely. Have you done
an assessment of the performance impact of this change? I can't
imagine this being used in any kind of performance or scalability-sensitive environment.

I have used filebench to saturate an HDD and an SSD, registered a task to be notified about every file in the filesystem, and measured no difference in I/O throughput. To measure the CPU utilization of Duet, I tried an extreme case where I booted using only one core and again saturated an HDD using filebench. There was a 1-1.5% increase in CPU utilization. There is a description of this result in the paper. I have also tuned filebench to hit the cache often in my experiments (more than 60-70% of accesses going to less than 10% of the data), but the results were similar. For the Hadoop and Spark experiments we used a 24-node cluster and these overhead numbers didn't seem to affect performance.

Quoted 8 lines

The current tracing code has a model where the trace producers put data in *one* place, then all the mulitple consumers pull it out of that place. Duet seems to have the model that the producer puts the data in multiple places and consumers consume it from their own private copies.
That seems a bit backwards and puts cost directly in to hot code paths. Even a single task watching a single file on the system makes everyone
go in and pay some of this cost for every SetPageDirty().

Duet operates in a similar way. There is one large global hash table to avoid collisions, so that on average a single lookup is sufficient to place a page in it. Due to its global nature, if a page is of interest to multiple tasks, only one entry is used to hold the events for that page across all tasks. And to avoid walking that hash table for relevant events on a read(), each task maintains a separate bitmap of the hash table's buckets that tells it which buckets to look into. (In the past I've also tried a work queue approach on the hot code path, but the overhead was almost double as a result of allocating the work queue items.)

Having said all the above, Dave, I've seen your work at the 2013 Linux Plumbers Conference on scalability issues, so if you think I'm missing something in my replies, please call me out on that. I'm definitely open to improving this code.

Quoted 4 lines

Let's say we had a big system with virtually everything sitting in the page cache. Does duet have a way to find things currently _in_ the cache, or only when things move in/out of it?

At task registration time we grab the superblock for the filesystem of the registered path, and then scan_page_cache() traverses the list of inodes currently in memory. We enqueue ADDED and DIRTY events for relevant inodes as needed.

Quoted 6 lines

Tasks seem to have a fixed 'struct path' ->regpath at duet_task_init() time. The code goes page->mapping->inode->i_dentry and then tries to compare that with the originally recorded path. Does this even work in the face of things like bind mounts, mounts that change after duet_task_init(), or mounting a fs with a different superblock underneath a watched path? It seems awfully fragile.

This is an excellent point. Currently any events that occur on inodes of a different superblock would get filtered at duet_hook() for those tasks that haven't registered with that superblock. One solution is to do a duet_init() once per file system, and have the user application use select() on all those fds. This could potentially be done under the covers by the userlevel library.

I'm not sure how to handle mounts that change, however. At the very least I would like to be able to somehow inform Duet at unmount to close any outstanding fds. Any ideas/thoughts on this would be really appreciated, obviously.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#6 lore raw
Quoted 10 lines · George Amvrosiadis
Quoted 8 lines · Dave Hansen
Quoted 1 line · George Amvrosiadis
 21 files changed, 2424 insertions(+), 1 deletion(-)

I like the idea, but yikes, that's a lot of code.

Have you considered using or augmenting the kernel's existing tracing mechanisms? Have you considered using something like netlink for transporting the data out of the kernel?

Quoted 5 lines

We contemplated a couple other solutions. One was extending existing debugging mechanisms. E.g., there are already tracepoints at __add_to_page_cache_locked() and __delete_from_page_cache(). A consistent reaction I got for doing that, however, was that of exposing an unruly interface to user applications, which is certainly not an elegant solution.

What's to stop you from using tracing to gather and transport data out of the kernel and then aggregate and present it to apps in an "elegant" way of your choosing?

Quoted 5 lines
Quoted 4 lines

The PageDirty() hooks look simple but turn out to be horribly deep. Where we used to have a plain old bit set, we now have new locks, potentially long periods of irq disabling, and loops over all the tasks doing duet, even path lookup!

Quoted 8 lines

It's true that the hooks are deep, but they are fully exercised only once per inode, per task. The reasoning behind the 'struct bmap_rbnode'->seen bitmap is to remember whether an inode was seen before by a given task. During that first access is when we do the path lookup to decide whether this inode is relevant to the task and mark 'struct bmap_rbnode'->relv accordingly. If it is not, we ignore future events from it. Tasks can also use the 'structu bmap_rbnode'->done bitmap to indicate that they are done with a specific inode, which also stops those events from passing that task loop.

OK, but it still disables interrupts and takes a spinlock for each bitmap it checks. That spinlock becomes essentially a global lock in a hot path, which can't be good.

Quoted 6 lines
Quoted 5 lines

Given a big system, I would imagine these locks slowing down SetPageDirty() and things like write() pretty severely. Have you done
an assessment of the performance impact of this change? I can't
imagine this being used in any kind of performance or scalability-sensitive environment.

Quoted 9 lines

I have used filebench to saturate an HDD and an SSD, registered a task to be notified about every file in the filesystem, and measured no difference in I/O throughput. To measure the CPU utilization of Duet, I tried an extreme case where I booted using only one core and again saturated an HDD using filebench. There was a 1-1.5% increase in CPU utilization. There is a description of this result in the paper. I have also tuned filebench to hit the cache often in my experiments (more than 60-70% of accesses going to less than 10% of the data), but the results were similar. For the Hadoop and Spark experiments we used a 24-node cluster and these overhead numbers didn't seem to affect performance.

I'd say testing with _more_ cores is important, not less. How about trying to watch a single file, then have one process per core writing to a 1MB file in a loop. What does that do? Or, heck, just compile a kernel on a modern 2-socket system.

In any case, I still can't see the current duet _model_ ever working out, much less the implementation posted here.

Quoted 8 lines
Quoted 7 lines

The current tracing code has a model where the trace producers put data in *one* place, then all the mulitple consumers pull it out of that place. Duet seems to have the model that the producer puts the data in multiple places and consumers consume it from their own private copies.
That seems a bit backwards and puts cost directly in to hot code paths. Even a single task watching a single file on the system makes everyone
go in and pay some of this cost for every SetPageDirty().

Quoted 9 lines

Duet operates in a similar way. There is one large global hash table to avoid collisions, so that on average a single lookup is sufficient to place a page in it. Due to its global nature, if a page is of interest to multiple tasks, only one entry is used to hold the events for that page across all tasks. And to avoid walking that hash table for relevant events on a read(), each task maintains a separate bitmap of the hash table's buckets that tells it which buckets to look into. (In the past I've also tried a work queue approach on the hot code path, but the overhead was almost double as a result of allocating the work queue items.)

I don't think Duet operates in a similar way. Asserting that it does makes me wary that you've understood and actually considered how tracing works.

Duet takes global locks in hot paths. The tracing code doesn't do that.
It uses percpu buffers that don't require shared locks when adding
records. It makes the reader of the data do all the hard work.

Quoted 13 lines
Quoted 6 lines

Tasks seem to have a fixed 'struct path' ->regpath at duet_task_init() time. The code goes page->mapping->inode->i_dentry and then tries to compare that with the originally recorded path. Does this even work in the face of things like bind mounts, mounts that change after duet_task_init(), or mounting a fs with a different superblock underneath a watched path? It seems awfully fragile.

This is an excellent point. Currently any events that occur on inodes of a different superblock would get filtered at duet_hook() for those tasks that haven't registered with that superblock. One solution is to do a duet_init() once per file system, and have the user application use select() on all those fds. This could potentially be done under the covers by the userlevel library.

Quoted 4 lines

I'm not sure how to handle mounts that change, however. At the very least I would like to be able to somehow inform Duet at unmount to close any outstanding fds. Any ideas/thoughts on this would be really appreciated, obviously.

It's complicated. You can't simply toss things at unmount because it might have been a bind mount and still be mounted somewhere else.

I don't think it's really even worth having an in-depth discussion of how to modify duet. I can't imagine that this would get merged as-is, or even anything resembling the current design. If you want to see duet-like functionality in the kernel, I think it needs to be integrated better and enhance or take advantage of existing mechanisms.

You've identified a real problem and a real solution, and it is in an area where Linux is weak (monitoring the page cache). If you are really interested in seeing a solution that folks can use, I think you need to find some way to leverage existing kernel functionality (ftrace, fanotify, netlink, etc...), or come up with a much more compelling story about why you can't use them.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#7 lore raw
Quoted 10 lines · Dave Hansen

What's to stop you from using tracing to gather and transport data out of the kernel and then aggregate and present it to apps in an "elegant" way of your choosing?

I don't think it's really even worth having an in-depth discussion of how to modify duet. I can't imagine that this would get merged as-is, or even anything resembling the current design. If you want to see duet-like functionality in the kernel, I think it needs to be integrated better and enhance or take advantage of existing mechanisms.

Quoted 6 lines

You've identified a real problem and a real solution, and it is in an area where Linux is weak (monitoring the page cache). If you are really interested in seeing a solution that folks can use, I think you need to find some way to leverage existing kernel functionality (ftrace, fanotify, netlink, etc...), or come up with a much more compelling story about why you can't use them.

I took a few measurements of the ftrace overhead, and if limited to the page cache functions we're interested in, it's very reasonable. Duet does depend on exporting some data with each event, however, and tracepoints seem to be the most efficient way to do this. There are two issues, however:

(a) There are no tracepoints for page dirtying and flushing. Those would have to be added at the same place as the Duet hooks I submitted (unwrapping the page-flags.h macros) to catch those cases where pages are locked and the dirty bit is set manually.

(b) The page cache tracepoints are currently not exported symbols. If I can export those four tracepoints for page addition, removal, dirtying, and flushing, then the rest of the work (exporting the information to userspace) can be carried out within a module. In the future, once we reach a point of maturity where we are confident about the stability of the exporting interface and performance, we could engage in another conversation about potentially mainlining some of that code.

Dave, I can produce a patch that adds the extra two tracepoints and exports all four tracepoint symbols. This would be a short patch that would just extend existing tracing functionality. What do you think?

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

#8 lore raw
Quoted 3 lines · George Amvrosiadis

Dave, I can produce a patch that adds the extra two tracepoints and exports all four tracepoint symbols. This would be a short patch that would just extend existing tracing functionality. What do you think?

Adding those tracepoints is probably useful. It's probably something we need to have anyway as long as they don't cause too much code bloat or a noticeable performance impact when they're off.

As for exporting symbols, that's not done until something is merged.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>