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             : #include "base/logging.h"
       7             : #include "base/task_annotations.h"
       8             : #include "base/time_util.h"
       9             : #include "db/db.h"
      10             : #include "db/db_entry.h"
      11             : #include "db/db_partition.h"
      12             : #include "db/db_table.h"
      13             : #include "db/db_table_partition.h"
      14             : 
      15             : using namespace std;
      16             : 
      17             : // concurrency: called from DBPartition task.
      18     3984266 : void DBTablePartBase::Notify(DBEntryBase *entry) {
      19     3984266 :     if (entry->is_onlist()) {
      20     1441969 :         return;
      21             :     }
      22     2541947 :     entry->set_onlist();
      23     2548426 :     bool was_empty = change_list_.empty();
      24     2547997 :     change_list_.push_back(*entry);
      25     2550153 :     if (was_empty) {
      26     1333822 :         DB *db = parent()->database();
      27     1333791 :         DBPartition *partition = db->GetPartition(index_);
      28     1333775 :         partition->OnTableChange(this);
      29             :     }
      30             : }
      31             : 
      32             : //
      33             : // Concurrency: called from db::DBTable/db::IFMapTable task.
      34             : //
      35             : // Evaluate concurrency issues with DBEntryBase::ClearState when making
      36             : // changes to this method. We expect that either this method or ClearState
      37             : // is responsible for removing the DBEntryBase when they run concurrently,
      38             : // assuming the DBEntryBase is eligible for removal. The dbstate_mutex is
      39             : // used for synchronization.
      40             : //
      41     1333859 : bool DBTablePartBase::RunNotify() {
      42     3886230 :     for (int i = 0; ((i < kMaxIterations) && !change_list_.empty()); ++i) {
      43     2552172 :         DBEntryBase *entry = &change_list_.front();
      44     2551994 :         change_list_.pop_front();
      45             : 
      46     2551915 :         parent()->RunNotify(this, entry);
      47     2551199 :         entry->clear_onlist();
      48             : 
      49             :         // If the entry is marked deleted and all DBStates are removed
      50             :         // and it's not already on the remove queue, it can be removed
      51             :         // from the tree right away.
      52             :         //
      53             :         // Note that IsOnRemoveQ must be called after is_state_empty as
      54             :         // synchronization with DBEntryBase::ClearState happens via the
      55             :         // call to is_state_empty, and ClearState can set the OnRemoveQ
      56             :         // bit in the entry.
      57     3016709 :         if (entry->IsDeleted() && entry->is_state_empty(this) &&
      58      464376 :             !entry->IsOnRemoveQ()) {
      59      464304 :             Remove(entry);
      60             :         }
      61             :     }
      62             : 
      63     1333860 :     if (!change_list_.empty()) {
      64          58 :         DB *db = parent()->database();
      65          42 :         DBPartition *partition = db->GetPartition(index_);
      66          42 :         partition->OnTableChange(this);
      67          42 :         return false;
      68             :     }
      69     1333858 :     return true;
      70             : }
      71             : 
      72     1155991 : void DBTablePartBase::Delete(DBEntryBase *entry) {
      73     1155991 :     if (parent_->HasListeners()) {
      74      857845 :         entry->MarkDelete();
      75      857814 :         Notify(entry);
      76             :     } else {
      77             :         // Remove from change_list
      78      298324 :         if (entry->is_onlist()) {
      79        1424 :             change_list_.erase(change_list_.iterator_to(*entry));
      80             :         }
      81      298323 :         Remove(entry);
      82             :     }
      83     1156026 : }
      84             : 
      85     2076544 : DBTablePartition::DBTablePartition(DBTable *table, int index)
      86     2076544 :     : DBTablePartBase(table, index) {
      87     2076540 : }
      88             : 
      89      686329 : void DBTablePartition::Process(DBClient *client, DBRequest *req) {
      90      686329 :     DBTable *table = static_cast<DBTable *>(parent());
      91      686326 :     table->incr_input_count();
      92      686324 :     table->Input(this, client, req);
      93      686323 : }
      94             : 
      95     1135600 : void DBTablePartition::Add(DBEntry *entry) {
      96     1135600 :     std::scoped_lock lock(mutex_);
      97     1135757 :     std::pair<Tree::iterator, bool> ret = tree_.insert(*entry);
      98     1135587 :     assert(ret.second);
      99     1135587 :     entry->set_table_partition(static_cast<DBTablePartBase *>(this));
     100     1135580 :     Notify(entry);
     101     1135663 :     parent()->AddRemoveCallback(entry, true);
     102     1135649 : }
     103             : 
     104      227441 : void DBTablePartition::Change(DBEntry *entry) {
     105      227441 :     std::scoped_lock lock(mutex_);
     106      227441 :     Notify(entry);
     107      227441 : }
     108             : 
     109     1135622 : void DBTablePartition::Remove(DBEntryBase *db_entry) {
     110     1135622 :     std::scoped_lock lock(mutex_);
     111     1135643 :     DBEntry *entry = static_cast<DBEntry *>(db_entry);
     112     1135643 :     parent()->AddRemoveCallback(entry, false);
     113             : 
     114     1135549 :     bool success = tree_.erase(*entry);
     115     1135322 :     if (!success) {
     116           0 :         LOG(FATAL, "ABORT: DB node erase failed for table " + parent()->name());
     117           0 :         LOG(FATAL, "Invalid node " + db_entry->ToString());
     118           0 :         abort();
     119             :     }
     120     1135322 :     delete entry;
     121             : 
     122             :     // If a table is marked for deletion, then we may trigger the deletion
     123             :     // process when the last prefix is deleted
     124     1135791 :     if (tree_.empty())
     125      135065 :         table()->RetryDelete();
     126     1135640 : }
     127             : 
     128         474 : void DBTablePartition::AddWithoutAlloc(DBEntry *entry) {
     129         474 :     std::scoped_lock lock(mutex_);
     130         474 :     tree_.insert(*entry);
     131         474 :     entry->set_table_partition(static_cast<DBTablePartBase *>(this));
     132         474 :     Notify(entry);
     133         474 :     parent()->AddRemoveCallback(entry, true);
     134         474 : }
     135             : 
     136         474 : void DBTablePartition::RemoveWithoutDelete(DBEntry *entry) {
     137         474 :     std::scoped_lock lock(mutex_);
     138         474 :     bool success = tree_.erase(*entry);
     139         474 :     if (!success) {
     140           0 :         LOG(FATAL, "ABORT: DB node erase failed for table " + parent()->name());
     141           0 :         abort();
     142             :     }
     143         474 : }
     144             : 
     145     3074248 : DBEntry *DBTablePartition::FindInternal(const DBEntry *entry) {
     146     3074248 :     Tree::iterator loc = tree_.find(*entry);
     147     6147988 :     if (loc != tree_.end()) {
     148     1500904 :         return loc.operator->();
     149             :     }
     150     1573082 :     return NULL;
     151             : }
     152             : 
     153       24089 : const DBEntry *DBTablePartition::FindInternal(const DBEntry *entry) const {
     154       24089 :     Tree::const_iterator loc = tree_.find(*entry);
     155       48178 :     if (loc != tree_.end()) {
     156       16721 :         return loc.operator->();
     157             :     }
     158        7368 :     return NULL;
     159             : }
     160             : 
     161         117 : DBEntry *DBTablePartition::FindNoLock(const DBEntry *entry) {
     162         117 :     CHECK_CONCURRENCY("db::DBTable", "db::IFMapTable",
     163             :         "Agent::FlowEvent", "Agent::FlowUpdate");
     164         117 :     return FindInternal(entry);
     165             : }
     166             : 
     167     2223720 : DBEntry *DBTablePartition::Find(const DBEntry *entry) {
     168     2223720 :     std::scoped_lock lock(mutex_);
     169     4448414 :     return FindInternal(entry);
     170     2223910 : }
     171             : 
     172       24089 : const DBEntry *DBTablePartition::Find(const DBEntry *entry) const {
     173       24089 :     std::scoped_lock lock(mutex_);
     174       48178 :     return FindInternal(entry);
     175       24089 : }
     176             : 
     177          36 : DBEntry *DBTablePartition::FindNoLock(const DBRequestKey *key) {
     178          36 :     CHECK_CONCURRENCY("db::DBTable", "db::IFMapTable",
     179             :         "Agent::FlowEvent", "Agent::FlowUpdate");
     180          36 :     DBTable *table = static_cast<DBTable *>(parent());
     181          36 :     std::unique_ptr<DBEntry> entry_ptr = table->AllocEntry(key);
     182          72 :     return FindInternal(entry_ptr.get());
     183          36 : }
     184             : 
     185      849929 : DBEntry *DBTablePartition::Find(const DBRequestKey *key) {
     186      849929 :     DBTable *table = static_cast<DBTable *>(parent());
     187      849929 :     std::unique_ptr<DBEntry> entry_ptr = table->AllocEntry(key);
     188      849928 :     std::scoped_lock lock(mutex_);
     189     1699857 :     return FindInternal(entry_ptr.get());
     190      849929 : }
     191             : 
     192           0 : DBEntry *DBTablePartition::FindNext(const DBRequestKey *key) {
     193           0 :     std::scoped_lock lock(mutex_);
     194           0 :     DBTable *table = static_cast<DBTable *>(parent());
     195           0 :     std::unique_ptr<DBEntry> entry_ptr = table->AllocEntry(key);
     196             : 
     197           0 :     Tree::iterator loc = tree_.upper_bound(*(entry_ptr.get()));
     198           0 :     if (loc != tree_.end()) {
     199           0 :         return loc.operator->();
     200             :     }
     201           0 :     return NULL;
     202           0 : }
     203             : 
     204             : // Returns the matching entry or next in lex order
     205      664350 : DBEntry *DBTablePartition::lower_bound(const DBEntryBase *key) {
     206      664350 :     const DBEntry *entry = static_cast<const DBEntry *>(key);
     207      664350 :     std::scoped_lock lock(mutex_);
     208             : 
     209      664707 :     Tree::iterator it = tree_.lower_bound(*entry);
     210     1328976 :     if (it != tree_.end()) {
     211      664398 :         return (it.operator->());
     212             :     }
     213          90 :     return NULL;
     214      664488 : }
     215             : 
     216     1378778 : DBEntry *DBTablePartition::GetFirst() {
     217     1378778 :     std::scoped_lock lock(mutex_);
     218     1378831 :     Tree::iterator it = tree_.begin();
     219     2757629 :     if (it == tree_.end()) {
     220     1207865 :         return NULL;
     221             :     }
     222      170944 :     return it.operator->();
     223     1378809 : }
     224             : 
     225             : // Returns the next entry (Doesn't search). Threaded walk
     226     1747775 : DBEntry *DBTablePartition::GetNext(const DBEntryBase *key) {
     227     1747775 :     const DBEntry *entry = static_cast<const DBEntry *>(key);
     228     1747775 :     std::scoped_lock lock(mutex_);
     229             : 
     230     1748244 :     Tree::const_iterator it = tree_.iterator_to(*entry);
     231     1748031 :     it++;
     232     3495079 :     if (it != tree_.end()) {
     233     1517744 :         return const_cast<DBEntry *>(it.operator->());
     234             :     }
     235      229617 :     return NULL;
     236     1747361 : }
     237             : 
     238      142399 : DBTable *DBTablePartition::table() {
     239      142399 :     return static_cast<DBTable *>(parent());
     240             : }