STL, allocateur, sa mémoire partagée et ses fonctionnalités

La mémoire partagée est le moyen le plus rapide d'échanger des données entre les processus. Mais contrairement aux mécanismes de streaming (tuyaux, sockets de toutes bandes, files d'attente de fichiers ...), ici le programmeur a une totale liberté d'action, du coup, il écrit qui est ce qu'il veut.



Alors l'auteur s'est un jour demandé si ... s'il y avait une dégénérescence des adresses des segments de mémoire partagée dans différents processus. C'est en fait ce qui se passe lorsqu'un processus de mémoire partagée se fourche, mais qu'en est-il des différents processus? De plus, tous les systèmes n'ont pas de fourche.



Il semblerait que les adresses coïncident, et alors? À tout le moins, vous pouvez utiliser des pointeurs absolus et cela vous évite beaucoup de maux de tête. Il deviendra possible de travailler avec des chaînes C ++ et des conteneurs construits à partir de la mémoire partagée.



Un excellent exemple, au fait. Non pas que l'auteur ait vraiment aimé STL, mais c'est l'occasion de démontrer un test compact et compréhensible pour la performance de la technique proposée. Techniques qui permettent (comme on le voit) de simplifier et d'accélérer considérablement la communication interprocessus. Si cela fonctionne et comment vous devez payer, nous comprendrons plus loin.

introduction

L'idée de mémoire partagée est simple et élégante - puisque chaque processus opère dans son propre espace d'adressage virtuel, qui est projeté sur l'ensemble du système physique, alors pourquoi ne pas permettre à deux segments de processus différents de regarder la même zone de mémoire physique.



Et avec la prolifération des systèmes d'exploitation 64 bits et l'utilisation omniprésente d' un cache cohérent , l'idée de mémoire partagée a eu un second souffle. Désormais, il ne s'agit pas seulement d'un tampon cyclique - une implémentation DIY du «tuyau», mais d'un véritable «continuum transfunctioner» - un appareil extrêmement mystérieux et puissant, et seul son mystérieux est égal à sa puissance.



Regardons quelques exemples d'utilisation.

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

De manière générale, quel type de mémoire partagée idéale aimerions-nous voir? C'est une réponse facile - nous souhaitons que les objets qu'il contient puissent être utilisés comme s'il s'agissait d'objets partagés entre les threads du même processus. Oui, vous avez besoin d'une synchronisation (et vous en avez besoin de toute façon), mais sinon, il vous suffit de la prendre et de l'utiliser! Peut-être ... cela peut être arrangé.



Une preuve de concept nécessite une tâche minime et significative :

• il existe un analogue de std :: map <std :: string, std :: string> situé dans la mémoire partagée
• nous avons N processus qui ajoutent / modifient de manière asynchrone des valeurs avec un préfixe correspondant au numéro de processus (ex: key_1_ ... pour le processus numéro 1)
• en conséquence, nous pouvons contrôler le résultat final

Commençons par la chose la plus simple - puisque nous avons std :: string et std :: map , nous avons besoin d'un allocateur STL spécial.

Allocateur STL

Supposons qu'il existe des fonctions xalloc / xfree pour travailler avec la mémoire partagée comme des analogues de malloc / free . Dans ce cas, l'allocateur ressemble à ceci:

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

C'est suffisant pour accrocher std :: map & std :: string dessus

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

Avant de traiter les fonctions déclarées xalloc / xfree , qui fonctionnent avec l'allocateur en plus de la mémoire partagée, il vaut la peine de comprendre la mémoire partagée elle-même.

La memoire partagée

Différents threads du même processus sont dans le même espace d'adressage, ce qui signifie que chaque pointeur non- thread_local dans n'importe quel thread regarde au même endroit. Avec la mémoire partagée, il faut un effort supplémentaire pour obtenir cet effet.

les fenêtres

• Créons un fichier sur le mappage mémoire. La mémoire partagée, comme la mémoire ordinaire, est couverte par le mécanisme de pagination, ici, entre autres, il est déterminé si nous allons utiliser la pagination partagée ou allouer un fichier spécial à cela.
  
  
  
  

  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

  
  
  Le préfixe de nom de fichier «Local \\» signifie que l'objet sera créé dans l'espace de noms local de la session.
• Pour rejoindre un mappage déjà créé par un autre processus, utilisez
  
  
  
  

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

