[Spice-devel] [PATCH 06/10] RedChannelClient: store pipe items in a GList
Frediano Ziglio
fziglio at redhat.com
Fri Sep 9 14:27:37 UTC 2016
> Instead of using a Ring (and having a ring item link in every pipe
> item), store them in a GList. This also necesitated changing
> RedCharDeviceVDIPort->priv->read_bufs to a GList as well.
At least use a GQueue, a pipe is a queue.
> ---
> server/cursor-channel.c | 2 -
> server/dcc-send.c | 22 +++++------
> server/dcc.c | 22 +++++------
> server/display-channel.c | 7 +++-
> server/red-channel-client-private.h | 3 +-
> server/red-channel-client.c | 75
> ++++++++++++++++++++++---------------
> server/red-channel-client.h | 2 +-
> server/red-pipe-item.c | 1 -
> server/red-pipe-item.h | 6 ---
> server/reds.c | 14 +++----
> server/stream.c | 3 +-
> 11 files changed, 78 insertions(+), 79 deletions(-)
>
> diff --git a/server/cursor-channel.c b/server/cursor-channel.c
> index 9b0f493..aa02ff3 100644
> --- a/server/cursor-channel.c
> +++ b/server/cursor-channel.c
> @@ -190,8 +190,6 @@ static void cursor_pipe_item_free(RedPipeItem *base)
>
> RedCursorPipeItem *pipe_item = SPICE_UPCAST(RedCursorPipeItem, base);
>
> - spice_assert(!red_pipe_item_is_linked(&pipe_item->base));
> -
> cursor_item_unref(pipe_item->cursor_item);
> free(pipe_item);
> }
> diff --git a/server/dcc-send.c b/server/dcc-send.c
> index 972ccc6..187eaca 100644
> --- a/server/dcc-send.c
> +++ b/server/dcc-send.c
> @@ -189,7 +189,9 @@ static int is_brush_lossy(RedChannelClient *rcc,
> SpiceBrush *brush,
>
> static RedPipeItem *dcc_get_tail(DisplayChannelClient *dcc)
> {
> - return
> (RedPipeItem*)ring_get_tail(red_channel_client_get_pipe(RED_CHANNEL_CLIENT(dcc)));
> + GList *pipe = red_channel_client_get_pipe(RED_CHANNEL_CLIENT(dcc));
> + GList *last = g_list_last(pipe);
> + return last->data;
> }
>
> static void red_display_add_image_to_pixmap_cache(RedChannelClient *rcc,
> @@ -617,17 +619,13 @@ static int
> pipe_rendered_drawables_intersect_with_areas(DisplayChannelClient *dc
> SpiceRect
> *surface_areas[],
> int num_surfaces)
> {
> - RedPipeItem *pipe_item;
> - Ring *pipe;
> + GList *l;
>
> spice_assert(num_surfaces);
> - pipe = red_channel_client_get_pipe(RED_CHANNEL_CLIENT(dcc));
>
> - for (pipe_item = (RedPipeItem *)ring_get_head(pipe);
> - pipe_item;
> - pipe_item = (RedPipeItem *)ring_next(pipe, &pipe_item->link))
> - {
> + for (l = red_channel_client_get_pipe(RED_CHANNEL_CLIENT(dcc)); l !=
> NULL; l = l->next) {
> Drawable *drawable;
> + RedPipeItem *pipe_item = l->data;
>
> if (pipe_item->type != RED_PIPE_ITEM_TYPE_DRAW)
> continue;
> @@ -706,8 +704,7 @@ static void
> red_pipe_replace_rendered_drawables_with_images(DisplayChannelClient
> int resent_surface_ids[MAX_PIPE_SIZE];
> SpiceRect resent_areas[MAX_PIPE_SIZE]; // not pointers since drawables
> may be released
> int num_resent;
> - RedPipeItem *pipe_item;
> - Ring *pipe;
> + GList *l, *pipe;
>
> resent_surface_ids[0] = first_surface_id;
> resent_areas[0] = *first_area;
> @@ -716,9 +713,8 @@ static void
> red_pipe_replace_rendered_drawables_with_images(DisplayChannelClient
> pipe = red_channel_client_get_pipe(RED_CHANNEL_CLIENT(dcc));
>
> // going from the oldest to the newest
> - for (pipe_item = (RedPipeItem *)ring_get_tail(pipe);
> - pipe_item;
> - pipe_item = (RedPipeItem *)ring_prev(pipe, &pipe_item->link)) {
> + for (l = g_list_last(pipe); l != NULL; l = l->prev) {
> + RedPipeItem *pipe_item = l->data;
> Drawable *drawable;
> RedDrawablePipeItem *dpi;
> RedImageItem *image;
> diff --git a/server/dcc.c b/server/dcc.c
> index 9fea119..b12d034 100644
> --- a/server/dcc.c
> +++ b/server/dcc.c
> @@ -68,8 +68,8 @@ int dcc_drawable_is_in_pipe(DisplayChannelClient *dcc,
> Drawable *drawable)
> int dcc_clear_surface_drawables_from_pipe(DisplayChannelClient *dcc, int
> surface_id,
> int wait_if_used)
> {
> - Ring *ring;
> - RedPipeItem *item;
> + GList *l;
> + RedPipeItem *item = NULL;
> int x;
> RedChannelClient *rcc;
>
> @@ -78,13 +78,15 @@ int
> dcc_clear_surface_drawables_from_pipe(DisplayChannelClient *dcc, int surface
> no other drawable depends on them */
>
> rcc = RED_CHANNEL_CLIENT(dcc);
> - ring = &rcc->priv->pipe;
> - item = (RedPipeItem *) ring;
> - while ((item = (RedPipeItem *)ring_next(ring, &item->link))) {
> + l = rcc->priv->pipe;
> + while (l != NULL) {
> + GList *cur = l;
> Drawable *drawable;
> RedDrawablePipeItem *dpi = NULL;
> int depend_found = FALSE;
>
> + l = l->next;
> + item = cur->data;
> if (item->type == RED_PIPE_ITEM_TYPE_DRAW) {
> dpi = SPICE_CONTAINEROF(item, RedDrawablePipeItem,
> dpi_pipe_item);
> drawable = dpi->drawable;
> @@ -95,12 +97,7 @@ int
> dcc_clear_surface_drawables_from_pipe(DisplayChannelClient *dcc, int surface
> }
>
> if (drawable->surface_id == surface_id) {
> - RedPipeItem *tmp_item = item;
> - item = (RedPipeItem *)ring_prev(ring, &item->link);
> - red_channel_client_pipe_remove_and_release(rcc, tmp_item);
> - if (!item) {
> - item = (RedPipeItem *)ring;
> - }
> + red_channel_client_pipe_remove_and_release(rcc, item);
> continue;
> }
>
O(n) -> O(n^2) !
> @@ -289,7 +286,8 @@ static void red_drawable_pipe_item_free(RedPipeItem
> *item)
> dpi_pipe_item);
> spice_assert(item->refcount == 0);
>
> - spice_warn_if_fail(!ring_item_is_linked(&item->link));
> +
> spice_warn_if_fail(!red_channel_client_pipe_item_is_linked(RED_CHANNEL_CLIENT(dpi->dcc),
> +
> &dpi->dpi_pipe_item));
> if (ring_item_is_linked(&dpi->base)) {
> ring_remove(&dpi->base);
> }
> diff --git a/server/display-channel.c b/server/display-channel.c
> index 581cf18..bd2907f 100644
> --- a/server/display-channel.c
> +++ b/server/display-channel.c
> @@ -327,9 +327,12 @@ static void drawable_remove_from_pipes(Drawable
> *drawable)
> RingItem *item, *next;
>
> RING_FOREACH_SAFE(item, next, &drawable->pipes) {
> + RedChannelClient *rcc;
> +
> dpi = SPICE_UPCAST(RedDrawablePipeItem, item);
> - if (red_pipe_item_is_linked(&dpi->dpi_pipe_item)) {
> -
> red_channel_client_pipe_remove_and_release(RED_CHANNEL_CLIENT(dpi->dcc),
> + rcc = RED_CHANNEL_CLIENT(dpi->dcc);
> + if (red_channel_client_pipe_item_is_linked(rcc,
> &dpi->dpi_pipe_item)) {
> + red_channel_client_pipe_remove_and_release(rcc,
> &dpi->dpi_pipe_item);
> }
> }
Why not just removing? The is_linked test was here as removing a
not inserted item give error.
> diff --git a/server/red-channel-client-private.h
> b/server/red-channel-client-private.h
> index 532bfa3..b13f905 100644
> --- a/server/red-channel-client-private.h
> +++ b/server/red-channel-client-private.h
> @@ -59,8 +59,7 @@ struct RedChannelClientPrivate
>
> int during_send;
> int id; // debugging purposes
> - Ring pipe;
> - uint32_t pipe_size;
> + GList *pipe;
>
> RedChannelCapabilities remote_caps;
> int is_mini_header;
> diff --git a/server/red-channel-client.c b/server/red-channel-client.c
> index 0eed02b..9f678d7 100644
> --- a/server/red-channel-client.c
> +++ b/server/red-channel-client.c
> @@ -344,7 +344,7 @@ void red_channel_client_on_out_msg_done(void *opaque)
> } else {
> if (rcc->priv->latency_monitor.timer
> && !rcc->priv->send_data.blocked
> - && rcc->priv->pipe_size == 0) {
> + && rcc->priv->pipe == NULL) {
> /* It is possible that the socket will become idle, so we may be
> able to test latency */
> red_channel_client_restart_ping_timer(rcc);
> }
> @@ -354,8 +354,7 @@ void red_channel_client_on_out_msg_done(void *opaque)
>
> static void red_channel_client_pipe_remove(RedChannelClient *rcc,
> RedPipeItem *item)
> {
> - rcc->priv->pipe_size--;
> - ring_remove(&item->link);
> + rcc->priv->pipe = g_list_remove(rcc->priv->pipe, item);
> }
>
So inserting or just getting the number of items in the pipe
is going O(1) -> O(n).
> static void red_channel_client_set_remote_caps(RedChannelClient* rcc,
> @@ -681,8 +680,7 @@ RedChannelClient *red_channel_client_create(int size,
> RedChannel *channel, RedCl
> goto error;
> }
>
> - ring_init(&rcc->priv->pipe);
> - rcc->priv->pipe_size = 0;
> + rcc->priv->pipe = NULL;
>
> stream->watch = channel->core->watch_add(channel->core,
> stream->socket,
> @@ -743,7 +741,7 @@ RedChannelClient *red_channel_client_create_dummy(int
> size,
>
> rcc->incoming.header.data = rcc->incoming.header_buf;
> rcc->incoming.serial = 1;
> - ring_init(&rcc->priv->pipe);
> + rcc->priv->pipe = NULL;
>
> rcc->priv->dummy = TRUE;
> rcc->priv->dummy_connected = TRUE;
> @@ -1039,14 +1037,16 @@ void red_channel_client_send(RedChannelClient *rcc)
>
> static inline RedPipeItem *red_channel_client_pipe_item_get(RedChannelClient
> *rcc)
> {
> + GList *l;
> RedPipeItem *item;
>
> if (!rcc || rcc->priv->send_data.blocked
> || red_channel_client_waiting_for_ack(rcc)
> - || !(item = (RedPipeItem *)ring_get_tail(&rcc->priv->pipe))) {
> + || !(l = g_list_last(rcc->priv->pipe))) {
> return NULL;
> }
> - red_channel_client_pipe_remove(rcc, item);
> + item = l->data;
> + rcc->priv->pipe = g_list_delete_link(rcc->priv->pipe, l);
> return item;
> }
>
> @@ -1072,7 +1072,7 @@ void red_channel_client_push(RedChannelClient *rcc)
> while ((pipe_item = red_channel_client_pipe_item_get(rcc))) {
> red_channel_client_send_item(rcc, pipe_item);
> }
> - if (red_channel_client_no_item_being_sent(rcc) &&
> ring_is_empty(&rcc->priv->pipe)
> + if (red_channel_client_no_item_being_sent(rcc) && rcc->priv->pipe ==
> NULL
> && rcc->priv->stream->watch) {
> rcc->priv->channel->core->watch_update_mask(rcc->priv->stream->watch,
> SPICE_WATCH_EVENT_READ);
> @@ -1286,7 +1286,7 @@ void
> red_channel_client_set_message_serial(RedChannelClient *rcc, uint64_t seria
> rcc->priv->send_data.serial = serial;
> }
>
> -static inline gboolean client_pipe_add(RedChannelClient *rcc, RedPipeItem
> *item, RingItem *pos)
> +static inline gboolean prepare_pipe_add(RedChannelClient *rcc, RedPipeItem
> *item)
> {
> spice_assert(rcc && item);
> if (SPICE_UNLIKELY(!red_channel_client_is_connected(rcc))) {
> @@ -1294,20 +1294,21 @@ static inline gboolean
> client_pipe_add(RedChannelClient *rcc, RedPipeItem *item,
> red_pipe_item_unref(item);
> return FALSE;
> }
> - if (ring_is_empty(&rcc->priv->pipe) && rcc->priv->stream->watch) {
> + if (rcc->priv->pipe == NULL && rcc->priv->stream->watch) {
> rcc->priv->channel->core->watch_update_mask(rcc->priv->stream->watch,
> SPICE_WATCH_EVENT_READ |
> SPICE_WATCH_EVENT_WRITE);
> }
> - rcc->priv->pipe_size++;
> - ring_add(pos, &item->link);
> return TRUE;
> }
>
> void red_channel_client_pipe_add(RedChannelClient *rcc, RedPipeItem *item)
> {
>
> - client_pipe_add(rcc, item, &rcc->priv->pipe);
> + if (!prepare_pipe_add(rcc, item)) {
> + return;
> + }
> + rcc->priv->pipe = g_list_prepend(rcc->priv->pipe, item);
> }
>
> void red_channel_client_pipe_add_push(RedChannelClient *rcc, RedPipeItem
> *item)
> @@ -1320,27 +1321,40 @@ void
> red_channel_client_pipe_add_after(RedChannelClient *rcc,
> RedPipeItem *item,
> RedPipeItem *pos)
> {
> + GList *prev = NULL;
> +
> spice_assert(pos);
> - client_pipe_add(rcc, item, &pos->link);
> + if (!prepare_pipe_add(rcc, item)) {
> + return;
> + }
> + prev = g_list_find(rcc->priv->pipe, pos);
> + g_return_if_fail(prev != NULL);
> +
> + rcc->priv->pipe = g_list_insert_before(rcc->priv->pipe, prev->next,
> item);
> }
>
> int red_channel_client_pipe_item_is_linked(RedChannelClient *rcc,
> RedPipeItem *item)
> {
> - return ring_item_is_linked(&item->link);
> + return g_list_find(rcc->priv->pipe, item) != NULL;
> }
>
> void red_channel_client_pipe_add_tail(RedChannelClient *rcc,
> RedPipeItem *item)
> {
> - client_pipe_add(rcc, item, rcc->priv->pipe.prev);
> + if (!prepare_pipe_add(rcc, item)) {
> + return;
> + }
> + rcc->priv->pipe = g_list_append(rcc->priv->pipe, item);
> }
>
> void red_channel_client_pipe_add_tail_and_push(RedChannelClient *rcc,
> RedPipeItem *item)
> {
> - if (client_pipe_add(rcc, item, rcc->priv->pipe.prev)) {
> - red_channel_client_push(rcc);
> + if (!prepare_pipe_add(rcc, item)) {
> + return;
> }
> + rcc->priv->pipe = g_list_append(rcc->priv->pipe, item);
> + red_channel_client_push(rcc);
> }
>
> void red_channel_client_pipe_add_type(RedChannelClient *rcc, int
> pipe_item_type)
> @@ -1365,17 +1379,17 @@ void
> red_channel_client_pipe_add_empty_msg(RedChannelClient *rcc, int msg_type)
> gboolean red_channel_client_pipe_is_empty(RedChannelClient *rcc)
> {
> g_return_val_if_fail(rcc != NULL, TRUE);
> - return (rcc->priv->pipe_size == 0) && (ring_is_empty(&rcc->priv->pipe));
> + return (rcc->priv->pipe == NULL);
> }
>
> uint32_t red_channel_client_get_pipe_size(RedChannelClient *rcc)
> {
> - return rcc->priv->pipe_size;
> + return g_list_length(rcc->priv->pipe);
> }
>
> -Ring* red_channel_client_get_pipe(RedChannelClient *rcc)
> +GList* red_channel_client_get_pipe(RedChannelClient *rcc)
> {
> - return &rcc->priv->pipe;
> + return rcc->priv->pipe;
> }
>
> gboolean red_channel_client_is_mini_header(RedChannelClient *rcc)
> @@ -1405,16 +1419,15 @@ static void
> red_channel_client_clear_sent_item(RedChannelClient *rcc)
> // are we reading from an fd here? arghh
> static void red_channel_client_pipe_clear(RedChannelClient *rcc)
> {
> - RedPipeItem *item;
> + GList *l;
>
> if (rcc) {
> red_channel_client_clear_sent_item(rcc);
> }
> - while ((item = (RedPipeItem *)ring_get_head(&rcc->priv->pipe))) {
> - ring_remove(&item->link);
> - red_pipe_item_unref(item);
> + while ((l = rcc->priv->pipe)) {
> + red_pipe_item_unref(l->data);
> + rcc->priv->pipe = g_list_delete_link(rcc->priv->pipe, l);
> }
> - rcc->priv->pipe_size = 0;
> }
>
> void red_channel_client_ack_zero_messages_window(RedChannelClient *rcc)
> @@ -1545,8 +1558,8 @@ int
> red_channel_client_wait_pipe_item_sent(RedChannelClient *rcc,
> }
> red_channel_client_push(rcc);
>
> - while(item_in_pipe &&
> - (timeout == -1 || spice_get_monotonic_time_ns() < end_time)) {
> + while (item_in_pipe &&
> + (timeout == -1 || spice_get_monotonic_time_ns() < end_time)) {
> usleep(CHANNEL_BLOCKED_SLEEP_DURATION);
> red_channel_client_receive(rcc);
> red_channel_client_send(rcc);
> @@ -1598,7 +1611,7 @@ int
> red_channel_client_wait_outgoing_item(RedChannelClient *rcc,
>
> void red_channel_client_disconnect_if_pending_send(RedChannelClient *rcc)
> {
> - if (red_channel_client_is_blocked(rcc) || rcc->priv->pipe_size > 0) {
> + if (red_channel_client_is_blocked(rcc) || rcc->priv->pipe != NULL) {
> red_channel_client_disconnect(rcc);
> } else {
> spice_assert(red_channel_client_no_item_being_sent(rcc));
> diff --git a/server/red-channel-client.h b/server/red-channel-client.h
> index d2f7b3e..249e7fe 100644
> --- a/server/red-channel-client.h
> +++ b/server/red-channel-client.h
> @@ -114,7 +114,7 @@ void red_channel_client_pipe_add_type(RedChannelClient
> *rcc, int pipe_item_type)
> void red_channel_client_pipe_add_empty_msg(RedChannelClient *rcc, int
> msg_type);
> gboolean red_channel_client_pipe_is_empty(RedChannelClient *rcc);
> uint32_t red_channel_client_get_pipe_size(RedChannelClient *rcc);
> -Ring* red_channel_client_get_pipe(RedChannelClient *rcc);
> +GList* red_channel_client_get_pipe(RedChannelClient *rcc);
> gboolean red_channel_client_is_mini_header(RedChannelClient *rcc);
>
> void red_channel_client_ack_zero_messages_window(RedChannelClient *rcc);
> diff --git a/server/red-pipe-item.c b/server/red-pipe-item.c
> index 31262fa..d899610 100644
> --- a/server/red-pipe-item.c
> +++ b/server/red-pipe-item.c
> @@ -42,7 +42,6 @@ void red_pipe_item_init_full(RedPipeItem *item,
> gint type,
> red_pipe_item_free_t *free_func)
> {
> - ring_item_init(&item->link);
> item->type = type;
> item->refcount = 1;
> item->free_func = free_func ? free_func : (red_pipe_item_free_t *)free;
> diff --git a/server/red-pipe-item.h b/server/red-pipe-item.h
> index bf13b0b..a589c68 100644
> --- a/server/red-pipe-item.h
> +++ b/server/red-pipe-item.h
> @@ -26,7 +26,6 @@ struct RedPipeItem;
> typedef void red_pipe_item_free_t(struct RedPipeItem *item);
>
> typedef struct RedPipeItem {
> - RingItem link;
> int type;
>
> /* private */
> @@ -39,11 +38,6 @@ void red_pipe_item_init_full(RedPipeItem *item, int type,
> red_pipe_item_free_t f
> RedPipeItem *red_pipe_item_ref(RedPipeItem *item);
> void red_pipe_item_unref(RedPipeItem *item);
>
> -static inline int red_pipe_item_is_linked(RedPipeItem *item)
> -{
> - return ring_item_is_linked(&item->link);
> -}
> -
> static inline void red_pipe_item_init(RedPipeItem *item, int type)
> {
> red_pipe_item_init_full(item, type, NULL);
> diff --git a/server/reds.c b/server/reds.c
> index 153e201..9056c52 100644
> --- a/server/reds.c
> +++ b/server/reds.c
> @@ -238,7 +238,7 @@ struct RedCharDeviceVDIPortPrivate {
> AgentMsgFilter write_filter;
>
> /* read from agent */
> - Ring read_bufs;
> + GList *read_bufs;
> uint32_t read_state;
> uint32_t message_receive_len;
> uint8_t *receive_pos;
> @@ -806,15 +806,15 @@ static void vdi_read_buf_init(RedVDIReadBuf *buf)
>
> static RedVDIReadBuf *vdi_port_get_read_buf(RedCharDeviceVDIPort *dev)
> {
> - RingItem *item;
> + GList *item;
> RedVDIReadBuf *buf;
>
> - if (!(item = ring_get_head(&dev->priv->read_bufs))) {
> + if (!(item = g_list_first(dev->priv->read_bufs))) {
> return NULL;
> }
>
> - ring_remove(item);
> - buf = SPICE_CONTAINEROF(item, RedVDIReadBuf, base.link);
> + buf = item->data;
> + dev->priv->read_bufs = g_list_delete_link(dev->priv->read_bufs, item);
>
> g_warn_if_fail(buf->base.refcount == 0);
> vdi_read_buf_init(buf);
> @@ -827,7 +827,7 @@ static void vdi_port_read_buf_free(RedPipeItem *base)
> RedVDIReadBuf *buf = SPICE_UPCAST(RedVDIReadBuf, base);
>
> g_warn_if_fail(buf->base.refcount == 0);
> - ring_add(&buf->dev->priv->read_bufs, &buf->base.link);
> + buf->dev->priv->read_bufs = g_list_prepend(buf->dev->priv->read_bufs,
> buf);
>
> /* read_one_msg_from_vdi_port may have never completed because the
> read_bufs
> ring was empty. So we call it again so it can complete its work if
> @@ -4481,8 +4481,6 @@ red_char_device_vdi_port_init(RedCharDeviceVDIPort
> *self)
>
> self->priv = RED_CHAR_DEVICE_VDIPORT_PRIVATE(self);
>
> - ring_init(&self->priv->read_bufs);
> -
> self->priv->read_state = VDI_PORT_READ_STATE_READ_HEADER;
> self->priv->receive_pos = (uint8_t *)&self->priv->vdi_chunk_header;
> self->priv->receive_len = sizeof(self->priv->vdi_chunk_header);
> diff --git a/server/stream.c b/server/stream.c
> index 8558eec..fef9dc5 100644
> --- a/server/stream.c
> +++ b/server/stream.c
> @@ -360,7 +360,8 @@ static void before_reattach_stream(DisplayChannel
> *display,
> continue;
> }
>
> - if (red_pipe_item_is_linked(&dpi->dpi_pipe_item)) {
> + if (red_channel_client_pipe_item_is_linked(RED_CHANNEL_CLIENT(dcc),
> + &dpi->dpi_pipe_item)) {
> #ifdef STREAM_STATS
> agent->stats.num_drops_pipe++;
> #endif
This patch looks like O(n) blind. The n can be hundred so not much but
without looking at all code we can't be sure that some O(n^2) is turning
to O(n^4). Which is the worst case?
I don't think this patch is strictly GObject related.
Frediano
More information about the Spice-devel
mailing list