Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  * Copyright Contributors to the OpenSDN project
       4             :  */
       5             : 
       6             : #ifndef ctrlplane_label_block_h
       7             : #define ctrlplane_label_block_h
       8             : 
       9             : #include <atomic>
      10             : #include <vector>
      11             : #include <mutex>
      12             : #include <boost/intrusive_ptr.hpp>
      13             : 
      14             : #include "base/bitset.h"
      15             : 
      16             : class LabelBlock;
      17             : class LabelBlockManager;
      18             : 
      19             : typedef boost::intrusive_ptr<LabelBlockManager> LabelBlockManagerPtr;
      20             : typedef boost::intrusive_ptr<LabelBlock> LabelBlockPtr;
      21             : 
      22             : //
      23             : // This class represents the manager for a label space. The label space could
      24             : // be for the local node or for a remote node.  The manager maintains a list
      25             : // of LabelBlocks from which labels can be allocated.
      26             : //
      27             : // Clients locate LabelBLocks by specifying the first and last label values for
      28             : // a block. A new LabelBlock is created or the refcount for an existing one is
      29             : // updated as appropriate.  Note that we always return an intrusive pointer to
      30             : // LabelBlock, so that the removal of the LabelBlock happens automatically.
      31             : //
      32             : class LabelBlockManager {
      33             : public:
      34             :     LabelBlockManager();
      35             :     ~LabelBlockManager();
      36             :     LabelBlockPtr LocateBlock(uint32_t first, uint32_t last);
      37             :     void RemoveBlock(LabelBlock *block);
      38       11797 :     std::mutex &mutex() { return mutex_; }
      39             : 
      40             : private:
      41             :     friend class LabelBlockTest;
      42             :     friend void intrusive_ptr_add_ref(LabelBlockManager *block_manager);
      43             :     friend void intrusive_ptr_release(LabelBlockManager *block_manager);
      44             : 
      45             :     typedef std::vector<LabelBlock *> LabelBlockList;
      46             : 
      47             :     size_t size();
      48             : 
      49             :     std::atomic<int> refcount_;
      50             : 
      51             :     // The vector of LabelBlocks is protected via the mutex_. This is needed
      52             :     // because we need to handle concurrent calls to LocateBlock/RemoveBLock.
      53             :     std::mutex mutex_;
      54             :     LabelBlockList blocks_;
      55             : };
      56             : 
      57       35134 : inline void intrusive_ptr_add_ref(LabelBlockManager *block_manager) {
      58       35134 :     block_manager->refcount_++;
      59       35145 : }
      60             : 
      61       35140 : inline void intrusive_ptr_release(LabelBlockManager *block_manager) {
      62       35140 :     int prev = block_manager->refcount_.fetch_sub(1);
      63       35140 :     if (prev == 1) {
      64       10052 :         delete block_manager;
      65             :     }
      66       35140 : }
      67             : 
      68             : //
      69             : // This class represents a block of labels within a label space. Clients can
      70             : // make requests to allocate/release a single label from within this block.
      71             : // As mentioned above, clients always maintain an intrusive pointer to these
      72             : // objects.
      73             : //
      74             : // A BitSet is used to keep track of used/allocated values. A position in the
      75             : // BitSet represents an offset from the first value e.g. label value of first
      76             : // corresponds to bit position 0.
      77             : //
      78             : // TBD: A BitSet is not time efficient when managing a large label space so
      79             : // we should revisit the implementation of this class. Perhaps we could use
      80             : // an itable or a hierarchy of BitSets.
      81             : //
      82             : class LabelBlock {
      83             : public:
      84             :     LabelBlock(uint32_t first, uint32_t last);
      85             :     LabelBlock(LabelBlockManager *block_manager, uint32_t first, uint32_t last);
      86             :     ~LabelBlock();
      87             : 
      88             :     uint32_t AllocateLabel();
      89             :     void ReleaseLabel(uint32_t value);
      90             :     std::string ToString() const;
      91      177097 :     uint32_t first() { return first_; }
      92      162748 :     uint32_t last() { return last_; }
      93       41109 :     LabelBlockManagerPtr block_manager() { return block_manager_; }
      94             : 
      95             : private:
      96             :     friend class LabelBlockManager;
      97             :     friend class LabelBlockTest;
      98             :     friend void intrusive_ptr_add_ref(LabelBlock *block);
      99             :     friend void intrusive_ptr_release(LabelBlock *block);
     100             : 
     101             :     LabelBlockManagerPtr block_manager_;
     102             :     uint32_t first_, last_;
     103             :     size_t prev_pos_;
     104             :     std::atomic<int> refcount_;
     105             : 
     106             :     // The BitSet of used labels is protected via the mutex_. This is needed
     107             :     // since we need to handle concurrent calls to AllocateLabel/ReleaseLabel.
     108             :     std::mutex mutex_;
     109             :     BitSet used_bitset_;
     110             : };
     111             : 
     112       29318 : inline void intrusive_ptr_add_ref(LabelBlock *block) {
     113       29318 :     block->refcount_++;
     114       29318 : }
     115             : 
     116       29317 : inline void intrusive_ptr_release(LabelBlock *block) {
     117       29317 :     std::mutex mutex;
     118             : 
     119       41113 :     std::scoped_lock lock(block->block_manager() ? block->block_manager()->mutex() : mutex);
     120             : 
     121       29318 :     int prev = block->refcount_.fetch_sub(1);
     122       29318 :     if (prev == 1) {
     123        7926 :         delete block;
     124             :     }
     125       29318 : }
     126             : 
     127             : #endif