[Aboriginal] [Toybox] And back.

[Rob Landley]

On 04/09/2016 05:58 PM, Andy Chu wrote:
> On Sat, Apr 9, 2016 at 2:52 PM, Rob Landley <rob at landley.net> wrote:
>> I spent last week traveling to present at two conferences:
>>
>>   http://flourishconf.com/2016/speakers.php?id=18
>>
>> http://openiotelc2016.sched.org/event/6D9v/building-a-cpu-from-scratch-jcore-design-walkthrough-rob-landley-jeff-dionne-se-instruments
>>
>> Hopefully the videos will be up before too long. The slides are
>> http://landley.net/talks/flourish-2016.txt and
>> http://j-core.org/ELC-2016.pdf
> 
> Welcome back, and thanks for the links!  I'm always looking for things
> to put on my queue of programming videos.  I have to admit some
> ignorance about open hardware and nommu but it sounds interesting.

That's my $DAYJOB. They let me work on toybox about half the time
(because I use it), and the rest on stuff more directly in support of that.

I think open hardware (of the "VHDL is a proramming language, your
edit/compile/test cycle is under 10 minutes" type) has approximately the
same world-changing potential as self-hosting Android development
systems, but its impact is 5-10 years farther into the future. The
android stuff is on a tighter deadline...

>> And several days before that reinstalling my laptop (well, before
>> reinstalling I tried to upgrade ubuntu 12.04 to 14.04 _without_ a
>> reinstall, that video is at https://www.youtube.com/watch?v=26RTlPgg-tA ).
> 
> FWIW I think it's always wise to leave yourself a path to back out,
> rather than doing destructive updates (which I gather was an issue).
> I have two interchangeable OS partitions, and $HOME lives on a third
> data partition.  So if the new OS has issues I can always go back the
> old one by rebooting.

Oh I rsynced the whole mess to another machine before starting. (Among
other things I didn't trust the steam package not to still have the bug
where when you uninstall it you got an rm -rf ~ done on your home
directory.)

I'm just sad that upgrading ubuntu to a new release (instead of
reinstalling) has never worked properly for me in the history of ubuntu.
I knew better, but I gave it another try anyway.

>> So if you have a pending todo item that you think I should be working
>> on, giving me a poke to remind me where I was wouldn't go amiss.
> 
> I think we have a few open threads:
> 
> (1) expr has memory safety issues on master.  I posted a message
> demonstrating this with the ASAN patches:
> 
> http://lists.landley.net/pipermail/toybox-landley.net/2016-March/004884.html

Hmmm...

  # Case that triggers ASAN error
  testing "regex" "expr 3 : '\(.\)' = 4 : '\(.\)'" "0\n" "" ""

Ran it and it works fine for me, how do I enable the address
sanitization you're using to see the complaint? (It's giving me three
different stack dumps and referring to threads in a non-threaded
program, so my approach to that would just be to fling printf()s around
until I tracked down the line of code it was complaining about and then
walk through that...)

Is this an external program ala lint? An llvm mode? Something valgrind
does? Some new gcc feature added in 5.x?

> A lot of this has fallen out of my cache,

Mine too, 's why I asked. :)

I didn't write this command, so I don't have as good a mental model of
it as I should. I'm chipping away to try to GET a good mental model,
without which I can't properly maintain it...

> but I think at this point it
> makes sense to just follow the original strategy and be done with it:
> http://lists.landley.net/pipermail/toybox-landley.net/2016-March/004827.html

If we're letting the system free this memory when we exit(), fine. If
we're freeing it ourselves, then we should properly track the object
lifetimes.

> This patch is easy to inspect as correct... (and passes ASAN tests,
> etc.)  The other ones require a lot of code reading and are not
> correct.  The common case at runtime I suspect is 0, 1, or MAYBE 2
> mallocs, so it basically isn't going to matter AFAICT ... if there is
> a fast way to grep for expr on say Aboriginal packages that could help
> answer this.

The shell has $(( blah )) and I'd like to extend this to be able to
handle that, and/or factor out common code to handle both. So I care
about more than just getting one use case right.

> (2) I sent patches for a couple buffer overflows found by
> AddressSanitizer.  These are quite obvious and should be easy to
> review.
> 
> http://lists.landley.net/pipermail/toybox-landley.net/2016-March/004852.html

Hmmm, lotsa fdopen() calls, several of which fclose() a filehandle looks
like loopfiles() needs a FILE * variant...

[leaves window open for 3 days while distracted by other things]

