Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!helios!bcm!dimacs.rutgers.edu!seismo!uunet!ora!bloom-beacon!dont-send-mail-to-path-lines
From: mouse@lightning.mcrcim.mcgill.EDU
Newsgroups: comp.windows.x
Subject: Re:  resource ID allocation
Message-ID: <9103020227.AA05727@lightning.McRCIM.McGill.EDU>
Date: 2 Mar 91 02:27:00 GMT
Sender: daemon@athena.mit.edu (Mr Background)
Organization: The Internet
Lines: 107

>>> If not, clients which manage a lot of resources for a long time may
>>> run out of valid ID's.
>> This seems like a silly thing to worry about.  However, [...].
> Over christmas 1989 I ran Xvstress from the X Test Suite on (against
> :-)) one of our servers.  When I came back (after about two weeks)
> the XVSpixmap test had failed with a BADIDChoice error.  [...]

> I fixed up XVSpixmap.c by remembering display->resource_id before the
> test and resinstating it after (when the pixmaps had been freed).
> [...]
> Detecting wrap-round is easy, but dealing with it is not.  In general
> a (probably) small number of resource id's will be permanently
> allocated as an application starts up; it is essential that no
> attempt is made to reuse these when the resource id counter wraps
> round!  There are obvious heuristics (wrap round to
> client_base+<small number> rather than client_base), but the
> application may also allocated permanent id's at arbitrary times
> while it is running...

It seems to me that the solution to this is to reuse IDs right away.
For example, keep a table of IDs in use - or perhaps just their
resource_id values, which amounts to the same thing - and mark them as
taken or free as they are used or freed.  Then choosing a known-free ID
is as simple as looking for a free slot in the table.

Of course, it won't necessarily be implemented as a simple array.
Something like this, perhaps:

typedef struct Xlib_free_id { /* Xlib internal */
  struct Xlib_free_id *link;
  XID xid;
  } FreeID;

typedef struct _XDisplay {
  ....
  FreeID *free_ids;
  ....
  } Display;

FreeID *free_free_ids = 0;

XID new_xid(register Display *disp) /* Xlib internal */
{
 register FreeID *fid;
 register XID id;

 fid = disp->free_ids;
 if (fid)
  { disp->free_ids = fid->link;
    id = fid->xid;
    fid->link = free_free_ids;
    free_free_ids = fid;
  }
 else
  { id = (disp->resource_id++ << disp->resource_shift) |
						disp->resource_base;
  }
 return(id);
}

free_xid(register Display *disp, XID xid) /* Xlib internal */
{
 register FreeID *fid;

 fid = free_free_ids;
 if (fid)
  { free_free_ids = fid->link;
  }
 else
  { fid = malloc(sizeof(FreeID));
  }
 fid->xid = xid;
 fid->link = disp->free_ids;
 disp->free_ids = fid;
}

This should give decent performance with small memory overhead (except
for pathological programs that allocate a huge number of resources
simultaneously and then free most of them, which I wouldn't worry
about).  The major damage I can see is that when you use a resource
after freeing it, you are much less likely to get a
BadWindow/BadGC/BadDrawable/etc error; instead, you will all too likely
just get the wrong resource.  Perhaps this algorithm should be used
only on request (XHeavyResourceUsage(Display *, Boolean) perhaps?).

It does require hooks in the FreePixmap, FreeGC, DestroyWindow, etc,
routines.  While this will not always detect when an XID can be reused
(other clients can explicitly destroy resources, and multiple windows
with effectively impossible-to-determine XIDs can be destroyed with a
single call to XDestroyWindow), it will cover most cases.  It will
certainly come just about as close as any Xlib-based solution can.
(Watching for DestroyNotify events might help the window situation a
little bit.)

> The general solution is to have a private display->resource_alloc
> procedure which ``knows'' whether an id is only required for a short
> time or for a long time.

Aside from the strict stack discipline imposed on the temporary IDs by
this, a serious program (as opposed to stress test) may not always know
ahead of time whether a resource will stick around for a long time.
(Some will, certainly; this is a reasonable approach for them.)

					der Mouse

			old: mcgill-vision!mouse
			new: mouse@larry.mcrcim.mcgill.edu