Re: multi-threaded udp resolver

Re: multi-threaded udp resolver

[Damien Doligez]

>From: Julian Assange <proff@iq.org>

>While ocaml provides appropriate udp send/receive functions, the best
>mechanism for understanding the structure of dns packets is unknown to
>me.

What you describe looks like a parsing problem to me.  I would try to
use ocamlyacc or stream parsers if I had to solve your problem.  But
I've never done anything like that, so I can't guarantee it's really
the best way to do it.

-- Damien

RE: multi-threaded udp resolver

[Manuel Fahndrich]

Have a look at

Satish Chandra and Peter J. McCann, "Packet Types", in the Second Workshop
on Compiler Support for Systems Software (WCSSS), May 1999. 

The paper tries to formalize the structure of self-describing data
structures such as network packets.

Not that this is implemented in OCaml, but maybe a CAMLp4 prepass would
help.

-Manuel


-----Original Message-----
From: Julian Assange [mailto:proff@iq.org]
Sent: Saturday, March 18, 2000 9:57 AM
To: caml-redistribution@pauillac.inria.fr
Cc: proff@iq.org
Subject: multi-threaded udp resolver



I've previously written a multi-threaded udp dns resolver in c (not
threads so much as a fsm emulating threads). I'd like to, if possible
write one in ocaml directly, rather than simply hooking into the C
code (which wouldn't be that simple anyway, due to the various timers,
management of fd's etc it needs).

While ocaml provides appropriate udp send/receive functions, the best
mechanism for understanding the structure of dns packets is unknown to
me. DNS packets are `loosely' structured. That is, there are many
different structural elements (including arrays of those elements),
and exactly how they are crammed into a packet can only be determined
by reading the structure. i.e the first part of the structure
describes the type (but not structure) of the next strucural element
and so on.

Vixie's named/bind daemon doesn't even attempt to describe the
structure in any sort of data form, but rather uses the code flow
itself to describe the structure (e.g pulling 16 bits, assigning it to
a variable, advancing the interpretation pointer by 16 bits, testing
the variable, pulling 32 bits etc). This method is incredibly
error-prone, and it's hard to see a good way of fitting it in with
ocaml's type system. Any ideas on the best way to approach this problem?

Cheers,
Julian.

-- 
Stefan Kahrs in [Kah96] discusses the
   notion of completeness--programs which never go wrong can be
   type-checked--which complements Milner's notion of
   soundness--type-checked programs never go wrong [Mil78].

Re: multi-threaded udp resolver

[Dave Mason]

>>>>> On 10 Mar 2000 09:34:47 +1100, Julian Assange <proff@iq.org> said:

> While ocaml provides appropriate udp send/receive functions, the
> best mechanism for understanding the structure of dns packets is
> unknown to me. DNS packets are `loosely' structured. That is, there
>[...]
> Vixie's named/bind daemon doesn't even attempt to describe the
> structure in any sort of data form, but rather uses the code flow
> itself to describe the structure (e.g pulling 16 bits, assigning it
> to a variable, advancing the interpretation pointer by 16 bits,
> testing the variable, pulling 32 bits etc).

I would unpack the packet into a char list and then process it with something like:

let dispatch cont = function
	| t1::t2::rest -> (match (ord t1)*256+(ord t2) with
		| 1 -> type1 cont rest
		| 2 -> type2 cont rest
		| _ -> error...
		)
	| _ -> error...
and type1 cont = function
	| f1::f2::f3::...::rest] -> cont (...f1...f2...f3...) rest
	| _ -> error...
and type1 cont = function
	| f1::f2::rest] -> dispatch (fun v rest' -> cont (...f1...f2...v...) rest') rest
	| _ -> error...
;;

note that cont is a continuation, that will be used to process the
rest of the string after the current value is parsed.

You could also use an ocaml parser.

> This method is incredibly error-prone, and it's hard to see a good
> way of fitting it in with ocaml's type system. Any ideas on the best
> way to approach this problem?

Getting the types right can be a little tricky, but is doable.

../Dave

multi-threaded udp resolver

[Julian Assange]

I've previously written a multi-threaded udp dns resolver in c (not
threads so much as a fsm emulating threads). I'd like to, if possible
write one in ocaml directly, rather than simply hooking into the C
code (which wouldn't be that simple anyway, due to the various timers,
management of fd's etc it needs).

While ocaml provides appropriate udp send/receive functions, the best
mechanism for understanding the structure of dns packets is unknown to
me. DNS packets are `loosely' structured. That is, there are many
different structural elements (including arrays of those elements),
and exactly how they are crammed into a packet can only be determined
by reading the structure. i.e the first part of the structure
describes the type (but not structure) of the next strucural element
and so on.

Vixie's named/bind daemon doesn't even attempt to describe the
structure in any sort of data form, but rather uses the code flow
itself to describe the structure (e.g pulling 16 bits, assigning it to
a variable, advancing the interpretation pointer by 16 bits, testing
the variable, pulling 32 bits etc). This method is incredibly
error-prone, and it's hard to see a good way of fitting it in with
ocaml's type system. Any ideas on the best way to approach this problem?

Cheers,
Julian.

-- 
Stefan Kahrs in [Kah96] discusses the
   notion of completeness--programs which never go wrong can be
   type-checked--which complements Milner's notion of
   soundness--type-checked programs never go wrong [Mil78].