Алгоритм регистрации переполнений

[alibek]

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

Есть устройство, с которого по SNMP собирается информация.
Один из датчиков — счетчик трафика на интерфейсе. Тип данных — COUNTER (32-битный).
У этого типа данных есть такая особенность — когда он переполняется, он обнуляется.
Эти данные отображаются на графике, причем отображается не значение счетчика, а его производная (т.е. рисуется график загрузки канала); причем программа, рисующая график, знает об особенностях переполнения счетчиков, поэтому когда текущее значение счетчика получается меньше предыдущего, значит произошло переполнение и изменение (разница между текущим и предыдущим значением счетчика) определяется с учетом переполнения.
Программа, рисующая график, получает данные не напрямую по SNMP, а от cgi-скриптов, которые получают данные и передают их в программу.

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

[Хакер]

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

А в чём именно сложность?

[alibek]

В том, как это переполнение зафиксировать.

[Хакер]

1. Зачем его фиксировать? При вычислении производной оно автоматически уходит в силу особенностей организации беззнаковой арифметики.
2. Посмотрим подругому: почему с одним счётчиком проблемы нет, а со многими она возникает. В каком месте при переходе от одного счётчика к нескольким возникает проблема?

[Proxy]

Ну а если просто сложить, а затем уже работать как с одним? Ну если допустим счётчика 2, то по любому снижению значения суммы можно судить о переполнении одного или сразу двух счётчиков. Но глупо как-то, некорректно будет себя вести, если один счётчик обнулится, а второй в это время сильно возрастёт (более, чем на предыдущее значение сбросившегося счётчика). Ну и более чем для 2 счётчиков вообще смысла лишится.
Лично мне кажется, что не зная предыдущее значение даже пытаться не стоит.
А в чём вообще состоит цель суммирования значений счётчиков? Нельзя ли обойтись как-то иначе? Если цель — уместить несколько счётчиков в 1 переменную, то почему не оставить по 16 бит от каждого счётчика и уместить в одну 32-битную переменную 2 счётчика (ну сбрасываться будет сильно часто, иногда может между 2 опросами успеть сброситься неоднократно и будет фейл)? Ну или как-то ещё.

[Хакер]

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

Это антисовет. Суммирование значение счётчиков само при себе может привести к переполнению. Суммирование значений 4 счётчиков может дать 3 переполнения, а может дать и одна. И нельзя точно сказать, сколько их произошло.

Нужно для каждого счётчика вычислить дельту. А потом сложить вместе дельты. При этом вычисление дельты никак не нарушается от влияния переполнения.

Допустим, счётчик был бы не 32-, а 8-битным. Пусть предпоследнее измерение дало 250, а текущее 5. Если отнять от пятерчки число 250, то результат будет 11.

[Proxy]

Допустим, счётчик был бы не 32-, а 8-битным. Пусть предпоследнее измерение дало 250, а текущее 5. Если отнять от пятерчки число 250, то результат будет 11.

Ну так вроде и загвоздка вся в том, что предыдущее значение счётчика узнать — большая проблема. Если можно посчитать дельту, то и проблемы никакой, складывай себе и всё.
Ну насчёт суммы и переполнений в результате сложения, то я не оговаривал, что сумма должна храниться в 32-битной переменной. Это уже другой вопрос. Ну и да, абсурдно выйдет, если счётчиков более чем 2 или если дельта может оказаться сколько-нибудь близкой к 2^32 (31?). Невозможно будет понять было ли переполнение, если один счётчик переполнился, а второй в это время сильно возрос.

[Хакер]

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

Если бы это было большой проблемой, это было бы столь же актуально и для случая с одним счётчиком: вычислить dC/dt было бы невозможно.

[Proxy]

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

Если бы это было большой проблемой, это было бы столь же актуально и для случая с одним счётчиком: вычислить dC/dt было бы невозможно.

Ну так там дельту вычисляет сама программа, а cgi-скрипт как и тут не располагает предыдущим значением счётчика.

[Хакер]

Дельту считает программа, получающая значения счётчиков от cgi-скрипта, получающего их по SNMP?

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

Алибек, почему ты молчишь?

[alibek]

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

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

[Хакер]

Так не получится, программа не умеет суммировать дельты.

Она чужая и с закрытым исходным кодом?

Поэтому нужно либо исключить переполнение (взяв заведомо большую разрядность)

А в какой разрядности получает данные программа? Или она получает их в текстовом виде?

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

Для чего?

[alibek]

Она чужая и с закрытым исходным кодом?

Cacti.
Она с открытым кодом, но копаться в нем я не собираюсь.
Разрядность для счетчика может быть 32 или 64 бита (определяется автоматически), данные получаются в текстовом виде (вывод с cgi-скрипта, в формате поле:значение).

