Weekly reports - B

Weekly reports - B

[Luka Marčetić]

Anyway, here's something... *hangs head*
https://github.com/paxcoder/cluts

Re: Weekly reports - B

[Rich Felker]

On Thu, Jun 09, 2011 at 10:20:45PM +0200, Luka Marčetić wrote:
> Anyway, here's something... *hangs head*
> https://github.com/paxcoder/cluts

Is there a reason you're installing and uninstalling the SIGABRT
handler on each free? I suspect that's taking a LOT of time, slowing
down free by a factor of ~3x for large mmapped chunks and ~200x for
small chunks.

By the way, please don't feel like you need to do everything on your
own writing cluts. You're welcome to discuss ideas, troubles you run
into, get advice and code review, etc. both on the mailing list here
and on irc.

Best wishes,

Rich

Re: Weekly reports - B

[Solar Designer]

Luka, Rich -

On Thu, Jun 09, 2011 at 10:20:45PM +0200, Luka Mar??eti?? wrote:
> Anyway, here's something... *hangs head*
> https://github.com/paxcoder/cluts

Thanks for posting this.  I took a look.  This is good for the start,
but we obviously need a lot more. ;-)

Sorry to remind you, but we need Luka's code placed under an Open Source
license - and not only when cluts is "finished".  Each week's update
must be properly licensed.  Can one or both of you please propose a
license you're comfortable with?

Some assorted comments on the code, in arbitrary order:

For jumping out of a signal handler, you need to use sigjmp_buf,
sigsetjmp(), and siglongjmp().  Even so, some failed libc functions
might leave stdio (or something else) in an inconsistent state.  This is
probably irrelevant to simple string functions testing, but it will be
relevant to some other tests.  Thus, since we don't expect SIGSEGVs to
be frequent, maybe it'd be better to switch to forking child processes
(which must print something specific to fd 1 to indicate success)?
Or we can use both approaches - in different cases, as appropriate.

When you declare identifiers at the global scope in a file, but don't
need them exported to other source files, please make them "static" to
prevent inadvertent use from another source file.

What do you mean by "#define _XOPEN_SOURCE 9001"?  I think the highest
value currently defined is 700, and going too high may actually prevent
this from working (e.g., on Solaris).

Please avoid assignments to errno.  Use your own variable instead.

Overall, I think the code could be made prettier.  I'll post an idea
(which you don't have to use, but you may) in another message.

Luka - when I say that something could be written better, etc., please
don't be discouraged.  On the contrary, this indicates that you're doing
something interesting, comment-worthy. :-)  I am merely trying to
provide constructive criticism and help the project in this way.

Thanks again,

Alexander

Re: Weekly reports - B

[Rich Felker]

On Mon, Jun 13, 2011 at 06:11:30AM +0400, Solar Designer wrote:
> Luka, Rich -
> 
> On Thu, Jun 09, 2011 at 10:20:45PM +0200, Luka Mar??eti?? wrote:
> > Anyway, here's something... *hangs head*
> > https://github.com/paxcoder/cluts
> 
> Thanks for posting this.  I took a look.  This is good for the start,
> but we obviously need a lot more. ;-)

Yes. :)

> Sorry to remind you, but we need Luka's code placed under an Open Source
> license - and not only when cluts is "finished".  Each week's update
> must be properly licensed.  Can one or both of you please propose a
> license you're comfortable with?

Let's make it (new) BSD. Is that okay?

> Some assorted comments on the code, in arbitrary order:
> 
> For jumping out of a signal handler, you need to use sigjmp_buf,
> sigsetjmp(), and siglongjmp().

This only matters if you want the signal mask to be restored, which we
DO want, but another way to achieve the same thing would be to install
the signal handler with SA_NOMASK so the SIGSEGV never gets masked to
begin with (another SIGSEGV should not happen inside the signal
handler, and if it did while it was blocked, we'd be screwed anyway).

BTW another way to restore the signal mask, especially if you want it
to be restored to the mask at the time the signal was generated rather
than at the time the jump buffer was created, is to use the SA_SIGINFO
signal handler form and read the saved sigset_t from the ucontext_t
argument and restore it yourself with sigprocmask. :-)

> Even so, some failed libc functions
> might leave stdio (or something else) in an inconsistent state.  This is
> probably irrelevant to simple string functions testing, but it will be
> relevant to some other tests.  Thus, since we don't expect SIGSEGVs to
> be frequent, maybe it'd be better to switch to forking child processes
> (which must print something specific to fd 1 to indicate success)?
> Or we can use both approaches - in different cases, as appropriate.

