This is the mail archive of the 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
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

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)
        = 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.

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

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

code is

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

This triple buffers size until function succeeds.

Again triple buffer size until function succeeds.
Relevant code is
    if (__libc_use_alloca (buflen * 2))
      tmpbuf = extend_alloca (tmpbuf, buflen, buflen * 2);
        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.

again tripling buffer size until function succeeds.

extend_malloca would simplify things
tripling buffer size until function succeeds.


tripling buffer size until function succeeds.


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

Only extends buffer when needed.

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

tripling buffer size until function succeeds.
extend_malloca would simplify things.

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);
        onealt = (char *) malloc (pattern_len);
        if (onealt == NULL)

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

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

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.

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. 

Again having to memmove erases any possible performance benefits. alloca
large buffer first and then using realloc is faster.

tripling buffer size until function succeeds.
extend_malloca would simplify things

tripling buffer size until function succeeds.

tripling buffer size until function succeeds.
extend_malloca would simplify things

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]