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