You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@apr.apache.org by "Gregory (Grisha) Trubetskoy" <gr...@ispol.com> on 2002/08/27 21:40:18 UTC
A question about rings.
I asked this on apache-modules, but got no reply - it was probably the
wrong place to ask anyway.
I'm trying to unerstand the code behind rings, and I am puzzled by how the
sentinel is computed. Why is the offset to the next pointer in the _base_
subtracted from the pointer to _head_, and what's the point of the offset
subtraction.
In other words, instead of
#define APR_RING_SENTINEL(hp, elem, link) \
(struct elem *)((char *)(hp) - APR_OFFSETOF(struct elem, link))
Why not:
#define APR_RING_SENTINEL(hp, elem) \
(struct elem *)(hp)
It so happens that the APR_RING_ENTRY is always first in the element
structure, and so the offset is 0 which is why it works (and the macros
above yeld same result). But it seems to me that if the APR_RING_ENTRY
was't first, then the result of APR_RING_SENTINEL could be a pointer to
somewhere before beginning of head, or some place within head but before
APR_RING_HEAD, which could be some arbitrary and not necessarily constant
value.
The documentation for APR_RING_ENTRY first says that a structure can have
multiple APR_RING_ENTRY's for different rings, but then it warns that
APR_RING_ENTRY should always be first which seems to me
self-contradictory.
I also looked at the ring.h in splim code, and there it does the same
offset subtraction thing which makes no sense to me.
What am I missing?
Thanks,
Grisha
Re: A question about rings.
Posted by Cliff Woolley <jw...@virginia.edu>.
On Wed, 28 Aug 2002, Aaron Bannert wrote:
> This is *really* good stuff, including the ascii art. We should find
> a home for this in the docs. :)
Tony already committed it to apr_ring.h. :)
Thanks Tony!
--Cliff
Re: A question about rings.
Posted by Aaron Bannert <aa...@clove.org>.
On Wed, Aug 28, 2002 at 03:18:22PM +0100, Tony Finch wrote:
> 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.
This is *really* good stuff, including the ascii art. We should find
a home for this in the docs. :)
-aaron
Nevermind (Was Re: A question about rings.)
Posted by "Gregory (Grisha) Trubetskoy" <gr...@ispol.com>.
Oops, nevermind - the head of the ring apr_bucket_brigade.list, as is
evident from
#define APR_BRIGADE_SENTINEL(b) APR_RING_SENTINEL(&(b)->list, apr_bucket, link)
On Wed, 28 Aug 2002, Gregory (Grisha) Trubetskoy wrote:
>
> 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 <do...@dotat.at> http://dotat.at/
> > HUMBER THAMES DOVER WIGHT PORTLAND PLYMOUTH: NORTH BACKING SOUTHWEST 3 OR 4.
> > FAIR. MODERATE OR GOOD.
> >
>
>
Re: A question about rings.
Posted by "Gregory (Grisha) Trubetskoy" <gr...@ispol.com>.
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 <do...@dotat.at> http://dotat.at/
> HUMBER THAMES DOVER WIGHT PORTLAND PLYMOUTH: NORTH BACKING SOUTHWEST 3 OR 4.
> FAIR. MODERATE OR GOOD.
>
Re: A question about rings.
Posted by Tony Finch <do...@dotat.at>.
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 <do...@dotat.at> http://dotat.at/
HUMBER THAMES DOVER WIGHT PORTLAND PLYMOUTH: NORTH BACKING SOUTHWEST 3 OR 4.
FAIR. MODERATE OR GOOD.
Re: A question about rings.
Posted by Cliff Woolley <jw...@virginia.edu>.
On Tue, 27 Aug 2002, Gregory (Grisha) Trubetskoy wrote:
> I guess I am just having a difficult time picturing a scenario where
> elements are on multiple rings but must share the same head. I suppose
> there is a small gain in not having to allocate a head structure per
> ring...
You can get into tricky scenarios where you might want interlocking rings
or something like that. It would become then important to know which of
the sentinels you'd reached. If that makes sense. Anyway, I'm kind of
reaching at this point because I have yet to see an actual use case for
this. I'm sure there is one out there somewhere.
Tony? Maybe you can shed some more light on this.
--Cliff
Re: A question about rings.
Posted by "Gregory (Grisha) Trubetskoy" <gr...@ispol.com>.
On Tue, 27 Aug 2002, Cliff Woolley wrote:
> On Tue, 27 Aug 2002, Gregory (Grisha) Trubetskoy wrote:
>
> > In other words, instead of
> >
> > #define APR_RING_SENTINEL(hp, elem, link) \
> > (struct elem *)((char *)(hp) - APR_OFFSETOF(struct elem, link))
> >
> > Why not:
> >
> > #define APR_RING_SENTINEL(hp, elem) \
> > (struct elem *)(hp)
> >
> > It so happens that the APR_RING_ENTRY is always first in the element
> > structure, and so the offset is 0 which is why it works (and the macros
> > above yeld same result). But it seems to me that if the APR_RING_ENTRY
> > was't first, then the result of APR_RING_SENTINEL could be a pointer to
> > somewhere before beginning of head, or some place within head but before
> > APR_RING_HEAD, which could be some arbitrary and not necessarily constant
> > value.
>
> That's in fact exactly the point. The sentinel value is not really to be
> thought of as a pointer to anything in particular... it's just a magic
> number. A ring element structure can be set up so that each element can
> be on more than one ring at a time. In that case, each of the rings
> attached to any given head needs a unique sentinel value. So while it's
> true that this is hardly ever used and is optimized away, it's there just
> in case somebody wants to use it.
>
> Make more sense?
Thanks for the explanation.
I guess I am just having a difficult time picturing a scenario where
elements are on multiple rings but must share the same head. I suppose
there is a small gain in not having to allocate a head structure per
ring...
IMHO it seems like it would be cleaner if the pointer arithmetic was
removed and a restriction was made that each ring requires a unique head
element because it's pointer value *is* the sentinel. Then there would be
no magic about it (pun intended).
Then again I might be missing something... :-)
But thanks for taking the time to explain it,
Grisha
Re: A question about rings.
Posted by Cliff Woolley <jw...@virginia.edu>.
On Tue, 27 Aug 2002, Gregory (Grisha) Trubetskoy wrote:
> In other words, instead of
>
> #define APR_RING_SENTINEL(hp, elem, link) \
> (struct elem *)((char *)(hp) - APR_OFFSETOF(struct elem, link))
>
> Why not:
>
> #define APR_RING_SENTINEL(hp, elem) \
> (struct elem *)(hp)
>
> It so happens that the APR_RING_ENTRY is always first in the element
> structure, and so the offset is 0 which is why it works (and the macros
> above yeld same result). But it seems to me that if the APR_RING_ENTRY
> was't first, then the result of APR_RING_SENTINEL could be a pointer to
> somewhere before beginning of head, or some place within head but before
> APR_RING_HEAD, which could be some arbitrary and not necessarily constant
> value.
That's in fact exactly the point. The sentinel value is not really to be
thought of as a pointer to anything in particular... it's just a magic
number. A ring element structure can be set up so that each element can
be on more than one ring at a time. In that case, each of the rings
attached to any given head needs a unique sentinel value. So while it's
true that this is hardly ever used and is optimized away, it's there just
in case somebody wants to use it.
Make more sense?
--Cliff