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 <sys/socket.h>
7 : #include <sys/types.h>
8 : #if defined(__linux__)
9 : #include <linux/netlink.h>
10 : #include <linux/rtnetlink.h>
11 : #include <linux/sockios.h>
12 : #endif
13 :
14 : #include <boost/bind/bind.hpp>
15 : #include <boost/assign/list_of.hpp>
16 :
17 : #include <base/logging.h>
18 : #include <db/db.h>
19 : #include <db/db_entry.h>
20 : #include <db/db_table.h>
21 : #include <db/db_table_partition.h>
22 :
23 : #include <sandesh/sandesh_trace.h>
24 :
25 : #include "ksync_index.h"
26 : #include "ksync_entry.h"
27 : #include "ksync_object.h"
28 : #include "ksync_types.h"
29 :
30 : using namespace boost::placeholders;
31 :
32 : SandeshTraceBufferPtr KSyncErrorTraceBuf(
33 : SandeshTraceBufferCreate("KSync Error", 5000));
34 :
35 : KSyncObject::FwdRefTree KSyncObject::fwd_ref_tree_;
36 : KSyncObject::BackRefTree KSyncObject::back_ref_tree_;
37 : KSyncObjectManager *KSyncObjectManager::singleton_ = NULL;
38 : std::unique_ptr<KSyncEntry> KSyncObjectManager::default_defer_entry_;
39 :
40 : typedef std::map<uint32_t, std::string> VrouterErrorDescriptionMap;
41 : VrouterErrorDescriptionMap g_error_description =
42 : boost::assign::map_list_of<uint32_t, std::string>
43 : (ENOENT, "Entry not present")
44 : (EBADF, "Key mismatch")
45 : (ENOMEM, "Memory insufficient")
46 : (EBUSY, "Object cannot be modified")
47 : (EEXIST, "Object already present")
48 : (ENODEV, "Object not present")
49 : (EINVAL, "Invalid object parameters")
50 : (ENOSPC, "Object table full");
51 :
52 : // to be used only by test code, for triggering
53 : // stale entry timer callback explicitly
54 5 : void TestTriggerStaleEntryCleanupCb(KSyncObject *obj) {
55 5 : obj->StaleEntryCleanupCb();
56 5 : }
57 :
58 333 : KSyncObject::KSyncObject(const std::string &name) : need_index_(false), index_table_(),
59 333 : delete_scheduled_(false), stale_entry_tree_(),
60 333 : stale_entry_cleanup_timer_(NULL),
61 333 : stale_entry_cleanup_intvl_(0),
62 666 : stale_entries_per_intvl_(0) {
63 333 : KSyncTraceBuf = SandeshTraceBufferCreate(name, 1000);
64 333 : }
65 :
66 10 : KSyncObject::KSyncObject(const std::string &name, int max_index) :
67 10 : need_index_(true), index_table_(max_index),
68 10 : delete_scheduled_(false), stale_entry_tree_(),
69 10 : stale_entry_cleanup_timer_(NULL),
70 10 : stale_entry_cleanup_intvl_(0),
71 20 : stale_entries_per_intvl_(0) {
72 10 : KSyncTraceBuf = SandeshTraceBufferCreate(name, 1000);
73 10 : }
74 :
75 343 : KSyncObject::~KSyncObject() {
76 343 : assert(tree_.size() == 0);
77 343 : if (stale_entry_cleanup_timer_ != NULL) {
78 23 : TimerManager::DeleteTimer(stale_entry_cleanup_timer_);
79 : }
80 343 : }
81 :
82 23 : void KSyncObject::InitStaleEntryCleanup(boost::asio::io_context &ios,
83 : uint32_t cleanup_time,
84 : uint32_t cleanup_intvl,
85 : uint16_t entries_per_intvl) {
86 : // init should be called only once
87 23 : assert(stale_entry_cleanup_timer_ == NULL);
88 23 : stale_entry_cleanup_timer_ = TimerManager::CreateTimer(ios,
89 : "KSync Stale Entry Cleanup Timer",
90 : TaskScheduler::GetInstance()->GetTaskId("Agent::KSync"), 0);
91 23 : stale_entry_cleanup_timer_->Start(cleanup_time,
92 : boost::bind(&KSyncObject::StaleEntryCleanupCb, this));
93 23 : stale_entry_cleanup_intvl_ = cleanup_intvl;
94 23 : stale_entries_per_intvl_ = entries_per_intvl;
95 23 : }
96 :
97 0 : void KSyncObject::Shutdown() {
98 0 : assert(fwd_ref_tree_.size() == 0);
99 0 : assert(back_ref_tree_.size() == 0);
100 0 : }
101 :
102 90228 : KSyncEntry *KSyncObject::Find(const KSyncEntry *key) {
103 90228 : Tree::iterator it = tree_.find(*key);
104 180456 : if (it != tree_.end()) {
105 27372 : return it.operator->();
106 : }
107 :
108 62856 : return NULL;
109 : }
110 :
111 336 : KSyncEntry *KSyncObject::Next(const KSyncEntry *entry) const {
112 336 : std::lock_guard<std::recursive_mutex> lock(lock_);
113 : Tree::const_iterator it;
114 336 : if (entry == NULL) {
115 8 : it = tree_.begin();
116 : } else {
117 332 : it = tree_.iterator_to(*entry);
118 332 : it++;
119 : }
120 672 : if (it != tree_.end()) {
121 332 : return const_cast<KSyncEntry *>(it.operator->());
122 : }
123 4 : return NULL;
124 336 : }
125 5001 : KSyncEntry *KSyncObject::CreateImpl(const KSyncEntry *key) {
126 : // should not create an entry while scheduled for deletion
127 5001 : assert(delete_scheduled_ == false);
128 :
129 : KSyncEntry *entry;
130 5001 : if (need_index_) {
131 414 : entry = Alloc(key, index_table_.Alloc());
132 : } else {
133 4587 : entry = Alloc(key, KSyncEntry::kInvalidIndex);
134 : }
135 5001 : std::pair<Tree::iterator, bool> ret = tree_.insert(*entry);
136 5001 : if (ret.second == false) {
137 : // entry with same key already exists in the Ksync tree
138 : // delete the allocated entry and use the entry available
139 : // in ksync tree
140 1 : delete entry;
141 1 : entry = ret.first.operator->();
142 : } else {
143 : // add reference only if tree insert for newly allocated
144 : // entry succeeds, otherwise reference for tree insertion
145 : // is already accounted for
146 5000 : intrusive_ptr_add_ref(entry);
147 : }
148 5001 : return entry;
149 : }
150 :
151 115 : void KSyncObject::ClearStale(KSyncEntry *entry) {
152 : // Clear stale marked entry and remove from stale entry tree
153 115 : entry->stale_ = false;
154 115 : stale_entry_tree_.erase(entry);
155 115 : }
156 :
157 : // Creates a KSync entry. Calling routine sets no_lookup to TRUE when its
158 : // guaranteed that KSync entry is not present (ex: flow)
159 438 : KSyncEntry *KSyncObject::Create(const KSyncEntry *key, bool no_lookup) {
160 438 : std::lock_guard<std::recursive_mutex> lock(lock_);
161 :
162 438 : KSyncEntry *entry = NULL;
163 438 : if (no_lookup == false)
164 437 : entry = Find(key);
165 438 : if (entry == NULL) {
166 428 : entry = CreateImpl(key);
167 : } else {
168 10 : if (entry->stale_) {
169 : // Clear stale marked entry
170 1 : ClearStale(entry);
171 9 : } else if (entry->GetState() != KSyncEntry::TEMP && !entry->IsDeleted()) {
172 : // If entry is already present, it should be in TEMP state
173 : // or deleted state.
174 0 : assert(0);
175 : }
176 : }
177 :
178 438 : NotifyEvent(entry, KSyncEntry::ADD_CHANGE_REQ);
179 438 : return entry;
180 438 : }
181 :
182 437 : KSyncEntry *KSyncObject::Create(const KSyncEntry *key) {
183 437 : return Create(key, false);
184 : }
185 :
186 116 : KSyncEntry *KSyncObject::CreateStale(const KSyncEntry *key) {
187 : // Should not be called without initialising stale entry
188 : // cleanup InitStaleEntryCleanup
189 116 : assert(stale_entry_cleanup_timer_ != NULL);
190 116 : std::lock_guard<std::recursive_mutex> lock(lock_);
191 116 : KSyncEntry *entry = Find(key);
192 116 : if (entry == NULL) {
193 114 : entry = CreateImpl(key);
194 : } else {
195 2 : if (entry->GetState() != KSyncEntry::TEMP && !entry->IsDeleted()) {
196 : // If entry is already present, it should be in TEMP state
197 : // or deleted state to form a stale entry
198 1 : return NULL;
199 : }
200 : // cleanup associated DB entry for KSyncDBObject
201 : // so that DB operation on this KSyncEntry does not happen
202 : // without re-claiming this entry
203 1 : CleanupOnDel(entry);
204 : }
205 :
206 : // mark the entry stale and add to stale entry tree.
207 115 : entry->stale_ = true;
208 115 : stale_entry_tree_.insert(entry);
209 :
210 115 : NotifyEvent(entry, KSyncEntry::ADD_CHANGE_REQ);
211 : // try starting the timer if not running already
212 115 : stale_entry_cleanup_timer_->Start(stale_entry_cleanup_intvl_,
213 : boost::bind(&KSyncObject::StaleEntryCleanupCb, this));
214 115 : return entry;
215 116 : }
216 :
217 26956 : KSyncEntry *KSyncObject::GetReference(const KSyncEntry *key) {
218 26956 : KSyncEntry *entry = Find(key);
219 :
220 26956 : if (entry != NULL)
221 26570 : return entry;
222 :
223 386 : entry = CreateImpl(key);
224 386 : entry->SetState(KSyncEntry::TEMP);
225 386 : return entry;
226 : }
227 :
228 184 : void KSyncObject::Change(KSyncEntry *entry) {
229 184 : SafeNotifyEvent(entry, KSyncEntry::ADD_CHANGE_REQ);
230 184 : }
231 :
232 561 : void KSyncObject::Delete(KSyncEntry *entry) {
233 561 : if (entry->stale_) {
234 113 : ClearStale(entry);
235 : }
236 561 : SafeNotifyEvent(entry, KSyncEntry::DEL_REQ);
237 561 : }
238 :
239 77 : void KSyncObject::ChangeKey(KSyncEntry *entry, uint32_t arg) {
240 77 : std::lock_guard<std::recursive_mutex> lock(lock_);
241 77 : assert(tree_.erase(*entry) > 0);
242 77 : uint32_t old_key = GetKey(entry);
243 77 : UpdateKey(entry, arg);
244 77 : std::pair<Tree::iterator, bool> ret = tree_.insert(*entry);
245 77 : if (ret.second == false) {
246 : // entry with the same key already exist, to proceed further
247 : // switch place with the existing entry
248 0 : KSyncEntry *current = ret.first.operator->();
249 0 : assert(tree_.erase(*current) > 0);
250 0 : UpdateKey(current, old_key);
251 : // following tree insertions should always pass
252 0 : assert(tree_.insert(*current).second == true);
253 0 : assert(tree_.insert(*entry).second == true);
254 : }
255 77 : }
256 :
257 0 : uint32_t KSyncObject::GetKey(KSyncEntry *entry) {
258 0 : assert(false);
259 : return 0;
260 : }
261 :
262 5000 : void KSyncObject::FreeInd(KSyncEntry *entry, uint32_t index) {
263 5000 : assert(tree_.erase(*entry) > 0);
264 5000 : if (need_index_ == true && index != KSyncEntry::kInvalidIndex) {
265 413 : index_table_.Free(index);
266 : }
267 5000 : PreFree(entry);
268 5000 : Free(entry);
269 5000 : }
270 :
271 4852 : void KSyncObject::Free(KSyncEntry *entry) {
272 4852 : delete entry;
273 4852 : }
274 :
275 3009 : void KSyncObject::SafeNotifyEvent(KSyncEntry *entry,
276 : KSyncEntry::KSyncEvent event) {
277 3009 : std::lock_guard<std::recursive_mutex> lock(lock_);
278 3009 : NotifyEvent(entry, event);
279 3009 : }
280 :
281 : ///////////////////////////////////////////////////////////////////////////////
282 : // KSyncDBObject routines
283 : ///////////////////////////////////////////////////////////////////////////////
284 314 : KSyncDBObject::KSyncDBObject(const std::string &name) : KSyncObject(name), test_id_(-1) {
285 314 : table_ = NULL;
286 314 : }
287 :
288 2 : KSyncDBObject::KSyncDBObject(const std::string &name,
289 2 : int max_index) : KSyncObject(name, max_index), test_id_(-1) {
290 2 : table_ = NULL;
291 2 : }
292 :
293 15 : KSyncDBObject::KSyncDBObject(const std::string &name,
294 15 : DBTableBase *table) : KSyncObject(name), test_id_(-1) {
295 15 : table_ = table;
296 15 : id_ = table->Register(boost::bind(&KSyncDBObject::Notify, this, _1, _2));
297 15 : }
298 :
299 0 : KSyncDBObject::KSyncDBObject(const std::string &name,
300 0 : DBTableBase *table, int max_index)
301 0 : : KSyncObject(name, max_index), test_id_(-1) {
302 0 : table_ = table;
303 0 : id_ = table->Register(boost::bind(&KSyncDBObject::Notify, this, _1, _2));
304 0 : }
305 :
306 331 : KSyncDBObject::~KSyncDBObject() {
307 331 : if (table_) {
308 26 : UnregisterDb(table_);
309 : }
310 331 : }
311 :
312 308 : void KSyncDBObject::RegisterDb(DBTableBase *table) {
313 308 : assert(table_ == NULL);
314 308 : table_ = table;
315 308 : id_ = table->Register(boost::bind(&KSyncDBObject::Notify, this, _1, _2));
316 308 : }
317 :
318 323 : void KSyncDBObject::UnregisterDb(DBTableBase *table) {
319 323 : assert(table_ == table);
320 323 : table_->Unregister(id_);
321 323 : id_ = -1;
322 323 : table_ = NULL;
323 323 : }
324 :
325 3170 : KSyncDBObject::DBFilterResp KSyncDBObject::DBEntryFilter(
326 : const DBEntry *entry, const KSyncDBEntry *ksync) {
327 : // Default accept all
328 3170 : return DBFilterAccept;
329 : }
330 :
331 0 : void KSyncDBObject::set_test_id(DBTableBase::ListenerId id) {
332 0 : test_id_ = id;
333 0 : }
334 :
335 1 : DBTableBase::ListenerId KSyncDBObject::GetListenerId(DBTableBase *table) {
336 1 : assert(table_ == table);
337 1 : if (test_id_ != -1) {
338 0 : return test_id_;
339 : }
340 1 : return id_;
341 : }
342 :
343 4447 : void KSyncDBObject::CleanupOnDel(KSyncEntry *entry) {
344 4447 : KSyncDBEntry *kentry = static_cast<KSyncDBEntry *>(entry);
345 4447 : if (kentry->GetDBEntry() != NULL) {
346 : // when object is created only because of reference it will be in
347 : // temp state without DB entry, deletion of which doesn't need
348 : // this cleanup
349 4369 : kentry->GetDBEntry()->ClearState(table_, id_);
350 4369 : kentry->SetDBEntry(NULL);
351 : }
352 :
353 4447 : if (delete_scheduled()) {
354 : // we are in cleanup process remove all duplicate entries
355 2 : while (kentry->dup_entry_list_.empty() == false) {
356 : // and clear db entry state
357 1 : kentry->dup_entry_list_.front()->ClearState(table_, id_);
358 1 : kentry->dup_entry_list_.pop_front();
359 : }
360 : }
361 4447 : }
362 :
363 : // DBTable notification handler.
364 : // Generates events for the KSyncEntry state-machine based DBEntry
365 : // Stores the KSyncEntry allocated as DBEntry-state
366 13906 : void KSyncDBObject::Notify(DBTablePartBase *partition, DBEntryBase *e) {
367 13906 : std::lock_guard<std::recursive_mutex> lock(lock_);
368 13906 : DBEntry *entry = static_cast<DBEntry *>(e);
369 13906 : DBTableBase *table = partition->parent();
370 13906 : assert(table_ == table);
371 : KSyncDBEntry *ksync =
372 13906 : static_cast<KSyncDBEntry *>(entry->GetState(table, id_));
373 13906 : DBFilterResp resp = DBFilterAccept;
374 :
375 : // cleanup is in-process, ignore All db notifications.
376 13906 : if (delete_scheduled()) {
377 0 : return;
378 : }
379 :
380 : // Trigger DB Filter callback only for ADD/CHANGE, since we need to handle
381 : // cleanup for delete anyways.
382 13906 : if (!entry->IsDeleted()) {
383 9497 : resp = DBEntryFilter(entry, ksync);
384 : }
385 :
386 13906 : if (entry->IsDeleted() || resp == DBFilterDelete ||
387 : resp == DBFilterDelAdd) {
388 4413 : if (ksync != NULL) {
389 : // Check if there is any entry present in dup_entry_list
390 4370 : if (!ksync->dup_entry_list_.empty()) {
391 : // Check if entry getting deleted is actively associated with
392 : // Ksync Entry.
393 5 : if (entry == ksync->GetDBEntry()) {
394 : // clean up db entry state.
395 4 : CleanupOnDel(ksync);
396 4 : ksync->SetDBEntry(ksync->dup_entry_list_.front());
397 4 : ksync->dup_entry_list_.pop_front();
398 :
399 : // DB entry association changed, trigger re-sync.
400 4 : if (ksync->Sync(ksync->GetDBEntry())) {
401 4 : NotifyEvent(ksync, KSyncEntry::ADD_CHANGE_REQ);
402 : }
403 : } else {
404 : // iterate through entries and delete the
405 : // corresponding DB ref.
406 1 : KSyncDBEntry::DupEntryList::iterator it_dup;
407 1 : for (it_dup = ksync->dup_entry_list_.begin();
408 1 : it_dup != ksync->dup_entry_list_.end(); ++it_dup) {
409 1 : if (entry == *it_dup)
410 1 : break;
411 : }
412 : // something bad has happened if we fail to find the entry.
413 1 : assert(it_dup != ksync->dup_entry_list_.end());
414 1 : ksync->dup_entry_list_.erase(it_dup);
415 1 : entry->ClearState(table_, id_);
416 : }
417 : } else {
418 4365 : if (resp == DBFilterDelAdd) {
419 : // clean up db entry state, so that other ksync entry can
420 : // replace the states appropriately.
421 : // cleanup needs to be triggered before notifying delete
422 : // after that ksync entry might be already free'd
423 1 : CleanupOnDel(ksync);
424 : }
425 : // We may get duplicate delete notification in
426 : // case of db entry reuse
427 : // add -> change ->delete(Notify) -> change -> delete(Notify)
428 : // delete and change gets suppresed as delete and we get
429 : // a duplicate delete notification
430 4365 : if (ksync->IsDeleted() == false) {
431 4364 : NotifyEvent(ksync, KSyncEntry::DEL_REQ);
432 : }
433 : }
434 : }
435 4413 : if (resp != DBFilterDelAdd) {
436 : // return from here except for DBFilterDelAdd case, where
437 : // ADD needs to be triggered after Delete
438 4410 : return;
439 : }
440 : // reset ksync entry pointer, as ksync and DB entry is already
441 : // dissassociated
442 3 : ksync = NULL;
443 : }
444 :
445 9496 : if (resp == DBFilterIgnore) {
446 : // DB filter tells us to ignore this Add/Change.
447 9 : return;
448 : }
449 :
450 9487 : bool need_sync = false;
451 9487 : if (ksync == NULL) {
452 : KSyncEntry *key, *found;
453 :
454 : // TODO : Memory is allocated and freed only for lookup. Fix this.
455 4371 : key = DBToKSyncEntry(entry);
456 4371 : found = Find(key);
457 4371 : if (found == NULL) {
458 3999 : ksync = static_cast<KSyncDBEntry *>(CreateImpl(key));
459 : } else {
460 372 : ksync = static_cast<KSyncDBEntry *>(found);
461 372 : if (ksync->stale()) {
462 : // Clear stale marked entry and remove from stale entry tree
463 1 : ClearStale(ksync);
464 : }
465 : }
466 4371 : delete key;
467 4371 : entry->SetState(table, id_, ksync);
468 : // Allow reuse of KSync Entry if the previous associated DB Entry
469 : // is marked deleted. This can happen when Key for OPER DB entry
470 : // deferes from that used in KSync Object.
471 4371 : DBEntry *old_db_entry = ksync->GetDBEntry();
472 4371 : if (old_db_entry != NULL) {
473 : // cleanup previous state id the old db entry is delete marked.
474 7 : if (old_db_entry->IsDeleted()) {
475 1 : CleanupOnDel(ksync);
476 : } else {
477 : // In case Oper DB and Ksync use different Keys, its
478 : // possible to have multiple Oper DB entries pointing to
479 : // same Ksync Entry.
480 : // add the entry to dup_entry_list and return
481 6 : ksync->dup_entry_list_.push_back(entry);
482 6 : return;
483 : }
484 : }
485 4365 : ksync->SetDBEntry(entry);
486 4365 : need_sync = true;
487 : } else {
488 : // ignore change on non-associated entry.
489 5116 : if (entry != ksync->GetDBEntry()) {
490 1 : return;
491 : }
492 : }
493 :
494 9480 : if (ksync->IsDeleted()) {
495 : // ksync entry was marked as delete, sync required.
496 1 : need_sync = true;
497 : }
498 :
499 9480 : if (ksync->Sync(entry) || need_sync) {
500 6548 : NotifyEvent(ksync, KSyncEntry::ADD_CHANGE_REQ);
501 : }
502 13906 : }
503 :
504 : ///////////////////////////////////////////////////////////////////////////////
505 : // KSyncEntry routines
506 : ///////////////////////////////////////////////////////////////////////////////
507 25686 : bool KSyncEntry::IsResolved() {
508 25686 : KSyncObject *obj = GetObject();
509 25686 : if (obj->IsIndexValid() && index_ == kInvalidIndex)
510 0 : return false;
511 25686 : if (IsDataResolved() == false)
512 0 : return false;
513 25686 : return ((state_ >= IN_SYNC) && (state_ < DEL_DEFER_SYNC));
514 : }
515 :
516 7 : std::string KSyncEntry::VrouterErrorToString(uint32_t error) {
517 : std::map<uint32_t, std::string>::iterator iter =
518 7 : g_error_description.find(error);
519 7 : if (iter == g_error_description.end())
520 1 : return strerror(error);
521 6 : return iter->second;
522 : }
523 :
524 3 : std::string KSyncEntry::VrouterError(uint32_t error) const {
525 3 : return VrouterErrorToString(error);
526 : }
527 :
528 4 : void KSyncEntry::ErrorHandler(int err, uint32_t seq_no,
529 : KSyncEvent event) const {
530 4 : if (err == 0) {
531 1 : return;
532 : }
533 3 : std::string error_msg = VrouterError(err);
534 3 : KSYNC_ERROR(VRouterError, "VRouter operation failed. Error <", err,
535 : ":", error_msg, ">. Object <", ToString(),
536 : ">. Operation <", AckOperationString(event),
537 : ">. Message number :", seq_no);
538 :
539 3 : std::stringstream sstr;
540 3 : sstr << "VRouter operation failed. Error <" << err << ":" << error_msg <<
541 0 : ">. Object <" << ToString() << ">. Operation <" <<
542 3 : AckOperationString(event) << ">. Message number :" << seq_no;
543 3 : KSYNC_ERROR_TRACE(Trace, sstr.str().c_str());
544 3 : LOG(ERROR, sstr.str().c_str());
545 3 : }
546 :
547 6 : std::string KSyncEntry::AckOperationString(KSyncEvent event) const {
548 6 : switch(event) {
549 0 : case ADD_ACK:
550 0 : return "Addition";
551 :
552 2 : case CHANGE_ACK:
553 2 : return "Change";
554 :
555 2 : case DEL_ACK:
556 2 : return "Deletion";
557 :
558 2 : default:
559 : // AckOperationString should track only acks, if something else is
560 : // passed convert it to EventString
561 2 : return EventString(event);
562 : }
563 : }
564 :
565 29305 : std::string KSyncEntry::StateString() const {
566 29305 : std::stringstream str;
567 :
568 29305 : switch (state_) {
569 4466 : case INIT:
570 4466 : str << "Init";
571 4466 : break;
572 :
573 393 : case TEMP:
574 393 : str << "Temp";
575 393 : break;
576 :
577 3353 : case ADD_DEFER:
578 3353 : str << "Add defer";
579 3353 : break;
580 :
581 1038 : case CHANGE_DEFER:
582 1038 : str << "Change defer";
583 1038 : break;
584 :
585 6501 : case IN_SYNC:
586 6501 : str << "In sync";
587 6501 : break;
588 :
589 6481 : case SYNC_WAIT:
590 6481 : str << "Sync wait";
591 6481 : break;
592 :
593 499 : case NEED_SYNC:
594 499 : str << "Need sync";
595 499 : break;
596 :
597 8 : case DEL_DEFER_SYNC:
598 8 : str << "Delete defer sync";
599 8 : break;
600 :
601 2102 : case DEL_DEFER_REF:
602 2102 : str << "Delete pending due to reference";
603 2102 : break;
604 :
605 3 : case DEL_DEFER_DEL_ACK:
606 3 : str << "Delete pending due to Delete ack wait";
607 3 : break;
608 :
609 4450 : case DEL_ACK_WAIT:
610 4450 : str << "Delete ack wait";
611 4450 : break;
612 :
613 11 : case RENEW_WAIT:
614 11 : str << "Renew wait";
615 11 : break;
616 :
617 0 : case FREE_WAIT:
618 0 : str << "Free wait";
619 0 : break;
620 : }
621 :
622 29305 : if (stale_) {
623 116 : str << " (Stale entry) ";
624 : }
625 :
626 29305 : str << '(' << state_ << ')';
627 29305 : str << '(' << refcount_ << ')';
628 58610 : return str.str();
629 29305 : }
630 :
631 29307 : std::string KSyncEntry::EventString(KSyncEvent event) const {
632 29307 : std::stringstream str;
633 29307 : switch (event) {
634 7056 : case ADD_CHANGE_REQ:
635 7056 : str << "Add/Change request";
636 7056 : break;
637 :
638 4444 : case ADD_ACK:
639 4444 : str << "Add Ack";
640 4444 : break;
641 :
642 2036 : case CHANGE_ACK:
643 2036 : str << "Change ack";
644 2036 : break;
645 :
646 4851 : case DEL_REQ:
647 4851 : str << "Delete request";
648 4851 : break;
649 :
650 8 : case DEL_ADD_REQ:
651 8 : str << "Delete followed by Add request";
652 8 : break;
653 :
654 4455 : case DEL_ACK:
655 4455 : str << "Delete ack";
656 4455 : break;
657 :
658 4341 : case RE_EVAL:
659 4341 : str << "Re-evaluate";
660 4341 : break;
661 :
662 2116 : case INT_PTR_REL:
663 2116 : str << "Reference release";
664 2116 : break;
665 0 : case INVALID:
666 0 : str << "Invalid";
667 0 : break;
668 : }
669 29307 : str << '(' << event << ')';
670 58614 : return str.str();
671 29307 : }
672 :
673 79237 : void intrusive_ptr_add_ref(KSyncEntry *p) {
674 79237 : p->refcount_++;
675 79237 : };
676 :
677 : // KSync adds a reference to object when its created.
678 : // Delete the object if reference falls to 1 and either
679 : // (i) delete was deferred due to refcount or
680 : // (ii) the ksync entry is in TEMP state.
681 79237 : void intrusive_ptr_release(KSyncEntry *p) {
682 79237 : if (--p->refcount_ == 1) {
683 6287 : KSyncObject *obj = p->GetObject();
684 6287 : switch(p->state_) {
685 2264 : case KSyncEntry::TEMP:
686 : // FALLTHRU
687 : case KSyncEntry::DEL_DEFER_REF:
688 2264 : obj->SafeNotifyEvent(p, KSyncEntry::INT_PTR_REL);
689 2264 : break;
690 4023 : default:
691 4023 : break;
692 : }
693 : }
694 79237 : }
695 :
696 : ///////////////////////////////////////////////////////////////////////////////
697 : // KSyncEntry state machine.
698 : //
699 : // Brief description of States:
700 : //
701 : // INIT : KSyncEntry created. No events notified to the object yet
702 : // TEMP : Temporary object created either due to reference or on
703 : // process restart.
704 : // Ex: Obj-A refers to Obj-B. If Obj-B is not present when Obj-A
705 : // is to be sent, then Obj-B is created in TEMP state
706 : //
707 : // ADD_DEFER : Object deferred since it has some unmet constraints.
708 : // Ex: Obj-A refers to Obj-B. Obj-B is not yet added to kernel.
709 : // Obj-A will get to ADD_DEFER state
710 : // Obj-A goes into BackRefTree for Obj-B.
711 : // Creation of Obj-B will take Obj-A out of this state
712 : // CHANGE_DEFER : Object already added to kernel, subsequent change deferred
713 : // since it has some unmet constraints.
714 : // Ex: Obj-A refers to Obj-B. Obj-B is not yet added to kernel.
715 : // Obj-A will get to ADD_DEFER state
716 : // Obj-A goes into BackRefTree for Obj-B.
717 : // Add of Obj-B will take Obj-A out of this state
718 : // IN_SYNC : Object in-sync with kernel
719 : // SYNC_WAIT : Add or Change sent to kernel. Waiting for ACK from Kernel
720 : // NEED_SYNC : Object out-of-sync with kernel. Need to send a change message
721 : // to sync kernel state
722 : // DEL_DEFER_SYNC:Object deleted when waiting for ACK from kernel. Delete must
723 : // be sent to kernel on getting ACK
724 : // DEL_DEFER_REF: Object deleted with pending references . Delete must be sent
725 : // to kernel when all pending references goes away.
726 : // DEL_DEFER_DEL_ACK: Object delete with pending delete ack wait, Delete
727 : // needs to be sent after receiving a del ACK.
728 : // DEL_ACK_WAIT : Delete sent to Kernel. Waiting for ACK from kernel.
729 : // Can get renewed if there is request to ADD in this case
730 : // RENEW_WAIT : Object being renewed. Waiting for ACK of delete to renew the
731 : // object
732 : // FREE_WAIT : Object marked to be freed at the end of this function call.
733 : // Can only be a temporary state
734 : //
735 : // Brief description of Events:
736 : // ADD_CHANGE_REQ : Request to Add or Change an entry
737 : // ADD_ACK, : Ack from kernel for ADD request
738 : // CHANGE_ACK : Ack from kernel for CHANGE request
739 : // DEL_REQ : Request to DEL an entry
740 : // DEL_ADD_REQ : Request to DEL an entry followed by ADD for the same
741 : // DEL_ACK : Ack from kernel for DEL request
742 : // RE_EVAL : Event to re-evaluate dependencies.
743 : // Ex: If Obj-A is added into Obj-B back-ref tree
744 : // When Obj-B is created, RE_EVAL is sent to Obj-A
745 : ///////////////////////////////////////////////////////////////////////////////
746 :
747 : // Utility function to handle Add of KSyncEntry.
748 : // If operation is complete, move state to IN_SYNC. Else move to SYNC_WAIT
749 8336 : KSyncEntry::KSyncState KSyncSM_Add(KSyncObject *obj, KSyncEntry *entry) {
750 : KSyncEntry *dep;
751 8336 : if ((dep = entry->UnresolvedReference()) != NULL) {
752 3353 : obj->BackRefAdd(entry, dep);
753 3353 : return KSyncEntry::ADD_DEFER;
754 : }
755 :
756 4983 : entry->SetSeen();
757 4983 : if (entry->Add()) {
758 391 : return KSyncEntry::IN_SYNC;
759 : } else {
760 4592 : return KSyncEntry::SYNC_WAIT;
761 : }
762 : }
763 :
764 : // Utility function to handle Change of KSyncEntry.
765 : // If operation is complete, move state to IN_SYNC. Else move to SYNC_WAIT
766 3249 : KSyncEntry::KSyncState KSyncSM_Change(KSyncObject *obj, KSyncEntry *entry) {
767 : KSyncEntry *dep;
768 :
769 3249 : assert(entry->Seen());
770 3249 : if ((dep = entry->UnresolvedReference()) != NULL) {
771 1038 : obj->BackRefAdd(entry, dep);
772 1038 : return KSyncEntry::CHANGE_DEFER;
773 : }
774 :
775 2211 : if (entry->Change()) {
776 93 : return KSyncEntry::IN_SYNC;
777 : } else {
778 2118 : return KSyncEntry::SYNC_WAIT;
779 : }
780 : }
781 :
782 : // Utility function to handle Delete of KSyncEntry.
783 : // If there are more references to the object, then move it to DEL_DEFER
784 : // state. Object will be deleted when all references drop. If object is
785 : // still not seen by Kernel yet we don't have to delete it.
786 : //
787 : // If operation is complete, move state to IN_SYNC. Else move to SYNC_WAIT
788 7086 : KSyncEntry::KSyncState KSyncSM_Delete(KSyncEntry *entry) {
789 7086 : if (entry->GetRefCount() > 1) {
790 2102 : return KSyncEntry::DEL_DEFER_REF;
791 : }
792 :
793 4984 : assert(entry->GetRefCount() == 1);
794 4984 : if (!entry->Seen() && entry->AllowDeleteStateComp()) {
795 0 : return KSyncEntry::FREE_WAIT;
796 : }
797 4984 : if (entry->Delete()) {
798 387 : return KSyncEntry::FREE_WAIT;
799 : } else {
800 4597 : return KSyncEntry::DEL_ACK_WAIT;
801 : }
802 : }
803 :
804 : // Utility function to handle Delete followed by ADD of KSyncEntry.
805 : // delete is triggered irrespective of the references to the object
806 : // followed by ADD of the object
807 : //
808 : // If operation is complete, move state to IN_SYNC. Else move to SYNC_WAIT
809 7 : KSyncEntry::KSyncState KSyncSM_DeleteAdd(KSyncObject *obj, KSyncEntry *entry) {
810 : // DeleteAdd operation is not supported/defined for stale entries
811 : // when such an operation is required for stale entry, it must be
812 : // sufficient to trigger only a delete and let Add happen when
813 : // entry is ready to become non-stale
814 7 : assert(!entry->stale());
815 :
816 : // NOTE this API doesnot support managing references for delete trigger
817 7 : if (entry->Seen() || !entry->AllowDeleteStateComp()) {
818 7 : if (!entry->Delete()) {
819 : // move to renew wait to trigger Add on DEL_ACK
820 6 : return KSyncEntry::RENEW_WAIT;
821 : }
822 : }
823 :
824 1 : return KSyncSM_Add(obj, entry);
825 : }
826 :
827 : //
828 : //
829 : // ADD_CHANGE_REQ :
830 : // If entry has unresolved references, move it to ADD_DEFER
831 : // Else, send ADD message and move to SYNC_WAIT state
832 : //
833 : // No other events are expected in this state
834 4614 : KSyncEntry::KSyncState KSyncSM_Init(KSyncObject *obj, KSyncEntry *entry,
835 : KSyncEntry::KSyncEvent event) {
836 4614 : KSyncEntry::KSyncState state = KSyncEntry::INIT;
837 :
838 4614 : assert(entry->GetRefCount());
839 4614 : switch (event) {
840 4614 : case KSyncEntry::ADD_CHANGE_REQ:
841 4614 : state = KSyncSM_Add(obj, entry);
842 4614 : break;
843 :
844 0 : default:
845 0 : assert(0);
846 : break;
847 : }
848 :
849 4614 : return state;
850 : }
851 :
852 : // ADD_CHANGE_REQ :
853 : // ADD_CHANGE_REQ event for an entry in TEMP state.
854 : // If entry has unresolved references, move it to ADD_DEFER
855 : // Else, send ADD message and move to SYNC_WAIT state
856 : //
857 : // DEL_REQ :
858 : // DEL_REQ event for an entry in TEMP state. Can happen only when reference
859 : // for the TEMP entry is dropped
860 : //
861 : // Explicit DEL_REQ event is not expected. This is enforced by checking
862 : // ref-count
863 : //
864 : // Event notified when refcount for object goes to 1 In TEMP state.
865 : // Entry not sent to kernel, so dont send delete message
866 : // Delete object in this state
867 : //
868 541 : KSyncEntry::KSyncState KSyncSM_Temp(KSyncObject *obj, KSyncEntry *entry,
869 : KSyncEntry::KSyncEvent event) {
870 541 : KSyncEntry::KSyncState state = KSyncEntry::TEMP;
871 :
872 541 : assert(entry->GetRefCount());
873 541 : switch (event) {
874 375 : case KSyncEntry::ADD_CHANGE_REQ:
875 : case KSyncEntry::DEL_ADD_REQ:
876 375 : state = KSyncSM_Add(obj, entry);
877 375 : break;
878 :
879 166 : case KSyncEntry::INT_PTR_REL:
880 : case KSyncEntry::DEL_REQ:
881 166 : if (entry->GetRefCount() == 1) {
882 165 : state = KSyncEntry::FREE_WAIT;
883 : }
884 166 : break;
885 :
886 0 : default:
887 0 : assert(0);
888 : break;
889 : }
890 :
891 541 : return state;
892 : }
893 :
894 : // ADD_CHANGE_REQ :
895 : // ADD_CHANGE_REQ event for an entry in ADD_DEFER state.
896 : // Remove the old dependency constraint.
897 : // Re-evaluate to see if there are any further unmet dependencies
898 : //
899 : // RE_EVAL:
900 : // Triggred from back-ref tree when KSyncEntry waited on is added to Kernel
901 : // Entry would already be removed from backref tree
902 : // Re-evaluate to see if there are any further unmet dependencies
903 : //
904 : // DEL_REQ :
905 : // Delete when entry is not yet added to kernel. Dont delete entry. Move state
906 : // based on ref-count
907 3353 : KSyncEntry::KSyncState KSyncSM_AddDefer(KSyncObject *obj, KSyncEntry *entry,
908 : KSyncEntry::KSyncEvent event) {
909 3353 : KSyncEntry::KSyncState state = KSyncEntry::ADD_DEFER;
910 :
911 3353 : assert(entry->GetRefCount());
912 3353 : switch (event) {
913 26 : case KSyncEntry::ADD_CHANGE_REQ:
914 26 : obj->BackRefDel(entry);
915 : // FALLTHRU
916 3339 : case KSyncEntry::RE_EVAL:
917 3339 : state = KSyncSM_Add(obj, entry);
918 3339 : break;
919 :
920 : // Remove any back-ref entry
921 : // Free entry if there are no more references. Else wait in TEMP
922 : // state for either release of reference or for movement to different
923 : // state.
924 13 : case KSyncEntry::DEL_REQ:
925 13 : obj->BackRefDel(entry);
926 13 : if (entry->AllowDeleteStateComp() == false) {
927 5 : state = KSyncSM_Delete(entry);
928 8 : } else if (entry->GetRefCount() > 1) {
929 4 : state = KSyncEntry::TEMP;
930 : } else {
931 4 : state = KSyncEntry::FREE_WAIT;
932 : }
933 13 : break;
934 :
935 1 : case KSyncEntry::DEL_ADD_REQ:
936 1 : obj->BackRefDel(entry);
937 1 : state = KSyncSM_DeleteAdd(obj, entry);
938 1 : break;
939 :
940 0 : case KSyncEntry::INT_PTR_REL:
941 0 : break;
942 :
943 0 : default:
944 0 : assert(0);
945 : break;
946 : }
947 :
948 3353 : return state;
949 : }
950 :
951 : // ADD_CHANGE_REQ :
952 : // ADD_CHANGE_REQ event for an entry in CHANGE_DEFER state.
953 : // Remove the old dependency constraint.
954 : // Re-evaluate to see if there are any further unmet dependencies
955 : //
956 : // RE_EVAL:
957 : // Triggred from back-ref tree when KSyncEntry waited on is added to Kernel
958 : // Entry would already be removed from backref tree
959 : // Re-evaluate to see if there are any further unmet dependencies
960 : //
961 : // DEL_REQ :
962 : // Move state based on ref-count.
963 1038 : KSyncEntry::KSyncState KSyncSM_ChangeDefer(KSyncObject *obj, KSyncEntry *entry,
964 : KSyncEntry::KSyncEvent event) {
965 1038 : KSyncEntry::KSyncState state = KSyncEntry::CHANGE_DEFER;
966 :
967 1038 : assert(entry->GetRefCount());
968 1038 : switch (event) {
969 10 : case KSyncEntry::ADD_CHANGE_REQ:
970 10 : obj->BackRefDel(entry);
971 : // FALLTHRU
972 1036 : case KSyncEntry::RE_EVAL:
973 1036 : state = KSyncSM_Change(obj, entry);
974 1036 : break;
975 :
976 : // Remove any back-ref entry and process delete
977 2 : case KSyncEntry::DEL_REQ:
978 2 : obj->BackRefDel(entry);
979 2 : state = KSyncSM_Delete(entry);
980 2 : break;
981 :
982 0 : case KSyncEntry::DEL_ADD_REQ:
983 0 : obj->BackRefDel(entry);
984 0 : state = KSyncSM_DeleteAdd(obj, entry);
985 0 : break;
986 :
987 0 : case KSyncEntry::INT_PTR_REL:
988 0 : break;
989 :
990 0 : default:
991 0 : assert(0);
992 : break;
993 : }
994 :
995 1038 : return state;
996 : }
997 :
998 : // Object state IN-SYNC with kernel
999 : //
1000 : // ADD_CHANGE_REQ :
1001 : // Invoke Change on the object
1002 : //
1003 : // DEL_REQ :
1004 : // Delete of entry that is already added to kernel.
1005 6731 : KSyncEntry::KSyncState KSyncSM_InSync(KSyncObject *obj, KSyncEntry *entry,
1006 : KSyncEntry::KSyncEvent event) {
1007 6731 : KSyncEntry::KSyncState state = KSyncEntry::IN_SYNC;
1008 :
1009 6731 : assert(entry->GetRefCount());
1010 6731 : switch (event) {
1011 1758 : case KSyncEntry::ADD_CHANGE_REQ:
1012 1758 : state = KSyncSM_Change(obj, entry);
1013 1758 : break;
1014 :
1015 4972 : case KSyncEntry::DEL_REQ:
1016 4972 : state = KSyncSM_Delete(entry);
1017 4972 : break;
1018 :
1019 1 : case KSyncEntry::DEL_ADD_REQ:
1020 1 : state = KSyncSM_DeleteAdd(obj, entry);
1021 1 : break;
1022 :
1023 0 : case KSyncEntry::INT_PTR_REL:
1024 0 : break;
1025 :
1026 0 : default:
1027 0 : assert(0);
1028 : break;
1029 : }
1030 :
1031 6731 : return state;
1032 : }
1033 :
1034 : // Entry waiting on ACK or Add or Change
1035 : // If event is change request, move to NEED_SYNC
1036 : // If event is delete request, move to DEL_DEFER for references to drop
1037 6711 : KSyncEntry::KSyncState KSyncSM_SyncWait(KSyncObject *obj, KSyncEntry *entry,
1038 : KSyncEntry::KSyncEvent event) {
1039 6711 : KSyncEntry::KSyncState state = KSyncEntry::SYNC_WAIT;
1040 :
1041 6711 : assert(entry->GetRefCount());
1042 6711 : switch (event) {
1043 455 : case KSyncEntry::ADD_CHANGE_REQ:
1044 455 : state = KSyncEntry::NEED_SYNC;
1045 455 : break;
1046 :
1047 6248 : case KSyncEntry::ADD_ACK:
1048 : case KSyncEntry::CHANGE_ACK:
1049 6248 : if (entry->del_add_pending()) {
1050 : // del_add_pending trigger DeleteAdd
1051 1 : entry->set_del_add_pending(false);
1052 1 : state = KSyncSM_DeleteAdd(obj, entry);
1053 : } else {
1054 6247 : state = KSyncEntry::IN_SYNC;
1055 : }
1056 6248 : break;
1057 :
1058 7 : case KSyncEntry::DEL_REQ:
1059 7 : state = KSyncEntry::DEL_DEFER_SYNC;
1060 7 : entry->set_del_add_pending(false);
1061 7 : break;
1062 :
1063 1 : case KSyncEntry::DEL_ADD_REQ:
1064 : // entry is waiting for Ack, mark del_add_pending flag
1065 : // to trigger DeleteAdd on receiving Ack
1066 1 : entry->set_del_add_pending(true);
1067 1 : break;
1068 :
1069 0 : case KSyncEntry::INT_PTR_REL:
1070 0 : break;
1071 :
1072 0 : default:
1073 0 : assert(0);
1074 : break;
1075 : }
1076 :
1077 6711 : return state;
1078 : }
1079 :
1080 : // NEED_SYNC state means object was modified while waiting for ACK
1081 576 : KSyncEntry::KSyncState KSyncSM_NeedSync(KSyncObject *obj, KSyncEntry *entry,
1082 : KSyncEntry::KSyncEvent event) {
1083 576 : KSyncEntry::KSyncState state = KSyncEntry::NEED_SYNC;
1084 :
1085 576 : assert(entry->GetRefCount());
1086 576 : switch (event) {
1087 : // Continue in NEED_SYNC state on change
1088 120 : case KSyncEntry::ADD_CHANGE_REQ:
1089 120 : break;
1090 :
1091 : // Wait for ACK to arrive in DEL_DEFER_SYNC state
1092 1 : case KSyncEntry::DEL_REQ:
1093 1 : state = KSyncEntry::DEL_DEFER_SYNC;
1094 1 : entry->set_del_add_pending(false);
1095 1 : break;
1096 :
1097 0 : case KSyncEntry::DEL_ADD_REQ:
1098 : // entry is waiting for Ack, mark del_add_pending flag
1099 : // to trigger DeleteAdd on receiving Ack
1100 0 : entry->set_del_add_pending(true);
1101 0 : break;
1102 :
1103 : // Try to resend on getting ACK of pending operation
1104 455 : case KSyncEntry::ADD_ACK:
1105 : case KSyncEntry::CHANGE_ACK:
1106 455 : if (entry->del_add_pending()) {
1107 : // del_add_pending trigger DeleteAdd
1108 1 : entry->set_del_add_pending(false);
1109 1 : state = KSyncSM_DeleteAdd(obj, entry);
1110 : } else {
1111 454 : state = KSyncSM_Change(obj, entry);
1112 : }
1113 455 : break;
1114 :
1115 0 : case KSyncEntry::INT_PTR_REL:
1116 0 : break;
1117 :
1118 0 : default:
1119 0 : assert(0);
1120 : break;
1121 : }
1122 :
1123 576 : return state;
1124 : }
1125 :
1126 : // Object waiting for DELETE to be sent.
1127 : // ADD_CHANGE_REQ will result in renew of object. Send only a Change
1128 : // On ADD/CHANGE ACK, try sending delete
1129 8 : KSyncEntry::KSyncState KSyncSM_DelPending_Sync(KSyncObject *obj,
1130 : KSyncEntry *entry,
1131 : KSyncEntry::KSyncEvent event) {
1132 8 : KSyncEntry::KSyncState state = KSyncEntry::DEL_DEFER_SYNC;
1133 :
1134 8 : assert(entry->GetRefCount());
1135 8 : switch (event) {
1136 0 : case KSyncEntry::ADD_CHANGE_REQ:
1137 0 : state = KSyncEntry::NEED_SYNC;
1138 0 : break;
1139 :
1140 1 : case KSyncEntry::DEL_ADD_REQ:
1141 : // entry is waiting for Ack, mark del_add_pending flag
1142 : // to trigger DeleteAdd on receiving Ack
1143 1 : entry->set_del_add_pending(true);
1144 1 : state = KSyncEntry::NEED_SYNC;
1145 1 : break;
1146 :
1147 7 : case KSyncEntry::ADD_ACK:
1148 : case KSyncEntry::CHANGE_ACK:
1149 7 : state = KSyncSM_Delete(entry);
1150 7 : break;
1151 :
1152 0 : case KSyncEntry::INT_PTR_REL:
1153 0 : break;
1154 :
1155 0 : default:
1156 0 : assert(0);
1157 : break;
1158 : }
1159 :
1160 8 : return state;
1161 : }
1162 :
1163 : // Object waiting for DELETE to be sent.
1164 : // ADD_CHANGE_REQ will result in renew of object. Send only a Change
1165 : // On ADD/CHANGE ACK, try sending delete
1166 2102 : KSyncEntry::KSyncState KSyncSM_DelPending_Ref(KSyncObject *obj,
1167 : KSyncEntry *entry,
1168 : KSyncEntry::KSyncEvent event) {
1169 2102 : KSyncEntry::KSyncState state = KSyncEntry::DEL_DEFER_REF;
1170 :
1171 2102 : assert(entry->GetRefCount());
1172 2102 : switch (event) {
1173 2 : case KSyncEntry::ADD_CHANGE_REQ:
1174 2 : if (!entry->Seen()) {
1175 : // Trigger Add if entry was not seen earlier
1176 1 : state = KSyncSM_Add(obj, entry);
1177 : } else {
1178 1 : state = KSyncSM_Change(obj, entry);
1179 : }
1180 2 : break;
1181 :
1182 2099 : case KSyncEntry::INT_PTR_REL:
1183 : case KSyncEntry::DEL_REQ:
1184 2099 : assert(entry->GetRefCount()== 1);
1185 2099 : state = KSyncSM_Delete(entry);
1186 2099 : break;
1187 :
1188 1 : case KSyncEntry::DEL_ADD_REQ:
1189 1 : state = KSyncSM_DeleteAdd(obj, entry);
1190 1 : break;
1191 :
1192 0 : default:
1193 0 : assert(0);
1194 : break;
1195 : }
1196 :
1197 2102 : return state;
1198 : }
1199 :
1200 : // Object waiting for DELETE to be sent.
1201 : // ADD_CHANGE_REQ will result in renew of object. Send only a Change
1202 : // On DEL ACK, try sending delete
1203 3 : KSyncEntry::KSyncState KSyncSM_DelPending_DelAck(KSyncObject *obj,
1204 : KSyncEntry *entry,
1205 : KSyncEntry::KSyncEvent event) {
1206 3 : KSyncEntry::KSyncState state = KSyncEntry::DEL_DEFER_DEL_ACK;
1207 :
1208 3 : assert(entry->GetRefCount());
1209 3 : assert(entry->AllowDeleteStateComp() == false);
1210 :
1211 3 : switch (event) {
1212 0 : case KSyncEntry::ADD_CHANGE_REQ:
1213 0 : state = KSyncEntry::RENEW_WAIT;
1214 0 : entry->set_del_add_pending(false);
1215 0 : break;
1216 :
1217 2 : case KSyncEntry::DEL_ACK:
1218 2 : if (entry->del_add_pending()) {
1219 : // del_add_pending trigger DeleteAdd
1220 1 : entry->set_del_add_pending(false);
1221 1 : state = KSyncSM_DeleteAdd(obj, entry);
1222 : } else {
1223 1 : state = KSyncSM_Delete(entry);
1224 : }
1225 2 : break;
1226 :
1227 1 : case KSyncEntry::DEL_ADD_REQ:
1228 : // entry is waiting for Ack, mark del_add_pending flag
1229 : // to trigger DeleteAdd on receiving Ack
1230 1 : entry->set_del_add_pending(true);
1231 1 : break;
1232 :
1233 0 : case KSyncEntry::INT_PTR_REL:
1234 0 : break;
1235 :
1236 0 : default:
1237 0 : assert(0);
1238 : break;
1239 : }
1240 :
1241 3 : return state;
1242 : }
1243 :
1244 : // Object waiting for ACK of DELETE sent earlier
1245 : // ADD_CHANGE_REQ will result in renew of object. TODO: This is TBD
1246 4598 : KSyncEntry::KSyncState KSyncSM_DelAckWait(KSyncObject *obj, KSyncEntry *entry,
1247 : KSyncEntry::KSyncEvent event) {
1248 4598 : KSyncEntry::KSyncState state = KSyncEntry::DEL_ACK_WAIT;
1249 :
1250 4598 : assert(entry->GetRefCount());
1251 4598 : switch (event) {
1252 4 : case KSyncEntry::ADD_CHANGE_REQ:
1253 4 : state = KSyncEntry::RENEW_WAIT;
1254 4 : entry->set_del_add_pending(false);
1255 4 : break;
1256 :
1257 4594 : case KSyncEntry::DEL_ACK:
1258 4594 : if (entry->del_add_pending()) {
1259 : // del_add_pending trigger DeleteAdd
1260 0 : entry->set_del_add_pending(false);
1261 0 : state = KSyncSM_DeleteAdd(obj, entry);
1262 : } else {
1263 4594 : if (entry->GetRefCount() > 1) {
1264 150 : state = KSyncEntry::TEMP;
1265 : } else {
1266 4444 : state = KSyncEntry::FREE_WAIT;
1267 : }
1268 : }
1269 4594 : break;
1270 :
1271 0 : case KSyncEntry::DEL_ADD_REQ:
1272 : // entry is waiting for Ack, mark del_add_pending flag
1273 : // to trigger DeleteAdd on receiving Ack
1274 0 : entry->set_del_add_pending(true);
1275 0 : break;
1276 :
1277 0 : case KSyncEntry::INT_PTR_REL:
1278 0 : break;
1279 :
1280 0 : default:
1281 0 : assert(0);
1282 : break;
1283 : }
1284 :
1285 4598 : return state;
1286 : }
1287 :
1288 : // TODO: Object renewal. This is not yet handled
1289 11 : KSyncEntry::KSyncState KSyncSM_RenewWait(KSyncObject *obj, KSyncEntry *entry,
1290 : KSyncEntry::KSyncEvent event) {
1291 11 : KSyncEntry::KSyncState state = KSyncEntry::RENEW_WAIT;
1292 :
1293 11 : assert(entry->GetRefCount());
1294 11 : switch (event) {
1295 0 : case KSyncEntry::ADD_CHANGE_REQ:
1296 0 : entry->set_del_add_pending(false);
1297 0 : break;
1298 :
1299 3 : case KSyncEntry::DEL_REQ:
1300 3 : entry->set_del_add_pending(false);
1301 3 : if (entry->AllowDeleteStateComp()) {
1302 1 : state = KSyncEntry::DEL_ACK_WAIT;
1303 : } else {
1304 2 : state = KSyncEntry::DEL_DEFER_DEL_ACK;
1305 : }
1306 3 : break;
1307 :
1308 1 : case KSyncEntry::DEL_ADD_REQ:
1309 : // entry is waiting for Ack, mark del_add_pending flag
1310 : // to trigger DeleteAdd on receiving Ack
1311 1 : entry->set_del_add_pending(true);
1312 1 : break;
1313 :
1314 7 : case KSyncEntry::DEL_ACK:
1315 7 : if (entry->del_add_pending()) {
1316 : // del_add_pending trigger DeleteAdd
1317 1 : entry->set_del_add_pending(false);
1318 1 : state = KSyncSM_DeleteAdd(obj, entry);
1319 : } else {
1320 6 : state = KSyncSM_Add(obj, entry);
1321 : }
1322 7 : break;
1323 :
1324 0 : case KSyncEntry::INT_PTR_REL:
1325 0 : break;
1326 :
1327 0 : default:
1328 0 : assert(0);
1329 : break;
1330 : }
1331 :
1332 11 : return state;
1333 : }
1334 :
1335 30286 : void KSyncObject::NotifyEvent(KSyncEntry *entry, KSyncEntry::KSyncEvent event) {
1336 :
1337 : KSyncEntry::KSyncState state;
1338 30286 : bool dep_reval = false;
1339 30286 : KSyncEntry::KSyncState from_state = entry->GetState();
1340 :
1341 30286 : if (DoEventTrace()) {
1342 29305 : std::string obj_string(entry->ToString());
1343 29305 : std::string state_string(entry->StateString());
1344 29305 : std::string event_string(entry->EventString(event));
1345 29305 : KSYNC_TRACE(Event, this, obj_string, state_string,
1346 : event_string);
1347 29305 : }
1348 30286 : switch (entry->GetState()) {
1349 4614 : case KSyncEntry::INIT:
1350 4614 : state = KSyncSM_Init(this, entry, event);
1351 4614 : break;
1352 :
1353 541 : case KSyncEntry::TEMP:
1354 541 : dep_reval = true;
1355 541 : state = KSyncSM_Temp(this, entry, event);
1356 541 : break;
1357 :
1358 3353 : case KSyncEntry::ADD_DEFER:
1359 3353 : dep_reval = true;
1360 3353 : state = KSyncSM_AddDefer(this, entry, event);
1361 3353 : break;
1362 :
1363 1038 : case KSyncEntry::CHANGE_DEFER:
1364 1038 : dep_reval = true;
1365 1038 : state = KSyncSM_ChangeDefer(this, entry, event);
1366 1038 : break;
1367 :
1368 6731 : case KSyncEntry::IN_SYNC:
1369 6731 : state = KSyncSM_InSync(this, entry, event);
1370 6731 : break;
1371 :
1372 6711 : case KSyncEntry::SYNC_WAIT:
1373 6711 : dep_reval = true;
1374 6711 : state = KSyncSM_SyncWait(this, entry, event);
1375 6711 : break;
1376 :
1377 576 : case KSyncEntry::NEED_SYNC:
1378 576 : state = KSyncSM_NeedSync(this, entry, event);
1379 576 : break;
1380 :
1381 8 : case KSyncEntry::DEL_DEFER_SYNC:
1382 8 : state = KSyncSM_DelPending_Sync(this, entry, event);
1383 8 : break;
1384 :
1385 2102 : case KSyncEntry::DEL_DEFER_REF:
1386 2102 : dep_reval = true;
1387 2102 : state = KSyncSM_DelPending_Ref(this, entry, event);
1388 2102 : break;
1389 :
1390 3 : case KSyncEntry::DEL_DEFER_DEL_ACK:
1391 3 : state = KSyncSM_DelPending_DelAck(this, entry, event);
1392 3 : break;
1393 :
1394 4598 : case KSyncEntry::DEL_ACK_WAIT:
1395 4598 : state = KSyncSM_DelAckWait(this, entry, event);
1396 4598 : break;
1397 :
1398 11 : case KSyncEntry::RENEW_WAIT:
1399 11 : dep_reval = true;
1400 11 : state = KSyncSM_RenewWait(this, entry, event);
1401 11 : break;
1402 :
1403 0 : default:
1404 0 : assert(0);
1405 : break;
1406 : }
1407 :
1408 30286 : entry->SetState(state);
1409 30286 : entry->RecordTransition(from_state, state, event);
1410 :
1411 40161 : if (dep_reval == true && entry->IsResolved() &&
1412 9876 : entry->ShouldReEvalBackReference()) {
1413 9646 : BackRefReEval(entry);
1414 : }
1415 :
1416 30285 : if (state == KSyncEntry::FREE_WAIT || state == KSyncEntry::TEMP) {
1417 5154 : CleanupOnDel(entry);
1418 : }
1419 :
1420 30286 : if (state == KSyncEntry::FREE_WAIT) {
1421 5000 : intrusive_ptr_release(entry);
1422 5000 : FreeInd(entry, entry->GetIndex());
1423 : }
1424 :
1425 30286 : if (tree_.empty() == true) {
1426 334 : EmptyTable();
1427 : }
1428 30285 : }
1429 :
1430 11270 : void KSyncObject::NetlinkAckInternal(KSyncEntry *entry, KSyncEntry::KSyncEvent event) {
1431 11270 : std::lock_guard<std::recursive_mutex> lock(lock_);
1432 11270 : entry->Response();
1433 11270 : NotifyEvent(entry, event);
1434 11270 : }
1435 :
1436 5 : bool KSyncObject::StaleEntryCleanupCb() {
1437 : // donot reschedule timer if no stale entries
1438 5 : if (stale_entry_tree_.empty()) {
1439 2 : return false;
1440 : }
1441 :
1442 3 : uint32_t count = 0;
1443 3 : std::set<KSyncEntry::KSyncEntryPtr>::iterator it = stale_entry_tree_.begin();
1444 6 : while (it != stale_entry_tree_.end()) {
1445 4 : if (count == stale_entries_per_intvl_) {
1446 1 : break;
1447 : }
1448 3 : KSyncEntry *entry = (*it).get();
1449 : // Notify entry of stale timer expiration
1450 3 : entry->StaleTimerExpired();
1451 : // Delete removes entry from stale entry tree
1452 3 : Delete(entry);
1453 3 : it = stale_entry_tree_.begin();
1454 3 : count++;
1455 : }
1456 :
1457 : // iterate entries and trigger delete
1458 3 : return stale_entry_cleanup_timer_->Reschedule(stale_entry_cleanup_intvl_);
1459 : }
1460 :
1461 11270 : void KSyncObject::NetlinkAck(KSyncEntry *entry, KSyncEntry::KSyncEvent event) {
1462 11270 : NetlinkAckInternal(entry, event);
1463 11270 : }
1464 :
1465 : ///////////////////////////////////////////////////////////////////////////////
1466 : // KSyncEntry dependency management
1467 : ///////////////////////////////////////////////////////////////////////////////
1468 4391 : void KSyncObject::BackRefAdd(KSyncEntry *key, KSyncEntry *reference) {
1469 4391 : KSyncFwdReference *fwd_node = new KSyncFwdReference(key, reference);
1470 : FwdRefTree::iterator fwd_it = fwd_ref_tree_.find(*fwd_node);
1471 8782 : assert(fwd_it == fwd_ref_tree_.end());
1472 4391 : fwd_ref_tree_.insert(*fwd_node);
1473 4391 : intrusive_ptr_add_ref(key);
1474 4391 : intrusive_ptr_add_ref(reference);
1475 :
1476 4391 : KSyncBackReference *back_node = new KSyncBackReference(reference, key);
1477 : BackRefTree::iterator back_it = back_ref_tree_.find(*back_node);
1478 8782 : assert(back_it == back_ref_tree_.end());
1479 4391 : back_ref_tree_.insert(*back_node);
1480 4391 : }
1481 :
1482 4391 : void KSyncObject::BackRefDel(KSyncEntry *key) {
1483 4391 : KSyncFwdReference fwd_search_node(key, NULL);
1484 : FwdRefTree::iterator fwd_it = fwd_ref_tree_.find(fwd_search_node);
1485 8782 : if (fwd_it == fwd_ref_tree_.end()) {
1486 0 : return;
1487 : }
1488 4391 : KSyncFwdReference *entry = fwd_it.operator->();
1489 4391 : KSyncEntry *reference = entry->reference_;
1490 4391 : fwd_ref_tree_.erase(fwd_it);
1491 4391 : delete entry;
1492 :
1493 4391 : KSyncBackReference back_search_node(reference, key);
1494 : BackRefTree::iterator back_it = back_ref_tree_.find(back_search_node);
1495 8782 : assert(back_it != back_ref_tree_.end());
1496 4391 : KSyncBackReference *back_node = back_it.operator->();
1497 4391 : back_ref_tree_.erase(back_it);
1498 4391 : delete back_node;
1499 :
1500 4391 : intrusive_ptr_release(key);
1501 4391 : intrusive_ptr_release(reference);
1502 4391 : }
1503 :
1504 9646 : void KSyncObject::BackRefReEval(KSyncEntry *key) {
1505 9646 : std::vector<KSyncEntry *> buf;
1506 9646 : KSyncBackReference node(key, NULL);
1507 :
1508 9646 : for (BackRefTree::iterator it = back_ref_tree_.upper_bound(node);
1509 27970 : it != back_ref_tree_.end(); ) {
1510 : BackRefTree::iterator it_work = it;
1511 :
1512 8499 : KSyncBackReference *entry = it_work.operator->();
1513 8499 : if (entry->key_ != key) {
1514 4160 : break;
1515 : }
1516 4339 : KSyncEntry *back_ref = entry->back_reference_;
1517 4339 : buf.push_back(back_ref);
1518 4339 : BackRefDel(entry->back_reference_);
1519 4339 : it = back_ref_tree_.upper_bound(node);
1520 : }
1521 :
1522 9646 : std::vector<KSyncEntry *>::iterator it = buf.begin();
1523 13985 : while (it != buf.end()) {
1524 4339 : std::lock_guard<std::recursive_mutex> lock((*it)->GetObject()->lock_);
1525 4339 : NotifyEvent(*it, KSyncEntry::RE_EVAL);
1526 4339 : it++;
1527 4339 : }
1528 9646 : }
1529 :
1530 307 : bool KSyncObjectManager::Process(KSyncObjectEvent *event) {
1531 307 : switch(event->event_) {
1532 297 : case KSyncObjectEvent::UNREGISTER:
1533 297 : if (event->obj_->Size() == 0) {
1534 297 : delete event->obj_;
1535 : }
1536 297 : break;
1537 10 : case KSyncObjectEvent::DEL:
1538 : {
1539 10 : int count = 0;
1540 : // hold reference to entry to ensure the pointer sanity
1541 10 : KSyncEntry::KSyncEntryPtr entry(NULL);
1542 10 : if (event->ref_.get() == NULL) {
1543 7 : event->obj_->set_delete_scheduled();
1544 7 : if (event->obj_->IsEmpty()) {
1545 : // trigger explicit empty table callback for client to
1546 : // complete deletion of object in KSync Context.
1547 3 : event->obj_->EmptyTable();
1548 3 : break;
1549 : }
1550 : // get the first entry to start with
1551 4 : entry = event->obj_->Next(NULL);
1552 : } else {
1553 3 : entry = event->ref_.get();
1554 : }
1555 :
1556 : // hold reference to entry to ensure the pointer sanity
1557 : // next entry can get free'd in certain cases while processing
1558 : // current entry
1559 7 : KSyncEntry::KSyncEntryPtr next_entry(NULL);
1560 336 : while (entry.get() != NULL) {
1561 332 : next_entry = event->obj_->Next(entry.get());
1562 332 : count++;
1563 332 : if (entry->IsDeleted() == false) {
1564 : // trigger delete if entry is not marked delete already.
1565 331 : event->obj_->Delete(entry.get());
1566 : }
1567 :
1568 332 : if (count == kMaxEntriesProcess && next_entry.get() != NULL) {
1569 : // update reference with which entry to start with
1570 : // in next iteration.
1571 3 : event->ref_ = next_entry.get();
1572 : // yeild and re-enqueue event for processing later.
1573 3 : event_queue_->Enqueue(event);
1574 :
1575 : // release reference to deleted entry.
1576 3 : entry = NULL;
1577 3 : return false;
1578 : }
1579 329 : entry = next_entry.get();
1580 : }
1581 4 : break;
1582 17 : }
1583 0 : default:
1584 0 : assert(0);
1585 : }
1586 304 : delete event;
1587 304 : return true;
1588 : }
1589 :
1590 304 : void KSyncObjectManager::Enqueue(KSyncObjectEvent *event) {
1591 304 : event_queue_->Enqueue(event);
1592 304 : }
1593 :
1594 297 : void KSyncObjectManager::Unregister(KSyncObject *table) {
1595 : KSyncObjectEvent *event = new KSyncObjectEvent(table,
1596 297 : KSyncObjectEvent::UNREGISTER);
1597 297 : singleton_->Enqueue(event);
1598 297 : }
1599 :
1600 4 : KSyncObjectManager::KSyncObjectManager() {
1601 8 : event_queue_ = new WorkQueue<KSyncObjectEvent *>
1602 8 : (TaskScheduler::GetInstance()->GetTaskId("Agent::KSync"), 0,
1603 4 : boost::bind(&KSyncObjectManager::Process, this, _1));
1604 4 : }
1605 :
1606 1 : KSyncObjectManager::~KSyncObjectManager() {
1607 1 : delete event_queue_;
1608 1 : }
1609 :
1610 4 : KSyncObjectManager *KSyncObjectManager::Init() {
1611 4 : if (singleton_ == NULL) {
1612 4 : singleton_ = new KSyncObjectManager();
1613 : }
1614 4 : return singleton_;
1615 : }
1616 :
1617 1 : void KSyncObjectManager::Shutdown() {
1618 1 : if (singleton_) {
1619 1 : delete singleton_;
1620 : }
1621 1 : singleton_ = NULL;
1622 1 : }
1623 :
1624 : // Create a KSync Object event to trigger Delete of all the KSync Entries
1625 : // present in the given object.
1626 : // Once the delete is scheduled new entry creation is not allowed for this
1627 : // object and EmptyTable callback is trigger when all the entries of given
1628 : // object are cleaned up. As part of which client can delete the object.
1629 : //
1630 : // This API can be used to clean up KSync objects irrespective of config
1631 : // or oper tables
1632 :
1633 7 : void KSyncObjectManager::Delete(KSyncObject *object) {
1634 : KSyncObjectEvent *event = new KSyncObjectEvent(object,
1635 7 : KSyncObjectEvent::DEL);
1636 7 : Enqueue(event);
1637 7 : }
1638 :
1639 0 : KSyncObjectManager* KSyncObjectManager::GetInstance() {
1640 0 : return singleton_;
1641 : }
1642 :
1643 : // Create a dummy KSync Entry. This entry will all ways be in deferred state
1644 : // Any back-ref added to it will never get resolved.
1645 : // Can be used to defer an incomplete entry
1646 :
1647 : class KSyncDummyEntry : public KSyncEntry {
1648 : public:
1649 1 : KSyncDummyEntry() : KSyncEntry() { }
1650 2 : virtual ~KSyncDummyEntry() { }
1651 0 : virtual bool IsLess(const KSyncEntry &rhs) const {
1652 0 : return false;
1653 : }
1654 1 : std::string ToString() const { return "Dummy"; }
1655 0 : bool Add() { return false;}
1656 0 : bool Change() { return false; }
1657 0 : bool Delete() { return false; }
1658 1 : KSyncObject *GetObject() const { return NULL; }
1659 0 : KSyncEntry *UnresolvedReference() { return NULL; }
1660 1 : bool IsDataResolved() {return false;}
1661 : private:
1662 : DISALLOW_COPY_AND_ASSIGN(KSyncDummyEntry);
1663 : };
1664 :
1665 1 : KSyncEntry *KSyncObjectManager::default_defer_entry() {
1666 1 : if (default_defer_entry_.get() == NULL) {
1667 1 : default_defer_entry_.reset(new KSyncDummyEntry());
1668 : }
1669 1 : return default_defer_entry_.get();
1670 : }
|
