File lockfree_freelist.hpp¶
File List > base > lockfree_freelist.hpp
Go to the documentation of this file
/*
* Copyright 2008 Search Solution Corporation
* Copyright 2016 CUBRID Corporation
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
*/
#ifndef _LOCKFREE_FREELIST_HPP_
#define _LOCKFREE_FREELIST_HPP_
#include "lockfree_transaction_def.hpp"
#include "lockfree_transaction_descriptor.hpp"
#include "lockfree_transaction_reclaimable.hpp"
#include "lockfree_transaction_table.hpp"
#include <atomic>
#include <cstddef>
namespace lockfree
{
namespace tran
{
class system;
}
}
namespace lockfree
{
// T must have on_reclaim function
template <class T>
class freelist
{
public:
class free_node;
freelist () = delete;
freelist (tran::system &transys, size_t block_size, size_t initial_block_count = 1);
~freelist ();
free_node *claim (tran::descriptor &tdes);
free_node *claim (tran::index tran_index); // claim a free node
// note: transaction will remain started!
void retire (tran::descriptor &tdes, free_node &node);
void retire (tran::index tran_index, free_node &node);
size_t get_alloc_count () const;
size_t get_available_count () const;
size_t get_backbuffer_count () const;
size_t get_forced_allocation_count () const;
size_t get_retired_count () const;
size_t get_claimed_count () const;
tran::system &get_transaction_system ();
tran::table &get_transaction_table ();
private:
tran::system &m_transys;
tran::table *m_trantable;
size_t m_block_size;
std::atomic<free_node *> m_available_list; // list of available entries
// backbuffer head & tail; when available list is consumed, it is quickly replaced with back-buffer; without
// backbuffer, multiple threads can race to allocate multiple blocks at once
std::atomic<free_node *> m_backbuffer_head;
std::atomic<free_node *> m_backbuffer_tail;
// statistics:
std::atomic<size_t> m_available_count;
std::atomic<size_t> m_alloc_count;
std::atomic<size_t> m_bb_count;
std::atomic<size_t> m_forced_alloc_count;
std::atomic<size_t> m_retired_count;
void swap_backbuffer ();
void alloc_backbuffer ();
void force_alloc_block ();
void alloc_list (free_node *&head, free_node *&tail);
void dealloc_list (free_node *head);
free_node *pop_from_available ();
void push_to_list (free_node &head, free_node &tail, std::atomic<free_node *> &dest);
void clear_free_nodes (); // not thread safe!
void final_sanity_checks () const;
void check_my_pointer (free_node *node);
};
template <class T>
class freelist<T>::free_node : public tran::reclaimable_node
{
public:
free_node ();
~free_node () = default;
T &get_data ();
void reclaim () final override;
private:
friend freelist;
void set_owner (freelist &m_freelist);
void set_freelist_next (free_node *next);
void reset_freelist_next (void);
free_node *get_freelist_next ();
freelist *m_owner;
T m_t;
};
} // namespace lockfree
//
// implementation
//
#include <cassert>
namespace lockfree
{
//
// freelist
//
template <class T>
freelist<T>::freelist (tran::system &transys, size_t block_size, size_t initial_block_count)
: m_transys (transys)
, m_trantable (new tran::table (transys))
, m_block_size (block_size)
, m_available_list { NULL }
, m_backbuffer_head { NULL }
, m_backbuffer_tail { NULL }
, m_available_count { 0 }
, m_alloc_count { 0 }
, m_bb_count { 0 }
, m_forced_alloc_count { 0 }
, m_retired_count { 0 }
{
assert (block_size > 1);
// minimum two blocks
if (initial_block_count <= 1)
{
m_block_size /= 2;
initial_block_count = 2;
}
alloc_backbuffer ();
for (size_t i = 0; i < initial_block_count; i++)
{
swap_backbuffer ();
}
}
template <class T>
void
freelist<T>::swap_backbuffer ()
{
free_node *bb_head = m_backbuffer_head;
if (bb_head == NULL)
{
// somebody already allocated block
return;
}
free_node *bb_head_copy = bb_head; // make sure a copy is passed to compare exchange
if (!m_backbuffer_head.compare_exchange_strong (bb_head_copy, NULL))
{
// somebody already changing it
return;
}
free_node *bb_tail = m_backbuffer_tail.exchange (NULL);
assert (bb_tail != NULL);
m_available_count += m_bb_count.exchange (0);
push_to_list (*bb_head, *bb_tail, m_available_list);
alloc_backbuffer ();
}
template <class T>
void
freelist<T>::alloc_backbuffer ()
{
free_node *new_bb_head = NULL;
free_node *new_bb_tail = NULL;
alloc_list (new_bb_head, new_bb_tail);
// update backbuffer tail
free_node *dummy_null = NULL;
m_backbuffer_tail.compare_exchange_strong (dummy_null, new_bb_tail);
// update backbuffer head
push_to_list (*new_bb_head, *new_bb_tail, m_backbuffer_head);
m_bb_count += m_block_size;
}
template <class T>
void
freelist<T>::force_alloc_block ()
{
free_node *new_head = NULL;
free_node *new_tail = NULL;
alloc_list (new_head, new_tail);
// push directly to available
m_available_count += m_block_size;
++m_forced_alloc_count;
push_to_list (*new_head, *new_tail, m_available_list);
}
template <class T>
void
freelist<T>::alloc_list (free_node *&head, free_node *&tail)
{
head = tail = NULL;
free_node *node;
for (size_t i = 0; i < m_block_size; i++)
{
node = new free_node ();
node->set_owner (*this);
if (tail == NULL)
{
tail = node;
}
node->set_freelist_next (head);
head = node;
}
m_alloc_count += m_block_size;
}
template <class T>
void
freelist<T>::dealloc_list (free_node *head)
{
// free all
free_node *save_next = NULL;
for (free_node *node = head; node != NULL; node = save_next)
{
save_next = node->get_freelist_next ();
delete node;
}
}
template <class T>
freelist<T>::~freelist ()
{
delete m_trantable;
clear_free_nodes ();
}
template <class T>
void
freelist<T>::clear_free_nodes ()
{
final_sanity_checks ();
// move back-buffer to available
dealloc_list (m_backbuffer_head.load ());
m_backbuffer_head = NULL;
m_backbuffer_tail = NULL;
dealloc_list (m_available_list.load ());
m_available_list = NULL;
m_available_count = m_bb_count = m_alloc_count = 0;
}
template<class T>
typename freelist<T>::free_node *
freelist<T>::claim (tran::index tran_index)
{
return claim (m_trantable->get_descriptor (tran_index));
}
template<class T>
typename freelist<T>::free_node *
freelist<T>::claim (tran::descriptor &tdes)
{
tdes.start_tran ();
tdes.reclaim_retired_list ();
free_node *node;
size_t count = 0;
for (node = pop_from_available (); node == NULL && count < 100; node = pop_from_available (), ++count)
{
// if it loops many times, it is probably because the back-buffer allocator was preempted for a very long time.
// force allocations
swap_backbuffer ();
}
// if swapping backbuffer didn't work (probably back-buffer allocator was preempted for a long time), force
// allocating directly into available list
while (node == NULL)
{
force_alloc_block ();
node = pop_from_available ();
}
assert (node != NULL);
assert (m_available_count > 0);
m_available_count--;
check_my_pointer (node);
return node;
}
template<class T>
typename freelist<T>::free_node *
freelist<T>::pop_from_available ()
{
free_node *rhead = NULL;
free_node *rhead_copy = NULL;
free_node *next;
do
{
rhead = m_available_list;
if (rhead == NULL)
{
return NULL;
}
next = rhead->get_freelist_next ();
rhead_copy = rhead;
// todo: this is a dangerous preemption point; if I am preempted here, and thread 2 comes and does:
// - second thread gets same rhead and successfully moves m_available_list to next
// - third thread gets next and successfully moves m_available_list to next->next
// - second thread retires rhead. m_available_list becomes rhead and its next becomes next->next
// - I wake up, compare exchange m_available_list successfully because it is rhead again, but next will
// become the item third thread already claimed.
}
while (!m_available_list.compare_exchange_weak (rhead_copy, next));
rhead->reset_freelist_next ();
return rhead;
}
template<class T>
void
freelist<T>::retire (tran::index tran_index, free_node &node)
{
retire (m_trantable->get_descriptor (tran_index), node);
}
template<class T>
void
freelist<T>::retire (tran::descriptor &tdes, free_node &node)
{
assert (node.get_freelist_next () == NULL);
++m_retired_count;
check_my_pointer (&node);
tdes.retire_node (node);
}
template<class T>
void
freelist<T>::push_to_list (free_node &head, free_node &tail, std::atomic<free_node *> &dest)
{
free_node *rhead;
assert (tail.get_freelist_next () == NULL);
do
{
rhead = dest;
tail.set_freelist_next (rhead);
}
while (!dest.compare_exchange_weak (rhead, &head));
}
template<class T>
size_t
freelist<T>::get_alloc_count () const
{
return m_alloc_count;
}
template<class T>
size_t
freelist<T>::get_available_count () const
{
return m_available_count;
}
template<class T>
size_t
freelist<T>::get_backbuffer_count () const
{
return m_bb_count;
}
template<class T>
size_t
freelist<T>::get_forced_allocation_count () const
{
return m_forced_alloc_count;
}
template<class T>
size_t
freelist<T>::get_retired_count () const
{
return m_retired_count;
}
template<class T>
size_t
freelist<T>::get_claimed_count () const
{
size_t alloc_count = m_alloc_count;
size_t unused_count = m_available_count + m_bb_count + m_retired_count;
if (alloc_count > unused_count)
{
return alloc_count - unused_count;
}
else
{
return 0;
}
}
template<class T>
tran::system &
freelist<T>::get_transaction_system ()
{
return m_transys;
}
template<class T>
tran::table &
freelist<T>::get_transaction_table ()
{
return *m_trantable;
}
template<class T>
void
freelist<T>::final_sanity_checks () const
{
#if !defined (NDEBUG)
assert (m_available_count + m_bb_count == m_alloc_count);
// check back-buffer
size_t list_count = 0;
free_node *save_last = NULL;
for (free_node *iter = m_backbuffer_head; iter != NULL; iter = iter->get_freelist_next ())
{
++list_count;
save_last = iter;
}
assert (list_count == m_bb_count);
assert (list_count == m_block_size);
assert (save_last == m_backbuffer_tail);
// check available
list_count = 0;
for (free_node *iter = m_available_list; iter != NULL; iter = iter->get_freelist_next ())
{
++list_count;
}
assert (list_count == m_available_count);
#endif // DEBUG
}
template<class T>
void
freelist<T>::check_my_pointer (free_node *node)
{
assert (this == node->m_owner);
}
//
// freelist::handle
//
template<class T>
freelist<T>::free_node::free_node ()
: tran::reclaimable_node ()
, m_owner (NULL)
, m_t {}
{
}
template<class T>
void
freelist<T>::free_node::set_owner (freelist &fl)
{
m_owner = &fl;
}
template<class T>
void
freelist<T>::free_node::set_freelist_next (free_node *next)
{
m_retired_next = next;
}
template<class T>
void
freelist<T>::free_node::reset_freelist_next ()
{
m_retired_next = NULL;
}
template<class T>
typename freelist<T>::free_node *
freelist<T>::free_node::get_freelist_next ()
{
return static_cast<free_node *> (m_retired_next);
}
template<class T>
void
freelist<T>::free_node::reclaim ()
{
m_t.on_reclaim ();
m_retired_next = NULL;
--m_owner->m_retired_count;
++m_owner->m_available_count;
m_owner->push_to_list (*this, *this, m_owner->m_available_list);
}
template<class T>
T &
freelist<T>::free_node::get_data ()
{
return m_t;
}
} // namespace lockfree
#endif // !_LOCKFREE_FREELIST_HPP_