Ok, but I should probably just check in a fix to _this_ problem first.

> http://lists.landley.net/pipermail/toybox-landley.net/2016-March/004853.html

In pending for a reason, but thanks for the fix. :)

(I tend to apply fixes to pending verbatim on the theory that it's
unlikely to make it worse. With expr I'm reviewing it to promote out of
pending next release, so I'm trying to take ownership of that code. When
I get around to doing that with diff.c, the _t suffixes are 100% going
away again at the very least, FYI. Since struct is its own namespace,
nothing would ever NOT have a _t in there so adding it is silly.)

> Given that the test coverage is fairly low (e.g. there was an
> IRC-reported bug in 'paste', but no tests for paste), I think if we
> made a wide pass and added very basic "hello world" tests for every
> command, I'm sure we'd find dozens of real bugs.

Indeed. I have a todo item to go through the help text of each command
and make tests for every corner case of the usage documented in there.

Then go through the posix specs for each posix command and make tests
for every relevant statement of _that_.

For commands not in posix, use the relevant man page instead, although
that needs to be more heavily filtered. (Deviations from posix should
probably be documented. deviations from somebody else's man page, not so
much. But we might want to fluff out the help text.)

Toybox help text is hard: I want it to be concise, thorough, and easily
understandable. The first two goals are directly opposed to each other,
and both fight with the third. :(

(I'm pretty sure there are commands where I've spent more time on the
help text than on the code.)

> The nice thing about ASAN, etc. is that it increases the value of any
> tests you write.  For every code path you hit, you get assertions for
> free.

Ok.

> I'm sure that building Aboriginal with toybox_asan, etc. would
> shake out tons of issues.

Indeed. (Not necessarily ever externally visible on single-threaded
processes, but yay fixing stuff.)

> (3) The big test harness patches.  I sent out patches to run tests
> with 3 sanitizers: AddressSanitizer, Memory Sanitizer,
> UndefinedBehavior Sanitizer.  They are based on runtime instrumention,
> so there are pretty much no false positives (except maybe MSAN because
> I think you need to build libc with it too).  Nonetheless they are
> finding real bugs.
> 
> In addition, I got code coverage working a few weeks ago, which I
> think you expressed interest in.  I didn't sent out a patch for it.
> This a 4th form of runtime instrumentation -- as I recall it requires
> a change to toybox source, because toybox calls _exit() rather than
> exit().  The runtime instrumentation hooks exit() to write the
> coverage data file.

I've found the occasional if (toys.optflags && FLAG_x) thinko in the
code LONG after it should have caused some sort of problem, and yet... I
want the test suite to be thorough enough to catch those, but filling
out the test suite to that depth is a pre-1.0 goal for me. (As in
implement it all, then test the heck out of it.)

But right now people are still using stuff out of pending, which should
never happen, and is my fault for not keeping up. :)

(This weekend's been j-core catcup from ELC. And I still haven't figured
out why postfix is mad at me; kinda sad to give a talk, get 40 people
try to sign up to the mailing list, and the mailing list not actually
work a week later. Too many plates spinning...)

> I'm wondering what the general opinion is on these... I think the expr
> example shows that they are quite useful.  I saw that you started
> applying some of the fixes... although I would caution that there is
> actually some substantial knowledge/testing embodied in those patches
> -- I wrote them twice as mentioned, once in make and once in shell,
> and it definitely got better the second time.

I need to do a proper review pass on expr to promote it out of pending.
I just need a spare solid 8 hour block of time with no other demands on
it. :)

> (4) I didn't respond to your last e-mails yet... we were talking about
> shell and make.  So I actually have been cranking on my shell
> implementation in the last 1-2 weeks :)  I prefer having something
> concrete to talk about.
> 
> This is something I've wanted to do for a long time.  I had been
> experimenting with Python, Lua, OCaml, Lisp, etc. over the years.  And
> I guess toybox was to some extent an evaluation for writing it in C.
> 
> But it ended up in C++,

Good luck with that, I'll be over here.

> which is surprising to me (and probably to
> some people who have heard me complain about C++).  But it's turning
> out really well

C++ and Perl share the characteristic that the true horror of the
language doesn't crop up until the project's being maintained my
multiple people over a long period of time.

> -- one thing that enabled it is the re2c code
> generator, which is huge.  It takes regexes and generates compact
> state machines with no dependencies.  It's modular and doesn't force
> your code into weird patterns (very much the opposite of lex/flex).

As I said: good luck with that.

