El nuevo estándar de C, C11

Este año que termina nos deja con la actualización de dos grandes lenguajes de programación: C++ (vimos sus cambios en un artículo de dos partes y C, que lanzó C11 hace apenas dos semanas, con no demasiadas novedades que tratan de estandarizar características que muchos compiladores incluyen ya desde hace tiempo, y añadir una serie de mejoras al manejo de threads o de operaciones atómicas, así como añadir más compatibilidad con C++ (y en específico con su nueva versión, C++11).

Veamos algunos de los cambios con más detenimiento...

Funciones sin retorno (_Noreturn)

Se añade un modificador nuevo que permite al compilador optimizar el código de una función en caso de que nosotros especifiquemos que nunca va a retornar al llamante.

#include <nostdreturn.h>

void noreturn crash() {
    printf("Uops! :D\n");
    exit(-1);
}

Podemos usarlo en funciones que típicamente tratan casos de error que finalizan el programa por ejemplo.

Aparte, se añade un nuevo fichero de cabeceras, nostdreturn.h, donde se define la palabra clave noreturn como alias de _Noreturn.

Eliminada la función gets

Se elimina finalmente la función gets de la librería de C.

Esta función lee desde la entrada estándar un número indeterminado de carácteres (hasta un fin de línea). El hecho de que no se pueda especificar el máximo provoca que sea muy sencillo provocar un desbordamiento del buffer donde se están guardando esos carácteres.

#include <stdio.h>
char *gets_s(char *s, rsize_t n);

Para evitar los enormes problemas de seguridad que esto conlleva, en este nuevo estándar se elimina la función (ya en C99 estaba des-recomendada), y se aconseja el uso de la nueva función gets_s, que posee la misma cabecera, añadiendo un parámetro en el que se especifica el número máximo de carácteres a leer (menos 1, para el \0).

Mayor soporte de cadenas unicode

Al igual que en C++, y de una forma compatible con él, se añaden nuevos tipos de datos y aliases para manejar cadenas unicode. Se da soporte a tres representaciones distintas de unicode: UTF-8, UTF-16, UTF-32.

Hasta ahora estos formatos se representaban usualmente mediante los tipos char, unsigned short y unsigned long. El problema es que el tamaño de esos tipos de datos es dependiente de la plataforma y el compilador, por lo que no se podía hacer código portable.

Este nuevo estándar (al igual que el de C++), crea dos nuevos tipos de datos, llamados char16_t y char32_t, creados con el objetivo de representar carácteres en UTF-16 y UTF-32 respectivamente. UTF-8 seguirá usando un char normal. Además, se permite crear literales en las tres representaciones mencionadas marcando la cadena de carácteres con uno de los siguientes tres prefijos: (u8, u, U).

Por último, se añaden nuevas funciones en la librería estándar (almacenadas en uchar.h) para realizar conversiones entre los distintos formatos.

Si quieres más información sobre esto puedes consultar la primera parte del artículo sobre C++11.

Aserciones estáticas (static_assert)

Al igual que C++11, esta nueva versión de C añade una nueva palabra clave, static_assert, que permite añadir aserciones en el código que se ejecutan a nivel de compilador.

Las aserciones se encargan de comprobar condiciones que tienen que cumplirse a la hora de ejecutar una sección de código. Lo que hace especiales a estas aserciones es que no se ejecutan en tiempo de ejecución (cuando el programa es ejecutado por el usuario), si no que son comprobaciones realizadas en la fase de compilación (en una fase tardía donde los tipos son conocidos).

static_assert(sizeof(void*) >= 8, "No eres de 64-bit :P");

Este tipo de aserciones completa a las dos existentes anteriormente. La que se ejecuta con el preprocesador, #error, y la que se ejecuta en tiempo de ejecución, assert().

Funciones con comprobación de fronteras

El título de esta sección queda un poco críptico (no sabía muy bien como traducirlo), pero no es nada nuevo. El nuevo estándar de C añade una serie de funciones a la parte de su librería estándar encargada de manejar cadenas de carácteres. Estas nuevas funciones, cuyos nombres terminan mediante el sufijo _s, se diferencian de sus hermanas por comprobar los límites de los arrays usados como buffers antes de realizar las operaciones pertinentes.

char* strcat(char *s1, const char *s2);
errno_t strcat_s(char *s1, size_t n, const char *s2);

Como puede verse, la diferencia entre strcat y strcat_s es el segundo parámetro, que indica el número máximo de elementos que puede albergar el buffer de destino. Gracias a ese parámetro la función puede hacer más comprobaciones en tiempo de ejecución, comprobando que no se sobrepase el límite de memoria que tiene asignado el buffer de destino, por ejemplo.

Al igual que para strcat, se han añadido versiones con comprobación de fronteras para otras tantas funciones de la librería estándar.

Estructuras anónimas

Tras ser durante mucho tiempo soportadas en C++ se añade a este nuevo estándar el soporte de estructuras y uniones anónimas.

Estas estructuras son idénticas a las normales, salvando que no tienen un nombre mediante las que ser identificadas. Son muy útiles, por ejemplo, para crear código menos verboso a la hora de incorporar estructuras anidadas.

struct Persona {
    char *nombre;
    union {
        long dni;
        char *pasaporte;
    }
}

struct Persona p1;
p1.dni = 7987271;

Como puede verse en el fragmento de código anterior, al ser el unión anónimo, para acceder a sus campos no es preciso anteponer ningún nombre, dejando un código más claro y legible.

Manejo de threads

Este es posiblemente el cambio más grande que nos da este nuevo estándar. Se ha añadido el soporte a threads en la librería estándar, sin necesidad de usar librerías externas como hasta ahora con, por ejemplo, los threads POSIX (pthread.h).

Se ha añadido un nuevo fichero llamado threads.h en el que han incluído nuevos tipos de datos y funciones para ayudar a programar de forma concurrente. Se incluye el manejo de threads, así como de mutex y variables condicionales (para sincronización).

Dejamos el uso de esta librería para otro artículo separado, que hay mucho de lo que hablar... :)

