The busybox "printf" command is always 32 bit even when the shell isn't.

[Rob Landley]

On Sunday 04 January 2009 22:30:21 Denys Vlasenko wrote:
> On Monday 05 January 2009 02:27, Rob Landley wrote:
> > On Sunday 04 January 2009 15:04:50 Denys Vlasenko wrote:
> > > On Sunday 04 January 2009 20:11, Rob Landley wrote:
> > > > > > > > $ printf %x 2251797561885434; echo
> > > > > > > > 7ffff79c842fa
> > > > > > > > $ ./busybox printf %x 2251797561885434; echo
> > > > > > > > 79c842fa
> > > > > > > >
> > > > > > > > I need 64 bit math to convert timeconst.pl to timeconst.sh in
> > > > > > > > the Linux kernel build...
> > > > > > >
> > > > > > > By your command
> > > > > >
> > > > > > Thanks, and I'm happy to have this patch now to help get the perl
> > > > > > removal stuff into the kernel, but going forward I think there
> > > > > > should probably be a big config switch, "use 64 bit math on 32
> > > > > > bit platforms".
> > > > > >
> > > > > > Generally if you want 64 bit math, you probably want it
> > > > > > everywhere, but 32 bit systems will be with us in the embedded
> > > > > > world for a while yet (especially arm and mips and such), and
> > > > > > doing unnecessary 64 bit math there is especially painful.
> > > > > >
> > > > > > Also, what's the deal with ash "built in printf"?  Does this
> > > > > > relate to nofork, or is it a separate implementation, or...?
> > > > >
> > > > > Shells have "builtins". Which are sort of NOFORK, but are enabled
> > > > > independently of NOFORK. The rationale is that even if you do not
> > > > > use NOEXEC and NOFORK _applets_ (which is understandable,
> > > > > they are not as stable as I would like),
> > > > > you sure want "echo", "test" etc in shells to not be slow as hell.
> > > >
> > > > The only reason nofork applets would be unstable is because the
> > > > applet in question doesn't clean up after itself or uses the wrong
> > > > error handling functions (exiting on error isn't nice if it kills
> > > > your shell).
> > >
> > > Or shell user running "rm -rfi" and pressing Ctrl-Z at rm's prompt.
> >
> > This is an existing problem.  Type "read i" and then hit ctrl-z.
> >
> > And if you think _that_ one's bad, using a builtin command in a pipeline
> > is even more fun.  ("printf hello | sleep 100" pretty much forces the
> > shell to fork not one but two child processes to maintain its sanity.)
> >
> > (I spent most of a year looking at strange corners of shell
> > implementation back when unifying the busybox shells was my problem.)
> >
> > > Think what shell needs to do to properly create a child, and clean up
> > > open fds (opened by rm by virtue of doing recursive directory removal),
> > > rm's allocaled memory etc etc etc. This is not simple.
> >
> > I know.  But I also know that shell builtins and nofork applets are
> > mostly the same problem domain, and that the _easy_ thing to do is treat
> > cd and exit and such as "hidden" nofork commands (commands that don't
> > have their names published externally by busybox) and then put 'em in the
> > same process lookup table.
> >
> > In which case, inserting all builtin commands at the beginning or the end
> > of the $PATH is the config option, and whether or not to fork becomes an
> > implementation detail, and having individual config options for each
> > command seems a bit silly.
> >
> > > Perhaps we can declare that NOFORKs are not background'able from shell,
> > > and accept the fact that this either severely restricts the set of
> > > applets that can be NOFORKs (for example, cat can't be: "cat 14gig_file
> > > >/dev/disk" takes a long time), or creates an unexpected behavior for
> > > them when they are used from shell.
> > >
> > > What do you think about it?
> >
> > Well, ask yourself what the _advantage_ of nofork is.
> >
> > Fork is a fairly cheap operation in Linux, Ingo molnar managed a couple
> > million fork/exit cycles per second (described about halfway through
> > http://kerneltrap.org/node/517 ) when he cleaned up the fork/exit code
> > for scalability a few years back.
>
> It still destroys L1 dcache IIRC.

You go out of L1 cache every time you touch a new cache line.  Fetching that 
back from L2 is cheap.  If it destroyed the L2 cache, then I'd worry.

Cloning existing page tables doesn't require an mmu flush, nor does switching 
between processes with existing page tables.  Slowaris invented threading so 
they could avoid an mmu flush when switching between threads with identical 
page tables; but Linux is smarter about page table switching in general and 
only flushes what it needs to when switching process contexts.  (Hence Linux 
processes being cheaper than solaris threads.)  That's why the kernel area is 
mapped (but masked) into all process address spaces, otherwise you'd need an 
MMU reload to make a system call.

My frame of reference here is that Ingo Molnar managed 2 million fork/exit 
pairs per second on a threading benchmark five years ago, and the Linux guys 
have made it a point of pride that threads and processes are essentially the 
same thing on Linux and perform the same.

Have you benchmarked the difference?

> > What you're really trying to avoid is an _exec_ (and the corresponding
> > need for /proc/self/exe or similar), and there are a lot more applets
> > that the shell can fork and then run as a function call without doing an
> > exec than it can run in the same process context.
> >
> > So what you need is a NOEXEC category,
>
> Hmmm... I think you missed docs/nofork_noexec.txt file.
> Please read it, and let me know what you want added/corrected there.

We were discussing this before I left, but I haven't seen that doc...

> Unix shells traditionally execute some commands internally in the attempt
> to dramatically speed up execution.

in an attempt to.  (There could be more than one attempt.)

> It will be slow as hell if for every
> "echo blah" shell will fork and exec /bin/echo.

A) it's not as slow as it used to be,
B) whether the fork or the exec is the expensive part remains to be seen. :)

