kaslr.c 21.2 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0
2
3
4
5
6
7
8
9
10
11
12
/*
 * kaslr.c
 *
 * This contains the routines needed to generate a reasonable level of
 * entropy to choose a randomized kernel base address offset in support
 * of Kernel Address Space Layout Randomization (KASLR). Additionally
 * handles walking the physical memory maps (and tracking memory regions
 * to avoid) in order to select a physical memory location that can
 * contain the entire properly aligned running kernel image.
 *
 */
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/*
 * isspace() in linux/ctype.h is expected by next_args() to filter
 * out "space/lf/tab". While boot/ctype.h conflicts with linux/ctype.h,
 * since isdigit() is implemented in both of them. Hence disable it
 * here.
 */
#define BOOT_CTYPE_H

/*
 * _ctype[] in lib/ctype.c is needed by isspace() of linux/ctype.h.
 * While both lib/ctype.c and lib/cmdline.c will bring EXPORT_SYMBOL
 * which is meaningless and will cause compiling error in some cases.
 * So do not include linux/export.h and define EXPORT_SYMBOL(sym)
 * as empty.
 */
#define _LINUX_EXPORT_H
#define EXPORT_SYMBOL(sym)

32
#include "misc.h"
33
#include "error.h"
34
#include "../string.h"
35

36
37
38
39
#include <generated/compile.h>
#include <linux/module.h>
#include <linux/uts.h>
#include <linux/utsname.h>
40
#include <linux/ctype.h>
41
#include <linux/efi.h>
42
#include <generated/utsrelease.h>
43
#include <asm/efi.h>
44

45
46
47
48
/* Macros used by the included decompressor code below. */
#define STATIC
#include <linux/decompress/mm.h>

49
50
#ifdef CONFIG_X86_5LEVEL
unsigned int pgtable_l5_enabled __ro_after_init = 1;
51
52
unsigned int pgdir_shift __ro_after_init = 48;
unsigned int ptrs_per_p4d __ro_after_init = 512;
53
54
#endif

55
56
extern unsigned long get_cmd_line_ptr(void);

57
/* Simplified build-specific string for starting entropy. */
58
static const char build_str[] = UTS_RELEASE " (" LINUX_COMPILE_BY "@"
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
		LINUX_COMPILE_HOST ") (" LINUX_COMPILER ") " UTS_VERSION;

static unsigned long rotate_xor(unsigned long hash, const void *area,
				size_t size)
{
	size_t i;
	unsigned long *ptr = (unsigned long *)area;

	for (i = 0; i < size / sizeof(hash); i++) {
		/* Rotate by odd number of bits and XOR. */
		hash = (hash << ((sizeof(hash) * 8) - 7)) | (hash >> 7);
		hash ^= ptr[i];
	}

	return hash;
}

/* Attempt to create a simple but unpredictable starting entropy. */
77
static unsigned long get_boot_seed(void)
78
79
80
81
{
	unsigned long hash = 0;

	hash = rotate_xor(hash, build_str, sizeof(build_str));
82
	hash = rotate_xor(hash, boot_params, sizeof(*boot_params));
83
84
85
86

	return hash;
}

87
88
#define KASLR_COMPRESSED_BOOT
#include "../../lib/kaslr.c"
89

90
struct mem_vector {
91
92
	unsigned long long start;
	unsigned long long size;
93
94
};

95
96
97
98
99
/* Only supporting at most 4 unusable memmap regions with kaslr */
#define MAX_MEMMAP_REGIONS	4

static bool memmap_too_large;

100

101
102
103
104
/* Store memory limit specified by "mem=nn[KMG]" or "memmap=nn[KMG]" */
unsigned long long mem_limit = ULLONG_MAX;


105
106
107
108
109
enum mem_avoid_index {
	MEM_AVOID_ZO_RANGE = 0,
	MEM_AVOID_INITRD,
	MEM_AVOID_CMDLINE,
	MEM_AVOID_BOOTPARAMS,
110
111
	MEM_AVOID_MEMMAP_BEGIN,
	MEM_AVOID_MEMMAP_END = MEM_AVOID_MEMMAP_BEGIN + MAX_MEMMAP_REGIONS - 1,
112
113
114
	MEM_AVOID_MAX,
};

