👩🏿‍🎤 👨🏿‍🤝‍👨🏻 💃🏿 STL, asignador, su memoria compartida y sus características 🔮 👨‍🍳 🕑

La memoria compartida es la forma más rápida de intercambiar datos entre procesos. Pero a diferencia de los mecanismos de streaming (canalizaciones, sockets de todo tipo, colas de archivos ...), aquí el programador tiene total libertad de acción, como resultado, escribe quién es lo que quiere.

Entonces, el autor una vez se preguntó qué pasa si ... si hay una degeneración de las direcciones de los segmentos de memoria compartida en diferentes procesos. Esto es en realidad lo que sucede cuando un proceso de memoria compartida se bifurca, pero ¿qué pasa con los diferentes procesos? Además, no todos los sistemas tienen una bifurcación.

Parecería que las direcciones coincidieron, ¿y qué? Como mínimo, puede usar punteros absolutos y esto le ahorra muchos dolores de cabeza. Será posible trabajar con cadenas de C ++ y contenedores construidos a partir de memoria compartida.

Un excelente ejemplo, por cierto. No es que al autor le encantara STL, pero esta es una oportunidad para demostrar una prueba compacta y comprensible para el desempeño de la técnica propuesta. Técnicas que permiten (como se ve) simplificar y acelerar significativamente la comunicación entre procesos. Si funciona y cómo tiene que pagar, lo entenderemos más.

Introducción

La idea de la memoria compartida es simple y elegante, dado que cada proceso opera en su propio espacio de direcciones virtuales, que se proyecta en el sistema físico de todo el sistema, entonces, ¿por qué no permitir que dos segmentos de diferentes procesos miren la misma área de memoria física?

Y con la proliferación de sistemas operativos de 64 bits y el uso omnipresente de la caché coherente , la idea de la memoria compartida tuvo un segundo aire. Ahora no es solo un búfer cíclico, una implementación de bricolaje de una "tubería", sino un verdadero "transformador continuo", un dispositivo extremadamente misterioso y poderoso, además, solo su misterio es igual a su poder.

Veamos algunos ejemplos de uso.

“shared memory” MS SQL. (~10...15%)
Mysql Windows “shared memory”, .
Sqlite WAL-. , . (chroot).
PostgreSQL fork - . , .

.1 PostgreSQL ()

En términos generales, ¿qué nos gustaría ver la memoria compartida ideal? Esta es una respuesta fácil: deseamos que los objetos que contiene puedan usarse como si fueran objetos compartidos entre subprocesos del mismo proceso. Sí, necesitas sincronización (y la necesitas de todos modos), pero de lo contrario, ¡simplemente tómala y úsala! Quizás ... se pueda arreglar.

Una prueba de concepto requiere una tarea mínima y significativa :

hay un análogo de std :: map <std :: string, std :: string> ubicado en la memoria compartida
tenemos N procesos que agregan / cambian valores de forma asíncrona con un prefijo correspondiente al número de proceso (por ejemplo: key_1_ ... para el proceso número 1)
como resultado, podemos controlar el resultado final

Comencemos con lo más simple: dado que tenemos std :: string y std :: map , necesitamos un asignador STL especial.

Asignador STL

Supongamos que existen funciones xalloc / xfree para trabajar con memoria compartida como análogos de malloc / free . En este caso, el asignador se ve así:

template <typename T>
class stl_buddy_alloc
{
public:
	typedef T                 value_type;
	typedef value_type*       pointer;
	typedef value_type&       reference;
	typedef const value_type* const_pointer;
	typedef const value_type& const_reference;
	typedef ptrdiff_t         difference_type;
	typedef size_t            size_type;
public:
	stl_buddy_alloc() throw()
	{	// construct default allocator (do nothing)
	}
	stl_buddy_alloc(const stl_buddy_alloc<T> &) throw()
	{	// construct by copying (do nothing)
	}
	template<class _Other>
	stl_buddy_alloc(const stl_buddy_alloc<_Other> &) throw()
	{	// construct from a related allocator (do nothing)
	}

