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