[PATCH 1/2] dix: Better document Dispatch(), WaitForSomething() and alike

Fernando Carrijo fcarrijo at yahoo.com.br
Thu Jul 29 13:51:08 PDT 2010


Wrote this patch more as an exercise than anything else. And while I
realize that there's a thin line between what people consider benign
and pernicious commenting styles, I tend to believe that in case of
intricate code such as this, we better sin for verbiage than laconism.

Some words I took straight from "Efficiently Scheduling X Clients",
for which I hope not to be sued for plagiarism. Others are my own,
and I'm still not in position to guarantee their correctness.


Reviewed-by: Jamey Sharp <jamey at minilop.net>
Signed-off-by: Fernando Carrijo <fcarrijo at yahoo.com.br>
---
 dix/dispatch.c  |   74 ++++++++++++++++++++++++++---
 os/WaitFor.c    |  141 +++++++++++++++++++++++++++++++++++++++++++------------
 os/connection.c |    4 ++
 3 files changed, 181 insertions(+), 38 deletions(-)

diff --git a/dix/dispatch.c b/dix/dispatch.c
index 0e5aced..6cb54a1 100644
--- a/dix/dispatch.c
+++ b/dix/dispatch.c
@@ -240,6 +240,20 @@ long	    SmartLastPrint;
 void        Dispatch(void);
 void        InitProcVectors(void);
 
+/**
+ * Select the next client to be served.
+ *
+ * The chosen client will be picked up from the array of all clients ready for
+ * input and/or output; and will be the one with highest dynamic priority.
+ *
+ * @param[in] clientReady Array of clients ready for input and/or output.
+ * Actually, the array is not composed of clients, but of the indexes they
+ * occupy in the global variable clients.
+ *
+ * @param[in] nready Number of items in the array.
+ *
+ * @return The index of the chosen client in the global variable clients.
+ */
 static int
 SmartScheduleClient (int *clientReady, int nready)
 {
@@ -251,13 +265,15 @@ SmartScheduleClient (int *clientReady, int nready)
     long	now = SmartScheduleTime;
     long	idle;
 
-    bestPrio = -0x7fffffff;
+    bestPrio = -0x7fffffff; /* FIXME: Replace the magic by INT_MIN */
     bestRobin = 0;
     idle = 2 * SmartScheduleSlice;
+
     for (i = 0; i < nready; i++)
     {
 	client = clientReady[i];
 	pClient = clients[client];
+
 	/* Praise clients which are idle */
 	if ((now - pClient->smart_check_tick) >= idle)
 	{
@@ -266,7 +282,7 @@ SmartScheduleClient (int *clientReady, int nready)
 	}
 	pClient->smart_check_tick = now;
 	
-	/* check priority to select best client */
+	/* Check priority to select best client */
 	robin = (pClient->index - SmartLastIndex[pClient->smart_priority-SMART_MIN_PRIORITY]) & 0xff;
 	if (pClient->smart_priority > bestPrio ||
 	    (pClient->smart_priority == bestPrio && robin > bestRobin))
@@ -287,8 +303,15 @@ SmartScheduleClient (int *clientReady, int nready)
 	SmartLastPrint = now;
     }
 #endif
+
+    /* In the immediately previous step we just chose the best client.
+     * Now we set up the environment with data about this client to be
+     * used the next time SmartScheduleClient() gets called.
+     */
+
     pClient = clients[best];
     SmartLastIndex[bestPrio-SMART_MIN_PRIORITY] = pClient->index;
+
     /*
      * Set current client pointer
      */
@@ -352,6 +375,10 @@ Dispatch(void)
     nextFreeClientID = 1;
     nClients = 0;
 
+    /* clientReady will contain the indexes of all clients which are blocked,
+     * waiting for input or output to proceed. Since we can't divine how many
+     * clients will be, we simply allocate the maximum possible quantity.
+     */
     clientReady = malloc(sizeof(int) * MaxClients);
     if (!clientReady)
 	return;
@@ -365,6 +392,11 @@ Dispatch(void)
 	    FlushIfCriticalOutputPending();
 	}
 