115
static struct mem_vector mem_avoid[MEM_AVOID_MAX];
116
117
118
119
120
121
122
123
124
125
126
127

static bool mem_overlaps(struct mem_vector *one, struct mem_vector *two)
{
	/* Item one is entirely before item two. */
	if (one->start + one->size <= two->start)
		return false;
	/* Item one is entirely after item two. */
	if (one->start >= two->start + two->size)
		return false;
	return true;
}

128
char *skip_spaces(const char *str)
129
{
130
131
132
	while (isspace(*str))
		++str;
	return (char *)str;
133
}
134
135
#include "../../../../lib/ctype.c"
#include "../../../../lib/cmdline.c"
136
137
138
139
140
141
142
143
144
145
146
147
148
149

static int
parse_memmap(char *p, unsigned long long *start, unsigned long long *size)
{
	char *oldp;

	if (!p)
		return -EINVAL;

	/* We don't care about this option here */
	if (!strncmp(p, "exactmap", 8))
		return -EINVAL;

	oldp = p;
150
	*size = memparse(p, &p);
151
152
153
154
155
156
157
	if (p == oldp)
		return -EINVAL;

	switch (*p) {
	case '#':
	case '$':
	case '!':
158
		*start = memparse(p + 1, &p);
159
		return 0;
160
161
162
163
164
165
166
167
168
169
170
	case '@':
		/* memmap=nn@ss specifies usable region, should be skipped */
		*size = 0;
		/* Fall through */
	default:
		/*
		 * If w/o offset, only size specified, memmap=nn[KMG] has the
		 * same behaviour as mem=nn[KMG]. It limits the max address
		 * system can use. Region above the limit should be avoided.
		 */
		*start = 0;
171
172
173
174
175
176
		return 0;
	}

	return -EINVAL;
}

177
static void mem_avoid_memmap(char *str)
178
{
179
	static int i;
180

181
	if (i >= MAX_MEMMAP_REGIONS)
182
183
184
185
186
187
188
189
190
191
192
193
194
195
		return;

	while (str && (i < MAX_MEMMAP_REGIONS)) {
		int rc;
		unsigned long long start, size;
		char *k = strchr(str, ',');

		if (k)
			*k++ = 0;

		rc = parse_memmap(str, &start, &size);
		if (rc < 0)
			break;
		str = k;
196
197
198
199
200
201

		if (start == 0) {
			/* Store the specified memory limit if size > 0 */
			if (size > 0)
				mem_limit = size;

202
			continue;
203
		}
204
205
206
207
208
209
210
211
212
213
214

		mem_avoid[MEM_AVOID_MEMMAP_BEGIN + i].start = start;
		mem_avoid[MEM_AVOID_MEMMAP_BEGIN + i].size = size;
		i++;
	}

	/* More than 4 memmaps, fail kaslr */
	if ((i >= MAX_MEMMAP_REGIONS) && str)
		memmap_too_large = true;
}

215
216
217
218
219
220
static int handle_mem_memmap(void)
{
	char *args = (char *)get_cmd_line_ptr();
	size_t len = strlen((char *)args);
	char *tmp_cmdline;
	char *param, *val;
221
	u64 mem_size;
222

223
	if (!strstr(args, "memmap=") && !strstr(args, "mem="))
224
225
226
		return 0;

	tmp_cmdline = malloc(len + 1);
227
	if (!tmp_cmdline)
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
		error("Failed to allocate space for tmp_cmdline");

	memcpy(tmp_cmdline, args, len);
	tmp_cmdline[len] = 0;
	args = tmp_cmdline;

	/* Chew leading spaces */
	args = skip_spaces(args);

	while (*args) {
		args = next_arg(args, &param, &val);
		/* Stop at -- */
		if (!val && strcmp(param, "--") == 0) {
			warn("Only '--' specified in cmdline");
			free(tmp_cmdline);
			return -1;
		}

246
		if (!strcmp(param, "memmap")) {
247
			mem_avoid_memmap(val);
248
249
250
251
252
253
254
255
256
257
258
259
		} else if (!strcmp(param, "mem")) {
			char *p = val;

			if (!strcmp(p, "nopentium"))
				continue;
			mem_size = memparse(p, &p);
			if (mem_size == 0) {
				free(tmp_cmdline);
				return -EINVAL;
			}
			mem_limit = mem_size;
		}
260
261
262
263
264
265
	}

	free(tmp_cmdline);
	return 0;
}

