What happens when two semaphores change simultaneously and one of the two cannot decrement immediately?

Question

Consider this code:

struct sembuf s_op[2];

s_op[0].sem_num = old;
s_op[0].sem_op = 1;
s_op[0].sem_flg = 0;
s_op[1].sem_num = new;
s_op[1].sem_op = -1;
s_op[1].sem_flg = 0;
semop(semid, s_op, 2);

Now, if "new" cannot be decremented immediately (because it is already at 0), will there be a time interval in which the "old" semaphore has been increased and the "new" one has not? I mean, can this always happen atomically?

Answer 1

Here are some implementation details in Linux 5.4. The source code managing the sysV semaphores is in ipc/sem.c.

The semop() system call entry point calls the common internal do_semtimedop() function with the timeout parameter set to NULL:

SYSCALL_DEFINE3(semop, int, semid, struct sembuf __user *, tsops,
        unsigned, nsops)
{
    return do_semtimedop(semid, tsops, nsops, NULL);
}

After some checks on the parameters and permissions, loosely speaking, do_semtimedop() locks the whole semaphore set and calls another internal routine named perform_atomic_semop() which makes the requested "sem operations". This function scans the semaphore set twice:

1. First scan loop determines if any of the operation leads to a negative value for the semaphores in the set. If yes, it returns -EAGAIN if IPC_NOWAIT is set in the flags or 1 if it is not set. It may also return -ERANGE if one of the operations results in a value bigger than the maximum (defined as SEMVMX = 32767 in include/uapi/linux/sem.h).
2. Second scan loop makes the requested operations as the first loop determined that this will not result into negative values for the semaphores. 0 is returned.

static int perform_atomic_semop(struct sem_array *sma, struct sem_queue *q)
[...]
    /*
     * We scan the semaphore set twice, first to ensure that the entire
     * operation can succeed, therefore avoiding any pointless writes
     * to shared memory and having to undo such changes in order to block
     * until the operations can go through.
     */
    for (sop = sops; sop < sops + nsops; sop++) {
        int idx = array_index_nospec(sop->sem_num, sma->sem_nsems);

        curr = &sma->sems[idx];
        sem_op = sop->sem_op;
        result = curr->semval;

        if (!sem_op && result)
            goto would_block; /* wait-for-zero */

        result += sem_op;
        if (result < 0)
            goto would_block;

        if (result > SEMVMX)
            return -ERANGE;

        if (sop->sem_flg & SEM_UNDO) {
            int undo = un->semadj[sop->sem_num] - sem_op;

            /* Exceeding the undo range is an error. */
            if (undo < (-SEMAEM - 1) || undo > SEMAEM)
                return -ERANGE;
        }
    }

    for (sop = sops; sop < sops + nsops; sop++) {
        curr = &sma->sems[sop->sem_num];
        sem_op = sop->sem_op;
        result = curr->semval;

        if (sop->sem_flg & SEM_UNDO) {
            int undo = un->semadj[sop->sem_num] - sem_op;

            un->semadj[sop->sem_num] = undo;
        }
        curr->semval += sem_op;
        ipc_update_pid(&curr->sempid, q->pid);
    }

    return 0;

would_block:
    q->blocking = sop;
    return sop->sem_flg & IPC_NOWAIT ? -EAGAIN : 1;
}

Back in do_semtimedop(), the return from perform_atomic_semop() is checked:

• If the returned value is 0, any waiting tasks on the semaphore set are woken up to run their pending operations before being woken up (i.e. do_semtimedop() is recalled for each waiting task). The global lock is released and 0 is returned
• If the return value is negative (-EAGAIN or any other detected error like -ERANGE), the global lock is released and the errno is returned
• If the return value is > 0 (actually 1), the calling task is put to sleep: it is added in the wait queue of the semaphore set. The call is blocked until the task is woken up.

So, to answer the question, there is no intermediate time period where one semaphore operation is done while the other is pending on the same set. There are all done at once or the calling task is put to sleep until it can do it.