Name: clC74495 Date: 09/23/98


This bug is from Oracle, a JavaSoft licensee.

In CmdIDList.cpp, menu ids are generated by simply incrementing
an integer. In JDK 1.1.5, this integer was incremented without
bound, eventually passing the limit of menu ids that can be
used on Windows 95 and finally overflowing the integer. In JDK
1.1.7, a "solution" to this was put in, whereby when the
integer hits 65535, it is reset to 0. There are two problems:
1) 65535 is too high for Windows 95. Using id's in the 60000
   range is fine on Windows NT, but on Windows 95 it results
   in blank menu items.
2) Setting the integer back to 0 blindly overwrites menu items.
   That is, say I bring up a window which will stay up the
   entire time I run. Then, while my application is creating
   some other window, the menu id hits 65535 and loops back
   to 0. The new window's menu items will begin overwriting
   my first window's menu items. This results in a crash
   when one of these overwritten items is selected.
The code was apparently written assuming that no one would ever
use this many ids. But this is a very realistic case for us.
We have applications that are designed to be run continuously
without shutdown, and which have a lot of windows. We create
and destroy windows as necessary. After a few days of running,
we easily hit the 65535 limit.
The following code can be used to see these 2 problems. Note
that problem (1) can only be observed on Windows 95, but (2)
can be observed on both 95 and NT. This code uses 200 menu
items per window. Bringing up 300 such windows gives 60000
menu items and reproduces problem (1), while using 400 windows
uses 80000 menu items and illustrates problem (2). The number
of windows is specified by the numWindows variable.

import java.awt.*;
import java.awt.event.*;

public class MenuBug extends Frame {

    static int numWindows = 300;
    static int n = 0;

    public MenuBug() {
        MenuBar mb;
        Menu m;
        MenuItem mi;

        addWindowListener(new WindowAdapter() {
            public void windowClosing(WindowEvent e) {
                    System.exit(0);
            }
        });

mb = new MenuBar();
int i, j;
        for (i = 0; i < 10; i++) {
m = new Menu("Menu_" + (i+1));
for (j = 0; j < 20; j++) {
mi = new MenuItem("Menu item " + n++);
m.add(mi);
}
            mb.add(m);
}
setMenuBar(mb);
    }
    public static void main(String[] args) {
MenuBug firstWindow = new MenuBug();
firstWindow.setTitle("First Window");
firstWindow.setSize(450, 200);
firstWindow.setVisible(true);
for (int i = 0; i < numWindows; i++) {
MenuBug window = new MenuBug();

window.setTitle("Running...");
window.setSize(450, 200);
window.setVisible(true);
if (i != (numWindows - 1)) {
window.setVisible(false);
window.dispose();
}
            else {
window.setTitle("Last Window");
            }
}
    }
}

This will take a minute to run because it is creating so many
windows.

After running this code with 300 windows, you will see blank
menus in the window labelled "Last Window" on Windows 95.
After running with 400 windows, selecting a menu item in the
window labelled "First Window" will cause a crash on either
Windows NT or 95.

Problem (1) can be easily fixed by lowering the menu id limit.
As far as I can tell, Microsoft does not publish the maximum
id that can be used on Windows 95. But 32K is a safe bet and
is what we use to work around the problem. Together with the
solution to problem (2) below, lowering the limit does not
cause any problems.

Problem (2) can only be fixed by implementing an intelligent
menu recycling algorithm. When you hit the maximum number of
ids, don't just set back to id 0. Instead, start scanning for
free ids from menu items that have been garbage collected. Our
changes to CmdIDList.cpp to implement such an algorithm are
given here:

#include "CmdIDList.h"

#define INITIAL_CAPACITY 16
#define GROW_BY 16
#define MAX_CAPACITY 32768 // 32K

AwtCmdIDList::AwtCmdIDList() : m_lock("AwtCmdIDList")
{
    m_isfull = FALSE;
    m_size = 0;
    m_capacity = INITIAL_CAPACITY;
    m_array = (AwtObject**)malloc(m_capacity * sizeof(void*));
    ASSERT(m_array != NULL);
}

AwtCmdIDList::~AwtCmdIDList()
{
    free(m_array);
}

// Add an object to the end of the vector, increasing its capacity if necessary
UINT AwtCmdIDList::Add(AwtObject* obj)
{
  CriticalSection::Lock l(m_lock);

  UINT id;
  if ( !m_isfull && (m_size == m_capacity) ) {
    // We must grow the array
    if (m_capacity >= MAX_CAPACITY) {
      // The array is at maximum capacity and cannot be grown
      m_isfull = TRUE;
    }
    else {
      // Grow the array
      m_capacity += GROW_BY;
      m_array = (AwtObject**)realloc(m_array, m_capacity * sizeof(void*));
ASSERT(m_array != NULL);
    }
  }
  if ( m_isfull )
  {
    // Once the array is at maximum capacity, we must seek for free ids
    if (m_size >= m_capacity)
      m_size = 0;
    id = m_size;
    while( m_array[m_size] ) {
      if (++m_size >= m_capacity)
        m_size = 0;
      if (m_size == id) {
        // We've looped back around to where we started. This means there
        // are no free id's!
        ASSERT(FALSE);
        return 0;
      }
    }
  }
  id = m_size++;
  m_array[id] = obj;
  return id;
}

// Return the associated object.
AwtObject* AwtCmdIDList::Lookup(UINT id)
{
    CriticalSection::Lock l(m_lock);

    ASSERT(id < m_capacity);

    return m_array[id];
}

void AwtCmdIDList::Remove(UINT id)
{
    CriticalSection::Lock l(m_lock);
    m_array[id] = NULL;
}

The only change to CmdIDList.h was to add the m_isfull boolean.

This algorithm can only fail if 32768 menu ids are used AT THE
SAME TIME, that is, if you have enough windows on the screen
at any given time to use this many ids. But this should
realistically never happen. It does solve the case where
windows are created and destroyed over time. Performance will
be slightly worse once the maximum id has been hit, because it
must seek for new ids after that. But since menus tend to be
freed up as windows are freed, entire blocks of ids will become
free at one time (all the menu ids for the freed window). So
the algorithm should very quickly be able to find the next free
block of ids and then becomes a simple incrementation until
that block is filled up and it must seek to the next free block.
(Review ID: 39227)
======================================================================