[Хакер]

От cgi-скрипта приходит одно значение (сумма)?

[alibek]

От cgi-скрипта приходит одно или несколько полей в формате поле:значение, разделенных пробелом.
Cacti парсит вывод и сохраняет в БД значения (в соответствии с именем поля).
Можно создать 24 поля (по одному на каждый сетевой интерфейс), просуммировать их и вывести суммарный график.
Но это плохо, т.к. число полей не фиксирвоано — где 24 интерфейса, где 8, где 48.
Поэтому правильнее, чтобы cgi-скрипт сам получал значения со всех интерфейсов, суммировал их и отдавал сумму в одном поле.

[Хакер]

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

Значит пусть получает значения со всех реальных счётчиков, вычисляет dC/dt для каждого счётчика по отдельности, потом суммирует dC/dt всех счётчиков, потом умножает результат на dt и прибавляет результат к значению виртуального счётчика, и значение виртуального счётчика отдаёт программе.

[alibek]

вычисляет dC/dt для каждого счётчика по отдельности

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

[Хакер]

Знать о предыдущих состояниях он не может.

Почему он не может сохранять где-то предыдущие значения и время предыдущего измерения?

Хотя, кстати, давай так. Предположим, что счётчики у нас не 32-битные, а 8-битные. Просто, чтобы не нагружать самих себя длинными числами (4 миллиарда ...). Счётчик 8-битный и переполнение наступает после значения 255.

Приведи пример в следующей форме:

Код: Выделить всё

      Было:   Прибавилось:  Стало:
       C1A         C1D        C1B
       C2A         C2D        C2B
       C3A         C3D        C3B 
       ...         ...        ...
       CnA         CnD        CnB
       ----------------------------
Сумма: Total_A    Total_D    Total_B


при котором переполнение что-то бы портило.

Я пришёл к выводу, что переполнение страшно только в следующем случае: если сумма приростов значений счётчиков между двумя ближайшими измерениями больше чем 2 в степени, равной разрядности счётчика. То есть между двумя ближайшими измерениями через все интерфейсы успеют прокачать 4 Гб трафика, тогда да, переполнения страшны.

Вот пример с 8-битными счётчиками. Числа в десятичной системе счисления.

Код: Выделить всё

Арифметика с переполнениями (computer-like):

      Было:   Прибавилось:  Стало:
       255         000        255
       255         001        000
       255         002        001 
       255         003        002
       010         004        014
       ----------------------------
Сумма: 006         010        016

Код: Выделить всё

Арифметика без переполнений (human-like):

      Было:   Прибавилось:  Стало:
       255         000        255
       255         001        256
       255         002        257 
       255         003        258
       010         004        014
       ----------------------------
Сумма: 1030        010        1040

Как видишь, то, что переполнение происходит, никак не искажает результаты. Производная (то есть дельта) вычисляется правильно: несмотря на то, что при суммировании счётчики многократно переполнялись, дельта и там и там даёт 10.

C 32-битными счётчикам будет всё точно так же.

[alibek]

Почему он не может сохранять где-то предыдущие значения и время предыдущего измерения?

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

По поводу того, что переполнения не меняют картины.
Допустим, счетчики 8-разрядные.
Измерение 1: 0 0 0 0 (сумма 0)
Измерение 2: 10 1 80 20 (сумма 111, дельта 10+1+80+20=111)
Измерение 3: 30 10 200 50 (сумма 290 или 35, дельта 20+9+120+30=179)
Измерение 4: 80 20 30 100 (сумма 230, дельта 50+10+85+50=195)

Вообщем-то да, если эмулировать переполнение суммарного значения, то дельта не меняется.
Если его не эмулировать, тогда внешняя программа неправильно определяет разрядность счетчика (раз пришло 290, значит разрядность выше 8 бит) и поэтому неправильно считает дельту.

[Хакер]

т.е. нужно сохранять несколько сотен промежуточных значений.

Зачем? Не нужно сохранять значения каждого счётчика. Нужно сохранять сумму с учётом переполнений.
От текущей суммы отнимать сохранённую (причём отнимать тоже с учётом перполнения) и в Cacti отправлять уже саму дельту. Пусть Cacti не вычисляет дельту. Разве принципиально, чтобы её вычисляла именно она?

[alibek]

Зачем? Не нужно сохранять значения каждого счётчика. Нужно сохранять сумму с учётом переполнений.

Сумм тоже много (пара сотен).

Пусть Cacti не вычисляет дельту. Разве принципиально, чтобы её вычисляла именно она?

Желательно, чтобы этим занималась Cacti, т.к. алгоритм учета переполнений сложный.

[Хакер]

