What does QUEQUE do?

[Bodo Kaiser]

Hello,

I am currently reading the libuv source code to get a better view about the internals.

I am currently stuck about QUEUE. It appears nearly everywhere. Could somebody explain me:

1. What it specifically does?
2. What the backend is (is it kqueue, epoll, ...?)

Regards,
Bodo

[Ben Noordhuis]

It's an intrusive doubly-linked list (intrusive in the sense that the
prev/next pointers are embedded in the list members themselves). It's
not tied to any backend, it's just a handy data structure.

[bodo....@enabre.com]

Two things I still do not understand completely:

1. There are multiple QUEUE "instances" created in uv__loop_init. How can they used for storing requests, handles, etc. when a QUEUE can only hold two items?

https://github.com/joyent/libuv/blob/master/src/unix/loop.c#L37

2. The below example shows how the API of QUEUE is used:

static void uv__run_pending(uv_loop_t* loop) {
  QUEUE* q;
  uv__io_t* w;

  while (!QUEUE_EMPTY(&loop->pending_queue)) {
    q = QUEUE_HEAD(&loop->pending_queue);
    QUEUE_REMOVE(q);
    QUEUE_INIT(q);

    w = QUEUE_DATA(q, uv__io_t, pending_queue);
    w->cb(loop, w, UV__POLLOUT);
  }
}

I think the use of QUEUE_EMPTY and QUEUE_HEAD is not hard to guess and QUEUE_INIT just sets both QUEUE items to "q".

But how can I understand QUEUE_REMOVE and QUEUE_DATA?

#define QUEUE_REMOVE(q)                                                       \
  do {                                                                        \
    QUEUE_PREV_NEXT(q) = QUEUE_NEXT(q);                                       \
    QUEUE_NEXT_PREV(q) = QUEUE_PREV(q);                                       \
  }                                                                           \
  while (0)

#define QUEUE_DATA(ptr, type, field)                                          \
  ((type *) ((char *) (ptr) - ((long) &((type *) 0)->field)))

Bodo

[Ben Noordhuis]

On Fri, May 24, 2013 at 6:45 AM, <bodo....@enabre.com> wrote:
> Two things I still do not understand completely:
>
> 1. There are multiple QUEUE "instances" created in uv__loop_init. How can
> they used for storing requests, handles, etc. when a QUEUE can only hold two
> items?
>
> https://github.com/joyent/libuv/blob/master/src/unix/loop.c#L37

A QUEUE can function as either a list head (pointer to the first list
element) or a list node. So the QUEUE fields in uv_loop_t are list
heads that point to list nodes that are embedded in uv_handle_t or
uv_req_t structs.

> 2. The below example shows how the API of QUEUE is used:
>
> static void uv__run_pending(uv_loop_t* loop) {
> QUEUE* q;
> uv__io_t* w;
>
> while (!QUEUE_EMPTY(&loop->pending_queue)) {
> q = QUEUE_HEAD(&loop->pending_queue);
> QUEUE_REMOVE(q);
> QUEUE_INIT(q);
>
> w = QUEUE_DATA(q, uv__io_t, pending_queue);
> w->cb(loop, w, UV__POLLOUT);
> }
> }
>
>
> I think the use of QUEUE_EMPTY and QUEUE_HEAD is not hard to guess and
> QUEUE_INIT just sets both QUEUE items to "q".
>
> But how can I understand QUEUE_REMOVE and QUEUE_DATA?
>
> #define QUEUE_REMOVE(q)
> \
> do {
> \
> QUEUE_PREV_NEXT(q) = QUEUE_NEXT(q);
> \
> QUEUE_NEXT_PREV(q) = QUEUE_PREV(q);
> \
> }
> \
> while (0)
>
>
> #define QUEUE_DATA(ptr, type, field)
> \
> ((type *) ((char *) (ptr) - ((long) &((type *) 0)->field)))

The short answer is 'magic'. :-)

The longer answer is that QUEUE_REMOVE() unlinks the node from the
list by making its prev element point to its next element and vice
versa.

QUEUE_DATA() is just a container_of() macro: it calculates and returns
the address of the embedding struct.

I should mention that none of this is really specific to libuv. The
QUEUE type is very similar to the Linux kernel's struct list_head or
nginx's ngx_queue_t (which we used to use until some time ago.)

[Bodo Kaiser]

Am 24.05.2013 um 13:34 schrieb Ben Noordhuis <in...@bnoordhuis.nl>:

> On Fri, May 24, 2013 at 6:45 AM, <bodo....@enabre.com> wrote:
>> Two things I still do not understand completely:
>>
>> 1. There are multiple QUEUE "instances" created in uv__loop_init. How can
>> they used for storing requests, handles, etc. when a QUEUE can only hold two
>> items?
>>
>> https://github.com/joyent/libuv/blob/master/src/unix/loop.c#L37
>
> A QUEUE can function as either a list head (pointer to the first list
> element) or a list node. So the QUEUE fields in uv_loop_t are list
> heads that point to list nodes that are embedded in uv_handle_t or
> uv_req_t structs.
>

Ah, the list is built up recursively. Always wondered where the items are.

It still magic :)
At least I know get the theory ;)

Thanks,
Bodo

>
> --
> You received this message because you are subscribed to a topic in the Google Groups "libuv" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/libuv/1MqclTfh-4c/unsubscribe?hl=en-US.
> To unsubscribe from this group and all its topics, send an email to libuv+un...@googlegroups.com.
> To post to this group, send email to li...@googlegroups.com.
> Visit this group at http://groups.google.com/group/libuv?hl=en-US.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Wang Chengwen]

Maybe I find out how the QUEUE_DATA works.

I add the following code to src/unix/loop-watcher.c void uv__run_##name(uv_loop_t* loop)

printf("%p, %d\n", (char *)q, ((uintptr_t) &((uv_##name##_t *) 0)->queue));

I found that ((uintptr_t) &((uv_##name##_t *) 0)->queue)  is the offset of the field queue in the struct uv_##name##_t.

So i understand that the handle is the data, the pre and next pointer of the double link list is one field of the handle, i.e. the queue field.

The QUEUE_DATA just return handle itself.

Sorry for my bad English, I don't know my explanation is clear or not.

On Friday, May 24, 2013 12:45:42 PM UTC+8, bodo....@enabre.com wrote:

But how can I understand QUEUE_REMOVE and QUEUE_DATA?

#define QUEUE_REMOVE(q)                                                       \
  do {                                                                        \
    QUEUE_PREV_NEXT(q) = QUEUE_NEXT(q);                                       \
    QUEUE_NEXT_PREV(q) = QUEUE_PREV(q);                                       \
  }                                                                           \
  while (0)

#define QUEUE_DATA(ptr, type, field)                                          \
  ((type *) ((char *) (ptr) - ((long) &((type *) 0)->field))

Bodo