Dumper problems and a possible solutions

Dumper problems and a possible solutions

[Rich Felker]

Hi,

I've been trying to get current emacs working on musl libc based
systems, and running into trouble with the dumper. After a lot of
hacking I got it to work, and I'm hoping something based on the ideas
(not the implementation, which is hideously ugly) in my work could be
acceptable upstream.

By far the biggest problem is malloc-related. musl does not support
overriding malloc, so I'm building with system malloc. The emacs
dumper assumes all of the allocations that need to survive dumping end
up in the brk segment, which is not a constraint musl's allocator can
satisfy -- it has no support for huge allocations in brk, and will
sometimes opt to use mmap rather than brk for extending the heap for
small objects.

The hack I used to solve this is really simple: I added to alloc.c a
tiny allocator that just uses a giant static buffer which gets used
for lisp object allocations prior to dumping (it has an extern flag
that the dumper sets to indicate whether this code is running prior to
dumping or afterwards). With free being a NOP, as it is in my
implementation right now, I had to make this buffer 400 megs; that's
the main reason the patch would be utterly unacceptable as-is. I
believe the problem could be solved by writing a trivial "early
malloc" implementation that uses a static buffer, but with proper
recycling of free areas.

There are also, however, at least two other issues which affect static
linking. Dynamic linking does not seem to be affected because the
dumper doesn't save libc's globals in the dynamic-linked case, and
these involve global state in libc:

One is that, with modern Linux kernels with brk randomization as part
of ASLR, dumping saves malloc's idea of the current brk, and when it
mismatches at runtime, malloc will either crash or "allocate" memory
that's not even mapped. Trying to work around this in musl is not
acceptable because it would penalize all programs with extra syscalls
whenever malloc has to expand the brk.

The other issue is that musl's clock_gettime and related functions
store the pointer to the vdso version of this function. Since the
kernel maps vdso at a random address, the stored value from before
dumping will not be valid when the dumped executable is run.

To solve ALL of the problems with the dumper (which seems to be a
recurring theme), I have a proposed design to make it fully portable
-- even moreso than xemacs "portable dumper" which is still an ugly
hack. The idea is simple: after loading all of the lisp objects that
need dumping, walk the lisp heap and output a representation for each
object as a giant static array in C source format, then compile and
link this new translation unit with the rest of the emacs .o files to
produce a final emacs binary. No hacks with binary formats would be
involved; everything would happen at the C source level. As part of
the lisp heap dumping, address references to other objects would have
to be relocated to refer to the object's position in the static array
rather than the original address at which the object resided when
created in temacs. That's some non-trivial work, but definitely no
prohibitive, and as a bonus, the generated address-constant references
in the static array would transform to load-address-relative
relocations for the linker, allowing emacs to be built as a
position-indepdendent executable (PIE) if desired.

Does this sound like a viable direction? I'm not an emacs hacker by
any means and don't think I'm qualified to do the lisp heap dumping
implementation, but I could certainly help with design or any issues
that arise during implementation if others are interested in working
on it.

If not, or if that's going to be a very long-term project, would a
cleaned-up version of my current solution be acceptable upstream?

Rich

Re: Dumper problems and a possible solutions

[Stefan Monnier]

> To solve ALL of the problems with the dumper (which seems to be a
> recurring theme), I have a proposed design to make it fully portable
> -- even moreso than xemacs "portable dumper" which is still an ugly
> hack. The idea is simple: after loading all of the lisp objects that
> need dumping, walk the lisp heap and output a representation for each
> object as a giant static array in C source format, then compile and
> link this new translation unit with the rest of the emacs .o files to
> produce a final emacs binary. No hacks with binary formats would be
> involved; everything would happen at the C source level. As part of
> the lisp heap dumping, address references to other objects would have
> to be relocated to refer to the object's position in the static array
> rather than the original address at which the object resided when
> created in temacs. That's some non-trivial work, but definitely no
> prohibitive, and as a bonus, the generated address-constant references
> in the static array would transform to load-address-relative
> relocations for the linker, allowing emacs to be built as a
> position-indepdendent executable (PIE) if desired.

Generating a big static C array against which to link sounds fine and
very portable, indeed.  I'm not sure how hard/easy the relocation could
turn out to be.  There's the problem of finding *all* the references,
and there's the problem that moving an object means that its "hash"
value changes.

> If not, or if that's going to be a very long-term project, would a
> cleaned-up version of my current solution be acceptable upstream?

Making the "dump" portable would be very welcome.  Generating a big
static C array sounds OK.  So whether the result is acceptable or not
will depend on what's needed to solve the problems linked to relocation.

Another option is to "dump" the heap into a binary file that we would
later on "mmap".


        Stefan

Re: Dumper problems and a possible solutions

[Rich Felker]

On Tue, Jun 24, 2014 at 03:27:39PM -0400, Stefan Monnier wrote:
> > To solve ALL of the problems with the dumper (which seems to be a
> > recurring theme), I have a proposed design to make it fully portable
> > -- even moreso than xemacs "portable dumper" which is still an ugly
> > hack. The idea is simple: after loading all of the lisp objects that
> > need dumping, walk the lisp heap and output a representation for each
> > object as a giant static array in C source format, then compile and
> > link this new translation unit with the rest of the emacs .o files to
> > produce a final emacs binary. No hacks with binary formats would be
> > involved; everything would happen at the C source level. As part of
> > the lisp heap dumping, address references to other objects would have
> > to be relocated to refer to the object's position in the static array
> > rather than the original address at which the object resided when
> > created in temacs. That's some non-trivial work, but definitely no
> > prohibitive, and as a bonus, the generated address-constant references
> > in the static array would transform to load-address-relative
> > relocations for the linker, allowing emacs to be built as a
> > position-indepdendent executable (PIE) if desired.
> 
> Generating a big static C array against which to link sounds fine and
> very portable, indeed.  I'm not sure how hard/easy the relocation could
> turn out to be.  There's the problem of finding *all* the references,
> and there's the problem that moving an object means that its "hash"
> value changes.

Thanks for the feedback. Can you elaborate on how/why the hash
changes, and where it's stored that would need to be updated? As far
as the relocation, my impression is that it would just need to be able
to identify pointers in lisp objects (this is already possible since
the GC needs to do it, right?), and rewrite them to (essentially)
"static_lisp_heap + offset_of_pointed_to_object" when writing the dump
out as a C array.

> > If not, or if that's going to be a very long-term project, would a
> > cleaned-up version of my current solution be acceptable upstream?
> 
> Making the "dump" portable would be very welcome.  Generating a big
> static C array sounds OK.  So whether the result is acceptable or not
> will depend on what's needed to solve the problems linked to relocation.
> 
> Another option is to "dump" the heap into a binary file that we would
> later on "mmap".

This is the xemacs "portable dumper" approach, and I believe it's
inferrior because it depends on being able to map back at the same
location. If the region is a page-aligned static buffer in the main
executable and you mmap over it with MAP_FIXED, this is safe for the
most part, but it's still incompatible with PIE. I think it would be
nice to solve this problem in a way that also makes PIE possible.

Rich

Re: Dumper problems and a possible solutions

[Stefan Monnier]

> Thanks for the feedback. Can you elaborate on how/why the hash
> changes, and where it's stored that would need to be updated?

When placing an object in a hash-table, the hashing function often just
uses the address as "the hash value".  So any hash-table that uses such
a hash-function will need to be rehashed after relocation.

> As far as the relocation, my impression is that it would just need to
> be able to identify pointers in lisp objects (this is already possible
> since the GC needs to do it, right?), and rewrite them to
> (essentially) "static_lisp_heap + offset_of_pointed_to_object" when
> writing the dump out as a C array.

Yes, the GC already knows how to find the references that are inside
Lisp objects, but there can also be references coming from global
variables (for sure) or non-Lisp data-structures or maybe from the stack
(not sure about those last two).

> This is the xemacs "portable dumper" approach, and I believe it's
> inferrior because it depends on being able to map back at the same
> location.

We could support relocation at mmap-time to solve this.
Neither solution is clearly superior to the other, it just depends on
you priority.  For me, either way would be an improvement over what we
have (tho, again, it might still depend on the constraints imposed by
the need to perform relocation).


        Stefan

Re: Dumper problems and a possible solutions

[Rich Felker]

On Tue, Jun 24, 2014 at 04:24:47PM -0400, Stefan Monnier wrote:
> > Thanks for the feedback. Can you elaborate on how/why the hash
> > changes, and where it's stored that would need to be updated?
> 
> When placing an object in a hash-table, the hashing function often just
> uses the address as "the hash value".  So any hash-table that uses such
> a hash-function will need to be rehashed after relocation.

