UB in bitslice code #14
Comments
|
I believe the issue is that the Index implementations do not correctly bound the slice's len in the RangeFrom implementation. |
|
For more information: This crate uses the type struct BitSlice([u8]);which is returned by indexing methods as The simplest fix is to have |
|
Oh, you actually took a much deeper look than I did. Awesome! |
|
Thank you for reporting this! I've fixed the issue here #15 |
|
@arrsingh This does not fix the issue, it only evades the debug UB check. It is not allowed to have a reference of a slice which goes beyond the original allocation at all, but one obvious sign of this is a slice whose length is larger than |
|
This change ensures that the MSB of the len passed to from_raw_parts(...) will always be zero and hence the max value of len will be less than (2^63)-1. So it falls within the constraint specified in the documentation that len should never exceed I will stipulate that technically the len passed in will be greater than the underlying allocation and goes against the intent of the UB check. If one were to try and dereference the underlying pointer using the len as passed in then yes that behavior would be undefined. However, so long as the pointer is dereferenced only with the provided slice implementation in practice the length won't actually be accessed. Is this implementation a hack of the len field? Absolutely. |
|
No, this is a violation of rust UB rules as they are currently understood. The length field must not be more than isize::MAX but that is not the only constraint. Have you run the code through Miri? It is better at checking the more expensive UB rules. Here is a simplified example, where we just create a slice which has a size which is too large for its allocation (but still less than |
|
The fundamental issue here is that slices are double word pointers (64 bit pointer + 64 bit length = 128 bits on a 64 bit machine). Implementing a bitslice means that we need an additional 3 bits to store the offset of the first bit into the start byte. We could create a specific structure with a u8 offset in addition to the ptr and len, but that won't work because we can't transmute
Option 2 is the simplest and it works because while theoretically the len value can be dereferenced, in practice however, its difficult to dereference that pointer without going through the code that packs / unpacks it. For example, Someday I might get around to implementing the slice by wrapping a ZST rather than a |
|
I have to admit that I am not invested enough in this project or issue to write a fix, and if you want to ignore UB which is of a sufficiently theoretical nature and which does not seem to manifest as miscompilation in practice, that's your prerogative (I wouldn't blame you at all for doing that, I've done it myself from time to time). But I would suggest in that case either leaving this issue open, or putting a comment in the code acknowledging that you know it is UB and consider it okay in practice (and then if it blows up later it will at least be easier to track down). Separately, if you would like to defend option (2) as a legitimate technique and you think the rust opsem team (of which I am a member) is overstepping their bounds in declaring this UB, please bring it up on https://github.com/rust-lang/unsafe-code-guidelines/issues or https://rust-lang.zulipchat.com/#narrow/stream/136281-t-opsem . Regarding potential fixes: (1) is an interesting idea, I hadn't considered that. It doesn't run afoul of reference rules since the ZST slice encompasses 0 bytes, and while it may violate strict subobject rules (i.e. using a reference to access memory outside its declared length), those rules seem likely to be dropped anyway and are not supported in newer drafts of the memory model. (3) will definitely work but it comes at an obvious ergonomic cost. There is also option (4) of making |
|
Hacking the offset into the length is definitely not the best approach and I wouldn't recommend this in production. Its definitely a hack to make things work for now. I really should implement it by wrapping a ZST but for now its more work than I have time for. I'll leave this issue open as a reminder and once I get around to re implementing this I'll post an update here. |
This collections crate fails to uphold the required invariants for callers of
slice::from_raw_partsThe text was updated successfully, but these errors were encountered: