From 1a7c9a486d397cd58814616923af501282c43a26 Mon Sep 17 00:00:00 2001 From: Jeremy Harris Date: Sun, 11 Feb 2018 23:16:02 +0000 Subject: [PATCH] Revert "Macros: convert to tree for speed of lookup" This reverts commit 165acdd1ea3b7399b2279f94c881f8e366efaf71. --- doc/doc-txt/ChangeLog | 5 -- src/OS/Makefile-Base | 27 +++--- src/OS/os.c-SunOS5 | 13 +-- src/OS/os.h-SunOS5 | 2 - src/scripts/MakeLinks | 2 +- src/src/exim.c | 81 +++++++++--------- src/src/functions.h | 4 - src/src/globals.h | 4 +- src/src/macro.c | 137 ------------------------------- src/src/macro_predef.c | 62 +++----------- src/src/readconf.c | 181 ++++++++++++++++++++++++++--------------- src/src/structs.h | 43 +++------- src/src/tree.c | 51 ++++++------ 13 files changed, 218 insertions(+), 394 deletions(-) delete mode 100644 src/src/macro.c diff --git a/doc/doc-txt/ChangeLog b/doc/doc-txt/ChangeLog index 8ae418ab1..088c3d358 100644 --- a/doc/doc-txt/ChangeLog +++ b/doc/doc-txt/ChangeLog @@ -96,11 +96,6 @@ JH/17 Bug 2113: Fix conversation closedown with the Avast malware scanner. found indication; now we go on to read the "scan ok" response line, and send a quit. -JH/18 Convert macro handling to be tree-based, from the previous linear list. - With the number of builtin macros we now have this is worthwhile, - dropping the config-file read time (during which new macros are checked - and registered, and macros are expanded) from about 500 usec to about 180. - Exim version 4.90 ----------------- diff --git a/src/OS/Makefile-Base b/src/OS/Makefile-Base index 91ab876f9..eefc02bbd 100644 --- a/src/OS/Makefile-Base +++ b/src/OS/Makefile-Base @@ -36,7 +36,7 @@ FE = $(FULLECHO) # are set up, and finally it goes to the main Exim target. all: utils exim -config: $(EDITME) checklocalmake Makefile os.c config.h version.h version.sh macro_defs.c +config: $(EDITME) checklocalmake Makefile os.c config.h version.h version.sh macro.c checklocalmake: @if $(SHELL) $(SCRIPTS)/newer $(EDITME)-$(OSTYPE) $(EDITME) || \ @@ -135,7 +135,7 @@ OBJ_MACRO = macro_predef.o \ macro-manualroute.o macro-queryprogram.o macro-redirect.o \ macro-auth-spa.o macro-cram_md5.o macro-cyrus_sasl.o macro-dovecot.o macro-gsasl_exim.o \ macro-heimdal_gssapi.o macro-plaintext.o macro-spa.o macro-authtls.o \ - macro-dkim.o macro-malware.o macro-macro.o macro-tree.o macro-signing.o + macro-dkim.o macro-malware.o macro-signing.o $(OBJ_MACRO): $(MACRO_HSRC) @@ -229,12 +229,6 @@ macro-dkim.o: dkim.c macro-malware.o: malware.c @echo "$(CC) -DMACRO_PREDEF malware.c" $(FE)$(CC) -c $(CFLAGS) -DMACRO_PREDEF $(INCLUDE) -o $@ malware.c -macro-macro.o: macro.c - @echo "$(CC) -DMACRO_PREDEF macro.c" - $(FE)$(CC) -c $(CFLAGS) -DMACRO_PREDEF $(INCLUDE) -o $@ macro.c -macro-tree.o: tree.c - @echo "$(CC) -DMACRO_PREDEF tree.c" - $(FE)$(CC) -c $(CFLAGS) -DMACRO_PREDEF $(INCLUDE) -o $@ tree.c macro-signing.o: pdkim/signing.c @echo "$(CC) -DMACRO_PREDEF pdkim/signing.c" $(FE)$(CC) -c $(CFLAGS) -DMACRO_PREDEF $(INCLUDE) -o $@ pdkim/signing.c @@ -243,8 +237,8 @@ macro_predef: $(OBJ_MACRO) @echo "$(LNCC) -o $@" $(FE)$(LNCC) -o $@ $(LFLAGS) $(OBJ_MACRO) -macro_defs.c: macro_predef - ./macro_predef > macro_defs.c +macro.c: macro_predef + ./macro_predef > macro.c # This target is recognized specially by GNU make. It records those targets # that do not correspond to files that are being built and which should @@ -498,13 +492,14 @@ OBJ_EXPERIMENTAL = bmi_spam.o \ OBJ_LOOKUPS = lookups/lf_quote.o lookups/lf_check_file.o lookups/lf_sqlperform.o OBJ_EXIM = acl.o base64.o child.o crypt16.o daemon.o dbfn.o debug.o deliver.o \ - dkim.o dkim_transport.o directory.o dns.o drtables.o enq.o exim.o \ - expand.o environment.o filter.o filtertest.o globals.o hash.o \ - header.o host.o ip.o log.o lss.o macro.o macro_defs.o match.o moan.o \ + directory.o dns.o drtables.o enq.o exim.o expand.o filter.o \ + filtertest.o globals.o dkim.o dkim_transport.o hash.o \ + header.o host.o ip.o log.o lss.o match.o moan.o \ os.o parse.o queue.o \ rda.o readconf.o receive.o retry.o rewrite.o rfc2047.o \ route.o search.o sieve.o smtp_in.o smtp_out.o spool_in.o spool_out.o \ std-crypto.o store.o string.o tls.o tod.o transport.o tree.o verify.o \ + environment.o macro.o \ $(OBJ_LOOKUPS) \ local_scan.o $(EXIM_PERL) $(OBJ_WITH_CONTENT_SCAN) \ $(OBJ_EXPERIMENTAL) @@ -776,8 +771,6 @@ dbfn.o: $(HDRS) dbfn.c debug.o: $(HDRS) debug.c deliver.o: $(HDRS) transports/smtp.h deliver.c directory.o: $(HDRS) directory.c -dkim.o: $(HDRS) pdkim/pdkim.h dkim.c -dkim_transport.o: $(HDRS) dkim_transport.c dns.o: $(HDRS) dns.c enq.o: $(HDRS) enq.c exim.o: $(HDRS) exim.c @@ -792,8 +785,6 @@ host.o: $(HDRS) host.c ip.o: $(HDRS) ip.c log.o: $(HDRS) log.c lss.o: $(HDRS) lss.c -macro.o: $(HDRS) macro.c -macro_defs.o: $(HDRS) macro_defs.c match.o: $(HDRS) match.c moan.o: $(HDRS) moan.c os.o: $(HDRS) $(OS_C_INCLUDES) os.c @@ -822,6 +813,8 @@ tod.o: $(HDRS) tod.c transport.o: $(HDRS) transport.c tree.o: $(HDRS) tree.c verify.o: $(HDRS) transports/smtp.h verify.c +dkim.o: $(HDRS) pdkim/pdkim.h dkim.c +dkim_transport.o: $(HDRS) dkim_transport.c # Dependencies for WITH_CONTENT_SCAN modules diff --git a/src/OS/os.c-SunOS5 b/src/OS/os.c-SunOS5 index 8ad8c9380..162486958 100644 --- a/src/OS/os.c-SunOS5 +++ b/src/OS/os.c-SunOS5 @@ -3,7 +3,7 @@ *************************************************/ /* Copyright (c) University of Cambridge 2016 */ -/* Copyright (c) Jeremy Harris 2018 */ +/* Copyright (c) Jeremy Harris 2016 */ /* See the file NOTICE for conditions of use and distribution. */ /* Solaris-specific code. This is concatenated onto the generic @@ -13,15 +13,4 @@ src/os.c file. */ # include "setenv.c" #endif -/* This is missing in Solaris 10, present in Solaris 11. -A feature-test would be good. */ - -char * -strndup(const char * s, unsigned long n) -{ -char * dest; -if (!(dest = malloc(n))) return NULL; -return strncpy(dest, s, n); -} - /* End of os.c-SunOS5 */ diff --git a/src/OS/os.h-SunOS5 b/src/OS/os.h-SunOS5 index 113adc05f..dfbd8f1af 100644 --- a/src/OS/os.h-SunOS5 +++ b/src/OS/os.h-SunOS5 @@ -48,6 +48,4 @@ a buffer */ # define MAX(a,b) (((a)>(b))?(a):(b)) #endif -extern char * strndup(const char *, unsigned long); - /* End */ diff --git a/src/scripts/MakeLinks b/src/scripts/MakeLinks index 7427a8a2b..6314fe441 100755 --- a/src/scripts/MakeLinks +++ b/src/scripts/MakeLinks @@ -110,7 +110,7 @@ for f in blob.h dbfunctions.h dbstuff.h exim.h functions.h globals.h \ tod.c transport.c tree.c verify.c version.c \ dkim.c dkim.h dkim_transport.c dmarc.c dmarc.h \ valgrind.h memcheck.h \ - macro.c macro_predef.c macro_predef.h + macro_predef.c macro_predef.h do ln -s ../src/$f $f done diff --git a/src/src/exim.c b/src/src/exim.c index 354cdf7a8..327a8ecfe 100644 --- a/src/src/exim.c +++ b/src/src/exim.c @@ -1295,32 +1295,6 @@ exit(EXIT_FAILURE); * Validate that the macros given are okay * *************************************************/ -#ifdef WHITELIST_D_MACROS -static void -wlist_check(uschar * name, uschar * val, void * ctx) -{ -uschar ** w, ** whites = ctx; -unsigned len; -int n; - -for (w = whites; *w; ++w) - if (Ustrcmp(*w, name) == 0) break; -if (*w) - { - if (!val || !*val) return; - len = Ustrlen(val); - if ((n = pcre_exec(regex_whitelisted_macro, NULL, CS val, len, - 0, PCRE_EOPT, NULL, 0)) >= 0) - return; - if (n != PCRE_ERROR_NOMATCH) - debug_printf("macros_trusted checking %s returned %d\n", name, n); - } -*whites = NULL; -return; -} -#endif - - /* Typically, Exim will drop privileges if macros are supplied. In some cases, we want to not do so. @@ -1333,7 +1307,7 @@ macros_trusted(BOOL opt_D_used) { #ifdef WHITELIST_D_MACROS macro_item *m; -uschar *whitelisted, *end, *p, **whites; +uschar *whitelisted, *end, *p, **whites, **w; int white_count, i, n; size_t len; BOOL prev_char_item, found; @@ -1396,9 +1370,32 @@ for (p = whitelisted, i = 0; (p != end) && (i < white_count); ++p) } whites[i] = NULL; -tree_walk(tree_macros, wlist_check, whites); -if (!*whites) return FALSE; - +/* The list of commandline macros should be very short. +Accept the N*M complexity. */ +for (m = macros; m; m = m->next) if (m->command_line) + { + found = FALSE; + for (w = whites; *w; ++w) + if (Ustrcmp(*w, m->name) == 0) + { + found = TRUE; + break; + } + if (!found) + return FALSE; + if (!m->replacement) + continue; + if ((len = m->replen) == 0) + continue; + n = pcre_exec(regex_whitelisted_macro, NULL, CS m->replacement, len, + 0, PCRE_EOPT, NULL, 0); + if (n < 0) + { + if (n != PCRE_ERROR_NOMATCH) + debug_printf("macros_trusted checking %s returned %d\n", m->name, n); + return FALSE; + } + } DEBUG(D_any) debug_printf("macros_trusted overridden to true by whitelisting\n"); return TRUE; #endif @@ -1430,10 +1427,7 @@ len = Ustrlen(big_buffer); if (isupper(big_buffer[0])) { if (macro_read_assignment(big_buffer)) - { - uschar * s = Ustrchr(big_buffer, '='); - printf("Defined macro '%.*s'\n", (int)(s - big_buffer), big_buffer); - } + printf("Defined macro '%s'\n", mlast->name); } else if ((line = expand_string(big_buffer))) printf("%s\n", CS line); @@ -2428,21 +2422,22 @@ for (i = 1; i < argc; i++) while (isspace(*s)) s++; } - if (macro_search(name)) - { - fprintf(stderr, "exim: duplicated -D in command line\n"); - exit(EXIT_FAILURE); - } + for (m = macros; m; m = m->next) + if (Ustrcmp(m->name, name) == 0) + { + fprintf(stderr, "exim: duplicated -D in command line\n"); + exit(EXIT_FAILURE); + } - m = macro_create(name, s, TRUE); + m = macro_create(string_copy(name), string_copy(s), TRUE); if (clmacro_count >= MAX_CLMACROS) { fprintf(stderr, "exim: too many -D options on command line\n"); exit(EXIT_FAILURE); } - clmacros[clmacro_count++] = string_sprintf("-D%s=%s", - m->tnode.name, m->tnode.data.ptr); + clmacros[clmacro_count++] = string_sprintf("-D%s=%s", m->name, + m->replacement); } #endif break; @@ -4993,7 +4988,7 @@ if (expansion_test) /* Only admin users may see config-file macros this way */ - if (!admin_user) tree_macros = NULL; + if (!admin_user) macros = mlast = NULL; /* Allow $recipients for this testing */ diff --git a/src/src/functions.h b/src/src/functions.h index 2a4e54aeb..00da0cf20 100644 --- a/src/src/functions.h +++ b/src/src/functions.h @@ -256,10 +256,6 @@ extern int log_create_as_exim(uschar *); extern void log_close_all(void); extern macro_item * macro_create(const uschar *, const uschar *, BOOL); -extern macro_item * macro_search(const uschar *); -extern macro_item * macro_search_largest_prefix(const uschar *); -extern macro_item * macro_search_prefix(const uschar *); -extern void macro_print(uschar *, uschar *, void *); extern BOOL macro_read_assignment(uschar *); extern uschar *macros_expand(int, int *, BOOL *); extern void mainlog_close(void); diff --git a/src/src/globals.h b/src/src/globals.h index 468bfa917..766b8a42f 100644 --- a/src/src/globals.h +++ b/src/src/globals.h @@ -565,7 +565,8 @@ extern uschar *lookup_dnssec_authenticated; /* AD status of dns lookup */ extern int lookup_open_max; /* Max lookup files to cache */ extern uschar *lookup_value; /* Value looked up from file */ -extern unsigned m_number; /* count of macros */ +extern macro_item *macros; /* Configuration macros */ +extern macro_item *mlast; /* Last item in macro list */ extern uschar *mailstore_basename; /* For mailstore deliveries */ #ifdef WITH_CONTENT_SCAN extern uschar *malware_name; /* Name of virus or malware ("W32/Klez-H") */ @@ -954,7 +955,6 @@ extern int transport_write_timeout;/* Set to time out individual writes */ extern tree_node *tree_dns_fails; /* Tree of DNS lookup failures */ extern tree_node *tree_duplicates; /* Tree of duplicate addresses */ extern tree_node *tree_nonrecipients; /* Tree of nonrecipient addresses */ -extern tree_node *tree_macros; /* Configuration macros */ extern tree_node *tree_unusable; /* Tree of unusable addresses */ extern BOOL trusted_caller; /* Caller is trusted */ diff --git a/src/src/macro.c b/src/src/macro.c deleted file mode 100644 index 21e51044e..000000000 --- a/src/src/macro.c +++ /dev/null @@ -1,137 +0,0 @@ -/************************************************* -* Exim - an Internet mail transport agent * -*************************************************/ - -/* Copyright (c) University of Cambridge 1995 - 2018 */ -/* See the file NOTICE for conditions of use and distribution. */ - -/* Functions for handling macros */ - -#include "exim.h" - -#ifdef MACRO_PREDEF -# undef store_get -# define store_get(nbytes) malloc((size_t)(nbytes)) -#define string_copyn(s, len) strndup(CS(s), (len)) -#endif - -/************************************************* -* Deal with an assignment to a macro * -*************************************************/ - -/* We have a new definition; add to the collection. -Items are numbered so we can avoid recursion in expansions. - -Args: - name Name of the macro. Will be copied. - val Expansion result for the macro. Will be copied. -*/ - -macro_item * -macro_create(const uschar * name, const uschar * val, BOOL command_line) -{ -int namelen = Ustrlen(name); -macro_item * m = store_get(sizeof(macro_item) + namelen); - -/* fprintf(stderr, "%s: '%s' '%s'\n", __FUNCTION__, name, val); */ - -m->command_line = command_line; -m->namelen = namelen; -m->replen = Ustrlen(val); -m->m_number = m_number++; -memset(&m->tnode, 0, sizeof(tree_node)); -/* Use memcpy here not Ustrcpy to avoid spurious compiler-inserted check -when building with fortify-source. We know there is room for the copy into -this dummy for a variable-size array because of the way we did the memory -allocation above. */ -memcpy(m->tnode.name, name, namelen+1); -m->tnode.data.ptr = string_copyn(val, m->replen); -(void) tree_insertnode(&tree_macros, &m->tnode); - -return m; -} - - -/* Search for a macro, with an exact match on the name. -Return the node, or NULL for not-found. - -Arguments: name key to search for -*/ - -macro_item * -macro_search(const uschar * name) -{ -tree_node * t; - -t = tree_search(tree_macros, name); -return tnode_to_mitem(t); -} - - -/* Search for a macro with a (possibly improper) leading substring -matching the given name. Return the node, or NULL for not-found. - -Arguments: name key to search on -*/ - -macro_item * -macro_search_prefix(const uschar * s) -{ -tree_node * t; -int c; - -for (t = tree_macros; t; t = c < 0 ? t->left : t->right) - if ((c = Ustrncmp(s, t->name, tnode_to_mitem(t)->namelen)) == 0) - return tnode_to_mitem(t); -return NULL; -} - - -/* Search for the macro with the largest possible leading substring -matching the given name. */ - -macro_item * -macro_search_largest_prefix(const uschar * s) -{ -macro_item * found; -tree_node * child; -int c; - -if ((found = macro_search_prefix(s))) - { - /* There could be a node with a larger substring also matching the - name. If so it must be in the right subtree; either the right child - or (if that sorts after the name) in the left subtree of the right child. */ - - child = found->tnode.right; - while (child) - if ((c = Ustrncmp(s, child->name, tnode_to_mitem(child)->namelen)) == 0) - { - found = tnode_to_mitem(child); - child = found->tnode.right; - } - else if (c < 0 && (child = child->left)) - continue; - else - break; - } -return found; -} - - - -void -macro_print(uschar * name, uschar * val, void * ctx) -{ -BOOL names_only = (BOOL)(long)ctx; -if (names_only) - printf("%s\n", CS name); -else - printf("%s=%s\n", CS name, CS val); -} - - - -/* vi: aw ai sw=2 -*/ -/* End of macro.c */ diff --git a/src/src/macro_predef.c b/src/src/macro_predef.c index 30b5e8a54..0d70826bb 100644 --- a/src/src/macro_predef.c +++ b/src/src/macro_predef.c @@ -11,8 +11,7 @@ included in the main Exim build */ #include "exim.h" #include "macro_predef.h" -tree_node * tree_macros = NULL; -unsigned m_number = 1; +unsigned mp_index = 0; /* Global dummy variables */ @@ -24,7 +23,16 @@ uschar * syslog_facility_str; void builtin_macro_create_var(const uschar * name, const uschar * val) { -macro_create(name, val, FALSE); +printf ("static macro_item p%d = { ", mp_index); +if (mp_index == 0) + printf(".next=NULL,"); +else + printf(".next=&p%d,", mp_index-1); + +printf(" .command_line=FALSE, .namelen=%d, .replen=%d," + " .name=US\"%s\", .replacement=US\"%s\" };\n", + Ustrlen(name), Ustrlen(val), CS name, CS val); +mp_index++; } @@ -281,59 +289,15 @@ params_dkim(); } -static unsigned -macro_dump(macro_item * m) -{ -int left = 0, right = 0; -tree_node * t; -macro_item_64 * m64; - -/* fprintf(stderr, "%s %p\n", __FUNCTION__, m); */ - -if (!m) return 0; -/* fprintf(stderr, "%s '%s' l %p r %p\n", __FUNCTION__, m->tnode.name, m->tnode.left, m->tnode.left); */ -if ((t = m->tnode.left)) left = macro_dump(tnode_to_mitem(m->tnode.left)); -if ((t = m->tnode.right)) right = macro_dump(tnode_to_mitem(m->tnode.right)); - -printf ("static macro_item_64 p%u = { ", m->m_number); -printf(" .command_line=FALSE," - " .namelen=%d," - " .replen=%d," - " .m_number=%u," - " .tnode={", - Ustrlen(m->tnode.name), Ustrlen(m->tnode.data.ptr), m->m_number); -printf(left ? " .left=&p%d.tnode," : " .left=NULL,", left); -printf(right ? " .right=&p%d.tnode," : " .right=NULL,", right); -printf( - " .data.ptr=\"%s\"," - " .balance=%d," - " .name=\"%s\"}};\n", - CS m->tnode.data.ptr, - m->tnode.balance, - CS m->tnode.name); - -if (Ustrlen(m->tnode.name) +1 > sizeof(m64->tnode.name)) - { - printf("#error macro name too long for macro_item_64\n"); - exit(1); - } -return m->m_number; -} - - - int main(void) { -unsigned idx; - printf("#include \"exim.h\"\n"); features(); options(); params(); -idx = macro_dump(tnode_to_mitem(tree_macros)); -printf("tree_node * tree_macros = (tree_node *) &p%u.tnode;\n", idx); -printf("unsigned m_number = %u;\n", m_number); +printf("macro_item * macros = &p%d;\n", mp_index-1); +printf("macro_item * mlast = &p0;\n"); exit(0); } diff --git a/src/src/readconf.c b/src/src/readconf.c index 42bb5afe5..5d519e996 100644 --- a/src/src/readconf.c +++ b/src/src/readconf.c @@ -592,6 +592,38 @@ return US""; +/************************************************* +* Deal with an assignment to a macro * +*************************************************/ + +/* We have a new definition; append to the list. + +Args: + name Name of the macro. Must be in storage persistent past the call + val Expansion result for the macro. Ditto persistence. +*/ + +macro_item * +macro_create(const uschar * name, const uschar * val, BOOL command_line) +{ +macro_item * m = store_get(sizeof(macro_item)); + +/* fprintf(stderr, "%s: '%s' '%s'\n", __FUNCTION__, name, val); */ +m->next = NULL; +m->command_line = command_line; +m->namelen = Ustrlen(name); +m->replen = Ustrlen(val); +m->name = name; +m->replacement = val; +if (mlast) + mlast->next = m; +else + macros = m; +mlast = m; +return m; +} + + /* This function is called when a line that starts with an upper case letter is encountered. The argument "line" should contain a complete logical line, and start with the first letter of the macro name. The macro name and the @@ -642,37 +674,53 @@ while (isspace(*s)) s++; just skip this definition. It's an error to attempt to redefine a macro without redef set to TRUE, or to redefine a macro when it hasn't been defined earlier. It is also an error to define a macro whose name begins with the name of a -previously defined macro. +previously defined macro. This is the requirement that make using a tree +for macros hard; we must check all macros for the substring. Perhaps a +sorted list, and a bsearch, would work? Note: it is documented that the other way round works. */ -if ((m = macro_search_prefix(name))) +for (m = macros; m; m = m->next) { - if (m->namelen < namelen) /* substring match */ + if (Ustrcmp(m->name, name) == 0) { - log_write(0, LOG_CONFIG|LOG_PANIC, "\"%s\" cannot be defined as " - "a macro because previously defined macro \"%s\" is a substring", - name, m->tnode.name); - return FALSE; + if (!m->command_line && !redef) + { + log_write(0, LOG_CONFIG|LOG_PANIC, "macro \"%s\" is already " + "defined (use \"==\" if you want to redefine it", name); + return FALSE; + } + break; } - /* exact match */ - if (!m->command_line && !redef) + + if (m->namelen < namelen && Ustrstr(name, m->name) != NULL) { - log_write(0, LOG_CONFIG|LOG_PANIC, "macro \"%s\" is already " - "defined (use \"==\" if you want to redefine it", name); + log_write(0, LOG_CONFIG|LOG_PANIC, "\"%s\" cannot be defined as " + "a macro because previously defined macro \"%s\" is a substring", + name, m->name); return FALSE; } - if (m->command_line) /* overriding cmdline definition */ - return TRUE; + /* We cannot have this test, because it is documented that a substring + macro is permitted (there is even an example). + * + * if (m->namelen > namelen && Ustrstr(m->name, name) != NULL) + * log_write(0, LOG_CONFIG|LOG_PANIC_DIE, "\"%s\" cannot be defined as " + * "a macro because it is a substring of previously defined macro \"%s\"", + * name, m->name); + */ } +/* Check for an overriding command-line definition. */ + +if (m && m->command_line) return TRUE; + /* Redefinition must refer to an existing macro. */ if (redef) if (m) { m->replen = Ustrlen(s); - m->tnode.data.ptr = string_copy(s); + m->replacement = string_copy(s); } else { @@ -683,7 +731,7 @@ if (redef) /* We have a new definition. */ else - (void) macro_create(name, s, FALSE); + (void) macro_create(string_copy(name), string_copy(s), FALSE); return TRUE; } @@ -708,6 +756,7 @@ macros_expand(int len, int * newlen, BOOL * macro_found) { uschar * ss = big_buffer + len; uschar * s; +macro_item * m; /* Find the true start of the physical line - leading spaces are always ignored. */ @@ -728,52 +777,56 @@ if (len == 0 && isupper(*s)) if (*s != '=') s = ss; /* Not a macro definition */ } -/* Scan the line (from after XXX= if present), replacing any macros. Rescan -after replacement for any later-defined macros. */ +/* Skip leading chars which cannot start a macro name, to avoid multiple +pointless rescans in Ustrstr calls. */ + +while (*s && !isupper(*s) && *s != '_') s++; + +/* For each defined macro, scan the line (from after XXX= if present), +replacing all occurrences of the macro. */ *macro_found = FALSE; -while (*s) +for (m = macros; m; m = m->next) { - if (isupper(*s) || *s == '_' && isupper(s[1])) - { - macro_item * m; - unsigned mnum = 0; + uschar * p, *pp; + uschar * t = s; - while ((m = macro_search_largest_prefix(s)) && m->m_number > mnum) - { - uschar * pp; - int moveby; + while ((p = Ustrstr(t, m->name)) != NULL) + { + int moveby; - /* Expand the buffer if necessary */ +/* fprintf(stderr, "%s: matched '%s' in '%s'\n", __FUNCTION__, m->name, ss); */ + /* Expand the buffer if necessary */ - while (*newlen - m->namelen + m->replen + 1 > big_buffer_size) - { - int newsize = big_buffer_size + BIG_BUFFER_SIZE; - uschar *newbuffer = store_malloc(newsize); - memcpy(newbuffer, big_buffer, *newlen + 1); - s = newbuffer + (s - big_buffer); - ss = newbuffer + (ss - big_buffer); - big_buffer_size = newsize; - store_free(big_buffer); - big_buffer = newbuffer; - } + while (*newlen - m->namelen + m->replen + 1 > big_buffer_size) + { + int newsize = big_buffer_size + BIG_BUFFER_SIZE; + uschar *newbuffer = store_malloc(newsize); + memcpy(newbuffer, big_buffer, *newlen + 1); + p = newbuffer + (p - big_buffer); + s = newbuffer + (s - big_buffer); + ss = newbuffer + (ss - big_buffer); + t = newbuffer + (t - big_buffer); + big_buffer_size = newsize; + store_free(big_buffer); + big_buffer = newbuffer; + } - /* Shuffle the remaining characters up or down in the buffer before - copying in the replacement text. Don't rescan the replacement for this - same macro. */ + /* Shuffle the remaining characters up or down in the buffer before + copying in the replacement text. Don't rescan the replacement for this + same macro. */ - pp = s + m->namelen; - if ((moveby = m->replen - m->namelen) != 0) - { - memmove(s + m->replen, pp, (big_buffer + *newlen) - pp + 1); - *newlen += moveby; - } - Ustrncpy(s, m->tnode.data.ptr, m->replen); - *macro_found = TRUE; - mnum = m->m_number; + pp = p + m->namelen; + if ((moveby = m->replen - m->namelen) != 0) + { + memmove(p + m->replen, pp, (big_buffer + *newlen) - pp + 1); + *newlen += moveby; } + Ustrncpy(p, m->replacement, m->replen); + t = p + m->replen; + while (*t && !isupper(*t) && *t != '_') t++; + *macro_found = TRUE; } - s++; } /* An empty macro replacement at the start of a line could mean that ss no @@ -2810,25 +2863,26 @@ else if (Ustrcmp(type, "macro") == 0) fprintf(stderr, "exim: permission denied\n"); return FALSE; } - - if (name) - if ((m = macro_search(name))) - macro_print(m->tnode.name, m->tnode.data.ptr, (void *)(long)names_only); - else + for (m = macros; m; m = m->next) + if (!name || Ustrcmp(name, m->name) == 0) { - printf("%s %s not found\n", type, name); - return FALSE; + if (names_only) + printf("%s\n", CS m->name); + else + printf("%s=%s\n", CS m->name, CS m->replacement); + if (name) + return TRUE; } - else - tree_walk(tree_macros, macro_print, (void *)(long)names_only); + if (!name) return TRUE; - return TRUE; + printf("%s %s not found\n", type, name); + return FALSE; } if (names_only) { for (; d; d = d->next) printf("%s\n", CS d->name); - return TRUE;; + return TRUE; } /* Either search for a given driver, or print all of them */ @@ -2838,8 +2892,7 @@ for (; d; d = d->next) BOOL rc = FALSE; if (!name) printf("\n%s %s:\n", d->name, type); - else if (Ustrcmp(d->name, name) != 0) - continue; + else if (Ustrcmp(d->name, name) != 0) continue; for (ol = ol2; ol < ol2 + size; ol++) if (!(ol->type & opt_hidden)) diff --git a/src/src/structs.h b/src/src/structs.h index c8798e366..dfe5685e6 100644 --- a/src/src/structs.h +++ b/src/src/structs.h @@ -32,6 +32,17 @@ typedef struct gstring { uschar * s; /* The string memory */ } gstring; +/* Structure for remembering macros for the configuration file */ + +typedef struct macro_item { + struct macro_item * next; + BOOL command_line; + unsigned namelen; + unsigned replen; + const uschar * name; + const uschar * replacement; +} macro_item; + /* Structure for bit tables for debugging and logging */ typedef struct bit_table { @@ -694,38 +705,6 @@ typedef struct tree_node { uschar name[1]; /* node name - variable length */ } tree_node; -typedef struct tree_node_64 { - struct tree_node_64 *left; /* pointer to left child */ - struct tree_node_64 *right; /* pointer to right child */ - union - { - void *ptr; /* pointer to data */ - int val; /* or integer data */ - } data; - uschar balance; /* balancing factor */ - uschar name[64]; /* node name - bounded length */ -} tree_node_64; - -/* Structure for remembering macros for the configuration file */ - -typedef struct macro_item { - BOOL command_line; - unsigned namelen; - unsigned replen; - unsigned m_number; - tree_node tnode; /* contains name; ptr indicates val */ -} macro_item; - -typedef struct macro_item_64 { - BOOL command_line; - unsigned namelen; - unsigned replen; - unsigned m_number; - tree_node_64 tnode; /* contains name; ptr indicates val */ -} macro_item_64; - -#define tnode_to_mitem(tp) (tp ? (macro_item *) (CS(tp) - offsetof(macro_item, tnode)) : NULL) - /* Structure for holding time-limited data such as DNS returns. We use this rather than extending tree_node to avoid wasting space for most tree use (variables...) at the cost of complexity diff --git a/src/src/tree.c b/src/src/tree.c index b5918a6a3..3b6c3603b 100644 --- a/src/src/tree.c +++ b/src/src/tree.c @@ -12,7 +12,6 @@ functions as well. */ #include "exim.h" -#ifndef MACRO_PREDEF /************************************************* @@ -116,9 +115,10 @@ Returns: nothing static void write_tree(tree_node *p, FILE *f) { -fprintf(f, "%c%c %s\n", p->left ? 'Y':'N', p->right ? 'Y':'N', p->name); -if (p->left) write_tree(p->left, f); -if (p->right) write_tree(p->right, f); +fprintf(f, "%c%c %s\n", + (p->left == NULL)? 'N':'Y', (p->right == NULL)? 'N':'Y', p->name); +if (p->left != NULL) write_tree(p->left, f); +if (p->right != NULL) write_tree(p->right, f); } /* This is the top-level function, with the same arguments. */ @@ -126,7 +126,7 @@ if (p->right) write_tree(p->right, f); void tree_write(tree_node *p, FILE *f) { -if (!p) +if (p == NULL) { fprintf(f, "XX\n"); return; @@ -135,7 +135,6 @@ write_tree(p, f); } -#endif @@ -186,7 +185,7 @@ node->balance = 0; /* Deal with an empty tree */ -if (!p) +if (p == NULL) { *treebase = node; return TRUE; @@ -209,9 +208,9 @@ for (;;) /* Deal with climbing down the tree, exiting from the loop when we reach a leaf. */ - q = c > 0 ? &p->right : &p->left; + q = (c > 0)? &(p->right) : &(p->left); p = *q; - if (!p) break; + if (p == NULL) break; /* Save the address of the pointer to the last node en route which has a non-zero balance factor. */ @@ -228,13 +227,14 @@ that is the place at which the new node must be inserted. */ next node after it along the route. */ s = *t; -r = Ustrcmp(node->name, s->name) > 0 ? s->right : s->left; +r = (Ustrcmp(node->name, s->name) > 0)? s->right : s->left; /* Adjust balance factors along the route from s to node. */ p = r; while (p != node) + { if (Ustrcmp(node->name, p->name) < 0) { p->balance = tree_lbal; @@ -245,16 +245,15 @@ while (p != node) p->balance = tree_rbal; p = p->right; } + } /* Now the World-Famous Balancing Act */ -a = Ustrcmp(node->name, s->name) < 0 ? tree_lbal : tree_rbal; +a = (Ustrcmp(node->name, s->name) < 0)? tree_lbal : tree_rbal; -if (s->balance == 0) - s->balance = (uschar)a; /* The tree has grown higher */ -else if (s->balance != (uschar)a) - s->balance = 0; /* It's become more balanced */ -else /* It's got out of balance */ +if (s->balance == 0) s->balance = (uschar)a; /* The tree has grown higher */ + else if (s->balance != (uschar)a) s->balance = 0; /* It's become more balanced */ +else /* It's got out of balance */ { /* Perform a single rotation */ @@ -284,7 +283,7 @@ else /* It's got out of balance */ { if (a == tree_rbal) { - if (!r->left) return TRUE; /* Bail out if tree corrupt */ + if (r->left == NULL) return TRUE; /* Bail out if tree corrupt */ p = r->left; r->left = p->right; p->right = r; @@ -293,7 +292,7 @@ else /* It's got out of balance */ } else { - if (!r->right) return TRUE; /* Bail out if tree corrupt */ + if (r->right == NULL) return TRUE; /* Bail out if tree corrupt */ p = r->right; r->right = p->left; p->left = r; @@ -301,8 +300,8 @@ else /* It's got out of balance */ p->right = s; } - s->balance = p->balance == (uschar)a ? (uschar)(a^tree_bmask) : 0; - r->balance = p->balance == (uschar)(a^tree_bmask) ? (uschar)a : 0; + s->balance = (p->balance == (uschar)a)? (uschar)(a^tree_bmask) : 0; + r->balance = (p->balance == (uschar)(a^tree_bmask))? (uschar)a : 0; p->balance = 0; } @@ -331,15 +330,16 @@ Returns: pointer to node, or NULL if not found tree_node * tree_search(tree_node *p, const uschar *name) { -int c; -for ( ; p; p = c < 0 ? p->left : p->right) - if ((c = Ustrcmp(name, p->name)) == 0) - return p; +while (p) + { + int c = Ustrcmp(name, p->name); + if (c == 0) return p; + p = c < 0 ? p->left : p->right; + } return NULL; } -#ifndef MACRO_PREDEF /************************************************* * Walk tree recursively and execute function * @@ -361,6 +361,5 @@ tree_walk(p->left, f, ctx); tree_walk(p->right, f, ctx); } -#endif /* End of tree.c */ -- 2.25.1