Provide a `count`-like combinator, without preallocation

[chifflier]

• Rust version : rustc 1.56.1 (59eed8a2a 2021-11-01)
• nom version : 7.1.0
• nom compilation features used: default

Description

Currently, count uses Vec::with_capacity to preallocates the Vec (https://github.com/Geal/nom/blob/7.0.0/src/multi/mod.rs#L537). While this is best for performance, this makes the count combinator very fragile when using an untrusted count value: any large value will result in a immediate error (fuzzers love the count combinator!).

I don't know if it's possible to check the allocation in Vec (stable API does not seem to allow it :/ ), but maybe adding an upper bound in a new combinator (count_max) could be a workaround?

Test case

Example test case:

    #[test]
    fn count_oom() {

        let input: &[u8] = b"0123456789abcdef";

        let res: IResult<_, _, ()> = count(be_u32, 0xffff_ffff as usize)(input);
        assert!(res.is_err());
    }

Output (debug):

running 1 test
memory allocation of 17179869180 bytes failed
error: test failed, to rerun pass '--lib'

[chifflier]

Additional notes:

• the current preallocation is not exact anyway, since it allocates count bytes, not elements
• not preallocating is a (weak) workaround. Allocation can still fail in some cases
• using fold_many_m_n with m == n is a working workaround, but quite verbose and inelegant

[jkugelman]

I submitted PR #1545 to clamp Vec::with_capacity to 64KiB. This should fix the issue without necessitating a new combinator. What do you think?

[Nemo157]

• the current preallocation is not exact anyway, since it allocates count bytes, not elements

Vec::with_capacity is measured in elements, not bytes. So also #1545 is clamping the allocation to 65536 elements rather than 64KiB (probably only really relevant if your element type is at least a few hundred bytes).

[jkugelman]

Vec::with_capacity is measured in elements, not bytes. So also #1545 is clamping the allocation to 65536 elements rather than 64KiB (probably only really relevant if your element type is at least a few hundred bytes).

Good catch. I submitted https://github.com/Geal/nom/pull/1549 to fix this.