wip
[exim.git] / src / src / search.c
1 /*************************************************
2 *     Exim - an Internet mail transport agent    *
3 *************************************************/
4
5 /* Copyright (c) University of Cambridge 1995 - 2015 */
6 /* Copyright (c) The Exim Maintainers 2020 */
7 /* See the file NOTICE for conditions of use and distribution. */
8
9 /* A set of functions to search databases in various formats. An open
10 database is represented by a void * value which is returned from a lookup-
11 specific "open" function. These are now all held in individual modules in the
12 lookups subdirectory and the functions here form a generic interface.
13
14 Caching is used to improve performance. Open files are cached until a tidyup
15 function is called, and for each file the result of the last lookup is cached.
16 However, if too many files are opened, some of those that are not in use have
17 to be closed. Those open items that use real files are kept on a LRU chain to
18 help with this.
19
20 All the data is held in permanent store so as to be independent of the stacking
21 pool that is reset from time to time. In fact, we use malloc'd store so that it
22 can be freed when the caches are tidied up. It isn't actually clear whether
23 this is a benefit or not, to be honest. */
24
25 #include "exim.h"
26
27
28 /* Tree in which to cache open files until tidyup called. */
29
30 static tree_node *search_tree = NULL;
31
32 /* Two-way chain of open databases that use real files. This is maintained in
33 recently-used order for the purposes of closing the least recently used when
34 too many files are open. */
35
36 static tree_node *open_top = NULL;
37 static tree_node *open_bot = NULL;
38
39 /* Count of open databases that use real files */
40
41 static int open_filecount = 0;
42
43 /* Allow us to reset store used for lookups and lookup caching */
44
45 static rmark search_reset_point = NULL;
46
47
48
49 /*************************************************
50 *      Validate a plain lookup type name         *
51 *************************************************/
52
53 /* Only those names that are recognized and whose code is included in the
54 binary give an OK response. Use a binary chop search now that the list has got
55 so long.
56
57 Arguments:
58   name       lookup type name - not necessarily zero terminated (e.g. dbm*)
59   len        length of the name
60
61 Returns:     +ve => valid lookup name; value is offset in lookup_list
62              -ve => invalid name; message in search_error_message.
63 */
64
65 int
66 search_findtype(const uschar *name, int len)
67 {
68 int bot = 0;
69 int top = lookup_list_count;
70 while (top > bot)
71   {
72   int mid = (top + bot)/2;
73   int c = Ustrncmp(name, lookup_list[mid]->name, len);
74
75   /* If c == 0 we have matched the incoming name with the start of the search
76   type name. However, some search types are substrings of others (e.g. nis and
77   nisplus) so we need to check that the lengths are the same. The length of the
78   type name cannot be shorter (else c would not be 0); if it is not equal it
79   must be longer, and in that case, the incoming name comes before the name we
80   are testing. By leaving c == 0 when the lengths are different, and doing a
81   > 0 test below, this all falls out correctly. */
82
83   if (c == 0 && Ustrlen(lookup_list[mid]->name) == len)
84     {
85     if (lookup_list[mid]->find != NULL) return mid;
86     search_error_message  = string_sprintf("lookup type \"%.*s\" is not "
87       "available (not in the binary - check buildtime LOOKUP configuration)",
88       len, name);
89     return -1;
90     }
91
92   if (c > 0) bot = mid + 1; else top = mid;
93   }
94
95 search_error_message = string_sprintf("unknown lookup type \"%.*s\"",len,name);
96 return -1;
97 }
98
99
100
101 /*************************************************
102 *       Validate a full lookup type name         *
103 *************************************************/
104
105 /* This function recognizes the "partial-" prefix and also terminating * and *@
106 suffixes.
107
108 Arguments:
109   name         the full lookup type name
110   ptypeptr     where to put the partial type
111                  after subtraction of 1024 or 2048:
112                    negative     => no partial matching
113                    non-negative => minimum number of non-wild components
114   ptypeaff     where to put a pointer to the affix
115                  the affix is within name if supplied therein
116                  otherwise it's a literal string
117   afflen       the length of the affix
118   starflags    where to put the SEARCH_STAR and SEARCH_STARAT flags
119   opts         where to put the options
120
121 Returns:     +ve => valid lookup name; value is offset in lookup_list
122              -ve => invalid name; message in search_error_message.
123 */
124
125 int
126 search_findtype_partial(const uschar *name, int *ptypeptr, const uschar **ptypeaff,
127   int *afflen, int *starflags, const uschar ** opts)
128 {
129 int len, stype;
130 int pv = -1;
131 const uschar *ss = name;
132 const uschar * t;
133
134 *starflags = 0;
135 *ptypeaff = NULL;
136
137 /* Check for a partial matching type. It must start with "partial", optionally
138 followed by a sequence of digits. If this is followed by "-", the affix is the
139 default "*." string. Otherwise we expect an affix in parentheses. Affixes are a
140 limited number of characters, not including parens. */
141
142 if (Ustrncmp(name, "partial", 7) == 0)
143   {
144   ss += 7;
145   if (isdigit (*ss))
146     {
147     pv = 0;
148     while (isdigit(*ss)) pv = pv*10 + *ss++ - '0';
149     }
150   else pv = 2;         /* Default number of wild components */
151
152   if (*ss == '(')
153     {
154     *ptypeaff = ++ss;
155     while (ispunct(*ss) && *ss != ')') ss++;
156     if (*ss != ')') goto BAD_TYPE;
157     *afflen = ss++ - *ptypeaff;
158     }
159   else if (*ss++ == '-')
160     {
161     *ptypeaff = US "*.";
162     *afflen = 2;
163     }
164   else
165     {
166     BAD_TYPE:
167     search_error_message = string_sprintf("format error in lookup type \"%s\"",
168       name);
169     return -1;
170     }
171   }
172
173 /* Now we are left with a lookup name, possibly followed by * or *@,
174 and then by options starting with a "," */
175
176 len = Ustrlen(ss);
177 if ((t = Ustrchr(ss, '*')))
178   {
179   len = t - ss;
180   *starflags |= (t[1] == '@' ? SEARCH_STARAT : SEARCH_STAR);
181   }
182 else
183   t = ss;
184
185 if ((t = Ustrchr(t, ',')))
186   {
187   int l = t - ss;
188   if (l < len) len = l;
189   *opts = string_copy(t+1);
190   }
191 else
192   *opts = NULL;
193
194 /* Check for the individual search type. Only those that are actually in the
195 binary are valid. For query-style types, "partial" and default types are
196 erroneous. */
197
198 stype = search_findtype(ss, len);
199 if (stype >= 0 && mac_islookup(stype, lookup_querystyle))
200   {
201   if (pv >= 0)
202     {
203     search_error_message = string_sprintf("\"partial\" is not permitted "
204       "for lookup type \"%s\"", ss);
205     return -1;
206     }
207   if ((*starflags & (SEARCH_STAR|SEARCH_STARAT)) != 0)
208     {
209     search_error_message = string_sprintf("defaults using \"*\" or \"*@\" are "
210       "not permitted for lookup type \"%s\"", ss);
211     return -1;
212     }
213   }
214
215 *ptypeptr = pv;
216 return stype;
217 }
218
219
220 /* Set the parameters for the three different kinds of lookup.
221 Arguments:
222  search_type    the search-type code
223  search         the search-type string
224  query          argument for the search; filename or query
225  fnamep         pointer to return filename
226  opts           options
227
228 Return: keyquery        the search-type (for single-key) or query (for query-type)
229  */
230 uschar *
231 search_args(int search_type, uschar * search, uschar * query, uschar ** fnamep,
232   const uschar * opts)
233 {
234 Uskip_whitespace(&query);
235 if (mac_islookup(search_type, lookup_absfilequery))
236   {                                     /* query-style but with file (sqlite) */
237   int sep = ',';
238
239   /* Check options first for new-style file spec */
240   if (opts) for (uschar * s; s = string_nextinlist(&opts, &sep, NULL, 0); )
241     if (Ustrncmp(s, "file=", 5) == 0)
242       {
243       *fnamep = s+5;
244       return query;
245       }
246
247   /* If no filename from options, use old-tyle space-sep prefix on query */
248   if (*query == '/')
249     {
250     uschar * s = query;
251     while (*query && !isspace(*query)) query++;
252     *fnamep = string_copyn(s, query - s);
253     Uskip_whitespace(&query);
254     }
255   else
256     *fnamep = NULL;
257   return query;         /* remainder after file skipped */
258   }
259 if (!mac_islookup(search_type, lookup_querystyle))
260   {                                     /* single-key */
261   *fnamep = query;
262   return search;        /* modifiers important so use "keyquery" for them */
263   }
264 *fnamep = NULL;                         /* else query-style */
265 return query;
266 }
267
268
269
270 /*************************************************
271 *               Release cached resources         *
272 *************************************************/
273
274 /* When search_open is called it caches the "file" that it opens in
275 search_tree. The name of the tree node is a concatenation of the search type
276 with the file name. For query-style lookups, the file name is empty. Real files
277 are normally closed only when this tidyup routine is called, typically at the
278 end of sections of code where a number of lookups might occur. However, if too
279 many files are open simultaneously, some get closed beforehand. They can't be
280 removed from the tree. There is also a general tidyup function which is called
281 for the lookup driver, if it exists.
282
283 First, there is an internal, recursive subroutine.
284
285 Argument:    a pointer to a search_openfile tree node
286 Returns:     nothing
287 */
288
289 static void
290 tidyup_subtree(tree_node *t)
291 {
292 search_cache * c = (search_cache *)(t->data.ptr);
293 if (t->left)  tidyup_subtree(t->left);
294 if (t->right) tidyup_subtree(t->right);
295 if (c && c->handle && lookup_list[c->search_type]->close)
296   lookup_list[c->search_type]->close(c->handle);
297 }
298
299
300 /* The external entry point
301
302 Argument: none
303 Returns:  nothing
304 */
305
306 void
307 search_tidyup(void)
308 {
309 int old_pool = store_pool;
310
311 DEBUG(D_lookup) debug_printf_indent("search_tidyup called\n");
312
313 /* Close individually each cached open file. */
314
315 store_pool = POOL_SEARCH;
316 if (search_tree)
317   {
318   tidyup_subtree(search_tree);
319   search_tree = NULL;
320   }
321 open_top = open_bot = NULL;
322 open_filecount = 0;
323
324 /* Call the general tidyup entry for any drivers that have one. */
325
326 for (int i = 0; i < lookup_list_count; i++) if (lookup_list[i]->tidy)
327   (lookup_list[i]->tidy)();
328
329 if (search_reset_point) search_reset_point = store_reset(search_reset_point);
330 store_pool = old_pool;
331 }
332
333
334
335
336 /*************************************************
337 *             Open search database               *
338 *************************************************/
339
340 /* A mode, and lists of owners and groups, are passed over for checking in
341 the cases where the database is one or more files. Return NULL, with a message
342 pointed to by message, in cases of error.
343
344 For search types that use a file or files, check up on the mode after
345 opening. It is tempting to do a stat before opening the file, and use it as
346 an existence check. However, doing that opens a small security loophole in
347 that the status could be changed before the file is opened. Can't quite see
348 what problems this might lead to, but you can't be too careful where security
349 is concerned. Fstat() on an open file can normally be expected to succeed,
350 but there are some NFS states where it does not.
351
352 There are two styles of query: (1) in the "single-key+file" style, a single
353 key string and a file name are given, for example, for linear searches, DBM
354 files, or for NIS. (2) In the "query" style, no "filename" is given; instead
355 just a single query string is passed. This applies to multiple-key lookup
356 types such as NIS+.
357
358 Before opening, scan the tree of cached files to see if this file is already
359 open for the correct search type. If so, return the saved handle. If not, put
360 the handle in the tree for possible subsequent use. See search_tidyup above for
361 closing all the cached files.
362
363 A count of open databases which use real files is maintained, and if this
364 gets too large, we have to close a cached file. Its entry remains in the tree,
365 but is marked closed.
366
367 Arguments:
368   filename       the name of the file for single-key+file style lookups,
369                  NULL for query-style lookups
370   search_type    the type of search required
371   modemask       if a real single file is used, this specifies mode bits that
372                  must not be set; otherwise it is ignored
373   owners         if a real single file is used, this specifies the possible
374                  owners of the file; otherwise it is ignored
375   owngroups      if a real single file is used, this specifies the possible
376                  group owners of the file; otherwise it is ignored
377
378 Returns:         an identifying handle for the open database;
379                  this is the pointer to the tree block in the
380                  cache of open files; return NULL on open failure, with
381                  a message in search_error_message
382 */
383
384 void *
385 search_open(const uschar * filename, int search_type, int modemask,
386   uid_t * owners, gid_t * owngroups)
387 {
388 void *handle;
389 tree_node *t;
390 search_cache *c;
391 lookup_info *lk = lookup_list[search_type];
392 uschar keybuffer[256];
393 int old_pool = store_pool;
394
395 if (filename && is_tainted(filename))
396   {
397   log_write(0, LOG_MAIN|LOG_PANIC,
398     "Tainted filename for search: '%s'", filename);
399   return NULL;
400   }
401
402 /* Change to the search store pool and remember our reset point */
403
404 store_pool = POOL_SEARCH;
405 if (!search_reset_point) search_reset_point = store_mark();
406
407 DEBUG(D_lookup) debug_printf_indent("search_open: %s \"%s\"\n", lk->name,
408   filename ? filename : US"NULL");
409
410 /* See if we already have this open for this type of search, and if so,
411 pass back the tree block as the handle. The key for the tree node is the search
412 type plus '0' concatenated with the file name. There may be entries in the tree
413 with closed files if a lot of files have been opened. */
414
415 sprintf(CS keybuffer, "%c%.254s", search_type + '0',
416   filename ? filename : US"");
417
418 if ((t = tree_search(search_tree, keybuffer)))
419   {
420   if ((c = (search_cache *)t->data.ptr)->handle)
421     {
422     DEBUG(D_lookup) debug_printf_indent("  cached open\n");
423     store_pool = old_pool;
424     return t;
425     }
426   DEBUG(D_lookup) debug_printf_indent("  cached closed\n");
427   }
428
429 /* Otherwise, we need to open the file or database - each search type has its
430 own code, which is now split off into separately compiled modules. Before doing
431 this, if the search type is one that uses real files, check on the number that
432 we are holding open in the cache. If the limit is reached, close the least
433 recently used one. */
434
435 if (lk->type == lookup_absfile && open_filecount >= lookup_open_max)
436   if (!open_bot)
437     log_write(0, LOG_MAIN|LOG_PANIC, "too many lookups open, but can't find "
438       "one to close");
439   else
440     {
441     search_cache *c = (search_cache *)(open_bot->data.ptr);
442     DEBUG(D_lookup) debug_printf_indent("Too many lookup files open\n  closing %s\n",
443       open_bot->name);
444     if ((open_bot = c->up))
445       ((search_cache *)(open_bot->data.ptr))->down = NULL;
446     else
447       open_top = NULL;
448     ((lookup_list[c->search_type])->close)(c->handle);
449     c->handle = NULL;
450     open_filecount--;
451     }
452
453 /* If opening is successful, call the file-checking function if there is one,
454 and if all is still well, enter the open database into the tree. */
455
456 if (!(handle = (lk->open)(filename, &search_error_message)))
457   {
458   store_pool = old_pool;
459   return NULL;
460   }
461
462 if (  lk->check
463    && !lk->check(handle, filename, modemask, owners, owngroups,
464          &search_error_message))
465   {
466   lk->close(handle);
467   store_pool = old_pool;
468   return NULL;
469   }
470
471 /* If this is a search type that uses real files, keep count. */
472
473 if (lk->type == lookup_absfile) open_filecount++;
474
475 /* If we found a previously opened entry in the tree, re-use it; otherwise
476 insert a new entry. On re-use, leave any cached lookup data and the lookup
477 count alone. */
478
479 if (!t)
480   {
481   t = store_get(sizeof(tree_node) + Ustrlen(keybuffer), FALSE);
482   t->data.ptr = c = store_get(sizeof(search_cache), FALSE);
483   c->item_cache = NULL;
484   Ustrcpy(t->name, keybuffer);
485   tree_insertnode(&search_tree, t);
486   }
487 else c = t->data.ptr;
488
489 c->handle = handle;
490 c->search_type = search_type;
491 c->up = c->down = NULL;
492
493 store_pool = old_pool;
494 return t;
495 }
496
497
498
499
500
501 /*************************************************
502 *  Internal function: Find one item in database  *
503 *************************************************/
504
505 /* The answer is always put into dynamic store. The last lookup for each handle
506 is cached.
507
508 Arguments:
509   handle       the handle from search_open; points to tree node
510   filename     the filename that was handed to search_open, or
511                NULL for query-style searches
512   keystring    the keystring for single-key+file lookups, or
513                the querystring for query-style lookups
514   cache_rd     FALSE to avoid lookup in cache layer
515   opts         type-specific options
516
517 Returns:       a pointer to a dynamic string containing the answer,
518                or NULL if the query failed or was deferred; in the
519                latter case, search_find_defer is set TRUE; after an unusual
520                failure, there may be a message in search_error_message.
521 */
522
523 static uschar *
524 internal_search_find(void * handle, const uschar * filename, uschar * keystring,
525   BOOL cache_rd, const uschar * opts)
526 {
527 tree_node * t = (tree_node *)handle;
528 search_cache * c = (search_cache *)(t->data.ptr);
529 expiring_data * e = NULL;       /* compiler quietening */
530 uschar * data = NULL;
531 int search_type = t->name[0] - '0';
532 int old_pool = store_pool;
533
534 /* Lookups that return DEFER may not always set an error message. So that
535 the callers don't have to test for NULL, set an empty string. */
536
537 search_error_message = US"";
538 f.search_find_defer = FALSE;
539
540 DEBUG(D_lookup) debug_printf_indent("internal_search_find: file=\"%s\"\n  "
541   "type=%s key=\"%s\" opts=%s%s%s\n", filename,
542   lookup_list[search_type]->name, keystring,
543   opts ? "\"" : "", opts, opts ? "\"" : "");
544
545 /* Insurance. If the keystring is empty, just fail. */
546
547 if (keystring[0] == 0) return NULL;
548
549 /* Use the special store pool for search data */
550
551 store_pool = POOL_SEARCH;
552
553 /* Look up the data for the key, unless it is already in the cache for this
554 file. No need to check c->item_cache for NULL, tree_search will do so. Check
555 whether we want to use the cache entry last so that we can always replace it. */
556
557 if (  (t = tree_search(c->item_cache, keystring))
558    && (!(e = t->data.ptr)->expiry || e->expiry > time(NULL))
559    && (!opts && !e->opts  ||  opts && e->opts && Ustrcmp(opts, e->opts) == 0)
560    && cache_rd
561    )
562   { /* Data was in the cache already; set the pointer from the tree node */
563   data = e->data.ptr;
564   DEBUG(D_lookup) debug_printf_indent("cached data used for lookup of %s%s%s\n",
565     keystring,
566     filename ? US"\n  in " : US"", filename ? filename : US"");
567   }
568 else
569   {
570   uint do_cache = UINT_MAX;
571   int keylength = Ustrlen(keystring);
572
573   DEBUG(D_lookup)
574     {
575     if (t)
576       debug_printf_indent("cached data found but %s; ",
577         e->expiry && e->expiry <= time(NULL) ? "out-of-date"
578         : cache_rd ? "wrong opts" : "no_rd option set");
579     debug_printf_indent("%s lookup required for %s%s%s\n",
580       filename ? US"file" : US"database",
581       keystring,
582       filename ? US"\n  in " : US"", filename ? filename : US"");
583     }
584
585   /* Call the code for the different kinds of search. DEFER is handled
586   like FAIL, except that search_find_defer is set so the caller can
587   distinguish if necessary. */
588
589   if (lookup_list[search_type]->find(c->handle, filename, keystring, keylength,
590       &data, &search_error_message, &do_cache, opts) == DEFER)
591     f.search_find_defer = TRUE;
592
593   /* A record that has been found is now in data, which is either NULL
594   or points to a bit of dynamic store. Cache the result of the lookup if
595   caching is permitted. Lookups can disable caching, when they did something
596   that changes their data. The mysql and pgsql lookups do this when an
597   UPDATE/INSERT query was executed.  Lookups can also set a TTL for the
598   cache entry; the dnsdb lookup does.
599   Finally, the caller can request no caching by setting an option. */
600
601   else if (do_cache)
602     {
603     DEBUG(D_lookup) debug_printf_indent("%s cache entry\n",
604       t ? "replacing old" : "creating new");
605     if (!t)     /* No existing entry.  Create new one. */
606       {
607       int len = keylength + 1;
608       e = store_get(sizeof(expiring_data) + sizeof(tree_node) + len,
609                     is_tainted(keystring));
610       t = (tree_node *)(e+1);
611       memcpy(t->name, keystring, len);
612       t->data.ptr = e;
613       tree_insertnode(&c->item_cache, t);
614       }
615       /* Else previous, out-of-date cache entry.  Update with the */
616       /* new result and forget the old one */
617     e->expiry = do_cache == UINT_MAX ? 0 : time(NULL)+do_cache;
618     e->opts = opts ? string_copy(opts) : NULL;
619     e->data.ptr = data;
620     }
621
622   /* If caching was disabled, empty the cache tree. We just set the cache
623   pointer to NULL here, because we cannot release the store at this stage. */
624
625   else
626     {
627     DEBUG(D_lookup) debug_printf_indent("lookup forced cache cleanup\n");
628     c->item_cache = NULL;       /* forget all lookups on this connection */
629     }
630   }
631
632 DEBUG(D_lookup)
633   {
634   if (data)
635     debug_printf_indent("lookup yielded: %s\n", data);
636   else if (f.search_find_defer)
637     debug_printf_indent("lookup deferred: %s\n", search_error_message);
638   else debug_printf_indent("lookup failed\n");
639   }
640
641 /* Return it in new dynamic store in the regular pool */
642
643 store_pool = old_pool;
644 return data ? string_copy(data) : NULL;
645 }
646
647
648
649
650 /*************************************************
651 * Find one item in database, possibly wildcarded *
652 *************************************************/
653
654 /* This function calls the internal function above; once only if there
655 is no partial matching, but repeatedly when partial matching is requested.
656
657 Arguments:
658   handle         the handle from search_open
659   filename       the filename that was handed to search_open, or
660                    NULL for query-style searches
661   keystring      the keystring for single-key+file lookups, or
662                    the querystring for query-style lookups
663   partial        -1 means no partial matching;
664                    otherwise it's the minimum number of components;
665   affix          the affix string for partial matching
666   affixlen       the length of the affix string
667   starflags      SEARCH_STAR and SEARCH_STARAT flags
668   expand_setup   pointer to offset for setting up expansion strings;
669                  don't do any if < 0
670   opts           type-specific options
671
672 Returns:         a pointer to a dynamic string containing the answer,
673                  or NULL if the query failed or was deferred; in the
674                  latter case, search_find_defer is set TRUE
675 */
676
677 uschar *
678 search_find(void * handle, const uschar * filename, uschar * keystring,
679   int partial, const uschar * affix, int affixlen, int starflags,
680   int * expand_setup, const uschar * opts)
681 {
682 tree_node * t = (tree_node *)handle;
683 BOOL set_null_wild = FALSE, cache_rd = TRUE, ret_key = FALSE;
684 uschar * yield;
685
686 DEBUG(D_lookup)
687   {
688   if (partial < 0) affixlen = 99;   /* So that "NULL" prints */
689   debug_printf_indent("search_find: file=\"%s\"\n  key=\"%s\" "
690     "partial=%d affix=%.*s starflags=%x opts=%s%s%s\n",
691     filename ? filename : US"NULL",
692     keystring, partial, affixlen, affix, starflags,
693     opts ? "\"" : "", opts, opts ? "\"" : "");
694
695   }
696
697 /* Parse global lookup options. Also, create a new options list with
698 the global options dropped so that the cache-modifiers are not
699 used in the cache key. */
700
701 if (opts)
702   {
703   int sep = ',';
704   gstring * g = NULL;
705
706   for (uschar * ele; ele = string_nextinlist(&opts, &sep, NULL, 0); )
707     if (Ustrcmp(ele, "ret=key") == 0) ret_key = TRUE;
708     else if (Ustrcmp(ele, "cache=no_rd") == 0) cache_rd = FALSE;
709     else g = string_append_listele(g, ',', ele);
710
711   opts = string_from_gstring(g);
712   }
713
714 /* Arrange to put this database at the top of the LRU chain if it is a type
715 that opens real files. */
716
717 if (  open_top != (tree_node *)handle 
718    && lookup_list[t->name[0]-'0']->type == lookup_absfile)
719   {
720   search_cache *c = (search_cache *)(t->data.ptr);
721   tree_node *up = c->up;
722   tree_node *down = c->down;
723
724   /* Cut it out of the list. A newly opened file will a NULL up pointer.
725   Otherwise there will be a non-NULL up pointer, since we checked above that
726   this block isn't already at the top of the list. */
727
728   if (up)
729     {
730     ((search_cache *)(up->data.ptr))->down = down;
731     if (down)
732       ((search_cache *)(down->data.ptr))->up = up;
733     else
734       open_bot = up;
735     }
736
737   /* Now put it at the head of the list. */
738
739   c->up = NULL;
740   c->down = open_top;
741   if (!open_top) open_bot = t;
742   else ((search_cache *)(open_top->data.ptr))->up = t;
743   open_top = t;
744   }
745
746 DEBUG(D_lookup)
747   {
748   debug_printf_indent("LRU list:\n");
749   for (tree_node *t = open_top; t; )
750     {
751     search_cache *c = (search_cache *)(t->data.ptr);
752     debug_printf_indent("  %s\n", t->name);
753     if (t == open_bot) debug_printf_indent("  End\n");
754     t = c->down;
755     }
756   }
757
758 /* First of all, try to match the key string verbatim. If matched a complete
759 entry but could have been partial, flag to set up variables. */
760
761 yield = internal_search_find(handle, filename, keystring, cache_rd, opts);
762 if (f.search_find_defer) return NULL;
763
764 if (yield) { if (partial >= 0) set_null_wild = TRUE; }
765
766 /* Not matched a complete entry; handle partial lookups, but only if the full
767 search didn't defer. Don't use string_sprintf() to construct the initial key,
768 just in case the original key is too long for the string_sprintf() buffer (it
769 *has* happened!). The case of a zero-length affix has to be treated specially.
770 */
771
772 else if (partial >= 0)
773   {
774   int len = Ustrlen(keystring);
775   uschar *keystring2;
776
777   /* Try with the affix on the front, except for a zero-length affix */
778
779   if (affixlen == 0) keystring2 = keystring; else
780     {
781     keystring2 = store_get(len + affixlen + 1,
782                         is_tainted(keystring) || is_tainted(affix));
783     Ustrncpy(keystring2, affix, affixlen);
784     Ustrcpy(keystring2 + affixlen, keystring);
785     DEBUG(D_lookup) debug_printf_indent("trying partial match %s\n", keystring2);
786     yield = internal_search_find(handle, filename, keystring2, cache_rd, opts);
787     if (f.search_find_defer) return NULL;
788     }
789
790   /* The key in its entirety did not match a wild entry; try chopping off
791   leading components. */
792
793   if (!yield)
794     {
795     int dotcount = 0;
796     uschar *keystring3 = keystring2 + affixlen;
797     uschar *s = keystring3;
798     while (*s != 0) if (*s++ == '.') dotcount++;
799
800     while (dotcount-- >= partial)
801       {
802       while (*keystring3 != 0 && *keystring3 != '.') keystring3++;
803
804       /* If we get right to the end of the string (which will be the last time
805       through this loop), we've failed if the affix is null. Otherwise do one
806       last lookup for the affix itself, but if it is longer than 1 character,
807       remove the last character if it is ".". */
808
809       if (*keystring3 == 0)
810         {
811         if (affixlen < 1) break;
812         if (affixlen > 1 && affix[affixlen-1] == '.') affixlen--;
813         Ustrncpy(keystring2, affix, affixlen);
814         keystring2[affixlen] = 0;
815         keystring3 = keystring2;
816         }
817       else
818         {
819         keystring3 -= affixlen - 1;
820         if (affixlen > 0) Ustrncpy(keystring3, affix, affixlen);
821         }
822
823       DEBUG(D_lookup) debug_printf_indent("trying partial match %s\n", keystring3);
824       yield = internal_search_find(handle, filename, keystring3,
825                 cache_rd, opts);
826       if (f.search_find_defer) return NULL;
827       if (yield)
828         {
829         /* First variable is the wild part; second is the fixed part. Take care
830         to get it right when keystring3 is just "*". */
831
832         if (expand_setup && *expand_setup >= 0)
833           {
834           int fixedlength = Ustrlen(keystring3) - affixlen;
835           int wildlength = Ustrlen(keystring) - fixedlength - 1;
836           *expand_setup += 1;
837           expand_nstring[*expand_setup] = keystring;
838           expand_nlength[*expand_setup] = wildlength;
839           *expand_setup += 1;
840           expand_nstring[*expand_setup] = keystring + wildlength + 1;
841           expand_nlength[*expand_setup] = (fixedlength < 0)? 0 : fixedlength;
842           }
843         break;
844         }
845       keystring3 += affixlen;
846       }
847     }
848
849   else set_null_wild = TRUE; /* Matched a wild entry without any wild part */
850   }
851
852 /* If nothing has been matched, but the option to look for "*@" is set, try
853 replacing everything to the left of @ by *. After a match, the wild part
854 is set to the string to the left of the @. */
855
856 if (!yield  &&  starflags & SEARCH_STARAT)
857   {
858   uschar *atat = Ustrrchr(keystring, '@');
859   if (atat != NULL && atat > keystring)
860     {
861     int savechar;
862     savechar = *(--atat);
863     *atat = '*';
864
865     DEBUG(D_lookup) debug_printf_indent("trying default match %s\n", atat);
866     yield = internal_search_find(handle, filename, atat, cache_rd, opts);
867     *atat = savechar;
868     if (f.search_find_defer) return NULL;
869
870     if (yield && expand_setup && *expand_setup >= 0)
871       {
872       *expand_setup += 1;
873       expand_nstring[*expand_setup] = keystring;
874       expand_nlength[*expand_setup] = atat - keystring + 1;
875       *expand_setup += 1;
876       expand_nstring[*expand_setup] = keystring;
877       expand_nlength[*expand_setup] = 0;
878       }
879     }
880   }
881
882 /* If we still haven't matched anything, and the option to look for "*" is set,
883 try that. If we do match, the first variable (the wild part) is the whole key,
884 and the second is empty. */
885
886 if (!yield  &&  starflags & (SEARCH_STAR|SEARCH_STARAT))
887   {
888   DEBUG(D_lookup) debug_printf_indent("trying to match *\n");
889   yield = internal_search_find(handle, filename, US"*", cache_rd, opts);
890   if (yield && expand_setup && *expand_setup >= 0)
891     {
892     *expand_setup += 1;
893     expand_nstring[*expand_setup] = keystring;
894     expand_nlength[*expand_setup] = Ustrlen(keystring);
895     *expand_setup += 1;
896     expand_nstring[*expand_setup] = keystring;
897     expand_nlength[*expand_setup] = 0;
898     }
899   }
900
901 /* If this was a potentially partial lookup, and we matched either a
902 complete non-wild domain entry, or we matched a wild-carded entry without
903 chopping off any of the domain components, set up the expansion variables
904 (if required) so that the first one is empty, and the second one is the
905 fixed part of the domain. The set_null_wild flag is set only when yield is not
906 NULL. */
907
908 if (set_null_wild && expand_setup && *expand_setup >= 0)
909   {
910   *expand_setup += 1;
911   expand_nstring[*expand_setup] = keystring;
912   expand_nlength[*expand_setup] = 0;
913   *expand_setup += 1;
914   expand_nstring[*expand_setup] = keystring;
915   expand_nlength[*expand_setup] = Ustrlen(keystring);
916   }
917
918 /* If we have a result, check the options to see if the key was wanted rather
919 than the result.  Return a de-tainted version of the key on the grounds that
920 it have been validated by the lookup. */
921
922 if (yield && ret_key)
923   yield = string_copy_taint(keystring, FALSE);
924
925 return yield;
926 }
927
928 /* End of search.c */