linuxcompressed-devel — Linux Compressed Cache Development Mailing List

Re: [lc-devel] Chunk list issues

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

Hi Anderson,

> 
>> On 6/28/06, Anderson Briglia <bri...@gm...> wrote:
>> > > > I have a doubt related to chunk operations:
>> > > >
>> > > > - I guess you will use the virtual swap as the compressed cache for
>> > > > anon pages, right? If yes, how will you swapin/swapout chunks? If a
>> > > > single chunk points to a portion of a physical page, and the
>> > > > swapin/swapout operations handle entire pages of data.
>> > >
>> > > Yes, vswap is for anon pages. I think you are mistaken 
>> somewhere...I'm not using
>> > > bio structs or anything to swapin/out pages from vswap.
>> >
>> > Ok. Will be possible to transfer pages from vswap to a 'real' swap 
>> area?
>> >
>>
>> Yes, but 'procedure' will be same as for transferring a page from a
>> swap to any other swap: change it swp_entry_t to have 'type' for other
>> swap and it will get written to this second swap.
> 
> What will be the factor that determines when/which page will be
> migrated from vswap to real swap?
>

vswap is full. Maybe others but I haven't thought of them yet :P

> How the chk->count is increased or decreased? Is this count related to
> page->_count?
> 

chk->_count has same purpose as page->_count. When you use a chunk you take a 
count. When you no longer want it you decrement the count. When it goes 0, free it.


I hope to post an implementation of compression structure (as on wiki) by 
Sunday. Its as a separate module (storage-test). After a bit of testing I will 
merge it with main ccaching code.
This will also allow working on structure separately from rest of ccaching 
details :)

Cheers,
Nitin Gupta

Re: [lc-devel] Chunk list issues

[Anderson B. <bri...@gm...>]

Hi Nitin,

> On 6/28/06, Anderson Briglia <bri...@gm...> wrote:
> > > > I have a doubt related to chunk operations:
> > > >
> > > > - I guess you will use the virtual swap as the compressed cache for
> > > > anon pages, right? If yes, how will you swapin/swapout chunks? If a
> > > > single chunk points to a portion of a physical page, and the
> > > > swapin/swapout operations handle entire pages of data.
> > >
> > > Yes, vswap is for anon pages. I think you are mistaken somewhere...I'm not using
> > > bio structs or anything to swapin/out pages from vswap.
> >
> > Ok. Will be possible to transfer pages from vswap to a 'real' swap area?
> >
>
> Yes, but 'procedure' will be same as for transferring a page from a
> swap to any other swap: change it swp_entry_t to have 'type' for other
> swap and it will get written to this second swap.

What will be the factor that determines when/which page will be
migrated from vswap to real swap?

How the chk->count is increased or decreased? Is this count related to
page->_count?

Cheers,

Anderson Briglia

Re: [lc-devel] Chunk list issues

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

Hi Anderson,

On 6/28/06, Anderson Briglia <bri...@gm...> wrote:
> > > I have a doubt related to chunk operations:
> > >
> > > - I guess you will use the virtual swap as the compressed cache for
> > > anon pages, right? If yes, how will you swapin/swapout chunks? If a
> > > single chunk points to a portion of a physical page, and the
> > > swapin/swapout operations handle entire pages of data.
> >
> > Yes, vswap is for anon pages. I think you are mistaken somewhere...I'm not using
> > bio structs or anything to swapin/out pages from vswap.
>
> Ok. Will be possible to transfer pages from vswap to a 'real' swap area?
>

Yes, but 'procedure' will be same as for transferring a page from a
swap to any other swap: change it swp_entry_t to have 'type' for other
swap and it will get written to this second swap.

Or, if you want to know if we can fall back to real swap if vswap is
full, then also yes, it is already being done (please see git tree).

> > So, for swap out: Get enough free chunks from free list and store compressed
> > page in them.
>
> And the free chunks will point to pages inserted into the vswap memory
> area? So, all chunks are allocated using the vswap area?

Pages will be compressed, spread out in chunks, a chunk_head will
point to first of these chunks. This chunk_head ptr is stored in radix
node corres. to page being compressed.
There is no such thing as 'vswap area' or maybe I didn't understand your ques :)

Cheers,
Nitin Gupta

Re: [lc-devel] Chunk list issues

[Anderson B. <bri...@gm...>]

Hi Gupta,

> > I have a doubt related to chunk operations:
> >
> > - I guess you will use the virtual swap as the compressed cache for
> > anon pages, right? If yes, how will you swapin/swapout chunks? If a
> > single chunk points to a portion of a physical page, and the
> > swapin/swapout operations handle entire pages of data.
>
> Yes, vswap is for anon pages. I think you are mistaken somewhere...I'm not using
> bio structs or anything to swapin/out pages from vswap.

Ok. Will be possible to transfer pages from vswap to a 'real' swap area?

> So, for swap out: Get enough free chunks from free list and store compressed
> page in them.

And the free chunks will point to pages inserted into the vswap memory
area? So, all chunks are allocated using the vswap area?

> And, for swap in: chunk_head->chunk_list gives to first chunk and chunks are
> linked. So, you can get data from all these chunks, (maybe) collect them in a
> page, decompress it and return to caller.
>
> I have started implementation for this compression structure and post when its
> ready. This should also reveal possible problems which I don't see now.

Cheers,

Anderson Briglia

Re: [lc-devel] Chunk list issues

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

Hi Anderson,

Anderson Briglia wrote:
> Hi Gupta and others,
> 
> I have a doubt related to chunk operations:
> 
> - I guess you will use the virtual swap as the compressed cache for
> anon pages, right? If yes, how will you swapin/swapout chunks? If a
> single chunk points to a portion of a physical page, and the
> swapin/swapout operations handle entire pages of data.

Yes, vswap is for anon pages. I think you are mistaken somewhere...I'm not using 
bio structs or anything to swapin/out pages from vswap.
So, for swap out: Get enough free chunks from free list and store compressed 
page in them.
And, for swap in: chunk_head->chunk_list gives to first chunk and chunks are 
linked. So, you can get data from all these chunks, (maybe) collect them in a 
page, decompress it and return to caller.

I have started implementation for this compression structure and post when its 
ready. This should also reveal possible problems which I don't see now.

Cheers,
Nitin


> 
> On 6/27/06, Nitin Gupta <nit...@gm...> wrote:
>> 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.
>>>
...

Re: [lc-devel] Chunk list issues

[Anderson B. <bri...@gm...>]

Hi Gupta and others,

I have a doubt related to chunk operations:

- I guess you will use the virtual swap as the compressed cache for
anon pages, right? If yes, how will you swapin/swapout chunks? If a
single chunk points to a portion of a physical page, and the
swapin/swapout operations handle entire pages of data.

Best regards,

Anderson Briglia

On 6/27/06, Nitin Gupta <nit...@gm...> wrote:
> 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.
> >
>
>
> Using Tomcat but need to do more? Need to support web services, security?
> Get stuff done quickly with pre-integrated technology to make your job easier
> Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
> http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
> _______________________________________________
> linuxcompressed-devel mailing list
> lin...@li...
> https://lists.sourceforge.net/lists/listinfo/linuxcompressed-devel
>

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.
> 

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.

