Messages in this thread | | | Date | Wed, 11 Jan 2012 23:59:25 +0400 | From | Cyrill Gorcunov <> | 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@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |