Приводит ли чтение или запись целого 32-битного слова, даже если у нас есть только ссылка на его часть, к неопределенному поведению? - PullRequest
Новая
       48

Приводит ли чтение или запись целого 32-битного слова, даже если у нас есть только ссылка на его часть, к неопределенному поведению?

0 голосов
/ 04 мая 2018

Я пытаюсь понять, что именно позволяет модель псевдонимов и памяти Rust. В частности, меня интересует, когда доступ к памяти за пределами диапазона, на который у вас есть ссылка (на который может ссылаться другой код в том же или другом потоке), становится неопределенным поведением.

Следующие примеры все обращаются к памяти вне того, что обычно разрешено, но способами, которые были бы безопасны, если бы компилятор генерировал очевидный код сборки. Кроме того, я вижу небольшой потенциальный конфликт с оптимизацией компилятора, но они могут все еще нарушать строгие правила псевдонимов Rust или LLVM, что приводит к неопределенному поведению.

Все операции правильно выровнены и, следовательно, не могут пересекать строку кэша или границу страницы.

  1. Считайте выровненное 32-битное слово, окружающее данные, к которым мы хотим получить доступ, и отбросим части, находящиеся за пределами того, что нам разрешено читать.

    Варианты этого могут быть полезны в коде SIMD. 

    pub fn read(x: &u8) -> u8 {
    let pb = x as *const u8;
    let pw = ((pb as usize) & !3) as *const u32;
    let w = unsafe { *pw }.to_le();
    (w >> ((pb as usize) & 3) * 8) as u8
}

  2. То же, что 1, но читает 32-битное слово, используя atomic_load свойственное. 

    pub fn read_vol(x: &u8) -> u8 {
    let pb = x as *const u8;
    let pw = ((pb as usize) & !3) as *const AtomicU32;
    let w = unsafe { (&*pw).load(Ordering::Relaxed) }.to_le();
    (w >> ((pb as usize) & 3) * 8) as u8
}

  3. Замените выровненное 32-разрядное слово, содержащее значение, которое нам нужно, при использовании CAS. Он перезаписывает части вне того, к чему у нас есть доступ, и того, что уже есть, поэтому он влияет только на те части, к которым у нас есть доступ.

    Это может быть полезно для эмуляции маленьких атомных типов, используя большие. Я использовал AtomicU32 для простоты, на практике AtomicUsize является интересным. 

    pub fn write(x: &mut u8, value:u8) {
    let pb = x as *const u8;
    let atom_w = unsafe { &*(((pb as usize) & !3) as *const AtomicU32) };
    let mut old = atom_w.load(Ordering::Relaxed);
    loop {
        let shift = ((pb as usize) & 3) * 8;
        let new = u32::from_le((old.to_le() & 0xFF_u32 <<shift)|((value as u32) << shift));
        match atom_w.compare_exchange_weak(old, new, Ordering::SeqCst, Ordering::Relaxed) {
            Ok(_) => break,
            Err(x) => old = x,
        }
    }
}

1 Ответ

0 голосов
/ 09 мая 2018

Это очень интересный вопрос. На самом деле есть несколько проблем с этими функциями, что делает их необоснованными (то есть небезопасными для раскрытия) по различным формальным причинам. В то же время я не могу создать проблемное взаимодействие между этими функциями и оптимизацией компилятора.

Доступ за пределы

Я бы сказал, что все эти функции не работают, потому что они могут получить доступ к нераспределенной памяти. Каждый из них я могу вызвать с помощью &*Box::new(0u8) или &mut *Box::new(0u8), что приводит к выходам за пределы допустимого доступа, т. Е. Доступам, превышающим то, что было выделено с использованием malloc (или любого другого распределителя). Ни C, ни LLVM не разрешают такой доступ. (Я использую кучу, потому что мне проще думать о распределении там, но то же самое относится и к стеку, где каждая переменная стека на самом деле имеет свое независимое распределение.)

Конечно, ссылка на язык LLVM на самом деле не определяет, когда загрузка имеет неопределенное поведение из-за отсутствия доступа внутри объекта. Тем не менее, мы можем получить подсказку в документации getlementptr inbounds, в которой написано

Адреса в границах для выделенного объекта - это все адреса, которые указывают на объект, плюс адрес на один байт после конца.

Я вполне уверен, что наличие границ является необходимым, но недостаточным требованием для фактического использования адреса с загрузкой / хранением.

Обратите внимание, что это не зависит от того, что происходит на уровне сборки; LLVM будет выполнять оптимизацию на основе модели памяти более высокого уровня, которая рассуждает в терминах выделенных блоков (или «объектов», как их называет C) и оставаясь в пределах этих блоков. C (и Rust) не являются сборкой, и на них невозможно использовать рассуждения на основе сборки. Большую часть времени можно извлечь противоречия из рассуждений на основе сборки (см., Например, эту ошибку в LLVM для очень тонкого примера: приведение указателя на целое число и обратно равно , а не НОП). На этот раз, однако, единственные примеры, которые я могу придумать, являются довольно надуманными: например, при отображении в память ввода-вывода даже чтение из местоположения может «что-то» означать для базового оборудования, и может быть такое чтение -чувствительное место, расположенное прямо рядом с тем, которое передано в read. Но на самом деле я мало что знаю об этом типе разработки встроенных / драйверов, так что это может быть совершенно нереально.

