STL, alocador, sua memória compartilhada e seus recursos



A memória compartilhada é a maneira mais rápida de trocar dados entre processos. Mas, ao contrário dos mecanismos de streaming (canais, sockets de todas as faixas, filas de arquivos ...), aqui o programador tem total liberdade de ação, como resultado, ele escreve quem é o que deseja.



Assim, o autor uma vez se perguntou e se ... se houver uma degeneração dos endereços de segmentos de memória compartilhada em diferentes processos. Isso é realmente o que acontece quando um processo de memória compartilhada bifurca, mas e os diferentes processos? Além disso, nem todos os sistemas possuem um fork.



Parece que os endereços coincidem e daí? No mínimo, você pode usar indicadores absolutos e isso evita muitas dores de cabeça. Será possível trabalhar com strings C ++ e contêineres construídos a partir de memória compartilhada.



Um excelente exemplo, aliás. Não que o autor realmente amasse STL, mas esta é uma oportunidade de demonstrar um teste compacto e compreensível para o desempenho da técnica proposta. Uma técnica que permite (ao que parece) simplificar e acelerar significativamente a comunicação entre processos. Se funciona e como você deve pagar, entenderemos melhor.



Introdução



A ideia de memória compartilhada é simples e elegante - já que cada processo opera em seu próprio espaço de endereço virtual, que é projetado no físico de todo o sistema, então por que não permitir que dois segmentos de processos diferentes olhem para a mesma área de memória física.



E com a proliferação de sistemas operacionais de 64 bits e o uso onipresente de cache coerente , a ideia de memória compartilhada ganhou um segundo fôlego. Agora não é apenas um buffer cíclico - uma implementação DIY de um “cano”, mas um verdadeiro “transfuncionador contínuo” - um dispositivo extremamente misterioso e poderoso, além disso, apenas seu mistério é igual ao seu poder.



Vejamos alguns exemplos de uso.



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





    .1 PostgreSQL ()


De um modo geral, o que gostaríamos de ver a memória compartilhada ideal? Esta é uma resposta fácil - desejamos que os objetos contidos nela possam ser usados ​​como se fossem objetos compartilhados entre threads do mesmo processo. Sim, você precisa de sincronização (e você precisa de qualquer maneira), mas caso contrário, basta pegá-la e usá-la! Talvez ... isso possa ser arranjado.



Uma prova de conceito requer uma tarefa mínima significativa :



  • existe um análogo de std :: map <std :: string, std :: string> localizado na memória compartilhada
  • temos N processos que adicionam / alteram valores de forma assíncrona com um prefixo correspondente ao número do processo (ex: key_1_ ... para o processo número 1)
  • como resultado, podemos controlar o resultado final


Vamos começar com a coisa mais simples - como temos std :: string e std :: map , precisamos de um alocador STL especial.



Alocador STL



Suponha que existam funções xalloc / xfree para trabalhar com memória compartilhada como análogos de malloc / free . Nesse caso, o alocador se parece com isto:



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));
	}
};


Isso é o suficiente para ligar std :: map & std :: string nele




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 lidar com as funções xalloc / xfree declaradas , que funcionam com o alocador no topo da memória compartilhada, vale a pena entender a própria memória compartilhada.



Memoria compartilhada



Threads diferentes do mesmo processo estão no mesmo espaço de endereço, o que significa que cada ponteiro não thread_local em qualquer thread olha para o mesmo lugar. Com a memória compartilhada, é necessário um esforço extra para atingir esse efeito.



janelas



  • Vamos criar um mapeamento de arquivo para memória. A memória compartilhada, como a memória comum, é coberta pelo mecanismo de paginação, aqui, entre outras coisas, é determinado se usaremos paginação compartilhada ou alocaremos um arquivo especial para isso.



    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


    O prefixo do nome do arquivo “Local \\” significa que o objeto será criado no namespace local da sessão.
  • Para ingressar em um mapeamento já criado por outro processo, use



    HANDLE hMapFile = OpenFileMapping(
    	FILE_MAP_ALL_ACCESS,      // read/write access
    	FALSE,                    // do not inherit the name
    	"Local\\SomeData");       // name of mapping object
  • Agora você precisa criar um segmento apontando para a tela acabada



    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);                    // 
    


    o tamanho do segmento 0 significa que o tamanho com o qual a exibição foi criada com o deslocamento será usado.



    O mais importante aqui é a dica. Se não for especificado (NULL), o sistema pegará o endereço a seu critério. Mas se o valor for diferente de zero, será feita uma tentativa de criar um segmento do tamanho desejado com o endereço desejado. É definindo seu valor como o mesmo em diferentes processos que alcançamos a degeneração dos endereços de memória compartilhada. No modo de 32 bits, encontrar um grande pedaço contíguo não alocado do espaço de endereço não é fácil, no modo de 64 bits não existe esse problema, você sempre pode encontrar algo adequado.


