Вы читаете avva

Зря ли я столько сил разбазарил? - о началах программирования [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

о началах программирования [мар. 29, 2011|09:46 pm]
Previous Entry В избранное Поделиться Next Entry
(эта запись будет интересна лишь программистам и сочувствующим)

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




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

А Линусу - спасибо за мастер-класс.
СсылкаОтветить

Comments:
Страница 1 из 5
<<[1] [2] [3] [4] [5] >>
[User Picture]From: beldmit
2011-03-29 07:58 pm none (UTC)

(Link)

Я недавно натыкался на вчем-то аналогичную упертость.

http://beldmit.livejournal.com/302709.html#cutid1
[User Picture]From: sinm
2011-03-29 07:58 pm none (UTC)

(Link)

Спасибо, интересно.
[User Picture]From: sanmai
2011-03-30 12:26 am none (UTC)

(Link)

Да, Линус неспроста тот, кто он есть.
[User Picture]From: melkore
2011-03-29 07:59 pm none (UTC)

наверное нубский вопрос, но...

(Link)

правильно ли я понимаю, что Федоровцами в данном случае не движет ровным счётом ничего кроме упрямства?
[User Picture]From: beldmit
2011-03-29 08:01 pm none (UTC)

Re: наверное нубский вопрос, но...

(Link)

Как можно! Не упрямство, а чистота идеологии!
[User Picture]From: dixi
2011-03-29 08:00 pm none (UTC)

(Link)

Ох. Я думал что такие люди только в анекдотах про BOFH бывают.
[User Picture]From: motto
2011-03-29 08:09 pm none (UTC)

(Link)

ты меня удивляешь таки

а вообще, это прекрасная и киношная история, типа "Деликатесов" Leon
с одной стороны очевидно, что хорошие парни - они из интела, а с другой -- киллер симпатичный такой и о цветочке заботится Линус говорит дело, практически, словами майкрософта
это же дико, дико смешно (смешнее может быть только просмотр флеша под линуксом)

[User Picture]From: trueblacker
2011-03-29 08:01 pm none (UTC)

(Link)

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

Хотя мне несложно их понять и я даже гдето разделяю их протест против несовершенства этого мира.
[User Picture]From: dibr
2011-03-29 08:48 pm none (UTC)

(Link)

Так священные тексты как раз на стороне фанатиков: в них написано, что memcpy() и memmove() - разные функции, и memcpy() не обязана работать корректно при перекрытии областей. Вот они и настаивают на том, что если memcpy() _может_ не работать корректно - то она и _не должна_ работать корректно...
(Удалённый комментарий)
[User Picture]From: stefashka
2011-03-29 08:02 pm none (UTC)

(Link)

Линус просто ведёт себя как взрослый человек и зрелый разработчик. А разработчики Федоры всё ещё не переболели юношеским максимализмом и бодро моськают.
From: lazyreader
2011-03-29 08:06 pm none (UTC)

(Link)

Ну надо и их понять. С чего бы им вот прямо подрываться и из-за адобовского тупоумия бежать править код, покрывать его тестами, выпускать релиз libc?

Это всё-таки не то же самое, чтобы студенту пару строчек в скрипте поправить.
[User Picture]From: motto
2011-03-29 08:02 pm none (UTC)

(Link)

прямой репортаж из банки с тараканами - ок
[User Picture]From: aalien
2011-03-29 08:47 pm none (UTC)

(Link)

…в голове.
[User Picture]From: sleeping_death
2011-03-29 08:03 pm none (UTC)

(Link)

*double facepalm*

не совсем только понятно, как можно быть на стороне программистов федоры.
From: lazyreader
2011-03-29 08:08 pm none (UTC)

(Link)

А что им надо было сделать? Выкинуть интеловскую оптимизацию и вернуть старый код memcpy? Это, кстати, единственное, что удовлетворило бы всех (кроме тех, кто хочет получить оптимизацию).
From: lazyreader
2011-03-29 08:03 pm none (UTC)

(Link)

Интересная история, и все в ней ведут себя так, как я бы ожидал.

Торвальдс - прагматик. Предпочитает "free as in free beer, not as in free speech" (как-то так, по памяти).

Дреппер - давно известен упёртостью; разработчики glibc правы в принципе, но, наверное, могли бы уступить. В конце концов, стандарт C не требует от memcpy, чтобы она именно не проверяла перекрытия и не вела себя как memmove.

Adobe - просто не могла упустить удобный случай написать глючный софт и, вместо исправления, сохранять гордое молчание. Дреппер прав, по крайней мере, в одном - если софт пишут люди, которых вообще не стоит подпускать к клавиатуре, то результат будет именно таким.
[User Picture]From: taganay
2011-03-29 08:15 pm none (UTC)

(Link)

Софт пишут люди, поэтому если в библиотеке имеются грабли, то на эти грабли будет наступленно наиболее болезненным способом. Поэтому если есть возможность грабли убрать, их надо вначале убрать, а уж потом разбираться, кого можно подпускать к клавиатуре, а кого - нет.
[User Picture]From: igorlord
2011-03-29 08:06 pm none (UTC)

(Link)

Don't know, but it seems that memcpy did not have any bugs. You cannot have implementation bugs, if the implementation fits the spec. It can be a spec bug (and it can easily argued that it is), but no one is/was proposing to change the spec for C.

A different question is what to do about this situation, when many applications have managed to screw up and misuse memcpy?

It is the answer to this question that seems more interesting. I would, indeed, vote for using memmove instead of memcpy by default and add a compiler parameter and, possibly, pragma to turn on the original "fast" memcpy.

I do have some small reservations about this approach, though, because in a typical server-type application, when you run a profiler, memcpy typically shows up in the top 20-30 functions (because it is used so often to copy around little buffers and strings). This "fix" would make it even slightly more expensive.
[User Picture]From: alexcohn
2011-04-13 12:44 pm none (UTC)

(Link)

+1 "чума на оба ваши дома"

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

Чего я не понимаю во всём этом шуме - где патч работающая версия от Adobe? Можно сколько угодно спорить, нужно ли исправлять glibc, но если все вынуждены пользоваться неофициальной версией флеш-плейера, то что-то не ладно в адобском королевстве.

А пока для Федоры решение должно быть - воспользоваться методами Microsoft Windows, и вписать в систему tweak: для флеш плейера такой-то версии - подставить memmove вместо memcpy. Никто не знает, к каким странным эффектам подобная подстановка может привести в еще одной неприкаянной аппликации.
[User Picture]From: yarmola
2011-03-29 08:09 pm none (UTC)

(Link)

Спасибо за поучительную историю!

С чем-то похожим приходится сталкиваться при поддержке хорошо специфицированных форматов данных. Моя позиция состоит в том что пытаться читать нужно все что хоть как-то можно прочитать. Именно потому что "THE USER DOESN'T CARE" :)
[User Picture]From: _iga
2011-03-29 11:43 pm none (UTC)

