memmgr.c copy

ati driver

//#include "vmemmgr.h"
#include <stdlib.h>
#include <KernelExport.h>
#include <limits.h>
#include "../include/benaphore.h"
#include "../common/utils.h"
#include <string.h>

#ifdef __cplusplus
extern "C" {
#endif

void    _kdprintf_(const char *format, ...);
//bool    set_dprintf_enabled(bool);	/* returns old enable flag */

#ifdef __cplusplus
}
#endif

#define dprintf _kdprintf_


extern int debug_level_flow;
extern int debug_level_info;
extern int debug_level_error;

#define DEBUG_MSG_PREFIX "Radeon - "

#include "../include/debug_ext.h"

typedef struct free_entry {
	struct free_entry *next;
} free_entry;

typedef struct vmem_entry {
	struct vmem_entry *next, *prev;
	int pos;
	int num_blocks;
	struct vmem_client *client;
	struct vmem_entry_user *alloc_user;
	uint id;
} vmem_entry;

typedef struct vmem_entry_user {
	int prev, next;
	void *cookie_user;
	int last_access;
} vmem_entry_user;

typedef struct vmem_pool {
	struct vmem_client **clients;
	uint max_clients;
	size_t block_size;
	int block_shift;
	vmem_entry *first;
	vmem_entry *unused_list;
	uint max_allocs;
	vmem_entry *allocs;
	benaphore lock;
	free_entry *unused_clients;

	vmem_entry_user alloc_dummy;
	int num_blocks;
} vmem_pool;

typedef struct vmem_client {
	void *dev;
	struct vmem_user *user;
	struct vmem_entry_user *allocs;
	struct vmem_pool *pool;
	uint unused_list;
	uint max_allocs;
	uint discarded_list;
	area_id alloc_area_id;
	int id;
	
	struct vmem_client *prev, *next;
} vmem_client;

typedef struct vmem_dev_info {
	vmem_client *clients;
} vmem_dev_info;

typedef struct vmem_user {
	int timestamp;
} vmem_user;

#define vmem_entry_NOT_DISCARDED -1
#define vmem_entry_LOCKED -2


static vmem_client *vmem_check_client_id( vmem_pool *pool, uint client_id, vmem_dev_info *dev );

static float vmem_calc_costs( vmem_pool *pool, vmem_entry *start, int num_blocks )
{
	float costs = 0;
	
	for( 
		;
		num_blocks > 0; 
		num_blocks -= start->num_blocks, start = start->next ) 
	{
		vmem_client *client;
		int age;

		client = start->client;		
		if( client == NULL )
			continue;
			
		age = start->alloc_user->last_access - client->user->timestamp;
		
		if( age < 1 )
			age = 1;
			
		costs += (float)start->num_blocks / age;
	}
	
	return costs;
}

static void vmem_server_discard( vmem_pool *pool, vmem_entry *alloc )
{
	vmem_client *client;
	vmem_entry_user *alloc_user;
	
	client = alloc->client;
	alloc_user = alloc->alloc_user;
	
	alloc_user->next = client->discarded_list;
	alloc_user->prev = INT_MAX;
	client->discarded_list = alloc_user - client->allocs;
	
	alloc->alloc_user = &pool->alloc_dummy;
	alloc->client = NULL;
}	

static bool vmem_server_save_discard( vmem_pool *pool, vmem_entry *alloc )
{
	vmem_client *client;
	vmem_entry_user *alloc_user;
	
	client = alloc->client;
	alloc_user = alloc->alloc_user;
	
	if( alloc_user->prev <= vmem_entry_LOCKED )
		return false;
	
	alloc_user->next = client->discarded_list;
	alloc_user->prev = INT_MAX;
	client->discarded_list = alloc_user - client->allocs;
	
	alloc->alloc_user = &pool->alloc_dummy;
	alloc->client = NULL;
	return true;
}	

