Random IRC quote :      <@matalaz> "El Euskera es una lengua que se habla en el Norte de Espaa y el Sur de Francia"

A naive (but fast) memory leak detection system

El objetivo de este post es el plantear un sistema de deteccion de leaks que sea lo suficientemente rapido como para ser usado en aplicaciones complejas o en aplicaciones que hagan un uso desmedido del heap. El objetivo es un sistema que sin un uso extra de memoria excesivo, y con una perdida de rendimiento minimo, sea capaz de detectar los leaks de nuestra aplicacion.

El codigo y las ideas que voy a exponer son solo un esbozo y una pequeña prueba de concepto. Quedaria un gran trabajo por hacer para llegar a obtener algo realmente funcional.

Y dicho esto, vamos a meternos de lleno en el tema.

La idea es bastante sencilla. Sabemos que el Heap de Windows devuelve bloques de memoria que estan alineados a ocho bytes. Sabemos que Windows divide a partes iguales el espacio de direcciones entre Kernel mode y User mode (vamos a ignorar el modo de inicio /3gb). En IA32 esto nos deja un espacio de direcciones de 2gb para el usuario. Ahora bien, si quisiesemos terner un bitmap que pudiese representar cualquier reserva de memoria necesitariamos
2gb/(8*8) = 32mb
O lo que es lo mismo. Con solo gastar 32mb podemos terner un bitmap que represente cualquier reserva. Con esto conseguimos una estructura a traves de la cual gestionar los mallocs que el usuario tiene en un momento dado.
Por otro lado, un sistema de este tipo necesita gestionar mas informacion a parte de los punteros de los mallocs. ¿Donde almacenamos esta informacion? Lo que haremos es añadir esa informacion al malloc que hagamos para satisfacer la peticion del usuario.
En este modelo tenemos dos ventajas: No hacemos mallocs extra para nuestras gestiones, y solo necesitamos tener en cuenta la sincronia en el bitmap que representa las peticiones de los usuarios que han sido satisfechas.

Comenzaremos definiendo una cabecera para las reservas que pidan los usuarios:

typedef struct _ALLOCATION_HEADER
{
  DWORD UserSize;
}ALLOCATION_HEADER, *LPALLOCATION_HEADER;
 

Y algunos defines:

#define _1GB_               (ULONG)(1024 * 1024 * 1024)
#define BYTE_BITS           (ULONG)(8)

#define HEAP_ALIGNMENT      (ULONG)(8)
#define LONG_BITS           (ULONG)(BYTE_BITS * sizeof(DWORD))
#define USER_ADDRESS_SPACE  (ULONG)(2 * _1GB_)
#define CONTROL_SIZE        (ULONG)(USER_ADDRESS_SPACE / (HEAP_ALIGNMENT * LONG_BITS))
 

El define CONTROL_SIZE sera el tamaño de un array de LONG’s que tiene 32MB de tamaño. Esto es, nuestro bitmap:

static LONG AllocControl[CONTROL_SIZE] = {0};
 

Ahora un par de funciones hacer set/clear de un bit en el bitmap (Añadir o quitar un malloc). Estas funciones son triviales, y tan solo hay que tener cuidado de asegurarnos de que se puede acceder correctamente desde varios hilos de forma concurrente. En este caso el tiempo que tarda en ejecutarse el codigo que hay que proteger es despreciable por lo que no tiene sentido usar una seccion critica (Si queremos asegurar la correcta sincronia y no queremos implementarla nosotros mismos una alternativa aceptable podria ser una seccion critica, pero siempre con un spinlock adecuado)

static
__inline
void
SetMalloc(LPVOID Buffer)
{
  DWORD MallocInfo = (DWORD)(ULONG_PTR)Buffer / HEAP_ALIGNMENT;
  LONG *SegmentAddr = &(AllocControl[MallocInfo / LONG_BITS]);
  DWORD NewBit  = 1 << (MallocInfo % LONG_BITS);
  DWORD Segment;

  do
  {
    Segment = *SegmentAddr;
  }while(InterlockedCompareExchange(SegmentAddr, Segment | NewBit, Segment) != Segment);
}

static
__inline
void
ClearMalloc(LPVOID Buffer)
{
  DWORD MallocInfo = (DWORD)(ULONG_PTR)Buffer / HEAP_ALIGNMENT;
  LONG *SegmentAddr = &(AllocControl[MallocInfo / LONG_BITS]);
  DWORD OldBit  = 1 << (MallocInfo % LONG_BITS);
  DWORD Segment;

  do
  {
    Segment = *SegmentAddr;
  }
  while(InterlockedCompareExchange(SegmentAddr, Segment & ~OldBit, Segment) != Segment);
}
 

La funcion malloc:

void * malloc_detect_leaks(size_t size)
{
  size_t RealSize;
  LPALLOCATION_HEADER Header;
  LPVOID Result = NULL;

  RealSize = size + sizeof(ALLOCATION_HEADER);

  Header = (LPALLOCATION_HEADER) malloc(RealSize);
  if(Header != NULL)
  {
    SetMalloc(Header);
    Header->UserSize = size;
    Result = Header + 1;
  }
  return Result;
}
 

El calloc:

void * calloc_detect_leaks(size_t n, size_t size)
{
  size_t RealSize;
  LPALLOCATION_HEADER Header;
  LPVOID Result = NULL;

  size *= n;
  RealSize = size + sizeof(ALLOCATION_HEADER);

  Header = (LPALLOCATION_HEADER) calloc(1, RealSize);
  if(Header != NULL)
  {
    SetMalloc(Header);
    Header->UserSize = size;
    Result = Header + 1;
  }
  return Result;
}
 

El free:

void free_detect_leaks(void * ptr)
{
  if(ptr != NULL)
  {
    LPALLOCATION_HEADER Header = (LPALLOCATION_HEADER) ptr;

    Header -= 1;

    ClearMalloc(Header);    
    free(Header);
  }
}
 

Y el realloc. En el caso del realloc es importante el orden en el que se llevan a cabo las acciones. Este orden es evidente si revisamos el significado estricto de las estructuras de datos que utilizamos. Nuestro bitmap representa los mallocs que hemos satisfecho. Antes del realloc es necesario eliminar la reserva del usuario del Bitmap (Aunque mas tarde tengamos que volvera a añadirla). Si no lo hiciesemos asi necesitariamos estructuras de control extra para evitar problemas de sincronia:

void *realloc_detect_leaks(void *ptr, size_t size)
{
  LPALLOCATION_HEADER Old = NULL;
  LPALLOCATION_HEADER New = NULL;
  LPVOID Result = NULL;
  DWORD RealSize = 0;

  if(ptr != NULL)
  {
    Old = (LPALLOCATION_HEADER)ptr;
    Old -= 1;
    ClearMalloc(Old);
  }

  RealSize = size;
  if(RealSize != 0)
  {
    RealSize += sizeof(ALLOCATION_HEADER);
  }

  New = (LPALLOCATION_HEADER)realloc(Old, RealSize);
  if(RealSize != 0)
  {
    if(New != NULL)
    {
      SetMalloc(New);
      New->UserSize = size;
      Result = New + 1;
    }
    else
    {
      if(Old != NULL)
      {
        SetMalloc(Old);
      }
    }
  }
  return Result;
}
 

Y por ultimo, una funcion que genera un fichero de dump muyh basico con los leaks de nuestra aplicacion:

void DumpLeaks(LPCSTR FilePath)
{
  FILE *File;

  File = fopen(FilePath, "a+t");
  if(File != NULL)
  {
    DWORD ControlSegment = 0;
    DWORD i;

    for(i = 0; i < CONTROL_SIZE ; ++i)
    {
      DWORD SegMent = AllocControl[i];
      DWORD Offset = 0;

      while(SegMent != 0)
      {
        if((SegMent & 1) != 0)
        {
          LPALLOCATION_HEADER Leak = (LPALLOCATION_HEADER)(ControlSegment + Offset);
          LPBYTE Buffer;
          int Size;

          Size = Leak->UserSize;
          Buffer = (LPBYTE)(Leak + 1);

          fprintf(File, "\nLeak of %d bytes at 0x%0p\nDump:\n", Size, Buffer);

          while(Size != 0)
          {
            int LineSize = min(Size, 16);
            int i = 0;

            for(i = 0 ; i < LineSize ; i++)
            {
              fprintf(File, "%02x ", Buffer[i]);
            }

            for(;i < 16 ; i++)
            {
              fprintf(File, "   ");
            }

            fprintf(File, "| ");

            for(i = 0 ; i < LineSize ; i++)
            {
              if(Buffer[i] < 32 || Buffer[i] == 127)
              {
                fprintf(File, " ");
              }
              else
              {
                fprintf(File, "%c", Buffer[i]);
              }
            }

            for(;i < 16 ; i++)
            {
              fprintf(File, " ");
            }
            fprintf(File, "\n");

            Size -= LineSize;
            Buffer += LineSize;
          }

          fprintf(File, "\n");
        }
        SegMent >>= 1;
        Offset += HEAP_ALIGNMENT;
      }
      ControlSegment += LONG_BITS * HEAP_ALIGNMENT;
    }
    fclose(File);
  }
}
 

En las pruebas que he llevado a cabo la perdida de rendimiento no se aprecia, y el gasto de memoria extra es de 32MB mas un DWORD por cada malloc. Lo cierto es que el bitmap de 32MB puede reducirse considerablemente con una implementacion adecuada, aunque una implementacion mas util añadiria algo mas de overhead a cada malloc.

