This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] malloca v2


On Wed, Jan 16, 2013 at 03:14:02PM -0800, Roland McGrath wrote:
> There are numerous style problems I won't bother to enumerate.  Someone
> else might be more in the mood to repeat all the same stuff that anybody
> who has sent more than two patches to this list ought to have picked up
> already by now.
> 
> You're using __attribute__ ((cleanup)) wrong, suggesting you
> haven't actually tested this properly.

Now it is time to get interface rigth. It is pointless to test code that
probably wont be there. 
> 
> I'm only interested in something to be used by libc internals.  So
> conditionals about any other kind of use are just cruft in the way of
> useful review for libc purposes.
> 
> A quick glancing audit of all the uses of __libc_use_alloca shows that few
> of them are used in loops and the like.  Uses without loops don't need such
> complexity in the cleanup function, because there is just one block to
> free.  

This was mentioned previously in thread.
There are quite a few places where _libc_use_alloca is used for times in function.
You need that complexity there, otherwise you waste four registers
insteead one and in likely case do four checks instead one.

> Of the uses in loops, some already use something more complex like
> extend_alloca and/or alloca_account, so that those could not be converted
> to your API without losing some of the more sophisticated adaptive behavior
> they have now.

This replaces alloca_account by doing bookkeeping automatically. Also
tests can be made more effective than current. Already 
mentioned as alloca_account that ignore len in previous iteration.

extend_alloca/extend_alloca_account are separate concern. A
extend_alloca uses try to keep all allocations at stack so they should
stay.
They have several issues, one is that they waste memory by needlesly allocating
more than requested.
I planed to address this by free_alloca that checks pointer is in top of
stack if it is then frees it.
This would allow to add extend_malloca that can free stack space when
grows large. 

> 
> I'm not really interested in any new internal API that doesn't address all
> the kinds of uses we already have.  That means supporting the uses that
> today use extend_alloca and alloca_account.
> 
> Preemptively fiddling with the implementation like you are doing seems like
> a waste of effort to me.  The sensible path to anything that will actually
> be accepted in libc would start with doing a thorough audit of the uses of
> alloca that exist in the libc code today, categorizing them by how complex
Ok you got what you wished for. 

$ git grep extend_alloca

elf/dl-deps.c 
Its usage makes it hard to run out of stack even if we replaced
extend_alloca by alloca. But it is used wrong. It has loop with extend_alloca
and alloca. Relevant fragment is this:

size_t new_size = l->l_ldnum * sizeof (struct link_map *);

    if (new_size > needed_space_bytes)
      needed_space
        = extend_alloca (needed_space, needed_space_bytes, new_size);

When at i'th iteration l->l_ldnum is i and extra alloca always happens between
these then you have quadratic space complexity when linear is possible.

elf/dl-fini.c
Relatively ok. Only contain duplicate code which elf/dl-deps.c did not
duplicate.

  if (maps_size == 0)
      {
        maps_size = nloaded * sizeof (struct link_map *);
        maps = (struct link_map **) alloca (maps_size);
      }
    else
      maps = (struct link_map **)
        extend_alloca (maps, maps_size,
           nloaded * sizeof (struct link_map *));

elf/pldd-xx.c
elf/pldd.c
code is

 while ((nexe = readlinkat (dfd, "exe", exe, exesize)) == exesize)
    extend_alloca (exe, exesize, 2 * exesize);

This triple buffers size until function succeeds.

grp/compat-initgroups.c
Again triple buffer size until function succeeds.
Relevant code is
    if (__libc_use_alloca (buflen * 2))
      tmpbuf = extend_alloca (tmpbuf, buflen, buflen * 2);
    else
      {
        buflen *= 2;
        char *newbuf = realloc (use_malloc ? tmpbuf : NULL, buflen);
        if (newbuf == NULL)
          {
            result = NSS_STATUS_TRYAGAIN;
            goto done;
          }
        use_malloc = true;
        tmpbuf = newbuf;
      }

extend_malloca would simplify things.


inet/getnameinfo.c
again tripling buffer size until function succeeds.

nis/nss_compat/compat-initgroups.c
extend_malloca would simplify things
tripling buffer size until function succeeds.

nis/nss_compat/compat-initgroups.c
nptl/sysdeps/unix/sysv/linux/pthread_setaffinity.c
nscd/aicache.c
nscd/connections.c

tripling buffer size until function succeeds.


nscd/grpcache.c
nscd/hstcache.c
nscd/pwdcache.c
nscd/servicescache.c

These four contain identical code for lookup function. Macro could
simplify things.
tripling buffer size until function succeeds.
extend_malloca would simplify things


nscd/nscd_getgr_r.c 
Only extends buffer when needed.

nss/getent.c 
Extend alloca is for race between adding groups to user and reading all
groups. Probably extend_alloca is not needed.

nss/nss_files/files-hosts.c
tripling buffer size until function succeeds.
extend_malloca would simplify things.

posix/glob.c
Definitely needs cleanup. There are parts like

#ifdef _LIBC
    int alloca_onealt = __libc_use_alloca (alloca_used + pattern_len);
    if (alloca_onealt)
      onealt = alloca_account (pattern_len, alloca_used);
    else
#endif
      {
        onealt = (char *) malloc (pattern_len);
        if (onealt == NULL)

with avoidable ifdef for example by 
#ifndef _LIBC
#define __libc_use_alloca 0
#endif

I didn't look into detail but malloca would simplify it.

posix/wordexp.c
increasing size by 1000 could lead to possible quadratic time but I do not
see how could be password entry more than 1000 characters large.

stdio-common/vfprintf.c
Here it is better to compute size in first pass  by loop
for (f = lead_str_end; *f != L_('\0'); f = specs[nspecs++].next_fmt);
To avoid  memmove when reallocating. 

stdio-common/vfscanf.c
Again having to memmove erases any possible performance benefits. alloca
large buffer first and then using realloc is faster.

sysdeps/posix/getaddrinfo.c
tripling buffer size until function succeeds.
extend_malloca would simplify things

sysdeps/unix/sysv/linux/gethostid.c
tripling buffer size until function succeeds.

sysdeps/unix/sysv/linux/getlogin_r.c
tripling buffer size until function succeeds.
extend_malloca would simplify things

sysdeps/unix/sysv/linux/sched_setaffinity.c
tripling buffer size until function succeeds.

> the usage patterns are and the details of those complexities.  Only from
> that information can one evaluate an API proposal to see how it compares in
> maintainability to what we have now across all the categories.  If
> something handles all the uses adequately and is clearly easier to use for
> at least many of them, then it will merit serious consideration.  That
> consideration will require analysis of the generated code to see how it
> compares to what we get today, and we'll only accept it if the code is at
> least as good or is only slightly worse in some corner cases if that's
> justified by a great improvement in maintainability.
> 
> 
> Thanks,
> Roland

-- 

Change your language to Finnish.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]