+	/* WaitForSomething() returns the number of clients waiting for input and/or
+	 * output, and also populates clientReady with their indexes in the global
+	 * variable clients. When it returns, those clients have their priorities
+	 * calculated; and that's all the Smart Scheduler needs to do its job.
+	 */
 	nready = WaitForSomething(clientReady);
 
 	if (nready && !SmartScheduleDisable)
@@ -372,11 +404,15 @@ Dispatch(void)
 	    clientReady[0] = SmartScheduleClient (clientReady, nready);
 	    nready = 1;
 	}
-       /***************** 
-	*  Handle events in round robin fashion, doing input between 
-	*  each round 
-	*****************/
 
+       /* Each client is assigned a base priority when it connects to the server.
+        * Requests are executed from the client with highest priority. Many kinds
+        * of events cause changes in priority. Clients with the same priority are
+        * served in round-robin fashion, this keeps even many busy clients all
+        * making progress.
+        *
+        * See: Efficiently Scheduling X Clients, by Keith Packard.
+        */
 	while (!dispatchException && (--nready >= 0))
 	{
 	    client = clients[clientReady[nready]];
@@ -400,16 +436,33 @@ Dispatch(void)
 		    ProcessInputEvents();
 		
 		FlushIfCriticalOutputPending();
+
+		/* Each scheduled client is allowed to execute requests for the
+		 * same interval after which time other clients are given a
+		 * turn.
+		 *
+		 * If the client is still running at the end of the interval,
+		 * the client's priority is reduced by one (but no less than a
+		 * minimum value). If the client hasn't been ready to run for
+		 * some time, priority is increased by one (but no more than the
+		 * initial base value).
+		 *
+		 * These priority adjustments penalize busy applications and
+		 * praise idle ones. This is a simplification of discovering
+		 * precisely how much time a client has used; that would require
+		 * a system call. The cost of system calls is important in
+		 * determining how often each call can be made without a
+		 * significant impact on overall scheduling performance.
+		 */
 		if (!SmartScheduleDisable && 
 		    (SmartScheduleTime - start_tick) >= SmartScheduleSlice)
 		{
-		    /* Penalize clients which consume ticks */
 		    if (client->smart_priority > SMART_MIN_PRIORITY)
 			client->smart_priority--;
 		    break;
 		}
-		/* now, finally, deal with client requests */
 
+		/* Finally deal with client requests. */
 	        result = ReadRequestFromClient(client);
 	        if (result <= 0) 
 	        {
@@ -419,11 +472,13 @@ Dispatch(void)
 	        }
 
 		client->sequence++;
+
 #ifdef XSERVER_DTRACE
 		XSERVER_REQUEST_START(LookupMajorName(MAJOROP), MAJOROP,
 			      ((xReq *)client->requestBuffer)->length,
 			      client->index, client->requestBuffer);
 #endif
+		/* Handle all devilish outcomes of request servicing. */
 		if (result > (maxBigRequestSize << 2))
 		    result = BadLength;
 		else {
@@ -432,6 +487,7 @@ Dispatch(void)
 			result = (* client->requestVector[MAJOROP])(client);
 		    XaceHookAuditEnd(client, result);
 		}
+
 #ifdef XSERVER_DTRACE
 		XSERVER_REQUEST_DONE(LookupMajorName(MAJOROP), MAJOROP,
 			      client->sequence, client->index, result);
@@ -450,7 +506,9 @@ Dispatch(void)
 		    break;
 		}
 	    }
+
 	    FlushAllOutput();
+
 	    client = clients[clientReady[nready]];
 	    if (client)
 		client->smart_stop_tick = SmartScheduleTime;
