У моего давнего британского партнёра (именно для него два года назад писалось «Распознавание почтовых адресов») появилась новая идея по оптимизации бизнес-процессов: коробки по складу должны возить роботы, а грузчики — только перекладывать товары с робота на полку и обратно. Смысл, естественно, не в том, чтобы за каждым роботом по пятам шёл грузчик, и принимался за погрузку-разгрузку, как только робот остановится — а чтобы роботов было намного больше, чем грузчиков, и чтобы роботы большую часть времени стояли в конечной точке своего маршрута, ожидая погрузки. Тогда грузчик будет лишь переходить от одного робота к следующему, нагружая каждый, и не будет тратить рабочее время на переноску товаров.

Предыстория

В прошлом году мы экспериментировали с платформой самоходного пылесоса Roomba. Новенький пылесос обошёлся нам около £300 (подержанный можно найти за £100 и даже дешевле), и в его состав входят два электропривода на колёса, два датчика касания спереди, инфракрасный датчик снизу (для обнаружения ступенек) и сверху (для поиска зарадной станции). Точный перечень датчиков зависит от модели: в протоколе предусмотрено до четырёх инфракрасных датчиков снизу, каждый из которых возвращает один бит («пол виден/не виден»). В любом случае, никаких дальномеров: все имеющиеся датчики однобитные. Кроме того, никаких «программируемых ардуин» в Roomba нет, и чтобы им управлять, нужно установить сверху лаптоп (или ардуину) и общаться с роботом по RS-232. Поигравшись с пылесосом вдоволь, мы так и оставили его пылиться на одной из полок склада.

В этом году мы решили попробовать Microsoft Robotics Development Studio (MRDS), для продвижения которого Microsoft сформулировала спецификацию «MRDS Reference Platform» — набор оборудования и протокол управления «стандартным» роботом. Эта спецификация позволила бы роботолюбам создавать совместимых роботов и переносить между ними программы. По сравнению с аппаратным оснащением пылесоса, Reference Platform намного сложнее и мощнее: в спецификацию включён Kinect, три ИК-дальномера и два ультразвуковых, а также датчики вращения колёс (encoders). Реализацию MRDS RP пока что предлагает только фирма Parallax под названием Eddie (порядка £1000, не включая Kinect). Необычайное сходство Eddie с фотографиями робота-прототипа в спецификации MRDS RP наводит на мысли, что спецификация создавалась в тесном сотрудничестве с Parallax, иначе говоря — Parallax удалось добиться, что Microsoft приняли их платформу за эталонную.

Кроме разнообразия датчиков, Eddie обладает механически впечатляющей платформой (заявленная грузоподъёмность 20кг, а мощности моторов достаточно, чтобы толкать впереди себя складской погрузчик) и программируемым контроллером Parallax Propeller, т.е. критические куски кода можно зашить непосредственно в робота, а не только командовать им с компа.

Недавно Реймонд Чен завершил серию постов, начатую ещё полтора года назад, и посвящённую управлению виртуальной памятью безо всякой поддержки со стороны процессора: Windows до версии 3.0 включительно поддерживала реальный режим 8086. В этом режиме трансляция адреса из «виртуального» (видимого программе) в физический (выдаваемый на системную шину) осуществляется бесхитростным сложением сегмента и смещения — никакой «проверки доступа», никаких «недопустимых адресов». Все адреса доступны всем. При этом в Windows могли одновременно работать несколько программ и не мешать друг другу; Windows могла перемещать их сегменты в памяти, выгружать неиспользуемые, и по мере необходимости подгружать назад, возможно — по другим адресам.

(Интересно, всегдашние холиворщики «это была графическая оболочка, а не операционная система» в курсе об этих её необычайных способностях?)

Один французский «исследователь безопасности» этим летом опубликовал невиданно много найденных им уязвимостей типа arbitrary file upload в разных «написанных на коленке», но популярных CMS и плагинах к ним. Удивительно, как беспечны бывают создатели и администраторы небольших форумов, блогов и интернет-магазинчиков. Как правило, в каталоге, куда загружаются аватары, резюме, смайлики и прочие ресурсы, которые пользователь может загружать на сайт — разрешено выполнение кода PHP; а значит, загрузка PHP-скрипта под видом картинки позволит злоумышленнику выполнять на сервере произвольный код.

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

