atomi c LIFO со связным списком в сборке AArch64 с использованием загрузки или сохранения между ldxr / stxr - PullRequest
Новая
       139

atomi c LIFO со связным списком в сборке AArch64 с использованием загрузки или сохранения между ldxr / stxr

1 голос
/ 19 июня 2020

Я реализовал LIFO для контекста разделяемой памяти с использованием сборки для ARMv8 64bit.

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

Это правильная сборка для реализации atomi c вставка и удаление для LIFO?

Он использует LL / S C с дополнительной загрузкой или сохранением между LDXR и STXR для чтения головы -> next или сохраните указатель в новом узле. 

typedef union {
   void * head[1];
}lifo;
int atomic_lifo_init(lifo * h) {
if (h) {
   h->head[0]=NULL;
  }
}
inline void *
 atomic_lifo_delete (lifo *h)
 {
         void    *ret = NULL;
         /*sa_ignore UNUSED_VAR*/
         void *  tmp = NULL;
 
         asm volatile ("\n"
                 "2:  ldxr      %0,[%2] \n" //load the head from h, which points the 1st node of list to local ret pointer.
                 "    cbz     %0, 3f \n" //check if the lifo is empty.
                 "    ldr      %1,[%0] \n" //store in tmp the 2nd node by derefencing the ret (h->head points 1st node. value of each node is next node as 1st attribute of node structure is pointing next.)
                 "    stxr     %w1, %1,[%2] \n" //update h->head with tmp.
                 "    cbnz     %w1, 2b \n" //continue if failed
                 "3:              \n"
                 : "=&r" (ret), "=&r" (tmp)
                 : "r" (h)
                 : "memory"
                 );
         return(ret);
 }
 
 /*
  * atomic_lifo_insert()
  *      Put an element on a list, protected against SMP
  */
 void
 atomic_lifo_insert (lifo *h, void *__new)
 {
         /*sa_ignore UNUSED_VAR*/
         void * next = NULL;
         void * flag = NULL;
         asm volatile (" \n"
                 "1: ldxr      %1,[%2] \n" //load head[0] from h,which points 1st node to local next pointer
                 "   str      %1,[%3] \n" //store the local next pointer to value of __new, as 1st attribute of the any node is next (convention used here). so __new's next is pointing current 1st node.
                 "   stxr    %w0, %3,[%2] \n" //update the h->head with 
   __next.
                 "   cbnz    %w0, 1b \n" //if stxr is failure try again.
                 : "=&r" (flag), "=&r" (next)
                 : "r" (h), "r" (__new)
                 : "memory"
                 );
 }

Я действительно новичок в сборке ARM, поэтому любая помощь приветствуется.

1 Ответ

1 голос
/ 20 июня 2020

Ваши встроенные ограничения asm выглядят правильно, это должно компилироваться так, как вы планировали. Вероятно, вы могли бы использовать "+m" (*h), чтобы компилятор мог выбрать режим адресации вместо жесткого кодирования его с помощью "r"(h) и [%2].

Что касается порядка, ldr упорядочивается по зависимости после ldxr (например, C11 memory_order_consume), так что это работает.

Но str между LL / S C в insert может не стать видимым до после stxr публикует адрес в других потоках. Так что я думаю вам нужно stlxr (релиз-магазин) в insert.

Выполнение дополнительной загрузки или сохранения между LDXR / STXR небезопасно. В статье LL / S C Википедии упоминается, что некоторые реализации могут ложно выйти из строя, если вы выполните любую загрузку или сохранение между LL и S C. Wiki сообщает, что PowerP C специально это допускает. Но AArch64 в целом явно не делает: в соответствии с руководством по ARM ( см. Комментарий @James Greenhalgh ):

Циклы LoadExcl / StoreExcl гарантируют только продвижение вперед if [...] Между Load-Exclusive и Store-Exclusive нет явных обращений к памяти.

Могут быть некоторые процессоры AArch64, где вы создадите бесконечный l oop из stxr сбой, но могут быть и другие, где это работает. Если на практике это работает на тестируемом вами процессоре, вероятно, неплохо было бы посмотреть, есть ли какая-либо документация, подтверждающая это.

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

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

Однако я не очень тщательно продумывал ваш алгоритм; У меня также нет опыта разработки или использования вещей, связанных с необработанным LL / S C. Я в принципе знаю, как они работают, но не готов сказать, что это определенно правильно. Я не вижу никаких проблем после того, как немного подумал об этом, но это не значит, что их нет.

...