REG_STARTEND (regex)

REG_STARTEND (regex)

[Daniel Cegiełka]

Hi,
Is there a chance that musl will support REG_STARTEND? It is used
quite often in *BSD.

http://www.sourceware.org/ml/libc-alpha/2004-03/msg00038.html

Daniel

Re: REG_STARTEND (regex)

[Rich Felker]

On Tue, Jan 15, 2013 at 11:34:59AM +0100, Daniel Cegiełka wrote:
> Hi,
> Is there a chance that musl will support REG_STARTEND? It is used
> quite often in *BSD.
> 
> http://www.sourceware.org/ml/libc-alpha/2004-03/msg00038.html

Probably not, at least not in the immediate future. The original TRE
code actually worked with strings as a base+length rather than
null-terminated internally, which meant a lot of things were a lot
more expensive they should be; if I remember correctly, even searches
for text guaranteed to be found near the beginning of the string
required strlen for the whole string, i.e. the whole operation was
needlessly O(n). In one of the cleanup rounds, I changed it to use
null termination, which simplified a lot of the tests; many checks
collapsed away since \0 was automatically not in the set being checked
against and thus no second check was requried.

If/when we overhaul regex again, I'll certainly consider this request
and see if the design can be made such that it's not expensive. But I
don't see any easy way to do it right now short of making a temp copy
of the string. That _would_ be possible; \0 could be replaced with
\xff, and \xff replaced with \fe, and special logic added to allow
\xff (which is otherwise an invalid byte and never matchable) while
still rejecting \xfe and other invalid bytes. This would require no
changes to the internals, but it would have the property of requiring
an O(n) malloc/memcpy, which is certainly not very appealing.

Rich

Re: REG_STARTEND (regex)

[Daniel Cegiełka]

Thank you for your reply. It's terribly sad that there are so many
problems with portability. There are a lot of high-quality tools in
the *BSD, which could be used in Linux. And rather than stick to the
POSIX people still create a barrier, like REG_STARTEND, 'sed -i',
bison (instead POSIX yacc), perl in the Makefile(!!!) etc.

'sed -i' is used in many programs (even linux, e2fsprogs, old libcap
etc.) and there is no chance to avoid it. So I'm looking for an
alternative to the gnu-sed+gnulib. I found that sed from FreeBSD has
support for -i and is much smaller than the gnu sed:

http://svnweb.freebsd.org/base/release/9.1.0/usr.bin/sed/

ls -lh /bin/sed ./sed
-rwxr-xr-x 1 root root 143K Jun 22  2012 /bin/sed
-rwxr-xr-x 1 root root  35K Jan 15 14:32 ./sed

(compiled on linux with glibc)

Now I want to use it with musl, but sed (and grep) from FreeBSD uses
REG_STARTEND and I don't really know how to solve this problem.


http://svnweb.freebsd.org/base/release/9.1.0/usr.bin/sed/process.c?revision=243808&view=markup

651 	/* Set anchors */
652 	match[0].rm_so = 0;
653 	match[0].rm_eo = slen;
654 	
655 	eval = regexec(defpreg, string,
656 	nomatch ? 0 : maxnsub + 1, match, eflags | REG_STARTEND);


Does anyone have suggestions on how this can be modified to be able to
use it with musl.

Daniel

Re: REG_STARTEND (regex)

[John Spencer]

On 01/15/2013 04:16 PM, Daniel Cegiełka wrote:
>   So I'm looking for an
> alternative to the gnu-sed+gnulib.

the sed from busybox 1.20.2 works perfect for me, entire sabotage is 
built using it.
and there are some things like ncurses that make heavy use of it, so i'm 
quite confident it's either completely or almost bugfree at this point.
i dont think it will be much work to rip it out of busybox to make it a 
free-standing tool.

Re: REG_STARTEND (regex)

[Daniel Cegiełka]

2013/1/15 John Spencer <maillist-musl@barfooze.de>:
> On 01/15/2013 04:16 PM, Daniel Cegiełka wrote:
>
> the sed from busybox 1.20.2 works perfect for me, entire sabotage is built
> using it.
> and there are some things like ncurses that make heavy use of it, so i'm
> quite confident it's either completely or almost bugfree at this point.
> i dont think it will be much work to rip it out of busybox to make it a
> free-standing tool.

busybox's tools share a lot of code.. and it is not easy to separate
one tool without moving whole bblib. This is a good option if you want
to use busybox as a base system/tools.

Daniel

Re: REG_STARTEND (regex)

