reduce the memory needed for crc16 bitmap cache lists

6 files changed, 260 insertions, 13 deletions

diff --git a/common/Makefile.am b/common/Makefile.am
index 16f3c56d..ab9c2bd5 100644
--- a/common/Makefile.am
+++ b/common/Makefile.am
@@ -5,6 +5,7 @@ EXTRA_DIST = \
   file.h \
   file_loc.h \
   list.h \
+  list16.h \
   fifo.h \
   log.h \
   os_calls.h \
@@ -32,6 +33,7 @@ libcommon_la_SOURCES = \
   d3des.c \
   file.c \
   list.c \
+  list16.c \
   fifo.c \
   log.c \
   os_calls.c \
diff --git a/common/list16.c b/common/list16.c
new file mode 100644
index 00000000..caeb9cdb
--- /dev/null
+++ b/common/list16.c
@@ -0,0 +1,188 @@
+/**
+ * xrdp: A Remote Desktop Protocol server.
+ *
+ * Copyright (C) Jay Sorg 2004-2014
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * simple list
+ */
+
+#include "arch.h"
+#include "os_calls.h"
+#include "list16.h"
+
+/*****************************************************************************/
+struct list16 *APP_CC
+list16_create(void)
+{
+    struct list16 *self;
+
+    self = (struct list16 *)g_malloc(sizeof(struct list16), 0);
+    list16_init(self);
+    return self;
+}
+
+/*****************************************************************************/
+void APP_CC
+list16_delete(struct list16 *self)
+{
+    if (self == 0)
+    {
+        return;
+    }
+
+    list16_deinit(self);
+    g_free(self);
+}
+
+/*****************************************************************************/
+void APP_CC
+list16_init(struct list16* self)
+{
+    g_memset(self, 0, sizeof(struct list16));
+    self->max_count = 4;
+    self->items = self->mitems;
+}
+
+/*****************************************************************************/
+void APP_CC
+list16_deinit(struct list16* self)
+{
+    if (self->items != self->mitems)
+    {
+        g_free(self->items);
+    }
+}
+
+/*****************************************************************************/
+void APP_CC
+list16_add_item(struct list16 *self, tui16 item)
+{
+    tui16 *p;
+    int i;
+
+    if (self->count >= self->max_count)
+    {
+        i = self->max_count;
+        self->max_count += 4;
+        p = (tui16 *)g_malloc(sizeof(tui16) * self->max_count, 1);
+        g_memcpy(p, self->items, sizeof(tui16) * i);
+        if (self->items != self->mitems)
+        {
+            g_free(self->items);
+        }
+        self->items = p;
+    }
+
+    self->items[self->count] = item;
+    self->count++;
+}
+
+/*****************************************************************************/
+tui16 APP_CC
+list16_get_item(struct list16 *self, int index)
+{
+    if (index < 0 || index >= self->count)
+    {
+        return 0;
+    }
+
+    return self->items[index];
+}
+
+/*****************************************************************************/
+void APP_CC
+list16_clear(struct list16 *self)
+{
+    if (self->items != self->mitems)
+    {
+        g_free(self->items);
+    }
+    self->count = 0;
+    self->max_count = 4;
+    self->items = self->mitems;
+}
+
+/*****************************************************************************/
+int APP_CC
+list16_index_of(struct list16 *self, tui16 item)
+{
+    int i;
+
+    for (i = 0; i < self->count; i++)
+    {
+        if (self->items[i] == item)
+        {
+            return i;
+        }
+    }
+
+    return -1;
+}
+
+/*****************************************************************************/
+void APP_CC
+list16_remove_item(struct list16 *self, int index)
+{
+    int i;
+
+    if (index >= 0 && index < self->count)
+    {
+        for (i = index; i < (self->count - 1); i++)
+        {
+            self->items[i] = self->items[i + 1];
+        }
+
+        self->count--;
+    }
+}
+
+/*****************************************************************************/
+void APP_CC
+list16_insert_item(struct list16 *self, int index, tui16 item)
+{
+    tui16 *p;
+    int i;
+
+    if (index == self->count)
+    {
+        list_add_item(self, item);
+        return;
+    }
+
+    if (index >= 0 && index < self->count)
+    {
+        self->count++;
+
+        if (self->count > self->max_count)
+        {
+            i = self->max_count;
+            self->max_count += 4;
+            p = (tui16 *)g_malloc(sizeof(tui16) * self->max_count, 1);
+            g_memcpy(p, self->items, sizeof(tui16) * i);
+            if (self->items != self->mitems)
+            {
+                g_free(self->items);
+            }
+            self->items = p;
+        }
+
+        for (i = (self->count - 2); i >= index; i--)
+        {
+            self->items[i + 1] = self->items[i];
+        }
+
+        self->items[index] = item;
+    }
+}
diff --git a/common/list16.h b/common/list16.h
new file mode 100644
index 00000000..1a328ea7
--- /dev/null
+++ b/common/list16.h
@@ -0,0 +1,56 @@
+/**
+ * xrdp: A Remote Desktop Protocol server.
+ *
+ * Copyright (C) Jay Sorg 2004-2014
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * simple list
+ */
+
+#if !defined(LIST16_H)
+#define LIST16_H
+
+#include "arch.h"
+
+/* list */
+struct list16
+{
+  tui16* items;
+  int count;
+  int max_count;
+  tui16 mitems[4];
+};
+
+struct list16* APP_CC
+list16_create(void);
+void APP_CC
+list16_delete(struct list16* self);
+void APP_CC
+list16_init(struct list16* self);
+void APP_CC
+list16_deinit(struct list16* self);
+void APP_CC
+list16_add_item(struct list16* self, tui16 item);
+tui16 APP_CC
+list16_get_item(struct list16* self, int index);
+void APP_CC
+list16_clear(struct list16* self);
+int APP_CC
+list16_index_of(struct list16* self, tui16 item);
+void APP_CC
+list16_remove_item(struct list16* self, int index);
+void APP_CC
+list16_insert_item(struct list16* self, int index, tui16 item);
+
+#endif
diff --git a/xrdp/xrdp.h b/xrdp/xrdp.h
index a4d2971b..1713835d 100644
--- a/xrdp/xrdp.h
+++ b/xrdp/xrdp.h
@@ -26,6 +26,7 @@
 #include "parse.h"
 #include "trans.h"
 #include "list.h"
