Sage malloc

[Georg S. Weber]

Hi sage-devel,

currently Sage uses, if possible, the system's malloc.
This has a big advantage --- that strategy certainly is the one
supporting portability of Sage best.

I don't know if there is a timeline already for the use of customized
"Sage malloc" versions for some (or all) systems Sage runs on.

But one obstacle in the past has been that Singular/omalloc had
hardcoded the use of its own copy (slightly adapted source code) of
Doug Lea's dlmalloc v2.6.5 from 1998 (see e.g. http://en.wikipedia.org/wiki/Doug_Lea
--- there is also a link to a code repository).

The most recent dlmalloc has the version number v2.8.3, and there are
interesting remarks in its history/comments since v2.6.5. Like "don't
use sbrk on Macs"; and "modern Linux kernels may still be able to
serve memory via mmap, even if sbrk fails to do so, so now do use mmap
as a backup strategy".

But up to now, if in Singular/omalloc one wanted to switch away from
the default dlmalloc v2.6.5, one ran into a "double free" problem (at
least under Mac OS X, and Cygwin). This even happens, if one plugs
back in the "default" dlmalloc code! To my knowledge, Michael Abshoff
was the first one to report this here in sage-devel, but I couldn't
find an appropriate trac ticket. So I created #5344 for this.

And there's now a patch waiting for review :-).

Depending on this issue is the patch I uploaded to trac #4181 (the
problem underlying at least trac #3760 also, and possibly #5278). It
just kicks out the use of a proprietary malloc implementation from
Singular/omalloc, and enforces to use the system's malloc instead.

Of course, there might a price to pay --- the old (but lean) dlmalloc
from 1998 probably is faster in certain instances and use cases.

But this leads us immediately back to the question of a "Sage malloc",
customized resp. customizable for specific purposes. And certainly not
only Singular/omalloc, but without doubt all of Sage would benefit
from a recent malloc implementation with good and easy-to-use
tunability (e.g. for maximum speed) on current systems. Doug Lea's
malloc 2.8.x series has a promising concept of "mspaces", one for each
thread, to name an example.

Personally, I don't have the time to do investigations, and to conduct
the necessary benchmarks and tests. Any volunteers?

Cheers,
gsw

[mabshoff]

On Feb 22, 2:19 pm, "Georg S. Weber" <GeorgSWe...@googlemail.com>
wrote:
> Hi sage-devel,

Hi,

> currently Sage uses, if possible, the system's malloc.
> This has a big advantage --- that strategy certainly is the one
> supporting portability of Sage best.
>
> I don't know if there is a timeline already for the use of customized
> "Sage malloc" versions for some (or all) systems Sage runs on.
>
> But one obstacle in the past has been that Singular/omalloc had
> hardcoded the use of its own copy (slightly adapted source code) of

> Doug Lea's dlmalloc v2.6.5 from 1998 (see e.g.http://en.wikipedia.org/wiki/Doug_Lea

> --- there is also a link to a code repository).
>
> The most recent dlmalloc has the version number v2.8.3, and there are
> interesting remarks in its history/comments since v2.6.5. Like "don't
> use sbrk on Macs"; and "modern Linux kernels may still be able to
> serve memory via mmap, even if sbrk fails to do so, so now do use mmap
> as a backup strategy".
>
> But up to now, if in Singular/omalloc one wanted to switch away from
> the default dlmalloc v2.6.5, one ran into a "double free" problem (at
> least under Mac OS X, and Cygwin). This even happens, if one plugs
> back in the "default" dlmalloc code! To my knowledge, Michael Abshoff
> was the first one to report this here in sage-devel, but I couldn't
> find an appropriate trac ticket. So I created #5344 for this.
>
> And there's now a patch waiting for review :-).

"Needs work" - it breaks 25 doctests on OSX by introducing segfaults.
See the comments I made on the ticket.

