+++ /dev/null
-// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
-// vim: ts=8 sw=2 smarttab
-/*
- * Ceph - scalable distributed file system
- *
- * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
- *
- * This is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License version 2.1, as published by the Free Software
- * Foundation. See file COPYING.
- *
- */
-
-
-
-#ifndef CEPH_LRU_H
-#define CEPH_LRU_H
-
-#include <math.h>
-#include <stdint.h>
-
-#include "common/config.h"
-#include "xlist.h"
-
-class LRUObject {
-public:
- LRUObject() : lru(), lru_link(this), lru_pinned(false) { }
- ~LRUObject();
-
- // pin/unpin item in cache
- void lru_pin();
- void lru_unpin();
- bool lru_is_expireable() const { return !lru_pinned; }
-
- friend class LRU;
-private:
- class LRU *lru;
- xlist<LRUObject *>::item lru_link;
- bool lru_pinned;
-};
-
-class LRU {
-public:
- LRU() : num_pinned(0), midpoint(0.6) {}
-
- 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; }
-
- void lru_set_midpoint(double f) { midpoint = fmin(1.0, fmax(0.0, f)); }
-
- void lru_clear() {
- while (!top.empty()) {
- lru_remove(top.front());
- }
- while (!bottom.empty()) {
- lru_remove(bottom.front());
- }
- while (!pintail.empty()) {
- lru_remove(pintail.front());
- }
- assert(num_pinned == 0);
- }
-
- // insert at top of lru
- void lru_insert_top(LRUObject *o) {
- assert(!o->lru);
- o->lru = this;
- 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);
- o->lru = this;
- 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;
- bottom.push_back(&o->lru_link);
- if (o->lru_pinned) num_pinned++;
- adjust();
- }
-
- // remove an item
- LRUObject *lru_remove(LRUObject *o) {
- if (!o->lru) return o;
- 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) {
- 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) {
- 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) {
- 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 (pintail.size() > 0) {
- top.push_back(&pintail.front()->lru_link);
- adjust();
- }
- }
-
- // expire -- expire a single item
- LRUObject *lru_get_next_expire() {
- // look through tail of bot
- while (bottom.size()) {
- LRUObject *p = bottom.back();
- if (!p->lru_pinned) return p;
-
- // move to pintail
- pintail.push_front(&p->lru_link);
- adjust();
- }
-
- // ok, try head then
- while (top.size()) {
- LRUObject *p = top.back();
- if (!p->lru_pinned) return p;
-
- // move to pintail
- pintail.push_front(&p->lru_link);
- adjust();
- }
-
- // no luck!
- return NULL;
- }
-
- LRUObject *lru_expire() {
- LRUObject *p = lru_get_next_expire();
- if (p)
- return lru_remove(p);
- return NULL;
- }
-
- void lru_status() {
- //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<LRUObject *> LRUList;
- LRUList top, bottom, pintail;
-};
-
-inline LRUObject::~LRUObject() {
- if (lru) {
- lru->lru_remove(this);
- }
-}
-
-inline void LRUObject::lru_pin() {
- if (lru && !lru_pinned) {
- lru->num_pinned++;
- }
- lru_pinned = true;
-}
-
-inline void LRUObject::lru_unpin() {
- if (lru && lru_pinned) {
- lru->num_pinned--;
-
- // move from pintail -> bot
- if (lru_link.get_list() == &lru->pintail) {
- lru->lru_bottouch(this);
- }
- }
- lru_pinned = false;
-}
-
-#endif
Code Review / stor4nfv.git / blobdiff