Re: [lc-devel] vswap patch

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

Hi Allan,

On 6/24/06, Allan Bezerra <all...@gm...> wrote:
>
> > I didn't let print anything for vswap when reading /proc/swaps (please
> see: swap_show() in swapfile.c).
>
> Cool! Now, I understanding that. However, I think that show only summary
> line isn't good. Therefore, we can change the summary print order seq_puts(swap,
> "Filename\t\t\t\tType\t\tSize\tUsed\tPriority\n") to after SWP_COMPRESSED
> check. See the patch attached.
>
> Please, feel free to accept this suggestion.
>

diff --git a/mm/swapfile.c b/mm/swapfile.c
> index 2c439eb..a43bb9f 100644
> --- a/mm/swapfile.c
> +++ b/mm/swapfile.c
> @@ -1269,14 +1269,14 @@ static int swap_show(struct seq_file *sw
>         struct file *file;
>         int len;
>
> -       if (v == swap_info)
> -               seq_puts(swap,
> "Filename\t\t\t\tType\t\tSize\tUsed\tPriority\n");
> -
>         if (ptr->flags & SWP_COMPRESSED) {
>                 pr_info("vswap to be printed\n");
>                 return 0;
>         }
>
> +       if (v == swap_info)
> +               seq_puts(swap,
> "Filename\t\t\t\tType\t\tSize\tUsed\tPriority\n");
> +
>         file = ptr->swap_file;
>         len = seq_path(swap, file->f_vfsmnt, file->f_dentry, " \t\n\\");
>         seq_printf(swap, "%*s%s\t%u\t%u\t%d\n",
>


This patch has a problem. It will not print heading if vswap is enabled
before any other swap. So, patch will be:

diff --git a/mm/swapfile.c b/mm/swapfile.c
index a5461ef..a1d4af6 100644
--- a/mm/swapfile.c
+++ b/mm/swapfile.c
@@ -1329,13 +1329,15 @@ static int swap_show(struct seq_file *sw
        struct file *file;
        int len;

+       if (ptr->flags & SWP_COMPRESSED) {
+               pr_info("swap_show: vswap to be printed\n");
+               if (ptr->next == -1) return 0;
+       }
+
        if (v == swap_info)
                seq_puts(swap,
"Filename\t\t\t\tType\t\tSize\tUsed\tPriority\n");

-       if (ptr->flags & SWP_COMPRESSED) {
-               pr_info("vswap to be printed\n");
-               return 0;
-       }
+       if (ptr->flags & SWP_COMPRESSED) return 0;

        file = ptr->swap_file;
        len = seq_path(swap, file->f_vfsmnt, file->f_dentry, " \t\n\\");


Outputs:

problem with your patch:
[root@localhost ~]# cat /proc/swaps
[root@localhost ~]# echo "10" > /proc/sys/vm/max_anon_cc_size
[root@localhost ~]# cat /proc/swaps
[root@localhost ~]# swapon /dev/sda2
[root@localhost ~]# cat /proc/swaps  *** no heading ***
/dev/sda2                               partition       530136  0       -1
[root@localhost ~]#

with second patch:

[root@localhost ~]# cat /proc/swaps
[root@localhost ~]# echo "10" > /proc/sys/vm/max_anon_cc_size
[root@localhost ~]# cat /proc/swaps
[root@localhost ~]# swapon /dev/sda2
[root@localhost ~]# cat /proc/swaps ** heading back **
Filename                                Type            Size    Used
Priority/dev/sda2                               partition       530136
0       -1
[root@localhost ~]#

and it does't print anything when there's only vswap enabled (as expected).
I will soon push this in master branch...

Thanks for making me aware of this problem :)

Cheers,
Nitin Gupta

[lc-devel] Moving over

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

Hi All,

I have just moved project repository to dev.laptop.org (home to OLPC project) 
and a new mailing list: lin...@la...

Git is now used for version control. This will help keeping up with mainstream 
kernel development much easier. The servers here are fast too :)

You can subscribe to this ML at:
http://mailman.laptop.org/mailman/listinfo/linux-mm-cc

When getting code for first time do:
git clone git://dev.laptop.org/projects/linux-mm-cc linux-mm-cc

Then updates can be received using:
git pull

You can browse code online at:
http://dev.laptop.org/git.do
(project is named: linux-mm-cc)

[All development upto now has been committed to git tree]

There is no project page at laptop.org yet, nor is -commits list but should be 
up soon.

-----------------------------------------------------------------------------

SF CVS will not be frequently updated. Only when something visible is done, CVS 
will be synced.

If you are feeling nostalgic for dear ol' lc-devel...it's still there :)


Cheers,
Nitin Gupta

Re: [lc-devel] CCache work status

[Marcelo T. <ma...@kv...>]

On Wed, Jun 21, 2006 at 07:45:31PM -0400, Rik van Riel wrote:
> On Wed, 21 Jun 2006, Nitin Gupta wrote:
> 
> > This patch makes this vswap and system can swap out to this with no problem.
> > Also started work on to replace the page that comes to vswap with chunk_head
> > and restore them when they are looked up in page/swap cache lookup functions
> > (find_get_page() and friends). I hope to post this much in next few days.
> 
> Your patch looks like a good start.  I'll save the
> obvious code cleanup patches for later, when it's
> time to get stuff merged :)

Looks good indeed - Nitin, I guess the harder part of this is getting
the compression cost estimation / code actually working ?

Need to get the uncompression code working in do_swap_page()... 

Re: [lc-devel] Compressed caching

[John M. <joh...@gm...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Nitin Gupta wrote:
> 
> John Moser wrote:
>>> Just a quick note: We can't have floating point in kernel. So, I doubt
>>> how will we have monte-carlo algorithm ported to kernel?
>>>
>>
>> Nods.  I don't know if it can be rewritten in fixed point; however, it
>> is notable that mcarlo is probably not as useful as counting null bytes.
>>  Wilson-Kaplan algorithms treat 0 as a special case; think about
>> anonymous memory:

[......]

> /* --------------- Frame This One
> ---------------------------------------- */
>> At any rate, just running through with a NULL byte counter is probably
>> enough to decide whether to use WK or LZ.
>>
> /* ------- Simple, Fast and Reliable
> ------------------------------------- */
> 
> Great suggestion John Moser :-)
> 
> And..I think, this NULL byte count can be really optimized to a level
> that time to perform this _each_ time when compressing pages should be
> far compensated by time and space we'll save by having a good hit at
> selecting right compression algorithm.
> 

Optimizing, you can probably have it escape out when it hits a certain
number of NULLs; but you still want to avoid running it every time.
Mostly a page of memory is going to stay what it is; the stack, for
example, will always have loads of padding in it except for the case of
large on-stack buffers full of text and such (typically such buffers are
short and negligible; large ones would mean more than say half a page?).

At the very least, there's a lot of memory that won't change, and we can
avoid re-working this when we see that stuff come back.  This is
especially true of mmap()'d segments of executables and libraries,
although those aren't normally swapped anyway (they get invalidated and
cleared from memory, re-read from disk later; in the future compressed
caching could compress that stuff and just invalidate/free it when
memory pressure is high rather than sending it to swap).  There's other
data that behaves this way, though; for example, most of the control
information for GUIs like GTK won't change once the window is initially
built and drawn..

