/* Cancellation handling analysis aid.
   Copyright (C) Red Hat, Inc.
   Written by Ulrich Drepper <drepper@redhat.com>, 2003.  */
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <error.h>
#include <fcntl.h>
#include <gelf.h>
#include <search.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdio_ext.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>


struct symbol;


struct named_obj
{
  const char *name;
  struct symbol *sym;
  struct named_obj *next;
};


struct symbol
{
  struct named_obj *names;
  struct used_by
  {
    struct symbol *sym;
    struct used_by *next;
  } *used_by;
  struct fileinfo *file;
  size_t scn;
  GElf_Off from;
  GElf_Off to;
  bool marked;
};


struct reported
{
  const char *sname;
  const char *fname;
};


static void *global_syms;
static void *exported_syms;
static void *reported_cps;
static void *waived;

static bool verbose;
static bool show_missing_eh;


/* Simplification: for now we assume files have only one symbol table.
   Once this changes increase the following number or use some dynamic
   allocation.  */
#define NSYMTAB 1
struct fileinfo
{
  const char *fname;
  bool has_eh_frame;
  size_t nhandled_symtab;
  struct symtab
  {
    size_t ndx;
    struct named_obj *syms;
  } handled_symtab[NSYMTAB];
  struct fileinfo *next;
};
static struct fileinfo *allfiles;


static void handle_file (const char *fname);
static void handle_elf (Elf *elf, const char *fname);
static void handle_archive (int fd, Elf *elf, const char *fname);
static int global_compare (const void *p1, const void *p2);
static int reported_compare (const void *p1, const void *p2);
static void mark (struct symbol *sym);
static void read_dso (const char *fname);
static void read_waived (const char *fname);


int
main (int argc, char *argv[])
{
  int opt;
  bool any = false;
  const char *dsoname = NULL;
  int retval = 0;

  elf_version (EV_CURRENT);

  while ((opt = getopt (argc, argv, "cd:ef:hvw:")) != -1)
    switch (opt)
      {
      case 'c':
	show_missing_eh = false;
	break;
      case 'd':
	dsoname = optarg;
	break;
      case 'e':
	show_missing_eh = true;
	break;
      case 'f':
	handle_file (optarg);
	any = true;
	break;
      case 'h':
      usage:
	printf ("Usage: %s [-d DSO] [-f ELFILE]... [-w FILE]... SEED...\n",
		argv[0]);
	exit (retval);
      case 'v':
	verbose = true;
	break;
      case 'w':
	read_waived (optarg);
	break;
      default:
	abort ();
      }

  if (! any)
    handle_file ("libc_pic.a");

  if (dsoname != NULL && ! show_missing_eh)
    read_dso (dsoname);

  if (optind == argc)
    {
      puts ("no seeds");
      retval = 1;
      goto usage;
    }

  puts (show_missing_eh ? "files missing .eh_frame" : "cancellation points");
  while (optind < argc)
    {
      struct named_obj fake;
      fake.name = argv[optind];
      struct named_obj **found = tfind (&fake, &global_syms, global_compare);
      if (found == NULL)
	error (EXIT_FAILURE, 0, "seed '%s' not defined", argv[optind]);

      mark ((*found)->sym);

      ++optind;
    }

  return 0;
}


#define FATAL() fatal (__LINE__)
static void
__attribute ((noreturn))
fatal (int line)
{
  while (1)
    error (EXIT_FAILURE, 0, "fatal error %d", line);
}


static void
mark (struct symbol *sym)
{
  sym->marked = true;

  if (show_missing_eh)
    {
      if (! sym->file->has_eh_frame
	  && tfind (sym->file->fname, &waived,
		    (int (*) (const void *, const void *)) strcmp) == NULL)
	{
	  printf ("%s (for %s)\n", sym->file->fname, sym->names->name);
	  sym->file->has_eh_frame = true;
	}
    }
  else
    {
      struct named_obj *nr = sym->names;
      do
	if (tfind (nr->name, &exported_syms,
		   (int (*) (const void *, const void *)) strcmp) != NULL
	    && tfind (nr->name, &waived,
		      (int (*) (const void *, const void *)) strcmp) == NULL)
	  {
	    struct reported fake;

	    fake.sname = nr->name;
	    fake.fname = sym->file->fname;
	    if (tfind (&fake, &reported_cps, reported_compare) == NULL)
	      {
		printf ("%s:%s\n", sym->file->fname, nr->name);

		struct reported *newr;
		newr = (struct reported *) malloc (sizeof (*newr));
		*newr = fake;

		tsearch (newr, &reported_cps, reported_compare);
	      }
	  }
      while ((nr = nr->next) != NULL);
    }

  struct used_by *sr = sym->used_by;
  while (sr != NULL)
    {
      if (! sr->sym->marked)
	mark (sr->sym);

      sr = sr->next;
    }
}


