Библиотека Judy для работы с динамическими массивами

PDF

Компоненты библиотеки

Judy1 отображает индекс (Index — word) на бит.

JudyL отображает индекс (Index — word) на Value (word/указатель).

JudySL отображает индекс (строка с null-завершением) на Value.

JudyHS отображает индекс (массив байтов) размером Length на Value.

Judy представляет собой библиотеку C для создания и использования динамических массивов. Библиотека была предложена и реализована Doug Baskins из Hewlett-Packard.

Семейство функций и макросов поддерживает полностью динамические массивы, которые могут индексироваться 32- или 64-битовыми словами (в зависимости от размера word для процессора), строками с null-символом в конце или массивом байтов заданного размера. Динамический массив (разреженный) можно также считать функцией отображения или ассоциативной памятью.

Тип Word_t определен как typedef unsigned long int в файле Judy.h и должен иметь размер sizeof(void *), т. е. указателя.

В функциях Judy1 Index имет тип Word_t, а Value — просто бит (bit) или флаг наличия (отсутствия) Index в массиве. Этот можно рассматривать как огромное битовое поле (huge bitmap).

В функциях JudyL Index и Value имеют тип Word_t. В результате JudyL является чистым отображением слова на слово (указатель). JudySL и JudyHL базируются на этом свойстве JudyL.

В функциях JudySL Index является строкой с null-символом в конце, а ValueWord_t.

В функциях JudyHS Index является массивом байтов размера Length, а Value имеет тип Word_t. Дополнение (май 2004 г.) в Judy является гибридом, в котором используются лучшие качества методов хещирования и Judy. Автор надеется, что JudyHS послужит хорошей заменой методов хэширования, когда размер хэш-таблицы меняется при росте численности. Корректно настроенный метод хеширования со статическим размером таблицы и численностью непобедим по скорости. Обнако JudyHS будет работать лучше с численностью, отличающейся от оптимального размера хэш-таблицы. JudyHS не теряет производительности в тех случаях, где это известно для алгоритмов хэширования. JudyHS не использует связный список для обработки конфликтов хэш-значений, применяя взамен дерево массивов JudyL и виртуальную хэш-таблицу размером 4 миллиарда.

Массивы Judy являются быстрыми и небольшими по памяти, не требуют найтройки для широкого диапазона типов набора индексов (последовательные, периодические, кластерные, случайные). Judy обычно превосходит по скорости и экономии памяти другие модели хранения данных, такие как skip-списки, связные списки, двоичные, троичные и b-деревья и даже хэширование, а также повышает эффективность работы при очень больших размерах данных.

Массив Judy создается просто путем определения пустого (null) указателя, а затем по этому указателю сохраняется (вставляется) первый элемент массива. Используемая массивом Judy память примерно пропорциональна численности (количеству элементов).

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

Поскольку исходный (пустой) массив Judy представляется null-указателем, можно создать массив массивов Judy. Т. е. значениями массива Judy (Value), кроме Judy1, могут быть указатели на другие массивы Judy. Это существенно упрощает создание массивов произвольной размерности или значения Index (массивы JudySL и JudyHS используют для этого JudyL).

Файлы

/usr/share/doc/Judy/ — страницы руководства в формате HTML;
/usr/share/doc/Judy/demo/ — примеры файлов исходного кода.

Ошибки

На упрощение обработки ошибок в Judy было затрачено много сил и времени, что позволило сохранить гибкость и функциональность. Тема обработки ошибок достаточно скучна, но упускать ее нельзя. Из описанных здесь методов рекомендуется применять второй. Он создает наиболее быстрый код, используя минимальный объем памяти и требует написания дополнительного кода лишь для функций вставки и удаления. Метод совместим с двумя другими и предназначен для создания кода, который может обрабатывать отказы malloc() иначе, чем принято по умолчанию в Judy. Если принятый по умолчанию метод Judy работает хорошо, имеет смысл применять его.

Имеется две категории ошибок, возвращаемых Judy (и другими динамическими ADT):

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

  2. Нехватка памяти (отказ malloc()) при вставке (Insert, Set) или удалении (Delete, Unset) для изменения массива Judy. Для вставки или удаления не всегда применяется функция malloc(), поэтому операции могут быть успешными даже при отказе malloc().

Имеется три метода обработки ошибок при использовании макросов

  1. Принятый по умолчанию метод выводит сообщение об ошибке в stderr. Например,

File 'YourCfile.c', line 1234: JudyLIns(), JU_ERRNO_* == 2, ID == 321

Это говорит об ошибке в строке 321 функции JudyLIns(). Проблема возникла в строке 1234 файла YourCfile.c, где произошел отказ JLI(). JU_ERRNO_* == 2 указывает JU_ERRNO_NOMEM (определена в файле Judy.h). Идентификатор ID указывает номер строки исходного файла, где произошла ошибка. Программа была прервана с возвратом exit(1);. По умолчанию обе категории ошибок Judy обрабатываются этим методом.

  1. Запрет обработки ошибок в макросах

    Когда в программе «нет ошибок», сообщения могут выдаваться лишь для отказов malloc() и все возвращаемые ошибки можно считать такими отказами. Используя показанный ниже оператор #define, можно отключить все проверки и вывод ошибок. К коду, который может приводить к отказам malloc(), потребуется добавить специальный код. Judy сохраняет в массиве данные, присутствовавшие до вызова, в случаях отказа malloc()1.

#define JUDYERROR_NOTEST 1

в программном коде или

cc -DJUDYERROR_NOTEST sourcefile -lJudy

в командной строке.

//Пример использования метода 2 в программе.
    
JLI(PValue, PLArray, Index);
if (PValue == PJERR) goto out_of_memory_handling;
...

JLD(RC_int, PLArray, Index);
if (RC_int == JERR) goto out_of_memory_handling;
...

J1S(RC_int, P1Array, Index);
if (RC_int == JERR) goto out_of_memory_handling;
...

J1U(RC_int, P1Array, Index);
if (RC_int == JERR) goto out_of_memory_handling;
...

Отметим, что без определения JUDYERROR_NOTEST операция goto out_of_memory_handling не будет выполняться и компилятор исключит ее при оптимизации. Будет использован принятый по умолчанию метод использования макроса для вывода сообщения об ошибке, как описано выше. При определении JUDYERROR_NOTEST операция goto out_of_memory_handling будет выполняться в случае возникновения ошибки (отказ malloc()).

  1. Заданный пользователем макрос JUDYERROR()

    Макрос JUDYERROR(), определенный в файле Judy.h обеспечивает гибкую обработку ошибок, позволяющую программе использовать макросы массивов Judy вместо вызова функций. Можно использовать свой макрос JUDYERROR(), соответствующий реальным задачам. Ниже приведен пример возможного варианта взамен принятого по умолчанию. Он служит для различения двух типов ошибок и явно1 проверки остальных ошибок JU_ERRNO_NOMEM, которые могут возникать в программе.

// Пример Judy macro API для продолжения работы при нехватке памяти,
// вывода сообщения и возврата exit(1) при возникновении ошибки.

#ifndef JUDYERROR_NOTEST
#include <stdio.h>  // нужен для fprintf()

// Макрос, используемый Judy macro APIs для возврата кода -1:

#define JUDYERROR(CallerFile, CallerLine, JudyFunc, JudyErrno, JudyErrID) \
{                                                                         \
    if ((JudyErrno) != JU_ERRNO_NOMEM) /* не отказ malloc() */         	  \
    {                                                                     \
        (void) fprintf(stderr, "File '%s', line %d: %s(), "               \
            "JU_ERRNO_* == %d, ID == %d\n",                               \
            CallerFile, CallerLine,                                       \
            JudyFunc, JudyErrno, JudyErrID);                              \
        exit(1);                                                          \
    }                                                                     \
}
#endif // не определено JUDYERROR_NOTEST

Этот макрос обработки ошибок должен включаться в программу до оператора #include <Judy.h>.

Judy1

Макросы Judy1

Макросы Judy1 представляют собой библиотеку C для создания и использования динамического массива битов. Индексом массива может служить любое значение слова (word).

Массив Judy1 эквивалентен массиву или отображению (map) битов, адресуемому Index (ключ). Массив может быть разреженным (sparse), а Index может быть любым значением (Value) размера word. Наличие индекса представляет установленный (set) бит, а такой бит представляет наличие индекса. Отсутствие индекса представляет сброшенный (unset) бит, а сброшенный бит представляет отсутствие индекса.

Массив Judy1 выделяется с указателем NULL

Pvoid_t PJ1Array = (Pvoid_t) NULL;

Память для поддержки массива выделяется при установке бита и освобождается при его сбросе. Если указатель Judy1 (PJ1Array) имеет значение NULL, это говорит, что все биты сброшены (для массива Judy1 не требуется памяти).

Как и обычные массивы Judy1, не имеет дубликатов индексов.

При использовании описанных здесь макросов вместо вызова функций Judy1 принятая по умолчанию обработка ошибок передает сообщение на стандартный вывод ошибок и завершает программу с кодом exit(1). Другие методы обработки ошибок рассмотрены в разделе Ошибки.

Поскольку макросы иногда быстрее и включают более эффективную обработку ошибок по сравнению с функциями, их применение является предпочтительным в Judy1.

Синтаксис

cc [flags] sourcefiles -lJudy
#include <Judy.h>

int     Rc_int;                          // Код возврата - integer
Word_t  Rc_word;                         // Код возврата - unsigned word
Word_t  Index, Index1, Index2, Nth;

Pvoid_t PJ1Array = (Pvoid_t) NULL;       // Инициализация массива Judy1

J1S( Rc_int,  PJ1Array, Index);          // Judy1Set()
J1U( Rc_int,  PJ1Array, Index);          // Judy1Unset()
J1T( Rc_int,  PJ1Array, Index);          // Judy1Test()
J1C( Rc_word, PJ1Array, Index1, Index2); // Judy1Count()
J1BC(Rc_int,  PJ1Array, Nth, Index);     // Judy1ByCount()
J1FA(Rc_word, PJ1Array);                 // Judy1FreeArray()
J1MU(Rc_word, PJ1Array);                 // Judy1MemUsed()
J1F( Rc_int,  PJ1Array, Index);          // Judy1First()
J1N( Rc_int,  PJ1Array, Index);          // Judy1Next()
J1L( Rc_int,  PJ1Array, Index);          // Judy1Last()
J1P( Rc_int,  PJ1Array, Index);          // Judy1Prev()
J1FE(Rc_int,  PJ1Array, Index);          // Judy1FirstEmpty()
J1NE(Rc_int,  PJ1Array, Index);          // Judy1NextEmpty()
J1LE(Rc_int,  PJ1Array, Index);          // Judy1LastEmpty()
J1PE(Rc_int,  PJ1Array, Index);          // Judy1PrevEmpty()

Определения

J1S(Rc_int, PJ1Array, Index); // Judy1Set()

Устанавливает бит Index в массиве Judy1 PJ1Array. Возвращает Rc_int = 1 при сброшенном бите Index (нет ошибки) и 0 при установленном ранее бите (ошибка).

J1U(Rc_int, PJ1Array, Index); // Judy1Unset()

Сбрасывает бит Index в массиве Judy1 PJ1Array. Возвращает Rc_int = 1 при установленном ранее бите Index (нет ошибки) и 0 при сброшенном бите (ошибка).

J1T(Rc_int, PJ1Array, Index); // Judy1Test()

Проверяет установку бита Index в массиве Judy1 PJ1Array. Возвращает Rc_int = 1 при установленном бите Index (Index присутствует) и 0 при сброшенном бите (Index отсутствует).

J1C(Rc_word, PJ1Array, Index1, Index2); // Judy1Count()

Считает число индексов, присутствующих в массиве Judy1 PJ1Array между значениями Index1 и Index2 (включительно). Возвращает в Rc_word число интексов. Возврат Value = 0 может быть корректным для счетчика или указывать особый случай полностью заполненного массива (только на 32-битовых машинах). Более подробно это рассмотрено в описании функции Judy1Count(). Для подсчета числа присутствующих в массиве Judy1 индексов (численность) служит

J1C(Rc_word, PJ1Array, 0, -1);

Отметим, что -1 указывает максимальный индекс (все 1).

J1BC(Rc_int, PJ1Array, Nth, Index); // Judy1ByCount()

Находит Nth-й индекс, который присутствует в массиве Judy1 PJ1Array (Nth = 1 возвращает первый имеющийся индекс). Для указания последнего индекса в полностью заполненном массиве (присутствуют все индексы, что бывает редко) используется Nth = 0. Возвращает Rc_int = 1 и Index = Nth, если индекс найден, и Rc_int = 0 в противном случае (Value в Index не содержит полезной информации).

J1FA(Rc_word, PJ1Array); // Judy1FreeArray()

Освобождает весь массив Judy1 PJ1Array (быстрее цикла J1N(), J1U()). Возвращает в Rc_word число освобожденных битов и устанавливает PJ1Array = NULL.

J1MU(Rc_word, PJ1Array); // Judy1MemUsed()