(Link)

На практике это привело к тому, что дай бог 10% сайтов соответствуют W3C.
[User Picture]From: spamsink
2011-03-29 08:10 pm none (UTC)

(Link)

Андреасом Швабом ... Ульрихом Дреппером

Нет ли в этом посте антигерманизма?
[User Picture]From: poige
2011-04-01 02:43 pm none (UTC)

> Нет ли в этом посте антигерманизма?

(Link)

5+ :-)
[User Picture]From: igorlord
2011-03-29 08:10 pm none (UTC)

(Link)

P.S.
At my work, I've refused to change what was not broken in my code "because our code no longer works with your library". Instead, I got the other team to fix the crap they had. Now, both pieces of osftware are better for it -- my library does not have weird things "to make component X happy", and "component X" is better designed.
[User Picture]From: angerona
2011-03-29 08:10 pm none (UTC)

(Link)

на самом деле по-моему надо начинать с последней цитаты.

[User Picture]From: dbg
2011-03-29 08:11 pm none (UTC)

(Link)

Ура-ура. Федоровцы под предводительством Дреппера наконец приступили к строительству DeathStation 9000. Ждем скорейшей имплементации всех остальных фич.
[User Picture]From: develop7
2011-03-29 08:16 pm none (UTC)

(Link)

У Дреппера ЧСВ взыграло, КМК.
[User Picture]From: compiler
2011-03-29 08:17 pm none (UTC)

(Link)

Я не программист, а сочувствующий, но мораль мне совершенно очевидна. Особенно повеселил ответ Дреппера.
From: lazyreader
2011-03-29 08:18 pm none (UTC)

(Link)

В общем, подумав, можно догадаться, что практическое решение тут только одно.

Поскольку в мире полчища тупых программистов, которые пишут программы, не прочитав даже K&R, то следует: 1) memcpy навечно оставить в той имплементации, как сейчас; 2) интеловскую оптимизацию применить к memmove.

Касательно предложения Линуса сделать memcpy алиасом к memmove: оно не годится. Поскольку memcpy исторически копировала от начала к концу, могло найтись ненулевое количество идиотов, которые в своих программах использовали memcpy для копирования паттерна по памяти (это старый трюк):


char region[20] = {'h', 'e'};
memcpy(region, region + 2, 18); /* "hehehehehehehehehehe"



Это абсолютно нестандартно и не определено, но Adobe, насколько я знаю, ещё не всех идиотов наняла в штат. Так вот, если вместо memcpy вызывать memmove, то поломаются программы, использующие вышеприведённый трюк, а виноваты будут опять разработчики libc, Линус, Керниган и Ритчи и кто угодно, только не люди, которых нельзя подпускать к клавиатуре, а их подпускают и дают программировать.
[User Picture]From: motto
2011-03-29 08:54 pm none (UTC)

(Link)

Yep!
[User Picture]From: deadkittten
2011-03-29 08:19 pm none (UTC)

(Link)

Ну, подобное отношение к остальным программистам разработчики glibc не в первый раз демонстрируют. Вспомнить хотя бы историю с изменением обработки errno...
[User Picture]From: thxbye
2011-03-29 08:19 pm none (UTC)

(Link)

С точки зрения решения проблемы «прямо сейчас» — само собой, Торвальдс прав.
С точки зрения абстрактного разбора полётов — неправы обе стороны: разработчикам glibc давно стоило убрать «the burden of choosing correctness over speed» с плеч программистов; разработчикам прикладного софта — быть в курсе того, что «burden» всё ещё никуда не делся, и писать код соответствующим образом.
[User Picture]From: polytheme
2011-03-29 10:23 pm none (UTC)

(Link)

это почти правда, но, во-первых, убирать "burden" нужно не разработчикам glibc, а из стандарта, а во-вторых, разработчикам прикладного софта нужно быть не в курсе, что чего-то там куда-то не делось, а в курсе стандарта, и не совать свой длинный нос в код glibc. то есть что адобовцы - педерасы, вопрос очевидный и тут не ставится.
[User Picture]From: crz
2011-03-29 08:20 pm none (UTC)

(Link)

[User Picture]From: zigmar
2011-03-30 10:29 am none (UTC)

(Link)

лол :)
[User Picture]From: max630
2011-03-29 08:20 pm none (UTC)

(Link)

А Дреппер не в редхате ли работает?

В любом случае, сказал по сути правильно.
[User Picture]From: b_a_t
2011-03-29 09:59 pm none (UTC)

(Link)

Еще одна причина не пользоваться RedHat дистрами.
[User Picture]From: juunitaki
2011-03-29 08:20 pm none (UTC)

(Link)

Ломать — не строить.
From: friend_or_foe
2011-03-30 10:32 am none (UTC)

(Link)

Гнильё должно быть сломано, и чем быстрее, тем лучше.
Разработчики glibc - санитары леса.
[User Picture]From: max630
2011-03-29 08:25 pm none (UTC)

(Link)

Это, кстати, забавным образом перекликается с вашим вчерашним постом про правозащитников. Во всей этой истории почему-то никто не видно ссылку на багзиллу адоба с 213 комментами. А начинаться всё должно именно с неё.
From: lazyreader
2011-03-29 08:49 pm none (UTC)

(Link)

Ссылку не дадите ли? Любопытно, как в Adobe реагируют.
[User Picture]From: novus_ludy
2011-03-29 08:26 pm none (UTC)

(Link)

Комментарий со стороны. Спасибо за доступное изложение, интересно и вроде бы понятно даже непрограммистам.
Позиция оппонентов Линуса вызывает удивление. Там что-то религиозное, при этом заплатка, если я правильно понял из описания, не будет сама "плохим" кодом и вовсе не поощряет "плохое" программирование.
[User Picture]From: beldmit
2011-03-29 08:29 pm none (UTC)

(Link)

Поощряет забитие на спецификацию, но ей-богу, оправданное.
Страница 1 из 5
<<[1] [2] [3] [4] [5] >>