Compare And Swap Compileert fout voor ARMv7-a (Cortex-A8)

[DoubleJOnline]

Hallo,

Ik heb problemen met het compileren van:
__sync_bool_compare_and_swap(); voor ARMv7-a (Cortex A8).

Om te kijken waar het probleem zit heb ik eerst een simpele applicatie gemaakt om te kijken of ik daarmee het probleem kan vinden.
-> Hieronder volgt de code van dit programma inclusief makefile. Deze werkt en cross compileert ook voor ARM.
-> Vervolgens de situatie waarin het niet werkt.

Werkende situatie:
Test applicatie:

code:

#include <stdlib.h>
#include <stdio.h>

#include "utility/LockFree.h"

int main(int argc, char* argv[])
{
    long target = 3;
    
    // Simple compare and swap scenario test:
    // Read value to temp, generate update value, perform a compare and swap.
    int temp = target;
    int newVal = 8;
    printf("Current target value: %li\n", target);
    if (LUNA::Utility::CAS(&target, temp, newVal))
    {
        printf("Successfull compare and swap: %li\n", target);
    }
    else
    {
        printf("Unsuccessfull compare and swap: %li\n", target);
    }
        
    return 0;
}

Makefile:

code:

SOURCE_DIR=.
BUILD_DIR=build
LUNA_ROOT_DIR=/home/janjaap/workspace-cpp/LUNA/LUNA
SOURCE_FILES=$(SOURCE_DIR)/test.cpp
OBJECT_FILES=$(patsubst %.cpp,%.o,$(SOURCE_FILES))



ifeq ($(target),ARM)
CROSS_COMPILE=arm-linux-gnueabi-
LUNA_INCLUDE_DIR=$(LUNA_ROOT_DIR)/build_dir/target-arm-linux_v7-a/root-linux-arm-v7/include
LUNA_LINK_DIR=$(LUNA_ROOT_DIR)/build_dir/luna/target-arm-linux_v7-a
else
CROSS_COMPILE=
LUNA_INCLUDE_DIR=$(LUNA_ROOT_DIR)/staging_dir/target-i386-linux/include
LUNA_LINK_DIR=$(LUNA_ROOT_DIR)/build_dir/luna/target-i386-linux
endif

LDFLAGS=-L$(LUNA_LINK_DIR)
CPPFLAGS=-I$(LUNA_INCLUDE_DIR) -Wall
LIBS=-lLUNA -pthread -lrt


CC=$(CROSS_COMPILE)g++
LD=$(CROSS_COMPILE)g++
RM=rm -f

all: test

test: $(OBJECT_FILES)
    $(LD) $(LDFLAGS) $^ $(LIBS) -o $@


.cpp.o:
    $(CC) -c $(CFLAGS) $(CPPFLAGS) -o $@ $<
    
clean:
    $(RM) $(OBJECT_FILES) test

Code van de "LockFree.h" welke ik uit een intern ontwikkelde library gebruik:

code:

#pragma once

#include "utility/LUNATypes.h"
#include <stdlib.h>

namespace LUNA
{
  namespace Utility
  {
    template<typename PTRType, typename DataType>
    inline bool CAS(PTRType *ptr, DataType prev, DataType update)
    {
      return __sync_bool_compare_and_swap(ptr, prev, update);
    }
  }
}

Dit bovenstaande voorbeeld compileert prima voor zowel de x86 als ARMv7-a.

Niet werkende situatie::

Het probleem is echter wanneer ik deze CAS functie toepas in een lock-free queue. Om deze generiek te maken voor verschillende datatypes maak ik gebruik van templates. Hiervoor is een structure gedefinieerd die de pointers naar de nodes in de queue bijhoud:

code:

    template<typename ItemType>
    union pointer_t
    {
        DWORD dword;
        WORD words[2];
        struct node_t<ItemType>* ptrs[2];
    };

En de node:

code:

    template<typename ItemType>
    struct node_t
    {
        volatile pointer_t<ItemType> next;
        ItemType value;
    };

De compare and swap pas ik hierbij toe op de pointer_t structures:

code:

if (LUNA::Utility::CAS(&(nextPtr->dword), next.dword, make_tuple(relPtr, next.words[COUNT] + 1).dword))

Voor x86 compileert dit prima, echter wanneer ik dit voor ARMv7-a compileer, laat hij de compare and swap naar

code:

__sync_bool_compare_and_swap_8

verwijzen.
Dit levert op dat hij de referenties naar deze functie niet kan vinden:

code:

