mm/vmalloc.c: correct a few logic error for __insert_vmap_area()

PATCH Superseded zijun_hu 2 participants 9 messages Sep 21, 2016 – Sep 27, 2016

Subsystems (2)

Memory management vmalloc

lore

Share & tools

lore

zijun_hu

author

2016-09-21 04:24 UTC #0 lore raw

PATCH 1/5 mm/vmalloc.c: correct a few logic error for __insert_vmap_area()

From: zijun_hu <[email protected]>

correct a few logic error for __insert_vmap_area() since the else if condition is always true and meaningless

in order to fix this issue, if vmap_area inserted is lower than one on rbtree then walk around left branch; if higher then right branch otherwise intersects with the other then BUG_ON() is triggered

Signed-off-by zijun_hu <[email protected]>

---
 mm/vmalloc.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

mm/vmalloc.c +4 -4

index 91f44e7..cc6ecd6 100644
@@ -321,10 +321,10 @@ static void __insert_vmap_area(struct vmap_area *va)
 
 		parent = *p;
 		tmp_va = rb_entry(parent, struct vmap_area, rb_node);
-		if (va->va_start < tmp_va->va_end)
-			p = &(*p)->rb_left;
-		else if (va->va_end > tmp_va->va_start)
-			p = &(*p)->rb_right;
+		if (va->va_end <= tmp_va->va_start)
+			p = &parent->rb_left;
+		else if (va->va_start >= tmp_va->va_end)
+			p = &parent->rb_right;
 		else
 			BUG();
 	}

Signature · 1 line

1.9.1

David Rientjes

2016-09-21 21:10 UTC #1 lore raw

Quoted 9 lines · zijun_hu

From: zijun_hu <[email protected]>
correct a few logic error for __insert_vmap_area() since the else if condition is always true and meaningless
in order to fix this issue, if vmap_area inserted is lower than one on rbtree then walk around left branch; if higher then right branch otherwise intersects with the other then BUG_ON() is triggered

Under normal operation, you're right that the "else if" conditional should always succeed: we don't want to BUG() unless there's a bug. The original code can catch instances when va->va_start == tmp_va->va_end where we should BUG(). Your code silently ignores it.

zijun_hu

author

2016-09-21 22:35 UTC #2 lore raw

Quoted 12 lines · David Rientjes

Quoted 9 lines · zijun_hu
From: zijun_hu <[email protected]>
correct a few logic error for __insert_vmap_area() since the else if condition is always true and meaningless
in order to fix this issue, if vmap_area inserted is lower than one on rbtree then walk around left branch; if higher then right branch otherwise intersects with the other then BUG_ON() is triggered

Quoted 5 lines

Under normal operation, you're right that the "else if" conditional should always succeed: we don't want to BUG() unless there's a bug. The original code can catch instances when va->va_start == tmp_va->va_end where we should BUG(). Your code silently ignores it.

Hmm, the BUG_ON() appears in the original code, i don't introduce it. it maybe be better to consider va->va_start == tmp_va->va_end as normal case and should not BUG_ON() it since the available range of vmap_erea include the start boundary but the end, BTW, represented as [start, end)

this patch correct the logic to that mentioned in the comments, it maybe be more logical and more understandable

David Rientjes

2016-09-21 22:45 UTC #3 lore raw

Quoted 13 lines · zijun_hu

Quoted 8 lines
Quoted 7 lines
correct a few logic error for __insert_vmap_area() since the else if condition is always true and meaningless
in order to fix this issue, if vmap_area inserted is lower than one on rbtree then walk around left branch; if higher then right branch otherwise intersects with the other then BUG_ON() is triggered
Quoted 5 lines
Under normal operation, you're right that the "else if" conditional should always succeed: we don't want to BUG() unless there's a bug. The original code can catch instances when va->va_start == tmp_va->va_end where we should BUG(). Your code silently ignores it.

Quoted 5 lines

Hmm, the BUG_ON() appears in the original code, i don't introduce it. it maybe be better to consider va->va_start == tmp_va->va_end as normal case and should not BUG_ON() it since the available range of vmap_erea include the start boundary but the end, BTW, represented as [start, end)

We don't support inserting when va->va_start == tmp_va->va_end, plain and simple. There's no reason to do so. NACK to the patch.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

zijun_hu

author

2016-09-21 23:10 UTC #4 lore raw

Quoted 15 lines · David Rientjes

Quoted 13 lines · zijun_hu
Quoted 13 lines
Quoted 7 lines
correct a few logic error for __insert_vmap_area() since the else if condition is always true and meaningless
in order to fix this issue, if vmap_area inserted is lower than one on rbtree then walk around left branch; if higher then right branch otherwise intersects with the other then BUG_ON() is triggered
Under normal operation, you're right that the "else if" conditional should always succeed: we don't want to BUG() unless there's a bug. The original code can catch instances when va->va_start == tmp_va->va_end where we should BUG(). Your code silently ignores it.

Quoted 9 lines

Quoted 5 lines
Hmm, the BUG_ON() appears in the original code, i don't introduce it. it maybe be better to consider va->va_start == tmp_va->va_end as normal case and should not BUG_ON() it since the available range of vmap_erea include the start boundary but the end, BTW, represented as [start, end)
We don't support inserting when va->va_start == tmp_va->va_end, plain and simple. There's no reason to do so. NACK to the patch.

