ceph-devel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: David Howells <dhowells@redhat.com>
To: linux-cachefs@redhat.com
Cc: dhowells@redhat.com, Jeff Layton <jlayton@redhat.com>,
	David Wysochanski <dwysocha@redhat.com>,
	"Matthew Wilcox (Oracle)" <willy@infradead.org>,
	"J. Bruce Fields" <bfields@fieldses.org>,
	Christoph Hellwig <hch@infradead.org>,
	Dave Chinner <dchinner@redhat.com>,
	Alexander Viro <viro@zeniv.linux.org.uk>,
	linux-afs@lists.infradead.org, linux-nfs@vger.kernel.org,
	linux-cifs@vger.kernel.org, ceph-devel@vger.kernel.org,
	v9fs-developer@lists.sourceforge.net,
	linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: fscache: Redesigning the on-disk cache - LRU handling
Date: Thu, 04 Mar 2021 13:47:04 +0000	[thread overview]
Message-ID: <2973223.1614865624@warthog.procyon.org.uk> (raw)
In-Reply-To: <2653261.1614813611@warthog.procyon.org.uk>

David Howells <dhowells@redhat.com> wrote:

> 
>  (3) OpenAFS-style format.  One index file to look up {file_key,block#} and an
>      array of data files, each holding one block (e.g. a 256KiB-aligned chunk
>      of a file).  Each index entry has valid start/end offsets for easy
>      truncation.
> 
>      The index has a hash to facilitate the lookup and an LRU that allows a
>      block to be recycled at any time.

The LRU would probably have to be a doubly-linked list so that entries can be
removed from it easily.  This means typically touching two other entries,
which might not be in the same page; further, if the entry is being freed,
we'd need to excise it from the hash chain also, necessitating touching maybe
two more entries - which might also be in different pages.

Maybe the LRU idea plus a free block bitmap could be combined, however.

 (1) Say that there's a bit-pair map, with one bit pair per block.  The pair
     is set to 0 when the block is free.  When the block is accessed, the pair
     is set to 3.

 (2) When we run out of free blocks (ie. pairs that are zero), we decrement
     all the pairs and then look again.

 (3) Excision from the old hash chain would need to be done at allocation,
     though it does give a block whose usage has been reduced to 0 the chance
     to be resurrected.

Possible variations on the theme could be:

 (*) Set the pair to 2, not 3 when accessed.  Set the block to 3 to pin it;
     the process of decrementing all the pairs would leave it at 3.

 (*) Rather than decrementing all pairs at once, have a rotating window that
     does a part of the map at once.

 (*) If a round of decrementing doesn't reduce any pairs to zero, reject a
     request for space.

This would also work for a file index.

David


  reply	other threads:[~2021-03-04 13:49 UTC|newest]

Thread overview: 13+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-03-03 23:20 fscache: Redesigning the on-disk cache David Howells
2021-03-04 13:47 ` David Howells [this message]
2021-03-05  9:46 ` Amir Goldstein
2021-03-08  9:13 ` David Howells
2021-03-08 10:35   ` Amir Goldstein
2021-03-08 11:28   ` Metadata writtenback notification? -- was " David Howells
2021-03-08 22:32     ` Dave Chinner
2021-03-08 23:20       ` Matthew Wilcox
2021-03-09 11:27     ` David Howells
2021-03-08 18:54   ` J. Bruce Fields
2021-03-08 19:08   ` David Howells
2021-03-08 21:55   ` Dave Chinner
2021-03-09  9:21   ` David Howells

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=2973223.1614865624@warthog.procyon.org.uk \
    --to=dhowells@redhat.com \
    --cc=bfields@fieldses.org \
    --cc=ceph-devel@vger.kernel.org \
    --cc=dchinner@redhat.com \
    --cc=dwysocha@redhat.com \
    --cc=hch@infradead.org \
    --cc=jlayton@redhat.com \
    --cc=linux-afs@lists.infradead.org \
    --cc=linux-cachefs@redhat.com \
    --cc=linux-cifs@vger.kernel.org \
    --cc=linux-fsdevel@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-nfs@vger.kernel.org \
    --cc=v9fs-developer@lists.sourceforge.net \
    --cc=viro@zeniv.linux.org.uk \
    --cc=willy@infradead.org \
    --subject='Re: fscache: Redesigning the on-disk cache - LRU handling' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).