From 12d615b3c546211b48ee75921f0e06371dd62dae Mon Sep 17 00:00:00 2001 From: Patrick Donnelly Date: Thu, 7 Sep 2017 21:01:31 -0700 Subject: [PATCH] common: refactor of lru Avoids an unnecessary "max" size of the LRU which was used to calculate the midpoint. Instead, just dynamically move the LRUObjects between top and bottom on-the-fly. This change is necessary for a cache which which does not limit by the number of objects but by some other metric. (In this case, memory.) Signed-off-by: Patrick Donnelly --- src/client/Client.cc | 14 +- src/client/Client.h | 1 - src/include/lru.h | 322 +++++++++++++----------------------- src/mds/MDCache.cc | 2 - src/mds/MDCache.h | 2 - src/test/common/test_lru.cc | 131 +++++++++------ 6 files changed, 196 insertions(+), 276 deletions(-) diff --git a/src/client/Client.cc b/src/client/Client.cc index 1c256cecd90..18051806b5e 100644 --- a/src/client/Client.cc +++ b/src/client/Client.cc @@ -272,7 +272,6 @@ Client::Client(Messenger *m, MonClient *mc, Objecter *objecter_) if (cct->_conf->client_acl_type == "posix_acl") acl_type = POSIX_ACL; - lru.lru_set_max(cct->_conf->client_cache_size); lru.lru_set_midpoint(cct->_conf->client_cache_mid); // file handles @@ -332,7 +331,6 @@ void Client::tear_down_cache() // *** FIXME *** // empty lru - lru.lru_set_max(0); trim_cache(); assert(lru.lru_get_size() == 0); @@ -601,12 +599,13 @@ void Client::shutdown() void Client::trim_cache(bool trim_kernel_dcache) { - ldout(cct, 20) << "trim_cache size " << lru.lru_get_size() << " max " << lru.lru_get_max() << dendl; + uint64_t max = cct->_conf->client_cache_size; + ldout(cct, 20) << "trim_cache size " << lru.lru_get_size() << " max " << max << dendl; unsigned last = 0; while (lru.lru_get_size() != last) { last = lru.lru_get_size(); - if (lru.lru_get_size() <= lru.lru_get_max()) break; + if (!unmounting && lru.lru_get_size() <= max) break; // trim! Dentry *dn = static_cast(lru.lru_get_next_expire()); @@ -616,7 +615,7 @@ void Client::trim_cache(bool trim_kernel_dcache) trim_dentry(dn); } - if (trim_kernel_dcache && lru.lru_get_size() > lru.lru_get_max()) + if (trim_kernel_dcache && lru.lru_get_size() > max) _invalidate_kernel_dcache(); // hose root? @@ -5921,7 +5920,6 @@ void Client::unmount() wait_sync_caps(last_flush_tid); // empty lru cache - lru.lru_set_max(0); trim_cache(); while (lru.lru_get_size() > 0 || @@ -13751,9 +13749,7 @@ void Client::handle_conf_change(const struct md_config_t *conf, { Mutex::Locker lock(client_lock); - if (changed.count("client_cache_size") || - changed.count("client_cache_mid")) { - lru.lru_set_max(cct->_conf->client_cache_size); + if (changed.count("client_cache_mid")) { lru.lru_set_midpoint(cct->_conf->client_cache_mid); } if (changed.count("client_acl_type")) { diff --git a/src/client/Client.h b/src/client/Client.h index cb940a61b48..16aef0312c1 100644 --- a/src/client/Client.h +++ b/src/client/Client.h @@ -503,7 +503,6 @@ protected: friend void intrusive_ptr_release(Inode *in); //int get_cache_size() { return lru.lru_get_size(); } - //void set_cache_size(int m) { lru.lru_set_max(m); } /** * Don't call this with in==NULL, use get_or_create for that diff --git a/src/include/lru.h b/src/include/lru.h index e88cedc60b2..d04e94f19a4 100644 --- a/src/include/lru.h +++ b/src/include/lru.h @@ -17,283 +17,164 @@ #ifndef CEPH_LRU_H #define CEPH_LRU_H +#include #include #include "common/config.h" - - +#include "xlist.h" class LRUObject { - private: - LRUObject *lru_next, *lru_prev; - bool lru_pinned; - class LRU *lru; - class LRUList *lru_list; - - public: - LRUObject() { - lru_next = lru_prev = NULL; - lru_list = 0; - lru_pinned = false; - lru = 0; - } +public: + LRUObject() : lru(), lru_link(this), lru_pinned(false) { } + ~LRUObject(); // pin/unpin item in cache - void lru_pin(); + void lru_pin(); void lru_unpin(); bool lru_is_expireable() const { return !lru_pinned; } friend class LRU; - friend class LRUList; +private: + class LRU *lru; + xlist::item lru_link; + bool lru_pinned; }; +class LRU { +public: + LRU() : num_pinned(0), midpoint(0.6) {} -class LRUList { - private: - LRUObject *head, *tail; - uint32_t len; + uint64_t lru_get_size() const { return lru_get_top()+lru_get_bot()+lru_get_pintail(); } + uint64_t lru_get_top() const { return top.size(); } + uint64_t lru_get_bot() const{ return bottom.size(); } + uint64_t lru_get_pintail() const { return pintail.size(); } + uint64_t lru_get_num_pinned() const { return num_pinned; } - public: - LRUList() { - head = tail = 0; - len = 0; - } + void lru_set_midpoint(double f) { midpoint = fmin(1.0, fmax(0.0, f)); } - uint32_t get_length() const { return len; } - - LRUObject *get_head() { - return head; - } - LRUObject *get_tail() { - return tail; - } - - void clear() { - while (len > 0) { - remove(get_head()); + void lru_clear() { + while (!top.empty()) { + lru_remove(top.front()); } - } - - void insert_head(LRUObject *o) { - o->lru_next = head; - o->lru_prev = NULL; - if (head) { - head->lru_prev = o; - } else { - tail = o; + while (!bottom.empty()) { + lru_remove(bottom.front()); } - head = o; - o->lru_list = this; - len++; - } - void insert_tail(LRUObject *o) { - o->lru_next = NULL; - o->lru_prev = tail; - if (tail) { - tail->lru_next = o; - } else { - head = o; + while (!pintail.empty()) { + lru_remove(pintail.front()); } - tail = o; - o->lru_list = this; - len++; - } - - void remove(LRUObject *o) { - assert(o->lru_list == this); - if (o->lru_next) - o->lru_next->lru_prev = o->lru_prev; - else - tail = o->lru_prev; - if (o->lru_prev) - o->lru_prev->lru_next = o->lru_next; - else - head = o->lru_next; - o->lru_next = o->lru_prev = NULL; - o->lru_list = 0; - assert(len>0); - len--; - } - -}; - - -class LRU { - protected: - LRUList lru_top, lru_bot, lru_pintail; - uint32_t lru_num, lru_num_pinned; - uint32_t lru_max; // max items - double lru_midpoint; - - friend class LRUObject; - //friend class MDCache; // hack - - public: - LRU(int max = 0) { - lru_num = 0; - lru_num_pinned = 0; - lru_midpoint = .6; - lru_max = max; - } - - uint32_t lru_get_size() const { return lru_num; } - uint32_t lru_get_top() const { return lru_top.get_length(); } - uint32_t lru_get_bot() const{ return lru_bot.get_length(); } - uint32_t lru_get_pintail() const { return lru_pintail.get_length(); } - uint32_t lru_get_max() const { return lru_max; } - uint32_t lru_get_num_pinned() const { return lru_num_pinned; } - - void lru_set_max(uint32_t m) { lru_max = m; } - void lru_set_midpoint(float f) { lru_midpoint = f; } - - void lru_clear() { - lru_top.clear(); - lru_bot.clear(); - lru_pintail.clear(); - lru_num = 0; + assert(num_pinned == 0); } // insert at top of lru void lru_insert_top(LRUObject *o) { - //assert(!o->lru_in_lru); - //o->lru_in_lru = true; assert(!o->lru); o->lru = this; - lru_top.insert_head( o ); - lru_num++; - if (o->lru_pinned) lru_num_pinned++; - lru_adjust(); + top.push_front(&o->lru_link); + if (o->lru_pinned) num_pinned++; + adjust(); } // insert at mid point in lru void lru_insert_mid(LRUObject *o) { - //assert(!o->lru_in_lru); - //o->lru_in_lru = true; assert(!o->lru); o->lru = this; - lru_bot.insert_head(o); - lru_num++; - if (o->lru_pinned) lru_num_pinned++; + bottom.push_front(&o->lru_link); + if (o->lru_pinned) num_pinned++; + adjust(); } // insert at bottom of lru void lru_insert_bot(LRUObject *o) { assert(!o->lru); o->lru = this; - lru_bot.insert_tail(o); - lru_num++; - if (o->lru_pinned) lru_num_pinned++; + bottom.push_back(&o->lru_link); + if (o->lru_pinned) num_pinned++; + adjust(); } - /* - // insert at bottom of lru - void lru_insert_pintail(LRUObject *o) { - assert(!o->lru); - o->lru = this; - - assert(o->lru_pinned); - - lru_pintail.insert_head(o); - lru_num++; - lru_num_pinned += o->lru_pinned; - } - */ - - - - - // adjust top/bot balance, as necessary - void lru_adjust() { - if (!lru_max) return; - - unsigned toplen = lru_top.get_length(); - unsigned topwant = (unsigned)(lru_midpoint * ((double)lru_max - lru_num_pinned)); - while (toplen > 0 && - toplen > topwant) { - // remove from tail of top, stick at head of bot - // FIXME: this could be way more efficient by moving a whole chain of items. - - LRUObject *o = lru_top.get_tail(); - lru_top.remove(o); - lru_bot.insert_head(o); - toplen--; - } - } - - // remove an item LRUObject *lru_remove(LRUObject *o) { - // not in list - //assert(o->lru_in_lru); - //if (!o->lru_in_lru) return o; // might have expired and been removed that way. if (!o->lru) return o; - - assert((o->lru_list == &lru_pintail) || - (o->lru_list == &lru_top) || - (o->lru_list == &lru_bot)); - o->lru_list->remove(o); - - lru_num--; - if (o->lru_pinned) lru_num_pinned--; - o->lru = 0; + auto list = o->lru_link.get_list(); + assert(list == &top || list == &bottom || list == &pintail); + o->lru_link.remove_myself(); + if (o->lru_pinned) num_pinned--; + o->lru = nullptr; + adjust(); return o; } // touch item -- move to head of lru bool lru_touch(LRUObject *o) { - lru_remove(o); - lru_insert_top(o); + if (!o->lru) { + lru_insert_top(o); + } else { + assert(o->lru == this); + auto list = o->lru_link.get_list(); + assert(list == &top || list == &bottom || list == &pintail); + top.push_front(&o->lru_link); + adjust(); + } return true; } // touch item -- move to midpoint (unless already higher) bool lru_midtouch(LRUObject *o) { - if (o->lru_list == &lru_top) return false; - - lru_remove(o); - lru_insert_mid(o); + if (!o->lru) { + lru_insert_mid(o); + } else { + assert(o->lru == this); + auto list = o->lru_link.get_list(); + assert(list == &top || list == &bottom || list == &pintail); + if (list == &top) return false; + bottom.push_front(&o->lru_link); + adjust(); + } return true; } // touch item -- move to bottom bool lru_bottouch(LRUObject *o) { - lru_remove(o); - lru_insert_bot(o); + if (!o->lru) { + lru_insert_bot(o); + } else { + assert(o->lru == this); + auto list = o->lru_link.get_list(); + assert(list == &top || list == &bottom || list == &pintail); + bottom.push_back(&o->lru_link); + adjust(); + } return true; } void lru_touch_entire_pintail() { // promote entire pintail to the top lru - while (lru_pintail.get_length() > 0) { - LRUObject *o = lru_pintail.get_head(); - lru_pintail.remove(o); - lru_top.insert_tail(o); + while (pintail.size() > 0) { + top.push_back(&pintail.front()->lru_link); + adjust(); } } - // expire -- expire a single item LRUObject *lru_get_next_expire() { - LRUObject *p; - // look through tail of bot - while (lru_bot.get_length()) { - p = lru_bot.get_tail(); + while (bottom.size()) { + LRUObject *p = bottom.back(); if (!p->lru_pinned) return p; // move to pintail - lru_bot.remove(p); - lru_pintail.insert_head(p); + pintail.push_front(&p->lru_link); + adjust(); } // ok, try head then - while (lru_top.get_length()) { - p = lru_top.get_tail(); + while (top.size()) { + LRUObject *p = top.back(); if (!p->lru_pinned) return p; // move to pintail - lru_top.remove(p); - lru_pintail.insert_head(p); + pintail.push_front(&p->lru_link); + adjust(); } // no luck! @@ -307,32 +188,55 @@ class LRU { return NULL; } - void lru_status() { - //generic_dout(10) << "lru: " << lru_num << " items, " << lru_top.get_length() << " top, " << lru_bot.get_length() << " bot, " << lru_pintail.get_length() << " pintail" << dendl; + //generic_dout(10) << "lru: " << lru_get_size() << " items, " << top.size() << " top, " << bottom.size() << " bot, " << pintail.size() << " pintail" << dendl; } +protected: + // adjust top/bot balance, as necessary + void adjust() { + uint64_t toplen = top.size(); + uint64_t topwant = (midpoint * (double)(lru_get_size() - num_pinned)); + /* move items from below midpoint (bottom) to top: move midpoint forward */ + for (uint64_t i = toplen; i < topwant; i++) { + top.push_back(&bottom.front()->lru_link); + } + /* or: move items from above midpoint (top) to bottom: move midpoint backwards */ + for (uint64_t i = toplen; i > topwant; i--) { + bottom.push_front(&top.back()->lru_link); + } + } + + uint64_t num_pinned; + double midpoint; + + friend class LRUObject; +private: + typedef xlist LRUList; + LRUList top, bottom, pintail; }; +inline LRUObject::~LRUObject() { + if (lru) { + lru->lru_remove(this); + } +} inline void LRUObject::lru_pin() { if (lru && !lru_pinned) { - lru->lru_num_pinned++; - lru->lru_adjust(); + lru->num_pinned++; } lru_pinned = true; } inline void LRUObject::lru_unpin() { if (lru && lru_pinned) { - lru->lru_num_pinned--; + lru->num_pinned--; // move from pintail -> bot - if (lru_list == &lru->lru_pintail) { - lru->lru_pintail.remove(this); - lru->lru_bot.insert_tail(this); + if (lru_link.get_list() == &lru->pintail) { + lru->lru_bottouch(this); } - lru->lru_adjust(); } lru_pinned = false; } diff --git a/src/mds/MDCache.cc b/src/mds/MDCache.cc index 1eb4cc5a0f6..343167c99e1 100644 --- a/src/mds/MDCache.cc +++ b/src/mds/MDCache.cc @@ -202,10 +202,8 @@ MDCache::MDCache(MDSRank *m, PurgeQueue &purge_queue_) : cap_imports_num_opening = 0; opening_root = open = false; - lru.lru_set_max(g_conf->mds_cache_size); lru.lru_set_midpoint(g_conf->mds_cache_mid); - bottom_lru.lru_set_max(0); bottom_lru.lru_set_midpoint(0); decayrate.set_halflife(g_conf->mds_decay_halflife); diff --git a/src/mds/MDCache.h b/src/mds/MDCache.h index 01c230aab29..4af04efbdbe 100644 --- a/src/mds/MDCache.h +++ b/src/mds/MDCache.h @@ -672,8 +672,6 @@ public: CInode *get_root() { return root; } CInode *get_myin() { return myin; } - // cache - void set_cache_size(size_t max) { lru.lru_set_max(max); } size_t get_cache_size() { return lru.lru_get_size(); } // trimming diff --git a/src/test/common/test_lru.cc b/src/test/common/test_lru.cc index b3630792aef..5db18314c4b 100644 --- a/src/test/common/test_lru.cc +++ b/src/test/common/test_lru.cc @@ -23,101 +23,126 @@ class Item : public LRUObject { public: int id; - explicit Item(int v) : id(v) {} + Item() : id(0) {} + Item(int i) : id(i) {} + void set(int i) {id = i;} }; TEST(lru, InsertTop) { - LRU lru = LRU(10); - - lru.lru_set_midpoint(.5); // 50% of 10 elements. - for (int i=0; i<100; i++) { - lru.lru_insert_top(new Item(i)); + LRU lru; + static const int n = 100; + Item items[n]; + + lru.lru_set_midpoint(.5); // 50% of elements. + for (int i=0; i(lru.lru_expire()))->id); } TEST(lru, InsertMid) { - LRU lru = LRU(10); - - for (int i=0; i<100; i++) { - lru.lru_insert_mid(new Item(i)); + LRU lru; + static const int n = 102; + Item items[n]; + + lru.lru_set_midpoint(.7); // 70% of elements. + for (int i=0; i(lru.lru_expire()))->id); } TEST(lru, InsertBot) { - LRU lru = LRU(10); - - for (int i=0; i<100; i++) { - lru.lru_insert_bot(new Item(i)); + LRU lru; + static const int n = 100; + Item items[n]; + + lru.lru_set_midpoint(.7); // 70% of elements. + for (int i=0; i(lru.lru_expire()))->id); } TEST(lru, Adjust) { - LRU lru = LRU(10); - - lru.lru_set_midpoint(.6); // 60% of 10 elements. - for (int i=0; i<100; i++) { - lru.lru_touch(new Item(i)); + LRU lru; + static const int n = 100; + Item items[n]; + + lru.lru_set_midpoint(.6); // 60% of elements. + for (int i=0; i(lru.lru_expire()))->id); + ASSERT_EQ(1U, lru.lru_get_pintail()); + ASSERT_EQ(47U, lru.lru_get_top()); /* 60% of unpinned */ + ASSERT_EQ(51U, lru.lru_get_bot()); + ASSERT_EQ(99U, lru.lru_get_size()); + ASSERT_EQ(2, (static_cast(lru.lru_expire()))->id); + ASSERT_EQ(1U, lru.lru_get_pintail()); + ASSERT_EQ(46U, lru.lru_get_top()); /* 60% of unpinned */ + ASSERT_EQ(51U, lru.lru_get_bot()); + ASSERT_EQ(98U, lru.lru_get_size()); + ASSERT_EQ(3, (static_cast(lru.lru_expire()))->id); + ASSERT_EQ(4, (static_cast(lru.lru_expire()))->id); + ASSERT_EQ(6, (static_cast(lru.lru_expire()))->id); + ASSERT_EQ(2U, lru.lru_get_pintail()); + ASSERT_EQ(45U, lru.lru_get_top()); /* 60% of unpinned */ + ASSERT_EQ(48U, lru.lru_get_bot()); + ASSERT_EQ(95U, lru.lru_get_size()); } TEST(lru, Pinning) { - LRU lru = LRU(); + LRU lru; - Item *ob0 = new Item(0); - Item *ob1 = new Item(1); + Item ob0(0), ob1(1); // test before ob1 are in a LRU - ob1->lru_pin(); - ASSERT_FALSE(ob1->lru_is_expireable()); + ob1.lru_pin(); + ASSERT_FALSE(ob1.lru_is_expireable()); - ob1->lru_unpin(); - ASSERT_TRUE(ob1->lru_is_expireable()); + ob1.lru_unpin(); + ASSERT_TRUE(ob1.lru_is_expireable()); // test when ob1 are in a LRU - lru.lru_touch(ob0); - lru.lru_touch(ob1); + lru.lru_insert_top(&ob0); + lru.lru_insert_top(&ob1); - ob1->lru_pin(); - ob1->lru_pin(); // Verify that, one incr. + ob1.lru_pin(); + ob1.lru_pin(); // Verify that, one incr. ASSERT_EQ(1U, lru.lru_get_num_pinned()); - ASSERT_FALSE(ob1->lru_is_expireable()); + ASSERT_FALSE(ob1.lru_is_expireable()); - ob1->lru_unpin(); - ob1->lru_unpin(); // Verify that, one decr. + ob1.lru_unpin(); + ob1.lru_unpin(); // Verify that, one decr. ASSERT_EQ(0U, lru.lru_get_num_pinned()); - ASSERT_TRUE(ob1->lru_is_expireable()); + ASSERT_TRUE(ob1.lru_is_expireable()); ASSERT_EQ(0, (static_cast(lru.lru_expire()))->id); - ob0->lru_pin(); + ob0.lru_pin(); ASSERT_EQ(1, (static_cast(lru.lru_expire()))->id); } -- 2.39.5