Is there a time bomb in sequential process id allocation when the `unsigned` wraps?

Question

I'm designing and implementing a multiprocessing postscript interpreter ("lightweight" processes simulated by a single OS-thread), and I need to generate a unique identifier for each process in the system, as well as maintain ids for any dead processes which still have live references. (Reference: Adobe PLRM, 2ed, Ch. 7 Display PostScript, http://partners.adobe.com/public/developer/en/ps/psrefman.pdf‎)

I've started with a simple increment, which arithmetically maps to the table index for the per-process data.

http://code.google.com/p/xpost/source/browse/itp.c#115

unsigned nextid = 0;  // global (file-static) counter

unsigned initctxid(void) {  // generate a new cid
    while ( ctxcid(++nextid)->state != 0 )  // .state == 0 means free
        ;
    return nextid; 
}

context *ctxcid(unsigned cid) {  // get context data from cid
    return &itpdata.ctab[ (cid-1) % MAXCONTEXT ];
}

But there's gonna be a big problem if (when) the unsigned wraps around. Perhaps not scary for a game or an application, but this thing is supposed to be a server. Eventually. I'd like to avoid writing (in earnest) the disclaimer, "warning: will start having strange problems after running for a long time".

So, it should be easy enough to detect when it wraps, but what then? Bail out?

So the situation/scenario so far is: you're a multitasking postscript server with a handful of processes with cids allocated during one epoch of the generator, and the epoch has just turned. My thought (not impossible, just seems really hard) is to compact these existing IDs down to the 0..N range (rewriting all references, scanning all memory if necessary) and reset nextid to N.

But that's gonna be a pain-in-the-butt. Is there a different way to generate these IDs so I don't have to do a big garbage-collect on them, and have it work, you know, perpetually?

Edit: A fact I neglected to mention was that the Display PostScript reference says IDs are not re-used during a running instance of the system. But since these IDs are not exposed, they cannot be saved in any form other than the context object. So re-use should be just fine as long as no running process can know about it (contains an old context object in accessible memory).

Answer 1

It doesn't matter if nextid wraps (as long as you don't have any overflow checking enabled).

What will happen is that the id is just passed into the function ctxcid which limits it to the range [0..MAXCONTEXT) (using the mod %). So the wrapping around happens way before the nextid wraps around.

So actually the worse case for you is the array filling up, which will cause an infinite loop because that while loop won't exit.