haiku.git

/*
 * Copyright 2010, Ingo Weinhold, ingo_weinhold@gmx.de.
 * Copyright 2008-2010, Axel Dörfler. All Rights Reserved.
 * Copyright 2007, Hugo Santos. All Rights Reserved.
 *
 * Distributed under the terms of the MIT License.
 */


#include "ObjectDepot.h"

#include <algorithm>

#include <interrupts.h>
#include <slab/Slab.h>
#include <smp.h>
#include <util/AutoLock.h>

#include "slab_debug.h"
#include "slab_private.h"
#include "slab_queue.h"


struct DepotMagazine : public slab_queue_link {
			uint16				current_round;
			uint16				round_count;
			void*				rounds[0];

public:
	inline	bool				IsEmpty() const;
	inline	bool				IsFull() const;

	inline	void*				Pop();
	inline	bool				Push(void* object);

#if PARANOID_KERNEL_FREE
			bool				ContainsObject(void* object) const;
#endif
};


#if PARANOID_KERNEL_FREE
struct depot_cpu_store {
	DepotMagazine*	obtain;
	DepotMagazine*	store;
};
#else
struct depot_cpu_store {
	DepotMagazine*	loaded;
	DepotMagazine*	previous;
};
#endif


RANGE_MARKER_FUNCTION_BEGIN(SlabObjectDepot)


bool
DepotMagazine::IsEmpty() const
{
	return current_round == 0;
}


bool
DepotMagazine::IsFull() const
{
	return current_round == round_count;
}


void*
DepotMagazine::Pop()
{
	return rounds[--current_round];
}


bool
DepotMagazine::Push(void* object)
{
	if (IsFull())
		return false;

	rounds[current_round++] = object;
	return true;
}


#if PARANOID_KERNEL_FREE

bool
DepotMagazine::ContainsObject(void* object) const
{
	for (uint16 i = 0; i < current_round; i++) {
		if (rounds[i] == object)
			return true;
	}

	return false;
}

#endif // PARANOID_KERNEL_FREE


// #pragma mark -


static DepotMagazine*
alloc_magazine(object_depot* depot, uint32 flags)
{
	DepotMagazine* magazine = (DepotMagazine*)slab_internal_alloc(
		sizeof(DepotMagazine) + depot->magazine_capacity * sizeof(void*),
		flags);
	if (magazine) {
		magazine->next = NULL;
		magazine->current_round = 0;
		magazine->round_count = depot->magazine_capacity;
	}

	return magazine;
}


static void
free_magazine(DepotMagazine* magazine, uint32 flags)
{
	slab_internal_free(magazine, flags);
}


static void
empty_magazine(object_depot* depot, DepotMagazine* magazine, uint32 flags)
{
	for (uint16 i = 0; i < magazine->current_round; i++)
		depot->return_object(depot, depot->cookie, magazine->rounds[i], flags);
	free_magazine(magazine, flags);
}


static bool
exchange_with_full(object_depot* depot, DepotMagazine*& magazine)
{
	ASSERT(magazine == NULL || magazine->IsEmpty());

	SpinLocker _(depot->inner_lock);

	if (depot->full.head == NULL)
		return false;

	if (magazine != NULL) {
		depot->empty.Push(magazine);
		depot->empty_count++;
	}

	magazine = (DepotMagazine*)depot->full.Pop();
	depot->full_count--;
	return true;
}


static bool
exchange_with_empty(object_depot* depot, DepotMagazine*& magazine,
	DepotMagazine*& freeMagazine)
{
	ASSERT(magazine == NULL || magazine->IsFull());

#if PARANOID_KERNEL_FREE
	if (magazine != NULL) {
		// Reverse the rounds in the magazine so we get FIFO, not LIFO.
		for (int i = 0; i < magazine->current_round / 2; i++)
			std::swap(magazine->rounds[i], magazine->rounds[magazine->current_round - i - 1]);
	}
#endif

	SpinLocker _(depot->inner_lock);

	if (depot->empty.head == NULL)
		return false;

	if (magazine != NULL) {
		if (depot->full_count < depot->max_count) {
			depot->full.Push(magazine);
			depot->full_count++;
			freeMagazine = NULL;
		} else
			freeMagazine = magazine;
	}

	magazine = (DepotMagazine*)depot->empty.Pop();
	depot->empty_count--;
	return true;
}


static void
push_empty_magazine(object_depot* depot, DepotMagazine* magazine)
{
	SpinLocker _(depot->inner_lock);

	depot->empty.Push(magazine);
	depot->empty_count++;
}


