/* Create simple DB database from textual input.

   Copyright (C) 1996-2018 Free Software Foundation, Inc.

   This file is part of the GNU C Library.

   Contributed by Ulrich Drepper <drepper@cygnus.com>, 1996.

   The GNU C Library is free software; you can redistribute it and/or

   modify it under the terms of the GNU Lesser General Public

   License as published by the Free Software Foundation; either

   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public

   License along with the GNU C Library; if not, see

   <http://www.gnu.org/licenses/>.  */

#include <argp.h>

#include <assert.h>

#include <ctype.h>

#include <errno.h>

#include <error.h>

#include <fcntl.h>

#include <inttypes.h>

#include <libintl.h>

#include <locale.h>

#include <search.h>

#include <stdbool.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <unistd.h>

#include <stdint.h>

#include <sys/mman.h>

#include <sys/param.h>

#include <sys/stat.h>

#include <sys/uio.h>

#include "nss_db/nss_db.h"

/* Get libc version number.  */

#include "../version.h"

/* The hashing function we use.  */

#include "../intl/hash-string.h"

/* SELinux support.  */

#ifdef HAVE_SELINUX

# include <selinux/selinux.h>

#endif

#ifndef MAP_POPULATE

# define MAP_POPULATE 0

#endif

#define PACKAGE _libc_intl_domainname

/* List of data bases.  */

struct database

{

  char dbid;

  bool extra_string;

  struct database *next;

  void *entries;

  size_t nentries;

  size_t nhashentries;

  stridx_t *hashtable;

  size_t keystrlen;

  stridx_t *keyidxtab;

  char *keystrtab;

} *databases;

static size_t ndatabases;

static size_t nhashentries_total;

static size_t valstrlen;

static void *valstrtree;

static char *valstrtab;

static size_t extrastrlen;

/* Database entry.  */

struct dbentry

{

  stridx_t validx;

  uint32_t hashval;

  char str[0];

};

/* Stored string entry.  */

struct valstrentry

{

  stridx_t idx;

  bool extra_string;

  char str[0];

};

/* True if any entry has been added.  */

static bool any_dbentry;

/* If non-zero convert key to lower case.  */

static int to_lowercase;

/* If non-zero print content of input file, one entry per line.  */

static int do_undo;

/* If non-zero do not print informational messages.  */

static int be_quiet;

/* Name of output file.  */

static const char *output_name;

/* Name and version of program.  */

static void print_version (FILE *stream, struct argp_state *state);

void (*argp_program_version_hook) (FILE *, struct argp_state *) = print_version;

/* Definitions of arguments for argp functions.  */

static const struct argp_option options[] =

{

  { "fold-case", 'f', NULL, 0, N_("Convert key to lower case") },

  { "output", 'o', N_("NAME"), 0, N_("Write output to file NAME") },

  { "quiet", 'q', NULL, 0,

    N_("Do not print messages while building database") },

  { "undo", 'u', NULL, 0,

    N_("Print content of database file, one entry a line") },

  { "generated", 'g', N_("CHAR"), 0,

    N_("Generated line not part of iteration") },

  { NULL, 0, NULL, 0, NULL }

};

/* Short description of program.  */

static const char doc[] = N_("Create simple database from textual input.");

/* Strings for arguments in help texts.  */