> 
> 
> Cheers,
> Nitin Gupta
> 
> 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQIVAwUBRJnc5gs1xW0HCTEFAQJ5mRAAgfK7ZJFGudGjZpW9yqtXeCUGMCg8E2ss
8KLEl+bT+Jzja8+Qh+DYk1N6mMx4G7l0w/wR+M4JdnDEC2v/EzGMsbQ2IGWsEEl0
7eKpCUqvJUNiwaiNhsdoUy2BrC/6H3EXt4EEoqJtkFGAY1XTqT3kzHzopFlcFDPC
XOQaLMvnDGIIVLarH+CY6SfWvBv6OcEYTLYFg43FWhZyOhmZboQGAy6CAp9XYELq
0MsmSeM1FA4cHQOAqd68HCY23ZubS1sy/IrnfFaxp3z5M/YQr797sMLceyPjM2Ao
E/ZI3eVbtG+Qm+ZKqjpjGB+d/4MlD5brr/MlEpQqVXmGNkNTCMiwLW29r3/6or28
BIwkZ08kLOU/plqa5jum9nvb7IfQVK9ITUTRC39J9+xETCRAIV5mgR7PSCaIo7jm
bbA2L6dizHZIfr7uwYIQB8dCT2+qKZipOCPHyeDtVfacJ1xPwch3hImjh0Jdg6KK
lePMN52MLVlRp6fL7n3eEkMYXb9q2r3BzJ1jT+XBtF4xgfZXFxWpPEvUlhuFcZtD
bxSS/cslgyHDajxMl4N9jffTd6wYKBMwsFKllNQO6YVSSS6T7KGpPRdwIAOj9Wq4
6/3HFmDQRsDjgsnwkFZx1toViSTTsqk518uJPgqFnT2x+6stC8hk8T0GvMCCAmQi
kXZK9r5RaYQ=
=l3kb
-----END PGP SIGNATURE-----

Re: [lc-devel] CCache work status

[Rik v. R. <ri...@re...>]

On Wed, 21 Jun 2006, Nitin Gupta wrote:

> This patch makes this vswap and system can swap out to this with no problem.
> Also started work on to replace the page that comes to vswap with chunk_head
> and restore them when they are looked up in page/swap cache lookup functions
> (find_get_page() and friends). I hope to post this much in next few days.

Your patch looks like a good start.  I'll save the
obvious code cleanup patches for later, when it's
time to get stuff merged :)

-- 
All Rights Reversed

Re: [lc-devel] Compressed caching

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

John Moser wrote:
>> Just a quick note: We can't have floating point in kernel. So, I doubt
>> how will we have monte-carlo algorithm ported to kernel?
>>
> 
> Nods.  I don't know if it can be rewritten in fixed point; however, it
> is notable that mcarlo is probably not as useful as counting null bytes.
>  Wilson-Kaplan algorithms treat 0 as a special case; think about
> anonymous memory:
> 
> ADDR	DATA
> 0	char a
> 	\0 (pad)
> 	\0 (pad)
> 4	int i
> 	int i
> 	int i
> 	int i
> 8	short j
> 	short j
> 	\0 (pad)
> 	\0 (pad)
> 12	char b
> 	\0 (pad)
> 	\0 (pad)
> 	\0 (pad)
> 16	....
> 
> Data values will often be aligned to 4 bytes; stack frames tend to be
> aligned to 16 bytes I guess (STACK_ROUND() rounds to 16 bytes).
> Executable memory is even worse; loops and small functions and other
> code blocks tend to be aligned to page boundaries, so you have things
> that look like:
> 
> 
> ...;
> ...;
> jmp @a;
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> @a:  /* Aligned to 4096 byte page boundary */
> ...;
> loop;
> ...;
> ret;  /*return*/
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0
> function foo() { /* Function aligned to a page boundary */
> ........
> 
> And so on.  You get small clumps of zeros here and there that don't
> really compress any better than small clumps of A's or 7's or such; but
> WKdm and WK4x4 expect these so they have a special way to compress them
> with lots more efficiency than LZO.
> 

/* --------------- Frame This One ---------------------------------------- */
> At any rate, just running through with a NULL byte counter is probably
> enough to decide whether to use WK or LZ.
> 
/* ------- Simple, Fast and Reliable ------------------------------------- */

Great suggestion John Moser :-)

And..I think, this NULL byte count can be really optimized to a level that time 
to perform this _each_ time when compressing pages should be far compensated by 
time and space we'll save by having a good hit at selecting right compression 
algorithm.



Cheers,
Nitin Gupta

Re: [lc-devel] Chunk list issues

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

Mauricio Lin wrote:
> Hi Gupta,
> 
> I keep implementing some more functions related to chunk list operations.
> 
> If you have in mind functions that will be important in terms of chunk
> list, let me know.
> 

I'm not yet into compression structure implementation work, so can't think of 
any particular function. I will let you know when I come to it.

-- Nitin


