On 9/10/21 10:37 AM, Dominik DL6ER wrote:
> Hey Petr and Simon,
>
> On Thu, 2021-09-09 at 23:35 +0100, Simon Kelley wrote:
>> Much tidier is to simplify things and add an extra parameter to
>> log_query which is the type, if type is non-zero, log_query calls
>> querystr(), so
>>
>> log_query(flags, name, addr, querystr("description", type));
>>
>> becomes
>>
>> log_query(flags, name, addr, "description", type);
>>
> I agree this is a good solution, patch attached. I hope to have caught
> all places (I don't have the dependencies to build all possible
> combinations myself).
Builds fine with DNSSEC, LIBIDN2 and DBUS. I failed to notice querystr()
were called always and unconditionally, I thought I were optimizing just
--log-queries scenario.
>
> On Thu, 2021-09-09 at 23:35 +0100, Simon Kelley wrote:
>> querystr becomes a local function to cache.c or just gets rolled into
>> log_query().
> I did the former. Merging it into log_query() would make an already
> complex routine even longer.
>
>
> Concerning performance: The loop can at most iterate over 89 entries
> before it says: "Didn't find". However, for the vast vast majority of
> cases, the match will be in the first 30ish (AAAA and SRV) as query
> types behind those are not very likely to be seen. The loop breaks as
> soon as the match is found. Looking at the gcc11 x86_64 -O2 assembly,
> there are no surprises, only very few assembler instructions per
> iteration are needed. The next type integers in the table can always be
> found 16 bytes after the former. Hence, we just need
>
> .FOR_LOOP
> add rax, 1
> cmp rax, 89
> je .NOT_FOUND
> mov rdx, rax
> movsx rcx, eax
> sal rdx, 4
> cmp DWORD PTR typestr[rdx], r1d
> jne .FOR_LOOP
> [... stuff if found ...]
>
> Given we call library functions like strlen() and sprintf(), our loop
> here is surely not any kind of bottleneck. Even if it'd be even larger.
>
> Best,
> Dominik
I admit moving querystr into log_query is much more important
optimization than my table lookup change. But it can still be applied
with minor tweak and would save some loops. In patch #1. If HTTPS record
is logged, it would have to pass 64 rows before finding correct one.
With runtime dynamic data, we have not much better choices. But for
built-in static data, we can switch linear lookup to constant. I admit
64 iterations is not too much to save, but at least something. Often it
means lookup both for query and response.
I think dest = arg; should be called after querystr(), just like it was
before. It works with common addresses, but there might be some corner
cases broken. Change in patch #2.
--
Petr Menšík
Software Engineer
Red Hat, http://www.redhat.com/
email: pemen...@redhat.com
PGP: DFCF908DB7C87E8E529925BC4931CA5B6C9FC5CB
>From 281e9cc7fff0e067cb3b590f6f4e837ea80cae60 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Petr=20Men=C5=A1=C3=ADk?= <pemen...@redhat.com>
Date: Fri, 10 Sep 2021 16:18:08 +0200
Subject: [PATCH 2/2] Assign dest after arg is set
---
src/cache.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
diff --git a/src/cache.c b/src/cache.c
index ab8f9d9..f43c34b 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -1970,7 +1970,7 @@ static char *edestr(int ede)
void log_query(unsigned int flags, char *name, union all_addr *addr, char *arg, unsigned short type)
{
- char *source, *dest = arg;
+ char *source, *dest;
char *verb = "is";
char *extra = "";
@@ -1980,6 +1980,7 @@ void log_query(unsigned int flags, char *name, union all_addr *addr, char *arg,
/* build query type string if requested */
if(type > 0)
arg = querystr(arg, type);
+ dest = arg;
#ifdef HAVE_DNSSEC
if ((flags & F_DNSSECOK) && option_bool(OPT_EXTRALOG))
--
2.31.1
>From 95a7dba6d43a29bf0562c04262edf65db5bdc513 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Petr=20Men=C5=A1=C3=ADk?= <pemen...@redhat.com>
Date: Thu, 9 Sep 2021 21:42:10 +0200
Subject: [PATCH 1/2] Include all DNS types and speed up lookups
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Reworked proposal made by Dominik DL6ER, add all types registered by
IANA registry. Replace sequential walking through single table by
walking through set of arrays with offsets for their values. Makes
it more efficient with multiple values, while it omits gaps with
undefined types.
Signed-off-by: Petr Menšík <pemen...@redhat.com>
---
src/cache.c | 173 ++++++++++++++++++++++++++++++++++++--------------
src/dnsmasq.h | 2 +-
2 files changed, 125 insertions(+), 50 deletions(-)
diff --git a/src/cache.c b/src/cache.c
index 5be73cf..ab8f9d9 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -29,52 +29,125 @@ static void make_non_terminals(struct crec *source);
static struct crec *really_insert(char *name, union all_addr *addr, unsigned short class,
time_t now, unsigned long ttl, unsigned int flags);
+/* taken from https://www.iana.org/assignments/dns-parameters/dns-parameters.xhtml */
/* type->string mapping: this is also used by the name-hash function as a mixing table. */
+
+static const char *typestr_1[] = {
+ "A", /* 1 - a host address [RFC1035] */
+ "NS", /* 2 - an authoritative name server [RFC1035] */
+ "MD", /* 3 - a mail destination (OBSOLETE - use MX) [RFC1035] */
+ "MF", /* 4 - a mail forwarder (OBSOLETE - use MX) [RFC1035] */
+ "CNAME", /* 5 - the canonical name for an alias [RFC1035] */
+ "SOA", /* 6 - marks the start of a zone of authority [RFC1035] */
+ "MB", /* 7 - a mailbox domain name (EXPERIMENTAL) [RFC1035] */
+ "MG", /* 8 - a mail group member (EXPERIMENTAL) [RFC1035] */
+ "MR", /* 9 - a mail rename domain name (EXPERIMENTAL) [RFC1035] */
+ "NULL", /* 10 - a null RR (EXPERIMENTAL) [RFC1035] */
+ "WKS", /* 11 - a well known service description [RFC1035] */
+ "PTR", /* 12 - a domain name pointer [RFC1035] */
+ "HINFO", /* 13 - host information [RFC1035] */
+ "MINFO", /* 14 - mailbox or mail list information [RFC1035] */
+ "MX", /* 15 - mail exchange [RFC1035] */
+ "TXT", /* 16 - text strings [RFC1035] */
+ "RP", /* 17 - for Responsible Person [RFC1183] */
+ "AFSDB", /* 18 - for AFS Data Base location [RFC1183][RFC5864] */
+ "X25", /* 19 - for X.25 PSDN address [RFC1183] */
+ "ISDN", /* 20 - for ISDN address [RFC1183] */
+ "RT", /* 21 - for Route Through [RFC1183] */
+ "NSAP", /* 22 - for NSAP address, NSAP style A record [RFC1706] */
+ "NSAP_PTR", /* 23 - for domain name pointer, NSAP style [RFC1348][RFC1637][RFC1706] */
+ "SIG", /* 24 - for security signature [RFC2535][RFC2536][RFC2537][RFC2931][RFC3008][RFC3110][RFC3755][RFC4034] */
+ "KEY", /* 25 - for security key [RFC2535][RFC2536][RFC2537][RFC2539][RFC3008][RFC3110][RFC3755][RFC4034] */
+ "PX", /* 26 - X.400 mail mapping information [RFC2163] */
+ "GPOS", /* 27 - Geographical Position [RFC1712] */
+ "AAAA", /* 28 - IP6 Address [RFC3596] */
+ "LOC", /* 29 - Location Information [RFC1876] */
+ "NXT", /* 30 - Next Domain (OBSOLETE) [RFC2535][RFC3755] */
+ "EID", /* 31 - Endpoint Identifier [Michael_Patton][http://ana-3.lcs.mit.edu/~jnc/nimrod/dns.txt] 1995-06 */
+ "NIMLOC", /* 32 - Nimrod Locator [1][Michael_Patton][http://ana-3.lcs.mit.edu/~jnc/nimrod/dns.txt] 1995-06 */
+ "SRV", /* 33 - Server Selection [1][RFC2782] */
+ "ATMA", /* 34 - ATM Address [ ATM Forum Technical Committee, "ATM Name System, V2.0", Doc ID: AF-DANS-0152.000, July 2000. Available from and held in escrow by IANA.] */
+ "NAPTR", /* 35 - Naming Authority Pointer [RFC2168][RFC2915][RFC3403] */
+ "KX", /* 36 - Key Exchanger [RFC2230] */
+ "CERT", /* 37 - CERT [RFC4398] */
+ "A6", /* 38 - A6 (OBSOLETE - use AAAA) [RFC2874][RFC3226][RFC6563] */
+ "DNAME", /* 39 - DNAME [RFC6672] */
+ "SINK", /* 40 - SINK [Donald_E_Eastlake][http://tools.ietf.org/html/draft-eastlake-kitchen-sink] 1997-11 */
+ "OPT", /* 41 - OPT [RFC3225][RFC6891] */
+ "APL", /* 42 - APL [RFC3123] */
+ "DS", /* 43 - Delegation Signer [RFC3658][RFC4034] */
+ "SSHFP", /* 44 - SSH Key Fingerprint [RFC4255] */
+ "IPSECKEY", /* 45 - IPSECKEY [RFC4025] */
+ "RRSIG", /* 46 - RRSIG [RFC3755][RFC4034] */
+ "NSEC", /* 47 - NSEC [RFC3755][RFC4034][RFC9077] */
+ "DNSKEY", /* 48 - DNSKEY [RFC3755][RFC4034] */
+ "DHCID", /* 49 - DHCID [RFC4701] */
+ "NSEC3", /* 50 - NSEC3 [RFC5155][RFC9077] */
+ "NSEC3PARAM", /* 51 - NSEC3PARAM [RFC5155] */
+ "TLSA", /* 52 - TLSA [RFC6698] */
+ "SMIMEA", /* 53 - S/MIME cert association [RFC8162] SMIMEA/smimea-completed-template 2015-12-01 */
+ NULL, /* 54 */
+ "HIP", /* 55 - Host Identity Protocol [RFC8005] */
+ "NINFO", /* 56 - NINFO [Jim_Reid] NINFO/ninfo-completed-template 2008-01-21 */
+ "RKEY", /* 57 - RKEY [Jim_Reid] RKEY/rkey-completed-template 2008-01-21 */
+ "TALINK", /* 58 - Trust Anchor LINK [Wouter_Wijngaards] TALINK/talink-completed-template 2010-02-17 */
+ "CDS", /* 59 - Child DS [RFC7344] CDS/cds-completed-template 2011-06-06 */
+ "CDNSKEY", /* 60 - DNSKEY(s) the Child wants reflected in DS [RFC7344] 2014-06-16 */
+ "OPENPGPKEY", /* 61 - OpenPGP Key [RFC7929] OPENPGPKEY/openpgpkey-completed-template 2014-08-12 */
+ "CSYNC", /* 62 - Child-To-Parent Synchronization [RFC7477] 2015-01-27 */
+ "ZONEMD", /* 63 - Message Digest Over Zone Data [RFC8976] ZONEMD/zonemd-completed-template 2018-12-12 */
+ "SVCB", /* 64 - Service Binding [draft-ietf-dnsop-svcb-https-00] SVCB/svcb-completed-template 2020-06-30 */
+ "HTTPS", /* 65 - HTTPS Binding [draft-ietf-dnsop-svcb-https-00] HTTPS/https-completed-template 2020-06-30 */
+};
+
+
+static const char *typestr_99[] = {
+ "SPF", /* 99 - [RFC7208] */
+ "UINFO", /* 100 - [IANA-Reserved] */
+ "UID", /* 101 - [IANA-Reserved] */
+ "GID", /* 102 - [IANA-Reserved] */
+ "UNSPEC", /* 103 - [IANA-Reserved] */
+ "NID", /* 104 - [RFC6742] ILNP/nid-completed-template */
+ "L32", /* 105 - [RFC6742] ILNP/l32-completed-template */
+ "L64", /* 106 - [RFC6742] ILNP/l64-completed-template */
+ "LP", /* 107 - [RFC6742] ILNP/lp-completed-template */
+ "EUI48", /* 108 - an EUI-48 address [RFC7043] EUI48/eui48-completed-template 2013-03-27 */
+ "EUI64", /* 109 - an EUI-64 address [RFC7043] EUI64/eui64-completed-template 2013-03-27 */
+};
+
+static const char *typestr_249[] = {
+ "TKEY", /* 249 - Transaction Key [RFC2930] */
+ "TSIG", /* 250 - Transaction Signature [RFC8945] */
+ "IXFR", /* 251 - incremental transfer [RFC1995] */
+ "AXFR", /* 252 - transfer of an entire zone [RFC1035][RFC5936] */
+ "MAILB", /* 253 - mailbox-related RRs (MB, MG or MR) [RFC1035] */
+ "MAILA", /* 254 - mail agent RRs (OBSOLETE - see MX) [RFC1035] */
+ "ANY", /* 255 - A request for some or all records the server has available [RFC1035][RFC6895][RFC8482] */
+ "URI", /* 256 - URI [RFC7553] URI/uri-completed-template 2011-02-22 */
+ "CAA", /* 257 - Certification Authority Restriction [RFC8659] CAA/caa-completed-template 2011-04-07 */
+ "AVC", /* 258 - Application Visibility and Control [Wolfgang_Riedel] AVC/avc-completed-template 2016-02-26 */
+ "DOA", /* 259 - Digital Object Architecture [draft-durand-doa-over-dns] DOA/doa-completed-template 2017-08-30 */
+ "AMTRELAY", /* 260 - Automatic Multicast Tunneling Relay [RFC8777] AMTRELAY/amtrelay-completed-template 2019-02-06 */
+};
+
+static const char *typestr_32768[] = {
+ "TA", /* 32768 - DNSSEC Trust Authorities [Sam_Weiler][http://cameo.library.cmu.edu/][ Deploying DNSSEC Without a Signed Root. Technical Report 1999-19, Information Networking Institute, Carnegie Mellon University, April 2004.] 2005-12-13 */
+ "DLV", /* 32769 - DNSSEC Lookaside Validation (OBSOLETE) [RFC8749][RFC4431] */
+};
+
+
+#define OFFSET_ARRAY(o, a) { o, o+countof(a), a }
static const struct {
- unsigned int type;
- const char * const name;
-} typestr[] = {
- { 1, "A" },
- { 2, "NS" },
- { 5, "CNAME" },
- { 6, "SOA" },
- { 10, "NULL" },
- { 11, "WKS" },
- { 12, "PTR" },
- { 13, "HINFO" },
- { 15, "MX" },
- { 16, "TXT" },
- { 22, "NSAP" },
- { 23, "NSAP_PTR" },
- { 24, "SIG" },
- { 25, "KEY" },
- { 28, "AAAA" },
- { 29, "LOC" },
- { 33, "SRV" },
- { 35, "NAPTR" },
- { 36, "KX" },
- { 37, "CERT" },
- { 38, "A6" },
- { 39, "DNAME" },
- { 41, "OPT" },
- { 43, "DS" },
- { 46, "RRSIG" },
- { 47, "NSEC" },
- { 48, "DNSKEY" },
- { 50, "NSEC3" },
- { 51, "NSEC3PARAM" },
- { 52, "TLSA" },
- { 53, "SMIMEA" },
- { 55, "HIP" },
- { 249, "TKEY" },
- { 250, "TSIG" },
- { 251, "IXFR" },
- { 252, "AXFR" },
- { 253, "MAILB" },
- { 254, "MAILA" },
- { 255, "ANY" },
- { 257, "CAA" }
+ unsigned int offset;
+ unsigned int end;
+ const char ** const names;
+} typedb[] = {
+ OFFSET_ARRAY( 1, typestr_1 ),
+ OFFSET_ARRAY( 99, typestr_99 ),
+ OFFSET_ARRAY( 249, typestr_249 ),
+ OFFSET_ARRAY( 32768, typestr_32768 ),
};
+#undef OFFSET_ARRAY
static void cache_free(struct crec *crecp);
static void cache_unlink(struct crec *crecp);
@@ -162,7 +235,7 @@ static void rehash(int size)
static struct crec **hash_bucket(char *name)
{
unsigned int c, val = 017465; /* Barker code - minimum self-correlation in cyclic shift */
- const unsigned char *mix_tab = (const unsigned char*)typestr;
+ const unsigned char *mix_tab = (const unsigned char*)typestr_1;
while((c = (unsigned char) *name++))
{
@@ -1805,7 +1878,7 @@ char *record_source(unsigned int index)
return "<unknown>";
}
-static char *querystr(char *desc, unsigned short type)
+static char *querystr(const char *desc, unsigned short type)
{
unsigned int i;
int len = 10; /* strlen("type=xxxxx") */
@@ -1813,11 +1886,13 @@ static char *querystr(char *desc, unsigned short type)
static char *buff = NULL;
static int bufflen = 0;
- for (i = 0; i < (sizeof(typestr)/sizeof(typestr[0])); i++)
- if (typestr[i].type == type)
+ /* typedb is offset sorted */
+ for (i = 0; i < countof(typedb) && type >= typedb[i].offset; i++)
+ if (type < typedb[i].end)
{
- types = typestr[i].name;
- len = strlen(types);
+ types = typedb[i].names[type-typedb[i].offset];
+ if (types)
+ len = strlen(types);
break;
}
diff --git a/src/dnsmasq.h b/src/dnsmasq.h
index 56a3f1d..a11ccda 100644
--- a/src/dnsmasq.h
+++ b/src/dnsmasq.h
@@ -70,7 +70,7 @@ typedef unsigned short u16;
typedef unsigned int u32;
typedef unsigned long long u64;
-#define countof(x) (long)(sizeof(x) / sizeof(x[0]))
+#define countof(x) (sizeof(x) / sizeof(x[0]))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#include "dns-protocol.h"
--
2.31.1
_______________________________________________
Dnsmasq-discuss mailing list
Dnsmasq-discuss@lists.thekelleys.org.uk
https://lists.thekelleys.org.uk/cgi-bin/mailman/listinfo/dnsmasq-discuss
