xrdp: speed up bitmap cache lru using linked list

2 files changed, 126 insertions, 65 deletions

diff --git a/xrdp/xrdp_cache.c b/xrdp/xrdp_cache.c
index 3510856d..b637a380 100644
--- a/xrdp/xrdp_cache.c
+++ b/xrdp/xrdp_cache.c
@@ -48,24 +48,22 @@ xrdp_cache_reset_lru(struct xrdp_cache *self)
         lru = &(self->bitmap_lrus[index][0]);
         lru->next = 1;
         lru->prev = -1;
-        lru->cacheid = -1;
         /* middle items */
         for (jndex = 1; jndex < XRDP_MAX_BITMAP_CACHE_IDX - 1; jndex++)
         {
             lru = &(self->bitmap_lrus[index][jndex]);
             lru->next = jndex + 1;
             lru->prev = jndex - 1;
-            lru->cacheid = -1;
         }
         /* last item */
         lru = &(self->bitmap_lrus[index][XRDP_MAX_BITMAP_CACHE_IDX - 1]);
         lru->next = -1;
         lru->prev = XRDP_MAX_BITMAP_CACHE_IDX - 2;
-        lru->cacheid = -1;
 
         self->lru_head[index] = 0;
         self->lru_tail[index] = XRDP_MAX_BITMAP_CACHE_IDX - 1;
 
+        self->lru_reset[index] = 1;
     }
     return 0;
 }
@@ -165,6 +163,16 @@ xrdp_cache_delete(struct xrdp_cache *self)
 
     list_delete(self->xrdp_os_del_list);
 
+    /* free all crc lists */
+    for (i = 0; i < XRDP_MAX_BITMAP_CACHE_ID; i++)
+    {
+        for (j = 0; j < 64 * 1024; j++)
+        {
+            list_delete(self->crc16[i][j]);
+            self->crc16[i][j] = 0;
+        }
+    }
+
     g_free(self);
 }
 
@@ -219,20 +227,89 @@ xrdp_cache_reset(struct xrdp_cache *self,
     return 0;
 }
 
-#define COMPARE_WITH_CRC(_b1, _b2) \
+#define COMPARE_WITH_CRC32(_b1, _b2) \
  ((_b1 != 0) && (_b2 != 0) && (_b1->crc32 == _b2->crc32) && \
   (_b1->bpp == _b2->bpp) && \
   (_b1->width == _b2->width) && (_b1->height == _b2->height))
 
 /*****************************************************************************/
