From: Ingo Molnar <mingo@kernel.org>
To: Linus Torvalds <torvalds@linux-foundation.org>
Cc: linux-kernel@vger.kernel.org,
Peter Zijlstra <a.p.zijlstra@chello.nl>,
Arnaldo Carvalho de Melo <acme@infradead.org>,
Thomas Gleixner <tglx@linutronix.de>,
Andrew Morton <akpm@linux-foundation.org>
Subject: [GIT PULL] perf fixes
Date: Mon, 6 Jul 2015 17:29:54 +0200 [thread overview]
Message-ID: <20150706152954.GA16549@gmail.com> (raw)
Linus,
Please pull the latest perf-urgent-for-linus git tree from:
git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git perf-urgent-for-linus
# HEAD: ebf2d2689de551d90965090bb991fc640a0c0d41 perf/x86: Fix copy_from_user_nmi() return if range is not ok
This:
- Fixes the perf build, by fixing the rbtree.c sharing bug between kernel and
tools/perf by creating a local copy of rbtree.c (more will be done for v4.3)
- Fixes an AUX buffer (Intel-PT support) refcounting bug
- Fixes copy_from_user_nmi() return value.
Thanks,
Ingo
------------------>
Arnaldo Carvalho de Melo (5):
tools: Adopt {READ,WRITE_ONCE} from the kernel
perf tools: Copy rbtree.h from the kernel
tools: Copy lib/rbtree.c to tools/lib/
tools: Move rbtree.h from tools/perf/
tools: Copy rbtree_augmented.h from the kernel
Peter Zijlstra (1):
perf: Fix AUX buffer refcounting
Yann Droneaud (1):
perf/x86: Fix copy_from_user_nmi() return if range is not ok
arch/x86/lib/usercopy.c | 2 +-
kernel/events/core.c | 8 -
kernel/events/internal.h | 10 +
kernel/events/ring_buffer.c | 27 +-
tools/include/linux/compiler.h | 58 +++
tools/include/linux/export.h | 10 -
tools/include/linux/rbtree.h | 104 +++++
tools/include/linux/rbtree_augmented.h | 245 ++++++++++
tools/lib/rbtree.c | 548 +++++++++++++++++++++++
tools/perf/MANIFEST | 6 +-
tools/perf/util/Build | 2 +-
tools/perf/util/include/linux/rbtree.h | 16 -
tools/perf/util/include/linux/rbtree_augmented.h | 2 -
13 files changed, 995 insertions(+), 43 deletions(-)
delete mode 100644 tools/include/linux/export.h
create mode 100644 tools/include/linux/rbtree.h
create mode 100644 tools/include/linux/rbtree_augmented.h
create mode 100644 tools/lib/rbtree.c
delete mode 100644 tools/perf/util/include/linux/rbtree.h
delete mode 100644 tools/perf/util/include/linux/rbtree_augmented.h
diff --git a/arch/x86/lib/usercopy.c b/arch/x86/lib/usercopy.c
index ddf9ecb53cc3..e342586db6e4 100644
--- a/arch/x86/lib/usercopy.c
+++ b/arch/x86/lib/usercopy.c
@@ -20,7 +20,7 @@ copy_from_user_nmi(void *to, const void __user *from, unsigned long n)
unsigned long ret;
if (__range_not_ok(from, n, TASK_SIZE))
- return 0;
+ return n;
/*
* Even though this function is typically called from NMI/IRQ context
diff --git a/kernel/events/core.c b/kernel/events/core.c
index e965cfae4207..d3dae3419b99 100644
--- a/kernel/events/core.c
+++ b/kernel/events/core.c
@@ -4358,14 +4358,6 @@ static void ring_buffer_wakeup(struct perf_event *event)
rcu_read_unlock();
}
-static void rb_free_rcu(struct rcu_head *rcu_head)
-{
- struct ring_buffer *rb;
-
- rb = container_of(rcu_head, struct ring_buffer, rcu_head);
- rb_free(rb);
-}
-
struct ring_buffer *ring_buffer_get(struct perf_event *event)
{
struct ring_buffer *rb;
diff --git a/kernel/events/internal.h b/kernel/events/internal.h
index 2deb24c7a40d..2bbad9c1274c 100644
--- a/kernel/events/internal.h
+++ b/kernel/events/internal.h
@@ -11,6 +11,7 @@
struct ring_buffer {
atomic_t refcount;
struct rcu_head rcu_head;
+ struct irq_work irq_work;
#ifdef CONFIG_PERF_USE_VMALLOC
struct work_struct work;
int page_order; /* allocation order */
@@ -55,6 +56,15 @@ struct ring_buffer {
};
extern void rb_free(struct ring_buffer *rb);
+
+static inline void rb_free_rcu(struct rcu_head *rcu_head)
+{
+ struct ring_buffer *rb;
+
+ rb = container_of(rcu_head, struct ring_buffer, rcu_head);
+ rb_free(rb);
+}
+
extern struct ring_buffer *
rb_alloc(int nr_pages, long watermark, int cpu, int flags);
extern void perf_event_wakeup(struct perf_event *event);
diff --git a/kernel/events/ring_buffer.c b/kernel/events/ring_buffer.c
index 96472824a752..b2be01b1aa9d 100644
--- a/kernel/events/ring_buffer.c
+++ b/kernel/events/ring_buffer.c
@@ -221,6 +221,8 @@ void perf_output_end(struct perf_output_handle *handle)
rcu_read_unlock();
}
+static void rb_irq_work(struct irq_work *work);
+
static void
ring_buffer_init(struct ring_buffer *rb, long watermark, int flags)
{
@@ -241,6 +243,16 @@ ring_buffer_init(struct ring_buffer *rb, long watermark, int flags)
INIT_LIST_HEAD(&rb->event_list);
spin_lock_init(&rb->event_lock);
+ init_irq_work(&rb->irq_work, rb_irq_work);
+}
+
+static void ring_buffer_put_async(struct ring_buffer *rb)
+{
+ if (!atomic_dec_and_test(&rb->refcount))
+ return;
+
+ rb->rcu_head.next = (void *)rb;
+ irq_work_queue(&rb->irq_work);
}
/*
@@ -319,7 +331,7 @@ void *perf_aux_output_begin(struct perf_output_handle *handle,
rb_free_aux(rb);
err:
- ring_buffer_put(rb);
+ ring_buffer_put_async(rb);
handle->event = NULL;
return NULL;
@@ -370,7 +382,7 @@ void perf_aux_output_end(struct perf_output_handle *handle, unsigned long size,
local_set(&rb->aux_nest, 0);
rb_free_aux(rb);
- ring_buffer_put(rb);
+ ring_buffer_put_async(rb);
}
/*
@@ -557,7 +569,18 @@ static void __rb_free_aux(struct ring_buffer *rb)
void rb_free_aux(struct ring_buffer *rb)
{
if (atomic_dec_and_test(&rb->aux_refcount))
+ irq_work_queue(&rb->irq_work);
+}
+
+static void rb_irq_work(struct irq_work *work)
+{
+ struct ring_buffer *rb = container_of(work, struct ring_buffer, irq_work);
+
+ if (!atomic_read(&rb->aux_refcount))
__rb_free_aux(rb);
+
+ if (rb->rcu_head.next == (void *)rb)
+ call_rcu(&rb->rcu_head, rb_free_rcu);
}
#ifndef CONFIG_PERF_USE_VMALLOC
diff --git a/tools/include/linux/compiler.h b/tools/include/linux/compiler.h
index f0e72674c52d..9098083869c8 100644
--- a/tools/include/linux/compiler.h
+++ b/tools/include/linux/compiler.h
@@ -41,4 +41,62 @@
#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
+#include <linux/types.h>
+
+static __always_inline void __read_once_size(const volatile void *p, void *res, int size)
+{
+ switch (size) {
+ case 1: *(__u8 *)res = *(volatile __u8 *)p; break;
+ case 2: *(__u16 *)res = *(volatile __u16 *)p; break;
+ case 4: *(__u32 *)res = *(volatile __u32 *)p; break;
+ case 8: *(__u64 *)res = *(volatile __u64 *)p; break;
+ default:
+ barrier();
+ __builtin_memcpy((void *)res, (const void *)p, size);
+ barrier();
+ }
+}
+
+static __always_inline void __write_once_size(volatile void *p, void *res, int size)
+{
+ switch (size) {
+ case 1: *(volatile __u8 *)p = *(__u8 *)res; break;
+ case 2: *(volatile __u16 *)p = *(__u16 *)res; break;
+ case 4: *(volatile __u32 *)p = *(__u32 *)res; break;
+ case 8: *(volatile __u64 *)p = *(__u64 *)res; break;
+ default:
+ barrier();
+ __builtin_memcpy((void *)p, (const void *)res, size);
+ barrier();
+ }
+}
+
+/*
+ * Prevent the compiler from merging or refetching reads or writes. The
+ * compiler is also forbidden from reordering successive instances of
+ * READ_ONCE, WRITE_ONCE and ACCESS_ONCE (see below), but only when the
+ * compiler is aware of some particular ordering. One way to make the
+ * compiler aware of ordering is to put the two invocations of READ_ONCE,
+ * WRITE_ONCE or ACCESS_ONCE() in different C statements.
+ *
+ * In contrast to ACCESS_ONCE these two macros will also work on aggregate
+ * data types like structs or unions. If the size of the accessed data
+ * type exceeds the word size of the machine (e.g., 32 bits or 64 bits)
+ * READ_ONCE() and WRITE_ONCE() will fall back to memcpy and print a
+ * compile-time warning.
+ *
+ * Their two major use cases are: (1) Mediating communication between
+ * process-level code and irq/NMI handlers, all running on the same CPU,
+ * and (2) Ensuring that the compiler does not fold, spindle, or otherwise
+ * mutilate accesses that either do not require ordering or that interact
+ * with an explicit memory barrier or atomic instruction that provides the
+ * required ordering.
+ */
+
+#define READ_ONCE(x) \
+ ({ union { typeof(x) __val; char __c[1]; } __u; __read_once_size(&(x), __u.__c, sizeof(x)); __u.__val; })
+
+#define WRITE_ONCE(x, val) \
+ ({ union { typeof(x) __val; char __c[1]; } __u = { .__val = (val) }; __write_once_size(&(x), __u.__c, sizeof(x)); __u.__val; })
+
#endif /* _TOOLS_LINUX_COMPILER_H */
diff --git a/tools/include/linux/export.h b/tools/include/linux/export.h
deleted file mode 100644
index d07e586b9ba0..000000000000
--- a/tools/include/linux/export.h
+++ /dev/null
@@ -1,10 +0,0 @@
-#ifndef _TOOLS_LINUX_EXPORT_H_
-#define _TOOLS_LINUX_EXPORT_H_
-
-#define EXPORT_SYMBOL(sym)
-#define EXPORT_SYMBOL_GPL(sym)
-#define EXPORT_SYMBOL_GPL_FUTURE(sym)
-#define EXPORT_UNUSED_SYMBOL(sym)
-#define EXPORT_UNUSED_SYMBOL_GPL(sym)
-
-#endif
diff --git a/tools/include/linux/rbtree.h b/tools/include/linux/rbtree.h
new file mode 100644
index 000000000000..112582253dd0
--- /dev/null
+++ b/tools/include/linux/rbtree.h
@@ -0,0 +1,104 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <andrea@suse.de>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/include/linux/rbtree.h
+
+ To use rbtrees you'll have to implement your own insert and search cores.
+ This will avoid us to use callbacks and to drop drammatically performances.
+ I know it's not the cleaner way, but in C (not in C++) to get
+ performances and genericity...
+
+ See Documentation/rbtree.txt for documentation and samples.
+*/
+
+#ifndef __TOOLS_LINUX_PERF_RBTREE_H
+#define __TOOLS_LINUX_PERF_RBTREE_H
+
+#include <linux/kernel.h>
+#include <linux/stddef.h>
+
+struct rb_node {
+ unsigned long __rb_parent_color;
+ struct rb_node *rb_right;
+ struct rb_node *rb_left;
+} __attribute__((aligned(sizeof(long))));
+ /* The alignment might seem pointless, but allegedly CRIS needs it */
+
+struct rb_root {
+ struct rb_node *rb_node;
+};
+
+
+#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
+
+#define RB_ROOT (struct rb_root) { NULL, }
+#define rb_entry(ptr, type, member) container_of(ptr, type, member)
+
+#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
+
+/* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
+#define RB_EMPTY_NODE(node) \
+ ((node)->__rb_parent_color == (unsigned long)(node))
+#define RB_CLEAR_NODE(node) \
+ ((node)->__rb_parent_color = (unsigned long)(node))
+
+
+extern void rb_insert_color(struct rb_node *, struct rb_root *);
+extern void rb_erase(struct rb_node *, struct rb_root *);
+
+
+/* Find logical next and previous nodes in a tree */
+extern struct rb_node *rb_next(const struct rb_node *);
+extern struct rb_node *rb_prev(const struct rb_node *);
+extern struct rb_node *rb_first(const struct rb_root *);
+extern struct rb_node *rb_last(const struct rb_root *);
+
+/* Postorder iteration - always visit the parent after its children */
+extern struct rb_node *rb_first_postorder(const struct rb_root *);
+extern struct rb_node *rb_next_postorder(const struct rb_node *);
+
+/* Fast replacement of a single node without remove/rebalance/add/rebalance */
+extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+ struct rb_root *root);
+
+static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
+ struct rb_node **rb_link)
+{
+ node->__rb_parent_color = (unsigned long)parent;
+ node->rb_left = node->rb_right = NULL;
+
+ *rb_link = node;
+}
+
+#define rb_entry_safe(ptr, type, member) \
+ ({ typeof(ptr) ____ptr = (ptr); \
+ ____ptr ? rb_entry(____ptr, type, member) : NULL; \
+ })
+
+
+/*
+ * Handy for checking that we are not deleting an entry that is
+ * already in a list, found in block/{blk-throttle,cfq-iosched}.c,
+ * probably should be moved to lib/rbtree.c...
+ */
+static inline void rb_erase_init(struct rb_node *n, struct rb_root *root)
+{
+ rb_erase(n, root);
+ RB_CLEAR_NODE(n);
+}
+#endif /* __TOOLS_LINUX_PERF_RBTREE_H */
diff --git a/tools/include/linux/rbtree_augmented.h b/tools/include/linux/rbtree_augmented.h
new file mode 100644
index 000000000000..43be941db695
--- /dev/null
+++ b/tools/include/linux/rbtree_augmented.h
@@ -0,0 +1,245 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <andrea@suse.de>
+ (C) 2002 David Woodhouse <dwmw2@infradead.org>
+ (C) 2012 Michel Lespinasse <walken@google.com>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ tools/linux/include/linux/rbtree_augmented.h
+
+ Copied from:
+ linux/include/linux/rbtree_augmented.h
+*/
+
+#ifndef _TOOLS_LINUX_RBTREE_AUGMENTED_H
+#define _TOOLS_LINUX_RBTREE_AUGMENTED_H
+
+#include <linux/compiler.h>
+#include <linux/rbtree.h>
+
+/*
+ * Please note - only struct rb_augment_callbacks and the prototypes for
+ * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
+ * The rest are implementation details you are not expected to depend on.
+ *
+ * See Documentation/rbtree.txt for documentation and samples.
+ */
+
+struct rb_augment_callbacks {
+ void (*propagate)(struct rb_node *node, struct rb_node *stop);
+ void (*copy)(struct rb_node *old, struct rb_node *new);
+ void (*rotate)(struct rb_node *old, struct rb_node *new);
+};
+
+extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
+/*
+ * Fixup the rbtree and update the augmented information when rebalancing.
+ *
+ * On insertion, the user must update the augmented information on the path
+ * leading to the inserted node, then call rb_link_node() as usual and
+ * rb_augment_inserted() instead of the usual rb_insert_color() call.
+ * If rb_augment_inserted() rebalances the rbtree, it will callback into
+ * a user provided function to update the augmented information on the
+ * affected subtrees.
+ */
+static inline void
+rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+ const struct rb_augment_callbacks *augment)
+{
+ __rb_insert_augmented(node, root, augment->rotate);
+}
+
+#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
+ rbtype, rbaugmented, rbcompute) \
+static inline void \
+rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
+{ \
+ while (rb != stop) { \
+ rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
+ rbtype augmented = rbcompute(node); \
+ if (node->rbaugmented == augmented) \
+ break; \
+ node->rbaugmented = augmented; \
+ rb = rb_parent(&node->rbfield); \
+ } \
+} \
+static inline void \
+rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
+{ \
+ rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
+ rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
+ new->rbaugmented = old->rbaugmented; \
+} \
+static void \
+rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
+{ \
+ rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
+ rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
+ new->rbaugmented = old->rbaugmented; \
+ old->rbaugmented = rbcompute(old); \
+} \
+rbstatic const struct rb_augment_callbacks rbname = { \
+ rbname ## _propagate, rbname ## _copy, rbname ## _rotate \
+};
+
+
+#define RB_RED 0
+#define RB_BLACK 1
+
+#define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
+
+#define __rb_color(pc) ((pc) & 1)
+#define __rb_is_black(pc) __rb_color(pc)
+#define __rb_is_red(pc) (!__rb_color(pc))
+#define rb_color(rb) __rb_color((rb)->__rb_parent_color)
+#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
+#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+ rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
+}
+
+static inline void rb_set_parent_color(struct rb_node *rb,
+ struct rb_node *p, int color)
+{
+ rb->__rb_parent_color = (unsigned long)p | color;
+}
+
+static inline void
+__rb_change_child(struct rb_node *old, struct rb_node *new,
+ struct rb_node *parent, struct rb_root *root)
+{
+ if (parent) {
+ if (parent->rb_left == old)
+ parent->rb_left = new;
+ else
+ parent->rb_right = new;
+ } else
+ root->rb_node = new;
+}
+
+extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
+
+static __always_inline struct rb_node *
+__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
+ const struct rb_augment_callbacks *augment)
+{
+ struct rb_node *child = node->rb_right, *tmp = node->rb_left;
+ struct rb_node *parent, *rebalance;
+ unsigned long pc;
+
+ if (!tmp) {
+ /*
+ * Case 1: node to erase has no more than 1 child (easy!)
+ *
+ * Note that if there is one child it must be red due to 5)
+ * and node must be black due to 4). We adjust colors locally
+ * so as to bypass __rb_erase_color() later on.
+ */
+ pc = node->__rb_parent_color;
+ parent = __rb_parent(pc);
+ __rb_change_child(node, child, parent, root);
+ if (child) {
+ child->__rb_parent_color = pc;
+ rebalance = NULL;
+ } else
+ rebalance = __rb_is_black(pc) ? parent : NULL;
+ tmp = parent;
+ } else if (!child) {
+ /* Still case 1, but this time the child is node->rb_left */
+ tmp->__rb_parent_color = pc = node->__rb_parent_color;
+ parent = __rb_parent(pc);
+ __rb_change_child(node, tmp, parent, root);
+ rebalance = NULL;
+ tmp = parent;
+ } else {
+ struct rb_node *successor = child, *child2;
+ tmp = child->rb_left;
+ if (!tmp) {
+ /*
+ * Case 2: node's successor is its right child
+ *
+ * (n) (s)
+ * / \ / \
+ * (x) (s) -> (x) (c)
+ * \
+ * (c)
+ */
+ parent = successor;
+ child2 = successor->rb_right;
+ augment->copy(node, successor);
+ } else {
+ /*
+ * Case 3: node's successor is leftmost under
+ * node's right child subtree
+ *
+ * (n) (s)
+ * / \ / \
+ * (x) (y) -> (x) (y)
+ * / /
+ * (p) (p)
+ * / /
+ * (s) (c)
+ * \
+ * (c)
+ */
+ do {
+ parent = successor;
+ successor = tmp;
+ tmp = tmp->rb_left;
+ } while (tmp);
+ parent->rb_left = child2 = successor->rb_right;
+ successor->rb_right = child;
+ rb_set_parent(child, successor);
+ augment->copy(node, successor);
+ augment->propagate(parent, successor);
+ }
+
+ successor->rb_left = tmp = node->rb_left;
+ rb_set_parent(tmp, successor);
+
+ pc = node->__rb_parent_color;
+ tmp = __rb_parent(pc);
+ __rb_change_child(node, successor, tmp, root);
+ if (child2) {
+ successor->__rb_parent_color = pc;
+ rb_set_parent_color(child2, parent, RB_BLACK);
+ rebalance = NULL;
+ } else {
+ unsigned long pc2 = successor->__rb_parent_color;
+ successor->__rb_parent_color = pc;
+ rebalance = __rb_is_black(pc2) ? parent : NULL;
+ }
+ tmp = successor;
+ }
+
+ augment->propagate(tmp, NULL);
+ return rebalance;
+}
+
+static __always_inline void
+rb_erase_augmented(struct rb_node *node, struct rb_root *root,
+ const struct rb_augment_callbacks *augment)
+{
+ struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
+ if (rebalance)
+ __rb_erase_color(rebalance, root, augment->rotate);
+}
+
+#endif /* _TOOLS_LINUX_RBTREE_AUGMENTED_H */
diff --git a/tools/lib/rbtree.c b/tools/lib/rbtree.c
new file mode 100644
index 000000000000..17c2b596f043
--- /dev/null
+++ b/tools/lib/rbtree.c
@@ -0,0 +1,548 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <andrea@suse.de>
+ (C) 2002 David Woodhouse <dwmw2@infradead.org>
+ (C) 2012 Michel Lespinasse <walken@google.com>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/lib/rbtree.c
+*/
+
+#include <linux/rbtree_augmented.h>
+
+/*
+ * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
+ *
+ * 1) A node is either red or black
+ * 2) The root is black
+ * 3) All leaves (NULL) are black
+ * 4) Both children of every red node are black
+ * 5) Every simple path from root to leaves contains the same number
+ * of black nodes.
+ *
+ * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
+ * consecutive red nodes in a path and every red node is therefore followed by
+ * a black. So if B is the number of black nodes on every simple path (as per
+ * 5), then the longest possible path due to 4 is 2B.
+ *
+ * We shall indicate color with case, where black nodes are uppercase and red
+ * nodes will be lowercase. Unknown color nodes shall be drawn as red within
+ * parentheses and have some accompanying text comment.
+ */
+
+static inline void rb_set_black(struct rb_node *rb)
+{
+ rb->__rb_parent_color |= RB_BLACK;
+}
+
+static inline struct rb_node *rb_red_parent(struct rb_node *red)
+{
+ return (struct rb_node *)red->__rb_parent_color;
+}
+
+/*
+ * Helper function for rotations:
+ * - old's parent and color get assigned to new
+ * - old gets assigned new as a parent and 'color' as a color.
+ */
+static inline void
+__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
+ struct rb_root *root, int color)
+{
+ struct rb_node *parent = rb_parent(old);
+ new->__rb_parent_color = old->__rb_parent_color;
+ rb_set_parent_color(old, new, color);
+ __rb_change_child(old, new, parent, root);
+}
+
+static __always_inline void
+__rb_insert(struct rb_node *node, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
+{
+ struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
+
+ while (true) {
+ /*
+ * Loop invariant: node is red
+ *
+ * If there is a black parent, we are done.
+ * Otherwise, take some corrective action as we don't
+ * want a red root or two consecutive red nodes.
+ */
+ if (!parent) {
+ rb_set_parent_color(node, NULL, RB_BLACK);
+ break;
+ } else if (rb_is_black(parent))
+ break;
+
+ gparent = rb_red_parent(parent);
+
+ tmp = gparent->rb_right;
+ if (parent != tmp) { /* parent == gparent->rb_left */
+ if (tmp && rb_is_red(tmp)) {
+ /*
+ * Case 1 - color flips
+ *
+ * G g
+ * / \ / \
+ * p u --> P U
+ * / /
+ * n n
+ *
+ * However, since g's parent might be red, and
+ * 4) does not allow this, we need to recurse
+ * at g.
+ */
+ rb_set_parent_color(tmp, gparent, RB_BLACK);
+ rb_set_parent_color(parent, gparent, RB_BLACK);
+ node = gparent;
+ parent = rb_parent(node);
+ rb_set_parent_color(node, parent, RB_RED);
+ continue;
+ }
+
+ tmp = parent->rb_right;
+ if (node == tmp) {
+ /*
+ * Case 2 - left rotate at parent
+ *
+ * G G
+ * / \ / \
+ * p U --> n U
+ * \ /
+ * n p
+ *
+ * This still leaves us in violation of 4), the
+ * continuation into Case 3 will fix that.
+ */
+ parent->rb_right = tmp = node->rb_left;
+ node->rb_left = parent;
+ if (tmp)
+ rb_set_parent_color(tmp, parent,
+ RB_BLACK);
+ rb_set_parent_color(parent, node, RB_RED);
+ augment_rotate(parent, node);
+ parent = node;
+ tmp = node->rb_right;
+ }
+
+ /*
+ * Case 3 - right rotate at gparent
+ *
+ * G P
+ * / \ / \
+ * p U --> n g
+ * / \
+ * n U
+ */
+ gparent->rb_left = tmp; /* == parent->rb_right */
+ parent->rb_right = gparent;
+ if (tmp)
+ rb_set_parent_color(tmp, gparent, RB_BLACK);
+ __rb_rotate_set_parents(gparent, parent, root, RB_RED);
+ augment_rotate(gparent, parent);
+ break;
+ } else {
+ tmp = gparent->rb_left;
+ if (tmp && rb_is_red(tmp)) {
+ /* Case 1 - color flips */
+ rb_set_parent_color(tmp, gparent, RB_BLACK);
+ rb_set_parent_color(parent, gparent, RB_BLACK);
+ node = gparent;
+ parent = rb_parent(node);
+ rb_set_parent_color(node, parent, RB_RED);
+ continue;
+ }
+
+ tmp = parent->rb_left;
+ if (node == tmp) {
+ /* Case 2 - right rotate at parent */
+ parent->rb_left = tmp = node->rb_right;
+ node->rb_right = parent;
+ if (tmp)
+ rb_set_parent_color(tmp, parent,
+ RB_BLACK);
+ rb_set_parent_color(parent, node, RB_RED);
+ augment_rotate(parent, node);
+ parent = node;
+ tmp = node->rb_left;
+ }
+
+ /* Case 3 - left rotate at gparent */
+ gparent->rb_right = tmp; /* == parent->rb_left */
+ parent->rb_left = gparent;
+ if (tmp)
+ rb_set_parent_color(tmp, gparent, RB_BLACK);
+ __rb_rotate_set_parents(gparent, parent, root, RB_RED);
+ augment_rotate(gparent, parent);
+ break;
+ }
+ }
+}
+
+/*
+ * Inline version for rb_erase() use - we want to be able to inline
+ * and eliminate the dummy_rotate callback there
+ */
+static __always_inline void
+____rb_erase_color(struct rb_node *parent, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
+{
+ struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
+
+ while (true) {
+ /*
+ * Loop invariants:
+ * - node is black (or NULL on first iteration)
+ * - node is not the root (parent is not NULL)
+ * - All leaf paths going through parent and node have a
+ * black node count that is 1 lower than other leaf paths.
+ */
+ sibling = parent->rb_right;
+ if (node != sibling) { /* node == parent->rb_left */
+ if (rb_is_red(sibling)) {
+ /*
+ * Case 1 - left rotate at parent
+ *
+ * P S
+ * / \ / \
+ * N s --> p Sr
+ * / \ / \
+ * Sl Sr N Sl
+ */
+ parent->rb_right = tmp1 = sibling->rb_left;
+ sibling->rb_left = parent;
+ rb_set_parent_color(tmp1, parent, RB_BLACK);
+ __rb_rotate_set_parents(parent, sibling, root,
+ RB_RED);
+ augment_rotate(parent, sibling);
+ sibling = tmp1;
+ }
+ tmp1 = sibling->rb_right;
+ if (!tmp1 || rb_is_black(tmp1)) {
+ tmp2 = sibling->rb_left;
+ if (!tmp2 || rb_is_black(tmp2)) {
+ /*
+ * Case 2 - sibling color flip
+ * (p could be either color here)
+ *
+ * (p) (p)
+ * / \ / \
+ * N S --> N s
+ * / \ / \
+ * Sl Sr Sl Sr
+ *
+ * This leaves us violating 5) which
+ * can be fixed by flipping p to black
+ * if it was red, or by recursing at p.
+ * p is red when coming from Case 1.
+ */
+ rb_set_parent_color(sibling, parent,
+ RB_RED);
+ if (rb_is_red(parent))
+ rb_set_black(parent);
+ else {
+ node = parent;
+ parent = rb_parent(node);
+ if (parent)
+ continue;
+ }
+ break;
+ }
+ /*
+ * Case 3 - right rotate at sibling
+ * (p could be either color here)
+ *
+ * (p) (p)
+ * / \ / \
+ * N S --> N Sl
+ * / \ \
+ * sl Sr s
+ * \
+ * Sr
+ */
+ sibling->rb_left = tmp1 = tmp2->rb_right;
+ tmp2->rb_right = sibling;
+ parent->rb_right = tmp2;
+ if (tmp1)
+ rb_set_parent_color(tmp1, sibling,
+ RB_BLACK);
+ augment_rotate(sibling, tmp2);
+ tmp1 = sibling;
+ sibling = tmp2;
+ }
+ /*
+ * Case 4 - left rotate at parent + color flips
+ * (p and sl could be either color here.
+ * After rotation, p becomes black, s acquires
+ * p's color, and sl keeps its color)
+ *
+ * (p) (s)
+ * / \ / \
+ * N S --> P Sr
+ * / \ / \
+ * (sl) sr N (sl)
+ */
+ parent->rb_right = tmp2 = sibling->rb_left;
+ sibling->rb_left = parent;
+ rb_set_parent_color(tmp1, sibling, RB_BLACK);
+ if (tmp2)
+ rb_set_parent(tmp2, parent);
+ __rb_rotate_set_parents(parent, sibling, root,
+ RB_BLACK);
+ augment_rotate(parent, sibling);
+ break;
+ } else {
+ sibling = parent->rb_left;
+ if (rb_is_red(sibling)) {
+ /* Case 1 - right rotate at parent */
+ parent->rb_left = tmp1 = sibling->rb_right;
+ sibling->rb_right = parent;
+ rb_set_parent_color(tmp1, parent, RB_BLACK);
+ __rb_rotate_set_parents(parent, sibling, root,
+ RB_RED);
+ augment_rotate(parent, sibling);
+ sibling = tmp1;
+ }
+ tmp1 = sibling->rb_left;
+ if (!tmp1 || rb_is_black(tmp1)) {
+ tmp2 = sibling->rb_right;
+ if (!tmp2 || rb_is_black(tmp2)) {
+ /* Case 2 - sibling color flip */
+ rb_set_parent_color(sibling, parent,
+ RB_RED);
+ if (rb_is_red(parent))
+ rb_set_black(parent);
+ else {
+ node = parent;
+ parent = rb_parent(node);
+ if (parent)
+ continue;
+ }
+ break;
+ }
+ /* Case 3 - right rotate at sibling */
+ sibling->rb_right = tmp1 = tmp2->rb_left;
+ tmp2->rb_left = sibling;
+ parent->rb_left = tmp2;
+ if (tmp1)
+ rb_set_parent_color(tmp1, sibling,
+ RB_BLACK);
+ augment_rotate(sibling, tmp2);
+ tmp1 = sibling;
+ sibling = tmp2;
+ }
+ /* Case 4 - left rotate at parent + color flips */
+ parent->rb_left = tmp2 = sibling->rb_right;
+ sibling->rb_right = parent;
+ rb_set_parent_color(tmp1, sibling, RB_BLACK);
+ if (tmp2)
+ rb_set_parent(tmp2, parent);
+ __rb_rotate_set_parents(parent, sibling, root,
+ RB_BLACK);
+ augment_rotate(parent, sibling);
+ break;
+ }
+ }
+}
+
+/* Non-inline version for rb_erase_augmented() use */
+void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
+{
+ ____rb_erase_color(parent, root, augment_rotate);
+}
+
+/*
+ * Non-augmented rbtree manipulation functions.
+ *
+ * We use dummy augmented callbacks here, and have the compiler optimize them
+ * out of the rb_insert_color() and rb_erase() function definitions.
+ */
+
+static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
+static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
+static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
+
+static const struct rb_augment_callbacks dummy_callbacks = {
+ dummy_propagate, dummy_copy, dummy_rotate
+};
+
+void rb_insert_color(struct rb_node *node, struct rb_root *root)
+{
+ __rb_insert(node, root, dummy_rotate);
+}
+
+void rb_erase(struct rb_node *node, struct rb_root *root)
+{
+ struct rb_node *rebalance;
+ rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
+ if (rebalance)
+ ____rb_erase_color(rebalance, root, dummy_rotate);
+}
+
+/*
+ * Augmented rbtree manipulation functions.
+ *
+ * This instantiates the same __always_inline functions as in the non-augmented
+ * case, but this time with user-defined callbacks.
+ */
+
+void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
+{
+ __rb_insert(node, root, augment_rotate);
+}
+
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+struct rb_node *rb_first(const struct rb_root *root)
+{
+ struct rb_node *n;
+
+ n = root->rb_node;
+ if (!n)
+ return NULL;
+ while (n->rb_left)
+ n = n->rb_left;
+ return n;
+}
+
+struct rb_node *rb_last(const struct rb_root *root)
+{
+ struct rb_node *n;
+
+ n = root->rb_node;
+ if (!n)
+ return NULL;
+ while (n->rb_right)
+ n = n->rb_right;
+ return n;
+}
+
+struct rb_node *rb_next(const struct rb_node *node)
+{
+ struct rb_node *parent;
+
+ if (RB_EMPTY_NODE(node))
+ return NULL;
+
+ /*
+ * If we have a right-hand child, go down and then left as far
+ * as we can.
+ */
+ if (node->rb_right) {
+ node = node->rb_right;
+ while (node->rb_left)
+ node=node->rb_left;
+ return (struct rb_node *)node;
+ }
+
+ /*
+ * No right-hand children. Everything down and left is smaller than us,
+ * so any 'next' node must be in the general direction of our parent.
+ * Go up the tree; any time the ancestor is a right-hand child of its
+ * parent, keep going up. First time it's a left-hand child of its
+ * parent, said parent is our 'next' node.
+ */
+ while ((parent = rb_parent(node)) && node == parent->rb_right)
+ node = parent;
+
+ return parent;
+}
+
+struct rb_node *rb_prev(const struct rb_node *node)
+{
+ struct rb_node *parent;
+
+ if (RB_EMPTY_NODE(node))
+ return NULL;
+
+ /*
+ * If we have a left-hand child, go down and then right as far
+ * as we can.
+ */
+ if (node->rb_left) {
+ node = node->rb_left;
+ while (node->rb_right)
+ node=node->rb_right;
+ return (struct rb_node *)node;
+ }
+
+ /*
+ * No left-hand children. Go up till we find an ancestor which
+ * is a right-hand child of its parent.
+ */
+ while ((parent = rb_parent(node)) && node == parent->rb_left)
+ node = parent;
+
+ return parent;
+}
+
+void rb_replace_node(struct rb_node *victim, struct rb_node *new,
+ struct rb_root *root)
+{
+ struct rb_node *parent = rb_parent(victim);
+
+ /* Set the surrounding nodes to point to the replacement */
+ __rb_change_child(victim, new, parent, root);
+ if (victim->rb_left)
+ rb_set_parent(victim->rb_left, new);
+ if (victim->rb_right)
+ rb_set_parent(victim->rb_right, new);
+
+ /* Copy the pointers/colour from the victim to the replacement */
+ *new = *victim;
+}
+
+static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
+{
+ for (;;) {
+ if (node->rb_left)
+ node = node->rb_left;
+ else if (node->rb_right)
+ node = node->rb_right;
+ else
+ return (struct rb_node *)node;
+ }
+}
+
+struct rb_node *rb_next_postorder(const struct rb_node *node)
+{
+ const struct rb_node *parent;
+ if (!node)
+ return NULL;
+ parent = rb_parent(node);
+
+ /* If we're sitting on node, we've already seen our children */
+ if (parent && node == parent->rb_left && parent->rb_right) {
+ /* If we are the parent's left node, go to the parent's right
+ * node then all the way down to the left */
+ return rb_left_deepest_node(parent->rb_right);
+ } else
+ /* Otherwise we are the parent's right node, and the parent
+ * should be next */
+ return (struct rb_node *)parent;
+}
+
+struct rb_node *rb_first_postorder(const struct rb_root *root)
+{
+ if (!root->rb_node)
+ return NULL;
+
+ return rb_left_deepest_node(root->rb_node);
+}
diff --git a/tools/perf/MANIFEST b/tools/perf/MANIFEST
index fe50a1b34aa0..09dc0aabb515 100644
--- a/tools/perf/MANIFEST
+++ b/tools/perf/MANIFEST
@@ -18,6 +18,7 @@ tools/arch/x86/include/asm/atomic.h
tools/arch/x86/include/asm/rmwcc.h
tools/lib/traceevent
tools/lib/api
+tools/lib/rbtree.c
tools/lib/symbol/kallsyms.c
tools/lib/symbol/kallsyms.h
tools/lib/util/find_next_bit.c
@@ -44,6 +45,8 @@ tools/include/linux/kernel.h
tools/include/linux/list.h
tools/include/linux/log2.h
tools/include/linux/poison.h
+tools/include/linux/rbtree.h
+tools/include/linux/rbtree_augmented.h
tools/include/linux/types.h
include/asm-generic/bitops/arch_hweight.h
include/asm-generic/bitops/const_hweight.h
@@ -51,12 +54,10 @@ include/asm-generic/bitops/fls64.h
include/asm-generic/bitops/__fls.h
include/asm-generic/bitops/fls.h
include/linux/perf_event.h
-include/linux/rbtree.h
include/linux/list.h
include/linux/hash.h
include/linux/stringify.h
lib/hweight.c
-lib/rbtree.c
include/linux/swab.h
arch/*/include/asm/unistd*.h
arch/*/include/uapi/asm/unistd*.h
@@ -65,7 +66,6 @@ arch/*/lib/memcpy*.S
arch/*/lib/memset*.S
include/linux/poison.h
include/linux/hw_breakpoint.h
-include/linux/rbtree_augmented.h
include/uapi/linux/perf_event.h
include/uapi/linux/const.h
include/uapi/linux/swab.h
diff --git a/tools/perf/util/Build b/tools/perf/util/Build
index 586a59d46022..601d11440596 100644
--- a/tools/perf/util/Build
+++ b/tools/perf/util/Build
@@ -139,7 +139,7 @@ $(OUTPUT)util/find_next_bit.o: ../lib/util/find_next_bit.c FORCE
$(call rule_mkdir)
$(call if_changed_dep,cc_o_c)
-$(OUTPUT)util/rbtree.o: ../../lib/rbtree.c FORCE
+$(OUTPUT)util/rbtree.o: ../lib/rbtree.c FORCE
$(call rule_mkdir)
$(call if_changed_dep,cc_o_c)
diff --git a/tools/perf/util/include/linux/rbtree.h b/tools/perf/util/include/linux/rbtree.h
deleted file mode 100644
index f06d89f0b867..000000000000
--- a/tools/perf/util/include/linux/rbtree.h
+++ /dev/null
@@ -1,16 +0,0 @@
-#ifndef __TOOLS_LINUX_PERF_RBTREE_H
-#define __TOOLS_LINUX_PERF_RBTREE_H
-#include <stdbool.h>
-#include "../../../../include/linux/rbtree.h"
-
-/*
- * Handy for checking that we are not deleting an entry that is
- * already in a list, found in block/{blk-throttle,cfq-iosched}.c,
- * probably should be moved to lib/rbtree.c...
- */
-static inline void rb_erase_init(struct rb_node *n, struct rb_root *root)
-{
- rb_erase(n, root);
- RB_CLEAR_NODE(n);
-}
-#endif /* __TOOLS_LINUX_PERF_RBTREE_H */
diff --git a/tools/perf/util/include/linux/rbtree_augmented.h b/tools/perf/util/include/linux/rbtree_augmented.h
deleted file mode 100644
index 9d6fcdf1788b..000000000000
--- a/tools/perf/util/include/linux/rbtree_augmented.h
+++ /dev/null
@@ -1,2 +0,0 @@
-#include <stdbool.h>
-#include "../../../../include/linux/rbtree_augmented.h"
next reply other threads:[~2015-07-06 15:30 UTC|newest]
Thread overview: 376+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-07-06 15:29 Ingo Molnar [this message]
-- strict thread matches above, loose matches on Subject: below --
2023-01-06 11:57 [GIT PULL] perf fixes Ingo Molnar
2023-01-06 21:19 ` pr-tracker-bot
2022-10-02 10:56 Ingo Molnar
2022-10-02 16:47 ` Linus Torvalds
2022-10-03 10:55 ` Ingo Molnar
2022-10-02 17:20 ` pr-tracker-bot
2022-08-28 14:35 Ingo Molnar
2022-08-28 18:18 ` pr-tracker-bot
2022-08-06 19:10 Ingo Molnar
2022-08-07 0:50 ` pr-tracker-bot
2021-07-11 13:26 Ingo Molnar
2021-07-11 18:22 ` pr-tracker-bot
2021-06-12 12:48 Ingo Molnar
2021-06-12 19:09 ` pr-tracker-bot
2021-03-21 10:56 Ingo Molnar
2021-03-21 18:45 ` pr-tracker-bot
2020-08-15 11:21 Ingo Molnar
2020-08-16 1:55 ` pr-tracker-bot
2020-04-25 9:19 Ingo Molnar
2020-04-25 19:30 ` pr-tracker-bot
2020-03-24 9:19 Ingo Molnar
2020-03-24 17:15 ` pr-tracker-bot
2020-03-02 7:23 Ingo Molnar
2020-03-03 23:35 ` pr-tracker-bot
2020-02-15 8:53 Ingo Molnar
2020-02-15 21:25 ` pr-tracker-bot
2020-01-18 17:58 Ingo Molnar
2020-01-18 21:05 ` pr-tracker-bot
2019-12-21 16:16 Ingo Molnar
2019-12-21 18:55 ` pr-tracker-bot
2019-12-17 11:34 Ingo Molnar
2019-12-17 19:06 ` Linus Torvalds
2019-12-18 6:58 ` Ingo Molnar
2019-12-17 19:20 ` pr-tracker-bot
2019-12-01 22:15 Ingo Molnar
2019-12-02 4:40 ` pr-tracker-bot
2019-11-16 21:33 Ingo Molnar
2019-11-17 0:35 ` pr-tracker-bot
2019-11-01 17:48 Ingo Molnar
2019-11-01 18:48 ` Linus Torvalds
2019-11-01 20:30 ` Ingo Molnar
2019-11-01 21:01 ` Ingo Molnar
2019-11-01 22:15 ` Linus Torvalds
2019-11-01 19:10 ` pr-tracker-bot
2019-10-12 13:31 Ingo Molnar
2019-10-12 22:35 ` pr-tracker-bot
2019-07-14 12:01 Ingo Molnar
2019-07-14 18:45 ` pr-tracker-bot
2019-06-29 8:54 Ingo Molnar
2019-06-29 11:45 ` pr-tracker-bot
2019-06-02 17:39 Ingo Molnar
2019-06-02 18:15 ` pr-tracker-bot
2019-05-16 16:05 Ingo Molnar
2019-05-16 18:20 ` pr-tracker-bot
2019-05-05 12:47 Ingo Molnar
2019-05-05 22:10 ` pr-tracker-bot
2019-04-20 7:43 Ingo Molnar
2019-04-20 19:25 ` pr-tracker-bot
2019-04-12 13:06 Ingo Molnar
2019-04-13 4:05 ` pr-tracker-bot
2019-02-17 10:10 Ingo Molnar
2019-02-17 16:50 ` pr-tracker-bot
2019-02-10 9:01 Ingo Molnar
2019-02-10 18:30 ` pr-tracker-bot
2019-01-11 7:44 Ingo Molnar
2019-01-11 18:00 ` pr-tracker-bot
2018-11-30 6:25 Ingo Molnar
2018-11-30 21:00 ` pr-tracker-bot
2018-11-17 10:55 Ingo Molnar
2018-11-18 20:05 ` pr-tracker-bot
2018-10-20 8:10 Ingo Molnar
2018-10-20 13:28 ` Greg Kroah-Hartman
2018-10-11 9:12 Ingo Molnar
2018-10-11 12:32 ` Greg Kroah-Hartman
2018-10-11 8:59 Ingo Molnar
2018-10-05 9:42 Ingo Molnar
2018-10-05 9:55 ` Ingo Molnar
2018-10-05 23:30 ` Greg Kroah-Hartman
2018-09-15 13:11 Ingo Molnar
2018-07-30 17:53 Ingo Molnar
2018-07-13 19:59 Ingo Molnar
2018-06-30 8:44 Ingo Molnar
2018-06-04 9:04 Ingo Molnar
2018-03-31 10:40 Ingo Molnar
2018-03-25 8:53 Ingo Molnar
2018-02-06 21:29 Ingo Molnar
2017-12-06 22:17 Ingo Molnar
2017-11-26 12:40 Ingo Molnar
2017-11-05 14:40 Ingo Molnar
2017-11-09 8:13 ` Markus Trippelsdorf
2017-10-14 16:04 Ingo Molnar
2017-09-13 18:00 Ingo Molnar
2017-09-12 15:32 Ingo Molnar
2017-07-21 10:15 Ingo Molnar
2017-06-10 8:39 Ingo Molnar
2017-05-12 7:31 Ingo Molnar
2017-03-07 20:30 Ingo Molnar
2017-02-28 8:01 Ingo Molnar
2017-02-11 18:12 Ingo Molnar
2017-02-02 21:01 Ingo Molnar
2017-01-18 9:27 Ingo Molnar
2017-01-15 9:59 Ingo Molnar
2016-12-23 22:50 Ingo Molnar
2016-12-07 18:45 Ingo Molnar
2016-11-23 9:00 Ingo Molnar
2016-11-14 7:56 Ingo Molnar
2016-10-28 19:41 Ingo Molnar
2016-10-18 11:07 Ingo Molnar
2016-09-13 18:14 Ingo Molnar
2016-08-18 20:38 Ingo Molnar
2016-08-12 19:35 Ingo Molnar
2016-07-26 14:13 Ingo Molnar
2016-07-08 13:42 Ingo Molnar
2016-06-10 12:50 Ingo Molnar
2016-05-13 18:51 Ingo Molnar
2016-05-06 11:26 Ingo Molnar
2016-04-28 17:56 Ingo Molnar
2016-04-03 11:00 Ingo Molnar
2016-02-20 11:14 Ingo Molnar
2016-01-14 10:03 Ingo Molnar
2016-01-08 12:46 Ingo Molnar
2015-12-08 4:22 Ingo Molnar
2015-09-17 8:02 Ingo Molnar
2015-09-02 18:11 Ingo Molnar
2015-08-22 12:19 Ingo Molnar
2015-08-14 7:12 Ingo Molnar
2015-07-18 2:53 Ingo Molnar
2015-06-13 14:29 Ingo Molnar
2015-06-05 8:37 Ingo Molnar
2015-05-15 7:17 Ingo Molnar
2015-05-06 12:52 Ingo Molnar
2015-04-03 13:11 Ingo Molnar
2015-03-17 16:48 Ingo Molnar
2015-03-01 17:00 Ingo Molnar
2015-02-20 13:40 Ingo Molnar
2015-01-30 18:44 Ingo Molnar
2015-01-17 14:15 Ingo Molnar
2015-01-11 8:42 Ingo Molnar
2014-11-20 7:46 Ingo Molnar
2014-10-31 11:13 Ingo Molnar
2014-11-03 9:02 ` Paul Bolle
2014-11-03 10:04 ` Peter Zijlstra
2014-09-19 10:46 Ingo Molnar
2014-08-24 20:25 Ingo Molnar
2014-07-16 11:11 Ingo Molnar
2014-06-18 16:39 Ingo Molnar
2014-05-22 8:04 Ingo Molnar
2014-05-01 6:34 Ingo Molnar
2014-04-20 8:02 Ingo Molnar
2014-04-19 10:41 Ingo Molnar
2014-04-16 13:04 Ingo Molnar
2014-03-22 9:06 Ingo Molnar
2014-03-16 16:34 Ingo Molnar
2014-03-02 8:51 Ingo Molnar
2014-02-22 19:16 Ingo Molnar
2014-02-09 8:01 Ingo Molnar
2014-01-25 7:30 Ingo Molnar
2014-01-19 12:08 Ingo Molnar
2013-12-19 16:52 Ingo Molnar
2013-12-02 14:39 Ingo Molnar
2013-11-15 19:46 Ingo Molnar
2013-11-01 9:56 Ingo Molnar
2013-10-29 10:04 Ingo Molnar
2013-10-26 12:24 Ingo Molnar
2013-10-28 8:28 ` Markus Trippelsdorf
2013-10-28 9:02 ` ------------------------------ Markus Trippelsdorf
2013-10-28 9:34 ` Markus Trippelsdorf
2013-10-28 12:34 ` Arnaldo Carvalho de Melo
2013-10-28 12:42 ` Arnaldo Carvalho de Melo
2013-10-28 12:59 ` Markus Trippelsdorf
2013-10-29 9:50 ` Stephane Eranian
2013-10-29 10:06 ` Ingo Molnar
2013-10-29 12:47 ` Arnaldo Carvalho de Melo
2013-10-08 12:12 Ingo Molnar
2013-09-28 18:03 Ingo Molnar
2013-09-29 11:47 ` Markus Trippelsdorf
2013-09-29 21:33 ` Andi Kleen
2013-09-29 22:47 ` Markus Trippelsdorf
2013-09-30 6:27 ` Ingo Molnar
2013-09-30 18:54 ` Andi Kleen
2013-10-01 8:42 ` Ingo Molnar
2013-09-25 18:00 Ingo Molnar
2013-09-18 16:06 Ingo Molnar
2013-09-12 13:38 Ingo Molnar
2013-09-12 18:03 ` Linus Torvalds
2013-09-12 18:10 ` Linus Torvalds
2013-09-12 18:43 ` Arnaldo Carvalho de Melo
2013-09-12 19:12 ` Arnaldo Carvalho de Melo
2013-09-12 19:13 ` Linus Torvalds
2013-09-12 19:55 ` Ingo Molnar
2013-09-12 19:58 ` David Ahern
2013-09-12 20:02 ` Arnaldo Carvalho de Melo
2013-09-12 20:31 ` Ingo Molnar
2013-09-12 20:43 ` Ingo Molnar
2013-09-12 20:18 ` Ingo Molnar
2013-09-12 20:38 ` Arnaldo Carvalho de Melo
2013-09-12 20:46 ` Ingo Molnar
2013-09-12 21:09 ` David Ahern
2013-09-12 21:18 ` Ingo Molnar
2013-09-12 22:10 ` David Ahern
2013-09-13 5:09 ` Ingo Molnar
2013-09-13 9:32 ` Jean Pihet
2013-09-13 9:45 ` Ingo Molnar
2013-09-13 17:15 ` Jean Pihet
2013-09-12 18:51 ` Linus Torvalds
2013-09-12 20:33 ` Ingo Molnar
2013-09-12 20:38 ` Linus Torvalds
2013-09-12 20:49 ` Ingo Molnar
2013-09-12 20:52 ` Linus Torvalds
2013-09-12 21:01 ` Ingo Molnar
2013-09-12 20:10 ` Ingo Molnar
2013-08-13 16:51 Ingo Molnar
2013-07-10 8:52 Ingo Molnar
2013-06-26 8:52 Ingo Molnar
2013-06-20 8:58 Ingo Molnar
2013-05-05 10:10 Ingo Molnar
2013-04-21 8:16 Ingo Molnar
2013-04-14 15:20 Ingo Molnar
2013-03-21 9:56 Ingo Molnar
2013-03-11 14:28 Ingo Molnar
2013-02-26 7:02 Ingo Molnar
2013-03-14 20:32 ` Linus Torvalds
2013-03-14 21:06 ` Linus Torvalds
2013-03-14 22:09 ` Stephane Eranian
2013-03-14 22:17 ` Linus Torvalds
2013-03-14 22:19 ` Stephane Eranian
2013-03-14 22:42 ` Stephane Eranian
2013-03-14 22:53 ` Stephane Eranian
2013-03-14 23:11 ` Stephane Eranian
2013-03-15 0:24 ` Stephane Eranian
2013-03-15 1:06 ` Linus Torvalds
2013-03-15 8:01 ` Stephane Eranian
2013-03-15 10:50 ` Stephane Eranian
2013-02-04 18:20 Ingo Molnar
2012-12-01 11:11 Ingo Molnar
2012-10-26 14:44 Ingo Molnar
2012-10-23 11:02 Ingo Molnar
2012-10-20 0:56 Ingo Molnar
2012-09-21 19:08 Ingo Molnar
2012-09-13 14:39 Ingo Molnar
2012-08-23 10:59 Ingo Molnar
2012-08-20 9:08 Ingo Molnar
2012-08-21 7:59 ` Ingo Molnar
2012-08-05 17:43 Ingo Molnar
2012-08-03 16:40 Ingo Molnar
2012-07-14 7:51 Ingo Molnar
2012-06-22 13:36 Ingo Molnar
2012-06-22 18:07 ` Linus Torvalds
2012-06-22 18:38 ` Hagen Paul Pfeifer
2012-06-22 18:52 ` Linus Torvalds
2012-06-22 19:06 ` Hagen Paul Pfeifer
2012-06-22 19:54 ` Steven Rostedt
[not found] ` <86448d73-2e19-416f-8104-ce72aa5d76eb@email.android.com>
2012-06-22 23:18 ` Steven Rostedt
2012-06-23 0:51 ` Arjan van de Ven
2012-06-23 1:57 ` Steven Rostedt
2012-06-23 18:25 ` H. Peter Anvin
2012-06-22 18:50 ` Steven Rostedt
2012-06-15 18:48 Ingo Molnar
2012-06-08 9:20 Ingo Molnar
2012-05-30 15:39 Ingo Molnar
2012-05-17 8:19 Ingo Molnar
2012-04-27 6:32 Ingo Molnar
2012-04-16 17:48 Ingo Molnar
2012-04-14 10:54 Ingo Molnar
2012-04-03 22:40 Ingo Molnar
2012-03-13 16:56 Ingo Molnar
2012-03-05 9:27 Ingo Molnar
2012-03-02 10:47 Ingo Molnar
2012-02-10 12:45 Ingo Molnar
2012-02-02 10:00 Ingo Molnar
2012-01-26 18:11 Ingo Molnar
2011-12-29 21:02 Ingo Molnar
2011-12-09 6:16 Ingo Molnar
2011-12-05 19:13 Ingo Molnar
2011-11-07 18:49 Ingo Molnar
2011-11-07 19:00 ` Linus Torvalds
2011-11-07 19:50 ` Ingo Molnar
2011-08-22 17:00 Ingo Molnar
2011-08-11 8:17 Ingo Molnar
2011-07-07 18:11 Ingo Molnar
2011-06-19 8:44 Ingo Molnar
2011-06-13 9:53 Ingo Molnar
2011-06-08 13:46 Ingo Molnar
2011-05-28 16:34 Ingo Molnar
2011-05-24 2:41 Ingo Molnar
2011-05-23 13:41 Ingo Molnar
2011-05-23 22:10 ` Eric Dumazet
2011-05-23 22:19 ` Frederic Weisbecker
2011-05-23 22:22 ` Eric Dumazet
2011-05-20 17:18 Ingo Molnar
2011-05-17 22:07 Ingo Molnar
2011-05-07 18:20 Ingo Molnar
2011-04-29 18:17 Ingo Molnar
2011-04-22 13:42 Ingo Molnar
2011-04-19 15:56 Ingo Molnar
2011-04-16 10:03 Ingo Molnar
2011-04-07 17:48 Ingo Molnar
2011-04-02 10:25 Ingo Molnar
2011-03-25 13:11 Ingo Molnar
2011-03-10 7:53 Ingo Molnar
2011-02-28 17:34 Ingo Molnar
2011-02-22 16:03 Ingo Molnar
2011-02-15 16:58 Ingo Molnar
2011-02-06 11:27 Ingo Molnar
2011-02-03 15:47 Ingo Molnar
2011-01-24 13:34 Ingo Molnar
2011-01-24 19:48 ` Linus Torvalds
2011-01-24 20:07 ` Ingo Molnar
2011-01-24 20:11 ` Ingo Molnar
2011-01-24 20:17 ` Ingo Molnar
2011-01-24 20:17 ` Linus Torvalds
2011-01-24 20:27 ` Linus Torvalds
2011-01-24 20:38 ` Arnaldo Carvalho de Melo
2011-01-24 21:13 ` Linus Torvalds
2011-01-24 21:25 ` Ingo Molnar
2011-01-24 22:00 ` Arnaldo Carvalho de Melo
2011-01-25 0:16 ` Ingo Molnar
2011-01-24 20:37 ` Davidlohr Bueso
2011-01-24 20:14 ` Arnaldo Carvalho de Melo
2011-01-18 18:59 Ingo Molnar
2011-01-18 9:42 Ingo Molnar
2011-01-15 15:24 Ingo Molnar
2011-01-11 11:32 Ingo Molnar
2011-01-03 19:04 Ingo Molnar
2010-12-23 12:56 Ingo Molnar
2010-12-19 15:34 Ingo Molnar
2010-12-08 7:55 Ingo Molnar
2010-11-28 17:36 Ingo Molnar
2010-11-26 13:20 Ingo Molnar
2010-11-11 10:38 Ingo Molnar
2010-10-30 18:21 Ingo Molnar
2010-10-13 15:21 Ingo Molnar
2010-10-05 14:49 Ingo Molnar
2010-09-26 8:38 Ingo Molnar
2010-09-21 19:39 Ingo Molnar
2010-09-10 14:26 Ingo Molnar
2010-08-25 17:44 Ingo Molnar
2010-08-24 19:06 Ingo Molnar
2010-08-19 14:55 Ingo Molnar
2010-08-18 8:14 Ingo Molnar
2010-07-23 19:41 Ingo Molnar
2010-07-16 17:30 Ingo Molnar
2010-07-08 4:36 Frederic Weisbecker
2010-07-08 4:40 ` Frederic Weisbecker
2010-07-08 6:36 ` Ingo Molnar
2010-07-04 20:24 Ingo Molnar
2010-06-10 10:25 Ingo Molnar
2010-06-02 12:28 Ingo Molnar
2010-05-31 23:02 Frederic Weisbecker
2010-06-01 6:59 ` Ingo Molnar
2010-05-30 19:27 Ingo Molnar
2010-05-20 9:44 Frederic Weisbecker
2010-05-20 12:40 ` Ingo Molnar
2010-05-11 19:18 Ingo Molnar
2010-05-12 0:39 ` Linus Torvalds
2010-04-06 17:49 Ingo Molnar
2010-04-04 10:15 Ingo Molnar
2010-04-03 10:47 Frederic Weisbecker
2010-03-28 5:11 Frederic Weisbecker
2010-03-29 3:33 ` Ingo Molnar
2010-03-26 15:16 Ingo Molnar
2010-03-16 16:06 Ingo Molnar
2010-03-11 19:12 Ingo Molnar
2010-02-22 16:50 Ingo Molnar
2010-02-22 17:01 ` Linus Torvalds
2010-02-22 17:15 ` Frederic Weisbecker
2010-02-14 9:06 Ingo Molnar
2010-01-31 17:32 Ingo Molnar
2010-01-21 15:38 Ingo Molnar
2009-12-31 12:00 Ingo Molnar
2009-12-18 18:59 Ingo Molnar
2009-09-22 7:51 Ingo Molnar
2009-09-22 14:49 ` Linus Torvalds
2009-09-22 14:59 ` Ingo Molnar
2009-09-22 15:13 ` Linus Torvalds
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20150706152954.GA16549@gmail.com \
--to=mingo@kernel.org \
--cc=a.p.zijlstra@chello.nl \
--cc=acme@infradead.org \
--cc=akpm@linux-foundation.org \
--cc=linux-kernel@vger.kernel.org \
--cc=tglx@linutronix.de \
--cc=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).