linux-kernel - Re: ext4 extent status tree LRU locking

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20130614180054.GB1017@thunk.org>
Date:	Fri, 14 Jun 2013 14:00:54 -0400
From:	Theodore Ts'o <tytso@....edu>
To:	Dave Hansen <dave.hansen@...el.com>, linux-ext4@...r.kernel.org,
	LKML <linux-kernel@...r.kernel.org>, Jan kara <jack@...e.cz>
Subject: Re: ext4 extent status tree LRU locking

On Sat, Jun 15, 2013 at 01:00:28AM +0800, Zheng Liu wrote:
> > I have a suggestion for how to address this: Keep a timestamp of when
> > the list last has been sorted in struct ext4_super_info.  When
> > iterating over the list, looking for a candidate inode, if inode's
> > i_touch_when is greater than the last time sorted, skip the inode.  If
> > there are no inodes left in the list, or more than some threshold
> > inodes have been skipped, only then resort the list (and update the
> > timestamp in the ext4_super_info structure).
> > 
> 
> Thanks for your suggestion.  I fully agree with you.  What I concern is
> how to define this threshold.  A fixed value is very simple but too
> inflexible.  If this value is too big, this lru list could never be
> sorted.

In my proposal, if the list is never sorted before, we would
definitely sort the list the first time there is a request to shrink
the number of extent caches.  So the list would always be sorted at
least once.

If an inode gets accessed after the time when the list has been
sorted, then the last_touch time will be greater than the last_sorted
time, right?  And our goal is to use the least recently used inode, so
as long as we know they have been used more recently than the time the
list was sorted, and there are still inodes on the list where the
last_touch time is older than the last_sort time, we don't have a
problem.  So we will evict all of the non-delalloc extent cache items
from that inode, and remove it from the list.

The original reason for having the threshold at all is so that if we
skip a huge number of inodes on the list, this would take a long time.
But thinking about this some more, we don't even need a threshold.
What we do instead is if the the last_touch time is newer than the
last_sort time, we just move the inode to the end of the list.  That
means the end of the list will be unsorted, but that's OK, because the
oldest inodes are still at the beginning of the list.  Once the head
of the list is newer than the last_sorted time, then we know we need
to resort the entire list.

Does that make sense to you?

					- Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/