From f94f5bec1c0563954924d7e036d0f70970236b16 Mon Sep 17 00:00:00 2001 From: Jay Sorg Date: Fri, 14 Mar 2014 11:48:07 -0700 Subject: xrdp: speed up bitmap cache lookup using hash table --- xrdp/xrdp_types.h | 22 +++++++++++++++++++++- 1 file changed, 21 insertions(+), 1 deletion(-) (limited to 'xrdp/xrdp_types.h') diff --git a/xrdp/xrdp_types.h b/xrdp/xrdp_types.h index b345e36c..c3cf71b7 100644 --- a/xrdp/xrdp_types.h +++ b/xrdp/xrdp_types.h @@ -177,9 +177,18 @@ struct xrdp_palette_item struct xrdp_bitmap_item { int stamp; + int lru_index; struct xrdp_bitmap* bitmap; }; +struct xrdp_lru_item +{ + int next; + int prev; + int cacheid; + int pad0; +}; + struct xrdp_os_bitmap_item { int id; @@ -225,6 +234,16 @@ struct xrdp_cache int bitmap_stamp; struct xrdp_bitmap_item bitmap_items[XRDP_MAX_BITMAP_CACHE_ID] [XRDP_MAX_BITMAP_CACHE_IDX]; + + /* lru optimize */ + struct xrdp_lru_item bitmap_lrus[XRDP_MAX_BITMAP_CACHE_ID] + [XRDP_MAX_BITMAP_CACHE_IDX]; + int lru_head[XRDP_MAX_BITMAP_CACHE_ID]; + int lru_tail[XRDP_MAX_BITMAP_CACHE_ID]; + + /* crc optimize */ + struct list *crc16[XRDP_MAX_BITMAP_CACHE_ID][64 * 1024]; + int use_bitmap_comp; int cache1_entries; int cache1_size; @@ -453,7 +472,8 @@ struct xrdp_bitmap struct xrdp_bitmap* popped_from; int item_height; /* crc */ - int crc; + int crc32; + int crc16; }; #define NUM_FONTS 0x4e00 -- cgit v1.2.3 From f66c5911a2ae57368e571643750c0b79aec5498f Mon Sep 17 00:00:00 2001 From: Jay Sorg Date: Fri, 14 Mar 2014 18:41:52 -0700 Subject: xrdp: speed up bitmap cache lru using linked list --- xrdp/xrdp_cache.c | 188 ++++++++++++++++++++++++++++++++++++------------------ xrdp/xrdp_types.h | 3 +- 2 files changed, 126 insertions(+), 65 deletions(-) (limited to 'xrdp/xrdp_types.h') 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]; -- cgit v1.2.3 From da0d0e687aa25beec2f80c247c51a31b148dbf46 Mon Sep 17 00:00:00 2001 From: Jay Sorg Date: Sat, 15 Mar 2014 21:59:16 -0700 Subject: reduce the memory needed for crc16 bitmap cache lists --- common/Makefile.am | 2 + common/list16.c | 188 +++++++++++++++++++++++++++++++++++++++++++++++++++++ common/list16.h | 56 ++++++++++++++++ xrdp/xrdp.h | 1 + xrdp/xrdp_cache.c | 24 +++---- xrdp/xrdp_types.h | 2 +- 6 files changed, 260 insertions(+), 13 deletions(-) create mode 100644 common/list16.c create mode 100644 common/list16.h (limited to 'xrdp/xrdp_types.h') 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; -- cgit v1.2.3