to leaf nodes have the same number of black nodes,
- root node is black
Signed-off-by: Michel Lespinasse
---
tests/rbtree_test.c | 135 +++
1 files changed, 135 insertions(+), 0 deletions(-)
create mode 100644 tests/rbtree_test.c
diff --git a/tests
if its
implementation could still inline the rb_link_node() part and call
a private __rb_insert_color function to do the rebalancing).
Signed-off-by: Michel Lespinasse
---
fs/proc/proc_sysctl.c |1 +
1 files changed, 1 insertions(+), 0 deletions(-)
diff --git a/fs/proc/proc_sysctl.c b/fs/proc
include/linux/rbtree.h included some basic usage instructions, while
Documentation/rbtree.txt had some more complete and easier to follow
instructions. Replacing the former with a reference to the latter.
Signed-off-by: Michel Lespinasse
---
include/linux/rbtree.h | 67
On Tue, Jul 10, 2012 at 5:19 AM, Michal Nazarewicz wrote:
> On Tue, 10 Jul 2012 01:35:14 +0200, Michel Lespinasse
> wrote:
>> +#defineRB_RED 0
>> +#defineRB_BLACK1
>
> Interestingly, those are almost never used. RB_BLACK is used only o
On Tue, Jul 10, 2012 at 3:59 AM, Daniel Santos wrote:
>> One final rb_init_node() caller was recently added in sysctl code
>> to implement faster sysctl name lookups. This code doesn't make use
>> of RB_EMPTY_NODE at all, and from what I could see it only called
>> rb_init_node() under the
On Tue, Jul 10, 2012 at 5:27 AM, Michal Nazarewicz wrote:
> On Tue, 10 Jul 2012 01:35:15 +0200, Michel Lespinasse
> wrote:
>> + for (i = 0; i < CHECK_LOOPS; i++) {
>> + init();
>
> Is this init() needed?
So, the reasoning here is that we first
On Tue, Jul 10, 2012 at 5:27 AM, Michal Nazarewicz wrote:
> On Tue, 10 Jul 2012 01:35:15 +0200, Michel Lespinasse
> wrote:
>> + u32 prev_key = 0;
>> +
>> + for (rb = rb_first(); rb; rb = rb_next(rb)) {
>> + struct test_node *node = rb_ent
Update the alpha arch_get_unmapped_area function to make use of
vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
arch/alpha/kernel/osf_sys.c | 20 +---
1 files changed, 9 insertions(+), 11 deletions(-)
diff --git a/arch
Update the ia64 hugetlb_get_unmapped_area function to make use of
vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
arch/ia64/mm/hugetlbpage.c | 20 +---
1 files changed, 9 insertions(+), 11 deletions(-)
diff --git a/arch
the
vm_unmapped_area() infrastructure and regain the performance.
Signed-off-by: Michel Lespinasse
---
arch/powerpc/include/asm/page_64.h |3 +-
arch/powerpc/mm/hugetlbpage.c|2 +-
arch/powerpc/mm/slice.c | 108 +
arch/powerpc
Since all architectures have been converted to use vm_unmapped_area(),
there is no remaining use for the free_area_cache.
Signed-off-by: Michel Lespinasse
---
arch/arm/mm/mmap.c |2 --
arch/arm64/mm/mmap.c |2 --
arch/mips/mm/mmap.c |2
Update the powerpc slice_get_unmapped_area function to make use of
vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
arch/powerpc/mm/slice.c | 128 +-
1 files changed, 81 insertions(+), 47
Update the ia64 arch_get_unmapped_area function to make use of
vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
arch/ia64/kernel/sys_ia64.c | 37 -
1 files changed, 12 insertions(+), 25 deletions
.
Michel Lespinasse (8):
mm: use vm_unmapped_area() on parisc architecture
mm: use vm_unmapped_area() on alpha architecture
mm: use vm_unmapped_area() on frv architecture
mm: use vm_unmapped_area() on ia64 architecture
mm: use vm_unmapped_area() in hugetlbfs on ia64 architecture
mm: remove
Update the frv arch_get_unmapped_area function to make use of
vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
arch/frv/mm/elf-fdpic.c | 49 --
1 files changed, 17 insertions(+), 32 deletions
Update the parisc arch_get_unmapped_area function to make use of
vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
arch/parisc/kernel/sys_parisc.c | 46 ++
1 files changed, 17 insertions(+), 29 deletions
Whoops, I was supposed to find a more appropriate subject line before
sending this :]
On Tue, Jan 8, 2013 at 5:28 PM, Michel Lespinasse wrote:
> These patches, which apply on top of v3.8-rc kernels, are to complete the
> VMA gap finding code I introduced (following Rik's initial pr
On Tue, Jan 8, 2013 at 6:15 PM, Benjamin Herrenschmidt
wrote:
> On Tue, 2013-01-08 at 17:28 -0800, Michel Lespinasse wrote:
>> Update the powerpc slice_get_unmapped_area function to make use of
>> vm_unmapped_area() instead of implementing a brute force search.
>>
>
Like others before me, I have discovered how easy it is to DOS a
system by abusing the rwlock_t unfairness and causing the
tasklist_lock read side to be continuously held (my abuse code makes
use of the getpriority syscall, but there are plenty of other ways
anyway).
My understanding is that the
adable and it will avoid a fuckup in the future if
> somebody changes the algorithm and forgets to update one of the
> copies :-)
All right, does the following look more palatable then ?
(didn't re-test it, though)
Signed-off-by: Michel Lespinasse
---
arch/powerpc/mm/slice.c | 123 +++
On Wed, Jan 9, 2013 at 9:49 AM, Oleg Nesterov wrote:
> On 01/08, Michel Lespinasse wrote:
>> Like others before me, I have discovered how easy it is to DOS a
>> system by abusing the rwlock_t unfairness and causing the
>> tasklist_lock read side to be continuously held
On Tue, Jan 8, 2013 at 2:30 PM, Rik van Riel wrote:
> v3: use fixed-point math for the delay calculations, suggested by Michel
> Lespinasse
>
> - if (head == ticket)
> + if (head == ticket) {
> + /*
> +
tecting hash collisions to protect us against varying hold times,
because this case could happen even with a single spinlock. So we need
to make sure the base algorithm is robust and converges towards using
the shorter of the spinlock hold times; if we have that then forcing a
reset to MIN_SPINLOCK_
On Thu, Jan 10, 2013 at 5:05 AM, Rik van Riel wrote:
> Eric,
>
> with just patches 1-3, can you still reproduce the
> regression on your system?
>
> In other words, could we get away with dropping the
> complexity of patch 4, or do we still need it?
To be clear, I must say that I'm not opposing
ttp://lespinasse.org/config-2.6.24-rc6 if that's any help.
Thanks,
--
Michel Lespinasse
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.htm
the fix in order to try out the patches. So here it is :)
- Forwarded message from Michel Lespinasse -
Date: Tue, 17 Jul 2012 17:30:35 -0700
From: Michel Lespinasse
To: Andrew Morton
Cc: Doug Ledford
Subject: [PATCH] ipc/mqueue: remove unnecessary rb_init_node calls
Commits d6629859
.
Signed-off-by: Michel Lespinasse
---
fs/jffs2/readinode.c |6 --
1 files changed, 4 insertions(+), 2 deletions(-)
diff --git a/fs/jffs2/readinode.c b/fs/jffs2/readinode.c
index dc0437e..b00fc50 100644
--- a/fs/jffs2/readinode.c
+++ b/fs/jffs2/readinode.c
@@ -395,7 +395,9 @@ static int
) and case 3 (node to remove has 2 childs,
successor is a left-descendant of the right child).
Signed-off-by: Michel Lespinasse
---
lib/rbtree.c | 115 --
1 files changed, 72 insertions(+), 43 deletions(-)
diff --git a/lib/rbtree.c b/lib
Signed-off-by: Michel Lespinasse
---
lib/rbtree_test.c | 103 +++-
1 files changed, 101 insertions(+), 2 deletions(-)
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index 4c6d250..2dfafe4 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
, as my compiler output
is now *smaller* than before for that function. Speed wise, they seem
comparable though.
Signed-off-by: Michel Lespinasse
---
include/linux/rbtree.h |5 +
lib/rbtree.c | 14 +-
lib/rbtree_test.c | 31 +++
3
006e rb_replace_node
Signed-off-by: Michel Lespinasse
---
arch/x86/mm/pat_rbtree.c | 52 +
include/linux/rbtree.h |8 -
lib/rbtree.c | 71 --
3 files changed, 33 insertions(+), 98 deletions
together, but we still call into a generic
__rb_erase_color() (passing a non-inlined callback function) for the
rebalancing work. This is intended to strike a reasonable compromise
between speed and compiled code size.
Signed-off-by: Michel Lespinasse
---
include/linux/rbtree.h |5
ack to the root really is wasteful), I have not found a nice
elegant way to do that yet, let alone in a generic way. If someone wants
to try their hand at that problem, I would be very interested to see what
they can come up with.
Michel Lespinasse (6):
rbtree: rb_erase updates and comments
rbt
This avoids fetching the parent's left child when node is actually
that child. Saves a bit on code size, though it doesn't seem to make
a large difference in speed.
Signed-off-by: Michel Lespinasse
---
lib/rbtree.c | 21 +
1 files changed, 13 insertions(+), 8 deletions(-)
diff --git
On Thu, Nov 22, 2012 at 9:49 PM, Michel Lespinasse wrote:
> On Thu, Nov 22, 2012 at 9:14 AM, Sasha Levin wrote:
>> The following patch fixed the problem for me:
>>
>> diff --git a/include/linux/rbtree_augmented.h
>> b/include/linux/rbtree_augmented.h
>&
trigger an
integer overflow which would break the rbtree ordering.
Signed-off-by: Michel Lespinasse
---
tools/kvm/util/rbtree-interval.c | 10 +-
1 files changed, 5 insertions(+), 5 deletions(-)
diff --git a/tools/kvm/util/rbtree-interval.c b/tools/kvm/util/rbtree-interval.c
index
As the rbtree intervals are not overlapping, rb_int_search_single can
trivially be implemented without making use of the max_high field.
Signed-off-by: Michel Lespinasse
---
tools/kvm/util/rbtree-interval.c | 18 +-
1 files changed, 5 insertions(+), 13 deletions(-)
diff
Since nothing depends on the max_high field values anymore, we can just
remove the field and the code that was used to maintain it.
Signed-off-by: Michel Lespinasse
---
tools/kvm/include/kvm/rbtree-interval.h | 13 ---
tools/kvm/util/rbtree-interval.c| 58
On Mon, Nov 26, 2012 at 5:16 PM, Sasha Levin wrote:
> I've built today's -next, and got the following BUG pretty quickly (2-3
> hours):
>
> [ 1556.479284] BUG: unable to handle kernel paging request at 00412000
> [ 1556.480036] IP: [] validate_mm+0x34/0x130
> [ 1556.480036] PGD 31739067
On Thu, Oct 25, 2012 at 9:23 PM, Linus Torvalds
wrote:
> On Thu, Oct 25, 2012 at 8:57 PM, Rik van Riel wrote:
>>
>> That may not even be needed. Apparently Intel chips
>> automatically flush an entry from the TLB when it
>> causes a page fault. I assume AMD chips do the same,
>> because
On Fri, Oct 26, 2012 at 5:48 AM, Andi Kleen wrote:
> Michel Lespinasse writes:
>
>> On Thu, Oct 25, 2012 at 9:23 PM, Linus Torvalds
>> wrote:
>>> On Thu, Oct 25, 2012 at 8:57 PM, Rik van Riel wrote:
>>>>
>>>> That may not even be neede
On Sun, Nov 4, 2012 at 6:20 PM, Bob Liu wrote:
> The loop for each entry of vma->anon_vma_chain in validate_mm() is not
> protected by anon_vma lock.
> I think that may be the cause.
>
> Michel, What's your opinion？
Good catch, I think that's it. Somehow it had not occured to me to
verify the
On Sun, Nov 4, 2012 at 8:14 PM, Bob Liu wrote:
> Hmm, I attached a simple fix patch.
Reviewed-by: Michel Lespinasse
(also ran some tests with it, but I could never reproduce the original
issue anyway).
Bob, it would be easier if you had sent the original patch inline
rather t
On Sun, Nov 4, 2012 at 8:44 PM, Michel Lespinasse wrote:
> On Sun, Nov 4, 2012 at 8:14 PM, Bob Liu wrote:
>> Hmm, I attached a simple fix patch.
>
> Reviewed-by: Michel Lespinasse
> (also ran some tests with it, but I could never reproduce the original
> issue an
Update the sparc32 arch_get_unmapped_area function to make use of
vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
arch/sparc/kernel/sys_sparc_32.c | 24 +---
1 files changed, 9 insertions(+), 15 deletions(-)
diff
Update the sh arch_get_unmapped_area[_topdown] functions to make
use of vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
arch/sh/mm/mmap.c | 126 ++---
1 files changed, 24 insertions(+), 102
Update the tile hugetlb_get_unmapped_area function to make use of
vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
arch/tile/mm/hugetlbpage.c | 139
1 files changed, 25 insertions(+), 114
Update the sparc64 hugetlb_get_unmapped_area function to make use of
vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
arch/sparc/mm/hugetlbpage.c | 123 ++
1 files changed, 30 insertions(+), 93
Update the sparc64 arch_get_unmapped_area[_topdown] functions to make
use of vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
arch/sparc/kernel/sys_sparc_64.c | 132 +-
1 files changed, 30 insertions
Update the mips arch_get_unmapped_area[_topdown] functions to make
use of vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
arch/mips/mm/mmap.c | 99 +--
1 files changed, 17 insertions(+), 82
eck if the following gap is suitable.
This does have the potential to make unmapping VMAs more expensive,
especially for processes with very large numbers of VMAs, where the
VMA rbtree can grow quite deep.
Signed-off-by: Michel Lespinasse
Reviewed-by: Rik van Riel
---
include/linux/mm_types.
When CONFIG_DEBUG_VM_RB is enabled, check that rb_subtree_gap is
correctly set for every vma and that mm->highest_vm_end is also correct.
Also add an explicit 'bug' variable to track if browse_rb() detected any
invalid condition.
Signed-off-by: Michel Lespinasse
Reviewed-by: Rik van R
Update the x86_64 arch_get_unmapped_area[_topdown] functions to make
use of vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
Reviewed-by: Rik van Riel
---
arch/x86/include/asm/elf.h |6 +-
arch/x86/kernel/sys_x86_64.c | 151
Update the hugetlb_get_unmapped_area function to make use of
vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
fs/hugetlbfs/inode.c | 42 --
1 files changed, 8 insertions(+), 34 deletions(-)
diff
Update the i386 hugetlb_get_unmapped_area function to make use of
vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
arch/x86/mm/hugetlbpage.c | 130 +
1 files changed, 25 insertions(+), 105
Update the arm arch_get_unmapped_area[_topdown] functions to make
use of vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
---
arch/arm/mm/mmap.c | 119 ++--
1 files changed, 23 insertions(+), 96
A mmaps the file with pgoff 0, and program B mmaps the
file with pgoff 1. The old code would align the mmaps, resulting in
misaligned pages:
A: 0123
B: 123
After this patch, they are aligned so the pages line up:
A: 0123
B: 123
Signed-off-by: Michel Lespinasse
Proposed-by: Rik van Riel
gap length
- low/high address limits that the gap must fit into
- alignment mask and offset
Also update the generic arch_get_unmapped_area[_topdown] functions to
make use of vm_unmapped_area() instead of implementing a brute force search.
Signed-off-by: Michel Lespinasse
Reviewed-by: Rik van
tree walk is in the first cache line.
Signed-off-by: Michel Lespinasse
Signed-off-by: Rik van Riel
---
include/linux/mm_types.h | 12
1 files changed, 8 insertions(+), 4 deletions(-)
diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h
index 94fa52b28ee8..528da4abf8ee
duplicating the brute force algorithm all over the place. There is
still a bit of repetition between various implementations of
arch_get_unmapped_area[_topdown] functions that could probably be
simplified somehow, but I feel we can keep that for a later step...
Michel Lespinasse (15):
mm: add
: Bob Liu
Signed-off-by: Michel Lespinasse
---
mm/mmap.c |2 ++
1 files changed, 2 insertions(+), 0 deletions(-)
diff --git a/mm/mmap.c b/mm/mmap.c
index 2d942353d681..9a796c41e7d9 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -334,8 +334,10 @@ void validate_mm(struct mm_struct *mm)
On Mon, Nov 5, 2012 at 5:25 PM, David Miller wrote:
> From: Michel Lespinasse
> Date: Mon, 5 Nov 2012 14:47:12 -0800
>
>> Update the sparc32 arch_get_unmapped_area function to make use of
>> vm_unmapped_area() instead of implementing a brute force search.
>>
>>
Adding Sasha and Bob, which I forgot to CC in the original message.
On Mon, Nov 5, 2012 at 3:06 PM, Rik van Riel wrote:
> On 11/05/2012 05:46 PM, Michel Lespinasse wrote:
>>
>> Iterate vma->anon_vma_chain without anon_vma_lock may cause NULL ptr deref
>> in
>>
On Mon, Nov 5, 2012 at 5:41 AM, Michel Lespinasse wrote:
> On Sun, Nov 4, 2012 at 8:44 PM, Michel Lespinasse wrote:
>> On Sun, Nov 4, 2012 at 8:14 PM, Bob Liu wrote:
>>> Hmm, I attached a simple fix patch.
>>
>> Reviewed-by: Michel Lespinasse
>> (also ran s
On Tue, Nov 6, 2012 at 12:24 AM, Michel Lespinasse wrote:
> On Mon, Nov 5, 2012 at 5:41 AM, Michel Lespinasse wrote:
>> On Sun, Nov 4, 2012 at 8:44 PM, Michel Lespinasse wrote:
>>> On Sun, Nov 4, 2012 at 8:14 PM, Bob Liu wrote:
>>>> Hmm, I attached a simp
ning: unused variable 'start_addr'
> [-Wunused-variable]
>
> Introduced by commit "mm: use vm_unmapped_area() on arm architecture".
Sorry for the mistakes. The following changes should fix what's been reported
so far.
commit 1c98949798ce7a1d4a910775623e1830cf88a92c
Author: Miche
e for
> each function it appears in
commit 34550b95185c1ecfa8882664744c14edda385868
Author: Michel Lespinasse
Date: Thu Nov 8 22:14:34 2012 -0800
fix mm: augment vma rbtree with rb_subtree_gap
diff --git a/mm/mmap.c b/mm/mmap.c
index d12c69eaf23f..0b8f9d83e2e2 100644
--- a/mm/mmap.c
+++ b
> arch/tile/mm/hugetlbpage.c:256:20: note: each undeclared identifier is
> reported only once for each function it appears in
commit 86234092170b43771c3f6257cb320ff6e2c10c52
Author: Michel Lespinasse
Date: Thu Nov 8 22:13:58 2012 -0800
fix mm: use vm_unmapped_area() in hugetlbfs
Hi,
I'm having an issue booting current linux-next kernels on my test
machines. Userspace crashes when it's supposed to pivot to the rootfs.
With the loglevel=8 kernel parameter, the last messages I see are:
Checking root filesystem in pivot_root init.
[6.252717] usb 2-1: link
On Fri, Nov 9, 2012 at 8:51 PM, Al Viro wrote:
> On Fri, Nov 09, 2012 at 08:36:53PM -0800, Michel Lespinasse wrote:
>> Hi,
>>
>> I'm having an issue booting current linux-next kernels on my test
>> machines. Userspace crashes when it's supposed to pivot to the roo
On Fri, Nov 9, 2012 at 9:33 PM, Al Viro wrote:
> On Fri, Nov 09, 2012 at 08:57:58PM -0800, Michel Lespinasse wrote:
>> On Fri, Nov 9, 2012 at 8:51 PM, Al Viro wrote:
>> > On Fri, Nov 09, 2012 at 08:36:53PM -0800, Michel Lespinasse wrote:
>> >> Hi,
>> >>
On Fri, Nov 9, 2012 at 11:33 PM, Al Viro wrote:
> Could you verify that this on top of for-next gets the things working again?
> It's a very lazy way to deal with that (we don't want to bother with
> restoring extras, at the very least), but the rest can go separately (and
> is shared with
that
the node being erased doesn't need to have an up to date rb_subtree_gap.
These 3 patches apply on top of the stack I previously sent (or equally,
on top of the last published mmotm).
Michel Lespinasse (3):
mm: ensure safe rb_subtree_gap update when inserting new VMA
mm: ensure safe rb_subtree_gap
the problem and to Hugh Dickins
for coming up with a simpler test case)
Reported-by: Sasha Levin
Signed-off-by: Michel Lespinasse
---
mm/mmap.c | 27 +++
1 files changed, 15 insertions(+), 12 deletions(-)
diff --git a/mm/mmap.c b/mm/mmap.c
index 619b280505fe..14859b999a9f
to propagate the rb_subtree_gap updates as high up as necessary.
Signed-off-by: Michel Lespinasse
---
mm/mmap.c | 88 ++---
1 files changed, 55 insertions(+), 33 deletions(-)
diff --git a/mm/mmap.c b/mm/mmap.c
index c60ac9fe2d7e..408d330aca6c
ure vma_rb_erase() runs before there are any
such stale rb_subtree_gap values in the rbtree.
(I don't know of a reproduceable test case for this particular issue)
Signed-off-by: Michel Lespinasse
---
mm/mmap.c |6 +++---
1 files changed, 3 insertions(+), 3 deletions(-)
diff --git a/mm/mmap.c b
On Fri, Nov 9, 2012 at 6:13 AM, Sasha Levin wrote:
> While fuzzing with trinity inside a KVM tools (lkvm) guest, using today's
> -next
> kernel, I'm getting these:
>
> [ 117.007714] free gap 7fba0dd1c000, correct 7fba0dcfb000
> [ 117.019773] map_count 750 rb -1
> [ 117.028362] [
On Fri, Oct 19, 2012 at 4:41 AM, Peter Zijlstra wrote:
> On Thu, 2012-10-18 at 17:20 -0400, Rik van Riel wrote:
>> Having the function name indicate what the function is used
>> for makes the code a little easier to read. Furthermore,
>> the fault handling code largely consists of do__page
error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or
> ‘__attribute__’ before ‘void’
>
> This patch includes linux/compiler.h in rbtree_augmented.h so that the
> __always_inline macro is resolved correctly.
>
> Cc: Pekka Enberg
> Cc: Michel Lespinasse
> Cc: Ingo Molnar
> Signed-off-by: Will
gt; include/linux/compiler.h | 32 +--
> 5 files changed, 76 insertions(+), 42 deletions(-)
>
> Changes in v6:
> o Remove extraneous double negation
> o Fixed faulty macro expansion in last patch
Acked-by: Michel Lespinasse on the entire v6 series
On Thu, Nov 22, 2012 at 9:14 AM, Sasha Levin wrote:
> Hi Michel,
>
> I've noticed a bug regarding search of ioports in the KVM tool. Since the KVM
> tool is
> using kernel's augmented rbtree implementation to represent an interval
> rbtree I dug a
> bit into the new implementation in the
rbtree users, the new interface is ~2.5 times faster than the old.
Michel Lespinasse (9):
rbtree test: fix sparse warning about 64-bit constant
rbtree: add __rb_change_child() helper function
rbtree: place easiest case first in rb_erase()
rbtree: handle 1-child recoloring in rb_erase
Add __rb_change_child() as an inline helper function to replace code that
would otherwise be duplicated 4 times in the source.
No changes to binary size or speed.
Signed-off-by: Michel Lespinasse
Reviewed-by: Rik van Riel
---
lib/rbtree.c | 46
d 3.
Signed-off-by: Michel Lespinasse
Acked-by: Rik van Riel
---
lib/rbtree.c | 98 ++
1 files changed, 64 insertions(+), 34 deletions(-)
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 80b092538fa9..938061ecbe61 100644
--- a/lib/rbtree.c
++
Small test to measure the performance of augmented rbtrees.
Signed-off-by: Michel Lespinasse
Acked-by: Rik van Riel
---
lib/rbtree_test.c | 103 +++-
1 files changed, 101 insertions(+), 2 deletions(-)
diff --git a/lib/rbtree_test.c b/lib
As proposed by Peter Zijlstra, this makes it easier to define the augmented
rbtree callbacks.
Signed-off-by: Michel Lespinasse
---
arch/x86/mm/pat_rbtree.c | 37 ++---
include/linux/rbtree.h | 30 ++
lib/rbtree_test.c
convert arch/x86/mm/pat_rbtree.c to the proposed augmented rbtree api
and remove the old augmented rbtree implementation.
Signed-off-by: Michel Lespinasse
Acked-by: Rik van Riel
---
arch/x86/mm/pat_rbtree.c | 65 +
include/linux/rbtree.h |8
the tree.
In order to preserve maximum speed for the non-augmented case,
we provide two versions of each tree manipulation function.
rb_insert_augmented() is the augmented equivalent of rb_insert_color(),
and rb_erase_augmented() is the augmented equivalent of rb_erase().
Signed-off-by: Michel
in rb_erase(). __rb_erase_color() then
only needs to handle the no-childs case and can be modified accordingly.
Signed-off-by: Michel Lespinasse
Acked-by: Rik van Riel
---
lib/rbtree.c | 105 ++
1 files changed, 62 insertions(+), 43
In rb_erase, move the easy case (node to erase has no more than
1 child) first. I feel the code reads easier that way.
Signed-off-by: Michel Lespinasse
Reviewed-by: Rik van Riel
---
lib/rbtree.c | 35 ++-
1 files changed, 18 insertions(+), 17 deletions
Just a small fix to make sparse happy.
Signed-off-by: Michel Lespinasse
Reported-by: Fengguang Wu
Acked-by: Rik van Riel
---
lib/rbtree_test.c |2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index 19dfca9ff7d7..fd09465d82ca
On Mon, Aug 20, 2012 at 02:39:26AM -0700, Michel Lespinasse wrote:
> Instead of adding an atomic count for page references, we could limit
> the anon_vma stacking depth. In fork, we would only clone anon_vmas
> that have a low enough generation count. I think that's not great
> (ad
On Mon, Aug 13, 2012 at 1:20 AM, Peter Zijlstra wrote:
> On Tue, 2012-08-07 at 00:25 -0700, Michel Lespinasse wrote:
>> a faster worst-case complexity of O(k+log N) for stabbing queries in a
>> well-balanced prio tree, vs O(k*log N) for interval trees (where k=number
>>
On Wed, Oct 3, 2012 at 7:46 AM, Daniel Santos wrote:
> On 10/03/2012 09:01 AM, Steven Rostedt wrote:
>> You don't need to use get_maintainers. It's more of a help tool to find
>> maintainers and not something that is mandatory. Not everyone that has
>> ever touched one of these files needs to be
On Tue, Sep 04, 2012 at 04:27:45PM +0200, Andrea Arcangeli wrote:
> Hi Michel,
>
> On Tue, Sep 04, 2012 at 02:20:52AM -0700, Michel Lespinasse wrote:
> > This change fixes an anon_vma locking issue in the following situation:
> > - vma has no anon_vma
> > - next has an
On Tue, Sep 4, 2012 at 3:16 PM, Andrea Arcangeli wrote:
> I would suggest to do the strict fix as above in as patch 1/8 and push
> it in -mm, and to do only the optimization removal in 3/8. I think
> we want it in -stable too later, so it'll make life easier to
> cherry-pick the commit if it's
map would miss the vmas that are being updated.
Change-Id: I6a6127d3c1fc1ab4af2acfc7ed2d269b963f6792
Signed-off-by: Michel Lespinasse
---
include/linux/mm.h | 14 +
include/linux/rmap.h | 11 ---
mm/huge_memory.c |5 ++-
mm/interval_tree.c | 14 +
mm/ks
On Fri, Sep 7, 2012 at 3:13 PM, Andrew Morton wrote:
> On Tue, 4 Sep 2012 02:20:51 -0700
> Michel Lespinasse wrote:
>
>> This commit updates the generic interval tree code that was
>> introduced in "mm: replace vma prio_tree with an interval tree".
>>
>
On Fri, Sep 07, 2012 at 03:55:14PM -0700, Andrew Morton wrote:
> On Fri, 7 Sep 2012 15:29:36 -0700
> Michel Lespinasse wrote:
>
> > > Ho hum. I don't think I can be bothered untangling all this.
> >
> > I don't think you should have to do it yourself either.
>
On Fri, Sep 07, 2012 at 03:55:14PM -0700, Andrew Morton wrote:
> On Fri, 7 Sep 2012 15:29:36 -0700
> Michel Lespinasse wrote:
>
> > > Ho hum. I don't think I can be bothered untangling all this.
> >
> > I don't think you should have to do it yourself either.
>
701 - 800 of 1086 matches
Mail list logo
