dotgnu-pnet-commits
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[dotgnu-pnet-commits] [SCM] DotGNU Portable.NET engine, compilers and to


From: Klaus Treichel
Subject: [dotgnu-pnet-commits] [SCM] DotGNU Portable.NET engine, compilers and tools (pnet) branch, master, updated. 00944635fd6fc8748b054ad88900bdb046b1b738
Date: Mon, 08 Mar 2010 20:07:42 +0000

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "DotGNU Portable.NET engine, compilers and tools (pnet)".

The branch, master has been updated
       via  00944635fd6fc8748b054ad88900bdb046b1b738 (commit)
      from  3a9368ed8150c88166142d107781256a98ab0061 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
http://git.savannah.gnu.org/cgit/pnet.git/commit/?id=00944635fd6fc8748b054ad88900bdb046b1b738

commit 00944635fd6fc8748b054ad88900bdb046b1b738
Author: Klaus Treichel <address@hidden>
Date:   Mon Mar 8 21:07:15 2010 +0100

    Add a lock free single linked list implementation.

diff --git a/ChangeLog b/ChangeLog
index 9b412ab..44e0933 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2010-03-06  Klaus Treichel  <address@hidden>
+
+       * support/interlocked_slist.c, support/interlocked_slist.h: Add a
+       lock free single linked list implementation.
+
+       * support/Makefile.am: Add interlocked_slist.c and interlocked_slist.h
+       to the sources.
+
+       * tests/test_thread.c: Add tests for the interlocked slist.
+ 
 2010-02-21  Klaus Treichel  <address@hidden>
 
        * support/monitor.c: Replace the single list of monitors by one with
diff --git a/support/Makefile.am b/support/Makefile.am
index b97ebee..76d3e07 100644
--- a/support/Makefile.am
+++ b/support/Makefile.am
@@ -37,6 +37,8 @@ libILSupport_a_SOURCES = aes.c \
                                                 interlocked_arm.h \
                                                 interlocked_ppc.h \
                                                 interlocked_x86.h \
+                                                interlocked_slist.c \
+                                                interlocked_slist.h \
                                                 intern.c \
                                                 interrupt.c \
                                                 interrupt.h \
