Atomic test-and-set for LPC1788 microcontroller

Question

I'm working with the NXP LPC1788 microcontroller and I'm developing a multi-threaded application in C. In part of my application I define a custom linked-list data structure. I was previously having problems with my program due to concurrent access to a particular list which I seem to have solved by implementing a "lock acquire" method and a "lock release" method for lists which threads can call before accessing the list itself.

I did this by adding a 'sema' data member to the list struct:

typedef struct linked_list
{
  list_node_t *head;
  list_node_t *tail;
  uint32_t len;
  NODE_ITEM_TYPE_T itemType;
  uint32_t itemSize;
  uint8_t sema;
} linked_list_t;

My "lock acquire" method is given below:

void LIST_AcquireLock(linked_list_t *list)
{
  while(list->sema);
  list->sema = 1;
}

My "lock release" method is given below:

void LIST_ReleaseLock(linked_list_t *list)
{
  list->sema = 0;
}

Generally this seems to work okay, since my application involves adding and removing items to a list like this thousands of times a second and I have not noticed any bugs related to concurrent access since.

However, to be more confident that this works, I was wondering if there was any way of implementing a test-and-set approach. The LPC1788 relies on a version of the Thumb instruction set specific to Cortex-M3 microcontrollers, which can be found here or in the user manual on page 918+.

Looking through it, though, I can't find anything like a test-and-set instruction. I might just be overlooking it.

Ideally, I would like to have something like this:

void LIST_AcquireLock(linked_list_t *list)
{
  do{
    while(list->sema);
  } while(TestAndSet(list->sema));
}

EDIT

Based on Nemo's answer, I've attempted the following:

void LIST_AcquireLock(linked_list_t *list)
{
  // Wait until lock seems free.
  while(list->sema);

  // Make sure lock is actually free.
  do {

    // If the semaphore is locked, we continue.
    // OTHERWISE we try to lock it ourselves.
    if(__LDREXB(&(list->sema))) continue;

    // If __STREXB returns 1, then another thread might have accessed that
    // memory location and we can't be sure the lock operation is atomic,
    // so try the locking procedure again.
  } while(__STREXB(1, &(list->sema)));
}

If it's helpful, this is the corresponding assembly code:

LIST_AcquireLock:
??LIST_AcquireLock_0:
       0x56de: 0x7d01         LDRB      R1, [R0, #0x14]
       0x56e0: 0x2900         CMP       R1, #0
       0x56e2: 0xd1fc         BNE.N     ??LIST_AcquireLock_0    ; 0x56de
??LIST_AcquireLock_1:
       0x56e4: 0xf110 0x0114  ADDS.W    R1, R0, #20             ; 0x14
       0x56e8: 0xe8d1 0x1f4f  LDREXB    R1, [R1]
       0x56ec: 0xb2c9         UXTB      R1, R1
       0x56ee: 0x2900         CMP       R1, #0
??LIST_AcquireLock_2:
       0x56f0: 0xf110 0x0114  ADDS.W    R1, R0, #20             ; 0x14
       0x56f4: 0x2201         MOVS      R2, #1
       0x56f6: 0xe8c1 0x2f43  STREXB    R3, R2, [R1]
       0x56fa: 0x2b00         CMP       R3, #0
       0x56fc: 0xd1f2         BNE.N     ??LIST_AcquireLock_1    ; 0x56e4
       0x56fe: 0x4770         BX        LR

I'm having trouble reproducing the concurrent access issues (assuming it was concurrency issues I was having) so I don't know for sure that this works.

http://www.doulos.com/knowhow/arm/Hints_and_Tips/Implementing_Semaphores/ — Hans Passant, Sep 02 '14 at 14:54
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dai0321a/BIHEJCHB.html — Hans Passant, Sep 02 '14 at 14:55

score 1 · Accepted Answer · edited May 23 '17 at 11:43

ARM uses a "load-linked/store-exclusive" paradigm for atomic operations. See this question and Section 39.2.4.8 of the user manual you linked for details.

[Update]

Based on the code in the link @HansPassant provided, I would suggest some slight changes to your routine:

void LIST_AcquireLock(linked_list_t *list)
{
  // Wait until lock seems free.
  //while(list->sema); // unnecessary

  // Make sure lock is actually free.
  do {

    // If the semaphore is locked, we continue.
    // OTHERWISE we try to lock it ourselves.
    if(__LDREXB(&(list->sema))) continue;

    // If __STREXB returns 1, then another thread might have accessed that
    // memory location and we can't be sure the lock operation is atomic,
    // so try the locking procedure again.
  } while(__STREXB(1, &(list->sema)));

  // Ensure CPU does not reorder any memory accesses across lock acquisition.
  __DMB();
}

The __DMB() is probably irrelevant on very simple ARM cores, but it is definitely needed on more complex ones. Modern CPUs have complicated memory models.

Thanks! Before I mark this as accepted, would you mind just glancing over my implementation (the edit in the original post) just to confirm that I have the right idea. — Tagc, Sep 02 '14 at 15:37
Yes, your code looks OK... almost. You should read the links @HansPassant provided, especially the one from arm.com... You need a `__DNB()` instruction immediately after acquiring the lock to guarantee the CPU does not reorder any memory accesses across the lock operation. (Probably not an issue for very simple ARM cores, but definitely a concern in general.) — Nemo, Sep 02 '14 at 16:19

Atomic test-and-set for LPC1788 microcontroller

1 Answers1