apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Aaron Bannert <aa...@clove.org>
Subject Re: A question about rings.
Date Wed, 28 Aug 2002 17:57:03 GMT
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

Mime
View raw message