static void
handle_file (const char *fname)
{
  int fd = open (fname, O_RDONLY);
  if (fd == -1)
    error (EXIT_FAILURE, errno, "cannot open \"%s\"", fname);

  Elf *elf = elf_begin (fd, ELF_C_READ_MMAP, NULL);
  if (elf == NULL)
    error (EXIT_FAILURE, 0, "cannot create ELF descriptor: %s",
	   elf_errmsg (-1));

  if (elf_kind (elf) == ELF_K_ELF)
    handle_elf (elf, fname);
  else if (elf_kind (elf) == ELF_K_AR)
    handle_archive (fd, elf, fname);
  else
    error (EXIT_FAILURE, 0, "%s: unknown file type", fname);
}


static void
handle_archive (int fd, Elf *elf, const char *fname)
{
  Elf *subelf;
  Elf_Cmd cmd = ELF_C_READ_MMAP;
  while ((subelf = elf_begin (fd, cmd, elf)) != NULL)
    {
      Elf_Arhdr *arhdr = elf_getarhdr (subelf);
      if (strcmp (arhdr->ar_name, "/") != 0
	  && strcmp (arhdr->ar_name, "//") != 0)
	{
	  if (elf_kind (subelf) == ELF_K_ELF)
	    handle_elf (subelf, strdup (arhdr->ar_name));
	  else if (elf_kind (subelf) == ELF_K_AR)
	    handle_archive (fd, subelf, arhdr->ar_name);
	  else
	    error (EXIT_FAILURE, 0, "%s(%s): unknown file type",
		   fname, arhdr->ar_name);
	}

      cmd = elf_next (subelf);
      (void) elf_end (subelf);
    }
}


static int
global_compare (const void *p1, const void *p2)
{
  const struct named_obj *g1 = (const struct named_obj *) p1;
  const struct named_obj *g2 = (const struct named_obj *) p2;

  return strcmp (g1->name, g2->name);
}


static int
reported_compare (const void *p1, const void *p2)
{
  const struct reported *r1 = (const struct reported *) p1;
  const struct reported *r2 = (const struct reported *) p2;

  return strcmp (r1->sname, r2->sname) ?: strcmp (r1->fname, r2->fname);
}



