Benchmark Factorial – Parámetros acumulados

Voy hacer un benckmark de 3 implementaciones de factorial:

Em primer lugar, la implementación más simple y eficiente, por siempre de los jamases, al menos para arquitecturas de Von Newman y monoprocesador:

long factorial_iterativo(long n)
{
	long i, ac = 1;
	for(i=n; i>0; i--)
		ac = ac * i;
	return ac;
}

Despues esta la recursiva lineal, típico ejemplo de recursividad. Fijaos en la linea de la llamada recursiva …

long factorial_recursivo(long n)
{
	if (n == 0)
		return 1;
	else
		return n * factorial_recursivo(n-1);
}

Y esta es la que realmente tenía curiosidad de comparar.  Es un tipo de recursividad que hace que la vuelta en lugar de ser de pila, sea de cola. Es necesario modificar la interfaz y crear una nueva función manejadora que respete la interfaz. Se trata de ir acumulando el resultado como parametro y principalmente que en la linea que se hace la llamada recursiva, solo haya una llamada recursiva.

Esta función, teoricamente implementado en Caml el compilador al pasarlo a código maquina la pasa a iterativa automaticamente. Si esto fuera tambien así en C, podríamos utilizar funciones recursivas, sin miedo a desbordar la pila y sin problemas de redimiento. Y por supuesto ganando la claridad de resolver algunos problemas de naturaleza recursiva.

long _factorial_recursivo_PA(long n, long r)
{
	if (n==0)
		return r;
	else
		return _factorial_recursivo_PA(n-1, n*r);
}

long factorial_recursivo_PA(long n)
{
	return _factorial_recursivo_PA(n, 1);
}

Los resultados son estos:

Seguir leyendo

Obtener información de Binarios y librerías compartidas (nm/objdump)

nm – Listado de funciones de un objeto

Si queremos obtener un listado de funciones que tiene un código objeto o una librería compartida se utiliza «nm», que lo descubrí de casualidad.
Este comando lista todos los símbolos que contiene el código objeto o la librería dinámica.
Por ejemplo vamos a crear una librería dinámica con solo una función llamada «factorial».
Este es el código:

#include <stdio.h>

int factorial(int n)
{
    return n == 0 ? 1 : n * factorial(n-1);
}

Lo compilo así:

gcc factorial.c -o libfactorial.so -shared -fPIC

Ahora analizamos la librería con el comando «nm»:

nm -D libfactorial.so

Obtenemos esto:

         w _Jv_RegisterClasses
00002010 A __bss_start
         w __cxa_finalize
         w __gmon_start__
00002010 A _edata
00002018 A _end
000004c8 T _fini
00000314 T _init
0000044c T factorial

Vemos que nuestro función en código maquina esta en el offset del archivo 0x44c.
Si leemos el man, obtenemos el significado de los símbolos:

Symbol Type Description
A The symbol’s value is absolute, and will not be changed by further linking.
B Un-initialized data section
D Initialized data section
T Normal code section
U Undefined symbol used but not defined. Dependency on another library.
W Doubly defined symbol. If found, allow definition in another library to resolve dependency.

Las funciones T son las linkables, exceptuando «_fini» y «_init» que son funciones comunes a cualquier librería dinámica. (Esto es una suposición mía, aunque muy lógica por otra parte).

Un ejemplo de código de linkado típico:

#include <stdio.h>

int factorial(int n);

int main()
{
 printf("5! = %d\n", factorial(5));
 return 0;
}

Se compila así:

gcc link.c -o link -L. -lfactorial

Y como la librería no esta en una ruta estándar, se ejecutaría así:

export LD_LIBRARY_PATH="." && ./link
5! = 120

Vamos a probar un código que linke dinamicamente, pero en lugar de el fácil «-lname», lo haré con el dload, que nos sirve de ejercicio para entender como funcionan las librerías dinámicas. El código es el siguiente:

#include <stdio.h> // para fprintf
#include <stdlib.h> // para exit
#include <dlfcn.h>  // para dlopen, dlsym, dlerror, dlclose

int factorial(int n);

int main(int argc, char **argv)
{
 void *lib_handle;
 int (*factorial)(int);
 int x;
 char *error;

 lib_handle = dlopen("libfactorial.so", RTLD_LAZY);
 if (!lib_handle)
 {
 fprintf(stderr, "%s\n", dlerror());
 exit(1);
 }

 factorial = dlsym(lib_handle, "factorial");
 if ((error = dlerror()) != NULL)
 {
 fprintf(stderr, "%s\n", error);
 exit(1);
 }

 x = factorial(5);
 printf("5! = %d\n",x);

 dlclose(lib_handle);
 return 0;
}

