Messages in this thread |  | | Subject | Re: [RFC, PATCH] ipc/util.c: use idr_alloc_cyclic() for ipc allocations | From | Manfred Spraul <> | Date | Wed, 3 Oct 2018 13:37:07 +0200 |
| |
On 10/2/18 8:27 PM, Waiman Long wrote: > On 10/02/2018 12:19 PM, Manfred Spraul wrote: >> A bit related to the patch series that increases IPC_MNI: >> >> (User space) id reuse create the risk of data corruption: >> >> Process A: calls ipc function >> Process A: sleeps just at the beginning of the syscall >> Process B: Frees the ipc object (i.e.: calls ...ctl(IPC_RMID) >> Process B: Creates a new ipc object (i.e.: calls ...get()) >> <If new object and old object have the same id> >> Process A: is woken up, and accesses the new object >> >> To reduce the probability that the new and the old object >> have the same id, the current implementation adds a >> sequence number to the index of the object in the idr tree. >> >> To further reduce the probability for a reuse, switch from >> idr_alloc to idr_alloc_cyclic. >> >> The patch cycles over at least RADIX_TREE_MAP_SIZE, i.e. >> if there is only a small number of objects, the accesses >> continue to be direct. >> >> As an option, this could be made dependent on the extended >> mode: In extended mode, cycle over e.g. at least 16k ids. >> >> Signed-off-by: Manfred Spraul <manfred@colorfullife.com> >> --- >> >> Open questions: >> - Is there a significant performance advantage, especially >> there are many ipc ids? >> - Over how many ids should the code cycle always? >> - Further review remarks? >> >> ipc/util.c | 22 +++++++++++++++++++++- >> 1 file changed, 21 insertions(+), 1 deletion(-) >> >> diff --git a/ipc/util.c b/ipc/util.c >> index 0af05752969f..6f83841f6761 100644 >> --- a/ipc/util.c >> +++ b/ipc/util.c >> @@ -216,10 +216,30 @@ static inline int ipc_idr_alloc(struct ipc_ids *ids, struct kern_ipc_perm *new) >> */ >> >> if (next_id < 0) { /* !CHECKPOINT_RESTORE or next_id is unset */ >> + int idr_max; >> + >> new->seq = ids->seq++; >> if (ids->seq > IPCID_SEQ_MAX) >> ids->seq = 0; >> - idx = idr_alloc(&ids->ipcs_idr, new, 0, 0, GFP_NOWAIT); >> + >> + /* >> + * If a user space visible id is reused, then this creates a >> + * risk for data corruption. To reduce the probability that >> + * a number is reduced, two approaches are used: > reduced -> reused? Of course. > >> + * 1) the idr index is allocated cyclically. >> + * 2) the use space id is build by concatenating the >> + * internal idr index with a sequence number >> + * To avoid that both numbers have the same cycle time, try >> + * to set the size for the cyclic alloc to an odd number. >> + */ >> + idr_max = ids->in_use*2+1; >> + if (idr_max < RADIX_TREE_MAP_SIZE-1) >> + idr_max = RADIX_TREE_MAP_SIZE-1; >> + if (idr_max > IPCMNI) >> + idr_max = IPCMNI; >> + >> + idx = idr_alloc_cyclic(&ids->ipcs_idr, new, 0, idr_max, >> + GFP_NOWAIT); >> } else { >> new->seq = ipcid_to_seqx(next_id); >> idx = idr_alloc(&ids->ipcs_idr, new, ipcid_to_idx(next_id), > > Each of IPC components have their own sysctl parameters limiting the max > number of objects that can be allocated. With cyclic allocation, you > will have to make sure that idr_max is not larger than the corresponding > IPC sysctl parameters. That may require moving the limits to the > corresponding ipc_ids structure so that it can be used in ipc_idr_alloc().
First, I would disagree:
the sysctl limits specify how many objects can exist.
idr_max is the maximum index in the radix tree that can exist. There is a hard limit of IPCMNI, but that's it.
But:
The name is wrong, I will rename the variable to idx_max
> What is the point of comparing idr_max against RADIX_TREE_MAP_SIZE-1? Is > it for performance reason.
Let's assume you have only 1 ipc object, and you alloc/release that object.
At alloc time, ids->in_use is 0 -> idr_max 1 -> every object will end up with idx=0.
This would defeat the whole purpose of using a cyclic alloc.
Thus: cycle over at least 63 ids -> 5 additional bits to avoid collisions.
--
Manfred
|  |