Атомные операции в ARM

Question

Я работал над встроенной ОС для ARM, однако есть несколько вещей, которые я не понял в архитектуре даже после обращения к источникам ARMARM и linux.

Атомные операции.

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

arch/arm/include/asm/atomic.h :
    #define atomic_read(v)  (*(volatile int *)&(v)->counter)
    #define atomic_set(v,i) (((v)->counter) = (i))

Однако проблема возникает, когда я хочу атомарно манипулировать этим значением, используя инструкции процессора (atomic_inc, atomic_dec, atomic_cmpxchg и т. Д.), Которые используют LDREX и STREX для ARMv7 (моя цель).

ARMARM ничего не говорит о прерываниях, блокируемых в этом разделе, поэтому я предполагаю, что между LDREX и STREX может произойти прерывание. Он упоминает о блокировке шины памяти, которая, как мне кажется, полезна только для систем MP, где может быть больше процессоров, пытающихся получить доступ к одному и тому же местоположению одновременно. Но для UP (и, возможно, MP), если прерывание таймера (или IPI для SMP) срабатывает в этом небольшом окне LDREX и STREX, обработчик исключений выполняет, возможно, изменяет контекст процессора и возвращается к новой задаче, однако шокирующая часть наступает сейчас он выполняет CLREX и, следовательно, удаляет любую эксклюзивную блокировку, удерживаемую предыдущим потоком. Итак, как лучше использовать LDREX и STREX, чем LDR и STR для атомарности в системе UP?

Я читал кое-что о мониторе исключительной блокировки, поэтому у меня есть возможная теория, что когда поток возобновляет и выполняет STREX, монитор os вызывает этот вызов, что может быть обнаружено, и цикл может быть повторно выполнен с использованием нового значение в процессе (переход обратно в LDREX), я здесь?

Answer 1

Хорошо, получил ответ с их сайта.

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

Answer 2

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

do
{
  new_value = __LDREXW(dest) + 1;
} while (__STREXW(new_value, dest));

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

do
{
  old_value = *dest;

  new_value = complicated_function(old_value);
} while (CompareAndStore(dest, new_value, old_value) != 0);

... Assuming CompareAndStore is something like:

uint32_t CompareAndStore(uint32_t *dest, uint32_t new_value, uint_32 old_value)
{
  do
  {
    if (__LDREXW(dest) != old_value) return 1; // Failure
  } while(__STREXW(new_value, dest);
  return 0;
}

Этот код должен будет перезапустить свой основной цикл, если что-то изменится * dest во время вычисления нового значения, но потребуется перезапуск только небольшого цикла, если __STREXW завершится ошибкой по какой-то другой причине [что, вероятно, не слишком вероятно, учитывая, что будет только две инструкции между __LDREXW и __STREXW]

Приложение Примером ситуации, когда "вычисление нового значения на основе старого" может быть сложным, может быть ситуация, когда "значения" фактически являются ссылками на сложную структуру данных. Код может извлечь старую ссылку, извлечь новую структуру данных из старой, а затем обновить ссылку. Этот шаблон встречается гораздо чаще в сборках мусора, чем в программировании на "голое железо", но существует множество способов, которые могут возникнуть даже при программировании на голое железо. Обычные распределители malloc / calloc, как правило, не являются потокобезопасными / безопасными от прерываний, но часто используются распределители для структур фиксированного размера. Если у человека есть "пул" некоторого числа структур данных с степенью двойки (скажем, 255), можно использовать что-то вроде:

#define FOO_POOL_SIZE_SHIFT 8
#define FOO_POOL_SIZE (1 << FOO_POOL_SIZE_SHIFT)
#define FOO_POOL_SIZE_MASK (FOO_POOL_SIZE-1)

void do_update(void)
{
  // The foo_pool_alloc() method should return a slot number in the lower bits and
  // some sort of counter value in the upper bits so that once some particular
  // uint32_t value is returned, that same value will not be returned again unless
  // there are at least (UINT_MAX)/(FOO_POOL_SIZE) intervening allocations (to avoid
  // the possibility that while one task is performing its update, a second task
  // changes the thing to a new one and releases the old one, and a third task gets
  // given the newly-freed item and changes the thing to that, such that from the
  // point of view of the first task, the thing never changed.)

  uint32_t new_thing = foo_pool_alloc();
  uint32_t old_thing;
  do
  {
    // Capture old reference
    old_thing = foo_current_thing;

    // Compute new thing based on old one
    update_thing(&foo_pool[new_thing & FOO_POOL_SIZE_MASK],
      &foo_pool[old_thing & FOO_POOL_SIZE_MASK);
  } while(CompareAndSwap(&foo_current_thing, new_thing, old_thing) != 0);
  foo_pool_free(old_thing);
}

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