Replace AST Vmalloc with standard malloc

[krader1961]

There is no good reason that ksh and related commands should depend on the AST Vmalloc subsystem. In theory just doing -D_std_malloc when building should use the standard malloc subsystem. But that obviously hasn't been tested in several years since it doesn't build.

I did all the mechanical transformations necessary to use standard malloc rather than vmalloc. Only one unit test fails with that change which was not failing before: sh_match (all three variants). The failure only happens sporadically. The failure is a SIGSEGV in this statement from line 3177 in src/cmd/ksh93/sh/name.c:

if (mp && (mp->nvname == NULL || *mp->nvname == 0)) mp = NULL;

Obviously that should never result in a SIGSEGV unless the data structure has been corrupted. Capturing a core file shows that mp->nvname is sometimes an invalid address such as 0x8. In fact, every core file I've examined has that pointer set to 0x8 (which is the ASCII BS character). Without a doubt there is an off by one bug somewhere that is causing memory to be corrupted. Something likely to be papered over by the Vmalloc subsystem if it pads the blocks differently than the native malloc subsystem or otherwise alters how dynamically allocated blocks are arranged.

[krader1961]

I just found core dumps with mp->nvname set to 0x6 and 0x7. So it's clearly not a case of stuffing a backspace char into a string buffer that is too short.

[siteshwar]

You should be able to use system malloc() functions by setting -D_AST_std_malloc=1 in CFLAGS.

[krader1961]

You should be able to use system malloc() functions by setting -D_AST_std_malloc=1 in CFLAGS.

Maybe, but that doesn't really address the issue. We need to eliminate the dependency on the AST Vmalloc code. No one is going to actively maintain that subsystem. It is a potential source of bugs. It is unlikely to be optimized for new architectures like ARM or PPC. It may not interact well with tools like Valgrind and Asan. It is a complicated interface that no one outside of the AST authors is familiar with. The fact that some of its APIs which mirror the UNIX malloc APIs also zeroes the allocated memory while the UNIX malloc version does not is a source of confusion and bugs. Vmalloc has to be eliminated as a ksh dependency.

