Line data    Source code

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