neologix a écrit 346 commentaires

Ce n'est pas pareil.
Le problème qu'il décrit est un genre de livelock. Mais en pratique cela ne se produit pas, parce que statistiquement, au bout d'un certain temps, tu n'auras qu'un thread actif au sein de la section critique (qui est censée être courte), ou du moins tu n'auras pas de thread en train de modifier les donnés protégées.
Dans le cas que tu décris, effectivement, en cas de forte contention, en théorie tu peux avoir un problème de "starvation", où un thread se fait griller par ses petits copains ad vitam.
Mais c'est une question d'implémentation: par exemple, POSIX garantit ceci (man pthread_mutex_unlock):
"""If there are threads blocked on the mutex object referenced by mutex when pthread_mutex_unlock() is called, resulting in the mutex becoming available, the scheduling policy is used to determine which thread shall acquire the mutex."""

Le point important est "the scheduling policy" : c'est l'ordonnanceur qui choisit le thread qui va acquérir le mutex, et si un threads reste en attente trop longtemps sur un mutex, sa priorité finit par être plus importante que celle de ses amis.

Au passage, il y a un mécanisme de synchronisation utilisé par le noyau Linux qui se rapproche de STM : les seqlocks (il y a un lock utilisé pour les writers, mais pas de locks pour les readers).

Enfin, l'implémentation "STM" pour CPython d'Armin Rigo n'est pas vraiment (du tout) une forme de STM : elle se contente de garder le GIL locké (donc pas de concurrence, pas de notion de commit/rollback, c'est en fait un gros verrou global "implicite"). En plus elle présente pas mal de risques de deadlocks...

En effet, je pense que les moinsseurs n'ont pas compris ta suggestion...
J'avais pensé à un truc dans le genre, basé sur des TLS.
En en fait il s'avère que d'autres y ont pensé, et même écrit :
http://www.iecc.com/gclist/GC-harder.html http://www.nntpnews.info/threads/4513004-Lock-free-reference-counting http://guillaume.segu.in/papers/ns3-multithreading.pdf et http://sysrun.haifa.il.ibm.com/hrl/ISMM2009/present/wild_2.pdf

Par contre, il y a quelques problèmes a prendre en compte :
- avec un refcount par thread, il faudrait au moins deux niveaux d'indirection supplémentaires (typiquement chaque thread aurait une table contenant la liste des refcounts de chaque objet, l'adresse de cette table étant retrouvée par TLS)
- cette indirection augmenterait significativement le nombre d'instructions nécessaires par incref/decref (le lookup TLS doit être rapide, mais derrière il faut retrouver le refcount correspondant à l'objet)
- surtout, tu perds énormément en localité de référence : dans le cas classique, ton refcount est très probablement déjà en cache puisque tu viens de toucher à l'objet (c'est l'un des intérêts du comptage de référence par rapport au rammase-miette, qui lui s'amuse souvent à suivre des objets qui ne sont pas en cache et à te dégager ceux qui y sont déjà). Quelqu'un avait suggéré il y a quelque temps de sortir le refcount des objets pour une autre raison (en gros, comme le refcount peut-être incrémenté même lorsque l'objet est lu, après un fork() tu perds vite l'économie de mémoire apportée par le COW pour des gros datasets, voir http://mail.python.org/pipermail/python-dev/2011-May/111562.html), la dégradation de performance était non-négligeable, et c'était juste avec un seul thread
- lorsque ton thread-local refcount tombe à 0, il vérifier que tous les autres thread-local refcounts pour cet objet sont à 0, et ceci de façon atomique
- enfin, j'ai comme dans l'idée que dans 90% des cas, le refcount par thread varie entre 0 et 1, du coup on ne gagnerait rien (en fait on perdrait même)

Mais je vais essayer de creuser ça quand j'aurai un peu de temps, ça pourrait être marrant...