Macros genéricas

Se añade algo con el mismo olor (salvando las distancias) a los templates de C++. Se pueden crear macros genéricas, que permitan seguir uno u otro camino con respecto al tipo de los parámetros recibidos.

#define cbrt(X) _Generic((X), long double: cbrtl, \
                            default: cbrt, \
                            float: cbrtf)(X)

Este es el típico ejemplo para demostrar el funcionamiento de estas macros. La familia de funciones cbrt se encarga de hallar la raíz cúbica de un número, existiendo tres distintas funciones dependiendo de si el parámetro pasado es un long, un int o un float. Gracias a las nuevas macros genéricas podemos crear una macro que traduzca la llamada a la función correcta dependiendo del tipo del parámetro pasado.

Y hasta aquí...

Y poco más que contaros en este artículo. No son todas las novedades que da este nuevo estándar, pero si que son las más importantes a mi modo de ver. Si investigais un poco más podréis ver como se añaden igualmente ciertas funciones para facilitar el alineamiento de datos, así como para finalizar de forma segura un programa, mejor manejo de números complejos, ...

¡Feliz año nuevo para todos! :D

Listas Circulares en Linux

En este post vamos a ver uno de esos pequeños detalles que te hacen esbozar una sonrisa cuando los ves. Código que parece que literalmente, hace magia. Vamos a analizar una pequeñísima porción del código fuente de Linux.

A lo largo de las miles de lineas de código que tiene Linux se usan continuamente listas circulares. En el principio de los tiempos, cada programador se hacía su propia implementación, haciendo que el código fuese poco mantenible.

Hasta que llegado cierto momento en el desarrollo de la v2.1 se decidió realizar una implementación genérica, y portar todo el código existente a este nuevo sistema. Estas listas se usan actualmente en todo el kernel (lista de procesos, drivers, sistemas de ficheros soportados, ...). Pero antes de ver por qué el diseño que usan en Linux es tan bonito, hagamos una pequeña introducción sobre lo que es una lista circular, y como se suelen implementar.

Si todo esto ya te lo sabes, puedes saltar a la siguiente sección.

Listas Circulares

Las listas circulares son una de las estructuras de datos más básicas que existen. Consisten en una sucesión de elementos (una lista normal y corriente), en la que el último elemento apunta al primero, de tal manera que se puede recorrer de forma circular.

|filename|images/0004-listas-circulares-linux/lista-simple.png

Dentro de estas listas circulares, podemos subdividirlas mediante muchos criterios. Uno de los más usados es el número de enlaces que tiene. Las que son enlazadas simples (permiten recorrerse solo en un orden), y las que son doblemente enlazadas (a partir de un elemento, podemos visitar al anterior y al siguiente).

A diferencia de los arrays estáticos (como pudiese ser uno de C), nuestra lista circular no necesita saber cuantos elementos va a tener en tiempo de compilación, debido a que gracias al tratamiento de punteros y a la memoria dinámica del sistema, podremos ir variando su tamaño a nuestro antojo.

