What happens when you run out of PIDs?

The fork syscall should return -1, and set errno to EAGAIN. What happens after that will depend on the process that called fork.

From fork:

The fork() function shall fail if:

[EAGAIN]

The system lacked the necessary resources to create another process, or the system-imposed limit on the total number of processes under execution system-wide or by a single user {CHILD_MAX} would be exceeded.

POSIX doesn't specify that the PID of each new process is obtained by incrementing the previous PID. It only requires it to be unique.

On a system where PIDs are incremented on each fork(), I've observed that the values wrap around after reaching some upper bound (which in my experience is around 2¹⁵). After wrapping around, new PIDs are not strictly incremented, since some PID values will still be in use from previous cycles.

There shouldn't be a problem until you have 2^N simultaneously running processes. I suspect the system would run into some capacity limit long before that happened. In that case, the fork() system call would fail and probably set errno to EAGAIN or ENOMEM (man fork for details).

The code that implements fork may or may not check whether any PIDs are available. It might not bother, because it assumes that system resources would have run out before it got to that point, or it might have an explicit check for the sake of completeness and to handle future possibilities. I haven't checked, and if I had I could only address whichever kernel I had looked at.

UPDATE: On my current system (Ubuntu 20.04), the maximum PID is 2²², as seen here:

$ cat /proc/sys/kernel/pid_max
4194304

From man proc :

/proc/sys/kernel/pid_max (since Linux 2.5.34)

This file specifies the value at which PIDs wrap around (i.e., the value in this file is one greater than the maximum PID). PIDs greater than this value are not allocated; thus, the value in this file also acts as a system-wide limit on the total number of processes and threads. The default value for this file, 32768, results in the same range of PIDs as on earlier kernels. On 32-bit platforms, 32768 is the maximum value for pid_max. On 64-bit systems, pid_max can be set to any value up to 2^22 (PID_MAX_LIMIT, approximately 4 million).

But the specific maximum is probably not terribly relevant to the question, except that you're even less likely to be able to have 4+ million processes than to have more than 32767.

The maximum PID limit is much much less than 2^((sizeof(int)*CHAR_BIT). See What is the maximum value of the Process ID?. In other words, your PIDs will never go near 4 billion.

When all pid slots are filled, fork calls will start failing with errno==EAGAIN (see fork(2)). If you simply hit the top without filling all the slots, the next PID will be the next free slot after 1 (1 is init)