Algorithm Employed by System V IPC get Calls

Figure 45-1 shows some of the structures used internally by the kernel to represent information about System V IPC objects (in this case semaphores, but the details are similar for other IPC mechanisms), including the fields used to calculate IPC keys. For each IPC mechanism (shared memory, message queue, or semaphore), the kernel maintains an associated ipc_ids structure that records various global information about all instances of that IPC mechanism. This information includes a dynamically sized array of pointers, entries, to the associated data structure for each object instance (semid_ds structures in the case of semaphores). The current size of the entries array is recorded in the size field, with the max_id field holding the index of the highest currently in-use element.

Figure 45-1. Kernel data structures used to represent System V IPC (semaphore) objects

When an IPC get call is made, the algorithm used on Linux (other systems use similar algorithms) is approximately as follows:

The list of associated data structures (pointed to by elements of the entries array) is searched for one whose key field matches that specified in the get call.
If no match was found, and IPC_CREAT was specified, then a new mechanism-specific associated data structure (semid_ds in Figure 45-1) is allocated and initialized. This also involves updating various fields of the ipc_ids structure, and may involve resizing the entries array. A pointer to the new structure is placed in the first free element of entries. Two substeps are included as part of this initialization:
1. The key value supplied in the get call is copied into the xxx_perm.__key field of the newly allocated structure.
2. The current value of the seq field of the ipc_ids structure is copied into the xxx_perm.__seq field of the associated data structure, and the seq field is incremented by one.
The identifier for the IPC object is calculated using the following formula:
```
identifier = index + xxx_perm.__seq * SEQ_MULTIPLIER
```

In the formula used to calculate the IPC identifier, index is the index of this object instance within the entries array, and SEQ_MULTIPLIER is a constant defined with the value 32,768 (IPCMNI in the kernel source file include/linux/ipc.h). For example, in Figure 45-1, the identifier generated for the semaphore with the key value 0x4b079002 would be (2 + 5 * 32,768) = 163,842.

Note the following points about the algorithm employed by the get calls:

Even if a new IPC object is created with the same key, it will almost certainly have a different identifier, since the identifier is calculated based on the seq value saved in the associated data structure, and this value is incremented by one during the creation of each object of this type.

Note

The algorithm employed within the kernel wraps the seq value back to 0 when it reaches the value (INT_MAX / IPCMNI)—that is, 2,147,483,647 / 32,768 = 65,535. Thus, a new IPC object could have the same identifier as a previous object if 65,535 objects are created in the interim and the new object reuses the same element in the entries array as the previous object (i.e., this element must also have been freed in the interim). However, the chances of this occurring are small.

The algorithm generates a distinct set of identifier values for each index of the entries array.
Since the constant IPCMNI defines an upper limit on the number of System V objects of each type, the algorithm guarantees that each existing IPC object has a unique identifier.
Given an identifier value, the corresponding index into the entries array can be quickly calculated using this equation:

index = identifier % SEQ_MULTIPLIER

Being able to rapidly perform this calculation is necessary for the efficient operation of those IPC system calls that are supplied with the identifier of an IPC object (i.e., those calls in Table 45-1 other than the get calls).

In passing, it is worth noting that two different errors can result if a process makes an IPC system call (e.g., msgctl(), semop(), or shmat()) that specifies an identifier that doesn’t correspond to an existing object. If the corresponding index of entries is empty, the error EINVAL results. If the index points to an associated data structure, but the sequence number stored in that structure doesn’t yield the same identifier value, then it is assumed that an old object pointed to by this array index has been deleted and the index reused. This scenario is diagnosed with the error EIDRM.