We have a new, 7th (sic!) volume of Software Foundations: Security Foundations
https://softwarefoundations.cis.upenn.edu/secf-current/index.html

Topics include noninterference, security type systems, secure multi-execution, cryptographic constant time, and speculative load hardening. And that's not even all, as the volume is still in progress, and some new chapters are upcoming.

#free #book #verification

Ковід був сім років тому

*Тікає*

#prog #article

How uv got so fast

uv is fast because of what it doesn’t do, not because of what language it’s written in. The standards work of PEP 518, 517, 621, and 658 made fast package management possible. Dropping eggs, pip.conf, and permissive parsing made it achievable. Rust makes it a bit faster still.

pip could implement parallel downloads, global caching, and metadata-only resolution tomorrow. It doesn’t, largely because backwards compatibility with fifteen years of edge cases takes precedence. But it means pip will always be slower than a tool that starts fresh with modern assumptions.

Also TIL что в стандарте HTTP есть способ запрашивать у сервера только части контента (range заголовок)

#ml #meme

#prog #rust #article

OnceMap: Rust Pattern for Running Concurrent Work Exactly Once

When multiple tasks need the same resource, how do you ensure the work happens exactly once? uv’s solution is OnceMap - a lightweight concurrent memoization primitive that powers deduplication across the resolver and installer.

Не смотря на то, что код приведён для Rust, подход, судя по всему, можно адаптировать и под другие языки.

#prog #algo #article

When would you ever want bubblesort?

Про "балканизацию" интернета я говорю ~15 лет уже.

Прости нас, Тим! Мы всё проебали.

Cloudflare оштрафовали в Италии на 14.2 млн евро за отказ блокировки пиратских сайтов в DNS-сервисе 1.1.1.1
https://www.opennet.ru/opennews/art.shtml?num=64586

Итальянское управление по надзору в сфере связи (AGCOM) оштрафовало компанию Cloudflare на 14.2 млн евро за нарушение требований в отношении блокирования пиратского контента в публичном DNS-сервисе 1.1.1.1. Выставленный Cloudflare штраф стал крупнейшим взысканием за не выполнение анипиратского законодательства Италии, так как размер штрафа начисляется от общей выручки компании.

В феврале 2025 года AGCOM выдал компании Cloudflare предписание о прекращении DNS-резолвинга доменов и IP-адресов, через которые распространяется контент, нарушающий авторские права. Компания Cloudflare отказалась реализовать в DNS-сервисе 1.1.1.1 блокировку по предоставленному списку, назвав такую блокировку неоправданной и несоразмерной, а также указав на техническую невозможность реализации фильтров в сервисе 1.1.1.1, обрабатывающем 200 миллиардов запросов в день, без негативного влияния на производительность. В сервисе 1.1.1.1 изначально заявлено отсутствие какой-либо фильтрации, а для блокировки вредоносных ресурсов и сайтов только для взрослых предоставляются отдельные DNS-резоверы 1.1.1.2 и 1.1.1.3.

После отказа в AGCOM было проведено разбирательство, которое пришло к выводу, что компания Cloudflare открыто нарушила действующие в Италии правовые нормы, обязывающие провайдеров DNS и VPN блокировать пиратские сайты. В AGCOM сочли названную причину недостаточной и не согласились с доводом, что введение фильтров приведёт к снижению качества сервиса, так как компания Cloudflare не всегда является нейтральным посредником и известна своими сложными механизмами управления трафиком. По данным AGCOM у Cloudflare есть необходимый опыт и ресурсы для внедрения требуемой блокировки.

До этого, компания Cloudflare выступала с критикой действующей в Италии с 2024 года инициативы "Piracy Shield", в ходе которой под блокировку вместе с пиратскими сайтами часто попадали и легитимные ресурсы, пользующиеся теми же платформами хостинга и сетями доставки контента. Недовольство также связано с отсутствием прозрачности при наполнении списков блокировки "Piracy Shield", которые включают около 65 тысяч доменных имён и 14 тысяч IP-адресов.

Мэтью Принс (Matthew Prince), руководитель и сооснователь Cloudflare, также указал на порочность выдвигаемых AGCOM требований, предписывающих осуществлять блокировку в течение 30 минут после уведомления. За такой короткий промежуток времени невозможно полноценно верифицировать новые записи в списке блокировки, что не исключает возникновение ложных блокировок и создаёт риски превращения 1.1.1.1 в сервис для цензурирования ресурсов, неугодных европейским издателям контента, и навязывания своих условий о том, что допустимо, а что нет в интернете. Действия AGCOM также критикуются за отсутствие судебного надзора, прозрачности, формализованной процедуры и инструментов для подачи апелляций.

#game

Господа папищеки, у меня к вам вопрос.

Я уже какое-то время назад прошёл все игры из серии Ace attorney (включая спиноффы про Майлза и Рюносуке), и мне хотелось чего-то ещё похожего. Серию часто сравнивают с Danganronpa. Из-за этого, а также из-за того, что два фандома довольно враждебно относятся друг к другу, я решил поиграть самостоятельно и составить собственное мнение.

