о началах программирования

avva — 29.03.2011 (эта запись будет интересна лишь программистам и сочувствующим)

Из недавно обнаруженного бага в дистрибутиве Линукса Федора сложилась очень поучительная история, которую на мой взгляд неплохо бы преподавать в университетах, на уроках программирования, чтобы объяснять студентам не только как ключевые слова писать, но и как работать вместе с другими программистами и проектами. Чтобы видели, как нужно делать, и как нельзя. Эта полезная история - как бесплатный мастер-класс, проведенный Линусом Торвальдсом. И если вам непонятно в ней, на чьей стороне правда, или вам кажется, что она на стороне разработчиков Федоры и glibc, то вы - часть проблемы.

Вот краткий пересказ этой истории.

Функция memcpy(dst, src, size), как известно, копирует блок памяти размером size, начиная с адреса src, в адрес dst. Иными словами, она копирует регион src----->src+size в регион dst---->dst+size. Что будет, если эти два региона пересекаются?

Представьте себе, что dst начинается где-то в середине исходного региона: src----dst--->src+size---->dst+size. Тогда первый же скопированный байт из src в dst "наступит" на какой-то другой байт исходного региона и "испортит" его. В итоге мы получим не то, что хотели, а ерунду. Но эту проблему можно обойти: если мы будем копировать от конца к началу: последний байт, потом предпоследний, итд. - тогда все скопируется правильно. С другой стороны, если регионы пересекаются "наоборот": dst----src--->dst+size--->src+size, тогда копирование "от конца к началу" портит память, а копирование от начала к концу работает отлично.

Стандарт говорит, что функция memcpy() необязательно работает правильно, если регионы пересекаются. Есть другая функция, memmove(dst, src, size), которая всегда работает правильно, для любых аргументов. Ее имплементация обычно проверяет, пересекаются ли регионы, и в таком случае копирует "от начала к концу" или "от конца к началу", в зависимости от того, как надо. А memcpy() традиционно в библиотеках языка C копирует всегда от начала к концу. Если регионы пересекаются одним путем, то она работает нормально, если другим - плохо, если не пересекаются - нет проблем, ясно. Но вообще-то программисты должны вызывать memmove(), если подозревают, что регионы могут пересекаться.

(зачем вообще определили так, чтобы memcpy() могла неправильно работать? Потому что в 70-е годы иногда было важно экономить каждую инструкцию - и для экономии времени в очень медленных процессорах, и для экономии места, которые занимают инструкции в очень маленьких процессорах. Если мы всегда копируем в одну сторону, то memcpy() можно написать очень просто на ассемблере - двумя-тремя инструкциями, без проверок регионов и разных случаев).

Это была присказка. А сказка начинается прошлым летом, когда в исходники glibc внесли существенное изменение в код memcpy(), предложенное программистами из Интела. Новая версия memcpy() на некоторых процессорах при некоторых условиях копирует регионы от конца к началу, а при других условиях - от начала к концу. На других процессорах она как и раньше всегда копирует от начала к концу. Все эти сложные изменения должны были ускорить memcpy(), и вполне возможно, что они добились этой цели, хотя точных и убедительных измерений я так и не нашел. В Интеле работают хорошие программисты, но грамотная оптимизация такого рода - задача непростая и не всегда легко понять, что лучше.

Формально говоря, это изменение не противоречит стандарту. Но на практике оказалось, что во многих программах есть вызовы memcpy(), в которых регионы пересекаются тем путем, что работает нормально в традиционной имплементации. А в новой, при копировании от конца к началу, выходит ошибка. Но не всегда, а лишь на некоторых процессорах и в некоторых условиях. И пока что никто этого еще не знает, в конце июня прошлого лета.

29 сентября 2010 года. Пользователь "JCHuynh" открывает новый баг на сайте Федоры о том, что 64-битный флэш-плагин от Adobe перестал нормально проигрывать mp3-файлы, выдает все время какой-то треск вместо правильного звука. Adobe предоставляет два плагина для Линукса, но "официальный" 32-битный морально устарел и работает на 64-битных системах куда хуже "неофициального" 64-битного - этот последний как раз и начал барахлить.

Несколько других пользователей подтверждают проблему. 11 октября к ним присоединяется небезызвестный Линус Торвальдс. Выдвигаются разные идеи: баг в ядре? в драйвере звуковой карты? в аудио-библиотеках?

30 октября Майкл Янг обнаружил, что дело в версии glibc: версия в 13-м выпуске Федоры работает нормально, а в 14-м "трещит".

