linuxcompressed-devel

[lc-devel] Chunk list issues

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

Hi all,

After checking the chunk list in
http://linux-mm.org/CompressedCaching, I have some questions as
follows.

Did anyone start to implement the chunk list operations? Is there any
progress of it?

Regarding the "struct chunk_head", the field "chunk_list" points to
the related chunks, right?
I mean if a page A in the page cache is replaced by the corresponding
chunk head, the field chunk_list in such chunk_head points to the list
of related chunks of page A, even if some chunks are located in other
physical pages, right?

Where ca I find more info about the purpose of lru field in the struct
chunk_head?

BR,

Mauricio Lin.

Re: [lc-devel] Chunk list issues

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

Hi Mauricio,

Mauricio Lin wrote:
 > Hi all,
 >
 > After checking the chunk list in
 > http://linux-mm.org/CompressedCaching, I have some questions as
 > follows.
 >
 > Did anyone start to implement the chunk list operations? Is there any
 > progress of it?
 >

No, I haven't yet started compression structure implementation.

 > Regarding the "struct chunk_head", the field "chunk_list" points to
 > the related chunks, right?
 > I mean if a page A in the page cache is replaced by the corresponding
 > chunk head, the field chunk_list in such chunk_head points to the list
 > of related chunks of page A, even if some chunks are located in other
 > physical pages, right?
 >

Yes. A page is compressed and stored in chunks (which can be present in 
different physical pages). These chunks are linked together using chunk->next.

 > Where ca I find more info about the purpose of lru field in the struct
 > chunk_head?
 >

chunk_head->lru has basically same purpose as struct page->lru.

When compressed cache become full, we have to free some pages from ccache to the 
  swap disk. The chunk_head->lru field is to have these chunk_heads in LRU 
order. So, when freeing pages from ccache, take a chunk_head from head of LRU 
list and free the chunk_head and corres. chunk(s).

These freed chunks are then merged with other physically adjacent free chunks 
(found using chunk->chunks->{prev, next}). A chunk is identified as free by flag 
(say, CH_free) stored in 4 MSBs of chunk->size (A chunk has max size of 
PAGE_SIZE so, 4 bits are free).

Also, as mentioned on site: LRU Lists will be maintained separately for clean 
page cache pages, dirty page cache pages and swap cache pages. This will allow 
pages of these individual types to be separately tracked and when compressed 
cache size reaches limit, specific types of pages and be freed in priority to 
other (like put more pressure to free clean page cache pages than dirty page 
cache pages and least on swap cache pages).


Cheers,
Nitin Gupta

Re: [lc-devel] Chunk list issues

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

Hi Gupta,

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?

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?

BR,

Mauricio Lin.

On 6/19/06, Nitin Gupta <nit...@gm...> wrote:
> Hi Mauricio,
>
> Mauricio Lin wrote:
>  > Hi all,
>  >
>  > After checking the chunk list in
>  > http://linux-mm.org/CompressedCaching, I have some questions as
>  > follows.
>  >
>  > Did anyone start to implement the chunk list operations? Is there any
>  > progress of it?
>  >
>
> No, I haven't yet started compression structure implementation.
>
>  > Regarding the "struct chunk_head", the field "chunk_list" points to
>  > the related chunks, right?
>  > I mean if a page A in the page cache is replaced by the corresponding
>  > chunk head, the field chunk_list in such chunk_head points to the list
>  > of related chunks of page A, even if some chunks are located in other
>  > physical pages, right?
>  >
>
> Yes. A page is compressed and stored in chunks (which can be present in
> different physical pages). These chunks are linked together using chunk->next.
>
>  > Where ca I find more info about the purpose of lru field in the struct
>  > chunk_head?
>  >
>
> chunk_head->lru has basically same purpose as struct page->lru.
>
> When compressed cache become full, we have to free some pages from ccache to the
>   swap disk. The chunk_head->lru field is to have these chunk_heads in LRU
> order. So, when freeing pages from ccache, take a chunk_head from head of LRU
> list and free the chunk_head and corres. chunk(s).
>
> These freed chunks are then merged with other physically adjacent free chunks
> (found using chunk->chunks->{prev, next}). A chunk is identified as free by flag
> (say, CH_free) stored in 4 MSBs of chunk->size (A chunk has max size of
> PAGE_SIZE so, 4 bits are free).
>
> Also, as mentioned on site: LRU Lists will be maintained separately for clean
> page cache pages, dirty page cache pages and swap cache pages. This will allow
> pages of these individual types to be separately tracked and when compressed
> cache size reaches limit, specific types of pages and be freed in priority to
> other (like put more pressure to free clean page cache pages than dirty page
> cache pages and least on swap cache pages).
>
>
> Cheers,
> Nitin Gupta
>

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

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

