Re: [PATCH] Significant performace improvements on reiserfs systems

Re: [PATCH] Significant performace improvements on reiserfs systems

[Chris Mason]

On Thursday, September 20, 2001 07:08:25 PM +0200 Dieter Nützel
<Dieter.Nuetzel@hamburg.de> wrote:


> Please have a look at Robert Love's Linux kernel preemption patches and
> the  conversation about my reported latency results.
> 

Andrew Morton has patches that significantly improve the reiserfs latency,
looks like the last one he sent me was 2.4.7-pre9.  He and I did a bunch of
work to make sure they introduce schedules only when it was safe.

Andrew, are these still maintained or should I pull out the reiserfs bits?

-chris

Re: [PATCH] Significant performace improvements on reiserfs systems

[Andrew Morton]

Chris Mason wrote:
> 
> On Thursday, September 20, 2001 07:08:25 PM +0200 Dieter Nützel
> <Dieter.Nuetzel@hamburg.de> wrote:
> 
> > Please have a look at Robert Love's Linux kernel preemption patches and
> > the  conversation about my reported latency results.
> >
> 
> Andrew Morton has patches that significantly improve the reiserfs latency,
> looks like the last one he sent me was 2.4.7-pre9.  He and I did a bunch of
> work to make sure they introduce schedules only when it was safe.
> 
> Andrew, are these still maintained or should I pull out the reiserfs bits?
> 

This is the reiserfs part - it applies to 2.4.10-pre12 OK.

For the purposes of Robert's patch, conditional_schedule()
should be defined as 

	if (current->need_resched && current->lock_depth == 0) {
		unlock_kernel();
		lock_kernel();
	}

which is somewhat crufty, because the implementation of lock_kernel()
is arch-specific.  But all architectures seem to implement it the same way.



--- linux-2.4.7/include/linux/reiserfs_fs.h	Sat Jul 21 12:37:14 2001
+++ linux-akpm/include/linux/reiserfs_fs.h	Sun Jul 22 22:06:17 2001
@@ -1165,8 +1165,8 @@ extern inline loff_t max_reiserfs_offset
 #define fs_generation(s) ((s)->u.reiserfs_sb.s_generation_counter)
 #define get_generation(s) atomic_read (&fs_generation(s))
 #define FILESYSTEM_CHANGED_TB(tb)  (get_generation((tb)->tb_sb) != (tb)->fs_gen)
-#define fs_changed(gen,s) (gen != get_generation (s))
-
+#define __fs_changed(gen,s) (gen != get_generation (s))
+#define fs_changed(gen,s) ({conditional_schedule(); __fs_changed(gen,s);})
 
 /***************************************************************************/
 /*                  FIXATE NODES                                           */
--- linux-2.4.7/fs/reiserfs/bitmap.c	Wed May  2 22:00:06 2001
+++ linux-akpm/fs/reiserfs/bitmap.c	Sun Jul 22 22:06:17 2001
@@ -420,19 +420,31 @@ free_and_return:
     }
        
 
-    reiserfs_prepare_for_journal(s, SB_AP_BITMAP(s)[i], 1) ;
 
+/* this check needs to go before preparing the buffer because that can
+** schedule when low-latency patches are in use.  It is ok if the buffer
+** is locked, preparing it will wait on it, and we handle the case where
+** this block was allocated while we sleep below.
+*/
 #ifdef CONFIG_REISERFS_CHECK
-    if (buffer_locked (SB_AP_BITMAP (s)[i]) || is_reusable (s, search_start, 0) == 0)
-	reiserfs_panic (s, "vs-4140: reiserfs_new_blocknrs: bitmap block is locked or bad block number found");
+    if (is_reusable (s, search_start, 0) == 0)
+	reiserfs_panic (s, "vs-4140: reiserfs_new_blocknrs: bad block number found");
 #endif
 
+    reiserfs_prepare_for_journal(s, SB_AP_BITMAP(s)[i], 1) ;
+
     /* if this bit was already set, we've scheduled, and someone else
     ** has allocated it.  loop around and try again
     */
     if (reiserfs_test_and_set_le_bit (j, SB_AP_BITMAP (s)[i]->b_data)) {
 	reiserfs_warning("vs-4150: reiserfs_new_blocknrs, block not free");
 	reiserfs_restore_prepared_buffer(s, SB_AP_BITMAP(s)[i]) ;
+	/* if this block has been allocated while we slept, it is
+	** impossible to find any more contiguous blocks for ourselves.
+	** If we are doing preallocation, give up now and return.
+	*/
+	if (for_prealloc)
+	    goto free_and_return ;
 	amount_needed++ ;
 	continue ;
     }    