In the case of testing string functions, the test framework setup a
very narrow class of "likely causes" for the SIGSEGV, and unless the
functions are hopelessly broken, we can assume any SIGSEGV was caused
by the condition that was being tested for. Therefore, in this case I
don't think we have to worry about corrupt state and such. Note that
POSIX does not require string functions to be async-signal-safe, for
some odd reason, but as far as I know all real-world implementations
including glibc guarantee that they are (I found a discussion of glibc
strstr optimization where use of malloc was rejected because it would
violate their requirement that they want it to be async-signal-safe).
Thus they should not have any internal state that could get corrupted.

> When you declare identifiers at the global scope in a file, but don't
> need them exported to other source files, please make them "static" to
> prevent inadvertent use from another source file.

Agreed.

> What do you mean by "#define _XOPEN_SOURCE 9001"?  I think the highest
> value currently defined is 700, and going too high may actually prevent
> this from working (e.g., on Solaris).

I noticed this too. Also you're defining it after including headers,
which has no effect but invoking UB. To use feature test macros they
must be defined before any system headers are included.

> Please avoid assignments to errno.  Use your own variable instead.

Is this just a stylistic preference, or do you have a reason it could
be problematic?

Rich

Re: Weekly reports - B

[Solar Designer]

On Sun, Jun 12, 2011 at 10:22:21PM -0400, Rich Felker wrote:
> On Mon, Jun 13, 2011 at 06:11:30AM +0400, Solar Designer wrote:
> > Sorry to remind you, but we need Luka's code placed under an Open Source
> > license - and not only when cluts is "finished".  Each week's update
> > must be properly licensed.  Can one or both of you please propose a
> > license you're comfortable with?
> 
> Let's make it (new) BSD. Is that okay?

Sounds fine.  Thanks.

(I had mentioned my very slightly different preference before.  I won't
repeat that.)

> > Some assorted comments on the code, in arbitrary order:
> > 
> > For jumping out of a signal handler, you need to use sigjmp_buf,
> > sigsetjmp(), and siglongjmp().
> 
> This only matters if you want the signal mask to be restored, which we
> DO want,

Right, that's what I meant.

> but another way to achieve the same thing would be to install
> the signal handler with SA_NOMASK so the SIGSEGV never gets masked to
> begin with (another SIGSEGV should not happen inside the signal
> handler, and if it did while it was blocked, we'd be screwed anyway).
> 
> BTW another way to restore the signal mask, especially if you want it
> to be restored to the mask at the time the signal was generated rather
> than at the time the jump buffer was created, is to use the SA_SIGINFO
> signal handler form and read the saved sigset_t from the ucontext_t
> argument and restore it yourself with sigprocmask. :-)

Thank you for mentioning these.

For cluts, I think it'd be best not to go for them, though - they might
make cluts unnecessarily less portable.

> > Even so, some failed libc functions
> > might leave stdio (or something else) in an inconsistent state.  This is
> > probably irrelevant to simple string functions testing, but it will be
> > relevant to some other tests.  Thus, since we don't expect SIGSEGVs to
> > be frequent, maybe it'd be better to switch to forking child processes
> > (which must print something specific to fd 1 to indicate success)?
> > Or we can use both approaches - in different cases, as appropriate.
> 
> In the case of testing string functions, the test framework setup a
> very narrow class of "likely causes" for the SIGSEGV, and unless the
> functions are hopelessly broken, we can assume any SIGSEGV was caused
> by the condition that was being tested for. Therefore, in this case I
> don't think we have to worry about corrupt state and such.

Right.  I primarily wanted to bring the issue up early on, because Luka
will need to arrive at an approach to use for cluts tests in general.

> Note that
> POSIX does not require string functions to be async-signal-safe, for
> some odd reason, but as far as I know all real-world implementations
> including glibc guarantee that they are (I found a discussion of glibc
> strstr optimization where use of malloc was rejected because it would
> violate their requirement that they want it to be async-signal-safe).
> Thus they should not have any internal state that could get corrupted.

That's curious.  Thanks for sharing.

> > What do you mean by "#define _XOPEN_SOURCE 9001"?  I think the highest
> > value currently defined is 700, and going too high may actually prevent
> > this from working (e.g., on Solaris).
> 
> I noticed this too. Also you're defining it after including headers,
> which has no effect but invoking UB. To use feature test macros they
> must be defined before any system headers are included.

Sure.  I overlooked that detail in Luka's source.

> > Please avoid assignments to errno.  Use your own variable instead.
> 
> Is this just a stylistic preference, or do you have a reason it could
> be problematic?

Mostly a stylistic preference.  errno is defined to have a specific kind
of values assigned to it, by libc.  Reusing a variable for something
different than its original purpose makes the source code more difficult
to understand (even if very slightly).

As to actual potential issues:

