Subversion Repositories HelenOS-doc

Rev

Rev 99 | Rev 114 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 99 Rev 112
1 
<?xml version="1.0" encoding="UTF-8"?>
 1 
<?xml version="1.0" encoding="UTF-8"?>
2 
<chapter id="ipc">
 2 
<chapter id="ipc">
3 
  <?dbhtml filename="ipc.html"?>
 3 
  <?dbhtml filename="ipc.html"?>
4 
 
 4 
 
5 
  <title>IPC</title>
 5 
  <title>IPC</title>
6 
 
 6 
 
7 
  <para>Due to the high intertask communication traffic, IPC becomes critical
 7 
  <para>Due to the high intertask communication traffic, IPC becomes critical
8 
  subsystem for microkernels, putting high demands on the speed, latency and
 8 
  subsystem for microkernels, putting high demands on the speed, latency and
9 
  reliability of IPC model and implementation. Although theoretically the use
 9 
  reliability of IPC model and implementation. Although theoretically the use
10 
  of asynchronous messaging system looks promising, it is not often
 10 
  of asynchronous messaging system looks promising, it is not often
11 
  implemented because of a problematic implementation of end user
 11 
  implemented because of a problematic implementation of end user
12 
  applications. HelenOS implements a fully asynchronous messaging system but
 12 
  applications. HelenOS implements a fully asynchronous messaging system with
13 
  with a special layer providing a user application developer a reasonably
 13 
  a special layer providing a user application developer a reasonably
14 
  synchronous multithreaded environment sufficient to develop complex
 14 
  synchronous multithreaded environment sufficient to develop complex
15 
  protocols.</para>
 15 
  protocols.</para>
16 
 
 16 
 
17 
  <section>
 17 
  <section>
18 
    <title>Services provided by kernel</title>
 18 
    <title>Services provided by kernel</title>
19 
 
 19 
 
20 
    <para>Every message consists of 4 numeric arguments (32-bit and 64-bit on
 20 
    <para>Every message consists of 4 numeric arguments (32-bit and 64-bit on
21 
    the corresponding platforms), from which the first one is considered a
 21 
    the corresponding platforms), from which the first one is considered a
22 
    method number on message receipt and a return value on answer receipt. The
 22 
    method number on message receipt and a return value on answer receipt. The
23 
    received message contains identification of the incoming connection, so
 23 
    received message contains identification of the incoming connection, so
24 
    that the receiving application can distinguish the messages between
 24 
    that the receiving application can distinguish the messages between
25 
    different senders. Internally the message contains pointer to the
 25 
    different senders. Internally the message contains pointer to the
26 
    originating task and to the source of the communication channel. If the
 26 
    originating task and to the source of the communication channel. If the
27 
    message is forwarded, the originating task identifies the recipient of the
 27 
    message is forwarded, the originating task identifies the recipient of the
28 
    answer, the source channel identifies the connection in case of a hangup
 28 
    answer, the source channel identifies the connection in case of a hangup
29 
    response.</para>
 29 
    response.</para>
30 
 
 30 
 
31 
    <para>Every message must be eventually answered. The system keeps track of
 31 
    <para>Every message must be eventually answered. The system keeps track of
32 
    all messages, so that it can answer them with appropriate error code
 32 
    all messages, so that it can answer them with appropriate error code
33 
    should one of the connection parties fail unexpectedly. To limit buffering
 33 
    should one of the connection parties fail unexpectedly. To limit buffering
34 
    of the messages in the kernel, every process is has a limited account of
 34 
    of the messages in the kernel, every process is has a limited account of
35 
    asynchronous messages it can send simultanously. If the limit is reached,
 35 
    asynchronous messages it can send simultanously. If the limit is reached,
36 
    the kernel refuses to send any other message, until some active message is
 36 
    the kernel refuses to send any other message, until some active message is
37 
    answered.</para>
 37 
    answered.</para>
38 
 
 38 
 
39 
    <para>To facilitate kernel-to-user communication, the IPC subsystem
 39 
    <para>To facilitate kernel-to-user communication, the IPC subsystem
40 
    provides notification messages. The applications can subscribe to a
 40 
    provides notification messages. The applications can subscribe to a
41 
    notification channel and receive messages directed to this channel. Such
 41 
    notification channel and receive messages directed to this channel. Such
42 
    messages can be freely sent even from interrupt context as they are
 42 
    messages can be freely sent even from interrupt context as they are
43 
    primarily destined to deliver IRQ events to userspace device drivers.
 43 
    primarily destined to deliver IRQ events to userspace device drivers.
