tidb_query_vec_executors: Fixed stack-borrowing undefined-behavior #7709

brson · 2020-04-30T00:32:24Z

What problem does this PR solve?

This fixes undefined behavior in tidb_query_vec_executors. Miri reports a stacked borrowing error as described below.

Note that stacked borrowing is a way to model Rust's use of unsafe pointers, but is not officially part of Rust's memory model. Thus, this is not truly undefined behavior today, but could be eventually.

I don't understand the stacked borrowing rules enough to understand why the
existing code is a violation. It is creating a mutable unsafe pointer; then
taking some immutable borrows to the same data while doing nothing with that
pointer; then later using the pointer.

Simply moving the creation of the unsafe pointer to immediately before it
is used removes the error.

cc @RalfJung not sure if you like being tagged on miri stacked borrow reports. If you have time though maybe you could explain what's going on here.

Found with miri, which reports:

error: Undefined Behavior: trying to reborrow for SharedReadOnly, but parent tag <1121039> does not have an appropriate item in the borrow sta
ck
   --> components/tidb_query_vec_executors/src/slow_hash_aggr_executor.rs:281:32
    |
281 |             let offset_begin = self.group_key_buffer.len();
    |                                ^^^^^^^^^^^^^^^^^^^^^ trying to reborrow for SharedReadOnly, but parent tag <1121039> does not have an ap
propriate item in the borrow stack
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
    = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information

Signed-off-by: Brian Anderson andersrb@gmail.com

I don't understand the stacked borrowing rules enough to understand why the existing code is a violation. It is creating a mutable unsafe pointer; then taking some immutable borrows to the same data while doing nothing with that pointer; then later using the pointer. Simply moving the creation of the unsafe pointer to immediately before it is used removes the error. Found with miri, which reports: ``` error: Undefined Behavior: trying to reborrow for SharedReadOnly, but parent tag <1121039> does not have an appropriate item in the borrow sta ck --> components/tidb_query_vec_executors/src/slow_hash_aggr_executor.rs:281:32 | 281 | let offset_begin = self.group_key_buffer.len(); | ^^^^^^^^^^^^^^^^^^^^^ trying to reborrow for SharedReadOnly, but parent tag <1121039> does not have an ap propriate item in the borrow stack | = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information ``` Signed-off-by: Brian Anderson <andersrb@gmail.com>

nrc

I believe it is UB because the old line 280 takes a reference to self.group_key_buffer, but then inside the for loop self.group_key_buffer is mutated. This is equivalent to holding two &mut pointers, which is of course not allowed. This is only possible at all because the into creates a NonNull, which is basically a *mut pointer. It is not unsafe to have multiple *mut pointers as long as they are not dereferenced, but I guess miri is still treating it as UB.

Anyway, the fix LGTM

breezewish

Thanks for both @nrc @brson !

The code is trying to inserting string keys to a HashMap. Strings are generated dynamically. To avoid allocating memory for each string, strings are appended to a memory buffer first. And then, the pointer to the buffer, as well as the appending offset are inserted to the HashMap instead.

In this pattern, a non-mut reference (however implemented by using NonNull) to the buffer is always kept and stored in HashMap, while the buffer is meanwhile mutated to append more strings.

nrc · 2020-04-30T05:16:36Z

/merge

sre-bot · 2020-04-30T05:16:40Z

Your auto merge job has been accepted, waiting for:

7705

sre-bot · 2020-04-30T05:36:29Z

/run-all-tests

sre-bot · 2020-04-30T05:51:27Z

@brson merge failed.

nrc · 2020-04-30T06:14:30Z

/merge

sre-bot · 2020-04-30T06:14:36Z

/run-all-tests

sre-bot · 2020-04-30T06:18:26Z

@brson merge failed.

breezewish · 2020-04-30T07:37:45Z

/run-cherry-picker

…ikv#7709) Signed-off-by: Brian Anderson <andersrb@gmail.com>

sre-bot · 2020-04-30T07:39:09Z

cherry pick to release-4.0 in PR #7714

RalfJung · 2020-04-30T08:35:19Z

I believe it is UB because the old line 280 takes a reference to self.group_key_buffer, but then inside the for loop self.group_key_buffer is mutated. This is equivalent to holding two &mut pointers, which is of course not allowed. This is only possible at all because the into creates a NonNull, which is basically a *mut pointer. It is not unsafe to have multiple *mut pointers as long as they are not dereferenced, but I guess miri is still treating it as UB.

self.group_key_buffer is not a *mut though, is it? I have a hard time understanding what the code does here, but from your summary it sounds like you have a *mut and an &mut and both are being used. That is definitely UB because &mut must not have any aliases being used.

If you truly have two *mut, then indeed they can alias and both be used, and Miri should not complain about that.

