GNU Emacs LD_PRELOAD build hack

GNU Emacs LD_PRELOAD build hack

[Rich Felker]

[-- Attachment #1: Type: text/plain, Size: 4812 bytes --]

Background: GNU Emacs' build process depends on the ability of the
build-stage binary (temacs) to "dump" itself to a new executable file
containing preloaded lisp objects/state in its .data segment. This
process is highly non-portable even in principle; in practice, the big
issue is where malloc allocations end up. They need to all be
contiguous just above the .data/.bss in the original binary so that
they can become part of the .data mapping. Against musl's malloc, this
has two major ways it can fail:

1. musl uses mmap for large allocations (roughly, > 128-256k) and has
   no mechanism for obtaining such large objects from the main
   brk-based heap or even requesting such (whereas glibc has mallopt
   and/or an environment variable to control the mmap threshold, and
   emacs cheats and uses that to control glibc).

2. musl reclaims the gaps around the edges of writable mappings in the
   main program and shared libraries and uses them for malloc. If
   these are in shared libraries, they won't be dumped at all, and if
   they're in the main program, they actually overlap with .text on
   disk (the same page is mapped twice; this is the cause of the gaps)
   and thus the .text, not the heap data, gets written out to disk by
   the dumper.

Emacs provides its own malloc replacement and tries to use it by
default, but this has to be disabled with musl, since replacing malloc
in dynamic programs doesn't work (and static binaries don't work right
at all with emacs' dumper because libc state would get included in the
dump -- state which is "intentionally lost" when it resides in a
shared library whose state isn't dumped).

The right solution: As I discussed on the emacs-devel list nearly a
year ago, the right solution is to get rid of the non-portable code in
emacs, dumping the lisp heap and its data (rather than the whole
program) to a file and either mmapping it at runtime (and possibly
relocating pointers in it, if the new location it's loaded at differs)
or converting it to a C source file that's compiled and linked and for
which the (static or dynamic) linker can perform relocations at
link/load time. This solution also solves a number of other serious
issues related to the dumper, including its incompatibility with PIE
binaries.

Unfortunately, the right solution requires a significant overhaul by
someone with expertise in emacs internals, and it's not practical in
the short term. Meanwhile, we have users wanting emacs on musl-based
distros (myself included).

So, here's an alternate solution.

The hack: The basic trick is that we need to satisfy emacs assumptions
about malloc, but only at build (dumping) time, not permanently. My
first thought was to build emacs in the presence of a modified musl
libc.so whose malloc never uses mmap (issue 1) and never reclaims gaps
at the edge of writable mappings (issue 2), but then I realized we
could achieve the same thing without having to build a custom libc.so
at package-build time by exploiting LD_PRELOAD.

The attached file is my current draft of the LD_PRELOAD module to be
loaded when running temacs to dump. In short, what it does is:

- Throws away (wastes/leaks) and retries whenever it gets a result
  from malloc that's not between the initial value of the brk and the
  current (after malloc) value of the brk, i.e. anything not on the
  "main heap" that's contiguous with .bss/.data.

- For large allocations that would be serviced by mmap, and for which
  musl's malloc won't/can't allocate from the "main heap", allocate
  64k at a time, many times, from the heap, and exploit knowledge of
  the malloc chunk header/footer structures to paste them together to
  make one large chunk. (If the wrapper can't get contiguous chunks
  for this, then malloc will just fail and report failure.)

The first part of the hack is simple and clean. The second part is
hideously ugly, but the key point to realize is that it's only making
an assumption about the library implementation used at build time, not
when the emacs binary is later run. The dumped emacs does not include
any code from the LD_PRELOAD hack and it does not depend on the
assumptions made in the hack still being valid for the libc.so that's
used at runtime. If these assumptions do become invalidated (unlikely,
but possible), then all that's needed to get emacs building again is
updating the hack (or just building with an outdated libc.so). With
any luck, the non-portable dumping in emacs will be fixed long before
this is needed, anyway.

Over the next few days I hope to be working with people doing Alpine
Linux (and/or other dists) packaging to get this turned into a clean,
reproducible build procedure for GNU-Emacs-on-musl. In the mean time,
the source for the hack is attached in case anyone wants to start
hacking on it.

Rich

[-- Attachment #2: preload.c --]
[-- Type: text/plain, Size: 1798 bytes --]

#include <pthread.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <dlfcn.h>
#include <unistd.h>

static void *(*real_malloc)(size_t);
static void *initial_brk;

static pthread_once_t once_control[1];
static void once_func()
{
	real_malloc = dlsym(RTLD_NEXT, "malloc");
	initial_brk = sbrk(0);
}

static int cmp(const void *a, const void *b)
{
	void *aa = *(void **)a, *bb = *(void **)b;
	return aa < bb ? -1 : aa > bb ? 1 : 0;
}

void *malloc(size_t n)
{
	size_t i, j, k;
	pthread_once(once_control, once_func);
	if (n < 100000 || n > (size_t)-1/2) {
		void *p;
		do p = real_malloc(n);
		while (p > sbrk(0) || (p && p < initial_brk));
		return p;
	}
	size_t cnt = n/16384;
	void **list = real_malloc(sizeof *list * cnt);
	if (!list) return 0;
	for (i=0; i<cnt; i++) list[i] = 0;
	for (i=0; i<cnt; i++) {
		list[i] = real_malloc(65536 - 2*sizeof(size_t));
		if (!list[i]) goto fail;
		if (i<cnt/4) continue;
		size_t base = 0;
		qsort(list, i+1, sizeof(void *), cmp);
		for (j=0; j<i; j++) {
			char *p = list[base];
			char *s = list[j];
			char *z = list[j+1];
			if (z-s > 65536) {
				base = j+1;
				continue;
			}
			if (z-p < n+64) {
				continue;
			}
			for (k=0; k<base; k++) free(list[k]);
			*(size_t *)(p-sizeof(size_t)) = z-p | 1;
			*(size_t *)(z-2*sizeof(size_t)) = z-p | 1;
			for (k=j+1; k<i+1; k++) free(list[k]);
			free(list);
			return p;
		}
	}
fail:
	for (i=0; i<cnt; i++) free(list[i]);
	free(list);
	return 0;
}

void *calloc(size_t n, size_t m)
{
	if ((size_t)-1/n <= m) n *= m;
	else n = (size_t)-1;
	void *p = malloc(n);
	if (p) memset(p, 0, n);
	return p;
}

void *realloc(void *p, size_t n)
{
	void *q = malloc(n);
	if (!q) return 0;
	size_t l = *(size_t *)((char *)p - sizeof(size_t)) & -8;
	memcpy(q, p, l<n ? l : n);
	free(p);
	return q;
}

Re: GNU Emacs LD_PRELOAD build hack

[stephen Turner]

[-- Attachment #1: Type: text/plain, Size: 2814 bytes --]

On Feb 2, 2015 10:54 PM, "Rich Felker" <dalias@libc.org> wrote:
>
> Background: GNU Emacs' build process depends on the ability of the
> build-stage binary (temacs) to "dump" itself to a new executable file
> containing preloaded lisp objects/state in its .data segment. This
> process is highly non-portable even in principle; in practice, the big
> issue is where malloc allocations end up. They need to all be
> contiguous just above the .data/.bss in the original binary so that
> they can become part of the .data mapping. Against musl's malloc, this
> has two major ways it can fail:
>
> 1. musl uses mmap for large allocations (roughly, > 128-256k) and has
>    no mechanism for obtaining such large objects from the main
>    brk-based heap or even requesting such (whereas glibc has mallopt
>    and/or an environment variable to control the mmap threshold, and
>    emacs cheats and uses that to control glibc).
>
> 2. musl reclaims the gaps around the edges of writable mappings in the
>    main program and shared libraries and uses them for malloc. If
>    these are in shared libraries, they won't be dumped at all, and if
>    they're in the main program, they actually overlap with .text on
>    disk (the same page is mapped twice; this is the cause of the gaps)
>    and thus the .text, not the heap data, gets written out to disk by
>    the dumper.
>
> Emacs provides its own malloc replacement and tries to use it by
> default, but this has to be disabled with musl, since replacing malloc
> in dynamic programs doesn't work (and static binaries don't work right
> at all with emacs' dumper because libc state would get included in the
> dump -- state which is "intentionally lost" when it resides in a
> shared library whose state isn't dumped).
>
> The right solution: As I discussed on the emacs-devel list nearly a
> year ago, the right solution is to get rid of the non-portable code in
> emacs, dumping the lisp heap and its data (rather than the whole
> program) to a file and either mmapping it at runtime (and possibly
> relocating pointers in it, if the new location it's loaded at differs)
> or converting it to a C source file that's compiled and linked and for
> which the (static or dynamic) linker can perform relocations at
> link/load time. This solution also solves a number of other serious
> issues related to the dumper, including its incompatibility with PIE
> binaries.
>
> Unfortunately, the right solution requires a significant overhaul by
> someone with expertise in emacs internals, and it's not practical in
> the short term. Meanwhile, we have users wanting emacs on musl-based
> distros (myself included).
>
> So, here's an alternate solution.

I think there was a guy on the toybox list working on editors and might
have a emacs for you. Onefang comes to mind.

[-- Attachment #2: Type: text/html, Size: 3383 bytes --]

Re: GNU Emacs LD_PRELOAD build hack

[Rich Felker]

[-- Attachment #1: Type: text/plain, Size: 2836 bytes --]

On Mon, Feb 02, 2015 at 10:54:07PM -0500, Rich Felker wrote:
> The right solution: As I discussed on the emacs-devel list nearly a
> year ago, the right solution is to get rid of the non-portable code in
> emacs, dumping the lisp heap and its data (rather than the whole
> program) to a file and either mmapping it at runtime (and possibly
> relocating pointers in it, if the new location it's loaded at differs)
> or converting it to a C source file that's compiled and linked and for
> which the (static or dynamic) linker can perform relocations at
> link/load time. This solution also solves a number of other serious
> issues related to the dumper, including its incompatibility with PIE
> binaries.

Apparently since the discussion last year, the emacs folks went
forward with one of their proposed fixes -- not the best possible one,
but a good one nonetheless. These changes aren't in any release and
won't be for quite a while I expect, but using emacs git master, I was
able to build successfully with the attached patch and no hacks.

> So, here's an alternate solution.
> 
> The hack: The basic trick is that we need to satisfy emacs assumptions
> about malloc, but only at build (dumping) time, not permanently. My
> first thought was to build emacs in the presence of a modified musl
> libc.so whose malloc never uses mmap (issue 1) and never reclaims gaps
> at the edge of writable mappings (issue 2), but then I realized we
> could achieve the same thing without having to build a custom libc.so
> at package-build time by exploiting LD_PRELOAD.

Unfortunately there was another invalid assumption emacs was making
that I missed, which only came up when I tried to build on 64-bit:
under some conditions, it actually passes the pre-dump objects
obtained from malloc to the post-dump realloc/free functions. This
results in horrible heap-structure corruption and I have no idea
how/why it's working on glibc since it should break there too. Anyway,
discussing this on emacs-devel led to the much better solution using
git master, but I do also have a fixed based on the previously
reported LD_PRELOAD hack; it just depends on patching emacs not to
pass these pre-dump pointers to realloc/free. I'm attaching that patch
too in case anyone is interested.

Attached files:

emacs_alloc_invalid_frees.diff is the patch to supplement the
LD_PRELOAD hack on emacs-24.x.

emacs-master-musl.diff is the (lazy) patch for emacs git master
(presently commit 4188e3cc2bc69e75d4387b369e72e89fecc46a86) to make it
build on musl. It's not acceptable for upstream at this time because
the changes made are mostly unconditional. If anyone is willing to put
this into a form where it could be submitted upstream, I would very
much appreciate it; otherwise, distros packaging emacs can just use
the patch as-is or with minor changes.

Rich

[-- Attachment #2: emacs-master-musl.diff --]
[-- Type: text/plain, Size: 2295 bytes --]

--- emacs-4188e3cc2bc69e75d4387b369e72e89fecc46a86/configure.ac
+++ emacs/configure.ac
@@ -2092,7 +2092,7 @@
 
 system_malloc=$emacs_cv_sanitize_address
 
-hybrid_malloc=
+hybrid_malloc=yes
 
 case "$opsys" in
   ## darwin ld insists on the use of malloc routines in the System framework.
--- emacs-4188e3cc2bc69e75d4387b369e72e89fecc46a86/src/Makefile.in
+++ emacs/src/Makefile.in
@@ -373,6 +373,7 @@
 	region-cache.o sound.o atimer.o \
 	doprnt.o intervals.o textprop.o composite.o xml.o $(NOTIFY_OBJ) \
 	profiler.o decompress.o \
+	sheap.o \
 	$(MSDOS_OBJ) $(MSDOS_X_OBJ) $(NS_OBJ) $(CYGWIN_OBJ) $(FONT_OBJ) \
 	$(W32_OBJ) $(WINDOW_SYSTEM_OBJ) $(XGSELOBJ)
 obj = $(base_obj) $(NS_OBJC_OBJ)
--- emacs-4188e3cc2bc69e75d4387b369e72e89fecc46a86/src/gmalloc.c
+++ emacs/src/gmalloc.c
@@ -72,7 +72,7 @@
 #define free gfree
 #endif  /* HYBRID_MALLOC */
 
-#ifdef CYGWIN
+//#ifdef CYGWIN
 extern void *bss_sbrk (ptrdiff_t size);
 extern int bss_sbrk_did_unexec;
 extern char bss_sbrk_buffer[];
@@ -80,7 +80,7 @@
 #define DUMPED bss_sbrk_did_unexec
 #define ALLOCATED_BEFORE_DUMPING(P) \
   ((P) < bss_sbrk_buffer_end && (P) >= (void *) bss_sbrk_buffer)
-#endif
+//#endif
 
 #ifdef	__cplusplus
 extern "C"
@@ -1525,16 +1525,19 @@
 __default_morecore (ptrdiff_t increment)
 {
   void *result;
-#if defined (CYGWIN)
+//#if defined (CYGWIN)
   if (!DUMPED)
     {
       return bss_sbrk (increment);
     }
-#endif
+//#endif
+#if 0
   result = (void *) __sbrk (increment);
   if (result == (void *) -1)
     return NULL;
   return result;
+#endif
+  return NULL;
 }
 /* Copyright (C) 1991, 92, 93, 94, 95, 96 Free Software Foundation, Inc.
 
--- emacs-4188e3cc2bc69e75d4387b369e72e89fecc46a86/src/print.c
+++ emacs/src/print.c
@@ -755,7 +755,7 @@
   print_output_debug_flag = x;
 }
 
-#if defined (GNU_LINUX)
+#if defined (GNU_LINUX) && defined (__GLIBC__)
 
 /* This functionality is not vitally important in general, so we rely on
    non-portable ability to use stderr as lvalue.  */
--- emacs-4188e3cc2bc69e75d4387b369e72e89fecc46a86/src/unexelf.c
+++ emacs/src/unexelf.c
@@ -632,6 +632,9 @@
   off_t new_file_size;
   void *new_break;
 
+  extern int bss_sbrk_did_unexec;
+  bss_sbrk_did_unexec = 1;
+
   /* Pointers to the base of the image of the two files.  */
   caddr_t old_base, new_base;
 


[-- Attachment #3: emacs_alloc_invalid_frees.diff --]
[-- Type: text/plain, Size: 1258 bytes --]

--- emacs-24.3.orig/src/alloc.c
+++ emacs-24.3/src/alloc.c
@@ -47,6 +47,13 @@
 
 #include <verify.h>
 
+static void *initial_brk;
+__attribute__((__constructor__))
+static void init()
+{
+	initial_brk = sbrk(0);
+}
+
 /* GC_CHECK_MARKED_OBJECTS means do sanity checks on allocated objects.
    Doable only if GC_MARK_STACK.  */
 #if ! GC_MARK_STACK
@@ -699,6 +706,14 @@
 {
   void *val;
 
+  if (block && block < initial_brk) {
+    size_t len = (char *)initial_brk - (char *)block;
+    if (len > size) len = size;
+    void *p = xmalloc(size);
+    memcpy(p, block, len);
+    return p;
+  }
+
   MALLOC_BLOCK_INPUT;
   /* We must call malloc explicitly when BLOCK is 0, since some
      reallocs don't do this.  */
@@ -720,6 +735,7 @@
 void
 xfree (void *block)
 {
+  if (block < initial_brk) return;
   if (!block)
     return;
   MALLOC_BLOCK_INPUT;
@@ -910,6 +926,7 @@
 static void
 lisp_free (void *block)
 {
+  if (block < initial_brk) return;
   MALLOC_BLOCK_INPUT;
   free (block);
 #if GC_MARK_STACK && !defined GC_MALLOC_CHECK
@@ -1117,6 +1134,8 @@
 {
   struct ablock *ablock = block;
   struct ablocks *abase = ABLOCK_ABASE (ablock);
+
+  if (block < initial_brk) return;
 
   MALLOC_BLOCK_INPUT;
 #if GC_MARK_STACK && !defined GC_MALLOC_CHECK