Memory allocation issue

kobi_hikri · #1 24-Oct-2005, 05:48

Hey, guys.

How about this idea for memory handling by an OS : I wish that my OS will have a memory allocation table for some tasks. What I did this far is create an envelope function called smalloc that adds any allocation to the memory allocation table.
Next step is to add process ID into account (I will probably use a chained hash table), but I still didn't implement that part so I'm leaving the process ID out for now.

Here is what I did this far as a skeleton.
Any suggestions ?

CPP / C++ / C Code:

#include <stdlib.h>
#include <stdio.h>

//Allocation node.
struct anode
{
	void *pointer;
	struct anode *next;
};

//Allocation table.
struct atable
{
	struct anode *head;
	struct anode *tail;
	unsigned memory_blocks;	
};

void *smalloc(struct atable *allocations,size_t size);
void init_allocation_table(struct atable *allocations);
void add_allocation(struct atable *allocations,void *pointer_to_allocation);	

int main()
{
	int result = 0;
	struct atable my_allocations;
	int i;
	int *dummy;

	init_allocation_table(&my_allocations);
	//Allocate 100 memory blocks.
	for (i = 0;i < 100;i++)
		dummy = smalloc(&my_allocations,i);	
	printf ("%d allocations where made.\n",my_allocations.memory_blocks);

	return (result);
}

void *smalloc(struct atable *allocations,size_t size)
{
	void *result;
	result = malloc(size);
	if (result != NULL)
		//Add allocation to memory allocation table.
		add_allocation(allocations,result);
	return (result);
}

void init_allocation_table(struct atable *allocations)
{
	allocations->head = NULL;
	allocations->tail = NULL;
	allocations->memory_blocks = 0;
}
void  add_allocation(struct atable *allocations,void *pointer_to_allocation)
{
	struct anode *new_allocation;
	
	//Create the new allocation node.
	new_allocation = malloc(sizeof(struct anode));
	(*new_allocation).pointer = pointer_to_allocation;
	(*new_allocation).next = NULL;
	if (allocations->head == NULL)
	{
		allocations->head = new_allocation;
		allocations->tail = new_allocation;
	}
	else
	{
		new_allocation->next = allocations->head;
		allocations->head = new_allocation;
	}
	allocations->memory_blocks += 1;
}

Thanks in advance for any critique or insight,
Kobi.

Paramesh · #2 26-Oct-2005, 02:07

Hi Kobi,

Just my thought:
We can use typedef to avoid writing struct anode ...
I think there is no // comment in C language. We should use
/*comment*/ instead.

Cheers,
Paramesh.

kobi_hikri · #3 26-Oct-2005, 05:30

Quote:

Originally Posted by Paramesh

We can use [b]typedef[b] to avoid writing struct anode ...

I think you are right. The reason I didn't write it down as [b]typedef[b] is that I plan on having all the types that my OS uses in header files.
But you are correct, I probably should have mentioned it, or post the specific typedef's. Soon I will post it, after I decide exactly how things should happen (some types will be builded upon other types).

Quote:

Originally Posted by Paramesh

I think there is no // comment in C language. We should use
/*comment*/ instead.

You are correct

I didn't know that till this very second

I took it as an obvious but now I checked the K&R Reference (Page 192, section A2.2) and the ansi-c language works with /* and */ .

Thanks ,Paramesh.
Kobi.

davekw7x · #4 26-Oct-2005, 08:44

Quote:

Originally Posted by kobi_hikri

Hey, guys.

How about this idea for memory handling by an OS : I wish that my OS will have a memory allocation table for some tasks. What I did this far is create an envelope function called smalloc that adds any allocation to the memory allocation table.

I'm not sure how you are going to use this. Garbage collection or what?

My observation is that if you are going to allocate blocks of memory with the idea of freeing them up at some time in the future, then I think that the anode struct should have a size member in addition to the memory address pointer.

Regards,

Dave

kobi_hikri · #5 26-Oct-2005, 10:54

Quote:

Originally Posted by davekw7x

I'm not sure how you are going to use this. Garbage collection or what?

My observation is that if you are going to allocate blocks of memory with the idea of freeing them up at some time in the future, then I think that the anode struct should have a size member in addition to the memory address pointer.

