--- a/tools/xcutils/readnotes.c
+++ b/tools/xcutils/readnotes.c
@@ -162,6 +162,12 @@ static unsigned print_notes(struct elf_b
 		case XEN_ELFNOTE_PHYS32_ENTRY:
 			print_numeric_note("PHYS32_ENTRY", elf , note);
 			break;
+		case XEN_ELFNOTE_RANDOMIZE_LIMIT:
+			print_numeric_note("RANDOMIZE_LIMIT", elf, note);
+			break;
+		case XEN_ELFNOTE_RANDOMIZE_STRIDE:
+			print_numeric_note("RANDOMIZE_STRIDE", elf, note);
+			break;
 		default:
 			printf("unknown note type %#x\n",
 			       (unsigned)elf_uval(elf, note, type));
--- a/xen/common/libelf/libelf-dominfo.c
+++ b/xen/common/libelf/libelf-dominfo.c
@@ -109,6 +109,8 @@ elf_errorstatus elf_xen_parse_note(struc
         [XEN_ELFNOTE_INIT_P2M] = { "INIT_P2M", 0},
         [XEN_ELFNOTE_PADDR_OFFSET] = { "PADDR_OFFSET", 0},
         [XEN_ELFNOTE_HV_START_LOW] = { "HV_START_LOW", 0},
+        [XEN_ELFNOTE_RANDOMIZE_LIMIT] = { "RANDOMIZE_LIMIT", 0},
+        [XEN_ELFNOTE_RANDOMIZE_STRIDE] = { "RANDOMIZE_STRIDE", 0},
         [XEN_ELFNOTE_XEN_VERSION] = { "XEN_VERSION", 1},
         [XEN_ELFNOTE_GUEST_OS] = { "GUEST_OS", 1},
         [XEN_ELFNOTE_GUEST_VERSION] = { "GUEST_VERSION", 1},
@@ -203,6 +205,12 @@ elf_errorstatus elf_xen_parse_note(struc
     case XEN_ELFNOTE_HV_START_LOW:
         parms->virt_hv_start_low = val;
         break;
+    case XEN_ELFNOTE_RANDOMIZE_LIMIT:
+        parms->randomize_limit = val;
+        break;
+    case XEN_ELFNOTE_RANDOMIZE_STRIDE:
+        parms->randomize_stride = val;
+        break;
 
     case XEN_ELFNOTE_FEATURES:
         if ( elf_xen_parse_features(str, parms->f_supported,
@@ -404,6 +412,8 @@ static elf_errorstatus elf_xen_note_chec
 static elf_errorstatus elf_xen_addr_calc_check(struct elf_binary *elf,
                                    struct elf_dom_parms *parms)
 {
+    uint64_t r = 0;
+
     if ( (parms->elf_paddr_offset != UNSET_ADDR) &&
          (parms->virt_base == UNSET_ADDR) )
     {
@@ -418,6 +428,9 @@ static elf_errorstatus elf_xen_addr_calc
         parms->virt_base = 0;
         elf_msg(elf, "%s: VIRT_BASE unset, using 0x%" PRIx64 "\n",
                 __FUNCTION__, parms->virt_base);
+
+        /* Disable randomization if we had to guess virt_base. */
+        parms->randomize_stride = 0;
     }
 
     /*
@@ -439,6 +452,49 @@ static elf_errorstatus elf_xen_addr_calc
                 __FUNCTION__, parms->elf_paddr_offset);
     }
 
+    if ( parms->randomize_limit != UNSET_ADDR && parms->randomize_stride )
+    {
+        unsigned int i, n;
+
+        if ( parms->randomize_limit < elf->pstart )
+            r = (elf->pstart - parms->randomize_limit) /
+                parms->randomize_stride;
+        else if ( parms->randomize_limit > elf->pend )
+            r = (parms->randomize_limit - elf->pend) /
+                parms->randomize_stride;
+
+        r = (get_random() % (r + 1)) * parms->randomize_stride;
+
+        if ( parms->randomize_limit < elf->pstart )
+            r = -r;
+
+        elf_msg(elf, "%s: randomization displacement %#" PRIx64 "\n",
+                __FUNCTION__, r);
+
+        elf->pstart += r;
+        elf->pend += r;
+        parms->virt_hypercall += r;
+
+        /* Adjust program headers for elf_load_binary() (also see there). */
+        n = elf_uval(elf, elf->ehdr, e_phnum);
+        for ( i = 0; i < n; ++i )
+        {
+            ELF_HANDLE_DECL(elf_phdr) phdr = elf_phdr_by_index(elf, i);
+
+            if ( !elf_access_ok(elf, ELF_HANDLE_PTRVAL(phdr), 1) )
+                break;
+            if ( !elf_phdr_is_loadable(elf, phdr) )
+                continue;
+            elf_store_field(elf, phdr, p_paddr,
+                            elf_uval(elf, phdr, p_paddr) + r);
+            /*
+             * Don't update p_vaddr: We don't use it, and at least various
+             * 64-bit Linux versions have their per-CPU data outside the
+             * "normal" VA range (and that VA must not be adjusted).
+             */
+        }
+    }
+
     parms->virt_offset = parms->virt_base - parms->elf_paddr_offset;
     parms->virt_kstart = elf->pstart + parms->virt_offset;
     parms->virt_kend   = elf->pend   + parms->virt_offset;
@@ -446,6 +502,8 @@ static elf_errorstatus elf_xen_addr_calc
     if ( parms->virt_entry == UNSET_ADDR )
         parms->virt_entry = elf_uval(elf, elf->ehdr, e_entry);
 
+    parms->virt_entry += r;
+
     if ( parms->bsd_symtab )
     {
         elf_parse_bsdsyms(elf, elf->pend);
@@ -504,6 +562,7 @@ elf_errorstatus elf_xen_parse(struct elf
     parms->p2m_base = UNSET_ADDR;
     parms->elf_paddr_offset = UNSET_ADDR;
     parms->phys_entry = UNSET_ADDR32;
+    parms->randomize_limit = UNSET_ADDR;
 
     /* Find and parse elf notes. */
     count = elf_phdr_count(elf);
--- a/xen/common/libelf/libelf-private.h
+++ b/xen/common/libelf/libelf-private.h
@@ -86,6 +86,8 @@ do { strncpy((d),(s),sizeof((d))-1);
      (d)[sizeof((d))-1] = '\0';                 \
 } while (0)
 
+#define get_random() ((unsigned int)rand())
+
 #endif
 
 #undef memcpy
--- a/xen/include/public/elfnote.h
+++ b/xen/include/public/elfnote.h
@@ -210,9 +210,23 @@
 #define XEN_ELFNOTE_PHYS32_ENTRY 18
 
 /*
+ * The physical address boundary of the randomization range.  The
+ * other range boundary is the physical address the image got linked
+ * for (i.e. the lowest ELF program header physical address), and the
+ * value here may be both below or above that value.
+ */
+#define XEN_ELFNOTE_RANDOMIZE_LIMIT 19
+
+/*
+ * The stride to use for base address randomization.  A value of zero
+ * here has the same effect as this note being absent.
+ */
+#define XEN_ELFNOTE_RANDOMIZE_STRIDE 20
+
+/*
  * The number of the highest elfnote defined.
  */
-#define XEN_ELFNOTE_MAX XEN_ELFNOTE_PHYS32_ENTRY
+#define XEN_ELFNOTE_MAX XEN_ELFNOTE_RANDOMIZE_STRIDE
 
 /*
  * System information exported through crash notes.
--- a/xen/include/xen/libelf.h
+++ b/xen/include/xen/libelf.h
@@ -435,6 +435,8 @@ struct elf_dom_parms {
     uint64_t virt_hv_start_low;
     uint64_t p2m_base;
     uint64_t elf_paddr_offset;
+    uint64_t randomize_limit;
+    uint64_t randomize_stride;
     uint32_t f_supported[XENFEAT_NR_SUBMAPS];
     uint32_t f_required[XENFEAT_NR_SUBMAPS];
     uint32_t phys_entry;