RISC-V P4

PDF

Постановка задачи

Для выполнения перспективных работ возникла задача проверки работоспособности приложений P4 и компилятора P4C на аппаратной платформе с процессором RISC-V. В качестве платформы была выбрана плата HiFive Unleashed производства компании SiFive. Для этой платформы имеется ряд SDK, основанных на ОС Linux и доступных в исходном коде. После ряда экспериментов было выбрано в качестве основы решение SiFive Freedom Unleashed SDK на основе среды разработки OpenEmbedded (Yocto, OE). Репозиторий исходных кодов включает компоненты, оптимизированные для платы HiFive Unleashed, что позволило сразу же перейти к созданию образа с нужными компонентами P4. Создание и установка базового образа с компонентами P4 были описаны ранее. Здесь же более подробно рассматривается текущее состояние использованных компонент, возникшие проблемы и возможные способы их решения. Сборка образа выполнялась в среде Mageia Linux v7.1.

Набор компонент

Для экспериментов были выбраны модель BMV2 с библиотекой PI и компилятор P4C. Все эти компоненты зависят от библиотеки Judy, поэтому работа началась со сборки этой библиотеки, отсутствующей в репозитории meta-sifive.

Библиотека Judy

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

В процессе компиляции пакета создаются два исполняемых файла (JudyLTablesGen и Judy1TablesGen), которые запускаются для генерации таблиц (файлы C), применяемых далее в процессе компиляции. Проблема заключается в том, что создаются исполняемые файлы для процессора RISC-V, а запускаются они в среде кросс-компиляции и, естественно, не могут работать. Эта проблема известна уже давно (см., например, https://sourceforge.net/p/judy/bugs/21/ и https://www.linuxquestions.org/questions/linux-software-2/cross-compiling-libjudy-608455/), но решения найти не удалось, поэтому был выбран другой подход, представляющийся более реальным.

Библиотека была собрана непосредственно на платформе HiFive Unleashed1 и созданные таблицы были перенесены в среду кросс-компиляции, а запуск программ генерации таблиц был исключен из соответствующих файлов Makefile. Собранная в результате библиотека Judy работает при загрузке образа на платформе HiFive Unleashed.

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

Библиотека PI

PI представляет собой набор API (исходный код) для взаимодействия с объектами, определенными в программах P4 (таблицы, счетчики, измерители). Для сборки и работы требуется выполнить ряд зависимостей, включая пакет behavioral-model (bmv2). Но для сборки этого пакета требуется наличие PI. В результате образуется циклическая зависимость, которая не позволяет собрать пакеты в среде OE. Приходиться отказаться от поддержки BMV2. Остальная часть настройки и сборки проходит без проблем и пакет удается включить в образ.

Пакет BMV2

Этот пакет (исходный код) включает прототипы коммутаторов и маршрутизатора, работающих на основе кода P4. Некоторые фрагменты кода P4 представлены в примерах. Настройка и сборка пакета серьезных проблем не вызвали, пока не была предпринята попытка включить библиотеку Apache Thrift, без которой собирались лишь библиотеки, но не исполняемые программы (simple_switch и др.), что нас явно не устроило.

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

| checking dynamic linker characteristics... (cached) GNU/Linux ld.so 
| checking how to hardcode library paths into programs... immediate 
| checking whether riscv64-oe-linux-g++    -fstack-protector-strong  -D_FORTIFY_SOURCE=2 -Wformat -Wformat-security -Werror=format-security --sysroot=/OE/sifive-new/build/tmp-glibc/work/riscv64-oe-linux/bm/1.13.0+
gitAUTOINC+9a331b900c-r0/recipe-sysroot supports C++11 features by default... yes 
| checking for thrift... no 
| checking thrift/Thrift.h usability... no 
| checking thrift/Thrift.h presence... no 
| checking for thrift/Thrift.h... no 
| configure: error: Thrift headers not found. Install Thrift from http://thrift.apache.org/docs/install/ 
| WARNING: /OE/sifive-new/build/tmp-glibc/work/riscv64-oe-linux/bm/1.13.0+gitAUTOINC+9a331b900c-r0/temp/run.do_configure.3659:1 exit 1 from 'exit 1' 
ERROR: Task (/OE/sifive-new/meta-poPingUI/recipes-p4/bm/bm_git.bb:do_configure) failed with exit code '1'

Явное добавление в файл задания зависимости от thrift и thrift-native проблему не решило.

| checking for thrift... /OE/sifive-new/build/tmp-glibc/work/riscv64-oe-linux/bm/1.13.0+gitAUTOINC+9a331b900c-r0/recipe-sysroot-native/usr/bin/thrift 
| checking thrift/Thrift.h usability... yes 
| checking thrift/Thrift.h presence... yes 
| checking for thrift/Thrift.h... yes 
| checking thrift/stdcxx.h usability... no 
| checking thrift/stdcxx.h presence... no 
| checking for thrift/stdcxx.h... no 
| checking for thrift version... configure: error: in `/OE/sifive-new/build/tmp-glibc/work/riscv64-oe-linux/bm/1.13.0+gitAUTOINC+9a331b900c-r0/build': 
| configure: error: cannot run test program while cross compiling 
| See `config.log' for more details 
| WARNING: /OE/sifive-new/build/tmp-glibc/work/riscv64-oe-linux/bm/1.13.0+gitAUTOINC+9a331b900c-r0/temp/run.do_configure.9810:1 exit 1 from 'exit 1'

При просмотре журнала настройки конфигурации сборки (config.log) подтвердилось, что кросс-компиляция пакета не поддерживается.

configure:16615: error: cannot run test program while cross compiling

Таким образом, создание полноценного пакета BMV2 в среде кросс-компиляции оказалось невозможным и остается лишь собирать пакет непосредственно на платформе HiFive Unleashed.

Компилятор P4C

Пакет P4C представляет собой прототип компилятора, поддерживаюзий спецификации P414 и P416. При попытке собрать пакет в кросс-среде OE возникли проблемы, аналогичные ситуации с библиотеков Judy, описанной выше. Здесь также генерируется ряд файлов исходного кода с помощью созданной в процессе компиляции программы. Путем переноса файлов, созданных при сборке на платформе HiFive Unleashed и исключения одной строки из файла build.ninja, управляющего сборкой, проблему удалось решить.

Заключение

Проведенные эксперименты показывают, что собрать образ Linux для платы HiFive Unleashed (это справедливо и для других плат) с поддержкой P4 в среде кросс-компиляции OpenEmbedded на сегодняшний день не представляется возможным. Для решения этой задачи требуется внести достаточно серьезные изменения в исходный код ряда компонент и библиотек.

Работа выполнена в рамках проекта «Орион».

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

nmalykh@protocols.ru

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

2Она включена по умолчанию и для отключения нужна опция —without-thrift.




Сетевой стек thrift

PDF

Оригинал

Простое представление сетевого стека Apache Thrift приведено на рисунке

  +-------------------------------------------+
  | Server                                    |
  | (однопотоковый, управляемый по событиям ) |
  +-------------------------------------------+
  | Processor                                 |
  | (создан компилятором)                     |
  +-------------------------------------------+
  | Protocol                                  |
  | (JSON, compact и т. п.)                   |
  +-------------------------------------------+
  | Transport                                 |
  | (raw TCP, HTTP и т. п.)                   |
  +-------------------------------------------+

Transport

Транспортный уровень обеспечивает простую абстракцию чтения-записи из сети или в сеть. Это позволяет Thrift отвязать нижележащий (базовый) транспорт от остальной части системы (например, сериализации и десериализации). Интерфейс Transport обеспечивает ряд методов (неполный список):

  • open;

  • close;

  • read;

  • write;

  • flush.

В дополнение к интерфейсу Transport Thrift использует интерфейс ServerTransport для восприятия и создания примитивов транспортных объектов. Этот интерфейс применяется в основном на серверной стороне для создания новых транспортных обектов при входящих соединениях. Интерфейс ServerTransport поддерживает методы:

  • open;

  • listen;

  • accept;

  • close.

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

  • file — чтение и запись дисковых файлов;

  • http — взаимодействие по протоколу http.

Protocol

Абстракция протокола обеспечивает механизм отображения хранящихся в памяти структур данных в «проводной» формат (wire-format). Иными словами, протокол определяет использование типами данных нижележащего транспорта для кодирования и декодирования себя. Таким образом, реализация протокола управляет схемой кодирования и отвечает за сериализацию и десериализацию. Примеры протоколов включают JSON, XML, plain text, compact binary.

Функции интерфейса Protocol указаны ниже.

writeMessageBegin(name, type, seq)
writeMessageEnd()
writeStructBegin(name)
writeStructEnd()
writeFieldBegin(name, type, id)
writeFieldEnd()
writeFieldStop()
writeMapBegin(ktype, vtype, size)
writeMapEnd()
writeListBegin(etype, size)
writeListEnd()
writeSetBegin(etype, size)
writeSetEnd()
writeBool(bool)
writeByte(byte)
writeI16(i16)
writeI32(i32)
writeI64(i64)
writeDouble(double)
writeString(string)

name, type, seq = readMessageBegin()
                  readMessageEnd()
name = readStructBegin()
       readStructEnd()
name, type, id = readFieldBegin()
                 readFieldEnd()
k, v, size = readMapBegin()
             readMapEnd()
etype, size = readListBegin()
              readListEnd()
etype, size = readSetBegin()
              readSetEnd()
bool = readBool()
byte = readByte()
i16 = readI16()
i32 = readI32()
i64 = readI64()
double = readDouble()
string = readString()

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

  • binary — достаточно простое двоичное кодирование, где размер и тип поля представляются байтами, за которыми следуют значения полей;

  • compact — см. THRIFT-110;

  • json.

Processor

Уровень Processor инкапсулирует чтение данных из входного потока и запись в выходной поток. Потоки на входе и выходе представляются объектами уровня Protocol. Интерфейс Processor крайне прост и имеет вид

interface TProcessor {
    bool process(TProtocol in, TProtocol out) throws TException
}

Реализации процессора для конкретных серверов создаются компилятором. Процессов, по существу, считывает данные из «провода» (с помощью протокола ввода), передает их обработчику (реализуется пользователем) и записывает отклик в «провод» (с помощью протокола вывода).

Server

Сервер объединяет перечисленные выше функции:

  • создание транспорта;

  • создание протоколов ввода-вывода для транспорта;

  • создание процессора на основе протоколов ввода-вывода;

  • ожидание входящих вызовов и передача их процессору.


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

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

nmalykh@protocols.ru




BMv2 simple_switch

PDF

Оригинал

Модель bmv2 позволяет разработчикам реализовать свою архитектуру программируемого коммутатора на основе P4. Архитектура simple_switch подходит для большинства пользователей, поскольку она близка к абстрактной модели коммутатора, описанной в спецификации P414.

Язык P416 поддерживает разную архитектуру, например, несколько вариантов архитектуры для одного коммутатора, адаптера NIC1 и т. п. Архитектура v1model в составе компилятора p4c была разработана в соответствии с архитектурой коммутатора P414, что упрощает автоматическую трансляцию программ P414 в программы P416 с архитектурой v1model. Имеется несколько различий между P414 и v1model, описанных ниже (прежде всего имена метаданных).

Язык P416 сейчас включает переносимую архитектуру коммутации PSA2 определенную в отдельной спецификации. Архитектура PSA к октябрю 2019 г. уже была частично реализована, но пока не завершена. Она будет выполнена в виде программы psa_switch отдельно от описанной здесь программы simple_switch.

Этот документ описывает архитектуру simple_switch для программистов P4.

Стандартные метаданные

Для программ P416, использующих архитектуру v1model и включающих файл v1model.p4, все описанные ниже поля являются частью структуры standard_metadata_t.

Для программ P414 все описанные ниже поля являются частью предопределенного заголовка standard_metadata.

При маркировке описанных полей применяются два сокращения в маркировке имен полей:

  • поле sm14 определено в спецификации P414 v1.0.4 (раздел 6 «Standard Intrinsic Metadata»;

  • поле v1m определено в файле p4include/v1model.p4 репозитория p4c и предназначено для программ P416, собранных для архитектуры v1model.

Поля метаданных перечислены ниже.

ingress_port (sm14, v1m)

Для новых пакетов указывает номер порта, принявшего пакет (только чтение).

packet_length (sm14, v1m)

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

egress_spec (sm14, v1m)

Может задаваться входным кодом для указания выходного порта. Примитив P414 drop и примитив действия v1model mark_to_dropимеют побочный эффект назначения этому поля зависящего от реализации значения DROP_PORT3, в результате чего пакет будет отброшен в конце входной обработки без сохранения в буфере и передачи на выходную обработку. Относительный приоритет этого поля по сравнению с другими операциями рассмотрен в параграфе «Псевдокод для завершения входной и выходной обработки». Если программа P4 назначает egress_spec=DROP_PORT, ей следует выполнять процедуру after-ingress pseudocode, даже если она никогда не вызывает mark_to_drop (P416) или drop (P414).

egress_port (sm14, v1m)

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

egress_instance (sm14)

Переименованное поле egress_rid в simple_switch.

instance_type (sm14, v1m)

Содержит значение, которое может прочитать код P4. Во входном коде это значение позволяет определить пришел пакет из порта (NORMAL) или является результатом примитива повторного представления (RESUBMIT) или рециркуляции (RECIRC). При выходной обработке может служить для для определения был пакет обработан в результате примитива клонирования ingress-to-egress (INGRESS_CLONE), egress-to-egress (EGRESS_CLONE), групповой репликации при входной обработке (REPLICATION) или является обычным индивидуальным пакетом со входа (NORMAL). Пока подобные константы не являются предопределенными, можно применять этот список.

parser_status (sm14) или parser_error (v1m)

Поле parser_status задано в спецификации P414 и переименовано в parser_error в v1model. Значение 0 (sm14) или error.noError (P416 + v1model) говорит об отсутствии ошибок. Остальные значения указывают код ошибки.

parser_error_location (sm14)

Отсутствует в v1model.p4 и не реализовано в simple_switch.

checksum_error (v1m)

Доступно лишь для чтения. 1 указывает ошибку контрольной суммы при вызове verify_checksum, иначе поле содержит 0. Вызовы verify_checksum для v1model следует выполнять в элементе VerifyChecksum, выполняемом после анализа, но до входной обработки.

Внутренние метаданные

Каждая архитектура обычно определяет внутренние поля метаданных, используемые в дополнение к стандартным метаданным для расширения функциональности. В simple_switch используется 2 внутренних заголовка метаданных. Архитектура не требует этих заголовков и программу P4 можно написать и запустить ее в simple_switch без них. Однако эти заголовки нужны для включения некоторых функций simple_switch. Для большинства полей нет строгих требований по размеру, но рекомендуется следовать приведенным ниже описаниям. Некоторые поля доступны напрямую (чтение или/и запись), другие — только через примитивы действий.

Заголовок intrinsic_metadata

Для программ P416 с архитектурой v1model, включающих файл v1model.p4, все перечисленные ниже поля являются частью структуры standard_metadata_t и определять свою структуру для них не требуется.

Для программ P414 рекомендуется определять и создавать показанный ниже заголовок в каждой программе P4 для архитектуры simple_switch.

header_type intrinsic_metadata_t {
    fields {
        ingress_global_timestamp : 48;
        egress_global_timestamp : 48;
        mcast_grp : 16;
        egress_rid : 16;
    }
}
metadata intrinsic_metadata_t intrinsic_metadata;

ingress_global_timestamp

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

egress_global_timestamp

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

mcast_grp

Требуется для поддержки групповой адресации. Поле должно записываться во входном конвейере, гкогда пакет будет сочтен групповым (0 если нет). Значение поля должно соответствовать одной из multicast-групп, настроенных на интерфейсах bmv2 в процессе работы. Приоритет по сравнению с другими оперциями в конце входной обработки описан в параграфе «Псевдокод для завершения входной и выходной обработки».

egress_rid

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

Заголовокqueueing_metadata

Для программ P416 с архитектурой v1model, включающих файл v1model.p4, описанные поля являются частью структуры типа standard_metadata_t. Не требуется определять для этих полей свою структуру.

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

header_type queueing_metadata_t {
    fields {
        enq_timestamp : 48;
        enq_qdepth : 16;
        deq_timedelta : 32;
        deq_qdepth : 16;
        qid : 8;
    }
}
metadata queueing_metadata_t queueing_metadata;

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

enq_timestamp

Временная метка (мксек) первого включения пакета в очередь.

enq_qdepth

Глубина очереди при первом размещении пакета в ней, выраженная числом пакетов, а не их общим размером.

deq_timedelta

Время (мксек) нахождения пакета в очереди.

deq_qdepth

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

qid

При наличии множества очередей (например, по приоритетам) на каждом выходном порту каждой очереди присваивается уникальный идентификатор, который записывается в это поле. В остальных случаях поле имеет значение 0. Отметим, что поле qid не входит в тип standard_metadata_t модели v1model.

Поддерживаемые примитивы действий

Поддерживаются основные стандартные примитивы действий P414. Однако необязательные параметры не поддерживаются в bmv2, поэтому все указанные параметры являются обязательными. Полный список примитивов можно найти в файле primitives.cpp.

Псевдокод для завершения входной и выходной обработки

После входного конвейера (after-ingress) — краткая форма.

if (был вызван примитив clone) {
    создается клон(ы) пакета в соответствии с сессией clone
}
if (digest для генерации) {   // поскольку код назвается generate_digest
    передается сообщение digest программам уровня управления
}
if (был вызван примитив resubmit) {
    повтор входной обработки исходного пакета
} else if (mcast_grp != 0) {  // поскольку код присвоил значение mcast_grp
    групповая передача пакета в выходные порты группы mcast_grp
} else if (egress_spec == DROP_PORT) {  // например, в результате вызова drop/mark_to_drop
    отбрасывание пакета
} else {
    индивидуальная передача пакета в порт egress_spec
}

После входного конвейера (after-ingress) для определения, что произойдет в пакетом после завершения входной обработки (более подробная форма).

if (был вызван примитив clone) {
    // Это будет выполняться при вызове кодом примитива clone или
    // clone3 из программы P416 или примитива clone_ingress_pkt_to_egress
    // из программы P414 в процессе входной обработки.

    Могут создаваться клоны пакета, которые помещаются в буферы, заданные
    выходными портами, указанными для сеанса клонирования, номер которого
    был задан параметром session при последнем вызове примитива clone.

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

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

    Для действий clone3 (P416) и clone_ingress_pkt_to_egress (P414)
    также сохраняются финальные входные значения полей метаданных,
    заданных в списке аргумента, за исключением установки в поле
    instance_type значения PKT_INSTANCE_TYPE_INGRESS_CLONE.

    Каждый клон будет снова обрабатываться анализатором. Во многих
    случаях анализ будет просто давать те же заголовки, которые были
    получены ранее, но если анализатор меняет свое поведение в 
    зависимости от поля standard_metadata.instance_type, они изменятся.

    После анализа обработка каждого клона продолжается от начала
    выходного кода.
    // Выполняется приведенный ниже код
}
if (digest to generate) {
    // Выполняется при вызове кодом примитива generate_digest в
    // процессе входной обработки.
    Уровню управления передается сообщение digest со значениями полей,
    заданных в списке.
    // Выполняется приведенный ниже код
}
if (resubmit was called) {
    // Вполняется при вызове кодом примитива resubmit в процессе
    // входной обработки.
    Снова выполняется входная обработка пакета с неизменным содержимым
    и метаданными. Сохраняются финальные выходные значения всех полей,
    указанных в списке аргумента последнего вызова примитива resubmit(), 
    за исключением назначения instance_type = PKT_INSTANCE_TYPE_RESUBMIT.
} else if (mcast_grp != 0) {
    // выполняется при установке кодом standard_metadata.mcast_grp в
    // процессе входной обработки. В simple_switch нет специального
    // примитива для этого. Используется стандартный оператор присваивания
    // в P416 или примитив P414 modify_field().
    Могут создаваться копии пакета на базе списка пар (egress_port, egress_rid),
    заданного уровнем управления для значения mcast_grp value. Каждая копия
    помещается в соответствующую очередь. В поле instance_type каждой копии
    будет значение PKT_INSTANCE_TYPE_REPLICATION.
} else if (egress_spec == DROP_PORT) {
    // Выполняется при вызове кодом примитива mark_to_drop (P416) или drop (P414)
    // в процессе входной обработки.
    Пакет отбрасывается.
} else {
    Помещается в очередь каждая копия для порта egress_port = egress_spec.
}

После выходного конвейера (after-egress) — краткая форма.

if (был вызван примитив clone) {
    Создаются клоны пакета в соответствии с настройками сессии clone.
}
if (egress_spec == DROP_PORT) {  // e.g. because your code called drop/mark_to_drop
    Пакет отбрасывается.
} else if (был вызван примитив recirculate) {
    Начинается повторная входная обработка проанализированного пакета.
} else {
    Пакет передается в порт egress_port.
}

После выходного конвейера (after-egress) для определения действий после завершения выходной обработки (более подробная форма).

if (был вызван примитив clone) {
    // Выполняется при вызове примитива clone или clone3 в коде P416 или
    // clone_egress_pkt_to_egress в P414 при выходной обработке.

    Могут создаваться клоны пакета, которые помещаются в буферы, заданные
    выходными портами, указанными для сеанса клонирования, номер которого
    был задан параметром session при последнем вызове примитива clone.

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

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

    Если выполнялось действие clone3 (P416) или clone_egress_pkt_to_egress 
    (P414), сохраняются также финальные выходные значения полей метаданных,
    указанных в списке аргумента, за исключением установки в instance_type
    значения PKT_INSTANCE_TYPE_EGRESS_CLONE. Каждый клон будет иметь поля
    standard_metadata, переопределенные в начале выходной обработки
    (например, egress_port, egress_spec, egress_global_timestamp и т. п.)

    Обработка каждого клона будет продолжаться с начала выходного конвейера.
    // Выполняется приведенный ниже код
}
if (egress_spec == DROP_PORT) {
    // Выполняется при вызове примитива mark_to_drop (P416) или drop (P414) 
    // в процессе выходной обработки.
    Drop packet.
} else if (был вызван примитив recirculate) {
    // Выполяется при вызове recirculate во время выходной обработки.
    Заново выполняется входная обработка пакета, как созданного синтезатором,
    со всеми изменениями в процессе входной и выходной обработки. Сохраняются
    финальные выходные значения полей, заданных в списке аргумента при 
    последнем вызове примитива recirculate, за исключением установки в поле
    instance_type значения PKT_INSTANCE_TYPE_RECIRC.
} else {
    Пакет передается в выходной порт egress_port. Поскольку поле egress_port 
    доступно при выходной обработке лишь для чтения, отметим, что его значение
    должно быть определено в процессе входной обработки для обычных пакетов. 
    Единственным исключением является выполнение примитива clone при выходной
    обработке, где egress_port определяется уровнем управления для сеанса clone.
}

Поддерживаемые типы таблиц соответствия

Коммутатор simple_switch поддерживает поля таблиц ключей для всех перечисленных ниже значений match_kind:

  • exact из спецификации P416;

  • lpm (longest prefix match) из спецификации P416;

  • ternary из спецификации P416;

  • optionalиз v1model.p4;

  • range из v1model.p4;

  • selector из v1model.p4.

Поле selector поддерживается только для таблиц с реализацией действия selector.

Если таблица имеет более одного ключевого поля lpm, она отвергается реализацией p4c BMv2. Это может быть слегка обобщено, как описано ниже, но данное ограничение поддерживается в январской (2019 г.) версии p4c.

Таблицы range

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

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

Если таблица range имеет записи, определенные через записи const таблицы property, относительный приоритет таких записей является высшим у первой и низшим у последней (в порядке их указания в программе P4.

Таблицы ternary

Если в таблице нет поля range, но имеется хотя бы одно поле ternary или optional, таблица реализуется в BMv2 как ternary. Для таблиц range одному ключу поиска может соответствовать множество записей, поэтому каждая запись должна иметь численный приоритет, назначенный программой уровня управления. К таблицам ternary применимы приведенные выше замечания относительног полей lpm и записей, заданных с помощью const.

Таблицы lpm

Если таблица не имеет полей range, ternary и optional, но имеет поле lpm, такое поле должно быть единственным. В таблице может присутствовать несколько необязательных полей exact. Хотя в таблице может быть несколько записей, соответствующих одному ключу, такая таблица не может иметь более одной подходящей записи для каждого возможного размера префикса в поле lpm (поскольку две такие записи не могут иметь один ключ поиска). Уровень управления не может устанавливать приоритет для записей в такой таблице, он определяется размером префикса.

Если в таблице lpm есть записи, определенные через const в таблице property, относительный приоритет записей определяется размером префикса, а не порядком указания в программе P4.

Таблицы exact

Если таблица имеет лишь поля exact, она реализуется в BMv2 как таблица exact. Каждому ключу может соответствовать лишь одна запись, поскольку дублирование ключей поиска не допускается. В результате значения приоритета не требуются. BMv2 (и многие другие реализации P4) использует хэш-таблицы для сопоставления записей.

Если таблица exact включает записи, определенные через const в таблице property, ключу может соответствовать лишь одна запись поэтому порядок указания const в программе P4 не имеет значения.

Задание критериев поиска с помощью записей const

В приведенной ниже таблице для каждого значения match_kind и ключевых полей таблиц P416 показан синтаксис, разрешенный при указании набора полей сопоставления для записи таблицы в списке записей const. Ограничения состоят в том, что во всех разрешенных случаях lo, hi, val и mask должны иметь дозволенные положительные значения, т. е. не выходить за пределы разрешенных для поля диапазонов. Все элементы могут быть арифметическими выражениями, преобразуемыми в константы в момент компиляции.

 

range

ternary

optional

lpm

exact

lo .. hi

да4

нет

нет

нет

нет

val &&& mask

нет

да5

нет

да6

нет

val

да7

да8

да

да5

да

_ или default

да9

да6

да6

да6

нет

 

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

header h1_t {
    bit<8> f1;
    bit<8> f2;
}

struct headers_t {
    h1_t h1;
}

// ... позднее ...

control ingress(inout headers_t hdr,
                inout metadata_t m,
                inout standard_metadata_t stdmeta)
{
    action a(bit<9> x) { stdmeta.egress_spec = x; }
    table t1 {
        key = { hdr.h1.f1 : range; }
        actions = { a; }
        const entries = {
             1 ..  8 : a(1);
             6 .. 12 : a(2);  // диапазоны в записях могут перекрываться
            15 .. 15 : a(3);
            17       : a(4);  // эквивалентно 17 .. 17
            // Правило «соответствия всему» в таблице не требуется, но разрешено
            // (за исключением точного совпадения) и в некоторых примерах оно есть.
            _        : a(5);
        }
    }
    table t2 {
        key = { hdr.h1.f1 : ternary; }
        actions = { a; }
        // Не требуется задавать критерии сопоставления ternary шестнадцатеричными
        // значениями. Просто иногда это удобней.
        const entries = {
            0x04 &&& 0xfc : a(1);
            0x40 &&& 0x72 : a(2);
            0x50 &&& 0xff : a(3);
            0xfe          : a(4);  // эквивалентно 0xfe &&& 0xff
            _             : a(5);
        }
    }
    table t3 {
        key = {
            hdr.h1.f1 : optional;
            hdr.h1.f2 : optional;
        }
        actions = { a; }
        const entries = {
            // Отметим, что при наличии в таблице нескольких ключей записи const
            // для выражений выбора ключа должны заключаться в круглые скобки.
            (47, 72) : a(1);
            ( _, 72) : a(2);
            ( _, 75) : a(3);
            (49,  _) : a(4);
            _        : a(5);
        }
    }
    table t4 {
        key = { hdr.h1.f1 : lpm; }
        actions = { a; }
        const entries = {
            0x04 &&& 0xfc : a(1);
            0x40 &&& 0xf8 : a(2);
            0x04 &&& 0xff : a(3);
            0xf9          : a(4);  // эквивалентно 0xf9 &&& 0xff
            _             : a(5);
        }
    }
    table t5 {
        key = { hdr.h1.f1 : exact; }
        actions = { a; }
        const entries = {
            0x04 : a(1);
            0x40 : a(2);
            0x05 : a(3);
            0xf9 : a(4);
        }
    }
    // ... остальной код ...
}

Ограничения для операций recirculate, resubmit и clone

Операции recirculate, resubmit и clone не сохраняют метаданные (т. е. имеют пустой список полей, которые следует сохранить) работают должным образом при использовании p4c и simple_switch с P414 или P416 + архитектура v1model.

К сожалению часть операций, пытающихся сохранить метаданные, не работает корректно и по-прежнему вызывают для пакетов recirculate, resubmit или clone, не сохраняя желаемые значения метаданных. Эта проблема подробно обсуждалась разработчиками p4c и рабочей группой P4 в результате чего был разработан ряд предложений.

  • В долгосрочной перспективе архитектура P416 PSA использует механизм указания сохраняемых полей метаданных, отличающийся от v1model, и должна работать корректно. По состоянию на октябрь 2019 г. реализация PSA не завершена, поэтому сегодня она не помогает создавать рабочий код.

  • Желающим внести изменения в p4c и/или simple_switch, решающие эту проблему, следует обращаться в рабочую группу P4 для координации действий.

    • Предпочтительной формой помощи является завершение реализации архитектуры PSA.

    • Другим вариантом является совершенствование реализации архитектуры v1model. Некоторые из подходов к решению этой задачи рассматриваются здесь.

Эта проблема затрагивает не только программы P416, использующие архитектуру v1model, но и программы P414, использующие компилятор p4c, поскольку он транслирует код P414 в код P416 перед использованием той части компилятора, с которой связана проблема.

Фундаментальная проблема заключается в том, что P414 имеет конструкцию field_list, которая оганичивает именованные ссылки на другие поля. Когда эти списки используются в P414 для операций recirculate, resubmit или clone, которые сохраняют метаданные, они указывают цель не только для чтения этих полей, но и для их записи (пакет после операции recirculate, resubmit или clone). Списки полей P416, использующие синтаксис {field_1, field_2, …}, ограничены доступом к текущим значениям полей во время выполнения оператора или выражения, но не представляют какие-либо ссылки, и в соответствии со спецификацией P416 значения полей не могут быть изменены в другой части программы.

Советы по определению корректности сохранения метаданных

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

Python-программа bmv2-json-check.py пытается определить, похож ли какой-либо список полей для сохранения метаданных при вызове recirculate, resubmit или clone operations на имя созданной компилятором временной переменной. Используемые программой методы очень просты и не дают гарантии корректности результата. Программа лишь автоматизирует описанные ниже проверки.

Каждая операция recirculate, resubmit и clone представлена данными JSON в файле BMv2 JSON. Отыскиваются приведенные ниже строки в двойных кавычках:

  • "recirculate" единственным параметром является идентификатор field_list;

  • "resubmit" единственным параметром является идентификатор field_list;

  • "clone_ingress_pkt_to_egress" вторым параметром является идентификатор field_list;

  • "clone_egress_pkt_to_egress"вторым параметром является идентификатор field_list.

Эти поля можно найти в каждом списке полей раздела файла BMv2 JSON с ключом "field_lists". Программа simple_switch будет сохранять значения полей с этими именами, независимо от имен. Основная проблема заключается в соответствии или несоответствии месту, используемому компилятором для представления полей, которые нужно сохранить. В некоторых случаях они совпадают (часто для имен полей в файле BMv2 JSON, которые похожи или совпадают с именами полей в исходном коде P4), а в иных случаях представляется другое местоположение (например, созданные компилятором временные переменные для хранения полей, которые нужно сохранить). Имена полей, начинающиеся с tmp., намекают на реализацию p4c октября 2019 г., но это деталь реализации p4c, которая может измениться.

Замечания по архитектуре P416 + v1model

Ниже приведено описание работы P416 с архитектурой v1model. В некоторых случаях описанные детали относятся к реализации архитектуры v1model в BMv2 simple_switch и это отмечено явно, поскольку поведение (ограничения) других реализаций могут отличаться.

Ограничения для типа H

Тип H является параметром определения пакета V1Switch в файле v1model.p4, показанного ниже.

package V1Switch<H, M>(Parser<H, M> p,
                       VerifyChecksum<H, M> vr,
                       Ingress<H, M> ig,
                       Egress<H, M> eg,
                       ComputeChecksum<H, M> ck,
                       Deparser<H> dep
                       );

Этот тип H может быть структурой, содержащей элементы одного из перечисленных типов (но не иные):

  • header;

  • header_union;

  • стек header.

Ограничения для кода анализатора

Спецификация языка P416 версии 1.1 не поддерживает условный оператор if внутри анализатора (parser). Поскольку компилятор p4c использует in-line вызовы функций в точках вызова, это ограничение распространяется на тела функций вызываемых из кода анализатора. Есть два способа обойти это ограничение:

  • если условное выполнение можно реализовать за счет ожидания в процессе входной обработки, можно применить оператор if в
    этом процессе
    ;

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

В архитектуре v1model пакет, достигший состояния reject в анализаторе (например, в результате запрета соединений), не отбрасывается автоматически. Для пакета начинается входная обработка (Ingress) со значением поля стандартных метаданных parser_error в соответствии с обнаруженной ошибкой. Код P4 может отбрасывать такие пакеты или выполнять иные действия (например, передать клон пакета управляющему CPU для анализа и записи события).

Комбинация p4c и simple_switch не поддерживает явного перехода в состояние reject в исходном коде. Это можно сделать лишь через отказ при проверке вызова.

Ограничения для кода VerifyChecksum

Элемент VerifyChecksum выполняется после завершения работы анализатора (Parser) и до начала входной обработки (Ingress).Комбинация p4c и simple_switch поддерживает вызовы внешней функции verify_checksum или verify_checksum_with_payload лишь внутри этих элементов (см. определение в файле v1model.p4). Первый аргумент этих функций является логическое значение (условие), которое может использоваться для условного расчета контрольной суммы.

В архитектуре v1model пакеты с некорректной контрольной суммой не отбрасываются автоматически. Для такого пакета начинается входная обработка (Ingress) со значением стандартного поля метаданных checksum_error = 1. Если в программе используется множество вызовов verify_checksum или verify_checksum_with_payload, нет возможности определить, какой из этих вызовов определил некорректную сумму. Код P4 может отбрасывать такие пакет, но это не делается автоматически.

Ограничения для кода элементов Ingress и Egress

Программа simple_switch не поддерживает использования одной таблицы в элементе Ingress или Egressболее одного раза. В некоторых случаях это ограничение можно обойти путем создания нескольких таблиц с похожими определениями и однократного применения каждой таблицы в процессе выполнения элемента Ingress или Egress. Если нужно создать две таблицы с одинаковыми записями и действиями, программы уровня управления должны сохранять содержимое этих таблиц одинаковым (например, всегда добавлять запись в T2 при добавлении в T1).

Это решение можно было бы обобщить в simple_switch, но следует понимать, что некоторые высокоскоростные реализации ASIC с P4 могут вносить такое же ограничение на аппаратном уровне.

Ограничения для кода действий

На самом деле эти ограничения вносит компилятор p4c, а не simple_switch. Для снятия этих ограничений p4c следует учесть указанные ниже проблемы.

Спецификация P416 версии v1.1.0 разрешает операторы if внутри объявления действий. При использовании p4c для компиляции BMv2 simple_switch поддерживаются некоторые типы операторов if, в частности, те, которые могут быть преобразованы в назначения с использованием оператора condition ? true_expr : false_expr. Будет работать действие

    action foo() {
        meta.b = meta.b + 5;
        if (hdr.ethernet.etherType == 7) {
            hdr.ethernet.dstAddr = 1;
        } else {
            hdr.ethernet.dstAddr = 2;
        }
    }

Но не будет работать (по состоянию на 1 июля 2019 г.)

        action foo() {
        meta.b = meta.b + 5;
        if (hdr.ethernet.etherType == 7) {
            hdr.ethernet.dstAddr = 1;
        } else {
            mark_to_drop(standard_metadata);
        }
    }

С учетом приведенной ниже выдержки из спецификации P416 очевидна возможность наличия реализаций P4, которые могут ограничивать и не поддерживать операторы if внутри действий.

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

Таким образом, программы P4 с операторами if в коде действий явно будут менее переносимыми. Как отмечено выше, расширение p4c позволило бы поддержать использование операторов if в коде действий.

Ограничения для кода ComputeChecksum

Элемент ComputeChecksum выполняется сразу по завершении элемента Egress, но до начала работы Deparser. Комбинация p4c и simple_switch поддерживает последовательность вызовов внешних функций update_checksum и update_checksum_with_payload лишь внутри таких элементов. Первым аргументом этих функций является логическое значение, которое может применяться для условного расчета контрольной суммы.

Ограничения для кода Deparser

Элемент Deparser может включать лишь последовательность вызовов метода emit объекта packet_out.

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

Реализация BMv2 register

Как p4c, так и simple_switch поддерживают массивы регистров (register) с произвольными значениями типов bit<W> или int<W>, но не других типов (например, тип struct был бы удобен в некоторых программах, но это не поддерживается).

В качестве примера обхода этого ограничения предположим, что нужна структура с полями x, y, z типов bit<8>, bit<3>, bit<6>. Этого можно избежать, создав массив register с элементами типа bit<17> (общий размер 3 полей) и используя операции «нарезки» (slicing) битов P416 для выделения полей из 17-битового значения после чтения массива регистров. Перед записью в массив можно использовать операции конкатенации векторов P416 для слияния 3 полей в 17-битовое значения.

    register< bit<17> >(512) my_register_array;
    bit<9> index;

    // ... другой код ...

    // Пример действия написан в предположении выполнения другого кода,
    // (не показан) для задания нужного значения переменной index.

    action update_fields() {
        bit<17> tmp;
        bit<8> x;
        bit<3> y;
        bit<6> z;

        my_register_array.read(tmp, (bit<32>) index);
        // используется нарезка битов для извлечения логически разделенных
        // частей 17-битового значения регистра.
        x = tmp[16:9];
        y = tmp[8:6];
        z = tmp[5:0];

        // Здесь вносятся все изменения в переменные x, y и z Это просто
        // пример кода, не выполняющий реальной обработки пакетов.
        if (y == 0) {
            x = x + 1;
            y = 7;
            z = z ^ hdr.ethernet.etherType[3:0];
        } else {
            // x не меняется
            y = y - 1;
            z = z << 1;
        }

        // Конкатенация измененных значений x, y, z в 17-битовое значение
        // для записи в регистр.
        tmp = x ++ y ++ z;
        my_register_array.write((bit<32>) index, tmp);
    }

Хотя p4c и simple_switch поддерживают битовый размер W, достаточный для обработки пакетов, Thrift API (используется в simple_switch_CLI и возможно в некоторых программах контроллеров) поддерживает для уровня управления чтение и запись лишь до 64 батов (см. тип BmRegisterValue в файле standard.thrift, который задавал 64-битовое целое число по состоянию на октябрь 2019 г.). P4Runtime API не имеет этого ограничения, но пока в P4Runtime нет реализации чтения и записи для simple_switch (p4lang/PI#376)

BMv2 v1model поддерживает параллельную работу, блокируя все объекты register, доступные из действия, для предотвращения конфликтов с другими операциями. Для этого не нужно использовать аннотацию @atomic в программах P416. BMv2 v1model (10.2019) игнорирует аннотации @atomic в программах P416. Даже при использовании таких аннотаций BMv2 не будет считать любой блок кода, превышающий один вызов действия, атомарной транзакцией.

Реализация BMv2 random

Реализация в BMv2 v1model функции random поддерживает в параметрах lo и hi значения рабочих (run-time) переменных, т. е. не требует известных при компиляции значений. Нет также требования, чтобы значение (hi — lo + 1) было степенью 2. Тип T огграничен bit<W> с W не больше64.

Реализация BMv2 hash

Реализация в BMv2 v1model функции hash поддерживает в параметрах base и max значения рабочих (run-time) переменных, т. е. не требует известных при компиляции значений. Нет также требования, чтобы значение max было степенью 2.

Вызов hash возвращает значение, рассчитанное для данных H. Значением, записываемым в выходной параметр result будет (base + (H % max)), если max ≥1 и base в противном случае. Тип O для result, T для base и M для max ограничены bit<W> с W не больше 64.

Реализация BMv2 direct_counter

Если таблица t имеет объект direct_counter c, связанный с ней, включая в свое определение свойство counters = c, реализация BMv2 v1model ведет себя так, будто каждое действие для этой таблицы содержит ровно 1 вызов c.count(), независимо от их реального числа.

Реализация BMv2 direct_meter

Если таблица t имеет объект direct_meter m, связанный с ней, включая в свое определение свойство meters = m, хотя бы одно из действий этой таблицы должно включать вызов m.read(result_field); для некоторого поля result_field типа bit<W> с W ≥2. Когда это делается, реализация BMv2 v1model ведет себя так, будто все действия этой таблицы имеют такой вызов, независимо от его реального наличия.

Компилятор p4c выдает сообщение об ошибке (и не поддерживает) наличие для таблицы t двух действий, одно из которых имеет m.read(result_field1), а другое — m.read(result_field2) или оба вызова происходят в одном действии. Все вызовы метода read() для m должны иметь один параметр result, куда записывается результат.

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

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

nmalykh@protocols.ru

1Network Interface Card. Прим. перев.

2Portable Switch Architecture.

3Принятое по умолчанию значение 511 для simple_switch может быть изменено опцией командной строки --drop-port в зависимости от платформы.

4Должно выполняться условие lo
hi
. При поиске ключ k будет соответствовать, если выполняется условие lo k hi.

5Должно выполняться условие val == (val & mask). Биты маски со значением 1 задают совпадение, а биты 0 не имеют значения (не проверяются. При поиске ключ k будет соответствовать, если (k & mask) == (val & mask).

6Должно выполняться условие val == (val & mask) и маска должна быть «префиксной», т. е. иметь непрерывную последовательность 1 в старших битах. При попытке задать префикс как val/prefix_length в программе P416 (синтаксис, применяемый некоторыми командами линейных интерфейсов для задания префикса, например, в simple_switch_CLI), это будет арифметическим выражением для деления val на prefix_length и приведет к отказу в случае val для поиска совпадения. Компилятор не будет выдавать предупреждений, поскольку используется корректный синтаксис операции деления.

7Эквивалент диапазона val .. val и ведет себя как поиск сопадения для val.

8Эквивалент val &&& mask с 1 во всех позициях маски и ведет себя как поиск сопадения для val.

9Соответствует любому разрешенному значению поля. Эквивалент min_posible_field_value .. max_possible_field_value для поля range или 0 &&& 0 для полей ternary и lpm.




Измерение пропускной способности

NTK_RFC 0002

Bandwidth measurement

Измерение пропускной способности

PDF

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

Проблема измерения качества каналов

В текущей версии Npv7 радар (Radar) измеряет качество канала, используя лишь время кругового обхода rtt1 и потери пакетов. Это явно не оптимально, поскольку пропускная способность не учитывается и канал с малой пропускной способностью (например, 20 Кбит/с), но с небольшой задержкой окажется лучше широкополосного канала с умеренной задержкой.

Улучшение

Узел должен включать в пакеты трассировки (Tracer Packet) не только rtt пройденных каналов, но и текущую их пропускную способность (полосу). Это позволит формировать трафик с учетом реальной пропускной способности каналов.

Измерение пропускной способности

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

Общая доступная полоса

        A <--> B <--> C

Узел B «ловит» трафик между узлами A и C. В конце ловушки B измеряет общую доступную полосу каналов B—>C и B—>A. Имеются разные методы измерения пропускной способности каналов. Первый и простейший заключается в передаче неопределенного числа случайных пакетов в течение нескольких секунд по адресу получателя на канале. Скорость передачи контролируется с помощью libpcap и регистрируется максимальное число переданных в секунду байтов как доступнеая для выгрузки (upload) полоса данного канала. Этот метод очень эффективен и измеренная полоса является реальной, а не аппроксимированной. Побочным эффектом является полная загрузка канала на несколько секунд.

Другой вариант более изыскан и использует методы Packet Pair и Packet Train, описанные в http://perform.wpi.edu/downloads/wbest/README и http://www-static.cc.gatech.edu/fac/Constantinos.Dovrolis/bw.html.

Поскольку каналы могут быть асимметричными, измерения повторяются также для A—>B и C—>B. В результате будет получена пропускная способность каналов A->B, B->A, C->B, B->C.

Контроль полосы в реальном масштабе времени

С помощью библиотеки libpcap узел B может отслеживать использование полосы каналов.

Max_link_bw

Общая доступная пропускная способность канала.

nflows

Текущее число потоков в канале. Потоком считается множество (stream) пакетов, связанных с конкретным соединением.

Текущую доступную полосу канала можно аппроксимировать выражением

link_avail_bw   = Max_link_bw/(nflows+1)

Такая аппроксимация выбрана потому, что метод управления трафиком TCP похож на алгоритм max-min и при большом числе потоков link_avail_bw является хорошим приближением.

Если радар сообщает о значительных вариациях текущей доступной полосы, передается новый запрос QSPN.

Задержка rtt

Каждый узел сети будет задерживать пересылку полученного пакета Tracer (TP) на время, обратно пропорциональное link_avail_bw. Таким образом, пакеты TP будут приниматься для эффективности. Побочным эффектом этого правила является игнорирование крайних случаев, когда маршруты с очень низким значением rtt будут иметь очень малую полосу bw или маршруты с оптимальной полосой bw будут иметь обчень большое значение rtt. Однако в реальном мире такие ситуации достаточно редки, поскольку rtt и the зачастую связаны между собой.

Дополнительная информация об эффективности пакетов TP приведена в документе QSPN v2.

Пропускная способность маршрута

Пропускная способность маршрута из S в D обозначается bw(S -> D) и равна пропускной способности наихудшего канала в пути. Например, для маршрута

S --64Mb/s--> R --64Mb/s--> T --32Mb/s--> O --100Mb/s--> I --100Mb/s--> D

пропускная способность составит bw(S -> D) = 32 Мбит/с.

Пакет TP должен запомнить единственное значение пропускной способности (_one_ bw) и это будет bw() текущего маршрута. Например, если S передает TP, то по получении этого пакета узлом T, сохраненная в нем пропускная способность будет bw(S->R->T)=64, но при достижении узла O, она сменится на bw(S→R→T→O)=32.

Отметим, что каждое значение bw приблизительно соответствует доступной полосе соответствующего канала (link_avail_bw). Например, запись S —64Mb/s—> R показывает, что текущая пропускная способность канала S—>R составляет приблизительно 64 Мбит/с.

Асимметричные маршруты

QSPN v1 предоставляет каждому узлу наилучший маршрут загрузки трафика (download) с каждого другого узла. Рассмотрим в качестве примера узлы S и D.

       1:   ,--<-<-<---.
           /            \
         S                D
           \            / 
       2:   `-->->->---'

Маршруты типа 1 являются лучшими маршрутами выгрузки (upload) из D в S, а маршруты типа 2 — лучшими для противоположного направления. QSPN дает S только маршруты типа 1, а D знает только маршруты типа 2. Если маршруты не симметричны, S при выгрузке в D будет использовать маршрут типа 1, который может иметь низкую производительность.

Решение очень просто — S при выгрузке большого блока данных будет запрашивать у D его маршруты D->S (тип 2), т. е. лучшие маршруты выгрузки из S в D.

Демон Netsukuku, используя libpcap, будет отслеживать пакеты, исходящие от localhost. Если пакеты отправлялись более 16 секунд, демон будет запрашивать у целевого узла лучшие маршруты выгрузки (upload) и добавлять их в свою таблицу маршрутизации. Таким образом, маршруты выгрузки будут запрашиваться лишь при необходимости.

Отметим, что в QSPN v2 имеется встроенная поддержка асимметричной маршрутизации.

Задержка и полоса

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

Узлам Netsukuku следует поддерживать три типа таблиц маршрутизации:

  • маршруты с наилучшей пропускной способностью;

  • маршруты с наименьшей задержкой;

  • маршруты с эффективной комбинацией пропускной способности и задержки.

Если протокол приложения использует значения TOS в своих пакетах IP, можно добавить правила маршрутизации и выбрать для протокола подходящую таблицу (например, вторую для ssh).

Возможен вариант хранения в ядре лишь усредненной (третьей) таблицы, поскольку она применяется наиболее часто. Конкретные маршруты с наилучшей пропускной способностью и задержкой можно добавлять в ядро лишь в момент их использования. Например, при запуске bittorrent для загрузки с узлов A,B,C монитор ntkd будет добавлять в ядро маршруты с наилучшей пропускной способностью для A,B,C.

IGS

Шлюз inet-gw, позволяющий совместно использовать свое соединение с Internet, замеряет свою доступную полосу Internet-соединения. Максимальная пропускная способность в обоих направлениях известна, поскольку пользователь должен задать ее в конфигурационном файле netsukuku.conf. Таким образом, отслеживание устройства, используемого принятым по умолчанию маршрутом в Internet, позволяет легко узнать доступную полосу.

Балансировка нагрузки

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

Балансировка нагрузки внутри Netsukuku не зависит от проблем балансировки на IGS. Узлы ntk согласованы между собой и не используют NAT для взаимодействия внутри сети.


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

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

nmalykh@protocols.ru

1Round-trip time.




Библиотека 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Американские деревья растут корнем вверх. Прим. перев.




SiFive-OE-poPingUI-P4

PDF

Для экспериментов с применением языка P4 (p4.org) в сетевых устройствах была предпринята попытка сборки прототипа компилятора P4C на платформе HiFive Unleashed U540 компании SiFive. В качестве среды разработки использовалась система OpenEmbedded (www.yoctoproject.org) и базовый репозиторий SiFive (github.com/sifive/meta-sifive/tree/master). Для работы также требуется пакет repo, установка которого описана по ссылке.

Для сборки образов потребуется достаточно большое пространство на диске (после сборки образа на диске было занято 94 Гбайт), а сам диск должен быть быстрым (SSD или SAS).

  1. Создаем пустой каталог и переходим в него

    mkdir sifive-master
    cd sifive-master

    Далее в тексте этот каталог будет именоваться корневым и все ссылки на каталоги и файлы будут отсчитываться от него.

  2. Создаем и заполняем репозиторий

    $ repo init -u git://github.com/sifive/meta-sifive -b master -m tools/manifests/sifive.xml
    $ repo sync
  3. Создаем уровень meta-poPingUI

    $ bitbake-layers create-layer meta-poPingUI
    NOTE: Starting bitbake server... 
    Add your new layer with 'bitbake-layers add-layer meta-poPingUI'
    $ bitbake-layers add-layer meta-poPingUI
    NOTE: Starting bitbake server... 
    Unable to find bblayers.conf
  4. Копируем файл установки окружения из каталога meta-sifive

    $ cp meta-sifive/setup.sh meta-poPingUI/setup.sh
  5. Редактируем созданную копию, добавляя строку

    $ bitbake-layers add-layer ../meta-poPingUI
  6. Из строки DISTRO_FEATURES_append = » largefile opengl ptest multiarch pam systemd vulkan » удаляем opengl и vulkan и получаем в результате

    DISTRO_FEATURES_append = " largefile ptest multiarch pam systemd "
  7. В начале файла меняем имя создаваемого образа, как показано ниже

    BITBAKEIMAGE="coreip-cli"
  8. В конце файла помещаем символ комментария в показанные ниже строки

    # Add r600 drivers for AMD GPU 
    #PACKAGECONFIG_append_pn-mesa = " r600" 
    
    # Add support for modern AMD GPU (e.g. RX550 / POLARIS) 
    #PACKAGECONFIG_append_pn-mesa = " radeonsi" 
    #PACKAGECONFIG_append_pn-mesa = " gallium-llvm"
  9. Копируем каталог meta-sifive/conf в meta-poPingUI/conf

  10. Редактируем файл meta-poPingUI/conf/layer.conf, заменяя sifive на poPingUI, а также устанавливаем для уровня высокий приоритет, чтобы при совпадении имен задания выбирались из нашего уровня

    BBFILE_PRIORITY_meta-poPingUI = "9"
  11. Копируем каталог meta-sifive/recipes-sifive/images в meta-poPingUI/recipes-poPingUI/images

    Поскольку планируется работа лишь с платой HiFive без модулей расширения удаляем файлы с поддержкой графического интерфейса (demo-coreip-xfce4.bb и demo-coreip-xfce4-debug.bb), а файлы demo-coreip-cli.bb и demo-coreip-cli-debug.bb переименовываем в coreip-cli.bb и coreip-cli-debug.bb. Это позволит избежать путаницы и при необходимости воспользоваться образами уровня meta-sifive.

  12. Переходим в корневой каталог репозитория и вводим команду

    $ . ./meta-poPingUI/setup.sh
    Init OE 
    You had no conf/local.conf file. This configuration file has therefore been 
    created for you with some default values. You may wish to edit it to, for 
    example, select a different MACHINE (target hardware). See conf/local.conf 
    for more information as common configuration options are commented. 
    
    You had no conf/bblayers.conf file. This configuration file has therefore been 
    created for you with some default values. To add additional metadata layers 
    into your configuration please add entries to conf/bblayers.conf. 
    
    The Yocto Project has extensive documentation about OE including a reference 
    manual which can be found at: 
       http://yoctoproject.org/documentation 
    
    For more information about OpenEmbedded see their website: 
       http://www.openembedded.org/ 
    
    
    ### Shell environment set up for builds. ### 
    
    You can now run 'bitbake <target>' 
    
    Common targets are: 
       core-image-minimal 
       core-image-sato 
       meta-toolchain 
       meta-ide-support 
    
    You can also run generated qemu images with a command like 'runqemu qemux86'. 
    
    Other commonly useful commands are: 
    - 'devtool' and 'recipetool' handle common recipe tasks 
    - 'bitbake-layers' handles common layer tasks 
    - 'oe-pkgdata-util' handles common target package tasks 
    Adding layers 
    NOTE: Starting bitbake server... 
    NOTE: Starting bitbake server... 
    NOTE: Starting bitbake server... 
    NOTE: Starting bitbake server... 
    NOTE: Starting bitbake server... 
    NOTE: Starting bitbake server... 
    NOTE: Starting bitbake server... 
    NOTE: Starting bitbake server... 
    NOTE: Starting bitbake server... 
    Creating auto.conf 
    --------------------------------------------------- 
    MACHINE=freedom-u540 bitbake coreip-cli 
    --------------------------------------------------- 
    
    Buildable machine info 
    --------------------------------------------------- 
    * freedom-u540: The SiFive HiFive Unleashed board 
    * qemuriscv64: The 64-bit RISC-V machine 
    --------------------------------------------------- 
    
  13. Запускаем сборку образа командой

    $ MACHINE=freedom-u540 bitbake coreip-cli
    Parsing recipes: 100% |#############################################################################################################################################################################| Time: 0:00:18 
    Parsing of 2346 .bb files complete (0 cached, 2346 parsed). 3445 targets, 174 skipped, 0 masked, 0 errors. 
    NOTE: Resolving any missing task queue dependencies 
    
    Build Configuration: 
    BB_VERSION           = "1.46.0" 
    BUILD_SYS            = "x86_64-linux" 
    NATIVELSBSTRING      = "mageia-7" 
    TARGET_SYS           = "riscv64-oe-linux" 
    MACHINE              = "freedom-u540" 
    DISTRO               = "nodistro" 
    DISTRO_VERSION       = "nodistro.0" 
    TUNE_FEATURES        = "riscv64" 
    meta                 = "HEAD:57ccf1e3bb320bd28a2d106c98f4706434c3075a" 
    meta-oe               
    meta-python           
    meta-multimedia       
    meta-networking       
    meta-gnome            
    meta-xfce            = "HEAD:920161113533074d27dc93c521815380fdf20275" 
    meta-riscv           = "HEAD:8bd3402c76f897189842f65e521f1388777660ca" 
    meta-sifive          = "HEAD:4c97a625e70558fbca9dc210616b13115e22dbee" 
    meta-poPingUI        = "<unknown>:<unknown>"
    
    
  14. Процесс загрузки исходных кодов1 и сборки компонент достаточно долог и можно заняться другими делами. В моей системе Mageia 7.1 процесс завершается ошибкой

    virtual:native:/OE/sifive-master/openembedded-core/meta/recipes-devtools/perl/libxml-parser-perl_2.46.bb:do_configure

    Для решения этой проблемы создаем в каталоге уровня файл meta-poPingUI/recipes-devtools/libxml-parser-perl/libxml-parser-perl_2.46.bbappend, показанный ниже

    do_configure_prepend_class-native () { 
       cd ${S} 
       ${HOSTTOOLS_DIR}/perl Makefile.PL 
       cd - 
    }
  15. Проблема с networkmanager решается командой LC_ALL=C ../recipe-sysroot-native/usr/bin/intltool-merge -x -u -c ./po/.intltool-merge-cache ../NetworkManager-1.22.10/po data/org.freedesktop.NetworkManager.policy.in data/org.freedesktop.NetworkManager.policy из каталога build/tmp-glibc/work/riscv64-oe-linux/networkmanager/1.22.10-r0/build и создания символьной ссылки /usr/bin/nativeperl на локальный перл хоста2

  16. На этом первичные правки завершаются и образ собирается нормально. Можно начинать внесение своих правок.

  17. Сначала добавим Judy, поскольку от этого пакета зависит p4c и связанные пакеты.

    $ devtool add https://github.com/multiSnow/judy.git
    $ bitbake judy

    Процесс завершается ошибкой /lib/ld-linux-riscv64-lp64d.so.1: No such file or directory. Это связано с попыткой запуска двоичного файла генерации таблиц, собранного для RISCV, из среды сборки x86. Найти способ обхода этой проблемы мне не удалось, поэтому были просто взяты файлы, созданные на платформе HiFive Unleashed, и помещены в каталоги исходного кода judy. При этом запуск программы генерации (JudyLTablesGen и Judy1TablesGen) из Makefile был удален путем простого редактирования.

    Копируем файл JudyLTables.c в каталог build/tmp-glibc/work/riscv64-oe-linux/judy/1.0.5+git999-r0/judy-1.0.5+git999/src/JudyL и удаляем конец строки 7953 ./JudyLTablesGen. Затем повторяем команду bitbake judy и выполняем аналогичные процедуры в каталоге Judy1 с файлом Judy1Tables.c. Следующий запуск команды bitbake judy обеспечивает сборку пакета без ошибок.

  18. Добавляем созданное задание на уровень meta-poPingUI командой

    $ devtool finish -f judy meta-poPingUI/recipes-devtools

    из корневого каталога системы сборки. В результате готовое задание помещается на нужный уровень в каталог recipes-devtools. После этого следует повторить сборку задания, поскольку при переносе внесенные изменения теряются (см. 14). Операции выполняются с файлами в каталоге build/tmp-glibc/work/riscv64-oe-linux/judy/1.0.5+gitAUTOINC+a5971f3ee4-r0/build/src.

  19. Следующим добавляем пакет PI

    $ devtool add https://github.com/p4lang/PI.git

    В файле задания pi_git.bb меняем строку DEPENDS, как показано ниже

    DEPENDS = "readline judy nanomsg protobuf protobuf-c"
    

    И добавляем опции настройки

    EXTRA_OECONF = " --with-fe-cpp --with-proto=Protobuf --with-internal-rpc --with-cli "

    Между пакетами PI и bmv2 имеются циклические зависимости, поэтому PI придется собрать дважды без поддержки bmv2 (без опции —with-bmv2). Включаем задание на уровень meta-poPingUI командами из корневого каталога

    $ mkdir meta-poPingUI/recipes-p4
    $ devtool finish pi meta-poPingUI/recipes-p4
    $ bitbake pi
    
  20. Затем добавляем пакет bmv2 (behavioral model version 2), содержащий прототип коммутатора P4.

    $ devtool add https://github.com/p4lang/behavioral-model.git

    Система сборки создает для него задание с именем bm. Редактируем в файле задания bm_git.bb приведенные ниже строки

    DEPENDS = "gmp judy nanomsg libpcap pi boost"
    EXTRA_OECONF = " --with-nanomsg --with-pi --enable-modules --disable-dependency-tracking --without-thrift "
    

    Затем переносим задание на уровень meta-poPingUI командой из корневого каталога

    $ devtool finish bm meta-poPingUI/recipes-p4
  21. Начинаем сборку компилятора P4C

    $ devtool add https://github.com/p4lang/p4c.git

    Файл задания корректируем как показано ниже

    DEPENDS = "flex-native bison-native boost protobuf protobuf-native protobuf-c protobuf-c-native doxygen bm bdwgc gmp judy" 
    EXTRA_OECMAKE = "-DENABLE_GC=OFF -DENABLE_EBPF=OFF -DENABLE_PROTOBUF_STATIC=OFF "

    Сборка завершается ошибкой, связанной с запуском исполняемого файла RISCV (tools/irgenerator) в среде сборки x86. Для решения проблемы помещаем символ комментария в начало строки с вызовом команды irgenerator (строка 3194) в файле build.ninja каталога build/workspace/sources/p4c/oe-workdir/p4c-1.0+git999. Затем нужно скопировать в каталог build/workspace/sources/p4c/oe-workdir/p4c-1.0+git999/ir заранее подготовленные на целевой платформе файлы, перечисленные ниже

    gen-tree-macro.h 
    gen-tree-macro.h.fixup 
    gen-tree-macro.h.tmp 
    ir-generated.cpp 
    ir-generated.cpp.fixup 
    ir-generated.cpp.tmp 
    ir-generated.h 
    ir-generated.h.fixup 
    ir-generated.h.tmp 
    libir.a

    Копируем задание на уровень meta-poPingUI командой из корневого каталога

    $ devtool finish bm meta-poPingUI/recipes-p4

    После чего повторяем сборку и после получения ошибки внесим описанные выше правки в каталоге build/tmp-glibc/work/riscv64-oe-linux/p4c/1.0+gitAUTOINC+f79af56ea9-r0/build и еще раз собираем пакет командой

    $ bitbake p4c
  22. Сборка завершается без ошибок и можно внести задание в образ, редактируя файл meta-poPingUI/recipes-poPingUI/images/coreip-cli.bb. Для этого добавляем строку в конце переменной IMAGE_INSTALL, как показано ниже

       p4c \ 
       ${CORE_IMAGE_EXTRA_INSTALL} \ 
       " 
    
    IMAGE_INSTALL_append_freedom-u540 = "\ 
       unleashed-udev-rules \ 
       "
  23. Далее создаем образ командой

    $ MACHINE=freedom-u540 bitbake coreip-cli

    и по завершении его создания переносим на SD-карту командой

    $ zcat build/tmp-glibc/deploy/images/freedom-u540/coreip-cli-freedom-u540.wic.gz | sudo dd of=/dev/sdX bs=512K iflag=fullblock oflag=direct conv=fsync status=progress

    где sdX — имя устройства (SD-карта).

  24. По завершении записи можно отмонтировать SD-карту и перенести ее на плату HiFive Unleased. Для входа в систему служит имя пользователя root с паролем sifive.

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

Работа выполнена в рамках проекта «Орион».


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

nmalykh@protocols.ru


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

2Попытка выполнить команду из файла дополнения дает ошибку «You must have XML::Parser installed to run ../recipe-sysroot-native/usr/bin/intltool-merge». Добавление зависимостей проблему не решает.

3Номер строки может отличаться, поэтому лучше воспользоваться контекстным поиском в файле.

4Можно найти строку по контексту Generating IR class files. Искомая строка будет предыдущей.




SNSD

NTK_RFC 0009

Scattered Name Service Disgregation

Распределенная служба имен

PDF

В этом документе описана распределенная служба имен (Scattered Name Service Disgregation) — расширение протокола ANDNA. Текст будет включен в окончательную документацию, а сейчас в него можно вносить правки, связавшись с разработчиками.

SNSD


Распределенная служба имен SNSD является эквивалентом ANDNA для записи SRV Record в Internet DNS1, определенной в [1] и кратко описанной в [2].

SNSD отличается от SRV Record и имеет свои уникальные свойства.

С помощью SNSD можно связать адреса IP и имена хостов с другим hostname.

Каждая назначенная запись имеет номер службы (service number), что позволяет группировать адреса IP и hostname с одинаковым номером в массив. При запросе распознавания (resolution request) клиент будет указывать номер, поэтому он получит запись для указанного номера, связанного с hostname.

Например, узел X имеет зарегистрированное имя хоста angelica и по умолчанию для этого имени выделен IP-адрес 1.2.3.4. X связывает имя хоста depausceve со службой http (номер 80) для имени хоста angelica, а также адрес 11.22.33.44 со службой ftp (номер 21) хоста angelica.

Когда Y обычным путем распознает адрес angelica, он получает 1.2.3.4, но при распознавании адреса из web-браузера он будет запрашивать запись, связанную со службой http, и запрос будет возвращать depausceve. Браузер будет распознавать адрес по имени depausceve и получит доступ к серверу. Когда клиент ftp хоста Y будет пытаться распознать адрес angelica, он получит 11.22.33.44. Если Y попытается распознать адрес для не связанной службы, он получит основной адрес хоста 1.2.3.4.

Узел, связанный с записью SNSD, называется узлом SNSD (SNSD node). В приведенном примере такими узлами являются depausceve и 11.22.33.44.

Узел, который регистрирует записи и сохраняет регистрацию основного имени хоста, всегда называют регистрирующим узлом (register node), но может также использоваться термин Zero SNSD node — фактически это соответствует наиболее общей записи SNSD для службы с номером 0.

Отметим, что SNSD полностью отменяет NTK_RFC 0004 [3].

Служба, приоритет, вес

Номер службы

Номер службы указывает область действия записи SNSD. Адрес IP, связанный со службой номер x, будет возвращаться только в ответ на запросы распознавания, содержащие этот номер. Номер службы — это номер порта, с которым связана соответствующая служба. Номера портов можно узнать из файла /etc/services. Служба с номером 0 соответствует обычной записи ANDNA и в ответ на базовый запрос распознавания будет возвращаться соответствующий адрес IP.

Приритет

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

Вес

Значение веса, связанное с записью SNSD, служит для выбора среди нескольких записей с одинаковым приоритетом. Клиент запрашивает у ANDNA распознавание и получает, например, 8 разных записей. Первая запись, используемая клиентом, выбирается псевдослучайным способом. Каждая запись может быть выбрана с вероятностью, пропорциональной ее весу. Отметим, что в случае одинакового приоритета у всех записей выбор становится полностью случайным.

Для запрета использования записи можно задать нулевой вес. Значения веса должны быть меньше 128.

Регистрация SNSD

Метод регистрации записи SNSD похож на описанный в [3]. С одной службой можно связать до 16 записей. Максимальное число зарегистрированных записей составляет 256.

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

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

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

 * Изменение файла /etc/netsukuku/snsd_nodes.
{{{
register_node# cd /etc/netsukuku/ 
register_node# cat snsd_nodes
#
# Файл узлов SNSD
#
# В формате
# hostname:snsd_hostname:service:priority:weight[:pub_key_file]
# или
# hostname:snsd_ip:service:priority:weight[:pub_key_file]
#
# Параметр pub_key_file является необязательным. При его наличии NetsukukuD будет
# периодически проверять snsd_hostname и контролировать принадлежность имени к
# одной машине. При смене машины соответствующая запись snsd будет удаляться.
#

depausceve:pippo:http:1
depausceve:1.2.3.4:21:0

angelica:frenzu:ssh:1:/etc/netsukuku/snsd/frenzu.pubk

register_node#
register_node# scp frenzu:/usr/share/andna_lcl_keyring snsd/frenzu.pubk
}}}
 * Передача сигнала SIGHUP демону NetsukukuD на регистрирующем узле.
{{{
register_node# killall -HUP ntkd
# или 
register_node# rc.ntk reload
}}}

Нулевое значение SNSD IP

Основной адрес IP, связанный с обычным hostname, имеет по умолчанию приведенные ниже значения.

{{{
IP       = register_node IP     # Это значение нельзя изменить
service  = 0
priority = 16
weight   = 1
}}}

Можно связать другие записи SNSD со службой 0, но не разрешается менять основной адрес IP, в качестве которого может служить только IP-адрес узла register_node. Хотя нет возможности установить другую привязку для основного адреса IP, его можно «отключить», установив вес 0.

Строка, применяемая для смены значений веса и приоритета основного IP, имеет вид

{{{
hostname:hostname:0:priority:weight

# Например,
register_node# echo depausceve:depausceve:0:23:12 >> /etc/netsukuku/snsd_nodes
}}}

Цепочка SNSD

Поскольку для нулевой записи можно задать разные псевдонимы и резервные адреса IP, можно создавать цепочки SNSD. Например,

{{{
depausceve registers: depausceve:80 --> pippo
pippo registers:      pippo:0  --> frenzu
frenzu registers:     frenzu:0 --> angelica
}}}

Однако цепочки SNSD игнорируются и пригодным считается лишь первое преобразование. Поскольку для службы 0 всегда имеется основной адрес IP, распознавание выполняется всегда. В приведенном случае (depausceve:80 —> pippo:0) распознавание будет возвращать основной IP-адрес pippo:0.

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


[1] http://www.ietf.org/rfc/rfc2782.txt

[2] http://en.wikipedia.org/wiki/SRV_record

[3] Mail Exchange request, http://netsukuku.freaknet.org/main_doc/ntk_rfc/Ntk_MX_request

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

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

nmalykh@protocols.ru

1Domain Name System — служба доменных имен.




Протокол ANDNS

PDF

0. Введение

В этом документе описан протокол, применяемый для коммуникаций с ANDNA. Протокол используется для запросов в сфере internet. Например, можно запросить google.it в internet или depausceve в сети netsukuku.

В случае запросов internet элемент dns_wrapper будет взаимодействовать с серверами dns, заданными в файле /etc/resolv.conf, когда модуль ntkd загружен.

1. Обозначения

Далее на рисунках байты представляются в виде

         1  2  3  4  5  6  7  8
        +--+--+--+--+--+--+--+--+
        |                       |
        +--+--+--+--+--+--+--+--+

Числа указывают номера битов. Двухбайтовое слово представляется в форме

         1  2  3  4  5  6  7  8  1  2  3  4  5  6  7  8
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                       |                       |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

2. Заголовки

Заголовки имеют размер 4 байта и показанный на рисунке формат

        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                      ID                    | R|
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |QR| P| Z| QT  |  ANCOUNT  |I |   NK|   RCODE   |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

ID

Двухбайтовый идентификатор запроса. Значение ID выбирается случайным образом и в ответах должно применяться то же значение ID.

R

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

QR

0 для вопросов, 1 для ответов.

P

Если запрос является h2ip и связан с ntk, P задает протокол: 0 для TCP, 1 для UDP и 0 в остальных случаях.

Z

Сжатие zlib. При z=1 содержимое пакета (кроме заголовков) сжимается с помощью zlib (см. 8. Сжатие).

QT

Тип запроса (см. 3. Типы запросов). В откликах это поле должно сохраняться неизменным.

ANCOUNT

Счетчик ответов. Поле устанавливается только при QR=1 (пакет содержит ответы) и указывает число ответов в этом пакете.

I

Бит версии IP, использованной для содержимого пакета. Все адреса в пакете являются IPv4 (4 байта), если I=0 и IPv6 (16 байтов), если I=1. Этот бит полезен лишь в вопросах. Сервер будет возвращать ответ NO SUCH DOMAIN (нет такого домена), если на его узле применяется иная версия протокола IP. При совпадении версий в ответе будет использоваться та же версия протокола.

NK

Биты Netsukuku, позволяющий задать область запроса (query realm). При NK=1 областью запроса является netsukuku, при NK=2 — internet. Значение NK=0 указывает, что пакет не кодируется данным протоколом и содержит обычный протокол DNS (см. 4. Область запроса). В ответах это поле должно сохраняться.

RCODE

Результат запроса. Для пакетов с вопросами устанавливается RCODE = 0. В случае ошибок устанавливается ANCOUNT = 0.

3. Типы запросов

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

QTYPE = 0

Это классическое преобразование hostname -> ip (gethostbyname). Этот тип запросов применяется также для распознавания SNSD [1]. Можно указать сервис и общая форма представления такого запроса имеет вид

                hostname:service -> ip

Если сервис не указан, будет применяться 0-service.

Например, если нужно найти адрес хостинга сервиса http хоста depausceve, запрос может иметь вид

                depausceve:80

Формирование запросов описано в 6. Вопросы.

QTYPE = 1

Обратное преобразование ip -> host.

QTYPE =2

Глобальный запрос для всех служб указанного хоста. Областью запроса является Ntk.

4. Область запроса

Запрос можно сформулировать для поиска того или иного объекта в сети netsukuku или internet. При использовании протокола ANDNS область запроса указывается битами NK (см. 2. Заголовки).

Если используется протокол DNS, нужно формулировать запрос с неким суффиксом. Если запрос сделан для google.it.int (или google.it.INT), он будет относиться к internet. Запрос google.it.ntk (или google.it.NTK) будет относиться к сети netsukuku. Если суффикс не задан, по умолчанию областью запроса служит Netsukuku

Элемент dns_wrapper сначала определяет суффикс для корректного выбора области запроса. Найденный суффикс удаляется и запрос выполняется в соответствующей области.

5. RCODE

Это поле содержит код результата выполнения запроса. В пакетах с вопросом поле всегда имеет значение 0. Возможные коды в ответах перечислены ниже.

RCODE = 0 No Error

Пакет содержит ответы (ANSWERS), число которых указывается полем ANCOUNT (см. 2. Заголовки).

RCODE = 1 Interpretation Error

Сервер не понял запроса (запрос сформирован некорректно).

RCODE = 2 Server Fail

Сервер столкнулся с ошибкой при обработке корректного запроса.

RCODE = 3 No Such Domain

Искомого объекта не существует.

RCODE = 4 Not Implemented

Данный тип запросов не реализован на этом сервере.

RCODE = 5 Refused

Сервер отказывается взаимодействовать с вами.

Отметим, что выражение (RCODE XOR ANCOUNT) всегда истинно. Если RCODE содержит ту или иную ошибку (RCODE!=0), в пакете не будет ответа. Если же RCODE = 0 (нет ошибок), пакет содержит тот или иной ответ.

6. Вопросы

Формат вопроса зависит от QTYPE.

Case QTYPE = 0 (h2ip) и Realm=NTK

        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                    SERVICE                    |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                                               |       
        |                                               |       
        |                                               |
        |                   HOSTNAME                    |
        |                     HASH                      |
        |                     (HH)                      |
        |                                               |
        |                                               |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

SERVICE — 2-байтовое поле, представляющее значение сервиса SNSD [1].

HH — 16-байтовое хэш-значение имени хоста (hostname).

QTYPE = 0 (h2ip) и Realm=INET

        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                   SERVICE                     |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                   RDLENGTH                    |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                                               |
        \                                               \
        \                    RDATA                      \
        |                                               |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

SERVICE — 2-байтовое поле, представляющее значение сервиса SNSD [1]. В данный момент для преобразований INET сервис ограничен значением 25 (предполагается TCP) или 0.

RDLENGTH — размер RDATA.

RDATA — строка имени хоста с учетом strlen(RDATA)=RDLENGTH.

QTYPE = 1 (ip2h)

        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                                               |
        /                     RDATA                     /
        /                                               /
        |                                               |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

RDATA — адрес IP в двоичном формате. Размер поля (4 или 16 байтов) зависит от поля I в заголовке.

QTYPE = 2 (глобальный запрос)

        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                                               |       
        |                                               |       
        |                                               |
        |                   HOSTNAME                    |
        |                     HASH                      |
        |                     (HH)                      |
        |                                               |
        |                                               |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

HH — 16-байтовое хэш-значение имени хоста (hostname).

7. Ответы

QTYPE=0 (h2ip)

        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |  | T|     WG          |       PRIO            |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                                               |
        /                     RDATA                     /
        /                                               /
        |                                               |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Бит T устанавливается (1), если ответ содержит IP. T = 0 говорит о том, что ответ содержит хэш hostname.

WG указывает «вес» ответа [1].

PRIO — приоритет [1].

RDATA содержит двоичный адрес IP, размер которого определяется битом I в заголовке, или хэш hostname.

QTYPE=1 (ip2h)

        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                    RDLENGTH                   |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                                               |
        /                     RDATA                     /
        /                                               /
        |                                               |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

RDLENGTH — размер RDATA (RDATA — имя хоста).

RDATA — распознанное имя хоста.

QTYPE=2 (глобальный запрос)

При QTYPE=2 перед ответом помещается дополнительное поле заголовка

        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                    ANCOUNT                    |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Эти 2 байта указывают число ответов, порожденных запросом. Отметим, что поле ANCOUNT в основном заголовке будет иметь значение 1, если RCODE=0, и 0 в противном случае. Эти два байта указывают реальное число ответов для случая QTYPE=2.

После дополнительного заголовка размещаются ответы в показанном на рисунке формате.

        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        | M| T| P|  WG          |       PRIO            |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                    SERVICE                    |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                                               |
        /                     DATA                      /
        /                                               /
        |                                               |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Бит T указывает тип DATA (T для Hostname и 1 для IP).

Бит M устанавливается при установленном бите T и показывает, что это MAIN_IP для hostname.

P — протокол (0 для TCP, 1 для UDP).

При T=1 версия IP указывается в основном заголовке. Если T=0, данные имеют формат

        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                                               |       
        |                                               |       
        |                                               |
        |                   HOSTNAME                    |
        |                     HASH                      |
        |                     (HH)                      |
        |                                               |
        |                                               |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

HH — 16-байтовое хэш-значение SNSD hostname.

При T=1 данные имеют показанный на рисунке формат

        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                                               |
        /                    RDATA                      /
        /                                               /
        |                                               |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

RDATA — двоичное представление IP, размер которого зависит от бита I в основном заголовке (4 для IPv4, 16 для IPv6).

8. Сжатие

Формат сжатого пакета показан на рисунке.

        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                      ID                    | R|
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |QR| P| Z| QT  |  ANCOUNT  |I |   NK|   RCODE   |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                     USIZE                     |
        |                                               |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
        |                                               |
        /                     DATA                      /
        /                                               /
        |                                               |
        +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

Заголовки остаются не сжатыми. Содержимое пакета, вопрос и ответы сжимаются с помощью zlib. Буфером, для сжатия является DATA. Поле USIZE показывает исходный размер содержимого пакета (вопрос и ответы). Для сжатого пакета устанавливается Z=1.

[1] NTC_RFC 0009 http://netsukuku.freaknet.org/main_doc/ntk_rfc/Ntk_SNSD

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

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

nmalykh@protocols.ru