diff --git a/os/WaitFor.c b/os/WaitFor.c
index e663004..66f67e5 100644
--- a/os/WaitFor.c
+++ b/os/WaitFor.c
@@ -131,14 +131,14 @@ static OsTimerPtr timers = NULL;
  *     Make the server suspend until there is
  *	1. data from clients or
  *	2. input events available or
- *	3. ddx notices something of interest (graphics
- *	   queue ready, etc.) or
+ *	3. ddx notices something of interest (graphics queue ready, etc.) or
  *	4. clients that have buffered replies/events are ready
  *
- *     If the time between INPUT events is
- *     greater than ScreenSaverTime, the display is turned off (or
- *     saved, depending on the hardware).  So, WaitForSomething()
- *     has to handle this also (that's why the select() has a timeout.
+ *     If the time between INPUT events is greater than ScreenSaverTime,
+ *     the display is turned off (or saved, depending on the hardware).
+ *     So, WaitForSomething() has to handle this also; that's why the
+ *     select() has a timeout.
+ *
  *     For more info on ClientsWithInput, see ReadRequestFromClient().
  *     pClientsReady is an array to store ready client->index values into.
  *****************/
@@ -160,17 +160,19 @@ WaitForSomething(int *pClientsReady)
 
     FD_ZERO(&clientsReadable);
 
-    /* We need a while loop here to handle 
-       crashed connections and the screen saver timeout */
     while (1)
     {
-	/* deal with any blocked jobs */
 	if (workQueue)
 	    ProcessWorkQueue();
+
 	if (XFD_ANYSET (&ClientsWithInput))
 	{
 	    if (!SmartScheduleDisable)
 	    {
+                /* If there are any clients with input, and the server is smart
+                 * scheduling, then we have a lot of ground to walk. Let's just
+                 * setup the bag for the journey which lies ahead.
+                 */
 		someReady = TRUE;
 		waittime.tv_sec = 0;
 		waittime.tv_usec = 0;
@@ -178,10 +180,21 @@ WaitForSomething(int *pClientsReady)
 	    }
 	    else
 	    {
+                /* If there are any clients with input, and the server is dumb
+                 * scheduling, then we have little else to do: update the fd_set
+                 * clientsReadable and get out of this humongous while(1) loop.
+                 */
 		XFD_COPYSET (&ClientsWithInput, &clientsReadable);
 		break;
 	    }
 	}
+
+        /* If we reach this place then we know that: <there are no clients with
+         * input> XOR <there are any clients with input AND the server is smart
+         * scheduling>. In this case, we initialize LastSelectMask to contain
+         * all sockets, except for the ones which represent the clients with
+         * input, if any. LastSelectMask will be used by BlockHandler() below.
+         */
 	if (someReady)
 	{
 	    XFD_COPYSET(&AllSockets, &LastSelectMask);
@@ -189,6 +202,11 @@ WaitForSomething(int *pClientsReady)
 	}
 	else
 	{
+        /* Having no clients with input, then we check for expired timers in
+         * the global FIFO of timers. If any, we execute their callbacks. The
+         * variable wt is saved to be used by both BlockHandler() and Select()
+         * below.
+         */
         wt = NULL;
 	if (timers)
         {
@@ -209,18 +227,40 @@ WaitForSomething(int *pClientsReady)
 		wt = &waittime;
 	    }
 	}
+        /* Having no clients with input, we set LastSelectMask to all
+         * sockets. It will be used by BlockHandler() down the road.
+         */
 	XFD_COPYSET(&AllSockets, &LastSelectMask);
 	}
+
+        /* To eliminate the load of both a signal handler and another call to
+         * Select() on the system, the X server temporarily disables the timer
+         * if it receives a signal while suspended within Select(). When the
+         * server awakes again, it restarts the timer.
+         */
 	SmartScheduleStopTimer ();
 
 	BlockHandler((pointer)&wt, (pointer)&LastSelectMask);
+
+        /* If there's output pending to be delivered to any client, then we do
+         * it now, being careful to update AnyClientsWriteBlocked to TRUE and
+         * ClientsWriteBlocked (fd_set of clients to which we can deliver
+         * output) accordingly.
+         */
 	if (NewOutputPending)
 	    FlushAllOutput();
+
 	/* keep this check close to select() call to minimize race */
 	if (dispatchException)
+	{
 	    i = -1;
+	}
 	else if (AnyClientsWriteBlocked)
 	{
+            /* We Select() upon LastSelectMask, which is an fd_set of clients
+             * with input to be read by the server, and clientsWritable, which
+             * is an fd_set of clients to whom the server has output to send.
+             */
 	    XFD_COPYSET(&ClientsWriteBlocked, &clientsWritable);
 	    i = Select (MaxClients, &LastSelectMask, &clientsWritable, NULL, wt);
 	}
@@ -228,13 +268,31 @@ WaitForSomething(int *pClientsReady)
 	{
 	    i = Select (MaxClients, &LastSelectMask, NULL, NULL, wt);
 	}
+
 	selecterr = GetErrno();
+
 	WakeupHandler(i, (pointer)&LastSelectMask);
+
 	SmartScheduleStartTimer ();
-	if (i <= 0) /* An error or timeout occurred */
+
+        /* Right above, if we detected a dispatch exception, i was set to -1.
+         * Otherwise, i received the return of Select(), which is a negative
+         * value if that function returned with error, or 0 in case of a
+         * timeout. We check for those possibilities here:
+         */
+	if (i <= 0)
 	{
+            /* If a dispatch exception happened, just leave WaitForSomething(),
+             * and trust that Dispatch() will know how to handle the situation.
+             * In this case we return nready == 0.
+             */
 	    if (dispatchException)
 		return 0;
+
+            /* If the Select() above returned an error, and if the error is
+             * recoverable, we obviously recover from it. Otherwise, if the
+             * Select() error is unrecoverable, we die in a controlled way.
+             */
 	    if (i < 0) 
 	    {
 		if (selecterr == EBADF)    /* Some client disconnected */
@@ -256,13 +314,20 @@ WaitForSomething(int *pClientsReady)
 	    }
 	    else if (someReady)
 	    {
-		/*
-		 * If no-one else is home, bail quickly
+		/* If we got here, we know for sure that the above Select()
+		 * timed out, and some clients approached the server with input.
+		 * Then, we update the fd_set LastSelectMask and clientsReadable
+		 * with the value of ClientsWithInput, and break the monstrous
+		 * while(1) loop.
 		 */
 		XFD_COPYSET(&ClientsWithInput, &LastSelectMask);
 		XFD_COPYSET(&ClientsWithInput, &clientsReadable);
 		break;
 	    }
+
+            /* If the event queue is not empty, we don't need to wait anymore.
+             * Let's quit WaitForSomething() and process those events.
+             */
 	    if (*checkForInput[0] != *checkForInput[1])
 		return 0;
 
@@ -282,6 +347,11 @@ WaitForSomething(int *pClientsReady)
 	}
 	else
 	{
+            /* If we reached here, it means the Select() above returned > 0.  In
+             * other words: someone has data to be exchanged with us. Let's take
+             * it.
+             */
+
 	    fd_set tmp_set;
 
 	    if (*checkForInput[0] == *checkForInput[1]) {
@@ -299,8 +369,10 @@ WaitForSomething(int *pClientsReady)
                         return 0;
 	        }
 	    }
+
 	    if (someReady)
 		XFD_ORSET(&LastSelectMask, &ClientsWithInput, &LastSelectMask);
+
 	    if (AnyClientsWriteBlocked && XFD_ANYSET (&clientsWritable))
 	    {
 		NewOutputPending = TRUE;
@@ -319,11 +391,12 @@ WaitForSomething(int *pClientsReady)
 
 	    if (XFD_ANYSET (&devicesReadable) || XFD_ANYSET (&clientsReadable))
 		break;
-	    /* check here for DDXes that queue events during Block/Wakeup */
+
+	    /* Check here for DDXes that queue events during Block/Wakeup */
 	    if (*checkForInput[0] != *checkForInput[1])
 		return 0;
 	}
-    }
+    } /* End of the gigantic while(1) loop */
 
     nready = 0;
     if (XFD_ANYSET (&clientsReadable))