Две недели назад я начал работу в датской компании "Secunia", и хочу — как и многие хабровчане, уехавшие работать за рубеж — поделиться своим опытом. Не уверен, к какому хабу это должно относиться, но вроде бы предыдущие подобные рассказы были в «Офисах IT-компаний».

Поиск работы

Всё началось с того, что Google AdWords показал мне ссылку на вакансию "Senior Reverse Engineer and Vulnerability Researcher". Как раз в это время я искал новую работу, и гугл, видимо, тонко проанализировал мою историю поиска и содержимое последних писем; а может быть, просто подфартило. Эта вакансия до сих пор открыта; и если кто-нибудь из вас на неё устроится, упомянув меня в качестве порекомендовавшего, то мне будет положен какой-то приятный бонус. Так что не стесняйтесь.

В начале ноября я отправил на рассмотрение своё резюме, и получил по очереди два тестовых задания. Оба были похожи: дан кусок дизассемблированного кода x86 (одно задание было на Си, другое на С++). Нужно восстановить исходник и найти в нём возможные уязвимости и другие проблемы. От момента получения кода, до отправки заключения по нему — даётся час. Длина кода — около сотни команд. Фактически, у меня уходило минут двадцать на его разбор, и минут двадцать на написание соответствующего кода на Си/С++. Ничего сложного для любого, кто когда-нибудь пытался ковыряться в чужих программах.

В конце ноября у меня — удачно совпало — уже была запланирована поездка по Скандинавии; и в тот единственный день, когда я был в Копенгагене, я решил заскочить в Secunia, почти без предупреждения. Новая удача: именно в этот день им какие-то строители экскаватором перерубили интернет, и все сотрудники сидели без дела. Поэтому CTO оказался свободен, чтоб меня прособеседовать. Он произвёл на меня весьма серьёзное впечатление, но больше я его с тех пор не видел; а с моим нынешним начальником мы тогда обменялись разве что парой слов. Они сказали, что пришлют мне последнее, самое сложное и важное задание, и после этого окончательно решат по поводу моей кандидатуры.

Это последнее задание мне прислали в начале декабря. Нужно было найти конкретную версию Adobe Reader, взять готовый PDF-файл, который её валит — и написать подробный отчёт, почему это происходит. На задание давался день, с комментарием «не торопись, сделай качественно, сможешь за четыре часа — отлично, за шесть — приемлемо». У меня ушло где-то часов восемь с перерывами на кофе. Я отправил результат, и принялся ждать.

Ещё в те времена, когда на Хабре не было модным ругать HP, я собрался обновить свой старый лаптоп.
На официальном сайте http://hp.co.uk/ моё внимание привлекло спецпредложение: Compaq Presario CQ56-102SA за £249, включая доставку. Рядом было указано: «товар в наличии на складе, отправка в день получения заказа».

Вечером 22 августа я оформил заказ, расплатившись в онлайн-магазине HP своей израильской карточкой. Получил по электронной почте подтверждение, «заказ принят», и умиротворённо лёг спать.

Каково же было моё удивление найти наутро в почтовом ящике сообщение от HP: «заказ отменён».

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

Один из комментаторов серии постов Чена про безблокировочные алгоритмы поинтересовался, в каких условиях эти более сложные алгоритмы существенно превосходят по производительности такие простые примитивы блокировки, как критические секции.

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

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

Следуя совету хабрапублики, пробую новый вариант перевода термина "lock-free"

В прошлый раз мы видели «беззахватный по духу» алгоритм, где захват был реализован так, что поток, обращающийся к захваченным данным, не ждёт их освобождения, а отправляется «обходным путём» (вычисляет требуемый результат, не пользуясь услугами кэша). В своём следующем посте Реймонд объясняет, как данный алгоритм можно усовершенствовать на случай, когда «обходного пути» нет. Алгоритм, однако, остаётся беззахватным: каждый поток продолжает работать, не дожидаясь освобождения захваченных данных.

В общей переменной теперь нужны два служебных бита: вдобавок к флагу захвата, как в прошлом примере, — флаг «поручена новая работа»; а если порученная работа сложная, то кроме флага, нужно будет где-то хранить ещё и её параметры. Например, в общей переменной можно хранить указатель на (выравненный в памяти) объект с параметрами, а в свободных младших битах указателя — два названных флага.

Перед выполнением действия над объектом, первым делом мы его захватываем, атомарно устанавливая соответствующий флаг. Если окажется, что объект уже был захвачен, — поручим выполнение нашего действия захватившему потоку, установив второй флаг.

Если же объект удалось захватить, то после завершения работы с ним снимаем флаг захвата и одновременно проверяем, не поручили ли нам новую работу. (Т.е. не было ли обращений к объекту за то время, пока мы его держали захваченным.) Если есть работа, то мы выполним и её; и так далее, пока однажды при разблокировке объекта отложенной работы не окажется. Мы не вправе оставить объект в состоянии «не захвачен, но есть работа».

(Тот факт, что русского перевода понятию «lock-free» в литературе ещё не устоялось, — нисколько меня не убеждает, что такого перевода не должно быть.)

Предположим, анализ производительности вашего приложения выявил, что существенная часть процессорного времени тратится в некой вычислительной функции, и более того, эта функция многократно вызывается с одними и теми же параметрами — выполняя одинаковые вычисления вновь и вновь. Напрашивается простая оптимизация — кэш из одной записи, в котором бы хранились исходные данные и результат последнего вычисления.

BOOL IsPrime(int n)
{
 static int nLast = 1;
 static BOOL fLastIsPrime = FALSE;

 // если значение параметра не изменилось с прошлого раза,
 // воспользуемся готовым результатом
 if (n == nLast) return fLastIsPrime;

 // вычислим и запомним новый результат
 nLast = n;
 fLastIsPrime = slow_IsPrime(n);
 return fLastIsPrime;
}

Само собой, этот код потоконебезопасен: если один поток находится внутри вызова slow_IsPrime(), то другой поток, вызвавший IsPrime(), застанет значения переменных nLast и fLastIsPrime несоответствующими одно другому.

Простое решение — заключить код в критическую секцию; но простота идёт в ущерб производительности: если, скажем, nLast = 5, fLastIsPrime = TRUE, и два потока одновременно вызывают IsPrime(5), то совершенно ни к чему им выстраиваться в очередь: ничего не мешает им одновременно воспользоваться кэшированным значением.

Посмотрим, как можно реализовать наш кэш беззамочно.

Реализованное нами в прошлый раз атомарное умножение является примером более общей модели, которую Реймонд назвал «сделай, запиши,(попытайся снова)».

for (;;) {
 // берём начальное значение общей переменной,
 // которую мы собираемся изменять
 oldValue = sharedVariable;

 ... берём начальные значения других параметров ...

 newValue = ... вычисляем новое значение, используя
                oldValue и копии остальных параметров ...

 // вместо Xxx может быть Acquire, Release, или ничего
 if (InterlockedCompareExchangeXxx(
            &sharedVariable,
            newValue, oldValue) == oldValue) {
  break; // запись удалась
 }

 ... удаляем newValue ...

} // попытаемся снова

Мы вычисляем новое значение, и затем вызовом InterlockedCompareExchange записываем его в общую переменную только в том случае, если её значение не изменялось. Если оно изменилось, значит другой поток нас опередил; в этом случае попытаемся выполнить операцию по-новой, с самого начала, — в надежде, что в следующий раз никто нас не «подрежет».

Реймонд Чен написал занятную серию блогпостов о беззамочной синхронизации. Мне бы хотелось опубликовать эти заметки и для хаброчитателей. Данный пост — введение в серию, скомпилированное из трёх старых постов Чена.

1. Ленивая инициализация встроенными средствами C++
2. Беззамочная синхронизация
3. Беззамочная потоко-безопасная ленивая инициализация

Ленивая инициализация встроенными средствами C++

Инициализация статических локальных переменных в C++ непотокобезопасна, причём намеренно!

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

Попытайтесь сами найти рейс-кондишн во фрагменте кода, который вычисляет результат некоторой функции «лениво» — при первом обращении, и затем сохраняет этот результат для последующих обращений.

int ComputeSomething()
{
  static int cachedResult = ComputeSomethingSlowly();
  return cachedResult;
}

(Примерно такой код советуют в популярном C++ FAQ, чтобы не зависеть от выбранного компилятором порядка инициализации глобальных статических переменных.)

Первая статья об экспериментальном определении характеристик кэш-памяти появилась на свет несколько необычным образом. Играясь с утилитами из lmbench, я получил те самые три графика, и задался вопросом, сколько же информации об исследуемой системе можно из них вытянуть. Определив некоторые характеристики кэша и TLB, я затем задал эти графики студентам как домашнее задание — предвкушая, что им удастся обнаружить что-то такое, что я проглядел. В целом, студенты меня разочаровали, и не заметили даже связь ассоциативности с наклоном ступенек на графике. В конце семестра я собираюсь рассказать им своё решение; а чтобы оно к тому времени не забылось, я написал на скорую руку ту статью.

Затем Yekver предложил мне идею простой программы для Windows, которая определяла бы характеристики кэша автоматически, не требуя ручного анализа графиков. (Тем более, что версии lmbench для Windows не существует.) Для замера времени будем использовать функцию __rdtsc, которая возвращает 64-битное количество тактов с момента последнего сброса процессора. Сначала определим тактовую частоту процессора, замерив на произвольной нагрузке время выполнения и количество потребовавшихся тактов. Затем для расчёта времени доступа к памяти будем делить количество потраченных тактов на тактовую частоту процессора.

Подобно прошлому эксперименту, мы будем брать данные различного объёма от 4КБ до 512МБ, и проходить по массиву миллионы раз с последующим усреднением результата. Чтобы минимизировать влияние дополнительных операций в цикле нагрузки, следуя примеру авторов lat_mem_rd, используем для тела нагрузки операцию p=(void**)*p;, которая компилируется в одну машинную команду, и развернём её 256 раз, чтобы возврат к началу цикла выполнялся относительно редко.

«Если я системными политиками запрещаю значки на рабочем столе, то от двойного щелчка по нему начинает запускаться Диспетчер задач. Что за чудеса?»

Это примерно такое же открытие, какое сделал один мой коллега, убравший в своём старом доме декоративные панели, и обнаруживший за ними забытый чулан. В чулане он нашёл несколько раритетов времён Второй мировой войны, включая алкогольный талон с несколькими непробитыми ячейками. Сложно представить, что чувствовал владелец талона, забывший его в чулане.

Чулан, скрытый за рабочим столом Windows, — это Диспетчер программ, оставшийся со времён Windows 3.0. Диспетчер программ позволял запускать приложения, но не позволял переключаться между ними: в нём не было аналога панели задач, отображавшей все запущенные приложения. Чтобы увидеть список открытых окон, пользователь запускал Диспетчер задач — горячей клавишей Ctrl+Esc, либо двойным щелчком по пустому месту на рабочем столе.

Кроме возможности перейти к любому из открытых окон, Диспетчер задач позволял также закрыть приложения, или упорядочить окна — например, каскадом. Диспетчер задач был единственным местом в Windows, показывавшим открытые окна одновременно: например, Alt+Tab не показывал значки всех окон, как в современных версиях Windows, а переключался между ними по порядку.

Появившаяся в Windows 95 панель задач позволяла видеть все открытые окна и переключаться между ними в любой момент; Диспетчер задач был для этого больше не нужен. Кроме того, свёрнутые окна ложились теперь в панель задач, а не на рабочий стол, как в Windows 3.0. Из места для значков свёрнутых окон, рабочий стол превратился в место для часто используемых ярлыков.