6 ноября Систоуф Уилер запускает браузер под valgrind, и находит подозрительное предупреждение насчет неправильного вызова memcpy(). В тот же день Линус подтверждает его анализ. Через два дня Линус предлагает временное решение, основанное на трюке с LD_PRELOAD (см. коммент #38), и задается вопросом, зачем было менять memcpy() и действительно ли это улучшает ее скорость.

В тот же день один из разработчиков glibc Андреас Шваб закрывает баг с вердиктом NOTABUG: "The only stupidity is crap software violating well known rules that have existed forever."

В ответ Линус пытается объяснить Андреасу и нескольким другим разработчикам glibc прописные истины, которые должны и так быть известны любому компетентному программисту (комменты 40, 46). Например:

You can call it "crap software" all you like, but the thing is, if memcpy doesn't warn about overlaps, there's no test coverage, and in that case even well-designed software will have bugs.

Then the question becomes one of "Why break it?"

Баг остается открытым.

16 ноября (коммент 101) Линус предлагает очевидное решение: memcpy() должна быть алиасом memmove(). Если есть возможность как следует оптимизировать копирование, это надо сделать в memmove(), после проверки того, что регионы не пересекаются. Ведь эта проверка совершенно тривиальна и практически ничего не стоит на современных процессорах. Единственная причина не делать эту проверку - ради простоты: в особенно простой и тупой имплементации memcpy(), которая скажем ничего не проверяет, а просто копирует специальными инструкциями, еще можно предложить не проверять регионы. Но новая версия memcpy() и так уже делает много разных проверок, чтобы решить, в какую сторону копировать; в эту "сложную" версию добавить еще и проверку регионов уже точно ничего не стоит. Тут нечего и думать.

Но стойкие разработчики Федоры не видят причины менять свое мнение о том, что исправлять ничего не надо. Андре Робертино, 30 ноября (коммент 128): "Fedora's flash support is fine. Adobe's software is broken."

Линуса это выводит из себя (коммент 129):

"Quite frankly, I find your attitude to be annoying and downright stupid.

How hard can it be to understand the following simple sentence:

THE USER DOESN'T CARE."

См. также коммент 132, в котором Линус более подробно и основательно объясняет то, что я суммировал выше.

Наконец, 1 декабря баг открывают снова. Увы, это ни к чему не приводит, несмотря на продолжающиеся жалобы пользователей, не понимающих, почему нельзя его починить так, как предлагает Линус и другие нормальные люди.

Три месяца спустя, 21 февраля, Линус подытоживает (коммент 199):

A much better workaround is likely to just implement memcpy() as memmove() (you can replace the inline asm by that in my preload example if you want to). Once memcpy() isn't small and trivial any more, that's just the right thing to do.

The fact that the glibc people don't do that, and that this hasn't been elevated despite clearly being a big usability problem (normal users SHOULD NOT HAVE TO google bugzillas and play with LD_PRELOAD to have a working system), is just sad.

Quite frankly, there is no reason for the current memcpy() mess. There is no _technical_ reason for it, and there is certainly no usability reason for it. Why the Fedora people don't just fix it, I don't understand. It's a shame and a disgrace.

The fact that Adobe does something that isn't technically right is no excuse
for having a sub-par crap memcpy() implementation.

Он также спрашивает, как можно поднять приоритет этого бага или еще как-нибудь побудить
разработчиков Федоры его починить, на что один из разработчиков отвечает ему, что это
невозможно, а другой (Каллум Лервик, коммент 213) объясняет пользователям:

If you don't like it, you're simply using the wrong distribution.

The 32-bit flash plugin works fine. Y'all are lucky we tacitly support the
32-bit Flash plugin as much as we do.

Ему пытаются объяснить, что дело не только в Флэше, что этот баг в memcpy() создает проблемы и в других
программах, но он отказывается в это поверить.

(хороший пример такой проблемы можно увидеть в дискуссии в LWN. Разработчики Squashfs знали о том, что memcpy() нельзя вызывать с пересекающимися регионами, и позаботились об этом. Но в дальнейшем рефакторинге их кода эта ситуация изменилась, и никто не заметил, потому что старая memcpy продолжала работать нормально с этим видом пересечения. А новая стала работать неправильно...)

Позавчера, 27 марта, Райан Хантер отыскал цитату из классики - книги Кернигана и Пайка "Практика программирования" (коммент 245):

"The ANSI C standard defines two functions: memcpy , which is fast but might overwrite memory if source and destination overlap; and memove, which might be slower but will always be correct. The burden of choosing correctness over speed should not be placed upon the programmer; there should be only one function."

Torvalds, Kernighan, Pike: 1
glibc developers: 0

Мы дошли до сегодняшнего дня. Баг остается открытым и непочиненным.

Торвальдс попробовал также открыть баг "в апстриме", в трекере самой glibc. Он открыл его месяц назад и подробно описал, в чем дело, почему поведение новой memcpy() неверное, и как можно легко ее починить, не потеряв совершенно скорости.

Ответ главного разработчика glibc, Ульриха Дреппера, начинается так: "The existence of code written by people who should never have been allowed to touch a keyboard cannot be allowed to prevent a correct implementation."

---

На этом заканчивается моя поучительная история. То есть, она еще не закончена, баги открыты, но урок уже можно извлечь. Проверьте себя: если вы соглашаетесь с Андреасом Швабом, Андре Робертино, Каллумом Лервиком и Ульрихом Дреппером, то подумайте как следует. Перечитайте внимательно все комментарии в этих багах, а не только те, что я цитировал. Подумайте еще раз. И если вы все еще за них, мне остается лишь надеяться, что никогда не придется работать с вами над одним проектом.

А Линусу - спасибо за мастер-класс.

Оставить комментарий

Популярные посты:

• Архив