Сумм тоже много (пара сотен).

Ну и? 800 байтов, это смертельно?

Я всё-таки не могу понять саму суть проблемы. Вот GetTickCount() возвращает беззнаковый 32-битный результат, он тоже переполняется, но никого это не волнует, потому значение счётчика после переполнения минус значение счётчика до переполнения даст правильный временной интервал-результат. Неправильный результат будет только в том случае, если между двумя ближайшими измерениями счётчик тиков переполнялся более 1 раза.

[alibek]

Я всё-таки не могу понять саму суть проблемы.

Суть проблемы была в том, что нужно было эмулировать переполнение для суммы значений.
Если его эмулировать, то проблемы больше нет.

[Хакер]

Суть проблемы была в том, что нужно было эмулировать переполнение для суммы значений.

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

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

То есть вот этот пост решил проблему?

[alibek]

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

А каков естественный образ?
В скриптовых языках при переполнении происходит ошибка.

То есть вот этот пост решил проблему?

Вообщем да, натолкнул на мысль, где у меня была ошибка.

[Хакер]

А каков естественный образ?

Естественный образ таков, что когда процессор считает 0xFFFFFFFF + 2, то (естественным образом) получается 0x0000001. А когда отнимаем от числа 5 число 0xFFFFFFFF, получаем 6. То есть, если писать на Си/С++, то:

Код: Выделить всё

old_time = GetTickCount(); // За 1 секунду до переполнения, вернёт 4294966296
                 ... что-то делаем ...
new_time = GetTickCount(); // Через 2 секунду после переполнения, вернёт 2000

printf("%d\n", new_time - old_time); // Выведет 3000 без всяких контролей переполнения

Причём даже не важно, какие типы (signed или unsigned) мы используем, результат будет одинаков из-за того, что процессор и signed и unsigned числа считает одним и тем же образом, даже не беря во внимание разницу). Единственная вещь, где разница между типами signed и unsigned доходит до процессора — это инструкции сравнения.

[alibek]

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

[Хакер]

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

Ну, в VB похожая ситуация, и чтобы добиться поведения как в Си, я сделал следующие функции (вообще, они в составе несколько более полного модуля, может быть и стоит его опубликовать):

Код: Выделить всё

Private Const BITMSK_NEGATIVE_BIT_DW    As Long = &H80000000
Private Const BITMSK_NEGATIVE_BIT_W     As Integer = &H8000
Private Const BITMSK_NEGATIVE_BIT_B     As Byte = &H80

Private Const BITMSK_ALL_BITS_DW        As Long = &HFFFFFFFF
Private Const BITMSk_ALL_BITS_W         As Integer = &HFFFF
Private Const BITMSK_ALL_BITS_B         As Byte = &HFF

...
...
...


Public Function EmAddUnsigned(ByVal ul1 As Long, ByVal ul2 As Long) As Long
    If (BITMSK_NEGATIVE_BIT_DW And ul1) = _
       (BITMSK_NEGATIVE_BIT_DW And ul2) Then
        '
        ' Либо два неотрицательных числа, либо два отрицательных. Их
        ' сложение может дать переполнение, поэтому сделаем из них
        ' два разнознаковых числа (такие никогда не дадут переполнение):
        ' инвертируем одному из них MSB, складываем, а потом инвертируем
        ' MSB у результата. Биты инвертируются оператором Xor.
        '
       
        Const MSB As Long = BITMSK_NEGATIVE_BIT_DW ' Самый старший бит
        EmAddUnsigned = ((ul1 Xor MSB) + ul2) Xor MSB
    Else
        '
        ' Знаки разные, и можно просто сложить числа: два числа, только
        ' одно из которых отрицательное, никогда не дадут переполнение
        ' в результате сложения или вычитания.
        '
       
        EmAddUnsigned = ul1 + ul2
    End If
End Function

Public Function EmSubtractUnsigned(ByVal ul1 As Long, _
                                   ByVal ul2 As Long) As Long
    '
    ' Заранее предостерегаю от идеи сделать эту функцию как обёртку над
    ' EmAddUnsigned(ul1, -ul2). Выражение (-ul2) может дать overflow.
    ' Эта функция использует тот же принцип, что и EmAddUnsigned, но
    ' с обратной логикой выбора способа.
    '
   
    If (BITMSK_NEGATIVE_BIT_DW And ul1) = _
       (BITMSK_NEGATIVE_BIT_DW And ul2) Then
        EmSubtractUnsigned = ul1 - ul2
    Else
       
        Const MSB As Long = BITMSK_NEGATIVE_BIT_DW ' Самый старший бит
        EmSubtractUnsigned = ((ul1 Xor MSB) - ul2) Xor MSB
    End If
End Function