Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <alpine.LNX.2.11.1504232253520.2677@monopod.intra.ispras.ru>
Date: Thu, 23 Apr 2015 23:01:19 +0300 (MSK)
From: Alexander Monakov <amonakov@...ras.ru>
To: musl@...ts.openwall.com
Subject: Re: Resuming work on new semaphore

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

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.