Linux



Tudo é basicamente o mesmo aqui.



  • Crie um objeto de memória compartilhada



      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.




Em relação à dica, quais são as restrições ao seu valor? Na verdade, existem diferentes tipos de restrições.



Primeiro , a arquitetura / hardware. Algumas palavras devem ser ditas aqui sobre como um endereço virtual se transforma em físico. Se houver uma falha no cache TLB , você terá que acessar uma estrutura em árvore chamada tabela de páginas . Por exemplo, em IA-32 é assim:





Fig. 2 caso de páginas de 4K, tomadas aqui A



entrada na árvore é o conteúdo do registro CR3, os índices nas páginas dos diferentes níveis são fragmentos do endereço virtual. Nesse caso, 32 bits se tornam 32 bits, tudo é justo.



No AMD64, a imagem parece um pouco diferente.





Fig. 3 AMD64, páginas de 4K, retiradas daqui



CR3 agora tem 40 bits significativos em vez dos 20 anteriormente, em uma árvore de 4 níveis de páginas, o endereço físico é limitado a 52 bits enquanto o endereço virtual é limitado a 48 bits.



E apenas na (começando com) a microarquitetura Ice Lake (Intel) é permitido usar 57 bits do endereço virtual (e ainda 52 físico) ao trabalhar com uma tabela de página de 5 níveis.



Até agora, falamos apenas sobre Intel / AMD. Para variar, na arquitetura Aarch64 , a tabela de páginas pode ser de 3 ou 4 níveis, permitindo o uso de 39 ou 48 bits no endereço virtual, respectivamente ( 1 ).



Em segundo lugar, restrições de software. A Microsoft, em particular, impõe (44 bits até 8.1 / Server12, 48 a partir de) aquelas em diferentes opções de SO com base, entre outras coisas, em considerações de marketing.



A propósito, 48 dígitos, isso é 65 mil vezes 4GB cada, talvez em tais espaços abertos haja sempre um canto onde você pode seguir sua dica.



Alocador de memória compartilhada



Em primeiro lugar. O alocador deve residir na memória compartilhada alocada, colocando todos os seus dados internos lá.



Em segundo lugar. Estamos falando de uma ferramenta de comunicação entre processos, quaisquer otimizações associadas ao uso de TLS são irrelevantes.



Em terceiro lugar. Como vários processos estão envolvidos, o próprio alocador pode durar muito tempo, reduzindo a fragmentação da memória externa é de particular importância .



Quarto. Chamar o sistema operacional para obter memória adicional não é permitido. Assim, dlmalloc , por exemplo, aloca pedaços relativamente grandes diretamente via mmap . Sim, pode ser desmamado aumentando o limiar, mas mesmo assim.



Quinto. Os recursos de sincronização padrão em processo não são adequados, seja global com uma sobrecarga correspondente ou algo localizado diretamente na memória compartilhada, como spinlocks, é necessário. Digamos graças ao cache coerente. Em posix, também existem semáforos compartilhados sem nome para este caso .



No total, levando em consideração todos os itens acima e também porque havia um alocador vivo pelo método dos gêmeos em mãos (gentilmente cedido por Alexander Artyushin, ligeiramente revisado), a escolha acabou sendo fácil.



Vamos deixar a descrição dos detalhes da implementação para tempos melhores, agora a interface pública é interessante:



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

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


O destruidor é trivial porque BuddyAllocator não pega nenhum recurso estranho.



Preparações finais



Como tudo está localizado na memória compartilhada, essa memória deve ter um cabeçalho. Para nosso teste, este cabeçalho se parece com isto:



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_ é escrito ao criar memória compartilhada para que todos que se ligam a ela pelo nome possam descobrir o endereço real (dica) e reconectar, se necessário
  • não é bom codificar as dimensões assim, mas é aceitável para testes
  • o (s) construtor (es) devem ser chamados pelo processo de criação da memória compartilhada, tem a seguinte aparência:



    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();
    
  • o processo de conexão com a memória compartilhada deixa tudo pronto
  • agora temos tudo o que precisamos para os testes, exceto as funções 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 podemos começar.



