Re: [PATCH] dnscache: merge similar outgoing udp packets

On Wed, Apr 1, 2009 at 9:10 AM, Jeff King <[email protected]> wrote:
> This patch takes a slightly different approach to merging
> than the previous qmerge patch: rather than merging between
> the "query" and "dns_transmit" layers, it actually
> incorporates the merging into the dns_transmit layer.
>
> This makes it a much more invasive and messy patch, but
> means that it should correctly handle all situations
> (in particular, ones where sending to two different IPs will
> gives different results, generally because one server is
> down or lame).
>
> The general strategy is this:
>
>  - when a dns_transmit is about to send() a UDP query, it
>    checks for an equivalent inprogress query.
>
>    If it finds one, it marks the inprogress dns_transmit as
>    its "master", and itself as a "slave" of the master.
>
>    If it doesn't, it sends the packet and registers itself
>    as inprogress.
>
>  - when a dns_transmit recv()s a UDP packet, it creates a
>    copy of the packet for each of its slaves
>
> Two outgoing packets are considered equivalent if:
>
>  1. they are going to the same IP
>  2. they have the same qtype
>  3. they have the same qname
>
> Because this change affects the dns library itself, this
> change can potentially affect not just dnscache, but all of
> the diagnostic tools. To address this, merging must be
> enabled explicitly by the caller; dnscache will enable
> merging if the MERGEQUERIES environment variable is set.
>
> I tried to keep the patch as small and simple as possible so
> that its correctness could be verified by readers.  There
> are a few places where performance might benefit from making
> it more complex:
>
>  - dns_transmit now knows the value of MAXUDP, since it is
>    an upper bound on the number of slaves and inprogress
>    queries. As a result:
>
>      - each non-merging program which uses the dns library
>        wastes MAXUDP*sizeof(pointer) bytes of static memory
>        for the inprogress list
>
>      - each dns_transmit uses an extra MAXUDP*sizeof(pointer)
>        bytes for its slaves list. For dnscache, this
>        translates to 160K total on a 32-bit platform with
>        default MAXUDP.
>
>    Both could be avoided by using dynamic allocation.
>
>  - We have to do an O(MAXUDP) linear search to find similar
>    inprogress queries (non-merge-enabled users of the
>    library avoid paying this price, though).
>
>    This could be avoided by using a data structure with a
>    fast key lookup for inprogress.
>
> This patch is only lightly tested. Use on production servers at your own
> risk (and please report to the list if you have success using it).

This will be going into the much delayed zinq-djbdns-0.06.