44 
    These messages need not be answered, there is no party that could receive
 44 
    These messages need not be answered, there is no party that could receive
45 
    such response.</para>
 45 
    such response.</para>
46 
 
 46 
 
47 
    <section>
 47 
    <section>
48 
      <title>Low level IPC</title>
 48 
      <title>Low level IPC</title>
49 
 
 49 
 
50 
      <para>The whole IPC subsystem consists of one-way communication
 50 
      <para>The whole IPC subsystem consists of one-way communication
51 
      channels. Each task has one associated message queue (answerbox). The
 51 
      channels. Each task has one associated message queue (answerbox). The
52 
      task can open connections (identified by phone id) to other tasks, send
 52 
      task can call other tasks and connect it's phones to their answerboxes.,
53 
      and forward messages through these connections and answer received
 53 
      send and forward messages through these connections and answer received
54 
      messages. Every sent message is identified by a unique number, so that
 54 
      messages. Every sent message is identified by a unique number, so that
55 
      the response can be later matched against it. The message is sent over
 55 
      the response can be later matched against it. The message is sent over
56 
      the phone to the target answerbox. Server application periodically
 56 
      the phone to the target answerbox. Server application periodically
57 
      checks the answerbox and pulls messages from several queues associated
 57 
      checks the answerbox and pulls messages from several queues associated
58 
      with it. After completing the requested action, server sends a reply
 58 
      with it. After completing the requested action, server sends a reply
59 
      back to the answerbox of the originating task. If a need arises, it is
 59 
      back to the answerbox of the originating task. If a need arises, it is
60 
      possible to <emphasis>forward</emphasis> a recevied message throught any
 60 
      possible to <emphasis>forward</emphasis> a recevied message throught any
61 
      of the open phones to another task. This mechanism is used e.g. for
 61 
      of the open phones to another task. This mechanism is used e.g. for
62 
      opening new connections.</para>
 62 
      opening new connections.</para>
63 
 
 63 
 
- 
 
 64 
      <para>The answerbox contains four different message queues:</para>
- 
 
 65 
 
- 
 
 66 
      <itemizedlist>
- 
 
 67 
        <listitem>
- 
 
 68 
          <para>Incoming call queue</para>
- 
 
 69 
        </listitem>
- 
 
 70 
 
- 
 
 71 
        <listitem>
- 
 
 72 
          <para>Dispatched call queue</para>
- 
 
 73 
        </listitem>
- 
 
 74 
 
- 
 
 75 
        <listitem>
- 
 
 76 
          <para>Answer queue</para>
- 
 
 77 
        </listitem>
- 
 
 78 
 
- 
 
 79 
        <listitem>
- 
 
 80 
          <para>Notification queue</para>
- 
 
 81 
        </listitem>
- 
 
 82 
      </itemizedlist>
- 
 
 83 
 
- 
 
 84 
      <para>The communication between task A, that is connected to task B
- 
 
 85 
      looks as follows: Task A sends a message over it's phone to the target
- 
 
 86 
      asnwerbox. The message is saved in task B incoming call queue. When task
- 
 
 87 
      B fetches the message for processing, it is automatically moved into the
- 
 
 88 
      dispatched call queue. After the server decides to answer the message,
- 
 
 89 
      it is removed from dispatched queue and the result is moved into the
- 
 
 90 
      answer queue of task A.</para>
- 
 
 91 
 
64 
      <para>The arguments contained in the message are completely arbitrary
 92 
      <para>The arguments contained in the message are completely arbitrary
65 
      and decided by the user. The low level part of kernel IPC fills in
 93 
      and decided by the user. The low level part of kernel IPC fills in
66 
      appropriate error codes if there is an error during communication. It is
 94 
      appropriate error codes if there is an error during communication. It is
67 
      ensured that the applications are correctly notified about communication
 95 
      assured that the applications are correctly notified about communication
68 
      state. If the outgoing connection is closed with the hangup message, the
 96 
      state. If a program closes the outgoing connection, the target answerbox
69 
      target answerbox receives a hangup message. The connection
 97 
      receives a hangup message. The connection identification is not reused,
70 
      identification is not reused, until the hangup message is acknowledged
 98 
      until the hangup message is acknowledged and all other pending messages
71 
      and all other pending messages are answered.</para>
 99 
      are answered.</para>
72 
 
 100 
 
73 
      <para>If the server side decides to hangup an incoming connection, it
 101 
      <para>Closing an incoming connection is done by responding to any
74 
      does it by responding to any incoming message with an EHANGUP error
 102 
      incoming message with an EHANGUP error code. The connection is then
