* [PATCH 1/3] vmalloc: Add __vmalloc_node_try_addr function
2018-07-07 0:35 [PATCH RFC V2 0/3] KASLR feature to randomize each loadable module Rick Edgecombe
@ 2018-07-07 0:35 ` Rick Edgecombe
2018-07-07 0:35 ` [PATCH 2/3] x86/modules: Increase randomization for modules Rick Edgecombe
2018-07-07 0:35 ` [PATCH 3/3] vmalloc: Add debugfs modfraginfo Rick Edgecombe
2 siblings, 0 replies; 5+ messages in thread
From: Rick Edgecombe @ 2018-07-07 0:35 UTC (permalink / raw)
To: tglx, mingo, hpa, x86, linux-kernel, linux-mm, kernel-hardening
Cc: kristen, dave.hansen, arjan, Rick Edgecombe
Create __vmalloc_node_try_addr function that tries to allocate at a specific
address and supports caller specified behavior for whether any lazy purging
happens if there is a collision.
Signed-off-by: Rick Edgecombe <rick.p.edgecombe@intel.com>
---
include/linux/vmalloc.h | 3 +
mm/vmalloc.c | 174 ++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 177 insertions(+)
diff --git a/include/linux/vmalloc.h b/include/linux/vmalloc.h
index 398e9c9..c7712c8 100644
--- a/include/linux/vmalloc.h
+++ b/include/linux/vmalloc.h
@@ -82,6 +82,9 @@ extern void *__vmalloc_node_range(unsigned long size, unsigned long align,
unsigned long start, unsigned long end, gfp_t gfp_mask,
pgprot_t prot, unsigned long vm_flags, int node,
const void *caller);
+extern void *__vmalloc_node_try_addr(unsigned long addr, unsigned long size,
+ gfp_t gfp_mask, pgprot_t prot, unsigned long vm_flags,
+ int node, int try_purge, const void *caller);
#ifndef CONFIG_MMU
extern void *__vmalloc_node_flags(unsigned long size, int node, gfp_t flags);
static inline void *__vmalloc_node_flags_caller(unsigned long size, int node,
diff --git a/mm/vmalloc.c b/mm/vmalloc.c
index cfea25b..b6f2449 100644
--- a/mm/vmalloc.c
+++ b/mm/vmalloc.c
@@ -1710,6 +1710,180 @@ static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
}
/**
+ * __vmalloc_try_addr - try to alloc at a specific address
+ * @addr: address to try
+ * @size: size to try
+ * @gfp_mask: flags for the page level allocator
+ * @prot: protection mask for the allocated pages
+ * @vm_flags: additional vm area flags (e.g. %VM_NO_GUARD)
+ * @node: node to use for allocation or NUMA_NO_NODE
+ * @try_purge: try to purge if needed to fulfill and allocation
+ * @caller: caller's return address
+ *
+ * Try to allocate at the specific address. If it succeeds the address is
+ * returned. If it fails NULL is returned. If try_purge is zero, it will
+ * return an EBUSY ERR_PTR if it could have allocated if it was allowed to
+ * purge. It may trigger TLB flushes if a purge is needed, and try_purge is
+ * set.
+ */
+void *__vmalloc_node_try_addr(unsigned long addr, unsigned long size,
+ gfp_t gfp_mask, pgprot_t prot, unsigned long vm_flags,
+ int node, int try_purge, const void *caller)
+{
+ struct vmap_area *va;
+ struct vm_struct *area;
+ struct rb_node *n;
+ struct vmap_area *cur_va = NULL;
+ struct vmap_area *first_before = NULL;
+
+ int not_at_end = 0;
+ int need_purge = 0;
+ int blocked = 0;
+ int purged = 0;
+
+ unsigned long real_size = size;
+ unsigned long addr_end;
+
+ size = PAGE_ALIGN(size);
+ if (!size || (size >> PAGE_SHIFT) > totalram_pages)
+ return NULL;
+
+ WARN_ON(in_interrupt());
+
+ va = kmalloc_node(sizeof(struct vmap_area),
+ gfp_mask & GFP_RECLAIM_MASK, node);
+ if (unlikely(!va)) {
+ warn_alloc(gfp_mask, NULL,
+ "kmalloc: allocation failure");
+ return NULL;
+ }
+
+ area = kzalloc_node(sizeof(*area), gfp_mask & GFP_RECLAIM_MASK, node);
+ if (unlikely(!area)) {
+ warn_alloc(gfp_mask, NULL,
+ "kmalloc: allocation failure");
+ goto failva;
+ }
+ /*
+ * Only scan the relevant parts containing pointers to other objects
+ * to avoid false negatives.
+ */
+ kmemleak_scan_area(&va->rb_node, SIZE_MAX, gfp_mask & GFP_RECLAIM_MASK);
+
+ if (!(vm_flags & VM_NO_GUARD))
+ size += PAGE_SIZE;
+
+ addr_end = addr + size;
+ if (addr > addr_end)
+ return NULL;
+
+retry:
+ spin_lock(&vmap_area_lock);
+
+ n = vmap_area_root.rb_node;
+ while (n) {
+ cur_va = rb_entry(n, struct vmap_area, rb_node);
+ if (addr < cur_va->va_end) {
+ not_at_end = 1;
+ if (cur_va->va_start == addr) {
+ first_before = cur_va;
+ break;
+ }
+ n = n->rb_left;
+ } else {
+ first_before = cur_va;
+ n = n->rb_right;
+ }
+ }
+
+ /*
+ * Linearly search through to make sure there is a hole, unless we are
+ * at the end of the VA list.
+ */
+ if (not_at_end) {
+ /*
+ * If there is no VA that starts before the
+ * target address, start the check from the closest VA.
+ */
+ if (first_before)
+ cur_va = first_before;
+
+ while (cur_va->va_start < addr_end) {
+ if (cur_va->va_end > addr) {
+ if (cur_va->flags & VM_LAZY_FREE) {
+ need_purge = 1;
+ } else {
+ blocked = 1;
+ break;
+ }
+ }
+
+ if (list_is_last(&cur_va->list, &vmap_area_list))
+ break;
+
+ cur_va = list_next_entry(cur_va, list);
+ }
+
+ if (blocked || (!try_purge && need_purge)) {
+ /*
+ * If a non-lazy free va blocks the allocation, or
+ * we are not supposed to purge, but we need to the
+ * allocation fails.
+ */
+ goto fail;
+ }
+ if (try_purge && need_purge) {
+ if (purged) {
+ /* if purged once before, give up */
+ goto fail;
+ } else {
+ /*
+ * If the va blocking the allocation is set to
+ * be purged then purge all vmap_areas that are
+ * set to purged since this will flush the TLBs
+ * anyway.
+ */
+ spin_unlock(&vmap_area_lock);
+ purge_vmap_area_lazy();
+ need_purge = 0;
+ purged = 1;
+ goto retry;
+ }
+ }
+ }
+
+ va->va_start = addr;
+ va->va_end = addr_end;
+ va->flags = 0;
+ __insert_vmap_area(va);
+
+ spin_unlock(&vmap_area_lock);
+
+ setup_vmalloc_vm(area, va, vm_flags, caller);
+
+ addr = (unsigned long)__vmalloc_area_node(area, gfp_mask, prot, node);
+ if (!addr) {
+ warn_alloc(gfp_mask, NULL,
+ "vmalloc: allocation failure: %lu bytes", real_size);
+ return NULL;
+ }
+
+ clear_vm_uninitialized_flag(area);
+
+ kmemleak_vmalloc(area, size, gfp_mask);
+
+ return (void *)addr;
+fail:
+ kfree(area);
+ spin_unlock(&vmap_area_lock);
+failva:
+ kfree(va);
+ if (need_purge && !blocked)
+ return ERR_PTR(-EBUSY);
+ return NULL;
+}
+
+/**
* __vmalloc_node_range - allocate virtually contiguous memory
* @size: allocation size
* @align: desired alignment
--
2.7.4
^ permalink raw reply [flat|nested] 5+ messages in thread* [PATCH 2/3] x86/modules: Increase randomization for modules
2018-07-07 0:35 [PATCH RFC V2 0/3] KASLR feature to randomize each loadable module Rick Edgecombe
2018-07-07 0:35 ` [PATCH 1/3] vmalloc: Add __vmalloc_node_try_addr function Rick Edgecombe
@ 2018-07-07 0:35 ` Rick Edgecombe
2018-07-07 0:35 ` [PATCH 3/3] vmalloc: Add debugfs modfraginfo Rick Edgecombe
2 siblings, 0 replies; 5+ messages in thread
From: Rick Edgecombe @ 2018-07-07 0:35 UTC (permalink / raw)
To: tglx, mingo, hpa, x86, linux-kernel, linux-mm, kernel-hardening
Cc: kristen, dave.hansen, arjan, Rick Edgecombe
This changes the behavior of the KASLR logic for allocating memory for the text
sections of loadable modules. It randomizes the location of each module text
section with about 17 bits of entropy in typical use. This is enabled on X86_64
only. For 32 bit, the behavior is unchanged.
The algorithm evenly breaks the module space in two, a random area and a backup
area. For module text allocations, it first tries to allocate at a number of
randomly located starting pages inside the random section. If this fails, it
will allocate in the backup area. The backup area base will be offset in the
same way as the current algorithm does for the base area, 1024 possible
locations.
Signed-off-by: Rick Edgecombe <rick.p.edgecombe@intel.com>
---
arch/x86/include/asm/pgtable_64_types.h | 1 +
arch/x86/kernel/module.c | 103 ++++++++++++++++++++++++++++++--
2 files changed, 98 insertions(+), 6 deletions(-)
diff --git a/arch/x86/include/asm/pgtable_64_types.h b/arch/x86/include/asm/pgtable_64_types.h
index 054765a..56452a0 100644
--- a/arch/x86/include/asm/pgtable_64_types.h
+++ b/arch/x86/include/asm/pgtable_64_types.h
@@ -141,6 +141,7 @@ extern unsigned int ptrs_per_p4d;
/* The module sections ends with the start of the fixmap */
#define MODULES_END _AC(0xffffffffff000000, UL)
#define MODULES_LEN (MODULES_END - MODULES_VADDR)
+#define MODULES_RAND_LEN PAGE_ALIGN((MODULES_LEN/3)*2)
#define ESPFIX_PGD_ENTRY _AC(-2, UL)
#define ESPFIX_BASE_ADDR (ESPFIX_PGD_ENTRY << P4D_SHIFT)
diff --git a/arch/x86/kernel/module.c b/arch/x86/kernel/module.c
index f58336a..4ffff9f 100644
--- a/arch/x86/kernel/module.c
+++ b/arch/x86/kernel/module.c
@@ -77,6 +77,93 @@ static unsigned long int get_module_load_offset(void)
}
#endif
+static unsigned long get_module_area_base(void)
+{
+ return MODULES_VADDR + get_module_load_offset();
+}
+
+#if defined(CONFIG_X86_64) && defined(CONFIG_RANDOMIZE_BASE)
+static unsigned long get_module_vmalloc_start(void)
+{
+ if (kaslr_enabled())
+ return MODULES_VADDR + MODULES_RAND_LEN
+ + get_module_load_offset();
+ else
+ return get_module_area_base();
+}
+
+static void *try_module_alloc(unsigned long addr, unsigned long size,
+ int try_purge)
+{
+ return __vmalloc_node_try_addr(addr, size, GFP_KERNEL,
+ PAGE_KERNEL_EXEC, 0,
+ NUMA_NO_NODE, try_purge,
+ __builtin_return_address(0));
+}
+
+/*
+ * Try to allocate in the random area. First 5000 times without purging, then
+ * 5000 times with purging. If these fail, return NULL.
+ */
+static void *try_module_randomize_each(unsigned long size)
+{
+ void *p = NULL;
+ unsigned int i;
+ unsigned long offset;
+ unsigned long addr;
+ unsigned long end;
+ unsigned long last_lazy_free_blocked = 0;
+ const unsigned long nr_mod_positions = MODULES_RAND_LEN / MODULE_ALIGN;
+ const unsigned long nr_try_purge = 5000;
+ const unsigned long nr_no_purge = 5000;
+
+ if (!kaslr_enabled())
+ return NULL;
+
+ for (i = 0; i < nr_try_purge + nr_no_purge; i++) {
+ offset = (get_random_long() % nr_mod_positions) * MODULE_ALIGN;
+ addr = (unsigned long)MODULES_VADDR + offset;
+ end = addr + size;
+
+ if (end > addr && end < MODULES_END) {
+ if (i < nr_no_purge) {
+ /* First try to avoid having to purge */
+ p = try_module_alloc(addr, size, 0);
+
+ /*
+ * Save the last value that was blocked by a
+ * lazy purge area
+ */
+ if (IS_ERR(p) && PTR_ERR(p) == -EBUSY)
+ last_lazy_free_blocked = addr;
+ else if (p && !IS_ERR(p))
+ return p;
+ } else {
+ /* Give up and allow for purges */
+ if (i == nr_try_purge && last_lazy_free_blocked)
+ addr = last_lazy_free_blocked;
+
+ p = try_module_alloc(addr, size, 1);
+
+ if (p)
+ return p;
+ }
+ }
+ }
+ return NULL;
+}
+#else
+static unsigned long get_module_vmalloc_start(void)
+{
+ return get_module_area_base();
+}
+
+static void *try_module_randomize_each(unsigned long size)
+{
+ return NULL;
+}
+#endif
+
void *module_alloc(unsigned long size)
{
void *p;
@@ -84,16 +171,20 @@ void *module_alloc(unsigned long size)
if (PAGE_ALIGN(size) > MODULES_LEN)
return NULL;
- p = __vmalloc_node_range(size, MODULE_ALIGN,
- MODULES_VADDR + get_module_load_offset(),
- MODULES_END, GFP_KERNEL,
- PAGE_KERNEL_EXEC, 0, NUMA_NO_NODE,
- __builtin_return_address(0));
+ p = try_module_randomize_each(size);
+
+ if (!p)
+ p = __vmalloc_node_range(size, MODULE_ALIGN,
+ get_module_vmalloc_start(),
+ MODULES_END, GFP_KERNEL,
+ PAGE_KERNEL_EXEC, 0,
+ NUMA_NO_NODE,
+ __builtin_return_address(0));
+
if (p && (kasan_module_alloc(p, size) < 0)) {
vfree(p);
return NULL;
}
-
return p;
}
--
2.7.4
^ permalink raw reply [flat|nested] 5+ messages in thread* [PATCH 3/3] vmalloc: Add debugfs modfraginfo
2018-07-07 0:35 [PATCH RFC V2 0/3] KASLR feature to randomize each loadable module Rick Edgecombe
2018-07-07 0:35 ` [PATCH 1/3] vmalloc: Add __vmalloc_node_try_addr function Rick Edgecombe
2018-07-07 0:35 ` [PATCH 2/3] x86/modules: Increase randomization for modules Rick Edgecombe
@ 2018-07-07 0:35 ` Rick Edgecombe
2018-07-19 5:24 ` kbuild test robot
2 siblings, 1 reply; 5+ messages in thread
From: Rick Edgecombe @ 2018-07-07 0:35 UTC (permalink / raw)
To: tglx, mingo, hpa, x86, linux-kernel, linux-mm, kernel-hardening
Cc: kristen, dave.hansen, arjan, Rick Edgecombe
Add debugfs file "modfraginfo" for providing info on module space
fragmentation. This can be used for determining if loadable module
randomization is causing any problems for extreme module loading situations,
like huge numbers of modules or extremely large modules.
Sample output when RANDOMIZE_BASE and X86_64 is configured:
Largest free space: 847253504
External Memory Fragementation: 20%
Allocations in backup area: 0
Sample output when just X86_64:
Largest free space: 847253504
External Memory Fragementation: 20%
Signed-off-by: Rick Edgecombe <rick.p.edgecombe@intel.com>
---
mm/vmalloc.c | 101 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 100 insertions(+), 1 deletion(-)
diff --git a/mm/vmalloc.c b/mm/vmalloc.c
index b6f2449..85441f2 100644
--- a/mm/vmalloc.c
+++ b/mm/vmalloc.c
@@ -18,6 +18,7 @@
#include <linux/interrupt.h>
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
+#include <linux/debugfs.h>
#include <linux/debugobjects.h>
#include <linux/kallsyms.h>
#include <linux/list.h>
@@ -33,6 +34,7 @@
#include <linux/bitops.h>
#include <linux/uaccess.h>
+#include <asm/setup.h>
#include <asm/tlbflush.h>
#include <asm/shmparam.h>
@@ -2922,7 +2924,104 @@ static int __init proc_vmalloc_init(void)
proc_create_seq("vmallocinfo", 0400, NULL, &vmalloc_op);
return 0;
}
-module_init(proc_vmalloc_init);
+#else
+static int proc_vmalloc_init(void)
+{
+ return 0;
+}
+#endif
+#if defined(CONFIG_DEBUG_FS) && defined(CONFIG_X86_64)
+#if defined(CONFIG_RANDOMIZE_BASE)
+static void print_backup_area(struct seq_file *m, unsigned long backup_cnt)
+{
+ if (kaslr_enabled())
+ seq_printf(m, "Allocations in backup area:\t%lu\n", backup_cnt);
+}
+#else
+static void print_backup_area(struct seq_file *m, unsigned long backup_cnt)
+{
+}
#endif
+static int modulefraginfo_debug_show(struct seq_file *m, void *v)
+{
+ struct list_head *i;
+ unsigned long last_end = MODULES_VADDR;
+ unsigned long total_free = 0;
+ unsigned long largest_free = 0;
+ unsigned long backup_cnt = 0;
+ unsigned long gap;
+
+ spin_lock(&vmap_area_lock);
+
+ list_for_each(i, &vmap_area_list) {
+ struct vmap_area *obj = list_entry(i, struct vmap_area, list);
+
+ if (!(obj->flags & VM_LAZY_FREE)
+ && obj->va_start >= MODULES_VADDR
+ && obj->va_end <= MODULES_END) {
+
+ if (obj->va_start >= MODULES_VADDR + MODULES_RAND_LEN)
+ backup_cnt++;
+
+ gap = (obj->va_start - last_end);
+ if (gap > largest_free)
+ largest_free = gap;
+ total_free += gap;
+
+ last_end = obj->va_end;
+ }
+ }
+
+ gap = (MODULES_END - last_end);
+ if (gap > largest_free)
+ largest_free = gap;
+ total_free += gap;
+
+ spin_unlock(&vmap_area_lock);
+ seq_printf(m, "Largest free space:\t\t%lu\n", largest_free);
+ if (total_free)
+ seq_printf(m, "External Memory Fragmentation:\t%lu%%\n",
+ 100-(100*largest_free/total_free));
+ else
+ seq_puts(m, "External Memory Fragmentation:\t0%%\n");
+
+ print_backup_area(m, backup_cnt);
+
+ return 0;
+}
+
+static int proc_module_frag_debug_open(struct inode *inode, struct file *file)
+{
+ return single_open(file, modulefraginfo_debug_show, NULL);
+}
+
+static const struct file_operations debug_module_frag_operations = {
+ .open = proc_module_frag_debug_open,
+ .read = seq_read,
+ .llseek = seq_lseek,
+ .release = single_release,
+};
+
+static void debug_modfrag_init(void)
+{
+ debugfs_create_file("modfraginfo", 0400, NULL, NULL,
+ &debug_module_frag_operations);
+}
+#else /* defined(CONFIG_DEBUG_FS) && defined(CONFIG_X86_64) */
+static void debug_modfrag_init(void)
+{
+}
+#endif
+
+#if defined(CONFIG_DEBUG_FS) || defined(CONFIG_PROC_FS)
+static int __init info_vmalloc_init(void)
+{
+ proc_vmalloc_init();
+ debug_modfrag_init();
+ return 0;
+}
+
+module_init(info_vmalloc_init);
+#endif
--
2.7.4
^ permalink raw reply [flat|nested] 5+ messages in thread* Re: [PATCH 3/3] vmalloc: Add debugfs modfraginfo
2018-07-07 0:35 ` [PATCH 3/3] vmalloc: Add debugfs modfraginfo Rick Edgecombe
@ 2018-07-19 5:24 ` kbuild test robot
0 siblings, 0 replies; 5+ messages in thread
From: kbuild test robot @ 2018-07-19 5:24 UTC (permalink / raw)
To: Rick Edgecombe
Cc: kbuild-all, tglx, mingo, hpa, x86, linux-kernel, linux-mm,
kernel-hardening, kristen, dave.hansen, arjan, Rick Edgecombe
[-- Attachment #1: Type: text/plain, Size: 3167 bytes --]
Hi Rick,
Thank you for the patch! Yet something to improve:
[auto build test ERROR on linus/master]
[also build test ERROR on v4.18-rc5]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
url: https://github.com/0day-ci/linux/commits/Rick-Edgecombe/KASLR-feature-to-randomize-each-loadable-module/20180707-083637
config: um-allmodconfig (attached as .config)
compiler: gcc-7 (Debian 7.3.0-16) 7.3.0
reproduce:
# save the attached .config to linux build tree
make ARCH=um
All errors (new ones prefixed by >>):
mm/vmalloc.c: In function 'modulefraginfo_debug_show':
>> mm/vmalloc.c:2964:41: error: 'MODULES_RAND_LEN' undeclared (first use in this function); did you mean 'MODULE_NAME_LEN'?
if (obj->va_start >= MODULES_VADDR + MODULES_RAND_LEN)
^~~~~~~~~~~~~~~~
MODULE_NAME_LEN
mm/vmalloc.c:2964:41: note: each undeclared identifier is reported only once for each function it appears in
vim +2964 mm/vmalloc.c
2933
2934 #if defined(CONFIG_DEBUG_FS) && defined(CONFIG_X86_64)
2935 #if defined(CONFIG_RANDOMIZE_BASE)
2936 static void print_backup_area(struct seq_file *m, unsigned long backup_cnt)
2937 {
2938 if (kaslr_enabled())
2939 seq_printf(m, "Allocations in backup area:\t%lu\n", backup_cnt);
2940 }
2941 #else
2942 static void print_backup_area(struct seq_file *m, unsigned long backup_cnt)
2943 {
2944 }
2945 #endif
2946 static int modulefraginfo_debug_show(struct seq_file *m, void *v)
2947 {
2948 struct list_head *i;
2949 unsigned long last_end = MODULES_VADDR;
2950 unsigned long total_free = 0;
2951 unsigned long largest_free = 0;
2952 unsigned long backup_cnt = 0;
2953 unsigned long gap;
2954
2955 spin_lock(&vmap_area_lock);
2956
2957 list_for_each(i, &vmap_area_list) {
2958 struct vmap_area *obj = list_entry(i, struct vmap_area, list);
2959
2960 if (!(obj->flags & VM_LAZY_FREE)
2961 && obj->va_start >= MODULES_VADDR
2962 && obj->va_end <= MODULES_END) {
2963
> 2964 if (obj->va_start >= MODULES_VADDR + MODULES_RAND_LEN)
2965 backup_cnt++;
2966
2967 gap = (obj->va_start - last_end);
2968 if (gap > largest_free)
2969 largest_free = gap;
2970 total_free += gap;
2971
2972 last_end = obj->va_end;
2973 }
2974 }
2975
2976 gap = (MODULES_END - last_end);
2977 if (gap > largest_free)
2978 largest_free = gap;
2979 total_free += gap;
2980
2981 spin_unlock(&vmap_area_lock);
2982
2983 seq_printf(m, "Largest free space:\t\t%lu\n", largest_free);
2984 if (total_free)
2985 seq_printf(m, "External Memory Fragmentation:\t%lu%%\n",
2986 100-(100*largest_free/total_free));
2987 else
2988 seq_puts(m, "External Memory Fragmentation:\t0%%\n");
2989
2990 print_backup_area(m, backup_cnt);
2991
2992 return 0;
2993 }
2994
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
[-- Attachment #2: .config.gz --]
[-- Type: application/gzip, Size: 19863 bytes --]
^ permalink raw reply [flat|nested] 5+ messages in thread