Как Linux справляется с переполнением в jiffies?

Question

Предположим, у нас есть следующий код:

if (timeout > jiffies)
{
    /* we did not time out, good ... */
}
else
{
    /* we timed out, error ...*
}

Этот код отлично работает, когда значение jiffies не переполняется.Тем не менее, когда переполнение jiffies и переход к нулю, этот код не работает должным образом.

Linux, по-видимому, предоставляет макросы для решения этой проблемы переполнения

#define time_before(unknown, known) ((long)(unkown) - (long)(known) < 0)

, а код выше долженбыть защищенным от переполнения при замене этим макросом:

// SAFE AGAINST OVERFLOW
if (time_before(jiffies, timeout)
{
    /* we did not time out, good ... */
}
else
{
    /* we timed out, error ...*
}    

Но каково обоснование для time_before (и других макросов time_?

time_before (jiffies, timeout) будет расширено до

((long)(jiffies) - (long)(timeout) < 0)

Как этот код предотвращает проблемы переполнения?

Answer 1

Давайте попробуем:

#define time_before(unknown, known) ((long)(unkown) - (long)(known) < 0)

Я сильно упросту ситуацию, сказав, что long - это всего два байта, поэтому в шестнадцатеричном формате он может иметь значение в диапазоне [0, 0xFFFF].

Теперь он подписан, поэтому диапазон [0, 0xFFFF] можно разбить на два отдельных диапазона [0, 0x7FFF], [0x8000, 0xFFFF]. Они соответствуют значениям [0, 32767], [-32768, -1]. Вот схема:

[0x0      -              -                  -               0xFFFF]
[0x0                       0x7FFF][0x8000                   0xFFFF]
[0                         32,767][-32,768                      -1]

Скажите timeout - это 32 000. Мы хотим проверить, не истек ли наш тайм-аут, но на самом деле мы переполнились, поэтому jiffies равно -31 000. Поэтому, если бы мы наивно пытались оценить jiffies < timeout, мы бы получили True. Но, подключив значения:

   time_before(jiffies, offset)
== ((long)(jiffies) - (long)(offset) < 0)
== (-31000 - 32000 < 0)             // WTF is this. Clearly NOT -63000
== (-31000 - 1768 - 1 - 30231 < 0)  // simply expanded 32000
== (-32768 - 1 - 30232 < 0)         // this -1 causes an underflow
== (32767 - 30232 < 0)
== (2535 < 0)
== False

jiffies - это 4 байта, а не 2, но применяется тот же принцип. Это помогает вообще?

Answer 2

См., Например, здесь: http://fixunix.com/kernel/266713-%5Bpatch-1-4%5D-fs-autofs-use-time_before-time_before_eq-etc.html

Код с проверкой переполнения некоторой фиксированной небольшой константы был преобразован для использования time_before.Зачем?

Я просто суммирую комментарий, который относится к определению функций time_after и т. Д .:

include / linux / jiffies.h: 93

 93 /*
 94  *      These inlines deal with timer wrapping correctly. You are 
 95  *      strongly encouraged to use them
 96  *      1. Because people otherwise forget
 97  *      2. Because if the timer wrap changes in future you won't have to
 98  *         alter your driver code.
 99  *
100  * time_after(a,b) returns true if the time a is after time b.
101  *

Итак, time_before и time_after - лучшее усилие для обработки переполнения.

Ваш тестовый сценарий с большей вероятностью будет timeout < jiffles (без переполнения), чемtimeout > jiffles (с переполнением):

unsigned long jiffies = 2147483658;
unsigned long timeout = 10;

А если вы измените тайм-аут на

unsigned long timeout = -2146483000;

, каким будет ответ?

Или вы можете изменитьпроверка от

printf("%d",time_before(jiffies,timeout));

до

printf("%d",time_before(jiffies,old_jiffles+timeout));

, где old_jiffles - это сохраненное значение jiffles в начале таймера.

Итак, я думаю, что использование time_before может быть как:

old_jiffles=jiffles;
timeout=10;  // or even 10*HZ for ten-seconds

do_a_long_work_or_wait();

//check is the timeout reached or not
if(time_before(jiffies,old_jiffles+timeout) ) {
  do_another_long_work_or_wait();
} else {
  printk("ERRROR: the timeout is reached; here is a problem");
  panic();
}

Answer 3

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

Существует фундаментальное предположение, что timeout первоначально рассчитывалось как jiffies + some_offset в некоторый предшествующий недавний момент времени, в частности, менее половины диапазона переменных. Если вы пытаетесь измерить время дольше, чем это, то все пойдет не так, и вы получите неправильный ответ.

Если мы притворимся, что jiffies имеет 16-битную ширину для удобства объяснения (аналогично другим ответам):

timeout > jiffies

Это сравнение без знака, которое предназначено для возврата true, если мы еще не достигли тайм-аута. Некоторые примеры:

• timeout == 0x0300, jiffies == 0x0100: результат верный, как и ожидалось.
• timeout == 0x8100, jiffies == 0x7F00: результат верный, как и ожидалось.
• timeout == 0x0100, jiffies == 0xFF00: упс, результат ложный, но мы на самом деле не достигли тайм-аута, он просто обернул счетчик.
• timeout == 0x0100, jiffies == 0x0300: результат ложный, как и ожидалось.
• timeout == 0x7F00, jiffies == 0x8100: результат ложный, как и ожидалось.
• timeout == 0xFF00, jiffies == 0x0100: упс, результат верен, но мы действительно передали тайм-аут.

time_before (jiffies, timeout)

Это делает сравнение со знаком разницы значений, а не самих значений, и снова ожидается, что вернет true, если время ожидания еще не достигнуто. При условии, что приведенное выше предположение подтверждается, те же примеры:

• timeout == 0x0300, jiffies == 0x0100: результат верный, как и ожидалось.
• timeout == 0x8100, jiffies == 0x7F00: результат верный, как и ожидалось.
• timeout == 0x0100, jiffies == 0xFF00: результат верный, как и ожидалось.
• timeout == 0x0100, jiffies == 0x0300: результат ложный, как и ожидалось.
• timeout == 0x7F00, jiffies == 0x8100: результат ложный, как и ожидалось.
• timeout == 0xFF00, jiffies == 0x0100: результат ложный, как и ожидалось.

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

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