266
/*
267
268
269
 * In theory, KASLR can put the kernel anywhere in the range of [16M, 64T).
 * The mem_avoid array is used to store the ranges that need to be avoided
 * when KASLR searches for an appropriate random address. We must avoid any
270
 * regions that are unsafe to overlap with during decompression, and other
271
272
273
274
275
 * things like the initrd, cmdline and boot_params. This comment seeks to
 * explain mem_avoid as clearly as possible since incorrect mem_avoid
 * memory ranges lead to really hard to debug boot failures.
 *
 * The initrd, cmdline, and boot_params are trivial to identify for
276
 * avoiding. They are MEM_AVOID_INITRD, MEM_AVOID_CMDLINE, and
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
 * MEM_AVOID_BOOTPARAMS respectively below.
 *
 * What is not obvious how to avoid is the range of memory that is used
 * during decompression (MEM_AVOID_ZO_RANGE below). This range must cover
 * the compressed kernel (ZO) and its run space, which is used to extract
 * the uncompressed kernel (VO) and relocs.
 *
 * ZO's full run size sits against the end of the decompression buffer, so
 * we can calculate where text, data, bss, etc of ZO are positioned more
 * easily.
 *
 * For additional background, the decompression calculations can be found
 * in header.S, and the memory diagram is based on the one found in misc.c.
 *
 * The following conditions are already enforced by the image layouts and
 * associated code:
 *  - input + input_size >= output + output_size
 *  - kernel_total_size <= init_size
 *  - kernel_total_size <= output_size (see Note below)
 *  - output + init_size >= output + output_size
297
 *
298
299
300
301
302
 * (Note that kernel_total_size and output_size have no fundamental
 * relationship, but output_size is passed to choose_random_location
 * as a maximum of the two. The diagram is showing a case where
 * kernel_total_size is larger than output_size, but this case is
 * handled by bumping output_size.)
303
 *
304
 * The above conditions can be illustrated by a diagram:
305
 *
306
307
308
309
310
311
312
 * 0   output            input            input+input_size    output+init_size
 * |     |                 |                             |             |
 * |     |                 |                             |             |
 * |-----|--------|--------|--------------|-----------|--|-------------|
 *                |                       |           |
 *                |                       |           |
 * output+init_size-ZO_INIT_SIZE  output+output_size  output+kernel_total_size
313
 *
314
315
 * [output, output+init_size) is the entire memory range used for
 * extracting the compressed image.
316
 *
317
318
 * [output, output+kernel_total_size) is the range needed for the
 * uncompressed kernel (VO) and its run size (bss, brk, etc).
319
 *
320
321
322
 * [output, output+output_size) is VO plus relocs (i.e. the entire
 * uncompressed payload contained by ZO). This is the area of the buffer
 * written to during decompression.
323
 *
324
325
326
 * [output+init_size-ZO_INIT_SIZE, output+init_size) is the worst-case
 * range of the copied ZO and decompression code. (i.e. the range
 * covered backwards of size ZO_INIT_SIZE, starting from output+init_size.)
327
 *
328
329
330
 * [input, input+input_size) is the original copied compressed image (ZO)
 * (i.e. it does not include its run size). This range must be avoided
 * because it contains the data used for decompression.
331
 *
332
333
334
 * [input+input_size, output+init_size) is [_text, _end) for ZO. This
 * range includes ZO's heap and stack, and must be avoided since it
 * performs the decompression.
335
 *
336
337
338
 * Since the above two ranges need to be avoided and they are adjacent,
 * they can be merged, resulting in: [input, output+init_size) which
 * becomes the MEM_AVOID_ZO_RANGE below.
339
 */
