Free Guides
Language Tutorials
5. IPC mechanisms
This chapter describes the semaphore, shared memory, and message queue IPC mechanisms as implemented in the Linux 2.4 kernel. It is organized into four sections. The first three sections cover the interfaces and support functions for semaphores, message queues, and shared memory respectively. The last section describes a set of common functions and data structures that are shared by all three mechanisms.
5.1 Semaphores
The functions described in this section implement the user level semaphore mechanisms. Note that this implementation relies on the use of kernel splinlocks and kernel semaphores. To avoid confusion, the term "kernel semaphore" will be used in reference to kernel semaphores. All other uses of the word "sempahore" will be in reference to the user level semaphores.
Semaphore System Call Interfaces
sys_semget()
The entire call to sys_semget() is protected by the global sem_ids.sem kernel semaphore.
In the case where a new set of semaphores must be created, the newary() function is called to create and initialize a new semaphore set. The ID of the new set is returned to the caller.
In the case where a key value is provided for an existing semaphore set, ipc_findkey() is invoked to look up the corresponding semaphore descriptor array index. The parameters and permissions of the caller are verified before returning the semaphore set ID.
sys_semctl()
For the IPC_INFO, SEM_INFO, and SEM_STAT commands, semctl_nolock() is called to perform the necessary functions.
For the GETALL, GETVAL, GETPID, GETNCNT, GETZCNT, IPC_STAT, SETVAL,and SETALL commands, semctl_main() is called to perform the necessary functions.
For the IPC_RMID and IPC_SET command, semctl_down() is called to perform the necessary functions. Throughout both of these operations, the global sem_ids.sem kernel semaphore is held.
sys_semop()
After validating the call parameters, the semaphore operations data is copied from user space to a temporary buffer. If a small temporary buffer is sufficient, then a stack buffer is used. Otherwise, a larger buffer is allocated. After copying in the semaphore operations data, the global semaphores spinlock is locked, and the user-specified semaphore set ID is validated. Access permissions for the semaphore set are also validated.
All of the user-specified semaphore operations are parsed. During
this process, a count is maintained of all the operations that have the
SEM_UNDO flag set. A decrease flag is set if any of the
operations subtract from a semaphore value, and an alter
flag is set if any of the semaphore values are modified (i.e. increased
or decreased). The number of each semaphore to be modified is validated.
If SEM_UNDO was asserted for any of the semaphore operations, then the undo list for the current task is searched for an undo structure associated with this semaphore set. During this search, if the semaphore set ID of any of the undo structures is found to be -1, then freeundos() is called to free the undo structure and remove it from the list. If no undo structure is found for this semaphore set then alloc_undo() is called to allocate and initialize one.
Non-blocking Semaphore Operations
The try_atomic_semop() function returns zero to indicate that all operations in the sequence succeeded. In this case, update_queue() is called to traverse the queue of pending semaphore operations for the semaphore set and awaken any sleeping tasks that no longer need to block. This completes the execution of the sys_semop() system call for this case.
Semaphore Specific Support Structures
The following structures are used specifically for semaphore support:
struct sem_array
/* One sem_array data structure for each set of semaphores in the system. */
struct sem_array {
struct kern_ipc_perm sem_perm; /* permissions .. see ipc.h */
time_t sem_otime; /* last semop time */
time_t sem_ctime; /* last change time */
struct sem *sem_base; /* ptr to first semaphore in array */
struct sem_queue *sem_pending; /* pending operations to be processed */
struct sem_queue **sem_pending_last; /* last pending operation */
struct sem_undo *undo; /* undo requests on this array * /
unsigned long sem_nsems; /* no. of semaphores in array */
};
struct sem
/* One semaphore structure for each semaphore in the system. */
struct sem {
int semval; /* current value */
int sempid; /* pid of last operation */
};
struct seminfo
struct seminfo {
int semmap;
int semmni;
int semmns;
int semmnu;
int semmsl;
int semopm;
int semume;
int semusz;
int semvmx;
int semaem;
};
struct semid64_ds
struct semid64_ds {
struct ipc64_perm sem_perm; /* permissions .. see
ipc.h */
__kernel_time_t sem_otime; /* last semop time */
unsigned long __unused1;
__kernel_time_t sem_ctime; /* last change time */
unsigned long __unused2;
unsigned long sem_nsems; /* no. of semaphores in
array */
unsigned long __unused3;
unsigned long __unused4;
};
struct sem_queue
/* One queue for each sleeping process in the system. */
struct sem_queue {
struct sem_queue * next; /* next entry in the queue */
struct sem_queue ** prev; /* previous entry in the queue, *(q->pr
ev) == q */
struct task_struct* sleeper; /* this process */
struct sem_undo * undo; /* undo structure */
int pid; /* process id of requesting process */
int status; /* completion status of operation */
struct sem_array * sma; /* semaphore array for operations */
int id; /* internal sem id */
struct sembuf * sops; /* array of pending operations */
int nsops; /* number of operations */
int alter; /* operation will alter semaphore */
};
struct sembuf
/* semop system calls takes an array of these. */
struct sembuf {
unsigned short sem_num; /* semaphore index in array */
short sem_op; /* semaphore operation */
short sem_flg; /* operation flags */
};
struct sem_undo
/* Each task has a list of undo requests. They are executed automatically
* when the process exits.
*/
struct sem_undo {
struct sem_undo * proc_next; /* next entry on this process */
struct sem_undo * id_next; /* next entry on this semaphore set */
int semid; /* semaphore set identifier */
short * semadj; /* array of adjustments, one per
semaphore */
};
Semaphore Support Functions
The following functions are used specifically in support of semaphores:
newary()
newary() relies on the ipc_alloc() function to allocate the memory
required for the new semaphore set. It allocates enough memory for the
semaphore set descriptor and for each of the semaphores in the set. The
allocated memory is cleared, and the address of the first element of the
semaphore set descriptor is passed to ipc_addid(). ipc_addid() reserves
an array entry for the new semaphore set descriptor and initializes the
( struct kern_ipc_perm) data for the set. The global used_sems
variable is updated by the number of semaphores in the new set and the
initialization of the ( struct kern_ipc_perm) data for the new set is
completed. Other initialization for this set performed are listed below:
- The
sem_baseelement for the set is initialized to the address immediately following the ( struct sem_array) portion of the newly allocated data. This corresponds to the location of the first semaphore in the set. - The
sem_pendingqueue is initialized as empty.
All of the operations following the call to ipc_addid() are performed while holding the global semaphores spinlock. After unlocking the global semaphores spinlock, newary() calls ipc_buildid() (via sem_buildid()). This function uses the index of the semaphore set descriptor to create a unique ID, that is then returned to the caller of newary().
freeary()
freeary() is called by semctl_down() to perform the functions listed below. It is called with the global semaphores spinlock locked and it returns with the spinlock unlocked