--- linux-2.4.7/fs/reiserfs/buffer2.c	Tue Jan 16 10:31:19 2001
+++ linux-akpm/fs/reiserfs/buffer2.c	Sun Jul 22 22:06:17 2001
@@ -73,7 +73,9 @@ void wait_buffer_until_released (struct 
 
 struct buffer_head  * reiserfs_bread (kdev_t n_dev, int n_block, int n_size) 
 {
-    return bread (n_dev, n_block, n_size);
+    struct buffer_head *ret = bread (n_dev, n_block, n_size);
+    conditional_schedule();
+    return ret;
 }
 
 /* This function looks for a buffer which contains a given block.  If
--- linux-2.4.7/fs/reiserfs/journal.c	Sat Jul 21 12:37:14 2001
+++ linux-akpm/fs/reiserfs/journal.c	Sun Jul 22 22:06:17 2001
@@ -577,6 +577,7 @@ inline void insert_journal_hash(struct r
 
 /* lock the current transaction */
 inline static void lock_journal(struct super_block *p_s_sb) {
+  conditional_schedule();
   while(atomic_read(&(SB_JOURNAL(p_s_sb)->j_wlock)) > 0) {
     sleep_on(&(SB_JOURNAL(p_s_sb)->j_wait)) ;
   }
@@ -706,6 +707,7 @@ reiserfs_panic(s, "journal-539: flush_co
 	mark_buffer_dirty(tbh) ;
       }
       ll_rw_block(WRITE, 1, &tbh) ;
+      conditional_schedule();
       count++ ;
       put_bh(tbh) ; /* once for our get_hash */
     } 
@@ -833,6 +835,7 @@ static int update_journal_header_block(s
     set_bit(BH_Dirty, &(SB_JOURNAL(p_s_sb)->j_header_bh->b_state)) ;
     ll_rw_block(WRITE, 1, &(SB_JOURNAL(p_s_sb)->j_header_bh)) ;
     wait_on_buffer((SB_JOURNAL(p_s_sb)->j_header_bh)) ; 
+    conditional_schedule();
     if (!buffer_uptodate(SB_JOURNAL(p_s_sb)->j_header_bh)) {
       reiserfs_panic(p_s_sb, "journal-712: buffer write failed\n") ;
     }
@@ -2076,6 +2079,7 @@ int journal_join(struct reiserfs_transac
 }
 
 int journal_begin(struct reiserfs_transaction_handle *th, struct super_block  * p_s_sb, unsigned long nblocks) {
+  conditional_schedule();
   return do_journal_begin_r(th, p_s_sb, nblocks, 0) ;
 }
 
@@ -2213,6 +2217,7 @@ int journal_mark_dirty_nolog(struct reis
 }
 
 int journal_end(struct reiserfs_transaction_handle *th, struct super_block *p_s_sb, unsigned long nblocks) {
+  conditional_schedule();
   return do_journal_end(th, p_s_sb, nblocks, 0) ;
 }
 
@@ -2648,6 +2653,7 @@ void reiserfs_prepare_for_journal(struct
       }
 #endif
       wait_on_buffer(bh) ;
+      conditional_schedule();
     }
     retry_count++ ;
   }
