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