[PATCH 0/3] x86/boot/KASLR: enhance randomness of kernel load addr when using GiB hugepage

[PATCH 0/3] x86/boot/KASLR: enhance randomness of kernel load addr when using GiB hugepage

[Pingfan Liu]

commit 747ff6265db4 ("x86/boot/KASLR: Skip specified number of 1GB huge
pages when doing physical randomization (KASLR)") and commit
9b912485e0e7 ("x86/boot/KASLR: Add two new functions for 1GB huge pages
handling") prevent the physical load addr of kernel from spoiling a good
candidate of GiB page. But the algorithm deterministicly chooses the most
front GiB page for hugetlb, and sacrifices the randomness, which
is the heart of the KASLR. This patch tries to enlarge the randomness in
the cases where hugepages=X < the num Y of good candidate of GiB
page.
To comparison, taking a typical KVM guest for example, the head 3GiB mem
can not be used as GiB hugetlb. Denoting the total mem size as Z(GiB), when
Z=5, then Y=2, assuming X=1, the randomness range before this patch is
4GiB, after this patch is 5GiB, and get a 25% improvement of randomness.
If Z=6, then Y=3, assuming X=2, the improvement equals: 50%( 6/(6-2) - 1);
assuming X=1, the improvement will be: 20% (6/(6-1) - 1)

Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: "H. Peter Anvin" <hpa@zytor.com>
Cc: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>
Cc: Baoquan He <bhe@redhat.com>
Cc: Chao Fan <fanc.fnst@cn.fujitsu.com> (authored:1/16=6%)
Cc: x86@kernel.org

Pingfan Liu (3):
  x86/boot/KASLR: change the prototypes of
    process_efi_entries/process_e820_entries
  x86/boot/KASLR: change the prototype of process_mem_region() to meet
    the align requirement
  x86/boot/KASLR: enhance randomness when using GiB hugepage

 arch/x86/boot/compressed/kaslr.c | 228 ++++++++++++++++++++++++++-------------
 1 file changed, 152 insertions(+), 76 deletions(-)

-- 
2.7.4

[PATCH 1/3] x86/boot/KASLR: change the prototypes of process_efi_entries/process_e820_entries

[Pingfan Liu]

Changing the prototypes of process_efi_entries/process_e820_entries in
order to reuse the mem entries' iteration (used in patch 3/3).

Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: "H. Peter Anvin" <hpa@zytor.com>
Cc: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>
Cc: Baoquan He <bhe@redhat.com>
Cc: Chao Fan <fanc.fnst@cn.fujitsu.com> (authored:1/16=6%)
Cc: x86@kernel.org
---
 arch/x86/boot/compressed/kaslr.c | 20 +++++++++++++-------
 1 file changed, 13 insertions(+), 7 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index d1e19f3..5185267 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -573,6 +573,10 @@ static unsigned long slots_fetch_random(void)
 	return 0;
 }
 
+typedef void (*handles_mem_region)(struct mem_vector *entry,
+			       unsigned long minimum,
+			       unsigned long image_size);
+
 static void process_mem_region(struct mem_vector *entry,
 			       unsigned long minimum,
 			       unsigned long image_size)
@@ -658,7 +662,8 @@ static void process_mem_region(struct mem_vector *entry,
  * for slots adding)
  */
 static bool
-process_efi_entries(unsigned long minimum, unsigned long image_size)
+process_efi_entries(unsigned long minimum, unsigned long image_size,
+	handles_mem_region handle)
 {
 	struct efi_info *e = &boot_params->efi_info;
 	bool efi_mirror_found = false;
@@ -717,7 +722,7 @@ process_efi_entries(unsigned long minimum, unsigned long image_size)
 
 		region.start = md->phys_addr;
 		region.size = md->num_pages << EFI_PAGE_SHIFT;
-		process_mem_region(&region, minimum, image_size);
+		(*handle)(&region, minimum, image_size);
 		if (slot_area_index == MAX_SLOT_AREA) {
 			debug_putstr("Aborted EFI scan (slot_areas full)!\n");
 			break;
@@ -727,14 +732,15 @@ process_efi_entries(unsigned long minimum, unsigned long image_size)
 }
 #else
 static inline bool
-process_efi_entries(unsigned long minimum, unsigned long image_size)
+process_efi_entries(unsigned long minimum, unsigned long image_size,
+	handles_mem_region handle)
 {
 	return false;
 }
 #endif
 
 static void process_e820_entries(unsigned long minimum,
-				 unsigned long image_size)
+	unsigned long image_size, handles_mem_region handle)
 {
 	int i;
 	struct mem_vector region;
@@ -748,7 +754,7 @@ static void process_e820_entries(unsigned long minimum,
 			continue;
 		region.start = entry->addr;
 		region.size = entry->size;
-		process_mem_region(&region, minimum, image_size);
+		(*handle)(&region, minimum, image_size);
 		if (slot_area_index == MAX_SLOT_AREA) {
 			debug_putstr("Aborted e820 scan (slot_areas full)!\n");
 			break;
@@ -768,10 +774,10 @@ static unsigned long find_random_phys_addr(unsigned long minimum,
 	/* Make sure minimum is aligned. */
 	minimum = ALIGN(minimum, CONFIG_PHYSICAL_ALIGN);
 
-	if (process_efi_entries(minimum, image_size))
+	if (process_efi_entries(minimum, image_size, process_mem_region))
 		return slots_fetch_random();
 
-	process_e820_entries(minimum, image_size);
+	process_e820_entries(minimum, image_size, process_mem_region);
 	return slots_fetch_random();
 }
 
-- 
2.7.4

[PATCH 2/3] x86/boot/KASLR: change the prototype of process_mem_region() to meet the align requirement

[Pingfan Liu]

Changing the prototype of process_mem_region(), in order to reuse this func
to find a region with special alignment requirement (used in patch 3/3 to
find a region align on 1GiB boundary. And a trivial change on the data type
of mem_vector.size to ease the comparison of underflow.

Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: "H. Peter Anvin" <hpa@zytor.com>
Cc: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>
Cc: Baoquan He <bhe@redhat.com>
Cc: Chao Fan <fanc.fnst@cn.fujitsu.com> (authored:1/16=6%)
Cc: x86@kernel.org
---
 arch/x86/boot/compressed/kaslr.c | 36 ++++++++++++++++++++++++------------
 1 file changed, 24 insertions(+), 12 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 5185267..584f17c 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -89,7 +89,7 @@ static unsigned long get_boot_seed(void)
 
 struct mem_vector {
 	unsigned long long start;
-	unsigned long long size;
+	long long size;
 };
 
 /* Only supporting at most 4 unusable memmap regions with kaslr */
@@ -577,9 +577,12 @@ typedef void (*handles_mem_region)(struct mem_vector *entry,
 			       unsigned long minimum,
 			       unsigned long image_size);
 
-static void process_mem_region(struct mem_vector *entry,
-			       unsigned long minimum,
-			       unsigned long image_size)
+typedef void (*store_info)(struct mem_vector *region,
+	unsigned long image_size);
+
+static void __process_mem_region(struct mem_vector *entry,
+	unsigned long minimum, unsigned long volume, unsigned long align,
+	store_info store)
 {
 	struct mem_vector region, overlap;
 	struct slot_area slot_area;
@@ -598,9 +601,11 @@ static void process_mem_region(struct mem_vector *entry,
 	end = min(entry->size + entry->start, mem_limit);
 	if (entry->start >= end)
 		return;
-	cur_entry.start = entry->start;
-	cur_entry.size = end - entry->start;
 
+	cur_entry.start =  ALIGN(entry->start,  align);
+	cur_entry.size = end - cur_entry.start;
+	if (cur_entry.size < 0)
+		return;
 	region.start = cur_entry.start;
 	region.size = cur_entry.size;
 
@@ -613,7 +618,7 @@ static void process_mem_region(struct mem_vector *entry,
 			region.start = minimum;
 
 		/* Potentially raise address to meet alignment needs. */
-		region.start = ALIGN(region.start, CONFIG_PHYSICAL_ALIGN);
+		region.start = ALIGN(region.start, align);
 
 		/* Did we raise the address above the passed in memory entry? */
 		if (region.start > cur_entry.start + cur_entry.size)
@@ -628,22 +633,22 @@ static void process_mem_region(struct mem_vector *entry,
 			region.size = KERNEL_IMAGE_SIZE - region.start;
 
 		/* Return if region can't contain decompressed kernel */
-		if (region.size < image_size)
+		if (region.size < volume)
 			return;
 
 		/* If nothing overlaps, store the region and return. */
 		if (!mem_avoid_overlap(&region, &overlap)) {
-			process_gb_huge_pages(&region, image_size);
+			(*store)(&region, volume);
 			return;
 		}
 
-		/* Store beginning of region if holds at least image_size. */
-		if (overlap.start > region.start + image_size) {
+		/* Store beginning of region if holds at least volume. */
+		if (overlap.start > region.start + volume) {
 			struct mem_vector beginning;
 
 			beginning.start = region.start;
 			beginning.size = overlap.start - region.start;
-			process_gb_huge_pages(&beginning, image_size);
+			(*store)(&beginning, volume);
 		}
 
 		/* Return if overlap extends to or past end of region. */
@@ -656,6 +661,13 @@ static void process_mem_region(struct mem_vector *entry,
 	}
 }
 
+static void process_mem_region(struct mem_vector *entry,
+	unsigned long minimum, unsigned long image_size)
+{
+	__process_mem_region(entry, minimum, image_size, CONFIG_PHYSICAL_ALIGN,
+		store_slot_info);
+}
+
 #ifdef CONFIG_EFI
 /*
  * Returns true if mirror region found (and must have been processed
-- 
2.7.4

[PATCH 3/3] x86/boot/KASLR: enhance randomness when using GiB hugepage

[Pingfan Liu]

commit 747ff6265db4 ("x86/boot/KASLR: Skip specified number of 1GB huge
pages when doing physical randomization (KASLR)") and
commit 9b912485e0e7 ("x86/boot/KASLR: Add two new functions for 1GB huge pages
handling") prevent the physical load addr of kernel from spoiling a good
candidate of GiB page. But the algorithm deterministicly chooses the most
front GiB page for hugetlb, and sacrifices the randomness, which
is the heart of the KASLR. This patch tries to enlarge the randomness in
the cases where hugepages=X < the num Y of good candidate of GiB
page.
To comparison, taking a typical KVM guest for example, the head 3GiB mem
can not be used as GiB hugetlb. Denoting the total mem size as Z(GiB), when
Z=5, then Y=2, assuming X=1, the randomness range before this patch is
4GiB, after this patch is 5GiB, and get a 25% improvement of randomness.
If Z=6, then Y=3, assuming X=2, the improvement equals: 50%( 6/(6-2) - 1);
assuming X=1, the improvement will be: 20% (6/(6-1) - 1)

Signed-off-by: Pingfan Liu <kernelfans@gmail.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: "H. Peter Anvin" <hpa@zytor.com>
Cc: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>
Cc: Baoquan He <bhe@redhat.com>
Cc: Chao Fan <fanc.fnst@cn.fujitsu.com> (authored:1/16=6%)
Cc: x86@kernel.org
---
 arch/x86/boot/compressed/kaslr.c | 174 ++++++++++++++++++++++++++-------------
 1 file changed, 116 insertions(+), 58 deletions(-)

diff --git a/arch/x86/boot/compressed/kaslr.c b/arch/x86/boot/compressed/kaslr.c
index 584f17c..b0bc489 100644
--- a/arch/x86/boot/compressed/kaslr.c
+++ b/arch/x86/boot/compressed/kaslr.c
@@ -50,6 +50,7 @@ unsigned int ptrs_per_p4d __ro_after_init = 1;
 #endif
 
 extern unsigned long get_cmd_line_ptr(void);
+static int figure_hugepage_layout(unsigned long kernel_sz);
 
 /* Used by PAGE_KERN* macros: */
 pteval_t __default_kernel_pte_mask __read_mostly = ~0;
@@ -109,6 +110,9 @@ enum mem_avoid_index {
 	MEM_AVOID_BOOTPARAMS,
 	MEM_AVOID_MEMMAP_BEGIN,
 	MEM_AVOID_MEMMAP_END = MEM_AVOID_MEMMAP_BEGIN + MAX_MEMMAP_REGIONS - 1,
+	MEM_AVOID_HUGEPAGE_BEGIN,
+	/* support 4 continuous chunk which can hold GiB */
+	MEM_AVOID_HUGEPAGE_END = MEM_AVOID_HUGEPAGE_BEGIN + 4,
 	MEM_AVOID_MAX,
 };
 
@@ -241,7 +245,7 @@ static void parse_gb_huge_pages(char *param, char *val)
 }
 
 
-static int handle_mem_options(void)
+static int handle_mem_options(unsigned long output_size)
 {
 	char *args = (char *)get_cmd_line_ptr();
 	size_t len = strlen((char *)args);
@@ -291,6 +295,8 @@ static int handle_mem_options(void)
 		}
 	}
 
+	if (max_gb_huge_pages != 0)
+		figure_hugepage_layout(output_size);
 	free(tmp_cmdline);
 	return 0;
 }
@@ -370,7 +376,7 @@ static int handle_mem_options(void)
  * becomes the MEM_AVOID_ZO_RANGE below.
  */
 static void mem_avoid_init(unsigned long input, unsigned long input_size,
-			   unsigned long output)
+			   unsigned long output, unsigned long output_size)
 {
 	unsigned long init_size = boot_params->hdr.init_size;
 	u64 initrd_start, initrd_size;
@@ -416,7 +422,7 @@ static void mem_avoid_init(unsigned long input, unsigned long input_size,
 	/* We don't need to set a mapping for setup_data. */
 
 	/* Mark the memmap regions we need to avoid */
-	handle_mem_options();
+	handle_mem_options(output_size);
 
 #ifdef CONFIG_X86_VERBOSE_BOOTUP
 	/* Make sure video RAM can be used. */
@@ -495,60 +501,6 @@ static void store_slot_info(struct mem_vector *region, unsigned long image_size)
 	}
 }
 
-/*
- * Skip as many 1GB huge pages as possible in the passed region
- * according to the number which users specified:
- */
-static void
-process_gb_huge_pages(struct mem_vector *region, unsigned long image_size)
-{
-	unsigned long addr, size = 0;
-	struct mem_vector tmp;
-	int i = 0;
-
-	if (!max_gb_huge_pages) {
-		store_slot_info(region, image_size);
-		return;
-	}
-
-	addr = ALIGN(region->start, PUD_SIZE);
-	/* Did we raise the address above the passed in memory entry? */
-	if (addr < region->start + region->size)
-		size = region->size - (addr - region->start);
-
-	/* Check how many 1GB huge pages can be filtered out: */
-	while (size > PUD_SIZE && max_gb_huge_pages) {
-		size -= PUD_SIZE;
-		max_gb_huge_pages--;
-		i++;
-	}
-
-	/* No good 1GB huge pages found: */
-	if (!i) {
-		store_slot_info(region, image_size);
-		return;
-	}
-
-	/*
-	 * Skip those 'i'*1GB good huge pages, and continue checking and
-	 * processing the remaining head or tail part of the passed region
-	 * if available.
-	 */
-
-	if (addr >= region->start + image_size) {
-		tmp.start = region->start;
-		tmp.size = addr - region->start;
-		store_slot_info(&tmp, image_size);
-	}
-
-	size  = region->size - (addr - region->start) - i * PUD_SIZE;
-	if (size >= image_size) {
-		tmp.start = addr + i * PUD_SIZE;
-		tmp.size = size;
-		store_slot_info(&tmp, image_size);
-	}
-}
-
 static unsigned long slots_fetch_random(void)
 {
 	unsigned long slot;
@@ -573,6 +525,9 @@ static unsigned long slots_fetch_random(void)
 	return 0;
 }
 
+static struct slot_area gb_slots[MAX_SLOT_AREA];
+static int max_gb_chunk;
+
 typedef void (*handles_mem_region)(struct mem_vector *entry,
 			       unsigned long minimum,
 			       unsigned long image_size);
@@ -580,6 +535,19 @@ typedef void (*handles_mem_region)(struct mem_vector *entry,
 typedef void (*store_info)(struct mem_vector *region,
 	unsigned long image_size);
 
+static void store_gb_slot_info(struct mem_vector *region,
+	unsigned long unused_image_size)
+{
+	int num;
+
+	if (region->size < PUD_SIZE)
+		return;
+	num = region->size / PUD_SIZE;
+	gb_slots[max_gb_chunk].addr = region->start;
+	gb_slots[max_gb_chunk].num = num;
+	max_gb_chunk++;
+}
+
 static void __process_mem_region(struct mem_vector *entry,
 	unsigned long minimum, unsigned long volume, unsigned long align,
 	store_info store)
@@ -751,6 +719,26 @@ process_efi_entries(unsigned long minimum, unsigned long image_size,
 }
 #endif
 
+
+/* the candidate region for 1GiB page should avoid [0, MEM_AVOID_MEMMAP_END]
+ */
+static void calc_gb_slots(struct mem_vector *entry, unsigned long unused_min,
+	unsigned long unused)
+{
+	struct mem_vector v;
+	unsigned long start;
+
+	if (max_gb_chunk == MAX_SLOT_AREA) {
+		debug_putstr("Aborted GiB chunks full)!\n");
+		return;
+	}
+	v.start = ALIGN(entry->start, PUD_SIZE);
+	v.size = entry->start + entry->size - v.start;
+	if (v.size < 0)
+		return;
+	__process_mem_region(&v, 0, PUD_SIZE, PUD_SIZE, store_gb_slot_info);
+}
+
 static void process_e820_entries(unsigned long minimum,
 	unsigned long image_size, handles_mem_region handle)
 {
@@ -774,6 +762,76 @@ static void process_e820_entries(unsigned long minimum,
 	}
 }
 
+/* figure out the good 1GiB page slots, and compare the GiB slots num with
+ * "hugepages=x" in cmdline. For little and equal, It falls into 3 cases:
+ * 1st: equal, then prevent kaslr from extract kernel into these GiB slots
+ * 2nd. equal x plus 1, then pick up a GiB slot randomly into which kaslr is
+ * allows to extract kernel.
+ * 3rd. the rest, kaslr can extract kernel to any GiB slot
+ */
+static int figure_hugepage_layout(unsigned long kernel_sz)
+{
+	int i, idx = 0;
+	struct mem_vector region;
+	unsigned long first_end, second_start;
+	long slot_chosen, cur_slot_num;
+	long off;
+	int gb_total_slot = 0;
+
+	if (!process_efi_entries(0x1000000, kernel_sz, calc_gb_slots))
+		process_e820_entries(0x1000000, kernel_sz, calc_gb_slots);
+
+	/* for hugepage, the load addr should be only limited when ... */
+
+	for (i = 0; i < max_gb_chunk; i++)
+		gb_total_slot += gb_slots[i].num;
+	if (max_gb_huge_pages < (unsigned long)(gb_total_slot - 1))
+		return 0;
+
+	idx = MEM_AVOID_HUGEPAGE_BEGIN;
+	if (max_gb_huge_pages == gb_total_slot) {
+		for (i = 0; i < gb_total_slot; i++, idx++) {
+			mem_avoid[idx].start = gb_slots[i].addr;
+			mem_avoid[idx].size = gb_slots[i].num * PUD_SIZE;
+		}
+	/* randomly choose a GiB slot to load kernel */
+	} else if (max_gb_huge_pages == gb_total_slot - 1) {
+		slot_chosen = kaslr_get_random_long("Physical") % gb_total_slot;
+		cur_slot_num = 0;
+		for (i = 0; i < max_gb_chunk; i++) {
+			off = slot_chosen - cur_slot_num;
+			if (off > 0 && off < gb_slots[i].num) {
+				/* split the continuous area into two parts */
+				first_end = gb_slots[i].addr
+					+ (off - 1) * PUD_SIZE;
+				/* prevent kernel from crossing the GiB boundary
+				 * otherwise waste a good hugepage
+				 */
+				second_start = gb_slots[i].addr + off * PUD_SIZE
+				  - ALIGN(kernel_sz, CONFIG_PHYSICAL_ALIGN);
+				if (first_end != gb_slots[i].addr) {
+					mem_avoid[idx].start = gb_slots[i].addr;
+					mem_avoid[idx].size =
+						first_end - gb_slots[i].addr;
+					idx++;
+				}
+				mem_avoid[idx].start = second_start;
+				mem_avoid[idx].size = gb_slots[i].addr +
+				    gb_slots[i].num * PUD_SIZE - second_start;
+				idx++;
+			} else {
+				mem_avoid[idx].start = gb_slots[i].addr;
+				mem_avoid[idx].size =
+					gb_slots[i].num * PUD_SIZE;
+				idx++;
+			}
+			cur_slot_num += gb_slots[i].num;
+		}
+	}
+
+	return 0;
+}
+
 static unsigned long find_random_phys_addr(unsigned long minimum,
 					   unsigned long image_size)
 {
@@ -847,7 +905,7 @@ void choose_random_location(unsigned long input,
 	initialize_identity_maps();
 
 	/* Record the various known unsafe memory ranges. */
-	mem_avoid_init(input, input_size, *output);
+	mem_avoid_init(input, input_size, *output, output_size);
 
 	/*
 	 * Low end of the randomization range should be the
-- 
2.7.4

Re: [PATCH 0/3] x86/boot/KASLR: enhance randomness of kernel load addr when using GiB hugepage

[Chao Fan]

On Thu, Sep 06, 2018 at 10:36:19AM +0800, Pingfan Liu wrote:

Hi Pingfan,

>commit 747ff6265db4 ("x86/boot/KASLR: Skip specified number of 1GB huge
>pages when doing physical randomization (KASLR)") and commit
>9b912485e0e7 ("x86/boot/KASLR: Add two new functions for 1GB huge pages
>handling") prevent the physical load addr of kernel from spoiling a good
>candidate of GiB page. But the algorithm deterministicly chooses the most
>front GiB page for hugetlb, and sacrifices the randomness, which
>is the heart of the KASLR. This patch tries to enlarge the randomness in
>the cases where hugepages=X < the num Y of good candidate of GiB

Yes, in some situations, if Y > X, the patch would reduce the
randomness. And to reserve a fixed 1G for huge page is not perfect
enouth.
But the the size of slot is so small, the size of memory is so big.

>page.
>To comparison, taking a typical KVM guest for example, the head 3GiB mem
>can not be used as GiB hugetlb. Denoting the total mem size as Z(GiB), when
>Z=5, then Y=2, assuming X=1, the randomness range before this patch is
>4GiB, after this patch is 5GiB, and get a 25% improvement of randomness.

Such as your example,
in 4G, the probability every slot chosen is about 0.00049
in 5G, the probability every slot chosen is about 0.00039
Yes, you did improve 25% for randomness. But I wonder if it's worth to
improve from 0.00049 to 0.00039.

If there is something wrong in my understanding, please let me know.

Thanks,
Chao Fan

>If Z=6, then Y=3, assuming X=2, the improvement equals: 50%( 6/(6-2) - 1);
>assuming X=1, the improvement will be: 20% (6/(6-1) - 1)
>
>Cc: Thomas Gleixner <tglx@linutronix.de>
>Cc: Ingo Molnar <mingo@redhat.com>
>Cc: "H. Peter Anvin" <hpa@zytor.com>
>Cc: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>
>Cc: Baoquan He <bhe@redhat.com>
>Cc: Chao Fan <fanc.fnst@cn.fujitsu.com> (authored:1/16=6%)
>Cc: x86@kernel.org
>
>Pingfan Liu (3):
>  x86/boot/KASLR: change the prototypes of
>    process_efi_entries/process_e820_entries
>  x86/boot/KASLR: change the prototype of process_mem_region() to meet
>    the align requirement
>  x86/boot/KASLR: enhance randomness when using GiB hugepage
>
> arch/x86/boot/compressed/kaslr.c | 228 ++++++++++++++++++++++++++-------------
> 1 file changed, 152 insertions(+), 76 deletions(-)
>
>-- 
>2.7.4
>
>
>

Re: [PATCH 0/3] x86/boot/KASLR: enhance randomness of kernel load addr when using GiB hugepage

[Pingfan Liu]

On Thu, Sep 6, 2018 at 12:07 PM Chao Fan <fanc.fnst@cn.fujitsu.com> wrote:
>
> On Thu, Sep 06, 2018 at 10:36:19AM +0800, Pingfan Liu wrote:
>
> Hi Pingfan,
>
> >commit 747ff6265db4 ("x86/boot/KASLR: Skip specified number of 1GB huge
> >pages when doing physical randomization (KASLR)") and commit
> >9b912485e0e7 ("x86/boot/KASLR: Add two new functions for 1GB huge pages
> >handling") prevent the physical load addr of kernel from spoiling a good
> >candidate of GiB page. But the algorithm deterministicly chooses the most
> >front GiB page for hugetlb, and sacrifices the randomness, which
> >is the heart of the KASLR. This patch tries to enlarge the randomness in
> >the cases where hugepages=X < the num Y of good candidate of GiB
>
> Yes, in some situations, if Y > X, the patch would reduce the
> randomness. And to reserve a fixed 1G for huge page is not perfect
> enouth.
> But the the size of slot is so small, the size of memory is so big.
>
Yes, but this is the sense of a human,. and normally, we are protected
against the attack from a program.

> >page.
> >To comparison, taking a typical KVM guest for example, the head 3GiB mem
> >can not be used as GiB hugetlb. Denoting the total mem size as Z(GiB), when
> >Z=5, then Y=2, assuming X=1, the randomness range before this patch is
> >4GiB, after this patch is 5GiB, and get a 25% improvement of randomness.
>
> Such as your example,
> in 4G, the probability every slot chosen is about 0.00049
> in 5G, the probability every slot chosen is about 0.00039
> Yes, you did improve 25% for randomness. But I wonder if it's worth to
> improve from 0.00049 to 0.00039.
>
This is the case of least improvement.

> If there is something wrong in my understanding, please let me know.
>
Yes, you get my idea. There are two factor worth to consider. The 1st
one is the head 3GiB, if it can be reduce to 1GiB or 2GiB, then the
randomness will have a great improvement. The 2nd one is the X, which
also play a important role of the randomness.

Thanks and regards,
Pingfan

> Thanks,
> Chao Fan
>
> >If Z=6, then Y=3, assuming X=2, the improvement equals: 50%( 6/(6-2) - 1);
> >assuming X=1, the improvement will be: 20% (6/(6-1) - 1)
> >
> >Cc: Thomas Gleixner <tglx@linutronix.de>
> >Cc: Ingo Molnar <mingo@redhat.com>
> >Cc: "H. Peter Anvin" <hpa@zytor.com>
> >Cc: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>
> >Cc: Baoquan He <bhe@redhat.com>
> >Cc: Chao Fan <fanc.fnst@cn.fujitsu.com> (authored:1/16=6%)
> >Cc: x86@kernel.org
> >
> >Pingfan Liu (3):
> >  x86/boot/KASLR: change the prototypes of
> >    process_efi_entries/process_e820_entries
> >  x86/boot/KASLR: change the prototype of process_mem_region() to meet
> >    the align requirement
> >  x86/boot/KASLR: enhance randomness when using GiB hugepage
> >
> > arch/x86/boot/compressed/kaslr.c | 228 ++++++++++++++++++++++++++-------------
> > 1 file changed, 152 insertions(+), 76 deletions(-)
> >
> >--
> >2.7.4
> >
> >
> >
>
>

Re: [PATCH 0/3] x86/boot/KASLR: enhance randomness of kernel load addr when using GiB hugepage

[Chao Fan]

On Thu, Sep 06, 2018 at 01:58:08PM +0800, Pingfan Liu wrote:
>On Thu, Sep 6, 2018 at 12:07 PM Chao Fan <fanc.fnst@cn.fujitsu.com> wrote:
>>
>> On Thu, Sep 06, 2018 at 10:36:19AM +0800, Pingfan Liu wrote:
>>
>> Hi Pingfan,
>>
>> >commit 747ff6265db4 ("x86/boot/KASLR: Skip specified number of 1GB huge
>> >pages when doing physical randomization (KASLR)") and commit
>> >9b912485e0e7 ("x86/boot/KASLR: Add two new functions for 1GB huge pages
>> >handling") prevent the physical load addr of kernel from spoiling a good
>> >candidate of GiB page. But the algorithm deterministicly chooses the most
>> >front GiB page for hugetlb, and sacrifices the randomness, which
>> >is the heart of the KASLR. This patch tries to enlarge the randomness in
>> >the cases where hugepages=X < the num Y of good candidate of GiB
>>
>> Yes, in some situations, if Y > X, the patch would reduce the
>> randomness. And to reserve a fixed 1G for huge page is not perfect
>> enouth.
>> But the the size of slot is so small, the size of memory is so big.
>>
>Yes, but this is the sense of a human,. and normally, we are protected
>against the attack from a program.
>

Well, in my opinion, the problem that Baoquan tried to fix exists
only when Y == X. If Y > X, I think the problem is not a big problem,
even though kernel breaks a good 1G memory for huge page, there are still
enough place left.

>> >page.
>> >To comparison, taking a typical KVM guest for example, the head 3GiB mem
>> >can not be used as GiB hugetlb. Denoting the total mem size as Z(GiB), when
>> >Z=5, then Y=2, assuming X=1, the randomness range before this patch is
>> >4GiB, after this patch is 5GiB, and get a 25% improvement of randomness.
>>
>> Such as your example,
>> in 4G, the probability every slot chosen is about 0.00049
>> in 5G, the probability every slot chosen is about 0.00039
>> Yes, you did improve 25% for randomness. But I wonder if it's worth to
>> improve from 0.00049 to 0.00039.
>>
>This is the case of least improvement.
>
>> If there is something wrong in my understanding, please let me know.
>>
>Yes, you get my idea. There are two factor worth to consider. The 1st
>one is the head 3GiB, if it can be reduce to 1GiB or 2GiB, then the

Yes, as you said, from a human's feeling, I think if there are more
than one thousand slots, the probability is small enough.
In some situations, your patch improve the randomness much. As for whether
it's worth to do, let's see how other people think.

Thanks,
Chao Fan

>randomness will have a great improvement. The 2nd one is the X, which
>also play a important role of the randomness.
>
>Thanks and regards,
>Pingfan
>
>> Thanks,
>> Chao Fan
>>
>> >If Z=6, then Y=3, assuming X=2, the improvement equals: 50%( 6/(6-2) - 1);
>> >assuming X=1, the improvement will be: 20% (6/(6-1) - 1)
>> >
>> >Cc: Thomas Gleixner <tglx@linutronix.de>
>> >Cc: Ingo Molnar <mingo@redhat.com>
>> >Cc: "H. Peter Anvin" <hpa@zytor.com>
>> >Cc: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com>
>> >Cc: Baoquan He <bhe@redhat.com>
>> >Cc: Chao Fan <fanc.fnst@cn.fujitsu.com> (authored:1/16=6%)
>> >Cc: x86@kernel.org
>> >
>> >Pingfan Liu (3):
>> >  x86/boot/KASLR: change the prototypes of
>> >    process_efi_entries/process_e820_entries
>> >  x86/boot/KASLR: change the prototype of process_mem_region() to meet
>> >    the align requirement
>> >  x86/boot/KASLR: enhance randomness when using GiB hugepage
>> >
>> > arch/x86/boot/compressed/kaslr.c | 228 ++++++++++++++++++++++++++-------------
>> > 1 file changed, 152 insertions(+), 76 deletions(-)
>> >
>> >--
>> >2.7.4
>> >
>> >
>> >
>>
>>
>
>

Re: [PATCH 0/3] x86/boot/KASLR: enhance randomness of kernel load addr when using GiB hugepage

[Baoquan He]

Hi Pingfan,

On 09/06/18 at 10:36am, Pingfan Liu wrote:
> commit 747ff6265db4 ("x86/boot/KASLR: Skip specified number of 1GB huge
> pages when doing physical randomization (KASLR)") and commit
> 9b912485e0e7 ("x86/boot/KASLR: Add two new functions for 1GB huge pages
> handling") prevent the physical load addr of kernel from spoiling a good
> candidate of GiB page. But the algorithm deterministicly chooses the most
> front GiB page for hugetlb, and sacrifices the randomness, which
> is the heart of the KASLR. This patch tries to enlarge the randomness in
> the cases where hugepages=X < the num Y of good candidate of GiB
> page.

Better tell how you improve in cover letter or patch log.

> To comparison, taking a typical KVM guest for example, the head 3GiB mem
> can not be used as GiB hugetlb. Denoting the total mem size as Z(GiB), when
> Z=5, then Y=2, assuming X=1, the randomness range before this patch is
> 4GiB, after this patch is 5GiB, and get a 25% improvement of randomness.
> If Z=6, then Y=3, assuming X=2, the improvement equals: 50%( 6/(6-2) - 1);
> assuming X=1, the improvement will be: 20% (6/(6-1) - 1)

Hmm, what if hugepages=1, or 2, even 100, but system owns 1PB memory?

Secondly, even in the case that hugepages=1, system memory is 5G, if no
'movable_node' specified, the last 1G can't be chosen for hugepage.
Because memblock will allocate memory top to down. This is not
improving, but make the code not work.

Lastly, getting better randomness is the heart of KASLR, while
process_mem_region() is the heart of kernel KASLR code. Unless the
current code blocks serious fix, we'd better not touch it. Keeping
it can make the current code logic simple and more readable. It's
like a proved running well machine, we just dig out the unwanted
middle, feed the good head and tail regions into it, then it gives
back good slot for kernel position one by one.

To sum up, I personally think this patchset is not a good idea.

Thanks
Baoquan

Re: [PATCH 0/3] x86/boot/KASLR: enhance randomness of kernel load addr when using GiB hugepage

[Pingfan Liu]

On Mon, Sep 10, 2018 at 7:33 AM Baoquan He <bhe@redhat.com> wrote:
>
> Hi Pingfan,
>
> On 09/06/18 at 10:36am, Pingfan Liu wrote:
> > commit 747ff6265db4 ("x86/boot/KASLR: Skip specified number of 1GB huge
> > pages when doing physical randomization (KASLR)") and commit
> > 9b912485e0e7 ("x86/boot/KASLR: Add two new functions for 1GB huge pages
> > handling") prevent the physical load addr of kernel from spoiling a good
> > candidate of GiB page. But the algorithm deterministicly chooses the most
> > front GiB page for hugetlb, and sacrifices the randomness, which
> > is the heart of the KASLR. This patch tries to enlarge the randomness in
> > the cases where hugepages=X < the num Y of good candidate of GiB
> > page.
>
> Better tell how you improve in cover letter or patch log.
>
Yes, good advice.

> > To comparison, taking a typical KVM guest for example, the head 3GiB mem
> > can not be used as GiB hugetlb. Denoting the total mem size as Z(GiB), when
> > Z=5, then Y=2, assuming X=1, the randomness range before this patch is
> > 4GiB, after this patch is 5GiB, and get a 25% improvement of randomness.
> > If Z=6, then Y=3, assuming X=2, the improvement equals: 50%( 6/(6-2) - 1);
> > assuming X=1, the improvement will be: 20% (6/(6-1) - 1)
>
> Hmm, what if hugepages=1, or 2, even 100, but system owns 1PB memory?
>
Not agree, since the kvm guest is much popular, but most of them have
no much memory.

> Secondly, even in the case that hugepages=1, system memory is 5G, if no
> 'movable_node' specified, the last 1G can't be chosen for hugepage.
> Because memblock will allocate memory top to down. This is not
> improving, but make the code not work.
>
Yes, you are right. It is too hard to consider the runtime layout at
this very early stage.

> Lastly, getting better randomness is the heart of KASLR, while
> process_mem_region() is the heart of kernel KASLR code. Unless the
> current code blocks serious fix, we'd better not touch it. Keeping
> it can make the current code logic simple and more readable. It's

Yes.

Thanks,
Pingfan
> like a proved running well machine, we just dig out the unwanted
> middle, feed the good head and tail regions into it, then it gives
> back good slot for kernel position one by one.
>
> To sum up, I personally think this patchset is not a good idea.
>
> Thanks
> Baoquan