Skip to content

Commit 431f0f1

Browse files
ThomasWaldmannmaikschulzeclaude
committed
pythongh-155460: Pre-size each whole zstd frame, respect window_log_max
On top of the pre-allocation in the previous commit: - Pre-size only when the first input of a frame holds the whole zstd1 frame, and check the recorded size against that frame's compressed size instead of all of the input, so that neither a frame fed in pieces nor the data following a frame leads to a pre-allocation. The 1 GiB limit stays. - Check the frame's window size against window_log_max before pre-sizing: libzstd's single-pass mode, which a pre-sized output enables, doesn't check it. - zstd.decompress() feeds each frame whole, sized with get_frame_size(), so every frame of multi-frame input is pre-sized, not only the first. Co-authored-by: Maik Schulze <[email protected]> Co-Authored-By: Claude Opus 5.5 <[email protected]>
1 parent 0814951 commit 431f0f1

4 files changed

Lines changed: 346 additions & 20 deletions

File tree

‎Lib/compression/_common/_streams.py‎

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -172,14 +172,18 @@ def tell(self):
172172

173173

174174
def _decompress_all(data, decomp_factory, trailing_error=(), *,
175-
stream_magic=(), truncated_error, **decomp_args):
175+
stream_magic=(), truncated_error, stream_size=None,
176+
**decomp_args):
176177
"""Decompress all of the concatenated streams in *data*.
177178
178179
Each stream is decompressed by a new decompressor, made by calling
179180
*decomp_factory* with *decomp_args*. As in DecompressReader, an error
180181
of class *trailing_error* in a stream after the first one ends the
181182
data, unless that stream starts with *stream_magic*. A stream without
182183
an end-of-stream marker raises *truncated_error*.
184+
185+
*stream_size*, if given, is called with the data that starts a stream
186+
and returns the size of that stream, or None if it cannot tell.
183187
"""
184188
results = []
185189
# The views are released on exit, so that the caller can resize a
@@ -190,6 +194,13 @@ def _decompress_all(data, decomp_factory, trailing_error=(), *,
190194
# data, to decompress it in one go.
191195
chunk_size = len(data)
192196
while True:
197+
if stream_size is not None:
198+
# A stream whose size is known is fed whole, in one chunk
199+
# that ends where the stream ends.
200+
with data[pos:] as rest:
201+
size = stream_size(rest)
202+
if size:
203+
chunk_size = size
193204
decomp = decomp_factory(**decomp_args)
194205
start = pos
195206
res = []

‎Lib/compression/zstd/__init__.py‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -163,9 +163,20 @@ def decompress(data, zstd_dict=None, options=None):
163163
"""
164164
return _streams._decompress_all(data, ZstdDecompressor,
165165
truncated_error=ZstdError,
166+
stream_size=_frame_size,
166167
options=options, zstd_dict=zstd_dict)
167168

168169

170+
def _frame_size(data):
171+
# The size of the complete frame at the start of *data*, or None. Fed
172+
# whole, a frame that records its content size is decompressed into an
173+
# output buffer allocated once, at that size.
174+
try:
175+
return get_frame_size(data)
176+
except ZstdError:
177+
return None
178+
179+
169180
class CompressionParameter(enum.IntEnum):
170181
"""Compression parameters."""
171182

‎Lib/test/test_zstd.py‎

Lines changed: 230 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1053,6 +1053,236 @@ def test_decompress_content_size_known_split_input(self):
10531053
self.assertEqual(dat, DAT_130K_D)
10541054
self.assertTrue(d.eof)
10551055

1056+
# Hand-built frames, independent of what the compressor emits. See RFC 8878.
1057+
_BLOCK_SIZE_MAX = 128 * _1K
1058+
1059+
def _frame(content_size, blocks, window_log=17):
1060+
"""A frame whose header records *content_size*, whatever *blocks* hold."""
1061+
return (b'\x28\xb5\x2f\xfd' # magic number
1062+
+ bytes([0b1100_0000]) # 8-byte content size field
1063+
+ bytes([(window_log - 10) << 3]) # window size
1064+
+ content_size.to_bytes(8, 'little')
1065+
+ b''.join(blocks))
1066+
1067+
def _raw_block(data, last=False):
1068+
return (last | 0 << 1 | len(data) << 3).to_bytes(3, 'little') + data
1069+
1070+
def _rle_block(byte, size, last=False):
1071+
return (last | 1 << 1 | size << 3).to_bytes(3, 'little') + bytes([byte])
1072+
1073+
def _peak_allocation(func, *args, **kwargs):
1074+
"""Call func() and return the peak of memory allocated by Python
1075+
during the call, above what was allocated before it."""
1076+
import tracemalloc
1077+
tracing = tracemalloc.is_tracing()
1078+
if not tracing:
1079+
tracemalloc.start()
1080+
try:
1081+
before = tracemalloc.get_traced_memory()[0]
1082+
tracemalloc.reset_peak()
1083+
try:
1084+
func(*args, **kwargs)
1085+
except ZstdError:
1086+
pass
1087+
return tracemalloc.get_traced_memory()[1] - before
1088+
finally:
1089+
if not tracing:
1090+
tracemalloc.stop()
1091+
1092+
1093+
@support.cpython_only
1094+
class DecompressorOutputSizeTestCase(unittest.TestCase):
1095+
# A frame that records its content size has its output allocated once,
1096+
# at that size. The recorded size is input, though: it must never make
1097+
# the decompressor allocate more than the frame can decode to.
1098+
1099+
# Small enough not to stress the test machine, large enough that
1100+
# allocating it is not mistaken for the noise of a decompress() call.
1101+
CLAIM = 64 * _1M
1102+
NOISE = 1 * _1M
1103+
1104+
def assertAllocatedAbout(self, peak, size):
1105+
self.assertGreaterEqual(peak, size)
1106+
self.assertLess(peak, size + self.NOISE)
1107+
1108+
def test_hand_built_frames(self):
1109+
self.assertEqual(
1110+
decompress(_frame(5, [_raw_block(b'hello', last=True)])), b'hello')
1111+
self.assertEqual(
1112+
decompress(_frame(3, [_rle_block(ord('x'), 3, last=True)])), b'xxx')
1113+
1114+
def test_output_allocated_once(self):
1115+
data = bytes(range(256)) * (8 * _1K) # 2 MiB
1116+
frame = compress(data)
1117+
self.assertEqual(get_frame_info(frame).decompressed_size, len(data))
1118+
self.assertEqual(decompress(frame), data)
1119+
self.assertAllocatedAbout(_peak_allocation(decompress, frame), len(data))
1120+
self.assertAllocatedAbout(
1121+
_peak_allocation(ZstdDecompressor().decompress, frame), len(data))
1122+
1123+
def test_output_allocated_once_densest_frame(self):
1124+
# RLE blocks are the densest valid encoding: 4 bytes per 128 KiB.
1125+
# The plausibility check on the recorded size must accept them.
1126+
size = 64 * _BLOCK_SIZE_MAX # 8 MiB
1127+
frame = _frame(size, [_rle_block(ord('x'), _BLOCK_SIZE_MAX)] * 63
1128+
+ [_rle_block(ord('x'), _BLOCK_SIZE_MAX, last=True)])
1129+
self.assertEqual(len(frame), 14 + 64 * 4)
1130+
self.assertEqual(decompress(frame), b'x' * size)
1131+
self.assertAllocatedAbout(_peak_allocation(decompress, frame), size)
1132+
1133+
def test_output_allocated_once_with_dictionary(self):
1134+
data = b''.join(SAMPLES) * 50
1135+
frame = compress(data, zstd_dict=TRAINED_DICT)
1136+
self.assertEqual(get_frame_info(frame).decompressed_size, len(data))
1137+
self.assertEqual(decompress(frame, zstd_dict=TRAINED_DICT), data)
1138+
self.assertAllocatedAbout(
1139+
_peak_allocation(decompress, frame, zstd_dict=TRAINED_DICT),
1140+
len(data))
1141+
1142+
def test_output_allocated_per_frame(self):
1143+
data1 = bytes(range(256)) * (8 * _1K) # 2 MiB
1144+
data2 = b'second frame' * 1000
1145+
frame1, frame2 = compress(data1), compress(data2)
1146+
d = ZstdDecompressor()
1147+
self.assertEqual(d.decompress(frame1 + frame2), data1)
1148+
self.assertEqual(d.unused_data, frame2)
1149+
self.assertEqual(decompress(frame1 + frame2), data1 + data2)
1150+
self.assertAllocatedAbout(
1151+
_peak_allocation(ZstdDecompressor().decompress, frame1 + frame2),
1152+
len(data1))
1153+
1154+
def test_output_allocated_once_after_empty_input(self):
1155+
data = bytes(range(256)) * (8 * _1K) # 2 MiB
1156+
frame = compress(data)
1157+
def decompress_after_empty_input():
1158+
d = ZstdDecompressor()
1159+
self.assertEqual(d.decompress(b''), b'')
1160+
return d.decompress(frame)
1161+
self.assertEqual(decompress_after_empty_input(), data)
1162+
self.assertAllocatedAbout(
1163+
_peak_allocation(decompress_after_empty_input), len(data))
1164+
1165+
def test_output_allocated_once_each_frame(self):
1166+
# decompress() feeds every frame to its decompressor whole.
1167+
data = bytes(range(256)) * (8 * _1K) # 2 MiB
1168+
frame = compress(data)
1169+
small = compress(b'small frame')
1170+
skippable = (0x184D2A50).to_bytes(4, 'little') + (4).to_bytes(4, 'little')
1171+
skippable += b'skip'
1172+
for frames, expected in (([small, frame], b'small frame' + data),
1173+
([skippable, frame], data),
1174+
([frame, frame], data + data)):
1175+
with self.subTest(frames=[len(f) for f in frames]):
1176+
stream = b''.join(frames)
1177+
self.assertEqual(decompress(stream), expected)
1178+
# The output of each frame, and the joined result.
1179+
self.assertAllocatedAbout(
1180+
_peak_allocation(decompress, stream), 2 * len(expected))
1181+
1182+
def test_max_length_limits_allocation(self):
1183+
size = 64 * _BLOCK_SIZE_MAX # 8 MiB
1184+
frame = compress(b'x' * size)
1185+
d = ZstdDecompressor()
1186+
self.assertEqual(d.decompress(frame, 1000), b'x' * 1000)
1187+
self.assertFalse(d.eof)
1188+
self.assertLess(
1189+
_peak_allocation(ZstdDecompressor().decompress, frame, 1000),
1190+
self.NOISE)
1191+
1192+
def test_untrusted_content_size(self):
1193+
# 27 bytes cannot decode to more than 6 blocks.
1194+
frame = _frame(self.CLAIM, [_raw_block(b'0123456789', last=True)])
1195+
self.assertRaises(ZstdError, decompress, frame)
1196+
self.assertRaises(ZstdError, ZstdDecompressor().decompress, frame)
1197+
self.assertLess(_peak_allocation(decompress, frame), self.NOISE)
1198+
self.assertLess(
1199+
_peak_allocation(ZstdDecompressor().decompress, frame), self.NOISE)
1200+
1201+
def test_untrusted_content_size_huge(self):
1202+
for claim in (2**40, 2**62, 2**63 - 1):
1203+
with self.subTest(claim=claim):
1204+
frame = _frame(claim, [_raw_block(b'0123456789', last=True)])
1205+
# A ZstdError, not a MemoryError or OverflowError
1206+
self.assertRaises(ZstdError, decompress, frame)
1207+
self.assertLess(_peak_allocation(decompress, frame), self.NOISE)
1208+
1209+
def test_untrusted_content_size_trailing_data(self):
1210+
# Only the frame itself vouches for its size, not the data after it.
1211+
frame = _frame(self.CLAIM, [_raw_block(b'0123456789', last=True)])
1212+
blocks = self.CLAIM // _BLOCK_SIZE_MAX
1213+
valid = _frame(self.CLAIM, [_rle_block(ord('x'), _BLOCK_SIZE_MAX)]
1214+
* (blocks - 1)
1215+
+ [_rle_block(ord('x'), _BLOCK_SIZE_MAX,
1216+
last=True)])
1217+
for trailing in (bytes(64 * _1K), valid):
1218+
with self.subTest(trailing=len(trailing)):
1219+
data = frame + trailing
1220+
self.assertRaises(ZstdError, decompress, data)
1221+
self.assertRaises(ZstdError, ZstdDecompressor().decompress, data)
1222+
self.assertLess(_peak_allocation(decompress, data), self.NOISE)
1223+
self.assertLess(
1224+
_peak_allocation(ZstdDecompressor().decompress, data),
1225+
self.NOISE)
1226+
1227+
def test_untrusted_content_size_partial_frame(self):
1228+
# Until the whole frame is in, nothing vouches for the recorded size.
1229+
blocks = [_raw_block(bytes([i]) * _1K) for i in range(64)]
1230+
partial = _frame(self.CLAIM, blocks) # no last block
1231+
d = ZstdDecompressor()
1232+
self.assertEqual(d.decompress(partial),
1233+
b''.join(bytes([i]) * _1K for i in range(64)))
1234+
self.assertFalse(d.eof)
1235+
self.assertTrue(d.needs_input)
1236+
self.assertLess(
1237+
_peak_allocation(ZstdDecompressor().decompress, partial), self.NOISE)
1238+
1239+
def test_window_log_max(self):
1240+
# A frame that needs a larger window than allowed is refused, also
1241+
# when its output is allocated at once. (zstd doesn't check the
1242+
# window of a frame whose output fits the first, 32 KiB, block of the
1243+
# output buffer.)
1244+
window_log_max = DecompressionParameter.window_log_max
1245+
size = 64 * _1K
1246+
blocks = [_rle_block(ord('x'), size, last=True)]
1247+
frame = _frame(size, blocks, window_log=28)
1248+
for options in (None, {window_log_max: 0}): # default: 27
1249+
with self.subTest(options=options):
1250+
self.assertRaises(ZstdError, decompress, frame,
1251+
options=options)
1252+
self.assertRaises(ZstdError,
1253+
ZstdDecompressor(options=options).decompress,
1254+
frame)
1255+
self.assertEqual(decompress(frame, options={window_log_max: 28}),
1256+
b'x' * size)
1257+
frame = _frame(size, blocks, window_log=20)
1258+
options = {window_log_max: 19}
1259+
self.assertRaises(ZstdError, decompress, frame, options=options)
1260+
self.assertRaises(ZstdError,
1261+
ZstdDecompressor(options=options).decompress, frame)
1262+
self.assertEqual(decompress(frame, options={window_log_max: 20}),
1263+
b'x' * size)
1264+
# A single-segment frame needs a window of its content size.
1265+
frame = compress(b'x' * _1M)
1266+
self.assertRaises(ZstdError, decompress, frame,
1267+
options={window_log_max: 19})
1268+
self.assertEqual(decompress(frame, options={window_log_max: 20}),
1269+
b'x' * _1M)
1270+
1271+
def test_content_size_too_small(self):
1272+
# The output must not be cut off at the recorded size.
1273+
frame = _frame(_BLOCK_SIZE_MAX,
1274+
[_rle_block(ord('x'), _BLOCK_SIZE_MAX),
1275+
_rle_block(ord('y'), _BLOCK_SIZE_MAX, last=True)])
1276+
self.assertRaises(ZstdError, decompress, frame)
1277+
self.assertRaises(ZstdError, ZstdDecompressor().decompress, frame)
1278+
1279+
def test_content_size_too_large(self):
1280+
frame = _frame(2 * _BLOCK_SIZE_MAX,
1281+
[_rle_block(ord('x'), _BLOCK_SIZE_MAX, last=True)])
1282+
self.assertRaises(ZstdError, decompress, frame)
1283+
self.assertRaises(ZstdError, ZstdDecompressor().decompress, frame)
1284+
1285+
10561286
class DecompressorFlagsTestCase(unittest.TestCase):
10571287

10581288
@classmethod

0 commit comments

Comments
 (0)