• Vous devez maintenant créer un segment pointant vers l'affichage terminé
  
  
  
  

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

  
  
  taille du segment 0 signifie que la taille avec laquelle l'affichage a été créé, en tenant compte du décalage, sera utilisée.
  
  
  
  La chose la plus importante ici est un indice. S'il n'est pas spécifié (NULL), le système sélectionnera l'adresse à sa discrétion. Mais si la valeur est différente de zéro, une tentative sera faite pour créer un segment de la taille souhaitée avec l'adresse souhaitée. C'est en définissant sa valeur comme la même dans différents processus que l'on parvient à la dégénérescence des adresses de mémoire partagée. En mode 32 bits, trouver un grand morceau d'espace d'adressage contigu non alloué n'est pas facile, en mode 64 bits, ce problème n'existe pas, vous pouvez toujours trouver quelque chose qui convient.

Linux

Tout est fondamentalement le même ici.

• Créer un objet de mémoire partagée
  
  
  
  

    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.

En ce qui concerne l'indice, quelles sont les restrictions sur sa valeur? En fait, il existe différents types de restrictions.



Tout d'abord , l'architecture / le matériel. Il convient de dire ici quelques mots sur la façon dont une adresse virtuelle se transforme en adresse physique. S'il y a un manque de cache TLB , vous devez accéder à une structure arborescente appelée la table des pages . Par exemple, dans IA-32, cela ressemble à ceci:





Fig.2 cas de pages 4K, pris ici L'



entrée dans l'arbre est le contenu du registre CR3, les index dans les pages de niveaux différents sont des fragments de l'adresse virtuelle. Dans ce cas, 32 bits deviennent 32 bits, tout est juste.



Dans AMD64, l'image est un peu différente.





Fig. 3 AMD64, pages 4K, tirées d'ici



CR3 a maintenant 40 bits significatifs au lieu de 20 auparavant, dans un arbre de 4 niveaux de pages, l'adresse physique est limitée à 52 bits tandis que l'adresse virtuelle est limitée à 48 bits.



Et seule (en commençant par) la microarchitecture d' Ice Lake (Intel) est-il autorisé à utiliser 57 bits de l'adresse virtuelle (et toujours 52 physiques) lorsque vous travaillez avec une table de pages à 5 niveaux.



Jusqu'à présent, nous n'avons parlé que d'Intel / AMD. Juste pour un changement, dans l'architecture Aarch64 , la table de pages peut être de 3 ou 4 niveaux, permettant l'utilisation de 39 ou 48 bits dans l'adresse virtuelle, respectivement ( 1 ).



Deuxièmement, restrictions logicielles. Microsoft, en particulier, impose (44 bits jusqu'à 8.1 / Server12, 48 à partir de) ceux sur différentes options d'OS en fonction, entre autres, de considérations marketing.



À propos, 48 ​​chiffres, soit 65 mille fois 4 Go, peut-être, dans de tels espaces ouverts, il y a toujours un coin où vous pouvez vous en tenir à votre indice.

Allocateur de mémoire partagée

Tout d'abord. L'allocateur doit vivre sur la mémoire partagée allouée, y plaçant toutes ses données internes.



Deuxièmement. Nous parlons d'un outil de communication interprocessus, les optimisations associées à l'utilisation de TLS sont sans intérêt.



Troisièmement. Étant donné que plusieurs processus sont impliqués, l'allocateur lui-même peut vivre très longtemps, la réduction de la fragmentation de la mémoire externe est d' une importance particulière .



Quatrième. L'appel du système d'exploitation pour la mémoire supplémentaire n'est pas autorisé. Ainsi, dlmalloc , par exemple, alloue des blocs relativement volumineux directement via mmap . Oui, il peut être sevré en élevant le seuil, mais néanmoins.



Cinquième. Les outils de synchronisation en cours de processus standard ne sont pas bons, soit global avec la surcharge appropriée, soit quelque chose situé directement dans la mémoire partagée, comme des verrous rotatifs, est nécessaire. Disons grâce au cache cohérent. En posix, il existe également des sémaphores partagés sans nom pour ce cas .



Au total, compte tenu de tout ce qui précède, et aussi parce qu'il y avait un allocateur en direct par la méthode des jumeaux (aimablement fourni par Alexander Artyushin, légèrement révisé), le choix s'est avéré facile.



Laissons la description des détails de l'implémentation jusqu'à des temps meilleurs, maintenant l'interface publique est intéressante:

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

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

Le destructeur est trivial car BuddyAllocator ne récupère aucune ressource superflue.

Préparatifs finaux

Puisque tout est situé dans la mémoire partagée, cette mémoire doit avoir un en-tête. Pour notre test, cet en-tête ressemble à ceci:

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_ est écrit lors de la création de la mémoire partagée afin que tous ceux qui s'y attachent par leur nom puissent trouver l'adresse réelle (indice) et se reconnecter si nécessaire
• ce n'est pas bon de coder en dur les dimensions comme ça, mais c'est acceptable pour les tests
• le ou les constructeurs doivent être appelés par le processus créant la mémoire partagée, cela ressemble à ceci:
  
  
  
  

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

• le processus de connexion à la mémoire partagée prépare tout
• maintenant nous avons tout ce dont nous avons besoin pour les tests sauf les fonctions 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);
  }
  