75 
      code. The connection is then immediately closed. The client connection
 103 
      immediately closed. The client connection identification (phone id) is
76 
      identification (phone id) is not reused, until the client issues hangup
 104 
      not reused, until the client issues closes it's own side of the
77 
      system call to close the outgoing connection.</para>
 105 
      connection ("hangs his phone up").</para>
78 
 
 106 
 
79 
      <para>When a task dies (whether voluntarily or by being killes), cleanup
 107 
      <para>When a task dies (whether voluntarily or by being killed), cleanup
80 
      process is started which performs following tasks.</para>
 108 
      process is started. </para>
81 
 
 109 
 
82 
      <orderedlist>
 110 
      <orderedlist>
83 
        <listitem>
 111 
        <listitem>
84 
          <para>Hangs up all outgoing connections and sends hangup messages to
 112 
          <para>Hangs up all outgoing connections and sends hangup messages to
85 
          all target answerboxes.</para>
 113 
          all target answerboxes.</para>
86 
        </listitem>
 114 
        </listitem>
87 
 
 115 
 
88 
        <listitem>
 116 
        <listitem>
89 
          <para>Disconnects all incoming connections.</para>
 117 
          <para>Disconnects all incoming connections.</para>
90 
        </listitem>
 118 
        </listitem>
91 
 
 119 
 
92 
        <listitem>
 120 
        <listitem>
93 
          <para>Disconnects from all notification channels.</para>
 121 
          <para>Disconnects from all notification channels.</para>
94 
        </listitem>
 122 
        </listitem>
95 
 
 123 
 
96 
        <listitem>
 124 
        <listitem>
97 
          <para>Answers all unanswered messages from answerbox queues with
 125 
          <para>Answers all unanswered messages from answerbox queues with
98 
          appropriate error code.</para>
 126 
          appropriate error code.</para>
99 
        </listitem>
 127 
        </listitem>
100 
 
 128 
 
101 
        <listitem>
 129 
        <listitem>
102 
          <para>Waits until all outgoing messages are answered and all
 130 
          <para>Waits until all outgoing messages are answered and all
103 
          remaining answerbox queues are empty.</para>
 131 
          remaining answerbox queues are empty.</para>
104 
        </listitem>
 132 
        </listitem>
105 
      </orderedlist>
 133 
      </orderedlist>
106 
    </section>
 134 
    </section>
107 
 
 135 
 
108 
    <section>
 136 
    <section>
109 
      <title>System call IPC layer</title>
 137 
      <title>System call IPC layer</title>
110 
 
 138 
 
111 
      <para>On top of this simple protocol the kernel provides special
 139 
      <para>On top of this simple protocol the kernel provides special
112 
      services closely related to the inter-process communication. A range of
 140 
      services closely related to the inter-process communication. A range of
113 
      method numbers is allocated and protocol is defined for these functions.
 141 
      method numbers is allocated and protocol is defined for these functions.
114 
      The messages are interpreted by the kernel layer and appropriate actions
 142 
      The messages are interpreted by the kernel layer and appropriate actions
115 
      are taken depending on the parameters of message and answer. </para>
 143 
      are taken depending on the parameters of message and answer. </para>
116 
 
 144 
 
117 
      <para>The kernel provides the following services:</para>
 145 
      <para>The kernel provides the following services:</para>
118 
 
 146 
 
119 
      <itemizedlist>
 147 
      <itemizedlist>
120 
        <listitem>
 148 
        <listitem>
121 
          <para>Creating new outgoing connection</para>
 149 
          <para>Creating new outgoing connection</para>
122 
        </listitem>
 150 
        </listitem>
123 
 
 151 
 
124 
        <listitem>
 152 
        <listitem>
125 
          <para>Creating a callback connection</para>
 153 
          <para>Creating a callback connection</para>
126 
        </listitem>
 154 
        </listitem>
127 
 
 155 
 
128 
        <listitem>
 156 
        <listitem>
129 
          <para>Sending an address space area</para>
 157 
          <para>Sending an address space area</para>
130 
        </listitem>
 158 
        </listitem>
131 
 
 159 
 
132 
        <listitem>
 160 
        <listitem>
133 
          <para>Asking for an address space area</para>
 161 
          <para>Asking for an address space area</para>
134 
        </listitem>
 162 
        </listitem>
135 
      </itemizedlist>
 163 
      </itemizedlist>
- 
 
 164 
 
- 
 
 165 
      <para>On startup every task is automatically connected to a
- 
 
 166 
      <emphasis>name service task</emphasis>, which provides a switchboard