static inline vmem_entry *vmem_server_merge_allocs( vmem_pool *pool, 
	vmem_entry *alloc, bool merge_with_previous )
{
	vmem_entry *prev, *next;
	
	prev = alloc->prev;
	next = alloc->next;
	
	// if two blocks get merged, always the first one must remain 
	// (see vmem_discard_range)
	if( merge_with_previous && prev && prev->client == NULL ) {
		prev->num_blocks += alloc->num_blocks;
		
		prev->next = next;
		if( next )
			next->prev = prev;
			
		prev->next = pool->unused_list;
		pool->unused_list = prev;
			
		alloc = prev;
	}
	
	if( next && next->client == NULL ) {
		alloc->num_blocks += next->num_blocks;
		alloc->next = next->next;
		
		if( alloc->next )
			alloc->next->prev = alloc;

		next->next = pool->unused_list;
		pool->unused_list = next;
	}
	
	return alloc;
}

// allocation strategy:
// - we go through the entire range of vmemory, looking for the cheapest
//   range we could lay our hands on (i.e., locked vmemory is to be skipped)
// - in terms of costs: empty blocks are for free, non-empty are the
//   more expansive the bigger and the newer they are; costs are never negative
// - after we've found the cheapest place, all blocks in it are discarded
//   and a new one gets created instead

// specific allocation rules the code relies on:
// - any range must be start at the beginning of a block (skipping the 
//   beginning of a block doesn't lower the price, so there's no point doing that)
// - the block before the range must be non-empty; if it were, starting at
//   the empty block had the same price or were even cheaper if an non-empty
//   block wouldn't be overlapped anymore

static vmem_entry *vmem_find_block( vmem_pool *pool, int num_blocks )
{
	float best_costs = FLT_MAX;
	vmem_entry *best_alloc = NULL;
	vmem_entry *start, *cur;

	// be careful to not choose non-empty start-block after empty block
	for( 
		start = pool->first; 
		start; 
		start = start->client == NULL && start->next != NULL ? start->next->next : start->next ) 
	{
		float cur_costs;
		int left_blocks;
		
		for( 
			left_blocks = num_blocks, cur = start; 
			left_blocks > 0 && cur; ) 
		{
			if( cur->alloc_user->prev > vmem_entry_LOCKED ) {
				cur = cur->next;
				left_blocks -= cur->num_blocks;
			} else {
				start = cur = cur->next;
				left_blocks = num_blocks;
			} 
		}
			
		if( left_blocks > 0 ) 
			break;
			
		cur_costs = vmem_calc_costs( pool, start, num_blocks );

		if( cur_costs < best_costs ) {
			best_alloc = start;
			best_costs = cur_costs;
			
			if( best_costs == 0 )
				break;
		}
	}
	
	return best_alloc;
}

static bool vmem_server_save_discard_range( vmem_pool *pool, 
	vmem_entry *first, int num_blocks )
{
	vmem_entry *cur;
	
	cur = first;
	
	// the predecessor of "first" must not be empty;
	// this way, "first", which is made empty during the first iteration,
	// will remain during the entire process whereas all its successors
	// are "consumed" by it step by step (merging always adds the second block
	// to the first block); vmem_server_alloc relies on that!
	do {
		if( !vmem_server_save_discard( pool, cur ))
			return false;
		vmem_server_merge_allocs( pool, first, false );
		
		cur = first->next;
	} while( first->num_blocks < num_blocks );
	
	return true;
}

