Logo Search packages:      
Sourcecode: audit version File versions  Download package

gen_tables.c

/* gen_tables.c -- Generator of lookup tables.
 * Copyright 2008 Red Hat Inc., Durham, North Carolina.
 * All Rights Reserved.
 *
 * This 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.
 *
 * This 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 this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Authors:
 *      Miloslav Trma─Ź <mitr@redhat.com>
 */

#include "config.h"
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <limits.h>
#include <linux/net.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>

#include "gen_tables.h"
#include "libaudit.h"
#include "interpret.h"

/* This is from asm/ipc.h. Copying it for now as some platforms
 *  * have broken headers. */
#define SEMOP            1
#define SEMGET           2
#define SEMCTL           3
#define MSGSND          11
#define MSGRCV          12
#define MSGGET          13
#define MSGCTL          14
#define SHMAT           21
#define SHMDT           22
#define SHMGET          23
#define SHMCTL          24


/* The ratio of table size to number of non-empty elements allowed for a
   "direct" s2i table; if the ratio would be bigger, bsearch tables are used
   instead.

   2 looks like a lot at a first glance, but the bsearch tables need twice as
   much space per element, so with the ratio equal to 2 the direct table uses
   no more memory and is faster. */
#define DIRECT_THRESHOLD 2

/* Allow more than one string defined for a single integer value */
static bool allow_duplicate_ints; /* = false; */

struct value {
      int val;
      const char *s;
      size_t s_offset;
      size_t orig_index;
};

/* The mapping to store. */
static struct value values[] = {
#define _S(VAL, S) { (VAL), (S), 0, 0 },
#include TABLE_H
#undef _S
};

#define NUM_VALUES (sizeof(values) / sizeof(*values))

/* Compare two "struct value" members by name. */
static int
cmp_value_strings(const void *xa, const void *xb)
{
      const struct value *a, *b;

      a = xa;
      b = xb;
      return strcmp(a->s, b->s);
}

/* Compare two "struct value" members by value. */
static int
cmp_value_vals(const void *xa, const void *xb)
{
      const struct value *a, *b;

      a = xa;
      b = xb;
      if (a->val > b->val)
            return 1;
      if (a->val < b->val)
            return -1;
      /* Preserve the original order if there is an ambiguity, to always use
         the first specified value. */
      if (a->orig_index > b->orig_index)
            return 1;
      if (a->orig_index < b->orig_index)
            return -1;
      return 0;
}

/* Compare two "struct value" members by orig_index. */
static int
cmp_value_orig_index(const void *xa, const void *xb)
{
      const struct value *a, *b;

      a = xa;
      b = xb;
      if (a->orig_index > b->orig_index)
            return 1;
      if (a->orig_index < b->orig_index)
            return -1;
      return 0;
}

/* Output the string table, initialize values[*]->s_offset. */
static void
output_strings(const char *prefix)
{
      size_t i, offset;

      offset = 0;
      for (i = 0; i < NUM_VALUES; i++) {
            values[i].s_offset = offset;
            offset += strlen(values[i].s) + 1;
      }
      printf("static const char %s_strings[] = \"", prefix);
      assert(NUM_VALUES > 0);
      for (i = 0; i < NUM_VALUES; i++) {
            const char *c;

            if (i != 0 && i % 10 == 0)
                  fputs("\"\n"
                        "\t\"", stdout);
            for (c = values[i].s; *c != '\0'; c++) {
                  assert(*c != '"' && *c != '\\'
                         && isprint((unsigned char)*c));
                  putc(*c, stdout);
            }
            if (i != NUM_VALUES - 1)
                  fputs("\\0", stdout);
      }
      fputs("\";\n", stdout);
}

/* Output the string to integer mapping code.
   Assume strings are all uppsercase or all lowercase if specified by
   parameters; in that case, make the search case-insensitive.
   values must be sorted by strings. */