[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

[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

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

[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

[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,

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

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

[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

[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 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,

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

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 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.
> 
> 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] [linux-mm-cc] Re: Chunk list issues

[<ac...@sa...>]

Nitin Gupta wrote:
> 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 oth=
er
>>> 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
>

What should be considered here is how do we actually "migrate" a page
like this? Because this isn't done very often normally (how often do you
add/deactive swap areas) it is my understanding that this is an
expensive process, which is why we can't really do it, a proposal is to
instead of having a "vswap" area, that we allocate other physical swap
areas in advance and do the interception of find_get_page & friends as
is done in the git tree now. This way, when we need to kick out pages it
is a very straightforward process, just put it in the pre-allocated swap
slot. Of course this wastes swap space (probably disk) and doesn't work
with no swap area at all, so maybe a mix where you can add vswap in some
other way for no-swap area (where we never kick out pages anyways)
purely as an swap entry id excercise.

Greetings,
Asbj=F8rn Sannes

Re: [lc-devel] [linux-mm-cc] Re: Chunk list issues

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

Hi Sannes,

Asbjørn Sannes wrote:
> Nitin Gupta wrote:
>>
>>>> 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
>>
> 
> What should be considered here is how do we actually "migrate" a page
> like this? Because this isn't done very often normally (how often do you
> add/deactive swap areas) it is my understanding that this is an
> expensive process, which is why we can't really do it, a proposal is to
> instead of having a "vswap" area, that we allocate other physical swap
> areas in advance and do the interception of find_get_page & friends as
> is done in the git tree now. This way, when we need to kick out pages it
> is a very straightforward process, just put it in the pre-allocated swap
> slot. Of course this wastes swap space (probably disk) and doesn't work
> with no swap area at all, so maybe a mix where you can add vswap in some
> other way for no-swap area (where we never kick out pages anyways)
> purely as an swap entry id excercise.
> 

The only expensive step in this "migration" from vswap to real swap disk is 
scan_swap_map() (apart from actual disk write which has to be done anyway), 
which gives you a free swap slot. So, the expense is to run this scan_swap_map() 
twice -- once for vswap then for real swap when migrating pages.

This thing can be improved by fact that swap entry value does not determine 
(unlike for real swaps) where page goes in ccache storage. So, all we need is a 
unique no. every time we call scan_swap_map. For this, we can implement a custom 
scan_swap_map for vswap (and let usual one run for real swap). This can be as 
simple as a stack of free entries and will give us a unique swp_entry_t value 
instantly.  This is already being done in that storage-test module.

This will mitigate the cost of exec two scan_swap_map and your worry ;)

Cheers,
Nitin Gupta

Re: [lc-devel] [linux-mm-cc] Re: Chunk list issues

[<ac...@sa...>]

Nitin Gupta wrote:
> Hi Sannes,
>
> Asbj=F8rn Sannes wrote:
>> Nitin Gupta wrote:
>>>
>>>>> 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
>>>
>>
>> What should be considered here is how do we actually "migrate" a
>> page like this? Because this isn't done very often normally (how
>> often do you add/deactive swap areas) it is my understanding that
>> this is an expensive process, which is why we can't really do it, a
>>  proposal is to instead of having a "vswap" area, that we allocate
>> other physical swap areas in advance and do the interception of
>> find_get_page & friends as is done in the git tree now. This way,
>> when we need to kick out pages it is a very straightforward
>> process, just put it in the pre-allocated swap slot. Of course this
>>  wastes swap space (probably disk) and doesn't work with no swap
>> area at all, so maybe a mix where you can add vswap in some other
>> way for no-swap area (where we never kick out pages anyways) purely
>>  as an swap entry id excercise.
>>
>
> The only expensive step in this "migration" from vswap to real swap
> disk is scan_swap_map() (apart from actual disk write which has to be
>  done anyway), which gives you a free swap slot. So, the expense is
> to run this scan_swap_map() twice -- once for vswap then for real
> swap when migrating pages.
>

I'm  not sure how that is going to work, perhaps I'm missing the point,
scan_swap_map() is for allocating free slots of swap, which is fine.
What will be expensive is finding all those page table entries pointing
to your vswap page to be updated.

Keep in mind I'm talking about the case where you have a swap area
already and the heuristic wants to move a page from the compressed cache
to the disk (say kicking out the least recently used page).


> This thing can be improved by fact that swap entry value does not
> determine (unlike for real swaps) where page goes in ccache storage.
> So, all we need is a unique no. every time we call scan_swap_map. For
>  this, we can implement a custom scan_swap_map for vswap (and let
> usual one run for real swap). This can be as simple as a stack of
> free entries and will give us a unique swp_entry_t value instantly.
> This is already being done in that storage-test module.

Yes, this will take care of the case with no real swap (which was my
weak point).

> This will mitigate the cost of exec two scan_swap_map and your worry
> ;)

My worry was try_to_unuse() which visits each and every process going
through their memory allocations.

Mvh,
Asbj=F8rn Sannes

Re: [lc-devel] [linux-mm-cc] Re: Chunk list issues

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

On Sat, 1 Jul 2006, Asbj=F8rn Sannes wrote:

> What should be considered here is how do we actually "migrate" a page
> like this? Because this isn't done very often normally (how often do yo=
u
> add/deactive swap areas) it is my understanding that this is an
> expensive process, which is why we can't really do it, a proposal is to
> instead of having a "vswap" area,

For systems that actually have a disk, it is probably best
to implement compressed caching for swap cache pages.

Vswap is more useful for systems without swap, like the
OLPC laptops...

Lets not confuse the two.

--=20
All Rights Reversed