static void
handle_rel (Elf *elf, struct fileinfo *newfile, GElf_Ehdr *ehdr,
	    Elf_Scn *scn, GElf_Shdr *shdr)
{
  Elf_Scn *dscn = elf_getscn (elf, shdr->sh_info);
  GElf_Shdr dshdr_mem;
  GElf_Shdr *dshdr = gelf_getshdr (dscn, &dshdr_mem);
  if (dshdr == NULL)
    FATAL ();

  if ((dshdr->sh_flags & (SHF_ALLOC | SHF_EXECINSTR))
      != (SHF_ALLOC | SHF_EXECINSTR))
    return;

  Elf_Scn *sscn = elf_getscn (elf, shdr->sh_link);
  GElf_Shdr sshdr_mem;
  GElf_Shdr *sshdr = gelf_getshdr (sscn, &sshdr_mem);
  Elf_Data *sdata = elf_getdata (sscn, NULL);
  if (sdata == NULL)
    FATAL ();
  size_t nsym = sshdr->sh_size / sshdr->sh_entsize;

  int cnt;
  for (cnt = 0; cnt < newfile->nhandled_symtab; ++cnt)
    if (newfile->handled_symtab[cnt].ndx == shdr->sh_link)
      break;
  struct symtab *symtab = &newfile->handled_symtab[cnt];
  if (cnt == newfile->nhandled_symtab)
    {
      if (cnt == NSYMTAB)
	FATAL ();

      symtab->ndx = shdr->sh_link;
      symtab->syms = (struct named_obj *) calloc (nsym,
						  sizeof (struct named_obj));
      if (symtab->syms == NULL)
	error (EXIT_FAILURE, errno, "while allocating symbol reference array");

      for (cnt = 1; cnt < nsym; ++cnt)
	{
	  GElf_Sym sym_mem;
	  GElf_Sym *sym = gelf_getsym (sdata, cnt, &sym_mem);
	  if (sym == NULL)
	    FATAL ();

	  if (GELF_ST_TYPE (sym->st_info) != STT_NOTYPE
	      && GELF_ST_TYPE (sym->st_info) != STT_OBJECT
	      && GELF_ST_TYPE (sym->st_info) != STT_FUNC
	      && GELF_ST_TYPE (sym->st_info) != STT_TLS)
	    continue;

	  struct symbol *symobj = NULL;
	  if (sym->st_shndx != SHN_UNDEF)
	    {
	      /* Recognize aliases.  */
	      int cnt2;
	      for (cnt2 = 1; cnt2 < cnt; ++cnt2)
		if (symtab->syms[cnt2].sym != NULL
		    && symtab->syms[cnt2].sym->scn == sym->st_shndx
		    && symtab->syms[cnt2].sym->from == sym->st_value)
		  {
		    symobj = symtab->syms[cnt2].sym;
		    break;
		  }
	    }

	  symtab->syms[cnt].name = elf_strptr (elf, sshdr->sh_link,
					       sym->st_name);

	  struct named_obj fake;
	  fake.name = symtab->syms[cnt].name;
	  struct named_obj **found = NULL;

	  if (cnt >= sshdr->sh_info)
	    found = tfind (&fake, &global_syms, global_compare);

	  if (symobj == NULL && cnt >= sshdr->sh_info && found != NULL)
	    {
	      symobj = (*found)->sym;

	      if (symobj->scn != SHN_UNDEF && sym->st_shndx != SHN_UNDEF)
		{
		  GElf_Shdr tshdr_mem;
		  GElf_Shdr *tshdr;
		  tshdr = gelf_getshdr (elf_getscn (elf, sym->st_shndx),
					&tshdr_mem);
		  if (tshdr == NULL)
		    FATAL ();

		  if ((tshdr->sh_flags & SHF_GROUP) == 0
		      && strncmp (".gnu.linkonce.",
				  elf_strptr (elf, ehdr->e_shstrndx,
					      tshdr->sh_name), 14) != 0)
		    error (EXIT_FAILURE, 0, "\
duplicate definition of %s in %s\nprevious definition in %s",
			   fake.name, newfile->fname,
			   (*found)->sym->file->fname);
		}
	    }
	  else if (symobj != NULL && found != NULL && (*found)->sym != symobj)
	    {
	      /* Merge two symbol objects.  */
	      struct named_obj *rn = (*found)->sym->names;

	      struct used_by *ur = (*found)->sym->used_by;
	      if (ur != NULL)
		{
		  while (ur->next != NULL)
		    ur = ur->next;
		  ur->next = symobj->used_by;
		  symobj->used_by = (*found)->sym->used_by;
		}

	      free ((*found)->sym);

	      do
		rn->sym = symobj;
	      while ((rn = rn->next) != NULL);
	    }

	  symtab->syms[cnt].sym = symobj;

	  if (symobj == NULL)
	    {
	      symtab->syms[cnt].sym = symobj
		= (struct symbol *) calloc (sizeof (struct symbol), 1);
	      if (symobj == NULL)
		error (EXIT_FAILURE, errno, "while allocating symbol data");
	    }

	  if (cnt >= sshdr->sh_info && found == NULL)
	    tsearch (&symtab->syms[cnt], &global_syms, global_compare);

	  if (symobj->scn == SHN_UNDEF && sym->st_shndx != SHN_UNDEF)
	    {
	      symobj->from = sym->st_value;
	      symobj->to = sym->st_value + sym->st_size;
	      symobj->scn = sym->st_shndx;
	      symobj->file = newfile;
	    }

	  symtab->syms[cnt].next = symobj->names;
	  symobj->names = &symtab->syms[cnt];
	}

      ++newfile->nhandled_symtab;
    }

  Elf_Data *data = elf_getdata (scn, NULL);
  if (data == NULL)
    FATAL ();

  int nrel = shdr->sh_size / shdr->sh_entsize;
  for (cnt = 0; cnt < nrel; ++cnt)
    {
      GElf_Off offset;
      GElf_Xword info;

      if (shdr->sh_type == SHT_REL)
	{
	  GElf_Rel rel_mem;
	  GElf_Rel *rel = gelf_getrel (data, cnt, &rel_mem);
	  if (rel == NULL)
	    FATAL ();

	  offset = rel->r_offset;
	  info = rel->r_info;
	}
      else
	{
	  GElf_Rela rel_mem;
	  GElf_Rela *rel = gelf_getrela (data, cnt, &rel_mem);
	  if (rel == NULL)
	    FATAL ();

	  offset = rel->r_offset;
	  info = rel->r_info;
	}

      if (ehdr->e_machine == EM_386 && GELF_R_TYPE (info) == R_386_GOTPC)
	continue;

      int cnt2;
      for (cnt2 = 1; cnt2 < nsym; ++cnt2)
	if (symtab->syms[cnt2].sym != NULL
	    && symtab->syms[cnt2].sym->scn == shdr->sh_info
	    && symtab->syms[cnt2].sym->from <= offset
	    && symtab->syms[cnt2].sym->to > offset
	    && symtab->syms[cnt2].sym->file == newfile)
	  break;

      if (cnt2 != nsym)
	{
	  if (symtab->syms[GELF_R_SYM (info)].sym == NULL)
	    {
	      if (GELF_R_SYM (info) >= sshdr->sh_info)
		FATAL ();

	      if (verbose)
		printf ("%s: %s needs something local\n",
			newfile->fname, symtab->syms[cnt2].name);
	    }
	  else if (GELF_R_SYM (info) >= sshdr->sh_info)
	    {
	      if (verbose)
		printf ("%s: %s needs %s\n",
			newfile->fname, symtab->syms[cnt2].name,
			symtab->syms[GELF_R_SYM (info)].name);

	      struct used_by *newu;
	      newu = (struct used_by *) malloc (sizeof (*newu));
	      if (newu == NULL)
		error (EXIT_FAILURE, errno, "while recording dependencies");

	      newu->sym = symtab->syms[cnt2].sym;
	      newu->next = symtab->syms[GELF_R_SYM (info)].sym->used_by;
	      symtab->syms[GELF_R_SYM (info)].sym->used_by = newu;
	    }
	  else if (verbose)
	    printf ("%s: %s needs local %s\n",
		    newfile->fname, symtab->syms[cnt2].name,
		    symtab->syms[GELF_R_SYM (info)].name);
	}
      else if (strcmp (".eh_frame", elf_strptr (elf, ehdr->e_shstrndx,
						dshdr->sh_name)) != 0
	       /* For switch statements.  */
	       && strncmp (".rodata", elf_strptr (elf, ehdr->e_shstrndx,
						  dshdr->sh_name), 7) != 0
	       && verbose)
	{
	  printf ("*** %s: location for reference of %s not found\n",
		  newfile->fname, symtab->syms[GELF_R_SYM (info)].name);
	}
    }
}


