Re: [PATCH] uprobes: teach build_probe_list() to consider the range
* Oleg Nesterov [2012-07-09 15:35:10]: > Currently build_probe_list() builds the list of all uprobes attached > to the given inode, and the caller should filter out those who don't > fall into the [start,end) range, this is sub-optimal. > > This patch turns find_least_offset_node() into find_node_in_range() > which returns the first node inside the [min,max] range, and changes > build_probe_list() to use this node as a starting point for rb_prev() > and rb_next() to find all other nodes the caller needs. The resulting > list is no longer sorted but we do not care. > > This can speed up both build_probe_list() and the callers, but there > is another reason to introduce find_node_in_range(). It can be used > to figure out whether the given vma has uprobes or not, this will be > needed soon. > > While at it, shift INIT_LIST_HEAD(tmp_list) into build_probe_list(). > > Signed-off-by: Oleg Nesterov Acked-by: Srikar Dronamraju -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH] uprobes: teach build_probe_list() to consider the range
* Oleg Nesterov o...@redhat.com [2012-07-09 15:35:10]: Currently build_probe_list() builds the list of all uprobes attached to the given inode, and the caller should filter out those who don't fall into the [start,end) range, this is sub-optimal. This patch turns find_least_offset_node() into find_node_in_range() which returns the first node inside the [min,max] range, and changes build_probe_list() to use this node as a starting point for rb_prev() and rb_next() to find all other nodes the caller needs. The resulting list is no longer sorted but we do not care. This can speed up both build_probe_list() and the callers, but there is another reason to introduce find_node_in_range(). It can be used to figure out whether the given vma has uprobes or not, this will be needed soon. While at it, shift INIT_LIST_HEAD(tmp_list) into build_probe_list(). Signed-off-by: Oleg Nesterov o...@redhat.com Acked-by: Srikar Dronamraju sri...@linux.vnet.ibm.com -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH] uprobes: teach build_probe_list() to consider the range
On 07/09, Oleg Nesterov wrote:
>
> Currently build_probe_list() builds the list of all uprobes attached
> to the given inode, and the caller should filter out those who don't
> fall into the [start,end) range, this is sub-optimal.
>
> This patch turns find_least_offset_node() into find_node_in_range()
> which returns the first node inside the [min,max] range, and changes
> build_probe_list() to use this node as a starting point for rb_prev()
> and rb_next() to find all other nodes the caller needs. The resulting
> list is no longer sorted but we do not care.
>
> This can speed up both build_probe_list() and the callers, but there
> is another reason to introduce find_node_in_range(). It can be used
> to figure out whether the given vma has uprobes or not, this will be
> needed soon.
I guess it is not easy to read this patch without applying, I am sending
the code to simplify the review.
--
static struct rb_node *
find_node_in_range(struct inode *inode, loff_t min, loff_t max)
{
struct rb_node *n = uprobes_tree.rb_node;
while (n) {
struct uprobe *u = rb_entry(n, struct uprobe, rb_node);
if (inode < u->inode) {
n = n->rb_left;
} else if (inode > u->inode) {
n = n->rb_right;
} else {
if (max < u->offset)
n = n->rb_left;
else if (min > u->offset)
n = n->rb_right;
else
break;
}
}
return n;
}
/*
* For a given range in vma, build a list of probes that need to be inserted.
*/
static void build_probe_list(struct inode *inode,
struct vm_area_struct *vma,
unsigned long start, unsigned long end,
struct list_head *head)
{
loff_t min, max;
unsigned long flags;
struct rb_node *n, *t;
struct uprobe *u;
INIT_LIST_HEAD(head);
min = ((loff_t)vma->vm_pgoff << PAGE_SHIFT) + start - vma->vm_start;
max = min + (end - start) - 1;
spin_lock_irqsave(_treelock, flags);
n = find_node_in_range(inode, min, max);
if (n) {
for (t = n; t; t = rb_prev(t)) {
u = rb_entry(t, struct uprobe, rb_node);
if (u->inode != inode || u->offset < min)
break;
list_add(>pending_list, head);
atomic_inc(>ref);
}
for (t = n; (t = rb_next(t)); ) {
u = rb_entry(t, struct uprobe, rb_node);
if (u->inode != inode || u->offset > max)
break;
list_add(>pending_list, head);
atomic_inc(>ref);
}
}
spin_unlock_irqrestore(_treelock, flags);
}
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[PATCH] uprobes: teach build_probe_list() to consider the range
Currently build_probe_list() builds the list of all uprobes attached
to the given inode, and the caller should filter out those who don't
fall into the [start,end) range, this is sub-optimal.
This patch turns find_least_offset_node() into find_node_in_range()
which returns the first node inside the [min,max] range, and changes
build_probe_list() to use this node as a starting point for rb_prev()
and rb_next() to find all other nodes the caller needs. The resulting
list is no longer sorted but we do not care.
This can speed up both build_probe_list() and the callers, but there
is another reason to introduce find_node_in_range(). It can be used
to figure out whether the given vma has uprobes or not, this will be
needed soon.
While at it, shift INIT_LIST_HEAD(tmp_list) into build_probe_list().
Signed-off-by: Oleg Nesterov
---
kernel/events/uprobes.c | 103 +++
1 files changed, 50 insertions(+), 53 deletions(-)
diff --git a/kernel/events/uprobes.c b/kernel/events/uprobes.c
index 6194edb..c825404 100644
--- a/kernel/events/uprobes.c
+++ b/kernel/events/uprobes.c
@@ -939,59 +939,66 @@ void uprobe_unregister(struct inode *inode, loff_t
offset, struct uprobe_consume
put_uprobe(uprobe);
}
-/*
- * Of all the nodes that correspond to the given inode, return the node
- * with the least offset.
- */
-static struct rb_node *find_least_offset_node(struct inode *inode)
+static struct rb_node *
+find_node_in_range(struct inode *inode, loff_t min, loff_t max)
{
- struct uprobe u = { .inode = inode, .offset = 0};
struct rb_node *n = uprobes_tree.rb_node;
- struct rb_node *close_node = NULL;
- struct uprobe *uprobe;
- int match;
while (n) {
- uprobe = rb_entry(n, struct uprobe, rb_node);
- match = match_uprobe(, uprobe);
-
- if (uprobe->inode == inode)
- close_node = n;
+ struct uprobe *u = rb_entry(n, struct uprobe, rb_node);
- if (!match)
- return close_node;
-
- if (match < 0)
+ if (inode < u->inode) {
n = n->rb_left;
- else
+ } else if (inode > u->inode) {
n = n->rb_right;
+ } else {
+ if (max < u->offset)
+ n = n->rb_left;
+ else if (min > u->offset)
+ n = n->rb_right;
+ else
+ break;
+ }
}
- return close_node;
+ return n;
}
/*
- * For a given inode, build a list of probes that need to be inserted.
+ * For a given range in vma, build a list of probes that need to be inserted.
*/
-static void build_probe_list(struct inode *inode, struct list_head *head)
+static void build_probe_list(struct inode *inode,
+ struct vm_area_struct *vma,
+ unsigned long start, unsigned long end,
+ struct list_head *head)
{
- struct uprobe *uprobe;
+ loff_t min, max;
unsigned long flags;
- struct rb_node *n;
-
- spin_lock_irqsave(_treelock, flags);
-
- n = find_least_offset_node(inode);
+ struct rb_node *n, *t;
+ struct uprobe *u;
- for (; n; n = rb_next(n)) {
- uprobe = rb_entry(n, struct uprobe, rb_node);
- if (uprobe->inode != inode)
- break;
+ INIT_LIST_HEAD(head);
+ min = ((loff_t)vma->vm_pgoff << PAGE_SHIFT) + start - vma->vm_start;
+ max = min + (end - start) - 1;
- list_add(>pending_list, head);
- atomic_inc(>ref);
+ spin_lock_irqsave(_treelock, flags);
+ n = find_node_in_range(inode, min, max);
+ if (n) {
+ for (t = n; t; t = rb_prev(t)) {
+ u = rb_entry(t, struct uprobe, rb_node);
+ if (u->inode != inode || u->offset < min)
+ break;
+ list_add(>pending_list, head);
+ atomic_inc(>ref);
+ }
+ for (t = n; (t = rb_next(t)); ) {
+ u = rb_entry(t, struct uprobe, rb_node);
+ if (u->inode != inode || u->offset > max)
+ break;
+ list_add(>pending_list, head);
+ atomic_inc(>ref);
+ }
}
-
spin_unlock_irqrestore(_treelock, flags);
}
@@ -1021,9 +1028,8 @@ int uprobe_mmap(struct vm_area_struct *vma)
if (!inode)
return 0;
- INIT_LIST_HEAD(_list);
mutex_lock(uprobes_mmap_hash(inode));
- build_probe_list(inode, _list);
+ build_probe_list(inode, vma, vma->vm_start, vma->vm_end, _list);
ret
[PATCH] uprobes: teach build_probe_list() to consider the range
Currently build_probe_list() builds the list of all uprobes attached
to the given inode, and the caller should filter out those who don't
fall into the [start,end) range, this is sub-optimal.
This patch turns find_least_offset_node() into find_node_in_range()
which returns the first node inside the [min,max] range, and changes
build_probe_list() to use this node as a starting point for rb_prev()
and rb_next() to find all other nodes the caller needs. The resulting
list is no longer sorted but we do not care.
This can speed up both build_probe_list() and the callers, but there
is another reason to introduce find_node_in_range(). It can be used
to figure out whether the given vma has uprobes or not, this will be
needed soon.
While at it, shift INIT_LIST_HEAD(tmp_list) into build_probe_list().
Signed-off-by: Oleg Nesterov o...@redhat.com
---
kernel/events/uprobes.c | 103 +++
1 files changed, 50 insertions(+), 53 deletions(-)
diff --git a/kernel/events/uprobes.c b/kernel/events/uprobes.c
index 6194edb..c825404 100644
--- a/kernel/events/uprobes.c
+++ b/kernel/events/uprobes.c
@@ -939,59 +939,66 @@ void uprobe_unregister(struct inode *inode, loff_t
offset, struct uprobe_consume
put_uprobe(uprobe);
}
-/*
- * Of all the nodes that correspond to the given inode, return the node
- * with the least offset.
- */
-static struct rb_node *find_least_offset_node(struct inode *inode)
+static struct rb_node *
+find_node_in_range(struct inode *inode, loff_t min, loff_t max)
{
- struct uprobe u = { .inode = inode, .offset = 0};
struct rb_node *n = uprobes_tree.rb_node;
- struct rb_node *close_node = NULL;
- struct uprobe *uprobe;
- int match;
while (n) {
- uprobe = rb_entry(n, struct uprobe, rb_node);
- match = match_uprobe(u, uprobe);
-
- if (uprobe-inode == inode)
- close_node = n;
+ struct uprobe *u = rb_entry(n, struct uprobe, rb_node);
- if (!match)
- return close_node;
-
- if (match 0)
+ if (inode u-inode) {
n = n-rb_left;
- else
+ } else if (inode u-inode) {
n = n-rb_right;
+ } else {
+ if (max u-offset)
+ n = n-rb_left;
+ else if (min u-offset)
+ n = n-rb_right;
+ else
+ break;
+ }
}
- return close_node;
+ return n;
}
/*
- * For a given inode, build a list of probes that need to be inserted.
+ * For a given range in vma, build a list of probes that need to be inserted.
*/
-static void build_probe_list(struct inode *inode, struct list_head *head)
+static void build_probe_list(struct inode *inode,
+ struct vm_area_struct *vma,
+ unsigned long start, unsigned long end,
+ struct list_head *head)
{
- struct uprobe *uprobe;
+ loff_t min, max;
unsigned long flags;
- struct rb_node *n;
-
- spin_lock_irqsave(uprobes_treelock, flags);
-
- n = find_least_offset_node(inode);
+ struct rb_node *n, *t;
+ struct uprobe *u;
- for (; n; n = rb_next(n)) {
- uprobe = rb_entry(n, struct uprobe, rb_node);
- if (uprobe-inode != inode)
- break;
+ INIT_LIST_HEAD(head);
+ min = ((loff_t)vma-vm_pgoff PAGE_SHIFT) + start - vma-vm_start;
+ max = min + (end - start) - 1;
- list_add(uprobe-pending_list, head);
- atomic_inc(uprobe-ref);
+ spin_lock_irqsave(uprobes_treelock, flags);
+ n = find_node_in_range(inode, min, max);
+ if (n) {
+ for (t = n; t; t = rb_prev(t)) {
+ u = rb_entry(t, struct uprobe, rb_node);
+ if (u-inode != inode || u-offset min)
+ break;
+ list_add(u-pending_list, head);
+ atomic_inc(u-ref);
+ }
+ for (t = n; (t = rb_next(t)); ) {
+ u = rb_entry(t, struct uprobe, rb_node);
+ if (u-inode != inode || u-offset max)
+ break;
+ list_add(u-pending_list, head);
+ atomic_inc(u-ref);
+ }
}
-
spin_unlock_irqrestore(uprobes_treelock, flags);
}
@@ -1021,9 +1028,8 @@ int uprobe_mmap(struct vm_area_struct *vma)
if (!inode)
return 0;
- INIT_LIST_HEAD(tmp_list);
mutex_lock(uprobes_mmap_hash(inode));
- build_probe_list(inode, tmp_list);
+ build_probe_list(inode, vma, vma-vm_start,
Re: [PATCH] uprobes: teach build_probe_list() to consider the range
On 07/09, Oleg Nesterov wrote:
Currently build_probe_list() builds the list of all uprobes attached
to the given inode, and the caller should filter out those who don't
fall into the [start,end) range, this is sub-optimal.
This patch turns find_least_offset_node() into find_node_in_range()
which returns the first node inside the [min,max] range, and changes
build_probe_list() to use this node as a starting point for rb_prev()
and rb_next() to find all other nodes the caller needs. The resulting
list is no longer sorted but we do not care.
This can speed up both build_probe_list() and the callers, but there
is another reason to introduce find_node_in_range(). It can be used
to figure out whether the given vma has uprobes or not, this will be
needed soon.
I guess it is not easy to read this patch without applying, I am sending
the code to simplify the review.
--
static struct rb_node *
find_node_in_range(struct inode *inode, loff_t min, loff_t max)
{
struct rb_node *n = uprobes_tree.rb_node;
while (n) {
struct uprobe *u = rb_entry(n, struct uprobe, rb_node);
if (inode u-inode) {
n = n-rb_left;
} else if (inode u-inode) {
n = n-rb_right;
} else {
if (max u-offset)
n = n-rb_left;
else if (min u-offset)
n = n-rb_right;
else
break;
}
}
return n;
}
/*
* For a given range in vma, build a list of probes that need to be inserted.
*/
static void build_probe_list(struct inode *inode,
struct vm_area_struct *vma,
unsigned long start, unsigned long end,
struct list_head *head)
{
loff_t min, max;
unsigned long flags;
struct rb_node *n, *t;
struct uprobe *u;
INIT_LIST_HEAD(head);
min = ((loff_t)vma-vm_pgoff PAGE_SHIFT) + start - vma-vm_start;
max = min + (end - start) - 1;
spin_lock_irqsave(uprobes_treelock, flags);
n = find_node_in_range(inode, min, max);
if (n) {
for (t = n; t; t = rb_prev(t)) {
u = rb_entry(t, struct uprobe, rb_node);
if (u-inode != inode || u-offset min)
break;
list_add(u-pending_list, head);
atomic_inc(u-ref);
}
for (t = n; (t = rb_next(t)); ) {
u = rb_entry(t, struct uprobe, rb_node);
if (u-inode != inode || u-offset max)
break;
list_add(u-pending_list, head);
atomic_inc(u-ref);
}
}
spin_unlock_irqrestore(uprobes_treelock, flags);
}
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