+static int APP_CC
+xrdp_cache_update_lru(struct xrdp_cache *self, int cache_id, int lru_index)
+{
+    int tail_index;
+    struct xrdp_lru_item *nextlru;
+    struct xrdp_lru_item *prevlru;
+    struct xrdp_lru_item *thislru;
+    struct xrdp_lru_item *taillru;
+
+    LLOGLN(10, ("xrdp_cache_update_lru: lru_index %d", lru_index));
+    if ((lru_index < 0) || (lru_index >= XRDP_MAX_BITMAP_CACHE_IDX))
+    {
+        LLOGLN(0, ("xrdp_cache_update_lru: error"));
+        return 1;
+    }
+    if (self->lru_tail[cache_id] == lru_index)
+    {
+        /* nothing to do */
+        return 0;
+    }
+    else if (self->lru_head[cache_id] == lru_index)
+    {
+        /* moving head item to tail */
+
+        thislru = &(self->bitmap_lrus[cache_id][lru_index]);
+        nextlru = &(self->bitmap_lrus[cache_id][thislru->next]);
+        tail_index = self->lru_tail[cache_id];
+        taillru = &(self->bitmap_lrus[cache_id][tail_index]);
+
+        /* unhook old */
+        nextlru->prev = -1;
+
+        /* set head to next */
+        self->lru_head[cache_id] = thislru->next;
+
+        /* move to tail and hook up */
+        taillru->next = lru_index;
+        thislru->prev = tail_index;
+        thislru->next = -1;
+
+        /* update tail */
+        self->lru_tail[cache_id] = lru_index;
+
+    }
+    else
+    {
+        /* move middle item */
+
+        thislru = &(self->bitmap_lrus[cache_id][lru_index]);
+        prevlru = &(self->bitmap_lrus[cache_id][thislru->prev]);
+        nextlru = &(self->bitmap_lrus[cache_id][thislru->next]);
+        tail_index = self->lru_tail[cache_id];
+        taillru = &(self->bitmap_lrus[cache_id][tail_index]);
+
+        /* unhook old */
+        prevlru->next = thislru->next;
+        nextlru->prev = thislru->prev;
+
+        /* move to tail and hook up */
+        taillru->next = lru_index;
+        thislru->prev = tail_index;
+        thislru->next = -1;
+
+        /* update tail */
+        self->lru_tail[cache_id] = lru_index;
+    }
+    return 0;
+}
+
+/*****************************************************************************/
 /* returns cache id */
 int APP_CC
 xrdp_cache_add_bitmap(struct xrdp_cache *self, struct xrdp_bitmap *bitmap,
                       int hints)
 {
-    int i;
-    int j;
-    int oldest;
+    int index;
+    int jndex;
     int cache_id;
     int cache_idx;
     int bmp_size;
@@ -241,9 +318,11 @@ xrdp_cache_add_bitmap(struct xrdp_cache *self, struct xrdp_bitmap *bitmap,
     int crc16;
     int iig;
     int found;
-    int cacheidx;
+    int cache_entries;
+    int lru_index;
     struct list *ll;
     struct xrdp_bitmap *lbm;
+    struct xrdp_lru_item *llru;
 
     LLOGLN(10, ("xrdp_cache_add_bitmap:"));
     LLOGLN(10, ("xrdp_cache_add_bitmap: crc16 0x%4.4x",
@@ -251,7 +330,8 @@ xrdp_cache_add_bitmap(struct xrdp_cache *self, struct xrdp_bitmap *bitmap,
 
     e = (4 - (bitmap->width % 4)) & 3;
     found = 0;
-    i = 0;
+    cache_id = 0;
+    cache_entries = 0;
 
     /* client Bpp, bmp_size */
     Bpp = (bitmap->bpp + 7) / 8;
@@ -260,15 +340,18 @@ xrdp_cache_add_bitmap(struct xrdp_cache *self, struct xrdp_bitmap *bitmap,
 
     if (bmp_size <= self->cache1_size)
     {
-        i = 0;
+        cache_id = 0;
+        cache_entries = self->cache1_entries;
     }
     else if (bmp_size <= self->cache2_size)
     {
-        i = 1;
+        cache_id = 1;
+        cache_entries = self->cache2_entries;
     }
     else if (bmp_size <= self->cache3_size)
     {
-        i = 2;
+        cache_id = 2;
+        cache_entries = self->cache3_entries;
     }
     else
     {
@@ -278,73 +361,51 @@ xrdp_cache_add_bitmap(struct xrdp_cache *self, struct xrdp_bitmap *bitmap,
     }
 
     crc16 = bitmap->crc16;
-    ll = self->crc16[i][crc16];
-    for (j = 0; j < ll->count; j++)
+    ll = self->crc16[cache_id][crc16];
+    for (jndex = 0; jndex < ll->count; jndex++)
     {
-        cacheidx = list_get_item(ll, j);
-        if (COMPARE_WITH_CRC(self->bitmap_items[i][cacheidx].bitmap, bitmap))
+        cache_idx = list_get_item(ll, jndex);
+        if (COMPARE_WITH_CRC32
+                 (self->bitmap_items[cache_id][cache_idx].bitmap, bitmap))
         {
-            j = cacheidx;
-            LLOGLN(10, ("found bitmap at %d %d", i, j));
+            LLOGLN(10, ("found bitmap at %d %d", index, jndex));
             found = 1;
             break;
         }
     }
     if (found)
     {
-        self->bitmap_items[i][j].stamp = self->bitmap_stamp;
+        lru_index = self->bitmap_items[cache_id][cache_idx].lru_index;
+        self->bitmap_items[cache_id][cache_idx].stamp = self->bitmap_stamp;
         xrdp_bitmap_delete(bitmap);
-        return MAKELONG(j, i);
+
+        /* update lru to end */
+        xrdp_cache_update_lru(self, cache_id, lru_index);
+
+        return MAKELONG(cache_idx, cache_id);
     }
 
-    /* look for oldest */
-    cache_id = 0;
-    cache_idx = 0;
-    oldest = 0x7fffffff;
+    /* find lru */
 
-    if (bmp_size <= self->cache1_size)
+    /* check for reset */
+    if (self->lru_reset[cache_id])
     {
-        i = 0;
-
-        for (j = 0; j < self->cache1_entries; j++)
-        {
-            if (self->bitmap_items[i][j].stamp < oldest)
-            {
-                oldest = self->bitmap_items[i][j].stamp;
-                cache_id = i;
-                cache_idx = j;
-            }
-        }
+        self->lru_reset[cache_id] = 0;
+        LLOGLN(0, ("xrdp_cache_add_bitmap: reset detected cache_id %d",
+               cache_id));
+        self->lru_tail[cache_id] = cache_entries - 1;
+        index = self->lru_tail[cache_id];
+        llru = &(self->bitmap_lrus[cache_id][index]);
+        llru->next = -1;
     }
-    else if (bmp_size <= self->cache2_size)
-    {
-        i = 1;
 
-        for (j = 0; j < self->cache2_entries; j++)
-        {
-            if (self->bitmap_items[i][j].stamp < oldest)
-            {
-                oldest = self->bitmap_items[i][j].stamp;
-                cache_id = i;
-                cache_idx = j;
-            }
-        }
-    }
-    else if (bmp_size <= self->cache3_size)
-    {
-        i = 2;
+    /* lru is item at head */
+    lru_index = self->lru_head[cache_id];
+    cache_idx = lru_index;
+
+    /* update lru to end */
+    xrdp_cache_update_lru(self, cache_id, lru_index);
 
-        for (j = 0; j < self->cache3_entries; j++)
-        {
-            if (self->bitmap_items[i][j].stamp < oldest)
-            {
-                oldest = self->bitmap_items[i][j].stamp;
-                cache_id = i;
-                cache_idx = j;
-            }
-        }
-    }
-    
     LLOGLN(10, ("xrdp_cache_add_bitmap: oldest %d %d", cache_id, cache_idx));
 
     LLOGLN(10, ("adding bitmap at %d %d old ptr %p new ptr %p",
@@ -373,6 +434,7 @@ xrdp_cache_add_bitmap(struct xrdp_cache *self, struct xrdp_bitmap *bitmap,
 
     self->bitmap_items[cache_id][cache_idx].bitmap = bitmap;
     self->bitmap_items[cache_id][cache_idx].stamp = self->bitmap_stamp;
+    self->bitmap_items[cache_id][cache_idx].lru_index = lru_index;
 
     /* add to crc16 list */
     crc16 = bitmap->crc16;
diff --git a/xrdp/xrdp_types.h b/xrdp/xrdp_types.h
index c3cf71b7..082c3e58 100644
--- a/xrdp/xrdp_types.h
+++ b/xrdp/xrdp_types.h
@@ -185,8 +185,6 @@ struct xrdp_lru_item
 {
   int next;
   int prev;
-  int cacheid;
-  int pad0;
 };
 
 struct xrdp_os_bitmap_item
@@ -240,6 +238,7 @@ struct xrdp_cache
                                   [XRDP_MAX_BITMAP_CACHE_IDX];
   int lru_head[XRDP_MAX_BITMAP_CACHE_ID];
   int lru_tail[XRDP_MAX_BITMAP_CACHE_ID];
+  int lru_reset[XRDP_MAX_BITMAP_CACHE_ID];
 
   /* crc optimize */
   struct list *crc16[XRDP_MAX_BITMAP_CACHE_ID][64 * 1024];