static int vmem_server_alloc( vmem_pool *pool, vmem_client *client, size_t size, vmem_entry **res_block )
{
	int num_blocks;
	vmem_entry_user *alloc_user;
	unsigned int alloc_user_id;

	vmem_entry *best_alloc;
	
	if( size == 0 ) {
		SHOW_ERROR0( 1, "tried to alloc block of size zero" );
		return B_BAD_VALUE;
	}

	// do the client alloc check in advance to simplify cleanup on error
	if( client->unused_list == INT_MAX ) {
		SHOW_ERROR0( 1, "Out of client vmemory blocks" );
		return B_NO_MEMORY;
	}
	
	if( client->allocs[client->unused_list].next != INT_MAX &&
		(uint)client->allocs[client->unused_list].next >= client->max_allocs )
	{
		SHOW_ERROR( 1, "Client destroyed unused_list of client blocks (next=%d)", 
			client->allocs[client->unused_list].next );
		return B_NOT_ALLOWED;
	}

	num_blocks = (size + pool->block_size - 1) >> pool->block_shift;

	best_alloc = vmem_find_block( pool, num_blocks );

	if( best_alloc == NULL ) {
		SHOW_ERROR( 1, "Couldn't find gap of requested size (%i bytes)", size );
		return B_NO_MEMORY;
	}

	if( !vmem_server_save_discard_range( pool, best_alloc, num_blocks ))
		return B_BUSY;
	
	if( best_alloc->num_blocks > num_blocks ) {
		vmem_entry *new_block;
		
		// we do this after looking for a proper gap as we 
		// may have freed a server block during search
		if( pool->unused_list == NULL ) {
			SHOW_ERROR0( 1, "no free server block to split free range" );
			// don't need to undo alloc as: 
			// - best_alloc is an empty range; just a pity for the allocs discarded
			// - previous alloc cannot be empty (would violate selection rules)
			// - next alloc cannot be empty as it had been merged during vmem_discard_range
			return B_NO_MEMORY;
		}
		
		new_block = pool->unused_list;
		pool->unused_list = new_block->next;
		
		new_block->pos = best_alloc->pos + num_blocks;
		new_block->num_blocks = best_alloc->num_blocks - num_blocks;
		new_block->client = NULL;
		best_alloc->num_blocks = num_blocks;

		new_block->next = best_alloc->next;
		if( new_block->next )
			new_block->next->prev = new_block;
			
		new_block->prev = best_alloc;
		best_alloc->next = new_block;
	}

	alloc_user = &client->allocs[client->unused_list];
	client->unused_list = alloc_user->next;
	
	alloc_user->prev = vmem_entry_NOT_DISCARDED;
	alloc_user->last_access = client->user->timestamp;
	best_alloc->alloc_user = alloc_user;

	*res_block	= best_alloc;
	
	return B_OK;
}

static status_t vmem_server_unmark_discarded( vmem_client *client, vmem_entry_user *alloc )
{
	uint prev_id, next_id;
	vmem_entry_user *prev, *next;
	
	prev_id = (uint)alloc->prev;
	next_id = (uint)alloc->next;
	
	if( prev_id != INT_MAX ) {
		if( prev_id >= client->max_allocs ) goto invalid_id;
		client->allocs[prev_id].next = next_id;
	} else {
		client->discarded_list = next_id;
	}
	
	if( next_id != INT_MAX ) {
		if( next_id >= client->max_allocs ) goto invalid_id;
		client->allocs[next_id].prev = prev_id;
	}
		
	return B_OK;
	
invalid_id:
	SHOW_ERROR( 1, "Client destroyed discarded client blocks (block=%d, prev=%d, next=%d)", 
		alloc - client->allocs, alloc->prev, alloc->next );
	return B_BAD_VALUE;
}
	
static status_t vmem_server_free( vmem_pool *pool, vmem_client *client, vmem_entry *alloc )
{
	vmem_entry_user *alloc_user;
	
	alloc_user = alloc->alloc_user;
	alloc->client = NULL;
	
	if( alloc_user->prev >= 0 )
		vmem_server_unmark_discarded( client, alloc_user );
	
	alloc_user->next = client->unused_list;
	client->unused_list = alloc_user - client->allocs;

	vmem_server_merge_allocs( pool, alloc, true );
	
	return B_OK;
}

typedef struct vmem_io_alloc {
	uint client_id;
	size_t size;