i am sorry i disagree with you because
1) in almost all context of vmalloc, original logic treat the special case as normal for example, __find_vmap_area() or alloc_vmap_area()
2) don't use the limited vmap area effectively, it maybe causes BUG_ON() easy
3) consider below case
it provided there have been two vmap_areas [4, 12) and [20, 28), what will happens when alloc_vmap_area(8, 4, 6, 24,...)? should we use [12,20) for our request?

David Rientjes

2016-09-21 23:15 UTC #5 lore raw

Quoted 6 lines · zijun_hu

Quoted 3 lines
We don't support inserting when va->va_start == tmp_va->va_end, plain and simple. There's no reason to do so. NACK to the patch.
i am sorry i disagree with you because
1) in almost all context of vmalloc, original logic treat the special case as normal for example, __find_vmap_area() or alloc_vmap_area()

The ranges are [start, end) like everywhere else. __find_vmap_area() is implemented as such for the passed address. The address is aligned in alloc_vmap_area(), there's no surprise here. The logic is correct in __insert_vmap_area().

zijun_hu

author

2016-09-21 23:55 UTC #6 lore raw

Quoted 5 lines · David Rientjes

Quoted 3 lines · zijun_hu
Quoted 3 lines
We don't support inserting when va->va_start == tmp_va->va_end, plain and simple. There's no reason to do so. NACK to the patch.

Quoted 9 lines

Quoted 3 lines
i am sorry i disagree with you because
1) in almost all context of vmalloc, original logic treat the special case as normal for example, __find_vmap_area() or alloc_vmap_area()
The ranges are [start, end) like everywhere else. __find_vmap_area() is implemented as such for the passed address. The address is aligned in alloc_vmap_area(), there's no surprise here. The logic is correct in __insert_vmap_area().

1) is the desire behavior of __insert_vmap_area() conform with that mentioned in my comments?
2) which way of code implementation can present the desire purpose more clear and more understandable?

zijun_hu

author

2016-09-27 06:07 UTC #7 lore raw

In reply to David Rientjes

Quoted 5 lines · David Rientjes

Quoted 3 lines · zijun_hu
Quoted 3 lines
We don't support inserting when va->va_start == tmp_va->va_end, plain and simple. There's no reason to do so. NACK to the patch.

Quoted 9 lines

Quoted 3 lines
i am sorry i disagree with you because
1) in almost all context of vmalloc, original logic treat the special case as normal for example, __find_vmap_area() or alloc_vmap_area()
The ranges are [start, end) like everywhere else. __find_vmap_area() is implemented as such for the passed address. The address is aligned in alloc_vmap_area(), there's no surprise here. The logic is correct in __insert_vmap_area().

i am sorry to disagree with you
i will resend this patch with more detailed illustration

zijun_hu

author

2016-09-22 01:36 UTC #8 lore raw

In reply to zijun_hu

Quoted 10 lines · zijun_hu

From: zijun_hu <[email protected]>
correct a few logic error for __insert_vmap_area() since the else if condition is always true and meaningless
in order to fix this issue, if vmap_area inserted is lower than one on rbtree then walk around left branch; if higher then right branch otherwise intersects with the other then BUG_ON() is triggered
Signed-off-by zijun_hu <[email protected]>

i give more explanation to the intent of my change any comments is welcome

Quoted 9 lines

---
 mm/vmalloc.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

mm/vmalloc.c +0 -0

index 91f44e7..cc6ecd6 100644

mm/vmalloc.c static void __insert_vmap_area(struct vmap_area *va) · line 327

Quoted 7 lines

mm/vmalloc.c +0 -4

@@ -321,10 +321,10 @@ static void __insert_vmap_area(struct vmap_area *va)
 
 		parent = *p;
 		tmp_va = rb_entry(parent, struct vmap_area, rb_node);
-		if (va->va_start < tmp_va->va_end)
-			p = &(*p)->rb_left;
-		else if (va->va_end > tmp_va->va_start)
-			p = &(*p)->rb_right;

this else if condition is always true and meaningless as long as there are no zero sized vamp_area due to the following expression
va->va_end > va->va_start >= tmp_va->va_end > tmp_va->va_start

mm/vmalloc.c static void __insert_vmap_area(struct vmap_area *va) · line 325

Quoted 2 lines

mm/vmalloc.c +2 -0

+		if (va->va_end <= tmp_va->va_start)
+			p = &parent->rb_left;

if the vamp_area to be inserted is lower than that on the rbtree then we walk around the left branch of the node given
consider va->va_end == tmp_va->va_start as legal case which represent two neighbor areas tightly
BTW, the available range of a vmap area include the start boundary not the end, namely, [start, end)

mm/vmalloc.c static void __insert_vmap_area(struct vmap_area *va) · line 327

Quoted 2 lines

mm/vmalloc.c +2 -0

+		else if (va->va_start >= tmp_va->va_end)
+			p = &parent->rb_right;

if the vamp_area to be inserted is higher than that on the rbtree then we walk around the right branch of the node given

mm/vmalloc.c static void __insert_vmap_area(struct vmap_area *va) · line 329

Quoted 2 lines

mm/vmalloc.c +0 -0

 		else
 			BUG();

this indicate the vamp_area to be inserted have intersects with that on the rbtree then we remain the BUG() logic

Quoted 2 lines

mm/vmalloc.c +0 -0
 	}