True.
I added a memory_blocks counter and the intention was to have knowledge of memory blocks allocated.
Of course you are correct, and this information will be stored for each allocation (as well as process ID I'll add).

The main idea is to "control and monitor" memory allocation. A garbage collection is one usage I had in mind (When a process is terminated, I scan the hash table and free any unfreed memory allocated by this process).

Here it is, till now (Paramesh, I still didn't insert the typedef part - But I will soon).

CPP / C++ / C Code:

#include <stdlib.h>
#include <stdio.h>

//Allocation node.
struct anode
{
	void			*pointer;
	size_t			allocation_size;
	struct anode	*next;
};

//Allocation table.
struct atable
{
	struct anode	*head;
	struct anode	*tail;
	unsigned		memory_blocks;	
};

void *smalloc(struct atable *allocations,size_t size);
void init_allocation_table(struct atable *allocations);
void add_allocation(struct atable *allocations,void *pointer_to_allocation,size_t size);	

int main()
{
	int result = 0;
	struct atable my_allocations;
	int i;
	int *dummy;

	init_allocation_table(&my_allocations);
	//Allocate 100 memory blocks.
	for (i = 0;i < 100;i++)
		dummy = smalloc(&my_allocations,i);	
	printf ("%d bytes where allocated.\n",my_allocations.memory_blocks);

	return (result);
}

void *smalloc(struct atable *allocations,size_t size)
{
	void *result;
	result = malloc(size);
	if (result != NULL)
		//Add allocation to memory allocation table.
		add_allocation(allocations,result,size);
	return (result);
}

void init_allocation_table(struct atable *allocations)
{
	allocations->head = NULL;
	allocations->tail = NULL;
	allocations->memory_blocks = 0;
}
void  add_allocation(struct atable *allocations,void *pointer_to_allocation,size_t size)
{
	struct anode *new_allocation;
	
	//Create the new allocation node.
	new_allocation = malloc(sizeof(struct anode));
	(*new_allocation).pointer = pointer_to_allocation;
	(*new_allocation).allocation_size = size;
	(*new_allocation).next = NULL;
	if (allocations->head == NULL)
	{
		allocations->head = new_allocation;
		allocations->tail = new_allocation;
	}
	else
	{
		new_allocation->next = allocations->head;
		allocations->head = new_allocation;
	}
	allocations->memory_blocks += size;
}

Thanks, Dave.
Kobi.

kobi_hikri · #6 26-Oct-2005, 11:21

Here is the code untill now, still without the hash table (the memory allocation table is a "plain" linked list).

CPP / C++ / C Code:

#include <stdlib.h>
#include <stdio.h>

//Allocation node.
typedef struct anode
{
	void *pointer;
	size_t allocation_size;
	unsigned pid;
	struct anode *next;
} allocation_node;

//Allocation table.
typedef struct atable
{
	allocation_node	*head;
	allocation_node	*tail;
	unsigned memory_blocks;	
} allocation_table;

void *smalloc(allocation_table *allocations,size_t size,unsigned requsting_pid);
void init_allocation_table(allocation_table *allocations);
void add_allocation(allocation_table *allocations,void *pointer_to_allocation,size_t size,unsigned requsting_pid);	

int main()
{
	int result = 0;
	allocation_table my_allocations;
	int i;
	int *dummy;

	init_allocation_table(&my_allocations);
	//Allocate 100 memory blocks.
	for (i = 0;i < 100;i++)
		dummy = smalloc(&my_allocations,i,i);	
	printf ("%d bytes where allocated.\n",my_allocations.memory_blocks);

	return (result);
}

void *smalloc(allocation_table *allocations,size_t size,unsigned requsting_pid)
{
	void *result;
	result = malloc(size);
	if (result != NULL)
		//Add allocation to memory allocation table.
		add_allocation(allocations,result,size,requsting_pid);
	return (result);
}

void init_allocation_table(allocation_table *allocations)
{
	allocations->head = NULL;
	allocations->tail = NULL;
	allocations->memory_blocks = 0;
}
void  add_allocation(allocation_table *allocations,void *pointer_to_allocation,size_t size,unsigned requsting_pid)
{
	allocation_node *new_allocation;
	
	//Create the new allocation node.
	new_allocation = malloc(sizeof(allocation_node));
	(*new_allocation).pointer = pointer_to_allocation;
	(*new_allocation).allocation_size = size;
	(*new_allocation).pid = requsting_pid;
	(*new_allocation).next = NULL;
	if (allocations->head == NULL)
	{
		allocations->head = new_allocation;
		allocations->tail = new_allocation;
	}
	else
	{
		new_allocation->next = allocations->head;
		allocations->head = new_allocation;
	}
	allocations->memory_blocks += size;
}

As always, critique and suggestions are welcome.
Kobi.

kobi_hikri · #7 27-Oct-2005, 12:16

This is what I've done this last hour :

mem.h

CPP / C++ / C Code:

#define TABLE_SIZE	131

/*Allocation node.*/
typedef struct anode
{
	void *pointer;
	size_t allocation_size;
	unsigned pid;
	struct anode *next;
} allocation_node;

/*Allocation table.*/
typedef struct atable
{
	allocation_node	*table[TABLE_SIZE];
	unsigned memory_blocks;	
} allocation_table;

void *smalloc(allocation_table *allocations,size_t size,unsigned requsting_pid);
void init_allocation_table(allocation_table *allocations);
unsigned hash(unsigned value);
void add_allocation(allocation_table *allocations,void *pointer_to_allocation,size_t size,unsigned requsting_pid);
void print_allocation_table(allocation_table *allocations);

smalloc.c

CPP / C++ / C Code:

#include <stdlib.h>
#include <stdio.h>
#include "mem.h"

int main()
{
	unsigned result = 0;
	allocation_table my_allocations;
	unsigned i;
	int *dummy;

	init_allocation_table(&my_allocations);
	/*Allocate 100 memory blocks.*/
	for (i = 0;i < 100;i++)
		dummy = smalloc(&my_allocations,i,i);
	print_allocation_table(&my_allocations);
	printf ("%d bytes where allocated.\n",my_allocations.memory_blocks);

	return (result);
}

void *smalloc(allocation_table *allocations,size_t size,unsigned requsting_pid)
{
	void *result;
	result = malloc(size);
	if (result != NULL)
		/*Add allocation to memory allocation table.*/
		add_allocation(allocations,result,size,requsting_pid);
	return (result);
}

void init_allocation_table(allocation_table *allocations)
{
	unsigned i;
	for (i = 0;i < TABLE_SIZE;i++)
		(*allocations).table[i] = NULL;
	(*allocations).memory_blocks = 0;
}
void  add_allocation(allocation_table *allocations,void *pointer_to_allocation,size_t size,unsigned requsting_pid)
{
	allocation_node *new_allocation;
	unsigned bucket;
	/*Create the new allocation node.*/
	new_allocation = malloc(sizeof(allocation_node));
	(*new_allocation).pointer = pointer_to_allocation;
	(*new_allocation).allocation_size = size;
	(*new_allocation).pid = requsting_pid;
	(*new_allocation).next = NULL;
	/*Find the correct bucket in the hash table*/
	bucket = hash(requsting_pid) % TABLE_SIZE;
	if (allocations->table[bucket] == NULL)
	{
		allocations->table[bucket] = new_allocation;
	}
	else
	{
		new_allocation->next = allocations->table[bucket];
		allocations->table[bucket] = new_allocation;
	}
	allocations->memory_blocks += size;
}

/*Robert Jenkins' 32 bit Mix Function*/
unsigned hash(unsigned value)
{
  value += (value << 12);
  value ^= (value >> 22);
  value += (value << 4);
  value ^= (value >> 9);
  value += (value << 10);
  value ^= (value >> 2);
  value += (value << 7);
  value ^= (value >> 12);
  return (value);
}

void print_allocation_table(allocation_table *allocations)
{
	unsigned i;
	allocation_node *iterator;
	for (i = 0;i < TABLE_SIZE;i++)
	{
		printf("Bucket #%d -> ",i);
		iterator = allocations->table[i];
		while (iterator != NULL)
		{
			printf("(%d,%d)\t",iterator->pid,iterator->allocation_size);
			iterator = iterator->next;
		}
		printf("\n");
	}
}

Soon to come : remove_allocation, sum_allocations (by given pid).

Kobi.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Pointer Usage in C++: Beginner to Advanced	varunhome	C++ Forum	0	19-Aug-2005 09:25
Computer resets - weird memory slot issue	SpikeyUK	Computer Hardware Forum	7	22-Jul-2005 18:15
[Tutorial] Pointers in C (Part I)	Stack Overflow	C Programming Language	1	08-Apr-2005 18:35
3D array dynamic memory allocation	cjwatchdog	C Programming Language	3	20-Feb-2004 15:27

Memory allocation issue

Re: Memory allocation issue

Re: Memory allocation issue

Re: Memory allocation issue

Re: Memory allocation issue

Re: Memory allocation issue

Re: Memory allocation issue