Why PIDs?

[OSwhatever]

Why are PIDs used instead of a direct pointer to the process or thread structure?

I can see a problem with pointers when you kill a process with a certain process pointer and a new process is created with the same address, a faulting program can use the pointer believing it is the old process. Therefore PIDs are used so that a new number is aquired everytime a process is created.

PIDs are really an extra level of indirection, that requires som acceleration structure to make the lookup fast. If we could remove this indirection we could speed up almost every system call.

The process structure is probably aligned in some way leaving some lower bits zeroed. Could these bits be used as a leap number preventing the situation described above?

Are there situations that PIDs are the only way or can it be done with pointers instead?

[bewing]

Partiallly, it depends on your design. We can assume that your job struct array is fixed in kernelspace virtual memory. But in general, is the userspace mapping of pointers into kernelspace valid? If not, then you need to do a full transition into kernelmode anyway. What if the userspace program trashes the pointer and hands you a request for an invalid pointer? Can you validate it? How long will that take?

If you port the OS to various platforms, then the size of pointers changes. This might be annoying if these pointers are going to get stored in structs.

But in general, what you are talking about for PIDs is exactly what the FILE * stream stuff does for file descriptors. So it certainly can be made to work.

[Gigasoft]

With reference counting, you don't risk pointers becoming invalid. In a secure system, user applications should not pass pointers are parameters to system services, since there would be no easy way of determining if they are valid. In a nonsecure system, it would work out fine, and process IDs would be unnecessary.

When manipulating processes, or anything else, I prefer to use handles instead of universal IDs to name them, so that the system immediately knows what access rights the calling process has for the object, and rights can be delegated easily. Looking up a handle has the same time cost as looking up a process ID, except that no complicated access check is necessary.

[gerryg400]

I can see a problem with pointers when you kill a process with a certain process pointer and a new process is created with the same address, a faulting program can use the pointer believing it is the old process. Therefore PIDs are used so that a new number is aquired everytime a process is created.

