allocation limit for encoding conversion

Somebody ran into issues when generating large XML output (upwards of
256 MB) and then sending via a connection with a different
client_encoding. This occurs because we pessimistically allocate 4x as
much memory as the string needs, and we run into the 1GB palloc
limitation. ISTM we can do better now by using huge allocations, as per
the preliminary attached patch (which probably needs an updated overflow
check rather than have it removed altogether); but at least it is able
to process this query, which it wasn't without the patch:

select query_to_xml(
'select a, cash_words(a::text::money) from generate_series(0, 2000000) a',
true, false, '');

--
Álvaro Herrera

On 2019-Aug-16, Alvaro Herrera wrote:

> Somebody ran into issues when generating large XML output (upwards of
> 256 MB) and then sending via a connection with a different
> client_encoding.

ref: https://postgr.es/m/[email protected]
(pgsql-es-ayuda)

--
Álvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> writes:
> Somebody ran into issues when generating large XML output (upwards of
> 256 MB) and then sending via a connection with a different
> client_encoding. This occurs because we pessimistically allocate 4x as
> much memory as the string needs, and we run into the 1GB palloc
> limitation. ISTM we can do better now by using huge allocations, as per
> the preliminary attached patch (which probably needs an updated overflow
> check rather than have it removed altogether); but at least it is able
> to process this query, which it wasn't without the patch:

> select query_to_xml(
> 'select a, cash_words(a::text::money) from generate_series(0, 2000000) a',
> true, false, '');

I fear that allowing pg_do_encoding_conversion to return strings longer
than 1GB is just going to create failure cases somewhere else.

However, it's certainly true that 4x growth is a pretty unlikely worst
case. Maybe we could do something like

1. If string is short (say up to a few megabytes), continue to do it
like now. This avoids adding overhead for typical cases.

2. Otherwise, run some lobotomized form of encoding conversion that
just computes the space required (as an int64, I guess) without saving
the result anywhere.

3. If space required > 1GB, fail.

4. Otherwise, allocate just the space required, and convert.

regards, tom lane

Hi,

On 2019-08-16 17:31:49 -0400, Tom Lane wrote:
> Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> writes:
> > Somebody ran into issues when generating large XML output (upwards of
> > 256 MB) and then sending via a connection with a different
> > client_encoding. This occurs because we pessimistically allocate 4x as
> > much memory as the string needs, and we run into the 1GB palloc
> > limitation. ISTM we can do better now by using huge allocations, as per
> > the preliminary attached patch (which probably needs an updated overflow
> > check rather than have it removed altogether); but at least it is able
> > to process this query, which it wasn't without the patch:
>
> > select query_to_xml(
> > 'select a, cash_words(a::text::money) from generate_series(0, 2000000) a',
> > true, false, '');
>
> I fear that allowing pg_do_encoding_conversion to return strings longer
> than 1GB is just going to create failure cases somewhere else.
>
> However, it's certainly true that 4x growth is a pretty unlikely worst
> case. Maybe we could do something like
>
> 1. If string is short (say up to a few megabytes), continue to do it
> like now. This avoids adding overhead for typical cases.
>
> 2. Otherwise, run some lobotomized form of encoding conversion that
> just computes the space required (as an int64, I guess) without saving
> the result anywhere.
>
> 3. If space required > 1GB, fail.
>
> 4. Otherwise, allocate just the space required, and convert.

It's probably too big a hammer for this specific case, but I think at
some point we ought to stop using fixed size allocations for this kind
of work. Instead we should use something roughly like our StringInfo,
except that when exceeding the current size limit, the overflowing data
is stored in a separate allocation. And only once we actually need the
data in a consecutive form, we allocate memory that's large enough to
store the all the separate allocations in their entirety.

Greetings,

Andres Freund