> Depending on this issue is the patch I uploaded to trac #4181 (the
> problem underlying at least trac #3760 also, and possibly #5278). It
> just kicks out the use of a proprietary malloc implementation from
> Singular/omalloc, and enforces to use the system's malloc instead.
>
> Of course, there might a price to pay --- the old (but lean) dlmalloc
> from 1998 probably is faster in certain instances and use cases.
>
> But this leads us immediately back to the question of a "Sage malloc",
> customized resp. customizable for specific purposes. And certainly not
> only Singular/omalloc, but without doubt all of Sage would benefit
> from a recent malloc implementation with good and easy-to-use
> tunability (e.g. for maximum speed) on current systems. Doug Lea's
> malloc 2.8.x series has a promising concept of "mspaces", one for each
> thread, to name an example.
>
> Personally, I don't have the time to do investigations, and to conduct
> the necessary benchmarks and tests. Any volunteers?

-1 - memory debugging is already hard enough. Do not throw in
*another* opaque allocator to make things even more complicated.

This would also require a significant speedup IMHO to be worth it and
will also require significant code changes in the library to make this
happen. We already can use pymalloc in a bunch of places and it is
very fast for small allocs. Large mallocs are handed to the C library
which on most systems just calls mmap, so I am skeptical we will see a
real speedup anyway.

And that also leaves us with porting and debugging problems.

And since there are no threads in Python code I fail to see the
advantage of the better performance under threading :)
> Cheers,
> gsw

Thanks for trying to fix this, to bad it didn't work :(

Cheers,

Michael

[mabshoff]

Oooh, I think I was completely wrong :(, so I am changing my mind to
neutral with a likely output of positive review.

Georg: Please write shorter ticket descriptions in the future for the
less patient among us. That makes it less likely that I will look like
an idiot in public :)

Cheers,

Michael

[Georg S. Weber]

C'mon,

this does need a very thorough doctesting on as many architectures as
possible! My own overnight run with Sage 3.3 with additionally #5344
and #4181 applied has finished:
{{{
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 9321.6 seconds
}}}
That's the result of "MAKE testlong" on my MacBook Core2Duo, with Mac
OS X 10.4.11 and Xcode 2.5
(with MAKE='make -j2'). So for the first time ever, *all* the long
doctests for some Sage version did succeed on this box.

I'll have a look at the ticket descriptions in a minute, hopefully I
didn't foul things up (yeah, hope dies last ...).

Cheers,
gsw

[mabshoff]

On Feb 22, 10:01 pm, "Georg S. Weber" <GeorgSWe...@googlemail.com>
wrote:
> C'mon,

Hi Georg,

Unfortunately your patch only fixes two of the three problems that pop
up when switching Singular to use the system's malloc, i.e. the
minpoly problem I mention on the ticket still occurs. I did a build
from scratch over night after patching your changes into the
Singular.spkg+rebuild of the libSingular based extensions failed some
doctests involving minpoly and I will test the new build today to make
100% it wasn't something in my build, but I don't have any realistic
hope this will be fixed by a build from scratch.

Note that those pesky invalid/double frees on OSX only pop up from
doctesting on the screen only *if* the doctest segfaults or fails some
other way, so passing doctests for you on OSX are unfortunately no
indicator that this code works for the minpoly problem. And since I
saw those failures on OSX in 32 bit mode I am sure they are still
there. This code also needs to go through a complete round of
valgrinding anyway since it needs to be verified that no leaks are
introduced. I think the fix you made is a tremendous achievement and
should definitely be pushed upstream, but alas the minpoly problem
still makes it a "needs work", especially in light of the fact that we
need a stable Sage 3.4 for SD 13 and known bugs are better than
potentially new unknown bugs :).

The minpoly problem was first observed at Dev1 when the coercion
branch was merged into Sage and we did a test build on sage.math. It
was only observable on one such build, so there is some definite
strangeness going on and back then we failed to find the root cause
and fix it. Since it "went away" when we merged some of new coercion
piece by piece we eventually closed the ticket as fixed since the
issues in question (an invalid read in libSingular that was
"impossible" since it got past a ring check) was gone. It would be
very helpful if a Cython expert could look at the generated code and
figure out what is going on for minpoly since that fix would allow us
to merge your two fixes.

> Cheers,
> gsw

Cheers,

Michael

[Michael Brickenstein]

Actually, from my perspective overloading malloc is a constant source
of pain.
This makes developers fighting malloc implementation, instead of
writing algorithms.

I would prefer Singular not doing so and I hope, that Sage doesn't
follow our bad example.

I think, the problem omalloc solves would be tackled better by the
explicit use of a pool, where it is needed.
Michael

