#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
/* Constants */
#define ARRAY_SIZE 128
#define GEN_BITS 6
#define INDEX_BITS 7
#define MAX_PID ((1 << (GEN_BITS + INDEX_BITS)) - 1)
/* Macros to pack and unpack PIDs */
#define PID_TO_INDEX(pid) ((pid) & ((1 << INDEX_BITS) - 1))
#define PID_TO_GEN(pid) ((pid) >> INDEX_BITS)
#define MAKE_PID(gen, index) (((gen) << INDEX_BITS) | (index))
struct procinfo {
const char *name; /* In reality, we'd store other information here */
};
struct pid_entry {
/* Information we need to make the table work */
unsigned short generation;
bool is_free;
/* Information we want to store */
struct procinfo info;
};
struct pid_array {
struct pid_entry processes[ARRAY_SIZE];
int last_allocated;
};
/* We only have the one, so it's fine to make it global */
static struct pid_array pid_array;
/* Allocate a PID for a process with the given name. */
unsigned int
pid_alloc(const char *name)
{
int start = pid_array.last_allocated + 1;
for (int i = 0; i < ARRAY_SIZE; i++) {
int index = (start + i) % ARRAY_SIZE;
if (pid_array.processes[index].is_free) {
pid_array.processes[index].is_free = false;
unsigned int pid = MAKE_PID(
pid_array.processes[index].generation, index);
pid_array.last_allocated = index;
pid_array.processes[index].info.name = name;
return pid;
}
}
return MAX_PID + 1; // Error: no free PIDs
}
/* Free a PID. */
void
pid_free(unsigned int pid)
{
unsigned int index = PID_TO_INDEX(pid);
unsigned int generation = PID_TO_GEN(pid);
if (index < ARRAY_SIZE &&
pid_array.processes[index].generation == generation &&
!pid_array.processes[index].is_free) {
pid_array.processes[index].is_free = true;
pid_array.processes[index].generation =
(generation + 1) & ((1 << GEN_BITS) - 1);
}
}
/* Get the process information for a PID. */
struct procinfo *
pid_to_info(unsigned int pid)
{
unsigned int index = PID_TO_INDEX(pid);
unsigned int generation = PID_TO_GEN(pid);
if (index < ARRAY_SIZE &&
pid_array.processes[index].generation == generation &&
!pid_array.processes[index].is_free) {
return &pid_array.processes[index].info;
}
return NULL;
}
/* Initialize the PID array. */
void
pid_array_bootstrap(void)
{
for (int i = 0; i < ARRAY_SIZE; i++) {
pid_array.processes[i].is_free = true;
pid_array.processes[i].generation = 0;
}
pid_array.last_allocated = 0;
}
/* Test the PID allocator. */
int
main(void)
{
pid_array_bootstrap();
printf("Allocating three PIDs\n");
unsigned int pid1 = pid_alloc("Alice");
unsigned int pid2 = pid_alloc("Betty");
unsigned int pid3 = pid_alloc("Chloe");
printf("\nProcess names:\n");
printf("PID %u: %s\n", pid1, pid_to_info(pid1)->name);
printf("PID %u: %s\n", pid2, pid_to_info(pid2)->name);
printf("PID %u: %s\n", pid3, pid_to_info(pid3)->name);
pid_free(pid2);
printf("\nFreed PID %u\n", pid2);
/* Churn through 125 more PIDs to get to where we finally reuse an array
* slot, but not a PID. */
printf("\nChurning through more PIDs\n");
for (int i = 0; i < 125; i++) {
unsigned int pid = pid_alloc("Zarek");
pid_free(pid);
}
unsigned int pid4 = pid_alloc("Diane");
printf("Allocated new process with PID: %u\n", pid4);
printf("PID %u: %s (actually in slot %u)\n", pid4,
pid_to_info(pid4)->name, PID_TO_INDEX(pid4));
pid_free(pid1);
printf("\nFreed PID %u\n", pid1);
/* Churn through 127+62*128 = 8062 more PIDs, calculated get to where we
* finally reuse PID 1 */
printf("\nChurning through *LOTS* more PIDs\n");
for (int i = 0; i < 8063; i++) {
unsigned int pid = pid_alloc("Yanni");
pid_free(pid);
}
unsigned int pid5 = pid_alloc("Ellen");
printf("Allocated new process with PID: %u\n", pid5);
printf("PID %u: %s\n", pid5, pid_to_info(pid5)->name);
return 0;
}