IIRC, some ancient versions of glibc didn't allow programs to assign to
errno at all, because it was declared as a macro (not a variable).  That
was broken because there are in fact some cases when you need to zero
out errno before making certain libc calls to be able to distinguish
their different errors.  For example, with strtol().  Also, there are
cases when you need to save/restore errno (such as in a signal handler).
(Hmm, maybe I recall only part of the story, and there was something
enabling those things to work...)

Is it guaranteed that errno is preserved across libc calls that complete
without error?  Maybe not.  I don't really know, and I'd prefer not to
depend on that.

Generally, I think it is appropriate to limit uses of errno to checking
it immediately after a failed libc call, to zeroing it right before
certain libc calls, and to saving/restoring its value.  Oh, there's one
more: in portability functions, it is OK to set errno to specific -EXXX
values as appropriate to implement whatever function is being replaced.

Just an opinion.

Alexander

Re: Weekly reports - B

[Rich Felker]

On Mon, Jun 13, 2011 at 06:56:55AM +0400, Solar Designer wrote:
> > but another way to achieve the same thing would be to install
> > the signal handler with SA_NOMASK so the SIGSEGV never gets masked to
> > [...]
> 
> Thank you for mentioning these.
> 
> For cluts, I think it'd be best not to go for them, though - they might
> make cluts unnecessarily less portable.

That's a good point. I seem to recall some systems (including older
Linux) having broken SA_NOMASK.

> > > Please avoid assignments to errno.  Use your own variable instead.
> > 
> > Is this just a stylistic preference, or do you have a reason it could
> > be problematic?
> 
> Mostly a stylistic preference.  errno is defined to have a specific kind
> of values assigned to it, by libc.  Reusing a variable for something
> different than its original purpose makes the source code more difficult
> to understand (even if very slightly).
> 
> As to actual potential issues:
> 
> IIRC, some ancient versions of glibc didn't allow programs to assign to
> errno at all, because it was declared as a macro (not a variable).  That

This sounds like an urban legend. errno is a macro and has been for a
long time (ever since threads) on most systems. It's required by the
standard to be an lvalue macro.

> Is it guaranteed that errno is preserved across libc calls that complete
> without error?  Maybe not.  I don't really know, and I'd prefer not to
> depend on that.

Unless it's documented that a particular function can't, libc
functions can clobber errno all they like, whether or not they return
failure. The only thing they can't do is set it to 0, unless they put
some other nonzero (hopefully meaningful) value in it before
returning. Note that even strerror and perror can clobber errno if
they encounter an internal error, so if you want to portably print an
error message before acting on the error, you really need to save the
value of errno right away.

This all makes using errno a little bit messy, but if libc functions
were required not to change errno except when reporting an error,
pretty much every libc function that uses other libc functions would
be full of useless bloat and slowdowns saving and restoring errno
values...

Rich

Re: Weekly reports - B

[Solar Designer]

On Mon, Jun 13, 2011 at 12:54:18AM -0400, Rich Felker wrote:
> On Mon, Jun 13, 2011 at 06:56:55AM +0400, Solar Designer wrote:
> > IIRC, some ancient versions of glibc didn't allow programs to assign to
> > errno at all, because it was declared as a macro (not a variable).  That
> 
> This sounds like an urban legend. errno is a macro and has been for a
> long time (ever since threads) on most systems. It's required by the
> standard to be an lvalue macro.

Oh, of course I did not recall correctly.  Here's what I think this was
about: old programs such as qmail (not maintained upstream since 1998)
used "extern int errno;" instead of including errno.h, and indeed this
failed when errno became a macro (for threads, as you correctly remind
me).  So this was an entirely different issue.

> > Is it guaranteed that errno is preserved across libc calls that complete
> > without error?  Maybe not.  I don't really know, and I'd prefer not to
> > depend on that.
> 
> Unless it's documented that a particular function can't, libc
> functions can clobber errno all they like, whether or not they return
> failure. The only thing they can't do is set it to 0, unless they put
> some other nonzero (hopefully meaningful) value in it before
> returning.

I went to:

http://pubs.opengroup.org/onlinepubs/009695399/functions/errno.html

and it does say "No function in this volume of IEEE Std 1003.1-2001
shall set errno to 0. The setting of errno after a successful call to a
function is unspecified unless the description of that function
specifies that errno shall not be modified."  Which not surprisingly
matches what you wrote above.

I was a bit puzzled why they decided to outlaw setting of errno to 0 by
library functions, although this does make some sense to me (easy to
achieve and preserves at least some recent error code for poorly written
old programs).

> This all makes using errno a little bit messy, but if libc functions
> were required not to change errno except when reporting an error,
> pretty much every libc function that uses other libc functions would
> be full of useless bloat and slowdowns saving and restoring errno
> values...

Good point.  I guess they'd resort to calling other than exported
versions of the functions, though.  But this could mean extra function
call overhead for the exported versions...

