Re: [RFC] on general object IDs again

[Cyrill Gorcunov <gorcunov@gmail.com>]

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