>From fb429c58c113d6a2d38324644239e08b103d6c37 Mon Sep 17 00:00:00 2001 From: Fernando Carrijo <[email protected]> Date: Wed, 4 Aug 2010 23:34:24 -0300 Subject: [PATCH 1/2] dix: Better document Dispatch, WaitForSomething and friends
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. Reviewed-by: Jamey Sharp <[email protected]> Reviewed-by: Tiago Vignatti <[email protected]> Signed-off-by: Fernando Carrijo <[email protected]> --- 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..a1d5cfc 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 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
_______________________________________________ [email protected]: X.Org development Archives: http://lists.x.org/archives/xorg-devel Info: http://lists.x.org/mailman/listinfo/xorg-devel