P.S.: Did you know, that when overloading the "new operator" in C++,
there are two signatures for it:
one for new with exception support and one without.
Imagine, what happens, when overload the wrong one (essentially you
don't overload new) and overload delete correctly.

[Georg S. Weber]

We definitely *are* closing in on this devious bunch of bugs. I had
touched four Cython files (the ones noted in that other recent
Singular thread) and then did "sage -b" quite many times the past
weekend during experimenting around, but admittedly I didn't do a full
rebuild from scratch.

I'll do that as soon as I can, but I fear that the outcome will be too
late for Sage 3.4. Anyway, there is more than one way we could proceed
on --- one of them will lead us to our goal.

Probably there is more than one issue interwoven (I saw that David
Harvey once fixed a Sage ticket related to the Singular/omalloc
redefiniton of "strdup", which might hurt us here again), but that
certainly can and will be sorted out.

Cheers,
gsw

[mabshoff]

On Feb 23, 12:44 am, "Georg S. Weber" <GeorgSWe...@googlemail.com>
wrote:

> On 23 Feb., 08:10, mabshoff <mabsh...@googlemail.com> wrote:

Hi Georg,

>
> We definitely *are* closing in on this devious bunch of bugs. I had
> touched four Cython files (the ones noted in that other recent
> Singular thread) and then did "sage -b" quite many times the past
> weekend during experimenting around, but admittedly I didn't do a full
> rebuild from scratch.

Well, I have a patch that makes the libSingular extensions depend on a
Singular headers, so a -b rebuilds them automatically if I rebuild the
singular.spkg. Since I need to do that quite often I will get that
trivial patch into 3.4.

> I'll do that as soon as I can, but I fear that the outcome will be too
> late for Sage 3.4. Anyway, there is more than one way we could proceed
> on --- one of them will lead us to our goal.

Absolutely.

> Probably there is more than one issue interwoven (I saw that David
> Harvey once fixed a Sage ticket related to the Singular/omalloc
> redefiniton of "strdup", which might hurt us here again), but that
> certainly can and will be sorted out.

Do you have that ticket number handy?

> Cheers,
> gsw

Re the comments you just made on #5344: You propose to use

--with-malloc=external \
--with-external-malloc-h=dlmalloc.h \
--with-external-malloc-c=dlmalloc.c \

I *thought* that is equivalent to --with-malloc=system, but I might be
wrong. Since I use that in 64 bit mode on OSX (as well as the Cygwin
build, but that might not be needed there) and it introduces the exact
same failures I did rebuild the libSingular extensions after building
the singular.spkg in 64 bit mode using the system malloc. You patch
from #5344 does indeed make the two double free issues I observed go
away.

My initial thought was that the problems were with the Rational dtor
of Givaro ending up calling the dtor of Singular's Rational class, but
now I am starting to believe that this was caused by the mixup between
the two free implementations that you pointed out and fixed. That does
actually make a whole lot more sense since my earlier theory seemed
very strange. I come to the likely erroneous conclusion after
modifying Singular's Rational dtor to not free anything and that made
the problem go away, but it did not fix the underlying bug :(.

Now to answer your questions from the ticket:

1. Under which circumstances does this "minpoly issue" occur? Please
give me a kind of recipe.

Just build Singular.spkg with --with-malloc=system. I do believe that
is equivalent to the above solution you gave, but I am in the process
of verifying that. If it is not we might be able to get rid of the --
with-malloc=system for 64 bit OSX (and maybe Cygwin, too?) and fix
this issue at the same time.

The minpoly issue makes several doctests crash - see the list at

http://wiki.sagemath.org/osx64/sage-3.3

Notes:

* While 25 or so doctests failed on OSX 64 bit well over 900 passed
while every time at exit Sage did cause double frees, so a passing
test suite is no indication that the minpoly problem went away. The
crashing doctests where I wrote something about being libSingular
related were cases where dozens if not hundreds of double free
problems occurred right before segfaulting the Sage doctest run *way
before* it was finished, so this is not a cleanup at exit problem. I
also suspected that this might be an issue where an extension linked
against omalloc, but not libSingular, but any extension linking
against omalloc also links against libSingular, so all of those were
rebuild and a build from scratch is unlikely to fix this issue.

* The "double free at exit" issue patch you posted will probably fix
some of those failing doctest mentioned on the osx64 bit wiki page,
but I still did hit double free issues while doctesting Sage as
mentioned above, not at exit. I did hit one very quickly when testing
with my Sage 3.3. 64 bit OSX build, but after your patch they might
just harder to hit, i.e. all your long tests passed on your 32 bit OSX
10.4 build, but I had those failure in the log. I also believe that if
you build "your" singular.spkg on Linux you will see some issues under
valgrind, but if your fix is not equivalent to my use of --with-
malloc=system this patch might still solve all our problems. I will
know more in a couple hours. Due to the way the doctesting framework
works you will not see any of the double free messages unless you have
a failure or a segfault, so this is why I am hesitant to call the
minpoly issue fixed until I have substantial evidence via building +
valgrind that it truly goes away. You might have just gotten lucky
that none of the tests segfaulted.

* Since we hit the same issue at Dev1 only once I think this is just
an incredibly hard to hit bug and back then it was next to impossible
to reproduce it, i.e only one binary build on sage.math showed the
problem and we could not reproduce the problem by rebuilding seemingly
the exact same Sage release using the same compiler, etc. But now I
can reproduce this reliably over several Sage releases *every* time we
build using the system malloc on OSX in 32 and 64 bit, so I believe
this is a real bug and we will now fix it.

2. Under which circumstances, in contrast, does the "minpoly issue" go
away? Again, please give me a list of what to be done/seen.

It goes away even for 32 bit OSX build of Sage when I switch to not
using the system malloc and rebuilding the extensions depending on
libSingular. The double frees are there also when just using system
malloc (this is without your patch to the Singular.spkg in both cases,
but I will test that shortly with a 3.3 32 bit build). This is all on
OSX 10.5, so this might be a contributing factor since you test on OSX
10.4 AFAIK. If you want to reproduce this just take the same setup as
64 bit OSX from Singular's spkg-install and make it use the same
config modulo the compile flags in 32 bit OSX.

Keep up the great work, this has been an *incredible* amount of
debugging-fu and I am glad you are a Sage developer :)

Cheers,

Michael

[mabshoff]

Hi Georg,

here is the result of Sage 3.3 + your spkg patch for 64 bit. This is
compiled using --with-malloc=system:

sage -t devel/sage/sage/calculus/calculus.py # 0 doctests failed
sage -t devel/sage/sage/crypto/mq/sr.py # Segfault
sage -t devel/sage/sage/groups/generic.py # Segfault
sage -t devel/sage/sage/interfaces/lisp.py # 2 doctests failed
sage -t devel/sage/sage/libs/pari/gen.pyx # 2 doctests failed
sage -t devel/sage/sage/interfaces/maxima.py # 0 doctests failed
sage -t devel/sage/sage/rings/polynomial/multi_polynomial.pyx #
Segfault
sage -t devel/sage/sage/rings/polynomial/multi_polynomial_element.py
# Segfault
sage -t devel/sage/sage/rings/polynomial/
multi_polynomial_ideal_libsingular.pyx # Segfault
sage -t devel/sage/sage/rings/polynomial/multi_polynomial_ideal.py #
1 doctests failed
sage -t devel/sage/sage/rings/polynomial/
multi_polynomial_libsingular.pyx # Segfault
sage -t devel/sage/sage/rings/polynomial/toy_buchberger.py #
Segfault
sage -t devel/sage/sage/schemes/elliptic_curves/ell_generic.py #
Segfault
sage -t devel/sage/sage/schemes/elliptic_curves/ell_finite_field.py
# Segfault
sage -t devel/sage/sage/schemes/elliptic_curves/ell_number_field.py
# Segfault
sage -t devel/sage/sage/schemes/elliptic_curves/ell_point.py #
Segfault
sage -t devel/sage/sage/schemes/generic/affine_space.py # Segfault
sage -t devel/sage/sage/schemes/hyperelliptic_curves/
hyperelliptic_finite_field.py # Segfault

calculus.py, lisp.py and gen.pyx are issues unrelated to libSingular,
so they can be safely ignored. All of them have a likely fix and are
minor annoyances compared to the libSingular issue. So as you can see
once we fix the minpoly issue the 64 bit OSX port is in extremely
close reach to pass 100% of doctests. This should motivate our fellow
MacOSX Sage devs who know Cython as well as coercion really well
[cough RobertWB cough :p] to spend a little time on this to see what
is going on here.

I will now take the singular.spkg and change spkg-install exactly the
way you tested it on 32 bits, rebuild the spkg and extensions and
rerun the doctest.

Cheers,

Michael

[mabshoff]

On Feb 23, 4:42 am, mabshoff <mabsh...@googlemail.com> wrote:
> Hi Georg,
>
> here is the result of Sage 3.3 + your spkg patch for 64 bit. This is
> compiled using --with-malloc=system:

Ok, it turns out the failures I listed here are caused by oMalloc, but
they are not caused by Georg's patch. They are also identical
regardless if I use --with-malloc=system or Georg's second patch. I
build a 32 bit 3.3 build on OSX and all tests pass with -long, so very
nice work indeed. I will now take the spkg and run valgrind over all
doctests on Linux to see if I can scare something else out. Should I
fail again at this final task to poke a hole in George's patch it will
be merged into Sage 3.4.alpha0 tonight :)

