[PATCH] dix: Better document the functions Dispatch(), WaitForSomething() and alike.

Tiago Vignatti tiago.vignatti at Nokia.com
Thu Jul 29 05:11:14 PDT 2010


On Wed, Jul 28, 2010 at 10:26:34PM +0200, ext Fernando Carrijo wrote:
> Signed-off-by: Fernando Carrijo <fcarrijo at yahoo.com.br>
> ---
> 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 correctness.
> 
> So, if anyone see value in this, please review and apply.
> 
>  dix/dispatch.c  |   54 +++++++++++++++--
>  os/WaitFor.c    |  174 ++++++++++++++++++++++++++++++++++++++++---------------
>  os/connection.c |    4 +
>  3 files changed, 179 insertions(+), 53 deletions(-)
> 
> diff --git a/dix/dispatch.c b/dix/dispatch.c
> index 0e5aced..2ebe822 100644
> --- a/dix/dispatch.c
> +++ b/dix/dispatch.c
> @@ -240,6 +240,14 @@ long           SmartLastPrint;
>  void        Dispatch(void);
>  void        InitProcVectors(void);
> 
> +/* 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.
> + *
> + * nread:
> + *   number of items in the array
> + */

not sure if people really use that but we may want to write with doxygen tags.
You can take a look at dix/events.c for references.


>  static int
>  SmartScheduleClient (int *clientReady, int nready)
>  {
> @@ -251,7 +259,7 @@ SmartScheduleClient (int *clientReady, int nready)
>      long       now = SmartScheduleTime;
>      long       idle;
> 
> -    bestPrio = -0x7fffffff;
> +    bestPrio = -0x7fffffff; /* INT_MIN */

maybe put a "FIXME: change by INT_MIN" would be better?


>      bestRobin = 0;
>      idle = 2 * SmartScheduleSlice;
>      for (i = 0; i < nready; i++)
> @@ -287,6 +295,12 @@ 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;
>      /*
> @@ -352,6 +366,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 devine how many
> +     * clients will be, we simply allocate the maximum possible quantity.
> +     */
>      clientReady = malloc(sizeof(int) * MaxClients);
>      if (!clientReady)
>         return;
> @@ -361,10 +379,20 @@ Dispatch(void)
>      {
>          if (*icheck[0] != *icheck[1])
>         {
> +           /* While dispatching, only two things can be more important than client
> +            * scheduling: processing input events already present in the event queue,
> +            * and flushing to clients any critically-deemed pending data. That's why
> +            * we do this before going into WaitForSomething().
> +            */

last phrase seems superfluous.


>             ProcessInputEvents();
>             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 +400,14 @@ Dispatch(void)
>             clientReady[0] = SmartScheduleClient (clientReady, nready);
>             nready = 1;
>         }
> -       /*****************
> -       *  Handle events in round robin fashion, doing input between
> -       *  each round
> -       *****************/
> 
> +       /* According to the Smart Scheduler's Dynamic Priorities Policy each
                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                              is this on Keith's paper? Add a citation doesn't
                              hurt then.


> +        * client is assigned a base priority when it connects to the server.
> +        * Requests are executed from the client with highest priority. Various
> +        * 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.
> +        */
>         while (!dispatchException && (--nready >= 0))
>         {
>             client = clients[clientReady[nready]];
> @@ -400,10 +431,21 @@ Dispatch(void)
>                     ProcessInputEvents();
> 
>                 FlushIfCriticalOutputPending();
> +
> +               /* 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.

I understood everything until "required a system call". Can you be more
verbose here?


>                 if (!SmartScheduleDisable &&
>                     (SmartScheduleTime - start_tick) >= SmartScheduleSlice)
>                 {
> -                   /* Penalize clients which consume ticks */
>                     if (client->smart_priority > SMART_MIN_PRIORITY)
>                         client->smart_priority--;
>                     break;
> diff --git a/os/WaitFor.c b/os/WaitFor.c
> index e663004..94b19fb 100644
> --- a/os/WaitFor.c
> +++ b/os/WaitFor.c
> @@ -130,15 +130,15 @@ static OsTimerPtr timers = NULL;
>   * WaitForSomething:
>   *     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
> + *     2. input events available

you could leave the "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,38 +202,65 @@ WaitForSomething(int *pClientsReady)
>         }
>         else
>         {
> -        wt = NULL;
> -       if (timers)
> -        {
> -            now = GetTimeInMillis();
> -           timeout = timers->expires - now;
> -            if (timeout > 0 && timeout > timers->delta + 250) {
> -                /* time has rewound.  reset the timers. */
> -                CheckAllTimers();
> +            /* Having no clients with input, then we check for expired timers in
> +             * the FIFO. If there are, we execute their callbacks. The variable
> +             * wt is saved to be used by both BlockHandler() and Select() below.
> +             */
> +            wt = NULL;
> +            if (timers)
> +            {
> +                now = GetTimeInMillis();
> +                timeout = timers->expires - now;
> +                if (timeout > 0 && timeout > timers->delta + 250) {
> +                    /* Time has rewound. Reset the timers. */
> +                    CheckAllTimers();
> +                }
> +
> +                if (timers) {
> +                    timeout = timers->expires - now;
> +                    if (timeout < 0)
> +                        timeout = 0;
> +                    waittime.tv_sec = timeout / MILLI_PER_SECOND;
> +                    waittime.tv_usec = (timeout % MILLI_PER_SECOND) *
> +                                       (1000000 / MILLI_PER_SECOND);
> +                    wt = &waittime;
> +                }
>              }
> 
> -           if (timers) {
> -               timeout = timers->expires - now;
> -               if (timeout < 0)
> -                   timeout = 0;
> -               waittime.tv_sec = timeout / MILLI_PER_SECOND;
> -               waittime.tv_usec = (timeout % MILLI_PER_SECOND) *
> -                                  (1000000 / MILLI_PER_SECOND);
> -               wt = &waittime;
> -           }
> -       }
> -       XFD_COPYSET(&AllSockets, &LastSelectMask);
> +            /* Having no clients with input, we set LastSelectMask to all
> +             * sockets. It will be used by BlockHandler() further down.
> +             */
> +            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()
> +                * timedout, 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 the 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;
> @@ -323,7 +395,7 @@ WaitForSomething(int *pClientsReady)
>             if (*checkForInput[0] != *checkForInput[1])
>                 return 0;
>         }
> -    }
> +    } /* End of the gigantic while(1) loop */
> 
>      nready = 0;
>      if (XFD_ANYSET (&clientsReadable))
> @@ -341,6 +413,13 @@ WaitForSomething(int *pClientsReady)
>                 client_index = /* raphael: modified */
>                         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,24 +430,21 @@ 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;
> @@ -388,6 +464,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
> 

Thanks for doing this, Fernando!

             Tiago


More information about the xorg-devel mailing list