> 
> On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
>> Mauricio Lin wrote:
>> > Hi Gupta,
>> >
>> > BTW, is there any special reason the related chunks are just
>> > singly-linked list? Could they be also doubly-linked list as the
>> > master chunk list?
>> >
>> > BR,
>> >
>> > Mauricio Lin.
>> >
>> > On 6/21/06, Mauricio Lin <mau...@gm...> wrote:
>> >> Hi Gupta,
>> >>
>> >> I started to implement some basic operations related to chunk list
>> >> (not finished yet). Take a look if such functions and macros can be
>> >> useful.
>> >>
>> >> /* This works as the header of master chunk list*/
>> >> struct chunk init_chunk = {
>> >>         .start_addr = NULL,
>> >>         .size = 0,
>> >>         .next = NULL,
>> >>         .chunks = LIST_HEAD_INIT(init_chunk.chunks)
>> >> };
>> >>
>> >> #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 ; )
>> >>
>> >> static inline void add_chunk_to_list(struct chunk *chk)
>> >> {
>> >>         list_add_tail(&chk->chunks, &init_chunk.chunks);
>> >> }
>> >>
>> >> static inline void del_chunk_from_list(struct chunk *chk)
>> >> {
>> >>         list_del(&chk->chunks);
>> >> }
>> >>
>> >> What do you think?
>>
>> These will be useful. Thanks.
>>
>> -- Nitin
>>
>> >>
>> >> BR,
>> >>
>> >> Mauricio Lin.
>> >>
>> >>
>> >> On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
>> >> > Hi Mauricio,
>> >> >
>> >> > Mauricio Lin wrote:
>> >> > > On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
>> >> > >> Mauricio Lin wrote:
>> >> > >> > Regarding the master chunk list (chunks) in the struct chunk,
>> >> does it
>> >> > >> > store the chunks of one page cache or several page caches? 
>> Will be
>> >> > >> > there one master chunk list per page cache radix tree?
>> >> > >>
>> >> > >> 'master chunk list' is list of all chunks -- these chunks may be
>> >> part
>> >> > >> of a file,
>> >> > >> part of anon page, or free chunks. Its there to easily merge
>> >> > >> physically adjacent
>> >> > >> chunks when a chunk is freed.
>> >> > >
>> >> > > You mean there will be one master chunk list for several page 
>> cache
>> >> > > radix tree, right?
>> >> > >
>> >> >
>> >> > Yes.
>> >> > In other words: nodes of several page cache radix trees will be
>> >> replaces by
>> >> > chunk_head's. These chunk_head's point to corres. list of chunks.
>> >> And all these
>> >> > chunks are linked together by master chunk list (MCL).
>> >> >
>> >> > >>
>> >> > >> >
>> >> > >> > I also wonder where the chunk list header will be stored. For
>> >> instance
>> >> > >> > the list header of task_struct is stored in the tasks field of
>> >> > >> > init_task, so when an insertion happens in the list of
>> >> task_struct,
>> >> > >> > something like that is used:
>> >> > >> >
>> >> > >> > list_add_tail(&p->tasks, &init_task.tasks);
>> >> > >> >
>> >> > >> > where the first argument is the element to be inserted and the
>> >> second
>> >> > >> > argument corresponds the list header of task_struct.
>> >> > >> > Thus where the list header of chunks will be stored? Any idea?
>> >> > >> >
>> >> > >>
>> >> > >> A compressed page is stored in many chunks.
>> >> chunk_head->chunk_list is
>> >> > >> made to
>> >> > >> point to first of these chunks and these 'related' chunks are 
>> linked
>> >> > >> together
>> >> > >> using chunk->next
>> >> > >
>> >> > > OK, I know about the chunk_list purpose, but chunk_list is not the
>> >> > > header of master chunk list, since it is not a list_head. What 
>> I am
>> >> > > trying to say is if you want to add something in the master chunk
>> >> > > list, you have to use a function as list_add_tail() (or similar
>> >> one in
>> >> > > include/linux/list.h) and a header list is needed for representing
>> >> and
>> >> > > manipulating the master chunk list. If you are going to add 
>> something
>> >> > > in the master chunk list, certainly functions in 
>> include/linux/list.h
>> >> > > need be used. Let's suppose that list_add_tail() function is 
>> used to
>> >> > > insert a chunk in the list, so in this way something like this is
>> >> > > used:
>> >> > >
>> >> > > list_add_tail(&chk->chunks, chunk_list_head);
>> >> > >
>> >> > > chk is a instance of struct chunk, where the field "chunks" is
>> >> used to
>> >> > > link to the list.
>> >> > > chunk_list_head is the header of chunk list of type 'list_head'
>> >> > > (because every list has a header)
>> >> > >
>> >> > > Such can be declared and initiliazed as:
>> >> > > static LIST_HEAD(chunk_list_head);
>> >> > >
>> >> > > The chunk_list_head  (header of master chunk list) must be 
>> stored in
>> >> > > some place. So my question is where it is going to be stored ?
>> >> > >
>> >> >
>> >> > I was still stuck with 'related chunk list' (ok, RCL) while
>> >> answering you :)
>> >> > All these lists: MCL, LRU_{page_cache_clean,page_cache_dirty,anon},
>> >> > Free_{good,bad,ugly} will have their heads as globals in mm/ccache.c
>> >> >
>> >> > Of these:
>> >> > MCL lists use chunk->chunks (doubly linked)
>> >> > LRU lists use chunk_head->lru (doubly linked)
>> >> > Free lists use chunk->next (singly linked)
>> >> >
>> >> >
>> >> > Cheers,
>> >> > Nitin Gupta
>> >> >
>> >> >
>> >> >
>> >>
>> >
>>
>>
> 

Re: [lc-devel] Chunk list issues

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

Hi Gupta,

I keep implementing some more functions related to chunk list operations.

If you have in mind functions that will be important in terms of chunk
list, let me know.

BR,

Mauricio Lin.

On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
> Mauricio Lin wrote:
> > Hi Gupta,
> >
> > BTW, is there any special reason the related chunks are just
> > singly-linked list? Could they be also doubly-linked list as the
> > master chunk list?
> >
> > BR,
> >
> > Mauricio Lin.
> >
> > On 6/21/06, Mauricio Lin <mau...@gm...> wrote:
> >> Hi Gupta,
> >>
> >> I started to implement some basic operations related to chunk list
> >> (not finished yet). Take a look if such functions and macros can be
> >> useful.
> >>
> >> /* This works as the header of master chunk list*/
> >> struct chunk init_chunk = {
> >>         .start_addr = NULL,
> >>         .size = 0,
> >>         .next = NULL,
> >>         .chunks = LIST_HEAD_INIT(init_chunk.chunks)
> >> };
> >>
> >> #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 ; )
> >>
> >> static inline void add_chunk_to_list(struct chunk *chk)
> >> {
> >>         list_add_tail(&chk->chunks, &init_chunk.chunks);
> >> }
> >>
> >> static inline void del_chunk_from_list(struct chunk *chk)
> >> {
> >>         list_del(&chk->chunks);
> >> }
> >>
> >> What do you think?
>
> These will be useful. Thanks.
>
> -- Nitin
>
> >>
> >> BR,
> >>
> >> Mauricio Lin.
> >>
> >>
> >> On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
> >> > Hi Mauricio,
> >> >
> >> > Mauricio Lin wrote:
> >> > > On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
> >> > >> Mauricio Lin wrote:
> >> > >> > Regarding the master chunk list (chunks) in the struct chunk,
> >> does it
> >> > >> > store the chunks of one page cache or several page caches? Will be
> >> > >> > there one master chunk list per page cache radix tree?
> >> > >>
> >> > >> 'master chunk list' is list of all chunks -- these chunks may be
> >> part
> >> > >> of a file,
> >> > >> part of anon page, or free chunks. Its there to easily merge
> >> > >> physically adjacent
> >> > >> chunks when a chunk is freed.
> >> > >
> >> > > You mean there will be one master chunk list for several page cache
> >> > > radix tree, right?
> >> > >
> >> >
> >> > Yes.
> >> > In other words: nodes of several page cache radix trees will be
> >> replaces by
> >> > chunk_head's. These chunk_head's point to corres. list of chunks.
> >> And all these
> >> > chunks are linked together by master chunk list (MCL).
> >> >
> >> > >>
> >> > >> >
> >> > >> > I also wonder where the chunk list header will be stored. For
> >> instance
> >> > >> > the list header of task_struct is stored in the tasks field of
> >> > >> > init_task, so when an insertion happens in the list of
> >> task_struct,
> >> > >> > something like that is used:
> >> > >> >
> >> > >> > list_add_tail(&p->tasks, &init_task.tasks);
> >> > >> >
> >> > >> > where the first argument is the element to be inserted and the
> >> second
> >> > >> > argument corresponds the list header of task_struct.
> >> > >> > Thus where the list header of chunks will be stored? Any idea?
> >> > >> >
> >> > >>
> >> > >> A compressed page is stored in many chunks.
> >> chunk_head->chunk_list is
> >> > >> made to
> >> > >> point to first of these chunks and these 'related' chunks are linked
> >> > >> together
> >> > >> using chunk->next
> >> > >
> >> > > OK, I know about the chunk_list purpose, but chunk_list is not the
> >> > > header of master chunk list, since it is not a list_head. What I am
> >> > > trying to say is if you want to add something in the master chunk
> >> > > list, you have to use a function as list_add_tail() (or similar
> >> one in
> >> > > include/linux/list.h) and a header list is needed for representing
> >> and
> >> > > manipulating the master chunk list. If you are going to add something
> >> > > in the master chunk list, certainly functions in include/linux/list.h
> >> > > need be used. Let's suppose that list_add_tail() function is used to
> >> > > insert a chunk in the list, so in this way something like this is
> >> > > used:
> >> > >
> >> > > list_add_tail(&chk->chunks, chunk_list_head);
> >> > >
> >> > > chk is a instance of struct chunk, where the field "chunks" is
> >> used to
> >> > > link to the list.
> >> > > chunk_list_head is the header of chunk list of type 'list_head'
> >> > > (because every list has a header)
> >> > >
> >> > > Such can be declared and initiliazed as:
> >> > > static LIST_HEAD(chunk_list_head);
> >> > >
> >> > > The chunk_list_head  (header of master chunk list) must be stored in
> >> > > some place. So my question is where it is going to be stored ?
> >> > >
> >> >
> >> > I was still stuck with 'related chunk list' (ok, RCL) while
> >> answering you :)
> >> > All these lists: MCL, LRU_{page_cache_clean,page_cache_dirty,anon},
> >> > Free_{good,bad,ugly} will have their heads as globals in mm/ccache.c
> >> >
> >> > Of these:
> >> > MCL lists use chunk->chunks (doubly linked)
> >> > LRU lists use chunk_head->lru (doubly linked)
> >> > Free lists use chunk->next (singly linked)
> >> >
> >> >
> >> > Cheers,
> >> > Nitin Gupta
> >> >
> >> >
> >> >
> >>
> >
>
>