>(unsigned long long volatile*, unsigned long long, unsigned long long)]+0x30): undefined reference to `__sync_bool_compare_and_swap_8'
build/target-arm-linux_v7-a/obj/sharedMemTest.o: In function `bool LUNA::Utility::CAS<unsigned long long, unsigned long long>(unsigned long long*, unsigned long long, unsigned long long)':
sharedMemTest.cpp:(.text._ZN4LUNA7Utility3CASIyyEEbPT_T0_S4_[bool LUNA::Utility::CAS<unsigned long long, unsigned long long>(unsigned long long*, unsigned long long, unsigned long long)]+0x30): undefined reference to `__sync_bool_compare_and_swap_8'

Gezien de arm architecture 32 bits is, heb ik ook het vermoeden dat een 8 bytes CAS niet bestaat. De vraag hierbij dus:
-> Waarom wordt deze CAS naar een LONG data type gemapped.
-> Is er een methode om hem te forceren naar een _4 variant (__sync_bool_compare_and_swap_4() hardcoden heb ik al geprobeerd, dan compileert hij wel, maar gaat het bij de executie fout).

[Xiphalon]

Omdat

code:

        struct node_t<ItemType>* ptrs[2];

2 pointers, en dus 8 bytes is?

[MLM]

Over het algemeen zijn CAS (of andere lock-free instructies) alleen in processor-word grootte beschikbaar.
Een pointer is altijd processor-word grootte. Je kan er dus niet van uit gaan dat je 2 pointers kan CAS-en.
(Sidenote: met processor-word bedoel ik dus niet WORD, maar size_t)

x86 is in dit geval een uitzondering, omdat die een een LOCK CMPXCHG8B heeft.

Maar er zijn ook prima bruikbare lockless-queue algoritmes die met 4b CAS werken, kan je gewoon op internet vinden Bijvoorbeeld http://moodycamel.com/blo...t-lock-free-queue-for-c++ (SPSC) of http://www.1024cores.net/...ive-mpsc-node-based-queue (MPSC)

[ Voor 16% gewijzigd door MLM op 05-09-2013 14:21 ]

[deadinspace]

darkmage schreef op donderdag 05 september 2013 @ 13:43:
Omdat

code:

        struct node_t<ItemType>* ptrs[2];

2 pointers, en dus 8 bytes is?

Maar hij doet (in tegenstelling tot wat hij zelf schreef) helemaal geen CAS op pointer_t unions, maar op DWORDs:

C++:

if (LUNA::Utility::CAS(&(nextPtr->dword), next.dword, make_tuple(relPtr, next.words[COUNT] + 1).dword))

(Dat is in de foutmelding ook vrij duidelijk, want daar gaat het om een unsigned long long, niet om een union of array)

Dus de vraag lijkt mij eerder: Waar komt het DWORD type vandaan, hoe is die gedefinieerd, en gaat dat wel goed met crosscompilen?

[farlane]

Misschies is het handiger om de standaard inttypes te gebruiken?

[PrisonerOfPain]

deadinspace schreef op donderdag 05 september 2013 @ 14:26:
(Dat is in de foutmelding ook vrij duidelijk, want daar gaat het om een unsigned long long, niet om een union of array)

long long = 64 bit = 8 byte, vandaar de call naar de _8 functie.

[deadinspace]

farlane schreef op donderdag 05 september 2013 @ 14:35:
Misschies is het handiger om de standaard inttypes te gebruiken?

+1

DWORD is sowieso een archaisch begrip waarvan de bedoelde betekenis eigenlijk alleen klopt op 16-bit CPUs

PrisonerOfPain schreef op donderdag 05 september 2013 @ 15:32:
long long = 64 bit = 8 byte, vandaar de call naar de _8 functie.

Joh, echt waar?

Waar het mij om ging is dat darkmage opmerkte dat een array van twee pointers 64 bits is. Maar uit de foutmelding blijkt dat LUNA::Utility::CAS() aangeroepen wordt met een unsigned long long, niet met een array van twee pointers. Zie ook de rest van mijn post.

Oh, en een long long is niet per definitie 64 bit, maar dat terzijde.

[ Voor 21% gewijzigd door deadinspace op 05-09-2013 15:42 ]

[MLM]

Ik denk dat de auteur hier het daadwerkelijke DWORD (als in, bedoeld met de definitie double-word) gebruikt, gezien ook dat hij het uniont met twee pointers (en twee words). Dat heeft hij getypedeft met iets wat uiteindelijk resolved naar unsigned long long (en die is 8 bytes lang aldus de compiler, gezien die de built-in met _8 kiest).

Desondanks is de keuze voor de typenaam nogal ambigu, gezien de "standaard" windows definitie. Maar goed, hij gebruikt GCC, dus kans is dat windows niet 1 van zijn targets is. Misschien dat mensen daardoor wat verward zijn omdat ze de windows definitie verwachtten

Maar mijn punt uit mijn eerdere post blijft: je wilt een double-width CAS, en die heeft lang niet elke architectuur.

[ Voor 3% gewijzigd door MLM op 05-09-2013 17:09 ]

[farlane]

MLM schreef op donderdag 05 september 2013 @ 17:08:
Maar mijn punt uit mijn eerdere post blijft: je wilt een double-width CAS, en die heeft lang niet elke architectuur.

Als ik deze pagina zou de ARMv7a architectuur wel een doubleword variant kunnen ondersteunen, maar de vraag is of gcc(?) die ook daadwerkelijk heeft geimplementeerd.

[MLM]

Weet je zeker dat je -march switch goed staat? Ik ben verre van een GCC expert, maar anders kan je misschien met inline assembler proberen om de instructie te forceren.

[ Voor 9% gewijzigd door MLM op 06-09-2013 11:46 ]

[DoubleJOnline]

Hallo,

Dank allen voor de reactie. Het vermoeden dat x86 wel iets heeft voor 8byte CAS klopt denk ik wel.

Ik heb het als volgt opgelost. -> de tweede set van 4 bytes die vergeleken werd in het algoritme betrof een counter. Ik heb nog even kritisch naar de implementatie en de paper waarop deze gebaseerd was bekeken en tot de conclusie gekomen dat de desbetreffende counter niet onderdeel was van het algoritme volgens de paper en dat alleen het pointer gedeelte vergeleken wordt.

Dit heb ik dan ook uit de implementatie gehaald waardoor ik een 4 bytes pointer waarde overhield voor de CAS. Dit cross compileert nu prima.

Dank voor de feedback.

[MLM]

Die counter is meestal bedoeld om problemen omtrent ABA op te lossen, zie bijvoorbeeld Wikipedia: ABA problem

Door de counter weg te halen, is je code waarschijnlijk niet meer threadsafe onder hoge contention.