> To this end, shells
> have to _reimplement_ these commands internally.

They don't have to, it's an optimization.

> Busybox is unique in this regard because it already is a collection
> of reimplemented Unix commands,

I question busybox's identity as "a reimplementation".

The gnu project was a reimplementation of existing commands, but these days we 
treat it as "the standard".  Before that, bsd was a reimplementation of 
commands, and the System III/System V stuff from AT&T included a lot of 
reimplementations of the original Bell Labs "Version 6, Version 7" stuff.  
(The ones named "Version" were fro Ken and Dennis in the research department, 
the ones named "System" were from AT&T corporate and had been productized, 
often badly.)  And this is aside from what Solaris/AIX/HP-UX/Xenix did in 
their own versions.

So busybox contains "an implementation" of these commands.  Ours is as good as 
anybody else's, we don't merely exist relative to other projects but should 
stand on our own, thank you very much.  (Admittedly the standards have fallen 
behind actual real-world use of a lot of this stuff, hence an SUSv3 shell 
being a lot less interesting than a bash clone, and sed needing -i no matter 
what the spec says.  But that's normal.)

> and we can do the same trick
> for speeding up busybox shells, and more. NOEXEC and NOFORK applets
> are exactly those applets which are eligible for these tricks.

Name an applet that isn't NOEXEC.  If you fork, you get a process context.

Launching a busybox applet already involves wandering through some code that 
has nothing to do with the applet.  The main() code (where did that go... it's 
in libbb/appletlib.c... and it's #ifdef salad.  Fun...) and possibly 
busybox_main().  Why is the whole of ash.c qualitatively different?

> Applet will be subject to NOFORK/NOEXEC tricks if it is marked as such
> in applets.h. FEATURE_PREFER_APPLETS is a config option which
> globally enables usage of NOFORK/NOEXEC tricks.

FEATURE_PREFER_APPLETS is really a pathing issue.  It means when we're about 
to exec, search for a built-in applet first, meaning treat the sucker as if 
it's at the start of the $PATH.

Treating it as if it's at the end of the $PATH is another option, and allows 
the suckers to be overridden, but it also means we go through a whole $PATH 
lookup (another relatively expensive operation, although not so bad on linux 
because negative dentry cacheing is _cool_) before falling back to the built-
in version.  If the objective is performance, that's bad.  If the objective is 
portability (we still have access to all the built-in applets after a chroot 
into an empty directory), it's not so bad.

> If it is enabled, FEATURE_SH_STANDALONE can be enabled too,
> and then shells will use NOFORK/NOEXEC tricks for ordinary commands.
> NB: shell builtins use these tricks regardless of FEATURE_SH_STANDALONE
> or FEATURE_PREFER_APPLETS.

Strikes me as another way of doing the "applets at beginning of path, applets 
at end of path" thing...

> In C, if you want to call a program and wait for it, use
> spawn_and_wait(argv), BB_EXECVP(prog,argv) or BB_EXECLP(prog,argv0,...).
> They check whether program name is an applet name and optionally
> do NOFORK/NOEXEC thing depending on configuration.

Presumably half the reason for that is to automatically do vfork() behind the 
scenes when necessary?

>     NOEXEC
>
> NOEXEC applet should work correctly if another applet forks and then
> executes exit(<applet>_main(argc,argv)) in the child. The rules
> roughly are:
>
> * do not expect shared global variables/buffers to be in their
>   "initialized" state. Examples: xfunc_error_retval can be != 1,
>   bb_common_bufsiz1 can be scribbled over, ...

In toybox I have an xexec(char **argv) function I route this sort of thing 
through, which calls toy_exec() (for the built-in commands) and falls back to 
execvp.  I can trivially set a flag the first time it's called so that if it's 
called again it can memset the global state.

My global state is:
  char toybuf[4096];
    - working roughly like bb_common_bufsiz1 but _never_ used
      by any of the lib/*.c functions; yeah I need to fix dirtree)
  union global_union this;
    - union of each command's global variable structures, initialized to zero
      except for the parts automatically filled out by the command line
     argument parsing logic.  Currently largest user by far is cksum with
     "unsigned crc_table[256];", possibly that should be on the stack instead.
  extern struct toy_context toys;
    - Data available to every applet, completely filled out by toy_exec() so
      doesn't need to be zeroed anyway.

So I could tell xexec():
  static rerun=0;
  if (rerun) {
    memset(toybuf, 0, sizeof(toybuf));
    memset(this, 0, sizeof(union global_union));
  } else rerun=1;

And viola (a type of stringed instrument), it's re-enterable.  Although the 
logical place to put that is actually toy_init()...

Why any of the individual applets would have to care about this, I have no 
idea.

> * do not expect that stdio wasn't used before. Calling set[v]buf()
>   can be disastrous.

Toybox uses file handle operations a lot more than busybox does.

The new zero copy Linux pipe buffer infrastructure (introduced in 2.6.11, 
http://lwn.net/Articles/119682/ ) can actually aggregate multiple small writes 
if it runs out of space before the consumer's caught up.  (They added 
aggregation because the linux kernel build was spitting out a bunch of "..." 
individual periods as a progress indicator, and the first version maxed out at 
16 individual writes before blocking and waiting for the recipient to consume 
the data.)  Doesn't mean it always _will_ aggregate, but it means it's less 
interesting to try to fiddle with it in your own programs.

(Oh, and the nagle algorithm has been doing this for the network for years.)

In general, if somebody closes stdin or redirects stdout, it's inherited by 
child processes anyway.  Shells already have to be careful about leaving extra 
files open because those are inherited across an exec anyway.

> * ...
>
> NOEXEC applets save only one half of fork+exec overhead.

Bench it.

Between the path lookup, tearing down the old page tables and setting up new 
ones with different mappings (which is where your serious cache flushing comes 
in because the translation lookaside buffer went bye-bye and it had to dispose 
of its resources while it still knew what they were), faulting in the pages 
for the new executable, and doing the dynamic linking, I suspect exec is more 
like 90-95% of the work.

So that would mean NOEXEC applets save much more than just half the overhead, 
for a lot less than half the work.

> NOEXEC trick is disabled for NOMMU build.

Trying to optimize NOMMU at _all_ is a losing proposition if you ask me.  It's 
enough of a struggle to get things to work at all there.  Making nommu fast is 
a bonus for me, not a goal.

>     NOFORK
>
> NOFORK applet should work correctly if another applet simply runs
> <applet>_main(argc,argv) and then continues with its business (xargs,
> find, shells can do it). This poses much more serious limitations
> on what applet can/cannot do:

Very much so. :)

> * all NOEXEC limitations apply.
> * do not ever exit() or exec().
>   - xfuncs are okay. They are using special trick to return
>     to the caller applet instead of dying when they detect "x" condition.

At a guess, the setjmp/longjmp trick?

>   - you may "exit" to caller applet by calling xfunc_die(). Return value
>     is taken from xfunc_error_retval.
>   - fflush_stdout_and_exit(n) is ok to use.
> * do not use shared global data, or save/restore shared global data
>   prior to returning. (e.g. bb_common_bufsiz1 is off-limits).
>   - getopt32() is ok to use. You do not need to save/restore option_mask32,
>     it is already done by core code.

Toybox infrastructure calls the option parsing logic as part of toy_init(), so 
by the time you get to the main function your arguments are already digested 
into toys.optflags, your "this" global struct, and any remaining unparsed 
arguments in this.optargs.

> * if you allocate memory, you can use xmalloc() only on the very first
>   allocation. All other allocations should use malloc[_or_warn]().
>   After first allocation, you cannot use any xfuncs.
>   Otherwise, failing xfunc will return to caller applet
>   without freeing malloced data!

If you want to get disgusting you can have xmalloc() create a linked list 
during nofork operation, create an xfree() that ordinarily wraps normal free() 
but during nofork removes allocations from the list (and if it's a standard 
cheesy reverse order linked list where new entries get added to the head of 
the list, then recent allocations should be near the beginning of the list so 
free() shouldn't have far to look for 'em.  Then your nofork exit function can 
traverse the list to free everything before doing the longjmp.

I doubt it's worth it, though.  Prematurely returning commands don't just leak 
memory, the leak file handles and memory mappings too.  They may have done a 
chdir(), umask(), setsid(), setpgid(), redirected stdin/stdout/stderr, or 
changed their controlling terminal (tcsetpgrp, fun for the whole family).  If 
you were running as root they may have done a chroot(), set the real, 
effective, saved, or filesystem user IDs (and the same for group)...

You _can't_ automatically clean up after half that stuff.

Although I do note here an SUID_ALWAYS tagged NOEXEC applet needs to exec if 
it's not running as root.  Just FYI. :)

> * All allocated data, opened files, signal handlers, termios settings,
>   O_NONBLOCK flags etc should be freed/closed/restored prior to return.

Environment variables, process priority, stdin/stdout/stderr ferror() state...

There's a reason I didn't go down that rathole too far.

> I think making it a builtin unconditionally may be a good thing.
> It's 05:29 here, so I'll postpone it a bit. :)

If it can ever be builtin, it probably always should.  You can call it with a 
path if you really need an external one.  (How do you disable bash's builtin 
"echo"?  There's probably a way, but I've never bothered to learn it, and a 
quick check of the bash man page... is a contradiction in terms, really.)

Rob