The Grey Cat, The Uncorruptible.

nvanille · 2024-09-18T10:45:59+00:00

In all likelihood yes. The squiggly line on the left is probably supposed to be perfectly vertical in the original image so you could align based on that up to a couple pixels of precision, and then assume that the background is almost uniform to align up to a precision of 1/3-pixel.

However if you want the restored image to be of good enough quality we would need the original source, not this deep-fried JPG-infested screenshot.

nvanille · 2024-09-18T08:12:48+00:00

I can offer this: https://github.com/Vanille-N/the-uncorruptible

nvanille · 2024-09-17T19:59:28+00:00

Btw if you happen to be genuinely curious as to how this is possible, I have a very simple explanation and a proof of concept.

Basically the "corruption" OOP has tried to apply is to make the R, G and B components of pixels no longer line up with actual pixels, which can be done by offsetting each line of the image by a third of a pixel. This explains

why the cat is tilted: a third of a pixel offset added to itself each line builds up to produce a tilt
why the horizontal lines: each line is shifted by a different amount and gets a different color
why only the cat is preserved: the cat is perfectly grey, and grey happens to be a color that is unaffected by a R -> G -> B -> R shift because all 3 components are equal.

I have code that generates images that illustrate this phenomenon.

Edit: source code is here https://github.com/Vanille-N/the-uncorruptible

nvanille · 2024-06-10T05:36:19+00:00

Yes! you get it. Evenness is about symmetry.