The remaining issues for the 64 bit OSX build certainly seem rather
strange failures and are deep inside oMalloc, so the whole commentary
about the minpoly issue is likely a wrong lead. The strange thing is
also that I can reproducibly segfault doctests at the exact same spot,
but the failures occur with different commands and if I paste failing
doctests directly into an interactive Sage session they pass. Since
valgrind is available on OSX 10.5 Intel I will get it out of
valgrind's CVS in the next couple days and start to investigate.

Cheers,

Michael

[Carl Witty]

On Mon, Feb 23, 2009 at 9:53 AM, mabshoff <mabs...@googlemail.com> wrote:
> The remaining issues for the 64 bit OSX build certainly seem rather
> strange failures and are deep inside oMalloc, so the whole commentary
> about the minpoly issue is likely a wrong lead. The strange thing is
> also that I can reproducibly segfault doctests at the exact same spot,
> but the failures occur with different commands and if I paste failing
> doctests directly into an interactive Sage session they pass. Since
> valgrind is available on OSX 10.5 Intel I will get it out of
> valgrind's CVS in the next couple days and start to investigate.

One possibility is that these crashes are due to buggy __dealloc__
methods being called by the garbage collector. (This seems especially
plausible since __dealloc__ methods in the libsingular classes will
presumably be freeing memory allocated by oMalloc.)

