linux-kernel - Re: [RFC] on general object IDs again

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]

Date:	Wed, 11 Jan 2012 23:59:25 +0400
From:	Cyrill Gorcunov <gorcunov@...il.com>
To:	KOSAKI Motohiro <kosaki.motohiro@...il.com>
Cc:	Pavel Emelyanov <xemul@...allels.com>,
	LKML <linux-kernel@...r.kernel.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Kyle Moffett <kyle@...fetthome.net>, Tejun Heo <tj@...nel.org>,
	Glauber Costa <glommer@...allels.com>,
	Andi Kleen <andi@...stfloor.org>,
	Matt Helsley <matthltc@...ibm.com>,
	Pekka Enberg <penberg@...nel.org>,
	Eric Dumazet <eric.dumazet@...il.com>,
	Vasiliy Kulikov <segoon@...nwall.com>,
	Alexey Dobriyan <adobriyan@...il.com>,
	Herbert Xu <herbert@...dor.hengli.com.au>,
	"David S. Miller" <davem@...emloft.net>,
	"Eric W. Biederman" <ebiederm@...ssion.com>,
	Andrey Vagin <avagin@...nvz.org>
Subject: Re: [RFC] on general object IDs again

On Wed, Jan 11, 2012 at 02:29:48PM -0500, KOSAKI Motohiro wrote:
> >> > Then, you only need to compare. not any other calculation. i.e. only
> >> > need id uniqueness.
> >> > And any resource are referenced from tasks. so, can you reuse pid for
> >> > this? example,
> >> > two taska share one mm.
> >> >
> >> > task-a(pid: 100)
> >> >               |-----------------mm
> >> > task-b(pid: 200)
> >> >
> >> >
> >> > gen_obj_id(task-b, GEN_OBJ_ID_VM) return 100. (youngest pid of referenced tasks)
> >>
> >> We can, but determining the youngest pid for an mm struct is O(N) algo.
> >> Having N tasks with N mm_structs getting the sharing picture becomes O(N^2).
> >
> > Yeah, exactly. If not the speed problem we would simply stick
> > with Andrew's proposal as two-id-are-the-same(pid1, pid2)
> > syscall.
> 
> Why O(N^2) is matter? Typical HPC system have mere a few hundred pids.
> so, O(N^2) is not slow. How do you mesure Andrew's proposal?
> 

I consider quadratic approach only as a path where nothing
else can go. So to be fair -- I didn't measure such syscall.

> If you have 1000 pids and each syscall need 10usec,
> 
> 1000 * 1000 * 10 = 10,000,000usec = 10sec. But, important thing is, almost all
> processes don't share fs, mm and other structs. then, if we check
> reference count before task traversal, required time may reduce 1/10x - 1/100x.
> 

Sure thing, until some number of pids this will work (since compare two pointers
is very fast), but I fear eventually we will hit situation were such trade off
beat us. Also note that we do ask not only mm IDs, but ->files, ->signals,
->sysv.undo-list and so on (and who knows what else might be needed
in future). Since there is a hardware support for AES encoding on new
CPUs I think this is significant.

But again, Kosaki, if there some other fast way to retrieve such info,
it should be considered of course.

Technically for us plain kernel pointers would be enough unde root-only
approach but I've been strongly adviced to export such IDs via safe way
to a regular users as well (you could find the former patches from Pavel
in LKML archives).

	Cyrill
--
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/