Alexander

errno (was: Weekly reports - B)

[Solar Designer]

Rich,

On Mon, Jun 13, 2011 at 12:54:18AM -0400, Rich Felker wrote:
> ... errno is a macro and has been for a
> long time (ever since threads) on most systems. It's required by the
> standard to be an lvalue macro.

Any idea why glibc has __set_errno() internally instead of assigning to
its errno directly, then?  The implementation for __set_errno() does a
direct assignment anyway.  What did the glibc developers need
__set_errno() for if errno is required to be an lvalue, and do they
still need __set_errno() or is it legacy?

Meanwhile, I continue to use __set_errno() in my glibc patches, at least
for consistency with upstream's code.

Thanks,

Alexander

Re: errno (was: Weekly reports - B)

[Szabolcs Nagy]

* Solar Designer <solar@openwall.com> [2011-07-06 15:35:08 +0400]:
> On Mon, Jun 13, 2011 at 12:54:18AM -0400, Rich Felker wrote:
> > ... errno is a macro and has been for a
> > long time (ever since threads) on most systems. It's required by the
> > standard to be an lvalue macro.
> 
> Any idea why glibc has __set_errno() internally instead of assigning to
> its errno directly, then?  The implementation for __set_errno() does a
> direct assignment anyway.  What did the glibc developers need

it seems there was a different definition under sysdeps until

2002-07-19  Ulrich Drepper  <drepper@redhat.com>
    * sysdeps/generic/bits/errno.h: Remove __set_errno definition.
    * ...

and then

2002-11-25  Jakub Jelinek  <jakub@redhat.com>
    * include/errno.h (__set_errno): Define as errno = val
    unconditionally.


in older glibc eg sysdeps/unix/sysv/linux/bits/errno.h had code like

#ifdef _ERRNO_H

# undef EDOM
# undef EILSEQ
# undef ERANGE
# include <linux/errno.h>

/* Linux has no ENOTSUP error code.  */
# define ENOTSUP EOPNOTSUPP

/* Linux also has no ECANCELED error code.  Since it is not used here
   we define it to an invalid value.  */
# define ECANCELED      125
 
# ifndef __ASSEMBLER__
/* We now need a declaration of the `errno' variable.  */
extern int errno;
 
/* Function to get address of global `errno' variable.  */
extern int *__errno_location __P ((void)) __attribute__ ((__const__));

#  if defined _LIBC
/* We wouldn't need a special macro anymore but it is history.  */
#   define __set_errno(val) (*__errno_location ()) = (val)
#  endif /* _LIBC */

#  if !defined _LIBC || defined _LIBC_REENTRANT
/* When using threads, errno is a per-thread value.  */
#   define errno (*__errno_location ())
#  endif
# endif /* !__ASSEMBLER__ */
#endif /* _ERRNO_H */

Re: errno

[Solar Designer]

On Wed, Jul 06, 2011 at 02:57:38PM +0200, Szabolcs Nagy wrote:
> in older glibc eg sysdeps/unix/sysv/linux/bits/errno.h had code like
...
> /* We wouldn't need a special macro anymore but it is history.  */

It looks like we'd need to look at even older versions to find out why
the macro was ever needed.

Thanks!

Alexander

Re: errno (was: Weekly reports - B)

[Rich Felker]

On Wed, Jul 06, 2011 at 03:35:08PM +0400, Solar Designer wrote:
> Rich,
> 
> On Mon, Jun 13, 2011 at 12:54:18AM -0400, Rich Felker wrote:
> > ... errno is a macro and has been for a
> > long time (ever since threads) on most systems. It's required by the
> > standard to be an lvalue macro.
> 
> Any idea why glibc has __set_errno() internally instead of assigning to
> its errno directly, then?  The implementation for __set_errno() does a
> direct assignment anyway.  What did the glibc developers need
> __set_errno() for if errno is required to be an lvalue, and do they
> still need __set_errno() or is it legacy?

While this doesn't necessarily answer the historical question of
whether or why it may have been needed, I think part of the reason for
__set_errno (especiall in uclibc which uses a similar approach) might
be keeping down code size or improving performance. Simple assignment
to errno requires saving the value to be stored to errno in a
non-call-clobbered register or on the stack, making a call to
__errno_location, then reading back the saved error value and storing
it at the address returned by __errno_location. On the other hand,
with __set_errno, the process is just a single function call and the
error value does not need to be saved for use after the call returns.

Further, with NPTL's TLS model, it's possible to make __set_errno more
efficient than using __errno_location would be. The latter is
basically:

mov %gs:0,%eax
add $ERRNO_OFFSET,%eax
ret

while __set_errno can be purely:

mov 4(%esp),%eax
mov %eax,%gs:ERRNO_OFFSET
ret

And if you declare it regparm, you could even throw away the first
instruction... Or you could just make it an inline function and get
even bigger benefits (no actual call, on register spills, etc.)

Personally, in musl I've avoided doing things like this in favor of
simplicity. Presumably errno getting set should be a fairly uncommon
occurrance anyway, so speed isn't all that important, and I like code
that reads as plain C that could just as well be part of any
implementation of the standard library rather than being full of
implementation-specific tricks...

Rich

Weekly reports - X

[Luka Marčetić]

Hi there.
I'm sorry about falling behind so much. Good news though, summer brings 
me a free window that I'll be able to dedicate to cluts. This next week 
is the last one that I'll be busy with school until September. Next 
week, I'll finish format.c (and perhaps rename it to numerical.c or 
alike) and fix alloc.c(arrays instead of lists+implementing your 
suggestions-keep making them btw. i appreciate them). Things will 
finally pick up afterward.
About the license: I've been quiet because I like copyleft. My preferred 
license is GPLv3+. But Solar I think said nobody is going to make their 
own proprietary version of the library, so why not just make the license 
permissive and let them use it however. Perhaps we could compromise and 
choose LGPL, the musl's license. I think the reasoning behind that 
particular license is clear.

SUMMARY: 1) Serious work will start a week after this one. 2) How about 
LGPL as a compromise?
Thanks.
--Luka M.

Re: Weekly reports - X

[rich felker]

[-- Attachment #1: Type: text/plain, Size: 1926 bytes --]

Luka,
I would be happy enough with LGPL, but I believe Openwall's commitment to
GSoC included terms that all the code developed under their projects would
be under BSD license (or equally/more permissive). In any case I don't think
the license matters at all for test case code. Anyone who wanted to improve
it without releasing their improvements would almost surely be using it for
internal use only (testing their implementation), not as a deployed product,
so even if it were GPL they would not be obligated to release anything.
Conversely, since it must be in source form to be useful for testing an
implementation, even under BSD license, nobody could make a useful
closed-source test product out of cluts - the source is essential to using
it! Thus I think we should just put aside this bikeshed and BSD it.

Rich




On Sun, Jun 26, 2011 at 5:05 PM, Luka Marčetić <paxcoder@gmail.com> wrote:

> Hi there.
> I'm sorry about falling behind so much. Good news though, summer brings me
> a free window that I'll be able to dedicate to cluts. This next week is the
> last one that I'll be busy with school until September. Next week, I'll
> finish format.c (and perhaps rename it to numerical.c or alike) and fix
> alloc.c(arrays instead of lists+implementing your suggestions-keep making
> them btw. i appreciate them). Things will finally pick up afterward.
> About the license: I've been quiet because I like copyleft. My preferred
> license is GPLv3+. But Solar I think said nobody is going to make their own
> proprietary version of the library, so why not just make the license
> permissive and let them use it however. Perhaps we could compromise and
> choose LGPL, the musl's license. I think the reasoning behind that
> particular license is clear.
>
> SUMMARY: 1) Serious work will start a week after this one. 2) How about
> LGPL as a compromise?
> Thanks.
> --Luka M.
>

[-- Attachment #2: Type: text/html, Size: 2238 bytes --]

Re: Weekly reports - X

[Solar Designer]

Luka, Rich -

On Sun, Jun 26, 2011 at 05:13:42PM -0400, rich felker wrote:
> I would be happy enough with LGPL, but I believe Openwall's commitment to
> GSoC included terms that all the code developed under their projects would
> be under BSD license (or equally/more permissive).

This was mentioned, but it was not a commitment.  Google is OK with any
Open Source license.

The ideas page for Openwall says:

"With few exceptions (such as for changes to existing Linux kernel code,
which is under GPLv2 anyway), we require any contributed code to be made
available under a cut-down BSD license."

"By applying to work on one of the ideas with us, you signify your
acceptance of these terms and your intent to license your code
contributions accordingly."

So by applying to us under GSoC, Luka agreed to these terms.  Yet I am
willing to renegotiate to LGPL in this case, even though this makes me
somewhat less willing to contribute to the project.

(I realize that it may be the other way around for some other
prospective contributors, though.  Some people are more willing to
contribute when they know that copyleft prevents their code from being
used in proprietary products.  In my case, I am happier to contribute
when I know there won't be an artificial barrier to reuse of my code,
especially to reuse by me.  With copyleft, when I contribute to a source
file that is not solely written by me, I then have difficulty reusing my
own code contributions in differently-licensed projects.)

Anyhow, the important thing now is for Luka to start placing his cluts
code under any Open Source license.