Oui enfin il y a quand même un problème avec le comptage de référence naïf (je dis "naïf" parce que je n'ai pas cherché s'il existait des variantes qui ne posent pas ce problème) : dans le cadre d'un programme multi-thread, tu es obligé d'utiliser des opérations atomiques pour incrémenter/décrémenter ton compteur. Et ça, en terme de performances, c'est la mort (instructions en elles-mêmes, sans parler du cache line bouncing).
C'est l'une des principales raisons pour lesquelles CPython a toujours le GIL...

On a aussi...
http://bugs.python.org/issue?%40columns=id%2Cactivity%2Ctitle%2Ccreator%2Cassignee%2Cstatus%2Ctype&%40sort=-activity&%40filter=status&%40action=searchid&ignore=file%3Acontent&%40search_text=HP-UX&submit=search&status=-1%2C1%2C3

Marrant...
J'ai créé un bug report sur le tracker Python, il y a un peu plus d'un mois.
Mais on n'arrive pas à se mettre d'accord sur la façon de traiter ce problème:
- remplacer sys.platform par 'linux' sur Linux (actuellement on se contente de renvoyer MACHDEP)
- utiliser sys.platform.starswith('linux')
- utiliser platform.system()
- ajouter un nouveau sys.system

Du coup, ça n'avance pas vraiment, même si on est plusieurs développeurs à vouloir garder la sémantique actuelle 'linux3'.
Donc si vous utilisez sys.platform, je vous conseille de changer pour platform.system() ou os.uname()[0] (uniquement sur Unix), voire sys.platform.startswith('linux').
C'est tout con, mais c'est déjà le deuxième bug lié à ce problème qu'on voit (https://bugs.gentoo.org/show_bug.cgi?id=374579).

Bon, je préfère avoir des "bugs" comme ça sous Linux plutôt que les bugs qu'on se paie avec des OS bien pourris comme AIX et OS-X, parce que là c'est moins marrant...

Est-ce normal ?

Non. Linux ne l'autorise pas.

N'est-ce pas là une faille de sécurité ?