340
static void mem_avoid_init(unsigned long input, unsigned long input_size,
341
			   unsigned long output)
342
{
343
	unsigned long init_size = boot_params->hdr.init_size;
344
345
346
347
348
349
	u64 initrd_start, initrd_size;
	u64 cmd_line, cmd_line_size;
	char *ptr;

	/*
	 * Avoid the region that is unsafe to overlap during
350
	 * decompression.
351
	 */
352
353
	mem_avoid[MEM_AVOID_ZO_RANGE].start = input;
	mem_avoid[MEM_AVOID_ZO_RANGE].size = (output + init_size) - input;
354
355
	add_identity_map(mem_avoid[MEM_AVOID_ZO_RANGE].start,
			 mem_avoid[MEM_AVOID_ZO_RANGE].size);
356
357

	/* Avoid initrd. */
358
359
360
361
	initrd_start  = (u64)boot_params->ext_ramdisk_image << 32;
	initrd_start |= boot_params->hdr.ramdisk_image;
	initrd_size  = (u64)boot_params->ext_ramdisk_size << 32;
	initrd_size |= boot_params->hdr.ramdisk_size;
362
363
	mem_avoid[MEM_AVOID_INITRD].start = initrd_start;
	mem_avoid[MEM_AVOID_INITRD].size = initrd_size;
364
	/* No need to set mapping for initrd, it will be handled in VO. */
365
366

	/* Avoid kernel command line. */
367
368
	cmd_line  = (u64)boot_params->ext_cmd_line_ptr << 32;
	cmd_line |= boot_params->hdr.cmd_line_ptr;
369
370
	/* Calculate size of cmd_line. */
	ptr = (char *)(unsigned long)cmd_line;
371
	for (cmd_line_size = 0; ptr[cmd_line_size++];)
372
		;
373
374
	mem_avoid[MEM_AVOID_CMDLINE].start = cmd_line;
	mem_avoid[MEM_AVOID_CMDLINE].size = cmd_line_size;
375
376
	add_identity_map(mem_avoid[MEM_AVOID_CMDLINE].start,
			 mem_avoid[MEM_AVOID_CMDLINE].size);
377

378
379
380
	/* Avoid boot parameters. */
	mem_avoid[MEM_AVOID_BOOTPARAMS].start = (unsigned long)boot_params;
	mem_avoid[MEM_AVOID_BOOTPARAMS].size = sizeof(*boot_params);
381
382
383
384
385
	add_identity_map(mem_avoid[MEM_AVOID_BOOTPARAMS].start,
			 mem_avoid[MEM_AVOID_BOOTPARAMS].size);

	/* We don't need to set a mapping for setup_data. */

386
	/* Mark the memmap regions we need to avoid */
387
	handle_mem_memmap();
388

389
390
391
392
#ifdef CONFIG_X86_VERBOSE_BOOTUP
	/* Make sure video RAM can be used. */
	add_identity_map(0, PMD_SIZE);
#endif
393
394
}

395
396
397
398
399
400
/*
 * Does this memory vector overlap a known avoided area? If so, record the
 * overlap region with the lowest address.
 */
static bool mem_avoid_overlap(struct mem_vector *img,
			      struct mem_vector *overlap)
401
402
{
	int i;
403
	struct setup_data *ptr;
404
405
	unsigned long earliest = img->start + img->size;
	bool is_overlapping = false;
406
407

	for (i = 0; i < MEM_AVOID_MAX; i++) {
408
409
410
		if (mem_overlaps(img, &mem_avoid[i]) &&
		    mem_avoid[i].start < earliest) {
			*overlap = mem_avoid[i];
411
			earliest = overlap->start;
412
413
			is_overlapping = true;
		}
414
415
	}

416
	/* Avoid all entries in the setup_data linked list. */
417
	ptr = (struct setup_data *)(unsigned long)boot_params->hdr.setup_data;
418
419
420
	while (ptr) {
		struct mem_vector avoid;

421
		avoid.start = (unsigned long)ptr;
422
423
		avoid.size = sizeof(*ptr) + ptr->len;

424
425
		if (mem_overlaps(img, &avoid) && (avoid.start < earliest)) {
			*overlap = avoid;
426
			earliest = overlap->start;
427
428
			is_overlapping = true;
		}
429
430
431
432

		ptr = (struct setup_data *)(unsigned long)ptr->next;
	}

433
	return is_overlapping;
434
435
}

