Re: [lc-devel] Chunk list issues

[Mauricio L. <mau...@gm...>]

Hi Gupta,

In order to make the development of chunk list operations easier to
debug, I have created a module that helps gradually to put more chunk
list operation an test it.

add_page_to_chunk_list() function is created to call the
compress_function() to compress a page and add the related chunk in a
chunk list (related and master chunk list). The remaining space of the
page after the compression is inserted in the free chunk list.
Currently add_page_to_chunk_list() allows just one chunk points to one
page, i.e. one chunk for one page. The next idea is to improve the
add_page_to_chunk_list() in order to allow many chunks (related chunk)
points to a page that stores many compressed pages.

The current /proc/chunk_list entry accepts a number as input:

# echo 2 > /proc/chunk_list

This number is the number of times that new pages will be allocated,
compressed and added in the chunk lists using the
add_page_to_chunk_list().

It shows as output something like:

# cat /proc/chunk_list

Master chunk list: 3278794752 (792) 3278795544 (3304) 3250196480 (788)
3250197268 (3308) 3250565120 (792) 3250565912 (3304) 3250429952 (788)
3250430740 (3308)
 Related Chunk list: 3278794752 (792) 3250565120 (792)
 Related Chunk list: 3250196480 (788) 3250429952 (788)
 Free list: 3278795544 (3304) 3250197268 (3308) 3250565912 (3304)
3250430740 (3308)

The large number is the chunk->start_addr value and the short number
inside the brackets is the chunk->size value. It prints the element of
each chunk list as "chunk->start_addr (chunk->size)".

The current module is presented as follows.

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/proc_fs.h>
#include <linux/sched.h>
#include <asm/uaccess.h>

#include <linux/ccache.h>

#define MODULE_NAME "chunk_list"

static struct proc_dir_entry *chunk_list_file;

struct chunk init_chunk = {
	.start_addr = NULL,
	.size = 0,
	.next = NULL,
	.chunks = LIST_HEAD_INIT(init_chunk.chunks)
};


// Some related chunk lists
struct chunk_head *chk_head_a = NULL;

struct chunk_head *chk_head_b = NULL;

struct chunk_head *chk_head_free = NULL;

// Some macros for chunk list operation
#define next_chunk(chk)	list_entry((chk)->chunks.next, struct chunk, chunks)

#define prev_chunk(chk)	list_entry((chk)->chunks.prev, struct chunk, chunks)

#define for_each_chunk(chk) \
	for (chk = &init_chunk ; (chk = next_chunk(chk)) != &init_chunk ; )

#define for_each_related_chunk(chk, chk_head) \
	for (chk = chk_head->chunk_list; chk != NULL; chk = chk->next)

/*
 * Add a chunk in the master chunk list
 */
static inline void add_chunk_to_list(struct chunk *chk)
{
	list_add_tail(&chk->chunks, &init_chunk.chunks);
}

/*
 * Delete a chunk from the master chunk list
 */
static inline void del_chunk_from_list(struct chunk *chk)
{
	list_del(&chk->chunks);
}

/*
 * Add a chunk in the related chunk list
 */
static inline void add_related_chunk_to_list(struct chunk_head *chk_head,
					     struct chunk *new_chk)
{
	struct chunk *chk = NULL;

	if (chk_head->chunk_list) {
		chk = chk_head->chunk_list;
		while (chk->next)
			chk = chk->next;
		chk->next = new_chk;
	}
	else
		chk_head->chunk_list=new_chk;

	new_chk->next = NULL;

	// Add to master chunk list as well
	add_chunk_to_list(new_chk);		
}

/*
 * Delete all related chunks from the list
 */
static inline void del_all_related_chunks_from_list(struct chunk_head *chk_head)
{
	struct chunk *chk = NULL;

	while (chk_head->chunk_list) {
		chk = chk_head->chunk_list;
		chk_head->chunk_list = chk->next;

		// Delete from master chunk list
		del_chunk_from_list(chk);

		// Free the chunk
		kfree(chk);
	}
}

/*
 * Add a chunk in the free chunk list
 */
static inline void add_chunk_to_free_list(void *start_addr,
					  unsigned short size)
{
	struct chunk *chk = NULL;
	chk = (struct chunk *)kmalloc(sizeof(struct chunk),
				      GFP_KERNEL);
	chk->start_addr = start_addr + size;
	chk->size = PAGE_SIZE - size;
	add_related_chunk_to_list(chk_head_free, chk);
}

/*
 * Add a page in the chunk list (NOT FINISHED YET)
 */
static inline void add_page_to_chunk_list(struct chunk_head *chk_head,
					  struct page *page)
{
	struct page *comp_page = NULL;
	struct chunk *chk = NULL;