Il faut déjà que ton serveur ait activé SO_REUSEADDR de son côté (bon, c'est courant).
Mais c'est aussi pour cela qu'on a inventé les ports réservés (<1024).
Là je suppose que ton programme tourne en administrateur, j'espère que tu es sûr de ton code...

Un peu plus de détails, avec un petit script pour expérimenter :

"""
import socket
import sys
import optparse

parser = optparse.OptionParser()
parser.add_option('-P', dest='protocol', default='tcp')
parser.add_option('-p', dest='port', type='int', default=4242)
parser.add_option('-r', dest='reuse', action='store_true', default=False)
options, args = parser.parse_args()

if options.protocol == 'udp':
s = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
else:
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)

if options.reuse:
s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)

try:
s.bind(('', options.port))
if options.protocol == 'tcp':
s.listen(3)
raw_input()
finally:
s.close()
"""

En gros :
- sans SO_REUSEADDR, tu te prends un EADDRINUSE en TCP/UDP si tu te bindes au même couple (interface, port)
- avec SO_REUSEADDR sur chaque socket, en UDP tu peux te binder plusieurs fois au même (interface, port), mais le comportement n'est déterministe que si tu reçois du broadcast/multicast (tous les socket srecoivent les données), en unicast il n'y a aucune garantie, généralement le premier socket va tout recevoir, et les autres rien
- en TCP, avec SO_REUSEADDR sur chaque socket, tu peux te binder plusieurs fois seulement si l'autre socket n'est pas en LISTEN (puisque plusieurs bind sur le même port alors qu'une communication unicast est établie n'a pas de sens)
Windows semble autoriser un bind multiple en TCP même si l'autre socket est en LISTEN, enfin je n'ai pas de Windows sous la main, et si c'est le cas ce n'est absolument pas normal/standard.
Enfin, l'intérêt principal de SO_REUSEADDR c'est de pourvoir réutiliser une adresse en TIME-WAIT.

J'ai laissé de côté SO_REUSEPORT parce qu'il n'est plus utilisé sous Linux:

/usr/include/asm-generic/socket.h:#define SO_REUSEADDR 2
/usr/include/asm-generic/socket.h:/* To add :#define SO_REUSEPORT 15 */

http://www.unixguide.net/network/socketfaq/4.11.shtml

et

http://msdn.microsoft.com/en-us/library/ms740621(v=vs.85).aspx

Y a-t-il vraiment des compilateurs qui ne procèdent pas ainsi

Au moins cPython :
http://wiki.python.org/moin/ASTBasedOptimization

Je vais même aller plus loin : les environnements de bureau modernes encouragent l'utilisation de pilotes graphiques non-libres, à cause des effets à la con qu'ils imposent.
Par ailleurs, tout le monde ne s'amuse pas à racheter un PC tous les 3 ans, et c'est vraiment gonflant de ne pas pouvoir faire tourner correctement GNOME/KDE/XFCE/... sans avoir une bête de course.
Moinssez-moi.

OK, pour le point 3, je me suis trompé, c'est bien le nombre de pages physiques mappées (par zone), pas committées, donc cela n'a pas d'influence.

1) oui bien sûr sans overcommit mmap ou malloc va retourner une erreur (enfin dans la majorité des cas). L'intérêt de split-stack sans overcommit c'est que tu pourras créer plus de threads, et gâcher moins de mémoire. Je suis d'accord que le comportement n'est pas déterministe, mais je ne pense pas que les cas ciblés soient le temps-réel ou les systèmes embarqués.
Il y a plein de cas où l'overcommitting est désactivé : par exemple tu évoques les problèmes de déterminisme, or l'OOM est hautement imprévisible. Sinon, il est souvent conseillé de le désactiver avec certaines bases de données, http://www.network-theory.co.uk/docs/postgresql/vol3/LinuxMemoryOvercommit.html. Enfin, il y a plein de systèmes qui ne supportent pas l'overcommitting (gcc ne compile pas que du code destiné à tourner sous Linux avec un MMU).

2) tout à fait d'accord, mais la probabilité d'occurrence de débordement de pile est plus faible

3) je me suis posé la même question. Il faudra que je vérifie le code, mais j'ai bien l'impression que c'est le nombre de pages mappées qui est pris en compte dans la politique de pagination. A creuse.

En plus l'utilisation en contexte embarqué des split-stack est peu recommandable pour les tâches RT. Dans le cas classique on peut pre-faulter la stack, ici on aura des mmap automatique en cours de vie du programme.

Tu as l'air d'avoir une approche systèmes embarqués temps-réel, mais je ne suis pas sûr que splitstacks s'adresse à ce type de cas.

Linux étant lasy (COW), la stack est réellement alloué qu'a l'utilisation et chaque thread peut alloué 8MB sans consommer de la RAM physique. Du coup le seul avantage que je vois c'est pour les système qui ont un espace d’adressage limité (32 bits). Et quand je lit ce que cette option coûte (chaque fonction doit vérifier s'il faut allouer une nouvelle pile), je vois pas l’intérêt du truc.

1) Tout le monde n'utilise pas l'overcommiting : dans ce cas, l'OOM killer va se déclencher au moment de la création des threads, et pas de leur utilisation de la stack, même s'il reste encore plein de mémoire physique disponible. Si tu utilises par exemple un pool de threads fixe, c'est une grosse limitation.
2) Le risque de stack overflow est moindre, puisque la stack est augmentée à la demande.
3) Même avec l'overcommiting, avoir un mémoire virtuelle importante (Committed_AS) a un impact sur les performances : le "page reclaiming code" (j'ai horreur du franglais, mais c'est plus clair) prend en compte la quantité de pages mappées pour savoir s'il doit swapper des process (swap_tendency prend en compte les valeurs mapped ratio et swappinnes). Donc rien qu'avoir un bazillion de threads qui ne font rien va augmenter la tendance du noyau à diminuer le page cache ou swapper.

