Re: 4.4 change in behavior from 4.3: how to catch unset when using ${#length}
On Mon, Oct 24, 2016 at 8:25 AM, Chet Ramey wrote:
> On 10/21/16 5:41 PM, L. A. Walsh wrote:
>> On 4.3 and earlier, at least on arrays, one could have
>> the illusion of this working w/o complaint -- and returning
>> 0 when the array was 0-len or unset, or the array length,
>> otherwise:
>>
>>
>> echo ${#array[@]:-0}
>>
>> But I note it only seemed to work in arrays, and in 4.4 gets a
>> syntax error:
>>
>> echo ${#array[@]:-0} bash: ${#array[@]:-0}: bad substitution
>
> Because it is a syntax error, and if it were not it would be ambiguous.
> The ${param:-word} word expansion takes a parameter, not another word
> expansion, as the object to be expanded.
On a possibly related note, would you consider adjusting +, :+, -, :-,
as in "${var[@]+word}" to align with the meaning of [[ -v var[@] ]] as
discussed in https://lists.gnu.org/archive/html/bug-bash/2014-11/msg00099.html
? I've always felt the best use of that expansion would be to test for
a defined array (or any set array element other than arr[0]).
${var[@]+word}, ${var[0]+word}, and ${var+word} are currently
redundant to my knowledge. The latter two I can understand, but var[@]
seems inconsistent.
My best interpretation of the current behaviour is that it copies that
of $@, which doesn't really make sense IMO because arrays may be
sparse. All the effects of ${@+word} make sense but don't translate
well directly to bash arrays. OTOH [[ -v var[@] ]] since bash 4.3
makes a lot of sense to me and I think they would translate well to
the corresponding parameter expansions.
Re: [PATCH] Add-rm-rf-as-examples-loadables-rm.c
On Monday, October 31, 2016 4:44:21 PM CET Eric Blake wrote:
> On 10/31/2016 04:14 PM, Chet Ramey wrote:
> >> > Nice, thanks for the modifications.
> >
> > Here's the modified version.
> >
> > Chet
> > -- ``The lyf so short, the craft so long to lerne.'' - Chaucer ``Ars
> > longa, vita brevis'' - Hippocrates Chet Ramey, UTech, CWRU c...@case.edu
> > http://cnswww.cns.cwru.edu/~chet/
> >
> > if ((dir = opendir(dirname)))
> >
> > {
> >
> > while ((dp = readdir(dir)))
>
> Ouch. This version has O(n^2) complexity when dealing with deep
> hierarchies. GNU Coreutils intentionally prefers using
> openat()/fdopendir() and so on in order to recurse through the tree with
> O(n) complexity instead of O(n^2).
As Chet stated, the purpose was to speed up ./configure runs. For that I can't
see very deeply nested directories with million of files in it.
> > {
> >
> > if (*dp->d_name == '.' && (dp->d_name[1] == 0 || (dp->d_name[1]
> > == '.' && dp->d_name[2] == 0)))>
> > continue;
> >
> >fnsize = dirlen + 1 + strlen(dp->d_name) + 1;
> >
> >fname = xmalloc (fnsize);
> >snprintf(fname, fnsize, "%s/%s", dirname, dp->d_name);
>
> And here is part of the HUGE speed penalty that you get in large
> directories. You are mallocing a LOT of memory, and waste a LOT of work
> since the majority of the time (while within a single directory) the
> prefix is unchanged from the previous iteration, while in the deep
> hierarchy; while doing everything directory-relative completely avoids
> the need to construct ever-deeper names.
I agree. My implementation used stack space - which should be fine for real
file
names. If in doubt, a simple heap reallocation strategy is just a few lines.
But the purpose argument hits here as well.
> >if (rm_file (fname) && force == 0)
> >
> > err = 1;
> >
> >free (fname);
> >
> > }
>
> Another speed sink - your implementation removes names in readdir()
> order; GNU Coreutils has proven benchmark numbers that unlink()ing files
> that are sorted by inode number is measurably faster than unlink()ing in
> readdir() order for directories with a large number of files. Yes, it
> is more complex to set up the tracking structures to sort things, but it
> pays off in the long run.
Maybe, but very likely is that completely dependent on the type of file system,
sounds very hacky.
I wonder why there isn't a system call that recursively removes a directory +
content, at least for Linux.
Again the purpose argument hits.
> > while ((opt = internal_getopt (list, "rf")) != -1)
> >
> > {
> >
> > switch (opt)
> >
> > {
> >
> > case 'r':
> > recursive = 1;
> > break;
>
> Per POSIX, 'rm -R' and 'rm -r' are identical; a couple tweaks to this
> patch will make support for 'rm -R' work out of the box.
Not needed for the purpose, but doesn't hurt.
> > case 'f':
> > force = 1;
> > break;
> >
> > CASE_HELPOPT;
> >
> > default:
> > builtin_usage ();
> > return (EX_USAGE);
> >
> > }
>
> You do NOT support the POSIX-mandated 'rm -i'. I don't necessarily
> blame you (since it is complex), but what you should REALLY do is that
> any time you don't recognize an option, your builtin should silently
> call the real rm utility, rather than failing. That way, your builtin
> can be a faster drop-in when it recognizes the simple cases, but remains
> POSIX-compliant (assuming the fallback app is POSIX compliant), as well
> as offer ALL extensions that the normal fallback understands, rather
> than being a crippled version that causes failures to code expecting
> POSIX or particular extension behaviors.
[*]
Such a fallback on unknown options is a good thing. I simply didn't know how
to do that in an acceptable manner (within a loadable bash builtin). This
should be done for other loadables as well (e.g. 'cat'). It would serve it's
purpose as 'example' even better.
>
> > }
> >
> > list = loptend;
> >
> > if (list == 0)
> >
> > return (EXECUTION_SUCCESS);
>
> This does not match the behavior of GNU coreutils. 'rm' without
> arguments prints a usage error and exits with nonzero status. But note
> that POSIX requires 'rm -f' without arguments to silently exit with
> success. POSIX only specifies the behavior of 'rm -f' without
> arguments; with 'rm', you can do what you want (therefore you comply
> with POSIX), but it's still nice to match what other implementations do.
[**]
As you say, preferable it should match with GNU coreutils in this point.
> While I think that it is neat that this builtin can be used to speed up
> configure scripts, I don't think it is ready for prime time yet. It's
> tough to recommend that autoconf be taught to use this sub-standard
> implementation.
It works wit
Re: [PATCH] Add-rm-rf-as-examples-loadables-rm.c
On 11/1/16 11:41 AM, Tim Ruehsen wrote:
>>> if ((dir = opendir(dirname)))
>>>
>>> {
>>>
>>> while ((dp = readdir(dir)))
>>
>> Ouch. This version has O(n^2) complexity when dealing with deep
>> hierarchies. GNU Coreutils intentionally prefers using
>> openat()/fdopendir() and so on in order to recurse through the tree with
>> O(n) complexity instead of O(n^2).
>
> As Chet stated, the purpose was to speed up ./configure runs. For that I
> can't
> see very deeply nested directories with million of files in it.
The bottom line is to identify the problem you're trying to solve, figure
out the requirements and constraints of that problem, and solve it
efficiently. In this case, the problem is speeding up configure, the
requirements are only those configure imposes, and the constraints are the
expected sets of files and directories to remove. If the problem you're
solving doesn't include directory trees with millions of files in deeply
nested directories, don't waste time optimizing the case you're not going
to encounter.
>
>>> {
>>>
>>> if (*dp->d_name == '.' && (dp->d_name[1] == 0 || (dp->d_name[1]
>>> == '.' && dp->d_name[2] == 0)))>
>>> continue;
>>>
>>>fnsize = dirlen + 1 + strlen(dp->d_name) + 1;
>>>
>>>fname = xmalloc (fnsize);
>>>snprintf(fname, fnsize, "%s/%s", dirname, dp->d_name);
>>
>> And here is part of the HUGE speed penalty that you get in large
>> directories. You are mallocing a LOT of memory, and waste a LOT of work
>> since the majority of the time (while within a single directory) the
>> prefix is unchanged from the previous iteration, while in the deep
>> hierarchy; while doing everything directory-relative completely avoids
>> the need to construct ever-deeper names.
>
> I agree. My implementation used stack space - which should be fine for real
> file
> names. If in doubt, a simple heap reallocation strategy is just a few lines.
> But the purpose argument hits here as well.
I agree: if you're not going to use this implementation in a situation
where you have large directories with large numbers of files, don't worry
about that case. Solve that problem if it becomes a problem.
The allocate-dynamic-arrays-on-the-stack trick only works for gcc and
compilers that masquerade as gcc. If this turns out to be important, we
can wrap the dynamic array allocation in #if __GNUC__ and go from there.
Given the constraints of this problem, it may not be a big deal.
>
>>>if (rm_file (fname) && force == 0)
>>>
>>> err = 1;
>>>
>>>free (fname);
>>>
>>> }
>>
>> Another speed sink - your implementation removes names in readdir()
>> order; GNU Coreutils has proven benchmark numbers that unlink()ing files
>> that are sorted by inode number is measurably faster than unlink()ing in
>> readdir() order for directories with a large number of files. Yes, it
>> is more complex to set up the tracking structures to sort things, but it
>> pays off in the long run.
The question is whether that long run can reasonably be expected to make a
difference with this issue and whether the effort and complexity is worth
it. I suspect that it would take more execution time to set up the extra
data structure you need to do this than to simply remove the files in the
order readdir presents them.
>> Per POSIX, 'rm -R' and 'rm -r' are identical; a couple tweaks to this
>> patch will make support for 'rm -R' work out of the box.
>
> Not needed for the purpose, but doesn't hurt.
Sure, that's easy enough.
>> You do NOT support the POSIX-mandated 'rm -i'.
Since configure scripts never call `rm -i', I don't see this as any kind
of problem.
> [*]
> Such a fallback on unknown options is a good thing. I simply didn't know how
> to do that in an acceptable manner (within a loadable bash builtin). This
> should be done for other loadables as well (e.g. 'cat'). It would serve it's
> purpose as 'example' even better.
>
>>
>>> }
>>>
>>> list = loptend;
>>>
>>> if (list == 0)
>>>
>>> return (EXECUTION_SUCCESS);
>>
>> This does not match the behavior of GNU coreutils. 'rm' without
>> arguments prints a usage error and exits with nonzero status. But note
>> that POSIX requires 'rm -f' without arguments to silently exit with
>> success. POSIX only specifies the behavior of 'rm -f' without
>> arguments; with 'rm', you can do what you want (therefore you comply
>> with POSIX), but it's still nice to match what other implementations do.
Again, easy enough to do.
I totally understand the ideological purity argument Eric is making: we
only want the best solution that addresses every possible case optimally.
I'm usually cool with that. But in this case, it seems like a little more
pragmatism is called for.
--
``The lyf so short, the craft so long to lerne.'' - Chaucer
``Ars l
Re: [PATCH] Add-rm-rf-as-examples-loadables-rm.c
On 11/01/2016 10:41 AM, Tim Ruehsen wrote: >> >> Ouch. This version has O(n^2) complexity when dealing with deep >> hierarchies. GNU Coreutils intentionally prefers using >> openat()/fdopendir() and so on in order to recurse through the tree with >> O(n) complexity instead of O(n^2). > > As Chet stated, the purpose was to speed up ./configure runs. For that I > can't > see very deeply nested directories with million of files in it. Except that gnulib DOES have a ./configure test that intentionally DOES create a very deeply nested directory in order to prove whether the OS has bugs that it needs to work around. See http://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=blob;f=m4/getcwd-path-max.m4;h=2531ccff. Okay, that's stretching my argument a bit, since that test DOES try hard to clean up its deep hierarchy in C rather than making the shell do it after the fact with rm -r. But my point is you cannot assume that the rm module would never be called on to delete deep hierarchies. [Side note - that particular gnulib test runs in a fraction of a second with O(n) time on sane OS and file systems, but at least the Windows 2000 NTFS driver had a bug, since fixed in newer versions of Windows, where the test took O(n^2) time because the OS/file system layer was tracking things by absolute name even though the test itself was taking great pains to track things relatively and avoid the user-space O(n^2) penalty of absolute names. For several years, I had to pre-prime my config.site on my Cygwin machines to skip to the correct answer of that test if I didn't want configure to take several minutes] >> And here is part of the HUGE speed penalty that you get in large >> directories. You are mallocing a LOT of memory, and waste a LOT of work >> since the majority of the time (while within a single directory) the >> prefix is unchanged from the previous iteration, while in the deep >> hierarchy; while doing everything directory-relative completely avoids >> the need to construct ever-deeper names. > > I agree. My implementation used stack space - which should be fine for real > file > names. If in doubt, a simple heap reallocation strategy is just a few lines. If you're going to use stack space, you also have to make sure that deep hierarchies don't overflow a stack page. But switching to a heap strategy may cause speed penalties on the common case of not having deep hierarchies, so the best code has both styles with a switch based on heuristics. > But the purpose argument hits here as well. And my counterargument hits here as well: If you can cleanly fall back to the REAL rm any time that you find you are no longer dealing with your purpose-built quick version, then your quick version can take shortcuts. That is, code that calls the real rm once it hits 4k in depth doesn't even have to worry about heap allocation (that's the real rm's job, at that point) - but you can only make that dichotomy of fast for the common case but correct for the corner case if you handle the corner case by calling into the real rm, rather than failing spectacularly. > Such a fallback on unknown options is a good thing. I simply didn't know how > to do that in an acceptable manner (within a loadable bash builtin). This > should be done for other loadables as well (e.g. 'cat'). It would serve it's > purpose as 'example' even better. Yes, this I can agree with - having a GOOD example of how to make a loadable builtin sanely fall back to the real counterpart would be useful for all of the loadables to follow. -- Eric Blake eblake redhat com+1-919-301-3266 Libvirt virtualization library http://libvirt.org signature.asc Description: OpenPGP digital signature
4.4: crash in redir10 test; use after free?
Running the bash 4.4 regression test suite on OpenBSD/amd64, I noticed
a crash in the redir tests. Specifically, running redir10.sub with
bash 4.4 causes it to die with a bus error most of the time.
Program terminated with signal 10, Bus error.
#0 0x1c9ad0634009 in find_pipeline (pid=97028, alive_only=1,
jobp=0x7f7ea514) at jobs.c:1481
1481 if (p->pid == pid && ((alive_only == 0 && PRECYCLED(p) == 0)
|| PALIVE(p)))
(gdb) p last_procsub_child
$1 = (PROCESS *) 0x1c9d2b698ca0
(gdb) p *last_procsub_child
$2 = {next = 0xdfdfdfdfdfdfdfdf, pid = -538976289, status = -538976289,
running = -538976289,
command = 0xdfdfdfdfdfdfdfdf }
(gdb) p /x last_procsub_child->pid
$3 = 0xdfdfdfdf
This looks like a use after free() since OpenBSD's malloc fills
some of the freed memory with 0xdf.
--
Christian "naddy" Weisgerber na...@mips.inka.de