	void deallocate(pointer _Ptr, size_type)
	{	// deallocate object at _Ptr, ignore size
		xfree(_Ptr);
	}
	pointer allocate(size_type _Count)
	{	// allocate array of _Count elements
		return (pointer)xalloc(sizeof(T) * _Count);
	}
	pointer allocate(size_type _Count, const void *)
	{	// allocate array of _Count elements, ignore hint
		return (allocate(_Count));
	}
};

Esto es suficiente para conectar std :: map & std :: string en él


template <typename _Kty, typename _Ty>
class q_map : 
    public std::map<
        _Kty, 
        _Ty, 
        std::less<_Kty>, 
        stl_buddy_alloc<std::pair<const _Kty, _Ty> > 
    >
{ };

typedef std::basic_string<
        char, 
        std::char_traits<char>, 
        stl_buddy_alloc<char> > q_string

Antes de tratar con las funciones xalloc / xfree declaradas , que funcionan con el asignador en la parte superior de la memoria compartida, vale la pena comprender la memoria compartida en sí.

Memoria compartida

Diferentes subprocesos del mismo proceso están en el mismo espacio de direcciones, lo que significa que cada puntero no thread_local en cualquier subproceso mira en el mismo lugar. Con la memoria compartida, se necesita un esfuerzo adicional para lograr este efecto.

Ventanas

Creemos un archivo a la asignación de memoria. La memoria compartida, como la memoria ordinaria, está cubierta por el mecanismo de paginación, aquí, entre otras cosas, se determina si usaremos la paginación compartida o asignaremos un archivo especial para esto.
```
HANDLE hMapFile = CreateFileMapping(
	INVALID_HANDLE_VALUE,     // use paging file
	NULL,                     // default security
	PAGE_READWRITE,           // read/write access
	(alloc_size >> 32)        // maximum object size (high-order DWORD)
	(alloc_size & 0xffffffff),// maximum object size (low-order DWORD)
	"Local\\SomeData");       // name of mapping object
```
El prefijo de nombre de archivo “Local \\” significa que el objeto se creará en el espacio de nombres local de la sesión.

Para unirse a un mapeo ya creado por otro proceso, use

HANDLE hMapFile = OpenFileMapping(
	FILE_MAP_ALL_ACCESS,      // read/write access
	FALSE,                    // do not inherit the name
	"Local\\SomeData");       // name of mapping object

Ahora necesita crear un segmento que apunte a la pantalla terminada
```
void *hint = (void *)0x200000000000ll;
unsigned char *shared_ptr = (unsigned char*)MapViewOfFileEx(
	hMapFile,                 // handle to map object
	FILE_MAP_ALL_ACCESS,      // read/write permission
	0,                        // offset in map object (high-order DWORD)
	0,                        // offset in map object (low-order DWORD)
	0,                        // segment size,
	hint);                    // 
```
tamaño de segmento 0 significa que se utilizará el tamaño con el que se creó la pantalla con el desplazamiento.

Lo más importante aquí es la pista. Si no se especifica (NULO), el sistema seleccionará la dirección a su discreción. Pero si el valor es distinto de cero, se intentará crear un segmento del tamaño deseado con la dirección deseada. Es definiendo su valor como el mismo en diferentes procesos que logramos la degeneración de direcciones de memoria compartida. En el modo de 32 bits, no es fácil encontrar un gran trozo de espacio de direcciones contiguo sin asignar, en el modo de 64 bits no existe tal problema, siempre puede encontrar algo adecuado.

Linux

Todo es básicamente igual aquí.

Crea un objeto de memoria compartida

  int fd = shm_open(
                 “/SomeData”,               //  ,   /
                 O_CREAT | O_EXCL | O_RDWR, // flags,  open
                 S_IRUSR | S_IWUSR);        // mode,  open

  ftruncate(fd, alloc_size);

