src/common/urcu.hpp

   1 /*
   2  * Copyright (C) 2022 Jérémie Galarneau <jeremie.galarneau@efficios.com>
   3  *
   4  * SPDX-License-Identifier: LGPL-2.1-only
   5  *
   6  */
   7
   8 #ifndef LTTNG_URCU_H
   9 #define LTTNG_URCU_H
  10
  11 #define _LGPL_SOURCE
  12 #include <common/exception.hpp>
  13 #include <common/hashtable/hashtable.hpp>
  14 #include <common/macros.hpp>
  15
  16 #include <iterator>
  17 #include <mutex>
  18 #include <urcu.h>
  19 #include <urcu/list.h>
  20 #include <urcu/rculfhash.h>
  21
  22 namespace lttng {
  23 namespace urcu {
  24
  25 namespace details {
  26 /*
  27  * Wrapper around an urcu read lock which satisfies the 'Mutex' named
  28  * requirements of C++11. Satisfying those requirements facilitates the use of
  29  * standard concurrency support library facilities.
  30  *
  31  * read_lock is under the details namespace since it is unlikely to be used
  32  * directly by exception-safe code. See read_lock_guard.
  33  */
  34 class read_lock {
  35 public:
  36         read_lock() = default;
  37         ~read_lock() = default;
  38
  39         /* "Not copyable" and "not moveable" Mutex requirements. */
  40         read_lock(const read_lock&) = delete;
  41         read_lock(read_lock&&) = delete;
  42         read_lock& operator=(read_lock&&) = delete;
  43         read_lock& operator=(const read_lock&) = delete;
  44
  45         void lock()
  46         {
  47                 rcu_read_lock();
  48         }
  49
  50         bool try_lock()
  51         {
  52                 lock();
  53                 return true;
  54         }
  55
  56         void unlock()
  57         {
  58                 rcu_read_unlock();
  59         }
  60 };
  61 } /* namespace details */
  62
  63 /*
  64  * Provides the basic concept of std::lock_guard for rcu reader locks.
  65  *
  66  * The RCU reader lock is held for the duration of lock_guard's lifetime.
  67  */
  68 class read_lock_guard {
  69 public:
  70         read_lock_guard() = default;
  71         ~read_lock_guard() = default;
  72
  73         read_lock_guard(const read_lock_guard&) = delete;
  74         read_lock_guard(read_lock_guard&&) = delete;
  75         read_lock_guard& operator=(read_lock_guard&&) = delete;
  76         read_lock_guard& operator=(const read_lock_guard&) = delete;
  77
  78 private:
  79         details::read_lock _lock;
  80         std::lock_guard<details::read_lock> _guard{ _lock };
  81 };
  82
  83 using unique_read_lock = std::unique_lock<details::read_lock>;
  84
  85 namespace details {
  86
  87 /* Implementation for types that contain a straight cds_lfht_node. */
  88 template <typename ContainedType, typename NodeType, NodeType ContainedType::*Member>
  89 static typename std::enable_if<std::is_same<cds_lfht_node, NodeType>::value, ContainedType *>::type
  90 get_element_from_node(cds_lfht_node& node)
  91 {
  92         return lttng::utils::container_of(&node, Member);
  93 }
  94
  95 /* Specialization for NodeType deriving from lttng_ht_node. */
  96 template <typename ContainedType, typename NodeType, NodeType ContainedType::*Member>
  97 static typename std::enable_if<std::is_base_of<lttng_ht_node, NodeType>::value, ContainedType *>::type
  98 get_element_from_node(cds_lfht_node& node)
  99 {
 100         return lttng_ht_node_container_of(&node, Member);
 101 }
 102 } /* namespace details */
 103
 104 /*
 105  * The lfht_iteration_adapter class template wraps the liburcu lfht API to provide iteration
 106  * capabilities. It allows users to iterate over a lock-free hash table with ranged-for semantics
 107  * while holding the RCU read lock. The reader lock is held for the lifetime of the iteration
 108  * adapter (i.e. not the lifetime of the iterators it provides).
 109  */
 110 template <typename ContainedType, typename NodeType, NodeType ContainedType::*Member>
 111 class lfht_iteration_adapter {
 112 public:
 113         /* Nested iterator class defines the iterator for lfht_iteration_adapter. */
 114         class iterator : public std::iterator<std::input_iterator_tag, std::uint64_t> {
 115                 /* Allow lfht_iteration_adapter to access private members of iterator. */
 116                 friend lfht_iteration_adapter;
 117
 118         public:
 119                 iterator(const iterator& other) = default;
 120                 iterator(iterator&& other) noexcept = default;
 121                 ~iterator() = default;
 122                 iterator& operator=(const iterator&) = delete;
 123                 iterator& operator=(iterator&&) noexcept = delete;
 124
 125                 /* Move to the next element in the hash table. */
 126                 iterator& operator++()
 127                 {
 128                         cds_lfht_next(&_ht, &_it);
 129                         return *this;
 130                 }
 131
 132                 bool operator==(const iterator& other) const noexcept
 133                 {
 134                         /* Compare pointed nodes by address. */
 135                         return other._it.node == _it.node;
 136                 }
 137
 138                 bool operator!=(const iterator& other) const noexcept
 139                 {
 140                         return !(*this == other);
 141                 }
 142
 143                 /* Dereference the iterator to access the contained element. */
 144                 ContainedType *operator*() const
 145                 {
 146                         auto *node = _it.node;
 147
 148                         /* Throw an exception if dereferencing an end iterator. */
 149                         if (!node) {
 150                                 LTTNG_THROW_OUT_OF_RANGE(
 151                                         "Dereferenced an iterator at the end of a liburcu hashtable");
 152                         }
 153
 154                         /* Retrieve the element from the node. */
 155                         return details::get_element_from_node<ContainedType, NodeType, Member>(
 156                                 *node);
 157                 }
 158
 159         protected:
 160                 iterator(cds_lfht& ht, const cds_lfht_iter& it) : _ht(ht), _it(it)
 161                 {
 162                 }
 163
 164                 /* Reference to the hash table being iterated over. */
 165                 cds_lfht& _ht;
 166                 /* Native lfht iterator pointing to the current position. */
 167                 cds_lfht_iter _it;
 168         };
 169
 170         explicit lfht_iteration_adapter(cds_lfht& ht) : _ht(ht)
 171         {
 172         }
 173
 174         /* Return an iterator to the beginning of the hash table. */
 175         iterator begin() const noexcept
 176         {
 177                 cds_lfht_iter it;
 178
 179                 cds_lfht_first(&_ht, &it);
 180                 return iterator(_ht, it);
 181         }
 182
 183         /* Return an iterator to the end of the hash table. */
 184         iterator end() const noexcept
 185         {
 186                 const cds_lfht_iter it = {};
 187
 188                 return iterator(_ht, it);
 189         }
 190
 191 protected:
 192         /* Reference to the hash table being iterated over. */
 193         cds_lfht& _ht;
 194         /* RCU read lock held during the iteration. */
 195         const lttng::urcu::read_lock_guard read_lock;
 196 };
 197
 198 /*
 199  * The lfht_filtered_iteration_adapter class template wraps the liburcu lfht API to provide
 200  * iteration capabilities over a result set. It allows users to iterate over a lock-free hash
 201  * table's elements matching a given key with ranged-for semantics while holding the RCU read lock.
 202  * The reader lock is held for the lifetime of the iteration adapter (i.e. not the lifetime of the
 203  * iterators it provides).
 204  */
 205 template <typename ContainedType, typename NodeType, NodeType ContainedType::*Member, typename KeyType>
 206 class lfht_filtered_iteration_adapter
 207         : public lfht_iteration_adapter<ContainedType, NodeType, Member> {
 208 public:
 209         /* Nested iterator class defines the iterator for lfht_filtered_iteration_adapter. */
 210         class iterator : public lfht_iteration_adapter<ContainedType, NodeType, Member>::iterator {
 211                 /* Allow lfht_filtered_iteration_adapter to access private members of iterator. */
 212                 friend lfht_filtered_iteration_adapter;
 213
 214         public:
 215                 iterator(const iterator& other) = default;
 216                 iterator(iterator&& other) noexcept = default;
 217                 ~iterator() = default;
 218                 iterator& operator=(const iterator&) = delete;
 219                 iterator& operator=(iterator&&) noexcept = delete;
 220
 221                 /* Move to the next element in the result set. */
 222                 iterator& operator++()
 223                 {
 224                         LTTNG_ASSERT(this->_it.node);
 225                         /* NOLINTBEGIN(cppcoreguidelines-pro-type-const-cast) */
 226                         cds_lfht_next_duplicate(
 227                                 &this->_ht,
 228                                 _match_function,
 229                                 reinterpret_cast<void *>(const_cast<KeyType *>(_key)),
 230                                 &this->_it);
 231                         /* NOLINTEND(cppcoreguidelines-pro-type-const-cast) */
 232                         return *this;
 233                 }
 234
 235         private:
 236                 iterator(cds_lfht& ht,
 237                          const cds_lfht_iter& it,
 238                          const KeyType *key,
 239                          cds_lfht_match_fct match_function) :
 240                         lfht_iteration_adapter<ContainedType, NodeType, Member>::iterator(ht, it),
 241                         _key(key),
 242                         _match_function(match_function)
 243                 {
 244                 }
 245
 246                 /* Only used to create an end iterator. */
 247                 iterator(cds_lfht& ht, const cds_lfht_iter& it) :
 248                         lfht_iteration_adapter<ContainedType, NodeType, Member>::iterator(ht, it),
 249                         _key(nullptr),
 250                         _match_function(nullptr)
 251                 {
 252                 }
 253
 254                 const KeyType *_key;
 255                 const cds_lfht_match_fct _match_function;
 256         };
 257
 258         explicit lfht_filtered_iteration_adapter(cds_lfht& ht,
 259                                                  const KeyType *key,
 260                                                  unsigned long key_hash,
 261                                                  cds_lfht_match_fct match_function) :
 262                 lfht_iteration_adapter<ContainedType, NodeType, Member>(ht),
 263                 _key(key),
 264                 _key_hash(key_hash),
 265                 _match_function(match_function)
 266         {
 267         }
 268
 269         /* Return an iterator to the first result. */
 270         iterator begin() const noexcept
 271         {
 272                 cds_lfht_iter it;
 273
 274                 /* NOLINTBEGIN(cppcoreguidelines-pro-type-const-cast) */
 275                 cds_lfht_lookup(&this->_ht,
 276                                 _key_hash,
 277                                 _match_function,
 278                                 reinterpret_cast<void *>(const_cast<KeyType *>(_key)),
 279                                 &it);
 280                 /* NOLINTEND(cppcoreguidelines-pro-type-const-cast) */
 281                 return iterator(this->_ht, it, _key, _match_function);
 282         }
 283
 284         iterator end() const noexcept
 285         {
 286                 const cds_lfht_iter it = {};
 287
 288                 return iterator(this->_ht, it);
 289         }
 290
 291 private:
 292         const KeyType *_key;
 293         const unsigned long _key_hash;
 294         const cds_lfht_match_fct _match_function;
 295 };
 296
 297 template <typename ContainedType, cds_list_head ContainedType::*Member>
 298 class list_iteration_adapter {
 299 public:
 300         /* Nested iterator class defines the iterator for list_iteration_adapter. */
 301         class iterator : public std::iterator<std::input_iterator_tag, std::uint64_t> {
 302                 /* Allow list_iteration_adapter to access private members of iterator. */
 303                 friend list_iteration_adapter;
 304
 305         public:
 306                 iterator(const iterator& other) = default;
 307                 iterator(iterator&& other) noexcept = default;
 308                 ~iterator() = default;
 309                 iterator& operator=(const iterator&) = delete;
 310                 iterator& operator=(iterator&&) noexcept = delete;
 311
 312                 /* Move to the next element in the hash table. */
 313                 iterator& operator++()
 314                 {
 315                         _node = _node_contents.next;
 316                         _node_contents = *_node;
 317                         return *this;
 318                 }
 319
 320                 bool operator==(const iterator& other) const noexcept
 321                 {
 322                         return other._node == _node;
 323                 }
 324
 325                 bool operator!=(const iterator& other) const noexcept
 326                 {
 327                         return !(*this == other);
 328                 }
 329
 330                 /* Dereference the iterator to access the contained element. */
 331                 ContainedType *operator*() const
 332                 {
 333                         /* Retrieve the element from the node. */
 334                         return lttng::utils::container_of(_node, Member);
 335                 }
 336
 337         protected:
 338                 explicit iterator(const cds_list_head& node) : _node(&node), _node_contents(node)
 339                 {
 340                 }
 341
 342                 /* Current node. */
 343                 const cds_list_head *_node;
 344                 /* Copy of node contents to allow safe deletion during the iteration. */
 345                 cds_list_head _node_contents;
 346         };
 347
 348         explicit list_iteration_adapter(const cds_list_head& list) : _list(list)
 349         {
 350         }
 351
 352         /* Return an iterator to the beginning of the hash table. */
 353         iterator begin() const noexcept
 354         {
 355                 return iterator(*_list.next);
 356         }
 357
 358         /* Return an iterator to the end of the hash table. */
 359         iterator end() const noexcept
 360         {
 361                 return iterator(_list);
 362         }
 363
 364 protected:
 365         /* Reference to the list being iterated over. */
 366         const cds_list_head& _list;
 367 };
 368
 369 template <typename ContainedType, cds_list_head ContainedType::*Member>
 370 class rcu_list_iteration_adapter : public list_iteration_adapter<ContainedType, Member> {
 371 public:
 372         /* Nested iterator class defines the iterator for rcu_list_iteration_adapter. */
 373         class iterator : public list_iteration_adapter<ContainedType, Member>::iterator {
 374                 /* Allow rcu_list_iteration_adapter to access private members of iterator. */
 375                 friend rcu_list_iteration_adapter;
 376
 377         public:
 378                 iterator(const iterator& other) = default;
 379                 iterator(iterator&& other) noexcept = default;
 380                 ~iterator() = default;
 381                 iterator& operator=(const iterator&) = delete;
 382                 iterator& operator=(iterator&&) noexcept = delete;
 383
 384                 /* Move to the next element in the hash table. */
 385                 iterator& operator++()
 386                 {
 387                         this->_node = rcu_dereference(this->_node_contents.next);
 388                         this->_node_contents = *this->_node;
 389                         return *this;
 390                 }
 391
 392         protected:
 393                 explicit iterator(const cds_list_head& node) :
 394                         list_iteration_adapter<ContainedType, Member>::iterator(node)
 395                 {
 396                 }
 397         };
 398
 399         explicit rcu_list_iteration_adapter(const cds_list_head& list) :
 400                 list_iteration_adapter<ContainedType, Member>(list)
 401         {
 402         }
 403
 404         /* Return an iterator to the beginning of the hash table. */
 405         iterator begin() const noexcept
 406         {
 407                 return iterator(*rcu_dereference(this->_list.next));
 408         }
 409
 410         /* Return an iterator to the end of the hash table. */
 411         iterator end() const noexcept
 412         {
 413                 return iterator(this->_list);
 414         }
 415
 416 protected:
 417         /* RCU read lock held during the iteration. */
 418         const lttng::urcu::read_lock_guard read_lock;
 419 };
 420
 421 } /* namespace urcu */
 422 } /* namespace lttng */
 423
 424 #endif /* LTTNG_URCU_H */