Codebase list dillo / 04a9d12f-a396-4174-9a05-f821555c55ec/main doc / IO.txt
04a9d12f-a396-4174-9a05-f821555c55ec/main

Tree @04a9d12f-a396-4174-9a05-f821555c55ec/main (Download .tar.gz)

IO.txt @04a9d12f-a396-4174-9a05-f821555c55ec/mainraw · history · blame

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
This is the updated base of a paper I wrote with Horst.
It provides a good introduction to Dillo's internals.
(Highly recommended if you plan to patch or develop in Dillo)

It may not be exactly accurate (it's quite old), but it explains
the theory behind in some detail, so it's more than recommended
reading material.
--Jcid


-----------------------------------------------------
Parallel network programming of the Dillo web browser
-----------------------------------------------------

 Jorge Arellano-Cid <jcid@dillo.org>
 Horst H. von Brand <vonbrand@inf.utfsm.cl>


--------
Abstract
--------

   Network  programs  face  several delay sources when sending or
retrieving  data.  This  is  particularly problematic in programs
which interact directly with the user, most notably web browsers.
We  present  a hybrid approach using threads communicated through
pipes  and  signal  driven  I/O, which allows a non-blocking main
thread and overlapping waiting times.


------------
Introduction
------------

   The Dillo project didn't start from scratch but mainly working
on  the  code base of gzilla (a light web browser written by Raph
Levien). As the project went by, the code of the whole source was
standardized,  and the networking engine was replaced with a new,
faster  design.  Later,  the  parser  was  changed,  the streamed
handling  of data and its error control was put under the control
of the CCC (Concomitant Control Chain), and the old widget system
was  replaced  with  a new one (Dw). The source code is currently
regarded   as   "very   stable   beta",   and   is  available  at
<http://www.dillo.org>. Dillo is a project licensed under the GNU
General Public License.

   This  paper covers basic design aspects of the hybrid approach
that  the  Dillo  web  browser  uses  to  solve  several  latency
problems.  After  introducing  the  main  delay-sources, the main
points of the hybrid design will be addressed.


-------------
Delay sources
-------------

   Network  programs  face several delay-sources while sending or
retrieving  data.  In  the particular case of a web browser, they
are found in:

  DNS querying:
    The time required to solve a name.

  Initiating the TCP connection:
    The three way handshake of the TCP protocol.

  Sending the query:
    The time spent uploading queries to the remote server.

  Retrieving data:
    The time spent expecting and receiving the query answer.

  Closing the TCP connection:
    The four packet-sending closing sequence of the TCP protocol.

   In  a  WAN  context,  every  single  item  of this list has an
associated  delay that is non deterministic and often measured in
seconds. If we add several connections per browsed page (each one
requiring  at  least  the 4 last steps), the total latency can be
considerable.


-----------------------------------
The traditional (blocking) approach
-----------------------------------

   The main problems with the blocking approach are:

     When issuing an operation that can't be completed
     immediately, the process is put to sleep waiting for
     completion, and the program doesn't do any other
     processing in the meantime.

     When waiting for a specific socket operation to complete,
     packets that belong to other connections may be arriving,
     and have to wait for service.

     Web browsers handle many small transactions,
     if waiting times are not overlapped
     the latency perceived by the user can be very annoying.

     If the user interface is just put to sleep during network
     operations, the program becomes unresponsive, confusing
     and perhaps alarming the user.

     Not overlapping waiting times and processing makes
     graphical rendering (which is arguably the central function
     of a browser) unnecessarily slow.


---------------------
Dillo's hybrid design
---------------------

   Dillo  uses  threads  and  signal  driven  I/O  extensively to
overlap   waiting   times  and  computation.  Handling  the  user
interface  in a thread that never blocks gives a good interactive
``feel.''  The  use of GTK+, a sophisticated widget framework for
graphical  user  interfaces,  helped very much to accomplish this
goal.  All the interface, rendering and I/O engine was built upon
its facilities.

   The  design  is  said to be ``hybrid'' because it uses threads
for  DNS  querying and reading local files, and signal driven I/O
for  TCP  connections.  The  threaded  DNS  scheme is potentially
concurrent  (this  depends on underlying hardware), while the I/O
handling   (both   local   files   and   remote  connections)  is
definitively parallel.

   To  simplify  the  structure  of  the browser, local files are
encapsulated  into  HTTP streams and presented to the rest of the
browser  as  such, in exactly the same way a remote connection is
handled.  To  create  this  illusion,  a thread is launched. This
thread  opens  a  pipe  to  the  browser,  it then synthesizes an
appropriate  HTTP  header, sends it together with the file to the
browser  proper.  In  this way, all the browser sees is a handle,
the  data on it can come from a remote connection or from a local
file.

   To  handle  a remote connection is more complex. In this case,
the  browser  asks the cache manager for the URL. The name in the
URL  has  to  be  resolved  through  the DNS engine, a socket TCP
connection  must be established, the HTTP request has to be sent,
and  finally  the  result  retrieved. Each of the steps mentioned
could  give  rise to errors, which have to be handled and somehow
communicated to the rest of the program. For performance reasons,
it  is  critical that responses are cached locally, so the remote
connection  doesn't  directly  hand over the data to the browser;
the  response is passed to the cache manager which then relays it
to  the rest of the browser. The DNS engine caches DNS responses,
and  either  answers  them from the cache or by querying the DNS.
Querying  is  done  in a separate thread, so that the rest of the
browser isn't blocked by long waits here.

   The  activities  mentioned do not happen strictly in the order
stated  above.  It  is  even possible that several URLs are being
handled  at  the  same  time,  in  order  to  overlap waiting and
downloading.   The   functions  called  directly  from  the  user
interface   have   to  return  quickly  to  maintain  interactive
response.  Sometimes they return connection handlers that haven't
been completely set up yet. As stated, I/O is signal-driven, when
one  of  the  descriptors  is ready for data transfer (reading or
writing), it wakes up the I/O engine.

   Data transfer between threads inside the browser is handled by
pipes,  shared  memory  is  little used. This almost obviates the
need for explicit synchronization, which is one of the main areas
of  complexity and bugs in concurrent programs. Dillo handles its
threads  in  a way that its developers can think of it as running
on a single thread of control. This is accomplished by making the
DNS  engine  call-backs  happen  within  the  main thread, and by
isolating file loading with pipes.

   Using threads in this way has three big advantages:

     The browser doesn't block when one of its child threads
     blocks. In particular, the user interface is responsive
     even while resolving a name or downloading a file.

     Developers don't need to deal with complex concurrent
     concerns. Concurrency is hard to handle,  and few developers
     are adept at this. This gives access a much larger pool of
     potential developers, something which can be critical
     in an open-source development project.

     By making the code mostly sequential, debugging the code
     with traditional tools like gdb is possible. Debugging
     parallel programs is very hard, and appropriate tools are
     hard to come by.

   Because  of  simplicity and portability concerns, DNS querying
is  done  in  a  separate  thread. The standard C library doesn't
provide  a  function for making DNS queries that don't block. The
alternative  is  to implement a new, custom DNS querying function
that doesn't block. This is certainly a complex task, integrating
this  mechanism  into the thread structure of the program is much
simpler.

   Using  a  thread  and  a  pipe  to  read  a  local file adds a
buffering step to the process (and a certain latency), but it has
a couple of significative advantages:

     By handling local files in the same way as remote
     connections, a significant amount of code is reused.

     A preprocessing step of the file data can be added easily,
     if needed. In fact, the file is encapsulated into an HTTP
     data stream.


-----------
DNS queries
-----------

   Dillo handles DNS queries with threads, letting a child thread
wait  until  the  DNS server answers the request. When the answer
arrives,  a call-back function is called, and the program resumes
what  it  was doing at DNS-request time. The interesting thing is
that  the  call-back  happens in the main thread, while the child
thread  simply  exits  when  done.  This is implemented through a
server-channel design.


The server channel
------------------

   There  is  one  thread  for each channel, and each channel can
have  multiple  clients. When the program requests an IP address,
the server first looks for a cached match; if it hits, the client
call-back  is  invoked immediately, but if not, the client is put
into  a  queue,  a thread is spawned to query the DNS, and a GTK+
idle  client  is  set  to poll the channel 5~times per second for
completion,  and  when  it finally succeeds, every client of that
channel is serviced.

   This  scheme  allows all the further processing to continue on
the same thread it began: the main thread.


------------------------
Handling TCP connections
------------------------

   Establishing   a   TCP  connection  requires  the  well  known
three-way handshake packet-sending sequence. Depending on network
traffic  and several other issues, significant delay can occur at
this phase.

   Dillo  handles the connection by a non blocking socket scheme.
Basically,  a socket file descriptor of AF_INET type is requested
and set to non-blocking I/O. When the DNS server has resolved the
name, the socket connection process begins by calling connect(2);
  {We use the Unix convention of identifying the manual section
   where the concept is described, in this case
   section 2 (system calls).}
which  returns  immediately  with an EINPROGRESS error.

   After  the  connection  reaches the EINPROGRESS ``state,'' the
socket  waits in background until connection succeeds (or fails),
when  that  happens, a callback function is awaked to perform the
following  steps: set the I/O engine to send the query and expect
its answer (both in background).

   The  advantage  of  this scheme is that every required step is
quickly  done  without  blocking the browser. Finally, the socket
will generate a signal whenever I/O is possible.


----------------
Handling queries
----------------

   In  the case of a HTTP URL, queries typically translate into a
short  transmission  (the  HTTP  query)  and  a lengthy retrieval
process.  Queries  are  not  always  short though, specially when
requesting  forms  (all  the  form  data  is  attached within the
query), and also when requesting CGI programs.

   Regardless  of  query  length,  query  sending  is  handled in
background.  The thread that was initiated at TCP connecting time
has all the transmission framework already set up; at this point,
packet   sending   is   just   a   matter   of  waiting  for  the
write  signal  (G_IO_OUT) to come and then sending the data. When
the  socket  gets  ready for transmission, the data is sent using
IO_write.


--------------
Receiving data
--------------

   Although  conceptually  similar to sending queries, retrieving
data is very different as the data received can easily exceed the
size  of  the query by many orders of magnitude (for example when
downloading  images or files). This is one of the main sources of
latency,  the  retrieval can take several seconds or even minutes
when downloading large files.

   The  data  retrieving process for a single file, that began by
setting up the expecting framework at TCP connecting time, simply
waits  for  the  read  signal  (G_IO_IN).  When  it  happens, the
low-level   I/O  engine  gets  called,  the  data  is  read  into
pre-allocated   buffers   and   the  appropriate  call-backs  are
performed.  Technically,  whenever  a G_IO_IN event is generated,
data  is  received  from the socket file descriptor, by using the
IO_read function. This iterative process finishes upon EOF (or on
an error condition).


----------------------
Closing the connection
----------------------

   Closing  a  TCP connection requires four data segments, not an
impressive  amount  but  twice  the round trip time, which can be
substantial.  When  data  retrieval  finishes,  socket closing is
triggered. There's nothing but a IO_close_fd call on the socket's
file  descriptor.  This  process was originally designed to split
the  four  segment  close into two partial closes, one when query
sending is done and the other when all data is in. This scheme is
not currently used because the write close also stops the reading
part.


The low-level I/O engine
------------------------

   Dillo  I/O  is carried out in the background. This is achieved
by  using  low level file descriptors and signals. Anytime a file
descriptor  shows  activity,  a  signal  is raised and the signal
handler takes care of the I/O.

   The  low-level  I/O  engine  ("I/O  engine"  from here on) was
designed  as  an  internal  abstraction layer for background file
descriptor  activity.  It  is  intended  to  be used by the cache
module  only;  higher level routines should ask the cache for its
URLs.  Every  operation  that  is  meant  to  be  carried  out in
background  should  be  handled by the I/O engine. In the case of
TCP sockets, they are created and submitted to the I/O engine for
any further processing.

   The  submitting process (client) must fill a request structure
and let the I/O engine handle the file descriptor activity, until
it  receives a call-back for finally processing the data. This is
better understood by examining the request structure:

 typedef struct {
    gint Key;              /* Primary Key (for klist) */
    gint Op;               /* IORead | IOWrite | IOWrites */
    gint FD;               /* Current File Descriptor */
    gint Flags;            /* Flag array */
    glong Status;          /* Number of bytes read, or -errno code */

    void *Buf;             /* Buffer place */
    size_t BufSize;        /* Buffer length */
    void *BufStart;        /* PRIVATE: only used inside IO.c! */

    void *ExtData;         /* External data reference (not used by IO.c) */
    void *Info;            /* CCC Info structure for this IO */
    GIOChannel *GioCh;     /* IO channel */
    guint watch_id;        /* glib's event source id */
 } IOData_t;

   To request an I/O operation, this structure must be filled and
passed to the I/O engine.

  'Op' and 'Buf' and 'BufSize' MUST be provided.

  'ExtData' MAY be provided.

  'Status',  'FD'  and  'GioCh'  are  set  by I/O engine internal
routines.

   When  there  is new data in the file descriptor, 'IO_callback'
gets  called  (by  glib).  Only  after  the  I/O  engine finishes
processing the data are the upper layers notified.


The I/O engine transfer buffer
------------------------------

   The  'Buf' and  'BufSize'  fields  of  the  request  structure
provide  the transfer buffer for each operation. This buffer must
be set by the client (to increase performance by avoiding copying
data).

   On  reads,  the client specifies the amount and where to place
the retrieved data; on writes, it specifies the amount and source
of  the  data  segment  that  is to be sent. Although this scheme
increases  complexity,  it has proven very fast and powerful. For
instance,  when  the  size  of  a document is known in advance, a
buffer for all the data can be allocated at once, eliminating the
need for multiple memory reallocations. Even more, if the size is
known  and the data transfer is taking the form of multiple small
chunks  of  data,  the  client  only  needs  to  update 'Buf' and
BufSize'  to  point  to  the  next byte in its large preallocated
reception  buffer  (by  adding  the  chunk size to 'Buf'). On the
other  hand,  if the size of the transfer isn't known in advance,
the  reception  buffer  can remain untouched until the connection
closes,  but  the  client  must  then accomplish the usual buffer
copying and reallocation.

   The  I/O  engine  also  lets  the client specify a full length
transfer  buffer  when  sending data. It doesn't matter (from the
client's  point  of  view) if the data fits in a single packet or
not,  it's  the I/O engine's job to divide it into smaller chunks
if needed and to perform the operation accordingly.


------------------------------------------
Handling multiple simultaneous connections
------------------------------------------

   The  previous sections describe the internal work for a single
connection,  the  I/O engine handles several of them in parallel.
This  is the normal downloading behavior of a web page. Normally,
after   retrieving   the   main  document  (HTML  code),  several
references  to  other files (typically images) and sometimes even
to  other  sites  (mostly advertising today) are found inside the
page.  In  order  to parse and complete the page rendering, those
other  documents  must  be  fetched  and  displayed, so it is not
uncommon  to  have  multiple  downloading  connections (every one
requiring the whole fetching process) happening at the same time.

   Even  though  socket  activity  can  reach  a hectic pace, the
browser  never  blocks.  Note also that the I/O engine is the one
that  directs  the  execution flow of the program by triggering a
call-back  chain whenever a file descriptor operation succeeds or
fails.

   A  key point for this multiple call-back chained I/O engine is
that  every  single  function  in the chain must be guaranteed to
return  quickly.  Otherwise,  the  whole  system  blocks until it
returns.


-----------
Conclusions
-----------

   Dillo is currently in very stable beta state. It already shows
impressive  performance,  and  its  interactive  ``feel'' is much
better than that of other web browsers.

   The modular structure of Dillo, and its reliance on GTK1 allow
it  to  be  very  small.  Not every feature of HTML-4.01 has been
implemented  yet,  but  no  significant  problems are foreseen in
doing this.

   The  fact  that  Dillo's  central  I/O engine is written using
advanced  features  of  POSIX  and  TCP/IP  networking  makes its
performance  possible, but on the other hand this also means that
only a fraction of the interested hackers are able to work on it.

   A  simple code base is critical when trying to attract hackers
to  work  on  a  project  like this one. Using the GTK+ framework
helped  both  in  creating  the  graphical  user interface and in
handling  the  concurrency  inside the browser. By having threads
communicate  through  pipes the need for explicit synchronization
is  almost  completely  eliminated,  and  with  it  most  of  the
complexity of concurrent programming disappears.

   A  clean,  strictly  applied  layering approach based on clear
abstractions  is  vital  in  each  programming  project.  A good,
supportive framework is of much help here.