Рабочий стол в Windows 95 — это окно Проводника, растянутое на весь экран, и расположенное ниже окон всех других программ. В этом окне Проводник отображает содержимое папки «Рабочий стол». Но под этим «рабочим столом» остался другой, настоящий рабочий стол,

В ряде случаев (например, для тонкой оптимизации программы под конкретный компьютер) полезно знать характеристики кэш-подсистемы: количество уровней, время доступа к каждому уровню, их размер и ассоциативность, и т.п.
Для одноразовой оптимизации необходимые значения можно посмотреть в спецификации на компьютер, но когда требуется автоматическая оптимизация (например, во время сборки и установки программы), характеристики приходится определять косвенно, по результатам прогона специального набора тестов.
Удобная тестовая программа для Linux — lat_mem_rd из пакета тестов lmbench. Её работа заключается в том, что она выделяет в памяти массив и читает его элементы с заданным шагом, циклически проходя по массиву снова и снова. Затем выделяется массив большего размера, и т.д. Для каждого значения шага и размера массива подсчитывается среднее время доступа.
Пример графика, который был получен этой программой на реальной системе:

Непонятно, почему люди относятся к программам, загружающим процессор на 100%, так, как будто эти программы без конца пинают беззащитных маленьких щенят. Им кажется, что столбец в Диспетчере задач — это счётчик: сколько щенят в секунду пинает программа.

Успокойтесь. Если программа загружает процессор на 100% и ничего при этом не делает, то, пожалуй, её можно отнести к бесстыдным пинателям щенят. Но если программа работает, и использует все 100% для своей работы, — то её, наоборот, стоит похвалить за эффективную работу!

Представьте себе: пусть нагрузка вашего процессора никогда не превышала бы 50%. Выходит, вы используете компьютер лишь наполовину; не значит ли это, что вы просто переплатили за него двойную цену? Задача, которая выполнилась бы за пять минут при полной загрузке, выполняется у вас за десять минут; но зато драгоценный индикатор загрузки никогда не переходит воображаемую «красную черту». (Обратите внимание: в Windows на этом индикаторе нет никакой красной черты.)

Например, один программист спрашивал, как изменить программу, чтобы она меньше загружала процессор, но при этом выполняла работу «за разумное время». Чего ради уменьшать загрузку? Почему вместо того, чтобы закончить работу как можно быстрее, — программа должна беспокоиться о циферках в Диспетчере задач?

Если бы вы заведовали банком, в котором работают десять клерков, и туда ломилась бы толпа посетителей, — вы бы впустили их, чтобы все десять клерков работали, или оставили бы посетителей ждать в очереди, чтобы загружать клерков не более чем наполовину?

(Windows была выпущена 20 ноября 1985. Сегодня ей исполняется 25. С днём рождения!)

В Windows API с самого начала есть две отдельные функции GetWindowsDirectory и GetSystemDirectory. Почему недостаточно было одной? Обе эти системные папки защищены от записи, обе входят в PATH и в список поиска DLL-библиотек. Зачем было их разделять?

Аксакалы вспомнят, что в те давние времена назначение этих папок различалось. Папка Windows была доступна для записи, и именно в ней хранились все настройки пользователя. Например, функция GetProfileInt читает из файла WIN.INI в папке Windows, и функция GetPrivateProfileInt, если не указан полный путь INI-файла, по умолчанию работает с папкой Windows.
В те давние времена не было отдельных папок с профилями пользователей; в папке Windows, по сути, хранился профиль единственного пользователя в системе.

С другой стороны, большинство системных файлов Windows хранилось в папке System, и эта папка использовалась только для чтения. Даже если не было механизма, фактически запрещавшего запись в эту папку, — сама Windows никогда в неё не писала (исключая установку и удаление приложений, и прочие операции по настройке системы).

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

Многие помнят программу «Dr.Watson», появившуюся в бета-версии Windows 3.0, и живую до сих пор — правда, уже под названием «Windows Error Reporting». В своём исходном варианте Dr.Watson записывал в лог-файл данные об ошибках в программах, чтобы этот файл можно было приложить к баг-репорту. Значком Dr.Watson был дружелюбный доктор со стетоскопом.



