Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Guard size <= 1 in binary_fuse8_allocate as the current behaviour is unsafe. #26

Closed
slimsag opened this issue Aug 21, 2021 · 6 comments
Closed
Labels
bug Something isn't working

Comments

@slimsag
Copy link
Contributor

slimsag commented Aug 21, 2021

I've noticed with very small input sizes (0, 1, 10, 100) that binary_fuse8_allocate sometimes relies on some.. questionable behavior.

For example, if called with size=0, filter->Fingerprints is ultimately allocated with filter->ArrayLength = 786432 (768 KiB), which seems high given a filter size of zero.

With size=1, sizeFactor ends up being INFINITY, which makes:

uint32_t capacity = (uint32_t)(round((double)size * sizeFactor));

result in effectively:

uint32_t capacity = (uint32_t)(round((double)0 * INFINITY)); 

https://godbolt.org/z/7vqY9ofY1

or more simply:

uint32_t capacity = (uint32_t)((double)INFINITY); 

I think this cast may be undefined behavior, as in GCC this results in -1 while in clang it results in an undefined value:
https://godbolt.org/z/daxcT7n5K

All this to say, I think very small input sizes (specifically 0, 1, 10, 100) may fail during binary_fuse8_allocate in the worst case scenario and, in the best case scenario, allocate a perhaps larger set of fingerprints than needed.

slimsag added a commit to hexops/fastfilter that referenced this issue Aug 21, 2021
This fixes our implementation and brings it inline with the upstream C
implementation in terms of handling large sets. Note that the upstream
C implementation has some compiler-specific behavior, so we adopted
what works here (which is, respecting clang and sometimes potentially
-overallocating a bit for very small sets of keys.)

See FastFilter/xor_singleheader#26

Fixes #24

Signed-off-by: Stephen Gutekanst <stephen@hexops.com>
slimsag added a commit to hexops/fastfilter that referenced this issue Aug 21, 2021
This fixes our implementation and brings it inline with the upstream C
implementation in terms of handling large sets. Note that the upstream
C implementation has some compiler-specific behavior, so we adopted
what works here (which is, respecting clang and sometimes potentially
-overallocating a bit for very small sets of keys.)

See FastFilter/xor_singleheader#26

Fixes #24

Signed-off-by: Stephen Gutekanst <stephen@hexops.com>
@lemire lemire added the bug Something isn't working label Aug 21, 2021
@lemire
Copy link
Member

lemire commented Aug 21, 2021

The case size <= 1 should definitively be guarded. It is a bug.

I do not see a problem with size = 10. Please elaborate if you still think that there is an issue.

@lemire
Copy link
Member

lemire commented Aug 21, 2021

cc @thomasmueller

@lemire lemire changed the title binary_fuse8_allocate contains overflow logic that may not always be correct Guard size <= 1 in binary_fuse8_allocate as the current behaviour is unsafe. Aug 21, 2021
@lemire
Copy link
Member

lemire commented Aug 21, 2021

@slimsag Thanks for the report. I shall be guarding these cases.

@lemire
Copy link
Member

lemire commented Aug 21, 2021

Fixed by commit dabe365

@slimsag
Copy link
Contributor Author

slimsag commented Aug 21, 2021

Can confirm there is no issue with size=10. Thanks!

@lemire
Copy link
Member

lemire commented Aug 22, 2021

Thanks for the feedback.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

2 participants