	// compress the page
	comp_page = compress_function(page);

	if (comp_page) {
		// create the chunk
		chk = (struct chunk *)kmalloc(sizeof(struct chunk),
					      GFP_KERNEL);
		chk->start_addr = page_address(comp_page);
		chk->size = comp_page->comp_size;

		// add to list
		add_related_chunk_to_list(chk_head, chk);
		
		// add the remaining space in the free chunk list
		if (chk->size < PAGE_SIZE)
			add_chunk_to_free_list(chk->start_addr, chk->size);

	}
}


static int read_chunk_list(char *page, char **start,
			   off_t off, int count,
			   int *eof, void *data)
{
	int len = 0;
	struct chunk *chk;
	char *output;
	char *item;

	output = kmalloc(100, GFP_KERNEL);
	item = kmalloc(6, GFP_KERNEL);
	strcpy(output, "Master chunk list: ");
	if (!list_empty(&init_chunk.chunks)) {
		
		for_each_chunk(chk) {
			sprintf(item, "%lu (%d) ", (unsigned long)(chk->start_addr), chk->size);
			strcat(output, item);
		}

		strcat(output, "\n Related Chunk list: ");		
		for_each_related_chunk(chk, chk_head_a) {
			sprintf(item, "%lu (%d) ", (unsigned long)(chk->start_addr), chk->size);
			strcat(output, item);
		}
		
		strcat(output, "\n Related Chunk list: ");
		for_each_related_chunk(chk, chk_head_b) {
			sprintf(item, "%lu (%d) ", (unsigned long)(chk->start_addr), chk->size);
			strcat(output, item);
		}

		strcat(output, "\n Free list: ");
		for_each_related_chunk(chk, chk_head_free) {
			sprintf(item, "%lu (%d) ", (unsigned long)(chk->start_addr), chk->size);
			strcat(output, item);
		}
		strcat(output, "\n");
		len = sprintf(page, output);
		kfree(output);
		kfree(item);
	}
	else {
		len = sprintf(page, "\n");
	}
	
	return len;
}

static int write_chunk_list(struct file *file,
			    const char *buffer,
			    unsigned long count,
			    void *data)
{
	char *input;
	int i;
	struct page *page;
	unsigned int nr;
	
	input = kmalloc(count, GFP_KERNEL);

	if (!input)
		return -ENOMEM;
	if(copy_from_user(input, buffer, count)) {
		kfree(input);
		return -EFAULT;
	}

	nr = simple_strtoul(input, NULL, 10);

	//del_all_related_chunks_from_list(chk_head_a);

	for (i=0; i<nr; i++) {
		page = alloc_page(GFP_KERNEL);
		memset(page_address(page), 1, PAGE_SIZE/2);
		memset(page_address(page) + PAGE_SIZE/2, 4, PAGE_SIZE/2);
		add_page_to_chunk_list(chk_head_a, page);
		
		page = alloc_page(GFP_KERNEL);
		memset(page_address(page), 1, PAGE_SIZE);
		add_page_to_chunk_list(chk_head_b, page);
	}

	kfree(input);
	return count;
}

static int __init init_chunk_list(void)
{
	int flag = 0;
	chunk_list_file = create_proc_entry("chunk_list", S_IRUGO | S_IWUSR, NULL);
	chunk_list_file->read_proc = read_chunk_list;
	chunk_list_file->write_proc = write_chunk_list;
	chunk_list_file->owner = THIS_MODULE;

	chk_head_a = (struct chunk_head *)kmalloc(sizeof(struct chunk_head),
						GFP_KERNEL);
	chk_head_a->chunk_list = NULL;
	
	chk_head_b = (struct chunk_head *)kmalloc(sizeof(struct chunk_head),
						GFP_KERNEL);
	chk_head_b->chunk_list = NULL;

	chk_head_free = (struct chunk_head *)kmalloc(sizeof(struct chunk_head),
						     GFP_KERNEL);
	chk_head_free->chunk_list = NULL;

	printk(KERN_DEBUG "%s included\n", MODULE_NAME);
	return flag;
}

static void __exit cleanup_chunk_list(void)
{	
	del_all_related_chunks_from_list(chk_head_a);
	del_all_related_chunks_from_list(chk_head_b);
	del_all_related_chunks_from_list(chk_head_free);
	kfree(chk_head_a);
	kfree(chk_head_b);
	kfree(chk_head_free);
    	remove_proc_entry("chunk_list", NULL);
	printk(KERN_DEBUG "%s removed\n", MODULE_NAME);
}

module_init(init_chunk_list);
module_exit(cleanup_chunk_list);
MODULE_LICENSE("GPL");

BR,

Mauricio Lin.