Re: Resuming work on new semaphore

[Rich Felker <dalias@libc.org>]

On Thu, Apr 23, 2015 at 11:01:19PM +0300, Alexander Monakov wrote:
> 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

Perhaps this can be patched up by saturating sem_getvalue's result? In
the case where the overflow happens it's transient, right? I think
that means discounting the overflow would be valid. But I'll need to
think about it more...

With that said, my inclination right now is that we should hold off on
trying to commit the new semaphore for this release cycle. I've been
aiming for this month and just about everything else is in order for
release, but the semaphore rabbit-hole keeps going deeper and I think
we need to work through this properly. I hope that's not too much of a
disappointment.

Rich