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 190456 : void DBTablePartBase::Notify(DBEntryBase *entry) { 19 190456 : if (entry->is_onlist()) { 20 71980 : return; 21 : } 22 118429 : entry->set_onlist(); 23 119548 : bool was_empty = change_list_.empty(); 24 119548 : change_list_.push_back(*entry); 25 120139 : if (was_empty) { 26 64545 : DB *db = parent()->database(); 27 64542 : DBPartition *partition = db->GetPartition(index_); 28 64540 : 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 64531 : bool DBTablePartBase::RunNotify() { 42 185320 : for (int i = 0; ((i < kMaxIterations) && !change_list_.empty()); ++i) { 43 120763 : DBEntryBase *entry = &change_list_.front(); 44 120734 : change_list_.pop_front(); 45 : 46 120718 : parent()->RunNotify(this, entry); 47 120818 : 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 135455 : if (entry->IsDeleted() && entry->is_state_empty(this) && 58 14658 : !entry->IsOnRemoveQ()) { 59 14640 : Remove(entry); 60 : } 61 : } 62 : 63 64508 : if (!change_list_.empty()) { 64 4 : DB *db = parent()->database(); 65 2 : DBPartition *partition = db->GetPartition(index_); 66 2 : partition->OnTableChange(this); 67 2 : return false; 68 : } 69 64510 : return true; 70 : } 71 : 72 50747 : void DBTablePartBase::Delete(DBEntryBase *entry) { 73 50747 : if (parent_->HasListeners()) { 74 43641 : entry->MarkDelete(); 75 43640 : Notify(entry); 76 : } else { 77 : // Remove from change_list 78 7109 : if (entry->is_onlist()) { 79 78 : change_list_.erase(change_list_.iterator_to(*entry)); 80 : } 81 7109 : Remove(entry); 82 : } 83 50747 : } 84 : 85 34369 : DBTablePartition::DBTablePartition(DBTable *table, int index) 86 34369 : : DBTablePartBase(table, index) { 87 34369 : } 88 : 89 64140 : void DBTablePartition::Process(DBClient *client, DBRequest *req) { 90 64140 : DBTable *table = static_cast<DBTable *>(parent()); 91 64139 : table->incr_input_count(); 92 64139 : table->Input(this, client, req); 93 64139 : } 94 : 95 50590 : void DBTablePartition::Add(DBEntry *entry) { 96 50590 : std::scoped_lock lock(mutex_); 97 50603 : std::pair<Tree::iterator, bool> ret = tree_.insert(*entry); 98 50575 : assert(ret.second); 99 50575 : entry->set_table_partition(static_cast<DBTablePartBase *>(this)); 100 50575 : Notify(entry); 101 50588 : parent()->AddRemoveCallback(entry, true); 102 50585 : } 103 : 104 9310 : void DBTablePartition::Change(DBEntry *entry) { 105 9310 : std::scoped_lock lock(mutex_); 106 9310 : Notify(entry); 107 9310 : } 108 : 109 50565 : void DBTablePartition::Remove(DBEntryBase *db_entry) { 110 50565 : std::scoped_lock lock(mutex_); 111 50583 : DBEntry *entry = static_cast<DBEntry *>(db_entry); 112 50583 : parent()->AddRemoveCallback(entry, false); 113 : 114 50552 : bool success = tree_.erase(*entry); 115 50539 : 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 50539 : 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 50587 : if (tree_.empty()) 125 3028 : table()->RetryDelete(); 126 50578 : } 127 : 128 482 : void DBTablePartition::AddWithoutAlloc(DBEntry *entry) { 129 482 : std::scoped_lock lock(mutex_); 130 482 : tree_.insert(*entry); 131 482 : entry->set_table_partition(static_cast<DBTablePartBase *>(this)); 132 482 : Notify(entry); 133 482 : parent()->AddRemoveCallback(entry, true); 134 482 : } 135 : 136 482 : void DBTablePartition::RemoveWithoutDelete(DBEntry *entry) { 137 482 : std::scoped_lock lock(mutex_); 138 482 : bool success = tree_.erase(*entry); 139 482 : if (!success) { 140 0 : LOG(FATAL, "ABORT: DB node erase failed for table " + parent()->name()); 141 0 : abort(); 142 : } 143 482 : } 144 : 145 229392 : DBEntry *DBTablePartition::FindInternal(const DBEntry *entry) { 146 229392 : Tree::iterator loc = tree_.find(*entry); 147 458720 : if (loc != tree_.end()) { 148 163307 : return loc.operator->(); 149 : } 150 66052 : return NULL; 151 : } 152 : 153 0 : const DBEntry *DBTablePartition::FindInternal(const DBEntry *entry) const { 154 0 : Tree::const_iterator loc = tree_.find(*entry); 155 0 : if (loc != tree_.end()) { 156 0 : return loc.operator->(); 157 : } 158 0 : 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 84234 : DBEntry *DBTablePartition::Find(const DBEntry *entry) { 168 84234 : std::scoped_lock lock(mutex_); 169 168549 : return FindInternal(entry); 170 84232 : } 171 : 172 0 : const DBEntry *DBTablePartition::Find(const DBEntry *entry) const { 173 0 : std::scoped_lock lock(mutex_); 174 0 : return FindInternal(entry); 175 0 : } 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 144974 : DBEntry *DBTablePartition::Find(const DBRequestKey *key) { 186 144974 : DBTable *table = static_cast<DBTable *>(parent()); 187 144974 : std::unique_ptr<DBEntry> entry_ptr = table->AllocEntry(key); 188 144974 : std::scoped_lock lock(mutex_); 189 289948 : return FindInternal(entry_ptr.get()); 190 144974 : } 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 53716 : DBEntry *DBTablePartition::lower_bound(const DBEntryBase *key) { 206 53716 : const DBEntry *entry = static_cast<const DBEntry *>(key); 207 53716 : std::scoped_lock lock(mutex_); 208 : 209 53832 : Tree::iterator it = tree_.lower_bound(*entry); 210 107542 : if (it != tree_.end()) { 211 53767 : return (it.operator->()); 212 : } 213 3 : return NULL; 214 53769 : } 215 : 216 41221 : DBEntry *DBTablePartition::GetFirst() { 217 41221 : std::scoped_lock lock(mutex_); 218 41232 : Tree::iterator it = tree_.begin(); 219 82460 : if (it == tree_.end()) { 220 35824 : return NULL; 221 : } 222 5405 : return it.operator->(); 223 41229 : } 224 : 225 : // Returns the next entry (Doesn't search). Threaded walk 226 123485 : DBEntry *DBTablePartition::GetNext(const DBEntryBase *key) { 227 123485 : const DBEntry *entry = static_cast<const DBEntry *>(key); 228 123485 : std::scoped_lock lock(mutex_); 229 : 230 123668 : Tree::const_iterator it = tree_.iterator_to(*entry); 231 123582 : it++; 232 246725 : if (it != tree_.end()) { 233 114413 : return const_cast<DBEntry *>(it.operator->()); 234 : } 235 8894 : return NULL; 236 123307 : } 237 : 238 8934 : DBTable *DBTablePartition::table() { 239 8934 : return static_cast<DBTable *>(parent()); 240 : }