dix: Use list for ready clients

This converts the dispatch loop into using a list of ready clients
instead of an array. This changes the WaitForSomething API so that it
notifies DIX when a client becomes ready to read, instead of returning
the set of ready clients.

Signed-off-by: Keith Packard <keithp@keithp.com>
Reviewed-by: Adam Jackson <ajax@redhat.com>

6 files changed, 118 insertions, 55 deletions

diff --git a/dix/dispatch.c b/dix/dispatch.c
index 7eb200dc4..3b9600e27 100644
--- a/dix/dispatch.c
+++ b/dix/dispatch.c
@@ -240,21 +240,76 @@ long SmartLastPrint;
 
 void Dispatch(void);
 
-static int
-SmartScheduleClient(int *clientReady, int nready)
+static struct xorg_list ready_clients;
+static struct xorg_list saved_ready_clients;
+
+static void
+init_client_ready(void)
+{
+    xorg_list_init(&ready_clients);
+    xorg_list_init(&saved_ready_clients);
+}
+
+Bool
+clients_are_ready(void)
+{
+    return !xorg_list_is_empty(&ready_clients);
+}
+
+/* Client has requests queued or data on the network */
+void
+mark_client_ready(ClientPtr client)
+{
+    if (xorg_list_is_empty(&client->ready))
+        xorg_list_append(&client->ready, &ready_clients);
+}
+
+/* Client has no requests queued and no data on network */
+void
+mark_client_not_ready(ClientPtr client)
+{
+    xorg_list_del(&client->ready);
+}
+
+static void
+mark_client_grab(ClientPtr grab)
+{
+    ClientPtr   client, tmp;
+
+    xorg_list_for_each_entry_safe(client, tmp, &ready_clients, ready) {
+        if (client != grab) {
+            xorg_list_del(&client->ready);
+            xorg_list_append(&client->ready, &saved_ready_clients);
+        }
+    }
+}
+
+static void
+mark_client_ungrab(void)
+{
+    ClientPtr   client, tmp;
+
+    xorg_list_for_each_entry_safe(client, tmp, &saved_ready_clients, ready) {
+        xorg_list_del(&client->ready);
+        xorg_list_append(&client->ready, &ready_clients);
+    }
+}
+
+static ClientPtr
+SmartScheduleClient(void)
 {
-    int i;
-    int client;
     ClientPtr pClient, best = NULL;
     int bestRobin, robin;
     long now = SmartScheduleTime;
     long idle;
+    int nready = 0;
 
     bestRobin = 0;
     idle = 2 * SmartScheduleSlice;
-    for (i = 0; i < nready; i++) {
-        client = clientReady[i];
-        pClient = clients[client];
+
+    xorg_list_for_each_entry(pClient, &ready_clients, ready) {
+        nready++;
+
         /* Praise clients which haven't run in a while */
         if ((now - pClient->smart_stop_tick) >= idle) {
             if (pClient->smart_priority < 0)
@@ -279,12 +334,12 @@ SmartScheduleClient(int *clientReady, int nready)
         }
 #ifdef SMART_DEBUG
         if ((now - SmartLastPrint) >= 5000)
-            fprintf(stderr, " %2d: %3d", client, pClient->smart_priority);
+            fprintf(stderr, " %2d: %3d", pClient->index, pClient->smart_priority);
 #endif
     }
 #ifdef SMART_DEBUG
     if ((now - SmartLastPrint) >= 5000) {
-        fprintf(stderr, " use %2d\n", best);
+        fprintf(stderr, " use %2d\n", best->index);
         SmartLastPrint = now;
     }
 #endif
@@ -292,9 +347,9 @@ SmartScheduleClient(int *clientReady, int nready)
     /*
      * Set current client pointer
      */
-    if (SmartLastClient != pClient) {
-        pClient->smart_start_tick = now;
-        SmartLastClient = pClient;
+    if (SmartLastClient != best) {
+        best->smart_start_tick = now;
+        SmartLastClient = best;
     }
     /*
      * Adjust slice
@@ -313,7 +368,7 @@ SmartScheduleClient(int *clientReady, int nready)
     else {
         SmartScheduleSlice = SmartScheduleInterval;
     }
-    return best->index;
+    return best;
 }
 
 void
@@ -336,44 +391,34 @@ DisableLimitedSchedulingLatency(void)
 void
 Dispatch(void)
 {
-    int *clientReady;           /* array of request ready clients */
     int result;
     ClientPtr client;
-    int nready;
     HWEventQueuePtr *icheck = checkForInput;
     long start_tick;
 
     nextFreeClientID = 1;
     nClients = 0;
 
-    clientReady = xallocarray(MaxClients, sizeof(int));
-    if (!clientReady)
-        return;
-
     SmartScheduleSlice = SmartScheduleInterval;
+    init_client_ready();
+
     while (!dispatchException) {
         if (*icheck[0] != *icheck[1]) {
             ProcessInputEvents();
             FlushIfCriticalOutputPending();
         }
 
-        nready = WaitForSomething(clientReady);
+        if (!WaitForSomething(clients_are_ready()))
+            continue;
 
-        if (nready) {
-            clientReady[0] = SmartScheduleClient(clientReady, nready);
-            nready = 1;
-        }
        /*****************
 	*  Handle events in round robin fashion, doing input between
 	*  each round
 	*****************/
 
-        while (!dispatchException && (--nready >= 0)) {
-            client = clients[clientReady[nready]];
-            if (!client) {
-                /* KillClient can cause this to happen */
-                continue;
-            }
+        if (!dispatchException && clients_are_ready()) {
+            client = SmartScheduleClient();
+
             isItTimeToYield = FALSE;
 
             start_tick = SmartScheduleTime;
@@ -445,8 +490,7 @@ Dispatch(void)
                 }
             }
             FlushAllOutput();
-            client = clients[clientReady[nready]];
-            if (client)
+            if (client == SmartLastClient)
                 client->smart_stop_tick = SmartScheduleTime;
         }
         dispatchException &= ~DE_PRIORITYCHANGE;
@@ -455,7 +499,6 @@ Dispatch(void)
     ddxBeforeReset();
 #endif
     KillAllClients();
-    free(clientReady);
     dispatchException &= ~DE_RESET;
     SmartScheduleLatencyLimited = 0;
     ResetOsBuffers();
@@ -1055,6 +1098,7 @@ ProcGrabServer(ClientPtr client)
         return rc;
     grabState = GrabActive;
     grabClient = client;
+    mark_client_grab(client);
 
     if (ServerGrabCallback) {
         ServerGrabInfoRec grabinfo;
@@ -1074,6 +1118,7 @@ UngrabServer(ClientPtr client)
 
     grabState = GrabNone;
     ListenToAllClients();
+    mark_client_ungrab();
     for (i = mskcnt; --i >= 0 && !grabWaiters[i];);
     if (i >= 0) {
         i <<= 5;
@@ -3365,6 +3410,7 @@ CloseDownClient(ClientPtr client)
         if (grabState != GrabNone && grabClient == client) {
             UngrabServer(client);
         }
+        mark_client_not_ready(client);
         BITCLEAR(grabWaiters, client->index);
         DeleteClientFromAnySelections(client);
         ReleaseActiveGrabs(client);
@@ -3454,6 +3500,7 @@ void
 InitClient(ClientPtr client, int i, void *ospriv)
 {
     client->index = i;
+    xorg_list_init(&client->ready);
     client->clientAsMask = ((Mask) i) << CLIENTOFFSET;
     client->closeDownMode = i ? DestroyAll : RetainPermanent;
     client->requestVector = InitialVector;
diff --git a/include/dixstruct.h b/include/dixstruct.h
index 8e70ae1fa..1f383497c 100644
--- a/include/dixstruct.h
+++ b/include/dixstruct.h
@@ -76,6 +76,7 @@ typedef struct _saveSet {
 typedef struct _Client {
     void *requestBuffer;
     void *osPrivate;             /* for OS layer, including scheduler */
+    struct xorg_list ready;      /* List of clients ready to run */
     Mask clientAsMask;
     short index;
     unsigned char majorOp, minorOp;
@@ -138,6 +139,20 @@ extern Bool SmartScheduleSignalEnable;
 extern void SmartScheduleStartTimer(void);
 extern void SmartScheduleStopTimer(void);
 
+/* Client has requests queued or data on the network */
+void mark_client_ready(ClientPtr client);
+
+/* Client has no requests queued and no data on network */
+void mark_client_not_ready(ClientPtr client);
+
+static inline Bool client_is_ready(ClientPtr client)
+{
+    return !xorg_list_is_empty(&client->ready);
+}
+
+Bool
+clients_are_ready(void);
+
 #define SMART_MAX_PRIORITY  (20)
 #define SMART_MIN_PRIORITY  (-20)
 
diff --git a/include/os.h b/include/os.h
index b0a068ed2..765562c80 100644
--- a/include/os.h
+++ b/include/os.h
@@ -96,8 +96,7 @@ extern _X_EXPORT void (*OsVendorVErrorFProc) (const char *,
 _X_ATTRIBUTE_PRINTF(1, 0);
 #endif
 
-extern _X_EXPORT int WaitForSomething(int *     /*pClientsReady */
-    );
+extern _X_EXPORT Bool WaitForSomething(Bool clients_are_ready);
 
 extern _X_EXPORT int ReadRequestFromClient(ClientPtr /*client */ );
 
diff --git a/os/WaitFor.c b/os/WaitFor.c
index 7bdd39987..8164c30dd 100644
--- a/os/WaitFor.c
+++ b/os/WaitFor.c
@@ -142,8 +142,8 @@ static volatile OsTimerPtr timers = NULL;
  *     pClientsReady is an array to store ready client->index values into.
  *****************/
 
-int
-WaitForSomething(int *pClientsReady)
+Bool
+WaitForSomething(Bool are_ready)
 {
     int i;
     struct timeval waittime, *wt;
@@ -154,7 +154,6 @@ WaitForSomething(int *pClientsReady)
     int selecterr;
     static int nready;
     CARD32 now = 0;
-    Bool someReady = FALSE;
     Bool someNotifyWriteReady = FALSE;
 
     FD_ZERO(&clientsReadable);
@@ -174,11 +173,9 @@ WaitForSomething(int *pClientsReady)
         /* deal with any blocked jobs */
         if (workQueue)
             ProcessWorkQueue();
-        if (XFD_ANYSET(&ClientsWithInput)) {
+
+        if (are_ready) {
             timeout = 0;
-            someReady = TRUE;
-        }
-        if (someReady) {
             XFD_COPYSET(&AllSockets, &LastSelectMask);
             XFD_UNSET(&LastSelectMask, &ClientsWithInput);
         }
@@ -227,12 +224,12 @@ WaitForSomething(int *pClientsReady)
         WakeupHandler(i);
         if (i <= 0) {           /* An error or timeout occurred */
             if (dispatchException)
-                return 0;
+                return FALSE;
             if (i < 0) {
                 if (selecterr == EBADF) {       /* Some client disconnected */
                     CheckConnections();
                     if (!XFD_ANYSET(&AllClients))
-                        return 0;
+                        return FALSE;
                 }
                 else if (selecterr == EINVAL) {
                     FatalError("WaitForSomething(): select: %s\n",
@@ -243,7 +240,7 @@ WaitForSomething(int *pClientsReady)
                            strerror(selecterr));
                 }
             }
-            else if (someReady) {
+            else if (are_ready) {
                 /*
                  * If no-one else is home, bail quickly
                  */
@@ -252,7 +249,7 @@ WaitForSomething(int *pClientsReady)
                 break;
             }
             if (*checkForInput[0] != *checkForInput[1])
-                return 0;
+                return FALSE;
 
             if (timers) {
                 int expired = 0;
@@ -267,7 +264,7 @@ WaitForSomething(int *pClientsReady)
                         DoTimer(timers, now, &timers);
                     OsReleaseSignals();
 
-                    return 0;
+                    return FALSE;
                 }
             }
         }
@@ -288,12 +285,11 @@ WaitForSomething(int *pClientsReady)
                             DoTimer(timers, now, &timers);
                         OsReleaseSignals();
 
-                        return 0;
+                        return FALSE;
                     }
                 }
             }
-            if (someReady)
-                XFD_ORSET(&LastSelectMask, &ClientsWithInput, &LastSelectMask);
+
             if (AnyWritesPending) {
                 XFD_ANDSET(&clientsWritable, &LastSelectWriteMask, &ClientsWriteBlocked);
                 if (XFD_ANYSET(&clientsWritable)) {
@@ -316,11 +312,12 @@ WaitForSomething(int *pClientsReady)
             if (XFD_ANYSET(&tmp_set) || someNotifyWriteReady)
                 HandleNotifyFds();
 
-            if (XFD_ANYSET(&clientsReadable))
+            if (are_ready || XFD_ANYSET(&clientsReadable))
                 break;
+
             /* check here for DDXes that queue events during Block/Wakeup */
             if (*checkForInput[0] != *checkForInput[1])
-                return 0;
+                return FALSE;
         }
     }
 
@@ -345,7 +342,8 @@ WaitForSomething(int *pClientsReady)
             curclient = XFD_FD(&savedClientsReadable, i);
             client_index = GetConnectionTranslation(curclient);
 #endif
-            pClientsReady[nready++] = client_index;
+            nready++;
+            mark_client_ready(clients[client_index]);
 #ifndef WIN32
             clientsReadable.fds_bits[i] &= ~(((fd_mask) 1L) << curclient);
         }
@@ -358,7 +356,7 @@ WaitForSomething(int *pClientsReady)
     if (nready)
         SmartScheduleStartTimer();
 
-    return nready;
+    return TRUE;
 }
 
 void
diff --git a/os/connection.c b/os/connection.c
index ad949c90e..9e0c97616 100644
--- a/os/connection.c
+++ b/os/connection.c
@@ -1232,6 +1232,7 @@ IgnoreClient(ClientPtr client)
         return;
 
     isItTimeToYield = TRUE;
+    mark_client_not_ready(client);
     if (!GrabInProgress || FD_ISSET(connection, &AllClients)) {
         if (FD_ISSET(connection, &ClientsWithInput))
             FD_SET(connection, &IgnoredClientsWithInput);
@@ -1273,8 +1274,10 @@ AttendClient(ClientPtr client)
         FD_SET(connection, &AllClients);
         FD_SET(connection, &AllSockets);
         FD_SET(connection, &LastSelectMask);
-        if (FD_ISSET(connection, &IgnoredClientsWithInput))
+        if (FD_ISSET(connection, &IgnoredClientsWithInput)) {
             FD_SET(connection, &ClientsWithInput);
+            mark_client_ready(client);
+        }
     }
     else {
         FD_SET(connection, &SavedAllClients);
diff --git a/os/io.c b/os/io.c
index 596deff47..36527dc56 100644
--- a/os/io.c
+++ b/os/io.c
@@ -354,6 +354,7 @@ ReadRequestFromClient(ClientPtr client)
                                  oci->size - oci->bufcnt);
         if (result <= 0) {
             if ((result < 0) && ETEST(errno)) {
+                mark_client_not_ready(client);
 #if defined(SVR4) && defined(__i386__) && !defined(__sun)
                 if (0)
 #endif