Возвращает в Rc_word число байтов памяти, занятых массивом Judy1 PJ1Array. Это очень быстрый макрос и его можно применять после J1S() или J1U() практически без снижения производительности.

Макросы поиска Judy1

Средства поиска в Judy1 позволяют найти установленные или сброшенные биты в массиве. Поиск может быть включающим или исключающим и выполняется в обоих направлениях. Все средства поиска используют похожие последовательности вызова. При успешном поиске в Rc_int возвращается 1 вместе с найденным индексом Index. При неудачном поиске Rc_int = 0, а Index не содержит полезной информации. Код возврата Rc_int должен проверяться до использования возвращенного Index, поскольку при поиске возможны отказы.

J1F(Rc_int, PJ1Array, Index); // Judy1First()

Включительный поиск первого присутствия индекса не меньше указанного Index. Для поиска первого элемента служит Index = 0. J1F() обычно служит для начала упорядоченного сканирования индексов в массиве Judy1.

J1N(Rc_int, PJ1Array, Index); // Judy1Next()

Исключительный поиск первого присутствия индекса больше указанного Index. J1N() обычно служит для продолжения упорядоченного сканирования индексов в массиве Judy1 или поиска «соседа» указанного индекса.

J1L(Rc_int, PJ1Array, Index); // Judy1Last()

Включительный поиск последнего присутствия индекса не больше указанного Index. Для поиска последнего индекса в массиве используется Index = -1 (все 1). J1L() обычно служит для начала упорядоченного сканирования в обратном направлении индексов в массиве Judy1.

J1P(Rc_int, PJ1Array, Index); // Judy1Prev()

Исключительный поиск предыдущего индекса меньше указанного Index. J1P() обычно служит для продолжения упорядоченного сканирования в обратном направлении индексов в массиве Judy1 или поиска «соседа» указанного индекса.

J1FE(Rc_int, PJ1Array, Index); // Judy1FirstEmpty()

Включительный поиск первого отсутствия индекса не меньше указанного Index. Для поиска первого отсутствующего элемента служит Index = 0.

J1NE(Rc_int, PJ1Array, Index); // Judy1NextEmpty()

Исключительный поиск первого отсутствия индекса больше указанного Index.

J1LE(Rc_int, PJ1Array, Index); // Judy1LastEmpty()

Включительный поиск последнего присутствия индекса не больше указанного Index. Для поиска последнего отсутствующего индекса в массиве используется Index = -1 (все 1)

J1PE(Rc_int, PJ1Array, Index); // Judy1PrevEmpty()

Исключительный поиск предыдущего индекса меньше указанного Index.

Пример

В приведенном ниже примере ошибки при вызове J1S() или J1U() вызывают пользовательскую процедуру process_malloc_failure. Этого не требуется при использовании принятого по умолчанию макроса JUDYERROR(), поскольку он завершает программу при любом отказе, включая ошибки malloc().

#include <stdio.h>
#include <Judy.h>

int main()  {                    // Пример программы с Judy1 macro API
   Word_t Index;                 // индекс (или ключ)
   Word_t Rcount;                // счетчик индексов (установленных битов)
   Word_t Rc_word;               // возвращаемое значение (word)
   int    Rc_int;                // возвращаемое логическое значение (0 или 1)

   Pvoid_t PJ1Array = (Pvoid_t) NULL; // инициализация массива Judy1

   Index = 123456;
   J1S(Rc_int, J1Array, Index);  // Установка бита 123456
   if (Rc_int == JERR) goto process_malloc_failure;
   if (Rc_int == 1) printf("OK - bit successfully set at %lu\n", Index);
   if (Rc_int == 0) printf("BUG - bit already set at %lu\n", Index);

   Index = 654321;
   J1T(Rc_int, J1Array, Index);  // проверка установки бита 654321
   if (Rc_int == 1) printf("BUG - set bit at %lu\n", Index);
   if (Rc_int == 0) printf("OK - bit not set at %lu\n", Index);

   J1C(Rcount, J1Array, 0, -1);  // счетчик установленных битов массива
   printf("%lu bits set in Judy1 array\n", Rcount);

   Index = 0;
   J1F(Rc_int, J1Array, Index);  // найти первый бит, установленный в массиве
   if (Rc_int == 1) printf("OK - first bit set is at %lu\n", Index);
   if (Rc_int == 0) printf("BUG - no bits set in array\n");

   J1MU(Rc_word, J1Array);       // объем используемой памяти
   printf("%lu Indexes used %lu bytes of memory\n", Rcount, Rc_word);

   Index = 123456;
   J1U(Rc_int, J1Array, Index);  // сбросить бит 123456
   if (Rc_int == JERR) goto process_malloc_failure;
   if (Rc_int == 1) printf("OK - bit successfully unset at %lu\n", Index);
   if (Rc_int == 0) printf("BUG - bit was not set at %lu\n", Index);

   return(0);
}

Функции Judy1

Функции Judy1 обеспечивают библиотеку C для работы с динамическими массивами битов, в которых индексом служит любое значение типа word.

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

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

При вызове функций Judy1 используется дополнительный параметр по сравнению с соответствующими макросами. Этим параметром является указатель на структуру ошибки или NULL (если детали ошибок не возвращаются).

Ниже функции описаны в терминах их использования макросами (для случая #define JUDYERROR_NOTEST 1). Это является рекомендуемым использованием макросов после завершения отладки программ. Если макрос JUDYERROR_NOTEST не задан, объявляется структура ошибки для хранения информации, возвращаемой из функций Judy1 при возникновении ошибок.

Следует обращать внимание на размещение символа & в разных функциях.

Синтаксис

int    Judy1Set(PPvoid_t PPJ1Array, Word_t Index, PJError_t PJError);
int    Judy1Unset(PPvoid_t PPJ1Array, Word_t Index, PJError_t PJError);
int    Judy1Test(Pcvoid_t PJ1Array, Word_t Index, PJError_t PJError);
Word_t Judy1Count(Pcvoid_t PJ1Array, Word_t Index1, Word_t Index2, PJError_t PJError);
int    Judy1ByCount(Pcvoid_t PJ1Array, Word_t Nth, Word_t * PIndex, PJError_t PJError);
Word_t Judy1FreeArray(PPvoid_t PPJ1Array, PJError_t PJError);
Word_t Judy1MemUsed(Pcvoid_t PJ1Array);
int    Judy1First(Pcvoid_t PJ1Array, Word_t * PIndex, PJError_t PJError);
int    Judy1Next(Pcvoid_t PJ1Array, Word_t * PIndex, PJError_t PJError);
int    Judy1Last(Pcvoid_t PJ1Array, Word_t * PIndex, PJError_t PJError);
int    Judy1Prev(Pcvoid_t PJ1Array, Word_t * PIndex, PJError_t PJError);
int    Judy1FirstEmpty(Pcvoid_t PJ1Array, Word_t * PIndex, PJError_t PJError);
int    Judy1NextEmpty(Pcvoid_t PJ1Array, Word_t * PIndex, PJError_t PJError);
int    Judy1LastEmpty(Pcvoid_t PJ1Array, Word_t * PIndex, PJError_t PJError);
int    Judy1PrevEmpty(Pcvoid_t PJ1Array, Word_t * PIndex, PJError_t PJError);

Определения

Judy1Set(&PJ1Array, Index, &JError)

#define J1S(Rc_int, PJ1Array, Index) \
   Rc_int = Judy1Set(&PJ1Array, Index, PJE0)

Judy1Unset(&PJ1Array, Index, &JError)

#define J1U(Rc_int, PJ1Array, Index) \
   Rc_int = Judy1Unset(&PJ1Array, Index, PJE0)

Judy1Test(PJ1Array, Index, &JError)

#define J1T(Rc_int, PJ1Array, Index) \
   Rc_int = Judy1Test(PJ1Array, Index, PJE0)

Judy1Count(PJ1Array, Index1, Index2, &JError)

#define J1C(Rc_word, PJ1Array, Index1, Index2) \
   Rc_word = Judy1Count(PJ1Array, Index1, Index2, PJE0)

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

JError_t JError;
Rc_word = Judy1Count(PJ1Array, Index1, Index2, &JError);
if (Rc_word == 0)	{
    if (JU_ERRNO(&JError) == JU_ERRNO_NONE)
        printf("Judy1 array population == 0\n");
    if (JU_ERRNO(&JError) == JU_ERRNO_FULL)
        printf("Judy1 array population == 2^32\n");
    if (JU_ERRNO(&JError) == JU_ERRNO_NULLPPARRAY)
        goto NullArray;
    if (JU_ERRNO(&JError) >  JU_ERRNO_NFMAX)
        goto Null_or_CorruptArray;
}

Judy1ByCount(PJ1Array, Nth, &Index, &JError)

#define J1BC(Rc_int, PJ1Array, Nth, Index) \
   Rc_int = Judy1ByCount(PJ1Array, Nth, &Index, PJE0)

Judy1FreeArray(&PJ1Array, &JError)

#define J1FA(Rc_word, PJ1Array) \
   Rc_word = Judy1FreeArray(&PJ1Array, PJE0)

Judy1MemUsed(PJ1Array)

#define J1MU(Rc_word, PJ1Array) \
   Rc_word = Judy1MemUsed(PJ1Array)

Judy1First(PJ1Array, &Index, &JError)

#define J1F(Rc_int, PJ1Array, Index) \
   Rc_int = Judy1First(PJ1Array, &Index, PJE0)

Judy1Next(PJ1Array, &Index, &JError)

#define J1N(Rc_int, PJ1Array, Index) \
   Rc_int = Judy1Next(PJ1Array, &Index, PJE0)

Judy1Last(PJ1Array, &Index, &JError)

#define J1L(Rc_int, PJ1Array, Index) \
   Rc_int = Judy1Last(PJ1Array, &Index, PJE0)

Judy1Prev(PJ1Array, &Index, &JError)

#define J1P(Rc_int, PJ1Array, Index) \
   Rc_int = Judy1Prev(PJ1Array, &Index, PJE0)

Judy1FirstEmpty(PJ1Array, &Index, &JError)

#define J1FE(Rc_int, PJ1Array, Index) \
   Rc_int = Judy1FirstEmpty(PJ1Array, &Index, PJE0)

Judy1NextEmpty(PJ1Array, &Index, &JError)

#define J1NE(Rc_int, PJ1Array, Index) \
   Rc_int = Judy1NextEmpty(PJ1Array, &Index, PJE0)

Judy1LastEmpty(PJ1Array, &Index, &JError)

#define J1LE(Rc_int, PJ1Array, Index) \
   Rc_int = Judy1LastEmpty(PJ1Array, &Index, PJE0)

Judy1PrevEmpty(PJ1Array, &Index, &JError)

#define J1PE(Rc_int, PJ1Array, Index) \
   Rc_int = Judy1PrevEmpty(PJ1Array, &Index, PJE0)

Определения всех функций Judy, типов Pvoid_t, Pcvoid_t, PPvoid_t, Word_t, JError_t и PJError_t, констант NULL, JU_ERRNO_*, JERR и PJE0 приведены в файле Judy.h (/usr/include/Judy.h). Следует отметить, что вызывающие должны определять массивы Judy1 типа Pvoid_t, который можно передать функциям, принимающим Pcvoid_t (constant Pvoid_t), а также по адресу в функции, принимающие PPvoid_t.

JudyL

Макросы JudyL

Макросы JudyL представляют собой библиотеку C для создания и использования динамического массива слов (word). Индексом массива может служить любое значение слова (word).

Массив JudyL эквивалентен массиву значений Value типа word, адресуемому Index (ключ). Массив может быть разреженным (sparse), а Index может быть любым значением (Value) размера word. Память для поддержки массива выделяется при вставке пары «индекс-значение» и освобождается при ее удалении. Массив JudyL можно также считать отображением слова на другое слово (указатель).

Если указатель Judy1 (PJ1Array) имеет значение NULL, это говорит, что все биты сброшены (для массива Judy1 не требуется памяти).

Как и обычные массивы, JudyL не имеет дубликатов индексов.

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

Массив JudyL выделяется с указателем NULL

Pvoid_t PJLArray = (Pvoid_t) NULL;

При использовании описанных здесь макросов вместо вызова функций JudyL принятая по умолчанию обработка ошибок передает сообщение на стандартный вывод ошибок и завершает программу с кодом exit(1). Другие методы обработки ошибок рассмотрены в разделе Ошибки.

Поскольку макросы иногда быстрее и включают более эффективную обработку ошибок по сравнению с функциями, их применение является предпочтительным в JudyL.

Синтаксис

cc [flags] sourcefiles -lJudy

#include <Judy.h>

int     Rc_int;                          // Код возврата - integer
Word_t  Rc_word;                         // Код возврата - unsigned word
Word_t  Index, Index1, Index2, Nth;

PWord_t  PValue;                         // Указатель на возвращаемое значение
Pvoid_t PJLArray = (Pvoid_t) NULL;       // Инициализация массива JudyL

JLI( PValue,  PJLArray, Index);          // JudyLIns()
JLD( Rc_int,  PJLArray, Index);          // JudyLDel()
JLG( PValue,  PJLArray, Index);          // JudyLGet()
JLC( Rc_word, PJLArray, Index1, Index2); // JudyLCount()
JLBC(PValue,  PJLArray, Nth, Index);     // JudyLByCount()
JLFA(Rc_word, PJLArray);                 // JudyLFreeArray()
JLMU(Rc_word, PJLArray);                 // JudyLMemUsed()
JLF( PValue,  PJLArray, Index);          // JudyLFirst()
JLN( PValue,  PJLArray, Index);          // JudyLNext()
JLL( PValue,  PJLArray, Index);          // JudyLLast()
JLP( PValue,  PJLArray, Index);          // JudyLPrev()
JLFE(Rc_int,  PJLArray, Index);          // JudyLFirstEmpty()
JLNE(Rc_int,  PJLArray, Index);          // JudyLNextEmpty()
JLLE(Rc_int,  PJLArray, Index);          // JudyLLastEmpty()
JLPE(Rc_int,  PJLArray, Index);          // JudyLPrevEmpty()

JLI(PValue, PJLArray, Index) // JudyLIns()

Вставляет Index и Value в массив JudyL PJLArray. При успешной вставке устанавливается значение Value = 0. Если Index уже присутствует, Value не меняется. Возвращает указатель PValue на значение Value, который программа может использовать для чтения или изменения Value, пока не будет выполнен следующий макрос JLI() (вставка), JLD() (удаление) или JLFA() (очистка массива) для массива PJLArray. Например,

*PValue = 1234;
Value = *PValue;

Возвращает в PValue значение PJERR, если возникает отказ malloc(). Отметим, что макросы JLI() и JLD() реорганизуют массив JudyL, поэтому PValue из предыдущего вызова JudyL становится непригодным и должно быть обновлено.

JLD(Rc_int, PJLArray, Index) // JudyLDel()

Удаляет пару IndexValue из массива JudyL. Макрос возвращает Rc_int = 1 при успешном удалении и Rc_int = 0, если Index отсутствует. При отказе malloc() устанавливается Rc_int = JERR.

JLG(PValue, PJLArray, Index) // JudyLGet()

Возвращает указатель PValue, связанный с Index в массиве PJLArray. Макрос возвращает значение Pvalue, указывающее на Value. При отсутствии Index возвращается PValue = NULL, а пр отказе malloc() — PValue = PJERR.

JLC(Rc_word, PJLArray, Index1, Index2) // JudyLCount()

Возвращает число индексов, имеющихся в массиве JudyL PJLArray между значениями Index1 и Index2 (включительно). Rc_word содержит значение счетчика. Значение 0 может указывать отсутствие индексов. Для подсчета всех индексов в массиве JudyL используется вызов

JLC(Rc_word, PJLArray, 0, -1);

JLBC(PValue, PJLArray, Nth, Index) // JudyLByCount()

Находит Nth-й, присутствующий в массиве JudyL PJLArray (при Nth = 1 возвращается первый имеющийся индекс).

Возвращает PValue с указанием на Value и Index, установленные для имеющегося Nth-ого индекса или PValue = NULL, если индекс отсутствует (значение Index в этом случае не имеет смысла).

JLFA(Rc_word, PJLArray) // JudyLFreeArray()

По указателю на массив JudyL полностью освобождает его гораздо быстрее чем в цикле JLN(), JLD(). Возвращает в Rc_word число освобожденных байтов и устанавливает PJLArray = NULL.

JLMU(Rc_word, PJLArray) // JudyLMemUsed()

Возвращает в Rc_word число байтов, выделенных malloc() для PJLArray. Это очень быстрый макрос и его можно использовать перед или после JLI() или JLD() практически без влияния на производительность.

Средства поиска JudyL

Макросы JLF(), JLN(), JLL(), JLP() позволяют выполнять поиск в массиве. Поиск может быть включительным или исключительным и выполняться в обоих направлениях. При успешном поиске Index содержит найденный индекс, а PValue — указатель на значение (Value) для найденного Index. Если поиск не дал результата, возвращается PValue = NULL, а Index не содержит полезной информации. Указатель PValue должен проверяться до использования Index, поскольку при поиске возможны отказы.

Макросы JLFE(), JLNE(), JLLE(), JLPE() позволяют искать отсутствующие (пустые) индексы в массиве. Поиск может быть включительным или исключительным и выполняется в обоих направлениях. При успешном поиске возвращается Index отсутствующего индекса и Rc_int = 1. При неудаче возвращается Rc_int = 0, а Index не содержит полезной информации. Значение Rc_int должно проверяться до использования Index, поскольку при поиске возможен отказ.

JLF(PValue, PJLArray, Index) // JudyLFirst()

Включительный поиск первого присутствующего индекса не меньше переданного Index. При Index = 0 отыскивается первый имеющийся индекс. JLF() обычно применяется для начала упорядоченного сканирования имеющихся в JudyL индексов.

JLN(PValue, PJLArray, Index) // JudyLNext()

Исключительный поиск первого присутствующего индекса больше переданного Index. JLN() обычно служит для продолжения упорядоченного сканирования индекса JudyL или поиска «соседа» данного индекса.

JLL(PValue, PJLArray, Index) // JudyLLast()

Включительный поиск последнего присутствующего индекса не больше переданного Index. При Index = -1 (все 1) отыскивается последний индекс массива. JLL() обычно применяется для упорядоченного сканирования присутствующих в массиве JudyL индексов в обратном направлении.

JLP(PValue, PJLArray, Index) // JudyLPrev()

Исключительный поиск предыдущего индекса меньше переданного Index. JLP() обычно служит для продолжения упорядоченного сканирования присутствующих в массиве JudyL индексов в обратном направлении.

JLFE(Rc_int, PJLArray, Index) // JudyLFirstEmpty()

Включительный поиск первого отсутствующего индекса не меньше переданного Index. Index = 0 задает поиск первого отсутствующего в массиве индекса.

JLNE(Rc_int, PJLArray, Index) // JudyLNextEmpty()

Исключительный поиск следующего отсутствующего индекса больше переданного Index.

JLLE(Rc_int, PJLArray, Index) // JudyLLastEmpty()

Включительный поиск последнеого отсутствующего индекса не больше переданного Index. При Index = -1 (все 1) отыскивается последний индекс, отсутствующий в массиве.

JLPE(Rc_int, PJLArray, Index) // JudyLPrevEmpty()

Исключительный поиск предыдущего индекса меньше переданного Index.

Многомерные массивы JudyL

Запись указателя на другой массив JudyL в Value массива JudyL обеспечивает простой способ поддержки динамических многомерных массивов. Такие массивы (деревья), созданные с помощью JudyL, являются очень быстрыми и нетребовательными к памяти (фактически, так реализованы JudySL и JudyHS). Таким способом можно реализовать произвольную размерность. Для завершения числа измерений (дерева), указатель в Value помечается как не указывающий на другой массив Judy с помощью флага JLAP_INVALID в младших битах указателя2. После удаления флага JLAP_INVALID значение используется как указатель на пользовательские данные. Флаг JLAP_INVALID определен в файле Judy.h.

Ниже приведен фрагмент кода, который можно использовать для проверки указания на другой массив JudyL.

PValue = (PWord_t)PMultiDimArray;

for (Dim = 0; ;Dim++)	{
   if (PValue == (PWord_t)NULL) goto IndexNotFound;

   /* Переход к следующему измерению в массиве. */
   JLG(PValue, (Pvoid_t)*PValue, Index[Dim]);

   /* Проверка указателя на пользовательский буфер. */
   if (*PValue & JLAP_INVALID)) break;
}
UPointer = (UPointer_t) (*PValue & ~JLAP_INVALID);  // mask and cast.
printf("User object pointer is 0x%lx\n", (Word_t) UPointer);
       ...

