code.vuplus.com Git - vuplus_xbmc/blob - xbmc/threads/LockFree.cpp

   1 /*
   2  *      Copyright (C) 2005-2013 Team XBMC
   3  *      http://xbmc.org
   4  *
   5  *  This Program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation; either version 2, or (at your option)
   8  *  any later version.
   9  *
  10  *  This Program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with XBMC; see the file COPYING.  If not, see
  17  *  <http://www.gnu.org/licenses/>.
  18  *
  19  */
  20
  21 #ifdef __ppc__
  22 #pragma GCC optimization_level 0
  23 #endif
  24
  25 #include "LockFree.h"
  26 #include <stdlib.h>
  27
  28 // oskwon :: cas/cas2, not implemented yet.
  29
  30 ///////////////////////////////////////////////////////////////////////////
  31 // Fast stack implementation
  32 // NOTE: non-locking only on systems that support atomic cas2 operations
  33 ///////////////////////////////////////////////////////////////////////////
  34 void lf_stack_init(lf_stack* pStack)
  35 {
  36   pStack->top.ptr = NULL;
  37   pStack->count = 0;
  38 }
  39
  40 void lf_stack_push(lf_stack* pStack, lf_node* pNode)
  41 {
  42   atomic_ptr top, newTop;
  43   do
  44   {
  45     top = pStack->top;
  46     pNode->next.ptr = top.ptr; // Link in the new node
  47     newTop.ptr = pNode;
  48 #if defined(__ppc__) || defined(__powerpc__) || defined(__arm__)
  49   } while(cas((long*)&pStack->top, atomic_ptr_to_long(top), atomic_ptr_to_long(newTop)) != atomic_ptr_to_long(top));
  50 #else
  51     newTop.version = top.version + 1;
  52   } while(cas2((long long*)&pStack->top, atomic_ptr_to_long_long(top), atomic_ptr_to_long_long(newTop)) != atomic_ptr_to_long_long(top));
  53 #endif
  54   AtomicIncrement(&pStack->count);
  55 }
  56
  57 lf_node* lf_stack_pop(lf_stack* pStack)
  58 {
  59   atomic_ptr top, newTop;
  60   do
  61   {
  62     top = pStack->top;
  63     if (top.ptr == NULL)
  64       return NULL;
  65     newTop.ptr = ((lf_node*)top.ptr)->next.ptr; // Unlink the current top node
  66 #if defined(__ppc__) || defined(__powerpc__) || defined(__arm__)
  67   } while(cas((long*)&pStack->top, atomic_ptr_to_long(top), atomic_ptr_to_long(newTop)) != atomic_ptr_to_long(top));
  68 #else
  69     newTop.version = top.version + 1;
  70   } while(cas2((long long*)&pStack->top, atomic_ptr_to_long_long(top), atomic_ptr_to_long_long(newTop)) != atomic_ptr_to_long_long(top));
  71 #endif
  72   AtomicDecrement(&pStack->count);
  73   return (lf_node*)top.ptr;
  74 }
  75
  76 ///////////////////////////////////////////////////////////////////////////
  77 // Fast heap implementation
  78 // NOTE: non-locking only on systems that support atomic cas2 operations
  79 ///////////////////////////////////////////////////////////////////////////
  80 // TODO: Implement auto-shrink based on chunk reference counts
  81
  82 // TODO: Read the page size from the OS or allow caller to specify
  83 // Maybe have a minimum number of blocks...
  84 #define MIN_ALLOC 4096
  85
  86 void lf_heap_init(lf_heap* pHeap, size_t blockSize, size_t initialSize /*= 0*/)
  87 {
  88   pHeap->alloc_lock = 0; // Initialize the allocation lock
  89   pHeap->top_chunk = NULL;
  90
  91   lf_stack_init(&pHeap->free_list); // Initialize the free-list stack
  92
  93   // Perform a few sanity checks on the parameters
  94   if (blockSize < sizeof(lf_node)) // Make sure we have blocks big enough to store in the free-list
  95     blockSize = sizeof(lf_node);
  96   pHeap->block_size = blockSize;
  97
  98   if (initialSize < 10 * blockSize)
  99     initialSize = 10 * blockSize; // TODO: This should be more intelligent
 100
 101   lf_heap_grow(pHeap, initialSize); // Allocate the first chunk
 102 }
 103
 104 void lf_heap_grow(lf_heap* pHeap, size_t size /*= 0*/)
 105 {
 106
 107   long blockSize = pHeap->block_size; // This has already been checked for sanity
 108   if (!size || size < MIN_ALLOC - sizeof(lf_heap_chunk)) // Allocate at least one page from the OS (TODO: Try valloc)
 109     size = MIN_ALLOC - sizeof(lf_heap_chunk);
 110   unsigned int blockCount = size / blockSize;
 111   if (size % blockSize) // maxe sure we have complete blocks
 112     size = blockSize * ++blockCount;
 113
 114   // Allocate the first chunk from the general heap and link it into the chunk list
 115   long mallocSize = size +  sizeof(lf_heap_chunk);
 116   lf_heap_chunk* pChunk = (lf_heap_chunk*) malloc(mallocSize);
 117   pChunk->size = mallocSize;
 118   SPINLOCK_ACQUIRE(pHeap->alloc_lock); // Lock the chunk list. Contention here is VERY unlikely, so use the simplest possible sync mechanism.
 119   pChunk->next = pHeap->top_chunk;
 120   pHeap->top_chunk = pChunk; // Link it into the list
 121   SPINLOCK_RELEASE(pHeap->alloc_lock); // The list is now consistent
 122
 123   // Add all blocks to the free-list
 124   unsigned char* pBlock = (unsigned char*)pChunk + sizeof(lf_heap_chunk);
 125   for ( unsigned int block = 0; block < blockCount; block++)
 126   {
 127     lf_stack_push(&pHeap->free_list, (lf_node*)pBlock);
 128     pBlock += blockSize;
 129   }
 130 }
 131
 132 void lf_heap_deinit(lf_heap* pHeap)
 133 {
 134   // Free all allocated chunks
 135   lf_heap_chunk* pNext;
 136   for(lf_heap_chunk* pChunk = pHeap->top_chunk; pChunk;  pChunk = pNext)
 137   {
 138     pNext = pChunk->next;
 139     free(pChunk);
 140   }
 141 }
 142
 143 void* lf_heap_alloc(lf_heap* pHeap)
 144 {
 145   void * p = lf_stack_pop(&pHeap->free_list);
 146   if (!p)
 147   {
 148     lf_heap_grow(pHeap, 0);
 149     // TODO: should we just call in recursively?
 150     return lf_stack_pop(&pHeap->free_list); // If growing didn't help, something is wrong (or someone else took them all REALLY fast)
 151   }
 152   return p;
 153 }
 154
 155 void lf_heap_free(lf_heap* pHeap, void* p)
 156 {
 157   if (!p) // Allow for NULL to pass safely
 158     return;
 159   lf_stack_push(&pHeap->free_list, (lf_node*)p); // Return the block to the free list
 160 }
 161
 162 ///////////////////////////////////////////////////////////////////////////
 163 // Lock-free queue
 164 ///////////////////////////////////////////////////////////////////////////
 165 void lf_queue_init(lf_queue* pQueue)
 166 {
 167   pQueue->len = 0;
 168   lf_heap_init(&pQueue->node_heap, sizeof(lf_queue_node)); // Intialize the node heap
 169   lf_queue_node* pNode = lf_queue_new_node(pQueue); // Create the 'empty' node
 170   pNode->next.ptr = NULL;
 171   pNode->value = (void*)0xdeadf00d;
 172   pQueue->head.ptr = pQueue->tail.ptr = pNode;
 173 }
 174
 175 void lf_queue_deinit(lf_queue* pQueue)
 176 {
 177   lf_heap_deinit(&pQueue->node_heap); // Clean up the node heap
 178 }
 179
 180 // TODO: template-ize
 181 void lf_queue_enqueue(lf_queue* pQueue, void* value)
 182 {
 183   lf_queue_node* pNode = lf_queue_new_node(pQueue); // Get a container
 184   pNode->value = value;
 185   pNode->next.ptr = NULL;
 186   atomic_ptr tail, next, node;
 187   do
 188   {
 189     tail = pQueue->tail;
 190     next = ((lf_queue_node*)tail.ptr)->next;
 191 #if defined(__ppc__) || defined(__powerpc__) || defined(__arm__)
 192     if (atomic_ptr_to_long(tail) == atomic_ptr_to_long(pQueue->tail)) // Check consistency
 193 #else
 194     if (atomic_ptr_to_long_long(tail) == atomic_ptr_to_long_long(pQueue->tail)) // Check consistency
 195 #endif
 196     {
 197       if (next.ptr == NULL) // Was tail pointing to the last node?
 198       {
 199         node.ptr = pNode;
 200 #if defined(__ppc__) || defined(__powerpc__) || defined(__arm__)
 201         if (cas((long*)&((lf_queue_node*)tail.ptr)->next, atomic_ptr_to_long(next), atomic_ptr_to_long(node)) == atomic_ptr_to_long(next)) // Try to link node at end
 202 #else
 203         node.version = next.version + 1;
 204         if (cas2((long long*)&((lf_queue_node*)tail.ptr)->next, atomic_ptr_to_long_long(next), atomic_ptr_to_long_long(node)) == atomic_ptr_to_long_long(next)) // Try to link node at end
 205 #endif
 206           break; // enqueue is done.
 207       }
 208       else // tail was lagging, try to help...
 209       {
 210         node.ptr = next.ptr;
 211 #if defined(__ppc__) || defined(__powerpc__) || defined(__arm__)
 212         cas((long*)&pQueue->tail, atomic_ptr_to_long(tail), atomic_ptr_to_long(node)); // We don't care if we  are successful or not
 213 #else
 214         node.version = tail.version + 1;
 215         cas2((long long*)&pQueue->tail, atomic_ptr_to_long_long(tail), atomic_ptr_to_long_long(node)); // We don't care if we  are successful or not
 216 #endif
 217       }
 218     }
 219   } while (true); // Keep trying until the enqueue is done
 220   node.ptr = pNode;
 221 #if defined(__ppc__) || defined(__powerpc__) || defined(__arm__)
 222   cas((long*)&pQueue->tail, atomic_ptr_to_long(tail), atomic_ptr_to_long(node)); // Try to swing the tail to the new node
 223 #else
 224   node.version = tail.version + 1;
 225   cas2((long long*)&pQueue->tail, atomic_ptr_to_long_long(tail), atomic_ptr_to_long_long(node)); // Try to swing the tail to the new node
 226 #endif
 227   AtomicIncrement(&pQueue->len);
 228 }
 229
 230 // TODO: template-ize
 231 void* lf_queue_dequeue(lf_queue* pQueue)
 232 {
 233   atomic_ptr head, tail, next, node;
 234   void* pVal = NULL;
 235   do
 236   {
 237     head = pQueue->head;
 238     tail = pQueue->tail;
 239     next = ((lf_queue_node*)head.ptr)->next;
 240 #if defined(__ppc__) || defined(__powerpc__) || defined(__arm__)
 241     if (atomic_ptr_to_long(head) == atomic_ptr_to_long(pQueue->head)) // Check consistency
 242 #else
 243     if (atomic_ptr_to_long_long(head) == atomic_ptr_to_long_long(pQueue->head)) // Check consistency
 244 #endif
 245     {
 246       if (head.ptr == tail.ptr) // Queue is empty or tail is lagging
 247       {
 248         if (next.ptr == NULL) // Queue is empty
 249           return NULL;
 250         node.ptr = next.ptr;
 251 #if defined(__ppc__) || defined(__powerpc__) || defined(__arm__)
 252         cas((long*)&pQueue->tail, atomic_ptr_to_long(tail), atomic_ptr_to_long(node)); // Tail is lagging. Try to advance it.
 253 #else
 254         node.version = tail.version + 1;
 255         cas2((long long*)&pQueue->tail, atomic_ptr_to_long_long(tail), atomic_ptr_to_long_long(node)); // Tail is lagging. Try to advance it.
 256 #endif
 257       }
 258       else // Tail is consistent. No need to deal with it.
 259       {
 260         pVal = ((lf_queue_node*)next.ptr)->value;
 261         node.ptr = next.ptr;
 262 #if defined(__ppc__) || defined(__powerpc__) || defined(__arm__)
 263         if (cas((long*)&pQueue->head, atomic_ptr_to_long(head), atomic_ptr_to_long(node)) == atomic_ptr_to_long(head))
 264 #else
 265         node.version = head.version + 1;
 266         if (cas2((long long*)&pQueue->head, atomic_ptr_to_long_long(head), atomic_ptr_to_long_long(node)) == atomic_ptr_to_long_long(head))
 267 #endif
 268           break; // Dequeue is done
 269       }
 270     }
 271   } while (true); // Keep trying until the dequeue is done or the queue empties
 272   lf_queue_free_node(pQueue, head.ptr);
 273   AtomicDecrement(&pQueue->len);
 274   return pVal;
 275 }
 276
 277 #ifdef __ppc__
 278 #pragma GCC optimization_level reset
 279 #endif