File: indexed_resource_pool.h

package info (click to toggle)
lizardfs 3.12.0+dfsg-3
  • links: PTS, VCS
  • area: main
  • in suites: buster, sid
  • size: 8,064 kB
  • sloc: cpp: 91,899; sh: 9,341; python: 3,878; ansic: 3,109; pascal: 128; makefile: 57
file content (226 lines) | stat: -rw-r--r-- 5,772 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
/*
   Copyright 2016 Skytechnology sp. z o.o..

   This file is part of LizardFS.

   LizardFS is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, version 3.

   LizardFS is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with LizardFS  If not, see <http://www.gnu.org/licenses/>.
 */

#pragma once

#include "chunkserver/chunk.h"
#include "common/platform.h"
#include "common/small_vector.h"

/*! Class for keeping resources that can be easily indexed with integers.
 *  Use case: Keeping open descriptors of chunks in order to close them
 *  not immediately, but when they are unused for a long period of time
 *  or desperately needed.
 *
 * Resources can be accessed either by their id or in LRU manner.
 * Thanks to that, it is possible to free least recently used resources
 * on demand while keeping the hot ones available.
 *
 */
template <typename Resource,
	int DefaultCapacity = 65536,
	int ReleaseThreshold_s = 4,
	int PopUnusedCount = 4>
class IndexedResourcePool {
public:
	static const int kNullId = 0;
	static const int kInitialPurgeListCapacity = 256;
	typedef small_vector<Resource, kInitialPurgeListCapacity> PurgeList;

	/*! Helper structure for keeping resources in double-linked list implemented
	 *  on top of a contiguous container.
	 */
	struct Entry {
		uint32_t timestamp;
		int next;
		int prev;
		Resource resource;

		Entry() : timestamp(), next(), prev(), resource() {}
	};

	IndexedResourcePool(int capacity = DefaultCapacity)
		: data_(capacity), mutex_(), garbage_collector_head_() {
	}

	/*!
	 * \brief Acquire existing resource.
	 *
	 * \param id Resource's index.
	 * \param data Resource passed as rvalue reference.
	 */
	void acquire(int id) {
		if (id < kNullId) {
			return;
		}
		std::lock_guard<std::mutex> guard(mutex_);
		assert((size_t)id < data_.size());
		erase(id);
	}

	/*!
	 * \brief Acquire created resource.
	 *
	 * \param id Resource's index.
	 * \param data Resource passed as rvalue reference.
	 */
	void acquire(int id, Resource &&data) {
		assert(id > kNullId);
		std::lock_guard<std::mutex> guard(mutex_);
		if ((size_t)id >= data_.size()) {
			data_.resize(id + 1);
		}
		erase(id);
		data_[id].resource = std::move(data);
	}

	/*!
	 * \brief Release resource and put it in the free list.
	 *
	 * \param id Resource's index.
	 * \param timestamp Timestamp of the moment of release.
	 */
	void release(int id, uint32_t timestamp) {
		if (id <= kNullId) {
			return;
		}
		std::lock_guard<std::mutex> guard(mutex_);
		assert((size_t)id < data_.size());
		erase(id);
		push_back(id);
		data_[id].timestamp = timestamp;
	}

	/*!
	 * \brief Enqueue resource for being freed
	 *
	 * \param id Resource's index.
	 * \return True if id was correct.
	 */
	bool purge(int id) {
		if (id <= kNullId) {
			return false;
		}
		std::lock_guard<std::mutex> guard(mutex_);
		data_[id].resource.purge();
		purge_list_.emplace_back(std::move(data_[id].resource));
		erase(id);
		return true;
	}

	/*!
	 * \brief Free up to 'count' resources unused since 'now'.
	 * Resources which can be freed should return true from their implementation
	 * of test method. Freeing is done in resource's destructor.
	 *
	 * \param now Current timestamp.
	 * \param count Maximum number of resources to be freed.
	 * \return Number of elements freed.
	 */
	template<typename ExtraLock>
	int freeUnused(uint32_t now, ExtraLock &extra_lock, int count = PopUnusedCount) {
		int freed = 0;
		small_vector<Resource, PopUnusedCount> candidates;
		candidates.reserve(count);
		flushPurgeList();
		mutex_.lock();
		garbage_collector_head_ = front();
		mutex_.unlock();
		while (true) {
			std::lock_guard<ExtraLock> extra_guard(extra_lock);
			std::lock_guard<std::mutex> guard(mutex_);
			if (freed >= count || garbage_collector_head_ == kNullId) {
				break;
			}

			Entry &node = data_[garbage_collector_head_];
			if (node.timestamp + ReleaseThreshold_s > now) {
				break;
			}

			if (node.resource.canRemove()) {
				candidates.emplace_back(std::move(node.resource));
				erase(garbage_collector_head_);
				freed++;
			} else {
				garbage_collector_head_ = node.next;
			}
		}
		return freed;
	}

	/*!
	 * \brief Get resource indexed by given id by reference.
	 *
	 * \param id Resource's index.
	 * \return Reference to resource with given id. Undefined if id is not acquired.
	 */
	Resource &getResource(int id) {
		assert(id > kNullId);
		return data_[id].resource;
	};

protected:
	/*!
	 * \brief Purge all previously enqueued resources
	 */
	void flushPurgeList() {
		PurgeList tmp;
		std::unique_lock<std::mutex> guard(mutex_);
		tmp = std::move(purge_list_);
		purge_list_.clear();
	}

	void erase(int id) {
		if (!contains(id)) {
			return;
		}
		int next_id = data_[id].next;
		data_[data_[id].next].prev = data_[id].prev;
		data_[data_[id].prev].next = data_[id].next;
		data_[id].prev = data_[id].next = kNullId;
		if (id == garbage_collector_head_) {
			garbage_collector_head_ = next_id;
		}
	}

	void push_back(int id) {
		data_[id].prev = back();
		data_[id].next = kNullId;
		data_[back()].next = id;
		data_[kNullId].prev = id;
	}

	inline bool contains(int id) {
		assert(id > kNullId);
		return data_[id].prev != kNullId || id == front();
	}

	inline int front() {
		return data_[kNullId].next;
	}

	inline int back() {
		return data_[kNullId].prev;
	}

	std::vector<Entry> data_;
	std::mutex mutex_;
	PurgeList purge_list_;
	int garbage_collector_head_;
};