@@ -2820,6 +2826,7 @@ printk("journal-2020: do_journal_end: BA
     /* copy all the real blocks into log area.  dirty log blocks */
     if (test_bit(BH_JDirty, &cn->bh->b_state)) {
       struct buffer_head *tmp_bh ;
+      conditional_schedule();		/* getblk can sleep, so... */
       tmp_bh = getblk(p_s_sb->s_dev, reiserfs_get_journal_block(p_s_sb) + 
 		     ((cur_write_start + jindex) % JOURNAL_BLOCK_COUNT), 
 				       p_s_sb->s_blocksize) ;
--- linux-2.4.7/fs/reiserfs/stree.c	Sat Jul 21 12:37:14 2001
+++ linux-akpm/fs/reiserfs/stree.c	Sun Jul 22 22:06:17 2001
@@ -681,9 +681,9 @@ int search_by_key (struct super_block * 
                                        DISK_LEAF_NODE_LEVEL */
     ) {
     kdev_t n_dev = p_s_sb->s_dev;
-    int  n_block_number = SB_ROOT_BLOCK (p_s_sb),
-      expected_level = SB_TREE_HEIGHT (p_s_sb),
-      n_block_size    = p_s_sb->s_blocksize;
+    int n_block_number; 
+    int expected_level;
+    int n_block_size = p_s_sb->s_blocksize;
     struct buffer_head  *       p_s_bh;
     struct path_element *       p_s_last_element;
     int				n_node_level, n_retval;
@@ -694,6 +694,8 @@ int search_by_key (struct super_block * 
     int n_repeat_counter = 0;
 #endif
 
+    conditional_schedule();
+
     /* As we add each node to a path we increase its count.  This means that
        we must be careful to release all nodes in a path before we either
        discard the path struct or re-use the path struct, as we do here. */
@@ -705,6 +707,9 @@ int search_by_key (struct super_block * 
     /* With each iteration of this loop we search through the items in the
        current node, and calculate the next current node(next path element)
        for the next iteration of this loop.. */
+    fs_gen = get_generation (p_s_sb);
+    n_block_number = SB_ROOT_BLOCK (p_s_sb);
+    expected_level = SB_TREE_HEIGHT (p_s_sb);
     while ( 1 ) {
 
 #ifdef CONFIG_REISERFS_CHECK
@@ -1174,6 +1179,8 @@ static char  prepare_for_delete_or_cut(
 	    for ( n_retry = 0, n_counter = *p_n_removed;
 		  n_counter < n_unfm_number; n_counter++, p_n_unfm_pointer-- )  {
 
+		conditional_schedule();
+
 		if (item_moved (&s_ih, p_s_path)) {
 		    need_research = 1 ;
 		    break;
@@ -1191,6 +1198,16 @@ static char  prepare_for_delete_or_cut(
 		}
 		/* Search for the buffer in cache. */
 		p_s_un_bh = get_hash_table(p_s_sb->s_dev, *p_n_unfm_pointer, n_blk_size);
+
+		/* AKPM: this is not _really_ needed.  It takes us from 2,000 usecs to 500 */
+		if (p_s_un_bh && conditional_schedule_needed()) {
+		  unconditional_schedule();
+		  if ( item_moved (&s_ih, p_s_path) )  {
+		      need_research = 1;
+		      brelse(p_s_un_bh) ;
+		      break ;
+		  }
+		}
 
 		if (p_s_un_bh) {
 		    mark_buffer_clean(p_s_un_bh) ;

Re: [PATCH] Significant performace improvements on reiserfs systems

[Andrea Arcangeli]

On Thu, Sep 20, 2001 at 01:19:53PM -0400, Chris Mason wrote:
> 
> 
> On Thursday, September 20, 2001 07:08:25 PM +0200 Dieter Nützel
> <Dieter.Nuetzel@hamburg.de> wrote:
> 
> 
> > Please have a look at Robert Love's Linux kernel preemption patches and
> > the  conversation about my reported latency results.
> > 
> 
> Andrew Morton has patches that significantly improve the reiserfs latency,
> looks like the last one he sent me was 2.4.7-pre9.  He and I did a bunch of
> work to make sure they introduce schedules only when it was safe.
> 
> Andrew, are these still maintained or should I pull out the reiserfs bits?

May not help latency but I suspect this could help reiserfs, it should
basically be a noop for ext2.

--- 2.4.10pre12aa2/fs/buffer.c.~1~	Thu Sep 20 20:14:19 2001
+++ 2.4.10pre12aa2/fs/buffer.c	Thu Sep 20 20:45:58 2001
@@ -2506,7 +2506,7 @@
 	spin_unlock(&free_list[isize].lock);
 
 	page->buffers = bh;
-	page->flags &= ~(1 << PG_referenced);
+	page->flags |= 1 << PG_referenced;
 	lru_cache_add(page);
 	UnlockPage(page);
 	atomic_inc(&buffermem_pages);

You may want to give it a spin.

Andrea

Re: [PATCH] Significant performace improvements on reiserfs systems

[Andrew Morton]

Andrea Arcangeli wrote:
> 
> ...
> --- 2.4.10pre12aa2/fs/buffer.c.~1~      Thu Sep 20 20:14:19 2001
> +++ 2.4.10pre12aa2/fs/buffer.c  Thu Sep 20 20:45:58 2001
> @@ -2506,7 +2506,7 @@
>         spin_unlock(&free_list[isize].lock);
> 
>         page->buffers = bh;
> -       page->flags &= ~(1 << PG_referenced);
> +       page->flags |= 1 << PG_referenced;

I don't see how this can change anything - getblk() calls
touch_buffer() shortly afterwards, which does the same
thing?

Re: [PATCH] Significant performace improvements on reiserfs systems

[Andrea Arcangeli]

On Thu, Sep 20, 2001 at 11:58:53AM -0700, Andrew Morton wrote:
> Andrea Arcangeli wrote:
> > 
> > ...
> > --- 2.4.10pre12aa2/fs/buffer.c.~1~      Thu Sep 20 20:14:19 2001
> > +++ 2.4.10pre12aa2/fs/buffer.c  Thu Sep 20 20:45:58 2001
> > @@ -2506,7 +2506,7 @@
> >         spin_unlock(&free_list[isize].lock);
> > 
> >         page->buffers = bh;
> > -       page->flags &= ~(1 << PG_referenced);
> > +       page->flags |= 1 << PG_referenced;
> 
> I don't see how this can change anything - getblk() calls
> touch_buffer() shortly afterwards, which does the same
> thing?

I'm worried the page is freed before it has a chance to be found in the
freelist in smp. The refill_freelist logic is broken too and right fix
would be much more invasive than the above one liner, we should return
one bh with b_count just set to 1 to be sure it's not collected away
under us and we have to try again. But this one probably will do the
trick too for now. and maybe it really doesn't matter as you say.

And also the get_hash_table need to touch the buffer since reiserfs
makes heavy use if it.

just a few ideas.

--- 2.4.10pre12aa2/fs/buffer.c.~1~	Thu Sep 20 20:14:19 2001
+++ 2.4.10pre12aa2/fs/buffer.c	Thu Sep 20 21:06:16 2001
@@ -598,8 +598,10 @@
 		    bh->b_size    == size	&&
 		    bh->b_dev     == dev)
 			break;
-	if (bh)
+	if (bh) {
 		get_bh(bh);
+		touch_buffer(bh);
+	}
 
 	return bh;
 }
@@ -1181,10 +1183,10 @@
 
 		/* Insert the buffer into the regular lists */
 		__insert_into_queues(bh);
+		touch_buffer(bh);
 	out:
 		write_unlock(&hash_table_lock);
 		spin_unlock(&lru_list_lock);
-		touch_buffer(bh);
 		return bh;
 	}
 

Andrea

Re: [PATCH] Significant performace improvements on reiserfs systems

[Robert Love]

On Thu, 2001-09-20 at 13:39, Andrew Morton wrote:
> > Andrew, are these still maintained or should I pull out the reiserfs bits?
> 
> This is the reiserfs part - it applies to 2.4.10-pre12 OK.
> 
> For the purposes of Robert's patch, conditional_schedule()
> should be defined as 
> 
> 	if (current->need_resched && current->lock_depth == 0) {
> 		unlock_kernel();
> 		lock_kernel();
> 	}
> 
> which is somewhat crufty, because the implementation of lock_kernel()
> is arch-specific.  But all architectures seem to implement it the same way.

Note that we only support preemption on i386 thus far, so this is not an
issue (yet).

One other note, in not all cases is it OK to just drop the one lock
(above it is).  Say we hold a spinlock, but another lock (most notably
the BKL) is also held.  Since the preemption counter is recursive, we
still won't allow preemption until all locks are dropped.  In this case,
we need to see what else needs to be dropped, or just call schedule()
explicitly.

> <patch snipped>

Looks nice, Andrew.

Anyone try this? (I don't use ReiserFS).

I am putting together a conditional scheduling patch to fix some of the
worst cases, for use in conjunction with the preemption patch, and this
might be useful.

-- 
Robert M. Love
rml at ufl.edu
rml at tech9.net

Re: [PATCH] Significant performace improvements on reiserfs systems

[Dieter Nützel]

Am Donnerstag, 20. September 2001 22:52 schrieb Robert Love:
> On Thu, 2001-09-20 at 13:39, Andrew Morton wrote:
> > > Andrew, are these still maintained or should I pull out the reiserfs
> > > bits?
> >
> > This is the reiserfs part - it applies to 2.4.10-pre12 OK.
> >
> > For the purposes of Robert's patch, conditional_schedule()
> > should be defined as
> >
> > 	if (current->need_resched && current->lock_depth == 0) {
> > 		unlock_kernel();
> > 		lock_kernel();
> > 	}
> >
> > which is somewhat crufty, because the implementation of lock_kernel()
> > is arch-specific.  But all architectures seem to implement it the same
> > way.

> > <patch snipped>
>
> Looks nice, Andrew.
>
> Anyone try this? (I don't use ReiserFS).

Yes, I will...:-)
Send it along.

>
> I am putting together a conditional scheduling patch to fix some of the
> worst cases, for use in conjunction with the preemption patch, and this
> might be useful.

The conditional_schedule() function hampered me from running it already.

-Dieter

Re: [PATCH] Significant performace improvements on reiserfs systems

[Robert Love]

On Thu, 2001-09-20 at 17:11, Dieter Nützel wrote:
> > I am putting together a conditional scheduling patch to fix some of the
> > worst cases, for use in conjunction with the preemption patch, and this
> > might be useful.
> 
> The conditional_schedule() function hampered me from running it already.

hrm, i didnt notice that conditional_schedule wasnt defined in that
patch.  you will need to do it, but do something more like

if (current->need_resched && current->lock_depth == 0) {
	unlock_kernel();
	lock_kernel();
}

like Andrew wrote.

If you don't jump on the idea of trying this :) I will send work out a
patch that does some other low-latency thigns and send it out.

-- 
Robert M. Love
rml at ufl.edu
rml at tech9.net

Re: [PATCH] Significant performace improvements on reiserfs systems

[Andrea Arcangeli]

On Thu, Sep 20, 2001 at 06:24:48PM -0400, Robert Love wrote:
> On Thu, 2001-09-20 at 17:11, Dieter Nützel wrote:
> > > I am putting together a conditional scheduling patch to fix some of the
> > > worst cases, for use in conjunction with the preemption patch, and this
> > > might be useful.
> > 
> > The conditional_schedule() function hampered me from running it already.
> 
> hrm, i didnt notice that conditional_schedule wasnt defined in that
> patch.  you will need to do it, but do something more like
> 
> if (current->need_resched && current->lock_depth == 0) {
> 	unlock_kernel();
> 	lock_kernel();
> }
> 
> like Andrew wrote.

nitpicking: the above is fine but it isn't complete, it may work for
most cases but for a generic function it would be better implemented
similarly to release_kernel_lock_save/restore so you take care of
lock_depth > 0 too:

	ftp://ftp.us.kernel.org/pub/linux/kernel/people/andrea/kernels/v2.2/2.2.20pre10aa1/72_copy-user-unlock-1

Andrea

Re: [PATCH] Significant performace improvements on reiserfs systems

[Robert Love]

On Thu, 2001-09-20 at 18:37, Andrea Arcangeli wrote:
> On Thu, Sep 20, 2001 at 06:24:48PM -0400, Robert Love wrote:
> >
> > if (current->need_resched && current->lock_depth == 0) {
> > 	unlock_kernel();
> > 	lock_kernel();
> > }

> nitpicking: the above is fine but it isn't complete, it may work for
> most cases but for a generic function it would be better implemented
> similarly to release_kernel_lock_save/restore so you take care of
> lock_depth > 0 too:

Let me explain a little about the patch, and then I am interested in if
your opinion changes.

When unlock_kernel() is called, the preemption code will be enabled and
check if the preemption count is non-zero -- its handled just like a
recursive lock.  If there are other locks held, preemption won't
happen.  Thus, we return to the caller code patch and lock_kernel() is
called and everyone is happy.

If unlock_kernel() is called, and the preemption code (which hangs off
the bottom of the locking code) sees that the lock depth is now 0, it
will call preempt_schedule (if needed) and allow a new process to run.
Then we return to the original code patch, call lock_kernel, and
continue.

Or am I missing something?

-- 
Robert M. Love
rml at ufl.edu
rml at tech9.net

Re: [PATCH] Significant performace improvements on reiserfs systems

[Andrea Arcangeli]

On Thu, Sep 20, 2001 at 06:56:04PM -0400, Robert Love wrote:
> On Thu, 2001-09-20 at 18:37, Andrea Arcangeli wrote:
> > On Thu, Sep 20, 2001 at 06:24:48PM -0400, Robert Love wrote:
> > >
> > > if (current->need_resched && current->lock_depth == 0) {
> > > 	unlock_kernel();
> > > 	lock_kernel();
> > > }
> 
> > nitpicking: the above is fine but it isn't complete, it may work for
> > most cases but for a generic function it would be better implemented
> > similarly to release_kernel_lock_save/restore so you take care of
> > lock_depth > 0 too:
> 
> Let me explain a little about the patch, and then I am interested in if
> your opinion changes.
> 
> When unlock_kernel() is called, the preemption code will be enabled and
> check if the preemption count is non-zero -- its handled just like a

All I'm saying is that you should check for >= 0, not == 0.

But anwyays it's pretty depressing to see such a costly check needed to
get latency right with the preemptive kernel approch, with
non-preemptive kernel we'd need to just check need_resched and a call
schedule in the unlikely case so it would be even lighter :) and no
fixed costs in UP spinlocks, per-cpu datastrctures etc... The point of
preemptive kernel would be just to prevent us to put such kind of
explicit (costly) checks in the code. My theory was that the cpu-costly
loops are mostly protected by some lock anyways and the fact you're
writing such horrid (but helpful) code is a kind of proof.

Andrea

Re: [PATCH] Significant performace improvements on reiserfs systems

[george anzinger]

Andrea Arcangeli wrote:
> 
> On Thu, Sep 20, 2001 at 06:56:04PM -0400, Robert Love wrote:
> > On Thu, 2001-09-20 at 18:37, Andrea Arcangeli wrote:
> > > On Thu, Sep 20, 2001 at 06:24:48PM -0400, Robert Love wrote:
> > > >
> > > > if (current->need_resched && current->lock_depth == 0) {
> > > >   unlock_kernel();
> > > >   lock_kernel();
> > > > }
> >
> > > nitpicking: the above is fine but it isn't complete, it may work for
> > > most cases but for a generic function it would be better implemented
> > > similarly to release_kernel_lock_save/restore so you take care of
> > > lock_depth > 0 too:
> >
> > Let me explain a little about the patch, and then I am interested in if
> > your opinion changes.
> >
> > When unlock_kernel() is called, the preemption code will be enabled and
> > check if the preemption count is non-zero -- its handled just like a
> 
> All I'm saying is that you should check for >= 0, not == 0.
> 
> But anwyays it's pretty depressing to see such a costly check needed to
> get latency right with the preemptive kernel approch, with
> non-preemptive kernel we'd need to just check need_resched and a call
> schedule in the unlikely case so it would be even lighter :) and no
> fixed costs in UP spinlocks, per-cpu datastrctures etc... The point of
> preemptive kernel would be just to prevent us to put such kind of
> explicit (costly) checks in the code. My theory was that the cpu-costly
> loops are mostly protected by some lock anyways and the fact you're
> writing such horrid (but helpful) code is a kind of proof.
> 
Actually, I rather think that the problem is lock granularity.  These
issues are present in the SMP systems as well.  A good solution would be
one that shortened the spinlock time.  No horrid preempt code, just
tight fast code.

And the ones to address these issues are the owners of the code.  Those
who want the lower latency are left, thur lack of knowledge and time,
with crude tools like the conditional_schedule().

George

Re: [PATCH] Significant performace improvements on reiserfs systems

[Andrew Morton]

george anzinger wrote:
> 
> ...
> Actually, I rather think that the problem is lock granularity.  These
> issues are present in the SMP systems as well.  A good solution would be
> one that shortened the spinlock time.  No horrid preempt code, just
> tight fast code.
> 

This may not be practical.

Take, for example, zap_page_range().   It simply has a lot
of work to do, and it does it inside a spinlock.  By doing
it in a tight loop, it's optimal.

There is no way to speed this function up by two or three orders
of magnitude.  (Well, there is: don't take the lock at all if
the mm isn't shared, but this is merely an example.  There are
other instances).

It seems that for a preemptive kernel to be successful, we need
to globally alter the kernel so that it never holds locks for
more than 500 microseconds.  Which is what the conditional_schedule()
(aka cooperative multitasking :)) patches do.

It seems that there are no magic bullets, and low latency will
forever have a global impact on kernel design, unless a way is
found to reschedule with locks held.  I recall that a large
part of the MontaVista patch involved turning spinlocks into
semaphores, yes?  That would seem to be the way to go.

Re: [PATCH] Significant performace improvements on reiserfs systems

[Robert Love]

On Thu, 2001-09-20 at 21:20, Andrew Morton wrote:
> This may not be practical.
> 
> Take, for example, zap_page_range().   It simply has a lot
> of work to do, and it does it inside a spinlock.  By doing
> it in a tight loop, it's optimal.
> 
> There is no way to speed this function up by two or three orders
> of magnitude.  (Well, there is: don't take the lock at all if
> the mm isn't shared, but this is merely an example.  There are
> other instances).

Agreed, but...

> It seems that for a preemptive kernel to be successful, we need
> to globally alter the kernel so that it never holds locks for
> more than 500 microseconds.  Which is what the conditional_schedule()
> (aka cooperative multitasking :)) patches do.
>
> It seems that there are no magic bullets, and low latency will
> forever have a global impact on kernel design, unless a way is
> found to reschedule with locks held.  I recall that a large
> part of the MontaVista patch involved turning spinlocks into
> semaphores, yes?  That would seem to be the way to go.

This would be the situation that solved the problem with little
complaint, huh?

-- 
Robert M. Love
rml at ufl.edu
rml at tech9.net

Re: [reiserfs-list] Re: [PATCH] Significant performace improvements on reiserfs systems

[Nikita Danilov]

Andrew Morton writes:
 > george anzinger wrote:
 > > 
 > > ...
 > > Actually, I rather think that the problem is lock granularity.  These
 > > issues are present in the SMP systems as well.  A good solution would be
 > > one that shortened the spinlock time.  No horrid preempt code, just
 > > tight fast code.
 > > 
 > 
 > This may not be practical.
 > 
 > Take, for example, zap_page_range().   It simply has a lot
 > of work to do, and it does it inside a spinlock.  By doing
 > it in a tight loop, it's optimal.
 > 
 > There is no way to speed this function up by two or three orders
 > of magnitude.  (Well, there is: don't take the lock at all if
 > the mm isn't shared, but this is merely an example.  There are
 > other instances).
 > 
 > It seems that for a preemptive kernel to be successful, we need
 > to globally alter the kernel so that it never holds locks for
 > more than 500 microseconds.  Which is what the conditional_schedule()
 > (aka cooperative multitasking :)) patches do.
 > 
 > It seems that there are no magic bullets, and low latency will
 > forever have a global impact on kernel design, unless a way is
 > found to reschedule with locks held.  I recall that a large

In Solaris, before spinning on a busy spin-lock, thread checks whether
spin-lock holder runs on the same processor. If so, thread goes to sleep
and holder wakes it up on spin-lock release. The same, I guess is going
for interrupts that are served as separate threads. This way, one can
re-schedule with spin-locks held.

 > part of the MontaVista patch involved turning spinlocks into
 > semaphores, yes?  That would seem to be the way to go.

Nikita.

Re: [reiserfs-list] Re: [PATCH] Significant performace improvements on reiserfs systems

[Alan Cox]

> In Solaris, before spinning on a busy spin-lock, thread checks whether
> spin-lock holder runs on the same processor. If so, thread goes to sleep
> and holder wakes it up on spin-lock release. The same, I guess is going


> for interrupts that are served as separate threads. This way, one can
> re-schedule with spin-locks held.

This is one of the things interrupt handling by threads gives you, but the
performance cost is not nice. When you consider that ksoftirqd when it
kicks in (currently far too often) takes up to 10% off gigabit ethernet
performance, you can appreciate why we don't want to go that path.

Our spinlock paths are supposed to be very small and predictable. Where 
there is sleeping involved we have semaphores.

As lockmeter shows we still have a few io_request_lock cases at least where
we lock for far too long

Alan

Re: [reiserfs-list] Re: [PATCH] Significant performace improvements on reiserfs systems

[Nikita Danilov]

Alan Cox writes:
 > > In Solaris, before spinning on a busy spin-lock, thread checks whether
 > > spin-lock holder runs on the same processor. If so, thread goes to sleep
 > > and holder wakes it up on spin-lock release. The same, I guess is going
 > 
 > 
 > > for interrupts that are served as separate threads. This way, one can
 > > re-schedule with spin-locks held.
 > 
 > This is one of the things interrupt handling by threads gives you, but the
 > performance cost is not nice. When you consider that ksoftirqd when it
 > kicks in (currently far too often) takes up to 10% off gigabit ethernet
 > performance, you can appreciate why we don't want to go that path.

I guess, reasoning behind Solaris design was that you have to disable
interrupts during critical sections more frequently than they would
actually block in them. So, you lose on interrupt thread creation and
when interrupts really block on a lock, but you gain because there is no
more need to disable interrupts when accessing data shared between
interrupt handler and the rest of the kernel. This can ultimately amount
to some net advantage especially when coupled with some sort of lazy
interrupt thread creation.

 > 
 > Our spinlock paths are supposed to be very small and predictable. Where 
 > there is sleeping involved we have semaphores.
 > 
 > As lockmeter shows we still have a few io_request_lock cases at least where
 > we lock for far too long

Reiserfs also likes to keep BKL while doing binary searches within nodes
of a tree.

 > 
 > Alan

Nikita.

 > -
 > To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
 > the body of a message to majordomo@vger.kernel.org
 > More majordomo info at  http://vger.kernel.org/majordomo-info.html
 > Please read the FAQ at  http://www.tux.org/lkml/

Re: [reiserfs-list] Re: [PATCH] Significant performace improvements on reiserfs systems

[Rusty Russell]

On Fri, 21 Sep 2001 13:18:31 +0100 (BST)
Alan Cox <alan@lxorguk.ukuu.org.uk> wrote:

> > In Solaris, before spinning on a busy spin-lock, thread checks whether
> > spin-lock holder runs on the same processor. If so, thread goes to sleep
> > and holder wakes it up on spin-lock release. The same, I guess is going
> 
> 
> > for interrupts that are served as separate threads. This way, one can
> > re-schedule with spin-locks held.
> 
> This is one of the things interrupt handling by threads gives you, but the
> performance cost is not nice. When you consider that ksoftirqd when it
> kicks in (currently far too often) takes up to 10% off gigabit ethernet
> performance, you can appreciate why we don't want to go that path.

I've been thinking about this: I know some people have been fiddling with making
do_softirq spin X times before kicking ksoftirqd, but how about the following?

Cheers,
Rusty.

--- linux-pmac/kernel/softirq.c	Sun Sep  9 15:11:37 2001
+++ working-pmac-ksoftirq/kernel/softirq.c	Mon Sep 24 09:44:07 2001
@@ -63,11 +63,12 @@
 	int cpu = smp_processor_id();
 	__u32 pending;
 	long flags;
-	__u32 mask;
+	long start;
 
 	if (in_interrupt())
 		return;
 
+	start = jiffies;
 	local_irq_save(flags);
 
 	pending = softirq_pending(cpu);
@@ -75,32 +76,32 @@
 	if (pending) {
 		struct softirq_action *h;
 
-		mask = ~pending;
 		local_bh_disable();
-restart:
-		/* Reset the pending bitmask before enabling irqs */
-		softirq_pending(cpu) = 0;
+		do {
+			/* Reset the pending bitmask before enabling irqs */
+			softirq_pending(cpu) = 0;
 
-		local_irq_enable();
+			local_irq_enable();
 
-		h = softirq_vec;
+			h = softirq_vec;
 
-		do {
-			if (pending & 1)
-				h->action(h);
-			h++;
-			pending >>= 1;
-		} while (pending);
-
-		local_irq_disable();
-
-		pending = softirq_pending(cpu);
-		if (pending & mask) {
-			mask &= ~pending;
-			goto restart;
-		}
+			do {
+				if (pending & 1)
+					h->action(h);
+				h++;
+				pending >>= 1;
+			} while (pending);
+
+			local_irq_disable();
+
+			pending = softirq_pending(cpu);
+
+			/* Don't spin here forever... */
+		} while (pending && start == jiffies);
 		__local_bh_enable();
 
+		/* If a timer tick went off, assume we're overloaded,
+                   and kick in ksoftirqd */
 		if (pending)
 			wakeup_softirqd(cpu);
 	}

Re: [PATCH] Significant performace improvements on reiserfs systems

[Robert Love]

On Thu, 2001-09-20 at 19:15, Andrea Arcangeli wrote:
> All I'm saying is that you should check for >= 0, not == 0.

And I am saying we already keep track of that, we have a preemption
counter.

> But anwyays it's pretty depressing to see such a costly check needed to
> get latency right with the preemptive kernel approch, with
> non-preemptive kernel we'd need to just check need_resched and a call
> schedule in the unlikely case so it would be even lighter :) and no
> fixed costs in UP spinlocks, per-cpu datastrctures etc... The point of
> preemptive kernel would be just to prevent us to put such kind of
> explicit (costly) checks in the code. My theory was that the cpu-costly
> loops are mostly protected by some lock anyways and the fact you're
> writing such horrid (but helpful) code is a kind of proof.

Well, with the preemptive kernel we already account for 90% of the high
latency areas.

Doing the "horrid" solution may solve some other issues, but agreeably
you are right its not the prettiest solution.

I don't agree, however, that its that much more costly, and maybe I am
missing something.  Assuming we are SMP (and thus have locks), where is
there a lot more overhead?  We check current->need_resched (which we
dont _have_ to), call unlock_kernel() and then call lock_kernel(), with
preemption happening automatically in between.  The preemption code
merely checks a counter and calls preempt_schedule() if needed.

Now, yes, this is not ideal.  Ideally we don't need any of this muck. 
Ideally preemption provides everything we need.  So, towards the future,
we can work towards that.  For very short locks, we could just disable
interrupts (a lot less overhead).  For long-held locks, we can replace
them with a more efficient lock -- spin-then-sleep or a
priority-inheriting mutex lock, for example.

I don't want to confuse the above, which is perhaps an ideal system for
inclusion in 2.5, with trying to lower latency further for those who
care via conditional scheduling and the such.

We already have average latency of <1ms with peaks 10-50ms.

-- 
Robert M. Love
rml at ufl.edu
rml at tech9.net