[PATCH 1/2] dix: Better document Dispatch(), WaitForSomething() and alike
Tiago Vignatti
tiago.vignatti at nokia.com
Mon Aug 2 07:52:00 PDT 2010
On Thu, Jul 29, 2010 at 10:51:08PM +0200, ext Fernando Carrijo wrote:
> 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.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
I don't understand this.
> + *
> + * @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.
> + */
maybe we should change AddEnabledDevice to AddInputDevice or something that
says it concerns only input devices.
> void
> AddEnabledDevice(int fd)
> {
Just one commentary on the top of this email that you may want to improve, but
for this patch and for the next one fixing the indentation:
Reviewed-by: Tiago Vignatti <tiago.vignatti at nokia.com>
Cheers,
Tiago
More information about the xorg-devel
mailing list