probably bug in current ext3/jbd

hi!

ext3/jbd use b_committed_data buffer in order to prevent allocation of blocks which were freed in non-committed transaction. I think there is bug in this code. look,

some thread commit thread
----------------------------------------------------------
get_undo_access(#1)
dirty_buffer(#1)
stop_journal()

start commit

start_journal()
get_undo_access(#1):
1) wait for #1 to be
in t_forget_list

write #1 to log put #1 onto t_forget_list

2) b_commit_data exists,

      finish get_undo_access()


                                           for_each_bh_in_forget_list() {
                                              if (jh->b_committed_data) {
                                                  kfree(jh->b_committed_data);
                                                  jh->b_committed_data = NULL;
                                              }
                                           }

/* using of b_committed_data */

b_committed_data is NULL ?

with best regards, Alex

Hi,

You just found a rather subtle bug which was fixed around 2 or 3 years ago. :-)

get_undo_access is a declaration of intention to modify the buffer. When that happens, it calls do_get_write_access() with the force_copy flag set. That means that it _always_ creates a new frozen_data copy of the buffer the first time we get undo access to a bitmap buffer within any given transaction. That basically means that for bitmaps, frozen_data always holds the version of the buffer as of the end of the previously completed transaction.

Ah, but the *immediately* following lines are:

			if (jh->b_frozen_data) {
				jh->b_committed_data = jh->b_frozen_data;
				jh->b_frozen_data = NULL;
			}

so the frozen data that was preserved at get_undo_access() time has now committed to disk and gets rotated into the b_committed_data version. This is exactly how we get the new version of the committed data when the old transaction commits.

Cheers,
Stephen

hi!

please, look:

thread A commit thread

                        	    if (jh->b_committed_data) {
                                	kfree(jh->b_committed_data);
                                        jh->b_committed_data = NULL;
                                    }

access for
b_committed_data == NULL ?

                                         if (jh->b_frozen_data) {
                                            jh->b_committed_data = jh->b_frozen_data;
                                            jh->b_frozen_data = NULL;
                                          }

or I miss something subtle here?

SCT> get_undo_access is a declaration of intention to modify the buffer. SCT> When that happens, it calls do_get_write_access() with the force_copy SCT> flag set. That means that it _always_ creates a new frozen_data copy of SCT> the buffer the first time we get undo access to a bitmap buffer within SCT> any given transaction. That basically means that for bitmaps, SCT> frozen_data always holds the version of the buffer as of the end of the SCT> previously completed transaction.

jh-> b_committed_data = NULL;

SCT> Ah, but the *immediately* following lines are:

SCT> if (jh->b_frozen_data) {
jh-> b_committed_data = jh->b_frozen_data;
jh-> b_frozen_data = NULL;
SCT> }

SCT> so the frozen data that was preserved at get_undo_access() time has now SCT> committed to disk and gets rotated into the b_committed_data version. SCT> This is exactly how we get the new version of the committed data when SCT> the old transaction commits.

SCT> Cheers,
SCT> Stephen

Hi,

Not with BKL. Without it, yes, that's definitely a risk, and you need some locking for the access to b_committed_data. Without that, even if you keep the jh->b_committed_data field valid, you risk freeing the old copy that another thread is using.

Cheers,
Stephen

aha. now it's clear. thank you. I catched J_ASSERT(b_committed_data != NULL) in ext3_free_blocks() with de-BKL'ed JBD. hence, my solution is to have a tid journal_head indicating which transaction uses b_committed_data.

I don't want to look intrusive, but .. what do you think about new locking schema I'm trying to implement?

SCT> Not with BKL. Without it, yes, that's definitely a risk, and you need SCT> some locking for the access to b_committed_data. Without that, even if SCT> you keep the jh->b_committed_data field valid, you risk freeing the old SCT> copy that another thread is using.

SCT> Cheers,
SCT> Stephen

hmm.
looks Andrew Morton should return BKL in ext3_get_block_handle() in -mm tree? this BKL protects ext3_alloc_branch() -> ext3_alloc_block() -> ext3_new_block() call chain. or we may implement new protection schema where each jh has some reference alike 'used by transaction N'

Andrew?

SCT> Not with BKL. Without it, yes, that's definitely a risk, and you need SCT> some locking for the access to b_committed_data. Without that, even if SCT> you keep the jh->b_committed_data field valid, you risk freeing the old SCT> copy that another thread is using.

Can this be solved by spinlocking the relevant buffer_head, in a similar way to your recent changes to journal_add_journal_head()?