+#include "list16.h"
 #include "libxrdpinc.h"
 #include "xrdp_constants.h"
 #include "xrdp_types.h"
diff --git a/xrdp/xrdp_cache.c b/xrdp/xrdp_cache.c
index b637a380..9c8098f6 100644
--- a/xrdp/xrdp_cache.c
+++ b/xrdp/xrdp_cache.c
@@ -79,8 +79,9 @@ xrdp_cache_reset_crc(struct xrdp_cache *self)
     {
         for (jndex = 0; jndex < 64 * 1024; jndex++)
         {
-            list_delete(self->crc16[index][jndex]);
-            self->crc16[index][jndex] = list_create();
+            /* it's ok it deinit a zero'ed out struct list16 */
+            list16_deinit(&(self->crc16[index][jndex]));
+            list16_init(&(self->crc16[index][jndex]));
         }
     }
     return 0;
@@ -168,8 +169,7 @@ xrdp_cache_delete(struct xrdp_cache *self)
     {
         for (j = 0; j < 64 * 1024; j++)
         {
-            list_delete(self->crc16[i][j]);
-            self->crc16[i][j] = 0;
+            list16_deinit(&(self->crc16[i][j]));
         }
     }
 
@@ -320,7 +320,7 @@ xrdp_cache_add_bitmap(struct xrdp_cache *self, struct xrdp_bitmap *bitmap,
     int found;
     int cache_entries;
     int lru_index;
-    struct list *ll;
+    struct list16 *ll;
     struct xrdp_bitmap *lbm;
     struct xrdp_lru_item *llru;
 
@@ -361,10 +361,10 @@ xrdp_cache_add_bitmap(struct xrdp_cache *self, struct xrdp_bitmap *bitmap,
     }
 
     crc16 = bitmap->crc16;
-    ll = self->crc16[cache_id][crc16];
+    ll = &(self->crc16[cache_id][crc16]);
     for (jndex = 0; jndex < ll->count; jndex++)
     {
-        cache_idx = list_get_item(ll, jndex);
+        cache_idx = list16_get_item(ll, jndex);
         if (COMPARE_WITH_CRC32
                  (self->bitmap_items[cache_id][cache_idx].bitmap, bitmap))
         {
@@ -418,15 +418,15 @@ xrdp_cache_add_bitmap(struct xrdp_cache *self, struct xrdp_bitmap *bitmap,
     if (lbm != 0)
     {
         crc16 = lbm->crc16;
-        ll = self->crc16[cache_id][crc16];
-        iig = list_index_of(ll, cache_idx);
+        ll = &(self->crc16[cache_id][crc16]);
+        iig = list16_index_of(ll, cache_idx);
         if (iig == -1)
         {
             LLOGLN(0, ("xrdp_cache_add_bitmap: error removing cache_idx"));
         }
         LLOGLN(10, ("xrdp_cache_add_bitmap: removing index %d from crc16 %d",
                iig, crc16));
-        list_remove_item(ll, iig);
+        list16_remove_item(ll, iig);
         xrdp_bitmap_delete(lbm);
     }
 
@@ -438,8 +438,8 @@ xrdp_cache_add_bitmap(struct xrdp_cache *self, struct xrdp_bitmap *bitmap,
 
     /* add to crc16 list */
     crc16 = bitmap->crc16;
-    ll = self->crc16[cache_id][crc16];
-    list_add_item(ll, cache_idx);
+    ll = &(self->crc16[cache_id][crc16]);
+    list16_add_item(ll, cache_idx);
     if (ll->count > 1)
     {
         LLOGLN(10, ("xrdp_cache_add_bitmap: count %d", ll->count));
diff --git a/xrdp/xrdp_types.h b/xrdp/xrdp_types.h
index 082c3e58..002e5c2c 100644
--- a/xrdp/xrdp_types.h
+++ b/xrdp/xrdp_types.h
@@ -241,7 +241,7 @@ struct xrdp_cache
   int lru_reset[XRDP_MAX_BITMAP_CACHE_ID];
 
   /* crc optimize */
-  struct list *crc16[XRDP_MAX_BITMAP_CACHE_ID][64 * 1024];
+  struct list16 crc16[XRDP_MAX_BITMAP_CACHE_ID][64 * 1024];
 
   int use_bitmap_comp;
   int cache1_entries;