[Toybox] pull: fix modprobe, login, switch_root, improve init, reboot

[Rich Felker]

On Sun, Oct 04, 2015 at 11:41:45PM -0500, Rob Landley wrote:
> On 10/04/2015 10:02 PM, Rich Felker wrote:
> > On Sat, Oct 03, 2015 at 05:44:54AM -0500, Rob Landley wrote:
> >>> It would be nice to audit all the toys that are
> >>> intended to be long-running rather than commands that just do their
> >>> thing and exit to reduce or eliminate any fatal exits after they reach
> >>> the 'long-running' part.
> >>
> >> Except strlower() calls xstrdup() in the I18N case and dlist_add() calls
> >> xmalloc() and dirtree_add_node() calls xzalloc()... You can _try_ to
> >> avoid it, but it's not a simple thing to audit. (And no, you can't check
> >> whether or not xexit() and such are linked in because common
> >> infrastructure like toy_init() and the option parsing logic use them.)
> > 
> > There should be static analysis tools that can show the call graph
> > restricted to actually-reachable code. As long as the false-positive
> > rate for reachability is low (and no false negatives) this should make
> > such auditing practical.
> 
> Or I could just the longjmp() solution that's already in the code.

I don't object to your existing approach, but it would be nice to find
if/where it leaks memory and fix those cases. If there are
circumstances under which a user can cause a long-running process to
repeatedly leak memory, that may be a problem. I don't think this is a
high priority task but it's nice to have a note of how it could be
approached if/when there's a desire.

> > For strlower, how do you manage knowing whether to free the result, or
> > is it only used in places where you wouldn't care about freeing?
> 
> Library code doesn't know what context it's used from so if it's an
> internal usage it can't leak it. (There's a libbuf analogous to toybuf
> that can elide small fixed allocations though.)
> 
> In the case of strlower though, it returns the new allocation and it's
> the caller's job to free it. But the allocation could fail.

OK.

> > An in-place strlower is definitely possible if you just make sure to
> > allocate the right amount of memory to account for any possible
> > expansion on case conversion at the time of allocation.
> 
> I am _so_ not going there, and that would modify the string passed to it
> which isn't guaranteed to be writeable, which is why I didn't do that.
> 
> (I note that in the i18n case I just arbitrarily doubled the size, plus
> null terminator. If characters can more than double in size during
> encoding between upper/lower case, I'd need to do more than that.
> Probably a two pass approach or something doing realloc.)

I think in practice this is safe. The only possible character sizes
are 1, 2, 3, or 4 bytes. Mappings that result in size changes 1->2,
2->3, 2->4, and 3->4 are all bounded by 2x. The only possible size
changes that would exceed 2x are 1->3 and 1->4. These would be
mappings of an ASCII character to a 3- or 4-byte character. The only
time an ASCII character is ever mapped outside ASCII for case mapping
is for the Turkish dotted/dotless I/i, and these are U+0130 and
U+0131, well within the 2-byte UTF-8 range. So I don't think there is
or will ever be a 1->3 or 1->4 case mapping.

> >> The standard idiom in toybox is to abort on fatal errors, which is the
> >> right thing to do 90% of the time and means we're not _ignoring_ errors
> >> by failing to check for them. I can't change that idiom for the
> >> remaining 10%, but I can convert it into exception handling with
> >> throw/catch. That's not ideal, but it's workable.
> >>
> >> (I have actually thought about this before. It's on the todo list. And
> >> it affects the nommu stuff too because allocation failures are _much_
> >> more likely in a context where all allocations must be contiguous and
> >> memory fragmentation limits your maximum allocation size, so malloc
> >> failures aren't just due to resource exhaustion there...)
> > 
> > By "all allocations must be contiguous" do you just mean "if I
> > malloc(N), there must be N physically consecutive bytes free for it to
> > succeed"?
> 
> Yes. That's a nommu constraint.
> 
> > Certainly the whole heap does not need to be contiguous, and
> > the physical contiguity requirement doesn't put any more constraints
> > on you than the virtual contiguity requirement does on MMU-ful systems
> > until you reach allocation sizes at least as large as page size (and
> > probably a good bit larger to make a practical difference).
> 
> You can't defragment on nommu. A 5 byte allocation in a virtual context
> can straddle pages if necessary, and the multiple small allocations are
> confined to the process's heap (allocated with page granularity) so
> they're naturally collated. That means fragmentation is _inherently_
> less of an issue on a system with an mmu. Your process's allocations
> don't interleave with other process's allocations within a heap, or if
> that heap can be logically contiguous from the process's point of view,
> so the entire category of issue basically doesn't come _up_ on mmu systems.
> 
> (I very vaguely remember a bit about this from college, how the various
> malloc strategies fit different contexts, and the "grab the smallest
> free space that fits the new allocation" strategy actually maximizes
> fragmentation with physical mapping.

Yes, but no good malloc will grab the smallest free space from the OS
except for large allocations served directly by mmap. I don't know the
details of how uClibc's malloc works, but when musl uses mmap to
construct the main heap (i.e. when brk is not available) it expands
the heap in exponentially-growing units. The first 2 mmaps are 4k, the
next 2 are 8k, the next 2 16k, etc., and expansions are permanent for
the lifetime of the process. The same strategy that prevents
fragmentation of the virtual address space on hosts with MMU also
prevents catastrophic fragmentation of physical memory on NOMMU hosts.

> There were whole fields of study on
> this back in the 60's and 70's...)

I would love the see some of them. The topic still matters just as
much on systems with MMU as it does for NOMMU if you're concerned
about running out of virtual address space (which is a real issue on
32-bit) or wasting memory (which is an issue everywhere unless you
just take the nasty approach of throwing 10 or 100 times more memory
than you should need at the problem). For musl's next-gen malloc I
want to solve both fragmentation problems inherent in the dlmalloc
type approach and excess need for synchronization between cores.

Rich

 1444596680.0