@@ -338,9 +411,16 @@ WaitForSomething(int *pClientsReady)
 	        int client_priority, client_index;
 
 		curclient = mffs (clientsReadable.fds_bits[i]) - 1;
-		client_index = /* raphael: modified */
+		client_index =
 			ConnectionTranslation[curclient + (i * (sizeof(fd_mask) * 8))];
 #else
+
+        /* If we got here, probably after breaking the huge while(1) loop,
+         * we know there are clients we should read data from. Then we walk
+         * the clients array, counting the one(s) with higher priority. The
+         * count of them is what we return to Dispatch().
+         */
+
 	int highest_priority = 0;
 	fd_set savedClientsReadable;
 	XFD_COPYSET(&clientsReadable, &savedClientsReadable);
@@ -351,29 +431,26 @@ WaitForSomething(int *pClientsReady)
 	    curclient = XFD_FD(&savedClientsReadable, i);
 	    client_index = GetConnectionTranslation(curclient);
 #endif
-		/*  We implement "strict" priorities.
-		 *  Only the highest priority client is returned to
-		 *  dix.  If multiple clients at the same priority are
-		 *  ready, they are all returned.  This means that an
-		 *  aggressive client could take over the server.
-		 *  This was not considered a big problem because
-		 *  aggressive clients can hose the server in so many 
-		 *  other ways :)
+		/*  We implement "strict" priorities.  Only the highest priority
+		 *  client is returned to dix.  If multiple clients at the same
+		 *  priority are ready, they are all returned.  This means that
+		 *  an aggressive client could take over the server.  This was
+		 *  not considered a big problem because aggressive clients can
+		 *  hose the server in so many other ways :)
 		 */
 		client_priority = clients[client_index]->priority;
 		if (nready == 0 || client_priority > highest_priority)
 		{
-		    /*  Either we found the first client, or we found
-		     *  a client whose priority is greater than all others
-		     *  that have been found so far.  Either way, we want 
-		     *  to initialize the list of clients to contain just
-		     *  this client.
-		     */
+		    /*  Either we found the first client, or we found a client
+		     *  whose priority is greater than all others that have been
+		     *  found so far.  Either way, we want to initialize the
+		     *  list of clients to contain just this client.
+                     */
 		    pClientsReady[0] = client_index;
 		    highest_priority = client_priority;
 		    nready = 1;
 		}
-		/*  the following if makes sure that multiple same-priority 
+		/*  The following if makes sure that multiple same-priority
 		 *  clients get batched together
 		 */
 		else if (client_priority == highest_priority)
@@ -388,6 +465,10 @@ WaitForSomething(int *pClientsReady)
 #endif
 	}
     }
+
+    /* If there aren't any clients readable, i.e. clientsReadable == 0,
+     * then we return 0 to Dispatch.
+     */
     return nready;
 }
 
diff --git a/os/connection.c b/os/connection.c
index c143fb6..f89eac5 100644
--- a/os/connection.c
+++ b/os/connection.c
@@ -1054,6 +1054,10 @@ AddGeneralSocket(int fd)
 	FD_SET(fd, &SavedAllSockets);
 }
 
+/* Adds the device fd to the set of fds representing enabled devices
+ * which will be checked by select() the next time WaitForSomething()
+ * loops over it in search of input data.
+ */
 void
 AddEnabledDevice(int fd)
 {
-- 
1.7.0.4




More information about the xorg-devel mailing list