Skip to contentSkip to conversation

Memory management livelock

PATCH In review Mikulas Patocka 12 participants 67 messages Sep 22, 2008 – Oct 21, 2008 1 message not in the archive

Subsystems (6)
lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw

PATCH 1/1 Memory management livelock

Hi

Here is a patch for MM livelock. The original bug report follows after the patch. To reproduce the bug on my computer, I had to change bs=4M to bs=65536 in examples in the original report.

Mikulas

---

Fix starvation in memory management.

The bug happens when one process is doing sequential buffered writes to a block device (or file) and another process is attempting to execute sync(), fsync() or direct-IO on that device (or file). This syncing process will wait indefinitelly, until the first writing process finishes.

For example, run these two commands:
dd if=/dev/zero of=/dev/sda1 bs=65536 &
dd if=/dev/sda1 of=/dev/null bs=4096 count=1 iflag=direct

The bug is caused by sequential walking of address space in write_cache_pages and wait_on_page_writeback_range: if some other process is constantly making dirty and writeback pages while these functions run, the functions will wait on every new page, resulting in indefinite wait.

To fix the starvation, I declared a mutex starvation_barrier in struct address_space. When the mutex is taken, anyone making dirty pages on that address space should stop. The functions that walk address space sequentially first estimate a number of pages to process. If they process more than this amount (plus some small delta), it means that someone is making dirty pages under them --- they take the mutex and hold it until they finish. When the mutex is taken, the function balance_dirty_pages will wait and not allow more dirty pages being made.

The mutex is not really used as a mutex, it does not prevent access to any critical section. It is used as a barrier that blocks new dirty pages from being created. I use mutex and not wait queue to make sure that the starvation can't happend the other way (if there were wait queue, excessive calls to write_cache_pages and wait_on_page_writeback_range would block balance_dirty_pages forever; with mutex it is guaranteed that every process eventually makes progress).

The essential property of this patch is that if the starvation doesn't happen, no additional locks are taken and no atomic operations are performed. So the patch shouldn't damage performance.

The indefinite starvation was observed in write_cache_pages and wait_on_page_writeback_range. Another possibility where it could happen is invalidate_inode_pages2_range.

There are two more functions that walk all the pages in address space, but I think they don't need this starvation protection:
truncate_inode_pages_range: it is called with i_mutex locked, so no new pages are created under it.
__invalidate_mapping_pages: it skips locked, dirty and writeback pages, so there's no point in protecting the function against starving on them.

---
 fs/inode.c          |    1 +
 include/linux/fs.h  |    1 +
 mm/filemap.c        |   16 ++++++++++++++++
 mm/page-writeback.c |   30 +++++++++++++++++++++++++++++-
 mm/swap_state.c     |    1 +
 mm/truncate.c       |   20 +++++++++++++++++++-
 6 files changed, 67 insertions(+), 2 deletions(-)
