apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Gregory (Grisha) Trubetskoy" <gri...@ispol.com>
Subject Re: A question about rings.
Date Wed, 28 Aug 2002 18:35:27 GMT

Hmm... But doesn't this mean that in apr_bucket_brigade, APR_RING_HEAD
should be first in the structure?

Currently, we have:

struct apr_bucket {
    APR_RING_ENTRY(apr_bucket) link;
    ...
}

struct apr_bucket_brigade {
    apr_pool_t *p;
    APR_RING_HEAD(apr_bucket_list, apr_bucket) list;
    ...
}

If I understood Tony's explanation correctly, then assuming we have:

apr_bucket *last;
apr_bucket_brigade *head;
apr_bucket *next;

and the above point to one another same as in Tony's example below, then

last->link.next->link.next
      ^^^^^^^^^
       sentinel

won't quite work, because the sentinel pointer (first link.next) will
point to the pool pointer in apr_bucket_brigade. But it _will_ work if
apr_bucket_brigade looks like this:

struct apr_bucket_brigade {
    APR_RING_HEAD(apr_bucket_list, apr_bucket) list;
    apr_pool_t *p;
    ...
}



On Wed, 28 Aug 2002, Tony Finch wrote:

> On Wed, Aug 28, 2002 at 03:09:50AM -0400, Cliff Woolley wrote:
> >
> > Tony?  Maybe you can shed some more light on this.
>
> Yes. The comment about the sentinel says it's magic, and it isn't lying.
> It is good and functional magic, though :-)
>
> One misconception to correct: each ring has exactly one head. An element
> may be on multiple rings -- for example, inside a kernel there may be
> a ring of all processes and run queues for each CPU, so the process
> structure will have ring entries for the ring of all processes and the
> run queue that it is on. But each of the rings is distinct -- on a dual
> CPU machine there will be three rings and three heads, and each process
> will be on two of the rings (because it has two ring entry structures).
>
> Time for some ASCII art, I think. This is to illustrate the arrangements
> of the next and prev pointers of each element in a single ring. Note that
> they point to the start of each element, not to the ring entry structure.
>
>      +->+------+<-+  +->+------+<-+  +->+------+<-+
>      |  |struct|  |  |  |struct|  |  |  |struct|  |
>     /   | elem |   \/   | elem |   \/   | elem |  \
>  ...    |      |   /\   |      |   /\   |      |   ...
>         +------+  |  |  +------+  |  |  +------+
>    ...--|prev  |  |  +--|ring  |  |  +--|prev  |
>         |  next|--+     | entry|--+     |  next|--...
>         +------+        +------+        +------+
>         | etc. |        | etc. |        | etc. |
>         :      :        :      :        :      :
>
> Now look at what happens at the head of the ring, which is nothing but
> a bare ring entry structure. The prev and next pointers in the first and
> last elements don't actually point to the head, they point to a phantom
> place called the sentinel. (There is a warning in the code's comments
> because pointers like this aren't strictly allowed by C.) Its value is
> such that last->next->next == first and first->prev->prev == last because
> the offset from the sentinel to the head's next pointer is the same as
> the offset from the start of an element to its next pointer.
>
>         last                            first
>      +->+------+<-+  +->sentinel<-+  +->+------+<-+
>      |  |struct|  |  |            |  |  |struct|  |
>     /   | elem |   \/              \/   | elem |  \
>  ...    |      |   /\              /\   |      |   ...
>         +------+  |  |  +------+  |  |  +------+
>    ...--|prev  |  |  +--|ring  |  |  +--|prev  |
>         |  next|--+     |  head|--+     |  next|--...
>         +------+        +------+        +------+
>         | etc. |                        | etc. |
>         :      :                        :      :
>
> Note that the offset mentioned above is different for each kind of ring
> that the element may be on -- in the example, the ring of all processes
> is a different kind of ring from the per-CPU run queues, and different
> kinds of ring use different names for their entry structures in each
> element.
>
> I hope this makes it clear how it works and what you would use it for.
> I should probably add this to the comments in the code.
>
> Tony.
> --
> f.a.n.finch <dot@dotat.at> http://dotat.at/
> HUMBER THAMES DOVER WIGHT PORTLAND PLYMOUTH: NORTH BACKING SOUTHWEST 3 OR 4.
> FAIR. MODERATE OR GOOD.
>



Mime
View raw message