Miri detects UB on tests when using `--features global`

[MortenLohne]

MIRIFLAGS="-Zmiri-tree-borrows" cargo miri test --features global immediately detects UB:

error: Undefined Behavior: read access through <52087> at alloc597[0x24a8] is forbidden
    --> /home/morten/dev/dlmalloc-rs/src/dlmalloc.rs:1725:9
     |
1725 |         (*me).head & !FLAG_BITS
     |         ^^^^^^^^^^ Undefined Behavior occurred here
     |
     = help: this indicates a potential bug in the program: it performed an invalid operation, but the Tree Borrows rules it violated are still experimental
     = help: the accessed tag <52087> has state Disabled which forbids this child read access
     = help: the accessed tag <52087> was created here, in the initial state Reserved
help: the accessed tag <52087> later transitioned to Disabled due to a foreign write access at offsets [0x24a8..0x24b0]
    --> /home/morten/dev/dlmalloc-rs/src/dlmalloc.rs:1745:9
     |
1745 |         (*me).head &= !PINUSE;
     |         ^^^^^^^^^^^^^^^^^^^^^
     = help: this transition corresponds to a loss of read and write permissions

Running miri with stacked borrows also reports UB. It looks like the tests have never been run under miri with --features global enabled before, which makes most of the tests run with the platform's default allocator instead. I have made #52 to address this.

I discovered this when investigating rust-lang/rust#144199, although this may be a different issue.

[alexcrichton]

I've gotten a bit further with #53 but I'm at a loss of how to fix the next bit. I'm never the best at interpreting Miri errors but to the best of my knowledge what's happening is that dlmalloc is, when freeing a pointer p, going left and right of p to adjacent "chunks" and manipulating flags/bits for those chunks. Afterwards when freeing the adjacent chunk (if it was still allocated) dlmalloc will inspect/write its own flags. That means that the pointer to modify a chunk's flags are derived either from adjacent chunks or the chunk itself, and that overlap in how the pointers are derived I think is what's causing a violation here.

I'm certainly no expert in dlmalloc itself so I'm not sure how to fix this. Argubaly what needs to happen is that chunk pointers all need to be derived from some "master pointer" for a chunk (maybe from the system allocator?) but I don't know how that would be inserted.

[MortenLohne]

I am definitely no expert (I first heard of dlmalloc last week), but is it possible that splitting head into separate machine words would work fix this problem? One word for the size itself, and another one for the flags in the lower 3 bits? The memory accesses in the error message are (semantically speaking) operating on disjoint bits in head, but of course in practice we have to go through the same bytes to access them, and miri complains.

Adding 4 bytes to the size of Chunk is of course unfortunate.

[alexcrichton]

Alas I'm not sure. I would not be confident modifying dlmalloc's in-memory layout for sure, but additionally I don't know if that would fix the Miri issue. Most of the time the only way I know if it fixes something is to implement all of it and see what happens, I find it difficult to predict.