331
Воспользуйтесь колесиком мышки чтобы настроить масштаб
aaaadddaaaa
TStupid или "НОВЕЙШИЙ ОРГАНОН". ПРИМЕР 3

Приложения ТРИЗ к программированию

© Сергей Сычёв, TRIZ-RI Group, Кирилл Лебедев, г. Санкт-Петербург

Приложения ТРИЗ к программированию. Пример 3. Пусть само проявится...


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

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

Остальное понятно из контекста разбираемых примеров.


ПРИМЕР 3. "ПУСТЬ САМО ПРОЯВИТСЯ..."

Шаг 0. Что мы имеем? (описание языком программиста)
Шаг 1. Абстрагируемся
Шаг 2. Пишем абстрактное решение (понятное любому)
Шаг 3. Переводим "абстрактное решение" на привычный для программиста язык


ШАГ 0
ЧТО МЫ ИМЕЕМ?

В одной библиотеке происходили значительные утечки памяти. По некоторым причинам (их описание выходит за рамки данного материала) утечки нельзя было обнаружить при помощи отладчика. Поэтому в исходном коде были переопределены операторы new и delete.

Переопределенный оператор new выделял блок памяти чуть большего размера, чем запрашивал у него пользователь. В дополнительную область заносилась служебная информация, а указатель на блок сохранялся в списке. Оператор delete удалял указатель из списка и освобождал блок памяти, на который он указывал.

По завершению работы программы информация о блоках памяти, которые содержал список, выводилась в файл. Таким образом, можно было составить представление о том, какой объем памяти был не освобожден.

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

Переопределенный оператор new имел вот такой вид:

T * pT = new T;

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

Тогда решили (для установления соответствия между структурами данных и блоками памяти, которые не были освобождены) в каждый оператор new передавать не только запрашиваемый размер, но и информацию о файле и строке, откуда данный оператор был вызван:

T * pT = new(__FILE__, __LINE__) T;

Для этого написали специализированную версию оператора new, которая принимает на вход все необходимые параметры:

void * operator new(const size_t nSize, const char * pszFileName, const size_t nLine)
{
...
}

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

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

#define new new(__FILE__, __LINE__)

после подстановки которого любой код вида:

// Используется обычная версия оператора new
T * pT = new T; 

будет эквивалентен такому коду:

// Используется расширенная версия оператора new
T * pT = new(__FILE__, __LINE__) T; 

К сожалению, и этот трюк не работал корректно. Бездумная подстановка изменяла не только вызовы оператора new, но и места, где он был объявлен. Многие классы библиотеки содержали свои специализированные версии операторов new и delete:

class Object
{
public:
  ... 
   void * operator new(const size_t nSize); 
   void operator delete(void * pData); 
  ...
}

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

Вот простая аналогия, взятая из данного источника: Соколов Г.Б., реплика на Форуме www.triz-ri.ru/forum со ссылкой на профессора мат. лингвистики Тузова:

"В русском языке можно:

  • разбить сквер,
  • разбить палатку,
  • разбить вазу,
  • разбить морду".

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

  • разрушить сквер,
  • разрушить палатку,
  • разрушить вазу,
  • разрушить морду.

Как минимум, в двух местах из 4-х, смысл выражения поменялся на прямо противоположный. Получается, что надо читать каждую фразу и в каждом случае подбирать свой синоним.

А теперь представим себе объем текста размером с "Анну Каренину"...

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

И как же быть? И даже не просто "как быть", а какую задачу решать?

Решать ли задачу о том, как передать оператору new дополнительные параметры, не понаделав ошибок? Или, все-таки, лучше думать о том, как иным способом (каким?) найти те некоторые вызовы оператора new (из множества возможных), которые и приводят к утечке.

А Вы как считаете?


ШАГ 1
АБСТРАГИРУЕМСЯ

В рамках плановой борьбы с собственным тупым времяпрепровождением тупые депутаты партии "Вертикаль вместо извилин" приняли высоконравственный закон: "О запрете чтения книг, содержащих нецензурные слова". Все бы ничего, но как быть большим библиотекам? По закону библиотекари теперь не имеют права без санкции прокурора выдавать книгу, если таковая содержит хотя бы одно матерное слово. И как же это определить?

Всех книг не перечитаешь, а что касается прогнозов, то библиотекари могут догадываться только о контекстах (жанрах, темах, направлениях), где можно встретить мат, но, во-первых, вряд ли они в состоянии верно все эти контексты даже предположить, а уж о том, чтобы перебрать, можно и не мечтать вовсе. И что же делать?


ШАГ 2
ОПИШЕМ АБСТРАКТНОЕ РЕШЕНИЕ

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