I see. Is this hashing all at the C level, or is it happening in lisp
code? Can the lisp code even see the address value for lisp objects?
If it's purely at the C level I doubt it would be hard to re-do the
hashes but I obviously haven't read the relevant code.

> > As far as the relocation, my impression is that it would just need to
> > be able to identify pointers in lisp objects (this is already possible
> > since the GC needs to do it, right?), and rewrite them to
> > (essentially) "static_lisp_heap + offset_of_pointed_to_object" when
> > writing the dump out as a C array.
> 
> Yes, the GC already knows how to find the references that are inside
> Lisp objects, but there can also be references coming from global
> variables (for sure) or non-Lisp data-structures or maybe from the stack
> (not sure about those last two).

How does the GC avoid freeing objects that have these kinds of
references?

BTW, at the point of dumping, my impression is that there should not
be relevant references from the stack; the whole call frame at the
time of dumping is thrown away and replaced by the new invocation of
main. Conceptually, the dumper can be thought of as a longjmp back to
the start of main.

> > This is the xemacs "portable dumper" approach, and I believe it's
> > inferrior because it depends on being able to map back at the same
> > location.
> 
> We could support relocation at mmap-time to solve this.

Yes, but that's conceptually just as difficult as dumping to a C
array: you have to patch up all the addresses and the hash values will
change.

> Neither solution is clearly superior to the other, it just depends on
> you priority.  For me, either way would be an improvement over what we
> have (tho, again, it might still depend on the constraints imposed by
> the need to perform relocation).

I agree completely. The current situation makes it nearly impossible
to port emacs to a system that's not making strong guarantees about
its implementation internals, and (at least from my understanding
reading list archives) it's imposing ugly constraints on existing
implementations (glibc) not to change internals in ways that would
break emacs' dumper. I would really like to see fixing this issue
treated as a priority in the future direction of emacs.

Rich

Re: Dumper problems and a possible solutions

[Stefan Monnier]

>> > Thanks for the feedback. Can you elaborate on how/why the hash
>> > changes, and where it's stored that would need to be updated?
>> When placing an object in a hash-table, the hashing function often just
>> uses the address as "the hash value".  So any hash-table that uses such
>> a hash-function will need to be rehashed after relocation.
> I see. Is this hashing all at the C level, or is it happening in lisp
> code?

It's in C.

> Can the lisp code even see the address value for lisp objects?

It usually doesn't see it, but the `sxhash' function does return values
which can depend on the address of objects (not for cons cells or
arrays, but for objects such as processes, markers, buffer, overlays,
...).
I think it happens rarely enough that we can hope to be OK on this front.

> If it's purely at the C level I doubt it would be hard to re-do the
> hashes but I obviously haven't read the relevant code.

Indeed, we just need to rehash all the hash-tables we find while
traversing the heap.

>> Yes, the GC already knows how to find the references that are inside
>> Lisp objects, but there can also be references coming from global
>> variables (for sure) or non-Lisp data-structures or maybe from the stack
>> (not sure about those last two).
> How does the GC avoid freeing objects that have these kinds of
> references?