static void
handle_elf (Elf *elf, const char *fname)
{
  if (fname == NULL)
    error (EXIT_FAILURE, errno, "while allocating file name");

  struct fileinfo *newfile;
  newfile = (struct fileinfo *) calloc (1, sizeof (struct fileinfo));
  if (newfile == NULL)
    error (EXIT_FAILURE, errno, "while allocating file structure");

  newfile->fname = fname;
  newfile->next = allfiles;
  allfiles = newfile;

  GElf_Ehdr ehdr_mem;
  GElf_Ehdr *ehdr = gelf_getehdr (elf, &ehdr_mem);
  if (ehdr == NULL)
    FATAL ();

  if (ehdr->e_type != ET_REL)
    {
      fprintf (stderr, "ignoring %s, no relocatable object file\n", fname);
      return;
    }

  Elf_Scn *scn = NULL;
  while ((scn = elf_nextscn (elf, scn)) != NULL)
    {
      GElf_Shdr shdr_mem;
      GElf_Shdr *shdr = gelf_getshdr (scn, &shdr_mem);
      if (shdr == NULL)
	FATAL ();

      if (shdr->sh_type == SHT_REL || shdr->sh_type == SHT_RELA)
	handle_rel (elf, newfile, ehdr, scn, shdr);
      else if (shdr->sh_type == SHT_PROGBITS
	       && (shdr->sh_flags & SHF_ALLOC) != 0
	       && strcmp (".eh_frame", elf_strptr (elf, ehdr->e_shstrndx,
						   shdr->sh_name)) == 0)
	newfile->has_eh_frame = true;
    }
}