436
437
438
439
440
441
442
443
444
struct slot_area {
	unsigned long addr;
	int num;
};

#define MAX_SLOT_AREA 100

static struct slot_area slot_areas[MAX_SLOT_AREA];

445
static unsigned long slot_max;
446

447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
static unsigned long slot_area_index;

static void store_slot_info(struct mem_vector *region, unsigned long image_size)
{
	struct slot_area slot_area;

	if (slot_area_index == MAX_SLOT_AREA)
		return;

	slot_area.addr = region->start;
	slot_area.num = (region->size - image_size) /
			CONFIG_PHYSICAL_ALIGN + 1;

	if (slot_area.num > 0) {
		slot_areas[slot_area_index++] = slot_area;
		slot_max += slot_area.num;
	}
}

466
467
static unsigned long slots_fetch_random(void)
{
468
469
470
	unsigned long slot;
	int i;

471
472
473
474
	/* Handle case of no slots stored. */
	if (slot_max == 0)
		return 0;

475
	slot = kaslr_get_random_long("Physical") % slot_max;
476
477
478
479
480
481
482
483
484
485
486
487

	for (i = 0; i < slot_area_index; i++) {
		if (slot >= slot_areas[i].num) {
			slot -= slot_areas[i].num;
			continue;
		}
		return slot_areas[i].addr + slot * CONFIG_PHYSICAL_ALIGN;
	}

	if (i == slot_area_index)
		debug_putstr("slots_fetch_random() failed!?\n");
	return 0;
488
489
}

490
static void process_mem_region(struct mem_vector *entry,
491
492
493
			       unsigned long minimum,
			       unsigned long image_size)
{
494
495
	struct mem_vector region, overlap;
	struct slot_area slot_area;
496
	unsigned long start_orig, end;
497
	struct mem_vector cur_entry;
498

499
	/* On 32-bit, ignore entries entirely above our maximum. */
500
	if (IS_ENABLED(CONFIG_X86_32) && entry->start >= KERNEL_IMAGE_SIZE)
501
502
503
		return;

	/* Ignore entries entirely below our minimum. */
504
	if (entry->start + entry->size < minimum)
505
506
		return;

507
	/* Ignore entries above memory limit */
508
509
	end = min(entry->size + entry->start, mem_limit);
	if (entry->start >= end)
510
		return;
511
512
	cur_entry.start = entry->start;
	cur_entry.size = end - entry->start;
513

514
	region.start = cur_entry.start;
515
	region.size = cur_entry.size;
516

517
518
519
	/* Give up if slot area array is full. */
	while (slot_area_index < MAX_SLOT_AREA) {
		start_orig = region.start;
520

521
522
523
		/* Potentially raise address to minimum location. */
		if (region.start < minimum)
			region.start = minimum;
524

525
526
		/* Potentially raise address to meet alignment needs. */
		region.start = ALIGN(region.start, CONFIG_PHYSICAL_ALIGN);
527

528
		/* Did we raise the address above the passed in memory entry? */
529
		if (region.start > cur_entry.start + cur_entry.size)
530
			return;
531

532
533
		/* Reduce size by any delta from the original address. */
		region.size -= region.start - start_orig;
534

535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
		/* On 32-bit, reduce region size to fit within max size. */
		if (IS_ENABLED(CONFIG_X86_32) &&
		    region.start + region.size > KERNEL_IMAGE_SIZE)
			region.size = KERNEL_IMAGE_SIZE - region.start;

		/* Return if region can't contain decompressed kernel */
		if (region.size < image_size)
			return;

		/* If nothing overlaps, store the region and return. */
		if (!mem_avoid_overlap(&region, &overlap)) {
			store_slot_info(&region, image_size);
			return;
		}

		/* Store beginning of region if holds at least image_size. */
		if (overlap.start > region.start + image_size) {
			struct mem_vector beginning;

			beginning.start = region.start;
			beginning.size = overlap.start - region.start;
			store_slot_info(&beginning, image_size);
		}

		/* Return if overlap extends to or past end of region. */
		if (overlap.start + overlap.size >= region.start + region.size)
			return;

		/* Clip off the overlapping region and start over. */
		region.size -= overlap.start - region.start + overlap.size;
		region.start = overlap.start + overlap.size;
566
567
568
	}
}

