Re: [lc-devel] Chunk list issues

[Nitin G. <nit...@gm...>]

Hi Mauricio,

I am currently implementing compression structure in compress-test module (see 
CompressedCaching/Code). This can then be transfered to ccache git tree.

Also, I've made some changes to chunk_head and chunk structs which further 
compact them by few bytes. I will update Wiki page soon.

I think your code will be useful too. Thanks.

Cheers,
Nitin Gupta


Mauricio Lin wrote:
> 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.
>