It knows about some of those pointers (via `staticpro' for global
variables and via conservative stack scanning for the stack).

> BTW, at the point of dumping, my impression is that there should not
> be relevant references from the stack;

That'd be my hope as well.

>> We could support relocation at mmap-time to solve this.
> Yes, but that's conceptually just as difficult as dumping to a C
> array: you have to patch up all the addresses and the hash values will
> change.

Agreed.  Relocation is the big issue and pretty much any technique we
may like to use will need to address the problem.
I wonder how smalltalk machines deal with it.

> I agree completely. The current situation makes it nearly impossible
> to port emacs to a system that's not making strong guarantees about
> its implementation internals, and (at least from my understanding
> reading list archives) it's imposing ugly constraints on existing
> implementations (glibc) not to change internals in ways that would
> break emacs' dumper. I would really like to see fixing this issue
> treated as a priority in the future direction of emacs.

It's been a latent problem for the last 20 years or so, but it rarely
bites, so it's not of terribly high priority in general, especially
since new systems don't show up very often.
But it's important enough that we might be willing to pay some price
(e.g. the relocation code will likely either require significant
changes to the GC code, or it will duplicate significant chunks of the
GC code).


        Stefan

Re: Dumper problems and a possible solutions

[Dmitry Antipov]

On 06/24/2014 09:19 PM, Rich Felker wrote:

> To solve ALL of the problems with the dumper (which seems to be a
> recurring theme), I have a proposed design to make it fully portable
> -- even moreso than xemacs "portable dumper" which is still an ugly
> hack. The idea is simple: after loading all of the lisp objects that
> need dumping, walk the lisp heap and output a representation for each
> object as a giant static array in C source format, then compile and
> link this new translation unit with the rest of the emacs .o files to
> produce a final emacs binary.

What about non-Lisp objects?

It's not too hard to walk through live (reachable) Lisp objects - this
is exactly what GC mark phase does. It's not too hard to walk through
all allocated Lisp objects - this is exactly what GC sweep phase does.
But what about lower-level stuff allocated with malloc at invisible
from Lisp? Of course, you can do your own serialization for these objects
as well - but only if you know about their internal structure. What about
stuff allocated by some external library? In general, you can't parse heap
(i.e. looking at object, you can't say where the next object is, what is the
type of next object, etc.). IIUC, "totally portable" heap dumper is impossible
without having a description of each possible heap object and ability to
distinguish between different types of objects.

Dmitry

Re: Dumper problems and a possible solutions

[Rich Felker]

On Wed, Jun 25, 2014 at 10:03:36PM +0400, Dmitry Antipov wrote:
> On 06/24/2014 09:19 PM, Rich Felker wrote:
> 
> >To solve ALL of the problems with the dumper (which seems to be a
> >recurring theme), I have a proposed design to make it fully portable
> >-- even moreso than xemacs "portable dumper" which is still an ugly
> >hack. The idea is simple: after loading all of the lisp objects that
> >need dumping, walk the lisp heap and output a representation for each
> >object as a giant static array in C source format, then compile and
> >link this new translation unit with the rest of the emacs .o files to
> >produce a final emacs binary.
> 
> What about non-Lisp objects?
> 
> It's not too hard to walk through live (reachable) Lisp objects - this
> is exactly what GC mark phase does. It's not too hard to walk through
> all allocated Lisp objects - this is exactly what GC sweep phase does.
> But what about lower-level stuff allocated with malloc at invisible
> from Lisp? Of course, you can do your own serialization for these objects
> as well - but only if you know about their internal structure. What about
> stuff allocated by some external library? In general, you can't parse heap
> (i.e. looking at object, you can't say where the next object is, what is the
> type of next object, etc.). IIUC, "totally portable" heap dumper is impossible
> without having a description of each possible heap object and ability to
> distinguish between different types of objects.

Are there such objects that need to be preserved across dumping? This
is a real question. I'm not familiar enough with emacs' internals to
know whether there are or not, but my impression is that emacs does
not need a fully general process-freeze-and-thaw dumper (in fact it
doesn't even try to be one), and my hope is that only the lisp state,
and perhaps some reasonably-trivial amount of non-lisp data with known
structure, actually needs to be preserved.

Can you or anyone else provide some answers to this question?

Rich

Re: Dumper problems and a possible solutions

[Eli Zaretskii]

> Date: Wed, 25 Jun 2014 22:03:36 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> Cc: emacs-devel@gnu.org
> 
> What about non-Lisp objects?
> 
> It's not too hard to walk through live (reachable) Lisp objects - this
> is exactly what GC mark phase does. It's not too hard to walk through
> all allocated Lisp objects - this is exactly what GC sweep phase does.
> But what about lower-level stuff allocated with malloc at invisible
> from Lisp? Of course, you can do your own serialization for these objects
> as well - but only if you know about their internal structure.

Is it possible to provide our own implementation of sbrk that
allocates memory from some large static array?  Or do modern malloc
implementations avoid calling sbrk when they need more memory?

If something like that is possible, we could do what the native and
Cygwin Windows builds already do: record all the objects, Lisp and C,
in that static array, which then gets dumped as part of the data
section.

> What about stuff allocated by some external library?

A valid concern, but I don't think we have that problem now.  If we
did, the Windows port would not be able to be built, because such
external libraries would call the malloc they were linked against, not
the replacement we provide during "-l loadup dump" phase of the build.

Re: Dumper problems and a possible solutions

[Dmitry Antipov]

On 06/25/2014 10:08 PM, Rich Felker wrote:

> Are there such objects that need to be preserved across dumping?

I don't know, and the worst thing is that we can't control over this.
With my debug build, 'ldd src/temacs  | wc -l' shows 112 external
libraries. What if just one of these libraries uses malloc() to allocate
an internal object in __attribute__((constructor)) function? There is no
way to handle this except intercepting all malloc() calls. This way we
move to our own heap management, which will have the same heap parsability
issues like system's malloc(), etc.

Dmitry

Re: Dumper problems and a possible solutions

[Rich Felker]

On Wed, Jun 25, 2014 at 09:20:40PM +0300, Eli Zaretskii wrote:
> > Date: Wed, 25 Jun 2014 22:03:36 +0400
> > From: Dmitry Antipov <dmantipov@yandex.ru>
> > Cc: emacs-devel@gnu.org
> > 
> > What about non-Lisp objects?
> > 
> > It's not too hard to walk through live (reachable) Lisp objects - this
> > is exactly what GC mark phase does. It's not too hard to walk through
> > all allocated Lisp objects - this is exactly what GC sweep phase does.
> > But what about lower-level stuff allocated with malloc at invisible
> > from Lisp? Of course, you can do your own serialization for these objects
> > as well - but only if you know about their internal structure.
> 
> Is it possible to provide our own implementation of sbrk that
> allocates memory from some large static array?

That's exactly the hack I described which I'm using right now. But
since I didn't implement a free-like operation and since
load_charset_map_from_file allocates >700k every time it's called, I
had to make the static array 400MB. This obviously isn't acceptable. I
think it would work with a "real" mini-malloc implementation using the
static array, and a much smaller static array (maybe 8-15 MB) but my
attempts to write a quick one have been sloppy and buggy so far.

I would be reasonably happy with this solution (at least it would fix
the problems I'm experiencing), but I don't think it's as elegant as
fixing the portability problem completely by getting rid of the need
to dump executable binary files and instead dumping a C array. And it
doesn't fix the fact that you can't build a PIE emacs.

> Or do modern malloc
> implementations avoid calling sbrk when they need more memory?

In general avoiding using brk to expand the heap is a bad idea on
Linux since alternate methods are considerably slower and can't
automatically obtain contiguous virtual space when it's available.
However, behaviors may vary.

In musl's malloc, we use brk if it's available (note: with PIE, most
kernels give you almost no available brk space due to the way the
mappings are laid out) for extending the heap that's usef for small
allocations, and fallback to constructing a discontiguous heap with
mmap if brk fails. However musl always uses mmap for huge allocations
(greater than ~100-200k) since it has no freelists for sizes that
large and since we want to always return freed memory that large to
the system.

Also, musl does not provide a working sbrk at all, since synchronizing
with an application's use of sbrk would introduce performance costs
into all correct applications that don't poke at the brk.

> If something like that is possible, we could do what the native and
> Cygwin Windows builds already do: record all the objects, Lisp and C,
> in that static array, which then gets dumped as part of the data
> section.
> 
> > What about stuff allocated by some external library?
> 
> A valid concern, but I don't think we have that problem now.  If we
> did, the Windows port would not be able to be built, because such
> external libraries would call the malloc they were linked against, not
> the replacement we provide during "-l loadup dump" phase of the build.

Indeed.

Rich

Re: Dumper problems and a possible solutions

[Rich Felker]

On Wed, Jun 25, 2014 at 10:30:22PM +0400, Dmitry Antipov wrote:
> On 06/25/2014 10:08 PM, Rich Felker wrote:
> 
> >Are there such objects that need to be preserved across dumping?
> 
> I don't know, and the worst thing is that we can't control over this.

Sure you can. If the lisp code doesn't reference such objects then
their existence of nonexistence is irrelevant to the new emacs
invocation after dumping.

> With my debug build, 'ldd src/temacs  | wc -l' shows 112 external
> libraries. What if just one of these libraries uses malloc() to allocate
> an internal object in __attribute__((constructor)) function?

If these libraries are shared libraries, all of that state will be
lost during dumping and reinitialized when the library is loaded again
at runtime.

As long as we're using the existing dumper system, where the whole
data segment gets written out to a new executable file, I agree
there's such a problem for static linking. But if emacs switched to
the new system I proposed, where ONLY the lisp state were dumped to a
static array, then none of these libraries' state could be saved at
all, and thus there would be no danger.

Rich

Re: Dumper problems and a possible solutions

[Eli Zaretskii]

> Date: Wed, 25 Jun 2014 22:30:22 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> Cc: emacs-devel@gnu.org
> 
> On 06/25/2014 10:08 PM, Rich Felker wrote:
> 
> > Are there such objects that need to be preserved across dumping?
> 
> I don't know, and the worst thing is that we can't control over this.
> With my debug build, 'ldd src/temacs  | wc -l' shows 112 external
> libraries. What if just one of these libraries uses malloc() to allocate
> an internal object in __attribute__((constructor)) function?

If they do, the dumped Emacs will likely crash.  Unless these
libraries invoke those constructors again when the dumped Emacs comes
up, in which case this problem doesn't exist anyway, besides some
wasted memory that cannot be used.

Re: Dumper problems and a possible solutions

[Stefan Monnier]

> What about non-Lisp objects?

The core purpose of the dumper is to do a kind of "define functions and
variables" that's faster than loading the corresponding .elc files.

So  all we really need is basically to dump the content of the obarray
and reload it later on (if it's dumped into a C file, then it's like the
reload happens at link time).

So, the problem only appears if there are objects reachable from the
obarray which come from external libraries.


        Stefan

Re: Dumper problems and a possible solutions

[Eli Zaretskii]

> Date: Wed, 25 Jun 2014 14:08:23 -0400
> From: Rich Felker <dalias@libc.org>
> Cc: emacs-devel@gnu.org
> 
> > What about non-Lisp objects?
> > 
> > It's not too hard to walk through live (reachable) Lisp objects - this
> > is exactly what GC mark phase does. It's not too hard to walk through
> > all allocated Lisp objects - this is exactly what GC sweep phase does.
> > But what about lower-level stuff allocated with malloc at invisible
> > from Lisp? Of course, you can do your own serialization for these objects
> > as well - but only if you know about their internal structure. What about
> > stuff allocated by some external library? In general, you can't parse heap
> > (i.e. looking at object, you can't say where the next object is, what is the
> > type of next object, etc.). IIUC, "totally portable" heap dumper is impossible
> > without having a description of each possible heap object and ability to
> > distinguish between different types of objects.
> 
> Are there such objects that need to be preserved across dumping? This
> is a real question. I'm not familiar enough with emacs' internals to
> know whether there are or not, but my impression is that emacs does
> not need a fully general process-freeze-and-thaw dumper (in fact it
> doesn't even try to be one), and my hope is that only the lisp state,
> and perhaps some reasonably-trivial amount of non-lisp data with known
> structure, actually needs to be preserved.
> 
> Can you or anyone else provide some answers to this question?

I don't think anyone knows the answer.  We've always dumped the entire
data segment, which includes everything, and never looked behind on
what exactly was dumped.

That said, I don't imagine we dump any non-Lisp data that is not
re-initialized after dumping anyway.  But the only way to know for
sure is to try.  E.g., run "temacs -l loadup dump" under a debugger or
some memory tracing tool, and see if there are any malloc calls that
allocate non-Lisp objects that are never freed before unexec runs.

Btw, would you like to subscribe to the list for the time being?  It
would definitely improve my life quality, as I would be spared the
need to release every of your messages for the list.

Re: Dumper problems and a possible solutions

[Eli Zaretskii]

> Date: Wed, 25 Jun 2014 14:32:41 -0400
> From: Rich Felker <dalias@libc.org>
> Cc: Dmitry Antipov <dmantipov@yandex.ru>, emacs-devel@gnu.org
> 
> > Is it possible to provide our own implementation of sbrk that
> > allocates memory from some large static array?
> 
> That's exactly the hack I described which I'm using right now. But
> since I didn't implement a free-like operation and since
> load_charset_map_from_file allocates >700k every time it's called, I
> had to make the static array 400MB.

That's not a problem, because those 700K are free'd before the next
one is allocated.  And in any case, they are all free'd before we call
unexec.  Just implement sbrk for negative increment.  The Windows port
already does that, see w32heap.c on the trunk.  It works with only
11MB of static array for 32-bit builds and 18MB for 64-bit.

> I think it would work with a "real" mini-malloc implementation using
> the static array, and a much smaller static array (maybe 8-15 MB)
> but my attempts to write a quick one have been sloppy and buggy so
> far.

If supporting deallocation in such an sbrk isn't feasible, how about
using gmalloc, as an malloc replacement before dumping?

> I would be reasonably happy with this solution (at least it would fix
> the problems I'm experiencing), but I don't think it's as elegant as
> fixing the portability problem completely by getting rid of the need
> to dump executable binary files and instead dumping a C array.

But it's conceptually much simpler and reliable.  That's "elegant" in
my book, when such hairy stuff is concerned.

> And it doesn't fix the fact that you can't build a PIE emacs.

Why is that important?

Re: Dumper problems and a possible solutions

[Rich Felker]

On Wed, Jun 25, 2014 at 09:49:42PM +0300, Eli Zaretskii wrote:
> > Date: Wed, 25 Jun 2014 14:32:41 -0400
> > From: Rich Felker <dalias@libc.org>
> > Cc: Dmitry Antipov <dmantipov@yandex.ru>, emacs-devel@gnu.org
> > 
> > > Is it possible to provide our own implementation of sbrk that
> > > allocates memory from some large static array?
> > 
> > That's exactly the hack I described which I'm using right now. But
> > since I didn't implement a free-like operation and since
> > load_charset_map_from_file allocates >700k every time it's called, I
> > had to make the static array 400MB.
> 
> That's not a problem, because those 700K are free'd before the next
> one is allocated.  And in any case, they are all free'd before we call
> unexec.  Just implement sbrk for negative increment.  The Windows port

But load_charset_map_from_file doesn't call an sbrk-like interface; it
calls (indirectly) xmalloc and xfree. So there's at least some
nontrivial glue that goes in between.

> already does that, see w32heap.c on the trunk.  It works with only
> 11MB of static array for 32-bit builds and 18MB for 64-bit.

Nice to know.

> > I think it would work with a "real" mini-malloc implementation using
> > the static array, and a much smaller static array (maybe 8-15 MB)
> > but my attempts to write a quick one have been sloppy and buggy so
> > far.
> 
> If supporting deallocation in such an sbrk isn't feasible, how about
> using gmalloc, as an malloc replacement before dumping?

I suspect it's a lot of work to wire up gmalloc to (1) avoid
interposing on the malloc/free/etc. names, (2) use the static mini-brk
buffer, (3) only allocate from the mini-brk buffer before dumping
(otherwise pass to real malloc), but still check realloc/free calls
after dumping and handle the case where the old memory was in the
mini-brk.

What seems easier, and what I tried, is writing a completely naive
malloc with a single freelist that's linear-searched on malloc and
which does not support coalescing free chunks. But I think my
implementation has some bugs still, because it's not working. I'm not
sure if they're bugs in the allocator, or bugs in how it's used (maybe
missing some places that would have to be redirected through it and
which are still calling malloc or free directly).

> > I would be reasonably happy with this solution (at least it would fix
> > the problems I'm experiencing), but I don't think it's as elegant as
> > fixing the portability problem completely by getting rid of the need
> > to dump executable binary files and instead dumping a C array.
> 
> But it's conceptually much simpler and reliable.  That's "elegant" in
> my book, when such hairy stuff is concerned.

No, it's less reliable. See my other posts in the thread about what
happens if you have other libraries linked and they do nontrivial
things prior to dumping (e.g. from static ctors). Dumping JUST the
lisp object state in a C array ensures that none of the pre-dump state
from other libraries (or even libc) can pollute the state observed
after dumping. Both the current method, and the proposed simple fixes
above, suffer from this issue and are therefore very fragile. As an
example (I think I mentioned this earlier), if you static link, musl
libc is remembering the clock_gettime vdso pointer from the pre-dump
state and attempting to use it later (which is not valid because the
kernel maps it at a random address).

> > And it doesn't fix the fact that you can't build a PIE emacs.
> 
> Why is that important?

Since emacs is processing lots of potentially untrusted data, PIE
hardening may be beneficial for hardening against vulnerabilities
where an attacker would otherwise be able to perform arbitrary code
execution as the user running emacs. I'm not aware of such
vulnerabilities, but being that I found things that look suspiciously
like use-after-free while reading the allocator-related code, I
wouldn't be surprised if they exist.

Rich

Re: Dumper problems and a possible solutions

[Eli Zaretskii]

> Date: Wed, 25 Jun 2014 15:03:33 -0400
> From: Rich Felker <dalias@libc.org>
> Cc: dmantipov@yandex.ru, emacs-devel@gnu.org
> 
> > > > Is it possible to provide our own implementation of sbrk that
> > > > allocates memory from some large static array?
> > > 
> > > That's exactly the hack I described which I'm using right now. But
> > > since I didn't implement a free-like operation and since
> > > load_charset_map_from_file allocates >700k every time it's called, I
> > > had to make the static array 400MB.
> > 
> > That's not a problem, because those 700K are free'd before the next
> > one is allocated.  And in any case, they are all free'd before we call
> > unexec.  Just implement sbrk for negative increment.  The Windows port
> 
> But load_charset_map_from_file doesn't call an sbrk-like interface; it
> calls (indirectly) xmalloc and xfree. So there's at least some
> nontrivial glue that goes in between.

Sorry, you are right.  What you need is non-toy malloc implementation
that is willing to work with your replacement sbrk.  Then support for
negative increments in sbrk isn't required.

But I still don't understand how you get to 400MB.  It's not that we
allocate hundreds of those 700K tables for charsets.  Do you have an
explanation for this?

> > If supporting deallocation in such an sbrk isn't feasible, how about
> > using gmalloc, as an malloc replacement before dumping?
> 
> I suspect it's a lot of work to wire up gmalloc to (1) avoid
> interposing on the malloc/free/etc. names, (2) use the static mini-brk
> buffer, (3) only allocate from the mini-brk buffer before dumping
> (otherwise pass to real malloc), but still check realloc/free calls
> after dumping and handle the case where the old memory was in the
> mini-brk.

Sorry, I don't see the difficulty.  Just make malloc/realloc/free be
pointers that point to gmalloc's implementation before dumping, and to
the libc implementation after it.  You may need some #define to rename
malloc to some other symbol, to avoid name clashes.  Am I missing
something?

> What seems easier, and what I tried, is writing a completely naive
> malloc with a single freelist that's linear-searched on malloc and
> which does not support coalescing free chunks. But I think my
> implementation has some bugs still, because it's not working.

The advantage of gmalloc is that it works out of the box.

> > > I would be reasonably happy with this solution (at least it would fix
> > > the problems I'm experiencing), but I don't think it's as elegant as
> > > fixing the portability problem completely by getting rid of the need
> > > to dump executable binary files and instead dumping a C array.
> > 
> > But it's conceptually much simpler and reliable.  That's "elegant" in
> > my book, when such hairy stuff is concerned.
> 
> No, it's less reliable. See my other posts in the thread about what
> happens if you have other libraries linked and they do nontrivial
> things prior to dumping (e.g. from static ctors).

But in those other posts I thought we agreed that whatever those ctors
do is irrelevant, as the dumped Emacs cannot possibly use what they
allocate, and those ctors will be invoked again in the dumped Emacs.

> As an example (I think I mentioned this earlier), if you static
> link, musl libc is remembering the clock_gettime vdso pointer from
> the pre-dump state and attempting to use it later (which is not
> valid because the kernel maps it at a random address).

You need to fix your libc to detect that it is re-exec'ed, and
re-initialize this stuff.

> > > And it doesn't fix the fact that you can't build a PIE emacs.
> > 
> > Why is that important?
> 
> Since emacs is processing lots of potentially untrusted data, PIE
> hardening may be beneficial for hardening against vulnerabilities
> where an attacker would otherwise be able to perform arbitrary code
> execution as the user running emacs. I'm not aware of such
> vulnerabilities, but being that I found things that look suspiciously
> like use-after-free while reading the allocator-related code, I
> wouldn't be surprised if they exist.

Sounds like a secondary requirement to me.  We should first make the
dumping work along these lines, and worry about bonuses later.

Re: Dumper problems and a possible solutions

[Rich Felker]

On Wed, Jun 25, 2014 at 10:18:16PM +0300, Eli Zaretskii wrote:
> > Date: Wed, 25 Jun 2014 15:03:33 -0400
> > From: Rich Felker <dalias@libc.org>
> > Cc: dmantipov@yandex.ru, emacs-devel@gnu.org
> > 
> > > > > Is it possible to provide our own implementation of sbrk that
> > > > > allocates memory from some large static array?
> > > > 
> > > > That's exactly the hack I described which I'm using right now. But
> > > > since I didn't implement a free-like operation and since
> > > > load_charset_map_from_file allocates >700k every time it's called, I
> > > > had to make the static array 400MB.
> > > 
> > > That's not a problem, because those 700K are free'd before the next
> > > one is allocated.  And in any case, they are all free'd before we call
> > > unexec.  Just implement sbrk for negative increment.  The Windows port
> > 
> > But load_charset_map_from_file doesn't call an sbrk-like interface; it
> > calls (indirectly) xmalloc and xfree. So there's at least some
> > nontrivial glue that goes in between.
> 
> Sorry, you are right.  What you need is non-toy malloc implementation
> that is willing to work with your replacement sbrk.  Then support for
> negative increments in sbrk isn't required.
> 
> But I still don't understand how you get to 400MB.  It's not that we
> allocate hundreds of those 700K tables for charsets.  Do you have an
> explanation for this?

Not hundreds at a time, but if the malloc operation is just positive
(fake-)sbrk and the free operation is a nop, hundreds of such charset
load operations will quickly add up. It might have succeeded with a
little less than 400 but that was the first guess I made that didn't
run out of memory (guesses were something like 10, 50, 100, 200, 400
IIRC).

> > > If supporting deallocation in such an sbrk isn't feasible, how about
> > > using gmalloc, as an malloc replacement before dumping?
> > 
> > I suspect it's a lot of work to wire up gmalloc to (1) avoid
> > interposing on the malloc/free/etc. names, (2) use the static mini-brk
> > buffer, (3) only allocate from the mini-brk buffer before dumping
> > (otherwise pass to real malloc), but still check realloc/free calls
> > after dumping and handle the case where the old memory was in the
> > mini-brk.
> 
> Sorry, I don't see the difficulty.  Just make malloc/realloc/free be
> pointers that point to gmalloc's implementation before dumping, and to
> the libc implementation after it.  You may need some #define to rename
> malloc to some other symbol, to avoid name clashes.  Am I missing
> something?

Yeah, what happens if, after dumping, the real emacs at runtime ends
up calling free() on one of the pre-dump pointers? Can't this happen?
This is why I want the whole pre-dump heap in a single C array: so we
can range-check addresses and determine if they're pre-dump
allocations (and in that case, NOP out free and do malloc+memcpy for
realloc).

> > > > I would be reasonably happy with this solution (at least it would fix
> > > > the problems I'm experiencing), but I don't think it's as elegant as
> > > > fixing the portability problem completely by getting rid of the need
> > > > to dump executable binary files and instead dumping a C array.
> > > 
> > > But it's conceptually much simpler and reliable.  That's "elegant" in
> > > my book, when such hairy stuff is concerned.
> > 
> > No, it's less reliable. See my other posts in the thread about what
> > happens if you have other libraries linked and they do nontrivial
> > things prior to dumping (e.g. from static ctors).
> 
> But in those other posts I thought we agreed that whatever those ctors
> do is irrelevant, as the dumped Emacs cannot possibly use what they
> allocate, and those ctors will be invoked again in the dumped Emacs.

Those ctors are free to inspect global data. For example one might
contain (this sort of idiom is necessary if you can't control the
relative order of ctors): if (!init) { do_something(); init=1; }. In
that case, the dump would save the value of init, and do_something()
would fail to happen at runtime. This issue is not something that
would be added with our proposed "simple fix"; it's an issue that
EXISTS NOW if any such libraries happen to be linked statically (if
they're dynamic, the dumper will fail to see/dump the data).

> > As an example (I think I mentioned this earlier), if you static
> > link, musl libc is remembering the clock_gettime vdso pointer from
> > the pre-dump state and attempting to use it later (which is not
> > valid because the kernel maps it at a random address).
> 
> You need to fix your libc to detect that it is re-exec'ed, and
> re-initialize this stuff.

I don't see any easy way to do that that's not a big violation of
encapsulation (startup code has no business knowing about
clock_gettime internals) and the whole efficiency of static linking
(startup code does not pull in any vdso stuff; that only gets pulled
in by using a function that needs a vdso lookup). This is some big
ugliness for the sake of supporting static-linked emacs. And it ends
up being a big case of whack-a-mole. Dumping and re-execing is not a
standard usage case and is way out there in the realm of undefined
behavior. Emacs is probably the only widely-used (or even known)
program that does it.

If this issue can't be fixed easily, I'd probably just recommend to
musl users not to static link emacs, or to patch in a global ctor that
clears AT_SYSINFO_EHDR from the aux vector so that vdso doesn't get
used at all.

> > > > And it doesn't fix the fact that you can't build a PIE emacs.
> > > 
> > > Why is that important?
> > 
> > Since emacs is processing lots of potentially untrusted data, PIE
> > hardening may be beneficial for hardening against vulnerabilities
> > where an attacker would otherwise be able to perform arbitrary code
> > execution as the user running emacs. I'm not aware of such
> > vulnerabilities, but being that I found things that look suspiciously
> > like use-after-free while reading the allocator-related code, I
> > wouldn't be surprised if they exist.
> 
> Sounds like a secondary requirement to me.  We should first make the
> dumping work along these lines, and worry about bonuses later.

That's fine with me.

Rich

Re: Dumper problems and a possible solutions

[Stefan Monnier]

> Since emacs is processing lots of potentially untrusted data, PIE
> hardening may be beneficial for hardening against vulnerabilities

IIUC what you mean by PIE, it requires a dumped Emacs where the position
of the (pre-filled) heap can change at every invocation.  If so, that
means relocation of all the pointers in the heap, at startup.

I had the impression you didn't want such relocation-at-startup (since
you used it as an argument against XEmacs-style dumping into a separate
heap file).


        Stefan

Re: Dumper problems and a possible solutions

[Stefan Monnier]

> But I still don't understand how you get to 400MB.  It's not that we
> allocate hundreds of those 700K tables for charsets.  Do you have an
> explanation for this?

Probably that when the GC collects some space and passes it to `free'
that space gets "lost" since his `free' is a no-op.
Maybe a quick fix is to tell GC not to free any blocks that it could
free, and instead keep them in its pool of blocks ready for re-use.


        Stefan

Re: Dumper problems and a possible solutions

[Eli Zaretskii]

> Date: Wed, 25 Jun 2014 15:57:30 -0400
> From: Rich Felker <dalias@libc.org>
> Cc: dmantipov@yandex.ru, emacs-devel@gnu.org
> 
> > But I still don't understand how you get to 400MB.  It's not that we
> > allocate hundreds of those 700K tables for charsets.  Do you have an
> > explanation for this?
> 
> Not hundreds at a time, but if the malloc operation is just positive
> (fake-)sbrk and the free operation is a nop, hundreds of such charset
> load operations will quickly add up.

Free operation shouldn't be a no-op, not in malloc.

And still, there are only a few (maybe 10) times we allocate these
700K tables, so 400MB sound very strange to me.

> > Sorry, I don't see the difficulty.  Just make malloc/realloc/free be
> > pointers that point to gmalloc's implementation before dumping, and to
> > the libc implementation after it.  You may need some #define to rename
> > malloc to some other symbol, to avoid name clashes.  Am I missing
> > something?
> 
> Yeah, what happens if, after dumping, the real emacs at runtime ends
> up calling free() on one of the pre-dump pointers?

You intercept the call and do nothing.

> > > No, it's less reliable. See my other posts in the thread about what
> > > happens if you have other libraries linked and they do nontrivial
> > > things prior to dumping (e.g. from static ctors).
> > 
> > But in those other posts I thought we agreed that whatever those ctors
> > do is irrelevant, as the dumped Emacs cannot possibly use what they
> > allocate, and those ctors will be invoked again in the dumped Emacs.
> 
> Those ctors are free to inspect global data. For example one might
> contain (this sort of idiom is necessary if you can't control the
> relative order of ctors): if (!init) { do_something(); init=1; }. In
> that case, the dump would save the value of init, and do_something()
> would fail to happen at runtime.

That's the same problem as with your clock_gettime, and it must be
fixed anyway, because any ctor run at dump time is almost certainly
picking up data that is irrelevant to the run time.

> > > As an example (I think I mentioned this earlier), if you static
> > > link, musl libc is remembering the clock_gettime vdso pointer from
> > > the pre-dump state and attempting to use it later (which is not
> > > valid because the kernel maps it at a random address).
> > 
> > You need to fix your libc to detect that it is re-exec'ed, and
> > re-initialize this stuff.
> 
> I don't see any easy way to do that that's not a big violation of
> encapsulation (startup code has no business knowing about
> clock_gettime internals) and the whole efficiency of static linking
> (startup code does not pull in any vdso stuff; that only gets pulled
> in by using a function that needs a vdso lookup).

One way is to have a counter that gets incremented each re-exec.  Then
the initialization code of clock_gettime could examine the counter and
re-initialize when its value changes since last time.

Re: Dumper problems and a possible solutions

[Rich Felker]

On Wed, Jun 25, 2014 at 04:06:33PM -0400, Stefan Monnier wrote:
> > Since emacs is processing lots of potentially untrusted data, PIE
> > hardening may be beneficial for hardening against vulnerabilities
> 
> IIUC what you mean by PIE, it requires a dumped Emacs where the position
> of the (pre-filled) heap can change at every invocation.  If so, that
> means relocation of all the pointers in the heap, at startup.

With the approach of dumping a C array containing references to
offsets within itself, this is completely transparent to the
application. The linker (ld) produces the right R_${ARCH}_RELATIVE
relocation records in the data segment and the dynamic linker applies
them at runtime.

> I had the impression you didn't want such relocation-at-startup (since
> you used it as an argument against XEmacs-style dumping into a separate
> heap file).

I didn't mean for that to be "an argument against XEmacs-style
dumping" since the XEmacs style is still much better than what GNU
emacs has now, simply an observation that it's not the ideal system.

Rich

Re: Dumper problems and a possible solutions

[Rich Felker]

On Wed, Jun 25, 2014 at 11:15:02PM +0300, Eli Zaretskii wrote:
> > Date: Wed, 25 Jun 2014 15:57:30 -0400
> > From: Rich Felker <dalias@libc.org>
> > Cc: dmantipov@yandex.ru, emacs-devel@gnu.org
> > 
> > > But I still don't understand how you get to 400MB.  It's not that we
> > > allocate hundreds of those 700K tables for charsets.  Do you have an
> > > explanation for this?
> > 
> > Not hundreds at a time, but if the malloc operation is just positive
> > (fake-)sbrk and the free operation is a nop, hundreds of such charset
> > load operations will quickly add up.
> 
> Free operation shouldn't be a no-op, not in malloc.

Agreed. But the question was about why my quick hack took 400MB, and
the answer is that it was using a static fake-brk with malloc=sbrk and
free=nop.

> And still, there are only a few (maybe 10) times we allocate these
> 700K tables, so 400MB sound very strange to me.

In my log, I see 768k allocations occuring roughly 94 times. Is it
possible that the temacs --batch commands I'm testing (IIRC taken from
commands that were failing in leim/Makefile, but perhaps I changed it
in some way I didn't notice?) are pulling in my .emacs file, which
might be causing more charsets to be loaded?

> > > Sorry, I don't see the difficulty.  Just make malloc/realloc/free be
> > > pointers that point to gmalloc's implementation before dumping, and to
> > > the libc implementation after it.  You may need some #define to rename
> > > malloc to some other symbol, to avoid name clashes.  Am I missing
> > > something?
> > 
> > Yeah, what happens if, after dumping, the real emacs at runtime ends
> > up calling free() on one of the pre-dump pointers?
> 
> You intercept the call and do nothing.

Right, but the free pointer can't directly point to the real (libc)
free. It has to point to the wrapper that does this range-check.

> > > > No, it's less reliable. See my other posts in the thread about what
> > > > happens if you have other libraries linked and they do nontrivial
> > > > things prior to dumping (e.g. from static ctors).
> > > 
> > > But in those other posts I thought we agreed that whatever those ctors
> > > do is irrelevant, as the dumped Emacs cannot possibly use what they
> > > allocate, and those ctors will be invoked again in the dumped Emacs.
> > 
> > Those ctors are free to inspect global data. For example one might
> > contain (this sort of idiom is necessary if you can't control the
> > relative order of ctors): if (!init) { do_something(); init=1; }. In
> > that case, the dump would save the value of init, and do_something()
> > would fail to happen at runtime.
> 
> That's the same problem as with your clock_gettime, and it must be
> fixed anyway, because any ctor run at dump time is almost certainly
> picking up data that is irrelevant to the run time.

Libc could _possibly_ work around it by virtue of having full control
over the init code. For other libraries, the issue is not fixable (see
my above example with code that has to control dependency order of
ctors), and shouldn't have to be fixed. If the library is written such
that static objects have a particular nominal initial value at the
source level, it should be able to rely on that value actually being
present at runtime. Failure to provide this guarantee is a bug in the
runtime (in this case, in the tool which produced the ELF file, i.e.
unexelf.c).

Rich

Re: Dumper problems and a possible solutions

[Samuel Bronson]

On 6/25/14, Rich Felker <dalias@libc.org> wrote:

> In musl's malloc, we use brk if it's available (note: with PIE, most
> kernels give you almost no available brk space due to the way the
> mappings are laid out) [...]

Yeah, that tiny gap has bitten in other ways, too:
<http://www.postgresql.org/message-id/20140519115318.GB7296@msgid.df7cb.de>
talks about a stack overflow with the same cause; I really think the
kernel should stop doing that.

> Also, musl does not provide a working sbrk at all, since synchronizing
> with an application's use of sbrk would introduce performance costs
> into all correct applications that don't poke at the brk.

Looking at the manpage, I can't really follow how having sbrk() would
involve a slowdown in everything?  Do you mean that musl's malloc gets
a speed bonus out of assuming it's the sole user of brk()/sbrk(), and
thus the whole region from the initial brk()point to the current
brk()point is belongs to it?  (Yeah, all (potentially) 125 MiB -
stacksize of it!)

Re: Dumper problems and a possible solutions

[Rich Felker]

On Wed, Jun 25, 2014 at 04:53:58PM -0400, Samuel Bronson wrote:
> On 6/25/14, Rich Felker <dalias@libc.org> wrote:
> 
> > In musl's malloc, we use brk if it's available (note: with PIE, most
> > kernels give you almost no available brk space due to the way the
> > mappings are laid out) [...]
> 
> Yeah, that tiny gap has bitten in other ways, too:
> <http://www.postgresql.org/message-id/20140519115318.GB7296@msgid.df7cb.de>
> talks about a stack overflow with the same cause; I really think the
> kernel should stop doing that.

Agreed. But it was a big enough issue (basically a show-stopper for
using PIE) that I just added a simple way to use mmap without having
to care about discontiguity because the waste is asymptotically zero.

> > Also, musl does not provide a working sbrk at all, since synchronizing
> > with an application's use of sbrk would introduce performance costs
> > into all correct applications that don't poke at the brk.
> 
> Looking at the manpage, I can't really follow how having sbrk() would
> involve a slowdown in everything? Do you mean that musl's malloc gets
> a speed bonus out of assuming it's the sole user of brk()/sbrk(), and
> thus the whole region from the initial brk()point to the current
> brk()point is belongs to it?

Yes, basically. malloc simply assumes the brk is where it last left
it, rather than querying it again, which would double the syscall
overhead. This could be avoided via a cooperating lock between sbrk
and malloc, but basically after sbrk touches the brk, malloc could not
safely use it anymore; if it did, the application might later clobber
malloc's heap.

brk/sbrk are documented as not being usable if malloc is used (see
http://pubs.opengroup.org/onlinepubs/7908799/xsh/brk.html) and they
were later removed from the standards because that essentially makes
it impossible to use them at all.

There's an ongoing discussion on whether it's desirable to provide an
emulated sbrk for legacy applications (note: these applications would
not work with real sbrk anyway if compiled as PIE!) but since there
are basically no users of brk/sbrk left except malloc implementations,
nobody has really cared much one way or the other whether it gets
added.

> (Yeah, all (potentially) 125 MiB -
> stacksize of it!)

I don't follow. brk has nothing to do with the stack, and in practice
it can obtain nearly the full 3GB (for 32-bit) of available virtual
address space in non-PIE programs.

Anyway, discussion of musl's malloc implementation is largely
off-topic to this discussion except insomuch as it reflects the
diversity of implementation possibilities that it would be nice for
emacs to support without ugly hacks. I'd rather this thread not be
"please change emacs because __________ in musl" but rather "let's
address a long-standing portability issue in emacs in such a way that
it won't come up again, and possibly gives other benefits like support
for PIE and fixing ugly corner-cases that are going to arise now that
modern emacs is linking so many libraries".

Rich

Re: Dumper problems and a possible solutions

[Stefan Monnier]

> With the approach of dumping a C array containing references to
> offsets within itself, this is completely transparent to the
> application. The linker (ld) produces the right R_${ARCH}_RELATIVE
> relocation records in the data segment and the dynamic linker applies
> them at runtime.

Two problems, here:
- we're still talking about performing relocation of all heap references
  during startup (not that it's a problem, of course).  Maybe we don't
  need to do it ourselves, but it still has to happen.
- Can the ld.so loader generate the *tagged* references used in the heap?


        Stefan

Re: Dumper problems and a possible solutions

[Rich Felker]

On Wed, Jun 25, 2014 at 05:43:00PM -0400, Stefan Monnier wrote:
> > With the approach of dumping a C array containing references to
> > offsets within itself, this is completely transparent to the
> > application. The linker (ld) produces the right R_${ARCH}_RELATIVE
> > relocation records in the data segment and the dynamic linker applies
> > them at runtime.
> 
> Two problems, here:
> - we're still talking about performing relocation of all heap references
>   during startup (not that it's a problem, of course).  Maybe we don't
>   need to do it ourselves, but it still has to happen.

Indeed. The difference is just between having to write non-portable
code that does it manually, and having it happen automatically as
consequences of the requirements of the C language.

> - Can the ld.so loader generate the *tagged* references used in the heap?

My understanding is that the tagged references are using the low bits
of otherwise-aligned pointers as flags. Is this correct? If so, then
these are just constant offsets applied to an address, and thus they
are still valid C address constant expressions, so they have to be
supported.

My understanding is that emacs also supports a mode for targets where
alignment up to 8 bytes cannot be guaranteed, where the high bits of
the pointer are used rather than the low bits, and where all pointers
are required to reside in "low addresses". This should also be able to
be supported at the dynamic-linker level as an addend. But at the C
source level, it's undefined behavior since the offsets go outside the
range of the array object. Of course this model is also incompatible
with PIE and with most modern systems where malloc may return "high"
addresses, and thereby likely buggy even on the systems it's currently
used on (if any). It could probably be fixed by using mmap to ensure
that the entire "high" memory space is filled with PROT_NONE mappings
before doing anything else, though, but I think fixing this build mode
is low priority since, in practice, all modern targets support 8-byte
alignment.

Rich

Re: Dumper problems and a possible solutions

[Andreas Schwab]

Rich Felker <dalias@libc.org> writes:

> With the approach of dumping a C array containing references to
> offsets within itself, this is completely transparent to the
> application. The linker (ld) produces the right R_${ARCH}_RELATIVE
> relocation records in the data segment and the dynamic linker applies
> them at runtime.

1. Relocations are highly architecture dependent.  2. Relocations only
apply to compiler-generated references, not runtime references.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: Dumper problems and a possible solutions

[Paul Eggert]

Rich Felker wrote:
> this model is also incompatible
> with PIE and with most modern systems where malloc may return "high"
> addresses, and thereby likely buggy even on the systems it's currently
> used on (if any).

The model works just fine on a typical modern 32-bit host, so long as 
you configure --with-wide-int.  That's because the 32-bit addresses fit 
comfortably in the low half of 64-bit integers.

Re: Dumper problems and a possible solutions

[Stefan Monnier]

>> - we're still talking about performing relocation of all heap references
>> during startup (not that it's a problem, of course).  Maybe we don't
>> need to do it ourselves, but it still has to happen.
> Indeed. The difference is just between having to write non-portable
> code that does it manually, and having it happen automatically as
> consequences of the requirements of the C language.

The manual code would be fairly normal C code, very similar to the
mark_object routine.  It shouldn't be noticeably less portable than the
current pointer<->int conversions we use for tagging purposes.

Of course, it's always nice when we can use someone else's code, but
I get the impression that to get the right behavior from the
compiler/linker/loader we may have to generate a fairly enormous C file
which will generate an enormous .o file and the resulting binary will
end up with a humongous relocation table.

Of course, only time will tell.

> My understanding is that the tagged references are using the low bits
> of otherwise-aligned pointers as flags. Is this correct? If so, then
> these are just constant offsets applied to an address, and thus they
> are still valid C address constant expressions, so they have to be
> supported.

Indeed, it might work.


        Stefan

Re: Dumper problems and a possible solutions

[Rich Felker]

On Wed, Jun 25, 2014 at 07:05:14PM -0400, Stefan Monnier wrote:
> >> - we're still talking about performing relocation of all heap references
> >> during startup (not that it's a problem, of course).  Maybe we don't
> >> need to do it ourselves, but it still has to happen.
> > Indeed. The difference is just between having to write non-portable
> > code that does it manually, and having it happen automatically as
> > consequences of the requirements of the C language.
> 
> The manual code would be fairly normal C code, very similar to the
> mark_object routine.  It shouldn't be noticeably less portable than the
> current pointer<->int conversions we use for tagging purposes.
> 
> Of course, it's always nice when we can use someone else's code, but
> I get the impression that to get the right behavior from the
> compiler/linker/loader we may have to generate a fairly enormous C file
> which will generate an enormous .o file and the resulting binary will
> end up with a humongous relocation table.

For non-PIE emacs, the relocations would only exist in the .o file,
which would only be "enormous" to the extent that the actual data is
(IIRC roughly 11 megs for 32-bit and 16 megs for 64-bit). For PIE,
the relocations are carried over to the executable, but they're all
relative (not symbolic) and thus trivial from a performance
standpoint.

Rich

Re: Dumper problems and a possible solutions

[Rich Felker]

On Wed, Jun 25, 2014 at 04:04:26PM -0700, Paul Eggert wrote:
> Rich Felker wrote:
> >this model is also incompatible
> >with PIE and with most modern systems where malloc may return "high"
> >addresses, and thereby likely buggy even on the systems it's currently
> >used on (if any).
> 
> The model works just fine on a typical modern 32-bit host, so long
> as you configure --with-wide-int.  That's because the 32-bit
> addresses fit comfortably in the low half of 64-bit integers.

I see. I wasn't aware of that option. In any case it would work just
fine with the proposed C static array output: for 32-bit pointers, the
lower 32 bits would actually be the address constant reference and the
upper 32 bits would be an integer constant expression.

Rich

Re: Dumper problems and a possible solutions

[Stephen J. Turnbull]

Rich Felker writes:

 > Can you or anyone else provide some answers to this question?

Sure.  src/dumper.c and the memory description objects in the XEmacs
sources.  If it's not tracked there (such as buffers and internal file
objects), then it's an implementation restriction but we havent't
needed it in practice, so a good first cut for you is to leave it out.
If it is handled there, then you can think about whether you need to
worry about it in your scheme or not.

Re: Dumper problems and a possible solutions

[Eli Zaretskii]

> Date: Wed, 25 Jun 2014 16:34:03 -0400
> From: Rich Felker <dalias@libc.org>
> Cc: dmantipov@yandex.ru, emacs-devel@gnu.org
> 
> > And still, there are only a few (maybe 10) times we allocate these
> > 700K tables, so 400MB sound very strange to me.
> 
> In my log, I see 768k allocations occuring roughly 94 times.

768K times 94 doesn't get anywhere close to 400MB.

> Is it possible that the temacs --batch commands I'm testing (IIRC
> taken from commands that were failing in leim/Makefile, but perhaps
> I changed it in some way I didn't notice?) are pulling in my .emacs
> file, which might be causing more charsets to be loaded?

No, it's more probable that I was mistaken about the count.  But
still, 400MB sounds way too much.

> > > > Sorry, I don't see the difficulty.  Just make malloc/realloc/free be
> > > > pointers that point to gmalloc's implementation before dumping, and to
> > > > the libc implementation after it.  You may need some #define to rename
> > > > malloc to some other symbol, to avoid name clashes.  Am I missing
> > > > something?
> > > 
> > > Yeah, what happens if, after dumping, the real emacs at runtime ends
> > > up calling free() on one of the pre-dump pointers?
> > 
> > You intercept the call and do nothing.
> 
> Right, but the free pointer can't directly point to the real (libc)
> free. It has to point to the wrapper that does this range-check.

Right.

> > > Those ctors are free to inspect global data. For example one might
> > > contain (this sort of idiom is necessary if you can't control the
> > > relative order of ctors): if (!init) { do_something(); init=1; }. In
> > > that case, the dump would save the value of init, and do_something()
> > > would fail to happen at runtime.
> > 
> > That's the same problem as with your clock_gettime, and it must be
> > fixed anyway, because any ctor run at dump time is almost certainly
> > picking up data that is irrelevant to the run time.
> 
> Libc could _possibly_ work around it by virtue of having full control
> over the init code. For other libraries, the issue is not fixable (see
> my above example with code that has to control dependency order of
> ctors), and shouldn't have to be fixed.

But the problem likely doesn't exist, because otherwise we will have
known about it by now.  Emacs cannot use such libraries.

Re: Dumper problems and a possible solutions

[Dmitry Antipov]

BTW, if you're doing your own libc, why do not implement Solaris-style dldump()?

Dmitry

Re: Dumper problems and a possible solutions

[Rich Felker]

On Thu, Jun 26, 2014 at 07:02:40AM +0400, Dmitry Antipov wrote:
> BTW, if you're doing your own libc, why do not implement Solaris-style dldump()?

Because dumping isn't really possible to do in a correct and
meaningful way without serious restrictions on what the code can do.
See Eli Zaretskii's email (Message-id: <83simspexv.fsf@gnu.org>)
stating that "Emacs cannot use such libraries." For a single
application like Emacs that's a decision that can be made. But to say
"[X feature of] libc can't support such code" when the code is
perfectly valid C is not really appropriate.

There's all sorts of state that cannot be preserved across dumping but
that's completely reasonable to have, such as pid, lock owners (tids
will not be the same after a dump), open files, etc. At one point I
actually tried to do a Solaris-style forkall() -- I mention this
because it has a lot of the same issues -- and partly had it working,
but the lock ownership issue turned out to be impractical to solve and
I abandoned it.


Rich

Re: Dumper problems and a possible solutions

[Rich Felker]

On Thu, Jun 26, 2014 at 05:44:44AM +0300, Eli Zaretskii wrote:
> > Date: Wed, 25 Jun 2014 16:34:03 -0400
> > From: Rich Felker <dalias@libc.org>
> > Cc: dmantipov@yandex.ru, emacs-devel@gnu.org
> > 
> > > And still, there are only a few (maybe 10) times we allocate these
> > > 700K tables, so 400MB sound very strange to me.
> > 
> > In my log, I see 768k allocations occuring roughly 94 times.
> 
> 768K times 94 doesn't get anywhere close to 400MB.

Yes, there were also a number of ~200k and ~400k allocations though,
which I did not get around to identifying the source of.

> > > > Those ctors are free to inspect global data. For example one might
> > > > contain (this sort of idiom is necessary if you can't control the
> > > > relative order of ctors): if (!init) { do_something(); init=1; }. In
> > > > that case, the dump would save the value of init, and do_something()
> > > > would fail to happen at runtime.
> > > 
> > > That's the same problem as with your clock_gettime, and it must be
> > > fixed anyway, because any ctor run at dump time is almost certainly
> > > picking up data that is irrelevant to the run time.
> > 
> > Libc could _possibly_ work around it by virtue of having full control
> > over the init code. For other libraries, the issue is not fixable (see
> > my above example with code that has to control dependency order of
> > ctors), and shouldn't have to be fixed.
> 
> But the problem likely doesn't exist, because otherwise we will have
> known about it by now.  Emacs cannot use such libraries.

I wouldn't be so sure. How much testing is even done with static
linking? With dynamic linking, the library's state will all be lost
across dump. Lots of the libraries emacs can optionally use have
sketchy global state, and I wouldn't be surprised at all if at least
one of them were failing to properly initialize in the post-dump
emacs. The symptoms might not even be immediately visible if the state
saved when dumping were "close enough" to correct to be used
post-dump.

Rich

Re: Dumper problems and a possible solutions

[Dmitry Antipov]

On 06/26/2014 08:14 AM, Rich Felker wrote:

> Because dumping isn't really possible to do in a correct and
> meaningful way without serious restrictions on what the code can do.

What do you think about this project: http://dmtcp.sourceforge.net/index.html?

 From their point of view, Emacs dumping is just a checkpointing in
the very special moment (when all Lisp libraries are loaded).

Dmitry

Re: Dumper problems and a possible solutions

[Rich Felker]

On Thu, Jun 26, 2014 at 08:32:55AM +0400, Dmitry Antipov wrote:
> On 06/26/2014 08:14 AM, Rich Felker wrote:
> 
> >Because dumping isn't really possible to do in a correct and
> >meaningful way without serious restrictions on what the code can do.
> 
> What do you think about this project: http://dmtcp.sourceforge.net/index.html?
> 
> From their point of view, Emacs dumping is just a checkpointing in
> the very special moment (when all Lisp libraries are loaded).

I consider dumping and checkpointing very different problems. With
dumping you just want to pre-generate and preserve some particular
data for future runs of the program, but you want these future runs to
behave as new processes with their own command lines, environment,
clean slate of open files, etc. With checkpointing, you want the
application not to even see that it was restarted. They also require
drastically different tools for implementation, e.g. non-hackish
checkpointing requires something like Linux namespaces so that the new
process (or family of processes, as some apps may be) sees itself as
having its original pid (and possibly pid tree), etc.

Rich

Re: Dumper problems and a possible solutions

[Eli Zaretskii]

> Date: Thu, 26 Jun 2014 00:28:39 -0400
> From: Rich Felker <dalias@libc.org>
> Cc: dmantipov@yandex.ru, emacs-devel@gnu.org
> 
> > > In my log, I see 768k allocations occuring roughly 94 times.
> > 
> > 768K times 94 doesn't get anywhere close to 400MB.
> 
> Yes, there were also a number of ~200k and ~400k allocations though,
> which I did not get around to identifying the source of.

If your 'free' is a no-op, I guess it could explain any number,
including 400MB.

Once again, I suggest to use gmalloc, or some existing less simplistic
implementation, instead.

Or, put it another way: if MS-Windows provides a way to use the libc
malloc with a custom 'sbrk' function, then perhaps the free software
platforms should have a similar feature as well (if they don't
already).  Once such a feature is provided, we could supply such a
custom 'sbrk' for the dumping phase, which will put all the data in a
static array, which will cleanly solve this issue for the observable
future.

> > > > > Those ctors are free to inspect global data. For example one might
> > > > > contain (this sort of idiom is necessary if you can't control the
> > > > > relative order of ctors): if (!init) { do_something(); init=1; }. In
> > > > > that case, the dump would save the value of init, and do_something()
> > > > > would fail to happen at runtime.
> > > > 
> > > > That's the same problem as with your clock_gettime, and it must be
> > > > fixed anyway, because any ctor run at dump time is almost certainly
> > > > picking up data that is irrelevant to the run time.
> > > 
> > > Libc could _possibly_ work around it by virtue of having full control
> > > over the init code. For other libraries, the issue is not fixable (see
> > > my above example with code that has to control dependency order of
> > > ctors), and shouldn't have to be fixed.
> > 
> > But the problem likely doesn't exist, because otherwise we will have
> > known about it by now.  Emacs cannot use such libraries.
> 
> I wouldn't be so sure. How much testing is even done with static
> linking?

In the past, quite a lot (the Emacs dumping method didn't change
significantly since about day one).  Nowadays, I don't think it is
tested much, except in the DJGPP (a.k.a. "MS-DOS") build of Emacs,
which uses static linking exclusively, because DJGPP doesn't support
shared libraries.  DJGPP's libc implements the startup code trick I
mentioned that forces reinitialization of state by functions which
need that, when they are first called in the dumped Emacs.  What's
left can be seen in unexcoff.c, where some of the global state is
explicitly reverted to its initial state before writing the image to
disk, see there in 'copy_text_and_data'.  Btw, one of these is the
'atexit' chain, which is probably relevant to other systems, if and
when they are statically linked.

> With dynamic linking, the library's state will all be lost
> across dump. Lots of the libraries emacs can optionally use have
> sketchy global state, and I wouldn't be surprised at all if at least
> one of them were failing to properly initialize in the post-dump
> emacs. The symptoms might not even be immediately visible if the state
> saved when dumping were "close enough" to correct to be used
> post-dump.

But if static linking is not used anymore on supported platforms
(putting MS-DOS aside), then this is not an issue, right?

Re: Dumper problems and a possible solutions

[Eli Zaretskii]

> Date: Thu, 26 Jun 2014 08:32:55 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> Cc: emacs-devel@gnu.org
> 
> What do you think about this project: http://dmtcp.sourceforge.net/index.html?
> 
>  From their point of view, Emacs dumping is just a checkpointing in
> the very special moment (when all Lisp libraries are loaded).

Yes, but their main focus is to preserve the system-side parts of the
program, like IP buffers and file descriptors, something that we
certainly don't want.

Re: Dumper problems and a possible solutions

[Rich Felker]

On Thu, Jun 26, 2014 at 06:03:33PM +0300, Eli Zaretskii wrote:
> > Date: Thu, 26 Jun 2014 08:32:55 +0400
> > From: Dmitry Antipov <dmantipov@yandex.ru>
> > Cc: emacs-devel@gnu.org
> > 
> > What do you think about this project: http://dmtcp.sourceforge.net/index.html?
> > 
> >  From their point of view, Emacs dumping is just a checkpointing in
> > the very special moment (when all Lisp libraries are loaded).
> 
> Yes, but their main focus is to preserve the system-side parts of the
> program, like IP buffers and file descriptors, something that we
> certainly don't want.

Indeed, this is why I consider emacs-style dumping and checkpointing
as essentially different problem domains.

Rich