D'abord, pour être sûr de ne pas avoir de problème d'incompatibilité avec l'userland (par exemple udev, X, chaîne de compilation).
Ensuite, parce que le noyau vanilla n'est pas "stable", dans le sens où la plupart des distributions utilisent les branches long term (en ce moment par exemple 2.6.32) avec de nombreux patchs backportés (il suffit de regarder le bruit provoqué par le changement de politique de RedHat au sujet de leur packaging du noyau pour voir combien de patches sont appliqués).

Juste pour préciser, c'est pas le fait que ce soient des pages anonymes qui empêche le swap...
Pour ce qui est de l'impossibilité, c'était vrai avec les hugepages classiques, maintenant avec THP je ne sais pas ce qu'il en est.

Pour le moment, les hugepage ne sont utilisables que pour des "anonymous pages" (ce qui exclut donc le demand paging et la pagination sur disque) :

Le patch actuel n'est pas encore tout à fait complet, puisqu'il ne permet d'exploiter que des huge pages d'une taille de 2 Mio. De plus, il ne fonctionne que sur les pages anonymes, c'est-à-dire celles obtenues à la suite d'un « malloc() ».

P.S. : même avec des pages de 4ko (sur x86), il y a de toute façon un read-ahead lors du demand-paging (sauf si les pages sont marquées VM_RAND_READ).

C'est un bug de binutils http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=616357

Si ça ne fonctionne pas, poste un message sur le forum.

P.S. : évite d'utiliser un noyau vanilla...

Quelle version de gcc ?

Intéressant...
Est-ce que vous avez des postes à pourvoir (CDI) dans le domaine du HPC chez EDF ?

On ne doit pas avoir la même notion de LTS : avec une nouvelle version tous les deux ans, plus un an de support, cela ne fait que trois ans au total, ce qui est vraiment faible...

Tu as au moins deux autres solutions :
1) démarre en runlevel 1 ("sans échec"), et lorsque tu as le prompt, entre "init 3"
-2) au démarrage, lorsque tu vois le menu Grub pour choisir le noyau à démarrer, appuie sur la touche 'e'. sélectionne la ligne contenant "boot", et appuie encore sur 'e'. à la fin de la ligne, ajoute "init 3", puis appuie sur esc, et enfin sur 'b'

Donc c'est bien ça, en runlevel 1 le réseau n'est pas configuré...

Tout est dans le titre.

vm.overcommit_memory = 2
vm.overcommit_ratio = 100

Ce n'est pas les paramètres par défaut, j'avais appliqué ces changements en me basant sur les recommandations du livre "Postgresql 9.0 High Performance".


Cela désactive l'overcommiting, cela signifie que le noyau n'allouera pas plus de SWAP + 100% RAM = SWAP + RAM. Sans cela, malloc peut renvoyer une adresse valide (i.e. pas NULL), mais l'OOM-killer se mettra en branle au moment où elle touchera les pages.

/proc/meminfo:
Committed_AS: 18687308 kB

Ça fait 17Go, mais que représente cette ligne ?


La mémoire réellement allouée. Le problème c'est que la valeur reportée par free (même en prenant en compte buffer/cache) est à peu près aussi fiable que madame Soleil : par exemple, sur certains noyaux, avec un FS ext3 monté avec data=ordered, si tu supprimes un fichier alors qu'il est ouvert, le taille reportée du page cache diminue, mais pas la mémoire free.
Un autre problème, c'est que tant que la page n'a pas été touchée par l'application, elle ne sera pas reportée comme utilisée.
Committed_AS est la quantité de mémoire qui a été réellement allouée par le noyau.
Il serait bien de faire un "watch cat /proc/meminfo" pendant que tu es en charge...

Que renvoie "sysctl -a | grep overcommit" ?
Que renvoie un "cat /proc/meminfo" (particulièrement la ligne committed_AS) ?