Archive for May, 2007

Menus Explored, Part 5

Friday, May 18th, 2007

The SourceMod menu system, now (mostly) finished, has its own wiki article, which is where most of this article will be directed to.

SourceMod’s menu complexity is effectively doubled because unlike the other menu systems mentioned, SourceMod needs to have one API that works for multiple systems at the same time (Valve-style menus and Radio-style menus). The trick is that both systems share very similar code with subtle changes. Finding a good way to abstract this was very difficult and took many rewrites.

In the end, we went for three layers of objects.

  • Styles, which are essentially mini-menu systems, detect item selection and are responsible for creating the other objects with their style-specific functionality.
  • Panels are low-level API for designing a menu without having to know how to call the underlying API (such as the ShowMenu message or using IServerPluginHelpers).
  • Menus are high-level API similar to AMX Mod X’s “new menus.” You can add items and an algorithm will display them such that every menu has a similar, consistent feel.

Although all of these objects derive from a base type, they are each responsible for implementing the API correctly; which means the complexity has doubled. However, there are a few cases we caught ahead of time:

  • Menus can be canceled such that no new menus can be displayed during the cancellation process. This is a huge re-entrancy feature that no previous system did, and it led to some weird infinite menu situations.
  • Menu are NOT queued. Because of drawing bugs with the HUD, it is possible for menus to disappear without ever sending a callback command. Thus, it would be possible to permanently stall the queue while the client is unable to select anything. Introducing a queue would mean introducing an arbitrary de-facto timeout for all menus. It would also further add to the API complexity and introduce usability questions like “should the menu be appended to the end or the front of the queue?” In the end, it suffices to:
    • Make all menus overwrite each other.
    • Make sure the API will tell menus when they’ve been overwritten.
    • Add functions to see if a player is currently supposed to be viewing a menu.

    With this functionality, authors can be respectful of other menus and wait to display for unimportant actions.

  • Callbacks are tied to menus once again, unlike the proprietary system but like AMX Mod X. This had to be done for plugin unloadability. If a handler wasn’t tied to a menu, you could display someone else’s menu with your own functions. When your plugin unloaded, Core would have to do a deep-sweep of everyone’s menus to make sure no handlers were owned by your plugin. (In fact, this already has to be done for Panels!) Instead since Menus are Handles, they will get automatically canceled when the owning plugin unloads, along with their callbacks.
  • The Menu Manager makes no attempt to interfere with styles. All of the drawing, preparation, and selection key detection is done by styles alone. The only thing the Menu Manager bothers to do is provide an algorithm for adding items to menus in a paginated way.
  • There is no “page key to item” algorithm like in the previous systems. Consider the fact that when rendering the menu, you know exactly which items are going to be bound to each key. We took this and gave each player a “selection[10]” array which maps each key press to a potential item. Now, item selection is O(1) with absolutely no complications whatsoever. There should never be any bugs with this, whereas the old system has continual problems.

While SourceMod’s menu system is much more complicated, a lot of this complication came from simply figuring out the design. When all is said and done, it is much easier and more reliable to work with.

Menus Explored, Part 4

Wednesday, May 16th, 2007

Last time, we saw that despite AMX Mod X’s new menu improvements, the system was still flawed in its implementation. After finishing the AMX Mod X new menu system, I had to implement another one for a proprietary project, and naturally used the AMX Mod X one as a basis.

There first major difference is the addition of more callbacks. In AMX Mod X, all menu actions were pumped through one callback best described as:

void MenuSelectItem(Menu *menu, int client, int item);

The new system adds:

void MenuSelectItem(Menu *menu, Item *item, int client);
void MenuDisplayEnd(Menu *menu, int client, bool cancelled);

Note that a menu being canceled and an item being selected are now separate callbacks. This separation is syntactic sugar, but helps make the API cleaner. The next major change is the addition of broadcast displays. Broadcasting displays a menu to one or more clients and waits for the menu to complete on each one. This is extremely helpful for implementing voting routines. The callbacks for broadcasting become:

void MenuSelectItem(Menu *menu, Item *item, int client);
void MenuDisplayEnd(Menu *menu, int client, bool cancelled);
void MenuBroadcastEnd(Menu *menu);

Additionally, queuing is added. Menus cannot override other menus, and instead get added to a queue. This queue is pricey in both complexity and processing power. Consider a voting menu that runs for N seconds – it must complete within N seconds regardless of whether or not all clients have selected items. This means that if the menu is queued on one client’s display, it must timeout while in the queue. For both Source and HL1 this check is implemented in players’ PreThink functions.