On dirait que nous pouvons commencer.

Expérience

Le test lui-même est très 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 est le numéro de processus / thread, le processus qui a créé la mémoire partagée n'a aucun curid, mais cela n'a pas d'importance pour le test.

Qmap , LOCK / UNLOCK sont différents pour différents tests.



Faisons quelques tests

1. THR_MTX - une application multithread, la synchronisation passe par std :: recursive_mutex ,
   
   qmap - global std :: map <std :: string, std :: string>
2. THR_SPN est une application multithread, la synchronisation passe par un verrou tournant:
   
   
   
   

   std::atomic_flag slock;
   ..
   while (slock.test_and_set(std::memory_order_acquire));  // acquire lock
   …
   slock.clear(std::memory_order_release);                 // release lock

   
   
   qmap - global std :: map <std :: string, std :: string>
3. PRC_SPN - plusieurs processus en cours d'exécution, la synchronisation passe par un verrou tournant:
   
   
   
   

   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 - plusieurs processus en cours d'exécution, la synchronisation passe par un mutex nommé .
   
   
   
   qmap - glob_header_t :: pglob _-> q_map_

Résultats (type de test vs nombre de processus / threads):



L'expérience a été réalisée sur un ordinateur biprocesseur (48 cœurs) avec Xeon® Gold 5118 2,3 GHz, Windows Server 2016.

Total

• Oui, utiliser les objets / conteneurs STL (placés en mémoire partagée) de différents processus peut être à condition qu'ils soient conçus de manière appropriée.
• , , PRC_SPN THR_SPN. , BuddyAllocator malloc\free MS ( ).
• . — + std::mutex . lock-free , .

La mémoire partagée est souvent utilisée pour transférer de gros flux de données comme une sorte de «tuyau» fait à la main. C'est une excellente idée même si vous devez organiser une synchronisation coûteuse entre les processus. Nous avons vu que ce n'est pas bon marché sur le test PRC_MTX, alors que même sans concurrence, travailler dans un processus a considérablement dégradé les performances.



L'explication du coût élevé est simple, si std: :( ​​recursive_) mutex (section critique sous Windows) peut fonctionner comme un spinlock, alors un mutex nommé est un appel système, entrant en mode noyau avec les coûts correspondants. De plus, la perte de contexte d'exécution par un thread / processus est toujours très coûteuse.



Mais comme la synchronisation des processus est inévitable, comment réduire les coûts? La réponse a longtemps été inventée: la mise en mémoire tampon. Tous les paquets ne sont pas synchronisés, mais une certaine quantité de données - le tampon dans lequel ces données sont sérialisées. Si le tampon est sensiblement plus grand que la taille du paquet, vous devez synchroniser beaucoup moins souvent.



Il est pratique de mélanger deux techniques - les données en mémoire partagée, et seuls les pointeurs relatifs (à partir du début de la mémoire partagée) sont envoyés à travers le canal de données interprocess (ex: boucle via localhost). Parce que le pointeur est généralement plus petit que le paquet de données, ce qui permet d'économiser sur la synchronisation.



Et dans le cas où la mémoire partagée est disponible pour différents processus à la même adresse virtuelle, vous pouvez ajouter un peu plus de performances.

• ne pas sérialiser les données pour l'envoi, ne pas désérialiser à la réception
• envoyer des pointeurs honnêtes vers des objets créés en mémoire partagée via le flux
• lorsque nous obtenons un objet prêt (pointeur), nous l'utilisons, puis nous le supprimons en utilisant une suppression régulière, toute la mémoire est automatiquement libérée. Cela nous évite de jouer avec le tampon en anneau.
• vous pouvez même envoyer pas de pointeur, mais (le minimum possible - un octet avec la valeur "vous avez du courrier") une notification sur le fait qu'il y a quelque chose dans la file d'attente

finalement

À faire et à ne pas faire pour les objets construits en mémoire partagée.

1. Utilisez RTTI . Pour des raisons évidentes. L'objet std :: type_info existe en dehors de la mémoire partagée et n'est pas disponible dans tous les processus.
2. Utilisez des méthodes virtuelles. Pour la même raison. Les tables de fonctions virtuelles et les fonctions elles-mêmes ne sont pas disponibles dans les processus.
3. Si nous parlons de STL, tous les fichiers exécutables des processus partageant la mémoire doivent être compilés par un compilateur avec les mêmes paramètres, et le STL lui-même doit être le même.

PS : merci à Alexander Artyushin et Dmitry Iptyshev (Dmitria) pour vous aider à préparer cet article.