1 /*
2 Licensed to the Apache Software Foundation (ASF) under one
3 or more contributor license agreements. See the NOTICE file
4 distributed with this work for additional information
5 regarding copyright ownership. The ASF licenses this file
6 to you under the Apache License, Version 2.0 (the
7 "License"); you may not use this file except in compliance
8 with the License. You may obtain a copy of the License at
9
10 http://www.apache.org/licenses/LICENSE-2.0
11
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17 */
18
19 /**
20 * @file fetch_policy_lru.cc
21 * @brief LRU fetch policy.
22 */
23
24 #include "fetch_policy_lru.h"
25 #include "common.h"
26
27 inline const char *
name()28 FetchPolicyLru::name()
29 {
30 return "lru";
31 }
32
33 bool
init(const char * parameters)34 FetchPolicyLru::init(const char *parameters)
35 {
36 if (nullptr == parameters) {
37 /* Leave defaults */
38 } else {
39 size_t size = 0;
40
41 /* look for buckets first */
42 const char *sizeStr = parameters;
43 const char *delim = strchr(parameters, ',');
44
45 if (nullptr == delim) {
46 /* no divider specified, set the buckets */
47 size = getValue(sizeStr, strlen(sizeStr));
48 } else {
49 /* set the buckets */
50 size = getValue(sizeStr, delim - sizeStr);
51 }
52
53 /* Defaults are considered minimum */
54 static const char *defaultStr = " (default)";
55 bool useDefault = false;
56
57 /* Make sure size is not larger than what std::list is physically able to hold */
58 LruList::size_type realMax = _list.max_size();
59 if (size > realMax) {
60 PrefetchDebug("size: %lu is not feasible, cutting to %lu", size, realMax);
61 size = realMax;
62 }
63 /* Guarantee minimum value */
64 if (size > _maxSize) {
65 _maxSize = size;
66 } else {
67 useDefault = true;
68 PrefetchError("size: %lu is not a good value", size);
69 };
70
71 PrefetchDebug("initialized %s fetch policy: size: %lu%s", name(), _maxSize, (useDefault ? defaultStr : ""));
72 }
73
74 return true;
75 }
76
77 inline size_t
getMaxSize()78 FetchPolicyLru::getMaxSize()
79 {
80 return _maxSize;
81 }
82
83 inline size_t
getSize()84 FetchPolicyLru::getSize()
85 {
86 return _size;
87 }
88
89 bool
acquire(const std::string & url)90 FetchPolicyLru::acquire(const std::string &url)
91 {
92 bool ret = false;
93
94 LruHash hash;
95 hash.init(url.c_str(), url.length());
96
97 LruMapIterator it = _map.find(&hash);
98
99 if (_map.end() != it) {
100 PrefetchDebug("recently used LRU entry, moving to front");
101
102 /* We have an entry in the LRU */
103 PrefetchAssert(_list.size() > 0);
104
105 /* Move to the front of the list */
106 _list.splice(_list.begin(), _list, it->second);
107
108 /* Don't trigger fetch if the url is found amongst the most recently used ones */
109 ret = false;
110 } else {
111 /* New LRU entry */
112 if (_size >= _maxSize) {
113 /* Move the last (least recently used) element to the front and remove it from the hash table. */
114 _list.splice(_list.begin(), _list, --_list.end());
115 _map.erase(&(*_list.begin()));
116 PrefetchDebug("reused the least recently used LRU entry");
117 } else {
118 /* With this implementation we are never removing LRU elements from the list but just updating the front element of the list
119 * so the following addition should happen at most FetchPolicyLru::_maxSize number of times */
120 _list.push_front(NULL_LRU_ENTRY);
121 _size++;
122 PrefetchDebug("created a new LRU entry, size=%d", (int)_size);
123 }
124 /* Update the "new" or the most recently used LRU entry and add it to the hash */
125 *_list.begin() = hash;
126 _map[&(*_list.begin())] = _list.begin();
127
128 /* Trigger fetch since the URL is not amongst the most recently used ones */
129 ret = true;
130 }
131
132 log("acquire", url, ret);
133 return ret;
134 }
135
136 bool
release(const std::string & url)137 FetchPolicyLru::release(const std::string &url)
138 {
139 log("release", url, true);
140 return true;
141 }
142