Skip to contentSkip to conversation

x86/boot/KASLR: enhance randomness of kernel load addr when using GiB hugepage

PATCH In review Pingfan Liu 3 participants 9 messages Sep 6, 2018 – Sep 10, 2018 x86

lore
Share & tools
lore
#0 lore raw

cover x86/boot/KASLR: enhance randomness of kernel load addr when using GiB hugepage

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 <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc "Kirill A. Shutemov" <[email protected]>
Cc Baoquan He <[email protected]>
Cc Chao Fan <[email protected]> (authored:1/16=6%)

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(-)
Signature · 1 line
2.7.4
#1 lore raw

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

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

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc "Kirill A. Shutemov" <[email protected]>
Cc Baoquan He <[email protected]>
Cc Chao Fan <[email protected]> (authored:1/16=6%)
---
 arch/x86/boot/compressed/kaslr.c | 20 +++++++++++++-------
 1 file changed, 13 insertions(+), 7 deletions(-)
arch/x86/boot/compressed/kaslr.c +13 -7
index d1e19f3..5185267 100644
@@ -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();
 }
 
Signature · 1 line
2.7.4
#2 lore raw

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

In reply to 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.

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc "Kirill A. Shutemov" <[email protected]>
Cc Baoquan He <[email protected]>
Cc Chao Fan <[email protected]> (authored:1/16=6%)
---
 arch/x86/boot/compressed/kaslr.c | 36 ++++++++++++++++++++++++------------
 1 file changed, 24 insertions(+), 12 deletions(-)
arch/x86/boot/compressed/kaslr.c +24 -12
index 5185267..584f17c 100644
@@ -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
Signature · 1 line
2.7.4
#3 lore raw

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

In reply to 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 <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc "Kirill A. Shutemov" <[email protected]>
Cc Baoquan He <[email protected]>
Cc Chao Fan <[email protected]> (authored:1/16=6%)
---
 arch/x86/boot/compressed/kaslr.c | 174 ++++++++++++++++++++++++++-------------
 1 file changed, 116 insertions(+), 58 deletions(-)
arch/x86/boot/compressed/kaslr.c +116 -58
index 584f17c..b0bc489 100644
@@ -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
Signature · 1 line
2.7.4
#4 lore raw
In reply to Pingfan Liu

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

Hi Pingfan,

Quoted 8 lines

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.

Quoted 5 lines

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

Quoted 26 lines

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 <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc "Kirill A. Shutemov" <[email protected]>
Cc Baoquan He <[email protected]>
Cc Chao Fan <[email protected]> (authored:1/16=6%)

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(-)
Signature · 1 line
2.7.4
#5 lore raw
Quoted 14 lines · Chao Fan

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

Hi Pingfan,

Quoted 8 lines

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

Quoted 5 lines

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.

Quoted 6 lines
Quoted 5 lines

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.

Quoted 6 lines

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.

Quoted 2 lines

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

Quoted 31 lines

Thanks,
Chao Fan

Quoted 26 lines

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 <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc "Kirill A. Shutemov" <[email protected]>
Cc Baoquan He <[email protected]>
Cc Chao Fan <[email protected]> (authored:1/16=6%)

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

#6 lore raw
Quoted 15 lines · Pingfan Liu
Quoted 14 lines · Chao Fan

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

Hi Pingfan,

Quoted 8 lines

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

Quoted 8 lines
Quoted 5 lines

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.

Quoted 12 lines
Quoted 6 lines
Quoted 5 lines

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.

Quoted 6 lines

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.

Quoted 6 lines

This is the case of least improvement.

Quoted 2 lines

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

Quoted 39 lines

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

Quoted 31 lines

Thanks,
Chao Fan

Quoted 26 lines

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 <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc "Kirill A. Shutemov" <[email protected]>
Cc Baoquan He <[email protected]>
Cc Chao Fan <[email protected]> (authored:1/16=6%)

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

#7 lore raw
In reply to Pingfan Liu

Hi Pingfan,

Quoted 9 lines · 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.

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

Quoted 6 lines

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

#8 lore raw
Quoted 14 lines · Baoquan He

Hi Pingfan,

Quoted 9 lines · 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.

Quoted 2 lines

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

Yes, good advice.

Quoted 9 lines
Quoted 6 lines

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.

Quoted 5 lines

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.

Quoted 4 lines

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

Quoted 8 lines

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