Current percentiles are:
 * P25: 34.44 KiB
 * P50: 71.59 KiB
 * P75: 498.5 KiB
 * P90: 1.056 MiB

Almost all used memory is RingBuffer. Its size depends on "window size" encoder parameter and varies between 1KiB to 16MiB.

Decoder tries to keep RingBuffer small, e.g. if it is known that output is smaller than "window size" then smaller RingBuffer is allocated.

This way, in most cases, Brotli memory usage is as large and produced output.
There is a way to save memory: if decoder is given output buffer big enough to place all produced data, then no RingBuffer is required.

The other way to reduce memory footprint is to inform server about desired "window size", so it would pass it to encoder.

(option with big enough output buffer is not implemented yet; it is easy to add it in less than a week)

The option with the big enough output buffer is interesting - we currently use a 512k shared memory buffer, but only request 32k at a time, so we can stream it to the renderer...Of course, that's *another* buffer we should consider shrinking.

"it may make sense not to advertise brotli support, or it may make sense not to advertise support whenever we're under memory pressure."

How can we make these guesses more actionable?

 - Do we have data on which we could base an estimation of how common this could be on low memory devices / low-memory pressure conditions?
 - How much of a reduction would we need in order to make a significant difference?
 - Should we have UMA to answer these questions?

These insights would also help the prioritization of this work.

The current percentiles from above, are those from UMA? If so, we could generate corresponding data for low-end devices (there's a filter in UMA for that).

Of appropriate filters I see only "Short Hardware Class". But there are too many items to choose from.

The filter is called "Low Memory Device (Android)"

P25 34.78
P50 65.26
P75 211.3
P90 645.0

Issue 641008 shows that there are a uptick in OOM in Brotli code. Here's one crash report that shows an OOM when Brotli tries to allocate ~1 MiB of memory: https://crash.corp.google.com/browse?q=custom_data.ChromeCrashProto.ptype%3D%27browser%27%20AND%20custom_data.ChromeCrashProto.magic_signature_1.name%3D%27%5BOut%20of%20Memory%5D%20net%3A%3ABrotliFilter%3A%3AAllocateMemory%27%20AND%20product.name%3D%27Chrome%27&ignore_case=false&enable_rewrite=true&omit_field_name=&omit_field_value=&omit_field_opt=%3D&stbtiq=&reportid=46dc42b700000000&index=1#0. Thanks mmenke@ for finding one with a minidump. 


"BrotliFilter.UsedMemoryKB shows" that Brotli has a medium foot print of 1MiB:
https://uma.googleplex.com/p/chrome/histograms/?endDate=20161120&dayCount=1&histograms=BrotliFilter.UsedMemoryKB&fixupData=true&showMax=true&filters=channel%2Ceq%2C1%2Cisofficial%2Ceq%2CTrue&implicitFilters=isofficial

How is this 1MiB spent? Do we a design doc justifying the memory usage?

1MiB is allocated when encoded file has 1MiB+ LZ backward reference window.
It is an essential concept of LZ compression.

Servers that encode content have ability to limit this window size. So, memory consumption depends on content producers.

It is possible to make decoder wait until required amount of memory is available, but to use this ability we need a way to perform non-crashing memory request.

Drive by question: If the server has the ability to limit the window size, does it also have the ability to increase it?  I.e. Brotli be used as a vector to DDOS browser memory even if we're not in low-memory situations?

(For the record, I think SDCH has a similar vulnerability.  And GZIP may as well.)

Maximum window size is 16MiB. But brotli allocates memory carefully; it will not request N MiB until it is necessary (i.e. output is bigger N/2 MiB).

Gzip only uses a 32k window per stream, and compression tables, which are probably, at worst, around 16k, and most likely much smaller than that, depending on how they're stored.

This issue was raised when brotli was added (Not sure about SDCH).  Wonder how many brotli streams we're simultaneously decompressing.  Gathering that information may tell us enough to figure out if this is a leak or just brotli being brotli.

Eustas:  A memory allocator that could fail wouldn't be enough.  If we're 1MB away from OOMing, due to brotli, there's a good chance we'll OOM elsewhere.

I agree with Matt that Gzip is not memory heavy. Sdch can consume a fair amount of memory storing dictionaries, which needs a separate investigation. Sdch clears dictionaries under memory pressure (SdchOwner::OnMemoryPressure), though I am not sure how efficient that is. 

Eustas: Could you investigate that memory is released when decoding is done and we aren't leaking it? (as suggested in #17) I suppose we could start investigating whether brotli_free_func are invoked appropriately.

There is a DCHECK for that: https://cs.chromium.org/chromium/src/net/filter/brotli_source_stream.cc?rcl=0&l=43

Thanks for pointing out the DCHECK. 
Are there any production servers that uses Brotli? Or is there a local server that I can use? I am adding more instrumentation in net stack (https://docs.google.com/document/d/1zBX27tvkc8ZJHp9yvm6EQJrMDIhDCU92YlahaGFwsyc/edit), so I can look into this as well.

Facebook serves brotli.
It is very easy to create your own server, if you have Apache+PHP. Just add "Content-Encoding" header and push pre-compressed content.

I have a suspicion that the problem occurs not because memory is low, but because it is highly fragmented. All current Chrome OOMers seem like places that need single continuous piece. Can we somehow get memory map / free memory / allocated block size histogram for crashes?

And, of course, if problem is memory fragmentation, I can make a workaround in Brotli, to trade some speed to ability use small memory chunks. 

I looked into this and didn't find any memory leak. However, it looks like the ring buffer is as large as the entire response body. eustas@: is this expected?

I have a ~4MB resource with a compressed size of ~0.5MB. BrotliSourceStream allocated 4MB. Is this expected?

(trace file attached)

Deleted: brotli_4MB.json 19.6 MB

brotli_4MB.json 19.6 MB Download

This is expected if window size ("-w" param) is >= 22.
BROTLI_DEFAULT_WINDOW is 22 -> most likely it was used.

Current percentiles (Canary) are:
 * P25: 28.83 KiB
 * P50: 49.40 KiB
 * P75: 113.25 KiB
 * P90: 923.54 KiB

Latest percentiles (Aug 01 2017):
 * P50: 39.16 KiB
 * P75: 98.48 KiB
 * P80: 113.46 KiB
 * P85: 171.43 KiB
 * P90: 308.57 KiB
 * P95: 590.57 KiB

Latest data from M63 Android Stable (Jan 01 2018) with Low Memory Device(Android) filter:
P25	27.83 KiB
P50	33.80 KiB
P75	95.64 KiB
P85	159.3 KiB
P95	329.1 KiB

https://uma.googleplex.com/p/chrome/histograms/?endDate=20180101&dayCount=7&histograms=BrotliFilter.UsedMemoryKB&fixupData=true&hideExactCounts=true&showMax=true&analysis=0.25%200.5%200.75%200.85%200.95&filters=platform%2Ceq%2CA%2Cchannel%2Ceq%2C4%2Cis_low_mem%2Ceq%2CTrue%2Call_version%2Ceq%2C63.0.3239.111%2Cisofficial%2Ceq%2CTrue&implicitFilters=isofficial

I've subscribed to the BrotliFilter.UsedMemoryKB histogram for several months now. The memory usage has come down. The median memory usage (~40KiB) is reasonable and is comparable to that of gzip. We could avoid advertising Brotli if we are under memory pressure, but given the memory usage numbers, this is probably of low priority. I am archiving this bug due to lack of activity. Please feel free to reopen if further investigation is needed.