memmgr.c copy 3

ati driver

//#include "memmgr.h"
#include <stdlib.h>
#include <KernelExport.h>
#include <limits.h>

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"

#if 0
mem_info *mem_init( void *start, int len, int block_size )
{
	mem_block *first;
	mem_info *mem;
	
	first = malloc( sizeof( *first ));
	if( first == NULL )
		return NULL;
		
	first->base = start;
	first->size = len;
	first->prev = first->next = NULL;
	first->inuse = false;
	
	mem = malloc( sizeof( *mem ));
	if( mem == NULL ) {
		free( first );
		return NULL;
	}
	
	mem->first = first;
	
	return mem;
}

void mem_destroy( mem_info *info )
{
	mem_block *cur, *next;
	
	for( cur = info->first; cur; cur = next ) {
		next = cur->next;
		
		free( cur );
	}
	
	free( info );
}

#endif

typedef struct mem_block_server {
	struct mem_block_server *next, *prev;
	int pos;
	int num_blocks;
	int client_id_header;
	struct mem_block_client *block_client;
} mem_block_server;

typedef struct mem_header_server {
	struct mem_header_client **clients;
	int block_size;
	int block_size_shift;
	mem_block_server *first_block;
	mem_block_server *unused_list;
} mem_header_server;

typedef struct mem_header_client {
	struct mem_header_user *header_user;
	struct mem_block_client *blocks;
	struct mem_header_server *header_server;
	int free_list;
} mem_header_client;

typedef struct mem_header_user {
	int timestamp;
	int discarded_list;
} mem_header_user;

#define MEM_BLOCK_NOT_DISCARDED -1
#define MEM_BLOCK_LOCKED -2

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

float mem_calc_costs( mem_header_server *header_server, mem_block_server *start_block, int num_blocks )
{
	float costs = 0;
	
	for( 
		;
		num_blocks > 0; 
		num_blocks -= start_block->num_blocks, start_block = start_block->next ) 
	{
		mem_header_client *header_client;
		float age;
		
		if( start_block->client_id_header < 0 )
			continue;
			
		header_client = header_server->clients[start_block->client_id_header];
			
		age = start_block->block_client->last_access - 
			header_client->header_user->timestamp;
		
		if( age < 1 )
			age = 1;
			
		costs += start_block->num_blocks / age;
	}
	
	return costs;
}

void mem_server_discard( mem_header_server *header_server, mem_block_server *block_server )
{
	mem_header_client *header_client;
	mem_header_user *header_user;
	mem_block_client *block_client;
	
	header_client = header_server->clients[block_server->client_id_header];
	header_user = header_client->header_user;
	block_client = block_server->block_client;
	
	block_client->next = header_user->discarded_list;
	block_client->prev = 0;
	header_user->discarded_list = block_client - header_client->blocks;	
}	

static inline mem_block_server *mem_merge_blocks( mem_header_server *header_server, 
	mem_block_server *block_server, int merge_with_previous )
{
	mem_block_server *prev, *next;
	
	prev = block_server->prev;
	next = block_server->next;
	
	// if two blocks get merged, always the first one must remain 
	// (see mem_server_alloc)
	if( merge_with_previous && prev && prev->client_id_header < 0 ) {
		prev->num_blocks += block_server->num_blocks;
		
		prev->next = next;
		if( next )
			next->prev = prev;
			
		prev->next = header_server->unused_list;
		header_server->unused_list = prev;
			
		block_server = prev;
	}
	
	if( next && next->client_id_header < 0 ) {
		block_server->num_blocks += next->num_blocks;
		block_server->next = next->next;
		
		if( block_server->next )
			block_server->next->prev = block_server;

		next->next = header_server->unused_list;
		header_server->unused_list = next;
	}
	
	return block_server;
}

// allocation strategy:
// - we go through the entire range of memory, looking for the cheapest
//   range we could lay our hands on (i.e., locked memory 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

if we've found one, all blocks in it are discarded
		// don't replace if current costs are the same, as we guarantee that
		// best_block has no empty predecessor; reason: comparing the costs
		// of a range starting at an empty block A with a range starting with
		// A's (non-empty) successor B, the second case cannot be cheaper as 
		// the empty block A used in the first case is for free and any new
		// block that had to be used instead of A in the second case cannot
		// be cheaper as being for free (if the last block of the first case
		// is too long, we may not need a new block for the second case, so
		// both cases have the same cost), if we have a tie, first case wins
		// as it got tested first


mem_block_server *mem_find_block( mem_header_server *header_server, int num_blocks )
{
	float best_costs = FLT_MAX;
	mem_block_server *best_block = NULL;
	mem_block_server *start_block, *cur_block;

	for( 
		start_block = header_server->first_block; 
		start_block; 
		start_block = start_block->next ) 
	{
		float cur_costs;
		int left_blocks;
		
		for( 
			left_blocks = num_blocks, cur_block = start_block; 
			left_blocks > 0 && cur_block; ) 
		{
			if( cur_block->block_client->prev > MEM_BLOCK_LOCKED ) {
				cur_block = cur_block->next;
				left_blocks -= cur_block->num_blocks;
			} else {
				start_block = cur_block = cur_block->next;
				left_blocks = num_blocks;
			} 
		}
			
		if( left_blocks > 0 ) 
			break;
			
		cur_costs = mem_calc_costs( header_server, start_block, num_blocks );

		if( cur_costs < best_costs ) {
			best_block = start_block;
			best_costs = cur_costs;
			
			if( best_costs == 0 )
				break;
		}
	}
	
	return best_block;
}