[Rob Landley]

On 01/15/2013 09:50:16 AM, Daniel Cegiełka wrote:
> 2013/1/15 John Spencer <maillist-musl@barfooze.de>:
> > On 01/15/2013 04:16 PM, Daniel Cegiełka wrote:
> >
> > the sed from busybox 1.20.2 works perfect for me, entire sabotage  
> is built
> > using it.
> > and there are some things like ncurses that make heavy use of it,  
> so i'm
> > quite confident it's either completely or almost bugfree at this  
> point.
> > i dont think it will be much work to rip it out of busybox to make  
> it a
> > free-standing tool.
> 
> busybox's tools share a lot of code.. and it is not easy to separate
> one tool without moving whole bblib. This is a good option if you want
> to use busybox as a base system/tools.

make allnoconfig
make menuconfig
switch on just "sed"
make
mv busybox sed

Rob

Re: REG_STARTEND (regex)

[John Spencer]

On 01/15/2013 04:50 PM, Daniel Cegiełka wrote:
>
> busybox's tools share a lot of code.. and it is not easy to separate
> one tool without moving whole bblib.

by ripping it out of busybox i meant that you only copy the required 
functions out of it.
i dont think the sed applet will use more than 10% of libbb's functionality.

Re: REG_STARTEND (regex)

[Rob Landley]

On 01/15/2013 12:38:51 PM, John Spencer wrote:
> On 01/15/2013 04:50 PM, Daniel Cegiełka wrote:
>> 
>> busybox's tools share a lot of code.. and it is not easy to separate
>> one tool without moving whole bblib.
> 
> by ripping it out of busybox i meant that you only copy the required  
> functions out of it.
> i dont think the sed applet will use more than 10% of libbb's  
> functionality.