You can try adding calls to gc.collect() to the doctests to see if the
behavior changes; if so, this very likely is the problem.

Carl

[Georg S. Weber]

Hi Michael,

I could not put that much effort into it yesterday evening, but one
overnight complete build & testlong of Sage 3.3 with a
"singular...p3a.spkg" dropped in instead of the original "p3" one did
go through flawlessly. So either the #4181 patch (malloc=system) made
the minpoly issue go away again if it had been introduced by the #5344
patch (remove potential "four double free" problem), or the minpoly
issue is not introduced by it resp. does not occur at all with my
setting (32 Bit OS X 10.4.11).

Cheers,
gsw

[mabshoff]

On Feb 24, 12:10 am, "Georg S. Weber" <GeorgSWe...@googlemail.com>
wrote:

> On 23 Feb., 18:53, mabshoff <mabsh...@googlemail.com> wrote:

Hi Gerog,

> Hi Michael,
>
> I could not put that much effort into it yesterday evening, but one
> overnight complete build & testlong of Sage 3.3 with a
> "singular...p3a.spkg" dropped in instead of the original "p3" one did
> go through flawlessly. So either the #4181 patch (malloc=system) made
> the minpoly issue go away again if it had been introduced by the #5344
> patch (remove potential "four double free" problem), or the minpoly
> issue is not introduced by it resp. does not occur at all with my
> setting (32 Bit OS X 10.4.11).

All is good and you got positive reviews for

#4181: Georg Weber: Singular/omalloc: do use the system's malloc
#5344: Georg Weber: Singular/omalloc "double free" problem

and hence by extension

#3760: creating 666 rings in singular fails with an out of memory
error on 32-bit intel os x

You Singular.spkg fix did also partially resolve

#5278: On modern fedora 64 installs, sage exists frequently when
omalloc thinks there is no memory left

but there was another issue I found a fix for in the Python tracker.
The fixed python.spkg isn't uploaded yet, but it will be there in a
couple hours.

