mm/vmalloc: simplify merge_or_add_vmap_area() func.
Subsystems (2)
Uladzislau Rezki (Sony)
maintainerPATCH 1/3 mm/vmalloc: simplify merge_or_add_vmap_area() func.
Currently when a VA is deallocated and is about to be placed back to the tree, it can be either: merged with next/prev neighbors or inserted if not coalesced.
On those steps the tree can be populated several times. For example when both neighbors are merged. It can be avoided and simplified in fact.
Therefore do it only once when VA points to final merged area, after all manipulations: merging/removing/inserting.
--- mm/vmalloc.c | 25 ++++++++++++++----------- 1 file changed, 14 insertions(+), 11 deletions(-)
mm/vmalloc.c +14 -11
@@ -753,9 +753,6 @@ merge_or_add_vmap_area(struct vmap_area *va,if (sibling->va_start == va->va_end) { sibling->va_start = va->va_start; -/* Check and update the tree if needed. */ -augment_tree_propagate_from (sibling); -/* Free vmap_area object. */ kmem_cache_free (vmap_area_cachep, va);
@@ -775,14 +772,18 @@ merge_or_add_vmap_area(struct vmap_area *va,if (next->prev != head) { sibling = list_entry(next->prev, struct vmap_area, list);if (sibling->va_end == va->va_start) { - sibling->va_end = va->va_end; - -/* Check and update the tree if needed. */ -augment_tree_propagate_from (sibling); - +/* +* If both neighbors are coalesced, it is important +* to unlink the "next" node first, followed by merging +* with "previous" one. Otherwise the tree might not be +* fully populated if a sibling's augmented value is +* "normalized" because of rotation operations. +*/ if (merged)unlink_va (va, root); + sibling->va_end = va->va_end; +/* Free vmap_area object. */ kmem_cache_free (vmap_area_cachep, va);
@@ -793,11 +794,13 @@ merge_or_add_vmap_area(struct vmap_area *va, } insert: -if (!merged) { +if (!merged)link_va (va, root, parent, link, head); -augment_tree_propagate_from (va); - } +/* +* Last step is to check and update the tree. +*/ +augment_tree_propagate_from (va);return va; }
Signature · 1 line
2.20.1
Uladzislau Rezki (Sony)
maintainerPATCH 2/3 mm/vmalloc: simplify augment_tree_propagate_check() func.
This function is for debug purpose only. Currently it uses recursion for tree traversal, checking an augmented value of each node to find out if it is valid or not.
The recursion can corrupt the stack because the tree can be huge if synthetic tests are applied. To prevent it, navigate the tree from bottom to upper levels using a regular list instead, because nodes are linked among each other also. It is faster and without recursion.
--- mm/vmalloc.c | 42 ++++++++---------------------------------- 1 file changed, 8 insertions(+), 34 deletions(-)
mm/vmalloc.c +8 -34
@@ -589,43 +589,17 @@ unlink_va(struct vmap_area *va, struct rb_root *root)#if DEBUG_AUGMENT_PROPAGATE_CHECK static void -augment_tree_propagate_check (struct rb_node *n) +augment_tree_propagate_check (void ) {struct vmap_area *va; -struct rb_node *node; -unsigned long size; -bool found = false; - -if (n ==NULL ) -return ; - - va = rb_entry(n, struct vmap_area, rb_node); - size = va->subtree_max_size; - node = n; - -while (node) { - va = rb_entry(node, struct vmap_area, rb_node); - -if (get_subtree_max_size (node->rb_left) == size) { - node = node->rb_left; - }else { -if (va_size (va) == size) { - found = true; -break ; - } +unsigned long computed_size; - node = node->rb_right; - } - } - -if (!found) { - va = rb_entry(n, struct vmap_area, rb_node); -pr_emerg ("tree is corrupted: %lu, %lu\n" , -va_size (va), va->subtree_max_size); +list_for_each_entry (va, &free_vmap_area_list, list) { + computed_size =compute_subtree_max_size (va); +if (computed_size != va->subtree_max_size) +pr_emerg ("tree is corrupted: %lu, %lu\n" , +va_size (va), va->subtree_max_size); } - -augment_tree_propagate_check (n->rb_left); -augment_tree_propagate_check (n->rb_right); }#endif
@@ -680,7 +654,7 @@ augment_tree_propagate_from(struct vmap_area *va) }#if DEBUG_AUGMENT_PROPAGATE_CHECK -augment_tree_propagate_check (free_vmap_area_root.rb_node); +augment_tree_propagate_check ();#endif }
Signature · 1 line
2.20.1
Uladzislau Rezki (Sony)
maintainerPATCH 3/3 mm/vmalloc: switch to "propagate()" callback
In reply to Uladzislau Rezki (Sony)An augment_tree_propagate_from() function uses its own implementation that populates a tree from the specified node toward a root node.
From the other hand the RB_DECLARE_CALLBACKS_MAX macro provides the "propagate()" callback that does exactly the same. Having two similar functions does not make sense and is redundant.
Reuse "built in" functionality to the macros. So the code size gets reduced.
--- mm/vmalloc.c | 25 ++++++------------------- 1 file changed, 6 insertions(+), 19 deletions(-)
mm/vmalloc.c +6 -19
@@ -633,25 +633,12 @@ augment_tree_propagate_check(void) static __always_inline voidaugment_tree_propagate_from (struct vmap_area *va) { -struct rb_node *node = &va->rb_node; -unsigned long new_va_sub_max_size; - -while (node) { - va = rb_entry(node, struct vmap_area, rb_node); - new_va_sub_max_size =compute_subtree_max_size (va); - -/* -* If the newly calculated maximum available size of the -* subtree is equal to the current one, then it means that -* the tree is propagated correctly. So we have to stop at -* this point to save cycles. -*/ -if (va->subtree_max_size == new_va_sub_max_size) -break ; - - va->subtree_max_size = new_va_sub_max_size; - node =rb_parent (&va->rb_node); - } +/* +* Populate the tree from bottom towards the root until +* the calculated maximum available size of checked node +* is equal to its current one. +*/ +free_vmap_area_rb_augment_cb_propagate (&va->rb_node,NULL );#if DEBUG_AUGMENT_PROPAGATE_CHECK augment_tree_propagate_check ();
Signature · 1 line
2.20.1