diff --git a/support/interlocked_slist.c b/support/interlocked_slist.c
new file mode 100644
index 0000000..b8e0eae
--- /dev/null
+++ b/support/interlocked_slist.c
@@ -0,0 +1,97 @@
+/*
+ * interlocked_slist.c - Implementation for a lock free single linked list.
+ *
+ * Copyright (C) 2010  Southern Storm Software, Pty Ltd.
+ *
+ * Authors: Klaus Treichel (address@hidden)
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include "thr_defs.h"
+#include "interlocked_slist.h"
+
+void ILInterlockedSListAppend(ILInterlockedSListHead *head,
+                                                         
ILInterlockedSListElement *elem)
+{
+       ILInterlockedSListElement *tail;
+       ILInterlockedSListElement *prev_tail;
+
+       IL_THREAD_ASSERT(head != 0);
+       IL_THREAD_ASSERT(elem != 0);
+
+       tail = &(head->tail);
+       elem->next = &(head->tail);
+       /* Exchange the current tail with the element to append. */
+       prev_tail = (ILInterlockedSListElement 
*)ILInterlockedExchangeP_Acquire((void **)&(tail->next), elem);
+       /* set the next pointer of the previous tail to the new element */
+       prev_tail->next = elem;
+       /* and make sure this is seen by all other threads */
+       ILInterlockedMemoryBarrier();
+}
+
+void *ILInterlockedSListGet(ILInterlockedSListHead *head)
+{
+       ILInterlockedSListElement *tail;
+
+       IL_THREAD_ASSERT(head != 0);
+
+       tail = &(head->tail);
+       do
+       {
+               ILInterlockedSListElement *prev_head;
+
+               prev_head = (ILInterlockedSListElement 
*)ILInterlockedLoadP((void **)&(head->head.next));
+               if(prev_head != tail)
+               {
+                       ILInterlockedSListElement *next_head;
+
+                       next_head = (ILInterlockedSListElement 
*)ILInterlockedLoadP((void **)&(prev_head->next));
+                       if(ILInterlockedCompareAndExchangeP_Acquire((void 
**)&(head->head.next), next_head, prev_head) == prev_head)
+                       {
+                               /*
+                                * We removed the head element successfully.
+                                */
+                               if(next_head == tail)
+                               {
+                                       /*
+                                        * The list is empty from the head's 
point of view.
+                                        * So try to reset the tail to the 
list's head.
+                                        */
+                                       
if(ILInterlockedCompareAndExchangeP_Acquire((void **)&(tail->next), 
&(head->head), prev_head) != prev_head)
+                                       {
+                                               /*
+                                                * We have to wait until the 
next pointer is set accordingly.
+                                                */
+                                               do
+                                               {
+                                                       _ILThreadYield();
+                                                       next_head = 
(ILInterlockedSListElement *)ILInterlockedLoadP((void **)&(prev_head->next));
+                                               } while(next_head == tail);
+                                               
ILInterlockedStoreP_Acquire((void **)&(head->head.next), next_head);
+                                       }
+                               }
+                               return prev_head;
+                       }
+               }
+               else
+               {
+                       /* The list is empty */
+                       return 0;
+               }
+               
+       } while(1);
+       return 0;
+}
diff --git a/support/interlocked_slist.h b/support/interlocked_slist.h
new file mode 100644
index 0000000..7f4975a
--- /dev/null
+++ b/support/interlocked_slist.h
@@ -0,0 +1,75 @@
+/*
+ * interlocked_slist.h - Declarations for a lock free single linked list.
+ *
+ * Copyright (C) 2010  Southern Storm Software, Pty Ltd.
+ *
+ * Authors: Klaus Treichel (address@hidden)
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#ifndef _INTERLOCKED_SLIST_H_
+#define _INTERLOCKED_SLIST_H_
+
+#include "interlocked.h"
+
+/*
+ * Semantics:
+ */
+
+typedef struct _tagILInterlockedSListHead ILInterlockedSListHead;
+typedef struct _tagILInterlockedSListElement ILInterlockedSListElement;
+struct _tagILInterlockedSListElement
+{
+       void   *next;   /* Really an ILInterlockedSListElement */
+};
+
+struct _tagILInterlockedSListHead
+{
+       ILInterlockedSListElement       head;
+       ILInterlockedSListElement       tail;
+};
+
+static IL_INLINE void ILInterlockedSListHead_Init(ILInterlockedSListHead *head)
+{
+       head->head.next = &(head->tail);
+       head->tail.next = &(head->head);
+}
+
+static IL_INLINE int ILInterlockedSList_IsEmpty(ILInterlockedSListHead *head)
+{
+       return (ILInterlockedLoadP(&(head->head.next)) == (void 
*)&(head->tail));
+}
+
+static IL_INLINE int ILInterlockedSList_IsClean(ILInterlockedSListHead *head)
+{
+       return ((ILInterlockedLoadP(&(head->head.next)) == (void 
*)&(head->tail)) &&
+                       (ILInterlockedLoadP(&(head->tail.next)) == (void 
*)&(head->head)));
+}
+
+/*
+ * Append an element to the single linked list.
+ */
+void ILInterlockedSListAppend(ILInterlockedSListHead *head,
+                                                         
ILInterlockedSListElement *elem);
+
+/*
+ * Get the head element of the single linked list and remove it from the list.
+ * The pointer returned is a pointer to the ILInterlockedSListElement removed.
+ * Returns 0 if the list is empty.
+ */
+void *ILInterlockedSListGet(ILInterlockedSListHead *head);
+
+#endif /* _INTERLOCKED_SLIST_H_ */
diff --git a/tests/test_thread.c b/tests/test_thread.c
index 9f0a479..3cb8cf0 100755
--- a/tests/test_thread.c
+++ b/tests/test_thread.c
@@ -21,6 +21,7 @@
 #include "ilunit.h"
 #include "../support/thr_defs.h"
 #include "../support/interlocked.h"
+#include "../support/interlocked_slist.h"
 #include "il_thread.h"
 #include "il_gc.h"
 #if HAVE_UNISTD_H
@@ -1566,6 +1567,141 @@ static void interlocked_thrash_addsub(void *arg)
        }
 }
 
