x86/pat changes for v2.6.34
Subsystems (4)
Linus,
Please pull the latest x86-pat-for-linus git tree from:
git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip.git x86-pat-for-linus
Please have a look at the lib/rbtree.c changes. The rebalancing changes ought to not impact performance - rb_erase() possibly in a small way. Should this perhaps be done via a separate API entry, instead of modifying existing rbtree code?
out-of-topic modifications in x86-pat-for-linus:
------------------------------------------------include/linux/rbtree.h # 17d9ddc: rbtree: Add support for augmentedlib/rbtree.c # 17d9ddc: rbtree: Add support for augmented
Thanks,
Ingo
------------------>
Pallipadi, Venkatesh (2):
rbtree: Add support for augmented rbtrees
x86, pat: Migrate to rbtree only backend for pat memtype management
[email protected] (1):
x86, pat: Preparatory changes in pat.c for bigger rbtree change
Documentation/rbtree.txt | 58 ++++++++++ arch/x86/mm/Makefile | 1 + arch/x86/mm/pat.c | 231 +++---------------------------------- arch/x86/mm/pat_internal.h | 46 ++++++++ arch/x86/mm/pat_rbtree.c | 271 ++++++++++++++++++++++++++++++++++++++++++++ include/linux/rbtree.h | 5 +- lib/rbtree.c | 48 +++++++- 7 files changed, 443 insertions(+), 217 deletions(-) create mode 100644 arch/x86/mm/pat_internal.h create mode 100644 arch/x86/mm/pat_rbtree.c
Documentation/rbtree.txt +58 -0
@@ -190,3 +190,61 @@ Example: for (node = rb_first(&mytree); node; node = rb_next(node)) printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring); +Support for Augmented rbtrees +----------------------------- + +Augmented rbtree is an rbtree with "some" additional data stored in each node. +This data can be used to augment some new functionality to rbtree. +Augmented rbtree is an optional feature built on top of basic rbtree +infrastructure. rbtree user who wants this feature will have an augment +callback function in rb_root initialized. + +This callback function will be called from rbtree core routines whenever +a node has a change in one or both of its children. It is the responsibility +of the callback function to recalculate the additional data that is in the +rb node using new children information. Note that if this new additional +data affects the parent node's additional data, then callback function has +to handle it and do the recursive updates. + + +Interval tree is an example of augmented rb tree. Reference - +"Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. +More details about interval trees: + +Classical rbtree has a single key and it cannot be directly used to store +interval ranges like [lo:hi] and do a quick lookup for any overlap with a new +lo:hi or to find whether there is an exact match for a new lo:hi. + +However, rbtree can be augmented to store such interval ranges in a structured +way making it possible to do efficient lookup and exact match. + +This "extra information" stored in each node is the maximum hi +(max_hi) value among all the nodes that are its descendents. This +information can be maintained at each node just be looking at the node +and its immediate children. And this will be used in O(log n) lookup +for lowest match (lowest start address among all possible matches) +with something like: + +find_lowest_match(lo, hi, node) +{ + lowest_match = NULL; + while (node) { + if (max_hi(node->left) > lo) { + // Lowest overlap if any must be on left side + node = node->left; + } else if (overlap(lo, hi, node)) { + lowest_match = node; + break; + } else if (lo > node->lo) { + // Lowest overlap if any must be on right side + node = node->right; + } else { + break; + } + } + return lowest_match; +} + +Finding exact match will be to first find lowest match and then to follow +successor nodes looking for exact match, until the start of a node is beyond +the hi value we are looking for.
arch/x86/mm/Makefile +1 -0
@@ -6,6 +6,7 @@ nostackp := $(call cc-option, -fno-stack-protector) CFLAGS_physaddr.o := $(nostackp) CFLAGS_setup_nx.o := $(nostackp) +obj-$(CONFIG_X86_PAT) += pat_rbtree.o obj-$(CONFIG_SMP) += tlb.o obj-$(CONFIG_X86_32) += pgtable_32.o iomap_32.o
arch/x86/mm/pat.c +19 -212
314 lines not on this page · raw message
arch/x86/mm/pat_internal.h new file +46 -0
46 lines not on this page · raw message
arch/x86/mm/pat_rbtree.c new file +271 -0
271 lines not on this page · raw message
include/linux/rbtree.h +4 -1
@@ -110,6 +110,7 @@ struct rb_nodestruct rb_root {struct rb_node *rb_node; +void (*augment_cb)(struct rb_node *node); };
@@ -129,7 +130,9 @@ static inline void rb_set_color(struct rb_node *rb, int color) rb->rb_parent_color = (rb->rb_parent_color & ~1 ) | color; } -#define RB_ROOT (struct rb_root) { NULL, } +#define RB_ROOT (struct rb_root) { NULL, NULL, } +#define RB_AUGMENT_ROOT (x) (struct rb_root) { NULL, x} +#define rb_entry (ptr, type, member) container_of(ptr, type, member)#define RB_EMPTY_ROOT (root) ((root)->rb_node == NULL)
lib/rbtree.c +44 -4
103 lines not on this page · raw message
Quoted 20 lines · Ingo Molnar
Linus,
Please pull the latest x86-pat-for-linus git tree from:
git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip.git x86-pat-for-linusPlease have a look at the
lib/rbtree.cchanges. The rebalancing changes ought to not impact performance -rb_erase()possibly in a small way. Should this perhaps be done via a separate API entry, instead of modifying existing rbtree code?out-of-topic modifications in x86-pat-for-linus:
------------------------------------------------include/linux/rbtree.h# 17d9ddc: rbtree: Add support for augmentedlib/rbtree.c# 17d9ddc: rbtree: Add support for augmentedThanks,
Ingo
Quoted 7 lines
------------------>
Pallipadi, Venkatesh (2):
rbtree: Add support for augmented rbtrees
x86, pat: Migrate to rbtree only backend for pat memtype management[email protected] (1):
x86, pat: Preparatory changes inpat.cfor bigger rbtree change
There are few dependencies with this patchset.
These patches should go in before "Add support for augmented rbtrees":
"btrfs: use RB_ROOT to intialize rb_trees instead of settingrb_node to NULL"
http://lkml.indiana.edu/hypermail/linux/kernel/1002.2/02946.html
"[patch 0/3] Fixup rb_root initializations to use RB_ROOT"
http://lkml.indiana.edu/hypermail/linux/kernel/1002.2/03037.html
And this is an x86 bug fix on top of "Migrate to rbtree only backend for pat memtype management"
http://lkml.indiana.edu/hypermail/linux/kernel/1002.3/00346.html
Thanks,
Venki
H. Peter Anvin
reviewerQuoted 23 lines · Venkatesh
Quoted 11 lines · Ingo Molnar
Linus,
Please pull the latest x86-pat-for-linus git tree from:
git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-2.6-tip.git x86-pat-for-linusPlease have a look at the
lib/rbtree.cchanges. The rebalancing changes ought to not impact performance -rb_erase()possibly in a small way. Should this perhaps be done via a separate API entry, instead of modifying existing rbtree code?Quoted 5 lines
out-of-topic modifications in x86-pat-for-linus:
------------------------------------------------include/linux/rbtree.h# 17d9ddc: rbtree: Add support for augmentedlib/rbtree.c# 17d9ddc: rbtree: Add support for augmentedThese patches should go in before "Add support for augmented rbtrees":
"btrfs: use
RB_ROOTto intializerb_treesinstead ofsettingrb_nodeto NULL"
http://lkml.indiana.edu/hypermail/linux/kernel/1002.2/02946.html
Quoted 9 lines
"[patch 0/3] Fixup
rb_rootinitializations to useRB_ROOT"
http://lkml.indiana.edu/hypermail/linux/kernel/1002.2/03037.htmlAnd this is an x86 bug fix on top of "Migrate to rbtree only backend for pat memtype management"
http://lkml.indiana.edu/hypermail/linux/kernel/1002.3/00346.html
I have added that the latter patch to tip:x86/pat; Ingo should hopefully run it through his test machine overnight and bump x86-pat-for-linus.
I feel a bit uncomfortable with the btrfs patches just because they're out of my area, but I'm Cc:ing Chris to let him either take the patches or tell me to shut up and just do it ;)
-hpa