As the main author of the busybox sed applet I'm pretty sure it doesn't  
(unless they changed it since I left), but it's also pretty easy to  
build just sed. (I also implemented the ability to build every busybox  
command as a standalone binary several years ago, it might still be  
there. I haven't looked.)

Rob

Re: REG_STARTEND (regex)

[Rob Landley]

On 01/15/2013 09:16:29 AM, Daniel Cegiełka wrote:
> 'sed -i' is used in many programs (even linux, e2fsprogs, old libcap
> etc.) and there is no chance to avoid it. So I'm looking for an
> alternative to the gnu-sed+gnulib. I found that sed from FreeBSD has
> support for -i and is much smaller than the gnu sed:

I added -i support to busybox sed back around 2005, and the toybox
version should have -i when I get around to writing it. (Still
debugging weird cp corner cases at the moment, then mount/umount
are up next.) It's trivial to implement.

Rob

Re: REG_STARTEND (regex)

[Rich Felker]

On Tue, Jan 15, 2013 at 04:16:29PM +0100, Daniel Cegiełka wrote:
> Thank you for your reply. It's terribly sad that there are so many
> problems with portability. There are a lot of high-quality tools in
> the *BSD, which could be used in Linux. And rather than stick to the
> POSIX people still create a barrier, like REG_STARTEND, 'sed -i',
> bison (instead POSIX yacc), perl in the Makefile(!!!) etc.
> 
> 'sed -i' is used in many programs (even linux, e2fsprogs, old libcap
> etc.) and there is no chance to avoid it. So I'm looking for an
> alternative to the gnu-sed+gnulib. I found that sed from FreeBSD has
> support for -i and is much smaller than the gnu sed:
> 
> http://svnweb.freebsd.org/base/release/9.1.0/usr.bin/sed/
> 
> ls -lh /bin/sed ./sed
> -rwxr-xr-x 1 root root 143K Jun 22  2012 /bin/sed
> -rwxr-xr-x 1 root root  35K Jan 15 14:32 ./sed
> 
> (compiled on linux with glibc)
> 
> Now I want to use it with musl, but sed (and grep) from FreeBSD uses
> REG_STARTEND and I don't really know how to solve this problem.
> 
> 
> http://svnweb.freebsd.org/base/release/9.1.0/usr.bin/sed/process.c?revision=243808&view=markup
> 
> 651 	/* Set anchors */
> 652 	match[0].rm_so = 0;
> 653 	match[0].rm_eo = slen;
> 654 	
> 655 	eval = regexec(defpreg, string,
> 656 	nomatch ? 0 : maxnsub + 1, match, eflags | REG_STARTEND);
> 
> 
> Does anyone have suggestions on how this can be modified to be able to
> use it with musl.

If the start position is 0, which it seems to be here, there's nothing
to be done but removing REG_STARTEND. All it's doing is allowing you
to process data with embedded nul bytes, which is not required by the
standard or useful for any meaningful use of sed. Nobody will notice
the difference with it missing unless they're trying to perform
hideous hacks like patching binary files with sed...

If the start position were not zero, you could compensate by just
adding the start offset to the pointer you pass in, then adjusting all
the match offsets after regexec returns.

Rich

Re: REG_STARTEND (regex)

[Daniel Cegiełka]

2013/1/15 Rich Felker <dalias@aerifal.cx>

> If the start position is 0, which it seems to be here, there's nothing
> to be done but removing REG_STARTEND. All it's doing is allowing you
> to process data with embedded nul bytes, which is not required by the
> standard or useful for any meaningful use of sed. Nobody will notice
> the difference with it missing unless they're trying to perform
> hideous hacks like patching binary files with sed...
>
> If the start position were not zero, you could compensate by just
> adding the start offset to the pointer you pass in, then adjusting all
> the match offsets after regexec returns.
>

thx Rich,
I found a similar solution in a 'file' package:

		else {
			regmatch_t pmatch[1];
#ifndef REG_STARTEND
#define	REG_STARTEND	0
			size_t l = ms->search.s_len - 1;
			char c = ms->search.s[l];
			((char *)(intptr_t)ms->search.s)[l] = '\0';
#else
			pmatch[0].rm_so = 0;
			pmatch[0].rm_eo = ms->search.s_len;
#endif
			rc = regexec(&rx, (const char *)ms->search.s,
			    1, pmatch, REG_STARTEND);
#if REG_STARTEND == 0
			((char *)(intptr_t)ms->search.s)[l] = c;
#endif
			switch (rc) {
			case 0:


https://raw.github.com/glensc/file/master/src/softmagic.c

Best regards,
Daniel

Re: REG_STARTEND (regex)

[Rob Landley]

On 01/15/2013 12:45:13 PM, Rich Felker wrote:
> > Does anyone have suggestions on how this can be modified to be able  
> to
> > use it with musl.
> 
> If the start position is 0, which it seems to be here, there's nothing
> to be done but removing REG_STARTEND. All it's doing is allowing you
> to process data with embedded nul bytes, which is not required by the
> standard or useful for any meaningful use of sed.

Actually people use sed to modify embedded strings in binaries.  
(Strange but true.)

> Nobody will notice
> the difference with it missing unless they're trying to perform
> hideous hacks like patching binary files with sed...

Which people do.

However, mostly this involves embedded nuls in the data being  
processed, not embedded nuls in the pattern space. So it's merely  
creepy rather than outright pathological. And the caller can wrap the  
regex library to do its own strlen stuff and restart right after the  
embedded NUL if there's data left. (Which was on the todo list for  
busybox sed back when Bruce happened, possibly Denys has implemented it  
since.)

Rob

Re: REG_STARTEND (regex)

[Rich Felker]

On Wed, Jan 16, 2013 at 09:42:01AM -0600, Rob Landley wrote:
> On 01/15/2013 12:45:13 PM, Rich Felker wrote:
> >> Does anyone have suggestions on how this can be modified to be
> >able to
> >> use it with musl.
> >
> >If the start position is 0, which it seems to be here, there's nothing
> >to be done but removing REG_STARTEND. All it's doing is allowing you
> >to process data with embedded nul bytes, which is not required by the
> >standard or useful for any meaningful use of sed.
> 
> Actually people use sed to modify embedded strings in binaries.
> (Strange but true.)
> 
> >Nobody will notice
> >the difference with it missing unless they're trying to perform
> >hideous hacks like patching binary files with sed...
> 
> Which people do.
> 
> However, mostly this involves embedded nuls in the data being
> processed, not embedded nuls in the pattern space. So it's merely
> creepy rather than outright pathological. And the caller can wrap
> the regex library to do its own strlen stuff and restart right after
> the embedded NUL if there's data left. (Which was on the todo list
> for busybox sed back when Bruce happened, possibly Denys has
> implemented it since.)

If sed wants to support this without providing its own
embedded-NUL-capable regex library, it should just treat NUL as a kind
of boundary/line-break so that the pattern space never ends up
containing NUL bytes. However, there are still a good many other
portability issues with passing binary files to sed, even if you
ignore the fact that POSIX sed specifically requires a text file as
input, so I think it's rather misguided to cater to these uses anyway.

Rich

Re: REG_STARTEND (regex)

[Justin Cormack]

On Tue, Jan 15, 2013 at 3:16 PM, Daniel Cegiełka
<daniel.cegielka@gmail.com> wrote:
> Thank you for your reply. It's terribly sad that there are so many
> problems with portability. There are a lot of high-quality tools in
> the *BSD, which could be used in Linux. And rather than stick to the
> POSIX people still create a barrier, like REG_STARTEND, 'sed -i',
> bison (instead POSIX yacc), perl in the Makefile(!!!) etc.
>
> 'sed -i' is used in many programs (even linux, e2fsprogs, old libcap
> etc.) and there is no chance to avoid it. So I'm looking for an
> alternative to the gnu-sed+gnulib. I found that sed from FreeBSD has
> support for -i and is much smaller than the gnu sed:
>
> http://svnweb.freebsd.org/base/release/9.1.0/usr.bin/sed/
>
> ls -lh /bin/sed ./sed
> -rwxr-xr-x 1 root root 143K Jun 22  2012 /bin/sed
> -rwxr-xr-x 1 root root  35K Jan 15 14:32 ./sed
>
> (compiled on linux with glibc)
>
> Now I want to use it with musl, but sed (and grep) from FreeBSD uses
> REG_STARTEND and I don't really know how to solve this problem.
>
>
> http://svnweb.freebsd.org/base/release/9.1.0/usr.bin/sed/process.c?revision=243808&view=markup
>
> 651     /* Set anchors */
> 652     match[0].rm_so = 0;
> 653     match[0].rm_eo = slen;
> 654
> 655     eval = regexec(defpreg, string,
> 656     nomatch ? 0 : maxnsub + 1, match, eflags | REG_STARTEND);
>
>
> Does anyone have suggestions on how this can be modified to be able to
> use it with musl.

I know this was a long time ago, but NetBSD now has (in HEAD) FreeBSD
sed modified to not use REG_STARTEND, which does compile on Musl. You
could either use the NetBSD version, or try to get FreeBSD to port the
fixes.

Justin

Re: REG_STARTEND (regex)

[bfdamkoehler]

Hello,

I noticed an issue with localtime() in musl-1.1.2. In my environment TZ 
is set to EST5EDT. There is a test program below that demonstrates this. 
localtime() is returning with isdst == 1 for for a time_t value of 
1394327858 (08-Mar-14 20:17). Daylight savings time starts on 09-Mar-14. 
Note that if you decrement the time_t value in the test program isdst 
remains set.

This time_t value is the st_atime value of a file on my machine, as 
returned by stat64().

Just as further test I moved the file around to an AIX 5.2 machine, HPUX 
11.11, and OpenBSD 5.0 system and a Centos 6.5 linux machine. I used ls 
and tar on them to display the file date and they all came out as 
08-Mar-14 20:17, as does the output from my application if it is linked 
with the gcc libc. When my application is linked with musl it produces a 
time of 08-Mar-14 21:17.

I just wanted to mention that I had noticed this.

Bruce


#include                <stdio.h>
#include                <string.h>
#include                <stdlib.h>
#include                <time.h>

int main()
{
     time_t              bin_time = 1394327858;  /* should be 08-Mar-14 
20:17 but */
                                                 /* localtime returns 
isdst=1 so  */
                                                 /* it is 08-Mar-14 
21:17         */
     struct tm           *tm_ptr;
     char                *cptr;

//#define GO_BACK_N_DAYS_IN_TIME
#ifdef  GO_BACK_N_DAYS_IN_TIME
     bin_time = 1394327858 - ( (24 * 60 * 60) * 60);
#endif

     cptr = getenv("TZ");
     if( cptr == NULL )
         printf("the TZ environment variable is not defined\n");
     else
         printf("the TZ environment variable is set to %s\n", cptr);

     tm_ptr = localtime(&bin_time);
     printf("The local time is ...\n");
     printf("\t\ttm_sec ........... %d\n", tm_ptr->tm_sec);
     printf("\t\ttm_min ........... %d\n", tm_ptr->tm_min);
     printf("\t\ttm_hour .......... %d\n", tm_ptr->tm_hour);
     printf("\t\ttm_mday .......... %d\n", tm_ptr->tm_mday);
     printf("\t\ttm_mon ........... %d\n", tm_ptr->tm_mon);
     printf("\t\ttm_year .......... %d\n", tm_ptr->tm_year);
     printf("\t\ttm_wday .......... %d\n", tm_ptr->tm_wday);
     printf("\t\ttm_yday .......... %d\n", tm_ptr->tm_yday);
     printf("\t\ttm_is_dst......... %d\n", tm_ptr->tm_isdst);
     printf("\n\n");

     printf("tm_hour should be 20 and tm_is_dst should be 0 -- DST 
starts on 09-Mar-14.\n");
     printf("\n\n");

}

Re: REG_STARTEND (regex)

[Rich Felker]

On Wed, Jun 11, 2014 at 09:00:00PM -0400, bfdamkoehler wrote:
> 
> Hello,
> 
> I noticed an issue with localtime() in musl-1.1.2. In my environment
> TZ is set to EST5EDT. There is a test program below that
> demonstrates this. localtime() is returning with isdst == 1 for for
> a time_t value of 1394327858 (08-Mar-14 20:17). Daylight savings
> time starts on 09-Mar-14. Note that if you decrement the time_t
> value in the test program isdst remains set.
> 
> This time_t value is the st_atime value of a file on my machine, as
> returned by stat64().
> 
> Just as further test I moved the file around to an AIX 5.2 machine,
> HPUX 11.11, and OpenBSD 5.0 system and a Centos 6.5 linux machine. I
> used ls and tar on them to display the file date and they all came
> out as 08-Mar-14 20:17, as does the output from my application if it
> is linked with the gcc libc. When my application is linked with musl
> it produces a time of 08-Mar-14 21:17.
> 
> I just wanted to mention that I had noticed this.

I think the issue is just that you don't have a complete POSIX TZ rule
for EST5EDT written. With TZ=EST5EDT,M3.2.0/2,M11.1.0/2 (corresponding
to the current rules in effect for this timezone) I get the expected
output. Without specifying the full rule like this, I don't think you
can expect the right behavior since it changes every few years.
However, I think musl is also wrong not to have some sort of
meaningful default. I'll look into it more.

BTW if you intended to use the modern zoneinfo file rather than the
POSIX TZ string for EST5EDT, try TZ=:EST5EDT or TZ=US/Easter. glibc
may use the zoneinfo file before treating the string as a POSIX TZ
string but musl doesn't since doing so is non-conforming; the leading
':' can force it to treat it as a file though.

Rich

Re: REG_STARTEND (regex)

[bfdamkoehler]

On 06/11/2014 09:40 PM, Rich Felker wrote:
> I think the issue is just that you don't have a complete POSIX TZ rule
> for EST5EDT written. With TZ=EST5EDT,M3.2.0/2,M11.1.0/2 (corresponding
> to the current rules in effect for this timezone) I get the expected
> output. Without specifying the full rule like this, I don't think you
> can expect the right behavior since it changes every few years.
> However, I think musl is also wrong not to have some sort of
> meaningful default. I'll look into it more.
I get the correct results using your TZ environment variable.

Actually, when I first tested with musl I didn't have a TZ environment 
variable and the time was off by 4 hours. Setting it seemed to fix the 
issue at first.

My linux machine has the timezone was set by the redhat/centos 
system-config-date to New York (I changed it to Detroit since then) and 
the "system uses UTC is not checked". This is a binary file but it ends 
in EST5EDT,M3.2.0,M11.1.0.

Should musl be using /etc/localtime if TZ is not defined?

Re: REG_STARTEND (regex)

[Rich Felker]

On Thu, Jun 12, 2014 at 09:15:26PM -0400, bfdamkoehler wrote:
> On 06/11/2014 09:40 PM, Rich Felker wrote:
> >I think the issue is just that you don't have a complete POSIX TZ rule
> >for EST5EDT written. With TZ=EST5EDT,M3.2.0/2,M11.1.0/2 (corresponding
> >to the current rules in effect for this timezone) I get the expected
> >output. Without specifying the full rule like this, I don't think you
> >can expect the right behavior since it changes every few years.
> >However, I think musl is also wrong not to have some sort of
> >meaningful default. I'll look into it more.
> I get the correct results using your TZ environment variable.
> 
> Actually, when I first tested with musl I didn't have a TZ
> environment variable and the time was off by 4 hours. Setting it
> seemed to fix the issue at first.
> 
> My linux machine has the timezone was set by the redhat/centos
> system-config-date to New York (I changed it to Detroit since then)
> and the "system uses UTC is not checked". This is a binary file but
> it ends in EST5EDT,M3.2.0,M11.1.0.
> 
> Should musl be using /etc/localtime if TZ is not defined?

See commit f616294914e7c289791d856dca636bbccad5fef7.

Rich