- 
 
 167 
      functionality. To open a new outgoing connection, the client sends a
- 
 
 168 
      <constant>CONNECT_ME_TO</constant> message using any of his phones. If
- 
 
 169 
      the recepient of this message answers with an accepting answer, a new
- 
 
 170 
      connection is created. In itself, this mechanism would allow only
- 
 
 171 
      duplicating existing connection. However, if the message is forwarded,
- 
 
 172 
      the new connection is made to the final recipient. </para>
- 
 
 173 
 
- 
 
 174 
      <para>On startup every task is automatically connect to the name service
- 
 
 175 
      task, which acts as a switchboard and forwards requests for connection
- 
 
 176 
      to specific services. To be able to forward a message it must have a
- 
 
 177 
      phone connected to the service tasks. The task creates this connection
- 
 
 178 
      using a <constant>CONNECT_TO_ME</constant> message which creates a
- 
 
 179 
      callback connection. Every service that wants to receive connections
- 
 
 180 
      asks name service task to create a callback connection.</para>
- 
 
 181 
 
- 
 
 182 
      <para>Tasks can share their address space areas using IPC messages. The
- 
 
 183 
      2 message types - AS_AREA_SEND and AS_AREA_RECV are used for sending and
- 
 
 184 
      receiving an address area respectively. The shared area can be accessed
- 
 
 185 
      as soon as the message is acknowledged. </para>
136 
    </section>
 186 
    </section>
137 
  </section>
 187 
  </section>
138 
 
 188 
 
139 
  <section>
 189 
  <section>
140 
    <title>Userspace view</title>
 190 
    <title>Userspace view</title>
141 
 
 191 
 
142 
    <para>The conventional design of the asynchronous api seems to produce
 192 
    <para>The conventional design of the asynchronous api seems to produce
143 
    applications with one event loop and several big switch statements.
 193 
    applications with one event loop and several big switch statements.
144 
    However, by intensive utilization of user-space threads, it was possible
 194 
    However, by intensive utilization of user-space threads, it was possible
145 
    to create an environment that is not necesarilly restricted to this type
 195 
    to create an environment that is not necesarilly restricted to this type
146 
    of event-driven programming and allows for more fluent expression of
 196 
    of event-driven programming and allows for more fluent expression of
147 
    application programs.</para>
 197 
    application programs.</para>
148 
 
 198 
 
149 
    <section>
 199 
    <section>
150 
      <title>Single point of entry</title>
 200 
      <title>Single point of entry</title>
151 
 
 201 
 
152 
      <para>Each tasks is associated with only one answerbox. If a
 202 
      <para>Each tasks is associated with only one answerbox. If a
153 
      multi-threaded application needs to communicate, it must be not only
 203 
      multi-threaded application needs to communicate, it must be not only
154 
      able to send a message, but it should be able to retrieve the answer as
 204 
      able to send a message, but it should be able to retrieve the answer as
155 
      well. If several threads pull messages from task answerbox, it is a
 205 
      well. If several threads pull messages from task answerbox, it is a
156 
      matter of fortune, which thread receives which message. If a particular
 206 
      matter of fortune, which thread receives which message. If a particular
157 
      thread needs to wait for a message answer, an idle
 207 
      thread needs to wait for a message answer, an idle
158 
      <emphasis>manager</emphasis> task is found or a new one is created and
 208 
      <emphasis>manager</emphasis> task is found or a new one is created and
159 
      control is transfered to this manager task. The manager tasks pops
 209 
      control is transfered to this manager task. The manager tasks pops
160 
      messages from the answerbox and puts them into appropriate queues of
 210 
      messages from the answerbox and puts them into appropriate queues of
161 
      running tasks. If a task waiting for a message is not running, the
 211 
      running tasks. If a task waiting for a message is not running, the
162 
      control is transferred to it.</para>
 212 
      control is transferred to it.</para>
163 
 
 213 
 
164 
      <para>Very similar situation arises when a task decides to send a lot of
 214 
      <para>Very similar situation arises when a task decides to send a lot of
165 
      messages and reaches kernel limit of asynchronous messages. In such
 215 
      messages and reaches kernel limit of asynchronous messages. In such
166 
      situation 2 remedies are available - the userspace liberary can either
 216 
      situation 2 remedies are available - the userspace liberary can either
167 
      cache the message locally and resend the message when some answers
 217 
      cache the message locally and resend the message when some answers
168 
      arrive, or it can block the thread and let it go on only after the
 218 
      arrive, or it can block the thread and let it go on only after the