Also, the queue is undefined for some menu situations. For example, let’s say a player’s menu stops being drawn for some reason. Let’s say the HUD bugs out from an ALT+TAB (common in HL1), or another menu that can’t be detected overrides it. If that menu had an infinite display time, and the player can’t select any items, it means the queue will never be processed again. The only real way to solve this is to put an upper bound on menu times. For example, if an infinite menu isn’t processed with 60 seconds, and there are items in the queue, the queue will be processed.

The queue must be guaranteed to properly flush in every imaginable case; that is, if a menu is displayed to a client, an exit state must ALWAYS be passed onto the MenuDisplayEnd callback. Otherwise, memory leaks would be the worst of problems. Menu code is often heavily state based, and if menus don’t end, the next state in a plugin’s logic will never be reached. Over the past year, I have encountered maybe twenty five bugs combined with AMX Mod X’s menu system and the proprietary one. Every single one falls into one of two categories:

  1. The “key to item selection” algorithm fails in some case. This is the algorithm that, given a page in a menu and a key pressed, determines which item was selected.
  2. Some logic error in the menu system fails to call MenuDisplayEnd, meaning a state never jumps, or memory leaks. These logic errors are usually re-entrancy bugs, optimization oversights, or problems with clients disconnecting.

Menus are complicated. Tomorrow, we’ll look at why SourceMod’s menu system becomes frighteningly more complicated.

Menus Explored, Part 3

Monday, May 14th, 2007

Last article, we saw that AMX Mod X’s new menus allowed for separate menu building objects, which could then be displayed to clients. This display-agnostic system makes mod support, pagination, and item selection calculation much easier for developers.

The first question is a crucial one. Let’s say we want to translate a menu differently for each player. Do we:

  1. Create a different menu for each player and then destroy it, or;
  2. Alter the menu after each display?

The answer is neither. The new menu system has item callbacks, which are called before drawing each item. In these callbacks, developers can dynamically change how their menu is displayed per-client, without altering the menu itself. In here, the item’s display text can be altered, or the item’s enabled/disabled status can be toggled. When we start discussing SourceMod’s menu system, we’ll see that this concept totally breaks down when we combine it with AMX Mod X’s pagination and item selection algorithms.

What happens if we destroy a menu that’s being displayed? The menu gets removed from every player. While it may linger on the screen, Core must remove all references to it.

What happens if a menu gets displayed over another menu? AMX Mod X does not queue menus. Next article we’ll take a look at a system that does.

The most important question of all is: what happens if a player doesn’t select an item? If the menu gets overridden, canceled, the client disconnected, or the menu times out, the user must have some way of knowing so they can call menu_destroy. The menu handler has a special case for this in which the callback gets an invalid item, -3, which means “the menu has been exited.” Thus, there are two burdens here:

  • Core must guarantee that if the menu is ever “lost” somehow, that the callback will always be given an exit code. Otherwise, it will memory leak.
  • There is a burden on developers to make sure that they call menu_destroy on temporary menus both in the case of a valid item and an exit code.

The situation gets even murkier. Let’s say we have the following pseudo-code:

show(client)
{
   new menu = menu_create("My Menu", "MyHandler")
   menu_display(menu, client)
   menu_destroy(menu)
}
 
public MyHandler(menu, client, item)
{
   if (item == MENU_EXIT)
   {
      menu_destroy(menu)
   } else {
      /* item code */
      menu_destroy(menu)
   }
}

In this example, we’ve destroyed a menu while it’s being displayed. This triggers the menu’s handler with an exit code. However, the code has no way of knowing that the menu is already being destroyed, and thus must assume it’s safe to destroy the menu. Although this re-entrancy problem is mitigated with menu_cancel, it still exists, and it must be made safe in Core.

In conclusion, we can see that the AMX Mod X new menu system is still flawed. It has subtle re-entrancy issues stemming from a limited callback design. It has complicated case scenarios about the current state of a menu and its relation to players. It does not support queuing. The item selection calculations tend to be expensive and buggy, as it has to account for which page the player was viewing. And lastly, as we’ll see later, the pagination system itself does not really work in advanced cases.

Next article, we’ll go into another menu system I designed for a proprietary system at the same time. After that, we’ll dive into SourceMod menus.

Menus Explored, Part 2

Friday, May 11th, 2007

Last article, we saw that menus needed to be separated into building and displaying, or else you end up with very limited, platform-specific code. How did we try to correct this with AMX Mod X’s new menu system?

