[PATCH v2] ipc: Fix race condition in ipc_idr_alloc()

[PATCH v2] ipc: Fix race condition in ipc_idr_alloc()

[Waiman Long]

In ipc_idr_alloc(), the sequence number of the kern_ipc_perm object
was updated before calling idr_alloc(). Thus the ipc_checkid() call
would fail for any previously allocated IPC id.  That gets changed
recently in order to conserve the sequence number space. That can
lead to a possible race condition where another thread may have called
ipc_obtain_object_check() concurrently with a recently deleted IPC id.
If idr_alloc() function happens to allocate the deleted index value,
that thread will incorrectly get a handle to the new IPC id.

However, we don't know if we should increment seq before the index value
is allocated and compared with the previously allocated index value. To
solve this dilemma, we will always put a new sequence number into the
kern_ipc_perm object before calling idr_alloc(). If it happens that the
sequence number don't need to be changed, we write back the right value
afterward. This will ensure that a concurrent ipc_obtain_object_check()
will not incorrectly match a deleted IPC id to to a new one.

This is actually no different from what ipc_idr_alloc() used to
be. The new IPC id is no danger of being incorrectly rejected as the
kern_ipc_perm object will have the right seq value by the time the new
id is returned.

v2: Update commit log and code comment.

Reported-by: Manfred Spraul <manfred@colorfullife.com>
Signed-off-by: Waiman Long <longman@redhat.com>
---
 ipc/util.c | 27 ++++++++++++++++++++++++---
 1 file changed, 24 insertions(+), 3 deletions(-)

diff --git a/ipc/util.c b/ipc/util.c
index 78e14acb51a7..631ed4790c83 100644
--- a/ipc/util.c
+++ b/ipc/util.c
@@ -221,15 +221,36 @@ 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 */
+		/*
+		 * It is possible that another thread may have called
+		 * ipc_obtain_object_check() concurrently with a recently
+		 * deleted IPC id (idx|seq). If idr_alloc*() happens to
+		 * allocate this deleted idx value, the other thread may
+		 * incorrectly get a handle to the new IPC id.
+		 *
+		 * To prevent this race condition from happening, we will
+		 * always store a new sequence number into the kern_ipc_perm
+		 * object before calling idr_alloc*(). This is what
+		 * ipc_idr_alloc() used to behave. If we find out that we
+		 * don't need to change seq, we write back the right value
+		 * to the kern_ipc_perm object before returning the new
+		 * IPC id to userspace.
+		 */
+		new->seq = ids->seq + 1;
+		if (new->seq > IPCID_SEQ_MAX)
+			new->seq = 0;
+
 		if (ipc_mni_extended)
 			idx = idr_alloc_cyclic(&ids->ipcs_idr, new, 0, ipc_mni,
 						GFP_NOWAIT);
 		else
 			idx = idr_alloc(&ids->ipcs_idr, new, 0, 0, GFP_NOWAIT);
 