The "minpoly" issue is still there on 64 bit OSX, but is it unrelated
to your work, i.e. the double frees also disappear on OSX 64 bit, but
the segfaults remain. They are caused inside oMalloc, but as Carl
Witty pointed out right above in

http://groups.google.com/group/sage-devel/msg/4ea57c8579828bce

the might likely be caused by timing issues with garbage collection,
etc. This will probably remain unsolved for 3.4, but it seems like a
great lead to get one of the final 64 bit OSX bugs fixed.

In total I spend 16 hours reviewing and testing your patches. I also
did valgrind all of Sage's doctests with your Singular.spkg (thank the
NSF again for giving us 24 core systems since I just used 18 of them
to do this in a couple hours), so I am signing off on all of your
fixes and will merge them in a couple hours in 3.4.alpha0.

Sorry again for giving you a hard time for the review, but in the end
it made me work on the review very hard to still poke a hole into your
patches and I failed. But I am glad I failed :). Given that this is
rather critical infrastructure work for a very important Sage release
I wanted to be extra careful.

> Cheers,
> gsw

Cheers,

Michael

[Georg S. Weber]

Hi Michael,

this got me a bit high-spirited, so I assembled another singular.spkg
with some bigger cleanups w.r.t memory allocator usage. I did a
complete build with this spkg dropped into Sage 3.3 instead of the
original spkg on my OS X 32bit box, and the build and subsequent
"testlong" runs just finished without any failure.

If you could give that one another try on some idle OS X 64 box --- if
there is something new to be seen, we should get even further. Yes, I
saw the message from Carl. But OO programming and garbage collector
stuff in not the kind of programming land I'm acquainted to. So while
his approach is from "above", mine is from "below" --- let's squeeze
hard together. But if the approach "from below" yields nothing, the I
fear others (Carl, Robert, ...) have to step in.

This spkg might also be worth a shot for some renewed Cygwin
experimentation. I tried hard to get away all proprietary functions
called "malloc" and being deing defined by using the std header
<stdlib.h> although the implementation is proprietary and inside
libomalloc. Maybe that was a problem for making a DLL on Cygwin out of
Singular/omalloc. Let's see (there's no hurry).

Oh, I should mention that this spkg is uploaded on sage.math under /
home/weberg/spkg/singular-3-0-4-4-20080711.p3test01.spkg

Cheers,
gsw

[mabshoff]

On Feb 24, 9:25 pm, "Georg S. Weber" <GeorgSWe...@googlemail.com>
wrote:
> Hi Michael,

Hi Georg,

> this got me a bit high-spirited

:)

>, so I assembled another singular.spkg
> with some bigger cleanups w.r.t memory allocator usage. I did a
> complete build with this spkg dropped into Sage 3.3 instead of the
> original spkg on my OS X 32bit box, and the build and subsequent
> "testlong" runs just finished without any failure.

Ok, as mentioned earlier I just got to Athens a few hours ago and am
catching up, but I will take this for a spin tomorrow.

> If you could give that one another try on some idle OS X 64 box --- if
> there is something new to be seen, we should get even further. Yes, I
> saw the message from Carl. But OO programming and garbage collector
> stuff in not the kind of programming land I'm acquainted to. So while
> his approach is from "above", mine is from "below" --- let's squeeze
> hard together. But if the approach "from below" yields nothing, the I
> fear others (Carl, Robert, ...) have to step in.

Ok, 64 bit OSX might still contain a mix of problems.

> This spkg might also be worth a shot for some renewed Cygwin
> experimentation. I tried hard to get away all proprietary functions
> called "malloc" and being deing defined by using the std header
> <stdlib.h> although the implementation is proprietary and inside
> libomalloc. Maybe that was a problem for making a DLL on Cygwin out of
> Singular/omalloc. Let's see (there's no hurry).

The cygwin problem was that the memory manager was never initialized,
due to hard coded flags via numerical values for certain RTLD_* flags,
but that is fixed now. That it worked at all on OSX is minor miracle
and we can probably thank the OSX linker/dlopen implementation for
that.

> Oh, I should mention that this spkg is uploaded on sage.math under /
> home/weberg/spkg/singular-3-0-4-4-20080711.p3test01.spkg
>
> Cheers,
> gsw

Cheers

Michael