569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
#ifdef CONFIG_EFI
/*
 * Returns true if mirror region found (and must have been processed
 * for slots adding)
 */
static bool
process_efi_entries(unsigned long minimum, unsigned long image_size)
{
	struct efi_info *e = &boot_params->efi_info;
	bool efi_mirror_found = false;
	struct mem_vector region;
	efi_memory_desc_t *md;
	unsigned long pmap;
	char *signature;
	u32 nr_desc;
	int i;

	signature = (char *)&e->efi_loader_signature;
	if (strncmp(signature, EFI32_LOADER_SIGNATURE, 4) &&
	    strncmp(signature, EFI64_LOADER_SIGNATURE, 4))
		return false;

#ifdef CONFIG_X86_32
	/* Can't handle data above 4GB at this time */
	if (e->efi_memmap_hi) {
		warn("EFI memmap is above 4GB, can't be handled now on x86_32. EFI should be disabled.\n");
		return false;
	}
	pmap =  e->efi_memmap;
#else
	pmap = (e->efi_memmap | ((__u64)e->efi_memmap_hi << 32));
#endif

	nr_desc = e->efi_memmap_size / e->efi_memdesc_size;
	for (i = 0; i < nr_desc; i++) {
		md = efi_early_memdesc_ptr(pmap, e->efi_memdesc_size, i);
		if (md->attribute & EFI_MEMORY_MORE_RELIABLE) {
			efi_mirror_found = true;
607
			break;
608
609
610
		}
	}

611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
	for (i = 0; i < nr_desc; i++) {
		md = efi_early_memdesc_ptr(pmap, e->efi_memdesc_size, i);

		/*
		 * Here we are more conservative in picking free memory than
		 * the EFI spec allows:
		 *
		 * According to the spec, EFI_BOOT_SERVICES_{CODE|DATA} are also
		 * free memory and thus available to place the kernel image into,
		 * but in practice there's firmware where using that memory leads
		 * to crashes.
		 *
		 * Only EFI_CONVENTIONAL_MEMORY is guaranteed to be free.
		 */
		if (md->type != EFI_CONVENTIONAL_MEMORY)
			continue;

		if (efi_mirror_found &&
		    !(md->attribute & EFI_MEMORY_MORE_RELIABLE))
			continue;

		region.start = md->phys_addr;
		region.size = md->num_pages << EFI_PAGE_SHIFT;
		process_mem_region(&region, minimum, image_size);
		if (slot_area_index == MAX_SLOT_AREA) {
			debug_putstr("Aborted EFI scan (slot_areas full)!\n");
			break;
		}
	}
	return true;
641
642
643
644
645
646
647
648
649
}
#else
static inline bool
process_efi_entries(unsigned long minimum, unsigned long image_size)
{
	return false;
}
#endif

650
651
static void process_e820_entries(unsigned long minimum,
				 unsigned long image_size)
652
653
{
	int i;
654
	struct mem_vector region;
655
656
657
658
659
660
661
662
	struct boot_e820_entry *entry;

	/* Verify potential e820 positions, appending to slots list. */
	for (i = 0; i < boot_params->e820_entries; i++) {
		entry = &boot_params->e820_table[i];
		/* Skip non-RAM entries. */
		if (entry->type != E820_TYPE_RAM)
			continue;
663
664
		region.start = entry->addr;
		region.size = entry->size;
665
		process_mem_region(&region, minimum, image_size);
666
667
668
669
670
671
		if (slot_area_index == MAX_SLOT_AREA) {
			debug_putstr("Aborted e820 scan (slot_areas full)!\n");
			break;
		}
	}
}
672