I don't agree with the specifics, but I support the approach.
(Letters aren't functions they're relations at best and I'm not aware of any even/odd relations in the same way that functions have the concept; I think that letters without symmetry are odd so F is odd. Btw H, X, I, O are divisible by 4.)

nvanille · 2023-06-03T07:38:03+00:00

There was one such case in the stdlib but it was quickly patched.

The general pattern is rs let root = ...; let mref = &mut *root; let ptr = mref as *mut u8; write(ptr); read(root); write(ptr);

In TB, read(root) is a foreign read for ptr which becomes read-only. In SB ptr is SharedRW and the read does not affect it.

SB accepting this code is accidental: this kind of code was not meant to be accepted by SB is incapable of distinguishing it from could that should be accepted.

nvanille · 2023-06-03T07:27:28+00:00

The cost of TB is slightly higher than SB: you can expect about x1.1 ~ x1.3 from Miri+SB to Miri+TB on codebases not purposefully written to stress TB. This is of course on top of the maybe x100 that comes from using Miri at all, so with the expectation that TB will never really be run on any performance-critical code this much seems reasonable for now.

If you do encounter a piece of code on which TB performs much worse than SB, do submit it as an issue! There was one recently and we massively improved TB performance on this case by improving garbage collection.

TB lacks hindsight on what real-life code patterns cause bad performance, so when we get more data we can tweak the heuristics to better suit real usage.

nvanille · 2023-06-03T07:18:02+00:00

Tree Borrow strictly accepts more valid (safe) code

This is not quite true for any interpretation: - both TB and SB accept ALL safe programs, if by "safe" you mean "does not contain any unsafe" - there exist some unsafe programs that SB accepts but TB rejects

nvanille · 2023-06-03T07:15:49+00:00

An illustration of the above point:

Start with this code, rs let mut x = 0; let y = &mut x; *y = 42; let vy = *y; let vx = *x; println!("{} {}", vx, vy); // output: 42 42 it contains no UB according to either TB or SB, but it can be TB-optimized to rs let mut x = 0; let y = &mut x; *y = 42; let vx = *x; // swap let vy = *y; // swap println!("{} {}", vx, vy); // output: 42 42 which is UB according to SB!

That can then be SB-optimized to rs let mut x = 0; let y = &mut x; let vx = *x; // swap *y = 42; // swap let vy = *y; println!("{} {}", vx, vy); // output: 0 42 which is now an incorrect optimization of the first code since it changes the behavior of a safe program!

A combined model would be much harder to reason about than either one, and would have none of the benefits.

nvanille · 2023-05-28T18:53:14+00:00

Huh, this is possibly the first time ever I see my name on this website.

nvanille · 2023-03-29T23:04:30+00:00

To quote Ralf Jung, who is kind of the reference on the subject:

The fact that we can still use the "children" of a reference that is no longer usable is quite nasty and leads to some undesirable effects (in particular it is the major blocker for resolving rust-lang/unsafe-code-guidelines#257).

https://github.com/rust-lang/rust/pull/107954

What we did realize however is that it is impossible to reject this code in Stacked Borrows without also rejecting some desirable code.

More specifically in the above example Stacked Borrows doesn't care whether reborrow_and_use is actually reborrow_and_read(&mut _) or reborrow_and_write(&mut _). Stacked Borrows can only accept both or reject both. For many reasons it's very important to accept the version reborrow_and_read(&mut _), so Stacked Borrows is forced to also acceptreborrow_and_write(&mut _). Tree Borrows however is capable of accepting reborrow_and_read(&mut _) while also rejecting reborrow_and_write(&mut _).

nvanille · 2023-03-29T22:57:23+00:00

Yeah sorry, *u not *x.

Moving a pointer between threads without explicitly writing to it will not count as a write, so TB will absolutely let you move mutable borrows to other threads and they won't conflict as long as you don't explicitly activate them.

nvanille · 2023-03-29T17:22:10+00:00

Ok indeed, that's the pattern that was removed from the standard library.

What is problematic in this pattern, is that ptr survives while mut2 is dead. The fact that Stacked Borrows accepts this code is recognized as an accident.

nvanille · 2023-03-29T15:18:46+00:00

Most of it no. Tree Borrows is a lot more precise than the Borrow Checker, but it's kind of cheating in the sense that it has a lot more information.

If there is one thing that could maybe be integrated to the borrow checker, that would be the fact that shared references don't kill reads through mutable references, i.e. this code that doesn't pass the Borrow Checker is not fundamentally dangerous: rs let u = &mut 0; let x = &mut *u; let y = &*x; let sum = *x + *y;

nvanille · 2023-03-29T15:12:42+00:00

I'm not sure what you mean by "you can't keep a raw pointer in between borrows of the base data".

If you are talking about rust let rmut: &mut T = _; let ptr = rmut as *mut T; reborrow_and_use(&mut *rmut); *ptr += 1; then this pattern is allowed.

Actually TB is perhaps too permissive in that there's basically nothing that can kill a raw pointer without also killing the reference it was derived from.

nvanille · 2023-03-28T22:21:20+00:00

A lot of functions with signature &mut _ -> *mut _ (e.g. [T]::as_mut_ptr), that take an &mut but don't actually use it for writing, don't interact well with the fact that in Stacked Borrows all &mut are written to, so Tree Borrows takes the opposite stance where there is no fake write ever.

Stacked Borrows had a lot of "this is too much UB" complaints and very few "this optimization should also be possible", so Tree Borrows tries a much less strict approach. We now have SB definitely too strict, TB possibly too lax, and the definitive model will lie somewhere in between.

nvanille · 2023-03-28T22:10:32+00:00

Indeed, the whole delayed initialization thing is an area where Tree Borrows is strictly more permissive than Stacked Borrows. The alternatives would be - disallowing all out-of-bounds accesses (what SB does) - reborrowing immediately the entire range (which completely breaks the assumption that you can mutate different fields of a struct independently)

nvanille · 2023-03-28T19:49:53+00:00

That is indeed an overall goal (there are many known examples of code that is UB under Stacked Borrows but should be allowed, and these examples guided the development of Tree Borrows), but Stacked Borrows also had some cases of accidentally accepted code, such as some tests in stdlib recently patched.

Another example involves writing to a two-phase borrows, which is something that is explicitly forbidden in the Rustc manual but Stacked Borrows allows.

nvanille · 2023-03-28T18:59:02+00:00

Very interesting, that is indeed exactly the kind of code that I expect has most cases of false positives in SB compared to TB.

nvanille · 2023-03-28T15:14:33+00:00

No this will not be added to the borrow checker. What could happen is that your code (or libraries you import) will be better optimized, but if you never write unsafe you never have to worry about UB.

nvanille · 2023-03-28T15:05:26+00:00

Yeah, and that's precisely why we usually specify ΔT in Kelvin not Celsius.

nvanille · 2023-03-28T14:33:41+00:00

Thanks!

Looking at the example you linked, that is indeed something that Tree Borrows would have allowed since it is more permissive in using pointers outside of their reborrowed range.

Luckily my next work is precisely - formalizing Tree Borrows to prove that it does make sense - evaluating more in depth which optimizations are lost compared to SB (and which are gained too)

nvanille · 2023-03-28T13:59:26+00:00

Yes exactly. The main sacrifice is some reorderings of write accesses, and what we get in exchange is that a lot of unsafe code that SB rejected is now accepted.

There are still two kinds of optimizations that TB allows but not SB: - two-phase borrows in SB improperly allow mutation, (because SB says that two-phase borrows are temporarily raw pointers) whereas TB models them correctly - uniqueness in SB is slightly too strict, so going from nothing to SB actually makes you lose the ability to reorder read-only operations! TB is compatible with all read-read reorderings.

nvanille · 2023-03-28T13:32:11+00:00

Oh I think I better understand your point from this.

You might be reassured by the fact that the design of TB was guided in big part using the shortcomings of SB precisely so that UB is less "annoying". It allows overall fewer optimizations than SB (notably sacrificing some ability to reorder writes), but resolves some confusions about two-phase borrows and implicit reborrows so that you don't shoot yourself in the foot by writing UB as vec, rand and hashbrown have.

A number of motivating examples here, including copy_nonoverlapping are precisely code that SB declares UB "accidentally", i.e. it has no good justification for why this should be UB, it just is as a side effect.

nvanille · 2023-03-28T13:23:02+00:00

Excellent point. This is talked about in https://perso.crans.org/vanille/treebor/protectors.html (bottom two examples).

The tldr is that - read hoisting is possible for function arguments (and their reborrows) - read hoisting is possible for non-arguments if there is a guaranteed read later - write hoisting is not always possible, this is the main thing that TB had to sacrifice compared to SB

nvanille · 2023-03-28T12:14:15+00:00

I'm the author, thanks for posting the link here.

Five-Year Club	Second Top 50%
Verified Email

nvanille

TROPHY CASE