On Sun, 04 Mar 2012 06:05:46 +0100, David Henningsson <[email protected]> wrote: > On 03/02/2012 04:45 PM, Tanu Kaskinen wrote: >> On Fri, 2012-03-02 at 13:49 +0100, David Henningsson wrote: >>> Instead of trying to verify the algorithm, I went to Google to look for >>> a reference implementation to compare against, and quickly found [1]. >>> And indeed our flist looks like the one under the section "Naive >>> lock-free stack which suffers from ABA problem." on that page. :-/ >>> What's worse, there does not seem to be an easy fix. > > Have you ever woken up in the middle of the night with an idea of how to
> solve the problem almost clear in your mind? The wikipedia page said > "tag bits" was a common workaround, using the low bits of the pointer. I > initially rejected the idea as I didn't think it would be portable > enough, but now I realise that the pointers are just indices to a table. > > So I've written a patch which I post separately, please review. I've > been running my own test case for a while and seems to have succeeded so > far. > > @Eric Casteleijn, as you seem to be the only one that can reproduce this > problem somewhat reliably, would you mind trying my patch for a few days > and see if it resolves the problem? If so, I'll prepare a PPA for you to > use for testing. Hi David, I wrote probably something similar (patch is attached). It would be interesting to compare our patches, but I could not find your patch from the mailing list yet. It is good to keep in mind that at least my version of the tag approach is not guaranteed to avoid the ABA-problem, it only makes it very unlikely. In 64bit system one may argue that it is impossible for one thread to remain asleep while the one element it was trying to manipulate is poped and pushed back to linked list exactly 4294967296 times and then, while the same element is still on top of the list, the thread is scheduled again and it fall for the ABA-problem. But what about 32bit system, can we draw the same conclusion there? I would say the above scenario is still virtually impossible, even if you change the number 4294967296 to 65536. Sorry for the mess I caused. At the time of making the ABA-suffering flist-implementation I was desperately looking for a fix to a notorious Nokia N900 "diesel engine"-bug* and when I found the fix I was just happy that the flist-test passed went on to the next problem. * The sound resembling a diesel engine came when a memblock in a free list was swapped out. While PA was waiting for the memblock to be accessible again the alsa-device kept on playing the same 20ms DMA buffer content over and over again. Best regards, Jyri ps. I have not had time to test the patch on 32bit system yet.
From 680169b383306617949494acd7a0b3a26489b153 Mon Sep 17 00:00:00 2001 From: Jyri Sarha <[email protected]> Date: Sun, 4 Mar 2012 21:24:49 +0200 Subject: [PATCH] flist: Avoid ABA-problem by using transaction tag in atomic operations --- src/pulsecore/flist.c | 146 +++++++++++++++++++++++++++++++++++++++++-------- 1 files changed, 122 insertions(+), 24 deletions(-) diff --git a/src/pulsecore/flist.c b/src/pulsecore/flist.c index d279271..b0e04f8 100644 --- a/src/pulsecore/flist.c +++ b/src/pulsecore/flist.c @@ -38,9 +38,36 @@ #define FLIST_SIZE 128 +#if __WORDSIZE == 64 + +typedef uint64_t pa_flist_idx_tag; +typedef uint32_t pa_flist_idx; +typedef uint32_t pa_flist_tag; + +#define FLIST_IDX_MASK ((pa_flist_idx_tag)0x00000000FFFFFFFF) +#define FLIST_TAG_MASK ((pa_flist_idx_tag)0xFFFFFFFF00000000) +#define FLIST_TAG_SHIFT 32 +#define FLIST_IDX_TAG_EMPTY ((pa_flist_idx_tag)0xFFFFFFFFFFFFFFFF) +#define FLIST_MAX_SIZE (UINT32_MAX-1) + +#else /* Assume 32 bit word size */ + +typedef uint32_t pa_flist_idx_tag; +typedef uint16_t pa_flist_idx; +typedef uint16_t pa_flist_tag; + +#define FLIST_IDX_MASK ((uint32_t)0x0000FFFF) +#define FLIST_TAG_MASK ((uint32_t)0xFFFF0000) +#define FLIST_TAG_SHIFT 16 +#define FLIST_IDX_TAG_EMPTY ((uint32_t)0xFFFFFFFF) +#define FLIST_MAX_SIZE (UINT16_MAX-1) + +#endif + /* Lock free single linked list element. */ struct pa_flist_elem { - pa_atomic_ptr_t next; + volatile pa_flist_idx_tag next_idx_tag; + volatile pa_flist_idx_tag my_idx_tag; pa_atomic_ptr_t ptr; }; @@ -50,39 +77,109 @@ struct pa_flist { const char *name; unsigned size; /* Stack that contains pointers stored into free list */ - pa_atomic_ptr_t stored; + volatile pa_flist_idx_tag stored; /* Stack that contains empty list elements */ - pa_atomic_ptr_t empty; + volatile pa_flist_idx_tag empty; pa_flist_elem table[]; }; +static pa_flist_idx idx_tag_get_idx(pa_flist_idx_tag idx_tag) { + return (pa_flist_idx) (FLIST_IDX_MASK & idx_tag); +} + +static pa_flist_tag idx_tag_get_tag(pa_flist_idx_tag idx_tag) { + return (pa_flist_tag) ((FLIST_TAG_MASK & idx_tag) >> FLIST_TAG_SHIFT); +} + +static pa_flist_idx_tag idx_tag_make(pa_flist_idx idx, pa_flist_tag tag) { + return (((pa_flist_idx_tag) tag << FLIST_TAG_SHIFT) | (pa_flist_idx_tag) idx); +} + +static pa_flist_idx_tag idx_tag_atomic_load(volatile pa_flist_idx_tag *idx_tag_ptr) { + return (pa_flist_idx_tag) pa_atomic_ptr_load((pa_atomic_ptr_t *) idx_tag_ptr); +} + +static void idx_tag_atomic_store(volatile pa_flist_idx_tag *idx_tag_ptr, + pa_flist_idx_tag idx_tag) { + pa_atomic_ptr_store((pa_atomic_ptr_t *) idx_tag_ptr, (void *) idx_tag); +} + +static pa_bool_t idx_tag_atomic_cmpxchg(volatile pa_flist_idx_tag *idx_tag_ptr, + pa_flist_idx_tag old, + pa_flist_idx_tag new) { + return pa_atomic_ptr_cmpxchg((pa_atomic_ptr_t *) idx_tag_ptr, + (void *) old, (void *) new); +} + +static pa_flist_elem *idx_tag_get_elem(pa_flist_elem *table, + pa_flist_idx_tag idx_tag) { + return &table[idx_tag_get_idx(idx_tag)]; +} + +static pa_flist_idx_tag idx_tag_get_next_idx_tag(pa_flist_elem *table, + pa_flist_idx_tag idx_tag) { + return idx_tag_atomic_load(&idx_tag_get_elem(table, idx_tag)->next_idx_tag); +} + +static pa_flist_idx_tag idx_tag_get_idx_tag(pa_flist_elem *table, + pa_flist_idx_tag idx_tag) { + return idx_tag_atomic_load(&idx_tag_get_elem(table, idx_tag)->my_idx_tag); +} + /* Lock free pop from linked list stack */ -static pa_flist_elem *stack_pop(pa_atomic_ptr_t *list) { - pa_flist_elem *poped; - pa_assert(list); +static pa_flist_elem *stack_pop(pa_flist_elem *table, + volatile pa_flist_idx_tag *list_head) { + pa_flist_idx_tag poped; + pa_assert(list_head); do { - poped = (pa_flist_elem *) pa_atomic_ptr_load(list); - } while (poped != NULL && !pa_atomic_ptr_cmpxchg(list, poped, pa_atomic_ptr_load(&poped->next))); + poped = idx_tag_atomic_load(list_head); + } while (poped != FLIST_IDX_TAG_EMPTY && + !idx_tag_atomic_cmpxchg(list_head, poped, + idx_tag_get_next_idx_tag(table, poped))); + + if (poped == FLIST_IDX_TAG_EMPTY) + return NULL; + + pa_assert(idx_tag_get_idx(idx_tag_get_idx_tag(table, poped)) == + (pa_flist_idx)(idx_tag_get_elem(table, poped) - table)); + pa_assert(idx_tag_get_idx_tag(table, poped) == poped); + + return idx_tag_get_elem(table, poped); +} + +static pa_flist_idx_tag idx_tag_elem_for_push(pa_flist_elem *elem, + pa_flist_idx_tag next) { + pa_flist_idx_tag idx_tag = idx_tag_atomic_load(&elem->my_idx_tag); + pa_flist_idx_tag new_idx_tag = idx_tag_make(idx_tag_get_idx(idx_tag), + idx_tag_get_tag(idx_tag)+1); + + idx_tag_atomic_store(&elem->my_idx_tag, new_idx_tag); + + idx_tag_atomic_store(&elem->next_idx_tag, next); - return poped; + return new_idx_tag; } /* Lock free push to linked list stack */ -static void stack_push(pa_atomic_ptr_t *list, pa_flist_elem *new_elem) { - pa_flist_elem *next; - pa_assert(list); +static void stack_push(pa_flist_elem *table, + volatile pa_flist_idx_tag *list_head, + pa_flist_elem *new_elem) { + pa_flist_idx_tag next; + pa_flist_idx_tag new_idx_tag; + pa_assert(list_head); do { - next = pa_atomic_ptr_load(list); - pa_atomic_ptr_store(&new_elem->next, next); - } while (!pa_atomic_ptr_cmpxchg(list, next, new_elem)); + next = idx_tag_atomic_load(list_head); + new_idx_tag = idx_tag_elem_for_push(new_elem, next); + } while (!idx_tag_atomic_cmpxchg(list_head, next, new_idx_tag)); } pa_flist *pa_flist_new_with_name(unsigned size, const char *name) { pa_flist *l; - unsigned i; + pa_flist_idx i; pa_assert(name); + pa_assert(size <= FLIST_MAX_SIZE); if (!size) size = FLIST_SIZE; @@ -91,10 +188,11 @@ pa_flist *pa_flist_new_with_name(unsigned size, const char *name) { l->name = pa_xstrdup(name); l->size = size; - pa_atomic_ptr_store(&l->stored, NULL); - pa_atomic_ptr_store(&l->empty, NULL); + idx_tag_atomic_store(&l->stored, FLIST_IDX_TAG_EMPTY); + idx_tag_atomic_store(&l->empty, FLIST_IDX_TAG_EMPTY); for (i=0; i < size; i++) { - stack_push(&l->empty, &l->table[i]); + idx_tag_atomic_store(&l->table[i].my_idx_tag, idx_tag_make(i, 0)); + stack_push(l->table, &l->empty, &l->table[i]); } return l; } @@ -109,7 +207,7 @@ void pa_flist_free(pa_flist *l, pa_free_cb_t free_cb) { if (free_cb) { pa_flist_elem *elem; - while((elem = stack_pop(&l->stored))) + while((elem = stack_pop(l->table, &l->stored))) free_cb(pa_atomic_ptr_load(&elem->ptr)); } @@ -122,14 +220,14 @@ int pa_flist_push(pa_flist *l, void *p) { pa_assert(l); pa_assert(p); - elem = stack_pop(&l->empty); + elem = stack_pop(l->table, &l->empty); if (elem == NULL) { if (pa_log_ratelimit(PA_LOG_DEBUG)) pa_log_debug("%s flist is full (don't worry)", l->name); return -1; } pa_atomic_ptr_store(&elem->ptr, p); - stack_push(&l->stored, elem); + stack_push(l->table, &l->stored, elem); return 0; } @@ -139,13 +237,13 @@ void* pa_flist_pop(pa_flist *l) { void *ptr; pa_assert(l); - elem = stack_pop(&l->stored); + elem = stack_pop(l->table, &l->stored); if (elem == NULL) return NULL; ptr = pa_atomic_ptr_load(&elem->ptr); - stack_push(&l->empty, elem); + stack_push(l->table, &l->empty, elem); return ptr; } -- 1.7.4.1
_______________________________________________ pulseaudio-discuss mailing list [email protected] http://lists.freedesktop.org/mailman/listinfo/pulseaudio-discuss
