| Message ID | 1541794292-19425-3-git-send-email-longman@redhat.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | ipc: Increase IPCMNI limit & IPC id generation modes | expand |
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.
On 11/10/2018 02: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. With non-cyclic idr allocation, the cursor will never wraps back to 0. It is to the lowest available integer. I can do that with cyclic idr allocation. Cheers, Longman
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@colorfullife.com> 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@infradead.org: (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@colorfullife.com> --- 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; }
On 2/27/19 9:30 PM, Waiman Long wrote: > On 11/20/2018 02:41 PM, Manfred Spraul wrote: >> From 6bbade73d21884258a995698f21ad3128df8e98a Mon Sep 17 00:00:00 2001 >> From: Manfred Spraul<manfred@colorfullife.com> >> 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 fromwilly@infradead.org: >> >> (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@colorfullife.com> >> --- >> 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. > > I don't think that is true. The IDR code just need to associate a > pointer to the given ID. It is not going to access anything inside. So > we don't need to set the seq number first before calling idr_alloc(). > We must, sorry - there is even a CVE associate to that bug: CVE-2015-7613, https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=b9a532277938798b53178d5a66af6e2915cb27cf The problem is not the IDR code, the problem is that ipc_obtain_object_check() calls ipc_checkid(), and ipc_checkid() accesses ipcp->seq. And since the ipc_checkid() is called before acquiring any locks, everything must be fully initialized before idr_alloc(). >> + */ >> + 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; > > This code has dependence on the internal implementation of the IDR > code. So if the IDR code is changed and the one who does it forgets to > update the IPC code, we may have a problem. Using idr_alloc_cyclic() > for all will likely increase memory footprint which can be a problem > on IoT devices that have little memory. That is the main reason why I > opted to use idr_alloc_cyclic() only when in ipcmni_extend mode which > I am sure won't be activated on systems with little memory. > I know. But IoT devices with little memory will compile out sysv (as it is done by Android). -- Manfred
diff --git a/include/linux/ipc_namespace.h b/include/linux/ipc_namespace.h index 6ab8c1b..7d5f553 100644 --- a/include/linux/ipc_namespace.h +++ b/include/linux/ipc_namespace.h @@ -16,6 +16,7 @@ struct ipc_ids { int in_use; unsigned short seq; + unsigned short deleted; struct rw_semaphore rwsem; struct idr ipcs_idr; int max_idx; diff --git a/ipc/util.c b/ipc/util.c index 07ae117..00000a1 100644 --- a/ipc/util.c +++ b/ipc/util.c @@ -115,6 +115,7 @@ static int __init ipc_init(void) void ipc_init_ids(struct ipc_ids *ids) { ids->in_use = 0; + ids->deleted = false; ids->seq = 0; init_rwsem(&ids->rwsem); rhashtable_init(&ids->key_ht, &ipc_kht_params); @@ -193,6 +194,10 @@ static struct kern_ipc_perm *ipc_findkey(struct ipc_ids *ids, key_t key) * * The caller must own kern_ipc_perm.lock.of the new object. * On error, the function returns a (negative) error code. + * + * To conserve sequence number space, especially with extended ipc_mni, + * the sequence number is incremented only when one or more IDs have been + * removed previously. */ static inline int ipc_idr_alloc(struct ipc_ids *ids, struct kern_ipc_perm *new) { @@ -216,9 +221,13 @@ 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; + if (ids->deleted) { + ids->seq++; + if (ids->seq > IPCID_SEQ_MAX) + ids->seq = 0; + ids->deleted = false; + } + new->seq = ids->seq; idx = idr_alloc(&ids->ipcs_idr, new, 0, 0, GFP_NOWAIT); } else { new->seq = ipcid_to_seqx(next_id); @@ -436,6 +445,7 @@ void ipc_rmid(struct ipc_ids *ids, struct kern_ipc_perm *ipcp) idr_remove(&ids->ipcs_idr, idx); ipc_kht_remove(ids, ipcp); ids->in_use--; + ids->deleted = true; ipcp->deleted = true; if (unlikely(idx == ids->max_idx)) {
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. Signed-off-by: Waiman Long <longman@redhat.com> --- include/linux/ipc_namespace.h | 1 + ipc/util.c | 16 +++++++++++++--- 2 files changed, 14 insertions(+), 3 deletions(-)