[5962] in Athena Bugs
Xlib R4 Context Manager: Context.c
daemon@ATHENA.MIT.EDU (cfields@ATHENA.MIT.EDU)
Thu Sep 6 20:19:15 1990
From: cfields@ATHENA.MIT.EDU
Date: Thu, 6 Sep 90 20:18:54 -0400
To: bugs@MIT.EDU
The Context Manager of X11R4 (XSaveContext, XFindContext, et. al.) has
a nasty bug in it in the case that there are a large number (>1024) of
entries.
To tickle this bug:
----------------------------------------------------------------------
#include <stdio.h>
#include <X11/Xlib.h>
#include <X11/Xutil.h>
main()
{
int n, t;
Display *d;
d = XOpenDisplay(NULL);
for (n = 0; n < 513; n++)
{
XSaveContext(d, n, 0, n - 1);
XSaveContext(d, n, 0, n + 1);
XFindContext(d, n, 0, (caddr_t *)&t);
if (t != n + 1)
{
fprintf(stdout, "mismatch: %d %d\n", n + 1, t);
exit(-1);
}
}
XFindContext(d, 0, 0, (caddr_t *)&n);
fprintf(stdout, "%d\n", n);
}
----------------------------------------------------------------------
The "mismatch" fprintf is never executed, which is correct; however,
the last line of code prints out -1. It should print 1. (If you change
513 to 512, things work properly.)
What's happening?
First of all, the Context Manager uses an array of linked lists to
store its data. Each (WINDOW, CONTEXT) pair is hashed to come up with
an index into the array, and then the linked list that the array
element points to is where data is stored to and retreived from.
So, XSaveContext does not check to see if it's replacing an old value,
which is not in itself a bug (it's sort of documented in the
comments). So, when
XSaveContext(d, n, 0, n - 1);
XSaveContext(d, n, 0, n + 1);
is executed, two entries are made into the linked list that (n,0)
hashed into. The later saved value supercedes the previous value by
virtue of the fact that its entry is inserted into the linked list in
front of the original entry, and XFindContext searches from front to
back.
This is all fine. The problem comes when you add your 1025th entry.
The code is set up so that when you reach this size, it will increase
the size of the hash table.
----------------------------------------------------------------------
/* Resize the given dsp to have the given number of hash buckets. */
static int ResizeTable(dsp, NewSize)
Dsp dsp;
int NewSize;
{
TableEntry *OldHashTable;
register TableEntry CurEntry, NextEntry;
register int i, OldHashSize, CurHash;
OldHashTable = dsp->table;
OldHashSize = dsp->size;
dsp->table = (TableEntry *) Xcalloc((unsigned)NewSize,sizeof(TableEntry));
if (dsp->table == NULL) {
dsp->table = OldHashTable;
return XCNOMEM;
}
dsp->size = NewSize;
dsp->maxentries = NewSize; /* When to next resize the hash table. */
if (OldHashTable != NULL) {
for (i=0 ; i<OldHashSize ; i++) {
CurEntry = OldHashTable[i] ;
while (CurEntry != NULL) {
(void) XDeleteContext(dsp->display,
CurEntry->window, CurEntry->context);
NextEntry = CurEntry->next;
CurHash = HashValue(CurEntry->window, CurEntry->context,
NewSize);
CurEntry->next = dsp->table[CurHash];
dsp->table[CurHash] = CurEntry;
CurEntry = NextEntry;
}
}
Xfree((char *) OldHashTable);
}
return 0;
}
----------------------------------------------------------------------
So, this code allocates a hash table of the new size we want. Then it
begins copying entries from the old table into the new one. It makes
an effort (via the XDeleteContext call) to remove all but the newest
of equivalent (WINDOW, CONTEXT) pairs. But what it actually does is
remove all but the _oldest_. That is:
old table list: A B C
Assume A, B, C have the same (WINDOW, CONTEXT).
So the code takes A, deletes anything of its (WINDOW, CONTEXT) from the
new table, and then adds it to the table.
new table list: A
Next we get to B. It deletes A, and then puts B in the list. But B
is older than A...
A good fix might be:
int garbage;
.
.
.
if (OldHashTable != NULL) {
for (i=0 ; i<OldHashSize ; i++) {
CurEntry = OldHashTable[i] ;
while (CurEntry != NULL) {
NextEntry = CurEntry->next;
if (XCNOENT == XFindContext(dsp->display,
CurEntry->window,
CurEntry->context,
&garbage)) {
CurHash = HashValue(CurEntry->window, CurEntry->context,
NewSize);
CurEntry->next = dsp->table[CurHash];
dsp->table[CurHash] = CurEntry;
}
else
Xfree((char *) CurEntry);
CurEntry = NextEntry;
}
}
This checks to see if there's already an entry with the same (WINDOW,
CONTEXT) before adding the current entry. If there is, it just frees
the current entry and continues. This should properly preserve the
newest of a set of (WINDOW, CONTEXT) entries. But I haven't tested it.
Another fix would be just to have XSaveContext write over the top of a
duplicate (WINDOW, CONTEXT) entry in the first place.