I modified the struct Namval definition in src/cmd/ksh93/include/nval.h to optionally include padding before and after the Dtlink_t nvlink; member at the head of the structure. With padding only after that sub-structure that "fixes" the problem. Adding debug printf() calls I can see the least significant byte being modified when it should remain zero. With padding before that sub-structure the problem is also "fixed" (although I haven't yet added debug printf() calls to see how that padding is affected).

Some piece of code is incorrectly modifying a buffer that appears adjacent to a struct Namval structure. This is evident by structure members like mp->nvlink.rh.__rght being set to suspicious values like 0xd000000000000000. With padding added to the start of struct Namval those suspicious values are not seen in the Dtlink_t substructure of struct Namval. All of which implies that something is writing past the end of a buffer and affecting an adjacent struct Namval structure. It seems likely that the code only works by accident as a consequence of how AST Vmalloc allocates memory.

[krader1961]

You should be able to use system malloc() functions by setting -D_AST_std_malloc=1 in CFLAGS.

In theory, yes. But that results in this compilation failure (on macOS):

cc  -o src/cmd/builtin/pty 'src/cmd/builtin/pty@exe/pty.c.o' -Wl,-headerpad_max_install_names src/lib/libast/libast.a src/lib/libcmd/libcmd.a -lutil -lm /usr/lib/libiconv.dylib -lm /usr/lib/libiconv.dylib
Undefined symbols for architecture x86_64:
  "_memalign", referenced from:
      __ast_memalign in libast.a(vmalloc_malloc.c.o)
     (maybe you meant: __ast_memalign)
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

And despite many hours of trying to figure out why replacing vmalloc with standard malloc causes the sh_match unit test, and only that test, to fail I don't understand what is wrong. There is a significant bug in the code. Either the code assumes specific alignment of Vmalloc dynamically allocated data structures or other Vmalloc behavior that should not be visible to users of that subsystem.

[krader1961]

Jeebus H. Christ! Investigating this problem keeps revealing more bogosities. Like the fact that the macro new_of() has two (identical) definitions. And that it calls calloc() with the size and count arguments in the wrong order. Which happens to be harmless but if they can't get that right it casts doubt on the correctness of the rest of the code.

Also, new_of() is used exactly 19 times in the code currently in the master branch. It's used exactly 21 times in the 2016-01-10-beta branch which has a third, incompatible definition.

Too, given that the macro new_of() uses calloc(), it is odd that code like function nv_diropen() contains this redundant initialization of the buffer:

struct nvdir *save, *dp = new_of(struct nvdir, len + 1);
...
memset((void *)dp, 0, sizeof(*dp));

Note the memset() is completely superfluous given that calloc() was used to allocate the buffer. How in the hell does something like that get committed? I'm pretty close to giving up on this project given that the quality of the code is far worse than I expected and no one seems interested in actually improving it other than me.

[fpmurphy]

I'm pretty close to giving up on this project given that the quality of the code is far worse than I expected and no one seems interested in actually improving it other than me.

Why should anybody be interested? You are acting like a one-man wrecking crew.. You are doing a great job in assassinating the software legacy of David Korn!

[krader1961]

There's a use after free bug in the code. I added a lot of debug printf() calls. Even when meson test sh_name succeeds those debug prints show that mp->nvname in function nv_name() is invalid after this assignment:

Namval_t *nq = shp->last_table, *mp = (Namval_t *)np->nvenv;

Even when mp->nvname happens to contain a valid virtual address it points to a clearly bogus string. When it contains an invalid virtual address a SIGSEGV is the result.

Running the test on macOS with env var MallocScribble=1 causes the test to fail every single time rather than roughly 1/4 of the time. What that env var does is cause each free() call to write 0x55 to each freed byte. The resulting debug printf() calls and core dump shows that supposedly valid buffers now contain 0x55. It looks like the Vmalloc code uses a garbage collection algorithm for reclaiming freed memory which would mask this bug.

P.S., David Korn, while I respect him as much as I do Edsger W. Dijkstra or Donald Knuth, is not a god. He did not write all of the AST code. Like all software engineers he sometimes makes mistakes. Removing dependencies on things like the AST Vmalloc subsystem is not "assassinating the software legacy of David Korn". Please have some perspective. If you want to use and maintain AST Vmalloc you're welcome to do so in the 2012-08-01-master or 2016-01-10-beta branches. There is no reason the ksh command should depend on that AST subsystem. Especially since a) there are just a handful of uses of Vmalloc specific interfaces (i.e., something other than malloc(), etc.), b) those Vmalloc specific uses are trivially replaced by standard malloc calls, and c) there is zero reason to believe that any distro will ever ship Vmalloc as a first class library. I have no idea why you are taking the elimination of unnecessary AST dependencies by the ksh command so personally. Especially since removing those dependencies is helping to identify bugs in the code written by David Korn and his colleagues that we want to keep (i.e., the code, not the bugs in that code).

[krader1961]

If I stub out the free() function so it is a no-op I am unable to reproduce the problem. So I am now 100% certain this is a "use after free" bug. In fact, debugging prints shows the structure whose contents are corrupted being freed:

WTF free 0x7fe5f4c146f0
0   nv_delete + 1037
1   array_putval + 790
2   nv_putv + 520
3   _nv_unset + 1113
4   table_unset + 637
5   sh_unscope + 74
6   sh_funscope_20120720 + 2550
7   sh_funct + 770
8   sh_exec + 12202
9   exfile + 3351
10  sh_main + 4345
11  main + 38
12  start + 1

And shortly thereafter the address is used in nv_name() when it is assigned to mp thusly:

     if (!nv_isattr(np, NV_MINIMAL | NV_EXPORT) && np->nvenv) {
        Namval_t *nq = shp->last_table, *mp = (Namval_t *)np->nvenv;

Because the structure pointed to by address 0x7fe5f4c146f0 wasn't freed due to my stubbing out free() that pointer (and the pointers in the Nameval_t it points to) are still valid.

[krader1961]

More info: I augmented the free() function in src/lib/libast/vmalloc/malloc.c to poison the freed buffer with 0x55 like the macOS MallocScribble=1 env var does for the native free(). That causes exactly the same failure I documented in my previous comment. So the only reason this failure doesn't occur all the time with the current code is a consequence of Vmalloc not reusing freed blocks as quickly as the native malloc. In other words it is a nondeterministic bug that will trigger randomly based on unpredictable factors like the phase of the moon.

Whether the bug is in nv_delete() or someplace else is TBD.

[krader1961]

@fpmurphy, Are you interested in helping fix the "use after free()" bug I've found that happens to be masked by the behavior of the AST Vmalloc subsystem? If not is your recommendation to just continue using Vmalloc which masks the bug so that it manifests less often which makes it even harder to debug?

[krader1961]

I removed the "bug" label because the bug has nothing to do with removing the ksh dependency on AST Vmalloc. The bug was already present and masked by the dependency being removed. If it weren't for that bug this change would be trivial.

[krader1961]

@jelmd and @fpmurphy: Do you think we should retain the dependency on AST Vmalloc? If so, why? If we should retain that dependency are you, or your colleagues, willing to add the equivalent of the GNU MALLOC_PERTURB_ env var or the macOS MallocScribble env var so that we can readily detect bugs due to expecting malloc() to return a buffer initialized to zero or "use after free" bugs? If you or your colleagues are not willing to do that work why should ksh continue to use that implementation given that we now know it masks serious bugs in the ksh code? Which is to say, I don't understand your earlier comment, @fpmurphy, and upvote by @jelmd.

[DavidMorano]

My two cents on the continued use of VMALLOC.
For those of us who have written multithreaded KSH built-ins (plug-ins), VMALLOC has to be complied out (and its function taken over by the native MALLOC facility for example) because VMALLOC itself, in its current form, is not multithread-safe! Use of VMALLOC, in my particular experience, leads to a quick and certain core dump as soon as more than one thread touches any of the MALLOC interface subroutines. For real safety (real safety in real life), VMALLOC would not only have to be made multithread-safe, it would also have to be made fork-safe! The requirement for fork-safety is so that any child processes created (using |fork(2)| at the core it it) by either the main thread (that would be KSH itself), or by any of the subordinate multi-threads within the built-ins, or from any background threads behind it all (KSH and the built-ins) will not hang on the lock protecting access to the memory allocation system. whatever it may be. All native MALLOC facilities (that I know of) are already both multithread-safe and fork-safe. For those who may not be familiar with fork-safety, see the documentation on |pthread_atfork(3x)| (or |pthread_atfork(3c)|, |pthread_atfork(3thr)|, or whatever) for starters. Read several or all of the "pthread_atfork()" manuals you can find if your first one does not speak about the dangers of using |fork(2)| in a multithreaded environment. Also, for those who still do not "get" it, research on-line (through searches or whatever else you want) the problems with using |fork(2)| in a multithreaded environment.

Multithreading can be a high no-joke environment. Either core dumps or hangs (on locks) happen in a flash if the correct coding procedures are not followed. As far as I know, the main KSH thread itself performs |fork(2)|s without always following immediately on w/ an |execxxx(2)|. It seems to do this sort of thing when creating sub-shells (or other reasons also). A potential conflict can arise if a background thread touches any of the MALLOC interface subroutines while the main KSH executes its |fork2)|. This is OK if (and it is a big IF) the correct fork-safety procedures are followed in any library facilities (including any MALLOC subsystem) that guard themselves for multithread-safety by using any lock mechanisms (usually a mutex of some sort). Also, some system (LIBC or other) calls that call |fork(2)| may be made (due to legacy library use) from any thread in the process and then its child might go on to touch a MALLOC interface subroutine (because it has always done so in the past) assuming already that the MALLOC subsystem was both multithread-safe and fork-safe. This may be due to legacy system library code that had assumed that its own system MALLOC facility was in place (or at least that some multithread-safe and fork-safe MALLOC facility had replaced it). In general, it was not a good idea to replace a multithread-safe and fork-safe system library MALLOC facility with one that was neither. The MALLOC facility is just too central to the whole of user-space code for anyone to play around with it lightly (making it either not multithread-safe or not fork-safe, by accident or otherwise).

The short of it is that either VMALOC should be made both multithread-safe and fork-safe if it is to be continued OR any applications with multithreaded built-ins or background threads will have to continue to compile out VMALLOC in the future just as we have had to do so in the past. In my opinion, KSH should be changed to have a multithread-safe and fork-safe MALLOC facility by default. In this way both single-threaded and multi-threaded built-ins, and background threads, can be used without having to recompile KSH itself (getting rid of VMALLOC) for the multithreaded cases. Making VMALLOC both multithread-safe and fork-safe can certainly be done, but I am just much more comfortable with using the default system MALLOC facility which has already been acid tested in heavy multithreaded and fork environments.

In related matters, is VMALLOC really faster, or so much more faster, than the latest default system MALLOC facilities? Default UNIX system MALLOC facilities have generally been carefully tuned to provide the best trade-offs in both speed and memory usage (or waste) for the most general user work-load cases. Of course, "faster" does not help anybody when your process group (collection of cooperating processes) either core dumps or hangs! Enough said (for now).

[krader1961]

@DavidMorano, It is very unlikely that AST vmalloc is faster or otherwise better than the native malloc implementation. As you note the malloc subsystem provided by most distros is already highly optimized. Also, because it will be a dependency of 99.9% of the programs on a given distro it is a safe bet it is bug free. And if a problem is found a huge number of people will pounce on the problem and it will be fixed quickly. Which is not going to be true for AST vmalloc.

It is also unlikely that AST vmalloc will be optimal on a new architecture like the open source RISC-V that was created seven years ago. In fact, there is a good chance that due to the age of the AST vmalloc code it will actually behave incorrectly, or at least sub-optimally, on new CPU architectures like RISC-V.

Too, ksh should behave correctly whether the distro malloc or AST vmalloc is used. So I don't see correctness of ksh as a compelling argument to continue using AST vmalloc. Quite the contrary given that its behavior has masked at least one significant bug.

So I ask again: @fpmurphy and @jelmd, Can you make even a marginally convincing argument that AST vmalloc should remain a ksh dependency. If not what was the point of your snide comment and upvote seven days ago?

[DavidMorano]

@krader1961 wrote:

Too, ksh should behave correctly whether the distro malloc or AST vmalloc is used. So I don't see correctness of ksh as a compelling argument to continue using AST vmalloc. Quite the contrary given that its behavior has masked at least one significant bug.

Yes, I very much agree with this. KSH should be fixed to work correctly with any MALLOC subsystem, and not just with AST VMALLOC. In the interest of full disclosure, since I am not using the AST VMALLOC subsystem in my KSH (having compiled it out for the native MALLOC subsystem instead), I have an ulterior motive for KSH to work correctly without using the AST VMALLOC. But regardless, I would hope that everyone has an interest in seeing all bugs removed from KSH whether or not the bugs are readily manifesting bad problems at the moment with the present use of VMALLOC. It could be that some future order of heap allocations could cause existing bugs to manifest worse behavior: core dumps or just subtly incorrect behavior.

[krader1961]

@DavidMorano, Do you run the ksh unit tests in your build that uses the platform malloc rather than AST vmalloc? I ask because my mechanical transformation of the code (rather than relying on things like -D_AST_std_malloc=1) results in random test failures. Random in the sense that a given test, like sh_match or treemove, only fail some of the time. If I do meson test treemove, for example, it only fails roughly 1/5 of the time on my primary macOS system when using the system malloc rather than AST vmalloc.

[DavidMorano]

Do you run the ksh unit tests in your build that uses the platform malloc rather than AST vmalloc?

It has been some years now, so I may not remember correctly, but:

• I was building KSH version 93v- using NMAKE
• I think I did run the tests and got some failures, but as much as I can remember, the failures were not related to memory allocations; the failures were something else which I chose to ignore (forget what they were now)
• also , I hacked the code to build without VMALLOC even without specifying -D_AST_std_malloc=1; I specifically wanted to make -D_AST_std_malloc=1 obsolete so that VMALLOC never got compiled in under any circumstances, on purpose or by accident (remember that multithreading and VMALLOC results in core dumps)
• if I get some free time (not likely right now), I may go back and do some additional investigation on what tests fail, if any (sorry but I cannot be of more help right now)
• almost forgot, I patched 93v- over these last three years or so with most (maybe all, or almost all) of the bug fixes posted on the previous AT&T AST mailing lists

[krader1961]

Gah! Building with

#define _AST_std_malloc 1
#define _std_malloc 1
#define std_malloc 1

on macOS results in building the pty binary failing with

[428/532] Linking target src/cmd/builtin/pty.
FAILED: src/cmd/builtin/pty
cc  -o src/cmd/builtin/pty 'src/cmd/builtin/pty@exe/pty.c.o' -Wl,-headerpad_max_install_na
Undefined symbols for architecture x86_64:
  "_memalign", referenced from:
      __ast_memalign in libast.a(vmalloc_malloc.c.o)
     (maybe you meant: __ast_memalign)
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

Which suggests that trying to build the project with standard (i.e., platform) malloc is broken on anything other than SysV (i.e., ATT) or Linux platforms. It definitely means that the existing #if tests are incorrect with respect to determining whether the memalign symbol is available.

[DavidMorano]

Which suggests that trying to build the project with standard (i.e., platform) malloc is broken on anything other than SysV (i.e., ATT) or Linux platforms. It definitely means that the existing #if tests are incorrect with respect to determining whether the memalign symbol is available.

Yes, I built on a SysV (AT&T) derived system.

I do not really remember now, but I may have hacked up more than a single #if somewhere in order to get VMALLOC out of the build, obsoleting -D_AST_std_malloc=1. It was about maybe 15 years or more since I first hacked out VMALLOC, so I do not remember what I even did at the time (and had carried forward since).

[krader1961]

FWIW, I was able to build ksh using the officially sanctioned way to have vmalloc just be a thin wrapper around the system malloc. To do so I had to comment out the call to memfatal() in src/cmd/ksh93/sh/init.c and the declaration of _ast_memalign() in src/lib/libast/vmalloc/malloc.c since no implmentation was defined in addition to defining the magic preprocessor symbols. That ksh binary, not surprisingly, fails the unit tests in exactly the same manner as my branch that doesn't include any vmalloc headers or link against the vmalloc subsystem.

[krader1961]

In light of the recent work by @siteshwar to fix the use-after-free bugs I resurrected my commit from February to replace Vmalloc with the system malloc. Imagine my surprise when the API/topen.c test failed with this error: FAILED can't reopen a closed stream! [errno=0]. It turns out the unit test is broken. This is the test:

    if (!(f = sfopen(NULL, "123", "s"))) terror("Opening a stream");
    sfclose(f);
    if (sfopen(f, "123", "s") != NULL) terror("can't reopen a closed stream!");

The second sfopen() is expected to succeed. And if it does succeed it should return a non-NULL pointer. In fact it should return the original f pointer. But the test reports an error if that occurs. Obviously whomever wrote that test was verifying the broken behavior rather than the correct behavior. This is a poster child example of incorrectly writing a test that verifies broken behavior rather than verifying the API behaves as documented.

I doubt this is the only example of a unit test that is treating broken behavior as correct behavior.

[krader1961]

Regarding my previous comment about the topen.c unit test there is another bug. A use-after-free bug. That's because the sfclose() call frees the structure pointed to by f. Which means it is not safe to pass that pointer to a subsequent sfopen().

[krader1961]

And, not surprisingly, there are other tests, like src/cmd/tests/sfio/ttmpfile.c, which have the same mistake.

[krader1961]

All the tests are now passing on Linux except one: signal.sh. What is interesting is that it is now failing in two ways. The first matches a failure I've seen on BSD/macOS from day one (SIGINT handler running twice when it should run just once). The second failure is because the SIGRT stress test at the end of that unit test module doesn't terminate; e.g., test timeout. I suspect we'd see that test timeout on BSD/macOS as well if it weren't for the fact it currently fails with expected SI_QUEUE or SI_USER, got |0| on those platforms.

[krader1961]

You may have noticed that while meson test signal passes the testlog.txt file contains errors like this:

/tmp/ksh.signal.SkPKRWa/sigtst1: line 119: À-³´æ%: not found

That is from this block in src/cmd/ksh93/tests/signal/sigtst1:

case $test_mode in
*d*) sigtst2 $test_mode ;;
*)   $SHELL -c "sigtst2 $test_mode" ;;
esac

Interestingly with this change from Vmalloc to the system malloc those errors disappear. In their place the int_trap() function is run twice even though only one SIGINT is delivered. As I mentioned earlier that has been the behavior on BSD/macOS from day one. So we have yet another example of Vmalloc masking a bug.

[krader1961]

I have no doubt this change will reveal new bugs. The latest Coverity scan now identifies several previously undiagnosed memory leaks because we're no longer using the AST Vmalloc API (which Coverity doesn't know is a replacement for stdlib malloc). On the other hand this will make debugging easier and eliminate one source of leaks. That source being a dynamically allocated buffer returned by a libc function. Prior to this change the free() call on that buffer would be intercepted by Vmalloc which would recognize it didn't own the buffer and silently ignore the free request.