Только что завершив первую игру в серии, я с уверенностью могу сказать, что игра действительно даёт то, что мне так нравится в Ace attorney: расследование и судебные дебаты. Более того, игра удивила меня хорошим саундтреком. К сожалению, в игре хватает много того, что мне не понравилось, и приличное доля моих претензий сводится к тому, как в игре много лишнего.

* Диалоги тут часто длятся едва ли не втрое дольше, чем надо, и повторяют одну и ту же мысль. Особенно это раздражает в финальной главе.

* Грязные шутки повторяются подозрительно часто и в целом вызывают ощущения стыда за авторов.

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

* Персонажи, за редкими исключениями, раздражают своей одномерностью и не вызывают симпатии.

* Финал игры сценарно исполнен крайне криво: через несколько сюжетных твистов подряд и кучу экспозиции (ещё и от лица главного злодея), а бесконечные прения на тему отчаянья и надежды заставляют закатывать глаза. Тот факт, что последняя глава требует повышенного подавления неверия (suspension of disbelief), тоже умаляют эффект, который она могла бы иначе иметь.

* Номинально тут есть прокачка, но смысла в ней довольно мало из-за того, насколько мизерный эффект улучшения оказывают на геймплей.

В целом, я получил свою долю удовольствия от игры, но из-за означенных выше моментов остался в целом скорее недоволен. Я наслышан, что сиквел во многих аспектах является улучшением на фоне оригинала, но я всё ещё не уверен, что он стоит моих денег и времени. Потому у меня вопрос: исходя из моих претензий к первой игре, стоит ли мне играть в Danganronpa 2? И если да, то стоит ли играть в оригинальную версию или в 2x2?

И #video #meme в тему

Кстати, довольно забавно, насколько слабо озвучка влияет на общее впечатление.

В Ace Attorney озвучены только отдельные крики ключевых персонажей (главным образом иконическое "Objection!"), а все остальные фразы сопровождаются электронными бипами в такт словам, и их всего две разновидности: для мужских персонажей и для женских. В Danganronpa же целиком озвучены все реплики по время судов. Тем не менее, лучше держать в напряжении и удивлять твистам это не особо помогает — Ace Attorney достигает схожего эффекта и при этом не полагается на дешёвую театральщину, выезжая исключительно текстом.

Собственно, по моему мнению, Селестия Люденберг — единственный персонаж, для которого озвучка делает игру более интересной, и то только в одной главе. Для всей остальной игры озвучку можно было бы выкинуть без особого ущерба для опыта.

#meme про новогодние каникулы

#prog #rust #моё

У Алексея Кладова есть пост про реализацию интернирования строк (советую прочитать перед моим постом). Как он замечает, простейший способ интернировать строки — через такой тип:

struct Interner {
    map: HashMap<String, u32>,
    vec: Vec<String>,
}

Новые строки добавляются через вставку в map, а идентификатор строк создаётся от длины vec на момент добавления. map позволяет быстро проверить, была ли строка записана, а vec позволяет быстро получить строку по её идентификатору.

Недостаток такого решения очевиден: каждая строка выделяется в куче дважды. Особенно это печально в связи с тем, что строки часто интернируют именно для того, чтобы сэкономить память, выделяя её только единожды на каждое значение. Алексей решает это тем, что выделяет память по возможности одним куском в одной String и хранит в мапе &str на эту память с принудительно приведённым к 'static временем жизни. Инвалидацию ссылок он обходит остроумным приёмом: при нехватке ёмкости он выделяет новый буфер, вдвое больше предыдущего, и записывает новые строки туда, а старый буфер переносит в отдельный вектор. Он эксплуатирует тот факт, что адреса выделенной в куче памяти стабильны и не меняются при перемещении String. С таким дизайном определение структуры данных выглядит так:

struct Interner {
    map: HashMap<&'static str, u32>,
    vec: Vec<&'static str>,
    // новые строки записывают сюда
    buf: String,
    // буферы с недостаточной памятью переносят сюда
    full: Vec<String>,
}

К сожалению, у этого дизайна есть несколько недостатков.
* Выдаваемые Interner идентификаторы не самодостаточны: всё ещё нужно обращаться к пулу, если нам потребуется содержимое строки. Пул при этом можно перепутать
* Из-за индексации каждый лукап — потенциальная паника.
* Идентификаторы никак не привязаны к пулу временами жизни: если мы создадим пул, выделим строку, дропнем пул, создадим заново и снова выделим строку, то возвращённые значения будут считаться равными — что технически верно, но не вполне корректно.
* Можно сравнивать идентификаторы, полученные от двух разных пулов, и получить как и ложно-положительные, так и ложно-отрицательные результаты, и компилятор вообще никак от этого не защищает.
* Очень нишевый недостаток: u32 не имеет ниши и потому не получает null pointer optimization при оборачивании в Option. Это, в принципе, решаемо оборачиванием в NonNull<u32>, но не очень удобно из-за инкремента при генерации и декремента при индексации.
* Количество потребляемой таки пулом памяти может только расти, явное переиспользование памяти невозможно. Это может быть важно, если нам требуется многократно использовать пул в ограниченной области действия.

От всех этих недостатков можно избавиться, используя два решения.