El código hay que mirarlo detenidamente, especialmente el puntero a función, pero por lo demás, es sencillo y se autocomenta.
Se compila así:

gcc -rdynamic -o dlopen dlopen.c -ldl

Probamos el ejecutable:

export LD_LIBRARY_PATH="." && ./dlopen
5! = 120

objdump – Desensamblando de binarios

Con este comando podemos obtener el código en ensamblador a partir del código maquina. El comando es el siguiente:

objdump -d libfactorial.so

Si además lo compilamos introduciendo los símbolos de debugeo (parámetro -g), podemos ver el código en ensamblador combinado con el código fuente. Se añadiría el parametro -S:

objdump -d -S libfactorial.so

Ya sabíamos que nuestra función «factorial» estaba en el offset 0x44c, por tanto lo busco en la salida de objdump y pasteo la salida (en este caso, con símbolos de debugeo):

0000044c <factorial>:
#include <stdio.h>

int factorial(int n)
{
 44c:	55                   	push   %ebp
 44d:	89 e5                	mov    %esp,%ebp
 44f:	53                   	push   %ebx
 450:	83 ec 14             	sub    $0x14,%esp
 453:	e8 ef ff ff ff       	call   447 <__i686.get_pc_thunk.bx>
 458:	81 c3 9c 1b 00 00    	add    $0x1b9c,%ebx
    return n == 0 ? 1 : n * factorial(n-1);
 45e:	83 7d 08 00          	cmpl   $0x0,0x8(%ebp)
 462:	74 14                	je     478 <factorial+0x2c>
 464:	8b 45 08             	mov    0x8(%ebp),%eax
 467:	83 e8 01             	sub    $0x1,%eax
 46a:	89 04 24             	mov    %eax,(%esp)
 46d:	e8 f2 fe ff ff       	call   364 <factorial@plt>
 472:	0f af 45 08          	imul   0x8(%ebp),%eax
 476:	eb 05                	jmp    47d <factorial+0x31>
 478:	b8 01 00 00 00       	mov    $0x1,%eax
}
 47d:	83 c4 14             	add    $0x14,%esp
 480:	5b                   	pop    %ebx
 481:	5d                   	pop    %ebp
 482:	c3                   	ret

Con el poco ensamblador que me enseñan en la uni, puedo deducir los siguientes offsets:

45e: Es la comparación de n con 0
462: Si la igualdad anterior se cumple, salta a la línea 44c + 2c = 478
478: Es el interior del IF, iguala el parámetro que viene de la pila con 1. Definiendo 0! = 1
464: Se ejecutaría si la comparación de 45e no se da. Se asigna la vuelta de la recursión
467: Se resta 1 a n
46a: Se prepara e parámetro n-1 en eax, previo a una llamada.
46d: Se hace la llamada recursiva a si mismo.
472: Se multiplica por 8 la vuelta de la recursión.
476: Estamos en el else, por tanto esta jmp se salta el interior del if. 44c + 31 = 47d
47d: De aquí en adelante prepara el return, deja la pila como estaba antes de la llamada y se restaura el IP.

Vamos a hacer algo fácil «crackear»(si se le puede llamar crackeo a esto xD) el programa para cambiar la asignación de:
0!=1 por 0!=4

Por tanto el 5! en lugar de dar 120 va dar 4 veces más, 480.

Para hello abrimos con algún editor de hexadecimal:

ghex2 libfactorial.so

Vamos al OFFSET 479 (478 + 1) y cambiamos el 01 por 04.

Hacemos la prueba de fuego:

export LD_LIBRARY_PATH="." && ./dlopen

Y efectivamente:

5! = 480

OuYeah!


Bueno con esto acabo, este articulo es sobre todo didáctico por lo que si alguno puede completar más el articulo con sus comentarios, se le agradeceremos todos.

Fuentes:
http://www.yolinux.com/TUTORIALS/LibraryArchives-StaticAndDynamic.html
http://unixhelp.ed.ac.uk/CGI/man-cgi?nm
http://node1.yo-linux.com/cgi-bin/man2html?cgi_command=ld
http://node1.yo-linux.com/cgi-bin/man2html?cgi_command=ldconfig