[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