Busybox has hush and ash, before that there was sash and nash, I believe
android is using mirablos' msh, Ubuntu switched from bash to dash for
the dumbest reason ever:

  https://wiki.ubuntu.com/DashAsBinSh

(Yes, seriously, "our init scripts are too slow and changing the
#!/bin/sh at the start of each one is too intrusive a change, let's
change what /bin/sh points to for the first time since Linus Torvalds
extended his terminal program to handle the system calls to run bash in
1991 making it the first program Linux ever ran, I.E. let's break
compatability with the ONE thing that every Linux system in the entire
history of Linux has agreed on, and in the process breaking all sorts of
stuff including the kernel build. Oh, that didn't fix our init scripts'
slowness? Screw it then, replace "init" with "upstart" a year later, but
never EVER admit that redirecting /bin/sh was a MISTAKE, let alone undo
it... You may notice I stopped trusting Ubuntu's technical judgement
about this time because really: they're INSANE.)

I'm writing a new shell because:

A) toybox could benefit from one (standalone static binary as a system
rescue tool, running internal commands speeds up shell scripts a lot,
getting the minimal self-hosting package set down, and busybox already
has one and replacing busybox is still a checklist item.)

B) it would be nice to have a reasonable bash replacement available,
with dash and msh and hush _aren't_. (Ash is sort of halfway there, but
missing obvious useful stuff and the code is a mass of historical scar
tissue originally bolted to the side of busybox by a russian programmer
who used a PC translation program instead of learning english, meaning
in the 3 years I interacted with him he never got the tiniest bit better
at communicating, nor did he ever have the patience to puzzle through
more than about three sentences at a time of what we sent to him...
Sorry, battle scars showing there.)

> For the parser, I took the POSIX shell grammar and ported it to ANTLR
> (but I'm NOT using ANTLR for any code generation, because it's
> ridiculously unsuitable for that, in contrast to re2c).
> 
> One thing I didn't quite realize is how much context-free grammars are
> like code... they need refactoring, testing, and have performance
> implications.  IMO the POSIX grammar is not really suitable for source
> code, although bash seems to have done that...
> 
> ANTLR actually does a nice lookahead analysis on the grammar, which
> can help performance. And it's a good tool because it uses top down
> parsing algorithms, which fits the shell a lot better than bottom up
> parsing like Yacc.
> 
> I'm close to the point of porting this debugged grammar to a recursive
> descent parser, which will then be able to accomodate all the special
> cases that POSIX lays out.  (I am trying to avoid the asymptotic
> approach to correctness that some shells seem to use...)

Ok.

> I also wrote a little shell test framework and have been torturing the
> nooks and crannies of bash and dash.  I found one place where bash is
> not POSIX conformant and dash is, and some other differences.

If nobody's cared about bash's lack of posix conformance in the past 20
years, I'm pretty sure posix is what's broken here. (Or at least
irrelevant.)

> All in all I think the POSIX grammar is pretty good and helpful, although it
> only covers a single sublanguage out of the 3 or 4 that are in the
> shell.

I'll take your word for it?

Back in 2006 I printed out the Advanced Bash Scripting guide and made it
about 1/3 of the way through it on various bus rides. I have the problem
reasonably scoped, but am doing a variant of "shortest job first"
scheduling by leaving the really nasty ones for last unless something
bumps them up the todo list.

> So, the implementation obviously isn't going to be in toybox directly,
> but it could be used for Aboriginal.

Could, but why? (If you want to test it yourself that way, have fun?
Really making a Linux From Scratch chapter 5 with your shell instead of
bash and then building linux from scratch under the result should get
you about as good testing...)

> That's still in the future
> though, since I've only implemented a very basic runtime.  It executes
> basic commands, but nothing else.  95% of the work has been
> lexing/parsing so far.
> 
> I will have to write something up, because it seems there hasn't been
> a modern implementation of shell in awhile.

There's a reason?

Ping @mirabilos on twitter, he'll get a kick out of this.

> Most implementations use
> gotos, global variables, and macros a lot -- and not in a good way.
> For example, bash's

FSF code is never a good example of anything. I intentionally don't read
the FSF implementations, ever. Didn't when I was doing busybox, still
don't. I'll run them under strace, that's as far as I go.

> function/macros to get the next token is somewhat
> ridiculous, and ash/dash use some horrible goto tricks as well.  The
> mksh lexer seems somewhat principled although I didn't follow it all.

I read a bit of pdksh (public domain and all), but it seemed too old to
be of much help in terms of actual usable code...

> Andy

Rob