facebook / facebook/zstd

RFE: decompressor can work with simple malloc

Open
#3,453 9 comments 1 reaction 1 assignee Claimed by @felixhandte View on GitHub
documentation feature request question
Dominant language
C
Stars
27.9k
Forks
2.6k
Avg merge
1d 3h
Merged PRs (30d)
8

Description

**Is your feature request related to a problem? Please describe.**
Request For Enhancement (RFE): Please document, enhance, and maintain Zstd so that the decompressor **can** work with a malloc+free that uses a private allocation arena with various simple allocation strategies. This request arises from the desire to use Zstd decompression in primitive or "embedded" environments where general-purpose malloc+free is expensive in space, time, and/or development time.

**Describe the solution you'd like**
The simple allocation strategies (truly minimal complexity and code) for decompression are:

0. Fixed-in-advance arena size and block placement, with offsets parameterized by 3 or fewer parameters. free() is a no_op. The run-time decompressor for "upx --lzma" uses a single alloca() of 12KiB to 58KiB, with internal divisions depending on the LZMA parameters literal_context_bits and position_bits, which have been restricted at compression-time.

1. malloc() allocates each (aligned) request adjacent to the previous allocation; free() is a no_op. The compressor reports the
total size of all requests that will be made during decompression by the known decompressors.

2. Stack allocation from one end of the arena: malloc() is a Push, free() is a Pop. The compressor reports the minimum size of the stack.

3. Two stacks, growing towards each other from the ends of the arena. The decompressor code specifies which stack should be used by each call to malloc(). This allows separating allocations with long lifetimes from those with short lifetimes, which usually can reduce the size of the arena and simplify the scheduling of calls to free().

4. Stack, but with mark()+release() like Pascal. This can be even more flexible because release() removes the ordering restriction on what would otherwise be a sequence of calls to free(). Strategies 0 and 1 above (where free() is a no_op) are special cases of implied mark() at the beginning of decompression, and implied release() at the end.

The return values from calling the compressor must include the minimum size of the private decompression arena for each of the simple allocation strategies.

**Describe alternatives you've considered**
Implement general stand-alone malloc+free for the primitive environments.

**Additional context**
The follow-on request will be for a compressor which takes an incoming argument that specifies the size of the arena that the decompressor can support. The compressor must choose parameters and strategy (including which variant of decompression code) that is constrained by that maximum, taking advantage of the properties of each simple implementation of malloc+free during decompression.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.