ftruncate . shm_open /dev/shm/. shmget\shmat SysV, ftok (inode ).

```
int fd = shm_open(“/SomeData”, O_RDWR, 0);
```

  void *hint = (void *)0x200000000000ll;
  unsigned char *shared_ptr = (unsigned char*) = mmap(
                   hint,                      // 
                   alloc_size,                // segment size,
                   PROT_READ | PROT_WRITE,    // protection flags
                   MAP_SHARED,                // sharing flags
                   fd,                        // handle to map object
                   0);                        // offset

hint.

Con respecto a la pista, ¿cuáles son las restricciones sobre su valor? De hecho, existen diferentes tipos de restricciones.

Primero , la arquitectura / hardware. Aquí se deben decir algunas palabras sobre cómo una dirección virtual se convierte en una física. Si hay un error de caché de TLB , debe acceder a una estructura de árbol llamada tabla de páginas . Por ejemplo, en IA-32 se ve así:

Fig.2 caso de páginas 4K, tomado aquí La

entrada al árbol es el contenido del registro CR3, los índices en las páginas de diferentes niveles son fragmentos de la dirección virtual. En este caso, 32 bits se convierten en 32 bits, todo es justo.

En AMD64, la imagen se ve un poco diferente.

Fig.3 AMD64, páginas 4K, tomadas de aquí

CR3 ahora tiene 40 bits significativos en lugar de 20 anteriormente, en un árbol de 4 niveles de páginas, la dirección física está limitada a 52 bits mientras que la dirección virtual está limitada a 48 bits.

Y solo en (comenzando con) la microarquitectura de Ice Lake (Intel) se permite usar 57 bits de la dirección virtual (y aún 52 físicos) cuando se trabaja con una tabla de páginas de 5 niveles.

Hasta ahora, solo hemos hablado de Intel / AMD. Solo para variar, en la arquitectura Aarch64 , la tabla de páginas puede ser de 3 o 4 niveles, permitiendo el uso de 39 o 48 bits en la dirección virtual, respectivamente ( 1 ).

En segundo lugar, restricciones de software. Microsoft, en particular, impone (44 bits hasta 8.1 / Server12, 48 a partir de) aquellos en diferentes opciones de sistema operativo basándose, entre otras cosas, en consideraciones de marketing.

Por cierto, 48 dígitos, esto es 65 mil veces 4GB cada uno, quizás en esos espacios abiertos siempre hay un rincón donde puedes seguir tu pista.

Asignador de memoria compartida

Ante todo. El asignador debe vivir en la memoria compartida asignada, colocando todos sus datos internos allí.

En segundo lugar. Estamos hablando de una herramienta de comunicación entre procesos, cualquier optimización asociada con el uso de TLS es irrelevante.

En tercer lugar. Dado que hay varios procesos involucrados, el asignador en sí puede vivir durante mucho tiempo, por lo que reducir la fragmentación de la memoria externa es de particular importancia .

Cuarto. No se permite llamar al sistema operativo para obtener memoria adicional. Entonces, dlmalloc , por ejemplo, asigna fragmentos relativamente grandes directamente a través de mmap . Sí, se puede destetar elevando el umbral, pero no obstante.

Quinto. Las instalaciones estándar de sincronización en proceso no son adecuadas, ya sea global con una sobrecarga correspondiente o algo ubicado directamente en la memoria compartida, como los bloqueos giratorios. Digamos gracias al caché coherente. En posix también hay semáforos compartidos sin nombre para este caso .

En total, teniendo en cuenta todo lo anterior y también porque había un asignador en vivo por el método de los gemelos a mano (amablemente proporcionado por Alexander Artyushin, ligeramente revisado), la elección no fue difícil.

Dejemos la descripción de los detalles de la implementación para mejores tiempos, ahora la interfaz pública es interesante:

class BuddyAllocator {
public:
	BuddyAllocator(uint64_t maxCapacity, u_char * buf, uint64_t bufsize);
	~BuddyAllocator(){};

	void *allocBlock(uint64_t nbytes);
	void freeBlock(void *ptr);
...
};

El destructor es trivial porque BuddyAllocator no se apropia de recursos extraños.

Preparativos finales

Dado que todo está ubicado en la memoria compartida, esta memoria debe tener un encabezado. Para nuestra prueba, este encabezado se ve así:

struct glob_header_t {
	//     magic
	uint64_t magic_;
	// hint     
	const void *own_addr_;
	//  
	BuddyAllocator alloc_;
	// 
	std::atomic_flag lock_;
	//   
	q_map<q_string, q_string> q_map_;

	static const size_t alloc_shift = 0x01000000;
	static const size_t balloc_size = 0x10000000;
	static const size_t alloc_size = balloc_size + alloc_shift;
	static glob_header_t *pglob_;
};
static_assert (
    sizeof(glob_header_t) < glob_header_t::alloc_shift, 
    "glob_header_t size mismatch");

glob_header_t *glob_header_t::pglob_ = NULL;

own_addr_ se escribe al crear la memoria compartida para que todos los que se adjuntan a ella por su nombre puedan averiguar la dirección real (pista) y volver a conectarse si es necesario
no es bueno codificar las dimensiones de esta manera, pero es aceptable para las pruebas

el (los) constructor (es) deben ser llamados por el proceso que crea la memoria compartida, se ve así:

glob_header_t::pglob_ = (glob_header_t *)shared_ptr;