169 
      message is finally sent to the kernel layer. With one exception HelenOS
 219 
      message is finally sent to the kernel layer. With one exception HelenOS
170 
      uses the second approach - when the kernel responds that maximum limit
 220 
      uses the second approach - when the kernel responds that maximum limit
171 
      of asynchronous messages was reached, control is transferred to manager
 221 
      of asynchronous messages was reached, control is transferred to manager
172 
      thread. The manager thread then handles incoming replies and when space
 222 
      thread. The manager thread then handles incoming replies and when space
173 
      is available, sends the message to kernel and resumes application thread
 223 
      is available, sends the message to kernel and resumes application thread
174 
      execution.</para>
 224 
      execution.</para>
175 
 
 225 
 
176 
      <para>If a kernel notification is received, the servicing procedure is
 226 
      <para>If a kernel notification is received, the servicing procedure is
177 
      run in the context of the manager thread. Although it wouldn't be
 227 
      run in the context of the manager thread. Although it wouldn't be
178 
      impossible to allow recursive calling, it could potentially lead to an
 228 
      impossible to allow recursive calling, it could potentially lead to an
179 
      explosion of manager threads. Thus, the kernel notification procedures
 229 
      explosion of manager threads. Thus, the kernel notification procedures
180 
      are not allowed to wait for a message result, they can only answer
 230 
      are not allowed to wait for a message result, they can only answer
181 
      messages and send new ones without waiting for their results. If the
 231 
      messages and send new ones without waiting for their results. If the
182 
      kernel limit for outgoing messages is reached, the data is automatically
 232 
      kernel limit for outgoing messages is reached, the data is automatically
183 
      cached within the application. This behaviour is enforced automatically
 233 
      cached within the application. This behaviour is enforced automatically
184 
      and the decision making is hidden from developers view.</para>
 234 
      and the decision making is hidden from developers view.</para>
185 
    </section>
 235 
    </section>
186 
 
 236 
 
187 
    <section>
 237 
    <section>
188 
      <title>Synchronization problem</title>
 238 
      <title>Ordering problem</title>
189 
 
 239 
 
190 
      <para>Unfortunately, in the real world is is never so easy. E.g. if a
 240 
      <para>Unfortunately, in the real world is is never so easy. E.g. if a
191 
      server handles incoming requests and as a part of it's response sends
 241 
      server handles incoming requests and as a part of it's response sends
192 
      asynchronous messages, it can be easily prempted and other thread may
 242 
      asynchronous messages, it can be easily prempted and other thread may
193 
      start intervening. This can happen even if the application utilizes only
 243 
      start intervening. This can happen even if the application utilizes only
194 
      1 kernel thread. Classical synchronization using semaphores is not
 244 
      1 kernel thread. Classical synchronization using semaphores is not
195 
      possible, as locking on them would block the thread completely and the
 245 
      possible, as locking on them would block the thread completely and the
196 
      answer couldn't be ever processed. The IPC framework allows a developer
 246 
      answer couldn't be ever processed. The IPC framework allows a developer
197 
      to specify, that the thread should not be preempted to any other thread
 247 
      to specify, that the thread should not be preempted to any other thread
198 
      (except notification handlers) while still being able to queue messages
 248 
      (except notification handlers) while still being able to queue messages
199 
      belonging to other threads and regain control when the answer
 249 
      belonging to other threads and regain control when the answer
200 
      arrives.</para>
 250 
      arrives.</para>
201 
 
 251 
 
202 
      <para>This mechanism works transparently in multithreaded environment,
 252 
      <para>This mechanism works transparently in multithreaded environment,
203 
      where classical locking mechanism (futexes) should be used. The IPC
 253 
      where classical locking mechanism (futexes) should be used. The IPC
204 
      framework ensures that there will always be enough free threads to
 254 
      framework ensures that there will always be enough free threads to
205 
      handle the threads requiring correct synchronization and allow the
 255 
      handle the threads requiring correct synchronization and allow the
206 
      application to run more user-space threads inside the kernel threads
 256 
      application to run more user-space threads inside the kernel threads
207 
      without the danger of locking all kernel threads in futexes.</para>
 257 
      without the danger of locking all kernel threads in futexes.</para>
208 
    </section>
 258 
    </section>
209 
 
 259 
 
210 
    <section>
 260 
    <section>
211 
      <title>The interface</title>
 261 
      <title>The interface</title>
212 
 
 262 
 
213 
      <para></para>
 263 
      <para></para>
214 
    </section>
 264 
    </section>
215 
  </section>
 265 
  </section>
216 
</chapter>
 266 
</chapter>