673
674
675
static unsigned long find_random_phys_addr(unsigned long minimum,
					   unsigned long image_size)
{
676
677
	/* Check if we had too many memmaps. */
	if (memmap_too_large) {
678
		debug_putstr("Aborted memory entries scan (more than 4 memmap= args)!\n");
679
680
681
		return 0;
	}

682
683
684
	/* Make sure minimum is aligned. */
	minimum = ALIGN(minimum, CONFIG_PHYSICAL_ALIGN);

685
686
687
	if (process_efi_entries(minimum, image_size))
		return slots_fetch_random();

688
	process_e820_entries(minimum, image_size);
689
690
691
	return slots_fetch_random();
}

692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
static unsigned long find_random_virt_addr(unsigned long minimum,
					   unsigned long image_size)
{
	unsigned long slots, random_addr;

	/* Make sure minimum is aligned. */
	minimum = ALIGN(minimum, CONFIG_PHYSICAL_ALIGN);
	/* Align image_size for easy slot calculations. */
	image_size = ALIGN(image_size, CONFIG_PHYSICAL_ALIGN);

	/*
	 * There are how many CONFIG_PHYSICAL_ALIGN-sized slots
	 * that can hold image_size within the range of minimum to
	 * KERNEL_IMAGE_SIZE?
	 */
	slots = (KERNEL_IMAGE_SIZE - minimum - image_size) /
		 CONFIG_PHYSICAL_ALIGN + 1;

710
	random_addr = kaslr_get_random_long("Virtual") % slots;
711
712
713
714

	return random_addr * CONFIG_PHYSICAL_ALIGN + minimum;
}

715
716
717
718
/*
 * Since this function examines addresses much more numerically,
 * it takes the input and output pointers as 'unsigned long'.
 */
719
720
721
722
723
void choose_random_location(unsigned long input,
			    unsigned long input_size,
			    unsigned long *output,
			    unsigned long output_size,
			    unsigned long *virt_addr)
724
{
725
	unsigned long random_addr, min_addr;
726
727

	if (cmdline_find_option_bool("nokaslr")) {
728
		warn("KASLR disabled: 'nokaslr' on cmdline.");
729
		return;
730
731
	}

732
	boot_params->hdr.loadflags |= KASLR_FLAG;
733

734
735
736
	/* Prepare to add new identity pagetables on demand. */
	initialize_identity_maps();

737
	/* Record the various known unsafe memory ranges. */
738
	mem_avoid_init(input, input_size, *output);
739

740
741
742
743
744
745
746
	/*
	 * Low end of the randomization range should be the
	 * smaller of 512M or the initial kernel image
	 * location:
	 */
	min_addr = min(*output, 512UL << 20);

747
	/* Walk available memory entries to find a random address. */
748
	random_addr = find_random_phys_addr(min_addr, output_size);
749
	if (!random_addr) {
750
		warn("Physical KASLR disabled: no suitable memory region!");
751
752
753
754
755
756
	} else {
		/* Update the new physical address location. */
		if (*output != random_addr) {
			add_identity_map(random_addr, output_size);
			*output = random_addr;
		}
757
758
759
760
761
762
763
764
765

		/*
		 * This loads the identity mapping page table.
		 * This should only be done if a new physical address
		 * is found for the kernel, otherwise we should keep
		 * the old page table to make it be like the "nokaslr"
		 * case.
		 */
		finalize_identity_maps();
766
767
	}

768
769
770
771
772

	/* Pick random virtual address starting from LOAD_PHYSICAL_ADDR. */
	if (IS_ENABLED(CONFIG_X86_64))
		random_addr = find_random_virt_addr(LOAD_PHYSICAL_ADDR, output_size);
	*virt_addr = random_addr;
773
}