+static void interlocked_slist_create(void *arg)
+{
+       ILInterlockedSListHead head;
+
+       ILInterlockedSListHead_Init(&head);
+
+       if(!ILInterlockedSList_IsClean(&head))
+       {
+               ILUnitFailed("List is not clean after creation.\n");
+       }
+}
+
+static void interlocked_slist_add_rem_single(void *arg)
+{
+       ILInterlockedSListHead head;
+       ILInterlockedSListElement elem;
+       ILInterlockedSListElement *rem_elem;
+
+       ILInterlockedSListHead_Init(&head);
+
+       ILInterlockedSListAppend(&head, &elem);
+
+       rem_elem = (ILInterlockedSListElement *)ILInterlockedSListGet(&head);
+
+       if(rem_elem != &elem)
+       {
+               ILUnitFailed("The element removed from the list doesn't match 
the added element.\n");
+       }
+
+       if(!ILInterlockedSList_IsClean(&head))
+       {
+               ILUnitFailed("List is not clean after removing the element.\n");
+       }
+}
+
+#define SLIST_ITERATIONS 1000000
+
+static void _interlocked_slist_append_thrash(void *arg)
+{
+       ILInterlockedSListHead *head = (ILInterlockedSListHead *)arg;
+       int i;
+
+       for(i = 0; i < SLIST_ITERATIONS; ++i)
+       {
+               ILInterlockedSListElement *elem;
+
+               elem = (ILInterlockedSListElement 
*)malloc(sizeof(ILInterlockedSListElement));
+               if(elem == 0)
+               {
+                       ILUnitOutOfMemory();
+               }
+               ILInterlockedSListAppend(head, elem);
+       }
+}
+
+static void _interlocked_slist_get_thrash(void *arg)
+{
+       ILInterlockedSListHead *head = (ILInterlockedSListHead *)arg;
+       int i;
+
+       i = 0;
+       while(i < SLIST_ITERATIONS)
+       {
+               ILInterlockedSListElement *elem;
+
+               elem = (ILInterlockedSListElement *)ILInterlockedSListGet(head);
+               if(elem)
+               {
+                       ++i;
+                       free(elem);
+               }
+       }
+}
+
+static void interlocked_slist_add_rem_thrash(void *arg)
+{
+       ILInterlockedSListHead head;
+       ILThread *thread[8];
+       int joinResults[8];
+       int i;
+       int haveError = 0;
+
+       ILInterlockedSListHead_Init(&head);
+
+       for(i = 0; i < 4; ++i)
+       {
+               thread[i] = ILThreadCreate(_interlocked_slist_append_thrash, 
&head);
+               if(!thread[i])
+               {
+                       ILUnitOutOfMemory();
+               }
+       }
+
+       for(i = 4; i < 8; ++i)
+       {
+               thread[i] = ILThreadCreate(_interlocked_slist_get_thrash, 
&head);
+               if(!thread[i])
+               {
+                       ILUnitOutOfMemory();
+               }
+       }
+
+       /* Start the threads */
+       for(i = 0; i < 4; ++i)
+       {
+               ILThreadStart(thread[i]);
+               ILThreadStart(thread[4 + i]);
+       }
+
+       /* Wait for the threads to finish */
+       for(i = 0; i < 8; ++i)
+       {
+               joinResults[i] = ILThreadJoin(thread[i], 30000);
+       }
+
+       for(i = 0; i < 8; ++i)
+       {
+               if(joinResults[i] != IL_JOIN_OK)
+               {
+                       haveError = 1;
+                       ILUnitFailMessage("Failed to join thread[%i] with 
returncode %i", i, joinResults[i]);
+               }
+               /* Destroy the thread object */
+               ILThreadDestroy(thread[i]);
+       }
+       if(haveError)
+       {
+               ILUnitFailEndMessages();
+       }
+       else if(!ILInterlockedSList_IsClean(&head))
+       {
+               ILUnitFailed("List is not clean after running the test.\n");
+       }
+}
+
 /*
  * Test wait mutex creation.
  */
@@ -3451,6 +3587,15 @@ void ILUnitRegisterTests(void)
        RegisterSimple(interlocked_thrash_addsub);
 
        /*
+        * Test the interlocked single linked list operations.
+        */
+       ILUnitRegisterSuite("Interlocked single linked list operations");
+       RegisterSimple(interlocked_slist_create);
+       RegisterSimple(interlocked_slist_add_rem_single);
+       RegisterSimple(interlocked_slist_add_rem_thrash);
+
+       
+       /*
         * Test wait mutex behaviours.
         */
        ILUnitRegisterSuite("Wait Mutex Tests");

-----------------------------------------------------------------------

Summary of changes:
 ChangeLog                   |   10 +++
 support/Makefile.am         |    2 +
 support/interlocked_slist.c |   97 +++++++++++++++++++++++++++++
 support/interlocked_slist.h |   75 ++++++++++++++++++++++
 tests/test_thread.c         |  145 +++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 329 insertions(+), 0 deletions(-)
 create mode 100644 support/interlocked_slist.c
 create mode 100644 support/interlocked_slist.h


hooks/post-receive
-- 
DotGNU Portable.NET engine, compilers and tools (pnet)




reply via email to

[Prev in Thread] Current Thread [Next in Thread]