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  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]
Date:   Thu, 17 Jun 2021 10:22:47 +0200
From:   Jan Kara <jack@...e.cz>
To:     Andreas Dilger <adilger@...ger.ca>
Cc:     Jan Kara <jack@...e.cz>, Ted Tso <tytso@....edu>,
        linux-ext4@...r.kernel.org
Subject: Re: [PATCH 3/4] ext4: Speedup ext4 orphan inode handling

On Thu 17-06-21 01:44:13, Andreas Dilger wrote:
> On Jun 16, 2021, at 4:56 AM, Jan Kara <jack@...e.cz> wrote:
> > 
> > Ext4 orphan inode handling is a bottleneck for workloads which heavily
> > truncate / unlink small files since it contends on the global
> > s_orphan_mutex lock (and generally it's difficult to improve scalability
> > of the ondisk linked list of orphaned inodes).
> > 
> > This patch implements new way of handling orphan inodes. Instead of
> > linking orphaned inode into a linked list, we store it's inode number in
> > a new special file which we call "orphan file". Currently we still
> > protect the orphan file with a spinlock for simplicity but even in this
> > setting we can substantially reduce the length of the critical section
> > and thus speedup some workloads.
> 
> Is it a single spinlock for the whole file?  Did you consider using
> a per-page lock or grouplock?  With a page in the orphan file for each
> CPU core, it would basically be lockless.

See the next patch :) I've made this one simple in terms of locking:

a) to be able to evaluate how global spinlock performs
b) to make code simpler for review

> > +static int ext4_orphan_file_add(handle_t *handle, struct inode *inode)
> > +{
> > 	spin_lock(&oi->of_lock);
> > +	for (i = 0; i < oi->of_blocks && !oi->of_binfo[i].ob_free_entries; i++);
> > +	if (i == oi->of_blocks) {
> > +		spin_unlock(&oi->of_lock);
> > +		/*
> > +		 * For now we don't grow or shrink orphan file. We just use
> > +		 * whatever was allocated at mke2fs time. The additional
> > +		 * credits we would have to reserve for each orphan inode
> > +		 * operation just don't seem worth it.
> > +		 */
> > +		return -ENOSPC;
> > +	}
> > +	oi->of_binfo[i].ob_free_entries--;
> > +	spin_unlock(&oi->of_lock);
> 
> How do we know how large to make the orphan file at mkfs time?  What if it
> becomes full during use?  It seems like reserving a fixed number of blocks
> will invariably be incorrect for the actual workload on the filesystem.

If orphan file gets full (too many orphaned inodes at this moment), we will
just fallback to using the good old orphan list. So only performance will
suffer.

In terms of number of blocks, for reasonably large filesystems we reserve
512 4k blocks for orphan file so that allows for 523776 orphaned inodes.
Sure it's possible to exhaust it but frankly I don't find it likely so I'm
not sure dynamic sizing is worth the hassle.

> > @@ -49,6 +95,16 @@ int ext4_orphan_add(handle_t *handle, struct inode *inode)
> > 	ASSERT((S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) ||
> > 		  S_ISLNK(inode->i_mode)) || inode->i_nlink == 0);
> > 
> > +	if (sbi->s_orphan_info.of_blocks) {
> > +		err = ext4_orphan_file_add(handle, inode);
> > +		/*
> > +		 * Fallback to normal orphan list of orphan file is
> > +		 * out of space
> > +		 */
> > +		if (err != -ENOSPC)
> > +			return err;
> > +	}
> 
> This could schedule a task on a workqueue to allocate a few more blocks?
> That could easily reserve more credits for this action, without making
> the common case more expensive.  Even if it isn't used with the current
> mount, it would be available for the next mount (which presumably would
> also need additional blocks).
> 
> Whether it is worth the complexity to make this fully dynamic, at least
> it would auto-tune for the workload placed on this filesystem, and would
> not initially be worse than the old single-linked list.

Adding more blocks would not be that hard as you say but if we are growing
a file there may be need to make it shorter as well (as e.g. shortlived
peak in number of orphaned inodes could have accumulated bazilion blocks
for orphan file) and that will be a bit more tricky. It can be done but I
don't think it's worth the complexity...

Thanks for the review!
								Honza
-- 
Jan Kara <jack@...e.com>
SUSE Labs, CR

Powered by blists - more mailing lists