[pulseaudio-commits] 2 commits - src/pulsecore

[Tanu Kaskinen]

 src/pulsecore/flist.c |   74 ++++++++++++++++++++++++++++++++++----------------
 1 file changed, 51 insertions(+), 23 deletions(-)

New commits:
commit 25c73a00c405c74532fe05b6b59467c8c8adabb3
Author: Tanu Kaskinen <tanuk at iki.fi>
Date:   Wed Mar 7 09:39:18 2012 +0200

    flist: Make name non-const to avoid casting with pa_xfree().

diff --git a/src/pulsecore/flist.c b/src/pulsecore/flist.c
index fa8974a..0aa95c7 100644
--- a/src/pulsecore/flist.c
+++ b/src/pulsecore/flist.c
@@ -54,7 +54,7 @@ struct pa_flist_elem {
 typedef struct pa_flist_elem pa_flist_elem;
 
 struct pa_flist {
-    const char *name;
+    char *name;
     unsigned size;
 
     pa_atomic_t current_tag;
@@ -141,7 +141,7 @@ void pa_flist_free(pa_flist *l, pa_free_cb_t free_cb) {
             free_cb(pa_atomic_ptr_load(&elem->ptr));
     }
 
-    pa_xfree((char *) l->name);
+    pa_xfree(l->name);
     pa_xfree(l);
 }
 

commit 641103314a423328094624db0f518630d5d90dee
Author: David Henningsson <david.henningsson at canonical.com>
Date:   Sun Mar 4 06:07:37 2012 +0100

    flist: Avoid the ABA problem
    
    Our flist implementation suffers from the ABA problem
    (see http://en.wikipedia.org/wiki/ABA_problem), causing PulseAudio
    to crash very rarely, usually inside memblock operations.
    By turning stored pointers into stored table indices, we have some
    extra bits that we can use to store tag bits, which is a known
    workaround for the ABA problem.
    
    Buglink: https://bugs.launchpad.net/bugs/924416
    Signed-off-by: David Henningsson <david.henningsson at canonical.com>

diff --git a/src/pulsecore/flist.c b/src/pulsecore/flist.c
index d279271..fa8974a 100644
--- a/src/pulsecore/flist.c
+++ b/src/pulsecore/flist.c
@@ -3,6 +3,7 @@
 
   Copyright 2006-2008 Lennart Poettering
   Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+  Copyright (C) 2012 Canonical Ltd.
 
   Contact: Jyri Sarha <Jyri.Sarha at nokia.com>
 
@@ -38,9 +39,15 @@
 
 #define FLIST_SIZE 128
 
+/* Atomic table indices contain
+   sign bit = if set, indicates empty/NULL value
+   tag bits (to avoid the ABA problem)
+   actual index bits
+*/
+
 /* Lock free single linked list element. */
 struct pa_flist_elem {
-    pa_atomic_ptr_t next;
+    pa_atomic_t next;
     pa_atomic_ptr_t ptr;
 };
 
@@ -49,34 +56,49 @@ typedef struct pa_flist_elem pa_flist_elem;
 struct pa_flist {
     const char *name;
     unsigned size;
+
+    pa_atomic_t current_tag;
+    int index_mask;
+    int tag_shift;
+    int tag_mask;
+
     /* Stack that contains pointers stored into free list */
-    pa_atomic_ptr_t stored;
+    pa_atomic_t stored;
     /* Stack that contains empty list elements */
-    pa_atomic_ptr_t empty;
+    pa_atomic_t empty;
     pa_flist_elem table[];
 };
 
 /* Lock free pop from linked list stack */
-static pa_flist_elem *stack_pop(pa_atomic_ptr_t *list) {
-    pa_flist_elem *poped;
+static pa_flist_elem *stack_pop(pa_flist *flist, pa_atomic_t *list) {
+    pa_flist_elem *popped;
+    int idx;
     pa_assert(list);
 
     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)));
+        idx = pa_atomic_load(list);
+        if (idx < 0)
+            return NULL;
+        popped = &flist->table[idx & flist->index_mask];
+    } while (!pa_atomic_cmpxchg(list, idx, pa_atomic_load(&popped->next)));
 
-    return poped;
+    return popped;
 }
 
 /* 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;
+static void stack_push(pa_flist *flist, pa_atomic_t *list, pa_flist_elem *new_elem) {
+    int tag, newindex, next;
     pa_assert(list);
 
+    tag = pa_atomic_inc(&flist->current_tag);
+    newindex = new_elem - flist->table;
+    pa_assert(newindex >= 0 && newindex < (int) flist->size);
+    newindex |= (tag << flist->tag_shift) & flist->tag_mask;
+
     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 = pa_atomic_load(list);
+        pa_atomic_store(&new_elem->next, next);
+    } while (!pa_atomic_cmpxchg(list, next, newindex));
 }
 
 pa_flist *pa_flist_new_with_name(unsigned size, const char *name) {
@@ -91,10 +113,16 @@ 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);
+
+    while (1 << l->tag_shift < (int) size)
+        l->tag_shift++;
+    l->index_mask = (1 << l->tag_shift) - 1;
+    l->tag_mask = INT_MAX - l->index_mask;
+
+    pa_atomic_store(&l->stored, -1);
+    pa_atomic_store(&l->empty, -1);
     for (i=0; i < size; i++) {
-        stack_push(&l->empty, &l->table[i]);
+        stack_push(l, &l->empty, &l->table[i]);
     }
     return l;
 }
@@ -109,7 +137,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, &l->stored)))
             free_cb(pa_atomic_ptr_load(&elem->ptr));
     }
 
@@ -122,14 +150,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, &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, &l->stored, elem);
 
     return 0;
 }
@@ -139,13 +167,13 @@ void* pa_flist_pop(pa_flist *l) {
     void *ptr;
     pa_assert(l);
 
-    elem = stack_pop(&l->stored);
+    elem = stack_pop(l, &l->stored);
     if (elem == NULL)
         return NULL;
 
     ptr = pa_atomic_ptr_load(&elem->ptr);
 
-    stack_push(&l->empty, elem);
+    stack_push(l, &l->empty, elem);
 
     return ptr;
 }