Típicamente las listas enlazadas se suelen implementar mediante un struct que contiene, aparte del elemento en cuestión, un puntero a una estructura de su mismo tipo, mediante el cual apuntar al elemento siguiente.

En caso de que quisiésemos implementar una lista doblemente enlazada, sólo tendríamos que añadir un puntero más, en este caso apuntado al elemento anterior.

struct nodo {
    int elemento;
    struct nodo * siguiente;
};

Así de simple. Para usar esta lista, nos bastaría con crear un par de elementos e iniciar sus atributos de forma correcta.

Como con una lista se suelen realizar tareas muy comunes (añadir, eliminar, iterar, ...) lo lógico sería crear un par de funciones que nos facilitasen la tarea.

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

typedef struct nodo {
    int elemento;
    struct nodo * siguiente;
} nodo;

int add_nodo(nodo **l, int e) {
    nodo *nuevo = (nodo *) malloc(sizeof(nodo));

    if (!nuevo)
        return -ENOMEM;

    nuevo->elemento = e;
    nuevo->siguiente = *l;
    *l = nuevo;

    return 0;
}

void imprimir_lista(nodo *l) {
    printf("Los elementos de la lista son: ");

    while (l != NULL) {
        printf("%d, ", l->elemento);
        l = l->siguiente;
    }

    printf("\n");
}

int main(void) {
    nodo *l1 = NULL;

    add_nodo(&l1, 10);
    add_nodo(&l1, 20);
    add_nodo(&l1, 50);
    imprimir_lista(l1);

    // No estamos liberando la memoria solicitada... ¬¬
    return 0;
}

En este código podemos ver como tenemos dos funciones (es un ejemplo muy escueto).

La primera, add_nodo, nos sirve para añadir una elemento a la lista circular. Este elemento se reserva en el heap del sistema, usando para ello la llamada malloc(3). Una vez reservada la memoria, se introduce delante del nodo que le pasamos como parámetro.

La segunda, imprimir_lista, simplemente itera a partir de un nodo recorriéndolos todos hasta llegar al pasado como parámetro de nuevo.

Esta implementación, que es muy parecida a la que se sigue en muchísimos casos, tiene como problema que no se puede generalizar la solución para otros tipos de datos.

Es decir, en nuestro anterior ejemplo, los elementos que guardamos son enteros (en la estructura que identifica nuestra lista podemos ver como el elemento es un int). Si queremos crear otra lista con otro tipo de elementos, tendremos que implementar un nuevo struct (con otro nuevo set de funciones para añadir, eliminar, iterar...).

Como podéis ver, este es un trabajo muy repetitivo, que al final hace que se repita muchísimo código, con pequeñas diferencias.

Formas de solucionar esto hay varias.

Por ejemplo, podríamos usar punteros genéricos, lo que nos permite guardar en la lista cualquier tipo de objeto.

Básicamente consiste en guardar un puntero a algo (void*), de tal manera que al añadir un elemento en la lista no guardaremos el elemento en sí, si no un puntero al mismo. Debido a que un puntero siempre ocupa lo mismo (independientemente del tipo del dato apuntado), este sistema nos permitiría guardar cualquier tipo de dato.

Esta solución, sin embargo, aunque arregla este problema, crea otros tantos, como que hay que castear el objeto antes de poder usarlo, o que al pasar a guardar un puntero del objeto, en vez del objeto en si, tenemos que tener cuidado con que a lo largo de la vida de la lista ese objeto no deje de existir (porque fue creado en la pila de otra función por ejemplo).

La solución de Linux

Linux implementa una lista doblemente enlazada circular.

|filename|images/0004-listas-circulares-linux/lista-circular.png

Aparte, no existe el concepto de primer y último nodo. No le dan ningún tipo de importancia a esta información. Facilitan formas de recorrer la lista entera, independientemente de que nodo cojamos como cabecera de la lista.

Pero lo que hace especial a la solución de Linux es que pasa por embeber la propia lista dentro de nuestra estructura... y no al revés; es decir, le dan la vuelta a la tortilla.

En vez de tener nuestro elemento guardado dentro del struct, lo que se hace es meter la estructura que representa a un nodo, dentro de nuestro propio dato.

Así explicado suena un poco raro, así que pasemos a ver código real. El struct que representa estas listas se llama list_head. Y si miramos como está implementado veremos que tiene únicamente dos elementos:

struct list_head {
    struct list_head *next, *prev;
};

Un puntero al siguiente elemento, y otro al anterior (como vimos anteriormente).

Para usar estas listas únicamente tendremos que insertar un elemento struct list_head en nuestra propia estructura. Vamos a realizar un ejemplo parecido al anterior, pero ahora usando las listas circulares de Linux.

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include "list.h"