Re: [lc-devel] Chunk list issues

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

Mauricio Lin wrote:
> Hi Gupta,
> 
> BTW, is there any special reason the related chunks are just
> singly-linked list? Could they be also doubly-linked list as the
> master chunk list?
> 

making that as doubly linked list will make each chunk take 4 bytes (32-bit 
system) extra. Thats the only reason.

-- Nitin

> BR,
> 
> Mauricio Lin.
> 
> On 6/21/06, Mauricio Lin <mau...@gm...> wrote:
>> Hi Gupta,
>>
>> I started to implement some basic operations related to chunk list
>> (not finished yet). Take a look if such functions and macros can be
>> useful.
>>
>> /* This works as the header of master chunk list*/
>> struct chunk init_chunk = {
>>         .start_addr = NULL,
>>         .size = 0,
>>         .next = NULL,
>>         .chunks = LIST_HEAD_INIT(init_chunk.chunks)
>> };
>>
>> #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 ; )
>>
>> static inline void add_chunk_to_list(struct chunk *chk)
>> {
>>         list_add_tail(&chk->chunks, &init_chunk.chunks);
>> }
>>
>> static inline void del_chunk_from_list(struct chunk *chk)
>> {
>>         list_del(&chk->chunks);
>> }
>>
>> What do you think?
>>
>> BR,
>>
>> Mauricio Lin.
>>
>>
>> On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
>> > Hi Mauricio,
>> >
>> > Mauricio Lin wrote:
>> > > On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
>> > >> Mauricio Lin wrote:
>> > >> > Regarding the master chunk list (chunks) in the struct chunk, 
>> does it
>> > >> > store the chunks of one page cache or several page caches? Will be
>> > >> > there one master chunk list per page cache radix tree?
>> > >>
>> > >> 'master chunk list' is list of all chunks -- these chunks may be 
>> part
>> > >> of a file,
>> > >> part of anon page, or free chunks. Its there to easily merge
>> > >> physically adjacent
>> > >> chunks when a chunk is freed.
>> > >
>> > > You mean there will be one master chunk list for several page cache
>> > > radix tree, right?
>> > >
>> >
>> > Yes.
>> > In other words: nodes of several page cache radix trees will be 
>> replaces by
>> > chunk_head's. These chunk_head's point to corres. list of chunks. 
>> And all these
>> > chunks are linked together by master chunk list (MCL).
>> >
>> > >>
>> > >> >
>> > >> > I also wonder where the chunk list header will be stored. For 
>> instance
>> > >> > the list header of task_struct is stored in the tasks field of
>> > >> > init_task, so when an insertion happens in the list of 
>> task_struct,
>> > >> > something like that is used:
>> > >> >
>> > >> > list_add_tail(&p->tasks, &init_task.tasks);
>> > >> >
>> > >> > where the first argument is the element to be inserted and the 
>> second
>> > >> > argument corresponds the list header of task_struct.
>> > >> > Thus where the list header of chunks will be stored? Any idea?
>> > >> >
>> > >>
>> > >> A compressed page is stored in many chunks. 
>> chunk_head->chunk_list is
>> > >> made to
>> > >> point to first of these chunks and these 'related' chunks are linked
>> > >> together
>> > >> using chunk->next
>> > >
>> > > OK, I know about the chunk_list purpose, but chunk_list is not the
>> > > header of master chunk list, since it is not a list_head. What I am
>> > > trying to say is if you want to add something in the master chunk
>> > > list, you have to use a function as list_add_tail() (or similar 
>> one in
>> > > include/linux/list.h) and a header list is needed for representing 
>> and
>> > > manipulating the master chunk list. If you are going to add something
>> > > in the master chunk list, certainly functions in include/linux/list.h
>> > > need be used. Let's suppose that list_add_tail() function is used to
>> > > insert a chunk in the list, so in this way something like this is
>> > > used:
>> > >
>> > > list_add_tail(&chk->chunks, chunk_list_head);
>> > >
>> > > chk is a instance of struct chunk, where the field "chunks" is 
>> used to
>> > > link to the list.
>> > > chunk_list_head is the header of chunk list of type 'list_head'
>> > > (because every list has a header)
>> > >
>> > > Such can be declared and initiliazed as:
>> > > static LIST_HEAD(chunk_list_head);
>> > >
>> > > The chunk_list_head  (header of master chunk list) must be stored in
>> > > some place. So my question is where it is going to be stored ?
>> > >
>> >
>> > I was still stuck with 'related chunk list' (ok, RCL) while 
>> answering you :)
>> > All these lists: MCL, LRU_{page_cache_clean,page_cache_dirty,anon},
>> > Free_{good,bad,ugly} will have their heads as globals in mm/ccache.c
>> >
>> > Of these:
>> > MCL lists use chunk->chunks (doubly linked)
>> > LRU lists use chunk_head->lru (doubly linked)
>> > Free lists use chunk->next (singly linked)
>> >
>> >
>> > Cheers,
>> > Nitin Gupta
>> >
>> >
>> >
>>
> 

Re: [lc-devel] Chunk list issues

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