Этот код работает, поскольку malloc() гарантирует возврат указателя с младшими битами, имеющими значение 0x0. Флаг JLAP_INVALID должен удаляться перед использованием указателя.

Пример

Считывание последовательности пар «индекс-значение» со стандартного ввода, сохранение в массиве и вывод в отсортированном виде.

#include <stdio.h>
#include <Judy.h>

Word_t   Index;                     // индекс массива
Word_t   Value;                     // значение элемента массива
Word_t * PValue;                    // указатель на значение элемента массива
int      Rc_int;                    // код возврата

Pvoid_t  PJLArray = (Pvoid_t) NULL; // Инициализация массива JudyL

while (scanf("%lu %lu", &Index, &Value))	{
    JLI(PValue, PJLArray, Index);
    If (PValue == PJERR) goto process_malloc_failure;
    *PValue = Value;                // запись нового значения
}
// Затем перебираются все сохраненные индексы в порядке сортировки сначала по возрастанию, 
// потом по убыванию и во втором проходе каждый индекс удаляется.

Index = 0;
JLF(PValue, PJLArray, Index);
while (PValue != NULL)	{
    printf("%lu %lu\n", Index, *PValue));
    JLN(PValue, PJLArray, Index);
}

Index = -1;
JLL(PValue, PJLArray, Index);
while (PValue != NULL)	{
    printf("%lu %lu\n", Index, *PValue));

    JLD(Rc_int, PJLArray, Index);
    if (Rc_int == JERR) goto process_malloc_failure;

    JLP(PValue, PJLArray, Index);
}

Функции JudyL

Функции JudyL обеспечивают библиотеку C для создания и работы с динамическими массивами слов (word), использующими в качестве индекса любые значения слов (word).

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

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

При вызове функций JudyL используется дополнительный параметр по сравнению с соответствующими макросами. Этим параметром является указатель на структуру ошибки или NULL (если детали ошибок не возвращаются).