Yes, I think this (especially if you're using a slab allocator for kernel objects) and using a portable type for pid_t are the main inspirations for using an integer rather than a pointer for pid. And it's not just pids. In a Posixy system there are timers, semaphores, mutexes, threads,.. all manner of things that may require the same indirection. Some of these always use the smallest available entry and others (like the pid) use all the entries before reusing the lower numbers. There are ways to improve efficiency in both cases but it doesn't seem quite possible to make a system where every operation is O(1) and deterministic. In the end I decided that a dynamic array 'class' was the way to go.

[OSwhatever]

Partiallly, it depends on your design. We can assume that your job struct array is fixed in kernelspace virtual memory. But in general, is the userspace mapping of pointers into kernelspace valid? If not, then you need to do a full transition into kernelmode anyway. What if the userspace program trashes the pointer and hands you a request for an invalid pointer? Can you validate it? How long will that take?

If you port the OS to various platforms, then the size of pointers changes. This might be annoying if these pointers are going to get stored in structs.

But in general, what you are talking about for PIDs is exactly what the FILE * stream stuff does for file descriptors. So it certainly can be made to work.

Often FILE* use some kind of magic number in order to identify invalid pointers so I guess the same could be applied to process structures. Not 100% water tight but for most cases it should work.

[Owen]

Partiallly, it depends on your design. We can assume that your job struct array is fixed in kernelspace virtual memory. But in general, is the userspace mapping of pointers into kernelspace valid? If not, then you need to do a full transition into kernelmode anyway. What if the userspace program trashes the pointer and hands you a request for an invalid pointer? Can you validate it? How long will that take?

If you port the OS to various platforms, then the size of pointers changes. This might be annoying if these pointers are going to get stored in structs.

But in general, what you are talking about for PIDs is exactly what the FILE * stream stuff does for file descriptors. So it certainly can be made to work.

Often FILE* use some kind of magic number in order to identify invalid pointers so I guess the same could be applied to process structures. Not 100% water tight but for most cases it should work.

FILE* doesn't have to cross privilege boundaries. Its a pointer to an in process data structure - and generally encapsulates an ID which is an integer of some description.

PIDs do. They're handles to other processes. The kernel has to be able to validate them - and the only way to do this is to pass handle numbers and validate them

[Gigasoft]

I try to stay away from inconsistencies in how different types of objects are referred to. What good is it to have one type of global identifier for accessing processes, another private identifier for timers, another for semaphores, another for mutexes, another for files, etc? With a single mechanism for naming these objects, you don't have to invent the same thing over and over. One day I might want to pass a handle to an opened file to another process that doesn't have the privileges to open it on its own, and another day I might want to share a mutex between two processes, then I might want them to share a semaphore. It would be unreasonable to implement completely different ways to accomplish this based on the object type. I'd rather implement it once and for all and then forget about it.

[Owen]

Mostly I agree with you - but I have some issues with the prospect of making mutexes a standard handle. Namely, now you need to enter the kernel whenever you want to lock/unlock it, when in the uncontentious case you shouldn't need to.

Of course, providing a way to convert a mutex to a standard handle (so you can, say, select() or your OS' equivalent on it) is a wise idea)

[gerryg400]

With a single mechanism for naming these objects, you don't have to invent the same thing over and over.

So you think an abstract handle is preferable ?

[gerryg400]

Of course, providing a way to convert a mutex to a standard handle (so you can, say, select() or your OS' equivalent on it) is a wise idea)

Mutexes really need to be a variable in process space. But they also need a handle if you want to be able to block in the kernel when the mutex is not available. I've not really found a great solution to this and currently, I'm afraid to say, all my mutex calls enter the kernel. I'll need to address this one day, but time is short.

[Owen]

Of course, providing a way to convert a mutex to a standard handle (so you can, say, select() or your OS' equivalent on it) is a wise idea)

Mutexes really need to be a variable in process space. But they also need a handle if you want to be able to block in the kernel when the mutex is not available. I've not really found a great solution to this and currently, I'm afraid to say, all my mutex calls enter the kernel. I'll need to address this one day, but time is short.

Linux has a rather elegant solution: It looks up the physical address of the given mutex pointer and keys the queue object on that.

It does unfortunately mean that you can't select/poll/epoll on a mutex though; I've often wondered how difficult it would be to add support for that kind of feature.

[Gigasoft]

Yes, handles are definitely my preferred naming mechanism in most cases.

As for mutexes, those would be a special case and one could perhaps have two types of mutexes, one entirely kernel managed and one partially implemented in userland. Or, one could have a single kernel managed mutex type which implements functionality to assist an user space optimization layer.

Maybe one could specifiy one of several modes when creating a mutex, such as: shareable using system call only, single process with user mode layer and shareable accessible both with system call and user mode layer. Perhaps a mode where information accessed by the user mode layer is stored at an user-specified offset in a shared memory block. In this way, the shared memory can be mapped into system space and the system can access it in any process context, so that the mutex can be included in a multiple waiting scenario.

[froggey]

It does unfortunately mean that you can't select/poll/epoll on a mutex though; I've often wondered how difficult it would be to add support for that kind of feature.

There was support for this at one point:

FUTEX_FD (present up to and including Linux 2.6.25)
To support asynchronous wakeups, this operation associates a file descriptor with a futex. If another process executes a FUTEX_WAKE, the
process will receive the signal number that was passed in val. The calling process must close the returned file descriptor after use.
The arguments timeout, uaddr2 and val3 are ignored.

To prevent race conditions, the caller should test if the futex has been upped after FUTEX_FD returns.

Because it was inherently racy, FUTEX_FD has been removed from Linux 2.6.26 onwards.

[gerryg400]

Linux has a rather elegant solution: It looks up the physical address of the given mutex pointer and keys the queue object on that.

Oh, that's a good idea. It means mutexes can work in shared memory. It would need some sort of reverse lookup - either a hashing function or a linked list hanging off the phys_page struct. Something for me to think about.

[OSwhatever]

Partiallly, it depends on your design. We can assume that your job struct array is fixed in kernelspace virtual memory. But in general, is the userspace mapping of pointers into kernelspace valid? If not, then you need to do a full transition into kernelmode anyway. What if the userspace program trashes the pointer and hands you a request for an invalid pointer? Can you validate it? How long will that take?

If you port the OS to various platforms, then the size of pointers changes. This might be annoying if these pointers are going to get stored in structs.

But in general, what you are talking about for PIDs is exactly what the FILE * stream stuff does for file descriptors. So it certainly can be made to work.

Often FILE* use some kind of magic number in order to identify invalid pointers so I guess the same could be applied to process structures. Not 100% water tight but for most cases it should work.

FILE* doesn't have to cross privilege boundaries. Its a pointer to an in process data structure - and generally encapsulates an ID which is an integer of some description.

PIDs do. They're handles to other processes. The kernel has to be able to validate them - and the only way to do this is to pass handle numbers and validate them

How about doing it the other way. You have pointers as PIDs but the kernel validates the pointer for every system call. Basically, you can have a hash lookup of the pointer and if the pointer doesn't exist as a key, the pointer is invalid.

You have a problem when PIDs are wrapping, then you suddenly need to account where free PIDs are available. Doing this takes time and space. With pointers you "getting a free PID" for free since the memory allocation is basically doing the same thing.

The question is if you have a 32-bit PID, when is it going to wrap? Never or quickly? Imagine server with that creates a thread for every request, PID number will increase quickly.

Linux has a bitmap representing a free PIDs. Max threads are 32k so that yields a 4kB bitmap. If your programs are very thready and usage of pop up threads is common, that 4kB bitmap search is going to take time.