Mauricio Lin wrote:
> Hi Gupta,
> 
> BTW, is there any special reason the related chunks are just
> singly-linked list? Could they be also doubly-linked list as the
> master chunk list?
> 
> BR,
> 
> Mauricio Lin.
> 
> On 6/21/06, Mauricio Lin <mau...@gm...> wrote:
>> Hi Gupta,
>>
>> I started to implement some basic operations related to chunk list
>> (not finished yet). Take a look if such functions and macros can be
>> useful.
>>
>> /* This works as the header of master chunk list*/
>> struct chunk init_chunk = {
>>         .start_addr = NULL,
>>         .size = 0,
>>         .next = NULL,
>>         .chunks = LIST_HEAD_INIT(init_chunk.chunks)
>> };
>>
>> #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 ; )
>>
>> static inline void add_chunk_to_list(struct chunk *chk)
>> {
>>         list_add_tail(&chk->chunks, &init_chunk.chunks);
>> }
>>
>> static inline void del_chunk_from_list(struct chunk *chk)
>> {
>>         list_del(&chk->chunks);
>> }
>>
>> What do you think?

These will be useful. Thanks.

-- Nitin

>>
>> BR,
>>
>> Mauricio Lin.
>>
>>
>> On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
>> > Hi Mauricio,
>> >
>> > Mauricio Lin wrote:
>> > > On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
>> > >> Mauricio Lin wrote:
>> > >> > Regarding the master chunk list (chunks) in the struct chunk, 
>> does it
>> > >> > store the chunks of one page cache or several page caches? Will be
>> > >> > there one master chunk list per page cache radix tree?
>> > >>
>> > >> 'master chunk list' is list of all chunks -- these chunks may be 
>> part
>> > >> of a file,
>> > >> part of anon page, or free chunks. Its there to easily merge
>> > >> physically adjacent
>> > >> chunks when a chunk is freed.
>> > >
>> > > You mean there will be one master chunk list for several page cache
>> > > radix tree, right?
>> > >
>> >
>> > Yes.
>> > In other words: nodes of several page cache radix trees will be 
>> replaces by
>> > chunk_head's. These chunk_head's point to corres. list of chunks. 
>> And all these
>> > chunks are linked together by master chunk list (MCL).
>> >
>> > >>
>> > >> >
>> > >> > I also wonder where the chunk list header will be stored. For 
>> instance
>> > >> > the list header of task_struct is stored in the tasks field of
>> > >> > init_task, so when an insertion happens in the list of 
>> task_struct,
>> > >> > something like that is used:
>> > >> >
>> > >> > list_add_tail(&p->tasks, &init_task.tasks);
>> > >> >
>> > >> > where the first argument is the element to be inserted and the 
>> second
>> > >> > argument corresponds the list header of task_struct.
>> > >> > Thus where the list header of chunks will be stored? Any idea?
>> > >> >
>> > >>
>> > >> A compressed page is stored in many chunks. 
>> chunk_head->chunk_list is
>> > >> made to
>> > >> point to first of these chunks and these 'related' chunks are linked
>> > >> together
>> > >> using chunk->next
>> > >
>> > > OK, I know about the chunk_list purpose, but chunk_list is not the
>> > > header of master chunk list, since it is not a list_head. What I am
>> > > trying to say is if you want to add something in the master chunk
>> > > list, you have to use a function as list_add_tail() (or similar 
>> one in
>> > > include/linux/list.h) and a header list is needed for representing 
>> and
>> > > manipulating the master chunk list. If you are going to add something
>> > > in the master chunk list, certainly functions in include/linux/list.h
>> > > need be used. Let's suppose that list_add_tail() function is used to
>> > > insert a chunk in the list, so in this way something like this is
>> > > used:
>> > >
>> > > list_add_tail(&chk->chunks, chunk_list_head);
>> > >
>> > > chk is a instance of struct chunk, where the field "chunks" is 
>> used to
>> > > link to the list.
>> > > chunk_list_head is the header of chunk list of type 'list_head'
>> > > (because every list has a header)
>> > >
>> > > Such can be declared and initiliazed as:
>> > > static LIST_HEAD(chunk_list_head);
>> > >
>> > > The chunk_list_head  (header of master chunk list) must be stored in
>> > > some place. So my question is where it is going to be stored ?
>> > >
>> >
>> > I was still stuck with 'related chunk list' (ok, RCL) while 
>> answering you :)
>> > All these lists: MCL, LRU_{page_cache_clean,page_cache_dirty,anon},
>> > Free_{good,bad,ugly} will have their heads as globals in mm/ccache.c
>> >
>> > Of these:
>> > MCL lists use chunk->chunks (doubly linked)
>> > LRU lists use chunk_head->lru (doubly linked)
>> > Free lists use chunk->next (singly linked)
>> >
>> >
>> > Cheers,
>> > Nitin Gupta
>> >
>> >
>> >
>>
> 

Re: [lc-devel] Chunk list issues

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

Hi Gupta,

BTW, is there any special reason the related chunks are just
singly-linked list? Could they be also doubly-linked list as the
master chunk list?

BR,

Mauricio Lin.

On 6/21/06, Mauricio Lin <mau...@gm...> wrote:
> Hi Gupta,
>
> I started to implement some basic operations related to chunk list
> (not finished yet). Take a look if such functions and macros can be
> useful.
>
> /* This works as the header of master chunk list*/
> struct chunk init_chunk = {
>         .start_addr = NULL,
>         .size = 0,
>         .next = NULL,
>         .chunks = LIST_HEAD_INIT(init_chunk.chunks)
> };
>
> #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 ; )
>
> static inline void add_chunk_to_list(struct chunk *chk)
> {
>         list_add_tail(&chk->chunks, &init_chunk.chunks);
> }
>
> static inline void del_chunk_from_list(struct chunk *chk)
> {
>         list_del(&chk->chunks);
> }
>
> What do you think?
>
> BR,
>
> Mauricio Lin.
>
>
> On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
> > Hi Mauricio,
> >
> > Mauricio Lin wrote:
> > > On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
> > >> Mauricio Lin wrote:
> > >> > Regarding the master chunk list (chunks) in the struct chunk, does it
> > >> > store the chunks of one page cache or several page caches? Will be
> > >> > there one master chunk list per page cache radix tree?
> > >>
> > >> 'master chunk list' is list of all chunks -- these chunks may be part
> > >> of a file,
> > >> part of anon page, or free chunks. Its there to easily merge
> > >> physically adjacent
> > >> chunks when a chunk is freed.
> > >
> > > You mean there will be one master chunk list for several page cache
> > > radix tree, right?
> > >
> >
> > Yes.
> > In other words: nodes of several page cache radix trees will be replaces by
> > chunk_head's. These chunk_head's point to corres. list of chunks. And all these
> > chunks are linked together by master chunk list (MCL).
> >
> > >>
> > >> >
> > >> > I also wonder where the chunk list header will be stored. For instance
> > >> > the list header of task_struct is stored in the tasks field of
> > >> > init_task, so when an insertion happens in the list of task_struct,
> > >> > something like that is used:
> > >> >
> > >> > list_add_tail(&p->tasks, &init_task.tasks);
> > >> >
> > >> > where the first argument is the element to be inserted and the second
> > >> > argument corresponds the list header of task_struct.
> > >> > Thus where the list header of chunks will be stored? Any idea?
> > >> >
> > >>
> > >> A compressed page is stored in many chunks. chunk_head->chunk_list is
> > >> made to
> > >> point to first of these chunks and these 'related' chunks are linked
> > >> together
> > >> using chunk->next
> > >
> > > OK, I know about the chunk_list purpose, but chunk_list is not the
> > > header of master chunk list, since it is not a list_head. What I am
> > > trying to say is if you want to add something in the master chunk
> > > list, you have to use a function as list_add_tail() (or similar one in
> > > include/linux/list.h) and a header list is needed for representing and
> > > manipulating the master chunk list. If you are going to add something
> > > in the master chunk list, certainly functions in include/linux/list.h
> > > need be used. Let's suppose that list_add_tail() function is used to
> > > insert a chunk in the list, so in this way something like this is
> > > used:
> > >
> > > list_add_tail(&chk->chunks, chunk_list_head);
> > >
> > > chk is a instance of struct chunk, where the field "chunks" is used to
> > > link to the list.
> > > chunk_list_head is the header of chunk list of type 'list_head'
> > > (because every list has a header)
> > >
> > > Such can be declared and initiliazed as:
> > > static LIST_HEAD(chunk_list_head);
> > >
> > > The chunk_list_head  (header of master chunk list) must be stored in
> > > some place. So my question is where it is going to be stored ?
> > >
> >
> > I was still stuck with 'related chunk list' (ok, RCL) while answering you :)
> > All these lists: MCL, LRU_{page_cache_clean,page_cache_dirty,anon},
> > Free_{good,bad,ugly} will have their heads as globals in mm/ccache.c
> >
> > Of these:
> > MCL lists use chunk->chunks (doubly linked)
> > LRU lists use chunk_head->lru (doubly linked)
> > Free lists use chunk->next (singly linked)
> >
> >
> > Cheers,
> > Nitin Gupta
> >
> >
> >
>

