[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