Первый из них заключается в трюке, используемом в thin_vec: вместо того, чтобы хранить длину аллокации отдельно, выделять дополнительную память в куче и хранить в начале длину строки. Сами интернированные строки будут хранить указатель на начало аллокации и создавать толстый указатель на строку по требованию. Это даёт несколько преимуществ:

* Выдаваемые идентификаторы могут быть переведены в строки без обращения к пулу — его не надо держать под рукой и получение строки не может паниковать.
* К создаваемой строке можно (на самом деле нужно, для корректности) привязать время жизни. Это позволяет избежать ошибок со случайным переиспользованием строк и до какой-то степени защищает от сравнения строк из разных пулов.
* Указатель имеет естественную нишу в виде null и потому получает оптимизацию раскладки Option.

Второе решение заключается в том, чтобы использовать bump-аллокатор — в данном случае bumpalo. Он даёт гарантии стабильности адресов, а внутри использует тот же трюк с удваиваемыми буферами, который нам не надо повторять самостоятельно. Дополнительно он позволяет скопом освобождать память, сохраняя при этом аллокацию последнего буфера, что позволяет уменьшить потребление памяти и обращение к аллокатору и закрыть таким образом последний недостаток решения Кладова.

Что ж, приступим к реализации!

Запишем сначала определение интернированной строки:

#[derive(Clone, Copy, PartialEq, Eq)]
pub struct InternedStr<'a> {
    ptr: NonNull<u8>,
    _lt: PhantomData<&'a ()>,
}

impl<'a> InternedStr<'a> {
    // Конструктор unsafe, потому что корректность
    // времён жизни нужно обеспечивать пользователю
    unsafe fn from_ptr(ptr: NonNull<u8>) -> Self {
        Self {
            ptr,
            _lt: PhantomData,
        }
    }
}

Самая полезная операция для это строки — перевод в &str. Для этого нам нужно считать размер строки из начала аллокации, сдвинуть указатель на размер usize и сделать толстый указатель из полученного тонкого и длины:

const USIZE_SIZE: usize = std::mem::size_of::<usize>();

impl<'a> InternedStr<'a> {
    pub fn as_str(self) -> &'a str {
        let len = unsafe { self.ptr.cast::<usize>().read() };
        let ptr = unsafe { self.ptr.add(USIZE_SIZE) };
        unsafe {
            str::from_utf8_unchecked(
                std::slice::from_raw_parts(
                    ptr.as_ptr(),
                    len
                )
            )
        }
    }
}

Теперь немного подумаем о том, как будет выглядеть пул строк. Очевидно, нам нужен Bump для выделения памяти. Также нам всё ещё нужно иметь возможность быстро определять, записали мы строку или нет, поэтому в пул нужно включить HashSet<InternedStr<'_>>.

Со вторым полем есть пара вопросов.

Во-первых, какое именно время жизни нужно вписать для хранимых InternedStr? Технически мы заимствуем память из соседнего поля типа Bump, то есть определение является самоссылающимся типом. Воспользуемся типичным для такой ситуации подходом: будем хранить в множестве InternedStr<'static>, а безопасность это, вообще говоря, некорректного времени жизни будем обеспечивать API, который будет выдавать строки со временем жизни, привязанным к пулу строк.

Во-вторых, что делать с мутабельностью? Выделение новых строк в памяти, очевидно, требует модификации множества, но если мы запишем метод вида

fn alloc(&mut self, s: &str) -> InternedStr<'_> { ... }

, то из-за исключительного заимствования пулом будет невозможно пользоваться, пока возвращённая строка не будет дропнута. Очевидно, здесь требуется внутренняя изменяемость, и так как Bump и так !Sync, достаточно немногопоточного RefCell.

Итого определение выглядит так:

const USIZE_ALIGN: usize = std::mem::align_of::<usize>();

#[derive(Default)]
pub struct Interner<S = std::collections::hash_map::RandomState> {
    strs: RefCell<HashSet<InternedStr<'static>, S>>,
    mem: Bump<{ USIZE_ALIGN }>,
}

Bump параметризован минимальным выравниванием для аллокаций. Выравнивание для usize позволяет нам использовать выровненный доступ к длине в InternedStr::as_str, то есть read вместо read_unaligned.

Запишем реализацию метода для выделения строки:

    pub fn alloc(&self, s: &str) -> InternedStr<'_> {
        ...

Для начала нужно проверить, записана ли вообще уже строка. Если да, то сразу возвращаем её — в этом и состоит смысл интернирования:

        ...
        let mut strs = self.strs.borrow_mut();
        if let Some(&interned) = strs.get(s) {
            return interned;
        }
        ...

Теперь нужно выделить память под строку и под длину строки. У Bump есть много методов выделения памяти, но почти все из них подразумевают, что значение для аллокации уже есть в наличии. В нашем случае это не так, поэтому мы воспользуемся методом, который возвращает неинициализированную память: Bump::alloc_layout.

(тут на самом деле можно попенять авторов, потому что этот метод почему-то возвращает NonNull<u8> вместо гораздо более эргономичного &mut [MaybeUninit<u8>])