AM> Can this be solved by spinlocking the relevant buffer_head, in a similar AM> way to your recent changes to journal_add_journal_head()?

yes, we may protect it by such lock, but this lock have to be held all time ext3_new_block() uses some b_committed_data because last one may be freed during current ext3_new_block(). I don't think it's good.

probably, another solution is do not free b_committed_data if it's referenced by new transaction and make copy from b_frozen instead of freeing it.

Take a closer look - I don't think it'll be too messy, and certainly the hold times will not be a problem.

hi!

here is small patch that intented to fix race with b_committed_data. also, as Andrew asked I introduced new bit-based spinlock and converted pte_chain_lock()/pte_chain_unlock() to use that one. patch tested by dbench 1/2/4/6/8/16/24.

with best regards, Alex

diff -puNr linux-2.5.69-mm6/include/linux/rmap-locking.h b_commited_data-race/include/linux/rmap-locking.h
@@ -10,32 +10,8 @@
 struct pte_chain;
 extern kmem_cache_t *pte_chain_cache;
 
-static inline void pte_chain_lock(struct page *page)
-{
-	/*
-	 * Assuming the lock is uncontended, this never enters
-	 * the body of the outer loop. If it is contended, then
-	 * within the inner loop a non-atomic test is used to
-	 * busywait with less bus contention for a good time to
-	 * attempt to acquire the lock bit.
-	 */
-	preempt_disable();
-#ifdef CONFIG_SMP
-	while (test_and_set_bit(PG_chainlock, &page->flags)) {
-		while (test_bit(PG_chainlock, &page->flags))
-			cpu_relax();
-	}
-#endif
-}
-
-static inline void pte_chain_unlock(struct page *page)
-{
-#ifdef CONFIG_SMP
-	smp_mb__before_clear_bit();
-	clear_bit(PG_chainlock, &page->flags);
-#endif
-	preempt_enable();
-}
+#define pte_chain_lock(page)	bb_spin_lock(PG_chainlock, &page->flags)
+#define pte_chain_unlock(page)	bb_spin_unlock(PG_chainlock, &page->flags)
 
 struct pte_chain *pte_chain_alloc(int gfp_flags);
 void __pte_chain_free(struct pte_chain *pte_chain);

diff -puNr linux-2.5.69-mm6/include/linux/jbd.h b_commited_data-race/include/linux/jbd.h
@@ -292,6 +292,7 @@ enum jbd_state_bits {
 	BH_Revoked,		/* Has been revoked from the log */
 	BH_RevokeValid,		/* Revoked flag is valid */
 	BH_JBDDirty,		/* Is dirty but journaled */
+	BH_JLock,		/* Buffer is locked for short time */
 };
 
 BUFFER_FNS(JBD, jbd)

@@ -308,6 +309,9 @@ static inline struct journal_head *bh2jh
 {
 	return bh->b_private;
 }
