/* -*- linux-c -*- 
 * symbols.c - stp symbol and module functions
 *
 * Copyright (C) Red Hat Inc, 2006-2008
 *
 * This file is part of systemtap, and is free software.  You can
 * redistribute it and/or modify it under the terms of the GNU General
 * Public License (GPL); either version 2, or (at your option) any
 * later version.
 *
 * The u32_swap(), generic_swap(), and sort() functions were adapted from
 * lib/sort.c of kernel 2.6.22-rc5. It was written by Matt Mackall.
 */

#ifndef _STP_SYMBOLS_C_
#define _STP_SYMBOLS_C_
#include "../sym.h"



static void _stp_create_unwind_hdr(struct _stp_module *m);


static void _stp_do_relocation(const char __user *buf, size_t count)
{
  struct _stp_msg_relocation msg;
  unsigned mi, si;

  if (sizeof(msg) != count)
    {
      errk ("STP_RELOCATE message size mismatch (%lu vs %lu)\n",
            (long unsigned) sizeof(msg), (long unsigned) count);
      return;
    }

  if (unlikely(copy_from_user (& msg, buf, count)))
    return;

  dbug_sym(2, "relocate (%s %s 0x%lx)\n", msg.module, msg.reloc, (unsigned long) msg.address);


  /* Save the relocation value.  XXX: While keeping the data here is
     fine for the kernel address space ("kernel" and "*.ko" modules),
     it is NOT fine for user-space apps.  They need a separate
     relocation values for each address space, since the same shared
     libraries/executables can be mapped in at different
     addresses.  */

  for (mi=0; mi<_stp_num_modules; mi++)
    {
      if (strcmp (_stp_modules[mi]->name, msg.module))
        continue;

      for (si=0; si<_stp_modules[mi]->num_sections; si++)
        {
          if (strcmp (_stp_modules[mi]->sections[si].symbol, msg.reloc))
            continue;

          _stp_modules[mi]->sections[si].addr = msg.address;
        } /* loop over sections */
    } /* loop over modules */
}


static int _stp_compare_addr(const void *p1, const void *p2)
{
	struct _stp_symbol *s1 = (struct _stp_symbol *)p1;
	struct _stp_symbol *s2 = (struct _stp_symbol *)p2;
	if (s1->addr == s2->addr)
		return 0;
	if (s1->addr < s2->addr)
		return -1;
	return 1;
}

static void _stp_swap_symbol(void *x, void *y, int size)
{
	struct _stp_symbol *a = (struct _stp_symbol *)x;
	struct _stp_symbol *b = (struct _stp_symbol *)y;
	unsigned long addr = a->addr;
	const char *symbol = a->symbol;
	a->addr = b->addr;
	a->symbol = b->symbol;
	b->addr = addr;
	b->symbol = symbol;
}

static void u32_swap(void *a, void *b, int size)
{
	u32 t = *(u32 *)a;
	*(u32 *)a = *(u32 *)b;
	*(u32 *)b = t;
}

static void generic_swap(void *a, void *b, int size)
{
	do {
		char t = *(char *)a;
		*(char *)a++ = *(char *)b;
		*(char *)b++ = t;
	} while (--size > 0);
}

/**
 * sort - sort an array of elements
 * @base: pointer to data to sort
 * @num: number of elements
 * @size: size of each element
 * @cmp: pointer to comparison function
 * @swap: pointer to swap function or NULL
 *
 * This function does a heapsort on the given array. You may provide a
 * swap function optimized to your element type.
 *
 * Sorting time is O(n log n) both on average and worst-case. While
 * qsort is about 20% faster on average, it suffers from exploitable
 * O(n*n) worst-case behavior and extra memory requirements that make
 * it less suitable for kernel use.
*/
void _stp_sort(void *base, size_t num, size_t size,
	       int (*cmp) (const void *, const void *), void (*swap) (void *, void *, int size))
{
	/* pre-scale counters for performance */
	int i = (num / 2 - 1) * size, n = num * size, c, r;

	if (!swap)
		swap = (size == 4 ? u32_swap : generic_swap);

	/* heapify */
	for (; i >= 0; i -= size) {
		for (r = i; r * 2 + size < n; r = c) {
			c = r * 2 + size;
			if (c < n - size && cmp(base + c, base + c + size) < 0)
				c += size;
			if (cmp(base + r, base + c) >= 0)
				break;
			swap(base + r, base + c, size);
		}
	}

	/* sort */
	for (i = n - size; i >= 0; i -= size) {
		swap(base, base + i, size);
		for (r = 0; r * 2 + size < i; r = c) {
			c = r * 2 + size;
			if (c < i - size && cmp(base + c, base + c + size) < 0)
				c += size;
			if (cmp(base + r, base + c) >= 0)
				break;
			swap(base + r, base + c, size);
		}
	}
}

/* filter out section names we don't care about */
static int _stp_section_is_interesting(const char *name)
{
	int ret = 1;
	if (!strncmp("__", name, 2)
	    || !strncmp(".note", name, 5)
	    || !strncmp(".gnu", name, 4)
	    || !strncmp(".mod", name, 4))
		ret = 0;
	return ret;
}


#endif /* _STP_SYMBOLS_C_ */