static void
read_dso (const char *fname)
{
  int fd = open (fname, O_RDONLY);
  if (fd == -1)
    error (EXIT_FAILURE, errno, "cannot open DSO '%s'", fname);

  Elf *elf = elf_begin (fd, ELF_C_READ_MMAP, NULL);
  if (elf == NULL)
    error (EXIT_FAILURE, 0, "cannot create ELF descriptor for DSO '%s': %s",
	   fname, elf_errmsg (-1));

  GElf_Ehdr ehdr_mem;
  GElf_Ehdr *ehdr = gelf_getehdr (elf, &ehdr_mem);
  if (ehdr == NULL)
    FATAL ();

  GElf_Off dynoff = 0;
  int cnt;
  for (cnt = 0; cnt < ehdr->e_phnum; ++cnt)
    {
      GElf_Phdr phdr_mem;
      GElf_Phdr *phdr = gelf_getphdr (elf, cnt, &phdr_mem);
      if (phdr->p_type == PT_DYNAMIC)
	{
	  dynoff = phdr->p_offset;
	  break;
	}
    }
  if (dynoff == 0)
    error (EXIT_FAILURE, 0, "DSO '%s' has no PT_DYNAMIC entry", fname);

  Elf_Scn *scn = NULL;
  GElf_Shdr shdr_mem;
  GElf_Shdr *shdr = NULL;
  while ((scn = elf_nextscn (elf, scn)) != NULL)
    {
      shdr = gelf_getshdr (scn, &shdr_mem);
      if (shdr == NULL)
	FATAL ();

      if (shdr->sh_offset == dynoff && shdr->sh_type == SHT_DYNAMIC)
	break;
    }

  if (scn == NULL)
    error (EXIT_FAILURE, 0, "cannot find PT_DYNAMIC section in DSO '%s'",
	   fname);

  GElf_Off symoff = 0;
  Elf_Data *data = elf_getdata (scn, NULL);
  cnt = 0;
  while (1)
    {
      GElf_Dyn dyn_mem;
      GElf_Dyn *dyn = gelf_getdyn (data, cnt++, &dyn_mem);
      if (dyn == NULL)
	FATAL ();

      if (dyn->d_tag == DT_SYMTAB)
	{
	  symoff = dyn->d_un.d_val;
	  break;
	}

      if (dyn->d_tag == DT_NULL)
	error (EXIT_FAILURE, 0, "cannot find DT_SYMTAB in DSO '%s'", fname);
    }

  scn = NULL;
  while ((scn = elf_nextscn (elf, scn)) != NULL)
    {
      shdr = gelf_getshdr (scn, &shdr_mem);
      if (shdr == NULL)
	FATAL ();

      if (shdr->sh_offset == symoff && shdr->sh_type == SHT_DYNSYM)
	break;
    }

  if (scn == NULL)
    error (EXIT_FAILURE, 0, "cannot find dynamic symbol table in DSO '%s'",
	   fname);

  data = elf_getdata (scn, NULL);
  int nsym = shdr->sh_size / shdr->sh_entsize;
  for (cnt = shdr->sh_info; cnt < nsym; ++cnt)
    {
      GElf_Sym sym_mem;
      GElf_Sym *sym = gelf_getsym (data, cnt, &sym_mem);
      if (sym == NULL)
	FATAL ();

      tsearch (elf_strptr (elf, shdr->sh_link, sym->st_name), &exported_syms,
	       (int (*) (const void *, const void *)) strcmp);
    }
}


static void
read_waived (const char *fname)
{
  FILE *fp = fopen (fname, "r");
  if (fp == NULL)
    error (EXIT_FAILURE, errno, "cannot open '%s'", fname);

  char *line = NULL;
  size_t len = 0;

  __fsetlocking (fp, FSETLOCKING_BYCALLER);

  while (!feof_unlocked (fp))
    {
      if (getline (&line, &len, fp) <= 0)
	break;

      char *cp = line;
      while (isspace (*cp))
	++cp;

      char *beg = cp;

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

      beg = strdup (beg);
      if (beg == NULL)
	error (EXIT_FAILURE, errno, "cannot read waive file");

      tsearch (beg, &waived, (int (*) (const void *, const void *)) strcmp);
    }

  free (line);

  fclose (fp);
}