> In any case I don't think
> the license matters at all for test case code. Anyone who wanted to improve
> it without releasing their improvements would almost surely be using it for
> internal use only (testing their implementation), not as a deployed product,
> so even if it were GPL they would not be obligated to release anything.

Right.  But there might be reusable components - e.g., the framework may
be reused for tests to be bundled with another library (not a libc).

> Conversely, since it must be in source form to be useful for testing an
> implementation, even under BSD license, nobody could make a useful
> closed-source test product out of cluts - the source is essential to using
> it! Thus I think we should just put aside this bikeshed and BSD it.

Right.  This sounds good to me.

> On Sun, Jun 26, 2011 at 5:05 PM, Luka Mar??eti?? <paxcoder@gmail.com> wrote:
> > I'm sorry about falling behind so much. Good news though, summer brings me
> > a free window that I'll be able to dedicate to cluts. This next week is the
> > last one that I'll be busy with school until September. Next week, I'll
> > finish format.c (and perhaps rename it to numerical.c or alike) and fix
> > alloc.c(arrays instead of lists+implementing your suggestions-keep making
> > them btw. i appreciate them). Things will finally pick up afterward.

Thank you for describing your nearest plans for work on cluts.

When do you intend to start putting the tests into a framework?  I think
you should have started with that by now, but we were hoping you'd have
more tests by now too...

> > About the license: I've been quiet because I like copyleft. My preferred

You should have stated so rather than remain quiet.

> > license is GPLv3+. But Solar I think said nobody is going to make their own
> > proprietary version of the library, so why not just make the license
> > permissive and let them use it however. Perhaps we could compromise and
> > choose LGPL, the musl's license. I think the reasoning behind that
> > particular license is clear.
> >
> > SUMMARY: 1) Serious work will start a week after this one.

That delay is really unfortunate, but we have to accept it I guess.

> > 2) How about LGPL as a compromise?

Please see above.

Please commit your files with some Open Source license statements on
them as soon as you reasonably can - perhaps tomorrow?

If you choose cut-down BSD, it'd look like:

/*
 * Copyright (c) 2011 Your Name <email addr>
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted.
 *
 * There's ABSOLUTELY NO WARRANTY, express or implied.
 */

or you may use LGPL if this makes you more comfortable and thus results
in more code from you. ;-)

Thanks,

Alexander

Re: Weekly reports - X

[Luka Marčetić]

