x86,mm/pat: Move towards using generic interval tree
v3 cover x86,mm/pat: Move towards using generic interval tree
Changes from v2:
- Removed unnecessary goto error path in patch 1, per tglx.
- Added the corresponding Makefile change for patch 4, per mingo.
- Added tglx's review tags.
Changes from v1[0]:
- Got rid of more code in patch 1 by using the end - 1 for closed intervals, instead of keeping the overlap-check.
- added an additional cleanup patch.
Hi,
I'm sending this series again in this format as the interval tree node conversion will, at a minimum, take longer than hoped for (ie: Jason still removing interval tree users for the mmu_notifier rework[1]). There is also a chance this will never see be done.
As such, I'm resending this series (where patch 1 is the only interesting one and which Ingo acked previously, with the exception that the nodes remain fully closed). In the future, it would be trivial to port pat tree to semi open nodes, but for now think that it makes sense to just get the pat changes in.
Please consider for v5.5. Thanks!
[0] https://lore.kernel.org/lkml/[email protected]/
[1] https://marc.info/?l=linux-mm&m=157116340411211
Davidlohr Bueso (4):
x86/mm, pat: Convert pat tree to generic interval tree x86/mm, pat: Cleanup some of the local memtype_rb_* calls x86/mm, pat: Drop rbt prefix from external memtype calls x86/mm, pat: Rename pat_rbtree.c to pat_interval.c
arch/x86/mm/Makefile | 2 +- arch/x86/mm/pat.c | 8 +- arch/x86/mm/pat_internal.h | 20 ++-- arch/x86/mm/pat_interval.c | 185 +++++++++++++++++++++++++++++++ arch/x86/mm/pat_rbtree.c | 268 --------------------------------------------- 5 files changed, 200 insertions(+), 283 deletions(-) create mode 100644 arch/x86/mm/pat_interval.c delete mode 100644 arch/x86/mm/pat_rbtree.c
Signature · 1 line
2.16.4
PATCH v3 1/4 x86/mm, pat: Convert pat tree to generic interval tree
With some considerations, the custom pat_rbtree implementation can be simplified to use most of the generic interval_tree machinery.
o The tree inorder traversal can slightly differ when there are key ('start') collisions in the tree due to one going left and another right. This, however, only affects the output of debugfs' pat_memtype_list file.
o Generic interval trees are now fully closed [a, b], for which we need to adjust the last endpoint (ie: end - 1).
o Erasing logic must remain untouched as well.
In order for the types to remain u64, the 'memtype_interval' calls are introduced, as opposed to simply using struct interval_tree.
In addition, pat tree might potentially also benefit by the fast overlap detection for the insertion case when looking up the first overlapping node in the tree.
Finally, I've tested this on various servers, via sanity warnings, running side by side with the current version and so far see no differences in the returned pointer node when doing memtype_rb_lowest_match() lookups.
--- arch/x86/mm/pat_rbtree.c | 162 ++++++++++++----------------------------------- 1 file changed, 42 insertions(+), 120 deletions(-)
arch/x86/mm/pat_rbtree.c +42 -120
@@ -5,14 +5,13 @@* Authors: Venkatesh Pallipadi <[email protected]> * Suresh B Siddha <[email protected]> * -* Interval tree (augmented rbtree) used to store the PAT memory type -* reservations. +* Interval tree used to store the PAT memory type reservations. */ #include <linux/seq_file.h> #include <linux/debugfs.h> #include <linux/kernel.h> -#include <linux/rbtree_augmented.h> +#include <linux/interval_tree_generic.h> #include <linux/sched.h> #include <linux/gfp.h>
@@ -33,72 +32,33 @@* * memtype_lock protects the rbtree. */ - -static struct rb_root memtype_rbroot =RB_ROOT ; - -static int is_node_overlap (struct memtype *node,u64 start,u64 end) +static inline u64 memtype_interval_start (struct memtype *memtype) { -if (node->start >= end || node->end <= start) -return 0 ; - -return 1 ; +return memtype->start; } -static u64 get_subtree_max_end (struct rb_node *node) +static inline u64 memtype_interval_end (struct memtype *memtype) { -u64 ret =0 ; -if (node) { - struct memtype *data = rb_entry(node, struct memtype, rb); - ret = data->subtree_max_end; - } -return ret; +return memtype->end -1 ; } +INTERVAL_TREE_DEFINE(struct memtype, rb, u64, subtree_max_end, + memtype_interval_start, memtype_interval_end, + static, memtype_interval) -#define NODE_END (node) ((node)->end) - -RB_DECLARE_CALLBACKS_MAX (static, memtype_rb_augment_cb, - struct memtype, rb, u64, subtree_max_end, NODE_END) - -/* Find the first (lowest start addr) overlapping range from rb tree */ -static struct memtype *memtype_rb_lowest_match (struct rb_root *root, -u64 start,u64 end) -{ -struct rb_node *node = root->rb_node; -struct memtype *last_lower =NULL ; - -while (node) { - struct memtype *data = rb_entry(node, struct memtype, rb); - -if (get_subtree_max_end (node->rb_left) > start) { -/* Lowest overlap if any must be on left side */ - node = node->rb_left; - }else if (is_node_overlap (data, start, end)) { - last_lower = data; -break ; - }else if (start >= data->start) { -/* Lowest overlap if any must be on right side */ - node = node->rb_right; - }else { -break ; - } - } -return last_lower;/* Returns NULL if there is no overlap */ -} +static struct rb_root_cached memtype_rbroot =RB_ROOT_CACHED ;enum {MEMTYPE_EXACT_MATCH =0 ,MEMTYPE_END_MATCH =1 }; -static struct memtype *memtype_rb_match (struct rb_root *root, -u64 start,u64 end,int match_type) +static struct memtype *memtype_match (struct rb_root_cached *root, +u64 start,u64 end,int match_type) {struct memtype *match; - match =memtype_rb_lowest_match (root, start, end); + match =memtype_interval_iter_first (root, start, end);while (match !=NULL && match->start < end) { -struct rb_node *node; -if ((match_type ==MEMTYPE_EXACT_MATCH ) && (match->start == start) && (match->end == end))return match;
@@ -107,26 +67,21 @@ static struct memtype *memtype_rb_match(struct rb_root *root, (match->start < start) && (match->end == end))return match; - node =rb_next (&match->rb); -if (node) - match = rb_entry(node, struct memtype, rb); -else - match =NULL ; + match =memtype_interval_iter_next (match, start, end); }return NULL ;/* Returns NULL if there is no match */ } -static int memtype_rb_check_conflict (struct rb_root *root, +static int memtype_rb_check_conflict (struct rb_root_cached *root,u64 start,u64 end,enum page_cache_mode reqtype,enum page_cache_mode *newtype) { -struct rb_node *node;struct memtype *match;enum page_cache_mode found_type = reqtype; - match =memtype_rb_lowest_match (&memtype_rbroot, start, end); + match =memtype_interval_iter_first (&memtype_rbroot, start, end);if (match ==NULL ) goto success;
@@ -136,19 +91,12 @@ static int memtype_rb_check_conflict(struct rb_root *root,dprintk ("Overlap at 0x%Lx-0x%Lx\n" , match->start, match->end); found_type = match->type; - node =rb_next (&match->rb); -while (node) { - match = rb_entry(node, struct memtype, rb); - -if (match->start >= end)/* Checked all possible matches */ - goto success; - -if (is_node_overlap (match, start, end) && - match->type != found_type) { + match =memtype_interval_iter_next (match, start, end); +while (match) { +if (match->type != found_type) goto failure; - } - node =rb_next (&match->rb); + match =memtype_interval_iter_next (match, start, end); } success:if (newtype)
@@ -163,44 +111,21 @@ static int memtype_rb_check_conflict(struct rb_root *root,return -EBUSY ; } -static void memtype_rb_insert (struct rb_root *root,struct memtype *newdata) -{ -struct rb_node **node = &(root->rb_node); -struct rb_node *parent =NULL ; - -while (*node) { - struct memtype *data = rb_entry(*node, struct memtype, rb); - - parent = *node; -if (data->subtree_max_end < newdata->end) - data->subtree_max_end = newdata->end; -if (newdata->start <= data->start) - node = &((*node)->rb_left); -else if (newdata->start > data->start) - node = &((*node)->rb_right); - } - - newdata->subtree_max_end = newdata->end; -rb_link_node (&newdata->rb, parent, node); -rb_insert_augmented (&newdata->rb, root, &memtype_rb_augment_cb); -} -int rbt_memtype_check_insert (struct memtype *new,enum page_cache_mode *ret_type) {int err =0 ; err =memtype_rb_check_conflict (&memtype_rbroot, new->start, new->end, - new->type, ret_type); + new->type, ret_type); +if (err) +return err; -if (!err) { -if (ret_type) - new->type = *ret_type; +if (ret_type) + new->type = *ret_type; - new->subtree_max_end = new->end; -memtype_rb_insert (&memtype_rbroot, new); - } -return err; +memtype_interval_insert (new, &memtype_rbroot); +return 0 ; }struct memtype *rbt_memtype_erase (u64 start,u64 end)
@@ -214,26 +139,23 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)* it then checks with END_MATCH, i.e. shrink the size of a node * from the end for the mremap case. */ - data =memtype_rb_match (&memtype_rbroot, start, end, -MEMTYPE_EXACT_MATCH ); + data =memtype_match (&memtype_rbroot, start, end, +MEMTYPE_EXACT_MATCH );if (!data) { - data =memtype_rb_match (&memtype_rbroot, start, end, -MEMTYPE_END_MATCH ); + data =memtype_match (&memtype_rbroot, start, end, +MEMTYPE_END_MATCH );if (!data)return ERR_PTR (-EINVAL ); }if (data->start == start) {/* munmap: erase this node */ -rb_erase_augmented (&data->rb, &memtype_rbroot, - &memtype_rb_augment_cb); +memtype_interval_remove (data, &memtype_rbroot); }else {/* mremap: update the end value of this node */ -rb_erase_augmented (&data->rb, &memtype_rbroot, - &memtype_rb_augment_cb); +memtype_interval_remove (data, &memtype_rbroot); data->end = start; - data->subtree_max_end = data->end; -memtype_rb_insert (&memtype_rbroot, data); +memtype_interval_insert (data, &memtype_rbroot);return NULL ; }
@@ -242,24 +164,24 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)struct memtype *rbt_memtype_lookup (u64 addr) { -return memtype_rb_lowest_match (&memtype_rbroot, addr, addr +PAGE_SIZE ); +return memtype_interval_iter_first (&memtype_rbroot, addr, + addr +PAGE_SIZE ); }#if defined(CONFIG_DEBUG_FS )int rbt_memtype_copy_nth_element (struct memtype *out,loff_t pos) { -struct rb_node *node; +struct memtype *match;int i =1 ; - node =rb_first (&memtype_rbroot); -while (node && pos != i) { - node =rb_next (node); + match =memtype_interval_iter_first (&memtype_rbroot,0 ,ULONG_MAX ); +while (match && pos != i) { + match =memtype_interval_iter_next (match,0 ,ULONG_MAX ); i++; } -if (node) {/* pos == i */ - struct memtype *this = rb_entry(node, struct memtype, rb); - *out = *this; +if (match) {/* pos == i */ + *out = *match;return 0 ; }else {return 1 ;
Signature · 1 line
2.16.4
[tip: x86/mm] x86/mm/pat: Convert the PAT tree to a generic interval tree
The following commit has been merged into the x86/mm branch of tip:
The following commit has been merged into the x86/mm branch of tip:
Commit-ID: 2418ac70a9c1f083cb7919fd20c050e2a41c2d1e Gitweb: https://git.kernel.org/tip/2418ac70a9c1f083cb7919fd20c050e2a41c2d1e Author: Davidlohr Bueso <[email protected]> AuthorDate: Wed, 20 Nov 2019 17:15:58 -08:00 Committer: Ingo Molnar <[email protected]> CommitterDate: Thu, 21 Nov 2019 17:37:30 +01:00
x86/mm/pat: Convert the PAT tree to a generic interval tree
With some considerations, the custom pat_rbtree implementation can be simplified to use most of the generic interval_tree machinery:
- The tree inorder traversal can slightly differ when there are key ('start') collisions in the tree due to one going left and another right. This, however, only affects the output of debugfs' pat_memtype_list file.
- Generic interval trees are now fully closed [a, b], for which we need to adjust the last endpoint (ie: end - 1).
- Erasing logic must remain untouched as well.
- In order for the types to remain u64, the 'memtype_interval' calls are introduced, as opposed to simply using struct interval_tree.
In addition, the PAT tree might potentially also benefit by the fast overlap detection for the insertion case when looking up the first overlapping node in the tree.
No change in behavior is intended.
Finally, I've tested this on various servers, via sanity warnings, running side by side with the current version and so far see no differences in the returned pointer node when doing memtype_rb_lowest_match() lookups.
--- arch/x86/mm/pat_rbtree.c | 162 +++++++++----------------------------- 1 file changed, 42 insertions(+), 120 deletions(-)
arch/x86/mm/pat_rbtree.c +42 -120
@@ -5,14 +5,13 @@* Authors: Venkatesh Pallipadi <[email protected]> * Suresh B Siddha <[email protected]> * -* Interval tree (augmented rbtree) used to store the PAT memory type -* reservations. +* Interval tree used to store the PAT memory type reservations. */ #include <linux/seq_file.h> #include <linux/debugfs.h> #include <linux/kernel.h> -#include <linux/rbtree_augmented.h> +#include <linux/interval_tree_generic.h> #include <linux/sched.h> #include <linux/gfp.h>
@@ -33,72 +32,33 @@* * memtype_lock protects the rbtree. */ - -static struct rb_root memtype_rbroot =RB_ROOT ; - -static int is_node_overlap (struct memtype *node,u64 start,u64 end) +static inline u64 memtype_interval_start (struct memtype *memtype) { -if (node->start >= end || node->end <= start) -return 0 ; - -return 1 ; +return memtype->start; } -static u64 get_subtree_max_end (struct rb_node *node) +static inline u64 memtype_interval_end (struct memtype *memtype) { -u64 ret =0 ; -if (node) { - struct memtype *data = rb_entry(node, struct memtype, rb); - ret = data->subtree_max_end; - } -return ret; +return memtype->end -1 ; } +INTERVAL_TREE_DEFINE(struct memtype, rb, u64, subtree_max_end, + memtype_interval_start, memtype_interval_end, + static, memtype_interval) -#define NODE_END (node) ((node)->end) - -RB_DECLARE_CALLBACKS_MAX (static, memtype_rb_augment_cb, - struct memtype, rb, u64, subtree_max_end, NODE_END) - -/* Find the first (lowest start addr) overlapping range from rb tree */ -static struct memtype *memtype_rb_lowest_match (struct rb_root *root, -u64 start,u64 end) -{ -struct rb_node *node = root->rb_node; -struct memtype *last_lower =NULL ; - -while (node) { - struct memtype *data = rb_entry(node, struct memtype, rb); - -if (get_subtree_max_end (node->rb_left) > start) { -/* Lowest overlap if any must be on left side */ - node = node->rb_left; - }else if (is_node_overlap (data, start, end)) { - last_lower = data; -break ; - }else if (start >= data->start) { -/* Lowest overlap if any must be on right side */ - node = node->rb_right; - }else { -break ; - } - } -return last_lower;/* Returns NULL if there is no overlap */ -} +static struct rb_root_cached memtype_rbroot =RB_ROOT_CACHED ;enum {MEMTYPE_EXACT_MATCH =0 ,MEMTYPE_END_MATCH =1 }; -static struct memtype *memtype_rb_match (struct rb_root *root, -u64 start,u64 end,int match_type) +static struct memtype *memtype_match (struct rb_root_cached *root, +u64 start,u64 end,int match_type) {struct memtype *match; - match =memtype_rb_lowest_match (root, start, end); + match =memtype_interval_iter_first (root, start, end);while (match !=NULL && match->start < end) { -struct rb_node *node; -if ((match_type ==MEMTYPE_EXACT_MATCH ) && (match->start == start) && (match->end == end))return match;
@@ -107,26 +67,21 @@ static struct memtype *memtype_rb_match(struct rb_root *root, (match->start < start) && (match->end == end))return match; - node =rb_next (&match->rb); -if (node) - match = rb_entry(node, struct memtype, rb); -else - match =NULL ; + match =memtype_interval_iter_next (match, start, end); }return NULL ;/* Returns NULL if there is no match */ } -static int memtype_rb_check_conflict (struct rb_root *root, +static int memtype_rb_check_conflict (struct rb_root_cached *root,u64 start,u64 end,enum page_cache_mode reqtype,enum page_cache_mode *newtype) { -struct rb_node *node;struct memtype *match;enum page_cache_mode found_type = reqtype; - match =memtype_rb_lowest_match (&memtype_rbroot, start, end); + match =memtype_interval_iter_first (&memtype_rbroot, start, end);if (match ==NULL ) goto success;
@@ -136,19 +91,12 @@ static int memtype_rb_check_conflict(struct rb_root *root,dprintk ("Overlap at 0x%Lx-0x%Lx\n" , match->start, match->end); found_type = match->type; - node =rb_next (&match->rb); -while (node) { - match = rb_entry(node, struct memtype, rb); - -if (match->start >= end)/* Checked all possible matches */ - goto success; - -if (is_node_overlap (match, start, end) && - match->type != found_type) { + match =memtype_interval_iter_next (match, start, end); +while (match) { +if (match->type != found_type) goto failure; - } - node =rb_next (&match->rb); + match =memtype_interval_iter_next (match, start, end); } success:if (newtype)
@@ -163,44 +111,21 @@ failure:return -EBUSY ; } -static void memtype_rb_insert (struct rb_root *root,struct memtype *newdata) -{ -struct rb_node **node = &(root->rb_node); -struct rb_node *parent =NULL ; - -while (*node) { - struct memtype *data = rb_entry(*node, struct memtype, rb); - - parent = *node; -if (data->subtree_max_end < newdata->end) - data->subtree_max_end = newdata->end; -if (newdata->start <= data->start) - node = &((*node)->rb_left); -else if (newdata->start > data->start) - node = &((*node)->rb_right); - } - - newdata->subtree_max_end = newdata->end; -rb_link_node (&newdata->rb, parent, node); -rb_insert_augmented (&newdata->rb, root, &memtype_rb_augment_cb); -} -int rbt_memtype_check_insert (struct memtype *new,enum page_cache_mode *ret_type) {int err =0 ; err =memtype_rb_check_conflict (&memtype_rbroot, new->start, new->end, - new->type, ret_type); + new->type, ret_type); +if (err) +return err; -if (!err) { -if (ret_type) - new->type = *ret_type; +if (ret_type) + new->type = *ret_type; - new->subtree_max_end = new->end; -memtype_rb_insert (&memtype_rbroot, new); - } -return err; +memtype_interval_insert (new, &memtype_rbroot); +return 0 ; }struct memtype *rbt_memtype_erase (u64 start,u64 end)
@@ -214,26 +139,23 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)* it then checks with END_MATCH, i.e. shrink the size of a node * from the end for the mremap case. */ - data =memtype_rb_match (&memtype_rbroot, start, end, -MEMTYPE_EXACT_MATCH ); + data =memtype_match (&memtype_rbroot, start, end, +MEMTYPE_EXACT_MATCH );if (!data) { - data =memtype_rb_match (&memtype_rbroot, start, end, -MEMTYPE_END_MATCH ); + data =memtype_match (&memtype_rbroot, start, end, +MEMTYPE_END_MATCH );if (!data)return ERR_PTR (-EINVAL ); }if (data->start == start) {/* munmap: erase this node */ -rb_erase_augmented (&data->rb, &memtype_rbroot, - &memtype_rb_augment_cb); +memtype_interval_remove (data, &memtype_rbroot); }else {/* mremap: update the end value of this node */ -rb_erase_augmented (&data->rb, &memtype_rbroot, - &memtype_rb_augment_cb); +memtype_interval_remove (data, &memtype_rbroot); data->end = start; - data->subtree_max_end = data->end; -memtype_rb_insert (&memtype_rbroot, data); +memtype_interval_insert (data, &memtype_rbroot);return NULL ; }
@@ -242,24 +164,24 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)struct memtype *rbt_memtype_lookup (u64 addr) { -return memtype_rb_lowest_match (&memtype_rbroot, addr, addr +PAGE_SIZE ); +return memtype_interval_iter_first (&memtype_rbroot, addr, + addr +PAGE_SIZE ); }#if defined(CONFIG_DEBUG_FS )int rbt_memtype_copy_nth_element (struct memtype *out,loff_t pos) { -struct rb_node *node; +struct memtype *match;int i =1 ; - node =rb_first (&memtype_rbroot); -while (node && pos != i) { - node =rb_next (node); + match =memtype_interval_iter_first (&memtype_rbroot,0 ,ULONG_MAX ); +while (match && pos != i) { + match =memtype_interval_iter_next (match,0 ,ULONG_MAX ); i++; } -if (node) {/* pos == i */ - struct memtype *this = rb_entry(node, struct memtype, rb); - *out = *this; +if (match) {/* pos == i */ + *out = *match;return 0 ; }else {return 1 ;
[tip: x86/mm] x86/mm/pat: Convert the PAT tree to a generic interval tree
In reply to Davidlohr BuesoThe following commit has been merged into the x86/mm branch of tip:
The following commit has been merged into the x86/mm branch of tip:
Commit-ID: 8d04a5f97a5fa9d7afdf46eda3a5ceaa973a1bcc Gitweb: https://git.kernel.org/tip/8d04a5f97a5fa9d7afdf46eda3a5ceaa973a1bcc Author: Davidlohr Bueso <[email protected]> AuthorDate: Wed, 20 Nov 2019 17:15:58 -08:00 Committer: Ingo Molnar <[email protected]> CommitterDate: Thu, 21 Nov 2019 18:47:30 +01:00
x86/mm/pat: Convert the PAT tree to a generic interval tree
With some considerations, the custom pat_rbtree implementation can be simplified to use most of the generic interval_tree machinery:
- The tree inorder traversal can slightly differ when there are key ('start') collisions in the tree due to one going left and another right. This, however, only affects the output of debugfs' pat_memtype_list file.
- Generic interval trees are now fully closed [a, b], for which we need to adjust the last endpoint (ie: end - 1).
- Erasing logic must remain untouched as well.
- In order for the types to remain u64, the 'memtype_interval' calls are introduced, as opposed to simply using struct interval_tree.
In addition, the PAT tree might potentially also benefit by the fast overlap detection for the insertion case when looking up the first overlapping node in the tree.
No change in behavior is intended.
Finally, I've tested this on various servers, via sanity warnings, running side by side with the current version and so far see no differences in the returned pointer node when doing memtype_rb_lowest_match() lookups.
--- arch/x86/mm/pat_rbtree.c | 162 +++++++++----------------------------- 1 file changed, 42 insertions(+), 120 deletions(-)
arch/x86/mm/pat_rbtree.c +42 -120
@@ -5,14 +5,13 @@* Authors: Venkatesh Pallipadi <[email protected]> * Suresh B Siddha <[email protected]> * -* Interval tree (augmented rbtree) used to store the PAT memory type -* reservations. +* Interval tree used to store the PAT memory type reservations. */ #include <linux/seq_file.h> #include <linux/debugfs.h> #include <linux/kernel.h> -#include <linux/rbtree_augmented.h> +#include <linux/interval_tree_generic.h> #include <linux/sched.h> #include <linux/gfp.h>
@@ -33,72 +32,33 @@* * memtype_lock protects the rbtree. */ - -static struct rb_root memtype_rbroot =RB_ROOT ; - -static int is_node_overlap (struct memtype *node,u64 start,u64 end) +static inline u64 memtype_interval_start (struct memtype *memtype) { -if (node->start >= end || node->end <= start) -return 0 ; - -return 1 ; +return memtype->start; } -static u64 get_subtree_max_end (struct rb_node *node) +static inline u64 memtype_interval_end (struct memtype *memtype) { -u64 ret =0 ; -if (node) { - struct memtype *data = rb_entry(node, struct memtype, rb); - ret = data->subtree_max_end; - } -return ret; +return memtype->end -1 ; } +INTERVAL_TREE_DEFINE(struct memtype, rb, u64, subtree_max_end, + memtype_interval_start, memtype_interval_end, + static, memtype_interval) -#define NODE_END (node) ((node)->end) - -RB_DECLARE_CALLBACKS_MAX (static, memtype_rb_augment_cb, - struct memtype, rb, u64, subtree_max_end, NODE_END) - -/* Find the first (lowest start addr) overlapping range from rb tree */ -static struct memtype *memtype_rb_lowest_match (struct rb_root *root, -u64 start,u64 end) -{ -struct rb_node *node = root->rb_node; -struct memtype *last_lower =NULL ; - -while (node) { - struct memtype *data = rb_entry(node, struct memtype, rb); - -if (get_subtree_max_end (node->rb_left) > start) { -/* Lowest overlap if any must be on left side */ - node = node->rb_left; - }else if (is_node_overlap (data, start, end)) { - last_lower = data; -break ; - }else if (start >= data->start) { -/* Lowest overlap if any must be on right side */ - node = node->rb_right; - }else { -break ; - } - } -return last_lower;/* Returns NULL if there is no overlap */ -} +static struct rb_root_cached memtype_rbroot =RB_ROOT_CACHED ;enum {MEMTYPE_EXACT_MATCH =0 ,MEMTYPE_END_MATCH =1 }; -static struct memtype *memtype_rb_match (struct rb_root *root, -u64 start,u64 end,int match_type) +static struct memtype *memtype_match (struct rb_root_cached *root, +u64 start,u64 end,int match_type) {struct memtype *match; - match =memtype_rb_lowest_match (root, start, end); + match =memtype_interval_iter_first (root, start, end);while (match !=NULL && match->start < end) { -struct rb_node *node; -if ((match_type ==MEMTYPE_EXACT_MATCH ) && (match->start == start) && (match->end == end))return match;
@@ -107,26 +67,21 @@ static struct memtype *memtype_rb_match(struct rb_root *root, (match->start < start) && (match->end == end))return match; - node =rb_next (&match->rb); -if (node) - match = rb_entry(node, struct memtype, rb); -else - match =NULL ; + match =memtype_interval_iter_next (match, start, end); }return NULL ;/* Returns NULL if there is no match */ } -static int memtype_rb_check_conflict (struct rb_root *root, +static int memtype_rb_check_conflict (struct rb_root_cached *root,u64 start,u64 end,enum page_cache_mode reqtype,enum page_cache_mode *newtype) { -struct rb_node *node;struct memtype *match;enum page_cache_mode found_type = reqtype; - match =memtype_rb_lowest_match (&memtype_rbroot, start, end); + match =memtype_interval_iter_first (&memtype_rbroot, start, end);if (match ==NULL ) goto success;
@@ -136,19 +91,12 @@ static int memtype_rb_check_conflict(struct rb_root *root,dprintk ("Overlap at 0x%Lx-0x%Lx\n" , match->start, match->end); found_type = match->type; - node =rb_next (&match->rb); -while (node) { - match = rb_entry(node, struct memtype, rb); - -if (match->start >= end)/* Checked all possible matches */ - goto success; - -if (is_node_overlap (match, start, end) && - match->type != found_type) { + match =memtype_interval_iter_next (match, start, end); +while (match) { +if (match->type != found_type) goto failure; - } - node =rb_next (&match->rb); + match =memtype_interval_iter_next (match, start, end); } success:if (newtype)
@@ -163,44 +111,21 @@ failure:return -EBUSY ; } -static void memtype_rb_insert (struct rb_root *root,struct memtype *newdata) -{ -struct rb_node **node = &(root->rb_node); -struct rb_node *parent =NULL ; - -while (*node) { - struct memtype *data = rb_entry(*node, struct memtype, rb); - - parent = *node; -if (data->subtree_max_end < newdata->end) - data->subtree_max_end = newdata->end; -if (newdata->start <= data->start) - node = &((*node)->rb_left); -else if (newdata->start > data->start) - node = &((*node)->rb_right); - } - - newdata->subtree_max_end = newdata->end; -rb_link_node (&newdata->rb, parent, node); -rb_insert_augmented (&newdata->rb, root, &memtype_rb_augment_cb); -} -int rbt_memtype_check_insert (struct memtype *new,enum page_cache_mode *ret_type) {int err =0 ; err =memtype_rb_check_conflict (&memtype_rbroot, new->start, new->end, - new->type, ret_type); + new->type, ret_type); +if (err) +return err; -if (!err) { -if (ret_type) - new->type = *ret_type; +if (ret_type) + new->type = *ret_type; - new->subtree_max_end = new->end; -memtype_rb_insert (&memtype_rbroot, new); - } -return err; +memtype_interval_insert (new, &memtype_rbroot); +return 0 ; }struct memtype *rbt_memtype_erase (u64 start,u64 end)
@@ -214,26 +139,23 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)* it then checks with END_MATCH, i.e. shrink the size of a node * from the end for the mremap case. */ - data =memtype_rb_match (&memtype_rbroot, start, end, -MEMTYPE_EXACT_MATCH ); + data =memtype_match (&memtype_rbroot, start, end, +MEMTYPE_EXACT_MATCH );if (!data) { - data =memtype_rb_match (&memtype_rbroot, start, end, -MEMTYPE_END_MATCH ); + data =memtype_match (&memtype_rbroot, start, end, +MEMTYPE_END_MATCH );if (!data)return ERR_PTR (-EINVAL ); }if (data->start == start) {/* munmap: erase this node */ -rb_erase_augmented (&data->rb, &memtype_rbroot, - &memtype_rb_augment_cb); +memtype_interval_remove (data, &memtype_rbroot); }else {/* mremap: update the end value of this node */ -rb_erase_augmented (&data->rb, &memtype_rbroot, - &memtype_rb_augment_cb); +memtype_interval_remove (data, &memtype_rbroot); data->end = start; - data->subtree_max_end = data->end; -memtype_rb_insert (&memtype_rbroot, data); +memtype_interval_insert (data, &memtype_rbroot);return NULL ; }
@@ -242,24 +164,24 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)struct memtype *rbt_memtype_lookup (u64 addr) { -return memtype_rb_lowest_match (&memtype_rbroot, addr, addr +PAGE_SIZE ); +return memtype_interval_iter_first (&memtype_rbroot, addr, + addr +PAGE_SIZE ); }#if defined(CONFIG_DEBUG_FS )int rbt_memtype_copy_nth_element (struct memtype *out,loff_t pos) { -struct rb_node *node; +struct memtype *match;int i =1 ; - node =rb_first (&memtype_rbroot); -while (node && pos != i) { - node =rb_next (node); + match =memtype_interval_iter_first (&memtype_rbroot,0 ,ULONG_MAX ); +while (match && pos != i) { + match =memtype_interval_iter_next (match,0 ,ULONG_MAX ); i++; } -if (node) {/* pos == i */ - struct memtype *this = rb_entry(node, struct memtype, rb); - *out = *this; +if (match) {/* pos == i */ + *out = *match;return 0 ; }else {return 1 ;
PATCH v3 2/4 x86/mm, pat: Cleanup some of the local memtype_rb_* calls
In reply to Davidlohr BuesoCleanup by both getting rid of passing the rb_root down the helper calls; there is only one. Secondly rename some of the calls from memtype_rb_*.
--- arch/x86/mm/pat_rbtree.c | 21 ++++++++------------- 1 file changed, 8 insertions(+), 13 deletions(-)
arch/x86/mm/pat_rbtree.c +8 -13
@@ -52,12 +52,11 @@ enum { MEMTYPE_END_MATCH = 1 }; -static struct memtype *memtype_match (struct rb_root_cached *root, -u64 start,u64 end,int match_type) +static struct memtype *memtype_match (u64 start,u64 end,int match_type) {struct memtype *match; - match =memtype_interval_iter_first (root, start, end); + match =memtype_interval_iter_first (&memtype_rbroot, start, end);while (match !=NULL && match->start < end) {if ((match_type ==MEMTYPE_EXACT_MATCH ) && (match->start == start) && (match->end == end))
@@ -73,10 +72,9 @@ static struct memtype *memtype_match(struct rb_root_cached *root,return NULL ;/* Returns NULL if there is no match */ } -static int memtype_rb_check_conflict (struct rb_root_cached *root, -u64 start,u64 end, -enum page_cache_mode reqtype, -enum page_cache_mode *newtype) +static int memtype_check_conflict (u64 start,u64 end, +enum page_cache_mode reqtype, +enum page_cache_mode *newtype) {struct memtype *match;enum page_cache_mode found_type = reqtype;
@@ -116,8 +114,7 @@ int rbt_memtype_check_insert(struct memtype *new, {int err =0 ; - err =memtype_rb_check_conflict (&memtype_rbroot, new->start, new->end, - new->type, ret_type); + err =memtype_check_conflict (new->start, new->end, new->type, ret_type);if (err)return err;
@@ -139,11 +136,9 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)* it then checks with END_MATCH, i.e. shrink the size of a node * from the end for the mremap case. */ - data =memtype_match (&memtype_rbroot, start, end, -MEMTYPE_EXACT_MATCH ); + data =memtype_match (start, end,MEMTYPE_EXACT_MATCH );if (!data) { - data =memtype_match (&memtype_rbroot, start, end, -MEMTYPE_END_MATCH ); + data =memtype_match (start, end,MEMTYPE_END_MATCH );if (!data)return ERR_PTR (-EINVAL ); }
Signature · 1 line
2.16.4
[tip: x86/mm] x86/mm/pat: Do not pass 'rb_root' down the memtype tree helper functions
The following commit has been merged into the x86/mm branch of tip:
The following commit has been merged into the x86/mm branch of tip:
Commit-ID: a2cb4c9af3150189b0e31039333d6fa0c54776e8 Gitweb: https://git.kernel.org/tip/a2cb4c9af3150189b0e31039333d6fa0c54776e8 Author: Davidlohr Bueso <[email protected]> AuthorDate: Wed, 20 Nov 2019 17:15:59 -08:00 Committer: Ingo Molnar <[email protected]> CommitterDate: Thu, 21 Nov 2019 17:37:31 +01:00
x86/mm/pat: Do not pass 'rb_root' down the memtype tree helper functions
Get rid of the passing the rb_root down the helper calls; there is only one: &memtype_rbroot.
No change in functionality.
[ mingo: Fixed the changelog which described a different version of the patch. ]
--- arch/x86/mm/pat_rbtree.c | 21 ++++++++------------- 1 file changed, 8 insertions(+), 13 deletions(-)
arch/x86/mm/pat_rbtree.c +8 -13
@@ -52,12 +52,11 @@ enum { MEMTYPE_END_MATCH = 1 }; -static struct memtype *memtype_match (struct rb_root_cached *root, -u64 start,u64 end,int match_type) +static struct memtype *memtype_match (u64 start,u64 end,int match_type) {struct memtype *match; - match =memtype_interval_iter_first (root, start, end); + match =memtype_interval_iter_first (&memtype_rbroot, start, end);while (match !=NULL && match->start < end) {if ((match_type ==MEMTYPE_EXACT_MATCH ) && (match->start == start) && (match->end == end))
@@ -73,10 +72,9 @@ static struct memtype *memtype_match(struct rb_root_cached *root,return NULL ;/* Returns NULL if there is no match */ } -static int memtype_rb_check_conflict (struct rb_root_cached *root, -u64 start,u64 end, -enum page_cache_mode reqtype, -enum page_cache_mode *newtype) +static int memtype_check_conflict (u64 start,u64 end, +enum page_cache_mode reqtype, +enum page_cache_mode *newtype) {struct memtype *match;enum page_cache_mode found_type = reqtype;
@@ -116,8 +114,7 @@ int rbt_memtype_check_insert(struct memtype *new, {int err =0 ; - err =memtype_rb_check_conflict (&memtype_rbroot, new->start, new->end, - new->type, ret_type); + err =memtype_check_conflict (new->start, new->end, new->type, ret_type);if (err)return err;
@@ -139,11 +136,9 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)* it then checks with END_MATCH, i.e. shrink the size of a node * from the end for the mremap case. */ - data =memtype_match (&memtype_rbroot, start, end, -MEMTYPE_EXACT_MATCH ); + data =memtype_match (start, end,MEMTYPE_EXACT_MATCH );if (!data) { - data =memtype_match (&memtype_rbroot, start, end, -MEMTYPE_END_MATCH ); + data =memtype_match (start, end,MEMTYPE_END_MATCH );if (!data)return ERR_PTR (-EINVAL ); }
Re: [PATCH 2/4] x86/mm, pat: Cleanup some of the local memtype_rb_* calls
In reply to Davidlohr BuesoQuoted 6 lines · Davidlohr Bueso
Cleanup by both getting rid of passing the
rb_rootdown the helper calls; there is only one. Secondly rename some of the calls from memtype_rb_*.Reviewed-by Thomas Gleixner <[email protected]>Signed-off-by Davidlohr Bueso <[email protected]>
Note that the changelog doesn't match what the patch does - in reality the renames are done in a separate patch.
I fixed up the changelog as you can see it from the tip-bot notification.
Thanks,
Ingo
[tip: x86/mm] x86/mm/pat: Do not pass 'rb_root' down the memtype tree helper functions
In reply to Davidlohr BuesoThe following commit has been merged into the x86/mm branch of tip:
The following commit has been merged into the x86/mm branch of tip:
Commit-ID: 6a9930b1c50d83facfa0f78e4f2f9ba0364f43f3 Gitweb: https://git.kernel.org/tip/6a9930b1c50d83facfa0f78e4f2f9ba0364f43f3 Author: Davidlohr Bueso <[email protected]> AuthorDate: Wed, 20 Nov 2019 17:15:59 -08:00 Committer: Ingo Molnar <[email protected]> CommitterDate: Thu, 21 Nov 2019 18:47:59 +01:00
x86/mm/pat: Do not pass 'rb_root' down the memtype tree helper functions
Get rid of the passing the rb_root down the helper calls; there is only one: &memtype_rbroot.
No change in functionality.
[ mingo: Fixed the changelog which described a different version of the patch. ]
--- arch/x86/mm/pat_rbtree.c | 21 ++++++++------------- 1 file changed, 8 insertions(+), 13 deletions(-)
arch/x86/mm/pat_rbtree.c +8 -13
@@ -52,12 +52,11 @@ enum { MEMTYPE_END_MATCH = 1 }; -static struct memtype *memtype_match (struct rb_root_cached *root, -u64 start,u64 end,int match_type) +static struct memtype *memtype_match (u64 start,u64 end,int match_type) {struct memtype *match; - match =memtype_interval_iter_first (root, start, end); + match =memtype_interval_iter_first (&memtype_rbroot, start, end);while (match !=NULL && match->start < end) {if ((match_type ==MEMTYPE_EXACT_MATCH ) && (match->start == start) && (match->end == end))
@@ -73,10 +72,9 @@ static struct memtype *memtype_match(struct rb_root_cached *root,return NULL ;/* Returns NULL if there is no match */ } -static int memtype_rb_check_conflict (struct rb_root_cached *root, -u64 start,u64 end, -enum page_cache_mode reqtype, -enum page_cache_mode *newtype) +static int memtype_check_conflict (u64 start,u64 end, +enum page_cache_mode reqtype, +enum page_cache_mode *newtype) {struct memtype *match;enum page_cache_mode found_type = reqtype;
@@ -116,8 +114,7 @@ int rbt_memtype_check_insert(struct memtype *new, {int err =0 ; - err =memtype_rb_check_conflict (&memtype_rbroot, new->start, new->end, - new->type, ret_type); + err =memtype_check_conflict (new->start, new->end, new->type, ret_type);if (err)return err;
@@ -139,11 +136,9 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)* it then checks with END_MATCH, i.e. shrink the size of a node * from the end for the mremap case. */ - data =memtype_match (&memtype_rbroot, start, end, -MEMTYPE_EXACT_MATCH ); + data =memtype_match (start, end,MEMTYPE_EXACT_MATCH );if (!data) { - data =memtype_match (&memtype_rbroot, start, end, -MEMTYPE_END_MATCH ); + data =memtype_match (start, end,MEMTYPE_END_MATCH );if (!data)return ERR_PTR (-EINVAL ); }
PATCH v3 3/4 x86/mm, pat: Drop rbt prefix from external memtype calls
In reply to Davidlohr BuesoDrop the rbt_memtype_* calls (those used by pat.c) as we no longer use an rbtree directly.
--- arch/x86/mm/pat.c | 8 ++++---- arch/x86/mm/pat_internal.h | 20 ++++++++++---------- arch/x86/mm/pat_rbtree.c | 12 ++++++------ 3 files changed, 20 insertions(+), 20 deletions(-)
arch/x86/mm/pat.c +4 -4
@@ -603,7 +603,7 @@ int reserve_memtype(u64 start, u64 end, enum page_cache_mode req_type,spin_lock (&memtype_lock); - err =rbt_memtype_check_insert (new, new_type); + err =memtype_check_insert (new, new_type);if (err) { pr_info("x86/PAT: reserve_memtype failed [mem %#010Lx-%#010Lx], track %s, req %s\n", start, end - 1,
@@ -650,7 +650,7 @@ int free_memtype(u64 start, u64 end) }spin_lock (&memtype_lock); - entry =rbt_memtype_erase (start, end); + entry =memtype_erase (start, end);spin_unlock (&memtype_lock);if (IS_ERR (entry)) {
@@ -693,7 +693,7 @@ static enum page_cache_mode lookup_memtype(u64 paddr)spin_lock (&memtype_lock); - entry =rbt_memtype_lookup (paddr); + entry =memtype_lookup (paddr);if (entry !=NULL ) rettype = entry->type;else
@@ -1109,7 +1109,7 @@ static struct memtype *memtype_get_idx(loff_t pos)return NULL ;spin_lock (&memtype_lock); - ret =rbt_memtype_copy_nth_element (print_entry, pos); + ret =memtype_copy_nth_element (print_entry, pos);spin_unlock (&memtype_lock);if (!ret) {
arch/x86/mm/pat_internal.h +10 -10
@@ -29,20 +29,20 @@ static inline char *cattr_name(enum page_cache_mode pcm) }#ifdef CONFIG_X86_PAT -extern int rbt_memtype_check_insert (struct memtype *new, -enum page_cache_mode *new_type); -extern struct memtype *rbt_memtype_erase (u64 start,u64 end); -extern struct memtype *rbt_memtype_lookup (u64 addr); -extern int rbt_memtype_copy_nth_element (struct memtype *out,loff_t pos); +extern int memtype_check_insert (struct memtype *new, +enum page_cache_mode *new_type); +extern struct memtype *memtype_erase (u64 start,u64 end); +extern struct memtype *memtype_lookup (u64 addr); +extern int memtype_copy_nth_element (struct memtype *out,loff_t pos);#else -static inline int rbt_memtype_check_insert (struct memtype *new, -enum page_cache_mode *new_type) +static inline int memtype_check_insert (struct memtype *new, +enum page_cache_mode *new_type) {return 0 ; } -static inline struct memtype *rbt_memtype_erase (u64 start,u64 end) +static inline struct memtype *memtype_erase (u64 start,u64 end) {return NULL ; } -static inline struct memtype *rbt_memtype_lookup (u64 addr) +static inline struct memtype *memtype_lookup (u64 addr) {return NULL ; } -static inline int rbt_memtype_copy_nth_element (struct memtype *out,loff_t pos) +static inline int memtype_copy_nth_element (struct memtype *out,loff_t pos) {return 0 ; }#endif
arch/x86/mm/pat_rbtree.c +6 -6
@@ -109,8 +109,8 @@ static int memtype_check_conflict(u64 start, u64 end,return -EBUSY ; } -int rbt_memtype_check_insert (struct memtype *new, -enum page_cache_mode *ret_type) +int memtype_check_insert (struct memtype *new, +enum page_cache_mode *ret_type) {int err =0 ;
@@ -125,13 +125,13 @@ int rbt_memtype_check_insert(struct memtype *new,return 0 ; } -struct memtype *rbt_memtype_erase (u64 start,u64 end) +struct memtype *memtype_erase (u64 start,u64 end) {struct memtype *data;/* * Since the memtype_rbroot tree allows overlapping ranges, -* rbt_memtype_erase() checks with EXACT_MATCH first, i.e. free +* memtype_erase() checks with EXACT_MATCH first, i.e. free * a whole node for the munmap case. If no such entry is found, * it then checks with END_MATCH, i.e. shrink the size of a node * from the end for the mremap case.
@@ -157,14 +157,14 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)return data; } -struct memtype *rbt_memtype_lookup (u64 addr) +struct memtype *memtype_lookup (u64 addr) {return memtype_interval_iter_first (&memtype_rbroot, addr, addr +PAGE_SIZE ); }#if defined(CONFIG_DEBUG_FS ) -int rbt_memtype_copy_nth_element (struct memtype *out,loff_t pos) +int memtype_copy_nth_element (struct memtype *out,loff_t pos) {struct memtype *match;int i =1 ;
Signature · 1 line
2.16.4
[tip: x86/mm] x86/mm/pat: Drop the rbt_ prefix from external memtype calls
The following commit has been merged into the x86/mm branch of tip:
The following commit has been merged into the x86/mm branch of tip:
Commit-ID: 010ca1041da3d0384fbcbaf4e4f92203c8ea9b7b Gitweb: https://git.kernel.org/tip/010ca1041da3d0384fbcbaf4e4f92203c8ea9b7b Author: Davidlohr Bueso <[email protected]> AuthorDate: Wed, 20 Nov 2019 17:16:00 -08:00 Committer: Ingo Molnar <[email protected]> CommitterDate: Thu, 21 Nov 2019 17:37:31 +01:00
x86/mm/pat: Drop the rbt_ prefix from external memtype calls
Drop the rbt_memtype_*() call rbt_ prefix, as we no longer use an rbtree directly.
--- arch/x86/mm/pat.c | 8 ++++---- arch/x86/mm/pat_internal.h | 20 ++++++++++---------- arch/x86/mm/pat_rbtree.c | 12 ++++++------ 3 files changed, 20 insertions(+), 20 deletions(-)
arch/x86/mm/pat.c +4 -4
@@ -603,7 +603,7 @@ int reserve_memtype(u64 start, u64 end, enum page_cache_mode req_type,spin_lock (&memtype_lock); - err =rbt_memtype_check_insert (new, new_type); + err =memtype_check_insert (new, new_type);if (err) { pr_info("x86/PAT: reserve_memtype failed [mem %#010Lx-%#010Lx], track %s, req %s\n", start, end - 1,
@@ -650,7 +650,7 @@ int free_memtype(u64 start, u64 end) }spin_lock (&memtype_lock); - entry =rbt_memtype_erase (start, end); + entry =memtype_erase (start, end);spin_unlock (&memtype_lock);if (IS_ERR (entry)) {
@@ -693,7 +693,7 @@ static enum page_cache_mode lookup_memtype(u64 paddr)spin_lock (&memtype_lock); - entry =rbt_memtype_lookup (paddr); + entry =memtype_lookup (paddr);if (entry !=NULL ) rettype = entry->type;else
@@ -1109,7 +1109,7 @@ static struct memtype *memtype_get_idx(loff_t pos)return NULL ;spin_lock (&memtype_lock); - ret =rbt_memtype_copy_nth_element (print_entry, pos); + ret =memtype_copy_nth_element (print_entry, pos);spin_unlock (&memtype_lock);if (!ret) {
arch/x86/mm/pat_internal.h +10 -10
@@ -29,20 +29,20 @@ static inline char *cattr_name(enum page_cache_mode pcm) }#ifdef CONFIG_X86_PAT -extern int rbt_memtype_check_insert (struct memtype *new, -enum page_cache_mode *new_type); -extern struct memtype *rbt_memtype_erase (u64 start,u64 end); -extern struct memtype *rbt_memtype_lookup (u64 addr); -extern int rbt_memtype_copy_nth_element (struct memtype *out,loff_t pos); +extern int memtype_check_insert (struct memtype *new, +enum page_cache_mode *new_type); +extern struct memtype *memtype_erase (u64 start,u64 end); +extern struct memtype *memtype_lookup (u64 addr); +extern int memtype_copy_nth_element (struct memtype *out,loff_t pos);#else -static inline int rbt_memtype_check_insert (struct memtype *new, -enum page_cache_mode *new_type) +static inline int memtype_check_insert (struct memtype *new, +enum page_cache_mode *new_type) {return 0 ; } -static inline struct memtype *rbt_memtype_erase (u64 start,u64 end) +static inline struct memtype *memtype_erase (u64 start,u64 end) {return NULL ; } -static inline struct memtype *rbt_memtype_lookup (u64 addr) +static inline struct memtype *memtype_lookup (u64 addr) {return NULL ; } -static inline int rbt_memtype_copy_nth_element (struct memtype *out,loff_t pos) +static inline int memtype_copy_nth_element (struct memtype *out,loff_t pos) {return 0 ; }#endif
arch/x86/mm/pat_rbtree.c +6 -6
@@ -109,8 +109,8 @@ failure:return -EBUSY ; } -int rbt_memtype_check_insert (struct memtype *new, -enum page_cache_mode *ret_type) +int memtype_check_insert (struct memtype *new, +enum page_cache_mode *ret_type) {int err =0 ;
@@ -125,13 +125,13 @@ int rbt_memtype_check_insert(struct memtype *new,return 0 ; } -struct memtype *rbt_memtype_erase (u64 start,u64 end) +struct memtype *memtype_erase (u64 start,u64 end) {struct memtype *data;/* * Since the memtype_rbroot tree allows overlapping ranges, -* rbt_memtype_erase() checks with EXACT_MATCH first, i.e. free +* memtype_erase() checks with EXACT_MATCH first, i.e. free * a whole node for the munmap case. If no such entry is found, * it then checks with END_MATCH, i.e. shrink the size of a node * from the end for the mremap case.
@@ -157,14 +157,14 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)return data; } -struct memtype *rbt_memtype_lookup (u64 addr) +struct memtype *memtype_lookup (u64 addr) {return memtype_interval_iter_first (&memtype_rbroot, addr, addr +PAGE_SIZE ); }#if defined(CONFIG_DEBUG_FS ) -int rbt_memtype_copy_nth_element (struct memtype *out,loff_t pos) +int memtype_copy_nth_element (struct memtype *out,loff_t pos) {struct memtype *match;int i =1 ;
[tip: x86/mm] x86/mm/pat: Drop the rbt_ prefix from external memtype calls
In reply to Davidlohr BuesoThe following commit has been merged into the x86/mm branch of tip:
The following commit has been merged into the x86/mm branch of tip:
Commit-ID: 511aaca834fe2dc0b652406bda6283842fdc70ce Gitweb: https://git.kernel.org/tip/511aaca834fe2dc0b652406bda6283842fdc70ce Author: Davidlohr Bueso <[email protected]> AuthorDate: Wed, 20 Nov 2019 17:16:00 -08:00 Committer: Ingo Molnar <[email protected]> CommitterDate: Thu, 21 Nov 2019 18:48:07 +01:00
x86/mm/pat: Drop the rbt_ prefix from external memtype calls
Drop the rbt_memtype_*() call rbt_ prefix, as we no longer use an rbtree directly.
--- arch/x86/mm/pat.c | 8 ++++---- arch/x86/mm/pat_internal.h | 20 ++++++++++---------- arch/x86/mm/pat_rbtree.c | 12 ++++++------ 3 files changed, 20 insertions(+), 20 deletions(-)
arch/x86/mm/pat.c +4 -4
@@ -603,7 +603,7 @@ int reserve_memtype(u64 start, u64 end, enum page_cache_mode req_type,spin_lock (&memtype_lock); - err =rbt_memtype_check_insert (new, new_type); + err =memtype_check_insert (new, new_type);if (err) { pr_info("x86/PAT: reserve_memtype failed [mem %#010Lx-%#010Lx], track %s, req %s\n", start, end - 1,
@@ -650,7 +650,7 @@ int free_memtype(u64 start, u64 end) }spin_lock (&memtype_lock); - entry =rbt_memtype_erase (start, end); + entry =memtype_erase (start, end);spin_unlock (&memtype_lock);if (IS_ERR (entry)) {
@@ -693,7 +693,7 @@ static enum page_cache_mode lookup_memtype(u64 paddr)spin_lock (&memtype_lock); - entry =rbt_memtype_lookup (paddr); + entry =memtype_lookup (paddr);if (entry !=NULL ) rettype = entry->type;else
@@ -1109,7 +1109,7 @@ static struct memtype *memtype_get_idx(loff_t pos)return NULL ;spin_lock (&memtype_lock); - ret =rbt_memtype_copy_nth_element (print_entry, pos); + ret =memtype_copy_nth_element (print_entry, pos);spin_unlock (&memtype_lock);if (!ret) {
arch/x86/mm/pat_internal.h +10 -10
@@ -29,20 +29,20 @@ static inline char *cattr_name(enum page_cache_mode pcm) }#ifdef CONFIG_X86_PAT -extern int rbt_memtype_check_insert (struct memtype *new, -enum page_cache_mode *new_type); -extern struct memtype *rbt_memtype_erase (u64 start,u64 end); -extern struct memtype *rbt_memtype_lookup (u64 addr); -extern int rbt_memtype_copy_nth_element (struct memtype *out,loff_t pos); +extern int memtype_check_insert (struct memtype *new, +enum page_cache_mode *new_type); +extern struct memtype *memtype_erase (u64 start,u64 end); +extern struct memtype *memtype_lookup (u64 addr); +extern int memtype_copy_nth_element (struct memtype *out,loff_t pos);#else -static inline int rbt_memtype_check_insert (struct memtype *new, -enum page_cache_mode *new_type) +static inline int memtype_check_insert (struct memtype *new, +enum page_cache_mode *new_type) {return 0 ; } -static inline struct memtype *rbt_memtype_erase (u64 start,u64 end) +static inline struct memtype *memtype_erase (u64 start,u64 end) {return NULL ; } -static inline struct memtype *rbt_memtype_lookup (u64 addr) +static inline struct memtype *memtype_lookup (u64 addr) {return NULL ; } -static inline int rbt_memtype_copy_nth_element (struct memtype *out,loff_t pos) +static inline int memtype_copy_nth_element (struct memtype *out,loff_t pos) {return 0 ; }#endif
arch/x86/mm/pat_rbtree.c +6 -6
@@ -109,8 +109,8 @@ failure:return -EBUSY ; } -int rbt_memtype_check_insert (struct memtype *new, -enum page_cache_mode *ret_type) +int memtype_check_insert (struct memtype *new, +enum page_cache_mode *ret_type) {int err =0 ;
@@ -125,13 +125,13 @@ int rbt_memtype_check_insert(struct memtype *new,return 0 ; } -struct memtype *rbt_memtype_erase (u64 start,u64 end) +struct memtype *memtype_erase (u64 start,u64 end) {struct memtype *data;/* * Since the memtype_rbroot tree allows overlapping ranges, -* rbt_memtype_erase() checks with EXACT_MATCH first, i.e. free +* memtype_erase() checks with EXACT_MATCH first, i.e. free * a whole node for the munmap case. If no such entry is found, * it then checks with END_MATCH, i.e. shrink the size of a node * from the end for the mremap case.
@@ -157,14 +157,14 @@ struct memtype *rbt_memtype_erase(u64 start, u64 end)return data; } -struct memtype *rbt_memtype_lookup (u64 addr) +struct memtype *memtype_lookup (u64 addr) {return memtype_interval_iter_first (&memtype_rbroot, addr, addr +PAGE_SIZE ); }#if defined(CONFIG_DEBUG_FS ) -int rbt_memtype_copy_nth_element (struct memtype *out,loff_t pos) +int memtype_copy_nth_element (struct memtype *out,loff_t pos) {struct memtype *match;int i =1 ;
PATCH v3 4/4 x86/mm, pat: Rename pat_rbtree.c to pat_interval.c
In reply to Davidlohr BuesoConsidering the previous changes, this is a more proper name.
---
arch/x86/mm/Makefile | 2 +-
arch/x86/mm/{pat_rbtree.c => pat_interval.c} | 0
2 files changed, 1 insertion(+), 1 deletion(-)
rename arch/x86/mm/{pat_rbtree.c => pat_interval.c} (100%)arch/x86/mm/Makefile +1 -1
@@ -23,7 +23,7 @@ CFLAGS_mem_encrypt_identity.o := $(nostackp) CFLAGS_fault.o := -I $(srctree)/$(src)/../include/asm/trace -obj-$(CONFIG_X86_PAT) += pat_rbtree.o +obj-$(CONFIG_X86_PAT) += pat_interval.o obj-$(CONFIG_X86_32) += pgtable_32.o iomap_32.o
arch/x86/mm/pat_interval.c renamed from arch/x86/mm/pat_rbtree.c +0 -0
Signature · 1 line
2.16.4
[tip: x86/mm] x86/mm/pat: Rename pat_rbtree.c to pat_interval.c
The following commit has been merged into the x86/mm branch of tip:
The following commit has been merged into the x86/mm branch of tip:
Commit-ID: 820cac65197c2a5ff8eb5af658909ce0210a358b Gitweb: https://git.kernel.org/tip/820cac65197c2a5ff8eb5af658909ce0210a358b Author: Davidlohr Bueso <[email protected]> AuthorDate: Wed, 20 Nov 2019 17:16:01 -08:00 Committer: Ingo Molnar <[email protected]> CommitterDate: Thu, 21 Nov 2019 17:37:32 +01:00
x86/mm/pat: Rename pat_rbtree.c to pat_interval.c
Considering the previous changes, this is a more proper name.
--- arch/x86/mm/Makefile | 2 +- arch/x86/mm/pat_interval.c | 185 ++++++++++++++++++++++++++++++++++++- arch/x86/mm/pat_rbtree.c | 185 +------------------------------------ 3 files changed, 186 insertions(+), 186 deletions(-) create mode 100644 arch/x86/mm/pat_interval.c delete mode 100644 arch/x86/mm/pat_rbtree.c
arch/x86/mm/Makefile +1 -1
@@ -23,7 +23,7 @@ CFLAGS_mem_encrypt_identity.o := $(nostackp) CFLAGS_fault.o := -I $(srctree)/$(src)/../include/asm/trace -obj-$(CONFIG_X86_PAT) += pat_rbtree.o +obj-$(CONFIG_X86_PAT) += pat_interval.o obj-$(CONFIG_X86_32) += pgtable_32.o iomap_32.o
arch/x86/mm/pat_interval.c new file +185 -0
185 lines not on this page · raw message
arch/x86/mm/pat_rbtree.c deleted +0 -185
185 lines not on this page · raw message
[tip: x86/mm] x86/mm/pat: Rename pat_rbtree.c to pat_interval.c
In reply to Davidlohr BuesoThe following commit has been merged into the x86/mm branch of tip:
The following commit has been merged into the x86/mm branch of tip:
Commit-ID: 7f264dab5b60343358e788d4c939c166c22ea4a2 Gitweb: https://git.kernel.org/tip/7f264dab5b60343358e788d4c939c166c22ea4a2 Author: Davidlohr Bueso <[email protected]> AuthorDate: Wed, 20 Nov 2019 17:16:01 -08:00 Committer: Ingo Molnar <[email protected]> CommitterDate: Thu, 21 Nov 2019 18:48:18 +01:00
x86/mm/pat: Rename pat_rbtree.c to pat_interval.c
Considering the previous changes, this is a more proper name.
--- arch/x86/mm/Makefile | 2 +- arch/x86/mm/pat_interval.c | 185 ++++++++++++++++++++++++++++++++++++- arch/x86/mm/pat_rbtree.c | 185 +------------------------------------ 3 files changed, 186 insertions(+), 186 deletions(-) create mode 100644 arch/x86/mm/pat_interval.c delete mode 100644 arch/x86/mm/pat_rbtree.c
arch/x86/mm/Makefile +1 -1
@@ -23,7 +23,7 @@ CFLAGS_mem_encrypt_identity.o := $(nostackp) CFLAGS_fault.o := -I $(srctree)/$(src)/../include/asm/trace -obj-$(CONFIG_X86_PAT) += pat_rbtree.o +obj-$(CONFIG_X86_PAT) += pat_interval.o obj-$(CONFIG_X86_32) += pgtable_32.o iomap_32.o
arch/x86/mm/pat_interval.c new file +185 -0
185 lines not on this page · raw message
arch/x86/mm/pat_rbtree.c deleted +0 -185
185 lines not on this page · raw message
Quoted 35 lines · Davidlohr Bueso
Changes from v2:
- Removed unnecessary goto error path in patch 1, per tglx.
- Added the correspondingMakefilechange for patch 4, per mingo.
- Added tglx's review tags.Changes from v1[0]:
- Got rid of more code in patch 1 by using the end - 1 for closed intervals, instead of keeping the overlap-check.- added an additional cleanup patch.
Hi,
I'm sending this series again in this format as the interval tree node conversion will, at a minimum, take longer than hoped for (ie: Jason still removing interval tree users for the
mmu_notifierrework[1]). There is also a chance this will never see be done.As such, I'm resending this series (where patch 1 is the only interesting one and which Ingo acked previously, with the exception that the nodes remain fully closed). In the future, it would be trivial to port pat tree to semi open nodes, but for now think that it makes sense to just get the pat changes in.
Please consider for v5.5. Thanks!
[0] https://lore.kernel.org/lkml/[email protected]/
[1] https://marc.info/?l=linux-mm&m=157116340411211Davidlohr Bueso (4):
x86/mm, pat: Convert pat tree to generic interval tree x86/mm, pat: Cleanup some of the local memtype_rb_* calls x86/mm, pat: Drop rbt prefix from external memtype calls x86/mm, pat: Renamepat_rbtree.ctopat_interval.c
Quoted 8 lines
arch/x86/mm/Makefile | 2 +- arch/x86/mm/pat.c | 8 +- arch/x86/mm/pat_internal.h | 20 ++-- arch/x86/mm/pat_interval.c | 185 +++++++++++++++++++++++++++++++ arch/x86/mm/pat_rbtree.c | 268 --------------------------------------------- 5 files changed, 200 insertions(+), 283 deletions(-) create mode 100644 arch/x86/mm/pat_interval.c delete mode 100644 arch/x86/mm/pat_rbtree.c
Thanks Davidlohr - this is a really nice cleanup of the logic and of the tree data structure, and I've applied your earlier series to tip:WIP.x86/mm already, with a few more work-in-progress patches from me on top that tidy up this area of the code.
In particular I've done a bunch of changes to improve the hackability of all pat/memtype/set_memory facilities, we've now got <asm/memtype.h>, memtype.[ch], memtype_interval.c and set_memory.c in arch/x86/mm/pat/:
dagon:~/tip> ls -l arch/x86/mm/pat/
total 112
-rw-r--r-- 1 mingo mingo 5782 Nov 21 06:41 cpa-test.c
-rw-r--r-- 1 mingo mingo 117 Nov 21 06:41 Makefile
-rw-r--r-- 1 mingo mingo 32026 Nov 21 06:41 memtype.c -rw-r--r-- 1 mingo mingo 1470 Nov 21 06:41 memtype.h -rw-r--r-- 1 mingo mingo 5003 Nov 21 06:41 memtype_interval.c -rw-r--r-- 1 mingo mingo 56668 Nov 21 06:41 set_memory.c
( Note: cpa-test.c should probable be renamed to set_memory_test.c, with
a few explicit set_memory() API tests added as well, not just the internal change_page_attribute() tests. Will do this later. )
The memtype APIs are (rightside column):
reserve_memtype() => memtype_reserve()
free_memtype() => memtype_free()
kernel_map_sync_memtype() => memtype_kernel_map_sync()
io_reserve_memtype() => memtype_reserve_io()
io_free_memtype() => memtype_free_io() memtype_check_insert() => memtype_check_insert()
memtype_erase() => memtype_erase()
memtype_lookup() => memtype_lookup()
memtype_copy_nth_element() => memtype_copy_nth_element()But there's a lot more changes:
218bf1a8c73b: x86/mm/pat: Convert the PAT tree to a generic interval tree 3309be371c20: x86/mm/pat: Clean up some of the local memtype_rb_*() calls
b40805c214c5: x86/mm/pat: Drop the rbt_ prefix from external memtype function names
ee4e7b04b718: x86/mm/pat: Rename pat_rbtree.c to pat_interval.c
8afed68b3426: x86/mm/pat: Update the comments in pat.c and pat_interval.c and refresh the code a bit
bc8a3eed1241: x86/mm/pat: Disambiguate PAT-disabled boot messages
10ffd914266a: x86/mm/pat: Create fixed width output in /sys/kernel/debug/x86/pat_memtype_list, similar to the E820 debug printouts 37dfd5d60000: x86/mm/pat: Simplify the free_memtype() control flow
b686cd38771d: x86/mm/pat: Harmonize 'struct memtype *' local variable and function parameter use 7fa6ebcdfb73: x86/mm/pat: Clean up PAT initialization flags
a224f826be60: x86/mm/pat: Move the memtype related files to arch/x86/mm/pat/
acb2f580640a: x86/mm/pat: Standardize on memtype_*() prefix for APIs
393cac16e6b7: x86/mm/pat: Rename <asm/pat.h> => <asm/memtype.h>
22a6d30c44c7: x86/mm/pat: Clean up <asm/memtype.h> externs
56ca0be07c28: x86/mm/pat: Fix typo in the Kconfig help text
07fbea7b3be2: x86/mm: Tabulate the page table encoding definitions
I'll send them out separately as well once completed, but wanted to give you a heads-up. My patches are in WIP state because neither the changelogs nor the split-up is necessarily final.
These can all be accessed and followed under:
git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git WIP.x86/mm
What do you think about these changes? Anything else you'd like to see happen?
In terms of upstreaming plans, the 4 commits from you I grouped separately definitely look like v5.5 material to me - will merge them into tip:x86/mm later today.
Thanks,
Ingo