typedef struct {
    struct list_head lista;
    int elemento;
} nodo;

int main(void) {
    struct list_head *iter;
    nodo n_head, *aux;

    // Inicializamos la lista
    INIT_LIST_HEAD(&n_head.lista);

    for (i=0; i<5; i++) {
        aux = (nodo*) malloc(sizeof(nodo));

        if (!aux)
            return -ENOMEM;

        aux->elemento = i;

        // Añadimos un elemento más a la lista
        list_add(&aux->lista, &n_head.lista);
    }

    // Recorremos todos los elementos
    printf("Los elementos de la lista son: ");

    list_for_each(iter, &n_head.lista) {
        // Extraemos nuestro struct de la lista
        aux = list_entry(iter, nodo, lista);
        printf("%d, ", aux->elemento);
    }

    printf("\n");

    // Volvemos a olvidarnos de liberar la memoria
    return 0;
}

Es un ejemplo muy sencillo en el que podemos ver la potencia de la API de estas listas. Como podemos ver, tenemos una estructura nodo, que aparte de guardar nuestro elemento (igual que en el caso anterior), contiene un elemento de tipo struct list_head, que será el que guarde la referencia a nuestra lista circular.

Mencionar, que se pueden insertar tantos list_head como se quiera; es decir, que un mismo elemento puede pertenecer a infinitas listas circulares.

En este caso, creamos un nodo que usaremos como cabecera de la lista (aunque como ya dijimos, para estas listas todos los nodos tienen la misma importancia), y a partir de él, inicializamos la lista con la macro INIT_LIST_HEAD.

A continuación, con list_add, añadimos un total de 5 elementos. Esta macro recibe dos parámetros. Como primer parámetro, el nodo a insertar. Y como segundo, el nodo tras el cual queremos insertar el elemento.

Y por último, imprimimos los números insertados. Especial atención a las dos macros usadas aquí. list_for_each, que se expande a un bucle for normal y corriente (con prefetching), que a partir del pivote usado (el segundo parámetro) empieza a recorrer todos los nodos de la lista (guardándolos en el iterador, el primer parámetro) hasta llegar al nodo pivote de nuevo.

Y list_entry, que es la macro que hace realmente la magia (la analizaremos con más calma después). Gracias a esta macro conseguiremos extraer el elemento (nuestro struct nodo), a partir del list_head que tenemos guardado en la variable iter.

La API de estas listas es muy rica, proporcionando funciones (macros realmente) para insertar elementos antes o después de nuestro pivote, para recorrerlas del derecho o del revés, para activar o desactivar el prefetching, ...

Es un módulo a usar siempre que necesitemos listas, independientemente de que estemos desarrollando para el kernel o no (todo el código está contenido en un fichero que no tiene dependencias externas).

¿Y cómo demonios hace eso?

Pasemos a ver un poco el código del kernel. La implementación de las listas circulares la podemos ver en el fichero include/linux/list.h

Merece la pena leer todo el código de la librería, llamando poderosamente la atención una cosa. ¿Cómo consigue la lista devolver la estructura contenedora a partir de la referencia a su propio campo? Es decir, y usando nuestro ejemplo anterior... ¿Como puede C, a partir de una referencia al struct list_head, sacar el struct nodo en el cual está contenido?

La encargada de ello es la función list_entry, que a parte de que resulta ser una macro, tiene un código muy sencillo. Únicamente llama a la macro container_of.

Esta macro es la que realiza toda la magia (no solo se usa para las listas circulares), y podemos encontrarla desarrollada en el fichero include/linux/kernel.h.

Recibe tres parámetros (los mismos que list_entry):

ptr
El puntero al campo de la estructura.
type
El tipo de estructura que queremos sacar (a la cual pertenece el campo anterior)
member
El nombre del campo que estamos pasando desde el primer parámetro.

Analicemos paso a paso el código de la macro container_of.

#define container_of(ptr, type, member) ({          \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})

Es muy poco código (apenas dos líneas), pero veremos como condensa mucha información.

Para empezar, la estructura principal es bastante rara. Contiene dos instrucciones rodeadas mediante un par de paréntesis y llaves. Para entender que es esta estructura, vamos a poner un ejemplo muy simple

#include <stdio.h>

int main(void) {
    int num = ({int i = 0; i+100;});
    printf("%d\n", num);
    return 0;
}

Como podemos ver, en la línea 4 se ejecutan dos instrucciones, y finalmente el printf imprime por pantalla el valor 100. Pues esta extraña estructura no es más que una extensión de GCC (sí, el código de Linux no es, por lo general, portable a otros compiladores), llamada Statement Expression

