[PATCH] radix-tree pagecache for 2.4.19-pre5-ac3

[PATCH] radix-tree pagecache for 2.4.19-pre5-ac3

[Art Haas]

[-- Attachment #1: Type: text/plain, Size: 787 bytes --]

Hi.

Once again the patch has been re-diffed for the latest -ac
kernel. It's running on my machine now. Enjoy!

I'm interested in hearing back from anyone using this
patch - I'd like to be sure that it applies cleanly (I
believe it does), and that the kernel built with the
patch runs well. The -ac kernels with rmap and the O(1)
scheduler are working well for me, and I'm hoping that
this patch adds to those kernels. At some point I'm hoping
the patch is included in to the -ac patchset, and the
eventual inclusion into the standard kernel release.

My thanks to everyone working on the kernel.

Art Haas

-- 
They that can give up essential liberty to obtain a little temporary
safety deserve neither liberty nor safety.
 -- Benjamin Franklin, Historical Review of Pennsylvania, 1759

[-- Attachment #2: radix-tree-2419p5ac3.patch.bz2 --]
[-- Type: application/octet-stream, Size: 12586 bytes --]

Re: [PATCH] radix-tree pagecache for 2.4.19-pre5-ac3

[Paul P Komkoff Jr]

Replying to Art Haas:
> Hi.
> 
> Once again the patch has been re-diffed for the latest -ac
> kernel. It's running on my machine now. Enjoy!

I'm sure you will glad to hear that your patch trashing the box it runs on
completely.

I'm now developing -stingr4* patchset against -pre5-ac3 and I am very angry.
I wasted about 6 hours today hinting this very obscure bug and didn't caught
it well :(

the kernel with radix tree pagecache patch under LTP fs tests load fails
generating the following oopses (below).

I'm sure Mr.Viro will glad to see it too because I am stuck and after 1st
pass cannot see the place in where I_FREEING can be removed from
inode->i_state tracing from iput to clear_inode thru reiserfs_delete_inode.

But maybe I'm just blind. Anyway, oopses included, ltp fs just finished its
second run on kernel without radix tree pagecache, and is happy.

anyone interested in viewing "exactly my kernel"
bk://linux-stingr.bkbits.net/unstable - you can clone existing marcelo tree
with clone -rv2.4.19-pre5 then bk pull changes from mine

ksymoops 2.4.5 on i686 2.4.19-pre5-ac3-s42.  Options used
     -V (default)
     -k /proc/ksyms (default)
     -l /proc/modules (default)
     -o /lib/modules/2.4.19-pre5-ac3-s42/ (default)
     -m /boot/System.map (specified)

Warning (compare_maps): ksyms_base symbol vmalloc_to_page_R__ver_vmalloc_to_page not found in System.map.  Ignoring ksyms_base entry
cpu: 0, clocks: 664766, slice: 221588
cpu: 1, clocks: 664766, slice: 221588
 /dev/scsi/host0/bus0/target2/lun0:<7>LDM:  DEBUG (ldm.c, 963): validate_partition_table: No MS-DOS partition found.
 /dev/scsi/host0/bus0/target4/lun0:<7>LDM:  DEBUG (ldm.c, 963): validate_partition_table: No MS-DOS partition found.
  Receiver lock-up bug exists -- enabling work-around.
kernel BUG at inode.c:515!
invalid operand: 0000
CPU:    0
EIP:    0010:[<c015241a>]    Not tainted
Using defaults from ksymoops -t elf32-i386 -a i386
EFLAGS: 00010286
eax: c57c08a0   ebx: ffffffff   ecx: c57c08c0   edx: c57c08c0
esi: c57c08a0   edi: c13a7000   ebp: c57c08a0   esp: c8227ed8
ds: 0018   es: 0018   ss: 0018
Process growfiles (pid: 8896, stackpage=c8227000)
Stack: c8227efc c13a7000 00000024 c57c090c c57c090c c8227efc c016f362 c57c08a0 
       c8226000 c023a3a4 00000007 00000024 00002ed9 c13a7000 00000000 c57c08a0 
       c13a7000 c57c08a0 c016f2b0 c02708a0 cbaa0ec0 c0152ed3 c57c08a0 cbaa0ec0 
Call Trace: [<c016f362>] [<c016f2b0>] [<c0152ed3>] [<c01510a6>] [<c01496da>] 
   [<c014834a>] [<c0149799>] [<c0115ef0>] [<c0108afb>] 
Code: 0f 0b 03 02 15 20 24 c0 8b 86 1c 01 00 00 a9 10 00 00 00 75 


>>EIP; c015241a <clear_inode+1a/100>   <=====

>>eax; c57c08a0 <_end+5494114/c585874>
>>ebx; ffffffff <END_OF_CODE+335dd3e0/????>
>>ecx; c57c08c0 <_end+5494134/c585874>
>>edx; c57c08c0 <_end+5494134/c585874>
>>esi; c57c08a0 <_end+5494114/c585874>
>>edi; c13a7000 <_end+107a874/c585874>
>>ebp; c57c08a0 <_end+5494114/c585874>
>>esp; c8227ed8 <_end+7efb74c/c585874>

Trace; c016f362 <reiserfs_delete_inode+b2/f0>
Trace; c016f2b0 <reiserfs_delete_inode+0/f0>
Trace; c0152ed3 <iput+143/240>
Trace; c01510a6 <d_delete+66/b0>
Trace; c01496da <vfs_unlink+1ba/1f0>
Trace; c014834a <lookup_hash+4a/d0>
Trace; c0149799 <sys_unlink+89/f0>
Trace; c0115ef0 <do_page_fault+0/45b>
Trace; c0108afb <system_call+33/38>

Code;  c015241a <clear_inode+1a/100>
00000000 <_EIP>:
Code;  c015241a <clear_inode+1a/100>   <=====
   0:   0f 0b                     ud2a      <=====
Code;  c015241c <clear_inode+1c/100>
   2:   03 02                     add    (%edx),%eax
Code;  c015241e <clear_inode+1e/100>
   4:   15 20 24 c0 8b            adc    $0x8bc02420,%eax
Code;  c0152423 <clear_inode+23/100>
   9:   86 1c 01                  xchg   %bl,(%ecx,%eax,1)
Code;  c0152426 <clear_inode+26/100>
   c:   00 00                     add    %al,(%eax)
Code;  c0152428 <clear_inode+28/100>
   e:   a9 10 00 00 00            test   $0x10,%eax
Code;  c015242d <clear_inode+2d/100>
  13:   75 00                     jne    15 <_EIP+0x15> c015242f <clear_inode+2f/100>

kernel BUG at inode.c:515!
invalid operand: 0000
CPU:    1
EIP:    0010:[<c015241a>]    Not tainted
EFLAGS: 00010286
eax: c157e2c0   ebx: ffffffff   ecx: c157e2e0   edx: c157e2e0
esi: c157e2c0   edi: c13a7000   ebp: c157e2c0   esp: c405be88
ds: 0018   es: 0018   ss: 0018
Process gzip (pid: 8901, stackpage=c405b000)
Stack: c405beac c13a7000 00000024 c157e32c c157e32c c405beac c016f362 c157e2c0 
       c405a000 c023a3a4 00000013 00000024 00002f12 c13a7000 00000000 c157e2c0 
       c13a7000 c157e2c0 c016f2b0 c02708a0 cbc29240 c0152ed3 c157e2c0 cbc29240 
Call Trace: [<c016f362>] [<c016f2b0>] [<c0152ed3>] [<c01505a7>] [<c01504dc>] 
   [<c013e0ee>] [<c013cbf1>] [<c011d5ad>] [<c011ddbe>] [<c01146ff>] [<c0108afb>] 
Code: 0f 0b 03 02 15 20 24 c0 8b 86 1c 01 00 00 a9 10 00 00 00 75 


>>EIP; c015241a <clear_inode+1a/100>   <=====

>>eax; c157e2c0 <_end+1251b34/c585874>
>>ebx; ffffffff <END_OF_CODE+335dd3e0/????>
>>ecx; c157e2e0 <_end+1251b54/c585874>
>>edx; c157e2e0 <_end+1251b54/c585874>
>>esi; c157e2c0 <_end+1251b34/c585874>
>>edi; c13a7000 <_end+107a874/c585874>
>>ebp; c157e2c0 <_end+1251b34/c585874>
>>esp; c405be88 <_end+3d2f6fc/c585874>

Trace; c016f362 <reiserfs_delete_inode+b2/f0>
Trace; c016f2b0 <reiserfs_delete_inode+0/f0>
Trace; c0152ed3 <iput+143/240>
Trace; c01505a7 <dput+e7/150>
Trace; c01504dc <dput+1c/150>
Trace; c013e0ee <fput+ce/f0>
Trace; c013cbf1 <filp_close+91/a0>
Trace; c011d5ad <put_files_struct+4d/d0>
Trace; c011ddbe <do_exit+11e/250>
Trace; c01146ff <smp_apic_timer_interrupt+ef/120>
Trace; c0108afb <system_call+33/38>

Code;  c015241a <clear_inode+1a/100>
00000000 <_EIP>:
Code;  c015241a <clear_inode+1a/100>   <=====
   0:   0f 0b                     ud2a      <=====
Code;  c015241c <clear_inode+1c/100>
   2:   03 02                     add    (%edx),%eax
Code;  c015241e <clear_inode+1e/100>
   4:   15 20 24 c0 8b            adc    $0x8bc02420,%eax
Code;  c0152423 <clear_inode+23/100>
   9:   86 1c 01                  xchg   %bl,(%ecx,%eax,1)
Code;  c0152426 <clear_inode+26/100>
   c:   00 00                     add    %al,(%eax)
Code;  c0152428 <clear_inode+28/100>
   e:   a9 10 00 00 00            test   $0x10,%eax
Code;  c015242d <clear_inode+2d/100>
  13:   75 00                     jne    15 <_EIP+0x15> c015242f <clear_inode+2f/100>


1 warning issued.  Results may not be reliable.

-- 
Paul P 'Stingray' Komkoff 'Greatest' Jr // (icq)23200764 // (irc)Spacebar
  PPKJ1-RIPE // (smtp)i@stingr.net // (http)stingr.net // (pgp)0xA4B4ECA4

Re: [PATCH] radix-tree pagecache for 2.4.19-pre5-ac3

[William Lee Irwin III]

On Sun, Apr 07, 2002 at 11:44:39AM -0500, Art Haas wrote:
> Once again the patch has been re-diffed for the latest -ac
> kernel. It's running on my machine now. Enjoy!
> I'm interested in hearing back from anyone using this
> patch - I'd like to be sure that it applies cleanly (I
> believe it does), and that the kernel built with the
> patch runs well. The -ac kernels with rmap and the O(1)
> scheduler are working well for me, and I'm hoping that
> this patch adds to those kernels. At some point I'm hoping
> the patch is included in to the -ac patchset, and the
> eventual inclusion into the standard kernel release.
> My thanks to everyone working on the kernel.

Thank you! This has saved me some effort.

Burning question:
What are the hunks changing arch/i386/kernel/setup.c there for?
Also, there appears to be a livelock in add_to_swap(), (yes, this
has killed my boxen dead) something to help with this follows.
(It at least turned up a different problem I'm still working on.)


Cheers,
Bill


diff -urN linux-virgin/mm/swap_state.c linux/mm/swap_state.c
--- linux-virgin/mm/swap_state.c	Tue Apr  9 18:50:48 2002
+++ linux/mm/swap_state.c	Tue Apr  9 21:28:15 2002
@@ -104,6 +104,7 @@
  */
 int add_to_swap(struct page * page)
 {
+	int error;
 	swp_entry_t entry;
 
 	if (!PageLocked(page))
@@ -118,11 +119,15 @@
 		 * (adding to the page cache will clear the dirty
 		 * and uptodate bits, so we need to do it again)
 		 */
-		if (add_to_swap_cache(page, entry) == 0) {
+		error = add_to_swap_cache(page, entry);
+		if (!error) {
 			SetPageUptodate(page);
 			set_page_dirty(page);
 			swap_free(entry);
 			return 1;
+		} else if (error = -ENOMEM) {
+			swap_free(entry);
+			return 0;
 		}
 		/* Raced with "speculative" read_swap_cache_async */
 		swap_free(entry);

Re: [PATCH] radix-tree pagecache for 2.4.19-pre5-ac3

[William Lee Irwin III]

On Sun, Apr 07, 2002 at 11:44:39AM -0500, Art Haas wrote:
> Once again the patch has been re-diffed for the latest -ac
> kernel. It's running on my machine now. Enjoy!
> I'm interested in hearing back from anyone using this
> patch - I'd like to be sure that it applies cleanly (I
> believe it does), and that the kernel built with the
> patch runs well. The -ac kernels with rmap and the O(1)
> scheduler are working well for me, and I'm hoping that
> this patch adds to those kernels. At some point I'm hoping
> the patch is included in to the -ac patchset, and the
> eventual inclusion into the standard kernel release.
> My thanks to everyone working on the kernel.

Thank you! This has saved me some effort.

Burning question:
What are the hunks changing arch/i386/kernel/setup.c there for?
Also, there appears to be a livelock in add_to_swap(), (yes, this
has killed my boxen dead) something to help with this follows.
(It at least turned up a different problem I'm still working on.)


Cheers,
Bill


diff -urN linux-virgin/mm/swap_state.c linux/mm/swap_state.c
--- linux-virgin/mm/swap_state.c	Tue Apr  9 18:50:48 2002
+++ linux/mm/swap_state.c	Tue Apr  9 21:28:15 2002
@@ -104,6 +104,7 @@
  */
 int add_to_swap(struct page * page)
 {
+	int error;
 	swp_entry_t entry;
 
 	if (!PageLocked(page))
@@ -118,11 +119,15 @@
 		 * (adding to the page cache will clear the dirty
 		 * and uptodate bits, so we need to do it again)
 		 */
-		if (add_to_swap_cache(page, entry) == 0) {
+		error = add_to_swap_cache(page, entry);
+		if (!error) {
 			SetPageUptodate(page);
 			set_page_dirty(page);
 			swap_free(entry);
 			return 1;
+		} else if (error = -ENOMEM) {
+			swap_free(entry);
+			return 0;
 		}
 		/* Raced with "speculative" read_swap_cache_async */
 		swap_free(entry);
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: [PATCH] radix-tree pagecache for 2.4.19-pre5-ac3

[Art Haas]

On Wed, Apr 10, 2002 at 01:59:47PM -0700, William Lee Irwin III wrote:
> On Sun, Apr 07, 2002 at 11:44:39AM -0500, Art Haas wrote:
> [ ... snip ... ]
> 
> Thank you! This has saved me some effort.
> 
> Burning question:
> What are the hunks changing arch/i386/kernel/setup.c there for?

The initial patch I downloaded had those changes in there. Looking
at them now there doesn't seem to be any reason to include them. Perhaps
they were inadvertently added originally, and I've been continuing
that tradition ...

> Also, there appears to be a livelock in add_to_swap(), (yes, this
> has killed my boxen dead) something to help with this follows.
> (It at least turned up a different problem I'm still working on.)

Sorry to hear that. I haven't had any trouble on my machine, but
it's an old machine (200MHz Pentium), and I run desktop stuff, so
the load the patch is exposed to on this machine must not be enough
to trip things up. 

Thanks for the feedback and your additional patch! I have
one question about it though ...

> diff -urN linux-virgin/mm/swap_state.c linux/mm/swap_state.c
> --- linux-virgin/mm/swap_state.c	Tue Apr  9 18:50:48 2002
> +++ linux/mm/swap_state.c	Tue Apr  9 21:28:15 2002
> @@ -104,6 +104,7 @@
>   */
>  int add_to_swap(struct page * page)
>  {
> +	int error;
>  	swp_entry_t entry;
>  
>  	if (!PageLocked(page))
> @@ -118,11 +119,15 @@
>  		 * (adding to the page cache will clear the dirty
>  		 * and uptodate bits, so we need to do it again)
>  		 */
> -		if (add_to_swap_cache(page, entry) == 0) {
> +		error = add_to_swap_cache(page, entry);
> +		if (!error) {
>  			SetPageUptodate(page);
>  			set_page_dirty(page);
>  			swap_free(entry);
>  			return 1;
> +		} else if (error = -ENOMEM) {
> +			swap_free(entry);
> +			return 0;
>  		}
>  		/* Raced with "speculative" read_swap_cache_async */
>  		swap_free(entry);
> 

Should the new "else" clause be ...

		} else if (error == -ENOMEM) {

I think you've dropped an "=". Maybe this is the cause of the
other trouble you were seeing?

I hadn't posted it yet, but I've made a newer version of the
patch that incorporates the latest changes from Christoph Hellwig
and Andrew Morton - the changes of spin_lock() and spin_unlock()
to (read|write)_lock() and (read|write)_unlock, plus a few cosmetic
changes. I'm running a kernel with those changes right now (and things
work for me, but we've seen how that goes ...) . I'll rebuild my kernel
with your fix to the swap_state.c file and see how that kernel
performs. I can cook up a script to repeatedly build something and
let things run for a while. If it works I'll post my modified patch tomorrow.

Thanks again for the feedback!
-- 
They that can give up essential liberty to obtain a little temporary
safety deserve neither liberty nor safety.
 -- Benjamin Franklin, Historical Review of Pennsylvania, 1759
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: [PATCH] radix-tree pagecache for 2.4.19-pre5-ac3

[William Lee Irwin III]

On Wed, Apr 10, 2002 at 05:08:42PM -0500, Art Haas wrote:
> I think you've dropped an "=". Maybe this is the cause of the
> other trouble you were seeing?
> I hadn't posted it yet, but I've made a newer version of the
> patch that incorporates the latest changes from Christoph Hellwig
> and Andrew Morton - the changes of spin_lock() and spin_unlock()
> to (read|write)_lock() and (read|write)_unlock, plus a few cosmetic
> changes. I'm running a kernel with those changes right now (and things
> work for me, but we've seen how that goes ...) . I'll rebuild my kernel
> with your fix to the swap_state.c file and see how that kernel
> performs. I can cook up a script to repeatedly build something and
> let things run for a while. If it works I'll post my modified patch tomorrow.
> Thanks again for the feedback!

I did, you will need the == sorry.

I've been running Cerberus with this on a logical 8-way machine
(physical 4-way), it seems to hit about 2-5 minutes into the tests.
I'll back out my own changes and see what I turn up.


Cheers,
Bill
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: [PATCH] radix-tree pagecache for 2.4.19-pre5-ac3

[William Lee Irwin III]

On Wed, Apr 10, 2002 at 05:08:42PM -0500, Art Haas wrote:
> I think you've dropped an "=". Maybe this is the cause of the
> other trouble you were seeing?

I don't believe so. Just a vanilla 2.4.19-pre5-ac3 + your posted patch
+ corrected livelock fix (without it it livelocks instead) oopses at
fs/inode.c:515 within approximately 2 minutes:

    510 void clear_inode(struct inode *inode)
    511 {
    512         invalidate_inode_buffers(inode);
    513
    514         if (inode->i_data.nrpages)
    515                 BUG();
    516         if (!(inode->i_state & I_FREEING))
    517                 BUG();
    518         if (inode->i_state & I_CLEAR)
    519                 BUG();


Cheers,
Bill
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: [PATCH] radix-tree pagecache for 2.4.19-pre5-ac3

[William Lee Irwin III]

On Wed, Apr 10, 2002 at 05:08:42PM -0500, Art Haas wrote:
> Sorry to hear that. I haven't had any trouble on my machine, but
> it's an old machine (200MHz Pentium), and I run desktop stuff, so
> the load the patch is exposed to on this machine must not be enough
> to trip things up. 
> I think you've dropped an "=". Maybe this is the cause of the
> other trouble you were seeing?

No, it appears to be because all pagecache locking was removed from vmscan.c
Acquisitions and releases of pagecache_lock must be converted to the
analogous acquisitions and releases of the mapping->page_lock, with proper
movement of the points it's acquired and released for the per-mapping lock.
Testing with Cerberus on SMP machines helps find these issues.

The following hunks might need a bit more critical examination.


Cheers,
Bill


--- linux-2.4.19-pre5-ac3/mm/vmscan.c.ajh	2002-04-06 15:33:00.000000000 -0600
+++ linux-2.4.19-pre5-ac3/mm/vmscan.c	2002-04-06 15:33:45.000000000 -0600
@@ -84,11 +84,10 @@
 	int maxscan;
 
 	/*
-	 * We need to hold the pagecache_lock around all tests to make sure
-	 * reclaim_page() cannot race with find_get_page() and friends.
+	 * The pagecache_lock was removed with the addition of
+	 * the radix-tree patch.
 	 */
 	spin_lock(&pagemap_lru_lock);
-	spin_lock(&pagecache_lock);
 	maxscan = zone->inactive_clean_pages;
 	while (maxscan-- && !list_empty(&zone->inactive_clean_list)) {
 		page_lru = zone->inactive_clean_list.prev;
@@ -136,13 +135,11 @@
 		zone->inactive_clean_pages--;
 		UnlockPage(page);
 	}
-	spin_unlock(&pagecache_lock);
 	spin_unlock(&pagemap_lru_lock);
 	return NULL;
 
 found_page:
 	del_page_from_inactive_clean_list(page);
-	spin_unlock(&pagecache_lock);
 	spin_unlock(&pagemap_lru_lock);
 	if (entry.val)
 		swap_free(entry);
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: [PATCH] radix-tree pagecache for 2.4.19-pre5-ac3

[Art Haas]

On Thu, Apr 11, 2002 at 11:39:59AM -0700, William Lee Irwin III wrote:
> On Wed, Apr 10, 2002 at 05:08:42PM -0500, Art Haas wrote:
> > Sorry to hear that. I haven't had any trouble on my machine, but
> > it's an old machine (200MHz Pentium), and I run desktop stuff, so
> > the load the patch is exposed to on this machine must not be enough
> > to trip things up. 
> > I think you've dropped an "=". Maybe this is the cause of the
> > other trouble you were seeing?
> 
> No, it appears to be because all pagecache locking was removed from vmscan.c
> Acquisitions and releases of pagecache_lock must be converted to the
> analogous acquisitions and releases of the mapping->page_lock, with proper
> movement of the points it's acquired and released for the per-mapping lock.
> Testing with Cerberus on SMP machines helps find these issues.
> 
> The following hunks might need a bit more critical examination.
> 
> [ ... snip part of patch ... ]

I'll take any and all blame for the changes in vmscan.c that cause
problems.  I'm running on a machine with a single processor, and don't
have access to an SMP machine to test things on, so problems
arising on such machines would likely slip past me. :-(

I did go download Cerberus today, and started looking at what it
does, how to run it, etc.

I'll go dig into vmscan.c again. Thank you for your continued
efforts on reviewing and fixing the radix-tree patch.

-- 
They that can give up essential liberty to obtain a little temporary
safety deserve neither liberty nor safety.
 -- Benjamin Franklin, Historical Review of Pennsylvania, 1759
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/