Hi Matthew,
On 11/10/18 8:41 AM, Matthew Wilcox wrote:
On Fri, Nov 09, 2018 at 03:11:31PM -0500, Waiman Long wrote:
The mixing in of a sequence number into the IPC IDs is probably to
avoid ID reuse in userspace as much as possible. With ipcmni_extend
mode, the number of usable sequence numbers is greatly reduced leading
to higher chance of ID reuse.
To address this issue, we need to conserve the sequence number space
as much as possible. Right now, the sequence number is incremented
for every new ID created. In reality, we only need to increment the
sequence number when one or more IDs have been removed previously to
make sure that those IDs will not be reused when a new one is built.
This is being done irrespective of the ipcmni mode.
That's not what I said. Increment the sequence ID when the cursor wraps,
not when there's been a deletion.
Something like the attached patch?
Unfortunately, idr_alloc_cyclic cannot be used, this creates some
copy&paste from lib/idr.c to ipc/util.c
[as potential replacement for patch 2 and 3 from the series]
--
Manfred
>From 6bbade73d21884258a995698f21ad3128df8e98a Mon Sep 17 00:00:00 2001
From: Manfred Spraul <manfred@xxxxxxxxxxxxxxxx>
Date: Sat, 29 Sep 2018 15:43:28 +0200
Subject: [PATCH 2/2] ipc/util.c: use idr_alloc_cyclic() for ipc allocations
A bit related to the patch that increases IPC_MNI, and
partially based on the mail from willy@xxxxxxxxxxxxx:
(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, perform a cyclic
allocation, and increase the sequence number only when there is
a wrap-around. Unfortunately, idr_alloc_cyclic cannot be used,
because the sequence number must be increased when a wrap-around
occurs.
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.
Signed-off-by: Manfred Spraul <manfred@xxxxxxxxxxxxxxxx>
---
ipc/util.c | 48 ++++++++++++++++++++++++++++++++++++++++++++----
1 file changed, 44 insertions(+), 4 deletions(-)
diff --git a/ipc/util.c b/ipc/util.c
index 07ae117ccdc0..fa7b8fa7a14c 100644
--- a/ipc/util.c
+++ b/ipc/util.c
@@ -216,10 +216,49 @@ 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 */
- new->seq = ids->seq++;
- if (ids->seq > IPCID_SEQ_MAX)
- ids->seq = 0;
- idx = idr_alloc(&ids->ipcs_idr, new, 0, 0, GFP_NOWAIT);
+ int idx_max;
+
+ /*
+ * If a user space visible id is reused, then this creates a
+ * risk for data corruption. To reduce the probability that
+ * a number is reused, three approaches are used:
+ * 1) the idr index is allocated cyclically.
+ * 2) the use space id is build by concatenating the
+ * internal idr index with a sequence number.
+ * 3) The sequence number is only increased when the index
+ * wraps around.
+ * Note that this code cannot use idr_alloc_cyclic:
+ * new->seq must be set before the entry is inserted in the
+ * idr.
+ */
+ idx_max = ids->in_use*2;
+ if (idx_max < RADIX_TREE_MAP_SIZE)
+ idx_max = RADIX_TREE_MAP_SIZE;
+ if (idx_max > ipc_mni)
+ idx_max = ipc_mni;
+
+ if (ids->ipcs_idr.idr_next <= idx_max) {
+ new->seq = ids->seq;
+ idx = idr_alloc(&ids->ipcs_idr, new,
+ ids->ipcs_idr.idr_next,
+ idx_max, GFP_NOWAIT);
+ }
+
+ if ((idx == -ENOSPC) && (ids->ipcs_idr.idr_next > 0)) {
+ /*
+ * A wrap around occurred.
+ * Increase ids->seq, update new->seq
+ */
+ ids->seq++;
+ if (ids->seq > IPCID_SEQ_MAX)
+ ids->seq = 0;
+ new->seq = ids->seq;
+
+ idx = idr_alloc(&ids->ipcs_idr, new, 0, idx_max,
+ GFP_NOWAIT);
+ }
+ if (idx >= 0)
+ ids->ipcs_idr.idr_next = idx+1;
} else {
new->seq = ipcid_to_seqx(next_id);
idx = idr_alloc(&ids->ipcs_idr, new, ipcid_to_idx(next_id),
@@ -227,6 +266,7 @@ static inline int ipc_idr_alloc(struct ipc_ids *ids, struct kern_ipc_perm *new)
}
if (idx >= 0)
new->id = (new->seq << IPCMNI_SEQ_SHIFT) + idx;
+
return idx;
}
--
2.17.2
