xref: /haiku/src/system/kernel/slab/ObjectDepot.cpp (revision 825566f82f652d82ffaf3f0deca0a2bcda1e02c2)
1a8806e5eSIngo Weinhold /*
2a8806e5eSIngo Weinhold  * Copyright 2008, Axel Dörfler. All Rights Reserved.
3a8806e5eSIngo Weinhold  * Copyright 2007, Hugo Santos. All Rights Reserved.
4a8806e5eSIngo Weinhold  *
5a8806e5eSIngo Weinhold  * Distributed under the terms of the MIT License.
6a8806e5eSIngo Weinhold  */
7a8806e5eSIngo Weinhold 
8a8806e5eSIngo Weinhold 
9a8806e5eSIngo Weinhold #include <slab/ObjectDepot.h>
10a8806e5eSIngo Weinhold 
11a8806e5eSIngo Weinhold #include <algorithm>
12a8806e5eSIngo Weinhold 
13a8806e5eSIngo Weinhold #include <util/AutoLock.h>
14a8806e5eSIngo Weinhold 
15a8806e5eSIngo Weinhold #include "slab_private.h"
16a8806e5eSIngo Weinhold 
17a8806e5eSIngo Weinhold 
18a8806e5eSIngo Weinhold static const int kMagazineCapacity = 32;
19a8806e5eSIngo Weinhold 	// TODO: Should be dynamically tuned per cache.
20a8806e5eSIngo Weinhold 
21a8806e5eSIngo Weinhold 
22*825566f8SIngo Weinhold struct DepotMagazine {
23*825566f8SIngo Weinhold 			DepotMagazine*		next;
24*825566f8SIngo Weinhold 			uint16				current_round;
25*825566f8SIngo Weinhold 			uint16				round_count;
26a8806e5eSIngo Weinhold 			void*				rounds[0];
27*825566f8SIngo Weinhold 
28*825566f8SIngo Weinhold public:
29*825566f8SIngo Weinhold 	inline	bool				IsEmpty() const;
30*825566f8SIngo Weinhold 	inline	bool				IsFull() const;
31*825566f8SIngo Weinhold 
32*825566f8SIngo Weinhold 	inline	void*				Pop();
33*825566f8SIngo Weinhold 	inline	bool				Push(void* object);
34a8806e5eSIngo Weinhold };
35a8806e5eSIngo Weinhold 
36a8806e5eSIngo Weinhold 
37a8806e5eSIngo Weinhold struct depot_cpu_store {
38a8806e5eSIngo Weinhold 	recursive_lock	lock;
39*825566f8SIngo Weinhold 	DepotMagazine*	loaded;
40*825566f8SIngo Weinhold 	DepotMagazine*	previous;
41a8806e5eSIngo Weinhold };
42a8806e5eSIngo Weinhold 
43a8806e5eSIngo Weinhold 
44*825566f8SIngo Weinhold bool
45*825566f8SIngo Weinhold DepotMagazine::IsEmpty() const
46a8806e5eSIngo Weinhold {
47*825566f8SIngo Weinhold 	return current_round == 0;
48a8806e5eSIngo Weinhold }
49a8806e5eSIngo Weinhold 
50a8806e5eSIngo Weinhold 
51*825566f8SIngo Weinhold bool
52*825566f8SIngo Weinhold DepotMagazine::IsFull() const
53a8806e5eSIngo Weinhold {
54*825566f8SIngo Weinhold 	return current_round == round_count;
55a8806e5eSIngo Weinhold }
56a8806e5eSIngo Weinhold 
57a8806e5eSIngo Weinhold 
58*825566f8SIngo Weinhold void*
59*825566f8SIngo Weinhold DepotMagazine::Pop()
60a8806e5eSIngo Weinhold {
61*825566f8SIngo Weinhold 	return rounds[--current_round];
62a8806e5eSIngo Weinhold }
63a8806e5eSIngo Weinhold 
64a8806e5eSIngo Weinhold 
65*825566f8SIngo Weinhold bool
66*825566f8SIngo Weinhold DepotMagazine::Push(void* object)
67a8806e5eSIngo Weinhold {
68*825566f8SIngo Weinhold 	if (IsFull())
69a8806e5eSIngo Weinhold 		return false;
70*825566f8SIngo Weinhold 
71*825566f8SIngo Weinhold 	rounds[current_round++] = object;
72a8806e5eSIngo Weinhold 	return true;
73a8806e5eSIngo Weinhold }
74a8806e5eSIngo Weinhold 
75a8806e5eSIngo Weinhold 
76*825566f8SIngo Weinhold static DepotMagazine*
77a8806e5eSIngo Weinhold alloc_magazine()
78a8806e5eSIngo Weinhold {
79*825566f8SIngo Weinhold 	DepotMagazine* magazine = (DepotMagazine*)slab_internal_alloc(
80*825566f8SIngo Weinhold 		sizeof(DepotMagazine) + kMagazineCapacity * sizeof(void*), 0);
81a8806e5eSIngo Weinhold 	if (magazine) {
82a8806e5eSIngo Weinhold 		magazine->next = NULL;
83a8806e5eSIngo Weinhold 		magazine->current_round = 0;
84a8806e5eSIngo Weinhold 		magazine->round_count = kMagazineCapacity;
85a8806e5eSIngo Weinhold 	}
86a8806e5eSIngo Weinhold 
87a8806e5eSIngo Weinhold 	return magazine;
88a8806e5eSIngo Weinhold }
89a8806e5eSIngo Weinhold 
90a8806e5eSIngo Weinhold 
91a8806e5eSIngo Weinhold static void
92*825566f8SIngo Weinhold free_magazine(DepotMagazine* magazine)
93a8806e5eSIngo Weinhold {
94*825566f8SIngo Weinhold 	slab_internal_free(magazine);
95a8806e5eSIngo Weinhold }
96a8806e5eSIngo Weinhold 
97a8806e5eSIngo Weinhold 
98a8806e5eSIngo Weinhold static void
99*825566f8SIngo Weinhold empty_magazine(object_depot* depot, DepotMagazine* magazine)
100a8806e5eSIngo Weinhold {
101a8806e5eSIngo Weinhold 	for (uint16 i = 0; i < magazine->current_round; i++)
102*825566f8SIngo Weinhold 		depot->return_object(depot, depot->cookie, magazine->rounds[i]);
103a8806e5eSIngo Weinhold 	free_magazine(magazine);
104a8806e5eSIngo Weinhold }
105a8806e5eSIngo Weinhold 
106a8806e5eSIngo Weinhold 
107a8806e5eSIngo Weinhold static bool
108*825566f8SIngo Weinhold exchange_with_full(object_depot* depot, DepotMagazine*& magazine)
109a8806e5eSIngo Weinhold {
110a8806e5eSIngo Weinhold 	RecursiveLocker _(depot->lock);
111a8806e5eSIngo Weinhold 
112a8806e5eSIngo Weinhold 	if (depot->full == NULL)
113a8806e5eSIngo Weinhold 		return false;
114a8806e5eSIngo Weinhold 
115a8806e5eSIngo Weinhold 	depot->full_count--;
116a8806e5eSIngo Weinhold 	depot->empty_count++;
117a8806e5eSIngo Weinhold 
118a8806e5eSIngo Weinhold 	_push(depot->empty, magazine);
119a8806e5eSIngo Weinhold 	magazine = _pop(depot->full);
120a8806e5eSIngo Weinhold 	return true;
121a8806e5eSIngo Weinhold }
122a8806e5eSIngo Weinhold 
123a8806e5eSIngo Weinhold 
124a8806e5eSIngo Weinhold static bool
125*825566f8SIngo Weinhold exchange_with_empty(object_depot* depot, DepotMagazine*& magazine)
126a8806e5eSIngo Weinhold {
127a8806e5eSIngo Weinhold 	RecursiveLocker _(depot->lock);
128a8806e5eSIngo Weinhold 
129a8806e5eSIngo Weinhold 	if (depot->empty == NULL) {
130a8806e5eSIngo Weinhold 		depot->empty = alloc_magazine();
131a8806e5eSIngo Weinhold 		if (depot->empty == NULL)
132a8806e5eSIngo Weinhold 			return false;
133a8806e5eSIngo Weinhold 	} else {
134a8806e5eSIngo Weinhold 		depot->empty_count--;
135a8806e5eSIngo Weinhold 	}
136a8806e5eSIngo Weinhold 
137a8806e5eSIngo Weinhold 	if (magazine) {
138a8806e5eSIngo Weinhold 		_push(depot->full, magazine);
139a8806e5eSIngo Weinhold 		depot->full_count++;
140a8806e5eSIngo Weinhold 	}
141a8806e5eSIngo Weinhold 
142a8806e5eSIngo Weinhold 	magazine = _pop(depot->empty);
143a8806e5eSIngo Weinhold 	return true;
144a8806e5eSIngo Weinhold }
145a8806e5eSIngo Weinhold 
146a8806e5eSIngo Weinhold 
147a8806e5eSIngo Weinhold static inline depot_cpu_store*
148a8806e5eSIngo Weinhold object_depot_cpu(object_depot* depot)
149a8806e5eSIngo Weinhold {
150a8806e5eSIngo Weinhold 	return &depot->stores[smp_get_current_cpu()];
151a8806e5eSIngo Weinhold }
152a8806e5eSIngo Weinhold 
153a8806e5eSIngo Weinhold 
154a8806e5eSIngo Weinhold // #pragma mark -
155a8806e5eSIngo Weinhold 
156a8806e5eSIngo Weinhold 
157a8806e5eSIngo Weinhold status_t
158*825566f8SIngo Weinhold object_depot_init(object_depot* depot, uint32 flags, void* cookie,
159*825566f8SIngo Weinhold 	void (*return_object)(object_depot* depot, void* cookie, void* object))
160a8806e5eSIngo Weinhold {
161a8806e5eSIngo Weinhold 	depot->full = NULL;
162a8806e5eSIngo Weinhold 	depot->empty = NULL;
163a8806e5eSIngo Weinhold 	depot->full_count = depot->empty_count = 0;
164a8806e5eSIngo Weinhold 
165a8806e5eSIngo Weinhold 	recursive_lock_init(&depot->lock, "depot");
166a8806e5eSIngo Weinhold 
167*825566f8SIngo Weinhold 	depot->stores = (depot_cpu_store*)slab_internal_alloc(
168*825566f8SIngo Weinhold 		sizeof(depot_cpu_store) * smp_get_num_cpus(), flags);
169a8806e5eSIngo Weinhold 	if (depot->stores == NULL) {
170a8806e5eSIngo Weinhold 		recursive_lock_destroy(&depot->lock);
171a8806e5eSIngo Weinhold 		return B_NO_MEMORY;
172a8806e5eSIngo Weinhold 	}
173a8806e5eSIngo Weinhold 
174a8806e5eSIngo Weinhold 	for (int i = 0; i < smp_get_num_cpus(); i++) {
175a8806e5eSIngo Weinhold 		recursive_lock_init(&depot->stores[i].lock, "cpu store");
176a8806e5eSIngo Weinhold 		depot->stores[i].loaded = depot->stores[i].previous = NULL;
177a8806e5eSIngo Weinhold 	}
178a8806e5eSIngo Weinhold 
179*825566f8SIngo Weinhold 	depot->cookie = cookie;
180a8806e5eSIngo Weinhold 	depot->return_object = return_object;
181a8806e5eSIngo Weinhold 
182a8806e5eSIngo Weinhold 	return B_OK;
183a8806e5eSIngo Weinhold }
184a8806e5eSIngo Weinhold 
185a8806e5eSIngo Weinhold 
186a8806e5eSIngo Weinhold void
187a8806e5eSIngo Weinhold object_depot_destroy(object_depot* depot)
188a8806e5eSIngo Weinhold {
189a8806e5eSIngo Weinhold 	object_depot_make_empty(depot);
190a8806e5eSIngo Weinhold 
191a8806e5eSIngo Weinhold 	for (int i = 0; i < smp_get_num_cpus(); i++) {
192a8806e5eSIngo Weinhold 		recursive_lock_destroy(&depot->stores[i].lock);
193a8806e5eSIngo Weinhold 	}
194a8806e5eSIngo Weinhold 
195*825566f8SIngo Weinhold 	slab_internal_free(depot->stores);
196a8806e5eSIngo Weinhold 
197a8806e5eSIngo Weinhold 	recursive_lock_destroy(&depot->lock);
198a8806e5eSIngo Weinhold }
199a8806e5eSIngo Weinhold 
200a8806e5eSIngo Weinhold 
201a8806e5eSIngo Weinhold static void*
202a8806e5eSIngo Weinhold object_depot_obtain_from_store(object_depot* depot, depot_cpu_store* store)
203a8806e5eSIngo Weinhold {
204a8806e5eSIngo Weinhold 	RecursiveLocker _(store->lock);
205a8806e5eSIngo Weinhold 
206a8806e5eSIngo Weinhold 	// To better understand both the Alloc() and Free() logic refer to
207a8806e5eSIngo Weinhold 	// Bonwick's ``Magazines and Vmem'' [in 2001 USENIX proceedings]
208a8806e5eSIngo Weinhold 
209a8806e5eSIngo Weinhold 	// In a nutshell, we try to get an object from the loaded magazine
210a8806e5eSIngo Weinhold 	// if it's not empty, or from the previous magazine if it's full
211a8806e5eSIngo Weinhold 	// and finally from the Slab if the magazine depot has no full magazines.
212a8806e5eSIngo Weinhold 
213a8806e5eSIngo Weinhold 	if (store->loaded == NULL)
214a8806e5eSIngo Weinhold 		return NULL;
215a8806e5eSIngo Weinhold 
216a8806e5eSIngo Weinhold 	while (true) {
217*825566f8SIngo Weinhold 		if (!store->loaded->IsEmpty())
218*825566f8SIngo Weinhold 			return store->loaded->Pop();
219a8806e5eSIngo Weinhold 
220*825566f8SIngo Weinhold 		if (store->previous
221*825566f8SIngo Weinhold 			&& (store->previous->IsFull()
222*825566f8SIngo Weinhold 				|| exchange_with_full(depot, store->previous))) {
223a8806e5eSIngo Weinhold 			std::swap(store->previous, store->loaded);
224*825566f8SIngo Weinhold 		} else
225a8806e5eSIngo Weinhold 			return NULL;
226a8806e5eSIngo Weinhold 	}
227a8806e5eSIngo Weinhold }
228a8806e5eSIngo Weinhold 
229a8806e5eSIngo Weinhold 
230a8806e5eSIngo Weinhold static int
231a8806e5eSIngo Weinhold object_depot_return_to_store(object_depot* depot, depot_cpu_store* store,
232a8806e5eSIngo Weinhold 	void* object)
233a8806e5eSIngo Weinhold {
234a8806e5eSIngo Weinhold 	RecursiveLocker _(store->lock);
235a8806e5eSIngo Weinhold 
236a8806e5eSIngo Weinhold 	// We try to add the object to the loaded magazine if we have one
237a8806e5eSIngo Weinhold 	// and it's not full, or to the previous one if it is empty. If
238a8806e5eSIngo Weinhold 	// the magazine depot doesn't provide us with a new empty magazine
239a8806e5eSIngo Weinhold 	// we return the object directly to the slab.
240a8806e5eSIngo Weinhold 
241a8806e5eSIngo Weinhold 	while (true) {
242*825566f8SIngo Weinhold 		if (store->loaded && store->loaded->Push(object))
243a8806e5eSIngo Weinhold 			return 1;
244a8806e5eSIngo Weinhold 
245*825566f8SIngo Weinhold 		if ((store->previous && store->previous->IsEmpty())
246a8806e5eSIngo Weinhold 			|| exchange_with_empty(depot, store->previous))
247a8806e5eSIngo Weinhold 			std::swap(store->loaded, store->previous);
248a8806e5eSIngo Weinhold 		else
249a8806e5eSIngo Weinhold 			return 0;
250a8806e5eSIngo Weinhold 	}
251a8806e5eSIngo Weinhold }
252a8806e5eSIngo Weinhold 
253a8806e5eSIngo Weinhold 
254a8806e5eSIngo Weinhold void*
255a8806e5eSIngo Weinhold object_depot_obtain(object_depot* depot)
256a8806e5eSIngo Weinhold {
257a8806e5eSIngo Weinhold 	return object_depot_obtain_from_store(depot, object_depot_cpu(depot));
258a8806e5eSIngo Weinhold }
259a8806e5eSIngo Weinhold 
260a8806e5eSIngo Weinhold 
261a8806e5eSIngo Weinhold int
262a8806e5eSIngo Weinhold object_depot_store(object_depot* depot, void* object)
263a8806e5eSIngo Weinhold {
264a8806e5eSIngo Weinhold 	return object_depot_return_to_store(depot, object_depot_cpu(depot),
265a8806e5eSIngo Weinhold 		object);
266a8806e5eSIngo Weinhold }
267a8806e5eSIngo Weinhold 
268a8806e5eSIngo Weinhold 
269a8806e5eSIngo Weinhold void
270a8806e5eSIngo Weinhold object_depot_make_empty(object_depot* depot)
271a8806e5eSIngo Weinhold {
272a8806e5eSIngo Weinhold 	for (int i = 0; i < smp_get_num_cpus(); i++) {
273a8806e5eSIngo Weinhold 		depot_cpu_store* store = &depot->stores[i];
274a8806e5eSIngo Weinhold 
275a8806e5eSIngo Weinhold 		RecursiveLocker _(store->lock);
276a8806e5eSIngo Weinhold 
277a8806e5eSIngo Weinhold 		if (depot->stores[i].loaded)
278a8806e5eSIngo Weinhold 			empty_magazine(depot, depot->stores[i].loaded);
279a8806e5eSIngo Weinhold 		if (depot->stores[i].previous)
280a8806e5eSIngo Weinhold 			empty_magazine(depot, depot->stores[i].previous);
281a8806e5eSIngo Weinhold 		depot->stores[i].loaded = depot->stores[i].previous = NULL;
282a8806e5eSIngo Weinhold 	}
283a8806e5eSIngo Weinhold 
284a8806e5eSIngo Weinhold 	RecursiveLocker _(depot->lock);
285a8806e5eSIngo Weinhold 
286a8806e5eSIngo Weinhold 	while (depot->full)
287a8806e5eSIngo Weinhold 		empty_magazine(depot, _pop(depot->full));
288a8806e5eSIngo Weinhold 
289a8806e5eSIngo Weinhold 	while (depot->empty)
290a8806e5eSIngo Weinhold 		empty_magazine(depot, _pop(depot->empty));
291a8806e5eSIngo Weinhold }
292