Ниже функции описаны в терминах их использования макросами (для случая #define JUDYERROR_NOTEST 1). Это является рекомендуемым использованием макросов после завершения отладки программ. Если макрос JUDYERROR_NOTEST не задан, объявляется структура ошибки для хранения информации, возвращаемой из функций JudyL при возникновении ошибок.

Следует обращать внимание на размещение символа & в разных функциях.

Синтаксис

PPvoid_t JudyLIns(PPvoid_t PPJLArray, Word_t    Index, PJError_t PJError);
int      JudyLDel(PPvoid_t PPJLArray, Word_t    Index, PJError_t PJError);
PPvoid_t JudyLGet(Pcvoid_t  PJLArray, Word_t    Index, PJError_t PJError);
Word_t   JudyLCount(Pcvoid_t PJLArray, Word_t Index1, Word_t Index2, PJError_t PJError);
PPvoid_t JudyLByCount(Pcvoid_t PJLArray, Word_t Nth, Word_t * PIndex, PJError_t PJError);
Word_t   JudyLFreeArray(PPvoid_t PPJLArray, PJError_t PJError);
Word_t   JudyLMemUsed(Pcvoid_t  PJLArray);
PPvoid_t JudyLFirst(Pcvoid_t  PJLArray, Word_t * PIndex, PJError_t PJError);
PPvoid_t JudyLNext(Pcvoid_t  PJLArray, Word_t * PIndex, PJError_t PJError);
PPvoid_t JudyLLast(Pcvoid_t  PJLArray, Word_t * PIndex, PJError_t PJError);
PPvoid_t JudyLPrev(Pcvoid_t  PJLArray, Word_t * PIndex, PJError_t PJError);
int      JudyLFirstEmpty(Pcvoid_t  PJLArray, Word_t * PIndex, PJError_t PJError);
int      JudyLNextEmpty(Pcvoid_t PJLArray, Word_t * PIndex, PJError_t PJError);
int      JudyLLastEmpty(Pcvoid_t PJLArray, Word_t * PIndex, PJError_t PJError);
int      JudyLPrevEmpty(Pcvoid_t PJLArray, Word_t * PIndex, PJError_t PJError);

Определения

JudyLIns(&PJLArray, Index, &JError)

#define JLI(PValue, PJLArray, Index)  \
   PValue = JudyLIns(&PJLArray, Index, PJE0)

JudyLDel(&PJLArray, Index, &JError)

#define JLD(Rc_int, PJLArray, Index)  \
   Rc_int = JudyLDel(&PJLArray, Index, PJE0)

JudyLGet(PJLArray, Index, &JError)

#define JLG(PValue, PJLArray, Index)  \
   PValue = JudyLGet(PJLArray, Index, PJE0)

JudyLCount(PJLArray, Index1, Index2, &JError)

#define JLC(Rc_word, PJLArray, Index1, Index2)  \
   Rc_word = JudyLCount(PJLArray, Index1, Index2, PJE0)

JudyLByCount(PJLArray, Nth, &Index, &JError)

#define JLBC(PValue, PJLArray, Nth, Index) \
   PValue = JudyLByCount(PJLArray, Nth, &Index, PJE0)

JudyLFreeArray(&PJLArray, &JError)

#define JLFA(Rc_word, PJLArray) \
   Rc_word = JudyLFreeArray(&PJLArray, PJE0)

JudyLMemUsed(PJLArray)

#define JLMU(Rc_word, PJLArray) \
   Rc_word = JudyLMemUsed(PJLArray)

JudyLFirst(PJLArray, &Index, &JError)

#define JLF(PValue, PJLArray, Index) \
   PValue = JudyLFirst(PJLArray, &Index, PJEO)

JudyLNext(PJLArray, &Index, &JError)

#define JLN(PValue, PJLArray, Index) \
   PValue = JudyLNext(PJLArray, &Index, PJEO)

JudyLLast(PJLArray, &Index, &JError)

#define JLL(PValue, PJLArray, Index) \
   PValue = JudyLLast(PJLArray, &Index, PJEO)

JudyLPrev(PJLArray, &Index, &JError)

#define JLP(PValue, PJLArray, Index) \
   PValue = JudyLPrev(PJLArray, &Index, PJEO)

JudyLFirstEmpty(PJLArray, &Index, &JError)

#define JLFE(Rc_int, PJLArray, Index) \
   Rc_int = JudyLFirstEmpty(PJLArray, &Index, PJEO)

JudyLNextEmpty(PJLArray, &Index, &JError)

#define JLNE(Rc_int, PJLArray, Index) \
   Rc_int = JudyLNextEmpty(PJLArray, &Index, PJEO)

JudyLLastEmpty(PJLArray, &Index, &JError)

#define JLLE(Rc_int, PJLArray, Index) \
   Rc_int = JudyLLastEmpty(PJLArray, &Index, PJEO)

JudyLPrevEmpty(PJLArray, &Index, &JError)

#define JLPE(Rc_int, PJLArray, Index) \
   Rc_int = JudyLPrevEmpty(PJLArray, &Index, PJEO)

Определения всех функций Judy, типов Pvoid_t, Pcvoid_t, PPvoid_t, Word_t, JError_t и PJError_t, констант NULL, JU_ERRNO_*, JERR и PJE0 приведены в файле Judy.h (/usr/include/Judy.h). Следует отметить, что вызывающие должны определять массивы Judy1 типа Pvoid_t, который можно передать функциям, принимающим Pcvoid_t (constant Pvoid_t), а также по адресу в функции, принимающие PPvoid_t.

Большиство функций JudyL возвращает PPvoid_t, поскольку значения в массиве могут быть ссылками на другие объекты, или Word_t *, когда нужен указатель на Value, а не указатель на указатель.

JudySL

Макросы JudySL

Макросы JudySL обеспечивают библиотеку C для создания и работы с динамическими массивами, использующими строки с null-символом в конце в качестве Index (ассоциативный массив).

Массив JudySL эквивалентен отсортированному набору строк, с каждой из которых связано значение Value типа word. Value адресуются индексами Index (ключ), которые представляют собой строки произвольного размера, завершающиеся null-символом. Память для массива выделяется при вставке пар «индекс-значение» и и освобождается при удалении пар. Это форма ассоциативного массива, где элементы сортируются лексически (с учетом регистра) по индексам. Это можно рассматривать как

void * JudySLArray["Toto, I don't think we're in Kansas any more"];

Массив JudySL создается с указателем NULL

Pvoid_t PJSLArray = (Pvoid_t) NULL;

Как в обычных массивах индексы не дублируются.

При использовании описанных здесь макросов вместо вызова функций JudySL принятая по умолчанию обработка ошибок выводит сообщения на стандартный вывод ошибок и завершает программу с exit(1).

Синтаксис

cc [flags] sourcefiles -lJudy

#include <Judy.h>

#define MAXLINELEN 1000000           // задает максимальный размер строк

Word_t * PValue;                     // элемент массива JudySL
uint8_t  Index[MAXLINELEN];          // строка
int      Rc_int;                     // возвращаемое значение
Word_t   Rc_word;                    // полное слово возвращаемого значения

Pvoid_t PJSLArray = (Pvoid_t) NULL;  // Инициализация массива JudySL

JSLI(PValue,  PJSLArray, Index);     // JudySLIns()
JSLD(Rc_int,  PJSLArray, Index);     // JudySLDel()
JSLG(PValue,  PJSLArray, Index);     // JudySLGet()
JSLFA(Rc_word, PJSLArray);           // JudySLFreeArray()
JSLF(PValue,  PJSLArray, Index);     // JudySLFirst()
JSLN(PValue,  PJSLArray, Index);     // JudySLNext()
JSLL(PValue,  PJSLArray, Index);     // JudySLLast()
JSLP(PValue,  PJSLArray, Index);     // JudySLPrev()

JSLI(PValue, PJSLArray, Index) // JudySLIns()

Вставляет строку Index и Value в массив JudySL PJSLArray. При успешной вставке Index устанавливается Value = 0. Если Index уже присутствует, Value не меняется. Макрос возвращает указатель PValue на значениеValue индекса Index. Программы должны использовать этот указатель для изменения Value, например,

*PValue = 1234;

Макросы JSLI() и JSLD реорганизуют массив JudySL, поэтому возвращенные предыдущими вызовами JudySL указатели теряют силу и должны быть определены заново.

JSLD(Rc_int, PJSLArray, Index) // JudySLDel()

Удаляет заданную пару IndexValue (элемент) из массива JudySL. Возвращает Rc_int = 1 при успешном удалении и Rc_int = 0, если Index отсутствует в массиве.

JSLG(PValue, PJSLArray, Index) // JudySLGet()

Возвращает указатель на Value индекса Index или PValue = NULL, если Index отсутствует в массиве.

JSLFA(Rc_word, PJSLArray) // JudySLFreeArray()

По указателю на массив JudySL (PJSLArray) освобождает массив полностью (гораздо быстрей, нежели цикл JSLN(), JSLD()). Возвращает в Rc_word число освобожденных байтов и PJSLArray = NULL.

Средства поиска JudySL

Средства поиска JudySL обеспечивают поиск индексов в массиве (включительный или исключительный) в прямом и обратном направлении.

При успешном поиске Index содержит найденный индекс, а PValue — указатель на значение (Value) для найденного Index. Если поиск не дал результата, возвращается PValue = NULL, а Index не содержит полезной информации. Указатель PValue должен проверяться до использования Index, поскольку при поиске возможны отказы. Для учета всех возможных результатов буфер Index должен иметь размер не меньше максимально длинной строки массива.

JSLF(PValue, PJSLArray, Index) // JudySLFirst()

Включительный поиск первого имеющегося индекса не меньше переданной строки Index. Поиск с пустой (null) строкой индекса будет возвращать первый индекс в массиве. JSLF() обычно применяется для начала упорядоченного сканирования действительных индексов массива JudySL.

uint8_t Index[MAXLINELEN];
strcpy (Index, "");
JSLF(PValue, PJSLArray, Index);

JSLN(PValue, PJSLArray, Index) // JudySLNext()

Исключительный поиск следующего индекса больше переданной строки Index. JSLN() обычно служит для продолжения упорядоченного сканирования действительных индексов в массиве JudySL или поиска «соседа» заданного индекса.

JSLL(PValue, PJSLArray, Index) // JudySLLast()

Включительный поиск последнего имеющегося индекса не больше переданной строки Index. Начало поиска со строки с максимальным значением (например, самой длинной строки с 0xff байтов) возвратит последний индекс в массиве. JSLL() обычно служит для начала упорядоченного сканирования действительных индексов массива JudySL в обратном направлении.

JSLP(PValue, PJSLArray, Index) // JudySLPrev()

Исключительный поиск предыдущего индекса меньше переданной строки Index. JSLP() обычно служит для продолжения упорядоченного сканирования действительных индексов массива JudySL в обратном направлении или поиска «соседа» указанного индекса.

Пример программы сортировки строк

#include <stdio.h>
#include <Judy.h>

#define MAXLINE 1000000                 // максимальный размер строки (длина)

uint8_t   Index[MAXLINE];               // строка для вставки

int     // Синтаксис:  JudySort < file_to_sort
main()
{
    Pvoid_t   PJArray = (PWord_t)NULL;  // Массив Judy.
    PWord_t   PValue;                   // Элемент массива Judy.
    Word_t    Bytes;                    // Размер массива JudySL.

    while (fgets(Index, MAXLINE, stdin) != (char *)NULL)
    {
        JSLI(PValue, PJArray, Index);   // Сохранить строку в массиве.
        if (PValue == PJERR)            // Недостаточно памяти?
        {                               // Обработка нехватки памяти.
            printf("Malloc failed -- get more ram\n");
            exit(1);
        }
        ++(*PValue);                    // Число экземпляров строк.
    }
    Index[0] = '\0';                    // Начать с наименьшей строки.
    JSLF(PValue, PJArray, Index);       // Находит первую строку.
    while (PValue != NULL)
    {
        while ((*PValue)--)             // Выводит дубликаты.
            printf("%s", Index);
        JSLN(PValue, PJArray, Index);   // находит следующую строку.
    }
    JSLFA(Bytes, PJArray);              // Освобождает массив.

    fprintf(stderr, "The JudySL array used %lu bytes of memory\n", Bytes);
    return (0);
}

Функции JudySL

Функции JudySL обеспечивают библиотеку C для создания и работы с динамическими массивами строк, завершающихся null-символом (ассоциативный массив).

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

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

При вызове функций JudySL используется дополнительный параметр по сравнению с соответствующими макросами. Этим параметром является указатель на структуру ошибки или NULL (если детали ошибок не возвращаются).

Ниже функции описаны в терминах их использования макросами (для случая #define JUDYERROR_NOTEST 1). Это является рекомендуемым использованием макросов после завершения отладки программ. Если макрос JUDYERROR_NOTEST не задан, объявляется структура ошибки для хранения информации, возвращаемой из функций JudySL при возникновении ошибок.

Следует обращать внимание на размещение символа & в разных функциях.

Синтаксис

PPvoid_t JudySLIns(PPvoid_t PPJSLArray, const uint8_t * Index, PJError_t PJError);
int      JudySLDel(PPvoid_t PPJSLArray, const uint8_t * Index, PJError_t PJError);
PPvoid_t JudySLGet(Pcvoid_t PJSLArray, const uint8_t * Index, PJError_t PJError);
Word_t   JudySLFreeArray(PPvoid_t PPJSLArray, PJError_t PJError);
PPvoid_t JudySLFirst(Pcvoid_t PJSLArray, uint8_t * Index, PJError_t PJError);
PPvoid_t JudySLNext(Pcvoid_t PJSLArray, uint8_t * Index, PJError_t PJError);
PPvoid_t JudySLLast(Pcvoid_t PJSLArray, uint8_t * Index, PJError_t PJError);
PPvoid_t JudySLPrev(Pcvoid_t PJSLArray, uint8_t * Index, PJError_t PJError);

Определения

JudySLIns(&PJSLArray, Index, &JError)

#define JSLI(PValue, PJSLArray, Index) \
   PValue = JudyLIns(&PJSLArray, Index, PJE0)

JudySLDel(&PJSLArray, Index, &JError)

#define JSLD(Rc_int, PJSLArray, Index) \
   Rc_int = JudySLDel(&PJSLArray, Index, PJE0)

JudySLGet(PJSLArray, Index, &JError)

#define JSLG(PValue, PJSLArray, Index) \
   PValue = JudySLIns(PJSLArray, Index, PJE0)

JudySLFreeArray(&PJSLArray, &JError)

#define JSLFA(Rc_word, PJSLArray) \
   Rc_word = JudySLFreeArray(&PJSLArray, PJE0)

JudySLFirst(PJSLArray, Index, &JError)

#define JSLF(PValue, PJSLArray, Index) \
   PValue = JudySLFirst(PJSLArray, Index, PJE0)

JudySLNext(PJSLArray, Index, &JError)

#define JSLN(PValue, PJSLArray, Index) \
   PValue = JudySLNext(PJSLArray, Index, PJE0)

JudySLLast(PJSLArray, Index, &JError)

#define JSLL(PValue, PJSLArray, Index) \
   PValue = JudySLLast(PJSLArray, Index, PJE0)

JudySLPrev(PJSLArray, Index, &JError)

#define JSLP(PValue, PJSLArray, Index) \
   PValue = JudySLPrev(PJSLArray, Index, PJE0)

Определения всех функций Judy, типов Pvoid_t, Pcvoid_t, PPvoid_t, Word_t, JError_t и PJError_t, констант NULL, JU_ERRNO_*, JERR и PJE0 приведены в файле Judy.h (/usr/include/Judy.h). Следует отметить, что вызывающие должны определять массивы Judy1 типа Pvoid_t, который можно передать функциям, принимающим Pcvoid_t (constant Pvoid_t), а также по адресу в функции, принимающие PPvoid_t.

Большиство функций JudySL возвращает PPvoid_t, поскольку значения в массиве могут быть ссылками на другие объекты, или Word_t *, когда нужен указатель на Value, а не указатель на указатель.

JudyHS

Макросы JudyHS

Библиотека C для создания и работы с динамическими массивами, использующими массив байтов размера Length в качестве Index и word как Value.

Массив JudyHS эквивалентен массиву значений или указателей размера word. Index служит указателем на массив байтов заданного размера Length. Вместо использования строк с null-завершением (как в JudySL) здесь могут применяться строки с любыми битами, включая null. Это дополнение (май 2004 г.) к массивам Judy является комбинацией методов хэширования и Judy. В JudyHS не возникает возможности снижения производительности за счет знания алгоритма хэширования.

Поскольку JudyHS базируется на хэшировании, индексы не сохраняются в каком-либо определенном порядке. Поэтому функции JudyHSFirst(), JudyHSNext(), JudyHSPrev() и JudyHSLast() для поиска соседей не имеют практического значения. Значение Length для каждого массива байтов может меняться от 0 до предела malloc() (около 2 Гбайт).

Отличием JudyHS является скорость и расширяемость при сохранении эффективности использования памяти. Скорость сопоставима с лучшими методами хэширования, а эффективность использования памяти близка к связным спискам для таких же Index и Value. Массивы JudyHS рассчитаны на работу с числом индексов от 0 до миллиардов.

Массив JudyHS создается с указателем NULL.

Pvoid_t PJHSArray = (Pvoid_t) NULL;

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

Синтаксис

cc [flags] sourcefiles -lJudy

#include <Judy.h>

Word_t  * PValue;                           // элемент массива JudyHS
int       Rc_int;                           // код возврата
Word_t    Rc_word;                          // полное значение возвращаемого слова
Pvoid_t   PJHSArray = (Pvoid_t) NULL;       // инициализация массива JudyHS
uint8_t * Index;                            // указатель на массив байтов
Word_t    Length;                           // число байтов в Index

JHSI( PValue,  PJHSArray, Index, Length);   // JudyHSIns()
JHSD( Rc_int,  PJHSArray, Index, Length);   // JudyHSDel()
JHSG( PValue,  PJHSArray, Index, Length);   // JudyHSGet()
JHSFA(Rc_word, PJHSArray);                  // JudyHSFreeArray()

Определения

JHSI(PValue, PJHSArray, Index, Length) // JudyHSIns()

По указателю на массив JudyHS (PJHSArray) вставляет строку Index размера Length и Value в массив JudyHS PJHSArray. При успешной вставке Index устанавливается Value = 0. Если Index уже есть в массиве, Value не меняется. Возвращаемое значение PValue указывает на Value. Программам следует использовать этот указатель для изменения Value, например,

Value = *PValue;
*PValue = 1234;

Отметим, что JHSI() и JHSD могут реорганизовать массив JudyHS, поэтому возвращенные из предыдущих вызовов JudyHS указатели должны быть обновлены (с помощью JHSG()).

JHSD(Rc_int, PJHSArray, Index, Length) // JudyHSDel()

По указателю на массив JudyHS (PJHSArray) удаляет указанный Index вместе с Value из массива JudyHS. Возвращает Rc_int = 1 при успешном удалении и Rc_int = 0, если Index отсутствует.

JHSG(PValue, PJHSArray, Index, Length) // JudyHSGet()

По указателю на массив JudyHS (PJHSArray) находит значение Value, связанное с Index. Возвращает указатель PValue на значение Value для Index или PValue = NULL при отсутствии Index.

JHSFA(Rc_word, PJHSArray) // JudyHSFreeArray()

По указателю на массив JudyHS (PJHSArray) освобождает массив целиком. Возвращает в Rc_word число освобожденных байтов и PJHSArray = NULL.

Пример

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

#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <Judy.h>

// Команда компиляции cc -O PrintDupLines.c -lJudy -o PrintDupLines

#define MAXLINE 1000000                 /* Максимальный размер строки */
uint8_t   Index[MAXLINE];               // Проверяемая строка

int     // Команда PrintDupLines < file
main()	{
    Pvoid_t   PJArray = (PWord_t)NULL;  // Массив Judy.
    PWord_t   PValue;                   // Указатель на элемент массива Judy.
    Word_t    Bytes;                    // Размер массива JudyHS.
    Word_t    LineNumb = 0;             // Номер текущей строки.
    Word_t    Dups = 0;                 // Число строк-дубликатов.

    while (fgets(Index, MAXLINE, stdin) != (char *)NULL)	{
        LineNumb++;                     // Номер строки.

        // Сохранение строки в массиве
        JHSI(PValue, PJArray, Index, strlen(Index)); 
        if (PValue == PJERR)	{      // См. Ошибки.
            fprintf(stderr, "Out of memory -- exit\n");
            exit(1);
        }
        if (*PValue == 0)	{             // Проверка дублирования
            Dups++;
            printf("Duplicate lines %lu:%lu:%s", *PValue, LineNumb, Index);
        } else {
            *PValue = LineNumb;         // Сохранение номера строки
        }
    }
    printf("%lu Duplicates, free JudyHS array of %lu Lines\n", 
                    Dups, LineNumb - Dups);
    JHSFA(Bytes, PJArray);              // Освобождение массива JudyHS
    printf("JudyHSFreeArray() free'ed %lu bytes of memory\n", Bytes);
    return (0);
}

Функции JudyHS

Функции JudySL обеспечивают библиотеку C для создания и работы с динамическими массивами из массивов байтов размера Length с использованием индексов типа word.

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

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

При вызове функций JudyHS используется дополнительный параметр по сравнению с соответствующими макросами. Этим параметром является указатель на структуру ошибки или NULL (если детали ошибок не возвращаются).

Ниже функции описаны в терминах их использования макросами (для случая #define JUDYERROR_NOTEST 1). Это является рекомендуемым использованием макросов после завершения отладки программ. Если макрос JUDYERROR_NOTEST не задан, объявляется структура ошибки для хранения информации, возвращаемой из функций JudyHS при возникновении ошибок.

Следует обращать внимание на размещение символа & в разных функциях.

Синтаксис

PPvoid_t JudyHSIns(PPvoid_t PPJHS, void *Index, Word_t Length, PJError_t PJError);
int      JudyHSDel(PPvoid_t PPJHS, void *Index, Word_t Length, PJError_t PJError);
PPvoid_t JudyHSGet(Pcvoid_t  PJHS, void *Index, Word_t Length, PJError_t PJError);
Word_t   JudyHSFreeArray(PPvoid_t PPJHS, PJError_t PJError);

Определения

JudyHSIns(&PJHS, Index, Length, &JError)

#define JHSI(PValue, PJHS, Index) \
   PValue = JudyLIns(&PJHS, Index, PJE0)

JudyHSDel(&PJHS, Index, Length, &JError)

#define JHSD(Rc_int, PJHS, Index, Length) \
   Rc_int = JudyHSDel(&PJHS, Index, Length, PJE0)

JudyHSGet(PJHS, Index, Length)

#define JHSG(PValue, PJHS, Index, Length) \
   PValue = JudyHSIns(PJHS, Index, Length)

JudyHSFreeArray(&PJHS, &JError)

#define JHSFA(Rc_word, PJHS) \
   Rc_word = JudyHSFreeArray(&PJHS, PJE0)

Определения всех функций Judy, типов Pvoid_t, Pcvoid_t, PPvoid_t, Word_t, JError_t и PJError_t, констант NULL, JU_ERRNO_*, JERR и PJE0 приведены в файле Judy.h (/usr/include/Judy.h). Следует отметить, что вызывающие должны определять массивы Judy1 типа Pvoid_t, который можно передать функциям, принимающим Pcvoid_t (constant Pvoid_t), а также по адресу в функции, принимающие PPvoid_t.

Большиство функций JudyHS возвращает PPvoid_t, поскольку значения в массиве могут быть ссылками на другие объекты, или Word_t *, когда нужен указатель на Value, а не указатель на указатель.


Перевод на русский язык

Николай Малых

nmalykh@protocols.ru

1В процессе тестирования Judy было найдено очень мало malloc()/ОС, где не возникало ошибок при отказах malloc(). Иногда приходилось ждать очень долго, поскольку в большинстве систем запускалась «бесконечная» подкачка.

2В текущей версии Judy.h значение этого флага 0x4 было заменено на 0x1, чтобы можно было использовать функцию malloc(), не выравнивающую выделенную память по 8-битовой границе (например, старая версия valgrind).

 




Краткое описание работы массивов JUDY

PDF

Doug Baskins, doug@sourcejudy.com

16 октября 2001 г., изменено в июле 2002

Разработчика алгоритма Judy часто спрашивают, почему этот алгоритм такой быстрый. Здесь предпринята попытка кратко ответить на этот вопрос. Более полное описание пакета приведено в документе Judy Shop Manual.

Исходный код Judy был открыт в июне 2002 г. и доступен по ссылке http://sourceforge.net/projects/judy1.

Дерево Judy в общем случае быстрее и требует меньше памяти, нежели такие варианты как бинарные деревья (AVL) trees, b-деревья и skip-списки. При использовании конфигурации Judy Scalable Hashing пакет обычно быстрее других методов хэширования.

Термины пространство (expanse), численность (population) и плотность (density) нечасто применяются в литературе о поиске по дереву, поэтому ниже даны краткие определения.

Пространство

Диапазон возможных ключей (например, 256 — 511).

Численность

Число ключей в пространстве (например, для 260, 300, 499, 500 это будет 4).

Плотность

Описывает степень разреженности пространства ключей (density = population/expanse). Плотность 1,0 означает, что все возможные ключи установлены или действительный в данном пространстве.

Термины узел (node) и ветвь (branch) в этом документе взаимозаменяемы.

Термины ключ (key) и индекс (index) взаимозаменяемы в документе. Дерево Judy рассматривается как неограниченный массив Judy на уровне интерфейса API. Пространства массивов JudyL и Judy1 ограничены размером слова (32 или 64 бита), применяемого в качестве индекса. Массив JudySL ограничен лишь размером строки ключа, которая может быть сохранена в машине.

Заполнение строки кэша CPU — это дополнительное время, требуемое для чтения ссылки из ОЗУ (RAM) если слово не найдено в кэше. В современных компьютерах это время составляет 50 — 2000 машинных команд2. Поэтому такого заполнения следует избегать, если ту же работу можно выполнить менее чем за 50 команд.

Некоторые причины превосходства Judy по сравнению с двоичными деревьями, b-tree и skip-списками указаны ниже.

  • Judy редко отдает предпочтение простоте по отношению к скорости и пространству (алгоритм Judy прост лиш на уровне API).

  • Judy по возможности избегает заполнения строк кэша (основной критерий устройства Judy).

  • Для b-tree требуется поиск в кажом узле (ветви), что ведет к заполнению большого числа строк кэша.

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

  • Skip-списки приблизительно эквивалентны дереву степени 4, что увеличивает число заполнений строк кэша.

  • Основанное на пространстве цифровое дерево (Judy является его вариантом) не требует балансировки при расширении.

  • Часть ключа (8 битов) служит для деления пространства на субдеревья, а в этих субдеревьях требуется лишь оставшаяся часть ключа , что сокращает размер.

Основным недостатком простых деревьев является неэффективное использование памяти, особенно при больших значениях степени втевления узлов N. Дерево Judy решает эту проблему. Фактически, это дерево превосходит по эффективности использования памяти почти все другие структуры (включая простые связные списки). Исключением может являться плотно заполненный линейный массив (array[]).

С точки зрения скорости Judy представляет собой дерево степени 256 (trie) в соответствии с определением D. Knuth (том 3). Число 256 для степени дерева является «магическим» по ряду причин. Основная причина заключается в том, что байт (минимальный адресуемый элемент памяти) имеет размер 8 битов. Высокая степень также ведет к снижению числа заполнений строк кэша на доступ.

Интересно отметить, что в ранней версии Judy использовалось расширение ветвей (иногда это называют level-compressed trie). Возможности расширения возникают главным образом на верхних уровнях дерева. Поскольку дерево представляет собой иерархию, верхние ветви с большой вероятностью присутствуют в кэше, поэтому их расширение не снижает существенно число заполнений строк кэша. Позднее расширение ветвей было исключено из Judy. Однако пакет Judy был настроен на использование наименьшего возможного числа инструкций, когда доступ вероятно будет к кэшу.

Наличие кэше CPU в современных машинах изменило многие алгоритмы. Для использования преимуществ кэша важно применять его как можно чаще. В дереве Judy наличие кэша снижает число заполнений строк кэша в 1-3 раза (или более) на поиск.

В пространстве 232 (или 2564) требуется не более 4 заполнений строк кэша для наихудшего случая доступа к плотно заполненному дереву степени 256. В пространстве 264 (или 2568) требуется 8 заполнений в наихудшем случае. На практике Judy обычно делает это гораздо эффективней. Одной из причин этого является то, что «плотность» ключей редко бывает минимально возможнойй в большинстве подпространств. Для увеличения глубины дерева Judy требуется высокая плотность в сочетании с большой численностью. Объяснять это долго. Можно провести аналогию с кучей песка. Потребуется много песка для создания высокой кучи, особенно если под каждой песчинкой должно размещаться 256 других. В 64-битовом варианте Judy для создания 8 уровней может потребоваться больше памяти, нежели имеется на планете.

Judy эффективно приспосабливается к разным уровням плотности и численности. Поскольку структурой данных Judy служит дерево деревьев, каждое субдерево является статическим пространством, которое оптимизировано в соответствии с плотностью содержащихся ключей. Для поддержки такой гибкости в 32(64)-битовом Judy имеется приблизительно 25(85) первичных и примерно столько же вторичных структур данных. Здесь описаны некоторые из них для демонстрации связи (синергии) плотности и сжатия.

С точки зрения расхода памяти (размера) дерево Judy совместно использует (без дублирования) цифровой ключ в дереве. Эта форма сжатия ключа является естественным результатом применения цифрового дерева. Было бы очень неудобно делать на это деревьях, сбалансированных по численности (и, по-видимому, это не было сделано). Каждый указатель в дереве Judy ссылается на похожее меньшее субпространство, в то же время декодируя другие 8 битов ключа (в чистом цифровом дереве ключи не хранятся внутри и определяются по положению).

Рассмотрим верхнюю часть небольшого дерева Judy (JudyL) и нижнюю часть плотно заполненного дерева Judy1. Дерево Judy с численностью 0 является просто указателем NULL. Дерево JudyL с одним ключом является корневым указателем на объект из двух слов, содержащий ключ и связанное с ним значение. Дерево JudyL с численностью два ключа является объектом из 4 слов (2 значения и 2 сортированных ключа. Дерево с численностью 3 ключа является объектом из 8 слов с (число слов + 3) значений и тремя сортированными ключами.

Это можно продолжать до численности в 32 ключа, когда формируется фактическая древовидная структура со «сжатым» узлом степени 256, которая декодирует первый байт каждого ключа. Значение 32 было выбрано потому, что именно здесь структура дерева требует эквивалентного числа заполнений строк кэша. Все объекты ниже этого узла содержат ключи, которые сокращаются по меньшей мере на первый байт.

Имеется три типа узлов, два из которых связаны с 1 заполнением строки кэша при прохождении и один — с 2. На каждом пути вниз3 по дереву при любой численности проходится не более 1 объекта с заполнением двух строк кэша. Это означает, что иногда может быть дополнительное заполнение одной строки кэша по сравнению с ожидаемым при прохождении чистого узла степени 256.

С другой стороны, густонаселенное дерево Judy1, в котором ключ декодирован на 1 байт и плотность подпространства ключей степени 256 выше 0,094 (25 ключей/пространство 256), битовая последовательность из 32 байтов (256 битов) формируется из имеющегося сортированного массива из 24 1-байтовых ключей (обработка значений опущена). В результате для ключа используется около 1,3 (32/25) байта памяти (по сравнению с 1,0). Отметим, что рост плотности (численности) на этом этапе не требует увеличения памяти для ключей. Например, при достижении плотности 0,5 (численность = 128 / пространство = 256) потребляется около 2 битов ((32/128)*8) на ключ с добавлением некоторых издержек (2,0 слова) для структуры дерева.

Отметим, что вставка или удаление ключа почти так же просты, как установки или сброс бита. Кроме того, расход памяти почти одинаков для 32- и 64-битовых деревьев Judy. При одинаковом размере ключей 32- и 64-битовые деревья Judy очень похожи по расходу памяти на ключ, глубине и производительности. Однако расход памяти в 64-битовом Judy выше, поскольку размер указателей и значений (JudyL) удваивается.

В короткой заметке невозможно описать такие детали структур данных как Root, JPM, указатели, линейные, битовые и несжатые узлы, области значений, непосредственные индексы, терминальные узлы (листья), менее сжатая форма, управления памятью, быстрый поиск листьев и подсчет деревьев. Однако базовые понятия здесь рассмотрены, а остальное можно узнать из документации.

Doug Baskins
doug@sourcejudy.com

Вольный перевод на русский язык

Николай Малых

nmalykh@protocols.ru

1Этот вариант кода не поддерживает некоторые современные процессоры. Более современный вариант доступен по ссылке. Прим. перев.

2Современные машины часто используют конвейерную запись в ОЗУ и это не вносит дополнительной задержки в Judy.

3Американские деревья растут корнем вверх. Прим. перев.




Устройство синтаксических анализаторов пакетов

             PDF

Design Principles for Packet Parsers

Glen Gibb1, George Varghese2, Mark Horowitz1, Nick McKeown1

Тезисы

Все сетевые устройства должны анализировать заголовки пакетов для выбора способов обработки пакета. Коммутатор Ethernet с 64 портами 10 Гбит/с должен анализировать миллиарды пакетов каждую секунду, извлекая поля, нужные для принятия решений. Хотя анализаторы являются необходимой частью любого коммуникационного устройства, очень мало написано об устройстве анализаторов и сравнении различных вариантов устройства. Что лучше — один быстрый анализатор или несколько медленных? Сколь дорого изменение конфигурации анализатора в «полевых» условия? Как выбор анализатора влияет на размеры элементов и потребляемую мощность?

В этой статье сравниваются варианты синтаксических анализаторов для коммутаторов и маршрутизаторов, а также описан генератор синтаксических анализаторов, создающий файлы Verilog, пригодные для загрузки в устройства. Показано, что (1) анализаторы пакетов занимают 1-2% площади микросхем, а (2) возможность программирования анализаторов лишь удваивает (достаточно малые) размеры анализатора.

1. Введение

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

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

Почему анализ пакетов представляет сложность? Размер и формат пакетов меняется от сети к сети и от пакета к пакету. Базовая структура включает один или множество заголовков, данные (payload) и может также включать трейлер. На каждом этапе инкапсуляции в заголовок включается идентификатор, показывающий тип данных, следующих после заголовка. На рисунке 1 приведен простой пример пакета TCP.

Рисунок 1. Пакет TCP.

На практике пакеты зачастую включают множество заголовков, которые содержат информацию протоколов вышележащих уровней (например, заголовки HTTP) или дополнительные данные, отсутствующие в имеющихся заголовках (например, идентификатор VLAN4 в кампусной сети или метка MPLS5 в магистрали Internet). Сегодня наличие множества заголовков в пакете стало нормой.

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

  1. Пропускная способность. Большинство анализаторов должно работать со скоростью линии, поддерживая непрерывный поток следующих один за другим пакетов минимального размера. Канал Ethernet 10 Гбит/с может доставлять новый пакет каждые 70 нсек, а современный контроллер ASIC 64 × 40 Гбит/с в коммутаторе Ethernet должен обрабатывать пакет каждые 270 пксек.

  2. Последовательность заголовков. Заголовки обычно включают поле, указывающее следующий заголовок, предлагая их последовательную обработку.

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

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

  5. Программируемость. Формат заголовка может измениться уже после создания анализатора в результате появления нового стандарта или использования сетевым оператором специальных заголовков для идентификации трафика в сети. Например, в последние годы были предложены или внедрены форматы PBB, VxLAN, NVGRE, STT, OTV.

Хотя синтаксический анализатор имеется в каждом сетевом устройстве, посвященных анализаторам работ опубликовано очень мало. Авторам известны лишь две публикации, непосредственно относящиеся к анализу пакетов [1, 8] и ни в одной из них не рассматриваются компромиссы между размером на кристалле, скоростью и потребляемой мощностью, при этом в обеих вносится неприемлемая для скоростных приложений задержка. Сопоставление по регулярным выражениям не применимо — анализ обрабатывает часть каждого пакета под управлением графа разбора, тогда как при сопоставлении regex сканируется весь пакет.

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

При разработке анализатора возникает ряд естественных вопросов. Какую долю площади кристалла и потребляемой мощности можно отдать анализатору в вариантах одного или нескольких анализаторов на микросхему? Каким должен быть размер слова при обработке заголовков? Короткие слова требуют более высоких частот, длинные позволяют обработать несколько заголовков в один прием. Насколько программируемым должен быть анализатор: Какая гибкость нужна пользователям для добавления произвольных заголовков с полями в произвольных местах?

Рассмотрим эти вопросы по порядку. Сначала описывается процесс анализа (2. Синтаксический анализ) и вводится понятие графа анализа для представления последовательности заголовков и описания конечного автомата анализа (3. Граф анализа). Затем рассматривается устройство фиксированных и программируемых анализаторов (4. Устройство анализатора) и детали генерации записей в таблицах программируемого анализатора (5. Генерация таблицы анализа). В заключение представлены принципы устройства анализаторов на примерах (6. Принципы устройства). Варианты устройства были подготовлены с использованием подготовленного инструмента, который на основе заданного графа анализа создает анализатор, параметризованный по ряду характеристик. Было сгенерировано более 500 различных анализаторов на основе библиотеки TSMC 45 nm ASIC. Для сравнения каждый анализатор настраивался на обработку пакетов в Ethernet ASIC 64 × 10 Гбит/с.

В целом эта статья:

  • фиксирует проблему устройства потоковых анализаторов пакетов (4.5. Работа в потоковом режиме);

  • выделяет сходства и различия с декодированием инструкций в процессорах (4.6. Сравнение с декодированием инструкций);

  • описывает новую методологию устройства потоковых анализаторов пакетов для оптимизации прощади, скорости и потребляемой мощности (6.1. Генератор анализаторов); в работе [8], напротив, описана реализация FPGA и теоретическая модель, не дающая представления об основных компромиссах между площадью и потребляемой мощностью в ASIC;

  • описывает многочисленные результаты, включая коммутаторы 64 × 10 Гбит/с, являющиеся важными компонентами современных сетей, и указывает принципы построения таких коммутаторов (6.2. Фиксированный анализатор, 6.3. Программируемый анализатор);

  • показывает, что программируемый анализатор занимает 1–2% площади (6.3. Программируемый анализатор);

  • показывает увеличение стоимости программируемого анализатора вдвое (6.3. Программируемый анализатор).

2. Синтаксический анализ

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

Рисунок 2. Процесс анализа.

Процесс анализа показан на рисунке 2. Большой прямоугольник обозначает анализируемый пакет, а меньшие прямоугольники с закруглением — место текущей обработки. Состояние анализатора отслеживает тип и размер текущего заголовка.

Обработка начинается с «головы» пакета (2a). Исходный тип пакета обычно не меняется для данной сети и известен анализатору (например, Ethernet). Анализатор знает структуру каждого типа заголовков, что позволяет ему найти поле (поля), указывающие размер данного заголовка и тип следующего.

Анализатор читает поле следующего заголовка как IPv4 (2b). Размер заголовка IPv4 не является постоянным — поле размера включено в заголовок, но изначально неизвестно анализатору.

Считывается размер заголовка IPv4 и состояние анализатора соответствующим образом обновляется (2c). Размер указывает положение следующего заголовка и должен быть определен до начала работы с тем.

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

3. Граф анализа

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

Рисунок 3. Примеры графов анализа.

Граф анализа является конечным автоматом (машиной состояний), который последовательно распознает заголовки в пакете. Начиная с корневого узла переходы (смена) состояний выполняются в соответствии со значениями поля следующего заголовка (next-header). Путь через граф соответствует последовательности заголовков.

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

Традиционные анализаторы используют фиксированный граф. Для поддержки различных возможных вариантов реальный граф устройства представляет собой объединение (union) графов для разных возможных случаев. На рисунке 3е показан пример графа анализа в коммутаторе — это объединение графов для отдельных случаев, включая показанные на рисунках 3a-d. Объединение включает 28 узлов и 677 путей. Данное объединение в статье называется big-union.

4. Устройство анализатора

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

4.1. Модель абстрактного анализатора

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

Рисунок 4. Абстрактный анализатор.

На рисунке 4 представлена абстрактная модель анализатора, включающая модули идентификации заголовка (header identification), извлечения полей (field extraction) и буферизации (field buffer). Данные заголовка попадают в анализатор и передаются модулям идентификации заголовков и извлечения полей. Модуль идентификации распознает заголовки и информирует модуль извлечения о типе и местоположении заголовка. Модуль извлечения считывает поля и отправляет их в модуль буферизации. Этот модуль собирает извлеченные поля, передавая их последующим этапам обработки после извлечения всех нужных полей.

Идентификация заголовка

Модуль идентификации заголовков реализует конечный автомат графа анализа (3. Граф анализа). Алгоритм 1 показывает процесс анализа, определяющий тип и размещение каждого заголовка.

Алгоритм 1. Определение типа и размера заголовка
procedure IdentifyHeaders(pkt)
	hdr = initialType
	pos = 0
	while hdr ≠ DONE do
		NotifyFieldExtraction(hdr, pos)
		len = GetHdrLen(pkt, hdr, pos)
		hdr = GetNextHdrType(pkt, hdr, pos)
		pos = pos + len
	end while
end procedure
Извлечение поля

Процесс извлечения поля прост и выполняется в соответствии с типом и местоположением поля, представленным модулю, а также списком полей для каждого типа заголовков. Алгоритм 2 показывает этот процесс.

Алгоритм 2. Извлечение полей
procedure ExtractFields(pkt, hdr, hdrPos)
	fields = GetFieldList(hdr)
	for (fieldPos, fieldLen) = fields do
		Extract(pkt, hdrPos + fieldPos, fieldLen)
	end for
end procedure

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

Буфер полей

Буфер полей аккумулирует извлеченные значения до выполнения поиска в таблице коммутатора. Извлеченные поля выводятся буфером как «широкий» вектор битов, поскольку поиск в таблице выполняется одновременно по всем полям. Вывод в форме вектора битов требует реализации буфера в форме широкого массива регистров. На каждый регистр требуется один мультиплексор (MUX) для выбора полей, возвращенных блоком извлечения.

4.2. Фиксированный анализатор

Фиксированный анализатор работает с одним графом анализа, выбранным при разработке и представляющим собой объединение графов для каждого варианта, который коммутатор должен поддерживать. Логика в фиксированном графе оптимизирована для выбранного графа анализа.

Описанное здесь устройство анализатора не отражает в точности анализаторы реальных устройств, но обесепчивает качественное представление. Как показано в параграфе 6.2. Фиксированный анализатор, размер фиксированного анализатора на кристалле существенно меньше размера буфера полей. Размер буфера определяется графом анализа и для параллельной передачи всех извлеченных полей в модули сопоставления буфер должен включать массив регистров и мультиплексоров. Отсутствие гибкости в устройстве буфера предполагает, что его размер не зависит существенно от устройства анализатора.

4.2.1. Идентификация заголовка

Модуль идентификации заголовков, показанный на рисунке 5, состоит из четырех элементов: конечный автомат (state machine), буфер, процессоры заголовков и элемент упорядочивания (sequence resolution).

Рисунок 5. Модуль идентификации заголовка.

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

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

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

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

4.2.2. Извлечение полей

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

Рисунок 6. Модуль извлечения поля.

4.3. Программируемый анализатор

Программируемый анализатор использует граф анализа, задаваемый в процессе работы. Здесь выбран подход на основе таблицы состояний для простоты понимания и реализации. Таблицы состояний легко реализуются в RAM и/или TCAM. Адресуемая по содержимому память (CAM7) — это ассоциативная память, оптимизированная для поиска, что позволяет выполнять поиск по всей памяти параллеотно для каждого входного значения. В двоичной CAM сопоставляется каждый бит, а в троичной (TCAM) не имеющие значения (don’t care) биты пропускаются при сравнении.

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

Рисунок 7. Программируемый анализатор.

Модуль идентификации заголовков упрощен по сравнению с фиксированным анализатором, как можно видеть из рисунка 8. Он содержит логику отслеживания состояний и буфер, а вся логика, относящаяся к заголовкам, перенесена в TCAM и RAM. Текущее состояние и часть буферов передаются в TCAM, откуда возвращается первая совпадающая запись. Передаваемые в TCAM байты могут быть непрерывным блоком данных или разрозненными элементами из разных мест, а общий размер может составлять от 1 байта до всего пакета. Запись RAM, соответствующая найденной в TCAM записи, считывается и указывает следующее состояние для модуля идентификации заголовков, а также совпадающие заголовки. Запись RAM может также задавать такие данные как число байтов для перемещения (к следующему заголовку) и подмножество байтов для следующего извлечения.

Рисунок 8. Идентификация заголовка.

Модуль извлечения полей почти не отличается от фиксированного анализатора, лишь таблица с местоположениями полей перенесена из модуля в RAM.

4.4. Требования производительности

Анализатор должен работать со скоростью линии для худших вариантов картины трафика в приложениях (например, коммутатор Ethernet). Невозможность анализа со скоростью линии приведет к потере пакетов при переполнении входного буфера.

Один экземпляр анализатора может оказаться неспособным работать со скоростю линии — например при тактовой частоте 1 ГГц в коммутаторе 64 × 10 Гбит/с коммутатор должен обрабатывать в среднем 640 битов за один такт. Параллельная работа нескольких экземпляров анализатора позволяет обеспечить требуемую производительность, если каждый экземпляр анализатора обрабатывает свой пакет.

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

4.5. Работа в потоковом режиме

Анализаторы можно разделить на потоковые (streaming) и прочие (non-streaming). Не поддерживающий потоки анализатор получает весь комплект заголовков до начала анализа, тогда как потоковый ведет анализ непосредственно в процессе приема пакета. Примером анализатора без поточной обработки может служить Kangaroo [8].

Не работающие с потокм анализаторы вносят задержку, связанную с ожиданием приема всей цепочки заголовков, что делает их непригодными для высокоскоростных систем с малыми задержками. Например, буферизация 125 байтов заголовков при скорости 1 Гбит/с сносит задержку в 1 мксек, что уже является проблемой для приложений ЦОД. Преимуществом анализаторов с буферизацией является возможность работать в процессе анализа с любой частью заголовков, что существенно упрощает процесс.

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

Фиксированные и программируемые анализаторы могут работать в потоковом и буферизуемом режиме. Далее рассматриваются потоковые реализации.

4.6. Сравнение с декодированием инструкций

Анализ пакетов похож на декодирование инструкций в современных процессорах CISC8 [15], когда каждая инструкция CISC преобразуется в одну или множество микроопераций в стиле RISC9 (μops). Оба эти процесса являются двухэтапными с последовательной и распараллеливаемой (non-serial) фазами. Фазами анализа являются идентификация заголовков и извлечение полей, фазами декодирования инструкций — определение размера (ILD10) и декодирование (ID11) инструкции. Система кодирования инструкций проще заголовков и не требуется декодировать размер, что позволяет использовать одну операцию определения размера для любой инструкции. Процесс ILD является последовательным, размер инструкции определяет начало следующей. ID определяет тип каждой инструкции, извлекает поля (операнды) и выдает соответствующую последовательность μops. Множество инструкций может обрабатываться параллельно, поскольку их стартовые позиции известны.

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

5. Генерация таблицы анализа

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

5.1. Структура таблицы

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

Таблица содержит столбцы для текущего заголовка (current header), его размера (current header length), искомых значений (lookup value), типа следующего заголовка (next header), и смещения поиска в следующем цикле. Каждое ребро графа анализа задает смену состояния, поэтому каждому ребру должна соответствовать запись в таблице.На рисунке 9a показан граф анализа, а на рисунке 9b — соответствующие записи таблицы.

Рисунок 9. Записи таблицы анализа.

Вместо использования всего пакета в качестве входных данных для таблицы анализа достаточно полей, указывающих размер заголовка и тип следующего заголовка, что существенно снижает размер таблицы. Например, для заголовка IPv4 достаточно 4 байтов со смещением 20). Смещение указывает поля, служащие входными данными для таблицы анализа.

5.2. Генерация таблиц

Число записей в таблице можно снизить путем кодирования в одной записи нескольких переходов и, следовательно, идентификации множества заголовков. Фрагмент графа с рисунка 9a можно представить иначе (рисунок 10a) и новая таблица будет иметь на 1 запись меньше. Снижение числа записей в таблице обеспечивает преимущество, поскольку от размера таблицы зависит занимаемая на кристалле площадь (6.3. Программируемый анализатор).

Объединение нескольких переходов в одну запись таблицы можно рассматривать как кластеризацию или слияние узлов. Кластер, соответствующий первой записи на рисунке 10a, показан на рисунке 10b.

Алгоритм генерации таблиц

Кластеризация графов является сложной задачей сетевой обработки [5, p. 209]Ю для решения которой имеется множество приближений [3, 4, 7], но они плохо подходят. Kozanitis с соавторами [8] представили алгоритм динамического программирования для снижения числа записей в таблицах Kangaroo (анализатор с промежуточной буферизацией), но этот алгоритм не подходит для потокового анализа «на лету». Алгоритм предполагает возможность доступа к данным в любой части заголовка, но потоковая модель обеспечивает возможность работы лишь с небольшим окном данных.

Рисунок 10. Кластер узлов.

Авторы разработали на основе алгоритма Kangaroo свой вариант, который подходит для потокового анализа. Входными данными алгоритма служат ориентированный ациклический граф G = (V, E), максимальное число искомых згачений (k), требуемая скорость (B) в битах за цикл и размер окна w. Алгоритм кластеризует узлы G так, что (1) для каждого кластера требуется не более k операций поиска, (2) выполняемых в окне w, (3) все пути требуют в среднем обработки не менее B битов на цикл и (4) число кластеров минимизировано. Использующий динамическое программирование алгоритм представлен уравнением (1).

Функция OPT(n, b, o) возвращает число записей таблицы, требуемых для субграфа от узла n в окне со смещением o и требуемой скоростью обработки b. Clusters(n, o) указывает все действительные кластеры, начинающиеся с узла n в окне со смещением o. Смещение окна определяет число заголовков после n, попадающих в это окно. Clusters использует число операций поиска k и размер окна w для ограничения размера кластеров. Функция Entries(c) возвращает число записей таблицы, требуемых для кластера c. Successor(c) указывает все узлы, достижимые из кластера c через одно ребро. На рисунке 11a показан кластер и соответствующие преемники (successor), а на рисунке 11b показано влияние окна w на формирование кластера.

Рисунок 11. Формирование кластера.

Рекурсивные вызовы OPT указывают число записей таблицы, требуемых для каждого узла-преемника. Значения b и o требуется обновлять. Обновленное значение b отражает число битов, потребляемых в цикле анализа, где обрабатывается c. Обновленное смещение o отражает объем данных, которые были получены и потреблены в процессе обработки c.

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

Улучшенная генерация таблиц

Описанный выше алгоритм (и Kangaroo) корректно идентифицирует минимальный набор записей таблицы лишь для графа анализа, являющегося деревом. Алгоритм независимо обрабатывает каждый субграф, что ведет к генерации разных наборов записей для некоторых перекрывающихся секций субграфов. На рисунке 12a показан фрагмент графа анализа, в котором субграфы из узлов C и K имеют совпадающие узлы F и G. Генерация разных наборов кластеров для перекрывающихся узлов ведет к ненужному росту числа записей. На рисунке 12b показан другой вариант кластеризации где для области наложения генерируется общий кластер.

Рисунок 12. Улучшение кластера.

Неоптимальные решения возникают лишь в случаях, когда к узлу ведет множество входных ребер. Эвристический подход для улучшения удаляет субграф S со множеством входных ребер из графа G и находит S назависимо. Затем находится решение для графа G − S и результаты объединяются. Объединенное решение сравнивается с предыдущим и сохраняется, если ребер в нем меньше. Сравнение должно выполняться, поскольку иногда число ребер может возрастать. Процесс повторяется для каждого субграфа с множеством входных ребер. На рисунке 12c показан этот процесс для одного субграфа.

6. Принципы устройства

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

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

Каждый из представленных анализаторов имеет пропускную способность 640 Гбит/с, если явно не указано иное. Эта производительность соответствует современным микросхемам коммутации с 64 портами 10 Гбит/с [2, 6, 10, 11]. Для достижения такой производительности нужно множество экземпляров анализатора.

6.1. Генератор анализаторов

Тщательное исследование пространства проектирования требует анализа и сравнения множества экземпляров синтаксических анализаторов. Для этого был разраюотан генератор, создающий уникальные экземпляры анализаторов по представленным графам анализа и параметрам. Генератор был собран на основе генератора микросхем Genesis [14] — инструмента для генериции вариантов микросхем с использованием «шаблонов» архитектуры и набора конфигурационных параметров приложения. Шаблоны создаются на основе Verilog и Perl, где Perl служит для генерации кода Verilog.

Генератор позволяет моделировать фиксированные и программируемые анализаторы, описанные выше. Параметрами генератора служат граф анализа, разрядность обработки, тип (фиксированный или программируемый), размер буфера полей и размер программируемой памяти TCAM/RAM. Выводом генератора являются файлы Verilog. Результаты по площади и потребляемой мощности были получены с помощью Synopsys Design Compiler G-2012.06 и библиотеки TSMC 45 нм.

Генератор доступен для загрузки по ссылке http: //yuba.stanford.edu/~grg/parser.html12.

Работа генератора

Для фиксированного анализатора важны два параметра — граф анализа и разрядность обработки. Граф задается в текстовом файле с описанием каждого типа заголовков, содержащим имена и размеры полей, указание извлекаемых полей, отображение значений полей на тип следующего заголовка, а для заголовков переменного размера — отображение, указывающее способ определения размера по значениям полей. Описание заголовка IPv4 приведено на рисунке 13.

ipv4 {
		fields {
		version	: 4,
		ihl		: 4,
		diffserv	: 8 : extract,
		totalLen	: 16,
		identification : 16,
		flags		: 3 : extract,
		fragOffset	: 13,
		ttl		: 8 : extract,
		protocol	: 8 : extract,
		hdrChecksum	: 16,
		srcAddr	: 32 : extract,
		dstAddr	: 32 : extract,
		options	: *,
	}
	next_header = map(fragOffset, protocol) {
		1 : icmp,
		6 : tcp,
		17 : udp,
	}
	length = ihl * 4 * 8
	max_length = 256
}

Рисунок 13. Заголовок IPv4.


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

Рисунок 14. Области обработки графа.

Генератор делит граф анализа с использованием заданной разрядности обработки, как показано на рисунке 14. каждая область показывает заголовки, которые могут быть видны в одном цикле. В затененной на рисунке области может поместиться 1 или 2 тега VLAN. Процессоры заголовков инициируются с нужным смещением для каждой из указанных областей.

Обработка заголовка может быть отложена генератором до следующей области с целью минимизации сдвигов по заголовку. На рисунке 14 затененная область может включать 4 первых байта верхнего заголовка IPv4, однако в этом случае анализатору потребуется два процессора IPv4 — один для смещения 0 (VLAN → IPv4), другой для 4 (VLAN → VLAN → IPv4).

Таблица извлечения полей (4.2.2. Извлечение полей) генерируется с использованием помеченных для чтения полей (в описании графа анализа). Запись таблицы для заголовка IPv4 будет указывать извлечение байтов 1, 6, 8, 9 и 12–19. Размер буфера полей задается с учетом всех извлекаемых полей.

Для программируемого анализатора нужно указать разрядность обработки, размер таблицы анализа, размер окна, а также число и размер поиска в таблице анализа. Граф анализа не нужен как параметр генератора для программируемого анализатора, поскольку этот граф задается в процесмсе работы.

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

Генератор не создает TCAM и RAM для таблицы состояний анализа. Для этого нужен генератор от производителя, учитывающий используемую технологию. Вместо этого генератор создает «фиктивную» (не синтезируемую) память для имитации.

Тестовый стенд служит для проверки создаваемых генератором анализаторов. Граф анализа используется для создания входных пакетов и проверки векторов выходных заголовков. Разрядность обработки определяет «ширину» ввода байтовых последовательностей пакета.

6.2. Фиксированный анализатор

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

Разрядность обработки увеличивает площадь, но снижает энергопотребление.

Пропускная способность одного экземпляра анализатора определяется выражением r = w × f , где w — разрядность (ширина) обработки, а f — тактовая частота. Для фиксированной пропускной способности w ∝ 1/f .

На рисунке 15a показана зависимость прощади и потребяемой мощности одного анализатора от разрядности при скорости 10 Гбит/с. Повышение разрядности увеличивает занимаемую площадь за счет размещения дополнительных ресурсов, но энергопотребление снижается за счет уменьшения тактовой частоты (причем быстрее, чем растет объем логики13). Потребность в дополнительных ресурсах обусловлена двумя причинами. Во-первых, для более широкой шины требуется больше линий, регистров, мультиплексоров и т. п. Во-вторых, в области обработки (окне) могут появляться дополнительные заголовки (6.1. Генератор анализаторов), для которых потребуются дополнительные экземпляры процессоров заголовков.

Используйте меньше быстрых процессоров при агрегировании экземпляров анализатора.

На рисунке 15b показана зависимость прощади и потребяемой мощности экземпляров анализатора от их скорости при агрегировании до пропускной способности 640 Гбит/с. Можно видеть незначительный выигрыш в энергопотреблении при небольшом числе быстрых анализаторов. Общая площадь при этом почти не меняется. Скорость одного экземпляра анализатора невозможно увеличивать бесконечно и при достижении некого порога начинается рост площади и потребляемой мощности (не показано на графике).

Рисунок 15. Влияние устройства на площадь и потребляемую мощность.


Основную площадь занимают буферы полей.

На рисунке 15c показаны площади, занимаеые функциональными блоками для нескольких графов анализа. Буферы полей во всех случаях доминируют, занимая примерно 2/3 площади. Некоторая гибкость обеспечивается за счет создания буфера в виде массива регистров для параллельной передачи данных нисходящим элементам (4.1. Модель абстрактного анализатора ).

Число извлекаемых анализатором битов определяет плошадь (при фиксированной разрядности).

На рисунке 15d приведена зависимость площади от числа извлекаемых битов для нескольких графов анализа. Практически все точки ложатся на одну прямую. Красным крестиком указана точка для простого графа анализа, приведенного на рисунке 15e. Этот граф включает 3 узла, но преобразуется в такое число битов, как и граф big-union. Точка лежит слегка ниже общей прямой, поскольку в этом случае проще идентификация заголовка и извление полей.

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

6.3. Программируемый анализатор

К программируемым анализаторам применимы описанные выше принципы, которые дополняются указанными здесь.

Влияния таблицы состояний и буфера полей имеют одинаковый порядок.

На рисунке 15f показано сравнение площадей для фиксированного (с графом big-union) и программируемого анализатора. Оба анализатора включают буферы полей размером 4 Кбит, а программируемый анализатор имеет 256 × 40 бит TCAM (запись содержит 8 бит состояния и 2 × 16 бит полей заголовков). На рисунке видно, что программруемый анализатор занимает почти вдвое большую площадь.

Важно отметить, что размер фиксированного анализатора приведен с учетом выбранного графа, а размер программируемого должен учитывать все ожидаемые графы анализа. При использовании программируемого анализатора с простым графом может остаться много свободных ресурсов. Например, граф сети предприятия требует лишь 672 бита из буфера полей 4 Кбит. Буфера полей 4 Кбит и 256 × 40 бит TCAM более чем достаточно для реализации всех проверяемых графов анализа. Их общий размер вдвое превышает размер, требуемый для big-union.

На рисунке 15f показана одна точка, но сравнение по таблицам состояний анализатора и размерам буфера полей показывает, что программируемый анализатор занимает в 1,5 — 3 раза большую площадт по сравнению с фиксированным (при разумном размере таблиц и буферов).

Анализатор занимает незначительную часть кристалла микросхемы коммутатора. Фиксированный анализатор на рисунке 15f занимает 2,6 мм2, а программируемый — 4,4 мм2 при технологии 45 нм. Площадь современного коммутатора 64 × 10 Гбит/с составляет 200−400 мм214.

Минимизация входных данных поиска в таблице анализа.

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

В таблице 1 показано требуемое число записей и общий размер таблицы для разного числа входных элементов по 16 бит для графа анализа big-union. Общее число записей незначительно снижается при переходе от 1 к 3 операциям поиска, но общий размер таблицы существенно растет. Число просмотров таблицы следует минимизировать для снижения общей площади анализатора, поскольку эта таблица является одним из основных потребителей площади.

Таблица 1. TCAM.

Число входных элементов

Число записей

Разрядность (бит)

Размер (бит)

1

113

24

2712

2

105

40

4200

3

99

56

5544

4

102

72

7344

В этом примере число записей в таблице поиска увеличивается, когда число просмотров превышает 3. Это вызвано эвристикой снижения числа записей в таблице, которая рассматривает по очереди каждый субграф с несколькими входными ребрами. Решение удалить субграф может повлиять на поиск следующего субграфа. В этом случае последовательность выбора при трех поисках на цикл работает лучше, чем выбор при 4 поисках за цикл.

Исследование показало, что два поиска значений по 16 бит обеспечивают хороший баланс размера таблицы состояний анализа и поддержки скорости линии для широкого диапазона заголовков. Все используемые сегодня основные заголовки имеют размер не менее 4 байтов, а большинство кратны этому размеру. Большинство 4-байтовых заголовков включает лишь одно значение для поиска, что позволяет идентифицировать два заголовка по 4 байта за один цикл. В будущем не предполагается большого числа более коротких заголовков, поскольку в них не разместить достаточный объем информации.

7. Смежные работы

Kangaroo [8] представляет собой программируемый анализатор с разбором множества заголовков в одном цикле. Kangaroo буферизует все данные заголовка перед анализом, что вносит задержку, которая слишком велик для современных коммутаторов. Attig [1] представил язык для описания последовательностей заголовков вместе с анализатором на основе FPGA и компилятором. В микросхемах коммутаторов используются микросхемы ASIC, а не FPGA, что предявляет иные требования к устройству анализаторов. Однако таких работ на сегодняшний день не известно. Neither work explores design trade-offs or extract general parser design principles.

Много написано об аппаратном ускорении поиска по регулярным выражениям (например, [12,16,17]) а анализаторах уровня приложений (например, [13, 18]). Синтаксический анализ — это исследование небольшой части пакета, описываемой графом анализа, а при сопоставлении с регулярным выражением выполняется просмотр всех байтов пакета. Различия в областях поиска, обнаруживаемых элементах и требованиях к производительности ведут к разным подходам в проектировании. Анализ на прикладных уровнях достаточно часто включает сопоставление с регулярными выражениями.

Производительность программных анализаторов можно повысить за счет использования упрощенного быстрого пути и полного медленного пути [9]. Быстрый путь обслуживает большую часть входных данных, а по медленному идут лишь редко встречающиеся входные данные. Однако это не применимо к аппаратным синтаксическим анализаторам, поскольку коммутаторы должны гарантировать производительность линии для худших вариантов картины трафика (программные анализаторы таких гарантий не дают).

8. Заключение

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

Исследование показало, что основную площадь, используемую анализатором на кристалле, занимает буфер полей для фиксированных анализаторов и комбинация такого буфера с таблицей анализа для программируемых анализаторов. Множество анализаторов можно объединить для повышения пропускной способности и применение небольшого числа скоростных анализаторов обеспечивает преимущество по потребляемой мощности (без преимущества по площади). Программируемость анализаторов стоит недорого — это увеличивает площадь самого анализатора вдвое, но площадь кристалла лишь на 1 — 2%.

9. Литература15

[1] M. Attig and G. Brebner. 400 Gb/s Programmable Packet Parsing on a Single FPGA. In Proc. ANCS ’11, pages 12–23, 2011.

[2] Broadcom Trident II Ethernet Switch Series. http://www.broadcom.com/products/Switching/Enterprise/BCM56850-Series.

[3] G. Even, J. Naor, S. Rao, and B. Schieber. Fast approximate graph partitioning algorithms. SIAM Journal on Computing, 28(6):2187–2214, 1999.

[4] C. M. Fiduccia and R. M. Mattheyses. A linear-time heuristic for improving network partitions. In Proc. DAC ’82, pages 175–181, 1982.

[5] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

[6] Intel Ethernet Switch Silicon FM6000. http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ethernet-switch-fm6000-sdn-paper.pdf16.

[7] B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell Systems Technical Journal, (49):291âĂŞ–307, 1970.

[8] C. Kozanitis, J. Huber, S. Singh, and G. Varghese. Leaping Multiple Headers in a Single Bound: Wire-Speed Parsing Using the Kangaroo System. In Proc. INFOCOM 2010, pages 1–9, Mar. 2010.

[9] S. Kumar. Acceleration of Network Processing Algorithms. PhD thesis, Washington University, 2008.

[10] Marvell Prestera CX. https://origin-www.marvell.com/switching/prestera-cx/17.

[11] Mellanox SwitxhX-2. http://www.mellanox.com/sdn/18.

[12] J. Moscola, Y. Cho, and J. Lockwood. A Scalable Hybrid Regular Expression Pattern Matcher. In Proc. FCCM ’06., pages 337–338, 2006.

[13] J. Moscola, Y. Cho, and J. Lockwood. Hardware-Accelerated Parser for Extraction of Metadata in Semantic Network Content. In IEEE Aerospace Conference ’07, pages 1–8, 2007.

[14] O. Shacham, O. Azizi, M. Wachs, W. Qadeer, Z. Asgar, K. Kelley, J. Stevenson, S. Richardson, M. Horowitz, B. Lee, A. Solomatnikov, and A. Firoozshahian. Rethinking Digital Design: Why Design Must Change19. IEEE Micro, 30(6):9–24, Nov.-Dec. 2010.

[15] J. P. Shen and M. Lipasti. Modern Processor Design: Fundamentals of Superscalar Processors. McGraw-Hill, 2005.

[16] J. Van Lunteren. High-Performance Pattern-Matching for Intrusion Detection. In Proc. INFOCOM ’06, pages 1–13, 2006.

Перевод на русский язык

Николай Малых

nmalykh@protocols.ru

1Stanford University.

2Microsoft Research.

3Access-control list.

4Virtual LAN [20] — виртуальная ЛВС.

5Multiprotocol Label Switching [19] — многопротокольная коммутация по меткам.

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

7Content-addressable memory.

8Complex Instruction Set Computing — архитектура процессора с полным набором команд.

9Restricted (Reduced) Instruction Set Computing — архитектура процессора с ограниченным (упрощенным) набором команд.

10Instruction length decode — декодирование размера инстукции (команды).

11Instruction decode — декодирование инструкции.

12В настоящее время исходный код генератора перенесен на Github — https://github.com/grg/parser-gen.

13Заявление странное, поскольку приведенный график показывает иное. Прим. перев.

14Информация получена из разговора с сотрудником производителя микросхем.

15Большая часть ссылок на доступные в сети документы добавлена при переводе.

16Приведенная в статье ссылка не работает. Можно воспользоваться другой. Прим. перев.

17Приведенная в статье ссылка не работает. Можно воспользоваться другой. Прим. перев.

18Приведенная в статье ссылка не работает. Можно воспользоваться другой. Прим. перев.

19Описание и код генератора Genesis доступны по ссылке. Прим. перев.