free_list.cpp
Go to the documentation of this file.
00001 
00002 /*********************************************************************
00003 * Software License Agreement (BSD License)
00004 *
00005 *  Copyright (c) 2010, Willow Garage, Inc.
00006 *  All rights reserved.
00007 *
00008 *  Redistribution and use in source and binary forms, with or without
00009 *  modification, are permitted provided that the following conditions
00010 *  are met:
00011 *
00012 *   * Redistributions of source code must retain the above copyright
00013 *     notice, this list of conditions and the following disclaimer.
00014 *   * Redistributions in binary form must reproduce the above
00015 *     copyright notice, this list of conditions and the following
00016 *     disclaimer in the documentation and/or other materials provided
00017 *     with the distribution.
00018 *   * Neither the name of the Willow Garage nor the names of its
00019 *     contributors may be used to endorse or promote products derived
00020 *     from this software without specific prior written permission.
00021 *
00022 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00023 *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00024 *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
00025 *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
00026 *  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
00027 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
00028 *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00029 *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
00030 *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00031 *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
00032 *  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00033 *  POSSIBILITY OF SUCH DAMAGE.
00034 *********************************************************************/
00035 
00036 #include <lockfree/free_list.h>
00037 #include <allocators/aligned.h>
00038 
00039 using namespace ros;
00040 
00041 namespace lockfree
00042 {
00043 
00044 FreeList::FreeList()
00045 : blocks_(0)
00046 , next_(0)
00047 , block_size_(0)
00048 , block_count_(0)
00049 {
00050 }
00051 
00052 FreeList::FreeList(uint32_t block_size, uint32_t block_count)
00053 : blocks_(0)
00054 , next_(0)
00055 , block_size_(0)
00056 , block_count_(0)
00057 {
00058   initialize(block_size, block_count);
00059 }
00060 
00061 FreeList::~FreeList()
00062 {
00063   for (uint32_t i = 0; i < block_count_; ++i)
00064   {
00065     next_[i].~atomic_uint32_t();
00066   }
00067 
00068   allocators::alignedFree(blocks_);
00069   allocators::alignedFree(next_);
00070 }
00071 
00072 void FreeList::initialize(uint32_t block_size, uint32_t block_count)
00073 {
00074   ROS_ASSERT(!blocks_);
00075   ROS_ASSERT(!next_);
00076 
00077   block_size_ = block_size;
00078   block_count_ = block_count;
00079 
00080   head_.store(0);
00081   alloc_count_.store(0);
00082 
00083   blocks_ = (uint8_t*)allocators::alignedMalloc(block_size * block_count, ROSRT_CACHELINE_SIZE);
00084   next_ = (atomic_uint32_t*)allocators::alignedMalloc(sizeof(atomic_uint32_t) * block_count, ROSRT_CACHELINE_SIZE);
00085 
00086   memset(blocks_, 0xCD, block_size * block_count);
00087 
00088   for (uint32_t i = 0; i < block_count_; ++i)
00089   {
00090     new (next_ + i) atomic_uint32_t();
00091 
00092     if (i == block_count_ - 1)
00093     {
00094       next_[i].store(0xffffffffUL);
00095     }
00096     else
00097     {
00098       next_[i].store(i + 1);
00099     }
00100   }
00101 }
00102 
00103 bool FreeList::hasOutstandingAllocations()
00104 {
00105   return alloc_count_.load() == 0;
00106 }
00107 
00108 void* FreeList::allocate()
00109 {
00110 #if FREE_LIST_DEBUG
00111   initDebug();
00112 #endif
00113 
00114   ROS_ASSERT(blocks_);
00115 
00116   while (true)
00117   {
00118     uint64_t head = head_.load(memory_order_consume);
00119 
00120 #if FREE_LIST_DEBUG
00121     typename Debug::Item i;
00122     i.head = head;
00123     i.time = ros::WallTime::now();
00124     i.op = Debug::Alloc;
00125 #endif
00126 
00127     if (getVal(head) == 0xffffffffULL)
00128     {
00129 #if FREE_LIST_DEBUG
00130       debug_->items.push_back(i);
00131 #endif
00132       return 0;  // Allocation failed
00133     }
00134 
00135     FREELIST_DEBUG_YIELD();
00136 
00137     // Load the next index
00138     uint64_t new_head = next_[getVal(head)].load();
00139 
00140     FREELIST_DEBUG_YIELD();
00141 
00142     // Increment the tag to avoid ABA
00143     setTag(new_head, getTag(head) + 1);
00144 
00145 #if FREE_LIST_DEBUG
00146     i.new_head = new_head;
00147 #endif
00148 
00149     FREELIST_DEBUG_YIELD();
00150 
00151     // If setting head to next is successful, return the item at next
00152     if (head_.compare_exchange_strong(head, new_head))
00153     {
00154 #if FREE_LIST_DEBUG
00155       i.addr = blocks_ + (block_size_ * getVal(head));
00156       i.success = 1;
00157       debug_->items.push_back(i);
00158 #endif
00159       alloc_count_.fetch_add(1);
00160       return static_cast<void*>(blocks_ + (block_size_ * getVal(head)));
00161     }
00162 
00163 #if FREE_LIST_DEBUG
00164       i.success = 0;
00165       debug_->items.push_back(i);
00166 #endif
00167   }
00168 }
00169 
00170 void FreeList::free(void const* mem)
00171 {
00172   if (!mem)
00173   {
00174     return;
00175   }
00176 
00177 #if FREE_LIST_DEBUG
00178   initDebug();
00179 #endif
00180 
00181   uint32_t index = (static_cast<uint8_t const*>(mem) - blocks_) / block_size_;
00182 
00183   ROS_ASSERT(((static_cast<uint8_t const*>(mem) - blocks_) % block_size_) == 0);
00184   ROS_ASSERT(owns(mem));
00185 
00186   while (true)
00187   {
00188     // Load head
00189     uint64_t head = head_.load(memory_order_consume);
00190 
00191 #if FREE_LIST_DEBUG
00192     typename Debug::Item i;
00193     i.head = head;
00194     i.time = ros::WallTime::now();
00195     i.op = Debug::Free;
00196 #endif
00197 
00198     FREELIST_DEBUG_YIELD();
00199 
00200     uint64_t new_head = head;
00201     // set new head to the index of the block we're currently freeing
00202     setVal(new_head, index);
00203     // Increment the tag to avoid ABA
00204     setTag(new_head, getTag(new_head) + 1);
00205 
00206 
00207     FREELIST_DEBUG_YIELD();
00208 
00209     // Store head as next index for this item
00210     next_[index].store(getVal(head));
00211 
00212     FREELIST_DEBUG_YIELD();
00213 
00214 #if FREE_LIST_DEBUG
00215     i.new_head = new_head;
00216 #endif
00217 
00218     FREELIST_DEBUG_YIELD();
00219 
00220     // If setting the head to next is successful, return
00221     if (head_.compare_exchange_strong(head, new_head))
00222     {
00223 #if FREE_LIST_DEBUG
00224       i.success = 1;
00225       i.addr = blocks_ + (block_size_ * index);
00226       debug_->items.push_back(i);
00227 #endif
00228       alloc_count_.fetch_sub(1);
00229       return;
00230     }
00231 
00232 #if FREE_LIST_DEBUG
00233       i.success = 0;
00234       debug_->items.push_back(i);
00235 #endif
00236   }
00237 }
00238 
00239 bool FreeList::owns(void const* mem)
00240 {
00241   uint32_t sub = (static_cast<uint8_t const*>(mem) - blocks_);
00242   return sub < block_count_ * block_size_;
00243 }
00244 
00245 } // namespace lockfree
00246 


lockfree
Author(s): Josh Faust
autogenerated on Wed Aug 26 2015 16:00:00