Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #ifndef ctrlplane_db_table_h
       6             : #define ctrlplane_db_table_h
       7             : 
       8             : #include <atomic>
       9             : #include <memory>
      10             : #include <vector>
      11             : #include <unistd.h>
      12             : #include <boost/function.hpp>
      13             : #include <boost/intrusive_ptr.hpp>
      14             : 
      15             : #include "base/util.h"
      16             : 
      17             : class DB;
      18             : class DBClient;
      19             : class DBEntryBase;
      20             : class DBEntry;
      21             : class DBTablePartBase;
      22             : class DBTablePartition;
      23             : class DBTableWalk;
      24             : class ShowTableListener;
      25             : 
      26             : class DBRequestKey {
      27             : public:
      28     2311673 :     virtual ~DBRequestKey() { }
      29             : };
      30             : class DBRequestData {
      31             : public:
      32      476479 :     virtual ~DBRequestData() { }
      33             : };
      34             : 
      35             : struct DBRequest {
      36             :     typedef enum {
      37             :         DB_ENTRY_INVALID = 0,
      38             :         DB_ENTRY_ADD_CHANGE = 1,
      39             :         DB_ENTRY_DELETE = 2,
      40             :         DB_ENTRY_NOTIFY = 3,
      41             :     } DBOperation;
      42             :     DBOperation oper;
      43             : 
      44             :     DBRequest();
      45        1490 :     DBRequest(DBOperation op) : oper(op) { }
      46             :     ~DBRequest();
      47             : 
      48             :     std::unique_ptr<DBRequestKey> key;
      49             :     std::unique_ptr<DBRequestData> data;
      50             : 
      51             :     // Swap contents between two DBRequest entries.
      52             :     void Swap(DBRequest *rhs);
      53             : 
      54             : private:
      55             :     DISALLOW_COPY_AND_ASSIGN(DBRequest);
      56             : };
      57             : 
      58             : // Database table interface.
      59             : class DBTableBase {
      60             : public:
      61             :     typedef boost::function<void(DBTablePartBase *, DBEntryBase *)> ChangeCallback;
      62             :     typedef int ListenerId;
      63             : 
      64             :     static const int kInvalidId = -1;
      65             : 
      66             :     DBTableBase(DB *db, const std::string &name);
      67             :     virtual ~DBTableBase();
      68             : 
      69             :     // Enqueue a request to the table. Takes ownership of the data.
      70             :     bool Enqueue(DBRequest *req);
      71             :     void EnqueueRemove(DBEntryBase *db_entry);
      72             : 
      73             :     // Determine the table partition depending on the record key.
      74             :     virtual DBTablePartBase *GetTablePartition(const DBRequestKey *key) = 0;
      75             :     // Determine the table partition depending on the Entry
      76             :     virtual DBTablePartBase *GetTablePartition(const DBEntryBase *entry) = 0;
      77             :     // Determine the table partition for given index
      78             :     virtual DBTablePartBase *GetTablePartition(const int index) = 0;
      79             : 
      80             :     // Record has been modified.
      81             :     virtual void Change(DBEntryBase *) = 0;
      82             : 
      83             :     // Callback from table partition for entry add/remove.
      84     2007857 :     virtual void AddRemoveCallback(const DBEntryBase *entry, bool add) const { }
      85             : 
      86             :     // Register a DB listener.
      87             :     ListenerId Register(ChangeCallback callback,
      88             :         const std::string &name = "unspecified");
      89             :     void Unregister(ListenerId listener);
      90             : 
      91             :     void RunNotify(DBTablePartBase *tpart, DBEntryBase *entry);
      92             : 
      93             :     // Manage db state count for a listener.
      94             :     void AddToDBStateCount(ListenerId listener, int count);
      95             : 
      96             :     uint64_t GetDBStateCount(ListenerId listener);
      97             : 
      98             :     // Calculate the size across all partitions.
      99             :     // Must be called from Task which is mutually exclusive with db::DBTable.
     100           0 :     virtual size_t Size() const { return 0; }
     101     1196457 :     bool empty() const { return (Size() == 0); }
     102             : 
     103             :     // Suspended deletion resume hook for user function
     104      138992 :     virtual void RetryDelete() { }
     105             :     virtual bool MayDelete() const;
     106             : 
     107     3624835 :     DB *database() { return db_; }
     108             :     const DB *database() const { return db_; }
     109             : 
     110    11463074 :     const std::string &name() const { return name_; }
     111             : 
     112             :     bool HasListeners() const;
     113             :     size_t GetListenerCount() const;
     114             :     void FillListeners(std::vector<ShowTableListener> *listeners) const;
     115             : 
     116           0 :     uint64_t enqueue_count() const { return enqueue_count_; }
     117             :     void incr_enqueue_count() { enqueue_count_++; }
     118             :     void reset_enqueue_count() { enqueue_count_ = 0; }
     119             : 
     120         248 :     uint64_t input_count() const { return input_count_; }
     121      648187 :     void incr_input_count() { input_count_++; }
     122             :     void reset_input_count() { input_count_ = 0; }
     123             : 
     124           0 :     uint64_t notify_count() const { return notify_count_; }
     125             :     void incr_notify_count() { notify_count_++; }
     126             :     void reset_notify_count() { notify_count_ = 0; }
     127             : 
     128      577232 :     bool HasWalkers() const { return walker_count_ != 0; }
     129       10313 :     uint64_t walker_count() const { return walker_count_; }
     130      219712 :     void incr_walker_count() { walker_count_++; }
     131      219712 :     uint64_t decr_walker_count() { return --walker_count_; }
     132             : 
     133       10365 :     uint64_t walk_request_count() const { return walk_request_count_; }
     134       10478 :     uint64_t walk_complete_count() const { return walk_complete_count_; }
     135       10313 :     uint64_t walk_cancel_count() const { return walk_cancel_count_; }
     136        9220 :     uint64_t walk_again_count() const { return walk_again_count_; }
     137        9253 :     uint64_t walk_count() const { return walk_count_; }
     138      255962 :     void incr_walk_request_count() { walk_request_count_++; }
     139      226704 :     void incr_walk_complete_count() { walk_complete_count_++; }
     140           0 :     void incr_walk_cancel_count() { walk_cancel_count_++; }
     141         480 :     void incr_walk_again_count() { walk_again_count_++; }
     142      226254 :     void incr_walk_count() { walk_count_++; }
     143             : 
     144             : private:
     145             :     class ListenerInfo;
     146             :     DB *db_;
     147             :     std::string name_;
     148             :     std::unique_ptr<ListenerInfo> info_;
     149             :     uint64_t enqueue_count_;
     150             :     uint64_t input_count_;
     151             :     uint64_t notify_count_;
     152             :     std::atomic<uint64_t> walker_count_;
     153             :     std::atomic<uint64_t> walk_count_;
     154             :     std::atomic<uint64_t> walk_request_count_;
     155             :     std::atomic<uint64_t> walk_complete_count_;
     156             :     std::atomic<uint64_t> walk_cancel_count_;
     157             :     std::atomic<uint64_t> walk_again_count_;
     158             : };
     159             : 
     160             : // An implementation of DBTableBase that uses boost::set as data-store
     161             : // Most of the DB Table implementations should derive from here instead of
     162             : // DBTableBase directly.
     163             : // Derive directly from DBTableBase only if there is a strong reason to do so
     164             : //
     165             : // Additionally, provides a set of virtual functions to override the default
     166             : // functionality
     167             : class DBTable : public DBTableBase {
     168             : public:
     169             :     typedef boost::intrusive_ptr<DBTableWalk> DBTableWalkRef;
     170             : 
     171             :     // Walker function:
     172             :     // Called for each DBEntry under a db::DBTable task that corresponds to the
     173             :     // specific partition.
     174             :     // arguments: DBTable partition and DBEntry.
     175             :     // returns: true (continue); false (stop).
     176             :     typedef boost::function<bool(DBTablePartBase *, DBEntryBase *)> WalkFn;
     177             : 
     178             :     // Called when all partitions are done iterating.
     179             :     typedef boost::function<void(DBTableWalkRef, DBTableBase *)> WalkCompleteFn;
     180             : 
     181             :     static const int kIterationToYield = 256;
     182             : 
     183             :     DBTable(DB *db, const std::string &name);
     184             :     virtual ~DBTable();
     185             :     void Init();
     186             : 
     187             :     ///////////////////////////////////////////////////////////
     188             :     // virtual functions to be implemented by derived class
     189             :     ///////////////////////////////////////////////////////////
     190             : 
     191             :     // Alloc a derived DBEntry
     192             :     virtual std::unique_ptr<DBEntry> AllocEntry(const DBRequestKey *key) const = 0;
     193             : 
     194             :     // Hash for an entry. Used to identify partition
     195      884433 :     virtual size_t Hash(const DBEntry *entry) const {return 0;};
     196             : 
     197             :     // Hash for key. Used to identify partition
     198      178939 :     virtual size_t Hash(const DBRequestKey *key) const {return 0;};
     199             : 
     200             :     // Alloc a derived DBTablePartBase entry. The default implementation
     201             :     // allocates DBTablePart should be good for most common cases.
     202             :     // Override if *really* necessary
     203             :     virtual DBTablePartition *AllocPartition(int index);
     204             : 
     205             :     // Input processing implemented by derived class. Default
     206             :     // implementation takes care of Add/Delete/Change.
     207             :     // Override if *really* necessary
     208             :     virtual void Input(DBTablePartition *tbl_partition, DBClient *client,
     209             :                        DBRequest *req);
     210             : 
     211             :     // Add hook for user function. Must return entry to be inserted into tree
     212             :     // Must return NULL if no entry is to be added into tree
     213             :     virtual DBEntry *Add(const DBRequest *req);
     214             :     // Change hook for user function. Return 'true' if clients need to be
     215             :     // notified of the change
     216             :     virtual bool OnChange(DBEntry *entry, const DBRequest *req);
     217             :     // Delete hook for user function
     218             :     virtual bool Delete(DBEntry *entry, const DBRequest *req);
     219             : 
     220             :     void NotifyAllEntries();
     221             : 
     222             :     ///////////////////////////////////////////////////////////
     223             :     // Utility methods for table
     224             :     ///////////////////////////////////////////////////////////
     225             :     // Find DB Entry. Get key from from argument
     226             :     DBEntry *Find(const DBEntry *entry);
     227             :     const DBEntry *Find(const DBEntry *entry) const;
     228             : 
     229             :     DBEntry *Find(const DBRequestKey *key, int id = -1);
     230             :     const DBEntry *Find(const DBRequestKey *key, int id = -1) const;
     231             : 
     232             :     // Find DB Entry without taking lock. Calling routine must ensure its
     233             :     // running in exclusion with DB task
     234             :     DBEntry *FindNoLock(const DBEntry *entry);
     235             :     DBEntry *FindNoLock(const DBRequestKey *key);
     236             : 
     237             :     ///////////////////////////////////////////////////////////////
     238             :     // Virtual functions from DBTableBase implemented by DBTable
     239             :     ///////////////////////////////////////////////////////////////
     240             : 
     241             :     // Return the table partition for a specific request.
     242             :     virtual DBTablePartBase *GetTablePartition(const DBRequestKey *key);
     243             :     virtual const DBTablePartBase *GetTablePartition(
     244             :         const DBRequestKey *key) const;
     245             :     // Return the table partition for a DBEntryBase
     246             :     virtual DBTablePartBase *GetTablePartition(const DBEntryBase *entry);
     247             :     virtual const DBTablePartBase *GetTablePartition(
     248             :         const DBEntryBase *entry) const;
     249             :     // Return the table partition for a index
     250             :     virtual DBTablePartBase *GetTablePartition(const int index);
     251             :     virtual const DBTablePartBase *GetTablePartition(const int index) const;
     252             : 
     253             :     // Change notification handler.
     254             :     virtual void Change(DBEntryBase *entry);
     255             : 
     256             :     virtual int PartitionCount() const;
     257             : 
     258             :     // Calculate the size across all partitions.
     259             :     virtual size_t Size() const;
     260             : 
     261             :     // helper functions
     262             : 
     263             :     // Delete all the state entries of a specific listener.
     264             :     // Not thread-safe. Used to shutdown and cleanup the process.
     265             :     static void DBStateClear(DBTable *table, ListenerId id);
     266             : 
     267             : 
     268             :     // Walk APIs
     269             :     // Create a DBTable Walker
     270             :     // Concurrency : can be invoked from any task
     271             :     DBTableWalkRef AllocWalker(WalkFn walk_fn, WalkCompleteFn walk_complete);
     272             : 
     273             :     // Release the Walker
     274             :     // Concurrency : can be invoked from any task
     275             :     void ReleaseWalker(DBTableWalkRef &walk);
     276             : 
     277             :     // Start a walk on the table.
     278             :     // Concurrency : should be invoked from a task which is mutually exclusive
     279             :     // "db::Walker" task
     280             :     void WalkTable(DBTableWalkRef walk);
     281             : 
     282             :     // Walk the table again
     283             :     // Concurrency : should be invoked from a task which is mutually exclusive
     284             :     // "db::Walker" task
     285             :     void WalkAgain(DBTableWalkRef walk);
     286             : 
     287           2 :     void SetWalkIterationToYield(int count) {
     288           2 :         max_walk_iteration_to_yield_ = count;
     289           2 :     }
     290             : 
     291      792999 :     int GetWalkIterationToYield() {
     292      792999 :         return max_walk_iteration_to_yield_;
     293             :     }
     294             : 
     295           6 :     void SetWalkTaskId(int task_id) {
     296           6 :         walker_task_id_ = task_id;
     297           6 :     }
     298             : 
     299      130455 :     int GetWalkerTaskId() {
     300      130455 :         return walker_task_id_;
     301             :     }
     302             : private:
     303             :     friend class DBTableWalkMgr;
     304             :     class TableWalker;
     305             :     // A Job for walking through the DBTablePartition
     306             :     class WalkWorker;
     307             : 
     308      792230 :     static void db_walker_wait() {
     309             :         static unsigned int walk_sleep_usecs_;
     310             :         static bool once;
     311             : 
     312      792230 :         if (!once) {
     313          93 :             once = true;
     314             : 
     315          93 :             char *wait = getenv("DB_WALKER_WAIT_USECS");
     316          93 :             if (wait) {
     317           0 :               walk_sleep_usecs_ = (unsigned int) strtoul(wait, NULL, 0);
     318           0 :               if (walk_sleep_usecs_ > 1000000)
     319           0 :                 walk_sleep_usecs_ = 1000000;
     320             :             }
     321             :             
     322             :         }
     323             : 
     324      792230 :         if (walk_sleep_usecs_) {
     325           0 :             usleep(walk_sleep_usecs_);
     326             :         }
     327      792230 :     }
     328             : 
     329             :     ///////////////////////////////////////////////////////////
     330             :     // Utility methods
     331             :     ///////////////////////////////////////////////////////////
     332             :     // Hash key to a partition id
     333             :     int GetPartitionId(const DBRequestKey *key);
     334             :     // Hash entry to a partition id
     335             :     int GetPartitionId(const DBEntry *entry);
     336             : 
     337             :     // Called from DBTableWalkMgr to start the walk
     338             :     void StartWalk();
     339             : 
     340             :     // Call DBTableWalkMgr to notify the walkers
     341             :     bool InvokeWalkCb(DBTablePartBase *part, DBEntryBase *entry);
     342             : 
     343             :     // Call DBTableWalkMgr::WalkDone
     344             :     void WalkDone();
     345             : 
     346             :     // Walker callback for NotifyAllEntries()
     347             :     bool WalkCallback(DBTablePartBase *tpart, DBEntryBase *entry);
     348             :     void WalkCompleteCallback(DBTableBase *tbl_base);
     349             : 
     350             :     std::unique_ptr<TableWalker> walker_;
     351             :     std::vector<DBTablePartition *> partitions_;
     352             :     DBTable::DBTableWalkRef walk_ref_;
     353             :     int walker_task_id_;
     354             :     int max_walk_iteration_to_yield_;
     355             : 
     356             :     DISALLOW_COPY_AND_ASSIGN(DBTable);
     357             : };
     358             : 
     359             : class DBTableWalk {
     360             : public:
     361             :     enum WalkState {
     362             :         INIT = 1,
     363             :         WALK_REQUESTED = 2,
     364             :         WALK_IN_PROGRESS = 3,
     365             :         WALK_DONE = 4,
     366             :         WALK_STOPPED = 5,
     367             :     };
     368             : 
     369      219262 :     DBTableWalk(DBTable *table, DBTable::WalkFn walk_fn,
     370             :                 DBTable::WalkCompleteFn walk_complete)
     371      219262 :         : table_(table), walk_fn_(walk_fn), walk_complete_(walk_complete) {
     372      219262 :         walk_state_ = INIT;
     373      219262 :         walk_again_ = false;
     374      219262 :         refcount_ = 0;
     375      219262 :     }
     376             : 
     377      702742 :     DBTable *table() const { return table_;}
     378      793439 :     DBTable::WalkFn walk_fn() const { return walk_fn_;}
     379      227482 :     DBTable::WalkCompleteFn walk_complete() const { return walk_complete_;}
     380             : 
     381             :     bool requested() const { return (walk_state_ == WALK_REQUESTED);}
     382      256166 :     bool in_progress() const { return (walk_state_ == WALK_IN_PROGRESS);}
     383      794252 :     bool done() const { return (walk_state_ == WALK_DONE);}
     384     1476751 :     bool stopped() const { return (walk_state_ == WALK_STOPPED);}
     385     1249142 :     bool walk_again() const { return walk_again_;}
     386       22658 :     bool walk_is_active() const {
     387       45291 :         return ((walk_state_ == WALK_REQUESTED) ||
     388       45291 :                 (walk_state_ == WALK_IN_PROGRESS));
     389             :     }
     390             : 
     391             :     WalkState walk_state() const { return walk_state_;}
     392             : 
     393             : private:
     394             :     friend class DBTableWalkMgr;
     395             : 
     396             :     friend void intrusive_ptr_add_ref(DBTableWalk *walker);
     397             :     friend void intrusive_ptr_release(DBTableWalk *walker);
     398             : 
     399         480 :     void set_walk_again() { walk_again_ = true;}
     400      227741 :     void reset_walk_again() { walk_again_ = false;}
     401             : 
     402      227488 :     void set_walk_done() { walk_state_ = WALK_DONE;}
     403      255769 :     void set_walk_requested() { walk_state_ = WALK_REQUESTED;}
     404      227741 :     void set_in_progress() { walk_state_ = WALK_IN_PROGRESS;}
     405      157707 :     void set_walk_stopped() { walk_state_ = WALK_STOPPED;}
     406             : 
     407             :     DBTable *table_;
     408             :     DBTable::WalkFn walk_fn_;
     409             :     DBTable::WalkCompleteFn walk_complete_;
     410             :     std::atomic<WalkState> walk_state_;
     411             :     std::atomic<bool> walk_again_;
     412             :     std::atomic<int> refcount_;
     413             : 
     414             :     DISALLOW_COPY_AND_ASSIGN(DBTableWalk);
     415             : };
     416             : 
     417     2775961 : inline void intrusive_ptr_add_ref(DBTableWalk *walker) {
     418     2775961 :     walker->refcount_.fetch_add(1);
     419     2775961 : }
     420             : 
     421     2776067 : inline void intrusive_ptr_release(DBTableWalk *walker) {
     422     2776067 :     int prev = walker->refcount_.fetch_sub(1);
     423     2776067 :     if (prev == 1) {
     424      219262 :         DBTable *table = walker->table();
     425      219262 :         delete walker;
     426      219262 :         table->decr_walker_count();
     427      219262 :         table->RetryDelete();
     428             :     }
     429     2776067 : }
     430             : #endif