Experimentar



O teste em si é muito simples:



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 é o número do processo / thread, o processo que criou a memória compartilhada tem curid zero, mas isso não importa para o teste.

Qmap , LOCK / UNLOCK são diferentes para testes diferentes.



Vamos fazer alguns testes



  1. THR_MTX - um aplicativo multithread, a sincronização passa por std :: recursive_mutex ,

    qmap - global std :: map <std :: string, std :: string>
  2. THR_SPN é um aplicativo multithread, a sincronização passa por um 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 - std :: map global <std :: string, std :: string>
  3. PRC_SPN - vários processos em execução, a sincronização passa por um spinlock:



    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_
  4. PRC_MTX - vários processos em execução, a sincronização passa por um mutex nomeado .



    qmap - glob_header_t :: pglob _-> q_map_


Resultados (tipo de teste x número de processos / threads):

1 2 4 8 dezesseis
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 ''


O experimento foi realizado em um computador de processador dual (48 núcleos) com Xeon® Gold 5118 2,3 GHz, Windows Server 2016.



Total



  • Sim, é possível usar objetos / containers STL (alocados em memória compartilhada) de diferentes processos , desde que sejam projetados de forma adequada.
  • , , PRC_SPN THR_SPN. , BuddyAllocator malloc\free MS ( ).
  • . — + std::mutex . lock-free , .




A memória compartilhada é freqüentemente usada para transferir grandes fluxos de dados como uma espécie de "tubo" feito à mão. Esta é uma ótima ideia, embora você precise organizar uma sincronização cara entre os processos. Vimos que não é barato no teste PRC_MTX, quando mesmo sem competição, trabalhar dentro de um processo degradou significativamente o desempenho.



A explicação para o alto custo é simples, se std: :( ​​recursive_) mutex (seção crítica no Windows) pode funcionar como um spinlock, então um mutex nomeado é uma chamada de sistema, entrando no modo kernel com os custos correspondentes. Além disso, a perda de contexto de execução por um thread / processo é sempre muito cara.



Mas, uma vez que a sincronização de processos é inevitável, como podemos reduzir custos? A resposta foi inventada há muito tempo - buffering. Nem todo pacote é sincronizado, mas uma certa quantidade de dados - o buffer no qual esses dados são serializados. Se o buffer for visivelmente maior do que o tamanho do pacote, você terá que sincronizar com muito menos freqüência.



É conveniente misturar duas técnicas - dados em memória compartilhada, e apenas ponteiros relativos (do início da memória compartilhada) são enviados através do canal de dados interprocessos (ex: loop por localhost). Porque o ponteiro é geralmente menor que o pacote de dados, é possível economizar na sincronização.



E no caso em que diferentes processos tenham acesso à memória compartilhada no mesmo endereço virtual, você pode adicionar um pouco mais de desempenho.



  • não serializar dados para envio, não desserializar no recebimento
  • enviar ponteiros honestos para objetos criados na memória compartilhada através do fluxo
  • quando obtemos um objeto pronto (ponteiro), nós o usamos, então o deletamos por meio de uma deleção normal, toda a memória é automaticamente liberada. Isso nos impede de mexer com o buffer de anel.
  • você pode até enviar não um ponteiro, mas (o mínimo possível - um byte com o valor “você tem e-mail”) uma notificação sobre o fato de que há algo na fila


Finalmente



Faça e não faça para objetos construídos na memória compartilhada.



  1. Use RTTI . Por razões óbvias. O objeto std :: type_info existe fora da memória compartilhada e não está disponível nos processos.
  2. Use métodos virtuais. Pela mesma razão. As tabelas de funções virtuais e as próprias funções não estão disponíveis nos processos.
  3. Se falamos em STL, todos os arquivos executáveis ​​de processos que compartilham memória devem ser compilados por um compilador com as mesmas configurações, e o próprio STL deve ser o mesmo.


PS : obrigado a Alexander Artyushin e Dmitry Iptyshev (Dmitria) para obter ajuda na preparação deste artigo.



All Articles