apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Tony Finch <...@dotat.at>
Subject Re: A question about rings.
Date Wed, 28 Aug 2002 14:18:22 GMT
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