Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #include "base/logging.h"
       6             : #include "base/task_annotations.h"
       7             : #include "base/time_util.h"
       8             : #include "db/db.h"
       9             : #include "db/db_entry.h"
      10             : #include "db/db_partition.h"
      11             : #include "db/db_table.h"
      12             : #include "db/db_table_partition.h"
      13             : 
      14             : using namespace std;
      15             : 
      16             : // concurrency: called from DBPartition task.
      17     3994018 : void DBTablePartBase::Notify(DBEntryBase *entry) {
      18     3994018 :     if (entry->is_onlist()) {
      19     1430849 :         return;
      20             :     }
      21     2563177 :     entry->set_onlist();
      22     2567419 :     bool was_empty = change_list_.empty();
      23     2567341 :     change_list_.push_back(*entry);
      24     2568317 :     if (was_empty) {
      25     1357118 :         DB *db = parent()->database();
      26     1357081 :         DBPartition *partition = db->GetPartition(index_);
      27     1357059 :         partition->OnTableChange(this);
      28             :     }
      29             : }
      30             : 
      31             : //
      32             : // Concurrency: called from db::DBTable/db::IFMapTable task.
      33             : //
      34             : // Evaluate concurrency issues with DBEntryBase::ClearState when making
      35             : // changes to this method. We expect that either this method or ClearState
      36             : // is responsible for removing the DBEntryBase when they run concurrently,
      37             : // assuming the DBEntryBase is eligible for removal. The dbstate_mutex is
      38             : // used for synchronization.
      39             : //
      40     1357234 : bool DBTablePartBase::RunNotify() {
      41     3927260 :     for (int i = 0; ((i < kMaxIterations) && !change_list_.empty()); ++i) {
      42     2569813 :         DBEntryBase *entry = &change_list_.front();
      43     2569691 :         change_list_.pop_front();
      44             : 
      45     2569676 :         parent()->RunNotify(this, entry);
      46     2570030 :         entry->clear_onlist();
      47             : 
      48             :         // If the entry is marked deleted and all DBStates are removed
      49             :         // and it's not already on the remove queue, it can be removed
      50             :         // from the tree right away.
      51             :         //
      52             :         // Note that IsOnRemoveQ must be called after is_state_empty as
      53             :         // synchronization with DBEntryBase::ClearState happens via the
      54             :         // call to is_state_empty, and ClearState can set the OnRemoveQ
      55             :         // bit in the entry.
      56     3041391 :         if (entry->IsDeleted() && entry->is_state_empty(this) &&
      57      471393 :             !entry->IsOnRemoveQ()) {
      58      471293 :             Remove(entry);
      59             :         }
      60             :     }
      61             : 
      62     1357200 :     if (!change_list_.empty()) {
      63          43 :         DB *db = parent()->database();
      64          45 :         DBPartition *partition = db->GetPartition(index_);
      65          45 :         partition->OnTableChange(this);
      66          45 :         return false;
      67             :     }
      68     1357229 :     return true;
      69             : }
      70             : 
      71     1171725 : void DBTablePartBase::Delete(DBEntryBase *entry) {
      72     1171725 :     if (parent_->HasListeners()) {
      73      873610 :         entry->MarkDelete();
      74      873534 :         Notify(entry);
      75             :     } else {
      76             :         // Remove from change_list
      77      298250 :         if (entry->is_onlist()) {
      78        1428 :             change_list_.erase(change_list_.iterator_to(*entry));
      79             :         }
      80      298250 :         Remove(entry);
      81             :     }
      82     1171662 : }
      83             : 
      84     2076702 : DBTablePartition::DBTablePartition(DBTable *table, int index)
      85     2076702 :     : DBTablePartBase(table, index) {
      86     2076559 : }
      87             : 
      88      735814 : void DBTablePartition::Process(DBClient *client, DBRequest *req) {
      89      735814 :     DBTable *table = static_cast<DBTable *>(parent());
      90      735798 :     table->incr_input_count();
      91      735768 :     table->Input(this, client, req);
      92      735770 : }
      93             : 
      94     1149147 : void DBTablePartition::Add(DBEntry *entry) {
      95     1149147 :     std::scoped_lock lock(mutex_);
      96     1149223 :     std::pair<Tree::iterator, bool> ret = tree_.insert(*entry);
      97     1149042 :     assert(ret.second);
      98     1149042 :     entry->set_table_partition(static_cast<DBTablePartBase *>(this));
      99     1149033 :     Notify(entry);
     100     1149099 :     parent()->AddRemoveCallback(entry, true);
     101     1149078 : }
     102             : 
     103      230186 : void DBTablePartition::Change(DBEntry *entry) {
     104      230186 :     std::scoped_lock lock(mutex_);
     105      230186 :     Notify(entry);
     106      230186 : }
     107             : 
     108     1149005 : void DBTablePartition::Remove(DBEntryBase *db_entry) {
     109     1149005 :     std::scoped_lock lock(mutex_);
     110     1149084 :     DBEntry *entry = static_cast<DBEntry *>(db_entry);
     111     1149084 :     parent()->AddRemoveCallback(entry, false);
     112             : 
     113     1149009 :     bool success = tree_.erase(*entry);
     114     1148739 :     if (!success) {
     115           0 :         LOG(FATAL, "ABORT: DB node erase failed for table " + parent()->name());
     116           0 :         LOG(FATAL, "Invalid node " + db_entry->ToString());
     117           0 :         abort();
     118             :     }
     119     1148739 :     delete entry;
     120             : 
     121             :     // If a table is marked for deletion, then we may trigger the deletion
     122             :     // process when the last prefix is deleted
     123     1149405 :     if (tree_.empty())
     124      137839 :         table()->RetryDelete();
     125     1149083 : }
     126             : 
     127         399 : void DBTablePartition::AddWithoutAlloc(DBEntry *entry) {
     128         399 :     std::scoped_lock lock(mutex_);
     129         399 :     tree_.insert(*entry);
     130         399 :     entry->set_table_partition(static_cast<DBTablePartBase *>(this));
     131         399 :     Notify(entry);
     132         399 :     parent()->AddRemoveCallback(entry, true);
     133         399 : }
     134             : 
     135         399 : void DBTablePartition::RemoveWithoutDelete(DBEntry *entry) {
     136         399 :     std::scoped_lock lock(mutex_);
     137         399 :     bool success = tree_.erase(*entry);
     138         399 :     if (!success) {
     139           0 :         LOG(FATAL, "ABORT: DB node erase failed for table " + parent()->name());
     140           0 :         abort();
     141             :     }
     142         399 : }
     143             : 
     144     3260991 : DBEntry *DBTablePartition::FindInternal(const DBEntry *entry) {
     145     3260991 :     Tree::iterator loc = tree_.find(*entry);
     146     6521678 :     if (loc != tree_.end()) {
     147     1647046 :         return loc.operator->();
     148             :     }
     149     1613781 :     return NULL;
     150             : }
     151             : 
     152       24101 : const DBEntry *DBTablePartition::FindInternal(const DBEntry *entry) const {
     153       24101 :     Tree::const_iterator loc = tree_.find(*entry);
     154       48202 :     if (loc != tree_.end()) {
     155       16719 :         return loc.operator->();
     156             :     }
     157        7382 :     return NULL;
     158             : }
     159             : 
     160         144 : DBEntry *DBTablePartition::FindNoLock(const DBEntry *entry) {
     161         144 :     CHECK_CONCURRENCY("db::DBTable", "db::IFMapTable",
     162             :         "Agent::FlowEvent", "Agent::FlowUpdate");
     163         144 :     return FindInternal(entry);
     164             : }
     165             : 
     166     2232593 : DBEntry *DBTablePartition::Find(const DBEntry *entry) {
     167     2232593 :     std::scoped_lock lock(mutex_);
     168     4465907 :     return FindInternal(entry);
     169     2232709 : }
     170             : 
     171       24101 : const DBEntry *DBTablePartition::Find(const DBEntry *entry) const {
     172       24101 :     std::scoped_lock lock(mutex_);
     173       48202 :     return FindInternal(entry);
     174       24101 : }
     175             : 
     176          93 : DBEntry *DBTablePartition::FindNoLock(const DBRequestKey *key) {
     177          93 :     CHECK_CONCURRENCY("db::DBTable", "db::IFMapTable",
     178             :         "Agent::FlowEvent", "Agent::FlowUpdate");
     179          93 :     DBTable *table = static_cast<DBTable *>(parent());
     180          93 :     std::unique_ptr<DBEntry> entry_ptr = table->AllocEntry(key);
     181         186 :     return FindInternal(entry_ptr.get());
     182          93 : }
     183             : 
     184     1027890 : DBEntry *DBTablePartition::Find(const DBRequestKey *key) {
     185     1027890 :     DBTable *table = static_cast<DBTable *>(parent());
     186     1027890 :     std::unique_ptr<DBEntry> entry_ptr = table->AllocEntry(key);
     187     1027890 :     std::scoped_lock lock(mutex_);
     188     2055780 :     return FindInternal(entry_ptr.get());
     189     1027890 : }
     190             : 
     191           0 : DBEntry *DBTablePartition::FindNext(const DBRequestKey *key) {
     192           0 :     std::scoped_lock lock(mutex_);
     193           0 :     DBTable *table = static_cast<DBTable *>(parent());
     194           0 :     std::unique_ptr<DBEntry> entry_ptr = table->AllocEntry(key);
     195             : 
     196           0 :     Tree::iterator loc = tree_.upper_bound(*(entry_ptr.get()));
     197           0 :     if (loc != tree_.end()) {
     198           0 :         return loc.operator->();
     199             :     }
     200           0 :     return NULL;
     201           0 : }
     202             : 
     203             : // Returns the matching entry or next in lex order
     204      665340 : DBEntry *DBTablePartition::lower_bound(const DBEntryBase *key) {
     205      665340 :     const DBEntry *entry = static_cast<const DBEntry *>(key);
     206      665340 :     std::scoped_lock lock(mutex_);
     207             : 
     208      665636 :     Tree::iterator it = tree_.lower_bound(*entry);
     209     1331007 :     if (it != tree_.end()) {
     210      665406 :         return (it.operator->());
     211             :     }
     212          97 :     return NULL;
     213      665503 : }
     214             : 
     215     1379213 : DBEntry *DBTablePartition::GetFirst() {
     216     1379213 :     std::scoped_lock lock(mutex_);
     217     1379276 :     Tree::iterator it = tree_.begin();
     218     2758499 :     if (it == tree_.end()) {
     219     1207326 :         return NULL;
     220             :     }
     221      171913 :     return it.operator->();
     222     1379239 : }
     223             : 
     224             : // Returns the next entry (Doesn't search). Threaded walk
     225     1749173 : DBEntry *DBTablePartition::GetNext(const DBEntryBase *key) {
     226     1749173 :     const DBEntry *entry = static_cast<const DBEntry *>(key);
     227     1749173 :     std::scoped_lock lock(mutex_);
     228             : 
     229     1749550 :     Tree::const_iterator it = tree_.iterator_to(*entry);
     230     1749304 :     it++;
     231     3497602 :     if (it != tree_.end()) {
     232     1517155 :         return const_cast<DBEntry *>(it.operator->());
     233             :     }
     234      231508 :     return NULL;
     235     1748663 : }
     236             : 
     237      145211 : DBTable *DBTablePartition::table() {
     238      145211 :     return static_cast<DBTable *>(parent());
     239             : }