The crux of the new menu system is in four functions:

  • menu_create/menu_destroy – Creates/destroys a new menu object.
  • menu_additem – Adds a selectable item to the menu.
  • menu_display – Displays a menu to a client.

Note that instead of generating the display string themselves, users can now add items one by one. The display function handles building the internal string for the user, as well as calculating the selectable key bitmask. The menu also handles pagination; if you add more than 10 items, the menu will be drawn with “Next/Back” options that work automatically.

How does the callback work? Instead of using the menu text string as a unique identifier, the menu handle itself is considered unique. Each new menu gets one and only one callback, and this is registered in menu_create. The only complicated part about this callback is calculating which item the user actually selected. If the user presses key ’5′ on page ’3′, the meaning of that 5 will change based on whether page 3 is at the middle or the end of the menu, how many items there are per page, and how many items were drawn on that particular page. Core does this by breaking the menu items into separate pages, and then remembering which page a user viewed. Since it doesn’t remember which items were on which page, it must make a positional calculation on every selection.

Why do menus work that way? It’s an optimization. Consider if menu_display destroyed the menu once the client was finished, or made a copy of the old menu, or something like that, just so the exact item list could be preserved even if the original was altered. This continual copying would be a performance hindrance, and suggesting to users that changing menus during display is a good idea would only lead to their own coding mistakes. Thus, we made the decision to keep menus “static” – you can add or edit items, but not remove them. Nonetheless, the actual item selection algorithm itself has been a near-endless source of “off by one” bugs, and we’ll see later that SourceMod does away with it.

The complications just start here. Next article, we’ll visit more issues that derived from AMX Mod X’s new menu system:

  • If you can’t edit the menu while it’s being displayed, how can you display one menu to multiple people and translate/disable certain items for each displayed instance? Do you have to create and destroy a new menu for each user?
  • If you destroy a menu, what happens if it’s currently being displayed to other players?
  • To avoid memory leaks, you need to call menu_destroy when you’re finished with a menu. But how can you destroy it if a player’s menu never finishes (disconnect, overridden, et cetera)?
  • If you display a menu to a player when a menu already exists for them, what happens?

Menus Explored, Part 1

Wednesday, May 9th, 2007

Menus are surprisingly complex design issues. Much like timers, they have gone through numerous iterations in both API and implementation throughout my/our development projects.

A menu system can be broken down into two major pieces. The first piece is the part that builds the menu; for example, managing how many items the menu has. The second piece is the part that draws the menu, displaying it to the client, and interpreting the response. For this series, these will respectively be referred to as the “builder” and the “displayer.”

First, let’s start off with the most basic of menu systems: AMX Mod’s. This system was carried over into AMX Mod X, but since AMX Mod X has a newer menu system, we will refer to these as “old menus.” Old menus have no building API; you only get a display function.

The first set of problems manifest from not having a building API. The menu display function, show_menu, is a direct wrapper around the ShowMenu network message. You pass it a giant string, a selectable keys bitmask, and a hold time, and Core will split the string into packets and send the message off.

This sort of wrapper does not constitute a menu API:

  • The menu string must be built by the user. This makes cross-mod compatibility cumbersome, as “color” vs “no color” syntaxes and whatnot must be accounted for manually.
  • There is no concept of automated pagination or callbacks; users must implement these themselves.
  • Since the direct display string is handled by every plugin, highly inconsistent code and display styles appear everywhere.
  • Dynamically generated menus require manual string manipulation and selectable key bitmasking.

From an implementation standpoint, it gets worse. Notice that show_menu doesn’t require a callback function. How do you find when your menu gets selected?

Old menus are registered via two functions. The first is register_menuid. This function takes in a string pattern and returns a unique integer, a menu id. The second is register_menucmd. This binds a menu id to a function. When you call show_menu, Core will look through every single string registered with register_menu_id. If it finds one such that it is contained within your show_menu string, it will remember that menu id from the player. Finally, when the player uses “menuselect,” Core will lookup the menu id. Then, it will execute every “menucmd” that is bound to that menu id.

This system is atrocious for two reasons. The first is that it requires every user to have a unique string in their menu display. That is a huge burden on someone with dynamic menus. If the strings aren’t unique, bad things will happen since another command or callback could be assigned. Second, it will break a multi-lingual display. In fact, show_menu has an optional parameter which is a hack around this flaw. This hack lets users create unique menu identifiers that are not related to the menu text itself.

Furthermore, show_menu has no respect for other menus. It will trample whatever is in its way; there is no queuing. It also will not tell you whether or not your menu was trampled by another menu, or whether the client disconnected, or whether the menu timed out client-side.