Re: [lc-devel] Chunk list issues

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

Hi Gupta,

I started to implement some basic operations related to chunk list
(not finished yet). Take a look if such functions and macros can be
useful.

/* This works as the header of master chunk list*/
struct chunk init_chunk = {
	.start_addr = NULL,
	.size = 0,
	.next = NULL,
	.chunks = LIST_HEAD_INIT(init_chunk.chunks)
};

#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 ; )

static inline void add_chunk_to_list(struct chunk *chk)
{
	list_add_tail(&chk->chunks, &init_chunk.chunks);
}

static inline void del_chunk_from_list(struct chunk *chk)
{
	list_del(&chk->chunks);
}

What do you think?

BR,

Mauricio Lin.


On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
> Hi Mauricio,
>
> Mauricio Lin wrote:
> > On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
> >> Mauricio Lin wrote:
> >> > Regarding the master chunk list (chunks) in the struct chunk, does it
> >> > store the chunks of one page cache or several page caches? Will be
> >> > there one master chunk list per page cache radix tree?
> >>
> >> 'master chunk list' is list of all chunks -- these chunks may be part
> >> of a file,
> >> part of anon page, or free chunks. Its there to easily merge
> >> physically adjacent
> >> chunks when a chunk is freed.
> >
> > You mean there will be one master chunk list for several page cache
> > radix tree, right?
> >
>
> Yes.
> In other words: nodes of several page cache radix trees will be replaces by
> chunk_head's. These chunk_head's point to corres. list of chunks. And all these
> chunks are linked together by master chunk list (MCL).
>
> >>
> >> >
> >> > I also wonder where the chunk list header will be stored. For instance
> >> > the list header of task_struct is stored in the tasks field of
> >> > init_task, so when an insertion happens in the list of task_struct,
> >> > something like that is used:
> >> >
> >> > list_add_tail(&p->tasks, &init_task.tasks);
> >> >
> >> > where the first argument is the element to be inserted and the second
> >> > argument corresponds the list header of task_struct.
> >> > Thus where the list header of chunks will be stored? Any idea?
> >> >
> >>
> >> A compressed page is stored in many chunks. chunk_head->chunk_list is
> >> made to
> >> point to first of these chunks and these 'related' chunks are linked
> >> together
> >> using chunk->next
> >
> > OK, I know about the chunk_list purpose, but chunk_list is not the
> > header of master chunk list, since it is not a list_head. What I am
> > trying to say is if you want to add something in the master chunk
> > list, you have to use a function as list_add_tail() (or similar one in
> > include/linux/list.h) and a header list is needed for representing and
> > manipulating the master chunk list. If you are going to add something
> > in the master chunk list, certainly functions in include/linux/list.h
> > need be used. Let's suppose that list_add_tail() function is used to
> > insert a chunk in the list, so in this way something like this is
> > used:
> >
> > list_add_tail(&chk->chunks, chunk_list_head);
> >
> > chk is a instance of struct chunk, where the field "chunks" is used to
> > link to the list.
> > chunk_list_head is the header of chunk list of type 'list_head'
> > (because every list has a header)
> >
> > Such can be declared and initiliazed as:
> > static LIST_HEAD(chunk_list_head);
> >
> > The chunk_list_head  (header of master chunk list) must be stored in
> > some place. So my question is where it is going to be stored ?
> >
>
> I was still stuck with 'related chunk list' (ok, RCL) while answering you :)
> All these lists: MCL, LRU_{page_cache_clean,page_cache_dirty,anon},
> Free_{good,bad,ugly} will have their heads as globals in mm/ccache.c
>
> Of these:
> MCL lists use chunk->chunks (doubly linked)
> LRU lists use chunk_head->lru (doubly linked)
> Free lists use chunk->next (singly linked)
>
>
> Cheers,
> Nitin Gupta
>
>
>

Re: [lc-devel] Chunk list issues

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

Hi Mauricio,

Mauricio Lin wrote:
> On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
>> Mauricio Lin wrote:
>> > Regarding the master chunk list (chunks) in the struct chunk, does it
>> > store the chunks of one page cache or several page caches? Will be
>> > there one master chunk list per page cache radix tree?
>>
>> 'master chunk list' is list of all chunks -- these chunks may be part 
>> of a file,
>> part of anon page, or free chunks. Its there to easily merge 
>> physically adjacent
>> chunks when a chunk is freed.
> 
> You mean there will be one master chunk list for several page cache
> radix tree, right?
> 

Yes.
In other words: nodes of several page cache radix trees will be replaces by 
chunk_head's. These chunk_head's point to corres. list of chunks. And all these 
chunks are linked together by master chunk list (MCL).

>>
>> >
>> > I also wonder where the chunk list header will be stored. For instance
>> > the list header of task_struct is stored in the tasks field of
>> > init_task, so when an insertion happens in the list of task_struct,
>> > something like that is used:
>> >
>> > list_add_tail(&p->tasks, &init_task.tasks);
>> >
>> > where the first argument is the element to be inserted and the second
>> > argument corresponds the list header of task_struct.
>> > Thus where the list header of chunks will be stored? Any idea?
>> >
>>
>> A compressed page is stored in many chunks. chunk_head->chunk_list is 
>> made to
>> point to first of these chunks and these 'related' chunks are linked 
>> together
>> using chunk->next
> 
> OK, I know about the chunk_list purpose, but chunk_list is not the
> header of master chunk list, since it is not a list_head. What I am
> trying to say is if you want to add something in the master chunk
> list, you have to use a function as list_add_tail() (or similar one in
> include/linux/list.h) and a header list is needed for representing and
> manipulating the master chunk list. If you are going to add something
> in the master chunk list, certainly functions in include/linux/list.h
> need be used. Let's suppose that list_add_tail() function is used to
> insert a chunk in the list, so in this way something like this is
> used:
> 
> list_add_tail(&chk->chunks, chunk_list_head);
> 
> chk is a instance of struct chunk, where the field "chunks" is used to
> link to the list.
> chunk_list_head is the header of chunk list of type 'list_head'
> (because every list has a header)
> 
> Such can be declared and initiliazed as:
> static LIST_HEAD(chunk_list_head);
> 
> The chunk_list_head  (header of master chunk list) must be stored in
> some place. So my question is where it is going to be stored ?
> 