new (&glob_header_t::pglob_->alloc_)
        qz::BuddyAllocator(
                //  
                glob_header_t::balloc_size,
                //  
                shared_ptr + glob_header_t::alloc_shift,
                //   
                glob_header_t::alloc_size - glob_header_t::alloc_shift;

new (&glob_header_t::pglob_->q_map_) 
                q_map<q_string, q_string>();

glob_header_t::pglob_->lock_.clear();

el proceso de conexión a la memoria compartida prepara todo
ahora tenemos todo lo que necesitamos para las pruebas excepto las funciones xalloc / xfree
```
void *xalloc(size_t size)
{
	return glob_header_t::pglob_->alloc_.allocBlock(size);
}
void xfree(void* ptr)
{
	glob_header_t::pglob_->alloc_.freeBlock(ptr);
}
```

Parece que puedes empezar.

Experimentar

La prueba en sí es muy simple:

for (int i = 0; i < 100000000; i++)
{
        char buf1[64];
        sprintf(buf1, "key_%d_%d", curid, (i % 100) + 1);
        char buf2[64];
        sprintf(buf2, "val_%d", i + 1);

        LOCK();

        qmap.erase(buf1); //   
        qmap[buf1] = buf2;

        UNLOCK();
}

Curid es el número de proceso / hilo, el proceso que creó la memoria compartida tiene cero curid, pero no importa para la prueba.

Qmap , LOCK / UNLOCK son diferentes para diferentes pruebas.

Hagamos algunas pruebas

THR_MTX - una aplicación multiproceso, la sincronización pasa por std :: recursive_mutex ,

qmap - global std :: map <std :: string, std :: string>
THR_SPN es una aplicación multiproceso, la sincronización pasa por un spinlock:
```
std::atomic_flag slock;
..
while (slock.test_and_set(std::memory_order_acquire));  // acquire lock
…
slock.clear(std::memory_order_release);                 // release lock
```
qmap - estándar global :: mapa <estándar :: cadena, estándar :: cadena>

PRC_SPN : varios procesos en ejecución, la sincronización pasa por un bloqueo de giro :

while (glob_header_t::pglob_->lock_.test_and_set(              // acquire lock
        std::memory_order_acquire));                          
…
glob_header_t::pglob_->lock_.clear(std::memory_order_release); // release lock

qmap - glob_header_t :: pglob _-> q_map_

PRC_MTX : varios procesos en ejecución, la sincronización pasa por un mutex con nombre .

qmap - glob_header_t :: pglob _-> q_map_

Resultados (tipo de prueba frente a número de procesos / subprocesos):

	1	2	4	8	dieciséis
THR_MTX	1'56 ''	5'41 ''	7'53 ''	51'38 ''	185'49
THR_SPN	1'26 ''	7'38 ''	25'30 ''	103'29 ''	347'04 ''
PRC_SPN	1'24 ''	7'27 ''	24'02 ''	92'34 ''	322'41 ''
PRC_MTX	4'55 ''	13'01 ''	78'14 ''	133'25 ''	357'21 ''

El experimento se llevó a cabo en una computadora de doble procesador (48 núcleos) con Xeon® Gold 5118 2.3GHz, Windows Server 2016.

Total

Sí, es posible utilizar objetos / contenedores STL (asignados en memoria compartida) de diferentes procesos , siempre que estén diseñados adecuadamente.
, , PRC_SPN THR_SPN. , BuddyAllocator malloc\free MS ( ).
. — + std::mutex . lock-free , .

La memoria compartida se utiliza a menudo para transferir grandes flujos de datos como una especie de "tubería" hecha a mano. Esta es una gran idea, aunque necesita organizar una costosa sincronización entre procesos. Vimos que no es barato en la prueba PRC_MTX, cuando incluso sin competencia, trabajar dentro de un proceso degradó significativamente el rendimiento.

La explicación del alto costo es simple, si std: :( recursive_) mutex (sección crítica bajo Windows) puede funcionar como un spinlock, entonces un mutex con nombre es una llamada al sistema, entrando en modo kernel con los costos correspondientes. Además, la pérdida de contexto de ejecución por un hilo / proceso siempre es muy costosa.

Pero dado que la sincronización de procesos es inevitable, ¿cómo podemos reducir los costos? La respuesta se ha inventado durante mucho tiempo: el almacenamiento en búfer. No todos los paquetes están sincronizados, sino una cierta cantidad de datos: el búfer en el que se serializan estos datos. Si el búfer es notablemente más grande que el tamaño del paquete, entonces debe sincronizar con mucha menos frecuencia.

Es conveniente mezclar dos técnicas: datos en la memoria compartida, y solo los punteros relativos (desde el comienzo de la memoria compartida) se envían a través del canal de datos entre procesos (por ejemplo: bucle a través de localhost). Porque el puntero suele ser más pequeño que el paquete de datos, ahorrando en sincronización.

Y en el caso de que diferentes procesos tengan acceso a la memoria compartida en la misma dirección virtual, puede agregar un poco más de rendimiento.

no serialice los datos para enviarlos, no los deserialice al recibirlos
enviar sugerencias honestas a los objetos creados en la memoria compartida a través de la transmisión
cuando obtenemos un objeto listo (puntero), lo usamos, luego lo eliminamos mediante una eliminación regular, toda la memoria se libera automáticamente. Esto nos evita jugar con el búfer de anillo.
incluso puede enviar no un puntero, sino (el mínimo posible - un byte con el valor "tienes correo") una notificación del hecho de que hay algo en la cola

Finalmente

Qué hacer y qué no hacer con los objetos construidos en la memoria compartida.

Utilice RTTI . Por obvias razones. El objeto std :: type_info existe fuera de la memoria compartida y no está disponible en todos los procesos.
Utilice métodos virtuales. Por la misma razón. Las tablas de funciones virtuales y las funciones mismas no están disponibles en todos los procesos.
Si hablamos de STL, todos los archivos ejecutables de procesos que comparten memoria deben ser compilados por el mismo compilador con la misma configuración, y el STL en sí debe ser el mismo.

PD : gracias a Alexander Artyushin y Dmitry Iptyshev (Dmitria) para obtener ayuda en la preparación de este artículo.

STL, asignador, su memoria compartida y sus características