Sea como sea, al prueba de concepto parece valida, y a partir de aqui se podria seguir construyendo un Leak Detector bastante rapido.

Esto es una prueba de concepto que he implementado en un par de horas, asi que pido disculpas publicamente porque lo cierto es que el codigo esta bastante descuidado.

Y esto es to to todo amigos!!

7 Comentarios para “A naive (but fast) memory leak detection system”

  1. Comment por José Antonio | 09/01/10 at 5:48 pm

    Algun libro que recomiendes para poder entender lo que escribiste??

  2. Comment por Hermis Antonio Juarez | 09/07/10 at 3:02 pm

    Para el amigo anterior del comentario es bastante dificil que entendas si no tenes los conocimientos suficientes de Programacion y mucho menos saber que son los Leaks por lo demas el detector esta bastante bien el codigo se ve muy sencillo un poco mas de orden no estaria nada mal Saludos!

    Hermis Antonio Juarez
    Analista de Sistemas y Seguridad Informatica!

  3. abc
    Comment por abc | 09/14/10 at 8:25 am

    Why not just you AppVerifier (Application Verifier) ?

  4. Comment por Miguel | 09/14/10 at 12:01 pm

    abc,

    You are rigth. Today in day you have some interesting tools and many built in features in the operating systems and compilers. Application Verifier is a good example. If you are looking for a easy to use tool, LeakDiag could be the best choice. There are other powerful tools like purify or BoudsChecker that offers you a interesting bunch of options. Finally, you can also try to develop something based on the debugging facilities exposed by the ntdll heaps, or by the runtime that you are using.

    But I think that the main problem with all those approach is that there are platform specific or, even worse, compiler specific. The other point is that with that solutions you have a limited capacity to set up different options when for example you are hunting a heisenbug. Imagine that you are only interesting in tracking BIG allocations. If you dont have your own infrastructure you can be in trouble.

    Finally, I also have to say that this small post only shows a first step about what to do (IMHO). I think that even when its hard to sell, a good debugging platform in your application is very useful.

  5. Comment por Miguel | 09/14/10 at 12:37 pm

    Well, I want to write an addendum to my last comment. I think that nowdays we usually focus on dynamic analyzers when we are trying to find and solve memory leaks and other bugs.
    I think that static analyzers can be a very usefull tool. I have worked with Lint, Klockwork and Coverity. Maybe today in day there are a bit limited because they dont know very much about the platform, and they have some problems when they are dealing with things like pointer to funcions or abstract classes. But I think that with things like source code annotations those applications can be highly improved. In my oponion, in a near future we will need to do both dynamic and static analysis in order to minimize bugs and assure quality. Moreover, I already do it.

  6. Comment por IvanHernanz | 09/21/10 at 4:47 pm

    Hola, un post muy interesante.

    El problema que veo aqui es que si realizas el analisis en dinamico, tendras el sempieterno problema de la cobertura de codigo, ya que te puedes encontrar con flujos del programa por donde no se ejecute y de igual forma tu pseudo-instrumentacion.

    Creo que los memory leaks los podrias localizar con un «analisis estatico» del programa, ya que es un problema de Data Flow Analysis, concretamente un Def-Use, (tipico en optimizacion de compiladores) con un framework interprocedural (utilizando el algoritmo iterativo).

    Estoy ahora mismo un poco liado, pero si te interesa o le interesa a alguien podriamos montar una POC a ver que tal.

    No se … Ya me contais. Saludetes.

  7. Comment por Miguel | 09/22/10 at 10:40 am

    Ivan,

    Totalmente de acuerdo contigo. Al final durante el análisis dinámico es muy difícil conseguir una cobertura de código completa. Se suele llegar a un punto en el que aumentar el porcentaje de cobertura significa realizar un esfuerzo difícil de asumir para una empresa que no ve un beneficio en esas tareas, y para el programador para el que la tarea seguramente sea bastante aburrida. Y aunque se usen procesos de desarrollo de Software orientados como por ejemplo TDD, al final en mayor o menor medida el problema siempre persiste.

    Si embargo tampoco creo que el análisis estático sea la solución definitiva. Como ya dije en uno de los comentarios anteriores, los analizadores estáticos pueden tener problemas en situaciones tales como el uso de punteros a función, o con las herencias. Además, tampoco he visto ningún analizador estático que tenga en cuenta seriamente la posibilidad de encontrarse en un entorno multithread o gestionar variables volátiles, y en la mayoría de los casos también suelen tener un conocimiento muy limitado del sistema operativo.

    Personalmente creo que a los analizadores estáticos son herramientas muy útiles, pero los test de calidad siempre van a requerir una mezcla de análisis dinámico y análisis estático. Pero aparte de la necesidad de análisis dinámicos, el análisis estático de código me parece muy interesante. Es un campo en el que creo que quedan muchas cosas por hacer.

Se han cerrado los comentarios