static void
output_s2i(const char *prefix, bool uppercase, bool lowercase)
{
      size_t i;

      for (i = 0; i < NUM_VALUES - 1; i++) {
            assert(strcmp(values[i].s, values[i + 1].s) <= 0);
            if (strcmp(values[i].s, values[i + 1].s) == 0) {
                  fprintf(stderr, "Duplicate value `%s': %d, %d\n",
                        values[i].s, values[i].val, values[i + 1].val);
                  abort();
            }
      }
      printf("static const unsigned %s_s2i_s[] = {", prefix);
      for (i = 0; i < NUM_VALUES; i++) {
            if (i % 10 == 0)
                  fputs("\n\t", stdout);
            assert(values[i].s_offset <= UINT_MAX);
            printf("%zu,", values[i].s_offset);
      }
      printf("\n"
             "};\n"
             "static const int %s_s2i_i[] = {", prefix);
      for (i = 0; i < NUM_VALUES; i++) {
            if (i % 10 == 0)
                  fputs("\n\t", stdout);
            printf("%d,", values[i].val);
      }
      fputs("\n"
            "};\n", stdout);
      assert(!(uppercase && lowercase));
      if (uppercase) {
            for (i = 0; i < NUM_VALUES; i++) {
                  const char *c;

                  for (c = values[i].s; *c != '\0'; c++)
                        assert(isascii((unsigned char)*c)
                               && !GT_ISLOWER(*c));
            }
      } else if (lowercase) {
            for (i = 0; i < NUM_VALUES; i++) {
                  const char *c;

                  for (c = values[i].s; *c != '\0'; c++)
                        assert(isascii((unsigned char)*c)
                               && !GT_ISUPPER(*c));
            }
      }
      if (uppercase || lowercase) {
            printf("static int %s_s2i(const char *s, int *value) {\n"
                   "\tsize_t len, i;\n"
                   "\tlen = strlen(s);\n"
                   "\t{ char copy[len + 1];\n"
                   "\tfor (i = 0; i < len; i++) {\n"
                   "\t\tchar c = s[i];\n", prefix);
            if (uppercase)
                  fputs("\t\tcopy[i] = GT_ISLOWER(c) ? c - 'a' + 'A' "
                                            ": c;\n", stdout);
            else
                  fputs("\t\tcopy[i] = GT_ISUPPER(c) ? c - 'A' + 'a' "
                                            ": c;\n", stdout);
            printf("\t}\n"
                   "\tcopy[i] = 0;\n"
                   "\treturn s2i__(%s_strings, %s_s2i_s, %s_s2i_i, %zu, "
                              "copy, value);\n"
                   "\t}\n"
                   "}\n", prefix, prefix, prefix, NUM_VALUES);
      } else
            printf("static int %s_s2i(const char *s, int *value) {\n"
                   "\treturn s2i__(%s_strings, %s_s2i_s, %s_s2i_i, %zu, s, "
                              "value);\n"
                   "}\n", prefix, prefix, prefix, prefix, NUM_VALUES);
}

/* Output the string to integer mapping table.
   values must be sorted by strings. */
static void
output_i2s(const char *prefix)
{
      struct value *unique_values;
      int min_val, max_val;
      size_t i, n;

      assert(NUM_VALUES > 0);
      for (i = 0; i < NUM_VALUES - 1; i++) {
            assert(values[i].val <= values[i + 1].val);
            if (!allow_duplicate_ints
                && values[i].val == values[i + 1].val) {
                  fprintf(stderr, "Duplicate value %d: `%s', `%s'\n",
                        values[i].val, values[i].s, values[i + 1].s);
                  abort();
            }
      }

      unique_values = malloc(NUM_VALUES * sizeof(*unique_values));
      assert(unique_values != NULL);
      n = 0;
      for (i = 0; i < NUM_VALUES; i++) {
            if (n == 0 || unique_values[n - 1].val != values[i].val) {
                  unique_values[n] = values[i];
                  n++;
            }
      }

      min_val = unique_values[0].val;
      max_val = unique_values[n - 1].val;
      if (((double)max_val - (double)min_val) / n <= DIRECT_THRESHOLD) {
            int next_index;

            printf("static const unsigned %s_i2s_direct[] = {", prefix);
            next_index = min_val;
            i = 0;
            for (;;) {
                  if ((next_index - min_val) % 10 == 0)
                        fputs("\n\t", stdout);
                  while (unique_values[i].val < next_index)
                        /* This can happen if (allow_duplicate_ints) */
                        i++;
                  if (unique_values[i].val == next_index) {
                        assert(unique_values[i].s_offset <= UINT_MAX);
                        printf("%zu,", unique_values[i].s_offset);
                  } else
                        fputs("-1u,", stdout);
                  if (next_index == max_val)
                        /* Done like this to avoid integer overflow */
                        break;
                  next_index++;
            }
            printf("\n"
                   "};\n"
                   "static const char *%s_i2s(int v) {\n"
                   "\treturn i2s_direct__(%s_strings, %s_i2s_direct, %d, "
                                   "%d, v);\n"
                   "}\n", prefix, prefix, prefix, min_val, max_val);
      } else {
            printf("static const int %s_i2s_i[] = {", prefix);
            for (i = 0; i < n; i++) {
                  if (i % 10 == 0)
                        fputs("\n\t", stdout);
                  printf("%d,", unique_values[i].val);
            }
            printf("\n"
                   "};\n"
                   "static const unsigned %s_i2s_s[] = {", prefix);
            for (i = 0; i < n; i++) {
                  if (i % 10 == 0)
                        fputs("\n\t", stdout);
                  assert(unique_values[i].s_offset <= UINT_MAX);
                  printf("%zu,", unique_values[i].s_offset);
            }
            printf("\n"
                   "};\n"
                   "static const char *%s_i2s(int v) {\n"
                   "\treturn i2s_bsearch__(%s_strings, %s_i2s_i, %s_i2s_s, "
                        "%zu, v);\n"
                   "}\n", prefix, prefix, prefix, prefix, n);
      }
      free(unique_values);
}

