2.4.9aa2 and please test mmap-rb-4

Diff between 2.4.9aa1 and 2.4.9aa2:

Only in 2.4.9aa2: 00_megaraid-paranoid-1

Possibly it's a bug in the anti-bounce buffer patch but make sure the megaraid gets not confused by the fact I'm really allowing it to get the 512k large requests with the sd-max_sectors patch (in mainline the line I #ifdeffed out are meaningless so it never got tested).

Only in 2.4.9aa1: 00_o_direct-13 Only in 2.4.9aa2: 00_o_direct-14

Janet Morgan promptly noticed I needed to s/>=/</ (it was an editing error while preparing the -13 patch).

Only in 2.4.9aa1: 00_poll-nfds-1 Only in 2.4.9aa2: 00_poll-nfds-2

Fixed off by one check.

Only in 2.4.9aa1: 40_blkdev-pagecache-13 Only in 2.4.9aa2: 40_blkdev-pagecache-14

Rediffed against o_direct-14.

Only in 2.4.9aa1: 70_mmap-rb-3 Only in 2.4.9aa2: 70_mmap-rb-4

Fixed severe bug that caused mm corruption and crashes. (splitted a __vma_link_file off __vma_link_rb, build_mmap_rb must not mess with anything but the rb itself) Improved other bits to cover all the merging cases and some minor optimization.

Since I couldn't find other issues in my workloads I'd now ask everybody who complained about the lack of vma merging in 2.4 to test this patch on their systems and to report the performance difference while running their vma intensive applications. Thanks!

You don't need to use the -aa tree to test this patch, I ported it on top of 2.4.9 vanilla too, you can find it here:

ftp://ftp.kernel.org/pub/linux/kernel/people/andrea/patches/v2.4/2.4.9/mmap-rb-4

Andrea

I benchmarked it a little bit here.

Test run on a PII SMP 450mhz on top of 2.4.9aa2.

---------------------------------------------------------------------------
With_out_ the mmap-rb-4 patch applied:

GROWSDOWNMERGE:

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsdownmerge

real    0m0.230s
user    0m0.020s
sys     0m0.210s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsdownmerge

real    0m0.230s
user    0m0.030s
sys     0m0.200s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsdownmerge

real    0m0.230s
user    0m0.030s
sys     0m0.200s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsdownmerge

real    0m0.231s
user    0m0.010s
sys     0m0.220s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsdownmerge

real    0m0.231s
user    0m0.030s
sys     0m0.200s

andrea@laser:/misc/andrea-athlon/vma-merging >

GROWSDOWNNOMERGE:

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsdownnomerge

real    0m0.231s
user    0m0.040s
sys     0m0.190s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsdownnomerge

real    0m0.228s
user    0m0.030s
sys     0m0.190s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsdownnomerge

real    0m0.230s
user    0m0.050s
sys     0m0.180s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsdownnomerge

real    0m0.230s
user    0m0.010s
sys     0m0.220s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsdownnomerge

real    0m0.230s
user    0m0.010s
sys     0m0.220s

andrea@laser:/misc/andrea-athlon/vma-merging >

GROWSUPMERGE:

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupmerge

real    0m0.096s
user    0m0.010s
sys     0m0.090s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupmerge

real    0m0.096s
user    0m0.010s
sys     0m0.080s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupmerge

real    0m0.096s
user    0m0.040s
sys     0m0.050s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupmerge

real    0m0.096s
user    0m0.020s
sys     0m0.070s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupmerge

real    0m0.096s
user    0m0.030s
sys     0m0.070s

andrea@laser:/misc/andrea-athlon/vma-merging >

GROWSUPNOMERGE:

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupnomerge

real    0m0.229s
user    0m0.040s
sys     0m0.190s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupnomerge

real    0m0.229s
user    0m0.030s
sys     0m0.200s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupnomerge

real    0m0.229s
user    0m0.020s
sys     0m0.210s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupnomerge

real    0m0.229s
user    0m0.030s
sys     0m0.200s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupnomerge

real    0m0.229s
user    0m0.040s
sys     0m0.190s

andrea@laser:/misc/andrea-athlon/vma-merging >

GROWSUPDOWN:

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupdown

real    0m0.241s
user    0m0.010s
sys     0m0.220s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupdown

real    0m0.240s
user    0m0.030s
sys     0m0.210s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupdown

real    0m0.240s
user    0m0.040s
sys     0m0.200s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupdown

real    0m0.240s
user    0m0.050s
sys     0m0.190s

andrea@laser:/misc/andrea-athlon/vma-merging >

---------------------------------------------------------------------------

With the mmap-rb-4 patch applied:

GROWSDOWNMERGE:

andrea@laser:/misc/andrea-athlon/vma-merging > time growsdownmerge

real    0m0.096s
user    0m0.030s
sys     0m0.070s

andrea@laser:/misc/andrea-athlon/vma-merging > time growsdownmerge

real    0m0.096s
user    0m0.030s
sys     0m0.070s

andrea@laser:/misc/andrea-athlon/vma-merging > time growsdownmerge

real    0m0.096s
user    0m0.020s
sys     0m0.080s

andrea@laser:/misc/andrea-athlon/vma-merging > time growsdownmerge

real    0m0.096s
user    0m0.050s
sys     0m0.050s

andrea@laser:/misc/andrea-athlon/vma-merging > time growsdownmerge

real    0m0.096s
user    0m0.030s
sys     0m0.070s

andrea@laser:/misc/andrea-athlon/vma-merging >

GROWSDOWNNOMERGE:

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsdownnomerge

real    0m0.220s
user    0m0.030s
sys     0m0.190s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsdownnomerge

real    0m0.220s
user    0m0.020s
sys     0m0.200s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsdownnomerge

real    0m0.220s
user    0m0.020s
sys     0m0.200s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsdownnomerge

real    0m0.221s
user    0m0.040s
sys     0m0.190s

andrea@laser:/misc/andrea-athlon/vma-merging >

GROWSUPMERGE:

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupmerge

real    0m0.096s
user    0m0.020s
sys     0m0.080s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupmerge

real    0m0.096s
user    0m0.020s
sys     0m0.080s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupmerge

real    0m0.096s
user    0m0.020s
sys     0m0.080s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupmerge

real    0m0.096s
user    0m0.010s
sys     0m0.090s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupmerge

real    0m0.096s
user    0m0.040s
sys     0m0.060s

andrea@laser:/misc/andrea-athlon/vma-merging >

GROWSUPNOMERGE:

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupnomerge

real    0m0.218s
user    0m0.010s
sys     0m0.200s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupnomerge

real    0m0.217s
user    0m0.020s
sys     0m0.200s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupnomerge

real    0m0.216s
user    0m0.040s
sys     0m0.180s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupnomerge

real    0m0.216s
user    0m0.050s
sys     0m0.160s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupnomerge

real    0m0.215s
user    0m0.020s
sys     0m0.190s

andrea@laser:/misc/andrea-athlon/vma-merging >

GROWSUPDOWN:

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupdown

real    0m0.220s
user    0m0.040s
sys     0m0.180s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupdown

real    0m0.218s
user    0m0.030s
sys     0m0.200s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupdown

real    0m0.220s
user    0m0.030s
sys     0m0.190s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupdown

real    0m0.219s
user    0m0.030s
sys     0m0.190s

andrea@laser:/misc/andrea-athlon/vma-merging > time ./growsupdown

real    0m0.219s
user    0m0.010s
sys     0m0.210s

andrea@laser:/misc/andrea-athlon/vma-merging >
---------------------------------------------------------------------------

End results of the mmap-rb-4 patch:

without rb-tree-4 with rb-tree-4 % improvement
growsdownmerge 0.230 0.096 +139.58%
growsdownnomerge 0.230 0.220 +4.54%
growsupmerge 0.096 0.096 0%
growsupnomerge 0.229 0.218 +5.04%
growsupdown 0.240 0.216 +11.11%

I am *very* satisfied about those results (and it still runs rock solid here, I didn't even rebooted my desktop yet since yesterday, running all the time as usual kernel compiles, mutt, kde 2.2-pre, konqueror-2.2pre, xmms etc...)

The test programs are a 5 minute hack and you can find them below for completeness (they are not cleaned up, they're appended just so you can see the exact workload I used for the benchmarks).

(btw, I could have splitted the growsupdown into growsupdownnomerge and growsupdownmerge, but it was not interesting because I just know that if math works I would have scored around + 139/2 % for the "merge" case, so the actual growsupdown is really a growsupdownnomerge that was the only one interesting and intended to stress another path of the rebalancing algorithms of the trees [actually the growdownnomerge growsupnomerge cases are the worst cases for the rb rebalancing and this is confirmed by the improvement of the growsupdown, for the avl instead the growsupnomerge and growsdownnomerge seems not the worst case, I'm not sure but it could even be the best pattern for the avl rebalancing])

If somebody is willing to also write the benchmarks for the mremap/mprotect vma merging cases he should get improvements of the order of the +139% there too.

growsdownmerge.c

---------------------------------------------------------------------------
#include <sys/mman.h>

#define NR_MAPS 55000

main()

{
	void * p[NR_MAPS];
	int i;
	char * addr = (char *) 0xa0000000;
	for (i = 0; i < NR_MAPS; i++) {
#if 0
		p[i] = mmap(0, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
#else
		p[i] = mmap(addr, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE|MAP_FIXED, -1, 0);
#if 1
		addr -= 4096;
#else
		addr -= 8192;
#endif
#endif
		if ((unsigned long) p[i] == (unsigned long) -1)
			perror("mmap"), exit(1);
#if 0
		printf("%p\n", p[i]);
#endif
	}
#if 0
	pause();

#endif
}
---------------------------------------------------------------------------

growsdownnomerge.c

---------------------------------------------------------------------------
#include <sys/mman.h>

#define NR_MAPS 55000

main()

{
	void * p[NR_MAPS];
	int i;
	char * addr = (char *) 0xa0000000;
	for (i = 0; i < NR_MAPS; i++) {
#if 0
		p[i] = mmap(0, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
#else
		p[i] = mmap(addr, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE|MAP_FIXED, -1, 0);
#if 0
		addr -= 4096;
#else
		addr -= 8192;
#endif
#endif
		if ((unsigned long) p[i] == (unsigned long) -1)
			perror("mmap"), exit(1);
#if 0
		printf("%p\n", p[i]);
#endif
	}
#if 0
	pause();

#endif
}
---------------------------------------------------------------------------

growsupmerge.c:

---------------------------------------------------------------------------
#include <sys/mman.h>

#define NR_MAPS 55000

main()

{
	void * p[NR_MAPS];
	int i;
	char * addr = (char *) 0x50000000;
	for (i = 0; i < NR_MAPS; i++) {
#if 0
		p[i] = mmap(0, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
#else
		p[i] = mmap(addr, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE|MAP_FIXED, -1, 0);
#if 1
		addr += 4096;
#else
		addr += 8192;
#endif
#endif
		if ((unsigned long) p[i] == (unsigned long) -1)
			perror("mmap"), exit(1);
#if 0
		printf("%p\n", p[i]);
#endif
	}
#if 0
	pause();

#endif
}
---------------------------------------------------------------------------

growsupnomerge.c

---------------------------------------------------------------------------
#include <sys/mman.h>

#define NR_MAPS 55000

main()

{
	void * p[NR_MAPS];
	int i;
	char * addr = (char *) 0x50000000;
	for (i = 0; i < NR_MAPS; i++) {
#if 0
		p[i] = mmap(0, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
#else
		p[i] = mmap(addr, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE|MAP_FIXED, -1, 0);
#if 0
		addr += 4096;
#else
		addr += 8192;
#endif
#endif
		if ((unsigned long) p[i] == (unsigned long) -1)
			perror("mmap"), exit(1);
#if 0
		printf("%p\n", p[i]);
#endif
	}
#if 0
	pause();

#endif
}
---------------------------------------------------------------------------

growsupdown.c

---------------------------------------------------------------------------
#include <sys/mman.h>

#define NR_MAPS 55000

main()

{
	void * p[NR_MAPS];
	int i;
	int up = 1;
	int count = 0;
	char * addr = (char *) 0x50000000;
	for (i = 0; i < NR_MAPS; i++) {
#if 0
		p[i] = mmap(0, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
#else
		p[i] = mmap(addr + (count * up), 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE|MAP_FIXED, -1, 0);
#endif
		count += 4096;
		up = -up;
		if ((unsigned long) p[i] == (unsigned long) -1)
			perror("mmap"), exit(1);
#if 0
		printf("%p\n", p[i]);
#endif
	}
#if 0
	pause();

#endif
}
---------------------------------------------------------------------------

Andrea

one more benchmark. This one is intended to benchmark the improvement of the better rebuild of the tree during fork (not just because of the faster rbtree balancing but also because of avoiding all such stupid tree lookups that the old code in 2.4.9 was used to do, the new code does zero lookup on the tree during the rebuild).

This is the testcase I wrote for it (really only the fork() syscall gets benchmarked):

rebuild-tree.c:

----------------------------------------------------------------
#include <sys/mman.h>
#include <asm/msr.h>

#define NR_MAPS 55000

main()

{
	void * p[NR_MAPS];
	int i;
	char * addr = (char *) 0x50000000;
	unsigned long long start, stop;
	int pid;

	for (i = 0; i < NR_MAPS; i++) {
#if 0
		p[i] = mmap(0, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
#else
		p[i] = mmap(addr, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE|MAP_FIXED, -1, 0);
#if 0
		addr += 4096;
#else
		addr += 8192;
#endif
#endif
		if ((unsigned long) p[i] == (unsigned long) -1)
			perror("mmap"), exit(1);
#if 0
		printf("%p\n", p[i]);
#endif
	}

#if 0
	pause();

#endif

	rdtscll(start);
	pid = fork();
	rdtscll(stop);
	if (!pid) {
		pause();
		return;
	}

	printf("fork latency due tree rebuild %Lu cpu cycles\n", stop-start);
	kill(pid, 15);
}

----------------------------------------------------------------

Here the results:

without mmap-rb-4 patch:

andrea@laser:/misc/andrea-athlon/vma-merging > for i in 1 2 3 4 5 6 7 8 9 10; do ./rebuild-tree ;done fork latency due tree rebuild 48842213 cpu cycles
fork latency due tree rebuild 48069185 cpu cycles
fork latency due tree rebuild 47687032 cpu cycles
fork latency due tree rebuild 47568124 cpu cycles
fork latency due tree rebuild 47363311 cpu cycles
fork latency due tree rebuild 47446545 cpu cycles
fork latency due tree rebuild 47446201 cpu cycles
fork latency due tree rebuild 47485410 cpu cycles
fork latency due tree rebuild 47474240 cpu cycles
fork latency due tree rebuild 47472238 cpu cycles andrea@laser:/misc/andrea-athlon/vma-merging >

with mmap-rb-4 patch:

andrea@laser:/misc/andrea-athlon/vma-merging > for i in 1 2 3 4 5 6 7 8 9 10; do ./rebuild-tree ;done fork latency due tree rebuild 43566796 cpu cycles
fork latency due tree rebuild 43808195 cpu cycles
fork latency due tree rebuild 43877997 cpu cycles
fork latency due tree rebuild 43971400 cpu cycles
fork latency due tree rebuild 43959884 cpu cycles
fork latency due tree rebuild 43584169 cpu cycles
fork latency due tree rebuild 43521534 cpu cycles
fork latency due tree rebuild 42923027 cpu cycles
fork latency due tree rebuild 43092195 cpu cycles
fork latency due tree rebuild 43110561 cpu cycles andrea@laser:/misc/andrea-athlon/vma-merging >

So it's a +8%.

Andrea