(Actually isn't buffer_ptr a *const? It is created from a shared reference, so it must not be used for mutation, unless there are UnsafeCell.)

nrc · 2020-04-30T08:41:23Z

Thanks @RalfJung !

self.group_key_buffer is Box<Vec<u8>>. self is &mut, so self.group_key_buffer is being mutated via an implicit &mut.

buffer_ptr is a NonNull, which aiui is equivalent to *mut for this sort of thing (although I think you are right that there should be an UnsafeCell somewhere).

RalfJung · 2020-04-30T08:54:10Z

buffer_ptr is a NonNull, which aiui is equivalent to *mut for this sort of thing

It is, but you are creating it from a shared reference it looks like, which means you must not use it for mutation.

*(&x as *const _ as *mut _) = 5 is UB.

OTOH, Miri catches those bugs, so I am not entirely sure what is actually happening here. Unfortunately the into() makes it impossible to see which types are involved.

(although I think you are right that there should be an UnsafeCell somewhere).

UnsafeCell is only needed if you truly want to mutate data behind a shared reference. If that is not what you want, then just create your NonNull from an &mut.

RalfJung · 2020-04-30T08:59:20Z

buffer_ptr is a NonNull, which aiui is equivalent to *mut for this sort of thing

I should clarify: Raw pointers, once created, do not care about their type.

But how you create a raw pointer initially (from a safe reference) matters. Casting a reference to *const is very different from casting a reference to *mut. The former creates a raw pointer that is immutable like shared references are, the latter creates a raw pointer that may be used for mutation.

NonNull::from(&x) creates a read-only raw pointer (modulo interior mutability, aka UnsafeCell). This example demonstrates the UB. The UB arises because this takes a shared reference, casts it around a bit, and then writes to it -- whereas the aliasing rules state that you must under no circumstances use shared references for mutation (outside UnsafeCell).

nrc · 2020-04-30T22:15:06Z

Thanks @RalfJung !

…ikv#7709) Signed-off-by: Brian Anderson <andersrb@gmail.com>

…7709) (#7714) Signed-off-by: Brian Anderson <andersrb@gmail.com> Co-authored-by: Brian Anderson <andersrb@gmail.com>

brson requested review from breezewish and sticnarf April 30, 2020 00:32

nrc approved these changes Apr 30, 2020

View reviewed changes

breezewish approved these changes Apr 30, 2020

View reviewed changes

Merge branch 'master' into vec-exec-ub

9ce05ff

sre-bot added the status/can-merge Indicates a PR has been approved by a committer. label Apr 30, 2020

Merge branch 'master' into vec-exec-ub

f07201d

breezewish merged commit 9f1a97a into tikv:master Apr 30, 2020

breezewish added the needs-cherry-pick-release-4.0 Type: Need cherry pick to release 4.0 label Apr 30, 2020

sre-bot pushed a commit to sre-bot/tikv that referenced this pull request Apr 30, 2020

tidb_query_vec_executors: Fixed stack-borrowing undefined-behavior (t…

0c4461e

…ikv#7709) Signed-off-by: Brian Anderson <andersrb@gmail.com>

sre-bot mentioned this pull request Apr 30, 2020

tidb_query_vec_executors: Fixed stack-borrowing undefined-behavior (#7709) #7714

Merged

c1ay pushed a commit to c1ay/tikv that referenced this pull request May 9, 2020

tidb_query_vec_executors: Fixed stack-borrowing undefined-behavior (t…

b00adbc

…ikv#7709) Signed-off-by: Brian Anderson <andersrb@gmail.com>

brson added a commit to brson/tikv that referenced this pull request May 10, 2020

tidb_query_vec_executors: Fixed stack-borrowing undefined-behavior (t…

f8593b9

…ikv#7709) Signed-off-by: Brian Anderson <andersrb@gmail.com>

MyonKeminta pushed a commit that referenced this pull request May 11, 2020

tidb_query_vec_executors: Fixed stack-borrowing undefined-behavior (#…

19690cb

…7709) (#7714) Signed-off-by: Brian Anderson <andersrb@gmail.com> Co-authored-by: Brian Anderson <andersrb@gmail.com>

tidb_query_vec_executors: Fixed stack-borrowing undefined-behavior #7709

tidb_query_vec_executors: Fixed stack-borrowing undefined-behavior #7709

Uh oh!

Conversation

brson commented Apr 30, 2020

What problem does this PR solve?

Uh oh!

nrc left a comment

Choose a reason for hiding this comment

Uh oh!

breezewish left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

nrc commented Apr 30, 2020

Uh oh!

sre-bot commented Apr 30, 2020

Uh oh!

sre-bot commented Apr 30, 2020

Uh oh!

sre-bot commented Apr 30, 2020

Uh oh!

nrc commented Apr 30, 2020

Uh oh!

sre-bot commented Apr 30, 2020

Uh oh!

sre-bot commented Apr 30, 2020

Uh oh!

breezewish commented Apr 30, 2020

Uh oh!

sre-bot commented Apr 30, 2020

Uh oh!

RalfJung commented Apr 30, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

nrc commented Apr 30, 2020

Uh oh!

RalfJung commented Apr 30, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

RalfJung commented Apr 30, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

nrc commented Apr 30, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

breezewish left a comment •

edited

Loading

RalfJung commented Apr 30, 2020 •

edited

Loading

RalfJung commented Apr 30, 2020 •

edited

Loading

RalfJung commented Apr 30, 2020 •

edited

Loading