Básicamente, permite ejecutar varias expresiones como si fuesen una sola. La última de la lista, que deberá terminar en un punto y coma, será el valor que devolverá la expresión.

En el ejemplo anterior, podemos ver como inicializamos una variable llamada i, y a continuación le sumamos a su valor (que es 0), el número 100. El resultado de esta operación es la que se devolverá al entero num. Es decir, que valdrá 100.

Pues análogamente, nuestra macro container_of contiene dos instrucciones con este formato, de tal manera que en la primera instrucción creamos una variable, y en la segunda operamos con ella, devolviendo como valor de la expresión el resultado de esta operación.

Pero antes de ver que operación se hace concretamente sigamos viendo con calma el código de la macro, en concreto podemos ver como se hace uso de otras dos funciones: typeof y offsetof.

La primera, typeof, no tiene mucho misterio, es otra extensión de GCC que en base a una variable, nos devuelve el tipo del que es. De esta manera podremos crear una variable del mismo tipo que otra, aunque no sepamos a priori de que tipo es la primera.

La segunda, offsetof, es una macro definida en el estándar ANSI C, pero que el kernel redeclara. Esto es debido a que esta macro realiza operaciones que no están aseguradas por el estándar de C, si no que el resultado puede variar de un compilador a otro.

Por ello, la mayor parte de los compiladores definen una función (por lo general llamada __builtin_offsetof). Linux simplemente comprueba si tal función existe; y en caso afirmativo, la usa sobre la predeterminada.

Lo que hace esta macro es devolver el offset (la distancia) que separa un campo de un struct, del inicio del mismo.

El código suele ser parecido al siguiente:

#define offsetof(st, m) \
     ((size_t) ( (char *)&((st *)(0))->m - (char *)0 ))

Esta macro realiza las siguientes operaciones:

  1. Castea el elemento 0 (NULL), a un puntero del tipo de estructura requerido, y a continuación accede al elemento especificado. Por último, obtiene la dirección. Es decir, devuelve el número de bytes que hay entre el inicio de la estructura (que está en la posición 0 en este caso), y el elemento que queremos devolver.
  2. A continuación, hace lo propio con el valor 0.
  3. Castea ambos elementos a punteros a carácter. Esto es debido a que el estándar de C asegura que un carácter ocupa 1 Byte.
  4. Por último, resta ambos valores, obteniendo el offset del campo que queremos (el número de bytes que lo separa del inicio de la estructura).

Con estas aclaraciones ya estamos listos para entender que hace la macro container_of. Vamos a volver a poner el código para tenerlo más cerquita.

#define container_of(ptr, type, member) ({          \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})

Como vemos, concatena dos expresiones en una.

  • La primera crea un puntero a una variable (llamada __mptr) de la estructura interna, list_head en nuestro ejemplo. Para ello, accede al miembro (lista en nuestro caso), y a continuación usa typeof para crear una nueva variable de este tipo. A continuación la inicializa con el valor del primer parámetro, que recordad, en el caso de las listas circulares, es el elemento sobre el que estamos iterando.

    Es decir, si en cierto momento de la ejecución de nuestro código anterior llamamos a la macro container_of(&nodo1, nodo, lista) pasándole como primer parámetro la dirección del nodo1, la primera línea lo que hará será crear una variable de tipo list_head, que apunte al elemento lista de ese nodo1. Esa variable, a grandes rasgos, guarda la dirección de memoria donde está el elemento list_head de nodo1 (un puntero no es más que una dirección, un numerito).

  • La segunda, obtiene el offset del campo list_head en nuestra estructura (con la macro offsetof tal como explicamos anteriormente), y a continuación, le resta este valor a la dirección de la variable creada anteriormente. Por último, castea este valor a un puntero a nuestro tipo de estructura.

Y el valor devuelto es el resultado de esta última operación, que no es más que la dirección de memoria donde empieza nuestra estructura nodo.

Es decir, que, poniendo números concretos, la primera línea de esta macro devuelve la dirección donde está la estructura contenida (la 0x200 por ejemplo). Y la segunda, obtiene el offset de esta estructura contenida, sobre la exterior (un offset de 0x4 bytes por ejemplo, que es lo que suele ocupar un int).

|filename|images/0004-listas-circulares-linux/struct.png

Para terminar, si queremos acceder a la estructura exterior, no tendremos más que restar 0x4 a 0x200, dando 0x1FC, que es la dirección de memoria donde está la estructura exterior.

Y eso es todo... como dije al principio, auténtica magia :)