/* Output the string to integer mapping table as a transtab[].
   values must be sorted in the desired order. */
static void
output_i2s_transtab(const char *prefix)
{
      size_t i;
      char *uc_prefix;

      printf("static const struct transtab %s_table[] = {", prefix);
      for (i = 0; i < NUM_VALUES; i++) {
            if (i % 10 == 0)
                  fputs("\n\t", stdout);
            printf("{%d,%zu},", values[i].val, values[i].s_offset);
      }
      uc_prefix = strdup(prefix);
      assert(uc_prefix != NULL);
      for (i = 0; uc_prefix[i] != '\0'; i++)
            uc_prefix[i] = toupper((unsigned char)uc_prefix[i]);
      printf("\n"
             "};\n"
             "#define %s_NUM_ENTRIES "
             "(sizeof(%s_table) / sizeof(*%s_table))\n", uc_prefix, prefix,
             prefix);
}

int
main(int argc, char **argv)
{
      bool gen_i2s, gen_i2s_transtab, gen_s2i, uppercase, lowercase;
      char *prefix;
      size_t i;

      /* This is required by gen_tables.h */
      assert(NUM_VALUES <= (SSIZE_MAX / 2 + 1));

      /* To make sure GT_ISUPPER and GT_ISLOWER work. */
      assert('Z' == 'A' + 25 && 'z' == 'a' + 25);
      gen_i2s = false;
      gen_i2s_transtab = false;
      gen_s2i = false;
      uppercase = false;
      lowercase = false;
      prefix = NULL;
      assert (argc > 1);
      for (i = 1; i < (size_t)argc; i++) {
            if (strcmp(argv[i], "--i2s") == 0)
                  gen_i2s = true;
            else if (strcmp(argv[i], "--i2s-transtab") == 0)
                  gen_i2s_transtab = true;
            else if (strcmp(argv[i], "--s2i") == 0)
                  gen_s2i = true;
            else if (strcmp(argv[i], "--uppercase") == 0)
                  uppercase = true;
            else if (strcmp(argv[i], "--lowercase") == 0)
                  lowercase = true;
            else if (strcmp(argv[i], "--duplicate-ints") == 0)
                  allow_duplicate_ints = true;
            else {
                  assert(*argv[i] != '-');
                  assert(prefix == NULL);
                  prefix = argv[i];
            }
      }
      assert(prefix != NULL);
      assert(!(uppercase && lowercase));

      printf("/* This is a generated file, see Makefile.am for its "
             "inputs. */\n");
      for (i = 0; i < NUM_VALUES; i++)
            values[i].orig_index = i;
      qsort(values, NUM_VALUES, sizeof(*values), cmp_value_strings);
      /* FIXME? if (gen_s2i), sort the strings in some other order
         (e.g. "first 4 nodes in BFS of the bsearch tree first") to use the
         cache better. */
      /* FIXME? If the only thing generated is a transtab, keep the strings
         in the original order to use the cache better. */
      output_strings(prefix);
      if (gen_s2i)
            output_s2i(prefix, uppercase, lowercase);
      if (gen_i2s) {
            qsort(values, NUM_VALUES, sizeof(*values), cmp_value_vals);
            output_i2s(prefix);
      }
      if (gen_i2s_transtab) {
            qsort(values, NUM_VALUES, sizeof(*values),
                  cmp_value_orig_index);
            output_i2s_transtab(prefix);
      }
      return EXIT_SUCCESS;
}

Generated by  Doxygen 1.6.0   Back to index