-		if ((idx <= ids->last_idx) && (++ids->seq > IPCID_SEQ_MAX))
-			ids->seq = 0;
-		new->seq = ids->seq;
+		/* Make ids->seq and new->seq stay in sync */
+		if (idx <= ids->last_idx)
+			ids->seq = new->seq;
+		else
+			new->seq = ids->seq;
 		ids->last_idx = idx;
 	} else {
 		new->seq = ipcid_to_seqx(next_id);
-- 
2.18.1

Re: [PATCH v2] ipc: Fix race condition in ipc_idr_alloc()

[Manfred Spraul]

Hello Waiman,

I hate to write such mail, but what do you try to achieve?
Create code that works with 99.999% probability, to ensure that we have 
undebuggable issues?

On 3/11/19 3:53 PM, Waiman Long wrote:
> In ipc_idr_alloc(), the sequence number of the kern_ipc_perm object
> was updated before calling idr_alloc(). Thus the ipc_checkid() call
> would fail for any previously allocated IPC id.  That gets changed
> recently in order to conserve the sequence number space. That can
> lead to a possible race condition where another thread may have called
> ipc_obtain_object_check() concurrently with a recently deleted IPC id.
> If idr_alloc() function happens to allocate the deleted index value,
> that thread will incorrectly get a handle to the new IPC id.
>
> However, we don't know if we should increment seq before the index value
> is allocated and compared with the previously allocated index value. To
> solve this dilemma, we will always put a new sequence number into the
> kern_ipc_perm object before calling idr_alloc(). If it happens that the
> sequence number don't need to be changed, we write back the right value
> afterward. This will ensure that a concurrent ipc_obtain_object_check()
> will not incorrectly match a deleted IPC id to to a new one.
>
> This is actually no different from what ipc_idr_alloc() used to
> be.

This is plain wrong.

ipc_idr_alloc() was carefully written to ensure that everything is fully 
initialized before the idr_alloc().

The patch breaks that, and instead of fixing it properly, you continue.

>   The new IPC id is no danger of being incorrectly rejected as the
> kern_ipc_perm object will have the right seq value by the time the new
> id is returned.

And?

The whole issue of seq numbers is to prevent accidential collisions.

thread 1 calls semctl(0x1234, IPC_RMID);x = semget().

thread 2 calls semop(0x1234,...).

That everything is corrected before the syscall in thread 1 returns is 
nice - but a meaningless statement.

I've noticed that you initialize new->seq to "seq+1", and then reduce it 
again if there was no wrap-around.

That minimizes the probability, but the code a total mess.


> v2: Update commit log and code comment.
>
> Reported-by: Manfred Spraul <manfred@colorfullife.com>
> Signed-off-by: Waiman Long <longman@redhat.com>

At least Fixes: "[PATCH v12 2/3] ipc: Conserve sequence numbers in 
ipcmni_extend mode" is missing.

Mutch better would be if you retract patches 2 and 3 from your series, 
and do it correctly immediately.

> ---
>   ipc/util.c | 27 ++++++++++++++++++++++++---
>   1 file changed, 24 insertions(+), 3 deletions(-)
>
> diff --git a/ipc/util.c b/ipc/util.c
> index 78e14acb51a7..631ed4790c83 100644
> --- a/ipc/util.c
> +++ b/ipc/util.c
> @@ -221,15 +221,36 @@ 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 */
> +		/*
> +		 * It is possible that another thread may have called
> +		 * ipc_obtain_object_check() concurrently with a recently
> +		 * deleted IPC id (idx|seq). If idr_alloc*() happens to
> +		 * allocate this deleted idx value, the other thread may
> +		 * incorrectly get a handle to the new IPC id.
> +		 *
> +		 * To prevent this race condition from happening, we will
> +		 * always store a new sequence number into the kern_ipc_perm
> +		 * object before calling idr_alloc*(). This is what
> +		 * ipc_idr_alloc() used to behave.

I would avoid to describe history in the comments:

 From my understanding, the comments should describe the current situation.

History belongs into the commit description.

>   If we find out that we
> +		 * don't need to change seq, we write back the right value
> +		 * to the kern_ipc_perm object before returning the new
> +		 * IPC id to userspace.
> +		 */
> +		new->seq = ids->seq + 1;
> +		if (new->seq > IPCID_SEQ_MAX)
> +			new->seq = 0;
> +
>   		if (ipc_mni_extended)
>   			idx = idr_alloc_cyclic(&ids->ipcs_idr, new, 0, ipc_mni,
>   						GFP_NOWAIT);
>   		else
>   			idx = idr_alloc(&ids->ipcs_idr, new, 0, 0, GFP_NOWAIT);
>   
> -		if ((idx <= ids->last_idx) && (++ids->seq > IPCID_SEQ_MAX))
> -			ids->seq = 0;
> -		new->seq = ids->seq;
> +		/* Make ids->seq and new->seq stay in sync */
> +		if (idx <= ids->last_idx)
> +			ids->seq = new->seq;
> +		else
> +			new->seq = ids->seq;

For this line, a big comment would be required:

new->seq is now written after idr_alloc().

This is the opposite of what is written in the comments on top of 
ipc_idr_alloc().

So if the patch is applied, the code would contradict the comments -> 
total mess.


@Andrew: From my point of view, patches 2 and 3 from the series are not 
ready for merging.

I would propose to drop them.

--

     Manfred