fs/inode.c +1 -0
Index: linux-2.6.27-rc7-devel/fs/inode.c
===================================================================
@@ -214,6 +214,7 @@ void inode_init_once(struct inode *inode
 	spin_lock_init(&inode->i_data.i_mmap_lock);
 	INIT_LIST_HEAD(&inode->i_data.private_list);
 	spin_lock_init(&inode->i_data.private_lock);
+	mutex_init(&inode->i_data.starvation_barrier);
 	INIT_RAW_PRIO_TREE_ROOT(&inode->i_data.i_mmap);
 	INIT_LIST_HEAD(&inode->i_data.i_mmap_nonlinear);
 	i_size_ordered_init(inode);
include/linux/fs.h +1 -0
Index: linux-2.6.27-rc7-devel/include/linux/fs.h
===================================================================
@@ -539,6 +539,7 @@ struct address_space {
 	spinlock_t		private_lock;	/* for use by the address_space */
 	struct list_head	private_list;	/* ditto */
 	struct address_space	*assoc_mapping;	/* ditto */
+	struct mutex		starvation_barrier;	/* taken when fsync starves */
 } __attribute__((aligned(sizeof(long))));
 	/*
 	 * On most architectures that alignment is already the case; but
mm/filemap.c +16 -0
Index: linux-2.6.27-rc7-devel/mm/filemap.c
===================================================================
@@ -269,10 +269,19 @@ int wait_on_page_writeback_range(struct 
 	int nr_pages;
 	int ret = 0;
 	pgoff_t index;
+	long pages_to_process;
 
 	if (end < start)
 		return 0;
 
+	/*
+	 * Estimate the number of pages to process. If we process significantly
+	 * more than this, someone is making writeback pages under us.
+	 * We must pull the anti-starvation plug.
+	 */
+	pages_to_process = bdi_stat(mapping->backing_dev_info, BDI_WRITEBACK);
+	pages_to_process += pages_to_process >> 3;
+
 	pagevec_init(&pvec, 0);
 	index = start;
 	while ((index <= end) &&
@@ -288,6 +297,10 @@ int wait_on_page_writeback_range(struct 
 			if (page->index > end)
 				continue;
 
+			if (pages_to_process >= 0)
+				if (!pages_to_process--)
+					mutex_lock(&mapping->starvation_barrier);
+
 			wait_on_page_writeback(page);
 			if (PageError(page))
 				ret = -EIO;
@@ -296,6 +309,9 @@ int wait_on_page_writeback_range(struct 
 		cond_resched();
 	}
 
+	if (pages_to_process < 0)
+		mutex_unlock(&mapping->starvation_barrier);
+
 	/* Check for outstanding write errors */
 	if (test_and_clear_bit(AS_ENOSPC, &mapping->flags))
 		ret = -ENOSPC;
mm/page-writeback.c +29 -1
Index: linux-2.6.27-rc7-devel/mm/page-writeback.c
===================================================================
@@ -435,6 +435,15 @@ static void balance_dirty_pages(struct a
 
 	struct backing_dev_info *bdi = mapping->backing_dev_info;
 
+	/*
+	 * If there is sync() starving on this address space, block
+	 * writers until it finishes.
+	 */
+	if (unlikely(mutex_is_locked(&mapping->starvation_barrier))) {
+		mutex_lock(&mapping->starvation_barrier);
+		mutex_unlock(&mapping->starvation_barrier);
+	}
+
 	for (;;) {
 		struct writeback_control wbc = {
 			.bdi		= bdi,
@@ -876,12 +885,21 @@ int write_cache_pages(struct address_spa
 	pgoff_t end;		/* Inclusive */
 	int scanned = 0;
 	int range_whole = 0;
+	long pages_to_process;
 
 	if (wbc->nonblocking && bdi_write_congested(bdi)) {
 		wbc->encountered_congestion = 1;
 		return 0;
 	}
 
+	/*
+	 * Estimate the number of pages to process. If we process significantly
+	 * more than this, someone is making dirty pages under us.
+	 * Pull the anti-starvation plug to stop him.
+	 */
+	pages_to_process = bdi_stat(mapping->backing_dev_info, BDI_RECLAIMABLE);
+	pages_to_process += pages_to_process >> 3;
+
 	pagevec_init(&pvec, 0);
 	if (wbc->range_cyclic) {
 		index = mapping->writeback_index; /* Start from prev offset */
@@ -902,7 +920,13 @@ retry:
 
 		scanned = 1;
 		for (i = 0; i < nr_pages; i++) {
-			struct page *page = pvec.pages[i];
+			struct page *page;
+
+			if (pages_to_process >= 0)
+				if (!pages_to_process--)
+					mutex_lock(&mapping->starvation_barrier);
+
+			page = pvec.pages[i];
 
 			/*
 			 * At this point we hold neither mapping->tree_lock nor
@@ -958,6 +982,10 @@ retry:
 		index = 0;
 		goto retry;
 	}
+
+	if (pages_to_process < 0)
+		mutex_unlock(&mapping->starvation_barrier);
+
 	if (wbc->range_cyclic || (range_whole && wbc->nr_to_write > 0))
 		mapping->writeback_index = index;
 
mm/swap_state.c +1 -0
Index: linux-2.6.27-rc7-devel/mm/swap_state.c
===================================================================
@@ -43,6 +43,7 @@ struct address_space swapper_space = {
 	.a_ops		= &swap_aops,
 	.i_mmap_nonlinear = LIST_HEAD_INIT(swapper_space.i_mmap_nonlinear),
 	.backing_dev_info = &swap_backing_dev_info,
+	.starvation_barrier = __MUTEX_INITIALIZER(swapper_space.starvation_barrier),
 };
 
 #define INC_CACHE_INFO(x)	do { swap_cache_info.x++; } while (0)
mm/truncate.c +19 -1
Index: linux-2.6.27-rc7-devel/mm/truncate.c
===================================================================
@@ -392,6 +392,14 @@ int invalidate_inode_pages2_range(struct
 	int ret2 = 0;
 	int did_range_unmap = 0;
 	int wrapped = 0;
+	long pages_to_process;
+
+	/*
+	 * Estimate number of pages to process. If we process more, someone
+	 * is making pages under us.
+	 */
+	pages_to_process = mapping->nrpages;
+	pages_to_process += pages_to_process >> 3;
 
 	pagevec_init(&pvec, 0);
 	next = start;
@@ -399,9 +407,15 @@ int invalidate_inode_pages2_range(struct
 		pagevec_lookup(&pvec, mapping, next,
 			min(end - next, (pgoff_t)PAGEVEC_SIZE - 1) + 1)) {
 		for (i = 0; i < pagevec_count(&pvec); i++) {
-			struct page *page = pvec.pages[i];
+			struct page *page;
 			pgoff_t page_index;
 
+			if (pages_to_process >= 0)
+				if (!pages_to_process--)
+					mutex_lock(&mapping->starvation_barrier);
+
+			page = pvec.pages[i];
+
 			lock_page(page);
 			if (page->mapping != mapping) {
 				unlock_page(page);
@@ -449,6 +463,10 @@ int invalidate_inode_pages2_range(struct
 		pagevec_release(&pvec);
 		cond_resched();
 	}
+
+	if (pages_to_process < 0)
+		mutex_unlock(&mapping->starvation_barrier);
+
 	return ret;
 }
 EXPORT_SYMBOL_GPL(invalidate_inode_pages2_range);
Quoted 116 lines

----- Forwarded message from Chris Webb <[email protected]> -----

Date: Thu, 11 Sep 2008 10:47:36 +0100
From: Chris Webb <[email protected]>
Subject: Unexpected behaviour with O_DIRECT affecting lvm

To reproduce:

  # dd if=/dev/zero of=/dev/scratch/a bs=4M &
  [1] 2612
  # lvm lvrename /dev/scratch/b /dev/scratch/c
  [hangs]

(Similarly for lvremote, lvcreate, etc., and it doesn't matter whether the operation is on the same VG or a different one.)

Stracing lvm, I saw

stat64("/dev/dm-7", {st_mode=S_IFBLK|0600, st_rdev=makedev(251, 7), ...}) = 0 open("/dev/dm-7", O_RDWR|O_DIRECT|O_LARGEFILE|O_NOATIME) = 6 fstat64(6, {st_mode=S_IFBLK|0600, st_rdev=makedev(251, 7), ...}) = 0
ioctl(6, BLKBSZGET, 0x89bbb30) = 0
_llseek(6, 0, [0], SEEK_SET) = 0
read(6,
[hangs]

If I kill the dd at this point, the lvm unblocks and continues as normal:

read(6, "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"..., 4096) = 4096
close(6) = 0
stat64("/dev/dm-8", {st_mode=S_IFBLK|0600, st_rdev=makedev(251, 8), ...}) = 0 stat64("/dev/dm-8", {st_mode=S_IFBLK|0600, st_rdev=makedev(251, 8), ...}) = 0 open("/dev/dm-8", O_RDWR|O_DIRECT|O_LARGEFILE|O_NOATIME) = 6
[etc]

/dev/dm-7 is the dm device corresponding to /dev/disk.1/0.0 which is being written to.

I wrote a tiny test program which does a single O_DIRECT read of 4096 bytes from a device, and can confirm that, more generally, an O_DIRECT read from a device being continuously written to always hangs indefinitely. This occurs even if I ionice -c3 the dd, and ionice -c1 -n0 the O_DIRECT reader...

  # dd if=/dev/zero of=/dev/disk.1/0.0 bs=4M &
  [1] 2697
  # ~/tmp/readtest
  [hangs]
  # ionice -c3 dd if=/dev/zero of=/dev/disk.1/0.0 bs=4M &
  [1] 2734
  # ionice -c1 -n0 ~/tmp/readtest
  [hangs]

There's no problem if the dd is in the other direction, reading continuously from the LV, nor if the test read isn't O_DIRECT. Attempting to kill -9 the O_DIRECT reader doesn't succeed until after the read() returns.

Finally, I've tried replacing the LV with a raw disk /dev/sdb, and the same behaviour appears there for all choices of IO scheduler for the disk, so it's neither device mapper specific nor even IO scheduler specific! This means that it isn't in any sense a bug in your code, of course, but given that the phenomenon seems to block any LVM management operation when heavy writes are going on, surely we can't be the first people to hit this whilst using the LVM tool. I'm wondering whether you've had other similar reports or have any other suggestions?

For what it's worth, these tests were initially done on our dev machine which is running lvm 2.02.38 and a kernel from the head of Linus' tree (usually no more than a couple of days old with a queue of my local patches that Ed hasn't integrated into the upstream ata-over-ethernet drivers yet), but the same behaviour appears on my totally standard desktop machine with much older 2.6.25 and 2.6.24.4 kernels 'as released', so I think it's pretty long-standing.

Best wishes,

Chris.

#define _GNU_SOURCE
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define BLOCK 4096

int main(int argc, char **argv) {
int fd, n;
char *buffer;

  if (argc != 2) {
    fprintf(stderr, "Usage: %s FILE\n", argv[0]);
    return 1;
  }

  buffer = valloc(BLOCK);
  if (!buffer) {
    perror("valloc");
    return 1;
  }

  fd = open(argv[1], O_RDONLY | O_LARGEFILE | O_DIRECT);
  if (fd < 0) {
    perror("open");
    return 1;
  }

  if (pread(fd, buffer, BLOCK, 0) < 0)
    perror("pread");

close(fd);
return 0;
}

maintainer
#2 lore raw
Quoted 10 lines · On Mon, 22 Sep 2008 17:10:04 -0400 (EDT) Mikulas Patocka <[email protected]>…

The bug happens when one process is doing sequential buffered writes to a block device (or file) and another process is attempting to execute sync(), fsync() or direct-IO on that device (or file). This syncing process will wait indefinitelly, until the first writing process finishes.

For example, run these two commands:
dd if=/dev/zero of=/dev/sda1 bs=65536 &
dd if=/dev/sda1 of=/dev/null bs=4096 count=1 iflag=direct

Quoted 5 lines

The bug is caused by sequential walking of address space in write_cache_pages and wait_on_page_writeback_range: if some other process is constantly making dirty and writeback pages while these functions run, the functions will wait on every new page, resulting in indefinite wait.

Shouldn't happen. All the data-syncing functions should have an upper bound on the number of pages which they attempt to write. In the example above, we end up in here:

int __filemap_fdatawrite_range(struct address_space *mapping, loff_t start,
loff_t end, int sync_mode)

{
	int ret;
	struct writeback_control wbc = {
		.sync_mode = sync_mode,
		.nr_to_write = mapping->nrpages * 2,	<<--
		.range_start = start,
		.range_end = end,
	};

so generic_file_direct_write()'s filemap_write_and_wait() will attempt to write at most 2* the number of pages which are in cache for that inode.

I'd say that either a) that logic got broken or b) you didn't wait long enough, and we might need to do something to make it not wait so long.

But before we patch anything we should fully understand what is happening and why the current anti-livelock code isn't working in this case.

#3 lore raw
In reply to Mikulas Patocka
Quoted 35 lines
Quoted 10 lines · On Mon, 22 Sep 2008 17:10:04 -0400 (EDT) Mikulas Patocka <mpatocka@xxxxxxxxxx>…

The bug happens when one process is doing sequential buffered writes to a block device (or file) and another process is attempting to execute sync(), fsync() or direct-IO on that device (or file). This syncing process will wait indefinitelly, until the first writing process finishes.

For example, run these two commands:
dd if=/dev/zero of=/dev/sda1 bs=65536 &
dd if=/dev/sda1 of=/dev/null bs=4096 count=1 iflag=direct

Quoted 5 lines

The bug is caused by sequential walking of address space in write_cache_pages and wait_on_page_writeback_range: if some other process is constantly making dirty and writeback pages while these functions run, the functions will wait on every new page, resulting in indefinite wait.

Shouldn't happen. All the data-syncing functions should have an upper bound on the number of pages which they attempt to write. In the example above, we end up in here:

int __filemap_fdatawrite_range(struct address_space *mapping, loff_t start,
loff_t end, int sync_mode)
{
int ret;
struct writeback_control wbc = {
.sync_mode = sync_mode,
.nr_to_write = mapping->nrpages * 2, <<--
.range_start = start,
.range_end = end,
};

Quoted 2 lines

so generic_file_direct_write()'s filemap_write_and_wait() will attempt to write at most 2* the number of pages which are in cache for that inode.

See write_cache_pages:

if (wbc->sync_mode != WB_SYNC_NONE)

        wait_on_page_writeback(page);	(1)
if (PageWriteback(page) ||
    !clear_page_dirty_for_io(page)) {
        unlock_page(page);		(2)
        continue;
}
ret = (*writepage)(page, wbc, data);
if (unlikely(ret == AOP_WRITEPAGE_ACTIVATE)) {
        unlock_page(page);
        ret = 0;
}
if (ret || (--(wbc->nr_to_write) <= 0))
        done = 1;

--- so if it goes by points (1) and (2), the counter is not decremented, yet the function waits for the page. If there is constant stream of writeback pages being generated, it waits on each on them --- that is, forever. I have seen livelock in this function. For you that example with two dd's, one buffered write and the other directIO read doesn't work? For me it livelocks here.

wait_on_page_writeback_range is another example where the livelock happened, there is no protection at all against starvation.

BTW. that .nr_to_write = mapping->nrpages * 2 looks like a dangerous thing to me.

Imagine this case: You have two pages with indices 4 and 5 dirty in a file. You call fsync(). It sets nr_to_write to 4.

Meanwhile, another process makes pages 0, 1, 2, 3 dirty.

The fsync() process goes to write_cache_pages, writes the first 4 dirty pages and exits because it goes over the limit.

result --- you violate fsync() semantics, pages that were dirty before call to fsync() are not written when fsync() exits.

Quoted 6 lines

I'd say that either a) that logic got broken or b) you didn't wait long enough, and we might need to do something to make it not wait so long.

But before we patch anything we should fully understand what is happening and why the current anti-livelock code isn't working in this case.

Mikulas

maintainer
#4 lore raw
Quoted 62 lines · On Tue, 23 Sep 2008 18:34:20 -0400 (EDT) Mikulas Patocka <[email protected]>…
Quoted 35 lines
Quoted 10 lines · On Mon, 22 Sep 2008 17:10:04 -0400 (EDT) Mikulas Patocka <mpatocka@xxxxxxxxxx>…

The bug happens when one process is doing sequential buffered writes to a block device (or file) and another process is attempting to execute sync(), fsync() or direct-IO on that device (or file). This syncing process will wait indefinitelly, until the first writing process finishes.

For example, run these two commands:
dd if=/dev/zero of=/dev/sda1 bs=65536 &
dd if=/dev/sda1 of=/dev/null bs=4096 count=1 iflag=direct

Quoted 5 lines

The bug is caused by sequential walking of address space in write_cache_pages and wait_on_page_writeback_range: if some other process is constantly making dirty and writeback pages while these functions run, the functions will wait on every new page, resulting in indefinite wait.

Shouldn't happen. All the data-syncing functions should have an upper bound on the number of pages which they attempt to write. In the example above, we end up in here:

int __filemap_fdatawrite_range(struct address_space *mapping, loff_t start,
loff_t end, int sync_mode)
{
int ret;
struct writeback_control wbc = {
.sync_mode = sync_mode,
.nr_to_write = mapping->nrpages * 2, <<--
.range_start = start,
.range_end = end,
};

Quoted 2 lines

so generic_file_direct_write()'s filemap_write_and_wait() will attempt to write at most 2* the number of pages which are in cache for that inode.

See write_cache_pages:

if (wbc->sync_mode != WB_SYNC_NONE)

        wait_on_page_writeback(page);	(1)
if (PageWriteback(page) ||
    !clear_page_dirty_for_io(page)) {
        unlock_page(page);		(2)
        continue;
}
ret = (*writepage)(page, wbc, data);
if (unlikely(ret == AOP_WRITEPAGE_ACTIVATE)) {
        unlock_page(page);
        ret = 0;
}
if (ret || (--(wbc->nr_to_write) <= 0))
        done = 1;

--- so if it goes by points (1) and (2), the counter is not decremented, yet the function waits for the page. If there is constant stream of writeback pages being generated, it waits on each on them --- that is, forever. I have seen livelock in this function. For you that example with two dd's, one buffered write and the other directIO read doesn't work? For me it livelocks here.

Quoted 2 lines

wait_on_page_writeback_range is another example where the livelock happened, there is no protection at all against starvation.

um, OK. So someone else is initiating IO for this inode and this thread *never* gets to initiate any writeback. That's a bit of a surprise.

How do we fix that? Maybe decrement nt_to_write for these pages as well?

Quoted 7 lines

BTW. that .nr_to_write = mapping->nrpages * 2 looks like a dangerous thing to me.

Imagine this case: You have two pages with indices 4 and 5 dirty in a file. You call fsync(). It sets nr_to_write to 4.

Quoted 7 lines

Meanwhile, another process makes pages 0, 1, 2, 3 dirty.

The fsync() process goes to write_cache_pages, writes the first 4 dirty pages and exits because it goes over the limit.

result --- you violate fsync() semantics, pages that were dirty before call to fsync() are not written when fsync() exits.

yup, that's pretty much unfixable, really, unless new locks are added which block threads which are writing to unrelated sections of the file, and that could hurt some workloads quite a lot, I expect.

Hopefully high performance applications are instantiating the file up-front and are using sync_file_range() to prevent these sorts of things from happening. But they probably aren't.

#5 lore raw
Quoted 68 lines · Andrew Morton
Quoted 62 lines · On Tue, 23 Sep 2008 18:34:20 -0400 (EDT) Mikulas Patocka <[email protected]>…
Quoted 35 lines
Quoted 10 lines · On Mon, 22 Sep 2008 17:10:04 -0400 (EDT) Mikulas Patocka <mpatocka@xxxxxxxxxx>…

The bug happens when one process is doing sequential buffered writes to a block device (or file) and another process is attempting to execute sync(), fsync() or direct-IO on that device (or file). This syncing process will wait indefinitelly, until the first writing process finishes.

For example, run these two commands:
dd if=/dev/zero of=/dev/sda1 bs=65536 &
dd if=/dev/sda1 of=/dev/null bs=4096 count=1 iflag=direct

Quoted 5 lines

The bug is caused by sequential walking of address space in write_cache_pages and wait_on_page_writeback_range: if some other process is constantly making dirty and writeback pages while these functions run, the functions will wait on every new page, resulting in indefinite wait.

Shouldn't happen. All the data-syncing functions should have an upper bound on the number of pages which they attempt to write. In the example above, we end up in here:

int __filemap_fdatawrite_range(struct address_space *mapping, loff_t start,
loff_t end, int sync_mode)
{
int ret;
struct writeback_control wbc = {
.sync_mode = sync_mode,
.nr_to_write = mapping->nrpages * 2, <<--
.range_start = start,
.range_end = end,
};

Quoted 2 lines

so generic_file_direct_write()'s filemap_write_and_wait() will attempt to write at most 2* the number of pages which are in cache for that inode.

See write_cache_pages:

if (wbc->sync_mode != WB_SYNC_NONE)

        wait_on_page_writeback(page);	(1)
if (PageWriteback(page) ||
    !clear_page_dirty_for_io(page)) {
        unlock_page(page);		(2)
        continue;
}
ret = (*writepage)(page, wbc, data);
if (unlikely(ret == AOP_WRITEPAGE_ACTIVATE)) {
        unlock_page(page);
        ret = 0;
}
if (ret || (--(wbc->nr_to_write) <= 0))
        done = 1;

--- so if it goes by points (1) and (2), the counter is not decremented, yet the function waits for the page. If there is constant stream of writeback pages being generated, it waits on each on them --- that is, forever. I have seen livelock in this function. For you that example with two dd's, one buffered write and the other directIO read doesn't work? For me it livelocks here.

Quoted 2 lines

wait_on_page_writeback_range is another example where the livelock happened, there is no protection at all against starvation.

Quoted 6 lines

um, OK. So someone else is initiating IO for this inode and this thread *never* gets to initiate any writeback. That's a bit of a surprise.

How do we fix that? Maybe decrement nt_to_write for these pages as well?

And what do you want to do with wait_on_page_writeback_range? When I solved that livelock in write_cache_pages(), I got another livelock in wait_on_page_writeback_range.

Quoted 11 lines
Quoted 11 lines

BTW. that .nr_to_write = mapping->nrpages * 2 looks like a dangerous thing to me.

Imagine this case: You have two pages with indices 4 and 5 dirty in a file. You call fsync(). It sets nr_to_write to 4.

Meanwhile, another process makes pages 0, 1, 2, 3 dirty.

The fsync() process goes to write_cache_pages, writes the first 4 dirty pages and exits because it goes over the limit.

Quoted 6 lines
Quoted 2 lines

result --- you violate fsync() semantics, pages that were dirty before call to fsync() are not written when fsync() exits.

yup, that's pretty much unfixable, really, unless new locks are added which block threads which are writing to unrelated sections of the file, and that could hurt some workloads quite a lot, I expect.

It is fixable with the patch I sent --- it doesn't take any locks unless the starvation happens. Then, you don't have to use .nr_to_write for fsync anymore.

Another solution could be to record in page structure jiffies when the page entered dirty state and writeback state. The start writeback/wait on writeback functions could then trivially ignore pages that were dirtied/writebacked while the function was in progress.

Quoted 3 lines

Hopefully high performance applications are instantiating the file up-front and are using sync_file_range() to prevent these sorts of things from happening. But they probably aren't.

--- for databases it is pretty much possible that one thread is writing already journaled data (so it doesn't care when the data are really written) and another thread is calling fsync() on the same inode simultaneously --- so fsync() could mistakenly write the data generated by the first thread and ignore the data generated by the second thread, that it should really write.

Mikulas

maintainer
#6 lore raw
Quoted 5 lines · On Tue, 23 Sep 2008 19:11:51 -0400 (EDT) Mikulas Patocka <[email protected]>…
Quoted 5 lines
Quoted 4 lines

wait_on_page_writeback_range is another example where the livelock happened, there is no protection at all against starvation.

Quoted 8 lines
Quoted 6 lines

um, OK. So someone else is initiating IO for this inode and this thread *never* gets to initiate any writeback. That's a bit of a surprise.

How do we fix that? Maybe decrement nt_to_write for these pages as well?

And what do you want to do with wait_on_page_writeback_range?

Don't know. I was asking you.

Quoted 18 lines

When I
solved that livelock in write_cache_pages(), I got another livelock in wait_on_page_writeback_range.

Quoted 14 lines
Quoted 13 lines

BTW. that .nr_to_write = mapping->nrpages * 2 looks like a dangerous thing to me.

Imagine this case: You have two pages with indices 4 and 5 dirty in a file. You call fsync(). It sets nr_to_write to 4.

Meanwhile, another process makes pages 0, 1, 2, 3 dirty.

The fsync() process goes to write_cache_pages, writes the first 4 dirty pages and exits because it goes over the limit.

result --- you violate fsync() semantics, pages that were dirty before call to fsync() are not written when fsync() exits.

Quoted 7 lines
Quoted 3 lines

yup, that's pretty much unfixable, really, unless new locks are added which block threads which are writing to unrelated sections of the file, and that could hurt some workloads quite a lot, I expect.

It is fixable with the patch I sent --- it doesn't take any locks unless the starvation happens. Then, you don't have to use .nr_to_write for fsync anymore.

I agree that the patch is low-impact and relatively straightforward. The main problem is making the address_space larger - there can (and often are) millions and millions of these things in memory. Making it larger is a big deal. We should work hard to seek an alternative and afacit that isn't happening here.

We already have existing code and design which attempts to avoid livelock without adding stuff to the address_space. Can it be modified so as to patch up this quite obscure and rarely-occuring problem?

Quoted 17 lines

Another solution could be to record in page structure jiffies when the page entered dirty state and writeback state. The start writeback/wait on writeback functions could then trivially ignore pages that were dirtied/writebacked while the function was in progress.

Quoted 3 lines

Hopefully high performance applications are instantiating the file up-front and are using sync_file_range() to prevent these sorts of things from happening. But they probably aren't.

--- for databases it is pretty much possible that one thread is writing already journaled data (so it doesn't care when the data are really written) and another thread is calling fsync() on the same inode simultaneously --- so fsync() could mistakenly write the data generated by the first thread and ignore the data generated by the second thread, that it should really write.

Mikulas

#7 lore raw
Quoted 14 lines
Quoted 7 lines
Quoted 3 lines

yup, that's pretty much unfixable, really, unless new locks are added which block threads which are writing to unrelated sections of the file, and that could hurt some workloads quite a lot, I expect.

It is fixable with the patch I sent --- it doesn't take any locks unless the starvation happens. Then, you don't have to use .nr_to_write for fsync anymore.

I agree that the patch is low-impact and relatively straightforward. The main problem is making the address_space larger - there can (and often are) millions and millions of these things in memory. Making it larger is a big deal. We should work hard to seek an alternative and afacit that isn't happening here.

Quoted 3 lines

We already have existing code and design which attempts to avoid livelock without adding stuff to the address_space. Can it be modified so as to patch up this quite obscure and rarely-occuring problem?

I reworked my patch to use a bit in address_space->flags and hashes wait queues, so it doesn't take any extra memory. I'm sending it in three parts.
1 - make generic function wait_action_schedule
2 - fix the livelock, the logic is exactly the same as in my previous patch, wait_on_bit_lock is used instead of mutexes
3 - remove that nr_pages * 2 limit, because it causes misbehavior and possible data loss.

Mikulas

#8 lore raw

PATCH 1/3 Memory management livelock

In reply to Andrew Morton

A generic function wait_action_schedule that allows to use wait_on_bit_lock just like mutexes.

---
 include/linux/wait.h |    8 +++++++-
 kernel/wait.c        |    7 +++++++
 2 files changed, 14 insertions(+), 1 deletion(-)
include/linux/wait.h +7 -1
Index: linux-2.6.27-rc7-devel/include/linux/wait.h
===================================================================
@@ -513,7 +513,13 @@ static inline int wait_on_bit_lock(void 
 		return 0;
 	return out_of_line_wait_on_bit_lock(word, bit, action, mode);
 }
-	
+
+/**
+ * wait_action_schedule - this function can be passed to wait_on_bit or
+ * wait_on_bit_lock and it will call just schedule().
+ */
+int wait_action_schedule(void *);
+
 #endif /* __KERNEL__ */
 
 #endif
kernel/wait.c +7 -0
Index: linux-2.6.27-rc7-devel/kernel/wait.c
===================================================================
@@ -251,3 +251,10 @@ wait_queue_head_t *bit_waitqueue(void *w
 	return &zone->wait_table[hash_long(val, zone->wait_table_bits)];
 }
 EXPORT_SYMBOL(bit_waitqueue);
+
+int wait_action_schedule(void *word)
+{
+	schedule();
+	return 0;
+}
+EXPORT_SYMBOL(wait_action_schedule);
#9 lore raw

PATCH 2/3 Memory management livelock

In reply to Andrew Morton

Avoid starvation when walking address space.

---
 include/linux/pagemap.h |    1 +
 mm/filemap.c            |   20 ++++++++++++++++++++
 mm/page-writeback.c     |   37 ++++++++++++++++++++++++++++++++++++-
 mm/truncate.c           |   24 +++++++++++++++++++++++-
 4 files changed, 80 insertions(+), 2 deletions(-)
include/linux/pagemap.h +1 -0
Index: linux-2.6.27-rc7-devel/include/linux/pagemap.h
===================================================================
@@ -21,6 +21,7 @@
 #define	AS_EIO		(__GFP_BITS_SHIFT + 0)	/* IO error on async write */
 #define AS_ENOSPC	(__GFP_BITS_SHIFT + 1)	/* ENOSPC on async write */
 #define AS_MM_ALL_LOCKS	(__GFP_BITS_SHIFT + 2)	/* under mm_take_all_locks() */
+#define AS_STARVATION	(__GFP_BITS_SHIFT + 3)	/* an anti-starvation barrier */
 
 static inline void mapping_set_error(struct address_space *mapping, int error)
 {
mm/filemap.c +20 -0
Index: linux-2.6.27-rc7-devel/mm/filemap.c
===================================================================
@@ -269,10 +269,19 @@ int wait_on_page_writeback_range(struct 
 	int nr_pages;
 	int ret = 0;
 	pgoff_t index;
+	long pages_to_process;
 
 	if (end < start)
 		return 0;
 
+	/*
+	 * Estimate the number of pages to process. If we process significantly
+	 * more than this, someone is making writeback pages under us.
+	 * We must pull the anti-starvation plug.
+	 */
+	pages_to_process = bdi_stat(mapping->backing_dev_info, BDI_WRITEBACK);
+	pages_to_process += (pages_to_process >> 3) + 16;
+
 	pagevec_init(&pvec, 0);
 	index = start;
 	while ((index <= end) &&
@@ -288,6 +297,10 @@ int wait_on_page_writeback_range(struct 
 			if (page->index > end)
 				continue;
 
+			if (pages_to_process >= 0)
+				if (!pages_to_process--)
+					wait_on_bit_lock(&mapping->flags, AS_STARVATION, wait_action_schedule, TASK_UNINTERRUPTIBLE);
+
 			wait_on_page_writeback(page);
 			if (PageError(page))
 				ret = -EIO;
@@ -296,6 +309,13 @@ int wait_on_page_writeback_range(struct 
 		cond_resched();
 	}
 
+	if (pages_to_process < 0) {
+		smp_mb__before_clear_bit();
+		clear_bit(AS_STARVATION, &mapping->flags);
+		smp_mb__after_clear_bit();
+		wake_up_bit(&mapping->flags, AS_STARVATION);
+	}
+
 	/* Check for outstanding write errors */
 	if (test_and_clear_bit(AS_ENOSPC, &mapping->flags))
 		ret = -ENOSPC;
mm/page-writeback.c +36 -1
Index: linux-2.6.27-rc7-devel/mm/page-writeback.c
===================================================================
@@ -435,6 +435,18 @@ static void balance_dirty_pages(struct a
 
 	struct backing_dev_info *bdi = mapping->backing_dev_info;
 
+	/*
+	 * If there is sync() starving on this address space, block
+	 * writers until it finishes.
+	 */
+	if (unlikely(test_bit(AS_STARVATION, &mapping->flags))) {
+		wait_on_bit_lock(&mapping->flags, AS_STARVATION, wait_action_schedule, TASK_UNINTERRUPTIBLE);
+		smp_mb__before_clear_bit();
+		clear_bit(AS_STARVATION, &mapping->flags);
+		smp_mb__after_clear_bit();
+		wake_up_bit(&mapping->flags, AS_STARVATION);
+	}
+
 	for (;;) {
 		struct writeback_control wbc = {
 			.bdi		= bdi,
@@ -876,12 +888,21 @@ int write_cache_pages(struct address_spa
 	pgoff_t end;		/* Inclusive */
 	int scanned = 0;
 	int range_whole = 0;
+	long pages_to_process;
 
 	if (wbc->nonblocking && bdi_write_congested(bdi)) {
 		wbc->encountered_congestion = 1;
 		return 0;
 	}
 
+	/*
+	 * Estimate the number of pages to process. If we process significantly
+	 * more than this, someone is making dirty pages under us.
+	 * Pull the anti-starvation plug to stop him.
+	 */
+	pages_to_process = bdi_stat(mapping->backing_dev_info, BDI_RECLAIMABLE);
+	pages_to_process += (pages_to_process >> 3) + 16;
+
 	pagevec_init(&pvec, 0);
 	if (wbc->range_cyclic) {
 		index = mapping->writeback_index; /* Start from prev offset */
@@ -902,7 +923,13 @@ retry:
 
 		scanned = 1;
 		for (i = 0; i < nr_pages; i++) {
-			struct page *page = pvec.pages[i];
+			struct page *page;
+
+			if (pages_to_process >= 0)
+				if (!pages_to_process--)
+					wait_on_bit_lock(&mapping->flags, AS_STARVATION, wait_action_schedule, TASK_UNINTERRUPTIBLE);
+
+			page = pvec.pages[i];
 
 			/*
 			 * At this point we hold neither mapping->tree_lock nor
@@ -949,6 +976,14 @@ retry:
 		pagevec_release(&pvec);
 		cond_resched();
 	}
+
+	if (pages_to_process < 0) {
+		smp_mb__before_clear_bit();
+		clear_bit(AS_STARVATION, &mapping->flags);
+		smp_mb__after_clear_bit();
+		wake_up_bit(&mapping->flags, AS_STARVATION);
+	}
+
 	if (!scanned && !done) {
 		/*
 		 * We hit the last page and there is more work to be done: wrap
mm/truncate.c +23 -1
Index: linux-2.6.27-rc7-devel/mm/truncate.c
===================================================================
@@ -392,6 +392,14 @@ int invalidate_inode_pages2_range(struct
 	int ret2 = 0;
 	int did_range_unmap = 0;
 	int wrapped = 0;
+	long pages_to_process;
+
+	/*
+	 * Estimate number of pages to process. If we process more, someone
+	 * is making pages under us.
+	 */
+	pages_to_process = mapping->nrpages;
+	pages_to_process += (pages_to_process >> 3) + 16;
 
 	pagevec_init(&pvec, 0);
 	next = start;
@@ -399,9 +407,15 @@ int invalidate_inode_pages2_range(struct
 		pagevec_lookup(&pvec, mapping, next,
 			min(end - next, (pgoff_t)PAGEVEC_SIZE - 1) + 1)) {
 		for (i = 0; i < pagevec_count(&pvec); i++) {
-			struct page *page = pvec.pages[i];
+			struct page *page;
 			pgoff_t page_index;
 
+			if (pages_to_process >= 0)
+				if (!pages_to_process--)
+					wait_on_bit_lock(&mapping->flags, AS_STARVATION, wait_action_schedule, TASK_UNINTERRUPTIBLE);
+
+			page = pvec.pages[i];
+
 			lock_page(page);
 			if (page->mapping != mapping) {
 				unlock_page(page);
@@ -449,6 +463,14 @@ int invalidate_inode_pages2_range(struct
 		pagevec_release(&pvec);
 		cond_resched();
 	}
+
+	if (pages_to_process < 0) {
+		smp_mb__before_clear_bit();
+		clear_bit(AS_STARVATION, &mapping->flags);
+		smp_mb__after_clear_bit();
+		wake_up_bit(&mapping->flags, AS_STARVATION);
+	}
+
 	return ret;
 }
 EXPORT_SYMBOL_GPL(invalidate_inode_pages2_range);
maintainer
#10 lore raw
Quoted 2 lines

Subject: [PATCH 2/3] Memory management livelock

Please don't send multiple patches with identical titles - think up a good, unique, meaningful title for each patch.

Quoted 4 lines · On Wed, 24 Sep 2008 14:52:18 -0400 (EDT) Mikulas Patocka <[email protected]>…

Avoid starvation when walking address space.

Please include a full changelog with each iteration of each patch.

That changelog should explain the reason for playing games with bitlocks so Linus doesn't have kittens when he sees it.

Quoted 28 lines
 include/linux/pagemap.h |    1 +
 mm/filemap.c            |   20 ++++++++++++++++++++
 mm/page-writeback.c     |   37 ++++++++++++++++++++++++++++++++++++-
 mm/truncate.c           |   24 +++++++++++++++++++++++-
 4 files changed, 80 insertions(+), 2 deletions(-)

Index: linux-2.6.27-rc7-devel/include/linux/pagemap.h
===================================================================

include/linux/pagemap.h +1 -0
@@ -21,6 +21,7 @@
 #define	AS_EIO		(__GFP_BITS_SHIFT + 0)	/* IO error on async write */
 #define AS_ENOSPC	(__GFP_BITS_SHIFT + 1)	/* ENOSPC on async write */
 #define AS_MM_ALL_LOCKS	(__GFP_BITS_SHIFT + 2)	/* under mm_take_all_locks() */
+#define AS_STARVATION	(__GFP_BITS_SHIFT + 3)	/* an anti-starvation barrier */
 
 static inline void mapping_set_error(struct address_space *mapping, int error)
 {

Index: linux-2.6.27-rc7-devel/mm/filemap.c
===================================================================

mm/filemap.c +1 -0
@@ -269,10 +269,19 @@ int wait_on_page_writeback_range(struct 
 	int nr_pages;
 	int ret = 0;
 	pgoff_t index;
+	long pages_to_process;
 

mm/filemap.c int wait_on_page_writeback_range(struct · line 283

Quoted 10 lines
mm/filemap.c +7 -0
 	if (end < start)
 		return 0;
 
+	/*
+	 * Estimate the number of pages to process. If we process significantly
+	 * more than this, someone is making writeback pages under us.
+	 * We must pull the anti-starvation plug.
+	 */
+	pages_to_process = bdi_stat(mapping->backing_dev_info, BDI_WRITEBACK);
+	pages_to_process += (pages_to_process >> 3) + 16;

This sequence appears twice and it would probably be clearer to implement it in a well-commented function.

mm/filemap.c int wait_on_page_writeback_range(struct · line 302

Quoted 10 lines
mm/filemap.c +3 -0
 	pagevec_init(&pvec, 0);
 	index = start;
 	while ((index <= end) &&
@@ -288,6 +297,10 @@ int wait_on_page_writeback_range(struct 
 			if (page->index > end)
 				continue;
 
+			if (pages_to_process >= 0)
+				if (!pages_to_process--)
+					wait_on_bit_lock(&mapping->flags, AS_STARVATION, wait_action_schedule, TASK_UNINTERRUPTIBLE);

This is copied three times and perhaps also should be factored out.

Please note that an effort has been made to make mm/filemap.c look presentable in an 80-col display.

mm/filemap.c int wait_on_page_writeback_range(struct · line 317

Quoted 13 lines
mm/filemap.c +6 -0
 			wait_on_page_writeback(page);
 			if (PageError(page))
 				ret = -EIO;
@@ -296,6 +309,13 @@ int wait_on_page_writeback_range(struct 
 		cond_resched();
 	}
 
+	if (pages_to_process < 0) {
+		smp_mb__before_clear_bit();
+		clear_bit(AS_STARVATION, &mapping->flags);
+		smp_mb__after_clear_bit();
+		wake_up_bit(&mapping->flags, AS_STARVATION);
+	}

This sequence is repeated three or four times and should be pulled out into a well-commented function. That comment should explain the logic behind the use of these barriers, please.

#11 lore raw

RFC: one-bit mutexes (was: Re: [PATCH 2/3] Memory management livelock)

Hi

I removed the repeated code and create a new bit mutexes. They are space-efficient mutexes that consume only one bit. See the next 3 patches.

If you are concerned about the size of an inode, I can convert other mutexes to bit mutexes: i_mutex and inotify_mutex. I could also create bit_spinlock (one-bit spinlock that uses test_and_set_bit) and save space for address_space->tree_lock, address_space->i_mmap_lock, address_space->private_lock, inode->i_lock.

Look at it and say what you think about the idea of condensing mutexes into single bits.

Mikulas

Quoted 95 lines
Quoted 2 lines

Subject: [PATCH 2/3] Memory management livelock

Please don't send multiple patches with identical titles - think up a good, unique, meaningful title for each patch.

Quoted 4 lines · On Wed, 24 Sep 2008 14:52:18 -0400 (EDT) Mikulas Patocka <[email protected]>…

Avoid starvation when walking address space.

Please include a full changelog with each iteration of each patch.

That changelog should explain the reason for playing games with bitlocks so Linus doesn't have kittens when he sees it.

Quoted 28 lines
 include/linux/pagemap.h |    1 +
 mm/filemap.c            |   20 ++++++++++++++++++++
 mm/page-writeback.c     |   37 ++++++++++++++++++++++++++++++++++++-
 mm/truncate.c           |   24 +++++++++++++++++++++++-
 4 files changed, 80 insertions(+), 2 deletions(-)

Index: linux-2.6.27-rc7-devel/include/linux/pagemap.h
===================================================================

include/linux/pagemap.h +1 -0
@@ -21,6 +21,7 @@
 #define	AS_EIO		(__GFP_BITS_SHIFT + 0)	/* IO error on async write */
 #define AS_ENOSPC	(__GFP_BITS_SHIFT + 1)	/* ENOSPC on async write */
 #define AS_MM_ALL_LOCKS	(__GFP_BITS_SHIFT + 2)	/* under mm_take_all_locks() */
+#define AS_STARVATION	(__GFP_BITS_SHIFT + 3)	/* an anti-starvation barrier */
 
 static inline void mapping_set_error(struct address_space *mapping, int error)
 {

Index: linux-2.6.27-rc7-devel/mm/filemap.c
===================================================================

mm/filemap.c +1 -0
@@ -269,10 +269,19 @@ int wait_on_page_writeback_range(struct 
 	int nr_pages;
 	int ret = 0;
 	pgoff_t index;
+	long pages_to_process;
 

mm/filemap.c int wait_on_page_writeback_range(struct · line 283

Quoted 10 lines
mm/filemap.c +7 -0
 	if (end < start)
 		return 0;
 
+	/*
+	 * Estimate the number of pages to process. If we process significantly
+	 * more than this, someone is making writeback pages under us.
+	 * We must pull the anti-starvation plug.
+	 */
+	pages_to_process = bdi_stat(mapping->backing_dev_info, BDI_WRITEBACK);
+	pages_to_process += (pages_to_process >> 3) + 16;

This sequence appears twice and it would probably be clearer to implement it in a well-commented function.

mm/filemap.c int wait_on_page_writeback_range(struct · line 302

Quoted 10 lines
mm/filemap.c +3 -0
 	pagevec_init(&pvec, 0);
 	index = start;
 	while ((index <= end) &&
@@ -288,6 +297,10 @@ int wait_on_page_writeback_range(struct 
 			if (page->index > end)
 				continue;
 
+			if (pages_to_process >= 0)
+				if (!pages_to_process--)
+					wait_on_bit_lock(&mapping->flags, AS_STARVATION, wait_action_schedule, TASK_UNINTERRUPTIBLE);

This is copied three times and perhaps also should be factored out.

Please note that an effort has been made to make mm/filemap.c look presentable in an 80-col display.

mm/filemap.c int wait_on_page_writeback_range(struct · line 317

Quoted 13 lines
mm/filemap.c +6 -0
 			wait_on_page_writeback(page);
 			if (PageError(page))
 				ret = -EIO;
@@ -296,6 +309,13 @@ int wait_on_page_writeback_range(struct 
 		cond_resched();
 	}
 
+	if (pages_to_process < 0) {
+		smp_mb__before_clear_bit();
+		clear_bit(AS_STARVATION, &mapping->flags);
+		smp_mb__after_clear_bit();
+		wake_up_bit(&mapping->flags, AS_STARVATION);
+	}

This sequence is repeated three or four times and should be pulled out into a well-commented function. That comment should explain the logic behind the use of these barriers, please.

#12 lore raw

Re: RFC: one-bit mutexes (was: Re: [PATCH 2/3] Memory management livelock)

Quoted 4 lines · Mikulas Patocka

Hi

I removed the repeated code and create a new bit mutexes. They are space-efficient mutexes that consume only one bit. See the next 3 patches.

Pretty reasonable to have.

Quoted 2 lines

If you are concerned about the size of an inode, I can convert other mutexes to bit mutexes: i_mutex and inotify_mutex.

I wouldn't worry for now. mutexes can be unlocked much faster than bit mutexes, especially in the fastpath. And due to slab, it would be unlikely to actually save any space.

Quoted 4 lines

I could also create
bit_spinlock (one-bit spinlock that uses test_and_set_bit) and save space for address_space->tree_lock, address_space->i_mmap_lock, address_space->private_lock, inode->i_lock.

We have that already. It is much much faster to unlock spinlocks than bit spinlocks in general (if you own the word exclusively, then it's not, but then you would be less likely to save space), and we can also do proper FIFO ticket locks with a larger word.

Quoted 2 lines

Look at it and say what you think about the idea of condensing mutexes into single bits.

Looks pretty good to me.

#13 lore raw

Re: RFC: one-bit mutexes (was: Re: [PATCH 2/3] Memory management livelock)

Quoted 6 lines
Quoted 2 lines

If you are concerned about the size of an inode, I can convert other mutexes to bit mutexes: i_mutex and inotify_mutex.

I wouldn't worry for now. mutexes can be unlocked much faster than bit mutexes, especially in the fastpath. And due to slab, it would be unlikely to actually save any space.

Maybe inotify_mutex. You are right that i_mutex is so heavily contended that slowing it down to save few words wouldn't be good. Do you know about any inotify-intensive workload?

Quoted 9 lines
Quoted 4 lines

I could also create
bit_spinlock (one-bit spinlock that uses test_and_set_bit) and save space for address_space->tree_lock, address_space->i_mmap_lock, address_space->private_lock, inode->i_lock.

We have that already. It is much much faster to unlock spinlocks than bit spinlocks in general (if you own the word exclusively, then it's not, but then you would be less likely to save space), and we can also do proper FIFO ticket locks with a larger word.

BTW. why do spinlocks on x86(64) have 32 bits and not 8 bits or 16 bits? Are atomic 32-bit instuctions faster?

Can x86(86) system have 256 CPUs?

Mikulas

#14 lore raw

Re: RFC: one-bit mutexes (was: Re: [PATCH 2/3] Memory management livelock)

Quoted 10 lines · Mikulas Patocka
Quoted 6 lines
Quoted 2 lines

If you are concerned about the size of an inode, I can convert other mutexes to bit mutexes: i_mutex and inotify_mutex.

I wouldn't worry for now. mutexes can be unlocked much faster than bit mutexes, especially in the fastpath. And due to slab, it would be unlikely to actually save any space.

Maybe inotify_mutex. You are right that i_mutex is so heavily contended that slowing it down to save few words wouldn't be good. Do you know about any inotify-intensive workload?

Don't really know, no. I think most desktop environments use it to some extent, but no idea how much.

Quoted 5 lines
Quoted 5 lines
Quoted 4 lines

I could also create
bit_spinlock (one-bit spinlock that uses test_and_set_bit) and save space for address_space->tree_lock, address_space->i_mmap_lock, address_space->private_lock, inode->i_lock.

Quoted 7 lines
Quoted 4 lines

We have that already. It is much much faster to unlock spinlocks than bit spinlocks in general (if you own the word exclusively, then it's not, but then you would be less likely to save space), and we can also do proper FIFO ticket locks with a larger word.

BTW. why do spinlocks on x86(64) have 32 bits and not 8 bits or 16 bits? Are atomic 32-bit instuctions faster?

In the case of <= 256 CPUs, they could be an unsigned short I think. Probably it has never been found to be a huge win because they are often beside other ints or longs. I think I actually booted up the kernel with 16-bit spinlocks when doing the FIFO locks, but never sent a patch for it... Don't let me stop you from trying though.

Quoted 1 line

Can x86(86) system have 256 CPUs?

Well, none that I know of which actually exist. SGI is hoping to have 4096 CPU x86 systems as far as I can tell.

#15 lore raw

PATCH 1/3 bit mutexes

In reply to Andrew Morton

A bit mutex implementation.

Bit mutex is a space-efficient mutex that consumes exactly one bit in the apropriate structure (if mutex debugging is turned off). Bit mutex is implemented as a bit in unsigned long field. Other bits in the field may be used for other purposes, if test/set/clear_bit functions are used to manipulate them. There is no wait queue in the structure containing the bit mutex; hashed wait queues for waiting on bits are used.

Additional structure struct bit_mutex is needed, it contains lock debugging & dependency information. When the kernel is compiled without lock debugging, this structure is empty.

Bit mutexes are used with functions
bit_mutex_init
bit_mutex_lock
bit_mutex_unlock
bit_mutex_is_locked
These functions take 3 arguments: pointer to the unsigned long field, the bit position and pointer to struct bit_mutex.

---
 include/linux/bit-mutex.h |   98 ++++++++++++++++++++++++++++++++++++++++++++++
 include/linux/wait.h      |    8 +++
 kernel/Makefile           |    2 
 kernel/bit-mutex-debug.c  |   55 +++++++++++++++++++++++++
 kernel/wait.c             |    7 +++
 5 files changed, 169 insertions(+), 1 deletion(-)
include/linux/bit-mutex.h new file +98 -0
Index: linux-2.6.27-rc8-devel/include/linux/bit-mutex.h
===================================================================
@@ -0,0 +1,98 @@
+#ifndef __LINUX_BIT_MUTEX_H
+#define __LINUX_BIT_MUTEX_H
+
+#include <linux/bitops.h>
+#include <linux/lockdep.h>
+#include <linux/wait.h>
+#include <linux/sched.h>
+
+struct bit_mutex {
+#ifdef CONFIG_DEBUG_MUTEXES
+	unsigned long		*field;
+	int 			bit;
+	struct thread_info	*owner;
+	const char		*name;
+	void			*magic;
+#endif
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+	struct lockdep_map	dep_map;
+#endif
+};
+
+#ifndef CONFIG_DEBUG_MUTEXES
+
+static inline void bit_mutex_init(unsigned long *field, int bit, struct bit_mutex *mtx)
+{
+	clear_bit(bit, field);
+	smp_mb__after_clear_bit();
+}
+
+static inline void bit_mutex_lock(unsigned long *field, int bit, struct bit_mutex *mtx)
+{
+	wait_on_bit_lock(field, bit, wait_action_schedule, TASK_UNINTERRUPTIBLE);
+}
+
+static inline void bit_mutex_unlock(unsigned long *field, int bit, struct bit_mutex *mtx)
+{
+	smp_mb__before_clear_bit();
+	clear_bit(bit, field);
+	smp_mb__after_clear_bit();
+	wake_up_bit(field, bit);
+}
+
+static inline int bit_mutex_is_locked(unsigned long *field, int bit, struct bit_mutex *mtx)
+{
+	return test_bit(bit, field);
+}
+
+#define __DEBUG_BIT_MUTEX_INITIALIZER(field, bit, mtx)
+
+#else
+
+void __bit_mutex_init(unsigned long *field, int bit, struct bit_mutex *mtx, const char *name, struct lock_class_key *key);
+
+#define bit_mutex_init(field, bit, mtx)				\
+do {								\
+	static struct lock_class_key __key;			\
+	__bit_mutex_init(field, bit, mtx, #mtx, &__key);	\
+} while (0)
+
+void __bit_mutex_lock(unsigned long *field, int bit, struct bit_mutex *mtx, int subclass);
+
+#define bit_mutex_lock(field, bit, mtx)				\
+	__bit_mutex_lock(field, bit, mtx, 0)
+
+void __bit_mutex_unlock(unsigned long *field, int bit, struct bit_mutex *mtx, int subclass);
+
+#define bit_mutex_unlock(field, bit, mtx)			\
+	__bit_mutex_unlock(field, bit, mtx, 0)
+
+int bit_mutex_is_locked(unsigned long *field, int bit, struct bit_mutex *mtx);
+
+#define __DEBUG_BIT_MUTEX_INITIALIZER(field_, bit_, mtx)	\
+	.magic = &(mtx),					\
+	.field = (field_),					\
+	.bit = (bit_)
+
+#endif
+
+
+#ifdef CONFIG_DEBUG_LOCK_ALLOC
+
+#define __DEP_MAP_BIT_MUTEX_INITIALIZER(field, bit, mtx)	\
+	, .dep_map = { .name = #mtx }
+
+#else
+
+#define __DEP_MAP_BIT_MUTEX_INITIALIZER(field, bit, mtx)
+
+#endif
+
+
+#define __BIT_MUTEX_INITIALIZER(field, bit, mtx)		\
+	{							\
+		__DEBUG_BIT_MUTEX_INITIALIZER(field, bit, mtx)	\
+		__DEP_MAP_BIT_MUTEX_INITIALIZER(field, bit, mtx)\
+	}
+
+#endif
include/linux/wait.h +7 -1
Index: linux-2.6.27-rc8-devel/include/linux/wait.h
===================================================================
@@ -513,7 +513,13 @@ static inline int wait_on_bit_lock(void 
 		return 0;
 	return out_of_line_wait_on_bit_lock(word, bit, action, mode);
 }
-	
+
+/**
+ * wait_action_schedule - this function can be passed to wait_on_bit or
+ * wait_on_bit_lock and it will call just schedule().
+ */
+int wait_action_schedule(void *);
+
 #endif /* __KERNEL__ */
 
 #endif
kernel/wait.c +7 -0
Index: linux-2.6.27-rc8-devel/kernel/wait.c
===================================================================
@@ -251,3 +251,10 @@ wait_queue_head_t *bit_waitqueue(void *w
 	return &zone->wait_table[hash_long(val, zone->wait_table_bits)];
 }
 EXPORT_SYMBOL(bit_waitqueue);
+
+int wait_action_schedule(void *word)
+{
+	schedule();
+	return 0;
+}
+EXPORT_SYMBOL(wait_action_schedule);
kernel/Makefile +2 -0
Index: linux-2.6.27-rc8-devel/kernel/Makefile
===================================================================
@@ -17,6 +17,7 @@ ifdef CONFIG_FTRACE
 # Do not trace debug files and internal ftrace files
 CFLAGS_REMOVE_lockdep.o = -pg
 CFLAGS_REMOVE_lockdep_proc.o = -pg
+CFLAGS_REMOVE_bit-mutex-debug.o = -pg
 CFLAGS_REMOVE_mutex-debug.o = -pg
 CFLAGS_REMOVE_rtmutex-debug.o = -pg
 CFLAGS_REMOVE_cgroup-debug.o = -pg
@@ -29,6 +30,7 @@ obj-$(CONFIG_SYSCTL_SYSCALL_CHECK) += sy
 obj-$(CONFIG_STACKTRACE) += stacktrace.o
 obj-y += time/
 obj-$(CONFIG_DEBUG_MUTEXES) += mutex-debug.o
+obj-$(CONFIG_DEBUG_MUTEXES) += bit-mutex-debug.o
 obj-$(CONFIG_LOCKDEP) += lockdep.o
 ifeq ($(CONFIG_PROC_FS),y)
 obj-$(CONFIG_LOCKDEP) += lockdep_proc.o
kernel/bit-mutex-debug.c new file +55 -0

55 lines not on this page · raw message

#16 lore raw

PATCH 2/3 Fix fsync livelock

In reply to Andrew Morton

Fix starvation in memory management.

The bug happens when one process is doing sequential buffered writes to a block device (or file) and another process is attempting to execute sync(), fsync() or direct-IO on that device (or file). This syncing process will wait indefinitelly, until the first writing process finishes.

For example, run these two commands:
dd if=/dev/zero of=/dev/sda1 bs=65536 &
dd if=/dev/sda1 of=/dev/null bs=4096 count=1 iflag=direct

The bug is caused by sequential walking of address space in write_cache_pages and wait_on_page_writeback_range: if some other process is constantly making dirty and writeback pages while these functions run, the functions will wait on every new page, resulting in indefinite wait.

To fix the starvation, I declared a bit mutex starvation_barrier in struct address_space. The bit AS_STARVATION_BARRIER in address_space->flags is used for actual locking. When the mutex is taken, anyone making dirty pages on that address space should stop. The functions that walk address space sequentially first estimate a number of pages to process. If they process more than this amount (plus some small delta), it means that someone is making dirty pages under them --- they take the mutex and hold it until they finish. When the mutex is taken, the function balance_dirty_pages will wait and not allow more dirty pages being made.

The mutex is not really used as a mutex, it does not prevent access to any critical section. It is used as a barrier that blocks new dirty pages from being created. I use mutex and not wait queue to make sure that the starvation can't happend the other way (if there were wait queue, excessive calls to write_cache_pages and wait_on_page_writeback_range would block balance_dirty_pages forever; with mutex it is guaranteed that every process eventually makes progress).

The essential property of this patch is that if the starvation doesn't happen, no additional locks are taken and no atomic operations are performed. So the patch shouldn't damage performance.

The indefinite starvation was observed in write_cache_pages and wait_on_page_writeback_range. Another possibility where it could happen is invalidate_inode_pages2_range.

There are two more functions that walk all the pages in address space, but I think they don't need this starvation protection:
truncate_inode_pages_range: it is called with i_mutex locked, so no new pages are created under it.
__invalidate_mapping_pages: it skips locked, dirty and writeback pages, so there's no point in protecting the function against starving on them.

---
 fs/inode.c              |    1 +
 include/linux/fs.h      |    3 +++
 include/linux/pagemap.h |   14 ++++++++++++++
 mm/filemap.c            |    5 +++++
 mm/page-writeback.c     |   18 +++++++++++++++++-
 mm/swap_state.c         |    1 +
 mm/truncate.c           |   10 +++++++++-
 7 files changed, 50 insertions(+), 2 deletions(-)
fs/inode.c +1 -0
Index: linux-2.6.27-rc8-devel/fs/inode.c
===================================================================
@@ -216,6 +216,7 @@ void inode_init_once(struct inode *inode
 	spin_lock_init(&inode->i_data.private_lock);
 	INIT_RAW_PRIO_TREE_ROOT(&inode->i_data.i_mmap);
 	INIT_LIST_HEAD(&inode->i_data.i_mmap_nonlinear);
+	bit_mutex_init(&inode->i_data.flags, AS_STARVATION_BARRIER, &inode->i_data.starvation_barrier);
 	i_size_ordered_init(inode);
 #ifdef CONFIG_INOTIFY
 	INIT_LIST_HEAD(&inode->inotify_watches);
include/linux/fs.h +3 -0
Index: linux-2.6.27-rc8-devel/include/linux/fs.h
===================================================================
@@ -289,6 +289,7 @@ extern int dir_notify_enable;
 #include <linux/init.h>
 #include <linux/pid.h>
 #include <linux/mutex.h>
+#include <linux/bit-mutex.h>
 #include <linux/capability.h>
 #include <linux/semaphore.h>
 
@@ -539,6 +540,8 @@ struct address_space {
 	spinlock_t		private_lock;	/* for use by the address_space */
 	struct list_head	private_list;	/* ditto */
 	struct address_space	*assoc_mapping;	/* ditto */
+
+	struct bit_mutex	starvation_barrier;/* taken when fsync starves */
 } __attribute__((aligned(sizeof(long))));
 	/*
 	 * On most architectures that alignment is already the case; but
include/linux/pagemap.h +14 -0
Index: linux-2.6.27-rc8-devel/include/linux/pagemap.h
===================================================================
@@ -21,6 +21,7 @@
 #define	AS_EIO		(__GFP_BITS_SHIFT + 0)	/* IO error on async write */
 #define AS_ENOSPC	(__GFP_BITS_SHIFT + 1)	/* ENOSPC on async write */
 #define AS_MM_ALL_LOCKS	(__GFP_BITS_SHIFT + 2)	/* under mm_take_all_locks() */
+#define AS_STARVATION_BARRIER (__GFP_BITS_SHIFT + 3) /* an anti-starvation barrier */
 
 static inline void mapping_set_error(struct address_space *mapping, int error)
 {
@@ -424,4 +425,17 @@ static inline int add_to_page_cache(stru
 	return error;
 }
 
+#define starvation_protection_head(n)				\
+	long pages_to_process = (n);				\
+	pages_to_process += (pages_to_process >> 3) + 16;
+
+#define starvation_protection_step(mapping)			\
+	if (pages_to_process >= 0)				\
+		if (!pages_to_process--)			\
+			bit_mutex_lock(&(mapping)->flags, AS_STARVATION_BARRIER, &(mapping)->starvation_barrier);
+
+#define starvation_protection_end(mapping)			\
+	if (pages_to_process < 0)				\
+		bit_mutex_unlock(&(mapping)->flags, AS_STARVATION_BARRIER, &(mapping)->starvation_barrier);
+
 #endif /* _LINUX_PAGEMAP_H */
mm/filemap.c +5 -0
Index: linux-2.6.27-rc8-devel/mm/filemap.c
===================================================================
@@ -269,6 +269,7 @@ int wait_on_page_writeback_range(struct 
 	int nr_pages;
 	int ret = 0;
 	pgoff_t index;
+	starvation_protection_head(bdi_stat(mapping->backing_dev_info, BDI_WRITEBACK));
 
 	if (end < start)
 		return 0;
@@ -288,6 +289,8 @@ int wait_on_page_writeback_range(struct 
 			if (page->index > end)
 				continue;
 
+			starvation_protection_step(mapping);
+
 			wait_on_page_writeback(page);
 			if (PageError(page))
 				ret = -EIO;
@@ -296,6 +299,8 @@ int wait_on_page_writeback_range(struct 
 		cond_resched();
 	}
 
+	starvation_protection_end(mapping);
+
 	/* Check for outstanding write errors */
 	if (test_and_clear_bit(AS_ENOSPC, &mapping->flags))
 		ret = -ENOSPC;
mm/page-writeback.c +17 -1
Index: linux-2.6.27-rc8-devel/mm/page-writeback.c
===================================================================
@@ -435,6 +435,14 @@ static void balance_dirty_pages(struct a
 
 	struct backing_dev_info *bdi = mapping->backing_dev_info;
 
+	if (unlikely(bit_mutex_is_locked(&mapping->flags, AS_STARVATION_BARRIER,
+	    &mapping->starvation_barrier))) {
+		bit_mutex_lock(&mapping->flags, AS_STARVATION_BARRIER,
+			&mapping->starvation_barrier);
+		bit_mutex_unlock(&mapping->flags, AS_STARVATION_BARRIER,
+			&mapping->starvation_barrier);
+	}
+
 	for (;;) {
 		struct writeback_control wbc = {
 			.bdi		= bdi,
@@ -876,6 +884,7 @@ int write_cache_pages(struct address_spa
 	pgoff_t end;		/* Inclusive */
 	int scanned = 0;
 	int range_whole = 0;
+	starvation_protection_head(bdi_stat(mapping->backing_dev_info, BDI_RECLAIMABLE));
 
 	if (wbc->nonblocking && bdi_write_congested(bdi)) {
 		wbc->encountered_congestion = 1;
@@ -902,7 +911,11 @@ retry:
 
 		scanned = 1;
 		for (i = 0; i < nr_pages; i++) {
-			struct page *page = pvec.pages[i];
+			struct page *page;
+
+			starvation_protection_step(mapping);
+
+			page = pvec.pages[i];
 
 			/*
 			 * At this point we hold neither mapping->tree_lock nor
@@ -963,6 +976,9 @@ retry:
 
 	if (wbc->range_cont)
 		wbc->range_start = index << PAGE_CACHE_SHIFT;
+
+	starvation_protection_end(mapping);
+
 	return ret;
 }
 EXPORT_SYMBOL(write_cache_pages);
mm/swap_state.c +1 -0
Index: linux-2.6.27-rc8-devel/mm/swap_state.c
===================================================================
@@ -43,6 +43,7 @@ struct address_space swapper_space = {
 	.a_ops		= &swap_aops,
 	.i_mmap_nonlinear = LIST_HEAD_INIT(swapper_space.i_mmap_nonlinear),
 	.backing_dev_info = &swap_backing_dev_info,
+	.starvation_barrier = __BIT_MUTEX_INITIALIZER(&swapper_space.flags, AS_STARVATION_BARRIER, swapper_space.starvation_barrier),
 };
 
 #define INC_CACHE_INFO(x)	do { swap_cache_info.x++; } while (0)
mm/truncate.c +9 -1
Index: linux-2.6.27-rc8-devel/mm/truncate.c
===================================================================
@@ -392,6 +392,7 @@ int invalidate_inode_pages2_range(struct
 	int ret2 = 0;
 	int did_range_unmap = 0;
 	int wrapped = 0;
+	starvation_protection_head(mapping->nrpages);
 
 	pagevec_init(&pvec, 0);
 	next = start;
@@ -399,9 +400,13 @@ int invalidate_inode_pages2_range(struct
 		pagevec_lookup(&pvec, mapping, next,
 			min(end - next, (pgoff_t)PAGEVEC_SIZE - 1) + 1)) {
 		for (i = 0; i < pagevec_count(&pvec); i++) {
-			struct page *page = pvec.pages[i];
+			struct page *page;
 			pgoff_t page_index;
 
+			starvation_protection_step(mapping);
+
+			page = pvec.pages[i];
+
 			lock_page(page);
 			if (page->mapping != mapping) {
 				unlock_page(page);
@@ -449,6 +454,9 @@ int invalidate_inode_pages2_range(struct
 		pagevec_release(&pvec);
 		cond_resched();
 	}
+
+	starvation_protection_end(mapping);
+
 	return ret;
 }
 EXPORT_SYMBOL_GPL(invalidate_inode_pages2_range);
#17 lore raw

Re: [PATCH 2/3] Fix fsync livelock

Quoted 12 lines · On Sun, 5 Oct 2008 18:14:50 -0400 (EDT) Mikulas Patocka <[email protected]>…

Fix starvation in memory management.

The bug happens when one process is doing sequential buffered writes to a block device (or file) and another process is attempting to execute sync(), fsync() or direct-IO on that device (or file). This syncing process will wait indefinitelly, until the first writing process finishes.

For example, run these two commands:
dd if=/dev/zero of=/dev/sda1 bs=65536 &
dd if=/dev/sda1 of=/dev/null bs=4096 count=1 iflag=direct

Quoted 5 lines

The bug is caused by sequential walking of address space in write_cache_pages and wait_on_page_writeback_range: if some other process is constantly making dirty and writeback pages while these functions run, the functions will wait on every new page, resulting in indefinite wait.

are you sure?
isn't the right fix to just walk the file pages only once?

#18 lore raw

Re: [PATCH 2/3] Fix fsync livelock

Quoted 15 lines · Arjan van de Ven
Quoted 12 lines · On Sun, 5 Oct 2008 18:14:50 -0400 (EDT) Mikulas Patocka <[email protected]>…

Fix starvation in memory management.

The bug happens when one process is doing sequential buffered writes to a block device (or file) and another process is attempting to execute sync(), fsync() or direct-IO on that device (or file). This syncing process will wait indefinitelly, until the first writing process finishes.

For example, run these two commands:
dd if=/dev/zero of=/dev/sda1 bs=65536 &
dd if=/dev/sda1 of=/dev/null bs=4096 count=1 iflag=direct

Quoted 8 lines
Quoted 5 lines

The bug is caused by sequential walking of address space in write_cache_pages and wait_on_page_writeback_range: if some other process is constantly making dirty and writeback pages while these functions run, the functions will wait on every new page, resulting in indefinite wait.

are you sure?
isn't the right fix to just walk the file pages only once?

It walks the pages only once --- and waits on each on them. But because new pages are contantly appearing under it, that "walk only once" becomes infinite loop (well, finite, until the whole disk is written).

Mikulas

#19 lore raw

Re: [PATCH 2/3] Fix fsync livelock

Quoted 7 lines · On Sun, 5 Oct 2008 19:02:57 -0400 (EDT) Mikulas Patocka <[email protected]>…
Quoted 2 lines

are you sure?
isn't the right fix to just walk the file pages only once?

It walks the pages only once --- and waits on each on them. But because new pages are contantly appearing under it, that "walk only once" becomes infinite loop (well, finite, until the whole disk is written).

well. fsync() promises that everything that's dirty at the time of the call will hit the disk. That is not something you can compromise. The only way out would be is to not allow new dirty during an fsync()... which is imo even worse.

Submit them all in one go, then wait, should not be TOO bad. Unless a lot was dirty already, but then you go back to "but it has to go to disk".

Signature · 3 lines
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org
#20 lore raw

Re: [PATCH 2/3] Fix fsync livelock

Quoted 11 lines · Arjan van de Ven
Quoted 7 lines · On Sun, 5 Oct 2008 19:02:57 -0400 (EDT) Mikulas Patocka <[email protected]>…
Quoted 2 lines

are you sure?
isn't the right fix to just walk the file pages only once?

It walks the pages only once --- and waits on each on them. But because new pages are contantly appearing under it, that "walk only once" becomes infinite loop (well, finite, until the whole disk is written).

Quoted 8 lines

well. fsync() promises that everything that's dirty at the time of the call will hit the disk. That is not something you can compromise. The only way out would be is to not allow new dirty during an fsync()... which is imo even worse.

Submit them all in one go, then wait, should not be TOO bad. Unless a lot was dirty already, but then you go back to "but it has to go to disk".

The problem here is that you have two processes --- one is writing, the other is simultaneously syncing. The syncing process can't distinguish the pages that were created before fsync() was invoked (it has to wait on them) and the pages that were created while fsync() was running (it doesn't have to wait on them) --- so it waits on them all. The result is livelock, it waits indefinitely, because more and more pages are being created.

The patch changes it so that if it waits long enough, it stops the other writers creating dirty pages.

Or, how otherwise would you implement "Submit them all in one go, then wait"? The current code is:
you grab page 0, see it is under writeback, wait on it
you grab page 1, see it is under writeback, wait on it
you grab page 2, see it is under writeback, wait on it
you grab page 3, see it is under writeback, wait on it
...
--- and the other process is just making more and more writeback pages while your waiting routine run. So the waiting is indefinite.

Mikulas

#21 lore raw

Re: [PATCH 2/3] Fix fsync livelock

Quoted 9 lines · On Sun, 5 Oct 2008 19:18:22 -0400 (EDT) Mikulas Patocka <[email protected]>…

On Sun, 5 Oct 2008, Arjan van de Ven wrote:

The problem here is that you have two processes --- one is writing, the other is simultaneously syncing. The syncing process can't distinguish the pages that were created before fsync() was invoked (it has to wait on them) and the pages that were created while fsync() was running (it doesn't have to wait on them) --- so it waits on them all.

for pages it already passed that's not true.
but yes while you walk, you may find new ones. tough luck.

Quoted 7 lines

Or, how otherwise would you implement "Submit them all in one go, then wait"? The current code is:
you grab page 0, see it is under writeback, wait on it you grab page 1, see it is under writeback, wait on it you grab page 2, see it is under writeback, wait on it you grab page 3, see it is under writeback, wait on it

it shouldn't be doing this. It should be "submit the lot" "wait on the lot that got submitted".

keeping away new writers is just shifting the latency to an innocent party (since the fsync() is just bloody expensive, the person doing it should be paying the price, not the rest of the system), and a grave mistake.

If the fsync() implementation isn't smart enough, sure, lets improve it. But not by shifting latency around... lets make it more efficient at submitting IO.
If we need to invent something like "chained IO" where if you wait on the last of the chain, you wait on the entirely chain, so be it.

Signature · 3 lines
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org
#22 lore raw

Re: [PATCH 2/3] Fix fsync livelock

Quoted 23 lines · Arjan van de Ven
Quoted 9 lines · On Sun, 5 Oct 2008 19:18:22 -0400 (EDT) Mikulas Patocka <[email protected]>…

On Sun, 5 Oct 2008, Arjan van de Ven wrote:

The problem here is that you have two processes --- one is writing, the other is simultaneously syncing. The syncing process can't distinguish the pages that were created before fsync() was invoked (it has to wait on them) and the pages that were created while fsync() was running (it doesn't have to wait on them) --- so it waits on them all.

for pages it already passed that's not true.
but yes while you walk, you may find new ones. tough luck.

Quoted 7 lines

Or, how otherwise would you implement "Submit them all in one go, then wait"? The current code is:
you grab page 0, see it is under writeback, wait on it you grab page 1, see it is under writeback, wait on it you grab page 2, see it is under writeback, wait on it you grab page 3, see it is under writeback, wait on it

Quoted 2 lines

it shouldn't be doing this. It should be "submit the lot" "wait on the lot that got submitted".

And how do you want to implement that "wait on the lot that got submitted". Note that you can't allocate an array or linked list that holds pointers to all submitted pages. And if you add anything to the page structure or radix tree, you have to serialize concurrent sync,fsync calls, otherwise they'd fight over these bits.

Quoted 4 lines

keeping away new writers is just shifting the latency to an innocent party (since the fsync() is just bloody expensive, the person doing it should be paying the price, not the rest of the system), and a grave mistake.

I assume that if very few people complained about the livelock till now, very few people will see degraded write performance. My patch blocks the writes only if the livelock happens, so if the livelock doesn't happen in unpatched kernel for most people, the patch won't make it worse.

Quoted 5 lines

If the fsync() implementation isn't smart enough, sure, lets improve it. But not by shifting latency around... lets make it more efficient at submitting IO.
If we need to invent something like "chained IO" where if you wait on the last of the chain, you wait on the entirely chain, so be it.

This looks madly complicated. And ineffective, because if some page was submitted before fsync() was invoked, and is under writeback while fsync() is called, fsync() still has to wait on it.

Mikulas

#23 lore raw

Re: [PATCH 2/3] Fix fsync livelock

Quoted 5 lines · On Sun, 5 Oct 2008 20:01:46 -0400 (EDT) Mikulas Patocka <[email protected]>…

I assume that if very few people complained about the livelock till now, very few people will see degraded write performance. My patch blocks the writes only if the livelock happens, so if the livelock doesn't happen in unpatched kernel for most people, the patch won't make it worse.

I object to calling this a livelock. It's not.
And yes, fsync is slow and lots of people are seeing that. It's not helped by how ext3 is implemented (where fsync is effectively equivalent of a sync for many cases).
But again, moving the latency to "innocent" parties is not acceptable.

Quoted 10 lines
Quoted 6 lines

If the fsync() implementation isn't smart enough, sure, lets improve it. But not by shifting latency around... lets make it more efficient at submitting IO.
If we need to invent something like "chained IO" where if you wait on the last of the chain, you wait on the entirely chain, so be it.

This looks madly complicated. And ineffective, because if some page was submitted before fsync() was invoked, and is under writeback while fsync() is called, fsync() still has to wait on it.

so?
just make a chain per inode always...

Signature · 3 lines
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org
#24 lore raw

Re: [PATCH 2/3] Fix fsync livelock

Quoted 10 lines · Arjan van de Ven
Quoted 5 lines · On Sun, 5 Oct 2008 20:01:46 -0400 (EDT) Mikulas Patocka <[email protected]>…

I assume that if very few people complained about the livelock till now, very few people will see degraded write performance. My patch blocks the writes only if the livelock happens, so if the livelock doesn't happen in unpatched kernel for most people, the patch won't make it worse.

I object to calling this a livelock. It's not.

It unlocks itself when the whole disk is written, and it can be several hours (or days, if you have many-terabyte array). So formally it is not livelock, from the user experience it is --- he sees unkillable process in 'D' state for many hours.

Quoted 12 lines

And yes, fsync is slow and lots of people are seeing that. It's not helped by how ext3 is implemented (where fsync is effectively equivalent of a sync for many cases).
But again, moving the latency to "innocent" parties is not acceptable.

Quoted 7 lines
Quoted 6 lines

If the fsync() implementation isn't smart enough, sure, lets improve it. But not by shifting latency around... lets make it more efficient at submitting IO.
If we need to invent something like "chained IO" where if you wait on the last of the chain, you wait on the entirely chain, so be it.

Quoted 6 lines
Quoted 3 lines

This looks madly complicated. And ineffective, because if some page was submitted before fsync() was invoked, and is under writeback while fsync() is called, fsync() still has to wait on it.

so?
just make a chain per inode always...

The point is that many fsync()s may run in parallel and you have just one inode and just one chain. And if you add two-word list_head to a page, to link it on this list, many developers will hate it for increasing its size.

See the work dobe by Nick Piggin somewhere in this thread. He uses just one bit in radix tree to mark pages to process. But he needs to serialize all syncs on a given file, they no longer run in parallel.

Mikulas

#25 lore raw

Re: [PATCH 2/3] Fix fsync livelock

On Sun, 5 Oct 2008 23:30:51 -0400 (EDT

Quoted 4 lines

The point is that many fsync()s may run in parallel and you have just one inode and just one chain. And if you add two-word list_head to a page, to link it on this list, many developers will hate it for increasing its size.

why to a page?
a list head in the inode and chain up the bios....
or not make an actual list but just a "is the previous one done" thing it's not all that hard to get something that works on a per inode basis, that gives "wait for all io upto this one".

Signature · 3 lines
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org
#26 lore raw

Re: [PATCH 2/3] Fix fsync livelock

Quoted 8 lines · Arjan van de Ven

On Sun, 5 Oct 2008 23:30:51 -0400 (EDT

Quoted 4 lines

The point is that many fsync()s may run in parallel and you have just one inode and just one chain. And if you add two-word list_head to a page, to link it on this list, many developers will hate it for increasing its size.

why to a page?
a list head in the inode and chain up the bios....

And if you want to wait for a bio submitted by a different process? There's no way you can find the bio from the page.

Quoted 3 lines

or not make an actual list but just a "is the previous one done" thing it's not all that hard to get something that works on a per inode basis, that gives "wait for all io upto this one".

So code it :)

Mikulas

#27 lore raw

Re: [PATCH 2/3] Fix fsync livelock

Quoted 8 lines · On Mon, 6 Oct 2008 09:00:14 -0400 (EDT) Mikulas Patocka <[email protected]>…
Quoted 6 lines · Arjan van de Ven

On Sun, 5 Oct 2008 23:30:51 -0400 (EDT

Quoted 4 lines

The point is that many fsync()s may run in parallel and you have just one inode and just one chain. And if you add two-word list_head to a page, to link it on this list, many developers will hate it for increasing its size.

Quoted 5 lines
Quoted 2 lines

why to a page?
a list head in the inode and chain up the bios....

And if you want to wait for a bio submitted by a different process? There's no way you can find the bio from the page.

the point is that the kernel would always chain it to the inode, independent of who or when it is submitted

Signature · 3 lines
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org
#28 lore raw

Re: [PATCH 2/3] Fix fsync livelock

Quoted 11 lines · Arjan van de Ven
Quoted 8 lines · On Mon, 6 Oct 2008 09:00:14 -0400 (EDT) Mikulas Patocka <[email protected]>…
Quoted 6 lines · Arjan van de Ven

On Sun, 5 Oct 2008 23:30:51 -0400 (EDT

Quoted 4 lines

The point is that many fsync()s may run in parallel and you have just one inode and just one chain. And if you add two-word list_head to a page, to link it on this list, many developers will hate it for increasing its size.

Quoted 8 lines
Quoted 5 lines
Quoted 2 lines

why to a page?
a list head in the inode and chain up the bios....

And if you want to wait for a bio submitted by a different process? There's no way you can find the bio from the page.

the point is that the kernel would always chain it to the inode, independent of who or when it is submitted

If you add a list to an inode, you need to protect it with a spinlock. So you take one more spinlock for any write bio submitted --- a lot of developers would hate it.

Another problem: how do you want to walk all dirty pages and submit bio for them?

The act of allocating and submission of bio can block (if you run out of some mempool) and in this case it wait until some other bio is finished. During this time, more dirty pages can be created.

Also, if you find a page that is both dirty and under writeback, you need to wait until a writeback finishes and then initiate another writeback (because the old writeback may be writing stale data). You again, block, and more dirty pages can appear.

And if you block and more dirty pages appear, you are prone to the livelock.

[ In Nick Piggin's patch, it is needed to lock the whole address space, mark dirty pages in one non-blocking pass and write marked pages again in a blocking pass --- so that if more dirty pages appear while bios are submitted, the new pages will be skipped ]

Mikulas

#29 lore raw

Re: [PATCH 2/3] Fix fsync livelock

In reply to Arjan van de Ven
Quoted 10 lines · Arjan van de Ven
Quoted 5 lines · On Sun, 5 Oct 2008 20:01:46 -0400 (EDT) Mikulas Patocka <[email protected]>…

I assume that if very few people complained about the livelock till now, very few people will see degraded write performance. My patch blocks the writes only if the livelock happens, so if the livelock doesn't happen in unpatched kernel for most people, the patch won't make it worse.

I object to calling this a livelock. It's not.

8 hours of process in D state is a livelock. And we can do minimal fix here, this almost never happens in real life anyway.

Latency imposed of writer should not be a problem...

Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
#30 lore raw

Re: [PATCH 2/3] Fix fsync livelock

In reply to Mikulas Patocka
Quoted 3 lines · Mikulas Patocka

This looks madly complicated. And ineffective, because if some page was submitted before fsync() was invoked, and is under writeback while fsync() is called, fsync() still has to wait on it.

fsync() waiting on pre-issued writeback pages is the correct behaviour.

IOW, if the page is under writeback at the time an fsync() is issued (e.g. issued by pdflush), the page was *not clean* at the time the fsync() was called and hence must be clean when fsync() returns. fsync() needs to wait for all pages under I/O at the time it is called, not just the dirty pages it issues I/O on.....

Cheers,

Dave.

Signature · 2 lines
Dave Chinner
[email protected]
#31 lore raw

PATCH 3/3 Fix fsync-vs-write misbehavior

In reply to Andrew Morton

Fix violation of sync()/fsync() semantics. Previous code walked up to mapping->nrpages * 2 pages. Because pages could be created while __filemap_fdatawrite_range was in progress, it could lead to a misbehavior. Example: there are two pages in address space with indices 4, 5. Both are dirty. Someone calls __filemap_fdatawrite_range, it sets .nr_to_write = 4. Meanwhile, some other process creates dirty pages 0, 1, 2, 3. __filemap_fdatawrite_range writes pages 0, 1, 2, 3, finds out that it reached the limit and exits.

Result: pages that were dirty before __filemap_fdatawrite_range was invoked were not written.

With starvation protection from the previous patch, this mapping->nrpages * 2 logic is no longer needed.

---
 mm/filemap.c |    7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
mm/filemap.c +6 -1
Index: linux-2.6.27-rc7-devel/mm/filemap.c
===================================================================
@@ -202,6 +202,11 @@ static int sync_page_killable(void *word
  * opposed to a regular memory cleansing writeback.  The difference between
  * these two operations is that if a dirty page/buffer is encountered, it must
  * be waited upon, and not just skipped over.
+ *
+ * Because new pages dirty can be created while this is executing, that
+ * mapping->nrpages * 2 condition is unsafe. If we are doing data integrity
+ * write, we must write all the pages. AS_STARVATION bit will eventually prevent
+ * creating more dirty pages to avoid starvation.
  */
 int __filemap_fdatawrite_range(struct address_space *mapping, loff_t start,
 				loff_t end, int sync_mode)
@@ -209,7 +214,7 @@ int __filemap_fdatawrite_range(struct ad
 	int ret;
 	struct writeback_control wbc = {
 		.sync_mode = sync_mode,
-		.nr_to_write = mapping->nrpages * 2,
+		.nr_to_write = sync_mode == WB_SYNC_NONE ? mapping->nrpages * 2 : LONG_MAX,
 		.range_start = start,
 		.range_end = end,
 	};
#32 lore raw

PATCH 1/1 documentation: explain memory barriers

In reply to Andrew Morton
Quoted 3 lines · On Wed, 1 Oct 2008 22:54:04 -0700 Andrew Morton wrote:

This sequence is repeated three or four times and should be pulled out into a well-commented function. That comment should explain the logic behind the use of these barriers, please.

Quoted 1 line · and on 2008-OCT-08 Ben Hutchings wrote:

All memory barriers need a comment to explain why and what they're doing.

Should this be added to CodingStyle or some other file?

From: Randy Dunlap <[email protected]>

We want all uses of memory barriers to be explained in the source code.

---
 Documentation/SubmitChecklist |    3 +++
 1 file changed, 3 insertions(+)
Documentation/SubmitChecklist +3 -0
@@ -85,3 +85,6 @@ kernel patches.
 23: Tested after it has been merged into the -mm patchset to make sure
     that it still works with all of the other queued patches and various
     changes in the VM, VFS, and other subsystems.
+
+24: All memory barriers {e.g., barrier(), rmb(), wmb()} need a comment in the
+    source code that explains the logic of what they are doing and why.
#33 lore raw

Re: [PATCH] documentation: explain memory barriers

Quoted 9 lines · Randy Dunlap
Quoted 3 lines · On Wed, 1 Oct 2008 22:54:04 -0700 Andrew Morton wrote:

This sequence is repeated three or four times and should be pulled out into a well-commented function. That comment should explain the logic behind the use of these barriers, please.

Quoted 1 line · and on 2008-OCT-08 Ben Hutchings wrote:

All memory barriers need a comment to explain why and what they're doing.

Seriously? When a barrier is used, it's generally self-evident what it's doing. The real problem is when a barrier is *not* used. It would probably be more helpful to comment every non-barrier line of code to explain why it's okay if memory operations are getting reordered.

-- Chris

maintainer
#34 lore raw

Re: [PATCH] documentation: explain memory barriers

Quoted 10 lines · On Wed, 08 Oct 2008 21:17:58 -0400 Chris Snook <[email protected]> wrote:
Quoted 9 lines · Randy Dunlap
Quoted 3 lines · On Wed, 1 Oct 2008 22:54:04 -0700 Andrew Morton wrote:

This sequence is repeated three or four times and should be pulled out into a well-commented function. That comment should explain the logic behind the use of these barriers, please.

Quoted 1 line · and on 2008-OCT-08 Ben Hutchings wrote:

All memory barriers need a comment to explain why and what they're doing.

I approve this message.

Quoted 2 lines

Seriously? When a barrier is used, it's generally self-evident what it's doing.

fs/buffer.c:sync_buffer(). Have fun.

#35 lore raw

Re: [PATCH] documentation: explain memory barriers

Quoted 10 lines · Andrew Morton
Quoted 8 lines · On Wed, 08 Oct 2008 21:17:58 -0400 Chris Snook <[email protected]> wrote:
Quoted 7 lines · Randy Dunlap
Quoted 3 lines · On Wed, 1 Oct 2008 22:54:04 -0700 Andrew Morton wrote:

This sequence is repeated three or four times and should be pulled out into a well-commented function. That comment should explain the logic behind the use of these barriers, please.

and on 2008-OCT-08 Ben Hutchings wrote:

Quoted 8 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line

All memory barriers need a comment to explain why and what they're doing.

I approve this message.

Quoted 2 lines

Seriously? When a barrier is used, it's generally self-evident what it's doing.

fs/buffer.c:sync_buffer(). Have fun.

The real disaster there is the clear_buffer_##name macro and friends, as evidenced by fs/ext2/inode.c:599

clear_buffer_new(bh_result); /* What's this do? */

I'm completely in favor of documenting everything that can potentially interact with that train wreck, but I maintain that the vast majority of memory barriers are self-evident.

-- Chris

#36 lore raw

Re: [PATCH] documentation: explain memory barriers

Quoted 17 lines · Chris Snook
Quoted 16 lines · Andrew Morton
Quoted 9 lines · On Wed, 08 Oct 2008 21:17:58 -0400 Chris Snook <[email protected]> wrote:
Quoted 8 lines · Randy Dunlap
Quoted 3 lines · On Wed, 1 Oct 2008 22:54:04 -0700 Andrew Morton wrote:

This sequence is repeated three or four times and should be pulled out into a well-commented function. That comment should explain the logic behind the use of these barriers, please.

Quoted 2 lines · and on 2008-OCT-08 Ben Hutchings wrote:

All memory barriers need a comment to explain why and what they're doing.

I approve this message.

Quoted 2 lines

Seriously? When a barrier is used, it's generally self-evident what it's doing.

Quoted 6 lines
Quoted 1 line

fs/buffer.c:sync_buffer(). Have fun.

The real disaster there is the clear_buffer_##name macro and friends, as evidenced by fs/ext2/inode.c:599

clear_buffer_new(bh_result); /* What's this do? */

That's not a disaster. It is relatively easy even if you have no idea about any of that code to a) work out what BH_New flag does, see where it gets set and where it gets cleared, and then work out what that does. Actually, buffer.c used to leak BH_New in some cases, but now it should be a bug if BH_New is found to be set there (buffer.c should take any BH_New buffers, initialize them appropriately, and clear BH_New; a dangling BH_New would indicate uninitialized data going to or coming from the block).

No, they're easy, because you can find every single place where any one cares about them with a single simple grep.

Again, fs/buffer.c:sync_buffer(). Which stores and/or loads is that barrier sequencing against which subsequent stores and/or loads? Why?

For another fun example, mm/filemap.c:sync_page. This actually has a big comment, but (to me) it isn't even evident then which loads and stores are being sequenced against which subsequent ones because it is not explicitly documented. And I do have some experience in adding barriers to existing mm code where they have been missed completely.

mempool_free, set_dumpable, freeze_bdev.

Quoted 2 lines

I'm completely in favor of documenting everything that can potentially interact with that train wreck,

What's the train-wreck, again?

Quoted 2 lines

but I maintain that the vast majority of
memory barriers are self-evident.

They are self-evident if you have spent a lot of time getting the state machine and locking/concurrency model in your mind. If you have not, then how do you know there is not some memory operation way back or forward in the instruction stream that is supposed to be ordered by this barrier?

All memory barriers have to be documented, except acquire/release for critical sections, IMO.

#37 lore raw

Re: [PATCH] documentation: explain memory barriers

In reply to Chris Snook
Quoted 20 lines · Chris Snook
Quoted 10 lines · Andrew Morton
Quoted 8 lines · On Wed, 08 Oct 2008 21:17:58 -0400 Chris Snook <[email protected]> wrote:
Quoted 7 lines · Randy Dunlap
Quoted 3 lines · On Wed, 1 Oct 2008 22:54:04 -0700 Andrew Morton wrote:

This sequence is repeated three or four times and should be pulled out into a well-commented function. That comment should explain the logic behind the use of these barriers, please.

and on 2008-OCT-08 Ben Hutchings wrote:

Quoted 8 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line

All memory barriers need a comment to explain why and what they're doing.

I approve this message.

Quoted 2 lines

Seriously? When a barrier is used, it's generally self-evident what it's doing.

fs/buffer.c:sync_buffer(). Have fun.

Quoted 8 lines

The real disaster there is the clear_buffer_##name macro and friends, as evidenced by fs/ext2/inode.c:599

clear_buffer_new(bh_result); /* What's this do? */

I'm completely in favor of documenting everything that can potentially interact with that train wreck, but I maintain that the vast majority of memory barriers are self-evident.

Acquire and release barriers attached to operations are usually self- evident; standalone wmb() and rmb() much less so. It is helpful to be explicit about exactly which memory operations need to be ordered, which are often not the memory operations immediately preceding and following it. "all" may have been a bit strong though.

Ben.

Signature · 3 lines
Ben Hutchings, Senior Software Engineer, Solarflare Communications
Not speaking for my employer; that's the marketing department's job.
They asked us to note that Solarflare product names are trademarked.
#38 lore raw

Re: [PATCH] documentation: explain memory barriers

Quoted 11 lines · Ben Hutchings
Quoted 3 lines · Chris Snook

I'm completely in favor of documenting everything that can potentially interact with that train wreck, but I maintain that the vast majority of memory barriers are self-evident.

Acquire and release barriers attached to operations are usually self- evident; standalone wmb() and rmb() much less so. It is helpful to be explicit about exactly which memory operations need to be ordered, which are often not the memory operations immediately preceding and following it. "all" may have been a bit strong though.

No, I don't think so. We should absolutely force "all". That allows nobody to be lazy, no confusion, and reminds people that memory barriers are not easy to follow for a new reader of the code, or necessarily even the author, 6 months later. If somebody is too lazy to write a comment, they can use locks

One last quick quiz, easier than the earlier ones... mm/vmscan.c:__remove_mapping has a score of lines documenting exactly what memory operations are being ordered, and even an example of what happens if the ordering is not folllowed. This is a pretty good comment, if I say so myself. However, it has one deficiency in that it doesn't explicitly state where the write barrier(s) is (IMO the comments for one part of an ordering protocol should reference the other parts of the protcol).

Where are the store barriers, or why are they not required?

#39 lore raw

Re: [PATCH] documentation: explain memory barriers

In reply to Randy Dunlap

Documentation/SubmitChecklist kernel patches. · line 90

Quoted 3 lines · Randy Dunlap
Documentation/SubmitChecklist +3 -0
+
+24: All memory barriers {e.g., barrier(), rmb(), wmb()} need a comment in the
+    source code that explains the logic of what they are doing and why.

"what they are doing" will almost always be "flush value to RAM" or similar. How about this instead:

+ 24: All memory barriers ({e.g., barrier(), rmb(), wmb()} need a comment in the
+ source code that explains the race condition being prevented, and states
+ the location of the other code or hardware feature that races with this.
+
+ An example comment:
+
+ /*
+ * If we don't do a wmb() here, the RBFROBNIZ register on the XU293
+ * card will get confused and wedge the hardware...
+ */
+ wmb();

#40 lore raw

Re: [PATCH] documentation: explain memory barriers

Quoted 8 lines · On Thursday 09 October 2008 12:50, [email protected] wrote:
Quoted 4 lines · Randy Dunlap

+
+24: All memory barriers {e.g., barrier(), rmb(), wmb()} need a comment
in the + source code that explains the logic of what they are doing
and why.

"what they are doing" will almost always be "flush value to RAM" or similar.

Memory barriers don't flush anything anywhere. It's simple: you must explain which operations you are ordering against which.

Review

Quoted 13 lines

How about this instead:

+ 24: All memory barriers ({e.g., barrier(), rmb(), wmb()} need a comment
in the + source code that explains the race condition being prevented,
and states + the location of the other code or hardware feature that
races with this. +

(quoted diff) +7 -0
+    An example comment:
+
+ 	/*
+ 	 * If we don't do a wmb() here, the RBFROBNIZ register on the XU293
+ 	 * card will get confused and wedge the hardware...
+ 	 */
+	wmb();

This comment is no good, because it doesn't tell you what the memory barrier does. It tells you what might happen if you omit it.

/*
* If we don't do a wmb() here, the store to the RBFROBNIZ,
* above, might reach the device before the store X, below. *
* If that happens, then the XU293 card will get confused
* and wedge the hardware...
*/
wmb();

If you don't comment like that, then how does the reader know that the wmb is not *also* supposed to order the store with any other of the limitless subsequent stores until the next memory ordering operation? Or any of the previous stores since the last one?

#41 lore raw

Re: [PATCH] documentation: explain memory barriers

Quoted 11 lines · Nick Piggin
Quoted 8 lines · On Thursday 09 October 2008 12:50, [email protected] wrote:
Quoted 4 lines · Randy Dunlap

+
+24: All memory barriers {e.g., barrier(), rmb(), wmb()} need a comment
in the + source code that explains the logic of what they are doing
and why.

"what they are doing" will almost always be "flush value to RAM" or similar.

Memory barriers don't flush anything anywhere.

That's what I get for commenting on stuff when I'm into a 40-hour week by Wednesday. :)

I was speaking of the generic programmer who does stuff like:

	x = 10; /* set x to 10 */ 

for "what they are doing". You know the type. ;)

"flush value to RAM", "force memory barrier operation", and I think I've seen a few kzalloc()'s that have "allocate zero'ed memory" on them. "what they are doing" is usually not worth writing down, but being verbose for the *why* is almost always good, especially for things like memory barriers that almost nobody can get their brains wrapped around (how many flame-fests per year do we have about "volatile"? ;)

Quoted 9 lines

/*
* If we don't do a wmb() here, the store to the RBFROBNIZ,
* above, might reach the device before the store X, below. *
* If that happens, then the XU293 card will get confused
* and wedge the hardware...
*/
wmb();

Quoted 4 lines

If you don't comment like that, then how does the reader know that the wmb is not *also* supposed to order the store with any other of the limitless subsequent stores until the next memory ordering operation? Or any of the previous stores since the last one?

Even better (as I missed the "also supposed to know" case). My general point was that a concrete example would improve Randy's original patch by showing what sort of things should be in the comment, and your correction pointed out *why* a concrete example was needed. ;)

#42 lore raw

PATCH 3/3 Memory management livelock

In reply to Andrew Morton

Fix violation of sync()/fsync() semantics. Previous code walked up to mapping->nrpages * 2 pages. Because pages could be created while __filemap_fdatawrite_range was in progress, it could lead to a misbehavior.
Example: there are two pages in address space with indices 4, 5. Both are dirty. Someone calls __filemap_fdatawrite_range, it sets .nr_to_write = 4. Meanwhile, some other process creates dirty pages 0, 1, 2, 3. __filemap_fdatawrite_range writes pages 0, 1, 2, 3, finds out that it reached the limit and exits.
Result: pages that were dirty before __filemap_fdatawrite_range was invoked were not written.

With starvation protection from the previous patch, this mapping->nrpages * 2 logic is no longer needed.

---
 mm/filemap.c |    7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
mm/filemap.c +6 -1
Index: linux-2.6.27-rc7-devel/mm/filemap.c
===================================================================
@@ -202,6 +202,11 @@ static int sync_page_killable(void *word
  * opposed to a regular memory cleansing writeback.  The difference between
  * these two operations is that if a dirty page/buffer is encountered, it must
  * be waited upon, and not just skipped over.
+ *
+ * Because new pages dirty can be created while this is executing, that
+ * mapping->nrpages * 2 condition is unsafe. If we are doing data integrity
+ * write, we must write all the pages. AS_STARVATION bit will eventually prevent
+ * creating more dirty pages to avoid starvation.
  */
 int __filemap_fdatawrite_range(struct address_space *mapping, loff_t start,
 				loff_t end, int sync_mode)
@@ -209,7 +214,7 @@ int __filemap_fdatawrite_range(struct ad
 	int ret;
 	struct writeback_control wbc = {
 		.sync_mode = sync_mode,
-		.nr_to_write = mapping->nrpages * 2,
+		.nr_to_write = sync_mode == WB_SYNC_NONE ? mapping->nrpages * 2 : LONG_MAX,
 		.range_start = start,
 		.range_end = end,
 	};
#43 lore raw
In reply to Andrew Morton
Quoted 21 lines · Andrew Morton

On Tue, 23 Sep 2008 18:34:20 -0400 (EDT)

Quoted 18 lines · Mikulas Patocka
Quoted 18 lines

On Mon, 22 Sep 2008 17:10:04 -0400 (EDT)

Quoted 15 lines · Mikulas Patocka

The bug happens when one process is doing sequential buffered writes to a block device (or file) and another process is attempting to execute sync(), fsync() or direct-IO on that device (or file). This syncing process will wait indefinitelly, until the first writing process finishes.

For example, run these two commands:
dd if=/dev/zero of=/dev/sda1 bs=65536 &
dd if=/dev/sda1 of=/dev/null bs=4096 count=1 iflag=direct

The bug is caused by sequential walking of address space in write_cache_pages and wait_on_page_writeback_range: if some other process is constantly making dirty and writeback pages while these functions run, the functions will wait on every new page, resulting in indefinite wait.

I think the problem has been misidentified, or else I have misread the code. See below. I hope I'm right, because I think the patches are pretty heavy on complexity in these already complex paths...

It would help if you explicitly identify the exact livelock. Ie. give a sequence of behaviour that leads to our progress rate falling to zero.

Quoted 37 lines
Quoted 37 lines
Quoted 16 lines

Shouldn't happen. All the data-syncing functions should have an upper bound on the number of pages which they attempt to write. In the example above, we end up in here:

int __filemap_fdatawrite_range(struct address_space *mapping, loff_t start,
loff_t end, int sync_mode)
{
int ret;
struct writeback_control wbc = {
.sync_mode = sync_mode,
.nr_to_write = mapping->nrpages * 2, <<--
.range_start = start,
.range_end = end,
};

Quoted 3 lines

so generic_file_direct_write()'s filemap_write_and_wait() will attempt to write at most 2* the number of pages which are in cache for that inode.

See write_cache_pages:

if (wbc->sync_mode != WB_SYNC_NONE)

        wait_on_page_writeback(page);	(1)
if (PageWriteback(page) ||
    !clear_page_dirty_for_io(page)) {
        unlock_page(page);		(2)
        continue;
}
ret = (*writepage)(page, wbc, data);
if (unlikely(ret == AOP_WRITEPAGE_ACTIVATE)) {
        unlock_page(page);
        ret = 0;
}
if (ret || (--(wbc->nr_to_write) <= 0))
        done = 1;
Quoted 4 lines
Quoted 4 lines

--- so if it goes by points (1) and (2), the counter is not decremented, yet the function waits for the page. If there is constant stream of writeback pages being generated, it waits on each on them --- that is, forever.

*What* is, forever? Data integrity syncs should have pages operated on in-order, until we get to the end of the range. Circular writeback could go through again, possibly, but no more than once.

Quoted 7 lines
Quoted 6 lines

I have seen livelock in this function. For you that example with two dd's, one buffered write and the other directIO read doesn't work? For me it livelocks here.

wait_on_page_writeback_range is another example where the livelock happened, there is no protection at all against starvation.

Quoted 6 lines

um, OK. So someone else is initiating IO for this inode and this thread *never* gets to initiate any writeback. That's a bit of a surprise.

How do we fix that? Maybe decrement nt_to_write for these pages as well?

What's the actual problem, though? nr_to_write should not be used for data integrity operations, and it should not be critical for other writeout. Upper layers should be able to deal with it rather than have us lying to them.

Quoted 6 lines
Quoted 6 lines

BTW. that .nr_to_write = mapping->nrpages * 2 looks like a dangerous thing to me.

Imagine this case: You have two pages with indices 4 and 5 dirty in a file. You call fsync(). It sets nr_to_write to 4.

Quoted 7 lines
Quoted 7 lines

Meanwhile, another process makes pages 0, 1, 2, 3 dirty.

The fsync() process goes to write_cache_pages, writes the first 4 dirty pages and exits because it goes over the limit.

result --- you violate fsync() semantics, pages that were dirty before call to fsync() are not written when fsync() exits.

Wow, that's really nasty. Sad we still have known data integrity problems in such core functions.

Quoted 3 lines

yup, that's pretty much unfixable, really, unless new locks are added which block threads which are writing to unrelated sections of the file, and that could hurt some workloads quite a lot, I expect.

Why is it unfixable? Just ignore nr_to_write, and write out everything properly, I would have thought.

Some things may go a tad slower, but those are going to be the things that are using fsync, in which cases they are going to hurt much more from the loss of data integrity than a slowdown.

Unfortunately because we have played fast and loose for so long, they expect this behaviour, were tested and optimised with it, and systems designed and deployed with it, and will notice performance regressions if we start trying to do things properly. This is one of my main arguments for doing things correctly up-front, even if it means a massive slowdown in some real or imagined workload: at least then we will hear about complaints and be able to try to improve them rather than setting ourselves up for failure later.
/rant

Anyway, in this case, I don't think there would be really big problems. Also, I think there is a reasonable optimisation that might improve it (2nd last point, in attached patch).

OK, so after glancing at the code... wow, it seems like there are a lot of bugs in there.

write_cache_pages has a number of problems, which appear to be real bugs:

* scanned == 1 is supposed to mean that cyclic writeback has circled through zero, thus we should not circle again. However it gets set to 1 after the first successful pagevec lookup. This leads to cases where not enough data gets written. Counterexample: file with first 10 pages dirty, writeback_index == 5, nr_to_write == 10. Then the 5 last pages will be found, and scanned will be set to 1, after writing those out, we will not cycle back to get the first 5. Rework this logic.

* If AOP_WRITEPAGE_ACTIVATE is returned, the filesystem is calling on us to drop the page lock and retry, however the existing code would just skip that page regardless of whether or not it was a data interity operation. Change this to always retry such a result.

This is a data interity bug.

* If ret signals a real error, but we still have some pages left in the pagevec, done would be set to 1, but the remaining pages would continue to be processed and ret will be overwritten in the process. It could easily be overwritten with success, and thus success will be returned even if there is an error. Fix this by bailing immediately if there is an error, and retaining the error code.

This is a data interity bug.

* nr_to_write is heeded by data interity operations, and the callers tend to set it to silly values that could break data interity semantics. For example, nr_to_write can be set to mapping->nr_pages * 2, however if a file has a single, dirty page, then fsync is called, subsequent pages might be concurrently added and dirtied, then write_cache_pages might writeout two of these newly dirty pages, while not writing out the old page that should have been written out. Fix this by ignoring nr_to_write if it is a data integrity sync.

This is a data interity bug.

* In the range_cont case, range_start is set to index << PAGE_CACHE_SHIFT, but index is a pgoff_t and range_start is loff_t, so we can get truncation of the value on 32-bit platforms. Fix this by adding the standard loff_t cast.

This is a data interity bug (depending on how range_cont is used).

Other problems that are not strictly bugs:

o If we get stuck behind another process that is cleaning pages, we will be forced to wait for them to finish, then perform our own writeout (if it was redirtied during the long wait), then wait for that. If a page under writeout is still clean, we can skip waiting for it (if we're part of a data integrity sync, we'll be waiting for all writeout pages afterwards).

o Control structures containing non-indempotent expressions. Break these out and make flow control clearer from data control.

---
 mm/filemap.c        |    2 -
 mm/page-writeback.c |  101 +++++++++++++++++++++++++++++++++++-----------------
 2 files changed, 70 insertions(+), 33 deletions(-)
mm/page-writeback.c +69 -32
Index: linux-2.6/mm/page-writeback.c
===================================================================
@@ -869,13 +869,13 @@ int write_cache_pages(struct address_spa
 {
 	struct backing_dev_info *bdi = mapping->backing_dev_info;
 	int ret = 0;
-	int done = 0;
 	struct pagevec pvec;
 	int nr_pages;
+	pgoff_t writeback_index;
 	pgoff_t index;
 	pgoff_t end;		/* Inclusive */
-	int scanned = 0;
 	int range_whole = 0;
+	int cycled;
 
 	if (wbc->nonblocking && bdi_write_congested(bdi)) {
 		wbc->encountered_congestion = 1;
@@ -884,23 +884,28 @@ int write_cache_pages(struct address_spa
 
 	pagevec_init(&pvec, 0);
 	if (wbc->range_cyclic) {
-		index = mapping->writeback_index; /* Start from prev offset */
-		end = -1;
+		cycled = 0;
+		writeback_index = mapping->writeback_index; /* prev offset */
+		index = writeback_index;
+		if (index == 0)
+			cycled = 1;
+		end = ULLONG_MAX;
 	} else {
 		index = wbc->range_start >> PAGE_CACHE_SHIFT;
 		end = wbc->range_end >> PAGE_CACHE_SHIFT;
 		if (wbc->range_start == 0 && wbc->range_end == LLONG_MAX)
 			range_whole = 1;
-		scanned = 1;
 	}
 retry:
-	while (!done && (index <= end) &&
-	       (nr_pages = pagevec_lookup_tag(&pvec, mapping, &index,
-					      PAGECACHE_TAG_DIRTY,
-					      min(end - index, (pgoff_t)PAGEVEC_SIZE-1) + 1))) {
-		unsigned i;
+	do {
+		int i;
+
+		nr_pages = pagevec_lookup_tag(&pvec, mapping, &index,
+			      PAGECACHE_TAG_DIRTY,
+			      min(end - index, (pgoff_t)PAGEVEC_SIZE - 1) + 1);
+		if (!nr_pages)
+			break;
 
-		scanned = 1;
 		for (i = 0; i < nr_pages; i++) {
 			struct page *page = pvec.pages[i];
 
@@ -911,58 +916,90 @@ retry:
 			 * swizzled back from swapper_space to tmpfs file
 			 * mapping
 			 */
+again:
 			lock_page(page);
 
+			/*
+			 * Page truncated or invalidated. We can freely skip it
+			 * then, even for data integrity operations: the page
+			 * has disappeared concurrently, so there could be no
+			 * real expectation of this data interity operation
+			 * even if there is now a new, dirty page at the same
+			 * pagecache address.
+			 */
 			if (unlikely(page->mapping != mapping)) {
+continue_unlock:
 				unlock_page(page);
 				continue;
 			}
 
-			if (!wbc->range_cyclic && page->index > end) {
-				done = 1;
+			if (page->index > end) {
+				/* Can't be cyclic: end == ULLONG_MAX */
 				unlock_page(page);
-				continue;
+done_release:
+				pagevec_release(&pvec);
+				goto done;
 			}
 
-			if (wbc->sync_mode != WB_SYNC_NONE)
-				wait_on_page_writeback(page);
-
-			if (PageWriteback(page) ||
-			    !clear_page_dirty_for_io(page)) {
-				unlock_page(page);
-				continue;
+			if (PageWriteback(page)) {
+				/* someone else wrote it for us */
+				if (!PageDirty(page)) {
+					goto continue_unlock;
+				} else {
+					/* hmm, but it has been dirtied again */
+					if (wbc->sync_mode != WB_SYNC_NONE)
+						wait_on_page_writeback(page);
+					else
+						goto continue_unlock;
+				}
 			}
 
+			BUG_ON(PageWriteback(page));
+
+			if (!clear_page_dirty_for_io(page))
+				goto continue_unlock;
+
 			ret = (*writepage)(page, wbc, data);
 
-			if (unlikely(ret == AOP_WRITEPAGE_ACTIVATE)) {
-				unlock_page(page);
-				ret = 0;
+			if (unlikely(ret)) {
+				/* Must retry the write, esp. for integrity */
+				if (ret == AOP_WRITEPAGE_ACTIVATE) {
+					unlock_page(page);
+					ret = 0;
+					goto again;
+				}
+				goto done;
+			}
+			if (wbc->sync_mode == WB_SYNC_NONE) {
+				wbc->nr_to_write--;
+				if (wbc->nr_to_write <= 0)
+					goto done_release;
 			}
-			if (ret || (--(wbc->nr_to_write) <= 0))
-				done = 1;
 			if (wbc->nonblocking && bdi_write_congested(bdi)) {
 				wbc->encountered_congestion = 1;
-				done = 1;
+				goto done_release;
 			}
 		}
 		pagevec_release(&pvec);
 		cond_resched();
-	}
-	if (!scanned && !done) {
+	} while (index <= end);
+
+	if (wbc->range_cyclic && !cycled) {
 		/*
 		 * We hit the last page and there is more work to be done: wrap
 		 * back to the start of the file
 		 */
-		scanned = 1;
+		cycled = 1;
 		index = 0;
+		end = writeback_index - 1; /* won't be -ve, see above */
 		goto retry;
 	}
+done:
 	if (wbc->range_cyclic || (range_whole && wbc->nr_to_write > 0))
 		mapping->writeback_index = index;
-
 	if (wbc->range_cont)
-		wbc->range_start = index << PAGE_CACHE_SHIFT;
+		wbc->range_start = (loff_t)index << PAGE_CACHE_SHIFT;
+
 	return ret;
 }
 EXPORT_SYMBOL(write_cache_pages);
mm/filemap.c +1 -1
Index: linux-2.6/mm/filemap.c
===================================================================
@@ -209,7 +209,7 @@ int __filemap_fdatawrite_range(struct ad
 	int ret;
 	struct writeback_control wbc = {
 		.sync_mode = sync_mode,
-		.nr_to_write = mapping->nrpages * 2,
+		.nr_to_write = LONG_MAX,
 		.range_start = start,
 		.range_end = end,
 	};
maintainer
#44 lore raw
Quoted 6 lines · On Fri, 3 Oct 2008 12:32:23 +1000 Nick Piggin <[email protected]> wrote:
Quoted 3 lines

yup, that's pretty much unfixable, really, unless new locks are added which block threads which are writing to unrelated sections of the file, and that could hurt some workloads quite a lot, I expect.

Why is it unfixable? Just ignore nr_to_write, and write out everything properly, I would have thought.

That can cause fsync to wait arbitrarily long if some other process is writing the file. This happens.

#45 lore raw
Quoted 1 line · Andrew Morton

On Fri, 3 Oct 2008 12:32:23 +1000 Nick Piggin <[email protected]>

Quoted 9 lines · wrote:
Quoted 6 lines
Quoted 3 lines

yup, that's pretty much unfixable, really, unless new locks are added which block threads which are writing to unrelated sections of the file, and that could hurt some workloads quite a lot, I expect.

Why is it unfixable? Just ignore nr_to_write, and write out everything properly, I would have thought.

That can cause fsync to wait arbitrarily long if some other process is writing the file.

It can be fixed without touching non-fsync paths (see my next email for the way to fix it without touching fastpaths).

Quoted 1 line

This happens.

What does such a thing? It would have been nicer to ask them to not do that then, or get them to use range syncs or something. Now that's much harder because we've accepted the crappy workaround for so long.

It's far far worse to just ignore data integrity of fsync because of the problem. Should at least have returned an error from fsync in that case, or make it interruptible or something.

maintainer
#46 lore raw
Quoted 7 lines · On Fri, 3 Oct 2008 12:59:17 +1000 Nick Piggin <[email protected]> wrote:
Quoted 1 line · Andrew Morton

On Fri, 3 Oct 2008 12:32:23 +1000 Nick Piggin <[email protected]>

Quoted 4 lines · wrote:
Quoted 4 lines
Quoted 3 lines

yup, that's pretty much unfixable, really, unless new locks are added which block threads which are writing to unrelated sections of the file, and that could hurt some workloads quite a lot, I expect.

Quoted 9 lines
Quoted 5 lines
Quoted 2 lines

Why is it unfixable? Just ignore nr_to_write, and write out everything properly, I would have thought.

That can cause fsync to wait arbitrarily long if some other process is writing the file.

It can be fixed without touching non-fsync paths (see my next email for the way to fix it without touching fastpaths).

yup.

Quoted 4 lines
Quoted 2 lines

This happens.

What does such a thing?

I forget. People do all sorts of weird stuff.

Quoted 7 lines

It would have been nicer to ask them to not do
that then, or get them to use range syncs or something. Now that's much harder because we've accepted the crappy workaround for so long.

It's far far worse to just ignore data integrity of fsync because of the problem. Should at least have returned an error from fsync in that case, or make it interruptible or something.

If a file has one dirty page at offset 1000000000000000 then someone does an fsync() and someone else gets in first and starts madly writing pages at offset 0, we want to write that page at 1000000000000000. Somehow.

I expect there's no solution which avoids blocking the writers at some stage.

#47 lore raw
Quoted 1 line · Andrew Morton

On Fri, 3 Oct 2008 12:59:17 +1000 Nick Piggin <[email protected]>

Quoted 8 lines · wrote:
Quoted 7 lines · Andrew Morton
Quoted 3 lines

That can cause fsync to wait arbitrarily long if some other process is writing the file.

It can be fixed without touching non-fsync paths (see my next email for the way to fix it without touching fastpaths).

Quoted 7 lines

yup.

Quoted 3 lines
Quoted 1 line

This happens.

What does such a thing?

I forget. People do all sorts of weird stuff.

Damn people...

I guess they also do non-weird stuff like expecting fsync to really fsync.

Quoted 8 lines
Quoted 7 lines

It would have been nicer to ask them to not do
that then, or get them to use range syncs or something. Now that's much harder because we've accepted the crappy workaround for so long.

It's far far worse to just ignore data integrity of fsync because of the problem. Should at least have returned an error from fsync in that case, or make it interruptible or something.

Quoted 7 lines

If a file has one dirty page at offset 1000000000000000 then someone does an fsync() and someone else gets in first and starts madly writing pages at offset 0, we want to write that page at 1000000000000000. Somehow.

I expect there's no solution which avoids blocking the writers at some stage.

See my other email. Something roughly like this would do the trick (hey, it actually boots and runs and does fix the problem too).

It's ugly because we don't have quite the right radix tree operations yet (eg. lookup multiple tags, set tag X if tag Y was set, proper range lookups). But the theory is to up-front tag the pages that we need to get to disk.

Completely no impact or slowdown to any writers (although it does add 8 bytes of tags to the radix tree node... but doesn't increase memory footprint as such due to slab).

include/linux/fs.h +3 -1
Index: linux-2.6/include/linux/fs.h
===================================================================
@@ -578,10 +578,12 @@ struct block_device {
 
 /*
  * Radix-tree tags, for tagging dirty and writeback pages within the pagecache
- * radix trees
+ * radix trees. Also, to snapshot all pages required to be fsync'ed in order
+ * to obey data integrity semantics.
  */
 #define PAGECACHE_TAG_DIRTY	0
 #define PAGECACHE_TAG_WRITEBACK	1
+#define PAGECACHE_TAG_FSYNC	2
 
 int mapping_tagged(struct address_space *mapping, int tag);
 
include/linux/radix-tree.h +1 -1
Index: linux-2.6/include/linux/radix-tree.h
===================================================================
@@ -55,7 +55,7 @@ static inline int radix_tree_is_indirect
 
 /*** radix-tree API starts here ***/
 
-#define RADIX_TREE_MAX_TAGS 2
+#define RADIX_TREE_MAX_TAGS 3
 
 /* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
 struct radix_tree_root {
mm/page-writeback.c +182 -25

231 lines not on this page · raw message

mm/filemap.c +59 -1

78 lines not on this page · raw message

maintainer
#48 lore raw
Quoted 5 lines · On Fri, 3 Oct 2008 13:47:21 +1000 Nick Piggin <[email protected]> wrote:
Quoted 2 lines

I expect there's no solution which avoids blocking the writers at some stage.

See my other email. Something roughly like this would do the trick (hey, it actually boots and runs and does fix the problem too).

It needs exclusion to protect all those temp tags. Is do_fsync()'s i_mutex sufficient? It's qute unobvious (and unmaintainable?) that all the callers of this stuff are running under that lock.

Quoted 4 lines

It's ugly because we don't have quite the right radix tree operations yet (eg. lookup multiple tags, set tag X if tag Y was set, proper range lookups). But the theory is to up-front tag the pages that we need to get to disk.

Perhaps some callback-calling radix tree walker.

Quoted 3 lines

Completely no impact or slowdown to any writers (although it does add 8 bytes of tags to the radix tree node... but doesn't increase memory footprint as such due to slab).

Can we reduce the amount of copy-n-pasting here?

#49 lore raw
Quoted 1 line · Andrew Morton

On Fri, 3 Oct 2008 13:47:21 +1000 Nick Piggin <[email protected]>

Quoted 9 lines · wrote:
Quoted 5 lines
Quoted 2 lines

I expect there's no solution which avoids blocking the writers at some stage.

See my other email. Something roughly like this would do the trick (hey, it actually boots and runs and does fix the problem too).

It needs exclusion to protect all those temp tags. Is do_fsync()'s i_mutex sufficient? It's qute unobvious (and unmaintainable?) that all the callers of this stuff are running under that lock.

Yeah... it does need a lock, which I brushed under the carpet :P I was going to just say use i_mutex, but then we really would start impacting on other fastpaths (eg writers).

Possibly a new mutex in the address_space? That way we can say "anybody who holds this mutex is allowed to use the tag for anything" and it doesn't have to be fsync specific (whether that would be of any use to anything else, I don't know).

Quoted 6 lines
Quoted 4 lines

It's ugly because we don't have quite the right radix tree operations yet (eg. lookup multiple tags, set tag X if tag Y was set, proper range lookups). But the theory is to up-front tag the pages that we need to get to disk.

Perhaps some callback-calling radix tree walker.

Possibly, yes. That would make it fairly general. I'll have a look...

Quoted 5 lines
Quoted 3 lines

Completely no impact or slowdown to any writers (although it does add 8 bytes of tags to the radix tree node... but doesn't increase memory footprint as such due to slab).

Can we reduce the amount of copy-n-pasting here?

Yeah... I went to break the sync/async cases into two, but it looks like it may not have been worthwhile. Just another branch might be the best way to go.

As far as the c&p in setting the FSYNC tag, yes that should all go away if the radix-tree is up to scratch. Basically:

radix_tree_tag_set_if_tagged(start, end, ifWRITEBACK|DIRTY, setFSYNC);

should be able to replace the whole thing, and we'd hold the tree_lock, so we would not have to take the page lock etc. Basically it would be much nicer... even somewhere close to a viable solution.

maintainer
#50 lore raw
Quoted 13 lines · On Fri, 3 Oct 2008 14:07:55 +1000 Nick Piggin <[email protected]> wrote:
Quoted 1 line · Andrew Morton

On Fri, 3 Oct 2008 13:47:21 +1000 Nick Piggin <[email protected]>

Quoted 9 lines · wrote:
Quoted 5 lines
Quoted 2 lines

I expect there's no solution which avoids blocking the writers at some stage.

See my other email. Something roughly like this would do the trick (hey, it actually boots and runs and does fix the problem too).

It needs exclusion to protect all those temp tags. Is do_fsync()'s i_mutex sufficient? It's qute unobvious (and unmaintainable?) that all the callers of this stuff are running under that lock.

Quoted 5 lines

Yeah... it does need a lock, which I brushed under the carpet :P I was going to just say use i_mutex, but then we really would start impacting on other fastpaths (eg writers).

Possibly a new mutex in the address_space?

That's another, umm 24 bytes minimum in the address_space (and inode). That's fairly ouch, which is why Miklaus did that hokey bit-based thing.

Quoted 20 lines

That way we can say
"anybody who holds this mutex is allowed to use the tag for anything" and it doesn't have to be fsync specific (whether that would be of any use to anything else, I don't know).

Quoted 6 lines
Quoted 4 lines

It's ugly because we don't have quite the right radix tree operations yet (eg. lookup multiple tags, set tag X if tag Y was set, proper range lookups). But the theory is to up-front tag the pages that we need to get to disk.

Perhaps some callback-calling radix tree walker.

Possibly, yes. That would make it fairly general. I'll have a look...

Quoted 4 lines
Quoted 3 lines

Completely no impact or slowdown to any writers (although it does add 8 bytes of tags to the radix tree node... but doesn't increase memory footprint as such due to slab).

Quoted 5 lines
Quoted 1 line

Can we reduce the amount of copy-n-pasting here?

Yeah... I went to break the sync/async cases into two, but it looks like it may not have been worthwhile. Just another branch might be the best way to go.

Yup. Could add another do-this flag in the writeback_control, perhaps. Or even a function pointer.

Quoted 8 lines

As far as the c&p in setting the FSYNC tag, yes that should all go away if the radix-tree is up to scratch. Basically:

radix_tree_tag_set_if_tagged(start, end, ifWRITEBACK|DIRTY, setFSYNC);

should be able to replace the whole thing, and we'd hold the tree_lock, so we would not have to take the page lock etc. Basically it would be much nicer... even somewhere close to a viable solution.

#51 lore raw
Quoted 6 lines · Andrew Morton

On Fri, 3 Oct 2008 14:07:55 +1000 Nick Piggin <[email protected]>

Quoted 1 line

Possibly a new mutex in the address_space?

That's another, umm 24 bytes minimum in the address_space (and inode). That's fairly ouch, which is why Miklaus did that hokey bit-based thing.

Well yeah, it would be a bit based mutex in mapping->flags with hashed waitqueues. Like Miklaus's.

Quoted 6 lines
Quoted 3 lines

Yeah... I went to break the sync/async cases into two, but it looks like it may not have been worthwhile. Just another branch might be the best way to go.

Yup. Could add another do-this flag in the writeback_control, perhaps. Or even a function pointer.

Yeah... possibly we could just _always_ do the PAGECACHE_TAG_FSYNC thing if mode != WB_SYNC_NONE. I think if we had the infrastructure there to do it all, it should always be something we want to do for data integrity writeout.

#52 lore raw
In reply to Andrew Morton
Quoted 11 lines · Andrew Morton
Quoted 5 lines · On Fri, 3 Oct 2008 13:47:21 +1000 Nick Piggin <[email protected]> wrote:
Quoted 2 lines

I expect there's no solution which avoids blocking the writers at some stage.

See my other email. Something roughly like this would do the trick (hey, it actually boots and runs and does fix the problem too).

It needs exclusion to protect all those temp tags. Is do_fsync()'s i_mutex sufficient? It's qute unobvious (and unmaintainable?) that all the callers of this stuff are running under that lock.

That filemap_fdatawrite and filemap_fdatawait in fsync() aren't really called under i_mutex (see do_fsync).

So the possible solutions are:

1. Add jiffies when the page was diried and wroteback to struct page
+ no impact on locking and concurrency
- increases the structure by 8 bytes

2. Stop the writers when the starvation happens (what I did)
+ doesn't do any locking if the livelock doesn't happen
- locks writers when the livelock happens (I think it's not really serious --- because very few people complained about the livelock, very few people will see performance degradation from blocking the writers).

3. Add another bit to radix tree (what Nick did)
+ doesn't ever block writers
- unconditionally takes the lock on fsync path and serializates concurrent syncs/fsyncs. Probably low overhead too ... or I don't know, is there any possible situation when more processes execute sync() in parallel and user would see degradations if those syncs were serialized?

Mikulas

#53 lore raw
Quoted 2 lines · Mikulas Patocka
Quoted 1 line · Andrew Morton

On Fri, 3 Oct 2008 13:47:21 +1000 Nick Piggin <[email protected]>

Quoted 10 lines · wrote:
Quoted 9 lines
Quoted 5 lines
Quoted 2 lines

I expect there's no solution which avoids blocking the writers at some stage.

See my other email. Something roughly like this would do the trick (hey, it actually boots and runs and does fix the problem too).

It needs exclusion to protect all those temp tags. Is do_fsync()'s i_mutex sufficient? It's qute unobvious (and unmaintainable?) that all the callers of this stuff are running under that lock.

Quoted 8 lines

That filemap_fdatawrite and filemap_fdatawait in fsync() aren't really called under i_mutex (see do_fsync).

So the possible solutions are:

1. Add jiffies when the page was diried and wroteback to struct page
+ no impact on locking and concurrency
- increases the structure by 8 bytes

This one is not practical.

Quoted 5 lines

2. Stop the writers when the starvation happens (what I did)
+ doesn't do any locking if the livelock doesn't happen
- locks writers when the livelock happens (I think it's not really serious --- because very few people complained about the livelock, very few people will see performance degradation from blocking the writers).

Maybe it is because not much actually does sequential writes to a massive file or block device while trying to fsync it as well? I don't know. You could still have cases where fsync takes much longer than expected but it is still not long enough for a user to report it as a "livelock" bug.

Quoted 6 lines

3. Add another bit to radix tree (what Nick did)
+ doesn't ever block writers
- unconditionally takes the lock on fsync path and serializates concurrent syncs/fsyncs. Probably low overhead too ... or I don't know, is there any possible situation when more processes execute sync() in parallel and user would see degradations if those syncs were serialized?

#54 lore raw
Quoted 15 lines
Quoted 5 lines

So the possible solutions are:

1. Add jiffies when the page was diried and wroteback to struct page
+ no impact on locking and concurrency
- increases the structure by 8 bytes

This one is not practical.

Quoted 5 lines

2. Stop the writers when the starvation happens (what I did)
+ doesn't do any locking if the livelock doesn't happen
- locks writers when the livelock happens (I think it's not really serious --- because very few people complained about the livelock, very few people will see performance degradation from blocking the writers).

Quoted 4 lines

Maybe it is because not much actually does sequential writes to a massive file or block device while trying to fsync it as well? I don't know. You could still have cases where fsync takes much longer than expected but it is still not long enough for a user to report it as a "livelock" bug.

At most twice the time it would normally take (one loop of writeback queue until it detects the livelock and the other loop until it drains all the new pages that were created during the first loop).

While with solution (3) it would take only once for the whole writeback queue.

Mikulas

Quoted 6 lines
Quoted 6 lines

3. Add another bit to radix tree (what Nick did)
+ doesn't ever block writers
- unconditionally takes the lock on fsync path and serializates concurrent syncs/fsyncs. Probably low overhead too ... or I don't know, is there any possible situation when more processes execute sync() in parallel and user would see degradations if those syncs were serialized?

#55 lore raw
In reply to Nick Piggin
Quoted 67 lines · Nick Piggin
Quoted 21 lines · Andrew Morton

On Tue, 23 Sep 2008 18:34:20 -0400 (EDT)

Quoted 18 lines · Mikulas Patocka
Quoted 18 lines

On Mon, 22 Sep 2008 17:10:04 -0400 (EDT)

Quoted 15 lines · Mikulas Patocka

The bug happens when one process is doing sequential buffered writes to a block device (or file) and another process is attempting to execute sync(), fsync() or direct-IO on that device (or file). This syncing process will wait indefinitelly, until the first writing process finishes.

For example, run these two commands:
dd if=/dev/zero of=/dev/sda1 bs=65536 &
dd if=/dev/sda1 of=/dev/null bs=4096 count=1 iflag=direct

The bug is caused by sequential walking of address space in write_cache_pages and wait_on_page_writeback_range: if some other process is constantly making dirty and writeback pages while these functions run, the functions will wait on every new page, resulting in indefinite wait.

I think the problem has been misidentified, or else I have misread the code. See below. I hope I'm right, because I think the patches are pretty heavy on complexity in these already complex paths...

It would help if you explicitly identify the exact livelock. Ie. give a sequence of behaviour that leads to our progress rate falling to zero.

Quoted 37 lines
Quoted 37 lines
Quoted 16 lines

Shouldn't happen. All the data-syncing functions should have an upper bound on the number of pages which they attempt to write. In the example above, we end up in here:

int __filemap_fdatawrite_range(struct address_space *mapping, loff_t start,
loff_t end, int sync_mode)
{
int ret;
struct writeback_control wbc = {
.sync_mode = sync_mode,
.nr_to_write = mapping->nrpages * 2, <<--
.range_start = start,
.range_end = end,
};

Quoted 3 lines

so generic_file_direct_write()'s filemap_write_and_wait() will attempt to write at most 2* the number of pages which are in cache for that inode.

See write_cache_pages:

if (wbc->sync_mode != WB_SYNC_NONE)

        wait_on_page_writeback(page);	(1)
if (PageWriteback(page) ||
    !clear_page_dirty_for_io(page)) {
        unlock_page(page);		(2)
        continue;
}
ret = (*writepage)(page, wbc, data);
if (unlikely(ret == AOP_WRITEPAGE_ACTIVATE)) {
        unlock_page(page);
        ret = 0;
}
if (ret || (--(wbc->nr_to_write) <= 0))
        done = 1;
Quoted 8 lines
Quoted 4 lines
Quoted 4 lines

--- so if it goes by points (1) and (2), the counter is not decremented, yet the function waits for the page. If there is constant stream of writeback pages being generated, it waits on each on them --- that is, forever.

*What* is, forever? Data integrity syncs should have pages operated on in-order, until we get to the end of the range. Circular writeback could go through again, possibly, but no more than once.

OK, I have been able to reproduce it somewhat. It is not a livelock, but what is happening is that direct IO read basically does an fsync on the file before performing the IO. The fsync gets stuck behind the dd that is dirtying the pages, and ends up following behind it and doing all its IO for it.

The following patch avoids the issue for direct IO, by using the range syncs rather than trying to sync the whole file.

The underlying problem I guess is unchanged. Is it really a problem, though? The way I'd love to solve it is actually by adding another bit or two to the pagecache radix tree, that can be used to transiently tag the tree for future operations. That way we could record the dirty and writeback pages up front, and then only bother with operating on them.

That's *if* it really is a problem. I don't have much pity for someone doing buffered IO and direct IO to the same pages of the same file :)

mm/filemap.c +4 -14
Index: linux-2.6/mm/filemap.c
===================================================================
@@ -1304,11 +1304,8 @@ generic_file_aio_read(struct kiocb *iocb
 			goto out; /* skip atime */
 		size = i_size_read(inode);
 		if (pos < size) {
-			retval = filemap_write_and_wait(mapping);
-			if (!retval) {
-				retval = mapping->a_ops->direct_IO(READ, iocb,
+			retval = mapping->a_ops->direct_IO(READ, iocb,
 							iov, pos, nr_segs);
-			}
 			if (retval > 0)
 				*ppos = pos + retval;
 			if (retval) {
@@ -2110,18 +2107,10 @@ generic_file_direct_write(struct kiocb *
 	if (count != ocount)
 		*nr_segs = iov_shorten((struct iovec *)iov, *nr_segs, count);
 
-	/*
-	 * Unmap all mmappings of the file up-front.
-	 *
-	 * This will cause any pte dirty bits to be propagated into the
-	 * pageframes for the subsequent filemap_write_and_wait().
-	 */
 	write_len = iov_length(iov, *nr_segs);
 	end = (pos + write_len - 1) >> PAGE_CACHE_SHIFT;
-	if (mapping_mapped(mapping))
-		unmap_mapping_range(mapping, pos, write_len, 0);
 
-	written = filemap_write_and_wait(mapping);
+	written = filemap_write_and_wait_range(mapping, pos, pos + write_len - 1);
 	if (written)
 		goto out;
 
@@ -2507,7 +2496,8 @@ generic_file_buffered_write(struct kiocb
 	 * the file data here, to try to honour O_DIRECT expectations.
 	 */
 	if (unlikely(file->f_flags & O_DIRECT) && written)
-		status = filemap_write_and_wait(mapping);
+		status = filemap_write_and_wait_range(mapping,
+					pos, pos + written - 1);
 
 	return written ? written : status;
 }
#56 lore raw
Quoted 13 lines
Quoted 3 lines

*What* is, forever? Data integrity syncs should have pages operated on in-order, until we get to the end of the range. Circular writeback could go through again, possibly, but no more than once.

OK, I have been able to reproduce it somewhat. It is not a livelock, but what is happening is that direct IO read basically does an fsync on the file before performing the IO. The fsync gets stuck behind the dd that is dirtying the pages, and ends up following behind it and doing all its IO for it.

The following patch avoids the issue for direct IO, by using the range syncs rather than trying to sync the whole file.

Quoted 8 lines

The underlying problem I guess is unchanged. Is it really a problem, though? The way I'd love to solve it is actually by adding another bit or two to the pagecache radix tree, that can be used to transiently tag the tree for future operations. That way we could record the dirty and writeback pages up front, and then only bother with operating on them.

That's *if* it really is a problem. I don't have much pity for someone doing buffered IO and direct IO to the same pages of the same file :)

LVM does (that is where the bug was discovered). Basically, it scans all the block devices with direct IO and if someone else does buffered IO on any device simultaneously, it locks up.

That fsync-vs-write livelock is quite improbably (why would some application do it?) --- although it could be used as a DoS --- getting unkillable process.

But there is another possible real-world problem --- sync-vs-write --- i.e. admin plugs in two disks and copies data from one to the other. Meanwhile, some unrelated server process executes sync(). The server goes into coma until the copy finishes.

Mikulas

#57 lore raw
Quoted 19 lines · Mikulas Patocka
Quoted 19 lines
Quoted 3 lines

*What* is, forever? Data integrity syncs should have pages operated on in-order, until we get to the end of the range. Circular writeback could go through again, possibly, but no more than once.

OK, I have been able to reproduce it somewhat. It is not a livelock, but what is happening is that direct IO read basically does an fsync on the file before performing the IO. The fsync gets stuck behind the dd that is dirtying the pages, and ends up following behind it and doing all its IO for it.

The following patch avoids the issue for direct IO, by using the range syncs rather than trying to sync the whole file.

The underlying problem I guess is unchanged. Is it really a problem, though? The way I'd love to solve it is actually by adding another bit or two to the pagecache radix tree, that can be used to transiently tag the tree for future operations. That way we could record the dirty and writeback pages up front, and then only bother with operating on them.

Quoted 6 lines
Quoted 2 lines

That's *if* it really is a problem. I don't have much pity for someone doing buffered IO and direct IO to the same pages of the same file :)

LVM does (that is where the bug was discovered). Basically, it scans all the block devices with direct IO and if someone else does buffered IO on any device simultaneously, it locks up.

Scans all block devices with direct IO? Hmm, why, I wonder? Should really consider using buffered (posix_fadvise to readahead/dropbehind).

Quoted 3 lines

That fsync-vs-write livelock is quite improbably (why would some application do it?) --- although it could be used as a DoS --- getting unkillable process.

I'm not sure.

#58 lore raw
Quoted 6 lines
Quoted 3 lines

LVM does (that is where the bug was discovered). Basically, it scans all the block devices with direct IO and if someone else does buffered IO on any device simultaneously, it locks up.

Scans all block devices with direct IO? Hmm, why, I wonder? Should really consider using buffered (posix_fadvise to readahead/dropbehind).

LVM must not allocate any memory when doing IO because it suspends the block device and memory allocation could trigger writeback on the suspended device and deadlock.

So it preallocates heap and stack, mlockall()s itself and does direct IO.

Well, there are still two allocations on direct IO path --- one in __blockdev_direct_IO and the other in dio_bio_alloc. If you have an idea how to get rid of them (especially that kzalloc(sizeof(*dio), GFP_KERNEL), that bio allocation would be quite easy to avoid), it would be benefical.

Mikulas

#59 lore raw
Quoted 9 lines · Mikulas Patocka
Quoted 5 lines
Quoted 3 lines

LVM does (that is where the bug was discovered). Basically, it scans all the block devices with direct IO and if someone else does buffered IO on any device simultaneously, it locks up.

Scans all block devices with direct IO? Hmm, why, I wonder? Should really consider using buffered (posix_fadvise to readahead/dropbehind).

LVM must not allocate any memory when doing IO because it suspends the block device and memory allocation could trigger writeback on the suspended device and deadlock.
So it preallocates heap and stack, mlockall()s itself and does direct IO.

True, but unrelated to the scanning, which LVM performs *prior* to entering such a state.

We use direct IO while scanning because it's essential all nodes in a cluster see the same updated version of the data after any node updated it.

Alasdair

Signature · 1 line
[email protected]
#60 lore raw
In reply to Nick Piggin
Quoted 6 lines · Nick Piggin
Quoted 3 lines · Mikulas Patocka

LVM does (that is where the bug was discovered). Basically, it scans all the block devices with direct IO and if someone else does buffered IO on any device simultaneously, it locks up.

Scans all block devices with direct IO? Hmm, why, I wonder? Should really consider using buffered (posix_fadvise to readahead/dropbehind).

Scan in the sense of it reading a few sectors from each potential LVM device to check whether it contains an LVM label.

Alasdair

Signature · 1 line
[email protected]
#61 lore raw

application syncing options (was Re: [PATCH] Memory management livelock)

In reply to Nick Piggin
Quoted 13 lines · Nick Piggin
Quoted 3 lines

*What* is, forever? Data integrity syncs should have pages operated on in-order, until we get to the end of the range. Circular writeback could go through again, possibly, but no more than once.

OK, I have been able to reproduce it somewhat. It is not a livelock, but what is happening is that direct IO read basically does an fsync on the file before performing the IO. The fsync gets stuck behind the dd that is dirtying the pages, and ends up following behind it and doing all its IO for it.

The following patch avoids the issue for direct IO, by using the range syncs rather than trying to sync the whole file.

Quoted 8 lines

The underlying problem I guess is unchanged. Is it really a problem, though? The way I'd love to solve it is actually by adding another bit or two to the pagecache radix tree, that can be used to transiently tag the tree for future operations. That way we could record the dirty and writeback pages up front, and then only bother with operating on them.

That's *if* it really is a problem. I don't have much pity for someone doing buffered IO and direct IO to the same pages of the same file :)

I've seen lots of discussions here about different options in syncing. in this case a fix is to do a fsync of a range. I've also seen discussions of how the kernel filesystem code can do ordered writes without having to wait for them with the use of barriers, is this capability exported to userspace? if so, could you point me at documentation for it?

David Lang

#62 lore raw

Re: application syncing options (was Re: [PATCH] Memory management livelock)

Quoted 21 lines · On Fri, 3 Oct 2008, [email protected] wrote:
Quoted 19 lines · Nick Piggin
Quoted 3 lines

*What* is, forever? Data integrity syncs should have pages operated on in-order, until we get to the end of the range. Circular writeback could go through again, possibly, but no more than once.

OK, I have been able to reproduce it somewhat. It is not a livelock, but what is happening is that direct IO read basically does an fsync on the file before performing the IO. The fsync gets stuck behind the dd that is dirtying the pages, and ends up following behind it and doing all its IO for it.

The following patch avoids the issue for direct IO, by using the range syncs rather than trying to sync the whole file.

The underlying problem I guess is unchanged. Is it really a problem, though? The way I'd love to solve it is actually by adding another bit or two to the pagecache radix tree, that can be used to transiently tag the tree for future operations. That way we could record the dirty and writeback pages up front, and then only bother with operating on them.

Quoted 5 lines
Quoted 2 lines

That's *if* it really is a problem. I don't have much pity for someone doing buffered IO and direct IO to the same pages of the same file :)

I've seen lots of discussions here about different options in syncing. in this case a fix is to do a fsync of a range.

It fixes the bug in concurrent direct read+buffed write, but won't fix the bug with concurrent sync+buffered write.

Quoted 4 lines

I've also seen discussions of how the
kernel filesystem code can do ordered writes without having to wait for them with the use of barriers, is this capability exported to userspace? if so, could you point me at documentation for it?

It isn't. And it is good that it isn't --- the more complicated API, the more maintenance work.

Mikulas

Quoted 2 lines

David Lang

#63 lore raw

Re: application syncing options (was Re: [PATCH] Memory management livelock)

Quoted 9 lines · Mikulas Patocka
Quoted 4 lines · On Fri, 3 Oct 2008, [email protected] wrote:

I've also seen discussions of how the
kernel filesystem code can do ordered writes without having to wait for them with the use of barriers, is this capability exported to userspace? if so, could you point me at documentation for it?

It isn't. And it is good that it isn't --- the more complicated API, the more maintenance work.

I can understand that most software would not want to deal with complications like this, but for things thta have requirements similar to journaling filesystems (databases for example) it would seem that there would be advantages to exposing this capabilities.

David Lang

#64 lore raw

Re: application syncing options (was Re: [PATCH] Memory management livelock)

Quoted 13 lines · On Sun, 5 Oct 2008, [email protected] wrote:
Quoted 10 lines · Mikulas Patocka
Quoted 5 lines · On Fri, 3 Oct 2008, [email protected] wrote:

I've also seen discussions of how the
kernel filesystem code can do ordered writes without having to wait for them
with the use of barriers, is this capability exported to userspace? if so, could you point me at documentation for it?

It isn't. And it is good that it isn't --- the more complicated API, the more maintenance work.

Quoted 6 lines

I can understand that most software would not want to deal with complications like this, but for things thta have requirements similar to journaling filesystems (databases for example) it would seem that there would be advantages to exposing this capabilities.

David Lang

If you invent new interface that allows submitting several ordered IOs from userspace, it will require excessive maintenance overhead over long period of time. So it should be only justified, if the performance improvement is excessive as well.

It should not be like "here you improve 10% performance on some synthetic benchmark in one application that was rewritten to support the new interface" and then create a few more security vulnerabilities (because of the complexity of the interface) and damage overall Linux progress, because everyone is catching bugs in the new interface and checking it for correctness.

Mikulas

#65 lore raw

Re: application syncing options (was Re: [PATCH] Memory management livelock)

Quoted 27 lines · Mikulas Patocka
Quoted 13 lines · On Sun, 5 Oct 2008, [email protected] wrote:
Quoted 10 lines · Mikulas Patocka
Quoted 5 lines · On Fri, 3 Oct 2008, [email protected] wrote:

I've also seen discussions of how the
kernel filesystem code can do ordered writes without having to wait for them
with the use of barriers, is this capability exported to userspace? if so, could you point me at documentation for it?

It isn't. And it is good that it isn't --- the more complicated API, the more maintenance work.

Quoted 6 lines

I can understand that most software would not want to deal with complications like this, but for things thta have requirements similar to journaling filesystems (databases for example) it would seem that there would be advantages to exposing this capabilities.

David Lang

If you invent new interface that allows submitting several ordered IOs from userspace, it will require excessive maintenance overhead over long period of time. So it should be only justified, if the performance improvement is excessive as well.

Quoted 6 lines

It should not be like "here you improve 10% performance on some synthetic benchmark in one application that was rewritten to support the new interface" and then create a few more security vulnerabilities (because of the complexity of the interface) and damage overall Linux progress, because everyone is catching bugs in the new interface and checking it for correctness.

the same benchmarks that show that it's far better for the in-kernel filesystem code to use write barriers should apply for FUSE filesystems.

this isn't a matter of a few % in performance, if an application is sync-limited in a way that can be converted to write-ordered the potential is for the application to speed up my many times.

programs that maintain indexes or caches of data that lives in other files will be able to write data && barrier && write index && fsync and double their performance vs write data && fsync && write index && fsync

databases can potentially do even better, today they need to fsync data to disk before they can update their journal to indicate that the data has been written, with a barrier they could order the writes so that the write to the journal doesn't happen until the writes of the data. they would neve need to call an fsync at all (when emptying the journal)

for systems without solid-state drives or battery-backed caches, the ability to eliminate fsyncs by being able to rely on the order of the writes is a huge benifit.

David Lang

#66 lore raw

Re: application syncing options (was Re: [PATCH] Memory management livelock)

Quoted 12 lines
Quoted 11 lines

If you invent new interface that allows submitting several ordered IOs from userspace, it will require excessive maintenance overhead over long period of time. So it should be only justified, if the performance improvement is excessive as well.

It should not be like "here you improve 10% performance on some synthetic benchmark in one application that was rewritten to support the new interface" and then create a few more security vulnerabilities (because of the complexity of the interface) and damage overall Linux progress, because everyone is catching bugs in the new interface and checking it for correctness.

Quoted 2 lines

the same benchmarks that show that it's far better for the in-kernel filesystem code to use write barriers should apply for FUSE filesystems.

FUSE is slow by design, and it is used in cases where performance isn't crucial.

Quoted 7 lines

this isn't a matter of a few % in performance, if an application is sync-limited in a way that can be converted to write-ordered the potential is for the application to speed up my many times.

programs that maintain indexes or caches of data that lives in other files will be able to write data && barrier && write index && fsync and double their performance vs write data && fsync && write index && fsync

They can do: write data with O_SYNC; write another piece of data with O_SYNC.

And the only difference from barriers is the waiting time after the first O_SYNC before the second I/O is submitted (such delay wouldn't happen with barriers).

And now I/O delay is in milliseconds and process wakeup time is tens of microseconds, it doesn't look like eliminating process wakeup time would do more than few percents.

Quoted 5 lines

databases can potentially do even better, today they need to fsync data to disk before they can update their journal to indicate that the data has been written, with a barrier they could order the writes so that the write to the journal doesn't happen until the writes of the data. they would neve need to call an fsync at all (when emptying the journal)

Good databases can pack several user transactions into one fsync() write. If the database server is properly engineered, it accumulates all user transactions committed so far into one chunk, writes that chunk with one fsync() call and then reports successful commit to the clients.

So if you increase fsync() latency, it should have no effect on the transactional throughput --- only on latency of transactions. Similarly, if you decrease fsync() latency, it won't increase number of processed transactions.

Certainly, there are primitive embedded database libraries that fsync() after each transaction, but they don't have good performance anyway.

Quoted 3 lines

for systems without solid-state drives or battery-backed caches, the ability to eliminate fsyncs by being able to rely on the order of the writes is a huge benifit.

I may ask --- where are the applications that require extra slow fsync() latency? Databases are not that, they batch transactions.

If you want to improve things, you can try:
* implement O_DSYNC (like O_SYNC, but doesn't update inode mtime)
* implement range_fsync and range_fdatasync (sync on file range --- the kernel has already support for that, you can just add a syscall)
* turn on FUA bit for O_DSYNC writes, that eliminates the need to flush drive cache in O_DSYNC call

--- these are definitely less invasive than new I/O submitting interface.

Mikulas

Quoted 2 lines

David Lang

#67 lore raw

Re: application syncing options (was Re: [PATCH] Memory management livelock)

Quoted 12 lines · Mikulas Patocka
Quoted 12 lines
Quoted 11 lines

If you invent new interface that allows submitting several ordered IOs from userspace, it will require excessive maintenance overhead over long period of time. So it should be only justified, if the performance improvement is excessive as well.

It should not be like "here you improve 10% performance on some synthetic benchmark in one application that was rewritten to support the new interface" and then create a few more security vulnerabilities (because of the complexity of the interface) and damage overall Linux progress, because everyone is catching bugs in the new interface and checking it for correctness.

Quoted 5 lines
Quoted 2 lines

the same benchmarks that show that it's far better for the in-kernel filesystem code to use write barriers should apply for FUSE filesystems.

FUSE is slow by design, and it is used in cases where performance isn't crucial.

FUSE is slow, but I don't believe that it's a design goal for it to be slow, it's a limitation of the implementation. so things that could speed it up would be a good thing.

Quoted 11 lines
Quoted 7 lines

this isn't a matter of a few % in performance, if an application is sync-limited in a way that can be converted to write-ordered the potential is for the application to speed up my many times.

programs that maintain indexes or caches of data that lives in other files will be able to write data && barrier && write index && fsync and double their performance vs write data && fsync && write index && fsync

They can do: write data with O_SYNC; write another piece of data with O_SYNC.

Quoted 7 lines

And the only difference from barriers is the waiting time after the first O_SYNC before the second I/O is submitted (such delay wouldn't happen with barriers).

And now I/O delay is in milliseconds and process wakeup time is tens of microseconds, it doesn't look like eliminating process wakeup time would do more than few percents.

each sync write needs to wait for a disk rotation (and a seek if you are writing to different files). if you only do two writes you save one disk rotation, if you do five writes you save four disk rotations

Quoted 10 lines
Quoted 5 lines

databases can potentially do even better, today they need to fsync data to disk before they can update their journal to indicate that the data has been written, with a barrier they could order the writes so that the write to the journal doesn't happen until the writes of the data. they would neve need to call an fsync at all (when emptying the journal)

Good databases can pack several user transactions into one fsync() write. If the database server is properly engineered, it accumulates all user transactions committed so far into one chunk, writes that chunk with one fsync() call and then reports successful commit to the clients.

if there are multiple users doing transactions at the same time they will benifit from overlapping the fsyncs. but each user session cannot complete their transaction until the fsync completes

Quoted 4 lines

So if you increase fsync() latency, it should have no effect on the transactional throughput --- only on latency of transactions. Similarly, if you decrease fsync() latency, it won't increase number of processed transactions.

only if you have all your transactions happening in parallel. in the real world programs sometimes need to wait for one transaction to complete so that they can do the next one.

Quoted 10 lines

Certainly, there are primitive embedded database libraries that fsync() after each transaction, but they don't have good performance anyway.

Quoted 3 lines

for systems without solid-state drives or battery-backed caches, the ability to eliminate fsyncs by being able to rely on the order of the writes is a huge benifit.

I may ask --- where are the applications that require extra slow fsync() latency? Databases are not that, they batch transactions.

Quoted 8 lines

If you want to improve things, you can try:
* implement O_DSYNC (like O_SYNC, but doesn't update inode mtime)
* implement range_fsync and range_fdatasync (sync on file range --- the kernel has already support for that, you can just add a syscall)
* turn on FUA bit for O_DSYNC writes, that eliminates the need to flush drive cache in O_DSYNC call

--- these are definitely less invasive than new I/O submitting interface.

but all of these require that the application stop and wait for each seperate write to take place before proceeding to the next step.

if this doesn't matter, then why the big push to have the in-kernel filesystems start using barriers? I understood that this resulted in large performance increases in the places that they are used from just being able to avoid having to drain the entire request queue, and you are saying that the applications would not only need to wait for the queue to flush, but for the disk to acknowledge the write.

syncs are slow, in some cases _very_ slow.

David Lang