Как я искал баг, которому 20 лет

Знаете, что меня зацепило в этой истории? Человек, родившийся в 2004 году, каждый день использует оконный менеджер 1997 года выпуска. И не просто «ностальгирует ради фана» — нет, это её основная рабочая машина. 24 МБ оперативной памяти, полная кастомизация, абсолютный контроль через клавиатуру. И вот в какой-то момент весь рабочий стол зависает намертво при открытии PDF-файла с лекциями.

Дедлайн по презентации — не самое удачное время для встречи с 20-летним багом.

Разбираемся, что произошло

Автор статьи — Kamila Szewczyk, редактор блога Iczelia — работала над слайдами для своего курса. Обычная ситуация: открыла PDF в Atril (это просмотрщик документов в MATE), и всё — рабочий стол замер. Ничего не реагирует, мышь не двигается, клавиатура мертва.

Первое, что приходит в голову — deadlock (взаимная блокировка). Но оказалось, что нет. Программа не зависла совсем — она медленно, но верно выполняла какую-то работу. Каждый раз при открытии этого конкретного PDF-файла.

Привязка отладчика к живому процессу показала странную картину: все вызовы крутились вокруг кэша шрифтов в библиотеке imlib2. Причём функция получения глифа (глиф — буква или символ шрифта) вызывалась с разными индексами — 0, 20, 73, 81, 82, 87, 88… То есть внутри что-то двигалось, но зависало где-то снаружи.

Ключевым оказался фрейм номер 8 — функция TextstateTextFitMB. Она отвечает за обрезание текста, который не помещается в отведённое место. Представьте: у вас есть заголовок окна «Kickoff.pdf — Introduction to Physics» и декорация окна может вместить только 291 пиксель. Что делать? Правильно — выкинуть буквы из середины и поставить троеточие. Получится что-то вроде «Kickoff…sics».

Математика, которая сломалась

Вот здесь и происходит самое интересное. Функция использует вариант метода Ньютона для итеративного подбора количества символов для удаления. Идея простая: удаляем сколько-то букв, меряем результат, смотрим — помещается или нет. Если нет — удаляем ещё (или добавляем обратно). И так до тех пор, пока не получим нужную ширину.

Но вот проблема: метод Ньютона converge (сходится — достигает правильного результата) только при определённых условиях. Если производная слишком мала или функция ведёт себя нелинейно — алгоритм начинает колебаться между двумя состояниями.

Посмотрите на дамп переменных:

nuke_count = 8   nc2 = 36   wc_len = 81   len_n = 76
nuke_count = 11  nc2 = 35   wc_len = 81   len_n = 73
nuke_count = 8   nc2 = 36   wc_len = 81   len_n = 76
...

Один и тот же текст. Две попытки. Бесконечно. nuke_count (количество удаляемых символов) прыгает туда-сюда: 8 → 11 → 8 → 11… Метод Ньютона не может найти решение и осциллирует (повторяется по кругу, колеблется между двумя состояниями).

Диагностика в картинках

ОСЦИЛЛЯЦИЯ МЕТОДА НЬЮТОНА
═══════════════════════════

попытка 1   попытка 2
    │           │
    ▼           ▼
 nuke_count
    ▲
 11 ┤       ╭──╮      ╭──╮
   │   ╭────╯  ╰──────╯  ╰─────
 8 ┤───╯                           (8 → 11 → 8 → ...)
   │
   └─────────────────────────────▶
              итерация

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

Вывод

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

Исправили? Патч отправили в апстрим FreeType — добавили ограничение на количество итераций и защиту от осцилляций через проверку изменения знака между итерациями.

Но главный вывод для меня другой: иногда самые безумные баги живут десятилетиями просто потому, что воспроизводятся только в очень специфических условиях. Конкретная ширина окна + конкретный шрифт + конкретный PDF = идеальный шторм из математической нестабильности.

Ссылки

• Fixing a 20-year-old bug in Enlightenment E16 — оригинальная статья Kamila Szewczyk
• Atril — просмотрщик документов в MATE
• imlib2 — библиотека для работы с изображениями