[PATCH 06/25] Add struct scratch_buffer and its internal helper functions

[Florian Weimer]

Paul,

thank you for your extensive comments.

On 03/02/2015 08:33 PM, Paul Eggert wrote:
> On 03/01/2015 06:28 AM, Florian Weimer wrote:
>> +   The non-inlined functions are implemented in such a way that it is
>> +   possible to change the size of the pre-allocated buffer without
>> +   impacting ABI.
> 
> Why does this matter?  The ABI is not exported to users, right?  The
> comment should explain why the ABI business matters.

It helps slightly with online updates.  I don't want to introduce any
additional problems for them if we fine-tune the buffer size.

>> +#define SCRATCH_BUFFER_ALIGNMENT \
>> +  __attribute__ ((aligned (__alignof__ (union {void *p; double d;}))))
> 
> This should use __attribute__ ((aligned (alignof (max_align_t)))), at
> least on C11 platforms.

Hmm.  Isn't intmax_t enough?

>> +struct scratch_buffer {
>> +  void *data;    /* Pointer to the beginning of the scratch area.  */
>> +  size_t length; /* Allocated space at the data pointer, in bytes.  */
>> +  char __space[1024 - sizeof (size_t)] SCRATCH_BUFFER_ALIGNMENT;
>> +} SCRATCH_BUFFER_ALIGNMENT;
> 
> Why are there two SCRATCH_BUFFER_ALIGNMENTs there?  One suffices, no?

Right.

> Why 1024?

That's the magic constant most of the existing code (in NSS) used.

>  And why "- sizeof (size_t)"?  A comment should say.

It turns into - 2 * sizeof (size_t) after doubling for the first heap
allocation, which is the current size of the malloc metadata.  I'll drop
it, it's probably too cute.  If we want to optimize the malloc case,
checking for lack of malloc overloading and then extending transparently
to malloc_usable_size bytes (if no malloc override is in place) seems
more reasonable.

>> +/* Grows *BUFFER by some arbitrary amount.  The buffer contents is NOT
>> +   preserved.  Returns true on success, fails on allocation failure
>> +   (in which case the old buffer is freed).  On success, the new
>> +   buffer is slightly larger (by at least 16 bytes) than the previous
>> +   size.  On failure, *BUFFER is deallocated, but remains in a
>> +   free-able state.  */
> 
> Why 16?  The comment should say.

I bumped it to 512 and added an explanation:

   scratch_buffer_grow and scratch_buffer_grow_preserve are guaranteed
   to grow the buffer by at least 512 bytes.  This means that when
   using the scratch buffer as a backing store for a non-character
   array whose element size, in bytes, is 512 or smaller, the scratch
   buffer only has to grown once to make room for at least one more
   element.

> Shouldn't the caller have some say on how big to grow the buffer?  I can
> see a caller knowing how much space it'll need.

Most callers don't.  And for the very few remaining ones, there is
scratch_buffer_set_array_size.

>  As things stand, such a
> caller needs to repeatedly grow the buffer until it's big enough, which
> is awkward.

It's the main use case in NSS because that's the way gethostbyname_r and
friends were specified.  You don't get to know the required buffer size
on failure.

> Hmm, I see that scratch_buffer_set_array_size lets one set
> the array size to any value, but there's no variant of
> scratch_buffer_set_array_size that preserves the buffer.

It has not come up yet.

> On failure this function sets errno, right?  The comment should say this.

Right.

>> +/* Grows *BUFFER so that it can store at least NELEM elemnts of SIZE
>> +   bytes.  The buffer contents is NOT preserved.  Returns true on
>> +   success, fails on allocation failure (in which case the old buffer
>> +   is freed, but *BUFFER remains a free-able state).  */
> 
> Similar remark about errno.  Also, is this function allowed to shrink
> *BUFFER?  Also, is SIZE allowed to be zero?  The comment should say.

What about this?

/* Grows *BUFFER so that it can store at least NELEM elements of SIZE
   bytes.  The buffer contents is NOT preserved.  Both NELEM and SIZE
   can be zero.  It is unspecified wheter this function can reduce the
   array size.  It returns true on success, false on allocation
   failure (in which case the old buffer is freed, but *BUFFER remains
   a free-able state, and errno is set).  */

>> +  size_t new_length = buffer->length * 2;
> 
> In Gnulib we originally did it this way, but nowadays we grow by a
> factor of 1.5 (new_length = old_length + old_length / 2 + 1) rather than
> by a factor of 2, as this was less jerky for large buffers. Perhaps do
> something similar here?

I think we should leave the fine-tuning to a later stage.  See also the
comment above about malloc_usable_size.

The original code used a growth factor of 3 during the alloca phase, and
2 during the malloc phase.  (After the i386 ABI change for stack
alignment, it's effectively 2 and 2.)

>> +  size_t size_max_square_root = ((size_t)1) << (sizeof (size_t) * 4);
>> +  /* Avoid overflow check if both values are small. */
>> +  if (nelem >= size_max_square_root || size >= size_max_square_root)
> 
> "4" is too much a mystery here and should be spelled out as CHAR_BIT /
> 2.  Also, this is smaller and faster when done this way:
> 
>    if ((nelem | size) >> (sizeof (size_t) * CHAR_BIT / 2) != 0)

Thanks, that's indeed nicer.

In the end, it will best what the compiler will be able to turn in a
multiply-with-overflow-check (which most CPUs provide, but not MIPS, so
it was never standardized as part of C).  Very recent GCC has
__builtin_umull_overflow, so maybe we can use that one day.

>> +      if (nelem != 0 && size > SIZE_MAX / nelem)
> 
> This is a run-time integer division.  It can be a bit faster to do the
> division at compile-time.

I know.  G++ uses a constant which is rounded down to make sure the
constant can be stored directly in the instruction stream on RISC.  The
exact value is often very difficult to encode.

> Gnulib does this by computing 'SIZE_MAX /
> size' in an inline function; 'size' is normally a constant (and must be
> nonzero in Gnulib, which is a reasonable restriction here too).  With
> this optimization, Gnulib doesn't need to mess with size square roots
> either, another minor performance win.

It's hard to tell what's better here.  Even on 32 bit, you need at least
65,536 array elements before the division kicks in.  The current callers
do not call this function repeatedly in a loop.  That's why I think it's
reasonable to simplify the call site instead.  And with
__builtin_umull_overflow, the division will go away eventually anyway.

Empirically, I'm pretty certain the division does not matter
performance-wise.  On x86_64 and i386, the old alloca code had an
integer division, too, and no one complained about its performance.

-- 
Florian Weimer / Red Hat Product Security