void mem_discard_range( mem_header_server *header_server, 
	mem_block_server *first_block, int num_blocks )
{
	mem_block_server *cur_block;
	
	// we assume that the predecessor of first_block is not empty;
	// this way, first_block, 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)
	for( 
		cur_block = first_block; 
		first_block->num_blocks < num_blocks; 
		cur_block = first_block->next ) 
	{
		mem_server_discard( header_server, cur_block );
		mem_merge_blocks( header_server, first_block, false );
	}
}

int mem_server_alloc( mem_header_client *header_client, int size )
{
	int num_blocks;
	mem_header_server *header_server = header_client->header_server;
	mem_block_server *start_block;

	int left_blocks;
	mem_block_server *cur_block, *best_block;
	int cur_pos;
	
	if( size == 0 ) {
		SHOW_ERROR0( 1, "tried to alloc block of size zero" );
		return B_BAD_VALUE;
	}

	if( header_client->free_list < 0 ) {
		SHOW_ERROR0( 1, "Out of client memory blocks" );
		return B_NO_MEMORY;
	}
	
	num_blocks = (size + header_server->block_size - 1) >> header_server->block_size_shift;

	best_block = mem_find_block( header_server, num_blocks );

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

	mem_discard_range( header_server, best_block, num_blocks )
	
	
	// during merging of unused blocks, best_block can only get enlarged but not
	// optimized away because:
	// - the previous block cannot be empty, as in this case we had choosen this 
	//   one as the best block (see mem_find_block)
	// - therefore, only the next block can be empty, but whenever two blocks get
	//   merged, the first of them survives
	if( best_block->num_blocks > num_blocks ) {
		// we do this after looking for a proper gap as we 
		// may have freed a server block during search
		if( header_server->unused_list == NULL ) {
			SHOW_ERROR0( 1, "no free server block to split free range" );
			return B_NO_MEMORY;
		}
		
		free_block = mem_server->unused_list;
		mem_server->unused_list = free_block->next;
		
		free_block->start = best_block->start + num_blocks;
		free_block->len = best_block->num_blocks - num_blocks;
		free_block->client_id_header = -1;
		best_block->num_blocks = num_blocks;

		free_block->prev = best_block->prev;		
		if( free_block->prev )
			free_block->prev->next = free_block;
			
		free_block->next = best_block;
		best_block->prev = free_block;
	}

	block_client = header_client->free_list;
	block_client_id = block_client - header_client->blocks;
	if( block_client_id < 0 || 
		block_client_id >= header_client->num_blocks ||
		block_client != header_client->blocks[block_client_id] )
	{
		SHOW_ERROR0( "Client destroyed freelist of client blocks (freelist=%p)", block_client );
		return B_NOT_ALLOWED;
	}
	
	block_client->prev = MEM_BLOCK_NOT_DISCARDED;
	block_client->age = header_client->header_user->timestamp;
	
	return B_OK;	
}

void mem_server_markfree( mem_server_info *mem_server, int pos, int len )
{
	server_block = client_block->server_block;
	free_block = mem_server->blocks[client_block->start];

	free_block->start = start;
	free_block->len = len;
	
	if( start > 0 ) {
		prev_block = mem_server->blocks[start-1];
		if( prev_block->state = state_free ) {
			prev_block->len += len;
			free_block = prev_block;
		}
	}
	
	for( cur_pos = server_block->start, blocks_left = server_block->len;
		 blocks_left > 0;
		 ++cur_pos, --blocks_left )
	{
		mem_server->blocks[cur_pos] = free_block;
	}
}

void mem_server_unmark_discarded( mem_client_info *mem_client, mem_client_block *client_block )
{
	block_id = cur_block - mem_client->blocks;
	
	if( cur_block->prev == 1 ) {
		mem_client->discarded_list = cur_block->next;
		mem_client->blocks[mem_client->discarded_list].prev = 1;
	} else {
		mem_client->blocks[block->prev].next = block->next;
	}
	
	if( cur_block->next )
		mem_client->blocks[block->next].prev = cur_block->prev;
}
	
status_t mem_server_free( mem_client_info *mem_client, mem_client_block *client_block )
{
	mem_server_info *mem_server = mem_client->server_info;
	
	if( client_block->prev )
		mem_unmark_discarded( mem_client, client_block );

	client_block->next = mem_client->free_list;
	mem_client->free_list = client_block - mem_client->blocks;
}


void mem_client_alloc( mem_client_info *mem_client, int len )
{
	ioctl( 
}

#if 0	
	mem_block *cur, *new_entry;
	
	size = (size + mem->block_size - 1) & ~(mem->block_size - 1);
	
	for( cur = mem->first; cur; cur = cur->next ) {
		if( !cur->inuse && cur->size >= size )
			break;
	}
	
	if( cur == NULL )
		return NULL;
		
	cur->inuse = true;
	
	if( size == cur->size )
		return cur;
		
	new_entry = malloc( sizeof( *new_entry ));
	
	if( new_entry == NULL )
		return NULL;
	
	new_entry->base = cur->base;
	new_entry->size = size;
		
	cur->base += size;
	cur->size -= size;
		
	if( cur->prev )
		cur->prev->next = new_entry;
	else
		mem->first = new_entry;
		
	cur->prev = new_entry;
	new_entry->next = cur;
	
	return new_entry;
}

void mem_free( mem_info *info, mem_block *block )
{
	mem_block *prev, *next;
	
	block->inuse = false;
	
	prev = block->prev;
	
	if( prev && !prev->inuse ) {
		prev->size += block->size;

		if( block->next )
			block->next->prev = prev;

		prev->next = block->next;

		free( block );
		block = prev;
	}

	next = block->next;
		
	if( next && !next->inuse ) {
		next->size += block->size;
		
		if( block->prev ) {
			block->prev->next = next;
		} else
			info->first = next;
		
		next->prev = block->prev;
		
		free( block );
	}
}
#endif