static inline depot_cpu_store*
object_depot_cpu(object_depot* depot)
{
	return &depot->stores[smp_get_current_cpu()];
}


// #pragma mark - public API


status_t
object_depot_init(object_depot* depot, size_t capacity, size_t maxCount,
	uint32 flags, void* cookie, void (*return_object)(object_depot* depot,
		void* cookie, void* object, uint32 flags))
{
	depot->full.Init();
	depot->empty.Init();
	depot->full_count = depot->empty_count = 0;
	depot->max_count = maxCount;
	depot->magazine_capacity = capacity;

	rw_lock_init(&depot->outer_lock, "object depot");
	B_INITIALIZE_SPINLOCK(&depot->inner_lock);

	int cpuCount = smp_get_num_cpus();
	depot->stores = (depot_cpu_store*)slab_internal_alloc(
		sizeof(depot_cpu_store) * cpuCount, flags);
	if (depot->stores == NULL) {
		rw_lock_destroy(&depot->outer_lock);
		return B_NO_MEMORY;
	}

	for (int i = 0; i < cpuCount; i++) {
#if PARANOID_KERNEL_FREE
		depot->stores[i].obtain = NULL;
		depot->stores[i].store = NULL;
#else
		depot->stores[i].loaded = NULL;
		depot->stores[i].previous = NULL;
#endif
	}

	depot->cookie = cookie;
	depot->return_object = return_object;

	return B_OK;
}


void
object_depot_destroy(object_depot* depot, uint32 flags)
{
	object_depot_make_empty(depot, flags);

	slab_internal_free(depot->stores, flags);

	rw_lock_destroy(&depot->outer_lock);
}


void*
object_depot_obtain(object_depot* depot)
{
	ReadLocker readLocker(depot->outer_lock);
	InterruptsLocker interruptsLocker;

	depot_cpu_store* store = object_depot_cpu(depot);

#if PARANOID_KERNEL_FREE
	// When paranoid free is enabled, we want to defer object reuse,
	// instead of reusing as rapidly as possible. Thus we always exchange
	// full and empty magazines with the depot.

	if (store->obtain == NULL || store->obtain->IsEmpty()) {
		if (!exchange_with_full(depot, store->obtain))
			return NULL;
	}

	return store->obtain->Pop();
#else
	// To better understand both the Alloc() and Free() logic refer to
	// Bonwick's ``Magazines and Vmem'' [in 2001 USENIX proceedings]

	// In a nutshell, we try to get an object from the loaded magazine
	// if it's not empty, or from the previous magazine if it's full
	// and finally from the Slab if the magazine depot has no full magazines.

	if (store->loaded == NULL)
		return NULL;

	while (true) {
		if (!store->loaded->IsEmpty())
			return store->loaded->Pop();

		if (store->previous != NULL
			&& (store->previous->IsFull()
				|| exchange_with_full(depot, store->previous))) {
			std::swap(store->previous, store->loaded);
		} else
			return NULL;
	}
#endif
}