Библиотекарь, услышав сигнал, смотрит запись в карточке читателя (что он взял) и фиксирует: в каком первоисточнике такое бывает и сколько раз.

Затем эти записи в карточках читателей собираем и заводим еще один раздел в библиотечном классификаторе «Матерное», который внутри тоже дробим на подконтексты (в зависимости от того, к какому направлению относится тот или иной первоисточник).

Через некоторое время структурированная картина мата проявляется и детализируется сама собой. Хоть снимай на видео и показывай потом в ускоренном режиме.


ШАГ 3
ПЕРЕВЕДЕМ "АБСТРАКТНОЕ РЕШЕНИЕ" НА ПРИВЫЧНЫЙ ЯЗЫК

Вместо того чтобы перебирать огромное количество вызовов оператора new, определяем, при выполнении каких операций происходят утечки памяти. Затем, открываем исходный код программы и находим функцию, которая отвечает за выполнение этих операций. Если такую функцию найти сложно, то берем главную функцию программы. Найденную функцию дробим на контексты.

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

НАПРИМЕР,

// Дробим основную функцию программы на контексты

void MainFunction()
{
   push("Context 1");
   DoSomething_1();
   pop();
   push("Context 2");
   DoSomething_2();
   pop();
  ...
   push("Context N");
   DoSomething_N();
   pop();
}

// Дробим дальше функции на подконтексты

void DoSomething_1()
{
   push("Action1");
   T * pT = new T();
   DoAction_1(pT);
   pop();
   push("Action 2");
   Other * pOther = new Other();
   Do_Action_2(pOther);
   pop();
}

Сами контексты мы объединяем в стек и предоставляем функции push и pop для работы с ним. Функция push помещает новый контекст в вершину стека, а функция pop – наоборот, извлекает контекст из вершины стека, а на его место помещает другой контекст, который находится в стеке перед извлеченным. Используя эти процедуры, мы можем разбить любую процедуру на контексты, а любой контекст – на подконтексты и т.п.

// Размер стека
static const int MAX_CONTEXT = 100;

// Стек контекстов
static const char * g_ContextStack[MAX_CONTEXT];

// Количество контекстов в стеке
static int g_iContextCount = 0;

// Помещает контекст в стек
void push(const char * pszContext)
{
   assert(g_iContextCount < MAX_CONTEXT);

   // Помещаем контекст в вершину стека. Затем - увеличиваем количество элементов в стеке
   g_ContextStack[g_iContextCount++] = pszContext;
}

// Выталкивает контекст из стека
void pop()
{
   assert(g_iContextCount > 0);
   --g_iContextCount;
}

// Возвращает вершину стека (текущий контекст)
const char * CurrentContext()
{
   assert(g_iContextCount > 0 && g_iContextCount    return g_ContextStack[g_iContextCount - 1];
}

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

struct TMemBlock

{
   unsigned long m_ulSize;
   const char * m_pszContext;
};

void * operator new(size_t nSize)
{
   if (nSize > 0)
   {
      void * pData = malloc(nSize + sizeof(TMemBlock));
      if (pData)
      {
// Преобразуем указатель pData к указателю на TMemBlock
         TMemBlock * pMemBlock = (TMemBlock *)pData;
         pMemBlock->m_ulSize = nSize + sizeof(TMemBlock);
         pMemBlock->m_pszContext = CurrentContext();

        Добавляем pMemBlock в список выделенных блоков;

        // Возвращаем указатель на часть памяти за pMemBlock
         return pMemBlock + 1;
      }
   }
   return NULL;
}

void operator delete(void * pData)
{
   if (pData)
   {
      // Получаем указатель на TMemBlock
      TMemBlock * pMemBlock = ((TMemBlock *)pData) - 1;

      Удаляем pMemBlock из списка выделенных блоков;

      // Освобождаем память
      free(pMemBlock);
   }
}

Алгоритм поиска места утечки прост. Сначала мы находим последовательность действий, при выполнении которой теряется память. Затем, открываем исходный код и находим функцию, которая отвечает за выполнение этой последовательности. Если такую функцию найти сложно, то берем главную функцию программы. Найденную процедуру разделяем на контексты, компилируем и запускаем программу.

Тем самым мы распределяем все множество операторов new между контекстами.

После завершения программы, анализируем лог-файл и находим контексты, в которых произошли утечки. Если необходимо, "дробим" их дальше на подконтексты. После чего повторяем алгоритм...

Примечание.
Разбор этой же задачи иным способом - см. в статье: С.В. Сычев, К.А. Лебедев "Как вспомнить "и так известное".

Другие примеры раздела TStupid - см. здесь и здесь.

Материал опубликован на сайте "Открытые методики рекламы и PR "Рекламное Измерение" 17 октября 2005 г.

aaaadddaaaa