+
+#define jbd_lock_bh(bh)		bb_spin_lock(BH_JLock, &bh->b_state)
+#define jbd_unlock_bh(bh)	bb_spin_unlock(BH_JLock, &bh->b_state)
 
 #define HAVE_JOURNAL_CALLBACK_STATUS
 /**

diff -puNr linux-2.5.69-mm6/fs/jbd/commit.c b_commited_data-race/fs/jbd/commit.c
@@ -686,12 +686,14 @@ skip_commit: /* The journal should be un
 		 * Otherwise, we can just throw away the frozen data now.
 		 */
 		if (jh->b_committed_data) {
+			jbd_lock_bh(jh2bh(jh));
 			kfree(jh->b_committed_data);
 			jh->b_committed_data = NULL;
 			if (jh->b_frozen_data) {
 				jh->b_committed_data = jh->b_frozen_data;
 				jh->b_frozen_data = NULL;
 			}
+			jbd_unlock_bh(jh2bh(jh));
 		} else if (jh->b_frozen_data) {
 			kfree(jh->b_frozen_data);
 			jh->b_frozen_data = NULL;

diff -puNr linux-2.5.69-mm6/fs/ext3/balloc.c b_commited_data-race/fs/ext3/balloc.c
@@ -185,11 +185,14 @@ do_more:
 	if (err)
 		goto error_return;
 
+	jbd_lock_bh(bitmap_bh);
+	
 	for (i = 0; i < count; i++) {
 		/*
 		 * An HJ special.  This is expensive...
 		 */
 #ifdef CONFIG_JBD_DEBUG
+		jbd_unlock_bh(bitmap_bh);
 		{
 			struct buffer_head *debug_bh;
 			debug_bh = sb_find_get_block(sb, block + i);

@@ -202,6 +205,7 @@ do_more:
 				__brelse(debug_bh);
 			}
 		}
+		jbd_lock_bh(bitmap_bh);
 #endif
 		/* @@@ This prevents newly-allocated data from being
 		 * freed and then reallocated within the same

@@ -243,6 +247,7 @@ do_more:
 			dquot_freed_blocks++;
 		}
 	}
+	jbd_unlock_bh(bitmap_bh);
 
 	spin_lock(sb_bgl_lock(sbi, block_group));
 	gdp->bg_free_blocks_count =

@@ -289,11 +294,12 @@ error_return:
  * data-writes at some point, and disable it for metadata allocations or
  * sync-data inodes.
  */
-static int ext3_test_allocatable(int nr, struct buffer_head *bh)
+static inline int ext3_test_allocatable(int nr, struct buffer_head *bh,
+					int have_access)
 {
 	if (ext3_test_bit(nr, bh->b_data))
 		return 0;
-	if (!buffer_jbd(bh) || !bh2jh(bh)->b_committed_data)
+	if (!have_access || !buffer_jbd(bh) || !bh2jh(bh)->b_committed_data)
 		return 1;
 	return !ext3_test_bit(nr, bh2jh(bh)->b_committed_data);
 }

@@ -305,8 +311,8 @@ static int ext3_test_allocatable(int nr,
  * the initial goal; then for a free byte somewhere in the bitmap; then
  * for any free bit in the bitmap.
  */
-static int find_next_usable_block(int start,
-			struct buffer_head *bh, int maxblocks)
+static int find_next_usable_block(int start, struct buffer_head *bh,
+				int maxblocks, int have_access)
 {
 	int here, next;
 	char *p, *r;

@@ -322,7 +328,8 @@ static int find_next_usable_block(int st
 		 */
 		int end_goal = (start + 63) & ~63;
 		here = ext3_find_next_zero_bit(bh->b_data, end_goal, start);
-		if (here < end_goal && ext3_test_allocatable(here, bh))
+		if (here < end_goal &&
+			ext3_test_allocatable(here, bh, have_access))
 			return here;
 		
 		ext3_debug ("Bit not found near goal\n");

@@ -345,7 +352,7 @@ static int find_next_usable_block(int st
 	r = memscan(p, 0, (maxblocks - here + 7) >> 3);
 	next = (r - ((char *) bh->b_data)) << 3;
 	
-	if (next < maxblocks && ext3_test_allocatable(next, bh))
+	if (next < maxblocks && ext3_test_allocatable(next, bh, have_access))
 		return next;
 	
 	/* The bitmap search --- search forward alternately

@@ -357,13 +364,13 @@ static int find_next_usable_block(int st
 						 maxblocks, here);
 		if (next >= maxblocks)
 			return -1;
-		if (ext3_test_allocatable(next, bh))
+		if (ext3_test_allocatable(next, bh, have_access))
 			return next;
 
-		J_ASSERT_BH(bh, bh2jh(bh)->b_committed_data);
-		here = ext3_find_next_zero_bit
-			((unsigned long *) bh2jh(bh)->b_committed_data, 
-			 maxblocks, next);
+		if (have_access)
+			here = ext3_find_next_zero_bit
+				((unsigned long *) bh2jh(bh)->b_committed_data, 
+			 	maxblocks, next);
 	}
 	return -1;
 }

@@ -402,17 +409,18 @@ ext3_try_to_allocate(struct super_block 
 
 	*errp = 0;
 
-	if (goal >= 0 && ext3_test_allocatable(goal, bitmap_bh))
+	if (goal >= 0 && ext3_test_allocatable(goal, bitmap_bh, 0))
 		goto got;
 
 repeat:
 	goal = find_next_usable_block(goal, bitmap_bh,
-				EXT3_BLOCKS_PER_GROUP(sb));
+				EXT3_BLOCKS_PER_GROUP(sb), have_access);
 	if (goal < 0)
 		goto fail;
 
 	for (i = 0;
-		i < 7 && goal > 0 && ext3_test_allocatable(goal - 1, bitmap_bh);
+		i < 7 && goal > 0 && 
+			ext3_test_allocatable(goal - 1, bitmap_bh, have_access);
 		i++, goal--);
 
 got:

@@ -429,6 +437,7 @@ got:
 			*errp = fatal;
 			goto fail;
 		}
+		jbd_lock_bh(bitmap_bh);
 		have_access = 1;
 	}
 

@@ -444,6 +453,7 @@ got:
 	}
 
 	BUFFER_TRACE(bitmap_bh, "journal_dirty_metadata for bitmap block");
+	jbd_unlock_bh(bitmap_bh);
 	fatal = ext3_journal_dirty_metadata(handle, bitmap_bh);
 	if (fatal) {
 		*errp = fatal;

@@ -454,6 +464,7 @@ got:
 fail:
 	if (have_access) {
 		BUFFER_TRACE(bitmap_bh, "journal_release_buffer");
+		jbd_unlock_bh(bitmap_bh);
 		ext3_journal_release_buffer(handle, bitmap_bh);
 	}
 	return -1;

diff -puNr linux-2.5.69-mm6/include/linux/spinlock.h b_commited_data-race/include/linux/spinlock.h
@@ -540,4 +540,37 @@ do { \
 extern int atomic_dec_and_lock(atomic_t *atomic, spinlock_t *lock);
 #endif
 
+/*
+ *  bit-based spin_lock()
+ */
+static inline void bb_spin_lock(int bitnum, unsigned long *addr)
+{
+	/*
+	 * Assuming the lock is uncontended, this never enters
+	 * the body of the outer loop. If it is contended, then
+	 * within the inner loop a non-atomic test is used to
+	 * busywait with less bus contention for a good time to
+	 * attempt to acquire the lock bit.
+	 */
+	preempt_disable();
+#ifdef CONFIG_SMP
+	while (test_and_set_bit(bitnum, addr)) {
+		while (test_bit(bitnum, addr))
+			cpu_relax();
+	}
+#endif
+}
+
+/*
+ *  bit-based spin_unlock()
+ */
+static inline void bb_spin_unlock(int bitnum, unsigned long *addr)
+{
+#ifdef CONFIG_SMP
+	smp_mb__before_clear_bit();
+	clear_bit(bitnum, addr);
+#endif
+	preempt_enable();
+}
+
 #endif /* __LINUX_SPINLOCK_H */

Thanks, it looks good.

The balloc.c code is getting awfully convoluted and hard to follow, but no obvious restructuring strategies are leaping out at me.

AM> The balloc.c code is getting awfully convoluted and hard to follow, AM> but no obvious restructuring strategies are leaping out at me.

agree. I'll try to figure out something more readable sometime

hi!

I think current journal_release_buffer() which is used by ext3 allocator in -mm tree has a bug. look, it won't decrement credits if concurrent thread already put buffer on metadata list. but this may ext3_try_to_allocate() may overflow handle's credist.
so, jbd will hit J_ASSERT_JH(jh, handle->h_buffer_credits > 0) somewhere

void journal_release_buffer (handle_t *handle, struct buffer_head *bh)

{
        .....
        if (jh->b_jlist == BJ_Reserved && jh->b_transaction == transaction &&
            !buffer_jdirty(jh2bh(jh))) {
                JBUFFER_TRACE(jh, "unused: refiling it");
                handle->h_buffer_credits++;
                __journal_refile_buffer(jh);
        }
        ....
}

here is the patch against 2.5.69-mm6:

diff -puNr linux-2.5.69-mm6/fs/jbd/transaction.c edited/fs/jbd/transaction.c
@@ -1146,10 +1146,10 @@ void journal_release_buffer (handle_t *h
 	if (jh->b_jlist == BJ_Reserved && jh->b_transaction == transaction &&
 	    !buffer_jdirty(jh2bh(jh))) {
 		JBUFFER_TRACE(jh, "unused: refiling it");
-		handle->h_buffer_credits++;
 		__journal_refile_buffer(jh);
 	}
 	spin_unlock(&journal_datalist_lock);
+	handle->h_buffer_credits++;
 
 	JBUFFER_TRACE(jh, "exit");
 	unlock_journal(journal);

Yes, that is so.

But some other handle has gained itself a free buffer. That is actually harmless, except for one thing: as the handles are closed down, ->t_outstanding_credits will be too small. We could conceivably end up overflowing the journal.

umm, one possible solution to that is to rework the t_outstanding_credits logic so that we instead record:

number of buffers attached to the transaction +
sum of the initial size of all currently-running handles.

as each handle is closed off, we subtract its initial size from the above metric. Any buffers which that handle happened to add to the lists would have already been accounted for, when they were added.

I _think_ that'll work...

One other benefit of doing it that way is that having the original handle size kept in the handle means that you can properly flag errors when a nested transaction is "started" on an existing handle and the new start wants more credits than were actually in the handle.

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/