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 _______________________________________________ Toybox mailing list [email protected] http://lists.landley.net/listinfo.cgi/toybox-landley.net
