linux-kernel - Re: [PATCH vfs 1/2] lib: implement ptrset

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: <20141118124624.ff0b3140068a090b2860f202@linux-foundation.org>
Date:	Tue, 18 Nov 2014 12:46:24 -0800
From:	Andrew Morton <akpm@...ux-foundation.org>
To:	Tejun Heo <tj@...nel.org>
Cc:	Jens Axboe <axboe@...nel.dk>,
	Alexander Viro <viro@...iv.linux.org.uk>,
	Christoph Hellwig <hch@...radead.org>,
	linux-fsdevel@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH vfs 1/2] lib: implement ptrset

On Fri, 14 Nov 2014 08:12:02 -0500 Tejun Heo <tj@...nel.org> wrote:

> Hello, Andrew.
> 
> On Thu, Nov 13, 2014 at 02:40:41PM -0800, Andrew Morton wrote:
> > In that case tjpointer_add() would need to do a kmalloc() for each inode
> > which is added to the bdev/cdev, just as ptrset_add() is doing.
> > 
> > That might require a nasty preload thing.  But really, for just two
> > known callers it would be better to require the caller to create the
> > storage.
> > 
> > 
> > 	struct tjpointer *new_tpj;
> > 
> > 	new_tpj = kmalloc(...);
> > 	lock();
> > 	tjpointer_add(&my_tjp_list, new_tjp, my_pointer);
> > 	unlock();
> > 
> > Basically what I'm saying is nuke the rbtree and use lists.
> 
> Hah?  Then, each removal would be O(N) where N is the number of total
> block devices and there are cases where massive number of block
> devices exist and many are added / removed back-to-back.  I don't
> think making those operations O(N^2) is a good idea.
> 

bdev_evict_inode() walks all the inodes attached to the bdev and
unlinks them from the bdev.  That can be done with
list_for_each_safe(), just as it is (effectively) in current mainline.

IOW, all we need to do is to remove the list_head from struct inode and
create a new, separately allocated { struct list_head l; void *inode }
to point at the inode.  IOW, simply convert the intrusive list to a
nonintrusive list.


This is proving a painful way of extracting a changelog :( Perhaps I'm
still not getting it and you should have another go, this time
explaining the reasoning behind the design choices.
--
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/