I was still stuck with 'related chunk list' (ok, RCL) while answering you :)
All these lists: MCL, LRU_{page_cache_clean,page_cache_dirty,anon}, 
Free_{good,bad,ugly} will have their heads as globals in mm/ccache.c

Of these:
MCL lists use chunk->chunks (doubly linked)
LRU lists use chunk_head->lru (doubly linked)
Free lists use chunk->next (singly linked)


Cheers,
Nitin Gupta

[lc-devel] CCache work status

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

Hi,

I just took all work upto now to 2.6.17.1 and virtual swap work seems to be
gaining some ground now.

This patch makes this vswap and system can swap out to this with no problem.
Also started work on to replace the page that comes to vswap with chunk_head
and restore them when they are looked up in page/swap cache lookup functions
(find_get_page() and friends). I hope to post this much in next few days.

Following this, I will start actual compression using algos ported and
compression structure implementation (as on Wiki).

Cheers,
Nitin Gupta

Re: [lc-devel] Chunk list issues

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

On 6/21/06, Mauricio Lin <mau...@gm...> wrote:
> Hi Gupta,
>
> On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
> > Hi Mauricio,
> >
> > Mauricio Lin wrote:
> > > Regarding the master chunk list (chunks) in the struct chunk, does it
> > > store the chunks of one page cache or several page caches? Will be
> > > there one master chunk list per page cache radix tree?
> >
> > 'master chunk list' is list of all chunks -- these chunks may be part of a file,
> > part of anon page, or free chunks. Its there to easily merge physically adjacent
> > chunks when a chunk is freed.
>
> You mean there will be one master chunk list for several page cache
> radix tree, right?
>
> >
> > >
> > > I also wonder where the chunk list header will be stored. For instance
> > > the list header of task_struct is stored in the tasks field of
> > > init_task, so when an insertion happens in the list of task_struct,
> > > something like that is used:
> > >
> > > list_add_tail(&p->tasks, &init_task.tasks);
> > >
> > > where the first argument is the element to be inserted and the second
> > > argument corresponds the list header of task_struct.
> > > Thus where the list header of chunks will be stored? Any idea?
> > >
> >
> > A compressed page is stored in many chunks. chunk_head->chunk_list is made to
> > point to first of these chunks and these 'related' chunks are linked together
> > using chunk->next
>
> OK, I know about the chunk_list purpose, but chunk_list is not the
> header of master chunk list, since it is not a list_head. What I am
> trying to say is if you want to add something in the master chunk
> list, you have to use a function as list_add_tail() (or similar one in
> include/linux/list.h) and a header list is needed for representing and
> manipulating the master chunk list. If you are going to add something
> in the master chunk list, certainly functions in include/linux/list.h
> need be used. Let's suppose that list_add_tail() function is used to
> insert a chunk in the list, so in this way something like this is
> used:
>
> list_add_tail(&chk->chunks, chunk_list_head);
>
> chk is a instance of struct chunk, where the field "chunks" is used to
> link to the list.
> chunk_list_head is the header of chunk list of type 'list_head'
> (because every list has a header)
>
> Such can be declared and initiliazed as:
> static LIST_HEAD(chunk_list_head);
>
> The chunk_list_head  (header of master chunk list) must be stored in
> some place. So my question is where it is going to be stored ?
>

Perhaps create an init_chunk that stores the header of master chunk
list is a good way. So that follows the same idea of init_task for
list of task_struct.

> BR,
>
> Mauricio Lin.
>

Re: [lc-devel] Chunk list issues

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

Hi Gupta,

On 6/21/06, Nitin Gupta <nit...@gm...> wrote:
> Hi Mauricio,
>
> Mauricio Lin wrote:
> > Regarding the master chunk list (chunks) in the struct chunk, does it
> > store the chunks of one page cache or several page caches? Will be
> > there one master chunk list per page cache radix tree?
>
> 'master chunk list' is list of all chunks -- these chunks may be part of a file,
> part of anon page, or free chunks. Its there to easily merge physically adjacent
> chunks when a chunk is freed.

You mean there will be one master chunk list for several page cache
radix tree, right?

>
> >
> > I also wonder where the chunk list header will be stored. For instance
> > the list header of task_struct is stored in the tasks field of
> > init_task, so when an insertion happens in the list of task_struct,
> > something like that is used:
> >
> > list_add_tail(&p->tasks, &init_task.tasks);
> >
> > where the first argument is the element to be inserted and the second
> > argument corresponds the list header of task_struct.
> > Thus where the list header of chunks will be stored? Any idea?
> >
>
> A compressed page is stored in many chunks. chunk_head->chunk_list is made to
> point to first of these chunks and these 'related' chunks are linked together
> using chunk->next

OK, I know about the chunk_list purpose, but chunk_list is not the
header of master chunk list, since it is not a list_head. What I am
trying to say is if you want to add something in the master chunk
list, you have to use a function as list_add_tail() (or similar one in
include/linux/list.h) and a header list is needed for representing and
manipulating the master chunk list. If you are going to add something
in the master chunk list, certainly functions in include/linux/list.h
need be used. Let's suppose that list_add_tail() function is used to
insert a chunk in the list, so in this way something like this is
used:

list_add_tail(&chk->chunks, chunk_list_head);

chk is a instance of struct chunk, where the field "chunks" is used to
link to the list.
chunk_list_head is the header of chunk list of type 'list_head'
(because every list has a header)

Such can be declared and initiliazed as:
static LIST_HEAD(chunk_list_head);

The chunk_list_head  (header of master chunk list) must be stored in
some place. So my question is where it is going to be stored ?

BR,

Mauricio Lin.

Re: [lc-devel] Chunk list issues

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

Hi Mauricio,

Mauricio Lin wrote:
> Regarding the master chunk list (chunks) in the struct chunk, does it
> store the chunks of one page cache or several page caches? Will be
> there one master chunk list per page cache radix tree?

'master chunk list' is list of all chunks -- these chunks may be part of a file, 
part of anon page, or free chunks. Its there to easily merge physically adjacent 
chunks when a chunk is freed.

> 
> I also wonder where the chunk list header will be stored. For instance
> the list header of task_struct is stored in the tasks field of
> init_task, so when an insertion happens in the list of task_struct,
> something like that is used:
> 
> list_add_tail(&p->tasks, &init_task.tasks);
> 
> where the first argument is the element to be inserted and the second
> argument corresponds the list header of task_struct.
> Thus where the list header of chunks will be stored? Any idea?
> 

A compressed page is stored in many chunks. chunk_head->chunk_list is made to 
point to first of these chunks and these 'related' chunks are linked together 
using chunk->next


Cheers,
Nitin Gupta