KQUEUE race condition

[Filip Navara]

Hi,

I think I found a race condition in KQUEUE code, but I'm not sure my 
solution is optimal. If no items are queued, KeRemoveQueue calls 
KeWaitForSingleObject and then after it finishes it acquires dispatcher 
lock and removes a list item. The problem arises when someone calls 
KeRemoveQueue just after the KeWaitForSingleObject call finishes and 
before the dispatcher lock is acquired. In this case he can remove the 
last item in the list and this will cause the first KeRemoveQueue (the 
one that waited) to return garbage. Can anybody think of better solution 
than the attached patch?

Regards,
Filip

Index: ntoskrnl/ke/queue.c
===================================================================
RCS file: /CVS/ReactOS/reactos/ntoskrnl/ke/queue.c,v
retrieving revision 1.11
diff -u -r1.11 queue.c
--- ntoskrnl/ke/queue.c	15 Aug 2004 16:39:05 -0000	1.11
+++ ntoskrnl/ke/queue.c	21 Nov 2004 00:39:52 -0000
@@ -159,27 +159,38 @@
       return ListEntry;
    }

-   //need to wait for it...
-   KeReleaseDispatcherDatabaseLock (OldIrql);
-
-   Status = KeWaitForSingleObject(Queue,
-                                  WrQueue,
-                                  WaitMode,
-                                  TRUE,//Alertable,
-                                  Timeout);
-
-   if (Status == STATUS_TIMEOUT || Status == STATUS_USER_APC)
-   {
-      return (PVOID)Status;
-   }
-   else
+   for (;;)
    {
-      OldIrql = KeAcquireDispatcherDatabaseLock ();
-      ListEntry = RemoveHeadList(&Queue->EntryListHead);
+      //need to wait for it...
       KeReleaseDispatcherDatabaseLock (OldIrql);
-      return ListEntry;
-   }

+      Status = KeWaitForSingleObject(Queue,
+                                     WrQueue,
+                                     WaitMode,
+                                     TRUE,//Alertable,
+                                     Timeout);
+
+      if (Status == STATUS_TIMEOUT || Status == STATUS_USER_APC)
+      {
+         return (PVOID)Status;
+      }
+      else
+      {
+         OldIrql = KeAcquireDispatcherDatabaseLock ();
+
+         /*
+          * Prevent a race condition. If someone calls KeRemoveQueue
+          * just after we end up waiting and before acquiring the spin
+          * lock he can get the last item in the list...
+          */
+         if (IsListEmpty(&Queue->EntryListHead))
+            continue;
+
+         ListEntry = RemoveHeadList(&Queue->EntryListHead);
+         KeReleaseDispatcherDatabaseLock (OldIrql);
+         return ListEntry;
+      }
+   }
 }

[Alex Ionescu]

Hi,

Why not hold the lock all the way through?

Best regards,
Alex Ionescu

Filip Navara wrote:
> Hi,
>
> I think I found a race condition in KQUEUE code, but I'm not sure my 
> solution is optimal. If no items are queued, KeRemoveQueue calls 
> KeWaitForSingleObject and then after it finishes it acquires 
> dispatcher lock and removes a list item. The problem arises when 
> someone calls KeRemoveQueue just after the KeWaitForSingleObject call 
> finishes and before the dispatcher lock is acquired. In this case he 
> can remove the last item in the list and this will cause the first 
> KeRemoveQueue (the one that waited) to return garbage. Can anybody 
> think of better solution than the attached patch?
>
> Regards,
> Filip
> Index: ntoskrnl/ke/queue.c
>
> RCS file: /CVS/ReactOS/reactos/ntoskrnl/ke/queue.c,v
> retrieving revision 1.11
> diff -u -r1.11 queue.c
> --- ntoskrnl/ke/queue.c	15 Aug 2004 16:39:05 -0000	1.11
> +++ ntoskrnl/ke/queue.c	21 Nov 2004 00:39:52 -0000
> @@ -159,27 +159,38 @@
>       return ListEntry;
>    }
> //need to wait for it...
> KeReleaseDispatcherDatabaseLock (OldIrql);
> Status = KeWaitForSingleObject(Queue,
>                              WrQueue,
>                              WaitMode,
>                              TRUE,//Alertable,
>                              Timeout);
> if (Status == STATUS_TIMEOUT || Status == STATUS_USER_APC)
> {
>  return (PVOID)Status;
> }
> else
> for (;;)
> {
>  OldIrql = KeAcquireDispatcherDatabaseLock ();
>  ListEntry = RemoveHeadList(&Queue->EntryListHead);
>  //need to wait for it...
> KeReleaseDispatcherDatabaseLock (OldIrql);
>  return ListEntry;
> }
>  Status = KeWaitForSingleObject(Queue,
>                                 WrQueue,
>                                 WaitMode,
>                                 TRUE,//Alertable,
>                                 Timeout);
>  if (Status == STATUS_TIMEOUT || Status == STATUS_USER_APC)
>  {
>     return (PVOID)Status;
>  }
>  else
>  {
>     OldIrql = KeAcquireDispatcherDatabaseLock ();
>     /*
>      * Prevent a race condition. If someone calls KeRemoveQueue
>      * just after we end up waiting and before acquiring the spin
>      * lock he can get the last item in the list...
>      */
>     if (IsListEmpty(&Queue->EntryListHead))
>        continue;
>     ListEntry = RemoveHeadList(&Queue->EntryListHead);
>     KeReleaseDispatcherDatabaseLock (OldIrql);
>     return ListEntry;
>  }
> }
>
> }
>
> Ros-dev mailing list
> [e-mail]
> http://reactos.com:8080/mailman/listinfo/ros-dev

