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