1/*
2 * Copyright 2010, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Copyright 2008-2010, Axel D��rfler. All Rights Reserved.
4 * Copyright 2007, Hugo Santos. All Rights Reserved.
5 *
6 * Distributed under the terms of the MIT License.
7 */
8
9
10#include <slab/ObjectDepot.h>
11
12#include <algorithm>
13
14#include <int.h>
15#include <slab/Slab.h>
16#include <smp.h>
17#include <util/AutoLock.h>
18
19#include "slab_debug.h"
20#include "slab_private.h"
21
22
23struct DepotMagazine {
24			DepotMagazine*		next;
25			uint16				current_round;
26			uint16				round_count;
27			void*				rounds[0];
28
29public:
30	inline	bool				IsEmpty() const;
31	inline	bool				IsFull() const;
32
33	inline	void*				Pop();
34	inline	bool				Push(void* object);
35
36#if PARANOID_KERNEL_FREE
37			bool				ContainsObject(void* object) const;
38#endif
39};
40
41
42struct depot_cpu_store {
43	DepotMagazine*	loaded;
44	DepotMagazine*	previous;
45};
46
47
48RANGE_MARKER_FUNCTION_BEGIN(SlabObjectDepot)
49
50
51bool
52DepotMagazine::IsEmpty() const
53{
54	return current_round == 0;
55}
56
57
58bool
59DepotMagazine::IsFull() const
60{
61	return current_round == round_count;
62}
63
64
65void*
66DepotMagazine::Pop()
67{
68	return rounds[--current_round];
69}
70
71
72bool
73DepotMagazine::Push(void* object)
74{
75	if (IsFull())
76		return false;
77
78	rounds[current_round++] = object;
79	return true;
80}
81
82
83#if PARANOID_KERNEL_FREE
84
85bool
86DepotMagazine::ContainsObject(void* object) const
87{
88	for (uint16 i = 0; i < current_round; i++) {
89		if (rounds[i] == object)
90			return true;
91	}
92
93	return false;
94}
95
96#endif // PARANOID_KERNEL_FREE
97
98
99// #pragma mark -
100
101
102static DepotMagazine*
103alloc_magazine(object_depot* depot, uint32 flags)
104{
105	DepotMagazine* magazine = (DepotMagazine*)slab_internal_alloc(
106		sizeof(DepotMagazine) + depot->magazine_capacity * sizeof(void*),
107		flags);
108	if (magazine) {
109		magazine->next = NULL;
110		magazine->current_round = 0;
111		magazine->round_count = depot->magazine_capacity;
112	}
113
114	return magazine;
115}
116
117
118static void
119free_magazine(DepotMagazine* magazine, uint32 flags)
120{
121	slab_internal_free(magazine, flags);
122}
123
124
125static void
126empty_magazine(object_depot* depot, DepotMagazine* magazine, uint32 flags)
127{
128	for (uint16 i = 0; i < magazine->current_round; i++)
129		depot->return_object(depot, depot->cookie, magazine->rounds[i], flags);
130	free_magazine(magazine, flags);
131}
132
133
134static bool
135exchange_with_full(object_depot* depot, DepotMagazine*& magazine)
136{
137	ASSERT(magazine->IsEmpty());
138
139	SpinLocker _(depot->inner_lock);
140
141	if (depot->full == NULL)
142		return false;
143
144	depot->full_count--;
145	depot->empty_count++;
146
147	_push(depot->empty, magazine);
148	magazine = _pop(depot->full);
149	return true;
150}
151
152
153static bool
154exchange_with_empty(object_depot* depot, DepotMagazine*& magazine,
155	DepotMagazine*& freeMagazine)
156{
157	ASSERT(magazine == NULL || magazine->IsFull());
158
159	SpinLocker _(depot->inner_lock);
160
161	if (depot->empty == NULL)
162		return false;
163
164	depot->empty_count--;
165
166	if (magazine != NULL) {
167		if (depot->full_count < depot->max_count) {
168			_push(depot->full, magazine);
169			depot->full_count++;
170			freeMagazine = NULL;
171		} else
172			freeMagazine = magazine;
173	}
174
175	magazine = _pop(depot->empty);
176	return true;
177}
178
179
180static void
181push_empty_magazine(object_depot* depot, DepotMagazine* magazine)
182{
183	SpinLocker _(depot->inner_lock);
184
185	_push(depot->empty, magazine);
186	depot->empty_count++;
187}
188
189
190static inline depot_cpu_store*
191object_depot_cpu(object_depot* depot)
192{
193	return &depot->stores[smp_get_current_cpu()];
194}
195
196
197// #pragma mark - public API
198
199
200status_t
201object_depot_init(object_depot* depot, size_t capacity, size_t maxCount,
202	uint32 flags, void* cookie, void (*return_object)(object_depot* depot,
203		void* cookie, void* object, uint32 flags))
204{
205	depot->full = NULL;
206	depot->empty = NULL;
207	depot->full_count = depot->empty_count = 0;
208	depot->max_count = maxCount;
209	depot->magazine_capacity = capacity;
210
211	rw_lock_init(&depot->outer_lock, "object depot");
212	B_INITIALIZE_SPINLOCK(&depot->inner_lock);
213
214	int cpuCount = smp_get_num_cpus();
215	depot->stores = (depot_cpu_store*)slab_internal_alloc(
216		sizeof(depot_cpu_store) * cpuCount, flags);
217	if (depot->stores == NULL) {
218		rw_lock_destroy(&depot->outer_lock);
219		return B_NO_MEMORY;
220	}
221
222	for (int i = 0; i < cpuCount; i++) {
223		depot->stores[i].loaded = NULL;
224		depot->stores[i].previous = NULL;
225	}
226
227	depot->cookie = cookie;
228	depot->return_object = return_object;
229
230	return B_OK;
231}
232
233
234void
235object_depot_destroy(object_depot* depot, uint32 flags)
236{
237	object_depot_make_empty(depot, flags);
238
239	slab_internal_free(depot->stores, flags);
240
241	rw_lock_destroy(&depot->outer_lock);
242}
243
244
245void*
246object_depot_obtain(object_depot* depot)
247{
248	ReadLocker readLocker(depot->outer_lock);
249	InterruptsLocker interruptsLocker;
250
251	depot_cpu_store* store = object_depot_cpu(depot);
252
253	// To better understand both the Alloc() and Free() logic refer to
254	// Bonwick's ``Magazines and Vmem'' [in 2001 USENIX proceedings]
255
256	// In a nutshell, we try to get an object from the loaded magazine
257	// if it's not empty, or from the previous magazine if it's full
258	// and finally from the Slab if the magazine depot has no full magazines.
259
260	if (store->loaded == NULL)
261		return NULL;
262
263	while (true) {
264		if (!store->loaded->IsEmpty())
265			return store->loaded->Pop();
266
267		if (store->previous
268			&& (store->previous->IsFull()
269				|| exchange_with_full(depot, store->previous))) {
270			std::swap(store->previous, store->loaded);
271		} else
272			return NULL;
273	}
274}
275
276
277void
278object_depot_store(object_depot* depot, void* object, uint32 flags)
279{
280	ReadLocker readLocker(depot->outer_lock);
281	InterruptsLocker interruptsLocker;
282
283	depot_cpu_store* store = object_depot_cpu(depot);
284
285	// We try to add the object to the loaded magazine if we have one
286	// and it's not full, or to the previous one if it is empty. If
287	// the magazine depot doesn't provide us with a new empty magazine
288	// we return the object directly to the slab.
289
290	while (true) {
291		if (store->loaded != NULL && store->loaded->Push(object))
292			return;
293
294		DepotMagazine* freeMagazine = NULL;
295		if ((store->previous != NULL && store->previous->IsEmpty())
296			|| exchange_with_empty(depot, store->previous, freeMagazine)) {
297			std::swap(store->loaded, store->previous);
298
299			if (freeMagazine != NULL) {
300				// Free the magazine that didn't have space in the list
301				interruptsLocker.Unlock();
302				readLocker.Unlock();
303
304				empty_magazine(depot, freeMagazine, flags);
305
306				readLocker.Lock();
307				interruptsLocker.Lock();
308
309				store = object_depot_cpu(depot);
310			}
311		} else {
312			// allocate a new empty magazine
313			interruptsLocker.Unlock();
314			readLocker.Unlock();
315
316			DepotMagazine* magazine = alloc_magazine(depot, flags);
317			if (magazine == NULL) {
318				depot->return_object(depot, depot->cookie, object, flags);
319				return;
320			}
321
322			readLocker.Lock();
323			interruptsLocker.Lock();
324
325			push_empty_magazine(depot, magazine);
326			store = object_depot_cpu(depot);
327		}
328	}
329}
330
331
332void
333object_depot_make_empty(object_depot* depot, uint32 flags)
334{
335	WriteLocker writeLocker(depot->outer_lock);
336
337	// collect the store magazines
338
339	DepotMagazine* storeMagazines = NULL;
340
341	int cpuCount = smp_get_num_cpus();
342	for (int i = 0; i < cpuCount; i++) {
343		depot_cpu_store& store = depot->stores[i];
344
345		if (store.loaded) {
346			_push(storeMagazines, store.loaded);
347			store.loaded = NULL;
348		}
349
350		if (store.previous) {
351			_push(storeMagazines, store.previous);
352			store.previous = NULL;
353		}
354	}
355
356	// detach the depot's full and empty magazines
357
358	DepotMagazine* fullMagazines = depot->full;
359	depot->full = NULL;
360
361	DepotMagazine* emptyMagazines = depot->empty;
362	depot->empty = NULL;
363
364	writeLocker.Unlock();
365
366	// free all magazines
367
368	while (storeMagazines != NULL)
369		empty_magazine(depot, _pop(storeMagazines), flags);
370
371	while (fullMagazines != NULL)
372		empty_magazine(depot, _pop(fullMagazines), flags);
373
374	while (emptyMagazines)
375		free_magazine(_pop(emptyMagazines), flags);
376}
377
378
379#if PARANOID_KERNEL_FREE
380
381bool
382object_depot_contains_object(object_depot* depot, void* object)
383{
384	WriteLocker writeLocker(depot->outer_lock);
385
386	int cpuCount = smp_get_num_cpus();
387	for (int i = 0; i < cpuCount; i++) {
388		depot_cpu_store& store = depot->stores[i];
389
390		if (store.loaded != NULL && !store.loaded->IsEmpty()) {
391			if (store.loaded->ContainsObject(object))
392				return true;
393		}
394
395		if (store.previous != NULL && !store.previous->IsEmpty()) {
396			if (store.previous->ContainsObject(object))
397				return true;
398		}
399	}
400
401	for (DepotMagazine* magazine = depot->full; magazine != NULL;
402			magazine = magazine->next) {
403		if (magazine->ContainsObject(object))
404			return true;
405	}
406
407	return false;
408}
409
410#endif // PARANOID_KERNEL_FREE
411
412
413// #pragma mark - private kernel API
414
415
416void
417dump_object_depot(object_depot* depot)
418{
419	kprintf("  full:     %p, count %lu\n", depot->full, depot->full_count);
420	kprintf("  empty:    %p, count %lu\n", depot->empty, depot->empty_count);
421	kprintf("  max full: %lu\n", depot->max_count);
422	kprintf("  capacity: %lu\n", depot->magazine_capacity);
423	kprintf("  stores:\n");
424
425	int cpuCount = smp_get_num_cpus();
426
427	for (int i = 0; i < cpuCount; i++) {
428		kprintf("  [%d] loaded:   %p\n", i, depot->stores[i].loaded);
429		kprintf("      previous: %p\n", depot->stores[i].previous);
430	}
431}
432
433
434int
435dump_object_depot(int argCount, char** args)
436{
437	if (argCount != 2)
438		kprintf("usage: %s [address]\n", args[0]);
439	else
440		dump_object_depot((object_depot*)parse_expression(args[1]));
441
442	return 0;
443}
444
445
446int
447dump_depot_magazine(int argCount, char** args)
448{
449	if (argCount != 2) {
450		kprintf("usage: %s [address]\n", args[0]);
451		return 0;
452	}
453
454	DepotMagazine* magazine = (DepotMagazine*)parse_expression(args[1]);
455
456	kprintf("next:          %p\n", magazine->next);
457	kprintf("current_round: %u\n", magazine->current_round);
458	kprintf("round_count:   %u\n", magazine->round_count);
459
460	for (uint16 i = 0; i < magazine->current_round; i++)
461		kprintf("  [%i] %p\n", i, magazine->rounds[i]);
462
463	return 0;
464}
465
466
467RANGE_MARKER_FUNCTION_END(SlabObjectDepot)
468