[Casper Hornstrup]

You cannot wait at DISPATCH_LEVEL.

Casper
> -----Original Message-----
> From: [e-mail] 
> [mailto:[e-mail]] On Behalf Of Alex Ionescu
> Sent: 21. november 2004 02:04
> To: ReactOS Development List
> Subject: Re: [ros-dev] KQUEUE race condition
>
> Hi,
>
> Why not hold the lock all the way through?
>
> Best regards,
> Alex Ionescu

[Filip Navara]

Filip Navara wrote:
> Hi,
>
> I think I found a race condition in KQUEUE code, but I'm not sure my 
> solution is optimal. If no items are queued, KeRemoveQueue calls 
> KeWaitForSingleObject and then after it finishes it acquires 
> dispatcher lock and removes a list item. The problem arises when 
> someone calls KeRemoveQueue just after the KeWaitForSingleObject call 
> finishes and before the dispatcher lock is acquired. In this case he 
> can remove the last item in the list and this will cause the first 
> KeRemoveQueue (the one that waited) to return garbage. Can anybody 
> think of better solution than the attached patch?
>
> Regards,
> Filip

Now with a corrected patch...

Index: ntoskrnl/ke/queue.c
===================================================================
RCS file: /CVS/ReactOS/reactos/ntoskrnl/ke/queue.c,v
retrieving revision 1.11
diff -u -r1.11 queue.c
--- ntoskrnl/ke/queue.c	15 Aug 2004 16:39:05 -0000	1.11
+++ ntoskrnl/ke/queue.c	21 Nov 2004 13:21:52 -0000
@@ -159,27 +159,41 @@
       return ListEntry;
    }

-   //need to wait for it...
-   KeReleaseDispatcherDatabaseLock (OldIrql);
-
-   Status = KeWaitForSingleObject(Queue,
-                                  WrQueue,
-                                  WaitMode,
-                                  TRUE,//Alertable,
-                                  Timeout);
-
-   if (Status == STATUS_TIMEOUT || Status == STATUS_USER_APC)
-   {
-      return (PVOID)Status;
-   }
-   else
+   for (;;)
    {
-      OldIrql = KeAcquireDispatcherDatabaseLock ();
-      ListEntry = RemoveHeadList(&Queue->EntryListHead);
+      //need to wait for it...
       KeReleaseDispatcherDatabaseLock (OldIrql);
-      return ListEntry;
-   }

+      Status = KeWaitForSingleObject(Queue,
+                                     WrQueue,
+                                     WaitMode,
+                                     TRUE,//Alertable,
+                                     Timeout);
+
+      if (Status == STATUS_TIMEOUT || Status == STATUS_USER_APC)
+      {
+         return (PVOID)Status;
+      }
+      else
+      {
+         OldIrql = KeAcquireDispatcherDatabaseLock ();
+
+         /*
+          * Prevent a race condition. If someone calls KeRemoveQueue
+          * just after we end up waiting and before acquiring the spin
+          * lock he can get the last item in the list...
+          */
+         if (IsListEmpty(&Queue->EntryListHead))
+         {
+            Queue->Header.SignalState++;
+            continue;
+         }
+
+         ListEntry = RemoveHeadList(&Queue->EntryListHead);
+         KeReleaseDispatcherDatabaseLock (OldIrql);
+         return ListEntry;
+      }
+   }
 }