static const char args_doc[] = N_("\

INPUT-FILE OUTPUT-FILE\n-o OUTPUT-FILE INPUT-FILE\n-u INPUT-FILE");

/* Prototype for option handler.  */

static error_t parse_opt (int key, char *arg, struct argp_state *state);

/* Function to print some extra text in the help message.  */

static char *more_help (int key, const char *text, void *input);

/* Data structure to communicate with argp functions.  */

static struct argp argp =

{

  options, parse_opt, args_doc, doc, NULL, more_help

};

/* List of databases which are not part of the iteration table.  */

static struct db_option

{

  char dbid;

  struct db_option *next;

} *db_options;

/* Prototypes for local functions.  */

static int process_input (FILE *input, const char *inname,

			  int to_lowercase, int be_quiet);

static int print_database (int fd);

static void compute_tables (void);

static int write_output (int fd);

/* SELinux support.  */

#ifdef HAVE_SELINUX

/* Set the SELinux file creation context for the given file. */

static void set_file_creation_context (const char *outname, mode_t mode);

static void reset_file_creation_context (void);

#else

# define set_file_creation_context(_outname,_mode)

# define reset_file_creation_context()

#endif

/* External functions.  */

#include <programs/xmalloc.h>

int

main (int argc, char *argv[])

{

  const char *input_name;

  FILE *input_file;

  int remaining;

  int mode = 0644;

  /* Set locale via LC_ALL.  */

  setlocale (LC_ALL, "");

  /* Set the text message domain.  */

  textdomain (_libc_intl_domainname);

  /* Initialize local variables.  */

  input_name = NULL;

  /* Parse and process arguments.  */

  argp_parse (&argp, argc, argv, 0, &remaining, NULL);

  /* Determine file names.  */

  if (do_undo || output_name != NULL)

    {

      if (remaining + 1 != argc)

	{

	wrong_arguments:

	  error (0, 0, gettext ("wrong number of arguments"));

	  argp_help (&argp, stdout, ARGP_HELP_SEE,

		     program_invocation_short_name);

	  exit (1);

	}

      input_name = argv[remaining];

    }

  else

    {

      if (remaining + 2 != argc)

	goto wrong_arguments;

      input_name = argv[remaining++];

      output_name = argv[remaining];

    }

  /* Special handling if we are asked to print the database.  */

  if (do_undo)

    {

      int fd = open (input_name, O_RDONLY);

      if (fd == -1)

	error (EXIT_FAILURE, errno, gettext ("cannot open database file `%s'"),

	       input_name);

      int status = print_database (fd);

      close (fd);

      return status;

    }

  /* Open input file.  */

  if (strcmp (input_name, "-") == 0 || strcmp (input_name, "/dev/stdin") == 0)

    input_file = stdin;

  else

    {

      struct stat64 st;

      input_file = fopen64 (input_name, "r");

      if (input_file == NULL)

	error (EXIT_FAILURE, errno, gettext ("cannot open input file `%s'"),

	       input_name);

      /* Get the access rights from the source file.  The output file should

	 have the same.  */

      if (fstat64 (fileno (input_file), &st) >= 0)

	mode = st.st_mode & ACCESSPERMS;

    }

  /* Start the real work.  */

  int status = process_input (input_file, input_name, to_lowercase, be_quiet);

  /* Close files.  */

  if (input_file != stdin)

    fclose (input_file);

  /* No need to continue when we did not read the file successfully.  */

  if (status != EXIT_SUCCESS)

    return status;

  /* Bail out if nothing is to be done.  */

  if (!any_dbentry)

    {

      if (be_quiet)

	return EXIT_SUCCESS;

      else

	error (EXIT_SUCCESS, 0, gettext ("no entries to be processed"));

    }

  /* Compute hash and string tables.  */

  compute_tables ();

  /* Open output file.  This must not be standard output so we don't

     handle "-" and "/dev/stdout" special.  */

  char *tmp_output_name;

  if (asprintf (&tmp_output_name, "%s.XXXXXX", output_name) == -1)

    error (EXIT_FAILURE, errno, gettext ("cannot create temporary file name"));

  set_file_creation_context (output_name, mode);

  int fd = mkstemp (tmp_output_name);

  reset_file_creation_context ();

  if (fd == -1)

    error (EXIT_FAILURE, errno, gettext ("cannot create temporary file"));

  status = write_output (fd);

  if (status == EXIT_SUCCESS)

    {

      struct stat64 st;

      if (fstat64 (fd, &st) == 0)

	{

	  if ((st.st_mode & ACCESSPERMS) != mode)

	    /* We ignore problems with changing the mode.  */

	    fchmod (fd, mode);

	}

      else

	{

	  error (0, errno, gettext ("cannot stat newly created file"));

	  status = EXIT_FAILURE;

	}

    }

  close (fd);

  if (status == EXIT_SUCCESS)

    {

      if (rename (tmp_output_name, output_name) != 0)

	{

	  error (0, errno, gettext ("cannot rename temporary file"));

	  status = EXIT_FAILURE;

	  goto do_unlink;

	}

    }

  else

  do_unlink:

    unlink (tmp_output_name);

  return status;

}

/* Handle program arguments.  */

static error_t

parse_opt (int key, char *arg, struct argp_state *state)

{

  struct db_option *newp;

  switch (key)

    {

    case 'f':

      to_lowercase = 1;

      break;

    case 'o':

      output_name = arg;

      break;

    case 'q':

      be_quiet = 1;

      break;

    case 'u':

      do_undo = 1;

      break;

    case 'g':

      newp = xmalloc (sizeof (*newp));

      newp->dbid = arg[0];

      newp->next = db_options;

      db_options = newp;

      break;

    default:

      return ARGP_ERR_UNKNOWN;

    }

  return 0;

}

static char *

more_help (int key, const char *text, void *input)

{

  char *tp = NULL;

  switch (key)

    {

    case ARGP_KEY_HELP_EXTRA:

      /* We print some extra information.  */

      if (asprintf (&tp, gettext ("\

For bug reporting instructions, please see:\n\

%s.\n"), REPORT_BUGS_TO) < 0)

	return NULL;

      return tp;

    default:

      break;

    }

  return (char *) text;

}

/* Print the version information.  */

static void

print_version (FILE *stream, struct argp_state *state)

{

  fprintf (stream, "makedb %s%s\n", PKGVERSION, VERSION);

  fprintf (stream, gettext ("\

Copyright (C) %s Free Software Foundation, Inc.\n\

This is free software; see the source for copying conditions.  There is NO\n\

warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n\

"), "2018");

  fprintf (stream, gettext ("Written by %s.\n"), "Ulrich Drepper");

}

static int

dbentry_compare (const void *p1, const void *p2)

{

  const struct dbentry *d1 = (const struct dbentry *) p1;

  const struct dbentry *d2 = (const struct dbentry *) p2;

  if (d1->hashval != d2->hashval)

    return d1->hashval < d2->hashval ? -1 : 1;

  return strcmp (d1->str, d2->str);

}

static int

valstr_compare (const void *p1, const void *p2)

{

  const struct valstrentry *d1 = (const struct valstrentry *) p1;

  const struct valstrentry *d2 = (const struct valstrentry *) p2;

  return strcmp (d1->str, d2->str);

}

static int

process_input (FILE *input, const char *inname, int to_lowercase, int be_quiet)

{

  char *line;

  size_t linelen;

  int status;

  size_t linenr;

  line = NULL;

  linelen = 0;

  status = EXIT_SUCCESS;

  linenr = 0;

  struct database *last_database = NULL;

  while (!feof_unlocked (input))

    {

      ssize_t n = getline (&line, &linelen, input);

      if (n < 0)

	/* This means end of file or some bug.  */

	break;

      if (n == 0)

	/* Short read.  Probably interrupted system call. */

	continue;

      ++linenr;

      if (line[n - 1] == '\n')

	/* Remove trailing newline.  */

	line[--n] = '\0';

      char *cp = line;

      while (isspace (*cp))

	++cp;

      if (*cp == '#' || *cp == '\0')

	/* First non-space character in line '#': it's a comment.

	   Also go to the next line if it is empty except for whitespaces. */

	continue;

      /* Skip over the character indicating the database so that it is not

	 affected by TO_LOWERCASE.  */

      char *key = cp++;

      while (*cp != '\0' && !isspace (*cp))

	{

	  if (to_lowercase)

	    *cp = tolower (*cp);

	  ++cp;

	}

      if (*cp == '\0')

	/* It's a line without a value field.  */

	continue;

      *cp++ = '\0';

      size_t keylen = cp - key;

      while (isspace (*cp))

	++cp;

      char *data = cp;

      size_t datalen = (&line[n] - cp) + 1;

      /* Find the database.  */

      if (last_database == NULL || last_database->dbid != key[0])

	{

	  last_database = databases;

	  while (last_database != NULL && last_database->dbid != key[0])

	    last_database = last_database->next;

	  if (last_database == NULL)

	    {

	      last_database = xmalloc (sizeof (*last_database));

	      last_database->dbid = key[0];

	      last_database->extra_string = false;

	      last_database->next = databases;

	      last_database->entries = NULL;

	      last_database->nentries = 0;

	      last_database->keystrlen = 0;

	      databases = last_database;

	      struct db_option *runp = db_options;

	      while (runp != NULL)

		if (runp->dbid == key[0])

		  {

		    last_database->extra_string = true;

		    break;

		  }

		else

		  runp = runp->next;

	    }

	}

      /* Skip the database selector.  */

      ++key;

      --keylen;

      /* Store the data.  */

      struct valstrentry *nentry = xmalloc (sizeof (struct valstrentry)

					    + datalen);

      if (last_database->extra_string)

	nentry->idx = extrastrlen;

      else

	nentry->idx = valstrlen;

      nentry->extra_string = last_database->extra_string;

      memcpy (nentry->str, data, datalen);

      struct valstrentry **fdata = tsearch (nentry, &valstrtree,

					    valstr_compare);

      if (fdata == NULL)

	error (EXIT_FAILURE, errno, gettext ("cannot create search tree"));

      if (*fdata != nentry)

	{

	  /* We can reuse a string.  */

	  free (nentry);

	  nentry = *fdata;

	}

      else

	if (last_database->extra_string)

	  extrastrlen += datalen;

	else

	  valstrlen += datalen;

      /* Store the key.  */

      struct dbentry *newp = xmalloc (sizeof (struct dbentry) + keylen);

      newp->validx = nentry->idx;

      newp->hashval = __hash_string (key);

      memcpy (newp->str, key, keylen);

      struct dbentry **found = tsearch (newp, &last_database->entries,

					dbentry_compare);

      if (found == NULL)

	error (EXIT_FAILURE, errno, gettext ("cannot create search tree"));

      if (*found != newp)

	{

	  free (newp);

	  if (!be_quiet)

	    error_at_line (0, 0, inname, linenr, gettext ("duplicate key"));

	  continue;

	}

      ++last_database->nentries;

      last_database->keystrlen += keylen;

      any_dbentry = true;

    }

  if (ferror_unlocked (input))

    {

      error (0, 0, gettext ("problems while reading `%s'"), inname);

      status = EXIT_FAILURE;

    }

  return status;

}

static void

copy_valstr (const void *nodep, const VISIT which, const int depth)

{

  if (which != leaf && which != postorder)

    return;

  const struct valstrentry *p = *(const struct valstrentry **) nodep;

  strcpy (valstrtab + (p->extra_string ? valstrlen : 0) + p->idx, p->str);

}

/* Determine if the candidate is prime by using a modified trial division

   algorithm. The candidate must be both odd and greater than 4.  */

static int

is_prime (size_t candidate)

{

  size_t divn = 3;

  size_t sq = divn * divn;

  assert (candidate > 4 && candidate % 2 != 0);

  while (sq < candidate && candidate % divn != 0)

    {

      ++divn;

      sq += 4 * divn;

      ++divn;

    }

  return candidate % divn != 0;

}

static size_t

next_prime (size_t seed)

{

  /* Make sure that we're always greater than 4.  */

  seed = (seed + 4) | 1;

  while (!is_prime (seed))

    seed += 2;

  return seed;

}

static void

compute_tables (void)

{

  valstrtab = xmalloc (roundup (valstrlen + extrastrlen, sizeof (stridx_t)));

  while ((valstrlen + extrastrlen) % sizeof (stridx_t) != 0)

    valstrtab[valstrlen++] = '\0';

  twalk (valstrtree, copy_valstr);

  static struct database *db;

  for (db = databases; db != NULL; db = db->next)

    if (db->nentries != 0)

      {

	++ndatabases;

	/* We simply use an odd number large than twice the number of

	   elements to store in the hash table for the size.  This gives

	   enough efficiency.  */

#define TEST_RANGE 30

	size_t nhashentries_min = next_prime (db->nentries < TEST_RANGE

					      ? db->nentries

					      : db->nentries * 2 - TEST_RANGE);

	size_t nhashentries_max = MAX (nhashentries_min, db->nentries * 4);

	size_t nhashentries_best = nhashentries_min;

	size_t chainlength_best = db->nentries;

	db->hashtable = xmalloc (2 * nhashentries_max * sizeof (stridx_t)

				 + db->keystrlen);

	db->keyidxtab = db->hashtable + nhashentries_max;

	db->keystrtab = (char *) (db->keyidxtab + nhashentries_max);

	static size_t max_chainlength;

	static char *wp;

	static size_t nhashentries;

	static bool copy_string;

	void add_key(const void *nodep, const VISIT which, const int depth)

	{

	  if (which != leaf && which != postorder)

	    return;

	  const struct dbentry *dbe = *(const struct dbentry **) nodep;

	  ptrdiff_t stridx;

	  if (copy_string)

	    {

	      stridx = wp - db->keystrtab;

	      wp = stpcpy (wp, dbe->str) + 1;

	    }

	  else

	    stridx = 0;

	  size_t hidx = dbe->hashval % nhashentries;

	  size_t hval2 = 1 + dbe->hashval % (nhashentries - 2);

	  size_t chainlength = 0;

	  while (db->hashtable[hidx] != ~((stridx_t) 0))

	    {

	      ++chainlength;

	      if ((hidx += hval2) >= nhashentries)

		hidx -= nhashentries;

	    }

	  db->hashtable[hidx] = ((db->extra_string ? valstrlen : 0)

				 + dbe->validx);

	  db->keyidxtab[hidx] = stridx;

	  max_chainlength = MAX (max_chainlength, chainlength);

	}

	copy_string = false;

	nhashentries = nhashentries_min;

	for (size_t cnt = 0; cnt < TEST_RANGE; ++cnt)

	  {

	    memset (db->hashtable, '\xff', nhashentries * sizeof (stridx_t));

	    max_chainlength = 0;

	    wp = db->keystrtab;

	    twalk (db->entries, add_key);

	    if (max_chainlength == 0)

	      {

		/* No need to look further, this is as good as it gets.  */

		nhashentries_best = nhashentries;

		break;

	      }

	    if (max_chainlength < chainlength_best)

	      {

		chainlength_best = max_chainlength;

		nhashentries_best = nhashentries;

	      }

	    nhashentries = next_prime (nhashentries + 1);

	    if (nhashentries > nhashentries_max)

	      break;

	  }

	/* Recompute the best table again, this time fill in the strings.  */

	nhashentries = nhashentries_best;

	memset (db->hashtable, '\xff',

		2 * nhashentries_max * sizeof (stridx_t));

	copy_string = true;

	wp = db->keystrtab;

	twalk (db->entries, add_key);

	db->nhashentries = nhashentries_best;

	nhashentries_total += nhashentries_best;

    }

}

static int

write_output (int fd)

{

  struct nss_db_header *header;

  uint64_t file_offset = (sizeof (struct nss_db_header)

			  + (ndatabases * sizeof (header->dbs[0])));

  header = alloca (file_offset);

  header->magic = NSS_DB_MAGIC;

  header->ndbs = ndatabases;

  header->valstroffset = file_offset;

  header->valstrlen = valstrlen;

  size_t filled_dbs = 0;

  struct iovec iov[2 + ndatabases * 3];

  iov[0].iov_base = header;

  iov[0].iov_len = file_offset;

  iov[1].iov_base = valstrtab;

  iov[1].iov_len = valstrlen + extrastrlen;

  file_offset += iov[1].iov_len;

  size_t keydataoffset = file_offset + nhashentries_total * sizeof (stridx_t);

  for (struct database *db = databases; db != NULL; db = db->next)

    if (db->entries != NULL)

      {

	assert (file_offset % sizeof (stridx_t) == 0);

	assert (filled_dbs < ndatabases);

	header->dbs[filled_dbs].id = db->dbid;

	memset (header->dbs[filled_dbs].pad, '\0',

		sizeof (header->dbs[0].pad));

	header->dbs[filled_dbs].hashsize = db->nhashentries;

	iov[2 + filled_dbs].iov_base = db->hashtable;

	iov[2 + filled_dbs].iov_len = db->nhashentries * sizeof (stridx_t);

	header->dbs[filled_dbs].hashoffset = file_offset;

	file_offset += iov[2 + filled_dbs].iov_len;

	iov[2 + ndatabases + filled_dbs * 2].iov_base = db->keyidxtab;

	iov[2 + ndatabases + filled_dbs * 2].iov_len

	  = db->nhashentries * sizeof (stridx_t);

	header->dbs[filled_dbs].keyidxoffset = keydataoffset;

	keydataoffset += iov[2 + ndatabases + filled_dbs * 2].iov_len;

	iov[3 + ndatabases + filled_dbs * 2].iov_base = db->keystrtab;

	iov[3 + ndatabases + filled_dbs * 2].iov_len = db->keystrlen;

	header->dbs[filled_dbs].keystroffset = keydataoffset;

	keydataoffset += iov[3 + ndatabases + filled_dbs * 2].iov_len;

	++filled_dbs;

      }

  assert (filled_dbs == ndatabases);

  assert (file_offset == (iov[0].iov_len + iov[1].iov_len

			  + nhashentries_total * sizeof (stridx_t)));

  header->allocate = file_offset;

  if (writev (fd, iov, 2 + ndatabases * 3) != keydataoffset)

    {

      error (0, errno, gettext ("failed to write new database file"));

      return EXIT_FAILURE;

    }

  return EXIT_SUCCESS;

}

static int

print_database (int fd)

{

  struct stat64 st;

  if (fstat64 (fd, &st) != 0)

    error (EXIT_FAILURE, errno, gettext ("cannot stat database file"));

  const struct nss_db_header *header = mmap (NULL, st.st_size, PROT_READ,

					     MAP_PRIVATE|MAP_POPULATE, fd, 0);

  if (header == MAP_FAILED)

    error (EXIT_FAILURE, errno, gettext ("cannot map database file"));

  if (header->magic != NSS_DB_MAGIC)

    error (EXIT_FAILURE, 0, gettext ("file not a database file"));

  const char *valstrtab = (const char *) header + header->valstroffset;

  for (unsigned int dbidx = 0; dbidx < header->ndbs; ++dbidx)

    {

      const stridx_t *stridxtab

	= ((const stridx_t *) ((const char *) header

			       + header->dbs[dbidx].keyidxoffset));

      const char *keystrtab

	= (const char *) header + header->dbs[dbidx].keystroffset;

      const stridx_t *hashtab

	= (const stridx_t *) ((const char *) header

			      + header->dbs[dbidx].hashoffset);

      for (uint32_t hidx = 0; hidx < header->dbs[dbidx].hashsize; ++hidx)

	if (hashtab[hidx] != ~((stridx_t) 0))

	  printf ("%c%s %s\n",

		  header->dbs[dbidx].id,

		  keystrtab + stridxtab[hidx],

		  valstrtab + hashtab[hidx]);

    }

  return EXIT_SUCCESS;

}

#ifdef HAVE_SELINUX

static void

set_file_creation_context (const char *outname, mode_t mode)

{

  static int enabled;

  static int enforcing;

  security_context_t ctx;

  /* Check if SELinux is enabled, and remember. */

  if (enabled == 0)

    enabled = is_selinux_enabled () ? 1 : -1;

  if (enabled < 0)

    return;

  /* Check if SELinux is enforcing, and remember. */

  if (enforcing == 0)

    enforcing = security_getenforce () ? 1 : -1;

  /* Determine the context which the file should have. */

  ctx = NULL;

  if (matchpathcon (outname, S_IFREG | mode, &ctx) == 0 && ctx != NULL)

    {

      if (setfscreatecon (ctx) != 0)

	error (enforcing > 0 ? EXIT_FAILURE : 0, 0,

	       gettext ("cannot set file creation context for `%s'"),

	       outname);

      freecon (ctx);

    }

}

static void

reset_file_creation_context (void)

{

  setfscreatecon (NULL);

}

#endif