(РЕДАКТИРОВАТЬ: я должен добавить, что я не эксперт по LLVM. Вероятно, список рассылки llvm-dev является лучшим местом для определения того, хотят ли они взять на себя обязательство разрешить такой доступ за пределы допустимого.)

Данные гонки

Существует еще одна причина, по которой некоторые из этих функций не работают: параллелизм. Вы ясно уже видели это, судя по использованию одновременных обращений.

И read, и read_vol определенно несостоятельны в семантике параллелизма C11 . Представьте, что x является первым элементом [u8], и другой поток пишет во второй элемент одновременно с выполнением read / read_vol. Наше прочтение всего 32-битного слова совпадает с записью другого потока. Это классическая «гонка данных»: два потока обращаются к одному и тому же местоположению одновременно, один доступ является записью, а другой - не атомарным. Под C11 любая гонка данных - UB, поэтому мы находимся. LLVM немного более разрешительный, поэтому, возможно, разрешены и read, и read_val, но прямо сейчас Rust заявляет, что использует модель C11 .

Также обратите внимание, что "vol" - это плохое имя (если вы подразумевали это как сокращение для "volatile") - в C атомарность не имеет ничего общего с volatile! Буквально невозможно написать правильный параллельный код при использовании volatile, а не атомарного кода. К сожалению, в Java volatile речь идет об атомарности, но это volatile совсем не то, что в C.

И, наконец, write также вводит гонку данных между атомарным чтением-изменением-обновлением и неатомарной записью в другом потоке, так что это также UB в C11. И на этот раз это также UB в LLVM: другой поток может читать из одного из дополнительных местоположений, на которые влияет write, поэтому вызов write приведет к гонке данных между нашей записью и потоком другого потока чтение. LLVM указывает, что в этом случае чтение возвращает undef. Таким образом, вызов write может обеспечить безопасный доступ к тому же местоположению в других потоках, вернуть undef и впоследствии вызвать UB.

У нас есть примеры проблем, вызванных этими функциями?

Огорчает то, что, хотя я нашел несколько причин исключить ваши функции в соответствии со спецификацией, кажется, нет веской причины, по которой эти функции исключаются! Проблемы параллелизма read и read_vol устраняются моделью LLVM (которая, однако, имеет другие проблемы, по сравнению с C11), но write недопустима в LLVM только потому, что гонки данных для чтения-записи приводят к возврату чтения undef - - и в этом случае мы знаем, что записываем то же значение, которое уже было сохранено в этих других байтах! Разве LLVM не может просто сказать, что в этом особом случае (запись уже существующего значения) чтение должно вернуть это значение? Возможно, да, но этот материал достаточно тонкий, поэтому я не удивлюсь, если это лишит законной силы некоторую неясную оптимизацию.

Более того, по крайней мере на не встроенных платформах доступ за пределы, осуществляемый read, вряд ли вызовет реальные проблемы. Я предполагаю, что можно представить семантику, которая возвращает undef при чтении байта за пределами допустимого диапазона, который гарантированно будет находиться на той же странице, что и встроенный byte. Но это все равно оставит write незаконным, и это действительно сложно: write может быть разрешено, только если память в этих других местах остается абсолютно неизменной. Там могут быть произвольные данные, хранящиеся там из других распределений, частей стекового кадра, что угодно. Так что каким-то образом формальная модель должна была бы позволить вам читать эти другие байты, не позволять вам получать что-либо путем их проверки, но также проверять, что вы не меняете байты, прежде чем записывать их обратно с помощью CAS. Я не знаю ни одной модели, которая позволила бы вам сделать это. Но я благодарю вас за то, что вы обратили мое внимание на эти неприятные случаи. Всегда приятно знать, что еще есть много вещей, которые нужно исследовать с точки зрения моделей памяти:)

Правила наложения имен в Rust

Наконец, вам, вероятно, было интересно узнать, нарушают ли эти функции какое-либо из дополнительных правил наложения имен, добавленных в Rust. Проблема в том, что мы не знаем - эти правила находятся в стадии разработки . Однако все предложения, которые я видел до сих пор, действительно исключали бы ваши функции: когда вы держите &mut u8 (скажем, тот, который указывает прямо рядом с тем, который передан read / read_vol / write) правила псевдонимов обеспечивают гарантию того, что никакого доступа к этому байту не произойдет ни у кого, кроме вас. Таким образом, ваши функции читают из памяти, что другие могут хранить &mut u8, что уже заставляет их нарушать правила псевдонимов.

Однако, мотивация для этих правил состоит в том, чтобы соответствовать модели параллелизма C11 и правилам LLVM для доступа к памяти. Если LLVM объявляет что-то UB, мы должны сделать это также UB в Rust, если только мы не хотим изменить наш codegen таким образом, чтобы избежать UB (и, как правило, жертвовать производительностью). Более того, учитывая, что Rust принял модель параллелизма C11, то же самое относится и к этому. Таким образом, в этих случаях правила наложения имен не имеют никакого выбора, но делают эти обращения незаконными. Мы могли бы вернуться к этому, как только у нас появится более разрешающая модель памяти, но сейчас наши руки связаны.

...