Re: [lc-devel] Initial Compressed Cache structure

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

Asbjørn Sannes wrote:
> Nitin Gupta wrote:
>   
>> I've been working on Compressed Cache structure for last few days.
>> Following is the brain dump of all the details required for ccache
>> structure implementation. This doc is a *headache* to follow (poorly
>> written, no diagrams included) -- but I'll later sketch them if
>> required for any part.
>>     
>
> <snip>
>
>   
>> When shrinking, see pages belonging to which inode's mapping are
>> mostly being freed (using simple hooks in shrink_list()-vmscan.c).
>> This shows that a particular inode's (file's) pages are not being used.
>> So, when shrinking, search the radix tree for compressed pages (search
>> based on PAGECACHE_TAG_COMPRESSED tag) and free all the associated
>> chunks. Since a page can only be freed when all the chunks contained
>> within are freed, relocate the remaining chunks in the page to free
>> chunks in other pages and finally free the page.
>>
>>     
> I'm not sure I follow, at least I need some clarification, when do you
> know a page is empty (so that it can be freed) or if you choose a page,
> how do you know what compressed page a chunk belongs to?
>
> PS! I might be confused since I have been looking at storing anonymous
> memory into the compressed area.
>
> Mvh,
> Asbjørn Sannes
>
>
>
>   
You asked:
I) when do you know a page is empty (so that it can be freed)?
II) if you choose a page, how do you know what compressed page a chunk 
belongs to?

For (I):

When a chunk is freed, foll. occurs:
1) It is merged with adjacent free blocks.
2) Check if this merged free chunk spans one or more pages.
3) If chunk spans one or more pages, free those pages.

Foll. gives a rough code for this:

// two helper functions (func1, func2)

// round-off an address to it page's base(start) address
func1 (chunk's start_addr)
{
    base_page_addr = chunk->start_addr & PAGE_MASK;
    return base_page_addr;
}

// get struct page from page's base(start) address
func2 (base addr of page where chunk is located)
{
    pfn = (base_page_addr - PAGE_OFFSET) >> PAGE_OFFSET;
    struct page *page = mem_map + pfn;
    return page;
}


-- let chunk=final merged chunk obtained after step (1)
-- if chunk->size < PAGE_SIZE then skip (2) and (3)
-- while (chunk->size >= PAGE_SIZE) {
   
    calc base_page_addr for this chunk (using func1);
   
    // delta is space used by chunk in page where it is present
    delta = base_page_addr + PAGE_SIZE - chunk->start_addr;
   
    // consider cases of whether chunk starts at page boundary or not

    if (chunk->start_addr & PAGE_MASK) {    // chunk starts at page boundary
        // page is 'struct page' of the page where chunk starts from 
(using func2)
        chunk->start_addr += PAGE_SIZE;
        free_page(page);
    } else {
        if (chunk->size >= delta + PAGE_SIZE) {
            Create New Chunk with start addr as chunk->start_addr and 
size=delta;
            Add above created chunk free list;

            chunk->start_addr += delta+PAGE_SIZE;
            free_page(page->next);    // 'page' is as obtained in above 
case (using func2)
      } else break;

    }

    chunk->size -= PAGE_SIZE;
   
   } // end of while
       


For (II): (if you choose a page, how do you know what compressed page a 
chunk belongs to?)

You can't do that. If you need it, we can simply add index and mapping 
fields of compressed page to struct chunk. But, this will make big 
metadata overhead. Basically, I could not see requirement to know which 
compressed page a chunk belongs to in any of ccache operations (insert, 
delete, shrink. expand).


Cheers,
Nitin