4 files changed, 296 insertions, 205 deletions

diff --git a/arch/x86/mm/Makefile b/arch/x86/mm/Makefile
index 06630d26e56d..a4c768397baa 100644
--- a/arch/x86/mm/Makefile
+++ b/arch/x86/mm/Makefile
@@ -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
diff --git a/arch/x86/mm/pat.c b/arch/x86/mm/pat.c
index 628e507b7936..951011166ef5 100644
--- a/arch/x86/mm/pat.c
+++ b/arch/x86/mm/pat.c
@@ -130,65 +130,7 @@ void pat_init(void)
 
 #undef PAT
 
-/*
- * The global memtype list keeps track of memory type for specific
- * physical memory areas. Conflicting memory types in different
- * mappings can cause CPU cache corruption. To avoid this we keep track.
- *
- * The list is sorted based on starting address and can contain multiple
- * entries for each address (this allows reference counting for overlapping
- * areas). All the aliases have the same cache attributes of course.
- * Zero attributes are represented as holes.
- *
- * The data structure is a list that is also organized as an rbtree
- * sorted on the start address of memtype range.
- *
- * memtype_lock protects both the linear list and rbtree.
- */
-
-static struct rb_root memtype_rbroot = RB_ROOT;
-static LIST_HEAD(memtype_list);
-static DEFINE_SPINLOCK(memtype_lock);   /* protects memtype list */
-
-static struct memtype *memtype_rb_search(struct rb_root *root, u64 start)
-{
-        struct rb_node *node = root->rb_node;
-        struct memtype *last_lower = NULL;
-
-        while (node) {
-                struct memtype *data = container_of(node, struct memtype, rb);
-
-                if (data->start < start) {
-                        last_lower = data;
-                        node = node->rb_right;
-                } else if (data->start > start) {
-                        node = node->rb_left;
-                } else
-                        return data;
-        }
-
-        /* Will return NULL if there is no entry with its start <= start */
-        return last_lower;
-}
-
-static void memtype_rb_insert(struct rb_root *root, struct memtype *data)
-{
-        struct rb_node **new = &(root->rb_node);
-        struct rb_node *parent = NULL;
-
-        while (*new) {
-                struct memtype *this = container_of(*new, struct memtype, rb);
-
-                parent = *new;
-                if (data->start <= this->start)
-                        new = &((*new)->rb_left);
-                else if (data->start > this->start)
-                        new = &((*new)->rb_right);
-        }
-
-        rb_link_node(&data->rb, parent, new);
-        rb_insert_color(&data->rb, root);
-}
+static DEFINE_SPINLOCK(memtype_lock);   /* protects memtype accesses */
 
 /*
  * Does intersection of PAT memory type and MTRR memory type and returns
@@ -216,33 +158,6 @@ static unsigned long pat_x_mtrr_type(u64 start, u64 end, unsigned long req_type)
         return req_type;
 }
 
-static int
-chk_conflict(struct memtype *new, struct memtype *entry, unsigned long *type)
-{
-        if (new->type != entry->type) {
-                if (type) {
-                        new->type = entry->type;
-                        *type = entry->type;
-                } else
-                        goto conflict;
-        }
-
-         /* check overlaps with more than one entry in the list */
-        list_for_each_entry_continue(entry, &memtype_list, nd) {
-                if (new->end <= entry->start)
-                        break;
-                else if (new->type != entry->type)
-                        goto conflict;
-        }
-        return 0;
-
- conflict:
-        printk(KERN_INFO "%s:%d conflicting memory types "
-               "%Lx-%Lx %s<->%s\n", current->comm, current->pid, new->start,
-               new->end, cattr_name(new->type), cattr_name(entry->type));
-        return -EBUSY;
-}
-
 static int pat_pagerange_is_ram(unsigned long start, unsigned long end)
 {
         int ram_page = 0, not_rampage = 0;
@@ -328,64 +243,6 @@ static int free_ram_pages_type(u64 start, u64 end)
         return 0;
 }
 
-static int memtype_check_insert(struct memtype *new, unsigned long *new_type)
-{
-        struct memtype *entry;
-        u64 start, end;
-        unsigned long actual_type;
-        struct list_head *where;
-        int err = 0;
-
-        start = new->start;
-        end = new->end;
-        actual_type = new->type;
-
-        /* Search for existing mapping that overlaps the current range */
-        where = NULL;
-        list_for_each_entry(entry, &memtype_list, nd) {
-                if (end <= entry->start) {
-                        where = entry->nd.prev;
-                        break;
-                } else if (start <= entry->start) { /* end > entry->start */
-                        err = chk_conflict(new, entry, new_type);
-                        if (!err) {
-                                dprintk("Overlap at 0x%Lx-0x%Lx\n",
-                                        entry->start, entry->end);
-                                where = entry->nd.prev;
-                        }
-                        break;
-                } else if (start < entry->end) { /* start > entry->start */
-                        err = chk_conflict(new, entry, new_type);
-                        if (!err) {
-                                dprintk("Overlap at 0x%Lx-0x%Lx\n",
-                                        entry->start, entry->end);
-
-                                /*
-                                 * Move to right position in the linked
-                                 * list to add this new entry
-                                 */
-                                list_for_each_entry_continue(entry,
-                                                        &memtype_list, nd) {
-                                        if (start <= entry->start) {
-                                                where = entry->nd.prev;
-                                                break;
-                                        }
-                                }
-                        }
-                        break;
-                }
-        }
-        if (!err) {
-                if (where)
-                        list_add(&new->nd, where);
-                else
-                        list_add_tail(&new->nd, &memtype_list);
-
-                memtype_rb_insert(&memtype_rbroot, new);
-        }
-        return err;
-}
-
 /*
  * req_type typically has one of the:
  * - _PAGE_CACHE_WB
@@ -459,7 +316,7 @@ int reserve_memtype(u64 start, u64 end, unsigned long req_type,
 
         spin_lock(&memtype_lock);
 
-        err = memtype_check_insert(new, new_type);
+        err = rbt_memtype_check_insert(new, new_type);
         if (err) {
                 printk(KERN_INFO "reserve_memtype failed 0x%Lx-0x%Lx, "
                        "track %s, req %s\n",
@@ -481,7 +338,6 @@ int reserve_memtype(u64 start, u64 end, unsigned long req_type,
 
 int free_memtype(u64 start, u64 end)
 {
-        struct memtype *entry, *saved_entry;
         int err = -EINVAL;
         int is_range_ram;
 
@@ -505,46 +361,7 @@ int free_memtype(u64 start, u64 end)
         }
 
         spin_lock(&memtype_lock);
-
-        entry = memtype_rb_search(&memtype_rbroot, start);
-        if (unlikely(entry == NULL))
-                goto unlock_ret;
-
+        err = rbt_memtype_erase(start, end);