Andres Freund <andres(at)anarazel(dot)de> writes:
> On 2019-08-16 17:31:49 -0400, Tom Lane wrote:
>> I fear that allowing pg_do_encoding_conversion to return strings longer
>> than 1GB is just going to create failure cases somewhere else.
>>
>> However, it's certainly true that 4x growth is a pretty unlikely worst
>> case. Maybe we could do something like
>> 1. If string is short (say up to a few megabytes), continue to do it
>> like now. This avoids adding overhead for typical cases.
>> 2. Otherwise, run some lobotomized form of encoding conversion that
>> just computes the space required (as an int64, I guess) without saving
>> the result anywhere.
>> 3. If space required > 1GB, fail.
>> 4. Otherwise, allocate just the space required, and convert.

> It's probably too big a hammer for this specific case, but I think at
> some point we ought to stop using fixed size allocations for this kind
> of work. Instead we should use something roughly like our StringInfo,
> except that when exceeding the current size limit, the overflowing data
> is stored in a separate allocation. And only once we actually need the
> data in a consecutive form, we allocate memory that's large enough to
> store the all the separate allocations in their entirety.

That sounds pretty messy :-(.

I spent some time looking at what I proposed above, and concluded that
it's probably impractical. In the first place, we'd have to change
the API spec for encoding conversion functions. Now maybe that would
not be a huge deal, because there likely aren't very many people outside
the core code who are defining their own conversion functions, but it's
still a negative. More importantly, unless we wanted to duplicate
large swaths of code, we'd end up inserting changes about like this
into the inner loops of encoding conversions:

- *dest++ = code;
+ if (dest)
+ *dest++ = code;
+ outcount++;

which seems like it'd be bad for performance.

So I now think that Alvaro's got basically the right idea, except
that I'm still afraid to allow strings larger than MaxAllocSize
to run around loose in the backend. So in addition to the change
he suggested, we need a final check on strlen(result) not being
too large. We can avoid doing a useless strlen() if the input len
is small, though.

It then occurred to me that we could also repalloc the output buffer
down to just the required size, which is pointless if it's small
but not if we can give back several hundred MB. This is conveniently
mergeable with the check to see whether we need to check strlen or not.

... or at least, that's what I thought we could do. Testing showed
me that AllocSetRealloc never actually gives back any space, even
when it's just acting as a frontend for a direct malloc. However,
we can fix that for little more than the price of swapping the order
of the is-it-a-decrease and is-it-a-large-chunk stanzas, as in the
0002 patch below.

I also put back the missing overflow check --- although that's unreachable
in a 64-bit machine, it's not at all in 32-bit. The patch is still
useful in 32-bit though, since it still doubles the size of string
we can cope with.

I think this is committable, though surely another pair of eyeballs
on it wouldn't hurt. Also, is it worth having a different error
message for the case where the output does exceed MaxAllocSize?

regards, tom lane

On 2019-09-24 16:19:41 -0400, Tom Lane wrote:
> Andres Freund <andres(at)anarazel(dot)de> writes:
> > On 2019-08-16 17:31:49 -0400, Tom Lane wrote:
> >> I fear that allowing pg_do_encoding_conversion to return strings longer
> >> than 1GB is just going to create failure cases somewhere else.
> >>
> >> However, it's certainly true that 4x growth is a pretty unlikely worst
> >> case. Maybe we could do something like
> >> 1. If string is short (say up to a few megabytes), continue to do it
> >> like now. This avoids adding overhead for typical cases.
> >> 2. Otherwise, run some lobotomized form of encoding conversion that
> >> just computes the space required (as an int64, I guess) without saving
> >> the result anywhere.
> >> 3. If space required > 1GB, fail.
> >> 4. Otherwise, allocate just the space required, and convert.
>
> > It's probably too big a hammer for this specific case, but I think at
> > some point we ought to stop using fixed size allocations for this kind
> > of work. Instead we should use something roughly like our StringInfo,
> > except that when exceeding the current size limit, the overflowing data
> > is stored in a separate allocation. And only once we actually need the
> > data in a consecutive form, we allocate memory that's large enough to
> > store the all the separate allocations in their entirety.
>
> That sounds pretty messy :-(.

I don't think it's too bad - except for now allowing the .data member of
such a 'chunked' StringInfo to be directly accessible, it'd be just
about the same interface as the current stringinfo. Combined perhaps
with a helper or two for "de-chunking" directly into another stringinfo,
network buffer etc, to avoid the unnecessary allocation of a buffer of
the overall size when the result is just going to be memcpy'd elsewhere.

Obviously a good first step would just to pass a StringInfo to the
encoding routines. That'd solve the need for pessimistic overallocation,
because the buffer can be enlarged. And by sizing the initial allocation
to the input string (or at least only a small factor above), we'd not
usually need (many) reallocations.

That'd also remove the need for unnecessary strlen/memcpy done in many
encoding conversion callsites, like e.g.:

p = pg_server_to_client(str, slen);
if (p != str) /* actual conversion has been done? */
{
slen = strlen(p);
appendBinaryStringInfo(buf, p, slen);
pfree(p);
}

which do show up in profiles.

> I spent some time looking at what I proposed above, and concluded that
> it's probably impractical. In the first place, we'd have to change
> the API spec for encoding conversion functions. Now maybe that would
> not be a huge deal, because there likely aren't very many people outside
> the core code who are defining their own conversion functions, but it's
> still a negative. More importantly, unless we wanted to duplicate
> large swaths of code, we'd end up inserting changes about like this
> into the inner loops of encoding conversions:
>
> - *dest++ = code;
> + if (dest)
> + *dest++ = code;
> + outcount++;
> which seems like it'd be bad for performance.

One thing this made me wonder is if we shouldn't check the size of the
output string explicitly, rather than relying on overallocation. The
only reason we need an allocation bigger than MaxAllocSize here is that
we don't pass the output buffer size to the conversion routines. If
those routines instead checked whether the output buffer size is
exceeded, and returned with the number of converted input bytes *and*
the position in the output buffer, we wouldn't have to overallocate
quite so much.

But I suspect using a StringInfo, as suggested above, would be better.

To avoid making the tight innermost loop more expensive, I'd perhaps
code it roughly like:

/*
* Initially size output buffer to the likely required length, to
* avoid unnecessary reallocations while growing.
*/
enlargeStringInfo(output, input_len * ESTIMATED_GROWTH_FACTOR);

/*
* Process input in chunks, to reduce overhead of maintaining output buffer
* for each processed input char. Increasing the buffer size too much will
* lead to memory being wasted due to the necessary over-allocation.
*/
#define CHUNK_SIZE 128
remaining_bytes = input_len;
while (remaining_bytes > 0)
{
local_len = Min(remaining_bytes, CHUNK_SIZE);

/* ensure we have output buffer space for this chunk */
enlargeStringInfo(output, MAX_CONVERSION_GROWTH * local_len);

/* growing the stringinfo may invalidate previous dest */
dest = output->data + output->len;

while (local_len > 0)
{
/* current conversion logic, barely any slower */
}

remaining_bytes -= local_len;
output->len = dest - output->data;
}

Assert(remaining_bytes == 0);

And to avoid duplicating this code all over I think we could package it
in a inline function with a per-char callback. Just about every useful
compiler ought to be able to remove those levels of indirection.

So a concrete conversion routine might look like:

static inline int
iso8859_1_to_utf8_char(ConversionState *state)
{
unsigned short c = *state->src;

if (c == 0)
report_invalid_encoding(PG_LATIN1, (const char *) state->src, state->len);
if (!IS_HIGHBIT_SET(c))
*state->dest++ = c;
else
{
*state->dest++ = (c >> 6) | 0xc0;
*state->dest++ = (c & 0x003f) | HIGHBIT;
}
state->src++;
state->len--;
}

Datum
iso8859_1_to_utf8(PG_FUNCTION_ARGS)
{
ConversionState state = {
.conservative_growth_factor = 1.05,
.max_perchar_overhead = 2,
.src = (unsigned char *) PG_GETARG_CSTRING(2),
.dest = (StringInfo *) PG_GETARG_POINTER(3),
.len = PG_GETARG_INT32(4),
};

return encoding_conv_helper(&state, iso8859_1_to_utf8_char);
}

where encoding_conv_helper is a static inline function that does the
chunking described above.

There's probably some added complexity around making sure that the
chunking properly deals with multi-byte encodings properly, but that
seems solvable.

> It then occurred to me that we could also repalloc the output buffer
> down to just the required size, which is pointless if it's small
> but not if we can give back several hundred MB. This is conveniently
> mergeable with the check to see whether we need to check strlen or not.
>
> ... or at least, that's what I thought we could do. Testing showed
> me that AllocSetRealloc never actually gives back any space, even
> when it's just acting as a frontend for a direct malloc. However,
> we can fix that for little more than the price of swapping the order
> of the is-it-a-decrease and is-it-a-large-chunk stanzas, as in the
> 0002 patch below.

That seems generally like a good idea.

Greetings,

Andres Freund

Andres Freund <andres(at)anarazel(dot)de> writes:
> On 2019-09-24 16:19:41 -0400, Tom Lane wrote:
>> Andres Freund <andres(at)anarazel(dot)de> writes:
>>> It's probably too big a hammer for this specific case, but I think at
>>> some point we ought to stop using fixed size allocations for this kind
>>> of work. Instead we should use something roughly like our StringInfo,
>>> except that when exceeding the current size limit, the overflowing data
>>> is stored in a separate allocation. And only once we actually need the
>>> data in a consecutive form, we allocate memory that's large enough to
>>> store the all the separate allocations in their entirety.

>> That sounds pretty messy :-(.

> I don't think it's too bad - except for now allowing the .data member of
> such a 'chunked' StringInfo to be directly accessible, it'd be just
> about the same interface as the current stringinfo.

I dunno. What you're describing would be a whole lotta work, and it'd
break a user-visible API, and no amount of finagling is going to prevent
it from making conversions somewhat slower, and the cases where it matters
to not preallocate a surely-large-enough buffer are really few and far
between. I have to think that we have better ways to spend our time.

regards, tom lane

Hi,

On September 24, 2019 3:09:28 PM PDT, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>Andres Freund <andres(at)anarazel(dot)de> writes:
>> On 2019-09-24 16:19:41 -0400, Tom Lane wrote:
>>> Andres Freund <andres(at)anarazel(dot)de> writes:
>>>> It's probably too big a hammer for this specific case, but I think
>at
>>>> some point we ought to stop using fixed size allocations for this
>kind
>>>> of work. Instead we should use something roughly like our
>StringInfo,
>>>> except that when exceeding the current size limit, the overflowing
>data
>>>> is stored in a separate allocation. And only once we actually need
>the
>>>> data in a consecutive form, we allocate memory that's large enough
>to
>>>> store the all the separate allocations in their entirety.
>
>>> That sounds pretty messy :-(.
>
>> I don't think it's too bad - except for now allowing the .data member
>of
>> such a 'chunked' StringInfo to be directly accessible, it'd be just
>> about the same interface as the current stringinfo.
>
>I dunno. What you're describing would be a whole lotta work, and it'd
>break a user-visible API, and no amount of finagling is going to
>prevent
>it from making conversions somewhat slower, and the cases where it
>matters
>to not preallocate a surely-large-enough buffer are really few and far
>between. I have to think that we have better ways to spend our time.

It'd not just avoid the overallocation, but also avoid the strlen and memcpy afterwards at the callsites, as well as the separate allocation. So I'd bet it'd be almost always a win.

Andres

--
Sent from my Android device with K-9 Mail. Please excuse my brevity.

I wrote:
> [ v2-0001-cope-with-large-encoding-conversions.patch ]
> [ v2-0002-actually-recover-space-in-repalloc.patch ]

I've pushed these patches (after some more review and cosmetic
adjustments) and marked the CF entry closed. Andres is welcome
to see if he can improve the situation further.

regards, tom lane

On 2019-Oct-03, Tom Lane wrote:

> I wrote:
> > [ v2-0001-cope-with-large-encoding-conversions.patch ]
> > [ v2-0002-actually-recover-space-in-repalloc.patch ]
>
> I've pushed these patches (after some more review and cosmetic
> adjustments) and marked the CF entry closed. Andres is welcome
> to see if he can improve the situation further.

Many thanks!

--
Álvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services