Большинству неизвестно, что вначале эта программа называлась иначе.

Дело началось с того, что одна небольшая английская компания решила рассылать рекламные листовки своим существующим и потенциальным клиентам.
Обнаружилась проблема: есть отдельная внутренняя база клиентов, делавших заказы по телефону; отдельная база веб-клиентов, делавших заказы на сайте; и несколько баз «потенциальных клиентов» от разных информаторов.
Тысячи клиентов попали сразу в несколько баз, или даже несколько раз в одну базу.
Если клиент, «засветившийся» пять раз, получит пять одинаковых рекламных листовок с немного отличающимся написанием имени или адреса, то эффект от такой кампании получится противоположный — не говоря уже о бессмысленных расходах на лишние листовки.
Как же отсеять повторы в списке рассылки?

Среди всех данных о клиенте самое однозначное, что его определяет — это почтовый индекс (postcode). Этого мало, но это хорошая отправная точка.

Екатерина Лажинцева занимается русификацией продуктов Microsoft ещё со времён Windows for Workgroups. Некоторое время она публиковала в своём ЖЖ занятные случаи из прошлых локализаций, включая историю приснопамятного «приложеньица» в IE 4.0.

И он отчасти от неопытности, отчасти в пылу молодого задора переводил не совсем обычным образом. Много чего мы все-таки вернули в более привычный вид, но вот «приложеньице запущено» было замечено слишком поздно, когда строка уже ушла из Ирландии в Редмонд для включения в Java-машину, и исправить это нам уже не дали. (из других интересных переводов: Access denied «В притязаниях отказано».)

В настройках JVM необычные переводы отыскиваются до сих пор:

В первом выпуске Windows 95 можно было выбрать часовой пояс, кликнув по точке на карте мира; выбранный часовой пояс подсвечивался более ярким цветом.

Аналогичным образом в бета-версиях Windows 95 можно было выбирать и локаль («Язык и стандарты»).

Обе карты прожили лишь считанные месяцы: карта локалей не дожила даже до релиза; карта часовых поясов — до первого сервис-пака. Хотя границы отображались в соответствии с официально признанными ООН, недовольные их расположением не заставили себя долго ждать.

Newsgroups: rec.humor.funny
Oganization: Netscape Communications Corp.
Subject: Mozilla stomps IE
From: francis@netscape.com (John Francis Stracke)
Date: Sat, 4 Oct 97 3:20:05 EDT

Ладно, имейте в виду, что я не видел сам, как это было; мне рассказали, когда всё уже закончилось, и показали результат. Но:

В прошлую полночь (с 30.09 на 1.10) вышел новый Браузер мистера Билла, IE 4.0. Между полуночью и 1:30 кто-то (кто бы это мог быть?) притащил огромный символ IE и поставил его на газоне перед зданием Netscape. Конструкция была металлическая, достаточно толстая, чтобы стоять стоймя. Наверное, они думали, что мы до утра ничего не заметим; а пока успеем подогнать технику, чтобы убрать скульптуру, репортёры уже успеют её сфотографировать. Мы не сможем обратиться в суд, потому что у нас нет на MS никаких улик, и будем выглядеть обиженными ботаниками.

Не стоит и говорить, что MS облажались. Они забыли, что в полночь мы всё ещё на работе! Кто-то заметил на газоне новое украшение, и не стал терять зря силы на попытки его убрать. Они решили показать Биллу, чего они стоят: собрали всех, кого смогли найти, опрокинули символ наземь, и написали баллончиком «Netscape Now» на боку. Потом они притащили нашу двухметровую фигуру Мозиллы (чудища-талисмана Netscape), и поставили её сверху на логотип IE.



Теперь Мозилла стоял на теле поверженного противика с довольной ухмылкой, поднимая большой палец. Вокруг ходили репортёры и снимали. Его показали по телевизору и в местных газетах; говорят, даже у Рейтер вышел репортаж. Мы не в восторге от того, что дело получило огласку, слишком уж всё по-ребячески… Но они первые начали! :-)

Рейтер: Microsoft после гулянки подшутили над Netscape