On 06/28/2011 12:18 AM, Solar Designer wrote:
>
> Please see above.
>
> Please commit your files with some Open Source license statements on
> them as soon as you reasonably can - perhaps tomorrow?
>
> If you choose cut-down BSD, it'd look like:
>
> /*
>   * Copyright (c) 2011 Your Name<email addr>
>   *
>   * Redistribution and use in source and binary forms, with or without
>   * modification, are permitted.
>   *
>   * There's ABSOLUTELY NO WARRANTY, express or implied.
>   */
>
> or you may use LGPL if this makes you more comfortable and thus results
> in more code from you. ;-)
>
> Thanks,
>
> Alexander
>
Sorry for not responding, here I go now:
I did push an Apache license to the repo (patent caluses etc. though 
really I'd like LGPL) before I saw this. But now that I see Openwall 
project requires a BSD license, I'll remove it. I guess I'll just add 
the above header to all the source files by Thursday. As I've mentioned 
to Alexander, I'm finishing up numeric.c today, and then I'll pick 
another task, and start writing a framework in parallel.
In light of the discussion with Alex, I may also switch to daily reports 
this week. In any case, you'll be informed.
-Luka

Re: Weekly reports - X

[Rich Felker]

On Mon, Jul 04, 2011 at 09:30:47PM +0200, Luka Marčetić wrote:
> mentioned to Alexander, I'm finishing up numeric.c today, and then
> I'll pick another task, and start writing a framework in parallel.
> In light of the discussion with Alex, I may also switch to daily
> reports this week. In any case, you'll be informed.

Daily reports would be great.

Rich

specification of cluts tests - code or/and data? (was: Weekly reports - B)

[Solar Designer]

Luka, Rich -

On Mon, Jun 13, 2011 at 06:11:30AM +0400, Solar Designer wrote:
> Overall, I think the code could be made prettier.  I'll post an idea
> (which you don't have to use, but you may) in another message.

Here's what I meant:

Rather than write a piece of code for testing every property of every
function, we could consider implementing interpreters or wrapper
functions for common tests, or tables (arrays of structs) listing similar
tests.  A problem here is that call to a string function via a function
pointer might not invoke the same implementation that direct use would
(there could be a macro or a C compiler builtin).  On the other hand,
this also means that whatever approach to program structure we choose,
we could want to test both kinds of uses of string functions (direct and
via function pointer), to test both implementations (which might be
present).

This is not directly relevant, but to illustrate the use of interpreter
or data structure approach to a task where most people tend to write
lots of code instead, see:

http://openwall.info/wiki/people/solar/software/public-domain-source-code/intel-80186-disassembler

This is a complete i80186 disassembler in only 164 bytes of code, plus
some 2.5 KB of data (17 KB source).  Other disassemblers I saw typically
process the different instruction types, addressing modes, etc. in code,
and are much larger (in terms of code+data, as well as their source code).

Maybe this will give you some inspiration for coming up with suitable
data structures to define some classes of tests.  You do not have to
take it to the same "extreme" level - very generic code, data structures
that are tricky to specify in C.  You'll need to find a balance that
works well for cluts.

And you do not have to use an approach like this at all.  You may
continue as you have started.  I just thought I'd mention the option.

Maybe this helps.

Alexander

Re: specification of cluts tests - code or/and data?

[Solar Designer]

[-- Attachment #1: Type: text/plain, Size: 1856 bytes --]

Luka, Rich -

On Mon, Jun 13, 2011 at 06:22:31AM +0400, Solar Designer wrote:
> Rather than write a piece of code for testing every property of every
> function, we could consider implementing interpreters or wrapper
> functions for common tests, or tables (arrays of structs) listing similar
> tests.  A problem here is that call to a string function via a function
> pointer might not invoke the same implementation that direct use would
> (there could be a macro or a C compiler builtin).  On the other hand,
> this also means that whatever approach to program structure we choose,
> we could want to test both kinds of uses of string functions (direct and
> via function pointer), to test both implementations (which might be
> present).

I wrote some code to illustrate this.  As written, it tests only some
trivial properties of a handful of string functions, but it is
extensible.  Please see attached.

Functions to test are specified like this:

static void *i_memcpy(void *dst, const void *src, size_t n)
{ return memcpy(dst, src, n); /* might use inlined code */ }

static fspec funcs[] = {
	{memcpy, {F_PTR | F_DST, F_DST, F_SRC, F_N}},
	{i_memcpy, {F_PTR | F_DST, F_DST, F_SRC, F_N}},
	{strcpy, {F_PTR | F_DST | F_NUL, F_DST, F_SRC}},
	{strncpy, {F_PTR | F_DST | F_PAD, F_DST, F_SRC, F_N}},
	{strcat, {F_PTR | F_DST | F_NUL, F_DST | F_SRC, F_SRC}},
	{strncat, {F_PTR | F_DST | F_NUL, F_DST | F_SRC, F_SRC, F_N}},
	{strchr, {F_PTR | F_IN_A1 | F_NUL, F_SRC, F_C}},
	{strstr, {F_PTR | F_IN_A1 | F_NUL, F_SRC, F_SRC}},
	{NULL}
};

As written, arg_next() tries to test all values in a range, but it will
need to be adjusted to skip ranges of string lengths for long strings.

As you can see, deeply nested loops seen in Luka's code are avoided
here.  Even with 8-char tabs (my preference), everything comfortably
fits in under 80 chars.

Alexander

[-- Attachment #2: str.c --]
[-- Type: text/plain, Size: 3749 bytes --]

/*
 * Copyright (c) 2011 Solar Designer <solar at openwall.com>
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted.
 *
 * There's ABSOLUTELY NO WARRANTY, express or implied.
 */

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

#define STR_SIZE			100
#define MIN_C				'a'
#define MAX_C				'z'

#define F_DST				0x00000001
#define F_SRC				0x00000002
#define F_PTR				0x00000004
#define F_IS_PTR			(F_DST | F_SRC | F_PTR)
#define F_N				0x00000008
#define F_C				0x00000010
#define F_NUL				0x00000100
#define F_PAD				0x00000200
#define F_IN_A1				0x00000400

typedef struct {
	void *f;
	unsigned int a[4]; /* a0 = f(a1, a2, a3) */
} fspec;

static void *i_memcpy(void *dst, const void *src, size_t n)
{ return memcpy(dst, src, n); /* might use inlined code */ }

static fspec funcs[] = {
	{memcpy, {F_PTR | F_DST, F_DST, F_SRC, F_N}},
	{i_memcpy, {F_PTR | F_DST, F_DST, F_SRC, F_N}},
	{strcpy, {F_PTR | F_DST | F_NUL, F_DST, F_SRC}},
	{strncpy, {F_PTR | F_DST | F_PAD, F_DST, F_SRC, F_N}},
	{strcat, {F_PTR | F_DST | F_NUL, F_DST | F_SRC, F_SRC}},
	{strncat, {F_PTR | F_DST | F_NUL, F_DST | F_SRC, F_SRC, F_N}},
	{strchr, {F_PTR | F_IN_A1 | F_NUL, F_SRC, F_C}},
	{strstr, {F_PTR | F_IN_A1 | F_NUL, F_SRC, F_SRC}},
	{NULL}
};

typedef struct {
	enum {A_DST, A_SRC, A_N, A_C} t;
	union {
		struct {
			char *s;
			size_t len;
		} s;
		size_t n;
		int c;
	} v;
} arg;

static void arg_reset(arg *a)
{
	switch (a->t) {
	case A_DST:
		break;
	case A_SRC:
		a->v.s.s[0] = '\0';
		a->v.s.len = 0;
		break;
	case A_N:
		a->v.n = 0;
		break;
	case A_C:
		a->v.c = MIN_C;
		break;
	default:
		abort();
	}
}

static int arg_next(arg *a)
{
	switch (a->t) {
	case A_DST:
		return 1;
	case A_SRC:
		a->v.s.s[a->v.s.len] =
		    MIN_C + (a->v.s.len % (MAX_C - MIN_C + 1));
		if (++a->v.s.len >= STR_SIZE) {
			arg_reset(a);
			return 1;
		}
		a->v.s.s[a->v.s.len] = '\0';
		return 0;
	case A_N:
		if (++a->v.n >= STR_SIZE) {
			arg_reset(a);
			return 1;
		}
		return 0;
	case A_C:
		if (++a->v.c > MAX_C) {
			arg_reset(a);
			return 1;
		}
		return 0;
	default:
		abort();
	}
}

static void arg_alloc(arg *a, unsigned int flags)
{
	if (flags & F_IS_PTR) {
		a->t = (flags & F_SRC) ? A_SRC : A_DST;
		a->v.s.s = malloc(STR_SIZE * 2); /* consider strcat() */
		assert(a->v.s.s != NULL);
	} else if (flags & F_N)
		a->t = A_N;
	else if (flags & F_C)
		a->t = A_C;
	else
		abort();
	arg_reset(a);
}

static void arg_free(arg *a)
{
	if (a->t == A_DST || a->t == A_SRC)
		free(a->v.s.s);
}

static void test_one(fspec *f)
{
	arg a[3];
	int ia, na;

	na = 1;
	while (f->a[na] && na < 4)
		na++;
	na--;

	for (ia = 0; ia < na; ia++)
		arg_alloc(&a[ia], f->a[ia + 1]);

	do {
		const char *r = NULL;

		/* (ptr, ptr, n) or (ptr, ptr) */
		if ((f->a[1] & F_IS_PTR) && (f->a[2] & F_IS_PTR) &&
		    !(f->a[3] & ~F_N)) {
			r = ((char * (*)(char *, char *, size_t))f->f)
			    (a[0].v.s.s, a[1].v.s.s, a[2].v.n);
		} else
		/* (ptr, c) */
		if ((f->a[1] & F_IS_PTR) && (f->a[2] & F_C) && !f->a[3]) {
			r = ((char * (*)(char *, int))f->f)
			    (a[0].v.s.s, a[1].v.c);
		}

		if (((f->a[0] & F_DST) && r != a[0].v.s.s) ||
		    ((f->a[0] & F_IN_A1) &&
		    r && (r < a[0].v.s.s || r > a[0].v.s.s + a[0].v.s.len)))
			fprintf(stderr, "Wrong return value: %p '%s'\n", r, r);

/*
 * Should perform other checks here: for proper NUL termination or padding (as
 * indicated by F_NUL or F_PAD), etc. (need to add more flags).
 */

		ia = 0;
		while (ia < na && arg_next(&a[ia]))
			ia++;
	} while (ia < na);

	for (ia = 0; ia < na; ia++)
		arg_free(&a[ia]);
}

static void test_all(void)
{
	fspec *f;

	for (f = funcs; f->f; f++)
		test_one(f);
}

int main(void)
{
	test_all();

	return 0;
}

cluts repository (was: Weekly reports - B)

[Solar Designer]

Luka,

On Thu, Jun 09, 2011 at 10:20:45PM +0200, Luka Mar??eti?? wrote:
> Anyway, here's something... *hangs head*
> https://github.com/paxcoder/cluts

This gives error 404 today.  Did you move the repository elsewhere or is
it a github glitch?

Alexander

Re: cluts repository

[Solar Designer]

Luka,

On Sat, Jul 09, 2011 at 10:41:47AM +0400, Solar Designer wrote:
> On Thu, Jun 09, 2011 at 10:20:45PM +0200, Luka Mar??eti?? wrote:
> > Anyway, here's something... *hangs head*
> > https://github.com/paxcoder/cluts
> 
> This gives error 404 today.  Did you move the repository elsewhere or is
> it a github glitch?

Oh, I just found (in another message) that you moved it to
https://github.com/lmarcetic/cluts

Alexander