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