void
object_depot_store(object_depot* depot, void* object, uint32 flags)
{
	ReadLocker readLocker(depot->outer_lock);
	InterruptsLocker interruptsLocker;

	depot_cpu_store* store = object_depot_cpu(depot);

	while (true) {
#if PARANOID_KERNEL_FREE
		if (store->store != NULL && store->store->Push(object))
			return;

		DepotMagazine* freeMagazine = NULL;
		if (exchange_with_empty(depot, store->store, freeMagazine)) {
#else
		// We try to add the object to the loaded magazine if we have one
		// and it's not full, or to the previous one if it is empty. If
		// the magazine depot doesn't provide us with a new empty magazine
		// we return the object directly to the slab.

		if (store->loaded != NULL && store->loaded->Push(object))
			return;

		DepotMagazine* freeMagazine = NULL;
		if ((store->previous != NULL && store->previous->IsEmpty())
			|| exchange_with_empty(depot, store->previous, freeMagazine)) {
			std::swap(store->loaded, store->previous);
#endif
			if (freeMagazine != NULL) {
				// Free the magazine that didn't have space in the list
				interruptsLocker.Unlock();
				readLocker.Unlock();

				empty_magazine(depot, freeMagazine, flags);

				readLocker.Lock();
				interruptsLocker.Lock();

				store = object_depot_cpu(depot);
			}
		} else {
			// allocate a new empty magazine
			interruptsLocker.Unlock();
			readLocker.Unlock();

			DepotMagazine* magazine = alloc_magazine(depot, flags);
			if (magazine == NULL) {
				depot->return_object(depot, depot->cookie, object, flags);
				return;
			}

			readLocker.Lock();
			interruptsLocker.Lock();

			push_empty_magazine(depot, magazine);
			store = object_depot_cpu(depot);
		}
	}
}


void
object_depot_make_empty(object_depot* depot, uint32 flags)
{
	WriteLocker writeLocker(depot->outer_lock);

	// collect the store magazines

	slab_queue storeMagazines;
	storeMagazines.Init();

	int cpuCount = smp_get_num_cpus();
	for (int i = 0; i < cpuCount; i++) {
		depot_cpu_store& store = depot->stores[i];

#if PARANOID_KERNEL_FREE
		if (store.obtain != NULL) {
			storeMagazines.Push(store.obtain);
			store.obtain = NULL;
		}

		if (store.store != NULL) {
			storeMagazines.Push(store.store);
			store.store = NULL;
		}
#else
		if (store.loaded != NULL) {
			storeMagazines.Push(store.loaded);
			store.loaded = NULL;
		}

		if (store.previous != NULL) {
			storeMagazines.Push(store.previous);
			store.previous = NULL;
		}
#endif
	}

	// detach the depot's full and empty magazines

	slab_queue fullMagazines = depot->full;
	depot->full.Init();

	slab_queue emptyMagazines = depot->empty;
	depot->empty.Init();

	writeLocker.Unlock();

	// free all magazines

	while (storeMagazines.head != NULL)
		empty_magazine(depot, (DepotMagazine*)storeMagazines.Pop(), flags);

	while (fullMagazines.head != NULL)
		empty_magazine(depot, (DepotMagazine*)fullMagazines.Pop(), flags);

	while (emptyMagazines.head != NULL)
		free_magazine((DepotMagazine*)emptyMagazines.Pop(), flags);
}


#if PARANOID_KERNEL_FREE

bool
object_depot_contains_object(object_depot* depot, void* object)
{
	WriteLocker writeLocker(depot->outer_lock);

	int cpuCount = smp_get_num_cpus();
	for (int i = 0; i < cpuCount; i++) {
		depot_cpu_store& store = depot->stores[i];

		if (store.obtain != NULL && !store.obtain->IsEmpty()) {
			if (store.obtain->ContainsObject(object))
				return true;
		}

		if (store.store != NULL && !store.store->IsEmpty()) {
			if (store.store->ContainsObject(object))
				return true;
		}
	}

	for (DepotMagazine* magazine = (DepotMagazine*)depot->full.head; magazine != NULL;
			magazine = (DepotMagazine*)magazine->next) {
		if (magazine->ContainsObject(object))
			return true;
	}

	return false;
}

#endif // PARANOID_KERNEL_FREE


// #pragma mark - private kernel API


void
dump_object_depot(object_depot* depot)
{
	kprintf("  full:     %p, count %lu\n", depot->full.head, depot->full_count);
	kprintf("  empty:    %p, count %lu\n", depot->empty.head, depot->empty_count);
	kprintf("  max full: %lu\n", depot->max_count);
	kprintf("  capacity: %lu\n", depot->magazine_capacity);
	kprintf("  stores:\n");

	int cpuCount = smp_get_num_cpus();

#if PARANOID_KERNEL_FREE
	for (int i = 0; i < cpuCount; i++) {
		kprintf("  [%d] obtain:   %p\n", i, depot->stores[i].obtain);
		kprintf("      store:    %p\n", depot->stores[i].store);
	}
#else
	for (int i = 0; i < cpuCount; i++) {
		kprintf("  [%d] loaded:   %p\n", i, depot->stores[i].loaded);
		kprintf("      previous: %p\n", depot->stores[i].previous);
	}
#endif
}


int
dump_object_depot(int argCount, char** args)
{
	if (argCount != 2)
		kprintf("usage: %s [address]\n", args[0]);
	else
		dump_object_depot((object_depot*)parse_expression(args[1]));

	return 0;
}


int
dump_depot_magazine(int argCount, char** args)
{
	if (argCount != 2) {
		kprintf("usage: %s [address]\n", args[0]);
		return 0;
	}

	DepotMagazine* magazine = (DepotMagazine*)parse_expression(args[1]);

	kprintf("next:          %p\n", magazine->next);
	kprintf("current_round: %u\n", magazine->current_round);
	kprintf("round_count:   %u\n", magazine->round_count);

	for (uint16 i = 0; i < magazine->current_round; i++)
		kprintf("  [%i] %p\n", i, magazine->rounds[i]);

	return 0;
}


RANGE_MARKER_FUNCTION_END(SlabObjectDepot)