From mboxrd@z Thu Jan  1 00:00:00 1970
X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/7498
Path: news.gmane.org!not-for-mail
From: Alexander Monakov <amonakov@ispras.ru>
Newsgroups: gmane.linux.lib.musl.general
Subject: Re: Resuming work on new semaphore
Date: Thu, 23 Apr 2015 23:01:19 +0300 (MSK)
Message-ID: <alpine.LNX.2.11.1504232253520.2677@monopod.intra.ispras.ru>
References: <20150402152642.GW6817@brightrain.aerifal.cx> <alpine.LNX.2.11.1504030021400.8195@monopod.intra.ispras.ru> <20150402231457.GC6817@brightrain.aerifal.cx> <alpine.LNX.2.11.1504051613090.8195@monopod.intra.ispras.ru> <alpine.LNX.2.11.1504051712170.8195@monopod.intra.ispras.ru>
 <20150405190214.GF6817@brightrain.aerifal.cx> <alpine.LNX.2.11.1504052217310.8195@monopod.intra.ispras.ru> <20150405202314.GG6817@brightrain.aerifal.cx> <alpine.LNX.2.11.1504052358560.8195@monopod.intra.ispras.ru> <alpine.LNX.2.11.1504120104090.8190@monopod.intra.ispras.ru>
 <20150423160624.GF17573@brightrain.aerifal.cx> <alpine.LNX.2.11.1504232031340.2677@monopod.intra.ispras.ru>
Reply-To: musl@lists.openwall.com
NNTP-Posting-Host: plane.gmane.org
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Trace: ger.gmane.org 1429819295 4467 80.91.229.3 (23 Apr 2015 20:01:35 GMT)
X-Complaints-To: usenet@ger.gmane.org
NNTP-Posting-Date: Thu, 23 Apr 2015 20:01:35 +0000 (UTC)
To: musl@lists.openwall.com
Original-X-From: musl-return-7511-gllmg-musl=m.gmane.org@lists.openwall.com Thu Apr 23 22:01:35 2015
Return-path: <musl-return-7511-gllmg-musl=m.gmane.org@lists.openwall.com>
Envelope-to: gllmg-musl@m.gmane.org
Original-Received: from mother.openwall.net ([195.42.179.200])
	by plane.gmane.org with smtp (Exim 4.69)
	(envelope-from <musl-return-7511-gllmg-musl=m.gmane.org@lists.openwall.com>)
	id 1YlNJU-0007j5-Sw
	for gllmg-musl@m.gmane.org; Thu, 23 Apr 2015 22:01:32 +0200
Original-Received: (qmail 26186 invoked by uid 550); 23 Apr 2015 20:01:31 -0000
Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm
Precedence: bulk
List-Post: <mailto:musl@lists.openwall.com>
List-Help: <mailto:musl-help@lists.openwall.com>
List-Unsubscribe: <mailto:musl-unsubscribe@lists.openwall.com>
List-Subscribe: <mailto:musl-subscribe@lists.openwall.com>
Original-Received: (qmail 26168 invoked from network); 23 Apr 2015 20:01:31 -0000
In-Reply-To: <alpine.LNX.2.11.1504232031340.2677@monopod.intra.ispras.ru>
User-Agent: Alpine 2.11 (LNX 23 2013-08-11)
Xref: news.gmane.org gmane.linux.lib.musl.general:7498
Archived-At: <http://permalink.gmane.org/gmane.linux.lib.musl.general/7498>

I was over-eager in size-optimizing and at first didn't notice that we may not
report EOVERFLOW after successfully incrementing val[0]; therefore we can
reuse only the very end of the futex-wake path:

#define VAL0_MAX (SEM_VALUE_MAX/2+1)
#define VAL1_MAX (SEM_VALUE_MAX/2)

int sem_post(sem_t *sem)
{
	int priv, old, val = sem->__val[0];
	val -= val == VAL0_MAX;
	while (old = val, (val = a_cas(sem->__val, val, val+1)) != old)
		if (val == VAL0_MAX) {
			priv = sem->__val[2];
			do {
				if ((val = sem->__val[1]) >= VAL1_MAX) {
					errno = EOVERFLOW;
					return -1;
				}
			} while (val != a_cas(sem->__val+1, val, val+1));
			goto wake;
		}
	if (val < 0) {
		priv = sem->__val[2];
		a_inc(sem->__val+1);
wake:
		__wake(sem->__val+1, 1, priv);
	}
	return 0;
}

Now instead of 'premature EOVERFLOW' problem we have the 'val[1] overshoot'
problem.  It can lead to getvalue overflow:

1. Semaphore initialized to SEM_VALUE_MAX
2. Thread A downs val[0] to 0
3. Thread B downs val[0] to -1
4. Thread A calls sem_post: val[0] == 0, val[1] == VAL1_MAX+1
.. (thread B does not consume the post yet)
5. Thread A ups val[0] to VAL0_MAX
.. now getvalue returns INT_MIN

Alexander