As you can see, the problems behind this system are legion. The lack of design separation forces users to keep rewriting highly redundant and awkward, complicated code. The poor internal implementation means menus have fundamental flaws and will always be conflicting with each other in multiple ways.

Next article, we’ll see attempts at addressing these problems in later APIs.

KeyValues (SourceMod Scripting)

Monday, May 7th, 2007

Today’s article is a wiki article about KeyValues (SourceMod Scripting).

While we don’t encourage using KeyValues for C++, they work quite nicely in scripts, where event based parsers are more complicated to set up, especially since dynamic structures do not otherwise exist yet.

The original API for KeyValues was very confusing, which was a direct result of Valve’s header being poorly documented. However, the current version of the API is much more useful and covers most of the use cases as easily as possible. The wiki article goes into detail about iteration, traversal, and deletion.

The only noteworthy (and confusing) thing about SourceMod’s KeyValues API is the traversal stack. Why does it maintain an internal stack of how deep you’ve nested? Because the only other solution would be to return a new Handle. Observe the difference:

native bool:KvFindKey(Handle:kv, const String:name[]);
native Handle:KvFindKey(Handle:kv, const String:name[]);

In the second example, the user must explicitly call CloseHandle simply for finding a sub-section. Not only is this extremely annoying, but also inefficient, and would lead to a myriad of memory leaks due to people forgetting to close simple iterations everywhere.

C++ users don’t have to worry about this, of course. This is a consequence of pointers needing to be stuffed through Handles combined with the lack of a garbage collector.

Events in SourceMod

Friday, May 4th, 2007

Today we’re introducing another wiki article: Events (SourceMod Scripting).

Events are one of the nicest additions to HL2, providing a message passing system similar to network messages, but more user friendly and much easier to debug. You’ll notice one major piece missing from the API: enumeration. Event properties are not enumerable.

Unfortunately, this was only a feature in Valve’s original API, IGameEventManager. When Valve added IGameEventManager2 as a more optimized API, they never bothered to expose the KeyValues functionality implicit in IGameEvent (implemented as CGameEvent). Since the original API is deprecated, SourceMod uses the newer version.

Of course, SourceMod’s event API is completely unrelated to AMX Mod X’s register_event, which was based on user messages. The Half-Life 2 game event manager only touches netcode when it transmits events (for which there is a special svc code). (AMX Mod X’s function should have been named register_message from the start.)

ConVars (cvars) in SourceMod

Wednesday, May 2nd, 2007

Today’s article is mostly a wiki addition: ConVars (SourceMod Scripting).

The major difference between SourceMod’s cvar API and AMX Mod X’s is how cvars are addressed. AMX Mod X references cvars by name, a string. SourceMod’s cvar API references by a Handle, which contains the ConVar pointer.

AMX Mod X’s failure to use the HL1 cvar_t pointer is nothing short of horrendous. The only benefit is that it makes coding much easier for newcomers. Unfortunately, it’s a huge performance issue. There are hundreds of cvars, and doing named lookups for every cvar operation is extremely painful, especially if the same cvar is used over and over again.

Even more concerning, it took the AMX Mod X developers (me included) a long time to notice this. Only later in the 1.x branch were “pcvar” natives introduced. These natives dealt with direct cvar_t pointers, and used the engine call SET_CVAR_DIRECT to make changes. One must wonder why HL1 even had SET_CVAR_FLOAT and SET_CVAR_STRING, as it basically encourages using much slower code.

While many people still use AMX Mod X’s name based lookup, “pcvar” usage is encouraged. Of course with SourceMod, it is the only option.

SourceMod maintains similarity with AMX Mod X’s “pcvar” API by using one Handle for every named cvar. If two plugins create or find the same cvar, they will both receive the same Handle. Thus, no plugin owns any cvars, and cvars are not removed until SourceMod unloads. This has a few benefits:

  • You can directly compare cvar Handles. For example, instead of doing a strcmp() call, you can do if (hndl1 == hndl2)
  • If a plugin unloads, the cvar will stick around, so any settings will still be set if the plugin reloads or refreshes.
  • Plugins don’t have to call CloseHandle() simply for finding a ConVar

The other major difference is that HL2 engine passes ConVar changes through a callback. Thus, you can detect changes without making a secondary console command. This was not possible in HL1. Although you could hook SET_CVAR_FLOAT, it was not virtual, and thus internal or plugin usage of it would not be caught. Also, the change callbacks are per-ConVar; HL1′s is global, and thus a bit less optimized.